• Andrew Morton's avatar
    [PATCH] radix-tree reinitialisation fix · ca22d5dd
    Andrew Morton authored
    This patch fixes a problem which was discovered by Vladimir Saveliev
    <vs@namesys.com>
    
    Radix trees have a `height' field, which defines how far the pages are
    from the root of the tree.  It starts out at zero and increases as the
    trees depth is grown.
    
    But it is never decreased.  It cannot be decreased without a full tree
    traversal.
    
    Because radix_tree_delete() does not decrease `height', we end up
    returning inodes to their filesystem's inode slab cache with a non-zero
    height.
    
    And when that inode is reused from slab for a new file, it still has a
    non-zero height.  So we're breaking the slab rules by not putting
    objects back in a fully reinitialised state.
    
    So the new file starts out life with whatever height the previous owner
    of the inode had.  Which is space- and speed-inefficient.
    
    The most efficient place to fix this would be in destroy_inode().  But
    that only fixes the problem for inodes - there are other users of radix
    trees.
    
    So fix it in radix_tree_delete(): if the tree was emptied, reset
    `height' to zero.
    ca22d5dd
radix-tree.c 9.2 KB