The patch titled
lockdep core: improve the lock-chain-hash
has been added to the -mm tree. Its filename is
lockdep-core-improve-the-lock-chain-hash.patch
See http://www.zip.com.au/~akpm/linux/patches/stuff/added-to-mm.txt to find
out what to do about this
------------------------------------------------------
Subject: lockdep core: improve the lock-chain-hash
From: Ingo Molnar <mingo@xxxxxxx>
With CONFIG_DEBUG_LOCK_ALLOC turned off i was getting sporadic failures in
the locking self-test:
------------>
| Locking API testsuite:
----------------------------------------------------------------------------
| spin |wlock |rlock |mutex | wsem | rsem |
--------------------------------------------------------------------------
A-A deadlock: ok | ok | ok | ok | ok | ok |
A-B-B-A deadlock: ok | ok | ok | ok | ok | ok |
A-B-B-C-C-A deadlock: ok | ok | ok | ok | ok | ok |
A-B-C-A-B-C deadlock: ok | ok | ok | ok | ok | ok |
A-B-B-C-C-D-D-A deadlock: ok |FAILED| ok | ok | ok | ok |
A-B-C-D-B-D-D-A deadlock: ok | ok | ok | ok | ok | ok |
A-B-C-D-B-C-D-A deadlock: ok | ok | ok | ok | ok |FAILED|
after much debugging it turned out to be caused by accidental chain-hash
key collisions. The current hash is:
#define iterate_chain_key(key1, key2) \
(((key1) << MAX_LOCKDEP_KEYS_BITS/2) ^ \
((key1) >> (64-MAX_LOCKDEP_KEYS_BITS/2)) ^ \
(key2))
where MAX_LOCKDEP_KEYS_BITS is 11. This hash is pretty good as it will
shift by 5 bits in every iteration, where every new ID 'mixed' into the
hash would have up to 11 bits. But because there was a 6 bits overlap
between subsequent IDs and their high bits tended to be similar, there was
a chance for accidental chain-hash collision for a low number of locks
held.
the solution is to shift by 11 bits:
#define iterate_chain_key(key1, key2) \
(((key1) << MAX_LOCKDEP_KEYS_BITS) ^ \
((key1) >> (64-MAX_LOCKDEP_KEYS_BITS)) ^ \
(key2))
This keeps the hash perfect up to 5 locks held, but even above that the
hash is still good because 11 bits is a relative prime to the total 64
bits, so a complete match will only occur after 64 held locks (which doesnt
happen in Linux). Even after 5 locks held, entropy of the 5 IDs mixed into
the hash is already good enough so that overlap doesnt generate a colliding
hash ID.
with this change the false positives went away.
Signed-off-by: Ingo Molnar <mingo@xxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxx>
---
kernel/lockdep.c | 4 ++--
1 files changed, 2 insertions(+), 2 deletions(-)
diff -puN kernel/lockdep.c~lockdep-core-improve-the-lock-chain-hash kernel/lockdep.c
--- a/kernel/lockdep.c~lockdep-core-improve-the-lock-chain-hash
+++ a/kernel/lockdep.c
@@ -122,8 +122,8 @@ static struct list_head chainhash_table[
* unique.
*/
#define iterate_chain_key(key1, key2) \
- (((key1) << MAX_LOCKDEP_KEYS_BITS/2) ^ \
- ((key1) >> (64-MAX_LOCKDEP_KEYS_BITS/2)) ^ \
+ (((key1) << MAX_LOCKDEP_KEYS_BITS) ^ \
+ ((key1) >> (64-MAX_LOCKDEP_KEYS_BITS)) ^ \
(key2))
void lockdep_off(void)
_
Patches currently in -mm which might be from mingo@xxxxxxx are
lockdep-ifdef-fix.patch
prevent-timespec-timeval-to-ktime_t-overflow.patch
lockdep-do-not-touch-console-state-when-tainting-the-kernel.patch
use-the-correct-restart-option-for-futex_lock_pi.patch
git-netdev-all.patch
bootmem-use-max_dma_address-instead-of-low32limit.patch
slab-fix-lockdep-warnings.patch
slab-fix-lockdep-warnings-fix.patch
slab-fix-lockdep-warnings-fix-2.patch
i386-kill-references-to-xtime.patch
make-touch_nmi_watchdog-imply-touch_softlockup_watchdog-on.patch
make-touch_nmi_watchdog-imply-touch_softlockup_watchdog-on-fix.patch
let-warn_on-warn_on_once-return-the-condition.patch
let-warn_on-warn_on_once-return-the-condition-fix.patch
let-warn_on-warn_on_once-return-the-condition-fix-2.patch
spinlock_debug-dont-recompute-jiffies_per_loop.patch
lockdep-dont-pull-in-includes-when-lockdep-disabled.patch
rtmutex-clean-up-and-remove-some-extra-spinlocks.patch
rtmutex-clean-up-and-remove-some-extra-spinlocks-more.patch
lockdep-print-kernel-version.patch
check-return-value-of-cpu_callback.patch
posix-timers-fix-clock_nanosleep-doesnt-return-the-remaining-time-in-compatibility-mode-2.patch
posix-timers-fix-the-flags-handling-in-posix_cpu_nsleep-2.patch
has_stopped_jobs-cleanup.patch
__dequeue_signal-cleanup.patch
simplify-update_times-avoid-jiffies-jiffies_64-aliasing-problem-2.patch
do_sched_setscheduler-dont-take-tasklist_lock.patch
introduce-is_rt_policy-helper.patch
sched_setscheduler-fix-policy-checks.patch
reparent_to_init-use-has_rt_policy.patch
futex_find_get_task-dont-take-tasklist_lock.patch
sys_get_robust_list-dont-take-tasklist_lock.patch
make-spinlock-rwlock-annotations-more-accurate-by-using.patch
replace-_spin_trylock-with-spin_trylock-in-the-irq.patch
lockdep-core-add-enable-disable_irq_irqsave-irqrestore-apis.patch
set-exit_dead-state-in-do_exit-not-in-schedule.patch
kill-pf_dead-flag.patch
introduce-task_dead-state.patch
select_bad_process-kill-a-bogus-pf_dead-task_dead-check.patch
maximum-latency-tracking-infrastructure.patch
maximum-latency-tracking-infrastructure-tidy.patch
lockdep-core-improve-the-lock-chain-hash.patch
ntp-move-all-the-ntp-related-code-to-ntpc.patch
nfsd-lockdep-annotation.patch
sched-force-sbin-init-off-isolated-cpus.patch
sched-remove-unnecessary-sched-group-allocations.patch
sched-remove-unnecessary-sched-group-allocations-fix.patch
lower-migration-thread-stop-machine-prio.patch
sched-generic-sched_group-cpu-power-setup.patch
sched-add-above-background-load-function.patch
mm-implement-swap-prefetching.patch
sched-cleanup-remove-task_t-convert-to-struct-task_struct-prefetch.patch
genirq-convert-the-x86_64-architecture-to-irq-chips.patch
genirq-convert-the-i386-architecture-to-irq-chips.patch
genirq-irq-convert-the-move_irq-flag-from-a-32bit-word-to-a-single-bit.patch
genirq-irq-add-moved_masked_irq.patch
genirq-x86_64-irq-reenable-migrating-irqs-to-other-cpus.patch
genirq-msi-simplify-msi-enable-and-disable.patch
genirq-msi-make-the-msi-boolean-tests-return-either-0-or-1.patch
genirq-msi-implement-helper-functions-read_msi_msg-and-write_msi_msg.patch
genirq-msi-refactor-the-msi_ops.patch
genirq-msi-simplify-the-msi-irq-limit-policy.patch
genirq-irq-add-a-dynamic-irq-creation-api.patch
genirq-ia64-irq-dynamic-irq-support.patch
genirq-i386-irq-dynamic-irq-support.patch
genirq-x86_64-irq-dynamic-irq-support.patch
genirq-msi-make-the-msi-code-irq-based-and-not-vector-based.patch
genirq-x86_64-irq-move-msi-message-composition-into-io_apicc.patch
genirq-i386-irq-move-msi-message-composition-into-io_apicc.patch
genirq-msi-only-build-msi-apicc-on-ia64.patch
genirq-x86_64-irq-remove-the-msi-assumption-that-irq-==-vector.patch
genirq-i386-irq-remove-the-msi-assumption-that-irq-==-vector.patch
genirq-irq-remove-msi-hacks.patch
genirq-irq-generalize-the-check-for-hardirq_bits.patch
genirq-x86_64-irq-make-the-external-irq-handlers-report-their-vector-not-the-irq-number.patch
genirq-x86_64-irq-make-vector_irq-per-cpu.patch
genirq-x86_64-irq-make-vector_irq-per-cpu-warning-fix.patch
genirq-x86_64-irq-kill-gsi_irq_sharing.patch
genirq-x86_64-irq-kill-irq-compression.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
