Re: [PATCH v3 3/5] arm64: mte: implement CONFIG_ARM64_MTE_COMP

[Alexander Potapenko]

On Wed, Jul 19, 2023 at 8:09 AM Yury Norov <yury.norov@xxxxxxxxx> wrote:
...
> > +
> > +/* Functions below are exported for testing purposes. */
>
> Then declare them in a separate local header or simply in the test, but
> please not in a public header.

Fair enough, moved them to the test.

> > +
> > +/*
> > + * EA0 stands for "Evgenii's Algorithm 0", as the initial proposal contained two
> > + * compression algorithms.
>
> This is the 4th time I see mr. Stepanov's credentials in the patch.
> I've no doubts he's a worthy gentleman but please avoid mentioning
> people in source code. Suggested-by is enough. IIRC, the rule for
> that exists for about decade.
>
> For the purpose of namespacing, the mte_compress/mte_decompress would
> sound better.

This indeed makes sense; "EA0" is not widely recognizable, and we are
unlikely to have more than one MTE compression algorithm anyway.
I changed "ea0" to "mte" in the patch series.



> > + *
> > + * 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.
>
> I honestly tried to understand... For example, what the
>         'r_sizes[0..4] : i7 x 5'
> means? An array of 5 elements, 17 bits each? But it's alone greater
> than size of pointer... Oh gosh...

iN (note that it is a small i, not a 1) is LLVM notation for an N-bit
integer type.
There's no such thing in C syntax, and describing the data layout
using bitfields would be painful.
Would it help if I add a comment explaining that iN is an N-bit
integer? Or do you prefer something like

  r_sizes[0..4] : 5 x 7 bits

?

>
> Moreover, MTE tags are all 4-bits.
>
> It seems like text without pictures is above my mental abilities. Can you
> please illustrate it? For example, from the #4, I (hopefully correctly)
> realized that:
>
> Inline frame format:
>    0                                                    60       62  63
>  +---------------------------------------------------------------------+
I think it's more natural to number bits from 63 to 0

>  |              No idea what happens here             |    Lidx    | X |
>  +---------------------------------------------------------------------+
>  63    : X      :  RAZ : Reserved for Xarray.
>  60-62 : Lidx   : 0..5 : Largest element index.

There's some mismatch now between this picture, where Lidx is i3, and
the implementation that treats it as an i4, merging bit 63 into it.
Maybe we can avoid this by not splitting off bit 63?

>                      6 : Reserved
>                      7 : Invalid handler

No, 7 means "treat this handle as an out-of-line one". It is still
valid, but instead of tag data it contains a pointer.

>
> Because of the size, I believe this comment is worth to put in Docs,
> moreover we already have "Documentation/arch/arm64/memory-tagging-extension.rst"
> Why don't you add an 'MTE Compression' section in there?

Good idea, will do!

>
> > +#include <linux/bits.h>
> > +#include <linux/bitmap.h>
> > +#include <linux/gfp.h>
> > +#include <linux/module.h>
> > +#include <linux/slab.h>
> > +#include <linux/swab.h>
> > +#include <linux/string.h>
> > +#include <linux/types.h>
>
> Nit: Alphabetic order?
Ack.

>
> Andy is right, bitmap.h includes bit.h, no need to include both. And if
> your code will get broken one day, it's a bitmap maintainers' work to fix.
Ack.


> > +
> > +/*
> > + * Sizes of compressed values.
> > + */
> > +#define BITS_PER_TAG 4
> > +#define BITS_PER_SIZE 7
> > +#define BITS_PER_LARGEST_IDX_INLINE 4
> > +#define BITS_PER_LARGEST_IDX 6
>
> But in the comment you say that largest index in inline frame is 3-bits long.

The comment says "i4" (see my comments above)

> > +
> > +/* Translate allocation size into mtecomp_caches[] index. */
> > +static int ea0_size_to_cache_id(int len)
>
> Here and everywhere, do you need signed values? If not, unsigned int.

Done as part of fixing Andy's comments

> > +
> > +/* 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)
> > +                             tags[pos / 2] = (prev << 4) | r_tags[i];
> > +                     else
> > +                             prev = r_tags[i];
> > +                     pos++;
> > +             }
> > +     }
> > +}
> > +EXPORT_SYMBOL_NS(ea0_ranges_to_tags, MTECOMP);
>
> Because I didn't understand the compressed frame format, not sure I
> can understand this logic...
Hope the above comments will help, if not - please let me know.

> > +
> > +/* 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;
> > +     }
> > +}
>
> I wonder if there's a math formula here? Can you explain where from
> those numbers come?

I'll add a comment there.
Basically, for the inline case it is the biggest N such as 4 + 4*N +
7*(N-1) <= 63
(not 64, because Xarray steals one bit from us)

For the out-of-line case it is the biggest N such as 6+4*N + 7*(N-1)
<= array size in bits (128, 256, or 512).

>
> > +#define RANGES_INLINE ea0_size_to_ranges(8)
>
> Maybe
>
>  #define RANGES_INLINE (6)

Fair enough.


> > +
> > +static void bitmap_write(unsigned long *bitmap, unsigned long value,
> > +                      unsigned long *pos, unsigned long bits)
>
> Please don't steal prefixes. But the idea is good. For the next
> iteration, let's rename bitmap_set_value() to bitmap_write()?
> So that your function will be an mte_bitmap_write().

I don't object, but it diverges from bitmap_set_value8() now.
Will do.