lkml.org 
[lkml]   [2019]   [Apr]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Subject[PATCH 00/28] Optimize IRQ usage checks and other small bits
Date
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

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