[PATCH 00/28] Optimize IRQ usage checks and other small bits

[Yuyang Du <duyuyang@gmail.com>]

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