New malloc implementation

Question

I've written a new malloc implementation similar to dlmalloc and was hoping for feedback on it.

The goals for this library are:

• Easy to read and maintain
• Be more memory conserving
• High efficiency and good performance
• Portability

The documentation is here and the code could be found here.

/********************** mallocstate config begin **********/

/*!
 * Decide to use or not use locks
 */
#if !defined(AKMALLOC_USE_LOCKS) || AKMALLOC_USE_LOCKS
#  define AK_MALLOCSTATE_USE_LOCKS
#endif

#if defined(AK_MALLOCSTATE_USE_LOCKS)
#  define AK_SLAB_USE_LOCKS
#  define AK_CA_USE_LOCKS
#  define AKMALLOC_LOCK_DEFINE(nm)  ak_spinlock nm
#  define AKMALLOC_LOCK_INIT(lk)    ak_spinlock_init((lk))
#  define AKMALLOC_LOCK_ACQUIRE(lk) ak_spinlock_acquire((lk))
#  define AKMALLOC_LOCK_RELEASE(lk) ak_spinlock_release((lk))
#else
#  define AKMALLOC_LOCK_DEFINE(nm)
#  define AKMALLOC_LOCK_INIT(lk)
#  define AKMALLOC_LOCK_ACQUIRE(lk)
#  define AKMALLOC_LOCK_RELEASE(lk)
#endif

#if !defined(AK_COALESCE_SEGMENT_GRANULARITY)
#  define AK_COALESCE_SEGMENT_GRANULARITY (((size_t)1) << 18) /* 256KB */
#endif

#if !defined(AK_SEG_CBK_DEFINED)
/**
 * Gets a pointer to a memory segment and its size.
 * \param p; Pointer to segment memory.
 * \param sz; Number of bytes in the segment.
 * 
 * \return \c 0 to stop iteration, non-zero to continue.
 */
typedef int(*ak_seg_cbk)(const void*, size_t);
#endif

/********************** mallocstate config end ************/

/********************** slab begin **********************/

typedef struct ak_slab_tag ak_slab;

typedef struct ak_slab_root_tag ak_slab_root;

#if defined(AK_SLAB_USE_LOCKS)
#  define AK_SLAB_LOCK_DEFINE(nm)    ak_spinlock nm
#  define AK_SLAB_LOCK_INIT(root)    ak_spinlock_init(ak_as_ptr((root)->LOCKED))
#  define AK_SLAB_LOCK_ACQUIRE(root) ak_spinlock_acquire(ak_as_ptr((root)->LOCKED))
#  define AK_SLAB_LOCK_RELEASE(root) ak_spinlock_release(ak_as_ptr((root)->LOCKED))
#else
#  define AK_SLAB_LOCK_DEFINE(nm)
#  define AK_SLAB_LOCK_INIT(root)
#  define AK_SLAB_LOCK_ACQUIRE(root)
#  define AK_SLAB_LOCK_RELEASE(root)
#endif

struct ak_slab_tag
{
    ak_slab*      fd;
    ak_slab*      bk;
    ak_slab_root* root;
    ak_bitset512  avail;
    void*         _unused;
};

/*!
 * Slab allocator
 */
struct ak_slab_root_tag
{
    ak_u32 sz;                      /**< the size of elements in this slab */
    ak_u32 npages;                  /**< number of pages to obtain from the OS */
    ak_u32 navail;                  /**< max number of available bits for the slab size \p sz */
    ak_u32 nempty;                  /**< number of empty pages */
    ak_u32 release;                 /**< number of accumulated free empty pages since last release */
    ak_u32 _unused;                 /**< for alignment */

    ak_slab partial_root;           /**< root of the partially filled slab list*/
    ak_slab full_root;              /**< root of the full slab list */
    ak_slab empty_root;             /**< root of the empty slab list */

    ak_u32 RELEASE_RATE;            /**< number of pages moved to empty before a release */
    ak_u32 MAX_PAGES_TO_FREE;       /**< number of pages to free when release happens */
    AK_SLAB_LOCK_DEFINE(LOCKED);    /**< lock for this allocator if locks are enabled */
};

#if !defined(AK_SLAB_RELEASE_RATE)
#  define AK_SLAB_RELEASE_RATE 127
#endif

#if !defined(AK_SLAB_MAX_PAGES_TO_FREE)
#  define AK_SLAB_MAX_PAGES_TO_FREE AK_SLAB_RELEASE_RATE
#endif

/**************************************************************/
/* P R I V A T E                                              */
/**************************************************************/

#define ak_slab_unlink(slab)               \
  do {                                     \
    ak_slab* const sU = (slab);            \
    sU->bk->fd = (sU->fd);                 \
    sU->fd->bk = (sU->bk);                 \
    sU->fd = sU->bk = AK_NULLPTR;          \
  } while (0)

#define ak_slab_link_fd(slab, fwd)         \
  do {                                     \
    ak_slab* const sLF = (slab);           \
    ak_slab* const fLF = (fwd);            \
    sLF->fd = fLF;                         \
    fLF->bk = sLF;                         \
  } while (0)

#define ak_slab_link_bk(slab, back)        \
  do {                                     \
    ak_slab* const sLB = (slab);           \
    ak_slab* const bLB = (back);           \
    sLB->bk = bLB;                         \
    bLB->fd = sLB;                         \
  } while (0)

#define ak_slab_link(slab, fwd, back)      \
  do {                                     \
    ak_slab* const sL = (slab);            \
    ak_slab* const fL = (fwd);             \
    ak_slab* const bL = (back);            \
    ak_slab_link_bk(sL, bL);               \
    ak_slab_link_fd(sL, fL);               \
  } while (0)

ak_inline static void ak_slab_init_chain_head(ak_slab* s, ak_slab_root* rootp)
{
    s->fd = s->bk = s;
    s->root = rootp;
    ak_bitset512_clear_all(&(s->avail));
}

ak_inline static ak_sz ak_num_pages_for_sz(ak_sz sz)
{
    return (sz)/4;
}

#define ak_slab_init(m, s, av, r)                                             \
  do {                                                                        \
    void* slabmem = (m);                                                      \
    ak_sz slabsz = (s);                                                       \
    ak_sz slabnavail = (av);                                                  \
    ak_slab_root* slabroot = (r);                                             \
                                                                              \
    AKMALLOC_ASSERT(slabmem);                                                 \
    AKMALLOC_ASSERT(slabsz < (AKMALLOC_DEFAULT_PAGE_SIZE - sizeof(ak_slab))); \
    AKMALLOC_ASSERT(slabsz > 0);                                              \
    AKMALLOC_ASSERT(slabsz % 2 == 0);                                         \
                                                                              \
    AKMALLOC_ASSERT(slabnavail < 512);                                        \
    AKMALLOC_ASSERT(slabnavail > 0);                                          \
                                                                              \
    ak_slab* s = (ak_slab*)slabmem;                                           \
    s->fd = s->bk = AK_NULLPTR;                                               \
    s->root = slabroot;                                                       \
    ak_bitset512_clear_all(&(s->avail));                                      \
    int inavail = (int)slabnavail;                                            \
    for (int i = 0; i < inavail; ++i) {                                       \
        ak_bitset512_set(&(s->avail), i);                                     \
    }                                                                         \
    (void)slabsz;                                                             \
  } while (0)

ak_inline static ak_slab* ak_slab_new_init(char* mem, ak_sz sz, ak_sz navail, ak_slab* fd, ak_slab* bk, ak_slab_root* root)
{
    ak_slab_init(mem, sz, navail, root);
    ak_slab* slab = ak_ptr_cast(ak_slab, mem);
    ak_slab_link(slab, fd, bk);
    return slab;
}

static ak_slab* ak_slab_new_alloc(ak_sz sz, ak_slab* fd, ak_slab* bk, ak_slab_root* root)
{
    const int NPAGES = root->npages;

    // try to acquire a page and fit as many slabs as possible in
    char* const mem = (char*)ak_os_alloc(NPAGES * AKMALLOC_DEFAULT_PAGE_SIZE);
    {// return if no mem
        if (ak_unlikely(!mem)) { return AK_NULLPTR; }
    }

    ak_sz navail = root->navail;

    char* cmem = mem;
    for (int i = 0; i < NPAGES - 1; ++i) {
        ak_slab* nextpage = ak_ptr_cast(ak_slab, (cmem + AKMALLOC_DEFAULT_PAGE_SIZE));
        ak_slab* curr = ak_slab_new_init(cmem, sz, navail, nextpage, bk, root);
        AKMALLOC_ASSERT(ak_bitset512_num_trailing_ones(&(curr->avail)) == (int)navail);
        (void)curr;
        bk = nextpage;
        cmem += AKMALLOC_DEFAULT_PAGE_SIZE;
    }

    ak_slab_new_init(cmem, sz, navail, fd, bk, root);

    return ak_ptr_cast(ak_slab, mem);
}

