Skip to contentSkip to conversation

Build failure with v4.9-rc1 and GCC trunk -- compiler weirdness

PATCH Will Deacon 10 participants 30 messages Oct 17, 2016 – Feb 2, 2017

Subsystems (3)
Kbuild Common clk Arm/Marvell Kirkwood and Armada 370, 375, 38x, 39x, XP, 3700, 7K/8K, CN9130 SoC support
lore
Share & tools
lore

Will Deacon

author
#0 lore raw

Hi all,

I'm seeing an arm64 build failure with -rc1 and GCC trunk, although I believe that the new compiler behaviour at the heart of the problem has the potential to affect other architectures and other pieces of kernel code relying on dead-code elimination to remove deliberately undefined functions.

The failure looks like:

  | drivers/built-in.o: In function `armada_3700_add_composite_clk':
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:
  | undefined reference to `____ilog2_NaN'
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:(.text+0xc72e0):
  | relocation truncated to fit: R_AARCH64_CALL26 against undefined symbol
  | `____ilog2_NaN'
  |
  | make: *** [vmlinux] Error 1

and if we look at the source for armada_3700_add_composite_clk, we see that this is caused by:

  int table_size = 0;

rate->reg = reg + (u64)rate->reg;
for (clkt = rate->table; clkt->div; clkt++)

	 table_size++;

rate->width = order_base_2(table_size);

order_base_2 calls ilog2, which has the ____ilog2_NaN call:

#define ilog2(n) \

(						\
	__builtin_constant_p(n) ? (		\
		(n) < 1 ? ____ilog2_NaN() :	\

This is because we're in a curious case where GCC has emitted a special-cased version of armada_3700_add_composite_clk, with table_size effectively constant-folded as 0. Whilst we shouldn't see this in a non-buggy kernel (hence the deliberate call to the undefined function ____ilog2_NaN), it means that the final link fails because we have a ____ilog2_NaN in the code, with a runtime check on table_size.

In other words, __builtin_constant_p appears to be weaker than we've been assuming. Talking to the compiler guys here, this is due to the "jump-threading" optimisation pass, so the patch below disables that.

A simpler example is:

int foo();
int bar();

int count(int *argc)

{
	int table_size = 0;

	for (; *argc; argc++)
		table_size++;

	if (__builtin_constant_p(table_size))
		return table_size == 0 ? foo() : bar();

	return bar();
}

which compiles to:

count:

	ldr	w0, [x0]
	cbz	w0, .L4
	b	bar
	.p2align 3

.L4:
b foo

and, with the "optimisation" disabled:

count:
b bar

Thoughts? It feels awfully fragile disabling passes like this, but with GCC transforming the code like this, I can't immediately think of a way to preserve the intended behaviour of the code.

Will

--->8

Makefile +5 -0
index 512e47a53e9a..750873d6d11e 100644
@@ -641,6 +641,11 @@ endif
 # Tell gcc to never replace conditional load with a non-conditional one
 KBUILD_CFLAGS	+= $(call cc-option,--param=allow-store-data-races=0)
 
+# Stop gcc from converting switches into a form that defeats dead code
+# elimination and can subsequently lead to calls to intentionally
+# undefined functions appearing in the final link.
+KBUILD_CFLAGS	+= $(call cc-option,--param=max-fsm-thread-path-insns=1)
+
 include scripts/Makefile.gcc-plugins
 
 ifdef CONFIG_READABLE_ASM
#1 lore raw
Quoted 38 lines · Will Deacon

Hi all,

I'm seeing an arm64 build failure with -rc1 and GCC trunk, although I believe that the new compiler behaviour at the heart of the problem has the potential to affect other architectures and other pieces of kernel code relying on dead-code elimination to remove deliberately undefined functions.

The failure looks like:

  | drivers/built-in.o: In function `armada_3700_add_composite_clk':
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:
  | undefined reference to `____ilog2_NaN'
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:(.text+0xc72e0):
  | relocation truncated to fit: R_AARCH64_CALL26 against undefined symbol
  | `____ilog2_NaN'
  |
  | make: *** [vmlinux] Error 1

and if we look at the source for armada_3700_add_composite_clk, we see that this is caused by:

  int table_size = 0;

  rate->reg = reg + (u64)rate->reg;
  for (clkt = rate->table; clkt->div; clkt++)
         table_size++;
  rate->width = order_base_2(table_size);

order_base_2 calls ilog2, which has the ____ilog2_NaN call:

