how to do lock free allocation - per process reservation (4mb split out) - APCG(superblock) - every superblock has its own lock - finding an empty superblock - loop for superblock without owner - if found, mark it as owned - if not found lock on the superblock with oldest atime - mark a block as owned, for the period of a single request - lock(sma) APCG(superblock)->owner = pid/thread id APCG(superblock)->atime = time(0); unlock(sma) - no locks after marking superblock as owned - alloc() checks for ownership held for a max of 1 mins, give up and allocate again - ownership GC in 2 minutes - allocate internal with old algo - first entry in superblock is always a block_tag each block is part of multiple lists size classes - small(0-128) , medium (128-1k), large(1k-...) allocation sizes - multiple of 16 bytes freelist = memchunk; memchunk { header; }; header { memchunk * prev; memchunk * next; size_t size; } allocation - look in correct list - do not reset allocd->prev - skip over self self->prev->next = self->next self->next->prev = self->prev splitting - go up lists, if not found new = self+size new->size = self->size - size + sizeof(memchunk) self->prev->next = new new->prev = self->prev new->next = self->next self->next->prev = new if(new->next > (new->size + new)) allocd = new + new->size allocd->prev = new free'ing - self->prev is a free block or self is the first free block - self->next = self->prev->next - self->prev->next = self - self->next->prev = self merging - if (self->prev + self->prev->size) == self self->prev->next = self->next self->next->prev = self->prev if(self + self->size < self->next) (self + self->size)->prev = self->prev self->prev->size += self->size + sizeof(memchunk) - if (self + self->size == self->next) self->size += self->next->size + sizeof(memchunk) self->next = self->next->next self->next->prev = self if(self + self->size < self->next) (self + self->size)->prev = self if free block has next > (self + size), ((block*)(self + size))->prev has to be self