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