1// SPDX-License-Identifier: GPL-2.0 2/* 3 * Randomized tests for eBPF longest-prefix-match maps 4 * 5 * This program runs randomized tests against the lpm-bpf-map. It implements a 6 * "Trivial Longest Prefix Match" (tlpm) based on simple, linear, singly linked 7 * lists. The implementation should be pretty straightforward. 8 * 9 * Based on tlpm, this inserts randomized data into bpf-lpm-maps and verifies 10 * the trie-based bpf-map implementation behaves the same way as tlpm. 11 */ 12 13#include <assert.h> 14#include <errno.h> 15#include <inttypes.h> 16#include <linux/bpf.h> 17#include <stdio.h> 18#include <stdlib.h> 19#include <string.h> 20#include <time.h> 21#include <unistd.h> 22#include <arpa/inet.h> 23#include <sys/time.h> 24#include <sys/resource.h> 25 26#include <bpf/bpf.h> 27#include "bpf_util.h" 28 29struct tlpm_node { 30 struct tlpm_node *next; 31 size_t n_bits; 32 uint8_t key[]; 33}; 34 35static struct tlpm_node *tlpm_match(struct tlpm_node *list, 36 const uint8_t *key, 37 size_t n_bits); 38 39static struct tlpm_node *tlpm_add(struct tlpm_node *list, 40 const uint8_t *key, 41 size_t n_bits) 42{ 43 struct tlpm_node *node; 44 size_t n; 45 46 n = (n_bits + 7) / 8; 47 48 /* 'overwrite' an equivalent entry if one already exists */ 49 node = tlpm_match(list, key, n_bits); 50 if (node && node->n_bits == n_bits) { 51 memcpy(node->key, key, n); 52 return list; 53 } 54 55 /* add new entry with @key/@n_bits to @list and return new head */ 56 57 node = malloc(sizeof(*node) + n); 58 assert(node); 59 60 node->next = list; 61 node->n_bits = n_bits; 62 memcpy(node->key, key, n); 63 64 return node; 65} 66 67static void tlpm_clear(struct tlpm_node *list) 68{ 69 struct tlpm_node *node; 70 71 /* free all entries in @list */ 72 73 while ((node = list)) { 74 list = list->next; 75 free(node); 76 } 77} 78 79static struct tlpm_node *tlpm_match(struct tlpm_node *list, 80 const uint8_t *key, 81 size_t n_bits) 82{ 83 struct tlpm_node *best = NULL; 84 size_t i; 85 86 /* Perform longest prefix-match on @key/@n_bits. That is, iterate all 87 * entries and match each prefix against @key. Remember the "best" 88 * entry we find (i.e., the longest prefix that matches) and return it 89 * to the caller when done. 90 */ 91 92 for ( ; list; list = list->next) { 93 for (i = 0; i < n_bits && i < list->n_bits; ++i) { 94 if ((key[i / 8] & (1 << (7 - i % 8))) != 95 (list->key[i / 8] & (1 << (7 - i % 8)))) 96 break; 97 } 98 99 if (i >= list->n_bits) { 100 if (!best || i > best->n_bits) 101 best = list; 102 } 103 } 104 105 return best; 106} 107 108static struct tlpm_node *tlpm_delete(struct tlpm_node *list, 109 const uint8_t *key, 110 size_t n_bits) 111{ 112 struct tlpm_node *best = tlpm_match(list, key, n_bits); 113 struct tlpm_node *node; 114 115 if (!best || best->n_bits != n_bits) 116 return list; 117 118 if (best == list) { 119 node = best->next; 120 free(best); 121 return node; 122 } 123 124 for (node = list; node; node = node->next) { 125 if (node->next == best) { 126 node->next = best->next; 127 free(best); 128 return list; 129 } 130 } 131 /* should never get here */ 132 assert(0); 133 return list; 134} 135 136static void test_lpm_basic(void) 137{ 138 struct tlpm_node *list = NULL, *t1, *t2; 139 140 /* very basic, static tests to verify tlpm works as expected */ 141 142 assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8)); 143 144 t1 = list = tlpm_add(list, (uint8_t[]){ 0xff }, 8); 145 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8)); 146 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16)); 147 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0x00 }, 16)); 148 assert(!tlpm_match(list, (uint8_t[]){ 0x7f }, 8)); 149 assert(!tlpm_match(list, (uint8_t[]){ 0xfe }, 8)); 150 assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 7)); 151 152 t2 = list = tlpm_add(list, (uint8_t[]){ 0xff, 0xff }, 16); 153 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8)); 154 assert(t2 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16)); 155 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 15)); 156 assert(!tlpm_match(list, (uint8_t[]){ 0x7f, 0xff }, 16)); 157 158 list = tlpm_delete(list, (uint8_t[]){ 0xff, 0xff }, 16); 159 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8)); 160 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16)); 161 162 list = tlpm_delete(list, (uint8_t[]){ 0xff }, 8); 163 assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8)); 164 165 tlpm_clear(list); 166} 167 168static void test_lpm_order(void) 169{ 170 struct tlpm_node *t1, *t2, *l1 = NULL, *l2 = NULL; 171 size_t i, j; 172 173 /* Verify the tlpm implementation works correctly regardless of the 174 * order of entries. Insert a random set of entries into @l1, and copy 175 * the same data in reverse order into @l2. Then verify a lookup of 176 * random keys will yield the same result in both sets. 177 */ 178 179 for (i = 0; i < (1 << 12); ++i) 180 l1 = tlpm_add(l1, (uint8_t[]){ 181 rand() % 0xff, 182 rand() % 0xff, 183 }, rand() % 16 + 1); 184 185 for (t1 = l1; t1; t1 = t1->next) 186 l2 = tlpm_add(l2, t1->key, t1->n_bits); 187 188 for (i = 0; i < (1 << 8); ++i) { 189 uint8_t key[] = { rand() % 0xff, rand() % 0xff }; 190 191 t1 = tlpm_match(l1, key, 16); 192 t2 = tlpm_match(l2, key, 16); 193 194 assert(!t1 == !t2); 195 if (t1) { 196 assert(t1->n_bits == t2->n_bits); 197 for (j = 0; j < t1->n_bits; ++j) 198 assert((t1->key[j / 8] & (1 << (7 - j % 8))) == 199 (t2->key[j / 8] & (1 << (7 - j % 8)))); 200 } 201 } 202 203 tlpm_clear(l1); 204 tlpm_clear(l2); 205} 206 207static void test_lpm_map(int keysize) 208{ 209 size_t i, j, n_matches, n_matches_after_delete, n_nodes, n_lookups; 210 struct tlpm_node *t, *list = NULL; 211 struct bpf_lpm_trie_key *key; 212 uint8_t *data, *value; 213 int r, map; 214 215 /* Compare behavior of tlpm vs. bpf-lpm. Create a randomized set of 216 * prefixes and insert it into both tlpm and bpf-lpm. Then run some 217 * randomized lookups and verify both maps return the same result. 218 */ 219 220 n_matches = 0; 221 n_matches_after_delete = 0; 222 n_nodes = 1 << 8; 223 n_lookups = 1 << 16; 224 225 data = alloca(keysize); 226 memset(data, 0, keysize); 227 228 value = alloca(keysize + 1); 229 memset(value, 0, keysize + 1); 230 231 key = alloca(sizeof(*key) + keysize); 232 memset(key, 0, sizeof(*key) + keysize); 233 234 map = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, 235 sizeof(*key) + keysize, 236 keysize + 1, 237 4096, 238 BPF_F_NO_PREALLOC); 239 assert(map >= 0); 240 241 for (i = 0; i < n_nodes; ++i) { 242 for (j = 0; j < keysize; ++j) 243 value[j] = rand() & 0xff; 244 value[keysize] = rand() % (8 * keysize + 1); 245 246 list = tlpm_add(list, value, value[keysize]); 247 248 key->prefixlen = value[keysize]; 249 memcpy(key->data, value, keysize); 250 r = bpf_map_update_elem(map, key, value, 0); 251 assert(!r); 252 } 253 254 for (i = 0; i < n_lookups; ++i) { 255 for (j = 0; j < keysize; ++j) 256 data[j] = rand() & 0xff; 257 258 t = tlpm_match(list, data, 8 * keysize); 259 260 key->prefixlen = 8 * keysize; 261 memcpy(key->data, data, keysize); 262 r = bpf_map_lookup_elem(map, key, value); 263 assert(!r || errno == ENOENT); 264 assert(!t == !!r); 265 266 if (t) { 267 ++n_matches; 268 assert(t->n_bits == value[keysize]); 269 for (j = 0; j < t->n_bits; ++j) 270 assert((t->key[j / 8] & (1 << (7 - j % 8))) == 271 (value[j / 8] & (1 << (7 - j % 8)))); 272 } 273 } 274 275 /* Remove the first half of the elements in the tlpm and the 276 * corresponding nodes from the bpf-lpm. Then run the same 277 * large number of random lookups in both and make sure they match. 278 * Note: we need to count the number of nodes actually inserted 279 * since there may have been duplicates. 280 */ 281 for (i = 0, t = list; t; i++, t = t->next) 282 ; 283 for (j = 0; j < i / 2; ++j) { 284 key->prefixlen = list->n_bits; 285 memcpy(key->data, list->key, keysize); 286 r = bpf_map_delete_elem(map, key); 287 assert(!r); 288 list = tlpm_delete(list, list->key, list->n_bits); 289 assert(list); 290 } 291 for (i = 0; i < n_lookups; ++i) { 292 for (j = 0; j < keysize; ++j) 293 data[j] = rand() & 0xff; 294 295 t = tlpm_match(list, data, 8 * keysize); 296 297 key->prefixlen = 8 * keysize; 298 memcpy(key->data, data, keysize); 299 r = bpf_map_lookup_elem(map, key, value); 300 assert(!r || errno == ENOENT); 301 assert(!t == !!r); 302 303 if (t) { 304 ++n_matches_after_delete; 305 assert(t->n_bits == value[keysize]); 306 for (j = 0; j < t->n_bits; ++j) 307 assert((t->key[j / 8] & (1 << (7 - j % 8))) == 308 (value[j / 8] & (1 << (7 - j % 8)))); 309 } 310 } 311 312 close(map); 313 tlpm_clear(list); 314 315 /* With 255 random nodes in the map, we are pretty likely to match 316 * something on every lookup. For statistics, use this: 317 * 318 * printf(" nodes: %zu\n" 319 * " lookups: %zu\n" 320 * " matches: %zu\n" 321 * "matches(delete): %zu\n", 322 * n_nodes, n_lookups, n_matches, n_matches_after_delete); 323 */ 324} 325 326/* Test the implementation with some 'real world' examples */ 327 328static void test_lpm_ipaddr(void) 329{ 330 struct bpf_lpm_trie_key *key_ipv4; 331 struct bpf_lpm_trie_key *key_ipv6; 332 size_t key_size_ipv4; 333 size_t key_size_ipv6; 334 int map_fd_ipv4; 335 int map_fd_ipv6; 336 __u64 value; 337 338 key_size_ipv4 = sizeof(*key_ipv4) + sizeof(__u32); 339 key_size_ipv6 = sizeof(*key_ipv6) + sizeof(__u32) * 4; 340 key_ipv4 = alloca(key_size_ipv4); 341 key_ipv6 = alloca(key_size_ipv6); 342 343 map_fd_ipv4 = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, 344 key_size_ipv4, sizeof(value), 345 100, BPF_F_NO_PREALLOC); 346 assert(map_fd_ipv4 >= 0); 347 348 map_fd_ipv6 = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, 349 key_size_ipv6, sizeof(value), 350 100, BPF_F_NO_PREALLOC); 351 assert(map_fd_ipv6 >= 0); 352 353 /* Fill data some IPv4 and IPv6 address ranges */ 354 value = 1; 355 key_ipv4->prefixlen = 16; 356 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); 357 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); 358 359 value = 2; 360 key_ipv4->prefixlen = 24; 361 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); 362 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); 363 364 value = 3; 365 key_ipv4->prefixlen = 24; 366 inet_pton(AF_INET, "192.168.128.0", key_ipv4->data); 367 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); 368 369 value = 5; 370 key_ipv4->prefixlen = 24; 371 inet_pton(AF_INET, "192.168.1.0", key_ipv4->data); 372 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); 373 374 value = 4; 375 key_ipv4->prefixlen = 23; 376 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); 377 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); 378 379 value = 0xdeadbeef; 380 key_ipv6->prefixlen = 64; 381 inet_pton(AF_INET6, "2a00:1450:4001:814::200e", key_ipv6->data); 382 assert(bpf_map_update_elem(map_fd_ipv6, key_ipv6, &value, 0) == 0); 383 384 /* Set tprefixlen to maximum for lookups */ 385 key_ipv4->prefixlen = 32; 386 key_ipv6->prefixlen = 128; 387 388 /* Test some lookups that should come back with a value */ 389 inet_pton(AF_INET, "192.168.128.23", key_ipv4->data); 390 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0); 391 assert(value == 3); 392 393 inet_pton(AF_INET, "192.168.0.1", key_ipv4->data); 394 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0); 395 assert(value == 2); 396 397 inet_pton(AF_INET6, "2a00:1450:4001:814::", key_ipv6->data); 398 assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0); 399 assert(value == 0xdeadbeef); 400 401 inet_pton(AF_INET6, "2a00:1450:4001:814::1", key_ipv6->data); 402 assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0); 403 assert(value == 0xdeadbeef); 404 405 /* Test some lookups that should not match any entry */ 406 inet_pton(AF_INET, "10.0.0.1", key_ipv4->data); 407 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -1 && 408 errno == ENOENT); 409 410 inet_pton(AF_INET, "11.11.11.11", key_ipv4->data); 411 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -1 && 412 errno == ENOENT); 413 414 inet_pton(AF_INET6, "2a00:ffff::", key_ipv6->data); 415 assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == -1 && 416 errno == ENOENT); 417 418 close(map_fd_ipv4); 419 close(map_fd_ipv6); 420} 421 422static void test_lpm_delete(void) 423{ 424 struct bpf_lpm_trie_key *key; 425 size_t key_size; 426 int map_fd; 427 __u64 value; 428 429 key_size = sizeof(*key) + sizeof(__u32); 430 key = alloca(key_size); 431 432 map_fd = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, 433 key_size, sizeof(value), 434 100, BPF_F_NO_PREALLOC); 435 assert(map_fd >= 0); 436 437 /* Add nodes: 438 * 192.168.0.0/16 (1) 439 * 192.168.0.0/24 (2) 440 * 192.168.128.0/24 (3) 441 * 192.168.1.0/24 (4) 442 * 443 * (1) 444 * / \ 445 * (IM) (3) 446 * / \ 447 * (2) (4) 448 */ 449 value = 1; 450 key->prefixlen = 16; 451 inet_pton(AF_INET, "192.168.0.0", key->data); 452 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); 453 454 value = 2; 455 key->prefixlen = 24; 456 inet_pton(AF_INET, "192.168.0.0", key->data); 457 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); 458 459 value = 3; 460 key->prefixlen = 24; 461 inet_pton(AF_INET, "192.168.128.0", key->data); 462 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); 463 464 value = 4; 465 key->prefixlen = 24; 466 inet_pton(AF_INET, "192.168.1.0", key->data); 467 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); 468 469 /* remove non-existent node */ 470 key->prefixlen = 32; 471 inet_pton(AF_INET, "10.0.0.1", key->data); 472 assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 && 473 errno == ENOENT); 474 475 /* assert initial lookup */ 476 key->prefixlen = 32; 477 inet_pton(AF_INET, "192.168.0.1", key->data); 478 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); 479 assert(value == 2); 480 481 /* remove leaf node */ 482 key->prefixlen = 24; 483 inet_pton(AF_INET, "192.168.0.0", key->data); 484 assert(bpf_map_delete_elem(map_fd, key) == 0); 485 486 key->prefixlen = 32; 487 inet_pton(AF_INET, "192.168.0.1", key->data); 488 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); 489 assert(value == 1); 490 491 /* remove leaf (and intermediary) node */ 492 key->prefixlen = 24; 493 inet_pton(AF_INET, "192.168.1.0", key->data); 494 assert(bpf_map_delete_elem(map_fd, key) == 0); 495 496 key->prefixlen = 32; 497 inet_pton(AF_INET, "192.168.1.1", key->data); 498 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); 499 assert(value == 1); 500 501 /* remove root node */ 502 key->prefixlen = 16; 503 inet_pton(AF_INET, "192.168.0.0", key->data); 504 assert(bpf_map_delete_elem(map_fd, key) == 0); 505 506 key->prefixlen = 32; 507 inet_pton(AF_INET, "192.168.128.1", key->data); 508 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); 509 assert(value == 3); 510 511 /* remove last node */ 512 key->prefixlen = 24; 513 inet_pton(AF_INET, "192.168.128.0", key->data); 514 assert(bpf_map_delete_elem(map_fd, key) == 0); 515 516 key->prefixlen = 32; 517 inet_pton(AF_INET, "192.168.128.1", key->data); 518 assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 && 519 errno == ENOENT); 520 521 close(map_fd); 522} 523 524int main(void) 525{ 526 struct rlimit limit = { RLIM_INFINITY, RLIM_INFINITY }; 527 int i, ret; 528 529 /* we want predictable, pseudo random tests */ 530 srand(0xf00ba1); 531 532 /* allow unlimited locked memory */ 533 ret = setrlimit(RLIMIT_MEMLOCK, &limit); 534 if (ret < 0) 535 perror("Unable to lift memlock rlimit"); 536 537 test_lpm_basic(); 538 test_lpm_order(); 539 540 /* Test with 8, 16, 24, 32, ... 128 bit prefix length */ 541 for (i = 1; i <= 16; ++i) 542 test_lpm_map(i); 543 544 test_lpm_ipaddr(); 545 546 test_lpm_delete(); 547 548 printf("test_lpm: OK\n"); 549 return 0; 550} 551