On Fri, 4 Jun 2010 20:40:53 +0200
Jan Kara <jack@xxxxxxx> wrote:
> Implement function for setting one tag if another tag is set
> for each item in given range.
>
>
> ...
>
> /**
> + * radix_tree_gang_tag_if_tagged - for each item in given range set given
> + * tag if item has another tag set
> + * @root: radix tree root
> + * @first_index: starting index of a range to scan
> + * @last_index: last index of a range to scan
> + * @iftag: tag index to test
> + * @settag: tag index to set if tested tag is set
> + *
> + * This function scans range of radix tree from first_index to last_index.
> + * For each item in the range if iftag is set, the function sets also
> + * settag.
> + *
> + * The function returns number of leaves where the tag was set.
> + */
> +unsigned long radix_tree_gang_tag_if_tagged(struct radix_tree_root *root,
> + unsigned long first_index, unsigned long last_index,
> + unsigned int iftag, unsigned int settag)
This is kind of a misuse of the term "gang".
First we had radix_tree_lookup(), which returned a single page.
That was a bit inefficient, so then we added radix_tree_gang_lookup(),
which retuned a "gang" of pages.
But radix_tree_gang_tag_if_tagged() doesn't return a gang of anything
(it has no `void **results' argument).
radix_tree_range_tag_if_tagged()?
> +{
> + unsigned int height = root->height, shift;
> + unsigned long tagged = 0, index = first_index;
> + struct radix_tree_node *open_slots[height], *slot;
> +
> + last_index = min(last_index, radix_tree_maxindex(height));
> + if (first_index > last_index)
> + return 0;
> + if (!root_tag_get(root, iftag))
> + return 0;
> + if (height == 0) {
> + root_tag_set(root, settag);
> + return 1;
> + }
> +
> + shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
> + slot = radix_tree_indirect_to_ptr(root->rnode);
> +
> + for (;;) {
> + int offset;
> +
> + offset = (index >> shift) & RADIX_TREE_MAP_MASK;
> + if (!slot->slots[offset])
> + goto next;
> + if (!tag_get(slot, iftag, offset))
> + goto next;
> + tag_set(slot, settag, offset);
> + if (height == 1) {
> + tagged++;
> + goto next;
> + }
> + /* Go down one level */
> + height--;
> + shift -= RADIX_TREE_MAP_SHIFT;
> + open_slots[height] = slot;
> + slot = slot->slots[offset];
> + continue;
> +next:
> + /* Go to next item at level determined by 'shift' */
> + index = ((index >> shift) + 1) << shift;
> + if (index > last_index)
> + break;
> + while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) {
> + /*
> + * We've fully scanned this node. Go up. Because
> + * last_index is guaranteed to be in the tree, what
> + * we do below cannot wander astray.
> + */
> + slot = open_slots[height];
> + height++;
> + shift += RADIX_TREE_MAP_SHIFT;
> + }
> + }
> + /*
> + * The iftag must have been set somewhere because otherwise
> + * we would return immediated at the beginning of the function
> + */
> + root_tag_set(root, settag);
> +
> + return tagged;
> +}
> +EXPORT_SYMBOL(radix_tree_gang_tag_if_tagged);
Wouldn't this be a lot simpler if it used __lookup_tag()? Along the
lines of
do {
slot *slots[N];
n = __lookup_tag(.., slots, ...);
for (i = 0; i < n; i++)
tag_set(slots[i], ...);
} while (something);
?
That's still one cache miss per slot and misses on the slots will
preponderate, so the performance won't be much different.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxxx For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>