1// SPDX-License-Identifier: GPL-2.0
  2/* Copyright (c) 2019 Facebook */
  3
  4/* WARNING: This implemenation is not necessarily the same
  5 * as the tcp_dctcp.c.  The purpose is mainly for testing
  6 * the kernel BPF logic.
  7 */
  8
  9#include "bpf_tracing_net.h"
 10#include <bpf/bpf_helpers.h>
 11#include <bpf/bpf_tracing.h>
 12
 13#ifndef EBUSY
 14#define EBUSY 16
 15#endif
 16#define min(a, b) ((a) < (b) ? (a) : (b))
 17#define max(a, b) ((a) > (b) ? (a) : (b))
 18#define min_not_zero(x, y) ({			\
 19	typeof(x) __x = (x);			\
 20	typeof(y) __y = (y);			\
 21	__x == 0 ? __y : ((__y == 0) ? __x : min(__x, __y)); })
 22static bool before(__u32 seq1, __u32 seq2)
 23{
 24	return (__s32)(seq1-seq2) < 0;
 25}
 26
 27char _license[] SEC("license") = "GPL";
 28
 29volatile const char fallback_cc[TCP_CA_NAME_MAX];
 30const char bpf_dctcp[] = "bpf_dctcp";
 31const char tcp_cdg[] = "cdg";
 32char cc_res[TCP_CA_NAME_MAX];
 33int tcp_cdg_res = 0;
 34int stg_result = 0;
 35int ebusy_cnt = 0;
 36
 37struct {
 38	__uint(type, BPF_MAP_TYPE_SK_STORAGE);
 39	__uint(map_flags, BPF_F_NO_PREALLOC);
 40	__type(key, int);
 41	__type(value, int);
 42} sk_stg_map SEC(".maps");
 43
 44#define DCTCP_MAX_ALPHA	1024U
 45
 46struct bpf_dctcp {
 47	__u32 old_delivered;
 48	__u32 old_delivered_ce;
 49	__u32 prior_rcv_nxt;
 50	__u32 dctcp_alpha;
 51	__u32 next_seq;
 52	__u32 ce_state;
 53	__u32 loss_cwnd;
 54};
 55
 56static unsigned int dctcp_shift_g = 4; /* g = 1/2^4 */
 57static unsigned int dctcp_alpha_on_init = DCTCP_MAX_ALPHA;
 58
 59static void dctcp_reset(const struct tcp_sock *tp, struct bpf_dctcp *ca)
 60{
 61	ca->next_seq = tp->snd_nxt;
 62
 63	ca->old_delivered = tp->delivered;
 64	ca->old_delivered_ce = tp->delivered_ce;
 65}
 66
 67SEC("struct_ops")
 68void BPF_PROG(bpf_dctcp_init, struct sock *sk)
 69{
 70	const struct tcp_sock *tp = tcp_sk(sk);
 71	struct bpf_dctcp *ca = inet_csk_ca(sk);
 72	int *stg;
 73
 74	if (!(tp->ecn_flags & TCP_ECN_OK) && fallback_cc[0]) {
 75		/* Switch to fallback */
 76		if (bpf_setsockopt(sk, SOL_TCP, TCP_CONGESTION,
 77				   (void *)fallback_cc, sizeof(fallback_cc)) == -EBUSY)
 78			ebusy_cnt++;
 79
 80		/* Switch back to myself and the recurred bpf_dctcp_init()
 81		 * will get -EBUSY for all bpf_setsockopt(TCP_CONGESTION),
 82		 * except the last "cdg" one.
 83		 */
 84		if (bpf_setsockopt(sk, SOL_TCP, TCP_CONGESTION,
 85				   (void *)bpf_dctcp, sizeof(bpf_dctcp)) == -EBUSY)
 86			ebusy_cnt++;
 87
 88		/* Switch back to fallback */
 89		if (bpf_setsockopt(sk, SOL_TCP, TCP_CONGESTION,
 90				   (void *)fallback_cc, sizeof(fallback_cc)) == -EBUSY)
 91			ebusy_cnt++;
 92
 93		/* Expecting -ENOTSUPP for tcp_cdg_res */
 94		tcp_cdg_res = bpf_setsockopt(sk, SOL_TCP, TCP_CONGESTION,
 95					     (void *)tcp_cdg, sizeof(tcp_cdg));
 96		bpf_getsockopt(sk, SOL_TCP, TCP_CONGESTION,
 97			       (void *)cc_res, sizeof(cc_res));
 98		return;
 99	}
100
101	ca->prior_rcv_nxt = tp->rcv_nxt;
102	ca->dctcp_alpha = min(dctcp_alpha_on_init, DCTCP_MAX_ALPHA);
103	ca->loss_cwnd = 0;
104	ca->ce_state = 0;
105
106	stg = bpf_sk_storage_get(&sk_stg_map, (void *)tp, NULL, 0);
107	if (stg) {
108		stg_result = *stg;
109		bpf_sk_storage_delete(&sk_stg_map, (void *)tp);
110	}
111	dctcp_reset(tp, ca);
112}
113
114SEC("struct_ops")
115__u32 BPF_PROG(bpf_dctcp_ssthresh, struct sock *sk)
116{
117	struct bpf_dctcp *ca = inet_csk_ca(sk);
118	struct tcp_sock *tp = tcp_sk(sk);
119
120	ca->loss_cwnd = tp->snd_cwnd;
121	return max(tp->snd_cwnd - ((tp->snd_cwnd * ca->dctcp_alpha) >> 11U), 2U);
122}
123
124SEC("struct_ops")
125void BPF_PROG(bpf_dctcp_update_alpha, struct sock *sk, __u32 flags)
126{
127	const struct tcp_sock *tp = tcp_sk(sk);
128	struct bpf_dctcp *ca = inet_csk_ca(sk);
129
130	/* Expired RTT */
131	if (!before(tp->snd_una, ca->next_seq)) {
132		__u32 delivered_ce = tp->delivered_ce - ca->old_delivered_ce;
133		__u32 alpha = ca->dctcp_alpha;
134
135		/* alpha = (1 - g) * alpha + g * F */
136
137		alpha -= min_not_zero(alpha, alpha >> dctcp_shift_g);
138		if (delivered_ce) {
139			__u32 delivered = tp->delivered - ca->old_delivered;
140
141			/* If dctcp_shift_g == 1, a 32bit value would overflow
142			 * after 8 M packets.
143			 */
144			delivered_ce <<= (10 - dctcp_shift_g);
145			delivered_ce /= max(1U, delivered);
146
147			alpha = min(alpha + delivered_ce, DCTCP_MAX_ALPHA);
148		}
149		ca->dctcp_alpha = alpha;
150		dctcp_reset(tp, ca);
151	}
152}
153
154static void dctcp_react_to_loss(struct sock *sk)
155{
156	struct bpf_dctcp *ca = inet_csk_ca(sk);
157	struct tcp_sock *tp = tcp_sk(sk);
158
159	ca->loss_cwnd = tp->snd_cwnd;
160	tp->snd_ssthresh = max(tp->snd_cwnd >> 1U, 2U);
161}
162
163SEC("struct_ops")
164void BPF_PROG(bpf_dctcp_state, struct sock *sk, __u8 new_state)
165{
166	if (new_state == TCP_CA_Recovery &&
167	    new_state != BPF_CORE_READ_BITFIELD(inet_csk(sk), icsk_ca_state))
168		dctcp_react_to_loss(sk);
169	/* We handle RTO in bpf_dctcp_cwnd_event to ensure that we perform only
170	 * one loss-adjustment per RTT.
171	 */
172}
173
174static void dctcp_ece_ack_cwr(struct sock *sk, __u32 ce_state)
175{
176	struct tcp_sock *tp = tcp_sk(sk);
177
178	if (ce_state == 1)
179		tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
180	else
181		tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR;
182}
183
184/* Minimal DCTP CE state machine:
185 *
186 * S:	0 <- last pkt was non-CE
187 *	1 <- last pkt was CE
188 */
189static void dctcp_ece_ack_update(struct sock *sk, enum tcp_ca_event evt,
190				 __u32 *prior_rcv_nxt, __u32 *ce_state)
191{
192	__u32 new_ce_state = (evt == CA_EVENT_ECN_IS_CE) ? 1 : 0;
193
194	if (*ce_state != new_ce_state) {
195		/* CE state has changed, force an immediate ACK to
196		 * reflect the new CE state. If an ACK was delayed,
197		 * send that first to reflect the prior CE state.
198		 */
199		if (inet_csk(sk)->icsk_ack.pending & ICSK_ACK_TIMER) {
200			dctcp_ece_ack_cwr(sk, *ce_state);
201			bpf_tcp_send_ack(sk, *prior_rcv_nxt);
202		}
203		inet_csk(sk)->icsk_ack.pending |= ICSK_ACK_NOW;
204	}
205	*prior_rcv_nxt = tcp_sk(sk)->rcv_nxt;
206	*ce_state = new_ce_state;
207	dctcp_ece_ack_cwr(sk, new_ce_state);
208}
209
210SEC("struct_ops")
211void BPF_PROG(bpf_dctcp_cwnd_event, struct sock *sk, enum tcp_ca_event ev)
212{
213	struct bpf_dctcp *ca = inet_csk_ca(sk);
214
215	switch (ev) {
216	case CA_EVENT_ECN_IS_CE:
217	case CA_EVENT_ECN_NO_CE:
218		dctcp_ece_ack_update(sk, ev, &ca->prior_rcv_nxt, &ca->ce_state);
219		break;
220	case CA_EVENT_LOSS:
221		dctcp_react_to_loss(sk);
222		break;
223	default:
224		/* Don't care for the rest. */
225		break;
226	}
227}
228
229SEC("struct_ops")
230__u32 BPF_PROG(bpf_dctcp_cwnd_undo, struct sock *sk)
231{
232	const struct bpf_dctcp *ca = inet_csk_ca(sk);
233
234	return max(tcp_sk(sk)->snd_cwnd, ca->loss_cwnd);
235}
236
237extern void tcp_reno_cong_avoid(struct sock *sk, __u32 ack, __u32 acked) __ksym;
238
239SEC("struct_ops")
240void BPF_PROG(bpf_dctcp_cong_avoid, struct sock *sk, __u32 ack, __u32 acked)
241{
242	tcp_reno_cong_avoid(sk, ack, acked);
243}
244
245SEC(".struct_ops")
246struct tcp_congestion_ops dctcp_nouse = {
247	.init		= (void *)bpf_dctcp_init,
248	.set_state	= (void *)bpf_dctcp_state,
249	.flags		= TCP_CONG_NEEDS_ECN,
250	.name		= "bpf_dctcp_nouse",
251};
252
253SEC(".struct_ops")
254struct tcp_congestion_ops dctcp = {
255	.init		= (void *)bpf_dctcp_init,
256	.in_ack_event   = (void *)bpf_dctcp_update_alpha,
257	.cwnd_event	= (void *)bpf_dctcp_cwnd_event,
258	.ssthresh	= (void *)bpf_dctcp_ssthresh,
259	.cong_avoid	= (void *)bpf_dctcp_cong_avoid,
260	.undo_cwnd	= (void *)bpf_dctcp_cwnd_undo,
261	.set_state	= (void *)bpf_dctcp_state,
262	.flags		= TCP_CONG_NEEDS_ECN,
263	.name		= "bpf_dctcp",
264};