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.
