• Andrew Morton's avatar
    [PATCH] radix-tree tags for selective lookup · 8691fb83
    Andrew Morton authored
    Add radix-tree tagging so we can look up dirty or writeback pages in
    O(log64(n)) time.
    
    Each radix-tree node gains two bits for each slot: one for page dirtiness and
    one for page writebackness.
    
    If a tag bit is set on a leaf node, it indicates that item at the
    corresponding slot is tagged (say, a dirty page).
    
    If a tag bit is set in a non-leaf node it indicates that the same tag bit is
    set in the subtree which lies under the corresponding slot.  ie: "there is a
    dirty page under here somewhere, but you need to search down further to find
    it".
    
    A gang lookup function is provided which can walk the radix tree in
    logarithmic time looking for items which are tagged, starting from a
    specified offset.  We use this for in-order searches for dirty or writeback
    pages.
    
    There is a userspace test harness for this code at
    
    http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz
    8691fb83
radix-tree.c 19.7 KB