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 <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);
  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);
 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);
 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), icsk_ca_state))
 161                 dctcp_react_to_loss(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);
 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, 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);
 208
 209         switch (ev) {
 210         case CA_EVENT_ECN_IS_CE:
 211         case CA_EVENT_ECN_NO_CE:
 212                 dctcp_ece_ack_update(sk, ev, &ca->prior_rcv_nxt, &ca->ce_state);
 213                 break;
 214         case CA_EVENT_LOSS:
 215                 dctcp_react_to_loss(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);
 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 };