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