#define ilog2(n)                                \
(                                               \
        __builtin_constant_p(n) ? (             \
                (n) < 1 ? ____ilog2_NaN() :     \
Quoted 7 lines

This is because we're in a curious case where GCC has emitted a special-cased version of armada_3700_add_composite_clk, with table_size effectively constant-folded as 0. Whilst we shouldn't see this in a non-buggy kernel (hence the deliberate call to the undefined function ____ilog2_NaN), it means that the final link fails because we have a ____ilog2_NaN in the code, with a runtime check on table_size.

This is indeed an unintended side effect, but I would not call it weird behaviour at all. The code in its current form does not handle the case where it could end up passing 0 into order_base_2(), and we simply need to handle that case. If order_base_2() is not defined for input 0, it should BUG() in that case, and the associated __builtin_unreachable() should prevent the special version from being emitted. If order_base_2() is defined for input 0, it should not invoke ilog2() with that argument, and the problem should go away as well.

Signature · 1 line
Ard.
Quoted 61 lines

In other words, __builtin_constant_p appears to be weaker than we've been assuming. Talking to the compiler guys here, this is due to the "jump-threading" optimisation pass, so the patch below disables that.

A simpler example is:

int foo();
int bar();

int count(int *argc)

{
        int table_size = 0;

        for (; *argc; argc++)
                table_size++;

        if (__builtin_constant_p(table_size))
                return table_size == 0 ? foo() : bar();

        return bar();
}

which compiles to:

count:

        ldr     w0, [x0]
        cbz     w0, .L4
        b       bar
        .p2align 3

.L4:
b foo

and, with the "optimisation" disabled:

count:
b bar

Thoughts? It feels awfully fragile disabling passes like this, but with GCC transforming the code like this, I can't immediately think of a way to preserve the intended behaviour of the code.

Will

--->8

Makefile +5 -0
index 512e47a53e9a..750873d6d11e 100644
@@ -641,6 +641,11 @@ endif
 # Tell gcc to never replace conditional load with a non-conditional one
 KBUILD_CFLAGS  += $(call cc-option,--param=allow-store-data-races=0)
 
+# Stop gcc from converting switches into a form that defeats dead code
+# elimination and can subsequently lead to calls to intentionally
+# undefined functions appearing in the final link.
+KBUILD_CFLAGS  += $(call cc-option,--param=max-fsm-thread-path-insns=1)
+
 include scripts/Makefile.gcc-plugins
 
 ifdef CONFIG_READABLE_ASM
author
#2 lore raw

Hi Ard,

Quoted 45 lines · Ard Biesheuvel
Quoted 36 lines · Will Deacon

I'm seeing an arm64 build failure with -rc1 and GCC trunk, although I believe that the new compiler behaviour at the heart of the problem has the potential to affect other architectures and other pieces of kernel code relying on dead-code elimination to remove deliberately undefined functions.

The failure looks like:

  | drivers/built-in.o: In function `armada_3700_add_composite_clk':
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:
  | undefined reference to `____ilog2_NaN'
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:(.text+0xc72e0):
  | relocation truncated to fit: R_AARCH64_CALL26 against undefined symbol
  | `____ilog2_NaN'
  |
  | make: *** [vmlinux] Error 1

and if we look at the source for armada_3700_add_composite_clk, we see that this is caused by:

  int table_size = 0;

  rate->reg = reg + (u64)rate->reg;
  for (clkt = rate->table; clkt->div; clkt++)
         table_size++;
  rate->width = order_base_2(table_size);

order_base_2 calls ilog2, which has the ____ilog2_NaN call:

#define ilog2(n)                                \
(                                               \
        __builtin_constant_p(n) ? (             \
                (n) < 1 ? ____ilog2_NaN() :     \
Quoted 7 lines

This is because we're in a curious case where GCC has emitted a special-cased version of armada_3700_add_composite_clk, with table_size effectively constant-folded as 0. Whilst we shouldn't see this in a non-buggy kernel (hence the deliberate call to the undefined function ____ilog2_NaN), it means that the final link fails because we have a ____ilog2_NaN in the code, with a runtime check on table_size.

Quoted 4 lines

This is indeed an unintended side effect, but I would not call it weird behaviour at all. The code in its current form does not handle the case where it could end up passing 0 into order_base_2(), and we simply need to handle that case.

The reasons I think it's weird are:

(1) The optimisation doesn't generate better code in this case -- optimising for the table_size == 0 case is uninformed, particularly as that *cannot* happen at runtime (GCC probably can't tell, due to things like container_of, but all the clock data is static).

(2) __builtin_constant_p(n) could be interpreted by a developer as "this code will execute with a constant n at runtime". With this issue, GCC could (in theory) generate a specialisation for every possible value of a variable, and return __builtin_constant_p as true for all of them, which somewhat undermines the point of the builtin.

Quoted 5 lines

If order_base_2() is not defined for input 0, it should BUG() in that case, and the associated __builtin_unreachable() should prevent the special version from being emitted. If order_base_2() is defined for input 0, it should not invoke ilog2() with that argument, and the problem should go away as well.

I don't necessarily think it should BUG() if it's not defined for input 0; things like __ffs don't do that and we'd be introducing conditional checks for cases that should not happen. The comment above order_base_2 does suggest that ob2(0) should return 0, but it can actually end up invoking ilog2(-1), which is obviously wrong.

I could update the comment, but that doesn't fix the build issue.

Will

#3 lore raw
Quoted 53 lines · Will Deacon

Hi Ard,

Quoted 45 lines · Ard Biesheuvel
Quoted 36 lines · Will Deacon

I'm seeing an arm64 build failure with -rc1 and GCC trunk, although I believe that the new compiler behaviour at the heart of the problem has the potential to affect other architectures and other pieces of kernel code relying on dead-code elimination to remove deliberately undefined functions.

The failure looks like:

  | drivers/built-in.o: In function `armada_3700_add_composite_clk':
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:
  | undefined reference to `____ilog2_NaN'
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:(.text+0xc72e0):
  | relocation truncated to fit: R_AARCH64_CALL26 against undefined symbol
  | `____ilog2_NaN'
  |
  | make: *** [vmlinux] Error 1

and if we look at the source for armada_3700_add_composite_clk, we see that this is caused by:

  int table_size = 0;

  rate->reg = reg + (u64)rate->reg;
  for (clkt = rate->table; clkt->div; clkt++)
         table_size++;
  rate->width = order_base_2(table_size);

order_base_2 calls ilog2, which has the ____ilog2_NaN call:

#define ilog2(n)                                \
(                                               \
        __builtin_constant_p(n) ? (             \
                (n) < 1 ? ____ilog2_NaN() :     \
Quoted 7 lines

This is because we're in a curious case where GCC has emitted a special-cased version of armada_3700_add_composite_clk, with table_size effectively constant-folded as 0. Whilst we shouldn't see this in a non-buggy kernel (hence the deliberate call to the undefined function ____ilog2_NaN), it means that the final link fails because we have a ____ilog2_NaN in the code, with a runtime check on table_size.

Quoted 4 lines

This is indeed an unintended side effect, but I would not call it weird behaviour at all. The code in its current form does not handle the case where it could end up passing 0 into order_base_2(), and we simply need to handle that case.

Quoted 7 lines

The reasons I think it's weird are:

(1) The optimisation doesn't generate better code in this case -- optimising for the table_size == 0 case is uninformed, particularly as that *cannot* happen at runtime (GCC probably can't tell, due to things like container_of, but all the clock data is static).

AFAICT, the references to the static clock data are indirected via of_device_get_match_data(), which means there is no way the compiler can prove that table_size is always non-zero.

Quoted 7 lines

(2) __builtin_constant_p(n) could be interpreted by a developer as "this code will execute with a constant n at runtime". With this issue, GCC could (in theory) generate a specialisation for every possible value of a variable, and return __builtin_constant_p as true for all of them, which somewhat undermines the point of the builtin.

Yes, and that would be perfectly legal from a correctness point of view, and would likely help performance as well. By using __builtin_constant_p(), you are choosing to perform a build time evaluation of an expression that would ordinarily be evaluated only at runtime. This implies that you have to address undefined behavior at build time rather than at runtime as well.

Quoted 6 lines
Quoted 5 lines

If order_base_2() is not defined for input 0, it should BUG() in that case, and the associated __builtin_unreachable() should prevent the special version from being emitted. If order_base_2() is defined for input 0, it should not invoke ilog2() with that argument, and the problem should go away as well.

Quoted 8 lines

I don't necessarily think it should BUG() if it's not defined for input 0; things like __ffs don't do that and we'd be introducing conditional checks for cases that should not happen. The comment above order_base_2 does suggest that ob2(0) should return 0, but it can actually end up invoking ilog2(-1), which is obviously wrong.

I could update the comment, but that doesn't fix the build issue.

Fixing roundup_pow_of_two() [which is arguably incorrect] would probably fix the build issue as well, no?

include/linux/log2.h +1 -1
index fd7ff3d91e6a..8a4be5e4223b 100644
@@ -168,7 +168,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 #define roundup_pow_of_two(n)                  \
 (                                              \
        __builtin_constant_p(n) ? (             \
-               (n == 1) ? 1 :                  \
+               (n <= 1) ? 1 :                  \
                (1UL << (ilog2((n) - 1) + 1))   \
                                   ) :          \
        __roundup_pow_of_two(n)                 \
#4 lore raw
Quoted 93 lines · Ard Biesheuvel
Quoted 53 lines · Will Deacon

Hi Ard,

Quoted 45 lines · Ard Biesheuvel
Quoted 36 lines · Will Deacon

I'm seeing an arm64 build failure with -rc1 and GCC trunk, although I believe that the new compiler behaviour at the heart of the problem has the potential to affect other architectures and other pieces of kernel code relying on dead-code elimination to remove deliberately undefined functions.

The failure looks like:

  | drivers/built-in.o: In function `armada_3700_add_composite_clk':
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:
  | undefined reference to `____ilog2_NaN'
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:(.text+0xc72e0):
  | relocation truncated to fit: R_AARCH64_CALL26 against undefined symbol
  | `____ilog2_NaN'
  |
  | make: *** [vmlinux] Error 1

and if we look at the source for armada_3700_add_composite_clk, we see that this is caused by:

  int table_size = 0;

  rate->reg = reg + (u64)rate->reg;
  for (clkt = rate->table; clkt->div; clkt++)
         table_size++;
  rate->width = order_base_2(table_size);

order_base_2 calls ilog2, which has the ____ilog2_NaN call:

#define ilog2(n)                                \
(                                               \
        __builtin_constant_p(n) ? (             \
                (n) < 1 ? ____ilog2_NaN() :     \
Quoted 7 lines

This is because we're in a curious case where GCC has emitted a special-cased version of armada_3700_add_composite_clk, with table_size effectively constant-folded as 0. Whilst we shouldn't see this in a non-buggy kernel (hence the deliberate call to the undefined function ____ilog2_NaN), it means that the final link fails because we have a ____ilog2_NaN in the code, with a runtime check on table_size.

Quoted 4 lines

This is indeed an unintended side effect, but I would not call it weird behaviour at all. The code in its current form does not handle the case where it could end up passing 0 into order_base_2(), and we simply need to handle that case.

Quoted 7 lines

The reasons I think it's weird are:

(1) The optimisation doesn't generate better code in this case -- optimising for the table_size == 0 case is uninformed, particularly as that *cannot* happen at runtime (GCC probably can't tell, due to things like container_of, but all the clock data is static).

AFAICT, the references to the static clock data are indirected via of_device_get_match_data(), which means there is no way the compiler can prove that table_size is always non-zero.

Quoted 7 lines

(2) __builtin_constant_p(n) could be interpreted by a developer as "this code will execute with a constant n at runtime". With this issue, GCC could (in theory) generate a specialisation for every possible value of a variable, and return __builtin_constant_p as true for all of them, which somewhat undermines the point of the builtin.

Yes, and that would be perfectly legal from a correctness point of view, and would likely help performance as well. By using __builtin_constant_p(), you are choosing to perform a build time evaluation of an expression that would ordinarily be evaluated only at runtime. This implies that you have to address undefined behavior at build time rather than at runtime as well.

Quoted 12 lines
Quoted 5 lines

If order_base_2() is not defined for input 0, it should BUG() in that case, and the associated __builtin_unreachable() should prevent the special version from being emitted. If order_base_2() is defined for input 0, it should not invoke ilog2() with that argument, and the problem should go away as well.

I don't necessarily think it should BUG() if it's not defined for input 0; things like __ffs don't do that and we'd be introducing conditional checks for cases that should not happen. The comment above order_base_2 does suggest that ob2(0) should return 0, but it can actually end up invoking ilog2(-1), which is obviously wrong.

Quoted 4 lines
Quoted 2 lines

I could update the comment, but that doesn't fix the build issue.

Fixing roundup_pow_of_two() [which is arguably incorrect]

I just spotted the comment that says it is undefined. But that means it could legally return 1 for input 0, i suppose

Quoted 16 lines

would
probably fix the build issue as well, no?

include/linux/log2.h +1 -1
index fd7ff3d91e6a..8a4be5e4223b 100644
@@ -168,7 +168,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 #define roundup_pow_of_two(n)                  \
 (                                              \
        __builtin_constant_p(n) ? (             \
-               (n == 1) ? 1 :                  \
+               (n <= 1) ? 1 :                  \
                (1UL << (ilog2((n) - 1) + 1))   \
                                   ) :          \
        __roundup_pow_of_two(n)                 \
#5 lore raw
Quoted 24 lines · CEST Ard Biesheuvel
Quoted 23 lines · Ard Biesheuvel
Quoted 2 lines · Will Deacon
Quoted 1 line · Ard Biesheuvel

On 17 October 2016 at 19:38, Will Deacon <[email protected]> wrote:

Yes, and that would be perfectly legal from a correctness point of view, and would likely help performance as well. By using __builtin_constant_p(), you are choosing to perform a build time evaluation of an expression that would ordinarily be evaluated only at runtime. This implies that you have to address undefined behavior at build time rather than at runtime as well.

Quoted 12 lines
Quoted 5 lines

If order_base_2() is not defined for input 0, it should BUG() in that case, and the associated __builtin_unreachable() should prevent the special version from being emitted. If order_base_2() is defined for input 0, it should not invoke ilog2() with that argument, and the problem should go away as well.

I don't necessarily think it should BUG() if it's not defined for input 0; things like __ffs don't do that and we'd be introducing conditional checks for cases that should not happen. The comment above order_base_2 does suggest that ob2(0) should return 0, but it can actually end up invoking ilog2(-1), which is obviously wrong.

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

I could update the comment, but that doesn't fix the build issue.

Fixing roundup_pow_of_two() [which is arguably incorrect]

I just spotted the comment that says it is undefined. But that means it could legally return 1 for input 0, i suppose

I think having the link error in roundup_pow_of_two() is safer than returning 1.

Why not turn it into a runtime warning in this driver?

drivers/clk/mvebu/armada-37xx-periph.c +4 -2
index cecb0fdfaef6..711d1d9842cc 100644
@@ -349,8 +349,10 @@ static int armada_3700_add_composite_clk(const struct clk_periph_data *data,
 			rate->reg = reg + (u64)rate->reg;
 			for (clkt = rate->table; clkt->div; clkt++)
 				table_size++;
-			rate->width = order_base_2(table_size);
-			rate->lock = lock;
+			if (!WARN_ON(table_size == 0)) {
+				rate->width = order_base_2(table_size);
+				rate->lock = lock;
+			}
 		}
 	}

Arnd

#6 lore raw
Quoted 45 lines · Arnd Bergmann
Quoted 24 lines · CEST Ard Biesheuvel
Quoted 23 lines · Ard Biesheuvel
Quoted 2 lines · Will Deacon
Quoted 1 line · Ard Biesheuvel

On 17 October 2016 at 19:38, Will Deacon <[email protected]> wrote:

Yes, and that would be perfectly legal from a correctness point of view, and would likely help performance as well. By using __builtin_constant_p(), you are choosing to perform a build time evaluation of an expression that would ordinarily be evaluated only at runtime. This implies that you have to address undefined behavior at build time rather than at runtime as well.

Quoted 12 lines
Quoted 5 lines

If order_base_2() is not defined for input 0, it should BUG() in that case, and the associated __builtin_unreachable() should prevent the special version from being emitted. If order_base_2() is defined for input 0, it should not invoke ilog2() with that argument, and the problem should go away as well.

I don't necessarily think it should BUG() if it's not defined for input 0; things like __ffs don't do that and we'd be introducing conditional checks for cases that should not happen. The comment above order_base_2 does suggest that ob2(0) should return 0, but it can actually end up invoking ilog2(-1), which is obviously wrong.

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

I could update the comment, but that doesn't fix the build issue.

Fixing roundup_pow_of_two() [which is arguably incorrect]

I just spotted the comment that says it is undefined. But that means it could legally return 1 for input 0, i suppose

I think having the link error in roundup_pow_of_two() is safer than returning 1.

Why not turn it into a runtime warning in this driver?

drivers/clk/mvebu/armada-37xx-periph.c +0 -0
index cecb0fdfaef6..711d1d9842cc 100644
@@ -349,8 +349,10 @@ static int armada_3700_add_composite_clk(const struct clk_periph_data *data,
                        rate->reg = reg + (u64)rate->reg;
                        for (clkt = rate->table; clkt->div; clkt++)

drivers/clk/mvebu/armada-37xx-periph.c static int armada_3700_add_composite_clk(const struct clk_periph_data *data, · line 358

Quoted 10 lines
drivers/clk/mvebu/armada-37xx-periph.c +4 -2
                                table_size++;
-                       rate->width = order_base_2(table_size);
-                       rate->lock = lock;
+                       if (!WARN_ON(table_size == 0)) {
+                               rate->width = order_base_2(table_size);
+                               rate->lock = lock;
+                       }
                }
        }

I guess Will is not looking for a way to fix the driver, but for a way to eliminate this issue entirely going forward.

In general, I think the issue where constant folding results in ilog2() or other similar functions being called with invalid build time constant parameter values is simply something we have to deal with.

In this case, it is in fact order_base_2() that deviates from its documented behavior (as Will points out), and fixing /that/ should make this particular issue go away afaict.

#7 lore raw
Quoted 24 lines · CEST Ard Biesheuvel
Quoted 10 lines

Why not turn it into a runtime warning in this driver?

drivers/clk/mvebu/armada-37xx-periph.c +0 -0
index cecb0fdfaef6..711d1d9842cc 100644
@@ -349,8 +349,10 @@ static int armada_3700_add_composite_clk(const struct clk_periph_data *data,
                        rate->reg = reg + (u64)rate->reg;
                        for (clkt = rate->table; clkt->div; clkt++)

drivers/clk/mvebu/armada-37xx-periph.c static int armada_3700_add_composite_clk(const struct clk_periph_data *data, · line 358

Quoted 10 lines
drivers/clk/mvebu/armada-37xx-periph.c +4 -2
                                table_size++;
-                       rate->width = order_base_2(table_size);
-                       rate->lock = lock;
+                       if (!WARN_ON(table_size == 0)) {
+                               rate->width = order_base_2(table_size);
+                               rate->lock = lock;
+                       }
                }
        }

I guess Will is not looking for a way to fix the driver, but for a way to eliminate this issue entirely going forward.

Quoted 8 lines

In general, I think the issue where constant folding results in ilog2() or other similar functions being called with invalid build time constant parameter values is simply something we have to deal with.

In this case, it is in fact order_base_2() that deviates from its documented behavior (as Will points out), and fixing /that/ should make this particular issue go away afaict.

Ah, right. I also noticed that order_base_2() is defined as log2(1 << (log2(n-1)+1)), which seems a bit redundant. Maybe we can simplify it to something like

#define order_base_2(n) ((n) <= 1) ? 0 : log2((n) - 1) + 1)

Arnd

#8 lore raw
In reply to Arnd Bergmann

Hi Arnd,

Quoted 43 lines · Arnd Bergmann
Quoted 24 lines · CEST Ard Biesheuvel
Quoted 23 lines · Ard Biesheuvel
Quoted 2 lines · Will Deacon
Quoted 1 line · Ard Biesheuvel

On 17 October 2016 at 19:38, Will Deacon <[email protected]> wrote:

Yes, and that would be perfectly legal from a correctness point of view, and would likely help performance as well. By using __builtin_constant_p(), you are choosing to perform a build time evaluation of an expression that would ordinarily be evaluated only at runtime. This implies that you have to address undefined behavior at build time rather than at runtime as well.

Quoted 12 lines
Quoted 5 lines

If order_base_2() is not defined for input 0, it should BUG() in that case, and the associated __builtin_unreachable() should prevent the special version from being emitted. If order_base_2() is defined for input 0, it should not invoke ilog2() with that argument, and the problem should go away as well.

I don't necessarily think it should BUG() if it's not defined for input 0; things like __ffs don't do that and we'd be introducing conditional checks for cases that should not happen. The comment above order_base_2 does suggest that ob2(0) should return 0, but it can actually end up invoking ilog2(-1), which is obviously wrong.

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

I could update the comment, but that doesn't fix the build issue.

Fixing roundup_pow_of_two() [which is arguably incorrect]

I just spotted the comment that says it is undefined. But that means it could legally return 1 for input 0, i suppose

I think having the link error in roundup_pow_of_two() is safer than returning 1.

Why not turn it into a runtime warning in this driver?

drivers/clk/mvebu/armada-37xx-periph.c +0 -0
index cecb0fdfaef6..711d1d9842cc 100644

drivers/clk/mvebu/armada-37xx-periph.c static int armada_3700_add_composite_clk(const struct clk_periph_data *data, · line 355

Quoted 9 lines
drivers/clk/mvebu/armada-37xx-periph.c +4 -2
@@ -349,8 +349,10 @@ static int armada_3700_add_composite_clk(const struct clk_periph_data *data,
 			rate->reg = reg + (u64)rate->reg;
 			for (clkt = rate->table; clkt->div; clkt++)
 				table_size++;
-			rate->width = order_base_2(table_size);
-			rate->lock = lock;
+			if (!WARN_ON(table_size == 0)) {
+				rate->width = order_base_2(table_size);
+				rate->lock = lock;
+			}

With the way the data are constructed in the driver I don't see how the table_size can be 0.

However I understand it is more something for the compiler.

In this case it is better to nullify the rate_hw as having width=0 will lead to trouble in the clk_divider operations

If it is the needed solution for this build error I can submit this kind of patch:

drivers/clk/mvebu/armada-37xx-periph.c +8 -3
index 45905fc0d75b..dbc49359406d 100644
@@ -345,11 +345,16 @@ static int armada_3700_add_composite_clk(const struct clk_periph_data *data,
                        const struct clk_div_table *clkt;
                        int table_size = 0;
 
-                       rate->reg = reg + (u64)rate->reg;
                        for (clkt = rate->table; clkt->div; clkt++)
                                table_size++;
-                       rate->width = order_base_2(table_size);
-                       rate->lock = lock;
+                       if (!WARN_ON(table_size == 0)) {
+                               rate->reg = reg + (u64)rate->reg;
+                               rate->width = order_base_2(table_size);
+                               rate->lock = lock;
+                       } else {
+                               rate_hw = NULL;
+                               rate_ops = NULL;
+                       }
                }
        }

Gregory

Quoted 11 lines
drivers/clk/mvebu/armada-37xx-periph.c +0 -0
 		}
 	}

Arnd

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Signature · 4 lines
Gregory Clement, Free Electrons
Kernel, drivers, real-time and embedded Linux
development, consulting, training and support.
http://free-electrons.com
#9 lore raw
In reply to Will Deacon
Quoted 11 lines · Will Deacon

Hi Ard,

Quoted 5 lines · Ard Biesheuvel

If order_base_2() is not defined for input 0, it should BUG() in that case, and the associated __builtin_unreachable() should prevent the special version from being emitted. If order_base_2() is defined for input 0, it should not invoke ilog2() with that argument, and the problem should go away as well.

I don't necessarily think it should BUG() if it's not defined for input 0;

In any case, Linus will have a rant about that: Linus has already been concerned about the abuse of BUG(). BUG() should not be used as an assert() replacement, but should be used where we have absolutely no other option than to crash the kernel, because (eg) continuing would result in the users' data being corrupted.

So no, BUG() is not the answer here.

Signature · 3 lines
RMK's Patch system: http://www.armlinux.org.uk/developer/patches/
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.
#10 lore raw
In reply to Will Deacon
Quoted 10 lines · Will Deacon

Hi all,

I'm seeing an arm64 build failure with -rc1 and GCC trunk, although I believe that the new compiler behaviour at the heart of the problem has the potential to affect other architectures and other pieces of kernel code relying on dead-code elimination to remove deliberately undefined functions.

The failure looks like:

Quoted 11 lines
  | drivers/built-in.o: In function `armada_3700_add_composite_clk':
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:
  | undefined reference to `____ilog2_NaN'
  |
  | linux/drivers/clk/mvebu/armada-37xx-periph.c:351:(.text+0xc72e0):
  | relocation truncated to fit: R_AARCH64_CALL26 against undefined symbol
  | `____ilog2_NaN'
  |
  | make: *** [vmlinux] Error 1

This is a gcc bug, see:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=72785

Signature · 1 line
Markus
#11 lore raw
Quoted 3 lines · Markus Trippelsdorf

This is a gcc bug, see:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=72785

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

I don't think the link-time check is so important that we need to notice it, and the "____ilog2_NaN()" could just be replaced with "0".

Linus

#12 lore raw
Quoted 9 lines · Linus Torvalds
Quoted 3 lines · Markus Trippelsdorf

This is a gcc bug, see:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=72785

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

Signature · 1 line
Markus
#13 lore raw
Quoted 7 lines · Markus Trippelsdorf
Quoted 6 lines · Linus Torvalds
Quoted 3 lines · Markus Trippelsdorf

This is a gcc bug, see:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=72785

Quoted 7 lines
Quoted 3 lines

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

order_base_2() is still broken though, given that it is documented as

* The first few values calculated by this routine:

 *  ob2(0) = 0
 *  ob2(1) = 0
 *  ob2(2) = 1
 *  ob2(3) = 2
 *  ob2(4) = 2
 *  ob2(5) = 3

whereas order_base_2(0) actually ends up invoking roundup_pow_of_two(0), which is documented as being undefined.

#14 lore raw
In reply to Markus Trippelsdorf
Quoted 8 lines · Markus Trippelsdorf
Quoted 4 lines · Linus Torvalds

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

Ahh, self-built? So it's not part of some experimental ARM distro setup and this will be annoying lots of people?

If so, still think that we could just get rid of the ____ilog2_NaN() thing as it's not _that_ important, but it's certainly not very high-priority. Will can do it in his tree too for testing, and it can remind people to get the gcc problem fixed.

Linus

author
#15 lore raw
Quoted 8 lines · Linus Torvalds
Quoted 6 lines · Markus Trippelsdorf
Quoted 4 lines · Linus Torvalds

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Quoted 5 lines
Quoted 2 lines

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

Ahh, self-built? So it's not part of some experimental ARM distro setup and this will be annoying lots of people?

Our friendly compiler guys built it, but it's just a snapshot of trunk, so it's all heading towards GCC 7.0. AFAIU, the problematic optimisation is also a mid-end pass, so it would affect other architectures too.

Quoted 4 lines

If so, still think that we could just get rid of the ____ilog2_NaN() thing as it's not _that_ important, but it's certainly not very high-priority. Will can do it in his tree too for testing, and it can remind people to get the gcc problem fixed.

I'm carrying the diff below, which fixes arm64 defconfig, but I'm worried that we might be relying on this trick elsewhere. The arm __bad_cmpxchg function, for example.

Will

--->8

include/linux/log2.h +2 -11
index fd7ff3d91e6a..9cf5ad69065d 100644
@@ -16,12 +16,6 @@
 #include <linux/bitops.h>
 
 /*
- * deal with unrepresentable constant logarithms
- */
-extern __attribute__((const, noreturn))
-int ____ilog2_NaN(void);
-
-/*
  * non-constant log of base 2 calculators
  * - the arch may override these in asm/bitops.h if they can be implemented
  *   more efficiently than using fls() and fls64()

@@ -85,7 +79,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 #define ilog2(n)				\
 (						\
 	__builtin_constant_p(n) ? (		\
-		(n) < 1 ? ____ilog2_NaN() :	\
+		(n) < 1 ? 0 :			\
 		(n) & (1ULL << 63) ? 63 :	\
 		(n) & (1ULL << 62) ? 62 :	\
 		(n) & (1ULL << 61) ? 61 :	\

@@ -149,9 +143,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 		(n) & (1ULL <<  3) ?  3 :	\
 		(n) & (1ULL <<  2) ?  2 :	\
 		(n) & (1ULL <<  1) ?  1 :	\
-		(n) & (1ULL <<  0) ?  0 :	\
-		____ilog2_NaN()			\
-				   ) :		\
+		0) :				\
 	(sizeof(n) <= 4) ?			\
 	__ilog2_u32(n) :			\
 	__ilog2_u64(n)				\

@@ -194,7 +186,6 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  * @n: parameter
  *
  * The first few values calculated by this routine:
- *  ob2(0) = 0
  *  ob2(1) = 0
  *  ob2(2) = 1
  *  ob2(3) = 2
#16 lore raw
Quoted 71 lines · Will Deacon
Quoted 8 lines · Linus Torvalds
Quoted 6 lines · Markus Trippelsdorf
Quoted 4 lines · Linus Torvalds

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Quoted 5 lines
Quoted 2 lines

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

Ahh, self-built? So it's not part of some experimental ARM distro setup and this will be annoying lots of people?

Our friendly compiler guys built it, but it's just a snapshot of trunk, so it's all heading towards GCC 7.0. AFAIU, the problematic optimisation is also a mid-end pass, so it would affect other architectures too.

Quoted 4 lines

If so, still think that we could just get rid of the ____ilog2_NaN() thing as it's not _that_ important, but it's certainly not very high-priority. Will can do it in his tree too for testing, and it can remind people to get the gcc problem fixed.

I'm carrying the diff below, which fixes arm64 defconfig, but I'm worried that we might be relying on this trick elsewhere. The arm __bad_cmpxchg function, for example.

Will

--->8

include/linux/log2.h +2 -10
index fd7ff3d91e6a..9cf5ad69065d 100644
@@ -16,12 +16,6 @@
 #include <linux/bitops.h>
 
 /*
- * deal with unrepresentable constant logarithms
- */
-extern __attribute__((const, noreturn))
-int ____ilog2_NaN(void);
-
-/*
  * non-constant log of base 2 calculators
  * - the arch may override these in asm/bitops.h if they can be implemented
  *   more efficiently than using fls() and fls64()

@@ -85,7 +79,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 #define ilog2(n)				\
 (						\
 	__builtin_constant_p(n) ? (		\
-		(n) < 1 ? ____ilog2_NaN() :	\
+		(n) < 1 ? 0 :			\
 		(n) & (1ULL << 63) ? 63 :	\
 		(n) & (1ULL << 62) ? 62 :	\
 		(n) & (1ULL << 61) ? 61 :	\

@@ -149,9 +143,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 		(n) & (1ULL <<  3) ?  3 :	\
 		(n) & (1ULL <<  2) ?  2 :	\
 		(n) & (1ULL <<  1) ?  1 :	\
-		(n) & (1ULL <<  0) ?  0 :	\
-		____ilog2_NaN()			\
-				   ) :		\
+		0) :				\
 	(sizeof(n) <= 4) ?			\
 	__ilog2_u32(n) :			\
 	__ilog2_u64(n)				\

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 191

Quoted 7 lines
include/linux/log2.h +0 -1
@@ -194,7 +186,6 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  * @n: parameter
  *
  * The first few values calculated by this routine:
- *  ob2(0) = 0
  *  ob2(1) = 0
  *  ob2(2) = 1
  *  ob2(3) = 2

Reviving this thread as gcc 7 has now hit Fedora rawhide and has this same issue. I pulled in the above patch from Will as a temporary work around for building. It didn't look like there was consensus on a permanent solution though from the thread.

Thanks,
Laura

#17 lore raw
Quoted 76 lines · Laura Abbott
Quoted 75 lines · Will Deacon
Quoted 8 lines · Linus Torvalds
Quoted 6 lines · Markus Trippelsdorf
Quoted 4 lines · Linus Torvalds

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Quoted 5 lines
Quoted 2 lines

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

Ahh, self-built? So it's not part of some experimental ARM distro setup and this will be annoying lots of people?

Our friendly compiler guys built it, but it's just a snapshot of trunk, so it's all heading towards GCC 7.0. AFAIU, the problematic optimisation is also a mid-end pass, so it would affect other architectures too.

Quoted 4 lines

If so, still think that we could just get rid of the ____ilog2_NaN() thing as it's not _that_ important, but it's certainly not very high-priority. Will can do it in his tree too for testing, and it can remind people to get the gcc problem fixed.

I'm carrying the diff below, which fixes arm64 defconfig, but I'm worried that we might be relying on this trick elsewhere. The arm __bad_cmpxchg function, for example.

Will

--->8

include/linux/log2.h +2 -11
index fd7ff3d91e6a..9cf5ad69065d 100644
@@ -16,12 +16,6 @@
 #include <linux/bitops.h>
 
 /*
- * deal with unrepresentable constant logarithms
- */
-extern __attribute__((const, noreturn))
-int ____ilog2_NaN(void);
-
-/*
  * non-constant log of base 2 calculators
  * - the arch may override these in asm/bitops.h if they can be implemented
  *   more efficiently than using fls() and fls64()

@@ -85,7 +79,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 #define ilog2(n)                             \
 (                                            \
      __builtin_constant_p(n) ? (             \
-             (n) < 1 ? ____ilog2_NaN() :     \
+             (n) < 1 ? 0 :                   \
              (n) & (1ULL << 63) ? 63 :       \
              (n) & (1ULL << 62) ? 62 :       \
              (n) & (1ULL << 61) ? 61 :       \

@@ -149,9 +143,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
              (n) & (1ULL <<  3) ?  3 :       \
              (n) & (1ULL <<  2) ?  2 :       \
              (n) & (1ULL <<  1) ?  1 :       \
-             (n) & (1ULL <<  0) ?  0 :       \
-             ____ilog2_NaN()                 \
-                                ) :          \
+             0) :                            \
      (sizeof(n) <= 4) ?                      \
      __ilog2_u32(n) :                        \
      __ilog2_u64(n)                          \

@@ -194,7 +186,6 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  * @n: parameter
  *
  * The first few values calculated by this routine:
- *  ob2(0) = 0
  *  ob2(1) = 0
Quoted 9 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 191

Quoted 3 lines
include/linux/log2.h +0 -0
  *  ob2(2) = 1
  *  ob2(3) = 2

Reviving this thread as gcc 7 has now hit Fedora rawhide and has this same issue. I pulled in the above patch from Will as a temporary work around for building. It didn't look like there was consensus on a permanent solution though from the thread.

I still think order_base_2() is broken, since it may invoke roundup_pow_of_two() with an input value that is documented as producing undefined output. I would argue that the below is the correct fix.

include/linux/log2.h +13 -1
index fd7ff3d91e6a..46523731bec0 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n ? 1UL << fls_long(n - 1) : 1;
+}
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       ilog2(__order_base_2(n))                \
+ )
 
 #endif /* _LINUX_LOG2_H */
#18 lore raw
Quoted 106 lines · Ard Biesheuvel
Quoted 76 lines · Laura Abbott
Quoted 75 lines · Will Deacon
Quoted 8 lines · Linus Torvalds
Quoted 6 lines · Markus Trippelsdorf
Quoted 4 lines · Linus Torvalds

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Quoted 5 lines
Quoted 2 lines

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

Ahh, self-built? So it's not part of some experimental ARM distro setup and this will be annoying lots of people?

Our friendly compiler guys built it, but it's just a snapshot of trunk, so it's all heading towards GCC 7.0. AFAIU, the problematic optimisation is also a mid-end pass, so it would affect other architectures too.

Quoted 4 lines

If so, still think that we could just get rid of the ____ilog2_NaN() thing as it's not _that_ important, but it's certainly not very high-priority. Will can do it in his tree too for testing, and it can remind people to get the gcc problem fixed.

I'm carrying the diff below, which fixes arm64 defconfig, but I'm worried that we might be relying on this trick elsewhere. The arm __bad_cmpxchg function, for example.

Will

--->8

include/linux/log2.h +2 -11
index fd7ff3d91e6a..9cf5ad69065d 100644
@@ -16,12 +16,6 @@
 #include <linux/bitops.h>
 
 /*
- * deal with unrepresentable constant logarithms
- */
-extern __attribute__((const, noreturn))
-int ____ilog2_NaN(void);
-
-/*
  * non-constant log of base 2 calculators
  * - the arch may override these in asm/bitops.h if they can be implemented
  *   more efficiently than using fls() and fls64()

@@ -85,7 +79,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 #define ilog2(n)                             \
 (                                            \
      __builtin_constant_p(n) ? (             \
-             (n) < 1 ? ____ilog2_NaN() :     \
+             (n) < 1 ? 0 :                   \
              (n) & (1ULL << 63) ? 63 :       \
              (n) & (1ULL << 62) ? 62 :       \
              (n) & (1ULL << 61) ? 61 :       \

@@ -149,9 +143,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
              (n) & (1ULL <<  3) ?  3 :       \
              (n) & (1ULL <<  2) ?  2 :       \
              (n) & (1ULL <<  1) ?  1 :       \
-             (n) & (1ULL <<  0) ?  0 :       \
-             ____ilog2_NaN()                 \
-                                ) :          \
+             0) :                            \
      (sizeof(n) <= 4) ?                      \
      __ilog2_u32(n) :                        \
      __ilog2_u64(n)                          \

@@ -194,7 +186,6 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  * @n: parameter
  *
  * The first few values calculated by this routine:
- *  ob2(0) = 0
  *  ob2(1) = 0
Quoted 9 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 191

Quoted 3 lines
include/linux/log2.h +0 -0
  *  ob2(2) = 1
  *  ob2(3) = 2

Reviving this thread as gcc 7 has now hit Fedora rawhide and has this same issue. I pulled in the above patch from Will as a temporary work around for building. It didn't look like there was consensus on a permanent solution though from the thread.

I still think order_base_2() is broken, since it may invoke roundup_pow_of_two() with an input value that is documented as producing undefined output. I would argue that the below is the correct fix.

include/linux/log2.h +5 -1
index fd7ff3d91e6a..46523731bec0 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n ? 1UL << fls_long(n - 1) : 1;
+}

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 220

Quoted 10 lines
include/linux/log2.h +8 -0
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       ilog2(__order_base_2(n))                \
+ )
 
 #endif /* _LINUX_LOG2_H */

Actually, there is a still a redundant shift/fls() in there, this is even simpler:

include/linux/log2.h +13 -1
index fd7ff3d91e6a..4741534bd7af 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n > 1 ? ilog2(n - 1) + 1 : 0;
+}
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       __order_base_2(n)                       \
+ )
 
 #endif /* _LINUX_LOG2_H */
#19 lore raw
Quoted 39 lines · Ard Biesheuvel
Quoted 19 lines · Ard Biesheuvel

I still think order_base_2() is broken, since it may invoke roundup_pow_of_two() with an input value that is documented as producing undefined output. I would argue that the below is the correct fix.

include/linux/log2.h +5 -1
index fd7ff3d91e6a..46523731bec0 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n ? 1UL << fls_long(n - 1) : 1;
+}

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 220

Quoted 10 lines
include/linux/log2.h +8 -0
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       ilog2(__order_base_2(n))                \
+ )
 
 #endif /* _LINUX_LOG2_H */

