Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1641702

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

Show all headers | View raw

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.

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH v3 -tip 0/6] locking: Introduce range reader/writer lock Davidlohr Bueso <dave@stgolabs.net> - 2017-05-15 11:10 +0200
  [PATCH 5/6] locking/locktorture: Support range rwlocks Davidlohr Bueso <dave@stgolabs.net> - 2017-05-15 11:10 +0200
  [PATCH 1/6] interval-tree: Build unconditionally Davidlohr Bueso <dave@stgolabs.net> - 2017-05-15 11:10 +0200
  [PATCH 2/6] locking: Introduce range reader/writer lock Davidlohr Bueso <dave@stgolabs.net> - 2017-05-15 11:10 +0200
    Re: [PATCH 2/6] locking: Introduce range reader/writer lock Peter Zijlstra <peterz@infradead.org> - 2017-05-15 15:10 +0200
      Re: [PATCH 2/6] locking: Introduce range reader/writer lock Davidlohr Bueso <dave@stgolabs.net> - 2017-05-17 00:20 +0200
    Re: [PATCH 2/6] locking: Introduce range reader/writer lock Peter Zijlstra <peterz@infradead.org> - 2017-05-15 15:50 +0200
      Re: [PATCH 2/6] locking: Introduce range reader/writer lock Davidlohr Bueso <dave@stgolabs.net> - 2017-05-16 23:20 +0200
    Re: [PATCH 2/6] locking: Introduce range reader/writer lock Peter Zijlstra <peterz@infradead.org> - 2017-05-15 16:00 +0200
    Re: [PATCH 2/6] locking: Introduce range reader/writer lock Laurent Dufour <ldufour@linux.vnet.ibm.com> - 2017-05-23 17:20 +0200
  [PATCH 3/6] locking/locktorture: Fix rwsem reader_delay Davidlohr Bueso <dave@stgolabs.net> - 2017-05-15 11:10 +0200
  [PATCH 6/6] staging/lustre: Use generic range rwlock Davidlohr Bueso <dave@stgolabs.net> - 2017-05-15 11:10 +0200
    Re: [PATCH 6/6] staging/lustre: Use generic range rwlock "Dilger, Andreas" <andreas.dilger@intel.com> - 2017-05-18 10:40 +0200
  [PATCH 4/6] locking/locktorture: Fix num reader/writer corner cases Davidlohr Bueso <dave@stgolabs.net> - 2017-05-15 11:10 +0200
  Re: [PATCH v3 -tip 0/6] locking: Introduce range reader/writer lock Christoph Hellwig <hch@infradead.org> - 2017-05-15 18:20 +0200

csiph-web