samples/bpf/hbm_out_kern.c

   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";