With that reasoning, you should write your own kernel too -- you realize that the kernel scheduler will take locks at some point, right?
I think that malloc is a sufficiently abstract operation here that its implementation shouldn't constitute whether the algorithm as a whole is lock-free or not.