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