Implement MTE tag compression for swapped pages

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

+Cc: William

Quoted 2 lines · Alexander Potapenko

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

A couple of years (?) ago it was a series to achieve something like this with better (?) code. Why not resurrect that one?

https://www.mail-archive.com/[email protected]/msg2195426.html

--
With Best Regards,
Andy Shevchenko

Quoted 10 lines · Andy Shevchenko

+Cc: William

Quoted 2 lines · Alexander Potapenko

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

A couple of years (?) ago it was a series to achieve something like this with better (?) code. Why not resurrect that one?

Quoted 1 line

https://www.mail-archive.com/[email protected]/msg2195426.html

It looks more compact thanks to GENMASK, I can cook something based on the proposed bitmap_{set,get}_value (and change the names if you prefer the shorter ones).
But I'd better avoid pulling in the rest of that series without a strong need.

Quoted 12 lines · Alexander Potapenko

Quoted 10 lines · Andy Shevchenko

+Cc: William

Quoted 2 lines · Alexander Potapenko

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

A couple of years (?) ago it was a series to achieve something like this with better (?) code. Why not resurrect that one?

Quoted 6 lines

Quoted 1 line

https://www.mail-archive.com/[email protected]/msg2195426.html

It looks more compact thanks to GENMASK, I can cook something based on the proposed bitmap_{set,get}_value (and change the names if you prefer the shorter ones).
But I'd better avoid pulling in the rest of that series without a strong need.

William, what do you think on this?

I'm personally prefer William's version as not only it was published first it was carefully designed and got a lot of review already. We just hadn't had the user for it that time.

Signature · 2 lines

With Best Regards,
Andy Shevchenko

Quoted 17 lines · Andy Shevchenko

Quoted 9 lines · Alexander Potapenko

Quoted 7 lines · Andy Shevchenko

Quoted 2 lines · Alexander Potapenko

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

A couple of years (?) ago it was a series to achieve something like this with better (?) code. Why not resurrect that one?

Quoted 6 lines

Quoted 1 line

https://www.mail-archive.com/[email protected]/msg2195426.html

It looks more compact thanks to GENMASK, I can cook something based on the proposed bitmap_{set,get}_value (and change the names if you prefer the shorter ones).
But I'd better avoid pulling in the rest of that series without a strong need.

Quoted 5 lines

William, what do you think on this?

I'm personally prefer William's version as not only it was published first it was carefully designed and got a lot of review already. We just hadn't had the user for it that time.

Yes, that version went through several revisions so it's been well tested and known to work -- as you pointed out it just lacked the users to warrant merging it into the tree. If it statisfies the use-case required here now, then I think we should it pick it up rather than reinvent the solution again.

Also, we probably don't need the "clump" code in there, so perhaps splitting it out to just the bitmap_{set,get}_value relevant code is fine.

Quoted 30 lines · William Breathitt Gray

Quoted 17 lines · Andy Shevchenko

Quoted 9 lines · Alexander Potapenko

Quoted 7 lines · Andy Shevchenko

Quoted 2 lines · Alexander Potapenko

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

A couple of years (?) ago it was a series to achieve something like this with better (?) code. Why not resurrect that one?

Quoted 6 lines

Quoted 1 line

https://www.mail-archive.com/[email protected]/msg2195426.html

It looks more compact thanks to GENMASK, I can cook something based on the proposed bitmap_{set,get}_value (and change the names if you prefer the shorter ones).
But I'd better avoid pulling in the rest of that series without a strong need.

Quoted 5 lines

William, what do you think on this?

I'm personally prefer William's version as not only it was published first it was carefully designed and got a lot of review already. We just hadn't had the user for it that time.

Yes, that version went through several revisions so it's been well tested and known to work -- as you pointed out it just lacked the users to warrant merging it into the tree. If it statisfies the use-case required here now, then I think we should it pick it up rather than reinvent the solution again.

Quoted 3 lines

Also, we probably don't need the "clump" code in there, so perhaps splitting it out to just the bitmap_{set,get}_value relevant code is fine.

Agree, thank you for your comments!

--
With Best Regards,
Andy Shevchenko

Quoted 3 lines · Andy Shevchenko

Quoted 2 lines · William Breathitt Gray

Quoted 1 line · Andy Shevchenko

On Thu, Jul 13, 2023 at 08:05:34PM +0200, Alexander Potapenko wrote:

Quoted 16 lines

Quoted 15 lines

Quoted 5 lines

William, what do you think on this?

