数据库内核月报 － 2019 / 10

dberr_t dict_build_tablespace(trx_t *trx, Tablespace *tablespace) {
  ...
  err = fil_ibd_create(space, tablespace->name(), datafile->filepath(),
                       tablespace->flags(), FIL_IBD_FILE_INITIAL_SIZE);
  ...
  // 初始化fsp header的其他字段
  bool ret = fsp_header_init(space, FIL_IBD_FILE_INITIAL_SIZE, &mtr, false);
  ...
}

static dberr_t fil_create_tablespace(space_id_t space_id, const char *name,
                                     const char *path, ulint flags,
                                     page_no_t size, fil_type_t type)
{
	...
    // 创建ibd文件
	file = os_file_create(
      	type == FIL_TYPE_TEMPORARY ? innodb_temp_file_key : innodb_data_file_key,
      	path, OS_FILE_CREATE | OS_FILE_ON_ERROR_NO_EXIT, OS_FILE_NORMAL,
      	OS_DATA_FILE, srv_read_only_mode && (type != FIL_TYPE_TEMPORARY),
      	&success);
    ...
    // 这里会将新创建的ibd文件填0以预分配空间
    // 调试显示size=7，即分配的空间为7*16KB，但os_file_set_size内会将其向上调整至8*16KB
    // buf2 = static_cast<byte *>(ut_malloc_nokey(buf_size + UNIV_PAGE_SIZE));
    success = os_file_set_size(path, file, 0, size * page_size.physical(),
                             srv_read_only_mode, true);
	...
    // 初始化fsp header pages，其中前3个page作用比较关键：
    // page 0: root page，也是fsp header page
    // page 1: ibuf_bitmap page，作用暂时不明
    // page 2: inode page，管理segment分配，每个inode entry对应一个segment
    buf2 = static_cast<byte *>(ut_malloc_nokey(3 * page_size.logical()));

  	page = static_cast<byte *>(ut_align(buf2, page_size.logical()));
  	memset(page, '\0', page_size.logical());
	
  	flags = fsp_flags_set_page_size(flags, page_size);
  	fsp_header_init_fields(page, space_id, flags);
  	mach_write_to_4(page + FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID, space_id);

  	mach_write_to_4(page + FIL_PAGE_SRV_VERSION, DD_SPACE_CURRENT_SRV_VERSION);
  	mach_write_to_4(page + FIL_PAGE_SPACE_VERSION, DD_SPACE_CURRENT_SPACE_VERSION);
	...
}

buf_block_t *fseg_create_general(
    space_id_t space_id, 
    page_no_t page,  // 调用者多传入0,表示需要分配一个新page作为segment header
    ulint byte_offset,   
    ibool has_done_reservation, 
    mtr_t *mtr)                 
{

  fil_space_t *space = fil_space_get(space_id);

  mtr_x_lock_space(space, mtr);
  const page_size_t page_size(space->flags);
  ...

  space_header = fsp_get_space_header(space_id, page_size, mtr);

  // 分配inode entry，代表该segment
  inode = fsp_alloc_seg_inode(space_header, mtr);

  // 从table space的page header中读取下一个要使用的segment id
  // 将其设置在inode entry的FSEG_ID字段中
  // 同时将刚刚已分配的segment id递增1并写回space的page header的FSP_SEG_ID字段
  seg_id = mach_read_from_8(space_header + FSP_SEG_ID);
  mlog_write_ull(space_header + FSP_SEG_ID, seg_id + 1, mtr);
  mlog_write_ull(inode + FSEG_ID, seg_id, mtr);
  mlog_write_ulint(inode + FSEG_NOT_FULL_N_USED, 0, MLOG_4BYTES, mtr);

  // 初始化inode中的各种extent链表
  flst_init(inode + FSEG_FREE, mtr);
  flst_init(inode + FSEG_NOT_FULL, mtr);
  flst_init(inode + FSEG_FULL, mtr);

  // 初始化segment的frag page数组为空(未分配任何page)
  mlog_write_ulint(inode + FSEG_MAGIC_N, FSEG_MAGIC_N_VALUE, MLOG_4BYTES, mtr);
  for (i = 0; i < FSEG_FRAG_ARR_N_SLOTS; i++) {
    fseg_set_nth_frag_page_no(inode, i, FIL_NULL, mtr);
  }

  // 且该page的类型是FIL_PAGE_TYPE_SYS
  // 该page是Change Buffer的header page，主要用于对ibuf btree的Page管理。
  if (page == 0) {
    block = fseg_alloc_free_page_low(space, page_size, inode, 0, FSP_UP,
                                     RW_SX_LATCH, mtr, mtr);

    header = byte_offset + buf_block_get_frame(block);
    mlog_write_ulint(buf_block_get_frame(block) + FIL_PAGE_TYPE,
                     FIL_PAGE_TYPE_SYS, MLOG_2BYTES, mtr);
  }

  // 初始化page header
  mlog_write_ulint(header + FSEG_HDR_OFFSET, page_offset(inode), MLOG_2BYTES,
                   mtr);
  mlog_write_ulint(header + FSEG_HDR_PAGE_NO,
                   page_get_page_no(page_align(inode)), MLOG_4BYTES, mtr);
  mlog_write_ulint(header + FSEG_HDR_SPACE, space_id, MLOG_4BYTES, mtr);
  ...
}

