path: root/src/common/mempool.c

//
// Memory Pool Implementation (Threadsafe)
//
//
// Author: Florian Wilkemeyer <fw@f-ws.de>
//
// Copyright (c) rAthena Project (www.rathena.org) - Licensed under GNU GPL
// For more information, see LICENCE in the main folder
//
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#ifdef WIN32
#include "../common/winapi.h"
#else
#include <unistd.h>
#endif

#include "../common/cbasetypes.h"
#include "../common/showmsg.h"
#include "../common/mempool.h"
#include "../common/atomic.h"
#include "../common/spinlock.h"
#include "../common/thread.h"
#include "../common/malloc.h"
#include "../common/mutex.h"

#define ALIGN16 ra_align(16)
#define ALIGN_TO(x, a) (x + ( a - ( x % a) ) )
#define ALIGN_TO_16(x)  ALIGN_TO(x, 16)

#undef MEMPOOL_DEBUG
#define MEMPOOLASSERT


#define NODE_TO_DATA(x) ( ((char*)x) + sizeof(struct node) )
#define DATA_TO_NODE(x) ( (struct node*)(((char*)x) - sizeof(struct node)) )
struct ra_align(16) node {
    void    *next;
    void    *segment;
#ifdef MEMPOOLASSERT
    bool    used;
    uint64  magic;
#define NODE_MAGIC 0xBEEF00EAEACAFE07ll
#endif
};


// The Pointer to this struct is the base address of the segment itself.
struct pool_segment {
    mempool pool; // pool, this segment belongs to
    struct  pool_segment *next;
    int64   num_nodes_total;
    int64   num_bytes;
};


struct mempool {
    // Settings
    char *name;
    uint64  elem_size;
    uint64  elem_realloc_step;
    int64   elem_realloc_thresh;

    // Callbacks that get called for every node that gets allocated
    // Example usage: initialization of mutex/lock for each node.
    memPoolOnNodeAllocationProc     onalloc;
    memPoolOnNodeDeallocationProc   ondealloc;

    // Locks
    SPIN_LOCK segmentLock;
    SPIN_LOCK nodeLock;


    // Internal
    struct pool_segment *segments;
    struct node *free_list;

    volatile int64  num_nodes_total;
    volatile int64  num_nodes_free;

    volatile int64  num_segments;
    volatile int64  num_bytes_total;

    volatile int64  peak_nodes_used;        // Peak Node Usage
    volatile int64  num_realloc_events;     // Number of reallocations done. (allocate additional nodes)

    // list (used for global management such as allocator..)
    struct mempool *next;
} ra_align(8); // Dont touch the alignment, otherwise interlocked functions are broken ..


///
// Implementation:
//
static void segment_allocate_add(mempool p,  uint64 count);

static SPIN_LOCK l_mempoolListLock;
static mempool  l_mempoolList = NULL;
static rAthread l_async_thread = NULL;
static ramutex  l_async_lock = NULL;
static racond   l_async_cond = NULL;
static volatile int32 l_async_terminate = 0;

static void *mempool_async_allocator(void *x)
{
    mempool p;


    while (1) {
        if (l_async_terminate > 0)
            break;

        EnterSpinLock(&l_mempoolListLock);

        for (p = l_mempoolList;  p != NULL;  p = p->next) {

            if (p->num_nodes_free < p->elem_realloc_thresh) {
                // add new segment.
                segment_allocate_add(p, p->elem_realloc_step);
                // increase stats counter
                InterlockedIncrement64(&p->num_realloc_events);
            }

        }

        LeaveSpinLock(&l_mempoolListLock);

        ramutex_lock(l_async_lock);
        racond_wait(l_async_cond,   l_async_lock,  -1);
        ramutex_unlock(l_async_lock);
    }


    return NULL;
}//end: mempool_async_allocator()


