/*

* Copyright (C) 2009, 2010, 2011 Lockless Inc., Steven Von Fuerst.

*

* This library is free software: you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation, either version 3 of the License, or

* (at your option) any later version.

*

* This library is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details.

*

* You should have received a copy of the GNU General Public License

* along with this program. If not, see <http://www.gnu.org/licenses/>.

*/

/*

* Implement a lockfree allocator based upon lockless queues

* that communicate between processors, and btrees to hold the

* unallocated memory.

*/

#define _GNU_SOURCE

#include "compiler.h"

#include "ll_asm.h"

#include "ll_list.h"

#include <stdarg.h>

#include <stdint.h>

#include <stdlib.h>

#include <string.h>

#ifndef WINDOWS

#include <linux/futex.h>

#include <sys/mman.h>

#include <sys/syscall.h>

#include <unistd.h>

#endif /* !WINDOWS */

#include <errno.h>

#include <fcntl.h>

#include <malloc.h>

#include <stdio.h>

#include <sys/stat.h>

#include <sys/types.h>

#include <unistd.h>

/* Debugging */

// #define DEBUG_ALLOC

/* Extra checking */

// #define DEBUG_ALLOC_SLOW

/* Memory leak debugging */

// #define DEBUG_LEAK

// #define DEBUG_LEAK_DISP 0

/* For windows and valgrind */

// #define EMU_SBRK

// #define EMU_SBRK_VG

/* Turn off slab usage - useful for debugging btree and small alloc code */

// #define DEBUG_NO_SLAB

/* Turn on home-made profiler */

// #define DEBUG_PROFILE

#ifdef DEBUG_PROFILE

#include "prof.h"

#else

#define DECL_PROF_FUNC int __attribute((unused)) profile_dummy

#endif

#ifndef WINDOWS

#define PAGESIZE 4096UL

#else

#define PAGESIZE ((size_t)65536)

#endif

/* Seperator between allocations */

#define SEPSIZE 16

#define PTRSIZE 8

#define HEADERSIZE 32

#define ADDR_SIZE 27

#define SLABSIZE ((uintptr_t)(1 << 17))

// #define SLABBMAX ((SLABSIZE / 8) - 2)

#define SLABBMAX 64 /* About 4M per thread */

/* Slab sizes 0 to 512 bytes in steps of 16 */

#define NUM_SB 33

#define SB_MAX ((NUM_SB - 1) * 16)

/* Maximum size of medium allocations */

#define BTMALLOC ((1L << ADDR_SIZE) - HEADERSIZE)

#define TOP_SIZE (-(PAGESIZE * 2))

/* Minimum size to allocate at a time */

#define MINALLOC (1L << 21)

/* 64 queues */

#define NUM_QS 64

#define QS_MAX (NUM_QS * 16 - SEPSIZE)

/* Only check four fast bins */

#define FAST_MASK 0x0fULL

/* Clear the fast lists at least this often on free() */

#define FREE_FAST ((1 << 16) - 1)

/* The biggest size that can reasonably be stored in the fast lists */

#ifdef __x86_64__

#define FAST_64_BIN 67108863

#else

#define FAST_64_BIN 3669975

#endif

#ifdef __x86_64__

#define MYSIZE_TO_PTR(T, N) ((dlist *)(((char *)T) + offsetof(atls, qs) + N - SEPSIZE))

#else

#define MYSIZE_TO_PTR(T, N) ((dlist *)(((char *)T) + offsetof(atls, qs) + N / 2 - PTRSIZE))

#endif

/* Fast-lists */

#define NUM_FL 64

/* btree size */

#define BT_MAX 16

/* 64bit mask type */

typedef unsigned long long u64b;

/* Pre declare */

typedef struct btree btree;

typedef struct sep sep;

struct sep

{

btree *left;

#ifndef __x86_64__

int pad;

#endif

__extension__ union

{

__extension__ struct

{

unsigned bs_offset;

unsigned size;

};

uintptr_t prev;

};

};

struct btree

{

/* Seperator */

sep s;

__extension__ union

{

slist list;

dlist list2;

void *data;

__extension__ struct

{

btree *parent;

unsigned bsize[BT_MAX + 1];

char prev[BT_MAX + 1];

btree *ptr[BT_MAX];

};

};

#ifndef __x86_64__

unsigned pad;

#endif

};

#ifdef WINDOWS

/* For documentation purposes only */

struct mallinfo

{

/* Total space allocated with sbrk in all threads */

int arena;

/* Number of ordinary (non-slab and non-mmap) allocations */

int ordblks;

/* Number of blocks in this threads slab */

int smblks;

/* Number of mmaped chunks in our thread */

int hblks;

/* Number of btree nodes for our thread */

int hblkhd;

/* Total (possibly partially) used slab blocks */

int usmblks;

/* Total number of free slab blocks */

int fsmblks;

/* Total allocated space for this thread including overhead */

int uordblks;

/* Total free space for this thread in ordinary mmap region */

int fordblks;

/* zero */

int keepcost;

};

#endif

/* Seperator bitflags */

#define FLG_UNUSED 0x01

#define FLG_LUNUSED 0x02

#define FLG_LSIZE8 0x04

#define FLG_SIZE8 0x08

static int b_leaf(btree *b);

#define SEP_INDEX(b, loc, v) (((unsigned char *)&((b)->bsize[loc]))[v])

/* Index into the zeroth int in bsize[] */

#define b_start(b) SEP_INDEX(b, 0, 0)

#define b_pindex(b) SEP_INDEX(b, 0, 1)

#define b_mask(b) (*(unsigned short *)&SEP_INDEX(b, 0, 2))

#define b_next(b, loc) SEP_INDEX(b, loc, 0)

#define b_prev(b, loc) (b->prev[loc])

#define b_last(b) b_prev(b, 0)

#define b_ptr(b, loc) (b->ptr[(loc)-1])

typedef union mealloc mealloc;

union mealloc

{

__extension__ struct

{

slist **tail;

dlist m_list;

};

__extension__ struct

{

char pad[16];

btree b;

};

/* Prevent compiler warning "no named members" */

void *dummy;

};

typedef struct sbheader sbheader;

struct sbheader

{

__extension__ union

{

__extension__ struct

{

slist **tail;

dlist list;

uintptr_t max;

unsigned size;

};

/* First cache line is mostly read-only */

char pad[64];

};

/* Second cache line is read-write */

uintptr_t first;

unsigned used;

#ifndef __x86_64__

u64b dummy; /* padding to get right alignment */

#endif

/* This needs to be 16 byte aligned */

void *data;

};

/* 64k block of pointers to free blocks */

typedef struct freesb freesb;

struct freesb

{

freesb *next;

unsigned count;

sbheader *blocks[SLABBMAX];

};

typedef struct atls atls;

struct atls

{

slist fl[NUM_FL];

u64b f_mask;

#ifndef __x86_64__

unsigned dummy; /* padding to get right q8 alignment */

#endif

/* Note that qs[0] is a miss-aligned btree pointer! */

dlist qs[NUM_QS];

__extension__ union

{

__extension__ struct

{

/* Overlap with the seperator in bheap */

slist btree_freenode;

unsigned b_hgt;

unsigned b_cnt;

};

btree bheap;

};

u64b q_mask;

/* Partially full slabs */

dlist slab[NUM_SB];

dlist slab_full;

freesb *slab_chunk;

size_t percpu_hash;

size_t a_alloced;

size_t s_wanted;

slist *head;

dlist bl;

#ifdef DEBUG_LEAK

int leak_fd;

#endif

/* Hazard list */

dlist h_list;

void *hazard;

/* Deleted list */

atls *d_list;

int fcount;

char callocable;

char dummy3[59];

/* Off by itself to reduce false sharing */

slist *tail;

};

#ifdef USE_DLL

#define PREFIX(X) llalloc##X

