[v2 0/5] Implement MTE tag compression for swapped pages

[v2 0/5] Implement MTE tag compression for swapped pages

[Alexander Potapenko]

Currently, when MTE pages are swapped out, the tags are kept in the
memory, occupying 128 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 EA0 algorithm suggested by Evgenii Stepanov and
implemented in this patch series is able to efficiently compress
128-byte tag buffers, resulting in practical compression ratio between
2.5x and 20x. 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 EA0 provides better compression than existing
kernel compression algorithms (LZ4, LZO, LZ4HC, ZSTD) can offer, because
EA0 specifically targets 128-byte buffers.

To implement compression/decompression, we also extend <linux/bitmap.h>
with methods to set/get 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.

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

Alexander Potapenko (5):
  lib/bitmap: add bitmap_{set,get}_value_unaligned()
  lib/test_bitmap: add tests for bitmap_{set,get}_value_unaligned
  arm64: mte: implement CONFIG_ARM64_MTE_COMP
  arm64: mte: add a test for MTE tags compression
  arm64: mte: add compression support to mteswap.c

 arch/arm64/Kconfig               |  20 ++
 arch/arm64/include/asm/mtecomp.h |  60 +++++
 arch/arm64/mm/Makefile           |   7 +
 arch/arm64/mm/mtecomp.c          | 412 +++++++++++++++++++++++++++++++
 arch/arm64/mm/mteswap.c          |  19 +-
 arch/arm64/mm/mteswap.h          |  12 +
 arch/arm64/mm/mteswap_comp.c     |  50 ++++
 arch/arm64/mm/mteswap_nocomp.c   |  37 +++
 arch/arm64/mm/test_mtecomp.c     | 175 +++++++++++++
 include/linux/bitmap.h           |  63 +++++
 lib/test_bitmap.c                |  34 +++
 11 files changed, 878 insertions(+), 11 deletions(-)
 create mode 100644 arch/arm64/include/asm/mtecomp.h
 create mode 100644 arch/arm64/mm/mtecomp.c
 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

-- 
2.41.0.255.g8b1d071c50-goog


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

[v2 1/5] lib/bitmap: add bitmap_{set,get}_value_unaligned()

[Alexander Potapenko]

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

Suggested-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Alexander Potapenko <glider@google.com>
---
 include/linux/bitmap.h | 63 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 63 insertions(+)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 03644237e1efb..8e36ce07bafd4 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -77,6 +77,8 @@ struct device;
  *  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_set_value8(map, value, start)        Set 8bit value to map at start
+ *  bitmap_get_value_unaligned(map, start, nbits)  Get value up to BITS_PER_LONG
+ *  bitmap_set_value_unaligned(map, value, start, nbits)  Set value up to BITS_PER_LONG
  *
  * Note, bitmap_zero() and bitmap_fill() operate over the region of
  * unsigned longs, that is, bits behind bitmap till the unsigned long
@@ -583,6 +585,35 @@ static inline unsigned long bitmap_get_value8(const unsigned long *map,
 	return (map[index] >> offset) & 0xFF;
 }
 
+/**
+ * bitmap_get_value_unaligned - get an @nbits-bit value within a memory region
+ * @map: address to the bitmap memory region
+ * @start: bit offset of the value; may not be a multiple of 8
+ * @nbits: number of bits to get
+ *
+ * Returns the @nbits-sized value located at the @start bit offset within the
+ * @map memory region.
+ */
+static inline unsigned long bitmap_get_value_unaligned(const unsigned long *map,
+						       unsigned long start,
+						       unsigned long nbits)
+{
+	const size_t index = BIT_WORD(start);
+	const unsigned long offset = start % BITS_PER_LONG;
+	const unsigned long carry = (offset + nbits) % BITS_PER_LONG;
+	unsigned long hi, lo, result;
+
+	if (offset + nbits <= BITS_PER_LONG) {
+		result = map[index] >> (BITS_PER_LONG - offset - nbits);
+		return result & BITMAP_LAST_WORD_MASK(nbits);
+	}
+
+	hi = map[index] & BITMAP_LAST_WORD_MASK(BITS_PER_LONG - offset);
+	lo = map[index + 1] & BITMAP_FIRST_WORD_MASK(BITS_PER_LONG - carry);
+	lo >>= (BITS_PER_LONG - carry);
+	return (hi << carry) | lo;
+}
+
 /**
  * bitmap_set_value8 - set an 8-bit value within a memory region
  * @map: address to the bitmap memory region
@@ -599,6 +630,38 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value,
 	map[index] |= value << offset;
 }
 
+/**
+ * bitmap_set_value_unaligned - set an @nbits-bit value within a memory region
+ * @map: address to the bitmap memory region
+ * @value: the value up to BITS_PER_LONG bits (will be clamped to @nbits)
+ * @start: bit offset of the value; may not be a multiple of 8
+ * @nbits: number of bits to set
+ */
+static inline void bitmap_set_value_unaligned(unsigned long *map,
+					      unsigned long value,
+					      unsigned long start,
+					      unsigned long nbits)
+{
+	const size_t index = BIT_WORD(start);
+	const unsigned long offset = start % BITS_PER_LONG;
+	unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
+	const unsigned long carry = (offset + nbits) % BITS_PER_LONG;
+
+	value &= mask;
+	if (offset + nbits <= BITS_PER_LONG) {
+		value <<= (BITS_PER_LONG - offset - nbits);
+		mask <<= (BITS_PER_LONG - offset - nbits);
+		map[index] &= ~mask;
+		map[index] |= value;
+		return;
+	}
+	map[index] &= ~BITMAP_LAST_WORD_MASK(BITS_PER_LONG - offset);
+	map[index] |= (value >> (carry));
+	value &= BITMAP_LAST_WORD_MASK(carry);
+	map[index + 1] &= ~BITMAP_FIRST_WORD_MASK(BITS_PER_LONG - carry);
+	map[index + 1] |= value << (BITS_PER_LONG - carry);
+}
+
 #endif /* __ASSEMBLY__ */
 
 #endif /* __LINUX_BITMAP_H */
