In Aya/Rust, BPF map definitions are nested in two nested types:
* A struct representing the map type (e.g., `HashMap`, `RingBuf`) that
provides methods for interacting with the map type (e.g. `HashMap::get`,
`RingBuf::reserve`).
* An `UnsafeCell`, which informs the Rust compiler that the type is
thread-safe and can be safely mutated even as a global variable. The
kernel guarantees map operation safety.
This leads to a type hierarchy like:
```rust
pub struct HashMap<K, V, const M: usize, const F: usize = 0>(
core::cell::UnsafeCell<HashMapDef<K, V, M, F>>,
);
const BPF_MAP_TYPE_HASH: usize = 1;
pub struct HashMapDef<K, V, const M: usize, const F: usize = 0> {
r#type: *const [i32; BPF_MAP_TYPE_HASH],
key: *const K,
value: *const V,
max_entries: *const [i32; M],
map_flags: *const [i32; F],
}
```
Then used in the BPF program code as a global variable:
```rust
#[link_section = ".maps"]
static HASH_MAP: HashMap<u32, u32, 1337> = HashMap::new();
```
Which is an equivalent of the following BPF map definition in C:
```c
#define BPF_MAP_TYPE_HASH 1
struct {
int (*type)[BPF_MAP_TYPE_HASH];
typeof(int) *key;
typeof(int) *value;
int (*max_entries)[1337];
} map_1 __attribute__((section(".maps")));
```
Accessing the actual map definition requires traversing:
```
HASH_MAP -> __0 -> value
```
Previously, the BPF backend only visited the pointee types of the
outermost struct, and didn’t descend into inner wrappers. This caused
issues when the key/value types were custom structs:
```rust
// Define custom structs for key and values.
pub struct MyKey(u32);
pub struct MyValue(u32);
#[link_section = ".maps"]
#[export_name = "HASH_MAP"]
pub static HASH_MAP: HashMap<MyKey, MyValue, 10> = HashMap::new();
```
These types weren’t fully visited and appeared in BTF as forward
declarations:
```
#30: <FWD> 'MyKey' kind:struct
#31: <FWD> 'MyValue' kind:struct
```
The fix is to enhance `visitMapDefType` to recursively visit inner
composite members. If a member is a composite type (likely a wrapper),
it is now also visited using `visitMapDefType`, ensuring that the
pointee types of the innermost stuct members, like `MyKey` and
`MyValue`, are fully resolved in BTF.
With this fix, the correct BTF entries are emitted:
```
#6: <STRUCT> 'MyKey' sz:4 n:1
#00 '__0' off:0 --> [7]
#7: <INT> 'u32' bits:32 off:0
#8: <PTR> --> [9]
#9: <STRUCT> 'MyValue' sz:4 n:1
#00 '__0' off:0 --> [7]
```
Fixes: #143361
Ihor Solodrai reported a case ([1]) where gcc reports an error but clang ignores that error and proceeds to generate incorrect code. More specifically, the problematic code looks like: if r1 == 0xcafefeeddeadbeef goto <label> Here, 0xcafefeeddeadbeef needs to be encoded in a 32-bit imm field of the insns and the 32-bit imm allows sign extenstion to 64-bit imm. Obviously, 0xcafefeeddeadbeef cannot encode properly. The compilation failed for gcc with the following error: Error: immediate out of range, shall fit in 32 bits Given a 64-bit imm value, converting to the proper 32-bit imm value must satisfy the following 64-bit patterns: 00000000 00000000 00000000 00000000 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 11111111 11111111 11111111 11111111 1xxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx So if the top 32-bits is 0 or the top 33-bits is 0x1ffffffff, then the 64-bit imm value can be truncated into proper 32-bit imm. Otherwise, a warning message, the same as gcc, will be issued. If -Werror is enabled during compilation, the warning will turn into an error. [1] https://lore.kernel.org/bpf/70affb12-327b-4882-bd1d-afda8b8c6f56@linux.dev/
Currently, to avoid generating too much BTF types, for a struct type
like
```
struct foo {
int val;
struct bar *ptr;
};
```
if the BTF generation reaches 'struct foo', it will not generate actual
type for 'struct bar' and instead a forward decl is generated. The
'struct bar' is actual generated in BTF unless it is reached through a
non-struct pointer member.
Such a limitation forces bpf developer to hack and workaround this
problem. See [1] and [2]. For example in [1], we have
```
struct map_value {
struct prog_test_ref_kfunc *not_kptr;
struct prog_test_ref_kfunc __kptr *val;
struct node_data __kptr *node;
};
```
The BTF type for 'struct node_data' is not generated. Note that we have
a '__kptr' annotation. Similar problem for [2] with a '__uptr'
annotation. Note that the issue in [1] has been resolved later but the
hack in [2] is still needed.
This patch relaxed the struct type (with struct pointer member) BTF
generation if the struct pointer has a btf_type_tag annotation.
[1] https://lore.kernel.org/r/20230310230743.2320707-4-davemarchevsky@fb.com
[2] https://lore.kernel.org/r/20241023234759.860539-9-martin.lau@linux.dev
Currently, middle-end generates 'unreachable' insn if the compiler
feels the code is indeed unreachable or the code becomes invalid
due to some optimizaiton (e.g. code optimization with uninitialized
variables).
Right now BPF backend ignores 'unreachable' insn during selectiondag
lowering. For cases where 'unreachable' is due to invalid code
transformation, such a signal will be missed. Later on, users needs
some effort to debug it which impacts developer productivity.
This patch enabled selectiondag lowering for 'unreachable' insn.
Previous attempt ([1]) tries to have a backend IR pass to filter
out 'unreachable' insns in a number of cases. But such pattern
matching may misalign with future middle-end optimization with
'unreachable' insns.
This patch takes a different approach. The 'unreachable' insn is
lowered with special encoding in bpf object file and verifier
will do proper verification for the bpf prog. More specifically,
the 'unreachable' insn is replaced by a __bpf_trap() function.
This function will be a kfunc (in ".ksyms" section) with a weak
attribute, but does not have definition. The actual kfunc definition
is expected to be in kernel. The __bpf_trap() extern function
is also encoded in BTF. The name __bpf_trap() is chosen to satisfy
reserved identifier requirement.
Besides the uninitialized variable case, the builtin function
'__builtin_trap' can also generate kfunc __bpf_trap(). For example
in [3], we have
```
# define __bpf_unreachable() __builtin_trap()
```
If the compiler didn't remove __builtin_trap() during middle-end
optimization, compilation will fail.
With this patch, compilation will not fail and __builtin_trap()
is converted to __bpf_trap() kfunc. The eventual failure will be
in verifier instead of llvm compilation. To keep compilation
time failure, user can add an option like `-ftrap-function=<something>`.
I tested this patch on bpf selftests and all tests are passed.
I also tried original example in [2] and the code looks like below:
```
; {
0: bf 16 00 00 00 00 00 00 r6 = r1
; bpf_printk("Start");
1: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x0 ll
0000000000000008: R_BPF_64_64 .rodata
3: b4 02 00 00 06 00 00 00 w2 = 0x6
4: 85 00 00 00 06 00 00 00 call 0x6
; DEFINE_FUNC_CTX_POINTER(data)
5: 61 61 4c 00 00 00 00 00 w1 = *(u32 *)(r6 + 0x4c)
; bpf_printk("pre ipv6_hdrlen_offset");
6: 18 01 00 00 06 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x6 ll
0000000000000030: R_BPF_64_64 .rodata
8: b4 02 00 00 17 00 00 00 w2 = 0x17
9: 85 00 00 00 06 00 00 00 call 0x6
10: 85 10 00 00 ff ff ff ff call -0x1
0000000000000050: R_BPF_64_32 __bpf_trap
11: 95 00 00 00 00 00 00 00 exit
<END>
```
Eventually kernel verifier will emit the following logs:
```
10: (85) call __bpf_trap#74479
unexpected __bpf_trap() due to uninitialized variable?
```
In another internal sched-ext bpf prog, with the patch we have bpf code:
```
Disassembly of section .text:
0000000000000000 <scx_storage_init_single>:
; {
0: bc 13 00 00 00 00 00 00 w3 = w1
1: b4 01 00 00 00 00 00 00 w1 = 0x0
; const u32 zero = 0;
...
0000000000003a80 <create_dom>:
; {
1872: bc 16 00 00 00 00 00 00 w6 = w1
; bpf_printk("dom_id %d", dom_id);
1873: 18 01 00 00 3f 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x3f ll
0000000000003a88: R_BPF_64_64 .rodata
1875: b4 02 00 00 0a 00 00 00 w2 = 0xa
1876: bc 63 00 00 00 00 00 00 w3 = w6
1877: 85 00 00 00 06 00 00 00 call 0x6
; ret = scx_bpf_create_dsq(dom_id, 0);
1878: bc 61 00 00 00 00 00 00 w1 = w6
1879: b4 02 00 00 00 00 00 00 w2 = 0x0
1880: 85 10 00 00 ff ff ff ff call -0x1
0000000000003ac0: R_BPF_64_32 scx_bpf_create_dsq
; domc->node_cpumask = node_data[node_id];
1881: 85 10 00 00 ff ff ff ff call -0x1
0000000000003ac8: R_BPF_64_32 __bpf_trap
1882: 95 00 00 00 00 00 00 00 exit
<END>
```
The verifier can easily report the error too.
A bpf flag `-bpf-disable-trap-unreachable` is introduced to disable
trapping for 'unreachable' or __builtin_trap.
[1] https://github.com/llvm/llvm-project/pull/126858
[2] https://github.com/msune/clang_bpf/blob/main/Makefile#L3
[3] https://github.com/libbpf/libbpf/blob/master/src/bpf_helpers.h
Alexei reported a bpf selftest failure with recent llvm for bpf prog
file progs/arena_spin_lock.c. The failure only happens when clang is
built with cmake option LLVM_ENABLE_ASSERTIONS=ON.
The error message looks like:
```
clang: /home/yhs/work/yhs/llvm-project/llvm/lib/IR/Instructions.cpp:3460:
llvm::BitCastInst::BitCastInst(Value *, Type *, const Twine &, InsertPosition):
Assertion `castIsValid(getOpcode(), S, Ty) && "Illegal BitCast"' failed.
```
Further investigation shows that the problem is triggered in
BPF/BPFAbstractMemberAccess.cpp
for code
```
auto *BCInst =
new BitCastInst(Base, PointerType::getUnqual(BB->getContext()));
```
For the above BitCastInst, Since 'Base' has non-zero AddrSapce, the
compiler expects the type also has the same AddrSpace. But the above
PointerType::getUnqual(...) does not have AddrSpace and hence causes the
assertion failure.
Providing the proper AddrSpace for the BitCast type fixed the issue.
Co-authored-by: Yonghong Song <yonghong.song@linux.dev>
As discussed in [1], introduce BPF instructions with load-acquire and
store-release semantics under -mcpu=v4. Define 2 new flags:
BPF_LOAD_ACQ 0x100
BPF_STORE_REL 0x110
A "load-acquire" is a BPF_STX | BPF_ATOMIC instruction with the 'imm'
field set to BPF_LOAD_ACQ (0x100).
Similarly, a "store-release" is a BPF_STX | BPF_ATOMIC instruction with
the 'imm' field set to BPF_STORE_REL (0x110).
Unlike existing atomic read-modify-write operations that only support
BPF_W (32-bit) and BPF_DW (64-bit) size modifiers, load-acquires and
store-releases also support BPF_B (8-bit) and BPF_H (16-bit). An 8- or
16-bit load-acquire zero-extends the value before writing it to a 32-bit
register, just like ARM64 instruction LDAPRH and friends.
As an example (assuming little-endian):
long foo(long *ptr) {
return __atomic_load_n(ptr, __ATOMIC_ACQUIRE);
}
foo() can be compiled to:
db 10 00 00 00 01 00 00 r0 = load_acquire((u64 *)(r1 + 0x0))
95 00 00 00 00 00 00 00 exit
opcode (0xdb): BPF_ATOMIC | BPF_DW | BPF_STX
imm (0x00000100): BPF_LOAD_ACQ
Similarly:
void bar(short *ptr, short val) {
__atomic_store_n(ptr, val, __ATOMIC_RELEASE);
}
bar() can be compiled to:
cb 21 00 00 10 01 00 00 store_release((u16 *)(r1 + 0x0), w2)
95 00 00 00 00 00 00 00 exit
opcode (0xcb): BPF_ATOMIC | BPF_H | BPF_STX
imm (0x00000110): BPF_STORE_REL
Inline assembly is also supported.
Add a pre-defined macro, __BPF_FEATURE_LOAD_ACQ_STORE_REL, to let
developers detect this new feature. It can also be disabled using a new
llc option, -disable-load-acq-store-rel.
Using __ATOMIC_RELAXED for __atomic_store{,_n}() will generate a "plain"
store (BPF_MEM | BPF_STX) instruction:
void foo(short *ptr, short val) {
__atomic_store_n(ptr, val, __ATOMIC_RELAXED);
}
6b 21 00 00 00 00 00 00 *(u16 *)(r1 + 0x0) = w2
95 00 00 00 00 00 00 00 exit
Similarly, using __ATOMIC_RELAXED for __atomic_load{,_n}() will generate
a zero-extending, "plain" load (BPF_MEM | BPF_LDX) instruction:
int foo(char *ptr) {
return __atomic_load_n(ptr, __ATOMIC_RELAXED);
}
71 11 00 00 00 00 00 00 w1 = *(u8 *)(r1 + 0x0)
bc 10 08 00 00 00 00 00 w0 = (s8)w1
95 00 00 00 00 00 00 00 exit
Currently __ATOMIC_CONSUME is an alias for __ATOMIC_ACQUIRE. Using
__ATOMIC_SEQ_CST ("sequentially consistent") is not supported yet and
will cause an error:
$ clang --target=bpf -mcpu=v4 -c bar.c > /dev/null
bar.c:1:5: error: sequentially consistent (seq_cst) atomic load/store is
not supported
1 | int foo(int *ptr) { return __atomic_load_n(ptr, __ATOMIC_SEQ_CST); }
| ^
...
Finally, rename those isST*() and isLD*() helper functions in
BPFMISimplifyPatchable.cpp based on what the instructions actually do,
rather than their instruction class.
[1]
https://lore.kernel.org/all/20240729183246.4110549-1-yepeilin@google.com/
This fixes the handling of subregister extract copies. This will allow AMDGPU to remove its implementation of shouldRewriteCopySrc, which exists as a 10 year old workaround to this bug. peephole-opt-fold-reg-sequence-subreg.mir will show the expected improvement once the custom implementation is removed. The copy coalescing processing here is overly abstracted from what's actually happening. Previously when visiting coalescable copy-like instructions, we would parse the sources one at a time and then pass the def of the root instruction into findNextSource. This means that the first thing the new ValueTracker constructed would do is getVRegDef to find the instruction we are currently processing. This adds an unnecessary step, placing a useless entry in the RewriteMap, and required skipping the no-op case where getNewSource would return the original source operand. This was a problem since in the case of a subregister extract, shouldRewriteCopySource would always say that it is useful to rewrite and the use-def chain walk would abort, returning the original operand. Move the process to start looking at the source operand to begin with. This does not fix the confused handling in the uncoalescable copy case which is proving to be more difficult. Some currently handled cases have multiple defs from a single source, and other handled cases have 0 input operands. It would be simpler if this was implemented with isCopyLikeInstr, rather than guessing at the operand structure as it does now. There are some improvements and some regressions. The regressions appear to be downstream issues for the most part. One of the uglier regressions is in PPC, where a sequence of insert_subrgs is used to build registers. I opened #125502 to use reg_sequence instead, which may help. The worst regression is an absurd SPARC testcase using a <251 x fp128>, which uses a very long chain of insert_subregs. We need improved subregister handling locally in PeepholeOptimizer, and other pasess like MachineCSE to fix some of the other regressions. We should handle subregister composes and folding more indexes into insert_subreg and reg_sequence.
This PR removes the old `nocapture` attribute, replacing it with the new `captures` attribute introduced in #116990. This change is intended to be essentially NFC, replacing existing uses of `nocapture` with `captures(none)` without adding any new analysis capabilities. Making use of non-`none` values is left for a followup. Some notes: * `nocapture` will be upgraded to `captures(none)` by the bitcode reader. * `nocapture` will also be upgraded by the textual IR reader. This is to make it easier to use old IR files and somewhat reduce the test churn in this PR. * Helper APIs like `doesNotCapture()` will check for `captures(none)`. * MLIR import will convert `captures(none)` into an `llvm.nocapture` attribute. The representation in the LLVM IR dialect should be updated separately.
Emil Tsalapatis from Meta reported such a case where 'may_goto 0' insn is generated by clang compiler. But 'may_goto 0' insn is actually a no-op so it makes sense to remove that in llvm. The patch is also able to handle the following code pattern ``` ... may_goto 2 may_goto 1 may_goto 0 ... ``` where three may_goto insns can all be removed. --------- Co-authored-by: Yonghong Song <yonghong.song@linux.dev>
Similar to 806761a7629df268c8aed49657aeccffa6bca449 -mtriple= specifies the full target triple while -march= merely sets the architecture part of the default target triple (e.g. Windows, macOS), leaving a target triple which may not make sense. Therefore, -march= is error-prone and not recommended for tests without a target triple. The issue has been benign as we recognize bpf*-apple-darwin as ELF instead of rejecting it outrightly.