Skip to contentSkip to conversation

Enable BPF programs to declare arrays of kptr, bpf_rb_root, and bpf_list_head.

PATCH Superseded Kui-Feng Lee 3 participants 13 messages May 1, 2024 – May 3, 2024

Subsystems (4)

v3 of 7 Superseded Latest is v7 →

lore
Share & tools
lore
#0 lore raw

v3 cover Enable BPF programs to declare arrays of kptr, bpf_rb_root, and bpf_list_head.

Some types, such as type kptr, bpf_rb_root, and bpf_list_head, are treated in a special way. Previously, these types could not be the type of a field in a struct type that is used as the type of a global variable. They could not be the type of a field in a struct type that is used as the type of a field in the value type of a map either. They could not even be the type of array elements. This means that they can only be the type of global variables or of direct fields in the value type of a map.

The patch set aims to enable the use of these specific types in arrays and struct fields, providing flexibility. It examines the types of global variables or the value types of maps, such as arrays and struct types, recursively to identify these special types and generate field information for them.

For example,

  ...
  struct task_struct __kptr *ptr[3];
  ...

it will create 3 instances of "struct btf_field" in the "btf_record" of the data section.

[...,
btf_field(offset=0x100, type=BPF_KPTR_REF),
btf_field(offset=0x108, type=BPF_KPTR_REF),
btf_field(offset=0x110, type=BPF_KPTR_REF),
...
]

It creates a record of each of three elements. These three records are almost identical except their offsets.

Another example is

  ...
  struct A {
    ...
    struct task_struct __kptr *task;
    struct bpf_rb_root root;
    ...
  }

  struct A foo[2];

it will create 4 records.

[...,
btf_field(offset=0x7100, type=BPF_KPTR_REF),
btf_field(offset=0x7108, type=BPF_RB_ROOT:),
btf_field(offset=0x7200, type=BPF_KPTR_REF),
btf_field(offset=0x7208, type=BPF_RB_ROOT:),
...
]

Assuming that the size of an element/struct A is 0x100 and "foo" starts at 0x7000, it includes two kptr records at 0x7100 and 0x7200, and two rbtree root records at 0x7108 and 0x7208.

All these field information will be flatten, for struct types, and repeated, for arrays.

---
Changes from v2:

- Support fields in nested struct type.

- Remove nelems and duplicate field information with offset adjustments for arrays.

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.

v2: https://lore.kernel.org/all/[email protected]/
v1: https://lore.kernel.org/bpf/[email protected]/

Kui-Feng Lee (7):
bpf: Remove unnecessary checks on the offset of btf_field.
bpf: Remove unnecessary call to btf_field_type_size().
bpf: create repeated fields for arrays.
bpf: look into the types of the fields of a struct type recursively. selftests/bpf: Test kptr arrays and kptrs in nested struct fields. selftests/bpf: Test global bpf_rb_root arrays and fields in nested
struct types.
selftests/bpf: Test global bpf_list_head arrays.

 kernel/bpf/btf.c                              | 161 +++++++++++++++++-
 kernel/bpf/verifier.c                         |   4 +-
 .../selftests/bpf/prog_tests/cpumask.c        |   5 +
 .../selftests/bpf/prog_tests/linked_list.c    |  12 ++
 .../testing/selftests/bpf/prog_tests/rbtree.c |  47 +++++
 .../selftests/bpf/progs/cpumask_success.c     | 133 +++++++++++++++
 .../testing/selftests/bpf/progs/linked_list.c |  42 +++++
 tools/testing/selftests/bpf/progs/rbtree.c    |  77 +++++++++
 8 files changed, 473 insertions(+), 8 deletions(-)
Signature · 1 line
2.34.1
#1 lore raw

PATCH v3 1/7 bpf: Remove unnecessary checks on the offset of btf_field.

reg_find_field_offset() always return a btf_field with a matching offset value. Checking the offset of the returned btf_field is unnecessary.

---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
index 5d42db05315e..86d20433c10d 100644
@@ -11638,7 +11638,7 @@ __process_kf_arg_ptr_to_graph_node(struct bpf_verifier_env *env,
 
 	node_off = reg->off + reg->var_off.value;
 	field = reg_find_field_offset(reg, node_off, node_field_type);
-	if (!field || field->offset != node_off) {
+	if (!field) {
 		verbose(env, "%s not found at offset=%u\n", node_type_name, node_off);
 		return -EINVAL;
 	}
Signature · 1 line
2.34.1
#2 lore raw

PATCH v3 2/7 bpf: Remove unnecessary call to btf_field_type_size().

In reply to Kui-Feng Lee

field->size has been initialized by bpf_parse_fields() with the value returned by btf_field_type_size(). Use it instead of calling btf_field_type_size() again.

---
 kernel/bpf/btf.c      | 2 +-
 kernel/bpf/verifier.c | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)
kernel/bpf/btf.c +1 -1
index 8291fbfd27b1..d4c3342e2027 100644
@@ -6692,7 +6692,7 @@ int btf_struct_access(struct bpf_verifier_log *log,
 		for (i = 0; i < rec->cnt; i++) {
 			struct btf_field *field = &rec->fields[i];
 			u32 offset = field->offset;
-			if (off < offset + btf_field_type_size(field->type) && offset < off + size) {
+			if (off < offset + field->size && offset < off + size) {
 				bpf_log(log,
 					"direct access to %s is disallowed\n",
 					btf_field_type_name(field->type));
kernel/bpf/verifier.c +1 -1
index 86d20433c10d..43144a6be45c 100644
@@ -5448,7 +5448,7 @@ static int check_map_access(struct bpf_verifier_env *env, u32 regno,
 		 * this program. To check that [x1, x2) overlaps with [y1, y2),
 		 * it is sufficient to check x1 < y2 && y1 < x2.
 		 */
-		if (reg->smin_value + off < p + btf_field_type_size(field->type) &&
+		if (reg->smin_value + off < p + field->size &&
 		    p < reg->umax_value + off + size) {
 			switch (field->type) {
 			case BPF_KPTR_UNREF:
Signature · 1 line
2.34.1
#3 lore raw

PATCH v3 3/7 bpf: create repeated fields for arrays.

In reply to Kui-Feng Lee

The verifier uses field information for certain special types, such as kptr, rbtree root, and list head. These types are treated differently. However, we did not previously support these types in arrays. This update examines arrays and duplicates field information the same number of times as the length of the array if the element type is one of the special types.

---
 kernel/bpf/btf.c | 81 +++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 76 insertions(+), 5 deletions(-)
kernel/bpf/btf.c +76 -5
index d4c3342e2027..4a78cd28fab0 100644
@@ -3493,6 +3493,41 @@ 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.
+ *
+ * Copy and repeat a field for repeat_cnt
+ * times. The field is 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)
+{
+	u32 i;
+	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;
+	}
+
+	cur = field + 1;
+	for (i = 0; i < repeat_cnt; i++) {
+		memcpy(&info[cur], &info[field], sizeof(info[0]));
+		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)
@@ -3505,6 +3540,19 @@ static int btf_find_struct_field(const struct btf *btf,
 	for_each_member(i, t, member) {
 		const struct btf_type *member_type = btf_type_by_id(btf,
 								    member->type);
+		const struct btf_array *array;
+		u32 j, nelems = 1;
+
+		/* Walk into array types to find the element type and the
+		 * number of elements in the (flattened) array.
+		 */
+		for (j = 0; j < MAX_RESOLVE_DEPTH && btf_type_is_array(member_type); j++) {
+			array = btf_array(member_type);
+			nelems *= array->nelems;
+			member_type = btf_type_by_id(btf, array->type);
+		}
+		if (nelems == 0)
+			continue;
 
 		field_type = btf_get_field_type(__btf_name_by_offset(btf, member_type->name_off),
 						field_mask, &seen_mask, &align, &sz);
@@ -3556,9 +3604,14 @@ static int btf_find_struct_field(const struct btf *btf,
 
 		if (ret == BTF_FIELD_IGNORE)
 			continue;
-		if (idx >= info_cnt)
+		if (idx + nelems > info_cnt)
 			return -E2BIG;
-		++idx;
+		if (nelems > 1) {
+			ret = btf_repeat_field(info, idx, nelems - 1, sz);
+			if (ret < 0)
+				return ret;
+		}
+		idx += nelems;
 	}
 	return idx;
 }
@@ -3575,6 +3628,19 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 	for_each_vsi(i, t, vsi) {
 		const struct btf_type *var = btf_type_by_id(btf, vsi->type);
 		const struct btf_type *var_type = btf_type_by_id(btf, var->type);
+		const struct btf_array *array;
+		u32 j, nelems = 1;
+
+		/* Walk into array types to find the element type and the
+		 * number of elements in the (flattened) array.
+		 */
+		for (j = 0; j < MAX_RESOLVE_DEPTH && btf_type_is_array(var_type); j++) {
+			array = btf_array(var_type);
+			nelems *= array->nelems;
+			var_type = btf_type_by_id(btf, array->type);
+		}
+		if (nelems == 0)
+			continue;
 
 		field_type = btf_get_field_type(__btf_name_by_offset(btf, var_type->name_off),
 						field_mask, &seen_mask, &align, &sz);
@@ -3584,7 +3650,7 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 			return field_type;
 
 		off = vsi->offset;
-		if (vsi->size != sz)
+		if (vsi->size != sz * nelems)
 			continue;
 		if (off % align)
 			continue;
@@ -3624,9 +3690,14 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 
 		if (ret == BTF_FIELD_IGNORE)
 			continue;
-		if (idx >= info_cnt)
+		if (idx + nelems > info_cnt)
 			return -E2BIG;
-		++idx;
+		if (nelems > 1) {
+			ret = btf_repeat_field(info, idx, nelems - 1, sz);
+			if (ret < 0)
+				return ret;
+		}
+		idx += nelems;
 	}
 	return idx;
 }
Signature · 1 line
2.34.1
maintainer
#4 lore raw

Re: [PATCH bpf-next v3 3/7] bpf: create repeated fields for arrays.

On Wed, 2024-05-01 at 13:47 -0700, Kui-Feng Lee wrote:

I think this looks good for repeating fields of nested arrays (w/o visiting nested structures), two nits below.

Quoted 7 lines
kernel/bpf/btf.c +3 -0
@@ -3575,6 +3628,19 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 	for_each_vsi(i, t, vsi) {
 		const struct btf_type *var = btf_type_by_id(btf, vsi->type);
 		const struct btf_type *var_type = btf_type_by_id(btf, var->type);
+		const struct btf_array *array;
+		u32 j, nelems = 1;
+

kernel/bpf/btf.c static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t, · line 3643

Quoted 10 lines
kernel/bpf/btf.c +10 -0
+		/* Walk into array types to find the element type and the
+		 * number of elements in the (flattened) array.
+		 */
+		for (j = 0; j < MAX_RESOLVE_DEPTH && btf_type_is_array(var_type); j++) {
+			array = btf_array(var_type);
+			nelems *= array->nelems;
+			var_type = btf_type_by_id(btf, array->type);
+		}
+		if (nelems == 0)
+			continue;

Nit: Should this return an error if j == MAX_RESOLVE_DEPTH after the loop?

Quoted 13 lines
kernel/bpf/btf.c +1 -1
 		field_type = btf_get_field_type(__btf_name_by_offset(btf, var_type->name_off),
 						field_mask, &seen_mask, &align, &sz);
@@ -3584,7 +3650,7 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 			return field_type;
 
 		off = vsi->offset;
-		if (vsi->size != sz)
+		if (vsi->size != sz * nelems)
 			continue;
 		if (off % align)
 			continue;

kernel/bpf/btf.c static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t, · line 3694

Quoted 6 lines
kernel/bpf/btf.c +1 -1
@@ -3624,9 +3690,14 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 
 		if (ret == BTF_FIELD_IGNORE)
 			continue;
-		if (idx >= info_cnt)
+		if (idx + nelems > info_cnt)
 			return -E2BIG;

Nit: This is bounded by BTF_FIELDS_MAX which has value of 11,
would that be enough?

Quoted 10 lines
kernel/bpf/btf.c +6 -1
-		++idx;
+		if (nelems > 1) {
+			ret = btf_repeat_field(info, idx, nelems - 1, sz);
+			if (ret < 0)
+				return ret;
+		}
+		idx += nelems;
 	}
 	return idx;
 }
#5 lore raw

Re: [PATCH bpf-next v3 3/7] bpf: create repeated fields for arrays.

Quoted 16 lines · Eduard Zingerman

On Wed, 2024-05-01 at 13:47 -0700, Kui-Feng Lee wrote:

I think this looks good for repeating fields of nested arrays (w/o visiting nested structures), two nits below.

Quoted 11 lines
kernel/bpf/btf.c +7 -0
@@ -3575,6 +3628,19 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
  	for_each_vsi(i, t, vsi) {
  		const struct btf_type *var = btf_type_by_id(btf, vsi->type);
  		const struct btf_type *var_type = btf_type_by_id(btf, var->type);
+		const struct btf_array *array;
+		u32 j, nelems = 1;
+
+		/* Walk into array types to find the element type and the
+		 * number of elements in the (flattened) array.
+		 */
+		for (j = 0; j < MAX_RESOLVE_DEPTH && btf_type_is_array(var_type); j++) {
Quoted 8 lines

kernel/bpf/btf.c static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t, · line 3643

Quoted 6 lines
kernel/bpf/btf.c +6 -0
+			array = btf_array(var_type);
+			nelems *= array->nelems;
+			var_type = btf_type_by_id(btf, array->type);
+		}
+		if (nelems == 0)
+			continue;

Nit: Should this return an error if j == MAX_RESOLVE_DEPTH after the loop?

agree

Quoted 15 lines
Quoted 15 lines
kernel/bpf/btf.c +1 -1
  		field_type = btf_get_field_type(__btf_name_by_offset(btf, var_type->name_off),
  						field_mask, &seen_mask, &align, &sz);
@@ -3584,7 +3650,7 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
  			return field_type;
 
  		off = vsi->offset;
-		if (vsi->size != sz)
+		if (vsi->size != sz * nelems)
  			continue;
  		if (off % align)
  			continue;
@@ -3624,9 +3690,14 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 
Quoted 8 lines

kernel/bpf/btf.c static int btf_find_struct_field(const struct btf *btf, · line 3608

Quoted 5 lines
kernel/bpf/btf.c +1 -1
  		if (ret == BTF_FIELD_IGNORE)
  			continue;
-		if (idx >= info_cnt)
+		if (idx + nelems > info_cnt)
  			return -E2BIG;

Nit: This is bounded by BTF_FIELDS_MAX which has value of 11,
would that be enough?

So far, no one has complained it yet!
But, some one will reach the limit in future.
If people want a flexible length, I will solve it in a follow-up. WDYT?

Quoted 13 lines
Quoted 11 lines
kernel/bpf/btf.c +6 -1
-		++idx;
+		if (nelems > 1) {
+			ret = btf_repeat_field(info, idx, nelems - 1, sz);
+			if (ret < 0)
+				return ret;
+		}
+		idx += nelems;
  	}
  	return idx;
  }
maintainer
#6 lore raw

Re: [PATCH bpf-next v3 3/7] bpf: create repeated fields for arrays.

On Fri, 2024-05-03 at 11:02 -0700, Kui-Feng Lee wrote:

[...]

Quoted 11 lines
Quoted 10 lines

kernel/bpf/btf.c static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t, · line 3694

Quoted 7 lines
kernel/bpf/btf.c +1 -1
@@ -3624,9 +3690,14 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 
  		if (ret == BTF_FIELD_IGNORE)
  			continue;
-		if (idx >= info_cnt)
+		if (idx + nelems > info_cnt)
  			return -E2BIG;

Nit: This is bounded by BTF_FIELDS_MAX which has value of 11,
would that be enough?

Quoted 4 lines

So far, no one has complained it yet!
But, some one will reach the limit in future.
If people want a flexible length, I will solve it in a follow-up. WDYT?

Sure, follow-up works.
Just that 11 is not much for an array.
I think sched_ext is the only user for this feature at the moment, so you are in the best position to judge which size is appropriate.

#7 lore raw

PATCH v3 4/7 bpf: look into the types of the fields of a struct type recursively.

In reply to Kui-Feng Lee

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.

---
 kernel/bpf/btf.c | 118 +++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 98 insertions(+), 20 deletions(-)
kernel/bpf/btf.c +98 -20
index 4a78cd28fab0..2ceff77b7e71 100644
@@ -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;
 		}
Signature · 1 line
2.34.1
maintainer
#8 lore raw

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

Quoted 22 lines · Kui-Feng Lee

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".

Quoted 6 lines

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.

---

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

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

[...]

Quoted 8 lines
kernel/bpf/btf.c +8 -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

kernel/bpf/btf.c static int btf_get_field_type(const char *name, u32 field_mask, u32 *seen_mask, · line 3551

Quoted 10 lines
kernel/bpf/btf.c +10 -0
+ * 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'.

Quoted 24 lines
kernel/bpf/btf.c +21 -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)

[...]

kernel/bpf/btf.c static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t, · line 3709

Quoted 4 lines
kernel/bpf/btf.c +0 -0
@@ -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.

Quoted 18 lines
kernel/bpf/btf.c +15 -0
+		/* 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)

[...]

#9 lore raw

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

Quoted 58 lines · Eduard Zingerman
Quoted 22 lines · Kui-Feng Lee

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".

Quoted 6 lines

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.

---

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

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

[...]

Quoted 14 lines
kernel/bpf/btf.c +14 -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)
Quoted 8 lines

kernel/bpf/btf.c static int btf_get_field_type(const char *name, u32 field_mask, u32 *seen_mask, · line 3551

Quoted 4 lines
kernel/bpf/btf.c +4 -0
+{
+	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!

Quoted 32 lines

The 'info_cnt' field won't work as it could be unchanged in btf_find_struct_field() if 'idx == 0'

Quoted 24 lines
kernel/bpf/btf.c +21 -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)

[...]

Quoted 2 lines
kernel/bpf/btf.c +0 -0
@@ -3644,6 +3707,21 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 
Quoted 8 lines

kernel/bpf/btf.c static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t, · line 3709

Quoted 2 lines
kernel/bpf/btf.c +0 -0
  		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.

Quoted 21 lines
Quoted 19 lines
kernel/bpf/btf.c +15 -0
+		/* 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)

[...]

#10 lore raw

PATCH v3 5/7 selftests/bpf: Test kptr arrays and kptrs in nested struct fields.

In reply to Kui-Feng Lee

Make sure that BPF programs can declare global kptr arrays and kptr fields in struct types that is the type of a global variable or the type of a nested descendant field in a global variable.

An array with only one element is special case, that it treats the element like a non-array kptr field. Nested arrays are also tested to ensure they are handled properly.

---
 .../selftests/bpf/prog_tests/cpumask.c        |   5 +
 .../selftests/bpf/progs/cpumask_success.c     | 133 ++++++++++++++++++
 2 files changed, 138 insertions(+)
tools/testing/selftests/bpf/prog_tests/cpumask.c +5 -0
index ecf89df78109..2570bd4b0cb2 100644
@@ -18,6 +18,11 @@ static const char * const cpumask_success_testcases[] = {
 	"test_insert_leave",
 	"test_insert_remove_release",
 	"test_global_mask_rcu",
+	"test_global_mask_array_one_rcu",
+	"test_global_mask_array_rcu",
+	"test_global_mask_array_l2_rcu",
+	"test_global_mask_nested_rcu",
+	"test_global_mask_nested_deep_rcu",
 	"test_cpumask_weight",
 };
 
tools/testing/selftests/bpf/progs/cpumask_success.c +133 -0

145 lines not on this page · raw message

Signature · 1 line
2.34.1
#11 lore raw

PATCH v3 6/7 selftests/bpf: Test global bpf_rb_root arrays and fields in nested struct types.

In reply to Kui-Feng Lee

Make sure global arrays of bpf_rb_root and fields of bpf_rb_root in nested struct types work correctly.

---
 .../testing/selftests/bpf/prog_tests/rbtree.c | 47 +++++++++++
 tools/testing/selftests/bpf/progs/rbtree.c    | 77 +++++++++++++++++++
 2 files changed, 124 insertions(+)
tools/testing/selftests/bpf/prog_tests/rbtree.c +47 -0
index e9300c96607d..9818f06c97c5 100644
@@ -31,6 +31,28 @@ static void test_rbtree_add_nodes(void)
 	rbtree__destroy(skel);
 }
 
+static void test_rbtree_add_nodes_nested(void)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts,
+		    .data_in = &pkt_v4,
+		    .data_size_in = sizeof(pkt_v4),
+		    .repeat = 1,
+	);
+	struct rbtree *skel;
+	int ret;
+
+	skel = rbtree__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "rbtree__open_and_load"))
+		return;
+
+	ret = bpf_prog_test_run_opts(bpf_program__fd(skel->progs.rbtree_add_nodes_nested), &opts);
+	ASSERT_OK(ret, "rbtree_add_nodes_nested run");
+	ASSERT_OK(opts.retval, "rbtree_add_nodes_nested retval");
+	ASSERT_EQ(skel->data->less_callback_ran, 1, "rbtree_add_nodes_nested less_callback_ran");
+
+	rbtree__destroy(skel);
+}
+
 static void test_rbtree_add_and_remove(void)
 {
 	LIBBPF_OPTS(bpf_test_run_opts, opts,
@@ -53,6 +75,27 @@ static void test_rbtree_add_and_remove(void)
 	rbtree__destroy(skel);
 }
 
+static void test_rbtree_add_and_remove_array(void)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts,
+		    .data_in = &pkt_v4,
+		    .data_size_in = sizeof(pkt_v4),
+		    .repeat = 1,
+	);
+	struct rbtree *skel;
+	int ret;
+
+	skel = rbtree__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "rbtree__open_and_load"))
+		return;
+
+	ret = bpf_prog_test_run_opts(bpf_program__fd(skel->progs.rbtree_add_and_remove_array), &opts);
+	ASSERT_OK(ret, "rbtree_add_and_remove_array");
+	ASSERT_OK(opts.retval, "rbtree_add_and_remove_array retval");
+
+	rbtree__destroy(skel);
+}
+
 static void test_rbtree_first_and_remove(void)
 {
 	LIBBPF_OPTS(bpf_test_run_opts, opts,
@@ -104,8 +147,12 @@ void test_rbtree_success(void)
 {
 	if (test__start_subtest("rbtree_add_nodes"))
 		test_rbtree_add_nodes();
+	if (test__start_subtest("rbtree_add_nodes_nested"))
+		test_rbtree_add_nodes_nested();
 	if (test__start_subtest("rbtree_add_and_remove"))
 		test_rbtree_add_and_remove();
+	if (test__start_subtest("rbtree_add_and_remove_array"))
+		test_rbtree_add_and_remove_array();
 	if (test__start_subtest("rbtree_first_and_remove"))
 		test_rbtree_first_and_remove();
 	if (test__start_subtest("rbtree_api_release_aliasing"))
tools/testing/selftests/bpf/progs/rbtree.c +77 -0

101 lines not on this page · raw message

Signature · 1 line
2.34.1
#12 lore raw

PATCH v3 7/7 selftests/bpf: Test global bpf_list_head arrays.

In reply to Kui-Feng Lee

Make sure global arrays of bpf_list_heads and fields of bpf_list_heads in nested struct types work correctly.

---
 .../selftests/bpf/prog_tests/linked_list.c    | 12 ++++++
 .../testing/selftests/bpf/progs/linked_list.c | 42 +++++++++++++++++++
 2 files changed, 54 insertions(+)
tools/testing/selftests/bpf/prog_tests/linked_list.c +12 -0
index 2fb89de63bd2..77d07e0a4a55 100644
@@ -183,6 +183,18 @@ static void test_linked_list_success(int mode, bool leave_in_map)
 	if (!leave_in_map)
 		clear_fields(skel->maps.bss_A);
 
+	ret = bpf_prog_test_run_opts(bpf_program__fd(skel->progs.global_list_push_pop_nested), &opts);
+	ASSERT_OK(ret, "global_list_push_pop_nested");
+	ASSERT_OK(opts.retval, "global_list_push_pop_nested retval");
+	if (!leave_in_map)
+		clear_fields(skel->maps.bss_A);
+
+	ret = bpf_prog_test_run_opts(bpf_program__fd(skel->progs.global_list_array_push_pop), &opts);
+	ASSERT_OK(ret, "global_list_array_push_pop");
+	ASSERT_OK(opts.retval, "global_list_array_push_pop retval");
+	if (!leave_in_map)
+		clear_fields(skel->maps.bss_A);
+
 	if (mode == PUSH_POP)
 		goto end;
 
tools/testing/selftests/bpf/progs/linked_list.c +42 -0

54 lines not on this page · raw message

Signature · 1 line
2.34.1