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

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

Co-authored-by: Nikita Popov <github@npopov.com>

Note that PointerUnion::{is,get,dyn_cast} have been soft deprecated in
PointerUnion.h:

  // FIXME: Replace the uses of is(), get() and dyn_cast() with
  //        isa<T>, cast<T> and the llvm::dyn_cast<T>

Three commits in this pull request:
commit 1: implement pattern matching for memory ordering seq_cst,
acq_rel, release, acquire and monotonic. Specially, for monotonic memory
ordering (relaxed memory model), if no return value is used, locked insn
is used.
commit 2: add support to handle dwarf atomic modifier in BTF generation.
Actually atomic modifier is ignored in BTF.
commit 3: add tests for new atomic ordering support and BTF support with
_Atomic type.
I removed RFC tag as now patch sets are in reasonable states.

For atomic fetch_and_*() operations, do pattern matching with memory
ordering
seq_cst, acq_rel, release, acquire and monotonic (relaxed). For
fetch_and_*()
operations with seq_cst/acq_rel/release/acquire ordering,
atomic_fetch_*()
instructions are generated. For monotonic ordering, locked insns are
generated
if return value is not used. Otherwise, atomic_fetch_*() insns are used.
The main motivation is to resolve the kernel issue [1].
   
The following are memory ordering are supported:
  seq_cst, acq_rel, release, acquire, relaxed
Current gcc style __sync_fetch_and_*() operations are all seq_cst.

To use explicit memory ordering, the _Atomic type is needed. The
following is
an example:

```
$ cat test.c
\#include <stdatomic.h>
void f1(_Atomic int *i) {
   (void)__c11_atomic_fetch_and(i, 10, memory_order_relaxed);
}
void f2(_Atomic int *i) {
   (void)__c11_atomic_fetch_and(i, 10, memory_order_acquire);
}
void f3(_Atomic int *i) {
   (void)__c11_atomic_fetch_and(i, 10, memory_order_seq_cst);
}
$ cat run.sh
clang  -I/home/yhs/work/bpf-next/tools/testing/selftests/bpf -O2 --target=bpf -c test.c -o test.o && llvm-objdum
p -d test.o
$ ./run.sh
       
test.o: file format elf64-bpf
       
Disassembly of section .text:

0000000000000000 <f1>:
       0:       b4 02 00 00 0a 00 00 00 w2 = 0xa
       1:       c3 21 00 00 50 00 00 00 lock *(u32 *)(r1 + 0x0) &= w2
       2:       95 00 00 00 00 00 00 00 exit
       
0000000000000018 <f2>:
       3:       b4 02 00 00 0a 00 00 00 w2 = 0xa
       4:       c3 21 00 00 51 00 00 00 w2 = atomic_fetch_and((u32 *)(r1 + 0x0), w2)
       5:       95 00 00 00 00 00 00 00 exit
       
0000000000000030 <f3>:
       6:       b4 02 00 00 0a 00 00 00 w2 = 0xa
       7:       c3 21 00 00 51 00 00 00 w2 = atomic_fetch_and((u32 *)(r1 + 0x0), w2)
       8:       95 00 00 00 00 00 00 00 exit
```    

The following is another example where return value is used:

```
$ cat test1.c
\#include <stdatomic.h>
int f1(_Atomic int *i) {
   return __c11_atomic_fetch_and(i, 10, memory_order_relaxed);
}  
int f2(_Atomic int *i) {
   return __c11_atomic_fetch_and(i, 10, memory_order_acquire);
}  
int f3(_Atomic int *i) {
   return __c11_atomic_fetch_and(i, 10, memory_order_seq_cst);
}  
$ cat run.sh
clang  -I/home/yhs/work/bpf-next/tools/testing/selftests/bpf -O2 --target=bpf -c test1.c -o test1.o && llvm-objdump -d test1.o
$ ./run.sh

test.o: file format elf64-bpf

Disassembly of section .text:

0000000000000000 <f1>:
       0:       b4 00 00 00 0a 00 00 00 w0 = 0xa
       1:       c3 01 00 00 51 00 00 00 w0 = atomic_fetch_and((u32 *)(r1 + 0x0), w0)
       2:       95 00 00 00 00 00 00 00 exit
       
0000000000000018 <f2>:
       3:       b4 00 00 00 0a 00 00 00 w0 = 0xa
       4:       c3 01 00 00 51 00 00 00 w0 = atomic_fetch_and((u32 *)(r1 + 0x0), w0)
       5:       95 00 00 00 00 00 00 00 exit
       
0000000000000030 <f3>:
       6:       b4 00 00 00 0a 00 00 00 w0 = 0xa
       7:       c3 01 00 00 51 00 00 00 w0 = atomic_fetch_and((u32 *)(r1 + 0x0), w0)
       8:       95 00 00 00 00 00 00 00 exit
```    

