Skip to contentSkip to conversation

BPF round-robin scheduler

PATCH Superseded Geliang Tang 2 participants 6 messages Apr 29, 2022 – Apr 30, 2022

Subsystems (5)

v9 of 15 Superseded Latest is v15 →

lore
Share & tools
lore
#0 lore raw

v9 cover BPF round-robin scheduler

v9:
- add subflows array in mptcp_sched_data
- deponds on: "BPF packet scheduler" series v17 + Squash to "mptcp: add struct mptcp_sched_ops v17".

v8:
- use struct mptcp_sched_data.
- deponds on: "BPF packet scheduler" series v14.

v7:
- rename retrans to reinject.
- drop last_snd setting.
- deponds on: "BPF packet scheduler" series v13.

v6:
- set call_me_again flag.
- deponds on: "BPF packet scheduler" series v12.

v5:
- update patch 2, use temporary storage instead.
- update patch 3, use new helpers.
- deponds on: "BPF packet scheduler" series v11.

v4:
- add retrans argment for get_subflow()

v3:
- add last_snd write access.
- keep msk->last_snd setting in get_subflow().
- deponds on: "BPF packet scheduler" series v10.

v2:
- merge the squash-to patch.
- implement bpf_mptcp_get_subflows helper, instead of bpf_mptcp_get_next_subflow.
- deponds on: "BPF packet scheduler v9".

This patchset implements round-robin scheduler using BPF. Address to some commends for the RFC version:

https://patchwork.kernel.org/project/mptcp/cover/[email protected]/

Geliang Tang (3):
mptcp: add subflows array in mptcp_sched_data
selftests: bpf: add bpf_rr scheduler
selftests: bpf: add bpf_rr test

 include/net/mptcp.h                           |  3 ++
 net/mptcp/protocol.h                          | 16 ++++++
 .../testing/selftests/bpf/bpf_mptcp_helpers.h |  8 +++
 .../testing/selftests/bpf/prog_tests/mptcp.c  | 37 ++++++++++++++
 .../selftests/bpf/progs/mptcp_bpf_rr.c        | 49 +++++++++++++++++++
 5 files changed, 113 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/mptcp_bpf_rr.c
Signature · 1 line
2.34.1
#1 lore raw

PATCH v9 1/3 mptcp: add subflows array in mptcp_sched_data

This patch adds a subflow pointers array in struct mptcp_sched_data. Set the array before invoking get_subflow(), then get it in get_subflow() in the BPF contexts.

---
 include/net/mptcp.h                             |  3 +++
 net/mptcp/protocol.h                            | 16 ++++++++++++++++
 tools/testing/selftests/bpf/bpf_mptcp_helpers.h |  3 +++
 3 files changed, 22 insertions(+)
include/net/mptcp.h +3 -0
index bea7608d72d3..1a48e31f3ac7 100644
@@ -96,10 +96,13 @@ struct mptcp_out_options {
 };
 
 #define MPTCP_SCHED_NAME_MAX	16