Actually, there is a still a redundant shift/fls() in there, this is even simpler:

include/linux/log2.h +0 -0
index fd7ff3d91e6a..4741534bd7af 100644

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 206

Quoted 5 lines
include/linux/log2.h +1 -1
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))

commonly __attribute_const__

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 218

Quoted 12 lines
include/linux/log2.h +12 -0
+unsigned long __order_base_2(unsigned long n)
+{
+       return n > 1 ? ilog2(n - 1) + 1 : 0;
+}
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       __order_base_2(n)                       \
+ )

Does this work properly when n is a signed negative value?

#20 lore raw
Quoted 43 lines · Joe Perches
Quoted 42 lines · Ard Biesheuvel
Quoted 19 lines · Ard Biesheuvel

I still think order_base_2() is broken, since it may invoke roundup_pow_of_two() with an input value that is documented as producing undefined output. I would argue that the below is the correct fix.

include/linux/log2.h +5 -1
index fd7ff3d91e6a..46523731bec0 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n ? 1UL << fls_long(n - 1) : 1;
+}

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 220

Quoted 10 lines
include/linux/log2.h +8 -0
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       ilog2(__order_base_2(n))                \
+ )
 
 #endif /* _LINUX_LOG2_H */

Actually, there is a still a redundant shift/fls() in there, this is even simpler:

