GNU Linux-libre 6.6.15-gnu
[releases.git] / samples / bpf / hbm_out_kern.c
1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (c) 2019 Facebook
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of version 2 of the GNU General Public
6  * License as published by the Free Software Foundation.
7  *
8  * Sample Host Bandwidth Manager (HBM) BPF program.
9  *
10  * A cgroup skb BPF egress program to limit cgroup output bandwidth.
11  * It uses a modified virtual token bucket queue to limit average
12  * egress bandwidth. The implementation uses credits instead of tokens.
13  * Negative credits imply that queueing would have happened (this is
14  * a virtual queue, so no queueing is done by it. However, queueing may
15  * occur at the actual qdisc (which is not used for rate limiting).
16  *
17  * This implementation uses 3 thresholds, one to start marking packets and
18  * the other two to drop packets:
19  *                                  CREDIT
20  *        - <--------------------------|------------------------> +
21  *              |    |          |      0
22  *              |  Large pkt    |
23  *              |  drop thresh  |
24  *   Small pkt drop             Mark threshold
25  *       thresh
26  *
27  * The effect of marking depends on the type of packet:
28  * a) If the packet is ECN enabled and it is a TCP packet, then the packet
29  *    is ECN marked.
30  * b) If the packet is a TCP packet, then we probabilistically call tcp_cwr
31  *    to reduce the congestion window. The current implementation uses a linear
32  *    distribution (0% probability at marking threshold, 100% probability
33  *    at drop threshold).
34  * c) If the packet is not a TCP packet, then it is dropped.
35  *
36  * If the credit is below the drop threshold, the packet is dropped. If it
37  * is a TCP packet, then it also calls tcp_cwr since packets dropped by
38  * by a cgroup skb BPF program do not automatically trigger a call to
39  * tcp_cwr in the current kernel code.
40  *
41  * This BPF program actually uses 2 drop thresholds, one threshold
42  * for larger packets (>= 120 bytes) and another for smaller packets. This
43  * protects smaller packets such as SYNs, ACKs, etc.
44  *
45  * The default bandwidth limit is set at 1Gbps but this can be changed by
46  * a user program through a shared BPF map. In addition, by default this BPF
47  * program does not limit connections using loopback. This behavior can be
48  * overwritten by the user program. There is also an option to calculate
49  * some statistics, such as percent of packets marked or dropped, which
50  * the user program can access.
51  *
52  * A latter patch provides such a program (hbm.c)
53  */
54
55 #include "hbm_kern.h"
56
57 SEC("cgroup_skb/egress")
58 int _hbm_out_cg(struct __sk_buff *skb)
59 {
60         struct hbm_pkt_info pkti;
61         int len = skb->len;
62         unsigned int queue_index = 0;
63         unsigned long long curtime;
64         int credit;
65         signed long long delta = 0, new_credit;
66         int max_credit = MAX_CREDIT;
67         bool congestion_flag = false;
68         bool drop_flag = false;
69         bool cwr_flag = false;
70         bool ecn_ce_flag = false;
71         struct hbm_vqueue *qdp;
72         struct hbm_queue_stats *qsp = NULL;
73         int rv = ALLOW_PKT;
74
75         qsp = bpf_map_lookup_elem(&queue_stats, &queue_index);
76         if (qsp != NULL && !qsp->loopback && (skb->ifindex == 1))
77                 return ALLOW_PKT;
78
79         hbm_get_pkt_info(skb, &pkti);
80
81         // We may want to account for the length of headers in len
82         // calculation, like ETH header + overhead, specially if it
83         // is a gso packet. But I am not doing it right now.
84
85         qdp = bpf_get_local_storage(&queue_state, 0);
86         if (!qdp)
87                 return ALLOW_PKT;
88         else if (qdp->lasttime == 0)
89                 hbm_init_vqueue(qdp, 1024);
90
91         curtime = bpf_ktime_get_ns();
92
93         // Begin critical section
94         bpf_spin_lock(&qdp->lock);
95         credit = qdp->credit;
96         delta = curtime - qdp->lasttime;
97         /* delta < 0 implies that another process with a curtime greater
98          * than ours beat us to the critical section and already added
99          * the new credit, so we should not add it ourselves
100          */
101         if (delta > 0) {
102                 qdp->lasttime = curtime;
103                 new_credit = credit + CREDIT_PER_NS(delta, qdp->rate);
104                 if (new_credit > MAX_CREDIT)
105                         credit = MAX_CREDIT;
106                 else
107                         credit = new_credit;
108         }
109         credit -= len;
110         qdp->credit = credit;
111         bpf_spin_unlock(&qdp->lock);
112         // End critical section
113
114         // Check if we should update rate
115         if (qsp != NULL && (qsp->rate * 128) != qdp->rate) {
116                 qdp->rate = qsp->rate * 128;
117                 bpf_printk("Updating rate: %d (1sec:%llu bits)\n",
118                            (int)qdp->rate,
119                            CREDIT_PER_NS(1000000000, qdp->rate) * 8);
120         }
121
122         // Set flags (drop, congestion, cwr)
123         // Dropping => we are congested, so ignore congestion flag
124         if (credit < -DROP_THRESH ||
125             (len > LARGE_PKT_THRESH && credit < -LARGE_PKT_DROP_THRESH)) {
126                 // Very congested, set drop packet
127                 drop_flag = true;
128                 if (pkti.ecn)
129                         congestion_flag = true;
130                 else if (pkti.is_tcp)
131                         cwr_flag = true;
132         } else if (credit < 0) {
133                 // Congested, set congestion flag
134                 if (pkti.ecn || pkti.is_tcp) {
135                         if (credit < -MARK_THRESH)
136                                 congestion_flag = true;
137                         else
138                                 congestion_flag = false;
139                 } else {
140                         congestion_flag = true;
141                 }
142         }
143
144         if (congestion_flag) {
145                 if (bpf_skb_ecn_set_ce(skb)) {
146                         ecn_ce_flag = true;
147                 } else {
148                         if (pkti.is_tcp) {
149                                 unsigned int rand = bpf_get_prandom_u32();
150
151                                 if (-credit >= MARK_THRESH +
152                                     (rand % MARK_REGION_SIZE)) {
153                                         // Do congestion control
154                                         cwr_flag = true;
155                                 }
156                         } else if (len > LARGE_PKT_THRESH) {
157                                 // Problem if too many small packets?
158                                 drop_flag = true;
159                         }
160                 }
161         }
162
163         if (qsp != NULL)
164                 if (qsp->no_cn)
165                         cwr_flag = false;
166
167         hbm_update_stats(qsp, len, curtime, congestion_flag, drop_flag,
168                          cwr_flag, ecn_ce_flag, &pkti, credit);
169
170         if (drop_flag) {
171                 __sync_add_and_fetch(&(qdp->credit), len);
172                 rv = DROP_PKT;
173         }
174
175         if (cwr_flag)
176                 rv |= 2;
177         return rv;
178 }
179 char _license[] SEC("license") = "GPL";