• Nick Piggin's avatar
    [PATCH] radix-tree: direct data · 612d6c19
    Nick Piggin authored
    The ability to have height 0 radix trees (a direct pointer to the data item
    rather than going through a full node->slot) quietly disappeared with
    old-2.6-bkcvs commit ffee171812d51652f9ba284302d9e5c5cc14bdfd.  On 64-bit
    machines this causes nearly 600 bytes to be used for every <= 4K file in
    pagecache.
    
    Re-introduce this feature, root tags stored in spare ->gfp_mask bits.
    
    Simplify radix_tree_delete's complex tag clearing arrangement (which would
    become even more complex) by just falling back to tag clearing functions
    (the pagecache radix-tree never uses this path anyway, so the icache
    savings will mean it's actually a speedup).
    
    On my 4GB G5, this saves 8MB RAM per kernel kernel source+object tree in
    pagecache.
    
    Pagecache lookup, insertion, and removal speed for small files will also be
    improved.
    
    This makes RCU radix tree harder, but it's worth it.
    Signed-off-by: default avatarNick Piggin <npiggin@suse.de>
    Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
    612d6c19
radix-tree.c 21.5 KB