include/linux/log2.h +0 -0
index fd7ff3d91e6a..4741534bd7af 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
Quoted 5 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 206

Quoted 2 lines
include/linux/log2.h +1 -1
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))

commonly __attribute_const__

... except in <linux/ilog2.h>, which probably predates that.

Quoted 6 lines
Quoted 6 lines
include/linux/log2.h +6 -0
+unsigned long __order_base_2(unsigned long n)
+{
+       return n > 1 ? ilog2(n - 1) + 1 : 0;
+}
+
+#define order_base_2(n)                                \
Quoted 9 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 218

Quoted 6 lines
include/linux/log2.h +6 -0
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       __order_base_2(n)                       \
+ )

Does this work properly when n is a signed negative value?

No, but order_base_2() is explicitly only defined for inputs [0, ->), so its behavior for negative inputs is best left undefined.

#21 lore raw
Quoted 68 lines · Ard Biesheuvel
Quoted 43 lines · Joe Perches
Quoted 42 lines · Ard Biesheuvel
Quoted 19 lines · Ard Biesheuvel

I still think order_base_2() is broken, since it may invoke roundup_pow_of_two() with an input value that is documented as producing undefined output. I would argue that the below is the correct fix.

include/linux/log2.h +5 -1
index fd7ff3d91e6a..46523731bec0 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n ? 1UL << fls_long(n - 1) : 1;
+}

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 220

Quoted 10 lines
include/linux/log2.h +8 -0
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       ilog2(__order_base_2(n))                \
+ )
 
 #endif /* _LINUX_LOG2_H */

Actually, there is a still a redundant shift/fls() in there, this is even simpler:

include/linux/log2.h +0 -0
index fd7ff3d91e6a..4741534bd7af 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
Quoted 5 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 206

Quoted 2 lines
include/linux/log2.h +1 -1
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))

commonly __attribute_const__

... except in <linux/ilog2.h>, which probably predates that.

Quoted 6 lines
Quoted 6 lines
include/linux/log2.h +6 -0
+unsigned long __order_base_2(unsigned long n)
+{
+       return n > 1 ? ilog2(n - 1) + 1 : 0;
+}
+
+#define order_base_2(n)                                \
Quoted 9 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 218

Quoted 6 lines
include/linux/log2.h +6 -0
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       __order_base_2(n)                       \
+ )

Does this work properly when n is a signed negative value?

Quoted 1 line

No, but order_base_2() is explicitly only defined for inputs [0, ->),

where?

Quoted 1 line

so its behavior for negative inputs is best left undefined.

Or maybe add a BUILD_BUG_ON something like:

#define order_base_2(n) \

({									\
	typeof(n) _n = n;						\
	BUILD_BUG_ON(__builtin_constant_p(_n) && _n < 0);		\
	__builtin_constant_p(_n) ? (_n < 2 ? _n :?ilog2((_n) - 1) + 1))	\
				 :?__order_base_2(_n);			\
})
#22 lore raw
Quoted 69 lines · Joe Perches
Quoted 68 lines · Ard Biesheuvel
Quoted 43 lines · Joe Perches
Quoted 42 lines · Ard Biesheuvel
Quoted 19 lines · Ard Biesheuvel