You can see that for relaxed memory ordering, if return value is used,
atomic_fetch_and()
insn is used. Otherwise, if return value is not used, locked insn is
used.

Here is another example with global _Atomic variable:

```
$ cat test3.c
\#include <stdatomic.h>

_Atomic int i;

void f1(void) {
   (void)__c11_atomic_fetch_and(&i, 10, memory_order_relaxed);
}
void f2(void) {
   (void)__c11_atomic_fetch_and(&i, 10, memory_order_seq_cst);
}
$ cat run.sh
clang  -I/home/yhs/work/bpf-next/tools/testing/selftests/bpf -O2 --target=bpf -c test3.c -o test3.o && llvm-objdump -d test3.o
$ ./run.sh

test3.o:        file format elf64-bpf

Disassembly of section .text:

0000000000000000 <f1>:
       0:       b4 01 00 00 0a 00 00 00 w1 = 0xa
       1:       18 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r2 = 0x0 ll
       3:       c3 12 00 00 50 00 00 00 lock *(u32 *)(r2 + 0x0) &= w1
       4:       95 00 00 00 00 00 00 00 exit
       
0000000000000028 <f2>:
       5:       b4 01 00 00 0a 00 00 00 w1 = 0xa
       6:       18 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r2 = 0x0 ll
       8:       c3 12 00 00 51 00 00 00 w1 = atomic_fetch_and((u32 *)(r2 + 0x0), w1)
       9:       95 00 00 00 00 00 00 00 exit
```    

Note that in the above compilations, '-g' is not used. The reason is due
to the following IR
related to _Atomic type:
```
$clang  -I/home/yhs/work/bpf-next/tools/testing/selftests/bpf -O2 --target=bpf -g -S -emit-llvm test3.c
```
The related debug info for test3.c:
```
!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
!1 = distinct !DIGlobalVariable(name: "i", scope: !2, file: !3, line: 3, type: !16, isLocal: false, isDefinition: true)
...
!16 = !DIDerivedType(tag: DW_TAG_atomic_type, baseType: !17)
!17 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
```

If compiling test.c, the related debug info:
```
...
!19 = distinct !DISubprogram(name: "f1", scope: !1, file: !1, line: 3, type: !20, scopeLine: 3, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !25)
!20 = !DISubroutineType(types: !21)
!21 = !{null, !22}
!22 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !23, size: 64)
!23 = !DIDerivedType(tag: DW_TAG_atomic_type, baseType: !24)
!24 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
!25 = !{!26}
!26 = !DILocalVariable(name: "i", arg: 1, scope: !19, file: !1, line: 3, type: !22)
```

All the above suggests _Atomic behaves like a modifier (e.g. const,
restrict, volatile).
This seems true based on doc [1].

Without proper handling DW_TAG_atomic_type, llvm BTF generation will be
incorrect since
the current implementation assumes no existence of DW_TAG_atomic_type.
So we have
two choices here:
(1). llvm bpf backend processes DW_TAG_atomic_type but ignores it in BTF
encoding.
(2). Add another type, e.g., BTF_KIND_ATOMIC to BTF. BTF_KIND_ATOMIC
behaves as a
       modifier like const/volatile/restrict.

For choice (1), llvm bpf backend should skip dwarf::DW_TAG_atomic_type
during
BTF generation whenever necessary.

For choice (2), BTF_KIND_ATOMIC will be added to BTF so llvm backend and
kernel
needs to handle that properly. The main advantage of it probably is to
maintain
this atomic type so it is also available to skeleton. But I think for
skeleton
a raw type might be good enough unless user space intends to do some
atomic
operation with that, which is a unlikely case.
    
So I choose choice (1) in this RFC implementation. See the commit
message of the second commit for details.

[1]
https://lore.kernel.org/bpf/7b941f53-2a05-48ec-9032-8f106face3a3@linux.dev/
 [2] https://dwarfstd.org/issues/131112.1.html

---------

When BPF object files are linked with bpftool, every symbol must be
accompanied by BTF info. Ensure that extern functions referenced by
global variable initializers are included in BTF.

The primary motivation is "static" initialization of PROG maps:

```c
extern int elsewhere(struct xdp_md *);

struct {
  __uint(type, BPF_MAP_TYPE_PROG_ARRAY);
  __uint(max_entries, 1);
  __type(key, int);
  __type(value, int);
  __array(values, int (struct xdp_md *));
} prog_map SEC(".maps") = { .values = { elsewhere } };
```

BPF backend needs debug info to produce BTF. Debug info is not
normally generated for external variables and functions. Previously, it
was solved differently for variables (collecting variable declarations
    in ExternalDeclarations vector) and functions (logic invoked during
    codegen in CGExpr.cpp).

This patch generalises ExternalDefclarations to include both function
and variable declarations. This change ensures that function references
    are not missed no matter the context. Previously external functions
    referenced in constant expressions lacked debug info.