-- 
2.41.0.255.g8b1d071c50-goog


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 1/5] lib/bitmap: add bitmap_{set,get}_value_unaligned()

[Andy Shevchenko]

+Cc: William

On Thu, Jul 13, 2023 at 02:57:01PM +0200, Alexander Potapenko wrote:
> 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/linux-kernel@vger.kernel.org/msg2195426.html

-- 
With Best Regards,
Andy Shevchenko



_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 1/5] lib/bitmap: add bitmap_{set,get}_value_unaligned()

[Alexander Potapenko]

On Thu, Jul 13, 2023 at 7:29 PM Andy Shevchenko
<andriy.shevchenko@linux.intel.com> wrote:
>
> +Cc: William
>
> On Thu, Jul 13, 2023 at 02:57:01PM +0200, Alexander Potapenko wrote:
> > 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/linux-kernel@vger.kernel.org/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.

> --
> With Best Regards,
> Andy Shevchenko
>
>


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

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 1/5] lib/bitmap: add bitmap_{set,get}_value_unaligned()

[Andy Shevchenko]

On Thu, Jul 13, 2023 at 08:05:34PM +0200, Alexander Potapenko wrote:
> On Thu, Jul 13, 2023 at 7:29 PM Andy Shevchenko
> <andriy.shevchenko@linux.intel.com> wrote:
> >
> > +Cc: William
> >
> > On Thu, Jul 13, 2023 at 02:57:01PM +0200, Alexander Potapenko wrote:
> > > 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/linux-kernel@vger.kernel.org/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.

-- 
With Best Regards,
Andy Shevchenko



_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 1/5] lib/bitmap: add bitmap_{set,get}_value_unaligned()

[William Breathitt Gray]

[-- Attachment #1.1: Type: text/plain, Size: 1762 bytes --]

On Fri, Jul 14, 2023 at 11:04:16AM +0300, Andy Shevchenko wrote:
> On Thu, Jul 13, 2023 at 08:05:34PM +0200, Alexander Potapenko wrote:
> > On Thu, Jul 13, 2023 at 7:29 PM Andy Shevchenko
> > <andriy.shevchenko@linux.intel.com> wrote:
> > >
> > > +Cc: William
> > >
> > > On Thu, Jul 13, 2023 at 02:57:01PM +0200, Alexander Potapenko wrote:
> > > > 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/linux-kernel@vger.kernel.org/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.
> 
> -- 
> With Best Regards,
> Andy Shevchenko

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.

William Breathitt Gray

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 1/5] lib/bitmap: add bitmap_{set,get}_value_unaligned()

[Andy Shevchenko]

On Fri, Jul 14, 2023 at 07:19:15AM -0400, William Breathitt Gray wrote:
> On Fri, Jul 14, 2023 at 11:04:16AM +0300, Andy Shevchenko wrote:
> > On Thu, Jul 13, 2023 at 08:05:34PM +0200, Alexander Potapenko wrote:
> > > On Thu, Jul 13, 2023 at 7:29 PM Andy Shevchenko
> > > <andriy.shevchenko@linux.intel.com> wrote:
> > > > On Thu, Jul 13, 2023 at 02:57:01PM +0200, Alexander Potapenko wrote:
> > > > > 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/linux-kernel@vger.kernel.org/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.
> 
> 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.

Agree, thank you for your comments!

-- 
With Best Regards,
Andy Shevchenko



_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 1/5] lib/bitmap: add bitmap_{set,get}_value_unaligned()

[Alexander Potapenko]

On Fri, Jul 14, 2023 at 1:28 PM Andy Shevchenko
<andriy.shevchenko@linux.intel.com> wrote:
>
> On Fri, Jul 14, 2023 at 07:19:15AM -0400, William Breathitt Gray wrote:
> > On Fri, Jul 14, 2023 at 11:04:16AM +0300, Andy Shevchenko wrote:
> > > On Thu, Jul 13, 2023 at 08:05:34PM +0200, Alexander Potapenko wrote:
> > > > On Thu, Jul 13, 2023 at 7:29 PM Andy Shevchenko
> > > > <andriy.shevchenko@linux.intel.com> wrote:
> > > > > On Thu, Jul 13, 2023 at 02:57:01PM +0200, Alexander Potapenko wrote:
> > > > > > 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/linux-kernel@vger.kernel.org/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.
> >
> > 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.
>
> Agree, thank you for your comments!
>
> --
> With Best Regards,
> Andy Shevchenko
>
>
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).

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 1/5] lib/bitmap: add bitmap_{set,get}_value_unaligned()

[Andy Shevchenko]

On Fri, Jul 14, 2023 at 02:07:45PM +0200, Alexander Potapenko wrote:
> On Fri, Jul 14, 2023 at 1:28 PM Andy Shevchenko
> <andriy.shevchenko@linux.intel.com> wrote:
> > On Fri, Jul 14, 2023 at 07:19:15AM -0400, William Breathitt Gray wrote:
> > > On Fri, Jul 14, 2023 at 11:04:16AM +0300, Andy Shevchenko wrote:
> > > > On Thu, Jul 13, 2023 at 08:05:34PM +0200, Alexander Potapenko wrote:

...

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

Sounds good to me.

-- 
With Best Regards,
Andy Shevchenko



_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

[v2 2/5] lib/test_bitmap: add tests for bitmap_{set,get}_value_unaligned

[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.

Signed-off-by: Alexander Potapenko <glider@google.com>
---
 lib/test_bitmap.c | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)

diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 187f5b2db4cf1..8ca61f6e7f26e 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -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,26 @@ static void __init test_bitmap_const_eval(void)
 	BUILD_BUG_ON(~var != ~BIT(25));
 }
 
