本文详细介绍了Linux的XArray数据结构。

注意:本文分析中引用的代码来自于:linux-5.1.21.tar.xz

Xarray的由来

Matthew Wilcox认为内核的基数树的API设计不合理,比如

  • (1)“树”这个术语就很有迷惑性。基数树跟传统的,教科书上那种树,并不是很像。举例来说,树上的增加entry的操作,一直都被称为“插入”。但对基数树而言,“插入”并不是字面上发生的事情,尤其是当key已经存在的时候。基数树也支持“异常entry“,光是这个名字,就让用户听着不敢用了。

  • (2)基数树还要求用户自己处理锁。

Wilcox决定改良接口。基数树本身不变,它本身没什么问题。改变的是接口,现在接口暗示用户,把它当做数组来用,而不是当做树来用。因为基数树看起来就像是一个自动增长的数组:一个用unsigned long来索引的指针数组。这种视图,更好地描述了基数树的用途。

  • (1)XArray默认自己处理了锁,简化了使用
  • (2)基数树的“预加载”机制允许用户获取锁之前先预先分配内存,这个机制在XArray中被取消了,它太复杂又没有太多实际价值。
  • (3)XArray API被分为两部分,普通API和高级API。后者给用户更多可控性,比如用户可以显式管理锁。API可以用于不同的场景,满足不同的需求。比如Page Cache就可以用XArray。普通API完全在高级API的基础上实现,所以普通API也是高级API的使用范例。

另外:Xarray的全称为:eXtensible Arrays

XArray 基本数据结构

XArray主要包括结构体struct xarray和结构体struct xa_node.

xarray

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * struct xarray - The anchor of the XArray.
 * @xa_lock: Lock that protects the contents of the XArray.
 *
 * To use the xarray, define it statically or embed it in your data structure.
 * It is a very small data structure, so it does not usually make sense to
 * allocate it separately and keep a pointer to it in your data structure.
 *
 * You may use the xa_lock to protect your own data structures as well.
 */
/*
 * If all of the entries in the array are NULL, @xa_head is a NULL pointer.
 * If the only non-NULL entry in the array is at index 0, @xa_head is that
 * entry.  If any other entry in the array is non-NULL, @xa_head points
 * to an @xa_node.
 */
struct xarray {
	spinlock_t	xa_lock;
/* private: The rest of the data structure is not to be used directly. */
	gfp_t		xa_flags;
	void __rcu *	xa_head;
};

成员说明:

  • xa_lock: 用于包含XArray内容的锁。
  • xa_head:用于顶级的xa_node节点。

xa_node

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * @count is the count of every non-NULL element in the ->slots array
 * whether that is a value entry, a retry entry, a user pointer,
 * a sibling entry or a pointer to the next level of the tree.
 * @nr_values is the count of every element in ->slots which is
 * either a value entry or a sibling of a value entry.
 */
struct xa_node {
	unsigned char	shift;		/* Bits remaining in each slot */
	unsigned char	offset;		/* Slot offset in parent */
	unsigned char	count;		/* Total entry count */
	unsigned char	nr_values;	/* Value entry count */
	struct xa_node __rcu *parent;	/* NULL at top of tree */
	struct xarray	*array;		/* The array we belong to */
	union {
		struct list_head private_list;	/* For tree user */
		struct rcu_head	rcu_head;	/* Used when freeing node */
	};
	void __rcu	*slots[XA_CHUNK_SIZE];
	union {
		unsigned long	tags[XA_MAX_MARKS][XA_MARK_LONGS];
		unsigned long	marks[XA_MAX_MARKS][XA_MARK_LONGS];
	};
};

成员说明

  • (1)shift成员用于指定当前xa_node的slots数组中成员的单位,当shift为0时,说明当前xa_node的slots数组中成员为叶子节点,当shift为6时,说明当前xa_node的slots数组中成员指向的xa_node可以最多包含2^6(即64)个节点,
  • (2)offset成员表示该xa_node在父节点的slots数组中的偏移。(这里要注意,如果xa_node在父节点为NULL,offset是任意的值,因为没有被初始化)
  • (3)count成员表示该xa_node有多少个slots已经被使用。
  • (4)nr_values成员表示该xa_node有多少个slots存储的Value Entry。
  • (5)parent成员指向该xa_node的父节点
  • (6)array成员指向该xa_node所属的xarray
  • (7)slots是个指针数组,该数组既可以存储下一级的节点, 也可以用于存储即将插入的对象指针

