| Message ID | 20211203100846.3977195-1-keescook@chromium.org (mailing list archive) |
|---|---|
| State | Changes Requested |
| Headers | show |
| Series | find: Do not read beyond variable boundaries on small sizes | expand |
On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: > It's common practice to cast small variable arguments to the find_*_bit() It's a bad practice and should be fixed accordingly, no? > helpers to unsigned long and then use a size argument smaller than > sizeof(unsigned long): > > unsigned int bits; > ... > out = find_first_bit((unsigned long *)&bits, 32); > > This leads to the find helper dereferencing a full unsigned long, > regardless of the size of the actual variable. The unwanted bits > get masked away, but strictly speaking, a read beyond the end of > the target variable happens. Builds under -Warray-bounds complain > about this situation, for example: > > In file included from ./include/linux/bitmap.h:9, > from drivers/iommu/intel/iommu.c:17: > drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': > ./include/linux/find.h:119:37: error: array subscript 'long unsigned int[0]' is partly outside array bounds of 'int[1]' [-Werror=array-bounds] > 119 | unsigned long val = *addr & GENMASK(size - 1, 0); > | ^~~~~ > drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' > 2115 | int pds, max_pde; > | ^~~~~~~ > > Instead, just carefully read the correct variable size, all of which > happens at compile time since small_const_nbits(size) has already > determined that arguments are constant expressions. What is the performance impact?
On December 3, 2021 4:30:35 AM PST, Andy Shevchenko <andriy.shevchenko@linux.intel.com> wrote: >On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: >> It's common practice to cast small variable arguments to the find_*_bit() > >It's a bad practice and should be fixed accordingly, no? There's an argument to be made that the first arg should be void * but that's a pretty invasive change at this point (and orthogonal to this fix). I'd be happy to send a treewide change for that too, if folks wanted? > >> helpers to unsigned long and then use a size argument smaller than >> sizeof(unsigned long): >> >> unsigned int bits; >> ... >> out = find_first_bit((unsigned long *)&bits, 32); >> >> This leads to the find helper dereferencing a full unsigned long, >> regardless of the size of the actual variable. The unwanted bits >> get masked away, but strictly speaking, a read beyond the end of >> the target variable happens. Builds under -Warray-bounds complain >> about this situation, for example: >> >> In file included from ./include/linux/bitmap.h:9, >> from drivers/iommu/intel/iommu.c:17: >> drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': >> ./include/linux/find.h:119:37: error: array subscript 'long unsigned int[0]' is partly outside array bounds of 'int[1]' [-Werror=array-bounds] >> 119 | unsigned long val = *addr & GENMASK(size - 1, 0); >> | ^~~~~ >> drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' >> 2115 | int pds, max_pde; >> | ^~~~~~~ >> >> Instead, just carefully read the correct variable size, all of which >> happens at compile time since small_const_nbits(size) has already >> determined that arguments are constant expressions. > >What is the performance impact? There should be none. It's entirely using constant expressions, so all of it gets reduce at compile time to a single path without conditionals. The spot checks I did on the machine code showed no differences either (since I think optimization was doing the masking vis smaller width dereference). >
On Fri, Dec 03, 2021 at 02:30:35PM +0200, Andy Shevchenko wrote: > On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: > > It's common practice to cast small variable arguments to the find_*_bit() Not that common - I found 19 examples of this cast, and most of them are in drivers. The only non-driver case is kernel/trace/pid_list.c: static inline bool upper_empty(union upper_chunk *chunk) { /* * If chunk->data has no lower chunks, it will be the same * as a zeroed bitmask. Use find_first_bit() to test it * and if it doesn't find any bits set, then the array * is empty. */ int bit = find_first_bit((unsigned long *)chunk->data, sizeof(chunk->data) * 8); return bit >= sizeof(chunk->data) * 8; } And it's OK wrt type conversion because chunk->data is: union lower_chunk { union lower_chunk *next; unsigned long data[LOWER_SIZE]; // 2K in size }; Although, this function should use bitmap_empty(), probably like this: static inline bool upper_empty(union upper_chunk *chunk) { return bitmap_empty(chunk->data->data[0], BITS_PER_LONG); } Steven, can you comment on this? > It's a bad practice and should be fixed accordingly, no? Yes. > > helpers to unsigned long and then use a size argument smaller than > > sizeof(unsigned long): > > > > unsigned int bits; > > ... > > out = find_first_bit((unsigned long *)&bits, 32); > > > > This leads to the find helper dereferencing a full unsigned long, > > regardless of the size of the actual variable. The unwanted bits > > get masked away, but strictly speaking, a read beyond the end of > > the target variable happens. Builds under -Warray-bounds complain > > about this situation, for example: > > > > In file included from ./include/linux/bitmap.h:9, > > from drivers/iommu/intel/iommu.c:17: > > drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': > > ./include/linux/find.h:119:37: error: array subscript 'long unsigned int[0]' is partly outside array bounds of 'int[1]' [-Werror=array-bounds] > > 119 | unsigned long val = *addr & GENMASK(size - 1, 0); > > | ^~~~~ > > drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' > > 2115 | int pds, max_pde; > > | ^~~~~~~ The driver should be fixed. I would suggest using one of ffs/fls/ffz from include/asm/bitops.h Thanks, Yury > > Instead, just carefully read the correct variable size, all of which > > happens at compile time since small_const_nbits(size) has already > > determined that arguments are constant expressions. > > What is the performance impact? > > -- > With Best Regards, > Andy Shevchenko >
On Fri, Dec 03, 2021 at 08:37:59AM -0800, Kees Cook wrote: > > > On December 3, 2021 4:30:35 AM PST, Andy Shevchenko <andriy.shevchenko@linux.intel.com> wrote: > >On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: > >> It's common practice to cast small variable arguments to the find_*_bit() > > > >It's a bad practice and should be fixed accordingly, no? > > There's an argument to be made that the first arg should be void * but that's a pretty invasive change at this point (and orthogonal to this fix). What for? To save at most 7 bytes of alignment overhead for bitmaps like char bitmap[sizeof(unsigned long) + 1]? > I'd be happy to send a treewide change for that too, if folks wanted? For small arrays of bits that are fraction of machine word we have ffs/fls/ffz. For long bitmaps, the alignment overhead is not that important - at least nobody complained. If we convert bitmaps to void*, it would mean that we'd handle tails just like you did in this patch. The __find_bits_deref()-style function should be also called from each lib/bitmap.c function together with store() analogue, and overall impact would barely be positive. Char-aligned bitmaps would be traversed less efficient than word-aligned on most architectures, and we'll have the same problems that memcpy() has. Thanks, Yury > >> helpers to unsigned long and then use a size argument smaller than > >> sizeof(unsigned long): > >> > >> unsigned int bits; > >> ... > >> out = find_first_bit((unsigned long *)&bits, 32); > >> > >> This leads to the find helper dereferencing a full unsigned long, > >> regardless of the size of the actual variable. The unwanted bits > >> get masked away, but strictly speaking, a read beyond the end of > >> the target variable happens. Builds under -Warray-bounds complain > >> about this situation, for example: > >> > >> In file included from ./include/linux/bitmap.h:9, > >> from drivers/iommu/intel/iommu.c:17: > >> drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': > >> ./include/linux/find.h:119:37: error: array subscript 'long unsigned int[0]' is partly outside array bounds of 'int[1]' [-Werror=array-bounds] > >> 119 | unsigned long val = *addr & GENMASK(size - 1, 0); > >> | ^~~~~ > >> drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' > >> 2115 | int pds, max_pde; > >> | ^~~~~~~ > >> > >> Instead, just carefully read the correct variable size, all of which > >> happens at compile time since small_const_nbits(size) has already > >> determined that arguments are constant expressions. > > > >What is the performance impact? > > There should be none. It's entirely using constant expressions, so all of it gets reduce at compile time to a single path without conditionals. The spot checks I did on the machine code showed no differences either (since I think optimization was doing the masking vis smaller width dereference). > > > > > > -- > Kees Cook
On Fri, 3 Dec 2021 10:26:38 -0800 Yury Norov <yury.norov@gmail.com> wrote: > On Fri, Dec 03, 2021 at 02:30:35PM +0200, Andy Shevchenko wrote: > > On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: > > > It's common practice to cast small variable arguments to the find_*_bit() > > Not that common - I found 19 examples of this cast, and most of them > are in drivers. The only non-driver case is kernel/trace/pid_list.c: > > static inline bool upper_empty(union upper_chunk *chunk) > { > /* > * If chunk->data has no lower chunks, it will be the same > * as a zeroed bitmask. Use find_first_bit() to test it > * and if it doesn't find any bits set, then the array > * is empty. > */ > int bit = find_first_bit((unsigned long *)chunk->data, > sizeof(chunk->data) * 8); > return bit >= sizeof(chunk->data) * 8; > } > > And it's OK wrt type conversion because chunk->data is: > > union lower_chunk { > union lower_chunk *next; > unsigned long data[LOWER_SIZE]; // 2K in size > }; > > Although, this function should use bitmap_empty(), probably like this: > > static inline bool upper_empty(union upper_chunk *chunk) > { > return bitmap_empty(chunk->data->data[0], BITS_PER_LONG); > } > > Steven, can you comment on this? > > > It's a bad practice and should be fixed accordingly, no? > > Yes. You are probably right and that should be bitmap_empty(), but the above is incorrect. This is emulating a sparse bitmask in a tree. trace_pid_list { union upper_chunk upper[256]; }; union upper_chunk { union upper_chunk *next; // when freed used as free list pointer union lower_chunk data[256]; }; union lower_chunk { union lower_chunk *next; // for free list unsigned long data[512]; // for 64 bit // data[1024]; for 32 bit }; The code is initialized where we allocate some structures to fill the above tree, but when the sparse bitmask is empty, the upper pointers are null. That is, the pointers are only assigned *if and only if* there's a bit set in the lower structure. That way, we can quickly skip over large sections without having to look deeper into the tree if there's nothing set. Because the upper_chunk has an array of pointers, and the pointers are only allocated if the lower chunk they point to has a bit set, and are NULL otherwise. In order to find the first chunk to look at, or know if a chunk is empty, we scan the pointers as if they were long words, and if nothing is set, we know it is empty. The above is an abuse of find_first_bit() to scan the pointers. The equivalence of: int bit = find_first_bit((unsigned long *)chunk->data, sizeof(chunk->data) * 8); return bit >= sizeof(chunk->data) * 8; would then actually be: return bitmap_empty((unsigned long *)chunk->data, sizeof(chunk->data) * 8); Not what you wrote. -- Steve
On Fri, Dec 03, 2021 at 11:16:11AM -0800, Yury Norov wrote: > On Fri, Dec 03, 2021 at 08:37:59AM -0800, Kees Cook wrote: > > > > > > On December 3, 2021 4:30:35 AM PST, Andy Shevchenko <andriy.shevchenko@linux.intel.com> wrote: > > >On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: > > >> It's common practice to cast small variable arguments to the find_*_bit() > > > > > >It's a bad practice and should be fixed accordingly, no? > > > > There's an argument to be made that the first arg should be void * but that's a pretty invasive change at this point (and orthogonal to this fix). > > What for? To save at most 7 bytes of alignment overhead for bitmaps > like char bitmap[sizeof(unsigned long) + 1]? I just meant to simplify the calling conventions. Right now everyone has to cast to unsigned long *, which doesn't seem right: alignment and strides can be done in the routine. But, I have no strong opinion about this; it's just something I noticed while looking at it.
On Fri, Dec 03, 2021 at 10:26:38AM -0800, Yury Norov wrote: > On Fri, Dec 03, 2021 at 02:30:35PM +0200, Andy Shevchenko wrote: > > On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: > > > It's common practice to cast small variable arguments to the find_*_bit() > > Not that common - I found 19 examples of this cast, and most of them > are in drivers. I find 51 (most are in the for_each_* wrappers): $ RE=$(echo '\b('$(echo $(grep -E '^(unsigned long find|#define for_each)_' include/linux/find.h | cut -d'(' -f1 | awk '{print $NF}') | tr ' ' '|')')\(.*\(unsigned long \*\)') $ git grep -E "$RE" | wc -l 51 > > > This leads to the find helper dereferencing a full unsigned long, > > > regardless of the size of the actual variable. The unwanted bits > > > get masked away, but strictly speaking, a read beyond the end of > > > the target variable happens. Builds under -Warray-bounds complain > > > about this situation, for example: > > > > > > In file included from ./include/linux/bitmap.h:9, > > > from drivers/iommu/intel/iommu.c:17: > > > drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': > > > ./include/linux/find.h:119:37: error: array subscript 'long unsigned int[0]' is partly outside array bounds of 'int[1]' [-Werror=array-bounds] > > > 119 | unsigned long val = *addr & GENMASK(size - 1, 0); > > > | ^~~~~ > > > drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' > > > 2115 | int pds, max_pde; > > > | ^~~~~~~ > > The driver should be fixed. I would suggest using one of ffs/fls/ffz from > include/asm/bitops.h I don't think it's a good API design to make developers choose between functions based on the size of their target. This also doesn't work well for the main problem which is the for_each_* usage. The existing API is totally fine: it already diverts the constant expression small sizes to ffs/etc, and this change is only to that part. It's just changing the C description of how to get at the desired bits, so that -Warray-bounds doesn't (correctly) get upset about the wider-than-underlying-type OOB read. This is one of the last issues with -Warray-bounds, which has proven to be an effective compiler flag for finding real bugs. Since this patch doesn't change performance, doesn't change the resulting executable instructions, doesn't require any caller changes, and helps gain global -Warray-bounds coverage, I'm hoping to convince you of its value. :) -Kees
On Fri, Dec 03, 2021 at 03:01:30PM -0800, Kees Cook wrote: > On Fri, Dec 03, 2021 at 10:26:38AM -0800, Yury Norov wrote: > > On Fri, Dec 03, 2021 at 02:30:35PM +0200, Andy Shevchenko wrote: > > > On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: > > > > It's common practice to cast small variable arguments to the find_*_bit() > > > > Not that common - I found 19 examples of this cast, and most of them > > are in drivers. > > I find 51 (most are in the for_each_* wrappers): > > $ RE=$(echo '\b('$(echo $(grep -E '^(unsigned long find|#define for_each)_' include/linux/find.h | cut -d'(' -f1 | awk '{print $NF}') | tr ' ' '|')')\(.*\(unsigned long \*\)') > $ git grep -E "$RE" | wc -l > 51 > > > > > This leads to the find helper dereferencing a full unsigned long, > > > > regardless of the size of the actual variable. The unwanted bits > > > > get masked away, but strictly speaking, a read beyond the end of > > > > the target variable happens. Builds under -Warray-bounds complain > > > > about this situation, for example: > > > > > > > > In file included from ./include/linux/bitmap.h:9, > > > > from drivers/iommu/intel/iommu.c:17: > > > > drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': > > > > ./include/linux/find.h:119:37: error: array subscript 'long unsigned int[0]' is partly outside array bounds of 'int[1]' [-Werror=array-bounds] > > > > 119 | unsigned long val = *addr & GENMASK(size - 1, 0); > > > > | ^~~~~ > > > > drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' > > > > 2115 | int pds, max_pde; > > > > | ^~~~~~~ > > > > The driver should be fixed. I would suggest using one of ffs/fls/ffz from > > include/asm/bitops.h > > I don't think it's a good API design to make developers choose between > functions based on the size of their target. Bitmap functions work identically for all sizes from 0 to INT_MAX - 1. Users don't 'choose between functions based on the size of their target'. Can you explain more what you mean? > This also doesn't work well > for the main problem which is the for_each_* usage. for_each_*_bit() requires a pointer to an array of unsigned longs. If it's provided with something else, this is an error on a caller side. > The existing API is totally fine: it already diverts the constant > expression small sizes to ffs/etc, and this change is only to that > part. If you want to allow passing types other than unsigned long *, you need to be consistent and propagate this change to other bitmap functions. This is much more work than just fixing at most 48 wrong callers. (48 because I inspected some callers manually, and they are fine.) > It's just changing the C description of how to get at the desired > bits, so that -Warray-bounds doesn't (correctly) get upset about the > wider-than-underlying-type OOB read. As you said, -Warray-bounds _correctly_ gets upset about the dangerous typecasting. What suggested here is an attempt to shut down the compiler warning with the cost of complication of the code and possible maintenance issues. The correct example of handling tiny bitmaps can be found for example in drivers/mtd/nand/raw/ams-delta.c: static void gpio_nand_io_write(struct gpio_nand *priv, u8 byte) { struct gpio_descs *data_gpiods = priv->data_gpiods; DECLARE_BITMAP(values, BITS_PER_TYPE(byte)) = { byte, }; ... } > This is one of the last issues with -Warray-bounds, which has proven to > be an effective compiler flag for finding real bugs. Since this patch > doesn't change performance, doesn't change the resulting executable > instructions, doesn't require any caller changes, and helps gain global > -Warray-bounds coverage, I'm hoping to convince you of its value. :) I'm all for enabling -Warray-bounds, but the warnings that it spots only convinced me that bitmap API is used wrongly, and it should be fixed. Can you please share the list of bitmap-related issues found with -Warray-bounds that concerned you? I'll take a look and try to make a patch that fixes it. Thanks, Yury
On Tue, Dec 07, 2021 at 03:39:33PM -0800, Yury Norov wrote: > On Fri, Dec 03, 2021 at 03:01:30PM -0800, Kees Cook wrote: > > On Fri, Dec 03, 2021 at 10:26:38AM -0800, Yury Norov wrote: > > > On Fri, Dec 03, 2021 at 02:30:35PM +0200, Andy Shevchenko wrote: > > > > On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: > > > > > It's common practice to cast small variable arguments to the find_*_bit() > > > > > > Not that common - I found 19 examples of this cast, and most of them > > > are in drivers. > > > > I find 51 (most are in the for_each_* wrappers): > > > > $ RE=$(echo '\b('$(echo $(grep -E '^(unsigned long find|#define for_each)_' include/linux/find.h | cut -d'(' -f1 | awk '{print $NF}') | tr ' ' '|')')\(.*\(unsigned long \*\)') > > $ git grep -E "$RE" | wc -l > > 51 > > > > > > > This leads to the find helper dereferencing a full unsigned long, > > > > > regardless of the size of the actual variable. The unwanted bits > > > > > get masked away, but strictly speaking, a read beyond the end of > > > > > the target variable happens. Builds under -Warray-bounds complain > > > > > about this situation, for example: > > > > > > > > > > In file included from ./include/linux/bitmap.h:9, > > > > > from drivers/iommu/intel/iommu.c:17: > > > > > drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': > > > > > ./include/linux/find.h:119:37: error: array subscript 'long unsigned int[0]' is partly outside array bounds of 'int[1]' [-Werror=array-bounds] > > > > > 119 | unsigned long val = *addr & GENMASK(size - 1, 0); > > > > > | ^~~~~ > > > > > drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' > > > > > 2115 | int pds, max_pde; > > > > > | ^~~~~~~ > > > > > > The driver should be fixed. I would suggest using one of ffs/fls/ffz from > > > include/asm/bitops.h > > > > I don't think it's a good API design to make developers choose between > > functions based on the size of their target. > > Bitmap functions work identically for all sizes from 0 to INT_MAX - 1. > Users don't 'choose between functions based on the size of their target'. > > Can you explain more what you mean? > > > This also doesn't work well > > for the main problem which is the for_each_* usage. > > for_each_*_bit() requires a pointer to an array of unsigned longs. If > it's provided with something else, this is an error on a caller side. > > > The existing API is totally fine: it already diverts the constant > > expression small sizes to ffs/etc, and this change is only to that > > part. > > If you want to allow passing types other than unsigned long *, you need > to be consistent and propagate this change to other bitmap functions. > This is much more work than just fixing at most 48 wrong callers. > (48 because I inspected some callers manually, and they are fine.) > > > It's just changing the C description of how to get at the desired > > bits, so that -Warray-bounds doesn't (correctly) get upset about the > > wider-than-underlying-type OOB read. > > As you said, -Warray-bounds _correctly_ gets upset about the dangerous > typecasting. What suggested here is an attempt to shut down the > compiler warning with the cost of complication of the code and > possible maintenance issues. The correct example of handling tiny > bitmaps can be found for example in drivers/mtd/nand/raw/ams-delta.c: > > static void gpio_nand_io_write(struct gpio_nand *priv, u8 byte) > { > struct gpio_descs *data_gpiods = priv->data_gpiods; > DECLARE_BITMAP(values, BITS_PER_TYPE(byte)) = { byte, }; > > ... > } Or use memweight(), if it's more appropriate. > > This is one of the last issues with -Warray-bounds, which has proven to > > be an effective compiler flag for finding real bugs. Since this patch > > doesn't change performance, doesn't change the resulting executable > > instructions, doesn't require any caller changes, and helps gain global > > -Warray-bounds coverage, I'm hoping to convince you of its value. :) > > I'm all for enabling -Warray-bounds, but the warnings that it spots > only convinced me that bitmap API is used wrongly, and it should be > fixed. Can you please share the list of bitmap-related issues found > with -Warray-bounds that concerned you? I'll take a look and try to > make a patch that fixes it. > > Thanks, > Yury
On Tue, Dec 07, 2021 at 03:39:30PM -0800, Yury Norov wrote: > On Fri, Dec 03, 2021 at 03:01:30PM -0800, Kees Cook wrote: > > On Fri, Dec 03, 2021 at 10:26:38AM -0800, Yury Norov wrote: > > > On Fri, Dec 03, 2021 at 02:30:35PM +0200, Andy Shevchenko wrote: > > > > On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: > > > > > It's common practice to cast small variable arguments to the find_*_bit() > > > > > > Not that common - I found 19 examples of this cast, and most of them > > > are in drivers. > > > > I find 51 (most are in the for_each_* wrappers): > > > > $ RE=$(echo '\b('$(echo $(grep -E '^(unsigned long find|#define for_each)_' include/linux/find.h | cut -d'(' -f1 | awk '{print $NF}') | tr ' ' '|')')\(.*\(unsigned long \*\)') > > $ git grep -E "$RE" | wc -l > > 51 > > > > > > > This leads to the find helper dereferencing a full unsigned long, > > > > > regardless of the size of the actual variable. The unwanted bits > > > > > get masked away, but strictly speaking, a read beyond the end of > > > > > the target variable happens. Builds under -Warray-bounds complain > > > > > about this situation, for example: > > > > > > > > > > In file included from ./include/linux/bitmap.h:9, > > > > > from drivers/iommu/intel/iommu.c:17: > > > > > drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': > > > > > ./include/linux/find.h:119:37: error: array subscript 'long unsigned int[0]' is partly outside array bounds of 'int[1]' [-Werror=array-bounds] > > > > > 119 | unsigned long val = *addr & GENMASK(size - 1, 0); > > > > > | ^~~~~ > > > > > drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' > > > > > 2115 | int pds, max_pde; > > > > > | ^~~~~~~ > > > > > > The driver should be fixed. I would suggest using one of ffs/fls/ffz from > > > include/asm/bitops.h > > > > I don't think it's a good API design to make developers choose between > > functions based on the size of their target. > > Bitmap functions work identically for all sizes from 0 to INT_MAX - 1. > Users don't 'choose between functions based on the size of their target'. > > Can you explain more what you mean? I believe it was a reaction to your suggestion about ffs/ffz/etc. Kees, if we _know_ that the size of the value in question will always fit 32/64-bit, then ffs/ffz/etc is okay to use. OTOH, if the type of that value is unsigned long [] and bitmap APIs() is used, then of course the consistent use of bitmap APIs is preferable. I.o.w. uXX: ffX()/etc is fine. unsigned long: bitmap API. I believe that's what Yury meant.
From: Yury Norov > Sent: 07 December 2021 23:40 > > On Fri, Dec 03, 2021 at 03:01:30PM -0800, Kees Cook wrote: > > On Fri, Dec 03, 2021 at 10:26:38AM -0800, Yury Norov wrote: > > > On Fri, Dec 03, 2021 at 02:30:35PM +0200, Andy Shevchenko wrote: > > > > On Fri, Dec 03, 2021 at 02:08:46AM -0800, Kees Cook wrote: > > > > > It's common practice to cast small variable arguments to the find_*_bit() > > > > > > Not that common - I found 19 examples of this cast, and most of them > > > are in drivers. > > > > I find 51 (most are in the for_each_* wrappers): > > > > $ RE=$(echo '\b('$(echo $(grep -E '^(unsigned long find|#define for_each)_' include/linux/find.h | > cut -d'(' -f1 | awk '{print $NF}') | tr ' ' '|')')\(.*\(unsigned long \*\)') > > $ git grep -E "$RE" | wc -l > > 51 > > > > > > > This leads to the find helper dereferencing a full unsigned long, > > > > > regardless of the size of the actual variable. The unwanted bits > > > > > get masked away, but strictly speaking, a read beyond the end of > > > > > the target variable happens. Builds under -Warray-bounds complain > > > > > about this situation, for example: > > > > > > > > > > In file included from ./include/linux/bitmap.h:9, > > > > > from drivers/iommu/intel/iommu.c:17: > > > > > drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': > > > > > ./include/linux/find.h:119:37: error: array subscript 'long unsigned int[0]' is partly outside > array bounds of 'int[1]' [-Werror=array-bounds] > > > > > 119 | unsigned long val = *addr & GENMASK(size - 1, 0); > > > > > | ^~~~~ > > > > > drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' > > > > > 2115 | int pds, max_pde; > > > > > | ^~~~~~~ > > > > > > The driver should be fixed. I would suggest using one of ffs/fls/ffz from > > > include/asm/bitops.h > > > > I don't think it's a good API design to make developers choose between > > functions based on the size of their target. > > Bitmap functions work identically for all sizes from 0 to INT_MAX - 1. > Users don't 'choose between functions based on the size of their target'. > > Can you explain more what you mean? > > > This also doesn't work well > > for the main problem which is the for_each_* usage. > > for_each_*_bit() requires a pointer to an array of unsigned longs. If > it's provided with something else, this is an error on a caller side. > > > The existing API is totally fine: it already diverts the constant > > expression small sizes to ffs/etc, and this change is only to that > > part. > > If you want to allow passing types other than unsigned long *, you need > to be consistent and propagate this change to other bitmap functions. > This is much more work than just fixing at most 48 wrong callers. > (48 because I inspected some callers manually, and they are fine.) The type must be 'unsigned long *'. You must not use the bitmap functions on smaller types (eg int) if you know the maximum size is smaller. The code will do completely the wrong thing on BE systems. Even on x86-86 there have been issues with 8n+4 aligned int[] being passed and generating slow locked accesses when the buffer crosses a page boundary. So code that casts the argument to any of the bitmap function is really inherently broken. I think you'll also find code that is using the bitmap functions where it doesn't need locked updates. The implied locked updates are horribly inefficient on some architectures (hashed global locks have to be used). David - Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
On Tue, Dec 07, 2021 at 03:39:30PM -0800, Yury Norov wrote: > Bitmap functions work identically for all sizes from 0 to INT_MAX - 1. > Users don't 'choose between functions based on the size of their target'. > [...] > for_each_*_bit() requires a pointer to an array of unsigned longs. If > it's provided with something else, this is an error on a caller side. I have a sense we're both talking past each other. Let me try to show what I'm seeing: the code in the bitmap API chooses one of two paths: - if "size" is a constant expression and is sizeof(unsigned long) or smaller, mask to "size" and call into ff*() built-ins. - else, use a dynamic sized loop against a series of unsigned longs. For the dynamic size case, yes, absolutely, things must stay unsigned long aligned, etc, that makes sense. I don't want to change anything there. For the constant-expression size, this requirement does not hold. Every helper performs a constant expression sized mask of the argument before using ff*(), for example: unsigned long val; if (unlikely(offset >= size)) return size; val = *addr & GENMASK(size - 1, offset); return val ? __ffs(val) : size; In this case, the argument does _not_ need to be a pointer to native unsigned long. And this is seen in the many many places in the kernel using non-unsigned-long arguments with a constant-expression size. (e.g. an int with size 32).
On Tue, Dec 07, 2021 at 03:39:30PM -0800, Yury Norov wrote: > I'm all for enabling -Warray-bounds, but the warnings that it spots > only convinced me that bitmap API is used wrongly, and it should be > fixed. Can you please share the list of bitmap-related issues found > with -Warray-bounds that concerned you? I'll take a look and try to > make a patch that fixes it. On an x86 allmodconfig with -Warray-bounds, here are the bitmap warnings: In file included from ./include/linux/bitmap.h:9, from ./include/linux/cpumask.h:12, from ./arch/x86/include/asm/cpumask.h:5, from ./arch/x86/include/asm/msr.h:11, from ./arch/x86/include/asm/processor.h:22, from ./arch/x86/include/asm/cpufeature.h:5, from ./arch/x86/include/asm/thread_info.h:53, from ./include/linux/thread_info.h:60, from ./arch/x86/include/asm/preempt.h:7, from ./include/linux/preempt.h:78, from ./include/linux/spinlock.h:55, from ./include/linux/wait.h:9, from ./include/linux/wait_bit.h:8, from ./include/linux/fs.h:6, from ./include/linux/debugfs.h:15, from drivers/bus/mhi/core/init.c:7: drivers/bus/mhi/core/init.c: In function 'to_mhi_pm_state_str': ./include/linux/find.h:187:37: warning: array subscript 'long unsigned int[0]' is partly outside array bounds of 'enum mhi_pm_state[1]' [-Warray-bounds] 187 | unsigned long val = *addr & GENMASK(size - 1, 0); | ^~~~~ drivers/bus/mhi/core/init.c:80:51: note: while referencing 'state' 80 | const char *to_mhi_pm_state_str(enum mhi_pm_state state) | ~~~~~~~~~~~~~~~~~~^~~~~ In file included from ./include/linux/bitmap.h:9, from ./include/linux/cpumask.h:12, from ./include/linux/smp.h:13, from ./include/linux/lockdep.h:14, from ./include/linux/mutex.h:17, from ./include/linux/notifier.h:14, from ./include/linux/clk.h:14, from drivers/irqchip/irq-ingenic-tcu.c:7: drivers/irqchip/irq-ingenic-tcu.c: In function 'ingenic_tcu_intc_cascade': ./include/linux/find.h:40:23: warning: array subscript 'long unsigned int[0]' is partly outside array bounds of 'uint32_t[1]' {aka 'unsigned int[1]'} [-Warray-bounds] 40 | val = *addr & GENMASK(size - 1, offset); | ^~~~~ drivers/irqchip/irq-ingenic-tcu.c:30:18: note: while referencing 'irq_reg' 30 | uint32_t irq_reg, irq_mask; | ^~~~~~~ In file included from ./include/linux/bitmap.h:9, from ./include/linux/cpumask.h:12, from ./include/linux/smp.h:13, from ./include/linux/lockdep.h:14, from ./include/linux/mutex.h:17, from ./include/linux/notifier.h:14, from ./include/linux/clk.h:14, from drivers/irqchip/irq-ingenic-tcu.c:7: ./include/linux/find.h:40:23: warning: array subscript 'long unsigned int[0]' is partly outside array bounds of 'uint32_t[1]' {aka 'unsigned int[1]'} [-Warray-bounds] 40 | val = *addr & GENMASK(size - 1, offset); | ^~~~~ drivers/irqchip/irq-ingenic-tcu.c:30:18: note: while referencing 'irq_reg' 30 | uint32_t irq_reg, irq_mask; | ^~~~~~~ In file included from ./include/linux/bitmap.h:9, from drivers/iommu/intel/iommu.c:17: drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': ./include/linux/find.h:119:37: warning: array subscript 'long unsigned int[0]' is partly outside array bounds of 'int[1]' [-Warray-bounds] 119 | unsigned long val = *addr & GENMASK(size - 1, 0); | ^~~~~ drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' 2115 | int pds, max_pde; | ^~~~~~~ In file included from ./include/linux/bitmap.h:9, from ./include/linux/cpumask.h:12, from ./arch/x86/include/asm/cpumask.h:5, from ./arch/x86/include/asm/msr.h:11, from ./arch/x86/include/asm/processor.h:22, from ./arch/x86/include/asm/cpufeature.h:5, from ./arch/x86/include/asm/thread_info.h:53, from ./include/linux/thread_info.h:60, from ./arch/x86/include/asm/preempt.h:7, from ./include/linux/preempt.h:78, from ./include/linux/spinlock.h:55, from ./include/linux/swait.h:7, from ./include/linux/completion.h:12, from drivers/iio/adc/stmpe-adc.c:10: drivers/iio/adc/stmpe-adc.c: In function 'stmpe_adc_probe': ./include/linux/find.h:98:23: warning: array subscript 'long unsigned int[0]' is partly outside array bounds of 'u32[1]' {aka 'unsigned int[1]'} [-Warray-bounds] 98 | val = *addr | ~GENMASK(size - 1, offset); | ^~~~~ drivers/iio/adc/stmpe-adc.c:258:13: note: while referencing 'norequest_mask' 258 | u32 norequest_mask = 0; | ^~~~~~~~~~~~~~ In file included from ./include/linux/bitmap.h:9, from ./include/linux/cpumask.h:12, from ./arch/x86/include/asm/cpumask.h:5, from ./arch/x86/include/asm/msr.h:11, from ./arch/x86/include/asm/processor.h:22, from ./arch/x86/include/asm/cpufeature.h:5, from ./arch/x86/include/asm/thread_info.h:53, from ./include/linux/thread_info.h:60, from ./arch/x86/include/asm/preempt.h:7, from ./include/linux/preempt.h:78, from ./include/linux/spinlock.h:55, from ./include/linux/swait.h:7, from ./include/linux/completion.h:12, from drivers/iio/adc/stmpe-adc.c:10: ./include/linux/find.h:98:23: warning: array subscript 'long unsigned int[0]' is partly outside array bounds of 'u32[1]' {aka 'unsigned int[1]'} [-Warray-bounds] 98 | val = *addr | ~GENMASK(size - 1, offset); | ^~~~~ drivers/iio/adc/stmpe-adc.c:258:13: note: while referencing 'norequest_mask' 258 | u32 norequest_mask = 0; | ^~~~~~~~~~~~~~ I expect there are more outside of x86 allmodconfig. I still think it makes sense to have a single API that is forgiving with its inputs. We can change the API in one place and solve this for all callers.
On 03/12/2021 11.08, Kees Cook wrote: > It's common practice to cast small variable arguments to the find_*_bit() > helpers to unsigned long and then use a size argument smaller than > sizeof(unsigned long): > > unsigned int bits; > ... > out = find_first_bit((unsigned long *)&bits, 32); Those call sites need to be fixed, they are broken on BE anyway. And your __find_bits_deref does nothing to fix (paper over) that if, say, the caller uses an u32 to store an 8-bit bitmap. So NAK. Rasmus
diff --git a/include/linux/find.h b/include/linux/find.h index 5bb6db213bcb..5708d188b9cb 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -17,6 +17,41 @@ extern unsigned long _find_first_and_bit(const unsigned long *addr1, extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size); extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size); +static __always_inline +unsigned long __find_bits_deref(const void *addr, unsigned long size) +{ + unsigned long val; + + BUILD_BUG_ON(!small_const_nbits(size)); + /* + * This part of the routine will be evaluated at + * compile-time (due to small_const_nbits()), and only + * for values of "size" <= sizeof(unsigned long). As + * such, the compiler can see when the dereference of + * "addr" may be reading past the end of the variable + * (when it is smaller than unsigned long). While the + * GENMASK will clobber those bits for no exposure, it + * is still technically an OOB read. Instead, pick a + * better dereference width to avoid it entirely. + */ + switch (size) { + case 0 ... 8: + val = *(const unsigned char *)addr; + break; + case 9 ... 16: + val = *(const unsigned short *)addr; + break; + case 17 ... 32: + val = *(const unsigned int *)addr; + break; + default: + val = *(const unsigned long *)addr; + break; + } + + return val; +} + #ifndef find_next_bit /** * find_next_bit - find the next set bit in a memory region @@ -37,7 +72,8 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size, if (unlikely(offset >= size)) return size; - val = *addr & GENMASK(size - 1, offset); + val = __find_bits_deref(addr, size); + val &= GENMASK(size - 1, offset); return val ? __ffs(val) : size; } @@ -67,7 +103,9 @@ unsigned long find_next_and_bit(const unsigned long *addr1, if (unlikely(offset >= size)) return size; - val = *addr1 & *addr2 & GENMASK(size - 1, offset); + val = __find_bits_deref(addr1, size); + val &= __find_bits_deref(addr2, size); + val &= GENMASK(size - 1, offset); return val ? __ffs(val) : size; } @@ -95,7 +133,8 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, if (unlikely(offset >= size)) return size; - val = *addr | ~GENMASK(size - 1, offset); + val = __find_bits_deref(addr, size); + val |= ~GENMASK(size - 1, offset); return val == ~0UL ? size : ffz(val); } @@ -116,8 +155,10 @@ static inline unsigned long find_first_bit(const unsigned long *addr, unsigned long size) { if (small_const_nbits(size)) { - unsigned long val = *addr & GENMASK(size - 1, 0); + unsigned long val; + val = __find_bits_deref(addr, size); + val &= GENMASK(size - 1, 0); return val ? __ffs(val) : size; } @@ -141,8 +182,11 @@ unsigned long find_first_and_bit(const unsigned long *addr1, unsigned long size) { if (small_const_nbits(size)) { - unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0); + unsigned long val; + val = __find_bits_deref(addr1, size); + val &= __find_bits_deref(addr2, size); + val &= GENMASK(size - 1, 0); return val ? __ffs(val) : size; } @@ -163,8 +207,10 @@ static inline unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) { if (small_const_nbits(size)) { - unsigned long val = *addr | ~GENMASK(size - 1, 0); + unsigned long val; + val = __find_bits_deref(addr, size); + val |= ~GENMASK(size - 1, 0); return val == ~0UL ? size : ffz(val); } @@ -184,8 +230,10 @@ static inline unsigned long find_last_bit(const unsigned long *addr, unsigned long size) { if (small_const_nbits(size)) { - unsigned long val = *addr & GENMASK(size - 1, 0); + unsigned long val; + val = __find_bits_deref(addr, size); + val &= GENMASK(size - 1, 0); return val ? __fls(val) : size; }
It's common practice to cast small variable arguments to the find_*_bit() helpers to unsigned long and then use a size argument smaller than sizeof(unsigned long): unsigned int bits; ... out = find_first_bit((unsigned long *)&bits, 32); This leads to the find helper dereferencing a full unsigned long, regardless of the size of the actual variable. The unwanted bits get masked away, but strictly speaking, a read beyond the end of the target variable happens. Builds under -Warray-bounds complain about this situation, for example: In file included from ./include/linux/bitmap.h:9, from drivers/iommu/intel/iommu.c:17: drivers/iommu/intel/iommu.c: In function 'domain_context_mapping_one': ./include/linux/find.h:119:37: error: array subscript 'long unsigned int[0]' is partly outside array bounds of 'int[1]' [-Werror=array-bounds] 119 | unsigned long val = *addr & GENMASK(size - 1, 0); | ^~~~~ drivers/iommu/intel/iommu.c:2115:18: note: while referencing 'max_pde' 2115 | int pds, max_pde; | ^~~~~~~ Instead, just carefully read the correct variable size, all of which happens at compile time since small_const_nbits(size) has already determined that arguments are constant expressions. Signed-off-by: Kees Cook <keescook@chromium.org> --- include/linux/find.h | 62 +++++++++++++++++++++++++++++++++++++++----- 1 file changed, 55 insertions(+), 7 deletions(-)