#else

#ifdef USE_PREFIX

#define PREFIX(X) llalloc##X

#else

#define PREFIX(X) X

#endif

#endif

#ifndef DEBUG_ALLOC

#define always_inline inline __attribute__((always_inline))

#else

#define always_inline

#endif

/* This ISO C11 function might not have a prototype in older headers */

void *aligned_alloc(size_t alignment, size_t size);

#ifdef WINDOWS

void llmutex_lock(void *l);

void llmutex_unlock(void *l);

int llmutex_trylock(void *l);

typedef void *mutex_t;

#define mutex_lock llmutex_lock

#define mutex_unlock llmutex_unlock

#define mutex_trylock llmutex_trylock

#define MUTEX_INITIALIZER \

{ \

0 \

}

#ifndef EMU_SBRK

#define EMU_SBRK

#endif

#define set_enomem() _set_errno(ENOMEM)

/* Other functions that need prototypes */

#if defined USE_DLL || defined USE_PREFIX

void llallocfree(void *p);

void *llallocmalloc(size_t size);

void *llalloccalloc(size_t size, size_t n);

void *llallocrealloc(void *p, size_t size);

size_t llalloc_msize(void *p);

void *llalloc_expand(void *p, size_t size);

/* Hack - indirect calls to crt functions */

int (*__callnewh)(size_t);

int (*__newmode)(void);

#endif /* USE_DLL */

void cfree(void *p);

void *memalign(size_t align, size_t size);

int posix_memalign(void **p, size_t align, size_t size);

void *valloc(size_t size);

void *pvalloc(size_t size);

struct mallinfo mallinfo(void);

int malloc_trim(size_t pad);

int mallopt(int param, int val);

void *PREFIX(_calloc_impl)(size_t n, size_t size, int *errno_tmp);

void PREFIX(_free_nolock)(void *p);

void *PREFIX(_realloc_nolock)(void *p, size_t size);

void *PREFIX(_calloc_nolock)(size_t n, size_t size);

size_t PREFIX(_msize_nolock)(void *p);

static size_t malloc_usable_size(void *p);

void __tlregdtor(void (*)(void *));

#else /* WINDOWS */

static int sys_futex(void *addr1, int op, int val1, struct timespec *timeout, void *addr2, int val3)

{

return syscall(SYS_futex, addr1, op, val1, timeout, addr2, val3);

}

#define cmpxchg(P, O, N) __sync_val_compare_and_swap((P), (O), (N))

typedef union mutex_t mutex_t;

union mutex_t

{

unsigned u;

struct

{

unsigned char locked;

unsigned char contended;

} b;

};

static void mutex_init(mutex_t *m)

{

m->u = 0;

}

static void mutex_lock(mutex_t *m)

{

int i;

/* Try to grab lock */

for (i = 0; i < 100; i++)

{

if (!xchg_8(&m->b.locked, 1))

return;

cpu_relax();

}

/* Have to sleep */

while (xchg_32(&m->u, 257) & 1)

{

sys_futex(m, FUTEX_WAIT_PRIVATE, 257, NULL, NULL, 0);

}

}

static void mutex_unlock(mutex_t *m)

{

DECL_PROF_FUNC;

int i;

/* Locked and not contended */

if ((m->u == 1) && (cmpxchg(&m->u, 1, 0) == 1))

return;

/* Unlock */

m->b.locked = 0;

barrier();

/* Spin and hope someone takes the lock */

for (i = 0; i < 200; i++)

{

if (m->b.locked)

return;

cpu_relax();

}

/* We need to wake someone up */

m->b.contended = 0;

sys_futex(m, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);

}

static int mutex_trylock(mutex_t *m)

{

unsigned c;

if (m->b.locked)

return EBUSY;

c = xchg_8(&m->b.locked, 1);

if (!c)

return 0;

return EBUSY;

}

#define MUTEX_INITIALIZER \

{ \

0 \

}

/* Interface for hooks, if needed */

