The patch titled
lockdep core: improve the lock-chain-hash
has been removed from the -mm tree. Its filename is
lockdep-core-improve-the-lock-chain-hash.patch
This patch was dropped because it was merged into mainline or a subsystem tree
------------------------------------------------------
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 file 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
origin.patch
forcedeth-hardirq-lockdep-warning.patch
bonding-lockdep-annotation.patch
maximum-latency-tracking-infrastructure.patch
maximum-latency-tracking-infrastructure-tidy.patch
remove-the-old-bd_mutex-lockdep-annotation.patch
new-bd_mutex-lockdep-annotation.patch
doc-lockdep-design-explain-display-of-state-bits.patch
directed-yield-cpu_relax-variants-for-spinlocks-and-rw-locks.patch
directed-yield-direct-yield-of-spinlocks-for-powerpc.patch
directed-yield-direct-yield-of-spinlocks-for-s390.patch
sysrq-disable-lockdep-on-reboot.patch
typo-fixes-for-rt-mutex-designtxt.patch
completions-lockdep-annotate-on-stack-completions.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-introduce-child-field-in-sched_domain.patch
sched-cleanup-sched_group-cpu_power-setup.patch
sched-fixing-wrong-comment-for-find_idlest_cpu.patch
scheduler-numa-aware-placement-of-sched_group_allnodes.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
msi-simplify-msi-sanity-checks-by-adding-with-generic-irq-code.patch
msi-only-use-a-single-irq_chip-for-msi-interrupts.patch
msi-refactor-and-move-the-msi-irq_chip-into-the-arch-code.patch
msi-move-the-ia64-code-into-arch-ia64.patch
htirq-tidy-up-the-htirq-code.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
