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