From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S934386AbdEONpH (ORCPT ); Mon, 15 May 2017 09:45:07 -0400 Received: from bombadil.infradead.org ([65.50.211.133]:53215 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933582AbdEONpG (ORCPT ); Mon, 15 May 2017 09:45:06 -0400 Date: Mon, 15 May 2017 15:44:59 +0200 From: Peter Zijlstra To: Davidlohr Bueso Cc: mingo@kernel.org, akpm@linux-foundation.org, jack@suse.cz, kirill.shutemov@linux.intel.com, ldufour@linux.vnet.ibm.com, mhocko@suse.com, mgorman@techsingularity.net, linux-kernel@vger.kernel.org, Davidlohr Bueso Subject: Re: [PATCH 2/6] locking: Introduce range reader/writer lock Message-ID: <20170515134459.sl3jfewo7uj62cqs@hirez.programming.kicks-ass.net> References: <20170515090725.27055-1-dave@stgolabs.net> <20170515090725.27055-3-dave@stgolabs.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20170515090725.27055-3-dave@stgolabs.net> User-Agent: NeoMutt/20170113 (1.7.2) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.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.