1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (c) 2019 Facebook
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.
8 * Sample Host Bandwidth Manager (HBM) BPF program.
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).
17 * This implementation uses 3 thresholds, one to start marking packets and
18 * the other two to drop packets:
20 * - <--------------------------|------------------------> +
24 * Small pkt drop Mark threshold
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
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
34 * c) If the packet is not a TCP packet, then it is dropped.
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.
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.
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.
52 * A latter patch provides such a program (hbm.c)
57 SEC("cgroup_skb/egress")
58 int _hbm_out_cg(struct __sk_buff *skb)
60 struct hbm_pkt_info pkti;
62 unsigned int queue_index = 0;
63 unsigned long long curtime;
65 signed long long delta = 0, zero = 0;
66 int max_credit = MAX_CREDIT;
67 bool congestion_flag = false;
68 bool drop_flag = false;
69 bool cwr_flag = false;
70 struct hbm_vqueue *qdp;
71 struct hbm_queue_stats *qsp = NULL;
74 qsp = bpf_map_lookup_elem(&queue_stats, &queue_index);
75 if (qsp != NULL && !qsp->loopback && (skb->ifindex == 1))
78 hbm_get_pkt_info(skb, &pkti);
80 // We may want to account for the length of headers in len
81 // calculation, like ETH header + overhead, specially if it
82 // is a gso packet. But I am not doing it right now.
84 qdp = bpf_get_local_storage(&queue_state, 0);
87 else if (qdp->lasttime == 0)
88 hbm_init_vqueue(qdp, 1024);
90 curtime = bpf_ktime_get_ns();
92 // Begin critical section
93 bpf_spin_lock(&qdp->lock);
95 delta = curtime - qdp->lasttime;
96 /* delta < 0 implies that another process with a curtime greater
97 * than ours beat us to the critical section and already added
98 * the new credit, so we should not add it ourselves
101 qdp->lasttime = curtime;
102 credit += CREDIT_PER_NS(delta, qdp->rate);
103 if (credit > MAX_CREDIT)
107 qdp->credit = credit;
108 bpf_spin_unlock(&qdp->lock);
109 // End critical section
111 // Check if we should update rate
112 if (qsp != NULL && (qsp->rate * 128) != qdp->rate) {
113 qdp->rate = qsp->rate * 128;
114 bpf_printk("Updating rate: %d (1sec:%llu bits)\n",
116 CREDIT_PER_NS(1000000000, qdp->rate) * 8);
119 // Set flags (drop, congestion, cwr)
120 // Dropping => we are congested, so ignore congestion flag
121 if (credit < -DROP_THRESH ||
122 (len > LARGE_PKT_THRESH &&
123 credit < -LARGE_PKT_DROP_THRESH)) {
124 // Very congested, set drop flag
126 } else if (credit < 0) {
127 // Congested, set congestion flag
129 if (credit < -MARK_THRESH)
130 congestion_flag = true;
132 congestion_flag = false;
134 congestion_flag = true;
138 if (congestion_flag) {
139 if (!bpf_skb_ecn_set_ce(skb)) {
140 if (len > LARGE_PKT_THRESH) {
141 // Problem if too many small packets?
150 hbm_update_stats(qsp, len, curtime, congestion_flag, drop_flag);
153 __sync_add_and_fetch(&(qdp->credit), len);
157 char _license[] SEC("license") = "GPL";