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  * 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  * a user program, such as hbm, can access.
51  */
52 
53 #include "hbm_kern.h"
54 
55 SEC("cgroup_skb/egress")
_hbm_out_cg(struct __sk_buff * skb)56 int _hbm_out_cg(struct __sk_buff *skb)
57 {
58 	long long delta = 0, delta_send;
59 	unsigned long long curtime, sendtime;
60 	struct hbm_queue_stats *qsp = NULL;
61 	unsigned int queue_index = 0;
62 	bool congestion_flag = false;
63 	bool ecn_ce_flag = false;
64 	struct hbm_pkt_info pkti = {};
65 	struct hbm_vqueue *qdp;
66 	bool drop_flag = false;
67 	bool cwr_flag = false;
68 	int len = skb->len;
69 	int rv = ALLOW_PKT;
70 
71 	qsp = bpf_map_lookup_elem(&queue_stats, &queue_index);
72 
73 	// Check if we should ignore loopback traffic
74 	if (qsp != NULL && !qsp->loopback && (skb->ifindex == 1))
75 		return ALLOW_PKT;
76 
77 	hbm_get_pkt_info(skb, &pkti);
78 
79 	// We may want to account for the length of headers in len
80 	// calculation, like ETH header + overhead, specially if it
81 	// is a gso packet. But I am not doing it right now.
82 
83 	qdp = bpf_get_local_storage(&queue_state, 0);
84 	if (!qdp)
85 		return ALLOW_PKT;
86 	if (qdp->lasttime == 0)
87 		hbm_init_edt_vqueue(qdp, 1024);
88 
89 	curtime = bpf_ktime_get_ns();
90 
91 	// Begin critical section
92 	bpf_spin_lock(&qdp->lock);
93 	delta = qdp->lasttime - curtime;
94 	// bound bursts to 100us
95 	if (delta < -BURST_SIZE_NS) {
96 		// negative delta is a credit that allows bursts
97 		qdp->lasttime = curtime - BURST_SIZE_NS;
98 		delta = -BURST_SIZE_NS;
99 	}
100 	sendtime = qdp->lasttime;
101 	delta_send = BYTES_TO_NS(len, qdp->rate);
102 	__sync_add_and_fetch(&(qdp->lasttime), delta_send);
103 	bpf_spin_unlock(&qdp->lock);
104 	// End critical section
105 
106 	// Set EDT of packet
107 	skb->tstamp = sendtime;
108 
109 	// Check if we should update rate
110 	if (qsp != NULL && (qsp->rate * 128) != qdp->rate)
111 		qdp->rate = qsp->rate * 128;
112 
113 	// Set flags (drop, congestion, cwr)
114 	// last packet will be sent in the future, bound latency
115 	if (delta > DROP_THRESH_NS || (delta > LARGE_PKT_DROP_THRESH_NS &&
116 				       len > LARGE_PKT_THRESH)) {
117 		drop_flag = true;
118 		if (pkti.is_tcp && pkti.ecn == 0)
119 			cwr_flag = true;
120 	} else if (delta > MARK_THRESH_NS) {
121 		if (pkti.is_tcp)
122 			congestion_flag = true;
123 		else
124 			drop_flag = true;
125 	}
126 
127 	if (congestion_flag) {
128 		if (bpf_skb_ecn_set_ce(skb)) {
129 			ecn_ce_flag = true;
130 		} else {
131 			if (pkti.is_tcp) {
132 				unsigned int rand = bpf_get_prandom_u32();
133 
134 				if (delta >= MARK_THRESH_NS +
135 				    (rand % MARK_REGION_SIZE_NS)) {
136 					// Do congestion control
137 					cwr_flag = true;
138 				}
139 			} else if (len > LARGE_PKT_THRESH) {
140 				// Problem if too many small packets?
141 				drop_flag = true;
142 				congestion_flag = false;
143 			}
144 		}
145 	}
146 
147 	if (pkti.is_tcp && drop_flag && pkti.packets_out <= 1) {
148 		drop_flag = false;
149 		cwr_flag = true;
150 		congestion_flag = false;
151 	}
152 
153 	if (qsp != NULL && qsp->no_cn)
154 			cwr_flag = false;
155 
156 	hbm_update_stats(qsp, len, curtime, congestion_flag, drop_flag,
157 			 cwr_flag, ecn_ce_flag, &pkti, (int) delta);
158 
159 	if (drop_flag) {
160 		__sync_add_and_fetch(&(qdp->lasttime), -delta_send);
161 		rv = DROP_PKT;
162 	}
163 
164 	if (cwr_flag)
165 		rv |= CWR;
166 	return rv;
167 }
168 char _license[] SEC("license") = "GPL";
169