aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/radix-tree.c21
1 files changed, 17 insertions, 4 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 0eee4020a7be..519d3f00ef9e 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -60,9 +60,14 @@ struct radix_tree_path {
60}; 60};
61 61
62#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) 62#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
63#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2) 63#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
64 RADIX_TREE_MAP_SHIFT))
64 65
65static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly; 66/*
67 * The height_to_maxindex array needs to be one deeper than the maximum
68 * path as height 0 holds only 1 entry.
69 */
70static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
66 71
67/* 72/*
68 * Radix tree node cache. 73 * Radix tree node cache.
@@ -492,7 +497,11 @@ EXPORT_SYMBOL(radix_tree_tag_set);
492void *radix_tree_tag_clear(struct radix_tree_root *root, 497void *radix_tree_tag_clear(struct radix_tree_root *root,
493 unsigned long index, unsigned int tag) 498 unsigned long index, unsigned int tag)
494{ 499{
495 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; 500 /*
501 * The radix tree path needs to be one longer than the maximum path
502 * since the "list" is null terminated.
503 */
504 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
496 struct radix_tree_node *slot = NULL; 505 struct radix_tree_node *slot = NULL;
497 unsigned int height, shift; 506 unsigned int height, shift;
498 507
@@ -934,7 +943,11 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
934 */ 943 */
935void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) 944void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
936{ 945{
937 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; 946 /*
947 * The radix tree path needs to be one longer than the maximum path
948 * since the "list" is null terminated.
949 */
950 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
938 struct radix_tree_node *slot = NULL; 951 struct radix_tree_node *slot = NULL;
939 struct radix_tree_node *to_free; 952 struct radix_tree_node *to_free;
940 unsigned int height, shift; 953 unsigned int height, shift;