static ak_slab* ak_slab_new_reuse(ak_sz sz, ak_slab* fd, ak_slab* bk, ak_slab_root* root)
{
    AKMALLOC_ASSERT(root->nempty >= 1);

    ak_sz navail = root->navail;
    ak_slab* const curr = root->empty_root.fd;
    ak_slab_unlink(curr);
    ak_slab_new_init((char*)curr, sz, navail, fd, bk, root);

    --(root->nempty);

    return curr;
}

ak_inline static ak_slab* ak_slab_new(ak_sz sz, ak_slab* fd, ak_slab* bk, ak_slab_root* root)
{
    return (root->nempty > 0)
                ? ak_slab_new_reuse(sz, fd, bk, root)
                : ak_slab_new_alloc(sz, fd, bk, root);
}

#define ak_slab_2_mem(s) (char*)(void*)((s) + 1)

ak_inline static int ak_slab_all_free(ak_slab* s)
{
    const ak_bitset512* pavail = &(s->avail);
    ak_u32 nto;
    ak_bitset512_fill_num_trailing_ones(pavail, nto);
    return nto == s->root->navail;
}

ak_inline static int ak_slab_none_free(ak_slab* s)
{
    const ak_bitset512* pavail = &(s->avail);
    int ntz;
    ak_bitset512_fill_num_trailing_zeros(pavail, ntz);
    return ntz == 512;
}

static void* ak_slab_search(ak_slab* s, ak_sz sz, ak_u32 navail, ak_slab** pslab, int* pntz)
{
    const ak_slab* const root = s;
    void* mem = AK_NULLPTR;
    if (ak_likely(s->fd != root)) {
        AKMALLOC_ASSERT(pslab);
        AKMALLOC_ASSERT(pntz);
        s = s->fd;

        // partial list entry must not be full
        AKMALLOC_ASSERT(ak_bitset512_num_trailing_zeros(&(s->avail)) != 512);

        const ak_bitset512* pavail = &(s->avail);
        int ntz;
        ak_bitset512_fill_num_trailing_zeros(pavail, ntz);

        AKMALLOC_ASSERT(ak_bitset512_get(&(s->avail), ntz));
        ak_bitset512_clear(&(s->avail), ntz);
        mem = ak_slab_2_mem(s) + (ntz * sz);

        *pslab = s;
        if (ntz == (int)navail - 1) {
            ntz = 512;
        } else {
            ak_bitset512_fill_num_trailing_zeros(pavail, ntz);
        }
        *pntz = ntz;
    }
    return mem;
}

static void ak_slab_release_pages(ak_slab_root* root, ak_slab* s, ak_u32 numtofree)
{
    ak_slab* const r = s;
    ak_slab* next = AK_NULLPTR;
    s = s->fd;
    for (ak_u32 ct = 0; ct < numtofree; ++ct) {
        if (s == r) {
            break;
        } else {
            next = s->fd;
        }
        ak_slab_unlink(s);
        ak_os_free(s, AKMALLOC_DEFAULT_PAGE_SIZE);
        s = next;
    }
}

ak_inline static void ak_slab_release_os_mem(ak_slab_root* root)
{
    ak_u32 numtofree = root->nempty;
    numtofree = (numtofree > root->MAX_PAGES_TO_FREE)
                    ? root->MAX_PAGES_TO_FREE
                    : numtofree;
    ak_slab_release_pages(root, &(root->empty_root), numtofree);
    root->nempty -= numtofree;
    root->release = 0;
}

/**************************************************************/
/* P U B L I C                                                */
/**************************************************************/

/*!
 * Initialize a slab allocator.
 * \param s; Pointer to the allocator root to initialize (non-NULL)
 * \param sz; Size of the slab elements (maximum allowed is 4000)
 * \param npages; Number of pages to allocate from the OS at once.
 * \param relrate; Release rate, \ref akmallocDox
 * \param maxpagefree; Number of segments to free upon release, \ref akmallocDox
 */
static void ak_slab_init_root(ak_slab_root* s, ak_sz sz, ak_u32 npages, ak_u32 relrate, ak_u32 maxpagefree)
{
    s->sz = (ak_u32)sz;
    s->navail = (ak_u32)(AKMALLOC_DEFAULT_PAGE_SIZE - sizeof(ak_slab))/(ak_u32)sz;
    s->npages = npages;
    s->nempty = 0;
    s->release = 0;

    ak_slab_init_chain_head(&(s->partial_root), s);
    ak_slab_init_chain_head(&(s->full_root), s);
    ak_slab_init_chain_head(&(s->empty_root), s);

    s->RELEASE_RATE = relrate;
    s->MAX_PAGES_TO_FREE = maxpagefree;
    AK_SLAB_LOCK_INIT(s);
}

/*!
 * Default initialize a slab allocator.
 * \param s; Pointer to the allocator root to initialize (non-NULL)
 * \param sz; Size of the slab elements (maximum allowed is 4000)
 */
ak_inline static void ak_slab_init_root_default(ak_slab_root* s, ak_sz sz)
{
    ak_slab_init_root(s, sz, (ak_u32)ak_num_pages_for_sz(sz), (ak_u32)(AK_SLAB_RELEASE_RATE), (ak_u32)(AK_SLAB_MAX_PAGES_TO_FREE));
}

/*!
 * Attempt to allocate memory from the slab allocator root.
 * \param root; Pointer to the allocator root
 *
 * \return \c 0 on failure, else pointer to at least \p root->sz bytes of memory.
 */
ak_inline static void* ak_slab_alloc(ak_slab_root* root)
{
    int ntz = 0;
    ak_slab* slab = AK_NULLPTR;

    AK_SLAB_LOCK_ACQUIRE(root);
    const ak_sz sz = root->sz;

    void* mem = ak_slab_search(&(root->partial_root), sz, root->navail, &slab, &ntz);

    if (ak_unlikely(!mem)) {
        slab = ak_slab_new(sz, root->partial_root.fd, &(root->partial_root), root);
        if (ak_likely(slab)) {
            AKMALLOC_ASSERT(ak_bitset512_get(&(slab->avail), 0));
            ak_bitset512_clear(&(slab->avail), 0);
            mem = ak_slab_2_mem(slab);
        }
    } else if (ak_unlikely(ntz == 512)) {
        ak_slab_unlink(slab);
        ak_slab_link(slab, root->full_root.fd, &(root->full_root));
    }

    AK_SLAB_LOCK_RELEASE(root);

    return mem;
}

/*!
 * Return memory to the slab allocator root.
 * \param p; Pointer to the memory to return.
 */
ak_inline static void ak_slab_free(void* p)
{
    char* mem = (char*)p;

    // round to page
    ak_slab* slab = (ak_slab*)(ak_page_start_before(p));
    AKMALLOC_ASSERT(slab->root);

    ak_slab_root* root = slab->root;
    AK_SLAB_LOCK_ACQUIRE(root);

    int movetopartial = ak_slab_none_free(slab);
    const ak_sz sz = root->sz;

    int idx = (int)(mem - (char*)ak_slab_2_mem(slab))/(int)sz;
    AKMALLOC_ASSERT(!ak_bitset512_get(&(slab->avail), idx));
    ak_bitset512_set(&(slab->avail), idx);

    if (ak_unlikely(movetopartial)) {
        // put at the back of the partial list so the full ones
        // appear at the front
        ak_slab_unlink(slab);
        ak_slab_link(slab, &(root->partial_root), root->partial_root.bk);
    } else if (ak_unlikely(ak_slab_all_free(slab))) {
        ak_slab_unlink(slab);
        ak_slab_link(slab, root->empty_root.fd, &(root->empty_root));
        ++(root->nempty); ++(root->release);
        if (root->release >= root->RELEASE_RATE) {
            ak_slab_release_os_mem(root);
        }
    }

    AK_SLAB_LOCK_RELEASE(root);
}

/*!
 * Destroy the slab allocator root and return all memory to the OS.
 * \param root; Pointer to the allocator root
 */
static void ak_slab_destroy(ak_slab_root* root)
{
    ak_slab_release_pages(root, &(root->empty_root), AK_U32_MAX);
    ak_slab_release_pages(root, &(root->partial_root), AK_U32_MAX);
    ak_slab_release_pages(root, &(root->full_root), AK_U32_MAX);
    root->nempty = 0;
    root->release = 0;
}
/********************** slab end ************************/

/********************** coalescing allocator begin **********************/

/**
 * We choose a minimum alignment of 16. One could increase this, but not decrease.
 *
 * 16 byte alignment buys us a few things:
 * -# The 3 low-bits of an address will be 000. Therefore we can store metadata in them.
 * -# On x64, we can exactly store two pointers worth of information in any block which
 *    can be used to house an implicit free list.
 */
#define AK_COALESCE_ALIGN 16