void mempool_init()
{

    if (sizeof(struct node)%16 != 0) {
        ShowFatalError("mempool_init: struct node alignment failure.  %u != multiple of 16\n", sizeof(struct node));
        exit(EXIT_FAILURE);
    }

    // Global List start
    InitializeSpinLock(&l_mempoolListLock);
    l_mempoolList = NULL;

    // Initialize mutex + stuff needed for async allocator worker.
    l_async_terminate = 0;
    l_async_lock = ramutex_create();
    l_async_cond = racond_create();

    l_async_thread = rathread_createEx(mempool_async_allocator, NULL, 1024*1024,  RAT_PRIO_NORMAL);
    if (l_async_thread == NULL) {
        ShowFatalError("mempool_init: cannot spawn Async Allocator Thread.\n");
        exit(EXIT_FAILURE);
    }

}//end: mempool_init()


void mempool_final()
{
    mempool p, pn;

    ShowStatus("Mempool: Terminating async. allocation worker and remaining pools.\n");

    // Terminate worker / wait until its terminated.
    InterlockedIncrement(&l_async_terminate);
    racond_signal(l_async_cond);
    rathread_wait(l_async_thread, NULL);

    // Destroy cond var and mutex.
    racond_destroy(l_async_cond);
    ramutex_destroy(l_async_lock);

    // Free remaining mempools
    // ((bugged code! this should halppen, every mempool should
    //      be freed by the subsystem that has allocated it.)
    //
    EnterSpinLock(&l_mempoolListLock);
    p = l_mempoolList;
    while (1) {
        if (p == NULL)
            break;

        pn = p->next;

        ShowWarning("Mempool [%s] was not properly destroyed - forcing destroy.\n", p->name);
        mempool_destroy(p);

        p = pn;
    }
    LeaveSpinLock(&l_mempoolListLock);

}//end: mempool_final()


static void segment_allocate_add(mempool p,  uint64 count)
{

    // Required Memory:
    //  sz( segment )
    //  count * sz( real_node_size )
    //
    //  where real node size is:
    //      ALIGN_TO_16( sz( node ) ) + p->elem_size
    //  so the nodes usable address is  nodebase + ALIGN_TO_16(sz(node))
    //
    size_t total_sz;
    struct pool_segment *seg = NULL;
    struct node *nodeList = NULL;
    struct node *node = NULL;
    char *ptr = NULL;
    uint64 i;

    total_sz = ALIGN_TO_16(sizeof(struct pool_segment))
               + ((size_t)count * (sizeof(struct node) + (size_t)p->elem_size)) ;

#ifdef MEMPOOL_DEBUG
    ShowDebug("Mempool [%s] Segment AllocateAdd (num: %u, total size: %0.2fMiB)\n", p->name, count, (float)total_sz/1024.f/1024.f);
#endif

    // allocate! (spin forever until weve got the memory.)
    i=0;
    while (1) {
        ptr = (char *)aMalloc(total_sz);
        if (ptr != NULL) break;

        i++; // increase failcount.
        if (!(i & 7)) {
            ShowWarning("Mempool [%s] Segment AllocateAdd => System seems to be Out of Memory (%0.2f MiB). Try #%u\n", (float)total_sz/1024.f/1024.f,  i);
#ifdef WIN32
            Sleep(1000);
#else
            sleep(1);
#endif
        } else {
            rathread_yield(); /// allow/force vuln. ctxswitch
        }
    }//endwhile: allocation spinloop.

    // Clear Memory.
    memset(ptr, 0x00, total_sz);

    // Initialize segment struct.
    seg = (struct pool_segment *)ptr;
    ptr += ALIGN_TO_16(sizeof(struct pool_segment));

    seg->pool = p;
    seg->num_nodes_total = count;
    seg->num_bytes = total_sz;


    // Initialze nodes!
    nodeList = NULL;
    for (i = 0; i < count; i++) {
        node = (struct node *)ptr;
        ptr += sizeof(struct node);
        ptr += p->elem_size;

        node->segment = seg;
#ifdef MEMPOOLASSERT
        node->used = false;
        node->magic = NODE_MAGIC;
#endif

        if (p->onalloc != NULL)  p->onalloc(NODE_TO_DATA(node));

        node->next = nodeList;
        nodeList = node;
    }



    // Link in Segment.
    EnterSpinLock(&p->segmentLock);
    seg->next = p->segments;
    p->segments = seg;
    LeaveSpinLock(&p->segmentLock);

    // Link in Nodes
    EnterSpinLock(&p->nodeLock);
    nodeList->next = p->free_list;
    p->free_list = nodeList;
    LeaveSpinLock(&p->nodeLock);


    // Increase Stats:
    InterlockedExchangeAdd64(&p->num_nodes_total,  count);
    InterlockedExchangeAdd64(&p->num_nodes_free,   count);
    InterlockedIncrement64(&p->num_segments);
    InterlockedExchangeAdd64(&p->num_bytes_total,   total_sz);

}//end: segment_allocate_add()


