linux-toradex.git/lib/radix-tree.c, branch v2.6.19.2

[PATCH] gfp annotations: radix_tree_root

2006-10-10T22:37:23+00:00

struct radix_tree_root has unused upper bits of ->gfp_mask reused for
tags bitmap.  Annotated.

Signed-off-by: Al Viro 
Signed-off-by: Linus Torvalds

[PATCH] radixtree: normalize radix_tree_tag_get() return value

2006-06-25T17:01:13+00:00

In radix_tree_tag_get(), return normalized value of 0/1, as indicated
by its comment.

Signed-off-by: Wu Fengguang 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] buglet in radix_tree_tag_set

2006-06-23T14:42:49+00:00

The comment states: 'Setting a tag on a not-present item is a BUG.' Hence
if 'index' is larger than the maxindex; the item _cannot_ be presen; it
should also be a BUG.

Also, this allows the following statement (assume a fresh tree):

  radix_tree_tag_set(root, 16, 1);

to fail silently, but when preceded by:

  radix_tree_insert(root, 32, item);

it would BUG, because the height has been extended by the insert.

In neither case was 16 present.

Signed-off-by: Peter Zijlstra 
Acked-by: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] radix-tree: small

2006-06-23T14:42:49+00:00

Reduce radix tree node memory usage by about a factor of 4 for small files
(< 64K).  There are pointer traversal and memory usage costs for large
files with dense pagecache.

Signed-off-by: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] radix-tree: direct data

2006-06-23T14:42:49+00:00

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: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] radix-tree documentation cleanups

2006-03-25T16:22:59+00:00

Documentation changes to help radix tree users avoid overrunning the tags
array.  RADIX_TREE_TAGS moves to linux/radix-tree.h and is now known as
RADIX_TREE_MAX_TAGS (Nick Piggin's idea).  Tag parameters are changed to
unsigned, and some comments are updated.

Signed-off-by: Jonathan Corbet 
Cc: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] Fix over-zealous tag clearing in radix_tree_delete

2006-02-16T16:45:50+00:00

If a tag is set for a node being deleted from a radix_tree, then that
tag gets cleared from the parent of the node, even if it is set for some
siblings of the node begin deleted.

This patch changes the logic to include a test for any_tag_set similar
to the logic a little futher down.  Care is taken to ensure that
'nr_cleared_tags' remains equals to the number of entries in the 'tags'
array which are set to '0' (which means that this tag is not set in the
tree below pathp->node, and should be cleared at pathp->node and
possibly above.

[ Nick says: "Linus FYI, I was able to modify the radix tree test
  harness to catch the bug and can no longer trigger it after the fix.
  Resulting code passes all other harness tests as well of course." ]

Signed-off-by: Neil Brown 
Acked-by: Nick Piggin 
Signed-off-by: Linus Torvalds

[PATCH] radix-tree: reduce tree height upon partial truncation

2006-01-09T04:13:41+00:00

Shrink the height of a radix tree when it is partially truncated - we only do
shrinkage of full truncation at present.

Signed-off-by: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] radix tree: early termination of tag clearing

2006-01-09T04:13:41+00:00

Correctly determine the tags to be cleared in radix_tree_delete() so we
don't keep moving up the tree clearing tags that we don't need to.  For
example, if a tag is simply not set in the deleted item, nor anywhere up
the tree, radix_tree_delete() would attempt to clear it up the entire
height of the tree.

Also, tag_set() was made conditional so as not to dirty too many cachelines
high up in the radix tree.  Instead, put this logic into
radix_tree_tag_set().

Signed-off-by: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] radix tree: code consolidation

2006-01-09T04:13:41+00:00

Introduce helper any_tag_set() rather than repeat the same code sequence 4
times.

Signed-off-by: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds