On Tue, 2024-04-09 at 17:41 -0700, Kui-Feng Lee wrote:
> Make btf_record_find() find the btf_field for an offset by comparing the
> offset with the offset of each element, rather than the offset of the
> entire array, if a btf_field represents an array. It is important to have
> support for btf_field arrays in the future.
>
> Signed-off-by: Kui-Feng Lee <thinker.li@xxxxxxxxx>
> ---
> kernel/bpf/syscall.c | 19 +++++++++++++++----
> 1 file changed, 15 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
> index 543ff0d944e8..1a37731e632a 100644
> --- a/kernel/bpf/syscall.c
> +++ b/kernel/bpf/syscall.c
> @@ -516,11 +516,18 @@ int bpf_map_alloc_pages(const struct bpf_map *map, gfp_t gfp, int nid,
> static int btf_field_cmp(const void *a, const void *b)
> {
> const struct btf_field *f1 = a, *f2 = b;
> + int gt = 1, lt = -1;
>
> + if (f2->nelems == 0) {
> + swap(f1, f2);
> + swap(gt, lt);
> + }
> if (f1->offset < f2->offset)
> - return -1;
> - else if (f1->offset > f2->offset)
> - return 1;
> + return lt;
> + else if (f1->offset >= f2->offset + f2->size)
> + return gt;
> + if ((f1->offset - f2->offset) % (f2->size / f2->nelems))
> + return gt;
Binary search requires elements to be sorted in non-decreasing order,
however usage of '%' breaks this requirement. E.g. consider an array
with element size equal to 3:
| elem #0 | elem #1 |
| 0 | 1 | 2 | 3 | 4 | 5 |
^ ^ ^
' ' '
f2 f1 f1'
Here f1 > f2, but f1' == f2, while f1' > f1.
Depending on whether or not fields can overlap this might not be a problem,
but I suggest to rework the comparison function to avoid this confusion.
(E.g., find the leftmost field that overlaps with offset being searched for).
> return 0;
> }
>
> @@ -528,10 +535,14 @@ struct btf_field *btf_record_find(const struct btf_record *rec, u32 offset,
> u32 field_mask)
> {
> struct btf_field *field;
> + struct btf_field key = {
> + .offset = offset,
> + .size = 0, /* as a label for this key */
> + };
>
> if (IS_ERR_OR_NULL(rec) || !(rec->field_mask & field_mask))
> return NULL;
> - field = bsearch(&offset, rec->fields, rec->cnt, sizeof(rec->fields[0]), btf_field_cmp);
> + field = bsearch(&key, rec->fields, rec->cnt, sizeof(rec->fields[0]), btf_field_cmp);
> if (!field || !(field->type & field_mask))
> return NULL;
> return field;
