Introduce the for_each_set_clump macro

This patch reimplements the thunderx_gpio_set_multiple function in drivers/gpio/gpio-thunderx.c to use the new for_each_set_clump macro. Instead of looping for each bank in thunderx_gpio_set_multiple function, now we can skip bank which is not set and save cycles.

Cc Robert Richter <[email protected]>

Cc Bartosz Golaszewski <[email protected]>

Signed-off-by Syed Nayyar Waris <[email protected]>

Signed-off-by William Breathitt Gray <[email protected]>

---
Changes in v12:
- No change.

This patch reimplements the xgpio_set_multiple() function in drivers/gpio/gpio-xilinx.c to use the new generic functions:
bitmap_get_value() and bitmap_set_value(). The code is now simpler to read and understand. Moreover, instead of looping for each bit in xgpio_set_multiple() function, now we can check each channel at a time and save cycles.

Quoted 7 lines · Syed Nayyar Waris

This patch reimplements the xgpio_set_multiple() function in drivers/gpio/gpio-xilinx.c to use the new generic functions:
bitmap_get_value() and bitmap_set_value(). The code is now simpler to read and understand. Moreover, instead of looping for each bit in xgpio_set_multiple() function, now we can check each channel at a time and save cycles.

This now causes -Wtype-limits warnings in linux-next with gcc-10:

drivers/gpio/gpio-xilinx.c static void xgpio_set_multiple(struct gpio_chip *gc, unsigned long *mask, · line 152

Quoted 13 lines

drivers/gpio/gpio-xilinx.c +12 -0

+       u32 *const state = chip->gpio_state;
+       unsigned int *const width = chip->gpio_width;
+
+       DECLARE_BITMAP(old, 64);
+       DECLARE_BITMAP(new, 64);
+       DECLARE_BITMAP(changed, 64);
+
+       spin_lock_irqsave(&chip->gpio_lock[0], flags);
+       spin_lock(&chip->gpio_lock[1]);
+
+       bitmap_set_value(old, state[0], 0, width[0]);
+       bitmap_set_value(old, state[1], width[0], width[1]);

In file included 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/timex.h:5,
                 from ../include/linux/timex.h:65,
                 from ../include/linux/time32.h:13,
                 from ../include/linux/time.h:73,
                 from ../include/linux/stat.h:19,
                 from ../include/linux/module.h:13,
                 from ../drivers/gpio/gpio-xilinx.c:11:
../include/linux/bitmap.h:639:18: warning: array subscript [1,
67108864] is outside array bounds of 'long unsigned int[1]'
[-Warray-bounds]
  639 |   map[index + 1] |= value >> space;
      |   ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
In file included from ../include/linux/kasan-checks.h:5,
                 from ../include/asm-generic/rwonce.h:26,
                 from ./arch/x86/include/generated/asm/rwonce.h:1,
                 from ../include/linux/compiler.h:246,
                 from ../include/linux/build_bug.h:5,
                 from ../include/linux/bits.h:22,
                 from ../include/linux/bitops.h:6,
                 from ../drivers/gpio/gpio-xilinx.c:8:

../drivers/gpio/gpio-xilinx.c:144:17: note: while referencing 'old'
144 | DECLARE_BITMAP(old, 64);
| ^~~
../include/linux/types.h:11:16: note: in definition of macro 'DECLARE_BITMAP'
11 | unsigned long name[BITS_TO_LONGS(bits)]
| ^~~~
In file included 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/timex.h:5,
                 from ../include/linux/timex.h:65,
                 from ../include/linux/time32.h:13,
                 from ../include/linux/time.h:73,
                 from ../include/linux/stat.h:19,
                 from ../include/linux/module.h:13,
                 from ../drivers/gpio/gpio-xilinx.c:11:

The compiler clearly tries to do range-checking here and notices that the index into the fixed-length array on the stack is not correctly bounded. It seems this would happen whenever width[0] + width[1] is larger than 64.

I have just submitted patches for all other -Wtype-limits warnings and would like to enable this option by default. Can you try to find a way to make this code safer? I would expect that you need a variant of bitmap_set_value() that takes an explicit ceiling here, and checks the stand and nbits values against that.

Arnd

Quoted 9 lines · Arnd Bergmann

Quoted 7 lines · Syed Nayyar Waris

This patch reimplements the xgpio_set_multiple() function in drivers/gpio/gpio-xilinx.c to use the new generic functions:
bitmap_get_value() and bitmap_set_value(). The code is now simpler to read and understand. Moreover, instead of looping for each bit in xgpio_set_multiple() function, now we can check each channel at a time and save cycles.

Quoted 1 line

This now causes -Wtype-limits warnings in linux-next with gcc-10:

Hi Arnd,

What version of gcc-10 are you running? I'm having trouble generating these warnings so I suspect I'm using a different version than you.

Let me first verify that I understand the problem correctly. The issue is the possibility of a stack smash in bitmap_set_value() when the value of start + nbits is larger than the length of the map bitmap memory region. This is because index (or index + 1) could be outside the range of the bitmap memory region passed in as map. Is my understanding correct here?

In xgpio_set_multiple(), the variables width[0] and width[1] serve as possible start and nbits values for the bitmap_set_value() calls. Because width[0] and width[1] are unsigned int variables, GCC considers the possibility that the value of width[0]/width[1] might exceed the length of the bitmap memory region named old and thus result in a stack smash.

I don't know if invalid width values are actually possible for the Xilinx gpio device, but let's err on the side of safety and assume this is actually a possibility. We should verify that the combined value of gpio_width[0] + gpio_width[1] does not exceed 64 bits; we can add a check for this in xgpio_probe() when we grab the gpio_width values.

However, we're still left with the GCC warnings because GCC is not smart enough to know that we've already checked the boundary and width[0] and width[1] are valid values. I suspect we can avoid this warning is we refactor bitmap_set_value() to increment map seperately and then set it:

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
        const unsigned long offset = start % BITS_PER_LONG;
        const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
        const unsigned long space = ceiling - start;

        map += BIT_WORD(start);
        value &= GENMASK(nbits - 1, 0);

        if (space >= nbits) {
                *map &= ~(GENMASK(nbits - 1, 0) << offset);
                *map |= value << offset;
        } else {
                *map &= ~BITMAP_FIRST_WORD_MASK(start);
                *map |= value << offset;
                map++;
                *map &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                *map |= value >> space;
        }
}

This avoids adding a costly conditional check inside bitmap_set_value() when almost all bitmap_set_value() calls will have static arguments with well-defined and obvious boundaries.

Do you think this would be an acceptable solution to resolve your GCC warnings?

Quoted 11 lines · William Breathitt Gray

Quoted 9 lines · Arnd Bergmann

Quoted 7 lines · Syed Nayyar Waris

This patch reimplements the xgpio_set_multiple() function in drivers/gpio/gpio-xilinx.c to use the new generic functions:
bitmap_get_value() and bitmap_set_value(). The code is now simpler to read and understand. Moreover, instead of looping for each bit in xgpio_set_multiple() function, now we can check each channel at a time and save cycles.

Quoted 6 lines

Quoted 1 line

This now causes -Wtype-limits warnings in linux-next with gcc-10:

Hi Arnd,

What version of gcc-10 are you running? I'm having trouble generating these warnings so I suspect I'm using a different version than you.

I originally saw it with the binaries from
https://mirrors.edge.kernel.org/pub/tools/crosstool/, but I have also been able to reproduce it with a minimal test case on the binaries from godbolt.org, see https://godbolt.org/z/Wq8q4n

Quoted 6 lines

