Skip to contentSkip to conversation

mm: dual-bitmap page allocator consistency checker

RFC In review Sasha Levin 5 participants 29 messages Apr 24 – Apr 28

Subsystems (6)
lore
Share & tools
lore
#0 lore raw

cover mm: dual-bitmap page allocator consistency checker

Existing memory debugging tools - KASAN, KFENCE, page_poisoning - detect access violations and content corruption, but none of them can detect silent corruption in the page allocator's own metadata. If a hardware bit flip corrupts an allocation bitmap, the allocator hands out a page that is already in use (or fails to hand out a free one), and nothing in the kernel notices. This series adds a dual-bitmap consistency checker that maintains the invariant primary == ~secondary across two independently allocated bitmaps, so that any single-bit corruption in either bitmap is immediately detectable. The approach is based on NVIDIA safety research.

Field studies consistently show that DRAM errors at scale are far more common than textbook assumptions suggest, even with ECC. Schroeder et al. (SIGMETRICS 2009) found 8% of DIMMs experienced errors per year in Google's fleet; Sridharan and Liberty (SC 2012) reported similar rates at LANL; Meta's 2021-2022 work documented silent data corruption at scale, including memory-related faults. The critical property of allocator metadata corruption is that it doesn't trigger an invalid memory access - the corrupted data is structurally valid, just wrong. KASAN instruments accesses, not metadata integrity, so it cannot see this class of fault.

Functional safety is a different discipline from security that aims to reduce the risk of hardware and software misbehaving to an acceptable level. Security hardens against adversaries; safety hardens against random hardware failures (cosmic rays, cell wear-out, thermal noise) and systematic software failures (bugs). ISO 26262 (automotive functional safety) defines four Automotive Safety Integrity Levels, ASIL A through D. ASIL-D, the most stringent, is derived from the severity of the hazard in case of failure. IEC 61508 defines similar levels (SIL-1 through SIL-4) for industrial systems, and there are equivalent standards for avionics and medical devices. ISO 26262 requires Freedom From Interference (FFI): a safety element must not be corrupted by faults in other elements. For an OS kernel, this means the memory allocator's metadata must either be immune to corruption or corruption must be detected before it propagates. The dual-bitmap implements a way to protect from corruption coming from hardware or software - two complementary representations of page allocation state, allocated independently via memblock, where any single-bit fault in either bitmap is immediately detectable. Performance is secondary to correctness in this context. A safety mechanism must be simple enough to audit and certify, must fail deterministically (panic, not log-and-hope), and its correctness matters more than its throughput. The dual-bitmap adds two atomic bitops per alloc/free, but for safety-critical deployments this cost is acceptable because the alternative - undetected corruption propagating silently - violates the system's safety case. The static key ensures zero cost for kernels that don't need it.

The natural question is why not use page_ext. The key objection from a safety perspective is that page_ext stores per-page metadata in memory that is itself subject to the same hardware faults we're trying to detect. The dual-bitmap approach works because the two bitmaps are independent allocations - corruption in one is caught by comparison with the other. Embedding both in page_ext means a single fault could corrupt both the tracking data and its redundant copy in the same allocation region. ISO 26262 recommends this approach for protecting against hardware faults, but it also helps against software faults - co-locating both bitmaps in page_ext violates this principle. Beyond the safety argument, there are practical issues: page_ext adds 8-100+ bytes per page depending on enabled features while the dual-bitmap uses 2 bits per page total, and page_ext initializes after the buddy allocator while the checker must be active before memblock_free_all() hands pages to buddy.

Sasha Levin (7):
mm: add generic dual-bitmap consistency primitives
mm: add page consistency checker header
mm: add Kconfig options for page consistency checker
mm: add page consistency checker implementation mm/page_alloc: integrate page consistency hooks Documentation/mm: add page consistency checker documentation mm/page_consistency: add KUnit tests for dual-bitmap primitives

 Documentation/mm/index.rst            |   1 +
 Documentation/mm/page_consistency.rst | 211 +++++++++++++++
 MAINTAINERS                           |  10 +
 include/linux/dual_bitmap.h           | 216 ++++++++++++++++
 include/linux/page_consistency.h      |  84 ++++++
 mm/Kconfig.debug                      |  59 +++++
 mm/Makefile                           |   2 +
 mm/mm_init.c                          |   9 +
 mm/page_alloc.c                       |   4 +
 mm/page_consistency.c                 | 360 ++++++++++++++++++++++++++
 mm/page_consistency_test.c            | 274 ++++++++++++++++++++
 11 files changed, 1230 insertions(+)
 create mode 100644 Documentation/mm/page_consistency.rst
 create mode 100644 include/linux/dual_bitmap.h
 create mode 100644 include/linux/page_consistency.h
 create mode 100644 mm/page_consistency.c
 create mode 100644 mm/page_consistency_test.c
Signature · 1 line
2.53.0
#1 lore raw

RFC 1/7 mm: add generic dual-bitmap consistency primitives

From: Sasha Levin <[email protected]>

Add a header-only library implementing a pair-of-complementary-bitmaps integrity primitive: maintain two bitmaps where primary[i] == !secondary[i] for every bit i, and detect corruption by checking that invariant.

The motivation (silent metadata corruption that KASAN/KFENCE cannot see, plus the functional-safety argument for wanting this in the kernel) is described in the cover letter; this patch only introduces the building block.

The primary bitmap uses 1 for "allocated" and 0 for "free"; the secondary uses the opposite convention. dual_bitmap_set() and dual_bitmap_clear() update both bitmaps and return the previous primary bit so callers can distinguish a real state transition from a double-alloc or double-free. dual_bitmap_validate() walks every word and returns the number of words that fail the invariant.

Concurrency note: set and clear perform two independent atomic bit operations against the primary and secondary bitmaps, so the invariant is transiently violated between those two ops. A concurrent reader can observe an inconsistent pair on a healthy kernel. The validation helpers absorb this by retrying a small number of times with cpu_relax() and, after the retries, issuing an smp_rmb() and re-reading. Real corruption is persistent and survives the retries; transient races resolve within a few cpu_relax() loops. This keeps the update path lock-free at the cost of a bounded false-positive probability under extreme write rates, which is acceptable for a fail-stop integrity check.

Assisted-by Claude:claude-opus-4-7 <[email protected]>
---
 MAINTAINERS                 |  10 ++
 include/linux/dual_bitmap.h | 216 ++++++++++++++++++++++++++++++++++++
 2 files changed, 226 insertions(+)
 create mode 100644 include/linux/dual_bitmap.h
MAINTAINERS +10 -0
index d1cc0e12fe1f..81b1f44215b3 100644
@@ -19972,6 +19972,16 @@ F:	mm/page-writeback.c
 F:	mm/readahead.c
 F:	mm/truncate.c
 
+PAGE CONSISTENCY CHECKER
+M:	Sasha Levin <[email protected]>
+L:	[email protected]
+S:	Maintained
+F:	Documentation/mm/page_consistency.rst
+F:	include/linux/dual_bitmap.h
+F:	include/linux/page_consistency.h
+F:	mm/page_consistency.c
+F:	mm/page_consistency_test.c
+
 PAGE POOL
 M:	Jesper Dangaard Brouer <[email protected]>
 M:	Ilias Apalodimas <[email protected]>
include/linux/dual_bitmap.h new file +216 -0

216 lines not on this page · raw message

Signature · 1 line
2.53.0
#2 lore raw

RFC 2/7 mm: add page consistency checker header

In reply to Sasha Levin

From: Sasha Levin <[email protected]>

Define the interface for CONFIG_DEBUG_PAGE_CONSISTENCY. The API mirrors the pattern used by page_table_check: inline wrapper functions check a static key before calling the out-of-line tracking implementation, so that callers in the allocator hot path only pay for a predicted-not-taken branch when the feature is built in but not active.

The header is kept separate from the implementation so the hooks in page_alloc.c can be added without pulling in implementation details.

