无锁hash
## LF_HASH 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23typedef struct st_lf_hash {
LF_DYNARRAY array; /* hash itself */ 这个内部的element size 是sizeof(LF_SLIST *)
LF_ALLOCATOR alloc; /* allocator for elements */
my_hash_get_key get_key; /* see HASH */ --》query_cache_table_get_key
CHARSET_INFO *charset; /* see HASH */
lf_hash_func *hash_function; /* see HASH */
uint key_offset, key_length; /* see HASH */
uint element_size; /* size of memcpy'ed area on insert */
uint flags; /* LF_HASH_UNIQUE, etc */
int32 volatile size; /* size of array */
int32 volatile count; /* number of elements in the hash */
/**
"Initialize" hook - called to finish initialization of object provided by
LF_ALLOCATOR (which is pointed by "dst" parameter) and set element key
from object passed as parameter to lf_hash_insert (pointed by "src"
parameter). Allows to use LF_HASH with objects which are not "trivially
copyable".
NULL value means that element initialization is carried out by copying
first element_size bytes from object which provided as parameter to
lf_hash_insert.
*/
lf_hash_init_func *initialize;
} LF_HASH;
存放element后, 防止在使用的过程中, element 被释放了, 因此需要一个allocator, 里面关键是存放pinbox, 当使用一个元素时,申请一个lf_pins, 将这个指针放到lf_pins->pin中, 所有已回收的LF_PINS还是在数组中,不过使用stack来管理,pinstack_top_ver就是这个栈顶。前面说每个LF_PINS都有一个purgatory链表,链表中每个元素的next指针实际上是在addr的指定偏移位置,这个位置即由free_ptr_offset指定,free_func和free_func_arg则是当某个LF_PINS的purgatory等于10时,真正释放他们的回调函数及参数 ## LF_DYNARRAY ## LF_DYNARRAY
## LF_DYNARRAY & LF_ALLOCATOR & LF_PINBOX
1 | #define LF_DYNARRAY_LEVEL_LENGTH 256 |
### LF_ALLOCATOR LF_ALLOCATOR是一个简易的内存分配器,它里面包含一个LF_PINBOX,所有线程首先先从pinbox中申请一个LF_PINS,然后需要申请内存时就向LF_ALLOCATOR来申请(每次申请的大小固定),将申请到的地址pin在自己的LF_PINS当中。LF_ALLOCATOR将线程free掉的内存同样是用free stack来缓存起来,先看定义:
1 | typedef struct st_lf_allocator { |
### LF_PINBOX pinstack_top_ver 是要解决aba 的问题的 1
2
3
4
5
6
7
8typedef struct {
LF_DYNARRAY pinarray; -->> lf_dynarray_init(&pinbox->pinarray, sizeof(LF_PINS));
lf_pinbox_free_func *free_func; --》 (lf_pinbox_free_func *)alloc_free
void *free_func_arg; --》 //LF_HASH->alloc
uint free_ptr_offset; --> offsetof(LF_SLIST, key)
uint32 volatile pinstack_top_ver; /* this is a versioned pointer */
uint32 volatile pins_in_array; /* number of elements in array */
} LF_PINBOX;
### LF_PINS 1
2
3
4
5
6
7
8
9
10
11
12
typedef struct st_lf_pins {
void * volatile pin[LF_PINBOX_PINS];
LF_PINBOX *pinbox;
void *purgatory;
uint32 purgatory_count;
uint32 volatile link;
/* we want sizeof(LF_PINS) to be 64 to avoid false sharing */
#if SIZEOF_INT*2+SIZEOF_CHARP*(LF_PINBOX_PINS+2) != 64
char pad[64-sizeof(uint32)*2-sizeof(void*)*(LF_PINBOX_PINS+2)];
#endif
} LF_PINS;
1
2
3
4
5
6
7
8
9
10typedef struct {
intptr volatile link; /* a pointer to the next element in a listand a flag */
uint32 hashnr; /* reversed hash number, for sorting */
const uchar *key;
size_t keylen;
/*
data is stored here, directly after the keylen.
thus the pointer to data is (void*)(slist_element_ptr+1)
*/
} LF_SLIST;
query cache 中有一个LF_HASH,
初始化时是这样:
1 | lf_hash_init(&queries, sizeof(Query_cache_block *), LF_HASH_UNIQUE, 0, 0, |
真正使用上是这样
1 | #define lf_hash_init(A, B, C, D, E, F, G) \ |
看看它的数据结构,基本就和初始化部分比较吻合
初始化里面, 比较简单, 就几个注意点
1 | hash->charset= charset ? charset : &my_charset_bin; |
介绍2个子数据结构的初始化 hash->array, 在lf_hash_init2函数中
1 | lf_dynarray_init(&hash->array, sizeof(LF_SLIST *)); |
数据结构如下
第二个子数据结构 hash->alloc, 在函数 lf_hash_init2 中
初始化调用 1
2lf_alloc_init2(&hash->alloc, sizeof(LF_SLIST)+lf_hash->element_size,
offsetof(LF_SLIST, key), ctor, dtor);
我们再来看pinbox 数据结构
1 |
|
# 使用 ## 获取pin lf_hash_get_pins(&queries)
先看一下pin的数据结构
1 | LF_PINS *lf_pinbox_get_pins(LF_PINBOX *pinbox) { |