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 29 struct tlpm_node { 30 struct tlpm_node *next; 31 size_t n_bits; 32 uint8_t key[]; 33 }; 34 35 static struct tlpm_node *tlpm_add(struct tlpm_node *list, 36 const uint8_t *key, 37 size_t n_bits) 38 { 39 struct tlpm_node *node; 40 size_t n; 41 42 /* add new entry with @key/@n_bits to @list and return new head */ 43 44 n = (n_bits + 7) / 8; 45 node = malloc(sizeof(*node) + n); 46 assert(node); 47 48 node->next = list; 49 node->n_bits = n_bits; 50 memcpy(node->key, key, n); 51 52 return node; 53 } 54 55 static void tlpm_clear(struct tlpm_node *list) 56 { 57 struct tlpm_node *node; 58 59 /* free all entries in @list */ 60 61 while ((node = list)) { 62 list = list->next; 63 free(node); 64 } 65 } 66 67 static struct tlpm_node *tlpm_match(struct tlpm_node *list, 68 const uint8_t *key, 69 size_t n_bits) 70 { 71 struct tlpm_node *best = NULL; 72 size_t i; 73 74 /* Perform longest prefix-match on @key/@n_bits. That is, iterate all 75 * entries and match each prefix against @key. Remember the "best" 76 * entry we find (i.e., the longest prefix that matches) and return it 77 * to the caller when done. 78 */ 79 80 for ( ; list; list = list->next) { 81 for (i = 0; i < n_bits && i < list->n_bits; ++i) { 82 if ((key[i / 8] & (1 << (7 - i % 8))) != 83 (list->key[i / 8] & (1 << (7 - i % 8)))) 84 break; 85 } 86 87 if (i >= list->n_bits) { 88 if (!best || i > best->n_bits) 89 best = list; 90 } 91 } 92 93 return best; 94 } 95 96 static void test_lpm_basic(void) 97 { 98 struct tlpm_node *list = NULL, *t1, *t2; 99 100 /* very basic, static tests to verify tlpm works as expected */ 101 102 assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8)); 103 104 t1 = list = tlpm_add(list, (uint8_t[]){ 0xff }, 8); 105 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8)); 106 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16)); 107 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0x00 }, 16)); 108 assert(!tlpm_match(list, (uint8_t[]){ 0x7f }, 8)); 109 assert(!tlpm_match(list, (uint8_t[]){ 0xfe }, 8)); 110 assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 7)); 111 112 t2 = list = tlpm_add(list, (uint8_t[]){ 0xff, 0xff }, 16); 113 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8)); 114 assert(t2 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16)); 115 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 15)); 116 assert(!tlpm_match(list, (uint8_t[]){ 0x7f, 0xff }, 16)); 117 118 tlpm_clear(list); 119 } 120 121 static void test_lpm_order(void) 122 { 123 struct tlpm_node *t1, *t2, *l1 = NULL, *l2 = NULL; 124 size_t i, j; 125 126 /* Verify the tlpm implementation works correctly regardless of the 127 * order of entries. Insert a random set of entries into @l1, and copy 128 * the same data in reverse order into @l2. Then verify a lookup of 129 * random keys will yield the same result in both sets. 130 */ 131 132 for (i = 0; i < (1 << 12); ++i) 133 l1 = tlpm_add(l1, (uint8_t[]){ 134 rand() % 0xff, 135 rand() % 0xff, 136 }, rand() % 16 + 1); 137 138 for (t1 = l1; t1; t1 = t1->next) 139 l2 = tlpm_add(l2, t1->key, t1->n_bits); 140 141 for (i = 0; i < (1 << 8); ++i) { 142 uint8_t key[] = { rand() % 0xff, rand() % 0xff }; 143 144 t1 = tlpm_match(l1, key, 16); 145 t2 = tlpm_match(l2, key, 16); 146 147 assert(!t1 == !t2); 148 if (t1) { 149 assert(t1->n_bits == t2->n_bits); 150 for (j = 0; j < t1->n_bits; ++j) 151 assert((t1->key[j / 8] & (1 << (7 - j % 8))) == 152 (t2->key[j / 8] & (1 << (7 - j % 8)))); 153 } 154 } 155 156 tlpm_clear(l1); 157 tlpm_clear(l2); 158 } 159 160 static void test_lpm_map(int keysize) 161 { 162 size_t i, j, n_matches, n_nodes, n_lookups; 163 struct tlpm_node *t, *list = NULL; 164 struct bpf_lpm_trie_key *key; 165 uint8_t *data, *value; 166 int r, map; 167 168 /* Compare behavior of tlpm vs. bpf-lpm. Create a randomized set of 169 * prefixes and insert it into both tlpm and bpf-lpm. Then run some 170 * randomized lookups and verify both maps return the same result. 171 */ 172 173 n_matches = 0; 174 n_nodes = 1 << 8; 175 n_lookups = 1 << 16; 176 177 data = alloca(keysize); 178 memset(data, 0, keysize); 179 180 value = alloca(keysize + 1); 181 memset(value, 0, keysize + 1); 182 183 key = alloca(sizeof(*key) + keysize); 184 memset(key, 0, sizeof(*key) + keysize); 185 186 map = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, 187 sizeof(*key) + keysize, 188 keysize + 1, 189 4096, 190 BPF_F_NO_PREALLOC); 191 assert(map >= 0); 192 193 for (i = 0; i < n_nodes; ++i) { 194 for (j = 0; j < keysize; ++j) 195 value[j] = rand() & 0xff; 196 value[keysize] = rand() % (8 * keysize + 1); 197 198 list = tlpm_add(list, value, value[keysize]); 199 200 key->prefixlen = value[keysize]; 201 memcpy(key->data, value, keysize); 202 r = bpf_map_update_elem(map, key, value, 0); 203 assert(!r); 204 } 205 206 for (i = 0; i < n_lookups; ++i) { 207 for (j = 0; j < keysize; ++j) 208 data[j] = rand() & 0xff; 209 210 t = tlpm_match(list, data, 8 * keysize); 211 212 key->prefixlen = 8 * keysize; 213 memcpy(key->data, data, keysize); 214 r = bpf_map_lookup_elem(map, key, value); 215 assert(!r || errno == ENOENT); 216 assert(!t == !!r); 217 218 if (t) { 219 ++n_matches; 220 assert(t->n_bits == value[keysize]); 221 for (j = 0; j < t->n_bits; ++j) 222 assert((t->key[j / 8] & (1 << (7 - j % 8))) == 223 (value[j / 8] & (1 << (7 - j % 8)))); 224 } 225 } 226 227 close(map); 228 tlpm_clear(list); 229 230 /* With 255 random nodes in the map, we are pretty likely to match 231 * something on every lookup. For statistics, use this: 232 * 233 * printf(" nodes: %zu\n" 234 * "lookups: %zu\n" 235 * "matches: %zu\n", n_nodes, n_lookups, n_matches); 236 */ 237 } 238 239 /* Test the implementation with some 'real world' examples */ 240 241 static void test_lpm_ipaddr(void) 242 { 243 struct bpf_lpm_trie_key *key_ipv4; 244 struct bpf_lpm_trie_key *key_ipv6; 245 size_t key_size_ipv4; 246 size_t key_size_ipv6; 247 int map_fd_ipv4; 248 int map_fd_ipv6; 249 __u64 value; 250 251 key_size_ipv4 = sizeof(*key_ipv4) + sizeof(__u32); 252 key_size_ipv6 = sizeof(*key_ipv6) + sizeof(__u32) * 4; 253 key_ipv4 = alloca(key_size_ipv4); 254 key_ipv6 = alloca(key_size_ipv6); 255 256 map_fd_ipv4 = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, 257 key_size_ipv4, sizeof(value), 258 100, BPF_F_NO_PREALLOC); 259 assert(map_fd_ipv4 >= 0); 260 261 map_fd_ipv6 = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, 262 key_size_ipv6, sizeof(value), 263 100, BPF_F_NO_PREALLOC); 264 assert(map_fd_ipv6 >= 0); 265 266 /* Fill data some IPv4 and IPv6 address ranges */ 267 value = 1; 268 key_ipv4->prefixlen = 16; 269 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); 270 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); 271 272 value = 2; 273 key_ipv4->prefixlen = 24; 274 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); 275 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); 276 277 value = 3; 278 key_ipv4->prefixlen = 24; 279 inet_pton(AF_INET, "192.168.128.0", key_ipv4->data); 280 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); 281 282 value = 5; 283 key_ipv4->prefixlen = 24; 284 inet_pton(AF_INET, "192.168.1.0", key_ipv4->data); 285 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); 286 287 value = 4; 288 key_ipv4->prefixlen = 23; 289 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); 290 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); 291 292 value = 0xdeadbeef; 293 key_ipv6->prefixlen = 64; 294 inet_pton(AF_INET6, "2a00:1450:4001:814::200e", key_ipv6->data); 295 assert(bpf_map_update_elem(map_fd_ipv6, key_ipv6, &value, 0) == 0); 296 297 /* Set tprefixlen to maximum for lookups */ 298 key_ipv4->prefixlen = 32; 299 key_ipv6->prefixlen = 128; 300 301 /* Test some lookups that should come back with a value */ 302 inet_pton(AF_INET, "192.168.128.23", key_ipv4->data); 303 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0); 304 assert(value == 3); 305 306 inet_pton(AF_INET, "192.168.0.1", key_ipv4->data); 307 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0); 308 assert(value == 2); 309 310 inet_pton(AF_INET6, "2a00:1450:4001:814::", key_ipv6->data); 311 assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0); 312 assert(value == 0xdeadbeef); 313 314 inet_pton(AF_INET6, "2a00:1450:4001:814::1", key_ipv6->data); 315 assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0); 316 assert(value == 0xdeadbeef); 317 318 /* Test some lookups that should not match any entry */ 319 inet_pton(AF_INET, "10.0.0.1", key_ipv4->data); 320 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -1 && 321 errno == ENOENT); 322 323 inet_pton(AF_INET, "11.11.11.11", key_ipv4->data); 324 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -1 && 325 errno == ENOENT); 326 327 inet_pton(AF_INET6, "2a00:ffff::", key_ipv6->data); 328 assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == -1 && 329 errno == ENOENT); 330 331 close(map_fd_ipv4); 332 close(map_fd_ipv6); 333 } 334 335 int main(void) 336 { 337 struct rlimit limit = { RLIM_INFINITY, RLIM_INFINITY }; 338 int i, ret; 339 340 /* we want predictable, pseudo random tests */ 341 srand(0xf00ba1); 342 343 /* allow unlimited locked memory */ 344 ret = setrlimit(RLIMIT_MEMLOCK, &limit); 345 if (ret < 0) 346 perror("Unable to lift memlock rlimit"); 347 348 test_lpm_basic(); 349 test_lpm_order(); 350 351 /* Test with 8, 16, 24, 32, ... 128 bit prefix length */ 352 for (i = 1; i <= 16; ++i) 353 test_lpm_map(i); 354 355 test_lpm_ipaddr(); 356 357 printf("test_lpm: OK\n"); 358 return 0; 359 } 360