[PATCH bpf-next v2 00/11] Enable BPF programs to declare arrays of kptr, bpf_rb_root, and bpf_list_head.

[Kui-Feng Lee <thinker.li@gmail.com>]

The arrays of kptr, bpf_rb_root, and bpf_list_head didn't work as
global variables. This was due to these types being initialized and
verified in a special manner in the kernel. This patchset allows BPF
programs to declare arrays of kptr, bpf_rb_root, and bpf_list_head in
the global namespace.

The main change is to add "nelems" to btf_fields. The value of
"nelems" represents the number of elements in the array if a btf_field
represents an array. Otherwise, "nelem" will be 1. The verifier
verifies these types based on the information provided by the
btf_field.

The value of "size" will be the size of the entire array if a
btf_field represents an array. Dividing "size" by "nelems" gives the
size of an element. The value of "offset" will be the offset of the
beginning for an array. By putting this together, we can determine the
offset of each element in an array. For example,

    struct bpf_cpumask __kptr * global_mask_array[2];

the statement above indicates that there is an array containing two
kptr(s). The "size" specified in the corresponding 'btf_field' will be
"16" (the size of the array), and "nelems" will be "2". If the
"offset" of the 'btf_field' is 0xff00 from the beginning of the data
section, the first kptr is at 0xff00, and the second kptr is at
0xff08.

All arrays are flattened to get the value of "nelems". For example,

    struct bpf_cpumask __kptr * global_mask_array[2][3];

the above array will be flattened to a one dimension array having six
elements.

---
Changes from v1:

 - Move the check of element alignment out of btf_field_cmp() to
   btf_record_find().

 - Change the order of the previous patch 4 "bpf:
   check_map_kptr_access() compute the offset from the reg state" as
   the patch 7 now.

 - Reject BPF_RB_NODE and BPF_LIST_NODE with nelems > 1.

 - Rephrase the commit log of the patch "bpf: check_map_access() with
   the knowledge of arrays" to clarify the alignment on elements.

v1: https://lore.kernel.org/bpf/20240410004150.2917641-1-thinker.li@gmail.com/

Kui-Feng Lee (11):
  bpf: Remove unnecessary checks on the offset of btf_field.
  bpf: Remove unnecessary call to btf_field_type_size().
  bpf: Add nelems to struct btf_field_info and btf_field.
  bpf: initialize/free array of btf_field(s).
  bpf: Find btf_field with the knowledge of arrays.
  bpf: check_map_access() with the knowledge of arrays.
  bpf: check_map_kptr_access() compute the offset from the reg state.
  bpf: Enable and verify btf_field arrays.
  selftests/bpf: Test global kptr arrays.
  selftests/bpf: Test global bpf_rb_root arrays.
  selftests/bpf: Test global bpf_list_head arrays.

 include/linux/bpf.h                           |   8 +
 kernel/bpf/btf.c                              |  28 +++-
 kernel/bpf/syscall.c                          |  59 ++++---
 kernel/bpf/verifier.c                         |  26 ++--
 .../selftests/bpf/prog_tests/cpumask.c        |   3 +
 .../selftests/bpf/prog_tests/linked_list.c    |   6 +
 .../testing/selftests/bpf/prog_tests/rbtree.c |  23 +++
 .../selftests/bpf/progs/cpumask_success.c     | 147 ++++++++++++++++++
 .../testing/selftests/bpf/progs/linked_list.c |  24 +++
 tools/testing/selftests/bpf/progs/rbtree.c    |  63 ++++++++
 10 files changed, 353 insertions(+), 34 deletions(-)

-- 
2.34.1