[PATCH, RFC 1/2] lib: Implement range locks
From: Jan Kara
Implement range locking using interval tree.
Signed-off-by: Jan Kara
Signed-off-by: Kirill A. Shutemov
---
drivers/gpu/drm/Kconfig | 1 -
drivers/gpu/drm/i915/Kconfig | 1 -
include/linux/range_lock.h | 51 +
lib/Kconfig | 14
lib/Kconfig.debug| 1 -
lib/Makefile | 3 +-
lib/range_lock.c | 78
7 files changed, 130 insertions(+), 19 deletions(-)
create mode 100644 include/linux/range_lock.h
create mode 100644 lib/range_lock.c
diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig
index 06ae5008c5ed..1e02f73891fd 100644
--- a/drivers/gpu/drm/Kconfig
+++ b/drivers/gpu/drm/Kconfig
@@ -130,7 +130,6 @@ config DRM_RADEON
select POWER_SUPPLY
select HWMON
select BACKLIGHT_CLASS_DEVICE
- select INTERVAL_TREE
help
Choose this option if you have an ATI Radeon graphics card. There
are both PCI and AGP versions. You don't need to choose this to
diff --git a/drivers/gpu/drm/i915/Kconfig b/drivers/gpu/drm/i915/Kconfig
index eb87e2538861..c76525f8cbe9 100644
--- a/drivers/gpu/drm/i915/Kconfig
+++ b/drivers/gpu/drm/i915/Kconfig
@@ -5,7 +5,6 @@ config DRM_I915
depends on (AGP || AGP=n)
select INTEL_GTT
select AGP_INTEL if AGP
- select INTERVAL_TREE
# we need shmfs for the swappable backing store, and in particular
# the shmem_readpage() which depends upon tmpfs
select SHMEM
diff --git a/include/linux/range_lock.h b/include/linux/range_lock.h
new file mode 100644
index ..fe258a599676
--- /dev/null
+++ b/include/linux/range_lock.h
@@ -0,0 +1,51 @@
+/*
+ * Range locking
+ *
+ * We allow exclusive locking of arbitrary ranges. We guarantee that each
+ * range is locked only after all conflicting range locks requested previously
+ * have been unlocked. Thus we achieve fairness and avoid livelocks.
+ *
+ * The cost of lock and unlock of a range is O(log(R_all)+R_int) 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
+#include
+#include
+#include
+
+
+struct task_struct;
+
+struct range_lock {
+ struct interval_tree_node node;
+ struct task_struct *task;
+ /* Number of ranges which are blocking acquisition of the lock */
+ unsigned int blocking_ranges;
+};
+
+struct range_lock_tree {
+ struct rb_root root;
+ spinlock_t lock;
+};
+
+#define RANGE_LOCK_INITIALIZER(start, end) {\
+ .node = {\
+ .start = (start),\
+ .end = (end)\
+ }\
+}
+
+static inline void range_lock_tree_init(struct range_lock_tree *tree)
+{
+ tree->root = RB_ROOT;
+ spin_lock_init(>lock);
+}
+void range_lock_init(struct range_lock *lock, unsigned long start,
+unsigned long end);
+void range_lock(struct range_lock_tree *tree, struct range_lock *lock);
+void range_unlock(struct range_lock_tree *tree, struct range_lock *lock);
+#endif
diff --git a/lib/Kconfig b/lib/Kconfig
index a4766fee0017..29802dfd51de 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -355,20 +355,6 @@ config TEXTSEARCH_FSM
config BTREE
bool
-config INTERVAL_TREE
- bool
- help
- Simple, embeddable, interval-tree. Can find the start of an
- overlapping range in log(n) time and then iterate over all
- overlapping nodes. The algorithm is implemented as an
- augmented rbtree.
-
- See:
-
- Documentation/rbtree.txt
-
- for more information.
-
config ASSOCIATIVE_ARRAY
bool
help
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index f7dd8f1d4075..deb14201b3c1 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1643,7 +1643,6 @@ config RBTREE_TEST
config INTERVAL_TREE_TEST
tristate "Interval tree test"
depends on m && DEBUG_KERNEL
- select INTERVAL_TREE
help
A benchmark measuring the performance of the interval tree library
diff --git a/lib/Makefile b/lib/Makefile
index 51e1d761f0b9..7eafc7567306 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -13,7 +13,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
sha1.o md5.o irq_regs.o argv_split.o \
proportions.o flex_proportions.o ratelimit.o show_mem.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
-earlycpio.o seq_buf.o nmi_backtrace.o
+earlycpio.o seq_buf.o nmi_backtrace.o interval_tree.o range_lock.o
obj-$(CONFIG_ARCH_HAS_DEBUG_STRICT_USER_COPY_CHECKS) += usercopy.o
lib-$(CONFIG_MMU) += ioremap.o
@@ -63,7 +63,6 @@ CFLAGS_hweight.o = $(subst
$(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS))
obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
obj-$(CONFIG_BTREE) += btree.o
-obj-$(CONFIG_INTERVAL_TREE) +=
[PATCH, RFC 1/2] lib: Implement range locks
From: Jan Kara j...@suse.cz
Implement range locking using interval tree.
Signed-off-by: Jan Kara j...@suse.cz
Signed-off-by: Kirill A. Shutemov kirill.shute...@linux.intel.com
---
drivers/gpu/drm/Kconfig | 1 -
drivers/gpu/drm/i915/Kconfig | 1 -
include/linux/range_lock.h | 51 +
lib/Kconfig | 14
lib/Kconfig.debug| 1 -
lib/Makefile | 3 +-
lib/range_lock.c | 78
7 files changed, 130 insertions(+), 19 deletions(-)
create mode 100644 include/linux/range_lock.h
create mode 100644 lib/range_lock.c
diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig
index 06ae5008c5ed..1e02f73891fd 100644
--- a/drivers/gpu/drm/Kconfig
+++ b/drivers/gpu/drm/Kconfig
@@ -130,7 +130,6 @@ config DRM_RADEON
select POWER_SUPPLY
select HWMON
select BACKLIGHT_CLASS_DEVICE
- select INTERVAL_TREE
help
Choose this option if you have an ATI Radeon graphics card. There
are both PCI and AGP versions. You don't need to choose this to
diff --git a/drivers/gpu/drm/i915/Kconfig b/drivers/gpu/drm/i915/Kconfig
index eb87e2538861..c76525f8cbe9 100644
--- a/drivers/gpu/drm/i915/Kconfig
+++ b/drivers/gpu/drm/i915/Kconfig
@@ -5,7 +5,6 @@ config DRM_I915
depends on (AGP || AGP=n)
select INTEL_GTT
select AGP_INTEL if AGP
- select INTERVAL_TREE
# we need shmfs for the swappable backing store, and in particular
# the shmem_readpage() which depends upon tmpfs
select SHMEM
diff --git a/include/linux/range_lock.h b/include/linux/range_lock.h
new file mode 100644
index ..fe258a599676
--- /dev/null
+++ b/include/linux/range_lock.h
@@ -0,0 +1,51 @@
+/*
+ * Range locking
+ *
+ * We allow exclusive locking of arbitrary ranges. We guarantee that each
+ * range is locked only after all conflicting range locks requested previously
+ * have been unlocked. Thus we achieve fairness and avoid livelocks.
+ *
+ * The cost of lock and unlock of a range is O(log(R_all)+R_int) 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
+
+
+struct task_struct;
+
+struct range_lock {
+ struct interval_tree_node node;
+ struct task_struct *task;
+ /* Number of ranges which are blocking acquisition of the lock */
+ unsigned int blocking_ranges;
+};
+
+struct range_lock_tree {
+ struct rb_root root;
+ spinlock_t lock;
+};
+
+#define RANGE_LOCK_INITIALIZER(start, end) {\
+ .node = {\
+ .start = (start),\
+ .end = (end)\
+ }\
+}
+
+static inline void range_lock_tree_init(struct range_lock_tree *tree)
+{
+ tree-root = RB_ROOT;
+ spin_lock_init(tree-lock);
+}
+void range_lock_init(struct range_lock *lock, unsigned long start,
+unsigned long end);
+void range_lock(struct range_lock_tree *tree, struct range_lock *lock);
+void range_unlock(struct range_lock_tree *tree, struct range_lock *lock);
+#endif
diff --git a/lib/Kconfig b/lib/Kconfig
index a4766fee0017..29802dfd51de 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -355,20 +355,6 @@ config TEXTSEARCH_FSM
config BTREE
bool
-config INTERVAL_TREE
- bool
- help
- Simple, embeddable, interval-tree. Can find the start of an
- overlapping range in log(n) time and then iterate over all
- overlapping nodes. The algorithm is implemented as an
- augmented rbtree.
-
- See:
-
- Documentation/rbtree.txt
-
- for more information.
-
config ASSOCIATIVE_ARRAY
bool
help
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index f7dd8f1d4075..deb14201b3c1 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1643,7 +1643,6 @@ config RBTREE_TEST
config INTERVAL_TREE_TEST
tristate Interval tree test
depends on m DEBUG_KERNEL
- select INTERVAL_TREE
help
A benchmark measuring the performance of the interval tree library
diff --git a/lib/Makefile b/lib/Makefile
index 51e1d761f0b9..7eafc7567306 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -13,7 +13,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
sha1.o md5.o irq_regs.o argv_split.o \
proportions.o flex_proportions.o ratelimit.o show_mem.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
-earlycpio.o seq_buf.o nmi_backtrace.o
+earlycpio.o seq_buf.o nmi_backtrace.o interval_tree.o range_lock.o
obj-$(CONFIG_ARCH_HAS_DEBUG_STRICT_USER_COPY_CHECKS) += usercopy.o
lib-$(CONFIG_MMU) += ioremap.o
@@ -63,7 +63,6 @@ CFLAGS_hweight.o = $(subst
$(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS))
