linux中xarray与maple结构简析

2023-12-13 21:55:57

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值,则要连带向上传播。

文章来源:https://blog.csdn.net/qq_37517281/article/details/134860583
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。