[PATCH] powerpc: add for_each_node_by_foo helpers

[Benjamin Herrenschmidt]

> > I recently showed a variety of scenarios that would blow up in funny
> > ways.. It's not enough.
> 
> A variety of scenarios?  I'm aware of only one [1], which is kind of a
> corner case, and has never come up in practice to my knowledge.
> 
> If you know of others, I'd like to know the details.

I actually have one in mind that I remember, but I'm pretty sure I saw
another one... it's not that much of a corner case, I think in general,
it's almost impossible to handle safe management of a list/tree without
an external lock taken by iterators around the iteration, which I think
is why klist were created... Unless maybe we deal with node deletion
using some kind of RCU mecanism

> Are we talking about the same thing?  I'm talking about the
> of_find_node_by_foo iterators and they all hold the lock while
> traversing the tree.

Yes but not between calls...

> [1] IIRC, it's something like this:
> 
> Nodes A, B, and C are adjacent in the allnext list -- A->allnext = B,
> B->allnext = C.
> 
> A is unplugged from the tree (of_detach_node), but something still
> holds a reference to it so A is not freed yet.
> 
> B is then unplugged from the tree, but we can't get to A to fix up
> its allnext field to point to C.  B has no outstanding references
> and is freed.
> 
> The user of A attempts to dereference A->allnext, but B isn't
> there anymore.
> 
> This could happen with the sibling list and parent pointer as well.
> 
> So the basic issue is that traversing back into the tree from a node
> that has been unplugged from the tree is invalid -- the state of the
> tree is indeterminate with respect to the removed node's links into
> it.
> 
> Seems to me that one way to address this is to keep a node from being
> unplugged until all other users have dropped their references to it.

It might help by having references associated with links, but we end up
with cases where the tree will still reference a node after returning
from remove... Maybe putting a flag in the node when unliked to cause
other iterators to "skip" it and making sure that reference to a node
done by it's peers is counted would help...

Ben.