New read/write locks for PI and multiple readers

PATCH New Steven Rostedt 1 participant 7 messages Apr 25, 2008

Subsystems (5)

MM core Scheduler exec and binfmt Locking primitives +1 more subsystems

lore

Share & tools

lore

Steven Rostedt

author reviewer

2008-04-25 14:21 UTC #0 lore raw

cover New read/write locks for PI and multiple readers

Currently in the -rt patch the rwlocks (and rwsems) are converted into a simple mutex. That is, when PREEMP_RT is configured, the rwsems and rwlocks can only have one reader at a time. Those locks may only be held by a single owner (reader or writer). The reason for this is to allow priority inheritance for these locks. PI can be quite complex, but it is easier to handle PI when dealing with only a single owner. When multiple owners are involved it gets even more complex. But this patch series aims to accomplish PI over multiple owners.

Having multiple owners may also have other drawbacks in RT. One is that it adds a bit more non-determinism. Because a writer may have to wait the critical path time * each reader that currently holds the lock. Since the number of readers is not set, this creates a non-deterministic time frame. To deal with this, this patch series adds the ability to limit the number of readers that may own the lock. Setting that number to the number of CPUS may be a good idea.

Having no limit to the number of readers may also be preferable. Although it adds some non-determinism, the PI on the readers prevents unbounded priority inversion, where a task can block a lower priority task that holds a lock that is keeping higher priority tasks from running.

The way this algorithm works is by adding a new descriptor called rw_mutex. This descriptor also contains a RT mutex (one with PI). It also adds a new owner field in the rw_mutex. When taking the lock for read, it does a cmpxchg (if the arch supports it) on the owner field placing in its own current pointer if the owner field is currently NULL. If this succeeds, then it grabs the lock and increments the owner counts. If it fails it enters the slow path (if the arch doesn't have cmpxchg then it always enters the slow path).

The slow path for read checks to see if the owner field is set for readers, and if it is, it ups the owner counts of the locks and sets up the pointers from the lock to the readers and grabs the lock.

If it fails, the reader blocking is much like the same as a simple mutex since it may boost the writer (which there would be only one). But first if the owner of the rw_lock is not set in the rt_mutex, then the owner is updated, to allow the old PI algorithm to work (see patches for details).

For a writer to take the lock, in the fastpath it does a cmpxchg to the rw_mutex field by trying to copy in the current pointer plus the second least significant bit (the first least significant bit is set for serializing fast paths with slowpaths). The second least significant bit in the owner field denotes that the owner is a writer.

If it fails the fast path, it enters the slow path. There if it still can't get the lock, it updates the rt_mutex owner field (don't confuse the rt_mutex with the rw_mutex descriptors). If the owner of the lock is a reader the rt_mutex owner is given a factitious owner (RT_RW_READER).

The current PI algorithm takes at most two of the internal spin_locks at a time and checks for deadlocks. One reason to do this is that this algorithm is also used with futexes, and we can't allow user space code be able deadlocking the kernel. But because rwlocks and rwsems are never held while taking a futex (that would just be bad) we can trust the rwlocks and rwsems will not deadlock (or the kernel itself is bad).

Because of this, when the PI algorithm walks the chain and comes across a owner of RT_RW_READER, it breaks out of the loop, and will contiune to hold that rt_mutex's internal spin lock. Then it will go through each of the readers and continue the algorithm on each.

Yes this contains a recursive function, but it also keeps track at the number of times it recurs. Which brings us to the limits that the algorithm imposes. A task can only hold at most 5 different reader locks at the same time. This should not be an issue, since it would be bad programming practice to hold more that 5 different reader locks. This is because each task has an array of 5 reader lock structures that it uses to keep track of the reader locks it owns. This is for use of the PI algorithm.

For more on this code, see the patches.

-- Steve

Steven Rostedt

author reviewer

2008-04-25 14:21 UTC #1 lore raw

PATCH 1/6 add framework for multi readers on rwsems

Add the frame work for multiple readers and implemnt the code for rwsem first.

A new structure is created called rw_mutex. This is used by PREEMPT_RT rwsems and will later be incorporated with rwlocks.

The rw_mutex lock encapsulates the rt_mutex for use with rwsems (and later rwlocks). This patch is just the ground work. It simply allows for mulitple readers to grab the lock. This disables PI for readers. That is, when a writer is blocked on a rwsem with readers, it will not boost the readers. That work will be done later in the patch series.

Signed-off-by Steven Rostedt <[email protected]>

---
 include/linux/lockdep.h |   13 
 include/linux/rt_lock.h |   13 
 kernel/rt.c             |   64 ----
 kernel/rtmutex.c        |  706 +++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/rtmutex_common.h |   57 +++
 5 files changed, 795 insertions(+), 58 deletions(-)

