xarray是radixtree的一种实现,它部分使用了rcu机制来代替radixtree的加锁。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。
当插入一段地址区间时[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)
tree的根节点,删除node时发现根节点只有第一个slot占用时,会用第一个slot指向的node来代替根节点,放在xa_head上。(xas_shrink)
在插入更精细node节点(shift 更小的节点)时,要先调用xas_split_alloc做分割和内存分配,然后加锁的情况下做类似copy on write 的操作(xas_split将原表项迁移至新的split后的节点。)