Skip to contentSkip to conversation

Implement MTE tag compression for swapped pages

PATCH Superseded Alexander Potapenko 5 participants 21 messages Sep 22, 2023 – Oct 2, 2023 1 message not in the archive

Subsystems (4)

v5 of 12 Superseded Latest is v12 →

lore
Share & tools
lore
#0 lore raw

v5 cover Implement MTE tag compression for swapped pages

Currently, when MTE pages are swapped out, the tags are kept in the memory, occupying PAGE_SIZE/32 bytes per page. This is especially problematic for devices that use zram-backed in-memory swap, because tags stored uncompressed in the heap effectively reduce the available amount of swap memory.

The RLE-based algorithm suggested by Evgenii Stepanov and implemented in this patch series is able to efficiently compress fixed-size tag buffers, resulting in practical compression ratio between 2.5x and 4x. In most cases it is possible to store the compressed data in 63-bit Xarray values, resulting in no extra memory allocations.

Our measurements show that the proposed algorithm provides better compression than existing kernel compression algorithms (LZ4, LZO, LZ4HC, ZSTD) can offer.

To implement compression/decompression, we also extend <linux/bitmap.h> with methods to read/write bit values at arbitrary places in the map.

We refactor arch/arm64/mm/mteswap.c to support both the compressed (CONFIG_ARM64_MTE_COMP) and non-compressed case. For the former, in addition to tag compression, we move tag allocation from kmalloc() to separate kmem caches, providing greater locality and relaxing the alignment requirements.

v5:
- fixed comments by Andy Shevchenko, Catalin Marinas, and Yury Norov
- added support for 16K- and 64K pages
- more efficient bitmap_write() implementation

v4:
- fixed a bunch of comments by Andy Shevchenko and Yury Norov
- added Documentation/arch/arm64/mte-tag-compression.rst

v3:
- as suggested by Andy Shevchenko, use bitmap_get_value()/bitmap_set_value() written by Syed Nayyar Waris
- switched to unsigned long to reduce typecasts
- simplified the compression code

v2:
- as suggested by Yuri Norov, replace the poorly implemented struct bitq with <linux/bitmap.h>

Alexander Potapenko (4):
lib/test_bitmap: add tests for bitmap_{read,write}()
arm64: mte: implement CONFIG_ARM64_MTE_COMP
arm64: mte: add a test for MTE tags compression
arm64: mte: add compression support to mteswap.c

Syed Nayyar Waris (1):
lib/bitmap: add bitmap_{read,write}()

 Documentation/arch/arm64/index.rst            |   1 +
 .../arch/arm64/mte-tag-compression.rst        | 245 +++++++++
 arch/arm64/Kconfig                            |  21 +
 arch/arm64/include/asm/mtecomp.h              |  13 +
 arch/arm64/mm/Makefile                        |   7 +
 arch/arm64/mm/mtecomp.c                       | 467 ++++++++++++++++++
 arch/arm64/mm/mtecomp.h                       |  12 +
 arch/arm64/mm/mteswap.c                       |  20 +-
 arch/arm64/mm/mteswap.h                       |  12 +
 arch/arm64/mm/mteswap_comp.c                  |  60 +++
 arch/arm64/mm/mteswap_nocomp.c                |  38 ++
 arch/arm64/mm/test_mtecomp.c                  | 287 +++++++++++
 include/linux/bitmap.h                        |  68 +++
 lib/test_bitmap.c                             | 115 +++++
 14 files changed, 1355 insertions(+), 11 deletions(-)
 create mode 100644 Documentation/arch/arm64/mte-tag-compression.rst
 create mode 100644 arch/arm64/include/asm/mtecomp.h
 create mode 100644 arch/arm64/mm/mtecomp.c
 create mode 100644 arch/arm64/mm/mtecomp.h
 create mode 100644 arch/arm64/mm/mteswap.h
 create mode 100644 arch/arm64/mm/mteswap_comp.c
 create mode 100644 arch/arm64/mm/mteswap_nocomp.c
 create mode 100644 arch/arm64/mm/test_mtecomp.c
Signature · 1 line
2.42.0.515.g380fc7ccd1-goog
#1 lore raw

PATCH v5 1/5 lib/bitmap: add bitmap_{read,write}()

From: Syed Nayyar Waris <[email protected]>

The two new functions allow reading/writing values of length up to BITS_PER_LONG bits at arbitrary position in the bitmap.

The code was taken from "bitops: Introduce the for_each_set_clump macro" by Syed Nayyar Waris with a number of changes and simplifications:
- instead of using roundup(), which adds an unnecessary dependency on <linux/math.h>, we calculate space as BITS_PER_LONG-offset;
- indentation is reduced by not using else-clauses (suggested by checkpatch for bitmap_get_value());
- bitmap_get_value()/bitmap_set_value() are renamed to bitmap_read() and bitmap_write();
- some redundant computations are omitted.

