Understanding MySQL’s MEM_ROOT: Structure, Macros, and Allocation Mechanics

Key Macros Used by MEM_ROOT

#define MALLOC_OVERHEAD 8 // extra space reserved during allocation
#define ALLOC_MAX_BLOCK_TO_DROP 4096 // see usage later
#define ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP 10 // see usage later
#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))
#define MY_MIN(a,b) ((a) < (b) ? (a) : (b))

MEM_ROOT Structure

typedef struct st_mem_root {
    USED_MEM *free;               // head of free‑block list
    USED_MEM *used;               // head of used‑block list
    USED_MEM *pre_alloc;          // pre‑allocated block
    size_t    min_malloc;         // threshold to move block from free to used
    size_t    block_size;         // size of each block after init
    unsigned int block_num;      // actual number of blocks (starts at 4)
    unsigned int first_block_usage; // count of first‑block failures
    void (*error_handler)(void); // called 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 space 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;               // initial block count (4>>2 == 1)
    mem_root->first_block_usage = 0;
}

During initialization the effective block size is reduced by ALLOC_ROOT_MIN_BLOCK_SIZE. When more memory is needed, the allocator expands the pool using mem_root->block_num >> 2 * block_size, ensuring mem_root->block_num >> 2 is at least 1.

Allocation Routine (alloc_root)

void *alloc_root(MEM_ROOT *mem_root, size_t length) {
    size_t get_size, block_size;
    uchar *point;
    USED_MEM *next = 0;
    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;            // add to used list
            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));
        *prev = next;
    }
    point = (uchar*)((char*)next + (next->size - next->left));
    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 algorithm first scans the free list for a block with enough space. If a block is found but its remaining space is too small and it has been examined ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP times, the block is moved to the used list. If no suitable block exists, a new block is allocated using the larger of the calculated block size and the required size plus header.

Pointer Mechanics

The double‑pointer prev always points to the next field of the preceding node (or the head pointer). When a new block is inserted, the code assigns *prev = next;, effectively appending the new block to the end of the free list.

Overall Summary

MEM_ROOT implements a heuristic memory allocator for MySQL. It maintains two linked lists— free and used —and grows block size as the number of blocks increases (

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

). The allocator balances reuse of existing blocks with allocation of larger blocks when necessary, and it uses a simple counter to decide when to move under‑utilized blocks to the used list.