[1/2] bitmap: add sanity check function for find_bit()
Commit Message
find_bit() requires a pointer aligned to it's size. However some
subsystems (fs, for example) cast char* variables to unsigned long*
before passing them to find_bit(). Many architectures allow unaligned
pointers with the cost of performance degradation.
This patch adds runtime check for the pointers to be aligned.
Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
include/linux/find.h | 35 +++++++++++++++++++++++++++++++++++
lib/Kconfig.debug | 7 +++++++
2 files changed, 42 insertions(+)
Comments
On Wed, Oct 19, 2022 at 8:24 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> This patch adds runtime check for the pointers to be aligned.
No. Don't add pointless things like this. It only adds code, with no advantage.
The bitmap ops all operate on 'unsigned long', and if a bitmap isn't
aligned, we'll take a fault on the architectures that don't do
unaligned accesses natively.
And the find-bit functions simply aren't special enough to have this
kind of random testing, when the *basic* bitmap functions like
"set_bit()" and friends all do the accesses without any alignment
checks.
The fact that filesystem code often uses bitmap functions with a cast
from 'char *' is immaterial. Those things are already aligned
(typically they are a whole disk block). They just weren't an array of
'unsigned long'.
Linus
On Sun, Oct 23, 2022 at 03:19:24PM -0700, Linus Torvalds wrote:
> On Wed, Oct 19, 2022 at 8:24 PM Yury Norov <yury.norov@gmail.com> wrote:
> >
> > This patch adds runtime check for the pointers to be aligned.
>
> No. Don't add pointless things like this. It only adds code, with no advantage.
Sure. Patch #1 is mostly for Russell to address his concern about
unaligned bitmaps on ARM32. And it looks like it found nothing.
> The bitmap ops all operate on 'unsigned long', and if a bitmap isn't
> aligned, we'll take a fault on the architectures that don't do
> unaligned accesses natively.
ARMv6 may or may not support unaligned access depending on SCTLR.U
bit. This is what Russell was concerned about in the other email.
As far as I understand, linux enables that feature.
ARMv7 deprecates that bit and supports unaligned dereference
unconditionally, with few exceptions like exclusive access.
https://developer.arm.com/documentation/ddi0406/b/Appendices/ARMv6-Differences/Application-level-memory-support/Alignment?lang=en
Thanks,
Yury
> And the find-bit functions simply aren't special enough to have this
> kind of random testing, when the *basic* bitmap functions like
> "set_bit()" and friends all do the accesses without any alignment
> checks.
>
> The fact that filesystem code often uses bitmap functions with a cast
> from 'char *' is immaterial. Those things are already aligned
> (typically they are a whole disk block). They just weren't an array of
> 'unsigned long'.
>
> Linus
On Tue, Oct 25, 2022 at 10:11:51AM -0700, Yury Norov wrote:
> ARMv6 may or may not support unaligned access depending on SCTLR.U
> bit. This is what Russell was concerned about in the other email.
> As far as I understand, linux enables that feature.
However, we still support ARMv5 and ARMv4, both of which _trap_ every
unaligned access, which will make a findbit call with an unaligned
pointer using word loads painfully expensive. This is the main reason
we haven't used word loads in the findbit ops.
As mentioned, I have patches that do change that (and convert the
thing to use assembly macros to make updates much easier.)
On Tue, Oct 25, 2022 at 11:26 AM Russell King (Oracle)
<linux@armlinux.org.uk> wrote:
>
> However, we still support ARMv5 and ARMv4, both of which _trap_ every
> unaligned access, which will make a findbit call with an unaligned
> pointer using word loads painfully expensive. This is the main reason
> we haven't used word loads in the findbit ops.
The findbit ops really shouldn't be a special case, and bitmaps can
never be unaligned.
Just look at what 'test_bit()' does: the non-constant non-instrumented
version ends up as generic_test_bit(), which uses a "const volatile
unsigned long *" access to do the bitmap load.
So there is absolutely no way that bitmaps can ever be unaligned,
because that would trap.
And test_bit() is a lot more fundamental than one of the "find bits" functions.
Have we had bugs in this area before? Sure. People have used "unsigned
int" for flags and mised the bitmap ops on it, and it has worked on
x86.
But then it fails *miserably* on big-endian machines and on machines
that require more alignment (and even on x86 we have KASAN failures
etc these days and obviously without casts it will warn), so we've
hopefully fixed all those cases up long long ago.
So I really think it's pointless to worry about alignment for
"find_bit()" and friends, when much more fundamental bitop functions
don't worry about it.
Linus
On Tue, Oct 25, 2022 at 11:38:31AM -0700, Linus Torvalds wrote:
> On Tue, Oct 25, 2022 at 11:26 AM Russell King (Oracle)
> <linux@armlinux.org.uk> wrote:
> >
> > However, we still support ARMv5 and ARMv4, both of which _trap_ every
> > unaligned access, which will make a findbit call with an unaligned
> > pointer using word loads painfully expensive. This is the main reason
> > we haven't used word loads in the findbit ops.
>
> The findbit ops really shouldn't be a special case, and bitmaps can
> never be unaligned.
>
> Just look at what 'test_bit()' does: the non-constant non-instrumented
> version ends up as generic_test_bit(), which uses a "const volatile
> unsigned long *" access to do the bitmap load.
>
> So there is absolutely no way that bitmaps can ever be unaligned,
> because that would trap.
>
> And test_bit() is a lot more fundamental than one of the "find bits" functions.
>
> Have we had bugs in this area before? Sure. People have used "unsigned
> int" for flags and mised the bitmap ops on it, and it has worked on
> x86.
>
> But then it fails *miserably* on big-endian machines and on machines
> that require more alignment (and even on x86 we have KASAN failures
> etc these days and obviously without casts it will warn), so we've
> hopefully fixed all those cases up long long ago.
>
> So I really think it's pointless to worry about alignment for
> "find_bit()" and friends, when much more fundamental bitop functions
> don't worry about it.
Yes, which is what my series does by converting to use word operations
and not caring anymore whether the pointer is aligned or not.
My reply was more a correction of the apparent "we don't have to worry
about unaligned accesses because version 6 of the architecture has a
feature that means we don't have to worry" which I regard as broken
thinking, broken as long as we continue to support previous versions
of the architecture.
I'm planning to queue up my series of five patches today, so it should
be in tonight's linux-next.
@@ -7,6 +7,7 @@
#endif
#include <linux/bitops.h>
+#include <linux/bug.h>
unsigned long _find_next_bit(const unsigned long *addr1, unsigned long nbits,
unsigned long start);
@@ -35,6 +36,14 @@ unsigned long _find_next_bit_le(const unsigned long *addr, unsigned
long size, unsigned long offset);
#endif
+static __always_inline
+void check_find_bit(const unsigned long *addr)
+{
+#ifdef CONFIG_DEBUG_BITMAP
+ WARN_ON_ONCE(!IS_ALIGNED((unsigned long)addr, sizeof(unsigned long)));
+#endif
+}
+
#ifndef find_next_bit
/**
* find_next_bit - find the next set bit in a memory region
@@ -49,6 +58,8 @@ static inline
unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
unsigned long offset)
{
+ check_find_bit(addr);
+
if (small_const_nbits(size)) {
unsigned long val;
@@ -79,6 +90,9 @@ unsigned long find_next_and_bit(const unsigned long *addr1,
const unsigned long *addr2, unsigned long size,
unsigned long offset)
{
+ check_find_bit(addr1);
+ check_find_bit(addr2);
+
if (small_const_nbits(size)) {
unsigned long val;
@@ -138,6 +152,8 @@ static inline
unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
unsigned long offset)
{
+ check_find_bit(addr);
+
if (small_const_nbits(size)) {
unsigned long val;
@@ -164,6 +180,8 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
static inline
unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
{
+ check_find_bit(addr);
+
if (small_const_nbits(size)) {
unsigned long val = *addr & GENMASK(size - 1, 0);
@@ -270,6 +288,9 @@ unsigned long find_first_and_bit(const unsigned long *addr1,
const unsigned long *addr2,
unsigned long size)
{
+ check_find_bit(addr1);
+ check_find_bit(addr2);
+
if (small_const_nbits(size)) {
unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
@@ -292,6 +313,8 @@ unsigned long find_first_and_bit(const unsigned long *addr1,
static inline
unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
{
+ check_find_bit(addr);
+
if (small_const_nbits(size)) {
unsigned long val = *addr | ~GENMASK(size - 1, 0);
@@ -313,6 +336,8 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
static inline
unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
{
+ check_find_bit(addr);
+
if (small_const_nbits(size)) {
unsigned long val = *addr & GENMASK(size - 1, 0);
@@ -417,18 +442,24 @@ extern unsigned long find_next_clump8(unsigned long *clump,
static inline unsigned long find_next_zero_bit_le(const void *addr,
unsigned long size, unsigned long offset)
{
+ check_find_bit(addr);
+
return find_next_zero_bit(addr, size, offset);
}
static inline unsigned long find_next_bit_le(const void *addr,
unsigned long size, unsigned long offset)
{
+ check_find_bit(addr);
+
return find_next_bit(addr, size, offset);
}
static inline unsigned long find_first_zero_bit_le(const void *addr,
unsigned long size)
{
+ check_find_bit(addr);
+
return find_first_zero_bit(addr, size);
}
@@ -439,6 +470,8 @@ static inline
unsigned long find_next_zero_bit_le(const void *addr, unsigned
long size, unsigned long offset)
{
+ check_find_bit(addr);
+
if (small_const_nbits(size)) {
unsigned long val = *(const unsigned long *)addr;
@@ -472,6 +505,8 @@ static inline
unsigned long find_next_bit_le(const void *addr, unsigned
long size, unsigned long offset)
{
+ check_find_bit(addr);
+
if (small_const_nbits(size)) {
unsigned long val = *(const unsigned long *)addr;
@@ -543,6 +543,13 @@ endmenu # "Compiler options"
menu "Generic Kernel Debugging Instruments"
+config DEBUG_BITMAP
+ bool "Debug bitmaps"
+ help
+ Say Y here if you want to check bitmap functions parameters at
+ the runtime. Enable CONFIG_DEBUG_BITMAP only for debugging because
+ it may affect performance.
+
config MAGIC_SYSRQ
bool "Magic SysRq key"
depends on !UML