+static void __init test_set_get_value_unaligned(void)
+{
+	DECLARE_BITMAP(bitmap, BITS_PER_LONG * 2);
+	unsigned long val;
+	int i;
+
+	for (i = 0; i < BITS_PER_LONG * 2 - 7; i++) {
+		bitmap_zero(bitmap, BITS_PER_LONG * 2);
+		bitmap_set_value_unaligned(bitmap, 0b10101UL, i, 5);
+		val = bitmap_get_value_unaligned(bitmap, i, 5);
+		expect_eq_ulong(0b10101UL, val);
+		bitmap_set_value_unaligned(bitmap, 0b101UL, i + 5, 3);
+		val = bitmap_get_value_unaligned(bitmap, i + 5, 3);
+		expect_eq_ulong(0b101UL, val);
+		val = bitmap_get_value_unaligned(bitmap, i, 8);
+		expect_eq_ulong(0b10101101UL, val);
+	}
+}
+
+
 static void __init selftest(void)
 {
 	test_zero_clear();
@@ -1249,6 +1281,8 @@ static void __init selftest(void)
 	test_for_each_clear_bitrange_from();
 	test_for_each_set_clump8();
 	test_for_each_set_bit_wrap();
+
+	test_set_get_value_unaligned();
 }
 
 KSTM_MODULE_LOADERS(test_bitmap);
-- 
2.41.0.255.g8b1d071c50-goog


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

[v2 3/5] arm64: mte: implement CONFIG_ARM64_MTE_COMP

[Alexander Potapenko]

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.

Suggested-by: Evgenii Stepanov <eugenis@google.com>
Signed-off-by: Alexander Potapenko <glider@google.com>

---
 v2:
  - as suggested by Yuri Norov, switched from struct bitq (which is
    not needed anymore) to <linux/bitmap.h>
  - add missing symbol exports
---
 arch/arm64/Kconfig               |  10 +
 arch/arm64/include/asm/mtecomp.h |  60 +++++
 arch/arm64/mm/Makefile           |   1 +
 arch/arm64/mm/mtecomp.c          | 412 +++++++++++++++++++++++++++++++
 4 files changed, 483 insertions(+)
 create mode 100644 arch/arm64/include/asm/mtecomp.h
 create mode 100644 arch/arm64/mm/mtecomp.c

diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig
index 7856c3a3e35af..0aa727888e746 100644
--- a/arch/arm64/Kconfig
+++ b/arch/arm64/Kconfig
@@ -2091,6 +2091,16 @@ 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 MTE"
+	default y
+	depends on ARM64_MTE
+	help
+	  Enable tag compression support for ARM64 MTE.
+
+	  128-byte tag buffers corresponding to 4K pages can be compressed using
+	  the EA0 algorithm to save heap memory.
+
 config ARM64_SVE
 	bool "ARM Scalable Vector Extension support"
 	default y
