From mboxrd@z Thu Jan 1 00:00:00 1970 From: Nick Piggin Subject: [patch 5/6] radix-tree: gang set if tagged operation Date: Wed, 10 Dec 2008 08:28:50 +0100 Message-ID: <20081210072850.GF27096@wotan.suse.de> References: <20081210072454.GB27096@wotan.suse.de> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii To: Andrew Morton , linux-fsdevel@vger.kernel.org, Mikulas Patocka Return-path: Received: from mx2.suse.de ([195.135.220.15]:59344 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754372AbYLJH2v (ORCPT ); Wed, 10 Dec 2008 02:28:51 -0500 Content-Disposition: inline In-Reply-To: <20081210072454.GB27096@wotan.suse.de> Sender: linux-fsdevel-owner@vger.kernel.org List-ID: 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. Signed-off-by: Nick Piggin --- 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); 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) +{ + 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)) { + 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); + + 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; +} + /** * radix_tree_next_hole - find the next hole (not-present entry) * @root: tree root