Assisted-by Claude:claude-opus-4-7 <[email protected]>
---
 include/linux/page_consistency.h | 84 ++++++++++++++++++++++++++++++++
 1 file changed, 84 insertions(+)
 create mode 100644 include/linux/page_consistency.h
include/linux/page_consistency.h new file +84 -0
new file mode 100644
index 000000000000..f335fa3d6c5d
@@ -0,0 +1,84 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Dual-bitmap page consistency checking
+ *
+ * Provides corruption detection for page allocations using complementary
+ * bitmaps where the invariant (primary == ~secondary) must hold.
+ *
+ * Based on NVIDIA safety research.
+ */
+#ifndef _LINUX_PAGE_CONSISTENCY_H
+#define _LINUX_PAGE_CONSISTENCY_H
+
+#include <linux/types.h>
+#include <linux/mm_types.h>
+
+/* Return codes for page consistency checking */
+enum page_consistency_result {
+	PAGE_CONSISTENCY_OK = 0,
+	PAGE_CONSISTENCY_MISMATCH,
+	PAGE_CONSISTENCY_NOT_TRACKED,
+};
+
+#ifdef CONFIG_DEBUG_PAGE_CONSISTENCY
+
+#include <linux/jump_label.h>
+DECLARE_STATIC_KEY_FALSE(page_consistency_enabled);
+
+/* Initialization - called during mm_core_init() */
+void __init page_consistency_init(void);
+
+/* Core tracking functions */
+void __page_consistency_alloc(struct page *page, unsigned int order);
+void __page_consistency_free(struct page *page, unsigned int order);
+
+/* Validation functions */
+enum page_consistency_result page_consistency_check_page(struct page *page);
+enum page_consistency_result page_consistency_validate_all(void);
+
+/**
+ * page_consistency_alloc - Track page allocation
+ * @page: Allocated page
+ * @order: Allocation order
+ *
+ * Called from post_alloc_hook() to track page allocations.
+ * The static key avoids the out-of-line tracking call until initialization.
+ */
+static inline void page_consistency_alloc(struct page *page, unsigned int order)
+{
+	if (static_branch_unlikely(&page_consistency_enabled))
+		__page_consistency_alloc(page, order);
+}
+
+/**
+ * page_consistency_free - Track page free
+ * @page: Page being freed
+ * @order: Free order
+ *
+ * Called from free_pages_prepare() to track page frees.
+ * The static key avoids the out-of-line tracking call until initialization.
+ */
+static inline void page_consistency_free(struct page *page, unsigned int order)
+{
+	if (static_branch_unlikely(&page_consistency_enabled))
+		__page_consistency_free(page, order);
+}
+
+#else /* !CONFIG_DEBUG_PAGE_CONSISTENCY */
+
+static inline void __init page_consistency_init(void) {}
+static inline void page_consistency_alloc(struct page *page, unsigned int order) {}
+static inline void page_consistency_free(struct page *page, unsigned int order) {}
+
+static inline enum page_consistency_result page_consistency_check_page(struct page *page)
+{
+	return PAGE_CONSISTENCY_OK;
+}
+
+static inline enum page_consistency_result page_consistency_validate_all(void)
+{
+	return PAGE_CONSISTENCY_OK;
+}
+
+#endif /* CONFIG_DEBUG_PAGE_CONSISTENCY */
+#endif /* _LINUX_PAGE_CONSISTENCY_H */
Signature · 1 line
2.53.0
#3 lore raw

RFC 3/7 mm: add Kconfig options for page consistency checker

In reply to Sasha Levin

From: Sasha Levin <[email protected]>

Add two configuration options for the dual-bitmap page consistency checker.

DEBUG_PAGE_CONSISTENCY enables the feature itself. It depends on DEBUG_KERNEL since this is a debugging tool, and selects DEBUG_FS to provide the statistics interface. Memory overhead is two bits per physical page frame across two bitmaps, so about 1 MB for a 16 GB system. The bitmaps are statically sized at boot from memblock, so memory hotplug is not supported and the option depends on !MEMORY_HOTPLUG.

DEBUG_PAGE_CONSISTENCY_PANIC controls the response to a detected violation. When enabled (the default) the kernel panics on double-alloc, double-free, or bitmap corruption; when disabled it logs a warning and continues.

Assisted-by Claude:claude-opus-4-7 <[email protected]>
---
 mm/Kconfig.debug | 59 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)
mm/Kconfig.debug +59 -0
index 7638d75b27db..a005c904677c 100644
@@ -144,6 +144,65 @@ config PAGE_TABLE_CHECK_ENFORCED
 
 	  If unsure say "n".
 
+config DEBUG_PAGE_CONSISTENCY
+	bool "Debug page allocator with dual-bitmap consistency checking"
+	depends on DEBUG_KERNEL
+	depends on !MEMORY_HOTPLUG
+	select DEBUG_FS
+	help
+	  Enable dual-bitmap tracking of page allocations for corruption
+	  detection. Uses two complementary bitmaps where the invariant
+	  (primary == ~secondary) must hold. Any bit flip in either bitmap
+	  will be detected.
+
+	  This is useful for safety-critical systems requiring Freedom From
+	  Interference (FFI) guarantees per ISO 26262 (ASIL-D) and IEC 61508
+	  (SIL-3).
+
+	  When disabled, the hooks compile away. When enabled, a static key
+	  gates tracking until initialization succeeds. The bitmaps are flat,
+	  covering the entire PFN range from memblock_start_of_DRAM() to
+	  memblock_end_of_DRAM() including any holes. This is deliberate:
+	  simple (pfn - min_pfn) indexing is trivially auditable and avoids
+	  auxiliary data structures that could themselves be subject to
+	  corruption. Memory overhead is two bits per PFN in the spanned
+	  range, e.g. ~4 MB total for a 64 GB system. Waste from holes is
+	  typically under 2%.
+
+	  Based on NVIDIA safety research.
+
+	  If unsure, say N.
+
+config DEBUG_PAGE_CONSISTENCY_PANIC
+	bool "Panic on page consistency failure"
+	depends on DEBUG_PAGE_CONSISTENCY
+	default y
+	help
+	  If enabled, the kernel will panic when a page consistency
+	  violation is detected, such as double-alloc or double-free.
+
+	  If disabled, a WARN with a stack trace is emitted and execution
+	  continues.
+
+	  For safety-critical systems, say Y.
+	  For debugging/development, say N.
+
+config DEBUG_PAGE_CONSISTENCY_KUNIT_TEST
+	tristate "KUnit tests for dual-bitmap consistency primitives" if !KUNIT_ALL_TESTS
+	depends on KUNIT
+	default KUNIT_ALL_TESTS
+	help
+	  Enable KUnit tests for the dual-bitmap primitives defined in
+	  <linux/dual_bitmap.h>. These tests verify the core algorithm:
+	  setting and clearing bits in complementary bitmaps, detecting
+	  double-set and double-clear conditions, and detecting simulated
+	  corruption.
+
+	  The tests exercise only the header-only dual_bitmap library and
+	  do not require CONFIG_DEBUG_PAGE_CONSISTENCY.
+
+	  If unsure, say N.
+
 config PAGE_POISONING
 	bool "Poison pages after freeing"
 	help
Signature · 1 line
2.53.0
#4 lore raw

RFC 4/7 mm: add page consistency checker implementation

In reply to Sasha Levin

From: Sasha Levin <[email protected]>

This is the core implementation of the dual-bitmap page allocator consistency checker.

During initialization, two bitmaps are allocated covering the physical memory range reported by memblock. The primary bitmap starts zeroed (all pages free) and the secondary bitmap starts filled with ones (the complement). As pages are allocated and freed, both bitmaps are updated atomically using test_and_set_bit / test_and_clear_bit.

The mark_page_state() helper is the heart of the checker. When allocating, it sets the bit in primary and clears it in secondary. If the primary bit was already set, that indicates a double-alloc and triggers a panic (or warning, depending on config). The free path updates the bitmaps but defers double-free detection until after boot completes, since reserved boot memory pages are legitimately freed via free_reserved_area() and free_initmem() without ever being allocated through the buddy allocator.

