tools/testing/selftests/bpf/progs/bpf_dctcp.c

   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 };