Re: [PATCH 2/6] locking: Introduce range reader/writer lock

[Davidlohr Bueso <dave@stgolabs.net>]

On Mon, 15 May 2017, Peter Zijlstra wrote:

>Nearly every range_interval_tree_foreach() usage has a
>__range_intersects_intree() in front, suggesting our
>range_interval_tree_foreach() is 'broken'.
>
>I suppose the only question is if we should fix
>range_interval_tree_foreach() or interval_tree_iter_first(). I'm tempted
>to suggest the latter.

Yes this functionality would be helpful to all interval tree users,
but for that we have to cache the leftmost node, and given the way
interval trees are setup via templates, the latter gets icky _fast_:

- For one we could add extra parameters to INTERVAL_TREE_DEFINE and
pass an arbitrary structure that contains a ptr to the node type
as well as the rb_root. This of course busts the generic flavor.

Or,

- Add a second leftmost rb_node to struct rb_root and (at least) only
use it for interval trees; while there are rbtree users that do this
caching explicitly, I doubt folks would like for the general case.

So it would seem that we ought to tuck __range_intersects_intree()
in the range_interval_tree_foreach() helper.

Thanks,
Davidlohr