180 lines · c
1// SPDX-License-Identifier: GPL-2.02/* Copyright (c) 2019 Facebook3 *4 * This program is free software; you can redistribute it and/or5 * modify it under the terms of version 2 of the GNU General Public6 * 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 average12 * egress bandwidth. The implementation uses credits instead of tokens.13 * Negative credits imply that queueing would have happened (this is14 * a virtual queue, so no queueing is done by it. However, queueing may15 * occur at the actual qdisc (which is not used for rate limiting).16 *17 * This implementation uses 3 thresholds, one to start marking packets and18 * the other two to drop packets:19 * CREDIT20 * - <--------------------------|------------------------> +21 * | | | 022 * | Large pkt |23 * | drop thresh |24 * Small pkt drop Mark threshold25 * thresh26 *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 packet29 * is ECN marked.30 * b) If the packet is a TCP packet, then we probabilistically call tcp_cwr31 * to reduce the congestion window. The current implementation uses a linear32 * distribution (0% probability at marking threshold, 100% probability33 * 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 it37 * is a TCP packet, then it also calls tcp_cwr since packets dropped by38 * by a cgroup skb BPF program do not automatically trigger a call to39 * tcp_cwr in the current kernel code.40 *41 * This BPF program actually uses 2 drop thresholds, one threshold42 * for larger packets (>= 120 bytes) and another for smaller packets. This43 * protects smaller packets such as SYNs, ACKs, etc.44 *45 * The default bandwidth limit is set at 1Gbps but this can be changed by46 * a user program through a shared BPF map. In addition, by default this BPF47 * program does not limit connections using loopback. This behavior can be48 * overwritten by the user program. There is also an option to calculate49 * some statistics, such as percent of packets marked or dropped, which50 * 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 len82 // calculation, like ETH header + overhead, specially if it83 // 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 section94 bpf_spin_lock(&qdp->lock);95 credit = qdp->credit;96 delta = curtime - qdp->lasttime;97 /* delta < 0 implies that another process with a curtime greater98 * than ours beat us to the critical section and already added99 * the new credit, so we should not add it ourselves100 */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 else107 credit = new_credit;108 }109 credit -= len;110 qdp->credit = credit;111 bpf_spin_unlock(&qdp->lock);112 // End critical section113 114 // Check if we should update rate115 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 flag124 if (credit < -DROP_THRESH ||125 (len > LARGE_PKT_THRESH && credit < -LARGE_PKT_DROP_THRESH)) {126 // Very congested, set drop packet127 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 flag134 if (pkti.ecn || pkti.is_tcp) {135 if (credit < -MARK_THRESH)136 congestion_flag = true;137 else138 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 control154 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";180