1 // SPDX-License-Identifier: GPL-2.0 2 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ 3 4 #include <stddef.h> 5 #include <stdbool.h> 6 #include <linux/bpf.h> 7 #include <linux/if_ether.h> 8 #include <linux/ip.h> 9 #include <linux/ipv6.h> 10 #include <linux/in.h> 11 #include <linux/tcp.h> 12 #include <linux/udp.h> 13 #include <bpf/bpf_helpers.h> 14 #include <bpf/bpf_endian.h> 15 #include "bpf_compiler.h" 16 #include "xdp_lb_bench_common.h" 17 #include "bench_bpf_timing.bpf.h" 18 19 #ifndef IPPROTO_FRAGMENT 20 #define IPPROTO_FRAGMENT 44 21 #endif 22 23 /* jhash helpers */ 24 25 static inline __u32 rol32(__u32 word, unsigned int shift) 26 { 27 return (word << shift) | (word >> ((-shift) & 31)); 28 } 29 30 #define __jhash_mix(a, b, c) \ 31 { \ 32 a -= c; a ^= rol32(c, 4); c += b; \ 33 b -= a; b ^= rol32(a, 6); a += c; \ 34 c -= b; c ^= rol32(b, 8); b += a; \ 35 a -= c; a ^= rol32(c, 16); c += b; \ 36 b -= a; b ^= rol32(a, 19); a += c; \ 37 c -= b; c ^= rol32(b, 4); b += a; \ 38 } 39 40 #define __jhash_final(a, b, c) \ 41 { \ 42 c ^= b; c -= rol32(b, 14); \ 43 a ^= c; a -= rol32(c, 11); \ 44 b ^= a; b -= rol32(a, 25); \ 45 c ^= b; c -= rol32(b, 16); \ 46 a ^= c; a -= rol32(c, 4); \ 47 b ^= a; b -= rol32(a, 14); \ 48 c ^= b; c -= rol32(b, 24); \ 49 } 50 51 #define JHASH_INITVAL 0xdeadbeef 52 53 static inline __u32 __jhash_nwords(__u32 a, __u32 b, __u32 c, __u32 initval) 54 { 55 a += initval; 56 b += initval; 57 c += initval; 58 __jhash_final(a, b, c); 59 return c; 60 } 61 62 static inline __u32 jhash_2words(__u32 a, __u32 b, __u32 initval) 63 { 64 return __jhash_nwords(a, b, 0, initval + JHASH_INITVAL + (2 << 2)); 65 } 66 67 static inline __u32 jhash2_4words(const __u32 *k, __u32 initval) 68 { 69 __u32 a, b, c; 70 71 a = b = c = JHASH_INITVAL + (4 << 2) + initval; 72 73 a += k[0]; b += k[1]; c += k[2]; 74 __jhash_mix(a, b, c); 75 76 a += k[3]; 77 __jhash_final(a, b, c); 78 79 return c; 80 } 81 82 static __always_inline void ipv4_csum(struct iphdr *iph) 83 { 84 __u16 *next_iph = (__u16 *)iph; 85 __u32 csum = 0; 86 int i; 87 88 __pragma_loop_unroll_full 89 for (i = 0; i < (int)(sizeof(*iph) >> 1); i++) 90 csum += *next_iph++; 91 92 csum = (csum & 0xffff) + (csum >> 16); 93 csum = (csum & 0xffff) + (csum >> 16); 94 iph->check = ~csum; 95 } 96 97 struct { 98 __uint(type, BPF_MAP_TYPE_HASH); 99 __uint(max_entries, 64); 100 __type(key, struct vip_definition); 101 __type(value, struct vip_meta); 102 } vip_map SEC(".maps"); 103 104 struct lru_inner_map { 105 __uint(type, BPF_MAP_TYPE_LRU_HASH); 106 __type(key, struct flow_key); 107 __type(value, struct real_pos_lru); 108 __uint(max_entries, DEFAULT_LRU_SIZE); 109 } lru_inner SEC(".maps"); 110 111 struct { 112 __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS); 113 __type(key, __u32); 114 __type(value, __u32); 115 __uint(max_entries, BENCH_NR_CPUS); 116 __array(values, struct lru_inner_map); 117 } lru_mapping SEC(".maps"); 118 119 struct { 120 __uint(type, BPF_MAP_TYPE_ARRAY); 121 __uint(max_entries, CH_RINGS_SIZE); 122 __type(key, __u32); 123 __type(value, __u32); 124 } ch_rings SEC(".maps"); 125 126 struct { 127 __uint(type, BPF_MAP_TYPE_ARRAY); 128 __uint(max_entries, MAX_REALS); 129 __type(key, __u32); 130 __type(value, struct real_definition); 131 } reals SEC(".maps"); 132 133 struct { 134 __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY); 135 __uint(max_entries, STATS_SIZE); 136 __type(key, __u32); 137 __type(value, struct lb_stats); 138 } stats SEC(".maps"); 139 140 struct { 141 __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY); 142 __uint(max_entries, MAX_REALS); 143 __type(key, __u32); 144 __type(value, struct lb_stats); 145 } reals_stats SEC(".maps"); 146 147 struct { 148 __uint(type, BPF_MAP_TYPE_ARRAY); 149 __uint(max_entries, 1); 150 __type(key, __u32); 151 __type(value, struct ctl_value); 152 } ctl_array SEC(".maps"); 153 154 struct { 155 __uint(type, BPF_MAP_TYPE_ARRAY); 156 __uint(max_entries, 1); 157 __type(key, __u32); 158 __type(value, struct vip_definition); 159 } vip_miss_stats SEC(".maps"); 160 161 struct { 162 __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY); 163 __uint(max_entries, MAX_REALS); 164 __type(key, __u32); 165 __type(value, __u32); 166 } lru_miss_stats SEC(".maps"); 167 168 volatile __u32 flow_mask; 169 volatile __u32 cold_lru; 170 __u32 batch_gen; 171 172 /* 173 * old_eth MUST be read BEFORE writing the outer header because 174 * bpf_xdp_adjust_head makes them overlap. 175 */ 176 static __always_inline int encap_v4(struct xdp_md *xdp, __be32 saddr, __be32 daddr, 177 __u16 payload_len, const __u8 *dst_mac) 178 { 179 struct ethhdr *new_eth, *old_eth; 180 void *data, *data_end; 181 struct iphdr *iph; 182 183 if (bpf_xdp_adjust_head(xdp, -(int)sizeof(struct iphdr))) 184 return -1; 185 186 data = (void *)(long)xdp->data; 187 data_end = (void *)(long)xdp->data_end; 188 189 new_eth = data; 190 iph = data + sizeof(struct ethhdr); 191 old_eth = data + sizeof(struct iphdr); 192 193 if (new_eth + 1 > data_end || old_eth + 1 > data_end || iph + 1 > data_end) 194 return -1; 195 196 __builtin_memcpy(new_eth->h_source, old_eth->h_dest, sizeof(new_eth->h_source)); 197 __builtin_memcpy(new_eth->h_dest, dst_mac, sizeof(new_eth->h_dest)); 198 new_eth->h_proto = bpf_htons(ETH_P_IP); 199 200 __builtin_memset(iph, 0, sizeof(*iph)); 201 iph->version = 4; 202 iph->ihl = sizeof(*iph) >> 2; 203 iph->protocol = IPPROTO_IPIP; 204 iph->tot_len = bpf_htons(payload_len + sizeof(*iph)); 205 iph->ttl = 64; 206 iph->saddr = saddr; 207 iph->daddr = daddr; 208 ipv4_csum(iph); 209 210 return 0; 211 } 212 213 static __always_inline int encap_v6(struct xdp_md *xdp, const __be32 saddr[4], 214 const __be32 daddr[4], __u8 nexthdr, __u16 payload_len, 215 const __u8 *dst_mac) 216 { 217 struct ethhdr *new_eth, *old_eth; 218 void *data, *data_end; 219 struct ipv6hdr *ip6h; 220 221 if (bpf_xdp_adjust_head(xdp, -(int)sizeof(struct ipv6hdr))) 222 return -1; 223 224 data = (void *)(long)xdp->data; 225 data_end = (void *)(long)xdp->data_end; 226 227 new_eth = data; 228 ip6h = data + sizeof(struct ethhdr); 229 old_eth = data + sizeof(struct ipv6hdr); 230 231 if (new_eth + 1 > data_end || old_eth + 1 > data_end || ip6h + 1 > data_end) 232 return -1; 233 234 __builtin_memcpy(new_eth->h_source, old_eth->h_dest, sizeof(new_eth->h_source)); 235 __builtin_memcpy(new_eth->h_dest, dst_mac, sizeof(new_eth->h_dest)); 236 new_eth->h_proto = bpf_htons(ETH_P_IPV6); 237 238 __builtin_memset(ip6h, 0, sizeof(*ip6h)); 239 ip6h->version = 6; 240 ip6h->nexthdr = nexthdr; 241 ip6h->payload_len = bpf_htons(payload_len); 242 ip6h->hop_limit = 64; 243 __builtin_memcpy(&ip6h->saddr, saddr, sizeof(ip6h->saddr)); 244 __builtin_memcpy(&ip6h->daddr, daddr, sizeof(ip6h->daddr)); 245 246 return 0; 247 } 248 249 static __always_inline void update_stats(void *map, __u32 key, __u16 bytes) 250 { 251 struct lb_stats *st = bpf_map_lookup_elem(map, &key); 252 253 if (st) { 254 st->v1 += 1; 255 st->v2 += bytes; 256 } 257 } 258 259 static __always_inline void count_action(int action) 260 { 261 struct lb_stats *st; 262 __u32 key; 263 264 if (action == XDP_TX) 265 key = STATS_XDP_TX; 266 else if (action == XDP_PASS) 267 key = STATS_XDP_PASS; 268 else 269 key = STATS_XDP_DROP; 270 271 st = bpf_map_lookup_elem(&stats, &key); 272 if (st) 273 st->v1 += 1; 274 } 275 276 static __always_inline bool is_under_flood(void) 277 { 278 __u32 key = STATS_NEW_CONN; 279 struct lb_stats *conn_st = bpf_map_lookup_elem(&stats, &key); 280 __u64 cur_time; 281 282 if (!conn_st) 283 return true; 284 285 cur_time = bpf_ktime_get_ns(); 286 if ((cur_time - conn_st->v2) > ONE_SEC) { 287 conn_st->v1 = 1; 288 conn_st->v2 = cur_time; 289 } else { 290 conn_st->v1 += 1; 291 if (conn_st->v1 > MAX_CONN_RATE) 292 return true; 293 } 294 return false; 295 } 296 297 static __always_inline struct real_definition *connection_table_lookup(void *lru_map, 298 struct flow_key *flow, 299 __u32 *out_pos) 300 { 301 struct real_pos_lru *dst_lru; 302 struct real_definition *real; 303 __u32 key; 304 305 dst_lru = bpf_map_lookup_elem(lru_map, flow); 306 if (!dst_lru) 307 return NULL; 308 309 /* UDP connections use atime-based timeout instead of FIN/RST */ 310 if (flow->proto == IPPROTO_UDP) { 311 __u64 cur_time = bpf_ktime_get_ns(); 312 313 if (cur_time - dst_lru->atime > LRU_UDP_TIMEOUT) 314 return NULL; 315 dst_lru->atime = cur_time; 316 } 317 318 key = dst_lru->pos; 319 *out_pos = key; 320 real = bpf_map_lookup_elem(&reals, &key); 321 return real; 322 } 323 324 static __always_inline bool get_packet_dst(struct real_definition **real, struct flow_key *flow, 325 struct vip_meta *vip_info, bool is_v6, void *lru_map, 326 bool is_rst, __u32 *out_pos) 327 { 328 bool under_flood; 329 __u32 hash, ch_key; 330 __u32 *ch_val; 331 __u32 real_pos; 332 333 under_flood = is_under_flood(); 334 335 if (is_v6) { 336 __u32 src_hash = jhash2_4words((__u32 *)flow->srcv6, MAX_VIPS); 337 338 hash = jhash_2words(src_hash, flow->ports, CH_RING_SIZE); 339 } else { 340 hash = jhash_2words(flow->src, flow->ports, CH_RING_SIZE); 341 } 342 343 ch_key = CH_RING_SIZE * vip_info->vip_num + hash % CH_RING_SIZE; 344 ch_val = bpf_map_lookup_elem(&ch_rings, &ch_key); 345 if (!ch_val) 346 return false; 347 real_pos = *ch_val; 348 349 *real = bpf_map_lookup_elem(&reals, &real_pos); 350 if (!(*real)) 351 return false; 352 353 if (!(vip_info->flags & F_LRU_BYPASS) && !under_flood && !is_rst) { 354 struct real_pos_lru new_lru = { .pos = real_pos }; 355 356 if (flow->proto == IPPROTO_UDP) 357 new_lru.atime = bpf_ktime_get_ns(); 358 bpf_map_update_elem(lru_map, flow, &new_lru, BPF_ANY); 359 } 360 361 *out_pos = real_pos; 362 return true; 363 } 364 365 static __always_inline void update_vip_lru_miss_stats(struct vip_definition *vip, bool is_v6, 366 __u32 real_idx) 367 { 368 struct vip_definition *miss_vip; 369 __u32 key = 0; 370 __u32 *cnt; 371 372 miss_vip = bpf_map_lookup_elem(&vip_miss_stats, &key); 373 if (!miss_vip) 374 return; 375 376 if (is_v6) { 377 if (miss_vip->vipv6[0] != vip->vipv6[0] || miss_vip->vipv6[1] != vip->vipv6[1] || 378 miss_vip->vipv6[2] != vip->vipv6[2] || miss_vip->vipv6[3] != vip->vipv6[3]) 379 return; 380 } else { 381 if (miss_vip->vip != vip->vip) 382 return; 383 } 384 385 if (miss_vip->port != vip->port || miss_vip->proto != vip->proto) 386 return; 387 388 cnt = bpf_map_lookup_elem(&lru_miss_stats, &real_idx); 389 if (cnt) 390 *cnt += 1; 391 } 392 393 static __noinline int process_packet(struct xdp_md *xdp) 394 { 395 void *data = (void *)(long)xdp->data; 396 void *data_end = (void *)(long)xdp->data_end; 397 struct ethhdr *eth = data; 398 struct real_definition *dst = NULL; 399 struct vip_definition vip_def = {}; 400 struct ctl_value *cval; 401 struct flow_key flow = {}; 402 struct vip_meta *vip_info; 403 struct lb_stats *data_stats; 404 struct udphdr *uh; 405 __be32 tnl_src[4]; 406 void *lru_map; 407 void *l4; 408 __u16 payload_len; 409 __u32 real_pos = 0, cpu_num, key; 410 __u8 proto; 411 int action = XDP_DROP; 412 bool is_v6, is_syn = false, is_rst = false; 413 414 if (eth + 1 > data_end) 415 goto out; 416 417 if (eth->h_proto == bpf_htons(ETH_P_IPV6)) { 418 is_v6 = true; 419 } else if (eth->h_proto == bpf_htons(ETH_P_IP)) { 420 is_v6 = false; 421 } else { 422 action = XDP_PASS; 423 goto out; 424 } 425 426 if (is_v6) { 427 struct ipv6hdr *ip6h = (void *)(eth + 1); 428 429 if (ip6h + 1 > data_end) 430 goto out; 431 if (ip6h->nexthdr == IPPROTO_FRAGMENT) 432 goto out; 433 434 payload_len = sizeof(struct ipv6hdr) + bpf_ntohs(ip6h->payload_len); 435 proto = ip6h->nexthdr; 436 437 __builtin_memcpy(flow.srcv6, &ip6h->saddr, sizeof(flow.srcv6)); 438 __builtin_memcpy(flow.dstv6, &ip6h->daddr, sizeof(flow.dstv6)); 439 __builtin_memcpy(vip_def.vipv6, &ip6h->daddr, sizeof(vip_def.vipv6)); 440 l4 = (void *)(ip6h + 1); 441 } else { 442 struct iphdr *iph = (void *)(eth + 1); 443 444 if (iph + 1 > data_end) 445 goto out; 446 if (iph->ihl != 5) 447 goto out; 448 if (iph->frag_off & bpf_htons(PCKT_FRAGMENTED)) 449 goto out; 450 451 payload_len = bpf_ntohs(iph->tot_len); 452 proto = iph->protocol; 453 454 flow.src = iph->saddr; 455 flow.dst = iph->daddr; 456 vip_def.vip = iph->daddr; 457 l4 = (void *)(iph + 1); 458 } 459 460 /* TCP and UDP share the same port layout at offset 0 */ 461 if (proto != IPPROTO_TCP && proto != IPPROTO_UDP) { 462 action = XDP_PASS; 463 goto out; 464 } 465 466 uh = l4; 467 if ((void *)(uh + 1) > data_end) 468 goto out; 469 flow.port16[0] = uh->source; 470 flow.port16[1] = uh->dest; 471 472 if (proto == IPPROTO_TCP) { 473 struct tcphdr *th = l4; 474 475 if ((void *)(th + 1) > data_end) 476 goto out; 477 is_syn = th->syn; 478 is_rst = th->rst; 479 } 480 481 flow.proto = proto; 482 vip_def.port = flow.port16[1]; 483 vip_def.proto = proto; 484 485 vip_info = bpf_map_lookup_elem(&vip_map, &vip_def); 486 if (!vip_info) { 487 action = XDP_PASS; 488 goto out; 489 } 490 491 key = STATS_LRU; 492 data_stats = bpf_map_lookup_elem(&stats, &key); 493 if (!data_stats) 494 goto out; 495 data_stats->v1 += 1; 496 497 cpu_num = bpf_get_smp_processor_id(); 498 lru_map = bpf_map_lookup_elem(&lru_mapping, &cpu_num); 499 if (!lru_map) 500 goto out; 501 502 if (!(vip_info->flags & F_LRU_BYPASS) && !is_syn) 503 dst = connection_table_lookup(lru_map, &flow, &real_pos); 504 505 if (!dst) { 506 if (flow.proto == IPPROTO_TCP) { 507 struct lb_stats *miss_st; 508 509 key = STATS_LRU_MISS; 510 miss_st = bpf_map_lookup_elem(&stats, &key); 511 if (miss_st) 512 miss_st->v1 += 1; 513 } 514 515 if (!get_packet_dst(&dst, &flow, vip_info, is_v6, lru_map, is_rst, &real_pos)) 516 goto out; 517 518 update_vip_lru_miss_stats(&vip_def, is_v6, real_pos); 519 data_stats->v2 += 1; 520 } 521 522 key = 0; 523 cval = bpf_map_lookup_elem(&ctl_array, &key); 524 if (!cval) 525 goto out; 526 527 update_stats(&stats, vip_info->vip_num, payload_len); 528 update_stats(&reals_stats, real_pos, payload_len); 529 530 if (is_v6) { 531 create_encap_ipv6_src(flow.port16[0], flow.srcv6[0], tnl_src); 532 if (encap_v6(xdp, tnl_src, dst->dstv6, IPPROTO_IPV6, payload_len, cval->mac)) 533 goto out; 534 } else if (dst->flags & F_IPV6) { 535 create_encap_ipv6_src(flow.port16[0], flow.src, tnl_src); 536 if (encap_v6(xdp, tnl_src, dst->dstv6, IPPROTO_IPIP, payload_len, cval->mac)) 537 goto out; 538 } else { 539 if (encap_v4(xdp, create_encap_ipv4_src(flow.port16[0], flow.src), dst->dst, 540 payload_len, cval->mac)) 541 goto out; 542 } 543 544 action = XDP_TX; 545 546 out: 547 count_action(action); 548 return action; 549 } 550 551 static __always_inline int strip_encap(struct xdp_md *xdp, const struct ethhdr *saved_eth) 552 { 553 void *data = (void *)(long)xdp->data; 554 void *data_end = (void *)(long)xdp->data_end; 555 struct ethhdr *eth = data; 556 int hdr_sz; 557 558 if (eth + 1 > data_end) 559 return -1; 560 561 hdr_sz = (eth->h_proto == bpf_htons(ETH_P_IPV6)) ? (int)sizeof(struct ipv6hdr) 562 : (int)sizeof(struct iphdr); 563 564 if (bpf_xdp_adjust_head(xdp, hdr_sz)) 565 return -1; 566 567 data = (void *)(long)xdp->data; 568 data_end = (void *)(long)xdp->data_end; 569 eth = data; 570 571 if (eth + 1 > data_end) 572 return -1; 573 574 __builtin_memcpy(eth, saved_eth, sizeof(*saved_eth)); 575 return 0; 576 } 577 578 static __always_inline void randomize_src(struct xdp_md *xdp, int saddr_off, __u32 *rand_state) 579 { 580 void *data = (void *)(long)xdp->data; 581 void *data_end = (void *)(long)xdp->data_end; 582 __u32 *saddr = data + saddr_off; 583 584 *rand_state ^= *rand_state << 13; 585 *rand_state ^= *rand_state >> 17; 586 *rand_state ^= *rand_state << 5; 587 588 if ((void *)(saddr + 1) <= data_end) 589 *saddr = *rand_state & flow_mask; 590 } 591 592 SEC("xdp") 593 int xdp_lb_bench(struct xdp_md *xdp) 594 { 595 void *data = (void *)(long)xdp->data; 596 void *data_end = (void *)(long)xdp->data_end; 597 struct ethhdr *eth = data; 598 struct ethhdr saved_eth; 599 __u32 rand_state = 0; 600 __u32 batch_hash = 0; 601 int saddr_off = 0; 602 bool is_v6; 603 604 if (eth + 1 > data_end) 605 return XDP_DROP; 606 607 __builtin_memcpy(&saved_eth, eth, sizeof(saved_eth)); 608 609 is_v6 = (saved_eth.h_proto == bpf_htons(ETH_P_IPV6)); 610 611 saddr_off = sizeof(struct ethhdr) + (is_v6 ? offsetof(struct ipv6hdr, saddr) : 612 offsetof(struct iphdr, saddr)); 613 614 if (flow_mask) 615 rand_state = bpf_get_prandom_u32() | 1; 616 617 if (cold_lru) { 618 __u32 *saddr = data + saddr_off; 619 620 batch_gen++; 621 batch_hash = (batch_gen + bpf_get_smp_processor_id()) * KNUTH_HASH_MULT; 622 if ((void *)(saddr + 1) <= data_end) 623 *saddr ^= batch_hash; 624 } 625 626 return BENCH_BPF_LOOP( 627 process_packet(xdp), 628 ({ 629 if (__bench_result == XDP_TX) { 630 if (strip_encap(xdp, &saved_eth)) 631 return XDP_DROP; 632 if (rand_state) 633 randomize_src(xdp, saddr_off, &rand_state); 634 } 635 if (cold_lru) { 636 void *d = (void *)(long)xdp->data; 637 void *de = (void *)(long)xdp->data_end; 638 __u32 *__sa = d + saddr_off; 639 640 if ((void *)(__sa + 1) <= de) 641 *__sa ^= batch_hash; 642 } 643 }) 644 ); 645 } 646 647 char _license[] SEC("license") = "GPL"; 648