#if !defined(AK_COALESCE_SEGMENT_GRANULARITY)
#  define AK_COALESCE_SEGMENT_GRANULARITY 65536
#endif

#if !defined(AK_COALESCE_SEGMENT_SIZE)
/* 64KB */
#  define AK_COALESCE_SEGMENT_SIZE AK_COALESCE_SEGMENT_GRANULARITY
#endif

#if defined(AK_CA_USE_LOCKS)
#  define AK_CA_LOCK_DEFINE(nm)    ak_spinlock nm
#  define AK_CA_LOCK_INIT(root)    ak_spinlock_init(ak_as_ptr((root)->LOCKED))
#  define AK_CA_LOCK_ACQUIRE(root) ak_spinlock_acquire(ak_as_ptr((root)->LOCKED))
#  define AK_CA_LOCK_RELEASE(root) ak_spinlock_release(ak_as_ptr((root)->LOCKED))
#else
#  define AK_CA_LOCK_DEFINE(nm)
#  define AK_CA_LOCK_INIT(root)
#  define AK_CA_LOCK_ACQUIRE(root)
#  define AK_CA_LOCK_RELEASE(root)
#endif

typedef ak_sz ak_alloc_info;

typedef struct ak_alloc_node_tag ak_alloc_node;

typedef struct ak_free_list_node_tag ak_free_list_node;

typedef struct ak_ca_segment_tag ak_ca_segment;

typedef struct ak_ca_root_tag ak_ca_root;

struct ak_alloc_node_tag
{
#if AKMALLOC_BITNESS == 32
    ak_alloc_info _unused0;
    ak_alloc_info _unused1;
#endif
    ak_alloc_info previnfo;
    ak_alloc_info currinfo;
};

struct ak_free_list_node_tag
{
    ak_free_list_node* bk;
    ak_free_list_node* fd;
};

struct ak_ca_segment_tag
{
    ak_ca_segment* bk;
    ak_ca_segment* fd;
    ak_sz sz;
    ak_alloc_node* head;
};

/*!
 * The root for a coalescing allocator.
 */
struct ak_ca_root_tag
{
    ak_ca_segment main_root;        /**< root of non empty segments */
    ak_ca_segment empty_root;       /**< root of empty segments */

    ak_free_list_node free_root;    /**< root of the free list */

    ak_u32 nempty;                  /**< number of empty segments */
    ak_u32 release;                 /**< number of segments freed since last release */

    ak_u32 RELEASE_RATE;            /**< release rate for this root */
    ak_u32 MAX_SEGMENTS_TO_FREE;    /**< number of segments to free when release is done */
    ak_sz MIN_SIZE_TO_SPLIT;        /**< minimum size of split node to decide whether to 
                                         split a free list node */

    AK_CA_LOCK_DEFINE(LOCKED);      /**< lock for this allocator if locks are enabled */
};

/**************************************************************/
/* P R I V A T E                                              */
/**************************************************************/

#define ak_ca_to_sz(p) (((ak_sz)(p)) & ~(AK_COALESCE_ALIGN - 1))

#define ak_ca_is_first(p) (((ak_sz)(p)) & (AK_SZ_ONE << 0))

#define ak_ca_is_last(p) (((ak_sz)(p)) & (AK_SZ_ONE << 1))

#define ak_ca_is_free(p) (((ak_sz)(p)) & (AK_SZ_ONE << 2))

ak_inline static void ak_ca_set_sz(ak_alloc_info* p, ak_sz sz)
{
    AKMALLOC_ASSERT(sz == ak_ca_to_sz((ak_alloc_info)sz));
    // 7 because there are only 3 useful bits. the fourth bit may collect garbage.
    *p = (ak_alloc_info)((((ak_sz)*p)  &  ((ak_sz)7)) |
                                 (sz   & ~(AK_COALESCE_ALIGN - 1)));
}

ak_inline static void ak_ca_set_is_first(ak_alloc_info* p, int v)
{
    *p = (ak_alloc_info)((((ak_sz)*p) & ~(AK_SZ_ONE << 0)) | (v ? (AK_SZ_ONE << 0) : 0));
}

ak_inline static void ak_ca_set_is_last(ak_alloc_info* p, int v)
{
    *p = (ak_alloc_info)((((ak_sz)*p) & ~(AK_SZ_ONE << 1)) | (v ? (AK_SZ_ONE << 1) : 0));
}

ak_inline static void ak_ca_set_is_free(ak_alloc_info* p, int v)
{
    *p = (ak_alloc_info)((((ak_sz)*p) & ~(AK_SZ_ONE << 2)) | (v ? (AK_SZ_ONE << 2) : 0));
}

ak_inline static ak_alloc_node* ak_ca_next_node(ak_alloc_node* node)
{
    return ak_ca_is_last(node->currinfo)
                ? AK_NULLPTR
                : ak_ptr_cast(ak_alloc_node,((char*)(node + 1) + ak_ca_to_sz(node->currinfo)));
}

ak_inline static ak_alloc_node* ak_ca_prev_node(ak_alloc_node* node)
{
    return ak_ca_is_first(node->currinfo)
                ? AK_NULLPTR
                : ak_ptr_cast(ak_alloc_node, ((char*)(node - 1) - ak_ca_to_sz(node->previnfo)));
}

ak_inline static void ak_ca_update_footer(ak_alloc_node* p)
{
    ak_alloc_node* n = ak_ca_next_node(p);
    if (n) {
        n->previnfo = p->currinfo;
    }
}

#define ak_free_list_node_unlink(node)               \
  do {                                               \
    ak_free_list_node* const sU = (node);            \
    sU->bk->fd = (sU->fd);                           \
    sU->fd->bk = (sU->bk);                           \
    sU->fd = sU->bk = AK_NULLPTR;                    \
  } while (0)

#define ak_free_list_node_link_fd(node, fwd)         \
  do {                                               \
    ak_free_list_node* const sLF = (node);           \
    ak_free_list_node* const fLF = (fwd);            \
    sLF->fd = fLF;                                   \
    fLF->bk = sLF;                                   \
  } while (0)

#define ak_free_list_node_link_bk(node, back)        \
  do {                                               \
    ak_free_list_node* const sLB = (node);           \
    ak_free_list_node* const bLB = (back);           \
    sLB->bk = bLB;                                   \
    bLB->fd = sLB;                                   \
  } while (0)

#define ak_free_list_node_link(node, fwd, back)      \
  do {                                               \
    ak_free_list_node* const sL = (node);            \
    ak_free_list_node* const fL = (fwd);             \
    ak_free_list_node* const bL = (back);            \
    ak_free_list_node_link_bk(sL, bL);               \
    ak_free_list_node_link_fd(sL, fL);               \
  } while (0)

#define ak_ca_segment_unlink(node)                   \
  do {                                               \
    ak_ca_segment* const sU = (node);                \
    sU->bk->fd = (sU->fd);                           \
    sU->fd->bk = (sU->bk);                           \
    sU->fd = sU->bk = AK_NULLPTR;                    \
  } while (0)

#define ak_ca_segment_link_fd(node, fwd)             \
  do {                                               \
    ak_ca_segment* const sLF = (node);               \
    ak_ca_segment* const fLF = (fwd);                \
    sLF->fd = fLF;                                   \
    fLF->bk = sLF;                                   \
  } while (0)

#define ak_ca_segment_link_bk(node, back)            \
  do {                                               \
    ak_ca_segment* const sLB = (node);               \
    ak_ca_segment* const bLB = (back);               \
    sLB->bk = bLB;                                   \
    bLB->fd = sLB;                                   \
  } while (0)

#define ak_ca_segment_link(node, fwd, back)          \
  do {                                               \
    ak_ca_segment* const sL = (node);                \
    ak_ca_segment* const fL = (fwd);                 \
    ak_ca_segment* const bL = (back);                \
    ak_ca_segment_link_bk(sL, bL);                   \
    ak_ca_segment_link_fd(sL, fL);                   \
  } while (0)

#define ak_circ_list_for_each(type, name, list)      \
    type* name = (list)->fd;                         \
    for(type* const iterroot = (list); name != iterroot; name = name->fd)

#define ak_ca_aligned_size(x) ((x) ? (((x) + AK_COALESCE_ALIGN - 1) & ~(AK_COALESCE_ALIGN - 1)) : AK_COALESCE_ALIGN)

#define ak_ca_aligned_segment_size(x) (((x) + (AK_COALESCE_SEGMENT_SIZE) - 1) & ~((AK_COALESCE_SEGMENT_SIZE) - 1))

