Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Yuyang Du <duyuyang@gmail.com>
To:     peterz@infradead.org, will.deacon@arm.com, mingo@kernel.org
Cc:     bvanassche@acm.org, ming.lei@redhat.com, frederic@kernel.org,
        tglx@linutronix.de, linux-kernel@vger.kernel.org,
        Yuyang Du <duyuyang@gmail.com>
Subject: [PATCH 28/28] locking/lockdep: Reduce lock_list_entries by half
Date:   Wed, 24 Apr 2019 18:19:34 +0800
Message-Id: <20190424101934.51535-29-duyuyang@gmail.com>
In-Reply-To: <20190424101934.51535-1-duyuyang@gmail.com>
References: <20190424101934.51535-1-duyuyang@gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

The forward and backward dependencies consume the same number of
list_entries. Since backward dependencies are removed, the max number of
list_entries can be halved safely: MAX_LOCKDEP_ENTRIES /= 2, which goes
from 16384 to 8192 or 32768 to 16384.

Besides memory space reduction, the performance gain is also promising
with this new IRQ usage checking algorithm. We briefly show the
performance improvement on a simple workload: Linux kernel build (i.e.,
make clean; reboot; make vmlinux -j8). It is expected that for complex
real-world workloads with heavier lock usage and bigger dependency
graph, the benefits should be more.

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 % )

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep_internals.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 30d021b..3b4b3dd 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -92,11 +92,11 @@ enum {
  * table (if it's not there yet), and we check it for lock order
  * conflicts and deadlocks.
  */
-#define MAX_LOCKDEP_ENTRIES	16384UL
+#define MAX_LOCKDEP_ENTRIES	8194UL
 #define MAX_LOCKDEP_CHAINS_BITS	15
 #define MAX_STACK_TRACE_ENTRIES	262144UL
 #else
-#define MAX_LOCKDEP_ENTRIES	32768UL
+#define MAX_LOCKDEP_ENTRIES	16384UL
 
 #define MAX_LOCKDEP_CHAINS_BITS	16
 
-- 
1.8.3.1