@@ -514,6 +514,16 @@ do { \
lock_acquired(&(_lock)->dep_map, _RET_IP_); \
} while (0)
+#define RANGE_LOCK_CONTENDED(tree, _lock, try, lock) \
+do { \
+ if (!try(tree, _lock)) { \
+ lock_contended(&(tree)->dep_map, _RET_IP_); \
+ lock(tree, _lock); \
+ } \
+ lock_acquired(&(tree)->dep_map, _RET_IP_); \
+} while (0)
+
+
#define LOCK_CONTENDED_RETURN(_lock, try, lock) \
({ \
int ____err = 0; \
@@ -526,6 +536,18 @@ do { \
____err; \
})
+#define RANGE_LOCK_CONTENDED_RETURN(tree, _lock, try, lock) \
+({ \
+ int ____err = 0; \
+ if (!try(tree, _lock)) { \
+ lock_contended(&(tree)->dep_map, _RET_IP_); \
+ ____err = lock(tree, _lock); \
+ } \
+ if (!____err) \
+ lock_acquired(&(tree)->dep_map, _RET_IP_); \
+ ____err; \
+})
+
#else /* CONFIG_LOCK_STAT */
#define lock_contended(lockdep_map, ip) do {} while (0)
@@ -534,9 +556,15 @@ do { \
#define LOCK_CONTENDED(_lock, try, lock) \
lock(_lock)
+#define RANGE_LOCK_CONTENDED(tree, _lock, try, lock) \
+ lock(tree, _lock)
+
#define LOCK_CONTENDED_RETURN(_lock, try, lock) \
lock(_lock)
+#define RANGE_LOCK_CONTENDED_RETURN(tree, _lock, try, lock) \
+ lock(tree, _lock)
+
#endif /* CONFIG_LOCK_STAT */
#ifdef CONFIG_LOCKDEP
@@ -601,6 +629,11 @@ static inline void print_irqtrace_events(struct task_struct *curr)
#define rwsem_acquire_read(l, s, t, i) lock_acquire_shared(l, s, t, NULL, i)
#define rwsem_release(l, n, i) lock_release(l, n, i)
+#define range_lock_acquire(l, s, t, i) lock_acquire_exclusive(l, s, t, NULL, i)
+#define range_lock_acquire_nest(l, s, t, n, i) lock_acquire_exclusive(l, s, t, n, i)
+#define range_lock_acquire_read(l, s, t, i) lock_acquire_shared(l, s, t, NULL, i)
+#define range_lock_release(l, n, i) lock_release(l, n, i)
+
#define lock_map_acquire(l) lock_acquire_exclusive(l, 0, 0, NULL, _THIS_IP_)
#define lock_map_acquire_read(l) lock_acquire_shared_recursive(l, 0, 0, NULL, _THIS_IP_)
#define lock_map_acquire_tryread(l) lock_acquire_shared_recursive(l, 0, 1, NULL, _THIS_IP_)
new file mode 100644
@@ -0,0 +1,189 @@
+/*
+ * Range/interval rw-locking
+ * -------------------------
+ *
+ * Interval-tree based range locking is about controlling tasks' forward
+ * progress when adding an arbitrary interval (node) to the tree, depending
+ * on any overlapping ranges. A task can only continue (or wakeup) if there
+ * are no intersecting ranges, thus achieving mutual exclusion. To this end,
+ * a reference counter is kept for each intersecting range in the tree
+ * (_before_ adding itself to it). To enable shared locking semantics,
+ * the reader to-be-locked will not take reference if an intersecting node
+ * is also a reader, therefore ignoring the node altogether.
+ *
+ * Given the above, range lock order and fairness has fifo semantics among
+ * contended ranges. Among uncontended ranges, order is given by the inorder
+ * tree traversal which is performed.
+ *
+ * Example: Tasks A, B, C. Tree is empty.
+ *
+ * t0: A grabs the (free) lock [a,n]; thus ref[a,n] = 0.
+ * t1: B tries to grab the lock [g,z]; thus ref[g,z] = 1.
+ * t2: C tries to grab the lock [b,m]; thus ref[b,m] = 2.
+ *
+ * t3: A releases the lock [a,n]; thus ref[g,z] = 0, ref[b,m] = 1.
+ * t4: B grabs the lock [g.z].
+ *
+ * In addition, freedom of starvation is guaranteed by the fact that there
+ * is no lock stealing going on, everything being serialized by the tree->lock.
+ *
+ * The cost of lock and unlock of a range is O((1+R_int)log(R_all)) where
+ * R_all is total number of ranges and R_int is the number of ranges
+ * intersecting the operated range.
+ */
+#ifndef _LINUX_RANGE_LOCK_H
+#define _LINUX_RANGE_LOCK_H
+
+#include <linux/rbtree.h>
+#include <linux/interval_tree.h>
+#include <linux/list.h>
+#include <linux/spinlock.h>
+
+/*
+ * The largest range will span [0,RANGE_LOCK_FULL].
+ */
+#define RANGE_LOCK_FULL ~0UL
+
+struct range_lock {
+ struct interval_tree_node node;
+ struct task_struct *tsk;
+ /* Number of ranges which are blocking acquisition of the lock */
+ unsigned int blocking_ranges;
+ u64 seqnum;
+};
+
+struct range_lock_tree {
+ struct rb_root_cached root;
+ spinlock_t lock;
+ u64 seqnum; /* track order of incoming ranges, avoid overflows */
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+ struct lockdep_map dep_map;
+#endif
+};
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+# define __RANGE_LOCK_DEP_MAP_INIT(lockname) , .dep_map = { .name = #lockname }
+#else
+# define __RANGE_LOCK_DEP_MAP_INIT(lockname)
+#endif
+
+#define __RANGE_LOCK_TREE_INITIALIZER(name) \
+ { .root = RB_ROOT_CACHED \
+ , .seqnum = 0 \
+ , .lock = __SPIN_LOCK_UNLOCKED(name.lock) \
+ __RANGE_LOCK_DEP_MAP_INIT(name) } \
+
+#define DEFINE_RANGE_LOCK_TREE(name) \
+ struct range_lock_tree name = __RANGE_LOCK_TREE_INITIALIZER(name)
+
+#define __RANGE_LOCK_INITIALIZER(__start, __last) { \
+ .node = { \
+ .start = (__start) \
+ ,.last = (__last) \
+ } \
+ , .tsk = NULL \
+ , .blocking_ranges = 0 \
+ , .seqnum = 0 \
+ }
+
+#define DEFINE_RANGE_LOCK(name, start, last) \
+ struct range_lock name = __RANGE_LOCK_INITIALIZER((start), (last))
+
+#define DEFINE_RANGE_LOCK_FULL(name) \
+ struct range_lock name = __RANGE_LOCK_INITIALIZER(0, RANGE_LOCK_FULL)
+
+static inline void
+__range_lock_tree_init(struct range_lock_tree *tree,
+ const char *name, struct lock_class_key *key)
+{
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+ /*
+ * Make sure we are not reinitializing a held lock:
+ */
+ debug_check_no_locks_freed((void *)tree, sizeof(*tree));
+ lockdep_init_map(&tree->dep_map, name, key, 0);
+#endif
+ tree->root = RB_ROOT_CACHED;
+ spin_lock_init(&tree->lock);
+ tree->seqnum = 0;
+}
+
+#define range_lock_tree_init(tree) \
+do { \
+ static struct lock_class_key __key; \
+ \
+ __range_lock_tree_init((tree), #tree, &__key); \
+} while (0)
+
+void range_lock_init(struct range_lock *lock,
+ unsigned long start, unsigned long last);
+void range_lock_init_full(struct range_lock *lock);
+
+/*
+ * lock for reading
+ */
+void range_read_lock(struct range_lock_tree *tree, struct range_lock *lock);
+int range_read_lock_interruptible(struct range_lock_tree *tree,
+ struct range_lock *lock);
+int range_read_lock_killable(struct range_lock_tree *tree,
+ struct range_lock *lock);
+int range_read_trylock(struct range_lock_tree *tree, struct range_lock *lock);
+void range_read_unlock(struct range_lock_tree *tree, struct range_lock *lock);
+
+/*
+ * lock for writing
+ */
+void range_write_lock(struct range_lock_tree *tree, struct range_lock *lock);
+int range_write_lock_interruptible(struct range_lock_tree *tree,
+ struct range_lock *lock);
+int range_write_lock_killable(struct range_lock_tree *tree,
+ struct range_lock *lock);
+int range_write_trylock(struct range_lock_tree *tree, struct range_lock *lock);
+void range_write_unlock(struct range_lock_tree *tree, struct range_lock *lock);
+
+void range_downgrade_write(struct range_lock_tree *tree,
+ struct range_lock *lock);
+
+int range_is_locked(struct range_lock_tree *tree, struct range_lock *lock);
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+/*
+ * nested locking. NOTE: range locks are not allowed to recurse
+ * (which occurs if the same task tries to acquire the same
+ * lock instance multiple times), but multiple locks of the
+ * same lock class might be taken, if the order of the locks
+ * is always the same. This ordering rule can be expressed
+ * to lockdep via the _nested() APIs, but enumerating the
+ * subclasses that are used. (If the nesting relationship is
+ * static then another method for expressing nested locking is
+ * the explicit definition of lock class keys and the use of
+ * lockdep_set_class() at lock initialization time.
+ * See Documentation/locking/lockdep-design.txt for more details.)
+ */
+extern void range_read_lock_nested(struct range_lock_tree *tree,
+ struct range_lock *lock, int subclass);
+extern void range_write_lock_nested(struct range_lock_tree *tree,
+ struct range_lock *lock, int subclass);
+extern int range_write_lock_killable_nested(struct range_lock_tree *tree,
+ struct range_lock *lock, int subclass);
+extern void _range_write_lock_nest_lock(struct range_lock_tree *tree,
+ struct range_lock *lock, struct lockdep_map *nest_lock);
+
+# define range_write_lock_nest_lock(tree, lock, nest_lock) \
+do { \
+ typecheck(struct lockdep_map *, &(nest_lock)->dep_map); \
+ _range_write_lock_nest_lock(tree, lock, &(nest_lock)->dep_map); \
+} while (0);
+
+#else
+# define range_read_lock_nested(tree, lock, subclass) \
+ range_read_lock(tree, lock)
+# define range_write_lock_nest_lock(tree, lock, nest_lock) \
+ range_write_lock(tree, lock)
+# define range_write_lock_nested(tree, lock, subclass) \
+ range_write_lock(tree, lock)
+# define range_write_lock_killable_nested(tree, lock, subclass) \
+ range_write_lock_killable(tree, lock)
+#endif
+
+#endif
@@ -3,7 +3,7 @@
# and is generally not a function of system call inputs.
KCOV_INSTRUMENT := n
-obj-y += mutex.o semaphore.o rwsem.o percpu-rwsem.o rwsem-xadd.o
+obj-y += mutex.o semaphore.o rwsem.o percpu-rwsem.o rwsem-xadd.o range_lock.o
ifdef CONFIG_FUNCTION_TRACER
CFLAGS_REMOVE_lockdep.o = $(CC_FLAGS_FTRACE)
new file mode 100644
@@ -0,0 +1,667 @@
+/*
+ * Copyright (C) 2017 Jan Kara, Davidlohr Bueso.
+ */
+
+#include <linux/rbtree.h>
+#include <linux/spinlock.h>
+#include <linux/range_lock.h>
+#include <linux/lockdep.h>
+#include <linux/sched/signal.h>
+#include <linux/sched/debug.h>
+#include <linux/sched/wake_q.h>
+#include <linux/sched.h>
+#include <linux/export.h>
+
+#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))
+
+#define to_range_lock(ptr) container_of(ptr, struct range_lock, node)
+#define to_interval_tree_node(ptr) \
+ container_of(ptr, struct interval_tree_node, rb)
+
+static inline void
+__range_tree_insert(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ lock->seqnum = tree->seqnum++;
+ interval_tree_insert(&lock->node, &tree->root);
+}
+
+static inline void
+__range_tree_remove(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ interval_tree_remove(&lock->node, &tree->root);
+}
+
+/*
+ * lock->tsk reader tracking.
+ */
+#define RANGE_FLAG_READER 1UL
+
+static inline struct task_struct *range_lock_waiter(struct range_lock *lock)
+{
+ return (struct task_struct *)
+ ((unsigned long) lock->tsk & ~RANGE_FLAG_READER);
+}
+
+static inline void range_lock_set_reader(struct range_lock *lock)
+{
+ lock->tsk = (struct task_struct *)
+ ((unsigned long)lock->tsk | RANGE_FLAG_READER);
+}
+
+static inline void range_lock_clear_reader(struct range_lock *lock)
+{
+ lock->tsk = (struct task_struct *)
+ ((unsigned long)lock->tsk & ~RANGE_FLAG_READER);
+}
+
+static inline bool range_lock_is_reader(struct range_lock *lock)
+{
+ return (unsigned long) lock->tsk & RANGE_FLAG_READER;
+}
+
+static inline void
+__range_lock_init(struct range_lock *lock,
+ unsigned long start, unsigned long last)
+{
+ WARN_ON(start > last);
+
+ lock->node.start = start;
+ lock->node.last = last;
+ RB_CLEAR_NODE(&lock->node.rb);
+ lock->blocking_ranges = 0;
+ lock->tsk = NULL;
+ lock->seqnum = 0;
+}
+
+/**
+ * range_lock_init - Initialize a range lock
+ * @lock: the range lock to be initialized
+ * @start: start of the interval (inclusive)
+ * @last: last location in the interval (inclusive)
+ *
+ * Initialize the range's [start, last] such that it can
+ * later be locked. User is expected to enter a sorted
+ * range, such that @start <= @last.
+ *
+ * It is not allowed to initialize an already locked range.
+ */
+void range_lock_init(struct range_lock *lock,
+ unsigned long start, unsigned long last)
+{
+ __range_lock_init(lock, start, last);
+}
+EXPORT_SYMBOL_GPL(range_lock_init);
+
+/**
+ * range_lock_init_full - Initialize a full range lock
+ * @lock: the range lock to be initialized
+ *
+ * Initialize the full range.
+ *
+ * It is not allowed to initialize an already locked range.
+ */
+void range_lock_init_full(struct range_lock *lock)
+{
+ __range_lock_init(lock, 0, RANGE_LOCK_FULL);
+}
+EXPORT_SYMBOL_GPL(range_lock_init_full);
+
+static inline void
+range_lock_put(struct range_lock *lock, struct wake_q_head *wake_q)
+{
+ if (!--lock->blocking_ranges)
+ wake_q_add(wake_q, range_lock_waiter(lock));
+}
+
+static inline int wait_for_ranges(struct range_lock_tree *tree,
+ struct range_lock *lock, long state)
+{
+ int ret = 0;
+
+ while (true) {
+ set_current_state(state);
+
+ /* do we need to go to sleep? */
+ if (!lock->blocking_ranges)
+ break;
+
+ if (unlikely(signal_pending_state(state, current))) {
+ struct interval_tree_node *node;
+ unsigned long flags;
+ DEFINE_WAKE_Q(wake_q);
+
+ ret = -EINTR;
+ /*
+ * We're not taking the lock after all, cleanup
+ * after ourselves.
+ */
+ spin_lock_irqsave(&tree->lock, flags);
+
+ range_lock_clear_reader(lock);
+ __range_tree_remove(tree, lock);
+
+ range_interval_tree_foreach(node, &tree->root,
+ lock->node.start,
+ lock->node.last) {
+ struct range_lock *blked;
+ blked = to_range_lock(node);
+
+ if (range_lock_is_reader(lock) &&
+ range_lock_is_reader(blked))
+ continue;
+
+ /* unaccount for threads _we_ are blocking */
+ if (lock->seqnum < blked->seqnum)
+ range_lock_put(blked, &wake_q);
+ }
+
+ spin_unlock_irqrestore(&tree->lock, flags);
+ wake_up_q(&wake_q);
+ break;
+ }
+
+ schedule();
+ }
+
+ __set_current_state(TASK_RUNNING);
+ return ret;
+}
+
+/**
+ * range_read_trylock - Trylock for reading
+ * @tree: interval tree
+ * @lock: the range lock to be trylocked
+ *
+ * The trylock is against the range itself, not the @tree->lock.
+ *
+ * Returns 1 if successful, 0 if contention (must block to acquire).
+ */
+static inline int __range_read_trylock(struct range_lock_tree *tree,
+ struct range_lock *lock)
+{
+ int ret = true;
+ unsigned long flags;
+ struct interval_tree_node *node;
+
+ spin_lock_irqsave(&tree->lock, flags);
+
+ range_interval_tree_foreach(node, &tree->root,
+ lock->node.start, lock->node.last) {
+ struct range_lock *blocked_lock;
+ blocked_lock = to_range_lock(node);
+
+ if (!range_lock_is_reader(blocked_lock)) {
+ ret = false;
+ goto unlock;
+ }
+ }
+
+ range_lock_set_reader(lock);
+ __range_tree_insert(tree, lock);
+unlock:
+ spin_unlock_irqrestore(&tree->lock, flags);
+
+ return ret;
+}
+
+int range_read_trylock(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ int ret = __range_read_trylock(tree, lock);
+
+ if (ret)
+ range_lock_acquire_read(&tree->dep_map, 0, 1, _RET_IP_);
+
+ return ret;
+}
+
+EXPORT_SYMBOL_GPL(range_read_trylock);
+
+static __always_inline int __sched
+__range_read_lock_common(struct range_lock_tree *tree,
+ struct range_lock *lock, long state)
+{
+ struct interval_tree_node *node;
+ unsigned long flags;
+
+ spin_lock_irqsave(&tree->lock, flags);
+
+ range_interval_tree_foreach(node, &tree->root,
+ lock->node.start, lock->node.last) {
+ struct range_lock *blocked_lock;
+ blocked_lock = to_range_lock(node);
+
+ if (!range_lock_is_reader(blocked_lock))
+ lock->blocking_ranges++;
+ }
+
+ __range_tree_insert(tree, lock);
+
+ lock->tsk = current;
+ range_lock_set_reader(lock);
+ spin_unlock_irqrestore(&tree->lock, flags);
+
+ return wait_for_ranges(tree, lock, state);
+}
+
+static __always_inline int
+__range_read_lock(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ return __range_read_lock_common(tree, lock, TASK_UNINTERRUPTIBLE);
+}
+
+/**
+ * range_read_lock - Lock for reading
+ * @tree: interval tree
+ * @lock: the range lock to be locked
+ *
+ * Returns when the lock has been acquired or sleep until
+ * until there are no overlapping ranges.
+ */
+void range_read_lock(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ might_sleep();
+ range_lock_acquire_read(&tree->dep_map, 0, 0, _RET_IP_);
+
+ RANGE_LOCK_CONTENDED(tree, lock,
+ __range_read_trylock, __range_read_lock);
+}
+EXPORT_SYMBOL_GPL(range_read_lock);
+
+/**
+ * range_read_lock_interruptible - Lock for reading (interruptible)
+ * @tree: interval tree
+ * @lock: the range lock to be locked
+ *
+ * Lock the range like range_read_lock(), and return 0 if the
+ * lock has been acquired or sleep until until there are no
+ * overlapping ranges. If a signal arrives while waiting for the
+ * lock then this function returns -EINTR.
+ */
+int range_read_lock_interruptible(struct range_lock_tree *tree,
+ struct range_lock *lock)
+{
+ might_sleep();
+ return __range_read_lock_common(tree, lock, TASK_INTERRUPTIBLE);
+}
+EXPORT_SYMBOL_GPL(range_read_lock_interruptible);
+
+/**
+ * range_read_lock_killable - Lock for reading (killable)
+ * @tree: interval tree
+ * @lock: the range lock to be locked
+ *
+ * Lock the range like range_read_lock(), and return 0 if the
+ * lock has been acquired or sleep until until there are no
+ * overlapping ranges. If a signal arrives while waiting for the
+ * lock then this function returns -EINTR.
+ */
+static __always_inline int
+__range_read_lock_killable(struct range_lock_tree *tree,
+ struct range_lock *lock)
+{
+ return __range_read_lock_common(tree, lock, TASK_KILLABLE);
+}
+
+int range_read_lock_killable(struct range_lock_tree *tree,
+ struct range_lock *lock)
+{
+ might_sleep();
+ range_lock_acquire_read(&tree->dep_map, 0, 0, _RET_IP_);
+
+ if (RANGE_LOCK_CONTENDED_RETURN(tree, lock, __range_read_trylock,
+ __range_read_lock_killable)) {
+ range_lock_release(&tree->dep_map, 1, _RET_IP_);
+ return -EINTR;
+ }
+
+ return 0;
+}
+EXPORT_SYMBOL_GPL(range_read_lock_killable);
+
+/**
+ * range_read_unlock - Unlock for reading
+ * @tree: interval tree
+ * @lock: the range lock to be unlocked
+ *
+ * Wakes any blocked readers, when @lock is the only conflicting range.
+ *
+ * It is not allowed to unlock an unacquired read lock.
+ */
+void range_read_unlock(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ struct interval_tree_node *node;
+ unsigned long flags;
+ DEFINE_WAKE_Q(wake_q);
+
+ spin_lock_irqsave(&tree->lock, flags);
+
+ range_lock_clear_reader(lock);
+ __range_tree_remove(tree, lock);
+
+ range_lock_release(&tree->dep_map, 1, _RET_IP_);
+
+ range_interval_tree_foreach(node, &tree->root,
+ lock->node.start, lock->node.last) {
+ struct range_lock *blocked_lock;
+ blocked_lock = to_range_lock(node);
+
+ if (!range_lock_is_reader(blocked_lock))
+ range_lock_put(blocked_lock, &wake_q);
+ }
+
+ spin_unlock_irqrestore(&tree->lock, flags);
+ wake_up_q(&wake_q);
+}
+EXPORT_SYMBOL_GPL(range_read_unlock);
+
+/*
+ * Check for overlaps for fast write_trylock(), which is the same
+ * optimization that interval_tree_iter_first() does.
+ */
+static inline bool __range_overlaps_intree(struct range_lock_tree *tree,
+ struct range_lock *lock)
+{
+ struct interval_tree_node *root;
+ struct range_lock *left;
+
+ if (unlikely(RB_EMPTY_ROOT(&tree->root.rb_root)))
+ return false;
+
+ root = to_interval_tree_node(tree->root.rb_root.rb_node);
+ left = to_range_lock(to_interval_tree_node(rb_first_cached(&tree->root)));
+
+ return lock->node.start <= root->__subtree_last &&
+ left->node.start <= lock->node.last;
+}
+
+/**
+ * range_write_trylock - Trylock for writing
+ * @tree: interval tree
+ * @lock: the range lock to be trylocked
+ *
+ * The trylock is against the range itself, not the @tree->lock.
+ *
+ * Returns 1 if successful, 0 if contention (must block to acquire).
+ */
+static inline int __range_write_trylock(struct range_lock_tree *tree,
+ struct range_lock *lock)
+{
+ int overlaps;
+ unsigned long flags;
+
+ spin_lock_irqsave(&tree->lock, flags);
+ overlaps = __range_overlaps_intree(tree, lock);
+
+ if (!overlaps) {
+ range_lock_clear_reader(lock);
+ __range_tree_insert(tree, lock);
+ }
+
+ spin_unlock_irqrestore(&tree->lock, flags);
+
+ return !overlaps;
+}
+
+int range_write_trylock(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ int ret = __range_write_trylock(tree, lock);
+
+ if (ret)
+ range_lock_acquire(&tree->dep_map, 0, 1, _RET_IP_);
+
+ return ret;
+}
+EXPORT_SYMBOL_GPL(range_write_trylock);
+
+static __always_inline int __sched
+__range_write_lock_common(struct range_lock_tree *tree,
+ struct range_lock *lock, long state)
+{
+ struct interval_tree_node *node;
+ unsigned long flags;
+
+ spin_lock_irqsave(&tree->lock, flags);
+
+ range_interval_tree_foreach(node, &tree->root,
+ lock->node.start, lock->node.last) {
+ /*
+ * As a writer, we always consider an existing node. We
+ * need to wait; either the intersecting node is another
+ * writer or we have a reader that needs to finish.
+ */
+ lock->blocking_ranges++;
+ }
+
+ __range_tree_insert(tree, lock);
+
+ lock->tsk = current;
+ spin_unlock_irqrestore(&tree->lock, flags);
+
+ return wait_for_ranges(tree, lock, state);
+}
+
+static __always_inline int
+__range_write_lock(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ return __range_write_lock_common(tree, lock, TASK_UNINTERRUPTIBLE);
+}
+
+/**
+ * range_write_lock - Lock for writing
+ * @tree: interval tree
+ * @lock: the range lock to be locked
+ *
+ * Returns when the lock has been acquired or sleep until
+ * until there are no overlapping ranges.
+ */
+void range_write_lock(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ might_sleep();
+ range_lock_acquire(&tree->dep_map, 0, 0, _RET_IP_);
+
+ RANGE_LOCK_CONTENDED(tree, lock,
+ __range_write_trylock, __range_write_lock);
+}
+EXPORT_SYMBOL_GPL(range_write_lock);
+
+/**
+ * range_write_lock_interruptible - Lock for writing (interruptible)
+ * @tree: interval tree
+ * @lock: the range lock to be locked
+ *
+ * Lock the range like range_write_lock(), and return 0 if the
+ * lock has been acquired or sleep until until there are no
+ * overlapping ranges. If a signal arrives while waiting for the
+ * lock then this function returns -EINTR.
+ */
+int range_write_lock_interruptible(struct range_lock_tree *tree,
+ struct range_lock *lock)
+{
+ might_sleep();
+ return __range_write_lock_common(tree, lock, TASK_INTERRUPTIBLE);
+}
+EXPORT_SYMBOL_GPL(range_write_lock_interruptible);
+
+/**
+ * range_write_lock_killable - Lock for writing (killable)
+ * @tree: interval tree
+ * @lock: the range lock to be locked
+ *
+ * Lock the range like range_write_lock(), and return 0 if the
+ * lock has been acquired or sleep until until there are no
+ * overlapping ranges. If a signal arrives while waiting for the
+ * lock then this function returns -EINTR.
+ */
+static __always_inline int
+__range_write_lock_killable(struct range_lock_tree *tree,
+ struct range_lock *lock)
+{
+ return __range_write_lock_common(tree, lock, TASK_KILLABLE);
+}
+
+int range_write_lock_killable(struct range_lock_tree *tree,
+ struct range_lock *lock)
+{
+ might_sleep();
+ range_lock_acquire(&tree->dep_map, 0, 0, _RET_IP_);
+
+ if (RANGE_LOCK_CONTENDED_RETURN(tree, lock, __range_write_trylock,
+ __range_write_lock_killable)) {
+ range_lock_release(&tree->dep_map, 1, _RET_IP_);
+ return -EINTR;
+ }
+
+ return 0;
+}
+EXPORT_SYMBOL_GPL(range_write_lock_killable);
+
+/**
+ * range_write_unlock - Unlock for writing
+ * @tree: interval tree
+ * @lock: the range lock to be unlocked
+ *
+ * Wakes any blocked readers, when @lock is the only conflicting range.
+ *
+ * It is not allowed to unlock an unacquired write lock.
+ */
+void range_write_unlock(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ struct interval_tree_node *node;
+ unsigned long flags;
+ DEFINE_WAKE_Q(wake_q);
+
+ spin_lock_irqsave(&tree->lock, flags);
+
+ range_lock_clear_reader(lock);
+ __range_tree_remove(tree, lock);
+
+ range_lock_release(&tree->dep_map, 1, _RET_IP_);
+
+ range_interval_tree_foreach(node, &tree->root,
+ lock->node.start, lock->node.last) {
+ struct range_lock *blocked_lock;
+ blocked_lock = to_range_lock(node);
+
+ range_lock_put(blocked_lock, &wake_q);
+ }
+
+ spin_unlock_irqrestore(&tree->lock, flags);
+ wake_up_q(&wake_q);
+}
+EXPORT_SYMBOL_GPL(range_write_unlock);
+
+/**
+ * range_downgrade_write - Downgrade write range lock to read lock
+ * @tree: interval tree
+ * @lock: the range lock to be downgraded
+ *
+ * Wakes any blocked readers, when @lock is the only conflicting range.
+ *
+ * It is not allowed to downgrade an unacquired write lock.
+ */
+void range_downgrade_write(struct range_lock_tree *tree,
+ struct range_lock *lock)
+{
+ unsigned long flags;
+ struct interval_tree_node *node;
+ DEFINE_WAKE_Q(wake_q);
+
+ lock_downgrade(&tree->dep_map, _RET_IP_);
+
+ spin_lock_irqsave(&tree->lock, flags);
+
+ WARN_ON(range_lock_is_reader(lock));
+
+ range_interval_tree_foreach(node, &tree->root,
+ lock->node.start, lock->node.last) {
+ struct range_lock *blocked_lock;
+ blocked_lock = to_range_lock(node);
+
+ /*
+ * Unaccount for any blocked reader lock. Wakeup if possible.
+ */
+ if (range_lock_is_reader(blocked_lock))
+ range_lock_put(blocked_lock, &wake_q);
+ }
+
+ range_lock_set_reader(lock);
+ spin_unlock_irqrestore(&tree->lock, flags);
+ wake_up_q(&wake_q);
+}
+EXPORT_SYMBOL_GPL(range_downgrade_write);
+
+/**
+ * range_is_locked - Returns 1 if the given range is already either reader or
+ * writer owned. Otherwise 0.
+ * @tree: interval tree
+ * @lock: the range lock to be checked
+ *
+ * Similar to trylocks, this is against the range itself, not the @tree->lock.
+ */
+int range_is_locked(struct range_lock_tree *tree, struct range_lock *lock)
+{
+ int overlaps;
+ unsigned long flags;
+
+ spin_lock_irqsave(&tree->lock, flags);
+ overlaps = __range_overlaps_intree(tree, lock);
+ spin_unlock_irqrestore(&tree->lock, flags);
+
+ return overlaps;
+}
+EXPORT_SYMBOL_GPL(range_is_locked);
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+
+void range_read_lock_nested(struct range_lock_tree *tree,
+ struct range_lock *lock, int subclass)
+{
+ might_sleep();
+ range_lock_acquire_read(&tree->dep_map, subclass, 0, _RET_IP_);
+
+ RANGE_LOCK_CONTENDED(tree, lock, __range_read_trylock, __range_read_lock);
+}
+EXPORT_SYMBOL_GPL(range_read_lock_nested);
+
+void _range_write_lock_nest_lock(struct range_lock_tree *tree,
+ struct range_lock *lock,
+ struct lockdep_map *nest)
+{
+ might_sleep();
+ range_lock_acquire_nest(&tree->dep_map, 0, 0, nest, _RET_IP_);
+
+ RANGE_LOCK_CONTENDED(tree, lock,
+ __range_write_trylock, __range_write_lock);
+}
+EXPORT_SYMBOL_GPL(_range_write_lock_nest_lock);
+
+void range_write_lock_nested(struct range_lock_tree *tree,
+ struct range_lock *lock, int subclass)
+{
+ might_sleep();
+ range_lock_acquire(&tree->dep_map, subclass, 0, _RET_IP_);
+
+ RANGE_LOCK_CONTENDED(tree, lock,
+ __range_write_trylock, __range_write_lock);
+}
+EXPORT_SYMBOL_GPL(range_write_lock_nested);
+
+
+int range_write_lock_killable_nested(struct range_lock_tree *tree,
+ struct range_lock *lock, int subclass)
+{
+ might_sleep();
+ range_lock_acquire(&tree->dep_map, subclass, 0, _RET_IP_);
+
+ if (RANGE_LOCK_CONTENDED_RETURN(tree, lock, __range_write_trylock,
+ __range_write_lock_killable)) {
+ range_lock_release(&tree->dep_map, 1, _RET_IP_);
+ return -EINTR;
+ }
+
+ return 0;
+}
+EXPORT_SYMBOL_GPL(range_write_lock_killable_nested);
+#endif