How to write a thread-safe and efficient, lock-free memory allocator in C?

Question

How to write a thread-safe and efficient, lock-free memory allocator in C? By efficient I mean:

1. Fast allocation & deallocation

2. Optimal memory usage (minimal wastage and no external fragmentation)

3. Minimal meta-data overhead

Answer 1

http://www.research.ibm.com/people/m/michael/pldi-2004.pdf

This paper presents a completely lock-free memory allocator. It uses only widely-available operating system support and hardware atomic instructions. It offers guaranteed availability even under arbitrary thread termination and crash-failure, and it is immune to dead-lock regardless of scheduling policies, and hence it can be used even in interrupt handlers and real-time applications without requiring special scheduler support. Also, by leveraging some high-level structures from Hoard, our allocator is highly scalable, limits space blowup to a constant factor, and is capable of avoiding false sharing...