I'm personally prefer William's version as not only it was published first it was carefully designed and got a lot of review already. We just hadn't had the user for it that time.

Yes, that version went through several revisions so it's been well tested and known to work -- as you pointed out it just lacked the users to warrant merging it into the tree. If it statisfies the use-case required here now, then I think we should it pick it up rather than reinvent the solution again.

Also, we probably don't need the "clump" code in there, so perhaps splitting it out to just the bitmap_{set,get}_value relevant code is fine.

Quoted 1 line

Agree, thank you for your comments!

So would it be fine if I split off bitmap_set_value() and bitmap_get_value() from that series and send it (with the appropriate attribution) instead of my patch 1/5?
We'll probably still need to retain patch 2/5 (with the function names changed).

The config implements the EA0 algorithm suggested by Evgenii Stepanov to compress the memory tags for ARM MTE during swapping.

The algorithm is based on RLE and specifically targets 128-byte 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.

+/*
+ * EA0 stands for "Evgenii's Algorithm 0", as the initial proposal contained two
+ * compression algorithms.
+ *
+ * The algorithm attempts to compress a 128-byte (MTE_GRANULES_PER_PAGE / 2)
+ * array of tags into a smaller byte sequence that can be stored in a
+ * 16-, 32-, or 64-byte buffer. A special case is storing the tags inline in
+ * an 8-byte pointer.
+ *
+ * We encapsulate tag storage memory management in this module, because it is
+ * tightly coupled with the pointer representation.
+ * ea0_compress(*tags) takes a 128-byte buffer and returns an opaque value
+ * that can be stored in Xarray
+ * ea_decompress(*ptr, *tags) takes the opaque value and loads the tags into
+ * the provided 128-byte buffer.

+ *
+ *
+ *

+ * The compression algorithm works as follows.
+ *
+ * 1. The input array of 128 bytes is transformed into tag ranges (two arrays:
+ * @r_tags containing tag values and @r_sizes containing range lengths) by
+ * ea0_tags_to_ranges(). Note that @r_sizes sums up to 256.
+ *
+ * 2. Depending on the number N of ranges, the following storage class is picked:
+ * N <= 6: 8 bytes (inline case, no allocation required);
+ * 6 < N <= 11: 16 bytes

+ *      11 < N <= 23: 32 bytes
+ *      23 < N <= 46: 64 bytes
+ *      46 < N:       128 bytes (no compression will be performed)
+ *
+ * 3. The number of the largest element of @r_sizes is stored in @largest_idx.
+ *    The element itself is thrown away from @r_sizes, because it can be
+ *    reconstructed from the sum of the remaining elements. Note that now none
+ *    of the remaining @r_sizes elements is greater than 127.

+ *
+ * 4. For the inline case, the following values are stored in the 8-byte handle:
+ * largest_idx : i4
+ * r_tags[0..5] : i4 x 6
+ * r_sizes[0..4] : i7 x 5
+ * (if N is less than 6, @r_tags and @r_sizes are padded up with zero values)
+ *

+ *    Because @largest_idx is <= 5, bit 63 of the handle is always 0 (so it can
+ *    be stored in the Xarray), and bits 62..60 cannot all be 1, so it can be
+ *    distinguished from a kernel pointer.

+ *
+ * 5. For the out-of-line case, the storage is allocated from one of the
+ * "mte-tags-{16,32,64,128}" kmem caches. The resulting pointer is aligned
+ * on 8 bytes, so its bits 2..0 can be used to store the size class:

+ *     - 0 for 128 bytes
+ *     - 1 for 16
+ *     - 2 for 32
+ *     - 4 for 64.

+ * Bit 63 of the pointer is zeroed out, so that it can be stored in Xarray.
+ *
+ * 6. The data layout in the allocated storage is as follows:
+ * largest_idx : i6
+ * r_tags[0..N] : i4 x N
+ * r_sizes[0..N-1] : i7 x (N-1)
+ *
+ *
+ *

+ * The decompression algorithm performs the steps below.
+ *
+ * 1. Decide if data is stored inline (bits 62..60 of the handle != 0b111) or
+ * out-of line.
+ *
+ * 2. For the inline case, treat the handle itself as the input buffer.
+ *
+ * 3. For the out-of-line case, look at bits 2..0 of the handle to understand
+ * the input buffer length. To obtain the pointer to the input buffer, unset
+ * bits 2..0 of the handle and set bit 63.
+ *
+ * 4. If the input buffer is 128 byte long, copy its contents to the output
+ * buffer.
+ *
+ * 5. Otherwise, read @largest_idx, @r_tags and @r_sizes from the input buffer.
+ * Calculate the removed largest element of @r_sizes:
+ * largest = 256 - sum(r_sizes)
+ * and insert it into @r_sizes at position @largest_idx.
+ *
+ * 6. While @r_sizes[i] > 0, add a 4-bit value @r_tags[i] to the output buffer
+ * @r_sizes[i] times.
+ */