ak_inline static void* ak_ca_search_free_list(ak_free_list_node* root, ak_sz sz, ak_sz splitsz)
{
    AKMALLOC_ASSERT(splitsz >= sizeof(ak_free_list_node));
    AKMALLOC_ASSERT(splitsz % AK_COALESCE_ALIGN == 0);

    // add the overhead per node
    splitsz += sizeof(ak_alloc_node);

    // walk through list finding the first element that fits and split if required
    ak_circ_list_for_each(ak_free_list_node, node, root) {
        ak_alloc_node* n = ((ak_alloc_node*)(node)) - 1;
        AKMALLOC_ASSERT(ak_ca_is_free(n->currinfo));
        ak_sz nodesz = ak_ca_to_sz(n->currinfo);
        if (nodesz >= sz) {
            if ((nodesz - sz) > splitsz) {
                // split and assign
                ak_alloc_node* newnode = ak_ptr_cast(ak_alloc_node, (((char*)node) + sz));
                int islast = ak_ca_is_last(n->currinfo);

                ak_ca_set_sz(ak_as_ptr(n->currinfo), sz);
                ak_ca_set_is_last(ak_as_ptr(n->currinfo), 0);
                ak_ca_set_is_free(ak_as_ptr(n->currinfo), 0);
                ak_ca_update_footer(n);

                ak_ca_set_sz(ak_as_ptr(newnode->currinfo), nodesz - sz - sizeof(ak_alloc_node));
                ak_ca_set_is_first(ak_as_ptr(newnode->currinfo), 0);
                ak_ca_set_is_last(ak_as_ptr(newnode->currinfo), islast);
                ak_ca_set_is_free(ak_as_ptr(newnode->currinfo), 1);
                ak_ca_update_footer(newnode);

                // copy free list node from node
                ak_free_list_node* fl = (ak_free_list_node*)(newnode + 1);
                ak_free_list_node_link(fl, node->fd, node->bk);
                AKMALLOC_ASSERT(n->currinfo == newnode->previnfo);
            } else {
                // return as is
                ak_ca_set_is_free(ak_as_ptr(n->currinfo), 0);
                ak_ca_update_footer(n);
                ak_free_list_node_unlink(node);
            }
            return node;
        }
    }
    return AK_NULLPTR;
}

static int ak_ca_add_new_segment(ak_ca_root* root, char* mem, ak_sz sz)
{
    if (ak_likely(mem)) {
        // make segment
        ak_ca_segment* seg = ak_ptr_cast(ak_ca_segment, (mem + sz - sizeof(ak_ca_segment)));
        ak_ca_segment_link(seg, root->main_root.fd, ak_as_ptr(root->main_root));
        seg->sz = sz;
        seg->head = ak_ptr_cast(ak_alloc_node, mem);
        {// add to free list
            ak_alloc_node* hd = seg->head;
            ak_sz actualsize = (sz - sizeof(ak_alloc_node) - sizeof(ak_ca_segment));
            // store actual size in previnfo
            hd->previnfo = actualsize;
            ak_ca_set_is_first(ak_as_ptr(hd->currinfo), 1);
            ak_ca_set_is_last(ak_as_ptr(hd->currinfo), 1);
            ak_ca_set_is_free(ak_as_ptr(hd->currinfo), 1);
            ak_ca_set_sz(ak_as_ptr(hd->currinfo), actualsize);
            ak_free_list_node* fl = (ak_free_list_node*)(hd + 1);
            ak_free_list_node_link(fl, root->free_root.fd, ak_as_ptr(root->free_root));
        }
        return 1;
    }
    return 0;
}

static int ak_ca_get_new_segment(ak_ca_root* root, ak_sz sz)
{
    // align to segment size multiple
    sz += sizeof(ak_ca_segment) + sizeof(ak_alloc_node) + sizeof(ak_free_list_node);
    sz = ak_ca_aligned_segment_size(sz);

    // search empty_root for a segment that is as big or more
    char* mem = AK_NULLPTR;
    ak_sz segsz = sz;
    ak_circ_list_for_each(ak_ca_segment, seg, ak_as_ptr(root->empty_root)) {
        if (seg->sz >= sz) {
            mem = (char*)(seg->head);
            segsz = seg->sz;
            ak_ca_segment_unlink(seg);
            --(root->nempty);
            break;
        }
    }

    return ak_ca_add_new_segment(root, mem ? mem : ((char*)ak_os_alloc(sz)), segsz);
}

static ak_u32 ak_ca_return_os_mem(ak_ca_segment* r, ak_u32 num)
{
    ak_u32 ct = 0;
    ak_ca_segment* next = r->fd;
    ak_ca_segment* curr = next;
    for(; curr != r; curr = next) {
        if (ct >= num) {
            break;
        }
        next = curr->fd;
        ak_ca_segment_unlink(curr);
        ak_os_free(curr->head, curr->sz);
        ++ct;
    }
    return ct;
}

/**************************************************************/
/* P U B L I C                                                */
/**************************************************************/

/*!
 * Initialize a coalescing allocator.
 * \param root; Pointer to the allocator root to initialize (non-NULL)
 * \param relrate; Release rate, \ref akmallocDox
 * \param maxsegstofree; Number of segments to free upon release, \ref akmallocDox
 */
static void ak_ca_init_root(ak_ca_root* root, ak_u32 relrate, ak_u32 maxsegstofree)
{
    AKMALLOC_ASSERT_ALWAYS(AK_COALESCE_SEGMENT_SIZE % AK_COALESCE_SEGMENT_GRANULARITY == 0);
    AKMALLOC_ASSERT_ALWAYS(((AK_COALESCE_SEGMENT_SIZE & (AK_COALESCE_SEGMENT_SIZE - 1)) == 0) && "Segment size must be a power of 2");

    ak_ca_segment_link(&(root->main_root), &(root->main_root), &(root->main_root));
    ak_ca_segment_link(&(root->empty_root), &(root->empty_root), &(root->empty_root));
    ak_free_list_node_link(&(root->free_root), &(root->free_root), &(root->free_root));
    root->nempty = root->release = 0;

    root->RELEASE_RATE = relrate;
    root->MAX_SEGMENTS_TO_FREE = maxsegstofree;
    root->MIN_SIZE_TO_SPLIT = (sizeof(ak_free_list_node) >= AK_COALESCE_ALIGN) ? sizeof(ak_free_list_node) : AK_COALESCE_ALIGN;
    AK_CA_LOCK_INIT(root);
}

/*!
 * Default initialize a coalescing allocator.
 * \param root; Pointer to the allocator root to initialize (non-NULL)
 */
ak_inline static void ak_ca_init_root_default(ak_ca_root* root)
{
#if AKMALLOC_BITNESS == 32
    static const ak_u32 rate =  255;
#else
    static const ak_u32 rate = 2047;
#endif
    ak_ca_init_root(root, rate, rate);
}

/*!
 * Attempt to grow an existing allocation.
 * \param root; Pointer to the allocator root
 * \param mem; Existing memory to grow
 * \param newsz; The new size for the allocation
 *
 * \return \c 0 on failure, and \p mem on success which can hold at least \p newsz bytes.
 */
ak_inline static void* ak_ca_realloc_in_place(ak_ca_root* root, void* mem, ak_sz newsz)
{
    void* retmem = AK_NULLPTR;

    ak_alloc_node* n = ak_ptr_cast(ak_alloc_node, mem) - 1;
    AKMALLOC_ASSERT(ak_ca_is_free(n->currinfo));
    // check if there is a free next, if so, maybe merge
    ak_sz sz = ak_ca_to_sz(n->currinfo);

    ak_alloc_node* next = ak_ca_next_node(n);
    if (next && ak_ca_is_free(next->currinfo)) {
        AKMALLOC_ASSERT(n->currinfo == next->previnfo);
        ak_sz nextsz = ak_ca_to_sz(next->currinfo);
        ak_sz totalsz = nextsz + sz + sizeof(ak_alloc_node);
        if (totalsz >= newsz) {
            AK_CA_LOCK_ACQUIRE(root);

            // we could remember the prev and next free entries and link them
            // back if the freed size is larger and we split the new node
            // but we assume that reallocs are rare and that one realloc may get more
            // so we try to keep it simple here, and simply merge the two

            ak_free_list_node_unlink((ak_free_list_node*)(next + 1));
            // don't need to change attributes on next as it is goind away
            if (ak_ca_is_last(next->currinfo)) {
                ak_ca_set_is_last(ak_as_ptr(n->currinfo), 1);
            }
            ak_ca_set_sz(ak_as_ptr(n->currinfo), totalsz);
            ak_ca_update_footer(n);

            retmem = mem;

            AK_CA_LOCK_RELEASE(root);
        }
    }

    return retmem;
}

/*!
 * Attempt to allocate memory from the coalescing allocator root.
 * \param root; Pointer to the allocator root
 * \param s; The size for the allocation
 *
 * \return \c 0 on failure, else pointer to at least \p s bytes of memory.
 */