mark_page_state() returns whether the bitmap state actually changed, and the pages_tracked counter is only updated for real transitions. This keeps the counter an accurate reflection of the number of bits currently set in the primary bitmap, rather than a signed delta that can go negative during boot because of the reserved-area / initmem frees described above. The same property means post-boot "freeing of untracked pages" (e.g. a driver unloading a region it received via memblock) is detected as a real violation; by construction this code path remains a very small surface.

Initialization validates that the spanned PFN range fits in an unsigned int (bitmap_bytes and the bitmap APIs are bounded by that) and disables the feature if it does not; a zero-span memblock is treated the same way.

A debugfs interface is provided at /sys/kernel/debug/page_consistency/ with two files: "stats" shows counters for allocations, frees, and violations detected, while writing to "validate" triggers a full scan that checks the complement invariant holds for every bitmap word.

The enable check at the debugfs late_initcall uses static_key_enabled() rather than the static_branch_unlikely() hot-path helper, which is the idiomatic form for a cold init path.

Assisted-by Claude:claude-opus-4-7 <[email protected]>
---
 mm/Makefile           |   1 +
 mm/page_consistency.c | 360 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 361 insertions(+)
 create mode 100644 mm/page_consistency.c
mm/Makefile +1 -0
index 8ad2ab08244e..2ee360001456 100644
@@ -128,6 +128,7 @@ obj-$(CONFIG_NUMA_EMU) += numa_emulation.o
 obj-$(CONFIG_BALLOON) += balloon.o
 obj-$(CONFIG_PAGE_EXTENSION) += page_ext.o
 obj-$(CONFIG_PAGE_TABLE_CHECK) += page_table_check.o
+obj-$(CONFIG_DEBUG_PAGE_CONSISTENCY) += page_consistency.o
 obj-$(CONFIG_CMA_DEBUGFS) += cma_debug.o
 obj-$(CONFIG_SECRETMEM) += secretmem.o
 obj-$(CONFIG_CMA_SYSFS) += cma_sysfs.o
mm/page_consistency.c new file +360 -0

360 lines not on this page · raw message

Signature · 1 line
2.53.0
#5 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 22 lines
mm/page_consistency.c new file +21 -0
+	/*
+	 * Size bitmaps to cover the full PFN range including any holes.
+	 * Holes waste a few bits but a flat bitmap keeps the indexing
+	 * trivial (pfn - min_pfn) and avoids additional data structures
+	 * that would themselves be subject to corruption.  This matches
+	 * the approach used by pageblock_flags.
+	 */
+	pc_state.min_pfn = PHYS_PFN(memblock_start_of_DRAM());
+	pc_state.max_pfn = PHYS_PFN(memblock_end_of_DRAM());
+	spanned_pfns = pc_state.max_pfn - pc_state.min_pfn;
+	if (!spanned_pfns || spanned_pfns > UINT_MAX) {
+		pr_err("PFN span %lu cannot be represented by bitmap APIs, feature disabled\n",
+		       spanned_pfns);
+		return;
+	}
+
+	pc_state.db.nbits = spanned_pfns;
+
+	bitmap_bytes = BITS_TO_LONGS(pc_state.db.nbits) * sizeof(unsigned long);
+
+	pr_info("Initializing: PFN range [%lu-%lu), %u bits (%zu KB per bitmap)\n",

mm/page_consistency.c line 338

Quoted 10 lines
mm/page_consistency.c new file +10 -0
+		pc_state.min_pfn, pc_state.max_pfn, pc_state.db.nbits,
+		bitmap_bytes / 1024);
+
+	/* Allocate primary bitmap (zeroed by memblock_alloc) */
+	pc_state.db.bitmap[DUAL_BITMAP_PRIMARY] =
+		memblock_alloc(bitmap_bytes, SMP_CACHE_BYTES);
+	if (!pc_state.db.bitmap[DUAL_BITMAP_PRIMARY]) {
+		pr_err("Failed to allocate primary bitmap, feature disabled\n");
+		return;
+	}

One bitmap that covers all sparse memory available at boot.

Conclusion: Just horrible.

Signature · 3 lines
Cheers,

David
#6 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 35 lines · David Hildenbrand (Arm)
Quoted 22 lines
mm/page_consistency.c new file +21 -0
+	/*
+	 * Size bitmaps to cover the full PFN range including any holes.
+	 * Holes waste a few bits but a flat bitmap keeps the indexing
+	 * trivial (pfn - min_pfn) and avoids additional data structures
+	 * that would themselves be subject to corruption.  This matches
+	 * the approach used by pageblock_flags.
+	 */
+	pc_state.min_pfn = PHYS_PFN(memblock_start_of_DRAM());
+	pc_state.max_pfn = PHYS_PFN(memblock_end_of_DRAM());
+	spanned_pfns = pc_state.max_pfn - pc_state.min_pfn;
+	if (!spanned_pfns || spanned_pfns > UINT_MAX) {
+		pr_err("PFN span %lu cannot be represented by bitmap APIs, feature disabled\n",
+		       spanned_pfns);
+		return;
+	}
+
+	pc_state.db.nbits = spanned_pfns;
+
+	bitmap_bytes = BITS_TO_LONGS(pc_state.db.nbits) * sizeof(unsigned long);
+
+	pr_info("Initializing: PFN range [%lu-%lu), %u bits (%zu KB per bitmap)\n",

mm/page_consistency.c line 338

Quoted 10 lines
mm/page_consistency.c new file +10 -0
+		pc_state.min_pfn, pc_state.max_pfn, pc_state.db.nbits,
+		bitmap_bytes / 1024);
+
+	/* Allocate primary bitmap (zeroed by memblock_alloc) */
+	pc_state.db.bitmap[DUAL_BITMAP_PRIMARY] =
+		memblock_alloc(bitmap_bytes, SMP_CACHE_BYTES);
+	if (!pc_state.db.bitmap[DUAL_BITMAP_PRIMARY]) {
+		pr_err("Failed to allocate primary bitmap, feature disabled\n");
+		return;
+	}

One bitmap that covers all sparse memory available at boot.

Quoted 1 line

Conclusion: Just horrible.

Depends on who's looking at the code :)

I picked it for auditability: covering the whole range with two memblock_alloc'd arrays means the only thing on the lookup path is the bitmap words themselves, which is what the dual-bitmap invariant already checks.

We could go with per-section bitmaps which will fix the waste but pull mem_section[] into the trust boundary, so we'd have to start validating it too.

Signature · 2 lines
Thanks,
Sasha
#7 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 36 lines · Sasha Levin
Quoted 35 lines · David Hildenbrand (Arm)
Quoted 22 lines
mm/page_consistency.c new file +21 -0
+	/*
+	 * Size bitmaps to cover the full PFN range including any holes.
+	 * Holes waste a few bits but a flat bitmap keeps the indexing
+	 * trivial (pfn - min_pfn) and avoids additional data structures
+	 * that would themselves be subject to corruption.  This matches
+	 * the approach used by pageblock_flags.
+	 */
+	pc_state.min_pfn = PHYS_PFN(memblock_start_of_DRAM());
+	pc_state.max_pfn = PHYS_PFN(memblock_end_of_DRAM());
+	spanned_pfns = pc_state.max_pfn - pc_state.min_pfn;
+	if (!spanned_pfns || spanned_pfns > UINT_MAX) {
+		pr_err("PFN span %lu cannot be represented by bitmap APIs, feature disabled\n",
+		       spanned_pfns);
+		return;
+	}
+
+	pc_state.db.nbits = spanned_pfns;
+
+	bitmap_bytes = BITS_TO_LONGS(pc_state.db.nbits) * sizeof(unsigned long);
+
+	pr_info("Initializing: PFN range [%lu-%lu), %u bits (%zu KB per bitmap)\n",

mm/page_consistency.c line 338

Quoted 10 lines
mm/page_consistency.c new file +10 -0
+		pc_state.min_pfn, pc_state.max_pfn, pc_state.db.nbits,
+		bitmap_bytes / 1024);
+
+	/* Allocate primary bitmap (zeroed by memblock_alloc) */
+	pc_state.db.bitmap[DUAL_BITMAP_PRIMARY] =
+		memblock_alloc(bitmap_bytes, SMP_CACHE_BYTES);
+	if (!pc_state.db.bitmap[DUAL_BITMAP_PRIMARY]) {
+		pr_err("Failed to allocate primary bitmap, feature disabled\n");
+		return;
+	}

