[lkml]   [2019]   [Apr]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
Subject[PATCH 00/28] Optimize IRQ usage checks and other small bits
It would be desirable to optimize IRQ usage related checks as they
traverse dependency graph multiple times, especially for irq-unsafe
usage checks with backward search since most of the locks are

This series completely removes backward dependencies. The idea is to
mark locks whether they can be reached from irq-safe locks in forward
graph traverses after irq-safe locks are encountered.

As a result, this series not only cuts the dependency list entries by
half and saves memory, but also significantly reduces both forward and
backward checks, which is briefly demonstrated on a simple workload:
Linux kernel build (i.e., make clean; reboot; make vmlinux -j8).



direct dependencies: 6900 [max: 32768]
max bfs queue depth: 272
find-mask forwards checks: 2875
find-mask backwards checks: 50229


direct dependencies: 3444 [max: 16384] ( - 50 % )
max bfs queue depth: 223 ( - 18 % )
find-mask forwards checks: 370 ( - 87 % )
find-mask backwards checks: 0 ( - 100 % )

The patches are organized as follows:

Patches 1 - 18
My previous small improvements. They are trivial but each is made for a
reason, so I still post them here. Please give them a look, Peter. I
have carried them for a while and rebased them a couple of times solving

Patches 19 - 28
The new IRQ check algorithm implementation is fairly long, so I tried to
divide it into as many patches as I can (actually this does not help
much). Also I tried to describe what it does in changelogs as detailed
as I can.

The performance numbers have not considered Frederic's recent big
improvements. Anyway, this series happened in parallel and I'd be happy
to rebase it.

HEAD: 7037e8d0af6c8ce5657c83e894c756ee1d33ce80



Yuyang Du (28):
locking/lockdep: Change all print_*() return type to void
locking/lockdep: Add description and explanation in lockdep design doc
locking/lockdep: Adjust lock usage bit character checks
locking/lockdep: Remove useless conditional macro
locking/lockdep: Print the right depth for chain key colission
locking/lockdep: Update obsolete struct field description
locking/lockdep: Use lockdep_init_task for task initiation
locking/lockdep: Define INITIAL_CHAIN_KEY for chain keys to start with
locking/lockdep: Change the range of class_idx in held_lock struct
locking/lockdep: Remove unused argument in validate_chain() and
locking/lockdep: Update comment
locking/lockdep: Change type of the element field in circular_queue
locking/lockdep: Change the return type of __cq_dequeue()
locking/lockdep: Avoid constant checks in __bfs by using offset
locking/lockdep: Update comments on dependency search
locking/lockdep: Add explanation to lock usage rules in lockdep design
locking/lockdep: Remove redundant argument in check_deadlock
locking/lockdep: Remove unused argument in __lock_release
locking/lockdep: Optimize irq usage check when marking lock usage bit
locking/lockdep: Refactorize check_noncircular and check_redundant
locking/lockdep: Consolidate lock usage bit initialization
locking/lockdep: Adjust new bit cases in mark_lock
locking/lockdep: Update irqsafe lock bitmaps
locking/lockdep: Remove !dir in lock irq usage check
locking/lockdep: Implement new IRQ usage checking algorithm
locking/lockdep: Remove __bfs
locking/lockdep: Remove locks_before
locking/lockdep: Reduce lock_list_entries by half

Documentation/locking/lockdep-design.txt | 107 +++-
include/linux/lockdep.h | 51 +-
init/init_task.c | 2 +
kernel/fork.c | 3 -
kernel/locking/lockdep.c | 1033 ++++++++++++++++++------------
kernel/locking/lockdep_internals.h | 19 +-
kernel/locking/lockdep_proc.c | 1 -
7 files changed, 757 insertions(+), 459 deletions(-)


 \ /
  Last update: 2019-04-24 12:20    [W:0.159 / U:2.160 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site