Let me first verify that I understand the problem correctly. The issue is the possibility of a stack smash in bitmap_set_value() when the value of start + nbits is larger than the length of the map bitmap memory region. This is because index (or index + 1) could be outside the range of the bitmap memory region passed in as map. Is my understanding correct here?

Yes, that seems to be the case here.

Quoted 13 lines

In xgpio_set_multiple(), the variables width[0] and width[1] serve as possible start and nbits values for the bitmap_set_value() calls. Because width[0] and width[1] are unsigned int variables, GCC considers the possibility that the value of width[0]/width[1] might exceed the length of the bitmap memory region named old and thus result in a stack smash.

I don't know if invalid width values are actually possible for the Xilinx gpio device, but let's err on the side of safety and assume this is actually a possibility. We should verify that the combined value of gpio_width[0] + gpio_width[1] does not exceed 64 bits; we can add a check for this in xgpio_probe() when we grab the gpio_width values.

Quoted 4 lines

However, we're still left with the GCC warnings because GCC is not smart enough to know that we've already checked the boundary and width[0] and width[1] are valid values. I suspect we can avoid this warning is we refactor bitmap_set_value() to increment map seperately and then set it:

As I understand it, part of the problem is that gcc sees the possible range as being constrained by the operations on 'start' and 'nbits', in particular the shift in BIT_WORD() that put an upper bound on the index, but then it sees that the upper bound is higher than the upper bound of the array, i.e. element zero.

I added a check

      if (start >= 64 || start + size >= 64) return;

in the godbolt.org testcase, which does help limit the start index appropriately, but it is not sufficient to let the compiler see that the 'if (space >= nbits) ' condition is guaranteed to be true for all values here.

Quoted 27 lines

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
        const unsigned long offset = start % BITS_PER_LONG;
        const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
        const unsigned long space = ceiling - start;

        map += BIT_WORD(start);
        value &= GENMASK(nbits - 1, 0);

        if (space >= nbits) {
                *map &= ~(GENMASK(nbits - 1, 0) << offset);
                *map |= value << offset;
        } else {
                *map &= ~BITMAP_FIRST_WORD_MASK(start);
                *map |= value << offset;
                map++;
                *map &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                *map |= value >> space;
        }
}

This avoids adding a costly conditional check inside bitmap_set_value() when almost all bitmap_set_value() calls will have static arguments with well-defined and obvious boundaries.

Quoted 2 lines

Do you think this would be an acceptable solution to resolve your GCC warnings?