---
This patch was previously called "lib/bitmap: add
bitmap_{set,get}_value()"
(https://lore.kernel.org/lkml/[email protected]/)

v5:
- Address comments by Yury Norov:
- updated code comments and patch title/description
- replace GENMASK(nbits - 1, 0) with BITMAP_LAST_WORD_MASK(nbits)
- more compact bitmap_write() implementation

v4:
- Address comments by Andy Shevchenko and Yury Norov:
- prevent passing values >= 64 to GENMASK()
- fix commit authorship
- change comments
- check for unlikely(nbits==0)
- drop unnecessary const declarations
- fix kernel-doc comments
- rename bitmap_{get,set}_value() to bitmap_{read,write}()

---
 include/linux/bitmap.h | 68 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 68 insertions(+)
include/linux/bitmap.h +68 -0
index 03644237e1efb..25998a3a4b2b9 100644
@@ -76,7 +76,11 @@ struct device;
  *  bitmap_to_arr32(buf, src, nbits)            Copy nbits from buf to u32[] dst
  *  bitmap_to_arr64(buf, src, nbits)            Copy nbits from buf to u64[] dst
  *  bitmap_get_value8(map, start)               Get 8bit value from map at start
+ *  bitmap_read(map, start, nbits)              Read an nbits-sized value from
+ *                                              map at start
  *  bitmap_set_value8(map, value, start)        Set 8bit value to map at start
+ *  bitmap_write(map, value, start, nbits)      Write an nbits-sized value to
+ *                                              map at start
  *
  * Note, bitmap_zero() and bitmap_fill() operate over the region of
  * unsigned longs, that is, bits behind bitmap till the unsigned long
@@ -583,6 +587,33 @@ static inline unsigned long bitmap_get_value8(const unsigned long *map,
 	return (map[index] >> offset) & 0xFF;
 }
 
+/**
+ * bitmap_read - read a value of n-bits from the memory region
+ * @map: address to the bitmap memory region
+ * @start: bit offset of the n-bit value
+ * @nbits: size of value in bits, up to BITS_PER_LONG
+ *
+ * Returns: value of nbits located at the @start bit offset within the @map
+ * memory region.
+ */
+static inline unsigned long bitmap_read(const unsigned long *map,
+					unsigned long start,
+					unsigned long nbits)
+{
+	size_t index = BIT_WORD(start);
+	unsigned long offset = start % BITS_PER_LONG;
+	unsigned long space = BITS_PER_LONG - offset;
+	unsigned long value_low, value_high;
+
+	if (unlikely(!nbits))
+		return 0;
+	if (space >= nbits)
+		return (map[index] >> offset) & GENMASK(nbits - 1, 0);
+	value_low = map[index] & BITMAP_FIRST_WORD_MASK(start);
+	value_high = map[index + 1] & BITMAP_LAST_WORD_MASK(start + nbits);
+	return (value_low >> offset) | (value_high << space);
+}
+
 /**
  * bitmap_set_value8 - set an 8-bit value within a memory region
  * @map: address to the bitmap memory region
@@ -599,6 +630,43 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value,
 	map[index] |= value << offset;
 }
 
+/**
+ * bitmap_write - write n-bit value within a memory region
+ * @map: address to the bitmap memory region
+ * @value: value to write, clamped to nbits
+ * @start: bit offset of the n-bit value
+ * @nbits: size of value in bits, up to BITS_PER_LONG.
+ *
+ * bitmap_write() behaves similarly to @nbits calls of assign_bit(), i.e. bits
+ * beyond @nbits are ignored:
+ *
+ *   for (bit = 0; bit < nbits; bit++)
+ *           assign_bit(start + bit, bitmap, val & BIT(bit));
+ */
+static inline void bitmap_write(unsigned long *map,
+				unsigned long value,
+				unsigned long start, unsigned long nbits)
+{
+	size_t index = BIT_WORD(start);
+	unsigned long offset = start % BITS_PER_LONG;
+	unsigned long space = BITS_PER_LONG - offset;
+	unsigned long mask;
+
+	if (unlikely(!nbits))
+		return;
+	mask = BITMAP_LAST_WORD_MASK(nbits);
+	value &= mask;
+	if (space >= nbits) {
+		map[index] &= ~(mask << offset);
+		map[index] |= value << offset;
+		return;
+	}
+	map[index] &= ~BITMAP_FIRST_WORD_MASK(start);
+	map[index] |= value << offset;
+	map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
+	map[index + 1] |= (value >> space);
+}
+
 #endif /* __ASSEMBLY__ */
 
 #endif /* __LINUX_BITMAP_H */
Signature · 1 line
2.42.0.515.g380fc7ccd1-goog
#2 lore raw

PATCH v5 2/5 lib/test_bitmap: add tests for bitmap_{read,write}()

In reply to Alexander Potapenko

Add basic tests ensuring that values can be added at arbitrary positions of the bitmap, including those spanning into the adjacent unsigned longs.

---
This patch was previously called
"lib/test_bitmap: add tests for bitmap_{set,get}_value()"
(https://lore.kernel.org/lkml/[email protected]/)
and
"lib/test_bitmap: add tests for bitmap_{set,get}_value_unaligned"
(https://lore.kernel.org/lkml/[email protected]/)

v5:
- update patch title
- address Yury Norov's comments:
- rename the test cases
- factor out test_bitmap_write_helper() to test writing over

     different background patterns;

- add a test case copying a nontrivial value bit-by-bit;
- drop volatile

v4:
- Address comments by Andy Shevchenko: added Reviewed-by: and a link to the previous discussion
- Address comments by Yury Norov:
- expand the bitmap to catch more corner cases
- add code testing that bitmap_set_value() does not touch adjacent bits
- add code testing the nbits==0 case
- rename bitmap_{get,set}_value() to bitmap_{read,write}()

v3:
- switch to using bitmap_{set,get}_value()
- change the expected bit pattern in test_set_get_value(), as the test was incorrectly assuming 0 is the LSB.

---
 lib/test_bitmap.c | 115 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 115 insertions(+)
lib/test_bitmap.c +115 -0
index 187f5b2db4cf1..ea66e39b29a4e 100644
@@ -71,6 +71,17 @@ __check_eq_uint(const char *srcfile, unsigned int line,
 	return true;
 }
 
+static bool __init
+__check_eq_ulong(const char *srcfile, unsigned int line,
+		 const unsigned long exp_ulong, unsigned long x)
+{
+	if (exp_ulong != x) {
+		pr_err("[%s:%u] expected %lu, got %lu\n",
+			srcfile, line, exp_ulong, x);
+		return false;
+	}
+	return true;
+}
 
 static bool __init
 __check_eq_bitmap(const char *srcfile, unsigned int line,
@@ -186,6 +197,7 @@ __check_eq_str(const char *srcfile, unsigned int line,
 	})
 
 #define expect_eq_uint(...)		__expect_eq(uint, ##__VA_ARGS__)
+#define expect_eq_ulong(...)		__expect_eq(ulong, ##__VA_ARGS__)
 #define expect_eq_bitmap(...)		__expect_eq(bitmap, ##__VA_ARGS__)
 #define expect_eq_pbl(...)		__expect_eq(pbl, ##__VA_ARGS__)
 #define expect_eq_u32_array(...)	__expect_eq(u32_array, ##__VA_ARGS__)
@@ -1222,6 +1234,108 @@ static void __init test_bitmap_const_eval(void)
 	BUILD_BUG_ON(~var != ~BIT(25));
 }
 
+/*
+ * Test bitmap should be big enough to include the cases when start is not in
+ * the first word, and start+nbits lands in the following word.
+ */
+#define TEST_BIT_LEN (1000)
+#define TEST_BYTE_LEN (BITS_TO_BYTES(TEST_BIT_LEN))
+
+/*
+ * Helper function to test bitmap_write() overwriting the chosen byte pattern.
+ */
+static void __init test_bitmap_write_helper(unsigned char pattern)
+{
+	DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
+	DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN);
+	unsigned long w, r, bit;
+	int i, n, nbits;
+
+	/*
+	 * Check that setting a single bit does not accidentally touch the
+	 * adjacent bits.
+	 */
+	for (i = 0; i < TEST_BIT_LEN; i++) {
+		/*
+		 * A 0b10101010 pattern to catch both 0s replaced to 1s
+		 * and vice versa.
+		 */
+		memset(bitmap, pattern, TEST_BYTE_LEN);
+		memset(exp_bitmap, pattern, TEST_BYTE_LEN);
+		for (bit = 0; bit <= 1; bit++) {
+			bitmap_write(bitmap, bit, i, 1);
+			__assign_bit(i, exp_bitmap, bit);
+			expect_eq_bitmap(exp_bitmap, bitmap,
+					 TEST_BIT_LEN);
+		}
+	}
+
+	/* Ensure setting 0 bits does not change anything. */
+	memset(bitmap, pattern, TEST_BYTE_LEN);
+	memset(exp_bitmap, pattern, TEST_BYTE_LEN);
+	for (i = 0; i < TEST_BIT_LEN; i++) {
+		bitmap_write(bitmap, ~0UL, i, 0);
+		expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN);
+	}
+
+	for (nbits = BITS_PER_LONG; nbits >= 1; nbits--) {
+		w = 0xdeadbeefdeadbeefUL >> (BITS_PER_LONG - nbits);
+		for (i = 0; i <= TEST_BIT_LEN - nbits; i++) {
+			memset(bitmap, pattern, TEST_BYTE_LEN);
+			memset(exp_bitmap, pattern, TEST_BYTE_LEN);
+			for (n = 0; n < nbits; n++)
+				__assign_bit(i + n, exp_bitmap, w & BIT(n));
+			bitmap_write(bitmap, w, i, nbits);
+			expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN);
+			r = bitmap_read(bitmap, i, nbits);
+			expect_eq_ulong(r, w);
+		}
+	}
+}
+
+static void __init test_bitmap_read_write(void)
+{
+	unsigned char pattern[3] = {0x00, 0xaa, 0xff};
+	DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
+	unsigned long zero_bits = 0;
+	unsigned long val;
+	int i, pi;
+
+	/*
+	 * Setting/getting zero bytes should not crash the kernel.
+	 * READ_ONCE() prevents constant folding.
+	 */
+	bitmap_write(NULL, 0, 0, READ_ONCE(zero_bits));
+	val = bitmap_read(NULL, 0, READ_ONCE(zero_bits));
+	expect_eq_ulong(0, val);
+
+	/*
+	 * Ensure that bitmap_read() reads the same value that was previously
+	 * written, and two consequent values are correctly merged.
+	 * The resulting bit pattern is asymmetric to rule out possible issues
+	 * with bit numeration order.
+	 */
+	for (i = 0; i < TEST_BIT_LEN - 7; i++) {
+		bitmap_zero(bitmap, TEST_BIT_LEN);
+
+		bitmap_write(bitmap, 0b10101UL, i, 5);
+		val = bitmap_read(bitmap, i, 5);
+		expect_eq_ulong(0b10101UL, val);
+
+		bitmap_write(bitmap, 0b101UL, i + 5, 3);
+		val = bitmap_read(bitmap, i + 5, 3);
+		expect_eq_ulong(0b101UL, val);
+
+		val = bitmap_read(bitmap, i, 8);
+		expect_eq_ulong(0b10110101UL, val);
+	}
+
+	for (pi = 0; pi < sizeof(pattern); pi++)
+		test_bitmap_write_helper(pattern[pi]);
+}
+#undef TEST_BYTE_LEN
+#undef TEST_BIT_LEN
+
 static void __init selftest(void)
 {
 	test_zero_clear();
@@ -1237,6 +1351,7 @@ static void __init selftest(void)
 	test_bitmap_cut();
 	test_bitmap_print_buf();
 	test_bitmap_const_eval();
+	test_bitmap_read_write();
 
 	test_find_nth_bit();
 	test_for_each_set_bit();
Signature · 1 line
2.42.0.515.g380fc7ccd1-goog
#3 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

lib/test_bitmap.c static void __init test_bitmap_const_eval(void) · line 1241

Quoted 6 lines
lib/test_bitmap.c +5 -0
+/*
+ * Test bitmap should be big enough to include the cases when start is not in
+ * the first word, and start+nbits lands in the following word.
+ */
+#define TEST_BIT_LEN (1000)

Dunno why this didn't fire previously, but CONFIG_CPU_BIG_ENDIAN=y kernel reports mismatches here, presumably because the last quad word ends up partially initialized.
The easiest fix is to make TEST_BIT_LEN divisible by 64 (e.g. 1024)

#4 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

On Mon, Sep 25, 2023 at 02:16:37PM +0200, Alexander Potapenko wrote:

...

Quoted 9 lines

lib/test_bitmap.c static void __init test_bitmap_const_eval(void) · line 1241

Quoted 5 lines
lib/test_bitmap.c +5 -0
+/*
+ * Test bitmap should be big enough to include the cases when start is not in
+ * the first word, and start+nbits lands in the following word.
+ */
+#define TEST_BIT_LEN (1000)

Dunno why this didn't fire previously, but CONFIG_CPU_BIG_ENDIAN=y kernel reports mismatches here, presumably because the last quad word ends up partially initialized.

Hmm... But if designed and used correctly it shouldn't be the issue, and 1000, I believe, is carefully chosen to be specifically not dividable by pow-of-2 value.

Quoted 1 line

The easiest fix is to make TEST_BIT_LEN divisible by 64 (e.g. 1024)

Wouldn't it hide the real issue somewhere?

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#5 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

Quoted 15 lines · Andy Shevchenko

On Mon, Sep 25, 2023 at 02:16:37PM +0200, Alexander Potapenko wrote:

...

Quoted 9 lines

lib/test_bitmap.c static void __init test_bitmap_const_eval(void) · line 1241

Quoted 5 lines
lib/test_bitmap.c +5 -0
+/*
+ * Test bitmap should be big enough to include the cases when start is not in
+ * the first word, and start+nbits lands in the following word.
+ */
+#define TEST_BIT_LEN (1000)

Dunno why this didn't fire previously, but CONFIG_CPU_BIG_ENDIAN=y kernel reports mismatches here, presumably because the last quad word ends up partially initialized.

Quoted 4 lines

Hmm... But if designed and used correctly it shouldn't be the issue, and 1000, I believe, is carefully chosen to be specifically not dividable by pow-of-2 value.

The problem manifests already right after initialization:

static void __init test_bit_len_1000(void)

{
        DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
        DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN);
        memset(bitmap, 0x00, TEST_BYTE_LEN);
        memset(exp_bitmap, 0x00, TEST_BYTE_LEN);
        expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN);
}