mempool mempool_create(const char *name,
                       uint64 elem_size,
                       uint64 initial_count,
                       uint64 realloc_count,
                       memPoolOnNodeAllocationProc onNodeAlloc,
                       memPoolOnNodeDeallocationProc onNodeDealloc)
{
    //..
    uint64 realloc_thresh;
    mempool pool;
    pool = (mempool)aCalloc(1,  sizeof(struct mempool));

    if (pool == NULL) {
        ShowFatalError("mempool_create: Failed to allocate %u bytes memory.\n", sizeof(struct mempool));
        exit(EXIT_FAILURE);
    }

    // Check minimum initial count / realloc count requirements.
    if (initial_count < 50)
        initial_count = 50;
    if (realloc_count < 50)
        realloc_count = 50;

    // Set Reallocation threshold to 5% of realloc_count, at least 10.
    realloc_thresh = (realloc_count/100)*5; //
    if (realloc_thresh < 10)
        realloc_thresh = 10;

    // Initialize members..
    pool->name = aStrdup(name);
    pool->elem_size = ALIGN_TO_16(elem_size);
    pool->elem_realloc_step = realloc_count;
    pool->elem_realloc_thresh = realloc_thresh;
    pool->onalloc = onNodeAlloc;
    pool->ondealloc = onNodeDealloc;

    InitializeSpinLock(&pool->segmentLock);
    InitializeSpinLock(&pool->nodeLock);

    // Initial Statistic values:
    pool->num_nodes_total = 0;
    pool->num_nodes_free = 0;
    pool->num_segments = 0;
    pool->num_bytes_total = 0;
    pool->peak_nodes_used = 0;
    pool->num_realloc_events = 0;

    //
#ifdef MEMPOOL_DEBUG
    ShowDebug("Mempool [%s] Init (ElemSize: %u,  Initial Count: %u,  Realloc Count: %u)\n", pool->name,  pool->elem_size,  initial_count,  pool->elem_realloc_step);
#endif

    // Allocate first segment directly :)
    segment_allocate_add(pool, initial_count);


    // Add Pool to the global pool list
    EnterSpinLock(&l_mempoolListLock);
    pool->next = l_mempoolList;
    l_mempoolList = pool;
    LeaveSpinLock(&l_mempoolListLock);


    return pool;
}//end: mempool_create()