I still think order_base_2() is broken, since it may invoke roundup_pow_of_two() with an input value that is documented as producing undefined output. I would argue that the below is the correct fix.

include/linux/log2.h +5 -1
index fd7ff3d91e6a..46523731bec0 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n ? 1UL << fls_long(n - 1) : 1;
+}

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 220

Quoted 10 lines
include/linux/log2.h +8 -0
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       ilog2(__order_base_2(n))                \
+ )
 
 #endif /* _LINUX_LOG2_H */

Actually, there is a still a redundant shift/fls() in there, this is even simpler:

include/linux/log2.h +0 -0
index fd7ff3d91e6a..4741534bd7af 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
Quoted 5 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 206

Quoted 2 lines
include/linux/log2.h +1 -1
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))

commonly __attribute_const__

... except in <linux/ilog2.h>, which probably predates that.

Quoted 15 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 218

Quoted 12 lines
include/linux/log2.h +12 -0
+unsigned long __order_base_2(unsigned long n)
+{
+       return n > 1 ? ilog2(n - 1) + 1 : 0;
+}
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       __order_base_2(n)                       \
+ )

Does this work properly when n is a signed negative value?

Quoted 4 lines
Quoted 1 line

No, but order_base_2() is explicitly only defined for inputs [0, ->),

where?

The comment describes it as follows

/**
* order_base_2 - calculate the (rounded up) base 2 order of the argument
* @n: parameter
*
* The first few values calculated by this routine:

  *  ob2(0) = 0
  *  ob2(1) = 0
  *  ob2(2) = 1
  *  ob2(3) = 2
  *  ob2(4) = 2
  *  ob2(5) = 3
  *  ... and so on.

*/

i.e., it defines the output for inputs 0, 1, 2, 3, 4, 5, ..., and not for negative inputs, hence undefined.

Quoted 4 lines
Quoted 1 line

so its behavior for negative inputs is best left undefined.

Or maybe add a BUILD_BUG_ON something like:

Quoted 8 lines
#define order_base_2(n)                                                 \
({                                                                      \
        typeof(n) _n = n;                                               \
        BUILD_BUG_ON(__builtin_constant_p(_n) && _n < 0);               \
        __builtin_constant_p(_n) ? (_n < 2 ? _n : ilog2((_n) - 1) + 1)) \
                                 : __order_base_2(_n);                  \
})

This would interfere with the ability to use order_base_2() in initializers for global variables.

#23 lore raw
Quoted 1 line · Ard Biesheuvel

On 1 February 2017 at 19:49, Joe Perches <[email protected]> wrote:

[]

Quoted 11 lines
Quoted 10 lines

Or maybe add a BUILD_BUG_ON something like:

#define order_base_2(n)                                                 \
({                                                                      \
        typeof(n) _n = n;                                               \
        BUILD_BUG_ON(__builtin_constant_p(_n) && _n < 0);               \
        __builtin_constant_p(_n) ? (_n < 2 ? _n : ilog2((_n) - 1) + 1)) \
                                 : __order_base_2(_n);                  \
})
Quoted 2 lines

This would interfere with the ability to use order_base_2() in initializers for global variables.

There aren't any as far as I can tell and would using order_base_2() for a global initializer make sense?

#24 lore raw
Quoted 14 lines · Joe Perches
Quoted 1 line · Ard Biesheuvel

On 1 February 2017 at 19:49, Joe Perches <[email protected]> wrote:

[]

Quoted 11 lines
Quoted 10 lines

Or maybe add a BUILD_BUG_ON something like:

