tree ==== :: NAME tree - display radix tree, XArray, red-black tree or maple tree SYNOPSIS tree [-t [radix|xarray|rbtree|maple]] [-r offset] [-[s|S] struct[.member[,member]]] -[x|d] [-o offset] [-l] [-p] [-v] [-N] start DESCRIPTION This command dumps the contents of a radix tree, an XAarray, a red-black tree, or a maple tree. The arguments are as follows: -t type The type of tree to dump; the type string can be one of "radix", "rbtree", "xarray", or "maple", or alternatively, "ra", "rb", "x" or "m" are acceptable. If not specified, rbtree is the default type. -r offset If the "start" argument is the address of a data structure that contains an radix_tree_root, maple_tree, xarray or rb_root structure, then this is the offset to that structure member. If the offset is non-zero, then this option is required. The offset may be entered in either of two manners: 1. In "structure.member" format. 2. A number of bytes. -o offset For red-black trees only, the offset of the rb_node within its containing data structure; if the offset is non-zero, then this option is required. The offset may be entered in either of two manners: 1. In "structure.member" format. 2. A number of bytes. This option is not applicable to radix trees. -s struct For each entry in a tree, format and print it as this type of data structure; use the "struct.member" format in order to display a particular member of the structure. To display multiple members of a structure, use a comma-separated list of members. If any structure member contains an embedded structure or is an array, the the output may be restricted to the embedded structure or an array element by expressing the member argument as "struct.member.member" or "struct.member[index]"; embedded member specifications may extend beyond one level deep by expressing the struct argument as "struct.member.member.member...". -S struct Similar to -s, but instead of parsing gdb output, member values are read directly from memory, so the command works much faster for 1-, 2-, 4-, and 8-byte members. -l For red-black trees, dump the tree sorted in linear order starting with the leftmost node and progressing to the right. This option does not apply to radix trees. -p Display the node's position information, showing the relationship between it and the root. For red-black trees, a position that indicates "root/l/r" means that the node is the right child of the left child of the root node. For radix trees, xarrays and maple trees, the index, the height, and the slot index values are shown with respect to the root. -x Override default output format with hexadecimal format. -d Override default output format with decimal format. -v For maple trees only, dump the contents of each maple tree node. The meaning of the "start" argument, which can be expressed either in hexadecimal format or symbolically, depends upon whether the -N option is prepended: start The address of a radix_tree_root, maple_tree, xarray or rb_root structure, or the address of a structure containing the radix_tree_root, maple_tree, xarray or rb_root structure; if the latter, then the "-r offset" option must be used if the member offset of the root structure is non-zero. -N start The address of a radix_tree_node, maple_node, xa_node or rb_node structure, bypassing the radix_tree_root, maple_tree, xarray, or rb_root that points to it. EXAMPLES The vmap_area_root is a standalone rb_root structure. Display the virtual addresses of each vmap_area in its red-black tree: crash> whatis vmap_area_root struct rb_root vmap_area_root; crash> tree -t rbtree -o vmap_area.rb_node vmap_area_root ffff880128c508c0 ffff88012cb68140 ffff88012c9afec0 ffff88012d65c440 ... Display the vmap_area's va_start and va_end members of each of the entries above expressing the vmap_area.rb_node offset as a number of bytes: crash> tree -t rbtree -o 24 vmap_area_root -s vmap_area.va_start,va_end ffff880128c508c0 va_start = 0xffffc90014900000 va_end = 0xffffc90014921000 ffff88012cb68140 va_start = 0xffffc900110c0000 va_end = 0xffffc900110d1000 ffff88012c9afec0 va_start = 0xffffc90000640000 va_end = 0xffffc90000642000 ffff88012d65c440 va_start = 0xffffc90000620000 va_end = 0xffffc90000622000 ... Alternatively, use the -N option with the rb_node address contained in the vmap_area_root structure: crash> p vmap_area_root vmap_area_root = $8 = { rb_node = 0xffff880128c508d8 } crash> tree -t rbtree -o vmap_area.rb_node -N 0xffff880128c508d8 ffff880128c508c0 ffff88012cb68140 ffff88012c9afec0 ffff88012d65c440 Display the virtual address of each vm_area_struct in the red-black tree that has its root inside an mm_struct located at ffff880128b5a300. The vm_area_struct.vm_rb rb_node member has an offset of 0x38 bytes: crash> tree -t rbtree -r mm_struct.mm_rb ffff880128b5a300 -o 0x38 ffff88012a0de080 ffff880123e3ac78 ffff880123e3a700 ffff88012b2837c8 ... ffff880128c02ed0 ffff8801292e7958 ffff880123e3a318 ffff880123e3ad40 Add the -p option to the command above to show position information: crash> tree -t rbtree -r mm_struct.mm_rb ffff880128b5a300 -o 0x38 -p ffff88012a0de080 position: root ffff880123e3ac78 position: root/l ffff880123e3a700 position: root/l/l ffff88012b2837c8 position: root/l/l/l ... ffff880128c02ed0 position: root/r/r/l/r ffff8801292e7958 position: root/r/r/l/r/r ffff880123e3a318 position: root/r/r/r ffff880123e3ad40 position: root/r/r/r/r Given an mm_struct address of 0xffff880074b5be80, list the VMA tree in linear order from the leftmost node progressing to the right using the -l option: crash> tree -ls vm_area_struct.vm_start -o vm_area_struct.vm_rb \ -r mm_struct.mm_rb 0xffff880074b5be80 | paste - - ffff88001f2c50e0 vm_start = 0x400000 ffff88001f2c5290 vm_start = 0xceb000 ffff880074bfc6c0 vm_start = 0xcec000 ffff88001f2c4bd0 vm_start = 0xd10000 ffff880074bfc948 vm_start = 0x1fe9000 ffff880036e54510 vm_start = 0x7ff6aa296000 ffff88001f2c5bd8 vm_start = 0x7ff6aa298000 ffff880036e54af8 vm_start = 0x7ff6aa497000 ffff880036e54f30 vm_start = 0x7ff6aa498000 ffff88000e06aa20 vm_start = 0x7ff6aa499000 ffff88000e06b368 vm_start = 0x7ff6ab95f000 ... ffff88001f2c5e60 vm_start = 0x7ff6bc1af000 ffff88001f2c4ca8 vm_start = 0x7ff6bc1b6000 ffff88001f2c5008 vm_start = 0x7ff6bc200000 ffff88001f2c5d88 vm_start = 0x7ff6bc205000 ffff880074bfd6c8 vm_start = 0x7ff6bc206000 ffff88001f2c4288 vm_start = 0x7ff6bc207000 ffff88001f2c4510 vm_start = 0x7ffc7a5fc000 ffff88001f2c5b00 vm_start = 0x7ffc7a6d1000 Compared to the top/down root/leaves order: crash> tree -s vm_area_struct.vm_start -o vm_area_struct.vm_rb \ -r mm_struct.mm_rb 0xffff880074b5be80 | paste - - ffff88001f2c5a28 vm_start = 0x7ff6bbbb9000 ffff88001f2c55f0 vm_start = 0x7ff6bb252000 ffff88000e06a360 vm_start = 0x7ff6ac6c3000 ffff88001f2c4bd0 vm_start = 0xd10000 ffff88001f2c5290 vm_start = 0xceb000 ffff88001f2c50e0 vm_start = 0x400000 ffff880074bfc6c0 vm_start = 0xcec000 ffff88000e06b368 vm_start = 0x7ff6ab95f000 ffff88001f2c5bd8 vm_start = 0x7ff6aa298000 ffff880074bfc948 vm_start = 0x1fe9000 ffff880036e54510 vm_start = 0x7ff6aa296000 ffff880036e54f30 vm_start = 0x7ff6aa498000 ffff880036e54af8 vm_start = 0x7ff6aa497000 ffff88000e06aa20 vm_start = 0x7ff6aa499000 ffff88000e06ae58 vm_start = 0x7ff6ac1df000 ffff88000e06ba28 vm_start = 0x7ff6abefc000 ffff88000e06a6c0 vm_start = 0x7ff6ac41b000 ffff88001f2c4000 vm_start = 0x7ff6bac75000 ffff88000e06bd88 vm_start = 0x7ff6b2d00000 ffff88000e06b440 vm_start = 0x7ff6b28de000 ... ffff880074bfd6c8 vm_start = 0x7ff6bc206000 ffff88001f2c4510 vm_start = 0x7ffc7a5fc000 ffff88001f2c5b00 vm_start = 0x7ffc7a6d1000 Display a list of the page structs in the radix tree of an address_space structure located at ffff88012d364de0: crash> tree -t radix -r address_space.page_tree ffff88012d364de0 ffffea00040d12c0 ffffea00040d9a60 ffffea00040d9b08 ffffea000407eda8 ffffea0004084288 ... ffffea000407bc70 ffffea00040baf48 ffffea0004043f48 ffffea000407de58 Add the -p option to the command above to show position information: crash> tree -t radix -r address_space.page_tree ffff88012d364de0 -p ffffea00040d12c0 index: 0 position: root/0/0 ffffea00040d9a60 index: 1 position: root/0/1 ffffea00040d9b08 index: 2 position: root/0/2 ffffea000407eda8 index: 3 position: root/0/3 ffffea0004084288 index: 4 position: root/0/4 ... ffffea000407bc70 index: 217 position: root/3/25 ffffea00040baf48 index: 218 position: root/3/26 ffffea0004043f48 index: 219 position: root/3/27 ffffea000407de58 index: 220 position: root/3/28 Alternatively, take the address of the radix_tree_node from the radix_tree_root structure in the address_space structure above, and display the tree with the -N option: crash> struct address_space.page_tree ffff88012d364de0 page_tree = { height = 0x2, gfp_mask = 0x20, rnode = 0xffff8801238add71 } crash> tree -t radix -N 0xffff8801238add71 ffffea00040d12c0 ffffea00040d9a60 ffffea00040d9b08 ffffea000407eda8 ffffea0004084288 ffffea00040843a0 ... Using the same radix tree as above, display the flags and _count members of each page struct in the list, and force the output format to be hexadecimal: crash> tree -t radix -N 0xffff8801238add71 -s page.flags,_count -x ffffea00040d12c0 flags = 0x4000000002006c _count = { counter = 0x7 } ffffea00040d9a60 flags = 0x4000000002006c _count = { counter = 0x7 } ffffea00040d9b08 flags = 0x4000000002006c _count = { counter = 0x7 } ffffea000407eda8 flags = 0x4000000002006c _count = { counter = 0x7 } ... In more recent kernels, the XArray facility has replaced radix trees. Display a list of the page structs in the XArray of an address_space structure located at 0xffff94c235e76828, where the i_pages field is an embedded xarray structure: crash> tree -t xarray -r address_space.i_pages 0xffff94c235e76828 fffffcc005aa8380 fffffcc005cafa80 fffffcc005a79c80 fffffcc005ccad80 fffffcc005a72ec0 fffffcc005e27c00 fffffcc005ce3100 fffffcc005ff8dc0 fffffcc005c9a100 fffffcc005a49e40 fffffcc005c95a80 Add the -p option to the command above to show position information: crash> tree -t xarray -r address_space.i_pages 0xffff94c235e76828 -p fffffcc005aa8380 index: 90 position: root/1/26 fffffcc005cafa80 index: 91 position: root/1/27 fffffcc005a79c80 index: 92 position: root/1/28 fffffcc005ccad80 index: 93 position: root/1/29 fffffcc005a72ec0 index: 94 position: root/1/30 fffffcc005e27c00 index: 95 position: root/1/31 fffffcc005ce3100 index: 96 position: root/1/32 fffffcc005ff8dc0 index: 97 position: root/1/33 fffffcc005c9a100 index: 98 position: root/1/34 fffffcc005a49e40 index: 99 position: root/1/35 fffffcc005c95a80 index: 100 position: root/1/36 Alternatively, take the value found in the xa_head field from the xarray structure, and display the tree with the -N option: crash> address_space.i_pages 0xffff94c235e76828 i_pages = { ... [ xa_lock field not shown ] ... xa_flags = 1, xa_head = 0xffff94c23c1566ca } crash> tree -t x -N 0xffff94c23c1566ca fffffcc005aa8380 fffffcc005cafa80 fffffcc005a79c80 fffffcc005ccad80 fffffcc005a72ec0 fffffcc005e27c00 fffffcc005ce3100 fffffcc005ff8dc0 fffffcc005c9a100 fffffcc005a49e40 fffffcc005c95a80 Using the same xarray command as above, display the flags and _refcount members of each page struct in the list, and force the output format to be hexadecimal: crash> tree -t x -N 0xffff94c23c1566ca -s page.flags,_refcount -x fffffcc005aa8380 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } fffffcc005cafa80 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } fffffcc005a79c80 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } fffffcc005ccad80 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } fffffcc005a72ec0 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } fffffcc005e27c00 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } fffffcc005ce3100 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } fffffcc005ff8dc0 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } fffffcc005c9a100 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } fffffcc005a49e40 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } fffffcc005c95a80 flags = 0x57ffffc0000014 _refcount = { counter = 0x1 } The -v option is introduced specifically for dumping the complete content of maple tree: crash> tree -t maple 0xffff9034c006aec0 -v maple_tree(ffff9034c006aec0) flags 309, height 2 root 0xffff9034de70041e 0-18446744073709551615: node 0xffff9034de700400 depth 0 type 3 parent ... 0-140112331583487: node 0xffff9034c01e8800 depth 1 type 1 parent ... 0-94643156942847: 0x0 94643156942848-94643158024191: 0xffff9035131754c0 94643158024192-94643160117247: 0x0 ... The existing options can work as well for maple tree: crash> tree -t maple -r mm_struct.mm_mt 0xffff9034c006aec0 -p ffff9035131754c0 index: 1 position: root/0/1 ffff9035131751c8 index: 2 position: root/0/3 ffff9035131757b8 index: 3 position: root/0/4 ... crash> tree -t maple 0xffff9034c006aec0 -p -x -s vm_area_struct.vm_start,vm_end ffff9035131754c0 index: 1 position: root/0/1 vm_start = 0x5613d3c00000, vm_end = 0x5613d3d08000, ffff9035131751c8 index: 2 position: root/0/3 vm_start = 0x5613d3f07000, vm_end = 0x5613d3f0b000, ffff9035131757b8 index: 3 position: root/0/4 vm_start = 0x5613d3f0b000, vm_end = 0x5613d3f14000, ....