bpf/progs/bpf_dctcp.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /* Copyright (c) 2019 Facebook */
0003
0004 /* WARNING: This implemenation is not necessarily the same
0005  * as the tcp_dctcp.c.  The purpose is mainly for testing
0006  * the kernel BPF logic.
0007  */
0008
0009 #include <stddef.h>
0010 #include <linux/bpf.h>
0011 #include <linux/types.h>
0012 #include <linux/stddef.h>
0013 #include <linux/tcp.h>
0014 #include <bpf/bpf_helpers.h>
0015 #include <bpf/bpf_tracing.h>
0016 #include "bpf_tcp_helpers.h"
0017
0018 char _license[] SEC("license") = "GPL";
0019
0020 volatile const char fallback[TCP_CA_NAME_MAX];
0021 const char bpf_dctcp[] = "bpf_dctcp";
0022 const char tcp_cdg[] = "cdg";
0023 char cc_res[TCP_CA_NAME_MAX];
0024 int tcp_cdg_res = 0;
0025 int stg_result = 0;
0026
0027 struct {
0028     __uint(type, BPF_MAP_TYPE_SK_STORAGE);
0029     __uint(map_flags, BPF_F_NO_PREALLOC);
0030     __type(key, int);
0031     __type(value, int);
0032 } sk_stg_map SEC(".maps");
0033
0034 #define DCTCP_MAX_ALPHA 1024U
0035
0036 struct dctcp {
0037     __u32 old_delivered;
0038     __u32 old_delivered_ce;
0039     __u32 prior_rcv_nxt;
0040     __u32 dctcp_alpha;
0041     __u32 next_seq;
0042     __u32 ce_state;
0043     __u32 loss_cwnd;
0044 };
0045
0046 static unsigned int dctcp_shift_g = 4; /* g = 1/2^4 */
0047 static unsigned int dctcp_alpha_on_init = DCTCP_MAX_ALPHA;
0048
0049 static __always_inline void dctcp_reset(const struct tcp_sock *tp,
0050                     struct dctcp *ca)
0051 {
0052     ca->next_seq = tp->snd_nxt;
0053
0054     ca->old_delivered = tp->delivered;
0055     ca->old_delivered_ce = tp->delivered_ce;
0056 }
0057
0058 SEC("struct_ops/dctcp_init")
0059 void BPF_PROG(dctcp_init, struct sock *sk)
0060 {
0061     const struct tcp_sock *tp = tcp_sk(sk);
0062     struct dctcp *ca = inet_csk_ca(sk);
0063     int *stg;
0064
0065     if (!(tp->ecn_flags & TCP_ECN_OK) && fallback[0]) {
0066         /* Switch to fallback */
0067         bpf_setsockopt(sk, SOL_TCP, TCP_CONGESTION,
0068                    (void *)fallback, sizeof(fallback));
0069         /* Switch back to myself which the bpf trampoline
0070          * stopped calling dctcp_init recursively.
0071          */
0072         bpf_setsockopt(sk, SOL_TCP, TCP_CONGESTION,
0073                    (void *)bpf_dctcp, sizeof(bpf_dctcp));
0074         /* Switch back to fallback */
0075         bpf_setsockopt(sk, SOL_TCP, TCP_CONGESTION,
0076                    (void *)fallback, sizeof(fallback));
0077         /* Expecting -ENOTSUPP for tcp_cdg_res */
0078         tcp_cdg_res = bpf_setsockopt(sk, SOL_TCP, TCP_CONGESTION,
0079                          (void *)tcp_cdg, sizeof(tcp_cdg));
0080         bpf_getsockopt(sk, SOL_TCP, TCP_CONGESTION,
0081                    (void *)cc_res, sizeof(cc_res));
0082         return;
0083     }
0084
0085     ca->prior_rcv_nxt = tp->rcv_nxt;
0086     ca->dctcp_alpha = min(dctcp_alpha_on_init, DCTCP_MAX_ALPHA);
0087     ca->loss_cwnd = 0;
0088     ca->ce_state = 0;
0089
0090     stg = bpf_sk_storage_get(&sk_stg_map, (void *)tp, NULL, 0);
0091     if (stg) {
0092         stg_result = *stg;
0093         bpf_sk_storage_delete(&sk_stg_map, (void *)tp);
0094     }
0095     dctcp_reset(tp, ca);
0096 }
0097
0098 SEC("struct_ops/dctcp_ssthresh")
0099 __u32 BPF_PROG(dctcp_ssthresh, struct sock *sk)
0100 {
0101     struct dctcp *ca = inet_csk_ca(sk);
0102     struct tcp_sock *tp = tcp_sk(sk);
0103
0104     ca->loss_cwnd = tp->snd_cwnd;
0105     return max(tp->snd_cwnd - ((tp->snd_cwnd * ca->dctcp_alpha) >> 11U), 2U);
0106 }
0107
0108 SEC("struct_ops/dctcp_update_alpha")
0109 void BPF_PROG(dctcp_update_alpha, struct sock *sk, __u32 flags)
0110 {
0111     const struct tcp_sock *tp = tcp_sk(sk);
0112     struct dctcp *ca = inet_csk_ca(sk);
0113
0114     /* Expired RTT */
0115     if (!before(tp->snd_una, ca->next_seq)) {
0116         __u32 delivered_ce = tp->delivered_ce - ca->old_delivered_ce;
0117         __u32 alpha = ca->dctcp_alpha;
0118
0119         /* alpha = (1 - g) * alpha + g * F */
0120
0121         alpha -= min_not_zero(alpha, alpha >> dctcp_shift_g);
0122         if (delivered_ce) {
0123             __u32 delivered = tp->delivered - ca->old_delivered;
0124
0125             /* If dctcp_shift_g == 1, a 32bit value would overflow
0126              * after 8 M packets.
0127              */
0128             delivered_ce <<= (10 - dctcp_shift_g);
0129             delivered_ce /= max(1U, delivered);
0130
0131             alpha = min(alpha + delivered_ce, DCTCP_MAX_ALPHA);
0132         }
0133         ca->dctcp_alpha = alpha;
0134         dctcp_reset(tp, ca);
0135     }
0136 }
0137
0138 static __always_inline void dctcp_react_to_loss(struct sock *sk)
0139 {
0140     struct dctcp *ca = inet_csk_ca(sk);
0141     struct tcp_sock *tp = tcp_sk(sk);
0142
0143     ca->loss_cwnd = tp->snd_cwnd;
0144     tp->snd_ssthresh = max(tp->snd_cwnd >> 1U, 2U);
0145 }
0146
0147 SEC("struct_ops/dctcp_state")
0148 void BPF_PROG(dctcp_state, struct sock *sk, __u8 new_state)
0149 {
0150     if (new_state == TCP_CA_Recovery &&
0151         new_state != BPF_CORE_READ_BITFIELD(inet_csk(sk), icsk_ca_state))
0152         dctcp_react_to_loss(sk);
0153     /* We handle RTO in dctcp_cwnd_event to ensure that we perform only
0154      * one loss-adjustment per RTT.
0155      */
0156 }
0157
0158 static __always_inline void dctcp_ece_ack_cwr(struct sock *sk, __u32 ce_state)
0159 {
0160     struct tcp_sock *tp = tcp_sk(sk);
0161
0162     if (ce_state == 1)
0163         tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
0164     else
0165         tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR;
0166 }
0167
0168 /* Minimal DCTP CE state machine:
0169  *
0170  * S:   0 <- last pkt was non-CE
0171  *  1 <- last pkt was CE
0172  */
0173 static __always_inline
0174 void dctcp_ece_ack_update(struct sock *sk, enum tcp_ca_event evt,
0175               __u32 *prior_rcv_nxt, __u32 *ce_state)
0176 {
0177     __u32 new_ce_state = (evt == CA_EVENT_ECN_IS_CE) ? 1 : 0;
0178
0179     if (*ce_state != new_ce_state) {
0180         /* CE state has changed, force an immediate ACK to
0181          * reflect the new CE state. If an ACK was delayed,
0182          * send that first to reflect the prior CE state.
0183          */
0184         if (inet_csk(sk)->icsk_ack.pending & ICSK_ACK_TIMER) {
0185             dctcp_ece_ack_cwr(sk, *ce_state);
0186             bpf_tcp_send_ack(sk, *prior_rcv_nxt);
0187         }
0188         inet_csk(sk)->icsk_ack.pending |= ICSK_ACK_NOW;
0189     }
0190     *prior_rcv_nxt = tcp_sk(sk)->rcv_nxt;
0191     *ce_state = new_ce_state;
0192     dctcp_ece_ack_cwr(sk, new_ce_state);
0193 }
0194
0195 SEC("struct_ops/dctcp_cwnd_event")
0196 void BPF_PROG(dctcp_cwnd_event, struct sock *sk, enum tcp_ca_event ev)
0197 {
0198     struct dctcp *ca = inet_csk_ca(sk);
0199
0200     switch (ev) {
0201     case CA_EVENT_ECN_IS_CE:
0202     case CA_EVENT_ECN_NO_CE:
0203         dctcp_ece_ack_update(sk, ev, &ca->prior_rcv_nxt, &ca->ce_state);
0204         break;
0205     case CA_EVENT_LOSS:
0206         dctcp_react_to_loss(sk);
0207         break;
0208     default:
0209         /* Don't care for the rest. */
0210         break;
0211     }
0212 }
0213
0214 SEC("struct_ops/dctcp_cwnd_undo")
0215 __u32 BPF_PROG(dctcp_cwnd_undo, struct sock *sk)
0216 {
0217     const struct dctcp *ca = inet_csk_ca(sk);
0218
0219     return max(tcp_sk(sk)->snd_cwnd, ca->loss_cwnd);
0220 }
0221
0222 extern void tcp_reno_cong_avoid(struct sock *sk, __u32 ack, __u32 acked) __ksym;
0223
0224 SEC("struct_ops/dctcp_reno_cong_avoid")
0225 void BPF_PROG(dctcp_cong_avoid, struct sock *sk, __u32 ack, __u32 acked)
0226 {
0227     tcp_reno_cong_avoid(sk, ack, acked);
0228 }
0229
0230 SEC(".struct_ops")
0231 struct tcp_congestion_ops dctcp_nouse = {
0232     .init       = (void *)dctcp_init,
0233     .set_state  = (void *)dctcp_state,
0234     .flags      = TCP_CONG_NEEDS_ECN,
0235     .name       = "bpf_dctcp_nouse",
0236 };
0237
0238 SEC(".struct_ops")
0239 struct tcp_congestion_ops dctcp = {
0240     .init       = (void *)dctcp_init,
0241     .in_ack_event   = (void *)dctcp_update_alpha,
0242     .cwnd_event = (void *)dctcp_cwnd_event,
0243     .ssthresh   = (void *)dctcp_ssthresh,
0244     .cong_avoid = (void *)dctcp_cong_avoid,
0245     .undo_cwnd  = (void *)dctcp_cwnd_undo,
0246     .set_state  = (void *)dctcp_state,
0247     .flags      = TCP_CONG_NEEDS_ECN,
0248     .name       = "bpf_dctcp",
0249 };