#ifdef USE_ALLOC_HOOK

#include "ll_alloc_hook.c"

#endif

static void malloc_stats_aux(int show_nodes);

static gcc_used char dummy1[64];

static pthread_once_t init_once = PTHREAD_ONCE_INIT;

static pthread_key_t death_key;

/*

* If pthread isn't linked in,

* have weak replacements for the single-threaded case

*/

#pragma weak pthread_atfork

#pragma weak pthread_key_create

#pragma weak pthread_setspecific

#pragma weak pthread_once

#define set_enomem() (errno = ENOMEM)

#endif /* WINDOWS */

typedef union percpu_list percpu_list;

union percpu_list

{

__extension__ struct

{

mutex_t m;

freesb *list;

};

char pad[64];

};

/* Global thread hazard list */

static cache_align mutex_t h_lock = MUTEX_INITIALIZER;

static dlist h_list = DLIST_INIT(h_list);

static cache_align mutex_t d_lock = MUTEX_INITIALIZER;

static atls *d_list = NULL;

/* List of freed slab blocks */

static cache_align percpu_list *pc_slab;

static size_t cpu_total;

/* sbrk information */

#ifndef HOOK_SBRK

static cache_align mutex_t sb_lock = MUTEX_INITIALIZER;

static cache_align uintptr_t sbrk_start = 0;

static uintptr_t sbrk_size = 0;

static int sbrk_oom = 0;

#endif /* HOOK_SBRK */

static unsigned sltotal[NUM_SB];

#ifdef DEBUG_LEAK

#define LEAK_MAX 1024

typedef struct bigallocs bigallocs;

struct bigallocs

{

void *p;

size_t size;

};

static bigallocs big_leak[LEAK_MAX] = {{NULL, 0}};

static mutex_t l_lock = MUTEX_INITIALIZER;

#endif

/* Hack */

#define BUILD_ASSERT(C) \

do \

{ \

switch (0) \

{ \

case 0:; \

case (C):; \

} \

} while (0)

/* Pre-declares */

static always_inline void *split_node(atls *tl, btree *b, size_t t_size, size_t size);

static void merge_node(atls *tl, void *p);

static int init_sldata(void);

static void slab_free(atls *tl, void *p);

static void local_free(atls *tl, void *p);

static void *local_alloc(atls *tl, size_t size);

static void *slab_alloc_safe(atls *tl, size_t size);

static always_inline void *fast_alloc(atls *tl, size_t size);

static void *slow_alloc(atls *tl, size_t size);

static void atls_merge(atls *tl1, atls *tl2);

static void test_all(atls *tl);

static void *zalloc(atls *tl, size_t size);

void **independent_calloc(size_t n, size_t size, void **chunks);

void **independent_comalloc(size_t n, size_t *sizes, void **chunks);

static inline btree *small_next(btree *b)

{

return b->data;

}

static inline void set_small_next(btree *b, btree *next)

{

b->data = next;

}

#ifdef __x86_64__

static inline btree *small_prev(btree *b)

{

return (btree *)(b->s.prev & ~15);

}

static inline void set_small_prev(btree *b, btree *prev)

{

uintptr_t p = b->s.prev & 15;

b->s.prev = p + (uintptr_t)prev;

}

#else

static inline btree *small_prev(btree *b)

{

return (btree *)b->s.size;

}

static inline void set_small_prev(btree *b, btree *prev)

{

b->s.size = (unsigned)prev;

}

#endif

static inline void *shift(void *p, size_t s)

{

return &(((char *)p)[s]);

}

/* Unfortunately, TLS support with mingw is totally broken... so we need to emulate it */

#ifdef WINDOWS

static DWORD tls_index = TLS_OUT_OF_INDEXES;

static atls *get_tls(void)

{

if (tls_index == TLS_OUT_OF_INDEXES)

return NULL;

return TlsGetValue(tls_index);

}

static void set_tls(atls *tls)

{

TlsSetValue(tls_index, tls);

}

#else

