Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1617655 > unrolled thread
| Started by | Davidlohr Bueso <dave@stgolabs.net> |
|---|---|
| First post | 2017-04-06 11:00 +0200 |
| Last post | 2017-04-06 12:30 +0200 |
| Articles | 9 — 4 participants |
Back to article view | Back to linux.kernel
[PATCH v2 -tip 0/6] locking: Introduce range reader/writer lock Davidlohr Bueso <dave@stgolabs.net> - 2017-04-06 11:00 +0200
[PATCH 6/6] staging/lustre: Use generic range rwlock Davidlohr Bueso <dave@stgolabs.net> - 2017-04-06 11:00 +0200
Re: [PATCH 6/6] staging/lustre: Use generic range rwlock "Dilger, Andreas" <andreas.dilger@intel.com> - 2017-04-07 12:10 +0200
[PATCH 4/6] locking/locktorture: Fix num reader/writer corner cases Davidlohr Bueso <dave@stgolabs.net> - 2017-04-06 11:00 +0200
[PATCH 1/6] interval-tree: Build unconditionally Davidlohr Bueso <dave@stgolabs.net> - 2017-04-06 11:00 +0200
[PATCH 2/6] locking: Introduce range reader/writer lock Davidlohr Bueso <dave@stgolabs.net> - 2017-04-06 11:00 +0200
Re: [PATCH 2/6] locking: Introduce range reader/writer lock Laurent Dufour <ldufour@linux.vnet.ibm.com> - 2017-04-06 11:10 +0200
Re: [PATCH 2/6] locking: Introduce range reader/writer lock Davidlohr Bueso <dave@stgolabs.net> - 2017-04-06 19:00 +0200
Re: [PATCH 2/6] locking: Introduce range reader/writer lock Peter Zijlstra <peterz@infradead.org> - 2017-04-06 12:30 +0200
| From | Davidlohr Bueso <dave@stgolabs.net> |
|---|---|
| Date | 2017-04-06 11:00 +0200 |
| Subject | [PATCH v2 -tip 0/6] locking: Introduce range reader/writer lock |
| Message-ID | <ttbh9-6aP-61@gated-at.bofh.it> |
Changes from v1 (https://lwn.net/Articles/716383/), all in patch 2:
- s/EXPORT_SYMBOL/EXPORT_SYMBOL_GPL
- Made the tree walks a foreach loop, instead of while.
- Fixed signal_pending() lockup issue for unaccounted waiters.
- Fixed initialization macros.
- Check condition before signal_pending in loop.
- Make building the interval-tree unconditionally a separate patch.
- More/better documentation.
- Added jack's reviewed-by.
- Renamed inf to full.
** What's still pending:
- Debug support (it's been a pain to use lockdep with range locking).
- Renaming the lock; I don't agree that rwlock's should have exclusivity
on such a generic name; maybe they should be called rwspinlocks :)
- lustre 32bit offset caveat.
Hi,
Here's a very tardy proposal for enhancements to Jan's original[1] range lock
using interval trees. Because at some point it would be awesome to switch mmap_sem
from rwsem to range rwlock, I've focused on making it sharable and performance
enhancements reducing the performance delta between this and conventional locks as
much as possible -- details in patch 2.
The rest of the patches adds support for testing the new lock and actually
makes use of it for lustre. It has passed quite a bit of artificial pounding and
I believe/hope it is in shape to consider.
Laurent, while there are some pending items Peter wants, it might be worth
using this series for any further mmap_sem testing.
Applies on top of tip v4.11-rc5
[1] https://lkml.org/lkml/2013/1/31/483
Thanks!
Davidlohr Bueso (6):
interval-tree: Build unconditionally
locking: Introduce range reader/writer lock
locking/locktorture: Fix rwsem reader_delay
locking/locktorture: Fix num reader/writer corner cases
locking/locktorture: Support range rwlocks
staging/lustre: Use generic range rwlock
drivers/gpu/drm/Kconfig | 2 -
drivers/gpu/drm/i915/Kconfig | 1 -
drivers/staging/lustre/lustre/llite/Makefile | 2 +-
drivers/staging/lustre/lustre/llite/file.c | 21 +-
.../staging/lustre/lustre/llite/llite_internal.h | 4 +-
drivers/staging/lustre/lustre/llite/llite_lib.c | 3 +-
drivers/staging/lustre/lustre/llite/range_lock.c | 239 ---------
drivers/staging/lustre/lustre/llite/range_lock.h | 82 ---
include/linux/range_rwlock.h | 115 +++++
kernel/locking/Makefile | 2 +-
kernel/locking/locktorture.c | 299 ++++++++---
kernel/locking/range_rwlock.c | 554 +++++++++++++++++++++
lib/Kconfig | 14 -
lib/Kconfig.debug | 1 -
lib/Makefile | 3 +-
15 files changed, 903 insertions(+), 439 deletions(-)
delete mode 100644 drivers/staging/lustre/lustre/llite/range_lock.c
delete mode 100644 drivers/staging/lustre/lustre/llite/range_lock.h
create mode 100644 include/linux/range_rwlock.h
create mode 100644 kernel/locking/range_rwlock.c
--
2.12.0
[toc] | [next] | [standalone]
| From | Davidlohr Bueso <dave@stgolabs.net> |
|---|---|
| Date | 2017-04-06 11:00 +0200 |
| Subject | [PATCH 6/6] staging/lustre: Use generic range rwlock |
| Message-ID | <ttbqO-6ei-19@gated-at.bofh.it> |
| In reply to | #1617655 |
This replaces the in-house version, which is also derived
from Jan's interval tree implementation.
Cc: oleg.drokin@intel.com
Cc: andreas.dilger@intel.com
Cc: jsimmons@infradead.org
Cc: lustre-devel@lists.lustre.org
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
drivers/staging/lustre/lustre/llite/Makefile | 2 +-
drivers/staging/lustre/lustre/llite/file.c | 21 +-
.../staging/lustre/lustre/llite/llite_internal.h | 4 +-
drivers/staging/lustre/lustre/llite/llite_lib.c | 3 +-
drivers/staging/lustre/lustre/llite/range_lock.c | 239 ---------------------
drivers/staging/lustre/lustre/llite/range_lock.h | 82 -------
6 files changed, 15 insertions(+), 336 deletions(-)
delete mode 100644 drivers/staging/lustre/lustre/llite/range_lock.c
delete mode 100644 drivers/staging/lustre/lustre/llite/range_lock.h
diff --git a/drivers/staging/lustre/lustre/llite/Makefile b/drivers/staging/lustre/lustre/llite/Makefile
index 322d4fa63f5d..922a901bc62c 100644
--- a/drivers/staging/lustre/lustre/llite/Makefile
+++ b/drivers/staging/lustre/lustre/llite/Makefile
@@ -1,6 +1,6 @@
obj-$(CONFIG_LUSTRE_FS) += lustre.o
lustre-y := dcache.o dir.o file.o llite_lib.o llite_nfs.o \
- rw.o rw26.o namei.o symlink.o llite_mmap.o range_lock.o \
+ rw.o rw26.o namei.o symlink.o llite_mmap.o \
xattr.o xattr_cache.o xattr_security.o \
super25.o statahead.o glimpse.o lcommon_cl.o lcommon_misc.o \
vvp_dev.o vvp_page.o vvp_lock.o vvp_io.o vvp_object.o \
diff --git a/drivers/staging/lustre/lustre/llite/file.c b/drivers/staging/lustre/lustre/llite/file.c
index 481c0d01d4c6..1a14a79f87f8 100644
--- a/drivers/staging/lustre/lustre/llite/file.c
+++ b/drivers/staging/lustre/lustre/llite/file.c
@@ -42,6 +42,7 @@
#include <linux/file.h>
#include <linux/sched.h>
#include <linux/mount.h>
+#include <linux/range_rwlock.h>
#include "../include/lustre/ll_fiemap.h"
#include "../include/lustre/lustre_ioctl.h"
#include "../include/lustre_swab.h"
@@ -1055,7 +1056,7 @@ ll_file_io_generic(const struct lu_env *env, struct vvp_io_args *args,
struct ll_inode_info *lli = ll_i2info(file_inode(file));
struct ll_file_data *fd = LUSTRE_FPRIVATE(file);
struct vvp_io *vio = vvp_env_io(env);
- struct range_lock range;
+ struct range_rwlock range;
struct cl_io *io;
ssize_t result = 0;
int rc = 0;
@@ -1072,9 +1073,9 @@ ll_file_io_generic(const struct lu_env *env, struct vvp_io_args *args,
bool range_locked = false;
if (file->f_flags & O_APPEND)
- range_lock_init(&range, 0, LUSTRE_EOF);
+ range_rwlock_init(&range, 0, LUSTRE_EOF);
else
- range_lock_init(&range, *ppos, *ppos + count - 1);
+ range_rwlock_init(&range, *ppos, *ppos + count - 1);
vio->vui_fd = LUSTRE_FPRIVATE(file);
vio->vui_iter = args->u.normal.via_iter;
@@ -1087,10 +1088,9 @@ ll_file_io_generic(const struct lu_env *env, struct vvp_io_args *args,
if (((iot == CIT_WRITE) ||
(iot == CIT_READ && (file->f_flags & O_DIRECT))) &&
!(vio->vui_fd->fd_flags & LL_FILE_GROUP_LOCKED)) {
- CDEBUG(D_VFSTRACE, "Range lock [%llu, %llu]\n",
- range.rl_node.in_extent.start,
- range.rl_node.in_extent.end);
- rc = range_lock(&lli->lli_write_tree, &range);
+ CDEBUG(D_VFSTRACE, "Range lock [%lu, %lu]\n",
+ range.node.start, range.node.last);
+ rc = range_write_lock_interruptible(&lli->lli_write_tree, &range);
if (rc < 0)
goto out;
@@ -1100,10 +1100,9 @@ ll_file_io_generic(const struct lu_env *env, struct vvp_io_args *args,
rc = cl_io_loop(env, io);
ll_cl_remove(file, env);
if (range_locked) {
- CDEBUG(D_VFSTRACE, "Range unlock [%llu, %llu]\n",
- range.rl_node.in_extent.start,
- range.rl_node.in_extent.end);
- range_unlock(&lli->lli_write_tree, &range);
+ CDEBUG(D_VFSTRACE, "Range unlock [%lu, %lu]\n",
+ range.node.start, range.node.last);
+ range_write_unlock(&lli->lli_write_tree, &range);
}
} else {
/* cl_io_rw_init() handled IO */
diff --git a/drivers/staging/lustre/lustre/llite/llite_internal.h b/drivers/staging/lustre/lustre/llite/llite_internal.h
index 55f68acd85d1..aa2ae72e3e70 100644
--- a/drivers/staging/lustre/lustre/llite/llite_internal.h
+++ b/drivers/staging/lustre/lustre/llite/llite_internal.h
@@ -49,8 +49,8 @@
#include <linux/namei.h>
#include <linux/xattr.h>
#include <linux/posix_acl_xattr.h>
+#include <linux/range_rwlock.h>
#include "vvp_internal.h"
-#include "range_lock.h"
#ifndef FMODE_EXEC
#define FMODE_EXEC 0
@@ -193,7 +193,7 @@ struct ll_inode_info {
* }
*/
struct rw_semaphore lli_trunc_sem;
- struct range_lock_tree lli_write_tree;
+ struct range_rwlock_tree lli_write_tree;
struct rw_semaphore lli_glimpse_sem;
unsigned long lli_glimpse_time;
diff --git a/drivers/staging/lustre/lustre/llite/llite_lib.c b/drivers/staging/lustre/lustre/llite/llite_lib.c
index b229cbc7bb33..8054e916b3f5 100644
--- a/drivers/staging/lustre/lustre/llite/llite_lib.c
+++ b/drivers/staging/lustre/lustre/llite/llite_lib.c
@@ -40,6 +40,7 @@
#include <linux/statfs.h>
#include <linux/types.h>
#include <linux/mm.h>
+#include <linux/range_rwlock.h>
#include "../include/lustre/lustre_ioctl.h"
#include "../include/lustre_ha.h"
@@ -853,7 +854,7 @@ void ll_lli_init(struct ll_inode_info *lli)
mutex_init(&lli->lli_size_mutex);
lli->lli_symlink_name = NULL;
init_rwsem(&lli->lli_trunc_sem);
- range_lock_tree_init(&lli->lli_write_tree);
+ range_rwlock_tree_init(&lli->lli_write_tree);
init_rwsem(&lli->lli_glimpse_sem);
lli->lli_glimpse_time = 0;
INIT_LIST_HEAD(&lli->lli_agl_list);
diff --git a/drivers/staging/lustre/lustre/llite/range_lock.c b/drivers/staging/lustre/lustre/llite/range_lock.c
deleted file mode 100644
index 14148a097476..000000000000
--- a/drivers/staging/lustre/lustre/llite/range_lock.c
+++ /dev/null
@@ -1,239 +0,0 @@
-/*
- * GPL HEADER START
- *
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 only,
- * as published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License version 2 for more details (a copy is included
- * in the LICENSE file that accompanied this code).
- *
- * You should have received a copy of the GNU General Public License
- * version 2 along with this program; If not, see
- * http://www.gnu.org/licenses/gpl-2.0.html
- *
- * GPL HEADER END
- */
-/*
- * Range lock is used to allow multiple threads writing a single shared
- * file given each thread is writing to a non-overlapping portion of the
- * file.
- *
- * Refer to the possible upstream kernel version of range lock by
- * Jan Kara <jack@suse.cz>: https://lkml.org/lkml/2013/1/31/480
- *
- * This file could later replaced by the upstream kernel version.
- */
-/*
- * Author: Prakash Surya <surya1@llnl.gov>
- * Author: Bobi Jam <bobijam.xu@intel.com>
- */
-#include "range_lock.h"
-#include "../include/lustre/lustre_user.h"
-
-/**
- * Initialize a range lock tree
- *
- * \param tree [in] an empty range lock tree
- *
- * Pre: Caller should have allocated the range lock tree.
- * Post: The range lock tree is ready to function.
- */
-void range_lock_tree_init(struct range_lock_tree *tree)
-{
- tree->rlt_root = NULL;
- tree->rlt_sequence = 0;
- spin_lock_init(&tree->rlt_lock);
-}
-
-/**
- * Initialize a range lock node
- *
- * \param lock [in] an empty range lock node
- * \param start [in] start of the covering region
- * \param end [in] end of the covering region
- *
- * Pre: Caller should have allocated the range lock node.
- * Post: The range lock node is meant to cover [start, end] region
- */
-int range_lock_init(struct range_lock *lock, __u64 start, __u64 end)
-{
- int rc;
-
- memset(&lock->rl_node, 0, sizeof(lock->rl_node));
- if (end != LUSTRE_EOF)
- end >>= PAGE_SHIFT;
- rc = interval_set(&lock->rl_node, start >> PAGE_SHIFT, end);
- if (rc)
- return rc;
-
- INIT_LIST_HEAD(&lock->rl_next_lock);
- lock->rl_task = NULL;
- lock->rl_lock_count = 0;
- lock->rl_blocking_ranges = 0;
- lock->rl_sequence = 0;
- return rc;
-}
-
-static inline struct range_lock *next_lock(struct range_lock *lock)
-{
- return list_entry(lock->rl_next_lock.next, typeof(*lock), rl_next_lock);
-}
-
-/**
- * Helper function of range_unlock()
- *
- * \param node [in] a range lock found overlapped during interval node
- * search
- * \param arg [in] the range lock to be tested
- *
- * \retval INTERVAL_ITER_CONT indicate to continue the search for next
- * overlapping range node
- * \retval INTERVAL_ITER_STOP indicate to stop the search
- */
-static enum interval_iter range_unlock_cb(struct interval_node *node, void *arg)
-{
- struct range_lock *lock = arg;
- struct range_lock *overlap = node2rangelock(node);
- struct range_lock *iter;
-
- list_for_each_entry(iter, &overlap->rl_next_lock, rl_next_lock) {
- if (iter->rl_sequence > lock->rl_sequence) {
- --iter->rl_blocking_ranges;
- LASSERT(iter->rl_blocking_ranges > 0);
- }
- }
- if (overlap->rl_sequence > lock->rl_sequence) {
- --overlap->rl_blocking_ranges;
- if (overlap->rl_blocking_ranges == 0)
- wake_up_process(overlap->rl_task);
- }
- return INTERVAL_ITER_CONT;
-}
-
-/**
- * Unlock a range lock, wake up locks blocked by this lock.
- *
- * \param tree [in] range lock tree
- * \param lock [in] range lock to be deleted
- *
- * If this lock has been granted, relase it; if not, just delete it from
- * the tree or the same region lock list. Wake up those locks only blocked
- * by this lock through range_unlock_cb().
- */
-void range_unlock(struct range_lock_tree *tree, struct range_lock *lock)
-{
- spin_lock(&tree->rlt_lock);
- if (!list_empty(&lock->rl_next_lock)) {
- struct range_lock *next;
-
- if (interval_is_intree(&lock->rl_node)) { /* first lock */
- /* Insert the next same range lock into the tree */
- next = next_lock(lock);
- next->rl_lock_count = lock->rl_lock_count - 1;
- interval_erase(&lock->rl_node, &tree->rlt_root);
- interval_insert(&next->rl_node, &tree->rlt_root);
- } else {
- /* find the first lock in tree */
- list_for_each_entry(next, &lock->rl_next_lock,
- rl_next_lock) {
- if (!interval_is_intree(&next->rl_node))
- continue;
-
- LASSERT(next->rl_lock_count > 0);
- next->rl_lock_count--;
- break;
- }
- }
- list_del_init(&lock->rl_next_lock);
- } else {
- LASSERT(interval_is_intree(&lock->rl_node));
- interval_erase(&lock->rl_node, &tree->rlt_root);
- }
-
- interval_search(tree->rlt_root, &lock->rl_node.in_extent,
- range_unlock_cb, lock);
- spin_unlock(&tree->rlt_lock);
-}
-
-/**
- * Helper function of range_lock()
- *
- * \param node [in] a range lock found overlapped during interval node
- * search
- * \param arg [in] the range lock to be tested
- *
- * \retval INTERVAL_ITER_CONT indicate to continue the search for next
- * overlapping range node
- * \retval INTERVAL_ITER_STOP indicate to stop the search
- */
-static enum interval_iter range_lock_cb(struct interval_node *node, void *arg)
-{
- struct range_lock *lock = (struct range_lock *)arg;
- struct range_lock *overlap = node2rangelock(node);
-
- lock->rl_blocking_ranges += overlap->rl_lock_count + 1;
- return INTERVAL_ITER_CONT;
-}
-
-/**
- * Lock a region
- *
- * \param tree [in] range lock tree
- * \param lock [in] range lock node containing the region span
- *
- * \retval 0 get the range lock
- * \retval <0 error code while not getting the range lock
- *
- * If there exists overlapping range lock, the new lock will wait and
- * retry, if later it find that it is not the chosen one to wake up,
- * it wait again.
- */
-int range_lock(struct range_lock_tree *tree, struct range_lock *lock)
-{
- struct interval_node *node;
- int rc = 0;
-
- spin_lock(&tree->rlt_lock);
- /*
- * We need to check for all conflicting intervals
- * already in the tree.
- */
- interval_search(tree->rlt_root, &lock->rl_node.in_extent,
- range_lock_cb, lock);
- /*
- * Insert to the tree if I am unique, otherwise I've been linked to
- * the rl_next_lock of another lock which has the same range as mine
- * in range_lock_cb().
- */
- node = interval_insert(&lock->rl_node, &tree->rlt_root);
- if (node) {
- struct range_lock *tmp = node2rangelock(node);
-
- list_add_tail(&lock->rl_next_lock, &tmp->rl_next_lock);
- tmp->rl_lock_count++;
- }
- lock->rl_sequence = ++tree->rlt_sequence;
-
- while (lock->rl_blocking_ranges > 0) {
- lock->rl_task = current;
- __set_current_state(TASK_INTERRUPTIBLE);
- spin_unlock(&tree->rlt_lock);
- schedule();
-
- if (signal_pending(current)) {
- range_unlock(tree, lock);
- rc = -EINTR;
- goto out;
- }
- spin_lock(&tree->rlt_lock);
- }
- spin_unlock(&tree->rlt_lock);
-out:
- return rc;
-}
diff --git a/drivers/staging/lustre/lustre/llite/range_lock.h b/drivers/staging/lustre/lustre/llite/range_lock.h
deleted file mode 100644
index 779091ccec4e..000000000000
--- a/drivers/staging/lustre/lustre/llite/range_lock.h
+++ /dev/null
@@ -1,82 +0,0 @@
-/*
- * GPL HEADER START
- *
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 only,
- * as published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License version 2 for more details (a copy is included
- * in the LICENSE file that accompanied this code).
- *
- * You should have received a copy of the GNU General Public License
- * version 2 along with this program; If not, see
- * http://www.gnu.org/licenses/gpl-2.0.html
- *
- * GPL HEADER END
- */
-/*
- * Range lock is used to allow multiple threads writing a single shared
- * file given each thread is writing to a non-overlapping portion of the
- * file.
- *
- * Refer to the possible upstream kernel version of range lock by
- * Jan Kara <jack@suse.cz>: https://lkml.org/lkml/2013/1/31/480
- *
- * This file could later replaced by the upstream kernel version.
- */
-/*
- * Author: Prakash Surya <surya1@llnl.gov>
- * Author: Bobi Jam <bobijam.xu@intel.com>
- */
-#ifndef _RANGE_LOCK_H
-#define _RANGE_LOCK_H
-
-#include "../../include/linux/libcfs/libcfs.h"
-#include "../include/interval_tree.h"
-
-struct range_lock {
- struct interval_node rl_node;
- /**
- * Process to enqueue this lock.
- */
- struct task_struct *rl_task;
- /**
- * List of locks with the same range.
- */
- struct list_head rl_next_lock;
- /**
- * Number of locks in the list rl_next_lock
- */
- unsigned int rl_lock_count;
- /**
- * Number of ranges which are blocking acquisition of the lock
- */
- unsigned int rl_blocking_ranges;
- /**
- * Sequence number of range lock. This number is used to get to know
- * the order the locks are queued; this is required for range_cancel().
- */
- __u64 rl_sequence;
-};
-
-static inline struct range_lock *node2rangelock(const struct interval_node *n)
-{
- return container_of(n, struct range_lock, rl_node);
-}
-
-struct range_lock_tree {
- struct interval_node *rlt_root;
- spinlock_t rlt_lock; /* protect range lock tree */
- __u64 rlt_sequence;
-};
-
-void range_lock_tree_init(struct range_lock_tree *tree);
-int range_lock_init(struct range_lock *lock, __u64 start, __u64 end);
-int range_lock(struct range_lock_tree *tree, struct range_lock *lock);
-void range_unlock(struct range_lock_tree *tree, struct range_lock *lock);
-#endif
--
2.12.0
[toc] | [prev] | [next] | [standalone]
| From | "Dilger, Andreas" <andreas.dilger@intel.com> |
|---|---|
| Date | 2017-04-07 12:10 +0200 |
| Subject | Re: [PATCH 6/6] staging/lustre: Use generic range rwlock |
| Message-ID | <ttz06-5HY-19@gated-at.bofh.it> |
| In reply to | #1617661 |
On Apr 6, 2017, at 02:46, Davidlohr Bueso <dave@stgolabs.net> wrote:
>
> This replaces the in-house version, which is also derived
> from Jan's interval tree implementation.
>
> Cc: oleg.drokin@intel.com
> Cc: andreas.dilger@intel.com
> Cc: jsimmons@infradead.org
> Cc: lustre-devel@lists.lustre.org
> Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
This patch looks fine, but it would probably be better to also post the whole series on
linux-fsdevel for further review.
Cheers, Andreas
> ---
> drivers/staging/lustre/lustre/llite/Makefile | 2 +-
> drivers/staging/lustre/lustre/llite/file.c | 21 +-
> .../staging/lustre/lustre/llite/llite_internal.h | 4 +-
> drivers/staging/lustre/lustre/llite/llite_lib.c | 3 +-
> drivers/staging/lustre/lustre/llite/range_lock.c | 239 ---------------------
> drivers/staging/lustre/lustre/llite/range_lock.h | 82 -------
> 6 files changed, 15 insertions(+), 336 deletions(-)
> delete mode 100644 drivers/staging/lustre/lustre/llite/range_lock.c
> delete mode 100644 drivers/staging/lustre/lustre/llite/range_lock.h
>
> diff --git a/drivers/staging/lustre/lustre/llite/Makefile b/drivers/staging/lustre/lustre/llite/Makefile
> index 322d4fa63f5d..922a901bc62c 100644
> --- a/drivers/staging/lustre/lustre/llite/Makefile
> +++ b/drivers/staging/lustre/lustre/llite/Makefile
> @@ -1,6 +1,6 @@
> obj-$(CONFIG_LUSTRE_FS) += lustre.o
> lustre-y := dcache.o dir.o file.o llite_lib.o llite_nfs.o \
> - rw.o rw26.o namei.o symlink.o llite_mmap.o range_lock.o \
> + rw.o rw26.o namei.o symlink.o llite_mmap.o \
> xattr.o xattr_cache.o xattr_security.o \
> super25.o statahead.o glimpse.o lcommon_cl.o lcommon_misc.o \
> vvp_dev.o vvp_page.o vvp_lock.o vvp_io.o vvp_object.o \
> diff --git a/drivers/staging/lustre/lustre/llite/file.c b/drivers/staging/lustre/lustre/llite/file.c
> index 481c0d01d4c6..1a14a79f87f8 100644
> --- a/drivers/staging/lustre/lustre/llite/file.c
> +++ b/drivers/staging/lustre/lustre/llite/file.c
> @@ -42,6 +42,7 @@
> #include <linux/file.h>
> #include <linux/sched.h>
> #include <linux/mount.h>
> +#include <linux/range_rwlock.h>
> #include "../include/lustre/ll_fiemap.h"
> #include "../include/lustre/lustre_ioctl.h"
> #include "../include/lustre_swab.h"
> @@ -1055,7 +1056,7 @@ ll_file_io_generic(const struct lu_env *env, struct vvp_io_args *args,
> struct ll_inode_info *lli = ll_i2info(file_inode(file));
> struct ll_file_data *fd = LUSTRE_FPRIVATE(file);
> struct vvp_io *vio = vvp_env_io(env);
> - struct range_lock range;
> + struct range_rwlock range;
> struct cl_io *io;
> ssize_t result = 0;
> int rc = 0;
> @@ -1072,9 +1073,9 @@ ll_file_io_generic(const struct lu_env *env, struct vvp_io_args *args,
> bool range_locked = false;
>
> if (file->f_flags & O_APPEND)
> - range_lock_init(&range, 0, LUSTRE_EOF);
> + range_rwlock_init(&range, 0, LUSTRE_EOF);
> else
> - range_lock_init(&range, *ppos, *ppos + count - 1);
> + range_rwlock_init(&range, *ppos, *ppos + count - 1);
>
> vio->vui_fd = LUSTRE_FPRIVATE(file);
> vio->vui_iter = args->u.normal.via_iter;
> @@ -1087,10 +1088,9 @@ ll_file_io_generic(const struct lu_env *env, struct vvp_io_args *args,
> if (((iot == CIT_WRITE) ||
> (iot == CIT_READ && (file->f_flags & O_DIRECT))) &&
> !(vio->vui_fd->fd_flags & LL_FILE_GROUP_LOCKED)) {
> - CDEBUG(D_VFSTRACE, "Range lock [%llu, %llu]\n",
> - range.rl_node.in_extent.start,
> - range.rl_node.in_extent.end);
> - rc = range_lock(&lli->lli_write_tree, &range);
> + CDEBUG(D_VFSTRACE, "Range lock [%lu, %lu]\n",
> + range.node.start, range.node.last);
> + rc = range_write_lock_interruptible(&lli->lli_write_tree, &range);
> if (rc < 0)
> goto out;
>
> @@ -1100,10 +1100,9 @@ ll_file_io_generic(const struct lu_env *env, struct vvp_io_args *args,
> rc = cl_io_loop(env, io);
> ll_cl_remove(file, env);
> if (range_locked) {
> - CDEBUG(D_VFSTRACE, "Range unlock [%llu, %llu]\n",
> - range.rl_node.in_extent.start,
> - range.rl_node.in_extent.end);
> - range_unlock(&lli->lli_write_tree, &range);
> + CDEBUG(D_VFSTRACE, "Range unlock [%lu, %lu]\n",
> + range.node.start, range.node.last);
> + range_write_unlock(&lli->lli_write_tree, &range);
> }
> } else {
> /* cl_io_rw_init() handled IO */
> diff --git a/drivers/staging/lustre/lustre/llite/llite_internal.h b/drivers/staging/lustre/lustre/llite/llite_internal.h
> index 55f68acd85d1..aa2ae72e3e70 100644
> --- a/drivers/staging/lustre/lustre/llite/llite_internal.h
> +++ b/drivers/staging/lustre/lustre/llite/llite_internal.h
> @@ -49,8 +49,8 @@
> #include <linux/namei.h>
> #include <linux/xattr.h>
> #include <linux/posix_acl_xattr.h>
> +#include <linux/range_rwlock.h>
> #include "vvp_internal.h"
> -#include "range_lock.h"
>
> #ifndef FMODE_EXEC
> #define FMODE_EXEC 0
> @@ -193,7 +193,7 @@ struct ll_inode_info {
> * }
> */
> struct rw_semaphore lli_trunc_sem;
> - struct range_lock_tree lli_write_tree;
> + struct range_rwlock_tree lli_write_tree;
>
> struct rw_semaphore lli_glimpse_sem;
> unsigned long lli_glimpse_time;
> diff --git a/drivers/staging/lustre/lustre/llite/llite_lib.c b/drivers/staging/lustre/lustre/llite/llite_lib.c
> index b229cbc7bb33..8054e916b3f5 100644
> --- a/drivers/staging/lustre/lustre/llite/llite_lib.c
> +++ b/drivers/staging/lustre/lustre/llite/llite_lib.c
> @@ -40,6 +40,7 @@
> #include <linux/statfs.h>
> #include <linux/types.h>
> #include <linux/mm.h>
> +#include <linux/range_rwlock.h>
>
> #include "../include/lustre/lustre_ioctl.h"
> #include "../include/lustre_ha.h"
> @@ -853,7 +854,7 @@ void ll_lli_init(struct ll_inode_info *lli)
> mutex_init(&lli->lli_size_mutex);
> lli->lli_symlink_name = NULL;
> init_rwsem(&lli->lli_trunc_sem);
> - range_lock_tree_init(&lli->lli_write_tree);
> + range_rwlock_tree_init(&lli->lli_write_tree);
> init_rwsem(&lli->lli_glimpse_sem);
> lli->lli_glimpse_time = 0;
> INIT_LIST_HEAD(&lli->lli_agl_list);
> diff --git a/drivers/staging/lustre/lustre/llite/range_lock.c b/drivers/staging/lustre/lustre/llite/range_lock.c
> deleted file mode 100644
> index 14148a097476..000000000000
> --- a/drivers/staging/lustre/lustre/llite/range_lock.c
> +++ /dev/null
> @@ -1,239 +0,0 @@
> -/*
> - * GPL HEADER START
> - *
> - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
> - *
> - * This program is free software; you can redistribute it and/or modify
> - * it under the terms of the GNU General Public License version 2 only,
> - * as published by the Free Software Foundation.
> - *
> - * This program is distributed in the hope that it will be useful, but
> - * WITHOUT ANY WARRANTY; without even the implied warranty of
> - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> - * General Public License version 2 for more details (a copy is included
> - * in the LICENSE file that accompanied this code).
> - *
> - * You should have received a copy of the GNU General Public License
> - * version 2 along with this program; If not, see
> - * http://www.gnu.org/licenses/gpl-2.0.html
> - *
> - * GPL HEADER END
> - */
> -/*
> - * Range lock is used to allow multiple threads writing a single shared
> - * file given each thread is writing to a non-overlapping portion of the
> - * file.
> - *
> - * Refer to the possible upstream kernel version of range lock by
> - * Jan Kara <jack@suse.cz>: https://lkml.org/lkml/2013/1/31/480
> - *
> - * This file could later replaced by the upstream kernel version.
> - */
> -/*
> - * Author: Prakash Surya <surya1@llnl.gov>
> - * Author: Bobi Jam <bobijam.xu@intel.com>
> - */
> -#include "range_lock.h"
> -#include "../include/lustre/lustre_user.h"
> -
> -/**
> - * Initialize a range lock tree
> - *
> - * \param tree [in] an empty range lock tree
> - *
> - * Pre: Caller should have allocated the range lock tree.
> - * Post: The range lock tree is ready to function.
> - */
> -void range_lock_tree_init(struct range_lock_tree *tree)
> -{
> - tree->rlt_root = NULL;
> - tree->rlt_sequence = 0;
> - spin_lock_init(&tree->rlt_lock);
> -}
> -
> -/**
> - * Initialize a range lock node
> - *
> - * \param lock [in] an empty range lock node
> - * \param start [in] start of the covering region
> - * \param end [in] end of the covering region
> - *
> - * Pre: Caller should have allocated the range lock node.
> - * Post: The range lock node is meant to cover [start, end] region
> - */
> -int range_lock_init(struct range_lock *lock, __u64 start, __u64 end)
> -{
> - int rc;
> -
> - memset(&lock->rl_node, 0, sizeof(lock->rl_node));
> - if (end != LUSTRE_EOF)
> - end >>= PAGE_SHIFT;
> - rc = interval_set(&lock->rl_node, start >> PAGE_SHIFT, end);
> - if (rc)
> - return rc;
> -
> - INIT_LIST_HEAD(&lock->rl_next_lock);
> - lock->rl_task = NULL;
> - lock->rl_lock_count = 0;
> - lock->rl_blocking_ranges = 0;
> - lock->rl_sequence = 0;
> - return rc;
> -}
> -
> -static inline struct range_lock *next_lock(struct range_lock *lock)
> -{
> - return list_entry(lock->rl_next_lock.next, typeof(*lock), rl_next_lock);
> -}
> -
> -/**
> - * Helper function of range_unlock()
> - *
> - * \param node [in] a range lock found overlapped during interval node
> - * search
> - * \param arg [in] the range lock to be tested
> - *
> - * \retval INTERVAL_ITER_CONT indicate to continue the search for next
> - * overlapping range node
> - * \retval INTERVAL_ITER_STOP indicate to stop the search
> - */
> -static enum interval_iter range_unlock_cb(struct interval_node *node, void *arg)
> -{
> - struct range_lock *lock = arg;
> - struct range_lock *overlap = node2rangelock(node);
> - struct range_lock *iter;
> -
> - list_for_each_entry(iter, &overlap->rl_next_lock, rl_next_lock) {
> - if (iter->rl_sequence > lock->rl_sequence) {
> - --iter->rl_blocking_ranges;
> - LASSERT(iter->rl_blocking_ranges > 0);
> - }
> - }
> - if (overlap->rl_sequence > lock->rl_sequence) {
> - --overlap->rl_blocking_ranges;
> - if (overlap->rl_blocking_ranges == 0)
> - wake_up_process(overlap->rl_task);
> - }
> - return INTERVAL_ITER_CONT;
> -}
> -
> -/**
> - * Unlock a range lock, wake up locks blocked by this lock.
> - *
> - * \param tree [in] range lock tree
> - * \param lock [in] range lock to be deleted
> - *
> - * If this lock has been granted, relase it; if not, just delete it from
> - * the tree or the same region lock list. Wake up those locks only blocked
> - * by this lock through range_unlock_cb().
> - */
> -void range_unlock(struct range_lock_tree *tree, struct range_lock *lock)
> -{
> - spin_lock(&tree->rlt_lock);
> - if (!list_empty(&lock->rl_next_lock)) {
> - struct range_lock *next;
> -
> - if (interval_is_intree(&lock->rl_node)) { /* first lock */
> - /* Insert the next same range lock into the tree */
> - next = next_lock(lock);
> - next->rl_lock_count = lock->rl_lock_count - 1;
> - interval_erase(&lock->rl_node, &tree->rlt_root);
> - interval_insert(&next->rl_node, &tree->rlt_root);
> - } else {
> - /* find the first lock in tree */
> - list_for_each_entry(next, &lock->rl_next_lock,
> - rl_next_lock) {
> - if (!interval_is_intree(&next->rl_node))
> - continue;
> -
> - LASSERT(next->rl_lock_count > 0);
> - next->rl_lock_count--;
> - break;
> - }
> - }
> - list_del_init(&lock->rl_next_lock);
> - } else {
> - LASSERT(interval_is_intree(&lock->rl_node));
> - interval_erase(&lock->rl_node, &tree->rlt_root);
> - }
> -
> - interval_search(tree->rlt_root, &lock->rl_node.in_extent,
> - range_unlock_cb, lock);
> - spin_unlock(&tree->rlt_lock);
> -}
> -
> -/**
> - * Helper function of range_lock()
> - *
> - * \param node [in] a range lock found overlapped during interval node
> - * search
> - * \param arg [in] the range lock to be tested
> - *
> - * \retval INTERVAL_ITER_CONT indicate to continue the search for next
> - * overlapping range node
> - * \retval INTERVAL_ITER_STOP indicate to stop the search
> - */
> -static enum interval_iter range_lock_cb(struct interval_node *node, void *arg)
> -{
> - struct range_lock *lock = (struct range_lock *)arg;
> - struct range_lock *overlap = node2rangelock(node);
> -
> - lock->rl_blocking_ranges += overlap->rl_lock_count + 1;
> - return INTERVAL_ITER_CONT;
> -}
> -
> -/**
> - * Lock a region
> - *
> - * \param tree [in] range lock tree
> - * \param lock [in] range lock node containing the region span
> - *
> - * \retval 0 get the range lock
> - * \retval <0 error code while not getting the range lock
> - *
> - * If there exists overlapping range lock, the new lock will wait and
> - * retry, if later it find that it is not the chosen one to wake up,
> - * it wait again.
> - */
> -int range_lock(struct range_lock_tree *tree, struct range_lock *lock)
> -{
> - struct interval_node *node;
> - int rc = 0;
> -
> - spin_lock(&tree->rlt_lock);
> - /*
> - * We need to check for all conflicting intervals
> - * already in the tree.
> - */
> - interval_search(tree->rlt_root, &lock->rl_node.in_extent,
> - range_lock_cb, lock);
> - /*
> - * Insert to the tree if I am unique, otherwise I've been linked to
> - * the rl_next_lock of another lock which has the same range as mine
> - * in range_lock_cb().
> - */
> - node = interval_insert(&lock->rl_node, &tree->rlt_root);
> - if (node) {
> - struct range_lock *tmp = node2rangelock(node);
> -
> - list_add_tail(&lock->rl_next_lock, &tmp->rl_next_lock);
> - tmp->rl_lock_count++;
> - }
> - lock->rl_sequence = ++tree->rlt_sequence;
> -
> - while (lock->rl_blocking_ranges > 0) {
> - lock->rl_task = current;
> - __set_current_state(TASK_INTERRUPTIBLE);
> - spin_unlock(&tree->rlt_lock);
> - schedule();
> -
> - if (signal_pending(current)) {
> - range_unlock(tree, lock);
> - rc = -EINTR;
> - goto out;
> - }
> - spin_lock(&tree->rlt_lock);
> - }
> - spin_unlock(&tree->rlt_lock);
> -out:
> - return rc;
> -}
> diff --git a/drivers/staging/lustre/lustre/llite/range_lock.h b/drivers/staging/lustre/lustre/llite/range_lock.h
> deleted file mode 100644
> index 779091ccec4e..000000000000
> --- a/drivers/staging/lustre/lustre/llite/range_lock.h
> +++ /dev/null
> @@ -1,82 +0,0 @@
> -/*
> - * GPL HEADER START
> - *
> - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
> - *
> - * This program is free software; you can redistribute it and/or modify
> - * it under the terms of the GNU General Public License version 2 only,
> - * as published by the Free Software Foundation.
> - *
> - * This program is distributed in the hope that it will be useful, but
> - * WITHOUT ANY WARRANTY; without even the implied warranty of
> - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> - * General Public License version 2 for more details (a copy is included
> - * in the LICENSE file that accompanied this code).
> - *
> - * You should have received a copy of the GNU General Public License
> - * version 2 along with this program; If not, see
> - * http://www.gnu.org/licenses/gpl-2.0.html
> - *
> - * GPL HEADER END
> - */
> -/*
> - * Range lock is used to allow multiple threads writing a single shared
> - * file given each thread is writing to a non-overlapping portion of the
> - * file.
> - *
> - * Refer to the possible upstream kernel version of range lock by
> - * Jan Kara <jack@suse.cz>: https://lkml.org/lkml/2013/1/31/480
> - *
> - * This file could later replaced by the upstream kernel version.
> - */
> -/*
> - * Author: Prakash Surya <surya1@llnl.gov>
> - * Author: Bobi Jam <bobijam.xu@intel.com>
> - */
> -#ifndef _RANGE_LOCK_H
> -#define _RANGE_LOCK_H
> -
> -#include "../../include/linux/libcfs/libcfs.h"
> -#include "../include/interval_tree.h"
> -
> -struct range_lock {
> - struct interval_node rl_node;
> - /**
> - * Process to enqueue this lock.
> - */
> - struct task_struct *rl_task;
> - /**
> - * List of locks with the same range.
> - */
> - struct list_head rl_next_lock;
> - /**
> - * Number of locks in the list rl_next_lock
> - */
> - unsigned int rl_lock_count;
> - /**
> - * Number of ranges which are blocking acquisition of the lock
> - */
> - unsigned int rl_blocking_ranges;
> - /**
> - * Sequence number of range lock. This number is used to get to know
> - * the order the locks are queued; this is required for range_cancel().
> - */
> - __u64 rl_sequence;
> -};
> -
> -static inline struct range_lock *node2rangelock(const struct interval_node *n)
> -{
> - return container_of(n, struct range_lock, rl_node);
> -}
> -
> -struct range_lock_tree {
> - struct interval_node *rlt_root;
> - spinlock_t rlt_lock; /* protect range lock tree */
> - __u64 rlt_sequence;
> -};
> -
> -void range_lock_tree_init(struct range_lock_tree *tree);
> -int range_lock_init(struct range_lock *lock, __u64 start, __u64 end);
> -int range_lock(struct range_lock_tree *tree, struct range_lock *lock);
> -void range_unlock(struct range_lock_tree *tree, struct range_lock *lock);
> -#endif
> --
> 2.12.0
>
Cheers, Andreas
--
Andreas Dilger
Lustre Principal Architect
Intel Corporation
[toc] | [prev] | [next] | [standalone]
| From | Davidlohr Bueso <dave@stgolabs.net> |
|---|---|
| Date | 2017-04-06 11:00 +0200 |
| Subject | [PATCH 4/6] locking/locktorture: Fix num reader/writer corner cases |
| Message-ID | <ttbqO-6ei-33@gated-at.bofh.it> |
| In reply to | #1617655 |
Things can explode for locktorture if the user does combinations
of nwriters_stress=0 nreaders_stress=0. Fix this by not assuming
we always want to torture writer threads.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
kernel/locking/locktorture.c | 76 +++++++++++++++++++++++++-------------------
1 file changed, 44 insertions(+), 32 deletions(-)
diff --git a/kernel/locking/locktorture.c b/kernel/locking/locktorture.c
index 0ef5510f8742..a68167803eee 100644
--- a/kernel/locking/locktorture.c
+++ b/kernel/locking/locktorture.c
@@ -715,8 +715,7 @@ static void __torture_print_stats(char *page,
{
bool fail = 0;
int i, n_stress;
- long max = 0;
- long min = statp[0].n_lock_acquired;
+ long max = 0, min = statp ? statp[0].n_lock_acquired : 0;
long long sum = 0;
n_stress = write ? cxt.nrealwriters_stress : cxt.nrealreaders_stress;
@@ -823,7 +822,7 @@ static void lock_torture_cleanup(void)
* such, only perform the underlying torture-specific cleanups,
* and avoid anything related to locktorture.
*/
- if (!cxt.lwsa)
+ if (!cxt.lwsa && !cxt.lrsa)
goto end;
if (writer_tasks) {
@@ -898,6 +897,13 @@ static int __init lock_torture_init(void)
firsterr = -EINVAL;
goto unwind;
}
+
+ if (nwriters_stress == 0 && nreaders_stress == 0) {
+ pr_alert("lock-torture: must run at least one locking thread\n");
+ firsterr = -EINVAL;
+ goto unwind;
+ }
+
if (cxt.cur_ops->init)
cxt.cur_ops->init();
@@ -921,17 +927,19 @@ static int __init lock_torture_init(void)
#endif
/* Initialize the statistics so that each run gets its own numbers. */
+ if (nwriters_stress) {
+ lock_is_write_held = 0;
+ cxt.lwsa = kmalloc(sizeof(*cxt.lwsa) * cxt.nrealwriters_stress, GFP_KERNEL);
+ if (cxt.lwsa == NULL) {
+ VERBOSE_TOROUT_STRING("cxt.lwsa: Out of memory");
+ firsterr = -ENOMEM;
+ goto unwind;
+ }
- lock_is_write_held = 0;
- cxt.lwsa = kmalloc(sizeof(*cxt.lwsa) * cxt.nrealwriters_stress, GFP_KERNEL);
- if (cxt.lwsa == NULL) {
- VERBOSE_TOROUT_STRING("cxt.lwsa: Out of memory");
- firsterr = -ENOMEM;
- goto unwind;
- }
- for (i = 0; i < cxt.nrealwriters_stress; i++) {
- cxt.lwsa[i].n_lock_fail = 0;
- cxt.lwsa[i].n_lock_acquired = 0;
+ for (i = 0; i < cxt.nrealwriters_stress; i++) {
+ cxt.lwsa[i].n_lock_fail = 0;
+ cxt.lwsa[i].n_lock_acquired = 0;
+ }
}
if (cxt.cur_ops->readlock) {
@@ -948,19 +956,21 @@ static int __init lock_torture_init(void)
cxt.nrealreaders_stress = cxt.nrealwriters_stress;
}
- lock_is_read_held = 0;
- cxt.lrsa = kmalloc(sizeof(*cxt.lrsa) * cxt.nrealreaders_stress, GFP_KERNEL);
- if (cxt.lrsa == NULL) {
- VERBOSE_TOROUT_STRING("cxt.lrsa: Out of memory");
- firsterr = -ENOMEM;
- kfree(cxt.lwsa);
- cxt.lwsa = NULL;
- goto unwind;
- }
-
- for (i = 0; i < cxt.nrealreaders_stress; i++) {
- cxt.lrsa[i].n_lock_fail = 0;
- cxt.lrsa[i].n_lock_acquired = 0;
+ if (nreaders_stress) {
+ lock_is_read_held = 0;
+ cxt.lrsa = kmalloc(sizeof(*cxt.lrsa) * cxt.nrealreaders_stress, GFP_KERNEL);
+ if (cxt.lrsa == NULL) {
+ VERBOSE_TOROUT_STRING("cxt.lrsa: Out of memory");
+ firsterr = -ENOMEM;
+ kfree(cxt.lwsa);
+ cxt.lwsa = NULL;
+ goto unwind;
+ }
+
+ for (i = 0; i < cxt.nrealreaders_stress; i++) {
+ cxt.lrsa[i].n_lock_fail = 0;
+ cxt.lrsa[i].n_lock_acquired = 0;
+ }
}
}
@@ -990,12 +1000,14 @@ static int __init lock_torture_init(void)
goto unwind;
}
- writer_tasks = kzalloc(cxt.nrealwriters_stress * sizeof(writer_tasks[0]),
- GFP_KERNEL);
- if (writer_tasks == NULL) {
- VERBOSE_TOROUT_ERRSTRING("writer_tasks: Out of memory");
- firsterr = -ENOMEM;
- goto unwind;
+ if (nwriters_stress) {
+ writer_tasks = kzalloc(cxt.nrealwriters_stress * sizeof(writer_tasks[0]),
+ GFP_KERNEL);
+ if (writer_tasks == NULL) {
+ VERBOSE_TOROUT_ERRSTRING("writer_tasks: Out of memory");
+ firsterr = -ENOMEM;
+ goto unwind;
+ }
}
if (cxt.cur_ops->readlock) {
--
2.12.0
[toc] | [prev] | [next] | [standalone]
| From | Davidlohr Bueso <dave@stgolabs.net> |
|---|---|
| Date | 2017-04-06 11:00 +0200 |
| Subject | [PATCH 1/6] interval-tree: Build unconditionally |
| Message-ID | <ttbqP-6ei-55@gated-at.bofh.it> |
| In reply to | #1617655 |
In preparation for range locking, this patch gets rid of CONFIG_INTERVAL_TREE option as we will unconditionally build it. Signed-off-by: Davidlohr Bueso <dbueso@suse.de> --- drivers/gpu/drm/Kconfig | 2 -- drivers/gpu/drm/i915/Kconfig | 1 - lib/Kconfig | 14 -------------- lib/Kconfig.debug | 1 - lib/Makefile | 3 +-- 5 files changed, 1 insertion(+), 20 deletions(-) diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig index 88e01e08e279..e4d9eadd2c47 100644 --- a/drivers/gpu/drm/Kconfig +++ b/drivers/gpu/drm/Kconfig @@ -154,7 +154,6 @@ config DRM_RADEON select HWMON select BACKLIGHT_CLASS_DEVICE select BACKLIGHT_LCD_SUPPORT - 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 @@ -174,7 +173,6 @@ config DRM_AMDGPU select HWMON select BACKLIGHT_CLASS_DEVICE select BACKLIGHT_LCD_SUPPORT - select INTERVAL_TREE help Choose this option if you have a recent AMD Radeon graphics card. diff --git a/drivers/gpu/drm/i915/Kconfig b/drivers/gpu/drm/i915/Kconfig index 183f5dc1c3f2..8a9154550f46 100644 --- a/drivers/gpu/drm/i915/Kconfig +++ b/drivers/gpu/drm/i915/Kconfig @@ -3,7 +3,6 @@ config DRM_I915 depends on DRM depends on X86 && PCI select INTEL_GTT - 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/lib/Kconfig b/lib/Kconfig index 0c8b78a9ae2e..52ca6668a16d 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -347,20 +347,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 RADIX_TREE_MULTIORDER bool diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 97d62c2da6c2..a8a64eb54d3a 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1771,7 +1771,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 320ac46a8725..7881de026baf 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -41,7 +41,7 @@ obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \ gcd.o lcm.o list_sort.o uuid.o flex_array.o iov_iter.o clz_ctz.o \ bsearch.o find_bit.o llist.o memweight.o kfifo.o \ percpu-refcount.o percpu_ida.o rhashtable.o reciprocal_div.o \ - once.o refcount.o + once.o refcount.o interval_tree.o obj-y += string_helpers.o obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o obj-y += hexdump.o @@ -80,7 +80,6 @@ obj-$(CONFIG_DEBUG_LOCKING_API_SELFTESTS) += locking-selftest.o obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o obj-$(CONFIG_BTREE) += btree.o -obj-$(CONFIG_INTERVAL_TREE) += interval_tree.o obj-$(CONFIG_ASSOCIATIVE_ARRAY) += assoc_array.o obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o obj-$(CONFIG_DEBUG_LIST) += list_debug.o -- 2.12.0
[toc] | [prev] | [next] | [standalone]
| From | Davidlohr Bueso <dave@stgolabs.net> |
|---|---|
| Date | 2017-04-06 11:00 +0200 |
| Subject | [PATCH 2/6] locking: Introduce range reader/writer lock |
| Message-ID | <ttbqO-6ei-37@gated-at.bofh.it> |
| In reply to | #1617655 |
This implements a sleepable range rwlock, based on interval tree, serializing
conflicting/intersecting/overlapping ranges within the tree. The largest range
is given by [0, ~0 - 1] (inclusive). Unlike traditional locks, range locking
involves dealing with the tree itself and the range to be locked, normally
stack allocated and always explicitly prepared/initialized by the user in a
[a0, a1] a0 <= a1 sorted manner, before actually taking the lock.
An interval tree of locked and to-be-locked ranges is kept. When a new range
lock is requested, we add its interval to the tree and store number of
intervals intersecting it to 'blocking_ranges'. For the reader case,
'blocking_ranges' is only accounted for if the intersecting range is
marked as a writer. To achieve mutual exclusion of arbitrary ranges, we
guarantee that task is blocked until there are no overlapping ranges in the
tree.
When a range is unlocked, we again walk intervals that overlap with the
unlocked one and decrement their 'blocking_ranges'. Naturally, we wake up
owner of any range lock whose 'blocking_ranges' drops to 0. Wakeup order
therefore relies on the order of the interval tree -- as opposed to a
more traditional fifo mechanism. There is no lock stealing either, which
prevents starvation and guarantees fairness.
How much does it cost:
----------------------
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
new range range to be added.
Due to its sharable nature, full range locks can be compared with rw-sempahores,
which also serves from a mutex standpoint as writer-only situations are
pretty similar nowadays.
The first is the memory footprint, tree locks are larger than rwsems: 80 vs
40 bytes, and also requires an additional 72 bytes of stack for the range
structure.
Secondly, because every range call is serialized by the tree->lock, any lock()
fastpath will at least have an interval_tree_insert() and spinlock lock+unlock
overhead compared to a single atomic insn in the case of rwsems. Similar scenario
obviously for the unlock() case.
The torture module was used to measure 1-1 differences in lock acquisition with
increasing core counts over a period of 10 minutes. Readers and writers are
interleaved, with a slight advantage to writers as its the first kthread that is
created. The following shows the avg ops/minute with various thread-setups on
boxes with small and large core-counts.
** 4-core AMD Opteron **
(write-only)
rwsem-2thr: 4198.5, stddev: 7.77
range-2thr: 4199.1, stddev: 0.73
rwsem-4thr: 6036.8, stddev: 50.91
range-4thr: 6004.9, stddev: 126.57
rwsem-8thr: 6245.6, stddev: 59.39
range-8thr: 6229.3, stddev: 10.60
(read-only)
rwsem-2thr: 5930.7, stddev: 21.92
range-2thr: 5917.3, stddev: 25.45
rwsem-4thr: 9881.6, stddev: 0.70
range-4thr: 9540.2, stddev: 98.28
rwsem-8thr: 11633.2, stddev: 7.72
range-8thr: 11314.7, stddev: 62.22
For the read/write-only cases, there is very little difference between the range lock
and rwsems, with up to a 3% hit, which could very well be considered in the noise range.
(read-write)
rwsem-write-1thr: 1744.8, stddev: 11.59
rwsem-read-1thr: 1043.1, stddev: 3.97
range-write-1thr: 1740.2, stddev: 5.99
range-read-1thr: 1022.5, stddev: 6.41
rwsem-write-2thr: 1662.5, stddev: 0.70
rwsem-read-2thr: 1278.0, stddev: 25.45
range-write-2thr: 1321.5, stddev: 51.61
range-read-2thr: 1243.5, stddev: 30.40
rwsem-write-4thr: 1761.0, stddev: 11.31
rwsem-read-4thr: 1426.0, stddev: 7.07
range-write-4thr: 1417.0, stddev: 29.69
range-read-4thr: 1398.0, stddev: 56.56
While a single reader and writer threads does not show must difference, increasing
core counts shows that in reader/writer workloads, writer threads can take a hit in
raw performance of up to ~20%, while the number of reader throughput is quite similar
among both locks.
** 240-core (ht) IvyBridge **
(write-only)
rwsem-120thr: 6844.5, stddev: 82.73
range-120thr: 6070.5, stddev: 85.55
rwsem-240thr: 6292.5, stddev: 146.3
range-240thr: 6099.0, stddev: 15.55
rwsem-480thr: 6164.8, stddev: 33.94
range-480thr: 6062.3, stddev: 19.79
(read-only)
rwsem-120thr: 136860.4, stddev: 2539.92
range-120thr: 138052.2, stddev: 327.39
rwsem-240thr: 235297.5, stddev: 2220.50
range-240thr: 232099.1, stddev: 3614.72
rwsem-480thr: 272683.0, stddev: 3924.32
range-480thr: 256539.2, stddev: 9541.69
Similar to the small box, larger machines show that range locks take only a minor
(up to ~6% for 480 threads) hit even in completely exclusive or shared scenarios.
(read-write)
rwsem-write-60thr: 4658.1, stddev: 1303.19
rwsem-read-60thr: 1108.7, stddev: 718.42
range-write-60thr: 3203.6, stddev: 139.30
range-read-60thr: 1852.8, stddev: 147.5
rwsem-write-120thr: 3971.3, stddev: 1413.0
rwsem-read-120thr: 1038.8, stddev: 353.51
range-write-120thr: 2282.1, stddev: 207.18
range-read-120thr: 1856.5, stddev: 198.69
rwsem-write-240thr: 4112.7, stddev: 2448.1
rwsem-read-240thr: 1277.4, stddev: 430.30
range-write-240thr: 2353.1, stddev: 502.04
range-read-240thr: 1551.5, stddev: 361.33
When mixing readers and writers, writer throughput can take a hit of up to ~40%,
similar to the 4 core machine, however, reader threads can increase the number of
acquisitions in up to ~80%. In any case, the overall writer+reader throughput will
always be higher for rwsems. A huge factor in this behavior is that range locks
do not have writer spin-on-owner feature.
On both machines when actually testing threads acquiring different ranges, the
amount of throughput will always outperform the rwsem, due to the increased
parallelism; which is no surprise either. As such microbenchmarks that merely
pounds on a lock will pretty much always suffer upon direct lock conversions,
but not enough to matter in the overall picture.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
Reviewed-by: Jan Kara <jack@suse.cz>
---
include/linux/range_rwlock.h | 115 +++++++++
kernel/locking/Makefile | 2 +-
kernel/locking/range_rwlock.c | 554 ++++++++++++++++++++++++++++++++++++++++++
3 files changed, 670 insertions(+), 1 deletion(-)
create mode 100644 include/linux/range_rwlock.h
create mode 100644 kernel/locking/range_rwlock.c
diff --git a/include/linux/range_rwlock.h b/include/linux/range_rwlock.h
new file mode 100644
index 000000000000..0a8dad62d097
--- /dev/null
+++ b/include/linux/range_rwlock.h
@@ -0,0 +1,115 @@
+/*
+ * Range/interval rw-locking
+ * -------------------------
+ *
+ * An interval tree of locked and to-be-locked ranges is kept. When a new range
+ * lock is requested, we add its interval to the tree and store number of
+ * intervals intersecting it to 'blocking_ranges'. For the reader case,
+ * 'blocking_ranges' is only accounted for if the intersecting range is
+ * marked as a writer. To achieve mutual exclusion of arbitrary ranges, we
+ * guarantee that task is blocked until there are no overlapping ranges in the
+ * tree.
+ *
+ * When a range is unlocked, we again walk intervals that overlap with the
+ * unlocked one and decrement their 'blocking_ranges'. Naturally, we wake up
+ * owner of any range lock whose 'blocking_ranges' drops to 0. Wakeup order
+ * therefore relies on the order of the interval tree -- as opposed to a
+ * more traditional fifo mechanism. There is no lock stealing either, which
+ * prevents starvation and guarantees fairness.
+ *
+ * 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_RWLOCK_H
+#define _LINUX_RANGE_RWLOCK_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_RWLOCK_FULL].
+ */
+#define RANGE_RWLOCK_FULL ~0UL
+
+struct range_rwlock {
+ struct interval_tree_node node;
+ struct task_struct *waiter;
+ /* Number of ranges which are blocking acquisition of the lock */
+ unsigned int blocking_ranges;
+ u64 seqnum;
+};
+
+struct range_rwlock_tree {
+ struct rb_root root;
+ spinlock_t lock;
+ struct interval_tree_node *leftmost; /* compute smallest 'start' */
+ u64 seqnum; /* track order of incoming ranges, avoid overflows */
+};
+
+#define __RANGE_RWLOCK_TREE_INITIALIZER(name) \
+ { .leftmost = NULL \
+ , .root = RB_ROOT \
+ , .seqnum = 0 \
+ , .lock = __SPIN_LOCK_UNLOCKED(name.lock) }
+
+#define DEFINE_RANGE_RWLOCK_TREE(name) \
+ struct range_rwlock_tree name = __RANGE_RWLOCK_TREE_INITIALIZER(name)
+
+#define __RANGE_RWLOCK_INITIALIZER(__start, __last) { \
+ .node = { \
+ .start = (__start) \
+ ,.last = (__last) \
+ } \
+ , .task = NULL \
+ , .blocking_ranges = 0 \
+ , .reader = false \
+ , .seqnum = 0 \
+ }
+
+#define DEFINE_RANGE_RWLOCK(name, start, last) \
+ struct range_rwlock name = __RANGE_RWLOCK_INITIALIZER((start), (last))
+
+#define DEFINE_RANGE_RWLOCK_FULL(name) \
+ struct range_rwlock name = __RANGE_RWLOCK_INITIALIZER(0, RANGE_RWLOCK_FULL)
+
+static inline void range_rwlock_tree_init(struct range_rwlock_tree *tree)
+{
+ tree->root = RB_ROOT;
+ spin_lock_init(&tree->lock);
+ tree->leftmost = NULL;
+ tree->seqnum = 0;
+}
+
+void range_rwlock_init(struct range_rwlock *lock,
+ unsigned long start, unsigned long last);
+void range_rwlock_init_full(struct range_rwlock *lock);
+
+/*
+ * lock for reading
+ */
+void range_read_lock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
+int range_read_lock_interruptible(struct range_rwlock_tree *tree,
+ struct range_rwlock *lock);
+int range_read_lock_killable(struct range_rwlock_tree *tree,
+ struct range_rwlock *lock);
+int range_read_trylock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
+void range_read_unlock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
+
+/*
+ * lock for writing
+ */
+void range_write_lock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
+int range_write_lock_interruptible(struct range_rwlock_tree *tree,
+ struct range_rwlock *lock);
+int range_write_lock_killable(struct range_rwlock_tree *tree,
+ struct range_rwlock *lock);
+int range_write_trylock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
+void range_write_unlock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
+
+void range_downgrade_write(struct range_rwlock_tree *tree,
+ struct range_rwlock *lock);
+
+#endif
diff --git a/kernel/locking/Makefile b/kernel/locking/Makefile
index 760158d9d98d..bf054d0af82b 100644
--- a/kernel/locking/Makefile
+++ b/kernel/locking/Makefile
@@ -2,7 +2,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
+obj-y += mutex.o semaphore.o rwsem.o percpu-rwsem.o range_rwlock.o
ifdef CONFIG_FUNCTION_TRACER
CFLAGS_REMOVE_lockdep.o = $(CC_FLAGS_FTRACE)
diff --git a/kernel/locking/range_rwlock.c b/kernel/locking/range_rwlock.c
new file mode 100644
index 000000000000..550ad360d87a
--- /dev/null
+++ b/kernel/locking/range_rwlock.c
@@ -0,0 +1,554 @@
+#include <linux/rbtree.h>
+#include <linux/spinlock.h>
+#include <linux/range_rwlock.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_entry(ptr, type, member) container_of(ptr, type, member)
+
+#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_rwlock_tree *tree, struct range_rwlock *lock)
+{
+ struct interval_tree_node *root;
+
+ if (unlikely(RB_EMPTY_ROOT(&tree->root)))
+ return false;
+
+ root = range_entry(tree->root.rb_node, struct interval_tree_node, rb);
+
+ return lock->node.start <= root->__subtree_last &&
+ tree->leftmost->start <= lock->node.last;
+}
+
+static inline void
+__range_tree_insert(struct range_rwlock_tree *tree, struct range_rwlock *lock)
+{
+ if (unlikely(RB_EMPTY_ROOT(&tree->root)) ||
+ lock->node.start < tree->leftmost->start)
+ tree->leftmost = &lock->node;
+
+ lock->seqnum = tree->seqnum++;
+ interval_tree_insert(&lock->node, &tree->root);
+}
+
+static inline void
+__range_tree_remove(struct range_rwlock_tree *tree, struct range_rwlock *lock)
+{
+ if (tree->leftmost == &lock->node) {
+ struct rb_node *next = rb_next(&tree->leftmost->rb);
+ tree->leftmost = range_entry(next, struct interval_tree_node, rb);
+ }
+
+ interval_tree_remove(&lock->node, &tree->root);
+}
+
+/*
+ * lock->waiter reader tracking.
+ */
+#define RANGE_FLAG_READER 1UL
+
+static inline struct task_struct *range_lock_waiter(struct range_rwlock *lock)
+{
+ return (struct task_struct *)
+ ((unsigned long) lock->waiter & ~RANGE_FLAG_READER);
+}
+
+static inline void range_lock_set_reader(struct range_rwlock *lock)
+{
+ lock->waiter = (struct task_struct *)
+ ((unsigned long)lock->waiter | RANGE_FLAG_READER);
+}
+
+static inline void range_lock_clear_reader(struct range_rwlock *lock)
+{
+ lock->waiter = (struct task_struct *)
+ ((unsigned long)lock->waiter & ~RANGE_FLAG_READER);
+}
+
+static inline bool range_lock_is_reader(struct range_rwlock *lock)
+{
+ return (unsigned long) lock->waiter & RANGE_FLAG_READER;
+}
+
+static inline void
+__range_rwlock_init(struct range_rwlock *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->waiter = NULL;
+ lock->seqnum = 0;
+}
+
+/**
+ * range_rwlock_init - Initialize the 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_rwlock_init(struct range_rwlock *lock, unsigned long start,
+ unsigned long last)
+{
+ __range_rwlock_init(lock, start, last);
+}
+EXPORT_SYMBOL_GPL(range_rwlock_init);
+
+/**
+ * range_rwlock_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_rwlock_init_full(struct range_rwlock *lock)
+{
+ __range_rwlock_init(lock, 0, RANGE_RWLOCK_FULL);
+}
+EXPORT_SYMBOL_GPL(range_rwlock_init_full);
+
+static inline void
+range_rwlock_unblock(struct range_rwlock *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_rwlock_tree *tree,
+ struct range_rwlock *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);
+
+ if (!__range_intersects_intree(tree, lock))
+ goto unlock;
+
+ range_interval_tree_foreach(node, &tree->root,
+ lock->node.start,
+ lock->node.last) {
+ struct range_rwlock *blked;
+ blked = range_entry(node,
+ struct range_rwlock, 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_rwlock_unblock(blked, &wake_q);
+ }
+
+ unlock:
+ spin_unlock_irqrestore(&tree->lock, flags);
+ wake_up_q(&wake_q);
+ break;
+ }
+
+ schedule();
+ }
+
+ __set_current_state(TASK_RUNNING);
+ return ret;
+}
+
+static __always_inline int __sched
+__range_read_lock_common(struct range_rwlock_tree *tree,
+ struct range_rwlock *lock, long state)
+{
+ struct interval_tree_node *node;
+ unsigned long flags;
+
+ spin_lock_irqsave(&tree->lock, flags);
+ range_lock_set_reader(lock);
+
+ if (!__range_intersects_intree(tree, lock))
+ goto insert;
+
+ range_interval_tree_foreach(node, &tree->root,
+ lock->node.start, lock->node.last) {
+ struct range_rwlock *blocked_lock;
+ blocked_lock = range_entry(node, struct range_rwlock, node);
+
+ if (!range_lock_is_reader(blocked_lock))
+ lock->blocking_ranges++;
+ }
+insert:
+ __range_tree_insert(tree, lock);
+
+ lock->waiter = current;
+ spin_unlock_irqrestore(&tree->lock, flags);
+
+ return wait_for_ranges(tree, lock, state);
+}
+
+/**
+ * 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_rwlock_tree *tree, struct range_rwlock *lock)
+{
+ might_sleep();
+ __range_read_lock_common(tree, lock, TASK_UNINTERRUPTIBLE);
+}
+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_rwlock_tree *tree,
+ struct range_rwlock *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.
+ */
+int range_read_lock_killable(struct range_rwlock_tree *tree,
+ struct range_rwlock *lock)
+{
+ might_sleep();
+ return __range_read_lock_common(tree, lock, TASK_KILLABLE);
+}
+EXPORT_SYMBOL_GPL(range_read_lock_killable);
+
+/**
+ * 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).
+ */
+int range_read_trylock(struct range_rwlock_tree *tree, struct range_rwlock *lock)
+{
+ int ret = true;
+ unsigned long flags;
+ struct interval_tree_node *node;
+
+ spin_lock_irqsave(&tree->lock, flags);
+
+ 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) {
+ struct range_rwlock *blocked_lock;
+ blocked_lock = range_entry(node, struct range_rwlock, node);
+
+ if (!range_lock_is_reader(blocked_lock)) {
+ ret = false;
+ goto unlock;
+ }
+ }
+insert:
+ range_lock_set_reader(lock);
+ __range_tree_insert(tree, lock);
+unlock:
+ spin_unlock_irqrestore(&tree->lock, flags);
+
+ return ret;
+}
+EXPORT_SYMBOL_GPL(range_read_trylock);
+
+/**
+ * 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_rwlock_tree *tree, struct range_rwlock *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);
+
+ 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) {
+ struct range_rwlock *blocked_lock;
+ blocked_lock = range_entry(node, struct range_rwlock, node);
+
+ if (!range_lock_is_reader(blocked_lock))
+ range_rwlock_unblock(blocked_lock, &wake_q);
+ }
+
+ spin_unlock_irqrestore(&tree->lock, flags);
+ wake_up_q(&wake_q);
+}
+EXPORT_SYMBOL_GPL(range_read_unlock);
+
+static __always_inline int __sched
+__range_write_lock_common(struct range_rwlock_tree *tree,
+ struct range_rwlock *lock, long state)
+{
+ struct interval_tree_node *node;
+ unsigned long flags;
+
+ spin_lock_irqsave(&tree->lock, flags);
+
+ if (!__range_intersects_intree(tree, lock))
+ goto insert;
+
+ 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 block; either the intersecting node is another
+ * writer or we have a reader that needs to finish.
+ */
+ lock->blocking_ranges++;
+ }
+insert:
+ __range_tree_insert(tree, lock);
+
+ lock->waiter = current;
+ spin_unlock_irqrestore(&tree->lock, flags);
+
+ return wait_for_ranges(tree, lock, state);
+}
+
+/**
+ * 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_rwlock_tree *tree, struct range_rwlock *lock)
+{
+ might_sleep();
+ __range_write_lock_common(tree, lock, TASK_UNINTERRUPTIBLE);
+}
+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_rwlock_tree *tree,
+ struct range_rwlock *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.
+ */
+int range_write_lock_killable(struct range_rwlock_tree *tree,
+ struct range_rwlock *lock)
+{
+ might_sleep();
+ return __range_write_lock_common(tree, lock, TASK_KILLABLE);
+}
+EXPORT_SYMBOL_GPL(range_write_lock_killable);
+
+/**
+ * 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).
+ */
+int range_write_trylock(struct range_rwlock_tree *tree, struct range_rwlock *lock)
+{
+ int intersects;
+ unsigned long flags;
+
+ spin_lock_irqsave(&tree->lock, flags);
+ intersects = __range_intersects_intree(tree, lock);
+
+ if (!intersects) {
+ range_lock_clear_reader(lock);
+ __range_tree_insert(tree, lock);
+ }
+
+ spin_unlock_irqrestore(&tree->lock, flags);
+
+ return !intersects;
+}
+EXPORT_SYMBOL_GPL(range_write_trylock);
+
+/**
+ * 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_rwlock_tree *tree, struct range_rwlock *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);
+
+ 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) {
+ struct range_rwlock *blocked_lock;
+ blocked_lock = range_entry(node, struct range_rwlock, node);
+
+ range_rwlock_unblock(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_rwlock_tree *tree,
+ struct range_rwlock *lock)
+{
+ unsigned long flags;
+ struct interval_tree_node *node;
+ DEFINE_WAKE_Q(wake_q);
+
+ 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_rwlock *blocked_lock;
+ blocked_lock = range_entry(node, struct range_rwlock, node);
+
+ /*
+ * Unaccount for any blocked reader lock. Wakeup if possible.
+ */
+ if (range_lock_is_reader(blocked_lock))
+ range_rwlock_unblock(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);
--
2.12.0
[toc] | [prev] | [next] | [standalone]
| From | Laurent Dufour <ldufour@linux.vnet.ibm.com> |
|---|---|
| Date | 2017-04-06 11:10 +0200 |
| Subject | Re: [PATCH 2/6] locking: Introduce range reader/writer lock |
| Message-ID | <ttbAx-6xa-79@gated-at.bofh.it> |
| In reply to | #1617677 |
On 06/04/2017 10:46, Davidlohr Bueso wrote:
> This implements a sleepable range rwlock, based on interval tree, serializing
> conflicting/intersecting/overlapping ranges within the tree. The largest range
> is given by [0, ~0 - 1] (inclusive). Unlike traditional locks, range locking
> involves dealing with the tree itself and the range to be locked, normally
> stack allocated and always explicitly prepared/initialized by the user in a
> [a0, a1] a0 <= a1 sorted manner, before actually taking the lock.
>
> An interval tree of locked and to-be-locked ranges is kept. When a new range
> lock is requested, we add its interval to the tree and store number of
> intervals intersecting it to 'blocking_ranges'. For the reader case,
> 'blocking_ranges' is only accounted for if the intersecting range is
> marked as a writer. To achieve mutual exclusion of arbitrary ranges, we
> guarantee that task is blocked until there are no overlapping ranges in the
> tree.
>
> When a range is unlocked, we again walk intervals that overlap with the
> unlocked one and decrement their 'blocking_ranges'. Naturally, we wake up
> owner of any range lock whose 'blocking_ranges' drops to 0. Wakeup order
> therefore relies on the order of the interval tree -- as opposed to a
> more traditional fifo mechanism. There is no lock stealing either, which
> prevents starvation and guarantees fairness.
>
> How much does it cost:
> ----------------------
>
> 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
> new range range to be added.
>
> Due to its sharable nature, full range locks can be compared with rw-sempahores,
> which also serves from a mutex standpoint as writer-only situations are
> pretty similar nowadays.
>
> The first is the memory footprint, tree locks are larger than rwsems: 80 vs
> 40 bytes, and also requires an additional 72 bytes of stack for the range
> structure.
>
> Secondly, because every range call is serialized by the tree->lock, any lock()
> fastpath will at least have an interval_tree_insert() and spinlock lock+unlock
> overhead compared to a single atomic insn in the case of rwsems. Similar scenario
> obviously for the unlock() case.
>
> The torture module was used to measure 1-1 differences in lock acquisition with
> increasing core counts over a period of 10 minutes. Readers and writers are
> interleaved, with a slight advantage to writers as its the first kthread that is
> created. The following shows the avg ops/minute with various thread-setups on
> boxes with small and large core-counts.
>
> ** 4-core AMD Opteron **
> (write-only)
> rwsem-2thr: 4198.5, stddev: 7.77
> range-2thr: 4199.1, stddev: 0.73
>
> rwsem-4thr: 6036.8, stddev: 50.91
> range-4thr: 6004.9, stddev: 126.57
>
> rwsem-8thr: 6245.6, stddev: 59.39
> range-8thr: 6229.3, stddev: 10.60
>
> (read-only)
> rwsem-2thr: 5930.7, stddev: 21.92
> range-2thr: 5917.3, stddev: 25.45
>
> rwsem-4thr: 9881.6, stddev: 0.70
> range-4thr: 9540.2, stddev: 98.28
>
> rwsem-8thr: 11633.2, stddev: 7.72
> range-8thr: 11314.7, stddev: 62.22
>
> For the read/write-only cases, there is very little difference between the range lock
> and rwsems, with up to a 3% hit, which could very well be considered in the noise range.
>
> (read-write)
> rwsem-write-1thr: 1744.8, stddev: 11.59
> rwsem-read-1thr: 1043.1, stddev: 3.97
> range-write-1thr: 1740.2, stddev: 5.99
> range-read-1thr: 1022.5, stddev: 6.41
>
> rwsem-write-2thr: 1662.5, stddev: 0.70
> rwsem-read-2thr: 1278.0, stddev: 25.45
> range-write-2thr: 1321.5, stddev: 51.61
> range-read-2thr: 1243.5, stddev: 30.40
>
> rwsem-write-4thr: 1761.0, stddev: 11.31
> rwsem-read-4thr: 1426.0, stddev: 7.07
> range-write-4thr: 1417.0, stddev: 29.69
> range-read-4thr: 1398.0, stddev: 56.56
>
> While a single reader and writer threads does not show must difference, increasing
> core counts shows that in reader/writer workloads, writer threads can take a hit in
> raw performance of up to ~20%, while the number of reader throughput is quite similar
> among both locks.
>
> ** 240-core (ht) IvyBridge **
> (write-only)
> rwsem-120thr: 6844.5, stddev: 82.73
> range-120thr: 6070.5, stddev: 85.55
>
> rwsem-240thr: 6292.5, stddev: 146.3
> range-240thr: 6099.0, stddev: 15.55
>
> rwsem-480thr: 6164.8, stddev: 33.94
> range-480thr: 6062.3, stddev: 19.79
>
> (read-only)
> rwsem-120thr: 136860.4, stddev: 2539.92
> range-120thr: 138052.2, stddev: 327.39
>
> rwsem-240thr: 235297.5, stddev: 2220.50
> range-240thr: 232099.1, stddev: 3614.72
>
> rwsem-480thr: 272683.0, stddev: 3924.32
> range-480thr: 256539.2, stddev: 9541.69
>
> Similar to the small box, larger machines show that range locks take only a minor
> (up to ~6% for 480 threads) hit even in completely exclusive or shared scenarios.
>
> (read-write)
> rwsem-write-60thr: 4658.1, stddev: 1303.19
> rwsem-read-60thr: 1108.7, stddev: 718.42
> range-write-60thr: 3203.6, stddev: 139.30
> range-read-60thr: 1852.8, stddev: 147.5
>
> rwsem-write-120thr: 3971.3, stddev: 1413.0
> rwsem-read-120thr: 1038.8, stddev: 353.51
> range-write-120thr: 2282.1, stddev: 207.18
> range-read-120thr: 1856.5, stddev: 198.69
>
> rwsem-write-240thr: 4112.7, stddev: 2448.1
> rwsem-read-240thr: 1277.4, stddev: 430.30
> range-write-240thr: 2353.1, stddev: 502.04
> range-read-240thr: 1551.5, stddev: 361.33
>
> When mixing readers and writers, writer throughput can take a hit of up to ~40%,
> similar to the 4 core machine, however, reader threads can increase the number of
> acquisitions in up to ~80%. In any case, the overall writer+reader throughput will
> always be higher for rwsems. A huge factor in this behavior is that range locks
> do not have writer spin-on-owner feature.
>
> On both machines when actually testing threads acquiring different ranges, the
> amount of throughput will always outperform the rwsem, due to the increased
> parallelism; which is no surprise either. As such microbenchmarks that merely
> pounds on a lock will pretty much always suffer upon direct lock conversions,
> but not enough to matter in the overall picture.
>
> Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
> Reviewed-by: Jan Kara <jack@suse.cz>
> ---
> include/linux/range_rwlock.h | 115 +++++++++
> kernel/locking/Makefile | 2 +-
> kernel/locking/range_rwlock.c | 554 ++++++++++++++++++++++++++++++++++++++++++
> 3 files changed, 670 insertions(+), 1 deletion(-)
> create mode 100644 include/linux/range_rwlock.h
> create mode 100644 kernel/locking/range_rwlock.c
>
> diff --git a/include/linux/range_rwlock.h b/include/linux/range_rwlock.h
> new file mode 100644
> index 000000000000..0a8dad62d097
> --- /dev/null
> +++ b/include/linux/range_rwlock.h
> @@ -0,0 +1,115 @@
> +/*
> + * Range/interval rw-locking
> + * -------------------------
> + *
> + * An interval tree of locked and to-be-locked ranges is kept. When a new range
> + * lock is requested, we add its interval to the tree and store number of
> + * intervals intersecting it to 'blocking_ranges'. For the reader case,
> + * 'blocking_ranges' is only accounted for if the intersecting range is
> + * marked as a writer. To achieve mutual exclusion of arbitrary ranges, we
> + * guarantee that task is blocked until there are no overlapping ranges in the
> + * tree.
> + *
> + * When a range is unlocked, we again walk intervals that overlap with the
> + * unlocked one and decrement their 'blocking_ranges'. Naturally, we wake up
> + * owner of any range lock whose 'blocking_ranges' drops to 0. Wakeup order
> + * therefore relies on the order of the interval tree -- as opposed to a
> + * more traditional fifo mechanism. There is no lock stealing either, which
> + * prevents starvation and guarantees fairness.
> + *
> + * 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_RWLOCK_H
> +#define _LINUX_RANGE_RWLOCK_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_RWLOCK_FULL].
> + */
> +#define RANGE_RWLOCK_FULL ~0UL
> +
> +struct range_rwlock {
> + struct interval_tree_node node;
> + struct task_struct *waiter;
> + /* Number of ranges which are blocking acquisition of the lock */
> + unsigned int blocking_ranges;
> + u64 seqnum;
> +};
> +
> +struct range_rwlock_tree {
> + struct rb_root root;
> + spinlock_t lock;
> + struct interval_tree_node *leftmost; /* compute smallest 'start' */
> + u64 seqnum; /* track order of incoming ranges, avoid overflows */
> +};
> +
> +#define __RANGE_RWLOCK_TREE_INITIALIZER(name) \
> + { .leftmost = NULL \
> + , .root = RB_ROOT \
> + , .seqnum = 0 \
> + , .lock = __SPIN_LOCK_UNLOCKED(name.lock) }
> +
> +#define DEFINE_RANGE_RWLOCK_TREE(name) \
> + struct range_rwlock_tree name = __RANGE_RWLOCK_TREE_INITIALIZER(name)
> +
> +#define __RANGE_RWLOCK_INITIALIZER(__start, __last) { \
> + .node = { \
> + .start = (__start) \
> + ,.last = (__last) \
> + } \
> + , .task = NULL \
> + , .blocking_ranges = 0 \
> + , .reader = false \
> + , .seqnum = 0 \
> + }
> +
> +#define DEFINE_RANGE_RWLOCK(name, start, last) \
> + struct range_rwlock name = __RANGE_RWLOCK_INITIALIZER((start), (last))
> +
> +#define DEFINE_RANGE_RWLOCK_FULL(name) \
> + struct range_rwlock name = __RANGE_RWLOCK_INITIALIZER(0, RANGE_RWLOCK_FULL)
> +
> +static inline void range_rwlock_tree_init(struct range_rwlock_tree *tree)
> +{
> + tree->root = RB_ROOT;
> + spin_lock_init(&tree->lock);
> + tree->leftmost = NULL;
> + tree->seqnum = 0;
> +}
> +
> +void range_rwlock_init(struct range_rwlock *lock,
> + unsigned long start, unsigned long last);
> +void range_rwlock_init_full(struct range_rwlock *lock);
> +
> +/*
> + * lock for reading
> + */
> +void range_read_lock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
> +int range_read_lock_interruptible(struct range_rwlock_tree *tree,
> + struct range_rwlock *lock);
> +int range_read_lock_killable(struct range_rwlock_tree *tree,
> + struct range_rwlock *lock);
> +int range_read_trylock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
> +void range_read_unlock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
> +
> +/*
> + * lock for writing
> + */
> +void range_write_lock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
> +int range_write_lock_interruptible(struct range_rwlock_tree *tree,
> + struct range_rwlock *lock);
> +int range_write_lock_killable(struct range_rwlock_tree *tree,
> + struct range_rwlock *lock);
> +int range_write_trylock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
> +void range_write_unlock(struct range_rwlock_tree *tree, struct range_rwlock *lock);
> +
> +void range_downgrade_write(struct range_rwlock_tree *tree,
> + struct range_rwlock *lock);
> +
> +#endif
> diff --git a/kernel/locking/Makefile b/kernel/locking/Makefile
> index 760158d9d98d..bf054d0af82b 100644
> --- a/kernel/locking/Makefile
> +++ b/kernel/locking/Makefile
> @@ -2,7 +2,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
> +obj-y += mutex.o semaphore.o rwsem.o percpu-rwsem.o range_rwlock.o
>
> ifdef CONFIG_FUNCTION_TRACER
> CFLAGS_REMOVE_lockdep.o = $(CC_FLAGS_FTRACE)
> diff --git a/kernel/locking/range_rwlock.c b/kernel/locking/range_rwlock.c
> new file mode 100644
> index 000000000000..550ad360d87a
> --- /dev/null
> +++ b/kernel/locking/range_rwlock.c
> @@ -0,0 +1,554 @@
> +#include <linux/rbtree.h>
> +#include <linux/spinlock.h>
> +#include <linux/range_rwlock.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_entry(ptr, type, member) container_of(ptr, type, member)
> +
> +#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_rwlock_tree *tree, struct range_rwlock *lock)
> +{
> + struct interval_tree_node *root;
> +
> + if (unlikely(RB_EMPTY_ROOT(&tree->root)))
> + return false;
> +
> + root = range_entry(tree->root.rb_node, struct interval_tree_node, rb);
> +
> + return lock->node.start <= root->__subtree_last &&
> + tree->leftmost->start <= lock->node.last;
> +}
> +
> +static inline void
> +__range_tree_insert(struct range_rwlock_tree *tree, struct range_rwlock *lock)
> +{
> + if (unlikely(RB_EMPTY_ROOT(&tree->root)) ||
> + lock->node.start < tree->leftmost->start)
> + tree->leftmost = &lock->node;
> +
> + lock->seqnum = tree->seqnum++;
> + interval_tree_insert(&lock->node, &tree->root);
> +}
> +
> +static inline void
> +__range_tree_remove(struct range_rwlock_tree *tree, struct range_rwlock *lock)
> +{
> + if (tree->leftmost == &lock->node) {
> + struct rb_node *next = rb_next(&tree->leftmost->rb);
> + tree->leftmost = range_entry(next, struct interval_tree_node, rb);
> + }
> +
> + interval_tree_remove(&lock->node, &tree->root);
> +}
> +
> +/*
> + * lock->waiter reader tracking.
> + */
> +#define RANGE_FLAG_READER 1UL
> +
> +static inline struct task_struct *range_lock_waiter(struct range_rwlock *lock)
> +{
> + return (struct task_struct *)
> + ((unsigned long) lock->waiter & ~RANGE_FLAG_READER);
> +}
> +
> +static inline void range_lock_set_reader(struct range_rwlock *lock)
> +{
> + lock->waiter = (struct task_struct *)
> + ((unsigned long)lock->waiter | RANGE_FLAG_READER);
> +}
> +
> +static inline void range_lock_clear_reader(struct range_rwlock *lock)
> +{
> + lock->waiter = (struct task_struct *)
> + ((unsigned long)lock->waiter & ~RANGE_FLAG_READER);
> +}
> +
> +static inline bool range_lock_is_reader(struct range_rwlock *lock)
> +{
> + return (unsigned long) lock->waiter & RANGE_FLAG_READER;
> +}
> +
> +static inline void
> +__range_rwlock_init(struct range_rwlock *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->waiter = NULL;
> + lock->seqnum = 0;
> +}
> +
> +/**
> + * range_rwlock_init - Initialize the 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_rwlock_init(struct range_rwlock *lock, unsigned long start,
> + unsigned long last)
> +{
> + __range_rwlock_init(lock, start, last);
> +}
> +EXPORT_SYMBOL_GPL(range_rwlock_init);
> +
> +/**
> + * range_rwlock_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_rwlock_init_full(struct range_rwlock *lock)
> +{
> + __range_rwlock_init(lock, 0, RANGE_RWLOCK_FULL);
> +}
> +EXPORT_SYMBOL_GPL(range_rwlock_init_full);
> +
> +static inline void
> +range_rwlock_unblock(struct range_rwlock *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_rwlock_tree *tree,
> + struct range_rwlock *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);
> +
> + if (!__range_intersects_intree(tree, lock))
> + goto unlock;
> +
> + range_interval_tree_foreach(node, &tree->root,
> + lock->node.start,
> + lock->node.last) {
> + struct range_rwlock *blked;
> + blked = range_entry(node,
> + struct range_rwlock, 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_rwlock_unblock(blked, &wake_q);
How is 'seqnum' wrapping handled here ?
I'd rather see something like time_before() here, isn't it ?
Cheers,
Laurent.
[toc] | [prev] | [next] | [standalone]
| From | Davidlohr Bueso <dave@stgolabs.net> |
|---|---|
| Date | 2017-04-06 19:00 +0200 |
| Subject | Re: [PATCH 2/6] locking: Introduce range reader/writer lock |
| Message-ID | <ttiVj-3pQ-1@gated-at.bofh.it> |
| In reply to | #1617717 |
On Thu, 06 Apr 2017, Laurent Dufour wrote: >How is 'seqnum' wrapping handled here ? >I'd rather see something like time_before() here, isn't it ? Its a 64bit counter, no overflows.
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-04-06 12:30 +0200 |
| Subject | Re: [PATCH 2/6] locking: Introduce range reader/writer lock |
| Message-ID | <ttcPV-7fO-37@gated-at.bofh.it> |
| In reply to | #1617677 |
On Thu, Apr 06, 2017 at 01:46:16AM -0700, Davidlohr Bueso wrote: > +/* > + * Range/interval rw-locking > + * ------------------------- > + * > + * An interval tree of locked and to-be-locked ranges is kept. When a new range > + * lock is requested, we add its interval to the tree and store number of > + * intervals intersecting it to 'blocking_ranges'. You're again confusing semantics with implementation here. > For the reader case, > + * 'blocking_ranges' is only accounted for if the intersecting range is > + * marked as a writer. To achieve mutual exclusion of arbitrary ranges, we > + * guarantee that task is blocked until there are no overlapping ranges in the > + * tree. > + * > + * When a range is unlocked, we again walk intervals that overlap with the > + * unlocked one and decrement their 'blocking_ranges'. Naturally, we wake up > + * owner of any range lock whose 'blocking_ranges' drops to 0. Wakeup order > + * therefore relies on the order of the interval tree -- as opposed to a > + * more traditional fifo mechanism. Which order is that? (I could of course go read the interval tree code, but it shouldn't be too much effort to mention it here). > There is no lock stealing either, which > + * prevents starvation and guarantees fairness. So no lock stealing has always been very bad for performance. So are you sure people will not frob this back in? > +#ifndef _LINUX_RANGE_RWLOCK_H Still don't like the name... rwlock_t is a spinlock.
[toc] | [prev] | [standalone]
Back to top | Article view | linux.kernel
csiph-web