diff --git a/arch/arm64/include/asm/mtecomp.h b/arch/arm64/include/asm/mtecomp.h
new file mode 100644
index 0000000000000..65a3730cc50d9
--- /dev/null
+++ b/arch/arm64/include/asm/mtecomp.h
@@ -0,0 +1,60 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef __ASM_MTECOMP_H
+#define __ASM_MTECOMP_H
+
+#include <linux/types.h>
+
+/*
+ * ea0_compress() - compress the given tag array.
+ * @tags: 128-byte array to read the tags from.
+ *
+ * Compresses the tags and returns a 64-bit opaque handle pointing to the
+ * tag storage. May allocate memory, which is freed by @ea0_release_handle().
+ */
+u64 ea0_compress(u8 *tags);
+
+/*
+ * ea0_decompress() - decompress the tag array addressed by the handle.
+ * @handle: handle returned by @ea0_decompress()
+ * @tags: 128-byte array to write the tags to.
+ *
+ * Reads the compressed data and writes it into the user-supplied tag array.
+ * Returns true on success, false on error.
+ */
+bool ea0_decompress(u64 handle, u8 *tags);
+
+/*
+ * ea0_release_handle() - release the handle returned by ea0_compress().
+ * @handle: handle returned by ea0_compress().
+ */
+void ea0_release_handle(u64 handle);
+
+/* Functions below are exported for testing purposes. */
+
+/*
+ * ea0_storage_size() - calculate the memory occupied by compressed tags.
+ * @handle: storage handle returned by ea0_compress.
+ */
+int ea0_storage_size(u64 handle);
+
+/*
+ * ea0_tags_to_ranges() - break @tags into arrays of tag ranges.
+ * @tags: 128-byte array containing 256 MTE tags.
+ * @out_tags: u8 array to store the tag of every range.
+ * @out_sizes: u16 array to store the size of every range.
+ * @out_len: length of @out_tags and @out_sizes (output parameter, initially
+ *           equal to lengths of out_tags[] and out_sizes[]).
+ */
+void ea0_tags_to_ranges(u8 *tags, u8 *out_tags, short *out_sizes, int *out_len);
+
+/*
+ * ea0_ranges_to_tags() - fill @tags using given tag ranges.
+ * @r_tags: u8[256] containing the tag of every range.
+ * @r_sizes: u16[256] containing the size of every range.
+ * @r_len: length of @r_tags and @r_sizes.
+ * @tags: 128-byte array to write the tags to.
+ */
+void ea0_ranges_to_tags(u8 *r_tags, short *r_sizes, int r_len, u8 *tags);
+
+#endif // __ASM_MTECOMP_H
diff --git a/arch/arm64/mm/Makefile b/arch/arm64/mm/Makefile
index dbd1bc95967d0..46778f6dd83c2 100644
--- a/arch/arm64/mm/Makefile
+++ b/arch/arm64/mm/Makefile
@@ -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
diff --git a/arch/arm64/mm/mtecomp.c b/arch/arm64/mm/mtecomp.c
new file mode 100644
index 0000000000000..e6c1026bd7e89
--- /dev/null
+++ b/arch/arm64/mm/mtecomp.c
@@ -0,0 +1,412 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+/*
+ * MTE tag compression algorithm.
+ * Proposed by Evgenii Stepanov <eugenis@google.com>
+ */
+
+/*
+ * 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.
+ */
+
+#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>
+
+/* The handle must fit into an Xarray value. */
+#define HANDLE_MASK ~(BIT_ULL(63))
+
+/* Out-of-line handles have 0b111 in bits 62..60. */
+#define NOINLINE_MASK (BIT_ULL(62) | BIT_ULL(61) | BIT_ULL(60))
+
+/* Cache index is stored in the lowest pointer bits. */
+#define CACHE_ID_MASK (BIT_ULL(2) | BIT_ULL(1) | BIT_ULL(0))
+
+/* Four separate caches to store out-of-line data. */
+#define NUM_CACHES 4
+static struct kmem_cache *mtecomp_caches[NUM_CACHES];
+
+/* 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) {
+	case 1:
+		return 16;
+	case 2:
+		return 32;
+	case 3:
+		return 64;
+	default:
+		return 128;
+	}
+}
+
+/* Transform tags into tag ranges. */
+void ea0_tags_to_ranges(u8 *tags, u8 *out_tags, short *out_sizes, int *out_len)
+{
+	u8 prev_tag = 0xff;
+	int cur_idx = -1;
+	u8 cur_tag;
+	int i;
+
+	memset(out_tags, 0, *out_len * sizeof(*out_tags));
+	memset(out_sizes, 0, *out_len * sizeof(*out_sizes));
+	for (i = 0; i < MTE_GRANULES_PER_PAGE; i++) {
+		cur_tag = tags[i / 2];
+		if (i % 2)
+			cur_tag = cur_tag % 16;
+		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;
+		}
+	}
+	*out_len = cur_idx + 1;
+}
+EXPORT_SYMBOL(ea0_tags_to_ranges);
+
+/* Transform tag ranges back into tags. */
+void ea0_ranges_to_tags(u8 *r_tags, short *r_sizes, int r_len, u8 *tags)
+{
+	int i, j, pos = 0;
+	u8 prev;
+
+	for (i = 0; i < r_len; i++) {
+		for (j = 0; j < r_sizes[i]; j++) {
+			if (pos % 2 == 0)
+				prev = r_tags[i];
+			else
+				tags[pos / 2] = (prev << 4) | r_tags[i];
+			pos++;
+		}
+	}
+}
+EXPORT_SYMBOL(ea0_ranges_to_tags);
+
+/* Translate @num_ranges into the allocation size needed to hold them. */
+static int ea0_alloc_size(int num_ranges)
+{
+	if (num_ranges <= 6)
+		return 8;
+	if (num_ranges <= 11)
+		return 16;
+	if (num_ranges <= 23)
+		return 32;
+	if (num_ranges <= 46)
+		return 64;
+	return 128;
+}
+
+/* Translate allocation size into maximum number of ranges that it can hold. */
+static int ea0_size_to_ranges(int size)
+{
+	switch (size) {
+	case 8:
+		return 6;
+	case 16:
+		return 11;
+	case 32:
+		return 23;
+	case 64:
+		return 46;
+	default:
+		return 0;
+	}
+}
+
+/* Is the data stored inline in the handle itself? */
+static bool ea0_is_inline(u64 handle)
+{
+	return (handle & NOINLINE_MASK) != NOINLINE_MASK;
+}
+
+/* Get the size of the buffer backing @handle. */
+int ea0_storage_size(u64 handle)
+{
+	if (ea0_is_inline(handle))
+		return 8;
+	return ea0_cache_id_to_size(handle & CACHE_ID_MASK);
+}
+EXPORT_SYMBOL(ea0_storage_size);
+
+/* Compress ranges into the buffer of the given length. */
+static void ea0_compress_to_buf(int len, u8 *tags, short *sizes, u8 *buf,
+				int buflen)
+{
+	int largest_idx = -1, i;
+	short largest = 0;
+	unsigned long bit_pos = 0;
+
+	for (i = 0; i < len; i++) {
+		if (i == len)
+			break;
+		if (sizes[i] > largest) {
+			largest = sizes[i];
+			largest_idx = i;
+		}
+	}
+	if (len <= 6) {
+		/* Inline case, @buflen <= 8. */
+		bitmap_set_value_unaligned((unsigned long *)buf, largest_idx,
+					   bit_pos, 4);
+		bit_pos += 4;
+	} else {
+		bitmap_set_value_unaligned((unsigned long *)buf, largest_idx,
+					   bit_pos, 6);
+		bit_pos += 6;
+	}
+	for (i = 0; i < len; i++) {
+		bitmap_set_value_unaligned((unsigned long *)buf, tags[i],
+					   bit_pos, 4);
+		bit_pos += 4;
+	}
+	for (i = len; i < ea0_size_to_ranges(buflen); i++) {
+		bitmap_set_value_unaligned((unsigned long *)buf, 0, bit_pos, 4);
+		bit_pos += 4;
+	}
+	for (i = 0; i < len; i++) {
+		if (i == largest_idx)
+			continue;
+		bitmap_set_value_unaligned((unsigned long *)buf, sizes[i],
+					   bit_pos, 7);
+		bit_pos += 7;
+	}
+}
+
+/* Compress the data inline. */
+static u64 ea0_compress_inline(int len, u8 *tags, short *sizes)
+{
+	u64 result;
+
+	ea0_compress_to_buf(len, tags, sizes, (u8 *)&result, sizeof(result));
+	result = be64_to_cpu(result);
+	return result;
+}
+
+/* Compress @tags and return a handle. */
+u64 ea0_compress(u8 *tags)
+{
+	int alloc_size, cache_id;
+	struct kmem_cache *cache;
+	short r_sizes[256];
+	u8 r_tags[256];
+	int r_len = ARRAY_SIZE(r_tags);
+	u8 *storage;
+
+	ea0_tags_to_ranges(tags, r_tags, r_sizes, &r_len);
+	alloc_size = ea0_alloc_size(r_len);
+	if (alloc_size == 8)
+		return ea0_compress_inline(r_len, r_tags, r_sizes);
+	cache_id = ea0_size_to_cache_id(alloc_size);
+	cache = mtecomp_caches[cache_id];
+	storage = kmem_cache_alloc(cache, GFP_KERNEL);
+	if (alloc_size < 128) {
+		ea0_compress_to_buf(r_len, r_tags, r_sizes, storage,
+				    alloc_size);
+		return ((u64)storage | cache_id) & HANDLE_MASK;
+	}
+	memcpy(storage, tags, alloc_size);
+	return (u64)storage & HANDLE_MASK;
+}
+EXPORT_SYMBOL(ea0_compress);
+
+/* Decompress the contents of the given buffer into @tags. */
+static bool ea0_decompress_from_buf(u8 *buf, int buflen, u8 *tags)
+{
+	int largest_idx, i, r_len = ea0_size_to_ranges(buflen);
+	short r_sizes[46], sum = 0;
+	u8 r_tags[46];
+	unsigned long bit_pos = 0, l_bits = (buflen == 8) ? 4 : 6;
+
+	largest_idx = bitmap_get_value_unaligned((unsigned long *)buf, bit_pos,
+						 l_bits);
+	bit_pos += l_bits;
+	for (i = 0; i < r_len; i++) {
+		r_tags[i] = bitmap_get_value_unaligned((unsigned long *)buf,
+						       bit_pos, 4);
+		bit_pos += 4;
+	}
+	for (i = 0; i < r_len; i++) {
+		if (i == largest_idx)
+			continue;
+		r_sizes[i] = bitmap_get_value_unaligned((unsigned long *)buf,
+							bit_pos, 7);
+		bit_pos += 7;
+		if (!r_sizes[i]) {
+			r_len = i;
+			break;
+		}
+		sum += r_sizes[i];
+	}
+	if (sum >= 256)
+		return false;
+	r_sizes[largest_idx] = 256 - sum;
+	ea0_ranges_to_tags(r_tags, r_sizes, r_len, tags);
+	return true;
+}
+
+/* Get pointer to the out-of-line storage from a handle. */
+static void *ea0_storage(u64 handle)
+{
+	if (ea0_is_inline(handle))
+		return NULL;
+	return (void *)((handle & (~CACHE_ID_MASK)) | BIT_ULL(63));
+}
+
+/* Decompress tags from the buffer referenced by @handle. */
+bool ea0_decompress(u64 handle, u8 *tags)
+{
+	u8 *storage = ea0_storage(handle);
+	int size = ea0_storage_size(handle);
+
+	if (size == 128) {
+		memcpy(tags, storage, size);
+		return true;
+	}
+	if (size == 8) {
+		handle = cpu_to_be64(handle);
+		return ea0_decompress_from_buf((u8 *)&handle, sizeof(handle),
+					       tags);
+	}
+	return ea0_decompress_from_buf(storage, size, tags);
+}
+EXPORT_SYMBOL(ea0_decompress);
+
+/* Release the memory referenced by @handle. */
+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;
+
+	c = mtecomp_caches[ea0_size_to_cache_id(size)];
+	kmem_cache_free(c, storage);
+}
+EXPORT_SYMBOL(ea0_release_handle);
+
+/* Set up mtecomp_caches[]. */
+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;
+}
+
+module_init(mtecomp_init);
-- 
2.41.0.255.g8b1d071c50-goog


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 3/5] arm64: mte: implement CONFIG_ARM64_MTE_COMP