static fseg_inode_t *fsp_alloc_seg_inode(
    fsp_header_t *space_header,
    mtr_t *mtr)
{
  ...
  // 如果FSP_SEG_INODES_FREE链表为空
  // 该链表用于链接那些尚有inode空间可分配的inode_page
  // 如果该链表为空,那就要分配一个新的inode page了,这个过程我们在下面描述
  // 调用fsp_alloc_seg_inode_page创建一个新的inode page
  if (flst_get_len(space_header + FSP_SEG_INODES_FREE) == 0 &&
      !fsp_alloc_seg_inode_page(space_header, mtr)) {
    return (NULL);
  }
  
  ...
  // 从inode page中分配一个空闲inode
  const page_size_t page_size(mach_read_from_4(FSP_SPACE_FLAGS + space_header));
  const page_id_t page_id(
      page_get_space_id(page_align(space_header)),
      flst_get_first(space_header + FSP_SEG_INODES_FREE, mtr).page);

  block = buf_page_get(page_id, page_size, RW_SX_LATCH, mtr);
  page = buf_block_get_frame(block);

  // 遍历该inode page的所有inode entry
  // 如果发现某个Inode Entry的FSEG_ID字段未设置
  // 即认为该inode entry尚未分配
  n = fsp_seg_inode_page_find_free(page, 0, page_size, mtr);
  inode = fsp_seg_inode_page_get_nth_inode(page, n, page_size, mtr);

  // 如果由于本次分配导致该inode page内不再有可用的inode空间
  // 那需要将该inode page从space的FSP_SEG_INODES_FREE链表摘除并加入FSP_SEG_INODES_FULL链表尾部
  if (FIL_NULL == fsp_seg_inode_page_find_free(page, n + 1, page_size, mtr)) {
    flst_remove(space_header + FSP_SEG_INODES_FREE, page + FSEG_INODE_PAGE_NODE,
                mtr);
    flst_add_last(space_header + FSP_SEG_INODES_FULL,
                  page + FSEG_INODE_PAGE_NODE, mtr);
  }
  return (inode);
}

// 从space中分配一个未使用的inode page
static ibool fsp_alloc_seg_inode_page(
    fsp_header_t *space_header,
    mtr_t *mtr)
{
  space = page_get_space_id(page_align(space_header));
  const page_size_t page_size(mach_read_from_4(FSP_SPACE_FLAGS + space_header));

  // fsp_alloc_free_page这个函数比较有意思,值得仔细研究一番
  // 分配一个空闲page作为inode page
  block = fsp_alloc_free_page(space, page_size, 0, RW_SX_LATCH, mtr, mtr);
  page = buf_block_get_frame(block);
  // 设置新分配的PAGE类型为FIL_PAGE_INODE
  mlog_write_ulint(page + FIL_PAGE_TYPE, FIL_PAGE_INODE, MLOG_2BYTES, mtr);

  // 初始化inode page中的所有inode信息为空闲
  for (page_no_t i = 0; i < FSP_SEG_INODES_PER_PAGE(page_size); i++) {
    inode = fsp_seg_inode_page_get_nth_inode(page, i, page_size, mtr);
    mlog_write_ull(inode + FSEG_ID, 0, mtr);
  }
  // 将新分配的inode page加入至FSP_SEG_INODES_FREE链表的尾部
  flst_add_last(space_header + FSP_SEG_INODES_FREE, page + FSEG_INODE_PAGE_NODE, mtr);
  return (TRUE);
}