Unfortunately, it does not seem to make a difference, as gcc still knows that this compiles to the same result, and it produces the same warning as before (see https://godbolt.org/z/rjx34r)

Arnd

Quoted 11 lines · Arnd Bergmann

Quoted 6 lines

This avoids adding a costly conditional check inside bitmap_set_value() when almost all bitmap_set_value() calls will have static arguments with well-defined and obvious boundaries.

Do you think this would be an acceptable solution to resolve your GCC warnings?

Unfortunately, it does not seem to make a difference, as gcc still knows that this compiles to the same result, and it produces the same warning as before (see https://godbolt.org/z/rjx34r)

Quoted 1 line

Arnd

Hi Arnd,

Sharing a different version of bitmap_set_valuei() function. See below.

Let me know if the below solution looks good to you and if it resolves the above compiler warning.

(quoted diff) +4 -1

@@ -1,5 +1,5 @@
 static inline void bitmap_set_value(unsigned long *map,
-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

@@ -7,6 +7,9 @@ static inline void bitmap_set_value(unsigned long *map,
         const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
         const unsigned long space = ceiling - start;
 
+       if (index >= length)
+               return;
+
         value &= GENMASK(nbits - 1, 0);
 
         if (space >= nbits) {

Quoted 94 lines · Arnd Bergmann

Quoted 11 lines · William Breathitt Gray

Quoted 9 lines · Arnd Bergmann

Quoted 7 lines · Syed Nayyar Waris

This patch reimplements the xgpio_set_multiple() function in drivers/gpio/gpio-xilinx.c to use the new generic functions:
bitmap_get_value() and bitmap_set_value(). The code is now simpler to read and understand. Moreover, instead of looping for each bit in xgpio_set_multiple() function, now we can check each channel at a time and save cycles.

Quoted 6 lines

Quoted 1 line

This now causes -Wtype-limits warnings in linux-next with gcc-10:

Hi Arnd,

What version of gcc-10 are you running? I'm having trouble generating these warnings so I suspect I'm using a different version than you.

I originally saw it with the binaries from
https://mirrors.edge.kernel.org/pub/tools/crosstool/, but I have also been able to reproduce it with a minimal test case on the binaries from godbolt.org, see https://godbolt.org/z/Wq8q4n

Quoted 6 lines

Let me first verify that I understand the problem correctly. The issue is the possibility of a stack smash in bitmap_set_value() when the value of start + nbits is larger than the length of the map bitmap memory region. This is because index (or index + 1) could be outside the range of the bitmap memory region passed in as map. Is my understanding correct here?

Yes, that seems to be the case here.

Quoted 13 lines

In xgpio_set_multiple(), the variables width[0] and width[1] serve as possible start and nbits values for the bitmap_set_value() calls. Because width[0] and width[1] are unsigned int variables, GCC considers the possibility that the value of width[0]/width[1] might exceed the length of the bitmap memory region named old and thus result in a stack smash.

I don't know if invalid width values are actually possible for the Xilinx gpio device, but let's err on the side of safety and assume this is actually a possibility. We should verify that the combined value of gpio_width[0] + gpio_width[1] does not exceed 64 bits; we can add a check for this in xgpio_probe() when we grab the gpio_width values.

Quoted 4 lines

However, we're still left with the GCC warnings because GCC is not smart enough to know that we've already checked the boundary and width[0] and width[1] are valid values. I suspect we can avoid this warning is we refactor bitmap_set_value() to increment map seperately and then set it:

As I understand it, part of the problem is that gcc sees the possible range as being constrained by the operations on 'start' and 'nbits', in particular the shift in BIT_WORD() that put an upper bound on the index, but then it sees that the upper bound is higher than the upper bound of the array, i.e. element zero.

I added a check

      if (start >= 64 || start + size >= 64) return;

in the godbolt.org testcase, which does help limit the start index appropriately, but it is not sufficient to let the compiler see that the 'if (space >= nbits) ' condition is guaranteed to be true for all values here.

Quoted 27 lines

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
        const unsigned long offset = start % BITS_PER_LONG;
        const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
        const unsigned long space = ceiling - start;

        map += BIT_WORD(start);
        value &= GENMASK(nbits - 1, 0);

        if (space >= nbits) {
                *map &= ~(GENMASK(nbits - 1, 0) << offset);
                *map |= value << offset;
        } else {
                *map &= ~BITMAP_FIRST_WORD_MASK(start);
                *map |= value << offset;
                map++;
                *map &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                *map |= value >> space;
        }
}

This avoids adding a costly conditional check inside bitmap_set_value() when almost all bitmap_set_value() calls will have static arguments with well-defined and obvious boundaries.

Quoted 8 lines

Quoted 2 lines

Do you think this would be an acceptable solution to resolve your GCC warnings?

Unfortunately, it does not seem to make a difference, as gcc still knows that this compiles to the same result, and it produces the same warning as before (see https://godbolt.org/z/rjx34r)

Arnd

Hi Arnd,

Sharing a different version of bitmap_set_valuei() function. See below.

Let me know if the below solution looks good to you and if it resolves the above compiler warning.

(quoted diff) +4 -1

@@ -1,5 +1,5 @@
 static inline void bitmap_set_value(unsigned long *map,
-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

@@ -7,6 +7,9 @@ static inline void bitmap_set_value(unsigned long *map,
         const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
         const unsigned long space = ceiling - start;
 
+       if (index >= length)
+               return;
+
         value &= GENMASK(nbits - 1, 0);
 
         if (space >= nbits) {

Quoted 130 lines · Syed Nayyar Waris

Quoted 94 lines · Arnd Bergmann

Quoted 11 lines · William Breathitt Gray

Quoted 9 lines · Arnd Bergmann

Quoted 7 lines · Syed Nayyar Waris

This patch reimplements the xgpio_set_multiple() function in drivers/gpio/gpio-xilinx.c to use the new generic functions:
bitmap_get_value() and bitmap_set_value(). The code is now simpler to read and understand. Moreover, instead of looping for each bit in xgpio_set_multiple() function, now we can check each channel at a time and save cycles.

Quoted 6 lines

Quoted 1 line

This now causes -Wtype-limits warnings in linux-next with gcc-10:

Hi Arnd,

What version of gcc-10 are you running? I'm having trouble generating these warnings so I suspect I'm using a different version than you.

I originally saw it with the binaries from
https://mirrors.edge.kernel.org/pub/tools/crosstool/, but I have also been able to reproduce it with a minimal test case on the binaries from godbolt.org, see https://godbolt.org/z/Wq8q4n

Quoted 6 lines

Let me first verify that I understand the problem correctly. The issue is the possibility of a stack smash in bitmap_set_value() when the value of start + nbits is larger than the length of the map bitmap memory region. This is because index (or index + 1) could be outside the range of the bitmap memory region passed in as map. Is my understanding correct here?

Yes, that seems to be the case here.

Quoted 13 lines

In xgpio_set_multiple(), the variables width[0] and width[1] serve as possible start and nbits values for the bitmap_set_value() calls. Because width[0] and width[1] are unsigned int variables, GCC considers the possibility that the value of width[0]/width[1] might exceed the length of the bitmap memory region named old and thus result in a stack smash.

I don't know if invalid width values are actually possible for the Xilinx gpio device, but let's err on the side of safety and assume this is actually a possibility. We should verify that the combined value of gpio_width[0] + gpio_width[1] does not exceed 64 bits; we can add a check for this in xgpio_probe() when we grab the gpio_width values.

Quoted 4 lines

However, we're still left with the GCC warnings because GCC is not smart enough to know that we've already checked the boundary and width[0] and width[1] are valid values. I suspect we can avoid this warning is we refactor bitmap_set_value() to increment map seperately and then set it:

As I understand it, part of the problem is that gcc sees the possible range as being constrained by the operations on 'start' and 'nbits', in particular the shift in BIT_WORD() that put an upper bound on the index, but then it sees that the upper bound is higher than the upper bound of the array, i.e. element zero.

I added a check

      if (start >= 64 || start + size >= 64) return;

in the godbolt.org testcase, which does help limit the start index appropriately, but it is not sufficient to let the compiler see that the 'if (space >= nbits) ' condition is guaranteed to be true for all values here.

Quoted 27 lines

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
        const unsigned long offset = start % BITS_PER_LONG;
        const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
        const unsigned long space = ceiling - start;

        map += BIT_WORD(start);
        value &= GENMASK(nbits - 1, 0);

        if (space >= nbits) {
                *map &= ~(GENMASK(nbits - 1, 0) << offset);
                *map |= value << offset;
        } else {
                *map &= ~BITMAP_FIRST_WORD_MASK(start);
                *map |= value << offset;
                map++;
                *map &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                *map |= value >> space;
        }
}

This avoids adding a costly conditional check inside bitmap_set_value() when almost all bitmap_set_value() calls will have static arguments with well-defined and obvious boundaries.

Quoted 8 lines

Quoted 2 lines

Do you think this would be an acceptable solution to resolve your GCC warnings?

Unfortunately, it does not seem to make a difference, as gcc still knows that this compiles to the same result, and it produces the same warning as before (see https://godbolt.org/z/rjx34r)

Arnd

Hi Arnd,

Sharing a different version of bitmap_set_valuei() function. See below.

Let me know if the below solution looks good to you and if it resolves the above compiler warning.

(quoted diff) +4 -1

@@ -1,5 +1,5 @@
 static inline void bitmap_set_value(unsigned long *map,
-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

@@ -7,6 +7,9 @@ static inline void bitmap_set_value(unsigned long *map,
         const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
         const unsigned long space = ceiling - start;
 
+       if (index >= length)
+               return;
+
         value &= GENMASK(nbits - 1, 0);
 
         if (space >= nbits) {

Review static inline void bitmap_set_value(unsigned long *map, · line 27

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +18,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       return;
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

One of my concerns is that we're incurring the latency two additional conditional checks just to suppress a compiler warning about a case that wouldn't occur in the actual use of bitmap_set_value(). I'm hoping there's a way for us to suppress these warnings without adding onto the latency of this function; given that bitmap_set_value() is intended to be used in loops, conditionals here could significantly increase latency in drivers.

I wonder if array_index_nospec() might have the side effect of suppressing these warnings for us. For example, would this work:

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
	const unsigned long offset = start % BITS_PER_LONG;
	const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
	const unsigned long space = ceiling - start;
	size_t index = BIT_WORD(start);

	value &= GENMASK(nbits - 1, 0);

	if (space >= nbits) {
		index = array_index_nospec(index, index + 1);

		map[index] &= ~(GENMASK(nbits - 1, 0) << offset);
		map[index] |= value << offset;
	} else {
		index = array_index_nospec(index, index + 2);

		map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
		map[index + 0] |= value << offset;
		map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
		map[index + 1] |= value >> space;
	}
}

Or is this going to produce the same warning because we're not using an explicit check against the map array size?

William Breathitt Gray

Quoted 179 lines · William Breathitt Gray

Quoted 130 lines · Syed Nayyar Waris

Quoted 94 lines · Arnd Bergmann

Quoted 11 lines · William Breathitt Gray

Quoted 9 lines · Arnd Bergmann

Quoted 7 lines · Syed Nayyar Waris

This patch reimplements the xgpio_set_multiple() function in drivers/gpio/gpio-xilinx.c to use the new generic functions:
bitmap_get_value() and bitmap_set_value(). The code is now simpler to read and understand. Moreover, instead of looping for each bit in xgpio_set_multiple() function, now we can check each channel at a time and save cycles.

Quoted 6 lines

Quoted 1 line

This now causes -Wtype-limits warnings in linux-next with gcc-10:

Hi Arnd,

What version of gcc-10 are you running? I'm having trouble generating these warnings so I suspect I'm using a different version than you.

I originally saw it with the binaries from
https://mirrors.edge.kernel.org/pub/tools/crosstool/, but I have also been able to reproduce it with a minimal test case on the binaries from godbolt.org, see https://godbolt.org/z/Wq8q4n

Quoted 6 lines

Let me first verify that I understand the problem correctly. The issue is the possibility of a stack smash in bitmap_set_value() when the value of start + nbits is larger than the length of the map bitmap memory region. This is because index (or index + 1) could be outside the range of the bitmap memory region passed in as map. Is my understanding correct here?

Yes, that seems to be the case here.

Quoted 13 lines

In xgpio_set_multiple(), the variables width[0] and width[1] serve as possible start and nbits values for the bitmap_set_value() calls. Because width[0] and width[1] are unsigned int variables, GCC considers the possibility that the value of width[0]/width[1] might exceed the length of the bitmap memory region named old and thus result in a stack smash.

I don't know if invalid width values are actually possible for the Xilinx gpio device, but let's err on the side of safety and assume this is actually a possibility. We should verify that the combined value of gpio_width[0] + gpio_width[1] does not exceed 64 bits; we can add a check for this in xgpio_probe() when we grab the gpio_width values.

Quoted 4 lines

However, we're still left with the GCC warnings because GCC is not smart enough to know that we've already checked the boundary and width[0] and width[1] are valid values. I suspect we can avoid this warning is we refactor bitmap_set_value() to increment map seperately and then set it:

As I understand it, part of the problem is that gcc sees the possible range as being constrained by the operations on 'start' and 'nbits', in particular the shift in BIT_WORD() that put an upper bound on the index, but then it sees that the upper bound is higher than the upper bound of the array, i.e. element zero.

I added a check

      if (start >= 64 || start + size >= 64) return;

in the godbolt.org testcase, which does help limit the start index appropriately, but it is not sufficient to let the compiler see that the 'if (space >= nbits) ' condition is guaranteed to be true for all values here.

Quoted 27 lines

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
        const unsigned long offset = start % BITS_PER_LONG;
        const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
        const unsigned long space = ceiling - start;

        map += BIT_WORD(start);
        value &= GENMASK(nbits - 1, 0);

        if (space >= nbits) {
                *map &= ~(GENMASK(nbits - 1, 0) << offset);
                *map |= value << offset;
        } else {
                *map &= ~BITMAP_FIRST_WORD_MASK(start);
                *map |= value << offset;
                map++;
                *map &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                *map |= value >> space;
        }
}

This avoids adding a costly conditional check inside bitmap_set_value() when almost all bitmap_set_value() calls will have static arguments with well-defined and obvious boundaries.

Quoted 8 lines

Quoted 2 lines

Do you think this would be an acceptable solution to resolve your GCC warnings?

Unfortunately, it does not seem to make a difference, as gcc still knows that this compiles to the same result, and it produces the same warning as before (see https://godbolt.org/z/rjx34r)

Arnd

Hi Arnd,

Sharing a different version of bitmap_set_valuei() function. See below.

Let me know if the below solution looks good to you and if it resolves the above compiler warning.

(quoted diff) +4 -1

@@ -1,5 +1,5 @@
 static inline void bitmap_set_value(unsigned long *map,
-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

@@ -7,6 +7,9 @@ static inline void bitmap_set_value(unsigned long *map,
         const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
         const unsigned long space = ceiling - start;
 
+       if (index >= length)
+               return;
+
         value &= GENMASK(nbits - 1, 0);
 
         if (space >= nbits) {

Review static inline void bitmap_set_value(unsigned long *map, · line 27

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +18,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       return;
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

One of my concerns is that we're incurring the latency two additional conditional checks just to suppress a compiler warning about a case that wouldn't occur in the actual use of bitmap_set_value(). I'm hoping there's a way for us to suppress these warnings without adding onto the latency of this function; given that bitmap_set_value() is intended to be used in loops, conditionals here could significantly increase latency in drivers.

I wonder if array_index_nospec() might have the side effect of suppressing these warnings for us. For example, would this work:

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
      const unsigned long offset = start % BITS_PER_LONG;
      const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
      const unsigned long space = ceiling - start;
      size_t index = BIT_WORD(start);

      value &= GENMASK(nbits - 1, 0);

      if (space >= nbits) {
              index = array_index_nospec(index, index + 1);

              map[index] &= ~(GENMASK(nbits - 1, 0) << offset);
              map[index] |= value << offset;
      } else {
              index = array_index_nospec(index, index + 2);

              map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
              map[index + 0] |= value << offset;
              map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
              map[index + 1] |= value >> space;
      }
}

Quoted 4 lines

Or is this going to produce the same warning because we're not using an explicit check against the map array size?

William Breathitt Gray

After testing my suggestion, it looks like the warnings are still present. :-(

Something else I've also considered is perhaps using the GCC built-in function __builtin_unreachable() instead of returning. So in Syed's code we would have the following instead:

if (index + 1 >= length)

        __builtin_unreachable();

This might allow GCC to optimize better and avoid the conditional check all together, thus avoiding latency while also hinting enough context to the compiler to suppress the warnings.

William Breathitt Gray

Quoted 193 lines · William Breathitt Gray

Quoted 179 lines · William Breathitt Gray

Quoted 130 lines · Syed Nayyar Waris

Quoted 94 lines · Arnd Bergmann

Quoted 11 lines · William Breathitt Gray

Quoted 9 lines · Arnd Bergmann

Quoted 7 lines · Syed Nayyar Waris

This patch reimplements the xgpio_set_multiple() function in drivers/gpio/gpio-xilinx.c to use the new generic functions:
bitmap_get_value() and bitmap_set_value(). The code is now simpler to read and understand. Moreover, instead of looping for each bit in xgpio_set_multiple() function, now we can check each channel at a time and save cycles.

Quoted 6 lines

Quoted 1 line

This now causes -Wtype-limits warnings in linux-next with gcc-10:

Hi Arnd,

What version of gcc-10 are you running? I'm having trouble generating these warnings so I suspect I'm using a different version than you.

I originally saw it with the binaries from
https://mirrors.edge.kernel.org/pub/tools/crosstool/, but I have also been able to reproduce it with a minimal test case on the binaries from godbolt.org, see https://godbolt.org/z/Wq8q4n

Quoted 6 lines

Let me first verify that I understand the problem correctly. The issue is the possibility of a stack smash in bitmap_set_value() when the value of start + nbits is larger than the length of the map bitmap memory region. This is because index (or index + 1) could be outside the range of the bitmap memory region passed in as map. Is my understanding correct here?

Yes, that seems to be the case here.

Quoted 13 lines

In xgpio_set_multiple(), the variables width[0] and width[1] serve as possible start and nbits values for the bitmap_set_value() calls. Because width[0] and width[1] are unsigned int variables, GCC considers the possibility that the value of width[0]/width[1] might exceed the length of the bitmap memory region named old and thus result in a stack smash.

I don't know if invalid width values are actually possible for the Xilinx gpio device, but let's err on the side of safety and assume this is actually a possibility. We should verify that the combined value of gpio_width[0] + gpio_width[1] does not exceed 64 bits; we can add a check for this in xgpio_probe() when we grab the gpio_width values.

Quoted 4 lines

However, we're still left with the GCC warnings because GCC is not smart enough to know that we've already checked the boundary and width[0] and width[1] are valid values. I suspect we can avoid this warning is we refactor bitmap_set_value() to increment map seperately and then set it:

As I understand it, part of the problem is that gcc sees the possible range as being constrained by the operations on 'start' and 'nbits', in particular the shift in BIT_WORD() that put an upper bound on the index, but then it sees that the upper bound is higher than the upper bound of the array, i.e. element zero.

I added a check

      if (start >= 64 || start + size >= 64) return;

in the godbolt.org testcase, which does help limit the start index appropriately, but it is not sufficient to let the compiler see that the 'if (space >= nbits) ' condition is guaranteed to be true for all values here.

Quoted 27 lines

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
        const unsigned long offset = start % BITS_PER_LONG;
        const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
        const unsigned long space = ceiling - start;

        map += BIT_WORD(start);
        value &= GENMASK(nbits - 1, 0);

        if (space >= nbits) {
                *map &= ~(GENMASK(nbits - 1, 0) << offset);
                *map |= value << offset;
        } else {
                *map &= ~BITMAP_FIRST_WORD_MASK(start);
                *map |= value << offset;
                map++;
                *map &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                *map |= value >> space;
        }
}

This avoids adding a costly conditional check inside bitmap_set_value() when almost all bitmap_set_value() calls will have static arguments with well-defined and obvious boundaries.

Quoted 8 lines

Quoted 2 lines

Do you think this would be an acceptable solution to resolve your GCC warnings?

Unfortunately, it does not seem to make a difference, as gcc still knows that this compiles to the same result, and it produces the same warning as before (see https://godbolt.org/z/rjx34r)

Arnd

Hi Arnd,

Sharing a different version of bitmap_set_valuei() function. See below.

Let me know if the below solution looks good to you and if it resolves the above compiler warning.

(quoted diff) +4 -1

@@ -1,5 +1,5 @@
 static inline void bitmap_set_value(unsigned long *map,
-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

@@ -7,6 +7,9 @@ static inline void bitmap_set_value(unsigned long *map,
         const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
         const unsigned long space = ceiling - start;
 
+       if (index >= length)
+               return;
+
         value &= GENMASK(nbits - 1, 0);
 
         if (space >= nbits) {

Review static inline void bitmap_set_value(unsigned long *map, · line 27

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +18,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       return;
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

One of my concerns is that we're incurring the latency two additional conditional checks just to suppress a compiler warning about a case that wouldn't occur in the actual use of bitmap_set_value(). I'm hoping there's a way for us to suppress these warnings without adding onto the latency of this function; given that bitmap_set_value() is intended to be used in loops, conditionals here could significantly increase latency in drivers.

I wonder if array_index_nospec() might have the side effect of suppressing these warnings for us. For example, would this work:

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
      const unsigned long offset = start % BITS_PER_LONG;
      const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
      const unsigned long space = ceiling - start;
      size_t index = BIT_WORD(start);

      value &= GENMASK(nbits - 1, 0);

      if (space >= nbits) {
              index = array_index_nospec(index, index + 1);

              map[index] &= ~(GENMASK(nbits - 1, 0) << offset);
              map[index] |= value << offset;
      } else {
              index = array_index_nospec(index, index + 2);

              map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
              map[index + 0] |= value << offset;
              map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
              map[index + 1] |= value >> space;
      }
}

Quoted 4 lines

Or is this going to produce the same warning because we're not using an explicit check against the map array size?

William Breathitt Gray

After testing my suggestion, it looks like the warnings are still present. :-(

Something else I've also considered is perhaps using the GCC built-in function __builtin_unreachable() instead of returning. So in Syed's code we would have the following instead:

Quoted 8 lines

if (index + 1 >= length)

        __builtin_unreachable();

This might allow GCC to optimize better and avoid the conditional check all together, thus avoiding latency while also hinting enough context to the compiler to suppress the warnings.

William Breathitt Gray

I also thought of another optimization. Arnd, William, let me know what you think about it.

Since exceeding the array limit is a rather rare event, we can use the gcc extension: 'unlikely' for the boundary checks.
We can use it at the two places where 'index' and 'index + 1' is being checked against the boundary limit.

It might help optimize the code. Wouldn't it?

Syed Nayyar Waris

On Mon, Nov 09, 2020 at 06:04:11PM +0530, Syed Nayyar Waris wrote:

One of my concerns is that we're incurring the latency two additional conditional checks just to suppress a compiler warning about a case that wouldn't occur in the actual use of bitmap_set_value(). I'm hoping there's a way for us to suppress these warnings without adding onto the latency of this function; given that bitmap_set_value() is intended to be used in loops, conditionals here could significantly increase latency in drivers.

I wonder if array_index_nospec() might have the side effect of suppressing these warnings for us. For example, would this work:

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
        const unsigned long offset = start % BITS_PER_LONG;
        const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
        const unsigned long space = ceiling - start;
        size_t index = BIT_WORD(start);

        value &= GENMASK(nbits - 1, 0);

        if (space >= nbits) {
                index = array_index_nospec(index, index + 1);

                map[index] &= ~(GENMASK(nbits - 1, 0) << offset);
                map[index] |= value << offset;
        } else {
                index = array_index_nospec(index, index + 2);

                map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                map[index + 0] |= value << offset;
                map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                map[index + 1] |= value >> space;
        }
}

Or is this going to produce the same warning because we're not using an explicit check against the map array size?

Quoted 9 lines · William Breathitt Gray

On Mon, Nov 09, 2020 at 06:04:11PM +0530, Syed Nayyar Waris wrote:

One of my concerns is that we're incurring the latency two additional conditional checks just to suppress a compiler warning about a case that wouldn't occur in the actual use of bitmap_set_value(). I'm hoping there's a way for us to suppress these warnings without adding onto the latency of this function; given that bitmap_set_value() is intended to be used in loops, conditionals here could significantly increase latency in drivers.

At least for this caller, the size check would be a compile-time constant that can be eliminated.

Quoted 29 lines

I wonder if array_index_nospec() might have the side effect of suppressing these warnings for us. For example, would this work:

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
        const unsigned long offset = start % BITS_PER_LONG;
        const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
        const unsigned long space = ceiling - start;
        size_t index = BIT_WORD(start);

        value &= GENMASK(nbits - 1, 0);

        if (space >= nbits) {
                index = array_index_nospec(index, index + 1);

                map[index] &= ~(GENMASK(nbits - 1, 0) << offset);
                map[index] |= value << offset;
        } else {
                index = array_index_nospec(index, index + 2);

                map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                map[index + 0] |= value << offset;
                map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                map[index + 1] |= value >> space;
        }
}

Quoted 2 lines

Or is this going to produce the same warning because we're not using an explicit check against the map array size?

https://godbolt.org/z/fxnsG9

It still warns about the 'map[index + 1]' access: from all I can tell, gcc mainly complains because it cannot rule out that 'space < nbits', and then it knows the size of 'DECLARE_BITMAP(old, 64)' and finds that if 'index + 0' is correct, then 'index + 1' overflows that array.

Arnd

Quoted 47 lines · Arnd Bergmann

Quoted 9 lines · William Breathitt Gray

On Mon, Nov 09, 2020 at 06:04:11PM +0530, Syed Nayyar Waris wrote:

One of my concerns is that we're incurring the latency two additional conditional checks just to suppress a compiler warning about a case that wouldn't occur in the actual use of bitmap_set_value(). I'm hoping there's a way for us to suppress these warnings without adding onto the latency of this function; given that bitmap_set_value() is intended to be used in loops, conditionals here could significantly increase latency in drivers.

At least for this caller, the size check would be a compile-time constant that can be eliminated.

Quoted 29 lines

I wonder if array_index_nospec() might have the side effect of suppressing these warnings for us. For example, would this work:

static inline void bitmap_set_value(unsigned long *map,
unsigned long value,
unsigned long start, unsigned long nbits)

{
        const unsigned long offset = start % BITS_PER_LONG;
        const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
        const unsigned long space = ceiling - start;
        size_t index = BIT_WORD(start);

        value &= GENMASK(nbits - 1, 0);

        if (space >= nbits) {
                index = array_index_nospec(index, index + 1);

                map[index] &= ~(GENMASK(nbits - 1, 0) << offset);
                map[index] |= value << offset;
        } else {
                index = array_index_nospec(index, index + 2);

                map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                map[index + 0] |= value << offset;
                map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                map[index + 1] |= value >> space;
        }
}

Quoted 2 lines

Or is this going to produce the same warning because we're not using an explicit check against the map array size?

Quoted 8 lines

https://godbolt.org/z/fxnsG9

It still warns about the 'map[index + 1]' access: from all I can tell, gcc mainly complains because it cannot rule out that 'space < nbits', and then it knows the size of 'DECLARE_BITMAP(old, 64)' and finds that if 'index + 0' is correct, then 'index + 1' overflows that array.

Arnd

Hi Arnd,

As suggested by William, sharing another solution to suppress the compiler warning. Please let me know your views on the below fix. Thanks.

If its alright, I shall submit a (new) v13 patchset soon. Let me know.

(quoted diff) +1 -1

@@ -1,5 +1,5 @@
 static inline void bitmap_set_value(unsigned long *map,
-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Quoted 1 line · Syed Nayyar Waris

On Mon, Nov 09, 2020 at 03:41:53PM +0100, Arnd Bergmann wrote:

Quoted 7 lines

static inline void bitmap_set_value(unsigned long *map,

(quoted diff) +1 -1

-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Review static inline void bitmap_set_value(unsigned long *map, · line 24

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +15,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

Hi Syed,

Let's rename 'length' to 'nbits' as Arnd suggested, and rename 'nbits' to value_width.

Quoted 2 lines · William Breathitt Gray

Quoted 1 line · Syed Nayyar Waris

On Mon, Nov 09, 2020 at 03:41:53PM +0100, Arnd Bergmann wrote:

...

Quoted 20 lines

Quoted 7 lines

static inline void bitmap_set_value(unsigned long *map,

(quoted diff) +1 -1

-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Review static inline void bitmap_set_value(unsigned long *map, · line 24

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +15,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

Hi Syed,

Quoted 2 lines

Let's rename 'length' to 'nbits' as Arnd suggested, and rename 'nbits' to value_width.

length here is in longs. I guess this is the point of entire patch.

But to me sounds like it would be better to have simply bitmap_set_value64() / bitmap_set_value32() with proper optimization done and forget about variadic ones for now.

Quoted 26 lines · Andy Shevchenko

Quoted 2 lines · William Breathitt Gray

Quoted 1 line · Syed Nayyar Waris

On Mon, Nov 09, 2020 at 03:41:53PM +0100, Arnd Bergmann wrote:

...

Quoted 20 lines

Quoted 7 lines

static inline void bitmap_set_value(unsigned long *map,

(quoted diff) +1 -1

-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Review static inline void bitmap_set_value(unsigned long *map, · line 24

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +15,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

Hi Syed,

Quoted 4 lines

Quoted 2 lines

Let's rename 'length' to 'nbits' as Arnd suggested, and rename 'nbits' to value_width.

length here is in longs. I guess this is the point of entire patch.

Ah yes, this should become 'const unsigned long nbits' and represent the length of the bitmap in bits and not longs.

Quoted 3 lines

But to me sounds like it would be better to have simply bitmap_set_value64() / bitmap_set_value32() with proper optimization done and forget about variadic ones for now.

The gpio-xilinx driver can have arbitrary sizes for width[0] and width[1], so unfortunately that means we don't know the start position nor the width of the value beforehand.

Quoted 35 lines · William Breathitt Gray

Quoted 26 lines · Andy Shevchenko

Quoted 2 lines · William Breathitt Gray

Quoted 1 line · Syed Nayyar Waris

On Mon, Nov 09, 2020 at 03:41:53PM +0100, Arnd Bergmann wrote:

...

Quoted 20 lines

Quoted 7 lines

static inline void bitmap_set_value(unsigned long *map,

(quoted diff) +1 -1

-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Review static inline void bitmap_set_value(unsigned long *map, · line 24

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +15,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

Hi Syed,

Quoted 4 lines

Quoted 2 lines

Let's rename 'length' to 'nbits' as Arnd suggested, and rename 'nbits' to value_width.

length here is in longs. I guess this is the point of entire patch.

Ah yes, this should become 'const unsigned long nbits' and represent the length of the bitmap in bits and not longs.

Quoted 7 lines

Quoted 3 lines

But to me sounds like it would be better to have simply bitmap_set_value64() / bitmap_set_value32() with proper optimization done and forget about variadic ones for now.

The gpio-xilinx driver can have arbitrary sizes for width[0] and width[1], so unfortunately that means we don't know the start position nor the width of the value beforehand.

Start position should be all the time zero. You can't configure this IP to start from bit 2. Width can vary but start is IMHO all the time from 0 bit.

Thanks,
Michal

Quoted 30 lines · Michal Simek

Quoted 27 lines · William Breathitt Gray

Quoted 26 lines · Andy Shevchenko

Quoted 2 lines · William Breathitt Gray

Quoted 1 line · Syed Nayyar Waris

On Mon, Nov 09, 2020 at 03:41:53PM +0100, Arnd Bergmann wrote:

...

Quoted 20 lines

Quoted 7 lines

static inline void bitmap_set_value(unsigned long *map,

(quoted diff) +1 -1

-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Review static inline void bitmap_set_value(unsigned long *map, · line 24

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +15,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

Hi Syed,

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

Quoted 2 lines

Let's rename 'length' to 'nbits' as Arnd suggested, and rename 'nbits' to value_width.

length here is in longs. I guess this is the point of entire patch.

Ah yes, this should become 'const unsigned long nbits' and represent the length of the bitmap in bits and not longs.

Quoted 9 lines

Quoted 8 lines

Quoted 4 lines

But to me sounds like it would be better to have simply bitmap_set_value64() / bitmap_set_value32() with proper optimization done and forget about variadic ones for now.

The gpio-xilinx driver can have arbitrary sizes for width[0] and width[1], so unfortunately that means we don't know the start position nor the width of the value beforehand.

Quoted 6 lines

Start position should be all the time zero. You can't configure this IP to start from bit 2. Width can vary but start is IMHO all the time from 0 bit.

Thanks,
Michal

Hi Michal,

I'm referring to the mask creation, not the data bus transfer; see the implementation of the xgpio_set_multiple() function in linux-next for reference:
<https://git.kernel.org/pub/scm/linux/kernel/git/next/linux-next.git/tree/drivers/gpio/gpio-xilinx.c?h=akpm>.

To generate the old mask we call the following:

        bitmap_set_value(old, state[0], 0, width[0]);
        bitmap_set_value(old, state[1], width[0], width[1]);

Here, width[0] and width[1] can vary, which makes the exact values of the start and nbits parameters unknown beforehand (although we do know they are within the bitmap boundary).

Regardless, this is not an issue because we know the bitmap_set_value() is supposed to be called with valid values. We just need a way to hint to GCC that this is the case, without increasing the latency of the function -- which I think is possible if we use __builtin_unreachable() for the conditional path checking the index against the length of the bitmap.

William Breathitt Gray

Quoted 32 lines · William Breathitt Gray

Quoted 30 lines · Michal Simek

Quoted 27 lines · William Breathitt Gray

Quoted 26 lines · Andy Shevchenko

Quoted 2 lines · William Breathitt Gray

Quoted 1 line · Syed Nayyar Waris

On Mon, Nov 09, 2020 at 03:41:53PM +0100, Arnd Bergmann wrote:

...

Quoted 20 lines

Quoted 7 lines

static inline void bitmap_set_value(unsigned long *map,

(quoted diff) +1 -1

-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Review static inline void bitmap_set_value(unsigned long *map, · line 24

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +15,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

Hi Syed,

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

Quoted 2 lines

Let's rename 'length' to 'nbits' as Arnd suggested, and rename 'nbits' to value_width.

length here is in longs. I guess this is the point of entire patch.

Ah yes, this should become 'const unsigned long nbits' and represent the length of the bitmap in bits and not longs.

Hi William, Andy and All,

Thank You for reviewing. I was looking into the review comments and I have a question on the above.

Actually, in bitmap_set_value(), the intended comparison is to be made between 'index + 1' and 'length' (which is now renamed as 'nbits'). That is, the comparison would look-like as follows:
if (index + 1 >= nbits)

The 'index' is getting populated with BIT_WORD(start).
The 'index' variable in above is the actual index of the bitmap array, while in previous mail it is suggested to use 'nbits' which represent the length of the bitmap in bits and not longs.

Isn't it comparing two different things? index of array (not the bit-wise-length) on left hand side and nbits (bit-wise-length) on right hand side?

Have I misunderstood something? If yes, request to clarify.

Or do I have to first divide 'nbits' by BITS_PER_LONG and then compare it with 'index + 1'? Something like this?

Regards
Syed Nayyar Waris

Quoted 61 lines · Syed Nayyar Waris

Quoted 32 lines · William Breathitt Gray

Quoted 30 lines · Michal Simek

Quoted 27 lines · William Breathitt Gray

Quoted 26 lines · Andy Shevchenko

Quoted 2 lines · William Breathitt Gray

Quoted 1 line · Syed Nayyar Waris

On Mon, Nov 09, 2020 at 03:41:53PM +0100, Arnd Bergmann wrote:

...

Quoted 20 lines

Quoted 7 lines

static inline void bitmap_set_value(unsigned long *map,

(quoted diff) +1 -1

-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Review static inline void bitmap_set_value(unsigned long *map, · line 24

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +15,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

Hi Syed,

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

Quoted 2 lines

Let's rename 'length' to 'nbits' as Arnd suggested, and rename 'nbits' to value_width.

length here is in longs. I guess this is the point of entire patch.

Ah yes, this should become 'const unsigned long nbits' and represent the length of the bitmap in bits and not longs.

Hi William, Andy and All,

Thank You for reviewing. I was looking into the review comments and I have a question on the above.

Actually, in bitmap_set_value(), the intended comparison is to be made between 'index + 1' and 'length' (which is now renamed as 'nbits'). That is, the comparison would look-like as follows:
if (index + 1 >= nbits)

The 'index' is getting populated with BIT_WORD(start).
The 'index' variable in above is the actual index of the bitmap array, while in previous mail it is suggested to use 'nbits' which represent the length of the bitmap in bits and not longs.

Isn't it comparing two different things? index of array (not the bit-wise-length) on left hand side and nbits (bit-wise-length) on right hand side?

Quoted 7 lines

Have I misunderstood something? If yes, request to clarify.

Or do I have to first divide 'nbits' by BITS_PER_LONG and then compare it with 'index + 1'? Something like this?

Regards
Syed Nayyar Waris

The array elements of the bitmap memory region are abstracted away for the covenience of the users of the bitmap_* functions; the driver authors are able to treat their bitmaps as just a set of contiguous bits and not worry about where the division between array elements happen.

So to match the interface of the other bitmap_* functions, you should take in nbits and figure out the actual array length by dividing by BITS_PER_LONG inside bitmap_set_value(). Then you can use your conditional check (index + 1 >= length) like you have been doing so far.

William Breathitt Gray

Quoted 75 lines · William Breathitt Gray

Quoted 61 lines · Syed Nayyar Waris

Quoted 32 lines · William Breathitt Gray

Quoted 30 lines · Michal Simek

Quoted 27 lines · William Breathitt Gray

Quoted 26 lines · Andy Shevchenko

Quoted 2 lines · William Breathitt Gray

Quoted 1 line · Syed Nayyar Waris

On Mon, Nov 09, 2020 at 03:41:53PM +0100, Arnd Bergmann wrote:

...

Quoted 20 lines

Quoted 7 lines

static inline void bitmap_set_value(unsigned long *map,

(quoted diff) +1 -1

-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Review static inline void bitmap_set_value(unsigned long *map, · line 24

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +15,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

Hi Syed,

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

Quoted 2 lines

Let's rename 'length' to 'nbits' as Arnd suggested, and rename 'nbits' to value_width.

length here is in longs. I guess this is the point of entire patch.

Ah yes, this should become 'const unsigned long nbits' and represent the length of the bitmap in bits and not longs.

Hi William, Andy and All,

Thank You for reviewing. I was looking into the review comments and I have a question on the above.

Actually, in bitmap_set_value(), the intended comparison is to be made between 'index + 1' and 'length' (which is now renamed as 'nbits'). That is, the comparison would look-like as follows:
if (index + 1 >= nbits)

The 'index' is getting populated with BIT_WORD(start).
The 'index' variable in above is the actual index of the bitmap array, while in previous mail it is suggested to use 'nbits' which represent the length of the bitmap in bits and not longs.

Isn't it comparing two different things? index of array (not the bit-wise-length) on left hand side and nbits (bit-wise-length) on right hand side?

Quoted 7 lines

Have I misunderstood something? If yes, request to clarify.

Or do I have to first divide 'nbits' by BITS_PER_LONG and then compare it with 'index + 1'? Something like this?

Regards
Syed Nayyar Waris

The array elements of the bitmap memory region are abstracted away for the covenience of the users of the bitmap_* functions; the driver authors are able to treat their bitmaps as just a set of contiguous bits and not worry about where the division between array elements happen.

Quoted 6 lines

So to match the interface of the other bitmap_* functions, you should take in nbits and figure out the actual array length by dividing by BITS_PER_LONG inside bitmap_set_value(). Then you can use your conditional check (index + 1 >= length) like you have been doing so far.

William Breathitt Gray

Hi Arnd,

Sharing a new version of bitmap_set_value(). Let me know if it looks good and whether it suppresses the compiler warning.

The below patch is created against the v12 version of bitmap_set_value().

(quoted diff) +8 -7

-static inline void bitmap_set_value(unsigned long *map,
-                                    unsigned long value,
-                                    unsigned long start, unsigned long nbits)
+static inline void bitmap_set_value(unsigned long *map, unsigned long nbits,
+                                   unsigned long value, unsigned long value_width,
+                                   unsigned long start)
 {
-        const size_t index = BIT_WORD(start);
+        const unsigned long index = BIT_WORD(start);
+        const unsigned long length = BIT_WORD(nbits);
         const unsigned long offset = start % BITS_PER_LONG;
         const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
         const unsigned long space = ceiling - start;
 
-        value &= GENMASK(nbits - 1, 0);
+        value &= GENMASK(value_width - 1, 0);
 
-        if (space >= nbits) {
-                map[index] &= ~(GENMASK(nbits - 1, 0) << offset);
+        if (space >= value_width) {
+                map[index] &= ~(GENMASK(value_width - 1, 0) << offset);
                 map[index] |= value << offset;
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);

Quoted 116 lines · Syed Nayyar Waris

Quoted 75 lines · William Breathitt Gray

Quoted 61 lines · Syed Nayyar Waris

Quoted 32 lines · William Breathitt Gray

Quoted 30 lines · Michal Simek

Quoted 27 lines · William Breathitt Gray

Quoted 26 lines · Andy Shevchenko

Quoted 2 lines · William Breathitt Gray

Quoted 1 line · Syed Nayyar Waris

On Mon, Nov 09, 2020 at 03:41:53PM +0100, Arnd Bergmann wrote:

...

Quoted 20 lines

Quoted 7 lines

static inline void bitmap_set_value(unsigned long *map,

(quoted diff) +1 -1

-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Review static inline void bitmap_set_value(unsigned long *map, · line 24

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +15,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

Hi Syed,

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

Quoted 2 lines

Let's rename 'length' to 'nbits' as Arnd suggested, and rename 'nbits' to value_width.

length here is in longs. I guess this is the point of entire patch.

Ah yes, this should become 'const unsigned long nbits' and represent the length of the bitmap in bits and not longs.

Hi William, Andy and All,

Thank You for reviewing. I was looking into the review comments and I have a question on the above.

Actually, in bitmap_set_value(), the intended comparison is to be made between 'index + 1' and 'length' (which is now renamed as 'nbits'). That is, the comparison would look-like as follows:
if (index + 1 >= nbits)

The 'index' is getting populated with BIT_WORD(start).
The 'index' variable in above is the actual index of the bitmap array, while in previous mail it is suggested to use 'nbits' which represent the length of the bitmap in bits and not longs.

Isn't it comparing two different things? index of array (not the bit-wise-length) on left hand side and nbits (bit-wise-length) on right hand side?

Quoted 7 lines

Have I misunderstood something? If yes, request to clarify.

Or do I have to first divide 'nbits' by BITS_PER_LONG and then compare it with 'index + 1'? Something like this?

Regards
Syed Nayyar Waris

The array elements of the bitmap memory region are abstracted away for the covenience of the users of the bitmap_* functions; the driver authors are able to treat their bitmaps as just a set of contiguous bits and not worry about where the division between array elements happen.

Quoted 6 lines

So to match the interface of the other bitmap_* functions, you should take in nbits and figure out the actual array length by dividing by BITS_PER_LONG inside bitmap_set_value(). Then you can use your conditional check (index + 1 >= length) like you have been doing so far.

William Breathitt Gray

Hi Arnd,

Sharing a new version of bitmap_set_value(). Let me know if it looks good and whether it suppresses the compiler warning.

The below patch is created against the v12 version of bitmap_set_value().

(quoted diff) +8 -7

-static inline void bitmap_set_value(unsigned long *map,
-                                    unsigned long value,
-                                    unsigned long start, unsigned long nbits)
+static inline void bitmap_set_value(unsigned long *map, unsigned long nbits,
+                                   unsigned long value, unsigned long value_width,
+                                   unsigned long start)
 {
-        const size_t index = BIT_WORD(start);
+        const unsigned long index = BIT_WORD(start);
+        const unsigned long length = BIT_WORD(nbits);
         const unsigned long offset = start % BITS_PER_LONG;
         const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
         const unsigned long space = ceiling - start;
 
-        value &= GENMASK(nbits - 1, 0);
+        value &= GENMASK(value_width - 1, 0);
 
-        if (space >= nbits) {
-                map[index] &= ~(GENMASK(nbits - 1, 0) << offset);
+        if (space >= value_width) {
+                map[index] &= ~(GENMASK(value_width - 1, 0) << offset);
                 map[index] |= value << offset;
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);

Review

Quoted 10 lines

(quoted diff) +5 -1

                 map[index + 0] |= value << offset;
-                map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
+                map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + value_width);
                 map[index + 1] |= value >> space;
         }
 }

Hi Arnd,

What do you think of the above solution ( new version of bitmap_set_value() )? Does it look good?

Quoted 130 lines · Syed Nayyar Waris

Quoted 116 lines · Syed Nayyar Waris

Quoted 75 lines · William Breathitt Gray

Quoted 61 lines · Syed Nayyar Waris

Quoted 32 lines · William Breathitt Gray

Quoted 30 lines · Michal Simek

Quoted 27 lines · William Breathitt Gray

Quoted 26 lines · Andy Shevchenko

Quoted 2 lines · William Breathitt Gray

Quoted 1 line · Syed Nayyar Waris

On Mon, Nov 09, 2020 at 03:41:53PM +0100, Arnd Bergmann wrote:

...

Quoted 20 lines

Quoted 7 lines

static inline void bitmap_set_value(unsigned long *map,

(quoted diff) +1 -1

-                                    unsigned long value,
+                                    unsigned long value, const size_t length,
                                     unsigned long start, unsigned long nbits)
 {
         const size_t index = BIT_WORD(start);

Review static inline void bitmap_set_value(unsigned long *map, · line 24

Quoted 10 lines

(quoted diff) +4 -0

@@ -15,6 +15,10 @@ static inline void bitmap_set_value(unsigned long *map,
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
                 map[index + 0] |= value << offset;
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
                 map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
                 map[index + 1] |= value >> space;
         }

Hi Syed,

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

Quoted 2 lines

Let's rename 'length' to 'nbits' as Arnd suggested, and rename 'nbits' to value_width.

length here is in longs. I guess this is the point of entire patch.

Ah yes, this should become 'const unsigned long nbits' and represent the length of the bitmap in bits and not longs.

Hi William, Andy and All,

Thank You for reviewing. I was looking into the review comments and I have a question on the above.

Actually, in bitmap_set_value(), the intended comparison is to be made between 'index + 1' and 'length' (which is now renamed as 'nbits'). That is, the comparison would look-like as follows:
if (index + 1 >= nbits)

The 'index' is getting populated with BIT_WORD(start).
The 'index' variable in above is the actual index of the bitmap array, while in previous mail it is suggested to use 'nbits' which represent the length of the bitmap in bits and not longs.

Isn't it comparing two different things? index of array (not the bit-wise-length) on left hand side and nbits (bit-wise-length) on right hand side?

Quoted 7 lines

Have I misunderstood something? If yes, request to clarify.

Or do I have to first divide 'nbits' by BITS_PER_LONG and then compare it with 'index + 1'? Something like this?

Regards
Syed Nayyar Waris

The array elements of the bitmap memory region are abstracted away for the covenience of the users of the bitmap_* functions; the driver authors are able to treat their bitmaps as just a set of contiguous bits and not worry about where the division between array elements happen.

Quoted 6 lines

So to match the interface of the other bitmap_* functions, you should take in nbits and figure out the actual array length by dividing by BITS_PER_LONG inside bitmap_set_value(). Then you can use your conditional check (index + 1 >= length) like you have been doing so far.

William Breathitt Gray

Hi Arnd,

Sharing a new version of bitmap_set_value(). Let me know if it looks good and whether it suppresses the compiler warning.

The below patch is created against the v12 version of bitmap_set_value().

(quoted diff) +8 -7

-static inline void bitmap_set_value(unsigned long *map,
-                                    unsigned long value,
-                                    unsigned long start, unsigned long nbits)
+static inline void bitmap_set_value(unsigned long *map, unsigned long nbits,
+                                   unsigned long value, unsigned long value_width,
+                                   unsigned long start)
 {
-        const size_t index = BIT_WORD(start);
+        const unsigned long index = BIT_WORD(start);
+        const unsigned long length = BIT_WORD(nbits);
         const unsigned long offset = start % BITS_PER_LONG;
         const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
         const unsigned long space = ceiling - start;
 
-        value &= GENMASK(nbits - 1, 0);
+        value &= GENMASK(value_width - 1, 0);
 
-        if (space >= nbits) {
-                map[index] &= ~(GENMASK(nbits - 1, 0) << offset);
+        if (space >= value_width) {
+                map[index] &= ~(GENMASK(value_width - 1, 0) << offset);
                 map[index] |= value << offset;
         } else {
                 map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);

Review

Quoted 10 lines

(quoted diff) +5 -1

                 map[index + 0] |= value << offset;
-                map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
+
+               if (index + 1 >= length)
+                       __builtin_unreachable();
+
+                map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + value_width);
                 map[index + 1] |= value >> space;
         }
 }

Hi Arnd,

Quoted 2 lines

What do you think of the above solution ( new version of bitmap_set_value() )? Does it look good?

Sorry for the late reply and thanks for continuing to look at solutions.

I don't really like the idea of having the __builtin_unreachable() in there, since that would lead to even worse undefined behavior (jumping to a random instruction) than the previous one (writing to a random location) when invalid data gets passed.

Isn't passing the length of the bitmap sufficient to suppress the warning (sorry I did not try myself)? If not, maybe this could be a "BUG_ON(index + 1 >= length)" instead of the __builtin_unreachable(). That way it would at least crash in a well-defined way.

Arnd