4
\$\begingroup\$

I wrote this snippet to allocate blocks of memory, whose sizes and number are available during initialisation. I choose to equally divide the statically allocated memory. There are some error checks before allocating a block to a pool of memory and I maintain a free list in the memory blocks. It is not thread safe at the moment. Can I get some feedback?

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>

#define MAX_POOLS 4     // ceiling for num of pools
#define HEAP_SIZE 65536 // input heap size

// simple linked list
typedef struct {
    void* next;
} node_t;

typedef struct {
    uint16_t max_blocks;     // max allowed blocks
    uint16_t blocks_alloced; // contiguous blocks allocated
    uint8_t* pool_start;     //starting address of the pool
    node_t*  head;           // free list pointer
    size_t   block_size;     // block size
} pool_allocator_t;

static uint8_t pool_heap[HEAP_SIZE];
pool_allocator_t g_pools[MAX_POOLS];

static inline bool is_power_of_two(size_t in);

// added for tests
void pool_deinit(void)
{
    memset(pool_heap, 0, HEAP_SIZE);
    memset(g_pools, 0, MAX_POOLS);
}

bool pool_init(size_t* block_sizes, size_t block_size_count)
{
    // not supported
    if (block_size_count > MAX_POOLS) {
        return false;
    }

    // non positive inputs are invalid
    for (int i = 0; i < block_size_count; ++i) if ((int64_t)(block_sizes[i]) <= 0) return false;

    size_t unalloc_space = sizeof(pool_heap);
    uint8_t* boundary_start = pool_heap;
    uint8_t* boundary_end = pool_heap + sizeof(pool_heap);


    memset(g_pools, 0, MAX_POOLS * sizeof(pool_allocator_t));

    uint8_t* base_address = boundary_start;
    // equally sized partitions
    uint16_t partition_size = unalloc_space / block_size_count;

    for (int i = 0; i < block_size_count; ++i) {
        if (!is_power_of_two(block_sizes[i]) // enforce power of two numbers only, doesn't exactly take care of alignment issues
                || block_sizes[i] > partition_size // bigger than partition?
                || base_address > boundary_end // did we overstep?
                || base_address + block_sizes[i] > boundary_end) { // is expected size not going to be fulfilled?
            // clean up
            memset(g_pools, 0, MAX_POOLS * sizeof(pool_allocator_t));
            // init failed. fails even if first few blocks have been allocated successfully
            return false;
        }
        g_pools[i].pool_start = base_address;
        g_pools[i].head = NULL;
        g_pools[i].block_size = block_sizes[i];
        g_pools[i].max_blocks = partition_size / block_sizes[i];
        unalloc_space -= partition_size;
        base_address += (g_pools[i].max_blocks * g_pools[i].block_size);

        // print stats for this partition
    }

    return true;

}

void* pool_malloc(size_t n)
{
    // non-positive numbers are invalid inputs
    if ((int64_t)n <= 0) return NULL;

    pool_allocator_t* pool = NULL;

    // decide which partition will it go to
    uint8_t valid_partition = UINT8_MAX;
    size_t valid_block = UINT32_MAX;
    for (int i = 0; i < MAX_POOLS; ++i) {
        // get smallest block size out of all pools that can fit this input
        if (g_pools[i].pool_start != NULL
                && n <= g_pools[i].block_size
                && g_pools[i].block_size <= valid_block) {
            valid_block = g_pools[i].block_size;
            valid_partition = i;
        }
    }

    // valid partition was found
    if (valid_partition != UINT8_MAX) {
        pool = &g_pools[valid_partition];
    }


    // no relevant partition found for this size
    if (pool == NULL) {
        return NULL;
    }

    if (n <= pool->block_size) {
    } else {
        return NULL;
    }

    // result block pointer, start with NULL
    node_t* ret_block = NULL;

    // see if memory is already available before getting new block?
    if (pool->head != NULL) {
        // head is non-null, so we have a previously freed block for use
        // get this block's address and update head
        ret_block = pool->head;
        pool->head = pool->head->next;
    } else {
        // head is null, all previously allocated blocks are still under use. get a new block
        // check if space is available
        if (pool->blocks_alloced < pool->max_blocks) {
            // get address of new block, increment blocks under use
            ret_block = (void *)(pool->pool_start + pool->blocks_alloced * pool->block_size);
            pool->blocks_alloced++;
        } else {
            // cannot satisfy requirement, fail
        }

    }

    return ret_block;
}

