Начнем издалека

#pragma pack(1)
typedef struct {
 volatile unsigned __int64 top:46, ocount:18;
} top_aba_t;

desc->Next = queue_head;
queue_head = desc;

 descriptor_queue old_queue, new_queue;
 do {
 old_queue = queue_head;
 desc->Next = (descriptor*)old_queue.DescAvail;
 new_queue.DescAvail = (unsigned __int64)desc;
 new_queue.tag = old_queue.tag + 1;
 } while (!compare_and_swap64k(queue_head, old_queue, new_queue));

Lock-free FIFO queue

// Pseudostructure for lock-free list elements.
// The only requirement is that the 5th-8th byte of
// each element should be available to be used as
// the pointer for the implementation of a singly-linked
// list. 
struct queue_elem_t {
 char *_dummy;
 volatile queue_elem_t *next;
};

typedef struct {
 unsigned __int64 _pad0[8];
 top_aba_t both;
 unsigned __int64 _pad1[8];
} lf_fifo_queue_t;

Оборачиваем работу с атомарными функциями

#define compare_and_swap64k(a,b,c) \
 compare_and_swap64((volatile unsigned __int64*)&(a), \
 *((unsigned __int64*)&(b)), \
 *((unsigned __int64*)&(c)))

Определяем базовые функции работы со списком

static inline int lf_fifo_enqueue(lf_fifo_queue_t *queue, void *element) {
 top_aba_t old_top;
 top_aba_t new_top;
 
 for(;;) {
 old_top.ocount = queue->both.ocount;
 old_top.top = queue->both.top;

 ((queue_elem_t *)element)->next = (queue_elem_t *)old_top.top;
 new_top.top = (unsigned __int64)element;
 new_top.ocount += 1;
 if (compare_and_swap64k(queue->both, old_top, new_top)) 
 return 0;
 }
}

Собственно идея аллокатора

1. Активный суперблок содержит 5 элементов организованных в список, 4 из них доступны для использования.
2. А теперь мы зарезервировали следующий элемент (см credits)
3. И в результате выдали блок номер 5
4. А потом его вернули обратно (но попал он в partial list)

Опишем хип и дескриптор блока

struct Procheap {
 volatile active Active; // initially NULL
 volatile descriptor* Partial; // initially NULL
 sizeclass* sc; // pointer to parent sizeclass
};

struct Descriptor {
 struct queue_elem_t lf_fifo_queue_padding;
 volatile anchor Anchor; // anchor to superblock exact place
 descriptor* Next; // next element in list
 void* sb; // pointer to superblock
 procheap* heap; // pointer to owner procheap
 unsigned int sz; // block size
 unsigned int maxcount; // superblock size / sz
};

Приступим к реализации

__declspec(thread) procheap* heaps[2048 / GRANULARITY]; // = { };
static volatile descriptor_queue queue_head;

Malloc — как это работает

1. Если запрошенный размер не имеет нашего хипа для малых размеров — просто запрашиваем у системы
2. Выделяем память по очереди — сначала из активного списка, затем из списка фрагментов, и наконец — пробуем запросить у системы новый кусок.
3. У нас всегда есть память в системе, а если нет — надо только подождать в цикле

void* my_malloc(size_t sz) { 
 procheap *heap;
 void* addr;

 // Use sz and thread id to find heap.
 heap = find_heap(sz);

 if (!heap) 
 // Large block
 return alloc_large_block(sz);

 for(;;) { 
 addr = MallocFromActive(heap);
 if (addr) return addr;

 addr = MallocFromPartial(heap);
 if (addr) return addr;

 addr = MallocFromNewSB(heap);
 if (addr) return addr;
 } 
}

Memory Block Descriptors

Helpers

static void* AllocNewSB(size_t size, unsigned long alignement) {
 return VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
}

Последний рывок — и выделять / освобождать готов!

void my_free(void* ptr) {
 descriptor* desc;
 void* sb;
 anchor oldanchor, newanchor;
 procheap* heap = NULL;

 if (!ptr) return;
 
 // get prefix
 ptr = (void*)((char*)ptr - HEADER_SIZE); 
 if (*((char*)ptr) == (char)LARGE) {
 munmap(ptr, *((unsigned long *)((char*)ptr + TYPE_SIZE)));
 return;
 }
 desc = *((descriptor**)((char*)ptr + TYPE_SIZE));
 
 sb = desc->sb;
 do { 
 newanchor = oldanchor = desc->Anchor;

 *((unsigned long*)ptr) = oldanchor.avail;
 newanchor.avail = ((char*)ptr - (char*)sb) / desc->sz;

 if (oldanchor.state == FULL) newanchor.state = PARTIAL;

 if (oldanchor.count == desc->maxcount - 1) {
 heap = desc->heap;
 // instruction fence.
 newanchor.state = EMPTY;
 } 
 else 
 ++newanchor.count;

 // memory fence.
 } while (!compare_and_swap64k(desc->Anchor, oldanchor, newanchor));

 if (newanchor.state == EMPTY) {
 munmap(sb, heap->sc->sbsize);
 RemoveEmptyDesc(heap, desc);
 } 
 else if (oldanchor.state == FULL) 
 HeapPutPartial(desc);
}

Выводы

1. Scalable Lock-Free Dynamic Memory Allocation
2. Hoard memory allocator
3. Scalable Locality-ConsciousMultithreaded Memory Allocation

do {
 long snapshot = stack->head;
 long next = snapshot->next;
} while (!cas(&stack->head, next, snapshot));