diff options
| author | Andrew Morton <akpm@digeo.com> | 2002-12-14 03:17:21 -0800 |
|---|---|---|
| committer | Jaroslav Kysela <perex@suse.cz> | 2002-12-14 03:17:21 -0800 |
| commit | 7404e32c0f2dbd8cbca0126d7a46099ff1c4d57d (patch) | |
| tree | d21f20e290843e810f0b5fd9dd33430c78d64a69 /lib | |
| parent | 2134c9371b7612e0ee3ab449daa8b0e12ccf2df8 (diff) | |
| download | history-7404e32c0f2dbd8cbca0126d7a46099ff1c4d57d.tar.gz | |
[PATCH] handle overflows in radix_tree_gang_lookup()
Fix a radix-tree bug spotted by Vladimir Saveliev <vs@namesys.com>.
Each step in the radix tree spans six address bits. So a height=6 tree
spans 36-bits worth of nodes.
On 32-bit machines radix_tree_gang_lookup() doesn't handle this right -
at the 12TB mark it wraps back to zero, and returns pages at quite
wrong indices.
The patch fixes all that up, and tidies a couple of things.
A user-space test harness was developed so that the code can be sanely
tested. It is at
http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/radix-tree.c | 20 |
1 files changed, 9 insertions, 11 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c index dfa732c5998787..45935fe31b855a 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -196,8 +196,7 @@ EXPORT_SYMBOL(radix_tree_lookup); static /* inline */ unsigned int __lookup(struct radix_tree_root *root, void **results, unsigned long index, - unsigned int max_items, unsigned long *next_index, - unsigned long max_index) + unsigned int max_items, unsigned long *next_index) { unsigned int nr_found = 0; unsigned int shift; @@ -209,23 +208,21 @@ __lookup(struct radix_tree_root *root, void **results, unsigned long index, while (height > 0) { unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK; + for ( ; i < RADIX_TREE_MAP_SIZE; i++) { if (slot->slots[i] != NULL) break; index &= ~((1 << shift) - 1); index += 1 << shift; + if (index == 0) + goto out; /* 32-bit wraparound */ } if (i == RADIX_TREE_MAP_SIZE) goto out; height--; - shift -= RADIX_TREE_MAP_SHIFT; - if (height == 0) { - /* Bottom level: grab some items */ - unsigned long j; + if (height == 0) { /* Bottom level: grab some items */ + unsigned long j = index & RADIX_TREE_MAP_MASK; - BUG_ON((shift + RADIX_TREE_MAP_SHIFT) != 0); - - j = index & RADIX_TREE_MAP_MASK; for ( ; j < RADIX_TREE_MAP_SIZE; j++) { index++; if (slot->slots[j]) { @@ -235,6 +232,7 @@ __lookup(struct radix_tree_root *root, void **results, unsigned long index, } } } + shift -= RADIX_TREE_MAP_SHIFT; slot = slot->slots[i]; } out: @@ -281,9 +279,9 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results, if (cur_index > max_index) break; nr_found = __lookup(root, results + ret, cur_index, - max_items - ret, &next_index, max_index); + max_items - ret, &next_index); ret += nr_found; - if (next_index == max_index) + if (next_index == 0) break; cur_index = next_index; } |