linux中xarray与maple结构简析
xarray
简述
xarray是radixtree的一种实现,它部分使用了rcu机制来代替radixtree的加锁。
node结构
node的基本结构:
struct xa_node {
unsigned char shift; // 表示index取地址的高多少bit作下层的slot index
unsigned char offset; // node在上层结点中的slot index
void __rcu *slots[XA_CHUNK_SIZE]; // 下层的结点指针或数值
}
下层节点的slot可能存node、sibling、value。
节点插入(xas_store)
当插入一段地址区间时[0x112100, 0x112233],假设最后一级node的shift是8,上一级的shift是16,则它的index为[21, 23],(2233align到8位是2300),它跨过了21,22,23三个slot,则21是一个value节点,22,23是sibling节点指向21,如果22, 23中有节点是已经分裂的有更小shift的node,则要把这个node free掉,相当于原有区间被新的更大区间覆盖。(xas_store)
在插入更下层精细node节点(shift 更小的节点)时,要先调用xas_split_alloc做分割和内存分配,然后加锁的情况下做类似copy on write 的操作(xas_split将原表项迁移至新的split后的节点。)
节点删除(xas_shrink)
没什么特别的,除了当删除node时发现根节点只有第一个slot占用时,会用第一个slot指向的node来代替根节点,放在xa_head上。(xas_shrink)
maple
简述
maple 是一种b树的实现。但存的不是key,而是区间,区间的端点用pivot表示。pivot-1到pivot之间的区间是左开右闭的,即:(slot[pivot-1], slot[pivot]]。
/**
* Slots -> | 0 | 1 | 2 | ... | 12 | 13 | 14 | 15 |
* ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬
* │ │ │ │ │ │ │ │ └─ Implied maximum
* │ │ │ │ │ │ │ └─ Pivot 14
* │ │ │ │ │ │ └─ Pivot 13
* │ │ │ │ │ └─ Pivot 12
* │ │ │ │ └─ Pivot 11
* │ │ │ └─ Pivot 2
* │ │ └─ Pivot 1
* │ └─ Pivot 0
* └─ Implied minimum
*/
node结构
node 节点有五种形式:
1、pointer,叶子值
2、dense_node,点形式
void __rcu *slot[MAPLE_NODE_SLOTS];
3、maple_range_64,范围
struct maple_range_64 {
unsigned long pivot[MAPLE_RANGE64_SLOTS - 1];
void __rcu *slot[MAPLE_RANGE64_SLOTS];
}
4、maple_arange_64,带gap信息的node
struct maple_arange_64{
unsigned long pivot[MAPLE_ARANGE64_SLOTS - 1];
void __rcu *slot[MAPLE_ARANGE64_SLOTS];
unsigned long gap[MAPLE_ARANGE64_SLOTS];
struct maple_metadata meta;
}
5、除此之外当node不在树里时,会表现为dead状态的节点,长这样
struct {
void *pad;
struct rcu_head rcu;
struct maple_enode *piv_parent;
unsigned char parent_slot;
enum maple_type type;
unsigned char slot_len;
unsigned int ma_flags;
};
gap数组
考虑分配内存的场景,它不关心已经分配的区间,只关心未分配的区间,因而在maple_arange_64引入gap[]的节点,记录每个对应区间的最大空闲区间的大小,同时在node上引入一个meta叫gap(这两个名字是重的,maple的实现中有挺多第一次读时让人容易误解的命名),记录这个节点上有最大的空闲区间的区间index。可以通过mas_empty_area或mas_empty_area_rev来遍历gap(meta)和gap[],找到满足分配大小的最高的区间或最低的区间。
节点插入(mas_store)
节点插入时可能横跨多个节点(mas_wr_spanning_store),也可能不跨过节点(mas_wr_modify)。
如果横跨了个节点,则先找到范围两头所在的两个node节点(mas_wr_walk_index),忽略中间跨跃的区间和节点,将左节点前半部分、插入节点、右节点后半部分合并到一个栈上分配的struct?maple_big_node上,然后调mas_spanning_rebalance做分裂与合并。(mas_wr_spanning_store)
如果插入时没有跨节点,则检查节点中已有slot的情况(mas_wr_modify):
1、最简单的情况就是插入节点刚好完全覆盖原来为null的区间,这时只要把插入节点放在右pivot对应的slot上就可以了,顺便更新下gap。
2、最后两个pivot假设为a,b,插入的区间是c1,c2,则有些情况可以只简单改slot的值(mas_wr_append):
- (a,b],..,(c1,c2]
- (a/c1, c2], (c2,b]
- (a, c1], (c1, c2/b]
- (a,b/c1], (b/c1, c2]
3、如果是插在中间,则需要移动一些节点(mas_wr_node_store)。
4、最麻烦的情况是插入导致一个节点满了(mas_wr_bnode)。需要先在栈上生成一个中间大节点,把原node上的slots和要插入的节点一起放了大节点(mas_store_b_node),再去检查是否可以把一部分数据推到左右节点(mas_split->mas_push_data),如果不行就从下向上做一次分裂(mas_split->mast_split_data,这里只做分裂,不像rebalance那样还做合并)。
节点分裂与合并(mas_spanning_rebalance)
rebalance过程会找右节点,如果右节点不存在才找左节点,将这个兄弟节点的slot拷贝到栈上大节点,再创建两个新节点去分割这个大节点。
这里有个分裂成三个节点的情况:如果左右节点原本都是满的,新插入节点后,会装不下;或者如果选定的是右节点,则有一种情况,插入的节点刚好跨过了左边的max和右边的min导致多分出一个节点,也可能导致装不下。
接下来找到原来的左父节点与右父节点,将分裂后的两个或三个节点与左右父节点合并放回big node,合并后的slot数有三种情况:
1、如果big node的节点数不超过一个node的slot数的一半,则继续分裂(mas_spanning_rebalance)。
2、如果不超过一个node一半大小,则找它相邻的右下一个区间node(没有右节点找左上一个区间node),尝试与它合并(mast_spanning_rebalance,名字与之前那个会看混)并继续尝试是否需要分裂(mas_spanning_rebalance)。
3、如果big node 上节点在一半到满之间,那所有循环中的逻辑mas_mab_to_node、mast_set_split_parents、mast_cp_to_nodes、mast_combine_cp_right近乎不起作用,只是调整原有节点的值而已。
由于mas_spanning_rebalance代码用了count计数来模拟DFS过程,会有点难以理解,理解这里一个基本原则是:big node上节点超过node的slot数,则分裂一次再向上递归,向上递归前如果big node上节点不足node的slot数一半,则合并旁边节点,然后在本层多循环一次。
节点删除(mas_erase)
删除节点时,调mas_wr_store_entry来存一个空值(struct ma_wr_state上的entry为空),与原来插入路径一样,但在赋空值的同时会调mas_update_gap,更新区间的最大gap值到gap[]上,同时在node->meta上更新最大gap所在的pivot index。如果修改了本节点的最大gap值,则要连带向上传播。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!