One bitmap that covers all sparse memory available at boot.

Quoted 7 lines
Quoted 1 line

Conclusion: Just horrible.

Depends on who's looking at the code :)

I picked it for auditability: covering the whole range with two memblock_alloc'd arrays means the only thing on the lookup path is the bitmap words themselves, which is what the dual-bitmap invariant already checks.

The issue is that we are going back in time to a flat memory, without NUMA or hotplug support. We need an abstraction that avoids allocating this memory in enormous contiguous chunks, as thit approach will not work on modern hardware.

Quoted 3 lines

We could go with per-section bitmaps which will fix the waste but pull mem_section[] into the trust boundary, so we'd have to start validating it too.

Page-ext provides all of these capabilities, but as you described in the cover letter, it does not meet your requirements. Therefore, I believe a new abstraction layer is needed.

Pasha

#8 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 19 lines · Pasha Tatashin
Quoted 11 lines · Sasha Levin
Quoted 4 lines · David Hildenbrand (Arm)

One bitmap that covers all sparse memory available at boot.

Conclusion: Just horrible.

Depends on who's looking at the code :)

I picked it for auditability: covering the whole range with two memblock_alloc'd arrays means the only thing on the lookup path is the bitmap words themselves, which is what the dual-bitmap invariant already checks.

The issue is that we are going back in time to a flat memory, without NUMA or hotplug support. We need an abstraction that avoids allocating this memory in enormous contiguous chunks, as thit approach will not work on modern hardware.

Quoted 1 line
Quoted 6 lines
Quoted 2 lines

We could go with per-section bitmaps which will fix the waste but pull mem_section[] into the trust boundary, so we'd have to start validating it too.

Page-ext provides all of these capabilities, but as you described in the cover letter, it does not meet your requirements. Therefore, I believe a new abstraction layer is needed.

If we decided that we want this (and I am not convinced), we definitely want something that supports sparsity and, in particular, something that support memory hotplug.

Signature · 3 lines
Cheers,

David
#9 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 23 lines · David Hildenbrand (Arm)
Quoted 22 lines · Pasha Tatashin
Quoted 11 lines · Sasha Levin
Quoted 4 lines · David Hildenbrand (Arm)

One bitmap that covers all sparse memory available at boot.

Conclusion: Just horrible.

Depends on who's looking at the code :)

I picked it for auditability: covering the whole range with two memblock_alloc'd arrays means the only thing on the lookup path is the bitmap words themselves, which is what the dual-bitmap invariant already checks.

The issue is that we are going back in time to a flat memory, without NUMA or hotplug support. We need an abstraction that avoids allocating this memory in enormous contiguous chunks, as thit approach will not work on modern hardware.

Quoted 3 lines

We could go with per-section bitmaps which will fix the waste but pull mem_section[] into the trust boundary, so we'd have to start validating it too.

Quoted 7 lines
Quoted 3 lines

Page-ext provides all of these capabilities, but as you described in the cover letter, it does not meet your requirements. Therefore, I believe a new abstraction layer is needed.

If we decided that we want this (and I am not convinced), we definitely want something that supports sparsity and, in particular, something that support memory hotplug.

Makes sense. Let me take a few days and see if I can find some middle ground here.

Signature · 2 lines
Thanks,
Sasha
#10 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 13 lines · Sasha Levin
Quoted 12 lines · David Hildenbrand (Arm)
Quoted 10 lines · Pasha Tatashin

The issue is that we are going back in time to a flat memory, without NUMA or hotplug support. We need an abstraction that avoids allocating this memory in enormous contiguous chunks, as thit approach will not work on modern hardware.

Page-ext provides all of these capabilities, but as you described in the cover letter, it does not meet your requirements. Therefore, I believe a new abstraction layer is needed.

Quoted 7 lines
Quoted 3 lines

If we decided that we want this (and I am not convinced), we definitely want something that supports sparsity and, in particular, something that support memory hotplug.

Makes sense. Let me take a few days and see if I can find some middle ground here.

"The natural question is why not use page_ext. The key objection from a safety perspective is that page_ext stores per-page metadata in memory that is itself subject to the same hardware faults we're trying to detect. The dual-bitmap approach works because the two bitmaps are independent allocations - corruption in one is caught by comparison with the other."

So you want to have two bits per page, whereby both bits come from in dependent pages I assume?

Storing one bit in page_ext and one bit in page flags would be possible if we had a spare bit in page flags ... We could allocate two bitmaps per memory section.

But the real question is: how far away do these bits have to be in memory to be considered "independent" and not prone to the same corruption?

1 bit?
1 byte?
64 byte?
4096 byte?
???

"Embedding both in page_ext means a single fault could corrupt both the tracking data and its redundant copy in the same allocation region."

I might be wrong, but isn't that the case for any such fault, as you don't 100% know how the DIMM is organized internally?

Do we really expect that a MCE event would, for example, very likely corrupt two neighboring bits, or two bits in the same byte etc? What are the odds that we care?

It's hard to tell here which part of this work is "too research focused". For example, if I were to write a paper about that, I would make such claims to make it sound more complicated than it needs to be :)

Signature · 3 lines
Cheers,

David
#11 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 29 lines · David Hildenbrand (Arm)
Quoted 13 lines · Sasha Levin
Quoted 12 lines · David Hildenbrand (Arm)
Quoted 10 lines · Pasha Tatashin

The issue is that we are going back in time to a flat memory, without NUMA or hotplug support. We need an abstraction that avoids allocating this memory in enormous contiguous chunks, as thit approach will not work on modern hardware.

Page-ext provides all of these capabilities, but as you described in the cover letter, it does not meet your requirements. Therefore, I believe a new abstraction layer is needed.

Quoted 7 lines
Quoted 3 lines

If we decided that we want this (and I am not convinced), we definitely want something that supports sparsity and, in particular, something that support memory hotplug.

Makes sense. Let me take a few days and see if I can find some middle ground here.

"The natural question is why not use page_ext. The key objection from a safety perspective is that page_ext stores per-page metadata in memory that is itself subject to the same hardware faults we're trying to detect. The dual-bitmap approach works because the two bitmaps are independent allocations - corruption in one is caught by comparison with the other."

Quoted 2 lines

So you want to have two bits per page, whereby both bits come from in dependent pages I assume?

