Re: [patch 5/6] radix-tree: gang set if tagged operation

[Andrew Morton <akpm@linux-foundation.org>]

On Wed, 10 Dec 2008 08:28:50 +0100
Nick Piggin <npiggin@suse.de> wrote:

> 
> Add a "radix_tree_gang_set_if_tagged" operation, which takes a range of indexes,
> and sets a given tag, if any of the specified tags were found to be set. Used by
> the next patch to set an "fsync" bit on any dirty and writeback pages.
> 

Spent 15 seconds trying to decode the above, quickly gave up.

Because it's the code comments which matter, not the changelog.

Only there are no code comemnts.  The rest of the radix-tree API is
documented.

> ---
>  include/linux/radix-tree.h |    1 
>  lib/radix-tree.c           |  107 +++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 108 insertions(+)
> 
> Index: linux-2.6/include/linux/radix-tree.h
> ===================================================================
> --- linux-2.6.orig/include/linux/radix-tree.h
> +++ linux-2.6/include/linux/radix-tree.h
> @@ -183,6 +183,7 @@ unsigned int
>  radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
>  		unsigned long first_index, unsigned int max_items,
>  		unsigned int tag);
> +int radix_tree_gang_tag_set_if_tagged(struct radix_tree_root *root, unsigned long first_index, unsigned long last_index, unsigned long ifset, unsigned long thentag);

aww, c'mon, that's just stupid.  167 columns.

>  int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
>  
>  static inline void radix_tree_preload_end(void)
> Index: linux-2.6/lib/radix-tree.c
> ===================================================================
> --- linux-2.6.orig/lib/radix-tree.c
> +++ linux-2.6/lib/radix-tree.c
> @@ -629,6 +629,113 @@ int radix_tree_tag_get(struct radix_tree
>  EXPORT_SYMBOL(radix_tree_tag_get);
>  #endif
>  
> +int node_tag_set_if_tagged(struct radix_tree_node *node, unsigned int height, unsigned long first_index, unsigned long last_index, unsigned long ifset, unsigned long thentag)

This identifier is global?

> +{
> +	unsigned long first, last;
> +	int offset_start, offset_end, i;
> +	int ret = 0;
> +	unsigned int shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
> +	unsigned int size = RADIX_TREE_MAP_SIZE << shift;
> +
> +	first = first_index;
> +	last = min(last_index, ((first + size) & ~(size-1)) - 1);
> +
> +	offset_start = (first_index >> shift) & RADIX_TREE_MAP_MASK;
> +	offset_end = (last_index >> shift) & RADIX_TREE_MAP_MASK;
> +	for (i = offset_start; i <= offset_end; i++) {
> +
> +		if (height > 1) {
> +			struct radix_tree_node *slot;
> +
> +			slot = node->slots[i];
> +			if (!slot)
> +				goto notset;
> +
> +			if (node_tag_set_if_tagged(slot, height - 1,
> +						first, last,
> +						ifset, thentag)) {

It's recursive.

Considerable effort has been made to avoid recursion in the radix-tree
code and here it gets added with nary a mention in the code or the
changelog.  It *at least* needs justification by showing a calculation
of the maximum stack usage.  Which is dependent upon the value of
RADIX_TREE_MAP_SHIFT and is hence a constraint upon it.

(I have a vague feeling that we broke the don't-recur design a while back, but
re-breaking it is still bad).


> +				if (ifset == 0x1)
> +					BUG_ON(!tag_get(node, 0, i));
> +				if (ifset == 0x2)
> +					BUG_ON(!tag_get(node, 1, i));
> +				if (ifset == 0x2)
> +					BUG_ON(!tag_get(node, 0, i) &&
> +						!tag_get(node, 1, i));
> +				if (thentag & 0x4) {
> +					if (!tag_get(node, 2, i))
> +						tag_set(node, 2, i);
> +				}
> +				ret = 1;
> +			}
> +notset:
> +			first = last+1;
> +			last = min(last_index, first + size - 1);
> +
> +		} else {
> +			if (ifset & 0x1) {
> +				if (tag_get(node, 0, i))
> +					goto isset;
> +			}
> +			if (ifset & 0x2) {
> +				if (tag_get(node, 1, i))
> +					goto isset;
> +			}
> +			continue;
> +isset:
> +			if (thentag & 0x4) {
> +				if (!tag_get(node, 2, i))
> +					tag_set(node, 2, i);
> +			}
> +			ret = 1;
> +		}
> +	}
> +
> +	return ret;
> +}
> +
> +int radix_tree_gang_tag_set_if_tagged(struct radix_tree_root *root, unsigned long first_index, unsigned long last_index, unsigned long ifset, unsigned long thentag)
> +{
> +	unsigned int height;
> +	struct radix_tree_node *slot;
> +
> +	BUG_ON(ifset & ~0x3);
> +	BUG_ON(thentag & ~0x4);

boggle.

So these things are mystery bitfields.  They need documentation!  The
code's not reviewable in this state.

afacit these two fields could have type `int' or `unsigned'?  No need
to add the additional overhead of 64-bit?


> +	height = root->height;
> +	if (height == 0) {
> +		/* set the root's tag bit */
> +		if (first_index != 0)
> +			return 0;
> +
> +		if (ifset & 0x1)
> +			if (root_tag_get(root, 0))
> +				goto isset;
> +		if (ifset & 0x2)
> +			if (root_tag_get(root, 1))
> +				goto isset;
> +		return 0;
> +isset:
> +		if (thentag & 0x4) {
> +			if (!root_tag_get(root, 2))
> +				root_tag_set(root, 2);
> +		}
> +		return 1;
> +	}
> +
> +	slot = radix_tree_indirect_to_ptr(root->rnode);
> +	if (node_tag_set_if_tagged(slot, height, first_index, last_index, ifset, thentag)) {
> +		/* set the root's tag bit */
> +		if (thentag & 0x4) {
> +			if (!root_tag_get(root, 2))
> +				root_tag_set(root, 2);
> +		}
> +
> +		return 1;
> +	}
> +
> +	return 0;
> +}

The rest of the radix-tree API is exported to modules, so this addition
should also be.