samples/bpf/hbm_out_kern.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /* Copyright (c) 2019 Facebook
0003  *
0004  * This program is free software; you can redistribute it and/or
0005  * modify it under the terms of version 2 of the GNU General Public
0006  * License as published by the Free Software Foundation.
0007  *
0008  * Sample Host Bandwidth Manager (HBM) BPF program.
0009  *
0010  * A cgroup skb BPF egress program to limit cgroup output bandwidth.
0011  * It uses a modified virtual token bucket queue to limit average
0012  * egress bandwidth. The implementation uses credits instead of tokens.
0013  * Negative credits imply that queueing would have happened (this is
0014  * a virtual queue, so no queueing is done by it. However, queueing may
0015  * occur at the actual qdisc (which is not used for rate limiting).
0016  *
0017  * This implementation uses 3 thresholds, one to start marking packets and
0018  * the other two to drop packets:
0019  *                                  CREDIT
0020  *        - <--------------------------|------------------------> +
0021  *              |    |          |      0
0022  *              |  Large pkt    |
0023  *              |  drop thresh  |
0024  *   Small pkt drop             Mark threshold
0025  *       thresh
0026  *
0027  * The effect of marking depends on the type of packet:
0028  * a) If the packet is ECN enabled and it is a TCP packet, then the packet
0029  *    is ECN marked.
0030  * b) If the packet is a TCP packet, then we probabilistically call tcp_cwr
0031  *    to reduce the congestion window. The current implementation uses a linear
0032  *    distribution (0% probability at marking threshold, 100% probability
0033  *    at drop threshold).
0034  * c) If the packet is not a TCP packet, then it is dropped.
0035  *
0036  * If the credit is below the drop threshold, the packet is dropped. If it
0037  * is a TCP packet, then it also calls tcp_cwr since packets dropped by
0038  * by a cgroup skb BPF program do not automatically trigger a call to
0039  * tcp_cwr in the current kernel code.
0040  *
0041  * This BPF program actually uses 2 drop thresholds, one threshold
0042  * for larger packets (>= 120 bytes) and another for smaller packets. This
0043  * protects smaller packets such as SYNs, ACKs, etc.
0044  *
0045  * The default bandwidth limit is set at 1Gbps but this can be changed by
0046  * a user program through a shared BPF map. In addition, by default this BPF
0047  * program does not limit connections using loopback. This behavior can be
0048  * overwritten by the user program. There is also an option to calculate
0049  * some statistics, such as percent of packets marked or dropped, which
0050  * the user program can access.
0051  *
0052  * A latter patch provides such a program (hbm.c)
0053  */
0054
0055 #include "hbm_kern.h"
0056
0057 SEC("cgroup_skb/egress")
0058 int _hbm_out_cg(struct __sk_buff *skb)
0059 {
0060     struct hbm_pkt_info pkti;
0061     int len = skb->len;
0062     unsigned int queue_index = 0;
0063     unsigned long long curtime;
0064     int credit;
0065     signed long long delta = 0, new_credit;
0066     int max_credit = MAX_CREDIT;
0067     bool congestion_flag = false;
0068     bool drop_flag = false;
0069     bool cwr_flag = false;
0070     bool ecn_ce_flag = false;
0071     struct hbm_vqueue *qdp;
0072     struct hbm_queue_stats *qsp = NULL;
0073     int rv = ALLOW_PKT;
0074
0075     qsp = bpf_map_lookup_elem(&queue_stats, &queue_index);
0076     if (qsp != NULL && !qsp->loopback && (skb->ifindex == 1))
0077         return ALLOW_PKT;
0078
0079     hbm_get_pkt_info(skb, &pkti);
0080
0081     // We may want to account for the length of headers in len
0082     // calculation, like ETH header + overhead, specially if it
0083     // is a gso packet. But I am not doing it right now.
0084
0085     qdp = bpf_get_local_storage(&queue_state, 0);
0086     if (!qdp)
0087         return ALLOW_PKT;
0088     else if (qdp->lasttime == 0)
0089         hbm_init_vqueue(qdp, 1024);
0090
0091     curtime = bpf_ktime_get_ns();
0092
0093     // Begin critical section
0094     bpf_spin_lock(&qdp->lock);
0095     credit = qdp->credit;
0096     delta = curtime - qdp->lasttime;
0097     /* delta < 0 implies that another process with a curtime greater
0098      * than ours beat us to the critical section and already added
0099      * the new credit, so we should not add it ourselves
0100      */
0101     if (delta > 0) {
0102         qdp->lasttime = curtime;
0103         new_credit = credit + CREDIT_PER_NS(delta, qdp->rate);
0104         if (new_credit > MAX_CREDIT)
0105             credit = MAX_CREDIT;
0106         else
0107             credit = new_credit;
0108     }
0109     credit -= len;
0110     qdp->credit = credit;
0111     bpf_spin_unlock(&qdp->lock);
0112     // End critical section
0113
0114     // Check if we should update rate
0115     if (qsp != NULL && (qsp->rate * 128) != qdp->rate) {
0116         qdp->rate = qsp->rate * 128;
0117         bpf_printk("Updating rate: %d (1sec:%llu bits)\n",
0118                (int)qdp->rate,
0119                CREDIT_PER_NS(1000000000, qdp->rate) * 8);
0120     }
0121
0122     // Set flags (drop, congestion, cwr)
0123     // Dropping => we are congested, so ignore congestion flag
0124     if (credit < -DROP_THRESH ||
0125         (len > LARGE_PKT_THRESH && credit < -LARGE_PKT_DROP_THRESH)) {
0126         // Very congested, set drop packet
0127         drop_flag = true;
0128         if (pkti.ecn)
0129             congestion_flag = true;
0130         else if (pkti.is_tcp)
0131             cwr_flag = true;
0132     } else if (credit < 0) {
0133         // Congested, set congestion flag
0134         if (pkti.ecn || pkti.is_tcp) {
0135             if (credit < -MARK_THRESH)
0136                 congestion_flag = true;
0137             else
0138                 congestion_flag = false;
0139         } else {
0140             congestion_flag = true;
0141         }
0142     }
0143
0144     if (congestion_flag) {
0145         if (bpf_skb_ecn_set_ce(skb)) {
0146             ecn_ce_flag = true;
0147         } else {
0148             if (pkti.is_tcp) {
0149                 unsigned int rand = bpf_get_prandom_u32();
0150
0151                 if (-credit >= MARK_THRESH +
0152                     (rand % MARK_REGION_SIZE)) {
0153                     // Do congestion control
0154                     cwr_flag = true;
0155                 }
0156             } else if (len > LARGE_PKT_THRESH) {
0157                 // Problem if too many small packets?
0158                 drop_flag = true;
0159             }
0160         }
0161     }
0162
0163     if (qsp != NULL)
0164         if (qsp->no_cn)
0165             cwr_flag = false;
0166
0167     hbm_update_stats(qsp, len, curtime, congestion_flag, drop_flag,
0168              cwr_flag, ecn_ce_flag, &pkti, credit);
0169
0170     if (drop_flag) {
0171         __sync_add_and_fetch(&(qdp->credit), len);
0172         rv = DROP_PKT;
0173     }
0174
0175     if (cwr_flag)
0176         rv |= 2;
0177     return rv;
0178 }
0179 char _license[] SEC("license") = "GPL";