[bpf-next,1/2] bpf: Add bits iterator

Commit Message

Yafang Shao Feb. 18, 2024, 11:48 a.m. UTC

Add three new kfuncs for the bits iterator:
- bpf_iter_bits_new
  Initialize a new bits iterator for a given memory area. Due to the
  limitation of bpf memalloc, the max number of bits that can be iterated
  over is limited to (4096 * 8).
- bpf_iter_bits_next
  Get the next bit in a bpf_iter_bits
- bpf_iter_bits_destroy
  Destroy a bpf_iter_bits

The bits iterator facilitates the iteration of the bits of a memory area,
such as cpumask. It can be used in any context and on any address.

Signed-off-by: Yafang Shao <[e-mail]>
---
 kernel/bpf/helpers.c | 100 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)

Comments

John Fastabend Feb. 26, 2024, 11:21 p.m. UTC | #1

Yafang Shao wrote:
> Add three new kfuncs for the bits iterator:
> - bpf_iter_bits_new
>   Initialize a new bits iterator for a given memory area. Due to the
>   limitation of bpf memalloc, the max number of bits that can be iterated
>   over is limited to (4096 * 8).
> - bpf_iter_bits_next
>   Get the next bit in a bpf_iter_bits
> - bpf_iter_bits_destroy
>   Destroy a bpf_iter_bits
> 
> The bits iterator facilitates the iteration of the bits of a memory area,
> such as cpumask. It can be used in any context and on any address.

Just curious as I see more and a more kfuncs. Did you try to implement
this with existing BPF? The main trick looks to be to get an implementation
of FIND_NEXT_BIT? Without trying seems doable with one of the bpf loop
iterators?

Also this requires a bpf_iter_bits_new across every iteration of the
BPF program or anytime we need to pick up the changes. Any reason
we can't just read the memory directly?

Thanks,
John

> 
> Signed-off-by: Yafang Shao <[e-mail]>
> ---
>  kernel/bpf/helpers.c | 100 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 100 insertions(+)
> 
> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> index 93edf730d288..052f63891834 100644
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c
> @@ -2542,6 +2542,103 @@ __bpf_kfunc void bpf_throw(u64 cookie)
>  	WARN(1, "A call to BPF exception callback should never return\n");
>  }
>  
> +struct bpf_iter_bits {
> +	__u64 __opaque[2];
> +} __aligned(8);
> +
> +struct bpf_iter_bits_kern {
> +	unsigned long *bits;
> +	u32 nr_bits;
> +	int bit;
> +} __aligned(8);
> +
> +/**
> + * bpf_iter_bits_new() - Initialize a new bits iterator for a given memory area
> + * @it: The new bpf_iter_bits to be created
> + * @unsafe_ptr__ign: A ponter pointing to a memory area to be iterated over
> + * @nr_bits: The number of bits to be iterated over. Due to the limitation of
> + * memalloc, it can't greater than (4096 * 8).
> + *
> + * This function initializes a new bpf_iter_bits structure for iterating over
> + * a memory area which is specified by the @unsafe_ptr__ign and @nr_bits. It
> + * copy the data of the memory area to the newly created bpf_iter_bits @it for
> + * subsequent iteration operations.
> + *
> + * On success, 0 is returned. On failure, ERR is returned.
> + */
> +__bpf_kfunc int
> +bpf_iter_bits_new(struct bpf_iter_bits *it, const void *unsafe_ptr__ign, u32 nr_bits)
> +{
> +	struct bpf_iter_bits_kern *kit = (void *)it;
> +	u32 size = BITS_TO_BYTES(nr_bits);
> +	int err;
> +
> +	BUILD_BUG_ON(sizeof(struct bpf_iter_bits_kern) != sizeof(struct bpf_iter_bits));
> +	BUILD_BUG_ON(__alignof__(struct bpf_iter_bits_kern) !=
> +		     __alignof__(struct bpf_iter_bits));
> +
> +	if (!unsafe_ptr__ign || !nr_bits) {
> +		kit->bits = NULL;
> +		return -EINVAL;
> +	}
> +
> +	kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
> +	if (!kit->bits)
> +		return -ENOMEM;
> +
> +	err = bpf_probe_read_kernel_common(kit->bits, size, unsafe_ptr__ign);

Specifically, this why can't we iterate over unsafe_ptr__ign?

> +	if (err) {
> +		bpf_mem_free(&bpf_global_ma, kit->bits);
> +		kit->bits = NULL;
> +		return err;
> +	}
> +
> +	kit->nr_bits = nr_bits;
> +	kit->bit = -1;
> +	return 0;
> +}
> +
> +/**
> + * bpf_iter_bits_next() - Get the next bit in a bpf_iter_bits
> + * @it: The bpf_iter_bits to be checked
> + *
> + * This function returns a pointer to a number representing the value of the
> + * next bit in the bits.
> + *
> + * If there are no further bit available, it returns NULL.
> + */
> +__bpf_kfunc int *bpf_iter_bits_next(struct bpf_iter_bits *it)
> +{
> +	struct bpf_iter_bits_kern *kit = (void *)it;
> +	const unsigned long *bits = kit->bits;
> +	int bit;
> +
> +	if (!bits)
> +		return NULL;
> +
> +	bit = find_next_bit(bits, kit->nr_bits, kit->bit + 1);

Seems like this should be ok over unsafe memory as long as find_next_bit
is bounded?

> +	if (bit >= kit->nr_bits)
> +		return NULL;
> +
> +	kit->bit = bit;
> +	return &kit->bit;
> +}