...

[   29.601614][    T1] test_bitmap: [lib/test_bitmap.c:1250] bitmaps

contents differ: expected "960-963,966-967,969,971-973,976,978-979,981", got "963"
...

So it's probably expect_eq_bitmap() that is incorrectly rounding up the bitmap length somewhere (or maybe it is not supposed to be used for non-aligned bitmaps?)
Looking further...

#6 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

Quoted 25 lines · Alexander Potapenko
Quoted 15 lines · Andy Shevchenko

On Mon, Sep 25, 2023 at 02:16:37PM +0200, Alexander Potapenko wrote:

...

Quoted 9 lines

lib/test_bitmap.c static void __init test_bitmap_const_eval(void) · line 1241

Quoted 5 lines
lib/test_bitmap.c +5 -0
+/*
+ * Test bitmap should be big enough to include the cases when start is not in
+ * the first word, and start+nbits lands in the following word.
+ */
+#define TEST_BIT_LEN (1000)

Dunno why this didn't fire previously, but CONFIG_CPU_BIG_ENDIAN=y kernel reports mismatches here, presumably because the last quad word ends up partially initialized.

Quoted 4 lines

Hmm... But if designed and used correctly it shouldn't be the issue, and 1000, I believe, is carefully chosen to be specifically not dividable by pow-of-2 value.

The problem manifests already right after initialization:

Quoted 8 lines

static void __init test_bit_len_1000(void)

{
        DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
        DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN);
        memset(bitmap, 0x00, TEST_BYTE_LEN);
        memset(exp_bitmap, 0x00, TEST_BYTE_LEN);
        expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN);
}

The problem is that there's no direct analog of memset() that can be used to initialize bitmaps on both BE and LE systems. bitmap_zero() and bitmap_set() work by rounding up the bitmap size to BITS_TO_LONGS(nbits), but there's no bitmap_memset() that would do the same for an arbitrary byte pattern.
We could call memset(..., ..., BITS_TO_LONGS(TEST_BIT_LEN)), but that would be similar to declaring a bigger bitmap and not testing the last 24 bits.

Overall, unless allocating and initializing bitmaps with size divisible by sizeof(long), most of bitmap.c is undefined behavior, so I don't think it makes much sense to specifically test this case here (given that we do not extend bitmap_equal() in the patch set).

maintainer
#7 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

Quoted 35 lines · Alexander Potapenko
Quoted 25 lines · Alexander Potapenko
Quoted 15 lines · Andy Shevchenko

On Mon, Sep 25, 2023 at 02:16:37PM +0200, Alexander Potapenko wrote:

...

Quoted 9 lines

lib/test_bitmap.c static void __init test_bitmap_const_eval(void) · line 1241

Quoted 5 lines
lib/test_bitmap.c +5 -0
+/*
+ * Test bitmap should be big enough to include the cases when start is not in
+ * the first word, and start+nbits lands in the following word.
+ */
+#define TEST_BIT_LEN (1000)

Dunno why this didn't fire previously, but CONFIG_CPU_BIG_ENDIAN=y kernel reports mismatches here, presumably because the last quad word ends up partially initialized.

Quoted 4 lines

Hmm... But if designed and used correctly it shouldn't be the issue, and 1000, I believe, is carefully chosen to be specifically not dividable by pow-of-2 value.

The problem manifests already right after initialization:

Quoted 8 lines

static void __init test_bit_len_1000(void)

{
        DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
        DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN);
        memset(bitmap, 0x00, TEST_BYTE_LEN);
        memset(exp_bitmap, 0x00, TEST_BYTE_LEN);
        expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN);
}
Quoted 2 lines

The problem is that there's no direct analog of memset() that can be used to initialize bitmaps on both BE and LE systems.

memset fills an array of chars with the same value. In bitmap world we operate on array of bits, and there are only 2 possible values: '0' and '1'. For those we've got bitmap_zero() and bitmap_fill().

Quoted 6 lines

bitmap_zero() and bitmap_set() work by rounding up the bitmap size to BITS_TO_LONGS(nbits), but there's no bitmap_memset() that would do the same for an arbitrary byte pattern.
We could call memset(..., ..., BITS_TO_LONGS(TEST_BIT_LEN)), but that would be similar to declaring a bigger bitmap and not testing the last 24 bits.

No, you couldn't. On the test level, bitmap should be considered as a black box. memset()'ing it may (and did) damage internal structure.

If you have some pattern in mind, you can use bitmap_parselist(). For example, you can set every 2nd bit in your bitmap like this:

        bitmap_parselist("all:1/2", bitmap, 1000);

Check for almost 100 examples of bitmap_parselist usage in the test for bitmap_parselist in the same file.

Quoted 4 lines

Overall, unless allocating and initializing bitmaps with size divisible by sizeof(long), most of bitmap.c is undefined behavior, so I don't think it makes much sense to specifically test this case here (given that we do not extend bitmap_equal() in the patch set).

This is wrong statement. People spent huge amount of time making bitmap API working well for all combinations of lengths and endiannesses, including Andy and me.

NAK for this and for ignoring my other comment to v4.

#8 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

Quoted 51 lines · Yury Norov
Quoted 35 lines · Alexander Potapenko
Quoted 25 lines · Alexander Potapenko
Quoted 15 lines · Andy Shevchenko

On Mon, Sep 25, 2023 at 02:16:37PM +0200, Alexander Potapenko wrote:

...

Quoted 9 lines

lib/test_bitmap.c static void __init test_bitmap_const_eval(void) · line 1241

Quoted 5 lines
lib/test_bitmap.c +5 -0
+/*
+ * Test bitmap should be big enough to include the cases when start is not in
+ * the first word, and start+nbits lands in the following word.
+ */
+#define TEST_BIT_LEN (1000)

Dunno why this didn't fire previously, but CONFIG_CPU_BIG_ENDIAN=y kernel reports mismatches here, presumably because the last quad word ends up partially initialized.

Quoted 4 lines

Hmm... But if designed and used correctly it shouldn't be the issue, and 1000, I believe, is carefully chosen to be specifically not dividable by pow-of-2 value.

The problem manifests already right after initialization:

Quoted 8 lines

static void __init test_bit_len_1000(void)

{
        DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
        DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN);
        memset(bitmap, 0x00, TEST_BYTE_LEN);
        memset(exp_bitmap, 0x00, TEST_BYTE_LEN);
        expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN);
}
Quoted 2 lines

The problem is that there's no direct analog of memset() that can be used to initialize bitmaps on both BE and LE systems.

memset fills an array of chars with the same value. In bitmap world we operate on array of bits, and there are only 2 possible values: '0' and '1'. For those we've got bitmap_zero() and bitmap_fill().

Quoted 6 lines

