Re: [PATCH bpf-next 06/11] bpf: Find btf_field with the knowledge of arrays.

[Eduard Zingerman <eddyz87@gmail.com>]

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@gmail.com>
> ---
>  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;