Simple lock-free memory pool based on linked list

divert_mem_pool.c

#include "divert_mem_pool.h"
#include <stdlib.h>


divert_mem_pool_t *divert_create_pool(size_t max_alloc) {
    divert_mem_pool_t *pool =
            calloc(sizeof(divert_mem_pool_t), 1);
    if (pool == NULL) {
        return NULL;
    }
    pool->pool = calloc(sizeof(divert_mem_block_t *), max_alloc + 1);
    if (pool->pool == NULL) {
        free(pool);
        return NULL;
    }
    pool->max = max_alloc;
    pool->num_alloc = 0;
    pool->num_reuse = 0;
    pool->num_failed = 0;
    return pool;
}

void divert_destroy_pool(divert_mem_pool_t *pool) {
    if (pool != NULL) {
        // first free all memory blocks
        for (int idx = 0; idx <= pool->max; idx++) {
            for (divert_mem_block_t *blk = pool->pool[idx];
                 blk; blk = blk->next) {
                free(blk);
            }
        }
        // then free the entire pool
        if (pool->pool != NULL) {
            free(pool->pool);
        }
        free(pool);
    }
    return;
}

void *divert_mem_alloc(divert_mem_pool_t *pool, size_t size) {
    if (size > pool->max) { return NULL; }
    divert_mem_block_t *block = NULL, *next_blk = NULL;
    // remove a memory block from pool
    do {
        block = pool->pool[size];
        if (block == NULL) { break; }
        next_blk = block->next;
    } while (!__sync_bool_compare_and_swap(&pool->pool[size], block, next_blk));
    // if got a block of memory, just return it
    if (block != NULL) {
        block->next = NULL;
        // update number of reused blocks
        __sync_fetch_and_add(&pool->num_reuse, 1);
        return (void *)block + sizeof(divert_mem_block_t);
    }
    // if not, we allocate a new block of memory
    void *p = calloc(sizeof(divert_mem_block_t) + size, 1);
    if (p != NULL) {
        block = p;
        block->size = size;
        // update number of new allocated blocks
        __sync_fetch_and_add(&pool->num_alloc, 1);
        return p + sizeof(divert_mem_block_t);
    } else {
        // return NULL if allocation failed
        __sync_fetch_and_add(&pool->num_failed, 1);
        return NULL;
    }
}

void divert_mem_free(divert_mem_pool_t *pool, void *p) {
    if (p == NULL) { return; };
    divert_mem_block_t *block = p - sizeof(divert_mem_block_t);
    divert_mem_block_t *head = NULL;
    size_t size = block->size;
    do {
        head = pool->pool[size];
        block->next = head;
    } while (!__sync_bool_compare_and_swap(&pool->pool[size], head, block));
    return;
}

divert_mem_pool.h

#ifndef DIVERT_DIVERT_MEM_POOL_H
#define DIVERT_DIVERT_MEM_POOL_H


#include <unistd.h>
#include <_types/_uint32_t.h>


typedef struct divert_mem_block_s divert_mem_block_t;

struct divert_mem_block_s {
    size_t size;
    divert_mem_block_t *next;
};

typedef struct {
    divert_mem_block_t **pool;
    size_t num_alloc;
    size_t num_reuse;
    size_t num_failed;
    size_t max;
} divert_mem_pool_t;


divert_mem_pool_t *divert_create_pool(size_t max_alloc);

void divert_destroy_pool(divert_mem_pool_t *pool);

void *divert_mem_alloc(divert_mem_pool_t *pool, size_t size);

void divert_mem_free(divert_mem_pool_t *pool, void *p);

#endif //DIVERT_DIVERT_MEM_POOL_H

test_mem_pool.c

#include "divert_mem_pool.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <pthread.h>
#include <sys/types.h>


#define MAX_LOOP    10000
#define MEM_SIZE    1300
#define NUM_THREADS 16

void *thread_func(void *p) {
    divert_mem_pool_t *pool = p;
    int *res = calloc(sizeof(int), 1);
    u_char *data = calloc(MEM_SIZE, 1);
    // generate random data
    for (int i = 0; i < MEM_SIZE; i++) {
        data[i] = (u_char)rand();
    }
    for (int i = 0; i < MAX_LOOP; i++) {
        // allocate a block of memory
        void *buf = divert_mem_alloc(pool, MEM_SIZE);
        // copy private data of this thread
        memcpy(buf, data, MEM_SIZE);
        // sleep for up to 10 ms
        usleep((useconds_t)rand() % 10000);
        // check if data in buffer is still right
        for (int j = 0; j < MEM_SIZE; j++) {
            if (((u_char *)buf)[j] != data[j]) {
                puts("Fuck!");
                *res = 1;
            }
        }
        // randomly free the memory
        if (rand() % 2) {
            divert_mem_free(pool, buf);
        }
    }
    return res;
}



int main() {
    void *res;
    srand(time(NULL));
    divert_mem_pool_t *pool = divert_create_pool(MEM_SIZE);
    pthread_t threads[NUM_THREADS];
    // threads start
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_create(&threads[i], NULL, thread_func, pool);
    }
    // threads join
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], &res);
    }
    if (*(int *)res == 0) {
        puts("Success");
        printf("Num reused: %zu, num new allocated: %zu\n",
               pool->num_reuse, pool->num_alloc);
        divert_destroy_pool(pool);
    } else {
        puts("Failed");
    }
}