Thanks for working on this looks useful to me.

Alexei Starovoitov Feb. 27, 2024, 12:20 a.m. UTC | #2

On Mon, Feb 26, 2024 at 3:21 PM John Fastabend <[e-mail]> wrote:
> > +__bpf_kfunc int *bpf_iter_bits_next(struct bpf_iter_bits *it)
> > +{
> > +     struct bpf_iter_bits_kern *kit = (void *)it;
> > +     const unsigned long *bits = kit->bits;
> > +     int bit;
> > +
> > +     if (!bits)
> > +             return NULL;
> > +
> > +     bit = find_next_bit(bits, kit->nr_bits, kit->bit + 1);
>
> Seems like this should be ok over unsafe memory as long as find_next_bit
> is bounded?

Are you proposing to add find_next_bit() as a kfunc instead?

With the bpf_can_loop() proposal these two can be combined and
it will probably achieve the same result.
But imo this iterator is small enough to get in now and
delete later when there is a better way.
Ideally we'd need to add new instructions to operate with bits efficiently.

John Fastabend Feb. 27, 2024, 12:34 a.m. UTC | #3

Alexei Starovoitov wrote:
> On Mon, Feb 26, 2024 at 3:21 PM John Fastabend <[e-mail]> wrote:
> > > +__bpf_kfunc int *bpf_iter_bits_next(struct bpf_iter_bits *it)
> > > +{
> > > +     struct bpf_iter_bits_kern *kit = (void *)it;
> > > +     const unsigned long *bits = kit->bits;
> > > +     int bit;
> > > +
> > > +     if (!bits)
> > > +             return NULL;
> > > +
> > > +     bit = find_next_bit(bits, kit->nr_bits, kit->bit + 1);
> >
> > Seems like this should be ok over unsafe memory as long as find_next_bit
> > is bounded?
> 
> Are you proposing to add find_next_bit() as a kfunc instead?

I was suggesting you could likely implement find_next_bit() in
BPF directly no need for a kfunc.

> 
> With the bpf_can_loop() proposal these two can be combined and
> it will probably achieve the same result.
> But imo this iterator is small enough to get in now and
> delete later when there is a better way.

Agree its fine to go in as is IMO. Mostly just curious if anyone
tried to implement it in BPF.

> Ideally we'd need to add new instructions to operate with bits efficiently.

+1.

Patch

diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 93edf730d288..052f63891834 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -2542,6 +2542,103 @@  __bpf_kfunc void bpf_throw(u64 cookie)
 	WARN(1, "A call to BPF exception callback should never return\n");
 }
 
+struct bpf_iter_bits {
+	__u64 __opaque[2];
+} __aligned(8);
+
+struct bpf_iter_bits_kern {
+	unsigned long *bits;
+	u32 nr_bits;
+	int bit;
+} __aligned(8);
+
+/**
+ * bpf_iter_bits_new() - Initialize a new bits iterator for a given memory area
+ * @it: The new bpf_iter_bits to be created
+ * @unsafe_ptr__ign: A ponter pointing to a memory area to be iterated over
+ * @nr_bits: The number of bits to be iterated over. Due to the limitation of
+ * memalloc, it can't greater than (4096 * 8).
+ *
+ * This function initializes a new bpf_iter_bits structure for iterating over
+ * a memory area which is specified by the @unsafe_ptr__ign and @nr_bits. It
+ * copy the data of the memory area to the newly created bpf_iter_bits @it for
+ * subsequent iteration operations.
+ *
+ * On success, 0 is returned. On failure, ERR is returned.
+ */
+__bpf_kfunc int
+bpf_iter_bits_new(struct bpf_iter_bits *it, const void *unsafe_ptr__ign, u32 nr_bits)
+{
+	struct bpf_iter_bits_kern *kit = (void *)it;
+	u32 size = BITS_TO_BYTES(nr_bits);
+	int err;
+
+	BUILD_BUG_ON(sizeof(struct bpf_iter_bits_kern) != sizeof(struct bpf_iter_bits));
+	BUILD_BUG_ON(__alignof__(struct bpf_iter_bits_kern) !=
+		     __alignof__(struct bpf_iter_bits));
+
+	if (!unsafe_ptr__ign || !nr_bits) {
+		kit->bits = NULL;
+		return -EINVAL;
+	}
+
+	kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+	if (!kit->bits)
+		return -ENOMEM;
+
+	err = bpf_probe_read_kernel_common(kit->bits, size, unsafe_ptr__ign);
+	if (err) {
+		bpf_mem_free(&bpf_global_ma, kit->bits);
+		kit->bits = NULL;
+		return err;
+	}
+
+	kit->nr_bits = nr_bits;
+	kit->bit = -1;
+	return 0;
+}
+
+/**
+ * bpf_iter_bits_next() - Get the next bit in a bpf_iter_bits
+ * @it: The bpf_iter_bits to be checked
+ *
+ * This function returns a pointer to a number representing the value of the
+ * next bit in the bits.
+ *
+ * If there are no further bit available, it returns NULL.
+ */
+__bpf_kfunc int *bpf_iter_bits_next(struct bpf_iter_bits *it)
+{
+	struct bpf_iter_bits_kern *kit = (void *)it;
+	const unsigned long *bits = kit->bits;
+	int bit;
+
+	if (!bits)
+		return NULL;
+
+	bit = find_next_bit(bits, kit->nr_bits, kit->bit + 1);
+	if (bit >= kit->nr_bits)
+		return NULL;
+
+	kit->bit = bit;
+	return &kit->bit;
+}
+
+/**
+ * bpf_iter_bits_destroy() - Destroy a bpf_iter_bits
+ * @it: The bpf_iter_bits to be destroyed
+ *
+ * Destroy the resource associated with the bpf_iter_bits.
+ */
+__bpf_kfunc void bpf_iter_bits_destroy(struct bpf_iter_bits *it)
+{
+	struct bpf_iter_bits_kern *kit = (void *)it;
+
+	if (!kit->bits)
+		return;
+	bpf_mem_free(&bpf_global_ma, kit->bits);
+}
+
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(generic_btf_ids)
@@ -2618,6 +2715,9 @@  BTF_ID_FLAGS(func, bpf_dynptr_is_null)
 BTF_ID_FLAGS(func, bpf_dynptr_is_rdonly)
 BTF_ID_FLAGS(func, bpf_dynptr_size)
 BTF_ID_FLAGS(func, bpf_dynptr_clone)
+BTF_ID_FLAGS(func, bpf_iter_bits_new, KF_ITER_NEW)
+BTF_ID_FLAGS(func, bpf_iter_bits_next, KF_ITER_NEXT | KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_iter_bits_destroy, KF_ITER_DESTROY)
 BTF_KFUNCS_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {