lkml.org 
[lkml]   [2011]   [Dec]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH] radix_tree: take radix_tree_path off stack


    On 2011年12月19日 14:41, Hugh Dickins wrote:
    > Down, down in the deepest depths of GFP_NOIO page reclaim, we have
    > shrink_page_list() calling __remove_mapping() calling __delete_from_
    > swap_cache() or __delete_from_page_cache().
    >
    > You would not expect those to need much stack, but in fact they call
    > radix_tree_delete(): which declares a 192-byte radix_tree_path array
    > on its stack (to record the node,offsets it visits when descending,
    > in case it needs to ascend to update them). And if any tag is still
    > set [1], that calls radix_tree_tag_clear(), which declares a further
    > such 192-byte radix_tree_path array on the stack. (At least we have
    > interrupts disabled here, so won't then be pushing registers too.)
    >
    > That was probably a good choice when most users were 32-bit (array
    > of half the size), and adding fields to radix_tree_node would have
    > bloated it unnecessarily. But nowadays many are 64-bit, and each
    > radix_tree_node contains a struct rcu_head, which is only used when

    Can rcu_head in someway unionized with radix_tree_node->height
    and radix_tree_node->count? count is always referenced under lock
    and only the first node's height is referenced during lookup.
    Seems like if we atomically set root->rnode to NULL, before
    freeing the last node, we can ensure a valid read of the
    radix_tree_node->height when lookup by following it with
    a root->rnode == NULL test.

    I am not very sure of course, just a naive feeling.


    > freeing; whereas the radix_tree_path info is only used for updating
    > the tree (deleting, clearing tags or setting tags if tagged) when a
    > lock must be held, of no interest when accessing the tree locklessly.
    >
    > So add a parent pointer to the radix_tree_node, in union with the
    > rcu_head, and remove all uses of the radix_tree_path. There would
    > be space in that union to save the offset when descending as before
    > (we can argue that a lock must already be held to exclude other users),
    > but recalculating it when ascending is both easy (a constant shift and
    > a constant mask) and uncommon, so it seems better just to do that.
    >
    > Two little optimizations: no need to decrement height when descending,
    > adjusting shift is enough; and once radix_tree_tag_if_tagged() has set
    > tag on a node and its ancestors, it need not ascend from that node again.
    >
    > perf on the radix tree test harness reports radix_tree_insert() as 2%
    > slower (now having to set parent), but radix_tree_delete() 24% faster.
    > Surely that's an exaggeration from rtth's artificially low map shift 3,
    > but forcing it back to 6 still rates radix_tree_delete() 8% faster.
    >
    > [1] Can a pagecache tag (dirty, writeback or towrite) actually still be
    > set at the time of radix_tree_delete()? Perhaps not if the filesystem
    > is well-behaved. But although I've not tracked any stack overflow down
    > to this cause, I have observed a curious case in which a dirty tag is
    > set and left set on tmpfs: page migration's migrate_page_copy() happens
    > to use __set_page_dirty_nobuffers() to set PageDirty on the newpage,
    > and that sets PAGECACHE_TAG_DIRTY as a side-effect - harmless to a
    > filesystem which doesn't use tags, except for this stack depth issue.
    >
    > Signed-off-by: Hugh Dickins<hughd@google.com>
    > ----
    >
    > lib/radix-tree.c | 148 +++++++++++++++++++++------------------------
    > 1 file changed, 70 insertions(+), 78 deletions(-)
    >
    > --- 3.2-rc6/lib/radix-tree.c 2011-11-07 19:24:53.342418579 -0800
    > +++ linux/lib/radix-tree.c 2011-12-16 20:40:26.152758485 -0800
    > @@ -48,16 +48,14 @@
    > struct radix_tree_node {
    > unsigned int height; /* Height from the bottom */
    > unsigned int count;
    > - struct rcu_head rcu_head;
    > + union {
    > + struct radix_tree_node *parent; /* Used when ascending tree */
    > + struct rcu_head rcu_head; /* Used when freeing node */
    > + };
    > void __rcu *slots[RADIX_TREE_MAP_SIZE];
    > unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
    > };
    >
    > -struct radix_tree_path {
    > - struct radix_tree_node *node;
    > - int offset;
    > -};
    > -
    > #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
    > #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
    > RADIX_TREE_MAP_SHIFT))
    > @@ -256,6 +254,7 @@ static inline unsigned long radix_tree_m
    > static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
    > {
    > struct radix_tree_node *node;
    > + struct radix_tree_node *slot;
    > unsigned int height;
    > int tag;
    >
    > @@ -274,18 +273,23 @@ static int radix_tree_extend(struct radi
    > if (!(node = radix_tree_node_alloc(root)))
    > return -ENOMEM;
    >
    > - /* Increase the height. */
    > - node->slots[0] = indirect_to_ptr(root->rnode);
    > -
    > /* Propagate the aggregated tag info into the new root */
    > for (tag = 0; tag< RADIX_TREE_MAX_TAGS; tag++) {
    > if (root_tag_get(root, tag))
    > tag_set(node, tag, 0);
    > }
    >
    > + /* Increase the height. */
    > newheight = root->height+1;
    > node->height = newheight;
    > node->count = 1;
    > + node->parent = NULL;
    > + slot = root->rnode;
    > + if (newheight> 1) {
    > + slot = indirect_to_ptr(slot);
    > + slot->parent = node;
    > + }
    > + node->slots[0] = slot;
    > node = ptr_to_indirect(node);
    > rcu_assign_pointer(root->rnode, node);
    > root->height = newheight;
    > @@ -331,6 +335,7 @@ int radix_tree_insert(struct radix_tree_
    > if (!(slot = radix_tree_node_alloc(root)))
    > return -ENOMEM;
    > slot->height = height;
    > + slot->parent = node;
    > if (node) {
    > rcu_assign_pointer(node->slots[offset], slot);
    > node->count++;
    > @@ -504,47 +509,41 @@ EXPORT_SYMBOL(radix_tree_tag_set);
    > void *radix_tree_tag_clear(struct radix_tree_root *root,
    > unsigned long index, unsigned int tag)
    > {
    > - /*
    > - * The radix tree path needs to be one longer than the maximum path
    > - * since the "list" is null terminated.
    > - */
    > - struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
    > + struct radix_tree_node *node = NULL;
    > struct radix_tree_node *slot = NULL;
    > unsigned int height, shift;
    > + int uninitialized_var(offset);
    >
    > height = root->height;
    > if (index> radix_tree_maxindex(height))
    > goto out;
    >
    > - shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
    > - pathp->node = NULL;
    > + shift = height * RADIX_TREE_MAP_SHIFT;
    > slot = indirect_to_ptr(root->rnode);
    >
    > - while (height> 0) {
    > - int offset;
    > -
    > + while (shift) {
    > if (slot == NULL)
    > goto out;
    >
    > + shift -= RADIX_TREE_MAP_SHIFT;
    > offset = (index>> shift)& RADIX_TREE_MAP_MASK;
    > - pathp[1].offset = offset;
    > - pathp[1].node = slot;
    > + node = slot;
    > slot = slot->slots[offset];
    > - pathp++;
    > - shift -= RADIX_TREE_MAP_SHIFT;
    > - height--;
    > }
    >
    > if (slot == NULL)
    > goto out;
    >
    > - while (pathp->node) {
    > - if (!tag_get(pathp->node, tag, pathp->offset))
    > + while (node) {
    > + if (!tag_get(node, tag, offset))
    > goto out;
    > - tag_clear(pathp->node, tag, pathp->offset);
    > - if (any_tag_set(pathp->node, tag))
    > + tag_clear(node, tag, offset);
    > + if (any_tag_set(node, tag))
    > goto out;
    > - pathp--;
    > +
    > + index>>= RADIX_TREE_MAP_SHIFT;
    > + offset = index& RADIX_TREE_MAP_MASK;
    > + node = node->parent;
    > }
    >
    > /* clear the root's tag bit */
    > @@ -646,8 +645,7 @@ unsigned long radix_tree_range_tag_if_ta
    > unsigned int iftag, unsigned int settag)
    > {
    > unsigned int height = root->height;
    > - struct radix_tree_path path[height];
    > - struct radix_tree_path *pathp = path;
    > + struct radix_tree_node *node = NULL;
    > struct radix_tree_node *slot;
    > unsigned int shift;
    > unsigned long tagged = 0;
    > @@ -671,14 +669,8 @@ unsigned long radix_tree_range_tag_if_ta
    > shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
    > slot = indirect_to_ptr(root->rnode);
    >
    > - /*
    > - * we fill the path from (root->height - 2) to 0, leaving the index at
    > - * (root->height - 1) as a terminator. Zero the node in the terminator
    > - * so that we can use this to end walk loops back up the path.
    > - */
    > - path[height - 1].node = NULL;
    > -
    > for (;;) {
    > + unsigned long upindex;
    > int offset;
    >
    > offset = (index>> shift)& RADIX_TREE_MAP_MASK;
    > @@ -686,12 +678,10 @@ unsigned long radix_tree_range_tag_if_ta
    > goto next;
    > if (!tag_get(slot, iftag, offset))
    > goto next;
    > - if (height> 1) {
    > + if (shift) {
    > /* Go down one level */
    > - height--;
    > shift -= RADIX_TREE_MAP_SHIFT;
    > - path[height - 1].node = slot;
    > - path[height - 1].offset = offset;
    > + node = slot;
    > slot = slot->slots[offset];
    > continue;
    > }
    > @@ -701,15 +691,21 @@ unsigned long radix_tree_range_tag_if_ta
    > tag_set(slot, settag, offset);
    >
    > /* walk back up the path tagging interior nodes */
    > - pathp =&path[0];
    > - while (pathp->node) {
    > + upindex = index;
    > + while (node) {
    > + upindex>>= RADIX_TREE_MAP_SHIFT;
    > + offset = upindex& RADIX_TREE_MAP_MASK;
    > +
    > /* stop if we find a node with the tag already set */
    > - if (tag_get(pathp->node, settag, pathp->offset))
    > + if (tag_get(node, settag, offset))
    > break;
    > - tag_set(pathp->node, settag, pathp->offset);
    > - pathp++;
    > + tag_set(node, settag, offset);
    > + node = node->parent;
    > }
    >
    > + /* optimization: no need to walk up from this node again */
    > + node = NULL;
    > +
    > next:
    > /* Go to next item at level determined by 'shift' */
    > index = ((index>> shift) + 1)<< shift;
    > @@ -724,8 +720,7 @@ next:
    > * last_index is guaranteed to be in the tree, what
    > * we do below cannot wander astray.
    > */
    > - slot = path[height - 1].node;
    > - height++;
    > + slot = slot->parent;
    > shift += RADIX_TREE_MAP_SHIFT;
    > }
    > }
    > @@ -1299,7 +1294,7 @@ static inline void radix_tree_shrink(str
    > /* try to shrink tree height */
    > while (root->height> 0) {
    > struct radix_tree_node *to_free = root->rnode;
    > - void *newptr;
    > + struct radix_tree_node *slot;
    >
    > BUG_ON(!radix_tree_is_indirect_ptr(to_free));
    > to_free = indirect_to_ptr(to_free);
    > @@ -1320,10 +1315,12 @@ static inline void radix_tree_shrink(str
    > * (to_free->slots[0]), it will be safe to dereference the new
    > * one (root->rnode) as far as dependent read barriers go.
    > */
    > - newptr = to_free->slots[0];
    > - if (root->height> 1)
    > - newptr = ptr_to_indirect(newptr);
    > - root->rnode = newptr;
    > + slot = to_free->slots[0];
    > + if (root->height> 1) {
    > + slot->parent = NULL;
    > + slot = ptr_to_indirect(slot);
    > + }
    > + root->rnode = slot;
    > root->height--;
    >
    > /*
    > @@ -1363,16 +1360,12 @@ static inline void radix_tree_shrink(str
    > */
    > void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
    > {
    > - /*
    > - * The radix tree path needs to be one longer than the maximum path
    > - * since the "list" is null terminated.
    > - */
    > - struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
    > + struct radix_tree_node *node = NULL;
    > struct radix_tree_node *slot = NULL;
    > struct radix_tree_node *to_free;
    > unsigned int height, shift;
    > int tag;
    > - int offset;
    > + int uninitialized_var(offset);
    >
    > height = root->height;
    > if (index> radix_tree_maxindex(height))
    > @@ -1385,39 +1378,35 @@ void *radix_tree_delete(struct radix_tre
    > goto out;
    > }
    > slot = indirect_to_ptr(slot);
    > -
    > - shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
    > - pathp->node = NULL;
    > + shift = height * RADIX_TREE_MAP_SHIFT;
    >
    > do {
    > if (slot == NULL)
    > goto out;
    >
    > - pathp++;
    > + shift -= RADIX_TREE_MAP_SHIFT;
    > offset = (index>> shift)& RADIX_TREE_MAP_MASK;
    > - pathp->offset = offset;
    > - pathp->node = slot;
    > + node = slot;
    > slot = slot->slots[offset];
    > - shift -= RADIX_TREE_MAP_SHIFT;
    > - height--;
    > - } while (height> 0);
    > + } while (shift);
    >
    > if (slot == NULL)
    > goto out;
    >
    > /*
    > - * Clear all tags associated with the just-deleted item
    > + * Clear all tags associated with the item to be deleted.
    > + * This way of doing it would be inefficient, but seldom is any set.
    > */
    > for (tag = 0; tag< RADIX_TREE_MAX_TAGS; tag++) {
    > - if (tag_get(pathp->node, tag, pathp->offset))
    > + if (tag_get(node, tag, offset))
    > radix_tree_tag_clear(root, index, tag);
    > }
    >
    > to_free = NULL;
    > /* Now free the nodes we do not need anymore */
    > - while (pathp->node) {
    > - pathp->node->slots[pathp->offset] = NULL;
    > - pathp->node->count--;
    > + while (node) {
    > + node->slots[offset] = NULL;
    > + node->count--;
    > /*
    > * Queue the node for deferred freeing after the
    > * last reference to it disappears (set NULL, above).
    > @@ -1425,17 +1414,20 @@ void *radix_tree_delete(struct radix_tre
    > if (to_free)
    > radix_tree_node_free(to_free);
    >
    > - if (pathp->node->count) {
    > - if (pathp->node == indirect_to_ptr(root->rnode))
    > + if (node->count) {
    > + if (node == indirect_to_ptr(root->rnode))
    > radix_tree_shrink(root);
    > goto out;
    > }
    >
    > /* Node with zero slots in use so free it */
    > - to_free = pathp->node;
    > - pathp--;
    > + to_free = node;
    >
    > + index>>= RADIX_TREE_MAP_SHIFT;
    > + offset = index& RADIX_TREE_MAP_MASK;
    > + node = node->parent;
    > }
    > +
    > root_tag_clear_all(root);
    > root->height = 0;
    > root->rnode = NULL;
    >
    > --
    > To unsubscribe, send a message with 'unsubscribe linux-mm' in
    > the body to majordomo@kvack.org. For more info on Linux MM,
    > see: http://www.linux-mm.org/ .
    > Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
    > Don't email:<a href=mailto:"dont@kvack.org"> email@kvack.org</a>
    --
    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/

    \
     
     \ /
      Last update: 2011-12-19 09:23    [W:2.119 / U:0.084 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site