public inbox for linux-kernel@vger.kernel.org
 help / color / mirror / Atom feed
* RFC: radix tree safety
@ 2006-03-13 22:43 Jonathan Corbet
  2006-03-13 22:55 ` Nick Piggin
  2006-03-13 23:03 ` Randy.Dunlap
  0 siblings, 2 replies; 9+ messages in thread
From: Jonathan Corbet @ 2006-03-13 22:43 UTC (permalink / raw)
  To: linux-kernel

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

Signed-off-by: Jonathan Corbet <corbet@lwn.net>

--- 2.6.16-rc6/lib/radix-tree.c.orig	2006-03-13 14:42:48.000000000 -0700
+++ 2.6.16-rc6/lib/radix-tree.c	2006-03-13 15:33:35.000000000 -0700
@@ -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);

^ permalink raw reply	[flat|nested] 9+ messages in thread
end of thread, other threads:[~2006-03-17  0:42 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2006-03-13 22:43 RFC: radix tree safety Jonathan Corbet
2006-03-13 22:55 ` Nick Piggin
2006-03-13 23:50   ` Andrew Morton
2006-03-14  0:01     ` Jonathan Corbet
2006-03-14  0:14       ` Andrew Morton
2006-03-14  5:24         ` Nick Piggin
2006-03-16 17:13           ` Jonathan Corbet
2006-03-17  0:41             ` Nick Piggin
2006-03-13 23:03 ` Randy.Dunlap

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox