[bpf-next,v3,4/7] bpf: look into the types of the fields of a struct type recursively.

Commit Message

Kui-Feng Lee May 1, 2024, 8:47 p.m. UTC

The verifier has field information for specific special types, such as
kptr, rbtree root, and list head. These types are handled
differently. However, we did not previously examine the types of fields of
a struct type variable. Field information records were not generated for
the kptrs, rbtree roots, and linked_list heads that are not located at the
outermost struct type of a variable.

For example,

  struct A {
    struct task_struct __kptr * task;
  };

  struct B {
    struct A mem_a;
  }

  struct B var_b;

It did not examine "struct A" so as not to generate field information for
the kptr in "struct A" for "var_b".

This patch enables BPF programs to define fields of these special types in
a struct type other than the direct type of a variable or in a struct type
that is the type of a field in the value type of a map.

Signed-off-by: Kui-Feng Lee <[e-mail]>
---
 kernel/bpf/btf.c | 118 +++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 98 insertions(+), 20 deletions(-)

Comments

Eduard Zingerman May 2, 2024, 7:34 p.m. UTC | #1

On Wed, 2024-05-01 at 13:47 -0700, Kui-Feng Lee wrote:
> The verifier has field information for specific special types, such as
> kptr, rbtree root, and list head. These types are handled
> differently. However, we did not previously examine the types of fields of
> a struct type variable. Field information records were not generated for
> the kptrs, rbtree roots, and linked_list heads that are not located at the
> outermost struct type of a variable.
> 
> For example,
> 
>   struct A {
>     struct task_struct __kptr * task;
>   };
> 
>   struct B {
>     struct A mem_a;
>   }
> 
>   struct B var_b;
> 
> It did not examine "struct A" so as not to generate field information for
> the kptr in "struct A" for "var_b".
> 
> This patch enables BPF programs to define fields of these special types in
> a struct type other than the direct type of a variable or in a struct type
> that is the type of a field in the value type of a map.
> 
> Signed-off-by: Kui-Feng Lee <[e-mail]>
> ---

I think that the main logic of this commit is fine.
A few nitpicks about code organization below.

>  kernel/bpf/btf.c | 118 +++++++++++++++++++++++++++++++++++++++--------
>  1 file changed, 98 insertions(+), 20 deletions(-)
> 
> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index 4a78cd28fab0..2ceff77b7e71 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -3493,41 +3493,83 @@ static int btf_get_field_type(const char *name, u32 field_mask, u32 *seen_mask,

[...]

> +static int btf_find_struct_field(const struct btf *btf,
> +				 const struct btf_type *t, u32 field_mask,
> +				 struct btf_field_info *info, int info_cnt);
> +
> +/* Find special fields in the struct type of a field.
> + *
> + * This function is used to find fields of special types that is not a
> + * global variable or a direct field of a struct type. It also handles the
> + * repetition if it is the element type of an array.
> + */
> +static int btf_find_nested_struct(const struct btf *btf, const struct btf_type *t,
> +				  u32 off, u32 nelems,
> +				  u32 field_mask, struct btf_field_info *info,
> +				  int info_cnt)
> +{
> +	int ret, err, i;
> +
> +	ret = btf_find_struct_field(btf, t, field_mask, info, info_cnt);

btf_find_nested_struct() and btf_find_struct_field() are mutually recursive,
as far as I can see this is usually avoided in kernel source.
Would it be possible to make stack explicit or limit traversal depth here?
The 'info_cnt' field won't work as it could be unchanged in
btf_find_struct_field() if 'idx == 0'.

> +
> +	if (ret <= 0)
> +		return ret;
> +
> +	/* Shift the offsets of the nested struct fields to the offsets
> +	 * related to the container.
> +	 */
> +	for (i = 0; i < ret; i++)
> +		info[i].off += off;
> +
> +	if (nelems > 1) {
> +		err = btf_repeat_fields(info, 0, ret, nelems - 1, t->size);
> +		if (err == 0)
> +			ret *= nelems;
> +		else
> +			ret = err;
> +	}
> +
> +	return ret;
> +}
> +
>  static int btf_find_struct_field(const struct btf *btf,
>  				 const struct btf_type *t, u32 field_mask,
>  				 struct btf_field_info *info, int info_cnt)

[...]

> @@ -3644,6 +3707,21 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
>  
>  		field_type = btf_get_field_type(__btf_name_by_offset(btf, var_type->name_off),
>  						field_mask, &seen_mask, &align, &sz);

Actions taken for members in btf_find_datasec_var() and
btf_find_struct_field() are almost identical, would it be possible to
add a refactoring commit this patch-set so that common logic is moved
to a separate function? It looks like this function would have to be
parameterized only by member size and offset.

> +		/* Look into variables of struct types */
> +		if ((field_type == BPF_KPTR_REF || !field_type) &&
> +		    __btf_type_is_struct(var_type)) {
> +			sz = var_type->size;
> +			if (vsi->size != sz * nelems)
> +				continue;
> +			off = vsi->offset;
> +			ret = btf_find_nested_struct(btf, var_type, off, nelems, field_mask,
> +						     &info[idx], info_cnt - idx);
> +			if (ret < 0)
> +				return ret;
> +			idx += ret;
> +			continue;
> +		}
> +
>  		if (field_type == 0)
>  			continue;
>  		if (field_type < 0)

[...]

Kui-Feng Lee May 3, 2024, 6:07 p.m. UTC | #2

On 5/2/24 12:34, Eduard Zingerman wrote:
> On Wed, 2024-05-01 at 13:47 -0700, Kui-Feng Lee wrote:
>> The verifier has field information for specific special types, such as
>> kptr, rbtree root, and list head. These types are handled
>> differently. However, we did not previously examine the types of fields of
>> a struct type variable. Field information records were not generated for
>> the kptrs, rbtree roots, and linked_list heads that are not located at the
>> outermost struct type of a variable.
>>
>> For example,
>>
>>    struct A {
>>      struct task_struct __kptr * task;
>>    };
>>
>>    struct B {
>>      struct A mem_a;
>>    }
>>
>>    struct B var_b;
>>
>> It did not examine "struct A" so as not to generate field information for
>> the kptr in "struct A" for "var_b".
>>
>> This patch enables BPF programs to define fields of these special types in
>> a struct type other than the direct type of a variable or in a struct type
>> that is the type of a field in the value type of a map.
>>
>> Signed-off-by: Kui-Feng Lee <[e-mail]>
>> ---
> 
> I think that the main logic of this commit is fine.
> A few nitpicks about code organization below.
> 
>>   kernel/bpf/btf.c | 118 +++++++++++++++++++++++++++++++++++++++--------
>>   1 file changed, 98 insertions(+), 20 deletions(-)
>>
>> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
>> index 4a78cd28fab0..2ceff77b7e71 100644
>> --- a/kernel/bpf/btf.c
>> +++ b/kernel/bpf/btf.c
>> @@ -3493,41 +3493,83 @@ static int btf_get_field_type(const char *name, u32 field_mask, u32 *seen_mask,
> 
> [...]
> 
>> +static int btf_find_struct_field(const struct btf *btf,
>> +				 const struct btf_type *t, u32 field_mask,
>> +				 struct btf_field_info *info, int info_cnt);
>> +
>> +/* Find special fields in the struct type of a field.
>> + *
>> + * This function is used to find fields of special types that is not a
>> + * global variable or a direct field of a struct type. It also handles the
>> + * repetition if it is the element type of an array.
>> + */
>> +static int btf_find_nested_struct(const struct btf *btf, const struct btf_type *t,
>> +				  u32 off, u32 nelems,
>> +				  u32 field_mask, struct btf_field_info *info,
>> +				  int info_cnt)
>> +{
>> +	int ret, err, i;
>> +
>> +	ret = btf_find_struct_field(btf, t, field_mask, info, info_cnt);
> 
> btf_find_nested_struct() and btf_find_struct_field() are mutually recursive,
> as far as I can see this is usually avoided in kernel source.
> Would it be possible to make stack explicit or limit traversal depth here?

Sure!

> The 'info_cnt' field won't work as it could be unchanged in
> btf_find_struct_field() if 'idx == 0'
> 
>> +
>> +	if (ret <= 0)
>> +		return ret;
>> +
>> +	/* Shift the offsets of the nested struct fields to the offsets
>> +	 * related to the container.
>> +	 */
>> +	for (i = 0; i < ret; i++)
>> +		info[i].off += off;
>> +
>> +	if (nelems > 1) {
>> +		err = btf_repeat_fields(info, 0, ret, nelems - 1, t->size);
>> +		if (err == 0)
>> +			ret *= nelems;
>> +		else
>> +			ret = err;
>> +	}
>> +
>> +	return ret;
>> +}
>> +
>>   static int btf_find_struct_field(const struct btf *btf,
>>   				 const struct btf_type *t, u32 field_mask,
>>   				 struct btf_field_info *info, int info_cnt)
> 
> [...]
> 
>> @@ -3644,6 +3707,21 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
>>   
>>   		field_type = btf_get_field_type(__btf_name_by_offset(btf, var_type->name_off),
>>   						field_mask, &seen_mask, &align, &sz);
> 
> Actions taken for members in btf_find_datasec_var() and
> btf_find_struct_field() are almost identical, would it be possible to
> add a refactoring commit this patch-set so that common logic is moved
> to a separate function? It looks like this function would have to be
> parameterized only by member size and offset.

Of course, it could be.

> 
>> +		/* Look into variables of struct types */
>> +		if ((field_type == BPF_KPTR_REF || !field_type) &&
>> +		    __btf_type_is_struct(var_type)) {
>> +			sz = var_type->size;
>> +			if (vsi->size != sz * nelems)
>> +				continue;
>> +			off = vsi->offset;
>> +			ret = btf_find_nested_struct(btf, var_type, off, nelems, field_mask,
>> +						     &info[idx], info_cnt - idx);
>> +			if (ret < 0)
>> +				return ret;
>> +			idx += ret;
>> +			continue;
>> +		}
>> +
>>   		if (field_type == 0)
>>   			continue;
>>   		if (field_type < 0)
> 
> [...]

Patch

diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 4a78cd28fab0..2ceff77b7e71 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -3493,41 +3493,83 @@  static int btf_get_field_type(const char *name, u32 field_mask, u32 *seen_mask,
 
 #undef field_mask_test_name
 
-/* Repeat a field for a specified number of times.
+/* Repeat a number of fields for a specified number of times.
  *
- * Copy and repeat a field for repeat_cnt
- * times. The field is repeated by adding the offset of each field
+ * Copy the fields starting from first_field and repeat them for repeat_cnt
+ * times. The fields are repeated by adding the offset of each field
  * with
  *   (i + 1) * elem_size
  * where i is the repeat index and elem_size is the size of the element.
  */
-static int btf_repeat_field(struct btf_field_info *info, u32 field,
-			    u32 repeat_cnt, u32 elem_size)
+static int btf_repeat_fields(struct btf_field_info *info, u32 first_field,
+			     u32 field_cnt, u32 repeat_cnt, u32 elem_size)
 {
-	u32 i;
+	u32 i, j;
 	u32 cur;
 
 	/* Ensure not repeating fields that should not be repeated. */
-	switch (info[field].type) {
-	case BPF_KPTR_UNREF:
-	case BPF_KPTR_REF:
-	case BPF_KPTR_PERCPU:
-	case BPF_LIST_HEAD:
-	case BPF_RB_ROOT:
-		break;
-	default:
-		return -EINVAL;
+	for (i = 0; i < field_cnt; i++) {
+		switch (info[first_field + i].type) {
+		case BPF_KPTR_UNREF:
+		case BPF_KPTR_REF:
+		case BPF_KPTR_PERCPU:
+		case BPF_LIST_HEAD:
+		case BPF_RB_ROOT:
+			break;
+		default:
+			return -EINVAL;
+		}
 	}
 
-	cur = field + 1;
+	cur = first_field + field_cnt;
 	for (i = 0; i < repeat_cnt; i++) {
-		memcpy(&info[cur], &info[field], sizeof(info[0]));
-		info[cur++].off += (i + 1) * elem_size;
+		memcpy(&info[cur], &info[first_field], field_cnt * sizeof(info[0]));
+		for (j = 0; j < field_cnt; j++)
+			info[cur++].off += (i + 1) * elem_size;
 	}
 
 	return 0;
 }
 
+static int btf_find_struct_field(const struct btf *btf,
+				 const struct btf_type *t, u32 field_mask,
+				 struct btf_field_info *info, int info_cnt);
+
+/* Find special fields in the struct type of a field.
+ *
+ * This function is used to find fields of special types that is not a
+ * global variable or a direct field of a struct type. It also handles the
+ * repetition if it is the element type of an array.
+ */
+static int btf_find_nested_struct(const struct btf *btf, const struct btf_type *t,
+				  u32 off, u32 nelems,
+				  u32 field_mask, struct btf_field_info *info,
+				  int info_cnt)
+{
+	int ret, err, i;
+
+	ret = btf_find_struct_field(btf, t, field_mask, info, info_cnt);
+
+	if (ret <= 0)
+		return ret;
+
+	/* Shift the offsets of the nested struct fields to the offsets
+	 * related to the container.
+	 */
+	for (i = 0; i < ret; i++)
+		info[i].off += off;
+
+	if (nelems > 1) {
+		err = btf_repeat_fields(info, 0, ret, nelems - 1, t->size);
+		if (err == 0)
+			ret *= nelems;
+		else
+			ret = err;
+	}
+
+	return ret;
+}
+
 static int btf_find_struct_field(const struct btf *btf,
 				 const struct btf_type *t, u32 field_mask,
 				 struct btf_field_info *info, int info_cnt)
@@ -3556,6 +3598,27 @@  static int btf_find_struct_field(const struct btf *btf,
 
 		field_type = btf_get_field_type(__btf_name_by_offset(btf, member_type->name_off),
 						field_mask, &seen_mask, &align, &sz);
+		/* Look into fields of struct types */
+		if ((field_type == BPF_KPTR_REF || !field_type) &&
+		    __btf_type_is_struct(member_type)) {
+			/* For field_type == BPF_KPTR_REF, it is not
+			 * necessary a kptr type. It can also be other
+			 * types not special types handled here. However,
+			 * it can not be a struct type if it is a kptr.
+			 */
+			off = __btf_member_bit_offset(t, member);
+			if (off % 8)
+				/* valid C code cannot generate such BTF */
+				return -EINVAL;
+			off /= 8;
+			ret = btf_find_nested_struct(btf, member_type, off, nelems, field_mask,
+						     &info[idx], info_cnt - idx);
+			if (ret < 0)
+				return ret;
+			idx += ret;
+			continue;
+		}
+
 		if (field_type == 0)
 			continue;
 		if (field_type < 0)
@@ -3607,7 +3670,7 @@  static int btf_find_struct_field(const struct btf *btf,
 		if (idx + nelems > info_cnt)
 			return -E2BIG;
 		if (nelems > 1) {
-			ret = btf_repeat_field(info, idx, nelems - 1, sz);
+			ret = btf_repeat_fields(info, idx, 1, nelems - 1, sz);
 			if (ret < 0)
 				return ret;
 		}
@@ -3644,6 +3707,21 @@  static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 
 		field_type = btf_get_field_type(__btf_name_by_offset(btf, var_type->name_off),
 						field_mask, &seen_mask, &align, &sz);
+		/* Look into variables of struct types */
+		if ((field_type == BPF_KPTR_REF || !field_type) &&
+		    __btf_type_is_struct(var_type)) {
+			sz = var_type->size;
+			if (vsi->size != sz * nelems)
+				continue;
+			off = vsi->offset;
+			ret = btf_find_nested_struct(btf, var_type, off, nelems, field_mask,
+						     &info[idx], info_cnt - idx);
+			if (ret < 0)
+				return ret;
+			idx += ret;
+			continue;
+		}
+
 		if (field_type == 0)
 			continue;
 		if (field_type < 0)
@@ -3693,7 +3771,7 @@  static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 		if (idx + nelems > info_cnt)
 			return -E2BIG;
 		if (nelems > 1) {
-			ret = btf_repeat_field(info, idx, nelems - 1, sz);
+			ret = btf_repeat_fields(info, idx, 1, nelems - 1, sz);
 			if (ret < 0)
 				return ret;
 		}