bitmap_zero() and bitmap_set() work by rounding up the bitmap size to BITS_TO_LONGS(nbits), but there's no bitmap_memset() that would do the same for an arbitrary byte pattern.
We could call memset(..., ..., BITS_TO_LONGS(TEST_BIT_LEN)), but that would be similar to declaring a bigger bitmap and not testing the last 24 bits.

Quoted 2 lines

No, you couldn't. On the test level, bitmap should be considered as a black box. memset()'ing it may (and did) damage internal structure.

You are right about this. bitmap_zero() and bitmap_fill() are calling memset() under the hood, but I shouldn't have assumed doing raw memset is safe.
Unfortunately lib/test_bitmap.c does a bunch of memsets already, which probably led to the confusion.

Quoted 7 lines

If you have some pattern in mind, you can use bitmap_parselist(). For example, you can set every 2nd bit in your bitmap like this:

        bitmap_parselist("all:1/2", bitmap, 1000);

Check for almost 100 examples of bitmap_parselist usage in the test for bitmap_parselist in the same file.

Thanks! This solves my problem.
I am planning to use an intermediate bitmap to avoid parsing the pattern multiple times.

Quoted 9 lines
Quoted 5 lines

Overall, unless allocating and initializing bitmaps with size divisible by sizeof(long), most of bitmap.c is undefined behavior, so I don't think it makes much sense to specifically test this case here (given that we do not extend bitmap_equal() in the patch set).

This is wrong statement. People spent huge amount of time making bitmap API working well for all combinations of lengths and endiannesses, including Andy and me.

Please accept my apologies for that, I didn't mean to insult you, Andy, or anyone else.
My understanding of the comment at the top of lib/bitmap.c was that the bitmap API is expected to work in the presence of uninitialized values, which is actually not what the comment says. bitmap_zero() and such do ensure that none of the tail bytes remain uninitialized, so we are safe as long as those functions are used.

Quoted 2 lines

NAK for this and for ignoring my other comment to v4.

If you are talking about this comment:
https://lore.kernel.org/lkml/ZQ2WboApqYyEkjjG@yury-ThinkPad/, I was going to incorporate it in v6 (as it was sent after I published v5). I am fine with not mandating the return value for reading/writing zero bytes.

#9 lore raw

RE: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

In reply to Alexander Potapenko

...

Quoted 4 lines

Overall, unless allocating and initializing bitmaps with size divisible by sizeof(long), most of bitmap.c is undefined behavior, so I don't think it makes much sense to specifically test this case here (given that we do not extend bitmap_equal() in the patch set).

Bitmaps are arrays of unsigned long.
Using any of the APIs on anything else is a bug.
So it is always wrong to try to initialise 'a number of bytes'. The size used in the definition need not be a multiple of 8 (on 64bit) but the allocated data is always a multiple of 8.

Any calls to the functions that have a cast of the bitmap parameter are likely to be buggy.
And yes, there are loads of them, and many are buggy.

On LE you mostly get away with shorter memory allocations. But still get errors when trying to do locked operations on misaligned addresses.

David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)

#10 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

Quoted 13 lines · David Laight

...

Quoted 4 lines

Overall, unless allocating and initializing bitmaps with size divisible by sizeof(long), most of bitmap.c is undefined behavior, so I don't think it makes much sense to specifically test this case here (given that we do not extend bitmap_equal() in the patch set).

Bitmaps are arrays of unsigned long.
Using any of the APIs on anything else is a bug.
So it is always wrong to try to initialise 'a number of bytes'. The size used in the definition need not be a multiple of 8 (on 64bit) but the allocated data is always a multiple of 8.

Quoted 3 lines

Any calls to the functions that have a cast of the bitmap parameter are likely to be buggy.
And yes, there are loads of them, and many are buggy.

I got rid of the casts in the bitmap test, but they remain in mtecomp.c, where 16-, 32-, 64-byte buffers allocated by kmem_cache_alloc() are treated as bitmaps:
https://lore.kernel.org/linux-arm-kernel/[email protected]/T/#mdb0d636d2d357f8ffe6ac79cef1145df3440f659

Having them allocated by bitmap_alloc() won't work, because on Android bitmap_alloc() will allocate the buffers from the kmalloc-64 cache, defeating the purpose of the compression.

Would it be better to extend the bitmap.h API so that it is possible to allocate from a kmem cache (which would in turn require bitmap_kmem_cache_create() to ensure the alignment requirements)?

Quoted 9 lines

On LE you mostly get away with shorter memory allocations. But still get errors when trying to do locked operations on misaligned addresses.

David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)

--
Alexander Potapenko
Software Engineer

Google Germany GmbH
Erika-Mann-Straße, 33
80636 München

Geschäftsführer: Paul Manicle, Liana Sebastian
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg

A message that is not in the archive (sent off-list or not yet received): CAAH8bW-9ZWB=i0RWAWBXguOkguLHZGp7fLg7An73NqFnVmtgFw@mail.gmail.com

#12 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

Quoted 37 lines · Yury Norov
Quoted 24 lines · Alexander Potapenko
Quoted 13 lines · David Laight

...

Quoted 4 lines

Overall, unless allocating and initializing bitmaps with size divisible by sizeof(long), most of bitmap.c is undefined behavior, so I don't think it makes much sense to specifically test this case here (given that we do not extend bitmap_equal() in the patch set).

Bitmaps are arrays of unsigned long.
Using any of the APIs on anything else is a bug.
So it is always wrong to try to initialise 'a number of bytes'. The size used in the definition need not be a multiple of 8 (on 64bit) but the allocated data is always a multiple of 8.

Quoted 3 lines

Any calls to the functions that have a cast of the bitmap parameter are likely to be buggy.
And yes, there are loads of them, and many are buggy.

I got rid of the casts in the bitmap test, but they remain in mtecomp.c, where 16-, 32-, 64-byte buffers allocated by kmem_cache_alloc() are treated as bitmaps:
https://lore.kernel.org/linux-arm-kernel/[email protected]/T/#mdb0d636d2d357f8ffe6ac79cef1145df3440f659

Quoted 7 lines

Having them allocated by bitmap_alloc() won't work, because on Android bitmap_alloc() will allocate the buffers from the kmalloc-64 cache, defeating the purpose of the compression.

Would it be better to extend the bitmap.h API so that it is possible to allocate from a kmem cache (which would in turn require bitmap_kmem_cache_create() to ensure the alignment requirements)?

Quoted 5 lines

So all that is wrong then. Bad on me, I'd spend more time looking into your driver code...

We already have bitmap_(from,to)_u(64,32),
And you can use them. For 16-bit you have to add helpers yourself. But it's not a rocket science.

So e.g. for compressing something into a 16-byte buffer using bitmaps I'd need to:

1) Allocate the buffer: buf = kmem_cache_alloc(...)
2) Allocate the bitmap: bitmap = bitmap_alloc(16*8, ...)
3) Fill the bitmap: mte_compress_to_buf(..., bitmap, 16)
4) Copy the bitmap contents to the buffer: bitmap_to_arr64(buf, bitmap, 16*8)
5) Deallocate the bitmap: bitmap_free(bitmap)

instead of:

buf = kmem_cache_alloc(...) mte_compress_to_buf(..., (unsigned long *)buf, 16)

, correct?

Given that the buffer contents are opaque and its size is aligned on 8 bytes, could it be possible to somehow adopt the buf pointer instead?

Quoted 1 line

I'm AFK at the moment. I'll take a close look at your machinery at the weekend.

Thanks and take your time!

maintainer
#13 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

Quoted 55 lines · Alexander Potapenko
Quoted 37 lines · Yury Norov
Quoted 24 lines · Alexander Potapenko
Quoted 13 lines · David Laight

...

Quoted 4 lines

Overall, unless allocating and initializing bitmaps with size divisible by sizeof(long), most of bitmap.c is undefined behavior, so I don't think it makes much sense to specifically test this case here (given that we do not extend bitmap_equal() in the patch set).

Bitmaps are arrays of unsigned long.
Using any of the APIs on anything else is a bug.
So it is always wrong to try to initialise 'a number of bytes'. The size used in the definition need not be a multiple of 8 (on 64bit) but the allocated data is always a multiple of 8.

Quoted 3 lines

Any calls to the functions that have a cast of the bitmap parameter are likely to be buggy.
And yes, there are loads of them, and many are buggy.

I got rid of the casts in the bitmap test, but they remain in mtecomp.c, where 16-, 32-, 64-byte buffers allocated by kmem_cache_alloc() are treated as bitmaps:
https://lore.kernel.org/linux-arm-kernel/[email protected]/T/#mdb0d636d2d357f8ffe6ac79cef1145df3440f659

Quoted 7 lines

Having them allocated by bitmap_alloc() won't work, because on Android bitmap_alloc() will allocate the buffers from the kmalloc-64 cache, defeating the purpose of the compression.

