git: sbin/hammer: Fix boundary test on hammer show [2/3]

[Tomohiro Kusumi]

commit 6580f6422ff86ce3c7be21bd745e061cc8340edd
Author: Tomohiro Kusumi <kusumi.tomohiro at gmail.com>
Date:   Sun Aug 30 16:50:18 2015 +0900

    sbin/hammer: Fix boundary test on hammer show [2/3]
    
    get_elm_flags() using HAMMER_BTREE_TYPE_INTERNAL for btype
    of RBN of an internal node is not correct because btype of
    RBN is actually not specified. It could be internal or leaf
    or possibly 0, while RBN has no child regardless of the btype
    value.
    
    This results in get_elm_flags() having incorrect (but does
    not fail with 'B' mark) condition for left/right elm test
    for internal node. The correct way is to separate RBN case
    from non-RBN case. RBN logically has no child node (hammer
    erases child node offset with 0 on node split, if not zero
    clears the whole elm), so it can't be handled in the same
    switch(btype) cases like others are.
    
    Separating RBN from non-RBN (normal ELM) makes possible for
    each elm in an internal node to have correct left/right test.
    * non-RBN is the same as leaf node, so add test_lr() and
      use this in both internal and leaf node.
    * RBN needs to be handled differently, so add test_rbn_lr()
      and use this for RBN. The difference is that in RBN
      hammer_btree_cmp(&elm->base, right_bound) == 0
      could happen, so test_rbn_lr() can not set FLAG_TOOFARRIGHT
      when it's ==0. Below is some details on how this happens
      on RBN but not on non-RBN.
    
    ==========
    (A)
    This is what happens on internal split.
    
    before split
    I
    0 1 2 3 ...     n
    E E E E E E E E E R
               /
              /
             I                   62
             0 1 2 s ...       61|
             E E E E E E E E E E R
    
    after split
    I                 n+1
    0 1 2 3 ...   p   |
    E E E E E E E E E E R
               /   \
              /     \
             I       I           62-s-1
             0 1 2 s 0 1 2 ...   |
             E E E R=E E E E E E E R
    
    From the way hammer_split_internal() is implemented,
    E[p].base which points to the new child node is a copy of
    E[0].base in the new child node. Given that this E[0] is
    a copy of R(RBN) in the original child node (that was E[s]
    before internal split and was src of bcopy()), E[p].base
    also equals this R.base.
    
    Therefore
    hammer_btree_cmp(&elm->base, right_bound) == 0
    does happen for a right boundary elm where elm is R(RBN)
    and right_bound is &E[p].base. For non-RBN elms this is
    considered error for the same reason as leaf split case
    explained below.
    
    ==========
    (B)
    This is what happens on leaf split which is similar to above
    but not the same.
    before split
    I
    0 1 2 3 ...     n
    E E E E E E E E E R
               /
              /
             L
             0 1 2 s ...         62
             E E E E E E E E E E E
    
    after split
    I                 n+1
    0 1 2 3 ...   p   |
    E E E E E E E E E E R
               /   \
              /     \
             L       L             62-s-1
             0 1 2 s 0 1 2 ...     |
             E E E   E E E E E E E E
    
    hammer_leaf_split() basically does the same as internal,
    but the difference is that E[s] in the original child node
    does not become a boundary, nor does it point to a child.
    E[s] is just a junk space just like all the rest of the
    elms in the original child node.
    
    (Also leaf split tries to make E[p].base <= E[0].base of
    the new child node, instead of just copying E[0].base to
    E[p].base and make them equal like internal split does.
    See hammer_make_separator() for details.)
    
    This makes
    hammer_btree_cmp(&elm->base, right_bound) == 0
    not happen and considered error if it happens, where elm
    is either of E[0]..E[s-1] in the original child node and
    right_bound is &E[p].base.

Summary of changes:
 sbin/hammer/cmd_show.c | 79 +++++++++++++++++++++++++++++++-------------------
 1 file changed, 49 insertions(+), 30 deletions(-)

http://gitweb.dragonflybsd.org/dragonfly.git/commitdiff/6580f6422ff86ce3c7be21bd745e061cc8340edd


-- 
DragonFly BSD source repository