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

[Peter Zijlstra <peterz@infradead.org>]

On Mon, May 15, 2017 at 02:07:21AM -0700, Davidlohr Bueso wrote:

> +#define range_interval_tree_foreach(node, root, start, last)	\
> +	for (node = interval_tree_iter_first(root, start, last); \
> +	     node; node = interval_tree_iter_next(node, start, last))
> +

> +/*
> + * Fastpath range intersection/overlap between A: [a0, a1] and B: [b0, b1]
> + * is given by:
> + *
> + *        a0 <= b1 && b0 <= a1
> + *
> + * ... where A holds the lock range and B holds the smallest 'start' and
> + * largest 'last' in the tree. For the later, we rely on the root node,
> + * which by augmented interval tree property, holds the largest value in
> + * its last-in-subtree. This allows mitigating some of the tree walk overhead
> + * for non-intersecting ranges, maintained and consulted in O(1).
> + */
> +static inline bool
> +__range_intersects_intree(struct range_lock_tree *tree, struct range_lock *lock)
> +{
> +	struct interval_tree_node *root;
> +
> +	if (unlikely(RB_EMPTY_ROOT(&tree->root)))
> +		return false;
> +
> +	root = to_interval_tree_node(tree->root.rb_node);
> +
> +	return lock->node.start <= root->__subtree_last &&
> +		tree->leftmost->start <= lock->node.last;
> +}

> +
> +			if (!__range_intersects_intree(tree, lock))
> +				goto unlock;
> +
> +			range_interval_tree_foreach(node, &tree->root,
> +						    lock->node.start,
> +						    lock->node.last) {


> +
> +	if (!__range_intersects_intree(tree, lock))
> +		goto insert;
> +
> +	/*
> +	 * We have overlapping ranges in the tree, ensure that we can
> +	 * in fact share the lock.
> +	 */
> +	range_interval_tree_foreach(node, &tree->root,
> +				    lock->node.start, lock->node.last) {


> +	if (!__range_intersects_intree(tree, lock))
> +		goto insert;
> +
> +	range_interval_tree_foreach(node, &tree->root,
> +				    lock->node.start, lock->node.last) {


> +
> +	if (!__range_intersects_intree(tree, lock)) {
> +		/* nobody to wakeup, we're done */
> +		spin_unlock_irqrestore(&tree->lock, flags);
> +		return;
> +	}
> +
> +	range_interval_tree_foreach(node, &tree->root,
> +				    lock->node.start, lock->node.last) {


> +	if (!__range_intersects_intree(tree, lock))
> +		goto insert;
> +
> +	range_interval_tree_foreach(node, &tree->root,
> +				    lock->node.start, lock->node.last) {



> +	if (!__range_intersects_intree(tree, lock)) {
> +		/* nobody to wakeup, we're done */
> +		spin_unlock_irqrestore(&tree->lock, flags);
> +		return;
> +	}
> +
> +	range_interval_tree_foreach(node, &tree->root,
> +				    lock->node.start, lock->node.last) {


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.