现在的位置: 首页 > 综合 > 正文

思考mysql内核之初级系列9—innodb动态数组的实现

2014年01月28日 ⁄ 综合 ⁄ 共 6939字 ⁄ 字号 评论关闭

在上一篇,bingxialex聊了关于list的内容。在本篇里,bingxialex会聊到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,我们前两篇聊了常用结构hashlist,这两个结构很常见。我们快要开始聊文件空间存储了,在那里面有一个常用结构,我们看一下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 */

       ulint id,   /* 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查找prevnext

  Alex,这里面就带来了一些问题:1) dyn_array_tdyn_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

 

  创建完成之后,我们就可以使用该动态数组了。作为例子,我们在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 */

       ulint type)       /* 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;

抱歉!评论已关闭.