Ideally completely different DIMMs (though as you point out later, we can't easily make this happen).

Quoted 2 lines

Storing one bit in page_ext and one bit in page flags would be possible if we had a spare bit in page flags ... We could allocate two bitmaps per memory section.

Right, I think that the approach you proposed is roughly equivalent spatially (though I'd need to check with the safety folks here).

Quoted 8 lines

But the real question is: how far away do these bits have to be in memory to be considered "independent" and not prone to the same corruption?

1 bit?
1 byte?
64 byte?
4096 byte?
???

The notes I have from the research side of things (which should be taken with a grain of salt) are something along the lines of:

- ~79% are a single bit corruption
- ~9% are row faults, so multiple bit corruption within ~8kb
- ~4% are bank faults, so multiple bit corruption within ~512mb

Obviously the numbers would be very different depending on usecase, hardware, physical location (did you know bits are more likely to flip in higher altitudes?)...

Quoted 9 lines

"Embedding both in page_ext means a single fault could corrupt both the tracking data and its redundant copy in the same allocation region."

I might be wrong, but isn't that the case for any such fault, as you don't 100% know how the DIMM is organized internally?

Do we really expect that a MCE event would, for example, very likely corrupt two neighboring bits, or two bits in the same byte etc? What are the odds that we care?

For something like a datacenter deployment I'd agree with you - the odds are too low to care. For an unsupervised self driving vehicle, where there's no human (locally or remotely) available to take over, I'd like the odds to be as low as possible :)

Quoted 3 lines

It's hard to tell here which part of this work is "too research focused". For example, if I were to write a paper about that, I would make such claims to make it sound more complicated than it needs to be :)

Signature · 2 lines
Thanks,
Sasha
#12 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 9 lines
Quoted 8 lines

But the real question is: how far away do these bits have to be in memory to be considered "independent" and not prone to the same corruption?

1 bit?
1 byte?
64 byte?
4096 byte?
???

Quoted 6 lines

The notes I have from the research side of things (which should be taken with a grain of salt) are something along the lines of:

 - ~79% are a single bit corruption
 - ~9% are row faults, so multiple bit corruption within ~8kb
 - ~4% are bank faults, so multiple bit corruption within ~512mb

Interesting numbers, thanks! What are the other missing %?

Quoted 4 lines

Obviously the numbers would be very different depending on usecase, hardware, physical location (did you know bits are more likely to flip in higher altitudes?)...

Yeah, heavy cosmic ray apparently makes the problem worse.

The 512mb case is obviously tricky to handle (and is very hw dependent).

Placing bits at least two pages apart could be done more easily.

Quoted 8 lines
Quoted 8 lines

"Embedding both in page_ext means a single fault could corrupt both the tracking data and its redundant copy in the same allocation region."

I might be wrong, but isn't that the case for any such fault, as you don't 100% know how the DIMM is organized internally?

Quoted 8 lines
Quoted 3 lines

Do we really expect that a MCE event would, for example, very likely corrupt two neighboring bits, or two bits in the same byte etc? What are the odds that we care?

For something like a datacenter deployment I'd agree with you - the odds are too low to care. For an unsupervised self driving vehicle, where there's no human (locally or remotely) available to take over, I'd like the odds to be as low as possible :)

I thought that people usually use special RT OSes (with proven logic etc) for any safety-related systems. Using Linux on the core safety system sounds ... scary.

But, I'd expect corruption of other data (user pages? page tables?) a much bigger problem than page al locator metdata? What am I missing that this here is -- in context of the bigger problems there -- a thing we particularly care about?

Signature · 3 lines
Cheers,

David
#13 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 9 lines · David Hildenbrand (Arm)
Quoted 9 lines
Quoted 8 lines

But the real question is: how far away do these bits have to be in memory to be considered "independent" and not prone to the same corruption?

1 bit?
1 byte?
64 byte?
4096 byte?
???

Quoted 8 lines
Quoted 6 lines

The notes I have from the research side of things (which should be taken with a grain of salt) are something along the lines of:

 - ~79% are a single bit corruption
 - ~9% are row faults, so multiple bit corruption within ~8kb
 - ~4% are bank faults, so multiple bit corruption within ~512mb

Interesting numbers, thanks! What are the other missing %?

- ~6% single-column: bits in one physical column across multiple rows
- ~1% multi-rank
- ~0.6% multi-bank

Quoted 23 lines
Quoted 4 lines

Obviously the numbers would be very different depending on usecase, hardware, physical location (did you know bits are more likely to flip in higher altitudes?)...

Yeah, heavy cosmic ray apparently makes the problem worse.

The 512mb case is obviously tricky to handle (and is very hw dependent).

Placing bits at least two pages apart could be done more easily.

Quoted 12 lines
Quoted 11 lines

"Embedding both in page_ext means a single fault could corrupt both the tracking data and its redundant copy in the same allocation region."

I might be wrong, but isn't that the case for any such fault, as you don't 100% know how the DIMM is organized internally?

Do we really expect that a MCE event would, for example, very likely corrupt two neighboring bits, or two bits in the same byte etc? What are the odds that we care?

Quoted 7 lines
Quoted 4 lines

For something like a datacenter deployment I'd agree with you - the odds are too low to care. For an unsupervised self driving vehicle, where there's no human (locally or remotely) available to take over, I'd like the odds to be as low as possible :)

I thought that people usually use special RT OSes (with proven logic etc) for any safety-related systems. Using Linux on the core safety system sounds ... scary.

RT OSes are indeed the current approach.

s/scary/exciting ;)

Quoted 3 lines

But, I'd expect corruption of other data (user pages? page tables?) a much bigger problem than page al locator metdata? What am I missing that this here is -- in context of the bigger problems there -- a thing we particularly care about?

You are very correct! The allocator work was fairly standalone, so it was an easy first project to tackle.

In general, the approach depends on what we're trying to defend from:

1. bugs: an ASI-like MMU enforced "context" system.
2. physics: just like in most other areas - lots of redundancy. For example, consider redundant variables in safety critical code which exists as two
copies: var_v1 = value and var_v2 = value XOR mask. When accessing them, read both copies, XOR the second back, compare.

There were a few sessions back in LPC about this. Here's the one from Bryan Huntsman which gives a good overview:
https://www.youtube.com/watch?v=ie_ClBCed94

Signature · 2 lines
Thanks,
Sasha
#14 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

For something like a datacenter deployment I'd agree with you - the odds are too low to care. For an unsupervised self driving vehicle, where there's no human (locally or remotely) available to take over, I'd like the odds to be as low as possible :)

Quoted 7 lines
Quoted 3 lines

I thought that people usually use special RT OSes (with proven logic etc) for any safety-related systems. Using Linux on the core safety system sounds ... scary.

RT OSes are indeed the current approach.

s/scary/exciting ;)

Not so exciting for the passengers ;)

Quoted 7 lines
Quoted 4 lines

But, I'd expect corruption of other data (user pages? page tables?) a much bigger problem than page al locator metdata? What am I missing that this here is -- in context of the bigger problems there -- a thing we particularly care about?

You are very correct! The allocator work was fairly standalone, so it was an easy first project to tackle.

But in general, wouldn't we just expect ECC memory to give us an MCE, so we can detect what was corrupted and act accordingly?

That's how it usually works: hw detects a memory corruption and injects an MCE. We detect that we corrupted memmap state and kill the kernel.

Why does ECC not help here?

Quoted 9 lines

In general, the approach depends on what we're trying to defend from:

1. bugs: an ASI-like MMU enforced "context" system.
2. physics: just like in most other areas - lots of redundancy. For example, consider redundant variables in safety critical code which exists as two
copies: var_v1 = value and var_v2 = value XOR mask. When accessing them, read both copies, XOR the second back, compare.

Quoted 3 lines

There were a few sessions back in LPC about this. Here's the one from Bryan Huntsman which gives a good overview:
https://www.youtube.com/watch?v=ie_ClBCed94

Thanks, but I fundamentally don't understand how RAS capabilities interact here? We have mm/memory-failure.c for a reason :)

Signature · 3 lines
Cheers,

David
#15 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 24 lines · David Hildenbrand (Arm)
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

For something like a datacenter deployment I'd agree with you - the odds are too low to care. For an unsupervised self driving vehicle, where there's no human (locally or remotely) available to take over, I'd like the odds to be as low as possible :)

Quoted 7 lines
Quoted 3 lines

I thought that people usually use special RT OSes (with proven logic etc) for any safety-related systems. Using Linux on the core safety system sounds ... scary.

RT OSes are indeed the current approach.

s/scary/exciting ;)

Not so exciting for the passengers ;)

Quoted 7 lines
Quoted 4 lines

But, I'd expect corruption of other data (user pages? page tables?) a much bigger problem than page al locator metdata? What am I missing that this here is -- in context of the bigger problems there -- a thing we particularly care about?

You are very correct! The allocator work was fairly standalone, so it was an easy first project to tackle.

Quoted 7 lines

But in general, wouldn't we just expect ECC memory to give us an MCE, so we can detect what was corrupted and act accordingly?

That's how it usually works: hw detects a memory corruption and injects an MCE. We detect that we corrupted memmap state and kill the kernel.

Why does ECC not help here?

It helps, but it's not enough. ECC doesn't detect all errors (For example, SECDED corrects single-bit, detects double-bit, but triple-bit errors can land on a different valid codeword).

Quoted 8 lines
Quoted 8 lines

In general, the approach depends on what we're trying to defend from:

1. bugs: an ASI-like MMU enforced "context" system.
2. physics: just like in most other areas - lots of redundancy. For example, consider redundant variables in safety critical code which exists as two
copies: var_v1 = value and var_v2 = value XOR mask. When accessing them, read both copies, XOR the second back, compare.

Quoted 6 lines
Quoted 3 lines

There were a few sessions back in LPC about this. Here's the one from Bryan Huntsman which gives a good overview:
https://www.youtube.com/watch?v=ie_ClBCed94

Thanks, but I fundamentally don't understand how RAS capabilities interact here? We have mm/memory-failure.c for a reason :)

We do, but self driving safety requires way more than the current hardware can provide.

I'll point you to https://dl.acm.org/doi/10.1145/2775054.2694348 , which researched these issues in a datacenter environment (so no sun exposure, temperature controlled, designed to avoid electromagnetic interference).

"We call a fault that generates an error larger than 2 bits in an ECC word an undetectable-by-SECDED fault. A fault is undetectable-by-SECDED if it affects more than two bits in any ECC word, and the data written to that location does not match the value produced by the fault."

[...]

"A Cielo node has 288 DRAM devices, so this translates to 6048, 518, and 57.6 FIT per node for vendors A, B, and C, respectively. This translates to one undetected error every 0.8 days, every 9.5 days, and every 85 days on a machine the size of Cielo."

[...]

"Our main conclusion from this data is that SEC-DED ECC is poorly suited to modern DRAM subsystems. The rate of undetected errors is too high to justify its use in very large scale systems comprised of thousands of nodes where fidelity of results is critical."

The passengers you've mentioned before would be excited if they knew how high the bar is around their safety :)

Signature · 2 lines
Thanks,
Sasha
#16 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 24 lines
Quoted 4 lines

Thanks, but I fundamentally don't understand how RAS capabilities interact here? We have mm/memory-failure.c for a reason :)

We do, but self driving safety requires way more than the current hardware can provide.

I'll point you to https://dl.acm.org/doi/10.1145/2775054.2694348 , which researched these issues in a datacenter environment (so no sun exposure, temperature controlled, designed to avoid electromagnetic interference).

"We call a fault that generates an error larger than 2 bits in an ECC word an undetectable-by-SECDED fault. A fault is undetectable-by-SECDED if it affects more than two bits in any ECC word, and the data written to that location does not match the value produced by the fault."

[...]

"A Cielo node has 288 DRAM devices, so this translates to 6048, 518, and 57.6 FIT per node for vendors A, B, and C, respectively. This translates to one undetected error every 0.8 days, every 9.5 days, and every 85 days on a machine the size of Cielo."

Quoted 6 lines

[...]

"Our main conclusion from this data is that SEC-DED ECC is poorly suited to modern DRAM subsystems. The rate of undetected errors is too high to justify its use in very large scale systems comprised of thousands of nodes where fidelity of results is critical."

Yes, I read before that ECC is insufficient to detect certain bitflips.

But I don't understand how this patch set here is going to move the needle in any reasonable way?

You have your magical self-driving car algorithm.

Bitflips can corrupt your algorithm, your data, the kernel image, your user page tables, your kernel page tables. Even a pointer to a bitmap :)

... and we worry about the state of allocated vs. free pages.

Please enlighten me!

Quoted 3 lines

The passengers you've mentioned before would be excited if they knew how high the bar is around their safety :)

Heh :)

Signature · 3 lines
Cheers,

David
#17 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 36 lines · David Hildenbrand (Arm)
Quoted 24 lines
Quoted 4 lines

Thanks, but I fundamentally don't understand how RAS capabilities interact here? We have mm/memory-failure.c for a reason :)

We do, but self driving safety requires way more than the current hardware can provide.

I'll point you to https://dl.acm.org/doi/10.1145/2775054.2694348 , which researched these issues in a datacenter environment (so no sun exposure, temperature controlled, designed to avoid electromagnetic interference).

"We call a fault that generates an error larger than 2 bits in an ECC word an undetectable-by-SECDED fault. A fault is undetectable-by-SECDED if it affects more than two bits in any ECC word, and the data written to that location does not match the value produced by the fault."

[...]

"A Cielo node has 288 DRAM devices, so this translates to 6048, 518, and 57.6 FIT per node for vendors A, B, and C, respectively. This translates to one undetected error every 0.8 days, every 9.5 days, and every 85 days on a machine the size of Cielo."

Quoted 6 lines

[...]

"Our main conclusion from this data is that SEC-DED ECC is poorly suited to modern DRAM subsystems. The rate of undetected errors is too high to justify its use in very large scale systems comprised of thousands of nodes where fidelity of results is critical."

Yes, I read before that ECC is insufficient to detect certain bitflips.

But I don't understand how this patch set here is going to move the needle in any reasonable way?

Quoted 6 lines

You have your magical self-driving car algorithm.

Bitflips can corrupt your algorithm, your data, the kernel image, your user page tables, your kernel page tables. Even a pointer to a bitmap :)

... and we worry about the state of allocated vs. free pages.

Do we agree that this is one piece of a (much) larger puzzle that we would need to tackle?

Quoted 1 line

Please enlighten me!

Definitely! This is a pretty hefty body of work, so outside of trying to get the code out there we're also working on documentation, talks, webinars, etc in the context of ELISA (https://elisa.tech/).

The concept itself was approved by an independant assessor as compliant with the relevant safety standard, so the story is there, we're just working on getting it out.

Signature · 2 lines
Thanks,
Sasha
#18 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

Quoted 36 lines · Sasha Levin
Quoted 35 lines · David Hildenbrand (Arm)
Quoted 21 lines

We do, but self driving safety requires way more than the current hardware can provide.

I'll point you to https://dl.acm.org/doi/10.1145/2775054.2694348 , which researched these issues in a datacenter environment (so no sun exposure, temperature controlled, designed to avoid electromagnetic interference).

"We call a fault that generates an error larger than 2 bits in an ECC word an undetectable-by-SECDED fault. A fault is undetectable-by-SECDED if it affects more than two bits in any ECC word, and the data written to that location does not match the value produced by the fault."

[...]

"A Cielo node has 288 DRAM devices, so this translates to 6048, 518, and 57.6 FIT per node for vendors A, B, and C, respectively. This translates to one undetected error every 0.8 days, every 9.5 days, and every 85 days on a machine the size of Cielo."

Quoted 6 lines

[...]

"Our main conclusion from this data is that SEC-DED ECC is poorly suited to modern DRAM subsystems. The rate of undetected errors is too high to justify its use in very large scale systems comprised of thousands of nodes where fidelity of results is critical."

Yes, I read before that ECC is insufficient to detect certain bitflips.

But I don't understand how this patch set here is going to move the needle in any reasonable way?

You have your magical self-driving car algorithm.

Quoted 7 lines
Quoted 4 lines

Bitflips can corrupt your algorithm, your data, the kernel image, your user page tables, your kernel page tables. Even a pointer to a bitmap :)

... and we worry about the state of allocated vs. free pages.

Do we agree that this is one piece of a (much) larger puzzle that we would need to tackle?

Once you solved the real hard problems (corrupting random page state, page tables, all of that) we can think about whether adding complexity to the page allocator to detect possible corruptions.

As you state in your reply to Vlasta, the buddy keeps free pages in a list. So a pointer corruption there would be rather fatal, and I don't follow how the approach here makes things any better.

So for the time being, I don't think this proposal moves the needle in any reasonable way, and I don't think we want this any time soon.

Signature · 3 lines
Cheers,

David
#19 lore raw

Re: [RFC 4/7] mm: add page consistency checker implementation

In reply to Sasha Levin
Quoted 37 lines · Sasha Levin
Quoted 36 lines · David Hildenbrand (Arm)
Quoted 23 lines

