hbm_out_kern.c 5.5 KB

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