9—innodb动态数组的实现

最后更新于:2022-04-01 16:04:55

在上一篇,bingxi和alex聊了关于list的内容。在本篇里,bingxi和alex会聊到innodb的动态数组,也称为dyn。 对应的文件为: D:/mysql-5.1.7-beta/storage/innobase/include/dyn0dyn.h D:/mysql-5.1.7-beta/storage/innobase/include/dyn0dyn.ic D:/mysql-5.1.7-beta/storage/innobase/dyn/dyn0dyn.c ## 1)常用结构体 Alex:“bingxi,我们前两篇聊了常用结构hash、list,这两个结构很常见。我们快要开始聊文件空间存储了,在那里面有一个常用结构,我们看一下fsp0fsp.c中函数,比如fsp_get_space_header函数,调用参数里面有mtr_t。 ~~~ /************************************************************************** Gets a pointer to the space header and x-locks its page. */ UNIV_INLINE fsp_header_t* fsp_get_space_header( /*=================*/                      /* out: pointer to the space header, page x-locked */        ulintid,   /* in: space id */        mtr_t*     mtr)/* in: mtr */ ~~~ 我们接着看一下mtr_struct的定义,在结构体的定义前一行,我们可以看到Mini-transaction,称为mini事务。用于锁信息、mtr日志信息。 ~~~ /* Mini-transaction handle and buffer */ struct mtr_struct{        ulint        state;       /* MTR_ACTIVE, MTR_COMMITTING, MTR_COMMITTED */        dyn_array_t    memo;    /* memo stack for locks etc. */        dyn_array_t    log;  /* mini-transaction log */        ibool              modifications;                             /* TRUE if the mtr made modifications to                             buffer pool pages */        ulint        n_log_recs;                             /* count of how many page initial log records                             have been written to the mtr log */        ulint        log_mode; /* specifies which operations should be                             logged; default value MTR_LOG_ALL */        dulint             start_lsn;/* start lsn of the possible log entry for                             this mtr */        dulint             end_lsn;/* end lsn of the possible log entry for                             this mtr */        ulint        magic_n; }; ~~~ 我们将要开始fsp0fsp.c的内容,为了便于内容的独立,会将mtr的内容先剥离,在讲完存储之后,会继续讲B树,然后会到事务。 ” Bingxi:“alex,我赞同这一点。不过我认为还是把该结构体中的一个常用算法讲下,就是动态数组,mtr_t结构体中会有两个这样的结构成员: dyn_array_t    memo;    /* memo stack for locks etc. */ dyn_array_t    log;  /* mini-transaction log */ 所谓动态数组,就是一个动态的虚拟线性数组,数组的基本元素是byte,主要用于存放mtr的锁信息以及log。如果对于一个block数组不够存放时,需要增加新的block,每个block对应的存放数据字段的长度是固定的(默认值是512),但是不一定会用完。假设已经用了500个字节,这时候需要继续存放18个字节的内容,就会在该块中存放不了,会产生一个新的block用于存放。从而前一个block使用值为500。 我们先看了结构体的定义: ~~~ typedef struct dyn_block_struct            dyn_block_t; typedef dyn_block_t                    dyn_array_t; …… /*#################################################################*/ /* NOTE! Do not use the fields of the struct directly: the definition appears here only for the compiler to know its size! */ struct dyn_block_struct{        mem_heap_t*heap;       /* in the first block this is != NULL                             if dynamic allocation has been needed */        ulint        used;       /* number of data bytes used in this block */        byte        data[DYN_ARRAY_DATA_SIZE];                             /* storage for array elements */            UT_LIST_BASE_NODE_T(dyn_block_t) base;                             /* linear list of dyn blocks: this node is                             used only in the first block */        UT_LIST_NODE_T(dyn_block_t) list;                             /* linear list node: used in all blocks */ #ifdef UNIV_DEBUG        ulint        buf_end;/* only in the debug version: if dyn array is                             opened, this is the buffer end offset, else                             this is 0 */        ulint        magic_n; #endif }; ~~~ 在这个结构体中,我们可以看到上一篇聊到的list结构,可以通过list查找prev、next。 Alex,这里面就带来了一些问题:1) dyn_array_t与dyn_block_t是同样的定义,而一个动态数组只有一个首结点,那么UT_LIST_BASE_NODE_T(dyn_block_t) base成员是不是每个结构体都是有效的,2)一开始分配的时候只分配了一个结构体,也就是512字节的大小,如果不够用,则扩展了一个,插入到链表里面,链表成员是1个还是2个?3)使用的时候,如何判断一个block已经使用满了,比如前面我们说到一个情况:500个字节剩下了12个不够18个时候,产生了一个新的block,假设这时候要使用其中的10个字节,两个block都是符合,用哪个?如果用后一个,怎么标识前一个是满的。 ” Alex:“你的问题太多了,呵呵。我们先放下问题,看一下动态数组的初始化过程。这里面,我们还需要主意一点。虽然数据结构用的是同一个dyn_block_struct,但是我们称第一个节点为arr,表明这个是动态数据的头节点。其它的节点,我们称为block节点。 现在开始进行debug,在mtr0mtr.ic文件中的mtr_start函数体内设置断点,这里也是动态数组创建的唯一入口,设置断点进行调试。 ~~~ /******************************************************************* Starts a mini-transaction and creates a mini-transaction handle and a buffer in the memory buffer given by the caller. */ UNIV_INLINE mtr_t* mtr_start( /*======*/                      /* out: mtr buffer which also acts as                      the mtr handle */        mtr_t*     mtr)/* in: memory buffer for the mtr buffer */ {     //会创建两个动态数组,在两个创建的任一个设置断点        dyn_array_create(&(mtr->memo));        dyn_array_create(&(mtr->log));          mtr->log_mode = MTR_LOG_ALL;        mtr->modifications = FALSE;        mtr->n_log_recs = 0; #ifdef UNIV_DEBUG        mtr->state = MTR_ACTIVE;        mtr->magic_n = MTR_MAGIC_N; #endif        return(mtr); }            ~~~ 点击F11进入函数,查看动态数据的创建过程: ~~~ /************************************************************************* Initializes a dynamic array. */ UNIV_INLINE dyn_array_t* dyn_array_create( /*=============*/                             /* out: initialized dyn array */        dyn_array_t*  arr)  /* in: pointer to a memory buffer of                             size sizeof(dyn_array_t) */ {        ut_ad(arr);        ut_ad(DYN_ARRAY_DATA_SIZE < DYN_BLOCK_FULL_FLAG);        arr->heap = NULL;        arr->used = 0; #ifdef UNIV_DEBUG        arr->buf_end = 0;        arr->magic_n = DYN_BLOCK_MAGIC_N; #endif        return(arr); } ~~~ 执行该函数之后,结构体的情况见图1: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-07-22_5791c9c14d83d.gif) 创建完成之后,我们就可以使用该动态数组了。作为例子,我们在mtr_memo_push函数体内设置断点。 ~~~ /******************************************************* Pushes an object to an mtr memo stack. */ UNIV_INLINE void mtr_memo_push( /*==========*/        mtr_t*     mtr,/* in: mtr */        void*      object,     /* in: object */        ulinttype)       /* in: object type: MTR_MEMO_S_LOCK, ... */ {        dyn_array_t*         memo;        mtr_memo_slot_t*slot;        ut_ad(object);        ut_ad(type >= MTR_MEMO_PAGE_S_FIX);            ut_ad(type <= MTR_MEMO_X_LOCK);        ut_ad(mtr);        ut_ad(mtr->magic_n == MTR_MAGIC_N);        memo = &(mtr->memo);      //从动态中分配大小为sizeof(mtr_memo_slot_t)的空间 //然后对获取的空间进行赋值        slot = dyn_array_push(memo, sizeof(mtr_memo_slot_t));        slot->object = object;        slot->type = type; } ~~~ 从中我们可以得知dyn_array_pus是分配空间的地方(dyn_array_open函数有这样的功能,本文后面会提到),我们按F11进入该函数体。 ~~~ /************************************************************************* Makes room on top of a dyn array and returns a pointer to the added element. The caller must copy the element to the pointer returned. */ UNIV_INLINE void* dyn_array_push( /*===========*/                             /* out: pointer to the element */        dyn_array_t*  arr,  /* in: dynamic array */        ulint        size)/* in: size in bytes of the element */ {        dyn_block_t*  block;        ulint        used;          ut_ad(arr);        ut_ad(arr->magic_n == DYN_BLOCK_MAGIC_N);        ut_ad(size <= DYN_ARRAY_DATA_SIZE);        ut_ad(size); //步骤1:取得使用的used //存在多个节点是,arr表示的是链表中的首节点        block = arr;        used = block->used; //步骤2:如果首结点block有足够的空间存储,则返回指针,并修改used值。这种情况只出现在:该动态数组只有一个节点。 // used + size <= DYN_ARRAY_DATA_SIZE表示有足够的空间存储        if (used + size > DYN_ARRAY_DATA_SIZE) {               /* Get the last array block */         //步骤3:首结点没有空间存储,则取得base列表的最后一个结点         //该函数等价于:block =UT_LIST_GET_LAST(arr->base);         //如果有多个节点,首先肯定不符合used + size <= DYN_ARRAY_DATA_SIZE,在后文中有描述。               block = dyn_array_get_last_block(arr);               used = block->used;         //步骤4:如果最后一个结点有足够空间,则分配         //否则增加一个新的block               if (used + size > DYN_ARRAY_DATA_SIZE) {                      block = dyn_array_add_block(arr);                      used = block->used;               }        }        block->used = used + size;        ut_ad(block->used <= DYN_ARRAY_DATA_SIZE);        return((block->data) + used); } ~~~ 该函数的功能就是进行分配空间,如果有足够的空间则分配,否则就调用函数dyn_array_add_block生成一个新的block。假象现在的情形是一个block扩展为两个block的情况。查看该函数的实现。 ~~~ /**************************************************************** Adds a new block to a dyn array. */ dyn_block_t* dyn_array_add_block( /*================*/                             /* out: created block */        dyn_array_t*  arr)  /* in: dyn array */ {        mem_heap_t*heap;        dyn_block_t*  block;        ut_ad(arr);        ut_ad(arr->magic_n == DYN_BLOCK_MAGIC_N); //步骤1:结点是1扩展为2,还是n扩展为n+1(n>=2) // arr->heap=NULL则是1扩展为2,将自己作为首结点放在链表上,并分配一个内存堆        if (arr->heap == NULL) {               UT_LIST_INIT(arr->base);               UT_LIST_ADD_FIRST(list, arr->base, arr);         //1扩展为2的时候,创建一个heap,n扩展n+1(n>=2)时,则使用该heap               arr->heap = mem_heap_create(sizeof(dyn_block_t));        }     //步骤2:取得最后一个结点,将该block的used字段进行DYN_BLOCK_FULL_FLAG与操作,表示该结点已经使用满。每增加一个新的block总要将前一个block设置为已满,因此只有最后一个block是可用的。即使如前文所例,500字节不够用时创建了一个新的block,第二次有申请10个字节时,显示显示该块的大小>512了,因为DYN_BLOCK_FULL_FLAG的值为:0x1000000UL        block = dyn_array_get_last_block(arr);        block->used = block->used | DYN_BLOCK_FULL_FLAG;        heap = arr->heap;     //步骤3:创建一个新结点,并插入到链表尾        block = mem_heap_alloc(heap, sizeof(dyn_block_t));        block->used = 0;        UT_LIST_ADD_LAST(list, arr->base, block);        return(block); } ~~~ 1个结点扩展为2个结点后,见图2(prev和next指向结构的首字节,便于绘图进行了简化,此处加以说明。list的prev和next参考前一篇文章): ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-07-22_5791c9c1678eb.gif) 2个结点扩展为3个结点,见图3: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-07-22_5791c9c18435c.gif) 到这里,我们就解决了前面的三个问题。问题1:dyn_array_t与dyn_block_t是同样的定义,而一个动态数组只有一个首结点,那么UT_LIST_BASE_NODE_T(dyn_block_t) base成员是不是每个结构体都是有效的? ” Alex:“这个问题我明白,只有首结点的base是有效的。从图1中可以看出,只有一个结点时,base是无效。图2中,arr的base有两个成员,首结点是第一个成员,新增加的结点在首结点的后面。图3中,arr的base有三个成员,新增的成员在链表尾。” Bingxi:“问题2:一开始分配的时候只分配了一个结构体,也就是512字节的大小,如果不够用,则扩展了一个,插入到链表里面,链表成员是1个还是2个?” Alex:“从1个扩展到2个,链表的成员是2。” Bingxi:“问题3:使用的时候,如何判断一个block已经使用满了,比如前面我们说到一个情况:500个字节剩下了12个不够18个时候,产生了一个新的block,假设这时候要使用其中的10个字节,两个block都是符合,用哪个?如果用后一个,怎么标识前一个是满的。” Alex:“始终只有最后一个结点可能被使用,只有一个成员时,本身就是最后一个结点。新增结点时,会将前一个结点设置为已满。设置方法如下: block->used = block->used | DYN_BLOCK_FULL_FLAG; 这样进行分配操作时候,used + size > DYN_ARRAY_DATA_SIZE这个条件一定为真。表示首结点已经用满了,然后取最后一个结点。该条件只有一种情况为否,就是动态数组只有一个成员。 ~~~ if (used + size > DYN_ARRAY_DATA_SIZE) {               /* Get the last array block */                             block = dyn_array_get_last_block(arr);               used = block->used;                 if (used + size > DYN_ARRAY_DATA_SIZE) {                      block = dyn_array_add_block(arr);                      used = block->used;               }        } ~~~ ” Bingxi:“good,我现在问第4个问题:我们需要插入三个元素,我们插入一个元素,就需要修改一次used,再插入,又得调用push函数进行操作。频繁的对dyn的数据结构进行操作。这样的效率是很低的。” Alex:“稍等,我看下代码。找到了,通过dyn_array_open、dyn_array_close函数可以解决这个问题。这两个函数建议大家看下。另外,我也问你第5个问题,是不是大于512字节的数据就不能插入?” Bingxi:“这个问题,请参考函数dyn_push_string。其它的函数也看一下,养成看函数的习惯,呵呵。今天就到这儿吧。” Alex:“ok”
';