[Alexander Potapenko]

> +/* Compress the data inline. */
> +static u64 ea0_compress_inline(int len, u8 *tags, short *sizes)
> +{
> +       u64 result;
> +
> +       ea0_compress_to_buf(len, tags, sizes, (u8 *)&result, sizeof(result));
> +       result = be64_to_cpu(result);
This be64_to_cpu() is leftover from the previous compressor
implementation which treated u64 as u8[8] (i.e. big-endian).
The new implementation works with the native u64 representation, so
the conversion is not needed anymore (and actually produces invalid
handles that can't be stored in Xarray).
I will drop this call in v3.


> +bool ea0_decompress(u64 handle, u8 *tags)
> +{
> +       u8 *storage = ea0_storage(handle);
> +       int size = ea0_storage_size(handle);
> +
> +       if (size == 128) {
> +               memcpy(tags, storage, size);
> +               return true;
> +       }
> +       if (size == 8) {
> +               handle = cpu_to_be64(handle);
Ditto.

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 3/5] arm64: mte: implement CONFIG_ARM64_MTE_COMP

[Andy Shevchenko]

On Thu, Jul 13, 2023 at 02:57:03PM +0200, Alexander Potapenko wrote:
> 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.

> + *
> + *
> + *

Isn't a bit too many blank lines?

> + * 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)
> + *
> + *
> + *

Ditto.

> + * 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.
> + */

...

> +#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/*

...

> +#define HANDLE_MASK ~(BIT_ULL(63))

GENMASK_ULL(62, 0)

...

> +/* Out-of-line handles have 0b111 in bits 62..60. */
> +#define NOINLINE_MASK (BIT_ULL(62) | BIT_ULL(61) | BIT_ULL(60))

GENMASK_ULL()?

...

> +/* Cache index is stored in the lowest pointer bits. */
> +#define CACHE_ID_MASK (BIT_ULL(2) | BIT_ULL(1) | BIT_ULL(0))

Ditto.

...

> +/* 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) {
> +	case 1:
> +		return 16;
> +	case 2:
> +		return 32;
> +	case 3:
> +		return 64;
> +	default:
> +		return 128;
> +	}
> +}

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

...

> +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?

> +	int cur_idx = -1;
> +	u8 cur_tag;
> +	int i;
> +
> +	memset(out_tags, 0, *out_len * sizeof(*out_tags));
> +	memset(out_sizes, 0, *out_len * sizeof(*out_sizes));

array_size() ?

> +	for (i = 0; i < MTE_GRANULES_PER_PAGE; i++) {
> +		cur_tag = tags[i / 2];
> +		if (i % 2)
> +			cur_tag = cur_tag % 16;
> +		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?

> +	}
> +	*out_len = cur_idx + 1;
> +}

> +void ea0_ranges_to_tags(u8 *r_tags, short *r_sizes, int r_len, u8 *tags)
> +{
> +	int i, j, pos = 0;
> +	u8 prev;
> +
> +	for (i = 0; i < r_len; i++) {
> +		for (j = 0; j < r_sizes[i]; j++) {

> +			if (pos % 2 == 0)

Would be better to keep this aligned with above?

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

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

...

> +EXPORT_SYMBOL(ea0_storage_size);

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

...

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

Interesting dead code. What was the idea behind this?

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

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

...

> +		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);

> +		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.

...

> +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?

...

> +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;
> +}

> +

Unneeded blank line.

> +module_init(mtecomp_init);

-- 
With Best Regards,
Andy Shevchenko



_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 3/5] arm64: mte: implement CONFIG_ARM64_MTE_COMP

[Yury Norov]

> > +		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);
> 
> > +		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.

Big-endian arches are not OK. Out-of-boundary access is not OK when
the buf is not exactly a multiple of words.

> > +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?

This approach is called 'defensive programming' as I learned from
previous iteration. Another interesting thing is that the only caller
of the function in patch #5 explicitly checks the handle for NULL, so
we're surely double-defensed here.

        +void _mte_free_saved_tags(void *storage)
        +{
        +       unsigned long handle = xa_to_value(storage);
        +       int size;
        +
        +       if (!handle)
        +               return;
        +       size = ea0_storage_size(handle);
        +       ea0_release_handle(handle);
        +}

_mte_free_saved_tags() calculates size, but doesn't use it in any form,
just to calculate it again in callee...

Thanks,
Yury

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 3/5] arm64: mte: implement CONFIG_ARM64_MTE_COMP

[Andy Shevchenko]

On Thu, Jul 13, 2023 at 12:27:15PM -0700, Yury Norov wrote:

...

> > > +	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.

No, this approach called "let compiler optimize the check away". :-)

When compiler sees something like

	TYPE bar = MACRO(foo); // FUNC(foo);

	if (!foo)
		blalblabla;

the conditional can be eliminated as the optimizer thinks the way "okay,
developer already _used_ the foo in some code, it means it can't not be NULL,
let's drop a dead code".

(Yes, I know what defensive programming means and we actually quite rarely
 use it in the kernel for the internal APIs)

-- 
With Best Regards,
Andy Shevchenko



_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 3/5] arm64: mte: implement CONFIG_ARM64_MTE_COMP

[Alexander Potapenko]

> > + *
> > + *
> > + *
>
> Isn't a bit too many blank lines?

Will fix in v3, thanks!

> > + *
> > + *
> > + *
>
> Ditto.
Ack

> ...
>
> > +#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/*

Done (here and in other files).

> ...
>
> > +#define HANDLE_MASK ~(BIT_ULL(63))
>
> GENMASK_ULL(62, 0)
Done (here and below)

> 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.


> > +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?
This is an invalid tag value, let it be U8_MAX.


> > +     memset(out_tags, 0, *out_len * sizeof(*out_tags));
> > +     memset(out_sizes, 0, *out_len * sizeof(*out_sizes));
>
> array_size() ?
Done

>
> > +     for (i = 0; i < MTE_GRANULES_PER_PAGE; i++) {
> > +             cur_tag = tags[i / 2];
> > +             if (i % 2)
> > +                     cur_tag = cur_tag % 16;
> > +             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?

Done


> > +                     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.

>
> ...
>
> > +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?

>
> ...
>
> > +     for (i = 0; i < len; i++) {
> > +             if (i == len)
> > +                     break;
>
> Interesting dead code. What was the idea behind this?

Haha, no idea :)
Removed it.

>
> > +             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?


>
> > +             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.

In fact it makes sense to make buf an unsigned long*, we don't treat
it as a byte array anywhere else.

> ...
>
> > +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?

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.

>
> ...
>
> > +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;
> > +}
>
> > +
>
> 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

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 3/5] arm64: mte: implement CONFIG_ARM64_MTE_COMP

[Andy Shevchenko]

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

...

> > 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.

...

> > > +                     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.

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

	if (pos % 2)

kinda quicker to read and understand in my opinion.

...

> > > +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?

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

...

> > > +             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?

There will be (via ASoC tree and maybe IIO tree later on) in v6.6-rc1, but
as I think it can't be used anyway because you need the index of the value
as well.

...

> > > +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?
> 
> 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.

Even if it's a simple pointer arithmetics, the storage might (theoretically?)
have a dangling pointer, no?

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

...

> > > +
> >
> > 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.

-- 
With Best Regards,
Andy Shevchenko



_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [v2 3/5] arm64: mte: implement CONFIG_ARM64_MTE_COMP

[Alexander Potapenko]

On Fri, Jul 14, 2023 at 12:47 PM Andy Shevchenko
<andriy.shevchenko@linux.intel.com> wrote:
>
> On Fri, Jul 14, 2023 at 11:25:41AM +0200, Alexander Potapenko wrote:
>
> ...
>
> > > 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.
>
> ...
>
> > > > +                     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.
>
> Not big deal, but less characters improve the brain process, so
>
>         if (pos % 2)
>
> kinda quicker to read and understand in my opinion.

Ok, will do.

> ...
>
> > > > +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?
>
> I think you always need to include MODULE_IMPORT_NS for the sake of
> robustness of the code.

Thanks! The docs aren't very specific on this.



> ...
>
> > > > +
> > >
> > > 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.

Fair enough, will fix.

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

[v2 4/5] arm64: mte: add a test for MTE tags compression

[Alexander Potapenko]

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

Signed-off-by: Alexander Potapenko <glider@google.com>
---
 arch/arm64/Kconfig           |  10 ++
 arch/arm64/mm/Makefile       |   1 +
 arch/arm64/mm/test_mtecomp.c | 175 +++++++++++++++++++++++++++++++++++
 3 files changed, 186 insertions(+)
 create mode 100644 arch/arm64/mm/test_mtecomp.c

diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig
index 0aa727888e746..9473c1e2e8593 100644
--- a/arch/arm64/Kconfig
+++ b/arch/arm64/Kconfig
@@ -2101,6 +2101,16 @@ config ARM64_MTE_COMP
 	  128-byte tag buffers corresponding to 4K pages can be compressed using
 	  the EA0 algorithm to save heap memory.
 
+config ARM64_MTE_COMP_KUNIT_TEST
+	tristate "Test tag compression for ARM64 MTE" if !KUNIT_ALL_TESTS
+	default KUNIT_ALL_TESTS
+	depends on KUNIT && ARM64_MTE_COMP
+	help
+	  Test EA0 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
diff --git a/arch/arm64/mm/Makefile b/arch/arm64/mm/Makefile
index 46778f6dd83c2..170dc62b010b9 100644
--- a/arch/arm64/mm/Makefile
+++ b/arch/arm64/mm/Makefile
@@ -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
diff --git a/arch/arm64/mm/test_mtecomp.c b/arch/arm64/mm/test_mtecomp.c
new file mode 100644
index 0000000000000..67bef6f28dac4
--- /dev/null
+++ b/arch/arm64/mm/test_mtecomp.c
@@ -0,0 +1,175 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Test cases for EA0, the compression algorithm for MTE tags.
+ */
+
+#include <asm/mtecomp.h>
+#include <kunit/test.h>
+#include <linux/slab.h>
+#include <linux/types.h>
+
+/*
+ * Test that ea0_tags_to_ranges() produces a single range for a zero-filled tag
+ * buffer.
+ */
+static void test_tags_to_ranges_zero(struct kunit *test)
+{
+	u8 tags[128], dtags[128];
+	short r_sizes[256];
+	int r_len = 256;
+	u8 r_tags[256];
+
+	memset(tags, 0, 128);
+	ea0_tags_to_ranges(tags, r_tags, r_sizes, &r_len);
+	KUNIT_EXPECT_EQ(test, r_len, 1);
+	KUNIT_EXPECT_EQ(test, r_tags[0], 0);
+	KUNIT_EXPECT_EQ(test, r_sizes[0], 256);
+	ea0_ranges_to_tags(r_tags, r_sizes, r_len, dtags);
+	KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0);
+}
+
+/*
+ * Test that a small number of different tags is correctly transformed into
+ * ranges.
+ */
+static void test_tags_to_ranges_simple(struct kunit *test)
+{
+	u8 tags[128], dtags[128];
+	const u8 ex_tags[] = { 0xa, 0x0, 0xa, 0xb, 0x0 };
+	const short ex_sizes[] = { 1, 2, 2, 1, 250 };
+	short r_sizes[256];
+	int r_len = 256;
+	u8 r_tags[256];
+
+	memset(tags, 0, 128);
+	tags[0] = 0xa0;
+	tags[1] = 0x0a;
+	tags[2] = 0xab;
+	ea0_tags_to_ranges(tags, r_tags, r_sizes, &r_len);
+	KUNIT_EXPECT_EQ(test, r_len, 5);
+	KUNIT_EXPECT_EQ(test, memcmp(r_tags, ex_tags, sizeof(ex_tags)), 0);
+	KUNIT_EXPECT_EQ(test, memcmp(r_sizes, ex_sizes, sizeof(ex_sizes)), 0);
+	ea0_ranges_to_tags(r_tags, r_sizes, r_len, dtags);
+	KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0);
+}
+
+/* Test that repeated 0xa0 byte produces 256 ranges of length 1. */
+static void test_tags_to_ranges_repeated(struct kunit *test)
+{
+	u8 tags[128], dtags[128];
+	short r_sizes[256];
+	int r_len = 256;
+	u8 r_tags[256];
+
+	memset(tags, 0xa0, 128);
+	ea0_tags_to_ranges(tags, r_tags, r_sizes, &r_len);
+	KUNIT_EXPECT_EQ(test, r_len, 256);
+	ea0_ranges_to_tags(r_tags, r_sizes, r_len, dtags);
+	KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0);
+}
+
+/* Test that a zero-filled array is compressed into inline storage. */
+static void test_compress_zero(struct kunit *test)
+{
+	u8 tags[128], dtags[128];
+	u64 handle;
+
+	memset(tags, 0, 128);
+	handle = ea0_compress(tags);
+	KUNIT_EXPECT_EQ(test, handle & BIT_ULL(63), 0);
+	/* Tags are stored inline. */
+	KUNIT_EXPECT_EQ(test, ea0_storage_size(handle), 8);
+	KUNIT_EXPECT_TRUE(test, ea0_decompress(handle, dtags));
+	KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0);
+}
+
+/*
+ * Test that a very small number of tag ranges ends up compressed into 8 bytes.
+ */
+static void test_compress_simple(struct kunit *test)
+{
+	u8 tags[128], dtags[128];
+	u64 handle;
+
+	memset(tags, 0, 128);
+	tags[0] = 0xa0;
+	tags[1] = 0x0a;
+	tags[2] = 0xab;
+
+	handle = ea0_compress(tags);
+	KUNIT_EXPECT_EQ(test, handle & BIT_ULL(63), 0);
+	/* Tags are stored inline. */
+	KUNIT_EXPECT_EQ(test, ea0_storage_size(handle), 8);
+	KUNIT_EXPECT_TRUE(test, ea0_decompress(handle, dtags));
+	KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0);
+}
+
+/*
+ * Generate a buffer that will contain @nranges of tag ranges, test that it
+ * compresses into @exp_size bytes and decompresses into the original tag
+ * sequence.
+ */
+static void compress_range_helper(struct kunit *test, int nranges, int exp_size)
+{
+	u8 tags[128], dtags[128];
+	u64 handle;
+	int i;
+
+	memset(tags, 0, 128);
+
+	if (nranges > 1) {
+		nranges--;
+		for (i = 0; i < nranges / 2; i++)
+			tags[i] = 0xab;
+		if (nranges % 2)
+			tags[nranges / 2] = 0xa0;
+	}
+
+	handle = ea0_compress(tags);
+	KUNIT_EXPECT_EQ(test, handle & BIT_ULL(63), 0);
+	KUNIT_EXPECT_EQ(test, ea0_storage_size(handle), exp_size);
+	KUNIT_EXPECT_TRUE(test, ea0_decompress(handle, dtags));
+	KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0);
+}
+
+/*
+ * Test that every number of tag ranges is correctly compressed and
+ * decompressed.
+ */
+static void test_compress_ranges(struct kunit *test)
+{
+	int i, exp_size;
+
+	for (i = 1; i <= 256; i++) {
+		if (i < 7)
+			exp_size = 8;
+		else if (i < 12)
+			exp_size = 16;
+		else if (i < 24)
+			exp_size = 32;
+		else if (i < 47)
+			exp_size = 64;
+		else
+			exp_size = 128;
+		compress_range_helper(test, i, exp_size);
+	}
+}
+
+static struct kunit_case mtecomp_test_cases[] = {
+	KUNIT_CASE(test_tags_to_ranges_zero),
+	KUNIT_CASE(test_tags_to_ranges_simple),
+	KUNIT_CASE(test_tags_to_ranges_repeated),
+	KUNIT_CASE(test_compress_zero),
+	KUNIT_CASE(test_compress_simple),
+	KUNIT_CASE(test_compress_ranges),
+	{}
+};
+
+static struct kunit_suite mtecomp_test_suite = {
+	.name = "mtecomp",
+	.test_cases = mtecomp_test_cases,
+};
+kunit_test_suites(&mtecomp_test_suite);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Alexander Potapenko <glider@google.com>");
-- 
2.41.0.255.g8b1d071c50-goog


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