#define order_base_2(n)                                                 \
({                                                                      \
        typeof(n) _n = n;                                               \
        BUILD_BUG_ON(__builtin_constant_p(_n) && _n < 0);               \
        __builtin_constant_p(_n) ? (_n < 2 ? _n : ilog2((_n) - 1) + 1)) \
                                 : __order_base_2(_n);                  \
})
Quoted 6 lines
Quoted 2 lines

This would interfere with the ability to use order_base_2() in initializers for global variables.

There aren't any as far as I can tell and would using order_base_2() for a global initializer make sense?

Why wouldn't it make sense?

In any case, we could also solve this by doing this instead

#define order_base_2(n)                        \
(                                              \
       __builtin_constant_p(n) ? (             \
               ((n) == 0 || (n) == 1) ? 0 :    \
               ilog2((n) - 1) + 1) :           \
       __order_base_2(n)                       \

)

which will emit the usual unresolveable __ilog2_NaN reference when constants < 0 are passed to order_base_2()

#25 lore raw
In reply to Joe Perches
Quoted 9 lines · Joe Perches

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 218

Quoted 7 lines
include/linux/log2.h +7 -0
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       __order_base_2(n)                       \
+ )

Does this work properly when n is a signed negative value?

Do you see it returning a complex number?

#26 lore raw
In reply to Ard Biesheuvel
Quoted 107 lines · Ard Biesheuvel
Quoted 76 lines · Laura Abbott
Quoted 75 lines · Will Deacon
Quoted 8 lines · Linus Torvalds
Quoted 6 lines · Markus Trippelsdorf
Quoted 4 lines · Linus Torvalds

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Quoted 5 lines
Quoted 2 lines

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

Ahh, self-built? So it's not part of some experimental ARM distro setup and this will be annoying lots of people?

Our friendly compiler guys built it, but it's just a snapshot of trunk, so it's all heading towards GCC 7.0. AFAIU, the problematic optimisation is also a mid-end pass, so it would affect other architectures too.

Quoted 4 lines

If so, still think that we could just get rid of the ____ilog2_NaN() thing as it's not _that_ important, but it's certainly not very high-priority. Will can do it in his tree too for testing, and it can remind people to get the gcc problem fixed.

I'm carrying the diff below, which fixes arm64 defconfig, but I'm worried that we might be relying on this trick elsewhere. The arm __bad_cmpxchg function, for example.

Will

--->8

include/linux/log2.h +2 -11
index fd7ff3d91e6a..9cf5ad69065d 100644
@@ -16,12 +16,6 @@
 #include <linux/bitops.h>
 
 /*
- * deal with unrepresentable constant logarithms
- */
-extern __attribute__((const, noreturn))
-int ____ilog2_NaN(void);
-
-/*
  * non-constant log of base 2 calculators
  * - the arch may override these in asm/bitops.h if they can be implemented
  *   more efficiently than using fls() and fls64()

@@ -85,7 +79,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 #define ilog2(n)                             \
 (                                            \
      __builtin_constant_p(n) ? (             \
-             (n) < 1 ? ____ilog2_NaN() :     \
+             (n) < 1 ? 0 :                   \
              (n) & (1ULL << 63) ? 63 :       \
              (n) & (1ULL << 62) ? 62 :       \
              (n) & (1ULL << 61) ? 61 :       \

@@ -149,9 +143,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
              (n) & (1ULL <<  3) ?  3 :       \
              (n) & (1ULL <<  2) ?  2 :       \
              (n) & (1ULL <<  1) ?  1 :       \
-             (n) & (1ULL <<  0) ?  0 :       \
-             ____ilog2_NaN()                 \
-                                ) :          \
+             0) :                            \
      (sizeof(n) <= 4) ?                      \
      __ilog2_u32(n) :                        \
      __ilog2_u64(n)                          \

@@ -194,7 +186,6 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  * @n: parameter
  *
  * The first few values calculated by this routine:
- *  ob2(0) = 0
  *  ob2(1) = 0
Quoted 9 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 191

Quoted 3 lines
include/linux/log2.h +0 -0
  *  ob2(2) = 1
  *  ob2(3) = 2

Reviving this thread as gcc 7 has now hit Fedora rawhide and has this same issue. I pulled in the above patch from Will as a temporary work around for building. It didn't look like there was consensus on a permanent solution though from the thread.

I still think order_base_2() is broken, since it may invoke roundup_pow_of_two() with an input value that is documented as producing undefined output. I would argue that the below is the correct fix.

include/linux/log2.h +5 -1
index fd7ff3d91e6a..46523731bec0 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n ? 1UL << fls_long(n - 1) : 1;
+}

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 220

Quoted 10 lines
include/linux/log2.h +8 -0
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       ilog2(__order_base_2(n))                \
+ )
 
 #endif /* _LINUX_LOG2_H */

This fixes the problem although the comments should be updated as well. Is it worth fixing this for ilog2 as well just to avoid the link nonsense there as well?

Thanks,
Laura

#27 lore raw
Quoted 116 lines · Laura Abbott
Quoted 115 lines · Ard Biesheuvel
Quoted 76 lines · Laura Abbott
Quoted 75 lines · Will Deacon
Quoted 8 lines · Linus Torvalds
Quoted 6 lines · Markus Trippelsdorf
Quoted 4 lines · Linus Torvalds

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Quoted 5 lines
Quoted 2 lines

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

Ahh, self-built? So it's not part of some experimental ARM distro setup and this will be annoying lots of people?

Our friendly compiler guys built it, but it's just a snapshot of trunk, so it's all heading towards GCC 7.0. AFAIU, the problematic optimisation is also a mid-end pass, so it would affect other architectures too.

Quoted 4 lines

If so, still think that we could just get rid of the ____ilog2_NaN() thing as it's not _that_ important, but it's certainly not very high-priority. Will can do it in his tree too for testing, and it can remind people to get the gcc problem fixed.

I'm carrying the diff below, which fixes arm64 defconfig, but I'm worried that we might be relying on this trick elsewhere. The arm __bad_cmpxchg function, for example.

Will

--->8

include/linux/log2.h +2 -11
index fd7ff3d91e6a..9cf5ad69065d 100644
@@ -16,12 +16,6 @@
 #include <linux/bitops.h>
 
 /*
- * deal with unrepresentable constant logarithms
- */
-extern __attribute__((const, noreturn))
-int ____ilog2_NaN(void);
-
-/*
  * non-constant log of base 2 calculators
  * - the arch may override these in asm/bitops.h if they can be implemented
  *   more efficiently than using fls() and fls64()

@@ -85,7 +79,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 #define ilog2(n)                             \
 (                                            \
      __builtin_constant_p(n) ? (             \
-             (n) < 1 ? ____ilog2_NaN() :     \
+             (n) < 1 ? 0 :                   \
              (n) & (1ULL << 63) ? 63 :       \
              (n) & (1ULL << 62) ? 62 :       \
              (n) & (1ULL << 61) ? 61 :       \

@@ -149,9 +143,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
              (n) & (1ULL <<  3) ?  3 :       \
              (n) & (1ULL <<  2) ?  2 :       \
              (n) & (1ULL <<  1) ?  1 :       \
-             (n) & (1ULL <<  0) ?  0 :       \
-             ____ilog2_NaN()                 \
-                                ) :          \
+             0) :                            \
      (sizeof(n) <= 4) ?                      \
      __ilog2_u32(n) :                        \
      __ilog2_u64(n)                          \

@@ -194,7 +186,6 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  * @n: parameter
  *
  * The first few values calculated by this routine:
- *  ob2(0) = 0
  *  ob2(1) = 0
Quoted 9 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 191

Quoted 3 lines
include/linux/log2.h +0 -0
  *  ob2(2) = 1
  *  ob2(3) = 2

Reviving this thread as gcc 7 has now hit Fedora rawhide and has this same issue. I pulled in the above patch from Will as a temporary work around for building. It didn't look like there was consensus on a permanent solution though from the thread.

I still think order_base_2() is broken, since it may invoke roundup_pow_of_two() with an input value that is documented as producing undefined output. I would argue that the below is the correct fix.

include/linux/log2.h +13 -1
index fd7ff3d91e6a..46523731bec0 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n ? 1UL << fls_long(n - 1) : 1;
+}
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       ilog2(__order_base_2(n))                \
+ )
Quoted 5 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 220

Quoted 2 lines
include/linux/log2.h +0 -0
 #endif /* _LINUX_LOG2_H */

This fixes the problem although the comments should be updated as well.

This brings order_base_2() in line with the comments, so I am not sure what you'd want to update here?

Quoted 3 lines

Is it worth fixing this for ilog2 as well just to avoid the link nonsense there as well?

ilog2() is truly undefined for input 0, so the link nonsense is justified there imo

