MySQL MEM_ROOT ausführlich erklärt

In diesem Artikel wird die in MySQL weit verbreitete MEM_ROOT-Struktur ausführlich erläutert. Gleichzeitig wird der Debug-Teil der Informationen weggelassen und nur der Teil analysiert, in dem MEM_ROOT unter normalen Umständen für die Speicherzuweisung verwendet wird .

Vor der spezifischen Analyse listen wir zunächst einige Makros auf, die bei der Verwendung dieser Struktur verwendet werden:

#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)) //求两个数值之间的最小值

Werfen wir einen Blick auf die Informationen zur MEM_ROOT-Struktur:

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;

Im Folgenden sind die spezifischen Blockinformationen aufgeführt.

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

Tatsächlich verwaltet MEM_ROOT während des Zuweisungsprozesses verwendete und freie Blöcke über eine doppelt verknüpfte Liste:

Der Initialisierungsprozess von MEM_ROOT ist wie folgt:

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;
}

Während des Initialisierungsprozesses beträgt der block_size-Speicherplatz block_size-ALLOC_ROOT_MIN_BLOCK_SIZE. Denn wenn der Speicher nicht ausreicht und erweitert werden muss, wird die Kapazität über mem_root->block_num >>2 * block_size erweitert, sodass mem_root->block_num >>2 mindestens 1 ist, also während des Initialisierungsprozesses mem_root->block_num =4 (Anmerkung: 4>>2=1).

Werfen wir einen Blick auf die spezifischen Schritte zum Zuweisen von Speicher:

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;
    }
}

Die spezifische Logik des obigen Codes lautet wie folgt:

1. Sehen Sie sich die kostenlose verknüpfte Liste an und suchen Sie nach einem Block, der dem Bereich entspricht. Wenn ein passender Block gefunden wird, dann:
1.1 Geben Sie einfach die Anfangsadresse des Blocks von size-left zurück. Natürlich wird beim Durchlaufen der freien Liste beurteilt, dass der verbleibende Platz im ersten Block in der freien Liste
nicht dem Platz entspricht, der zugewiesen werden muss, und der Block wurde 10 Mal durchsucht
(ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP) Wenn die Zuordnungslänge nicht erfüllt ist und der verbleibende Platz des Blocks weniger als
4k (ALLOC_MAX_BLOCK_TO_DROP) beträgt, wird der Block in die verwendete verknüpfte Liste verschoben.

2. Wenn es keinen passenden Block in der freien verknüpften Liste gibt, dann:
2.1 Weisen Sie mem_root->block_size * (mem_root->block_num >> 2) und die Länge ALIGN_SIZE(sizeof(USED_MEM)) zu.
Der größere wird als neuer Blockspeicherplatz verwendet.
2.2 Abhängig von der Verwendung des Blocks hängen Sie den Block an die verwendete oder freie verknüpfte Liste.

Was hier beachtet werden muss, ist die Verwendung von sekundären Zeigern:

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

prev zeigt auf die Adresse, auf die next des letzten Blocks zeigt:

Ersetzen Sie also die Adresse von prev durch die Adresse des neuen Blocks, das heißt, fügen Sie den neuen Block am Ende der freien Liste hinzu: *prev=next;

Zusammenfassung:

MEM_ROOT verwendet einen heuristischen Zuweisungsalgorithmus für die Speicherzuweisung. Mit zunehmender Anzahl nachfolgender Blöcke wird der Speicher eines einzelnen Blocks größer: block_size= mem_root->block_size * (mem_root ->block_num > > 2) .