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
 57SEC("cgroup_skb/egress")
 58int _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}
179char _license[] SEC("license") = "GPL";