LoopJump's Blog

InnoDB源码解析-基础数据结构

2022-06-04

互斥锁 ib_mutex_t

typedef FutexMutex ib_mutex_t;

UT_MUTEX_TYPE(TTASFutexMutex, GenericPolicy, FutexMutex); 这个宏定义展开是 typedef PolicyMutex<TTASFutexMutex> FutexMutex;

PolicyMutex是个mutex框架，具体实现依赖模板参数MutexImpl。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename MutexImpl>
struct PolicyMutex
{
  typedef MutexImpl MutexType;
  typedef typename MutexImpl::MutexPolicy Policy;
  MutexImpl m_impl;

  // 申请互斥锁
  void enter(uint32_t n_spins, uint32_t n_delay, const char *name, uint32_t line)
  |-- policy().enter(m_impl, name, line);
  |-- m_impl.entry(n_spins, n_delay, name, line);
  |-- policy().locked(m_impl, name, line);

  void exit()
 |-- policy().release(m_impl);
 |-- m_impl.exit();
};

TTASFutexMutex 有一个字段代表锁状态，用CAS指令实现spinlock，如果spin次数超过阈值，使用SYS_futex。

typedef int lock_word_t; lock_word_t TTASFutexMutex::m_lock_word;

双向链表 ut_list

源码位置：include/ut0lst.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// list node 类型
// 这里Type是业务类型，比如 buf_page_t。
template<typename Type>
struct ut_list_node
{
  Type *prev;
  Type *next;
};

// list 类型
template<typename Type, typename NodePtr>
struct ut_list_base
{
  typedef Type elem_type;
  typedef NodePtr node_ptr;

  ulint count;
  elem_type *start;
  elem_type *end;
  // 内嵌到业务数据结构（如buf_page_t）里面的node对象（buf_page_t::list字段）的对象内偏移量。
  node_ptr node;
};

用于声明一个列表的宏 #define UT_LIST_BASE_NODE_T(t) ut_list_base<t, ut_list_node t::*>

比如 UT_LIST_BASE_NODE_T(buf_page_t) flush_list;  展开后为

ut_list_base<buf_page_t, ut_list_node buf_page_t::*> 。其中，ut_list_node buf_page_t::*是buf_page_t的成员变量指针的类型，即buf_page_t内成员偏移量的变量类型。

node字段的初始化在UT_LIST_INIT宏中，例如 UT_LIST_INIT(buf_pool->flush_list, &buf_page_t::list)中将node初始化为buf_page_t的list字段（即ut_list_node类型字段）的对象内偏移量

基本操作接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
UT_LIST_ADD_FIRST(LIST, ELEM);
UT_LIST_ADD_LAST(LIST, ELEM);
UT_LIST_INSERT_AFTER(LIST, ELEM1, ELEM2);
UT_LIST_REMOVE(LIST, ELEM);

UT_LIST_GET_NEXT(NAME, N); // 返回双向链表NAME的N节点的后继
UT_LIST_GET_PREV(NAME, N); // 返回双向链表NAME的N节点的前驱

UT_LIST_REVERSE(LIST);  // 逆序
UT_LIST_MOVE_TO_FRONT(LIST);

ut_list_map(const List& list, Fucntor &functor); // 遍历，functor(elem_type)
ut_list_exist(List &list, typename List::elem_type *elem);

向量 ib_vector_t

ib_vector_t自带了一个内存分配器，默认是heap_allocator。

1
2
3
4
5
6
7
8
struct ib_vector_t
{
  ib_alloc_t *allocator; // 分配器
  void *data;  // elemtns
  ulint used;  //
  ulint total; //
  ulint sizeof_value;
};

ib_alloc_t是内存分配器的抽象接口，里面定义了 申请、释放、resize三个函数指针。

1
2
3
4
5
6
struct ib_alloc_t {
  ib_mem_alloc_t mem_malloc;
  ib_mem_free_t  mem_release;
  ib_mem_resize_t mem_resize;
  void *arg;
};

具体的子类有heap_alloc/sync_heap/self_heap等等。

以heap_alloc为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
heap_alloc->arg = heap; // mem_heap_t*
heap_alloc->mem_malloc = ib_heap_malloc;
heap_alloc->mem_release = ib_heap_free;
heap_alloc->mem_resize = ib_heap_resize;

其中, mem_heap_t 定义：
typedef mem_block_t mem_heap_t;
typedef struct mem_block_info_t mem_block_t;

void* ib_heap_malloc(ib_alloc_t *allocator /* 底层分配器*/, ulint size)
{
  mem_heap_t *heap = (mem_heap_t*) allocator->arg;
  return mem_heap_alloc(heap, size); // 略
}

回到ib_vector_t的相关函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ib_vector* ib_vector_create(ib_alloc_t *allocator, ulint sizeof_value, ulint size)
|-- ib_vector_t *vec;
|-- vec = (ib_vector_t*)allocator->mem_alloc(allocator, sizeof(*vec));
|-- vec->used = 0;
|-- vec->total = size;
|-- vec->data = (void*)allocator->mem_alloc(allocator, sizeof_value * size);

ib_vector_push(ib_vector_t *vec, const void* elem)
|-- if (vec->used >= vec->total)
|---|-- ib_vector_resize(vec);
|---|---|-- new_total = vec->total * 2;
|---|---|-- vec->data = vec->allocator->mem_resize(vec->allocator, vec->data, old_size, new_size);
|-- last = vec->data + IB_VEC_OFFSET(vec, vec->used);
|-- memcpy(last, elem, vec->sizeof_value);
|-- vec->used++;

工作队列 ib_wqueue_t

ib_wqueue_t 是一个支持并发访问的阻塞队列。

1
2
3
4
5
6
struct ib_wqueue_t
{
  ib_mutex_t mutex; // 线程安全
  ib_list_t *items; // 链表
  os_event_t event; // 条件变量
};

哈希表 hash_table_t

1
2
3
4
typedef struct hash_table_struct {
	ib_ulint_t n_cells;
  hash_cell_t *array;
} hash_table_t;

hash_table_t 哈希表，冲突串链，hash_cell_t 即桶对象。

操作接口：HASH_INSERT / HASH_DELETE / HASH_SEARCH / HASH_SEARCH_ALL / HASH_DELETE_AND_COMPACT / HASH_MIGRATE 。

以HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA) 的一个具体操作例子，HASH_INSERT(buf_page_t, hash, buf_pool->page_hash, b->id.fold(), b); 参数各字段含义是：

1
2
3
4
5
TYPE = buf_pool_t
NAME = hash                     即buf_pool_t::hash字段，是用于hash冲突串链的next字段。
TABLE = buf_pool->page_hash     hashtable对象本身。
FOLD = b->id.fold()             计算hash值
DATA = b                        要插入的对象

注：看实现代码，HASH_SEARCH是先根据哈希值找到桶，然后在桶内查找。

Tags: MySQL
← InnoDB源码解析-存储管理层次 Databricks Lakehouse →

扫描二维码，分享此文章