Memory management for small allocations

Question

This code is for a program that needs to add thousands of strings to memory while it's running and these strings will be used until the end of execution. So the memory for these strings will be freed only in the end.

First I tested calling malloc for every new string and have used Valgrind to benchmark total execution cost for 200 hundred thousand strings. Then I wrote these memory handling functions that call malloc once and hand out small chunks of memory for every string. The overall execution cost for the entire program went down over 20%.

This is my first attempt at doing this, so I know this code is probably bad. I would like to know exactly what is wrong with it, so I won't make the same mistakes again.

//The actual numbers will be smaller after DEBUG
#define BIG_BLOCK       1073741824  //  1GiB ..........
#define MEDIUM_BLOCK     524288000  //500MiB .....
#define SMALL_BLOCK      104857600  //100MiB .

//Linked-list containing the required data for each malloc'ed block
typedef struct {
   void   *mem_pool;   //starting address for this block
   void   *next;       //next node
   size_t *position;   //current position
   size_t *available;  //how much memory was allocated?
} memory_t;

//First link
static memory_t *root = 0;

//handles malloc and returns a new memory_t node, it allocates
//more memory on the first call than on subsequent calls
static void *increase_memory(void)
{
    void        *result    = 0;
    memory_t    *new_block = 0;
    static int  firstCall  = 0;
    static const size_t default_sizes[] = {BIG_BLOCK, MEDIUM_BLOCK, SMALL_BLOCK, 0};

    for(size_t i = firstCall; default_sizes[i] != 0; ++i)
    {
        if((result = malloc(default_sizes[i])))
        {
            new_block = result;
            new_block->mem_pool = new_block;                                    //starting address for this block
            new_block->next = 0;                                                //link to next node
            new_block->position = result + sizeof(memory_t);                    //space for size_t *position
            *new_block->position = sizeof(memory_t) + sizeof(size_t) * 2;       //remove used addresses from pool (position, available)
            new_block->available = result + sizeof(memory_t) + sizeof(size_t);  //allocate space for size_t *available
            *new_block->available = default_sizes[i];                           //how much was allocated
            break;
        }
    }
    firstCall = 1; //first call happened, let's malloc smaller blocks
    return result;
}

//mallocs the first block, called by main()
int init_mem_pool(void)
{
    static int initialized = 0;
    if(!initialized++) root = increase_memory(); //protection against multiple calls

    return (root) ? 1 : 0;
    //Should I change the line above?
    //I believe it doesn't need to be this way but GCC compiler warns when the following are used:
    //return root;
    //return (int)root;
    //What should be done here?
}

//hands out memory chunks
void *get_memory(const size_t size)
{
    memory_t *current = root;
    void *temp = 0;

    while(current)
    {        
        //there's enough memory in the current node
        if((*current->position + size) < *current->available) //Brackets added for clarity, not sure if it's bad style...
        {
            temp = current->mem_pool + *current->position;
            *current->position += size;
            break;
        }

        //not enough memory, go to next node
        else if(current->next) current = current->next;

        //all nodes are full, create another one
        else current = current->next = increase_memory();
    }
    return temp;
}

//free all nodes
static void recursive_free(const memory_t * const node)
{
    if(node->next) recursive_free(node->next);
    free(node->mem_pool);
}

//called by main(), free all nodes
void clean_mem(void)
{
    //is there anything to free?
    if(root)recursive_free(root);
}

Answer 1

1. I know it's kind of standard to do this in C land but you should spell things like this if((result = malloc(default_sizes[i]))) out as:

   result = malloc(default_sizes[i]);
   if (result != NULL)
   {
   }
   

   Yes it's one line of code more but the intent is much more obvious at a first glance. As suggested in the comments you might want to invert the condition and continue. Reduces the level of nesting:

   result = malloc(default_sizes[i]);
   if (result == NULL) { continue; }
   

   Technically it's better to write if (NULL == result) because if you accidentally write = instead of == then the compiler will throw an error instead of compiling buggy code - I just can't seem to get myself into that habit for some reason. Probably because it reads a bit clunkier that way (imho).

2. It's perfectly legal for a struct to contain a pointer to itself like this:

   typedef struct memory_ {
       void           *mem_pool;   //starting address for this block
       struct memory_ *next;       //next node
       size_t         *position;   //current position
       size_t         *available;  //how much memory was allocated?
   } memory_t;
   

3. The return type of increase_memory should be memory_t * because that's what it returns. You can also get rid of result in there and use new_block in its place.

4. In init_mem_pool you asked some questions on the return value. I guess you want it to indicate whether the initialization was successful or not - which is if root is NULL or not so you can just write this:

   return root != NULL;
   

Answer 2

I would make the defines a little easier to read/change:

#define MEGABYTE        (1024 * 1024)
#define BIG_BLOCK       (1024 * MEGABYTE)
etc

---

In increase_memory, result is redundant and firstCall uses inconsistent naming style (Camel case). The way this variable is used is also wrong. Firstly, its use implies that it should be named first_call_has_been_done (no don't do that). If instead it is initialized to 1 and then reset to 0 on exit, its name now makes sense. However that then makes the loop initialization wrong, as i now starts at 1 on the first call:

for(size_t i = firstCall; default_sizes[i] != 0; ++i)...

which shows that you have misused the variable (used it for two logically separate purposes). What you meant was:

static int firstCall = 1;
size_t i = 1;
if (firstCall) {
     i = 0;
}
for (; default_sizes[i] != 0; ++i)...

which can be written:

static int firstCall = 1;
for(size_t i = firstCall ? 0 : 1; default_sizes[i] != 0; ++i)...

and now we have isolated the boolean and the array index. It amounts to the same thing but it is clearer what you mean.

I also don't see the logic in using three allocation sizes as you have. Is that an optimization to your target?

---

If it were my code, I would simplify the structure by using an zero-sized element at the end of the struct and not using pointers for the size or offset (in your existing code, I don't see why position/available are pointers and not offset/size integers). Also note that the _t suffix is reserved (posix I think). So I would get:

typedef struct mem {
    struct mem *next;
    size_t offset;
    size_t size;
    char block[];
} Memory;

And then using this I would just allocate the same size for each block

static Memory* increase_memory(void)
{
    Memory *block = malloc(BLOCKSIZE);
    if (block) {
        block->offset = 0;
        block->size = BLOCKSIZE - sizeof(Memory);
        block->next = 0;
    }
    return block;
}

The block data is then accessible using array indexing.