linux中xarray结构简析

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后的节点。)

相关推荐

  1. linuxxarray结构

    2023-12-07 19:44:03       63 阅读
  2. 数据库索引

    2023-12-07 19:44:03       55 阅读
  3. Spring Boot

    2023-12-07 19:44:03       40 阅读
  4. :分账系统

    2023-12-07 19:44:03       28 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-07 19:44:03       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-07 19:44:03       100 阅读
  3. 在Django里面运行非项目文件

    2023-12-07 19:44:03       82 阅读
  4. Python语言-面向对象

    2023-12-07 19:44:03       91 阅读

热门阅读

  1. Pod 存活探针 livenessProbe

    2023-12-07 19:44:03       58 阅读
  2. sklearn 笔记:neighbors.NearestNeighbors 自定义metric

    2023-12-07 19:44:03       56 阅读
  3. 当内核有内存泄漏的时候

    2023-12-07 19:44:03       44 阅读
  4. 【Spark基础】-- 宽窄依赖

    2023-12-07 19:44:03       49 阅读
  5. 拥有一台服务器可以做些什么

    2023-12-07 19:44:03       65 阅读
  6. Spark SQL百万级数据批量读写入MySQL

    2023-12-07 19:44:03       62 阅读
  7. 什么问题适合使用卡方检验?

    2023-12-07 19:44:03       44 阅读
  8. qt 链表QList,QLinkedList的常见使用

    2023-12-07 19:44:03       59 阅读
  9. 英伟达显卡系列与架构、代表产品

    2023-12-07 19:44:03       60 阅读
  10. Ubuntu 配置打开文件限制

    2023-12-07 19:44:03       64 阅读
  11. Python批量图像处理--图片重命名、图片旋转

    2023-12-07 19:44:03       64 阅读
  12. CG 函数

    2023-12-07 19:44:03       56 阅读