Shared ownership for local kptrs
Subsystems (4)
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: c4d3b488a90be95f4f9413dc7eae5fc113d15fe9
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 | 85 ++-- 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 | 116 +++-- kernel/bpf/map_in_map.c | 15 - kernel/bpf/syscall.c | 23 +- kernel/bpf/verifier.c | 153 +++++-- tools/include/uapi/linux/bpf.h | 4 + .../testing/selftests/bpf/bpf_experimental.h | 60 ++- .../selftests/bpf/prog_tests/linked_list.c | 8 +- .../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 | 410 ++++++++++++++++++ .../bpf/progs/refcounted_kptr_fail.c | 72 +++ 21 files changed, 1066 insertions(+), 347 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 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 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
@@ -6975,6 +6975,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]);
@@ -5307,6 +5316,7 @@ static const char *alloc_obj_fields[] = {"bpf_list_node" ,"bpf_rb_root" ,"bpf_rb_node" , + "bpf_refcount", }; static struct btf_struct_metas *
@@ -5380,7 +5390,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
@@ -6975,6 +6975,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 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 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(m); // 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;
@@ -2308,6 +2322,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
Re: [PATCH v1 bpf-next 4/9] bpf: Add bpf_refcount_acquire kfunc
Quoted 14 lines · Dave Marchevsky
Currently, 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 creationbpf_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 forbpf_obj_droppingitIn 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.
Quoted 7 lines
bpf_refcount_acquiretakes 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(m); // B
typo. should probably be bpf_refcount_acquire(n) ?
PATCH 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 | 76 +++++++++++++------ .../testing/selftests/bpf/bpf_experimental.h | 49 +++++++++--- 4 files changed, 147 insertions(+), 50 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 +54 -22
171 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
PATCH 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 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.
The issues prevented by clobbering non-owning refs on rbtree_remove are no longer issues, so it's safe to remove the invalidate_non_owning_refs call.
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 | 2 +- .../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, 134 insertions(+), 76 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 ==-1 && +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;
@@ -2360,7 +2366,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
@@ -10963,9 +10963,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 +1 -1
@@ -748,7 +748,7 @@ static void test_btf(void)break ; err =btf__load_into_kernel (btf); -ASSERT_EQ (err, -EINVAL ,"check btf" ); +ASSERT_EQ (err,0 ,"check btf" );btf__free (btf);break ; }
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
Re: [PATCH v1 bpf-next 7/9] bpf: Migrate bpf_rbtree_remove to possibly fail
Quoted 96 lines · Dave Marchevsky
This patch modifies
bpf_rbtree_removeto account for possible failure due to the inputrb_nodealready 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_NULLto bpf_rbtree_remove's kfunc flags - nowKF_RET_NULL|KF_ACQUIRE- provides the desired verifier semantics:* retval must be checked for NULL before use
* if NULL, retval'sref_obj_idis 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 CSBPF 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_removeno longer clobbers non-owning refs
====================================================An issue arises when
bpf_rbtree_removefails, 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_removein this example will always fail. Similarly tobpf_spin_unlock,bpf_rbtree_removeis a non-owning reference invalidation point. The verifier clobbers all non-owning refs after abpf_rbtree_removecall, 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 frombpf_rbtree_removeto allow the above usecase to pass verification. The logic for why this is now possible is as follows:Before this series,
bpf_rbtree_addcouldn'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 torbtree_removeone after another (seerbtree_api_release_aliasinginselftests/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.
Quoted 3 lines
The issues prevented by clobbering non-owning refs on
rbtree_removeare no longer issues, so it's safe to remove theinvalidate_non_owning_refscall.
I've read the above sentence as
"it's safe to remove invalidate_non_owning_refs() function"
and went ahead to read the patch to find out that it's invocation is removed for rbtree_remove case.
Which I expected to see after reading the previous paragraphs. If you can think of a way to rephrase the above paragraph it would be nice, but not a big deal.
Quoted 39 lines
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_removeretval for NULL where necessary, and moverbtree_api_release_aliasingfromprogs/rbtree_fail.ctoprogs/rbtree.csince it's now expected to pass verification.Signed-off-by Dave Marchevsky <[email protected]>--- kernel/bpf/btf.c | 21 +---- kernel/bpf/helpers.c | 8 +- kernel/bpf/verifier.c | 3 - .../selftests/bpf/prog_tests/linked_list.c | 2 +- .../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, 134 insertions(+), 76 deletions(-)kernel/bpf/btf.c +0
-10@@ -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(....);
kernel/bpf/btf.c struct btf_record *btf_parse_fields(const struct btf *btf, const struct btf_type · line 3808
Quoted 10 lines
kernel/bpf/btf.c +1
-9-* 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 == -1 &&
That will never trigger, since it was inited to -EINVAL. It should be refcount_off < 0.
Quoted 4 lines
kernel/bpf/btf.c +1
-0+ btf_record_has_field(rec, BPF_LIST_NODE) && btf_record_has_field(rec, BPF_RB_NODE)) { ret = -EINVAL ; goto end;
PATCH 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 | 38 ++++++++++++++++++++++++++++++++++---- kernel/bpf/helpers.c | 17 +++++++---------- 2 files changed, 41 insertions(+), 14 deletions(-)
include/linux/bpf.h +34 -4
@@ -355,6 +355,39 @@ static inline u32 btf_field_type_align(enum btf_field_type type) } } +static inline void __bpf_obj_init_field (enum btf_field_type type,u32 size,void *addr) +{ +memset (addr,0 , size); + +switch (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 void bpf_obj_init_field (const struct btf_field *field,void *addr) +{ +__bpf_obj_init_field (field->type, field->size, addr); +} +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 +402,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 +7 -10
@@ -1931,15 +1931,16 @@ __bpf_kfunc void *bpf_refcount_acquire_impl(void *p__refcounted_kptr, void *metareturn (void *)p__refcounted_kptr; } +#define __init_field_infer_size (field_type, addr)\ + __bpf_obj_init_field(field_type, btf_field_type_size(field_type), addr) +static int __bpf_list_add (struct bpf_list_node *node,struct bpf_list_head *head,bool tail,struct btf_record *rec,u64 off) {struct list_head *n = (void *)node, *h = (void *)head;if (unlikely (!h->next)) -INIT_LIST_HEAD (h); -if (unlikely (!n->next)) -INIT_LIST_HEAD (n); +__init_field_infer_size (BPF_LIST_HEAD , h);if (!list_empty (n)) {/* Only called from BPF prog, no need to migrate_disable */ __bpf_obj_drop_impl (n - off, rec);
@@ -1976,7 +1977,7 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool taistruct list_head *n, *h = (void *)head;if (unlikely (!h->next)) -INIT_LIST_HEAD (h); +__init_field_infer_size (BPF_LIST_HEAD , h);if (list_empty (h))return NULL ; n = tail ? h->prev : h->next;
@@ -1984,6 +1985,8 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool taireturn (struct bpf_list_node *)n; } +#undef __init_field_infer_size + __bpf_kfunc struct bpf_list_node *bpf_list_pop_front(struct bpf_list_head *head) {return __bpf_list_del (head, false);
@@ -2000,9 +2003,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 +2022,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
Re: [PATCH v1 bpf-next 8/9] bpf: Centralize btf_field-specific initialization logic
Quoted 71 lines · Dave Marchevsky
All
btf_fieldsin an object are 0-initialized by memset inbpf_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} andbpf_rb_node.An earlier patch in this series added the
bpf_refcountfield, for which the 0 state indicates that the refcounted object should be free'd.bpf_obj_inittreats 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.
Signed-off-by Dave Marchevsky <[email protected]>--- include/linux/bpf.h | 38 ++++++++++++++++++++++++++++++++++---- kernel/bpf/helpers.c | 17 +++++++---------- 2 files changed, 41 insertions(+), 14 deletions(-)include/linux/bpf.h +33
-0@@ -355,6 +355,39 @@ static inline u32 btf_field_type_align(enum btf_field_type type) } } +static inline void __bpf_obj_init_field (enum btf_field_type type,u32 size,void *addr) +{ +memset (addr,0 , size); + +switch (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 void bpf_obj_init_field (const struct btf_field *field,void *addr) +{ +__bpf_obj_init_field (field->type, field->size, addr); +} +static inline bool btf_record_has_field (const struct btf_record *rec,enum btf_field_type type) {if (IS_ERR_OR_NULL (rec))
include/linux/bpf.h static inline void bpf_obj_init(const struct btf_record *rec, void *obj) · line 405
Quoted 8 lines
include/linux/bpf.h +1
-4@@ -369,10 +402,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);
this part make sense.
Quoted 14 lines
include/linux/bpf.h +0
-0}/* 'dst' must be a temporary buffer and should not point to memory that is being kernel/bpf/helpers.c +3
-0@@ -1931,15 +1931,16 @@ __bpf_kfunc void *bpf_refcount_acquire_impl(void *p__refcounted_kptr, void *metareturn (void *)p__refcounted_kptr; } +#define __init_field_infer_size (field_type, addr)\ + __bpf_obj_init_field(field_type, btf_field_type_size(field_type), addr) +
kernel/bpf/helpers.c __bpf_kfunc void *bpf_refcount_acquire_impl(void *p__refcounted_kptr, void *meta · line 1943
Quoted 10 lines
kernel/bpf/helpers.c +1
-3static int __bpf_list_add (struct bpf_list_node *node,struct bpf_list_head *head,bool tail,struct btf_record *rec,u64 off) {struct list_head *n = (void *)node, *h = (void *)head;if (unlikely (!h->next)) -INIT_LIST_HEAD (h); -if (unlikely (!n->next)) -INIT_LIST_HEAD (n); +__init_field_infer_size (BPF_LIST_HEAD , h);
but this part is dubious.
What's the value? I think it's cleaner to keep it open coded with INIT_LIST_HEAD() instead of hiding it through the helper.
kernel/bpf/helpers.c static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool tai · line 1980
Quoted 9 lines
kernel/bpf/helpers.c +1
-1if (!list_empty (n)) {/* Only called from BPF prog, no need to migrate_disable */ __bpf_obj_drop_impl (n - off, rec);@@ -1976,7 +1977,7 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool taistruct list_head *n, *h = (void *)head;if (unlikely (!h->next)) -INIT_LIST_HEAD (h); +__init_field_infer_size (BPF_LIST_HEAD , h);
same here.
Quoted 35 lines
kernel/bpf/helpers.c +2
-6if (list_empty (h))return NULL ; n = tail ? h->prev : h->next;@@ -1984,6 +1985,8 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool taireturn (struct bpf_list_node *)n; } +#undef __init_field_infer_size + __bpf_kfunc struct bpf_list_node *bpf_list_pop_front(struct bpf_list_head *head) {return __bpf_list_del (head, false);@@ -2000,9 +2003,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 +2022,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 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 | 410 ++++++++++++++++++ .../bpf/progs/refcounted_kptr_fail.c | 72 +++ 3 files changed, 500 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 +410 -0
410 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
Re: [PATCH v1 bpf-next 9/9] selftests/bpf: Add refcounted_kptr tests
Quoted 253 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]>--- .../bpf/prog_tests/refcounted_kptr.c | 18 + .../selftests/bpf/progs/refcounted_kptr.c | 410 ++++++++++++++++++ .../bpf/progs/refcounted_kptr_fail.c | 72 +++ 3 files changed, 500 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.ctools/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 +193
-0@@ -0,0 +1,410 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */ + +#include <vmlinux.h> +#include <bpf/bpf_tracing.h> +#include <bpf/bpf_helpers.h> +#include <bpf/bpf_core_read.h> +#include "bpf_misc.h" +#include "bpf_experimental.h" + +struct node_data { +long key; +long list_data; +struct bpf_rb_node r; +struct bpf_list_node l; +struct bpf_refcount ref; +}; + +struct map_value { + struct node_data __kptr *node; +}; + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __type(key, int); + __type(value, struct map_value); + __uint(max_entries, 1); +} stashed_nodes SEC(".maps"); + +struct node_acquire { +long key; +long data; +struct bpf_rb_node node; +struct bpf_refcount refcount; +}; + +#define private (name) SEC(".bss." #name) __hidden __attribute__((aligned(8))) +private(A) struct bpf_spin_lock lock; +private(A) struct bpf_rb_root root __contains(node_data, r); +private(A) struct bpf_list_head head __contains(node_data, l); + +private(B) struct bpf_spin_lock alock; +private(B) struct bpf_rb_root aroot __contains(node_acquire, node); + +static bool less (struct bpf_rb_node *node_a,const struct bpf_rb_node *node_b) +{ +struct node_data *a; +struct node_data *b; + + a = container_of(node_a, struct node_data, r); + b = container_of(node_b, struct node_data, r); + +return a->key < b->key; +} + +static bool less_a (struct bpf_rb_node *a,const struct bpf_rb_node *b) +{ +struct node_acquire *node_a; +struct node_acquire *node_b; + + node_a = container_of(a, struct node_acquire, node); + node_b = container_of(b, struct node_acquire, node); + +return node_a->key < node_b->key; +} + +static __always_inline +long __insert_in_tree_and_list (struct bpf_list_head *head, +struct bpf_rb_root *root, +struct bpf_spin_lock *lock) +{ +struct node_data *n, *m; + + n =bpf_obj_new (typeof (*n)); +if (!n) +return -1 ; + + m =bpf_refcount_acquire (n); + m->key =123 ; + m->list_data =456 ; + +bpf_spin_lock (lock); +if (bpf_rbtree_add (root, &n->r, less)) { +/* Failure to insert - unexpected */ +bpf_spin_unlock (lock); +bpf_obj_drop (m); +return -2 ; + } +bpf_spin_unlock (lock); + +bpf_spin_lock (lock); +if (bpf_list_push_front (head, &m->l)) { +/* Failure to insert - unexpected */ +bpf_spin_unlock (lock); +return -3 ; + } +bpf_spin_unlock (lock); +return 0 ; +} + +static __always_inline +long __stash_map_insert_tree (int idx,int val,struct bpf_rb_root *root, +struct bpf_spin_lock *lock) +{ +struct map_value *mapval; +struct node_data *n, *m; + + mapval =bpf_map_lookup_elem (&stashed_nodes, &idx); +if (!mapval) +return -1 ; + + n =bpf_obj_new (typeof (*n)); +if (!n) +return -2 ; + + n->key = val; + m =bpf_refcount_acquire (n); + + n =bpf_kptr_xchg (&mapval->node, n); +if (n) { +bpf_obj_drop (n); +bpf_obj_drop (m); +return -3 ; + } + +bpf_spin_lock (lock); +if (bpf_rbtree_add (root, &m->r, less)) { +/* Failure to insert - unexpected */ +bpf_spin_unlock (lock); +return -4 ; + } +bpf_spin_unlock (lock); +return 0 ; +} + +static __always_inline +long __read_from_tree (struct bpf_rb_root *root,struct bpf_spin_lock *lock, +bool remove_from_tree) +{ +struct bpf_rb_node *rb; +struct node_data *n; +long res =-99 ; + +bpf_spin_lock (lock); + + rb =bpf_rbtree_first (root); +if (!rb) { +bpf_spin_unlock (lock); +return -1 ; + } + + n = container_of(rb, struct node_data, r); + res = n->key; + +if (!remove_from_tree) { +bpf_spin_unlock (lock); +return res; + } + + rb =bpf_rbtree_remove (root, rb); +bpf_spin_unlock (lock); +if (!rb) { +return -2 ; + } + n = container_of(rb, struct node_data, r); +bpf_obj_drop (n); +return res; +} + +static __always_inline +long __read_from_list (struct bpf_list_head *head,struct bpf_spin_lock *lock, +bool remove_from_list) +{ +struct bpf_list_node *l; +struct node_data *n; +long res =-99 ; + +bpf_spin_lock (lock); + + l =bpf_list_pop_front (head); +if (!l) { +bpf_spin_unlock (lock); +return -1 ; + } + + n = container_of(l, struct node_data, l); + res = n->list_data; + +if (!remove_from_list) { +if (bpf_list_push_back (head, &n->l)) { +bpf_spin_unlock (lock); +return -2 ; + }
tools/testing/selftests/bpf/progs/refcounted_kptr.c line 203
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c new file +10
-0+ } + +bpf_spin_unlock (lock); + +if (remove_from_list) +bpf_obj_drop (n); +return res; +} + +static __always_inline
Why __always_inline in this 5 helpers?
Will it pass the verifier if __always_inline is replaced with noinline?
Quoted 1 line
tools/testing/selftests/bpf/progs/refcounted_kptr.c new file +1
-0+long __read_from_unstash (int idx)
Re: [PATCH v1 bpf-next 9/9] selftests/bpf: Add refcounted_kptr tests
Quoted 259 lines · Alexei Starovoitov
Quoted 258 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]>--- .../bpf/prog_tests/refcounted_kptr.c | 18 + .../selftests/bpf/progs/refcounted_kptr.c | 410 ++++++++++++++++++ .../bpf/progs/refcounted_kptr_fail.c | 72 +++ 3 files changed, 500 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.ctools/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 +198
-0@@ -0,0 +1,410 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */ + +#include <vmlinux.h> +#include <bpf/bpf_tracing.h> +#include <bpf/bpf_helpers.h> +#include <bpf/bpf_core_read.h> +#include "bpf_misc.h" +#include "bpf_experimental.h" + +struct node_data { +long key; +long list_data; +struct bpf_rb_node r; +struct bpf_list_node l; +struct bpf_refcount ref; +}; + +struct map_value { + struct node_data __kptr *node; +}; + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __type(key, int); + __type(value, struct map_value); + __uint(max_entries, 1); +} stashed_nodes SEC(".maps"); + +struct node_acquire { +long key; +long data; +struct bpf_rb_node node; +struct bpf_refcount refcount; +}; + +#define private (name) SEC(".bss." #name) __hidden __attribute__((aligned(8))) +private(A) struct bpf_spin_lock lock; +private(A) struct bpf_rb_root root __contains(node_data, r); +private(A) struct bpf_list_head head __contains(node_data, l); + +private(B) struct bpf_spin_lock alock; +private(B) struct bpf_rb_root aroot __contains(node_acquire, node); + +static bool less (struct bpf_rb_node *node_a,const struct bpf_rb_node *node_b) +{ +struct node_data *a; +struct node_data *b; + + a = container_of(node_a, struct node_data, r); + b = container_of(node_b, struct node_data, r); + +return a->key < b->key; +} + +static bool less_a (struct bpf_rb_node *a,const struct bpf_rb_node *b) +{ +struct node_acquire *node_a; +struct node_acquire *node_b; + + node_a = container_of(a, struct node_acquire, node); + node_b = container_of(b, struct node_acquire, node); + +return node_a->key < node_b->key; +} + +static __always_inline +long __insert_in_tree_and_list (struct bpf_list_head *head, +struct bpf_rb_root *root, +struct bpf_spin_lock *lock) +{ +struct node_data *n, *m; + + n =bpf_obj_new (typeof (*n)); +if (!n) +return -1 ; + + m =bpf_refcount_acquire (n); + m->key =123 ; + m->list_data =456 ; + +bpf_spin_lock (lock); +if (bpf_rbtree_add (root, &n->r, less)) { +/* Failure to insert - unexpected */ +bpf_spin_unlock (lock); +bpf_obj_drop (m); +return -2 ; + } +bpf_spin_unlock (lock); + +bpf_spin_lock (lock); +if (bpf_list_push_front (head, &m->l)) { +/* Failure to insert - unexpected */ +bpf_spin_unlock (lock); +return -3 ; + } +bpf_spin_unlock (lock); +return 0 ; +} + +static __always_inline +long __stash_map_insert_tree (int idx,int val,struct bpf_rb_root *root, +struct bpf_spin_lock *lock) +{ +struct map_value *mapval; +struct node_data *n, *m; + + mapval =bpf_map_lookup_elem (&stashed_nodes, &idx); +if (!mapval) +return -1 ; + + n =bpf_obj_new (typeof (*n)); +if (!n) +return -2 ; + + n->key = val; + m =bpf_refcount_acquire (n); + + n =bpf_kptr_xchg (&mapval->node, n); +if (n) { +bpf_obj_drop (n); +bpf_obj_drop (m); +return -3 ; + } + +bpf_spin_lock (lock); +if (bpf_rbtree_add (root, &m->r, less)) { +/* Failure to insert - unexpected */ +bpf_spin_unlock (lock); +return -4 ; + } +bpf_spin_unlock (lock); +return 0 ; +} + +static __always_inline +long __read_from_tree (struct bpf_rb_root *root,struct bpf_spin_lock *lock, +bool remove_from_tree) +{ +struct bpf_rb_node *rb; +struct node_data *n; +long res =-99 ; + +bpf_spin_lock (lock); + + rb =bpf_rbtree_first (root); +if (!rb) { +bpf_spin_unlock (lock); +return -1 ; + } + + n = container_of(rb, struct node_data, r); + res = n->key; + +if (!remove_from_tree) { +bpf_spin_unlock (lock); +return res; + } + + rb =bpf_rbtree_remove (root, rb); +bpf_spin_unlock (lock); +if (!rb) { +return -2 ; + } + n = container_of(rb, struct node_data, r); +bpf_obj_drop (n); +return res; +} + +static __always_inline +long __read_from_list (struct bpf_list_head *head,struct bpf_spin_lock *lock, +bool remove_from_list) +{ +struct bpf_list_node *l; +struct node_data *n; +long res =-99 ; + +bpf_spin_lock (lock); + + l =bpf_list_pop_front (head); +if (!l) { +bpf_spin_unlock (lock); +return -1 ; + } + + n = container_of(l, struct node_data, l); + res = n->list_data; + +if (!remove_from_list) { +if (bpf_list_push_back (head, &n->l)) { +bpf_spin_unlock (lock); +return -2 ; + } + } + +bpf_spin_unlock (lock); + +if (remove_from_list)
Quoted 9 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c line 170
Quoted 5 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c new file +5
-0+bpf_obj_drop (n); +return res; +} + +static __always_inlineWhy
__always_inlinein this 5 helpers?
Will it pass the verifier if__always_inlineis replaced with noinline?
There's no good reason for __always_inline, I cargo-culted it from linked_list test. Both replacing w/ __attribute__((noinline)) and having neither results in passing tests, so I sent v2 with the latter.
Quoted 1 line
Quoted 1 line
tools/testing/selftests/bpf/progs/refcounted_kptr.c new file +1
-0+long __read_from_unstash (int idx)