| 187d0738 |
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, zero = 0; |
| 66 | int max_credit = MAX_CREDIT; |
| 67 | bool congestion_flag = false; |
| 68 | bool drop_flag = false; |
| 69 | bool cwr_flag = false; |
| 70 | struct hbm_vqueue *qdp; |
| 71 | struct hbm_queue_stats *qsp = NULL; |
| 72 | int rv = ALLOW_PKT; |
| 73 | |
| 74 | qsp = bpf_map_lookup_elem(&queue_stats, &queue_index); |
| 75 | if (qsp != NULL && !qsp->loopback && (skb->ifindex == 1)) |
| 76 | return ALLOW_PKT; |
| 77 | |
| 78 | hbm_get_pkt_info(skb, &pkti); |
| 79 | |
| 80 | // We may want to account for the length of headers in len |
| 81 | // calculation, like ETH header + overhead, specially if it |
| 82 | // is a gso packet. But I am not doing it right now. |
| 83 | |
| 84 | qdp = bpf_get_local_storage(&queue_state, 0); |
| 85 | if (!qdp) |
| 86 | return ALLOW_PKT; |
| 87 | else if (qdp->lasttime == 0) |
| 88 | hbm_init_vqueue(qdp, 1024); |
| 89 | |
| 90 | curtime = bpf_ktime_get_ns(); |
| 91 | |
| 92 | // Begin critical section |
| 93 | bpf_spin_lock(&qdp->lock); |
| 94 | credit = qdp->credit; |
| 95 | delta = curtime - qdp->lasttime; |
| 96 | /* delta < 0 implies that another process with a curtime greater |
| 97 | * than ours beat us to the critical section and already added |
| 98 | * the new credit, so we should not add it ourselves |
| 99 | */ |
| 100 | if (delta > 0) { |
| 101 | qdp->lasttime = curtime; |
| 102 | credit += CREDIT_PER_NS(delta, qdp->rate); |
| 103 | if (credit > MAX_CREDIT) |
| 104 | credit = MAX_CREDIT; |
| 105 | } |
| 106 | credit -= len; |
| 107 | qdp->credit = credit; |
| 108 | bpf_spin_unlock(&qdp->lock); |
| 109 | // End critical section |
| 110 | |
| 111 | // Check if we should update rate |
| 112 | if (qsp != NULL && (qsp->rate * 128) != qdp->rate) { |
| 113 | qdp->rate = qsp->rate * 128; |
| 114 | bpf_printk("Updating rate: %d (1sec:%llu bits)\n", |
| 115 | (int)qdp->rate, |
| 116 | CREDIT_PER_NS(1000000000, qdp->rate) * 8); |
| 117 | } |
| 118 | |
| 119 | // Set flags (drop, congestion, cwr) |
| 120 | // Dropping => we are congested, so ignore congestion flag |
| 121 | if (credit < -DROP_THRESH || |
| 122 | (len > LARGE_PKT_THRESH && |
| 123 | credit < -LARGE_PKT_DROP_THRESH)) { |
| 124 | // Very congested, set drop flag |
| 125 | drop_flag = true; |
| 126 | } else if (credit < 0) { |
| 127 | // Congested, set congestion flag |
| 128 | if (pkti.ecn) { |
| 129 | if (credit < -MARK_THRESH) |
| 130 | congestion_flag = true; |
| 131 | else |
| 132 | congestion_flag = false; |
| 133 | } else { |
| 134 | congestion_flag = true; |
| 135 | } |
| 136 | } |
| 137 | |
| 138 | if (congestion_flag) { |
| 139 | if (!bpf_skb_ecn_set_ce(skb)) { |
| 140 | if (len > LARGE_PKT_THRESH) { |
| 141 | // Problem if too many small packets? |
| 142 | drop_flag = true; |
| 143 | } |
| 144 | } |
| 145 | } |
| 146 | |
| 147 | if (drop_flag) |
| 148 | rv = DROP_PKT; |
| 149 | |
| 150 | hbm_update_stats(qsp, len, curtime, congestion_flag, drop_flag); |
| 151 | |
| 152 | if (rv == DROP_PKT) |
| 153 | __sync_add_and_fetch(&(qdp->credit), len); |
| 154 | |
| 155 | return rv; |
| 156 | } |
| 157 | char _license[] SEC("license") = "GPL"; |
projects / mirror_ubuntu-jammy-kernel.git / blame