arm64: insn: Generate 64 bit mask immediates correctly
cover arm64: insn: Generate 64 bit mask immediates correctly
Hello,
aarch64_insn_gen_logical_immediate() is generating the wrong code if it is handed a 64bit immediate which has a single span of 1s (i.e. a mask), with bit 63 set, and 0s in the remaining upper 32 bits. Clear as mud. An example always helps: 0x800000003fffffff would be wrongly encoded, but 0x000000003fffffff is unaffected.
It would appear eBPF is unable to hit these cases, as build_insn()'s imm value is a s32, so when used with BPF_ALU64, the sign-extended u64 immediate would always have all-1s or all-0s in the upper 32 bits.
KVM does not generate a va_mask with any of the top bits set as these VA wouldn't be usable with TTBR0_EL2.
Patch 3 fixes it, and doesn't depend on the rest of the series.
As the instruction encoder is a source of headaches, the first two patches add tests to help illustrate there is a problem, and that patch 3 fixes it.
The tests generate a header file of the expected values so it can be compared against other sources of the same information. Objdump can be used to check the header file is generated correctly. Embedding the code in gen_logic_imm in test_insn.c would give less confidence that the encoder is doing the right thing.
This series is based on v5.17-rc1, and can be retrieved from:
https://git.gitlab.arm.com/linux-arm/linux-jm.git insn_encoder/fls_bug/v1
Thanks,
James Morse (3):
arm64: selftests: Generate all the possible logical immediates as a
header
arm64: insn: Add tests for aarch64_insn_gen_logical_immediate()
arm64: insn: Generate 64 bit mask immediates correctly
arch/arm64/Kconfig.debug | 3 + arch/arm64/Makefile | 3 + arch/arm64/lib/Makefile | 2 + arch/arm64/lib/insn.c | 5 +- arch/arm64/lib/test_insn.c | 90 ++++++++++ arch/arm64/tools/.gitignore | 2 + arch/arm64/tools/Makefile | 12 +- arch/arm64/tools/gen_logic_imm.c | 190 +++++++++++++++++++++ tools/testing/selftests/arm64/Makefile | 2 +- tools/testing/selftests/arm64/lib/Makefile | 6 + tools/testing/selftests/arm64/lib/config | 1 + tools/testing/selftests/arm64/lib/insn.sh | 5 + 12 files changed, 318 insertions(+), 3 deletions(-) create mode 100644 arch/arm64/lib/test_insn.c create mode 100644 arch/arm64/tools/.gitignore create mode 100644 arch/arm64/tools/gen_logic_imm.c create mode 100644 tools/testing/selftests/arm64/lib/Makefile create mode 100644 tools/testing/selftests/arm64/lib/config create mode 100755 tools/testing/selftests/arm64/lib/insn.sh
Signature · 1 line
2.30.2
PATCH 1/3 arm64: selftests: Generate all the possible logical immediates as a header
Aarch64 has instructions to generate reasonably complicated 32 or 64 bit masks from only 13 bits of information. To test the in-kernel code that spots the pattern to produce the instruction encoding a golden set of values is needed.
A header file containing these is large. Instead, generate every possible instruction encoding, and its decoded immediate, based on the arm-arm's DecodeBitMasks() pseudocode. These are output in a format that can be used in a header file for the test.
Having the golden values in a header file allows them to be inspected, and checked against a trusted source. The generation program can be told to pass each value through objdump and compared.
Unsat's jitterbug project has a python script that does this too, but the license isn't clear from the github repository.
--- arch/arm64/Makefile | 1 + arch/arm64/tools/.gitignore | 2 + arch/arm64/tools/Makefile | 12 +- arch/arm64/tools/gen_logic_imm.c | 190 +++++++++++++++++++++++++++++++ 4 files changed, 204 insertions(+), 1 deletion(-) create mode 100644 arch/arm64/tools/.gitignore create mode 100644 arch/arm64/tools/gen_logic_imm.c
arch/arm64/Makefile +1 -0
@@ -176,6 +176,7 @@ vdso_install: archprepare: $(Q)$(MAKE) $(build)=arch/arm64/tools kapi + $(Q)$(MAKE) $(build)=arch/arm64/tools tests ifeq ($(CONFIG_ARM64_ERRATUM_843419),y) ifneq ($(CONFIG_ARM64_LD_HAS_FIX_ERRATUM_843419),y) @echo "warning: ld does not support --fix-cortex-a53-843419; kernel may be susceptible to erratum" >&2
arch/arm64/tools/.gitignore new file +2 -0
@@ -0,0 +1,2 @@ +# SPDX-License-Identifier: GPL-2.0-only +gen_logic_imm
arch/arm64/tools/Makefile +11 -1
@@ -4,10 +4,11 @@ gen := arch/$(ARCH)/include/generated kapi := $(gen)/asm kapi-hdrs-y := $(kapi)/cpucaps.h +tests-hdrs-y := $(kapi)/test_logic_imm_generated.h targets += $(addprefix ../../../,$(gen-y) $(kapi-hdrs-y)) -PHONY += kapi +PHONY += kapi tests kapi: $(kapi-hdrs-y) $(gen-y)
@@ -20,3 +21,12 @@ quiet_cmd_gen_cpucaps = GEN $@ $(kapi)/cpucaps.h: $(src)/gen-cpucaps.awk $(src)/cpucaps FORCE $(call if_changed,gen_cpucaps) + +tests: $(tests-hdrs-y) $(gen-y) + +quiet_cmd_build_gen_logic_imm = GEN $@ + cmd_build_gen_logic_imm = $(obj)/gen_logic_imm > $@ + +hostprogs := gen_logic_imm +$(kapi)/test_logic_imm_generated.h: $(obj)/gen_logic_imm FORCE + $(call if_changed,build_gen_logic_imm)
arch/arm64/tools/gen_logic_imm.c new file +190 -0
190 lines not on this page · raw message
Signature · 1 line
2.30.2
kernel test robot
build botRe: [PATCH 1/3] arm64: selftests: Generate all the possible logical immediates as a header
I love your patch! Perhaps something to improve:
Hi James,
I love your patch! Perhaps something to improve:
[auto build test WARNING on arm64/for-next/core]
[also build test WARNING on arm/for-next xilinx-xlnx/master soc/for-next kvmarm/next v5.17-rc1 next-20220127] [If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]
url: https://github.com/0day-ci/linux/commits/James-Morse/arm64-insn-Generate-64-bit-mask-immediates-correctly/20220128-002213 base: https://git.kernel.org/pub/scm/linux/kernel/git/arm64/linux.git for-next/core config: arm64-randconfig-p001-20220128 (https://download.01.org/0day-ci/archive/20220128/202201281052.Nzl9wJM4-lkp(a)intel.com/config) compiler: aarch64-linux-gcc (GCC) 11.2.0
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# https://github.com/0day-ci/linux/commit/1ead98d2c8c4c28ea27964dbf7b5b89a83b8e7ec
git remote add linux-review https://github.com/0day-ci/linux
git fetch --no-tags linux-review James-Morse/arm64-insn-Generate-64-bit-mask-immediates-correctly/20220128-002213 git checkout 1ead98d2c8c4c28ea27964dbf7b5b89a83b8e7ec
# save the config file to linux build tree
mkdir build_dir
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-11.2.0 make.cross O=build_dir ARCH=arm64 prepare
If you fix the issue, kindly add following tag as appropriate
All warnings (new ones prefixed by >>):
arch/arm64/tools/gen_logic_imm.c: In function 'validate':
>> arch/arm64/tools/gen_logic_imm.c:81:2: warning: ignoring return value of 'write' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | write(fd, &insn, sizeof(insn));
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
arch/arm64/tools/gen_logic_imm.c: In function 'validate':
>> arch/arm64/tools/gen_logic_imm.c:81:2: warning: ignoring return value of 'write' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | write(fd, &insn, sizeof(insn));
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ arch/arm64/kernel/vdso/vgettimeofday.c:9:5: warning: no previous prototype for '__kernel_clock_gettime' [-Wmissing-prototypes]
9 | int __kernel_clock_gettime(clockid_t clock,
| ^~~~~~~~~~~~~~~~~~~~~~
arch/arm64/kernel/vdso/vgettimeofday.c:15:5: warning: no previous prototype for '__kernel_gettimeofday' [-Wmissing-prototypes]
15 | int __kernel_gettimeofday(struct __kernel_old_timeval *tv,
| ^~~~~~~~~~~~~~~~~~~~~
arch/arm64/kernel/vdso/vgettimeofday.c:21:5: warning: no previous prototype for '__kernel_clock_getres' [-Wmissing-prototypes]
21 | int __kernel_clock_getres(clockid_t clock_id,
| ^~~~~~~~~~~~~~~~~~~~~
vim +81 arch/arm64/tools/gen_logic_imm.c
55
56 #define PIPE_READ 0
57 #define PIPE_WRITE 1
58 /*
59 * Use objdump to decode the encoded instruction, and compare the immediate.
60 * On error, returns the bad instruction, otherwise returns 0.
61 */
62 static int validate(u64 val, u32 immN, u32 imms, u32 immr, char *objdump)
63 {
64 pid_t child;
65 char *immediate;
66 char val_str[32];
67 u32 insn = 0x12000000;
68 char output[1024] = {0};
69 int fd, pipefd[2], bytes;
70 char filename[] = "validate_gen_logic_imm.XXXXXX";
71
72 insn |= 1 << 31;
73 insn |= (immN & 0x1)<<22;
74 insn |= (immr & 0x3f)<<16;
75 insn |= (imms & 0x3f)<<10;
76
77 fd = mkstemp(filename);
78 if (fd < 0)
79 abort();
80
> 81 write(fd, &insn, sizeof(insn));
82 close(fd);
83
84 if (pipe(pipefd))
85 return 0;
86
87 child = vfork();
88 if (child) {
89 close(pipefd[PIPE_WRITE]);
90 waitpid(child, NULL, 0);
91
92 bytes = read(pipefd[PIPE_READ], output, sizeof(output));
93 close(pipefd[PIPE_READ]);
94 if (!bytes || bytes == sizeof(output))
95 return insn;
96
97 immediate = strstr(output, "x0, x0, #");
98 if (!immediate)
99 return insn; 100 immediate += strlen("x0, x0, #");
101
102 /*
103 * strtoll() has its own ideas about overflow and underflow.
104 * Do a string comparison. immediate ends in a newline.
105 */
106 snprintf(val_str, sizeof(val_str), "0x%lx", val);
107 if (strncmp(val_str, immediate, strlen(val_str))) {
108 fprintf(stderr, "Unexpected decode from objdump: %s\n",
109 immediate);
110 return insn;
111 }
112 } else {
113 close(pipefd[PIPE_READ]);
114 close(1);
115 dup2(pipefd[PIPE_WRITE], 1);
116 execl(objdump, objdump, "-b", "binary", "-m", "aarch64", "-D",
117 filename, (char *) NULL);
118 abort();
119 }
120
121 unlink(filename);
122 return 0;
123 }
124
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org
PATCH 2/3 arm64: insn: Add tests for aarch64_insn_gen_logical_immediate()
In reply to James MorseAarch64 has instructions to generate reasonably complicated 32 or 64 bit masks from only 13 bits of information. aarch64_insn_gen_logical_immediate() has to created the immediate encoding by spotting the patterns in the 32 or 64 bit immediate.
Despite attempts to validate or model this code, or use it as-is outside the kernel tree, bugs still exist.
Add a self test module that tests this code in place against a golden set of values.
--- arch/arm64/Kconfig.debug | 3 + arch/arm64/Makefile | 2 + arch/arm64/lib/Makefile | 2 + arch/arm64/lib/insn.c | 3 + arch/arm64/lib/test_insn.c | 90 ++++++++++++++++++++++ tools/testing/selftests/arm64/Makefile | 2 +- tools/testing/selftests/arm64/lib/Makefile | 6 ++ tools/testing/selftests/arm64/lib/config | 1 + tools/testing/selftests/arm64/lib/insn.sh | 5 ++ 9 files changed, 113 insertions(+), 1 deletion(-) create mode 100644 arch/arm64/lib/test_insn.c create mode 100644 tools/testing/selftests/arm64/lib/Makefile create mode 100644 tools/testing/selftests/arm64/lib/config create mode 100755 tools/testing/selftests/arm64/lib/insn.sh
arch/arm64/Kconfig.debug +3 -0
@@ -20,4 +20,7 @@ config ARM64_RELOC_TEST depends on m tristate "Relocation testing module" +config TEST_INSN + tristate "Test functions located in the aarch64 instruction encoder at runtime" + source "drivers/hwtracing/coresight/Kconfig"
arch/arm64/Makefile +2 -0
@@ -176,7 +176,9 @@ vdso_install: archprepare: $(Q)$(MAKE) $(build)=arch/arm64/tools kapi +#ifdef CONFIG_TEST_INSN $(Q)$(MAKE) $(build)=arch/arm64/tools tests +#endif ifeq ($(CONFIG_ARM64_ERRATUM_843419),y) ifneq ($(CONFIG_ARM64_LD_HAS_FIX_ERRATUM_843419),y) @echo "warning: ld does not support --fix-cortex-a53-843419; kernel may be susceptible to erratum" >&2
arch/arm64/lib/Makefile +2 -0
@@ -22,3 +22,5 @@ obj-$(CONFIG_FUNCTION_ERROR_INJECTION) += error-inject.o obj-$(CONFIG_ARM64_MTE) += mte.o obj-$(CONFIG_KASAN_SW_TAGS) += kasan_sw_tags.o + +obj-$(CONFIG_TEST_INSN) += test_insn.o
arch/arm64/lib/insn.c +3 -0
@@ -193,6 +193,7 @@ u64 aarch64_insn_decode_immediate(enum aarch64_insn_imm_type type, u32 insn)return (insn >> shift) & mask; } +EXPORT_SYMBOL_GPL (aarch64_insn_decode_immediate);u32 __kprobes aarch64_insn_encode_immediate (enum aarch64_insn_imm_type type,u32 insn,u64 imm)
@@ -256,6 +257,7 @@ u32 aarch64_insn_decode_register(enum aarch64_insn_register_type type,return (insn >> shift) &GENMASK (4 ,0 ); } +EXPORT_SYMBOL_GPL (aarch64_insn_decode_register); static u32 aarch64_insn_encode_register(enum aarch64_insn_register_type type, u32 insn,
@@ -1424,6 +1426,7 @@ u32 aarch64_insn_gen_logical_immediate(enum aarch64_insn_logic_type type, insn =aarch64_insn_encode_register (AARCH64_INSN_REGTYPE_RN , insn, Rn);return aarch64_encode_immediate (imm, variant, insn); } +EXPORT_SYMBOL_GPL (aarch64_insn_gen_logical_immediate); u32 aarch64_insn_gen_extr(enum aarch64_insn_variant variant, enum aarch64_insn_register Rm,
arch/arm64/lib/test_insn.c new file +90 -0
90 lines not on this page · raw message
tools/testing/selftests/arm64/Makefile +1 -1
@@ -4,7 +4,7 @@ ARCH ?= $(shell uname -m 2>/dev/null || echo not) ifneq (,$(filter $(ARCH),aarch64 arm64)) -ARM64_SUBTARGETS ?= tags signal pauth fp mte bti abi +ARM64_SUBTARGETS ?= tags signal pauth fp mte bti abi lib else ARM64_SUBTARGETS := endif
tools/testing/selftests/arm64/lib/Makefile new file +6 -0
@@ -0,0 +1,6 @@ +# Copyright (C) 2022 ARM Limited +# Makefile for arm64/lib/ function selftests + +TEST_PROGS := insn.sh + +include ../../lib.mk
tools/testing/selftests/arm64/lib/config new file +1 -0
@@ -0,0 +1 @@ +CONFIG_TEST_INSN=m
tools/testing/selftests/arm64/lib/insn.sh new file +5 -0
@@ -0,0 +1,5 @@ +#!/bin/sh +# SPDX-License-Identifier: GPL-2.0 +# Tests the aarch64 instruction generation infrastructure using test_insn +# kernel module. +$(dirname $0)/../../kselftest/module.sh "insn" test_insn
Signature · 1 line
2.30.2
Will Deacon
maintainerRe: [PATCH 2/3] arm64: insn: Add tests for aarch64_insn_gen_logical_immediate()
Quoted 11 lines · James Morse
Aarch64 has instructions to generate reasonably complicated 32 or 64 bit masks from only 13 bits of information.
aarch64_insn_gen_logical_immediate()has to created the immediate encoding by spotting the patterns in the 32 or 64 bit immediate.Despite attempts to validate or model this code, or use it as-is outside the kernel tree, bugs still exist.
Add a self test module that tests this code in place against a golden set of values.
Quoted 7 lines
Signed-off-by James Morse <[email protected]>--- arch/arm64/Kconfig.debug | 3 + arch/arm64/Makefile | 2 + arch/arm64/lib/Makefile | 2 + arch/arm64/lib/insn.c | 3 + arch/arm64/lib/test_insn.c | 90 ++++++++++++++++++++++
Can we put the new tests under tools/testing/selftests/arm64 as well, please? It looks like there's precedence for having modules in there (e.g. bpf_testmod.c).
In the meantime, I'll pick up patch 3.
Cheers,
Will
PATCH 3/3 arm64: insn: Generate 64 bit mask immediates correctly
In reply to James MorseWhen the insn framework is used to encode an AND/ORR/EOR instruction, aarch64_encode_immediate() is used to pick the immr imms values.
If the immediate is a 64bit mask, with bit 63 set, and zeros in any of the upper 32 bits, the immr value is incorrectly calculated meaning the wrong mask is generated.
For example, 0x8000000000000001 should have an immr of 1, but 32 is used, meaning the resulting mask is 0x0000000300000000.
It would appear eBPF is unable to hit these cases, as build_insn()'s imm value is a s32, so when used with BPF_ALU64, the sign-extended u64 immediate would always have all-1s or all-0s in the upper 32 bits.
KVM does not generate a va_mask with any of the top bits set as these VA wouldn't be usable with TTBR0_EL2.
This happens because the rotation is calculated from fls(~imm), which takes an unsigned int, but the immediate may be 64bit.
Use fls64() so the 64bit mask doesn't get truncated to a u32.
--- arch/arm64/lib/insn.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
arch/arm64/lib/insn.c +1 -1
@@ -1381,7 +1381,7 @@ static u32 aarch64_encode_immediate(u64 imm,* Compute the rotation to get a continuous set of * ones, with the first bit set at position 0 */ - ror =fls (~imm); + ror =fls64 (~imm); }/*
Signature · 1 line
2.30.2
Quoted 32 lines · James Morse
When the insn framework is used to encode an AND/ORR/EOR instruction,
aarch64_encode_immediate()is used to pick the immr imms values.If the immediate is a 64bit mask, with bit 63 set, and zeros in any of the upper 32 bits, the immr value is incorrectly calculated meaning the wrong mask is generated.
For example,0x8000000000000001should have an immr of 1, but 32 is used, meaning the resulting mask is0x0000000300000000.It would appear eBPF is unable to hit these cases, as build_insn()'s imm value is a s32, so when used with
BPF_ALU64, the sign-extended u64 immediate would always have all-1s or all-0s in the upper 32 bits.KVM does not generate a
va_maskwith any of the top bits set as these VA wouldn't be usable withTTBR0_EL2.This happens because the rotation is calculated from fls(~imm), which takes an unsigned int, but the immediate may be 64bit.
Use
fls64()so the 64bit mask doesn't get truncated to a u32.Signed-off-by James Morse <[email protected]>--- arch/arm64/lib/insn.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)arch/arm64/lib/insn.c +0
-0
arch/arm64/lib/insn.c static u32 aarch64_encode_immediate(u64 imm, · line 1387
Quoted 8 lines
arch/arm64/lib/insn.c +1
-1@@ -1381,7 +1381,7 @@ static u32 aarch64_encode_immediate(u64 imm,* Compute the rotation to get a continuous set of * ones, with the first bit set at position 0 */ - ror =fls (~imm); + ror =fls64 (~imm); }/*
Oh crap, not again... :-( Clearly, my initial test harness wasn't as good as I thought. Out for morbid curiosity, how was this found?
Brown-paper-bag-for: Marc Zyngier <[email protected]>
M.
Signature · 1 line
Without deviation from the norm, progress is not possible.
Quoted 11 lines · James Morse
aarch64_insn_gen_logical_immediate()is generating the wrong code if it is handed a 64bit immediate which has a single span of 1s (i.e. a mask), with bit 63 set, and 0s in the remaining upper 32 bits. Clear as mud. An example always helps:0x800000003fffffffwould be wrongly encoded, but0x000000003fffffffis unaffected.It would appear eBPF is unable to hit these cases, as build_insn()'s imm value is a s32, so when used with
BPF_ALU64, the sign-extended u64 immediate would always have all-1s or all-0s in the upper 32 bits.[...]
Applied to arm64 (for-next/insn), thanks!
[1/3] arm64: selftests: Generate all the possible logical immediates as a header
(no commit info)
[2/3] arm64: insn: Add tests for aarch64_insn_gen_logical_immediate()
(no commit info)
[3/3] arm64: insn: Generate 64 bit mask immediates correctly
https://git.kernel.org/arm64/c/a6aab0188299
Cheers,
Signature · 5 lines
Will https://fixes.arm64.dev https://next.arm64.dev https://will.arm64.dev