3 LeapHeap Algorithms

This section sets out the workings of the LeapHeap allocate and free routines, which operate on the LeapHeap data structures presented in section 2 LeapHeap Data Structures. The routines are designed so that threads can run unhindered through them without waiting or sleeping.

At points in the text where a locked atomic operation is required, this is picked out with the assembler mnemonic for a suitable Intel Pentium instruction. Implementations for other processors will use different instructions; in fact the LeapHeap implementation itself differs. A list of the mnemonics used in this guide follows. For multiprocessor implementations the Intel LOCK prefix is understood.

CMPXCHG is normally used in a tight loop, involving a thread reading a memory location, modifying the value in register, then writing it back. The write only proceeds if the content of the memory location is the same as when it was read; if, exceptionally, it has been changed by another thread the original thread has to retry. This coding, though inelegant, is emphatically not the same as spinning on a lock waiting for another thread to release a resource; in a CMPXCHG loop, each retry is overwhelmingly likely to succeed.

There are also operations for which a memory access has to be atomic, but a locked instruction might not be necessary, such as when reading a pointer with the intention of following it. This is a detail left to the implementation; with the Pentium processor simple reads and writes automatically have the required property.

3.1 Bitmap Algorithm
3.2 List Algorithm