Rate limit by hard-coded 16-packet leaky bucket with less storage

diff --git a/genrules.py b/genrules.py
index b2bf796af9a86e43218f70e2a7c8f21eda034f01..93c22f5c9059dfb7f7cccefa7707dda1fb849871 100755 (executable)
--- a/genrules.py
+++ b/genrules.py
@@ -395,17 +395,17 @@ with open("rules.h", "w") as out:
                     elif exp == 0xff:
                         # NaN/INF. Just treat as INF and accept
                         first_action = None
-                    elif exp <= 127: # < 1
+                    elif exp < 127: # < 1
                         first_action = "{stats_replace}\nreturn XDP_DROP;"
-                    elif exp >= 127 + 63: # The count won't even fit in 64-bits, just accept
+                    elif exp >= 127 + 29: # We can't handle the precision required with ns this high
                         first_action = None
                     else:
                         mantissa = low_bytes & ((1 << 23) - 1)
                         value = 1.0 + mantissa / (2**23)
                         value *= 2**(exp-127)
-                        # Note that int64_t will overflow after 292 years of uptime
-                        first_action = "int64_t time = bpf_ktime_get_ns();\n"
-                        first_action +=  "uint64_t allowed_since_last = 0;\n"
+
+                        first_action =   "int64_t time = bpf_ktime_get_ns() & RATE_TIME_MASK;\n"
+                        first_action += f"int64_t per_pkt_ns = (1000000000LL << RATE_BUCKET_INTEGER_BITS) / {math.floor(value)};\n"
                         if ty == "0x8006" or ty == "0x800c":
                             spin_lock = "bpf_spin_lock(&rate->lock);"
                             spin_unlock = "bpf_spin_unlock(&rate->lock);"
@@ -437,27 +437,30 @@ with open("rules.h", "w") as out:
                                 first_action += f"struct persrc_rate6_ptr rate_ptr = get_v6_persrc_ratelimit(srcip, rate_map, {(high_byte + 1) * 4096});\n"
                                 first_action += f"struct persrc_rate6_entry *rate = rate_ptr.rate;\n"
                                 v6persrcratelimits.append((high_byte + 1) * 4096)
-                        first_action +=  "if (rate) {\n"
-                        first_action += f"\t{spin_lock}\n"
-                        first_action +=  "\tif (likely(rate->sent_rate > 0))" + " {\n"
-                        first_action +=  "\t\tint64_t diff = time - rate->sent_time;\n"
-                        # Unlikely or not, if the flow is slow, take a perf hit (though with the else if branch it doesn't matter)
-                        first_action +=  "\t\tif (unlikely(diff > 1000000000))\n"
-                        first_action +=  "\t\t\trate->sent_rate = 0;\n"
-                        first_action +=  "\t\telse if (likely(diff > 0))\n"
-                        first_action += f"\t\t\tallowed_since_last = ((uint64_t)diff) * {math.floor(value)} / 1000000000;\n"
-                        first_action +=  "\t}\n"
-                        first_action +=  "\tif (rate->sent_rate - ((int64_t)allowed_since_last) <= 0)" + " {\n"
                         if ty == "0x8006" or ty == "0x8306":
-                            first_action += "\t\trate->sent_rate = data_end - pktdata;\n"
+                            first_action += "uint64_t amt = data_end - pktdata;\n"
                         else:
-                            first_action += "\t\trate->sent_rate = 1;\n"
-                        first_action +=  "\t\trate->sent_time = time;\n"
-                        first_action += f"\t\t{spin_unlock}\n"
+                            first_action += "uint64_t amt = 1;\n"
+                        first_action +=  "if (rate) {\n"
+                        first_action += f"\t{spin_lock}\n"
+                        first_action +=  "\tint64_t bucket_pkts = (rate->sent_time & (~RATE_TIME_MASK)) >> (64 - RATE_BUCKET_BITS);\n"
+                        # We mask the top 12 bits, so date overflows every 52 days, handled below
+                        first_action +=  "\tint64_t time_diff = time - ((int64_t)(rate->sent_time & RATE_TIME_MASK));\n"
+                        first_action +=  "\tif (unlikely(time_diff < -1000000000 || time_diff > 16000000000)) {\n"
+                        first_action +=  "\t\tbucket_pkts = 0;\n"
                         first_action +=  "\t} else {\n"
