Inside MySQL’s MEM_ROOT: How Memory Allocation Really Works

Key Macros Used by MEM_ROOT

#define MALLOC_OVERHEAD 8               // extra space kept during allocation
#define ALLOC_MAX_BLOCK_TO_DROP 4096    // used later to decide when to drop a block
#define ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP 10 // used later to decide when to drop a block
#define ALIGN_SIZE(A)   MY_ALIGN((A),sizeof(double))
#define MY_ALIGN(A,L)   (((A) + (L) - 1) & ~((L) - 1))
#define ALLOC_ROOT_MIN_BLOCK_SIZE (MALLOC_OVERHEAD + sizeof(USED_MEM) + 8)
#define MY_MAX(a,b) ((a) > (b) ? (a) : (b)) // maximum of two values
#define MY_MIN(a,b) ((a) < (b) ? (a) : (b)) // minimum of two values

MEM_ROOT Structure

typedef struct st_mem_root {
    USED_MEM *free;               // head of free‑block linked list
    USED_MEM *used;               // head of used‑block linked list
    USED_MEM *pre_alloc;          // pre‑allocated block
    size_t    min_malloc;         // threshold below which a block is considered too small
    size_t    block_size;         // size used when a new block is created
    unsigned int block_num;       // current number of blocks (starts at 4)
    unsigned int first_block_usage; // count of how many times the first free block failed to satisfy a request
    void (*error_handler)(void);  // callback on allocation failure
} MEM_ROOT;

USED_MEM Structure (individual blocks)

typedef struct st_used_mem {
    struct st_used_mem *next; // next block in the list
    unsigned int left;        // remaining free bytes in this block
    unsigned int size;        // total size of the block
} USED_MEM;

Initialization of MEM_ROOT

void init_alloc_root(MEM_ROOT *mem_root, size_t block_size, size_t pre_alloc_size __attribute__((unused))) {
    mem_root->free = mem_root->used = mem_root->pre_alloc = 0;
    mem_root->min_malloc = 32;
    mem_root->block_size = block_size - ALLOC_ROOT_MIN_BLOCK_SIZE;
    mem_root->error_handler = 0;
    mem_root->block_num = 4;               // effectively 4 >> 2 = 1 for the first expansion
    mem_root->first_block_usage = 0;
}

During initialization the effective block size is reduced by ALLOC_ROOT_MIN_BLOCK_SIZE. When the allocator needs to grow, it multiplies mem_root->block_size by mem_root->block_num >> 2; because block_num starts at 4, the first expansion uses a factor of 1.

Memory Allocation Routine (alloc_root)

void *alloc_root(MEM_ROOT *mem_root, size_t length) {
    size_t get_size, block_size;
    uchar *point;
    reg1 USED_MEM *next = 0;
    reg2 USED_MEM **prev;

    length = ALIGN_SIZE(length);

    if ((*(prev = &mem_root->free)) != NULL) {
        if ((*prev)->left < length &&
            mem_root->first_block_usage++ >= ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP &&
            (*prev)->left < ALLOC_MAX_BLOCK_TO_DROP) {
            next = *prev;
            *prev = next->next;               // remove from free list
            next->next = mem_root->used;
            mem_root->used = next;
            mem_root->first_block_usage = 0;
        }
        for (next = *prev; next && next->left < length; next = next->next) {
            prev = &next->next;
        }
    }

    if (!next) { // need a new block
        block_size = mem_root->block_size * (mem_root->block_num >> 2);
        get_size = length + ALIGN_SIZE(sizeof(USED_MEM));
        get_size = MY_MAX(get_size, block_size);

        if (!(next = (USED_MEM*)my_malloc(get_size, MYF(MY_WME | ME_FATALERROR)))) {
            if (mem_root->error_handler) {
                (*mem_root->error_handler)();
            }
            DBUG_RETURN((void*)0);
        }
        mem_root->block_num++;
        next->next = *prev;
        next->size = get_size;
        next->left = get_size - ALIGN_SIZE(sizeof(USED_MEM)); // note: double‑counting bug mentioned in source
        *prev = next;
    }

    point = (uchar*)((char*)next + (next->size - next->left));
    // TODO: next part may be unnecessary due to mem_root->first_block_usage counter
    if ((next->left -= length) < mem_root->min_malloc) { // block becomes full
        *prev = next->next;               // remove from free list
        next->next = mem_root->used;
        mem_root->used = next;
        mem_root->first_block_usage = 0;
    }
    return (void*)point;
}

The function first aligns the requested size, then scans the free list for a block with enough left bytes. If a block is too small and has been examined more than ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP times, or its remaining space is below ALLOC_MAX_BLOCK_TO_DROP, it is moved to the used list.

If no suitable block exists, a new block is allocated. The size chosen is the larger of the aligned request plus the overhead of USED_MEM and the heuristic block_size computed from the current block_num. After successful allocation, block_num is incremented.

Finally, the function returns a pointer to the allocated region inside the chosen block and, if the block’s remaining space falls below min_malloc, the block is transferred to the used list.

Pointer‑Level Details

The variable prev is a double pointer that always points to the next field of the previous node in the list. When a new block is appended to the end of the free list, the assignment *prev = next; effectively links the new block after the last existing block.

Summary

MEM_ROOT uses a heuristic allocation strategy: as more blocks are created, the size of each new block grows according to

block_size = mem_root->block_size * (mem_root->block_num >> 2)

. The allocator maintains two linked lists ( free and used) and moves blocks between them based on usage counters and size thresholds, providing a balance between speed and memory fragmentation.