app/test/test_fib_perf.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
   3  * Copyright(c) 2019 Intel Corporation
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdint.h>
   8 #include <stdlib.h>
   9 #include <math.h>
  10
  11 #include <rte_cycles.h>
  12 #include <rte_random.h>
  13 #include <rte_branch_prediction.h>
  14 #include <rte_ip.h>
  15
  16 #include "test.h"
  17 #include "test_xmmt_ops.h"
  18
  19 #ifdef RTE_EXEC_ENV_WINDOWS
  20 static int
  21 test_fib_perf(void)
  22 {
  23         printf("fib_perf not supported on Windows, skipping test\n");
  24         return TEST_SKIPPED;
  25 }
  26
  27 #else
  28
  29 #include <rte_fib.h>
  30
  31 #define TEST_FIB_ASSERT(cond) do {                              \
  32         if (!(cond)) {                                          \
  33                 printf("Error at line %d:\n", __LINE__);        \
  34                 return -1;                                      \
  35         }                                                       \
  36 } while (0)
  37
  38 #define ITERATIONS (1 << 10)
  39 #define BATCH_SIZE (1 << 12)
  40 #define BULK_SIZE 32
  41
  42 #define MAX_RULE_NUM (1200000)
  43
  44 struct route_rule {
  45         uint32_t ip;
  46         uint8_t depth;
  47 };
  48
  49 static struct route_rule large_route_table[MAX_RULE_NUM];
  50
  51 static uint32_t num_route_entries;
  52 #define NUM_ROUTE_ENTRIES num_route_entries
  53
  54 enum {
  55         IP_CLASS_A,
  56         IP_CLASS_B,
  57         IP_CLASS_C
  58 };
  59 #define RTE_FIB_MAX_DEPTH       32
  60 /* struct route_rule_count defines the total number of rules in following a/b/c
  61  * each item in a[]/b[]/c[] is the number of common IP address class A/B/C, not
  62  * including the ones for private local network.
  63  */
  64 struct route_rule_count {
  65         uint32_t a[RTE_FIB_MAX_DEPTH];
  66         uint32_t b[RTE_FIB_MAX_DEPTH];
  67         uint32_t c[RTE_FIB_MAX_DEPTH];
  68 };
  69
  70 /* All following numbers of each depth of each common IP class are just
  71  * got from previous large constant table in app/test/test_lpm_routes.h .
  72  * In order to match similar performance, they keep same depth and IP
  73  * address coverage as previous constant table. These numbers don't
  74  * include any private local IP address. As previous large const rule
  75  * table was just dumped from a real router, there are no any IP address
  76  * in class C or D.
  77  */
  78 static struct route_rule_count rule_count = {
  79         .a = { /* IP class A in which the most significant bit is 0 */
  80                     0, /* depth =  1 */
  81                     0, /* depth =  2 */
  82                     1, /* depth =  3 */
  83                     0, /* depth =  4 */
  84                     2, /* depth =  5 */
  85                     1, /* depth =  6 */
  86                     3, /* depth =  7 */
  87                   185, /* depth =  8 */
  88                    26, /* depth =  9 */
  89                    16, /* depth = 10 */
  90                    39, /* depth = 11 */
  91                   144, /* depth = 12 */
  92                   233, /* depth = 13 */
  93                   528, /* depth = 14 */
  94                   866, /* depth = 15 */
  95                  3856, /* depth = 16 */
  96                  3268, /* depth = 17 */
  97                  5662, /* depth = 18 */
  98                 17301, /* depth = 19 */
  99                 22226, /* depth = 20 */
 100                 11147, /* depth = 21 */
 101                 16746, /* depth = 22 */
 102                 17120, /* depth = 23 */
 103                 77578, /* depth = 24 */
 104                   401, /* depth = 25 */
 105                   656, /* depth = 26 */
 106                  1107, /* depth = 27 */
 107                  1121, /* depth = 28 */
 108                  2316, /* depth = 29 */
 109                   717, /* depth = 30 */
 110                    10, /* depth = 31 */
 111                    66  /* depth = 32 */
 112         },
 113         .b = { /* IP class A in which the most 2 significant bits are 10 */
 114                     0, /* depth =  1 */
 115                     0, /* depth =  2 */
 116                     0, /* depth =  3 */
 117                     0, /* depth =  4 */
 118                     1, /* depth =  5 */
 119                     1, /* depth =  6 */
 120                     1, /* depth =  7 */
 121                     3, /* depth =  8 */
 122                     3, /* depth =  9 */
 123                    30, /* depth = 10 */
 124                    25, /* depth = 11 */
 125                   168, /* depth = 12 */
 126                   305, /* depth = 13 */
 127                   569, /* depth = 14 */
 128                  1129, /* depth = 15 */
 129                 50800, /* depth = 16 */
 130                  1645, /* depth = 17 */
 131                  1820, /* depth = 18 */
 132                  3506, /* depth = 19 */
 133                  3258, /* depth = 20 */
 134                  3424, /* depth = 21 */
 135                  4971, /* depth = 22 */
 136                  6885, /* depth = 23 */
 137                 39771, /* depth = 24 */
 138                   424, /* depth = 25 */
 139                   170, /* depth = 26 */
 140                   433, /* depth = 27 */
 141                    92, /* depth = 28 */
 142                   366, /* depth = 29 */
 143                   377, /* depth = 30 */
 144                     2, /* depth = 31 */
 145                   200  /* depth = 32 */
 146         },
 147         .c = { /* IP class A in which the most 3 significant bits are 110 */
 148                      0, /* depth =  1 */
 149                      0, /* depth =  2 */
 150                      0, /* depth =  3 */
 151                      0, /* depth =  4 */
 152                      0, /* depth =  5 */
 153                      0, /* depth =  6 */
 154                      0, /* depth =  7 */
 155                     12, /* depth =  8 */
 156                      8, /* depth =  9 */
 157                      9, /* depth = 10 */
 158                     33, /* depth = 11 */
 159                     69, /* depth = 12 */
 160                    237, /* depth = 13 */
 161                   1007, /* depth = 14 */
 162                   1717, /* depth = 15 */
 163                  14663, /* depth = 16 */
 164                   8070, /* depth = 17 */
 165                  16185, /* depth = 18 */
 166                  48261, /* depth = 19 */
 167                  36870, /* depth = 20 */
 168                  33960, /* depth = 21 */
 169                  50638, /* depth = 22 */
 170                  61422, /* depth = 23 */
 171                 466549, /* depth = 24 */
 172                   1829, /* depth = 25 */
 173                   4824, /* depth = 26 */
 174                   4927, /* depth = 27 */
 175                   5914, /* depth = 28 */
 176                  10254, /* depth = 29 */
 177                   4905, /* depth = 30 */
 178                      1, /* depth = 31 */
 179                    716  /* depth = 32 */
 180         }
 181 };
 182
 183 static void generate_random_rule_prefix(uint32_t ip_class, uint8_t depth)
 184 {
 185 /* IP address class A, the most significant bit is 0 */
 186 #define IP_HEAD_MASK_A                  0x00000000
 187 #define IP_HEAD_BIT_NUM_A               1
 188
 189 /* IP address class B, the most significant 2 bits are 10 */
 190 #define IP_HEAD_MASK_B                  0x80000000
 191 #define IP_HEAD_BIT_NUM_B               2
 192
 193 /* IP address class C, the most significant 3 bits are 110 */
 194 #define IP_HEAD_MASK_C                  0xC0000000
 195 #define IP_HEAD_BIT_NUM_C               3
 196
 197         uint32_t class_depth;
 198         uint32_t range;
 199         uint32_t mask;
 200         uint32_t step;
 201         uint32_t start;
 202         uint32_t fixed_bit_num;
 203         uint32_t ip_head_mask;
 204         uint32_t rule_num;
 205         uint32_t k;
 206         struct route_rule *ptr_rule;
 207
 208         if (ip_class == IP_CLASS_A) {        /* IP Address class A */
 209                 fixed_bit_num = IP_HEAD_BIT_NUM_A;
 210                 ip_head_mask = IP_HEAD_MASK_A;
 211                 rule_num = rule_count.a[depth - 1];
 212         } else if (ip_class == IP_CLASS_B) { /* IP Address class B */
 213                 fixed_bit_num = IP_HEAD_BIT_NUM_B;
 214                 ip_head_mask = IP_HEAD_MASK_B;
 215                 rule_num = rule_count.b[depth - 1];
 216         } else {                             /* IP Address class C */
 217                 fixed_bit_num = IP_HEAD_BIT_NUM_C;
 218                 ip_head_mask = IP_HEAD_MASK_C;
 219                 rule_num = rule_count.c[depth - 1];
 220         }
 221
 222         if (rule_num == 0)
 223                 return;
 224
 225         /* the number of rest bits which don't include the most significant
 226          * fixed bits for this IP address class
 227          */
 228         class_depth = depth - fixed_bit_num;
 229
 230         /* range is the maximum number of rules for this depth and
 231          * this IP address class
 232          */
 233         range = 1 << class_depth;
 234
 235         /* only mask the most depth significant generated bits
 236          * except fixed bits for IP address class
 237          */
 238         mask = range - 1;
 239
 240         /* Widen coverage of IP address in generated rules */
 241         if (range <= rule_num)
 242                 step = 1;
 243         else
 244                 step = round((double)range / rule_num);
 245
 246         /* Only generate rest bits except the most significant
 247          * fixed bits for IP address class
 248          */
 249         start = lrand48() & mask;
 250         ptr_rule = &large_route_table[num_route_entries];
 251         for (k = 0; k < rule_num; k++) {
 252                 ptr_rule->ip = (start << (RTE_FIB_MAX_DEPTH - depth))
 253                         | ip_head_mask;
 254                 ptr_rule->depth = depth;
 255                 ptr_rule++;
 256                 start = (start + step) & mask;
 257         }
 258         num_route_entries += rule_num;
 259 }
 260
 261 static void insert_rule_in_random_pos(uint32_t ip, uint8_t depth)
 262 {
 263         uint32_t pos;
 264         int try_count = 0;
 265         struct route_rule tmp;
 266
 267         do {
 268                 pos = lrand48();
 269                 try_count++;
 270         } while ((try_count < 10) && (pos > num_route_entries));
 271
 272         if ((pos > num_route_entries) || (pos >= MAX_RULE_NUM))
 273                 pos = num_route_entries >> 1;
 274
 275         tmp = large_route_table[pos];
 276         large_route_table[pos].ip = ip;
 277         large_route_table[pos].depth = depth;
 278         if (num_route_entries < MAX_RULE_NUM)
 279                 large_route_table[num_route_entries++] = tmp;
 280 }
 281
 282 static void generate_large_route_rule_table(void)
 283 {
 284         uint32_t ip_class;
 285         uint8_t  depth;
 286
 287         num_route_entries = 0;
 288         memset(large_route_table, 0, sizeof(large_route_table));
 289
 290         for (ip_class = IP_CLASS_A; ip_class <= IP_CLASS_C; ip_class++) {
 291                 for (depth = 1; depth <= RTE_FIB_MAX_DEPTH; depth++)
 292                         generate_random_rule_prefix(ip_class, depth);
 293         }
 294
 295         /* Add following rules to keep same as previous large constant table,
 296          * they are 4 rules with private local IP address and 1 all-zeros prefix
 297          * with depth = 8.
 298          */
 299         insert_rule_in_random_pos(RTE_IPV4(0, 0, 0, 0), 8);
 300         insert_rule_in_random_pos(RTE_IPV4(10, 2, 23, 147), 32);
 301         insert_rule_in_random_pos(RTE_IPV4(192, 168, 100, 10), 24);
 302         insert_rule_in_random_pos(RTE_IPV4(192, 168, 25, 100), 24);
 303         insert_rule_in_random_pos(RTE_IPV4(192, 168, 129, 124), 32);
 304 }
 305
 306 static void
 307 print_route_distribution(const struct route_rule *table, uint32_t n)
 308 {
 309         unsigned int i, j;
 310
 311         printf("Route distribution per prefix width:\n");
 312         printf("DEPTH    QUANTITY (PERCENT)\n");
 313         printf("---------------------------\n");
 314
 315         /* Count depths. */
 316         for (i = 1; i <= 32; i++) {
 317                 unsigned int depth_counter = 0;
 318                 double percent_hits;
 319
 320                 for (j = 0; j < n; j++)
 321                         if (table[j].depth == (uint8_t) i)
 322                                 depth_counter++;
 323
 324                 percent_hits = ((double)depth_counter)/((double)n) * 100;
 325                 printf("%.2u%15u (%.2f)\n", i, depth_counter, percent_hits);
 326         }
 327         printf("\n");
 328 }
 329
 330 static int
 331 test_fib_perf(void)
 332 {
 333         struct rte_fib *fib = NULL;
 334         struct rte_fib_conf config;
 335
 336         config.max_routes = 2000000;
 337         config.rib_ext_sz = 0;
 338         config.type = RTE_FIB_DIR24_8;
 339         config.default_nh = 0;
 340         config.dir24_8.nh_sz = RTE_FIB_DIR24_8_4B;
 341         config.dir24_8.num_tbl8 = 65535;
 342         uint64_t begin, total_time;
 343         unsigned int i, j;
 344         uint32_t next_hop_add = 0xAA;
 345         int status = 0;
 346         int64_t count = 0;
 347
 348         rte_srand(rte_rdtsc());
 349
 350         generate_large_route_rule_table();
 351
 352         printf("No. routes = %u\n", (unsigned int) NUM_ROUTE_ENTRIES);
 353
 354         print_route_distribution(large_route_table,
 355                 (uint32_t) NUM_ROUTE_ENTRIES);
 356
 357         fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
 358         TEST_FIB_ASSERT(fib != NULL);
 359
 360         /* Measure add. */
 361         begin = rte_rdtsc();
 362
 363         for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
 364                 if (rte_fib_add(fib, large_route_table[i].ip,
 365                                 large_route_table[i].depth, next_hop_add) == 0)
 366                         status++;
 367         }
 368         /* End Timer. */
 369         total_time = rte_rdtsc() - begin;
 370
 371         printf("Unique added entries = %d\n", status);
 372
 373         printf("Average FIB Add: %g cycles\n",
 374                         (double)total_time / NUM_ROUTE_ENTRIES);
 375
 376         /* Measure bulk Lookup */
 377         total_time = 0;
 378         count = 0;
 379         for (i = 0; i < ITERATIONS; i++) {
 380                 static uint32_t ip_batch[BATCH_SIZE];
 381                 uint64_t next_hops[BULK_SIZE];
 382
 383                 /* Create array of random IP addresses */
 384                 for (j = 0; j < BATCH_SIZE; j++)
 385                         ip_batch[j] = rte_rand();
 386
 387                 /* Lookup per batch */
 388                 begin = rte_rdtsc();
 389                 for (j = 0; j < BATCH_SIZE; j += BULK_SIZE) {
 390                         uint32_t k;
 391                         rte_fib_lookup_bulk(fib, &ip_batch[j], next_hops,
 392                                 BULK_SIZE);
 393                         for (k = 0; k < BULK_SIZE; k++)
 394                                 if (unlikely(!(next_hops[k] != 0)))
 395                                         count++;
 396                 }
 397
 398                 total_time += rte_rdtsc() - begin;
 399         }
 400         printf("BULK FIB Lookup: %.1f cycles (fails = %.1f%%)\n",
 401                         (double)total_time / ((double)ITERATIONS * BATCH_SIZE),
 402                         (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
 403
 404         /* Delete */
 405         status = 0;
 406         begin = rte_rdtsc();
 407         for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
 408                 /* rte_lpm_delete(lpm, ip, depth) */
 409                 status += rte_fib_delete(fib, large_route_table[i].ip,
 410                                 large_route_table[i].depth);
 411         }
 412
 413         total_time += rte_rdtsc() - begin;
 414
 415         printf("Average FIB Delete: %g cycles\n",
 416                         (double)total_time / NUM_ROUTE_ENTRIES);
 417
 418         rte_fib_free(fib);
 419
 420         return 0;
 421 }
 422
 423 #endif /* !RTE_EXEC_ENV_WINDOWS */
 424
 425 REGISTER_TEST_COMMAND(fib_perf_autotest, test_fib_perf);