mysql MEM_ROOT内存管理

关于小对象动态内存分配的问题有许多研究，也有许多实现库。 不过，为了平台的兼容性，mysql做了自己的实现，具体就如mysql university上说的：

MEM_ROOT block allocator

Allocates memory in blocks of 4K (or other parameterizable size).

• helps deal with the problem of memory framentation
• always thread local, unlike system heap
• does not have overhead of metadata per each allocation unit
• subject to internal fragmentation
• CHEAP and should be used instead of system heap whenever possible
• if out of memory calls error_handler_hook which sets an error in THD

Life time properties of allocation:

• two-phase allocation -- you can allocate many times, but can only free all at once
• if you control MEM_ROOT, you define when freeing happens.
• you can retain some part of memory when freeing to improve performance
• in most cases you use MEM_ROOTs controlled by system runtime and freed at pre-defined locations.

In this case you must know that you won't need the memory after it's freed when you use these memory roots.

在mysql的源码中，其算法实现主要集中在函数void *alloc_root(MEM_ROOT *mem_root, size_t length)上。这个函数的作用是实际的动态内存分配：首先在预分配的未使用的内存空间上找符合要求的位置，然后做标记，返回可用内存位置的第一个字节的指针。主要难点在深度为2的指针操作上。如果对c或者是c++指针链表操作比较熟悉的话，了解其机理不在话下。这里摘抄部分做分析

  size_t get_size, block_size;

  uchar* point;

  reg1 USED_MEM *next= 0;

  reg2 USED_MEM **prev;

  一些必要的调试

  DBUG_ENTER("alloc_root");

  DBUG_PRINT("enter",("root: 0x%lx", (long) mem_root));

  DBUG_ASSERT(alloc_root_inited(mem_root));

  DBUG_EXECUTE_IF("simulate_out_of_memory",

                  {

                    /* Avoid reusing an already allocated block */

                    if (mem_root->error_handler)

                      (*mem_root->error_handler)();

                    DBUG_SET("-d,simulate_out_of_memory");

                    DBUG_RETURN((void*) 0); /* purecov: inspected */

                  });

  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= 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));

    *prev=next;

  }

  point= (uchar*) ((char*) next+ (next->size-next->left));

  /*TODO: next part may be unneded due to mem_root->first_block_usage counter*/

标记内存的使用

  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;

  }

  DBUG_PRINT("exit",("ptr: 0x%lx", (ulong) point));

  DBUG_RETURN((void*) point);