void mempool_destroy(mempool p)
{
    struct  pool_segment *seg, *segnext;
    struct  node *niter;
    mempool piter, pprev;
    char *ptr;
    int64 i;

#ifdef MEMPOOL_DEBUG
    ShowDebug("Mempool [%s] Destroy\n", p->name);
#endif

    // Unlink from global list.
    EnterSpinLock(&l_mempoolListLock);
    piter = l_mempoolList;
    pprev = l_mempoolList;
    while (1) {
        if (piter == NULL)
            break;


        if (piter == p) {
            // unlink from list,
            //
            if (pprev == l_mempoolList) {
                // this (p) is list begin. so set next as head.
                l_mempoolList = p->next;
            } else {
                // replace prevs next wuth our next.
                pprev->next = p->next;
            }
            break;
        }

        pprev = piter;
        piter = piter->next;
    }

    p->next = NULL;
    LeaveSpinLock(&l_mempoolListLock);


    // Get both locks.
    EnterSpinLock(&p->segmentLock);
    EnterSpinLock(&p->nodeLock);


    if (p->num_nodes_free != p->num_nodes_total)
        ShowWarning("Mempool [%s] Destroy - %u nodes are not freed properly!\n", p->name, (p->num_nodes_total - p->num_nodes_free));

    // Free All Segments (this will also free all nodes)
    // The segment pointer is the base pointer to the whole segment.
    seg = p->segments;
    while (1) {
        if (seg == NULL)
            break;

        segnext = seg->next;

        // ..
        if (p->ondealloc != NULL) {
            // walk over the segment, and call dealloc callback!
            ptr = (char *)seg;
            ptr += ALIGN_TO_16(sizeof(struct pool_segment));
            for (i = 0; i < seg->num_nodes_total; i++) {
                niter = (struct node *)ptr;
                ptr += sizeof(struct node);
                ptr += p->elem_size;
#ifdef MEMPOOLASSERT
                if (niter->magic != NODE_MAGIC) {
                    ShowError("Mempool [%s] Destroy - walk over segment - node %p invalid magic!\n", p->name, niter);
                    continue;
                }
#endif

                p->ondealloc(NODE_TO_DATA(niter));


            }
        }//endif: ondealloc callback?

        // simple ..
        aFree(seg);

        seg = segnext;
    }

    // Clear node ptr
    p->free_list = NULL;
    InterlockedExchange64(&p->num_nodes_free, 0);
    InterlockedExchange64(&p->num_nodes_total, 0);
    InterlockedExchange64(&p->num_segments, 0);
    InterlockedExchange64(&p->num_bytes_total, 0);

    LeaveSpinLock(&p->nodeLock);
    LeaveSpinLock(&p->segmentLock);

    // Free pool itself :D
    aFree(p->name);
    aFree(p);

}//end: mempool_destroy()


void *mempool_node_get(mempool p)
{
    struct node *node;
    int64 num_used;

    if (p->num_nodes_free < p->elem_realloc_thresh)
        racond_signal(l_async_cond);

    while (1) {

        EnterSpinLock(&p->nodeLock);

        node = p->free_list;
        if (node != NULL)
            p->free_list = node->next;

        LeaveSpinLock(&p->nodeLock);

        if (node != NULL)
            break;

        rathread_yield();
    }

    InterlockedDecrement64(&p->num_nodes_free);

    // Update peak value
    num_used = (p->num_nodes_total - p->num_nodes_free);
    if (num_used > p->peak_nodes_used) {
        InterlockedExchange64(&p->peak_nodes_used, num_used);
    }

#ifdef MEMPOOLASSERT
    node->used = true;
#endif

    return NODE_TO_DATA(node);
}//end: mempool_node_get()


void mempool_node_put(mempool p, void *data)
{
    struct node *node;

    node = DATA_TO_NODE(data);
#ifdef MEMPOOLASSERT
    if (node->magic != NODE_MAGIC) {
        ShowError("Mempool [%s] node_put failed, given address (%p) has invalid magic.\n", p->name,  data);
        return; // lost,
    }

    {
        struct pool_segment *node_seg = node->segment;
        if (node_seg->pool != p) {
            ShowError("Mempool [%s] node_put faild, given node (data address %p) doesnt belongs to this pool. ( Node Origin is [%s] )\n", p->name, data, node_seg->pool);
            return;
        }
    }

    // reset used flag.
    node->used = false;
#endif

    //
    EnterSpinLock(&p->nodeLock);
    node->next = p->free_list;
    p->free_list = node;
    LeaveSpinLock(&p->nodeLock);

    InterlockedIncrement64(&p->num_nodes_free);

}//end: mempool_node_put()


mempool_stats mempool_get_stats(mempool pool)
{
    mempool_stats stats;

    // initialize all with zeros
    memset(&stats, 0x00, sizeof(mempool_stats));

    stats.num_nodes_total   = pool->num_nodes_total;
    stats.num_nodes_free    = pool->num_nodes_free;
    stats.num_nodes_used    = (stats.num_nodes_total - stats.num_nodes_free);
    stats.num_segments      = pool->num_segments;
    stats.num_realloc_events= pool->num_realloc_events;
    stats.peak_nodes_used   = pool->peak_nodes_used;
    stats.num_bytes_total   = pool->num_bytes_total;

    // Pushing such a large block over the stack as return value isnt nice
    // but lazy :) and should be okay in this case (Stats / Debug..)
    // if you dont like it - feel free and refactor it.
    return stats;
}//end: mempool_get_stats()