[v2 5/5] arm64: mte: add compression support to mteswap.c

[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 128-byte
tag buffers, as well as smaller buffers containing compressed tags, or
have compressed tags stored directly in them.

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 with the EA0 algorithm. 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 reach 20x and even more.

Signed-off-by: Alexander Potapenko <glider@google.com>
---
 arch/arm64/mm/Makefile         |  5 ++++
 arch/arm64/mm/mteswap.c        | 19 ++++++-------
 arch/arm64/mm/mteswap.h        | 12 ++++++++
 arch/arm64/mm/mteswap_comp.c   | 50 ++++++++++++++++++++++++++++++++++
 arch/arm64/mm/mteswap_nocomp.c | 37 +++++++++++++++++++++++++
 5 files changed, 112 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

diff --git a/arch/arm64/mm/Makefile b/arch/arm64/mm/Makefile
index 170dc62b010b9..46a798e2b67cb 100644
--- a/arch/arm64/mm/Makefile
+++ b/arch/arm64/mm/Makefile
@@ -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
 
diff --git a/arch/arm64/mm/mteswap.c b/arch/arm64/mm/mteswap.c
index cd508ba80ab1b..e072c1209fbb6 100644
--- a/arch/arm64/mm/mteswap.c
+++ b/arch/arm64/mm/mteswap.c
@@ -7,6 +7,8 @@
 #include <linux/swapops.h>
 #include <asm/mte.h>
 
+#include "mteswap.h"
+
 static DEFINE_XARRAY(mte_pages);
 
 void *mte_allocate_tag_storage(void)
@@ -27,20 +29,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 +53,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 +61,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 +75,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);
 }
