Re: RFC: radix tree safety

["Randy.Dunlap" <rdunlap@xenotime.net>]

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.
> 
> 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

> 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);


---
~Randy
You can't do anything without having to do something else first.
-- Belefant's Law
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/