123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179 |
- // SPDX-License-Identifier: GPL-2.0
- /* Copyright (c) 2019 Facebook
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of version 2 of the GNU General Public
- * License as published by the Free Software Foundation.
- *
- * Sample Host Bandwidth Manager (HBM) BPF program.
- *
- * A cgroup skb BPF egress program to limit cgroup output bandwidth.
- * It uses a modified virtual token bucket queue to limit average
- * egress bandwidth. The implementation uses credits instead of tokens.
- * Negative credits imply that queueing would have happened (this is
- * a virtual queue, so no queueing is done by it. However, queueing may
- * occur at the actual qdisc (which is not used for rate limiting).
- *
- * This implementation uses 3 thresholds, one to start marking packets and
- * the other two to drop packets:
- * CREDIT
- * - <--------------------------|------------------------> +
- * | | | 0
- * | Large pkt |
- * | drop thresh |
- * Small pkt drop Mark threshold
- * thresh
- *
- * The effect of marking depends on the type of packet:
- * a) If the packet is ECN enabled and it is a TCP packet, then the packet
- * is ECN marked.
- * b) If the packet is a TCP packet, then we probabilistically call tcp_cwr
- * to reduce the congestion window. The current implementation uses a linear
- * distribution (0% probability at marking threshold, 100% probability
- * at drop threshold).
- * c) If the packet is not a TCP packet, then it is dropped.
- *
- * If the credit is below the drop threshold, the packet is dropped. If it
- * is a TCP packet, then it also calls tcp_cwr since packets dropped by
- * by a cgroup skb BPF program do not automatically trigger a call to
- * tcp_cwr in the current kernel code.
- *
- * This BPF program actually uses 2 drop thresholds, one threshold
- * for larger packets (>= 120 bytes) and another for smaller packets. This
- * protects smaller packets such as SYNs, ACKs, etc.
- *
- * The default bandwidth limit is set at 1Gbps but this can be changed by
- * a user program through a shared BPF map. In addition, by default this BPF
- * program does not limit connections using loopback. This behavior can be
- * overwritten by the user program. There is also an option to calculate
- * some statistics, such as percent of packets marked or dropped, which
- * the user program can access.
- *
- * A latter patch provides such a program (hbm.c)
- */
- #include "hbm_kern.h"
- SEC("cgroup_skb/egress")
- int _hbm_out_cg(struct __sk_buff *skb)
- {
- struct hbm_pkt_info pkti;
- int len = skb->len;
- unsigned int queue_index = 0;
- unsigned long long curtime;
- int credit;
- signed long long delta = 0, new_credit;
- int max_credit = MAX_CREDIT;
- bool congestion_flag = false;
- bool drop_flag = false;
- bool cwr_flag = false;
- bool ecn_ce_flag = false;
- struct hbm_vqueue *qdp;
- struct hbm_queue_stats *qsp = NULL;
- int rv = ALLOW_PKT;
- qsp = bpf_map_lookup_elem(&queue_stats, &queue_index);
- if (qsp != NULL && !qsp->loopback && (skb->ifindex == 1))
- return ALLOW_PKT;
- hbm_get_pkt_info(skb, &pkti);
- // We may want to account for the length of headers in len
- // calculation, like ETH header + overhead, specially if it
- // is a gso packet. But I am not doing it right now.
- qdp = bpf_get_local_storage(&queue_state, 0);
- if (!qdp)
- return ALLOW_PKT;
- else if (qdp->lasttime == 0)
- hbm_init_vqueue(qdp, 1024);
- curtime = bpf_ktime_get_ns();
- // Begin critical section
- bpf_spin_lock(&qdp->lock);
- credit = qdp->credit;
- delta = curtime - qdp->lasttime;
- /* delta < 0 implies that another process with a curtime greater
- * than ours beat us to the critical section and already added
- * the new credit, so we should not add it ourselves
- */
- if (delta > 0) {
- qdp->lasttime = curtime;
- new_credit = credit + CREDIT_PER_NS(delta, qdp->rate);
- if (new_credit > MAX_CREDIT)
- credit = MAX_CREDIT;
- else
- credit = new_credit;
- }
- credit -= len;
- qdp->credit = credit;
- bpf_spin_unlock(&qdp->lock);
- // End critical section
- // Check if we should update rate
- if (qsp != NULL && (qsp->rate * 128) != qdp->rate) {
- qdp->rate = qsp->rate * 128;
- bpf_printk("Updating rate: %d (1sec:%llu bits)\n",
- (int)qdp->rate,
- CREDIT_PER_NS(1000000000, qdp->rate) * 8);
- }
- // Set flags (drop, congestion, cwr)
- // Dropping => we are congested, so ignore congestion flag
- if (credit < -DROP_THRESH ||
- (len > LARGE_PKT_THRESH && credit < -LARGE_PKT_DROP_THRESH)) {
- // Very congested, set drop packet
- drop_flag = true;
- if (pkti.ecn)
- congestion_flag = true;
- else if (pkti.is_tcp)
- cwr_flag = true;
- } else if (credit < 0) {
- // Congested, set congestion flag
- if (pkti.ecn || pkti.is_tcp) {
- if (credit < -MARK_THRESH)
- congestion_flag = true;
- else
- congestion_flag = false;
- } else {
- congestion_flag = true;
- }
- }
- if (congestion_flag) {
- if (bpf_skb_ecn_set_ce(skb)) {
- ecn_ce_flag = true;
- } else {
- if (pkti.is_tcp) {
- unsigned int rand = bpf_get_prandom_u32();
- if (-credit >= MARK_THRESH +
- (rand % MARK_REGION_SIZE)) {
- // Do congestion control
- cwr_flag = true;
- }
- } else if (len > LARGE_PKT_THRESH) {
- // Problem if too many small packets?
- drop_flag = true;
- }
- }
- }
- if (qsp != NULL)
- if (qsp->no_cn)
- cwr_flag = false;
- hbm_update_stats(qsp, len, curtime, congestion_flag, drop_flag,
- cwr_flag, ecn_ce_flag, &pkti, credit);
- if (drop_flag) {
- __sync_add_and_fetch(&(qdp->credit), len);
- rv = DROP_PKT;
- }
- if (cwr_flag)
- rv |= 2;
- return rv;
- }
- char _license[] SEC("license") = "GPL";
|