BPF rbtree next-gen datastructure
Subsystems (5)
v6 cover BPF rbtree next-gen datastructure
This series adds a rbtree datastructure following the "next-gen datastructure" precedent set by recently-added linked-list [0]. This is a reimplementation of previous rbtree RFC [1] to use kfunc + kptr instead of adding a new map type. This series adds a smaller set of API functions than that RFC - just the minimum needed to support current cgfifo example scheduler in ongoing sched_ext effort [2], namely:
bpf_rbtree_add
bpf_rbtree_remove
bpf_rbtree_first
The meat of this series is bugfixes and verifier infra work to support these API functions. Adding more rbtree kfuncs in future patches should be straightforward as a result.
First, the series refactors and extends linked_list's release_on_unlock logic. The concept of "reference to node that was added to data structure" is formalized as "non-owning reference". From linked_list's perspective this non-owning reference after linked_list_push_{front,back} has same semantics as release_on_unlock, with the addition of writes to such references being valid in the critical section. Such references are no longer marked PTR_UNTRUSTED. Patches 2 and 13 go into more detail.
The series then adds rbtree API kfuncs and necessary verifier support for them - namely support for callback args to kfuncs and some non-owning reference interactions that linked_list didn't need.
BPF rbtree uses struct rb_root_cached + existing rbtree lib under the hood. From the BPF program writer's perspective, a BPF rbtree is very similar to existing linked list. Consider the following example:
struct node_data {
long key;
long data;
struct bpf_rb_node node;
}
static bool less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
{
struct node_data *node_a;
struct node_data *node_b; node_a = container_of(a, struct node_data, node);
node_b = container_of(b, struct node_data, node);
return node_a->key < node_b->key;}
private(A) struct bpf_spin_lock glock; private(A) struct bpf_rb_root groot __contains(node_data, node);
/* ... in BPF program */
struct node_data *n, *m;
struct bpf_rb_node *res;
n = bpf_obj_new(typeof(*n));
if (!n)
/* skip */
n->key = 5;
n->data = 10;
bpf_spin_lock(&glock);
bpf_rbtree_add(&groot, &n->node, less);
bpf_spin_unlock(&glock);
bpf_spin_lock(&glock);
res = bpf_rbtree_first(&groot);
if (!res)
/* skip */
res = bpf_rbtree_remove(&groot, res);
if (!res)
/* skip */
bpf_spin_unlock(&glock);
m = container_of(res, struct node_data, node);
bpf_obj_drop(m);Some obvious similarities:
* Special bpf_rb_root and bpf_rb_node types have same semantics as bpf_list_head and bpf_list_node, respectively
* __contains is used to associated node type with root
* The spin_lock associated with a rbtree must be held when using rbtree API kfuncs
* Nodes are allocated via bpf_obj_new and dropped via bpf_obj_drop
* Rbtree takes ownership of node lifetime when a node is added. Removing a node gives ownership back to the program, requiring a bpf_obj_drop before program exit
Some new additions as well:
* Support for callbacks in kfunc args is added to enable 'less' callback use above
* bpf_rbtree_first is the first graph API function to return a
non-owning reference instead of convering an arg from own->non-own
* Because all references to nodes already added to the rbtree are non-owning, bpf_rbtree_remove must accept such a reference in order to remove it from the tree
Summary of patches:
Patches 1 - 5 implement the meat of rbtree-specific support in this series, gradually building up to implemented kfuncs that verify as expected.
Patch 6 adds the bpf_rbtree_{add,first,remove} to bpf_experimental.h.
Patch 7 adds tests, Patch 9 adds documentation.
[0]: lore.kernel.org/bpf/[email protected] [1]: lore.kernel.org/bpf/[email protected] [2]: lore.kernel.org/bpf/[email protected]
Changelog:
v5 -> v6: lore.kernel.org/bpf/[email protected]/
Patch #'s below refer to the patch's number in v5 unless otherwise stated.
* General / Patch 1
* Rebase onto latest bpf-next: "bpf: Migrate release_on_unlock logic to non-owning ref semantics"
* This was Patch 1 of v4, was applied, not included in v6
* Patch 3 - "bpf: Add bpf_rbtree_{add,remove,first} kfuncs"
* Use bpf_callback_t instead of plain-C fn ptr for bpf_rbtree_add. This necessitated having bpf_rbtree_add duplicate rbtree_add's functionality. Wrapper function was used w/ internal __bpf_rbtree_add helper so that bpf_experimental.h proto could continue to use plain-C fn ptr so BPF progs could benefit from typechecking (Alexei)
v4 -> v5: lore.kernel.org/bpf/[email protected]/
Patch #'s below refer to the patch's number in v4 unless otherwise stated.
* General
* Rebase onto latest bpf-next: "Merge branch 'bpf, mm: introduce cgroup.memory=nobpf'"
* Patches 1-3 are squashed into "bpf: Migrate release_on_unlock logic to non-owning ref semantics".
* Added type_is_non_owning_ref helper (Alexei)
* Use a NON_OWN_REF type flag instead of separate bool (Alexei)
* Patch 8 - "bpf: Special verifier handling for bpf_rbtree_{remove, first}"
* When doing btf_parse_fields, reject structs with both bpf_list_node and bpf_rb_node fields. This is a temporary measure that can be removed after "collection identity" followup. See comment added in btf_parse_fields for more detail (Kumar, Alexei)
* Add linked_list BTF test exercising check added to btf_parse_fields
* Minor changes and moving around of some reg type checks due to NON_OWN_REF type flag introduction
* Patch 10 - "selftests/bpf: Add rbtree selftests"
* Migrate failure tests to RUN_TESTS, __failure, __msg() framework (Alexei)
v3 -> v4: lore.kernel.org/bpf/[email protected]/
Patch #'s below refer to the patch's number in v3 unless otherwise stated.
* General
* Don't base this series on "bpf: Refactor release_regno searching logic",
which was submitted separately as a refactor.
* Rebase onto latest bpf-next: "samples/bpf: Add openat2() enter/exit tracepoint to syscall_tp sample"
* Patch 2 - "bpf: Improve bpf_reg_state space usage for non-owning ref lock"
* print_verifier_state change was adding redundant comma after "non_own_ref", fix it to put comma in correct place
* invalidate_non_owning_refs no longer needs to take bpf_active_lock param, since any non-owning ref reg in env's cur_state is assumed to use that state's active_lock (Alexei)
* invalidate_non_owning_refs' reg loop should check that the reg being
inspected is a PTR_TO_BTF_ID before checking reg->non_owning_ref_lock,
since that field is part of a union and may be filled w/ meaningless bytes
if reg != PTR_TO_BTF_ID (Alexei)* Patch 3 - "selftests/bpf: Update linked_list tests for non-owning ref semantics"
* Change the string searched for by the following tests:
* linked_list/incorrect_node_off1
* linked_list/double_push_front
* linked_list/double_push_back
necessary due to rebase / dropping of "release_regno searching logic" patch (see "General" changes)
* Patch 8 - "bpf: Special verifier handling for bpf_rbtree_{remove, first}"
* Just call invalidate_non_owning_refs w/ env instead of env, lock. (see Patch 2 changes)
* Patch 11 - "bpf, documentation: Add graph documentation for non-owning refs"
* Fix documentation formatting and improve content (David)
* v3's version of patch 11 was missing some changes, v4's patch 11 is still addressing David's feedback from v2
v2 -> v3: lore.kernel.org/bpf/[email protected]/
Patch #'s below refer to the patch's number in v2 unless otherwise stated.
* Patch 1 - "bpf: Support multiple arg regs w/ ref_obj_id for kfuncs"
* No longer needed as v3 doesn't have multiple ref_obj_id arg regs
* The refactoring pieces were submitted separately
(https://lore.kernel.org/bpf/[email protected]/)
* Patch 2 - "bpf: Migrate release_on_unlock logic to non-owning ref semantics"
* Remove KF_RELEASE_NON_OWN flag from list API push methods, just match against specific kfuncs for now (Alexei, David)
* Separate "release non owning reference" logic from KF_RELEASE logic (Alexei, David)
* reg_find_field_offset now correctly tests 'rec' instead of 'reg' after calling reg_btf_record (Dan Carpenter)
* New patch added after Patch 2 - "bpf: Improve bpf_reg_state space usage for non-owning ref lock"
* Eliminates extra bpf_reg_state memory usage by using a bool instead of
copying lock identity
* Patch 4 - "bpf: rename list_head -> graph_root in field info types"
* v2's version was applied to bpf-next, not including in respins
* Patch 6 - "bpf: Add bpf_rbtree_{add,remove,first} kfuncs"
* Remove KF_RELEASE_NON_OWN flag from rbtree_add, just add it to specific kfunc matching (Alexei, David)
* Patch 9 - "bpf: Special verifier handling for bpf_rbtree_{remove, first}"
* Remove KF_INVALIDATE_NON_OWN kfunc flag, just match against specific kfunc for now (Alexei, David)
* Patch 11 - "libbpf: Make BTF mandatory if program BTF has spin_lock or alloc_obj type"
* Drop for now, will submit separately
* Patch 12 - "selftests/bpf: Add rbtree selftests"
* Some expected-failure tests have different error messages due to "release non-owning reference logic" being separated from KF_RELEASE logic in Patch 2 changes
* Patch 13 - "bpf, documentation: Add graph documentation for non-owning refs"
* Fix documentation formatting and improve content (David)
v1 -> v2: lore.kernel.org/bpf/[email protected]/
Series-wide changes:
* Rename datastructure_{head,node,api} -> graph_{root,node,api} (Alexei)
* "graph datastructure" in patch summaries to refer to linked_list + rbtree instead of "next-gen datastructure" (Alexei)
* Move from hacky marking of non-owning references as PTR_UNTRUSTED to cleaner implementation (Alexei)
* Add invalidation of non-owning refs to rbtree_remove (Kumar, Alexei)
Patch #'s below refer to the patch's number in v1 unless otherwise stated.
Note that in v1 most of the meaty verifier changes were in the latter half of the series. Here, about half of that complexity has been moved to "bpf: Migrate release_on_unlock logic to non-owning ref semantics" - was Patch 3 in v1.
* Patch 1 - "bpf: Loosen alloc obj test in verifier's reg_btf_record"
* Was applied, dropped from further iterations
* Patch 2 - "bpf: map_check_btf should fail if btf_parse_fields fails"
* Dropped in favor of verifier check-on-use: when some normal verifier checking expects the map to have btf_fields correctly parsed, it won't find any and verification will fail
* New patch added before Patch 3 - "bpf: Support multiple arg regs w/ ref_obj_id for kfuncs"
* Addition of KF_RELEASE_NON_OWN flag, which requires KF_RELEASE, and tagging of bpf_list_push_{front,back} KF_RELEASE | KF_RELEASE_NON_OWN, means that list-in-list push_{front,back} will trigger "only one ref_obj_id arg reg" logic. This is because "head" arg to those functions can be a list-in-list, which itself can be an owning reference with ref_obj_id. So need to support multiple ref_obj_id for release kfuncs.
* Patch 3 - "bpf: Minor refactor of ref_set_release_on_unlock"
* Now a major refactor w/ a rename to reflect this
* "bpf: Migrate release_on_unlock logic to non-owning ref semantics"
* Replaces release_on_unlock with active_lock logic as discussed in v1
* New patch added after Patch 3 - "selftests/bpf: Update linked_list tests for non_owning_ref logic"
* Removes "write after push" linked_list failure tests - no longer failure scenarios.
* Patch 4 - "bpf: rename list_head -> datastructure_head in field info types"
* rename to graph_root instead. Similar renamings across the series - see series-wide changes.
* Patch 5 - "bpf: Add basic bpf_rb_{root,node} support"
* OWNER_FIELD_MASK -> GRAPH_ROOT_MASK, OWNEE_FIELD_MASK -> GRAPH_NODE_MASK, and change of "owner"/"ownee" in big btf_check_and_fixup_fields comment to "root"/"node" (Alexei)
* Patch 6 - "bpf: Add bpf_rbtree_{add,remove,first} kfuncs"
* bpf_rbtree_remove can no longer return NULL. v2 continues v1's "use type system to prevent remove of node that isn't in a datastructure" approach, so rbtree_remove should never have been able to return NULL
* Patch 7 - "bpf: Add support for bpf_rb_root and bpf_rb_node in kfunc args"
* is_bpf_datastructure_api_kfunc -> is_bpf_graph_api_kfunc (Alexei)
* Patch 8 - "bpf: Add callback validation to kfunc verifier logic"
* Explicitly disallow rbtree_remove in rbtree callback
* Explicitly disallow bpf_spin_{lock,unlock} call in rbtree callback, preventing possibility of "unbalanced" unlock (Alexei)
* Patch 10 - "bpf, x86: BPF_PROBE_MEM handling for insn->off < 0"
* Now that non-owning refs aren't marked PTR_UNTRUSTED it's not necessary to include this patch as part of the series
* After conversation w/ Alexei, did another pass and submitted as an
independent series (lore.kernel.org/bpf/[email protected]/)
* Patch 13 - "selftests/bpf: Add rbtree selftests"
* Since bpf_rbtree_remove can no longer return null, remove null checks
* Remove test confirming that rbtree_first isn't allowed in callback. We want this to be possible
* Add failure test confirming that rbtree_remove's new non-owning reference invalidation behavior behaves as expected
* Add SEC("license") to rbtree_btf_fail__* progs. They were previously failing due to lack of this section. Now they're failing for correct reasons.
* rbtree_btf_fail__add_wrong_type.c - add locking around rbtree_add, rename the bpf prog to something reasonable
* New patch added after patch 13 - "bpf, documentation: Add graph documentation for non-owning refs"
* Summarizes details of owning and non-owning refs which we hashed out in
v1
Dave Marchevsky (8):
bpf: Add basic bpf_rb_{root,node} support
bpf: Add bpf_rbtree_{add,remove,first} kfuncs
bpf: Add support for bpf_rb_root and bpf_rb_node in kfunc args
bpf: Add callback validation to kfunc verifier logic
bpf: Special verifier handling for bpf_rbtree_{remove, first}
bpf: Add bpf_rbtree_{add,remove,first} decls to bpf_experimental.h selftests/bpf: Add rbtree selftests
bpf, documentation: Add graph documentation for non-owning refs
Documentation/bpf/graph_ds_impl.rst | 266 +++++++++++ Documentation/bpf/other.rst | 3 +- include/linux/bpf.h | 20 +- include/uapi/linux/bpf.h | 11 + kernel/bpf/btf.c | 186 +++++--- kernel/bpf/helpers.c | 93 ++++ kernel/bpf/syscall.c | 28 +- kernel/bpf/verifier.c | 420 ++++++++++++++++-- tools/include/uapi/linux/bpf.h | 11 + .../testing/selftests/bpf/bpf_experimental.h | 24 + .../selftests/bpf/prog_tests/linked_list.c | 49 +- .../testing/selftests/bpf/prog_tests/rbtree.c | 117 +++++ tools/testing/selftests/bpf/progs/rbtree.c | 176 ++++++++ .../progs/rbtree_btf_fail__add_wrong_type.c | 52 +++ .../progs/rbtree_btf_fail__wrong_node_type.c | 49 ++ .../testing/selftests/bpf/progs/rbtree_fail.c | 322 ++++++++++++++ 16 files changed, 1707 insertions(+), 120 deletions(-) create mode 100644 Documentation/bpf/graph_ds_impl.rst create mode 100644 tools/testing/selftests/bpf/prog_tests/rbtree.c create mode 100644 tools/testing/selftests/bpf/progs/rbtree.c create mode 100644 tools/testing/selftests/bpf/progs/rbtree_btf_fail__add_wrong_type.c create mode 100644 tools/testing/selftests/bpf/progs/rbtree_btf_fail__wrong_node_type.c create mode 100644 tools/testing/selftests/bpf/progs/rbtree_fail.c
Signature · 1 line
2.30.2
PATCH v6 1/8 bpf: Add basic bpf_rb_{root,node} support
This patch adds special BPF_RB_{ROOT,NODE} btf_field_types similar to BPF_LIST_{HEAD,NODE}, adds the necessary plumbing to detect the new types, and adds bpf_rb_root_free function for freeing bpf_rb_root in map_values.
structs bpf_rb_root and bpf_rb_node are opaque types meant to obscure structs rb_root_cached rb_node, respectively.
btf_struct_access will prevent BPF programs from touching these special fields automatically now that they're recognized.
btf_check_and_fixup_fields now groups list_head and rb_root together as "graph root" fields and {list,rb}_node as "graph node", and does same ownership cycle checking as before. Note that this function does _not_ prevent ownership type mixups (e.g. rb_root owning list_node) - that's handled by btf_parse_graph_root.
After this patch, a bpf program can have a struct bpf_rb_root in a map_value, but not add anything to nor do anything useful with it.
--- include/linux/bpf.h | 20 ++- include/uapi/linux/bpf.h | 11 ++ kernel/bpf/btf.c | 162 ++++++++++++------ kernel/bpf/helpers.c | 40 +++++ kernel/bpf/syscall.c | 28 ++- kernel/bpf/verifier.c | 5 +- tools/include/uapi/linux/bpf.h | 11 ++ .../selftests/bpf/prog_tests/linked_list.c | 12 +- 8 files changed, 216 insertions(+), 73 deletions(-)
include/linux/bpf.h +19 -1
@@ -181,7 +181,10 @@ enum btf_field_type {BPF_KPTR =BPF_KPTR_UNREF |BPF_KPTR_REF ,BPF_LIST_HEAD = (1 <<4 ),BPF_LIST_NODE = (1 <<5 ), - BPF_GRAPH_NODE_OR_ROOT = BPF_LIST_NODE | BPF_LIST_HEAD, +BPF_RB_ROOT = (1 <<6 ), +BPF_RB_NODE = (1 <<7 ), +BPF_GRAPH_NODE_OR_ROOT =BPF_LIST_NODE |BPF_LIST_HEAD | + BPF_RB_NODE | BPF_RB_ROOT, }; struct btf_field_kptr {
@@ -285,6 +288,10 @@ static inline const char *btf_field_type_name(enum btf_field_type type)return "bpf_list_head" ;case BPF_LIST_NODE :return "bpf_list_node" ; +case BPF_RB_ROOT : +return "bpf_rb_root" ; +case BPF_RB_NODE : +return "bpf_rb_node" ;default :WARN_ON_ONCE (1 );return "unknown" ;
@@ -305,6 +312,10 @@ static inline u32 btf_field_type_size(enum btf_field_type type)return sizeof (struct bpf_list_head );case BPF_LIST_NODE :return sizeof (struct bpf_list_node ); +case BPF_RB_ROOT : +return sizeof (struct bpf_rb_root ); +case BPF_RB_NODE : +return sizeof (struct bpf_rb_node );default :WARN_ON_ONCE (1 );return 0 ;
@@ -325,6 +336,10 @@ static inline u32 btf_field_type_align(enum btf_field_type type)return __alignof__(struct bpf_list_head );case BPF_LIST_NODE :return __alignof__(struct bpf_list_node ); +case BPF_RB_ROOT : +return __alignof__(struct bpf_rb_root ); +case BPF_RB_NODE : +return __alignof__(struct bpf_rb_node );default :WARN_ON_ONCE (1 );return 0 ;
@@ -435,6 +450,9 @@ void copy_map_value_locked(struct bpf_map *map, void *dst, void *src,void bpf_timer_cancel_and_free (void *timer);void bpf_list_head_free (const struct btf_field *field,void *list_head,struct bpf_spin_lock *spin_lock); +void bpf_rb_root_free (const struct btf_field *field,void *rb_root, +struct bpf_spin_lock *spin_lock); +int bpf_obj_name_cpy (char *dst,const char *src,unsigned int size);
include/uapi/linux/bpf.h +11 -0
@@ -6917,6 +6917,17 @@ struct bpf_list_node { __u64 :64 ; } __attribute__((aligned(8))); +struct bpf_rb_root { + __u64 :64; + __u64 :64; +} __attribute__((aligned (8 ))); + +struct bpf_rb_node { + __u64 :64; + __u64 :64; + __u64 :64; +} __attribute__((aligned (8 ))); +struct bpf_sysctl {__u32 write;/* Sysctl is being read (= 0) or written (= 1). * Allows 1,2,4-byte read, but no write.
kernel/bpf/btf.c +107 -55
313 lines not on this page · raw message
kernel/bpf/helpers.c +40 -0
@@ -1772,6 +1772,46 @@ void bpf_list_head_free(const struct btf_field *field, void *list_head, } } +/* Like rbtree_postorder_for_each_entry_safe, but 'pos' and 'n' are +* 'rb_node *', so field name of rb_node within containing struct is not +* needed. +* +* Since bpf_rb_tree's node type has a corresponding struct btf_field with +* graph_root.node_offset, it's not necessary to know field name +* or type of node struct +*/ +#define bpf_rbtree_postorder_for_each_entry_safe (pos, n, root) \ + for (pos = rb_first_postorder(root); \ + pos && ({ n = rb_next_postorder(pos); 1; }); \ + pos = n) + +void bpf_rb_root_free (const struct btf_field *field,void *rb_root, +struct bpf_spin_lock *spin_lock) +{ +struct rb_root_cached orig_root, *root = rb_root; +struct rb_node *pos, *n; +void *obj; + +BUILD_BUG_ON (sizeof (struct rb_root_cached ) >sizeof (struct bpf_rb_root )); +BUILD_BUG_ON (__alignof__(struct rb_root_cached ) > __alignof__(struct bpf_rb_root )); + +__bpf_spin_lock_irqsave (spin_lock); + orig_root = *root; + *root =RB_ROOT_CACHED ; +__bpf_spin_unlock_irqrestore (spin_lock); + +bpf_rbtree_postorder_for_each_entry_safe (pos, n, &orig_root.rb_root) { + obj = pos; + obj -= field->graph_root.node_offset; + +bpf_obj_free_fields (field->graph_root.value_rec, obj); + +migrate_disable (); +bpf_mem_free (&bpf_global_ma, obj); +migrate_enable (); + } +} +__diag_push ();__diag_ignore_all ("-Wmissing-prototypes" ,"Global functions as their definitions will be in vmlinux BTF" );
kernel/bpf/syscall.c +19 -9
@@ -537,9 +537,6 @@ void btf_record_free(struct btf_record *rec)return ;for (i =0 ; i < rec->cnt; i++) {switch (rec->fields[i].type) { -case BPF_SPIN_LOCK : -case BPF_TIMER : -break ;case BPF_KPTR_UNREF :case BPF_KPTR_REF :if (rec->fields[i].kptr.module)
@@ -548,7 +545,11 @@ void btf_record_free(struct btf_record *rec)break ;case BPF_LIST_HEAD :case BPF_LIST_NODE : -/* Nothing to release for bpf_list_head */ +case BPF_RB_ROOT : +case BPF_RB_NODE : +case BPF_SPIN_LOCK : +case BPF_TIMER : +/* Nothing to release */ break ;default :WARN_ON_ONCE (1 );
@@ -581,9 +582,6 @@ struct btf_record *btf_record_dup(const struct btf_record *rec) new_rec->cnt =0 ;for (i =0 ; i < rec->cnt; i++) {switch (fields[i].type) { -case BPF_SPIN_LOCK : -case BPF_TIMER : -break ;case BPF_KPTR_UNREF :case BPF_KPTR_REF :btf_get (fields[i].kptr.btf);
@@ -594,7 +592,11 @@ struct btf_record *btf_record_dup(const struct btf_record *rec)break ;case BPF_LIST_HEAD :case BPF_LIST_NODE : -/* Nothing to acquire for bpf_list_head */ +case BPF_RB_ROOT : +case BPF_RB_NODE : +case BPF_SPIN_LOCK : +case BPF_TIMER : +/* Nothing to acquire */ break ;default : ret = -EFAULT ;
@@ -674,7 +676,13 @@ void bpf_obj_free_fields(const struct btf_record *rec, void *obj)continue ;bpf_list_head_free (field, field_ptr, obj + rec->spin_lock_off);break ; +case BPF_RB_ROOT : +if (WARN_ON_ONCE (rec->spin_lock_off <0 )) +continue ; +bpf_rb_root_free (field, field_ptr, obj + rec->spin_lock_off); +break ;case BPF_LIST_NODE : +case BPF_RB_NODE :break ;default :WARN_ON_ONCE (1 );
@@ -1010,7 +1018,8 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf,return -EINVAL ; map->record =btf_parse_fields (btf, value_type, -BPF_SPIN_LOCK |BPF_TIMER |BPF_KPTR |BPF_LIST_HEAD , +BPF_SPIN_LOCK |BPF_TIMER |BPF_KPTR |BPF_LIST_HEAD | +BPF_RB_ROOT , map->value_size);if (!IS_ERR_OR_NULL (map->record)) {int i;
@@ -1058,6 +1067,7 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf, }break ;case BPF_LIST_HEAD : +case BPF_RB_ROOT :if (map->map_type !=BPF_MAP_TYPE_HASH && map->map_type !=BPF_MAP_TYPE_LRU_HASH && map->map_type !=BPF_MAP_TYPE_ARRAY ) {
kernel/bpf/verifier.c +3 -2
@@ -14703,9 +14703,10 @@ static int check_map_prog_compatibility(struct bpf_verifier_env *env, {enum bpf_prog_type prog_type =resolve_prog_type (prog); -if (btf_record_has_field (map->record,BPF_LIST_HEAD )) { +if (btf_record_has_field (map->record,BPF_LIST_HEAD ) || +btf_record_has_field (map->record,BPF_RB_ROOT )) {if (is_tracing_prog_type (prog_type)) { -verbose (env,"tracing progs cannot use bpf_list_head yet\n" ); +verbose (env,"tracing progs cannot use bpf_{list_head,rb_root} yet\n" );return -EINVAL ; } }
tools/include/uapi/linux/bpf.h +11 -0
@@ -6917,6 +6917,17 @@ struct bpf_list_node { __u64 :64 ; } __attribute__((aligned(8))); +struct bpf_rb_root { + __u64 :64; + __u64 :64; +} __attribute__((aligned (8 ))); + +struct bpf_rb_node { + __u64 :64; + __u64 :64; + __u64 :64; +} __attribute__((aligned (8 ))); +struct bpf_sysctl {__u32 write;/* Sysctl is being read (= 0) or written (= 1). * Allows 1,2,4-byte read, but no write.
tools/testing/selftests/bpf/prog_tests/linked_list.c +6 -6
@@ -58,12 +58,12 @@ static struct { TEST(inner_map, pop_front) TEST(inner_map, pop_back)#undef TEST - { "map_compat_kprobe", "tracing progs cannot use bpf_list_head yet" }, - { "map_compat_kretprobe", "tracing progs cannot use bpf_list_head yet" }, - { "map_compat_tp", "tracing progs cannot use bpf_list_head yet" }, - { "map_compat_perf", "tracing progs cannot use bpf_list_head yet" }, - { "map_compat_raw_tp", "tracing progs cannot use bpf_list_head yet" }, - { "map_compat_raw_tp_w", "tracing progs cannot use bpf_list_head yet" }, + { "map_compat_kprobe", "tracing progs cannot use bpf_{list_head,rb_root} yet" }, + { "map_compat_kretprobe", "tracing progs cannot use bpf_{list_head,rb_root} yet" }, + { "map_compat_tp", "tracing progs cannot use bpf_{list_head,rb_root} yet" }, + { "map_compat_perf", "tracing progs cannot use bpf_{list_head,rb_root} yet" }, + { "map_compat_raw_tp", "tracing progs cannot use bpf_{list_head,rb_root} yet" }, + { "map_compat_raw_tp_w", "tracing progs cannot use bpf_{list_head,rb_root} yet" }, { "obj_type_id_oor", "local type ID argument must be in range [0, U32_MAX]" }, { "obj_new_no_composite", "bpf_obj_new type ID argument must be of a struct" }, { "obj_new_no_struct", "bpf_obj_new type ID argument must be of a struct" },
Signature · 1 line
2.30.2
PATCH v6 2/8 bpf: Add bpf_rbtree_{add,remove,first} kfuncs
In reply to Dave MarchevskyThis patch adds implementations of bpf_rbtree_{add,remove,first} and teaches verifier about their BTF_IDs as well as those of bpf_rb_{root,node}.
All three kfuncs have some nonstandard component to their verification that needs to be addressed in future patches before programs can properly use them:
* bpf_rbtree_add: Takes 'less' callback, need to verify it
* bpf_rbtree_first: Returns ptr_to_node_type(off=rb_node_off) instead
of ptr_to_rb_node(off=0). Return value ref is non-owning.
* bpf_rbtree_remove: Returns ptr_to_node_type(off=rb_node_off) instead of ptr_to_rb_node(off=0). 2nd arg (node) is a non-owning reference.
--- kernel/bpf/helpers.c | 53 +++++++++++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 14 +++++++++++- 2 files changed, 66 insertions(+), 1 deletion(-)
kernel/bpf/helpers.c +53 -0
@@ -1884,6 +1884,55 @@ __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head)return __bpf_list_del (head, true); } +struct bpf_rb_node *bpf_rbtree_remove (struct bpf_rb_root *root,struct bpf_rb_node *node) +{ +struct rb_root_cached *r = (struct rb_root_cached *)root; +struct rb_node *n = (struct rb_node *)node; + +rb_erase_cached (n, r); +RB_CLEAR_NODE (n); +return (struct bpf_rb_node *)n; +} + +/* Need to copy rbtree_add_cached's logic here because our 'less' is a BPF +* program +*/ +static void __bpf_rbtree_add (struct bpf_rb_root *root,struct bpf_rb_node *node, +void *less) +{ +struct rb_node **link = &((struct rb_root_cached *)root)->rb_root.rb_node; +bpf_callback_t cb = (bpf_callback_t )less; +struct rb_node *parent =NULL ; +bool leftmost = true; + +while (*link) { + parent = *link; +if (cb ((uintptr_t )node, (uintptr_t )parent,0 ,0 ,0 )) { + link = &parent->rb_left; + }else { + link = &parent->rb_right; + leftmost = false; + } + } + +rb_link_node ((struct rb_node *)node, parent, link); +rb_insert_color_cached ((struct rb_node *)node, + (struct rb_root_cached *)root, leftmost); +} + +void bpf_rbtree_add (struct bpf_rb_root *root,struct bpf_rb_node *node, +bool (less )(struct bpf_rb_node *a,const struct bpf_rb_node *b)) +{ +__bpf_rbtree_add (root, node, (void *)less); +} + +struct bpf_rb_node *bpf_rbtree_first (struct bpf_rb_root *root) +{ +struct rb_root_cached *r = (struct rb_root_cached *)root; + +return (struct bpf_rb_node *)rb_first_cached (r); +} +/** * bpf_task_acquire - Acquire a reference to a task. A task acquired by this * kfunc which is not stored in a map as a kptr, must be released by calling
@@ -2108,6 +2157,10 @@ BTF_ID_FLAGS(func, bpf_task_acquire, KF_ACQUIRE | KF_TRUSTED_ARGS) BTF_ID_FLAGS(func, bpf_task_acquire_not_zero, KF_ACQUIRE | KF_RCU | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_task_kptr_get, KF_ACQUIRE | KF_KPTR_GET | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_task_release, KF_RELEASE) +BTF_ID_FLAGS(func, bpf_rbtree_remove, KF_ACQUIRE) +BTF_ID_FLAGS(func, bpf_rbtree_add) +BTF_ID_FLAGS(func, bpf_rbtree_first, KF_RET_NULL) +#ifdef CONFIG_CGROUPS BTF_ID_FLAGS(func, bpf_cgroup_acquire, KF_ACQUIRE | KF_TRUSTED_ARGS)BTF_ID_FLAGS (func, bpf_cgroup_kptr_get,KF_ACQUIRE |KF_KPTR_GET |KF_RET_NULL )
kernel/bpf/verifier.c +13 -1
@@ -8638,6 +8638,8 @@ BTF_ID_LIST(kf_arg_btf_ids) BTF_ID(struct, bpf_dynptr_kern) BTF_ID(struct, bpf_list_head) BTF_ID(struct, bpf_list_node) +BTF_ID(struct, bpf_rb_root) +BTF_ID(struct, bpf_rb_node)static bool __is_kfunc_ptr_arg_type (const struct btf *btf,const struct btf_param *arg,int type)
@@ -8743,6 +8745,9 @@ enum special_kfunc_type { KF_bpf_rdonly_cast, KF_bpf_rcu_read_lock, KF_bpf_rcu_read_unlock, + KF_bpf_rbtree_remove, + KF_bpf_rbtree_add, + KF_bpf_rbtree_first, };BTF_SET_START (special_kfunc_set)
@@ -8754,6 +8759,9 @@ BTF_ID(func, bpf_list_pop_front) BTF_ID(func, bpf_list_pop_back) BTF_ID(func, bpf_cast_to_kern_ctx) BTF_ID(func, bpf_rdonly_cast) +BTF_ID(func, bpf_rbtree_remove) +BTF_ID(func, bpf_rbtree_add) +BTF_ID(func, bpf_rbtree_first)BTF_SET_END (special_kfunc_set)BTF_ID_LIST (special_kfunc_list)
@@ -8767,6 +8775,9 @@ BTF_ID(func, bpf_cast_to_kern_ctx) BTF_ID(func, bpf_rdonly_cast) BTF_ID(func, bpf_rcu_read_lock) BTF_ID(func, bpf_rcu_read_unlock) +BTF_ID(func, bpf_rbtree_remove) +BTF_ID(func, bpf_rbtree_add) +BTF_ID(func, bpf_rbtree_first)static bool is_kfunc_bpf_rcu_read_lock (struct bpf_kfunc_call_arg_meta *meta) {
@@ -9556,7 +9567,8 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, }if (meta.func_id == special_kfunc_list[KF_bpf_list_push_front] || - meta.func_id == special_kfunc_list[KF_bpf_list_push_back]) { + meta.func_id == special_kfunc_list[KF_bpf_list_push_back] || + meta.func_id == special_kfunc_list[KF_bpf_rbtree_add]) { release_ref_obj_id = regs[BPF_REG_2 ].ref_obj_id; err =ref_convert_owning_non_owning (env, release_ref_obj_id);if (err) {
Signature · 1 line
2.30.2
Re: [PATCH v6 bpf-next 2/8] bpf: Add bpf_rbtree_{add,remove,first} kfuncs
Quoted 2 lines · Dave Marchevsky
+struct
bpf_rb_node*bpf_rbtree_remove(structbpf_rb_root*root, structbpf_rb_node*node)
...
kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) · line 1929
Quoted 7 lines
kernel/bpf/helpers.c +7
-0+void bpf_rbtree_add (struct bpf_rb_root *root,struct bpf_rb_node *node, +bool (less )(struct bpf_rb_node *a,const struct bpf_rb_node *b)) +{ +__bpf_rbtree_add (root, node, (void *)less); +} + +struct bpf_rb_node *bpf_rbtree_first (struct bpf_rb_root *root)
__bpf_kfunc annotations were missing.
I've added them while applying.
The rest looks great. Very nice milestone.
PATCH v6 3/8 bpf: Add support for bpf_rb_root and bpf_rb_node in kfunc args
In reply to Dave MarchevskyNow that we find bpf_rb_root and bpf_rb_node in structs, let's give args that contain those types special classification and properly handle these types when checking kfunc args.
"Properly handling" these types largely requires generalizing similar handling for bpf_list_{head,node}, with little new logic added in this patch.
--- kernel/bpf/verifier.c | 238 +++++++++++++++++++++++++++++++++++------- 1 file changed, 203 insertions(+), 35 deletions(-)
kernel/bpf/verifier.c +203 -35
@@ -8521,6 +8521,9 @@ struct bpf_kfunc_call_arg_meta {struct {struct btf_field *field; } arg_list_head; +struct { +struct btf_field *field; + } arg_rbtree_root; };static bool is_kfunc_acquire (struct bpf_kfunc_call_arg_meta *meta)
@@ -8632,6 +8635,8 @@ enum {KF_ARG_DYNPTR_ID ,KF_ARG_LIST_HEAD_ID ,KF_ARG_LIST_NODE_ID , +KF_ARG_RB_ROOT_ID , +KF_ARG_RB_NODE_ID , };BTF_ID_LIST (kf_arg_btf_ids)
@@ -8673,6 +8678,16 @@ static bool is_kfunc_arg_list_node(const struct btf *btf, const struct btf_paramreturn __is_kfunc_ptr_arg_type (btf, arg,KF_ARG_LIST_NODE_ID ); } +static bool is_kfunc_arg_rbtree_root (const struct btf *btf,const struct btf_param *arg) +{ +return __is_kfunc_ptr_arg_type (btf, arg,KF_ARG_RB_ROOT_ID ); +} + +static bool is_kfunc_arg_rbtree_node (const struct btf *btf,const struct btf_param *arg) +{ +return __is_kfunc_ptr_arg_type (btf, arg,KF_ARG_RB_NODE_ID ); +} +/* Returns true if struct is composed of scalars, 4 levels of nesting allowed */ static bool __btf_type_is_scalar_struct(struct bpf_verifier_env *env, const struct btf *btf,
@@ -8732,6 +8747,8 @@ enum kfunc_ptr_arg_type {KF_ARG_PTR_TO_BTF_ID ,/* Also covers reg2btf_ids conversions */ KF_ARG_PTR_TO_MEM ,KF_ARG_PTR_TO_MEM_SIZE ,/* Size derived from next argument, skip it */ +KF_ARG_PTR_TO_RB_ROOT , + KF_ARG_PTR_TO_RB_NODE, }; enum special_kfunc_type {
@@ -8839,6 +8856,12 @@ get_kfunc_ptr_arg_type(struct bpf_verifier_env *env,if (is_kfunc_arg_list_node (meta->btf, &args[argno]))return KF_ARG_PTR_TO_LIST_NODE ; +if (is_kfunc_arg_rbtree_root (meta->btf, &args[argno])) +return KF_ARG_PTR_TO_RB_ROOT ; + +if (is_kfunc_arg_rbtree_node (meta->btf, &args[argno])) +return KF_ARG_PTR_TO_RB_NODE ; +if ((base_type (reg->type) ==PTR_TO_BTF_ID || reg2btf_ids[base_type (reg->type)])) {if (!btf_type_is_struct (ref_t)) { verbose(env, "kernel function %s args#%d pointer type %s %s is not supported\n",
@@ -9095,95 +9118,193 @@ static bool is_bpf_list_api_kfunc(u32 btf_id) btf_id == special_kfunc_list[KF_bpf_list_pop_back]; } -static int process_kf_arg_ptr_to_list_head (struct bpf_verifier_env *env, -struct bpf_reg_state *reg,u32 regno, -struct bpf_kfunc_call_arg_meta *meta) +static bool is_bpf_rbtree_api_kfunc (u32 btf_id) +{ +return btf_id == special_kfunc_list[KF_bpf_rbtree_add] || + btf_id == special_kfunc_list[KF_bpf_rbtree_remove] || + btf_id == special_kfunc_list[KF_bpf_rbtree_first]; +} + +static bool is_bpf_graph_api_kfunc (u32 btf_id) +{ +return is_bpf_list_api_kfunc (btf_id) ||is_bpf_rbtree_api_kfunc (btf_id); +} + +static bool check_kfunc_is_graph_root_api (struct bpf_verifier_env *env, +enum btf_field_type head_field_type, +u32 kfunc_btf_id) { +bool ret; + +switch (head_field_type) { +case BPF_LIST_HEAD : + ret =is_bpf_list_api_kfunc (kfunc_btf_id); +break ; +case BPF_RB_ROOT : + ret =is_bpf_rbtree_api_kfunc (kfunc_btf_id); +break ; +default : +verbose (env,"verifier internal error: unexpected graph root argument type %s\n" , +btf_field_type_name (head_field_type)); +return false; + } + +if (!ret) +verbose (env,"verifier internal error: %s head arg for unknown kfunc\n" , +btf_field_type_name (head_field_type)); +return ret; +} + +static bool check_kfunc_is_graph_node_api (struct bpf_verifier_env *env, +enum btf_field_type node_field_type, +u32 kfunc_btf_id) +{ +bool ret; + +switch (node_field_type) { +case BPF_LIST_NODE : + ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_front] || + kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_back]); +break ; +case BPF_RB_NODE : + ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_remove] || + kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_add]); +break ; +default : +verbose (env,"verifier internal error: unexpected graph node argument type %s\n" , +btf_field_type_name (node_field_type)); +return false; + } + +if (!ret) +verbose (env,"verifier internal error: %s node arg for unknown kfunc\n" , +btf_field_type_name (node_field_type)); +return ret; +} + +static int +__process_kf_arg_ptr_to_graph_root (struct bpf_verifier_env *env, +struct bpf_reg_state *reg,u32 regno, +struct bpf_kfunc_call_arg_meta *meta, +enum btf_field_type head_field_type, +struct btf_field **head_field) +{ +const char *head_type_name;struct btf_field *field;struct btf_record *rec; -u32 list_head_off; +u32 head_off; -if (meta->btf != btf_vmlinux || !is_bpf_list_api_kfunc (meta->func_id)) { -verbose (env,"verifier internal error: bpf_list_head argument for unknown kfunc\n" ); +if (meta->btf != btf_vmlinux) { +verbose (env,"verifier internal error: unexpected btf mismatch in kfunc call\n" );return -EFAULT ; } +if (!check_kfunc_is_graph_root_api (env, head_field_type, meta->func_id)) +return -EFAULT ; + + head_type_name =btf_field_type_name (head_field_type);if (!tnum_is_const (reg->var_off)) {verbose (env, -"R%d doesn't have constant offset. bpf_list_head has to be at the constant offset\n" , - regno); +"R%d doesn't have constant offset. %s has to be at the constant offset\n" , + regno, head_type_name);return -EINVAL ; } rec =reg_btf_record (reg); - list_head_off = reg->off + reg->var_off.value; - field =btf_record_find (rec, list_head_off,BPF_LIST_HEAD ); + head_off = reg->off + reg->var_off.value; + field =btf_record_find (rec, head_off, head_field_type);if (!field) { -verbose (env,"bpf_list_head not found at offset=%u\n" , list_head_off); +verbose (env,"%s not found at offset=%u\n" , head_type_name, head_off);return -EINVAL ; }/* All functions require bpf_list_head to be protected using a bpf_spin_lock */ if (check_reg_allocation_locked (env, reg)) { -verbose (env,"bpf_spin_lock at off=%d must be held for bpf_list_head\n" , - rec->spin_lock_off); +verbose (env,"bpf_spin_lock at off=%d must be held for %s\n" , + rec->spin_lock_off, head_type_name);return -EINVAL ; } -if (meta->arg_list_head.field) { -verbose (env,"verifier internal error: repeating bpf_list_head arg\n" ); +if (*head_field) { +verbose (env,"verifier internal error: repeating %s arg\n" , head_type_name);return -EFAULT ; } - meta->arg_list_head.field = field; + *head_field = field;return 0 ; } -static int process_kf_arg_ptr_to_list_node (struct bpf_verifier_env *env, +static int process_kf_arg_ptr_to_list_head (struct bpf_verifier_env *env,struct bpf_reg_state *reg,u32 regno,struct bpf_kfunc_call_arg_meta *meta) { +return __process_kf_arg_ptr_to_graph_root (env, reg, regno, meta,BPF_LIST_HEAD , + &meta->arg_list_head.field); +} + +static int process_kf_arg_ptr_to_rbtree_root (struct bpf_verifier_env *env, +struct bpf_reg_state *reg,u32 regno, +struct bpf_kfunc_call_arg_meta *meta) +{ +return __process_kf_arg_ptr_to_graph_root (env, reg, regno, meta,BPF_RB_ROOT , + &meta->arg_rbtree_root.field); +} + +static int +__process_kf_arg_ptr_to_graph_node (struct bpf_verifier_env *env, +struct bpf_reg_state *reg,u32 regno, +struct bpf_kfunc_call_arg_meta *meta, +enum btf_field_type head_field_type, +enum btf_field_type node_field_type, +struct btf_field **node_field) +{ +const char *node_type_name;const struct btf_type *et, *t;struct btf_field *field; -u32 list_node_off; +u32 node_off; -if (meta->btf != btf_vmlinux || - (meta->func_id != special_kfunc_list[KF_bpf_list_push_front] && - meta->func_id != special_kfunc_list[KF_bpf_list_push_back])) { -verbose (env,"verifier internal error: bpf_list_node argument for unknown kfunc\n" ); +if (meta->btf != btf_vmlinux) { +verbose (env,"verifier internal error: unexpected btf mismatch in kfunc call\n" );return -EFAULT ; } +if (!check_kfunc_is_graph_node_api (env, node_field_type, meta->func_id)) +return -EFAULT ; + + node_type_name =btf_field_type_name (node_field_type);if (!tnum_is_const (reg->var_off)) {verbose (env, -"R%d doesn't have constant offset. bpf_list_node has to be at the constant offset\n" , - regno); +"R%d doesn't have constant offset. %s has to be at the constant offset\n" , + regno, node_type_name);return -EINVAL ; } - list_node_off = reg->off + reg->var_off.value; - field =reg_find_field_offset (reg, list_node_off,BPF_LIST_NODE ); -if (!field || field->offset != list_node_off) { -verbose (env,"bpf_list_node not found at offset=%u\n" , list_node_off); + 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) { +verbose (env,"%s not found at offset=%u\n" , node_type_name, node_off);return -EINVAL ; } - field = meta->arg_list_head.field; + field = *node_field; et =btf_type_by_id (field->graph_root.btf, field->graph_root.value_btf_id); t =btf_type_by_id (reg->btf, reg->btf_id);if (!btf_struct_ids_match (&env->log, reg->btf, reg->btf_id,0 , field->graph_root.btf, field->graph_root.value_btf_id, true)) { -verbose (env,"operation on bpf_list_head expects arg#1 bpf_list_node at offset=%d " +verbose (env,"operation on %s expects arg#1 %s at offset=%d " "in struct %s, but arg is at offset=%d in struct %s\n" , +btf_field_type_name (head_field_type), +btf_field_type_name (node_field_type), field->graph_root.node_offset,btf_name_by_offset (field->graph_root.btf, et->name_off), - list_node_off,btf_name_by_offset (reg->btf, t->name_off)); + node_off,btf_name_by_offset (reg->btf, t->name_off));return -EINVAL ; } -if (list_node_off != field->graph_root.node_offset) { -verbose (env,"arg#1 offset=%d, but expected bpf_list_node at offset=%d in struct %s\n" , - list_node_off, field->graph_root.node_offset, +if (node_off != field->graph_root.node_offset) { +verbose (env,"arg#1 offset=%d, but expected %s at offset=%d in struct %s\n" , + node_off,btf_field_type_name (node_field_type), + field->graph_root.node_offset,btf_name_by_offset (field->graph_root.btf, et->name_off));return -EINVAL ; }
@@ -9191,6 +9312,24 @@ static int process_kf_arg_ptr_to_list_node(struct bpf_verifier_env *env,return 0 ; } +static int process_kf_arg_ptr_to_list_node (struct bpf_verifier_env *env, +struct bpf_reg_state *reg,u32 regno, +struct bpf_kfunc_call_arg_meta *meta) +{ +return __process_kf_arg_ptr_to_graph_node (env, reg, regno, meta, +BPF_LIST_HEAD ,BPF_LIST_NODE , + &meta->arg_list_head.field); +} + +static int process_kf_arg_ptr_to_rbtree_node (struct bpf_verifier_env *env, +struct bpf_reg_state *reg,u32 regno, +struct bpf_kfunc_call_arg_meta *meta) +{ +return __process_kf_arg_ptr_to_graph_node (env, reg, regno, meta, +BPF_RB_ROOT ,BPF_RB_NODE , + &meta->arg_rbtree_root.field); +} +static int check_kfunc_args (struct bpf_verifier_env *env,struct bpf_kfunc_call_arg_meta *meta) {const char *func_name = meta->func_name, *ref_tname;
@@ -9325,6 +9464,8 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_case KF_ARG_PTR_TO_DYNPTR :case KF_ARG_PTR_TO_LIST_HEAD :case KF_ARG_PTR_TO_LIST_NODE : +case KF_ARG_PTR_TO_RB_ROOT : +case KF_ARG_PTR_TO_RB_NODE :case KF_ARG_PTR_TO_MEM :case KF_ARG_PTR_TO_MEM_SIZE :/* Trusted by default */
@@ -9403,6 +9544,20 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_if (ret <0 )return ret;break ; +case KF_ARG_PTR_TO_RB_ROOT : +if (reg->type !=PTR_TO_MAP_VALUE && + reg->type != (PTR_TO_BTF_ID |MEM_ALLOC )) { +verbose (env,"arg#%d expected pointer to map value or allocated object\n" , i); +return -EINVAL ; + } +if (reg->type == (PTR_TO_BTF_ID |MEM_ALLOC ) && !reg->ref_obj_id) { +verbose (env,"allocated object must be referenced\n" ); +return -EINVAL ; + } + ret =process_kf_arg_ptr_to_rbtree_root (env, reg, regno, meta); +if (ret <0 ) +return ret; +break ;case KF_ARG_PTR_TO_LIST_NODE :if (reg->type != (PTR_TO_BTF_ID |MEM_ALLOC )) {verbose (env,"arg#%d expected pointer to allocated object\n" , i);
@@ -9416,6 +9571,19 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_if (ret <0 )return ret;break ; +case KF_ARG_PTR_TO_RB_NODE : +if (reg->type != (PTR_TO_BTF_ID |MEM_ALLOC )) { +verbose (env,"arg#%d expected pointer to allocated object\n" , i); +return -EINVAL ; + } +if (!reg->ref_obj_id) { +verbose (env,"allocated object must be referenced\n" ); +return -EINVAL ; + } + ret =process_kf_arg_ptr_to_rbtree_node (env, reg, regno, meta); +if (ret <0 ) +return ret; +break ;case KF_ARG_PTR_TO_BTF_ID :/* Only base_type is checked, further checks are done here */ if ((base_type(reg->type) != PTR_TO_BTF_ID ||
@@ -14417,7 +14585,7 @@ static int do_check(struct bpf_verifier_env *env)if ((insn->src_reg ==BPF_REG_0 && insn->imm != BPF_FUNC_spin_unlock) || (insn->src_reg ==BPF_PSEUDO_CALL ) || (insn->src_reg ==BPF_PSEUDO_KFUNC_CALL && - (insn->off !=0 || !is_bpf_list_api_kfunc (insn->imm)))) { + (insn->off !=0 || !is_bpf_graph_api_kfunc (insn->imm)))) {verbose (env,"function calls are not allowed while holding a lock\n" );return -EINVAL ; }
Signature · 1 line
2.30.2
PATCH v6 4/8 bpf: Add callback validation to kfunc verifier logic
In reply to Dave MarchevskySome BPF helpers take a callback function which the helper calls. For each helper that takes such a callback, there's a special call to __check_func_call with a callback-state-setting callback that sets up verifier bpf_func_state for the callback's frame.
kfuncs don't have any of this infrastructure yet, so let's add it in this patch, following existing helper pattern as much as possible. To validate functionality of this added plumbing, this patch adds callback handling for the bpf_rbtree_add kfunc and hopes to lay groundwork for future graph datastructure callbacks.
In the "general plumbing" category we have:
* check_kfunc_call doing callback verification right before clearing CALLER_SAVED_REGS, exactly like check_helper_call
* recognition of func_ptr BTF types in kfunc args as KF_ARG_PTR_TO_CALLBACK + propagation of subprogno for this arg type
In the "rbtree_add / graph datastructure-specific plumbing" category:
* Since bpf_rbtree_add must be called while the spin_lock associated with the tree is held, don't complain when callback's func_state doesn't unlock it by frame exit
* Mark rbtree_add callback's args with ref_set_non_owning to prevent rbtree api functions from being called in the callback. Semantically this makes sense, as less() takes no ownership of its args when determining which comes first.
--- kernel/bpf/verifier.c | 134 ++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 129 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +129 -5
@@ -191,6 +191,7 @@ struct bpf_verifier_stack_elem {static int acquire_reference_state (struct bpf_verifier_env *env,int insn_idx);static int release_reference (struct bpf_verifier_env *env,int ref_obj_id);static void invalidate_non_owning_refs (struct bpf_verifier_env *env); +static bool in_rbtree_lock_required_cb (struct bpf_verifier_env *env);static int ref_set_non_owning (struct bpf_verifier_env *env,struct bpf_reg_state *reg);
@@ -1642,6 +1643,16 @@ static void mark_ptr_not_null_reg(struct bpf_reg_state *reg) reg->type &= ~PTR_MAYBE_NULL ; } +static void mark_reg_graph_node (struct bpf_reg_state *regs,u32 regno, +struct btf_field_graph_root *ds_head) +{ +__mark_reg_known_zero (®s[regno]); + regs[regno].type =PTR_TO_BTF_ID |MEM_ALLOC ; + regs[regno].btf = ds_head->btf; + regs[regno].btf_id = ds_head->value_btf_id; + regs[regno].off = ds_head->node_offset; +} +static bool reg_is_pkt_pointer (const struct bpf_reg_state *reg) {return type_is_pkt_pointer (reg->type);
@@ -6837,6 +6848,10 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 arg, meta->ret_btf_id = reg->btf_id;break ;case ARG_PTR_TO_SPIN_LOCK : +if (in_rbtree_lock_required_cb (env)) { +verbose (env,"can't spin_{lock,unlock} in rbtree cb\n" ); +return -EACCES ; + }if (meta->func_id == BPF_FUNC_spin_lock) { err =process_spin_lock (env, regno, true);if (err)
@@ -7420,6 +7435,8 @@ static int set_callee_state(struct bpf_verifier_env *env,struct bpf_func_state *caller, struct bpf_func_state *callee, int insn_idx); +static bool is_callback_calling_kfunc (u32 btf_id); +static int __check_func_call (struct bpf_verifier_env *env,struct bpf_insn *insn,int *insn_idx,int subprog,set_callee_state_fn set_callee_state_cb)
@@ -7474,10 +7491,18 @@ static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn* interested in validating only BPF helpers that can call subprogs as * callbacks */ -if (set_callee_state_cb != set_callee_state && !is_callback_calling_function (insn->imm)) { -verbose (env,"verifier bug: helper %s#%d is not marked as callback-calling\n" , -func_id_name (insn->imm), insn->imm); -return -EFAULT ; +if (set_callee_state_cb != set_callee_state) { +if (bpf_pseudo_kfunc_call (insn) && + !is_callback_calling_kfunc (insn->imm)) { +verbose (env,"verifier bug: kfunc %s#%d not marked as callback-calling\n" , +func_id_name (insn->imm), insn->imm); +return -EFAULT ; + }else if (!bpf_pseudo_kfunc_call (insn) && + !is_callback_calling_function (insn->imm)) {/* helper */ +verbose (env,"verifier bug: helper %s#%d not marked as callback-calling\n" , +func_id_name (insn->imm), insn->imm); +return -EFAULT ; + } } if (insn->code == (BPF_JMP | BPF_CALL) &&
@@ -7742,6 +7767,63 @@ static int set_user_ringbuf_callback_state(struct bpf_verifier_env *env,return 0 ; } +static int set_rbtree_add_callback_state (struct bpf_verifier_env *env, +struct bpf_func_state *caller, +struct bpf_func_state *callee, +int insn_idx) +{ +/* void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node, +* bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b)); +* +* 'struct bpf_rb_node *node' arg to bpf_rbtree_add is the same PTR_TO_BTF_ID w/ offset +* that 'less' callback args will be receiving. However, 'node' arg was release_reference'd +* by this point, so look at 'root' +*/ +struct btf_field *field; + + field =reg_find_field_offset (&caller->regs[BPF_REG_1 ], caller->regs[BPF_REG_1 ].off, +BPF_RB_ROOT ); +if (!field || !field->graph_root.value_btf_id) +return -EFAULT ; + +mark_reg_graph_node (callee->regs,BPF_REG_1 , &field->graph_root); +ref_set_non_owning (env, &callee->regs[BPF_REG_1 ]); +mark_reg_graph_node (callee->regs,BPF_REG_2 , &field->graph_root); +ref_set_non_owning (env, &callee->regs[BPF_REG_2 ]); + +__mark_reg_not_init (env, &callee->regs[BPF_REG_3 ]); +__mark_reg_not_init (env, &callee->regs[BPF_REG_4 ]); +__mark_reg_not_init (env, &callee->regs[BPF_REG_5 ]); + callee->in_callback_fn = true; + callee->callback_ret_range =tnum_range (0 ,1 ); +return 0 ; +} + +static bool is_rbtree_lock_required_kfunc (u32 btf_id); + +/* Are we currently verifying the callback for a rbtree helper that must +* be called with lock held? If so, no need to complain about unreleased +* lock +*/ +static bool in_rbtree_lock_required_cb (struct bpf_verifier_env *env) +{ +struct bpf_verifier_state *state = env->cur_state; +struct bpf_insn *insn = env->prog->insnsi; +struct bpf_func_state *callee; +int kfunc_btf_id; + +if (!state->curframe) +return false; + + callee = state->frame[state->curframe]; + +if (!callee->in_callback_fn) +return false; + + kfunc_btf_id = insn[callee->callsite].imm; +return is_rbtree_lock_required_kfunc (kfunc_btf_id); +} +static int prepare_func_exit (struct bpf_verifier_env *env,int *insn_idx) {struct bpf_verifier_state *state = env->cur_state;
@@ -8510,6 +8592,7 @@ struct bpf_kfunc_call_arg_meta {bool r0_rdonly;u32 ret_btf_id;u64 r0_size; +u32 subprogno;struct {u64 value;bool found;
@@ -8688,6 +8771,18 @@ static bool is_kfunc_arg_rbtree_node(const struct btf *btf, const struct btf_parreturn __is_kfunc_ptr_arg_type (btf, arg,KF_ARG_RB_NODE_ID ); } +static bool is_kfunc_arg_callback (struct bpf_verifier_env *env,const struct btf *btf, +const struct btf_param *arg) +{ +const struct btf_type *t; + + t =btf_type_resolve_func_ptr (btf, arg->type,NULL ); +if (!t) +return false; + +return true; +} +/* Returns true if struct is composed of scalars, 4 levels of nesting allowed */ static bool __btf_type_is_scalar_struct(struct bpf_verifier_env *env, const struct btf *btf,
@@ -8747,6 +8842,7 @@ enum kfunc_ptr_arg_type {KF_ARG_PTR_TO_BTF_ID ,/* Also covers reg2btf_ids conversions */ KF_ARG_PTR_TO_MEM ,KF_ARG_PTR_TO_MEM_SIZE ,/* Size derived from next argument, skip it */ +KF_ARG_PTR_TO_CALLBACK ,KF_ARG_PTR_TO_RB_ROOT , KF_ARG_PTR_TO_RB_NODE, };
@@ -8871,6 +8967,9 @@ get_kfunc_ptr_arg_type(struct bpf_verifier_env *env,return KF_ARG_PTR_TO_BTF_ID ; } +if (is_kfunc_arg_callback (env, meta->btf, &args[argno])) +return KF_ARG_PTR_TO_CALLBACK ; +if (argno +1 < nargs &&is_kfunc_arg_mem_size (meta->btf, &args[argno +1 ], ®s[regno +1 ])) arg_mem_size = true;
@@ -9130,6 +9229,16 @@ static bool is_bpf_graph_api_kfunc(u32 btf_id)return is_bpf_list_api_kfunc (btf_id) ||is_bpf_rbtree_api_kfunc (btf_id); } +static bool is_callback_calling_kfunc (u32 btf_id) +{ +return btf_id == special_kfunc_list[KF_bpf_rbtree_add]; +} + +static bool is_rbtree_lock_required_kfunc (u32 btf_id) +{ +return is_bpf_rbtree_api_kfunc (btf_id); +} +static bool check_kfunc_is_graph_root_api (struct bpf_verifier_env *env,enum btf_field_type head_field_type,u32 kfunc_btf_id)
@@ -9468,6 +9577,7 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_case KF_ARG_PTR_TO_RB_NODE :case KF_ARG_PTR_TO_MEM :case KF_ARG_PTR_TO_MEM_SIZE : +case KF_ARG_PTR_TO_CALLBACK :/* Trusted by default */ break ;default :
@@ -9619,6 +9729,9 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_/* Skip next '__sz' argument */ i++;break ; +case KF_ARG_PTR_TO_CALLBACK : + meta->subprogno = reg->subprogno; +break ; } }
@@ -9753,6 +9866,16 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, } } +if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_add]) { + err =__check_func_call (env, insn, insn_idx_p, meta.subprogno, + set_rbtree_add_callback_state); +if (err) { +verbose (env,"kfunc %s#%d failed callback verification\n" , + func_name, func_id); +return err; + } + } +for (i =0 ; i <CALLER_SAVED_REGS ; i++)mark_reg_not_init (env, regs, caller_saved[i]);
@@ -14621,7 +14744,8 @@ static int do_check(struct bpf_verifier_env *env)return -EINVAL ; } -if (env->cur_state->active_lock.ptr) { +if (env->cur_state->active_lock.ptr && + !in_rbtree_lock_required_cb (env)) {verbose (env,"bpf_spin_unlock is missing\n" );return -EINVAL ; }
Signature · 1 line
2.30.2
PATCH v6 5/8 bpf: Special verifier handling for bpf_rbtree_{remove, first}
In reply to Dave MarchevskyNewly-added bpf_rbtree_{remove,first} kfuncs have some special properties that require handling in the verifier:
* both bpf_rbtree_remove and bpf_rbtree_first return the type containing the bpf_rb_node field, with the offset set to that field's offset, instead of a struct bpf_rb_node *
* mark_reg_graph_node helper added in previous patch generalizes this logic, use it
* bpf_rbtree_remove's node input is a node that's been inserted in the tree - a non-owning reference.
* bpf_rbtree_remove must invalidate non-owning references in order to avoid aliasing issue. Use previously-added invalidate_non_owning_refs helper to mark this function as a non-owning ref invalidation point.
* Unlike other functions, which convert one of their input arg regs to non-owning reference, bpf_rbtree_first takes no arguments and just returns a non-owning reference (possibly null)
* For now verifier logic for this is special-cased instead of adding new kfunc flag.
This patch, along with the previous one, complete special verifier handling for all rbtree API functions added in this series.
With functional verifier handling of rbtree_remove, under current non-owning reference scheme, a node type with both bpf_{list,rb}_node fields could cause the verifier to accept programs which remove such nodes from collections they haven't been added to.
In order to prevent this, this patch adds a check to btf_parse_fields which rejects structs with both bpf_{list,rb}_node fields. This is a temporary measure that can be removed after "collection identity" followup. See comment added in btf_parse_fields. A linked_list BTF test exercising the new check is added in this patch as well.
--- kernel/bpf/btf.c | 24 +++++++++++ kernel/bpf/verifier.c | 43 +++++++++++++------ .../selftests/bpf/prog_tests/linked_list.c | 37 ++++++++++++++++ 3 files changed, 92 insertions(+), 12 deletions(-)
kernel/bpf/btf.c +24 -0
@@ -3768,6 +3768,30 @@ struct btf_record *btf_parse_fields(const struct btf *btf, const struct btf_type goto end; } +/* need collection identity for non-owning refs before allowing this +* +* Consider a node type w/ both list and rb_node fields: +* struct node { +* struct bpf_list_node l; +* struct bpf_rb_node r; +* } +* +* Used like so: +* struct node *n = bpf_obj_new(....); +* bpf_list_push_front(&list_head, &n->l); +* bpf_rbtree_remove(&rb_root, &n->r); +* +* It should not be possible to rbtree_remove the node since it hasn't +* been added to a tree. But push_front converts n to a non-owning +* reference, and rbtree_remove accepts the non-owning reference to +* a type w/ bpf_rb_node field. +*/ +if (btf_record_has_field (rec,BPF_LIST_NODE ) && +btf_record_has_field (rec,BPF_RB_NODE )) { + ret = -EINVAL ; + goto end; + } +return rec; end:btf_record_free (rec);
kernel/bpf/verifier.c +31 -12
63 lines not on this page · raw message
tools/testing/selftests/bpf/prog_tests/linked_list.c +37 -0
@@ -715,6 +715,43 @@ static void test_btf(void)btf__free (btf);break ; } + +while (test__start_subtest ("btf: list_node and rb_node in same struct" )) { + btf =init_btf (); +if (!ASSERT_OK_PTR (btf,"init_btf" )) +break ; + + id =btf__add_struct (btf,"bpf_rb_node" ,24 ); +if (!ASSERT_EQ (id,5 ,"btf__add_struct bpf_rb_node" )) +break ; + id =btf__add_struct (btf,"bar" ,40 ); +if (!ASSERT_EQ (id,6 ,"btf__add_struct bar" )) +break ; + err =btf__add_field (btf,"a" ,LIST_NODE ,0 ,0 ); +if (!ASSERT_OK (err,"btf__add_field bar::a" )) +break ; + err =btf__add_field (btf,"c" ,5 ,128 ,0 ); +if (!ASSERT_OK (err,"btf__add_field bar::c" )) +break ; + + id =btf__add_struct (btf,"foo" ,20 ); +if (!ASSERT_EQ (id,7 ,"btf__add_struct foo" )) +break ; + err =btf__add_field (btf,"a" ,LIST_HEAD ,0 ,0 ); +if (!ASSERT_OK (err,"btf__add_field foo::a" )) +break ; + err =btf__add_field (btf,"b" ,SPIN_LOCK ,128 ,0 ); +if (!ASSERT_OK (err,"btf__add_field foo::b" )) +break ; + id =btf__add_decl_tag (btf,"contains:bar:a" ,7 ,0 ); +if (!ASSERT_EQ (id,8 ,"btf__add_decl_tag contains:bar:a" )) +break ; + + err =btf__load_into_kernel (btf); +ASSERT_EQ (err, -EINVAL ,"check btf" ); +btf__free (btf); +break ; + } }void test_linked_list (void )
Signature · 1 line
2.30.2
PATCH v6 6/8 bpf: Add bpf_rbtree_{add,remove,first} decls to bpf_experimental.h
In reply to Dave MarchevskyThese kfuncs will be used by selftests in following patches
--- .../testing/selftests/bpf/bpf_experimental.h | 24 +++++++++++++++++++ 1 file changed, 24 insertions(+)
tools/testing/selftests/bpf/bpf_experimental.h +24 -0
@@ -65,4 +65,28 @@ extern struct bpf_list_node *bpf_list_pop_front(struct bpf_list_head *head) __ks*/ extern struct bpf_list_node *bpf_list_pop_back (struct bpf_list_head *head) __ksym; +/* Description +* Remove 'node' from rbtree with root 'root' +* Returns +* Pointer to the removed node, or NULL if 'root' didn't contain 'node' +*/ +extern struct bpf_rb_node *bpf_rbtree_remove (struct bpf_rb_root *root, +struct bpf_rb_node *node) __ksym; + +/* Description +* Add 'node' to rbtree with root 'root' using comparator 'less' +* Returns +* Nothing +*/ +extern void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node, + bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b)) __ksym; + +/* Description +* Return the first (leftmost) node in input tree +* Returns +* Pointer to the node, which is _not_ removed from the tree. If the tree +* contains no nodes, returns NULL. +*/ +extern struct bpf_rb_node *bpf_rbtree_first (struct bpf_rb_root *root) __ksym; +#endif
Signature · 1 line
2.30.2
PATCH v6 7/8 selftests/bpf: Add rbtree selftests
In reply to Dave MarchevskyThis patch adds selftests exercising the logic changed/added in the previous patches in the series. A variety of successful and unsuccessful rbtree usages are validated:
Success:
* Add some nodes, let map_value bpf_rbtree_root destructor clean them up
* Add some nodes, remove one using the non-owning ref leftover by successful rbtree_add() call
* Add some nodes, remove one using the non-owning ref returned by rbtree_first() call
Failure:
* BTF where bpf_rb_root owns bpf_list_node should fail to load
* BTF where node of type X is added to tree containing nodes of type Y should fail to load
* No calling rbtree api functions in 'less' callback for rbtree_add
* No releasing lock in 'less' callback for rbtree_add
* No removing a node which hasn't been added to any tree
* No adding a node which has already been added to a tree
* No escaping of non-owning references past their lock's critical section
* No escaping of non-owning references past other invalidation points (rbtree_remove)
These tests mostly focus on rbtree-specific additions, but some of the failure cases revalidate scenarios common to both linked_list and rbtree which are covered in the former's tests. Better to be a bit redundant in case linked_list and rbtree semantics deviate over time.
--- .../testing/selftests/bpf/prog_tests/rbtree.c | 117 +++++++ tools/testing/selftests/bpf/progs/rbtree.c | 176 ++++++++++ .../progs/rbtree_btf_fail__add_wrong_type.c | 52 +++ .../progs/rbtree_btf_fail__wrong_node_type.c | 49 +++ .../testing/selftests/bpf/progs/rbtree_fail.c | 322 ++++++++++++++++++ 5 files changed, 716 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/rbtree.c create mode 100644 tools/testing/selftests/bpf/progs/rbtree.c create mode 100644 tools/testing/selftests/bpf/progs/rbtree_btf_fail__add_wrong_type.c create mode 100644 tools/testing/selftests/bpf/progs/rbtree_btf_fail__wrong_node_type.c create mode 100644 tools/testing/selftests/bpf/progs/rbtree_fail.c
tools/testing/selftests/bpf/prog_tests/rbtree.c new file +117 -0
@@ -0,0 +1,117 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include <test_progs.h> +#include <network_helpers.h> + +#include "rbtree.skel.h" +#include "rbtree_fail.skel.h" +#include "rbtree_btf_fail__wrong_node_type.skel.h" +#include "rbtree_btf_fail__add_wrong_type.skel.h" + +static void test_rbtree_add_nodes (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), &opts); +ASSERT_OK (ret,"rbtree_add_nodes run" ); +ASSERT_OK (opts.retval,"rbtree_add_nodes retval" ); +ASSERT_EQ (skel->data->less_callback_ran,1 ,"rbtree_add_nodes less_callback_ran" ); + +rbtree__destroy (skel); +} + +static void test_rbtree_add_and_remove (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), &opts); +ASSERT_OK (ret,"rbtree_add_and_remove" ); +ASSERT_OK (opts.retval,"rbtree_add_and_remove retval" ); +ASSERT_EQ (skel->data->removed_key,5 ,"rbtree_add_and_remove first removed key" ); + +rbtree__destroy (skel); +} + +static void test_rbtree_first_and_remove (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_first_and_remove), &opts); +ASSERT_OK (ret,"rbtree_first_and_remove" ); +ASSERT_OK (opts.retval,"rbtree_first_and_remove retval" ); +ASSERT_EQ (skel->data->first_data[0 ],2 ,"rbtree_first_and_remove first rbtree_first()" ); +ASSERT_EQ (skel->data->removed_key,1 ,"rbtree_first_and_remove first removed key" ); +ASSERT_EQ (skel->data->first_data[1 ],4 ,"rbtree_first_and_remove second rbtree_first()" ); + +rbtree__destroy (skel); +} + +void test_rbtree_success (void ) +{ +if (test__start_subtest ("rbtree_add_nodes" )) +test_rbtree_add_nodes (); +if (test__start_subtest ("rbtree_add_and_remove" )) +test_rbtree_add_and_remove (); +if (test__start_subtest ("rbtree_first_and_remove" )) +test_rbtree_first_and_remove (); +} + +#define BTF_FAIL_TEST (suffix) \ +void test_rbtree_btf_fail__##suffix(void) \ +{ \ + struct rbtree_btf_fail__##suffix *skel; \ + \ + skel = rbtree_btf_fail__##suffix##__open_and_load(); \ + if (!ASSERT_ERR_PTR(skel, \ + "rbtree_btf_fail__" #suffix "__open_and_load unexpected success")) \ + rbtree_btf_fail__##suffix##__destroy(skel); \ +} + +#define RUN_BTF_FAIL_TEST (suffix) \ + if (test__start_subtest("rbtree_btf_fail__" #suffix)) \ + test_rbtree_btf_fail__##suffix(); + +BTF_FAIL_TEST (wrong_node_type); +BTF_FAIL_TEST (add_wrong_type); + +void test_rbtree_btf_fail (void ) +{ +RUN_BTF_FAIL_TEST (wrong_node_type); +RUN_BTF_FAIL_TEST (add_wrong_type); +} + +void test_rbtree_fail (void ) +{ +RUN_TESTS (rbtree_fail); +}
tools/testing/selftests/bpf/progs/rbtree.c new file +176 -0
176 lines not on this page · raw message
tools/testing/selftests/bpf/progs/rbtree_btf_fail__add_wrong_type.c new file +52 -0
52 lines not on this page · raw message
tools/testing/selftests/bpf/progs/rbtree_btf_fail__wrong_node_type.c new file +49 -0
49 lines not on this page · raw message
tools/testing/selftests/bpf/progs/rbtree_fail.c new file +322 -0
322 lines not on this page · raw message
Signature · 1 line
2.30.2
PATCH v6 8/8 bpf, documentation: Add graph documentation for non-owning refs
In reply to Dave MarchevskyIt is difficult to intuit the semantics of owning and non-owning references from verifier code. In order to keep the high-level details from being lost in the mailing list, this patch adds documentation explaining semantics and details.
The target audience of doc added in this patch is folks working on BPF internals, as there's focus on "what should the verifier do here". Via reorganization or copy-and-paste, much of the content can probably be repurposed for BPF program writer audience as well.
--- Documentation/bpf/graph_ds_impl.rst | 266 ++++++++++++++++++++++++++++ Documentation/bpf/other.rst | 3 +- 2 files changed, 268 insertions(+), 1 deletion(-) create mode 100644 Documentation/bpf/graph_ds_impl.rst
Documentation/bpf/graph_ds_impl.rst new file +266 -0
@@ -0,0 +1,266 @@ +========================= +BPF Graph Data Structures +========================= + +This document describes implementation details of new-style "graph" data +structures (linked_list, rbtree), with particular focus on the verifier's +implementation of semantics specific to those data structures. + +Although no specific verifier code is referred to in this document, the document +assumes that the reader has general knowledge of BPF verifier internals, BPF +maps, and BPF program writing. + +Note that the intent of this document is to describe the current state of +these graph data structures. **No guarantees** of stability for either +semantics or APIs are made or implied here. + +.. contents:: + :local: + :depth: 2 + +Introduction +------------ + +The BPF map API has historically been the main way to expose data structures +of various types for use within BPF programs. Some data structures fit naturally +with the map API (HASH, ARRAY), others less so. Consequentially, programs +interacting with the latter group of data structures can be hard to parse +for kernel programmers without previous BPF experience. + +Luckily, some restrictions which necessitated the use of BPF map semantics are +no longer relevant. With the introduction of kfuncs, kptrs, and the any-context +BPF allocator, it is now possible to implement BPF data structures whose API +and semantics more closely match those exposed to the rest of the kernel. + +Two such data structures - linked_list and rbtree - have many verification +details in common. Because both have "root"s ("head" for linked_list) and +"node"s, the verifier code and this document refer to common functionality +as "graph_api", "graph_root", "graph_node", etc. + +Unless otherwise stated, examples and semantics below apply to both graph data +structures. + +Unstable API +------------ + +Data structures implemented using the BPF map API have historically used BPF +helper functions - either standard map API helpers like ``bpf_map_update_elem`` +or map-specific helpers. The new-style graph data structures instead use kfuncs +to define their manipulation helpers. Because there are no stability guarantees +for kfuncs, the API and semantics for these data structures can be evolved in +a way that breaks backwards compatibility if necessary. + +Root and node types for the new data structures are opaquely defined in the +``uapi/linux/bpf.h`` header. + +Locking +------- + +The new-style data structures are intrusive and are defined similarly to their +vanilla kernel counterparts: + +.. code-block:: c + struct node_data { + long key; + long data; + struct bpf_rb_node node; + }; + + struct bpf_spin_lock glock; + struct bpf_rb_root groot __contains(node_data, node); + +The "root" type for both linked_list and rbtree expects to be in a map_value +which also contains a ``bpf_spin_lock`` - in the above example both global +variables are placed in a single-value arraymap. The verifier considers this +spin_lock to be associated with the ``bpf_rb_root`` by virtue of both being in +the same map_value and will enforce that the correct lock is held when +verifying BPF programs that manipulate the tree. Since this lock checking +happens at verification time, there is no runtime penalty. + +Non-owning references +--------------------- + +**Motivation** + +Consider the following BPF code: + +.. code-block:: c + + struct node_data *n = bpf_obj_new(typeof(*n)); /* ACQUIRED */ + + bpf_spin_lock(&lock); + + bpf_rbtree_add(&tree, n); /* PASSED */ + + bpf_spin_unlock(&lock); + +From the verifier's perspective, the pointer ``n`` returned from ``bpf_obj_new`` +has type ``PTR_TO_BTF_ID | MEM_ALLOC``, with a ``btf_id`` of +``struct node_data`` and a nonzero ``ref_obj_id``. Because it holds ``n``, the +program has ownership of the pointee's (object pointed to by ``n``) lifetime. +The BPF program must pass off ownership before exiting - either via +``bpf_obj_drop``, which ``free``'s the object, or by adding it to ``tree`` with +``bpf_rbtree_add``. + +(``ACQUIRED`` and ``PASSED`` comments in the example denote statements where +"ownership is acquired" and "ownership is passed", respectively) + +What should the verifier do with ``n`` after ownership is passed off? If the +object was ``free``'d with ``bpf_obj_drop`` the answer is obvious: the verifier +should reject programs which attempt to access ``n`` after ``bpf_obj_drop`` as +the object is no longer valid. The underlying memory may have been reused for +some other allocation, unmapped, etc. + +When ownership is passed to ``tree`` via ``bpf_rbtree_add`` the answer is less +obvious. The verifier could enforce the same semantics as for ``bpf_obj_drop``, +but that would result in programs with useful, common coding patterns being +rejected, e.g.: + +.. code-block:: c + + int x; + struct node_data *n = bpf_obj_new(typeof(*n)); /* ACQUIRED */ + + bpf_spin_lock(&lock); + + bpf_rbtree_add(&tree, n); /* PASSED */ + x = n->data; + n->data = 42; + + bpf_spin_unlock(&lock); + +Both the read from and write to ``n->data`` would be rejected. The verifier +can do better, though, by taking advantage of two details: + + * Graph data structure APIs can only be used when the ``bpf_spin_lock`` + associated with the graph root is held + + * Both graph data structures have pointer stability + + * Because graph nodes are allocated with ``bpf_obj_new`` and + adding / removing from the root involves fiddling with the + ``bpf_{list,rb}_node`` field of the node struct, a graph node will + remain at the same address after either operation. + +Because the associated ``bpf_spin_lock`` must be held by any program adding +or removing, if we're in the critical section bounded by that lock, we know +that no other program can add or remove until the end of the critical section. +This combined with pointer stability means that, until the critical section +ends, we can safely access the graph node through ``n`` even after it was used +to pass ownership. + +The verifier considers such a reference a *non-owning reference*. The ref +returned by ``bpf_obj_new`` is accordingly considered an *owning reference*. +Both terms currently only have meaning in the context of graph nodes and API. + +**Details** + +Let's enumerate the properties of both types of references. + +*owning reference* + + * This reference controls the lifetime of the pointee + + * Ownership of pointee must be 'released' by passing it to some graph API + kfunc, or via ``bpf_obj_drop``, which ``free``'s the pointee + + * If not released before program ends, verifier considers program invalid + + * Access to the pointee's memory will not page fault + +*non-owning reference* + + * This reference does not own the pointee + + * It cannot be used to add the graph node to a graph root, nor ``free``'d via + ``bpf_obj_drop`` + + * No explicit control of lifetime, but can infer valid lifetime based on + non-owning ref existence (see explanation below) + + * Access to the pointee's memory will not page fault + +From verifier's perspective non-owning references can only exist +between spin_lock and spin_unlock. Why? After spin_unlock another program +can do arbitrary operations on the data structure like removing and ``free``-ing +via bpf_obj_drop. A non-owning ref to some chunk of memory that was remove'd, +``free``'d, and reused via bpf_obj_new would point to an entirely different thing. +Or the memory could go away. + +To prevent this logic violation all non-owning references are invalidated by the +verifier after a critical section ends. This is necessary to ensure the "will +not page fault" property of non-owning references. So if the verifier hasn't +invalidated a non-owning ref, accessing it will not page fault. + +Currently ``bpf_obj_drop`` is not allowed in the critical section, so +if there's a valid non-owning ref, we must be in a critical section, and can +conclude that the ref's memory hasn't been dropped-and- ``free``'d or +dropped-and-reused. + +Any reference to a node that is in an rbtree _must_ be non-owning, since +the tree has control of the pointee's lifetime. Similarly, any ref to a node +that isn't in rbtree _must_ be owning. This results in a nice property: +graph API add / remove implementations don't need to check if a node +has already been added (or already removed), as the ownership model +allows the verifier to prevent such a state from being valid by simply checking +types. + +However, pointer aliasing poses an issue for the above "nice property". +Consider the following example: + +.. code-block:: c + + struct node_data *n, *m, *o, *p; + n = bpf_obj_new(typeof(*n)); /* 1 */ + + bpf_spin_lock(&lock); + + bpf_rbtree_add(&tree, n); /* 2 */ + m = bpf_rbtree_first(&tree); /* 3 */ + + o = bpf_rbtree_remove(&tree, n); /* 4 */ + p = bpf_rbtree_remove(&tree, m); /* 5 */ + + bpf_spin_unlock(&lock); + + bpf_obj_drop(o); + bpf_obj_drop(p); /* 6 */ + +Assume the tree is empty before this program runs. If we track verifier state +changes here using numbers in above comments: + + 1) n is an owning reference + + 2) n is a non-owning reference, it's been added to the tree + + 3) n and m are non-owning references, they both point to the same node + + 4) o is an owning reference, n and m non-owning, all point to same node + + 5) o and p are owning, n and m non-owning, all point to the same node + + 6) a double-free has occurred, since o and p point to same node and o was + ``free``'d in previous statement + +States 4 and 5 violate our "nice property", as there are non-owning refs to +a node which is not in an rbtree. Statement 5 will try to remove a node which +has already been removed as a result of this violation. State 6 is a dangerous +double-free. + +At a minimum we should prevent state 6 from being possible. If we can't also +prevent state 5 then we must abandon our "nice property" and check whether a +node has already been removed at runtime. + +We prevent both by generalizing the "invalidate non-owning references" behavior +of ``bpf_spin_unlock`` and doing similar invalidation after +``bpf_rbtree_remove``. The logic here being that any graph API kfunc which: + + * takes an arbitrary node argument + + * removes it from the data structure + + * returns an owning reference to the removed node + +May result in a state where some other non-owning reference points to the same +node. So ``remove``-type kfuncs must be considered a non-owning reference +invalidation point as well.
Documentation/bpf/other.rst +2 -1
@@ -6,4 +6,5 @@ Other :maxdepth: 1 ringbuf - llvm_reloc + llvm_reloc + graph_ds_impl
Signature · 1 line
2.30.2
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 8 lines · On Mon, 13 Feb 2023 16:40:09 -0800 you wrote:
This series adds a rbtree datastructure following the "next-gen datastructure" precedent set by recently-added linked-list [0]. This is a reimplementation of previous rbtree RFC [1] to use kfunc + kptr instead of adding a new map type. This series adds a smaller set of API functions than that RFC - just the minimum needed to support current cgfifo example scheduler in ongoing
sched_exteffort [2], namely:[...]
Here is the summary with links:
- [v6,bpf-next,1/8] bpf: Add basic bpf_rb_{root,node} support
https://git.kernel.org/bpf/bpf-next/c/9c395c1b99bd - [v6,bpf-next,2/8] bpf: Add bpf_rbtree_{add,remove,first} kfuncs https://git.kernel.org/bpf/bpf-next/c/bd1279ae8a69 - [v6,bpf-next,3/8] bpf: Add support for bpf_rb_root and bpf_rb_node in kfunc args https://git.kernel.org/bpf/bpf-next/c/cd6791b4b6f6 - [v6,bpf-next,4/8] bpf: Add callback validation to kfunc verifier logic https://git.kernel.org/bpf/bpf-next/c/5d92ddc3de1b - [v6,bpf-next,5/8] bpf: Special verifier handling for bpf_rbtree_{remove, first} https://git.kernel.org/bpf/bpf-next/c/a40d3632436b - [v6,bpf-next,6/8] bpf: Add bpf_rbtree_{add,remove,first} decls to bpf_experimental.h https://git.kernel.org/bpf/bpf-next/c/c834df847ee6 - [v6,bpf-next,7/8] selftests/bpf: Add rbtree selftests https://git.kernel.org/bpf/bpf-next/c/215249f6adc0 - [v6,bpf-next,8/8] bpf, documentation: Add graph documentation for non-owning refs https://git.kernel.org/bpf/bpf-next/c/c31315c3aa09
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html