* [PATCH] replace timeconst bc script with an sh script @ 2019-06-20 6:22 Ethan Sommer 2019-06-20 7:23 ` Kieran Bingham 2019-10-29 21:02 ` [PATCH v3] " Ethan Sommer 0 siblings, 2 replies; 14+ messages in thread From: Ethan Sommer @ 2019-06-20 6:22 UTC (permalink / raw) Cc: e5ten.arch, linux-kernel, Masahiro Yamada, Ingo Molnar, Kieran Bingham, Heiko Carstens, Borislav Petkov, Mark Rutland, Kees Cook, Thomas Gleixner, Corey Minyard, John Stultz removes the bc build dependency introduced when timeconst.pl was replaced by timeconst.bc Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com> --- Kbuild | 4 +- kernel/time/timeconst.bc | 117 -------------------------------------- kernel/time/timeconst.sh | 118 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 120 insertions(+), 119 deletions(-) delete mode 100644 kernel/time/timeconst.bc create mode 100755 kernel/time/timeconst.sh diff --git a/Kbuild b/Kbuild index 8637fd14135f..2b5f2957cf04 100644 --- a/Kbuild +++ b/Kbuild @@ -20,9 +20,9 @@ timeconst-file := include/generated/timeconst.h targets += $(timeconst-file) -filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $< +filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ) -$(timeconst-file): kernel/time/timeconst.bc FORCE +$(timeconst-file): kernel/time/timeconst.sh FORCE $(call filechk,gentimeconst) ##### diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc deleted file mode 100644 index 7ed0e0fb5831..000000000000 --- a/kernel/time/timeconst.bc +++ /dev/null @@ -1,117 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ - -scale=0 - -define gcd(a,b) { - auto t; - while (b) { - t = b; - b = a % b; - a = t; - } - return a; -} - -/* Division by reciprocal multiplication. */ -define fmul(b,n,d) { - return (2^b*n+d-1)/d; -} - -/* Adjustment factor when a ceiling value is used. Use as: - (imul * n) + (fmulxx * n + fadjxx) >> xx) */ -define fadj(b,n,d) { - auto v; - d = d/gcd(n,d); - v = 2^b*(d-1)/d; - return v; -} - -/* Compute the appropriate mul/adj values as well as a shift count, - which brings the mul value into the range 2^b-1 <= x < 2^b. Such - a shift value will be correct in the signed integer range and off - by at most one in the upper half of the unsigned range. */ -define fmuls(b,n,d) { - auto s, m; - for (s = 0; 1; s++) { - m = fmul(s,n,d); - if (m >= 2^(b-1)) - return s; - } - return 0; -} - -define timeconst(hz) { - print "/* Automatically generated by kernel/time/timeconst.bc */\n" - print "/* Time conversion constants for HZ == ", hz, " */\n" - print "\n" - - print "#ifndef KERNEL_TIMECONST_H\n" - print "#define KERNEL_TIMECONST_H\n\n" - - print "#include <linux/param.h>\n" - print "#include <linux/types.h>\n\n" - - print "#if HZ != ", hz, "\n" - print "#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n" - print "#endif\n\n" - - if (hz < 2) { - print "#error Totally bogus HZ value!\n" - } else { - s=fmuls(32,1000,hz) - obase=16 - print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n" - print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n" - obase=10 - print "#define HZ_TO_MSEC_SHR32\t", s, "\n" - - s=fmuls(32,hz,1000) - obase=16 - print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n" - print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n" - obase=10 - print "#define MSEC_TO_HZ_SHR32\t", s, "\n" - - obase=10 - cd=gcd(hz,1000) - print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n" - print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n" - print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n" - print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n" - print "\n" - - s=fmuls(32,1000000,hz) - obase=16 - print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), ")\n" - print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), ")\n" - obase=10 - print "#define HZ_TO_USEC_SHR32\t", s, "\n" - - s=fmuls(32,hz,1000000) - obase=16 - print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), ")\n" - print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), ")\n" - obase=10 - print "#define USEC_TO_HZ_SHR32\t", s, "\n" - - obase=10 - cd=gcd(hz,1000000) - print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n" - print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n" - print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n" - print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n" - - cd=gcd(hz,1000000000) - print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n" - print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n" - print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n" - print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n" - print "\n" - - print "#endif /* KERNEL_TIMECONST_H */\n" - } - halt -} - -hz = read(); -timeconst(hz) diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh new file mode 100755 index 000000000000..df821988acbf --- /dev/null +++ b/kernel/time/timeconst.sh @@ -0,0 +1,118 @@ +#!/bin/sh +# SPDX-License-Identifier: GPL-2.0 + +if [ -z "$1" ]; then + printf '%s <HZ>\n' "$0" + exit 1 +else + hz="$1" +fi + +# 2 to the power of n +pot() { + local i=1 + local j=1 + while [ "${j}" -le "$1" ]; do + i="$((i * 2))" + j="$((j + 1))" + done + printf '%s\n' "${i}" +} + +# Greatest common denominator +gcd() { + local i="$1" + local j="$2" + local k + while [ "${j}" -ne 0 ]; do + k="${j}" + j="$((i % j))" + i="${k}" + done + printf '%s\n' "${i}" +} + +# Division by reciprocal multiplication. +fmul() { + printf '%s\n' "$((($(pot "$1") * $2 + $3 - 1) / $3))" +} + +# Adjustment factor when a ceiling value is used. +fadj() { + local i="$(gcd "$2" "$3")" + printf '%s\n' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))" +} + +# Compute the appropriate mul/adj values as well as a shift count, +# which brings the mul value into the range 2^b-1 <= x < 2^b. Such +# a shift value will be correct in the signed integer range and off +# by at most one in the upper half of the unsigned range. +fmuls() { + local i=0 + local j + while true; do + j="$(fmul "${i}" "$2" "$3")" + if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then + printf '%s\n' "${i}" && return + fi + i="$((i + 1))" + done +} + +printf '/* Automatically generated by %s */\n' "$0" +printf '/* Time conversion constants for HZ == %s */\n\n' "$1" + +printf '#ifndef KERNEL_TIMECONST_H\n' +printf '#define KERNEL_TIMECONST_H\n\n' + +printf '#include <linux/param.h>\n' +printf '#include <linux/types.h>\n\n' + +printf '#if HZ != %s\n' "$1" +printf '#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n' +printf '#endif\n\n' + +if [ "$1" -lt 2 ]; then + printf '#error Totally bogus HZ value!\n' + exit 1 +fi + +s="$(fmuls 32 1000 "$1")" +printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 "$1")" +printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 "$1")" +printf '#define HZ_TO_MSEC_SHR32\t%s\n' "${s}" + +s="$(fmuls 32 "$1" 1000)" +printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000)" +printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000)" +printf '#define MSEC_TO_HZ_SHR32\t%s\n' "${s}" + +cd="$(gcd "$1" 1000)" +printf '#define HZ_TO_MSEC_NUM\t\t%s\n' "$((1000 / cd))" +printf '#define HZ_TO_MSEC_DEN\t\t%s\n' "$((hz / cd))" +printf '#define MSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))" +printf '#define MSEC_TO_HZ_DEN\t\t%s\n\n' "$((1000 / cd))" + +s="$(fmuls 32 1000000 "$1")" +printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000000 "$1")" +printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000000 "$1")" +printf '#define HZ_TO_USEC_SHR32\t%s\n' "${s}" + +s="$(fmuls 32 "$1" 1000000)" +printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000000)" +printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000000)" +printf '#define USEC_TO_HZ_SHR32\t%s\n' "${s}" + +cd="$(gcd "$1" 1000000)" +printf '#define HZ_TO_USEC_NUM\t\t%s\n' "$((1000000 / cd))" +printf '#define HZ_TO_USEC_DEN\t\t%s\n' "$((hz / cd))" +printf '#define USEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))" +printf '#define USEC_TO_HZ_DEN\t\t%s\n' "$((1000000 / cd))" + +cd="$(gcd "$1" 1000000000)" +printf '#define HZ_TO_NSEC_NUM\t\t%s\n' "$((1000000000 / cd))" +printf '#define HZ_TO_NSEC_DEN\t\t%s\n' "$((hz / cd))" +printf '#define NSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))" +printf '#define NSEC_TO_HZ_DEN\t\t%s\n' "$((1000000000 / cd))" + +printf '\n#endif /* KERNEL_TIMECONST_H */\n' -- 2.22.0 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH] replace timeconst bc script with an sh script 2019-06-20 6:22 [PATCH] replace timeconst bc script with an sh script Ethan Sommer @ 2019-06-20 7:23 ` Kieran Bingham 2019-06-20 8:11 ` [PATCH v2] " Ethan Sommer 2019-10-29 21:02 ` [PATCH v3] " Ethan Sommer 1 sibling, 1 reply; 14+ messages in thread From: Kieran Bingham @ 2019-06-20 7:23 UTC (permalink / raw) To: Ethan Sommer Cc: linux-kernel, Masahiro Yamada, Ingo Molnar, Heiko Carstens, Borislav Petkov, Mark Rutland, Kees Cook, Thomas Gleixner, Corey Minyard, John Stultz Hi Ethan, Thank you for the patch, On 20/06/2019 07:22, Ethan Sommer wrote: > removes the bc build dependency introduced when timeconst.pl was > replaced by timeconst.bc Does this introduction of bc cause you problems when building? Documentation/process/changes.rst states that "You will need bc to build kernels 3.10 and higher" Is bc used elsewhere in the kernel? If this is the only use of BC and it is no longer a dependency - the process document should be updated. Though I see uses at: tools/testing/selftests/net/forwarding/lib.sh There is a small issue with quotes highlighted below, and the only other (really minor) comment is performance. time (echo 1000 | bc -q ./kernel/time/timeconst.bc) real 0m0.006s user 0m0.006s sys 0m0.000s vs time /tmp/timeconst.sh 1000 real 0m0.176s user 0m0.141s sys 0m0.050s So that's 176 milliseconds vs 6. (on an i7 gen8 laptop) which probably isn't going to affect things too much on the scale of building a kernel. But I measured it so I thought it was worth posting the results. -- Regards Kieran > Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com> > --- > Kbuild | 4 +- > kernel/time/timeconst.bc | 117 -------------------------------------- > kernel/time/timeconst.sh | 118 +++++++++++++++++++++++++++++++++++++++ > 3 files changed, 120 insertions(+), 119 deletions(-) > delete mode 100644 kernel/time/timeconst.bc > create mode 100755 kernel/time/timeconst.sh > > diff --git a/Kbuild b/Kbuild > index 8637fd14135f..2b5f2957cf04 100644 > --- a/Kbuild > +++ b/Kbuild > @@ -20,9 +20,9 @@ timeconst-file := include/generated/timeconst.h > > targets += $(timeconst-file) > > -filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $< > +filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ) > > -$(timeconst-file): kernel/time/timeconst.bc FORCE > +$(timeconst-file): kernel/time/timeconst.sh FORCE > $(call filechk,gentimeconst) > > ##### > diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc > deleted file mode 100644 > index 7ed0e0fb5831..000000000000 > --- a/kernel/time/timeconst.bc > +++ /dev/null > @@ -1,117 +0,0 @@ > -/* SPDX-License-Identifier: GPL-2.0 */ > - > -scale=0 > - > -define gcd(a,b) { > - auto t; > - while (b) { > - t = b; > - b = a % b; > - a = t; > - } > - return a; > -} > - > -/* Division by reciprocal multiplication. */ > -define fmul(b,n,d) { > - return (2^b*n+d-1)/d; > -} > - > -/* Adjustment factor when a ceiling value is used. Use as: > - (imul * n) + (fmulxx * n + fadjxx) >> xx) */ > -define fadj(b,n,d) { > - auto v; > - d = d/gcd(n,d); > - v = 2^b*(d-1)/d; > - return v; > -} > - > -/* Compute the appropriate mul/adj values as well as a shift count, > - which brings the mul value into the range 2^b-1 <= x < 2^b. Such > - a shift value will be correct in the signed integer range and off > - by at most one in the upper half of the unsigned range. */ > -define fmuls(b,n,d) { > - auto s, m; > - for (s = 0; 1; s++) { > - m = fmul(s,n,d); > - if (m >= 2^(b-1)) > - return s; > - } > - return 0; > -} > - > -define timeconst(hz) { > - print "/* Automatically generated by kernel/time/timeconst.bc */\n" > - print "/* Time conversion constants for HZ == ", hz, " */\n" > - print "\n" > - > - print "#ifndef KERNEL_TIMECONST_H\n" > - print "#define KERNEL_TIMECONST_H\n\n" > - > - print "#include <linux/param.h>\n" > - print "#include <linux/types.h>\n\n" > - > - print "#if HZ != ", hz, "\n" > - print "#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n" > - print "#endif\n\n" > - > - if (hz < 2) { > - print "#error Totally bogus HZ value!\n" > - } else { > - s=fmuls(32,1000,hz) > - obase=16 > - print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n" > - print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n" > - obase=10 > - print "#define HZ_TO_MSEC_SHR32\t", s, "\n" > - > - s=fmuls(32,hz,1000) > - obase=16 > - print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n" > - print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n" > - obase=10 > - print "#define MSEC_TO_HZ_SHR32\t", s, "\n" > - > - obase=10 > - cd=gcd(hz,1000) > - print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n" > - print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n" > - print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n" > - print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n" > - print "\n" > - > - s=fmuls(32,1000000,hz) > - obase=16 > - print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), ")\n" > - print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), ")\n" > - obase=10 > - print "#define HZ_TO_USEC_SHR32\t", s, "\n" > - > - s=fmuls(32,hz,1000000) > - obase=16 > - print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), ")\n" > - print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), ")\n" > - obase=10 > - print "#define USEC_TO_HZ_SHR32\t", s, "\n" > - > - obase=10 > - cd=gcd(hz,1000000) > - print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n" > - print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n" > - print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n" > - print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n" > - > - cd=gcd(hz,1000000000) > - print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n" > - print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n" > - print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n" > - print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n" > - print "\n" > - > - print "#endif /* KERNEL_TIMECONST_H */\n" > - } > - halt > -} > - > -hz = read(); > -timeconst(hz) > diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh > new file mode 100755 > index 000000000000..df821988acbf > --- /dev/null > +++ b/kernel/time/timeconst.sh > @@ -0,0 +1,118 @@ > +#!/bin/sh > +# SPDX-License-Identifier: GPL-2.0 > + > +if [ -z "$1" ]; then > + printf '%s <HZ>\n' "$0" > + exit 1 > +else > + hz="$1" > +fi > + > +# 2 to the power of n > +pot() { > + local i=1 > + local j=1 > + while [ "${j}" -le "$1" ]; do > + i="$((i * 2))" > + j="$((j + 1))" > + done > + printf '%s\n' "${i}" > +} > + > +# Greatest common denominator > +gcd() { > + local i="$1" > + local j="$2" > + local k > + while [ "${j}" -ne 0 ]; do > + k="${j}" > + j="$((i % j))" > + i="${k}" > + done > + printf '%s\n' "${i}" > +} > + > +# Division by reciprocal multiplication. > +fmul() { > + printf '%s\n' "$((($(pot "$1") * $2 + $3 - 1) / $3))" > +} > + > +# Adjustment factor when a ceiling value is used. > +fadj() { > + local i="$(gcd "$2" "$3")" > + printf '%s\n' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))" > +} > + > +# Compute the appropriate mul/adj values as well as a shift count, > +# which brings the mul value into the range 2^b-1 <= x < 2^b. Such > +# a shift value will be correct in the signed integer range and off > +# by at most one in the upper half of the unsigned range. > +fmuls() { > + local i=0 > + local j > + while true; do > + j="$(fmul "${i}" "$2" "$3")" > + if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then > + printf '%s\n' "${i}" && return > + fi > + i="$((i + 1))" > + done > +} > + > +printf '/* Automatically generated by %s */\n' "$0" > +printf '/* Time conversion constants for HZ == %s */\n\n' "$1" > + > +printf '#ifndef KERNEL_TIMECONST_H\n' > +printf '#define KERNEL_TIMECONST_H\n\n' > + > +printf '#include <linux/param.h>\n' > +printf '#include <linux/types.h>\n\n' > + > +printf '#if HZ != %s\n' "$1" > +printf '#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n' This generates an incorrect output: diff /tmp/bc.timed /tmp/sh.timed 1c1 < /* Automatically generated by kernel/time/timeconst.bc */ --- > /* Automatically generated by /tmp/timeconst.sh */ 11c11 < #error "include/generated/timeconst.h has the wrong HZ value!" --- > #error \qinclude/generated/timeconst.h has the wrong HZ value!\q here ^ and here ^ > +printf '#endif\n\n' > + > +if [ "$1" -lt 2 ]; then > + printf '#error Totally bogus HZ value!\n' > + exit 1 > +fi > + > +s="$(fmuls 32 1000 "$1")" > +printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 "$1")" > +printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 "$1")" > +printf '#define HZ_TO_MSEC_SHR32\t%s\n' "${s}" > + > +s="$(fmuls 32 "$1" 1000)" > +printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000)" > +printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000)" > +printf '#define MSEC_TO_HZ_SHR32\t%s\n' "${s}" > + > +cd="$(gcd "$1" 1000)" > +printf '#define HZ_TO_MSEC_NUM\t\t%s\n' "$((1000 / cd))" > +printf '#define HZ_TO_MSEC_DEN\t\t%s\n' "$((hz / cd))" > +printf '#define MSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))" > +printf '#define MSEC_TO_HZ_DEN\t\t%s\n\n' "$((1000 / cd))" > + > +s="$(fmuls 32 1000000 "$1")" > +printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000000 "$1")" > +printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000000 "$1")" > +printf '#define HZ_TO_USEC_SHR32\t%s\n' "${s}" > + > +s="$(fmuls 32 "$1" 1000000)" > +printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000000)" > +printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000000)" > +printf '#define USEC_TO_HZ_SHR32\t%s\n' "${s}" > + > +cd="$(gcd "$1" 1000000)" > +printf '#define HZ_TO_USEC_NUM\t\t%s\n' "$((1000000 / cd))" > +printf '#define HZ_TO_USEC_DEN\t\t%s\n' "$((hz / cd))" > +printf '#define USEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))" > +printf '#define USEC_TO_HZ_DEN\t\t%s\n' "$((1000000 / cd))" > + > +cd="$(gcd "$1" 1000000000)" > +printf '#define HZ_TO_NSEC_NUM\t\t%s\n' "$((1000000000 / cd))" > +printf '#define HZ_TO_NSEC_DEN\t\t%s\n' "$((hz / cd))" > +printf '#define NSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))" > +printf '#define NSEC_TO_HZ_DEN\t\t%s\n' "$((1000000000 / cd))" > + > +printf '\n#endif /* KERNEL_TIMECONST_H */\n' > -- Regards -- Kieran ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH v2] replace timeconst bc script with an sh script 2019-06-20 7:23 ` Kieran Bingham @ 2019-06-20 8:11 ` Ethan Sommer 2019-06-20 8:25 ` Borislav Petkov 0 siblings, 1 reply; 14+ messages in thread From: Ethan Sommer @ 2019-06-20 8:11 UTC (permalink / raw) Cc: hpa, Ethan Sommer, Jonathan Corbet, Masahiro Yamada, Randy Dunlap, Nick Desaulniers, Kees Cook, Joe Perches, Federico Vaga, Ingo Molnar, Kieran Bingham, Peter Zijlstra (Intel), Borislav Petkov, Mark Rutland, John Stultz, Corey Minyard, Thomas Gleixner, linux-doc, linux-kernel removes the bc build dependency introduced when timeconst.pl was replaced by timeconst.bc: 70730bca1331 ("kernel: Replace timeconst.pl with a bc script") Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com> --- Documentation/process/changes.rst | 6 -- Kbuild | 4 +- kernel/time/timeconst.bc | 117 ----------------------------- kernel/time/timeconst.sh | 118 ++++++++++++++++++++++++++++++ 4 files changed, 120 insertions(+), 125 deletions(-) delete mode 100644 kernel/time/timeconst.bc create mode 100755 kernel/time/timeconst.sh diff --git a/Documentation/process/changes.rst b/Documentation/process/changes.rst index 18735dc460a0..14347f6752ea 100644 --- a/Documentation/process/changes.rst +++ b/Documentation/process/changes.rst @@ -108,12 +108,6 @@ Perl You will need perl 5 and the following modules: ``Getopt::Long``, ``Getopt::Std``, ``File::Basename``, and ``File::Find`` to build the kernel. -BC --- - -You will need bc to build kernels 3.10 and higher - - OpenSSL ------- diff --git a/Kbuild b/Kbuild index 8637fd14135f..2b5f2957cf04 100644 --- a/Kbuild +++ b/Kbuild @@ -20,9 +20,9 @@ timeconst-file := include/generated/timeconst.h targets += $(timeconst-file) -filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $< +filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ) -$(timeconst-file): kernel/time/timeconst.bc FORCE +$(timeconst-file): kernel/time/timeconst.sh FORCE $(call filechk,gentimeconst) ##### diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc deleted file mode 100644 index 7ed0e0fb5831..000000000000 --- a/kernel/time/timeconst.bc +++ /dev/null @@ -1,117 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ - -scale=0 - -define gcd(a,b) { - auto t; - while (b) { - t = b; - b = a % b; - a = t; - } - return a; -} - -/* Division by reciprocal multiplication. */ -define fmul(b,n,d) { - return (2^b*n+d-1)/d; -} - -/* Adjustment factor when a ceiling value is used. Use as: - (imul * n) + (fmulxx * n + fadjxx) >> xx) */ -define fadj(b,n,d) { - auto v; - d = d/gcd(n,d); - v = 2^b*(d-1)/d; - return v; -} - -/* Compute the appropriate mul/adj values as well as a shift count, - which brings the mul value into the range 2^b-1 <= x < 2^b. Such - a shift value will be correct in the signed integer range and off - by at most one in the upper half of the unsigned range. */ -define fmuls(b,n,d) { - auto s, m; - for (s = 0; 1; s++) { - m = fmul(s,n,d); - if (m >= 2^(b-1)) - return s; - } - return 0; -} - -define timeconst(hz) { - print "/* Automatically generated by kernel/time/timeconst.bc */\n" - print "/* Time conversion constants for HZ == ", hz, " */\n" - print "\n" - - print "#ifndef KERNEL_TIMECONST_H\n" - print "#define KERNEL_TIMECONST_H\n\n" - - print "#include <linux/param.h>\n" - print "#include <linux/types.h>\n\n" - - print "#if HZ != ", hz, "\n" - print "#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n" - print "#endif\n\n" - - if (hz < 2) { - print "#error Totally bogus HZ value!\n" - } else { - s=fmuls(32,1000,hz) - obase=16 - print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n" - print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n" - obase=10 - print "#define HZ_TO_MSEC_SHR32\t", s, "\n" - - s=fmuls(32,hz,1000) - obase=16 - print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n" - print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n" - obase=10 - print "#define MSEC_TO_HZ_SHR32\t", s, "\n" - - obase=10 - cd=gcd(hz,1000) - print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n" - print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n" - print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n" - print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n" - print "\n" - - s=fmuls(32,1000000,hz) - obase=16 - print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), ")\n" - print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), ")\n" - obase=10 - print "#define HZ_TO_USEC_SHR32\t", s, "\n" - - s=fmuls(32,hz,1000000) - obase=16 - print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), ")\n" - print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), ")\n" - obase=10 - print "#define USEC_TO_HZ_SHR32\t", s, "\n" - - obase=10 - cd=gcd(hz,1000000) - print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n" - print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n" - print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n" - print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n" - - cd=gcd(hz,1000000000) - print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n" - print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n" - print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n" - print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n" - print "\n" - - print "#endif /* KERNEL_TIMECONST_H */\n" - } - halt -} - -hz = read(); -timeconst(hz) diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh new file mode 100755 index 000000000000..20dd24815ae1 --- /dev/null +++ b/kernel/time/timeconst.sh @@ -0,0 +1,118 @@ +#!/bin/sh +# SPDX-License-Identifier: GPL-2.0 + +if [ -z "$1" ]; then + printf '%s <HZ>\n' "$0" + exit 1 +else + hz="$1" +fi + +# 2 to the power of n +pot() { + local i=1 + local j=1 + while [ "${j}" -le "$1" ]; do + i="$((i * 2))" + j="$((j + 1))" + done + printf '%s\n' "${i}" +} + +# Greatest common denominator +gcd() { + local i="$1" + local j="$2" + local k + while [ "${j}" -ne 0 ]; do + k="${j}" + j="$((i % j))" + i="${k}" + done + printf '%s\n' "${i}" +} + +# Division by reciprocal multiplication. +fmul() { + printf '%s\n' "$((($(pot "$1") * $2 + $3 - 1) / $3))" +} + +# Adjustment factor when a ceiling value is used. +fadj() { + local i="$(gcd "$2" "$3")" + printf '%s\n' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))" +} + +# Compute the appropriate mul/adj values as well as a shift count, +# which brings the mul value into the range 2^b-1 <= x < 2^b. Such +# a shift value will be correct in the signed integer range and off +# by at most one in the upper half of the unsigned range. +fmuls() { + local i=0 + local j + while true; do + j="$(fmul "${i}" "$2" "$3")" + if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then + printf '%s\n' "${i}" && return + fi + i="$((i + 1))" + done +} + +printf '/* Automatically generated by kernel/time/timeconst.sh */\n' +printf '/* Time conversion constants for HZ == %s */\n\n' "$1" + +printf '#ifndef KERNEL_TIMECONST_H\n' +printf '#define KERNEL_TIMECONST_H\n\n' + +printf '#include <linux/param.h>\n' +printf '#include <linux/types.h>\n\n' + +printf '#if HZ != %s\n' "$1" +printf '#error "include/generated/timeconst.h has the wrong HZ value!"\n' +printf '#endif\n\n' + +if [ "$1" -lt 2 ]; then + printf '#error Totally bogus HZ value!\n' + exit 1 +fi + +s="$(fmuls 32 1000 "$1")" +printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 "$1")" +printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 "$1")" +printf '#define HZ_TO_MSEC_SHR32\t%s\n' "${s}" + +s="$(fmuls 32 "$1" 1000)" +printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000)" +printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000)" +printf '#define MSEC_TO_HZ_SHR32\t%s\n' "${s}" + +cd="$(gcd "$1" 1000)" +printf '#define HZ_TO_MSEC_NUM\t\t%s\n' "$((1000 / cd))" +printf '#define HZ_TO_MSEC_DEN\t\t%s\n' "$((hz / cd))" +printf '#define MSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))" +printf '#define MSEC_TO_HZ_DEN\t\t%s\n\n' "$((1000 / cd))" + +s="$(fmuls 32 1000000 "$1")" +printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000000 "$1")" +printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000000 "$1")" +printf '#define HZ_TO_USEC_SHR32\t%s\n' "${s}" + +s="$(fmuls 32 "$1" 1000000)" +printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000000)" +printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000000)" +printf '#define USEC_TO_HZ_SHR32\t%s\n' "${s}" + +cd="$(gcd "$1" 1000000)" +printf '#define HZ_TO_USEC_NUM\t\t%s\n' "$((1000000 / cd))" +printf '#define HZ_TO_USEC_DEN\t\t%s\n' "$((hz / cd))" +printf '#define USEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))" +printf '#define USEC_TO_HZ_DEN\t\t%s\n' "$((1000000 / cd))" + +cd="$(gcd "$1" 1000000000)" +printf '#define HZ_TO_NSEC_NUM\t\t%s\n' "$((1000000000 / cd))" +printf '#define HZ_TO_NSEC_DEN\t\t%s\n' "$((hz / cd))" +printf '#define NSEC_TO_HZ_NUM\t\t%s\n' "$((hz / cd))" +printf '#define NSEC_TO_HZ_DEN\t\t%s\n' "$((1000000000 / cd))" + +printf '\n#endif /* KERNEL_TIMECONST_H */\n' -- 2.22.0 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH v2] replace timeconst bc script with an sh script 2019-06-20 8:11 ` [PATCH v2] " Ethan Sommer @ 2019-06-20 8:25 ` Borislav Petkov 2019-06-20 8:43 ` Ethan Sommer [not found] ` <CAMEGPiqk5TU=z2_wvMfPuihVc5zOLRrTSVCpLA23k0r-hmAzmg@mail.gmail.com> 0 siblings, 2 replies; 14+ messages in thread From: Borislav Petkov @ 2019-06-20 8:25 UTC (permalink / raw) To: Ethan Sommer Cc: hpa, Jonathan Corbet, Masahiro Yamada, Randy Dunlap, Nick Desaulniers, Kees Cook, Joe Perches, Federico Vaga, Ingo Molnar, Kieran Bingham, Peter Zijlstra (Intel), Mark Rutland, John Stultz, Corey Minyard, Thomas Gleixner, linux-doc, linux-kernel On Thu, Jun 20, 2019 at 04:11:32AM -0400, Ethan Sommer wrote: > removes the bc build dependency introduced when timeconst.pl was > replaced by timeconst.bc: > 70730bca1331 ("kernel: Replace timeconst.pl with a bc script") I don't see you answering Kieran's questions anywhere... -- Regards/Gruss, Boris. SUSE Linux GmbH, GF: Felix Imendörffer, Mary Higgins, Sri Rasiah, HRB 21284 (AG Nürnberg) ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH v2] replace timeconst bc script with an sh script 2019-06-20 8:25 ` Borislav Petkov @ 2019-06-20 8:43 ` Ethan Sommer [not found] ` <CAMEGPiqk5TU=z2_wvMfPuihVc5zOLRrTSVCpLA23k0r-hmAzmg@mail.gmail.com> 1 sibling, 0 replies; 14+ messages in thread From: Ethan Sommer @ 2019-06-20 8:43 UTC (permalink / raw) To: Borislav Petkov Cc: hpa, Jonathan Corbet, Masahiro Yamada, Randy Dunlap, Nick Desaulniers, Kees Cook, Joe Perches, Federico Vaga, Ingo Molnar, Kieran Bingham, Peter Zijlstra (Intel), Mark Rutland, John Stultz, Corey Minyard, Thomas Gleixner, linux-doc, linux-kernel (resend because I didn't know gmail would make it html) Ah sorry about that, I accidentally replied to Kieran only instead of to all, my response was "I will upload a patch with those issues fixed shortly, in terms of the dependency as far as I know commands only required for running tests don't count as kernel compilation dependencies, and I don't see any other uses of bc except for Documentation/EDID/Makefile, so I believe that bc can be removed from the kernel compilation section of the process document and will include that change with the updated patch that fixes the 2 issues you pointed out." On Thu, Jun 20, 2019 at 4:26 AM Borislav Petkov <bp@suse.de> wrote: > > On Thu, Jun 20, 2019 at 04:11:32AM -0400, Ethan Sommer wrote: > > removes the bc build dependency introduced when timeconst.pl was > > replaced by timeconst.bc: > > 70730bca1331 ("kernel: Replace timeconst.pl with a bc script") > > I don't see you answering Kieran's questions anywhere... > > -- > Regards/Gruss, > Boris. > > SUSE Linux GmbH, GF: Felix Imendörffer, Mary Higgins, Sri Rasiah, HRB 21284 (AG Nürnberg) ^ permalink raw reply [flat|nested] 14+ messages in thread
[parent not found: <CAMEGPiqk5TU=z2_wvMfPuihVc5zOLRrTSVCpLA23k0r-hmAzmg@mail.gmail.com>]
* Re: [PATCH v2] replace timeconst bc script with an sh script [not found] ` <CAMEGPiqk5TU=z2_wvMfPuihVc5zOLRrTSVCpLA23k0r-hmAzmg@mail.gmail.com> @ 2019-06-20 8:45 ` Borislav Petkov 0 siblings, 0 replies; 14+ messages in thread From: Borislav Petkov @ 2019-06-20 8:45 UTC (permalink / raw) To: Ethan Sommer Cc: hpa, Jonathan Corbet, Masahiro Yamada, Randy Dunlap, Nick Desaulniers, Kees Cook, Joe Perches, Federico Vaga, Ingo Molnar, Kieran Bingham, Peter Zijlstra (Intel), Mark Rutland, John Stultz, Corey Minyard, Thomas Gleixner, linux-doc, linux-kernel On Thu, Jun 20, 2019 at 04:29:19AM -0400, Ethan Sommer wrote: > Ah sorry about that, I accidentally replied to Kieran only instead of to > all, my response was "I will upload a patch with those issues fixed > shortly, in terms of the dependency as far as I know commands only required > for running tests don't count as kernel compilation dependencies, and I > don't see any other uses of bc except for Documentation/EDID/Makefile, so I > believe that bc can be removed from the kernel compilation section of the > process document and will include that change with the updated patch that > fixes the 2 issues you pointed out." Sounds like parts of it should be in your commit message as a justification *why* you're doing it. You can do that for your next revision once you've waited a couple of days to gather feedback. Also, please do not top-post. Thx. -- Regards/Gruss, Boris. SUSE Linux GmbH, GF: Felix Imendörffer, Mary Higgins, Sri Rasiah, HRB 21284 (AG Nürnberg) ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH v3] replace timeconst bc script with an sh script 2019-06-20 6:22 [PATCH] replace timeconst bc script with an sh script Ethan Sommer 2019-06-20 7:23 ` Kieran Bingham @ 2019-10-29 21:02 ` Ethan Sommer 2019-10-30 11:37 ` Kieran Bingham 2019-11-02 20:54 ` hpa 1 sibling, 2 replies; 14+ messages in thread From: Ethan Sommer @ 2019-10-29 21:02 UTC (permalink / raw) Cc: H . Peter Anvin, Ethan Sommer, Jonathan Corbet, Federico Vaga, Chang S. Bae, Andrew Morton, Arnd Bergmann, Masahiro Yamada, Kieran Bingham, Ingo Molnar, Borislav Petkov, Mark Rutland, John Stultz, Kees Cook, Corey Minyard, Thomas Gleixner, linux-doc, linux-kernel removes the bc build dependency introduced when timeconst.pl was replaced by timeconst.bc: commit 70730bca1331 ("kernel: Replace timeconst.pl with a bc script") the reason for this change is that this is the only use of bc in the actual compilation of the kernel, so by replacing it with a shell script compiling the kernel no longer depends on bc. Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com> --- Documentation/process/changes.rst | 6 -- Kbuild | 4 +- kernel/time/timeconst.bc | 117 ------------------------------ kernel/time/timeconst.sh | 111 ++++++++++++++++++++++++++++ 4 files changed, 113 insertions(+), 125 deletions(-) delete mode 100644 kernel/time/timeconst.bc create mode 100644 kernel/time/timeconst.sh diff --git a/Documentation/process/changes.rst b/Documentation/process/changes.rst index 2284f2221f02..3ae168387109 100644 --- a/Documentation/process/changes.rst +++ b/Documentation/process/changes.rst @@ -105,12 +105,6 @@ Perl You will need perl 5 and the following modules: ``Getopt::Long``, ``Getopt::Std``, ``File::Basename``, and ``File::Find`` to build the kernel. -BC --- - -You will need bc to build kernels 3.10 and higher - - OpenSSL ------- diff --git a/Kbuild b/Kbuild index 3109ac786e76..7eba24cbdb78 100644 --- a/Kbuild +++ b/Kbuild @@ -18,9 +18,9 @@ $(bounds-file): kernel/bounds.s FORCE timeconst-file := include/generated/timeconst.h -filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $< +filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ) -$(timeconst-file): kernel/time/timeconst.bc FORCE +$(timeconst-file): kernel/time/timeconst.sh FORCE $(call filechk,gentimeconst) ##### diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc deleted file mode 100644 index 7ed0e0fb5831..000000000000 --- a/kernel/time/timeconst.bc +++ /dev/null @@ -1,117 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ - -scale=0 - -define gcd(a,b) { - auto t; - while (b) { - t = b; - b = a % b; - a = t; - } - return a; -} - -/* Division by reciprocal multiplication. */ -define fmul(b,n,d) { - return (2^b*n+d-1)/d; -} - -/* Adjustment factor when a ceiling value is used. Use as: - (imul * n) + (fmulxx * n + fadjxx) >> xx) */ -define fadj(b,n,d) { - auto v; - d = d/gcd(n,d); - v = 2^b*(d-1)/d; - return v; -} - -/* Compute the appropriate mul/adj values as well as a shift count, - which brings the mul value into the range 2^b-1 <= x < 2^b. Such - a shift value will be correct in the signed integer range and off - by at most one in the upper half of the unsigned range. */ -define fmuls(b,n,d) { - auto s, m; - for (s = 0; 1; s++) { - m = fmul(s,n,d); - if (m >= 2^(b-1)) - return s; - } - return 0; -} - -define timeconst(hz) { - print "/* Automatically generated by kernel/time/timeconst.bc */\n" - print "/* Time conversion constants for HZ == ", hz, " */\n" - print "\n" - - print "#ifndef KERNEL_TIMECONST_H\n" - print "#define KERNEL_TIMECONST_H\n\n" - - print "#include <linux/param.h>\n" - print "#include <linux/types.h>\n\n" - - print "#if HZ != ", hz, "\n" - print "#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n" - print "#endif\n\n" - - if (hz < 2) { - print "#error Totally bogus HZ value!\n" - } else { - s=fmuls(32,1000,hz) - obase=16 - print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n" - print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n" - obase=10 - print "#define HZ_TO_MSEC_SHR32\t", s, "\n" - - s=fmuls(32,hz,1000) - obase=16 - print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n" - print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n" - obase=10 - print "#define MSEC_TO_HZ_SHR32\t", s, "\n" - - obase=10 - cd=gcd(hz,1000) - print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n" - print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n" - print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n" - print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n" - print "\n" - - s=fmuls(32,1000000,hz) - obase=16 - print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), ")\n" - print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), ")\n" - obase=10 - print "#define HZ_TO_USEC_SHR32\t", s, "\n" - - s=fmuls(32,hz,1000000) - obase=16 - print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), ")\n" - print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), ")\n" - obase=10 - print "#define USEC_TO_HZ_SHR32\t", s, "\n" - - obase=10 - cd=gcd(hz,1000000) - print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n" - print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n" - print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n" - print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n" - - cd=gcd(hz,1000000000) - print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n" - print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n" - print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n" - print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n" - print "\n" - - print "#endif /* KERNEL_TIMECONST_H */\n" - } - halt -} - -hz = read(); -timeconst(hz) diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh new file mode 100644 index 000000000000..d1aa25f46be8 --- /dev/null +++ b/kernel/time/timeconst.sh @@ -0,0 +1,111 @@ +#!/bin/sh +# SPDX-License-Identifier: GPL-2.0 + +if [ -z "$1" ]; then + printf '%s <HZ>\n' "$0" >&2 + exit 1 +fi + +# 2 to the power of n +pot() { + local i=1 j=0 + while [ "$((j += 1))" -le "$1" ]; do + : "$((i *= 2))" + done + printf '%u' "${i}" +} + +# Greatest common denominator +gcd() { + local i="$1" j="$2" k + while [ "${j}" -ne 0 ]; do + k="${j}" j="$((i % j))" i="${k}" + done + printf '%u' "${i}" +} + +# Division by reciprocal multiplication. +fmul() { + printf '%u' "$((($(pot "$1") * $2 + $3 - 1) / $3))" +} + +# Adjustment factor when a ceiling value is used. +fadj() { + local i + i="$(gcd "$2" "$3")" + printf '%u' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))" +} + +# Compute the appropriate mul/adj values as well as a shift count, +# which brings the mul value into the range 2^b-1 <= x < 2^b. Such +# a shift value will be correct in the signed integer range and off +# by at most one in the upper half of the unsigned range. +fmuls() { + local i=0 j + while true; do + j="$(fmul "${i}" "$2" "$3")" + if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then + printf '%u' "${i}" + return + fi + : "$((i += 1))" + done +} + +printf '/* Automatically generated by kernel/time/timeconst.sh */\n' +printf '/* Time conversion constants for HZ == %u */\n\n' "$1" + +printf '#ifndef KERNEL_TIMECONST_H\n' +printf '#define KERNEL_TIMECONST_H\n\n' + +printf '#include <linux/param.h>\n' +printf '#include <linux/types.h>\n\n' + +printf '#if HZ != %u\n' "$1" +printf '#error "include/generated/timeconst.h has the wrong HZ value!"\n' +printf '#endif\n\n' + +if [ "$1" -lt 2 ]; then + printf '#error Totally bogus HZ value!\n' + exit 1 +fi + +s="$(fmuls 32 1000 "$1")" +printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 "$1")" +printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 "$1")" +printf '#define HZ_TO_MSEC_SHR32\t%u\n' "${s}" + +s="$(fmuls 32 "$1" 1000)" +printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000)" +printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000)" +printf '#define MSEC_TO_HZ_SHR32\t%u\n' "${s}" + +cd="$(gcd "$1" 1000)" +printf '#define HZ_TO_MSEC_NUM\t\t%u\n' "$((1000 / cd))" +printf '#define HZ_TO_MSEC_DEN\t\t%u\n' "$(($1 / cd))" +printf '#define MSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))" +printf '#define MSEC_TO_HZ_DEN\t\t%u\n\n' "$((1000 / cd))" + +s="$(fmuls 32 1000000 "$1")" +printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000000 "$1")" +printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000000 "$1")" +printf '#define HZ_TO_USEC_SHR32\t%u\n' "${s}" + +s="$(fmuls 32 "$1" 1000000)" +printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000000)" +printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000000)" +printf '#define USEC_TO_HZ_SHR32\t%u\n' "${s}" + +cd="$(gcd "$1" 1000000)" +printf '#define HZ_TO_USEC_NUM\t\t%u\n' "$((1000000 / cd))" +printf '#define HZ_TO_USEC_DEN\t\t%u\n' "$(($1 / cd))" +printf '#define USEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))" +printf '#define USEC_TO_HZ_DEN\t\t%u\n' "$((1000000 / cd))" + +cd="$(gcd "$1" 1000000000)" +printf '#define HZ_TO_NSEC_NUM\t\t%u\n' "$((1000000000 / cd))" +printf '#define HZ_TO_NSEC_DEN\t\t%u\n' "$(($1 / cd))" +printf '#define NSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))" +printf '#define NSEC_TO_HZ_DEN\t\t%u\n' "$((1000000000 / cd))" + +printf '\n#endif /* KERNEL_TIMECONST_H */\n' -- 2.23.0 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH v3] replace timeconst bc script with an sh script 2019-10-29 21:02 ` [PATCH v3] " Ethan Sommer @ 2019-10-30 11:37 ` Kieran Bingham 2019-10-30 16:26 ` Ethan Sommer 2019-11-02 20:54 ` hpa 1 sibling, 1 reply; 14+ messages in thread From: Kieran Bingham @ 2019-10-30 11:37 UTC (permalink / raw) To: Ethan Sommer, H . Peter Anvin Cc: Jonathan Corbet, Federico Vaga, Chang S. Bae, Andrew Morton, Arnd Bergmann, Masahiro Yamada, Ingo Molnar, Borislav Petkov, Mark Rutland, John Stultz, Kees Cook, Corey Minyard, Thomas Gleixner, linux-doc, linux-kernel, Linux-Renesas Hi Ethan, On 29/10/2019 21:02, Ethan Sommer wrote: > removes the bc build dependency introduced when timeconst.pl was > replaced by timeconst.bc: > commit 70730bca1331 ("kernel: Replace timeconst.pl with a bc script") > > the reason for this change is that this is the only use of bc in the > actual compilation of the kernel, so by replacing it with a shell script > compiling the kernel no longer depends on bc. > > Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com> > --- > Documentation/process/changes.rst | 6 -- > Kbuild | 4 +- > kernel/time/timeconst.bc | 117 ------------------------------ > kernel/time/timeconst.sh | 111 ++++++++++++++++++++++++++++ Running shellcheck on kernel/time/timeconst.sh produces the following warnings: shellcheck kernel/time/timeconst.sh In kernel/time/timeconst.sh line 11: local i=1 j=0 ^-- SC2039: In POSIX sh, 'local' is undefined. In kernel/time/timeconst.sh line 20: local i="$1" j="$2" k ^-- SC2039: In POSIX sh, 'local' is undefined. In kernel/time/timeconst.sh line 34: local i ^-- SC2039: In POSIX sh, 'local' is undefined. In kernel/time/timeconst.sh line 44: local i=0 j ^-- SC2039: In POSIX sh, 'local' is undefined. Will this cause an issue for people running posix shells? Which shells have you tested your script on ? Furthermore, I fear this conversion may not be suitable at present, as it produces potentially different results for CONFIG_HZ < 100 (There may be more diffs, but I haven't yet compared a larger search space) using a quick script I put together to compare the output of timeconst.sh and timeconst.bc for a given CONFIG_HZ: https://gist.github.com/kbingham/76e8718df7b7dc97361405cc1801a160 $ for i in `seq 0 300`; do ./check-timeconst.sh $i; done produces a diff on almost every value 2 - 243 http://paste.ubuntu.com/p/wNggrfFZXB/ Or rather 137 faults to be exact: for i in `seq 0 250`; \ do ./check-timeconst.sh $i; \ done | grep -- "--- BC" | wc -l I think that might be considered a blocker to this implementation, or those values and the impact should certainly be investigated thoroughly. I haven't looked into detail into the change of any of those values, so I can not ascertain which one is more correct (though I suspect it's likely to be bc that will have the 'more correct' value) I would fear doing this in shell just isn't going to maintain the correct precision, which is likely a strong reason why bc was selected in the first place. If you can find the issue that causes this diff in your shell processing, and clarify or fix it - then it might be possible to gain some backing to the implementation, but even then it might become a shell specific precision issue ... -- Regards Kieran > 4 files changed, 113 insertions(+), 125 deletions(-) > delete mode 100644 kernel/time/timeconst.bc > create mode 100644 kernel/time/timeconst.sh > > diff --git a/Documentation/process/changes.rst b/Documentation/process/changes.rst > index 2284f2221f02..3ae168387109 100644 > --- a/Documentation/process/changes.rst > +++ b/Documentation/process/changes.rst > @@ -105,12 +105,6 @@ Perl > You will need perl 5 and the following modules: ``Getopt::Long``, > ``Getopt::Std``, ``File::Basename``, and ``File::Find`` to build the kernel. > > -BC > --- > - > -You will need bc to build kernels 3.10 and higher > - > - > OpenSSL > ------- > > diff --git a/Kbuild b/Kbuild > index 3109ac786e76..7eba24cbdb78 100644 > --- a/Kbuild > +++ b/Kbuild > @@ -18,9 +18,9 @@ $(bounds-file): kernel/bounds.s FORCE > > timeconst-file := include/generated/timeconst.h > > -filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $< > +filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ) > > -$(timeconst-file): kernel/time/timeconst.bc FORCE > +$(timeconst-file): kernel/time/timeconst.sh FORCE > $(call filechk,gentimeconst) > > ##### > diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc > deleted file mode 100644 > index 7ed0e0fb5831..000000000000 > --- a/kernel/time/timeconst.bc > +++ /dev/null > @@ -1,117 +0,0 @@ > -/* SPDX-License-Identifier: GPL-2.0 */ > - > -scale=0 > - > -define gcd(a,b) { > - auto t; > - while (b) { > - t = b; > - b = a % b; > - a = t; > - } > - return a; > -} > - > -/* Division by reciprocal multiplication. */ > -define fmul(b,n,d) { > - return (2^b*n+d-1)/d; > -} > - > -/* Adjustment factor when a ceiling value is used. Use as: > - (imul * n) + (fmulxx * n + fadjxx) >> xx) */ > -define fadj(b,n,d) { > - auto v; > - d = d/gcd(n,d); > - v = 2^b*(d-1)/d; > - return v; > -} > - > -/* Compute the appropriate mul/adj values as well as a shift count, > - which brings the mul value into the range 2^b-1 <= x < 2^b. Such > - a shift value will be correct in the signed integer range and off > - by at most one in the upper half of the unsigned range. */ > -define fmuls(b,n,d) { > - auto s, m; > - for (s = 0; 1; s++) { > - m = fmul(s,n,d); > - if (m >= 2^(b-1)) > - return s; > - } > - return 0; > -} > - > -define timeconst(hz) { > - print "/* Automatically generated by kernel/time/timeconst.bc */\n" > - print "/* Time conversion constants for HZ == ", hz, " */\n" > - print "\n" > - > - print "#ifndef KERNEL_TIMECONST_H\n" > - print "#define KERNEL_TIMECONST_H\n\n" > - > - print "#include <linux/param.h>\n" > - print "#include <linux/types.h>\n\n" > - > - print "#if HZ != ", hz, "\n" > - print "#error \qinclude/generated/timeconst.h has the wrong HZ value!\q\n" > - print "#endif\n\n" > - > - if (hz < 2) { > - print "#error Totally bogus HZ value!\n" > - } else { > - s=fmuls(32,1000,hz) > - obase=16 > - print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n" > - print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n" > - obase=10 > - print "#define HZ_TO_MSEC_SHR32\t", s, "\n" > - > - s=fmuls(32,hz,1000) > - obase=16 > - print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n" > - print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n" > - obase=10 > - print "#define MSEC_TO_HZ_SHR32\t", s, "\n" > - > - obase=10 > - cd=gcd(hz,1000) > - print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n" > - print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n" > - print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n" > - print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n" > - print "\n" > - > - s=fmuls(32,1000000,hz) > - obase=16 > - print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), ")\n" > - print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), ")\n" > - obase=10 > - print "#define HZ_TO_USEC_SHR32\t", s, "\n" > - > - s=fmuls(32,hz,1000000) > - obase=16 > - print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), ")\n" > - print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), ")\n" > - obase=10 > - print "#define USEC_TO_HZ_SHR32\t", s, "\n" > - > - obase=10 > - cd=gcd(hz,1000000) > - print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n" > - print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n" > - print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n" > - print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n" > - > - cd=gcd(hz,1000000000) > - print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n" > - print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n" > - print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n" > - print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n" > - print "\n" > - > - print "#endif /* KERNEL_TIMECONST_H */\n" > - } > - halt > -} > - > -hz = read(); > -timeconst(hz) > diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh > new file mode 100644 > index 000000000000..d1aa25f46be8 > --- /dev/null > +++ b/kernel/time/timeconst.sh > @@ -0,0 +1,111 @@ > +#!/bin/sh > +# SPDX-License-Identifier: GPL-2.0 > + > +if [ -z "$1" ]; then > + printf '%s <HZ>\n' "$0" >&2 > + exit 1 > +fi > + > +# 2 to the power of n > +pot() { > + local i=1 j=0 > + while [ "$((j += 1))" -le "$1" ]; do > + : "$((i *= 2))" > + done > + printf '%u' "${i}" > +} > + > +# Greatest common denominator > +gcd() { > + local i="$1" j="$2" k > + while [ "${j}" -ne 0 ]; do > + k="${j}" j="$((i % j))" i="${k}" > + done > + printf '%u' "${i}" > +} > + > +# Division by reciprocal multiplication. > +fmul() { > + printf '%u' "$((($(pot "$1") * $2 + $3 - 1) / $3))" > +} > + > +# Adjustment factor when a ceiling value is used. > +fadj() { > + local i > + i="$(gcd "$2" "$3")" > + printf '%u' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))" > +} > + > +# Compute the appropriate mul/adj values as well as a shift count, > +# which brings the mul value into the range 2^b-1 <= x < 2^b. Such > +# a shift value will be correct in the signed integer range and off > +# by at most one in the upper half of the unsigned range. > +fmuls() { > + local i=0 j > + while true; do > + j="$(fmul "${i}" "$2" "$3")" > + if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then > + printf '%u' "${i}" > + return > + fi > + : "$((i += 1))" > + done > +} > + > +printf '/* Automatically generated by kernel/time/timeconst.sh */\n' > +printf '/* Time conversion constants for HZ == %u */\n\n' "$1" > + > +printf '#ifndef KERNEL_TIMECONST_H\n' > +printf '#define KERNEL_TIMECONST_H\n\n' > + > +printf '#include <linux/param.h>\n' > +printf '#include <linux/types.h>\n\n' > + > +printf '#if HZ != %u\n' "$1" > +printf '#error "include/generated/timeconst.h has the wrong HZ value!"\n' > +printf '#endif\n\n' > + > +if [ "$1" -lt 2 ]; then > + printf '#error Totally bogus HZ value!\n' > + exit 1 > +fi > + > +s="$(fmuls 32 1000 "$1")" > +printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 "$1")" > +printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 "$1")" > +printf '#define HZ_TO_MSEC_SHR32\t%u\n' "${s}" > + > +s="$(fmuls 32 "$1" 1000)" > +printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000)" > +printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000)" > +printf '#define MSEC_TO_HZ_SHR32\t%u\n' "${s}" > + > +cd="$(gcd "$1" 1000)" > +printf '#define HZ_TO_MSEC_NUM\t\t%u\n' "$((1000 / cd))" > +printf '#define HZ_TO_MSEC_DEN\t\t%u\n' "$(($1 / cd))" > +printf '#define MSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))" > +printf '#define MSEC_TO_HZ_DEN\t\t%u\n\n' "$((1000 / cd))" > + > +s="$(fmuls 32 1000000 "$1")" > +printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000000 "$1")" > +printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000000 "$1")" > +printf '#define HZ_TO_USEC_SHR32\t%u\n' "${s}" > + > +s="$(fmuls 32 "$1" 1000000)" > +printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" 1000000)" > +printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" 1000000)" > +printf '#define USEC_TO_HZ_SHR32\t%u\n' "${s}" > + > +cd="$(gcd "$1" 1000000)" > +printf '#define HZ_TO_USEC_NUM\t\t%u\n' "$((1000000 / cd))" > +printf '#define HZ_TO_USEC_DEN\t\t%u\n' "$(($1 / cd))" > +printf '#define USEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))" > +printf '#define USEC_TO_HZ_DEN\t\t%u\n' "$((1000000 / cd))" > + > +cd="$(gcd "$1" 1000000000)" > +printf '#define HZ_TO_NSEC_NUM\t\t%u\n' "$((1000000000 / cd))" > +printf '#define HZ_TO_NSEC_DEN\t\t%u\n' "$(($1 / cd))" > +printf '#define NSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))" > +printf '#define NSEC_TO_HZ_DEN\t\t%u\n' "$((1000000000 / cd))" > + > +printf '\n#endif /* KERNEL_TIMECONST_H */\n' > -- Regards -- Kieran ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH v3] replace timeconst bc script with an sh script 2019-10-30 11:37 ` Kieran Bingham @ 2019-10-30 16:26 ` Ethan Sommer 0 siblings, 0 replies; 14+ messages in thread From: Ethan Sommer @ 2019-10-30 16:26 UTC (permalink / raw) To: Kieran Bingham Cc: H . Peter Anvin, Jonathan Corbet, Federico Vaga, Chang S. Bae, Andrew Morton, Arnd Bergmann, Masahiro Yamada, Ingo Molnar, Borislav Petkov, Mark Rutland, John Stultz, Kees Cook, Corey Minyard, Thomas Gleixner, linux-doc, Linux Kernel Mailing List, Linux-Renesas > Running shellcheck on kernel/time/timeconst.sh produces the following > warnings: > > shellcheck kernel/time/timeconst.sh > > In kernel/time/timeconst.sh line 11: > local i=1 j=0 > ^-- SC2039: In POSIX sh, 'local' is undefined. > > > In kernel/time/timeconst.sh line 20: > local i="$1" j="$2" k > ^-- SC2039: In POSIX sh, 'local' is undefined. > > > In kernel/time/timeconst.sh line 34: > local i > ^-- SC2039: In POSIX sh, 'local' is undefined. > > > In kernel/time/timeconst.sh line 44: > local i=0 j > ^-- SC2039: In POSIX sh, 'local' is undefined. > > > > Will this cause an issue for people running posix shells? > Which shells have you tested your script on ? While local is not part of POSIX, it is widely supported, including by dash, and is used by many shell scripts in the kernel's build including link-vmlinux.sh, however I can easily make the script work without local by using unique variable names in each function and resetting all of them at the beginning of the functions if that is desired instead of local. > > Furthermore, I fear this conversion may not be suitable at present, as > it produces potentially different results for CONFIG_HZ < 100 > > (There may be more diffs, but I haven't yet compared a larger search space) > > using a quick script I put together to compare the output of > timeconst.sh and timeconst.bc for a given CONFIG_HZ: > > > https://gist.github.com/kbingham/76e8718df7b7dc97361405cc1801a160 > > > $ for i in `seq 0 300`; do ./check-timeconst.sh $i; done > > produces a diff on almost every value 2 - 243 > > http://paste.ubuntu.com/p/wNggrfFZXB/ > > Or rather 137 faults to be exact: > > for i in `seq 0 250`; \ > do ./check-timeconst.sh $i; \ > done | grep -- "--- BC" | wc -l > > > I think that might be considered a blocker to this implementation, or > those values and the impact should certainly be investigated thoroughly. > > I haven't looked into detail into the change of any of those values, so > I can not ascertain which one is more correct (though I suspect it's > likely to be bc that will have the 'more correct' value) > > I would fear doing this in shell just isn't going to maintain the > correct precision, which is likely a strong reason why bc was selected > in the first place. > > > If you can find the issue that causes this diff in your shell > processing, and clarify or fix it - then it might be possible to gain > some backing to the implementation, but even then it might become a > shell specific precision issue ... That definitely is a blocker, I will attempt to make this implementation match the bc script for those values. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH v3] replace timeconst bc script with an sh script 2019-10-29 21:02 ` [PATCH v3] " Ethan Sommer 2019-10-30 11:37 ` Kieran Bingham @ 2019-11-02 20:54 ` hpa 2019-11-03 21:56 ` Ethan Sommer 1 sibling, 1 reply; 14+ messages in thread From: hpa @ 2019-11-02 20:54 UTC (permalink / raw) To: Ethan Sommer Cc: Jonathan Corbet, Federico Vaga, Chang S. Bae, Andrew Morton, Arnd Bergmann, Masahiro Yamada, Kieran Bingham, Ingo Molnar, Borislav Petkov, Mark Rutland, John Stultz, Kees Cook, Corey Minyard, Thomas Gleixner, linux-doc, linux-kernel On October 29, 2019 2:02:44 PM PDT, Ethan Sommer <e5ten.arch@gmail.com> wrote: >removes the bc build dependency introduced when timeconst.pl was >replaced by timeconst.bc: >commit 70730bca1331 ("kernel: Replace timeconst.pl with a bc script") > >the reason for this change is that this is the only use of bc in the >actual compilation of the kernel, so by replacing it with a shell >script >compiling the kernel no longer depends on bc. > >Signed-off-by: Ethan Sommer <e5ten.arch@gmail.com> >--- > Documentation/process/changes.rst | 6 -- > Kbuild | 4 +- > kernel/time/timeconst.bc | 117 ------------------------------ > kernel/time/timeconst.sh | 111 ++++++++++++++++++++++++++++ > 4 files changed, 113 insertions(+), 125 deletions(-) > delete mode 100644 kernel/time/timeconst.bc > create mode 100644 kernel/time/timeconst.sh > >diff --git a/Documentation/process/changes.rst >b/Documentation/process/changes.rst >index 2284f2221f02..3ae168387109 100644 >--- a/Documentation/process/changes.rst >+++ b/Documentation/process/changes.rst >@@ -105,12 +105,6 @@ Perl > You will need perl 5 and the following modules: ``Getopt::Long``, >``Getopt::Std``, ``File::Basename``, and ``File::Find`` to build the >kernel. > >-BC >--- >- >-You will need bc to build kernels 3.10 and higher >- >- > OpenSSL > ------- > >diff --git a/Kbuild b/Kbuild >index 3109ac786e76..7eba24cbdb78 100644 >--- a/Kbuild >+++ b/Kbuild >@@ -18,9 +18,9 @@ $(bounds-file): kernel/bounds.s FORCE > > timeconst-file := include/generated/timeconst.h > >-filechk_gentimeconst = echo $(CONFIG_HZ) | bc -q $< >+filechk_gentimeconst = $(CONFIG_SHELL) $< $(CONFIG_HZ) > >-$(timeconst-file): kernel/time/timeconst.bc FORCE >+$(timeconst-file): kernel/time/timeconst.sh FORCE > $(call filechk,gentimeconst) > > ##### >diff --git a/kernel/time/timeconst.bc b/kernel/time/timeconst.bc >deleted file mode 100644 >index 7ed0e0fb5831..000000000000 >--- a/kernel/time/timeconst.bc >+++ /dev/null >@@ -1,117 +0,0 @@ >-/* SPDX-License-Identifier: GPL-2.0 */ >- >-scale=0 >- >-define gcd(a,b) { >- auto t; >- while (b) { >- t = b; >- b = a % b; >- a = t; >- } >- return a; >-} >- >-/* Division by reciprocal multiplication. */ >-define fmul(b,n,d) { >- return (2^b*n+d-1)/d; >-} >- >-/* Adjustment factor when a ceiling value is used. Use as: >- (imul * n) + (fmulxx * n + fadjxx) >> xx) */ >-define fadj(b,n,d) { >- auto v; >- d = d/gcd(n,d); >- v = 2^b*(d-1)/d; >- return v; >-} >- >-/* Compute the appropriate mul/adj values as well as a shift count, >- which brings the mul value into the range 2^b-1 <= x < 2^b. Such >- a shift value will be correct in the signed integer range and off >- by at most one in the upper half of the unsigned range. */ >-define fmuls(b,n,d) { >- auto s, m; >- for (s = 0; 1; s++) { >- m = fmul(s,n,d); >- if (m >= 2^(b-1)) >- return s; >- } >- return 0; >-} >- >-define timeconst(hz) { >- print "/* Automatically generated by kernel/time/timeconst.bc */\n" >- print "/* Time conversion constants for HZ == ", hz, " */\n" >- print "\n" >- >- print "#ifndef KERNEL_TIMECONST_H\n" >- print "#define KERNEL_TIMECONST_H\n\n" >- >- print "#include <linux/param.h>\n" >- print "#include <linux/types.h>\n\n" >- >- print "#if HZ != ", hz, "\n" >- print "#error \qinclude/generated/timeconst.h has the wrong HZ >value!\q\n" >- print "#endif\n\n" >- >- if (hz < 2) { >- print "#error Totally bogus HZ value!\n" >- } else { >- s=fmuls(32,1000,hz) >- obase=16 >- print "#define HZ_TO_MSEC_MUL32\tU64_C(0x", fmul(s,1000,hz), ")\n" >- print "#define HZ_TO_MSEC_ADJ32\tU64_C(0x", fadj(s,1000,hz), ")\n" >- obase=10 >- print "#define HZ_TO_MSEC_SHR32\t", s, "\n" >- >- s=fmuls(32,hz,1000) >- obase=16 >- print "#define MSEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000), ")\n" >- print "#define MSEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000), ")\n" >- obase=10 >- print "#define MSEC_TO_HZ_SHR32\t", s, "\n" >- >- obase=10 >- cd=gcd(hz,1000) >- print "#define HZ_TO_MSEC_NUM\t\t", 1000/cd, "\n" >- print "#define HZ_TO_MSEC_DEN\t\t", hz/cd, "\n" >- print "#define MSEC_TO_HZ_NUM\t\t", hz/cd, "\n" >- print "#define MSEC_TO_HZ_DEN\t\t", 1000/cd, "\n" >- print "\n" >- >- s=fmuls(32,1000000,hz) >- obase=16 >- print "#define HZ_TO_USEC_MUL32\tU64_C(0x", fmul(s,1000000,hz), >")\n" >- print "#define HZ_TO_USEC_ADJ32\tU64_C(0x", fadj(s,1000000,hz), >")\n" >- obase=10 >- print "#define HZ_TO_USEC_SHR32\t", s, "\n" >- >- s=fmuls(32,hz,1000000) >- obase=16 >- print "#define USEC_TO_HZ_MUL32\tU64_C(0x", fmul(s,hz,1000000), >")\n" >- print "#define USEC_TO_HZ_ADJ32\tU64_C(0x", fadj(s,hz,1000000), >")\n" >- obase=10 >- print "#define USEC_TO_HZ_SHR32\t", s, "\n" >- >- obase=10 >- cd=gcd(hz,1000000) >- print "#define HZ_TO_USEC_NUM\t\t", 1000000/cd, "\n" >- print "#define HZ_TO_USEC_DEN\t\t", hz/cd, "\n" >- print "#define USEC_TO_HZ_NUM\t\t", hz/cd, "\n" >- print "#define USEC_TO_HZ_DEN\t\t", 1000000/cd, "\n" >- >- cd=gcd(hz,1000000000) >- print "#define HZ_TO_NSEC_NUM\t\t", 1000000000/cd, "\n" >- print "#define HZ_TO_NSEC_DEN\t\t", hz/cd, "\n" >- print "#define NSEC_TO_HZ_NUM\t\t", hz/cd, "\n" >- print "#define NSEC_TO_HZ_DEN\t\t", 1000000000/cd, "\n" >- print "\n" >- >- print "#endif /* KERNEL_TIMECONST_H */\n" >- } >- halt >-} >- >-hz = read(); >-timeconst(hz) >diff --git a/kernel/time/timeconst.sh b/kernel/time/timeconst.sh >new file mode 100644 >index 000000000000..d1aa25f46be8 >--- /dev/null >+++ b/kernel/time/timeconst.sh >@@ -0,0 +1,111 @@ >+#!/bin/sh >+# SPDX-License-Identifier: GPL-2.0 >+ >+if [ -z "$1" ]; then >+ printf '%s <HZ>\n' "$0" >&2 >+ exit 1 >+fi >+ >+# 2 to the power of n >+pot() { >+ local i=1 j=0 >+ while [ "$((j += 1))" -le "$1" ]; do >+ : "$((i *= 2))" >+ done >+ printf '%u' "${i}" >+} >+ >+# Greatest common denominator >+gcd() { >+ local i="$1" j="$2" k >+ while [ "${j}" -ne 0 ]; do >+ k="${j}" j="$((i % j))" i="${k}" >+ done >+ printf '%u' "${i}" >+} >+ >+# Division by reciprocal multiplication. >+fmul() { >+ printf '%u' "$((($(pot "$1") * $2 + $3 - 1) / $3))" >+} >+ >+# Adjustment factor when a ceiling value is used. >+fadj() { >+ local i >+ i="$(gcd "$2" "$3")" >+ printf '%u' "$(($(pot "$1") * ($3 / i - 1) / ($3 / i)))" >+} >+ >+# Compute the appropriate mul/adj values as well as a shift count, >+# which brings the mul value into the range 2^b-1 <= x < 2^b. Such >+# a shift value will be correct in the signed integer range and off >+# by at most one in the upper half of the unsigned range. >+fmuls() { >+ local i=0 j >+ while true; do >+ j="$(fmul "${i}" "$2" "$3")" >+ if [ "${j}" -ge "$(pot "$(($1 - 1))")" ]; then >+ printf '%u' "${i}" >+ return >+ fi >+ : "$((i += 1))" >+ done >+} >+ >+printf '/* Automatically generated by kernel/time/timeconst.sh */\n' >+printf '/* Time conversion constants for HZ == %u */\n\n' "$1" >+ >+printf '#ifndef KERNEL_TIMECONST_H\n' >+printf '#define KERNEL_TIMECONST_H\n\n' >+ >+printf '#include <linux/param.h>\n' >+printf '#include <linux/types.h>\n\n' >+ >+printf '#if HZ != %u\n' "$1" >+printf '#error "include/generated/timeconst.h has the wrong HZ >value!"\n' >+printf '#endif\n\n' >+ >+if [ "$1" -lt 2 ]; then >+ printf '#error Totally bogus HZ value!\n' >+ exit 1 >+fi >+ >+s="$(fmuls 32 1000 "$1")" >+printf '#define HZ_TO_MSEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" 1000 >"$1")" >+printf '#define HZ_TO_MSEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" 1000 >"$1")" >+printf '#define HZ_TO_MSEC_SHR32\t%u\n' "${s}" >+ >+s="$(fmuls 32 "$1" 1000)" >+printf '#define MSEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" >1000)" >+printf '#define MSEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" >1000)" >+printf '#define MSEC_TO_HZ_SHR32\t%u\n' "${s}" >+ >+cd="$(gcd "$1" 1000)" >+printf '#define HZ_TO_MSEC_NUM\t\t%u\n' "$((1000 / cd))" >+printf '#define HZ_TO_MSEC_DEN\t\t%u\n' "$(($1 / cd))" >+printf '#define MSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))" >+printf '#define MSEC_TO_HZ_DEN\t\t%u\n\n' "$((1000 / cd))" >+ >+s="$(fmuls 32 1000000 "$1")" >+printf '#define HZ_TO_USEC_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" >1000000 "$1")" >+printf '#define HZ_TO_USEC_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" >1000000 "$1")" >+printf '#define HZ_TO_USEC_SHR32\t%u\n' "${s}" >+ >+s="$(fmuls 32 "$1" 1000000)" >+printf '#define USEC_TO_HZ_MUL32\tU64_C(0x%X)\n' "$(fmul "${s}" "$1" >1000000)" >+printf '#define USEC_TO_HZ_ADJ32\tU64_C(0x%X)\n' "$(fadj "${s}" "$1" >1000000)" >+printf '#define USEC_TO_HZ_SHR32\t%u\n' "${s}" >+ >+cd="$(gcd "$1" 1000000)" >+printf '#define HZ_TO_USEC_NUM\t\t%u\n' "$((1000000 / cd))" >+printf '#define HZ_TO_USEC_DEN\t\t%u\n' "$(($1 / cd))" >+printf '#define USEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))" >+printf '#define USEC_TO_HZ_DEN\t\t%u\n' "$((1000000 / cd))" >+ >+cd="$(gcd "$1" 1000000000)" >+printf '#define HZ_TO_NSEC_NUM\t\t%u\n' "$((1000000000 / cd))" >+printf '#define HZ_TO_NSEC_DEN\t\t%u\n' "$(($1 / cd))" >+printf '#define NSEC_TO_HZ_NUM\t\t%u\n' "$(($1 / cd))" >+printf '#define NSEC_TO_HZ_DEN\t\t%u\n' "$((1000000000 / cd))" >+ >+printf '\n#endif /* KERNEL_TIMECONST_H */\n' Please let me point out, again, that bc *is* part of the basic POSIX toolset, and the only tool in that toolset that allows for arbitrary-precision arithmetic. That being said, GNU as, which we also depends on, also contains bigint arithmetic, so it might be possible to coax as into outputting ASCII output without manually implementing bigints manually. Another option would be to use a C program linked with gmp. Binutils requires gmp, so it doesn't inherently add dependencies, but running it though as would probably be easier at least for the LLVM guys. I also have written a small, portable C bigint library, but that is a lot of code to add to the tree. -- Sent from my Android device with K-9 Mail. Please excuse my brevity. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH v3] replace timeconst bc script with an sh script 2019-11-02 20:54 ` hpa @ 2019-11-03 21:56 ` Ethan Sommer 2019-11-03 22:00 ` hpa 0 siblings, 1 reply; 14+ messages in thread From: Ethan Sommer @ 2019-11-03 21:56 UTC (permalink / raw) To: H . Peter Anvin Cc: Jonathan Corbet, Federico Vaga, Chang S. Bae, Andrew Morton, Arnd Bergmann, Masahiro Yamada, Kieran Bingham, Ingo Molnar, Borislav Petkov, Mark Rutland, John Stultz, Kees Cook, Corey Minyard, Thomas Gleixner, linux-doc, Linux Kernel Mailing List > Please let me point out, again, that bc *is* part of the basic POSIX toolset, and the only tool in that toolset that allows for arbitrary-precision arithmetic. That being said, GNU as, which we also depends on, also contains bigint arithmetic, so it might be possible to coax as into outputting ASCII output without manually implementing bigints manually. > > Another option would be to use a C program linked with gmp. Binutils requires gmp, so it doesn't inherently add dependencies, but running it though as would probably be easier at least for the LLVM guys. > > I also have written a small, portable C bigint library, but that is a lot of code to add to the tree. I don't know what the requirement is for the level of precision this would need to support is, so I don't know if this meets them, but I made a C program that doesn't use gmp, so while it probably doesn't theoretically have the same level of precision as bc, it does match it for output on anything up to 15000 (it doesn't stop matching timeconst.bc above 15000 I just didn't test any higher). The program is here: http://ix.io/20Ka If this is considered precise enough to be an acceptable replacement I will make a new patch to use it in place of timeconst.bc. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH v3] replace timeconst bc script with an sh script 2019-11-03 21:56 ` Ethan Sommer @ 2019-11-03 22:00 ` hpa 2019-11-03 23:57 ` Ethan Sommer 0 siblings, 1 reply; 14+ messages in thread From: hpa @ 2019-11-03 22:00 UTC (permalink / raw) To: Ethan Sommer Cc: Jonathan Corbet, Federico Vaga, Chang S. Bae, Andrew Morton, Arnd Bergmann, Masahiro Yamada, Kieran Bingham, Ingo Molnar, Borislav Petkov, Mark Rutland, John Stultz, Kees Cook, Corey Minyard, Thomas Gleixner, linux-doc, Linux Kernel Mailing List On November 3, 2019 1:56:50 PM PST, Ethan Sommer <e5ten.arch@gmail.com> wrote: >> Please let me point out, again, that bc *is* part of the basic POSIX >toolset, and the only tool in that toolset that allows for >arbitrary-precision arithmetic. That being said, GNU as, which we also >depends on, also contains bigint arithmetic, so it might be possible to >coax as into outputting ASCII output without manually implementing >bigints manually. >> >> Another option would be to use a C program linked with gmp. Binutils >requires gmp, so it doesn't inherently add dependencies, but running it >though as would probably be easier at least for the LLVM guys. >> >> I also have written a small, portable C bigint library, but that is a >lot of code to add to the tree. >I don't know what the requirement is for the level of precision this >would need to support is, so I don't know if this meets them, but I >made >a C program that doesn't use gmp, so while it probably doesn't >theoretically have the same level of precision as bc, it does match it >for output on anything up to 15000 (it doesn't stop matching >timeconst.bc above 15000 I just didn't test any higher). The program is >here: http://ix.io/20Ka >If this is considered precise enough to be an acceptable replacement >I will make a new patch to use it in place of timeconst.bc. The point isn't to make it work *now*, but getting it to *stay* work. -- Sent from my Android device with K-9 Mail. Please excuse my brevity. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH v3] replace timeconst bc script with an sh script 2019-11-03 22:00 ` hpa @ 2019-11-03 23:57 ` Ethan Sommer 2019-11-04 3:03 ` hpa 0 siblings, 1 reply; 14+ messages in thread From: Ethan Sommer @ 2019-11-03 23:57 UTC (permalink / raw) To: H . Peter Anvin Cc: Jonathan Corbet, Federico Vaga, Chang S. Bae, Andrew Morton, Arnd Bergmann, Masahiro Yamada, Kieran Bingham, Ingo Molnar, Borislav Petkov, Mark Rutland, John Stultz, Kees Cook, Corey Minyard, Thomas Gleixner, linux-doc, Linux Kernel Mailing List > The point isn't to make it work *now*, but getting it to *stay* work. Since the only thing that can change to affect the outcome of the script or program is the value of CONFIG_HZ, isn't knowing that it works within a range of any reasonable values to set CONFIG_HZ to enough to know that it will stay working? I just tested again using the bc script and my C program, and this time I tested every possible value up to 100000, and they both still matched output. It doesn't seem like there's something that would cause the C program to stop working in the future due to precision issues. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH v3] replace timeconst bc script with an sh script 2019-11-03 23:57 ` Ethan Sommer @ 2019-11-04 3:03 ` hpa 0 siblings, 0 replies; 14+ messages in thread From: hpa @ 2019-11-04 3:03 UTC (permalink / raw) To: Ethan Sommer Cc: Jonathan Corbet, Federico Vaga, Chang S. Bae, Andrew Morton, Arnd Bergmann, Masahiro Yamada, Kieran Bingham, Ingo Molnar, Borislav Petkov, Mark Rutland, John Stultz, Kees Cook, Corey Minyard, Thomas Gleixner, linux-doc, Linux Kernel Mailing List On November 3, 2019 3:57:06 PM PST, Ethan Sommer <e5ten.arch@gmail.com> wrote: >> The point isn't to make it work *now*, but getting it to *stay* work. >Since the only thing that can change to affect the outcome of the >script >or program is the value of CONFIG_HZ, isn't knowing that it works >within >a range of any reasonable values to set CONFIG_HZ to enough to know >that >it will stay working? I just tested again using the bc script and my C >program, and this time I tested every possible value up to 100000, and >they both still matched output. It doesn't seem like there's something >that would cause the C program to stop working in the future due to >precision issues. No, it's not. Because some time we are going to want to change the way the constants we need, or use them for something else, and be so on. -- Sent from my Android device with K-9 Mail. Please excuse my brevity. ^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2019-11-04 3:04 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-06-20 6:22 [PATCH] replace timeconst bc script with an sh script Ethan Sommer
2019-06-20 7:23 ` Kieran Bingham
2019-06-20 8:11 ` [PATCH v2] " Ethan Sommer
2019-06-20 8:25 ` Borislav Petkov
2019-06-20 8:43 ` Ethan Sommer
[not found] ` <CAMEGPiqk5TU=z2_wvMfPuihVc5zOLRrTSVCpLA23k0r-hmAzmg@mail.gmail.com>
2019-06-20 8:45 ` Borislav Petkov
2019-10-29 21:02 ` [PATCH v3] " Ethan Sommer
2019-10-30 11:37 ` Kieran Bingham
2019-10-30 16:26 ` Ethan Sommer
2019-11-02 20:54 ` hpa
2019-11-03 21:56 ` Ethan Sommer
2019-11-03 22:00 ` hpa
2019-11-03 23:57 ` Ethan Sommer
2019-11-04 3:03 ` hpa
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).