Messages in this thread | | | From | Yuyang Du <> | Subject | [PATCH 00/28] Optimize IRQ usage checks and other small bits | Date | Wed, 24 Apr 2019 18:19:06 +0800 |
| |
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 irq-unsafe.
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).
Results:
------ Before ------
direct dependencies: 6900 [max: 32768] max bfs queue depth: 272 find-mask forwards checks: 2875 find-mask backwards checks: 50229
----- After -----
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 confilicts.
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
Thanks, Yuyang
--
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 consistently 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 check_deadlock() 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 reference locking/lockdep: Update comments on dependency search locking/lockdep: Add explanation to lock usage rules in lockdep design doc 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(-)
-- 1.8.3.1
| |