// 参数@hint给出一个线索:可以尝试先使用该page所在的extent,如果其状态为free的话
// hint表明调用者建议从该page开始分配空间以获得更好的连续性
// 该函数会优先分配该hint page所在的extent,如果其尚未被分配的话
static xdes_t *fsp_alloc_free_extent(space_id_t space_id,
                                     const page_size_t &page_size,
                                     page_no_t hint, mtr_t *mtr) {
  fsp_header_t *header;
  fil_addr_t first;
  xdes_t *descr;
  buf_block_t *desc_block = NULL;

  header = fsp_get_space_header(space_id, page_size, mtr);

  // 计算hint page所在的extent的xdes对象位置
  // 这个函数会在下面仔细分析
  descr = xdes_get_descriptor_with_space_hdr(header, space_id, hint, mtr, false,
                                             &desc_block);
  fil_space_t *space = fil_space_get(space_id);

  // 该xdes状态是FREE，表明该extent未分配给其他人使用
  if (descr && (xdes_get_state(descr, mtr) == XDES_FREE)) {
      /* Ok, we can take this extent */
  } else {
    // 需要从table space header上的FSP_FREE链表中获取一个可分配的extent
    first = flst_get_first(header + FSP_FREE, mtr);
    if (fil_addr_is_null(first)) {
      // 如果FSP_FREE链表为空,那么只能分配一个新的xdes了，其磁盘位置记录在first中(page, boff)
      fsp_fill_free_list(false, space, header, mtr);
      first = flst_get_first(header + FSP_FREE, mtr);
    }
    
    descr = xdes_lst_get_descriptor(space_id, page_size, first, mtr);
  }
  flst_remove(header + FSP_FREE, descr + XDES_FLST_NODE, mtr);
  space->free_len--;
  return (descr);
}

static void fsp_fill_free_list(bool init_space, fil_space_t *space,
                               fsp_header_t *header, mtr_t *mtr) {
  page_no_t limit;
  page_no_t size;
  ulint flags;
  xdes_t *descr;
  ulint count = 0;
  page_no_t i;

  // size代表table space当前的大小(可以理解为ibd文件的大小)
  size = mach_read_from_4(header + FSP_SIZE);
  // limit: 暂时还不理解
  limit = mach_read_from_4(header + FSP_FREE_LIMIT);
  flags = mach_read_from_4(header + FSP_SPACE_FLAGS);

  const page_size_t page_size(flags);

  // 需要扩张ibd文件,调用fsp_try_extend_data_file
  // 扩张ibd文件逻辑在下面仔细研究
  if (size < limit + FSP_EXTENT_SIZE * FSP_FREE_ADD) {
    if ((!init_space && !fsp_is_system_tablespace(space->id) &&
         !fsp_is_global_temporary(space->id)) ||
        (space->id == TRX_SYS_SPACE &&
         srv_sys_space.can_auto_extend_last_file()) ||
        (fsp_is_global_temporary(space->id) &&
         srv_tmp_space.can_auto_extend_last_file())) {
      fsp_try_extend_data_file(space, header, mtr);
      size = space->size_in_header;
    }
  }

  // 文件成功扩张后,开始分配extent
  // limit到底是什么意思呢？
  i = limit;

  // 结束条件:
  // 1. 分配的extent未超过当前表空间物理文件大小(size)
  // 2. 分配的extent数量超过了FSP_FREE_ADD(4):这是因为程序中限制了每次填充extent的最大个数
  while ((init_space && i < 1) ||
         ((i + FSP_EXTENT_SIZE <= size) && (count < FSP_FREE_ADD))) {
    // 什么时候init_xdes为true呢? 还没思考明白
    // #define ut_2pow_remainder(n, m) ((n) & ((m)-1))
    bool init_xdes = (ut_2pow_remainder(i, page_size.physical()) == 0);

    space->free_limit = i + FSP_EXTENT_SIZE;
    mlog_write_ulint(header + FSP_FREE_LIMIT, i + FSP_EXTENT_SIZE, MLOG_4BYTES, mtr);

    // 需要初始化xdes page
    if (init_xdes) {
      ...
    }

    buf_block_t *desc_block = NULL;
    // 根据上面分配的extent计算其对应的xdes所在的xdes page以及在page内的偏移
    descr = xdes_get_descriptor_with_space_hdr(header, space->id, i, mtr,
                                               init_space, &desc_block);
    xdes_init(descr, mtr);

    if (init_xdes) {
      fsp_init_xdes_free_frag(header, descr, mtr);
    } else {
      // 将刚创建的extent加入至fsp header的FSP_FREE链表尾部
      flst_add_last(header + FSP_FREE, descr + XDES_FLST_NODE, mtr);
      count++;
    }

    i += FSP_EXTENT_SIZE;
  }
  space->free_len += (uint32_t)count;
}

