MySQL MEM_ROOT explained in detail

This article will explain in detail the MEM_ROOT structure that is widely used in MySQL, while omitting the debug part of the information and only analyzing the part where MEM_ROOT is used for memory allocation in MySQL under normal circumstances.

Before the specific analysis, let’s give an example of some macros used in the use of this structure:

#define MALLOC_OVERHEAD 8 //分配过程中，需要保留一部分额外的空间
#define ALLOC_MAX_BLOCK_TO_DROP 4096 //后续会继续分析该宏的用途
#define ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP 10 //后续会继续分析该宏的用途

#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 some useful general macros (should be done after all headers). */
/*作者：www.manongjc.com  */
#define MY_MAX(a, b) ((a) > (b) ? (a) : (b)) //求两个数值之间的最大值
#define MY_MIN(a, b) ((a) < (b) ? (a) : (b)) //求两个数值之间的最小值

Let’s take a look at the information related to the MEM_ROOT structure:

typedef struct st_mem_root
{
    USED_MEM    *free;                  /* free block link list的链表头指针 */
    USED_MEM    *used;                  /* used block link list的链表头指针 */
    USED_MEM    *pre_alloc;             /* 预先分配的block */
    size_t        min_malloc;             /* 如果block剩下的可用空间小于该值，将会从free list移动到used list */
    size_t        block_size;             /* 每次初始化的空间大小 */
    unsigned int    block_num;              /* 记录实际的block数量,初始化为4 */
    unsigned int    first_block_usage;      /* free list中的第一个block 测试不满足分配空间大小的次数 */
    void (*error_handler)( void );          /* 分配失败的错误处理函数 */
} MEM_ROOT;

The following is the specific block information allocated.

typedef struct st_used_mem
{ 
    struct st_used_mem *next; //指向下一个分配的block
    unsigned int left; //该block剩余的空间大小
    unsigned int size; //该block的总大小
} USED_MEM;

In fact, MEM_ROOT manages used and free blocks through a doubly linked list during the allocation process:

The initialization process of MEM_ROOT is as follows:

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; /* We shift this with >>2 */
    mem_root->first_block_usage    = 0;
}

During the initialization process, the block_size space is block_size-ALLOC_ROOT_MIN_BLOCK_SIZE. Because when the memory is not enough and needs to be expanded, the capacity is expanded through mem_root->block_num >>2 * block_size, so mem_root->block_num >>2 is at least 1, so during the initialization process mem_root->block_num=4 (note :4>>2=1).

Let’s take a look at the specific steps of allocating memory:

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 block from 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 )
    {       /* Time to alloc 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 );                              /* purecov: inspected */
        }
        mem_root->block_num++;
        next->next    = *prev;
        next->size    = get_size;
        next->left    = get_size - ALIGN_SIZE( sizeof(USED_MEM) );    /* bug:如果该block是通过mem_root->block_size * (mem_root->block_num >> 2)计算出来的，则已经去掉了ALIGN_SIZE(sizeof(USED_MEM)，这里重复了。 */
        *prev        = next;
    }

    point = (uchar *) ( (char *) next + (next->size - next->left) );
/*TODO: next part may be unneded due to mem_root->first_block_usage counter*/
/* 作者：www.manongjc.com */
    if ( (next->left -= length) < mem_root->min_malloc )
    {                                                                       /* Full block */
        *prev                = next->next;                   /* Remove block from list */
        next->next            = mem_root->used;
        mem_root->used            = next;
        mem_root->first_block_usage    = 0;
    }
}

The specific logic of the above code is as follows:

1. Check the free linked list to find a block that meets the space. If a suitable block is found, then:
1.1 Directly return the initial address of the block from size-left. Of course, during the free list traversal process, it will be judged that the left space in the first block in the free list does not meet the space that needs to be allocated, and the block has been searched 10 times (ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP) and does not meet the allocation requirement. length, and the remaining space of the block is less than
4k (ALLOC_MAX_BLOCK_TO_DROP), then move the block to the used linked list.

2. If there is no suitable block in the free linked list, then:

2.1 Allocate the larger of mem_root->block_size * (mem_root->block_num >> 2) and length+ALIGN_SIZE(sizeof(USED_MEM))

as the new block memory space.
2.2 Depending on the usage of the block, hang the block on the used or free linked list.

What needs to be noted here is the use of secondary pointers:

for (next= *prev ; next && next->left < length ; next= next->next)
prev= &next->next;
}

prev points to the address of the address pointed to by next of the last block:

So replace the address of prev with the address of the new block, that is, the address of the new block The new block is added to the end of the free list: *prev=next;

Summary:

MEM_ROOT uses a heuristic allocation algorithm. As the number of subsequent blocks increases, the memory of a single block will also increase. The larger: block_size= mem_root->block_size * (mem_root->block_num >> 2) .