Xarray vs Maple Tree

虽然系统中引入了maple tree，但是我们看到还是有很多地方在使用xarray，尤其是address space。现在我们来比较一下，这两种数据结构。看看同样是存储数据，这两种数据结构是怎么处理的。

这里采用的方法是通过xa_dump()/mt_dump()实际观察数据结构中的变化。

存储值

单个值

我们同样在0x123这个index写入value 6，来看看这两个数据结构是怎么保存这个值的。

xarray代码

	xa_store(&my_array, 0x123, xa_mk_value(6), GFP_NOWAIT | __GFP_DIRECT_RECLAIM);
	xa_dump(&my_array);
	xa_destroy(&my_array);

maple tree代码

	mas_set(&mas_writer, 0x123);
	mas_store_gfp(&mas_writer, xa_mk_value(6), GFP_KERNEL);
	mt_dump(&tree, mt_dump_dec);

dump 输出

xarray:

xarray: 0x5d98839f3a00x head 0x60c000000102x flags 0 marks 0 0 0
0-511: node 0x60c000000100x max 0 parent (nil)x shift 6 count 1 values 0 array 0x5d98839f3a00x list 0x60c000000118x 0x60c000000118x marks 0 0 0
  256-319: node 0x60c0000001c0x offset 4 parent 0x60c000000100x shift 3 count 1 values 0 array 0x5d98839f3a00x list 0x60c0000001d8x 0x60c0000001d8x marks 0 0 0
    288-295: node 0x60c000000280x offset 4 parent 0x60c0000001c0x shift 0 count 1 values 1 array 0x5d98839f3a00x list 0x60c000000298x 0x60c000000298x marks 0 0 0
      291: value 6 (0x6) [0xdx]

maple tree:

maple_tree(0x7fffe1680eb0) flags 5, height 1 root 0x61500000010e
0-18446744073709551615: node 0x615000000100 depth 0 type 1 parent 0x7fffe1680eb1 contents: (nil) 290 0xd 291 (nil) 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x2
  0-290: (nil)
  291: value 6 (0x6) [0xd]
  292-18446744073709551615: (nil)

可以看到maple tree只用了一个node，而xarray用了三个node。可以说，此时maple tree完胜。

当然，如果我们存储一个较小的index，（8以内）。因为被一个xa_node覆盖，所以在xarray中也是可以用一个node表达。但是这种情况在实际使用中太少了。

两个有一定间隔的值

在上面的基础上，我们再看看此时再一个有一定距离的index上存储一个值会如何？

xarray代码

maple tree代码

dump 输出

和上面的情况类似，对于xarray，index的位置是固定的，所以为了保存到index 5，xarray必须把和5有关的那些index位置也分配出来。而mapple tree则不需要，直接挤在一个节点就可以了。

存储范围

接下来我们看看存储一个范围的情况。

xarray 代码

maple tree 代码

dump 输出

同样是在一段区域内存储，maple tree只占用一个slot，而xarray则是要占用很多（占用的数量和区域大小一致）。

并且以此类推，如果在xarray中，我们扩大一下存储的区域。

xarray 代码

此时 dump 出来的结果就是

而同样是操作区域[0x123, 0x123 + 5], maple tree则还是用一个slot来代表。

maple tree 代码

dump 输出

到这里，我想我也基本理解了xarray和maple tree之间的区别了。

PreviousMaple TreeNextInterval Tree

Last updated

Was this helpful?