include/linux/rt_lock.h +9 -4

Index: linux-2.6.24.4-rt4/include/linux/rt_lock.h
===================================================================
@@ -60,6 +60,12 @@ typedef raw_spinlock_t spinlock_t;
 
 #ifdef CONFIG_PREEMPT_RT
 
+struct rw_mutex {
+	struct task_struct	*owner;
+	struct rt_mutex		mutex;
+	atomic_t		count;	/* number of times held for read */
+};
+
 /*
  * RW-semaphores are a spinlock plus a reader-depth count.
  *

@@ -71,8 +77,7 @@ typedef raw_spinlock_t spinlock_t;
  * fair and makes it simpler as well:
  */
 struct rw_semaphore {
-	struct rt_mutex		lock;
-	int			read_depth;
+	struct rw_mutex	owners;
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 	struct lockdep_map	dep_map;
 #endif

@@ -189,7 +194,7 @@ extern int __bad_func_type(void);
  */
 
 #define __RWSEM_INITIALIZER(name) \
-	{ .lock = __RT_MUTEX_INITIALIZER(name.lock), \
+	{ .owners.mutex = __RT_MUTEX_INITIALIZER(name.owners.mutex), \
 	  RW_DEP_MAP_INIT(name) }
 
 #define DECLARE_RWSEM(lockname) \

@@ -222,7 +227,7 @@ extern void fastcall rt_up_read(struct r
 extern void fastcall rt_up_write(struct rw_semaphore *rwsem);
 extern void fastcall rt_downgrade_write(struct rw_semaphore *rwsem);
 
-# define rt_rwsem_is_locked(rws)	(rt_mutex_is_locked(&(rws)->lock))
+# define rt_rwsem_is_locked(rws)	((rws)->owners.owner != NULL)
 
 #define PICK_RWSEM_OP(...) PICK_FUNCTION(struct compat_rw_semaphore *,	\
 	struct rw_semaphore *, ##__VA_ARGS__)

kernel/rtmutex.c +702 -4

779 lines not on this page · raw message

kernel/rtmutex_common.h +57 -0

81 lines not on this page · raw message

kernel/rt.c +14 ~~-50~~

115 lines not on this page · raw message

include/linux/lockdep.h +13 -0

Index: linux-2.6.24.4-rt4/include/linux/lockdep.h
===================================================================
@@ -383,6 +383,16 @@ do {								\
  	ret;							\
 })
 
+#define LOCK_CONTENDED_RT_RW(_lock, f_try, f_lock)		\
+do {								\
+	if (!f_try(&(_lock)->owners)) {				\
+		lock_contended(&(_lock)->dep_map, _RET_IP_);	\
+		f_lock(&(_lock)->owners);			\
+	}							\
+	lock_acquired(&(_lock)->dep_map);			\
+} while (0)
+
+
 #else /* CONFIG_LOCK_STAT */
 
 #define lock_contended(lockdep_map, ip) do {} while (0)

@@ -397,6 +407,9 @@ do {								\
 #define LOCK_CONTENDED_RT_RET(_lock, f_try, f_lock) \
 	f_lock(&(_lock)->lock)
 
+#define LOCK_CONTENDED_RT_RW(_lock, f_try, f_lock) \
+	f_lock(&(_lock)->owners)
+
 #endif /* CONFIG_LOCK_STAT */
 
 #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_GENERIC_HARDIRQS)

Steven Rostedt

author reviewer

2008-04-25 14:21 UTC #2 lore raw

PATCH 2/6 implement rwlocks management

In reply to Steven Rostedt

This patch adds the managment for rwlocks to have multiple readers. Like the rwsems, it does not do PI boosting on readers when a writer is blocked.

Signed-off-by Steven Rostedt <[email protected]>

---
 include/linux/rt_lock.h  |    5 -
 include/linux/spinlock.h |    2 
 kernel/rt.c              |   56 ++--------------
 kernel/rtmutex.c         |  158 ++++++++++++++++++++++++++++++++++-------------
 kernel/rtmutex_common.h  |    4 +
 5 files changed, 129 insertions(+), 96 deletions(-)

include/linux/rt_lock.h +2 -3

Index: linux-2.6.24.4-rt4/include/linux/rt_lock.h
===================================================================
@@ -87,8 +87,7 @@ struct rw_semaphore {
  * rwlocks - an RW semaphore plus lock-break field:
  */
 typedef struct {
-	struct rt_mutex		lock;
-	int			read_depth;
+	struct rw_mutex	owners;
 	unsigned int		break_lock;
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 	struct lockdep_map	dep_map;

@@ -96,7 +95,7 @@ typedef struct {
 } rwlock_t;
 
 #define __RW_LOCK_UNLOCKED(name) (rwlock_t) \
-	{ .lock = __RT_SPIN_INITIALIZER(name),	\
+	{ .owners.mutex = __RT_SPIN_INITIALIZER(name.owners.mutex),	\
 	  RW_DEP_MAP_INIT(name) }
 #else /* !PREEMPT_RT */

include/linux/spinlock.h +1 -1

Index: linux-2.6.24.4-rt4/include/linux/spinlock.h
===================================================================
@@ -266,7 +266,7 @@ do {							\
 
 #ifdef CONFIG_PREEMPT_RT
 # define rt_read_can_lock(rwl)	(!rt_mutex_is_locked(&(rwl)->lock))
-# define rt_write_can_lock(rwl)	(!rt_mutex_is_locked(&(rwl)->lock))
+# define rt_write_can_lock(rwl)	((rwl)->owners.owner == NULL)
 #else
  extern int rt_rwlock_can_lock_never_call_on_non_rt(rwlock_t *rwlock);
 # define rt_read_can_lock(rwl)	rt_rwlock_can_lock_never_call_on_non_rt(rwl)

kernel/rt.c +7 ~~-49~~

100 lines not on this page · raw message

kernel/rtmutex.c +115 ~~-43~~

336 lines not on this page · raw message

kernel/rtmutex_common.h +4 -0

Index: linux-2.6.24.4-rt4/kernel/rtmutex_common.h
===================================================================
@@ -166,6 +166,10 @@ extern void rt_mutex_down_write(struct r
 extern int rt_mutex_down_read_trylock(struct rw_mutex *rwm);
 extern void rt_mutex_down_read(struct rw_mutex *rwm);
 extern void rt_mutex_rwsem_init(struct rw_mutex *rwm, const char *name);
+extern void rt_rwlock_write_lock(struct rw_mutex *rwm);
+extern void rt_rwlock_read_lock(struct rw_mutex *rwm);
+extern void rt_rwlock_write_unlock(struct rw_mutex *rwm);
+extern void rt_rwlock_read_unlock(struct rw_mutex *rwm);
 
 #endif /* CONFIG_PREEMPT_RT */

Steven Rostedt

author reviewer

2008-04-25 14:21 UTC #3 lore raw

PATCH 3/6 map tasks to reader locks held

In reply to Steven Rostedt

This patch keeps track of all reader locks that are held for a task. The max depth is currently set to 5. A task may own the same lock multiple times for read without affecting this limit. It is bad programming practice to hold more than 5 different locks for read at the same time anyway so this should not be a problem. The 5 lock limit should be way more than enough.

Signed-off-by Steven Rostedt <[email protected]>

---
 include/linux/sched.h |   14 ++++++++++
 kernel/fork.c         |    4 +++
 kernel/rtmutex.c      |   66 ++++++++++++++++++++++++++++++++++++++++++++++----
 3 files changed, 80 insertions(+), 4 deletions(-)

include/linux/sched.h +14 -0

Index: linux-2.6.24.4-rt4/include/linux/sched.h
===================================================================
@@ -1005,6 +1005,14 @@ struct sched_entity {
 #endif
 };
 
+#ifdef CONFIG_PREEMPT_RT
+struct rw_mutex;
+struct reader_lock_struct {
+	struct rw_mutex *lock;
+	int count;
+};
+
+#endif
 struct task_struct {
 	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
 	void *stack;

@@ -1226,6 +1234,12 @@ struct task_struct {
 #endif
 
 #define MAX_PREEMPT_TRACE 25
+#define MAX_RWLOCK_DEPTH 5
+
+#ifdef CONFIG_PREEMPT_RT
+	int reader_lock_count;
+	struct reader_lock_struct owned_read_locks[MAX_RWLOCK_DEPTH];
+#endif
 
 #ifdef CONFIG_PREEMPT_TRACE
 	unsigned long preempt_trace_eip[MAX_PREEMPT_TRACE];

kernel/rtmutex.c +62 -4

132 lines not on this page · raw message

kernel/fork.c +4 -0

Index: linux-2.6.24.4-rt4/kernel/fork.c
===================================================================
@@ -1206,6 +1206,10 @@ static struct task_struct *copy_process(
 	p->lock_count = 0;
 #endif
 
+#ifdef CONFIG_PREEMPT_RT
+	p->reader_lock_count = 0;
+#endif
+
 	if (pid != &init_struct_pid) {
 		retval = -ENOMEM;
 		pid = alloc_pid(task_active_pid_ns(p));

Steven Rostedt

author reviewer

2008-04-25 14:21 UTC #4 lore raw

PATCH 4/6 implement reader limit on read write locks

In reply to Steven Rostedt

This patch allows for limiting the number of readers a lock may have. The limit is default to "no limit". The read write locks now keep track of, not only the number of times a lock is held by read, but also the number of tasks that have a reader. i.e. If 2 tasks hold the same read/write lock, and one task holds the lock twice, the count for the read/write lock would be 3 and the owner count is 2.

The limit of readers is controlled by

/proc/sys/kernel/rwlock_reader_limit

If this is set to zero or negative, than there is no limit.

Signed-off-by Steven Rostedt <[email protected]>

---
 include/linux/rt_lock.h |    1 
 kernel/rtmutex.c        |   89 +++++++++++++++++++++++++++++++++++-------------
 kernel/sysctl.c         |   14 +++++++
 3 files changed, 80 insertions(+), 24 deletions(-)

include/linux/rt_lock.h +1 -0

Index: linux-2.6.24.4-rt4/include/linux/rt_lock.h
===================================================================
@@ -64,6 +64,7 @@ struct rw_mutex {
 	struct task_struct	*owner;
 	struct rt_mutex		mutex;
 	atomic_t		count;	/* number of times held for read */
+	atomic_t		owners; /* number of owners as readers */
 };
 
 /*

kernel/rtmutex.c +65 ~~-24~~

172 lines not on this page · raw message

kernel/sysctl.c +14 -0

Index: linux-2.6.24.4-rt4/kernel/sysctl.c
===================================================================
@@ -150,6 +150,10 @@ static int parse_table(int __user *, int
 		void __user *, size_t, struct ctl_table *);
 #endif
 
+#ifdef CONFIG_PREEMPT_RT
+extern int rt_rwlock_limit;
+#endif
+
 
 #ifdef CONFIG_PROC_SYSCTL
 static int proc_do_cad_pid(struct ctl_table *table, int write, struct file *filp,

@@ -399,6 +403,16 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= &proc_dointvec,
 	},
 #endif
+#ifdef CONFIG_PREEMPT_RT
+	{
+		.ctl_name	= CTL_UNNUMBERED,
+		.procname	= "rwlock_reader_limit",
+		.data		= &rt_rwlock_limit,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec,
+	},
+#endif
 	{
 		.ctl_name	= KERN_PANIC,
 		.procname	= "panic",

Steven Rostedt

author reviewer

2008-04-25 14:21 UTC #5 lore raw

PATCH 5/6 map read/write locks back to their readers

In reply to Steven Rostedt

This patch adds a mapping from the read/write lock back to the owners that are readers. This is a link list of tasks that own the lock for read.

The link list is protected by the read/write lock's mutex wait_lock. To prevent grabbing this spinlock on the fast path, the list in not updated when there is only one reader. The reader task is pointed to by the owner field of the rw_mutex. When the second reader grabs the read lock it will add the first owner to the list under the wait_lock.

Signed-off-by Steven Rostedt <[email protected]>

---
 include/linux/rt_lock.h |    3 
 include/linux/sched.h   |    2 
 kernel/fork.c           |    8 ++
 kernel/rtmutex.c        |  187 ++++++++++++++++++++++++++++++++++--------------
 4 files changed, 146 insertions(+), 54 deletions(-)

include/linux/rt_lock.h +2 -1

Index: linux-2.6.24.4-rt4/include/linux/rt_lock.h
===================================================================
@@ -65,6 +65,7 @@ struct rw_mutex {
 	struct rt_mutex		mutex;
 	atomic_t		count;	/* number of times held for read */
 	atomic_t		owners; /* number of owners as readers */
+	struct list_head	readers;
 };
 
 /*

@@ -194,7 +195,7 @@ extern int __bad_func_type(void);
  */
 
 #define __RWSEM_INITIALIZER(name) \
-	{ .owners.mutex = __RT_MUTEX_INITIALIZER(name.owners.mutex), \
+	{ .owners.mutex = __RT_MUTEX_INITIALIZER(name.owners.mutex),	\
 	  RW_DEP_MAP_INIT(name) }
 
 #define DECLARE_RWSEM(lockname) \

include/linux/sched.h +2 -0

Index: linux-2.6.24.4-rt4/include/linux/sched.h
===================================================================
@@ -1009,6 +1009,8 @@ struct sched_entity {
 struct rw_mutex;
 struct reader_lock_struct {
 	struct rw_mutex *lock;
+	struct list_head list;
+	struct task_struct *task;
 	int count;
 };

kernel/fork.c +8 -0

Index: linux-2.6.24.4-rt4/kernel/fork.c
===================================================================
@@ -1208,6 +1208,14 @@ static struct task_struct *copy_process(
 
 #ifdef CONFIG_PREEMPT_RT
 	p->reader_lock_count = 0;
+	{
+		int i;
+		for (i = 0; i < MAX_RWLOCK_DEPTH; i++) {
+			INIT_LIST_HEAD(&p->owned_read_locks[i].list);
+			p->owned_read_locks[i].count = 0;
+			p->owned_read_locks[i].lock = NULL;
+		}
+	}
 #endif
 
 	if (pid != &init_struct_pid) {

kernel/rtmutex.c +134 ~~-53~~

347 lines not on this page · raw message

Steven Rostedt

author reviewer

2008-04-25 14:21 UTC #6 lore raw

PATCH 6/6 read lock Priority Inheritance implementation

In reply to Steven Rostedt

This patch adds the priority inheritance (PI) to the read / write locks. When a task is blocked on the lock that eventually is owned by a reader in the PI chain, it will boost all the readers if they are of lower priority than the blocked task.

Signed-off-by Steven Rostedt <[email protected]>

---
 include/linux/init_task.h |    8 +++
 include/linux/rt_lock.h   |    4 +
 kernel/fork.c             |    1 
 kernel/rtmutex.c          |  115 ++++++++++++++++++++++++++++++++++++++++++----
 4 files changed, 118 insertions(+), 10 deletions(-)

include/linux/rt_lock.h +4 -0

Index: linux-2.6.24.4-rt4/include/linux/rt_lock.h
===================================================================
@@ -13,6 +13,7 @@
 #include <linux/rtmutex.h>
 #include <asm/atomic.h>
 #include <linux/spinlock_types.h>
+#include <linux/sched_prio.h>
 
 #ifdef CONFIG_PREEMPT_RT
 /*

@@ -66,6 +67,7 @@ struct rw_mutex {
 	atomic_t		count;	/* number of times held for read */
 	atomic_t		owners; /* number of owners as readers */
 	struct list_head	readers;
+	int prio;
 };
 
 /*

@@ -98,6 +100,7 @@ typedef struct {
 
 #define __RW_LOCK_UNLOCKED(name) (rwlock_t) \
 	{ .owners.mutex = __RT_SPIN_INITIALIZER(name.owners.mutex),	\
+	  .owners.prio = MAX_PRIO,					\
 	  RW_DEP_MAP_INIT(name) }
 #else /* !PREEMPT_RT */

@@ -196,6 +199,7 @@ extern int __bad_func_type(void);
 
 #define __RWSEM_INITIALIZER(name) \
 	{ .owners.mutex = __RT_MUTEX_INITIALIZER(name.owners.mutex),	\
+	  .owners.prio = MAX_PRIO,					\
 	  RW_DEP_MAP_INIT(name) }
 
 #define DECLARE_RWSEM(lockname) \

kernel/rtmutex.c +105 ~~-10~~

199 lines not on this page · raw message

include/linux/init_task.h +8 -0

Index: linux-2.6.24.4-rt4/include/linux/init_task.h
===================================================================
@@ -99,6 +99,13 @@ extern struct nsproxy init_nsproxy;
 #define INIT_PREEMPT_RCU_BOOST(tsk)
 #endif /* #else #ifdef CONFIG_PREEMPT_RCU_BOOST */
 
+#ifdef CONFIG_PREEMPT_RT
+# define INIT_RW_OWNERS(tsk) .owned_read_locks = {			\
+		[0 ... (MAX_RWLOCK_DEPTH - 1) ] = { .task = &tsk } },
+#else
+# define INIT_RW_OWNERS(tsk)
+#endif
+
 extern struct group_info init_groups;
 
 #define INIT_STRUCT_PID {						\

@@ -189,6 +196,7 @@ extern struct group_info init_groups;
 	INIT_TRACE_IRQFLAGS						\
 	INIT_LOCKDEP							\
 	INIT_PREEMPT_RCU_BOOST(tsk)					\
+	INIT_RW_OWNERS(tsk)						\
 }

kernel/fork.c +1 -0

Index: linux-2.6.24.4-rt4/kernel/fork.c
===================================================================
@@ -1214,6 +1214,7 @@ static struct task_struct *copy_process(
 			INIT_LIST_HEAD(&p->owned_read_locks[i].list);
 			p->owned_read_locks[i].count = 0;
 			p->owned_read_locks[i].lock = NULL;
+			p->owned_read_locks[i].task = p;
 		}
 	}
 #endif