[Crash-utility] Adding a new command rbtree

[Dave Anderson]

----- Original Message -----
> At 2012-5-25 3:12, Dave Anderson wrote:
> > But again, the red-black tree dump should be similar to the radix tree
> > dump, and both of them should be similar to the "list" command. 
> Fixed. I misunderstood the address printed by list command. I thought I
> need to print the address of tree node.

You have fixed the red-black tree issue, but now it seems that the
radix tree dump no longer works.

As a verification of a red-black tree list, let's again take the list
of vm_area_structs that in a red-black list rooted at each mm_struct:

  crash> vm | head -3
  PID: 16041  TASK: ffff8100100187a0  CPU: 1   COMMAND: "crash"
         MM               PGD          RSS    TOTAL_VM
  ffff810039735ac0  ffff810001d8a000  111400k  190424k
  crash>

So the mm_struct address is ffff810039735ac0, its rb_root is 
at offset "-r mm_struct.mm_rb", and each rb_node in the list
can be found at the offset "-o vm_area_struct.vm_rb".  To 
verify, the "-s vm_area_struct.vm_mm" of each entry should 
point back to the mm_struct:

  crash> tree -t rb -r mm_struct.mm_rb -o vm_area_struct.vm_rb ffff810039735ac0 -s vm_area_struct.vm_mm
  ffff810039eedef8
    vm_mm = 0xffff810039735ac0
  ffff810024e06978
    vm_mm = 0xffff810039735ac0
  ffff8100065b61e8
    vm_mm = 0xffff810039735ac0
  ffff810005322e48
    vm_mm = 0xffff810039735ac0
  ffff81000468b818
    vm_mm = 0xffff810039735ac0
  ffff810025041d98
    vm_mm = 0xffff810039735ac0
  ... 
  
  
But in fixing red-black tree list, it seems that you have
broken radix tree lists, which worked OK in the previous patch.
The address_space.page_tree example that you use in the help page, 
and that I used in my last email, now fails.  For example, take an
address_space structure address of ffff81000d1edb88: 

  crash> vtop 400000 | tail -2
        PAGE       PHYSICAL      MAPPING       INDEX CNT FLAGS
  ffff8100009c4af8  d1e9000 ffff81000d1edb88        0  3 8080000000868
  crash>

Here is the radix_tree_root, and the topmost radix_tree_node:

  crash> address_space.page_tree ffff81000d1edb88
    page_tree = {
      height = 0x3, 
      gfp_mask = 0x220, 
      rnode = 0xffff81002ac43090
    }
  crash> kmem -s 0xffff81002ac43090
  CACHE            NAME                 OBJSIZE  ALLOCATED     TOTAL  SLABS  SSIZE
  ffff810037c8a200 radix_tree_node          536       3182      6405    915     4k
  SLAB              MEMORY            TOTAL  ALLOCATED  FREE
  ffff81002ac43040  ffff81002ac43090      7          4     3
  FREE / [ALLOCATED]
    [ffff81002ac43090]
  crash> 

It should dump its list of entries with the following command, but
which fails like so:
  
  crash> tree -t radix -r address_space.page_tree ffff81000d1edb88
  radix_tree_node at ffff81002ac43090
  struct radix_tree_node {
    count = 0x2, 
    slots = {0xffff8100197e8930, 0xffff810033bf9698, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x
  0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 
  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
    tags = {{0x0}, {0x0}}
  }
  tree: height 530 is greater than height_to_maxindex[]                   index 12
  crash> 
  
Dave