BPF rbtree next-gen datastructure
Subsystems (5)
v3 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:
Patch 1 lays groundwork for release_on_unlock -> non-owning ref changes
Patches 2 and 3 do release_on_unlock -> non-owning ref migration and update linked_list tests
Patch 4 is a nonfunctional rename
Patches 5 - 9 implement the meat of rbtree support in this series, gradually building up to implemented kfuncs that verify as expected.
Patch 10 adds the bpf_rbtree_{add,first,remove} to bpf_experimental.h.
Patch 12 adds tests, Patch 13 adds documentation.
[0]: lore.kernel.org/bpf/[email protected] [1]: lore.kernel.org/bpf/[email protected] [2]: lore.kernel.org/bpf/[email protected]
Changelog:
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 (13):
bpf: Support multiple arg regs w/ ref_obj_id for kfuncs
bpf: Migrate release_on_unlock logic to non-owning ref semantics selftests/bpf: Update linked_list tests for non-owning ref semantics
bpf: rename list_head -> graph_root in field info types
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
libbpf: Make BTF mandatory if program BTF has spin_lock or alloc_obj
type
selftests/bpf: Add rbtree selftests
bpf, documentation: Add graph documentation for non-owning refs
Documentation/bpf/graph_ds_impl.rst | 208 +++++ Documentation/bpf/other.rst | 3 +- include/linux/bpf.h | 23 +- include/linux/bpf_verifier.h | 39 +- include/linux/btf.h | 18 +- include/uapi/linux/bpf.h | 11 + kernel/bpf/btf.c | 181 ++-- kernel/bpf/helpers.c | 76 +- kernel/bpf/syscall.c | 28 +- kernel/bpf/verifier.c | 800 ++++++++++++++---- tools/include/uapi/linux/bpf.h | 11 + tools/lib/bpf/libbpf.c | 50 +- .../testing/selftests/bpf/bpf_experimental.h | 24 + .../selftests/bpf/prog_tests/linked_list.c | 22 +- .../testing/selftests/bpf/prog_tests/rbtree.c | 186 ++++ .../testing/selftests/bpf/progs/linked_list.c | 2 +- .../selftests/bpf/progs/linked_list_fail.c | 100 ++- 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 | 296 +++++++ 21 files changed, 2018 insertions(+), 337 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 v3 1/11 bpf: Migrate release_on_unlock logic to non-owning ref semantics
This patch introduces non-owning reference semantics to the verifier, specifically linked_list API kfunc handling. release_on_unlock logic for refs is refactored - with small functional changes - to implement these semantics, and bpf_list_push_{front,back} are migrated to use them.
When a list node is pushed to a list, the program still has a pointer to the node:
n = bpf_obj_new(typeof(*n)); bpf_spin_lock(&l); bpf_list_push_back(&l, n); /* n still points to the just-added node */ bpf_spin_unlock(&l);
What the verifier considers n to be after the push, and thus what can be done with n, are changed by this patch.
Common properties both before/after this patch:
* After push, n is only a valid reference to the node until end of critical section
* After push, n cannot be pushed to any list
* After push, the program can read the node's fields using n
Before:
* After push, n retains the ref_obj_id which it received on bpf_obj_new, but the associated bpf_reference_state's release_on_unlock field is set to true
* release_on_unlock field and associated logic is used to implement "n is only a valid ref until end of critical section"
* After push, n cannot be written to, the node must be removed from the list before writing to its fields
* After push, n is marked PTR_UNTRUSTED
After:
* After push, n's ref is released and ref_obj_id set to 0. The bpf_reg_state's non_owning_ref_lock struct is populated with the currently active lock
* non_owning_ref_lock and logic is used to implement "n is only a valid ref until end of critical section"
* n can be written to (except for special fields e.g. bpf_list_node,
timer, ...)
* No special type flag is added to n after push
Summary of specific implementation changes to achieve the above:
* release_on_unlock field, ref_set_release_on_unlock helper, and logic to "release on unlock" based on that field are removed
* The anonymous active_lock struct used by bpf_verifier_state is pulled out into a named struct bpf_active_lock.
* A non_owning_ref_lock field of type bpf_active_lock is added to bpf_reg_state's PTR_TO_BTF_ID union
* Helpers are added to use non_owning_ref_lock to implement non-owning ref semantics as described above
* invalidate_non_owning_refs - helper to clobber all non-owning refs matching a particular bpf_active_lock identity. Replaces release_on_unlock logic in process_spin_lock.
* ref_set_non_owning_lock - set non_owning_ref_lock for a reg based on current verifier state
* ref_convert_owning_non_owning - convert owning reference w/ specified ref_obj_id to non-owning references. Setup non_owning_ref_lock for each reg with that ref_obj_id and 0 out its ref_obj_id
After these changes, linked_list's "release on unlock" logic continues to function as before, except for the semantic differences noted above. The patch immediately following this one makes minor changes to linked_list selftests to account for the differing behavior.
--- include/linux/bpf.h | 1 + include/linux/bpf_verifier.h | 39 ++++----- kernel/bpf/verifier.c | 164 +++++++++++++++++++++++++---------- 3 files changed, 136 insertions(+), 68 deletions(-)
include/linux/bpf.h +1 -0
@@ -180,6 +180,7 @@ 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, }; struct btf_field_kptr {
include/linux/bpf_verifier.h +19 -20
@@ -43,6 +43,22 @@ enum bpf_reg_liveness { REG_LIVE_DONE = 0x8, /* liveness won't be updating this register anymore */ }; +/* For every reg representing a map value or allocated object pointer, +* we consider the tuple of (ptr, id) for them to be unique in verifier +* context and conside them to not alias each other for the purposes of +* tracking lock state. +*/ +struct bpf_active_lock { +/* This can either be reg->map_ptr or reg->btf. If ptr is NULL, +* there's no active lock held, and other fields have no +* meaning. If non-NULL, it indicates that a lock is held and +* id member has the reg->id of the register which can be >= 0. +*/ +void *ptr; +/* This will be reg->id */ +u32 id; +}; +struct bpf_reg_state {/* Ordering of fields matters. See states_equal() */ enum bpf_reg_type type;
@@ -68,6 +84,7 @@ struct bpf_reg_state {struct {struct btf *btf;u32 btf_id; +struct bpf_active_lock non_owning_ref_lock; };u32 mem_size;/* for PTR_TO_MEM | PTR_TO_MEM_OR_NULL */
@@ -223,11 +240,6 @@ struct bpf_reference_state {* exiting a callback function. */ int callback_ref; -/* Mark the reference state to release the registers sharing the same id -* on bpf_spin_unlock (for nodes that we will lose ownership to but are -* safe to access inside the critical section). -*/ -bool release_on_unlock; };/* state of the program:
@@ -328,21 +340,8 @@ struct bpf_verifier_state {u32 branches;u32 insn_idx;u32 curframe; -/* For every reg representing a map value or allocated object pointer, -* we consider the tuple of (ptr, id) for them to be unique in verifier -* context and conside them to not alias each other for the purposes of -* tracking lock state. -*/ -struct { -/* This can either be reg->map_ptr or reg->btf. If ptr is NULL, -* there's no active lock held, and other fields have no -* meaning. If non-NULL, it indicates that a lock is held and -* id member has the reg->id of the register which can be >= 0. -*/ -void *ptr; -/* This will be reg->id */ -u32 id; - } active_lock; + +struct bpf_active_lock active_lock;bool speculative;bool active_rcu_lock;
kernel/bpf/verifier.c +116 -48
266 lines not on this page · raw message
Signature · 1 line
2.30.2
PATCH v3 2/11 bpf: Improve bpf_reg_state space usage for non-owning ref lock
In reply to Dave MarchevskyThis patch eliminates extra bpf_reg_state memory usage added due to previous patch keeping a copy of lock identity in reg state for non-owning refs.
Instead of copying lock identity around, this patch changes non_owning_ref_lock field to be a bool, taking advantage of the following:
* There can currently only be one active lock at a time
* non-owning refs are only valid in the critical section
So if a verifier_state has an active_lock, any non-owning ref must've been obtained under that lock, and any non-owning ref not obtained under that lock must have been invalidated previously. Therefore if a non-owning ref is associated with a lock, it's the active_lock of the current state. So we can keep a bool "are we associated with active_lock of current state" instead of copying lock identity around.
--- include/linux/bpf_verifier.h | 2 +- kernel/bpf/verifier.c | 20 ++++++++++---------- 2 files changed, 11 insertions(+), 11 deletions(-)
include/linux/bpf_verifier.h +1 -1
@@ -84,7 +84,7 @@ struct bpf_reg_state {struct {struct btf *btf;u32 btf_id; -struct bpf_active_lock non_owning_ref_lock; +bool non_owning_ref_lock; };u32 mem_size;/* for PTR_TO_MEM | PTR_TO_MEM_OR_NULL */
kernel/bpf/verifier.c +10 -10
@@ -935,9 +935,8 @@ static void print_verifier_state(struct bpf_verifier_env *env,verbose_a ("id=%d" , reg->id);if (reg->ref_obj_id)verbose_a ("ref_obj_id=%d" , reg->ref_obj_id); -if (reg->non_owning_ref_lock.ptr) -verbose_a ("non_own_id=(%p,%d)" , reg->non_owning_ref_lock.ptr, - reg->non_owning_ref_lock.id); +if (reg->non_owning_ref_lock) +verbose (env,"non_own_ref," );if (t !=SCALAR_VALUE )verbose_a ("off=%d" , reg->off);if (type_is_pkt_pointer (t))
@@ -4834,7 +4833,7 @@ static int check_ptr_to_btf_access(struct bpf_verifier_env *env, }if (type_is_alloc (reg->type) && !reg->ref_obj_id && - !reg->non_owning_ref_lock.ptr) { + !reg->non_owning_ref_lock) {verbose (env,"verifier internal error: ref_obj_id for allocated object must be non-zero\n" );return -EFAULT ; }
@@ -7085,13 +7084,15 @@ static int release_reference(struct bpf_verifier_env *env,static void invalidate_non_owning_refs (struct bpf_verifier_env *env,struct bpf_active_lock *lock) { +struct bpf_active_lock *cur_state_lock;struct bpf_func_state *unused;struct bpf_reg_state *reg; + cur_state_lock = &env->cur_state->active_lock;bpf_for_each_reg_in_vstate (env->cur_state, unused, reg, ({ -if (reg->non_owning_ref_lock.ptr && - reg->non_owning_ref_lock.ptr == lock->ptr && - reg->non_owning_ref_lock.id == lock->id) +if (reg->non_owning_ref_lock && + cur_state_lock->ptr == lock->ptr && + cur_state_lock->id == lock->id)__mark_reg_unknown (env, reg); })); }
@@ -8718,13 +8719,12 @@ static int ref_set_non_owning_lock(struct bpf_verifier_env *env, struct bpf_reg_return -EFAULT ; } -if (reg->non_owning_ref_lock.ptr) { +if (reg->non_owning_ref_lock) {verbose (env,"verifier internal error: non_owning_ref_lock already set\n" );return -EFAULT ; } - reg->non_owning_ref_lock.id = state->active_lock.id; - reg->non_owning_ref_lock.ptr = state->active_lock.ptr; + reg->non_owning_ref_lock = true;return 0 ; }
Signature · 1 line
2.30.2
Re: [PATCH v3 bpf-next 02/11] bpf: Improve bpf_reg_state space usage for non-owning ref lock
Quoted 29 lines · Dave Marchevsky
This patch eliminates extra
bpf_reg_statememory usage added due to previous patch keeping a copy of lock identity in reg state for non-owning refs.Instead of copying lock identity around, this patch changes
non_owning_ref_lockfield to be a bool, taking advantage of the following:* There can currently only be one active lock at a time
* non-owning refs are only valid in the critical sectionSo if a
verifier_statehas anactive_lock, any non-owning ref must've been obtained under that lock, and any non-owning ref not obtained under that lock must have been invalidated previously. Therefore if a non-owning ref is associated with a lock, it's theactive_lockof the current state. So we can keep a bool "are we associated withactive_lockof current state" instead of copying lock identity around.Signed-off-by Dave Marchevsky <[email protected]>--- include/linux/bpf_verifier.h | 2 +- kernel/bpf/verifier.c | 20 ++++++++++---------- 2 files changed, 11 insertions(+), 11 deletions(-)include/linux/bpf_verifier.h +0
-0
include/linux/bpf_verifier.h struct bpf_reg_state { · line 90
Quoted 8 lines
include/linux/bpf_verifier.h +1
-1@@ -84,7 +84,7 @@ struct bpf_reg_state {struct {struct btf *btf;u32 btf_id; -struct bpf_active_lock non_owning_ref_lock; +bool non_owning_ref_lock; };u32 mem_size;/* for PTR_TO_MEM | PTR_TO_MEM_OR_NULL */
Pahole output after this change:
union {
int range; /* 8 4 */
struct {
struct bpf_map * map_ptr; /* 8 8 */
u32 map_uid; /* 16 4 */
}; /* 8 16 */
struct {
struct btf * btf; /* 8 8 */
u32 btf_id; /* 16 4 */
bool non_owning_ref_lock; /* 20 1 */
}; /* 8 16 */
u32 mem_size; /* 8 4 */
struct {
enum bpf_dynptr_type type; /* 8 4 */
bool first_slot; /* 12 1 */
} dynptr; /* 8 8 */
struct {
long unsigned int raw1; /* 8 8 */
long unsigned int raw2; /* 16 8 */
} raw; /* 8 16 */
u32 subprogno; /* 8 4 */
}; /* 8 16 */
The PTR_TO_BTF_ID union entry was taking 24 bytes in previous commit, now it's down to 16, so back to same size as before previous commit.
Re: [PATCH v3 bpf-next 02/11] bpf: Improve bpf_reg_state space usage for non-owning ref lock
In reply to Dave MarchevskyQuoted 5 lines · Dave Marchevsky
static void invalidate_non_owning_refs(struct
bpf_verifier_env*env,
structbpf_active_lock*lock)
{kernel/bpf/verifier.c +1
-0+struct bpf_active_lock *cur_state_lock;struct bpf_func_state *unused;
kernel/bpf/verifier.c static int release_reference(struct bpf_verifier_env *env, · line 7095
Quoted 10 lines
kernel/bpf/verifier.c +4
-3struct bpf_reg_state *reg; + cur_state_lock = &env->cur_state->active_lock; bpf_for_each_reg_in_vstate(env->cur_state, unused, reg, ({ - if (reg->non_owning_ref_lock.ptr && - reg->non_owning_ref_lock.ptr == lock->ptr && - reg->non_owning_ref_lock.id == lock->id) + if (reg->non_owning_ref_lock && + cur_state_lock->ptr == lock->ptr && + cur_state_lock->id == lock->id)
invalidate_non_owning_refs() is called with &cur_state, so the last two checks are redundant, but I suspect they hide the issue with the first check.
Just reg->non_owning_ref_lock is ambiguous.
It needs base_type(reg->type) == PTR_TO_BTF_ID first.
PATCH v3 3/11 selftests/bpf: Update linked_list tests for non-owning ref semantics
In reply to Dave MarchevskyCurrent linked_list semantics for release_on_unlock node refs are almost exactly the same as newly-introduced "non-owning reference" concept. The only difference: writes to a release_on_unlock node ref are not allowed, while writes to non-owning reference pointees are.
As a result the linked_list "write after push" failure tests are no longer scenarios that should fail.
The test##_missing_lock_##op and test##_incorrect_lock_##op macro-generated failure tests need to have a valid node argument in order to have the same error output as before. Otherwise verification will fail early and the expected error output won't be seen.
Some other tests have minor changes in error output, but fail for the same reason.
--- .../selftests/bpf/prog_tests/linked_list.c | 10 +- .../testing/selftests/bpf/progs/linked_list.c | 2 +- .../selftests/bpf/progs/linked_list_fail.c | 100 +++++++++++------- 3 files changed, 68 insertions(+), 44 deletions(-)
tools/testing/selftests/bpf/prog_tests/linked_list.c +5 -5
@@ -78,18 +78,18 @@ static struct { { "direct_write_head", "direct access to bpf_list_head is disallowed" }, { "direct_read_node", "direct access to bpf_list_node is disallowed" }, { "direct_write_node", "direct access to bpf_list_node is disallowed" }, - { "write_after_push_front", "only read is supported" }, - { "write_after_push_back", "only read is supported" }, { "use_after_unlock_push_front", "invalid mem access 'scalar'" }, { "use_after_unlock_push_back", "invalid mem access 'scalar'" }, - { "double_push_front", "arg#1 expected pointer to allocated object" }, - { "double_push_back", "arg#1 expected pointer to allocated object" }, + { "double_push_front", + "release kernel function bpf_list_push_front expects refcounted PTR_TO_BTF_ID" }, + { "double_push_back", + "release kernel function bpf_list_push_back expects refcounted PTR_TO_BTF_ID" }, { "no_node_value_type", "bpf_list_node not found at offset=0" }, { "incorrect_value_type","operation on bpf_list_head expects arg#1 bpf_list_node at offset=0 in struct foo, " "but arg is at offset=0 in struct bar" }, { "incorrect_node_var_off", "variable ptr_ access var_off=(0x0; 0xffffffff) disallowed" }, - { "incorrect_node_off1", "bpf_list_node not found at offset=1" }, + { "incorrect_node_off1", "No graph node or root found at R2 type:foo off:1" }, { "incorrect_node_off2", "arg#1 offset=40, but expected bpf_list_node at offset=0 in struct foo" }, { "no_head_type", "bpf_list_head not found at offset=0" }, { "incorrect_head_var_off1", "R1 doesn't have constant offset" },
tools/testing/selftests/bpf/progs/linked_list.c +1 -1
@@ -260,7 +260,7 @@ int test_list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head {int ret; - ret =list_push_pop_multiple (lock ,head, false); + ret =list_push_pop_multiple (lock, head, false);if (ret)return ret;return list_push_pop_multiple (lock, head, true);
tools/testing/selftests/bpf/progs/linked_list_fail.c +62 -38
135 lines not on this page · raw message
Signature · 1 line
2.30.2
PATCH v3 4/11 bpf: Add basic bpf_rb_{root,node} support
In reply to Dave MarchevskyThis 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
@@ -180,7 +180,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 {
@@ -284,6 +287,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" ;
@@ -304,6 +311,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 ;
@@ -324,6 +335,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 ;
@@ -434,6 +449,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
@@ -6912,6 +6912,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
@@ -527,9 +527,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)
@@ -538,7 +535,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 );
@@ -571,9 +572,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);
@@ -584,7 +582,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 ;
@@ -664,7 +666,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 );
@@ -1005,7 +1013,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;
@@ -1053,6 +1062,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
@@ -14429,9 +14429,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
@@ -6912,6 +6912,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 v3 5/11 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 | 28 ++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 14 +++++++++++++- 2 files changed, 41 insertions(+), 1 deletion(-)
kernel/bpf/helpers.c +28 -0
@@ -1884,6 +1884,30 @@ 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; +} + +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)) +{ +rb_add_cached ((struct rb_node *)node, (struct rb_root_cached *)root, + (bool (*)(struct rb_node *,const struct rb_node *))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 +2132,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
@@ -8425,6 +8425,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)
@@ -8530,6 +8532,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)
@@ -8541,6 +8546,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)
@@ -8554,6 +8562,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) {
@@ -9306,7 +9317,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
PATCH v3 6/11 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
@@ -8308,6 +8308,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)
@@ -8419,6 +8422,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)
@@ -8460,6 +8465,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,
@@ -8519,6 +8534,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 {
@@ -8626,6 +8643,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",
@@ -8854,95 +8877,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 ; }
@@ -8950,6 +9071,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;
@@ -9081,6 +9220,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 */
@@ -9159,6 +9300,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);
@@ -9172,6 +9327,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 ||
@@ -14143,7 +14311,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 v3 7/11 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_lock 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 | 135 ++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 130 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +130 -5
@@ -192,6 +192,8 @@ 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,struct bpf_active_lock *lock); +static bool in_rbtree_lock_required_cb (struct bpf_verifier_env *env); +static int ref_set_non_owning_lock (struct bpf_verifier_env *env,struct bpf_reg_state *reg);
@@ -1494,6 +1496,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);
@@ -6509,6 +6521,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)
@@ -7118,6 +7134,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)
@@ -7172,10 +7190,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) &&
@@ -7440,6 +7466,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_lock (env, &callee->regs[BPF_REG_1 ]); +mark_reg_graph_node (callee->regs,BPF_REG_2 , &field->graph_root); +ref_set_non_owning_lock (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;
@@ -8297,6 +8380,7 @@ struct bpf_kfunc_call_arg_meta {bool r0_rdonly;u32 ret_btf_id;u64 r0_size; +u32 subprogno;struct {u64 value;bool found;
@@ -8475,6 +8559,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,
@@ -8534,6 +8630,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, };
@@ -8658,6 +8755,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;
@@ -8889,6 +8989,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)
@@ -9224,6 +9334,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 :
@@ -9375,6 +9486,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 ; } }
@@ -9503,6 +9617,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]);
@@ -14347,7 +14471,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 v3 8/11 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.
--- kernel/bpf/verifier.c | 29 +++++++++++++++++++++++------ 1 file changed, 23 insertions(+), 6 deletions(-)
kernel/bpf/verifier.c +23 -6
@@ -9443,10 +9443,20 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_verbose (env,"arg#%d expected pointer to allocated object\n" , i);return -EINVAL ; } -if (!reg->ref_obj_id) { +if (meta->func_id == special_kfunc_list[KF_bpf_rbtree_remove]) { +if (reg->ref_obj_id) { +verbose (env,"rbtree_remove node input must be non-owning ref\n" ); +return -EINVAL ; + } +if (in_rbtree_lock_required_cb (env)) { +verbose (env,"rbtree_remove not allowed in rbtree cb\n" ); +return -EINVAL ; + } + }else 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;
@@ -9691,11 +9701,12 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, meta.func_id == special_kfunc_list[KF_bpf_list_pop_back]) {struct btf_field *field = meta.arg_list_head.field; -mark_reg_known_zero (env, regs,BPF_REG_0 ); - regs[BPF_REG_0 ].type =PTR_TO_BTF_ID |MEM_ALLOC ; - regs[BPF_REG_0 ].btf = field->graph_root.btf; - regs[BPF_REG_0 ].btf_id = field->graph_root.value_btf_id; - regs[BPF_REG_0 ].off = field->graph_root.node_offset; +mark_reg_graph_node (regs,BPF_REG_0 , &field->graph_root); + } else if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_remove] || + meta.func_id == special_kfunc_list[KF_bpf_rbtree_first]) { +struct btf_field *field = meta.arg_rbtree_root.field; + +mark_reg_graph_node (regs,BPF_REG_0 , &field->graph_root); } else if (meta.func_id == special_kfunc_list[KF_bpf_cast_to_kern_ctx]) {mark_reg_known_zero (env, regs,BPF_REG_0 ); regs[BPF_REG_0 ].type =PTR_TO_BTF_ID |PTR_TRUSTED ;
@@ -9761,7 +9772,13 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,if (is_kfunc_ret_null (&meta)) regs[BPF_REG_0 ].id = id; regs[BPF_REG_0 ].ref_obj_id = id; + }else if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_first]) { +ref_set_non_owning_lock (env, ®s[BPF_REG_0 ]); } + +if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_remove]) +invalidate_non_owning_refs (env, &env->cur_state->active_lock); +if (reg_may_point_to_spin_lock (®s[BPF_REG_0 ]) && !regs[BPF_REG_0 ].id) regs[BPF_REG_0 ].id = ++env->id_gen; }/* else { add_kfunc_call() ensures it is btf_type_is_void(t) } */
Signature · 1 line
2.30.2
PATCH v3 9/11 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 v3 10/11 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 | 184 +++++++++++ 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 | 296 ++++++++++++++++++ 5 files changed, 757 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 +184 -0
@@ -0,0 +1,184 @@ +// 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 char log_buf[1024 *1024 ]; + +static struct { +const char *prog_name; +const char *err_msg; +} rbtree_fail_tests[] = { + {"rbtree_api_nolock_add" ,"bpf_spin_lock at off=16 must be held for bpf_rb_root" }, + {"rbtree_api_nolock_remove" ,"bpf_spin_lock at off=16 must be held for bpf_rb_root" }, + {"rbtree_api_nolock_first" ,"bpf_spin_lock at off=16 must be held for bpf_rb_root" }, + +/* Specific failure string for these three isn't very important, but it shouldn't be +* possible to call rbtree api func from within add() callback +*/ + {"rbtree_api_add_bad_cb_bad_fn_call_add" ,"allocated object must be referenced" }, + {"rbtree_api_add_bad_cb_bad_fn_call_remove" ,"rbtree_remove not allowed in rbtree cb" }, + {"rbtree_api_add_bad_cb_bad_fn_call_first_unlock_after" , +"can't spin_{lock,unlock} in rbtree cb" }, + + {"rbtree_api_remove_unadded_node" ,"rbtree_remove node input must be non-owning ref" }, + {"rbtree_api_add_to_multiple_trees" ,"allocated object must be referenced" }, + {"rbtree_api_add_release_unlock_escape" ,"arg#1 expected pointer to allocated object" }, + {"rbtree_api_first_release_unlock_escape" ,"arg#1 expected pointer to allocated object" }, + {"rbtree_api_remove_no_drop" ,"Unreleased reference id=2 alloc_insn=11" }, + {"rbtree_api_release_aliasing" ,"arg#1 expected pointer to allocated object" }, +}; + +static void test_rbtree_fail_prog (const char *prog_name,const char *err_msg) +{ +LIBBPF_OPTS (bpf_object_open_opts, opts, + .kernel_log_buf = log_buf, + .kernel_log_size = sizeof(log_buf), + .kernel_log_level = 1 + ); +struct rbtree_fail *skel; +struct bpf_program *prog; +int ret; + + skel =rbtree_fail__open_opts (&opts); +if (!ASSERT_OK_PTR (skel,"rbtree_fail__open_opts" )) +return ; + + prog =bpf_object__find_program_by_name (skel->obj, prog_name); +if (!ASSERT_OK_PTR (prog,"bpf_object__find_program_by_name" )) + goto end; + +bpf_program__set_autoload (prog, true); + + ret =rbtree_fail__load (skel); +if (!ASSERT_ERR (ret,"rbtree_fail__load must fail" )) + goto end; + +if (!ASSERT_OK_PTR (strstr (log_buf, err_msg),"expected error message" )) { +fprintf (stderr,"Expected: %s\n" , err_msg); +fprintf (stderr,"Verifier: %s\n" , log_buf); + } + +end: +rbtree_fail__destroy (skel); +} + +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 ) +{ +int i; + +for (i =0 ; i <ARRAY_SIZE (rbtree_fail_tests); i++) { +if (!test__start_subtest (rbtree_fail_tests[i].prog_name)) +continue ; +test_rbtree_fail_prog (rbtree_fail_tests[i].prog_name, + rbtree_fail_tests[i].err_msg); + } +}
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 +296 -0
296 lines not on this page · raw message
Signature · 1 line
2.30.2
PATCH v3 11/11 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 | 228 ++++++++++++++++++++++++++++ Documentation/bpf/other.rst | 3 +- 2 files changed, 230 insertions(+), 1 deletion(-) create mode 100644 Documentation/bpf/graph_ds_impl.rst
Documentation/bpf/graph_ds_impl.rst new file +228 -0
@@ -0,0 +1,228 @@ +========================= +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. + +Non-owning references +--------------------- + +**Motivation** + +Consider the following BPF code: + +.. code-block:: c + + struct node_data *n = bpf_obj_new(typeof(*n)); /* BEFORE */ + + bpf_spin_lock(&lock); + + bpf_rbtree_add(&tree, n); /* AFTER */ + + 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``. + +(``BEFORE`` and ``AFTER`` comments in the example denote beginning of "before +ownership is passed" and "after ownership is passed") + +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)); /* BEFORE */ + + bpf_spin_lock(&lock); + + bpf_rbtree_add(&tree, n); /* AFTER */ + 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 verifier type system +prevents such a state from being valid. + +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 datastructure + + * 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
Re: [PATCH v3 bpf-next 11/11] bpf, documentation: Add graph documentation for non-owning refs
Quoted 5 lines · Dave Marchevsky
It 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.
Quoted 7 lines
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.
Signed-off-by Dave Marchevsky <[email protected]>---
Whoops, I forgot to rebase in some of the changes David requested into this patch. Since I'm sending v4 soon I will add those in. Probably worth waiting until v4 to look at this patch.