+#define MPTCP_SUBFLOWS_MAX	8
 
 struct mptcp_sched_data {
 	struct sock	*sock;
 	bool		call_again;
+	u8		subflows;
+	struct mptcp_subflow_context *array[MPTCP_SUBFLOWS_MAX];
 };
 
 struct mptcp_sched_ops {
net/mptcp/protocol.h +16 -0
index 0da2a91ad197..95a65582f1e8 100644
@@ -993,7 +993,9 @@ struct sock *mptcp_subflow_get_retrans(struct mptcp_sock *msk);
 
 static inline struct sock *mptcp_sched_get_send(struct mptcp_sock *msk)
 {
+	struct mptcp_subflow_context *subflow;
 	struct mptcp_sched_data data;
+	int i = 0;
 
 	sock_owned_by_me((struct sock *)msk);
 
@@ -1007,14 +1009,22 @@ static inline struct sock *mptcp_sched_get_send(struct mptcp_sock *msk)
 	if (!msk->sched)
 		return mptcp_subflow_get_send(msk);
 
+	mptcp_for_each_subflow(msk, subflow)
+		data.array[i++] = subflow;
+	data.subflows = i;
 	msk->sched->get_subflow(msk, false, &data);
+	for (i = 0; i < MPTCP_SUBFLOWS_MAX; i++)
+		data.array[i++] = NULL;
+	data.subflows = 0;
 
 	return data.sock;
 }
 
 static inline struct sock *mptcp_sched_get_retrans(struct mptcp_sock *msk)
 {
+	struct mptcp_subflow_context *subflow;
 	struct mptcp_sched_data data;
+	int i = 0;
 
 	sock_owned_by_me((const struct sock *)msk);
 
@@ -1025,7 +1035,13 @@ static inline struct sock *mptcp_sched_get_retrans(struct mptcp_sock *msk)
 	if (!msk->sched)
 		return mptcp_subflow_get_retrans(msk);
 
+	mptcp_for_each_subflow(msk, subflow)
+		data.array[i++] = subflow;
+	data.subflows = i;
 	msk->sched->get_subflow(msk, true, &data);
+	for (i = 0; i < MPTCP_SUBFLOWS_MAX; i++)
+		data.array[i++] = NULL;
+	data.subflows = 0;
 
 	return data.sock;
 }
tools/testing/selftests/bpf/bpf_mptcp_helpers.h +3 -0
index ee07caf978b3..1fe3d0a97429 100644
@@ -7,10 +7,13 @@
 #include "bpf_tcp_helpers.h"
 
 #define MPTCP_SCHED_NAME_MAX	16
+#define MPTCP_SUBFLOWS_MAX	8
 
 struct mptcp_sched_data {
 	struct sock	*sock;
 	bool		call_again;
+	__u8		subflows;
+	struct mptcp_subflow_context *array[MPTCP_SUBFLOWS_MAX];
 };
 
 struct mptcp_sched_ops {
Signature · 1 line
2.34.1
#3 lore raw

PATCH v9 2/3 selftests: bpf: add bpf_rr scheduler

In reply to Geliang Tang

This patch implements the round-robin BPF MPTCP scheduler, named bpf_rr, which always picks the next available subflow to send data. If no such next subflow available, picks the first one.

---
 .../testing/selftests/bpf/bpf_mptcp_helpers.h |  5 ++
 .../selftests/bpf/progs/mptcp_bpf_rr.c        | 49 +++++++++++++++++++
 2 files changed, 54 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/mptcp_bpf_rr.c
tools/testing/selftests/bpf/bpf_mptcp_helpers.h +5 -0
index 1fe3d0a97429..8ce5b1603962 100644
@@ -37,4 +37,9 @@ struct mptcp_sock {
 	char		ca_name[TCP_CA_NAME_MAX];
 } __attribute__((preserve_access_index));
 
+struct mptcp_subflow_context {
+	__u32	token;
+	struct	sock *tcp_sock;	    /* tcp sk backpointer */
+} __attribute__((preserve_access_index));
+
 #endif
tools/testing/selftests/bpf/progs/mptcp_bpf_rr.c new file +49 -0

49 lines not on this page · raw message

Signature · 1 line
2.34.1
#5 lore raw

PATCH v9 3/3 selftests: bpf: add bpf_rr test

In reply to Geliang Tang

This patch adds the round-robin BPF MPTCP scheduler test. Use sysctl to set net.mptcp.scheduler to use this sched. Add a veth net device to simulate the multiple addresses case. Use 'ip mptcp endpoint' command to add this new endpoint to PM netlink.

---
 .../testing/selftests/bpf/prog_tests/mptcp.c  | 37 +++++++++++++++++++
 1 file changed, 37 insertions(+)
tools/testing/selftests/bpf/prog_tests/mptcp.c +37 -0
index 44484a63e62a..fb4a4b37e818 100644
@@ -5,6 +5,7 @@
 #include "cgroup_helpers.h"
 #include "network_helpers.h"
 #include "mptcp_bpf_first.skel.h"
+#include "mptcp_bpf_rr.skel.h"
 
 #ifndef TCP_CA_NAME_MAX
 #define TCP_CA_NAME_MAX	16
@@ -361,10 +362,46 @@ static void test_first(void)
 	mptcp_bpf_first__destroy(first_skel);
 }
 
+static void test_rr(void)
+{
+	struct mptcp_bpf_rr *rr_skel;
+	int server_fd, client_fd;
+	struct bpf_link *link;
+
+	rr_skel = mptcp_bpf_rr__open_and_load();
+	if (CHECK(!rr_skel, "bpf_rr__open_and_load", "failed\n"))
+		return;
+
+	link = bpf_map__attach_struct_ops(rr_skel->maps.rr);
+	if (!ASSERT_OK_PTR(link, "bpf_map__attach_struct_ops")) {
+		mptcp_bpf_rr__destroy(rr_skel);
+		return;
+	}
+
+	system("ip link add veth1 type veth; \
+		ip addr add 10.0.1.1/24 dev veth1; \
+		ip link set veth1 up");
+	system("ip mptcp endpoint add 10.0.1.1 subflow");
+	system("sysctl -q net.mptcp.scheduler=bpf_rr");
+	server_fd = start_mptcp_server(AF_INET, NULL, 0, 0);
+	client_fd = connect_to_mptcp_fd(server_fd, 0);
+
+	send_data(server_fd, client_fd);
+
+	close(client_fd);
+	close(server_fd);
+	system("ip mptcp endpoint flush");
+	system("ip link del veth1");
+	bpf_link__destroy(link);
+	mptcp_bpf_rr__destroy(rr_skel);
+}
+
 void test_mptcp(void)
 {
 	if (test__start_subtest("base"))
 		test_base();
 	if (test__start_subtest("first"))
 		test_first();
+	if (test__start_subtest("rr"))
+		test_rr();
 }
Signature · 1 line
2.34.1
#4 lore raw

Re: [PATCH mptcp-next v9 2/3] selftests: bpf: add bpf_rr scheduler

In reply to Geliang Tang
Quoted 50 lines · Geliang Tang

This patch implements the round-robin BPF MPTCP scheduler, named bpf_rr, which always picks the next available subflow to send data. If no such next subflow available, picks the first one.

---
.../testing/selftests/bpf/bpf_mptcp_helpers.h | 5 ++
.../selftests/bpf/progs/mptcp_bpf_rr.c | 49 +++++++++++++++++++

2 files changed, 54 insertions(+)

create mode 100644 tools/testing/selftests/bpf/progs/mptcp_bpf_rr.c

tools/testing/selftests/bpf/bpf_mptcp_helpers.h +5 -0
index 1fe3d0a97429..8ce5b1603962 100644
@@ -37,4 +37,9 @@ struct mptcp_sock {
 	char		ca_name[TCP_CA_NAME_MAX];
 } __attribute__((preserve_access_index));
 
+struct mptcp_subflow_context {
+	__u32	token;
+	struct	sock *tcp_sock;	    /* tcp sk backpointer */
+} __attribute__((preserve_access_index));
+
 #endif
tools/testing/selftests/bpf/progs/mptcp_bpf_rr.c new file +19 -0
new file mode 100644
index 000000000000..2f31de4cfc84
@@ -0,0 +1,49 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2022, SUSE. */
+
+#include <linux/bpf.h>
+#include <linux/stddef.h>
+#include <linux/tcp.h>
+#include "bpf_mptcp_helpers.h"
+
+char _license[] SEC("license") = "GPL";
+
+SEC("struct_ops/mptcp_sched_rr_init")
+void BPF_PROG(mptcp_sched_rr_init, struct mptcp_sock *msk)
+{
+}
+
+SEC("struct_ops/mptcp_sched_rr_release")
+void BPF_PROG(mptcp_sched_rr_release, struct mptcp_sock *msk)
+{
+}

tools/testing/selftests/bpf/progs/mptcp_bpf_rr.c line 29

Quoted 10 lines
tools/testing/selftests/bpf/progs/mptcp_bpf_rr.c new file +10 -0
+
+void BPF_STRUCT_OPS(bpf_rr_get_subflow, struct mptcp_sock *msk,
+		    bool reinject, struct mptcp_sched_data *data)
+{
+	struct mptcp_subflow_context *subflow;
+	struct sock *ssk = msk->first;
+
+	for (int i = 0; i < MPTCP_SUBFLOWS_MAX; i++) {
+		if (i >= data->subflows)
+			break;

Is the extra 'if' statement required by the BPF verifier? If this is not allowed:

for (int i = 0; i < MPTCP_SUBFLOWS_MAX; i++)

is this?

for (int i = 0; i < MPTCP_SUBFLOWS_MAX && i < data->subflows; i++)

Quoted 25 lines
tools/testing/selftests/bpf/progs/mptcp_bpf_rr.c new file +20 -0
+
+		subflow = data->array[i];
+		if (subflow->tcp_sock != msk->last_snd) {
+			ssk = subflow->tcp_sock;
+			break;
+		}
+	}
+
+	msk->last_snd = ssk;
+	data->sock = ssk;
+	data->call_again = 0;
+}
+
+SEC(".struct_ops")
+struct mptcp_sched_ops rr = {
+	.init		= (void *)mptcp_sched_rr_init,
+	.release	= (void *)mptcp_sched_rr_release,
+	.get_subflow	= (void *)bpf_rr_get_subflow,
+	.name		= "bpf_rr",
+};
Signature · 1 line
2.34.1

--
Mat Martineau
Intel

#2 lore raw

Re: [PATCH mptcp-next v9 1/3] mptcp: add subflows array in mptcp_sched_data

In reply to Geliang Tang
Quoted 44 lines · Geliang Tang

This patch adds a subflow pointers array in struct mptcp_sched_data. Set the array before invoking get_subflow(), then get it in get_subflow() in the BPF contexts.

---

include/net/mptcp.h                             |  3 +++
net/mptcp/protocol.h                            | 16 ++++++++++++++++
tools/testing/selftests/bpf/bpf_mptcp_helpers.h |  3 +++
3 files changed, 22 insertions(+)
include/net/mptcp.h +3 -0
index bea7608d72d3..1a48e31f3ac7 100644
@@ -96,10 +96,13 @@ struct mptcp_out_options {
 };
 
 #define MPTCP_SCHED_NAME_MAX	16
+#define MPTCP_SUBFLOWS_MAX	8
 
 struct mptcp_sched_data {
 	struct sock	*sock;
 	bool		call_again;
+	u8		subflows;
+	struct mptcp_subflow_context *array[MPTCP_SUBFLOWS_MAX];
 };
 
 struct mptcp_sched_ops {
net/mptcp/protocol.h +2 -0
index 0da2a91ad197..95a65582f1e8 100644
@@ -993,7 +993,9 @@ struct sock *mptcp_subflow_get_retrans(struct mptcp_sock *msk);
 
 static inline struct sock *mptcp_sched_get_send(struct mptcp_sock *msk)
 {
+	struct mptcp_subflow_context *subflow;
 	struct mptcp_sched_data data;
+	int i = 0;
 
 	sock_owned_by_me((struct sock *)msk);
 

net/mptcp/protocol.h static inline struct sock *mptcp_sched_get_send(struct mptcp_sock *msk) · line 1014

Quoted 6 lines
net/mptcp/protocol.h +3 -0
@@ -1007,14 +1009,22 @@ static inline struct sock *mptcp_sched_get_send(struct mptcp_sock *msk)
 	if (!msk->sched)
 		return mptcp_subflow_get_send(msk);
 
+	mptcp_for_each_subflow(msk, subflow)
+		data.array[i++] = subflow;
+	data.subflows = i;

As I mentioned in a previous patch, a helper function here would be good.

net/mptcp/protocol.h static inline struct sock *mptcp_sched_get_send(struct mptcp_sock *msk) · line 1018

Quoted 4 lines
net/mptcp/protocol.h +3 -0
 	msk->sched->get_subflow(msk, false, &data);
+	for (i = 0; i < MPTCP_SUBFLOWS_MAX; i++)
+		data.array[i++] = NULL;
+	data.subflows = 0;

Why zero out this data on the stack if BPF does not have write access to it?

- Mat

Quoted 49 lines
net/mptcp/protocol.h +8 -0
 	return data.sock;
 }
 
 static inline struct sock *mptcp_sched_get_retrans(struct mptcp_sock *msk)
 {
+	struct mptcp_subflow_context *subflow;
 	struct mptcp_sched_data data;
+	int i = 0;
 
 	sock_owned_by_me((const struct sock *)msk);
 
@@ -1025,7 +1035,13 @@ static inline struct sock *mptcp_sched_get_retrans(struct mptcp_sock *msk)
 	if (!msk->sched)
 		return mptcp_subflow_get_retrans(msk);
 
+	mptcp_for_each_subflow(msk, subflow)
+		data.array[i++] = subflow;
+	data.subflows = i;
 	msk->sched->get_subflow(msk, true, &data);
+	for (i = 0; i < MPTCP_SUBFLOWS_MAX; i++)
+		data.array[i++] = NULL;
+	data.subflows = 0;
 
 	return data.sock;
 }
tools/testing/selftests/bpf/bpf_mptcp_helpers.h +3 -0
index ee07caf978b3..1fe3d0a97429 100644
@@ -7,10 +7,13 @@
 #include "bpf_tcp_helpers.h"
 
 #define MPTCP_SCHED_NAME_MAX	16
+#define MPTCP_SUBFLOWS_MAX	8
 
 struct mptcp_sched_data {
 	struct sock	*sock;
 	bool		call_again;
+	__u8		subflows;
+	struct mptcp_subflow_context *array[MPTCP_SUBFLOWS_MAX];
 };
 
 struct mptcp_sched_ops {
Signature · 1 line
2.34.1

--
Mat Martineau
Intel