void pool_free(void* ptr)
{

    // base case
    if (ptr == NULL) {
        return;
    }

    // check if it is beyond the boundaries of heap
    if (ptr < (void*)pool_heap || ptr >= (void*)&pool_heap[HEAP_SIZE]) {
    }

    pool_allocator_t* pool = NULL;

    uint8_t allocated_pools = 0;
    for(int i = 0; i < MAX_POOLS; ++i) if (g_pools[i].pool_start != NULL) allocated_pools++;

    // find which partition the memory exists in
    for (int i = 0; i < allocated_pools; ++i) {

        void* curr_pool_boundary = (void*)( g_pools[i].pool_start + g_pools[i].max_blocks * g_pools[i].block_size);

        if (ptr >= (void*)g_pools[i].pool_start // within boundary of this pool
                && ptr < curr_pool_boundary // within boundary of this pool
                && ((uint8_t*)ptr - g_pools[i].pool_start) % g_pools[i].block_size == 0) { //check if it is pointing to a valid block

            // found in this bin, check if it is pointing to a valid block
            pool = &g_pools[i];
        }

    }

    // memory block wasn't found, exit
    if (pool == NULL) {
        return;
    }

    // set to 0, may not be necessary
    memset(ptr, 0, pool->block_size);
    // now that it's de-allocated, we can make it a node
    node_t* freed_mem = (node_t*)ptr;
    // point next to previous free location
    freed_mem->next = pool->head;
    // last freed node should become head
    pool->head = freed_mem;
}

static inline bool is_power_of_two(size_t in)
{
    return (in & (in - 1)) == 0;
}

int main()
{
    size_t block[4] = {32, 64, 256, 1024};
    bool ret = pool_init(block, sizeof(block)/sizeof(block[0]));
    void* data1 = pool_malloc(16);
    void* data2 = pool_malloc(65);
    void* data3 = pool_malloc(1024);
    return 0;
}
```
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Looks like you're missing some code early in my_pool_init, right before the indented unalloc_space, line. That and the next two lines look like parameters to a function call but there is no function call and it won't currently compile. \$\endgroup\$ Dec 4, 2019 at 20:48
  • 1
    \$\begingroup\$ is_power_of_two will return true when in is 0. \$\endgroup\$ Dec 4, 2019 at 20:48
  • \$\begingroup\$ The declarations/definitions of pool_heap and g_pools are missing. The header files included are also missing (stdint.h, stdbool.h, and string.h), At the moment there is too much missing for us to review the code. \$\endgroup\$
    – pacmaninbw
    Dec 4, 2019 at 20:58
  • 1
    \$\begingroup\$ Edited code to produce a compile-worthy snippet. I check for non-positive integers before initializing, so is_power_of_two returning true for 0 should not happen? But that is a correct callout. \$\endgroup\$
    – rookie
    Dec 4, 2019 at 21:03

1 Answer 1

2
\$\begingroup\$

Algorithm

This looks like it was primarily developed as a library, it is possible on code review to provide separate files for review. Most of the code belongs possibly in a file called memoryblockallocator.c, there should also be a memoryblockallocator.h that provides the public function prototypes for memoryblockallocator.c. The main() function can be in a separate file called main.c which includes the header file memoryblockallocator.h. Within memoryblockallocator.c both pool_heap and g_pools should be declared as static so that they are not accessible to the rest of the program, currently only pool_heap is declared as static.

Due to the logic in is_power_of_two() there is no benefit in declaring this an inline function, also modern C compilers that optimize the generated code may ignore inline since it is only a recommendation in the C99 standard.

There is no need to put a size into the declaration size_t block[4] = {32, 64, 256, 1024}; in main(), C will give it the proper size, and the code already contains the proper way to calculate the size in the call to pool_init().

In the function void pool_free(void* ptr) it might be good if the code merged adjacent blocks so that if the memory needs to be allocated again it isn't too fragmented. When allocating memory it might be good to use either a best fit or first fit algorithm for the allocation also to reduce the possibility of fragmentation. To do this the node struct may need to be augmented with more information.

Lack of Error Checking or Checking of Return Values

The function pool_init(size_t* block_sizes, size_t block_size_count) returns a bool value indicating the success or failure of the initialization, but this is ignored in main(). If pool_intit() fails main() should probably report an error and exit.

Unused and Untested Functions

Niether the function void pool_deinit(void) or the function void pool_free(void* ptr) are called in the program. In the case of void pool_free(void* ptr) this means that an important and complex part of the code is not being tested. It would not be good to trust that void pool_free(void* ptr) is working properly without testing it.

If Statements That Don't Do Anything

In the function void pool_free(void* ptr) there is this if statement that doesn't change anything:

    // check if it is beyond the boundaries of heap
    if (ptr < (void*)pool_heap || ptr >= (void*)&pool_heap[HEAP_SIZE]) {
    }

If there is no action then this if statement isn't necessary

In the function void* pool_malloc(size_t n) there is this if statement.

    if (n <= pool->block_size) {
    } else {
        return NULL;
    }
    

The logic can be changed so that the code is simplified so there are no empty code blocks.

    if (n > pool->block_size) {
        return NULL;
    }

Inconsistent Use of Code Blocks in Flow Control

Withing the function void pool_free(void* ptr) there are these statements that control the flow of the function:

    if (ptr == NULL) {
        return;
    }


    for(int i = 0; i < MAX_POOLS; ++i) if (g_pools[i].pool_start != NULL) allocated_pools++;


    if (pool == NULL) {
        return;
    }

The first thing to notice is that two of the three if statements wrap braces around a single statement, this is a good practice, this code can be expanded easily in maintenance. The inconsistency is the for loop does not wrap the if statement in braces and the if statement does not wrap the action in braces either. This code will be very difficult to maintain by you or anyone that inherits the code. A second problem with the for loop is that there are 3 statements all on one line which is even harder to maintain. Based on the other statements in this function I would expect to see:

    for(int i = 0; i < MAX_POOLS; ++i)
    {
        if (g_pools[i].pool_start != NULL) 
        {
            allocated_pools++;
        }
    }

This could easily be turned into a function to reduce the amount of code in void pool_free(void* ptr)

static  uint8_t count_allocated_pools()
{
    uint8_t allocated_pools = 0;

    for(int i = 0; i < MAX_POOLS; ++i)
    {
        if (g_pools[i].pool_start != NULL)
        {
            allocated_pools++;
        }
    }

    return  allocated_pools;
}

Breaking the code up in this manner makes it easier to write, read, debug and maintain.

The suggestions in this section apply to the other functions as well.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you for the detailed feedback! Is it good practice to not explicitly specify size of an array when it is initialized, like int a[] = {3,4}? Secondly, since allocation is only of individual blocks and a free list is maintained, are there chances of fragmentation? Thirdly, is casting size_t to int64_t a valid way to check for negative numbers passed to a function accepting size_t? \$\endgroup\$
    – rookie
    Dec 5, 2019 at 7:23
  • 1
    \$\begingroup\$ The size_t type is unsigned, it can't ever be negative, it might wrap overflow where you go from a very large number back to zero so no. a[] = {3,4} is the most common way of initializing variables. Because your free list never merges adjacent free blocks back together you by default are fragmenting the memory. \$\endgroup\$
    – pacmaninbw
    Dec 5, 2019 at 13:20
  • \$\begingroup\$ C will not complain if a negative number is passed as an argument to a function accepting size_t. So it is upto the library to handle this case. I thought casting to int64_t would help in this case(to identify negative input). I'm not sure how to handle this case. \$\endgroup\$
    – rookie
    Dec 5, 2019 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.