[Crash-utility] Adding a new command rbtree

[Dave Anderson]

----- Original Message -----
 
> I still add "-N" option to make it possible to start from node.

Hello Qiao,

We're getting closer, but there is still a problem with red-black
tree dumps.
  
For this command to be useful, the "tree" command should do what the 
"list" command does when dumping a list of structures that have embedded
list_head members -- which is to dump the addresses of the data structures
in the list. 

In the case of radix tree lists, your patch does the right thing, which
is to dump the addresses of the items found in the lowest radix_tree_node 
slots[] array.  Taking an address_space address of ffff8805f5a73580, the 
address_space.page_tree radix tree dump shows the page struct addresses, 
and therefore the "-s page.mapping" option works -- confirming that each 
page struct has a reference back to the address_space:

  crash> tree -t radix -r address_space.page_tree ffff8805f5a73580 -s page.mapping
  ffffea00178472c0
    mapping = 0xffff8805f5a73580
  ffffea0017869240
    mapping = 0xffff8805f5a73580
  ffffea0017869280
    mapping = 0xffff8805f5a73580
  ffffea00178692c0
    mapping = 0xffff8805f5a73580
  ffffea0017869300
    mapping = 0xffff8805f5a73580
  ffffea0017869340
    mapping = 0xffff8805f5a73580
  ffffea0017869380
  ...

But in the case of red-black trees, your patch is not consistent, because
it dumps the addresses of the embedded rb_node structure in each data 
structure in the list.  A user would typically want to see the addresses 
of the containing data structure, *not* the embedded rb_node addresses.

For example, suppose we want to see the list of vm_area_structs that 
are members of the red-black tree whose root is in an mm_struct.  Using
your latest patch, this is what I see, where the mm_struct address
is ffff880828163180:

  crash> vm | head -3
  PID: 8426   TASK: ffff88042bd9cd00  CPU: 3   COMMAND: "crash"
         MM               PGD          RSS    TOTAL_VM
  ffff880828163180  ffff880828f7a000  193048k  344404k 
  crash>
  
Therefore, this command should dump the address of each vm_area_struct 
in the tree:

  crash> tree -t rb -r mm_struct.mm_rb -o vm_area_struct.vm_rb ffff880828163180 
  ffff880828a82d80
  ffff880828a82798
  ffff880828a83758
  ffff880828a81bc8
  ffff880828a83560
  ffff880828a821b0
  ffff88081c5a57d8
  ffff88081c5a7170
  ffff880828a80038
  ffff880828a80230
  ...

However, the addresses above are the addresses of the vm_area_struct.vm_rb 
rb_node members -- not the addresses of the containing vm_area_structs.
Confusing the issue even more, if I remove the "-o vm_area_struct.vm_rb" 
option from the command line, I see the exact same output as above:

  crash> tree -t rb -r mm_struct.mm_rb ffff880828163180
  ffff880828a82d80
  ffff880828a82798
  ffff880828a83758
  ffff880828a81bc8
  ffff880828a83560
  ffff880828a821b0
  ffff88081c5a57d8
  ffff88081c5a7170
  ffff880828a80038
  ffff880828a80230
  ...

For red-black trees, the "-o offset" option is always required unless 
the rb_node member in the containing data structure has a member 
offset of 0.

And presuming that I want a list of vm_area_struct addresses, your patch
doesn't do that.

I do note that "-s struct[.member,member]" will work correctly if 
the "-o vm_area_struct.vm_rb" is applied, so you're on the right track.

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.

Another minor nit -- you should disallow the usage of "-o offset" when 
a radix tree is being dumped.  Although your patch apparently ignores it,
it should display an error message and fail the command.

Thanks,
  Dave