RFC: radix tree safety
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);
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
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??
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
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 ;)
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
Quoted 2 lines · Nick Piggin
How about making the code self-documenting and more useful at the same
time: putRADIX_TREE_TAGSinradix-tree.h, and call itRADIX_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
@@ -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_treeint 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
Quoted 11 lines · Jonathan Corbet
Quoted 2 lines · Nick Piggin
How about making the code self-documenting and more useful at the same
time: putRADIX_TREE_TAGSinradix-tree.h, and call itRADIX_TREE_MAX_TAGSI 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_TAGSmoves tolinux/radix-tree.hand is now known asRADIX_TREE_MAX_TAGS(Nick Piggin's idea). Tag parameters are changed to unsigned, and some comments are updated.Signed-off-by Jonathan Corbet <[email protected]>
...
Signature · 2 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
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
Signed-off-by Jonathan Corbet <[email protected]>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