static UNIV_COLD ulint fsp_try_extend_data_file(fil_space_t *space,
                                                fsp_header_t *header,
                                                mtr_t *mtr)
{
  page_no_t size;
  page_no_t size_increase;

  size = mach_read_from_4(header + FSP_SIZE);

  const page_size_t page_size(mach_read_from_4(header + FSP_SPACE_FLAGS));

  if (space->id == TRX_SYS_SPACE) {
      ...
  } else if (fsp_is_global_temporary(space->id)) {
	  ...
  } else {
    // 首先判断如果当前ibd文件大小小于extent_size(典型是1MB)
    // 首先将其extent至extent_size(典型是1MB)
    page_no_t extent_pages = fsp_get_extent_size_in_pages(page_size);
    if (size < extent_pages) {
      /* Let us first extend the file to extent_size */
      if (!fsp_try_extend_data_file_with_pages(space, extent_pages - 1, header,
                                               mtr)) {
      }
      size = extent_pages;
    }
    // 接下来判断每次extent的幅度,其算法是:
    // 1. 如果当前ibd大小小于32个extent_size,每次extent单位为extent_size
    // 2. 否则,每次extent单位为FSP_FREE_ADD(4) * extent_size;
    size_increase = fsp_get_pages_to_extend_ibd(page_size, size);
  }

  if (!fil_space_extend(space, size + size_increase)) {
    DBUG_RETURN(false);
  }

  // 修改fsp header中的大小
  space->size_in_header =
      ut_calc_align_down(space->size, (1024 * 1024) / page_size.physical());

  fsp_header_size_update(header, space->size_in_header, mtr);
}

// offset为extent的起始page no
UNIV_INLINE MY_ATTRIBUTE((warn_unused_result)) xdes_t
    *xdes_get_descriptor_with_space_hdr(fsp_header_t *sp_header,
                                        space_id_t space, page_no_t offset,
                                        mtr_t *mtr, bool init_space = false,
                                        buf_block_t **desc_block = NULL) {
  ulint limit;
  ulint size;
  page_no_t descr_page_no;
  ulint flags;
  page_t *descr_page;

  const page_size_t page_size(flags);

  descr_page_no = xdes_calc_descriptor_page(page_size, offset);

  buf_block_t *block;

  if (descr_page_no == 0) {
    /* It is on the space header page */
    descr_page = page_align(sp_header);
    block = NULL;
  } else {
    block = buf_page_get(page_id_t(space, descr_page_no), page_size,
                         RW_SX_LATCH, mtr);
    descr_page = buf_block_get_frame(block);
  }

  if (desc_block != NULL) {
    *desc_block = block;
  }

  return (descr_page + XDES_ARR_OFFSET +
          XDES_SIZE * xdes_calc_descriptor_index(page_size, offset));
}

static buf_block_t *fseg_alloc_free_page_low(fil_space_t *space,
                                             const page_size_t &page_size,
                                             fseg_inode_t *seg_inode,
                                             page_no_t hint, byte direction,
                                             rw_lock_type_t rw_latch,
                                             mtr_t *mtr, mtr_t *init_mtr
)
{
	...
}

typedef struct fil_addr_struct
{
  ulint page;    /*page在space中的编号*/
  ulint boffset; /*page中的字节偏移量，在内存中使用2字节表示*/
} fil_addr_t;

typedef byte flst_node_t;
typedef byte flst_base_node_t;
/* The physical size of a list base node in bytes */
constexpr ulint FLST_BASE_NODE_SIZE = 4 + 2 * FIL_ADDR_SIZE;
/* The physical size of a list node in bytes */
constexpr ulint FLST_NODE_SIZE = 2 * FIL_ADDR_SIZE;

bool fsp_header_init(space_id_t space_id, page_no_t size, mtr_t *mtr,
                     bool is_boot) 
{
  flst_init(header + FSP_FREE, mtr);
  flst_init(header + FSP_FREE_FRAG, mtr);
  flst_init(header + FSP_FULL_FRAG, mtr);
  flst_init(header + FSP_SEG_INODES_FULL, mtr);
  flst_init(header + FSP_SEG_INODES_FREE, mtr);
}

UNIV_INLINE
void flst_init(flst_base_node_t *base, mtr_t *mtr)          
{
  mlog_write_ulint(base + FLST_LEN, 0, MLOG_4BYTES, mtr);
  flst_write_addr(base + FLST_FIRST, fil_addr_null, mtr);
  flst_write_addr(base + FLST_LAST, fil_addr_null, mtr);
}

buf_block_t *fseg_create_general(
    space_id_t space_id, 
    page_no_t page,
    ulint byte_offset,
    ibool has_done_reservation,
    mtr_t *mtr)
{
  ...
  flst_init(inode + FSEG_FREE, mtr);
  flst_init(inode + FSEG_NOT_FULL, mtr);
  flst_init(inode + FSEG_FULL, mtr);
  ...
}

// 以m为16384为例，如果n < 16384，计算的结果是0
// 如果16384 =< n < 32768,计算的结果是16384
// 如果32768 =< n < 49152,计算的结果是32768
// 以此类推
#define ut_2pow_round(n, m) ((n) & ~((m)-1))

UNIV_INLINE
page_no_t xdes_calc_descriptor_page(const page_size_t &page_size,
                                    page_no_t offset) 
{
      return (ut_2pow_round(offset, page_size.physical()));
}