From nobody Mon Sep 28 03:41:50 2026 Received: from mail-ot1-f54.google.com (mail-ot1-f54.google.com [209.85.210.54]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9BE3838D3ED for ; Thu, 27 Aug 2026 03:58:43 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803125; cv=none; b=ZvSiwS76J2skTGIBq0i4/po9z5EE7icZLeRCGLNtCvg0IOhOo7pvsgtDEccBf1WpbcIyd25+s/6JI6TLQLtB++GCbZy2nWnic/Q89wBPXBJTgTr+cOsvtAxWJUKxq+5odWSnSwShiK0IkFBbYi9LWfEkIKwVlczoWLvmQ53Ys6M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803125; c=relaxed/simple; bh=fnlndgyS+0lMEvKhIWQHZnrrmWJ12W0ngfJa+Pn3Asw=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=cxT6LMBEyqRVWRYG3v8rG8NOJa/bT5pRsrF3XXf4tRl4x3Jm2htcWDxRsr8VkVa5utATv+Ds+f6/J/5Rz1lFgvVK5VIXuzMlaLsnrJKYtOdGRjiX9dIjhSoK7e0tpgY8Khs+KaoLp3yTosl/RfkjPTylZITwycOA1EYZ8LXXJjM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=qfyIbhrU; arc=none smtp.client-ip=209.85.210.54 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="qfyIbhrU" Received: by mail-ot1-f54.google.com with SMTP id 46e09a7af769-7f4e1568932so154758a34.2 for ; Wed, 26 Aug 2026 20:58:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1787803122; x=1788407922; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=ielF9GNSqNYO2qJux1/hWiFGNLSXmzQdkPugM7U1Opk=; b=qfyIbhrUqsW4UjPeMqqAQNYMjaGABCGQOlR9bfC+wDe2wujRwSQP+rkBQThxxhx7fp Wv8WkR7OneSi7lx8v9EzJHgyKVD6CJ6uOW5xuPt/9CDfBhoLb4HSGqNDbaISUbOqBq7G IYnSYCnDHBQBkLWUCcDiWONWdBb0YTkfkzmYC+ahJR64RZ9/CmkAoUkIDDT9Fn5PAlvj x8K24TdCthYKuC5lX2heESsXrWAXwR+AA2l9YiKhU5fkMWfO3z+unVs4zkckT0mlqfgb jqCAXfgSfzO6GHIRmOere3fqSKYQi9jPBrWVb1CLtkozzrVLDksVLjKV7Gt2jEK3A/Pw kICg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1787803122; x=1788407922; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=ielF9GNSqNYO2qJux1/hWiFGNLSXmzQdkPugM7U1Opk=; b=oZ3glTMyHLZ6esWApAlqoYXWg+F/RuF2///4QiHnfkLB5NlInLdoWBAJzjVS3GqYuw DV0wbdNnyKiL7nt9IaFkItPya9XPss8IUF0Oz5A5Aq9UH+4ajfoAcehHBALPQQKy0Qyj RqUsOjwSQreTvF79tXz8wi7IsBuSeJhNJB4/LmNZ+pNouTVrKMDv9BXF5pjDOOolgZlb J3ZaTgtrfCxhdok0S2J6rvc+Bnh5sKBPoqNm8praZidE+BURMA6zSczV2tzNaBbHkKCV CR94LRXuyHRRdWjreu7KEhSl9wg8ajD/dZg2T7B6ew2ulfEQpu/2FQAWDBA7MWA3cx4E lrGA== X-Gm-Message-State: AFuF++lQF9aOKvd4Xl2cHKhdtM9VRiC7jBECYqMCg77pzMnKDluIacqR YxlgBLMQV1Hae3I1Kd6Ma3Vw99RHXweL2A/sRSTC3o52O2C3iGhnQKwb X-Gm-Gg: AR+sD13oNjJe85SH2JYWRPcpfneRec2eom0X4d/v0WEfF5y4Vs30hdInR7Mc4vSQZq1 Zye7CoEwlIDbdirNDO6xS+oO2S3kFFPYJGhpGw/8Rc7/qYCd3g5asW42nocUZ6xzAZ0D+H81WsK ni2KHLS/gZBue9y6hXvrLRafM/AQBy560oK4/1eRPDkuWBHziA+G2lqb2YKZAjZUYYaYpo6FWZP hew8aTWe72OBn/z7V4P49/zilxxD8CgJMpN/f2OBJmqlKk45v5lkh/fWZRLVEzkcYHMhiHskvIs aSJhkQqrsjuYhzr4YCbcW4ZfRG049KHkFWU/QgX+WtD2i7+EBTGjn8c3N+YBVQSC2wB2GIZp9zV UsSgmwSqLBezlHI8DS8CqaxcwLdrnrRkZF3sMlY/nf88xDoeQmaJY8i0A6iJw1tqrm9PEghaAU1 xwqjeFMpRh0fZJMIXFqNFK998mcb8vHzBl0Aize1zLoLgFu0WHWbK00QTmE6KH8KurwT6Au+z6v M6KfZF6YSdgFAbLIeyCk8U5SEWc9uvFOuob32wwcoDdrUgGfaEMphJpVeyjSdyEkh2bnEX5RHxA 1NNOyNBN X-Received: by 2002:a05:6820:849a:b0:6a3:e0fb:6f39 with SMTP id 006d021491bc7-6b1a04d64c6mr10480599eaf.23.1787803122401; Wed, 26 Aug 2026 20:58:42 -0700 (PDT) Received: from [192.168.0.245] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-467367af2bfsm900825fac.6.2026.08.26.20.58.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Aug 2026 20:58:41 -0700 (PDT) From: Jim Cromie Date: Wed, 26 Aug 2026 21:58:33 -0600 Subject: [PATCH 1/8] lockdep: Traverse adjacency lists directly in zap_class() Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260826-lockdep-memblock-v1-v1-1-e2db855391ec@gmail.com> References: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> In-Reply-To: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> To: Peter Zijlstra , Ingo Molnar , Will Deacon , Boqun Feng , Waiman Long Cc: linux-kernel@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1787803120; l=3636; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=fnlndgyS+0lMEvKhIWQHZnrrmWJ12W0ngfJa+Pn3Asw=; b=BhJsCRPisozK9mZUxc1+Fl/TV0QfI84/20FK1Rj4lJcVcQtKsV93sMuQAcGGXh1FGQwjkYVji JpeZWEcPVPwDfF/nXsIi2BnLG10Z2EC+KDFrv+zJTGSZZWYFswAlAHq X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= Lockdep's canonical graph representation is its per-class adjacency lists (locks_after and locks_before). However, zap_class() operates on a flat storage-layer projection of the graph: it scans the global list_entries_in_use bitmap across the entire edge pool. This global scan has a few defects: 0. Search Inefficiency: On a typical booted laptop with ~2,000 lock classes and ~6,500 active dependency list entries, zapping a single class forces 6,500+ table inspections under graph_lock across 4 KB of bitmap. Zapping a batch of classes during module unload multiplies this into tens of thousands of global array iterations. 1. Projection maintenance: the bitmap must be kept up-to-date. given 0, its a net burden, but we still need the bitmap elsewhere. 2. Incompatible with Array Segmentation: The loop relies on contiguous pointer arithmetic (list_entries + i) to map bitmap indices back to entries. This completely breaks once list_entries is segmented into dynamic 64 kB memblock slabs residing on disjoint memory pages. So just implement the adjacency check literally, per graph-theory. Real-world lock classes have very short adjacency lists: 3..5 entries on average for class->locks_after and class->locks_before, rarely exceeding 15. Directly walking these lists visits only ~10..15 nodes per zapped class, replacing 6,500+ global table dereferences with a handful of cacheline-local pointer hops (>99.8% reduction in loop iterations). Note: We continue clearing bits in list_entries_in_use for now, as alloc_list_entry() still queries the bitmap in this commit. The bitmap itself is eliminated soon Signed-off-by: Jim Cromie --- kernel/locking/lockdep.c | 31 ++++++++++++++++++++++++------- 1 file changed, 24 insertions(+), 7 deletions(-) diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 2d4c5bab5af8..6a4f21f3e9c8 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -6243,8 +6243,7 @@ static void remove_class_from_lock_chains(struct pend= ing_free *pf, */ static void zap_class(struct pending_free *pf, struct lock_class *class) { - struct lock_list *entry; - int i; + struct lock_list *entry, *tmp, *other, *other_tmp; =20 WARN_ON_ONCE(!class->key); =20 @@ -6252,11 +6251,29 @@ static void zap_class(struct pending_free *pf, stru= ct lock_class *class) * Remove all dependencies this lock is * involved in: */ - for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) { - entry =3D list_entries + i; - if (entry->class !=3D class && entry->links_to !=3D class) - continue; - __clear_bit(i, list_entries_in_use); + list_for_each_entry_safe(entry, tmp, &class->locks_after, entry) { + list_for_each_entry_safe(other, other_tmp, &entry->links_to->locks_befor= e, entry) { + if (other->links_to =3D=3D class) { + __clear_bit(other - list_entries, list_entries_in_use); + nr_list_entries--; + list_del_rcu(&other->entry); + break; + } + } + __clear_bit(entry - list_entries, list_entries_in_use); + nr_list_entries--; + list_del_rcu(&entry->entry); + } + list_for_each_entry_safe(entry, tmp, &class->locks_before, entry) { + list_for_each_entry_safe(other, other_tmp, &entry->links_to->locks_after= , entry) { + if (other->links_to =3D=3D class) { + __clear_bit(other - list_entries, list_entries_in_use); + nr_list_entries--; + list_del_rcu(&other->entry); + break; + } + } + __clear_bit(entry - list_entries, list_entries_in_use); nr_list_entries--; list_del_rcu(&entry->entry); } --=20 2.55.0 From nobody Mon Sep 28 03:41:50 2026 Received: from mail-ot1-f51.google.com (mail-ot1-f51.google.com [209.85.210.51]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CB522390224 for ; Thu, 27 Aug 2026 03:58:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.51 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803126; cv=none; b=AvzwKqxbCzokS0TeLHdT+TmvOMG0ydA9usH3v8ouzpFHl5+WwFlLeAIC4aHeUvvSV7tSlmLaBIKN4xKJZP1OuFp4wgz/5f4vMzSM/CQDwUbbD2iNQhm84CZ2acS4uoqiuHQY1yBfsWzT5W8bz+G3p7zHqsI7rYt7pWnrW9CLJjs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803126; c=relaxed/simple; bh=LV7C+hevD5jo0Qd1ODKuYm9AUbl3ktdplJF7EunsPCM=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=Edu5oBcwROskNFG3U10PFZobrK3bKNHuZCgXwvuMIgtHxe98YzPehihG0wbejKwRqKOwyho6Fm3Fdahu9wmqhCh3Bt9ZCSaOIXg7R6lc8UZsihw8/XR+xhgoqb0R4LMBVoMrx4E2JGoQD6anY1Nls98tglONBiDSu56Ney+c64k= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=m1quY3s+; arc=none smtp.client-ip=209.85.210.51 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="m1quY3s+" Received: by mail-ot1-f51.google.com with SMTP id 46e09a7af769-7eb6573bd52so224156a34.3 for ; Wed, 26 Aug 2026 20:58:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1787803123; x=1788407923; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=k4Y2U8xWTC4FJYDwWkNZ0ZGiY0VW6Zu3Z+04xUlwhys=; b=m1quY3s+n/no3UyhIDquBgGuNM8GDdNjW5+yPTYff/QZOc7fx5A8yrh4bMjJIuSp2A 29EP6egEFWSjvSEkdiIMdGBm3DZusRf3aHKriD5reI7mWzLCNDxz7KNtUAh8/C9FLz8w xHcBMTd8i/Hvoztda4ycsJfwrfDElNhy2dYO4L0j1ubcQnl6RRlAzEBGw3PoyvM0r4EA 1F3Y+6R39LcJtmaWlRpuaywT05NfGeWDQQ72rczLXE9R3JMbBCar9TRX4iQU826Qb5sz zC8eFQiNvyO03sbPeW0DhW0Q7ysD+wXhrTUMvcw9gOtS9I8QN638Pz3tbnH2NgmF/V7V X3/g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1787803123; x=1788407923; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=k4Y2U8xWTC4FJYDwWkNZ0ZGiY0VW6Zu3Z+04xUlwhys=; b=T/QbUlIknApE49/zONk/vH58vQiO5FezDzKU7OPqYWDerGA6MziIsyj6CZTyslFVll zGXn6RA2Rq9/l6XRZAXfjPyBDVSxOLD797FjhrIHOygFZJLAP/TLxKn1pGZwbNf5t8ny tZlB6TDcKpoqEoDJbJw+ouTSiDL1wZ7P06FLrcgsXXOjbtsUBpKiLjfXPipoGIdy0G4P d5PE2aZaAyIl4ZU3d4nM1hUZLARGrbDg6iSOGwPqyLaL1eEFO1t1sUcymRfAfaMRe592 qy3/DF3DBz/KrHgIEcTpTA5GJRgqtqGBiukUZzk4KM+Fc/ZS6GXrApurYD5ufCbQ1jG5 pEnw== X-Gm-Message-State: AFuF++nMdD9pgxLyEz2SW29AnfQQitHb7CmOP3hu0mupxrVACdMK6zZi nJgy48xIxLhZilK+9d1WGAJhWXY9wDXj6EEvcqwikfHMxnos0VMfXQd1 X-Gm-Gg: AR+sD13VuFPIaxhbkE1V3nHu3d5ZvNp/uhHhWAb9aJxgdeI1FC6ezs3j7Zzb7Bk4bC9 opxbOIxFczXIdlxWkYqgMRItfaO7PwsaPzLHnzmqWxsg9nWiXo3eHQOBMSa0vltP/mc+r1K7FZd I19ZrtQAeE3OnhwKeuJKzAicJUvA4vU0dcDzf7RkOO0lITexSPXbr/Pb3AbOcY2YLmaC+a89wny A7DhATHGsRvAZA7mUtZ4zWzH/neiKUDE8p6Ygp9Rl2aMXmnlR4VkHmEFX4QqXP1Y5Dfyo70P8cS 4e6FGFQvVzyctHOWdZmbxU8PB5By3EandIcY2pn91St5yIMrRCnfmQvHfUsofzsEjMhkGDZLyT4 lvMAoUbFbRFEFhDaL3p8nJCtCeyk1lh9AwkKG5rB1aLPrJ2gsQKCYv8EzMg9TciVGZdnttTOCpQ JAoVkVKUIi/XmDvabj2JpC277YanFMkNkSzhZu7prSAaQFkC/RiFBJJbWFhB3EHSO0sIvJIwlLY ZoqtZUxNGYisbQSAXlnZD61sV/GQryzEjGcnlUq/yyqXERsynWK+vvpCCaYRdMXHffsm/5RKvHS AdCvf+sSLUggY+0b6Zwa X-Received: by 2002:a05:6820:55c4:10b0:6b1:4357:9fe9 with SMTP id 006d021491bc7-6b1a03675c0mr9390227eaf.6.1787803123629; Wed, 26 Aug 2026 20:58:43 -0700 (PDT) Received: from [192.168.0.245] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-467367af2bfsm900825fac.6.2026.08.26.20.58.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Aug 2026 20:58:42 -0700 (PDT) From: Jim Cromie Date: Wed, 26 Aug 2026 21:58:34 -0600 Subject: [PATCH 2/8] lockdep: Add chunked array infrastructure and embedded indices Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260826-lockdep-memblock-v1-v1-2-e2db855391ec@gmail.com> References: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> In-Reply-To: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> To: Peter Zijlstra , Ingo Molnar , Will Deacon , Boqun Feng , Waiman Long Cc: linux-kernel@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1787803120; l=4352; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=LV7C+hevD5jo0Qd1ODKuYm9AUbl3ktdplJF7EunsPCM=; b=1SwhDkg8pHPHGRaZqLjVF8JnKhDqodfKVGuFnFmAFrcu2BklyY1qDhOcxo5iFmQD2kU82FZZb LsNeOc5r/l/CzhamJZfEaKUhpP8J1sWURSpw6t56eSf0jY0erjU03Qp X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= Lockdep's dependency graph has historically relied on flat static arrays in .bss. To transition these tables to dynamically allocated slabs without incurring division instructions, introduce the DECLARE_CHUNKED_ARRAY() and DEFINE_CHUNKED_ARRAY() macros. These macros construct 2-tier chunked arrays (Array-of-Arrays) indexed via Granlund-Montgomery reciprocal divide (reciprocal_divide()), mapping indices to (chunk, offset) tuples in constant time (~3 cycles). Also embed class_idx into struct lock_class and chain_idx into struct lock_chain to replace flat pointer arithmetic (ptr - base) with O(1) index lookups across disjoint slab chunks. Signed-off-by: Jim Cromie --- include/linux/lockdep.h | 3 ++- include/linux/lockdep_types.h | 1 + kernel/locking/lockdep_internals.h | 48 ++++++++++++++++++++++++++++++++++= ++-- 3 files changed, 49 insertions(+), 3 deletions(-) diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h index 621566345406..4c96959d8ad7 100644 --- a/include/linux/lockdep.h +++ b/include/linux/lockdep.h @@ -77,7 +77,7 @@ struct lock_chain { unsigned int irq_context : 2, depth : 6, base : 24; - /* 4 byte hole */ + unsigned int chain_idx; struct hlist_node entry; u64 chain_key; }; @@ -85,6 +85,7 @@ struct lock_chain { /* * Initialization, self-test and debugging-output methods: */ +extern void lockdep_early_init(void); extern void lockdep_init(void); extern void lockdep_reset(void); extern void lockdep_reset_lock(struct lockdep_map *lock); diff --git a/include/linux/lockdep_types.h b/include/linux/lockdep_types.h index eae115a26488..8acac0b59f69 100644 --- a/include/linux/lockdep_types.h +++ b/include/linux/lockdep_types.h @@ -121,6 +121,7 @@ struct lock_class { =20 unsigned int subclass; unsigned int dep_gen_id; + unsigned int class_idx; =20 /* * IRQ/softirq usage tracking bits: diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_in= ternals.h index 0e5e6ffe91a3..3d8bce0dc9f9 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -122,9 +122,53 @@ enum { #define MAX_LOCKDEP_CHAINS (1UL << MAX_LOCKDEP_CHAINS_BITS) =20 #define AVG_LOCKDEP_CHAIN_DEPTH 5 -#define MAX_LOCKDEP_CHAIN_HLOCKS (MAX_LOCKDEP_CHAINS * AVG_LOCKDEP_CHAIN_D= EPTH) +#include =20 -extern struct lock_chain lock_chains[]; +#define LOCKDEP_SLAB_SIZE (64 * 1024) +#define LOCKDEP_MAX_SLABS 64 + +/* + * Chunked Array Tables: + * Replaces flat monolithic BSS arrays with 2D chunk pointer matrices. + * Chunk 0 is statically allocated in BSS for early boot, while subsequent + * chunks are claimed from the memblock reservoir via lockdep_claim_slab(). + * Indexing uses compile-time Granlund-Montgomery reciprocal divide + * (~3-cycle multiply+shift, zero division instructions). + */ +#define DECLARE_CHUNKED_ARRAY(name, type) \ + enum { \ + name##_PER_CHUNK =3D (LOCKDEP_SLAB_SIZE / sizeof(type)), \ + }; \ + extern type * name##_chunks[LOCKDEP_MAX_SLABS]; \ + extern const struct reciprocal_value name##_rv; \ + static __always_inline type *idx_to_##name(unsigned int idx) \ + { \ + unsigned int chunk =3D reciprocal_divide(idx, name##_rv); \ + unsigned int offset =3D idx - (chunk * name##_PER_CHUNK); \ + type *chunk_ptr; \ + if (unlikely(chunk >=3D LOCKDEP_MAX_SLABS)) \ + return NULL; \ + /* Pairs with smp_store_release() when new chunk slabs are published */ \ + chunk_ptr =3D smp_load_acquire(&name##_chunks[chunk]); \ + if (unlikely(!chunk_ptr)) \ + return NULL; \ + return &chunk_ptr[offset]; \ + } + +#define DEFINE_CHUNKED_ARRAY(name, type) \ + static type name##_chunk0[name##_PER_CHUNK]; \ + type *name##_chunks[LOCKDEP_MAX_SLABS] =3D { name##_chunk0 }; \ + static unsigned int nr_##name##_chunks =3D 1; \ + const struct reciprocal_value name##_rv =3D \ + RECIPROCAL_VALUE_INIT(name##_PER_CHUNK) + +struct lockdep_slab_usage { + unsigned int lock_classes; + unsigned int direct_deps; + unsigned int lock_chains; + unsigned int chain_hlocks; + unsigned int stack_traces; +}; =20 #define LOCK_USAGE_CHARS (2*XXX_LOCK_USAGE_STATES + 1) =20 --=20 2.55.0 From nobody Mon Sep 28 03:41:50 2026 Received: from mail-ot1-f47.google.com (mail-ot1-f47.google.com [209.85.210.47]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BAB75385D7B for ; Thu, 27 Aug 2026 03:58:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.47 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803127; cv=none; b=X+foScIVE2+APie3xMUymk+D6X3NKeg1MkKrR1SkDj2yqSz82CRY8J5EBPM6p8Rlxoks7NDTeE/ddR8jHs2xcrVeqCql6fclzL7ZUGcszJCo4cMGDuK3tCr3HnaqL7xkvw8ar6ysLVyEU4vPSQrnR9lT6BHF1K5TVmAi7e5+rSQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803127; c=relaxed/simple; bh=7xH2J5Hr5hCWfWqBYkebvmkGGwU+I/aNQBP7/OLO9LU=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=WKFW2bsWg/RmJrJz8QQnxVQhHCLBa6DUUgq5W34JSnifUAlenbvpoqGiApdxCUA8M8xNNu3muN6Me8PaHquGYll6Kj8D/sfsAE/kDEZl7gFpIucGpxxbBIjn4Tj7JOrlO109tHyhhoL1aIr7ylV6JgJRJKoR9oFqiRyJxyBNc0M= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=W9umTilU; arc=none smtp.client-ip=209.85.210.47 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="W9umTilU" Received: by mail-ot1-f47.google.com with SMTP id 46e09a7af769-7ee4399c423so1528258a34.0 for ; Wed, 26 Aug 2026 20:58:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1787803124; x=1788407924; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=VLB/ujA8yYDNmLHTN9IIlJkJcIVKxZQzZL5WlW6fCXc=; b=W9umTilUfZ+a6nbwoWlgcOGg1SSXKN5nElRXrxbhGecgXGa9CNpjHaiQ35cBzijFrV TACzN4YJkV/DZc6ff11UJDiLxKHt0eQjtlU+G56YKGpWrG8QmgeJVPLoEy1hQwFhrPs3 2CpyyVaorqqxDbb/s8ga8QETC8HlP6hUsxBmZ8FHaTskQFXxKHf0m906qNK2GI04AJtx b7g8sKbJf/OeNqVmJTFkaqvMxKWNDEqsfAcafGISlWaptLi03yZWGe7j8OAaPUnL7VgE E+2lTCrg7xGiKZ6YzK+4z7QDMnYcVP4mzREVei/3VTUcJ93x/AF4kBHY16ZSWkAZ7bUG vN9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1787803124; x=1788407924; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=VLB/ujA8yYDNmLHTN9IIlJkJcIVKxZQzZL5WlW6fCXc=; b=JRUUOV0hoShPXS7cX1CPt4giiFDACK/6FPYIQVD9rDkQbN7621d0FUT/Vdf/9IKf51 kPkq/zZeqzvdpsHxKLCGn1QjlDPPaVpsNJcbXy8sgh3dLt7wScnPVxkzqTsKB4F80Mhq /g+tt78zK5bKiaFnCjHlTYPQXcUJJsUY1fWhzmWp1LitsYHGz2hsXVdK9Vb7NFziLYHE fLzOiBrfQxZoCCDY+Oj52c1PGw1SqwAQ1KlG4qeyIlWALCchbYLNBQRMk3+EH+OPySma EgPH1Xp7FJSXYZ5y6QVt/Au9kfqLOJ0p3ysdMQpqKrS4pD3V9GFAYlmsafArUcUdoL1j QkmQ== X-Gm-Message-State: AFuF++m4wDU42t6YjgnAz3Teyuypx9Q9sdAvsfpO/PYwV44pZs/5owlR 7zcVQm/iqKgsrx3cRcm1VSo1ckQfE39g9gQzrY0OS+wVhvcEfuz8Hnzx X-Gm-Gg: AR+sD12WnA1tq2lfI5jOSF8R5I1tijNogEwnfI7ly2kE632U2/GWQUwvYnnoqsqt8pn XMrpE1R6mnMtX5RnXj4yG1Nk7FnT++avk5Lwh8meZ9fyi0ieEMMEWpPMPXutrhuuv08V4cBjX6L 8wDcCSxmpReeY6X3Q5iDbmzE00BU8e5qlh5s0wbETZeoWiLe5YzGHaK3h39h0fjp0mX568kATNM zwcX3E7hAehCyziv15OryIFQtm+Jf6B4ZLqGEMu5yLlbYvDm5IxgqKf2AK/aiIPIyRSW3QJ67Vb cSsQ1M+9dwqyY59b/2GD9s2UJYmLJW8yKMoJC0pwqJ9TrvtVCSv7wCMuR9KDxJCvJoEye/U7PBS 0AgnIo8AI+D3fiVyR9yAazUrRBw/ba3/lU9CVzRjplqtR2hGVjSsB92vD4RFKjxtLIcmnwPOMML eaPbG9fXMvTzLhx3gQuKYS41bMpwcpH45KabbzCdrXaGEjeZwHr6xgmuMLMonzl7UkRaP9c9C1b gxmWezbyjgEsp/SI27/By3j6FifEQKdvgGuAGftGfskux4+sYsT41MYs/jzHNDzLGzUlka0hrbn drD4J3zk X-Received: by 2002:a05:6820:1a05:b0:6ae:ab01:91a8 with SMTP id 006d021491bc7-6b1a053ad8amr10898047eaf.34.1787803124589; Wed, 26 Aug 2026 20:58:44 -0700 (PDT) Received: from [192.168.0.245] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-467367af2bfsm900825fac.6.2026.08.26.20.58.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Aug 2026 20:58:44 -0700 (PDT) From: Jim Cromie Date: Wed, 26 Aug 2026 21:58:35 -0600 Subject: [PATCH 3/8] lockdep: Pre-reserve early memblock slab pool for dynamic tables Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260826-lockdep-memblock-v1-v1-3-e2db855391ec@gmail.com> References: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> In-Reply-To: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> To: Peter Zijlstra , Ingo Molnar , Will Deacon , Boqun Feng , Waiman Long Cc: linux-kernel@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1787803120; l=6278; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=7xH2J5Hr5hCWfWqBYkebvmkGGwU+I/aNQBP7/OLO9LU=; b=cHlISIFFiAHVupKSDAtbApaG2C3y9p8jbxVPYHVvqMhd1OUwvzq0fuVqhrcBwgtMCXIub7seS WlMK8zK9JpuDrJyn7Fc2f8YsBc3aGHK0fCaq6oQ9TMFToZMywBArwll X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= Lockdep cannot allocate memory dynamically during normal runtime because it cannot recurse into allocator locks. However, before mm_core_init() brings up the buddy allocator, lockdep can claim a contiguous pool of 64 KB slabs directly from early memblock. Add lockdep_early_init() to start_kernel() right before mm_core_init() to reserve a private pool of 64 KB slabs. Auto-tune the pool based on physical RAM (2 MB on <512 MB systems, 4 MB default, 8 MB on >64 GB servers) and accept overrides via lockdep_slabs=3DN and lockdep_headroom=3DM%. Provide lockdep_claim_slab() and lockdep_release_slab() to dole out and recycle slabs under graph_lock without invoking external locks. Signed-off-by: Jim Cromie --- init/main.c | 1 + kernel/locking/lockdep.c | 131 +++++++++++++++++++++++++++++++++= ++++ kernel/locking/lockdep_internals.h | 3 +- 3 files changed, 134 insertions(+), 1 deletion(-) diff --git a/init/main.c b/init/main.c index e363232b428b..12280dfe1d11 100644 --- a/init/main.c +++ b/init/main.c @@ -1031,6 +1031,7 @@ void start_kernel(void) vfs_caches_init_early(); sort_main_extable(); trap_init(); + lockdep_early_init(); mm_core_init(); maple_tree_init(); poking_init(); diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 6a4f21f3e9c8..68d82e46cbf6 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -58,12 +58,96 @@ #include #include #include +#include =20 #include =20 #include "lockdep_internals.h" #include "lock_events.h" =20 +static void *lockdep_slabs[LOCKDEP_MAX_SLABS]; +static unsigned int lockdep_nr_slabs; +static unsigned int lockdep_slabs_used; +static struct lockdep_slab_usage ld_slabs; + +static unsigned int requested_lockdep_slabs; +static unsigned int requested_lockdep_headroom_pct =3D 100; /* default 100= % headroom */ +static bool lockdep_headroom_specified; +static bool lockdep_disabled_early; + +static int __init setup_lockdep_slabs(char *str) +{ + unsigned long val; + + if (!str) + return -EINVAL; + + if (!strcmp(str, "off") || !strcmp(str, "0")) { + lockdep_disabled_early =3D true; + return 0; + } + + if (kstrtoul(str, 0, &val)) + return -EINVAL; + + if (val > 10000) { + pr_warn("lockdep: ignoring unrealistic lockdep_slabs=3D%lu\n", + val); + return -EINVAL; + } + + requested_lockdep_slabs =3D clamp_t(unsigned int, val, 2, LOCKDEP_MAX_SLA= BS); + return 0; +} +early_param("lockdep_slabs", setup_lockdep_slabs); + +static int __init setup_lockdep_headroom(char *str) +{ + unsigned long val; + + if (!str || kstrtoul(str, 0, &val)) + return -EINVAL; + + requested_lockdep_headroom_pct =3D clamp_t(unsigned int, val, 10, 900); + lockdep_headroom_specified =3D true; + return 0; +} +early_param("lockdep_headroom", setup_lockdep_headroom); + +static void *lockdep_free_slabs[LOCKDEP_MAX_SLABS]; +static unsigned int lockdep_nr_free_slabs; + +/* + * Claim a 64KB slab from the pre-allocated memblock reservoir. + * Must be called with graph_lock held. Completely lockless and deadlock-f= ree. + */ +static void *lockdep_claim_slab(unsigned int *table_counter) +{ + void *slab; + + if (lockdep_nr_free_slabs > 0) + slab =3D lockdep_free_slabs[--lockdep_nr_free_slabs]; + else if (lockdep_slabs_used < lockdep_nr_slabs) + slab =3D lockdep_slabs[lockdep_slabs_used++]; + else + return NULL; + + if (table_counter) + (*table_counter)++; + + return slab; +} + +static void lockdep_release_slab(void *slab, unsigned int *table_counter) +{ + if (!slab || lockdep_nr_free_slabs >=3D LOCKDEP_MAX_SLABS) + return; + + lockdep_free_slabs[lockdep_nr_free_slabs++] =3D slab; + if (table_counter && *table_counter > 0) + (*table_counter)--; +} + #include =20 #ifdef CONFIG_PROVE_LOCKING @@ -6646,6 +6730,53 @@ void lockdep_unregister_key(struct lock_class_key *k= ey) } EXPORT_SYMBOL_GPL(lockdep_unregister_key); =20 +void __init lockdep_early_init(void) +{ + unsigned int nr_slabs, i; + phys_addr_t phys_mem; + size_t slab_bytes; + void *pool; + + if (lockdep_disabled_early) { + pr_info("lockdep: disabled by early boot parameter, 0 bytes reserved\n"); + return; + } + + phys_mem =3D memblock_phys_mem_size(); + + /* Auto-tune based on physical memory and CPU count */ + if (phys_mem && phys_mem < (512ULL << 20)) + nr_slabs =3D 32; /* 2 MB on small systems (<512MB RAM) */ + else if (num_possible_cpus() >=3D 64 || phys_mem > (64ULL << 30)) + nr_slabs =3D 128; /* 8 MB on large servers (>64GB RAM or >64 CPUs) */ + else + nr_slabs =3D LOCKDEP_DEFAULT_SLABS; /* 64 slabs =3D 4 MB default */ + + /* Ensure initial reservation satisfies requested floor or headroom */ + if (requested_lockdep_slabs > nr_slabs) + nr_slabs =3D requested_lockdep_slabs; + + if (lockdep_headroom_specified && requested_lockdep_headroom_pct > 100) + nr_slabs =3D (nr_slabs * (100 + requested_lockdep_headroom_pct)) / 100; + + nr_slabs =3D clamp_t(unsigned int, nr_slabs, 8, LOCKDEP_MAX_SLABS); + + slab_bytes =3D (size_t)nr_slabs * LOCKDEP_SLAB_SIZE; + pool =3D memblock_alloc(slab_bytes, PAGE_SIZE); + if (!pool) { + pr_err("lockdep: failed to allocate %u slabs (%zu KB) from memblock\n", + nr_slabs, slab_bytes / 1024); + return; + } + + for (i =3D 0; i < nr_slabs; i++) + lockdep_slabs[i] =3D (char *)pool + (i * LOCKDEP_SLAB_SIZE); + + lockdep_nr_slabs =3D nr_slabs; + pr_info("lockdep: reserved %u slabs (%zu KB) from memblock\n", + nr_slabs, slab_bytes / 1024); +} + void __init lockdep_init(void) { pr_info("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ing= o Molnar\n"); diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_in= ternals.h index 3d8bce0dc9f9..3344361a1c3b 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -125,7 +125,8 @@ enum { #include =20 #define LOCKDEP_SLAB_SIZE (64 * 1024) -#define LOCKDEP_MAX_SLABS 64 +#define LOCKDEP_MAX_SLABS 512 +#define LOCKDEP_DEFAULT_SLABS 64 =20 /* * Chunked Array Tables: --=20 2.55.0 From nobody Mon Sep 28 03:41:50 2026 Received: from mail-oa1-f53.google.com (mail-oa1-f53.google.com [209.85.160.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 6F1543911B8 for ; Thu, 27 Aug 2026 03:58:47 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803139; cv=none; b=DrvR6IHn0m1p4oK1I4TDilvkqG48seGM6lsfoyACAfmBIk8I4oYw3oZuBGEUHL5WOvO3GDfESciGsQYA6VcyPyZb8CBmiS0pZ4bSHE//yGDpCfFyI7Bag1BgvI96N7bW/AmFwdCGP4uYA1UvOJL1xSEOqgpJype21XnKzWB4rq4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803139; c=relaxed/simple; bh=eUJlr3S+tlnMUkhMti83bQSlzulWI/N3YDgJQpZ1gRU=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=m7m5/oh0ekiS2VJrpXbravSNlVrrkPODFmIMqEiUwJv1R8KNfBZqHDLqxeta/5F2C0RTWGzVaXToW34GcXtUrD7xoZETemju0W9UdcdztLB2mD7//FgPsHazzM5d24xwjqXXH2crXIIVy/ZYsBdd50DxBKZivC3KUpcsH5v5QM0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=l6T2VY52; arc=none smtp.client-ip=209.85.160.53 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="l6T2VY52" Received: by mail-oa1-f53.google.com with SMTP id 586e51a60fabf-44cedfaab6bso1075874fac.3 for ; Wed, 26 Aug 2026 20:58:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1787803126; x=1788407926; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=pvseZbNFrrFaJ94HsfVR4G6O+oWFmL5cv2VdBlThlw8=; b=l6T2VY52EshXeZ7V9TE5moRDMo0p0ZIqyj7KLrlp70Sb1y1ZOwvWJAwvOlRX4nkfHc HSqB6m9QeP5H/7NnO76lAYnzHyqWUqvfsjeOcWo6h5WlvWxglsdLsZKKTY58+R0+gkQe A2ovlbH6I64TY5YIcnMmhid0dcHE8rwzCFyg+b5QqAtUW1uOMx6dmUE9L9TFGeTEGqTj g0ALzdJ+DddJJqWOQ00/sIHYxkCU3xuoj13HE3GI7zvkS29laYadne2/kY0Vxlur9ZAE VLX5xxQeWh74VzEpDf87aAdDpHqrBo2HwNkmM5I0332M74KzqfsE29lo/XauXCOxB7nD 5nvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1787803126; x=1788407926; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=pvseZbNFrrFaJ94HsfVR4G6O+oWFmL5cv2VdBlThlw8=; b=tA5LeTuQ8oAQnQ93YFk3B5xNm2+5v4SdSTo2g+Pw/XbGNEXhpq+Ccljw66oPOX9NHx YNio2q8IN9I0ykw/qS4BFzZj6OCnz/lhJkJMzMzJZNI8JGCgsLO9dLCBXW10kNO7nY8X A1EtDPROUkkzBuXE+d0Des2AqAj/UY+fpf8q1p6FmjFGpV4XG8oOF+Fv/+zPs8rIEMcq kqRNo8RE2OPC6IXf5X/zciv6oupLwUkz7lswP/UMjOrDdNLc/Ehg6//YDz3SWXZdZvFw Fv4KzWoxymRJ8TkH+EuaI3bSK4g/CnUs+W0giimvP16AkkgCEHoeuRyXTS7l/AtFctUr Tnqw== X-Gm-Message-State: AFuF++mID+IkSR5Pkk1Rb/lNU0GJOpOyso0wJkSWrz5V1iCMgtI8PEyh aHky1O+J2SA9+rtzAjdleeI1A5Y9hQkdMJR9WlsxX++24CQAQ5M6Z2YNNfSpxNzF X-Gm-Gg: AR+sD11SmuHwm06ZfdHUQjqPLOuDL8UBGdTMHs0JVZPxCC2Zel+M4yOGQg3HX9ZEUtO 795KeTFlaLYQx0/tjcTrVAxgsecVzNmtudOPnXC4WlGcua2x8LYIWirnNDmv8CYNe+sEfgW9Kpu miUZfk0CGWwEKXZdefH1cU+xpL8W8D7fTsdtx+xErUB6yUxbkuTHU3X22TJfLiqqZ/67bVV4wzj Omw3WSF+hhutvBwYSWBRkaUdbnyupIGD45ZhhNO9Lq5urI4gNNWI1BxauYwMIGWVlKn+SrzjKBp ACl06QKd7tSM6KMev/zj5SCteN0UT9hyPz1lT+UIyiOFHWZQ1Os8GUrJQywA/yU6Y8HerL3AWtR bvcpQGUR6rghmlKPXJf31FsqlRwKPxUIbFbltP3ThMEc2EhXJJm78rCA2vyfi7Nui7y+32Ys/Jp cS4aws+H9zbD4krdPTRlmR3OJGZkAUcPmIpiOKxdZvU7RoO4oU+pwjv+f9zPGoBlZax/dGqeokH 7Cw60gLUDZUrDzjAkN5D7xw4joYLiVDcz/XaQ0tvh851Pxa3+GP+9UqRNaHkf7VVV968QKgsyX6 AXJx2EsIWLmC18w7YwQ= X-Received: by 2002:a05:6870:e389:b0:448:908d:27e0 with SMTP id 586e51a60fabf-465989452aemr13363935fac.4.1787803125939; Wed, 26 Aug 2026 20:58:45 -0700 (PDT) Received: from [192.168.0.245] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-467367af2bfsm900825fac.6.2026.08.26.20.58.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Aug 2026 20:58:45 -0700 (PDT) From: Jim Cromie Date: Wed, 26 Aug 2026 21:58:36 -0600 Subject: [PATCH 4/8] lockdep: Convert 5 graph arrays to chunked tables backed by slab pool Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260826-lockdep-memblock-v1-v1-4-e2db855391ec@gmail.com> References: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> In-Reply-To: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> To: Peter Zijlstra , Ingo Molnar , Will Deacon , Boqun Feng , Waiman Long Cc: linux-kernel@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1787803120; l=42873; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=eUJlr3S+tlnMUkhMti83bQSlzulWI/N3YDgJQpZ1gRU=; b=cB7AHJ6XuTEDG6SRTQFs6Zaldk12EY0oXpgNsgphfGtV9GmGc7wAwoLiutTxAxC75FI5t0b2x 8Rk4hwP4zhCCHTVquEnx0MEZKAGNQym0hm6ASiGMyE+yikQ0LkL5q52 X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= Replace the monolithic static .bss tables for lock_classes, list_entries, lock_chains, chain_hlocks, and stack_trace with 2D chunked arrays (DECLARE_CHUNKED_ARRAY) backed by the early memblock slab pool. Retain 1 static chunk (Chunk 0) in .bss per consumer (~320 kB total) to cover early bootstrap locking before memblock is initialized: - lock_classes: 409 items in Chunk 0 (160 B each) - list_entries: 1,365 items in Chunk 0 (48 B each) - lock_chains: 2,048 items in Chunk 0 (32 B each) - chain_hlocks: 32,768 items in Chunk 0 (2 B each) - stack_trace: 8,192 items in Chunk 0 (8 B each) Update allocators (alloc_lock_chain(), alloc_chain_hlocks(), alloc_list_entry(), save_trace()) to claim new 64 KB slabs dynamically from the memblock reservoir under graph_lock when chunk capacity is exhausted. Replace flat array pointer arithmetic with embedded struct indices (class->class_idx and chain->chain_idx). Signed-off-by: Jim Cromie --- include/linux/lockdep.h | 1 + include/linux/lockdep_types.h | 2 +- kernel/locking/lockdep.c | 600 ++++++++++++++++++++++++---------= ---- kernel/locking/lockdep_internals.h | 63 ++-- 4 files changed, 436 insertions(+), 230 deletions(-) diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h index 4c96959d8ad7..0ebb9a3e1bea 100644 --- a/include/linux/lockdep.h +++ b/include/linux/lockdep.h @@ -340,6 +340,7 @@ static inline void lockdep_set_selftest_task(struct tas= k_struct *task) # define lock_set_class(l, n, key, s, i) do { (void)(key); } while (0) # define lock_set_novalidate_class(l, n, i) do { } while (0) # define lock_set_subclass(l, s, i) do { } while (0) +# define lockdep_early_init() do { } while (0) # define lockdep_init() do { } while (0) # define lockdep_init_map_type(lock, name, key, sub, inner, outer, type) \ do { (void)(name); (void)(key); } while (0) diff --git a/include/linux/lockdep_types.h b/include/linux/lockdep_types.h index 8acac0b59f69..fa0dcf3c3f70 100644 --- a/include/linux/lockdep_types.h +++ b/include/linux/lockdep_types.h @@ -114,6 +114,7 @@ struct lock_class { * "backward" graph nodes. */ struct list_head locks_after, locks_before; + unsigned int class_idx; =20 const struct lockdep_subclass_key *key; lock_cmp_fn cmp_fn; @@ -121,7 +122,6 @@ struct lock_class { =20 unsigned int subclass; unsigned int dep_gen_id; - unsigned int class_idx; =20 /* * IRQ/softirq usage tracking bits: diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 68d82e46cbf6..1c8db52af1ac 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -58,7 +58,9 @@ #include #include #include +#include #include +#include =20 #include =20 @@ -148,6 +150,28 @@ static void lockdep_release_slab(void *slab, unsigned = int *table_counter) (*table_counter)--; } =20 +void lockdep_get_slab_stats(struct lockdep_slab_stats *st) +{ + st->total_slabs =3D lockdep_nr_slabs; + st->used_slabs =3D lockdep_slabs_used - lockdep_nr_free_slabs; + st->usage =3D ld_slabs; +} + +#define BOOTSTRAP_LOCKDEP_ENTRIES 1024UL + +static struct lock_list list_entries[BOOTSTRAP_LOCKDEP_ENTRIES]; +static struct lock_list *list_entries_freelist; +static struct lock_list *list_entries_cur =3D list_entries; +static unsigned int list_entries_remaining =3D BOOTSTRAP_LOCKDEP_ENTRIES; + +static inline void free_list_entry(struct lock_list *entry) +{ + if (!entry) + return; + *(void **)entry =3D list_entries_freelist; + list_entries_freelist =3D entry; +} + #include =20 #ifdef CONFIG_PROVE_LOCKING @@ -289,8 +313,6 @@ static inline int debug_locks_off_graph_unlock(void) } =20 unsigned long nr_list_entries; -static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES]; -static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES); =20 /* * All data structures here are protected by the global debug_lock. @@ -305,29 +327,25 @@ unsigned long nr_lock_classes; unsigned long nr_zapped_classes; unsigned long nr_dynamic_keys; unsigned long max_lock_class_idx; -struct lock_class lock_classes[MAX_LOCKDEP_KEYS]; + +DEFINE_CHUNKED_ARRAY(lock_class, struct lock_class); + +static void lockdep_print_watermarks(const char *bug_msg); + DECLARE_BITMAP(lock_classes_in_use, MAX_LOCKDEP_KEYS); =20 static inline struct lock_class *hlock_class(struct held_lock *hlock) { unsigned int class_idx =3D hlock->class_idx; =20 - /* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfield */ barrier(); =20 if (!test_bit(class_idx, lock_classes_in_use)) { - /* - * Someone passed in garbage, we give up. - */ DEBUG_LOCKS_WARN_ON(1); return NULL; } =20 - /* - * At this point, if the passed hlock->class_idx is still garbage, - * we just have to live with it - */ - return lock_classes + class_idx; + return idx_to_lock_class(class_idx); } =20 #ifdef CONFIG_LOCK_STAT @@ -388,7 +406,7 @@ void lock_stats(struct lock_class *class, struct lock_c= lass_stats *stats) memset(stats, 0, sizeof(struct lock_class_stats)); for_each_possible_cpu(cpu) { struct lock_class_stats *pcs =3D - &per_cpu(cpu_lock_stats, cpu)[class - lock_classes]; + &per_cpu(cpu_lock_stats, cpu)[class->class_idx]; =20 for (i =3D 0; i < ARRAY_SIZE(stats->contention_point); i++) stats->contention_point[i] +=3D pcs->contention_point[i]; @@ -413,7 +431,7 @@ void clear_lock_stats(struct lock_class *class) =20 for_each_possible_cpu(cpu) { struct lock_class_stats *cpu_stats =3D - &per_cpu(cpu_lock_stats, cpu)[class - lock_classes]; + &per_cpu(cpu_lock_stats, cpu)[class->class_idx]; =20 memset(cpu_stats, 0, sizeof(struct lock_class_stats)); } @@ -423,7 +441,7 @@ void clear_lock_stats(struct lock_class *class) =20 static struct lock_class_stats *get_lock_stats(struct lock_class *class) { - return &this_cpu_ptr(cpu_lock_stats)[class - lock_classes]; + return &this_cpu_ptr(cpu_lock_stats)[class->class_idx]; } =20 static void lock_release_holdtime(struct held_lock *hlock) @@ -555,9 +573,26 @@ static __always_inline void lockdep_recursion_finish(v= oid) __this_cpu_write(lockdep_recursion, 0); } =20 +static void lockdep_selftest_trace_start(void); +static void lockdep_selftest_trace_finish(void); +static void lockdep_report_stage(const char *domain, const char *stage_nam= e); + void lockdep_set_selftest_task(struct task_struct *task) { - lockdep_selftest_task_struct =3D task; + unsigned long flags; + + if (task) { + lockdep_selftest_task_struct =3D task; + lockdep_selftest_trace_start(); + return; + } + + lockdep_selftest_task_struct =3D NULL; + raw_local_irq_save(flags); + lockdep_lock(); + lockdep_selftest_trace_finish(); + lockdep_unlock(); + raw_local_irq_restore(flags); } =20 /* @@ -622,6 +657,7 @@ unsigned long nr_stack_trace_entries; * @nr_entries: Number of entries in @entries. * @entries: Actual stack backtrace. */ +#define STACK_TRACE_HASH_SIZE (1 << CONFIG_LOCKDEP_STACK_TRACE_HASH_BITS) struct lock_trace { struct hlist_node hash_entry; u32 hash; @@ -630,17 +666,80 @@ struct lock_trace { }; #define LOCK_TRACE_SIZE_IN_LONGS \ (sizeof(struct lock_trace) / sizeof(unsigned long)) -/* - * Stack-trace: sequence of lock_trace structures. Protected by the graph_= lock. - */ -static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES]; +#define BOOTSTRAP_STACK_TRACE_ENTRIES 4096UL +#define MAX_LOCKDEP_TRACE_DEPTH 48 + +static unsigned long stack_trace[BOOTSTRAP_STACK_TRACE_ENTRIES]; +static unsigned long *trace_free_ptr =3D stack_trace; +static size_t trace_remaining_longs =3D BOOTSTRAP_STACK_TRACE_ENTRIES; + +static void *trace_slabs[LOCKDEP_MAX_SLABS]; +static unsigned int nr_trace_slabs; + static struct hlist_head stack_trace_hash[STACK_TRACE_HASH_SIZE]; =20 -static bool traces_identical(struct lock_trace *t1, struct lock_trace *t2) +struct lockdep_selftest_snap { + unsigned int nr_trace_slabs; + unsigned long *trace_free_ptr; + size_t trace_remaining_longs; + unsigned long nr_trace_entries; +}; +static struct lockdep_selftest_snap selftest_snap; + +static void lockdep_selftest_trace_start(void) +{ + selftest_snap.nr_trace_slabs =3D nr_trace_slabs; + selftest_snap.trace_free_ptr =3D trace_free_ptr; + selftest_snap.trace_remaining_longs =3D trace_remaining_longs; + selftest_snap.nr_trace_entries =3D nr_stack_trace_entries; + + lockdep_report_stage("selftest", "pre-test"); +} + +static void lockdep_selftest_trace_finish(void) +{ + unsigned int reclaimed_slabs =3D 0; + unsigned int i; + + if (!debug_locks || !selftest_snap.trace_free_ptr) + return; + + lockdep_report_stage("selftest", "peak-test"); + + for (i =3D selftest_snap.nr_trace_slabs; i < nr_trace_slabs; i++) { + lockdep_release_slab(trace_slabs[i], &ld_slabs.stack_traces); + trace_slabs[i] =3D NULL; + reclaimed_slabs++; + } + nr_trace_slabs =3D selftest_snap.nr_trace_slabs; + trace_free_ptr =3D selftest_snap.trace_free_ptr; + trace_remaining_longs =3D selftest_snap.trace_remaining_longs; + nr_stack_trace_entries =3D selftest_snap.nr_trace_entries; + memset(stack_trace_hash, 0, sizeof(stack_trace_hash)); + + if (reclaimed_slabs) + pr_info("lockdep: selftest complete : recycled %u trace slabs (%u kB) to= pool\n", + reclaimed_slabs, (reclaimed_slabs * LOCKDEP_SLAB_SIZE) / 1024); + + lockdep_report_stage("selftest", "post-test"); +} + +static inline void lock_trace_discard(struct lock_trace *trace, unsigned i= nt max_entries) +{ + size_t needed_longs =3D LOCK_TRACE_SIZE_IN_LONGS + max_entries; + + if ((unsigned long *)trace + needed_longs =3D=3D trace_free_ptr) { + trace_free_ptr =3D (unsigned long *)trace; + trace_remaining_longs +=3D needed_longs; + } +} + +static inline void lock_trace_trim(struct lock_trace *trace, unsigned int = unused_entries) { - return t1->hash =3D=3D t2->hash && t1->nr_entries =3D=3D t2->nr_entries && - memcmp(t1->entries, t2->entries, - t1->nr_entries * sizeof(t1->entries[0])) =3D=3D 0; + if (unused_entries && trace_free_ptr) { + trace_free_ptr -=3D unused_entries; + trace_remaining_longs +=3D unused_entries; + } } =20 static struct lock_trace *save_trace(void) @@ -648,40 +747,59 @@ static struct lock_trace *save_trace(void) struct lock_trace *trace, *t2; struct hlist_head *hash_head; u32 hash; - int max_entries; + size_t needed_longs =3D LOCK_TRACE_SIZE_IN_LONGS + MAX_LOCKDEP_TRACE_DEPT= H; =20 BUILD_BUG_ON_NOT_POWER_OF_2(STACK_TRACE_HASH_SIZE); - BUILD_BUG_ON(LOCK_TRACE_SIZE_IN_LONGS >=3D MAX_STACK_TRACE_ENTRIES); - - trace =3D (struct lock_trace *)(stack_trace + nr_stack_trace_entries); - max_entries =3D MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries - - LOCK_TRACE_SIZE_IN_LONGS; =20 - if (max_entries <=3D 0) { - if (!debug_locks_off_graph_unlock()) - return NULL; + if (trace_remaining_longs < needed_longs) { + unsigned long *slab =3D lockdep_claim_slab(&ld_slabs.stack_traces); =20 - nbcon_cpu_emergency_enter(); - print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!"); - dump_stack(); - nbcon_cpu_emergency_exit(); + if (unlikely(!slab)) + goto out_fail; =20 - return NULL; + trace_slabs[nr_trace_slabs++] =3D slab; + trace_free_ptr =3D slab; + trace_remaining_longs =3D LOCKDEP_SLAB_SIZE / sizeof(unsigned long); } - trace->nr_entries =3D stack_trace_save(trace->entries, max_entries, 3); =20 - hash =3D jhash(trace->entries, trace->nr_entries * - sizeof(trace->entries[0]), 0); + trace =3D (struct lock_trace *)trace_free_ptr; + trace_free_ptr +=3D needed_longs; + trace_remaining_longs -=3D needed_longs; + + trace->nr_entries =3D stack_trace_save(trace->entries, MAX_LOCKDEP_TRACE_= DEPTH, 3); + hash =3D jhash(trace->entries, trace->nr_entries * sizeof(unsigned long),= 0); trace->hash =3D hash; hash_head =3D stack_trace_hash + (hash & (STACK_TRACE_HASH_SIZE - 1)); + hlist_for_each_entry(t2, hash_head, hash_entry) { - if (traces_identical(trace, t2)) + if (t2->hash =3D=3D hash && t2->nr_entries =3D=3D trace->nr_entries && + !memcmp(t2->entries, trace->entries, + trace->nr_entries * sizeof(unsigned long))) { + /* Duplicate hit: rewind speculative allocation */ + lock_trace_discard(trace, MAX_LOCKDEP_TRACE_DEPTH); return t2; + } } - nr_stack_trace_entries +=3D LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries; + + /* Novel trace: trim unused tail frames */ + if (trace->nr_entries < MAX_LOCKDEP_TRACE_DEPTH) + lock_trace_trim(trace, MAX_LOCKDEP_TRACE_DEPTH - trace->nr_entries); + hlist_add_head(&trace->hash_entry, hash_head); + nr_stack_trace_entries +=3D LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries; =20 return trace; + +out_fail: + if (!debug_locks_off_graph_unlock()) + return NULL; + + nbcon_cpu_emergency_enter(); + lockdep_print_watermarks("BUG: lockdep stack trace allocation failed!"); + dump_stack(); + nbcon_cpu_emergency_exit(); + + return NULL; } =20 /* Return the number of stack traces in the stack_trace[] array. */ @@ -1075,46 +1193,15 @@ static bool assign_lock_key(struct lockdep_map *loc= k) =20 #ifdef CONFIG_DEBUG_LOCKDEP =20 -/* Check whether element @e occurs in list @h */ -static bool in_list(struct list_head *e, struct list_head *h) -{ - struct list_head *f; - - list_for_each(f, h) { - if (e =3D=3D f) - return true; - } - - return false; -} - -/* - * Check whether entry @e occurs in any of the locks_after or locks_before - * lists. - */ -static bool in_any_class_list(struct list_head *e) -{ - struct lock_class *class; - int i; - - for (i =3D 0; i < ARRAY_SIZE(lock_classes); i++) { - class =3D &lock_classes[i]; - if (in_list(e, &class->locks_after) || - in_list(e, &class->locks_before)) - return true; - } - return false; -} - static bool class_lock_list_valid(struct lock_class *c, struct list_head *= h) { struct lock_list *e; =20 list_for_each_entry(e, h, entry) { if (e->links_to !=3D c) { - printk(KERN_INFO "class %s: mismatch for lock entry %ld; class %s <> %s= ", + pr_info("class %s: mismatch for lock entry %p; class %s <> %s", c->name ? : "(?)", - (unsigned long)(e - list_entries), + e, e->links_to && e->links_to->name ? e->links_to->name : "(?)", e->class && e->class->name ? e->class->name : @@ -1126,7 +1213,8 @@ static bool class_lock_list_valid(struct lock_class *= c, struct list_head *h) } =20 #ifdef CONFIG_PROVE_LOCKING -static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS]; +static u16 get_chain_hlock(unsigned int offset); +static void set_chain_hlock(unsigned int offset, u16 val); #endif =20 static bool check_lock_chain_key(struct lock_chain *chain) @@ -1136,14 +1224,14 @@ static bool check_lock_chain_key(struct lock_chain = *chain) int i; =20 for (i =3D chain->base; i < chain->base + chain->depth; i++) - chain_key =3D iterate_chain_key(chain_key, chain_hlocks[i]); + chain_key =3D iterate_chain_key(chain_key, get_chain_hlock(i)); /* * The 'unsigned long long' casts avoid that a compiler warning * is reported when building tools/lib/lockdep. */ if (chain->chain_key !=3D chain_key) { printk(KERN_INFO "chain %lld: key %#llx <> %#llx\n", - (unsigned long long)(chain - lock_chains), + (unsigned long long)chain->chain_idx, (unsigned long long)chain->chain_key, (unsigned long long)chain_key); return false; @@ -1152,42 +1240,15 @@ static bool check_lock_chain_key(struct lock_chain = *chain) return true; } =20 -static bool in_any_zapped_class_list(struct lock_class *class) -{ - struct pending_free *pf; - int i; - - for (i =3D 0, pf =3D delayed_free.pf; i < ARRAY_SIZE(delayed_free.pf); i+= +, pf++) { - if (in_list(&class->lock_entry, &pf->zapped)) - return true; - } - - return false; -} - static bool __check_data_structures(void) { struct lock_class *class; struct lock_chain *chain; struct hlist_head *head; - struct lock_list *e; int i; =20 - /* Check whether all classes occur in a lock list. */ - for (i =3D 0; i < ARRAY_SIZE(lock_classes); i++) { - class =3D &lock_classes[i]; - if (!in_list(&class->lock_entry, &all_lock_classes) && - !in_list(&class->lock_entry, &free_lock_classes) && - !in_any_zapped_class_list(class)) { - printk(KERN_INFO "class %px/%s is not in any class list\n", - class, class->name ? : "(?)"); - return false; - } - } - /* Check whether all classes have valid lock lists. */ - for (i =3D 0; i < ARRAY_SIZE(lock_classes); i++) { - class =3D &lock_classes[i]; + list_for_each_entry(class, &all_lock_classes, lock_entry) { if (!class_lock_list_valid(class, &class->locks_before)) return false; if (!class_lock_list_valid(class, &class->locks_after)) @@ -1203,38 +1264,6 @@ static bool __check_data_structures(void) } } =20 - /* - * Check whether all list entries that are in use occur in a class - * lock list. - */ - for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) { - e =3D list_entries + i; - if (!in_any_class_list(&e->entry)) { - printk(KERN_INFO "list entry %d is not in any class list; class %s <> %= s\n", - (unsigned int)(e - list_entries), - e->class->name ? : "(?)", - e->links_to->name ? : "(?)"); - return false; - } - } - - /* - * Check whether all list entries that are not in use do not occur in - * a class lock list. - */ - for_each_clear_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) { - e =3D list_entries + i; - if (in_any_class_list(&e->entry)) { - printk(KERN_INFO "list entry %d occurs in a class list; class %s <> %s\= n", - (unsigned int)(e - list_entries), - e->class && e->class->name ? e->class->name : - "(?)", - e->links_to && e->links_to->name ? - e->links_to->name : "(?)"); - return false; - } - } - return true; } =20 @@ -1286,11 +1315,15 @@ static void init_data_structures_once(void) INIT_LIST_HEAD(&delayed_free.pf[0].zapped); INIT_LIST_HEAD(&delayed_free.pf[1].zapped); =20 - for (i =3D 0; i < ARRAY_SIZE(lock_classes); i++) { - list_add_tail(&lock_classes[i].lock_entry, &free_lock_classes); - INIT_LIST_HEAD(&lock_classes[i].locks_after); - INIT_LIST_HEAD(&lock_classes[i].locks_before); + for (i =3D 0; i < lock_class_PER_CHUNK; i++) { + struct lock_class *class =3D &lock_class_chunk0[i]; + + class->class_idx =3D i; + list_add_tail(&class->lock_entry, &free_lock_classes); + INIT_LIST_HEAD(&class->locks_after); + INIT_LIST_HEAD(&class->locks_before); } + init_chain_block_buckets(); } =20 @@ -1371,7 +1404,7 @@ register_lock_class(struct lockdep_map *lock, unsigne= d int subclass, int force) struct lockdep_subclass_key *key; struct hlist_head *hash_head; struct lock_class *class; - int idx; + int idx, i; =20 DEBUG_LOCKS_WARN_ON(!irqs_disabled()); =20 @@ -1406,19 +1439,43 @@ register_lock_class(struct lockdep_map *lock, unsig= ned int subclass, int force) /* Allocate a new lock class and add it to the hash. */ class =3D list_first_entry_or_null(&free_lock_classes, typeof(*class), lock_entry); + if (!class) { + if (nr_lock_class_chunks < LOCKDEP_MAX_SLABS) { + struct lock_class *chunk; + unsigned int chunk_idx =3D nr_lock_class_chunks; + + chunk =3D lockdep_claim_slab(&ld_slabs.lock_classes); + if (chunk) { + memset(chunk, 0, sizeof(struct lock_class) * lock_class_PER_CHUNK); + for (i =3D 0; i < lock_class_PER_CHUNK; i++) { + struct lock_class *c =3D &chunk[i]; + + c->class_idx =3D chunk_idx * lock_class_PER_CHUNK + i; + INIT_LIST_HEAD(&c->locks_after); + INIT_LIST_HEAD(&c->locks_before); + list_add_tail(&c->lock_entry, &free_lock_classes); + } + /* Pairs with smp_load_acquire() in idx_to_lock_class() */ + smp_store_release(&lock_class_chunks[chunk_idx], chunk); + nr_lock_class_chunks++; + class =3D list_first_entry_or_null(&free_lock_classes, typeof(*class), + lock_entry); + } + } + } if (!class) { if (!debug_locks_off_graph_unlock()) { return NULL; } =20 nbcon_cpu_emergency_enter(); - print_lockdep_off("BUG: MAX_LOCKDEP_KEYS too low!"); + lockdep_print_watermarks("BUG: MAX_LOCKDEP_KEYS too low!"); dump_stack(); nbcon_cpu_emergency_exit(); return NULL; } nr_lock_classes++; - __set_bit(class - lock_classes, lock_classes_in_use); + __set_bit(class->class_idx, lock_classes_in_use); debug_atomic_inc(nr_unused_locks); class->key =3D key; class->name =3D lock->name; @@ -1439,7 +1496,7 @@ register_lock_class(struct lockdep_map *lock, unsigne= d int subclass, int force) * of classes. */ list_move_tail(&class->lock_entry, &all_lock_classes); - idx =3D class - lock_classes; + idx =3D class->class_idx; if (idx > max_lock_class_idx) max_lock_class_idx =3D idx; =20 @@ -1484,22 +1541,39 @@ register_lock_class(struct lockdep_map *lock, unsig= ned int subclass, int force) */ static struct lock_list *alloc_list_entry(void) { - int idx =3D find_first_zero_bit(list_entries_in_use, - ARRAY_SIZE(list_entries)); + struct lock_list *entry; =20 - if (idx >=3D ARRAY_SIZE(list_entries)) { - if (!debug_locks_off_graph_unlock()) - return NULL; + if (list_entries_freelist) { + entry =3D list_entries_freelist; + list_entries_freelist =3D *(void **)entry; + } else if (list_entries_remaining > 0) { + entry =3D list_entries_cur++; + list_entries_remaining--; + } else { + struct lock_list *slab =3D lockdep_claim_slab(&ld_slabs.direct_deps); =20 - nbcon_cpu_emergency_enter(); - print_lockdep_off("BUG: MAX_LOCKDEP_ENTRIES too low!"); - dump_stack(); - nbcon_cpu_emergency_exit(); - return NULL; + if (unlikely(!slab)) + goto out_fail; + + list_entries_cur =3D slab; + list_entries_remaining =3D LOCKDEP_SLAB_SIZE / sizeof(struct lock_list); + entry =3D list_entries_cur++; + list_entries_remaining--; } + + memset(entry, 0, sizeof(*entry)); nr_list_entries++; - __set_bit(idx, list_entries_in_use); - return list_entries + idx; + return entry; + +out_fail: + if (!debug_locks_off_graph_unlock()) + return NULL; + + nbcon_cpu_emergency_enter(); + print_lockdep_off("BUG: lockdep pool exhausted!"); + dump_stack(); + nbcon_cpu_emergency_exit(); + return NULL; } =20 /* @@ -3407,9 +3481,32 @@ check_prevs_add(struct task_struct *curr, struct hel= d_lock *next) return 0; } =20 -struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; +DEFINE_CHUNKED_ARRAY(lock_chain, struct lock_chain); static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); -static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS]; + +DEFINE_CHUNKED_ARRAY(chain_hlock, u16); +static unsigned int total_chain_hlocks_capacity =3D chain_hlock_PER_CHUNK; + +unsigned int chain_hlocks_used(void) +{ + return total_chain_hlocks_capacity - (nr_free_chain_hlocks + nr_lost_chai= n_hlocks); +} + +static inline u16 get_chain_hlock(unsigned int offset) +{ + u16 *p =3D idx_to_chain_hlock(offset); + + return p ? *p : 0; +} + +static inline void set_chain_hlock(unsigned int offset, u16 val) +{ + u16 *p =3D idx_to_chain_hlock(offset); + + if (p) + *p =3D val; +} + unsigned long nr_zapped_lock_chains; unsigned int nr_free_chain_hlocks; /* Free chain_hlocks in buckets */ unsigned int nr_lost_chain_hlocks; /* Lost chain_hlocks */ @@ -3459,7 +3556,7 @@ static inline int size_to_bucket(int size) */ static inline int chain_block_next(int offset) { - int next =3D chain_hlocks[offset]; + int next =3D get_chain_hlock(offset); =20 WARN_ON_ONCE(!(next & CHAIN_BLK_FLAG)); =20 @@ -3468,7 +3565,7 @@ static inline int chain_block_next(int offset) =20 next &=3D ~CHAIN_BLK_FLAG; next <<=3D 16; - next |=3D chain_hlocks[offset + 1]; + next |=3D get_chain_hlock(offset + 1); =20 return next; } @@ -3478,17 +3575,17 @@ static inline int chain_block_next(int offset) */ static inline int chain_block_size(int offset) { - return (chain_hlocks[offset + 2] << 16) | chain_hlocks[offset + 3]; + return (get_chain_hlock(offset + 2) << 16) | get_chain_hlock(offset + 3); } =20 static inline void init_chain_block(int offset, int next, int bucket, int = size) { - chain_hlocks[offset] =3D (next >> 16) | CHAIN_BLK_FLAG; - chain_hlocks[offset + 1] =3D (u16)next; + set_chain_hlock(offset, (next >> 16) | CHAIN_BLK_FLAG); + set_chain_hlock(offset + 1, (u16)next); =20 if (size && !bucket) { - chain_hlocks[offset + 2] =3D size >> 16; - chain_hlocks[offset + 3] =3D (u16)size; + set_chain_hlock(offset + 2, size >> 16); + set_chain_hlock(offset + 3, (u16)size); } } =20 @@ -3563,7 +3660,7 @@ static void init_chain_block_buckets(void) for (i =3D 0; i < MAX_CHAIN_BUCKETS; i++) chain_block_buckets[i] =3D -1; =20 - add_chain_block(0, ARRAY_SIZE(chain_hlocks)); + add_chain_block(0, chain_hlock_PER_CHUNK); } =20 /* @@ -3584,14 +3681,33 @@ static int alloc_chain_hlocks(int req) =20 init_data_structures_once(); =20 - if (nr_free_chain_hlocks < req) - return -1; - /* * We require a minimum of 2 (u16) entries to encode a freelist * 'pointer'. */ req =3D max(req, 2); + +retry: + if (nr_free_chain_hlocks < req) { + if (nr_chain_hlock_chunks < LOCKDEP_MAX_SLABS) { + unsigned int chunk_idx =3D nr_chain_hlock_chunks; + unsigned int base_offset =3D chunk_idx * chain_hlock_PER_CHUNK; + u16 *chunk; + + chunk =3D lockdep_claim_slab(&ld_slabs.chain_hlocks); + if (chunk) { + memset(chunk, 0, sizeof(u16) * chain_hlock_PER_CHUNK); + /* Pairs with smp_load_acquire() in idx_to_chain_hlock() */ + smp_store_release(&chain_hlock_chunks[chunk_idx], chunk); + nr_chain_hlock_chunks++; + total_chain_hlocks_capacity +=3D chain_hlock_PER_CHUNK; + add_chain_block(base_offset, chain_hlock_PER_CHUNK); + } + } + if (nr_free_chain_hlocks < req) + return -1; + } + bucket =3D size_to_bucket(req); curr =3D chain_block_buckets[bucket]; =20 @@ -3632,6 +3748,24 @@ static int alloc_chain_hlocks(int req) return curr; } =20 + /* If fragmented and chunks remain, expand with a new chunk */ + if (nr_chain_hlock_chunks < LOCKDEP_MAX_SLABS) { + unsigned int chunk_idx =3D nr_chain_hlock_chunks; + unsigned int base_offset =3D chunk_idx * chain_hlock_PER_CHUNK; + u16 *chunk; + + chunk =3D lockdep_claim_slab(&ld_slabs.chain_hlocks); + if (chunk) { + memset(chunk, 0, sizeof(u16) * chain_hlock_PER_CHUNK); + /* Pairs with smp_load_acquire() in idx_to_chain_hlock() */ + smp_store_release(&chain_hlock_chunks[chunk_idx], chunk); + nr_chain_hlock_chunks++; + total_chain_hlocks_capacity +=3D chain_hlock_PER_CHUNK; + add_chain_block(base_offset, chain_hlock_PER_CHUNK); + goto retry; + } + } + return -1; } =20 @@ -3642,10 +3776,10 @@ static inline void free_chain_hlocks(int base, int = size) =20 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i) { - u16 chain_hlock =3D chain_hlocks[chain->base + i]; + u16 chain_hlock =3D get_chain_hlock(chain->base + i); unsigned int class_idx =3D chain_hlock_class_idx(chain_hlock); =20 - return lock_classes + class_idx; + return idx_to_lock_class(class_idx); } =20 /* @@ -3710,10 +3844,10 @@ static void print_chain_keys_chain(struct lock_chai= n *chain) =20 printk("depth: %u\n", chain->depth); for (i =3D 0; i < chain->depth; i++) { - hlock_id =3D chain_hlocks[chain->base + i]; + hlock_id =3D get_chain_hlock(chain->base + i); chain_key =3D print_chain_key_iteration(hlock_id, chain_key); =20 - print_lock_name(NULL, lock_classes + chain_hlock_class_idx(hlock_id)); + print_lock_name(NULL, idx_to_lock_class(chain_hlock_class_idx(hlock_id))= ); printk("\n"); } } @@ -3768,7 +3902,7 @@ static int check_no_collision(struct task_struct *cur= r, for (j =3D 0; j < chain->depth - 1; j++, i++) { id =3D hlock_id(&curr->held_locks[i]); =20 - if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] !=3D id)) { + if (DEBUG_LOCKS_WARN_ON(get_chain_hlock(chain->base + j) !=3D id)) { print_collision(curr, hlock, chain); return 0; } @@ -3783,25 +3917,64 @@ static int check_no_collision(struct task_struct *c= urr, */ long lockdep_next_lockchain(long i) { - i =3D find_next_bit(lock_chains_in_use, ARRAY_SIZE(lock_chains), i + 1); - return i < ARRAY_SIZE(lock_chains) ? i : -2; + i =3D find_next_bit(lock_chains_in_use, MAX_LOCKDEP_CHAINS, i + 1); + return i < MAX_LOCKDEP_CHAINS ? i : -2; } =20 unsigned long lock_chain_count(void) { - return bitmap_weight(lock_chains_in_use, ARRAY_SIZE(lock_chains)); + return bitmap_weight(lock_chains_in_use, MAX_LOCKDEP_CHAINS); +} + +static void lockdep_print_watermarks(const char *bug_msg) +{ + print_lockdep_off(bug_msg); + pr_err("Lockdep Stats: classes=3D%lu (chunks=3D%u), entries=3D%lu, chains= =3D%lu (chunks=3D%u), hlocks=3D%u (chunks=3D%u)\n", + nr_lock_classes, nr_lock_class_chunks, + nr_list_entries, + lock_chain_count(), nr_lock_chain_chunks, + chain_hlocks_used(), nr_chain_hlock_chunks); + pr_err("Lockdep Slabs: total=3D%u, used=3D%u (classes=3D%u, entries=3D%u,= chains=3D%u, hlocks=3D%u, trace=3D%u), free=3D%u\n", + lockdep_nr_slabs, lockdep_slabs_used, + ld_slabs.lock_classes, ld_slabs.direct_deps, + ld_slabs.lock_chains, ld_slabs.chain_hlocks, + ld_slabs.stack_traces, + lockdep_nr_slabs > lockdep_slabs_used ? lockdep_nr_slabs - lockdep= _slabs_used : 0); + show_mem(); } =20 /* Must be called with the graph lock held. */ static struct lock_chain *alloc_lock_chain(void) { - int idx =3D find_first_zero_bit(lock_chains_in_use, - ARRAY_SIZE(lock_chains)); + int idx =3D find_first_zero_bit(lock_chains_in_use, MAX_LOCKDEP_CHAINS); + unsigned int chunk_idx; + struct lock_chain *chain; =20 - if (unlikely(idx >=3D ARRAY_SIZE(lock_chains))) + if (unlikely(idx >=3D MAX_LOCKDEP_CHAINS)) return NULL; + + chunk_idx =3D reciprocal_divide(idx, lock_chain_rv); + if (chunk_idx >=3D LOCKDEP_MAX_SLABS) + return NULL; + + if (chunk_idx >=3D nr_lock_chain_chunks) { + struct lock_chain *chunk; + + chunk =3D lockdep_claim_slab(&ld_slabs.lock_chains); + if (!chunk) + return NULL; + + memset(chunk, 0, sizeof(struct lock_chain) * lock_chain_PER_CHUNK); + /* Pairs with smp_load_acquire() in idx_to_lock_chain() */ + smp_store_release(&lock_chain_chunks[chunk_idx], chunk); + nr_lock_chain_chunks =3D chunk_idx + 1; + } + __set_bit(idx, lock_chains_in_use); - return lock_chains + idx; + chain =3D idx_to_lock_chain(idx); + memset(chain, 0, sizeof(*chain)); + chain->chain_idx =3D idx; + return chain; } =20 /* @@ -3833,7 +4006,7 @@ static inline int add_chain_cache(struct task_struct = *curr, return 0; =20 nbcon_cpu_emergency_enter(); - print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!"); + lockdep_print_watermarks("BUG: MAX_LOCKDEP_CHAINS too low!"); dump_stack(); nbcon_cpu_emergency_exit(); return 0; @@ -3843,9 +4016,9 @@ static inline int add_chain_cache(struct task_struct = *curr, i =3D get_first_held_lock(curr, hlock); chain->depth =3D curr->lockdep_depth + 1 - i; =20 - BUILD_BUG_ON((1UL << 24) <=3D ARRAY_SIZE(chain_hlocks)); + BUILD_BUG_ON((1UL << 24) <=3D MAX_LOCKDEP_CHAIN_HLOCKS); BUILD_BUG_ON((1UL << 6) <=3D ARRAY_SIZE(curr->held_locks)); - BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <=3D ARRAY_SIZE(lock_clas= ses)); + BUILD_BUG_ON((1UL << (8 * sizeof(u16))) <=3D MAX_LOCKDEP_KEYS); =20 j =3D alloc_chain_hlocks(chain->depth); if (j < 0) { @@ -3853,7 +4026,7 @@ static inline int add_chain_cache(struct task_struct = *curr, return 0; =20 nbcon_cpu_emergency_enter(); - print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!"); + lockdep_print_watermarks("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!"); dump_stack(); nbcon_cpu_emergency_exit(); return 0; @@ -3863,9 +4036,9 @@ static inline int add_chain_cache(struct task_struct = *curr, for (j =3D 0; j < chain->depth - 1; j++, i++) { int lock_id =3D hlock_id(curr->held_locks + i); =20 - chain_hlocks[chain->base + j] =3D lock_id; + set_chain_hlock(chain->base + j, lock_id); } - chain_hlocks[chain->base + j] =3D hlock_id(hlock); + set_chain_hlock(chain->base + j, hlock_id(hlock)); hlist_add_head_rcu(&chain->entry, hash_head); debug_atomic_inc(chain_lookup_misses); inc_chains(chain->irq_context); @@ -5222,7 +5395,7 @@ static int __lock_acquire(struct lockdep_map *lock, u= nsigned int subclass, if (DEBUG_LOCKS_WARN_ON(depth >=3D MAX_LOCK_DEPTH)) return 0; =20 - class_idx =3D class - lock_classes; + class_idx =3D class->class_idx; =20 if (depth && !sync) { /* we're holding locks and the new held lock is not a sync */ @@ -5413,7 +5586,7 @@ static noinstr int match_held_lock(const struct held_= lock *hlock, if (DEBUG_LOCKS_WARN_ON(!hlock->nest_lock)) return 0; =20 - if (hlock->class_idx =3D=3D class - lock_classes) + if (hlock->class_idx =3D=3D class->class_idx) return 1; } =20 @@ -5521,7 +5694,7 @@ __lock_set_class(struct lockdep_map *lock, const char= *name, lock->wait_type_outer, lock->lock_type); class =3D register_lock_class(lock, subclass, 0); - hlock->class_idx =3D class - lock_classes; + hlock->class_idx =3D class->class_idx; =20 curr->lockdep_depth =3D i; curr->curr_chain_key =3D hlock->prev_chain_key; @@ -5871,7 +6044,7 @@ static void verify_lock_unused(struct lockdep_map *lo= ck, struct held_lock *hlock if (!(class->usage_mask & mask)) return; =20 - hlock->class_idx =3D class - lock_classes; + hlock->class_idx =3D class->class_idx; =20 print_usage_bug(current, hlock, LOCK_USED, LOCK_USAGE_STATES); #endif @@ -6279,7 +6452,7 @@ static void remove_class_from_lock_chain(struct pendi= ng_free *pf, int i; =20 for (i =3D chain->base; i < chain->base + chain->depth; i++) { - if (chain_hlock_class_idx(chain_hlocks[i]) !=3D class - lock_classes) + if (chain_hlock_class_idx(get_chain_hlock(i)) !=3D class->class_idx) continue; /* * Each lock class occurs at most once in a lock chain so once @@ -6301,7 +6474,7 @@ static void remove_class_from_lock_chain(struct pendi= ng_free *pf, * hlist_for_each_entry_rcu() loop is safe. */ hlist_del_rcu(&chain->entry); - __set_bit(chain - lock_chains, pf->lock_chains_being_freed); + __set_bit(chain->chain_idx, pf->lock_chains_being_freed); nr_zapped_lock_chains++; #endif } @@ -6338,28 +6511,28 @@ static void zap_class(struct pending_free *pf, stru= ct lock_class *class) list_for_each_entry_safe(entry, tmp, &class->locks_after, entry) { list_for_each_entry_safe(other, other_tmp, &entry->links_to->locks_befor= e, entry) { if (other->links_to =3D=3D class) { - __clear_bit(other - list_entries, list_entries_in_use); nr_list_entries--; list_del_rcu(&other->entry); + free_list_entry(other); break; } } - __clear_bit(entry - list_entries, list_entries_in_use); nr_list_entries--; list_del_rcu(&entry->entry); + free_list_entry(entry); } list_for_each_entry_safe(entry, tmp, &class->locks_before, entry) { list_for_each_entry_safe(other, other_tmp, &entry->links_to->locks_after= , entry) { if (other->links_to =3D=3D class) { - __clear_bit(other - list_entries, list_entries_in_use); nr_list_entries--; list_del_rcu(&other->entry); + free_list_entry(other); break; } } - __clear_bit(entry - list_entries, list_entries_in_use); nr_list_entries--; list_del_rcu(&entry->entry); + free_list_entry(entry); } if (list_empty(&class->locks_after) && list_empty(&class->locks_before)) { @@ -6371,8 +6544,8 @@ static void zap_class(struct pending_free *pf, struct= lock_class *class) if (class->usage_mask =3D=3D 0) debug_atomic_dec(nr_unused_locks); nr_lock_classes--; - __clear_bit(class - lock_classes, lock_classes_in_use); - if (class - lock_classes =3D=3D max_lock_class_idx) + __clear_bit(class->class_idx, lock_classes_in_use); + if (class->class_idx =3D=3D max_lock_class_idx) max_lock_class_idx--; } else { WARN_ONCE(true, "%s() failed for class %s\n", __func__, @@ -6450,8 +6623,8 @@ static void __free_zapped_classes(struct pending_free= *pf) =20 #ifdef CONFIG_PROVE_LOCKING bitmap_andnot(lock_chains_in_use, lock_chains_in_use, - pf->lock_chains_being_freed, ARRAY_SIZE(lock_chains)); - bitmap_clear(pf->lock_chains_being_freed, 0, ARRAY_SIZE(lock_chains)); + pf->lock_chains_being_freed, MAX_LOCKDEP_CHAINS); + bitmap_clear(pf->lock_chains_being_freed, 0, MAX_LOCKDEP_CHAINS); #endif } =20 @@ -6773,12 +6946,16 @@ void __init lockdep_early_init(void) lockdep_slabs[i] =3D (char *)pool + (i * LOCKDEP_SLAB_SIZE); =20 lockdep_nr_slabs =3D nr_slabs; - pr_info("lockdep: reserved %u slabs (%zu KB) from memblock\n", + lockdep_slabs_used =3D 0; + + pr_info("lockdep: reserved %u slabs (%zu KB) from memblock for dynamic ta= bles\n", nr_slabs, slab_bytes / 1024); } =20 void __init lockdep_init(void) { + init_data_structures_once(); + pr_info("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ing= o Molnar\n"); =20 pr_info("... MAX_LOCKDEP_SUBCLASSES: %lu\n", MAX_LOCKDEP_SUBCLASSES); @@ -6789,26 +6966,25 @@ void __init lockdep_init(void) pr_info("... MAX_LOCKDEP_CHAINS: %lu\n", MAX_LOCKDEP_CHAINS); pr_info("... CHAINHASH_SIZE: %lu\n", CHAINHASH_SIZE); =20 - pr_info(" memory used by lock dependency info: %zu kB\n", - (sizeof(lock_classes) + + pr_info(" memory used by lock dependency info: dynamic (bootstrap %zu kB)= \n", + (sizeof(lock_class_chunk0) + sizeof(lock_classes_in_use) + sizeof(classhash_table) + sizeof(list_entries) + - sizeof(list_entries_in_use) + sizeof(chainhash_table) + sizeof(delayed_free) #ifdef CONFIG_PROVE_LOCKING + sizeof(lock_cq) - + sizeof(lock_chains) + + sizeof(lock_chain_chunk0) + sizeof(lock_chains_in_use) - + sizeof(chain_hlocks) + + sizeof(chain_hlock_chunk0) #endif ) / 1024 ); =20 #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) - pr_info(" memory used for stack traces: %zu kB\n", - (sizeof(stack_trace) + sizeof(stack_trace_hash)) / 1024 + pr_info(" memory used for stack traces: dynamic (bootstrap %zu kB)\n", + sizeof(stack_trace) / 1024 ); #endif =20 diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_in= ternals.h index 3344361a1c3b..eaa23d9b4dd5 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -7,6 +7,15 @@ * lockdep subsystem internal functions and variables. */ =20 +#include +#include +#include +#include + +#define LOCKDEP_SLAB_SIZE (64 * 1024) +#define LOCKDEP_MAX_SLABS 512 +#define LOCKDEP_DEFAULT_SLABS 64 + /* * Lock-class usage-state bits: */ @@ -122,19 +131,25 @@ enum { #define MAX_LOCKDEP_CHAINS (1UL << MAX_LOCKDEP_CHAINS_BITS) =20 #define AVG_LOCKDEP_CHAIN_DEPTH 5 -#include +#define MAX_LOCKDEP_CHAIN_HLOCKS (MAX_LOCKDEP_CHAINS * AVG_LOCKDEP_CHAIN_D= EPTH) =20 -#define LOCKDEP_SLAB_SIZE (64 * 1024) -#define LOCKDEP_MAX_SLABS 512 -#define LOCKDEP_DEFAULT_SLABS 64 +/* + * Compile-time precomputation of struct reciprocal_value using the canoni= cal + * Granlund-Montgomery algorithm matching lib/math/reciprocal_div.c. + */ +#define RECIPROCAL_VALUE_INIT(d) { \ + .m =3D (u32)((((1ULL << 32) * ((1ULL << (ilog2((d) - 1) + 1)) - (d))) / (= d)) + 1), \ + .sh1 =3D (ilog2((d) - 1) + 1) > 0 ? 1 : 0, \ + .sh2 =3D (ilog2((d) - 1) + 1) > 1 ? (ilog2((d) - 1) + 1) - 1 : 0, \ +} =20 /* * Chunked Array Tables: * Replaces flat monolithic BSS arrays with 2D chunk pointer matrices. * Chunk 0 is statically allocated in BSS for early boot, while subsequent * chunks are claimed from the memblock reservoir via lockdep_claim_slab(). - * Indexing uses compile-time Granlund-Montgomery reciprocal divide - * (~3-cycle multiply+shift, zero division instructions). + * Indexing uses a compile-time hybrid: single-cycle bit shifts for power-= of-2 + * elements, and Granlund-Montgomery reciprocal divide for non-power-of-2. */ #define DECLARE_CHUNKED_ARRAY(name, type) \ enum { \ @@ -156,20 +171,16 @@ enum { return &chunk_ptr[offset]; \ } =20 -#define DEFINE_CHUNKED_ARRAY(name, type) \ +#define DEFINE_CHUNKED_ARRAY(name, type) \ static type name##_chunk0[name##_PER_CHUNK]; \ type *name##_chunks[LOCKDEP_MAX_SLABS] =3D { name##_chunk0 }; \ static unsigned int nr_##name##_chunks =3D 1; \ const struct reciprocal_value name##_rv =3D \ RECIPROCAL_VALUE_INIT(name##_PER_CHUNK) =20 -struct lockdep_slab_usage { - unsigned int lock_classes; - unsigned int direct_deps; - unsigned int lock_chains; - unsigned int chain_hlocks; - unsigned int stack_traces; -}; +DECLARE_CHUNKED_ARRAY(lock_chain, struct lock_chain); +DECLARE_CHUNKED_ARRAY(chain_hlock, u16); +void lockdep_chain_stats(unsigned int *nr_chunks, size_t *chunk_size, size= _t *tail_used); =20 #define LOCK_USAGE_CHARS (2*XXX_LOCK_USAGE_STATES + 1) =20 @@ -201,9 +212,27 @@ extern unsigned int max_lockdep_depth; extern unsigned int max_bfs_queue_depth; extern unsigned long max_lock_class_idx; =20 -extern struct lock_class lock_classes[MAX_LOCKDEP_KEYS]; +DECLARE_2D_RADIX(lock_class, struct lock_class); extern unsigned long lock_classes_in_use[]; =20 +struct lockdep_slab_usage { + unsigned int lock_classes; + unsigned int direct_deps; + unsigned int lock_chains; + unsigned int chain_hlocks; + unsigned int stack_traces; +}; + +struct lockdep_slab_stats { + unsigned int total_slabs; + unsigned int used_slabs; + struct lockdep_slab_usage usage; +}; + +unsigned int chain_hlocks_used(void); +unsigned long lock_chain_count(void); +void lockdep_get_slab_stats(struct lockdep_slab_stats *st); + #ifdef CONFIG_PROVE_LOCKING extern unsigned long lockdep_count_forward_deps(struct lock_class *); extern unsigned long lockdep_count_backward_deps(struct lock_class *); @@ -286,7 +315,7 @@ static inline void debug_class_ops_inc(struct lock_clas= s *class) { int idx; =20 - idx =3D class - lock_classes; + idx =3D class->class_idx; __debug_atomic_inc(lock_class_ops[idx]); } =20 @@ -295,7 +324,7 @@ static inline unsigned long debug_class_ops_read(struct= lock_class *class) int idx, cpu; unsigned long ops =3D 0; =20 - idx =3D class - lock_classes; + idx =3D class->class_idx; for_each_possible_cpu(cpu) ops +=3D per_cpu(lockdep_stats.lock_class_ops[idx], cpu); return ops; --=20 2.55.0 From nobody Mon Sep 28 03:41:50 2026 Received: from mail-ot1-f54.google.com (mail-ot1-f54.google.com [209.85.210.54]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 62FBA36897F for ; Thu, 27 Aug 2026 03:58:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803131; cv=none; b=sRKpqF34aY4nKhQ+MAOtZGH4Uq49j3MMqS80e2dakKO4FvhCZGmaMWOIDoTaFaJ22hcDu+iz8CTT5ZYZEntx/LVTZ6UUFJOYQiqHLsnIGU22sevU773XMN2s1JtQ6gt2j3YnGC7ca8Ld7pXQFb+emJIBu0no15djVy3wtybi+IE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803131; c=relaxed/simple; bh=KBbn5zMVc11FFLiEDAyH0VD8kb3z5zwz1J7+56mGnFM=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=Am3YSd1yzoXrLLTtSfrBL9VR0VBhHuHgnHA6FoO7DjhpVLobT0YmKaJFltf3dJtaa3Po3+jgs0B1z4LcdZaF2+3CbUnoSQ3MpFwg81IDUMrz3mEA33jfCjj6WecPa9DAX/igywo0XuuwtywEsQAj4Wo7Y7tJMn99N/7l2q4pCkU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=cL2LYI/B; arc=none smtp.client-ip=209.85.210.54 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="cL2LYI/B" Received: by mail-ot1-f54.google.com with SMTP id 46e09a7af769-7eb9b427da2so596278a34.0 for ; Wed, 26 Aug 2026 20:58:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1787803127; x=1788407927; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=i1ZYKnbhx55UfIG6vLf2ZPoaGRdGf42KIjwnPPEG1OU=; b=cL2LYI/BZPNhuZ4AFoxQBk6llab2BH4F6hEyRqthG4+8IaVnUk6vXyK4lmE/lX9qH7 I/mLkrizF/4tV7U0Sdh9g2A2L4uqBQO1kuC8S+mF/+4OdyxsUXLXGqSQj2+wSRQh1JeE nitDw2K+Cef+PH96CqCklGOWJynxD8PWoErDwVQBoAFMxXAWOaVIiDD2DE3r7vQuS6Ma wAqnGgk5j4I0ql4Ftdrik2ocoQ/DkBpkMF9KPTrKbFMN9lP/rDwCKUVgTapiDGKEYanb i9wfcuxQAmXkEfKhPSab7RbyWxyAWlOONHZ3jJBOzNA74Gdqfaz0qdgTHqPbeNV+U8nd YzbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1787803127; x=1788407927; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=i1ZYKnbhx55UfIG6vLf2ZPoaGRdGf42KIjwnPPEG1OU=; b=OLxZwAU1xxeUYI8u3ZajDqfPhzWefvrQnvHkv/X777AO5d2o23D+YJ6O5Xt07cjsiS DgvIGczxWKJeo13xs27//1pWdjX59EyS4N8AaQYm9ogYXAmwQJ2i536asmCuyI1B09Id GtwoA8jE5LYGgfpf9MHJyENiMXovWeN/hVMDZzzhGckqHtdbur6Xduw/rNTM/zuhgrKW TOM6qN6n2viy7b6xJc8m94gGdx0fwsF9oX0GlrUmwBa+Mo8v4CA0YOOVFD3FJr9JY16A uLG7gEQ8A1vUeRi/f2lXp5bNuwX2u2BdTDU9vb8znAMRg+psCdn6Ke8WPs6Xzis8PmwK 4f4A== X-Gm-Message-State: AFuF++lzE9Nl8hH+yq9N6I02ayPSXg3k/azxKQPBF55JDPYTk7+NdGk8 /VxmrrGuX2gr1IvCj9mTytxSD4NjnmNauooGyUztVpQJzf7sgBK4mrU0 X-Gm-Gg: AR+sD131meDiR/dqmNxn+3o+c3XIG5a+dQXCDkmoxirX9IZgaWLVaSPtpIgQXLRt5tv 8sVS/rS7tdAREgBTuIBA/BCr5+Ml/MMMElvJiRO6ZcHnf7BWafOACCNbcVUsSkKUpJQ64xYQypt Zkd0jzvcRvDH2/PgOTmZfdARCraw96x1S+iGFoz96dRuzVKN7KJKGOWlumTac8I85X07rCKPhFe sWWUkVotFCZ8vSDdaxrifnleNjhro911B3cLQeeOqb6aVDD0lyp0COX8MGG4N1olCYeFtFD6HOm xnNxgPErndp9C+wIg9eykhuABYNsMtnMjEmYbUOIT9Fpne0Y9UpYTms7yhMzmZYj6XCyzeZc37m FqRdJT9PK7ERa+c9INuAVFoObYWW4+xTzJX+jNd1XtTZoyQjl6nXgGSOT6XIi9V6Mz2Ijx0Ph0D 20pDhDcZHNOD4QsmXmBfAtAfBfmpItszYLQ8sqf2Y7Mewacf3URhszkJPwDJEArVuTLPxdoEFK0 aELDapUcokHEKu0GDURCArCBmtMwNdx4pHzK/nePpfKndVH6MG248lP99XUq7eFHFTQf+cuYW2j 6HF8piJI X-Received: by 2002:a05:6820:4b14:b0:6b1:19dd:f2cb with SMTP id 006d021491bc7-6b1b00bdba0mr2985829eaf.12.1787803126896; Wed, 26 Aug 2026 20:58:46 -0700 (PDT) Received: from [192.168.0.245] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-467367af2bfsm900825fac.6.2026.08.26.20.58.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Aug 2026 20:58:46 -0700 (PDT) From: Jim Cromie Date: Wed, 26 Aug 2026 21:58:37 -0600 Subject: [PATCH 5/8] lockdep: Fast-path power-of-2 tables with shift/mask indexing Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260826-lockdep-memblock-v1-v1-5-e2db855391ec@gmail.com> References: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> In-Reply-To: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> To: Peter Zijlstra , Ingo Molnar , Will Deacon , Boqun Feng , Waiman Long Cc: linux-kernel@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1787803120; l=3516; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=KBbn5zMVc11FFLiEDAyH0VD8kb3z5zwz1J7+56mGnFM=; b=iFOeT+4MtfEBubaJMjX8+5la/Gq0dbjCnYl0hKvKo8WFzOz86V+Xn7YbBVfxtcFJNzVkAWBW9 y64UMLc9A7+CibPDhvdFrE0DJoNayNs5owJ1n3pw4gRNhAYx7Nd9y+f X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= The 2D chunked arrays (DECLARE_CHUNKED_ARRAY) use Granlund-Montgomery reciprocal division (reciprocal_divide()) to map indices to (chunk, offset) tuples across 64 KB slabs. This achieves >99.8% packing density for non-power-of-2 structs (lock_classes @ 160 B and list_entries @ 48 B). However, the ultra-hot cache-verification tables (lock_chains @ 32 B and chain_hlocks @ 2 B) have exact power-of-2 chunk counts (2,048 and 32,768 elements per 64 KB slab). Add a compile-time branch in DECLARE_CHUNKED_ARRAY() using __builtin_ctz(): for power-of-2 tables, GCC/Clang folds translation into single-cycle bit shifts (idx >> SHIFT) and masks (idx & MASK), eliminating reciprocal multiplication overhead entirely from the hot acquire validation path. Workload Progression (hackbench -p -g 8 -l 1000, 4 vCPUs): Metric Upstream (1D) Generic (P2) Fast-Path (P3) Delta =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Runtime 8.482 s 8.895 s (+4.8%) 8.278 s -2.40% Cycles 52899510936 55428687460 52033166458 -1.64% Instructions 29008189069 31932214532 31698626928 +9.27% By replacing G-M multiplication with single-cycle bit shifts on the hot cache verification tables, cycle overhead drops by ~6.4% relative to Patch 2, bringing total cycles to parity with or slightly faster than upstream baseline (-1.64% cycles). Signed-off-by: Jim Cromie --- kernel/locking/lockdep.c | 2 +- kernel/locking/lockdep_internals.h | 15 +++++++++++++-- 2 files changed, 14 insertions(+), 3 deletions(-) diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 1c8db52af1ac..b2dc7619a5e3 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -3953,7 +3953,7 @@ static struct lock_chain *alloc_lock_chain(void) if (unlikely(idx >=3D MAX_LOCKDEP_CHAINS)) return NULL; =20 - chunk_idx =3D reciprocal_divide(idx, lock_chain_rv); + chunk_idx =3D idx / lock_chain_PER_CHUNK; if (chunk_idx >=3D LOCKDEP_MAX_SLABS) return NULL; =20 diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_in= ternals.h index eaa23d9b4dd5..ccd7343af672 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -154,14 +154,25 @@ enum { #define DECLARE_CHUNKED_ARRAY(name, type) \ enum { \ name##_PER_CHUNK =3D (LOCKDEP_SLAB_SIZE / sizeof(type)), \ + name##_IS_P2 =3D (!(name##_PER_CHUNK & (name##_PER_CHUNK - 1))), \ + name##_SHIFT =3D (__builtin_ctz(name##_PER_CHUNK)), \ + name##_MASK =3D (name##_PER_CHUNK - 1), \ }; \ extern type * name##_chunks[LOCKDEP_MAX_SLABS]; \ extern const struct reciprocal_value name##_rv; \ static __always_inline type *idx_to_##name(unsigned int idx) \ { \ - unsigned int chunk =3D reciprocal_divide(idx, name##_rv); \ - unsigned int offset =3D idx - (chunk * name##_PER_CHUNK); \ + unsigned int chunk, offset; \ type *chunk_ptr; \ + \ + if (name##_IS_P2) { \ + chunk =3D idx >> name##_SHIFT; \ + offset =3D idx & name##_MASK; \ + } else { \ + chunk =3D reciprocal_divide(idx, name##_rv); \ + offset =3D idx - (chunk * name##_PER_CHUNK); \ + } \ + \ if (unlikely(chunk >=3D LOCKDEP_MAX_SLABS)) \ return NULL; \ /* Pairs with smp_store_release() when new chunk slabs are published */ \ --=20 2.55.0 From nobody Mon Sep 28 03:41:50 2026 Received: from mail-ot1-f41.google.com (mail-ot1-f41.google.com [209.85.210.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2707A384CC3 for ; Thu, 27 Aug 2026 03:58:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.41 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803133; cv=none; b=Mc3K35erwOLlDltHJ5OoQaqRy7ayY6wCN32suRY81ObqnjS5M7fszK0CHy6jHrgDmYZS676rRvdaSXtw4w4RqNZNkTJDE8Ttc14lcm5fWkEGA4riywVHH6P84BjbSOFoDal+WIEbKGW2Qw1FMaKYp6/SRwlgXvLi2cMUy1e4qD0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803133; c=relaxed/simple; bh=BzqgNjOdN0qWM98KhttEMRv4SJhBp4Q8vk+Bnvl2unQ=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=LC44IxGisNQY1rUdbpUb5KbDMLjRFpecoHzjlxK0+hk4IeOfg907h04zCSS7U2h1Z4jaPqjkmr0YwX9Qbg1rVXr9Xeb+c40F2XhqK7lQHptQ3AZCyobujcBTcUMmEzViKvcpTk9M7AnwzI+OJ9svmisXk6USFGN8HMxlQ4XdtKE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=Xf5CW7Pl; arc=none smtp.client-ip=209.85.210.41 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Xf5CW7Pl" Received: by mail-ot1-f41.google.com with SMTP id 46e09a7af769-7f4dedd67b8so290214a34.1 for ; Wed, 26 Aug 2026 20:58:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1787803128; x=1788407928; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=XDTVl8cWfdTr0o46le//A8VK9qr8kHkjMhgj3GG9T/8=; b=Xf5CW7PlFI6Ws8j3JYQcE+FC78l4ExlOK+TomvRgwJqcmHBPJo4B8RIrerwtb0ymAc ITZWgI2Xt30ErNw3xVPg1bu7fSDxd0plcaK5Pm5K39pQEPKcRyO8ix0nOKkCLtsU2WYa Hb13OOrnUGW44pO+ogGRkAky3yTJTm3TMmqAwsQ6vIY7QLN7oY9RBJrcYqTpLiUFuS2Q ZFEEJ14LuEnyjHlPtoHKV/+fZfB42aopGwU6lmCbtcHOTmJV9KQFtFT13GRRAzlr8tcu MF+XljN8zQm0Uf2zXWbM3ylXny+UX38sjNtRZivQz+OWzMkhr794BxkWmVDlxnoLFCxY H+lg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1787803128; x=1788407928; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=XDTVl8cWfdTr0o46le//A8VK9qr8kHkjMhgj3GG9T/8=; b=buJcf6VjFzcVs+1C3qFjwDF4c2x6HpvjkPZS+tpfknLX4i8f5dspCz4j/4Crkg3iAa vY0wsWjet22QBW7F30AyJACB/aay+VDWNNvHL/gbuP3DnBhsLVJi/ENJ6GLv3yyQjnKx f/p/m4lXeWf3pKo0naiQDWAvBU9iP6imv3WffkuJiVKAjQ9QFEKJZjKRJoGCvOVC3S7x Fs9Mlbqk2wSGe3cPPsHVD/HoI5UX8s+CWajIXFTSYdsnffjuqtmkdnhLHx9DZnTz6OaZ MLw+SSq8PsTrG4zjMhCE6eoqA8tTuiwh8rM6hqi7DyUdMKBKgwMV2fk30eAdK3+6g+t0 kAtA== X-Gm-Message-State: AFuF++lXIPVQRD00lKpQ73jhon16DdTmnffv8rd+4Cx9LQloGAW8kzdJ EIZLpJlADfS5mji+nDEr3Y/ZUjTeZI6srNfHq0DLqjZ4gno13reXElIv X-Gm-Gg: AR+sD11O82P3tn7iEH2JzyQxGhZe1KOTi5Y3fWo+OJnFTJ4yqmdJUN4he5ToL6jyWeY TsnTNjr6V+4G6oQnuL22bgPPwzsHogXtCZ8gJMgquJRs5WpFOIFAWNonhKrfKq2Pgcyq+LYHug2 0woaSHgvJAyrP9S89unYe2wSYTZcK0WAnvPvd4vz4ULFpE/ekMGwyr+Zn+Te5N+ixkLoCFTzInL nfqJBRkacngsYC3f9OAarR3khKwCANav2fvDRKOShWsdwjtArZkhacmn4XdmqHmJxYC6diRgS5n jSD0pi4dDrmOvkm1FP/6472u9OI908tS53q7pt8XW0n8d5nxU15Bk++C3EclH9lLyfgKnXv1PmD JYEsRB2s70HTcLI1vZ9xb8vdQdUJogMhL1ZXxLc8DxjuVhdpMqB8v9bDhhKrVCSTuZGI+U+ocuZ 06brnKX8gRNT2i+/zG5tYwUS28t70/OQZRxULHuU1rzQTZ+IXs8xHI728cuatHzkBYTku6LIzV2 fw1vc4nua9TPAhSetWHCiN8LSDg7CXe0HISeGp5YcIjMH+HMNibqlqSBIXEO9lF2/ZcNhnlJqdu qJaSzE+jmaYfFffUlTA= X-Received: by 2002:a05:6820:8593:10b0:6b1:3756:f77a with SMTP id 006d021491bc7-6b1a0389cdcmr9677806eaf.4.1787803128002; Wed, 26 Aug 2026 20:58:48 -0700 (PDT) Received: from [192.168.0.245] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-467367af2bfsm900825fac.6.2026.08.26.20.58.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Aug 2026 20:58:47 -0700 (PDT) From: Jim Cromie Date: Wed, 26 Aug 2026 21:58:38 -0600 Subject: [PATCH 6/8] lockdep: Free unused reservation slabs to buddy allocator at late boot Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260826-lockdep-memblock-v1-v1-6-e2db855391ec@gmail.com> References: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> In-Reply-To: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> To: Peter Zijlstra , Ingo Molnar , Will Deacon , Boqun Feng , Waiman Long Cc: linux-kernel@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1787803120; l=5965; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=BzqgNjOdN0qWM98KhttEMRv4SJhBp4Q8vk+Bnvl2unQ=; b=MDUgGiEKUryrVrUZTIzcm+YR05qsgFsIkE6zi/LCIGQDrkqmFmPPCH9mkQ5wfUrkqM5PcB3V8 OGWx/1mTYZZAEucbtYQYVoA70FFWI/xHZwNw4uGsbkAS1/2izErx2M1 X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= During early boot, lockdep reserves a generous slab pool (e.g. 64 slabs =3D 4 MB) from memblock to guarantee uninterrupted initialization. Once the kernel reaches late_initcall, the boot locking storm is complete, and lockdep's steady-state working set is known. Add lockdep_post_init_trim() as a late_initcall_sync handler. Calculate required runtime headroom (default 100% headroom over boot usage, with a floor of 32 slabs, or custom lockdep_slabs=3DN / lockdep_headroom=3DM%), and return all excess slabs to the buddy page allocator via free_reserved_page(). Also register a reboot notifier to log total lifetime slab consumption and remaining headroom on clean system shutdown. Signed-off-by: Jim Cromie --- kernel/locking/lockdep.c | 71 +++++++++++++++++++++++++++++++++++++++= ++++ kernel/locking/lockdep_proc.c | 23 +++++++------- 2 files changed, 83 insertions(+), 11 deletions(-) diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index b2dc7619a5e3..3fb6c07cea36 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -6992,6 +6992,77 @@ void __init lockdep_init(void) sizeof(((struct task_struct *)NULL)->held_locks)); } =20 +static int lockdep_shutdown_notify(struct notifier_block *nb, + unsigned long code, void *unused) +{ + unsigned int used =3D lockdep_slabs_used - lockdep_nr_free_slabs; + unsigned int total =3D lockdep_nr_slabs; + unsigned int free_slabs =3D total > used ? total - used : 0; + unsigned int headroom_pct =3D used ? (free_slabs * 100) / used : 0; + + pr_info("lockdep: shutdown summary : %u/%u slabs (%u kB/%u kB, %u%% headr= oom left), %lu classes, %lu chains, %u hlocks\n", + used, total, + (used * LOCKDEP_SLAB_SIZE) / 1024, + (total * LOCKDEP_SLAB_SIZE) / 1024, + headroom_pct, + nr_lock_classes, lock_chain_count(), chain_hlocks_used()); + + return NOTIFY_OK; +} + +static struct notifier_block lockdep_reboot_nb =3D { + .notifier_call =3D lockdep_shutdown_notify, +}; + +static int __init lockdep_post_init_trim(void) +{ + unsigned int used =3D lockdep_slabs_used - lockdep_nr_free_slabs; + unsigned int initial_slabs =3D lockdep_nr_slabs; + unsigned int target_slabs, kept_headroom_slabs; + unsigned int freed_slabs =3D 0; + unsigned int i; + + if (!lockdep_nr_slabs) + return 0; + + /* Compute headroom requirement (default 100% or custom percentage) with = 32-slab floor */ + kept_headroom_slabs =3D DIV_ROUND_UP(used * requested_lockdep_headroom_pc= t, 100); + if (kept_headroom_slabs < 32) + kept_headroom_slabs =3D 32; + + target_slabs =3D used + kept_headroom_slabs; + + /* Satisfy both: target_slabs >=3D requested_lockdep_slabs AND headroom >= =3D M% */ + if (requested_lockdep_slabs > target_slabs) + target_slabs =3D requested_lockdep_slabs; + + target_slabs =3D clamp_t(unsigned int, target_slabs, used, lockdep_nr_sla= bs); + + /* Release excess slabs to buddy allocator */ + if (target_slabs < lockdep_nr_slabs) { + for (i =3D target_slabs; i < lockdep_nr_slabs; i++) { + struct page *page =3D virt_to_page(lockdep_slabs[i]); + unsigned long p; + + for (p =3D 0; p < (LOCKDEP_SLAB_SIZE >> PAGE_SHIFT); p++) + free_reserved_page(page + p); + + lockdep_slabs[i] =3D NULL; + } + freed_slabs =3D lockdep_nr_slabs - target_slabs; + lockdep_nr_slabs =3D target_slabs; + } + + pr_info("lockdep: boot complete : %u/%u slabs used, %u kept (%u%% headroo= m), %u returned to buddy (%u kB freed)\n", + used, initial_slabs, lockdep_nr_slabs, + lockdep_nr_slabs > used ? ((lockdep_nr_slabs - used) * 100) / used : 0, + freed_slabs, (freed_slabs * LOCKDEP_SLAB_SIZE) / 1024); + + register_reboot_notifier(&lockdep_reboot_nb); + return 0; +} +late_initcall_sync(lockdep_post_init_trim); + static void print_freed_lock_bug(struct task_struct *curr, const void *mem_from, const void *mem_to, struct held_lock *hlock) diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c index 1916db9aa46b..95b76047918d 100644 --- a/kernel/locking/lockdep_proc.c +++ b/kernel/locking/lockdep_proc.c @@ -32,16 +32,17 @@ * bitmap and max_lock_class_idx. */ #define iterate_lock_classes(idx, class) \ - for (idx =3D 0, class =3D lock_classes; idx <=3D max_lock_class_idx; \ - idx++, class++) + for (idx =3D 0, class =3D idx_to_lock_class(0); \ + idx <=3D max_lock_class_idx; \ + idx++, class =3D idx_to_lock_class(idx)) =20 static void *l_next(struct seq_file *m, void *v, loff_t *pos) { - struct lock_class *class =3D v; + unsigned long idx =3D ++*pos; =20 - ++class; - *pos =3D class - lock_classes; - return (*pos > max_lock_class_idx) ? NULL : class; + if (idx > max_lock_class_idx) + return NULL; + return idx_to_lock_class(idx); } =20 static void *l_start(struct seq_file *m, loff_t *pos) @@ -50,7 +51,7 @@ static void *l_start(struct seq_file *m, loff_t *pos) =20 if (idx > max_lock_class_idx) return NULL; - return lock_classes + idx; + return idx_to_lock_class(idx); } =20 static void l_stop(struct seq_file *m, void *v) @@ -59,7 +60,7 @@ static void l_stop(struct seq_file *m, void *v) =20 static void print_name(struct seq_file *m, struct lock_class *class) { - char str[KSYM_NAME_LEN]; + char str[128]; const char *name =3D class->name; =20 if (!name) { @@ -79,9 +80,9 @@ static int l_show(struct seq_file *m, void *v) struct lock_class *class =3D v; struct lock_list *entry; char usage[LOCK_USAGE_CHARS]; - int idx =3D class - lock_classes; + int idx =3D class->class_idx; =20 - if (v =3D=3D lock_classes) + if (idx =3D=3D 0) seq_printf(m, "all lock classes:\n"); =20 if (!test_bit(idx, lock_classes_in_use)) @@ -133,7 +134,7 @@ static void *lc_start(struct seq_file *m, loff_t *pos) if (*pos =3D=3D 0) return SEQ_START_TOKEN; =20 - return lock_chains + (*pos - 1); + return idx_to_lock_chain(*pos - 1); } =20 static void *lc_next(struct seq_file *m, void *v, loff_t *pos) --=20 2.55.0 From nobody Mon Sep 28 03:41:50 2026 Received: from mail-oa1-f47.google.com (mail-oa1-f47.google.com [209.85.160.47]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1AC7C38F935 for ; Thu, 27 Aug 2026 03:58:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.47 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803131; cv=none; b=i8dqN7D0JjGWjklbt5Zz7ysqZE+DiGmx12vTLQFgQxfEekvZNMWbZ4+Hu9RbAM7zTzlY/g+RHt/0VJqRR0SQZo+6gBG2BFOTDFCq11hsUfifiFZ7NVWAFRKzxFImNWFw9u8LhMfAcHxJqmudr9kSrKT/EUNWK+bAqf6Cn2sSPW4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803131; c=relaxed/simple; bh=kqAGrQKBnvnPgOUp0Is/BsYIX2enC25F2BBLntksDdM=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=V2ToV1CVYtOTJmATwRVNiZpL/nthxZgQOpJoKpEEZvrN2oDNe3aoXlaVLxZ5tg0tLyLUF6nCScOrDGL49rbbMHAFqpwIcURHrnCBoHgEJi23UjKSUzZXTDPjmBcU3PnksuFBAsnjQEwJTIFS5H/gMoZCDoH+F5EJQUM9H34Nngw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=J+UJI7Gt; arc=none smtp.client-ip=209.85.160.47 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="J+UJI7Gt" Received: by mail-oa1-f47.google.com with SMTP id 586e51a60fabf-459281bc13bso1608746fac.2 for ; Wed, 26 Aug 2026 20:58:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1787803129; x=1788407929; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=mZxMQK5WtsXLFwQrtkbnqWWj54ZVBmL2OgaA3/jRW4s=; b=J+UJI7GtsUnE4UAjjCj4A+YUDvrw9ECyndehe8/209qhTS0NvXuwTS40vEhPrifsde N84eaCSmVIMpwx1eVXeKM/cm827RLgvQ8GF9ZFCuiILDNh7OQtiXFlLRMOa9cLWUy/EO gzu9iPPLcv+ZMJdqsbEVQsAyr+qASsHkb9G9QXJGJcc6g35GcCiuXY7zVcp6mRo7+dOI oqgCQbJt0fItEUOtNZOL4YIe8fkpPFONMyykeVDjdy9xry6lrD/UBudgxqFFS6woG/9j 9YluZ2wwqAEllTFx10JPmolhCsSffQw15I9+KJHr+DibO1oxB8mQx3ILF0f65Q4DOzm8 eXfA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1787803129; x=1788407929; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=mZxMQK5WtsXLFwQrtkbnqWWj54ZVBmL2OgaA3/jRW4s=; b=nTxJC7ZpJ1lj8laPXLsxWzHCVOJl9L+Uw1tnjYJygamnCtmRiLGs2f6tj0CTc/vab9 OmQqRepFhHvYRQWv3mURlxZOzcwHoi4fiYUbK/iqixMN3ZkQ4KXpmJXqWx38oTN5PiYN jUpGCXBLglZ/q7i3v/1zztnuPxslVzEogrRoNaJ3gQVDBnsKM4PoIcw2CHT2rXSwnCHa 4Tl2spqjf8UUIOVKlKdV+gWJ14/VCczxsZOtFIoHSEGACFwGkXUNytwJPE859cDKijXa 7p6gxz8MEcPD7UiB3vCUq3C89vT4X0QW5bKnPEy93sI8UB62+qQGzxARsm0BnDYs8up2 G1Vg== X-Gm-Message-State: AFuF++khQu57JmA8Kgh2ZugzBcwwVpwmE3EZE1/pLOFnC0QPJM5OhUPH onIJ5keIJ80DZiqCQjOxhFP8Yfd9haB5uYhw4eJyO1N29OjabyhNcZRZfqOZhA53 X-Gm-Gg: AR+sD13XXCm8X/HlQXQuRn2ftT5B+Xxrm/dFJov+DfZmGyANiom5XdZP+rB69jOqB5E 9JFTRF0E1SryrLejxO+vHn98EdawzgT/m/uH31pZGf0wt1JqBcD7Nadw0SJ8g0t8zrY86aBimLX bCoEfxhxs7+YiakEW+XHDjMGRnnbxpKGe5xkSkYPMShSMzECP+B2L1bhcAUy8p8DrdkqHaWdImN N9ejIT52pkownlL8jAr/aL+yAEQiiVDSvH3Rfetyk1RX13TmHwoZ+EmxkAXnthXVhP6E1QvCcXh BB0edfsVhwtimES+aPh/GguFbpEeS3Eb6sCtuMK8VWyUkkkVIY11cQJyg9nHT5VMzDVvFDchaM8 YpSO1W+2VOseCslBxZJzZIIuL1sAbCJgO0QNvWVtUVxItxOkp4mP7jL47vbamXohrmCNU+Xy7Pb Yj7w8g3QGANn23n5t5N/6hBrVYLTyVIqCrB2XItEj5sHnrBNU5bJP2YjBkUjwpd49bn0ItVJLiB Bo3dYfAXIwn3+wvWmrx75/YINSD0WnAjfyxf+y9ylV6I/8A/Z5gEiqnq0S8VD2H37LKn1nkp6dv x6EFvRjq X-Received: by 2002:a05:6870:fb9f:b0:448:9d5b:6393 with SMTP id 586e51a60fabf-46599f6067dmr13214306fac.14.1787803128910; Wed, 26 Aug 2026 20:58:48 -0700 (PDT) Received: from [192.168.0.245] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-467367af2bfsm900825fac.6.2026.08.26.20.58.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Aug 2026 20:58:48 -0700 (PDT) From: Jim Cromie Date: Wed, 26 Aug 2026 21:58:39 -0600 Subject: [PATCH 7/8] lockdep: Expose slab pool telemetry in /proc/lockdep_stats and initcalls Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260826-lockdep-memblock-v1-v1-7-e2db855391ec@gmail.com> References: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> In-Reply-To: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> To: Peter Zijlstra , Ingo Molnar , Will Deacon , Boqun Feng , Waiman Long Cc: linux-kernel@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1787803120; l=6448; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=kqAGrQKBnvnPgOUp0Is/BsYIX2enC25F2BBLntksDdM=; b=uZ7Wd4Ljf/hajAN/9LfeUHolQFsjSym1A2G7yUaBESqdf1Nk/KyZ1IOyQ1xCbiOic1T7KNxRT VZARg1PyRvqDcUhCkOrFsgt+JIEwGWPdisQ8y0WJHs77+lp6PcZmx2d X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= Extend lockdep observability to track slab allocation dynamics: 0. In /proc/lockdep_stats, display total reserved slabs, used slabs, free slabs (headroom), and a per-consumer slab breakdown (lock_classes, direct deps, dependency chains, chain hlocks, stack traces). 1. In lockdep.c, add lockdep_report_stage() hooks registered across initcall milestones (core, postcore, arch, subsys, fs, device, late) to log slab consumption progress throughout kernel initialization. Signed-off-by: Jim Cromie --- kernel/locking/lockdep.c | 47 ++++++++++++++++++++++++++++++++++= ++++ kernel/locking/lockdep_internals.h | 4 +++- kernel/locking/lockdep_proc.c | 40 ++++++++++++++++++++++++-------- 3 files changed, 80 insertions(+), 11 deletions(-) diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 3fb6c07cea36..b6048e7c8b56 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -6992,6 +6992,53 @@ void __init lockdep_init(void) sizeof(((struct task_struct *)NULL)->held_locks)); } =20 +static void lockdep_report_stage(const char *domain, const char *stage_nam= e) +{ + unsigned int used =3D lockdep_slabs_used - lockdep_nr_free_slabs; + unsigned int class_per_chunk =3D lock_class_PER_CHUNK; + unsigned int entry_per_chunk =3D LOCKDEP_SLAB_SIZE / sizeof(struct lock_l= ist); + unsigned int chain_per_chunk =3D lock_chain_PER_CHUNK; + unsigned int hlock_per_chunk =3D chain_hlock_PER_CHUNK; + unsigned int trace_per_chunk =3D LOCKDEP_SLAB_SIZE / sizeof(unsigned long= ); + + unsigned int cl_w =3D nr_lock_classes / class_per_chunk; + unsigned int cl_f =3D ((nr_lock_classes % class_per_chunk) * 100) / class= _per_chunk; + + unsigned int en_w =3D nr_list_entries / entry_per_chunk; + unsigned int en_f =3D ((nr_list_entries % entry_per_chunk) * 100) / entry= _per_chunk; + + unsigned long chains =3D lock_chain_count(); + unsigned int ch_w =3D chains / chain_per_chunk; + unsigned int ch_f =3D ((chains % chain_per_chunk) * 100) / chain_per_chun= k; + + unsigned int hlocks =3D chain_hlocks_used(); + unsigned int hl_w =3D hlocks / hlock_per_chunk; + unsigned int hl_f =3D ((hlocks % hlock_per_chunk) * 100) / hlock_per_chun= k; + + unsigned int tr_w =3D nr_stack_trace_entries / trace_per_chunk; + unsigned int tr_f =3D ((nr_stack_trace_entries % trace_per_chunk) * 100) = / trace_per_chunk; + + pr_info("lockdep: %-8s [%-9s] : %u/%u slabs : classes=3D%u.%02u entries= =3D%u.%02u chains=3D%u.%02u hlocks=3D%u.%02u trace=3D%u.%02u\n", + domain, stage_name, used, lockdep_nr_slabs, + cl_w, cl_f, en_w, en_f, ch_w, ch_f, hl_w, hl_f, tr_w, tr_f); +} + +#define DEFINE_LOCKDEP_LEVEL_REPORT(lvl, name) \ + static int __init lockdep_report_##name(void) \ + { \ + lockdep_report_stage("initcall", #name); \ + return 0; \ + } \ + lvl(lockdep_report_##name) + +DEFINE_LOCKDEP_LEVEL_REPORT(core_initcall_sync, core); +DEFINE_LOCKDEP_LEVEL_REPORT(postcore_initcall_sync, postcore); +DEFINE_LOCKDEP_LEVEL_REPORT(arch_initcall_sync, arch); +DEFINE_LOCKDEP_LEVEL_REPORT(subsys_initcall_sync, subsys); +DEFINE_LOCKDEP_LEVEL_REPORT(fs_initcall_sync, fs); +DEFINE_LOCKDEP_LEVEL_REPORT(device_initcall_sync, device); +DEFINE_LOCKDEP_LEVEL_REPORT(late_initcall_sync, late); + static int lockdep_shutdown_notify(struct notifier_block *nb, unsigned long code, void *unused) { diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_in= ternals.h index ccd7343af672..6fb776618ac6 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -223,7 +223,7 @@ extern unsigned int max_lockdep_depth; extern unsigned int max_bfs_queue_depth; extern unsigned long max_lock_class_idx; =20 -DECLARE_2D_RADIX(lock_class, struct lock_class); +DECLARE_CHUNKED_ARRAY(lock_class, struct lock_class); extern unsigned long lock_classes_in_use[]; =20 struct lockdep_slab_usage { @@ -240,6 +240,8 @@ struct lockdep_slab_stats { struct lockdep_slab_usage usage; }; =20 +void lockdep_get_slab_stats(struct lockdep_slab_stats *st); + unsigned int chain_hlocks_used(void); unsigned long lock_chain_count(void); void lockdep_get_slab_stats(struct lockdep_slab_stats *st); diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c index 95b76047918d..76e32fca8c54 100644 --- a/kernel/locking/lockdep_proc.c +++ b/kernel/locking/lockdep_proc.c @@ -380,17 +380,37 @@ static int lockdep_stats_show(struct seq_file *m, voi= d *v) debug_locks); =20 /* - * Zapped classes and lockdep data buffers reuse statistics. + * Shared Memblock Slab Reservoir Statistics */ - seq_puts(m, "\n"); - seq_printf(m, " zapped classes: %11lu\n", - nr_zapped_classes); -#ifdef CONFIG_PROVE_LOCKING - seq_printf(m, " zapped lock chains: %11lu\n", - nr_zapped_lock_chains); - seq_printf(m, " large chain blocks: %11u\n", - nr_large_chain_blocks); -#endif + { + struct lockdep_slab_stats st; + + lockdep_get_slab_stats(&st); + if (st.total_slabs) { + unsigned int free_slabs =3D st.total_slabs > st.used_slabs ? + st.total_slabs - st.used_slabs : 0; + unsigned int headroom_pct =3D (free_slabs * 100) / st.total_slabs; + + seq_puts(m, "\n lockdep memblock slab reservoir:\n"); + seq_printf(m, " total slabs: %11u (%zu kB)\n", + st.total_slabs, (size_t)st.total_slabs * 64); + seq_printf(m, " used slabs: %11u (%zu kB)\n", + st.used_slabs, (size_t)st.used_slabs * 64); + seq_printf(m, " - lock_classes slabs: %11u (%zu kB)\n", + st.usage.lock_classes, (size_t)st.usage.lock_classes * 64); + seq_printf(m, " - direct deps slabs: %11u (%zu kB)\n", + st.usage.direct_deps, (size_t)st.usage.direct_deps * 64); + seq_printf(m, " - dependency chains slabs: %11u (%zu kB)\n", + st.usage.lock_chains, (size_t)st.usage.lock_chains * 64); + seq_printf(m, " - chain hlocks slabs: %11u (%zu kB)\n", + st.usage.chain_hlocks, (size_t)st.usage.chain_hlocks * 64); + seq_printf(m, " - stack_trace slabs: %11u (%zu kB)\n", + st.usage.stack_traces, (size_t)st.usage.stack_traces * 64); + seq_printf(m, " free slabs (headroom): %11u (%zu kB, %u%%)\n", + free_slabs, (size_t)free_slabs * 64, headroom_pct); + } + } + return 0; } =20 --=20 2.55.0 From nobody Mon Sep 28 03:41:50 2026 Received: from mail-oa1-f42.google.com (mail-oa1-f42.google.com [209.85.160.42]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 44BFA390219 for ; Thu, 27 Aug 2026 03:58:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.42 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803137; cv=none; b=m4szEiu6p4xhAuYabOurR2MWn/UJQlW39MXNzswA+pmygk4r/lEVx1ugo5AJfQYeM8vxOkibuPDCoruoyRUOYPB0r6rMeBM8ZixsO8ckzX8fN5SkMFSRdGa0iZ0Tl0dtVuOxHmerM2+sLte71vH3ab0hBTufIGSmdY5YiIsxWP8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787803137; c=relaxed/simple; bh=5rx5ERvKixj7FGUQj37v/bHFSs/DaokMES+BAqJO8D0=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=Kn3zeDhzBlVrPrKclWezXBOQYdxoA8baLCFCcUJc+Woeai5kuBOQZyvUoAJG+Iu0njxFfaJq0ROLBX0RNldROOOIHpoYGIG6417Dn/krE51mJLsg3eN8sZrSNnZIoVs80WYKQKoLiy7FEQBmzJDiULMtO4WPPKEwjblsolX3GIw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=BZTPaNqN; arc=none smtp.client-ip=209.85.160.42 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="BZTPaNqN" Received: by mail-oa1-f42.google.com with SMTP id 586e51a60fabf-45e6d266921so140827fac.2 for ; Wed, 26 Aug 2026 20:58:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1787803130; x=1788407930; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=gcJXoO2PZbvQNti1IoEfyjxaC4/aOEYoKd3T652pnHU=; b=BZTPaNqN3UZfv6HK7BgxTF2i9YM4J8iPlf2rVfnH9kLtO2jFGamMOYkSdBaeFFQ6jV BrR3HRqzKGAUGUsta5GlwnlEO3iroVlKBOPYhOGKoJaoArVT+A51Y40jSq/uoYoQo58n y/7DiAGYeagcujx72Tut8mDv0+7fEQ8pYS07rr7dWcMfvDuW+nDcWjOpA/cPTSxkhdsB ejQYjIV4BONfpYCsqRdZ3l0NLvLf9zr07VeEY1IZYbQTVCMIppMmygMp3XWDYxq+Jw0k x+fUADtmFgN+WfvznkCDfo5KfXjCNbJ82AmGcfdVDNfNNW0QsvfFiEaJykTa5/+oer95 fqJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1787803130; x=1788407930; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=gcJXoO2PZbvQNti1IoEfyjxaC4/aOEYoKd3T652pnHU=; b=Nj8gaUNfjGdsMqN9kqAVkUP+Mj60p/bm6klDdWQk4wxfkwE+BOks8hyT5pG140tq+c 1PONBuvPAqeJTSkyZQYcaRtvMvNPfE3nd7ZuoqOrZzDy2Hdg9j7oJvP2nXzpIFbIQlr5 WGlpBo2qMiaUKU/teeW/7gjdpnw0sGwsSn6uIGdwdoJgxOZwDiHaPD/Oo+THwyuDRbmO CGlFoEfp+4Ln7mVCXBgJgH/UmWoH96jRi4MVfhFPw1zB10j7U313tDPThbmJ4/cLLV3Y LrkkWNINvbEkRElv9NZLU6xIDDu6CisXK2pvMhUrSh7Ko5vza65kMbhmtuvnAE1uMmDR hyGQ== X-Gm-Message-State: AFuF++l2XQjdUJFSV/ERiLPV4UFRvpe/E/Cuz8oHWknBS2Ipj+MF3M/v IyVZEzKuz0Aywt0iV1517RugdU9BjQasdmpwDoLg9+vpING4DKSoE3YU X-Gm-Gg: AR+sD11Rfd9HP7Hsbq2MXz6nm0FxhBsmjrLPMbEm7zIUVnmKS9vUARSygANPhm/nf/S Qh6lYBm+aiHUaTeX4NATegUmpmdKtFG2VZ+2BbFsyHMo+C/9+h/1pijdcPcQ/W2UST3mXUAoB1U 842WUzOKTcWU7yUsMFFYBvqzrU8p9T1Q3K/H9pDuqPYsa4ijxQdr+Gc6r2vnbW6S0Fc3/2c0NB2 FpQJz5Db75d++ksO2jKpFb/0GmeKqAGqpUaWf/w+0owwEIjUidaEG+5qlaH5r7W4C5MD1w4D07y 0H3sW/fjAwrDpePJiYZddCHaa3Qmc/+er+uHu9HKW4hE2Fa/jBzcva4Crgt/4PRMTbUtOgn/UCG lyzG5boE8K22dmraxioV2/vglFjpJVJYD++217/iTcpEA410vOWFVCNTb6M6/zwZu2hk+l5yZg+ vQpexxRwJw1JIfhc+1/uDGVOV4CfWz9SnXxbJtiQSQ9onJsD7DRV6XYk0YIfnJr1ujx+uOzEqfU ArNO9AEsI9mYT7CfieZa48aw3teR4Aou1tCsbXqtxWL+knHxUe/A5z6trRx2Ayf4o5dwFS5Pl6p wDofmgan X-Received: by 2002:a05:6870:fb8e:b0:464:f373:b579 with SMTP id 586e51a60fabf-46594ee315bmr13253951fac.0.1787803130005; Wed, 26 Aug 2026 20:58:50 -0700 (PDT) Received: from [192.168.0.245] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-467367af2bfsm900825fac.6.2026.08.26.20.58.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Aug 2026 20:58:49 -0700 (PDT) From: Jim Cromie Date: Wed, 26 Aug 2026 21:58:40 -0600 Subject: [PATCH 8/8] lockdep: on debug_locks_off or OOM, recycle all slabs to buddy Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260826-lockdep-memblock-v1-v1-8-e2db855391ec@gmail.com> References: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> In-Reply-To: <20260826-lockdep-memblock-v1-v1-0-e2db855391ec@gmail.com> To: Peter Zijlstra , Ingo Molnar , Will Deacon , Boqun Feng , Waiman Long Cc: linux-kernel@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1787803120; l=4293; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=5rx5ERvKixj7FGUQj37v/bHFSs/DaokMES+BAqJO8D0=; b=h4GLEdvX2vSDycelajSVWzrtr4X5YrylJFcbesojZF33QpWgLG6zxjve68ZDwetZGiBBE7QUc hbDCfRUijcbD5+YvKdREkfLskWN6G5wNNvsipXin5pWF2227TbskGO4 X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= If lockdep breaks, by assertion failure or for ENOMEM-ish reasons, we can no longer use the graph-db. Since most of the graph-db is now allocated from memblock_alloc() slabs, we can release them all back to buddy, and hope that freeing ~1.5MB will help. (v7.2 has ~10MB tied up in .bss). 0. Hook debug_locks_off() / print_lockdep_off() via an asynchronous work item (lockdep_sacrifice_work) to release all held slabs back to the buddy allocator via free_reserved_page() in process context. 1. Register an OOM notifier (lockdep_oom_nb) at late_initcall. If the system encounters an out-of-memory emergency, lockdep sacrifices its entire dynamic slab pool (1..8 MB of physical RAM), reporting freed pages to the OOM killer to avoid terminating user processes. 2. Clear lockdep_slabs[] pointers and zero lockdep_nr_slabs under graph_lock to seal off subsequent allocations. Signed-off-by: Jim Cromie --- kernel/locking/lockdep.c | 81 ++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 81 insertions(+) diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index b6048e7c8b56..9f28530b2f1d 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -60,7 +60,9 @@ #include #include #include +#include #include +#include =20 #include =20 @@ -638,6 +640,82 @@ static int verbose(struct lock_class *class) return 0; } =20 +/* + * Release all memblock slabs (used and unused) back to the buddy allocator + * when lockdep is disabled or during system OOM emergencies. + * Must run in process context (workqueue or OOM notifier). + */ +static unsigned int lockdep_release_slabs_to_buddy(void) +{ + unsigned int freed_slabs =3D 0; + unsigned int nr =3D lockdep_nr_slabs; + unsigned long flags; + unsigned int i; + + if (!nr) + return 0; + + /* Invalidate table bounds under graph_lock */ + raw_local_irq_save(flags); + if (!graph_lock()) { + raw_local_irq_restore(flags); + return 0; + } + lockdep_nr_slabs =3D 0; + lockdep_slabs_used =3D 0; + graph_unlock(); + raw_local_irq_restore(flags); + + for (i =3D 0; i < nr; i++) { + struct page *page; + unsigned long p; + + if (!lockdep_slabs[i]) + continue; + + page =3D virt_to_page(lockdep_slabs[i]); + for (p =3D 0; p < (LOCKDEP_SLAB_SIZE >> PAGE_SHIFT); p++) + free_reserved_page(page + p); + + lockdep_slabs[i] =3D NULL; + freed_slabs++; + } + + if (freed_slabs) + pr_info("lockdep: emergency sacrifice =E2=80=94 released %u slabs (%u kB= ) to buddy allocator\n", + freed_slabs, (freed_slabs * LOCKDEP_SLAB_SIZE) / 1024); + + return freed_slabs; +} + +static void lockdep_sacrifice_work_fn(struct work_struct *work) +{ + lockdep_release_slabs_to_buddy(); +} +static DECLARE_WORK(lockdep_sacrifice_work, lockdep_sacrifice_work_fn); + +static int lockdep_oom_notify(struct notifier_block *self, + unsigned long dummy, void *parm) +{ + unsigned long *freed =3D parm; + unsigned int freed_slabs; + + if (!lockdep_nr_slabs) + return NOTIFY_OK; + + /* Turn off lockdep before sacrificing tables */ + debug_locks_off(); + freed_slabs =3D lockdep_release_slabs_to_buddy(); + if (freed && freed_slabs) + *freed +=3D (freed_slabs * (LOCKDEP_SLAB_SIZE >> PAGE_SHIFT)); + + return NOTIFY_OK; +} + +static struct notifier_block lockdep_oom_nb =3D { + .notifier_call =3D lockdep_oom_notify, +}; + static void print_lockdep_off(const char *bug_msg) { printk(KERN_DEBUG "%s\n", bug_msg); @@ -645,6 +723,8 @@ static void print_lockdep_off(const char *bug_msg) #ifdef CONFIG_LOCK_STAT printk(KERN_DEBUG "Please attach the output of /proc/lock_stat to the bug= report\n"); #endif + if (system_state >=3D SYSTEM_RUNNING) + schedule_work(&lockdep_sacrifice_work); } =20 unsigned long nr_stack_trace_entries; @@ -7105,6 +7185,7 @@ static int __init lockdep_post_init_trim(void) lockdep_nr_slabs > used ? ((lockdep_nr_slabs - used) * 100) / used : 0, freed_slabs, (freed_slabs * LOCKDEP_SLAB_SIZE) / 1024); =20 + register_oom_notifier(&lockdep_oom_nb); register_reboot_notifier(&lockdep_reboot_nb); return 0; } --=20 2.55.0