sys/tests/fib_lookup/fib_lookup.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause
   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(uint32_t fibnum)
 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(fibnum, 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         uint32_t fibnum = curthread->td_proc->p_fibnum;
 203
 204         for (int pass = 0; pass < count / CHUNK_SIZE; pass++) {
 205                 NET_EPOCH_ENTER(et);
 206                 nanouptime(&ts_pre);
 207                 pass_packets = run_test_inet_one_pass(fibnum);
 208                 nanouptime(&ts_post);
 209                 NET_EPOCH_EXIT(et);
 210
 211                 pass_diff = (ts_post.tv_sec - ts_pre.tv_sec) * 1000000000 +
 212                     (ts_post.tv_nsec - ts_pre.tv_nsec);
 213                 total_diff += pass_diff;
 214                 total_packets += pass_packets;
 215         }
 216
 217         printf("%zu packets in %zu nanoseconds, %zu pps\n",
 218             total_packets, total_diff, total_packets * 1000000000 / total_diff);
 219
 220         return (0);
 221 }
 222 SYSCTL_PROC(_net_route_test, OID_AUTO, run_inet,
 223     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 224     0, 0, run_test_inet, "I", "Execute fib4_lookup test");
 225
 226 static uint64_t
 227 run_test_inet6_one_pass(uint32_t fibnum)
 228 {
 229         /* Assume epoch */
 230         int sz = V_inet6_list_size;
 231         int tries = CHUNK_SIZE / sz;
 232         const struct in6_addr *a = V_inet6_addr_list;
 233         uint64_t count = 0;
 234
 235         for (int pass = 0; pass < tries; pass++) {
 236                 for (int i = 0; i < sz; i++) {
 237                         fib6_lookup(fibnum, &a[i], 0, NHR_NONE, 0);
 238                         count++;
 239                 }
 240         }
 241         return (count);
 242 }
 243
 244 static int
 245 run_test_inet6(SYSCTL_HANDLER_ARGS)
 246 {
 247         struct epoch_tracker et;
 248
 249         int count = 0;
 250         int error = sysctl_handle_int(oidp, &count, 0, req);
 251         if (error != 0)
 252                 return (error);
 253
 254         if (count == 0)
 255                 return (0);
 256
 257         if (V_inet6_list_size <= 0)
 258                 return (ENOENT);
 259
 260         printf("run: %d packets vnet %p\n", count, curvnet);
 261         if (count < CHUNK_SIZE)
 262                 count = CHUNK_SIZE;
 263
 264         struct timespec ts_pre, ts_post;
 265         int64_t pass_diff, total_diff = 0;
 266         uint64_t pass_packets, total_packets = 0;
 267         uint32_t fibnum = curthread->td_proc->p_fibnum;
 268
 269         for (int pass = 0; pass < count / CHUNK_SIZE; pass++) {
 270                 NET_EPOCH_ENTER(et);
 271                 nanouptime(&ts_pre);
 272                 pass_packets = run_test_inet6_one_pass(fibnum);
 273                 nanouptime(&ts_post);
 274                 NET_EPOCH_EXIT(et);
 275
 276                 pass_diff = (ts_post.tv_sec - ts_pre.tv_sec) * 1000000000 +
 277                     (ts_post.tv_nsec - ts_pre.tv_nsec);
 278                 total_diff += pass_diff;
 279                 total_packets += pass_packets;
 280         }
 281
 282         printf("%zu packets in %zu nanoseconds, %zu pps\n",
 283             total_packets, total_diff, total_packets * 1000000000 / total_diff);
 284
 285         return (0);
 286 }
 287 SYSCTL_PROC(_net_route_test, OID_AUTO, run_inet6,
 288     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 289     0, 0, run_test_inet6, "I", "Execute fib6_lookup test");
 290
 291 static bool
 292 cmp_dst(uint32_t fibnum, struct in_addr a)
 293 {
 294         struct nhop_object *nh_fib;
 295         struct rtentry *rt;
 296         struct route_nhop_data rnd = {};
 297
 298         nh_fib = fib4_lookup(fibnum, a, 0, NHR_NONE, 0);
 299         rt = fib4_lookup_rt(fibnum, a, 0, NHR_NONE, &rnd);
 300
 301         if (nh_fib == NULL && rt == NULL) {
 302                 return (true);
 303         } else if (nh_fib == nhop_select(rnd.rnd_nhop, 0)) {
 304                 return (true);
 305         }
 306
 307         struct in_addr dst;
 308         int plen;
 309         uint32_t scopeid;
 310         char key_str[INET_ADDRSTRLEN], dst_str[INET_ADDRSTRLEN];
 311
 312         inet_ntop(AF_INET, &a, key_str, sizeof(key_str));
 313         if (rnd.rnd_nhop == NULL) {
 314                 printf("[RT BUG] lookup for %s: RIB: ENOENT FIB: nh=%u\n",
 315                     key_str, nhop_get_idx(nh_fib));
 316         } else {
 317                 rt_get_inet_prefix_plen(rt, &dst, &plen, &scopeid);
 318                 inet_ntop(AF_INET, &dst, dst_str, sizeof(dst_str));
 319                 printf("[RT BUG] lookup for %s: RIB: %s/%d,nh=%u FIB: nh=%u\n",
 320                     key_str, dst_str, plen,
 321                     nhop_get_idx(nhop_select(rnd.rnd_nhop, 0)),
 322                     nh_fib ? nhop_get_idx(nh_fib) : 0);
 323         }
 324
 325         return (false);
 326 }
 327
 328 static bool
 329 cmp_dst6(uint32_t fibnum, const struct in6_addr *a)
 330 {
 331         struct nhop_object *nh_fib;
 332         struct rtentry *rt;
 333         struct route_nhop_data rnd = {};
 334
 335         nh_fib = fib6_lookup(fibnum, a, 0, NHR_NONE, 0);
 336         rt = fib6_lookup_rt(fibnum, a, 0, NHR_NONE, &rnd);
 337
 338         if (nh_fib == NULL && rt == NULL) {
 339                 return (true);
 340         } else if (nh_fib == nhop_select(rnd.rnd_nhop, 0)) {
 341                 return (true);
 342         }
 343
 344         struct in6_addr dst;
 345         int plen;
 346         uint32_t scopeid;
 347         char key_str[INET6_ADDRSTRLEN], dst_str[INET6_ADDRSTRLEN];
 348
 349         inet_ntop(AF_INET6, a, key_str, sizeof(key_str));
 350         if (rnd.rnd_nhop == NULL) {
 351                 printf("[RT BUG] lookup for %s: RIB: ENOENT FIB: nh=%u\n",
 352                     key_str, nhop_get_idx(nh_fib));
 353         } else {
 354                 rt_get_inet6_prefix_plen(rt, &dst, &plen, &scopeid);
 355                 inet_ntop(AF_INET6, &dst, dst_str, sizeof(dst_str));
 356                 printf("[RT BUG] lookup for %s: RIB: %s/%d,nh=%u FIB: nh=%u\n",
 357                     key_str, dst_str, plen,
 358                     nhop_get_idx(nhop_select(rnd.rnd_nhop, 0)),
 359                     nh_fib ? nhop_get_idx(nh_fib) : 0);
 360         }
 361
 362         return (false);
 363 }
 364
 365 /* Random lookups: correctness verification */
 366 static uint64_t
 367 run_test_inet_one_pass_random(uint32_t fibnum)
 368 {
 369         /* Assume epoch */
 370         struct in_addr a[64];
 371         int sz = 64;
 372         uint64_t count = 0;
 373
 374         for (int pass = 0; pass < CHUNK_SIZE / sz; pass++) {
 375                 arc4random_buf(a, sizeof(a));
 376                 for (int i = 0; i < sz; i++) {
 377                         if (!cmp_dst(fibnum, a[i]))
 378                                 return (0);
 379                         count++;
 380                 }
 381         }
 382         return (count);
 383 }
 384
 385 static int
 386 run_test_inet_random(SYSCTL_HANDLER_ARGS)
 387 {
 388         struct epoch_tracker et;
 389
 390         int count = 0;
 391         int error = sysctl_handle_int(oidp, &count, 0, req);
 392         if (error != 0)
 393                 return (error);
 394
 395         if (count == 0)
 396                 return (0);
 397
 398         if (count < CHUNK_SIZE)
 399                 count = CHUNK_SIZE;
 400
 401         struct timespec ts_pre, ts_post;
 402         int64_t pass_diff, total_diff = 1;
 403         uint64_t pass_packets, total_packets = 0;
 404         uint32_t fibnum = curthread->td_proc->p_fibnum;
 405
 406         for (int pass = 0; pass < count / CHUNK_SIZE; pass++) {
 407                 NET_EPOCH_ENTER(et);
 408                 nanouptime(&ts_pre);
 409                 pass_packets = run_test_inet_one_pass_random(fibnum);
 410                 nanouptime(&ts_post);
 411                 NET_EPOCH_EXIT(et);
 412
 413                 pass_diff = (ts_post.tv_sec - ts_pre.tv_sec) * 1000000000 +
 414                     (ts_post.tv_nsec - ts_pre.tv_nsec);
 415                 total_diff += pass_diff;
 416                 total_packets += pass_packets;
 417
 418                 if (pass_packets == 0)
 419                         break;
 420         }
 421
 422         /* Signal error to userland */
 423         if (pass_packets == 0)
 424                 return (EINVAL);
 425
 426         printf("%zu packets in %zu nanoseconds, %zu pps\n",
 427             total_packets, total_diff, total_packets * 1000000000 / total_diff);
 428
 429         return (0);
 430 }
 431 SYSCTL_PROC(_net_route_test, OID_AUTO, run_inet_random,
 432     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 433     0, 0, run_test_inet_random, "I", "Execute fib4_lookup random check tests");
 434
 435
 436 struct inet_array {
 437         uint32_t alloc_items;
 438         uint32_t num_items;
 439         uint32_t rnh_prefixes;
 440         int error;
 441         struct in_addr *arr;
 442 };
 443
 444 /*
 445  * For each prefix, add the following records to the lookup array:
 446  * * prefix-1, prefix, prefix + 1, prefix_end, prefix_end + 1
 447  */
 448 static int
 449 add_prefix(struct rtentry *rt, void *_data)
 450 {
 451         struct inet_array *pa = (struct inet_array *)_data;
 452         struct in_addr addr;
 453         int plen;
 454         uint32_t scopeid, haddr;
 455
 456         pa->rnh_prefixes++;
 457
 458         if (pa->num_items + 5 >= pa->alloc_items) {
 459                 if (pa->error == 0)
 460                         pa->error = ENOSPC;
 461                 return (0);
 462         }
 463
 464         rt_get_inet_prefix_plen(rt, &addr, &plen, &scopeid);
 465
 466         pa->arr[pa->num_items++] = addr;
 467         haddr = ntohl(addr.s_addr);
 468         if (haddr > 0) {
 469                 pa->arr[pa->num_items++].s_addr = htonl(haddr - 1);
 470                 pa->arr[pa->num_items++].s_addr = htonl(haddr + 1);
 471                 /* assume mask != 0 */
 472                 uint32_t mlen = (1 << (32 - plen)) - 1;
 473                 pa->arr[pa->num_items++].s_addr = htonl(haddr + mlen);
 474                 /* can overflow, but who cares */
 475                 pa->arr[pa->num_items++].s_addr = htonl(haddr + mlen + 1);
 476         }
 477
 478         return (0);
 479 }
 480
 481 static bool
 482 prepare_list(uint32_t fibnum, struct inet_array *pa)
 483 {
 484         struct rib_head *rh;
 485
 486         rh = rt_tables_get_rnh(fibnum, AF_INET);
 487
 488         uint32_t num_prefixes = rh->rnh_prefixes;
 489         bzero(pa, sizeof(struct inet_array));
 490         pa->alloc_items = (num_prefixes + 10) * 5;
 491         pa->arr = mallocarray(pa->alloc_items, sizeof(struct in_addr),
 492             M_TEMP, M_ZERO | M_WAITOK);
 493
 494         rib_walk(fibnum, AF_INET, false, add_prefix, pa);
 495
 496         if (pa->error != 0) {
 497                 printf("prefixes: old: %u, current: %u, walked: %u, allocated: %u\n",
 498                     num_prefixes, rh->rnh_prefixes, pa->rnh_prefixes, pa->alloc_items);
 499         }
 500
 501         return (pa->error == 0);
 502 }
 503
 504 static int
 505 run_test_inet_scan(SYSCTL_HANDLER_ARGS)
 506 {
 507         struct epoch_tracker et;
 508
 509         int count = 0;
 510         int error = sysctl_handle_int(oidp, &count, 0, req);
 511         if (error != 0)
 512                 return (error);
 513
 514         if (count == 0)
 515                 return (0);
 516
 517         struct inet_array pa = {};
 518         uint32_t fibnum = curthread->td_proc->p_fibnum;
 519
 520         if (!prepare_list(fibnum, &pa))
 521                 return (pa.error);
 522
 523         struct timespec ts_pre, ts_post;
 524         int64_t total_diff = 1;
 525         uint64_t total_packets = 0;
 526         int failure_count = 0;
 527
 528         NET_EPOCH_ENTER(et);
 529         nanouptime(&ts_pre);
 530         for (int i = 0; i < pa.num_items; i++) {
 531                 if (!cmp_dst(fibnum, pa.arr[i])) {
 532                         failure_count++;
 533                 }
 534                 total_packets++;
 535         }
 536         nanouptime(&ts_post);
 537         NET_EPOCH_EXIT(et);
 538
 539         if (pa.arr != NULL)
 540                 free(pa.arr, M_TEMP);
 541
 542         /* Signal error to userland */
 543         if (failure_count > 0) {
 544                 printf("[RT ERROR] total failures: %d\n", failure_count);
 545                 return (EINVAL);
 546         }
 547
 548         total_diff = (ts_post.tv_sec - ts_pre.tv_sec) * 1000000000 +
 549             (ts_post.tv_nsec - ts_pre.tv_nsec);
 550         printf("%zu packets in %zu nanoseconds, %zu pps\n",
 551             total_packets, total_diff, total_packets * 1000000000 / total_diff);
 552
 553         return (0);
 554 }
 555 SYSCTL_PROC(_net_route_test, OID_AUTO, run_inet_scan,
 556     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 557     0, 0, run_test_inet_scan, "I", "Execute fib4_lookup scan tests");
 558
 559 struct inet6_array {
 560         uint32_t alloc_items;
 561         uint32_t num_items;
 562         uint32_t rnh_prefixes;
 563         int error;
 564         struct in6_addr *arr;
 565 };
 566
 567 static bool
 568 safe_add(uint32_t *v, uint32_t inc)
 569 {
 570         if (*v < (UINT32_MAX - inc)) {
 571                 *v += inc;
 572                 return (true);
 573         } else {
 574                 *v -= (UINT32_MAX - inc + 1);
 575                 return (false);
 576         }
 577 }
 578
 579 static bool
 580 safe_dec(uint32_t *v, uint32_t inc)
 581 {
 582         if (*v >= inc) {
 583                 *v -= inc;
 584                 return (true);
 585         } else {
 586                 *v += (UINT32_MAX - inc + 1);
 587                 return (false);
 588         }
 589 }
 590
 591 static void
 592 inc_prefix6(struct in6_addr *addr, int inc)
 593 {
 594         for (int i = 0; i < 4; i++) {
 595                 uint32_t v = ntohl(addr->s6_addr32[3 - i]);
 596                 bool ret = safe_add(&v, inc);
 597                 addr->s6_addr32[3 - i] = htonl(v);
 598                 if (ret)
 599                         return;
 600                 inc = 1;
 601         }
 602 }
 603
 604 static void
 605 dec_prefix6(struct in6_addr *addr, int dec)
 606 {
 607         for (int i = 0; i < 4; i++) {
 608                 uint32_t v = ntohl(addr->s6_addr32[3 - i]);
 609                 bool ret = safe_dec(&v, dec);
 610                 addr->s6_addr32[3 - i] = htonl(v);
 611                 if (ret)
 612                         return;
 613                 dec = 1;
 614         }
 615 }
 616
 617 static void
 618 ipv6_writemask(struct in6_addr *addr6, uint8_t mask)
 619 {
 620         uint32_t *cp;
 621
 622         for (cp = (uint32_t *)addr6; mask >= 32; mask -= 32)
 623                 *cp++ = 0xFFFFFFFF;
 624         if (mask > 0)
 625                 *cp = htonl(mask ? ~((1 << (32 - mask)) - 1) : 0);
 626 }
 627
 628 /*
 629  * For each prefix, add the following records to the lookup array:
 630  * * prefix-1, prefix, prefix + 1, prefix_end, prefix_end + 1
 631  */
 632 static int
 633 add_prefix6(struct rtentry *rt, void *_data)
 634 {
 635         struct inet6_array *pa = (struct inet6_array *)_data;
 636         struct in6_addr addr, naddr;
 637         int plen;
 638         uint32_t scopeid;
 639
 640         pa->rnh_prefixes++;
 641
 642         if (pa->num_items + 5 >= pa->alloc_items) {
 643                 if (pa->error == 0)
 644                         pa->error = ENOSPC;
 645                 return (0);
 646         }
 647
 648         rt_get_inet6_prefix_plen(rt, &addr, &plen, &scopeid);
 649
 650         pa->arr[pa->num_items++] = addr;
 651         if (!IN6_ARE_ADDR_EQUAL(&addr, &in6addr_any)) {
 652                 naddr = addr;
 653                 dec_prefix6(&naddr, 1);
 654                 pa->arr[pa->num_items++] = naddr;
 655                 naddr = addr;
 656                 inc_prefix6(&naddr, 1);
 657                 pa->arr[pa->num_items++] = naddr;
 658
 659                 /* assume mask != 0 */
 660                 struct in6_addr mask6;
 661                 ipv6_writemask(&mask6, plen);
 662                 naddr = addr;
 663                 for (int i = 0; i < 3; i++)
 664                         naddr.s6_addr32[i] = htonl(ntohl(naddr.s6_addr32[i]) | ~ntohl(mask6.s6_addr32[i]));
 665
 666                 pa->arr[pa->num_items++] = naddr;
 667                 inc_prefix6(&naddr, 1);
 668                 pa->arr[pa->num_items++] = naddr;
 669         }
 670
 671         return (0);
 672 }
 673
 674 static bool
 675 prepare_list6(uint32_t fibnum, struct inet6_array *pa)
 676 {
 677         struct rib_head *rh;
 678
 679         rh = rt_tables_get_rnh(fibnum, AF_INET6);
 680
 681         uint32_t num_prefixes = rh->rnh_prefixes;
 682         bzero(pa, sizeof(struct inet6_array));
 683         pa->alloc_items = (num_prefixes + 10) * 5;
 684         pa->arr = mallocarray(pa->alloc_items, sizeof(struct in6_addr),
 685             M_TEMP, M_ZERO | M_WAITOK);
 686
 687         rib_walk(fibnum, AF_INET6, false, add_prefix6, pa);
 688
 689         if (pa->error != 0) {
 690                 printf("prefixes: old: %u, current: %u, walked: %u, allocated: %u\n",
 691                     num_prefixes, rh->rnh_prefixes, pa->rnh_prefixes, pa->alloc_items);
 692         }
 693
 694         return (pa->error == 0);
 695 }
 696
 697 static int
 698 run_test_inet6_scan(SYSCTL_HANDLER_ARGS)
 699 {
 700         struct epoch_tracker et;
 701
 702         int count = 0;
 703         int error = sysctl_handle_int(oidp, &count, 0, req);
 704         if (error != 0)
 705                 return (error);
 706
 707         if (count == 0)
 708                 return (0);
 709
 710         struct inet6_array pa = {};
 711         uint32_t fibnum = curthread->td_proc->p_fibnum;
 712
 713         if (!prepare_list6(fibnum, &pa))
 714                 return (pa.error);
 715
 716         struct timespec ts_pre, ts_post;
 717         int64_t total_diff = 1;
 718         uint64_t total_packets = 0;
 719         int failure_count = 0;
 720
 721         NET_EPOCH_ENTER(et);
 722         nanouptime(&ts_pre);
 723         for (int i = 0; i < pa.num_items; i++) {
 724                 if (!cmp_dst6(fibnum, &pa.arr[i])) {
 725                         failure_count++;
 726                 }
 727                 total_packets++;
 728         }
 729         nanouptime(&ts_post);
 730         NET_EPOCH_EXIT(et);
 731
 732         if (pa.arr != NULL)
 733                 free(pa.arr, M_TEMP);
 734
 735         /* Signal error to userland */
 736         if (failure_count > 0) {
 737                 printf("[RT ERROR] total failures: %d\n", failure_count);
 738                 return (EINVAL);
 739         }
 740
 741         total_diff = (ts_post.tv_sec - ts_pre.tv_sec) * 1000000000 +
 742             (ts_post.tv_nsec - ts_pre.tv_nsec);
 743         printf("%zu packets in %zu nanoseconds, %zu pps\n",
 744             total_packets, total_diff, total_packets * 1000000000 / total_diff);
 745
 746         return (0);
 747 }
 748 SYSCTL_PROC(_net_route_test, OID_AUTO, run_inet6_scan,
 749     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 750     0, 0, run_test_inet6_scan, "I", "Execute fib6_lookup scan tests");
 751
 752 #define LPS_SEQ         0x1
 753 #define LPS_ANN         0x2
 754 #define LPS_REP         0x4
 755
 756 struct lps_walk_state {
 757         uint32_t *keys;
 758         int pos;
 759         int lim;
 760 };
 761
 762 static int
 763 reduce_keys(struct rtentry *rt, void *_data)
 764 {
 765         struct lps_walk_state *wa = (struct lps_walk_state *) _data;
 766         struct in_addr addr;
 767         uint32_t scopeid;
 768         int plen;
 769
 770         rt_get_inet_prefix_plen(rt, &addr, &plen, &scopeid);
 771         wa->keys[wa->pos] = ntohl(addr.s_addr) |
 772             (wa->keys[wa->pos] & ~(0xffffffffU << (32 - plen)));
 773
 774         wa->pos++;
 775         return (wa->pos == wa->lim);
 776 }
 777
 778 static int
 779 rnd_lps(SYSCTL_HANDLER_ARGS)
 780 {
 781         struct epoch_tracker et;
 782         struct in_addr key;
 783         struct lps_walk_state wa;
 784         struct timespec ts_pre, ts_post;
 785         struct nhop_object *nh_fib;
 786         uint64_t total_diff, lps;
 787         uint32_t *keys, fibnum;
 788         uint32_t t, p;
 789         uintptr_t acc = 0;
 790         int i, pos, count = 0;
 791         int seq = 0, rep = 0;
 792         int error;
 793
 794         error = sysctl_handle_int(oidp, &count, 0, req);
 795         if (error != 0)
 796                 return (error);
 797         if (count <= 0)
 798                 return (0);
 799         fibnum = curthread->td_proc->p_fibnum;
 800
 801         keys = malloc(sizeof(*keys) * count, M_TEMP, M_NOWAIT);
 802         if (keys == NULL)
 803                 return (ENOMEM);
 804         printf("Preparing %d random keys...\n", count);
 805         arc4random_buf(keys, sizeof(*keys) * count);
 806         if (arg2 & LPS_ANN) {
 807                 wa.keys = keys;
 808                 wa.pos = 0;
 809                 wa.lim = count;
 810                 printf("Reducing keys to announced address space...\n");
 811                 do {
 812                         rib_walk(fibnum, AF_INET, false, reduce_keys,
 813                             &wa);
 814                 } while (wa.pos < wa.lim);
 815                 printf("Reshuffling keys...\n");
 816                 for (int i = 0; i < count; i++) {
 817                         p = random() % count;
 818                         t = keys[p];
 819                         keys[p] = keys[i];
 820                         keys[i] = t;
 821                 }
 822         }
 823
 824         if (arg2 & LPS_REP) {
 825                 rep = 1;
 826                 printf("REP ");
 827         }
 828         if (arg2 & LPS_SEQ) {
 829                 seq = 1;
 830                 printf("SEQ");
 831         } else if (arg2 & LPS_ANN)
 832                 printf("ANN");
 833         else
 834                 printf("RND");
 835         printf(" LPS test starting...\n");
 836
 837         NET_EPOCH_ENTER(et);
 838         nanouptime(&ts_pre);
 839         for (i = 0, pos = 0; i < count; i++) {
 840                 key.s_addr = keys[pos++] ^ ((acc >> 10) & 0xff);
 841                 nh_fib = fib4_lookup(fibnum, key, 0, NHR_NONE, 0);
 842                 if (seq) {
 843                         if (nh_fib != NULL) {
 844                                 acc += (uintptr_t) nh_fib + 123;
 845                                 if (acc & 0x1000)
 846                                         acc += (uintptr_t) nh_fib->nh_ifp;
 847                                 else
 848                                         acc -= (uintptr_t) nh_fib->nh_ifp;
 849                         } else
 850                                 acc ^= (acc >> 3) + (acc << 2) + i;
 851                         if (acc & 0x800)
 852                                 pos++;
 853                         if (pos >= count)
 854                                 pos = 0;
 855                 }
 856                 if (rep && ((i & 0xf) == 0xf)) {
 857                         pos -= 0xf;
 858                         if (pos < 0)
 859                                 pos += 0xf;
 860                 }
 861         }
 862         nanouptime(&ts_post);
 863         NET_EPOCH_EXIT(et);
 864
 865         free(keys, M_TEMP);
 866
 867         total_diff = (ts_post.tv_sec - ts_pre.tv_sec) * 1000000000 +
 868             (ts_post.tv_nsec - ts_pre.tv_nsec);
 869         lps = 1000000000ULL * count / total_diff;
 870         printf("%d lookups in %zu.%06zu milliseconds, %lu.%06lu MLPS\n",
 871             count, total_diff / 1000000, total_diff % 1000000,
 872             lps / 1000000, lps % 1000000);
 873
 874         return (0);
 875 }
 876 SYSCTL_PROC(_net_route_test, OID_AUTO, run_lps_rnd,
 877     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 878     0, 0, rnd_lps, "I",
 879     "Measure lookups per second, uniformly random keys, independent lookups");
 880 SYSCTL_PROC(_net_route_test, OID_AUTO, run_lps_rnd_ann,
 881     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 882     0, LPS_ANN, rnd_lps, "I",
 883     "Measure lookups per second, random keys from announced address space, "
 884     "independent lookups");
 885 SYSCTL_PROC(_net_route_test, OID_AUTO, run_lps_seq,
 886     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 887     0, LPS_SEQ, rnd_lps, "I",
 888     "Measure lookups per second, uniformly random keys, "
 889     "artificial dependencies between lookups");
 890 SYSCTL_PROC(_net_route_test, OID_AUTO, run_lps_seq_ann,
 891     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 892     0, LPS_SEQ | LPS_ANN, rnd_lps, "I",
 893     "Measure lookups per second, random keys from announced address space, "
 894     "artificial dependencies between lookups");
 895 SYSCTL_PROC(_net_route_test, OID_AUTO, run_lps_rnd_rep,
 896     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 897     0, LPS_REP, rnd_lps, "I",
 898     "Measure lookups per second, uniformly random keys, independent lookups, "
 899     "repeated keys");
 900 SYSCTL_PROC(_net_route_test, OID_AUTO, run_lps_rnd_ann_rep,
 901     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 902     0, LPS_ANN | LPS_REP, rnd_lps, "I",
 903     "Measure lookups per second, random keys from announced address space, "
 904     "independent lookups, repeated keys");
 905 SYSCTL_PROC(_net_route_test, OID_AUTO, run_lps_seq_rep,
 906     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 907     0, LPS_SEQ | LPS_REP, rnd_lps, "I",
 908     "Measure lookups per second, uniformly random keys, "
 909     "artificial dependencies between lookups, repeated keys");
 910 SYSCTL_PROC(_net_route_test, OID_AUTO, run_lps_seq_ann_rep,
 911     CTLFLAG_VNET | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
 912     0, LPS_SEQ | LPS_ANN | LPS_REP, rnd_lps, "I",
 913     "Measure lookups per second, random keys from announced address space, "
 914     "artificial dependencies between lookups, repeated keys");
 915
 916 static int
 917 test_fib_lookup_modevent(module_t mod, int type, void *unused)
 918 {
 919         int error = 0;
 920
 921         switch (type) {
 922         case MOD_LOAD:
 923                 break;
 924         case MOD_UNLOAD:
 925                 if (V_inet_addr_list != NULL)
 926                         free(V_inet_addr_list, M_TEMP);
 927                 if (V_inet6_addr_list != NULL)
 928                         free(V_inet6_addr_list, M_TEMP);
 929                 break;
 930         default:
 931                 error = EOPNOTSUPP;
 932                 break;
 933         }
 934         return (error);
 935 }
 936
 937 static moduledata_t testfiblookupmod = {
 938         "test_fib_lookup",
 939         test_fib_lookup_modevent,
 940         0
 941 };
 942
 943 DECLARE_MODULE(testfiblookupmod, testfiblookupmod, SI_SUB_PSEUDO, SI_ORDER_ANY);
 944 MODULE_VERSION(testfiblookup, 1);