-
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