#28 lore raw
Quoted 117 lines · Ard Biesheuvel
Quoted 116 lines · Laura Abbott
Quoted 115 lines · Ard Biesheuvel
Quoted 76 lines · Laura Abbott
Quoted 75 lines · Will Deacon
Quoted 8 lines · Linus Torvalds
Quoted 6 lines · Markus Trippelsdorf
Quoted 4 lines · Linus Torvalds

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Quoted 5 lines
Quoted 2 lines

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

Ahh, self-built? So it's not part of some experimental ARM distro setup and this will be annoying lots of people?

Our friendly compiler guys built it, but it's just a snapshot of trunk, so it's all heading towards GCC 7.0. AFAIU, the problematic optimisation is also a mid-end pass, so it would affect other architectures too.

Quoted 4 lines

If so, still think that we could just get rid of the ____ilog2_NaN() thing as it's not _that_ important, but it's certainly not very high-priority. Will can do it in his tree too for testing, and it can remind people to get the gcc problem fixed.

I'm carrying the diff below, which fixes arm64 defconfig, but I'm worried that we might be relying on this trick elsewhere. The arm __bad_cmpxchg function, for example.

Will

--->8

include/linux/log2.h +2 -11
index fd7ff3d91e6a..9cf5ad69065d 100644
@@ -16,12 +16,6 @@
 #include <linux/bitops.h>
 
 /*
- * deal with unrepresentable constant logarithms
- */
-extern __attribute__((const, noreturn))
-int ____ilog2_NaN(void);
-
-/*
  * non-constant log of base 2 calculators
  * - the arch may override these in asm/bitops.h if they can be implemented
  *   more efficiently than using fls() and fls64()

@@ -85,7 +79,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 #define ilog2(n)                             \
 (                                            \
      __builtin_constant_p(n) ? (             \
-             (n) < 1 ? ____ilog2_NaN() :     \
+             (n) < 1 ? 0 :                   \
              (n) & (1ULL << 63) ? 63 :       \
              (n) & (1ULL << 62) ? 62 :       \
              (n) & (1ULL << 61) ? 61 :       \

@@ -149,9 +143,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
              (n) & (1ULL <<  3) ?  3 :       \
              (n) & (1ULL <<  2) ?  2 :       \
              (n) & (1ULL <<  1) ?  1 :       \
-             (n) & (1ULL <<  0) ?  0 :       \
-             ____ilog2_NaN()                 \
-                                ) :          \
+             0) :                            \
      (sizeof(n) <= 4) ?                      \
      __ilog2_u32(n) :                        \
      __ilog2_u64(n)                          \

@@ -194,7 +186,6 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  * @n: parameter
  *
  * The first few values calculated by this routine:
- *  ob2(0) = 0
  *  ob2(1) = 0
Quoted 9 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 191

Quoted 3 lines
include/linux/log2.h +0 -0
  *  ob2(2) = 1
  *  ob2(3) = 2

Reviving this thread as gcc 7 has now hit Fedora rawhide and has this same issue. I pulled in the above patch from Will as a temporary work around for building. It didn't look like there was consensus on a permanent solution though from the thread.

I still think order_base_2() is broken, since it may invoke roundup_pow_of_two() with an input value that is documented as producing undefined output. I would argue that the below is the correct fix.

include/linux/log2.h +13 -1
index fd7ff3d91e6a..46523731bec0 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n ? 1UL << fls_long(n - 1) : 1;
+}
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       ilog2(__order_base_2(n))                \
+ )
Quoted 9 lines
Quoted 5 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 220

Quoted 2 lines
include/linux/log2.h +0 -0
 #endif /* _LINUX_LOG2_H */

This fixes the problem although the comments should be updated as well.

This brings order_base_2() in line with the comments, so I am not sure what you'd want to update here?

ob2(1) = 1 for the __builtin_constant_p case which doesn't match the comment of ob2(1) = 0. So my statement should actually be is this correct?

Thanks,
Laura

#29 lore raw
Quoted 128 lines · Laura Abbott
Quoted 117 lines · Ard Biesheuvel
Quoted 116 lines · Laura Abbott
Quoted 115 lines · Ard Biesheuvel
Quoted 76 lines · Laura Abbott
Quoted 75 lines · Will Deacon
Quoted 8 lines · Linus Torvalds
Quoted 6 lines · Markus Trippelsdorf
Quoted 4 lines · Linus Torvalds

Well, in the meantime we apparently have to live with it. Unless Will is using some unreleased gcc version that nobody else is using and we can just ignore it?

Quoted 5 lines
Quoted 2 lines

Yes, he is using gcc-7 that is unreleased. (It will be released April next year.)

Ahh, self-built? So it's not part of some experimental ARM distro setup and this will be annoying lots of people?

Our friendly compiler guys built it, but it's just a snapshot of trunk, so it's all heading towards GCC 7.0. AFAIU, the problematic optimisation is also a mid-end pass, so it would affect other architectures too.

Quoted 4 lines

If so, still think that we could just get rid of the ____ilog2_NaN() thing as it's not _that_ important, but it's certainly not very high-priority. Will can do it in his tree too for testing, and it can remind people to get the gcc problem fixed.

I'm carrying the diff below, which fixes arm64 defconfig, but I'm worried that we might be relying on this trick elsewhere. The arm __bad_cmpxchg function, for example.

Will

--->8

include/linux/log2.h +2 -11
index fd7ff3d91e6a..9cf5ad69065d 100644
@@ -16,12 +16,6 @@
 #include <linux/bitops.h>
 
 /*
- * deal with unrepresentable constant logarithms
- */
-extern __attribute__((const, noreturn))
-int ____ilog2_NaN(void);
-
-/*
  * non-constant log of base 2 calculators
  * - the arch may override these in asm/bitops.h if they can be implemented
  *   more efficiently than using fls() and fls64()

@@ -85,7 +79,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 #define ilog2(n)                             \
 (                                            \
      __builtin_constant_p(n) ? (             \
-             (n) < 1 ? ____ilog2_NaN() :     \
+             (n) < 1 ? 0 :                   \
              (n) & (1ULL << 63) ? 63 :       \
              (n) & (1ULL << 62) ? 62 :       \
              (n) & (1ULL << 61) ? 61 :       \

@@ -149,9 +143,7 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
              (n) & (1ULL <<  3) ?  3 :       \
              (n) & (1ULL <<  2) ?  2 :       \
              (n) & (1ULL <<  1) ?  1 :       \
-             (n) & (1ULL <<  0) ?  0 :       \
-             ____ilog2_NaN()                 \
-                                ) :          \
+             0) :                            \
      (sizeof(n) <= 4) ?                      \
      __ilog2_u32(n) :                        \
      __ilog2_u64(n)                          \

@@ -194,7 +186,6 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  * @n: parameter
  *
  * The first few values calculated by this routine:
- *  ob2(0) = 0
  *  ob2(1) = 0
Quoted 9 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 191

Quoted 3 lines
include/linux/log2.h +0 -0
  *  ob2(2) = 1
  *  ob2(3) = 2

Reviving this thread as gcc 7 has now hit Fedora rawhide and has this same issue. I pulled in the above patch from Will as a temporary work around for building. It didn't look like there was consensus on a permanent solution though from the thread.

I still think order_base_2() is broken, since it may invoke roundup_pow_of_two() with an input value that is documented as producing undefined output. I would argue that the below is the correct fix.

include/linux/log2.h +13 -1
index fd7ff3d91e6a..46523731bec0 100644
@@ -203,6 +203,18 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
  *  ... and so on.
  */
 
-#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+static inline __attribute__((__const__))
+unsigned long __order_base_2(unsigned long n)
+{
+       return n ? 1UL << fls_long(n - 1) : 1;
+}
+
+#define order_base_2(n)                                \
+(                                              \
+       __builtin_constant_p(n) ? (             \
+               ((n) < 2) ? (n) :               \
+               ilog2((n) - 1) + 1) :           \
+       ilog2(__order_base_2(n))                \
+ )
Quoted 9 lines
Quoted 5 lines

include/linux/log2.h unsigned long __rounddown_pow_of_two(unsigned long n) · line 220

Quoted 2 lines
include/linux/log2.h +0 -0
 #endif /* _LINUX_LOG2_H */

This fixes the problem although the comments should be updated as well.

This brings order_base_2() in line with the comments, so I am not sure what you'd want to update here?

Quoted 6 lines

ob2(1) = 1 for the __builtin_constant_p case which doesn't match the comment of ob2(1) = 0. So my statement should actually be is this correct?

Thanks,
Laura

You are right. But the final one I proposed is correct:

#define order_base_2(n)                        \
(                                              \
       __builtin_constant_p(n) ? (             \
               ((n) == 0 || (n) == 1) ? 0 :    \
               ilog2((n) - 1) + 1) :           \
       __order_base_2(n)                       \

)

and solves Joe's issue as well.

I will submit this as a proper patch.

Thanks,
Ard.