Re: [PATCH] radix_tree: take radix_tree_path off stack

From: Nai Xia
Date: Mon Dec 19 2011 - 04:37:19 EST

Next message: Jens Axboe: "Re: linux-next: build failure after merge of the block tree"
Previous message: Takashi Iwai: "Re: [PATCH 13/15] module_param: make bool parameters really bool (sound)"
In reply to: nai.xia: "Re: [PATCH] radix_tree: take radix_tree_path off stack"
Next in thread: Hugh Dickins: "Re: [PATCH] radix_tree: take radix_tree_path off stack"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

On Mon, Dec 19, 2011 at 4:20 PM, nai.xia <nai.xia@xxxxxxxxx> wrote:
>
>
> 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.

And besides, I think maybe there were another few ways if
we really care about the stack usage of radix_tree_path,
e.g.
1. We can make radix_tree_path.offset compact to u8
which is enough to index inside a node.

2. We can use dynamic array on stack instead of
RADIX_TREE_MAX_PATH, I think for most cases
this may save half of the space

3. Take benefit of radix_tree_path array already
traveled down to clear the tags instead of calling
a radix_tree_tag_clear with full array.

I am not speaking of the negatives of your patch
, just some alternatives for your reference.

And forgive my possible selfishness, I just created a home
made radix tree traveler based on radix_tree_path array to
simulate recursive calls, not ready to its vanishing...

Thanks,

Nai

>
>
>> 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@xxxxxxxxxx>
>> ----
>>
>> Â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@xxxxxxxxxx Â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@xxxxxxxxx";> Âemail@xxxxxxxxx</a>
èº{.nÇ+‰·Ÿ®‰†+%ŠËlzwm…ébëæìr¸›zX§»®w¥Š{ayºÊÚë,j¢f£¢·hš‹àz¹®w¥¢¸¢·¦j:+v‰¨ŠwèjØm¶Ÿÿ¾«‘êçzZ+ƒùšŽŠÝj"ú!¶iO•æ¬z·švØ^¶m§ÿðÃnÆàþY&—

Next message: Jens Axboe: "Re: linux-next: build failure after merge of the block tree"
Previous message: Takashi Iwai: "Re: [PATCH 13/15] module_param: make bool parameters really bool (sound)"
In reply to: nai.xia: "Re: [PATCH] radix_tree: take radix_tree_path off stack"
Next in thread: Hugh Dickins: "Re: [PATCH] radix_tree: take radix_tree_path off stack"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]