Would it be better to extend the bitmap.h API so that it is possible to allocate from a kmem cache (which would in turn require bitmap_kmem_cache_create() to ensure the alignment requirements)?

Quoted 5 lines

So all that is wrong then. Bad on me, I'd spend more time looking into your driver code...

We already have bitmap_(from,to)_u(64,32),
And you can use them. For 16-bit you have to add helpers yourself. But it's not a rocket science.

So e.g. for compressing something into a 16-byte buffer using bitmaps I'd need to:

1) Allocate the buffer: buf = kmem_cache_alloc(...)
2) Allocate the bitmap: bitmap = bitmap_alloc(16*8, ...)
3) Fill the bitmap: mte_compress_to_buf(..., bitmap, 16)
4) Copy the bitmap contents to the buffer: bitmap_to_arr64(buf, bitmap, 16*8)
5) Deallocate the bitmap: bitmap_free(bitmap)

instead of:

Quoted 8 lines

buf = kmem_cache_alloc(...) mte_compress_to_buf(..., (unsigned long *)buf, 16)

, correct?

Given that the buffer contents are opaque and its size is aligned on 8 bytes, could it be possible to somehow adopt the buf pointer instead?

I didn't find an explicit typecasting where you're using mte_compress_to_buf(), but now after hard 2nd look I see...

Firstly, now that in the documentation you are explicitly describing the return value of mte_compress() as 64-bit frame, the right way to go would be declaring the function as: u64 mte_compress(u8 *tags).

And the general pattern should be like this:

  unsigned long mte_compress(u8 *tags)
  {
          DECLARE_BITMAP(tmp, MTECOMP_CACHES_MAXBITS);
          void *storage;
          ...
          if (alloc_size < MTE_PAGE_TAG_STORAGE) {
                  storage = kmem_cache_alloc(cache, GFP_KERNEL);
                  mte_compress_to_buf(r_len, r_tags, r_sizes, tmp, alloc_size);
                  switch (alloc_size) {
                  case 16:
                          bitmap_to_arr16(storage, tmp, 16);
                          break;
                  case 32:
                          bitmap_to_arr32(storage, tmp, 32);
                          break;
                  case 64:
                          bitmap_to_arr64(storage, tmp, 64);
                          break;
                  default:
                          pr_err("error\n");
                  }
                  result = ((u64)storage | cache_id) & MTE_HANDLE_MASK;
                  goto ret;
          }
          ...

}

Yeah, it looks cumbersome, but this is the right way to go if you need a reliable BE-compatible driver. I think it will be less scary if you wrap the switch with a helper, and/or move it inside mte_compress_to_buf(), so that the mte_compress will stay unchanged.

Anyways, hope the above helped.

Thanks,
Yury

#14 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

Quoted 23 lines · Yury Norov
Quoted 12 lines · Alexander Potapenko

So e.g. for compressing something into a 16-byte buffer using bitmaps I'd need to:

1) Allocate the buffer: buf = kmem_cache_alloc(...)
2) Allocate the bitmap: bitmap = bitmap_alloc(16*8, ...)
3) Fill the bitmap: mte_compress_to_buf(..., bitmap, 16)
4) Copy the bitmap contents to the buffer: bitmap_to_arr64(buf, bitmap, 16*8)
5) Deallocate the bitmap: bitmap_free(bitmap)

instead of:

Quoted 8 lines

buf = kmem_cache_alloc(...) mte_compress_to_buf(..., (unsigned long *)buf, 16)

, correct?

Given that the buffer contents are opaque and its size is aligned on 8 bytes, could it be possible to somehow adopt the buf pointer instead?

Quoted 6 lines

I didn't find an explicit typecasting where you're using mte_compress_to_buf(), but now after hard 2nd look I see...

Firstly, now that in the documentation you are explicitly describing the return value of mte_compress() as 64-bit frame, the right way to go would be declaring the function as: u64 mte_compress(u8 *tags).

Ack.

Quoted 11 lines

And the general pattern should be like this:

  unsigned long mte_compress(u8 *tags)
  {
          DECLARE_BITMAP(tmp, MTECOMP_CACHES_MAXBITS);
          void *storage;
          ...
          if (alloc_size < MTE_PAGE_TAG_STORAGE) {
                  storage = kmem_cache_alloc(cache, GFP_KERNEL);
                  mte_compress_to_buf(r_len, r_tags, r_sizes, tmp, alloc_size);
Quoted 3 lines
                  switch (alloc_size) {
                  case 16:
                          bitmap_to_arr16(storage, tmp, 16);

I might be missing something, but why do we need the switch at all? The buffers we are allocating always contain a whole number of u64's - cannot we just always call bitmap_to_arr64()?

Note that for cases where alloc_size is > 8 we never make any assumptions about the contents of @storage, and don't care much about the byte order as long as swap decompression is done with the same endianness (which is always the case).
(The case where alloc_size==8 is somewhat special, and needs more accurate handling, because we do make assumptions about the bit layout there).

Quoted 14 lines
                          break;
                  case 32:
                          bitmap_to_arr32(storage, tmp, 32);
                          break;
                  case 64:
                          bitmap_to_arr64(storage, tmp, 64);
                          break;
                  default:
                          pr_err("error\n");
                  }
                  result = ((u64)storage | cache_id) & MTE_HANDLE_MASK;
                  goto ret;
          }
          ...
Quoted 4 lines

}

Yeah, it looks cumbersome, but this is the right way to go if you need a reliable BE-compatible driver.

What is the BE compatibility problem that you are anticipating here?

The issue that came up during testing was that on systems with different endianness we cannot treat unaligned buffers as bitmaps, because bitmap_write() might be touching memory past the allocation size.
I agree therefore with the general approach of encapsulating all bitmap operations in bitmap.h and hiding the implementation details behind the API.
But in this particular case it seems to complicate the otherwise trivial application of bitmap_read()/bitmap_write() to an external buffer with guaranteed 64-bit alignment: we'll end up allocating this temporary bitmap and doing a hard-to-optimize memcpy() between it and the final storage.

A straightforward solution for this would be to fork u64* versions of bitmap_read()/bitmap_write() implementations in mtecomp.c and apply them to u64* buffers allocated in that file.
This would remove the need for the temporary bitmap (because there's no encapsulation that mandates using bitmap.h now) and the extra memcpy().
But I don't like this either, because forking code that exists in headers is just wrong.

Quoted 8 lines

I think it will be less scary if you wrap
the switch with a helper, and/or move it inside mte_compress_to_buf(), so that the mte_compress will stay unchanged.

Anyways, hope the above helped.

Thanks,
Yury

--
Alexander Potapenko
Software Engineer

Google Germany GmbH
Erika-Mann-Straße, 33
80636 München

Geschäftsführer: Paul Manicle, Liana Sebastian
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg

maintainer
#15 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

Quoted 52 lines · Alexander Potapenko
Quoted 23 lines · Yury Norov
Quoted 12 lines · Alexander Potapenko

So e.g. for compressing something into a 16-byte buffer using bitmaps I'd need to:

1) Allocate the buffer: buf = kmem_cache_alloc(...)
2) Allocate the bitmap: bitmap = bitmap_alloc(16*8, ...)
3) Fill the bitmap: mte_compress_to_buf(..., bitmap, 16)
4) Copy the bitmap contents to the buffer: bitmap_to_arr64(buf, bitmap, 16*8)
5) Deallocate the bitmap: bitmap_free(bitmap)

instead of:

Quoted 8 lines

buf = kmem_cache_alloc(...) mte_compress_to_buf(..., (unsigned long *)buf, 16)

, correct?

Given that the buffer contents are opaque and its size is aligned on 8 bytes, could it be possible to somehow adopt the buf pointer instead?

Quoted 6 lines

I didn't find an explicit typecasting where you're using mte_compress_to_buf(), but now after hard 2nd look I see...

Firstly, now that in the documentation you are explicitly describing the return value of mte_compress() as 64-bit frame, the right way to go would be declaring the function as: u64 mte_compress(u8 *tags).

Ack.

Quoted 11 lines

