Re: [PATCH] bitmap: fix memset optimization on big-endian systems

[Sasha Levin]

Hi,

[This is an automated email]

This commit has been processed because it contains a "Fixes:" tag,
fixing commit: 2a98dc028f91 include/linux/bitmap.h: turn bitmap_set and 
bitmap_clear into memset when possible.

The bot has also determined it's probably a bug fixing patch. (score: 65.4067)

The bot has tested the following trees: v4.16, v4.15.15, v4.14.32.

v4.16: Build OK!
v4.15.15: Build OK!
v4.14.32: Build OK!

--
Thanks,
Sasha

Re: [PATCH] bitmap: fix memset optimization on big-endian systems

[Sasha Levin]

Hi,

[This is an automated email]

This commit has been processed because it contains a "Fixes:" tag,
fixing commit: 2a98dc028f91 include/linux/bitmap.h: turn bitmap_set and 
bitmap_clear into memset when possible.

The bot has also determined it's probably a bug fixing patch. (score: 65.4067)

The bot has tested the following trees: v4.16, v4.15.15, v4.14.32.

v4.16: Build OK!
v4.15.15: Build OK!
v4.14.32: Build OK!

--
Thanks,
Sasha

Re: [PATCH] bitmap: fix memset optimization on big-endian systems

[Omar Sandoval]

On Mon, Apr 02, 2018 at 04:49:39PM -0700, Linus Torvalds wrote:
> On Mon, Apr 2, 2018 at 4:37 PM, Linus Torvalds
>  wrote:
> >
> > We should probably have at least switched it to "unsigned long int"
> 
> I meant just "unsigned int", of course.
> 
> Right now we occasionally have a silly 64-bit field just for a couple of 
> flags.

Not to mention the mix of bit fields, macros, and enums, some of which
are bit masks, some of which are the bit number :)

> Of course, we do have cases where 64-bit architectures happily end up
> using more than 32 bits too, so the "unsigned long" is occasionally
> useful. But it's rare enough that it probably wasn't the right thing
> to do.
> 
> Water under the bridge. Part of it is due to another historical
> accident: the alpha port was one of the early ports, and it didn't do
> atomic byte accesses at all.
> 
> So we had multiple issues that all conspired to "unsigned long arrays
> are the natural for atomic bit operations" even though they have this
> really annoying byte order issue.

Thanks for the historical context, this is exactly what I was wondering
when I spotted this bug and fixed a similar one in Btrfs a couple of
years back.

Re: [PATCH] bitmap: fix memset optimization on big-endian systems

[Omar Sandoval]

On Mon, Apr 02, 2018 at 04:49:39PM -0700, Linus Torvalds wrote:
> On Mon, Apr 2, 2018 at 4:37 PM, Linus Torvalds
>  wrote:
> >
> > We should probably have at least switched it to "unsigned long int"
> 
> I meant just "unsigned int", of course.
> 
> Right now we occasionally have a silly 64-bit field just for a couple of 
> flags.

Not to mention the mix of bit fields, macros, and enums, some of which
are bit masks, some of which are the bit number :)

> Of course, we do have cases where 64-bit architectures happily end up
> using more than 32 bits too, so the "unsigned long" is occasionally
> useful. But it's rare enough that it probably wasn't the right thing
> to do.
> 
> Water under the bridge. Part of it is due to another historical
> accident: the alpha port was one of the early ports, and it didn't do
> atomic byte accesses at all.
> 
> So we had multiple issues that all conspired to "unsigned long arrays
> are the natural for atomic bit operations" even though they have this
> really annoying byte order issue.

Thanks for the historical context, this is exactly what I was wondering
when I spotted this bug and fixed a similar one in Btrfs a couple of
years back.

Re: [PATCH] bitmap: fix memset optimization on big-endian systems

[Linus Torvalds]

On Mon, Apr 2, 2018 at 4:37 PM, Linus Torvalds
 wrote:
>
> We should probably have at least switched it to "unsigned long int"

I meant just "unsigned int", of course.

Right now we occasionally have a silly 64-bit field just for a couple of flags.

Of course, we do have cases where 64-bit architectures happily end up
using more than 32 bits too, so the "unsigned long" is occasionally
useful. But it's rare enough that it probably wasn't the right thing
to do.

Water under the bridge. Part of it is due to another historical
accident: the alpha port was one of the early ports, and it didn't do
atomic byte accesses at all.

So we had multiple issues that all conspired to "unsigned long arrays
are the natural for atomic bit operations" even though they have this
really annoying byte order issue.

  Linus

Re: [PATCH] bitmap: fix memset optimization on big-endian systems

[Linus Torvalds]

On Mon, Apr 2, 2018 at 4:37 PM, Linus Torvalds
 wrote:
>
> We should probably have at least switched it to "unsigned long int"

I meant just "unsigned int", of course.

Right now we occasionally have a silly 64-bit field just for a couple of flags.

Of course, we do have cases where 64-bit architectures happily end up
using more than 32 bits too, so the "unsigned long" is occasionally
useful. But it's rare enough that it probably wasn't the right thing
to do.

Water under the bridge. Part of it is due to another historical
accident: the alpha port was one of the early ports, and it didn't do
atomic byte accesses at all.

So we had multiple issues that all conspired to "unsigned long arrays
are the natural for atomic bit operations" even though they have this
really annoying byte order issue.

  Linus

Re: [PATCH] bitmap: fix memset optimization on big-endian systems

[Linus Torvalds]

