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

Commit Message

Kui-Feng Lee April 10, 2024, 12:41 a.m. UTC

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 <[e-mail]>
---
 kernel/bpf/syscall.c | 19 +++++++++++++++----
 1 file changed, 15 insertions(+), 4 deletions(-)

Comments

Eduard Zingerman April 11, 2024, 10:14 p.m. UTC | #1

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 <[e-mail]>
> ---
>  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;

Kui-Feng Lee April 12, 2024, 2 a.m. UTC | #2

On 4/11/24 15:14, Eduard Zingerman wrote:
> 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 <[e-mail]>
>> ---
>>   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).

Ok! It will match the leftmost one overlapping with the offset. And
check if the offset aligning with one of the elements in btf_record_find().

> 
>>   	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;
> 
>

Patch

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;
 	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;