And the general pattern should be like this:

  unsigned long mte_compress(u8 *tags)
  {
          DECLARE_BITMAP(tmp, MTECOMP_CACHES_MAXBITS);
          void *storage;
          ...
          if (alloc_size < MTE_PAGE_TAG_STORAGE) {
                  storage = kmem_cache_alloc(cache, GFP_KERNEL);
                  mte_compress_to_buf(r_len, r_tags, r_sizes, tmp, alloc_size);
Quoted 3 lines
                  switch (alloc_size) {
                  case 16:
                          bitmap_to_arr16(storage, tmp, 16);

I might be missing something, but why do we need the switch at all? The buffers we are allocating always contain a whole number of u64's - cannot we just always call bitmap_to_arr64()?

Quoted 7 lines

Note that for cases where alloc_size is > 8 we never make any assumptions about the contents of @storage, and don't care much about the byte order as long as swap decompression is done with the same endianness (which is always the case).
(The case where alloc_size==8 is somewhat special, and needs more accurate handling, because we do make assumptions about the bit layout there).

So, this is my fault, and I'm really sorry. I read that 16-byte as 16-bit, and mistaken everything else. Please scratch the above.

If you allocate word-aligned memory, and it's a multiple of words, which is your case, and access it only using bitmap API like bitmap_read/write, everything should be fine.

Sorry again.

#16 lore raw

Re: [PATCH v5 2/5] lib/test_bitmap: add tests for bitmap_{read,write}()

Quoted 62 lines · Yury Norov
Quoted 52 lines · Alexander Potapenko
Quoted 23 lines · Yury Norov
Quoted 12 lines · Alexander Potapenko

So e.g. for compressing something into a 16-byte buffer using bitmaps I'd need to:

1) Allocate the buffer: buf = kmem_cache_alloc(...)
2) Allocate the bitmap: bitmap = bitmap_alloc(16*8, ...)
3) Fill the bitmap: mte_compress_to_buf(..., bitmap, 16)
4) Copy the bitmap contents to the buffer: bitmap_to_arr64(buf, bitmap, 16*8)
5) Deallocate the bitmap: bitmap_free(bitmap)

instead of:

Quoted 8 lines

buf = kmem_cache_alloc(...) mte_compress_to_buf(..., (unsigned long *)buf, 16)

, correct?

Given that the buffer contents are opaque and its size is aligned on 8 bytes, could it be possible to somehow adopt the buf pointer instead?

Quoted 6 lines

I didn't find an explicit typecasting where you're using mte_compress_to_buf(), but now after hard 2nd look I see...

Firstly, now that in the documentation you are explicitly describing the return value of mte_compress() as 64-bit frame, the right way to go would be declaring the function as: u64 mte_compress(u8 *tags).

Ack.

Quoted 11 lines