static void* ak_ca_alloc(ak_ca_root* root, ak_sz s)
{
    // align and round size
    ak_sz sz = ak_ca_aligned_size(s);
    AK_CA_LOCK_ACQUIRE(root);
    // search free list
    ak_sz splitsz = root->MIN_SIZE_TO_SPLIT;
    void* mem = ak_ca_search_free_list(ak_as_ptr(root->free_root), sz, splitsz);
    // add new segment
    if (ak_unlikely(!mem)) {
        // NOTE: could also move segments from empty_root to main_root
        if (ak_likely(ak_ca_get_new_segment(root, sz))) {
            mem = ak_ca_search_free_list(ak_as_ptr(root->free_root), sz, splitsz);
            AKMALLOC_ASSERT(mem);
        }
    }
    AK_CA_LOCK_RELEASE(root);
    return mem;
}

/*!
 * Return memory to the coalescing allocator root.
 * \param root; Pointer to the allocator root
 * \param m; The memory to return.
 */
ak_inline static void ak_ca_free(ak_ca_root* root, void* m)
{
    // get alloc header before
    ak_alloc_node* node = ((ak_alloc_node*)m) - 1;

    AK_CA_LOCK_ACQUIRE(root);

    ak_alloc_node* nextnode = ak_ca_next_node(node);
    ak_alloc_node* prevnode = ak_ca_prev_node(node);
    int coalesce = 0;

    // mark as free
    AKMALLOC_ASSERT(!ak_ca_is_free(node->currinfo));
    AKMALLOC_ASSERT(!nextnode || (node->currinfo == nextnode->previnfo));
    ak_ca_set_is_free(ak_as_ptr(node->currinfo), 1);
    ak_ca_update_footer(node);

    // NOTE: maybe this should happen at a lower frequency?
    // coalesce if free before or if free after or both
    if (prevnode && ak_ca_is_free(node->previnfo)) {
        // coalesce back
        // update node and the footer
        ak_sz newsz = ak_ca_to_sz(node->previnfo) + ak_ca_to_sz(node->currinfo) + sizeof(ak_alloc_node);
        ak_ca_set_sz(ak_as_ptr(prevnode->currinfo), newsz);
        ak_ca_set_is_last(ak_as_ptr(prevnode->currinfo), nextnode == AK_NULLPTR);
        ak_ca_update_footer(prevnode);
        AKMALLOC_ASSERT(!nextnode || ak_ca_next_node(prevnode) == nextnode);
        AKMALLOC_ASSERT(!nextnode || prevnode->currinfo == nextnode->previnfo);
        coalesce += 1;
        // update free list
    }

    if (nextnode && ak_ca_is_free(nextnode->currinfo)) {
        // coalesce forward
        // update node and the footer
        ak_alloc_node* n = (coalesce) ? prevnode : node;
        ak_sz newsz = ak_ca_to_sz(n->currinfo) + ak_ca_to_sz(nextnode->currinfo) + sizeof(ak_alloc_node);
        ak_ca_set_sz(ak_as_ptr(n->currinfo), newsz);
        ak_ca_set_is_last(ak_as_ptr(n->currinfo), ak_ca_is_last(nextnode->currinfo));
        ak_ca_update_footer(n);
        AKMALLOC_ASSERT(ak_ca_is_last(n->currinfo) || (n->currinfo == ak_ca_next_node(nextnode)->previnfo));
        coalesce += 2;
    }

    // update free lists
    ak_alloc_node* tocheck = AK_NULLPTR;
    switch (coalesce) {
        case 0: {
                // thread directly
                ak_free_list_node* fl = (ak_free_list_node*)(node + 1);
                ak_free_list_node_link(fl, root->free_root.fd, ak_as_ptr(root->free_root));
            }
            break;
        case 1: {
                // prevnode already threaded through
                tocheck = prevnode;
            }
            break;
        case 2: {
                // copy free list entry from nextnode
                ak_free_list_node* fl = (ak_free_list_node*)(node + 1);
                ak_free_list_node* nextfl = (ak_free_list_node*)(nextnode + 1);
                ak_free_list_node_link(fl, nextfl->fd, nextfl->bk);
                tocheck = node;
            }
            break;
        case 3: {
                ak_free_list_node* nextfl = (ak_free_list_node*)(nextnode + 1);
                ak_free_list_node_unlink(nextfl);
                tocheck = prevnode;
            }
            break;
        default:
            AKMALLOC_ASSERT_ALWAYS(0 && "Should not get here!");
            break;
    }

    // move to empty if segment is empty

    if (tocheck && ak_ca_is_first(tocheck->currinfo) && ak_ca_is_last(tocheck->currinfo)) {
        // remove free list entry
        ak_free_list_node* fl = (ak_free_list_node*)(tocheck + 1);
        ak_free_list_node_unlink(fl);
        // actual size is in tocheck->previnfo
        AKMALLOC_ASSERT(tocheck->previnfo == ak_ca_to_sz(tocheck->currinfo));
        ak_ca_segment* seg = ak_ptr_cast(ak_ca_segment, ((char*)(tocheck + 1) + tocheck->previnfo));
        AKMALLOC_ASSERT(tocheck->previnfo == (seg->sz - sizeof(ak_alloc_node) - sizeof(ak_ca_segment)));
        ak_ca_segment_unlink(seg);
        ak_ca_segment_link(seg, root->empty_root.fd, ak_as_ptr(root->empty_root));
        ++(root->nempty); ++(root->release);
        // check if we should free empties
        if (root->release >= root->RELEASE_RATE) {
            // release segment
            ak_u32 nrem = ak_ca_return_os_mem(ak_as_ptr(root->empty_root), root->MAX_SEGMENTS_TO_FREE);
            root->nempty -= nrem;
            root->release = 0;
        }
    }

    AK_CA_LOCK_RELEASE(root);
}

/*!
 * Destroy the coalescing allocator root and return all memory to the OS.
 * \param root; Pointer to the allocator root
 */
static void ak_ca_destroy(ak_ca_root* root)
{
    ak_ca_return_os_mem(ak_as_ptr(root->main_root), AK_U32_MAX);
    ak_ca_return_os_mem(ak_as_ptr(root->empty_root), AK_U32_MAX);
    root->nempty = root->release = 0;
}
/********************** coalescing allocator end ************************/

/********************** mallocstate begin **********************/

static void* ak_memset(void* m, int v, ak_sz sz)
{
    char* mem = (char*)m;
    for (ak_sz i = 0; i != sz; ++i) {
        mem[i] = v;
    }
    return m;
}

static void ak_memcpy(void* d, const void* s, ak_sz sz)
{
    char* mem = (char*)d;
    const char* srcmem = (const char*)s;
    for (ak_sz i = 0; i != sz; ++i) {
        mem[i] = srcmem[i];
    }
}

// Coalescing allocs give 16-byte aligned memory where the preamble
// uses three bits. The fourth bit is always free. We use that bit
// to distinguish slabs from coalesced outputs, and mmap-outputs.
//
// xxx0 - coalesce
// 0101 - slab
// 1001 - mmap
#define ak_alloc_type_bits(p) \
  ((*(((const ak_sz*)(p)) - 1)) & (AK_COALESCE_ALIGN - 1))

#define ak_alloc_type_coalesce(sz) \
  ((((ak_sz)sz) & ((ak_sz)8)) == 0)

#define ak_alloc_type_slab(sz) \
  ((((ak_sz)sz) & (AK_COALESCE_ALIGN - 1)) == 10)

#define ak_alloc_type_mmap(sz) \
  ((((ak_sz)sz) & (AK_COALESCE_ALIGN - 1)) == 9)

#define ak_alloc_mark_coalesce(p) ((void)(p))

#define ak_alloc_mark_slab(p) \
  *(((ak_sz*)(p)) - 1) = ((ak_sz)10)

#define ak_alloc_mark_mmap(p) \
  *(((ak_sz*)(p)) - 1) = ((ak_sz)9)

#if defined(AK_MIN_SLAB_ALIGN_16)
#  define ak_slab_mod_sz(x) (ak_ca_aligned_size((x)) + AK_COALESCE_ALIGN)
#  define ak_slab_alloc_2_mem(x) (((ak_sz*)x) + (AK_COALESCE_ALIGN / sizeof(ak_sz)))
#  define ak_slab_mem_2_alloc(x) (((ak_sz*)x) - (AK_COALESCE_ALIGN / sizeof(ak_sz)))
#  define ak_slab_usable_size(x) ((x) - AK_COALESCE_ALIGN)
#else
#  define ak_slab_mod_sz(x) (ak_ca_aligned_size((x) + sizeof(ak_sz)))
#  define ak_slab_alloc_2_mem(x) (((ak_sz*)x) + 1)
#  define ak_slab_mem_2_alloc(x) (((ak_sz*)x) - 1)
#  define ak_slab_usable_size(x) ((x) - sizeof(ak_sz))
#endif

/* cannot be changed. we have fixed size slabs */
#define MIN_SMALL_REQUEST 256

#if !defined(MMAP_SIZE)
#  if !AKMALLOC_WINDOWS
#    define MMAP_SIZE (AK_SZ_ONE << 20) /* 1 MB */
#  else/* Windows */
    /**
     * Memory mapping on Windows is slow. Put the entries in the large free list
     * to avoid mmap() calls.
     */
