Implement MTE tag compression for swapped pages
Subsystems (2)
cover Implement MTE tag compression for swapped pages
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 introduce <linux/bitqueue.h>, which provides a simple bit queue interface.
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.
Alexander Potapenko (5):
linux/bitqueue.h: add the bit queue implementation linux/bitqueue.h: add a KUnit test for bitqueue.h
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 | 398 +++++++++++++++++++++++++++++++ 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/bitqueue.h | 144 +++++++++++ lib/Kconfig.debug | 8 + lib/Makefile | 1 + lib/test_bitqueue.c | 244 +++++++++++++++++++ 13 files changed, 1164 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 create mode 100644 include/linux/bitqueue.h create mode 100644 lib/test_bitqueue.c
Signature · 1 line
2.41.0.255.g8b1d071c50-goog
PATCH RESEND 1/5 linux/bitqueue.h: add the bit queue implementation
struct bitq represents a bit queue with external storage.
Its purpose is to easily pack sub-byte values, which can be used, for example, to implement RLE algorithms.
--- include/linux/bitqueue.h | 144 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 144 insertions(+) create mode 100644 include/linux/bitqueue.h
include/linux/bitqueue.h new file +144 -0
@@ -0,0 +1,144 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* +* A simple bit queue which supports enqueueing/dequeueing of sub-byte values. +* +* This can be used to pack complex bitfields into byte arrays. +*/ +#ifndef _LINUX_BITQUEUE_H +#define _LINUX_BITQUEUE_H + +#include <linux/string.h> +#include <linux/types.h> + +/** +* struct bitq - represents a bit queue with external storage. +* @data: data buffer used by the queue. +* @size: size of @data in bytes. +* @bit_pos: current bit position. +*/ +struct bitq { +u8 *data; +int size, bit_pos; +}; + +/** +* bitq_init - initialize an empty bit queue. +* @q: struct bitq to be initialized. +* @data: external data buffer to use. +* @size: capacity in bytes. +* +* Return: 0 in the case of success, -1 if either of the pointers is NULL. +*/ +static inline int bitq_init (struct bitq *q,u8 *data,int size) +{ +if (!q || !data) +return -1 ; + q->data = data; + q->size = size; +memset (data,0 , size); + q->bit_pos =0 ; +return 0 ; +} + +/** +* bitq_init_full - make a bit queue from an initialized byte array. +* @q: struct bitq to be initialized. +* @data: external data buffer to use. +* @size: capacity in bytes. +* +* Return: 0 in the case of success, -1 if either of the pointers is NULL. +*/ +static inline int bitq_init_full (struct bitq *q,u8 *data,int size) +{ +if (!q || !data) +return -1 ; + q->data = data; + q->size = size; + q->bit_pos = q->size *8 ; +return 0 ; +} + +/** +* bitq_enqueue - push up to 8 bits to the end of the queue. +* @q: struct bitq. +* @value: byte containing the value to be pushed. +* @bits: number of bits (1 to 8) to push. +* +* Return: number of bits pushed, or -1 in the case of an error. +*/ +static inline int bitq_enqueue (struct bitq *q,u8 value,int bits) +{ +int byte_pos, left_in_byte, max_pos; +u8 hi, lo; + +if (!q || (bits <1 ) || (bits >8 )) +return -1 ; + + max_pos = q->size *8 ; +if ((max_pos - q->bit_pos) < bits) +return -1 ; + + left_in_byte =8 - (q->bit_pos %8 ); + byte_pos = q->bit_pos /8 ; +/* Clamp @value. */ + value %= (1 << bits); +if (left_in_byte >= bits) { +/* @value fits into the current byte. */ + value <<= (left_in_byte - bits); + q->data[byte_pos] |= value; + }else { +/* +* @value needs to be split between the current and the +* following bytes. +*/ + hi = value >> (bits - left_in_byte); + q->data[byte_pos] |= hi; + byte_pos++; + lo = value << (8 - (bits - left_in_byte)); + q->data[byte_pos] |= lo; + } + q->bit_pos += bits; +return bits; +} + +/** +* bitq_dequeue - pop up to 8 bits from the beginning of the queue. +* @q: struct bitq. +* @value: u8* to store the popped value (can be NULL). +* @bits: number of bits (1 to 8) to pop. +* +* Return: number of bits popped, or -1 in the case of an error. +*/ + +#include <linux/printk.h> +static inline int bitq_dequeue (struct bitq *q,u8 *value,int bits) +{ +int rem_bits =8 - bits, i; +u8 output; + +/* Invalid arguments. */ +if (!q || (bits <1 ) || (bits >8 )) +return -1 ; +/* Not enough space to insert @bits. */ +if (q->bit_pos < bits) +return -1 ; +/* Take the first @bits bits from the first byte. */ + output = q->data[0 ]; + output >>= rem_bits; +if (value) + *value = output; + +/* +* Shift every byte in the queue to the left by @bits, carrying over to +* the previous byte. +*/ +for (i =0 ; i < q->size -1 ; i++) { + q->data[i] = (q->data[i] << bits) | + (q->data[i +1 ] >> rem_bits); + } + q->data[q->size -1 ] <<= bits; + q->bit_pos -= bits; +return bits; +} + +#endif // _LINUX_BITQUEUE_H
Signature · 1 line
2.41.0.255.g8b1d071c50-goog
Re: [Resend v1 1/5] linux/bitqueue.h: add the bit queue implementation
+ Andy and Rasmus
Quoted 4 lines · Alexander Potapenko
struct bitq represents a bit queue with external storage.
Its purpose is to easily pack sub-byte values, which can be used, for example, to implement RLE algorithms.
Whatever it is, it's not a queue. The queue implies O(1) for insertion and deletion, but your 'dequeue' is clearly an O(n) procedure.
I'm not sure if I completely understand the purpose of the series, but from this description:
enqueueing/dequeueing of sub-byte values
I think, the simplest solution would be a circular queue (ringbuffer) based on bitmaps:
Init an empty 10-bit bitmap:
Head = 0
v
..... .....
^
Tail = 1
Enqueue 6-bit value 0b101010 at the end:
Head = 0
v
10101 0....
^
Tail = 1
Dequeue 3 bits from the beginning:
Head = 0
v
...01 0....
^
Tail = 1
And so on...
See some other comments inline.
Thanks,
Yury
Quoted 32 lines
Signed-off-by Alexander Potapenko <[email protected]>--- include/linux/bitqueue.h | 144 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 144 insertions(+) create mode 100644 include/linux/bitqueue.hinclude/linux/bitqueue.h new file +20
-0@@ -0,0 +1,144 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* +* A simple bit queue which supports enqueueing/dequeueing of sub-byte values. +* +* This can be used to pack complex bitfields into byte arrays. +*/ +#ifndef _LINUX_BITQUEUE_H +#define _LINUX_BITQUEUE_H + +#include <linux/string.h> +#include <linux/types.h> + +/** + * struct bitq - represents a bit queue with external storage. + * @data: data buffer used by the queue. + * @size: size of @data in bytes. + * @bit_pos: current bit position. + */ +struct bitq { + u8 *data;
include/linux/bitqueue.h line 30
Quoted 10 lines
include/linux/bitqueue.h new file +10
-0+int size, bit_pos; +}; + +/** +* bitq_init - initialize an empty bit queue. +* @q: struct bitq to be initialized. +* @data: external data buffer to use. +* @size: capacity in bytes. +* +* Return: 0 in the case of success, -1 if either of the pointers is NULL.
ENIVAL?
include/linux/bitqueue.h line 35
Quoted 5 lines
include/linux/bitqueue.h new file +5
-0+*/ +static inline int bitq_init (struct bitq *q,u8 *data,int size) +{ +if (!q || !data) +return -1 ;
This is a useless check. Erroneous code may (and often does) pass a broken pointer other than NULL.
And to make it worse, this error handling (instead of run-time segfault which can be easily caught at debugging) may make users think that passing NULL is the right thing. Check bit/bitmap and other kernel
functions: they don't check against NULL as a general rule, except for well-justified cases, like 'free(NULL)'.
include/linux/bitqueue.h line 38
Quoted 3 lines
include/linux/bitqueue.h new file +3
-0+ q->data = data; + q->size = size; +memset (data,0 , size);
Useless memset?
Quoted 11 lines
include/linux/bitqueue.h new file +11
-0+ q->bit_pos =0 ; +return 0 ; +} + +/** +* bitq_init_full - make a bit queue from an initialized byte array. +* @q: struct bitq to be initialized. +* @data: external data buffer to use. +* @size: capacity in bytes. +* +* Return: 0 in the case of success, -1 if either of the pointers is NULL.
include/linux/bitqueue.h line 59
Quoted 10 lines
include/linux/bitqueue.h new file +10
-0+*/ +static inline int bitq_init_full (struct bitq *q,u8 *data,int size) +{ +if (!q || !data) +return -1 ; + q->data = data; + q->size = size; + q->bit_pos = q->size *8 ; +return 0 ; +}
This all should not reside in a header.
Quoted 6 lines
include/linux/bitqueue.h new file +6
-0+ +/** +* bitq_enqueue - push up to 8 bits to the end of the queue. +* @q: struct bitq. +* @value: byte containing the value to be pushed. +* @bits: number of bits (1 to 8) to push.
include/linux/bitqueue.h line 75
Quoted 10 lines
include/linux/bitqueue.h new file +10
-0+* +* Return: number of bits pushed, or -1 in the case of an error. +*/ +static inline int bitq_enqueue (struct bitq *q,u8 value,int bits) +{ +int byte_pos, left_in_byte, max_pos; +u8 hi, lo; + +if (!q || (bits <1 ) || (bits >8 )) +return -1 ;
Pushing 0 elements in queue is usually not an error. Implementations usually return and do nothing. From the malloc() man page:
If size is 0, then malloc() returns a unique pointer value that can later be successfully passed to free().
include/linux/bitqueue.h line 79
Quoted 3 lines
include/linux/bitqueue.h new file +3
-0+ max_pos = q->size *8 ; +if ((max_pos - q->bit_pos) < bits) +return -1 ;
ENOMEM? Or probably better to resize the queue.
Quoted 10 lines
include/linux/bitqueue.h new file +10
-0+ + left_in_byte =8 - (q->bit_pos %8 ); + byte_pos = q->bit_pos /8 ; +/* Clamp @value. */ + value %= (1 << bits); +if (left_in_byte >= bits) { +/* @value fits into the current byte. */ + value <<= (left_in_byte - bits); + q->data[byte_pos] |= value; + }else {
include/linux/bitqueue.h line 99
Quoted 10 lines
include/linux/bitqueue.h new file +10
-0+/* +* @value needs to be split between the current and the +* following bytes. +*/ + hi = value >> (bits - left_in_byte); + q->data[byte_pos] |= hi; + byte_pos++; + lo = value << (8 - (bits - left_in_byte)); + q->data[byte_pos] |= lo; + }
This piece should be a bitmap_append() function, like:bitmap_append(addr, 3, 2, 0b11) would append 0b11 to the bitmap at offset 3. We already have bitmap_{set,get}_value8, so I suggest to extend the interface for unaligned offsets and lengths up to BITS_PER_LONG.
Quoted 29 lines
include/linux/bitqueue.h new file +29
-0+ q->bit_pos += bits; +return bits; +} + +/** +* bitq_dequeue - pop up to 8 bits from the beginning of the queue. +* @q: struct bitq. +* @value: u8* to store the popped value (can be NULL). +* @bits: number of bits (1 to 8) to pop. +* +* Return: number of bits popped, or -1 in the case of an error. +*/ + +#include <linux/printk.h> +static inline int bitq_dequeue (struct bitq *q,u8 *value,int bits) +{ +int rem_bits =8 - bits, i; +u8 output; + +/* Invalid arguments. */ +if (!q || (bits <1 ) || (bits >8 )) +return -1 ; +/* Not enough space to insert @bits. */ +if (q->bit_pos < bits) +return -1 ; +/* Take the first @bits bits from the first byte. */ + output = q->data[0 ]; + output >>= rem_bits; +if (value)
include/linux/bitqueue.h line 138
Quoted 10 lines
include/linux/bitqueue.h new file +10
-0+ *value = output; + +/* +* Shift every byte in the queue to the left by @bits, carrying over to +* the previous byte. +*/ +for (i =0 ; i < q->size -1 ; i++) { + q->data[i] = (q->data[i] << bits) | + (q->data[i +1 ] >> rem_bits); + }
As I already mentioned, this is O(N), which is wrong for queues. Add a pointer to the head in the bitq structure to avoid shifting every byte.
BTW, we've got bitmap_shift_{left,right} for this.
Quoted 8 lines
include/linux/bitqueue.h new file +6
-0+ q->data[q->size -1 ] <<= bits; + q->bit_pos -= bits; + return bits; +} + +#endif // _LINUX_BITQUEUE_H Signature · 1 line
2.41.0.255.g8b1d071c50-goog
Re: [Resend v1 1/5] linux/bitqueue.h: add the bit queue implementation
Quoted 11 lines · Yury Norov
+ Andy and Rasmus
Quoted 4 lines · Alexander Potapenko
struct bitq represents a bit queue with external storage.
Its purpose is to easily pack sub-byte values, which can be used, for example, to implement RLE algorithms.
Whatever it is, it's not a queue. The queue implies O(1) for insertion and deletion, but your 'dequeue' is clearly an O(n) procedure.
Thanks for spotting this!
I have indeed done a poor job implementing the dequeue method.
Quoted 1 line
I'm not sure if I completely understand the purpose of the series,
To implement tag compression, we need to serialize/deserialize "bit fields" looking e.g. like this:
int largest_idx : 6;
unsigned char tags[N] : 4*N;
unsigned char sizes[N-1] : 7*(N-1)to/from a byte array. This actually needs to be done only once, and enqueue()/dequeue() operations do not interleave, so there is no need for an actual queue.
I'll try to come up with something simple - maybe reimplement it as a ring buffer, or even skip the "ring" part, because it is not needed for my purpose.
(The struct may end up being less generic - in that case I'll move it from include/linux arch/arm64/mm/)
Quoted 16 lines
but
from this description:
enqueueing/dequeueing of sub-byte valuesI think, the simplest solution would be a circular queue (ringbuffer) based on bitmaps:
Quoted 7 lines
+/**
+ *bitq_init- initialize an empty bit queue.
+ * @q: struct bitq to be initialized.
+ * @data: external data buffer to use.
+ * @size: capacity in bytes.
+ *
+ * Return: 0 in the case of success, -1 if either of the pointers is NULL.
Quoted 1 line
ENIVAL?
Ack, better use the common error values.
Quoted 9 lines
include/linux/bitqueue.h line 35
Quoted 6 lines
+ */
include/linux/bitqueue.h new file +4
-0+static inline int bitq_init (struct bitq *q,u8 *data,int size) +{ +if (!q || !data) +return -1 ;This is a useless check. Erroneous code may (and often does) pass a broken pointer other than NULL.
I am actually a fan of defensive programming, but it's a good point that it does not defend against non-NULL pointers, and NULL is anyway an unexpected input value.
Quoted 6 lines
include/linux/bitqueue.h line 38
Quoted 4 lines
include/linux/bitqueue.h new file +3
-0+ q->data = data; + q->size = size; +memset (data,0 , size);Useless memset?
An overly cautious one, that lets us fetch values from partially initialized bytes. This code will be removed anyway.
Quoted 11 lines
include/linux/bitqueue.h line 59
Quoted 9 lines
include/linux/bitqueue.h new file +9
-0+static inline int bitq_init_full (struct bitq *q,u8 *data,int size) +{ +if (!q || !data) +return -1 ; + q->data = data; + q->size = size; + q->bit_pos = q->size *8 ; +return 0 ; +}This all should not reside in a header.
There's a handful of examples in include/linux where meaningful code is written in the headers, but I agree that in this particular case it is probably not justified by performance reasons.
Quoted 5 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+ if (!q || (bits < 1) || (bits > 8)) + return -1;Pushing 0 elements in queue is usually not an error. Implementations usually return and do nothing. From the
malloc()man page:
Agreed.
Quoted 8 lines
If size is 0, then
malloc()returns a unique pointer value that can later be successfully passed tofree().include/linux/bitqueue.h line 79
Quoted 3 lines
include/linux/bitqueue.h new file +3
-0+ max_pos = q->size *8 ; +if ((max_pos - q->bit_pos) < bits) +return -1 ;ENOMEM? Or probably better to resize the queue.
This "queue" relies on the external storage that may not be easily resizeable (e.g. when we are using a local u64 as a storage). ENOMEM sounds better (should we stick to this interface).
Quoted 11 lines
include/linux/bitqueue.h line 99
Quoted 10 lines
include/linux/bitqueue.h new file +10
-0+/* +* @value needs to be split between the current and the +* following bytes. +*/ + hi = value >> (bits - left_in_byte); + q->data[byte_pos] |= hi; + byte_pos++; + lo = value << (8 - (bits - left_in_byte)); + q->data[byte_pos] |= lo; + }
Quoted 5 lines
This piece should be a
bitmap_append()function, like:bitmap_append(addr, 3, 2, 0b11)would append 0b11 to the bitmap at offset 3. We already have bitmap_{set,get}_value8, so I suggest to extend the interface for unaligned offsets and lengths up toBITS_PER_LONG.
Interesting. Yeah, this could be part of bitmap.h instead.
Quoted 9 lines
include/linux/bitqueue.h line 138
Quoted 8 lines
include/linux/bitqueue.h new file +8
-0+/* +* Shift every byte in the queue to the left by @bits, carrying over to +* the previous byte. +*/ +for (i =0 ; i < q->size -1 ; i++) { + q->data[i] = (q->data[i] << bits) | + (q->data[i +1 ] >> rem_bits); + }
Quoted 5 lines
As I already mentioned, this is O(N), which is wrong for queues. Add a pointer to the head in the bitq structure to avoid shifting every byte.
BTW, we've got bitmap_shift_{left,right} for this.
Ack.
PATCH RESEND 2/5 linux/bitqueue.h: add a KUnit test for bitqueue.h
In reply to Alexander PotapenkoAdd tests checking that struct bitq correctly handles sub-byte values.
--- lib/Kconfig.debug | 8 ++ lib/Makefile | 1 + lib/test_bitqueue.c | 244 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 253 insertions(+) create mode 100644 lib/test_bitqueue.c
lib/Kconfig.debug +8 -0
@@ -2678,6 +2678,14 @@ config SIPHASH_KUNIT_TEST This is intended to help people writing architecture-specific optimized versions. If unsure, say N. +config BITQUEUE_KUNIT_TEST + tristate "Test <linux/bitqueue.h>" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + help + Enable this option to test the kernel's bit queue implementation + (<linux/bitqueue.h>). + config TEST_UDELAY tristate "udelay test driver" help
lib/Makefile +1 -0
@@ -394,6 +394,7 @@ CFLAGS_fortify_kunit.o += $(DISABLE_STRUCTLEAK_PLUGIN) obj-$(CONFIG_FORTIFY_KUNIT_TEST) += fortify_kunit.o obj-$(CONFIG_STRSCPY_KUNIT_TEST) += strscpy_kunit.o obj-$(CONFIG_SIPHASH_KUNIT_TEST) += siphash_kunit.o +obj-$(CONFIG_BITQUEUE_KUNIT_TEST) += test_bitqueue.o obj-$(CONFIG_GENERIC_LIB_DEVMEM_IS_ALLOWED) += devmem_is_allowed.o
lib/test_bitqueue.c new file +244 -0
244 lines not on this page · raw message
Signature · 1 line
2.41.0.255.g8b1d071c50-goog
PATCH RESEND 3/5 arm64: mte: implement CONFIG_ARM64_MTE_COMP
In reply to Alexander PotapenkoThe 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.
--- arch/arm64/Kconfig | 10 + arch/arm64/include/asm/mtecomp.h | 60 +++++ arch/arm64/mm/Makefile | 1 + arch/arm64/mm/mtecomp.c | 398 +++++++++++++++++++++++++++++++ 4 files changed, 469 insertions(+) create mode 100644 arch/arm64/include/asm/mtecomp.h create mode 100644 arch/arm64/mm/mtecomp.c
arch/arm64/Kconfig +10 -0
@@ -2065,6 +2065,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
arch/arm64/include/asm/mtecomp.h new file +60 -0
60 lines not on this page · raw message
arch/arm64/mm/Makefile +1 -0
@@ -10,6 +10,7 @@ obj-$(CONFIG_TRANS_TABLE) += trans_pgd.o obj-$(CONFIG_TRANS_TABLE) += trans_pgd-asm.o obj-$(CONFIG_DEBUG_VIRTUAL) += physaddr.o obj-$(CONFIG_ARM64_MTE) += mteswap.o +obj-$(CONFIG_ARM64_MTE_COMP) += mtecomp.o KASAN_SANITIZE_physaddr.o += n obj-$(CONFIG_KASAN) += kasan_init.o
arch/arm64/mm/mtecomp.c new file +398 -0
398 lines not on this page · raw message
Signature · 7 lines
2.41.0.255.g8b1d071c50-goog _______________________________________________ linux-arm-kernel mailing list [email protected] http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
PATCH RESEND 4/5 arm64: mte: add a test for MTE tags compression
In reply to Alexander PotapenkoEnsure that tag sequences containing alternating values are compressed to buffers of expected size and correctly decompressed afterwards.
--- 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
arch/arm64/Kconfig +10 -0
@@ -2075,6 +2075,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
arch/arm64/mm/Makefile +1 -0
@@ -11,6 +11,7 @@ obj-$(CONFIG_TRANS_TABLE) += trans_pgd-asm.o obj-$(CONFIG_DEBUG_VIRTUAL) += physaddr.o obj-$(CONFIG_ARM64_MTE) += mteswap.o obj-$(CONFIG_ARM64_MTE_COMP) += mtecomp.o +obj-$(CONFIG_ARM64_MTE_COMP_KUNIT_TEST) += test_mtecomp.o KASAN_SANITIZE_physaddr.o += n obj-$(CONFIG_KASAN) += kasan_init.o
arch/arm64/mm/test_mtecomp.c new file +175 -0
175 lines not on this page · raw message
Signature · 7 lines
2.41.0.255.g8b1d071c50-goog _______________________________________________ linux-arm-kernel mailing list [email protected] http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
PATCH RESEND 5/5 arm64: mte: add compression support to mteswap.c
In reply to Alexander PotapenkoDefine 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.
--- 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
arch/arm64/mm/Makefile +5 -0
@@ -11,6 +11,11 @@ obj-$(CONFIG_TRANS_TABLE) += trans_pgd-asm.o obj-$(CONFIG_DEBUG_VIRTUAL) += physaddr.o obj-$(CONFIG_ARM64_MTE) += mteswap.o obj-$(CONFIG_ARM64_MTE_COMP) += mtecomp.o +ifdef CONFIG_ARM64_MTE_COMP +obj-$(CONFIG_ARM64_MTE) += mteswap_comp.o +else +obj-$(CONFIG_ARM64_MTE) += mteswap_nocomp.o +endif obj-$(CONFIG_ARM64_MTE_COMP_KUNIT_TEST) += test_mtecomp.o KASAN_SANITIZE_physaddr.o += n
arch/arm64/mm/mteswap.c +8 -11
@@ -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); }
arch/arm64/mm/mteswap.h new file +12 -0
@@ -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_
arch/arm64/mm/mteswap_comp.c new file +50 -0
50 lines not on this page · raw message
arch/arm64/mm/mteswap_nocomp.c new file +37 -0
@@ -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); + } +}
Signature · 7 lines
2.41.0.255.g8b1d071c50-goog _______________________________________________ linux-arm-kernel mailing list [email protected] http://lists.infradead.org/mailman/listinfo/linux-arm-kernel