[PATCH bpf-next v2] libbpf: handle producer position overflow

[PATCH bpf-next v2] libbpf: handle producer position overflow

[Andrew Werner]

Before this patch, the producer position could overflow `unsigned
long`, in which case libbpf would forever stop processing new writes to
the ringbuf. This patch addresses that bug by avoiding ordered
comparison between the consumer and producer position. If the consumer
position is greater than the producer position, the assumption is that
the producer has overflowed.

A more defensive check could be to ensure that the delta is within
the allowed range, but such defensive checks are neither present in
the kernel side code nor in libbpf. The overflow that this patch
handles can occur while the producer and consumer follow a correct
protocol.

A selftest was written to demonstrate the bug, and indeed this patch
allows the test to continue to make progress past the overflow.
However, the author was unable to create a testing environment on a
32-bit machine, and the test requires substantial memory and over 4
hours to hit the overflow point on a 64-bit machine. Thus, the test
is not included in this patch because of the impracticality of running
it.

Additionally, this patch adds commentary around a separate point to note
that the modular arithmetic is valid in the face of overflows, as that
fact may not be obvious to future readers.

v1->v2:
 - Fixed comment grammar.
 - Properly formatted subject line.

Reference:
[v1]: https://lore.kernel.org/bpf/20230724132404.1280848-1-awerner32@gmail.com/T/#u

Signed-off-by: Andrew Werner <awerner32@gmail.com>
---
 tools/lib/bpf/ringbuf.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

diff --git a/tools/lib/bpf/ringbuf.c b/tools/lib/bpf/ringbuf.c
index 02199364db13..2055f3099843 100644
--- a/tools/lib/bpf/ringbuf.c
+++ b/tools/lib/bpf/ringbuf.c
@@ -237,7 +237,11 @@ static int64_t ringbuf_process_ring(struct ring *r)
 	do {
 		got_new_data = false;
 		prod_pos = smp_load_acquire(r->producer_pos);
-		while (cons_pos < prod_pos) {
+
+		/* Avoid signed comparisons between the positions; the producer
+		 * position can overflow before the consumer position.
+		 */
+		while (cons_pos != prod_pos) {
 			len_ptr = r->data + (cons_pos & r->mask);
 			len = smp_load_acquire(len_ptr);
 
@@ -498,6 +502,11 @@ void *user_ring_buffer__reserve(struct user_ring_buffer *rb, __u32 size)
 	prod_pos = smp_load_acquire(rb->producer_pos);
 
 	max_size = rb->mask + 1;
+
+	/* Note that this formulation is valid in the face of overflow of
+	 * prod_pos so long as the delta between prod_pos and cons_pos is
+	 * no greater than max_size.
+	 */
 	avail_size = max_size - (prod_pos - cons_pos);
 	/* Round up total size to a multiple of 8. */
 	total_size = (size + BPF_RINGBUF_HDR_SZ + 7) / 8 * 8;
-- 
2.39.2

Re: [PATCH bpf-next v2] libbpf: handle producer position overflow

[Hou Tao]

On 7/24/2023 9:25 PM, Andrew Werner wrote:
> Before this patch, the producer position could overflow `unsigned
> long`, in which case libbpf would forever stop processing new writes to
> the ringbuf. This patch addresses that bug by avoiding ordered
> comparison between the consumer and producer position. If the consumer
> position is greater than the producer position, the assumption is that
> the producer has overflowed.
>
> A more defensive check could be to ensure that the delta is within
> the allowed range, but such defensive checks are neither present in
> the kernel side code nor in libbpf. The overflow that this patch
> handles can occur while the producer and consumer follow a correct
> protocol.
>
> A selftest was written to demonstrate the bug, and indeed this patch
> allows the test to continue to make progress past the overflow.
> However, the author was unable to create a testing environment on a
> 32-bit machine, and the test requires substantial memory and over 4
> hours to hit the overflow point on a 64-bit machine. Thus, the test
> is not included in this patch because of the impracticality of running
> it.
>
> Additionally, this patch adds commentary around a separate point to note
> that the modular arithmetic is valid in the face of overflows, as that
> fact may not be obvious to future readers.
>
> v1->v2:
>  - Fixed comment grammar.
>  - Properly formatted subject line.
>
> Reference:
> [v1]: https://lore.kernel.org/bpf/20230724132404.1280848-1-awerner32@gmail.com/T/#u
>
> Signed-off-by: Andrew Werner <awerner32@gmail.com>

Acked-by: Hou Tao <houtao1@huawei.com>

Re: [PATCH bpf-next v2] libbpf: handle producer position overflow

[Jiri Olsa]

On Mon, Jul 24, 2023 at 09:25:45AM -0400, Andrew Werner wrote:
> Before this patch, the producer position could overflow `unsigned
> long`, in which case libbpf would forever stop processing new writes to
> the ringbuf. This patch addresses that bug by avoiding ordered
> comparison between the consumer and producer position. If the consumer
> position is greater than the producer position, the assumption is that
> the producer has overflowed.
> 
> A more defensive check could be to ensure that the delta is within
> the allowed range, but such defensive checks are neither present in
> the kernel side code nor in libbpf. The overflow that this patch
> handles can occur while the producer and consumer follow a correct
> protocol.
> 
> A selftest was written to demonstrate the bug, and indeed this patch
> allows the test to continue to make progress past the overflow.
> However, the author was unable to create a testing environment on a
> 32-bit machine, and the test requires substantial memory and over 4
> hours to hit the overflow point on a 64-bit machine. Thus, the test
> is not included in this patch because of the impracticality of running
> it.
> 
> Additionally, this patch adds commentary around a separate point to note
> that the modular arithmetic is valid in the face of overflows, as that
> fact may not be obvious to future readers.
> 
> v1->v2:
>  - Fixed comment grammar.
>  - Properly formatted subject line.
> 
> Reference:
> [v1]: https://lore.kernel.org/bpf/20230724132404.1280848-1-awerner32@gmail.com/T/#u
> 
> Signed-off-by: Andrew Werner <awerner32@gmail.com>
> ---
>  tools/lib/bpf/ringbuf.c | 11 ++++++++++-
>  1 file changed, 10 insertions(+), 1 deletion(-)
> 
> diff --git a/tools/lib/bpf/ringbuf.c b/tools/lib/bpf/ringbuf.c
> index 02199364db13..2055f3099843 100644
> --- a/tools/lib/bpf/ringbuf.c
> +++ b/tools/lib/bpf/ringbuf.c
> @@ -237,7 +237,11 @@ static int64_t ringbuf_process_ring(struct ring *r)
>  	do {
>  		got_new_data = false;
>  		prod_pos = smp_load_acquire(r->producer_pos);
> -		while (cons_pos < prod_pos) {
> +
> +		/* Avoid signed comparisons between the positions; the producer
> +		 * position can overflow before the consumer position.
> +		 */
> +		while (cons_pos != prod_pos) {
>  			len_ptr = r->data + (cons_pos & r->mask);
>  			len = smp_load_acquire(len_ptr);
>  
> @@ -498,6 +502,11 @@ void *user_ring_buffer__reserve(struct user_ring_buffer *rb, __u32 size)
>  	prod_pos = smp_load_acquire(rb->producer_pos);
>  
>  	max_size = rb->mask + 1;
> +
> +	/* Note that this formulation is valid in the face of overflow of
> +	 * prod_pos so long as the delta between prod_pos and cons_pos is
> +	 * no greater than max_size.
> +	 */
>  	avail_size = max_size - (prod_pos - cons_pos);

hi,
the above hunk handles the case for 'prod_pos < cons_pos',

but it looks like we assume 'cons_pos < prod_pos' in above calculation,
should we check on that?

jirka


>  	/* Round up total size to a multiple of 8. */
>  	total_size = (size + BPF_RINGBUF_HDR_SZ + 7) / 8 * 8;
> -- 
> 2.39.2
> 
> 

Re: [PATCH bpf-next v2] libbpf: handle producer position overflow

[Andrew Werner]

On Thu, Jul 27, 2023 at 4:33 AM Jiri Olsa <olsajiri@gmail.com> wrote:
>
> On Mon, Jul 24, 2023 at 09:25:45AM -0400, Andrew Werner wrote:
> > Before this patch, the producer position could overflow `unsigned
> > long`, in which case libbpf would forever stop processing new writes to
> > the ringbuf. This patch addresses that bug by avoiding ordered
> > comparison between the consumer and producer position. If the consumer
> > position is greater than the producer position, the assumption is that
> > the producer has overflowed.
> >
> > A more defensive check could be to ensure that the delta is within
> > the allowed range, but such defensive checks are neither present in
> > the kernel side code nor in libbpf. The overflow that this patch
> > handles can occur while the producer and consumer follow a correct
> > protocol.
> >
> > A selftest was written to demonstrate the bug, and indeed this patch
> > allows the test to continue to make progress past the overflow.
> > However, the author was unable to create a testing environment on a
> > 32-bit machine, and the test requires substantial memory and over 4
> > hours to hit the overflow point on a 64-bit machine. Thus, the test
> > is not included in this patch because of the impracticality of running
> > it.
> >
> > Additionally, this patch adds commentary around a separate point to note
> > that the modular arithmetic is valid in the face of overflows, as that
> > fact may not be obvious to future readers.
> >
> > v1->v2:
> >  - Fixed comment grammar.
> >  - Properly formatted subject line.
> >
> > Reference:
> > [v1]: https://lore.kernel.org/bpf/20230724132404.1280848-1-awerner32@gmail.com/T/#u
> >
> > Signed-off-by: Andrew Werner <awerner32@gmail.com>
> > ---
> >  tools/lib/bpf/ringbuf.c | 11 ++++++++++-
> >  1 file changed, 10 insertions(+), 1 deletion(-)
> >
> > diff --git a/tools/lib/bpf/ringbuf.c b/tools/lib/bpf/ringbuf.c
> > index 02199364db13..2055f3099843 100644
> > --- a/tools/lib/bpf/ringbuf.c
> > +++ b/tools/lib/bpf/ringbuf.c
> > @@ -237,7 +237,11 @@ static int64_t ringbuf_process_ring(struct ring *r)
> >       do {
> >               got_new_data = false;
> >               prod_pos = smp_load_acquire(r->producer_pos);
> > -             while (cons_pos < prod_pos) {
> > +
> > +             /* Avoid signed comparisons between the positions; the producer
> > +              * position can overflow before the consumer position.
> > +              */
> > +             while (cons_pos != prod_pos) {
> >                       len_ptr = r->data + (cons_pos & r->mask);
> >                       len = smp_load_acquire(len_ptr);
> >
> > @@ -498,6 +502,11 @@ void *user_ring_buffer__reserve(struct user_ring_buffer *rb, __u32 size)
> >       prod_pos = smp_load_acquire(rb->producer_pos);
> >
> >       max_size = rb->mask + 1;
> > +
> > +     /* Note that this formulation is valid in the face of overflow of
> > +      * prod_pos so long as the delta between prod_pos and cons_pos is
> > +      * no greater than max_size.
> > +      */
> >       avail_size = max_size - (prod_pos - cons_pos);
>
> hi,
> the above hunk handles the case for 'prod_pos < cons_pos',
>
> but it looks like we assume 'cons_pos < prod_pos' in above calculation,
> should we check on that?
>
> jirka

The code there does work (perhaps surprisingly) even if the cons_pos is
less than the prod_pos, so long as that delta is no greater than max_size.
I added the commentary there because I too found it to be unintuitive.

Consider the following program. It will print "delta: 20".

```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main() {
    unsigned long cons_pos = ULONG_MAX - 9;
    unsigned long prod_pos = 10;
    printf("delta: %lu\n", prod_pos - cons_pos);
    return 0;
}
```

-Andrew

>
>
> >       /* Round up total size to a multiple of 8. */
> >       total_size = (size + BPF_RINGBUF_HDR_SZ + 7) / 8 * 8;
> > --
> > 2.39.2
> >
> >

Re: [PATCH bpf-next v2] libbpf: handle producer position overflow

[Alexei Starovoitov]

On Thu, Jul 27, 2023 at 7:48 AM Andrew Werner <andrew@dataexmachina.dev> wrote:
>
> On Thu, Jul 27, 2023 at 4:33 AM Jiri Olsa <olsajiri@gmail.com> wrote:
> >
> > On Mon, Jul 24, 2023 at 09:25:45AM -0400, Andrew Werner wrote:
> > > Before this patch, the producer position could overflow `unsigned
> > > long`, in which case libbpf would forever stop processing new writes to
> > > the ringbuf. This patch addresses that bug by avoiding ordered
> > > comparison between the consumer and producer position. If the consumer
> > > position is greater than the producer position, the assumption is that
> > > the producer has overflowed.
> > >
> > > A more defensive check could be to ensure that the delta is within
> > > the allowed range, but such defensive checks are neither present in
> > > the kernel side code nor in libbpf. The overflow that this patch
> > > handles can occur while the producer and consumer follow a correct
> > > protocol.
> > >
> > > A selftest was written to demonstrate the bug, and indeed this patch
> > > allows the test to continue to make progress past the overflow.
> > > However, the author was unable to create a testing environment on a
> > > 32-bit machine, and the test requires substantial memory and over 4
> > > hours to hit the overflow point on a 64-bit machine. Thus, the test
> > > is not included in this patch because of the impracticality of running
> > > it.

Are you saying on a 64-bit host you were able to overflow 64-bit integer
in 4 hours?
Interesting.
Please share the test anyway. As a patch or github link. Anything works.

> > >
> > > Additionally, this patch adds commentary around a separate point to note
> > > that the modular arithmetic is valid in the face of overflows, as that
> > > fact may not be obvious to future readers.
> > >
> > > v1->v2:
> > >  - Fixed comment grammar.
> > >  - Properly formatted subject line.
> > >
> > > Reference:
> > > [v1]: https://lore.kernel.org/bpf/20230724132404.1280848-1-awerner32@gmail.com/T/#u
> > >
> > > Signed-off-by: Andrew Werner <awerner32@gmail.com>
> > > ---
> > >  tools/lib/bpf/ringbuf.c | 11 ++++++++++-
> > >  1 file changed, 10 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/tools/lib/bpf/ringbuf.c b/tools/lib/bpf/ringbuf.c
> > > index 02199364db13..2055f3099843 100644
> > > --- a/tools/lib/bpf/ringbuf.c
> > > +++ b/tools/lib/bpf/ringbuf.c
> > > @@ -237,7 +237,11 @@ static int64_t ringbuf_process_ring(struct ring *r)
> > >       do {
> > >               got_new_data = false;
> > >               prod_pos = smp_load_acquire(r->producer_pos);
> > > -             while (cons_pos < prod_pos) {
> > > +
> > > +             /* Avoid signed comparisons between the positions; the producer
> > > +              * position can overflow before the consumer position.
> > > +              */
> > > +             while (cons_pos != prod_pos) {
> > >                       len_ptr = r->data + (cons_pos & r->mask);
> > >                       len = smp_load_acquire(len_ptr);
> > >
> > > @@ -498,6 +502,11 @@ void *user_ring_buffer__reserve(struct user_ring_buffer *rb, __u32 size)
> > >       prod_pos = smp_load_acquire(rb->producer_pos);
> > >
> > >       max_size = rb->mask + 1;
> > > +
> > > +     /* Note that this formulation is valid in the face of overflow of
> > > +      * prod_pos so long as the delta between prod_pos and cons_pos is
> > > +      * no greater than max_size.
> > > +      */
> > >       avail_size = max_size - (prod_pos - cons_pos);
> >
> > hi,
> > the above hunk handles the case for 'prod_pos < cons_pos',
> >
> > but it looks like we assume 'cons_pos < prod_pos' in above calculation,
> > should we check on that?
> >
> > jirka
>
> The code there does work (perhaps surprisingly) even if the cons_pos is
> less than the prod_pos, so long as that delta is no greater than max_size.
> I added the commentary there because I too found it to be unintuitive.
>
> Consider the following program. It will print "delta: 20".
>
> ```c
> #include <stdio.h>
> #include <stdlib.h>
> #include <limits.h>
>
> int main() {
>     unsigned long cons_pos = ULONG_MAX - 9;
>     unsigned long prod_pos = 10;
>     printf("delta: %lu\n", prod_pos - cons_pos);
>     return 0;
> }
> ```
>
> -Andrew
>
> >
> >
> > >       /* Round up total size to a multiple of 8. */
> > >       total_size = (size + BPF_RINGBUF_HDR_SZ + 7) / 8 * 8;
> > > --
> > > 2.39.2
> > >
> > >
>

Re: [PATCH bpf-next v2] libbpf: handle producer position overflow

[Andrew Werner]

On Wed, Aug 2, 2023 at 11:41 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Thu, Jul 27, 2023 at 7:48 AM Andrew Werner <andrew@dataexmachina.dev> wrote:
> >
> > On Thu, Jul 27, 2023 at 4:33 AM Jiri Olsa <olsajiri@gmail.com> wrote:
> > >
> > > On Mon, Jul 24, 2023 at 09:25:45AM -0400, Andrew Werner wrote:
> > > > Before this patch, the producer position could overflow `unsigned
> > > > long`, in which case libbpf would forever stop processing new writes to
> > > > the ringbuf. This patch addresses that bug by avoiding ordered
> > > > comparison between the consumer and producer position. If the consumer
> > > > position is greater than the producer position, the assumption is that
> > > > the producer has overflowed.
> > > >
> > > > A more defensive check could be to ensure that the delta is within
> > > > the allowed range, but such defensive checks are neither present in
> > > > the kernel side code nor in libbpf. The overflow that this patch
> > > > handles can occur while the producer and consumer follow a correct
> > > > protocol.
> > > >
> > > > A selftest was written to demonstrate the bug, and indeed this patch
> > > > allows the test to continue to make progress past the overflow.
> > > > However, the author was unable to create a testing environment on a
> > > > 32-bit machine, and the test requires substantial memory and over 4
> > > > hours to hit the overflow point on a 64-bit machine. Thus, the test
> > > > is not included in this patch because of the impracticality of running
> > > > it.
>
> Are you saying on a 64-bit host you were able to overflow 64-bit integer
> in 4 hours?
> Interesting.
> Please share the test anyway. As a patch or github link. Anything works.

Here's a link to the test: https://github.com/ajwerner/bpf/commit/85e1240e7713

>
> > > >
> > > > Additionally, this patch adds commentary around a separate point to note
> > > > that the modular arithmetic is valid in the face of overflows, as that
> > > > fact may not be obvious to future readers.
> > > >
> > > > v1->v2:
> > > >  - Fixed comment grammar.
> > > >  - Properly formatted subject line.
> > > >
> > > > Reference:
> > > > [v1]: https://lore.kernel.org/bpf/20230724132404.1280848-1-awerner32@gmail.com/T/#u
> > > >
> > > > Signed-off-by: Andrew Werner <awerner32@gmail.com>
> > > > ---
> > > >  tools/lib/bpf/ringbuf.c | 11 ++++++++++-
> > > >  1 file changed, 10 insertions(+), 1 deletion(-)
> > > >
> > > > diff --git a/tools/lib/bpf/ringbuf.c b/tools/lib/bpf/ringbuf.c
> > > > index 02199364db13..2055f3099843 100644
> > > > --- a/tools/lib/bpf/ringbuf.c
> > > > +++ b/tools/lib/bpf/ringbuf.c
> > > > @@ -237,7 +237,11 @@ static int64_t ringbuf_process_ring(struct ring *r)
> > > >       do {
> > > >               got_new_data = false;
> > > >               prod_pos = smp_load_acquire(r->producer_pos);
> > > > -             while (cons_pos < prod_pos) {
> > > > +
> > > > +             /* Avoid signed comparisons between the positions; the producer
> > > > +              * position can overflow before the consumer position.
> > > > +              */
> > > > +             while (cons_pos != prod_pos) {
> > > >                       len_ptr = r->data + (cons_pos & r->mask);
> > > >                       len = smp_load_acquire(len_ptr);
> > > >
> > > > @@ -498,6 +502,11 @@ void *user_ring_buffer__reserve(struct user_ring_buffer *rb, __u32 size)
> > > >       prod_pos = smp_load_acquire(rb->producer_pos);
> > > >
> > > >       max_size = rb->mask + 1;
> > > > +
> > > > +     /* Note that this formulation is valid in the face of overflow of
> > > > +      * prod_pos so long as the delta between prod_pos and cons_pos is
> > > > +      * no greater than max_size.
> > > > +      */
> > > >       avail_size = max_size - (prod_pos - cons_pos);
> > >
> > > hi,
> > > the above hunk handles the case for 'prod_pos < cons_pos',
> > >
> > > but it looks like we assume 'cons_pos < prod_pos' in above calculation,
> > > should we check on that?
> > >
> > > jirka
> >
> > The code there does work (perhaps surprisingly) even if the cons_pos is
> > less than the prod_pos, so long as that delta is no greater than max_size.
> > I added the commentary there because I too found it to be unintuitive.
> >
> > Consider the following program. It will print "delta: 20".
> >
> > ```c
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <limits.h>
> >
> > int main() {
> >     unsigned long cons_pos = ULONG_MAX - 9;
> >     unsigned long prod_pos = 10;
> >     printf("delta: %lu\n", prod_pos - cons_pos);
> >     return 0;
> > }
> > ```
> >
> > -Andrew
> >
> > >
> > >
> > > >       /* Round up total size to a multiple of 8. */
> > > >       total_size = (size + BPF_RINGBUF_HDR_SZ + 7) / 8 * 8;
> > > > --
> > > > 2.39.2
> > > >
> > > >
> >