bpf: Fix backward progress bug in bpf_iter_udp
Subsystems (6)
Martin KaFai Lau
reviewerv3 cover bpf: Fix backward progress bug in bpf_iter_udp
From: Martin KaFai Lau <[email protected]>
This patch set fixes an issue in bpf_iter_udp that makes backward progress and prevents the user space process from finishing. There is a test at the end to reproduce the bug.
Please see individual patches for details.
v3:
- Fixed the iter_fd check and local_port check in the
patch 3 selftest. (Yonghong)
- Moved jhash2 to test_jhash.h in the patch 3. (Yonghong)
- Added explanation in the bucket selection in the patch 3. (Yonghong)
v2:
- Added patch 1 to fix another bug that goes back to the previous bucket
- Simplify the fix in patch 2 to always reset iter->offset to 0
- Add a test case to close all udp_sk in a bucket while in the middle of the iteration.
Martin KaFai Lau (3):
bpf: iter_udp: Retry with a larger batch size without going back to
the previous bucket
bpf: Avoid iter->offset making backward progress in bpf_iter_udp selftests/bpf: Test udp and tcp iter batching
net/ipv4/udp.c | 22 ++- .../bpf/prog_tests/sock_iter_batch.c | 135 ++++++++++++++++++ .../selftests/bpf/progs/bpf_tracing_net.h | 3 + .../selftests/bpf/progs/sock_iter_batch.c | 91 ++++++++++++ .../testing/selftests/bpf/progs/test_jhash.h | 31 ++++ 5 files changed, 270 insertions(+), 12 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/sock_iter_batch.c create mode 100644 tools/testing/selftests/bpf/progs/sock_iter_batch.c
Signature · 1 line
2.34.1
Martin KaFai Lau
reviewerPATCH v3 1/3 bpf: iter_udp: Retry with a larger batch size without going back to the previous bucket
From: Martin KaFai Lau <[email protected]>
The current logic is to use a default size 16 to batch the whole bucket. If it is too small, it will retry with a larger batch size.
The current code accidentally does a state->bucket-- before retrying. This goes back to retry with the previous bucket which has already been done. This patch fixed it.
It is hard to create a selftest. I added a WARN_ON(state->bucket < 0), forced a particular port to be hashed to the first bucket, created >16 sockets, and observed the for-loop went back
to the "-1" bucket.
--- net/ipv4/udp.c | 1 - 1 file changed, 1 deletion(-)
net/ipv4/udp.c +0 -1
@@ -3213,7 +3213,6 @@ static struct sock *bpf_iter_udp_batch(struct seq_file *seq)/* After allocating a larger batch, retry one more time to grab * the whole bucket. */ - state->bucket--; goto again; } done:
Signature · 1 line
2.34.1
Re: [PATCH v3 bpf 1/3] bpf: iter_udp: Retry with a larger batch size without going back to the previous bucket
Quoted 18 lines · Martin KaFai Lau
From: Martin KaFai Lau <[email protected]>
The current logic is to use a default size 16 to batch the whole bucket. If it is too small, it will retry with a larger batch size.
The current code accidentally does a state->bucket-- before retrying. This goes back to retry with the previous bucket which has already been done. This patch fixed it.
It is hard to create a selftest. I added a
WARN_ON(state->bucket < 0), forced a particular port to be hashed to the first bucket, created >16 sockets, and observed the for-loop went back
to the "-1" bucket.
Quoted 4 lines
Cc Aditi Ghag <[email protected]>Fixes c96dac8d369f ("bpf: udp: Implement batching for sockets iterator")Acked-by Yonghong Song <[email protected]>Signed-off-by Martin KaFai Lau <[email protected]>
LGTM!
Quoted 19 lines
---
net/ipv4/udp.c| 1 -1 file changed, 1 deletion(-)net/ipv4/udp.c +0
-1@@ -3213,7 +3213,6 @@ static struct sock *bpf_iter_udp_batch(struct seq_file *seq)/* After allocating a larger batch, retry one more time to grab * the whole bucket. */ - state->bucket--; goto again; }done:
Signature · 1 line
2.34.1
Martin KaFai Lau
reviewerPATCH v3 2/3 bpf: Avoid iter->offset making backward progress in bpf_iter_udp
In reply to Martin KaFai LauFrom: Martin KaFai Lau <[email protected]>
There is a bug in the bpf_iter_udp_batch() function that stops the userspace from making forward progress.
The case that triggers the bug is the userspace passed in a very small read buffer. When the bpf prog does bpf_seq_printf, the userspace read buffer is not enough to capture the whole bucket.
When the read buffer is not large enough, the kernel will remember the offset of the bucket in iter->offset such that the next userspace read() can continue from where it left off.
The kernel will skip the number (== "iter->offset") of sockets in the next read(). However, the code directly decrements the "--iter->offset". This is incorrect because the next read() may not consume the whole bucket either and then the next-next read() will start from offset 0. The net effect is the userspace will keep reading from the beginning of a bucket and the process will never finish. "iter->offset" must always go forward until the whole bucket is consumed.
This patch fixes it by using a local variable "resume_offset" and "resume_bucket". "iter->offset" is always reset to 0 before it may be used. "iter->offset" will be advanced to the "resume_offset" when it continues from the "resume_bucket" (i.e. "state->bucket == resume_bucket"). This brings it closer to the bpf_iter_tcp's offset handling which does not suffer the same bug.
--- net/ipv4/udp.c | 21 ++++++++++----------- 1 file changed, 10 insertions(+), 11 deletions(-)
net/ipv4/udp.c +10 -11
@@ -3137,16 +3137,18 @@ static struct sock *bpf_iter_udp_batch(struct seq_file *seq)struct bpf_udp_iter_state *iter = seq->private;struct udp_iter_state *state = &iter->state;struct net *net =seq_file_net (seq); +int resume_bucket, resume_offset;struct udp_table *udptable;unsigned int batch_sks =0 ;bool resized = false;struct sock *sk; + resume_bucket = state->bucket; + resume_offset = iter->offset; +/* The current batch is done, so advance the bucket. */ -if (iter->st_bucket_done) { +if (iter->st_bucket_done) state->bucket++; - iter->offset =0 ; - } udptable =udp_get_table_seq (seq, net);
@@ -3166,19 +3168,19 @@ static struct sock *bpf_iter_udp_batch(struct seq_file *seq)for (; state->bucket <= udptable->mask; state->bucket++) {struct udp_hslot *hslot2 = &udptable->hash2[state->bucket]; -if (hlist_empty (&hslot2->head)) { - iter->offset =0 ; +if (hlist_empty (&hslot2->head))continue ; - } + iter->offset =0 ;spin_lock_bh (&hslot2->lock);udp_portaddr_for_each_entry (sk, &hslot2->head) {if (seq_sk_match (seq, sk)) {/* Resume from the last iterated socket at the * offset in the bucket before iterator was stopped. */ -if (iter->offset) { - --iter->offset; +if (state->bucket == resume_bucket && + iter->offset < resume_offset) { + ++iter->offset;continue ; }if (iter->end_sk < iter->max_sk) {
@@ -3192,9 +3194,6 @@ static struct sock *bpf_iter_udp_batch(struct seq_file *seq)if (iter->end_sk)break ; - -/* Reset the current bucket's offset before moving to the next bucket. */ - iter->offset =0 ; }/* All done: no batch made. */
Signature · 1 line
2.34.1
Re: [PATCH v3 bpf 2/3] bpf: Avoid iter->offset making backward progress in bpf_iter_udp
Quoted 34 lines · Martin KaFai Lau
From: Martin KaFai Lau <[email protected]>
There is a bug in the
bpf_iter_udp_batch()function that stops the userspace from making forward progress.The case that triggers the bug is the userspace passed in a very small read buffer. When the bpf prog does
bpf_seq_printf, the userspace read buffer is not enough to capture the whole bucket.When the read buffer is not large enough, the kernel will remember the offset of the bucket in
iter->offsetsuch that the next userspaceread()can continue from where it left off.The kernel will skip the number (== "
iter->offset") of sockets in the nextread(). However, the code directly decrements the "--iter->offset". This is incorrect because the nextread()may not consume the whole bucket either and then the next-nextread()will start from offset 0. The net effect is the userspace will keep reading from the beginning of a bucket and the process will never finish. "iter->offset" must always go forward until the whole bucket is consumed.This patch fixes it by using a local variable "
resume_offset" and "resume_bucket". "iter->offset" is always reset to 0 before it may be used. "iter->offset" will be advanced to the "resume_offset" when it continues from the "resume_bucket" (i.e. "state->bucket==resume_bucket"). This brings it closer to the bpf_iter_tcp's offset handling which does not suffer the same bug.
Quoted 4 lines
Cc Aditi Ghag <[email protected]>Fixes c96dac8d369f ("bpf: udp: Implement batching for sockets iterator")Acked-by Yonghong Song <[email protected]>Signed-off-by Martin KaFai Lau <[email protected]>
Thanks!
Quoted 41 lines
---
net/ipv4/udp.c| 21 ++++++++++-----------1 file changed, 10 insertions(+), 11 deletions(-)net/ipv4/udp.c +7
-6@@ -3137,16 +3137,18 @@ static struct sock *bpf_iter_udp_batch(struct seq_file *seq)struct bpf_udp_iter_state *iter = seq->private;struct udp_iter_state *state = &iter->state;struct net *net =seq_file_net (seq); +int resume_bucket, resume_offset;struct udp_table *udptable;unsigned int batch_sks =0 ;bool resized = false;struct sock *sk; + resume_bucket = state->bucket; + resume_offset = iter->offset; +/* The current batch is done, so advance the bucket. */ -if (iter->st_bucket_done) { +if (iter->st_bucket_done) state->bucket++; - iter->offset =0 ; - } udptable =udp_get_table_seq (seq, net);@@ -3166,19 +3168,19 @@ static struct sock *bpf_iter_udp_batch(struct seq_file *seq)for (; state->bucket <= udptable->mask; state->bucket++) {struct udp_hslot *hslot2 = &udptable->hash2[state->bucket]; -if (hlist_empty (&hslot2->head)) { - iter->offset =0 ; +if (hlist_empty (&hslot2->head))continue ; - } + iter->offset =0 ;
net/ipv4/udp.c static struct sock *bpf_iter_udp_batch(struct seq_file *seq) · line 3182
Quoted 10 lines
net/ipv4/udp.c +2
-2spin_lock_bh (&hslot2->lock);udp_portaddr_for_each_entry (sk, &hslot2->head) {if (seq_sk_match (seq, sk)) {/* Resume from the last iterated socket at the * offset in the bucket before iterator was stopped. */ -if (iter->offset) { - --iter->offset; +if (state->bucket == resume_bucket && + iter->offset < resume_offset) {
I like this invariant of ensuring that the batching and resume operations are performed for the same bucket under consideration.
Quoted 17 lines
net/ipv4/udp.c +1
-3+ ++iter->offset;continue ; }if (iter->end_sk < iter->max_sk) {@@ -3192,9 +3194,6 @@ static struct sock *bpf_iter_udp_batch(struct seq_file *seq)if (iter->end_sk)break ; - -/* Reset the current bucket's offset before moving to the next bucket. */ - iter->offset =0 ; }/* All done: no batch made. */ Signature · 1 line
2.34.1
Martin KaFai Lau
reviewerPATCH v3 3/3 selftests/bpf: Test udp and tcp iter batching
In reply to Martin KaFai LauFrom: Martin KaFai Lau <[email protected]>
The patch adds a test to exercise the bpf_iter_udp batching logic. It specifically tests the case that there are multiple so_reuseport udp_sk in a bucket of the udp_table.
The test creates two sets of so_reuseport sockets and each set on a different port. Meaning there will be two buckets in the udp_table.
The test does the following:
1. read() 3 out of 4 sockets in the first bucket.
2. close() all sockets in the first bucket. This
will ensure the current bucket's offset in
the kernel does not affect the read() of the
following bucket.
3. read() all 4 sockets in the second bucket.
The test also reads one udp_sk at a time from the bpf_iter_udp prog. The true case in "do_test(..., bool onebyone)". This is the buggy case that the previous patch fixed.
It also tests the "false" case in "do_test(..., bool onebyone)", meaning the userspace reads the whole bucket. There is no bug in this case but adding this test also while
at it.
Considering the way to have multiple tcp_sk in the same bucket is similar (by using so_reuseport), this patch also tests the bpf_iter_tcp even though the bpf_iter_tcp batching logic works correctly.
Both IP v4 and v6 are exercising the same bpf_iter batching code path, so only v6 is tested.
--- .../bpf/prog_tests/sock_iter_batch.c | 135 ++++++++++++++++++ .../selftests/bpf/progs/bpf_tracing_net.h | 3 + .../selftests/bpf/progs/sock_iter_batch.c | 91 ++++++++++++ .../testing/selftests/bpf/progs/test_jhash.h | 31 ++++ 4 files changed, 260 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/sock_iter_batch.c create mode 100644 tools/testing/selftests/bpf/progs/sock_iter_batch.c
tools/testing/selftests/bpf/prog_tests/sock_iter_batch.c new file +135 -0
@@ -0,0 +1,135 @@ +// SPDX-License-Identifier: GPL-2.0 +// Copyright (c) 2024 Meta + +#include <test_progs.h> +#include "network_helpers.h" +#include "sock_iter_batch.skel.h" + +#define TEST_NS "sock_iter_batch_netns" + +static const int nr_soreuse =4 ; + +static void do_test (int sock_type,bool onebyone) +{ +int err, i, nread, to_read, total_read, iter_fd =-1 ; +int first_idx, second_idx, indices[nr_soreuse]; +struct bpf_link *link =NULL ; +struct sock_iter_batch *skel; +int *fds[2 ] = {}; + + skel =sock_iter_batch__open (); +if (!ASSERT_OK_PTR (skel,"sock_iter_batch__open" )) +return ; + +/* Prepare 2 buckets of sockets in the kernel hashtable */ +for (i =0 ; i <ARRAY_SIZE (fds); i++) { +int local_port; + + fds[i] =start_reuseport_server (AF_INET6 , sock_type,"::1" ,0 ,0 , + nr_soreuse); +if (!ASSERT_OK_PTR (fds[i],"start_reuseport_server" )) + goto done; + local_port =get_socket_local_port (*fds[i]); +if (!ASSERT_GE (local_port,0 ,"get_socket_local_port" )) + goto done; + skel->rodata->ports[i] =ntohs (local_port); + } + + err =sock_iter_batch__load (skel); +if (!ASSERT_OK (err,"sock_iter_batch__load" )) + goto done; + + link =bpf_program__attach_iter (sock_type ==SOCK_STREAM ? + skel->progs.iter_tcp_soreuse : + skel->progs.iter_udp_soreuse, +NULL ); +if (!ASSERT_OK_PTR (link,"bpf_program__attach_iter" )) + goto done; + + iter_fd =bpf_iter_create (bpf_link__fd (link)); +if (!ASSERT_GE (iter_fd,0 ,"bpf_iter_create" )) + goto done; + +/* Test reading a bucket (either from fds[0] or fds[1]). +* Only read "nr_soreuse - 1" number of sockets +* from a bucket and leave one socket out from +* that bucket on purpose. +*/ + to_read = (nr_soreuse -1 ) *sizeof (*indices); + total_read =0 ; + first_idx =-1 ; +do { + nread =read (iter_fd, indices, onebyone ?sizeof (*indices) : to_read); +if (nread <=0 || nread %sizeof (*indices)) +break ; + total_read += nread; + +if (first_idx ==-1 ) + first_idx = indices[0 ]; +for (i =0 ; i < nread /sizeof (*indices); i++) +ASSERT_EQ (indices[i], first_idx,"first_idx" ); + }while (total_read < to_read); +ASSERT_EQ (nread, onebyone ?sizeof (*indices) : to_read,"nread" ); +ASSERT_EQ (total_read, to_read,"total_read" ); + +free_fds (fds[first_idx], nr_soreuse); + fds[first_idx] =NULL ; + +/* Read the "whole" second bucket */ + to_read = nr_soreuse *sizeof (*indices); + total_read =0 ; + second_idx = !first_idx; +do { + nread =read (iter_fd, indices, onebyone ?sizeof (*indices) : to_read); +if (nread <=0 || nread %sizeof (*indices)) +break ; + total_read += nread; + +for (i =0 ; i < nread /sizeof (*indices); i++) +ASSERT_EQ (indices[i], second_idx,"second_idx" ); + }while (total_read <= to_read); +ASSERT_EQ (nread,0 ,"nread" ); +/* Both so_reuseport ports should be in different buckets, so +* total_read must equal to the expected to_read. +* +* For a very unlikely case, both ports collide at the same bucket, +* the bucket offset (i.e. 3) will be skipped and it cannot +* expect the to_read number of bytes. +*/ +if (skel->bss->bucket[0 ] != skel->bss->bucket[1 ]) +ASSERT_EQ (total_read, to_read,"total_read" ); + +done: +for (i =0 ; i <ARRAY_SIZE (fds); i++) +free_fds (fds[i], nr_soreuse); +if (iter_fd <0 ) +close (iter_fd); +bpf_link__destroy (link); +sock_iter_batch__destroy (skel); +} + +void test_sock_iter_batch (void ) +{ +struct nstoken *nstoken =NULL ; + +SYS_NOFAIL ("ip netns del " TEST_NS " &> /dev/null" ); +SYS (done,"ip netns add %s" ,TEST_NS ); +SYS (done,"ip -net %s link set dev lo up" ,TEST_NS ); + + nstoken =open_netns (TEST_NS ); +if (!ASSERT_OK_PTR (nstoken,"open_netns" )) + goto done; + +if (test__start_subtest ("tcp" )) { +do_test (SOCK_STREAM , true); +do_test (SOCK_STREAM , false); + } +if (test__start_subtest ("udp" )) { +do_test (SOCK_DGRAM , true); +do_test (SOCK_DGRAM , false); + } +close_netns (nstoken); + +done: +SYS_NOFAIL ("ip netns del " TEST_NS " &> /dev/null" ); +}
tools/testing/selftests/bpf/progs/bpf_tracing_net.h +3 -0
@@ -72,6 +72,8 @@#define inet_rcv_saddr sk.__sk_common.skc_rcv_saddr#define inet_dport sk.__sk_common.skc_dport +#define udp_portaddr_hash inet.sk.__sk_common.skc_u16hashes[1] +#define ir_loc_addr req.__req_common.skc_rcv_saddr#define ir_num req.__req_common.skc_num#define ir_rmt_addr req.__req_common.skc_daddr
@@ -85,6 +87,7 @@#define sk_rmem_alloc sk_backlog.rmem_alloc#define sk_refcnt __sk_common.skc_refcnt#define sk_state __sk_common.skc_state +#define sk_net __sk_common.skc_net#define sk_v6_daddr __sk_common.skc_v6_daddr#define sk_v6_rcv_saddr __sk_common.skc_v6_rcv_saddr#define sk_flags __sk_common.skc_flags
tools/testing/selftests/bpf/progs/sock_iter_batch.c new file +91 -0
91 lines not on this page · raw message
tools/testing/selftests/bpf/progs/test_jhash.h +31 -0
@@ -69,3 +69,34 @@ u32 jhash(const void *key, u32 length, u32 initval)return c; } + +static __always_inline u32 jhash2(const u32 *k, u32 length, u32 initval) +{ +u32 a, b, c; + +/* Set up the internal state */ + a = b = c =JHASH_INITVAL + (length<<2 ) + initval; + +/* Handle most of the key */ +while (length >3 ) { + a += k[0 ]; + b += k[1 ]; + c += k[2 ]; +__jhash_mix (a, b, c); + length -=3 ; + k +=3 ; + } + +/* Handle the last 3 u32's */ +switch (length) { +case 3 : c += k[2 ]; +case 2 : b += k[1 ]; +case 1 : a += k[0 ]; +__jhash_final (a, b, c); +break ; +case 0 :/* Nothing left to add */ +break ; + } + +return c; +}
Signature · 1 line
2.34.1
This series was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:
Quoted 9 lines · On Fri, 12 Jan 2024 11:05:27 -0800 you wrote:
From: Martin KaFai Lau <[email protected]>
This patch set fixes an issue in
bpf_iter_udpthat makes backward progress and prevents the user space process from finishing. There is a test at the end to reproduce the bug.Please see individual patches for details.
[...]
Here is the summary with links:
- [v3,bpf,1/3] bpf: iter_udp: Retry with a larger batch size without going back to the previous bucket
https://git.kernel.org/bpf/bpf/c/19ca0823f6ea - [v3,bpf,2/3] bpf: Avoid iter->offset making backward progress in bpf_iter_udp https://git.kernel.org/bpf/bpf/c/2242fd537fab - [v3,bpf,3/3] selftests/bpf: Test udp and tcp iter batching https://git.kernel.org/bpf/bpf/c/dbd7db7787ba
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html