Re: [PATCH v3] replace timeconst bc script with an sh script

[Kieran Bingham <kieran.bingham@ideasonboard.com>]

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