Skip to contentSkip to conversation

bpf: Introduce rbtree map

RFC PATCH In review Dave Marchevsky 4 participants 25 messages Aug 30, 2022 – Sep 8, 2022

Subsystems (5)
Kselftest BPF BPF selftests BPF core +1 more subsystems
lore
Share & tools
lore
#0 lore raw

v2 cover bpf: Introduce rbtree map

[ RFCv2: This RFC focuses on locking improvements. Some feedback from RFCv1 feedback and other discussions is not yet applied e.g. conversion to kfuncs, dropping open-coded iter. This isn't meant to imply that I disagree with this feedback, but rather want to make it easier to compare locking changes to RFCv1. Please see changelog at end of this cover letter for a list of newly-added patches and major changes worth looking at ]

Introduce a new map type, bpf_rbtree_map, allowing BPF programs to create and manipulate rbtree data structures. bpf_rbtree_map differs from 'classic' BPF map patterns in a few important ways:

* The map does not allocate its own elements. Instead,
BPF programs must call bpf_rbtree_alloc_node helper to allocate and bpf_rbtree_add to add map elem - referred to as 'node' from now on - to the rbtree. This means that rbtree maps can grow dynamically, do not preallocate, and that 'max_entries' has no meaning for rbtree maps.
* Separating allocation and insertion allows alloc_node call to occur in contexts where it's safe to allocate.

* It's possible to remove a node from a rbtree map with bpf_rbtree_remove helper.
* Goal here is to allow a node to be removed from one rbtree and added to another
[ NOTE: This functionality is still in progress ]

Helpers are added to manipulate nodes and trees:
* bpf_rbtree_{alloc,free}_node: Allocate / free node structs
* bpf_rbtree_{add,remove}: Add / remove nodes from rbtree maps
* A comparator function is passed to bpf_rbtree_add in order to find the correct place to add the node.
* bpf_rbtree_find: Find a node matching some condition in the rbtree
* A comparator function is passed in order to determine whether a node matches what's being searched for.

bpf_rbtree_add is very similar to the 'map_push_elem' builtin, but since verifier needs special logic to setup the comparator callback a new helper is added. Same for bpf_rbtree_find and 'map_lookup_elem' builtin.

In order to safely support separate allocation / insertion and passing nodes between rbtrees, some invariants must hold:

* A node that is not in a rbtree map must either be free'd or added to a rbtree map before the program terminates
* Nodes are in this state when returned from bpf_rbtree_alloc_node or bpf_rbtree_remove.

If a node is in a rbtree map it is 'owned' by the map, otherwise it is owned by the BPF program which holds a reference to it. Owner is responsible for the lifetime of the node.

This matches existing acquire / release semantics well. node_alloc and remove operations 'acquire' a node while add and node_free operations 'release' the node. The verifier enforces that acquired nodes are released before program terminates.

Some other implementation details:

* The value type of an rbtree map is expected to be a struct which contains 'struct rb_node' at offset 0.
* BPF programs may not modify the node struct's rb_node field.
* Otherwise the tree could be left in corrupted state
* Rbtree map is value-only. Keys have no meaning
* Since the value type is not known until the rbtree map is instantiated, helper protos have input and return type 'struct rb_node *' which verifier replaces with actual map value type.
* [ TODO: Existing logic prevents any writes to PTR_TO_BTF_ID. This broadly turned off in this patch and replaced with "no writes to struct rb_node is PTR_TO_BTF_ID struct has one". This is a hack and needs to be replaced. ]

Changelog:

RFCv1 -> RFCv2: lore.kernel.org/bpf/[email protected] Major changes:
* Add new patch ("bpf: Add verifier check for BPF_PTR_POISON retval and arg"), use BPF_PTR_POISON as placeholder btf_id for helpers which return or manipulate structs which contain rbtree node. (Alexei)
* Migrate all rbtree helpers to use BPF_PTR_POISON
* Testing this patch uncovered that rbtree_find was not in function_returns_rbtree_node check, add it. Rbtree_add was not setting a return btf_id type, fix that as well.

* Add new patch ("libbpf: Add support for private BSS map section") allowing struct bpf_spin_lock declaration in special internal map

* Add new patches improving ergonomics of associating lock with rbtree(1), teaching verifier to track rbtree locks(2), and teaching verifier to reject programs calling rbtree helpers without holding the necessary lock
* (1): "bpf: Support declarative association of lock with rbtree map" (3)
* (2): "bpf: Verifier tracking of rbtree_spin_lock held"
* (3): "bpf: Check rbtree lock held during verification"
* These are the changes most worth a look. Each commit has associated test change patch also added at the end of the series. Test patches are left unsquashed to ease RFC review.

Minor changes:
* patch "bpf: Add rbtree map"
* Alloc nodes w/ GFP_NOWAIT instead of GFP_KERNEL (Yonghong, Alexei)
* Rename access_may_touch_field -> access_can_write_field (Alexei)
* patch "bpf: Add CONDITIONAL_RELEASE type flag"
* No need to return int from mark_ptr_or_null_regs, go back to returning void (Alexei)

Dave Marchevsky (18):
bpf: Add verifier support for custom callback return range
bpf: Add verifier check for BPF_PTR_POISON retval and arg
bpf: Add rb_node_off to bpf_map
bpf: Add rbtree map
libbpf: Add support for private BSS map section
bpf: Add bpf_spin_lock member to rbtree
bpf: Add bpf_rbtree_{lock,unlock} helpers
bpf: Enforce spinlock hold for bpf_rbtree_{add,remove,find}
bpf: Support declarative association of lock with rbtree map
bpf: Verifier tracking of rbtree_spin_lock held
bpf: Check rbtree lock held during verification
bpf: Add OBJ_NON_OWNING_REF type flag
bpf: Add CONDITIONAL_RELEASE type flag
bpf: Introduce PTR_ITER and PTR_ITER_END type flags selftests/bpf: Add rbtree map tests
selftests/bpf: Declarative lock definition test changes selftests/bpf: Lock tracking test changes selftests/bpf: Rbtree static lock verification test changes

 include/linux/bpf.h                           |  17 +
 include/linux/bpf_types.h                     |   1 +
 include/linux/bpf_verifier.h                  |   3 +
 include/linux/btf.h                           |   1 +
 include/linux/poison.h                        |   3 +
 include/uapi/linux/bpf.h                      | 120 ++++
 kernel/bpf/Makefile                           |   2 +-
 kernel/bpf/btf.c                              |  21 +
 kernel/bpf/helpers.c                          |  48 +-
 kernel/bpf/rbtree.c                           | 442 ++++++++++++++
 kernel/bpf/syscall.c                          |  11 +-
 kernel/bpf/verifier.c                         | 546 ++++++++++++++++--
 tools/include/uapi/linux/bpf.h                | 120 ++++
 tools/lib/bpf/libbpf.c                        | 164 +++++-
 .../selftests/bpf/prog_tests/rbtree_map.c     | 134 +++++
 .../testing/selftests/bpf/progs/rbtree_map.c  | 119 ++++
 .../selftests/bpf/progs/rbtree_map_fail.c     | 243 ++++++++
 .../bpf/progs/rbtree_map_load_fail.c          |  31 +
 18 files changed, 1951 insertions(+), 75 deletions(-)
 create mode 100644 kernel/bpf/rbtree.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/rbtree_map.c
 create mode 100644 tools/testing/selftests/bpf/progs/rbtree_map.c
 create mode 100644 tools/testing/selftests/bpf/progs/rbtree_map_fail.c
 create mode 100644 tools/testing/selftests/bpf/progs/rbtree_map_load_fail.c
Signature · 1 line
2.30.2
#1 lore raw

RFC PATCH v2 1/18 bpf: Add verifier support for custom callback return range

Verifier logic to confirm that a callback function returns 0 or 1 was added in commit 69c087ba6225b ("bpf: Add bpf_for_each_map_elem() helper"). At the time, callback return value was only used to continue or stop iteration.

In order to support callbacks with a broader return value range, such as those added further in this series, add a callback_ret_range to bpf_func_state. Verifier's helpers which set in_callback_fn will also set the new field, which the verifier will later use to check return value bounds.

Default to tnum_range(0, 1) instead of using tnum_unknown as a sentinel value as the latter would prevent the valid range (0, U64_MAX) being used.

---
 include/linux/bpf_verifier.h | 1 +
 kernel/bpf/verifier.c        | 4 +++-
 2 files changed, 4 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +1 -0
index 2e3bad8640dc..9c017575c034 100644
@@ -237,6 +237,7 @@ struct bpf_func_state {
 	 */
 	u32 async_entry_cnt;
 	bool in_callback_fn;
+	struct tnum callback_ret_range;
 	bool in_async_callback_fn;
 
 	/* The following fields should be last. See copy_func_state() */
kernel/bpf/verifier.c +3 -1
index 9bef8b41e737..68bfa7c28048 100644
@@ -1745,6 +1745,7 @@ static void init_func_state(struct bpf_verifier_env *env,
 	state->callsite = callsite;
 	state->frameno = frameno;
 	state->subprogno = subprogno;
+	state->callback_ret_range = tnum_range(0, 1);
 	init_reg_state(env, state);
 	mark_verifier_state_scratched(env);
 }
@@ -6879,6 +6880,7 @@ static int set_find_vma_callback_state(struct bpf_verifier_env *env,
 	__mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
 	__mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
 	callee->in_callback_fn = true;
+	callee->callback_ret_range = tnum_range(0, 1);
 	return 0;
 }
 
@@ -6906,7 +6908,7 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 	caller = state->frame[state->curframe];
 	if (callee->in_callback_fn) {
 		/* enforce R0 return value range [0, 1]. */
-		struct tnum range = tnum_range(0, 1);
+		struct tnum range = callee->callback_ret_range;
 
 		if (r0->type != SCALAR_VALUE) {
 			verbose(env, "R0 not a scalar value\n");
Signature · 1 line
2.30.2
#2 lore raw

Re: [RFCv2 PATCH bpf-next 01/18] bpf: Add verifier support for custom callback return range

Quoted 47 lines · Dave Marchevsky

Verifier logic to confirm that a callback function returns 0 or 1 was added in commit 69c087ba6225b ("bpf: Add bpf_for_each_map_elem() helper"). At the time, callback return value was only used to continue or stop iteration.

In order to support callbacks with a broader return value range, such as those added further in this series, add a callback_ret_range to bpf_func_state. Verifier's helpers which set in_callback_fn will also set the new field, which the verifier will later use to check return value bounds.

Default to tnum_range(0, 1) instead of using tnum_unknown as a sentinel value as the latter would prevent the valid range (0, U64_MAX) being used.

---
 include/linux/bpf_verifier.h | 1 +
 kernel/bpf/verifier.c        | 4 +++-
 2 files changed, 4 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +1 -0
index 2e3bad8640dc..9c017575c034 100644
@@ -237,6 +237,7 @@ struct bpf_func_state {
         */
        u32 async_entry_cnt;
        bool in_callback_fn;
+       struct tnum callback_ret_range;
        bool in_async_callback_fn;
 
        /* The following fields should be last. See copy_func_state() */
kernel/bpf/verifier.c +1 -0
index 9bef8b41e737..68bfa7c28048 100644
@@ -1745,6 +1745,7 @@ static void init_func_state(struct bpf_verifier_env *env,
        state->callsite = callsite;
        state->frameno = frameno;
        state->subprogno = subprogno;
+       state->callback_ret_range = tnum_range(0, 1);
        init_reg_state(env, state);
        mark_verifier_state_scratched(env);
 }

kernel/bpf/verifier.c static int set_find_vma_callback_state(struct bpf_verifier_env *env, · line 6883

Quoted 4 lines
kernel/bpf/verifier.c +1 -0
@@ -6879,6 +6880,7 @@ static int set_find_vma_callback_state(struct bpf_verifier_env *env,
        __mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
        __mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
        callee->in_callback_fn = true;
+       callee->callback_ret_range = tnum_range(0, 1);

Thanks for removing this restriction for callback functions!

One quick question: is this line above needed? I think in __check_func_call, we always call init_func_state() first before calling set_find_vma_callback_state(), so after the init_func_state() call, the callee->callback_ret_range will already be set to tnum_range(0,1).

Quoted 15 lines
kernel/bpf/verifier.c +1 -2
        return 0;
 }
 
@@ -6906,7 +6908,7 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
        caller = state->frame[state->curframe];
        if (callee->in_callback_fn) {
                /* enforce R0 return value range [0, 1]. */
-               struct tnum range = tnum_range(0, 1);
+               struct tnum range = callee->callback_ret_range;
 
                if (r0->type != SCALAR_VALUE) {
                        verbose(env, "R0 not a scalar value\n");
--

2.30.2

#3 lore raw

Re: [RFCv2 PATCH bpf-next 01/18] bpf: Add verifier support for custom callback return range

Quoted 55 lines · Joanne Koong
Quoted 47 lines · Dave Marchevsky

Verifier logic to confirm that a callback function returns 0 or 1 was added in commit 69c087ba6225b ("bpf: Add bpf_for_each_map_elem() helper"). At the time, callback return value was only used to continue or stop iteration.

In order to support callbacks with a broader return value range, such as those added further in this series, add a callback_ret_range to bpf_func_state. Verifier's helpers which set in_callback_fn will also set the new field, which the verifier will later use to check return value bounds.

Default to tnum_range(0, 1) instead of using tnum_unknown as a sentinel value as the latter would prevent the valid range (0, U64_MAX) being used.

---
 include/linux/bpf_verifier.h | 1 +
 kernel/bpf/verifier.c        | 4 +++-
 2 files changed, 4 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +1 -0
index 2e3bad8640dc..9c017575c034 100644
@@ -237,6 +237,7 @@ struct bpf_func_state {
         */
        u32 async_entry_cnt;
        bool in_callback_fn;
+       struct tnum callback_ret_range;
        bool in_async_callback_fn;
 
        /* The following fields should be last. See copy_func_state() */
kernel/bpf/verifier.c +1 -0
index 9bef8b41e737..68bfa7c28048 100644
@@ -1745,6 +1745,7 @@ static void init_func_state(struct bpf_verifier_env *env,
        state->callsite = callsite;
        state->frameno = frameno;
        state->subprogno = subprogno;
+       state->callback_ret_range = tnum_range(0, 1);
        init_reg_state(env, state);
        mark_verifier_state_scratched(env);
 }

kernel/bpf/verifier.c static int set_find_vma_callback_state(struct bpf_verifier_env *env, · line 6883

Quoted 4 lines
kernel/bpf/verifier.c +1 -0
@@ -6879,6 +6880,7 @@ static int set_find_vma_callback_state(struct bpf_verifier_env *env,
        __mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
        __mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
        callee->in_callback_fn = true;
+       callee->callback_ret_range = tnum_range(0, 1);

Thanks for removing this restriction for callback functions!

Quoted 6 lines

One quick question: is this line above needed? I think in __check_func_call, we always call init_func_state() first before calling set_find_vma_callback_state(), so after the init_func_state() call, the callee->callback_ret_range will already be set to tnum_range(0,1).

You're right, it's not strictly necessary. I think that the default range being tnum_range(0, 1) - although necessary for backwards compat - is unintuitive. So decided to be explicit with existing callbacks so folks didn't have to go searching for the default to understand what the ret_range is, and it's more obvious that callback_ret_range should be changed if existing helper code is reused.

Quoted 15 lines
Quoted 15 lines
kernel/bpf/verifier.c +1 -2
        return 0;
 }
 
@@ -6906,7 +6908,7 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
        caller = state->frame[state->curframe];
        if (callee->in_callback_fn) {
                /* enforce R0 return value range [0, 1]. */
-               struct tnum range = tnum_range(0, 1);
+               struct tnum range = callee->callback_ret_range;
 
                if (r0->type != SCALAR_VALUE) {
                        verbose(env, "R0 not a scalar value\n");
--

2.30.2

#4 lore raw

Re: [RFCv2 PATCH bpf-next 01/18] bpf: Add verifier support for custom callback return range

Quoted 63 lines · Dave Marchevsky
Quoted 55 lines · Joanne Koong
Quoted 47 lines · Dave Marchevsky

Verifier logic to confirm that a callback function returns 0 or 1 was added in commit 69c087ba6225b ("bpf: Add bpf_for_each_map_elem() helper"). At the time, callback return value was only used to continue or stop iteration.

In order to support callbacks with a broader return value range, such as those added further in this series, add a callback_ret_range to bpf_func_state. Verifier's helpers which set in_callback_fn will also set the new field, which the verifier will later use to check return value bounds.

Default to tnum_range(0, 1) instead of using tnum_unknown as a sentinel value as the latter would prevent the valid range (0, U64_MAX) being used.

---
  include/linux/bpf_verifier.h | 1 +
  kernel/bpf/verifier.c        | 4 +++-
  2 files changed, 4 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +1 -0
index 2e3bad8640dc..9c017575c034 100644
@@ -237,6 +237,7 @@ struct bpf_func_state {
          */
         u32 async_entry_cnt;
         bool in_callback_fn;
+       struct tnum callback_ret_range;
         bool in_async_callback_fn;
 
         /* The following fields should be last. See copy_func_state() */
kernel/bpf/verifier.c +1 -0
index 9bef8b41e737..68bfa7c28048 100644
@@ -1745,6 +1745,7 @@ static void init_func_state(struct bpf_verifier_env *env,
         state->callsite = callsite;
         state->frameno = frameno;
         state->subprogno = subprogno;
+       state->callback_ret_range = tnum_range(0, 1);
         init_reg_state(env, state);
         mark_verifier_state_scratched(env);
  }

kernel/bpf/verifier.c static int set_find_vma_callback_state(struct bpf_verifier_env *env, · line 6883

Quoted 4 lines
kernel/bpf/verifier.c +1 -0
@@ -6879,6 +6880,7 @@ static int set_find_vma_callback_state(struct bpf_verifier_env *env,
         __mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
         __mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
         callee->in_callback_fn = true;
+       callee->callback_ret_range = tnum_range(0, 1);

Thanks for removing this restriction for callback functions!

Quoted 6 lines

One quick question: is this line above needed? I think in __check_func_call, we always call init_func_state() first before calling set_find_vma_callback_state(), so after the init_func_state() call, the callee->callback_ret_range will already be set to tnum_range(0,1).

Quoted 6 lines

You're right, it's not strictly necessary. I think that the default range being tnum_range(0, 1) - although necessary for backwards compat - is unintuitive. So decided to be explicit with existing callbacks so folks didn't have to go searching for the default to understand what the ret_range is, and it's more obvious that callback_ret_range should be changed if existing helper code is reused.

Maybe then it's better to keep callback_ret_range as range(0,0) in init_func_state() to nudge/force other places to set it explicitly ?

#5 lore raw

Re: [RFCv2 PATCH bpf-next 01/18] bpf: Add verifier support for custom callback return range

Quoted 71 lines · Alexei Starovoitov
Quoted 63 lines · Dave Marchevsky
Quoted 55 lines · Joanne Koong
Quoted 47 lines · Dave Marchevsky

Verifier logic to confirm that a callback function returns 0 or 1 was added in commit 69c087ba6225b ("bpf: Add bpf_for_each_map_elem() helper"). At the time, callback return value was only used to continue or stop iteration.

In order to support callbacks with a broader return value range, such as those added further in this series, add a callback_ret_range to bpf_func_state. Verifier's helpers which set in_callback_fn will also set the new field, which the verifier will later use to check return value bounds.

Default to tnum_range(0, 1) instead of using tnum_unknown as a sentinel value as the latter would prevent the valid range (0, U64_MAX) being used.

---
  include/linux/bpf_verifier.h | 1 +
  kernel/bpf/verifier.c        | 4 +++-

  2 files changed, 4 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +1 -0
index 2e3bad8640dc..9c017575c034 100644
@@ -237,6 +237,7 @@ struct bpf_func_state {
           */
          u32 async_entry_cnt;
          bool in_callback_fn;
+       struct tnum callback_ret_range;
          bool in_async_callback_fn;
 
          /* The following fields should be last. See copy_func_state() */
kernel/bpf/verifier.c +1 -0
index 9bef8b41e737..68bfa7c28048 100644
@@ -1745,6 +1745,7 @@ static void init_func_state(struct bpf_verifier_env *env,
          state->callsite = callsite;
          state->frameno = frameno;
          state->subprogno = subprogno;
+       state->callback_ret_range = tnum_range(0, 1);
          init_reg_state(env, state);
          mark_verifier_state_scratched(env);
   }

kernel/bpf/verifier.c static int set_find_vma_callback_state(struct bpf_verifier_env *env, · line 6883

Quoted 4 lines
kernel/bpf/verifier.c +1 -0
@@ -6879,6 +6880,7 @@ static int set_find_vma_callback_state(struct bpf_verifier_env *env,
          __mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
          __mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
          callee->in_callback_fn = true;
+       callee->callback_ret_range = tnum_range(0, 1);

Thanks for removing this restriction for callback functions!

Quoted 6 lines

One quick question: is this line above needed? I think in __check_func_call, we always call init_func_state() first before calling set_find_vma_callback_state(), so after the init_func_state() call, the callee->callback_ret_range will already be set to tnum_range(0,1).

Quoted 6 lines

You're right, it's not strictly necessary. I think that the default range being tnum_range(0, 1) - although necessary for backwards compat - is unintuitive. So decided to be explicit with existing callbacks so folks didn't have to go searching for the default to understand what the ret_range is, and it's more obvious that callback_ret_range should be changed if existing helper code is reused.

Quoted 2 lines

Maybe then it's better to keep callback_ret_range as range(0,0) in init_func_state() to nudge/force other places to set it explicitly ?

tnum_range(0, 0) sounds good to me.

Would you like me to send this separately with that change, so it can be applied independently of rest of these changes?

#6 lore raw

Re: [RFCv2 PATCH bpf-next 01/18] bpf: Add verifier support for custom callback return range

Quoted 73 lines · Dave Marchevsky
Quoted 71 lines · Alexei Starovoitov
Quoted 69 lines · Dave Marchevsky
Quoted 55 lines · Joanne Koong
Quoted 47 lines · Dave Marchevsky

Verifier logic to confirm that a callback function returns 0 or 1 was added in commit 69c087ba6225b ("bpf: Add bpf_for_each_map_elem() helper"). At the time, callback return value was only used to continue or stop iteration.

In order to support callbacks with a broader return value range, such as those added further in this series, add a callback_ret_range to bpf_func_state. Verifier's helpers which set in_callback_fn will also set the new field, which the verifier will later use to check return value bounds.

Default to tnum_range(0, 1) instead of using tnum_unknown as a sentinel value as the latter would prevent the valid range (0, U64_MAX) being used.

---
  include/linux/bpf_verifier.h | 1 +
  kernel/bpf/verifier.c        | 4 +++-
  2 files changed, 4 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +1 -0
index 2e3bad8640dc..9c017575c034 100644
@@ -237,6 +237,7 @@ struct bpf_func_state {
          */
         u32 async_entry_cnt;
         bool in_callback_fn;
+       struct tnum callback_ret_range;
         bool in_async_callback_fn;
 
         /* The following fields should be last. See copy_func_state() */
kernel/bpf/verifier.c +1 -0
index 9bef8b41e737..68bfa7c28048 100644
@@ -1745,6 +1745,7 @@ static void init_func_state(struct bpf_verifier_env *env,
         state->callsite = callsite;
         state->frameno = frameno;
         state->subprogno = subprogno;
+       state->callback_ret_range = tnum_range(0, 1);
         init_reg_state(env, state);
         mark_verifier_state_scratched(env);
  }

kernel/bpf/verifier.c static int set_find_vma_callback_state(struct bpf_verifier_env *env, · line 6883

Quoted 4 lines
kernel/bpf/verifier.c +1 -0
@@ -6879,6 +6880,7 @@ static int set_find_vma_callback_state(struct bpf_verifier_env *env,
         __mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
         __mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
         callee->in_callback_fn = true;
+       callee->callback_ret_range = tnum_range(0, 1);

Thanks for removing this restriction for callback functions!

Quoted 6 lines

One quick question: is this line above needed? I think in __check_func_call, we always call init_func_state() first before calling set_find_vma_callback_state(), so after the init_func_state() call, the callee->callback_ret_range will already be set to tnum_range(0,1).

You're right, it's not strictly necessary. I think that the default range being tnum_range(0, 1) - although necessary for backwards compat - is unintuitive. So decided to be explicit with existing callbacks so folks didn't have to go searching for the default to understand what the ret_range is, and it's more obvious that callback_ret_range should be changed if existing helper code is reused.

Quoted 7 lines
Quoted 2 lines

Maybe then it's better to keep callback_ret_range as range(0,0) in init_func_state() to nudge/force other places to set it explicitly ?

tnum_range(0, 0) sounds good to me.

Would you like me to send this separately with that change, so it can be applied independently of rest of these changes?

Whichever way is faster.
We can always apply a patch or a few patches out of a bigger set.

#7 lore raw

Re: [RFCv2 PATCH bpf-next 01/18] bpf: Add verifier support for custom callback return range

Quoted 77 lines · Alexei Starovoitov
Quoted 76 lines · Dave Marchevsky
Quoted 73 lines · Alexei Starovoitov
Quoted 63 lines · Dave Marchevsky
Quoted 55 lines · Joanne Koong
Quoted 47 lines · Dave Marchevsky

Verifier logic to confirm that a callback function returns 0 or 1 was added in commit 69c087ba6225b ("bpf: Add bpf_for_each_map_elem() helper"). At the time, callback return value was only used to continue or stop iteration.

In order to support callbacks with a broader return value range, such as those added further in this series, add a callback_ret_range to bpf_func_state. Verifier's helpers which set in_callback_fn will also set the new field, which the verifier will later use to check return value bounds.

Default to tnum_range(0, 1) instead of using tnum_unknown as a sentinel value as the latter would prevent the valid range (0, U64_MAX) being used.

---
  include/linux/bpf_verifier.h | 1 +
  kernel/bpf/verifier.c        | 4 +++-
  2 files changed, 4 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +1 -0
index 2e3bad8640dc..9c017575c034 100644
@@ -237,6 +237,7 @@ struct bpf_func_state {
          */
         u32 async_entry_cnt;
         bool in_callback_fn;
+       struct tnum callback_ret_range;
         bool in_async_callback_fn;
 
         /* The following fields should be last. See copy_func_state() */
kernel/bpf/verifier.c +1 -0
index 9bef8b41e737..68bfa7c28048 100644
@@ -1745,6 +1745,7 @@ static void init_func_state(struct bpf_verifier_env *env,
         state->callsite = callsite;
         state->frameno = frameno;
         state->subprogno = subprogno;
+       state->callback_ret_range = tnum_range(0, 1);
         init_reg_state(env, state);
         mark_verifier_state_scratched(env);
  }

kernel/bpf/verifier.c static int set_find_vma_callback_state(struct bpf_verifier_env *env, · line 6883

Quoted 4 lines
kernel/bpf/verifier.c +1 -0
@@ -6879,6 +6880,7 @@ static int set_find_vma_callback_state(struct bpf_verifier_env *env,
         __mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
         __mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
         callee->in_callback_fn = true;
+       callee->callback_ret_range = tnum_range(0, 1);

Thanks for removing this restriction for callback functions!

Quoted 6 lines

One quick question: is this line above needed? I think in __check_func_call, we always call init_func_state() first before calling set_find_vma_callback_state(), so after the init_func_state() call, the callee->callback_ret_range will already be set to tnum_range(0,1).

Quoted 6 lines

You're right, it's not strictly necessary. I think that the default range being tnum_range(0, 1) - although necessary for backwards compat - is unintuitive. So decided to be explicit with existing callbacks so folks didn't have to go searching for the default to understand what the ret_range is, and it's more obvious that callback_ret_range should be changed if existing helper code is reused.

Maybe then it's better to keep callback_ret_range as range(0,0) in init_func_state() to nudge/force other places to set it explicitly ?

Quoted 7 lines
Quoted 4 lines

tnum_range(0, 0) sounds good to me.

Would you like me to send this separately with that change, so it can be applied independently of rest of these changes?

Whichever way is faster.
We can always apply a patch or a few patches out of a bigger set.

Updated + rebased and sent as https://lore.kernel.org/bpf/[email protected]/

#8 lore raw

RFC PATCH v2 2/18 bpf: Add verifier check for BPF_PTR_POISON retval and arg

In reply to Dave Marchevsky

BPF_PTR_POISON was added in commit c0a5a21c25f37 ("bpf: Allow storing referenced kptr in map") to denote a bpf_func_proto btf_id which the verifier will replace with a dynamically-determined one at verification time.

This patch adds 'poison' functionality to BPF_PTR_POISON in order to prepare for expanded use of the value to poison ret- and arg-btf_id in further patches of this series. Specifically, when the verifier checks helper calls, it assumes that BPF_PTR_POISON'ed ret type will be replaced with a valid type before - or in lieu of - the default ret_btf_id logic. Similarly for argument btf_id.

If poisoned btf_id reaches default handling block for either, consider this a verifier internal error and fail verification. Otherwise a helper w/ poisoned btf_id but no verifier logic replacing the type will cause a crash as the invalid pointer is dereferenced.

Also move BPF_PTR_POISON to existing <linux/posion.h> header and replace the hardcoded value with something that looks slightly like BPF (0xB4F).

---
 include/linux/poison.h |  3 +++
 kernel/bpf/helpers.c   |  6 +++---
 kernel/bpf/verifier.c  | 28 ++++++++++++++++++++++------
 3 files changed, 28 insertions(+), 9 deletions(-)
include/linux/poison.h +3 -0
index d62ef5a6b4e9..599995d29fe4 100644
@@ -81,4 +81,7 @@
 /********** net/core/page_pool.c **********/
 #define PP_SIGNATURE		(0x40 + POISON_POINTER_DELTA)
 
+/********** kernel/bpf/ **********/
+#define BPF_PTR_POISON ((void *)(0xB4FUL + POISON_POINTER_DELTA))
+
 #endif
kernel/bpf/helpers.c +3 -3
index 3c1b9bbcf971..6de4dedf45c0 100644
@@ -15,6 +15,7 @@
 #include <linux/ctype.h>
 #include <linux/jiffies.h>
 #include <linux/pid_namespace.h>
+#include <linux/poison.h>
 #include <linux/proc_ns.h>
 #include <linux/security.h>
 #include <linux/btf_ids.h>
@@ -1410,10 +1411,9 @@ BPF_CALL_2(bpf_kptr_xchg, void *, map_value, void *, ptr)
 }
 
 /* Unlike other PTR_TO_BTF_ID helpers the btf_id in bpf_kptr_xchg()
- * helper is determined dynamically by the verifier.
+ * helper is determined dynamically by the verifier. Use BPF_PTR_POISON to
+ * denote type that verifier will determine.
  */
-#define BPF_PTR_POISON ((void *)((0xeB9FUL << 2) + POISON_POINTER_DELTA))
-
 static const struct bpf_func_proto bpf_kptr_xchg_proto = {
 	.func         = bpf_kptr_xchg,
 	.gpl_only     = false,
kernel/bpf/verifier.c +22 -6
index 68bfa7c28048..ee5b57140c73 100644
@@ -23,6 +23,7 @@
 #include <linux/error-injection.h>
 #include <linux/bpf_lsm.h>
 #include <linux/btf_ids.h>
+#include <linux/poison.h>
 
 #include "disasm.h"
 
@@ -5764,13 +5765,21 @@ static int check_reg_type(struct bpf_verifier_env *env, u32 regno,
 		if (meta->func_id == BPF_FUNC_kptr_xchg) {
 			if (map_kptr_match_type(env, meta->kptr_off_desc, reg, regno))
 				return -EACCES;
-		} else if (!btf_struct_ids_match(&env->log, reg->btf, reg->btf_id, reg->off,
+		} else {
+			if (arg_btf_id == BPF_PTR_POISON) {
+				verbose(env, "verifier internal error: R%d has "
+					"non-overwritten BPF_PTR_POISON type\n", regno);
+				return -EACCES;
+			}
+
+			if (!btf_struct_ids_match(&env->log, reg->btf, reg->btf_id, reg->off,
 						 btf_vmlinux, *arg_btf_id,
 						 strict_type_match)) {
-			verbose(env, "R%d is of type %s but %s is expected\n",
-				regno, kernel_type_name(reg->btf, reg->btf_id),
-				kernel_type_name(btf_vmlinux, *arg_btf_id));
-			return -EACCES;
+				verbose(env, "R%d is of type %s but %s is expected\n",
+					regno, kernel_type_name(reg->btf, reg->btf_id),
+					kernel_type_name(btf_vmlinux, *arg_btf_id));
+				return -EACCES;
+			}
 		}
 	}
 
@@ -7454,7 +7463,14 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 			ret_btf = meta.kptr_off_desc->kptr.btf;
 			ret_btf_id = meta.kptr_off_desc->kptr.btf_id;
 		} else {
-			ret_btf = btf_vmlinux;
+			if (fn->ret_btf_id == BPF_PTR_POISON) {
+				verbose(env, "verifier internal error: func %s "
+					"has non-overwritten "
+					"BPF_PTR_POISON return type\n",
+					func_id_name(func_id));
+				return -EINVAL;
+			}
+		        ret_btf = btf_vmlinux;
 			ret_btf_id = *fn->ret_btf_id;
 		}
 		if (ret_btf_id == 0) {
Signature · 1 line
2.30.2
#9 lore raw

RFC PATCH v2 3/18 bpf: Add rb_node_off to bpf_map

In reply to Dave Marchevsky

Similarly to other protected fields which might be in a map value - bpf_spin_lock and bpf_timer - keep track of existence and offset of struct rb_node within map value struct. This will allow later patches in this series to prevent writes to rb_node field.

Allowing bpf programs to modify the rbtree node struct's rb_node field would allow parent and children node pointers to be changed, which could corrupt an otherwise-valid rbtree.

---
 include/linux/bpf.h  |  6 ++++++
 include/linux/btf.h  |  1 +
 kernel/bpf/btf.c     | 21 +++++++++++++++++++++
 kernel/bpf/syscall.c |  3 +++
 4 files changed, 31 insertions(+)
include/linux/bpf.h +6 -0
index a627a02cf8ab..b4a44ffb0d6c 100644
@@ -215,6 +215,7 @@ struct bpf_map {
 	int spin_lock_off; /* >=0 valid offset, <0 error */
 	struct bpf_map_value_off *kptr_off_tab;
 	int timer_off; /* >=0 valid offset, <0 error */
+	int rb_node_off; /* >=0 valid offset, <0 error */
 	u32 id;
 	int numa_node;
 	u32 btf_key_type_id;
@@ -264,6 +265,11 @@ static inline bool map_value_has_kptrs(const struct bpf_map *map)
 	return !IS_ERR_OR_NULL(map->kptr_off_tab);
 }
 
+static inline bool map_value_has_rb_node(const struct bpf_map *map)
+{
+	return map->rb_node_off >= 0;
+}
+
 static inline void check_and_init_map_value(struct bpf_map *map, void *dst)
 {
 	if (unlikely(map_value_has_spin_lock(map)))
include/linux/btf.h +1 -0
index ad93c2d9cc1c..cbf10b6b4ada 100644
@@ -154,6 +154,7 @@ bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s,
 			   u32 expected_offset, u32 expected_size);
 int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t);
 int btf_find_timer(const struct btf *btf, const struct btf_type *t);
+int btf_find_rb_node(const struct btf *btf, const struct btf_type *t);
 struct bpf_map_value_off *btf_parse_kptrs(const struct btf *btf,
 					  const struct btf_type *t);
 bool btf_type_is_void(const struct btf_type *t);
kernel/bpf/btf.c +21 -0
index 903719b89238..f020efad8d9b 100644
@@ -3195,6 +3195,7 @@ enum btf_field_type {
 	BTF_FIELD_SPIN_LOCK,
 	BTF_FIELD_TIMER,
 	BTF_FIELD_KPTR,
+	BTF_FIELD_RB_NODE,
 };
 
 enum {
@@ -3282,6 +3283,7 @@ static int btf_find_struct_field(const struct btf *btf, const struct btf_type *t
 		switch (field_type) {
 		case BTF_FIELD_SPIN_LOCK:
 		case BTF_FIELD_TIMER:
+		case BTF_FIELD_RB_NODE:
 			ret = btf_find_struct(btf, member_type, off, sz,
 					      idx < info_cnt ? &info[idx] : &tmp);
 			if (ret < 0)
@@ -3332,6 +3334,7 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 		switch (field_type) {
 		case BTF_FIELD_SPIN_LOCK:
 		case BTF_FIELD_TIMER:
+		case BTF_FIELD_RB_NODE:
 			ret = btf_find_struct(btf, var_type, off, sz,
 					      idx < info_cnt ? &info[idx] : &tmp);
 			if (ret < 0)
@@ -3374,6 +3377,11 @@ static int btf_find_field(const struct btf *btf, const struct btf_type *t,
 		sz = sizeof(struct bpf_timer);
 		align = __alignof__(struct bpf_timer);
 		break;
+	case BTF_FIELD_RB_NODE:
+		name = "rb_node";
+		sz = sizeof(struct rb_node);
+		align = __alignof__(struct rb_node);
+		break;
 	case BTF_FIELD_KPTR:
 		name = NULL;
 		sz = sizeof(u64);
@@ -3420,6 +3428,19 @@ int btf_find_timer(const struct btf *btf, const struct btf_type *t)
 	return info.off;
 }
 
+int btf_find_rb_node(const struct btf *btf, const struct btf_type *t)
+{
+	struct btf_field_info info;
+	int ret;
+
+	ret = btf_find_field(btf, t, BTF_FIELD_RB_NODE, &info, 1);
+	if (ret < 0)
+		return ret;
+	if (!ret)
+		return -ENOENT;
+	return info.off;
+}
+
 struct bpf_map_value_off *btf_parse_kptrs(const struct btf *btf,
 					  const struct btf_type *t)
 {
kernel/bpf/syscall.c +3 -0
index 83c7136c5788..3947fbd137af 100644
@@ -1052,6 +1052,8 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf,
 		}
 	}
 
+	map->rb_node_off = btf_find_rb_node(btf, value_type);
+
 	if (map->ops->map_check_btf) {
 		ret = map->ops->map_check_btf(map, btf, key_type, value_type);
 		if (ret < 0)
@@ -1115,6 +1117,7 @@ static int map_create(union bpf_attr *attr)
 
 	map->spin_lock_off = -EINVAL;
 	map->timer_off = -EINVAL;
+	map->rb_node_off = -EINVAL;
 	if (attr->btf_key_type_id || attr->btf_value_type_id ||
 	    /* Even the map's value is a kernel's struct,
 	     * the bpf_prog.o must have BTF to begin with
Signature · 1 line
2.30.2
#10 lore raw

RFC PATCH v2 4/18 bpf: Add rbtree map

In reply to Dave Marchevsky

Introduce a new map type, bpf_rbtree_map, allowing BPF programs to create and manipulate rbtree data structures. bpf_rbtree_map differs from 'classic' BPF map patterns in a few important ways:

* The map does not allocate its own elements. Instead,
BPF programs must call bpf_rbtree_alloc_node helper to allocate and bpf_rbtree_add to add map elem - referred to as 'node' from now on - to the rbtree. This means that rbtree maps can grow dynamically, do not preallocate, and that 'max_entries' has no meaning for rbtree maps.
* Separating allocation and insertion allows alloc_node call to occur in contexts where it's safe to allocate.

* It's possible to remove a node from a rbtree map with bpf_rbtree_remove helper.
* Goal here is to allow a node to be removed from one rbtree and added to another
[ NOTE: This functionality is still in progress ]

Helpers are added to manipulate nodes and trees:
* bpf_rbtree_{alloc,free}_node: Allocate / free node structs
* bpf_rbtree_{add,remove}: Add / remove nodes from rbtree maps
* A comparator function is passed to bpf_rbtree_add in order to find the correct place to add the node.
* bpf_rbtree_find: Find a node matching some condition in the rbtree
* A comparator function is passed in order to determine whether a node matches what's being searched for.

bpf_rbtree_add is very similar to the 'map_push_elem' builtin, but since verifier needs special logic to setup the comparator callback a new helper is added. Same for bpf_rbtree_find and 'map_lookup_elem' builtin.

In order to safely support separate allocation / insertion and passing nodes between rbtrees, some invariants must hold:

* A node that is not in a rbtree map must either be free'd or added to a rbtree map before the program terminates
* Nodes are in this state when returned from bpf_rbtree_alloc_node or bpf_rbtree_remove.

If a node is in a rbtree map it is 'owned' by the map, otherwise it is owned by the BPF program which holds a reference to it. Owner is responsible for the lifetime of the node.

This matches existing acquire / release semantics well. node_alloc and remove operations 'acquire' a node while add and node_free operations 'release' the node. The verifier enforces that acquired nodes are released before program terminates.

Some other implementation details:

* The value type of an rbtree map is expected to be a struct which contains 'struct rb_node' at offset 0.
* BPF programs may not modify the node struct's rb_node field.
* Otherwise the tree could be left in corrupted state
* Rbtree map is value-only. Keys have no meaning
* Since the value type is not known until the rbtree map is instantiated, helper protos have input and return type 'struct rb_node *' which verifier replaces with actual map value type.
* [ TODO: Existing logic prevents any writes to PTR_TO_BTF_ID. This broadly turned off in this patch and replaced with "no writes to struct rb_node is PTR_TO_BTF_ID struct has one". This is a hack and needs to be replaced. ]

---
 include/linux/bpf_types.h      |   1 +
 include/uapi/linux/bpf.h       |  61 ++++++++
 kernel/bpf/Makefile            |   2 +-
 kernel/bpf/helpers.c           |  15 ++
 kernel/bpf/rbtree.c            | 256 +++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c          | 121 +++++++++++++++-
 tools/include/uapi/linux/bpf.h |  61 ++++++++
 7 files changed, 511 insertions(+), 6 deletions(-)
 create mode 100644 kernel/bpf/rbtree.c
include/linux/bpf_types.h +1 -0
index 2b9112b80171..78e9b5253983 100644
@@ -126,6 +126,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_STRUCT_OPS, bpf_struct_ops_map_ops)
 #endif
 BPF_MAP_TYPE(BPF_MAP_TYPE_RINGBUF, ringbuf_map_ops)
 BPF_MAP_TYPE(BPF_MAP_TYPE_BLOOM_FILTER, bloom_filter_map_ops)
+BPF_MAP_TYPE(BPF_MAP_TYPE_RBTREE, rbtree_map_ops)
 
 BPF_LINK_TYPE(BPF_LINK_TYPE_RAW_TRACEPOINT, raw_tracepoint)
 BPF_LINK_TYPE(BPF_LINK_TYPE_TRACING, tracing)
include/uapi/linux/bpf.h +61 -0

79 lines not on this page · raw message

kernel/bpf/Makefile +1 -1
index 057ba8e01e70..00eedab3ad53 100644
@@ -7,7 +7,7 @@ endif
 CFLAGS_core.o += $(call cc-disable-warning, override-init) $(cflags-nogcse-yy)
 
 obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o bpf_iter.o map_iter.o task_iter.o prog_iter.o link_iter.o
-obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o
+obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o rbtree.o
 obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o
 obj-$(CONFIG_BPF_SYSCALL) += bpf_local_storage.o bpf_task_storage.o
 obj-${CONFIG_BPF_LSM}	  += bpf_inode_storage.o
kernel/bpf/helpers.c +15 -0
index 6de4dedf45c0..d18d4d8ca1e2 100644
@@ -1598,6 +1598,11 @@ const struct bpf_func_proto bpf_probe_read_user_str_proto __weak;
 const struct bpf_func_proto bpf_probe_read_kernel_proto __weak;
 const struct bpf_func_proto bpf_probe_read_kernel_str_proto __weak;
 const struct bpf_func_proto bpf_task_pt_regs_proto __weak;
+const struct bpf_func_proto bpf_rbtree_alloc_node_proto __weak;
+const struct bpf_func_proto bpf_rbtree_add_proto __weak;
+const struct bpf_func_proto bpf_rbtree_find_proto __weak;
+const struct bpf_func_proto bpf_rbtree_remove_proto __weak;
+const struct bpf_func_proto bpf_rbtree_free_node_proto __weak;
 
 const struct bpf_func_proto *
 bpf_base_func_proto(enum bpf_func_id func_id)
@@ -1689,6 +1694,16 @@ bpf_base_func_proto(enum bpf_func_id func_id)
 		return &bpf_timer_cancel_proto;
 	case BPF_FUNC_kptr_xchg:
 		return &bpf_kptr_xchg_proto;
+	case BPF_FUNC_rbtree_alloc_node:
+		return &bpf_rbtree_alloc_node_proto;
+	case BPF_FUNC_rbtree_add:
+		return &bpf_rbtree_add_proto;
+	case BPF_FUNC_rbtree_find:
+		return &bpf_rbtree_find_proto;
+	case BPF_FUNC_rbtree_remove:
+		return &bpf_rbtree_remove_proto;
+	case BPF_FUNC_rbtree_free_node:
+		return &bpf_rbtree_free_node_proto;
 	default:
 		break;
 	}
kernel/bpf/rbtree.c new file +256 -0

256 lines not on this page · raw message

kernel/bpf/verifier.c +116 -5

199 lines not on this page · raw message

tools/include/uapi/linux/bpf.h +61 -0

79 lines not on this page · raw message

Signature · 1 line
2.30.2
#11 lore raw

RFC PATCH v2 5/18 libbpf: Add support for private BSS map section

In reply to Dave Marchevsky

Currently libbpf does not allow declaration of a struct bpf_spin_lock in global scope. Attempting to do so results in "failed to re-mmap" error, as .bss arraymap containing spinlock is not allowed to be mmap'd.

This patch adds support for a .bss.private section. The maps contained in this section will not be mmaped into userspace by libbpf, nor will they be exposed via bpftool-generated skeleton.

Intent here is to allow more natural programming pattern for global-scope spinlocks which will be used by rbtree locking mechanism in further patches in this series.

[
RFC Notes:

* Initially I called the section .bss.no_mmap, but the broader 'private' term better indicates that skeleton shouldn't expose these maps at all, IMO.

* bpftool/gen.c's is_internal_mmapable_map function checks whether the map flags have BPF_F_MMAPABLE, so no bpftool changes were necessary to remove .bss.private maps from skeleton
]

---
 tools/lib/bpf/libbpf.c | 65 ++++++++++++++++++++++++++++--------------
 1 file changed, 44 insertions(+), 21 deletions(-)
tools/lib/bpf/libbpf.c +44 -21
index 3f01f5cd8a4c..a6dd53e0c4b4 100644
@@ -463,6 +463,7 @@ struct bpf_struct_ops {
 #define KCONFIG_SEC ".kconfig"
 #define KSYMS_SEC ".ksyms"
 #define STRUCT_OPS_SEC ".struct_ops"
+#define BSS_SEC_PRIVATE ".bss.private"
 
 enum libbpf_map_type {
 	LIBBPF_MAP_UNSPEC,
@@ -576,6 +577,7 @@ enum sec_type {
 	SEC_BSS,
 	SEC_DATA,
 	SEC_RODATA,
+	SEC_BSS_PRIVATE,
 };
 
 struct elf_sec_desc {
@@ -1578,7 +1580,8 @@ bpf_map_find_btf_info(struct bpf_object *obj, struct bpf_map *map);
 
 static int
 bpf_object__init_internal_map(struct bpf_object *obj, enum libbpf_map_type type,
-			      const char *real_name, int sec_idx, void *data, size_t data_sz)
+			      const char *real_name, int sec_idx, void *data,
+			      size_t data_sz, bool do_mmap)
 {
 	struct bpf_map_def *def;
 	struct bpf_map *map;
@@ -1606,27 +1609,31 @@ bpf_object__init_internal_map(struct bpf_object *obj, enum libbpf_map_type type,
 	def->max_entries = 1;
 	def->map_flags = type == LIBBPF_MAP_RODATA || type == LIBBPF_MAP_KCONFIG
 			 ? BPF_F_RDONLY_PROG : 0;
-	def->map_flags |= BPF_F_MMAPABLE;
+	if (do_mmap)
+		def->map_flags |= BPF_F_MMAPABLE;
 
 	pr_debug("map '%s' (global data): at sec_idx %d, offset %zu, flags %x.\n",
 		 map->name, map->sec_idx, map->sec_offset, def->map_flags);
 
-	map->mmaped = mmap(NULL, bpf_map_mmap_sz(map), PROT_READ | PROT_WRITE,
-			   MAP_SHARED | MAP_ANONYMOUS, -1, 0);
-	if (map->mmaped == MAP_FAILED) {
-		err = -errno;
-		map->mmaped = NULL;
-		pr_warn("failed to alloc map '%s' content buffer: %d\n",
-			map->name, err);
-		zfree(&map->real_name);
-		zfree(&map->name);
-		return err;
+	map->mmaped = NULL;
+	if (do_mmap) {
+		map->mmaped = mmap(NULL, bpf_map_mmap_sz(map), PROT_READ | PROT_WRITE,
+				   MAP_SHARED | MAP_ANONYMOUS, -1, 0);
+		if (map->mmaped == MAP_FAILED) {
+			err = -errno;
+			map->mmaped = NULL;
+			pr_warn("failed to alloc map '%s' content buffer: %d\n",
+				map->name, err);
+			zfree(&map->real_name);
+			zfree(&map->name);
+			return err;
+		}
 	}
 
 	/* failures are fine because of maps like .rodata.str1.1 */
 	(void) bpf_map_find_btf_info(obj, map);
 
-	if (data)
+	if (do_mmap && data)
 		memcpy(map->mmaped, data, data_sz);
 
 	pr_debug("map %td is \"%s\"\n", map - obj->maps, map->name);
@@ -1638,12 +1645,14 @@ static int bpf_object__init_global_data_maps(struct bpf_object *obj)
 	struct elf_sec_desc *sec_desc;
 	const char *sec_name;
 	int err = 0, sec_idx;
+	bool do_mmap;
 
 	/*
 	 * Populate obj->maps with libbpf internal maps.
 	 */
 	for (sec_idx = 1; sec_idx < obj->efile.sec_cnt; sec_idx++) {
 		sec_desc = &obj->efile.secs[sec_idx];
+		do_mmap = true;
 
 		/* Skip recognized sections with size 0. */
 		if (sec_desc->data && sec_desc->data->d_size == 0)
@@ -1655,7 +1664,8 @@ static int bpf_object__init_global_data_maps(struct bpf_object *obj)
 			err = bpf_object__init_internal_map(obj, LIBBPF_MAP_DATA,
 							    sec_name, sec_idx,
 							    sec_desc->data->d_buf,
-							    sec_desc->data->d_size);
+							    sec_desc->data->d_size,
+							    do_mmap);
 			break;
 		case SEC_RODATA:
 			obj->has_rodata = true;
@@ -1663,14 +1673,18 @@ static int bpf_object__init_global_data_maps(struct bpf_object *obj)
 			err = bpf_object__init_internal_map(obj, LIBBPF_MAP_RODATA,
 							    sec_name, sec_idx,
 							    sec_desc->data->d_buf,
-							    sec_desc->data->d_size);
+							    sec_desc->data->d_size,
+							    do_mmap);
 			break;
+		case SEC_BSS_PRIVATE:
+			do_mmap = false;
 		case SEC_BSS:
 			sec_name = elf_sec_name(obj, elf_sec_by_idx(obj, sec_idx));
 			err = bpf_object__init_internal_map(obj, LIBBPF_MAP_BSS,
 							    sec_name, sec_idx,
 							    NULL,
-							    sec_desc->data->d_size);
+							    sec_desc->data->d_size,
+							    do_mmap);
 			break;
 		default:
 			/* skip */
@@ -1984,7 +1998,7 @@ static int bpf_object__init_kconfig_map(struct bpf_object *obj)
 	map_sz = last_ext->kcfg.data_off + last_ext->kcfg.sz;
 	err = bpf_object__init_internal_map(obj, LIBBPF_MAP_KCONFIG,
 					    ".kconfig", obj->efile.symbols_shndx,
-					    NULL, map_sz);
+					    NULL, map_sz, true);
 	if (err)
 		return err;
 
@@ -3428,6 +3442,10 @@ static int bpf_object__elf_collect(struct bpf_object *obj)
 			sec_desc->sec_type = SEC_BSS;
 			sec_desc->shdr = sh;
 			sec_desc->data = data;
+		} else if (sh->sh_type == SHT_NOBITS && strcmp(name, BSS_SEC_PRIVATE) == 0) {
+			sec_desc->sec_type = SEC_BSS_PRIVATE;
+			sec_desc->shdr = sh;
+			sec_desc->data = data;
 		} else {
 			pr_info("elf: skipping section(%d) %s (size %zu)\n", idx, name,
 				(size_t)sh->sh_size);
@@ -3890,6 +3908,7 @@ static bool bpf_object__shndx_is_data(const struct bpf_object *obj,
 	case SEC_BSS:
 	case SEC_DATA:
 	case SEC_RODATA:
+	case SEC_BSS_PRIVATE:
 		return true;
 	default:
 		return false;
@@ -3909,6 +3928,7 @@ bpf_object__section_to_libbpf_map_type(const struct bpf_object *obj, int shndx)
 		return LIBBPF_MAP_KCONFIG;
 
 	switch (obj->efile.secs[shndx].sec_type) {
+	case SEC_BSS_PRIVATE:
 	case SEC_BSS:
 		return LIBBPF_MAP_BSS;
 	case SEC_DATA:
@@ -4889,16 +4909,19 @@ bpf_object__populate_internal_map(struct bpf_object *obj, struct bpf_map *map)
 {
 	enum libbpf_map_type map_type = map->libbpf_type;
 	char *cp, errmsg[STRERR_BUFSIZE];
-	int err, zero = 0;
+	int err = 0, zero = 0;
 
 	if (obj->gen_loader) {
-		bpf_gen__map_update_elem(obj->gen_loader, map - obj->maps,
-					 map->mmaped, map->def.value_size);
+		if (map->mmaped)
+			bpf_gen__map_update_elem(obj->gen_loader, map - obj->maps,
+						 map->mmaped, map->def.value_size);
 		if (map_type == LIBBPF_MAP_RODATA || map_type == LIBBPF_MAP_KCONFIG)
 			bpf_gen__map_freeze(obj->gen_loader, map - obj->maps);
 		return 0;
 	}
-	err = bpf_map_update_elem(map->fd, &zero, map->mmaped, 0);
+
+	if (map->mmaped)
+		err = bpf_map_update_elem(map->fd, &zero, map->mmaped, 0);
 	if (err) {
 		err = -errno;
 		cp = libbpf_strerror_r(err, errmsg, sizeof(errmsg));
Signature · 1 line
2.30.2
#12 lore raw

RFC PATCH v2 6/18 bpf: Add bpf_spin_lock member to rbtree

In reply to Dave Marchevsky

This patch adds a struct bpf_spin_lock *lock member to bpf_rbtree, as well as a bpf_rbtree_get_lock helper which allows bpf programs to access the lock.

Ideally the bpf_spin_lock would be created independently oustide of the tree and associated with it before the tree is used, either as part of map definition or via some call like rbtree_init(&rbtree, &lock). Doing this in an ergonomic way is proving harder than expected, so for now use this workaround.

Why is creating the bpf_spin_lock independently and associating it with the tree preferable? Because we want to be able to transfer nodes between trees atomically, and for this to work need same lock associated with 2 trees.

Further locking-related patches will make it possible for the lock to be used in BPF programs and add code which enforces that the lock is held when doing any operation on the tree.

---
 include/uapi/linux/bpf.h       |  7 +++++++
 kernel/bpf/helpers.c           |  3 +++
 kernel/bpf/rbtree.c            | 24 ++++++++++++++++++++++++
 tools/include/uapi/linux/bpf.h |  7 +++++++
 4 files changed, 41 insertions(+)
include/uapi/linux/bpf.h +7 -0
index 1af17b27d34f..06d71207de0b 100644
@@ -5409,6 +5409,12 @@ union bpf_attr {
  *	Return
  *		0
  *
+ * void *bpf_rbtree_get_lock(struct bpf_map *map)
+ *	Description
+ *		Return the bpf_spin_lock associated with the rbtree
+ *
+ *	Return
+ *		Ptr to lock
  */
 #define __BPF_FUNC_MAPPER(FN)		\
 	FN(unspec),			\
@@ -5625,6 +5631,7 @@ union bpf_attr {
 	FN(rbtree_find),		\
 	FN(rbtree_remove),		\
 	FN(rbtree_free_node),		\
+	FN(rbtree_get_lock),		\
 	/* */
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
kernel/bpf/helpers.c +3 -0
index d18d4d8ca1e2..ae974d0aa70d 100644
@@ -1603,6 +1603,7 @@ const struct bpf_func_proto bpf_rbtree_add_proto __weak;
 const struct bpf_func_proto bpf_rbtree_find_proto __weak;
 const struct bpf_func_proto bpf_rbtree_remove_proto __weak;
 const struct bpf_func_proto bpf_rbtree_free_node_proto __weak;
+const struct bpf_func_proto bpf_rbtree_get_lock_proto __weak;
 
 const struct bpf_func_proto *
 bpf_base_func_proto(enum bpf_func_id func_id)
@@ -1704,6 +1705,8 @@ bpf_base_func_proto(enum bpf_func_id func_id)
 		return &bpf_rbtree_remove_proto;
 	case BPF_FUNC_rbtree_free_node:
 		return &bpf_rbtree_free_node_proto;
+	case BPF_FUNC_rbtree_get_lock:
+		return &bpf_rbtree_get_lock_proto;
 	default:
 		break;
 	}
kernel/bpf/rbtree.c +24 -0
index 7d50574e4d57..0cc495b7cb26 100644
@@ -10,6 +10,7 @@
 struct bpf_rbtree {
 	struct bpf_map map;
 	struct rb_root_cached root;
+	struct bpf_spin_lock *lock;
 };
 
 static int rbtree_map_alloc_check(union bpf_attr *attr)
@@ -38,6 +39,14 @@ static struct bpf_map *rbtree_map_alloc(union bpf_attr *attr)
 
 	tree->root = RB_ROOT_CACHED;
 	bpf_map_init_from_attr(&tree->map, attr);
+
+	tree->lock = bpf_map_kzalloc(&tree->map, sizeof(struct bpf_spin_lock),
+				     GFP_KERNEL | __GFP_NOWARN);
+	if (!tree->lock) {
+		bpf_map_area_free(tree);
+		return ERR_PTR(-ENOMEM);
+	}
+
 	return &tree->map;
 }
 
@@ -139,6 +148,7 @@ static void rbtree_map_free(struct bpf_map *map)
 
 	bpf_rbtree_postorder_for_each_entry_safe(pos, n, &tree->root.rb_root)
 		kfree(pos);
+	kfree(tree->lock);
 	bpf_map_area_free(tree);
 }
 
@@ -238,6 +248,20 @@ static int rbtree_map_get_next_key(struct bpf_map *map, void *key,
 	return -ENOTSUPP;
 }
 
+BPF_CALL_1(bpf_rbtree_get_lock, struct bpf_map *, map)
+{
+	struct bpf_rbtree *tree = container_of(map, struct bpf_rbtree, map);
+
+	return (u64)tree->lock;
+}
+
+const struct bpf_func_proto bpf_rbtree_get_lock_proto = {
+	.func = bpf_rbtree_get_lock,
+	.gpl_only = true,
+	.ret_type = RET_PTR_TO_MAP_VALUE,
+	.arg1_type = ARG_CONST_MAP_PTR,
+};
+
 BTF_ID_LIST_SINGLE(bpf_rbtree_map_btf_ids, struct, bpf_rbtree)
 const struct bpf_map_ops rbtree_map_ops = {
 	.map_meta_equal = bpf_map_meta_equal,
tools/include/uapi/linux/bpf.h +7 -0
index 1af17b27d34f..06d71207de0b 100644
@@ -5409,6 +5409,12 @@ union bpf_attr {
  *	Return
  *		0
  *
+ * void *bpf_rbtree_get_lock(struct bpf_map *map)
+ *	Description
+ *		Return the bpf_spin_lock associated with the rbtree
+ *
+ *	Return
+ *		Ptr to lock
  */
 #define __BPF_FUNC_MAPPER(FN)		\
 	FN(unspec),			\
@@ -5625,6 +5631,7 @@ union bpf_attr {
 	FN(rbtree_find),		\
 	FN(rbtree_remove),		\
 	FN(rbtree_free_node),		\
+	FN(rbtree_get_lock),		\
 	/* */
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
Signature · 1 line
2.30.2
#13 lore raw

RFC PATCH v2 7/18 bpf: Add bpf_rbtree_{lock,unlock} helpers

In reply to Dave Marchevsky

These helpers are equivalent to bpf_spin_{lock,unlock}, but the verifier doesn't try to enforce that no helper calls occur when there's an active spin lock.

[ TODO: Currently the verifier doesn't do _anything_ spinlock related when it sees one of these, including setting active_spin_lock. This is probably too lenient. Also, EXPORT_SYMBOL for internal lock helpers might not be the best code structure. ]

Future patches will add enforcement of "rbtree helpers must always be called when lock is held" constraint.

---
 include/uapi/linux/bpf.h       | 20 ++++++++++++++++++++
 kernel/bpf/helpers.c           | 12 ++++++++++--
 kernel/bpf/rbtree.c            | 29 +++++++++++++++++++++++++++++
 kernel/bpf/verifier.c          |  2 ++
 tools/include/uapi/linux/bpf.h | 20 ++++++++++++++++++++
 5 files changed, 81 insertions(+), 2 deletions(-)
include/uapi/linux/bpf.h +20 -0
index 06d71207de0b..f4c615fbf64f 100644
@@ -5415,6 +5415,24 @@ union bpf_attr {
  *
  *	Return
  *		Ptr to lock
+ *
+ * void *bpf_rbtree_lock(struct bpf_spin_lock *lock)
+ *	Description
+ *		Like bpf_spin_lock helper, but use separate helper for now
+ *		as we don't want this helper to have special meaning to the verifier
+ *		so that we can do rbtree helper calls between rbtree_lock/unlock
+ *
+ *	Return
+ *		0
+ *
+ * void *bpf_rbtree_unlock(struct bpf_spin_lock *lock)
+ *	Description
+ *		Like bpf_spin_unlock helper, but use separate helper for now
+ *		as we don't want this helper to have special meaning to the verifier
+ *		so that we can do rbtree helper calls between rbtree_lock/unlock
+ *
+ *	Return
+ *		0
  */
 #define __BPF_FUNC_MAPPER(FN)		\
 	FN(unspec),			\
@@ -5632,6 +5650,8 @@ union bpf_attr {
 	FN(rbtree_remove),		\
 	FN(rbtree_free_node),		\
 	FN(rbtree_get_lock),		\
+	FN(rbtree_lock),		\
+	FN(rbtree_unlock),		\
 	/* */
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
kernel/bpf/helpers.c +10 -2
index ae974d0aa70d..0ca5fed1013b 100644
@@ -316,7 +316,7 @@ static inline void __bpf_spin_unlock(struct bpf_spin_lock *lock)
 
 static DEFINE_PER_CPU(unsigned long, irqsave_flags);
 
-static inline void __bpf_spin_lock_irqsave(struct bpf_spin_lock *lock)
+inline void __bpf_spin_lock_irqsave(struct bpf_spin_lock *lock)
 {
 	unsigned long flags;
 
@@ -324,6 +324,7 @@ static inline void __bpf_spin_lock_irqsave(struct bpf_spin_lock *lock)
 	__bpf_spin_lock(lock);
 	__this_cpu_write(irqsave_flags, flags);
 }
+EXPORT_SYMBOL(__bpf_spin_lock_irqsave);
 
 notrace BPF_CALL_1(bpf_spin_lock, struct bpf_spin_lock *, lock)
 {
@@ -338,7 +339,7 @@ const struct bpf_func_proto bpf_spin_lock_proto = {
 	.arg1_type	= ARG_PTR_TO_SPIN_LOCK,
 };
 
-static inline void __bpf_spin_unlock_irqrestore(struct bpf_spin_lock *lock)
+inline void __bpf_spin_unlock_irqrestore(struct bpf_spin_lock *lock)
 {
 	unsigned long flags;
 
@@ -346,6 +347,7 @@ static inline void __bpf_spin_unlock_irqrestore(struct bpf_spin_lock *lock)
 	__bpf_spin_unlock(lock);
 	local_irq_restore(flags);
 }
+EXPORT_SYMBOL(__bpf_spin_unlock_irqrestore);
 
 notrace BPF_CALL_1(bpf_spin_unlock, struct bpf_spin_lock *, lock)
 {
@@ -1604,6 +1606,8 @@ const struct bpf_func_proto bpf_rbtree_find_proto __weak;
 const struct bpf_func_proto bpf_rbtree_remove_proto __weak;
 const struct bpf_func_proto bpf_rbtree_free_node_proto __weak;
 const struct bpf_func_proto bpf_rbtree_get_lock_proto __weak;
+const struct bpf_func_proto bpf_rbtree_lock_proto __weak;
+const struct bpf_func_proto bpf_rbtree_unlock_proto __weak;
 
 const struct bpf_func_proto *
 bpf_base_func_proto(enum bpf_func_id func_id)
@@ -1707,6 +1711,10 @@ bpf_base_func_proto(enum bpf_func_id func_id)
 		return &bpf_rbtree_free_node_proto;
 	case BPF_FUNC_rbtree_get_lock:
 		return &bpf_rbtree_get_lock_proto;
+	case BPF_FUNC_rbtree_lock:
+		return &bpf_rbtree_lock_proto;
+	case BPF_FUNC_rbtree_unlock:
+		return &bpf_rbtree_unlock_proto;
 	default:
 		break;
 	}
kernel/bpf/rbtree.c +29 -0
index 0cc495b7cb26..641821ee1a7f 100644
@@ -262,6 +262,35 @@ const struct bpf_func_proto bpf_rbtree_get_lock_proto = {
 	.arg1_type = ARG_CONST_MAP_PTR,
 };
 
+extern void __bpf_spin_unlock_irqrestore(struct bpf_spin_lock *lock);
+extern void __bpf_spin_lock_irqsave(struct bpf_spin_lock *lock);
+
+BPF_CALL_1(bpf_rbtree_lock, void *, lock)
+{
+	__bpf_spin_lock_irqsave((struct bpf_spin_lock *)lock);
+	return 0;
+}
+
+const struct bpf_func_proto bpf_rbtree_lock_proto = {
+	.func = bpf_rbtree_lock,
+	.gpl_only = true,
+	.ret_type = RET_INTEGER,
+	.arg1_type = ARG_PTR_TO_SPIN_LOCK,
+};
+
+BPF_CALL_1(bpf_rbtree_unlock, void *, lock)
+{
+	__bpf_spin_unlock_irqrestore((struct bpf_spin_lock *)lock);
+	return 0;
+}
+
+const struct bpf_func_proto bpf_rbtree_unlock_proto = {
+	.func = bpf_rbtree_unlock,
+	.gpl_only = true,
+	.ret_type = RET_INTEGER,
+	.arg1_type = ARG_PTR_TO_SPIN_LOCK,
+};
+
 BTF_ID_LIST_SINGLE(bpf_rbtree_map_btf_ids, struct, bpf_rbtree)
 const struct bpf_map_ops rbtree_map_ops = {
 	.map_meta_equal = bpf_map_meta_equal,
kernel/bpf/verifier.c +2 -0
index 0a2e958ddca8..b9e5d87fe323 100644
@@ -6057,6 +6057,8 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 arg,
 		} else if (meta->func_id == BPF_FUNC_spin_unlock) {
 			if (process_spin_lock(env, regno, false))
 				return -EACCES;
+		} else if (meta->func_id == BPF_FUNC_rbtree_lock ||
+			   meta->func_id == BPF_FUNC_rbtree_unlock) { // Do nothing for now
 		} else {
 			verbose(env, "verifier internal error\n");
 			return -EFAULT;
tools/include/uapi/linux/bpf.h +20 -0
index 06d71207de0b..f4c615fbf64f 100644
@@ -5415,6 +5415,24 @@ union bpf_attr {
  *
  *	Return
  *		Ptr to lock
+ *
+ * void *bpf_rbtree_lock(struct bpf_spin_lock *lock)
+ *	Description
+ *		Like bpf_spin_lock helper, but use separate helper for now
+ *		as we don't want this helper to have special meaning to the verifier
+ *		so that we can do rbtree helper calls between rbtree_lock/unlock
+ *
+ *	Return
+ *		0
+ *
+ * void *bpf_rbtree_unlock(struct bpf_spin_lock *lock)
+ *	Description
+ *		Like bpf_spin_unlock helper, but use separate helper for now
+ *		as we don't want this helper to have special meaning to the verifier
+ *		so that we can do rbtree helper calls between rbtree_lock/unlock
+ *
+ *	Return
+ *		0
  */
 #define __BPF_FUNC_MAPPER(FN)		\
 	FN(unspec),			\
@@ -5632,6 +5650,8 @@ union bpf_attr {
 	FN(rbtree_remove),		\
 	FN(rbtree_free_node),		\
 	FN(rbtree_get_lock),		\
+	FN(rbtree_lock),		\
+	FN(rbtree_unlock),		\
 	/* */
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
Signature · 1 line
2.30.2
#14 lore raw

RFC PATCH v2 8/18 bpf: Enforce spinlock hold for bpf_rbtree_{add,remove,find}

In reply to Dave Marchevsky

The bpf program calling these helpers must hold the spinlock associated with the rbtree map when doing so. Otherwise, a concurrent add/remove operation could corrupt the tree while {add,remove,find} are walking it with callback or pivoting after update.

---
 kernel/bpf/rbtree.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)
kernel/bpf/rbtree.c +14 -0
index 641821ee1a7f..85a1d35818d0 100644
@@ -13,6 +13,11 @@ struct bpf_rbtree {
 	struct bpf_spin_lock *lock;
 };
 
+static bool __rbtree_lock_held(struct bpf_rbtree *tree)
+{
+	return spin_is_locked((spinlock_t *)tree->lock);
+}
+
 static int rbtree_map_alloc_check(union bpf_attr *attr)
 {
 	if (attr->max_entries || !attr->btf_value_type_id)
@@ -92,6 +97,9 @@ BPF_CALL_3(bpf_rbtree_add, struct bpf_map *, map, void *, value, void *, cb)
 	struct bpf_rbtree *tree = container_of(map, struct bpf_rbtree, map);
 	struct rb_node *node = (struct rb_node *)value;
 
+	if (!__rbtree_lock_held(tree))
+		return (u64)NULL;
+
 	if (WARN_ON_ONCE(!RB_EMPTY_NODE(node)))
 		return (u64)NULL;
 
@@ -114,6 +122,9 @@ BPF_CALL_3(bpf_rbtree_find, struct bpf_map *, map, void *, key, void *, cb)
 {
 	struct bpf_rbtree *tree = container_of(map, struct bpf_rbtree, map);
 
+	if (!__rbtree_lock_held(tree))
+		return (u64)NULL;
+
 	return (u64)rb_find(key, &tree->root.rb_root,
 			    (int (*)(const void *key,
 				     const struct rb_node *))cb);
@@ -206,6 +217,9 @@ BPF_CALL_2(bpf_rbtree_remove, struct bpf_map *, map, void *, value)
 	struct bpf_rbtree *tree = container_of(map, struct bpf_rbtree, map);
 	struct rb_node *node = (struct rb_node *)value;
 
+	if (!__rbtree_lock_held(tree))
+		return (u64)NULL;
+
 	if (WARN_ON_ONCE(RB_EMPTY_NODE(node)))
 		return (u64)NULL;
 
Signature · 1 line
2.30.2
#15 lore raw

RFC PATCH v2 9/18 bpf: Support declarative association of lock with rbtree map

In reply to Dave Marchevsky

This patch adds support for association of a bpf_spin_lock in an internal arraymap with an rbtree, using the following pattern:

  struct bpf_spin_lock rbtree_lock SEC(".bss.private");

  struct {
          __uint(type, BPF_MAP_TYPE_RBTREE);
          __type(value, struct node_data);
          __array(lock, struct bpf_spin_lock);
  } rbtree SEC(".maps") = {
          .lock = {
                  [0] = &rbtree_lock,
          },
  };

There are a few benefits of this pattern over existing "init lock as part of map, use bpf_rbtree_get_lock" logic:

* Multiple rbtrees, potentially in different compilation units, may share the same lock

* Lock lifetime does not need to be tied to map lifetime, aside from being strictly greater than map's lifetime

* Can move from bpf_rbtree_{lock,unlock} to more generic bpf_{lock,unlock} helpers while still retaining static verification of locking behavior
* struct bpf_rbtree still keeps lock pointer and this declarative association guarantees that the pointer address is known at rbtree map creation time

Implementation notes:

The mechanics of declarative lock association are heavily inspired by declarative map-in-map inner map definition using __array(values,... . Similarly to map-in-map "values", libbpf's bpf_map init_slots is used to hold the target map, which in the above example is the .bss.private internal arraymap. However, unlike "values" inner maps, the lock is a map value within this map, so it's necessary to also pass the offset of the lock symbol within the internal arraymap.

No uapi changes are necessary as existing BPF_MAP_CREATE map_extra is used to pass the pair (fd of lock map, offset of symbol within lock map) to the kernel when creating the rbtree map. rbtree_map_alloc can then use this pair to find the address of the lock. Logic here is equivalent to verifier's rewrite of BPF_PSEUDO_MAP_FD in check_ld_imm and resolve_pseudo_ldimm64 - get actual struct bpf_map using fd, get address of map's value region using map_direct_value_addr, add offset to get actual lock addr.

This does introduce a dependency on the internal map containing the lock ("lock map") on both the libbpf- and kernel-side. For the former, it's now necessary to init internal global data maps before user btf maps, as the fd of the lock map must be known when data relo on rbtree map is performed. For the latter, rbtree now holds refcount to the lock map to ensure it cannot be freed until after the rbtree map is.

[
RFC NOTE: This patch doesn't change verifier behavior, it's still doing dynamic lock checking. Further patches in the series change this behavior. This patch and the rest of the locking patches should be squashed, leaving in this state for now to make it easier to include or toss things piecemeal after feedback
]

---
 kernel/bpf/rbtree.c    | 47 +++++++++++++++++---
 kernel/bpf/syscall.c   |  8 +++-
 tools/lib/bpf/libbpf.c | 99 +++++++++++++++++++++++++++++++++++++-----
 3 files changed, 136 insertions(+), 18 deletions(-)
kernel/bpf/rbtree.c +40 -7
index 85a1d35818d0..c61662822511 100644
@@ -11,6 +11,7 @@ struct bpf_rbtree {
 	struct bpf_map map;
 	struct rb_root_cached root;
 	struct bpf_spin_lock *lock;
+	struct bpf_map *lock_map;
 };
 
 static bool __rbtree_lock_held(struct bpf_rbtree *tree)
@@ -26,10 +27,22 @@ static int rbtree_map_alloc_check(union bpf_attr *attr)
 	return 0;
 }
 
+static void __rbtree_map_free(struct bpf_rbtree *tree)
+{
+	if (tree->lock_map)
+		bpf_map_put(tree->lock_map);
+	else if (tree->lock)
+		kfree(tree->lock);
+	bpf_map_area_free(tree);
+}
+
 static struct bpf_map *rbtree_map_alloc(union bpf_attr *attr)
 {
+	u32 lock_map_ufd, lock_map_offset;
 	struct bpf_rbtree *tree;
+	u64 lock_map_addr;
 	int numa_node;
+	int err;
 
 	if (!bpf_capable())
 		return ERR_PTR(-EPERM);
@@ -45,14 +58,35 @@ static struct bpf_map *rbtree_map_alloc(union bpf_attr *attr)
 	tree->root = RB_ROOT_CACHED;
 	bpf_map_init_from_attr(&tree->map, attr);
 
-	tree->lock = bpf_map_kzalloc(&tree->map, sizeof(struct bpf_spin_lock),
-				     GFP_KERNEL | __GFP_NOWARN);
-	if (!tree->lock) {
-		bpf_map_area_free(tree);
-		return ERR_PTR(-ENOMEM);
+	if (!attr->map_extra) {
+		tree->lock = bpf_map_kzalloc(&tree->map, sizeof(struct bpf_spin_lock),
+					     GFP_KERNEL | __GFP_NOWARN);
+		if (!tree->lock) {
+			err = -ENOMEM;
+			goto err_free;
+		}
+	} else {
+		lock_map_ufd = (u32)(attr->map_extra >> 32);
+		lock_map_offset = (u32)attr->map_extra;
+		tree->lock_map = bpf_map_get(lock_map_ufd);
+		if (IS_ERR(tree->lock_map) || !tree->lock_map->ops->map_direct_value_addr) {
+			err = PTR_ERR(tree->lock_map);
+			tree->lock_map = NULL;
+			goto err_free;
+		}
+
+		err = tree->lock_map->ops->map_direct_value_addr(tree->lock_map, &lock_map_addr,
+								 lock_map_offset);
+		if (err)
+			goto err_free;
+
+		tree->lock = (struct bpf_spin_lock *)(lock_map_addr + lock_map_offset);
 	}
 
 	return &tree->map;
+err_free:
+	__rbtree_map_free(tree);
+	return ERR_PTR(err);
 }
 
 static struct rb_node *rbtree_map_alloc_node(struct bpf_map *map, size_t sz)
@@ -159,8 +193,7 @@ static void rbtree_map_free(struct bpf_map *map)
 
 	bpf_rbtree_postorder_for_each_entry_safe(pos, n, &tree->root.rb_root)
 		kfree(pos);
-	kfree(tree->lock);
-	bpf_map_area_free(tree);
+	__rbtree_map_free(tree);
 }
 
 static int rbtree_map_check_btf(const struct bpf_map *map,
kernel/bpf/syscall.c +7 -1
index 3947fbd137af..fa1220394462 100644
@@ -1066,6 +1066,12 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf,
 	return ret;
 }
 
+static bool map_uses_map_extra(enum bpf_map_type type)
+{
+	return type == BPF_MAP_TYPE_BLOOM_FILTER ||
+	       type == BPF_MAP_TYPE_RBTREE;
+}
+
 #define BPF_MAP_CREATE_LAST_FIELD map_extra
 /* called via syscall */
 static int map_create(union bpf_attr *attr)
@@ -1087,7 +1093,7 @@ static int map_create(union bpf_attr *attr)
 		return -EINVAL;
 	}
 
-	if (attr->map_type != BPF_MAP_TYPE_BLOOM_FILTER &&
+	if (!map_uses_map_extra(attr->map_type) &&
 	    attr->map_extra != 0)
 		return -EINVAL;
 
tools/lib/bpf/libbpf.c +89 -10

185 lines not on this page · raw message

Signature · 1 line
2.30.2
#16 lore raw

RFC PATCH v2 10/18 bpf: Verifier tracking of rbtree_spin_lock held

In reply to Dave Marchevsky

This patch teaches the verifier that rbtree_{lock,unlock} interact with locks and eases use of rbtree_lock(&some_lock) where &some_lock is in a global internal map.

The verifier now tracks lock id for rbtree_{lock,unlock} and understands that lock can / must be held when calling various other rbtree helpers.

Logic is also added to ease this pattern:

  /* internal map */
  struct bpf_spin_lock lock SEC(".bss.private");

/* In bpf prog */

  rbtree_lock(&lock);
  /* ... use all registers for other work */
  rbtree_unlock(&lock);

In the above example, the prog compiles down to something like:

r1 = 0x12345
call rbtree_lock
/* begin other work
r1 = some_unrelated_value
r2 = r1 or similar never happens
*/
r1 = 0x12345
call rbtree_unlock

Each time "r1 = 0x12345" happens, verifier's check_ld_imm will assign a new id to the lock, which will result in it later complaining that the incorrect lock is being unlocked when checking rbtree_unlock.

To help with this pattern, bpf_verifier_state now has a maybe_active_spin_lock_addr field. If this field is nonzero and bpf_verifier_state's active_spin_lock is also nonzero, then maybe_active_spin_lock_addr contains the address of the active spin lock (corresponding to active_spin_lock's id). This allows the verifier to avoid assigning a new lock id when it sees the second "r1 = 0x12345", since it can recognize that the address matches an existing lock id.

[ RFC Notes:

* rbtree_process_spin_lock should be merged w/ normal process_spin_lock, same with rbtree_lock and normal lock helpers. Left separate for now to highlight the logic differences.

* The hacky maybe_active_spin_lock_addr logic can be improved by adding support to a custom .lock section similar to existing use of .bss.private. The new section type would function like .bss.private, but the verifier would know that locks in .lock are likely to be used like bpf_spin_lock(&lock), and could track the address of each map value for deduping, instead of just tracking single address. For multiple-lock scenario this is probably necessary.
]

---
 include/linux/bpf.h          |   2 +
 include/linux/bpf_verifier.h |   1 +
 kernel/bpf/rbtree.c          |   2 +-
 kernel/bpf/verifier.c        | 136 ++++++++++++++++++++++++++++++++---
 4 files changed, 129 insertions(+), 12 deletions(-)
include/linux/bpf.h +2 -0
index b4a44ffb0d6c..d6458aa7b79c 100644
@@ -497,6 +497,7 @@ enum bpf_return_type {
 	RET_PTR_TO_ALLOC_MEM,		/* returns a pointer to dynamically allocated memory */
 	RET_PTR_TO_MEM_OR_BTF_ID,	/* returns a pointer to a valid memory or a btf_id */
 	RET_PTR_TO_BTF_ID,		/* returns a pointer to a btf_id */
+	RET_PTR_TO_SPIN_LOCK,		/* returns a pointer to a struct bpf_spin_lock */
 	__BPF_RET_TYPE_MAX,
 
 	/* Extended ret_types. */
@@ -612,6 +613,7 @@ enum bpf_reg_type {
 	PTR_TO_MEM,		 /* reg points to valid memory region */
 	PTR_TO_BUF,		 /* reg points to a read/write buffer */
 	PTR_TO_FUNC,		 /* reg points to a bpf program function */
+	PTR_TO_SPIN_LOCK,	 /* reg points to a struct bpf_spin_lock */
 	__BPF_REG_TYPE_MAX,
 
 	/* Extended reg_types. */
include/linux/bpf_verifier.h +1 -0
index 9c017575c034..f81638844a4d 100644
@@ -313,6 +313,7 @@ struct bpf_verifier_state {
 	u32 insn_idx;
 	u32 curframe;
 	u32 active_spin_lock;
+	void *maybe_active_spin_lock_addr;
 	bool speculative;
 
 	/* first and last insn idx of this verifier state */
kernel/bpf/rbtree.c +1 -1
index c61662822511..0821e841a518 100644
@@ -305,7 +305,7 @@ BPF_CALL_1(bpf_rbtree_get_lock, struct bpf_map *, map)
 const struct bpf_func_proto bpf_rbtree_get_lock_proto = {
 	.func = bpf_rbtree_get_lock,
 	.gpl_only = true,
-	.ret_type = RET_PTR_TO_MAP_VALUE,
+	.ret_type = RET_PTR_TO_SPIN_LOCK,
 	.arg1_type = ARG_CONST_MAP_PTR,
 };
 
kernel/bpf/verifier.c +125 -11

235 lines not on this page · raw message

Signature · 1 line
2.30.2
#17 lore raw

RFC PATCH v2 11/18 bpf: Check rbtree lock held during verification

In reply to Dave Marchevsky

This patch builds on the previous few locking patches, teaching the verifier to check whether rbtree's lock is held.

[ RFC Notes:

* After this patch, could change helpers which only can fail due to dynamic lock check to always succeed, likely allowing us to get rid of CONDITIONAL_RELEASE logic. But since dynamic lock checking is almost certainly going to be necessary regardless, didn't do so.
]

---
 include/linux/bpf.h   |  2 ++
 kernel/bpf/rbtree.c   |  8 ++++++++
 kernel/bpf/verifier.c | 43 +++++++++++++++++++++++++++++++++++++++----
 3 files changed, 49 insertions(+), 4 deletions(-)
include/linux/bpf.h +2 -0
index d6458aa7b79c..b762c6b3dcfb 100644
@@ -155,6 +155,8 @@ struct bpf_map_ops {
 				     bpf_callback_t callback_fn,
 				     void *callback_ctx, u64 flags);
 
+	bool (*map_lock_held)(struct bpf_map *map, void *current_lock);
+
 	/* BTF id of struct allocated by map_alloc */
 	int *map_btf_id;
 
kernel/bpf/rbtree.c +8 -0
index 0821e841a518..b5d158254de6 100644
@@ -245,6 +245,13 @@ static int rbtree_map_delete_elem(struct bpf_map *map, void *value)
 	return -ENOTSUPP;
 }
 
+static bool rbtree_map_lock_held(struct bpf_map *map, void *current_lock)
+{
+	struct bpf_rbtree *tree = container_of(map, struct bpf_rbtree, map);
+
+	return tree->lock == current_lock;
+}
+
 BPF_CALL_2(bpf_rbtree_remove, struct bpf_map *, map, void *, value)
 {
 	struct bpf_rbtree *tree = container_of(map, struct bpf_rbtree, map);
@@ -353,4 +360,5 @@ const struct bpf_map_ops rbtree_map_ops = {
 	.map_delete_elem = rbtree_map_delete_elem,
 	.map_check_btf = rbtree_map_check_btf,
 	.map_btf_id = &bpf_rbtree_map_btf_ids[0],
+	.map_lock_held = rbtree_map_lock_held,
 };
kernel/bpf/verifier.c +39 -4

67 lines not on this page · raw message

Signature · 1 line
2.30.2
#18 lore raw

RFC PATCH v2 12/18 bpf: Add OBJ_NON_OWNING_REF type flag

In reply to Dave Marchevsky

Consider a pointer to a type that would normally need acquire / release semantics to be safely held. There may be scenarios where such a pointer can be safely held without the need to acquire a reference.

For example, although a PTR_TO_BTF_ID for a rbtree_map node is released via bpf_rbtree_add helper, the helper doesn't change the address of the node and must be called with the rbtree_map's spinlock held. Since the only way to remove a node from the rbtree - bpf_rbtree_remove helper - requires the same lock, the newly-added node cannot be removed by a concurrently-running program until the lock is released. Therefore it is safe to hold a reference to this node until bpf_rbtree_unlock is called.

This patch introduces a new type flag and associated verifier logic to handle such "non-owning" references.

Currently the only usecase I have is the rbtree example above, so the verifier logic is straightforward:
* Tag return types of bpf_rbtree_{add,find} with OBJ_NON_OWNING_REF
* These both require the rbtree lock to be held to return anything non-NULL
* Since ret type for both is PTR_TO_BTF_ID_OR_NULL, if lock is not held and NULL is returned, existing mark_ptr_or_null_reg logic will clear reg type.
* So if mark_ptr_or_null_reg logic turns the returned reg into a PTR_TO_BTF_ID | OBJ_NON_OWNING_REF, verifier knows lock is held.

* When the lock is released the verifier invalidates any regs holding non owning refs similarly to existing release_reference logic - but no need to clear ref_obj_id as an 'owning' reference was never acquired.

[ TODO: Currently the invalidation logic in clear_rbtree_node_non_owning_refs is not parametrized by map so unlocking any rbtree lock will invalidate all non-owning refs ]

---
 include/linux/bpf.h   |  1 +
 kernel/bpf/rbtree.c   |  4 +--
 kernel/bpf/verifier.c | 65 +++++++++++++++++++++++++++++++++++++++----
 3 files changed, 62 insertions(+), 8 deletions(-)
include/linux/bpf.h +1 -0
index b762c6b3dcfb..f164bd6e2f3a 100644
@@ -415,6 +415,7 @@ enum bpf_type_flag {
 	/* Size is known at compile time. */
 	MEM_FIXED_SIZE		= BIT(10 + BPF_BASE_TYPE_BITS),
 
+	OBJ_NON_OWNING_REF	= BIT(11 + BPF_BASE_TYPE_BITS),
 	__BPF_TYPE_FLAG_MAX,
 	__BPF_TYPE_LAST_FLAG	= __BPF_TYPE_FLAG_MAX - 1,
 };
kernel/bpf/rbtree.c +2 -2
index b5d158254de6..cc89639df8a2 100644
@@ -144,7 +144,7 @@ BPF_CALL_3(bpf_rbtree_add, struct bpf_map *, map, void *, value, void *, cb)
 const struct bpf_func_proto bpf_rbtree_add_proto = {
 	.func = bpf_rbtree_add,
 	.gpl_only = true,
-	.ret_type = RET_PTR_TO_BTF_ID_OR_NULL,
+	.ret_type = RET_PTR_TO_BTF_ID_OR_NULL | OBJ_NON_OWNING_REF,
 	.ret_btf_id = BPF_PTR_POISON,
 	.arg1_type = ARG_CONST_MAP_PTR,
 	.arg2_type = ARG_PTR_TO_BTF_ID | OBJ_RELEASE,
@@ -167,7 +167,7 @@ BPF_CALL_3(bpf_rbtree_find, struct bpf_map *, map, void *, key, void *, cb)
 const struct bpf_func_proto bpf_rbtree_find_proto = {
 	.func = bpf_rbtree_find,
 	.gpl_only = true,
-	.ret_type = RET_PTR_TO_BTF_ID_OR_NULL,
+	.ret_type = RET_PTR_TO_BTF_ID_OR_NULL | OBJ_NON_OWNING_REF,
 	.ret_btf_id = BPF_PTR_POISON,
 	.arg1_type = ARG_CONST_MAP_PTR,
 	.arg2_type = ARG_ANYTHING,
kernel/bpf/verifier.c +59 -6

109 lines not on this page · raw message

Signature · 1 line
2.30.2
#19 lore raw

RFC PATCH v2 13/18 bpf: Add CONDITIONAL_RELEASE type flag

In reply to Dave Marchevsky

Currently if a helper proto has an arg with OBJ_RELEASE flag, the verifier assumes the 'release' logic in the helper will always succeed, and therefore always clears the arg reg, other regs w/ same ref_obj_id, and releases the reference. This poses a problem for 'release' helpers which may not always succeed.

For example, bpf_rbtree_add will fail to add the passed-in node to a bpf_rbtree if the rbtree's lock is not held when the helper is called. In this case the helper returns NULL and the calling bpf program must release the node in another way before terminating to avoid leaking memory. An example of such logic:

1  struct node_data *node = bpf_rbtree_alloc_node(&rbtree, ...);
2  struct node_data *ret = bpf_rbtree_add(&rbtree, node);
3  if (!ret) {

4 bpf_rbtree_free_node(node);
5 return 0;
6 }
7 bpf_trace_printk("%d\n", ret->id);

However, current verifier logic does not allow this: after line 2, ref_obj_id of reg holding 'node' (BPF_REG_2) will be released via release_reference function, which will mark BPF_REG_2 and any other reg with same ref_obj_id as unknown. As a result neither ret nor node will point to anything useful if line 3's check passes. Additionally, since the reference is unconditionally released, the program would pass the verifier without the null check.

This patch adds 'conditional release' semantics so that the verifier can handle the above example correctly. The CONDITIONAL_RELEASE type flag works in concert with the existing OBJ_RELEASE flag - the latter is used to tag an argument, while the new type flag is used to tag return type.

If a helper has an OBJ_RELEASE arg type and CONDITIONAL_RELEASE return type, the helper is considered to use its return value to indicate success or failure of the release operation. NULL is returned if release fails, non-null otherwise.

For my concrete usecase - bpf_rbtree_add - CONDITIONAL_RELEASE works in concert with OBJ_NON_OWNING_REF: successful release results in a non-owning reference being returned, allowing line 7 in above example.

Instead of unconditionally releasing the OBJ_RELEASE reference when doing check_helper_call, for CONDITIONAL_RELEASE helpers the verifier will wait until the return value is checked for null.
If not null: the reference is released

If null: no reference is released. Since other regs w/ same ref_obj_id
were not marked unknown by check_helper_call, they can be used to release the reference via other means (line 4 above),

It's necessary to prevent conditionally-released ref_obj_id regs from being used between the release helper and null check. For example:

1  struct node_data *node = bpf_rbtree_alloc_node(&rbtree, ...);
2  struct node_data *ret = bpf_rbtree_add(&rbtree, node);
3  do_something_with_a_node(node);
4  if (!ret) {

5 bpf_rbtree_free_node(node);
6 return 0;
7 }

Line 3 shouldn't be allowed since node may have been released. The verifier tags all regs with ref_obj_id of the conditionally-released arg in the period between the helper call and null check for this reason.

Why no matching CONDITIONAL_ACQUIRE type flag? Existing verifier logic already treats acquire of an _OR_NULL type as a conditional acquire. Consider this code:

1 struct thing *i = acquire_helper_that_returns_thing_or_null(); 2 if (!i)
3 return 0;
4 manipulate_thing(i);
5 release_thing(i);

After line 1, BPF_REG_0 will have an _OR_NULL type and a ref_obj_id set. When the verifier sees line 2's conditional jump, existing logic in mark_ptr_or_null_regs, specifically the if:

if (ref_obj_id && ref_obj_id == id && is_null)

          /* regs[regno] is in the " == NULL" branch.
           * No one could have freed the reference state before
           * doing the NULL check.
           */
           WARN_ON_ONCE(release_reference_state(state, id));

will release the reference in the is_null state.

[ TODO: Either need to remove WARN_ON_ONCE there without adding CONDITIONAL_ACQUIRE flag or add the flag and don't WARN_ON_ONCE if it's set. Left out of first pass for simplicity's sake. ]

---
 include/linux/bpf.h          |   3 +
 include/linux/bpf_verifier.h |   1 +
 kernel/bpf/rbtree.c          |   2 +-
 kernel/bpf/verifier.c        | 114 +++++++++++++++++++++++++++++++----
 4 files changed, 108 insertions(+), 12 deletions(-)
include/linux/bpf.h +3 -0
index f164bd6e2f3a..83b8d63545e3 100644
@@ -416,6 +416,9 @@ enum bpf_type_flag {
 	MEM_FIXED_SIZE		= BIT(10 + BPF_BASE_TYPE_BITS),
 
 	OBJ_NON_OWNING_REF	= BIT(11 + BPF_BASE_TYPE_BITS),
+
+	CONDITIONAL_RELEASE	= BIT(12 + BPF_BASE_TYPE_BITS),
+
 	__BPF_TYPE_FLAG_MAX,
 	__BPF_TYPE_LAST_FLAG	= __BPF_TYPE_FLAG_MAX - 1,
 };
include/linux/bpf_verifier.h +1 -0
index f81638844a4d..e5f967d17bb9 100644
@@ -314,6 +314,7 @@ struct bpf_verifier_state {
 	u32 curframe;
 	u32 active_spin_lock;
 	void *maybe_active_spin_lock_addr;
+	u32 active_cond_ref_obj_id;
 	bool speculative;
 
 	/* first and last insn idx of this verifier state */
kernel/bpf/rbtree.c +1 -1
index cc89639df8a2..e6f51c27661c 100644
@@ -144,7 +144,7 @@ BPF_CALL_3(bpf_rbtree_add, struct bpf_map *, map, void *, value, void *, cb)
 const struct bpf_func_proto bpf_rbtree_add_proto = {
 	.func = bpf_rbtree_add,
 	.gpl_only = true,
-	.ret_type = RET_PTR_TO_BTF_ID_OR_NULL | OBJ_NON_OWNING_REF,
+	.ret_type = RET_PTR_TO_BTF_ID_OR_NULL | OBJ_NON_OWNING_REF | CONDITIONAL_RELEASE,
 	.ret_btf_id = BPF_PTR_POISON,
 	.arg1_type = ARG_CONST_MAP_PTR,
 	.arg2_type = ARG_PTR_TO_BTF_ID | OBJ_RELEASE,
kernel/bpf/verifier.c +103 -11

186 lines not on this page · raw message

Signature · 1 line
2.30.2
#20 lore raw

RFC PATCH v2 14/18 bpf: Introduce PTR_ITER and PTR_ITER_END type flags

In reply to Dave Marchevsky

Add two type flags, PTR_ITER and PTR_ITER_END, meant to support the following pattern for iterating data structures:

  struct node *elem = data_structure_iter_first(&some_map)
  while (elem) {
    do_something();
    elem = data_structure_iter_next(&some_map, elem);
  }

Currently the ret_type of both _first() and _next() helpers would be PTR_TO_BTF_ID_OR_NULL and the verifier would consider the loop to be infinite as it knows nothing about an arbitrary PTR_TO_BTF_ID value.

However, if we can express "this PTR_TO_BTF_ID will eventually be NULL if used in iteration helpers" via a new type flag, the verifier can use this information to determine that the loop will terminate while still verifying the loop body.

So for our contrived example above, _first() now returns a PTR_TO_BTF_ID_OR_NULL | PTR_ITER, which _next() expects as input, itself returning PTR_TO_BTF_ID_OR_NULL | PTR_ITER_END.

The verifier does nothing special for PTR_ITER, so the first iteration of the example loop will result in both elem == NULL and elem != NULL branches being verified. When verifying the latter branch, elem will become a PTR_TO_BTF_ID_OR_NULL | PTR_ITER_END.

When the verifier sees a reg holding PTR_ITER_END in a conditional jump it knows the reg type and val can be replaced with SCALAR 0. So in the example loop on 2nd iteration elem == NULL will be assumed and verification will continue with that branch only.

[ TODO:
* PTR_ITER needs to be associated with the helper that produced it, to prevent something like:

    struct node *elem = data_structure_iter_last(&some_map)
    while (elem) {
      do_something();
      elem = data_structure_iter_next(&some_map, elem);
    }

i.e. _first() and _next() should be used together, same with _last() and _prev().

* This is currently very unsafe. Per multiple conversations w/ Alexei and Andrii, there are probably some ways forward here, but may be more complex than it's worth. If so, can migrate to a callback-based approach with similar functionality .
]

---
 include/linux/bpf.h            |  3 ++
 include/uapi/linux/bpf.h       | 32 ++++++++++++++
 kernel/bpf/helpers.c           | 12 ++++++
 kernel/bpf/rbtree.c            | 78 ++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c          | 53 +++++++++++++++++++++--
 tools/include/uapi/linux/bpf.h | 32 ++++++++++++++
 6 files changed, 207 insertions(+), 3 deletions(-)
include/linux/bpf.h +3 -0
index 83b8d63545e3..f4aabfa943c1 100644
@@ -419,6 +419,9 @@ enum bpf_type_flag {
 
 	CONDITIONAL_RELEASE	= BIT(12 + BPF_BASE_TYPE_BITS),
 
+	PTR_ITER	= BIT(13 + BPF_BASE_TYPE_BITS),
+	PTR_ITER_END	= BIT(14 + BPF_BASE_TYPE_BITS),
+
 	__BPF_TYPE_FLAG_MAX,
 	__BPF_TYPE_LAST_FLAG	= __BPF_TYPE_FLAG_MAX - 1,
 };
include/uapi/linux/bpf.h +32 -0
index f4c615fbf64f..bb556c449cf0 100644
@@ -5433,6 +5433,34 @@ union bpf_attr {
  *
  *	Return
  *		0
+ *
+ * long bpf_rbtree_first(struct bpf_map *map)
+ *	Description
+ *		Return the first node in the tree according to sort order
+ *
+ *	Return
+ *		If found, ptr to node, otherwise NULL
+ *
+ * long bpf_rbtree_last(struct bpf_map *map)
+ *	Description
+ *		Return the last node in the tree according to sort order
+ *
+ *	Return
+ *		If found, ptr to node, otherwise NULL
+ *
+ * long bpf_rbtree_next(struct bpf_map *map, void *cur)
+ *	Description
+ *		Return the next node in the tree according to sort order
+ *
+ *	Return
+ *		If found, ptr to node, otherwise NULL
+ *
+ * long bpf_rbtree_prev(struct bpf_map *map, void *cur)
+ *	Description
+ *		Return the previous node in the tree according to sort order
+ *
+ *	Return
+ *		If found, ptr to node, otherwise NULL
  */
 #define __BPF_FUNC_MAPPER(FN)		\
 	FN(unspec),			\
@@ -5652,6 +5680,10 @@ union bpf_attr {
 	FN(rbtree_get_lock),		\
 	FN(rbtree_lock),		\
 	FN(rbtree_unlock),		\
+	FN(rbtree_first),		\
+	FN(rbtree_last),		\
+	FN(rbtree_next),		\
+	FN(rbtree_prev),		\
 	/* */
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
kernel/bpf/helpers.c +12 -0
index 0ca5fed1013b..32e245c559c4 100644
@@ -1608,6 +1608,10 @@ const struct bpf_func_proto bpf_rbtree_free_node_proto __weak;
 const struct bpf_func_proto bpf_rbtree_get_lock_proto __weak;
 const struct bpf_func_proto bpf_rbtree_lock_proto __weak;
 const struct bpf_func_proto bpf_rbtree_unlock_proto __weak;
+const struct bpf_func_proto bpf_rbtree_first_proto __weak;
+const struct bpf_func_proto bpf_rbtree_last_proto __weak;
+const struct bpf_func_proto bpf_rbtree_next_proto __weak;
+const struct bpf_func_proto bpf_rbtree_prev_proto __weak;
 
 const struct bpf_func_proto *
 bpf_base_func_proto(enum bpf_func_id func_id)
@@ -1715,6 +1719,14 @@ bpf_base_func_proto(enum bpf_func_id func_id)
 		return &bpf_rbtree_lock_proto;
 	case BPF_FUNC_rbtree_unlock:
 		return &bpf_rbtree_unlock_proto;
+	case BPF_FUNC_rbtree_first:
+		return &bpf_rbtree_first_proto;
+	case BPF_FUNC_rbtree_last:
+		return &bpf_rbtree_last_proto;
+	case BPF_FUNC_rbtree_next:
+		return &bpf_rbtree_next_proto;
+	case BPF_FUNC_rbtree_prev:
+		return &bpf_rbtree_prev_proto;
 	default:
 		break;
 	}
kernel/bpf/rbtree.c +78 -0

84 lines not on this page · raw message

kernel/bpf/verifier.c +50 -3

113 lines not on this page · raw message

tools/include/uapi/linux/bpf.h +32 -0
index f4c615fbf64f..bb556c449cf0 100644
@@ -5433,6 +5433,34 @@ union bpf_attr {
  *
  *	Return
  *		0
+ *
+ * long bpf_rbtree_first(struct bpf_map *map)
+ *	Description
+ *		Return the first node in the tree according to sort order
+ *
+ *	Return
+ *		If found, ptr to node, otherwise NULL
+ *
+ * long bpf_rbtree_last(struct bpf_map *map)
+ *	Description
+ *		Return the last node in the tree according to sort order
+ *
+ *	Return
+ *		If found, ptr to node, otherwise NULL
+ *
+ * long bpf_rbtree_next(struct bpf_map *map, void *cur)
+ *	Description
+ *		Return the next node in the tree according to sort order
+ *
+ *	Return
+ *		If found, ptr to node, otherwise NULL
+ *
+ * long bpf_rbtree_prev(struct bpf_map *map, void *cur)
+ *	Description
+ *		Return the previous node in the tree according to sort order
+ *
+ *	Return
+ *		If found, ptr to node, otherwise NULL
  */
 #define __BPF_FUNC_MAPPER(FN)		\
 	FN(unspec),			\
@@ -5652,6 +5680,10 @@ union bpf_attr {
 	FN(rbtree_get_lock),		\
 	FN(rbtree_lock),		\
 	FN(rbtree_unlock),		\
+	FN(rbtree_first),		\
+	FN(rbtree_last),		\
+	FN(rbtree_next),		\
+	FN(rbtree_prev),		\
 	/* */
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
Signature · 1 line
2.30.2
#21 lore raw

RFC PATCH v2 15/18 selftests/bpf: Add rbtree map tests

In reply to Dave Marchevsky

Add tests demonstrating happy path of rbtree map usage as well as exercising numerous failure paths and conditions. Structure of failing test runner is based on dynptr tests.

---
 .../selftests/bpf/prog_tests/rbtree_map.c     | 164 ++++++++++++
 .../testing/selftests/bpf/progs/rbtree_map.c  | 111 ++++++++
 .../selftests/bpf/progs/rbtree_map_fail.c     | 236 ++++++++++++++++++
 .../bpf/progs/rbtree_map_load_fail.c          |  24 ++
 4 files changed, 535 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/rbtree_map.c
 create mode 100644 tools/testing/selftests/bpf/progs/rbtree_map.c
 create mode 100644 tools/testing/selftests/bpf/progs/rbtree_map_fail.c
 create mode 100644 tools/testing/selftests/bpf/progs/rbtree_map_load_fail.c
tools/testing/selftests/bpf/prog_tests/rbtree_map.c new file +164 -0
new file mode 100644
index 000000000000..17cadcd05ee4
@@ -0,0 +1,164 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */
+
+#include <sys/syscall.h>
+#include <test_progs.h>
+#include "rbtree_map.skel.h"
+#include "rbtree_map_fail.skel.h"
+#include "rbtree_map_load_fail.skel.h"
+
+static size_t log_buf_sz = 1048576; /* 1 MB */
+static char obj_log_buf[1048576];
+
+static struct {
+	const char *prog_name;
+	const char *expected_err_msg;
+} rbtree_prog_load_fail_tests[] = {
+	{"rb_node__field_store", "only read is supported"},
+	{"rb_node__alloc_no_add", "Unreleased reference id=2 alloc_insn=3"},
+	{"rb_node__two_alloc_one_add", "Unreleased reference id=2 alloc_insn=3"},
+	{"rb_node__remove_no_free", "Unreleased reference id=5 alloc_insn=28"},
+	{"rb_tree__add_wrong_type", "rbtree: R2 is of type task_struct but node_data is expected"},
+	{"rb_tree__conditional_release_helper_usage",
+		"R2 type=ptr_cond_rel_ expected=ptr_"},
+};
+
+void test_rbtree_map_load_fail(void)
+{
+	struct rbtree_map_load_fail *skel;
+
+	skel = rbtree_map_load_fail__open_and_load();
+	if (!ASSERT_ERR_PTR(skel, "rbtree_map_load_fail__open_and_load"))
+		rbtree_map_load_fail__destroy(skel);
+}
+
+static void verify_fail(const char *prog_name, const char *expected_err_msg)
+{
+	LIBBPF_OPTS(bpf_object_open_opts, opts);
+	struct rbtree_map_fail *skel;
+	struct bpf_program *prog;
+	int err;
+
+	opts.kernel_log_buf = obj_log_buf;
+	opts.kernel_log_size = log_buf_sz;
+	opts.kernel_log_level = 1;
+
+	skel = rbtree_map_fail__open_opts(&opts);
+	if (!ASSERT_OK_PTR(skel, "rbtree_map_fail__open_opts"))
+		goto cleanup;
+
+	prog = bpf_object__find_program_by_name(skel->obj, prog_name);
+	if (!ASSERT_OK_PTR(prog, "bpf_object__find_program_by_name"))
+		goto cleanup;
+
+	bpf_program__set_autoload(prog, true);
+	err = rbtree_map_fail__load(skel);
+	if (!ASSERT_ERR(err, "unexpected load success"))
+		goto cleanup;
+
+	if (!ASSERT_OK_PTR(strstr(obj_log_buf, expected_err_msg), "expected_err_msg")) {
+		fprintf(stderr, "Expected err_msg: %s\n", expected_err_msg);
+		fprintf(stderr, "Verifier output: %s\n", obj_log_buf);
+	}
+
+cleanup:
+	rbtree_map_fail__destroy(skel);
+}
+
+void test_rbtree_map_alloc_node__size_too_small(void)
+{
+	struct rbtree_map_fail *skel;
+	struct bpf_program *prog;
+	struct bpf_link *link;
+	int err;
+
+	skel = rbtree_map_fail__open();
+	if (!ASSERT_OK_PTR(skel, "rbtree_map_fail__open"))
+		goto cleanup;
+
+	prog = skel->progs.alloc_node__size_too_small;
+	bpf_program__set_autoload(prog, true);
+
+	err = rbtree_map_fail__load(skel);
+	if (!ASSERT_OK(err, "unexpected load fail"))
+		goto cleanup;
+
+	link = bpf_program__attach(skel->progs.alloc_node__size_too_small);
+	if (!ASSERT_OK_PTR(link, "link"))
+		goto cleanup;
+
+	syscall(SYS_getpgid);
+
+	ASSERT_EQ(skel->bss->size_too_small__alloc_fail, 1, "alloc_fail");
+
+	bpf_link__destroy(link);
+cleanup:
+	rbtree_map_fail__destroy(skel);
+}
+
+void test_rbtree_map_add_node__no_lock(void)
+{
+	struct rbtree_map_fail *skel;
+	struct bpf_program *prog;
+	struct bpf_link *link;
+	int err;
+
+	skel = rbtree_map_fail__open();
+	if (!ASSERT_OK_PTR(skel, "rbtree_map_fail__open"))
+		goto cleanup;
+
+	prog = skel->progs.add_node__no_lock;
+	bpf_program__set_autoload(prog, true);
+
+	err = rbtree_map_fail__load(skel);
+	if (!ASSERT_OK(err, "unexpected load fail"))
+		goto cleanup;
+
+	link = bpf_program__attach(skel->progs.add_node__no_lock);
+	if (!ASSERT_OK_PTR(link, "link"))
+		goto cleanup;
+
+	syscall(SYS_getpgid);
+
+	ASSERT_EQ(skel->bss->no_lock_add__fail, 1, "alloc_fail");
+
+	bpf_link__destroy(link);
+cleanup:
+	rbtree_map_fail__destroy(skel);
+}
+
+void test_rbtree_map_prog_load_fail(void)
+{
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(rbtree_prog_load_fail_tests); i++) {
+		if (!test__start_subtest(rbtree_prog_load_fail_tests[i].prog_name))
+			continue;
+
+		verify_fail(rbtree_prog_load_fail_tests[i].prog_name,
+			    rbtree_prog_load_fail_tests[i].expected_err_msg);
+	}
+}
+
+void test_rbtree_map(void)
+{
+	struct rbtree_map *skel;
+	struct bpf_link *link;
+
+	skel = rbtree_map__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "rbtree_map__open_and_load"))
+		goto cleanup;
+
+	link = bpf_program__attach(skel->progs.check_rbtree);
+	if (!ASSERT_OK_PTR(link, "link"))
+		goto cleanup;
+
+	for (int i = 0; i < 100; i++)
+		syscall(SYS_getpgid);
+
+	ASSERT_EQ(skel->bss->calls, 100, "calls_equal");
+
+	bpf_link__destroy(link);
+cleanup:
+	rbtree_map__destroy(skel);
+}
tools/testing/selftests/bpf/progs/rbtree_map.c new file +111 -0

111 lines not on this page · raw message

tools/testing/selftests/bpf/progs/rbtree_map_fail.c new file +236 -0

236 lines not on this page · raw message

tools/testing/selftests/bpf/progs/rbtree_map_load_fail.c new file +24 -0
new file mode 100644
index 000000000000..036558eedd66
@@ -0,0 +1,24 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */
+
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+
+struct node_data_no_rb_node {
+	__u64 one;
+	__u64 two;
+	__u64 three;
+	__u64 four;
+	__u64 five;
+	__u64 six;
+	__u64 seven;
+};
+
+/* Should fail because value struct has no rb_node
+ */
+struct {
+	__uint(type, BPF_MAP_TYPE_RBTREE);
+	__type(value, struct node_data_no_rb_node);
+} rbtree_fail_no_rb_node SEC(".maps");
+
+char _license[] SEC("license") = "GPL";
Signature · 1 line
2.30.2
#22 lore raw

RFC PATCH v2 16/18 selftests/bpf: Declarative lock definition test changes

In reply to Dave Marchevsky

This patch contains test changes corresponding to the functional changes in patch "bpf: Support declarative association of lock with rbtree map". It will be squashed with other test patches, leaving in this state for RFCv2 feedback.

---
 tools/testing/selftests/bpf/progs/rbtree_map.c       | 12 +++++++++---
 tools/testing/selftests/bpf/progs/rbtree_map_fail.c  |  9 ++++++++-
 .../selftests/bpf/progs/rbtree_map_load_fail.c       |  9 ++++++++-
 3 files changed, 25 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/progs/rbtree_map.c +9 -3
index 0cd467838f6e..50f29b9a5b82 100644
@@ -11,12 +11,18 @@ struct node_data {
 	__u32 two;
 };
 
+long calls;
+struct bpf_spin_lock rbtree_lock SEC(".bss.private");
+
 struct {
 	__uint(type, BPF_MAP_TYPE_RBTREE);
 	__type(value, struct node_data);
-} rbtree SEC(".maps");
-
-long calls;
+	__array(lock, struct bpf_spin_lock);
+} rbtree SEC(".maps") = {
+	.lock = {
+		[0] = &rbtree_lock,
+	},
+};
 
 static bool less(struct rb_node *a, const struct rb_node *b)
 {
tools/testing/selftests/bpf/progs/rbtree_map_fail.c +8 -1
index 287c8db080d8..ab4002a8211c 100644
@@ -11,10 +11,17 @@ struct node_data {
 	__u32 two;
 };
 
+struct bpf_spin_lock rbtree_lock SEC(".bss.private");
+
 struct {
 	__uint(type, BPF_MAP_TYPE_RBTREE);
 	__type(value, struct node_data);
-} rbtree SEC(".maps");
+	__array(lock, struct bpf_spin_lock);
+} rbtree SEC(".maps") = {
+	.lock = {
+		[0] = &rbtree_lock,
+	},
+};
 
 long calls;
 
tools/testing/selftests/bpf/progs/rbtree_map_load_fail.c +8 -1
index 036558eedd66..5578769efa2f 100644
@@ -14,11 +14,18 @@ struct node_data_no_rb_node {
 	__u64 seven;
 };
 
+struct bpf_spin_lock rbtree_lock SEC(".bss.private");
+
 /* Should fail because value struct has no rb_node
  */
 struct {
 	__uint(type, BPF_MAP_TYPE_RBTREE);
 	__type(value, struct node_data_no_rb_node);
-} rbtree_fail_no_rb_node SEC(".maps");
+	__array(lock, struct bpf_spin_lock);
+} rbtree_fail_no_rb_node SEC(".maps") = {
+	.lock = {
+		[0] = &rbtree_lock,
+	},
+};
 
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.30.2
#23 lore raw

RFC PATCH v2 17/18 selftests/bpf: Lock tracking test changes

In reply to Dave Marchevsky

This patch contains test changes corresponding to the functional changes in "bpf: Verifier tracking of rbtree_spin_lock held". It will be squashed with other test patches, leaving in this state for RFCv2 feedback.

iter section of rbtree_map.c prog is commented out because iter helpers will be tossed anyways.

---
 .../selftests/bpf/prog_tests/rbtree_map.c     |  2 +-
 .../testing/selftests/bpf/progs/rbtree_map.c  | 16 ++++++++-------
 .../selftests/bpf/progs/rbtree_map_fail.c     | 20 +++++++++----------
 3 files changed, 20 insertions(+), 18 deletions(-)
tools/testing/selftests/bpf/prog_tests/rbtree_map.c +1 -1
index 17cadcd05ee4..7634a2d93f0b 100644
@@ -17,7 +17,7 @@ static struct {
 	{"rb_node__field_store", "only read is supported"},
 	{"rb_node__alloc_no_add", "Unreleased reference id=2 alloc_insn=3"},
 	{"rb_node__two_alloc_one_add", "Unreleased reference id=2 alloc_insn=3"},
-	{"rb_node__remove_no_free", "Unreleased reference id=5 alloc_insn=28"},
+	{"rb_node__remove_no_free", "Unreleased reference id=6 alloc_insn=26"},
 	{"rb_tree__add_wrong_type", "rbtree: R2 is of type task_struct but node_data is expected"},
 	{"rb_tree__conditional_release_helper_usage",
 		"R2 type=ptr_cond_rel_ expected=ptr_"},
tools/testing/selftests/bpf/progs/rbtree_map.c +9 -7
index 50f29b9a5b82..957672cce82a 100644
@@ -65,6 +65,7 @@ int check_rbtree(void *ctx)
 	struct node_data *node, *found, *ret;
 	struct node_data popped;
 	struct node_data search;
+	struct bpf_spin_lock *lock;
 	__u32 search2;
 
 	node = bpf_rbtree_alloc_node(&rbtree, sizeof(struct node_data));
@@ -73,7 +74,8 @@ int check_rbtree(void *ctx)
 
 	node->one = calls;
 	node->two = 6;
-	bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree));
+	lock = &rbtree_lock;
+	bpf_rbtree_lock(lock);
 
 	ret = (struct node_data *)bpf_rbtree_add(&rbtree, node, less);
 	if (!ret) {
@@ -81,28 +83,28 @@ int check_rbtree(void *ctx)
 		goto unlock_ret;
 	}
 
-	bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_unlock(lock);
 
-	bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_lock(lock);
 
 	search.one = calls;
 	found = (struct node_data *)bpf_rbtree_find(&rbtree, &search, cmp);
 	if (!found)
 		goto unlock_ret;
 
-	int node_ct = 0;
+	/*int node_ct = 0;
 	struct node_data *iter = (struct node_data *)bpf_rbtree_first(&rbtree);
 
 	while (iter) {
 		node_ct++;
 		iter = (struct node_data *)bpf_rbtree_next(&rbtree, iter);
-	}
+	}*/
 
 	ret = (struct node_data *)bpf_rbtree_remove(&rbtree, found);
 	if (!ret)
 		goto unlock_ret;
 
-	bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_unlock(lock);
 
 	bpf_rbtree_free_node(&rbtree, ret);
 
@@ -110,7 +112,7 @@ int check_rbtree(void *ctx)
 	return 0;
 
 unlock_ret:
-	bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_unlock(&rbtree_lock);
 	return 0;
 }
 
tools/testing/selftests/bpf/progs/rbtree_map_fail.c +10 -10
index ab4002a8211c..779b85294f37 100644
@@ -61,7 +61,7 @@ int alloc_node__size_too_small(void *ctx)
 		return 0;
 	}
 
-	bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_lock(&rbtree_lock);
 	/* will never execute, alloc_node should fail */
 	node->one = 1;
 	ret = bpf_rbtree_add(&rbtree, node, less);
@@ -71,7 +71,7 @@ int alloc_node__size_too_small(void *ctx)
 	}
 
 unlock_ret:
-	bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_unlock(&rbtree_lock);
 	return 0;
 }
 
@@ -148,7 +148,7 @@ int rb_node__two_alloc_one_add(void *ctx)
 		return 0;
 	node->one = 42;
 
-	bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_lock(&rbtree_lock);
 
 	ret = bpf_rbtree_add(&rbtree, node, less);
 	if (!ret) {
@@ -157,7 +157,7 @@ int rb_node__two_alloc_one_add(void *ctx)
 	}
 
 unlock_ret:
-	bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_unlock(&rbtree_lock);
 	return 0;
 }
 
@@ -171,7 +171,7 @@ int rb_node__remove_no_free(void *ctx)
 		return 0;
 	node->one = 42;
 
-	bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_lock(&rbtree_lock);
 
 	ret = bpf_rbtree_add(&rbtree, node, less);
 	if (!ret) {
@@ -188,7 +188,7 @@ int rb_node__remove_no_free(void *ctx)
 	 */
 
 unlock_ret:
-	bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_unlock(&rbtree_lock);
 	return 0;
 }
 
@@ -202,14 +202,14 @@ int rb_tree__add_wrong_type(void *ctx)
 
 	task = bpf_get_current_task_btf();
 
-	bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_lock(&rbtree_lock);
 
 	ret = bpf_rbtree_add(&rbtree, task, less);
 	/* Verifier should fail at bpf_rbtree_add, so don't bother handling
 	 * failure.
 	 */
 
-	bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_unlock(&rbtree_lock);
 	return 0;
 }
 
@@ -223,7 +223,7 @@ int rb_tree__conditional_release_helper_usage(void *ctx)
 		return 0;
 	node->one = 42;
 
-	bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_lock(&rbtree_lock);
 
 	ret = bpf_rbtree_add(&rbtree, node, less);
 	/* Verifier should fail when trying to use CONDITIONAL_RELEASE
@@ -236,7 +236,7 @@ int rb_tree__conditional_release_helper_usage(void *ctx)
 	}
 
 unlock_ret:
-	bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree));
+	bpf_rbtree_unlock(&rbtree_lock);
 	return 0;
 }
 
Signature · 1 line
2.30.2
#24 lore raw

RFC PATCH v2 18/18 selftests/bpf: Rbtree static lock verification test changes

In reply to Dave Marchevsky

These are test chagnes corresponding to commit "bpf: Check rbtree lock held during verification". They should be squashed with other test changes, but are left unsquashed as part of RFCv2 to ease tossing them piecemeal if associated functionality is dropped.

---
 .../selftests/bpf/prog_tests/rbtree_map.c     | 32 +------------------
 1 file changed, 1 insertion(+), 31 deletions(-)
tools/testing/selftests/bpf/prog_tests/rbtree_map.c +1 -31
index 7634a2d93f0b..07bc2780854c 100644
@@ -19,6 +19,7 @@ static struct {
 	{"rb_node__two_alloc_one_add", "Unreleased reference id=2 alloc_insn=3"},
 	{"rb_node__remove_no_free", "Unreleased reference id=6 alloc_insn=26"},
 	{"rb_tree__add_wrong_type", "rbtree: R2 is of type task_struct but node_data is expected"},
+	{"add_node__no_lock", "lock associated with rbtree is not held"},
 	{"rb_tree__conditional_release_helper_usage",
 		"R2 type=ptr_cond_rel_ expected=ptr_"},
 };
@@ -96,37 +97,6 @@ void test_rbtree_map_alloc_node__size_too_small(void)
 	rbtree_map_fail__destroy(skel);
 }
 
-void test_rbtree_map_add_node__no_lock(void)
-{
-	struct rbtree_map_fail *skel;
-	struct bpf_program *prog;
-	struct bpf_link *link;
-	int err;
-
-	skel = rbtree_map_fail__open();
-	if (!ASSERT_OK_PTR(skel, "rbtree_map_fail__open"))
-		goto cleanup;
-
-	prog = skel->progs.add_node__no_lock;
-	bpf_program__set_autoload(prog, true);
-
-	err = rbtree_map_fail__load(skel);
-	if (!ASSERT_OK(err, "unexpected load fail"))
-		goto cleanup;
-
-	link = bpf_program__attach(skel->progs.add_node__no_lock);
-	if (!ASSERT_OK_PTR(link, "link"))
-		goto cleanup;
-
-	syscall(SYS_getpgid);
-
-	ASSERT_EQ(skel->bss->no_lock_add__fail, 1, "alloc_fail");
-
-	bpf_link__destroy(link);
-cleanup:
-	rbtree_map_fail__destroy(skel);
-}
-
 void test_rbtree_map_prog_load_fail(void)
 {
 	int i;
Signature · 1 line
2.30.2