Skip to contentSkip to conversation

RFC: radix tree safety

PATCH Jonathan Corbet 4 participants 9 messages Mar 13, 2006 – Mar 17, 2006 Library code

lore
Share & tools
lore
#0 lore raw

I've been digging through the radix tree code, and I noticed that the tag functions have an interesting limitation. The tag is given as an integer value, but, in reality, the only values that work are zero and one. Anything else will return random results or (when setting tags) corrupt unrelated memory.

The number of radix tree users is small, so it's not hard to confirm that all tag values currently in use are legal. But the interface would seem to invite mistakes.

The following patch puts in checks for out-of-range tag values. I've elected to have the relevant call fail; one could argue that it should BUG instead. Either seems better than silently doing weird stuff. Not 2.6.16 material, obviously, but maybe suitable thereafter.

jon

lib/radix-tree.c renamed from lib/radix-tree.c.orig +11 -0
@@ -364,6 +364,8 @@ void *radix_tree_tag_set(struct radix_tr
 	height = root->height;
 	if (index > radix_tree_maxindex(height))
 		return NULL;
+	if (tag < 0 || tag >= RADIX_TREE_TAGS)
+		return NULL;
 
 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 	slot = root->rnode;
@@ -408,6 +410,8 @@ void *radix_tree_tag_clear(struct radix_
 	height = root->height;
 	if (index > radix_tree_maxindex(height))
 		goto out;
+	if (tag < 0 || tag >= RADIX_TREE_TAGS)
+		goto out;
 
 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 	pathp->node = NULL;
@@ -468,6 +472,8 @@ int radix_tree_tag_get(struct radix_tree
 	height = root->height;
 	if (index > radix_tree_maxindex(height))
 		return 0;
+	if (tag < 0 || tag >= RADIX_TREE_TAGS)
+		return 0;
 
 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 	slot = root->rnode;
@@ -660,6 +666,9 @@ radix_tree_gang_lookup_tag(struct radix_
 	unsigned long cur_index = first_index;
 	unsigned int ret = 0;
 
+	if (tag < 0 || tag >= RADIX_TREE_TAGS)
+		return 0;
+
 	while (ret < max_items) {
 		unsigned int nr_found;
 		unsigned long next_index;	/* Index of next search */
@@ -807,6 +816,8 @@ int radix_tree_tagged(struct radix_tree_
   	rnode = root->rnode;
   	if (!rnode)
   		return 0;
+	if (tag < 0 || tag >= RADIX_TREE_TAGS)
+		return 0;
 	return any_tag_set(rnode, tag);
 }
 EXPORT_SYMBOL(radix_tree_tagged);
#1 lore raw
Quoted 6 lines · Jonathan Corbet

I've been digging through the radix tree code, and I noticed that the tag functions have an interesting limitation. The tag is given as an integer value, but, in reality, the only values that work are zero and one. Anything else will return random results or (when setting tags) corrupt unrelated memory.

Quoted 10 lines

The number of radix tree users is small, so it's not hard to confirm that all tag values currently in use are legal. But the interface would seem to invite mistakes.

The following patch puts in checks for out-of-range tag values. I've elected to have the relevant call fail; one could argue that it should BUG instead. Either seems better than silently doing weird stuff. Not 2.6.16 material, obviously, but maybe suitable thereafter.

I'd agree if you make them BUG_ON()s.

Andrew Morton's kind of the radix-tree tags guy though... Andrew?

Nick

Send instant messages to your online friends http://au.messenger.yahoo.com

#2 lore raw
Quoted 8 lines · Nick Piggin
Quoted 5 lines · Jonathan Corbet

I've been digging through the radix tree code, and I noticed that the tag functions have an interesting limitation. The tag is given as an integer value, but, in reality, the only values that work are zero and one. Anything else will return random results or (when setting tags) corrupt unrelated memory.

Various people at various times have added additional tags. reiser4...

Quoted 11 lines
Quoted 10 lines

The number of radix tree users is small, so it's not hard to confirm that all tag values currently in use are legal. But the interface would seem to invite mistakes.

The following patch puts in checks for out-of-range tag values. I've elected to have the relevant call fail; one could argue that it should BUG instead. Either seems better than silently doing weird stuff. Not 2.6.16 material, obviously, but maybe suitable thereafter.

Quoted 3 lines

I'd agree if you make them BUG_ON()s.

Andrew Morton's kind of the radix-tree tags guy though... Andrew?

I don't really see the need - if someone goes and overindexes the data structure's capacity then they have a bug and hopefully that'll turn up in testing and will get fixed.

Or am I missing something obvious which makes radix-trees particularly dangerous or subtle??

#3 lore raw
Quoted 6 lines · Andrew Morton

I don't really see the need - if someone goes and overindexes the data structure's capacity then they have a bug and hopefully that'll turn up in testing and will get fixed.

Or am I missing something obvious which makes radix-trees particularly dangerous or subtle??

There's nothing in the interface documentation which says that a tag is an index to anything. It's an integer value which can be attached to an item in a radix tree. One has to look into the source to see the limitation built into it.

If we don't want the tests, fine, but it might make sense to fix the interface documentation, at least, to note that "tag" is not an arbitrary integer value.

jon

#4 lore raw
Quoted 10 lines · [email protected] (Jonathan Corbet) wrote:
Quoted 6 lines · Andrew Morton

I don't really see the need - if someone goes and overindexes the data structure's capacity then they have a bug and hopefully that'll turn up in testing and will get fixed.

Or am I missing something obvious which makes radix-trees particularly dangerous or subtle??

Quoted 9 lines

There's nothing in the interface documentation which says that a tag is an index to anything. It's an integer value which can be attached to an item in a radix tree. One has to look into the source to see the limitation built into it.

If we don't want the tests, fine, but it might make sense to fix the interface documentation, at least, to note that "tag" is not an arbitrary integer value.

Sure, we can live with the runtime cost of a documentation fix ;)

#5 lore raw
Quoted 9 lines · Andrew Morton
Quoted 4 lines · [email protected] (Jonathan Corbet) wrote:

If we don't want the tests, fine, but it might make sense to fix the interface documentation, at least, to note that "tag" is not an arbitrary integer value.

Sure, we can live with the runtime cost of a documentation fix ;)

How about making the code self-documenting and more useful at the same
time: put RADIX_TREE_TAGS in radix-tree.h, and call it RADIX_TREE_MAX_TAGS

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
#6 lore raw
Quoted 2 lines · Nick Piggin

How about making the code self-documenting and more useful at the same
time: put RADIX_TREE_TAGS in radix-tree.h, and call it RADIX_TREE_MAX_TAGS

I like that idea - how's the following? I also took the liberty of making the tag arguments be unsigned, since that is clearly the way they are intended to be used.

jon

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.

include/linux/radix-tree.h +8 -5
diff -urNp -X 2.6.16-rc6/Documentation/dontdiff 2.6.16-rc6/include/linux/radix-tree.h 2.6.16-rc6-rtree/include/linux/radix-tree.h
@@ -45,6 +45,8 @@ do {									\
 	(root)->rnode = NULL;						\
 } while (0)
 
+#define RADIX_TREE_MAX_TAGS 2
+
 int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
@@ -55,15 +57,16 @@ radix_tree_gang_lookup(struct radix_tree
 int radix_tree_preload(gfp_t gfp_mask);
 void radix_tree_init(void);
 void *radix_tree_tag_set(struct radix_tree_root *root,
-			unsigned long index, int tag);
+			unsigned long index, unsigned int tag);
 void *radix_tree_tag_clear(struct radix_tree_root *root,
-			unsigned long index, int tag);
+			unsigned long index, unsigned int tag);
 int radix_tree_tag_get(struct radix_tree_root *root,
-			unsigned long index, int tag);
+			unsigned long index, unsigned int tag);
 unsigned int
 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
-		unsigned long first_index, unsigned int max_items, int tag);
-int radix_tree_tagged(struct radix_tree_root *root, int tag);
+		unsigned long first_index, unsigned int max_items,
+		unsigned int tag);
+int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
 
 static inline void radix_tree_preload_end(void)
 {
lib/radix-tree.c +27 -22

177 lines not on this page · raw message

#7 lore raw
Quoted 11 lines · Jonathan Corbet
Quoted 2 lines · Nick Piggin

How about making the code self-documenting and more useful at the same
time: put RADIX_TREE_TAGS in radix-tree.h, and call it RADIX_TREE_MAX_TAGS

I like that idea - how's the following? I also took the liberty of making the tag arguments be unsigned, since that is clearly the way they are intended to be used.

Looks really good. Andrew will you pick it up?

Quoted 9 lines

jon

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.

...

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
#8 lore raw
In reply to Jonathan Corbet
Quoted 6 lines · On Mon, 13 Mar 2006 15:43:44 -0700 Jonathan Corbet wrote:

I've been digging through the radix tree code, and I noticed that the tag functions have an interesting limitation. The tag is given as an integer value, but, in reality, the only values that work are zero and one. Anything else will return random results or (when setting tags) corrupt unrelated memory.

Quoted 8 lines

The number of radix tree users is small, so it's not hard to confirm that all tag values currently in use are legal. But the interface would seem to invite mistakes.

The following patch puts in checks for out-of-range tag values. I've elected to have the relevant call fail; one could argue that it should BUG instead. Either seems better than silently doing weird stuff. Not 2.6.16 material, obviously, but maybe suitable thereafter.

or a typedef like gfp_flags

Quoted 44 lines

jon

lib/radix-tree.c renamed from lib/radix-tree.c.orig +9 -0
@@ -364,6 +364,8 @@ void *radix_tree_tag_set(struct radix_tr
 	height = root->height;
 	if (index > radix_tree_maxindex(height))
 		return NULL;
+	if (tag < 0 || tag >= RADIX_TREE_TAGS)
+		return NULL;
 
 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 	slot = root->rnode;
@@ -408,6 +410,8 @@ void *radix_tree_tag_clear(struct radix_
 	height = root->height;
 	if (index > radix_tree_maxindex(height))
 		goto out;
+	if (tag < 0 || tag >= RADIX_TREE_TAGS)
+		goto out;
 
 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 	pathp->node = NULL;
@@ -468,6 +472,8 @@ int radix_tree_tag_get(struct radix_tree
 	height = root->height;
 	if (index > radix_tree_maxindex(height))
 		return 0;
+	if (tag < 0 || tag >= RADIX_TREE_TAGS)
+		return 0;
 
 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 	slot = root->rnode;
@@ -660,6 +666,9 @@ radix_tree_gang_lookup_tag(struct radix_
 	unsigned long cur_index = first_index;
 	unsigned int ret = 0;
 
+	if (tag < 0 || tag >= RADIX_TREE_TAGS)
+		return 0;
+
 	while (ret < max_items) {
 		unsigned int nr_found;
 		unsigned long next_index;	/* Index of next search */

lib/radix-tree.c int radix_tree_tagged(struct radix_tree_ · line 823

Quoted 8 lines
lib/radix-tree.c renamed from lib/radix-tree.c.orig +2 -0
@@ -807,6 +816,8 @@ int radix_tree_tagged(struct radix_tree_
   	rnode = root->rnode;
   	if (!rnode)
   		return 0;
+	if (tag < 0 || tag >= RADIX_TREE_TAGS)
+		return 0;
 	return any_tag_set(rnode, tag);
 }
 EXPORT_SYMBOL(radix_tree_tagged);

---
~Randy
You can't do anything without having to do something else first. -- Belefant's Law