+#define HANDLE_MASK ~(BIT_ULL(63))

arch/arm64/mm/mtecomp.c new file +19 -0

+/* Translate allocation size into mtecomp_caches[] index. */
+static int ea0_size_to_cache_id(int len)
+{
+	switch (len) {
+	case 16:
+		return 1;
+	case 32:
+		return 2;
+	case 64:
+		return 3;
+	default:
+		return 0;
+	}
+}
+
+/* Translate mtecomp_caches[] index into allocation size. */
+static int ea0_cache_id_to_size(int id)
+{
+	switch (id) {

arch/arm64/mm/mtecomp.c new file +4 -0

+	for (i = 0; i < MTE_GRANULES_PER_PAGE; i++) {
+		cur_tag = tags[i / 2];
+		if (i % 2)
+			cur_tag = cur_tag % 16;

arch/arm64/mm/mtecomp.c new file +7 -0

+				prev = r_tags[i];
+			else
+				tags[pos / 2] = (prev << 4) | r_tags[i];
+			pos++;
+		}
+	}
+}

+EXPORT_SYMBOL(ea0_storage_size);

arch/arm64/mm/mtecomp.c new file +8 -0

+		bitmap_set_value_unaligned((unsigned long *)buf, largest_idx,
+					   bit_pos, 4);
 
+		bitmap_set_value_unaligned((unsigned long *)buf, largest_idx,
+					   bit_pos, 6);
 
+		bitmap_set_value_unaligned((unsigned long *)buf, tags[i],
+					   bit_pos, 4);
 
+		bitmap_set_value_unaligned((unsigned long *)buf, 0, bit_pos, 4);
 