#ifndef USE_ALLOC_HOOK

static __thread__ atls *tls = NULL;

#define get_tls() tls

#define set_tls(T) (tls = (T))

#endif

#endif

static size_t cpu_num(void)

{

#ifdef WINDOWS

SYSTEM_INFO info;

GetSystemInfo(&info);

return info.dwNumberOfProcessors;

#else

#ifdef SYS_MACOSX

int num;

size_t len = sizeof(num);

if (sysctlbyname("hw.ncpu", &num, &len, NULL, 0))

num = 1;

return num;

#else

return sysconf(_SC_NPROCESSORS_ONLN);

#endif /* SYS_MACOSX */

#endif /* WINDOWS */

}

/*

* Emulate sbrk()

* Assumes we are called under a lock */

#ifdef EMU_SBRK

#ifdef EMU_SBRK_VG

#define SBRK_SIZE (1ULL << 30)

#else /* EMU_SBRK_VG */

#ifdef __x86_64__

/* Default to 32GiB of sbrk space */

#define SBRK_SIZE (1ULL << 37)

#else /* __x86_64__ */

/* Default to 1GiB of sbrk space */

#define SBRK_SIZE (1ULL << 30)

#endif /* __x86_64__ */

#endif /* EMU_SBRK_VG */

static void *sbrk_mmap_base = NULL;

static void *sbrk_mmap_end = 0;

static void init_sbrk(void)

{

DECL_PROF_FUNC;

size_t size = SBRK_SIZE;

while (1)

{

#ifndef WINDOWS

sbrk_mmap_base = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0);

#else

/* Allocate address space - but no memory */

sbrk_mmap_base = VirtualAlloc(NULL, size, MEM_RESERVE, PAGE_READWRITE);

#endif

if (sbrk_mmap_base == MAP_FAILED)

{

sbrk_mmap_base = NULL;

size = size / 2;

if (size < 65536)

return;

}

else

{

sbrk_mmap_end = shift(sbrk_mmap_base, size);

return;

}

}

}

static void *emu_sbrk(size_t size)

{

DECL_PROF_FUNC;

void *out;

/* Hack - initialize if required */

if (!size)

init_sbrk();

if (!sbrk_mmap_base)

return MAP_FAILED;

out = sbrk_mmap_base;

sbrk_mmap_base = shift(sbrk_mmap_base, size);

if (sbrk_mmap_base >= sbrk_mmap_end)

{

sbrk_mmap_base = out;

return MAP_FAILED;

}

#ifdef WINDOWS

/* Enable memory */

VirtualAlloc(out, size, MEM_COMMIT, PAGE_READWRITE);

#endif

return out;

}

#define sbrk(S) emu_sbrk(S)

#endif

#ifndef HOOK_SBRK

static inline void init_sbrk_start(void)

{

void *v = sbrk(0);

sbrk_start = (uintptr_t)v;

}

#endif

static inline int is_slab(void *p)

{

return ((uintptr_t)p - sbrk_start < sbrk_size);

}

static inline void *page_start(void *p)

{

return (void *)(-PAGESIZE & (uintptr_t)p);

}

static inline size_t page_align(size_t s)

{

return -PAGESIZE & (s + PAGESIZE - 1);

}

static inline size_t sep_align(size_t s)

{

/*

* We want to align on 16byte boundaries

*

* 16 -> 16

* 24 -> 16

* 25 -> 32

* 32 -> 32

*/

/*

* Then we want to include the extra 8 bytes of last ptr that are free.

* Finally, we want to include the following sep data.

*/

/*

* 0 -> 16

* 8 -> 16

* 9 -> 32

* 16 -> 32

* 24 -> 32

* 25 -> 48

* 32 -> 48

* 40 -> 48

*/

return (s + 7 + 16) & ~15;

}

static inline int un_used(btree *b)

{

return (b->s.bs_offset & FLG_UNUSED);

}

static inline int left_unused(btree *b)

{

return b->s.bs_offset & FLG_LUNUSED;

}

