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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20170515134459.sl3jfewo7uj62cqs@hirez.programming.kicks-ass.net>
Date:   Mon, 15 May 2017 15:44:59 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Davidlohr Bueso <dave@...olabs.net>
Cc:     mingo@...nel.org, akpm@...ux-foundation.org, jack@...e.cz,
        kirill.shutemov@...ux.intel.com, ldufour@...ux.vnet.ibm.com,
        mhocko@...e.com, mgorman@...hsingularity.net,
        linux-kernel@...r.kernel.org, Davidlohr Bueso <dbueso@...e.de>
Subject: Re: [PATCH 2/6] locking: Introduce range reader/writer lock

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.