The patch titled
lock validator: prove rwsem locking correctness
has been added to the -mm tree. Its filename is
lock-validator-prove-rwsem-locking-correctness.patch
See http://www.zip.com.au/~akpm/linux/patches/stuff/added-to-mm.txt to find
out what to do about this
------------------------------------------------------
Subject: lock validator: prove rwsem locking correctness
From: Ingo Molnar <mingo@xxxxxxx>
Add CONFIG_PROVE_RWSEM_LOCKING, which uses the lock validator framework
to prove rwsem locking correctness.
Signed-off-by: Ingo Molnar <mingo@xxxxxxx>
Signed-off-by: Arjan van de Ven <arjan@xxxxxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxx>
---
include/asm-i386/rwsem.h | 38 ++++++++++++++-------
include/linux/rwsem-spinlock.h | 23 +++++++++++-
include/linux/rwsem.h | 56 +++++++++++++++++++++++++++++++
lib/rwsem-spinlock.c | 15 ++++++--
lib/rwsem.c | 19 ++++++++++
5 files changed, 135 insertions(+), 16 deletions(-)
diff -puN include/asm-i386/rwsem.h~lock-validator-prove-rwsem-locking-correctness include/asm-i386/rwsem.h
--- devel/include/asm-i386/rwsem.h~lock-validator-prove-rwsem-locking-correctness 2006-05-29 18:12:59.000000000 -0700
+++ devel-akpm/include/asm-i386/rwsem.h 2006-05-29 18:12:59.000000000 -0700
@@ -40,6 +40,7 @@
#include <linux/list.h>
#include <linux/spinlock.h>
+#include <linux/lockdep.h>
struct rwsem_waiter;
@@ -64,6 +65,9 @@ struct rw_semaphore {
#if RWSEM_DEBUG
int debug;
#endif
+#ifdef CONFIG_PROVE_RWSEM_LOCKING
+ struct lockdep_map dep_map;
+#endif
};
/*
@@ -75,22 +79,29 @@ struct rw_semaphore {
#define __RWSEM_DEBUG_INIT /* */
#endif
+#ifdef CONFIG_PROVE_RWSEM_LOCKING
+# define __RWSEM_DEP_MAP_INIT(lockname) , .dep_map = { .name = #lockname }
+#else
+# define __RWSEM_DEP_MAP_INIT(lockname)
+#endif
+
+
#define __RWSEM_INITIALIZER(name) \
{ RWSEM_UNLOCKED_VALUE, SPIN_LOCK_UNLOCKED, LIST_HEAD_INIT((name).wait_list) \
- __RWSEM_DEBUG_INIT }
+ __RWSEM_DEBUG_INIT __RWSEM_DEP_MAP_INIT(name) }
#define DECLARE_RWSEM(name) \
struct rw_semaphore name = __RWSEM_INITIALIZER(name)
-static inline void init_rwsem(struct rw_semaphore *sem)
-{
- sem->count = RWSEM_UNLOCKED_VALUE;
- spin_lock_init(&sem->wait_lock);
- INIT_LIST_HEAD(&sem->wait_list);
-#if RWSEM_DEBUG
- sem->debug = 0;
-#endif
-}
+extern void __init_rwsem(struct rw_semaphore *sem, const char *name,
+ struct lockdep_type_key *key);
+
+#define init_rwsem(sem) \
+do { \
+ static struct lockdep_type_key __key; \
+ \
+ __init_rwsem((sem), #sem, &__key); \
+} while (0)
/*
* lock for reading
@@ -143,7 +154,7 @@ LOCK_PREFIX " cmpxchgl %2,%0\n\t"
/*
* lock for writing
*/
-static inline void __down_write(struct rw_semaphore *sem)
+static inline void __down_write_nested(struct rw_semaphore *sem, int subtype)
{
int tmp;
@@ -167,6 +178,11 @@ LOCK_PREFIX " xadd %%edx,(%%eax)\n
: "memory", "cc");
}
+static inline void __down_write(struct rw_semaphore *sem)
+{
+ __down_write_nested(sem, 0);
+}
+
/*
* trylock for writing -- returns 1 if successful, 0 if contention
*/
diff -puN include/linux/rwsem.h~lock-validator-prove-rwsem-locking-correctness include/linux/rwsem.h
--- devel/include/linux/rwsem.h~lock-validator-prove-rwsem-locking-correctness 2006-05-29 18:12:59.000000000 -0700
+++ devel-akpm/include/linux/rwsem.h 2006-05-29 18:12:59.000000000 -0700
@@ -40,6 +40,20 @@ extern void FASTCALL(rwsemtrace(struct r
static inline void down_read(struct rw_semaphore *sem)
{
might_sleep();
+ rwsem_acquire_read(&sem->dep_map, 0, 0, _THIS_IP_);
+
+ rwsemtrace(sem,"Entering down_read");
+ __down_read(sem);
+ rwsemtrace(sem,"Leaving down_read");
+}
+
+/*
+ * Take a lock when not the owner will release it:
+ */
+static inline void down_read_non_owner(struct rw_semaphore *sem)
+{
+ might_sleep();
+
rwsemtrace(sem,"Entering down_read");
__down_read(sem);
rwsemtrace(sem,"Leaving down_read");
@@ -53,6 +67,8 @@ static inline int down_read_trylock(stru
int ret;
rwsemtrace(sem,"Entering down_read_trylock");
ret = __down_read_trylock(sem);
+ if (ret == 1)
+ rwsem_acquire_read(&sem->dep_map, 0, 1, _THIS_IP_);
rwsemtrace(sem,"Leaving down_read_trylock");
return ret;
}
@@ -63,12 +79,28 @@ static inline int down_read_trylock(stru
static inline void down_write(struct rw_semaphore *sem)
{
might_sleep();
+ rwsem_acquire(&sem->dep_map, 0, 0, _THIS_IP_);
+
rwsemtrace(sem,"Entering down_write");
__down_write(sem);
rwsemtrace(sem,"Leaving down_write");
}
/*
+ * lock for writing
+ */
+static inline void down_write_nested(struct rw_semaphore *sem, int subtype)
+{
+ might_sleep();
+ rwsem_acquire(&sem->dep_map, subtype, 0, _THIS_IP_);
+
+ rwsemtrace(sem,"Entering down_write_nested");
+ __down_write_nested(sem, subtype);
+ rwsemtrace(sem,"Leaving down_write_nested");
+}
+
+
+/*
* trylock for writing -- returns 1 if successful, 0 if contention
*/
static inline int down_write_trylock(struct rw_semaphore *sem)
@@ -76,6 +108,8 @@ static inline int down_write_trylock(str
int ret;
rwsemtrace(sem,"Entering down_write_trylock");
ret = __down_write_trylock(sem);
+ if (ret == 1)
+ rwsem_acquire(&sem->dep_map, 0, 0, _THIS_IP_);
rwsemtrace(sem,"Leaving down_write_trylock");
return ret;
}
@@ -85,16 +119,34 @@ static inline int down_write_trylock(str
*/
static inline void up_read(struct rw_semaphore *sem)
{
+ rwsem_release(&sem->dep_map, 1, _THIS_IP_);
+
rwsemtrace(sem,"Entering up_read");
__up_read(sem);
rwsemtrace(sem,"Leaving up_read");
}
+static inline void up_read_non_nested(struct rw_semaphore *sem)
+{
+ rwsem_release(&sem->dep_map, 0, _THIS_IP_);
+ __up_read(sem);
+}
+
+/*
+ * Not the owner will release it:
+ */
+static inline void up_read_non_owner(struct rw_semaphore *sem)
+{
+ __up_read(sem);
+}
+
/*
* release a write lock
*/
static inline void up_write(struct rw_semaphore *sem)
{
+ rwsem_release(&sem->dep_map, 1, _THIS_IP_);
+
rwsemtrace(sem,"Entering up_write");
__up_write(sem);
rwsemtrace(sem,"Leaving up_write");
@@ -105,6 +157,10 @@ static inline void up_write(struct rw_se
*/
static inline void downgrade_write(struct rw_semaphore *sem)
{
+ /*
+ * lockdep: a downgraded write will live on as a write
+ * dependency.
+ */
rwsemtrace(sem,"Entering downgrade_write");
__downgrade_write(sem);
rwsemtrace(sem,"Leaving downgrade_write");
diff -puN include/linux/rwsem-spinlock.h~lock-validator-prove-rwsem-locking-correctness include/linux/rwsem-spinlock.h
--- devel/include/linux/rwsem-spinlock.h~lock-validator-prove-rwsem-locking-correctness 2006-05-29 18:12:59.000000000 -0700
+++ devel-akpm/include/linux/rwsem-spinlock.h 2006-05-29 18:12:59.000000000 -0700
@@ -35,6 +35,9 @@ struct rw_semaphore {
#if RWSEM_DEBUG
int debug;
#endif
+#ifdef CONFIG_PROVE_RWSEM_LOCKING
+ struct lockdep_map dep_map;
+#endif
};
/*
@@ -46,16 +49,32 @@ struct rw_semaphore {
#define __RWSEM_DEBUG_INIT /* */
#endif
+#ifdef CONFIG_PROVE_RWSEM_LOCKING
+# define __RWSEM_DEP_MAP_INIT(lockname) , .dep_map = { .name = #lockname }
+#else
+# define __RWSEM_DEP_MAP_INIT(lockname)
+#endif
+
#define __RWSEM_INITIALIZER(name) \
-{ 0, SPIN_LOCK_UNLOCKED, LIST_HEAD_INIT((name).wait_list) __RWSEM_DEBUG_INIT }
+{ 0, SPIN_LOCK_UNLOCKED, LIST_HEAD_INIT((name).wait_list) __RWSEM_DEBUG_INIT __RWSEM_DEP_MAP_INIT(name) }
#define DECLARE_RWSEM(name) \
struct rw_semaphore name = __RWSEM_INITIALIZER(name)
-extern void FASTCALL(init_rwsem(struct rw_semaphore *sem));
+extern void __init_rwsem(struct rw_semaphore *sem, const char *name,
+ struct lockdep_type_key *key);
+
+#define init_rwsem(sem) \
+do { \
+ static struct lockdep_type_key __key; \
+ \
+ __init_rwsem((sem), #sem, &__key); \
+} while (0)
+
extern void FASTCALL(__down_read(struct rw_semaphore *sem));
extern int FASTCALL(__down_read_trylock(struct rw_semaphore *sem));
extern void FASTCALL(__down_write(struct rw_semaphore *sem));
+extern void FASTCALL(__down_write_nested(struct rw_semaphore *sem, int subtype));
extern int FASTCALL(__down_write_trylock(struct rw_semaphore *sem));
extern void FASTCALL(__up_read(struct rw_semaphore *sem));
extern void FASTCALL(__up_write(struct rw_semaphore *sem));
diff -puN lib/rwsem.c~lock-validator-prove-rwsem-locking-correctness lib/rwsem.c
--- devel/lib/rwsem.c~lock-validator-prove-rwsem-locking-correctness 2006-05-29 18:12:59.000000000 -0700
+++ devel-akpm/lib/rwsem.c 2006-05-29 18:12:59.000000000 -0700
@@ -8,6 +8,25 @@
#include <linux/init.h>
#include <linux/module.h>
+/*
+ * Initialize an rwsem:
+ */
+void __init_rwsem(struct rw_semaphore *sem, const char *name,
+ struct lockdep_type_key *key)
+{
+ sem->count = RWSEM_UNLOCKED_VALUE;
+ spin_lock_init(&sem->wait_lock);
+ INIT_LIST_HEAD(&sem->wait_list);
+#if RWSEM_DEBUG
+ sem->debug = 0;
+#endif
+#ifdef CONFIG_PROVE_RWSEM_LOCKING
+ lockdep_init_map(&sem->dep_map, name, key);
+#endif
+}
+
+EXPORT_SYMBOL(__init_rwsem);
+
struct rwsem_waiter {
struct list_head list;
struct task_struct *task;
diff -puN lib/rwsem-spinlock.c~lock-validator-prove-rwsem-locking-correctness lib/rwsem-spinlock.c
--- devel/lib/rwsem-spinlock.c~lock-validator-prove-rwsem-locking-correctness 2006-05-29 18:12:59.000000000 -0700
+++ devel-akpm/lib/rwsem-spinlock.c 2006-05-29 18:12:59.000000000 -0700
@@ -30,7 +30,8 @@ void rwsemtrace(struct rw_semaphore *sem
/*
* initialise the semaphore
*/
-void fastcall init_rwsem(struct rw_semaphore *sem)
+void __init_rwsem(struct rw_semaphore *sem, const char *name,
+ struct lockdep_type_key *key)
{
sem->activity = 0;
spin_lock_init(&sem->wait_lock);
@@ -38,6 +39,9 @@ void fastcall init_rwsem(struct rw_semap
#if RWSEM_DEBUG
sem->debug = 0;
#endif
+#ifdef CONFIG_PROVE_RWSEM_LOCKING
+ lockdep_init_map(&sem->dep_map, name, key);
+#endif
}
/*
@@ -204,7 +208,7 @@ int fastcall __down_read_trylock(struct
* get a write lock on the semaphore
* - we increment the waiting count anyway to indicate an exclusive lock
*/
-void fastcall __sched __down_write(struct rw_semaphore *sem)
+void fastcall __sched __down_write_nested(struct rw_semaphore *sem, int subtype)
{
struct rwsem_waiter waiter;
struct task_struct *tsk;
@@ -247,6 +251,11 @@ void fastcall __sched __down_write(struc
rwsemtrace(sem, "Leaving __down_write");
}
+void fastcall __sched __down_write(struct rw_semaphore *sem)
+{
+ __down_write_nested(sem, 0);
+}
+
/*
* trylock for writing -- returns 1 if successful, 0 if contention
*/
@@ -331,7 +340,7 @@ void fastcall __downgrade_write(struct r
rwsemtrace(sem, "Leaving __downgrade_write");
}
-EXPORT_SYMBOL(init_rwsem);
+EXPORT_SYMBOL(__init_rwsem);
EXPORT_SYMBOL(__down_read);
EXPORT_SYMBOL(__down_read_trylock);
EXPORT_SYMBOL(__down_write);
_
Patches currently in -mm which might be from mingo@xxxxxxx are
hrtimer-export-symbols.patch
x86_64-fix-stack-mmap-randomization-for-compat.patch
git-acpi.patch
lock-validator-sound-oss-emu10k1-midic-cleanup.patch
fix-drivers-mfd-ucb1x00-corec-irq-probing-bug.patch
git-infiniband.patch
git-netdev-all.patch
fix-for-serial-uart-lockup.patch
lock-validator-lockdep-small-xfs-init_rwsem-cleanup.patch
swapless-pm-add-r-w-migration-entries.patch
i386-break-out-of-recursion-in-stackframe-walk.patch
x86-re-enable-generic-numa.patch
vdso-randomize-the-i386-vdso-by-moving-it-into-a-vma.patch
vdso-randomize-the-i386-vdso-by-moving-it-into-a-vma-tidy.patch
vdso-randomize-the-i386-vdso-by-moving-it-into-a-vma-arch_vma_name-fix.patch
work-around-ppc64-bootup-bug-by-making-mutex-debugging-save-restore-irqs.patch
kernel-kernel-cpuc-to-mutexes.patch
cond-resched-might-sleep-fix.patch
define-__raw_get_cpu_var-and-use-it.patch
ide-cd-end-of-media-error-fix.patch
spin-rwlock-init-cleanups.patch
lock-validator-introduce-warn_on_oncecond.patch
time-clocksource-infrastructure.patch
sched-comment-bitmap-size-accounting.patch
sched-fix-interactive-ceiling-code.patch
sched-implement-smpnice.patch
sched-protect-calculation-of-max_pull-from-integer-wrap.patch
sched-store-weighted-load-on-up.patch
sched-add-discrete-weighted-cpu-load-function.patch
sched-prevent-high-load-weight-tasks-suppressing-balancing.patch
sched-improve-stability-of-smpnice-load-balancing.patch
sched-improve-smpnice-load-balancing-when-load-per-task.patch
smpnice-dont-consider-sched-groups-which-are-lightly-loaded-for-balancing.patch
smpnice-dont-consider-sched-groups-which-are-lightly-loaded-for-balancing-fix.patch
sched-modify-move_tasks-to-improve-load-balancing-outcomes.patch
sched-avoid-unnecessarily-moving-highest-priority-task-move_tasks.patch
sched-avoid-unnecessarily-moving-highest-priority-task-move_tasks-fix-2.patch
sched_domain-handle-kmalloc-failure.patch
sched_domain-handle-kmalloc-failure-fix.patch
sched_domain-dont-use-gfp_atomic.patch
sched_domain-use-kmalloc_node.patch
sched_domain-allocate-sched_group-structures-dynamically.patch
sched-add-above-background-load-function.patch
mm-implement-swap-prefetching-fix.patch
pi-futex-futex-code-cleanups.patch
pi-futex-robust-futex-docs-fix.patch
pi-futex-introduce-debug_check_no_locks_freed.patch
pi-futex-introduce-warn_on_smp.patch
pi-futex-add-plist-implementation.patch
pi-futex-scheduler-support-for-pi.patch
pi-futex-rt-mutex-core.patch
pi-futex-rt-mutex-docs.patch
pi-futex-rt-mutex-docs-update.patch
pi-futex-rt-mutex-debug.patch
pi-futex-rt-mutex-tester.patch
pi-futex-rt-mutex-futex-api.patch
pi-futex-futex_lock_pi-futex_unlock_pi-support.patch
futex_requeue-optimization.patch
genirq-rename-desc-handler-to-desc-chip.patch
genirq-rename-desc-handler-to-desc-chip-power-fix.patch
genirq-rename-desc-handler-to-desc-chip-ia64-fix.patch
genirq-rename-desc-handler-to-desc-chip-ia64-fix-2.patch
genirq-sem2mutex-probe_sem-probing_active.patch
genirq-cleanup-merge-irq_affinity-into-irq_desc.patch
genirq-cleanup-remove-irq_descp.patch
genirq-cleanup-remove-fastcall.patch
genirq-cleanup-misc-code-cleanups.patch
genirq-cleanup-reduce-irq_desc_t-use-mark-it-obsolete.patch
genirq-cleanup-include-linux-irqh.patch
genirq-cleanup-merge-irq_dir-smp_affinity_entry-into-irq_desc.patch
genirq-cleanup-merge-pending_irq_cpumask-into-irq_desc.patch
genirq-cleanup-turn-arch_has_irq_per_cpu-into-config_irq_per_cpu.patch
genirq-debug-better-debug-printout-in-enable_irq.patch
genirq-add-retrigger-irq-op-to-consolidate-hw_irq_resend.patch
genirq-doc-comment-include-linux-irqh-structures.patch
genirq-doc-handle_irq_event-and-__do_irq-comments.patch
genirq-cleanup-no_irq_type-cleanups.patch
genirq-doc-add-design-documentation.patch
genirq-add-genirq-sw-irq-retrigger.patch
genirq-add-irq_noprobe-support.patch
genirq-add-irq_norequest-support.patch
genirq-add-irq_noautoen-support.patch
genirq-update-copyrights.patch
genirq-core.patch
genirq-add-irq-chip-support.patch
genirq-add-handle_bad_irq.patch
genirq-add-irq-wake-power-management-support.patch
genirq-add-sa_trigger-support.patch
genirq-cleanup-no_irq_type-no_irq_chip-rename.patch
genirq-convert-the-x86_64-architecture-to-irq-chips.patch
genirq-convert-the-i386-architecture-to-irq-chips.patch
genirq-convert-the-i386-architecture-to-irq-chips-fix-2.patch
genirq-more-verbose-debugging-on-unexpected-irq-vectors.patch
lock-validator-floppyc-irq-release-fix.patch
lock-validator-forcedethc-fix.patch
lock-validator-mutex-section-binutils-workaround.patch
lock-validator-add-__module_address-method.patch
lock-validator-better-lock-debugging.patch
lock-validator-locking-api-self-tests.patch
lock-validator-locking-init-debugging-improvement.patch
lock-validator-beautify-x86_64-stacktraces.patch
lock-validator-x86_64-document-stack-frame-internals.patch
lock-validator-stacktrace.patch
lock-validator-fown-locking-workaround.patch
lock-validator-sk_callback_lock-workaround.patch
lock-validator-irqtrace-core.patch
lock-validator-irqtrace-cleanup-include-asm-i386-irqflagsh.patch
lock-validator-irqtrace-cleanup-include-asm-x86_64-irqflagsh.patch
lock-validator-lockdep-add-local_irq_enable_in_hardirq-api.patch
lock-validator-add-per_cpu_offset.patch
lock-validator-add-per_cpu_offset-fix.patch
lock-validator-core.patch
lock-validator-procfs.patch
lock-validator-design-docs.patch
lock-validator-prove-rwsem-locking-correctness.patch
lock-validator-prove-spinlock-rwlock-locking-correctness.patch
lock-validator-prove-mutex-locking-correctness.patch
lock-validator-print-all-lock-types-on-sysrq-d.patch
lock-validator-x86_64-early-init.patch
lock-validator-smp-alternatives-workaround.patch
lock-validator-do-not-recurse-in-printk.patch
lock-validator-disable-nmi-watchdog-if-config_lockdep.patch
lock-validator-special-locking-bdev.patch
lock-validator-special-locking-direct-io.patch
lock-validator-special-locking-serial.patch
lock-validator-special-locking-dcache.patch
lock-validator-special-locking-i_mutex.patch
lock-validator-special-locking-s_lock.patch
lock-validator-special-locking-futex.patch
lock-validator-special-locking-genirq.patch
lock-validator-special-locking-completions.patch
lock-validator-special-locking-waitqueues.patch
lock-validator-special-locking-mm.patch
lock-validator-special-locking-slab.patch
lock-validator-special-locking-skb_queue_head_init.patch
lock-validator-special-locking-timerc.patch
lock-validator-special-locking-schedc.patch
lock-validator-special-locking-hrtimerc.patch
lock-validator-special-locking-sock_lock_init.patch
lock-validator-special-locking-af_unix.patch
lock-validator-special-locking-bh_lock_sock.patch
lock-validator-special-locking-mmap_sem.patch
lock-validator-special-locking-sb-s_umount.patch
lock-validator-special-locking-sb-s_umount-fix.patch
lock-validator-special-locking-jbd.patch
lock-validator-special-locking-posix-timers.patch
lock-validator-special-locking-sch_genericc.patch
lock-validator-special-locking-xfrm.patch
lock-validator-special-locking-sound-core-seq-seq_portsc.patch
lock-validator-enable-lock-validator-in-kconfig.patch
lock-validator-enable-lock-validator-in-kconfig-x86-only.patch
lock-validator-special-locking-kgdb.patch
detect-atomic-counter-underflows.patch
debug-shared-irqs.patch
make-frame_pointer-default=y.patch
mutex-subsystem-synchro-test-module.patch
vdso-print-fatal-signals.patch
vdso-improve-print_fatal_signals-support-by-adding-memory-maps.patch
-
To unsubscribe from this list: send the line "unsubscribe mm-commits" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