static inline void set_unused(btree *b, btree *br)

{

br->s.bs_offset |= FLG_LUNUSED;

br->s.left = b;

b->s.bs_offset |= FLG_UNUSED;

}

static inline void set_used(btree *b, size_t size)

{

btree *br = shift(b, size);

br->s.bs_offset &= ~FLG_LUNUSED;

#ifdef DEBUG_ALLOC_SLOW

if (size != b->s.size)

errx(1, "size missmatch\n");

#endif

b->s.bs_offset &= ~FLG_UNUSED;

}

static inline void set_size8(btree *b)

{

btree *br = shift(b, 16);

br->s.bs_offset |= FLG_LSIZE8;

b->s.bs_offset |= FLG_SIZE8;

}

static inline void unset_size8(btree *b)

{

btree *br = shift(b, 16);

br->s.bs_offset &= ~FLG_LSIZE8;

b->s.bs_offset &= ~FLG_SIZE8;

b->s.size = 16;

b->s.bs_offset &= 15;

b->s.bs_offset += (br->s.bs_offset & ~15) - 16;

}

#ifdef __x86_64__

static inline btree *get_q8(atls *tl)

{

/* Mega hack - align so that we return a btree object pointer to the correct memory locations */

return shift(&tl->qs[0], -(uintptr_t)8);

}

#else

static inline btree *get_q8(atls *tl)

{

/* Mega hack - align so that we return a btree object pointer to the correct memory locations */

return shift(&tl->qs[0], -(uintptr_t)12);

}

#endif

static inline btree *read_left(btree *b)

{

if (!left_unused(b))

return NULL;

if (b->s.bs_offset & FLG_LSIZE8)

return shift(b, -(uintptr_t)16);

return b->s.left;

}

static inline mealloc *read_bs(btree *b)

{

uintptr_t s = b->s.bs_offset & ~15;

#ifdef DEBUG_ALLOC_SLOW

void *v = shift(b, -s);

if ((PAGESIZE - 1) & (uintptr_t)v)

errx(1, "mealloc misaligned\n");

#endif

return (mealloc *)shift(b, -s);

}

static void btree_init(btree *b)

{

/* Init header */

// b_start(b) = 0;

b_mask(b) = -1;

// b_pindex(b) = 0;

// b_last(b) = 0;

}

static inline void set_sep(btree *b, int size, btree *bo)

{

unsigned offset = bo->s.bs_offset & ~15;

/* Store split block offset + size + used indicators */

b->s.bs_offset = offset + ((uintptr_t)b - (uintptr_t)bo);

b->s.size = size;

}

#ifdef DEBUG_ALLOC

static void check_sep(btree *b)

{

btree *br = shift(b, b->s.size);

if (((uintptr_t)b) & 15)

errx(1, "btree misaligned\n");

if (is_slab(&b->data))

errx(1, "btree slab overlap\n");

/* Test unused bit */

if (un_used(b))

{

if (b->s.bs_offset & FLG_SIZE8)

{

br = shift(b, 16);

if (!(br->s.bs_offset & FLG_LSIZE8))

errx(1, "size8 bit missmatch\n");

}

else

{

if (b->s.size & 15)

errx(1, "mysize misaligned\n");

if ((b->s.size == 16) || (br->s.bs_offset & FLG_LSIZE8))

errx(1, "size8 bit missmatch\n");

if (read_left(br) != b)

errx(1, "left pointer wrong\n");

}

if (!left_unused(br))

errx(1, "Unused flag conflict\n");

}

else

{

if (b->s.size & 15)

errx(1, "mysize misaligned\n");

if (left_unused(br))

errx(1, "Unused flag conflict\n");

}

}

#else

#define check_sep(B) ((void)sizeof(B))

#endif

#ifndef WINDOWS

static __attribute__((format(gnu_printf, 2, 3))) void leak_print(atls *tl, const char *format, ...)

{

char buf[1024];

va_list ap;

va_start(ap, format);