On Mon, Apr 2, 2018 at 3:58 PM, Omar Sandoval  wrote:
>
> Commit 2a98dc028f91 introduced an optimization to bitmap_{set,clear}()
> which uses memset() when the start and length are constants aligned to a
> byte. This is wrong on big-endian systems;

Ugh, yes.

In retrospect, I do wish I had just made the bitmap types be
byte-based, but we had strong reasons for those "unsigned long" array
semantics.

The traditional problem - and the reason why it is byte-order
dependent - was that we often mix bitmap operations with "unsigned
long flags" style operations.

We should probably have at least switched it to "unsigned long int"
with the whole 64-bit transition, but never did even that, so the
bitmap format is not just byte order dependent, but dependent on the
size of "long".

I guess the "unsigned long flag" issue still exists in several places,
and we're stuck with it, probably forever. Think page flags, but also
various networking flags etc.

You'd *think* they use bitmap operations consistently, but they
definitely mix it with direct accesses to the flags field, eg the page
flags are usually done using the PG_xyz bit numbers, but occasionally
you have code that checks multiple independent bits at once, doing
things like

  #define PAGE_FLAGS_PRIVATE  \
  (1UL << PG_private | 1UL << PG_private_2)

  static inline int page_has_private(struct page *page)
  {
  return !!(page->flags & PAGE_FLAGS_PRIVATE);
  }

so the bits really are _exposed_ as being encoded as bits in an unsigned long.

Your patch is obviously correct, and we just need to make sure people
*really* understand that bitmaps are arrays of unsigned long, and byte
(and bit) order is a real thing.

 Linus

Re: [PATCH] bitmap: fix memset optimization on big-endian systems

[Linus Torvalds]

On Mon, Apr 2, 2018 at 3:58 PM, Omar Sandoval  wrote:
>
> Commit 2a98dc028f91 introduced an optimization to bitmap_{set,clear}()
> which uses memset() when the start and length are constants aligned to a
> byte. This is wrong on big-endian systems;

Ugh, yes.

In retrospect, I do wish I had just made the bitmap types be
byte-based, but we had strong reasons for those "unsigned long" array
semantics.

The traditional problem - and the reason why it is byte-order
dependent - was that we often mix bitmap operations with "unsigned
long flags" style operations.

We should probably have at least switched it to "unsigned long int"
with the whole 64-bit transition, but never did even that, so the
bitmap format is not just byte order dependent, but dependent on the
size of "long".

I guess the "unsigned long flag" issue still exists in several places,
and we're stuck with it, probably forever. Think page flags, but also
various networking flags etc.

You'd *think* they use bitmap operations consistently, but they
definitely mix it with direct accesses to the flags field, eg the page
flags are usually done using the PG_xyz bit numbers, but occasionally
you have code that checks multiple independent bits at once, doing
things like

  #define PAGE_FLAGS_PRIVATE  \
  (1UL << PG_private | 1UL << PG_private_2)

  static inline int page_has_private(struct page *page)
  {
  return !!(page->flags & PAGE_FLAGS_PRIVATE);
  }

so the bits really are _exposed_ as being encoded as bits in an unsigned long.

Your patch is obviously correct, and we just need to make sure people
*really* understand that bitmaps are arrays of unsigned long, and byte
(and bit) order is a real thing.

 Linus

Re: [PATCH] bitmap: fix memset optimization on big-endian systems

[Omar Sandoval]

On Mon, Apr 02, 2018 at 03:58:31PM -0700, Omar Sandoval wrote:
> From: Omar Sandoval 
> 
> Commit 2a98dc028f91 introduced an optimization to bitmap_{set,clear}()
> which uses memset() when the start and length are constants aligned to a
> byte. This is wrong on big-endian systems; our bitmaps are arrays of
> unsigned long, so bit n is not at byte n / 8 in memory. This was caught
> by the Btrfs selftests, but the bitmap selftests also fail when run on a
> big-endian machine.
> 
> We can still use memset if the start and length are aligned to an
> unsigned long, so do that on big-endian. The same problem applies to the
> memcmp in bitmap_equal(), so fix it there, too.
> 
> Fixes: 2a98dc028f91 ("include/linux/bitmap.h: turn bitmap_set and 
> bitmap_clear into memset when possible")
> Fixes: 2c6deb01525a ("bitmap: use memcmp optimisation in more situations")
> Cc: sta...@kernel.org

This should be sta...@vger.kernel.org, of course

Re: [PATCH] bitmap: fix memset optimization on big-endian systems

[Omar Sandoval]

On Mon, Apr 02, 2018 at 03:58:31PM -0700, Omar Sandoval wrote:
> From: Omar Sandoval 
> 
> Commit 2a98dc028f91 introduced an optimization to bitmap_{set,clear}()
> which uses memset() when the start and length are constants aligned to a
> byte. This is wrong on big-endian systems; our bitmaps are arrays of
> unsigned long, so bit n is not at byte n / 8 in memory. This was caught
> by the Btrfs selftests, but the bitmap selftests also fail when run on a
> big-endian machine.
> 
> We can still use memset if the start and length are aligned to an
> unsigned long, so do that on big-endian. The same problem applies to the
> memcmp in bitmap_equal(), so fix it there, too.
> 
> Fixes: 2a98dc028f91 ("include/linux/bitmap.h: turn bitmap_set and 
> bitmap_clear into memset when possible")
> Fixes: 2c6deb01525a ("bitmap: use memcmp optimisation in more situations")
> Cc: sta...@kernel.org

This should be sta...@vger.kernel.org, of course