[Crash-utility] Adding a new command rbtree

[Dave Anderson]

----- Original Message -----
> At 2012-5-30 22:53, Dave Anderson wrote:
> > Do you even test these patches before posting them?
> 
> Sorry. I made a patch, and after it was tested, I rework it and forget
> to test it again. It's all my fault that made so much trouble to you.  I
> apologize for it.

No problem... 

OK, so here is my current test matrix and results:

(1) tree -t rbtree -r mm_struct.mm_rb -o vm_area_struct.vm_rb <root> 

    RHEL5: OK
    RHEL6: OK
    Fedora: OK 

(2) tree -t rbtree -o vm_area_struct.vm_rb -N <node>

    RHEL5: OK
    RHEL6: OK
    Fedora: OK 

(3) tree -t radix -r address_space.page_tree <root>

    RHEL5: OK
    RHEL6: OK
    Fedora: OK

(4) tree -t radix -N <node>

    RHEL5: OK (not supported)   
    RHEL6: OK (note caveat below)
    Fedora: OK (note caveat below)

Caveat: for newer kernels that support -N for radix trees, a user might
run into a situation where the radix_tree_node pointer has the "1-bit"
set, and the node address is just cut-and-pasted.  For example:

  crash> address_space.page_tree ffff88000990e5e0
    page_tree = {
      height = 3, 
      gfp_mask = 32, 
      rnode = 0xffff880004682281
    }
  crash> tree -t radix -N 0xffff880004682281
  radix_tree_node at ffff880004682281
  struct radix_tree_node {
    height = 0x2000000, 
    count = 0xb8000000, 
    rcu_head = {
      next = 0x40ffff8800046824, 
      func = 0x70ffffffff812700
    }, 
    slots = {0x50ffff880017202d, 0xffff88003d60d0, 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, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
    tags = {{0x0}, {0x0}, {0x100000000000000}}
  }
  tree: height 33554432 is greater than height_to_maxindex[] index 12
  crash>

I forget what the usage of the low-bit means w/respect to
radix_tree_node pointers (?), but you've already got this in
place in your do_rdtree() function:

        if (node_p & 1)
                node_p &= ~1;

and I remember having to do the same thing in the currently
existing radix_tree_lookup() function.
    
So I believe that the 1-bit should be stripped off when a user
inadvertently enters such an address as a -N radix_tree_node address.  
With this change to cmd_tree(): 

        if (hexadecimal_only(args[optind], 0)) {
                value = htol(args[optind], FAULT_ON_ERROR, NULL);
                if (IS_KVADDR(value)) {
                        td->start = value;
+                       if ((td->start & 1) &&
+                           (td->flags & TREE_NODE_POINTER) &&
+                           (type_flag == RADIXTREE_REQUEST))
+                               td->start &= ~1;
                        goto next_arg;
                }
        }

it works OK regardless of the 1-bit setting:
  
  crash> address_space.page_tree ffff88000990e5e0
    page_tree = {
      height = 3, 
      gfp_mask = 32, 
      rnode = 0xffff880022c1ab41
    }
  crash> tree -t radix -N 0xffff880022c1ab41 
  ffffea0000327e28
  ffffea00002ee0d8
  ffffea00002ee110
  ...
  crash> tree -t radix -N 0xffff880022c1ab40 
  ffffea0000327e28
  ffffea00002ee0d8
  ffffea00002ee110
  ...
  
I haven't tinkered with the -p option, although I don't think that it's
a particularly important option.  I may add a couple more error-handling
additions, and perhaps some slight user interface changes, and the help
page needs to be cleaned-up/clarified.  But aside from that, this is 
looking pretty good for inclusion in crash-6.0.8.

No further patch posting is required unless you find a new bug or other
problem -- nice job!

Thanks,
  Dave