diff --git a/arch/arm64/mm/mteswap.h b/arch/arm64/mm/mteswap.h
new file mode 100644
index 0000000000000..bf25f2b3e75a4
--- /dev/null
+++ b/arch/arm64/mm/mteswap.h
@@ -0,0 +1,12 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef ARCH_ARM64_MM_MTESWAP_H_
+#define ARCH_ARM64_MM_MTESWAP_H_
+
+#include <linux/mm_types.h>
+
+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_
diff --git a/arch/arm64/mm/mteswap_comp.c b/arch/arm64/mm/mteswap_comp.c
new file mode 100644
index 0000000000000..bc2591f8d4f35
--- /dev/null
+++ b/arch/arm64/mm/mteswap_comp.c
@@ -0,0 +1,50 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/* MTE tag storage management with EA0 compression. */
+
+#include <asm/mte.h>
+#include <asm/mtecomp.h>
+#include <linux/pagemap.h>
+#include <linux/slab.h>
+#include <linux/swap.h>
+#include <linux/swapops.h>
+#include <linux/xarray.h>
+
+#include "mteswap.h"
+
+void *_mte_alloc_and_save_tags(struct page *page)
+{
+	u8 tags[128];
+	u64 handle;
+
+	mte_save_page_tags(page_address(page), tags);
+	handle = ea0_compress(tags);
+	return xa_mk_value(handle);
+}
+
+void _mte_free_saved_tags(void *storage)
+{
+	unsigned long handle = xa_to_value(storage);
+	int size;
+
+	if (!handle)
+		return;
+	size = ea0_storage_size(handle);
+	ea0_release_handle(handle);
+}
+
+void _mte_restore_tags(void *tags, struct page *page)
+{
+	u64 handle = xa_to_value(tags);
+	u8 tags_decomp[128];
+
+	if (!handle)
+		return;
+
+	if (try_page_mte_tagging(page)) {
+		if (!ea0_decompress(handle, tags_decomp))
+			return;
+		mte_restore_page_tags(page_address(page), tags_decomp);
+		set_page_mte_tagged(page);
+	}
+}
diff --git a/arch/arm64/mm/mteswap_nocomp.c b/arch/arm64/mm/mteswap_nocomp.c
new file mode 100644
index 0000000000000..efcdac88b342d
--- /dev/null
+++ b/arch/arm64/mm/mteswap_nocomp.c
@@ -0,0 +1,37 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/* MTE tag storage management without compression support. */
+
+#include <asm/mte.h>
+#include <linux/pagemap.h>
+#include <linux/slab.h>
+#include <linux/swap.h>
+#include <linux/swapops.h>
+#include <linux/xarray.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)) {
+		mte_restore_page_tags(page_address(page), tags);
+		set_page_mte_tagged(page);
+	}
+}
-- 
2.41.0.255.g8b1d071c50-goog


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel