app/test/test_lpm_perf.c

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