1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3 * 4 * Copyright (c) 2020 Alexander V. Chernikov 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 */ 27 28 #include <sys/cdefs.h> 29 __FBSDID("$FreeBSD$"); 30 #include "opt_inet.h" 31 #include "opt_inet6.h" 32 33 #include <sys/param.h> 34 #include <sys/kernel.h> 35 #include <sys/lock.h> 36 #include <sys/rmlock.h> 37 #include <sys/malloc.h> 38 #include <sys/module.h> 39 #include <sys/kernel.h> 40 #include <sys/socket.h> 41 #include <sys/sysctl.h> 42 #include <net/vnet.h> 43 44 #include <net/if.h> 45 #include <net/if_var.h> 46 47 #include <netinet/in.h> 48 #include <netinet/in_fib.h> 49 #include <netinet/ip.h> 50 51 #include <netinet6/in6_fib.h> 52 53 #include <net/route.h> 54 #include <net/route/nhop.h> 55 #include <net/route/route_ctl.h> 56 #include <net/route/route_var.h> 57 #include <net/route/fib_algo.h> 58 59 #define CHUNK_SIZE 10000 60 61 VNET_DEFINE_STATIC(struct in_addr *, inet_addr_list); 62 #define V_inet_addr_list VNET(inet_addr_list) 63 VNET_DEFINE_STATIC(int, inet_list_size); 64 #define V_inet_list_size VNET(inet_list_size) 65 66 VNET_DEFINE_STATIC(struct in6_addr *, inet6_addr_list); 67 #define V_inet6_addr_list VNET(inet6_addr_list) 68 VNET_DEFINE_STATIC(int, inet6_list_size); 69 #define V_inet6_list_size VNET(inet6_list_size) 70 71 SYSCTL_DECL(_net_route); 72 SYSCTL_NODE(_net_route, OID_AUTO, test, CTLFLAG_RW | CTLFLAG_MPSAFE, 0, 73 "Route algorithm lookups"); 74 75 static int 76 add_addr(int family, char *addr_str) 77 { 78 79 if (family == AF_INET) { 80 struct in_addr *paddr_old = V_inet_addr_list; 81 int size_old = V_inet_list_size; 82 struct in_addr addr; 83 84 if (inet_pton(AF_INET, addr_str, &addr) != 1) 85 return (EINVAL); 86 87 struct in_addr *paddr = mallocarray(size_old + 1, 88 sizeof(struct in_addr), M_TEMP, M_ZERO | M_WAITOK); 89 90 if (paddr_old != NULL) { 91 memcpy(paddr, paddr_old, size_old * sizeof(struct in_addr)); 92 free(paddr_old, M_TEMP); 93 } 94 paddr[size_old] = addr; 95 96 V_inet_addr_list = paddr; 97 V_inet_list_size = size_old + 1; 98 inet_ntop(AF_INET, &addr, addr_str, sizeof(addr_str)); 99 } else if (family == AF_INET6) { 100 struct in6_addr *paddr_old = V_inet6_addr_list; 101 int size_old = V_inet6_list_size; 102 struct in6_addr addr6; 103 104 if (inet_pton(AF_INET6, addr_str, &addr6) != 1) 105 return (EINVAL); 106 107 struct in6_addr *paddr = mallocarray(size_old + 1, 108 sizeof(struct in6_addr), M_TEMP, M_ZERO | M_WAITOK); 109 110 if (paddr_old != NULL) { 111 memcpy(paddr, paddr_old, size_old * sizeof(struct in6_addr)); 112 free(paddr_old, M_TEMP); 113 } 114 paddr[size_old] = addr6; 115 116 V_inet6_addr_list = paddr; 117 V_inet6_list_size = size_old + 1; 118 inet_ntop(AF_INET6, &addr6, addr_str, sizeof(addr_str)); 119 } 120 121 return (0); 122 } 123 124 static int 125 add_addr_sysctl_handler(struct sysctl_oid *oidp, struct sysctl_req *req, int family) 126 { 127 char addr_str[INET6_ADDRSTRLEN]; 128 int error; 129 130 bzero(addr_str, sizeof(addr_str)); 131 132 error = sysctl_handle_string(oidp, addr_str, sizeof(addr_str), req); 133 if (error != 0 || req->newptr == NULL) 134 return (error); 135 136 error = add_addr(family, addr_str); 137 138 return (0); 139 } 140 141 static int 142 add_inet_addr_sysctl_handler(SYSCTL_HANDLER_ARGS) 143 { 144 145 return (add_addr_sysctl_handler(oidp, req, AF_INET)); 146 } 147 SYSCTL_PROC(_net_route_test, OID_AUTO, add_inet_addr, 148 CTLTYPE_STRING | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0, 149 add_inet_addr_sysctl_handler, "A", "Set"); 150 151 static int 152 add_inet6_addr_sysctl_handler(SYSCTL_HANDLER_ARGS) 153 { 154 155 return (add_addr_sysctl_handler(oidp, req, AF_INET6)); 156 } 157 SYSCTL_PROC(_net_route_test, OID_AUTO, add_inet6_addr, 158 CTLTYPE_STRING | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0, 159 add_inet6_addr_sysctl_handler, "A", "Set"); 160 161 static uint64_t 162 run_test_inet_one_pass() 163 { 164 /* Assume epoch */ 165 int sz = V_inet_list_size; 166 int tries = CHUNK_SIZE / sz; 167 const struct in_addr *a = V_inet_addr_list; 168 uint64_t count = 0; 169 170 for (int pass = 0; pass < tries; pass++) { 171 for (int i = 0; i < sz; i++) { 172 fib4_lookup(RT_DEFAULT_FIB, a[i], 0, NHR_NONE, 0); 173 count++; 174 } 175 } 176 return (count); 177 } 178 179 static int 180 run_test_inet(SYSCTL_HANDLER_ARGS) 181 { 182 struct epoch_tracker et; 183 184 int count = 0; 185 int error = sysctl_handle_int(oidp, &count, 0, req); 186 if (error != 0) 187 return (error); 188 189 if (count == 0) 190 return (0); 191 192 if (V_inet_list_size <= 0) 193 return (ENOENT); 194 195 printf("run: %d packets vnet %p\n", count, curvnet); 196 if (count < CHUNK_SIZE) 197 count = CHUNK_SIZE; 198 199 struct timespec ts_pre, ts_post; 200 int64_t pass_diff, total_diff = 0; 201 uint64_t pass_packets, total_packets = 0; 202 203 for (int pass = 0; pass < count / CHUNK_SIZE; pass++) { 204 NET_EPOCH_ENTER(et); 205 nanouptime(&ts_pre); 206 pass_packets = run_test_inet_one_pass(); 207 nanouptime(&ts_post); 208 NET_EPOCH_EXIT(et); 209 210 pass_diff = (ts_post.tv_sec - ts_pre.tv_sec) * 1000000000 + 211 (ts_post.tv_nsec - ts_pre.tv_nsec); 212 total_diff += pass_diff; 213 total_packets += pass_packets; 214 } 215 216 printf("%zu packets in %zu nanoseconds, %zu pps\n", 217 total_packets, total_diff, total_packets * 1000000000 / total_diff); 218 219 return (0); 220 } 221 SYSCTL_PROC(_net_route_test, OID_AUTO, run_inet, 222 CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE, 223 0, 0, run_test_inet, "I", "Execute fib4_lookup test"); 224 225 static uint64_t 226 run_test_inet6_one_pass() 227 { 228 /* Assume epoch */ 229 int sz = V_inet6_list_size; 230 int tries = CHUNK_SIZE / sz; 231 const struct in6_addr *a = V_inet6_addr_list; 232 uint64_t count = 0; 233 234 for (int pass = 0; pass < tries; pass++) { 235 for (int i = 0; i < sz; i++) { 236 fib6_lookup(RT_DEFAULT_FIB, &a[i], 0, NHR_NONE, 0); 237 count++; 238 } 239 } 240 return (count); 241 } 242 243 static int 244 run_test_inet6(SYSCTL_HANDLER_ARGS) 245 { 246 struct epoch_tracker et; 247 248 int count = 0; 249 int error = sysctl_handle_int(oidp, &count, 0, req); 250 if (error != 0) 251 return (error); 252 253 if (count == 0) 254 return (0); 255 256 if (V_inet6_list_size <= 0) 257 return (ENOENT); 258 259 printf("run: %d packets vnet %p\n", count, curvnet); 260 if (count < CHUNK_SIZE) 261 count = CHUNK_SIZE; 262 263 struct timespec ts_pre, ts_post; 264 int64_t pass_diff, total_diff = 0; 265 uint64_t pass_packets, total_packets = 0; 266 267 for (int pass = 0; pass < count / CHUNK_SIZE; pass++) { 268 NET_EPOCH_ENTER(et); 269 nanouptime(&ts_pre); 270 pass_packets = run_test_inet6_one_pass(); 271 nanouptime(&ts_post); 272 NET_EPOCH_EXIT(et); 273 274 pass_diff = (ts_post.tv_sec - ts_pre.tv_sec) * 1000000000 + 275 (ts_post.tv_nsec - ts_pre.tv_nsec); 276 total_diff += pass_diff; 277 total_packets += pass_packets; 278 } 279 280 printf("%zu packets in %zu nanoseconds, %zu pps\n", 281 total_packets, total_diff, total_packets * 1000000000 / total_diff); 282 283 return (0); 284 } 285 SYSCTL_PROC(_net_route_test, OID_AUTO, run_inet6, 286 CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE, 287 0, 0, run_test_inet6, "I", "Execute fib6_lookup test"); 288 289 static bool 290 cmp_dst(uint32_t fibnum, struct in_addr a) 291 { 292 struct nhop_object *nh_fib; 293 struct rtentry *rt; 294 struct route_nhop_data rnd = {}; 295 296 nh_fib = fib4_lookup(fibnum, a, 0, NHR_NONE, 0); 297 rt = fib4_lookup_rt(fibnum, a, 0, NHR_NONE, &rnd); 298 299 if (nh_fib == NULL && rt == NULL) { 300 return (true); 301 } else if (nh_fib == nhop_select(rnd.rnd_nhop, 0)) { 302 return (true); 303 } 304 305 struct in_addr dst; 306 int plen; 307 uint32_t scopeid; 308 char key_str[INET_ADDRSTRLEN], dst_str[INET_ADDRSTRLEN]; 309 310 inet_ntop(AF_INET, &a, key_str, sizeof(key_str)); 311 if (rnd.rnd_nhop == NULL) { 312 printf("[RT BUG] lookup for %s: RIB: ENOENT FIB: nh=%u\n", 313 key_str, nhop_get_idx(nh_fib)); 314 } else { 315 rt_get_inet_prefix_plen(rt, &dst, &plen, &scopeid); 316 inet_ntop(AF_INET, &dst, dst_str, sizeof(dst_str)); 317 printf("[RT BUG] lookup for %s: RIB: %s/%d,nh=%u FIB: nh=%u\n", 318 key_str, dst_str, plen, 319 nhop_get_idx(nhop_select(rnd.rnd_nhop, 0)), 320 nhop_get_idx(nh_fib)); 321 } 322 323 return (false); 324 } 325 326 /* Random lookups: correctness verification */ 327 static uint64_t 328 run_test_inet_one_pass_random() 329 { 330 /* Assume epoch */ 331 struct in_addr a[64]; 332 int sz = 64; 333 uint64_t count = 0; 334 335 for (int pass = 0; pass < CHUNK_SIZE / sz; pass++) { 336 arc4random_buf(a, sizeof(a)); 337 for (int i = 0; i < sz; i++) { 338 if (!cmp_dst(RT_DEFAULT_FIB, a[i])) 339 return (0); 340 count++; 341 } 342 } 343 return (count); 344 } 345 346 static int 347 run_test_inet_random(SYSCTL_HANDLER_ARGS) 348 { 349 struct epoch_tracker et; 350 351 int count = 0; 352 int error = sysctl_handle_int(oidp, &count, 0, req); 353 if (error != 0) 354 return (error); 355 356 if (count == 0) 357 return (0); 358 359 if (count < CHUNK_SIZE) 360 count = CHUNK_SIZE; 361 362 struct timespec ts_pre, ts_post; 363 int64_t pass_diff, total_diff = 1; 364 uint64_t pass_packets, total_packets = 0; 365 366 for (int pass = 0; pass < count / CHUNK_SIZE; pass++) { 367 NET_EPOCH_ENTER(et); 368 nanouptime(&ts_pre); 369 pass_packets = run_test_inet_one_pass_random(); 370 nanouptime(&ts_post); 371 NET_EPOCH_EXIT(et); 372 373 pass_diff = (ts_post.tv_sec - ts_pre.tv_sec) * 1000000000 + 374 (ts_post.tv_nsec - ts_pre.tv_nsec); 375 total_diff += pass_diff; 376 total_packets += pass_packets; 377 378 if (pass_packets == 0) 379 break; 380 } 381 382 /* Signal error to userland */ 383 if (pass_packets == 0) 384 return (EINVAL); 385 386 printf("%zu packets in %zu nanoseconds, %zu pps\n", 387 total_packets, total_diff, total_packets * 1000000000 / total_diff); 388 389 return (0); 390 } 391 SYSCTL_PROC(_net_route_test, OID_AUTO, run_inet_random, 392 CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE, 393 0, 0, run_test_inet_random, "I", "Execute fib4_lookup random check tests"); 394 395 396 struct inet_array { 397 uint32_t alloc_items; 398 uint32_t num_items; 399 struct in_addr *arr; 400 int error; 401 }; 402 403 /* 404 * For each prefix, add the following records to the lookup array: 405 * * prefix-1, prefix, prefix + 1, prefix_end, prefix_end + 1 406 */ 407 static int 408 add_prefix(struct rtentry *rt, void *_data) 409 { 410 struct inet_array *pa = (struct inet_array *)_data; 411 struct in_addr addr; 412 int plen; 413 uint32_t scopeid, haddr; 414 415 if (pa->num_items + 5 >= pa->alloc_items) { 416 if (pa->error == 0) 417 pa->error = EINVAL; 418 return (0); 419 } 420 421 rt_get_inet_prefix_plen(rt, &addr, &plen, &scopeid); 422 423 pa->arr[pa->num_items++] = addr; 424 haddr = ntohl(addr.s_addr); 425 if (haddr > 0) { 426 pa->arr[pa->num_items++].s_addr = htonl(haddr - 1); 427 pa->arr[pa->num_items++].s_addr = htonl(haddr + 1); 428 /* assume mask != 0 */ 429 uint32_t mlen = (1 << (32 - plen)) - 1; 430 pa->arr[pa->num_items++].s_addr = htonl(haddr + mlen); 431 /* can overflow, but who cares */ 432 pa->arr[pa->num_items++].s_addr = htonl(haddr + mlen + 1); 433 } 434 435 return (0); 436 } 437 438 static bool 439 prepare_list(uint32_t fibnum, struct inet_array *pa) 440 { 441 struct rib_head *rh; 442 443 rh = rt_tables_get_rnh(fibnum, AF_INET); 444 445 uint32_t num_prefixes = (rh->rnh_prefixes + 10) * 5; 446 bzero(pa, sizeof(struct inet_array)); 447 pa->alloc_items = num_prefixes; 448 pa->arr = mallocarray(num_prefixes, sizeof(struct in_addr), 449 M_TEMP, M_ZERO | M_WAITOK); 450 451 rib_walk(RT_DEFAULT_FIB, AF_INET, false, add_prefix, pa); 452 453 return (pa->error == 0); 454 } 455 456 static int 457 run_test_inet_scan(SYSCTL_HANDLER_ARGS) 458 { 459 struct epoch_tracker et; 460 461 int count = 0; 462 int error = sysctl_handle_int(oidp, &count, 0, req); 463 if (error != 0) 464 return (error); 465 466 if (count == 0) 467 return (0); 468 469 struct inet_array pa = {}; 470 471 if (!prepare_list(RT_DEFAULT_FIB, &pa)) 472 return (pa.error); 473 474 struct timespec ts_pre, ts_post; 475 int64_t total_diff = 1; 476 uint64_t total_packets = 0; 477 478 NET_EPOCH_ENTER(et); 479 nanouptime(&ts_pre); 480 for (int i = 0; i < pa.num_items; i++) { 481 if (!cmp_dst(RT_DEFAULT_FIB, pa.arr[i])) { 482 error = EINVAL; 483 break; 484 } 485 total_packets++; 486 } 487 nanouptime(&ts_post); 488 NET_EPOCH_EXIT(et); 489 490 if (pa.arr != NULL) 491 free(pa.arr, M_TEMP); 492 493 /* Signal error to userland */ 494 if (error != 0) 495 return (error); 496 497 total_diff = (ts_post.tv_sec - ts_pre.tv_sec) * 1000000000 + 498 (ts_post.tv_nsec - ts_pre.tv_nsec); 499 printf("%zu packets in %zu nanoseconds, %zu pps\n", 500 total_packets, total_diff, total_packets * 1000000000 / total_diff); 501 502 return (0); 503 } 504 SYSCTL_PROC(_net_route_test, OID_AUTO, run_inet_scan, 505 CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE, 506 0, 0, run_test_inet_scan, "I", "Execute fib4_lookup scan tests"); 507 508 509 static int 510 test_fib_lookup_modevent(module_t mod, int type, void *unused) 511 { 512 int error = 0; 513 514 switch (type) { 515 case MOD_LOAD: 516 break; 517 case MOD_UNLOAD: 518 if (V_inet_addr_list != NULL) 519 free(V_inet_addr_list, M_TEMP); 520 if (V_inet6_addr_list != NULL) 521 free(V_inet6_addr_list, M_TEMP); 522 break; 523 default: 524 error = EOPNOTSUPP; 525 break; 526 } 527 return (error); 528 } 529 530 static moduledata_t testfiblookupmod = { 531 "test_fib_lookup", 532 test_fib_lookup_modevent, 533 0 534 }; 535 536 DECLARE_MODULE(testfiblookupmod, testfiblookupmod, SI_SUB_PSEUDO, SI_ORDER_ANY); 537 MODULE_VERSION(testfiblookup, 1); 538