+    /*
+     * Size bitmaps to cover the full PFN range including any holes. +     * Holes waste a few bits but a flat bitmap keeps the indexing +     * trivial (pfn - min_pfn) and avoids additional data structures +     * that would themselves be subject to corruption.  This matches +     * the approach used by pageblock_flags.
+     */
+    pc_state.min_pfn = PHYS_PFN(memblock_start_of_DRAM());
+    pc_state.max_pfn = PHYS_PFN(memblock_end_of_DRAM());
+    spanned_pfns = pc_state.max_pfn - pc_state.min_pfn;
+    if (!spanned_pfns || spanned_pfns > UINT_MAX) {
+        pr_err("PFN span %lu cannot be represented by bitmap APIs, feature disabled\n",
+               spanned_pfns);
+        return;
+    }

mm/page_consistency.c new file +6 -0
+
+    pc_state.db.nbits = spanned_pfns;
+
+    bitmap_bytes = BITS_TO_LONGS(pc_state.db.nbits) * sizeof(unsigned long);
+
+    pr_info("Initializing: PFN range [%lu-%lu), %u bits (%zu KB per bitmap)\n",

mm/page_consistency.c line 338

Quoted 10 lines
mm/page_consistency.c new file +10 -0
+        pc_state.min_pfn, pc_state.max_pfn, pc_state.db.nbits,
+        bitmap_bytes / 1024);
+
+    /* Allocate primary bitmap (zeroed by memblock_alloc) */
+    pc_state.db.bitmap[DUAL_BITMAP_PRIMARY] =
+        memblock_alloc(bitmap_bytes, SMP_CACHE_BYTES);
+    if (!pc_state.db.bitmap[DUAL_BITMAP_PRIMARY]) {
+        pr_err("Failed to allocate primary bitmap, feature disabled\n");
+        return;
+    }

One bitmap that covers all sparse memory available at boot.

Quoted 3 lines
Quoted 1 line

Conclusion: Just horrible.

Depends on who's looking at the code :)

Or who generated that code ;)

Signature · 3 lines
Cheers,

David
#20 lore raw

RFC 5/7 mm/page_alloc: integrate page consistency hooks

In reply to Sasha Levin

From: Sasha Levin <[email protected]>

Wire up the page consistency checker with the page allocator by adding tracking hooks in the allocation and free paths. The hooks follow the same pattern already established by page_owner and page_table_check, inserting calls at the points where page state transitions occur.

In post_alloc_hook(), a call to page_consistency_alloc() is added after the page_table_check_alloc() call. This records the allocation in both bitmaps, setting the primary bit and clearing the secondary bit for each page in the allocation.

In __free_pages_prepare(), calls to page_consistency_free() are added in both the early-return path for the hwpoison check and the normal exit path. These calls clear the primary bitmap and set the secondary bitmap, maintaining the complementary relationship that enables corruption detection. The free hook lives in the internal __free_pages_prepare() rather than its free_pages_prepare() wrapper so that every free path (including the bulk folio free path) is observed exactly once.

Initialization is hooked into mm_core_init() immediately before memblock_free_all(), while memblock is still active so it can use memblock_alloc() for the bitmaps, and after kho_memory_init() so that any memory handed back by a kexec-handover source has already been accounted.

Assisted-by Claude:claude-opus-4-7 <[email protected]>
---
 mm/mm_init.c    | 9 +++++++++
 mm/page_alloc.c | 4 ++++
 2 files changed, 13 insertions(+)
mm/mm_init.c +9 -0
index df34797691bd..4d9495fb8789 100644
@@ -22,6 +22,7 @@
 #include <linux/kmemleak.h>
 #include <linux/kfence.h>
 #include <linux/page_ext.h>
+#include <linux/page_consistency.h>
 #include <linux/pti.h>
 #include <linux/pgtable.h>
 #include <linux/stackdepot.h>
@@ -2717,6 +2718,14 @@ void __init mm_core_init(void)
 	 */
 	kho_memory_init();
 
+	/*
+	 * page_consistency_init() must run while memblock is active so it
+	 * can use memblock_alloc() for the bitmaps.  Boot-time reserved pages
+	 * may be freed before SYSTEM_RUNNING without ever having been allocated
+	 * through the buddy allocator, so the checker suppresses double-free
+	 * reports until boot has completed.
+	 */
+	page_consistency_init();
 	memblock_free_all();
 	mem_init();
 	kmem_cache_init();
mm/page_alloc.c +4 -0
index 2d4b6f1a554e..ae8f619875e9 100644
@@ -46,6 +46,7 @@
 #include <linux/sched/mm.h>
 #include <linux/page_owner.h>
 #include <linux/page_table_check.h>
+#include <linux/page_consistency.h>
 #include <linux/memcontrol.h>
 #include <linux/ftrace.h>
 #include <linux/lockdep.h>