And the general pattern should be like this:

  unsigned long mte_compress(u8 *tags)
  {
          DECLARE_BITMAP(tmp, MTECOMP_CACHES_MAXBITS);
          void *storage;
          ...
          if (alloc_size < MTE_PAGE_TAG_STORAGE) {
                  storage = kmem_cache_alloc(cache, GFP_KERNEL);
                  mte_compress_to_buf(r_len, r_tags, r_sizes, tmp, alloc_size);
Quoted 3 lines
                  switch (alloc_size) {
                  case 16:
                          bitmap_to_arr16(storage, tmp, 16);

I might be missing something, but why do we need the switch at all? The buffers we are allocating always contain a whole number of u64's - cannot we just always call bitmap_to_arr64()?

Quoted 7 lines

Note that for cases where alloc_size is > 8 we never make any assumptions about the contents of @storage, and don't care much about the byte order as long as swap decompression is done with the same endianness (which is always the case).
(The case where alloc_size==8 is somewhat special, and needs more accurate handling, because we do make assumptions about the bit layout there).

Quoted 6 lines

So, this is my fault, and I'm really sorry. I read that 16-byte as 16-bit, and mistaken everything else. Please scratch the above.

If you allocate word-aligned memory, and it's a multiple of words, which is your case, and access it only using bitmap API like bitmap_read/write, everything should be fine.

Ok, fine, I'll stick to the current implementation then.

#17 lore raw

PATCH v5 3/5 arm64: mte: implement CONFIG_ARM64_MTE_COMP

In reply to Alexander Potapenko

The config implements the algorithm compressing memory tags for ARM MTE during swapping.

The algorithm is based on RLE and specifically targets buffers of tags corresponding to a single page. In the common case a buffer can be compressed into 63 bits, making it possible to store it without additional memory allocation.

---
v5:
- make code PAGE_SIZE-agnostic, remove hardcoded constants, updated the docs
- implement debugfs interface
- Address comments by Andy Shevchenko:
- update description of mtecomp.c
- remove redundant assignments, simplify mte_tags_to_ranges()
- various code simplifications
- introduce mtecomp.h
- add :export: to Documentation/arch/arm64/mte-tag-compression.rst

v4:
- Addressed comments by Andy Shevchenko:
- expanded "MTE" to "Memory Tagging Extension" in Kconfig
- fixed kernel-doc comments, moved them to C source
- changed variables to unsigned where applicable
- some code simplifications, fewer unnecessary assignments
- added the mte_largest_idx_bits() helper
- added namespace prefixes to all functions
- added missing headers (but removed bits.h)
- Addressed comments by Yury Norov:
- removed test-only functions from mtecomp.h
- dropped the algoritm name (all functions are now prefixed with "mte")
- added more comments
- got rid of MTE_RANGES_INLINE
- renamed bitmap_{get,set}_value() to bitmap_{read,write}()
- moved the big comment explaining the algorithm to Documentation/arch/arm64/mte-tag-compression.rst, expanded it, add a link to it from Documentation/arch/arm64/index.rst
- removed hardcoded ranges from mte_alloc_size()/mte_size_to_ranges()

v3:
- Addressed comments by Andy Shevchenko:
- use bitmap_{set,get}_value() writte by Syed Nayyar Waris
- switched to unsigned long everywhere (fewer casts)
- simplified the code, removed redundant checks
- dropped ea0_compress_inline()
- added bit size constants and helpers to access the bitmap
- explicitly initialize all compressed sizes in ea0_compress_to_buf()
- initialize all handle bits

v2:
- as suggested by Yury Norov, switched from struct bitq (which is not needed anymore) to <linux/bitmap.h>
- add missing symbol exports

---
 Documentation/arch/arm64/index.rst            |   1 +
 .../arch/arm64/mte-tag-compression.rst        | 245 +++++++++
 arch/arm64/Kconfig                            |  11 +
 arch/arm64/include/asm/mtecomp.h              |  13 +
 arch/arm64/mm/Makefile                        |   1 +
 arch/arm64/mm/mtecomp.c                       | 467 ++++++++++++++++++
 arch/arm64/mm/mtecomp.h                       |  12 +
 7 files changed, 750 insertions(+)
 create mode 100644 Documentation/arch/arm64/mte-tag-compression.rst
 create mode 100644 arch/arm64/include/asm/mtecomp.h
 create mode 100644 arch/arm64/mm/mtecomp.c
 create mode 100644 arch/arm64/mm/mtecomp.h
Documentation/arch/arm64/index.rst +1 -0
index d08e924204bf1..bf6c1583233a9 100644
@@ -19,6 +19,7 @@ ARM64 Architecture
     legacy_instructions
     memory
     memory-tagging-extension
+    mte-tag-compression
     perf
     pointer-authentication
     ptdump
Documentation/arch/arm64/mte-tag-compression.rst new file +245 -0

245 lines not on this page · raw message

arch/arm64/Kconfig +11 -0
index a2511b30d0f67..d4fb3b8d11d77 100644
@@ -2093,6 +2093,17 @@ config ARM64_EPAN
 	  if the cpu does not implement the feature.
 endmenu # "ARMv8.7 architectural features"
 
+config ARM64_MTE_COMP
+	bool "Tag compression for ARM64 Memory Tagging Extension"
+	default y
+	depends on ARM64_MTE
+	help
+	  Enable tag compression support for ARM64 Memory Tagging Extension.
+
+	  Tag buffers corresponding to swapped RAM pages are compressed using
+	  RLE to conserve heap memory. In the common case compressed tags
+	  occupy 2.5x less memory.
+
 config ARM64_SVE
 	bool "ARM Scalable Vector Extension support"
 	default y
arch/arm64/include/asm/mtecomp.h new file +13 -0
new file mode 100644
index 0000000000000..71552bc429882
@@ -0,0 +1,13 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef __ASM_MTECOMP_H
+#define __ASM_MTECOMP_H
+
+#include <linux/types.h>
+
+unsigned long mte_compress(u8 *tags);
+bool mte_decompress(unsigned long handle, u8 *tags);
+void mte_release_handle(unsigned long handle);
+size_t mte_storage_size(unsigned long handle);
+
+#endif // __ASM_MTECOMP_H
arch/arm64/mm/Makefile +1 -0
index dbd1bc95967d0..46778f6dd83c2 100644
@@ -10,6 +10,7 @@ obj-$(CONFIG_TRANS_TABLE)	+= trans_pgd.o
 obj-$(CONFIG_TRANS_TABLE)	+= trans_pgd-asm.o
 obj-$(CONFIG_DEBUG_VIRTUAL)	+= physaddr.o
 obj-$(CONFIG_ARM64_MTE)		+= mteswap.o
+obj-$(CONFIG_ARM64_MTE_COMP)	+= mtecomp.o
 KASAN_SANITIZE_physaddr.o	+= n
 
 obj-$(CONFIG_KASAN)		+= kasan_init.o
arch/arm64/mm/mtecomp.c new file +467 -0

467 lines not on this page · raw message

arch/arm64/mm/mtecomp.h new file +12 -0
new file mode 100644
index 0000000000000..b94cf0384f2af
@@ -0,0 +1,12 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef ARCH_ARM64_MM_MTECOMP_H_
+#define ARCH_ARM64_MM_MTECOMP_H_
+
+/* Functions exported from mtecomp.c for test_mtecomp.c. */
+void mte_tags_to_ranges(u8 *tags, u8 *out_tags, unsigned short *out_sizes,
+			size_t *out_len);
+void mte_ranges_to_tags(u8 *r_tags, unsigned short *r_sizes, size_t r_len,
+			u8 *tags);
+
+#endif  // ARCH_ARM64_MM_TEST_MTECOMP_H_
Signature · 1 line
2.42.0.515.g380fc7ccd1-goog
#18 lore raw

PATCH v5 4/5 arm64: mte: add a test for MTE tags compression

In reply to Alexander Potapenko

Ensure that tag sequences containing alternating values are compressed to buffers of expected size and correctly decompressed afterwards.

---
v5:
- remove hardcoded constants, added test setup/teardown;
- support 16- and 64K pages;
- replace nested if-clauses with expected_size_from_ranges();
- call mte_release_handle() after tests that perform

    compression/decompression;

- address comments by Andy Shevchenko:
- fix include order;
- use mtecomp.h instead of function prototypes.

v4:
- addressed comments by Andy Shevchenko:
- expanded MTE to "Memory Tagging Extension" in Kconfig
- changed signed variables to unsigned where applicable
- added missing header dependencies

- addressed comments by Yury Norov:
- moved test-only declarations from mtecomp.h into this test
- switched to the new "mte"-prefixed function names, dropped the mentions of "EA0"
- added test_tag_to_ranges_n()

v3:
- addressed comments by Andy Shevchenko in another patch:
- switched from u64 to unsigned long
- added MODULE_IMPORT_NS(MTECOMP)
- fixed includes order

---
 arch/arm64/Kconfig           |  10 ++
 arch/arm64/mm/Makefile       |   1 +
 arch/arm64/mm/test_mtecomp.c | 287 +++++++++++++++++++++++++++++++++++
 3 files changed, 298 insertions(+)
 create mode 100644 arch/arm64/mm/test_mtecomp.c
arch/arm64/Kconfig +10 -0
index d4fb3b8d11d77..ffe3bec89df82 100644
@@ -2104,6 +2104,16 @@ config ARM64_MTE_COMP
 	  RLE to conserve heap memory. In the common case compressed tags
 	  occupy 2.5x less memory.
 
+config ARM64_MTE_COMP_KUNIT_TEST
+	tristate "Test tag compression for ARM64 Memory Tagging Extension" if !KUNIT_ALL_TESTS
+	default KUNIT_ALL_TESTS
+	depends on KUNIT && ARM64_MTE_COMP
+	help
+	  Test MTE compression algorithm enabled by CONFIG_ARM64_MTE_COMP.
+
+	  Ensure that tag sequences containing alternating values are compressed
+	  to buffers of expected size and correctly decompressed afterwards.
+
 config ARM64_SVE
 	bool "ARM Scalable Vector Extension support"
 	default y
arch/arm64/mm/Makefile +1 -0
index 46778f6dd83c2..170dc62b010b9 100644
@@ -11,6 +11,7 @@ obj-$(CONFIG_TRANS_TABLE)	+= trans_pgd-asm.o
 obj-$(CONFIG_DEBUG_VIRTUAL)	+= physaddr.o
 obj-$(CONFIG_ARM64_MTE)		+= mteswap.o
 obj-$(CONFIG_ARM64_MTE_COMP)	+= mtecomp.o
+obj-$(CONFIG_ARM64_MTE_COMP_KUNIT_TEST) += test_mtecomp.o
 KASAN_SANITIZE_physaddr.o	+= n
 
 obj-$(CONFIG_KASAN)		+= kasan_init.o
arch/arm64/mm/test_mtecomp.c new file +287 -0

287 lines not on this page · raw message

Signature · 1 line
2.42.0.515.g380fc7ccd1-goog
#19 lore raw

PATCH v5 5/5 arm64: mte: add compression support to mteswap.c

In reply to Alexander Potapenko

Define the internal mteswap.h interface:
- _mte_alloc_and_save_tags()
- _mte_free_saved_tags()
- _mte_restore_tags()

, that encapsulates saving tags for a struct page (together with memory allocation), restoring tags, and deleting the storage allocated for them.

These functions accept opaque pointers, which may point to tag buffers of size MTE_PAGE_TAG_STORAGE, as well as smaller buffers containing compressed tags, or may have compressed tags stored directly in the pointers.

The existing code from mteswap.c operating with uncompressed tags is split away into mteswap_nocomp.c, and the newly introduced mteswap_comp.c provides compression support. The latter implementation
is picked if CONFIG_ARM64_MTE_COMP=y.

Soon after booting Android, tag compression saves ~2.5x memory previously spent by mteswap.c on tag allocations. With the growing uptime, the savings may reach 4x and even more. On a moderately loaded device with ~20% pages using tagging, the compressed tags for swapped pages only occupied 2.9Mb instead of 16.5Mb:

8 bytes: 118277 allocations, 16089 deallocations 16 bytes: 10762 allocations, 6738 deallocations 32 bytes: 10748 allocations, 6823 deallocations 64 bytes: 10510 allocations, 6644 deallocations 128 bytes: 68375 allocations, 47378 deallocations uncompressed tag storage size: 17280000 compressed tag storage size: 3125024

---
v5:
- drop a dead variable from _mte_free_saved_tags() in mteswap_comp.c
- ensure MTE compression works with arbitrary page sizes
- update patch description

v4:
- minor code simplifications suggested by Andy Shevchenko, added missing header dependencies
- changed compression API names to reflect modifications made to memcomp.h (as suggested by Yury Norov)

v3:
- Addressed comments by Andy Shevchenko in another patch:
- fixed includes order
- replaced u64 with unsigned long
- added MODULE_IMPORT_NS(MTECOMP)

---
 arch/arm64/mm/Makefile         |  5 +++
 arch/arm64/mm/mteswap.c        | 20 +++++-------
 arch/arm64/mm/mteswap.h        | 12 +++++++
 arch/arm64/mm/mteswap_comp.c   | 60 ++++++++++++++++++++++++++++++++++
 arch/arm64/mm/mteswap_nocomp.c | 38 +++++++++++++++++++++
 5 files changed, 124 insertions(+), 11 deletions(-)
 create mode 100644 arch/arm64/mm/mteswap.h
 create mode 100644 arch/arm64/mm/mteswap_comp.c
 create mode 100644 arch/arm64/mm/mteswap_nocomp.c
arch/arm64/mm/Makefile +5 -0
index 170dc62b010b9..46a798e2b67cb 100644
@@ -11,6 +11,11 @@ obj-$(CONFIG_TRANS_TABLE)	+= trans_pgd-asm.o
 obj-$(CONFIG_DEBUG_VIRTUAL)	+= physaddr.o
 obj-$(CONFIG_ARM64_MTE)		+= mteswap.o
 obj-$(CONFIG_ARM64_MTE_COMP)	+= mtecomp.o
+ifdef CONFIG_ARM64_MTE_COMP
+obj-$(CONFIG_ARM64_MTE)		+= mteswap_comp.o
+else
+obj-$(CONFIG_ARM64_MTE)		+= mteswap_nocomp.o
+endif
 obj-$(CONFIG_ARM64_MTE_COMP_KUNIT_TEST) += test_mtecomp.o
 KASAN_SANITIZE_physaddr.o	+= n
 
arch/arm64/mm/mteswap.c +9 -11
index cd508ba80ab1b..9d8f87fd191a2 100644
@@ -5,8 +5,11 @@
 #include <linux/slab.h>
 #include <linux/swap.h>
 #include <linux/swapops.h>
+
 #include <asm/mte.h>
 
+#include "mteswap.h"
+
 static DEFINE_XARRAY(mte_pages);
 
 void *mte_allocate_tag_storage(void)
@@ -27,20 +30,18 @@ int mte_save_tags(struct page *page)
 	if (!page_mte_tagged(page))
 		return 0;
 
-	tag_storage = mte_allocate_tag_storage();
+	tag_storage = _mte_alloc_and_save_tags(page);
 	if (!tag_storage)
 		return -ENOMEM;
 
-	mte_save_page_tags(page_address(page), tag_storage);
-
 	/* page_private contains the swap entry.val set in do_swap_page */
 	ret = xa_store(&mte_pages, page_private(page), tag_storage, GFP_KERNEL);
 	if (WARN(xa_is_err(ret), "Failed to store MTE tags")) {
-		mte_free_tag_storage(tag_storage);
+		_mte_free_saved_tags(tag_storage);
 		return xa_err(ret);
 	} else if (ret) {
 		/* Entry is being replaced, free the old entry */
-		mte_free_tag_storage(ret);
+		_mte_free_saved_tags(ret);
 	}
 
 	return 0;
@@ -53,10 +54,7 @@ void mte_restore_tags(swp_entry_t entry, struct page *page)
 	if (!tags)
 		return;
 
-	if (try_page_mte_tagging(page)) {
-		mte_restore_page_tags(page_address(page), tags);
-		set_page_mte_tagged(page);
-	}
+	_mte_restore_tags(tags, page);
 }
 
 void mte_invalidate_tags(int type, pgoff_t offset)
@@ -64,7 +62,7 @@ void mte_invalidate_tags(int type, pgoff_t offset)
 	swp_entry_t entry = swp_entry(type, offset);
 	void *tags = xa_erase(&mte_pages, entry.val);
 
-	mte_free_tag_storage(tags);
+	_mte_free_saved_tags(tags);
 }
 
 void mte_invalidate_tags_area(int type)
@@ -78,7 +76,7 @@ void mte_invalidate_tags_area(int type)
 	xa_lock(&mte_pages);
 	xas_for_each(&xa_state, tags, last_entry.val - 1) {
 		__xa_erase(&mte_pages, xa_state.xa_index);
-		mte_free_tag_storage(tags);
+		_mte_free_saved_tags(tags);
 	}
 	xa_unlock(&mte_pages);
 }