+		bitmap_set_value_unaligned((unsigned long *)buf, sizes[i],

arch/arm64/mm/mtecomp.c new file +6 -0

+static int mtecomp_init(void)
+{
+	char name[16];
+	int size;
+	int i;
+

+module_init(mtecomp_init);

Quoted 16 lines

arch/arm64/mm/mtecomp.c new file +11 -0

+		bitmap_set_value_unaligned((unsigned long *)buf, largest_idx,
+					   bit_pos, 4);
 
+		bitmap_set_value_unaligned((unsigned long *)buf, largest_idx,
+					   bit_pos, 6);
 
+		bitmap_set_value_unaligned((unsigned long *)buf, tags[i],
+					   bit_pos, 4);
 
+		bitmap_set_value_unaligned((unsigned long *)buf, 0, bit_pos, 4);
 
+		bitmap_set_value_unaligned((unsigned long *)buf, sizes[i],
+					   bit_pos, 7);
 
+	largest_idx = bitmap_get_value_unaligned((unsigned long *)buf, bit_pos,
+						 l_bits);

arch/arm64/mm/mtecomp.c line 339

Quoted 5 lines

arch/arm64/mm/mtecomp.c new file +4 -0

+		r_tags[i] = bitmap_get_value_unaligned((unsigned long *)buf,
+						       bit_pos, 4);
 
+		r_sizes[i] = bitmap_get_value_unaligned((unsigned long *)buf,
+							bit_pos, 7);

These castings is a red flag. bitmap API shouldn't be used like this. Something is not okay here.

arch/arm64/mm/mtecomp.c line 389

Quoted 8 lines

arch/arm64/mm/mtecomp.c new file +7 -0

+void ea0_release_handle(u64 handle)
+{
+	void *storage = ea0_storage(handle);
+	int size = ea0_storage_size(handle);
+	struct kmem_cache *c;
 
+	if (!handle || !storage)
+		return;

You use handle before this check. Haven't you run static analysers?

Quoted 7 lines

arch/arm64/mm/mtecomp.c line 389

Quoted 5 lines

arch/arm64/mm/mtecomp.c new file +4 -0

+	void *storage = ea0_storage(handle);
+	int size = ea0_storage_size(handle);
 
+	if (!handle || !storage)
+		return;

You use handle before this check. Haven't you run static analysers?

This approach is called 'defensive programming' as I learned from previous iteration.

Quoted 3 lines

+ *
+ *
+ *

Isn't a bit too many blank lines?

Quoted 3 lines

+ *
+ *
+ *

Ditto.

...

arch/arm64/mm/mtecomp.c line 100

Quoted 8 lines

arch/arm64/mm/mtecomp.c new file +8 -0

+#include <linux/bitmap.h>
+#include <linux/gfp.h>
+#include <linux/module.h>
+#include <asm/mtecomp.h>
+#include <linux/slab.h>
+#include <linux/swab.h>
+#include <linux/string.h>
+#include <linux/types.h>

Please, keep linux/* and asm/* separated like

linux/*
...blank line...
asm/*

...

Quoted 1 line

+#define HANDLE_MASK ~(BIT_ULL(63))

GENMASK_ULL(62, 0)

Not sure why fls() / BIT() can't be used directly instead of these functions, but okay, they are not too ugly.

arch/arm64/mm/mtecomp.c line 148

Quoted 3 lines

arch/arm64/mm/mtecomp.c new file +3 -0

+void ea0_tags_to_ranges(u8 *tags, u8 *out_tags, short *out_sizes, int *out_len)
+{
+     u8 prev_tag = 0xff;

GENMASK()? U8_MAX? ((u8)-1)? What is this?

arch/arm64/mm/mtecomp.c line 154

Quoted 2 lines

arch/arm64/mm/mtecomp.c new file +2 -0

+     memset(out_tags, 0, *out_len * sizeof(*out_tags));
+     memset(out_sizes, 0, *out_len * sizeof(*out_sizes));

array_size() ?

Quoted 5 lines

arch/arm64/mm/mtecomp.c new file +4 -0

+     for (i = 0; i < MTE_GRANULES_PER_PAGE; i++) {
+             cur_tag = tags[i / 2];
+             if (i % 2)
+                     cur_tag = cur_tag % 16;

arch/arm64/mm/mtecomp.c line 168

Quoted 10 lines

arch/arm64/mm/mtecomp.c new file +10 -0

+             else
+                     cur_tag = cur_tag / 16;
+             if (cur_tag == prev_tag) {
+                     out_sizes[cur_idx]++;
+             } else {
+                     cur_idx++;
+                     prev_tag = cur_tag;
+                     out_tags[cur_idx] = prev_tag;
+                     out_sizes[cur_idx] = 1;
+             }

Perhaps instead of doing those % 2, / 2 we simply can go twice less outer loops and introduce an inner loop of 2 iterations?

Quoted 1 line

+ if (pos % 2 == 0)

Would be better to keep this aligned with above?

                        if (pos % 2)
                                ...
                        else
                                ...

...

Quoted 1 line

+EXPORT_SYMBOL(ea0_storage_size);

Btw, can we go to the namespaced export from day 1?

...

arch/arm64/mm/mtecomp.c line 248

Quoted 3 lines

arch/arm64/mm/mtecomp.c new file +3 -0

+     for (i = 0; i < len; i++) {
+             if (i == len)
+                     break;

Interesting dead code. What was the idea behind this?

arch/arm64/mm/mtecomp.c line 252

Quoted 5 lines

arch/arm64/mm/mtecomp.c new file +4 -0

+             if (sizes[i] > largest) {
+                     largest = sizes[i];
+                     largest_idx = i;
+             }

(alas max_array() can't be used here)

arch/arm64/mm/mtecomp.c line 339

Quoted 3 lines

arch/arm64/mm/mtecomp.c new file +2 -0

+             r_sizes[i] = bitmap_get_value_unaligned((unsigned long *)buf,
+                                                     bit_pos, 7);

These castings is a red flag. bitmap API shouldn't be used like this. Something is not okay here.

...

Quoted 5 lines

arch/arm64/mm/mtecomp.c new file +5 -0

+void ea0_release_handle(u64 handle)
+{
+     void *storage = ea0_storage(handle);
+     int size = ea0_storage_size(handle);
+     struct kmem_cache *c;

arch/arm64/mm/mtecomp.c line 389

Quoted 2 lines

arch/arm64/mm/mtecomp.c new file +2 -0

+     if (!handle || !storage)
+             return;

You use handle before this check. Haven't you run static analysers?

...

Quoted 14 lines

arch/arm64/mm/mtecomp.c new file +14 -0

+static int mtecomp_init(void)
+{
+     char name[16];
+     int size;
+     int i;
+
+     for (i = 0; i < NUM_CACHES; i++) {
+             size = ea0_cache_id_to_size(i);
+             snprintf(name, ARRAY_SIZE(name), "mte-tags-%d", size);
+             mtecomp_caches[i] =
+                     kmem_cache_create(name, size, size, 0, NULL);
+     }
+     return 0;
+}

Quoted 1 line

+

Unneeded blank line.

Quoted 2 lines

Not sure why fls() / BIT() can't be used directly instead of these functions, but okay, they are not too ugly.

They can't be used directly because 128 maps to 0, but I can sure simplify them a bit.

Quoted 8 lines

Quoted 1 line

+ if (pos % 2 == 0)

Would be better to keep this aligned with above?

                        if (pos % 2)
                                ...
                        else
                                ...

It would, but i % 2 above didn't survive the rewrite, so I assume it is fine to keep pos % 2 == 0 as is.

Quoted 3 lines

Quoted 1 line

+EXPORT_SYMBOL(ea0_storage_size);

Btw, can we go to the namespaced export from day 1?

Am I getting it right that I just need to change EXPORT_SYMBOL to EXPORT_SYMBOL_NS and import the namespace in arch/arm64/mm/test_mtecomp.c?
I.e. MODULE_IMPORT_NS is not needed in mteswap_comp.c, because it is linked into the kernel?

Quoted 6 lines

arch/arm64/mm/mtecomp.c line 252

Quoted 4 lines

arch/arm64/mm/mtecomp.c new file +4 -0

+             if (sizes[i] > largest) {
+                     largest = sizes[i];
+                     largest_idx = i;
+             }

(alas max_array() can't be used here)

There's no max_array() in the kernel, am I missing something?

Quoted 9 lines

Quoted 8 lines

arch/arm64/mm/mtecomp.c new file +7 -0

+void ea0_release_handle(u64 handle)
+{
+     void *storage = ea0_storage(handle);
+     int size = ea0_storage_size(handle);
+     struct kmem_cache *c;
 
+     if (!handle || !storage)
+             return;

Quoted 1 line

You use handle before this check. Haven't you run static analysers?

Sparse doesn't report anything in these files, are there any alternatives adopted in the kernel?

Note that handle is not dereferenced above, so there's no error per se.

Yet (as pointed out below) these checks are redundant, so I'll remove some of them.

Quoted 3 lines

Quoted 1 line

+

Unneeded blank line.

I think there's no agreement on this in the kernel code, but my version is more popular:

$ git grep -B2 '^module_init(' | grep '\-}' -A2 | grep module_init | wc
   2688    2707  164023
$ git grep -B2 '^module_init(' | grep '\-}' -A1 | grep module_init | wc
    505     523   30989

On Fri, Jul 14, 2023 at 11:25:41AM +0200, Alexander Potapenko wrote:

...

Quoted 5 lines

Quoted 2 lines

Not sure why fls() / BIT() can't be used directly instead of these functions, but okay, they are not too ugly.

They can't be used directly because 128 maps to 0, but I can sure simplify them a bit.

Right, that's why I'm okay with the current implementation. But if you want to rewrite, up to you.

...

Quoted 9 lines

Quoted 8 lines

Quoted 1 line

+ if (pos % 2 == 0)

Would be better to keep this aligned with above?

                        if (pos % 2)
                                ...
                        else
                                ...

Quoted 2 lines

It would, but i % 2 above didn't survive the rewrite, so I assume it is fine to keep pos % 2 == 0 as is.

Not big deal, but less characters improve the brain process, so

        if (pos % 2)

kinda quicker to read and understand in my opinion.

...

Quoted 4 lines

Quoted 3 lines

Quoted 1 line

+EXPORT_SYMBOL(ea0_storage_size);

Btw, can we go to the namespaced export from day 1?

Quoted 5 lines

Am I getting it right that I just need to change EXPORT_SYMBOL to EXPORT_SYMBOL_NS and import the namespace in arch/arm64/mm/test_mtecomp.c?
I.e. MODULE_IMPORT_NS is not needed in mteswap_comp.c, because it is linked into the kernel?

I think you always need to include MODULE_IMPORT_NS for the sake of robustness of the code.

...

Quoted 11 lines

Quoted 3 lines

Quoted 1 line

+

Unneeded blank line.

I think there's no agreement on this in the kernel code, but my version is more popular:

$ git grep -B2 '^module_init(' | grep '\-}' -A2 | grep module_init | wc
   2688    2707  164023
$ git grep -B2 '^module_init(' | grep '\-}' -A1 | grep module_init | wc
    505     523   30989

Even though, there is no need for this blank line. And note, for better argument, compare this for the new code added let's say for the past 2 years. I believe numbers will tend to my variant.

I.o.w. you need to count on trends and not only on frequencies.