> For the complete documentation index, see [llms.txt](https://richardweiyang-2.gitbook.io/kernel-exploring/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://richardweiyang-2.gitbook.io/kernel-exploring/00-index-3/06-maple_tree/08-xarray_vs_maple_tree.md).

# 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代码

```
	xa_store(&my_array, 5, xa_mk_value(5), GFP_NOWAIT | __GFP_DIRECT_RECLAIM);
	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, 5);
	mas_store_gfp(&mas_writer, xa_mk_value(5), GFP_KERNEL);
	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: 0x5f23e8340280x head 0x60c000000282x flags 0 marks 0 0 0
  0-511: node 0x60c000000280x max 0 parent (nil)x shift 6 count 2 values 0 array 0x5f23e8340280x list 0x60c000000298x 0x60c000000298x marks 0 0 0
    0-63: node 0x60c0000001c0x offset 0 parent 0x60c000000280x shift 3 count 1 values 0 array 0x5f23e8340280x list 0x60c0000001d8x 0x60c0000001d8x marks 0 0 0
      0-7: node 0x60c000000100x offset 0 parent 0x60c0000001c0x shift 0 count 1 values 1 array 0x5f23e8340280x list 0x60c000000118x 0x60c000000118x marks 0 0 0
        5: value 5 (0x5) [0xbx]
    256-319: node 0x60c000000340x offset 4 parent 0x60c000000280x shift 3 count 1 values 0 array 0x5f23e8340280x list 0x60c000000358x 0x60c000000358x marks 0 0 0
      288-295: node 0x60c000000400x offset 4 parent 0x60c000000340x shift 0 count 1 values 1 array 0x5f23e8340280x list 0x60c000000418x 0x60c000000418x marks 0 0 0
        291: value 6 (0x6) [0xdx]

maple tree:

maple_tree(0x7ffd88e59c40) flags 5, height 1 root 0x61500000010e
0-18446744073709551615: node 0x615000000100 depth 0 type 1 parent 0x7ffd88e59c41 contents: (nil) 4 0xb 5 (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 0x4
  0-4: (nil)
  5: value 5 (0x5) [0xb]
  6-290: (nil)
  291: value 6 (0x6) [0xd]
  292-18446744073709551615: (nil)
```

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

## 存储范围

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

xarray 代码

```
	xa_store_range(&my_array, 0x123, 0x123 + 2, xa_mk_value(6), GFP_NOWAIT | __GFP_DIRECT_RECLAIM);
	xa_dump(&my_array);
	xa_destroy(&my_array);
```

maple tree 代码

```
```

dump 输出

```
xarray:

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

maple tree:

maple_tree(0x7ffd66fac520) flags 5, height 1 root 0x61500000010e
0-18446744073709551615: node 0x615000000100 depth 0 type 1 parent 0x7ffd66fac521 contents: (nil) 290 0xd 293 (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-293: value 6 (0x6) [0xd]
  294-18446744073709551615: (nil)
```

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

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

xarray 代码

```
	xa_store_range(&my_array, 0x123, 0x123 + 5, xa_mk_value(6), GFP_NOWAIT | __GFP_DIRECT_RECLAIM);
	xa_dump(&my_array);
	xa_destroy(&my_array);
```

此时 dump 出来的结果就是

```
xarray:

xarray: 0x56512f750300x head 0x60c000000102x flags 0 marks 0 0 0
  0-511: node 0x60c000000100x max 0 parent (nil)x shift 6 count 1 values 0 array 0x56512f750300x list 0x60c000000118x 0x60c000000118x marks 0 0 0
    256-319: node 0x60c0000001c0x offset 4 parent 0x60c000000100x shift 3 count 2 values 0 array 0x56512f750300x list 0x60c0000001d8x 0x60c0000001d8x marks 0 0 0
      288-295: node 0x60c000000340x offset 4 parent 0x60c0000001c0x shift 0 count 5 values 5 array 0x56512f750300x list 0x60c000000358x 0x60c000000358x marks 0 0 0
        291: value 6 (0x6) [0xdx]
        292: sibling (slot 3)
        293: sibling (slot 3)
        294: sibling (slot 3)
        295: sibling (slot 3)
      296-303: node 0x60c000000280x offset 5 parent 0x60c0000001c0x shift 0 count 1 values 1 array 0x56512f750300x list 0x60c000000298x 0x60c000000298x marks 0 0 0
        296: value 6 (0x6) [0xdx]
```

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

maple tree 代码

```
	mas_set_range(&mas_writer, 0x123, 0x123 + 5);
	mas_store_gfp(&mas_writer, xa_mk_value(6), GFP_KERNEL);
	mt_dump(&tree, mt_dump_dec);
```

dump 输出

```
maple tree

maple_tree(0x7ffd796e3e70) flags 5, height 1 root 0x61500000010e
0-18446744073709551615: node 0x615000000100 depth 0 type 1 parent 0x7ffd796e3e71 contents: (nil) 290 0xd 296 (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-296: value 6 (0x6) [0xd]
  297-18446744073709551615: (nil)
```

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://richardweiyang-2.gitbook.io/kernel-exploring/00-index-3/06-maple_tree/08-xarray_vs_maple_tree.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.