@@ -1374,6 +1375,7 @@ __always_inline bool __free_pages_prepare(struct page *page,
 		/* Do not let hwpoison pages hit pcplists/buddy */
 		reset_page_owner(page, order);
 		page_table_check_free(page, order);
+		page_consistency_free(page, order);
 		pgalloc_tag_sub(page, 1 << order);
 
 		/*
@@ -1432,6 +1434,7 @@ __always_inline bool __free_pages_prepare(struct page *page,
 	page->private = 0;
 	reset_page_owner(page, order);
 	page_table_check_free(page, order);
+	page_consistency_free(page, order);
 	pgalloc_tag_sub(page, 1 << order);
 
 	if (!PageHighMem(page) && !(fpi_flags & FPI_TRYLOCK)) {
@@ -1888,6 +1891,7 @@ inline void post_alloc_hook(struct page *page, unsigned int order,
 
 	set_page_owner(page, order, gfp_flags);
 	page_table_check_alloc(page, order);
+	page_consistency_alloc(page, order);
 	pgalloc_tag_add(page, current, 1 << order);
 }
 
Signature · 1 line
2.53.0
#21 lore raw

RFC 6/7 Documentation/mm: add page consistency checker documentation

In reply to Sasha Levin

From: Sasha Levin <[email protected]>

Add documentation for the page consistency checker feature. The document explains the dual-bitmap algorithm, describes the configuration options, and covers the debugfs interface for monitoring and validation.

The algorithm section explains how the complementary bitmaps work: the primary bitmap uses 1 for allocated and 0 for free, while the secondary bitmap uses the opposite convention. This redundancy means any single-bit corruption in either bitmap will cause a detectable violation of the invariant that primary[bit] must equal ~secondary[bit].

The document also explains the intentional limitation around double-free detection. During boot, free_reserved_area() releases pages that were never allocated through the buddy allocator. Flagging these as errors would generate many false positives, so double-free detection is deferred until after boot completes.

Assisted-by Claude:claude-opus-4-7 <[email protected]>
---
 Documentation/mm/index.rst            |   1 +
 Documentation/mm/page_consistency.rst | 211 ++++++++++++++++++++++++++
 2 files changed, 212 insertions(+)
 create mode 100644 Documentation/mm/page_consistency.rst
Documentation/mm/index.rst +1 -0
index 7aa2a8886908..bef6c9bbc976 100644
@@ -57,6 +57,7 @@ documentation, or deleted if it has served its purpose.
    page_frags
    page_owner
    page_table_check
+   page_consistency
    remap_file_pages
    split_page_table_lock
    transhuge
Documentation/mm/page_consistency.rst new file +211 -0

211 lines not on this page · raw message

Signature · 1 line
2.53.0
#22 lore raw

RFC 7/7 mm/page_consistency: add KUnit tests for dual-bitmap primitives

In reply to Sasha Levin

From: Sasha Levin <[email protected]>

Add a KUnit test suite that exercises the dual-bitmap algorithm used by the page consistency checker. The tests verify that the core invariant is maintained through various operations and that corruption can be reliably detected.

The test suite covers several scenarios. The initial-state test confirms that a freshly initialized dual bitmap with zeroed primary and filled secondary passes validation. The set and clear tests verify that normal operations maintain the complementary relationship between bitmaps. The double-set and double-clear tests confirm that attempts to set an already-set bit or clear an already-clear bit are properly detected and reported through the return value.

The corruption detection tests are particularly important for validating the safety guarantees. These tests directly manipulate one bitmap without updating its complement, simulating what would happen if a memory error flipped a bit. Both primary and secondary corruption scenarios are tested, confirming that either type is caught by validation.

The suite also includes boundary condition tests covering the first bit, last bit, and word boundaries to ensure the bit manipulation logic handles edge cases correctly.

Assisted-by Claude:claude-opus-4-7 <[email protected]>
---
 mm/Makefile                |   1 +
 mm/page_consistency_test.c | 274 +++++++++++++++++++++++++++++++++++++
 2 files changed, 275 insertions(+)
 create mode 100644 mm/page_consistency_test.c
mm/Makefile +1 -0
index 2ee360001456..7106aeb79cf5 100644
@@ -129,6 +129,7 @@ obj-$(CONFIG_BALLOON) += balloon.o
 obj-$(CONFIG_PAGE_EXTENSION) += page_ext.o
 obj-$(CONFIG_PAGE_TABLE_CHECK) += page_table_check.o
 obj-$(CONFIG_DEBUG_PAGE_CONSISTENCY) += page_consistency.o
+obj-$(CONFIG_DEBUG_PAGE_CONSISTENCY_KUNIT_TEST) += page_consistency_test.o
 obj-$(CONFIG_CMA_DEBUGFS) += cma_debug.o
 obj-$(CONFIG_SECRETMEM) += secretmem.o
 obj-$(CONFIG_CMA_SYSFS) += cma_sysfs.o
mm/page_consistency_test.c new file +274 -0

274 lines not on this page · raw message

Signature · 1 line
2.53.0
#23 lore raw
In reply to Sasha Levin
Quoted 5 lines · Sasha Levin

corruption must be detected before it propagates. The dual-bitmap implements a way to protect from corruption coming from hardware or software - two complementary representations of page allocation state, allocated independently via memblock, where any single-bit fault in either bitmap is immediately detectable. Performance is secondary to

Quoted 8 lines

correctness in this context. A safety mechanism must be simple enough to audit and certify, must fail deterministically (panic, not log-and-hope), and its correctness matters more than its throughput. The dual-bitmap adds two atomic bitops per alloc/free, but for safety-critical deployments this cost is acceptable because the alternative - undetected corruption propagating silently - violates the system's safety case. The static key ensures zero cost for kernels that don't need it.

But doubling the storage requirement in order to achieve merely detection is significantly worse than state-of-the-art in 1950 (when Richard Hamming invented Hamming codes). If we used a (7,3) code, we'd have SECDED at a lower cost. Of course, there are far better codes available than that today.

#24 lore raw
Quoted 15 lines · Matthew Wilcox
Quoted 5 lines · Sasha Levin

corruption must be detected before it propagates. The dual-bitmap implements a way to protect from corruption coming from hardware or software - two complementary representations of page allocation state, allocated independently via memblock, where any single-bit fault in either bitmap is immediately detectable. Performance is secondary to

Quoted 8 lines

correctness in this context. A safety mechanism must be simple enough to audit and certify, must fail deterministically (panic, not log-and-hope), and its correctness matters more than its throughput. The dual-bitmap adds two atomic bitops per alloc/free, but for safety-critical deployments this cost is acceptable because the alternative - undetected corruption propagating silently - violates the system's safety case. The static key ensures zero cost for kernels that don't need it.

Quoted 5 lines

But doubling the storage requirement in order to achieve merely detection is significantly worse than state-of-the-art in 1950 (when Richard Hamming invented Hamming codes). If we used a (7,3) code, we'd have SECDED at a lower cost. Of course, there are far better codes available than that today.

I agree with the density concern. I have two reasons for that:

1. Update cost. On the alloc/free hot path the dual-bitmap update is two independent test_and_set_bit. A Hamming/SECDED codeword needs a read-modify-write of the whole word with locking on every state change.

2. Correlated faults. The two copies need to sit in different physical memory so a multi-bit fault (row, column, bank, row-hammer) can only hit one of them. See this paper which has some numbers:
https://dl.acm.org/doi/epdf/10.1145/2786763.2694348 - About 21% of DRAM faults span more than one bit, plain SECDED can leave up to 20 FIT per device of undetected errors from those, and it only helps at all if data and parity bits are spread across physically separate cells.

Two memblock_alloc'd bitmaps give that separation for free. You could interleave a code across two independent regions instead, but then the invariant check stops being a one-line complement check, which is what I was trying to keep simple for the audit side.

Signature · 2 lines
Thanks,
Sasha
#25 lore raw
In reply to Sasha Levin
Quoted 4 lines · Sasha Levin

Existing memory debugging tools - KASAN, KFENCE, page_poisoning - detect access violations and content corruption, but none of them can detect silent corruption in the page allocator's own metadata. If a hardware bit flip corrupts an allocation bitmap, the allocator hands out a page

An allocation what? The page allocator is a buddy allocator, it has no bitmap to track free/allocated state of pages?

#26 lore raw
Quoted 8 lines · Vlastimil Babka (SUSE)
Quoted 4 lines · Sasha Levin

Existing memory debugging tools - KASAN, KFENCE, page_poisoning - detect access violations and content corruption, but none of them can detect silent corruption in the page allocator's own metadata. If a hardware bit flip corrupts an allocation bitmap, the allocator hands out a page

An allocation what? The page allocator is a buddy allocator, it has no bitmap to track free/allocated state of pages?

You're right, the cover letter is misleading there. Buddy doesn't use a bitmap:
PageBuddy lives in page_type, the free list is a list, and page->private holds the order. The dual-bitmap is new metadata the feature adds, maintained from the alloc/free hooks.

What it actually catches is the same PFN being handed out twice before it's freed, or freed without having been allocated. Not every kind of buddy corruption shows up that way, but the common bad ones do. Corruption of the bitmap itself shows up through the complement invariant.

I'll fix the wording in v2.

Signature · 2 lines
Thanks,
Sasha
#27 lore raw
Quoted 7 lines · Sasha Levin
Quoted 6 lines · Vlastimil Babka (SUSE)
Quoted 4 lines · Sasha Levin

Existing memory debugging tools - KASAN, KFENCE, page_poisoning - detect access violations and content corruption, but none of them can detect silent corruption in the page allocator's own metadata. If a hardware bit flip corrupts an allocation bitmap, the allocator hands out a page

Quoted 7 lines
Quoted 2 lines

An allocation what? The page allocator is a buddy allocator, it has no bitmap to track free/allocated state of pages?

You're right, the cover letter is misleading there. Buddy doesn't use a bitmap:
PageBuddy lives in page_type, the free list is a list, and page->private holds the order. The dual-bitmap is new metadata the feature adds, maintained from the alloc/free hooks.

Given that you have PageBuddy (first "bit"), could we use a second bit in page_ext?

Signature · 3 lines
Cheers,

David
#28 lore raw
Quoted 11 lines · David Hildenbrand (Arm)
Quoted 10 lines · Sasha Levin
Quoted 8 lines · Vlastimil Babka (SUSE)
Quoted 4 lines · Sasha Levin

Existing memory debugging tools - KASAN, KFENCE, page_poisoning - detect access violations and content corruption, but none of them can detect silent corruption in the page allocator's own metadata. If a hardware bit flip corrupts an allocation bitmap, the allocator hands out a page

An allocation what? The page allocator is a buddy allocator, it has no bitmap to track free/allocated state of pages?

Quoted 6 lines
Quoted 4 lines

You're right, the cover letter is misleading there. Buddy doesn't use a bitmap:
PageBuddy lives in page_type, the free list is a list, and page->private holds the order. The dual-bitmap is new metadata the feature adds, maintained from the alloc/free hooks.

Given that you have PageBuddy (first "bit"), could we use a second bit in page_ext?

Hmm... Thats an interesting idea.

I can see two concerns with something like this:

1. The checker has to be live before memblock_free_all() hands pages to buddy. page_ext isn't fully up that early I think.

2. page_type encodes buddy, offline, slab tags, etc... and a page that isn't PageBuddy isn't necessarily allocated through alloc_pages. The invariant gets case-y.

But let me think about it a bit more.

Signature · 2 lines
Thanks,
Sasha