理解一下slots中存放的Entry的规则

slots中存储的entry中的低两位决定了Xarray如何解析其内容。

  1. 低2位是00时,它是一个Pointer Entry
  2. 低2位是10时,它是一个Internal Entry,一般指向下一级的xa_node.但是有些Internal Entry有特别的含义,比如:
  • 0-62: Sibling entries
  • 256: Zero entry
  • 257: Retry entry
  1. 低2为是x1时,它是一个Value Entry,或者tagged pointer

Xarray在linux下的图解

初始化后的图示

当一个XArray初始化后,其只有struct xrray结点,如下图:

![][1]

插入0后的图示

当插入0时,仍然只有xarray一个结构,如下图所示:

![][2]

插入0 和4的图示

当插入0和4时,树的高度增加1,如下图所示:

![][3]

插入131的图示

当插入131时,高度需要再增加1,如下图所示:

![][4]

插入4100的图示

当插入4100时,高度需要再增加1,如下图所示:

![][5]

普通 API

(1)定义一个XArray数组:

1
2
3
4
DEFINE_XARRAY(array_name);
/* or */
struct xarray array;
xa_init(&array);

(2)在XArray里存放一个值:

1
void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp);

这个函数会把参数给出的entry,放到请求的index这个地方。如果要XArray需要分配内存,会使用给定的gfp来分配。如果成功,返回值是之前存放在index的值。删除一个entry可以通过在这里存放NULL来实现,或者调用

1
void *xa_erase(struct xarray *xa, unsigned long index);

(3)xa_store的变体:

  • xa_insert用于存放但不覆盖现有的entry
  • 另一个变体:xa_cmpxchg,只有当存的值和old参数匹配上时,才会将entry存在index处。
1
2
3
4
static inline int __must_check xa_insert(struct xarray *xa,
		unsigned long index, void *entry, gfp_t gfp);
static inline void *xa_cmpxchg(struct xarray *xa, unsigned long index,
			void *old, void *entry, gfp_t gfp);

(4)用xa_load()从XArray里取出一个值:

1
void *xa_load(struct xarray *xa, unsigned long index);

返回值是存放在index处的值。XArray里,空entry和存入NULL的entry是等价的。因此xa_load不会对空entry有特殊的处理。

(5)非空entry上还可以设置最多3个比特的标签,标签管理函数:

1
2
3
bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark);
void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark);
void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark);

mark的值是XA_MARK_0, XA_MARK_1, XA_MARK_2三者之一。 xa_set_mark用于在index处的entry上设置标签 xa_clear_mark用于清除标签 xa_get_mark用于返回index处的entry的标签

(6)XArray是很稀疏的,因此一个普遍的准则是,不要进行低效的遍历查找非空项。要查找多个非空项,应该使用这个宏:

1
2
3
xa_for_each(xa, entry, index, max, filter) {
    /* Process "entry" */
}

在进入循环之前,需要把index设为遍历的起点,max设为遍历的最大index,filter指定需要过滤的mark。 循环执行时,index会被设为当前匹配到的entry。可以在循环里修改index,来改变迭代过程。修改XArray自身也是允许的。

(7)删除一个Xarray中所有的Entry

1
void xa_destroy(struct xarray *xa);

还有其他很多操作XArray的普通API。特殊情况下还可以使用高级API。 其它普通API包括:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
xa_for_each_marked()
xa_marked()
xa_extract()
xa_for_each_start()
xa_for_each_range()
xa_find()
xa_find_after() 
xa_empty() 
xa_reserve() 
xa_release()
xa_err()
xa_is_err() 
DEFINE_XARRAY_ALLOC() 
xa_init_flags()
xa_alloc() 
xa_alloc_bh()
xa_alloc_irq()
xa_alloc_cyclic().
DEFINE_XARRAY_ALLOC1()

高级 API

高级API我们留在下节文章分享。

参考文章