[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAG_fn=V4wyHjXT41byPbAkrZzisZRfKszwM4EUFV-FNWuXXfbw@mail.gmail.com>
Date: Wed, 26 Jul 2023 10:08:28 +0200
From: Alexander Potapenko <glider@...gle.com>
To: Yury Norov <yury.norov@...il.com>
Cc: catalin.marinas@....com, will@...nel.org, pcc@...gle.com,
andreyknvl@...il.com, andriy.shevchenko@...ux.intel.com,
linux@...musvillemoes.dk, linux-kernel@...r.kernel.org,
linux-arm-kernel@...ts.infradead.org, eugenis@...gle.com,
syednwaris@...il.com, william.gray@...aro.org,
Arnd Bergmann <arnd@...db.de>
Subject: Re: [PATCH v4 1/5] lib/bitmap: add bitmap_{set,get}_value()
On Sun, Jul 23, 2023 at 3:57 AM Yury Norov <yury.norov@...il.com> wrote:
>
> On Thu, Jul 20, 2023 at 07:39:52PM +0200, Alexander Potapenko wrote:
> > +/**
> > + * bitmap_write - write n-bit value within a memory region
> > + * @map: address to the bitmap memory region
> > + * @value: value of nbits
> > + * @start: bit offset of the n-bit value
> > + * @nbits: size of value in bits, up to BITS_PER_LONG
> > + */
> > +static inline void bitmap_write(unsigned long *map,
> > + unsigned long value,
> > + unsigned long start, unsigned long nbits)
> > +{
> > + size_t index = BIT_WORD(start);
> > + unsigned long offset = start % BITS_PER_LONG;
> > + unsigned long space = BITS_PER_LONG - offset;
> > +
> > + if (unlikely(!nbits))
> > + return;
> > + value &= GENMASK(nbits - 1, 0);
>
> Strictly speaking, a 'value' shouldn't contain set bits beyond nbits
> because otherwise it's an out-of-bonds type of error.
I can easily imagine someone passing -1 (or ~0) as a value, but
wanting to only write n bits of n.
>
> This is kind of gray zone to me, because it's a caller's responsibility
> to provide correct input. But on the other hand, it would be a great
> headache debugging corrupted bitmaps.
>
> Now that we've got a single user of the bitmap_write, and even more,
> it's wrapped with a helper, I think it would be reasonable to trim a
> 'value' in the helper, if needed.
>
> Anyways, the comment must warn about that loudly...
>
> > + if (space >= nbits) {
> > + map[index] &= ~(GENMASK(nbits - 1, 0) << offset);
>
> 'GENMASK(nbits - 1, 0) << offset' looks really silly.
As noted in the other patch discussion, pulling offset into GENMASK is
actually not an identity transformation, because nbits + offset may
exceed 64, producing an invalid mask.
>
> > + map[index] |= value << offset;
>
> Here you commit 2 reads and 2 writes for a word instead of one.
There won't be two reads and two writes.
The compiler will read map[index] to a register, apply the mask, then
write value << offset to it, then perform the write.
Unless map[] is a volatile, repeated reads/writes will be optimized
out by any decent compiler.
>
> > + return;
> > + }
> > + map[index] &= ~BITMAP_FIRST_WORD_MASK(start);
>
> ~FIRST_WORD is the same as LAST WORD. I tried to replace, and it saves
> ~25 bytes of .text on x86_64.
>
> > + map[index] |= value << offset;
> > + map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
> > + map[index + 1] |= (value >> space);
> > +}
>
> With all that I think the implementation should look something like
> this:
>
> unsigned long w, mask;
>
> if (unlikely(nbits == 0))
> return 0;
>
> map += BIT_WORD(start);
> start %= BITS_PER_LONG;
> end = start + nbits - 1;
>
> w = *map & (end < BITS_PER_LONG ? ~GENMASK(end, start) : BITMAP_LAST_WORD_MASK(start));
> *map = w | (value << start);
>
> if (end < BITS_PER_LONG)
> return;
>
> w = *++map & BITMAP_FIRST_WORD_MASK(end);
> *map = w | (value >> BITS_PER_LONG * 2 - end);
>
> It's not tested, except the /s/~FIRST_WORD/LAST_WORD/ part, but I expect
> it should be more efficient.
>
> Alexander, can you please try the above and compare?
I like the idea of sharing the first write between the branches, and
it can be made even shorter:
===========================================================
void bitmap_write_new(unsigned long *map, unsigned long value,
unsigned long start, unsigned long nbits)
{
unsigned long offset;
unsigned long space;
size_t index;
bool fit;
if (unlikely(!nbits))
return;
value &= GENMASK(nbits - 1, 0);
offset = start % BITS_PER_LONG;
space = BITS_PER_LONG - offset;
index = BIT_WORD(start);
fit = space >= nbits;
map[index] &= (fit ? (~(GENMASK(nbits - 1, 0) << offset)) :
~BITMAP_FIRST_WORD_MASK(start));
map[index] |= value << offset;
if (fit)
return;
map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
map[index + 1] |= (value >> space);
}
===========================================================
According to Godbolt (https://godbolt.org/z/n5Te779bf), this function
is 32 bytes shorter than yours under x86 Clang, and 8 bytes - under
GCC (which on the other hand does a poor job optimizing both).
Overall, given that there's currently a single user of these
functions, isn't it premature to optimize them without knowing
anything about their performance?
> In previous iteration, I asked you to share disassembly listings for the
> functions. Can you please do that now?
Will godbolt work for you (see above)?
>
> Regarding the rest of the series:
> - I still see Evgenii's name in mtecomp.c, and EA0 references;
Will fix, thanks!
> - git-am throws warning about trailing line;
Interesting, I generate the patches using `git format-patch`, I
thought `git am` should be the inversion of it. I'll check.
> - checkpatch warns 7 times;
Indeed, there were warnings that I ignored (e.g. one of them was
caused by me adding extern symbols to the test module, as requested
during the review process). I think I can fix all of them.
>
> Can you fix all the above before sending the new version?
>
> Have you tested generic part against BE32, BE64 and LE32 architectures;
> and arch part against BE64? If not, please do.
BE64 works, I'll also need to check the 32-bit versions as well.
Note that MTE is an ARM64 feature (yet we still need to ensure
bitops.h works on 32 bits).
>
> You're mentioning that the compression ratio is 2 to 20x. Can you
> share the absolute numbers? If it's 1k vs 2k, I think most people
> just don't care...
I'll provide the exact numbers with the next patch series. Last time I
checked, the order of magnitude was tens of megabytes.
> Can you share the code that you used to measure the compression ratio?
> Would it make sense to export the numbers via sysfs?
For out-of-line allocations the data can be derived from
/proc/slabinfo, but we don't calculate inline allocations.
Agreed, a debugfs interface won't hurt.
Powered by blists - more mailing lists