+                        first_action +=  "\t\tif (unlikely(time_diff < 0)) { time_diff = 0; }\n"
+                        first_action += f"\t\tint64_t pkts_since_last = (time_diff << RATE_BUCKET_BITS) * amt / per_pkt_ns;\n"
+                        first_action +=  "\t\tbucket_pkts -= pkts_since_last;\n"
+                        first_action +=  "\t}\n"
+                        first_action +=  "\tif (bucket_pkts >= (((1 << RATE_BUCKET_INTEGER_BITS) - 1) << RATE_BUCKET_DECIMAL_BITS)) {\n"
                         first_action += f"\t\t{spin_unlock}\n"
                         first_action +=  "\t\t{stats_replace}\n"
                         first_action +=  "\t\treturn XDP_DROP;\n"
+                        first_action +=  "\t} else {\n"
+                        first_action +=  "\t\tif (unlikely(bucket_pkts < 0)) bucket_pkts = 0;\n"
+                        first_action += f"\t\trate->sent_time = time | ((bucket_pkts + (1 << RATE_BUCKET_DECIMAL_BITS)) << (64 - RATE_BUCKET_BITS));\n"
+                        first_action += f"\t\t{spin_unlock}\n"
                         first_action +=  "\t}\n"
                         first_action +=  "}\n"
                 elif ty == "0x8007":

diff --git a/xdp.c b/xdp.c
index 95ab7df9743b85e16d701f79463d989c69b0832c..6a8c19e4f852bad1e108093332043d0033f8e55b 100644 (file)
--- a/xdp.c
+++ b/xdp.c
@@ -177,11 +177,18 @@ struct {
        } \
 }
 
+// Rate limits are done in a static-sized leaky bucket with a decimal counter
+// Bucket size is always exactly (1 << RATE_BUCKET_INTEGER_BITS)
+#define RATE_BUCKET_DECIMAL_BITS 8
+#define RATE_BUCKET_INTEGER_BITS 4
+
+#define RATE_BUCKET_BITS (RATE_BUCKET_DECIMAL_BITS + RATE_BUCKET_INTEGER_BITS)
+#define RATE_TIME_MASK ((1ULL << (64 - RATE_BUCKET_BITS)) - 1)
+
 #ifdef RATE_CNT
 struct ratelimit {
        struct bpf_spin_lock lock;
-       int64_t sent_rate;
-       int64_t sent_time;
+       uint64_t sent_time;
 };
 struct {
        __uint(type, BPF_MAP_TYPE_ARRAY);
@@ -210,8 +217,7 @@ struct {
 
 #define CREATE_PERSRC_LOOKUP(IPV, IP_TYPE) \
 struct persrc_rate##IPV##_entry { \
-       int64_t sent_rate; \
-       int64_t sent_time; \
+       uint64_t sent_time; \
        IP_TYPE srcip; \
 }; \
  \
@@ -241,20 +247,19 @@ static inline struct persrc_rate##IPV##_ptr get_v##IPV##_persrc_ratelimit(IP_TYP
        bpf_spin_lock(&buckets->lock); \
  \
        int min_sent_idx = 0; \
-       int64_t min_sent_time = INT64_MAX; \
+       uint64_t min_sent_time = UINT64_MAX; \
        for (int i = 0; i < SRC_HASH_BUCKET_COUNT; i++) { \
                if (first_bucket[i].srcip == key) { \
                        res.rate = &first_bucket[i]; \
                        res.lock = &buckets->lock; \
                        return res; \
-               } else if (min_sent_time > first_bucket[i].sent_time) { \
-                       min_sent_time = first_bucket[i].sent_time; \
+               } else if (min_sent_time > (first_bucket[i].sent_time & RATE_TIME_MASK)) { \
+                       min_sent_time = first_bucket[i].sent_time & RATE_TIME_MASK; \
                        min_sent_idx = i; \
                } \
        } \
        res.rate = &first_bucket[min_sent_idx]; \
        res.rate->srcip = key; \
-       res.rate->sent_rate = 0; \
        res.rate->sent_time = 0; \
        res.lock = &buckets->lock; \
        return res; \