arch/arm64/mm/mteswap.h new file +12 -0
new file mode 100644
index 0000000000000..4c576b76785d1
@@ -0,0 +1,12 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef ARCH_ARM64_MM_MTESWAP_H_
+#define ARCH_ARM64_MM_MTESWAP_H_
+
+struct page;
+
+void *_mte_alloc_and_save_tags(struct page *page);
+void _mte_free_saved_tags(void *tags);
+void _mte_restore_tags(void *tags, struct page *page);
+
+#endif // ARCH_ARM64_MM_MTESWAP_H_
arch/arm64/mm/mteswap_comp.c new file +60 -0

60 lines not on this page · raw message

arch/arm64/mm/mteswap_nocomp.c new file +38 -0
new file mode 100644
index 0000000000000..1e665a4b5f940
@@ -0,0 +1,38 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/* MTE tag storage management without compression support. */
+
+#include <linux/pagemap.h>
+#include <linux/slab.h>
+#include <linux/swap.h>
+#include <linux/swapops.h>
+#include <linux/xarray.h>
+
+#include <asm/mte.h>
+
+#include "mteswap.h"
+
+void *_mte_alloc_and_save_tags(struct page *page)
+{
+	void *storage;
+
+	storage = mte_allocate_tag_storage();
+	if (!storage)
+		return NULL;
+
+	mte_save_page_tags(page_address(page), storage);
+	return storage;
+}
+
+void _mte_free_saved_tags(void *storage)
+{
+	mte_free_tag_storage(storage);
+}
+
+void _mte_restore_tags(void *tags, struct page *page)
+{
+	if (!try_page_mte_tagging(page))
+		return;
+	mte_restore_page_tags(page_address(page), tags);
+	set_page_mte_tagged(page);
+}
Signature · 1 line
2.42.0.515.g380fc7ccd1-goog
#20 lore raw
In reply to Alexander Potapenko

+Cc: Olek, who internally is being developed something similar to your first patch here.

Quoted 82 lines · Alexander Potapenko

Currently, when MTE pages are swapped out, the tags are kept in the memory, occupying PAGE_SIZE/32 bytes per page. This is especially problematic for devices that use zram-backed in-memory swap, because tags stored uncompressed in the heap effectively reduce the available amount of swap memory.

The RLE-based algorithm suggested by Evgenii Stepanov and implemented in this patch series is able to efficiently compress fixed-size tag buffers, resulting in practical compression ratio between 2.5x and 4x. In most cases it is possible to store the compressed data in 63-bit Xarray values, resulting in no extra memory allocations.

Our measurements show that the proposed algorithm provides better compression than existing kernel compression algorithms (LZ4, LZO, LZ4HC, ZSTD) can offer.

To implement compression/decompression, we also extend <linux/bitmap.h> with methods to read/write bit values at arbitrary places in the map.

We refactor arch/arm64/mm/mteswap.c to support both the compressed (CONFIG_ARM64_MTE_COMP) and non-compressed case. For the former, in addition to tag compression, we move tag allocation from kmalloc() to separate kmem caches, providing greater locality and relaxing the alignment requirements.

v5:
- fixed comments by Andy Shevchenko, Catalin Marinas, and Yury Norov
- added support for 16K- and 64K pages
- more efficient bitmap_write() implementation

v4:
- fixed a bunch of comments by Andy Shevchenko and Yury Norov
- added Documentation/arch/arm64/mte-tag-compression.rst

v3:
- as suggested by Andy Shevchenko, use bitmap_get_value()/bitmap_set_value() written by Syed Nayyar Waris
- switched to unsigned long to reduce typecasts
- simplified the compression code

v2:
- as suggested by Yuri Norov, replace the poorly implemented struct bitq with <linux/bitmap.h>

Alexander Potapenko (4):
lib/test_bitmap: add tests for bitmap_{read,write}()
arm64: mte: implement CONFIG_ARM64_MTE_COMP
arm64: mte: add a test for MTE tags compression
arm64: mte: add compression support to mteswap.c

Syed Nayyar Waris (1):
lib/bitmap: add bitmap_{read,write}()

 Documentation/arch/arm64/index.rst            |   1 +
 .../arch/arm64/mte-tag-compression.rst        | 245 +++++++++
 arch/arm64/Kconfig                            |  21 +
 arch/arm64/include/asm/mtecomp.h              |  13 +
 arch/arm64/mm/Makefile                        |   7 +
 arch/arm64/mm/mtecomp.c                       | 467 ++++++++++++++++++
 arch/arm64/mm/mtecomp.h                       |  12 +
 arch/arm64/mm/mteswap.c                       |  20 +-
 arch/arm64/mm/mteswap.h                       |  12 +
 arch/arm64/mm/mteswap_comp.c                  |  60 +++
 arch/arm64/mm/mteswap_nocomp.c                |  38 ++
 arch/arm64/mm/test_mtecomp.c                  | 287 +++++++++++
 include/linux/bitmap.h                        |  68 +++
 lib/test_bitmap.c                             | 115 +++++
 14 files changed, 1355 insertions(+), 11 deletions(-)
 create mode 100644 Documentation/arch/arm64/mte-tag-compression.rst
 create mode 100644 arch/arm64/include/asm/mtecomp.h
 create mode 100644 arch/arm64/mm/mtecomp.c
 create mode 100644 arch/arm64/mm/mtecomp.h
 create mode 100644 arch/arm64/mm/mteswap.h
 create mode 100644 arch/arm64/mm/mteswap_comp.c
 create mode 100644 arch/arm64/mm/mteswap_nocomp.c
 create mode 100644 arch/arm64/mm/test_mtecomp.c
Signature · 1 line
2.42.0.515.g380fc7ccd1-goog
Signature · 2 lines
With Best Regards,
Andy Shevchenko
#21 lore raw

From: Andy Shevchenko <[email protected]>
Date: Fri, 22 Sep 2023 17:35:19 +0300

Quoted 2 lines

+Cc: Olek, who internally is being developed something similar to your first patch here.

Oh, thanks.
The patch you mentioned properly implements cross-boundary accesses, mine does not :D
But I guess we want to keep them both to keep the latter as optimized as the current bitmap_{get,set}_value8()?

Quoted 14 lines · Alexander Potapenko
Quoted 12 lines

Currently, when MTE pages are swapped out, the tags are kept in the memory, occupying PAGE_SIZE/32 bytes per page. This is especially problematic for devices that use zram-backed in-memory swap, because tags stored uncompressed in the heap effectively reduce the available amount of swap memory.

The RLE-based algorithm suggested by Evgenii Stepanov and implemented in this patch series is able to efficiently compress fixed-size tag buffers, resulting in practical compression ratio between 2.5x and 4x. In most cases it is possible to store the compressed data in 63-bit Xarray values, resulting in no extra memory allocations.

Quoted 3 lines
Quoted 3 lines

Our measurements show that the proposed algorithm provides better compression than existing kernel compression algorithms (LZ4, LZO, LZ4HC, ZSTD) can offer.

[...]

Thanks,
Olek