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