#    define MMAP_SIZE AK_SZ_MAX
#  endif
#endif


#define NSLABS 16

/*!
 * Sizes for the slabs in an \c ak_malloc_state
 */
static const ak_sz SLAB_SIZES[NSLABS] = {
    16,   32,   48,   64,   80,   96,  112,  128,
   144,  160,  176,  192,  208,  224,  240,  256
};

#define NCAROOTS 8

/*!
 * Sizes for the coalescing allocators in an \c ak_malloc_state
 *
 * Size here denotes maximum size request for each allocator.
 */
static const ak_sz CA_SIZES[NCAROOTS] = {
    768, 1408, 2048, 4096, 8192, 16384, 65536, MMAP_SIZE
};

typedef struct ak_malloc_state_tag ak_malloc_state;

/*!
 * Private malloc like allocator
 */
struct ak_malloc_state_tag
{
    ak_sz         init;             /**< whether initialized */
    ak_slab_root  slabs[NSLABS];    /**< slabs of different sizes */
    ak_ca_root    ca[NCAROOTS];     /**< coalescing allocators of different size ranges */
    ak_ca_segment map_root;         /**< root of list of mmap-ed segments */

    AKMALLOC_LOCK_DEFINE(MAP_LOCK); /**< lock for mmap-ed regions if locks are enabled */
};

#if !defined(AKMALLOC_COALESCING_ALLOC_RELEASE_RATE)
#  define AKMALLOC_COALESCING_ALLOC_RELEASE_RATE 24
#endif

#if !defined(AKMALLOC_COALESCING_ALLOC_MAX_PAGES_TO_FREE)
#  define AKMALLOC_COALESCING_ALLOC_MAX_PAGES_TO_FREE AKMALLOC_COALESCING_ALLOC_RELEASE_RATE
#endif

static void ak_try_reclaim_memory(ak_malloc_state* m)
{
    // for each slab, reclaim empty pages
    for (ak_sz i = 0; i < NSLABS; ++i) {
        ak_slab_root* s = ak_as_ptr(m->slabs[i]);
        ak_slab_release_pages(s, ak_as_ptr(s->empty_root), AK_U32_MAX);
        s->nempty = 0;
        s->release = 0;
    }
    // return unused segments in ca
    for (ak_sz i = 0; i < NCAROOTS; ++i) {
        ak_ca_root* ca = ak_as_ptr(m->ca[i]);
        ak_ca_return_os_mem(ak_as_ptr(ca->empty_root), AK_U32_MAX);
        ca->nempty = 0;
        ca->release = 0;
    }

    // all memory in mmap-ed regions is being used. we return pages immediately
    // when they are free'd.
}

ak_inline static void* ak_try_slab_alloc(ak_malloc_state* m, size_t sz)
{
    AKMALLOC_ASSERT(sz % AK_COALESCE_ALIGN == 0);
    ak_sz idx = (sz >> 4) - 1;
    ak_sz* mem = (ak_sz*)ak_slab_alloc(ak_as_ptr(m->slabs[idx]));
    if (ak_likely(mem)) {
        ak_alloc_mark_slab(ak_slab_alloc_2_mem(mem)); // we overallocate
        AKMALLOC_ASSERT(ak_alloc_type_slab(ak_alloc_type_bits(ak_slab_alloc_2_mem(mem))));
        mem = ak_slab_alloc_2_mem(mem);
    }
    return mem;
}

ak_inline static void* ak_try_coalesce_alloc(ak_malloc_state* m, ak_ca_root* proot, size_t sz)
{
    ak_sz* mem = (ak_sz*)ak_ca_alloc(proot, sz);
    if (ak_likely(mem)) {
        ak_alloc_mark_coalesce(mem);
        AKMALLOC_ASSERT(ak_alloc_type_coalesce(ak_alloc_type_bits(mem)));
    }
    return mem;
}

ak_inline static void* ak_try_alloc_mmap(ak_malloc_state* m, size_t sz)
{
    AKMALLOC_LOCK_ACQUIRE(ak_as_ptr(m->MAP_LOCK));
    ak_ca_segment* mem = (ak_ca_segment*)ak_os_alloc(sz);
    if (ak_likely(mem)) {
        ak_alloc_mark_mmap(mem + 1);
        AKMALLOC_ASSERT(ak_alloc_type_mmap(ak_alloc_type_bits(mem + 1)));
        mem->sz = sz;
        ak_ca_segment_link(mem, m->map_root.fd, ak_as_ptr(m->map_root));
        mem += 1;
    }
    AKMALLOC_LOCK_RELEASE(ak_as_ptr(m->MAP_LOCK));

    return mem;
}

ak_inline static ak_ca_root* ak_find_ca_root(ak_malloc_state* m, ak_sz sz)
{
    ak_sz i = 0;
    for (; i < NCAROOTS; ++i) {
        if (CA_SIZES[i] >= sz) {
            break;
        }
    }
    AKMALLOC_ASSERT(i < NCAROOTS);
    return ak_as_ptr(m->ca[i]);
}

ak_inline static void* ak_try_alloc(ak_malloc_state* m, size_t sz)
{
    void* retmem = AK_NULLPTR;
    ak_sz modsz = ak_slab_mod_sz(sz);
    if (modsz <= MIN_SMALL_REQUEST) {
        retmem = ak_try_slab_alloc(m, modsz);
        DBG_PRINTF("a,slab,%p,%llu\n", retmem, modsz);
    } else if (sz < MMAP_SIZE) {
        const ak_sz alnsz = ak_ca_aligned_size(sz);
        ak_ca_root* proot = ak_find_ca_root(m, sz);
        retmem = ak_try_coalesce_alloc(m, proot, alnsz);
        DBG_PRINTF("a,ca[%d],%p,%llu\n", (int)(proot-ak_as_ptr(m->ca[0])), retmem, alnsz);
    } else {
        sz += sizeof(ak_ca_segment);
        const ak_sz actsz = ak_ca_aligned_segment_size(sz);
        retmem = ak_try_alloc_mmap(m, actsz);
        DBG_PRINTF("a,mmap,%p,%llu\n", retmem, actsz);
    }

    return retmem;
}


static void* ak_aligned_alloc_from_state_no_checks(ak_malloc_state* m, size_t aln, size_t sz)
{
    ak_sz req = ak_ca_aligned_size(sz);
    req += aln + (2 * sizeof(ak_alloc_node)) + (2 * sizeof(ak_free_list_node));
    char* mem = AK_NULLPTR;
    // must request from coalesce alloc so we can return the extra piece
    ak_ca_root* ca = ak_find_ca_root(m, req);

    mem = (char*)ak_ca_alloc(ca, req);
    ak_alloc_node* node = ak_ptr_cast(ak_alloc_node, mem) - 1;
    if (ak_likely(mem)) {
        if ((((ak_sz)mem) & (aln - 1)) != 0) {
            // misaligned
            AK_CA_LOCK_ACQUIRE(ca);
            char* alnpos = (char*)(((ak_sz)(mem + aln - 1)) & ~(aln - 1));
            ak_alloc_node* alnnode = ak_ptr_cast(ak_alloc_node, alnpos) - 1;
            AKMALLOC_ASSERT((ak_sz)(alnpos - mem) >= (sizeof(ak_free_list_node) + sizeof(ak_alloc_node)));
            ak_sz actsz = ak_ca_to_sz(node->currinfo);
            int islast = ak_ca_is_last(node);

            ak_ca_set_sz(ak_as_ptr(node->currinfo), alnpos - mem - sizeof(ak_alloc_node));
            ak_ca_set_is_last(ak_as_ptr(node->currinfo), 0);
            ak_ca_set_is_free(ak_as_ptr(node->currinfo), 1);

            ak_ca_set_sz(ak_as_ptr(alnnode->currinfo), actsz - ak_ca_to_sz(node->currinfo));
            ak_ca_set_is_last(ak_as_ptr(alnnode->currinfo), islast);
            ak_ca_set_is_free(ak_as_ptr(alnnode->currinfo), 0);

            ak_ca_update_footer(node);
            ak_ca_update_footer(alnnode);
            mem = alnpos;
            AK_CA_LOCK_RELEASE(ca);
        }
        return mem;
    }
    return AK_NULLPTR;
}

ak_inline static size_t ak_malloc_usable_size_in_state(const void* mem);

/**************************************************************/
/* P U B L I C                                                */
/**************************************************************/

/*!
 * Initialize a private malloc like allocator.
 * \param s; Pointer to the allocator to initialize (non-NULL)
 */
