**diff options**

author | Nick Piggin <npiggin@kernel.dk> | 2012-05-29 15:07:34 -0700 |
---|---|---|

committer | Linus Torvalds <torvalds@linux-foundation.org> | 2012-05-29 16:22:33 -0700 |

commit | 5536805292e64393f57054de66578f17eb1ea994 (patch) | |

tree | d7c283b123fd1fa0a944b500aba31f01207a98fd /lib | |

parent | fd0a37355c4d39affa39d5cd75168fb94b292318 (diff) |

radix-tree: fix preload vector size

We are not preallocating a sufficient number of nodes.
Signed-off-by: Nick Piggin <npiggin@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

Diffstat (limited to 'lib')

-rw-r--r-- | lib/radix-tree.c | 15 |

1 files changed, 14 insertions, 1 deletions

diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 86516f5588e..d7c878cc006 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -73,11 +73,24 @@ static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly; static struct kmem_cache *radix_tree_node_cachep; /* + * The radix tree is variable-height, so an insert operation not only has + * to build the branch to its corresponding item, it also has to build the + * branch to existing items if the size has to be increased (by + * radix_tree_extend). + * + * The worst case is a zero height tree with just a single item at index 0, + * and then inserting an item at index ULONG_MAX. This requires 2 new branches + * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. + * Hence: + */ +#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1) + +/* * Per-cpu pool of preloaded nodes */ struct radix_tree_preload { int nr; - struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH]; + struct radix_tree_node *nodes[RADIX_TREE_PRELOAD_SIZE]; }; static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; |