Shared ownership for local kptrs
Subsystems (4)
v2 cover Shared ownership for local kptrs
This series adds support for refcounted local kptrs to the verifier. A local kptr is 'refcounted' if its type contains a struct bpf_refcount field:
struct refcounted_node {
long data;
struct bpf_list_node ll;
struct bpf_refcount ref;
};bpf_refcount is used to implement shared ownership for local kptrs.
Motivating usecase
==================
If a struct has two collection node fields, e.g.:
struct node {
long key;
long val;
struct bpf_rb_node rb;
struct bpf_list_node ll;
};It's not currently possible to add a node to both the list and rbtree:
long bpf_prog(void *ctx)
{
struct node *n = bpf_obj_new(typeof(*n));
if (!n) { /* ... */ } bpf_spin_lock(&lock);
bpf_list_push_back(&head, &n->ll);
bpf_rbtree_add(&root, &n->rb, less); /* Assume a resonable less() */
bpf_spin_unlock(&lock);}
The above program will fail verification due to current owning / non-owning ref
logic: after bpf_list_push_back, n is a non-owning reference and thus cannot be passed to bpf_rbtree_add. The only way to get an owning reference for the node that was added is to bpf_list_pop_{front,back} it.
More generally, verifier ownership semantics expect that a node has one owner (program, collection, or stashed in map) with exclusive ownership of the node's lifetime. The owner free's the node's underlying memory when it itself goes away.
Without a shared ownership concept it's impossible to express many real-world usecases such that they pass verification.
Semantic Changes
================
Before this series, the verifier could make this statement: "whoever has the owning reference has exclusive ownership of the referent's lifetime". As demonstrated in the previous section, this implies that a BPF program can't have an owning reference to some node if that node is in a collection. If such a state were possible, the node would have multiple owners, each thinking they have exclusive ownership. In order to support shared ownership it's necessary to modify the exclusive ownership semantic.
After this series' changes, an owning reference has ownership of the referent's lifetime, but it's not necessarily exclusive. The referent's underlying memory is guaranteed to be valid (i.e. not free'd) until the reference is dropped or used for collection insert.
This change doesn't affect UX of owning or non-owning references much:
* insert kfuncs (bpf_rbtree_add, bpf_list_push_{front,back}) still require an owning reference arg, as ownership still must be passed to the collection in a shared-ownership world.
* non-owning references still refer to valid memory without claiming any ownership.
One important conclusion that followed from "exclusive ownership" statement is no longer valid, though. In exclusive-ownership world, if a BPF prog has an owning reference to a node, the verifier can conclude that no collection has ownership of it. This conclusion was used to avoid runtime checking in the implementations of insert and remove operations (""has the node already been {inserted, removed}?").
In a shared-ownership world the aforementioned conclusion is no longer valid, which necessitates doing runtime checking in insert and remove operation kfuncs, and those functions possibly failing to insert or remove anything.
Luckily the verifier changes necessary to go from exclusive to shared ownership were fairly minimal. Patches in this series which do change verifier semantics generally have some summary dedicated to explaining why certain usecases Just Work for shared ownership without verifier changes.
Implementation
==============
The changes in this series can be categorized as follows:
* struct bpf_refcount opaque field + plumbing
* support for refcounted kptrs in bpf_obj_new and bpf_obj_drop
* bpf_refcount_acquire kfunc
* enables shared ownershp by bumping refcount + acquiring owning ref
* support for possibly-failing collection insertion and removal
* insertion changes are more complex
If a patch's changes have some nuance to their effect - or lack of effect - on verifier behavior, the patch summary talks about it at length.
Patch contents:
* Patch 1 removes btf_field_offs struct
* Patch 2 adds struct bpf_refcount and associated plumbing
* Patch 3 modifies semantics of bpf_obj_drop and bpf_obj_new to handle refcounted kptrs
* Patch 4 adds bpf_refcount_acquire
* Patches 5-7 add support for possibly-failing collection insert and remove
* Patch 8 centralizes constructor-like functionality for local kptr types
* Patch 9 adds tests for new functionality
base-commit: 4a1e885c6d143ff1b557ec7f3fc6ddf39c51502f
Changelog:
v1 -> v2: lore.kernel.org/bpf/[email protected]
Patch #s used below refer to the patch's position in v1 unless otherwise specified.
* General
* Rebase onto latest bpf-next (base-commit updated above)
* Patch 4 - "bpf: Add bpf_refcount_acquire kfunc"
* Fix typo in summary (Alexei)
* Patch 7 - "Migrate bpf_rbtree_remove to possibly fail"
* Modify a paragraph in patch summary to more clearly state that only bpf_rbtree_remove's non-owning ref clobbering behavior is changed by the patch (Alexei)
* refcount_off == -1 -> refcount_off < 0 in "node type w/ both list and rb_node fields" check, since any negative value means "no bpf_refcount field found", and furthermore refcount_off is never explicitly set to -1, but rather -EINVAL. (Alexei)
* Instead of just changing "btf: list_node and rb_node in same struct" test expectation to pass instead of fail, do some refactoring to test both "list_node, rb_node, and bpf_refcount" (success) and "list_node, rb_node, _no_ bpf_refcount" (failure) cases. This ensures that logic change in previous bullet point is correct.
* v1's "btf: list_node and rb_node in same struct" test changes didn't add bpf_refcount, so the fact that btf load succeeded w/ list and rb_nodes but no bpf_refcount field is further proof that this logic was incorrect in v1.
* Patch 8 - "bpf: Centralize btf_field-specific initialization logic"
* Instead of doing __init_field_infer_size in kfuncs when taking bpf_list_head type input which might've been 0-initialized in map, go back to simple oneliner initialization. Add short comment explaining why this is necessary. (Alexei)
* Patch 9 - "selftests/bpf: Add refcounted_kptr tests"
* Don't __always_inline helper fns in progs/refcounted_kptr.c (Alexei)
Dave Marchevsky (9):
bpf: Remove btf_field_offs, use btf_record's fields instead
bpf: Introduce opaque bpf_refcount struct and add btf_record plumbing
bpf: Support refcounted local kptrs in existing semantics
bpf: Add bpf_refcount_acquire kfunc
bpf: Migrate bpf_rbtree_add and bpf_list_push_{front,back} to possibly
fail
selftests/bpf: Modify linked_list tests to work with macro-ified
inserts
bpf: Migrate bpf_rbtree_remove to possibly fail
bpf: Centralize btf_field-specific initialization logic selftests/bpf: Add refcounted_kptr tests
include/linux/bpf.h | 80 ++-- include/linux/bpf_verifier.h | 7 +- include/linux/btf.h | 2 - include/uapi/linux/bpf.h | 4 + kernel/bpf/btf.c | 126 ++---- kernel/bpf/helpers.c | 113 +++-- kernel/bpf/map_in_map.c | 15 - kernel/bpf/syscall.c | 23 +- kernel/bpf/verifier.c | 155 +++++-- tools/include/uapi/linux/bpf.h | 4 + .../testing/selftests/bpf/bpf_experimental.h | 60 ++- .../selftests/bpf/prog_tests/linked_list.c | 96 +++-- .../testing/selftests/bpf/prog_tests/rbtree.c | 25 ++ .../bpf/prog_tests/refcounted_kptr.c | 18 + .../testing/selftests/bpf/progs/linked_list.c | 34 +- .../testing/selftests/bpf/progs/linked_list.h | 4 +- .../selftests/bpf/progs/linked_list_fail.c | 96 +++-- tools/testing/selftests/bpf/progs/rbtree.c | 74 +++- .../testing/selftests/bpf/progs/rbtree_fail.c | 77 ++-- .../selftests/bpf/progs/refcounted_kptr.c | 406 ++++++++++++++++++ .../bpf/progs/refcounted_kptr_fail.c | 72 ++++ 21 files changed, 1114 insertions(+), 377 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/refcounted_kptr.c create mode 100644 tools/testing/selftests/bpf/progs/refcounted_kptr.c create mode 100644 tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c
Signature · 1 line
2.34.1
PATCH v2 1/9 bpf: Remove btf_field_offs, use btf_record's fields instead
The btf_field_offs struct contains (offset, size) for btf_record fields, sorted by offset. btf_field_offs is always used in conjunction with btf_record, which has btf_field 'fields' array with (offset, type), the latter of which btf_field_offs' size is derived from via btf_field_type_size.
This patch adds a size field to struct btf_field and sorts btf_record's fields by offset, making it possible to get rid of btf_field_offs. Less data duplication and less code complexity results.
Since btf_field_offs' lifetime closely followed the btf_record used to populate it, most complexity wins are from removal of initialization code like:
if (btf_record_successfully_initialized) {
foffs = btf_parse_field_offs(rec);
if (IS_ERR_OR_NULL(foffs))
// free the btf_record and return err
}Other changes in this patch are pretty mechanical:
* foffs->field_off[i] -> rec->fields[i].offset
* foffs->field_sz[i] -> rec->fields[i].size
* Sort rec->fields in btf_parse_fields before returning
* It's possible that this is necessary independently of other changes in this patch. btf_record_find in syscall.c expects btf_record's fields to be sorted by offset, yet there's no explicit sorting of them before this patch, record's fields are populated in the order they're read from BTF struct definition. BTF docs don't say anything about the sortedness of struct fields.
* All functions taking struct btf_field_offs * input now instead take struct btf_record *. All callsites of these functions already have access to the correct btf_record.
--- include/linux/bpf.h | 44 +++++++++---------- include/linux/btf.h | 2 - kernel/bpf/btf.c | 93 ++++++++++------------------------------- kernel/bpf/helpers.c | 2 +- kernel/bpf/map_in_map.c | 15 ------- kernel/bpf/syscall.c | 17 +------- 6 files changed, 43 insertions(+), 130 deletions(-)
include/linux/bpf.h +19 -25
@@ -210,6 +210,7 @@ struct btf_field_graph_root {struct btf_field {u32 offset; +u32 size;enum btf_field_type type;union {struct btf_field_kptr kptr;
@@ -225,12 +226,6 @@ struct btf_record {struct btf_field fields[]; }; -struct btf_field_offs { -u32 cnt; -u32 field_off[BTF_FIELDS_MAX ]; -u8 field_sz[BTF_FIELDS_MAX ]; -}; -struct bpf_map {/* The first two cachelines with read-mostly members of which some * are also accessed in fast-path (e.g. ops, max_entries).
@@ -257,7 +252,6 @@ struct bpf_map {struct obj_cgroup *objcg;#endif char name[BPF_OBJ_NAME_LEN ]; -struct btf_field_offs *field_offs;/* The 3rd and 4th cacheline with misc members to avoid false sharing * particularly with refcounting. */
@@ -360,14 +354,14 @@ static inline bool btf_record_has_field(const struct btf_record *rec, enum btf_freturn rec->field_mask & type; } -static inline void bpf_obj_init (const struct btf_field_offs *foffs,void *obj) +static inline void bpf_obj_init (const struct btf_record *rec,void *obj) {int i; -if (!foffs) +if (IS_ERR_OR_NULL (rec))return ; -for (i =0 ; i < foffs->cnt; i++) -memset (obj + foffs->field_off[i],0 , foffs->field_sz[i]); +for (i =0 ; i < rec->cnt; i++) +memset (obj + rec->fields[i].offset,0 , rec->fields[i].size); }/* 'dst' must be a temporary buffer and should not point to memory that is being
@@ -379,7 +373,7 @@ static inline void bpf_obj_init(const struct btf_field_offs *foffs, void *obj)*/ static inline void check_and_init_map_value (struct bpf_map *map,void *dst) { -bpf_obj_init (map->field_offs, dst); +bpf_obj_init (map->record, dst); }/* memcpy that is used with 8-byte aligned pointers, power-of-8 size and
@@ -399,14 +393,14 @@ static inline void bpf_long_memcpy(void *dst, const void *src, u32 size) }/* copy everything but bpf_spin_lock, bpf_timer, and kptrs. There could be one of each. */ -static inline void bpf_obj_memcpy (struct btf_field_offs *foffs, +static inline void bpf_obj_memcpy (struct btf_record *rec,void *dst,void *src,u32 size,bool long_memcpy) {u32 curr_off =0 ;int i; -if (likely (!foffs)) { +if (IS_ERR_OR_NULL (rec)) {if (long_memcpy)bpf_long_memcpy (dst, src,round_up (size,8 ));else
@@ -414,49 +408,49 @@ static inline void bpf_obj_memcpy(struct btf_field_offs *foffs,return ; } -for (i =0 ; i < foffs->cnt; i++) { -u32 next_off = foffs->field_off[i]; +for (i =0 ; i < rec->cnt; i++) { +u32 next_off = rec->fields[i].offset;u32 sz = next_off - curr_off;memcpy (dst + curr_off, src + curr_off, sz); - curr_off += foffs->field_sz[i] + sz; + curr_off += rec->fields[i].size + sz; }memcpy (dst + curr_off, src + curr_off, size - curr_off); }static inline void copy_map_value (struct bpf_map *map,void *dst,void *src) { -bpf_obj_memcpy (map->field_offs, dst, src, map->value_size, false); +bpf_obj_memcpy (map->record, dst, src, map->value_size, false); }static inline void copy_map_value_long (struct bpf_map *map,void *dst,void *src) { -bpf_obj_memcpy (map->field_offs, dst, src, map->value_size, true); +bpf_obj_memcpy (map->record, dst, src, map->value_size, true); } -static inline void bpf_obj_memzero (struct btf_field_offs *foffs,void *dst,u32 size) +static inline void bpf_obj_memzero (struct btf_record *rec,void *dst,u32 size) {u32 curr_off =0 ;int i; -if (likely (!foffs)) { +if (IS_ERR_OR_NULL (rec)) {memset (dst,0 , size);return ; } -for (i =0 ; i < foffs->cnt; i++) { -u32 next_off = foffs->field_off[i]; +for (i =0 ; i < rec->cnt; i++) { +u32 next_off = rec->fields[i].offset;u32 sz = next_off - curr_off;memset (dst + curr_off,0 , sz); - curr_off += foffs->field_sz[i] + sz; + curr_off += rec->fields[i].size + sz; }memset (dst + curr_off,0 , size - curr_off); }static inline void zero_map_value (struct bpf_map *map,void *dst) { -bpf_obj_memzero (map->field_offs, dst, map->value_size); +bpf_obj_memzero (map->record, dst, map->value_size); } void copy_map_value_locked(struct bpf_map *map, void *dst, void *src,
include/linux/btf.h +0 -2
@@ -113,7 +113,6 @@ struct btf_id_dtor_kfunc {struct btf_struct_meta {u32 btf_id;struct btf_record *record; -struct btf_field_offs *field_offs; };struct btf_struct_metas {
@@ -207,7 +206,6 @@ int btf_find_timer(const struct btf *btf, const struct btf_type *t);struct btf_record *btf_parse_fields (const struct btf *btf,const struct btf_type *t,u32 field_mask,u32 value_size);int btf_check_and_fixup_fields (const struct btf *btf,struct btf_record *rec); -struct btf_field_offs *btf_parse_field_offs (struct btf_record *rec);bool btf_type_is_void (const struct btf_type *t);s32 btf_find_by_name_kind (const struct btf *btf,const char *name,u8 kind); const struct btf_type *btf_type_skip_modifiers(const struct btf *btf,
kernel/bpf/btf.c +21 -72
152 lines not on this page · raw message
kernel/bpf/helpers.c +1 -1
@@ -1893,7 +1893,7 @@ __bpf_kfunc void *bpf_obj_new_impl(u64 local_type_id__k, void *meta__ign)if (!p)return NULL ;if (meta) -bpf_obj_init (meta->field_offs, p); +bpf_obj_init (meta->record, p);return p; }
kernel/bpf/map_in_map.c +0 -15
@@ -56,18 +56,6 @@ struct bpf_map *bpf_map_meta_alloc(int inner_map_ufd) ret =PTR_ERR (inner_map_meta->record); goto free; } -if (inner_map_meta->record) { -struct btf_field_offs *field_offs; -/* If btf_record is !IS_ERR_OR_NULL, then field_offs is always -* valid. -*/ - field_offs =kmemdup (inner_map->field_offs,sizeof (*inner_map->field_offs),GFP_KERNEL | __GFP_NOWARN); -if (!field_offs) { - ret = -ENOMEM ; - goto free_rec; - } - inner_map_meta->field_offs = field_offs; - }/* Note: We must use the same BTF, as we also used btf_record_dup above * which relies on BTF being same for both maps, as some members like * record->fields.list_head have pointers like value_rec pointing into
@@ -88,8 +76,6 @@ struct bpf_map *bpf_map_meta_alloc(int inner_map_ufd)fdput (f);return inner_map_meta; -free_rec: -btf_record_free (inner_map_meta->record); free:kfree (inner_map_meta); put:
@@ -99,7 +85,6 @@ struct bpf_map *bpf_map_meta_alloc(int inner_map_ufd)void bpf_map_meta_free (struct bpf_map *map_meta) { -kfree (map_meta->field_offs);bpf_map_free_record (map_meta);btf_put (map_meta->btf);kfree (map_meta);
kernel/bpf/syscall.c +2 -15
@@ -717,14 +717,13 @@ void bpf_obj_free_fields(const struct btf_record *rec, void *obj)static void bpf_map_free_deferred (struct work_struct *work) { struct bpf_map *map = container_of(work, struct bpf_map, work); -struct btf_field_offs *foffs = map->field_offs;struct btf_record *rec = map->record;security_bpf_map_free (map);bpf_map_release_memcg (map);/* implementation dependent freeing */ map->ops->map_free (map); -/* Delay freeing of field_offs and btf_record for maps, as map_free +/* Delay freeing of btf_record for maps, as map_free * callback usually needs access to them. It is better to do it here * than require each callback to do the free itself manually. *
@@ -733,7 +732,6 @@ static void bpf_map_free_deferred(struct work_struct *work)* eventually calls bpf_map_free_meta, since inner_map_meta is only a * template bpf_map struct used during verification. */ -kfree (foffs);btf_record_free (rec); }
@@ -1125,7 +1123,6 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf,static int map_create (union bpf_attr *attr) {int numa_node =bpf_map_attr_numa_node (attr); -struct btf_field_offs *foffs;struct bpf_map *map;int f_flags;int err;
@@ -1205,17 +1202,9 @@ static int map_create(union bpf_attr *attr) attr->btf_vmlinux_value_type_id; } - - foffs =btf_parse_field_offs (map->record); -if (IS_ERR (foffs)) { - err =PTR_ERR (foffs); - goto free_map; - } - map->field_offs = foffs; - err =security_bpf_map_alloc (map);if (err) - goto free_map_field_offs; + goto free_map; err =bpf_map_alloc_id (map);if (err)
@@ -1239,8 +1228,6 @@ static int map_create(union bpf_attr *attr) free_map_sec:security_bpf_map_free (map); -free_map_field_offs: -kfree (map->field_offs); free_map:btf_put (map->btf); map->ops->map_free (map);
Signature · 1 line
2.34.1
PATCH v2 2/9 bpf: Introduce opaque bpf_refcount struct and add btf_record plumbing
In reply to Dave MarchevskyA 'struct bpf_refcount' is added to the set of opaque uapi/bpf.h types meant for use in BPF programs. Similarly to other opaque types like bpf_spin_lock and bpf_rbtree_node, the verifier needs to know where in user-defined struct types a bpf_refcount can be located, so necessary btf_record plumbing is added to enable this. bpf_refcount is sized to hold a refcount_t.
Similarly to bpf_spin_lock, the offset of a bpf_refcount is cached in btf_record as refcount_off in addition to being in the field array. Caching refcount_off makes sense for this field because further patches in the series will modify functions that take local kptrs (e.g. bpf_obj_drop) to change their behavior if the type they're operating on is refcounted. So enabling fast "is this type refcounted?" checks is desirable.
No such verifier behavior changes are introduced in this patch, just logic to recognize 'struct bpf_refcount' in btf_record.
--- include/linux/bpf.h | 8 ++++++++ include/uapi/linux/bpf.h | 4 ++++ kernel/bpf/btf.c | 12 +++++++++++- kernel/bpf/syscall.c | 6 +++++- tools/include/uapi/linux/bpf.h | 4 ++++ 5 files changed, 32 insertions(+), 2 deletions(-)
include/linux/bpf.h +8 -0
@@ -187,6 +187,7 @@ enum btf_field_type {BPF_RB_NODE = (1 <<7 ),BPF_GRAPH_NODE_OR_ROOT =BPF_LIST_NODE |BPF_LIST_HEAD |BPF_RB_NODE |BPF_RB_ROOT , + BPF_REFCOUNT = (1 << 8), };typedef void (*btf_dtor_kfunc_t )(void *);
@@ -223,6 +224,7 @@ struct btf_record {u32 field_mask;int spin_lock_off;int timer_off; +int refcount_off;struct btf_field fields[]; };
@@ -293,6 +295,8 @@ static inline const char *btf_field_type_name(enum btf_field_type type)return "bpf_rb_root" ;case BPF_RB_NODE :return "bpf_rb_node" ; +case BPF_REFCOUNT : +return "bpf_refcount" ;default :WARN_ON_ONCE (1 );return "unknown" ;
@@ -317,6 +321,8 @@ static inline u32 btf_field_type_size(enum btf_field_type type)return sizeof (struct bpf_rb_root );case BPF_RB_NODE :return sizeof (struct bpf_rb_node ); +case BPF_REFCOUNT : +return sizeof (struct bpf_refcount );default :WARN_ON_ONCE (1 );return 0 ;
@@ -341,6 +347,8 @@ static inline u32 btf_field_type_align(enum btf_field_type type)return __alignof__(struct bpf_rb_root );case BPF_RB_NODE :return __alignof__(struct bpf_rb_node ); +case BPF_REFCOUNT : +return __alignof__(struct bpf_refcount );default :WARN_ON_ONCE (1 );return 0 ;
include/uapi/linux/bpf.h +4 -0
@@ -6985,6 +6985,10 @@ struct bpf_rb_node { __u64 :64 ; } __attribute__((aligned(8))); +struct bpf_refcount { + __u32 :32; +} __attribute__((aligned (4 ))); +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 +11 -1
@@ -3391,6 +3391,7 @@ static int btf_get_field_type(const char *name, u32 field_mask, u32 *seen_mask,field_mask_test_name (BPF_LIST_NODE ,"bpf_list_node" );field_mask_test_name (BPF_RB_ROOT ,"bpf_rb_root" );field_mask_test_name (BPF_RB_NODE ,"bpf_rb_node" ); +field_mask_test_name (BPF_REFCOUNT ,"bpf_refcount" );/* Only return BPF_KPTR when all other types with matchable names fail */ if (field_mask &BPF_KPTR ) {
@@ -3439,6 +3440,7 @@ static int btf_find_struct_field(const struct btf *btf,case BPF_TIMER :case BPF_LIST_NODE :case BPF_RB_NODE : +case BPF_REFCOUNT : ret =btf_find_struct (btf, member_type, off, sz, field_type, idx < info_cnt ? &info[idx] : &tmp);if (ret <0 )
@@ -3504,6 +3506,7 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,case BPF_TIMER :case BPF_LIST_NODE :case BPF_RB_NODE : +case BPF_REFCOUNT : ret =btf_find_struct (btf, var_type, off, sz, field_type, idx < info_cnt ? &info[idx] : &tmp);if (ret <0 )
@@ -3734,6 +3737,7 @@ struct btf_record *btf_parse_fields(const struct btf *btf, const struct btf_type rec->spin_lock_off = -EINVAL ; rec->timer_off = -EINVAL ; + rec->refcount_off = -EINVAL ;for (i =0 ; i < cnt; i++) { field_type_size =btf_field_type_size (info_arr[i].type);if (info_arr[i].off + field_type_size > value_size) {
@@ -3763,6 +3767,11 @@ struct btf_record *btf_parse_fields(const struct btf *btf, const struct btf_type/* Cache offset for faster lookup at runtime */ rec->timer_off = rec->fields[i].offset;break ; +case BPF_REFCOUNT : +WARN_ON_ONCE (rec->refcount_off >=0 ); +/* Cache offset for faster lookup at runtime */ + rec->refcount_off = rec->fields[i].offset; +break ;case BPF_KPTR_UNREF :case BPF_KPTR_REF : ret =btf_parse_kptr (btf, &rec->fields[i], &info_arr[i]);
@@ -5308,6 +5317,7 @@ static const char *alloc_obj_fields[] = {"bpf_list_node" ,"bpf_rb_root" ,"bpf_rb_node" , + "bpf_refcount", }; static struct btf_struct_metas *
@@ -5381,7 +5391,7 @@ btf_parse_struct_metas(struct bpf_verifier_log *log, struct btf *btf) type = &tab->types[tab->cnt]; type->btf_id = i; record =btf_parse_fields (btf, t,BPF_SPIN_LOCK |BPF_LIST_HEAD |BPF_LIST_NODE | -BPF_RB_ROOT |BPF_RB_NODE , t->size); +BPF_RB_ROOT |BPF_RB_NODE |BPF_REFCOUNT , t->size);/* The record cannot be unset, treat it as an error if so */ if (IS_ERR_OR_NULL (record)) { ret =PTR_ERR_OR_ZERO (record) ?: -EFAULT ;
kernel/bpf/syscall.c +5 -1
@@ -552,6 +552,7 @@ void btf_record_free(struct btf_record *rec)case BPF_RB_NODE :case BPF_SPIN_LOCK :case BPF_TIMER : +case BPF_REFCOUNT :/* Nothing to release */ break ;default :
@@ -599,6 +600,7 @@ struct btf_record *btf_record_dup(const struct btf_record *rec)case BPF_RB_NODE :case BPF_SPIN_LOCK :case BPF_TIMER : +case BPF_REFCOUNT :/* Nothing to acquire */ break ;default :
@@ -705,6 +707,7 @@ void bpf_obj_free_fields(const struct btf_record *rec, void *obj)break ;case BPF_LIST_NODE :case BPF_RB_NODE : +case BPF_REFCOUNT :break ;default :WARN_ON_ONCE (1 );
@@ -1032,7 +1035,7 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf, map->record =btf_parse_fields (btf, value_type,BPF_SPIN_LOCK |BPF_TIMER |BPF_KPTR |BPF_LIST_HEAD | -BPF_RB_ROOT , +BPF_RB_ROOT |BPF_REFCOUNT , map->value_size);if (!IS_ERR_OR_NULL (map->record)) {int i;
@@ -1071,6 +1074,7 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf,break ;case BPF_KPTR_UNREF :case BPF_KPTR_REF : +case BPF_REFCOUNT : if (map->map_type != BPF_MAP_TYPE_HASH && map->map_type != BPF_MAP_TYPE_PERCPU_HASH && map->map_type != BPF_MAP_TYPE_LRU_HASH &&
tools/include/uapi/linux/bpf.h +4 -0
@@ -6985,6 +6985,10 @@ struct bpf_rb_node { __u64 :64 ; } __attribute__((aligned(8))); +struct bpf_refcount { + __u32 :32; +} __attribute__((aligned (4 ))); +struct bpf_sysctl {__u32 write;/* Sysctl is being read (= 0) or written (= 1). * Allows 1,2,4-byte read, but no write.
Signature · 1 line
2.34.1
PATCH v2 3/9 bpf: Support refcounted local kptrs in existing semantics
In reply to Dave MarchevskyA local kptr is considered 'refcounted' when it is of a type that has a bpf_refcount field. When such a kptr is created, its refcount should be initialized to 1; when destroyed, the object should be free'd only if a refcount decr results in 0 refcount.
Existing logic always frees the underlying memory when destroying a local kptr, and 0-initializes all btf_record fields. This patch adds checks for "is local kptr refcounted?" and new logic for that case in the appropriate places.
This patch focuses on changing existing semantics and thus conspicuously does _not_ provide a way for BPF programs in increment refcount. That follows later in the series.
__bpf_obj_drop_impl is modified to do the right thing when it sees a refcounted type. Container types for graph nodes (list, tree, stashed in map) are migrated to use __bpf_obj_drop_impl as a destructor for their nodes instead of each having custom destruction code in their _free paths. Now that "drop" isn't a synonym for "free" when the type is refcounted it makes sense to centralize this logic.
--- include/linux/bpf.h | 3 +++ kernel/bpf/helpers.c | 21 +++++++++++++-------- 2 files changed, 16 insertions(+), 8 deletions(-)
include/linux/bpf.h +3 -0
@@ -370,6 +370,9 @@ static inline void bpf_obj_init(const struct btf_record *rec, void *obj)return ;for (i =0 ; i < rec->cnt; i++)memset (obj + rec->fields[i].offset,0 , rec->fields[i].size); + +if (rec->refcount_off >=0 ) +refcount_set ((refcount_t *)(obj + rec->refcount_off),1 ); }/* 'dst' must be a temporary buffer and should not point to memory that is being
kernel/bpf/helpers.c +13 -8
@@ -1798,6 +1798,8 @@ bpf_base_func_proto(enum bpf_func_id func_id) } } +void __bpf_obj_drop_impl (void *p,const struct btf_record *rec); +void bpf_list_head_free (const struct btf_field *field,void *list_head,struct bpf_spin_lock *spin_lock) {
@@ -1828,13 +1830,8 @@ void bpf_list_head_free(const struct btf_field *field, void *list_head,/* The contained type can also have resources, including a * bpf_list_head which needs to be freed. */ -bpf_obj_free_fields (field->graph_root.value_rec, obj); -/* bpf_mem_free requires migrate_disable(), since we can be -* called from map free path as well apart from BPF program (as -* part of map ops doing bpf_obj_free_fields). -*/ migrate_disable (); -bpf_mem_free (&bpf_global_ma, obj); +__bpf_obj_drop_impl (obj, field->graph_root.value_rec);migrate_enable (); } }
@@ -1871,10 +1868,9 @@ void bpf_rb_root_free(const struct btf_field *field, void *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); +__bpf_obj_drop_impl (obj, field->graph_root.value_rec);migrate_enable (); } }
@@ -1897,8 +1893,17 @@ __bpf_kfunc void *bpf_obj_new_impl(u64 local_type_id__k, void *meta__ign)return p; } +/* Must be called under migrate_disable(), as required by bpf_mem_free */ void __bpf_obj_drop_impl (void *p,const struct btf_record *rec) { +if (rec && rec->refcount_off >=0 && + !refcount_dec_and_test ((refcount_t *)(p + rec->refcount_off))) { +/* Object is refcounted and refcount_dec didn't result in 0 +* refcount. Return without freeing the object +*/ +return ; + } +if (rec)bpf_obj_free_fields (rec, p);bpf_mem_free (&bpf_global_ma, p);
Signature · 1 line
2.34.1
PATCH v2 4/9 bpf: Add bpf_refcount_acquire kfunc
In reply to Dave MarchevskyCurrently, BPF programs can interact with the lifetime of refcounted local kptrs in the following ways:
bpf_obj_new - Initialize refcount to 1 as part of new object creation bpf_obj_drop - Decrement refcount and free object if it's 0 collection add - Pass ownership to the collection. No change to
refcount but collection is responsible for bpf_obj_dropping it
In order to be able to add a refcounted local kptr to multiple collections we need to be able to increment the refcount and acquire a new owning reference. This patch adds a kfunc, bpf_refcount_acquire, implementing such an operation.
bpf_refcount_acquire takes a refcounted local kptr and returns a new owning reference to the same underlying memory as the input. The input can be either owning or non-owning. To reinforce why this is safe, consider the following code snippets:
struct node *n = bpf_obj_new(typeof(*n)); // A
struct node *m = bpf_refcount_acquire(n); // B
In the above snippet, n will be alive with refcount=1 after (A), and since nothing changes that state before (B), it's obviously safe. If n is instead added to some rbtree, we can still safely refcount_acquire it:
struct node *n = bpf_obj_new(typeof(*n)); struct node *m; bpf_spin_lock(&glock); bpf_rbtree_add(&groot, &n->node, less); // A m = bpf_refcount_acquire(n); // B bpf_spin_unlock(&glock);
In the above snippet, after (A) n is a non-owning reference, and after
(B) m is an owning reference pointing to the same memory as n. Although n has no ownership of that memory's lifetime, it's guaranteed to be alive until the end of the critical section, and n would be clobbered if we were past the end of the critical section, so it's safe to bump refcount.
Implementation details:
* From verifier's perspective, bpf_refcount_acquire handling is similar to bpf_obj_new and bpf_obj_drop. Like the former, it returns a new owning reference matching input type, although like the latter, type can be inferred from concrete kptr input. Verifier changes in {check,fixup}_kfunc_call and check_kfunc_args are largely copied from aforementioned functions' verifier changes.
* An exception to the above is the new KF_ARG_PTR_TO_REFCOUNTED_KPTR arg, indicated by new "__refcounted_kptr" kfunc arg suffix. This is necessary in order to handle both owning and non-owning input without adding special-casing to "__alloc" arg handling. Also a convenient place to confirm that input type has bpf_refcount field.
* The implemented kfunc is actually bpf_refcount_acquire_impl, with 'hidden' second arg that the verifier sets to the type's struct_meta in fixup_kfunc_call.
--- kernel/bpf/helpers.c | 15 ++++ kernel/bpf/verifier.c | 74 ++++++++++++++++--- .../testing/selftests/bpf/bpf_experimental.h | 13 ++++ 3 files changed, 91 insertions(+), 11 deletions(-)
kernel/bpf/helpers.c +15 -0
@@ -1917,6 +1917,20 @@ __bpf_kfunc void bpf_obj_drop_impl(void *p__alloc, void *meta__ign)__bpf_obj_drop_impl (p, meta ? meta->record :NULL ); } +__bpf_kfunc void *bpf_refcount_acquire_impl(void *p__refcounted_kptr, void *meta__ign) +{ +struct btf_struct_meta *meta = meta__ign; +struct bpf_refcount *ref; + +/* Could just cast directly to refcount_t *, but need some code using +* bpf_refcount type so that it is emitted in vmlinux BTF +*/ + ref = (struct bpf_refcount *)p__refcounted_kptr + meta->record->refcount_off; + +refcount_inc ((refcount_t *)ref); +return (void *)p__refcounted_kptr; +} +static void __bpf_list_add (struct bpf_list_node *node,struct bpf_list_head *head,bool tail) {struct list_head *n = (void *)node, *h = (void *)head;
@@ -2276,6 +2290,7 @@ BTF_ID_FLAGS(func, crash_kexec, KF_DESTRUCTIVE)#endif BTF_ID_FLAGS(func, bpf_obj_new_impl, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_obj_drop_impl, KF_RELEASE) +BTF_ID_FLAGS(func, bpf_refcount_acquire_impl, KF_ACQUIRE) BTF_ID_FLAGS(func, bpf_list_push_front) BTF_ID_FLAGS(func, bpf_list_push_back)BTF_ID_FLAGS (func, bpf_list_pop_front,KF_ACQUIRE |KF_RET_NULL )
kernel/bpf/verifier.c +63 -11
169 lines not on this page · raw message
tools/testing/selftests/bpf/bpf_experimental.h +13 -0
@@ -37,6 +37,19 @@ extern void bpf_obj_drop_impl(void *kptr, void *meta) __ksym;/* Convenience macro to wrap over bpf_obj_drop_impl */ #define bpf_obj_drop (kptr) bpf_obj_drop_impl(kptr, NULL) +/* Description +* Increment the refcount on a refcounted local kptr, turning the +* non-owning reference input into an owning reference in the process. +* +* The 'meta' parameter is a hidden argument that is ignored. +* Returns +* An owning reference to the object pointed to by 'kptr' +*/ +extern void *bpf_refcount_acquire_impl (void *kptr,void *meta) __ksym; + +/* Convenience macro to wrap over bpf_refcount_acquire_impl */ +#define bpf_refcount_acquire (kptr) bpf_refcount_acquire_impl(kptr, NULL) +/* Description * Add a new entry to the beginning of the BPF linked list. * Returns
Signature · 1 line
2.34.1
PATCH v2 5/9 bpf: Migrate bpf_rbtree_add and bpf_list_push_{front,back} to possibly fail
In reply to Dave MarchevskyConsider this code snippet:
struct node {
long key;
bpf_list_node l;
bpf_rb_node r;
bpf_refcount ref;
}
int some_bpf_prog(void *ctx)
{
struct node *n = bpf_obj_new(/*...*/), *m; bpf_spin_lock(&glock);
bpf_rbtree_add(&some_tree, &n->r, /* ... */);
m = bpf_refcount_acquire(n);
bpf_rbtree_add(&other_tree, &m->r, /* ... */);
bpf_spin_unlock(&glock);
/* ... */}
After bpf_refcount_acquire, n and m point to the same underlying memory, and that node's bpf_rb_node field is being used by the some_tree insert, so overwriting it as a result of the second insert is an error. In order to properly support refcounted nodes, the rbtree and list insert functions must be allowed to fail. This patch adds such support.
The kfuncs bpf_rbtree_add, bpf_list_push_{front,back} are modified to return an int indicating success/failure, with 0 -> success, nonzero -> failure.
bpf_obj_drop on failure
=======================
Currently the only reason an insert can fail is the example above: the bpf_{list,rb}_node is already in use. When such a failure occurs, the insert kfuncs will bpf_obj_drop the input node. This allows the insert operations to logically fail without changing their verifier owning ref behavior, namely the unconditional release_reference of the input owning ref.
With insert that always succeeds, ownership of the node is always passed to the collection, since the node always ends up in the collection.
With a possibly-failed insert w/ bpf_obj_drop, ownership of the node is always passed either to the collection (success), or to bpf_obj_drop (failure). Regardless, it's correct to continue unconditionally releasing the input owning ref, as something is always taking ownership from the calling program on insert.
Keeping owning ref behavior unchanged results in a nice default UX for insert functions that can fail. If the program's reaction to a failed insert is "fine, just get rid of this owning ref for me and let me go on with my business", then there's no reason to check for failure since that's default behavior. e.g.:
long important_failures = 0;
int some_bpf_prog(void *ctx)
{
struct node *n, *m, *o; /* all bpf_obj_new'd */ bpf_spin_lock(&glock);
bpf_rbtree_add(&some_tree, &n->node, /* ... */);
bpf_rbtree_add(&some_tree, &m->node, /* ... */);
if (bpf_rbtree_add(&some_tree, &o->node, /* ... */)) {
important_failures++;
}
bpf_spin_unlock(&glock);}
If we instead chose to pass ownership back to the program on failed insert - by returning NULL on success or an owning ref on failure - programs would always have to do something with the returned ref on failure. The most likely action is probably "I'll just get rid of this owning ref and go about my business", which ideally would look like:
if (n = bpf_rbtree_add(&some_tree, &n->node, /* ... */))
bpf_obj_drop(n);But bpf_obj_drop isn't allowed in a critical section and inserts must occur within one, so in reality error handling would become a hard-to-parse mess.
For refcounted nodes, we can replicate the "pass ownership back to program on failure" logic with this patch's semantics, albeit in an ugly way:
struct node *n = bpf_obj_new(/* ... */), *m;
bpf_spin_lock(&glock);
m = bpf_refcount_acquire(n);
if (bpf_rbtree_add(&some_tree, &n->node, /* ... */)) {
/* Do something with m */
}
bpf_spin_unlock(&glock);
bpf_obj_drop(m);bpf_refcount_acquire is used to simulate "return owning ref on failure". This should be an uncommon occurrence, though.
Addition of two verifier-fixup'd args to collection inserts
===========================================================
The actual bpf_obj_drop kfunc isbpf_obj_drop_impl(void *, struct btf_struct_meta *), with bpf_obj_drop macro populating the second arg with 0 and the verifier later filling in the arg during insn fixup.
Because bpf_rbtree_add and bpf_list_push_{front,back} now might do bpf_obj_drop, these kfuncs need a btf_struct_meta parameter that can be passed to bpf_obj_drop_impl.
Similarly, because the 'node' param to those insert functions is the bpf_{list,rb}_node within the node type, and bpf_obj_drop expects a pointer to the beginning of the node, the insert functions need to be able to find the beginning of the node struct. A second verifier-populated param is necessary: the offset of {list,rb}_node within the node type.
These two new params allow the insert kfuncs to correctly call __bpf_obj_drop_impl:
beginning_of_node = bpf_rb_node_ptr - offset
if (already_inserted)
__bpf_obj_drop_impl(beginning_of_node, btf_struct_meta->record);Similarly to other kfuncs with "hidden" verifier-populated params, the insert functions are renamed with _impl prefix and a macro is provided for common usage. For example, bpf_rbtree_add kfunc is now bpf_rbtree_add_impl and bpf_rbtree_add is now a macro which sets "hidden" args to 0.
Due to the two new args BPF progs will need to be recompiled to work with the new _impl kfuncs.
This patch also rewrites the "hidden argument" explanation to more directly say why the BPF program writer doesn't need to populate the arguments with anything meaningful.
How does this new logic affect non-owning references?
=====================================================
Currently, non-owning refs are valid until the end of the critical section in which they're created. We can make this guarantee because, if a non-owning ref exists, the referent was added to some collection. The collection will drop() its nodes when it goes away, but it can't go away while our program is accessing it, so that's not a problem. If the referent is removed from the collection in the same CS that it was added in, it can't be bpf_obj_drop'd until after CS end. Those are the only two ways to free the referent's memory and neither can happen until after the non-owning ref's lifetime ends.
On first glance, having these collection insert functions potentially bpf_obj_drop their input seems like it breaks the "can't be bpf_obj_drop'd until after CS end" line of reasoning. But we care about the memory not being _freed_ until end of CS end, and a previous patch in the series modified bpf_obj_drop such that it doesn't free refcounted nodes until refcount == 0. So the statement can be more accurately rewritten as "can't be free'd until after CS end".
We can prove that this rewritten statement holds for any non-owning reference produced by collection insert functions:
* If the input to the insert function is _not_ refcounted
* We have an owning reference to the input, and can conclude it isn't in any collection
* Inserting a node in a collection turns owning refs into non-owning, and since our input type isn't refcounted, there's no way to obtain additional owning refs to the same underlying memory
* Because our node isn't in any collection, the insert operation cannot fail, so bpf_obj_drop will not execute
* If bpf_obj_drop is guaranteed not to execute, there's no risk of memory being free'd
* Otherwise, the input to the insert function is refcounted
* If the insert operation fails due to the node's list_head or rb_root already being in some collection, there was some previous successful insert which passed refcount to the collection
* We have an owning reference to the input, it must have been acquired via bpf_refcount_acquire, which bumped the refcount
* refcount must be >= 2 since there's a valid owning reference and the node is already in a collection
* Insert triggering bpf_obj_drop will decr refcount to >= 1, never resulting in a free
So although we may do bpf_obj_drop during the critical section, this will never result in memory being free'd, and no changes to non-owning ref logic are needed in this patch.
--- include/linux/bpf_verifier.h | 7 +- kernel/bpf/helpers.c | 65 ++++++++++++---- kernel/bpf/verifier.c | 78 +++++++++++++------ .../testing/selftests/bpf/bpf_experimental.h | 49 +++++++++--- 4 files changed, 148 insertions(+), 51 deletions(-)
include/linux/bpf_verifier.h +6 -1
@@ -464,7 +464,12 @@ struct bpf_insn_aux_data {*/ struct bpf_loop_inline_state loop_inline_state; }; -u64 obj_new_size;/* remember the size of type passed to bpf_obj_new to rewrite R1 */ +union { +/* remember the size of type passed to bpf_obj_new to rewrite R1 */ +u64 obj_new_size; +/* remember the offset of node field within type to rewrite */ +u64 insert_off; + };struct btf_struct_meta *kptr_struct_meta;u64 map_key_state;/* constant (32 bit) key tracking for maps */ int ctx_field_size;/* the ctx field size for load insn, maybe 0 */
kernel/bpf/helpers.c +48 -17
115 lines not on this page · raw message
kernel/bpf/verifier.c +55 -23
179 lines not on this page · raw message
tools/testing/selftests/bpf/bpf_experimental.h +39 -10
88 lines not on this page · raw message
Signature · 1 line
2.34.1
Re: [PATCH v2 bpf-next 5/9] bpf: Migrate bpf_rbtree_add and bpf_list_push_{front,back} to possibly fail
tools/testing/selftests/bpf/bpf_experimental.h extern struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root, · line 124
Quoted 8 lines · Dave Marchevsky
tools/testing/selftests/bpf/bpf_experimental.h +6
-2-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; +extern int bpf_rbtree_add_impl(struct bpf_rb_root *root, struct bpf_rb_node *node, + bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b), + void *meta, __u64 off) __ksym; + +/* Convenience macro to wrap over bpf_rbtree_add_impl */ +#define bpf_rbtree_add (head, node, less) bpf_rbtree_add_impl(head, node, less, NULL, 0)
Applied, but can we do better here?
It's not a new issue. We have the same inefficiency in bpf_obj_drop.
BPF program populates 1 or 2 extra registers, but the verifier patches the call insn with necessary values for R4 and R5 for bpf_rbtree_add_impl or R2 for bpf_obj_drop_impl. So one/two register assignments by bpf prog is a dead code.
Can we come up with a way to avoid this unnecessary register assignment in bpf prog? Can we keep
extern void bpf_rbtree_add(root, node, less) __ksym; ?
Both in the kernel and in bpf_experimental.h so that libbpf's bpf_object__resolve_ksym_func_btf_id() -> bpf_core_types_are_compat() check will succeed, but the kernel bpf_rbtree_add will actually have 5 arguments?
Maybe always_inline or __attribute__((alias(..))) trick we can use?
Or define both and patch bpf code to use _impl later ?
@@ -2053,6 +2053,12 @@ __bpf_kfunc int bpf_rbtree_add_impl(struct bpf_rb_root *root, struct bpf_rb_node
return __bpf_rbtree_add(root, node, (void *)less, meta ? meta->record : NULL, off);
}
+__bpf_kfunc notrace int 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))
+{
+ return 0;
+}
Only wastes 3 bytes of .text on x86 and extra BTF_KIND_FUNC in vmlinux BTF, but will save two registers assignment at run-time ?
Re: [PATCH v2 bpf-next 5/9] bpf: Migrate bpf_rbtree_add and bpf_list_push_{front,back} to possibly fail
Quoted 35 lines · Alexei Starovoitov
tools/testing/selftests/bpf/bpf_experimental.h extern struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root, · line 124
Quoted 8 lines · Dave Marchevsky
tools/testing/selftests/bpf/bpf_experimental.h +6
-2-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; +extern int bpf_rbtree_add_impl(struct bpf_rb_root *root, struct bpf_rb_node *node, + bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b), + void *meta, __u64 off) __ksym; + +/* Convenience macro to wrap over bpf_rbtree_add_impl */ +#define bpf_rbtree_add (head, node, less) bpf_rbtree_add_impl(head, node, less, NULL, 0)Applied, but can we do better here?
It's not a new issue. We have the same inefficiency inbpf_obj_drop.
BPF program populates 1 or 2 extra registers, but the verifier patches the call insn with necessary values for R4 and R5 forbpf_rbtree_add_implor R2 forbpf_obj_drop_impl. So one/two register assignments by bpf prog is a dead code.
Can we come up with a way to avoid this unnecessary register assignment in bpf prog? Can we keep
extern voidbpf_rbtree_add(root, node, less)__ksym; ?
Both in the kernel and inbpf_experimental.hso that libbpf'sbpf_object__resolve_ksym_func_btf_id()->bpf_core_types_are_compat()check will succeed, but the kernelbpf_rbtree_addwill actually have 5 arguments?
Maybealways_inlineor __attribute__((alias(..))) trick we can use?
Or define both and patch bpf code to use_impllater ?(quoted diff) +5
-0@@ -2053,6 +2053,12 @@ __bpf_kfunc int bpf_rbtree_add_impl(struct bpf_rb_root *root, struct bpf_rb_node return __bpf_rbtree_add(root, node, (void *)less, meta ? meta->record : NULL, off); } +__bpf_kfunc notrace int 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)) +{ + return 0; +} Only wastes 3 bytes of .text on x86 and extra BTF_KIND_FUNC in vmlinux BTF,
Quoted 1 line
but will save two registers assignment at run-time ?
I see what you mean, and agree that smarter patching of BPF insns is probably best way forward. Will give it a shot.
PATCH v2 6/9 selftests/bpf: Modify linked_list tests to work with macro-ified inserts
In reply to Dave MarchevskyThe linked_list tests use macros and function pointers to reduce code duplication. Earlier in the series, bpf_list_push_{front,back} were modified to be macros, expanding to invoke actual kfuncs bpf_list_push_{front,back}_impl. Due to this change, a code snippet like:
void (*p)(void *, void *) = (void *)&bpf_list_##op; p(hexpr, nexpr);
meant to do bpf_list_push_{front,back}(hexpr, nexpr), will no longer work as it's no longer valid to do &bpf_list_push_{front,back} since they're no longer functions.
This patch fixes issues of this type, along with two other minor changes
- one improvement and one fix - both related to the node argument to list_push_{front,back}.
* The fix: migration of list_push tests away from (void *, void *) func ptr uncovered that some tests were incorrectly passing pointer to node, not pointer to struct bpf_list_node within the node. This patch fixes such issues (CHECK(..., f) -> CHECK(..., &f->node))
* The improvement: In linked_list tests, the struct foo type has two list_node fields: node and node2, at byte offsets 0 and 40 within the struct, respectively. Currently node is used in ~all tests involving struct foo and lists. The verifier needs to do some work to account for the offset of bpf_list_node within the node type, so using node2 instead of node exercises that logic more in the tests. This patch migrates linked_list tests to use node2 instead of node.
--- .../selftests/bpf/prog_tests/linked_list.c | 6 +- .../testing/selftests/bpf/progs/linked_list.c | 34 +++---- .../testing/selftests/bpf/progs/linked_list.h | 4 +- .../selftests/bpf/progs/linked_list_fail.c | 96 ++++++++++--------- 4 files changed, 73 insertions(+), 67 deletions(-)
tools/testing/selftests/bpf/prog_tests/linked_list.c +3 -3
@@ -84,11 +84,11 @@ static struct { { "double_push_back", "arg#1 expected pointer to allocated object" }, { "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, " +"operation on bpf_list_head expects arg#1 bpf_list_node at offset=40 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_off2", "arg#1 offset=40, but expected bpf_list_node at offset=0 in struct foo" }, + { "incorrect_node_off1", "bpf_list_node not found at offset=41" }, + { "incorrect_node_off2", "arg#1 offset=0, but expected bpf_list_node at offset=40 in struct foo" }, { "no_head_type", "bpf_list_head not found at offset=0" }, { "incorrect_head_var_off1", "R1 doesn't have constant offset" }, { "incorrect_head_var_off2", "variable ptr_ access var_off=(0x0; 0xffffffff) disallowed" },
tools/testing/selftests/bpf/progs/linked_list.c +17 -17
@@ -25,7 +25,7 @@ int list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool l n =bpf_list_pop_front (head);bpf_spin_unlock (lock);if (n) { -bpf_obj_drop (container_of(n ,struct foo ,node )); +bpf_obj_drop (container_of(n ,struct foo ,node2 ));bpf_obj_drop (f);return 3 ; }
@@ -34,7 +34,7 @@ int list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool l n =bpf_list_pop_back (head);bpf_spin_unlock (lock);if (n) { -bpf_obj_drop (container_of(n ,struct foo ,node )); +bpf_obj_drop (container_of(n ,struct foo ,node2 ));bpf_obj_drop (f);return 4 ; }
@@ -42,7 +42,7 @@ int list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool lbpf_spin_lock (lock); f->data =42 ; -bpf_list_push_front (head, &f->node); +bpf_list_push_front (head, &f->node2);bpf_spin_unlock (lock);if (leave_in_map)return 0 ;
@@ -51,7 +51,7 @@ int list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool lbpf_spin_unlock (lock);if (!n)return 5 ; - f = container_of(n, struct foo, node); + f = container_of(n, struct foo, node2);if (f->data !=42 ) {bpf_obj_drop (f);return 6 ;
@@ -59,14 +59,14 @@ int list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool lbpf_spin_lock (lock); f->data =13 ; -bpf_list_push_front (head, &f->node); +bpf_list_push_front (head, &f->node2);bpf_spin_unlock (lock);bpf_spin_lock (lock); n =bpf_list_pop_front (head);bpf_spin_unlock (lock);if (!n)return 7 ; - f = container_of(n, struct foo, node); + f = container_of(n, struct foo, node2);if (f->data !=13 ) {bpf_obj_drop (f);return 8 ;
@@ -77,7 +77,7 @@ int list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool l n =bpf_list_pop_front (head);bpf_spin_unlock (lock);if (n) { -bpf_obj_drop (container_of(n ,struct foo ,node )); +bpf_obj_drop (container_of(n ,struct foo ,node2 ));return 9 ; }
@@ -85,7 +85,7 @@ int list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool l n =bpf_list_pop_back (head);bpf_spin_unlock (lock);if (n) { -bpf_obj_drop (container_of(n ,struct foo ,node )); +bpf_obj_drop (container_of(n ,struct foo ,node2 ));return 10 ; }return 0 ;
@@ -119,8 +119,8 @@ int list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *hea f[i +1 ]->data = i +1 ;bpf_spin_lock (lock); -bpf_list_push_front (head, &f[i]->node); -bpf_list_push_front (head, &f[i +1 ]->node); +bpf_list_push_front (head, &f[i]->node2); +bpf_list_push_front (head, &f[i +1 ]->node2);bpf_spin_unlock (lock); }
@@ -130,13 +130,13 @@ int list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *heabpf_spin_unlock (lock);if (!n)return 3 ; - pf = container_of(n, struct foo, node); + pf = container_of(n, struct foo, node2);if (pf->data != (ARRAY_SIZE (f) - i -1 )) {bpf_obj_drop (pf);return 4 ; }bpf_spin_lock (lock); -bpf_list_push_back (head, &pf->node); +bpf_list_push_back (head, &pf->node2);bpf_spin_unlock (lock); }
@@ -149,7 +149,7 @@ int list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *heabpf_spin_unlock (lock);if (!n)return 5 ; - pf = container_of(n, struct foo, node); + pf = container_of(n, struct foo, node2);if (pf->data != i) {bpf_obj_drop (pf);return 6 ;
@@ -160,7 +160,7 @@ int list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *hea n =bpf_list_pop_back (head);bpf_spin_unlock (lock);if (n) { -bpf_obj_drop (container_of(n ,struct foo ,node )); +bpf_obj_drop (container_of(n ,struct foo ,node2 ));return 7 ; }
@@ -168,7 +168,7 @@ int list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *hea n =bpf_list_pop_front (head);bpf_spin_unlock (lock);if (n) { -bpf_obj_drop (container_of(n ,struct foo ,node )); +bpf_obj_drop (container_of(n ,struct foo ,node2 ));return 8 ; }return 0 ;
@@ -199,7 +199,7 @@ int list_in_list(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool lebpf_spin_lock (lock); f->data =42 ; -bpf_list_push_front (head, &f->node); +bpf_list_push_front (head, &f->node2);bpf_spin_unlock (lock);if (leave_in_map)
@@ -210,7 +210,7 @@ int list_in_list(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool lebpf_spin_unlock (lock);if (!n)return 4 ; - f = container_of(n, struct foo, node); + f = container_of(n, struct foo, node2);if (f->data !=42 ) {bpf_obj_drop (f);return 5 ;
tools/testing/selftests/bpf/progs/linked_list.h +2 -2
@@ -22,7 +22,7 @@ struct foo {struct map_value {struct bpf_spin_lock lock;int data; - struct bpf_list_head head __contains(foo, node); + struct bpf_list_head head __contains(foo, node2); };struct array_map {
@@ -50,7 +50,7 @@ struct {#define private (name) SEC(".bss." #name) __hidden __attribute__((aligned(8))) private(A) struct bpf_spin_lock glock; -private(A) struct bpf_list_head ghead __contains(foo, node); +private(A) struct bpf_list_head ghead __contains(foo, node2); private(B) struct bpf_spin_lock glock2;#endif
tools/testing/selftests/bpf/progs/linked_list_fail.c +51 -45
211 lines not on this page · raw message
Signature · 1 line
2.34.1
PATCH v2 7/9 bpf: Migrate bpf_rbtree_remove to possibly fail
In reply to Dave MarchevskyThis patch modifies bpf_rbtree_remove to account for possible failure due to the input rb_node already not being in any collection. The function can now return NULL, and does when the aforementioned scenario occurs. As before, on successful removal an owning reference to the removed node is returned.
Adding KF_RET_NULL to bpf_rbtree_remove's kfunc flags - now KF_RET_NULL | KF_ACQUIRE - provides the desired verifier semantics:
* retval must be checked for NULL before use
* if NULL, retval's ref_obj_id is released
* retval is a "maybe acquired" owning ref, not a non-owning ref, so it will live past end of critical section (bpf_spin_unlock), and thus can be checked for NULL after the end of the CS
BPF programs must add checks
============================
This does change bpf_rbtree_remove's verifier behavior. BPF program writers will need to add NULL checks to their programs, but the resulting UX looks natural:
bpf_spin_lock(&glock);
n = bpf_rbtree_first(&ghead);
if (!n) { /* ... */}
res = bpf_rbtree_remove(&ghead, &n->node);
bpf_spin_unlock(&glock);if (!res) /* Newly-added check after this patch */
return 1;
n = container_of(res, /* ... */); /* Do something else with n */ bpf_obj_drop(n); return 0;
The "if (!res)" check above is the only addition necessary for the above program to pass verification after this patch.
bpf_rbtree_remove no longer clobbers non-owning refs
====================================================
An issue arises when bpf_rbtree_remove fails, though. Consider this example:
struct node_data {
long key;
struct bpf_list_node l;
struct bpf_rb_node r;
struct bpf_refcount ref;
}; long failed_sum;
void bpf_prog()
{
struct node_data *n = bpf_obj_new(/* ... */);
struct bpf_rb_node *res;
n->key = 10; bpf_spin_lock(&glock);
bpf_list_push_back(&some_list, &n->l); /* n is now a non-owning ref */
res = bpf_rbtree_remove(&some_tree, &n->r, /* ... */);
if (!res)
failed_sum += n->key; /* not possible */
bpf_spin_unlock(&glock);
/* if (res) { do something useful and drop } ... */}
The bpf_rbtree_remove in this example will always fail. Similarly to bpf_spin_unlock, bpf_rbtree_remove is a non-owning reference invalidation point. The verifier clobbers all non-owning refs after a bpf_rbtree_remove call, so the "failed_sum += n->key" line will fail verification, and in fact there's no good way to get information about the node which failed to add after the invalidation. This patch removes non-owning reference invalidation from bpf_rbtree_remove to allow the above usecase to pass verification. The logic for why this is now possible is as follows:
Before this series, bpf_rbtree_add couldn't fail and thus assumed that its input, a non-owning reference, was in the tree. But it's easy to construct an example where two non-owning references pointing to the same underlying memory are acquired and passed to rbtree_remove one after another (see rbtree_api_release_aliasing in selftests/bpf/progs/rbtree_fail.c).
So it was necessary to clobber non-owning refs to prevent this case and, more generally, to enforce "non-owning ref is definitely in some collection" invariant. This series removes that invariant and the failure / runtime checking added in this patch provide a clean way to deal with the aliasing issue - just fail to remove.
Because the aliasing issue prevented by clobbering non-owning refs is no longer an issue, this patch removes the invalidate_non_owning_refs call from verifier handling of bpf_rbtree_remove. Note that bpf_spin_unlock - the other caller of invalidate_non_owning_refs - clobbers non-owning refs for a different reason, so its clobbering behavior remains unchanged.
No BPF program changes are necessary for programs to remain valid as a result of this clobbering change. A valid program before this patch passed verification with its non-owning refs having shorter (or equal) lifetimes due to more aggressive clobbering.
Also, update existing tests to check bpf_rbtree_remove retval for NULL where necessary, and move rbtree_api_release_aliasing from progs/rbtree_fail.c to progs/rbtree.c since it's now expected to pass verification.
--- kernel/bpf/btf.c | 21 +---- kernel/bpf/helpers.c | 8 +- kernel/bpf/verifier.c | 3 - .../selftests/bpf/prog_tests/linked_list.c | 90 ++++++++++++------- .../testing/selftests/bpf/prog_tests/rbtree.c | 25 ++++++ tools/testing/selftests/bpf/progs/rbtree.c | 74 ++++++++++++++- .../testing/selftests/bpf/progs/rbtree_fail.c | 77 ++++++---------- 7 files changed, 191 insertions(+), 107 deletions(-)
kernel/bpf/btf.c +2 -19
@@ -3805,25 +3805,8 @@ 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 ) && +if (rec->refcount_off <0 && +btf_record_has_field (rec,BPF_LIST_NODE ) &&btf_record_has_field (rec,BPF_RB_NODE )) { ret = -EINVAL ; goto end;
kernel/bpf/helpers.c +7 -1
@@ -2000,6 +2000,12 @@ __bpf_kfunc struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root,struct rb_root_cached *r = (struct rb_root_cached *)root;struct rb_node *n = (struct rb_node *)node; +if (!n->__rb_parent_color) +RB_CLEAR_NODE (n); + +if (RB_EMPTY_NODE (n)) +return NULL ; +rb_erase_cached (n, r);RB_CLEAR_NODE (n);return (struct bpf_rb_node *)n;
@@ -2328,7 +2334,7 @@ BTF_ID_FLAGS(func, bpf_list_pop_front, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_pop_back, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_task_acquire, KF_ACQUIRE | KF_RCU | 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_remove, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_rbtree_add_impl)BTF_ID_FLAGS (func, bpf_rbtree_first,KF_RET_NULL )
kernel/bpf/verifier.c +0 -3
@@ -10922,9 +10922,6 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,ref_set_non_owning (env, ®s[BPF_REG_0 ]); } -if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_remove]) -invalidate_non_owning_refs (env); -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 if (btf_type_is_void (t)) {
tools/testing/selftests/bpf/prog_tests/linked_list.c +58 -32
103 lines not on this page · raw message
tools/testing/selftests/bpf/prog_tests/rbtree.c +25 -0
@@ -77,6 +77,29 @@ static void test_rbtree_first_and_remove(void)rbtree__destroy (skel); } +static void test_rbtree_api_release_aliasing (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_api_release_aliasing), &opts); +ASSERT_OK (ret,"rbtree_api_release_aliasing" ); +ASSERT_OK (opts.retval,"rbtree_api_release_aliasing retval" ); +ASSERT_EQ (skel->data->first_data[0 ],42 ,"rbtree_api_release_aliasing first rbtree_remove()" ); +ASSERT_EQ (skel->data->first_data[1 ],-1 ,"rbtree_api_release_aliasing second rbtree_remove()" ); + +rbtree__destroy (skel); +} +void test_rbtree_success (void ) {if (test__start_subtest ("rbtree_add_nodes" ))
@@ -85,6 +108,8 @@ void test_rbtree_success(void)test_rbtree_add_and_remove ();if (test__start_subtest ("rbtree_first_and_remove" ))test_rbtree_first_and_remove (); +if (test__start_subtest ("rbtree_api_release_aliasing" )) +test_rbtree_api_release_aliasing (); }#define BTF_FAIL_TEST (suffix) \
tools/testing/selftests/bpf/progs/rbtree.c +72 -2
94 lines not on this page · raw message
tools/testing/selftests/bpf/progs/rbtree_fail.c +27 -50
117 lines not on this page · raw message
Signature · 1 line
2.34.1
PATCH v2 8/9 bpf: Centralize btf_field-specific initialization logic
In reply to Dave MarchevskyAll btf_fields in an object are 0-initialized by memset in bpf_obj_init. This might not be a valid initial state for some field types, in which case kfuncs that use the type will properly initialize their input if it's been 0-initialized. Some BPF graph collection types and kfuncs do this: bpf_list_{head,node} and bpf_rb_node.
An earlier patch in this series added the bpf_refcount field, for which the 0 state indicates that the refcounted object should be free'd. bpf_obj_init treats this field specially, setting refcount to 1 instead of relying on scattered "refcount is 0? Must have just been initialized, let's set to 1" logic in kfuncs.
This patch extends this treatment to list and rbtree field types, allowing most scattered initialization logic in kfuncs to be removed.
Note that bpf_{list_head,rb_root} may be inside a BPF map, in which case they'll be 0-initialized without passing through the newly-added logic, so scattered initialization logic must remain for these collection root types.
--- include/linux/bpf.h | 33 +++++++++++++++++++++++++++++---- kernel/bpf/helpers.c | 14 ++++++-------- 2 files changed, 35 insertions(+), 12 deletions(-)
include/linux/bpf.h +29 -4
@@ -355,6 +355,34 @@ static inline u32 btf_field_type_align(enum btf_field_type type) } } +static inline void bpf_obj_init_field (const struct btf_field *field,void *addr) +{ +memset (addr,0 , field->size); + +switch (field->type) { +case BPF_REFCOUNT : +refcount_set ((refcount_t *)addr,1 ); +break ; +case BPF_RB_NODE : +RB_CLEAR_NODE ((struct rb_node *)addr); +break ; +case BPF_LIST_HEAD : +case BPF_LIST_NODE : +INIT_LIST_HEAD ((struct list_head *)addr); +break ; +case BPF_RB_ROOT : +/* RB_ROOT_CACHED 0-inits, no need to do anything after memset */ +case BPF_SPIN_LOCK : +case BPF_TIMER : +case BPF_KPTR_UNREF : +case BPF_KPTR_REF : +break ; +default : +WARN_ON_ONCE (1 ); +return ; + } +} +static inline bool btf_record_has_field (const struct btf_record *rec,enum btf_field_type type) {if (IS_ERR_OR_NULL (rec))
@@ -369,10 +397,7 @@ static inline void bpf_obj_init(const struct btf_record *rec, void *obj)if (IS_ERR_OR_NULL (rec))return ;for (i =0 ; i < rec->cnt; i++) -memset (obj + rec->fields[i].offset,0 , rec->fields[i].size); - -if (rec->refcount_off >=0 ) -refcount_set ((refcount_t *)(obj + rec->refcount_off),1 ); +bpf_obj_init_field (&rec->fields[i], obj + rec->fields[i].offset); }/* 'dst' must be a temporary buffer and should not point to memory that is being
kernel/bpf/helpers.c +6 -8
@@ -1936,10 +1936,11 @@ static int __bpf_list_add(struct bpf_list_node *node, struct bpf_list_head *head {struct list_head *n = (void *)node, *h = (void *)head; +/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't +* called on its fields, so init here +*/ if (unlikely (!h->next))INIT_LIST_HEAD (h); -if (unlikely (!n->next)) -INIT_LIST_HEAD (n);if (!list_empty (n)) {/* Only called from BPF prog, no need to migrate_disable */ __bpf_obj_drop_impl (n - off, rec);
@@ -1975,6 +1976,9 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool tai {struct list_head *n, *h = (void *)head; +/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't +* called on its fields, so init here +*/ if (unlikely (!h->next))INIT_LIST_HEAD (h);if (list_empty (h))
@@ -2000,9 +2004,6 @@ __bpf_kfunc struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root,struct rb_root_cached *r = (struct rb_root_cached *)root;struct rb_node *n = (struct rb_node *)node; -if (!n->__rb_parent_color) -RB_CLEAR_NODE (n); -if (RB_EMPTY_NODE (n))return NULL ;
@@ -2022,9 +2023,6 @@ static int __bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node,bpf_callback_t cb = (bpf_callback_t )less;bool leftmost = true; -if (!n->__rb_parent_color) -RB_CLEAR_NODE (n); -if (!RB_EMPTY_NODE (n)) {/* Only called from BPF prog, no need to migrate_disable */ __bpf_obj_drop_impl (n - off, rec);
Signature · 1 line
2.34.1
PATCH v2 9/9 selftests/bpf: Add refcounted_kptr tests
In reply to Dave MarchevskyTest refcounted local kptr functionality added in previous patches in the series.
Usecases which pass verification:
* Add refcounted local kptr to both tree and list. Then, read and - possibly, depending on test variant - delete from tree, then list.
* Also test doing read-and-maybe-delete in opposite order
* Stash a refcounted local kptr in a map_value, then add it to a rbtree. Read from both, possibly deleting after tree read.
* Add refcounted local kptr to both tree and list. Then, try reading and deleting twice from one of the collections.
* bpf_refcount_acquire of just-added non-owning ref should work, as should bpf_refcount_acquire of owning ref just out of bpf_obj_new
Usecases which fail verification:
* The simple successful bpf_refcount_acquire cases from above should both fail to verify if the newly-acquired owning ref is not dropped
--- .../bpf/prog_tests/refcounted_kptr.c | 18 + .../selftests/bpf/progs/refcounted_kptr.c | 406 ++++++++++++++++++ .../bpf/progs/refcounted_kptr_fail.c | 72 ++++ 3 files changed, 496 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/refcounted_kptr.c create mode 100644 tools/testing/selftests/bpf/progs/refcounted_kptr.c create mode 100644 tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c
tools/testing/selftests/bpf/prog_tests/refcounted_kptr.c new file +18 -0
@@ -0,0 +1,18 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */ + +#include <test_progs.h> +#include <network_helpers.h> + +#include "refcounted_kptr.skel.h" +#include "refcounted_kptr_fail.skel.h" + +void test_refcounted_kptr (void ) +{ +RUN_TESTS (refcounted_kptr); +} + +void test_refcounted_kptr_fail (void ) +{ +RUN_TESTS (refcounted_kptr_fail); +}
tools/testing/selftests/bpf/progs/refcounted_kptr.c new file +406 -0
406 lines not on this page · raw message
tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +72 -0
72 lines not on this page · raw message
Signature · 1 line
2.34.1
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH v2 bpf-next 9/9] selftests/bpf: Add refcounted_kptr tests
Quoted 27 lines · Dave Marchevsky
Test refcounted local kptr functionality added in previous patches in the series.
Usecases which pass verification:
* Add refcounted local kptr to both tree and list. Then, read and - possibly, depending on test variant - delete from tree, then list.
* Also test doing read-and-maybe-delete in opposite order
* Stash a refcounted local kptr in amap_value, then add it to a rbtree. Read from both, possibly deleting after tree read.
* Add refcounted local kptr to both tree and list. Then, try reading and deleting twice from one of the collections.
*bpf_refcount_acquireof just-added non-owning ref should work, as shouldbpf_refcount_acquireof owning ref just out ofbpf_obj_newUsecases which fail verification:
* The simple successful
bpf_refcount_acquirecases from above should both fail to verify if the newly-acquired owning ref is not droppedSigned-off-by Dave Marchevsky <[email protected]>---
[...]tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +4
-0+SEC("?tc") +__failure __msg("Unreleased reference id=3 alloc_insn=21") +long rbtree_refcounted_node_ref_escapes (void *ctx) +{
tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c line 44
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +10
-0+struct node_acquire *n, *m; + + n =bpf_obj_new (typeof (*n)); +if (!n) +return 1 ; + +bpf_spin_lock (&glock); +bpf_rbtree_add (&groot, &n->node, less); +/* m becomes an owning ref but is never drop'd or added to a tree */ + m =bpf_refcount_acquire (n);
I am analyzing the set (and I'll reply in detail to the cover letter), but this stood out.
Isn't this going to be problematic if n has refcount == 1 and is dropped internally by bpf_rbtree_add? Are we sure this can never occur? It took me some time, but the following schedule seems problematic.
CPU 0 CPU 1
n = bpf_obj_new
lock(lock1)bpf_rbtree_add(rbtree1, n)
m = bpf_rbtree_acquire(n)
unlock(lock1)
kptr_xchg(map, m) // move to map
// at this point, refcount = 2
m = kptr_xchg(map, NULL) lock(lock2)
lock(lock1) bpf_rbtree_add(rbtree2, m)
p = bpf_rbtree_first(rbtree1) if (!RB_EMPTY_NODE) bpf_obj_drop_impl(m) // Abpf_rbtree_remove(rbtree1, p)
unlock(lock1)bpf_obj_drop(p) // B
bpf_refcount_acquire(m) // use-after-free ...
B will decrement refcount from 1 to 0, after which bpf_refcount_acquire is basically performing a use-after-free (when fortunate, one will get a WARN_ON_ONCE splat for 0 to 1, otherwise, a silent refcount raise for some different object).
Re: [PATCH v2 bpf-next 9/9] selftests/bpf: Add refcounted_kptr tests
Quoted 55 lines · Kumar Kartikeya Dwivedi
Quoted 27 lines · Dave Marchevsky
Test refcounted local kptr functionality added in previous patches in the series.
Usecases which pass verification:
* Add refcounted local kptr to both tree and list. Then, read and - possibly, depending on test variant - delete from tree, then list.
* Also test doing read-and-maybe-delete in opposite order
* Stash a refcounted local kptr in amap_value, then add it to a rbtree. Read from both, possibly deleting after tree read.
* Add refcounted local kptr to both tree and list. Then, try reading and deleting twice from one of the collections.
*bpf_refcount_acquireof just-added non-owning ref should work, as shouldbpf_refcount_acquireof owning ref just out ofbpf_obj_newUsecases which fail verification:
* The simple successful
bpf_refcount_acquirecases from above should both fail to verify if the newly-acquired owning ref is not droppedSigned-off-by Dave Marchevsky <[email protected]>---
[...]tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +4
-0+SEC("?tc") +__failure __msg("Unreleased reference id=3 alloc_insn=21") +long rbtree_refcounted_node_ref_escapes (void *ctx) +{tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c line 44
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +10
-0+struct node_acquire *n, *m; + + n =bpf_obj_new (typeof (*n)); +if (!n) +return 1 ; + +bpf_spin_lock (&glock); +bpf_rbtree_add (&groot, &n->node, less); +/* m becomes an owning ref but is never drop'd or added to a tree */ + m =bpf_refcount_acquire (n);I am analyzing the set (and I'll reply in detail to the cover letter), but this stood out.
Isn't this going to be problematic if n has refcount == 1 and is dropped internally by
bpf_rbtree_add? Are we sure this can never occur? It took me some time, but the following schedule seems problematic.CPU 0 CPU 1
n =bpf_obj_new
lock(lock1)bpf_rbtree_add(rbtree1, n)
m =bpf_rbtree_acquire(n)
unlock(lock1)
kptr_xchg(map, m)// move to map
// at this point, refcount = 2
Quoted 7 lines
m = kptr_xchg(map, NULL) lock(lock2)lock(lock1)
bpf_rbtree_add(rbtree2, m)
p =bpf_rbtree_first(rbtree1)if (!RB_EMPTY_NODE)bpf_obj_drop_impl(m)// Abpf_rbtree_remove(rbtree1, p)
unlock(lock1)bpf_obj_drop(p)// B
You probably meant:
p2 = bpf_rbtree_remove(rbtree1, p)
unlock(lock1)
if (p2)
bpf_obj_drop(p2)
Quoted 7 lines
bpf_refcount_acquire(m) // use-after-free ...B will decrement refcount from 1 to 0, after which
bpf_refcount_acquireis basically performing a use-after-free (when fortunate, one will get aWARN_ON_ONCEsplat for 0 to 1, otherwise, a silent refcount raise for some different object).
As discussed earlier we'll be switching all bpf_obj_new to use BPF_MA_REUSE_AFTER_RCU_GP.
and to adress 0->1 transition.. it does look like we need to two flavors of bpf_refcount_acquire. One of owned refs and another for non-owned.
The owned bpf_refcount_acquire() can stay KF_ACQUIRE with refcount_inc,
while bpf_refcount_acquire() for non-own will use KF_ACQUIRE | KF_RET_NULL and refcount_inc_not_zero. The bpf prog can use bpf_refcount_acquire everywhere and the verifier will treat it on the spot differently depending on the argument.
So the code:
n = bpf_obj_new();
if (!n) ...;
m = bpf_refcount_acquire(n);
doesn't need to check if (!m).
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH v2 bpf-next 9/9] selftests/bpf: Add refcounted_kptr tests
Quoted 73 lines · Alexei Starovoitov
Quoted 55 lines · Kumar Kartikeya Dwivedi
Quoted 27 lines · Dave Marchevsky
Test refcounted local kptr functionality added in previous patches in the series.
Usecases which pass verification:
* Add refcounted local kptr to both tree and list. Then, read and - possibly, depending on test variant - delete from tree, then list.
* Also test doing read-and-maybe-delete in opposite order
* Stash a refcounted local kptr in amap_value, then add it to a rbtree. Read from both, possibly deleting after tree read.
* Add refcounted local kptr to both tree and list. Then, try reading and deleting twice from one of the collections.
*bpf_refcount_acquireof just-added non-owning ref should work, as shouldbpf_refcount_acquireof owning ref just out ofbpf_obj_newUsecases which fail verification:
* The simple successful
bpf_refcount_acquirecases from above should both fail to verify if the newly-acquired owning ref is not droppedSigned-off-by Dave Marchevsky <[email protected]>---
[...]tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +4
-0+SEC("?tc") +__failure __msg("Unreleased reference id=3 alloc_insn=21") +long rbtree_refcounted_node_ref_escapes (void *ctx) +{tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c line 44
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +10
-0+struct node_acquire *n, *m; + + n =bpf_obj_new (typeof (*n)); +if (!n) +return 1 ; + +bpf_spin_lock (&glock); +bpf_rbtree_add (&groot, &n->node, less); +/* m becomes an owning ref but is never drop'd or added to a tree */ + m =bpf_refcount_acquire (n);I am analyzing the set (and I'll reply in detail to the cover letter), but this stood out.
Isn't this going to be problematic if n has refcount == 1 and is dropped internally by
bpf_rbtree_add? Are we sure this can never occur? It took me some time, but the following schedule seems problematic.CPU 0 CPU 1
n =bpf_obj_new
lock(lock1)bpf_rbtree_add(rbtree1, n)
m =bpf_rbtree_acquire(n)
unlock(lock1)
kptr_xchg(map, m)// move to map
// at this point, refcount = 2Quoted 7 lines
m = kptr_xchg(map, NULL) lock(lock2)lock(lock1)
bpf_rbtree_add(rbtree2, m)
p =bpf_rbtree_first(rbtree1)if (!RB_EMPTY_NODE)bpf_obj_drop_impl(m)// Abpf_rbtree_remove(rbtree1, p)
unlock(lock1)bpf_obj_drop(p)// BYou probably meant:
p2 =bpf_rbtree_remove(rbtree1, p)
unlock(lock1)
if (p2)
bpf_obj_drop(p2)Quoted 3 lines
bpf_refcount_acquire(m) // use-after-free ...
Quoted 6 lines
Quoted 4 lines
B will decrement refcount from 1 to 0, after which
bpf_refcount_acquireis basically performing a use-after-free (when fortunate, one will get aWARN_ON_ONCEsplat for 0 to 1, otherwise, a silent refcount raise for some different object).As discussed earlier we'll be switching all
bpf_obj_newto useBPF_MA_REUSE_AFTER_RCU_GP
I probably missed that thread. In that case, is use of this stuff going to require bpf_rcu_read_lock in sleepable programs?
Quoted 12 lines
and to adress 0->1 transition.. it does look like we need to two flavors of
bpf_refcount_acquire. One of owned refs and another for non-owned.
The ownedbpf_refcount_acquire()can stayKF_ACQUIREwithrefcount_inc,
whilebpf_refcount_acquire()for non-own will useKF_ACQUIRE|KF_RET_NULLandrefcount_inc_not_zero. The bpf prog can usebpf_refcount_acquireeverywhere and the verifier will treat it on the spot differently depending on the argument.
So the code:
n =bpf_obj_new();
if (!n) ...;
m =bpf_refcount_acquire(n);
doesn't need to check if (!m).
If memory reuse is prevented, than indeed the above should fix the problem. Though it might be a bit surprising if a pointer from the same helper has to be null checked in one context, and not in another. Though that's just a minor point.
Re: [PATCH v2 bpf-next 9/9] selftests/bpf: Add refcounted_kptr tests
Quoted 80 lines · Kumar Kartikeya Dwivedi
Quoted 78 lines · Alexei Starovoitov
Quoted 53 lines · Kumar Kartikeya Dwivedi
Quoted 27 lines · Dave Marchevsky
Test refcounted local kptr functionality added in previous patches in the series.
Usecases which pass verification:
* Add refcounted local kptr to both tree and list. Then, read and - possibly, depending on test variant - delete from tree, then list.
* Also test doing read-and-maybe-delete in opposite order
* Stash a refcounted local kptr in amap_value, then add it to a rbtree. Read from both, possibly deleting after tree read.
* Add refcounted local kptr to both tree and list. Then, try reading and deleting twice from one of the collections.
*bpf_refcount_acquireof just-added non-owning ref should work, as shouldbpf_refcount_acquireof owning ref just out ofbpf_obj_newUsecases which fail verification:
* The simple successful
bpf_refcount_acquirecases from above should both fail to verify if the newly-acquired owning ref is not droppedSigned-off-by Dave Marchevsky <[email protected]>---
[...]tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +4
-0+SEC("?tc") +__failure __msg("Unreleased reference id=3 alloc_insn=21") +long rbtree_refcounted_node_ref_escapes (void *ctx) +{tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c line 44
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +10
-0+struct node_acquire *n, *m; + + n =bpf_obj_new (typeof (*n)); +if (!n) +return 1 ; + +bpf_spin_lock (&glock); +bpf_rbtree_add (&groot, &n->node, less); +/* m becomes an owning ref but is never drop'd or added to a tree */ + m =bpf_refcount_acquire (n);I am analyzing the set (and I'll reply in detail to the cover letter), but this stood out.
Isn't this going to be problematic if n has refcount == 1 and is dropped internally by
bpf_rbtree_add? Are we sure this can never occur? It took me some time, but the following schedule seems problematic.CPU 0 CPU 1
n =bpf_obj_new
lock(lock1)bpf_rbtree_add(rbtree1, n)
m =bpf_rbtree_acquire(n)
unlock(lock1)Quoted 9 lines
kptr_xchg(map, m)// move to map
// at this point, refcount = 2
m =kptr_xchg(map, NULL)lock(lock2)
lock(lock1)bpf_rbtree_add(rbtree2, m)
p =bpf_rbtree_first(rbtree1)if (!RB_EMPTY_NODE)bpf_obj_drop_impl(m)// Abpf_rbtree_remove(rbtree1, p)
unlock(lock1)bpf_obj_drop(p)// BYou probably meant:
p2 =bpf_rbtree_remove(rbtree1, p)
unlock(lock1)
if (p2)
bpf_obj_drop(p2)Quoted 7 lines
bpf_refcount_acquire(m)// use-after-free
...B will decrement refcount from 1 to 0, after which
bpf_refcount_acquireis basically performing a use-after-free (when fortunate, one will get aWARN_ON_ONCEsplat for 0 to 1, otherwise, a silent refcount raise for some different object).
Quoted 4 lines
Quoted 1 line
As discussed earlier we'll be switching all
bpf_obj_newto useBPF_MA_REUSE_AFTER_RCU_GPI probably missed that thread. In that case, is use of this stuff going to require
bpf_rcu_read_lockin sleepable programs?
Correct.
We've refactored rcu enforcement.
We also decided to stop waiting for gcc btf_tag support to land and went with allowlisting BTF_TYPE_SAFE_RCU[_OR_NULL] for fields that we need to use now.
Overall it allowed us to get rid of kptr_get.
Re: [PATCH v2 bpf-next 9/9] selftests/bpf: Add refcounted_kptr tests
In reply to Kumar Kartikeya DwivediQuoted 62 lines · Kumar Kartikeya Dwivedi
Quoted 27 lines · Dave Marchevsky
Test refcounted local kptr functionality added in previous patches in the series.
Usecases which pass verification:
* Add refcounted local kptr to both tree and list. Then, read and - possibly, depending on test variant - delete from tree, then list.
* Also test doing read-and-maybe-delete in opposite order
* Stash a refcounted local kptr in amap_value, then add it to a rbtree. Read from both, possibly deleting after tree read.
* Add refcounted local kptr to both tree and list. Then, try reading and deleting twice from one of the collections.
*bpf_refcount_acquireof just-added non-owning ref should work, as shouldbpf_refcount_acquireof owning ref just out ofbpf_obj_newUsecases which fail verification:
* The simple successful
bpf_refcount_acquirecases from above should both fail to verify if the newly-acquired owning ref is not droppedSigned-off-by Dave Marchevsky <[email protected]>---
[...]tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +4
-0+SEC("?tc") +__failure __msg("Unreleased reference id=3 alloc_insn=21") +long rbtree_refcounted_node_ref_escapes (void *ctx) +{tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c line 44
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c new file +10
-0+struct node_acquire *n, *m; + + n =bpf_obj_new (typeof (*n)); +if (!n) +return 1 ; + +bpf_spin_lock (&glock); +bpf_rbtree_add (&groot, &n->node, less); +/* m becomes an owning ref but is never drop'd or added to a tree */ + m =bpf_refcount_acquire (n);I am analyzing the set (and I'll reply in detail to the cover letter), but this stood out.
Isn't this going to be problematic if n has refcount == 1 and is dropped internally by
bpf_rbtree_add? Are we sure this can never occur? It took me some time, but the following schedule seems problematic.CPU 0 CPU 1
n =bpf_obj_new
lock(lock1)bpf_rbtree_add(rbtree1, n)
m =bpf_rbtree_acquire(n)
unlock(lock1)
kptr_xchg(map, m)// move to map
// at this point, refcount = 2m = kptr_xchg(map, NULL) lock(lock2)lock(lock1)
bpf_rbtree_add(rbtree2, m)
p =bpf_rbtree_first(rbtree1)if (!RB_EMPTY_NODE)bpf_obj_drop_impl(m)// Abpf_rbtree_remove(rbtree1, p)
unlock(lock1)bpf_obj_drop(p)// B
Quoted 7 lines
bpf_refcount_acquire(m) // use-after-free ...B will decrement refcount from 1 to 0, after which
bpf_refcount_acquireis basically performing a use-after-free (when fortunate, one will get aWARN_ON_ONCEsplat for 0 to 1, otherwise, a silent refcount raise for some different object).
Thanks for the detailed feedback here and in the other thread in the series. I will address the issues you raised ASAP, starting with this one, which I've confirmed via a repro selftest. Will be sending fixes soon.
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 10 lines · On Sat, 15 Apr 2023 13:18:02 -0700 you wrote:
This series adds support for refcounted local kptrs to the verifier. A local kptr is 'refcounted' if its type contains a struct
bpf_refcountfield:struct refcounted_node { long data; struct bpf_list_node ll; struct bpf_refcount ref; };[...]
Here is the summary with links:
- [v2,bpf-next,1/9] bpf: Remove btf_field_offs, use btf_record's fields instead
https://git.kernel.org/bpf/bpf-next/c/cd2a8079014a - [v2,bpf-next,2/9] bpf: Introduce opaque bpf_refcount struct and add btf_record plumbing https://git.kernel.org/bpf/bpf-next/c/d54730b50bae - [v2,bpf-next,3/9] bpf: Support refcounted local kptrs in existing semantics https://git.kernel.org/bpf/bpf-next/c/1512217c47f0 - [v2,bpf-next,4/9] bpf: Add bpf_refcount_acquire kfunc https://git.kernel.org/bpf/bpf-next/c/7c50b1cb76ac - [v2,bpf-next,5/9] bpf: Migrate bpf_rbtree_add and bpf_list_push_{front,back} to possibly fail https://git.kernel.org/bpf/bpf-next/c/d2dcc67df910 - [v2,bpf-next,6/9] selftests/bpf: Modify linked_list tests to work with macro-ified inserts https://git.kernel.org/bpf/bpf-next/c/de67ba3968fa - [v2,bpf-next,7/9] bpf: Migrate bpf_rbtree_remove to possibly fail https://git.kernel.org/bpf/bpf-next/c/404ad75a36fb - [v2,bpf-next,8/9] bpf: Centralize btf_field-specific initialization logic https://git.kernel.org/bpf/bpf-next/c/3e81740a9062 - [v2,bpf-next,9/9] selftests/bpf: Add refcounted_kptr tests https://git.kernel.org/bpf/bpf-next/c/6147f15131e2
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html
Kumar Kartikeya Dwivedi
maintainerQuoted 68 lines · Dave Marchevsky
This series adds support for refcounted local kptrs to the verifier. A local kptr is 'refcounted' if its type contains a struct
bpf_refcountfield:struct refcounted_node { long data; struct bpf_list_node ll; struct bpf_refcount ref; };
bpf_refcountis used to implement shared ownership for local kptrs.Motivating usecase
==================If a struct has two collection node fields, e.g.:
struct node { long key; long val; struct bpf_rb_node rb; struct bpf_list_node ll; };It's not currently possible to add a node to both the list and rbtree:
long bpf_prog(void *ctx) { struct node *n = bpf_obj_new(typeof(*n)); if (!n) { /* ... */ }bpf_spin_lock(&lock); bpf_list_push_back(&head, &n->ll); bpf_rbtree_add(&root, &n->rb, less); /* Assume a resonable less() */ bpf_spin_unlock(&lock);}
The above program will fail verification due to current owning / non-owning ref
logic: afterbpf_list_push_back, n is a non-owning reference and thus cannot be passed tobpf_rbtree_add. The only way to get an owning reference for the node that was added is to bpf_list_pop_{front,back} it.More generally, verifier ownership semantics expect that a node has one owner (program, collection, or stashed in map) with exclusive ownership of the node's lifetime. The owner free's the node's underlying memory when it itself goes away.
Without a shared ownership concept it's impossible to express many real-world usecases such that they pass verification.
Semantic Changes
================Before this series, the verifier could make this statement: "whoever has the owning reference has exclusive ownership of the referent's lifetime". As demonstrated in the previous section, this implies that a BPF program can't have an owning reference to some node if that node is in a collection. If such a state were possible, the node would have multiple owners, each thinking they have exclusive ownership. In order to support shared ownership it's necessary to modify the exclusive ownership semantic.
After this series' changes, an owning reference has ownership of the referent's lifetime, but it's not necessarily exclusive. The referent's underlying memory is guaranteed to be valid (i.e. not free'd) until the reference is dropped or used for collection insert.
This change doesn't affect UX of owning or non-owning references much:
Quoted 7 lines
* insert kfuncs (
bpf_rbtree_add, bpf_list_push_{front,back}) still require an owning reference arg, as ownership still must be passed to the collection in a shared-ownership world.* non-owning references still refer to valid memory without claiming any ownership.
[...]
I think there are a series of major issues right now. I am not sure everything can be addressed using bug fixes.
If I had to summarize the main problems in one liners:
The mutation of the node fields of an object can be racy. Lack of collection identity either at runtime or verification.
--
It is possible for multiple CPUs to get owned references to an object containing a rbtree or list node, and they can attempt to modify those fields in parallel without any synchronization.
CPU 0 CPU 1
n = bpf_obj_new(...)
m = bpf_refcount_acquire(n)kptr_xchg(map, m)
m = kptr_xchg(map, NULL)
// m == nbpf_spin_lock(lock1) bpf_spin_lock(lock2)bpf_rbtree_add(rbtree1, m) bpf_rbtree_add(rbtree2, n)
if (!RB_EMPTY_NODE) if (!RB_EMPTY_NODE) // RACE, both continue with 'else'bpf_spin_unlock(lock1) bpf_spin_unlock(lock2)
--
Blocking kptr_xchg for shared ownership nodes as a stopgap solution won't be sufficient. Consider this:
Two CPUs can do (consider rbtree1 having the only element we add from CPU 0):
CPU 0 CPU 1
n = bpf_obj_new(...)bpf_spin_lock(lock1)bpf_rbtree_add(rbtree1, n)
m = bpf_refcount_acquire(n)bpf_spin_unlock(lock1)
bpf_spin_lock(lock1)
n = bpf_rbtree_remove(bpf_rbtree_first(rbtree1)) bpf_spin_unlock(lock1)
// let m == nbpf_spin_lock(lock1) bpf_spin_lock(lock2)bpf_rbtree_add(rbtree1, m) bpf_rbtree_add(rbtree2, n)
if (!RB_EMPTY_NODE) if (!RB_EMPTY_NODE) // RACE, both continue with 'else'bpf_spin_unlock(lock1) bpf_spin_unlock(lock2)
--
There's also no discussion on the problem with collection identities we discussed before (maybe you plan to address it later):
https://lore.kernel.org/bpf/[email protected]
But static tracaking won't be sufficient any longer. Considering another case where the runtime will be confused about which rbtree a node belongs to.
CPU 0 CPU 1
n = bpf_obj_new(...)
m = bpf_refcount_acquire(n)kptr_xchg(map, m)
p = kptr_xchg(map, NULL) lock(lock2) bpf_rbtree_add(rbtree2, p->rnode) unlock(lock2)
lock(lock1)bpf_list_push_back(head1, n->lnode)
// make n non-owning refbpf_rbtree_remove(rbtree1, n->rnode); // OOPS, remove without lock2 unlock(lock1)
--
I can come up with multiple other examples. The point I'm trying to drive home is that it's a more fundamental issue in the way things are set up right now, not something that was overlooked during the implementation.
The root cause is that access to a node's fields is going to be racy once multiple CPUs have *mutable* references to it. The lack of ownership information mapped to the collection either at runtime or during verification is also a separate problem.
When we were discussing this a few months ago, we tried to form consensus on synchronizing updates over a node using an 'owner' pointer to eliminate similar races. Every node field has an associated owner field, which each updater modifying that node synchronizes over.
In short:
Node's owner describes its state at runtime.
node.owner == ptr_of_ds // part of DS
node.owner == NULL // not part of DS
node.owner == BPF_PTR_POISON // busy (about to go to NULL or ptr_of_ds before BPF_EXIT)
cmpxchg(node.owner, NULL, BPF_PTR_POISON) to make a free node busy. bpf_rbtree_add and such will do this to claim node ownership before trying to link it in, and then store owner to ptr_of_ds. The _store_ will be the *linearization* point of bpf_rbtree_add, not cmpxchg.
READ_ONCE(node.owner) == ptr_of_ds to ensure node belongs to locked ds, and will remain in this state until the end of CS, since ptr_to_ds to NULL only happens in remove under a held lock for the ds. bpf_rbtree_remove will do this check before WRITE_ONCE of NULL to unlink a node.
Ofcourse, this is slower, and requires extra space in the object, but unless this or something else is used to eliminate races, there will be bugs.
Quoted 140 lines · Kumar Kartikeya Dwivedi
Quoted 68 lines · Dave Marchevsky
This series adds support for refcounted local kptrs to the verifier. A local kptr is 'refcounted' if its type contains a struct
bpf_refcountfield:struct refcounted_node { long data; struct bpf_list_node ll; struct bpf_refcount ref; };
bpf_refcountis used to implement shared ownership for local kptrs.Motivating usecase
==================If a struct has two collection node fields, e.g.:
struct node { long key; long val; struct bpf_rb_node rb; struct bpf_list_node ll; };It's not currently possible to add a node to both the list and rbtree:
long bpf_prog(void *ctx) { struct node *n = bpf_obj_new(typeof(*n)); if (!n) { /* ... */ }bpf_spin_lock(&lock); bpf_list_push_back(&head, &n->ll); bpf_rbtree_add(&root, &n->rb, less); /* Assume a resonable less() */ bpf_spin_unlock(&lock);}
The above program will fail verification due to current owning / non-owning ref
logic: afterbpf_list_push_back, n is a non-owning reference and thus cannot be passed tobpf_rbtree_add. The only way to get an owning reference for the node that was added is to bpf_list_pop_{front,back} it.More generally, verifier ownership semantics expect that a node has one owner (program, collection, or stashed in map) with exclusive ownership of the node's lifetime. The owner free's the node's underlying memory when it itself goes away.
Without a shared ownership concept it's impossible to express many real-world usecases such that they pass verification.
Semantic Changes
================Before this series, the verifier could make this statement: "whoever has the owning reference has exclusive ownership of the referent's lifetime". As demonstrated in the previous section, this implies that a BPF program can't have an owning reference to some node if that node is in a collection. If such a state were possible, the node would have multiple owners, each thinking they have exclusive ownership. In order to support shared ownership it's necessary to modify the exclusive ownership semantic.
After this series' changes, an owning reference has ownership of the referent's lifetime, but it's not necessarily exclusive. The referent's underlying memory is guaranteed to be valid (i.e. not free'd) until the reference is dropped or used for collection insert.
This change doesn't affect UX of owning or non-owning references much:
Quoted 7 lines
* insert kfuncs (
bpf_rbtree_add, bpf_list_push_{front,back}) still require an owning reference arg, as ownership still must be passed to the collection in a shared-ownership world.* non-owning references still refer to valid memory without claiming any ownership.
[...]I think there are a series of major issues right now. I am not sure everything can be addressed using bug fixes.
If I had to summarize the main problems in one liners:
The mutation of the node fields of an object can be racy. Lack of collection identity either at runtime or verification.--
It is possible for multiple CPUs to get owned references to an object containing a rbtree or list node, and they can attempt to modify those fields in parallel without any synchronization.
CPU 0 CPU 1
n =bpf_obj_new(...)
m =bpf_refcount_acquire(n)kptr_xchg(map, m)
m =kptr_xchg(map, NULL)
// m == nbpf_spin_lock(lock1)bpf_spin_lock(lock2)bpf_rbtree_add(rbtree1, m)bpf_rbtree_add(rbtree2, n)
if (!RB_EMPTY_NODE) if (!RB_EMPTY_NODE) // RACE, both continue with 'else'bpf_spin_unlock(lock1)bpf_spin_unlock(lock2)--
Blocking
kptr_xchgfor shared ownership nodes as a stopgap solution won't be sufficient. Consider this:Two CPUs can do (consider rbtree1 having the only element we add from CPU 0):
CPU 0 CPU 1
n =bpf_obj_new(...)bpf_spin_lock(lock1)bpf_rbtree_add(rbtree1, n)
m =bpf_refcount_acquire(n)bpf_spin_unlock(lock1)
bpf_spin_lock(lock1)
n = bpf_rbtree_remove(bpf_rbtree_first(rbtree1))bpf_spin_unlock(lock1)
// let m == nbpf_spin_lock(lock1)bpf_spin_lock(lock2)bpf_rbtree_add(rbtree1, m)bpf_rbtree_add(rbtree2, n)
if (!RB_EMPTY_NODE) if (!RB_EMPTY_NODE) // RACE, both continue with 'else'bpf_spin_unlock(lock1)bpf_spin_unlock(lock2)--
There's also no discussion on the problem with collection identities we discussed before (maybe you plan to address it later):
https://lore.kernel.org/bpf/[email protected]But static tracaking won't be sufficient any longer. Considering another case where the runtime will be confused about which rbtree a node belongs to.
CPU 0 CPU 1
n =bpf_obj_new(...)
m =bpf_refcount_acquire(n)kptr_xchg(map, m)p = kptr_xchg(map, NULL) lock(lock2) bpf_rbtree_add(rbtree2, p->rnode) unlock(lock2)
Quoted 5 lines
lock(lock1)
bpf_list_push_back(head1, n->lnode)
// make n non-owning refbpf_rbtree_remove(rbtree1, n->rnode); // OOPS, remove without lock2 unlock(lock1)
Thanks for describing the races.
Quoted 11 lines
--
I can come up with multiple other examples. The point I'm trying to drive home is that it's a more fundamental issue in the way things are set up right now, not something that was overlooked during the implementation.
The root cause is that access to a node's fields is going to be racy once multiple CPUs have *mutable* references to it. The lack of ownership information mapped to the collection either at runtime or during verification is also a separate problem.
Quoted 8 lines
When we were discussing this a few months ago, we tried to form consensus on synchronizing updates over a node using an 'owner' pointer to eliminate similar races. Every node field has an associated owner field, which each updater modifying that node synchronizes over.
In short:
Node's owner describes its state at runtime.
node.owner ==ptr_of_ds// part of DS
what is DS ?
Quoted 8 lines
node.owner == NULL // not part of DS
node.owner ==BPF_PTR_POISON// busy (about to go to NULL orptr_of_dsbeforeBPF_EXIT)
cmpxchg(node.owner, NULL, BPF_PTR_POISON)to make a free node busy.bpf_rbtree_addand such will do this to claim node ownership before trying to link it in, and then store owner toptr_of_ds. The _store_ will be the *linearization* point ofbpf_rbtree_add, not cmpxchg.
Quoted 7 lines
READ_ONCE(node.owner)==ptr_of_dsto ensure node belongs to locked ds, and will remain in this state until the end of CS, sinceptr_to_dsto NULL only happens in remove under a held lock for the ds.bpf_rbtree_removewill do this check beforeWRITE_ONCEof NULL to unlink a node.Ofcourse, this is slower, and requires extra space in the object, but unless this or something else is used to eliminate races, there will be bugs.
Makes sense to me. Where do you propose to store the owner? Another explicit field that bpf prog has to provide inside a node?
A hidden field in bpf_refcount ?
A hidden field in bpf_list_node / bpf_rb_node ?
Kumar Kartikeya Dwivedi
maintainerQuoted 165 lines · Alexei Starovoitov
Quoted 140 lines · Kumar Kartikeya Dwivedi
Quoted 68 lines · Dave Marchevsky
This series adds support for refcounted local kptrs to the verifier. A local kptr is 'refcounted' if its type contains a struct
bpf_refcountfield:struct refcounted_node { long data; struct bpf_list_node ll; struct bpf_refcount ref; };
bpf_refcountis used to implement shared ownership for local kptrs.Motivating usecase
==================If a struct has two collection node fields, e.g.:
struct node { long key; long val; struct bpf_rb_node rb; struct bpf_list_node ll; };It's not currently possible to add a node to both the list and rbtree:
long bpf_prog(void *ctx) { struct node *n = bpf_obj_new(typeof(*n)); if (!n) { /* ... */ }bpf_spin_lock(&lock); bpf_list_push_back(&head, &n->ll); bpf_rbtree_add(&root, &n->rb, less); /* Assume a resonable less() */ bpf_spin_unlock(&lock);}
The above program will fail verification due to current owning / non-owning ref
logic: afterbpf_list_push_back, n is a non-owning reference and thus cannot be passed tobpf_rbtree_add. The only way to get an owning reference for the node that was added is to bpf_list_pop_{front,back} it.More generally, verifier ownership semantics expect that a node has one owner (program, collection, or stashed in map) with exclusive ownership of the node's lifetime. The owner free's the node's underlying memory when it itself goes away.
Without a shared ownership concept it's impossible to express many real-world usecases such that they pass verification.
Semantic Changes
================Before this series, the verifier could make this statement: "whoever has the owning reference has exclusive ownership of the referent's lifetime". As demonstrated in the previous section, this implies that a BPF program can't have an owning reference to some node if that node is in a collection. If such a state were possible, the node would have multiple owners, each thinking they have exclusive ownership. In order to support shared ownership it's necessary to modify the exclusive ownership semantic.
After this series' changes, an owning reference has ownership of the referent's lifetime, but it's not necessarily exclusive. The referent's underlying memory is guaranteed to be valid (i.e. not free'd) until the reference is dropped or used for collection insert.
This change doesn't affect UX of owning or non-owning references much:
Quoted 7 lines
* insert kfuncs (
bpf_rbtree_add, bpf_list_push_{front,back}) still require an owning reference arg, as ownership still must be passed to the collection in a shared-ownership world.* non-owning references still refer to valid memory without claiming any ownership.
[...]I think there are a series of major issues right now. I am not sure everything can be addressed using bug fixes.
If I had to summarize the main problems in one liners:
The mutation of the node fields of an object can be racy. Lack of collection identity either at runtime or verification.--
It is possible for multiple CPUs to get owned references to an object containing a rbtree or list node, and they can attempt to modify those fields in parallel without any synchronization.
CPU 0 CPU 1
n =bpf_obj_new(...)
m =bpf_refcount_acquire(n)kptr_xchg(map, m)
m =kptr_xchg(map, NULL)
// m == nbpf_spin_lock(lock1)bpf_spin_lock(lock2)bpf_rbtree_add(rbtree1, m)bpf_rbtree_add(rbtree2, n)
if (!RB_EMPTY_NODE) if (!RB_EMPTY_NODE) // RACE, both continue with 'else'bpf_spin_unlock(lock1)bpf_spin_unlock(lock2)--
Blocking
kptr_xchgfor shared ownership nodes as a stopgap solution won't be sufficient. Consider this:Two CPUs can do (consider rbtree1 having the only element we add from CPU 0):
CPU 0 CPU 1
n =bpf_obj_new(...)bpf_spin_lock(lock1)bpf_rbtree_add(rbtree1, n)
m =bpf_refcount_acquire(n)bpf_spin_unlock(lock1)
bpf_spin_lock(lock1)
n = bpf_rbtree_remove(bpf_rbtree_first(rbtree1))bpf_spin_unlock(lock1)
// let m == nbpf_spin_lock(lock1)bpf_spin_lock(lock2)bpf_rbtree_add(rbtree1, m)bpf_rbtree_add(rbtree2, n)
if (!RB_EMPTY_NODE) if (!RB_EMPTY_NODE) // RACE, both continue with 'else'bpf_spin_unlock(lock1)bpf_spin_unlock(lock2)--
There's also no discussion on the problem with collection identities we discussed before (maybe you plan to address it later):
https://lore.kernel.org/bpf/[email protected]But static tracaking won't be sufficient any longer. Considering another case where the runtime will be confused about which rbtree a node belongs to.
CPU 0 CPU 1
n =bpf_obj_new(...)
m =bpf_refcount_acquire(n)kptr_xchg(map, m)p = kptr_xchg(map, NULL) lock(lock2) bpf_rbtree_add(rbtree2, p->rnode) unlock(lock2)Quoted 5 lines
lock(lock1)
bpf_list_push_back(head1, n->lnode)
// make n non-owning refbpf_rbtree_remove(rbtree1, n->rnode); // OOPS, remove without lock2 unlock(lock1)Thanks for describing the races.
Quoted 16 lines
--
I can come up with multiple other examples. The point I'm trying to drive home is that it's a more fundamental issue in the way things are set up right now, not something that was overlooked during the implementation.
The root cause is that access to a node's fields is going to be racy once multiple CPUs have *mutable* references to it. The lack of ownership information mapped to the collection either at runtime or during verification is also a separate problem.
When we were discussing this a few months ago, we tried to form consensus on synchronizing updates over a node using an 'owner' pointer to eliminate similar races. Every node field has an associated owner field, which each updater modifying that node synchronizes over.
Quoted 6 lines
Quoted 3 lines
In short:
Node's owner describes its state at runtime.
node.owner ==ptr_of_ds// part of DSwhat is DS ?
The graph data structure.
Quoted 13 lines
Quoted 13 lines
node.owner == NULL // not part of DS
node.owner ==BPF_PTR_POISON// busy (about to go to NULL orptr_of_dsbeforeBPF_EXIT)
cmpxchg(node.owner, NULL, BPF_PTR_POISON)to make a free node busy.bpf_rbtree_addand such will do this to claim node ownership before trying to link it in, and then store owner toptr_of_ds. The _store_ will be the *linearization* point ofbpf_rbtree_add, not cmpxchg.
READ_ONCE(node.owner)==ptr_of_dsto ensure node belongs to locked ds, and will remain in this state until the end of CS, sinceptr_to_dsto NULL only happens in remove under a held lock for the ds.bpf_rbtree_removewill do this check beforeWRITE_ONCEof NULL to unlink a node.
Quoted 7 lines
Quoted 2 lines
Ofcourse, this is slower, and requires extra space in the object, but unless this or something else is used to eliminate races, there will be bugs.
Makes sense to me. Where do you propose to store the owner? Another explicit field that bpf prog has to provide inside a node?
A hidden field inbpf_refcount?
A hidden field inbpf_list_node/bpf_rb_node?
It will have to be with each bpf_list_node / bpf_rb_node.
Pseudocode wise, this is how things will work:
bpf_rbtree_add(rbtree, node):
// Move a node from free to busy state if (!cmpxchg(node.owner, NULL, BPF_PTR_POISON)) return -EINVAL __rb_add(...) WRITE_ONCE(node.owner, rbtree)
bpf_rbtree_remove(rbtree, node):
// Check if node is part of rbtree: // If != rbtree, it could be changing concurrently // If == rbtree, changing it requires the lock we are holding if (READ_ONCE(node.owner) != rbtree) return -EINVAL __rb_remove(...) WRITE_ONCE(node.owner, NULL)
Likewise for the linked list helpers.
My opinion would be to have a different bpf_list_node_shared and bpf_rb_node_shared for refcount_off >= 0 case, which encode both bpf_list_node and bpf_rb_node and their owner together, since the space and runtime check tradeoff is not required if you're using exclusive ownership.
One more point is that you can minimize cost of cmpxchg by adding compound operation helpers.
For instance (under appropriate locking):
bpf_rbtree_move(rbtree1, rbtree2, node):
if (READ_ONCE(node.owner) != rbtree1) return -EINVAL __rb_remove(rbtree1, node) __rb_add(rbtree2, node) WRITE_ONCE(node.owner, rbtree2)
Instead of:
bpf_rbtree_remove(rbtree1, node)
bpf_rbtree_add(rbtree2, node)
Quoted 191 lines · Kumar Kartikeya Dwivedi
Quoted 165 lines · Alexei Starovoitov
Quoted 140 lines · Kumar Kartikeya Dwivedi
Quoted 68 lines · Dave Marchevsky
This series adds support for refcounted local kptrs to the verifier. A local kptr is 'refcounted' if its type contains a struct
bpf_refcountfield:struct refcounted_node { long data; struct bpf_list_node ll; struct bpf_refcount ref; };
bpf_refcountis used to implement shared ownership for local kptrs.Motivating usecase
==================If a struct has two collection node fields, e.g.:
struct node { long key; long val; struct bpf_rb_node rb; struct bpf_list_node ll; };It's not currently possible to add a node to both the list and rbtree:
long bpf_prog(void *ctx) { struct node *n = bpf_obj_new(typeof(*n)); if (!n) { /* ... */ }bpf_spin_lock(&lock); bpf_list_push_back(&head, &n->ll); bpf_rbtree_add(&root, &n->rb, less); /* Assume a resonable less() */ bpf_spin_unlock(&lock);}
The above program will fail verification due to current owning / non-owning ref
logic: afterbpf_list_push_back, n is a non-owning reference and thus cannot be passed tobpf_rbtree_add. The only way to get an owning reference for the node that was added is to bpf_list_pop_{front,back} it.More generally, verifier ownership semantics expect that a node has one owner (program, collection, or stashed in map) with exclusive ownership of the node's lifetime. The owner free's the node's underlying memory when it itself goes away.
Without a shared ownership concept it's impossible to express many real-world usecases such that they pass verification.
Semantic Changes
================Before this series, the verifier could make this statement: "whoever has the owning reference has exclusive ownership of the referent's lifetime". As demonstrated in the previous section, this implies that a BPF program can't have an owning reference to some node if that node is in a collection. If such a state were possible, the node would have multiple owners, each thinking they have exclusive ownership. In order to support shared ownership it's necessary to modify the exclusive ownership semantic.
After this series' changes, an owning reference has ownership of the referent's lifetime, but it's not necessarily exclusive. The referent's underlying memory is guaranteed to be valid (i.e. not free'd) until the reference is dropped or used for collection insert.
This change doesn't affect UX of owning or non-owning references much:
Quoted 7 lines
* insert kfuncs (
bpf_rbtree_add, bpf_list_push_{front,back}) still require an owning reference arg, as ownership still must be passed to the collection in a shared-ownership world.* non-owning references still refer to valid memory without claiming any ownership.
[...]I think there are a series of major issues right now. I am not sure everything can be addressed using bug fixes.
If I had to summarize the main problems in one liners:
The mutation of the node fields of an object can be racy. Lack of collection identity either at runtime or verification.--
It is possible for multiple CPUs to get owned references to an object containing a rbtree or list node, and they can attempt to modify those fields in parallel without any synchronization.
CPU 0 CPU 1
n =bpf_obj_new(...)
m =bpf_refcount_acquire(n)kptr_xchg(map, m)
m =kptr_xchg(map, NULL)
// m == nbpf_spin_lock(lock1)bpf_spin_lock(lock2)bpf_rbtree_add(rbtree1, m)bpf_rbtree_add(rbtree2, n)
if (!RB_EMPTY_NODE) if (!RB_EMPTY_NODE) // RACE, both continue with 'else'bpf_spin_unlock(lock1)bpf_spin_unlock(lock2)--
Blocking
kptr_xchgfor shared ownership nodes as a stopgap solution won't be sufficient. Consider this:Two CPUs can do (consider rbtree1 having the only element we add from CPU 0):
CPU 0 CPU 1
n =bpf_obj_new(...)bpf_spin_lock(lock1)bpf_rbtree_add(rbtree1, n)
m =bpf_refcount_acquire(n)bpf_spin_unlock(lock1)
bpf_spin_lock(lock1)
n = bpf_rbtree_remove(bpf_rbtree_first(rbtree1))bpf_spin_unlock(lock1)
// let m == nbpf_spin_lock(lock1)bpf_spin_lock(lock2)bpf_rbtree_add(rbtree1, m)bpf_rbtree_add(rbtree2, n)
if (!RB_EMPTY_NODE) if (!RB_EMPTY_NODE) // RACE, both continue with 'else'bpf_spin_unlock(lock1)bpf_spin_unlock(lock2)--
There's also no discussion on the problem with collection identities we discussed before (maybe you plan to address it later):
https://lore.kernel.org/bpf/[email protected]But static tracaking won't be sufficient any longer. Considering another case where the runtime will be confused about which rbtree a node belongs to.
CPU 0 CPU 1
n =bpf_obj_new(...)
m =bpf_refcount_acquire(n)kptr_xchg(map, m)p = kptr_xchg(map, NULL) lock(lock2) bpf_rbtree_add(rbtree2, p->rnode) unlock(lock2)Quoted 5 lines
lock(lock1)
bpf_list_push_back(head1, n->lnode)
// make n non-owning refbpf_rbtree_remove(rbtree1, n->rnode); // OOPS, remove without lock2 unlock(lock1)Thanks for describing the races.
Quoted 16 lines
--
I can come up with multiple other examples. The point I'm trying to drive home is that it's a more fundamental issue in the way things are set up right now, not something that was overlooked during the implementation.
The root cause is that access to a node's fields is going to be racy once multiple CPUs have *mutable* references to it. The lack of ownership information mapped to the collection either at runtime or during verification is also a separate problem.
When we were discussing this a few months ago, we tried to form consensus on synchronizing updates over a node using an 'owner' pointer to eliminate similar races. Every node field has an associated owner field, which each updater modifying that node synchronizes over.
Quoted 6 lines
Quoted 3 lines
In short:
Node's owner describes its state at runtime.
node.owner ==ptr_of_ds// part of DSwhat is DS ?
The graph data structure.
Quoted 16 lines
Quoted 15 lines
node.owner == NULL // not part of DS
node.owner ==BPF_PTR_POISON// busy (about to go to NULL orptr_of_dsbeforeBPF_EXIT)
cmpxchg(node.owner, NULL, BPF_PTR_POISON)to make a free node busy.bpf_rbtree_addand such will do this to claim node ownership before trying to link it in, and then store owner toptr_of_ds. The _store_ will be the *linearization* point ofbpf_rbtree_add, not cmpxchg.
READ_ONCE(node.owner)==ptr_of_dsto ensure node belongs to locked ds, and will remain in this state until the end of CS, sinceptr_to_dsto NULL only happens in remove under a held lock for the ds.bpf_rbtree_removewill do this check beforeWRITE_ONCEof NULL to unlink a node.Ofcourse, this is slower, and requires extra space in the object, but unless this or something else is used to eliminate races, there will be bugs.
Quoted 6 lines
Quoted 4 lines
Makes sense to me. Where do you propose to store the owner? Another explicit field that bpf prog has to provide inside a node?
A hidden field inbpf_refcount?
A hidden field inbpf_list_node/bpf_rb_node?It will have to be with each
bpf_list_node/bpf_rb_node.
yeah. realized after pressed 'send'.
Quoted 6 lines
Pseudocode wise, this is how things will work:
bpf_rbtree_add(rbtree, node):// Move a node from free to busy state if (!cmpxchg(node.owner, NULL, BPF_PTR_POISON)) return -EINVAL
should be bpf_obj_drop here instead of plain return. In other words the current
if (!RB_EMPTY_NODE()) bpf_obj_drop
will be replaced by the above cmpxchg
Quoted 9 lines
__rb_add(...) WRITE_ONCE(node.owner, rbtree)
bpf_rbtree_remove(rbtree, node):// Check if node is part of rbtree: // If != rbtree, it could be changing concurrently // If == rbtree, changing it requires the lock we are holding if (READ_ONCE(node.owner) != rbtree) return -EINVAL
should be 'return NULL'.
The above check will replace current RB_EMPTY_NODE check.
Quoted 2 lines
__rb_remove(...) WRITE_ONCE(node.owner, NULL)
comparing to existing code it's only extra WRITE_ONCE and cmpxchg instead of load+cmp.
imo the perf cost is roughly the same. Because of that there is no need to have
two bpf_rbtree_add/remove for shared/exclusive nodes.
Quoted 6 lines
Likewise for the linked list helpers.
My opinion would be to have a different
bpf_list_node_sharedandbpf_rb_node_sharedforrefcount_off>= 0 case, which encode bothbpf_list_nodeandbpf_rb_nodeand their owner together, since the space and runtime check tradeoff is not required if you're using exclusive ownership.
true, but runtime performance of bpf_rbtree_add/remove is the same for both cases. With bpf_rb_node_shared the bpf prog will save 8 bytes of memory at the expense of plenty verifier complexity that would need to have two checks
if (btf_id == bpf_rb_node_shared || btf_id == bpf_rb_node) in a bunch of places and one of the two in another set of places.
I'd rather waste 8 bytes than complicate the verifier.
Having valid node->owner for exclusive rb-tree and link list is a nice debug feature too. Not saying we screwed up non-shared rb-tree, but I won't be surprised if somebody will figure out how to construct similar race there in the future.
Quoted 12 lines
One more point is that you can minimize cost of cmpxchg by adding compound operation helpers.
For instance (under appropriate locking):
bpf_rbtree_move(rbtree1, rbtree2, node):if (READ_ONCE(node.owner) != rbtree1) return -EINVAL __rb_remove(rbtree1, node) __rb_add(rbtree2, node) WRITE_ONCE(node.owner, rbtree2)
Quoted 3 lines
Instead of:
bpf_rbtree_remove(rbtree1, node)
bpf_rbtree_add(rbtree2, node)
That makes sense. Not urgent. Distant follow up.