static void ak_malloc_init_state(ak_malloc_state* s)
{
    AKMALLOC_ASSERT_ALWAYS(sizeof(ak_slab) % AK_COALESCE_ALIGN == 0);

    for (ak_sz i = 0; i != NSLABS; ++i) {
        ak_slab_init_root_default(ak_as_ptr(s->slabs[i]), SLAB_SIZES[i]);
    }

    for (ak_sz i = 0; i != NCAROOTS; ++i) {
        ak_ca_init_root(ak_as_ptr(s->ca[i]), AKMALLOC_COALESCING_ALLOC_RELEASE_RATE, AKMALLOC_COALESCING_ALLOC_MAX_PAGES_TO_FREE);
    }

    ak_ca_segment_link(ak_as_ptr(s->map_root), ak_as_ptr(s->map_root), ak_as_ptr(s->map_root));

    AKMALLOC_LOCK_INIT(ak_as_ptr(s->MAP_LOCK));
    s->init = 1;
}

/*!
 * Destroy the private malloc like allocator and return all memory to the OS.
 * \param m; Pointer to the allocator
 */
static void ak_malloc_destroy_state(ak_malloc_state* m)
{
    for (ak_sz i = 0; i < NSLABS; ++i) {
        ak_slab_destroy(ak_as_ptr(m->slabs[i]));
    }
    for (ak_sz i = 0; i < NCAROOTS; ++i) {
        ak_ca_destroy(ak_as_ptr(m->ca[i]));
    }
    {// mmaped chunks
        ak_ca_segment temp;
        ak_circ_list_for_each(ak_ca_segment, seg, &(m->map_root)) {
            temp = *seg;
            ak_os_free(seg, seg->sz);
            seg = &temp;
        }
    }
}

/*!
 * Attempt to allocate memory containing at least \p n bytes.
 * \param m; The allocator
 * \param sz; The size for the allocation
 *
 * \return \c 0 on failure, else pointer to at least \p n bytes of memory.
 */
static void* ak_malloc_from_state(ak_malloc_state* m, size_t sz)
{
    AKMALLOC_ASSERT(m->init);
    void* mem = ak_try_alloc(m, sz);
    if (ak_unlikely(!mem)) {
        ak_try_reclaim_memory(m);
        mem = ak_try_alloc(m, sz);
    }
    return mem;
}

/*!
 * Return memory to the allocator.
 * \param m; The allocator
 * \param mem; Pointer to the memory to return.
 */
ak_inline static void ak_free_to_state(ak_malloc_state* m, void* mem)
{
    if (ak_likely(mem)) {
#if defined(AKMALLOC_DEBUG_PRINT)
        ak_sz ussize = ak_malloc_usable_size_in_state(mem);
#endif/*defined(AKMALLOC_DEBUG_PRINT)*/
        ak_sz ty = ak_alloc_type_bits(mem);
        if (ak_alloc_type_slab(ty)) {
            DBG_PRINTF("d,slab,%p,%llu\n", mem, ussize);
            ak_slab_free(ak_slab_mem_2_alloc(mem));
        } else if (ak_alloc_type_mmap(ty)) {
            DBG_PRINTF("d,mmap,%p,%llu\n", mem, ussize);
            AKMALLOC_LOCK_ACQUIRE(ak_as_ptr(m->MAP_LOCK));
            ak_ca_segment* seg = ((ak_ca_segment*)mem) - 1;
            ak_ca_segment_unlink(seg);
            ak_os_free(seg, seg->sz);
            AKMALLOC_LOCK_RELEASE(ak_as_ptr(m->MAP_LOCK));
        } else {
            AKMALLOC_ASSERT(ak_alloc_type_coalesce(ty));
            const ak_alloc_node* n = ((const ak_alloc_node*)mem) - 1;
            const ak_sz alnsz = ak_ca_to_sz(n->currinfo);
            ak_ca_root* proot = ak_find_ca_root(m, alnsz);
            DBG_PRINTF("d,ca[%d],%p,%llu\n", (int)(proot-ak_as_ptr(m->ca[0])), mem, alnsz);
            ak_ca_free(proot, mem);
        }
    }
}

/*!
 * Attempt to grow memory at the region pointed to by \p p to a size \p newsz without relocation.
 * \param m; The allocator
 * \param mem; Memory to grow
 * \param newsz; New size to grow to
 *
 * \return \c NULL if no memory is available, or \p mem with at least \p newsz bytes.
 */
ak_inline static void* ak_realloc_in_place_from_state(ak_malloc_state* m, void* mem, size_t newsz)
{
    const ak_sz usablesize = ak_malloc_usable_size_in_state(mem);
    if (usablesize >= newsz) {
        return mem;
    }
    if (ak_alloc_type_coalesce(ak_alloc_type_bits(mem))) {
        ak_alloc_node* n = ak_ptr_cast(ak_alloc_node, mem) - 1;
        AKMALLOC_ASSERT(ak_ca_is_free(n->currinfo));
        // check if there is a free next, if so, maybe merge
        ak_sz sz = ak_ca_to_sz(n->currinfo);
        ak_ca_root* proot = ak_find_ca_root(m, sz);
        if (ak_ca_realloc_in_place(proot, mem, newsz)) {
            return mem;
        }
    }
    return AK_NULLPTR;
}

/*!
 * Attempt to grow memory at the region pointed to by \p p to a size \p newsz.
 * \param m; The allocator
 * \param mem; Memory to grow
 * \param newsz; New size to grow to
 *
 * This function will copy the old bytes to a new memory location if the old memory cannot be
 * grown in place, and will free the old memory. If no more memory is available it will not
 * destroy the old memory.
 *
 * \return \c NULL if no memory is available, or a pointer to memory with at least \p newsz bytes.
 */
static void* ak_realloc_from_state(ak_malloc_state* m, void* mem, size_t newsz)
{
    if (ak_unlikely(!mem)) {
        return ak_malloc_from_state(m, newsz);
    }

    if (ak_realloc_in_place_from_state(m, mem, newsz)) {
        return mem;
    }

    void* newmem = ak_malloc_from_state(m, newsz);
    if (!newmem) {
        return AK_NULLPTR;
    }
    if (ak_likely(mem)) {
        ak_memcpy(newmem, mem, ak_malloc_usable_size_in_state(mem));
        ak_free_to_state(m, mem);
    }
    return newmem;
}


/*!
 * Return the usable size of the memory region pointed to by \p p.
 * \param mem; Pointer to the memory to determize size of.
 *
 * \return The number of bytes that can be written to in the region.
 */
ak_inline static size_t ak_malloc_usable_size_in_state(const void* mem)
{
    if (ak_likely(mem)) {
        ak_sz ty = ak_alloc_type_bits(mem);
        if (ak_alloc_type_slab(ty)) {
            // round to page
            const ak_slab* slab = (const ak_slab*)(ak_page_start_before_const(mem));
            return ak_slab_usable_size(slab->root->sz);
        } else if (ak_alloc_type_mmap(ty)) {
            return (((const ak_ca_segment*)mem) - 1)->sz - sizeof(ak_ca_segment);
        } else {
            AKMALLOC_ASSERT(ak_alloc_type_coalesce(ty));
            const ak_alloc_node* n = ((const ak_alloc_node*)mem) - 1;
            AKMALLOC_ASSERT(!ak_ca_is_free(n->currinfo));
            return ak_ca_to_sz(n->currinfo);
        }
    } else {
        return 0;
    }
}

/*!
 * Attempt to allocate memory containing at least \p n bytes at an address which is
 * a multiple of \p aln. \p aln must be a power of two. \p sz must be a multiple of \p aln.
 * \param m; The allocator
 * \param aln; The alignment
 * \param sz; The size for the allocation
 *
 * \return \c 0 on failure, else pointer to at least \p n bytes of memory at an aligned address.
 */
static void* ak_aligned_alloc_from_state(ak_malloc_state* m, size_t aln, size_t sz)
{
    if (aln <= AK_COALESCE_ALIGN) {
        return ak_malloc_from_state(m, sz);
    }
    if ((aln & AK_SZ_ONE) || (aln & (aln - 1))) {
        size_t a = AK_COALESCE_ALIGN << 1;
        while (a < aln)  {
            a  = (a << 1);
        }
        aln = a;
    }
    return ak_aligned_alloc_from_state_no_checks(m, aln, sz);
}

#define AK_EINVAL 22
#define AK_ENOMEM 12

/*!
 * Attempt to allocate memory containing at least \p n bytes at an address which is
 * a multiple of \p aln and assign the address to \p *pmem. \p aln must be a power of two and
 * a multiple of \c sizeof(void*).
 * \param m; The allocator
 * \param pmem; The address where the memory address should be writted.
 * \param aln; The alignment
 * \param sz; The size for the allocation
 *
 * \return \c 0 on success, 12 if no more memory is available, and 22 if \p aln was not a power
 * of two and a multiple of \c sizeof(void*)
 */
static int ak_posix_memalign_from_state(ak_malloc_state* m, void** pmem, size_t aln, size_t sz)
{
    void* mem = AK_NULLPTR;
    if (aln == AK_COALESCE_ALIGN) {
        mem = ak_malloc_from_state(m, sz);
    } else {
        ak_sz div = (aln / sizeof(ak_sz));
        ak_sz rem = (aln & (sizeof(ak_sz)));
        if (rem != 0 || div == 0 || (div & (div - AK_SZ_ONE)) != 0) {
            return AK_EINVAL;
        }
        aln = (aln <= AK_COALESCE_ALIGN) ? AK_COALESCE_ALIGN : aln;
        mem = ak_aligned_alloc_from_state_no_checks(m, aln, sz);
    }

    if (!mem) {
        return AK_ENOMEM;
    }

    *pmem = mem;
    return 0;
}

/*!
 * Iterate over all memory segments allocated.
 * \param m; The allocator
 * \param cbk; Callback that is given the address of a segment and its size. \see ak_seg_cbk.
 */
static void ak_malloc_for_each_segment_in_state(ak_malloc_state* m, ak_seg_cbk cbk)
{
    // for each slab, reclaim empty pages
    for (ak_sz i = 0; i < NSLABS; ++i) {
        ak_slab_root* s = ak_as_ptr(m->slabs[i]);
        ak_circ_list_for_each(ak_slab, fslab, &(s->full_root)) {
            if (!cbk(fslab, AKMALLOC_DEFAULT_PAGE_SIZE)) {
                return;
            }
        }
        ak_circ_list_for_each(ak_slab, pslab, &(s->partial_root)) {
            if (!cbk(pslab, AKMALLOC_DEFAULT_PAGE_SIZE)) {
                return;
            }
        }
    }

    {// ca roots
        for (ak_sz i = 0; i < NCAROOTS; ++i) {
            ak_circ_list_for_each(ak_ca_segment, seg, &(m->ca[i].main_root)) {
                if (!cbk(seg->head, seg->sz)) {
                    return;
                }
            }
        }
    }

    {// mmaped chunks
        ak_circ_list_for_each(ak_ca_segment, seg, &(m->map_root)) {
            if (!cbk(seg, seg->sz)) {
                return;
            }
        }
    }
}
/********************** mallocstate end ************************/

/***********************************************
 * Exported APIs
 ***********************************************/

static int MALLOC_INIT = 0;

static ak_malloc_state MALLOC_ROOT;
static ak_malloc_state* GMSTATE = AK_NULLPTR;
static ak_spinlock MALLOC_INIT_LOCK = { 0 };

#define ak_ensure_malloc_state_init()                        \
{                                                            \
    if (ak_unlikely(!MALLOC_INIT)) {                         \
        AKMALLOC_LOCK_ACQUIRE(ak_as_ptr(MALLOC_INIT_LOCK));  \
        if (MALLOC_INIT != 1) {                              \
            GMSTATE = &MALLOC_ROOT;                          \
            ak_malloc_init_state(GMSTATE);                   \
            MALLOC_INIT = 1;                                 \
        }                                                    \
        AKMALLOC_LOCK_RELEASE(ak_as_ptr(MALLOC_INIT_LOCK));  \
    }                                                        \
    AKMALLOC_ASSERT(MALLOC_ROOT.init);                       \
}

AK_EXTERN_C_BEGIN

void* ak_malloc(size_t sz)
{
    ak_ensure_malloc_state_init();
    return ak_malloc_from_state(GMSTATE, sz);
}

void* ak_calloc(size_t elsz, size_t numel)
{
    const ak_sz sz = elsz*numel;
    void* mem = ak_malloc_from_state(GMSTATE, sz);
    return ak_memset(mem, 0, sz);
}

void ak_free(void* mem)
{
    ak_ensure_malloc_state_init();
    ak_free_to_state(GMSTATE, mem);
}

void* ak_aligned_alloc(size_t sz, size_t aln)
{
    ak_ensure_malloc_state_init();
    return ak_aligned_alloc_from_state(GMSTATE, sz, aln);
}

int ak_posix_memalign(void** pmem, size_t aln, size_t sz)
{
    ak_ensure_malloc_state_init();
    return ak_posix_memalign_from_state(GMSTATE, pmem, aln, sz);
}

void* ak_memalign(size_t sz, size_t aln)
{
    ak_ensure_malloc_state_init();
    return ak_aligned_alloc_from_state(GMSTATE, sz, aln);
}

size_t ak_malloc_usable_size(const void* mem)
{
    return ak_malloc_usable_size_in_state(mem);
}

void* ak_realloc(void* mem, size_t newsz)
{
    ak_ensure_malloc_state_init();
    return ak_realloc_from_state(GMSTATE, mem, newsz);
}

void* ak_realloc_in_place(void* mem, size_t newsz)
{
    ak_ensure_malloc_state_init();
    return ak_realloc_in_place_from_state(GMSTATE, mem, newsz);
}

void ak_malloc_for_each_segment(ak_seg_cbk cbk)
{
    ak_ensure_malloc_state_init();
    ak_malloc_for_each_segment_in_state(GMSTATE, cbk);
}

AK_EXTERN_C_END

Answer 1

It's obvious that you've spent a lot of time on this project. As far as I can tell the things you've done are to optimize the size of the code and the speed of execution. Optimization sometimes leads to code that is less maintainable.

Using your initials isn't a bad idea, but I would use ak__ rather than ak_ as the prefix. That way it's clearer that it is a prefix rather than an abbreviation. It's obvious that you're trying to work around the fact that the C language doesn't support name spaces.

I do wonder why you felt it was necessary to create your own ASSERTS rather than using the standard ASSERT().

Word Size
The size of unsigned int is compiler/machine dependent, the typedef name ak_u32 is misleading, see this StackOverflow question. This can lead to portability problems and your alignment isn't guarenteed.

Lower Case Macro Names
Using lower case macro names can be misleading, macros are generally all upper case. I would be expecting all the lower case macros to be functions.

#define ak_slab_unlink(slab)               \
  do {                                     \
    ak_slab* const sU = (slab);            \
    sU->bk->fd = (sU->fd);                 \
    sU->fd->bk = (sU->bk);                 \
    sU->fd = sU->bk = AK_NULLPTR;          \
  } while (0)

I as a developer would be very surprised if I had to maintain this code.

Inline Functions
Inline functions were originally created for C++, not C. Inline functions were created to replace macros. Is this library C or C++?

Informative Variable and Field Names
You have the struct

struct ak_slab_tag
{
    ak_slab*      fd;
    ak_slab*      bk;
    ak_slab_root* root;
    ak_bitset512  avail;
    void*         _unused;
};

I might be able to figure out what root, avail and _unused mean (avail and _unused are pretty clear), but I have no clue what fd or bk are. To me fd might be a File Descriptor. I have the same problem with r in the following function.

static void ak_slab_release_pages(ak_slab_root* root, ak_slab* s, ak_u32 numtofree)
{
    ak_slab* const r = s;
    ak_slab* next = AK_NULLPTR;
    s = s->fd;
    for (ak_u32 ct = 0; ct < numtofree; ++ct) {
        if (s == r) {
            break;
        } else {
            next = s->fd;
        }
        ak_slab_unlink(s);
        ak_os_free(s, AKMALLOC_DEFAULT_PAGE_SIZE);
        s = next;
    }
}

NULLPTR
As a C programmer I know what NULL is. If I wanted to define my own NULL I would probably do it this way

#define AK_NULLPTR NULL

Better yet, I would just use NULL.

Macro Nesting Duplicates Code
If I act as the C PreProcessor what I get for this macro

#define ak_slab_link(slab, fwd, back)      \
  do {                                     \
    ak_slab* const sL = (slab);            \
    ak_slab* const fL = (fwd);             \
    ak_slab* const bL = (back);            \
    ak_slab_link_bk(sL, bL);               \
    ak_slab_link_fd(sL, fL);               \
  } while (0)

is the following:

#define ak_slab_link(slab, fwd, back)    
  do {                                  
    ak_slab* const sL = (slab);        
    ak_slab* const fL = (fwd);        
    ak_slab* const bL = (back);      
    ak_slab_link_bk(sL, bL);        
    do {                             
      ak_slab* const sLB = (slab);  
      ak_slab* const bLB = (back);      
      sLB->bk = bLB;                   
      bLB->fd = sLB;                  
    } while (0);
    do {                                     
      ak_slab* const sLF = (slab);          
      ak_slab* const fLF = (fwd);          
      sLF->fd = fLF;                      
      fLF->bk = sLF;                     
    } while (0);
  } while (0)

When it could simply be:

    sLB->bk = (slab);
    bLB->fd = (back);                  
    sLF->fd = (fwd);                      
    fLF->bk = (slab);

Please note that the only place ak_slab_link_bk() and ak_slab_link_fd() are used is in the ak_slab_link() macro.

The ak_slab_link() macro is used effectively in several functions.

If I needed to maintain ak_slab_link() with the current implementation it is quite confusing.