app/test/test_lpm.c

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
   5  *   All rights reserved.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following conditions
   9  *   are met:
  10  *
  11  *     * Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *     * Redistributions in binary form must reproduce the above copyright
  14  *       notice, this list of conditions and the following disclaimer in
  15  *       the documentation and/or other materials provided with the
  16  *       distribution.
  17  *     * Neither the name of Intel Corporation nor the names of its
  18  *       contributors may be used to endorse or promote products derived
  19  *       from this software without specific prior written permission.
  20  *
  21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #include <stdio.h>
  35 #include <stdint.h>
  36 #include <stdlib.h>
  37 #include <errno.h>
  38 #include <sys/queue.h>
  39
  40 #include <rte_common.h>
  41 #include <rte_cycles.h>
  42 #include <rte_memory.h>
  43 #include <rte_random.h>
  44 #include <rte_branch_prediction.h>
  45 #include <rte_ip.h>
  46 #include <time.h>
  47
  48 #include "test.h"
  49
  50 #include "rte_lpm.h"
  51 #include "test_lpm_routes.h"
  52
  53 #define TEST_LPM_ASSERT(cond) do {                                            \
  54         if (!(cond)) {                                                        \
  55                 printf("Error at line %d: \n", __LINE__);                     \
  56                 return -1;                                                    \
  57         }                                                                     \
  58 } while(0)
  59
  60 typedef int32_t (*rte_lpm_test)(void);
  61
  62 static int32_t test0(void);
  63 static int32_t test1(void);
  64 static int32_t test2(void);
  65 static int32_t test3(void);
  66 static int32_t test4(void);
  67 static int32_t test5(void);
  68 static int32_t test6(void);
  69 static int32_t test7(void);
  70 static int32_t test8(void);
  71 static int32_t test9(void);
  72 static int32_t test10(void);
  73 static int32_t test11(void);
  74 static int32_t test12(void);
  75 static int32_t test13(void);
  76 static int32_t test14(void);
  77 static int32_t test15(void);
  78 static int32_t test16(void);
  79 static int32_t test17(void);
  80 static int32_t perf_test(void);
  81
  82 rte_lpm_test tests[] = {
  83 /* Test Cases */
  84         test0,
  85         test1,
  86         test2,
  87         test3,
  88         test4,
  89         test5,
  90         test6,
  91         test7,
  92         test8,
  93         test9,
  94         test10,
  95         test11,
  96         test12,
  97         test13,
  98         test14,
  99         test15,
 100         test16,
 101         test17,
 102         perf_test,
 103 };
 104
 105 #define NUM_LPM_TESTS (sizeof(tests)/sizeof(tests[0]))
 106 #define MAX_DEPTH 32
 107 #define MAX_RULES 256
 108 #define PASS 0
 109
 110 /*
 111  * Check that rte_lpm_create fails gracefully for incorrect user input
 112  * arguments
 113  */
 114 int32_t
 115 test0(void)
 116 {
 117         struct rte_lpm *lpm = NULL;
 118
 119         /* rte_lpm_create: lpm name == NULL */
 120         lpm = rte_lpm_create(NULL, SOCKET_ID_ANY, MAX_RULES, 0);
 121         TEST_LPM_ASSERT(lpm == NULL);
 122
 123         /* rte_lpm_create: max_rules = 0 */
 124         /* Note: __func__ inserts the function name, in this case "test0". */
 125         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, 0, 0);
 126         TEST_LPM_ASSERT(lpm == NULL);
 127
 128         /* socket_id < -1 is invalid */
 129         lpm = rte_lpm_create(__func__, -2, MAX_RULES, 0);
 130         TEST_LPM_ASSERT(lpm == NULL);
 131
 132         return PASS;
 133 }
 134
 135 /*
 136  * Create lpm table then delete lpm table 100 times
 137  * Use a slightly different rules size each time
 138  * */
 139 int32_t
 140 test1(void)
 141 {
 142         struct rte_lpm *lpm = NULL;
 143         int32_t i;
 144
 145         /* rte_lpm_free: Free NULL */
 146         for (i = 0; i < 100; i++) {
 147                 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES - i, 0);
 148                 TEST_LPM_ASSERT(lpm != NULL);
 149
 150                 rte_lpm_free(lpm);
 151         }
 152
 153         /* Can not test free so return success */
 154         return PASS;
 155 }
 156
 157 /*
 158  * Call rte_lpm_free for NULL pointer user input. Note: free has no return and
 159  * therefore it is impossible to check for failure but this test is added to
 160  * increase function coverage metrics and to validate that freeing null does
 161  * not crash.
 162  */
 163 int32_t
 164 test2(void)
 165 {
 166         struct rte_lpm *lpm = NULL;
 167
 168         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 169         TEST_LPM_ASSERT(lpm != NULL);
 170
 171         rte_lpm_free(lpm);
 172         rte_lpm_free(NULL);
 173         return PASS;
 174 }
 175
 176 /*
 177  * Check that rte_lpm_add fails gracefully for incorrect user input arguments
 178  */
 179 int32_t
 180 test3(void)
 181 {
 182         struct rte_lpm *lpm = NULL;
 183         uint32_t ip = IPv4(0, 0, 0, 0), next_hop = 100;
 184         uint8_t depth = 24;
 185         int32_t status = 0;
 186
 187         /* rte_lpm_add: lpm == NULL */
 188         status = rte_lpm_add(NULL, ip, depth, next_hop);
 189         TEST_LPM_ASSERT(status < 0);
 190
 191         /*Create vaild lpm to use in rest of test. */
 192         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 193         TEST_LPM_ASSERT(lpm != NULL);
 194
 195         /* rte_lpm_add: depth < 1 */
 196         status = rte_lpm_add(lpm, ip, 0, next_hop);
 197         TEST_LPM_ASSERT(status < 0);
 198
 199         /* rte_lpm_add: depth > MAX_DEPTH */
 200         status = rte_lpm_add(lpm, ip, (MAX_DEPTH + 1), next_hop);
 201         TEST_LPM_ASSERT(status < 0);
 202
 203         rte_lpm_free(lpm);
 204
 205         return PASS;
 206 }
 207
 208 /*
 209  * Check that rte_lpm_delete fails gracefully for incorrect user input
 210  * arguments
 211  */
 212 int32_t
 213 test4(void)
 214 {
 215         struct rte_lpm *lpm = NULL;
 216         uint32_t ip = IPv4(0, 0, 0, 0);
 217         uint8_t depth = 24;
 218         int32_t status = 0;
 219
 220         /* rte_lpm_delete: lpm == NULL */
 221         status = rte_lpm_delete(NULL, ip, depth);
 222         TEST_LPM_ASSERT(status < 0);
 223
 224         /*Create vaild lpm to use in rest of test. */
 225         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 226         TEST_LPM_ASSERT(lpm != NULL);
 227
 228         /* rte_lpm_delete: depth < 1 */
 229         status = rte_lpm_delete(lpm, ip, 0);
 230         TEST_LPM_ASSERT(status < 0);
 231
 232         /* rte_lpm_delete: depth > MAX_DEPTH */
 233         status = rte_lpm_delete(lpm, ip, (MAX_DEPTH + 1));
 234         TEST_LPM_ASSERT(status < 0);
 235
 236         rte_lpm_free(lpm);
 237
 238         return PASS;
 239 }
 240
 241 /*
 242  * Check that rte_lpm_lookup fails gracefully for incorrect user input
 243  * arguments
 244  */
 245 int32_t
 246 test5(void)
 247 {
 248 #if defined(RTE_LIBRTE_LPM_DEBUG)
 249         struct rte_lpm *lpm = NULL;
 250         uint32_t ip = IPv4(0, 0, 0, 0), next_hop_return = 0;
 251         int32_t status = 0;
 252
 253         /* rte_lpm_lookup: lpm == NULL */
 254         status = rte_lpm_lookup(NULL, ip, &next_hop_return);
 255         TEST_LPM_ASSERT(status < 0);
 256
 257         /*Create vaild lpm to use in rest of test. */
 258         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 259         TEST_LPM_ASSERT(lpm != NULL);
 260
 261         /* rte_lpm_lookup: depth < 1 */
 262         status = rte_lpm_lookup(lpm, ip, NULL);
 263         TEST_LPM_ASSERT(status < 0);
 264
 265         rte_lpm_free(lpm);
 266 #endif
 267         return PASS;
 268 }
 269
 270
 271
 272 /*
 273  * Call add, lookup and delete for a single rule with depth <= 24
 274  */
 275 int32_t
 276 test6(void)
 277 {
 278         struct rte_lpm *lpm = NULL;
 279         uint32_t ip = IPv4(0, 0, 0, 0), next_hop_add = 100, next_hop_return = 0;
 280         uint8_t depth = 24;
 281         int32_t status = 0;
 282
 283         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 284         TEST_LPM_ASSERT(lpm != NULL);
 285
 286         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 287         TEST_LPM_ASSERT(status == 0);
 288
 289         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 290         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 291
 292         status = rte_lpm_delete(lpm, ip, depth);
 293         TEST_LPM_ASSERT(status == 0);
 294
 295         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 296         TEST_LPM_ASSERT(status == -ENOENT);
 297
 298         rte_lpm_free(lpm);
 299
 300         return PASS;
 301 }
 302
 303 /*
 304  * Call add, lookup and delete for a single rule with depth > 24
 305  */
 306
 307 int32_t
 308 test7(void)
 309 {
 310         __m128i ipx4;
 311         uint32_t hop[4];
 312         struct rte_lpm *lpm = NULL;
 313         uint32_t ip = IPv4(0, 0, 0, 0), next_hop_add = 100, next_hop_return = 0;
 314         uint8_t depth = 32;
 315         int32_t status = 0;
 316
 317         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 318         TEST_LPM_ASSERT(lpm != NULL);
 319
 320         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 321         TEST_LPM_ASSERT(status == 0);
 322
 323         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 324         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 325
 326         ipx4 = _mm_set_epi32(ip, ip + 0x100, ip - 0x100, ip);
 327         rte_lpm_lookupx4(lpm, ipx4, hop, UINT32_MAX);
 328         TEST_LPM_ASSERT(hop[0] == next_hop_add);
 329         TEST_LPM_ASSERT(hop[1] == UINT32_MAX);
 330         TEST_LPM_ASSERT(hop[2] == UINT32_MAX);
 331         TEST_LPM_ASSERT(hop[3] == next_hop_add);
 332
 333         status = rte_lpm_delete(lpm, ip, depth);
 334         TEST_LPM_ASSERT(status == 0);
 335
 336         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 337         TEST_LPM_ASSERT(status == -ENOENT);
 338
 339         rte_lpm_free(lpm);
 340
 341         return PASS;
 342 }
 343
 344 /*
 345  * Use rte_lpm_add to add rules which effect only the second half of the lpm
 346  * table. Use all possible depths ranging from 1..32. Set the next hop = to the
 347  * depth. Check lookup hit for on every add and check for lookup miss on the
 348  * first half of the lpm table after each add. Finally delete all rules going
 349  * backwards (i.e. from depth = 32 ..1) and carry out a lookup after each
 350  * delete. The lookup should return the next_hop_add value related to the
 351  * previous depth value (i.e. depth -1).
 352  */
 353 int32_t
 354 test8(void)
 355 {
 356         __m128i ipx4;
 357         uint32_t hop[4];
 358         struct rte_lpm *lpm = NULL;
 359         uint32_t ip1 = IPv4(127, 255, 255, 255), ip2 = IPv4(128, 0, 0, 0);
 360         uint32_t next_hop_add, next_hop_return;
 361         uint8_t depth;
 362         int32_t status = 0;
 363
 364         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 365         TEST_LPM_ASSERT(lpm != NULL);
 366
 367         /* Loop with rte_lpm_add. */
 368         for (depth = 1; depth <= 32; depth++) {
 369                 /* Let the next_hop_add value = depth. Just for change. */
 370                 next_hop_add = depth;
 371
 372                 status = rte_lpm_add(lpm, ip2, depth, next_hop_add);
 373                 TEST_LPM_ASSERT(status == 0);
 374
 375                 /* Check IP in first half of tbl24 which should be empty. */
 376                 status = rte_lpm_lookup(lpm, ip1, &next_hop_return);
 377                 TEST_LPM_ASSERT(status == -ENOENT);
 378
 379                 status = rte_lpm_lookup(lpm, ip2, &next_hop_return);
 380                 TEST_LPM_ASSERT((status == 0) &&
 381                         (next_hop_return == next_hop_add));
 382
 383                 ipx4 = _mm_set_epi32(ip2, ip1, ip2, ip1);
 384                 rte_lpm_lookupx4(lpm, ipx4, hop, UINT32_MAX);
 385                 TEST_LPM_ASSERT(hop[0] == UINT32_MAX);
 386                 TEST_LPM_ASSERT(hop[1] == next_hop_add);
 387                 TEST_LPM_ASSERT(hop[2] == UINT32_MAX);
 388                 TEST_LPM_ASSERT(hop[3] == next_hop_add);
 389         }
 390
 391         /* Loop with rte_lpm_delete. */
 392         for (depth = 32; depth >= 1; depth--) {
 393                 next_hop_add = (uint8_t) (depth - 1);
 394
 395                 status = rte_lpm_delete(lpm, ip2, depth);
 396                 TEST_LPM_ASSERT(status == 0);
 397
 398                 status = rte_lpm_lookup(lpm, ip2, &next_hop_return);
 399
 400                 if (depth != 1) {
 401                         TEST_LPM_ASSERT((status == 0) &&
 402                                 (next_hop_return == next_hop_add));
 403                 } else {
 404                         TEST_LPM_ASSERT(status == -ENOENT);
 405                 }
 406
 407                 status = rte_lpm_lookup(lpm, ip1, &next_hop_return);
 408                 TEST_LPM_ASSERT(status == -ENOENT);
 409
 410                 ipx4 = _mm_set_epi32(ip1, ip1, ip2, ip2);
 411                 rte_lpm_lookupx4(lpm, ipx4, hop, UINT32_MAX);
 412                 if (depth != 1) {
 413                         TEST_LPM_ASSERT(hop[0] == next_hop_add);
 414                         TEST_LPM_ASSERT(hop[1] == next_hop_add);
 415                 } else {
 416                         TEST_LPM_ASSERT(hop[0] == UINT32_MAX);
 417                         TEST_LPM_ASSERT(hop[1] == UINT32_MAX);
 418                 }
 419                 TEST_LPM_ASSERT(hop[2] == UINT32_MAX);
 420                 TEST_LPM_ASSERT(hop[3] == UINT32_MAX);
 421         }
 422
 423         rte_lpm_free(lpm);
 424
 425         return PASS;
 426 }
 427
 428 /*
 429  * - Add & lookup to hit invalid TBL24 entry
 430  * - Add & lookup to hit valid TBL24 entry not extended
 431  * - Add & lookup to hit valid extended TBL24 entry with invalid TBL8 entry
 432  * - Add & lookup to hit valid extended TBL24 entry with valid TBL8 entry
 433  *
 434  */
 435 int32_t
 436 test9(void)
 437 {
 438         struct rte_lpm *lpm = NULL;
 439         uint32_t ip, ip_1, ip_2;
 440         uint8_t depth, depth_1, depth_2;
 441         uint32_t next_hop_add, next_hop_add_1, next_hop_add_2, next_hop_return;
 442         int32_t status = 0;
 443
 444         /* Add & lookup to hit invalid TBL24 entry */
 445         ip = IPv4(128, 0, 0, 0);
 446         depth = 24;
 447         next_hop_add = 100;
 448
 449         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 450         TEST_LPM_ASSERT(lpm != NULL);
 451
 452         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 453         TEST_LPM_ASSERT(status == 0);
 454
 455         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 456         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 457
 458         status = rte_lpm_delete(lpm, ip, depth);
 459         TEST_LPM_ASSERT(status == 0);
 460
 461         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 462         TEST_LPM_ASSERT(status == -ENOENT);
 463
 464         rte_lpm_delete_all(lpm);
 465
 466         /* Add & lookup to hit valid TBL24 entry not extended */
 467         ip = IPv4(128, 0, 0, 0);
 468         depth = 23;
 469         next_hop_add = 100;
 470
 471         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 472         TEST_LPM_ASSERT(status == 0);
 473
 474         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 475         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 476
 477         depth = 24;
 478         next_hop_add = 101;
 479
 480         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 481         TEST_LPM_ASSERT(status == 0);
 482
 483         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 484         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 485
 486         depth = 24;
 487
 488         status = rte_lpm_delete(lpm, ip, depth);
 489         TEST_LPM_ASSERT(status == 0);
 490
 491         depth = 23;
 492
 493         status = rte_lpm_delete(lpm, ip, depth);
 494         TEST_LPM_ASSERT(status == 0);
 495
 496         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 497         TEST_LPM_ASSERT(status == -ENOENT);
 498
 499         rte_lpm_delete_all(lpm);
 500
 501         /* Add & lookup to hit valid extended TBL24 entry with invalid TBL8
 502          * entry */
 503         ip = IPv4(128, 0, 0, 0);
 504         depth = 32;
 505         next_hop_add = 100;
 506
 507         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 508         TEST_LPM_ASSERT(status == 0);
 509
 510         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 511         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 512
 513         ip = IPv4(128, 0, 0, 5);
 514         depth = 32;
 515         next_hop_add = 101;
 516
 517         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 518         TEST_LPM_ASSERT(status == 0);
 519
 520         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 521         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 522
 523         status = rte_lpm_delete(lpm, ip, depth);
 524         TEST_LPM_ASSERT(status == 0);
 525
 526         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 527         TEST_LPM_ASSERT(status == -ENOENT);
 528
 529         ip = IPv4(128, 0, 0, 0);
 530         depth = 32;
 531         next_hop_add = 100;
 532
 533         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 534         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 535
 536         status = rte_lpm_delete(lpm, ip, depth);
 537         TEST_LPM_ASSERT(status == 0);
 538
 539         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 540         TEST_LPM_ASSERT(status == -ENOENT);
 541
 542         rte_lpm_delete_all(lpm);
 543
 544         /* Add & lookup to hit valid extended TBL24 entry with valid TBL8
 545          * entry */
 546         ip_1 = IPv4(128, 0, 0, 0);
 547         depth_1 = 25;
 548         next_hop_add_1 = 101;
 549
 550         ip_2 = IPv4(128, 0, 0, 5);
 551         depth_2 = 32;
 552         next_hop_add_2 = 102;
 553
 554         next_hop_return = 0;
 555
 556         status = rte_lpm_add(lpm, ip_1, depth_1, next_hop_add_1);
 557         TEST_LPM_ASSERT(status == 0);
 558
 559         status = rte_lpm_lookup(lpm, ip_1, &next_hop_return);
 560         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_1));
 561
 562         status = rte_lpm_add(lpm, ip_2, depth_2, next_hop_add_2);
 563         TEST_LPM_ASSERT(status == 0);
 564
 565         status = rte_lpm_lookup(lpm, ip_2, &next_hop_return);
 566         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_2));
 567
 568         status = rte_lpm_delete(lpm, ip_2, depth_2);
 569         TEST_LPM_ASSERT(status == 0);
 570
 571         status = rte_lpm_lookup(lpm, ip_2, &next_hop_return);
 572         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_1));
 573
 574         status = rte_lpm_delete(lpm, ip_1, depth_1);
 575         TEST_LPM_ASSERT(status == 0);
 576
 577         status = rte_lpm_lookup(lpm, ip_1, &next_hop_return);
 578         TEST_LPM_ASSERT(status == -ENOENT);
 579
 580         rte_lpm_free(lpm);
 581
 582         return PASS;
 583 }
 584
 585
 586 /*
 587  * - Add rule that covers a TBL24 range previously invalid & lookup (& delete &
 588  *   lookup)
 589  * - Add rule that extends a TBL24 invalid entry & lookup (& delete & lookup)
 590  * - Add rule that extends a TBL24 valid entry & lookup for both rules (&
 591  *   delete & lookup)
 592  * - Add rule that updates the next hop in TBL24 & lookup (& delete & lookup)
 593  * - Add rule that updates the next hop in TBL8 & lookup (& delete & lookup)
 594  * - Delete a rule that is not present in the TBL24 & lookup
 595  * - Delete a rule that is not present in the TBL8 & lookup
 596  *
 597  */
 598 int32_t
 599 test10(void)
 600 {
 601
 602         struct rte_lpm *lpm = NULL;
 603         uint32_t ip, next_hop_add, next_hop_return;
 604         uint8_t depth;
 605         int32_t status = 0;
 606
 607         /* Add rule that covers a TBL24 range previously invalid & lookup
 608          * (& delete & lookup) */
 609         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 610         TEST_LPM_ASSERT(lpm != NULL);
 611
 612         ip = IPv4(128, 0, 0, 0);
 613         depth = 16;
 614         next_hop_add = 100;
 615
 616         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 617         TEST_LPM_ASSERT(status == 0);
 618
 619         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 620         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 621
 622         status = rte_lpm_delete(lpm, ip, depth);
 623         TEST_LPM_ASSERT(status == 0);
 624
 625         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 626         TEST_LPM_ASSERT(status == -ENOENT);
 627
 628         rte_lpm_delete_all(lpm);
 629
 630         ip = IPv4(128, 0, 0, 0);
 631         depth = 25;
 632         next_hop_add = 100;
 633
 634         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 635         TEST_LPM_ASSERT(status == 0);
 636
 637         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 638         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 639
 640         status = rte_lpm_delete(lpm, ip, depth);
 641         TEST_LPM_ASSERT(status == 0);
 642
 643         rte_lpm_delete_all(lpm);
 644
 645         /* Add rule that extends a TBL24 valid entry & lookup for both rules
 646          * (& delete & lookup) */
 647
 648         ip = IPv4(128, 0, 0, 0);
 649         depth = 24;
 650         next_hop_add = 100;
 651
 652         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 653         TEST_LPM_ASSERT(status == 0);
 654
 655         ip = IPv4(128, 0, 0, 10);
 656         depth = 32;
 657         next_hop_add = 101;
 658
 659         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 660         TEST_LPM_ASSERT(status == 0);
 661
 662         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 663         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 664
 665         ip = IPv4(128, 0, 0, 0);
 666         next_hop_add = 100;
 667
 668         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 669         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 670
 671         ip = IPv4(128, 0, 0, 0);
 672         depth = 24;
 673
 674         status = rte_lpm_delete(lpm, ip, depth);
 675         TEST_LPM_ASSERT(status == 0);
 676
 677         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 678         TEST_LPM_ASSERT(status == -ENOENT);
 679
 680         ip = IPv4(128, 0, 0, 10);
 681         depth = 32;
 682
 683         status = rte_lpm_delete(lpm, ip, depth);
 684         TEST_LPM_ASSERT(status == 0);
 685
 686         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 687         TEST_LPM_ASSERT(status == -ENOENT);
 688
 689         rte_lpm_delete_all(lpm);
 690
 691         /* Add rule that updates the next hop in TBL24 & lookup
 692          * (& delete & lookup) */
 693
 694         ip = IPv4(128, 0, 0, 0);
 695         depth = 24;
 696         next_hop_add = 100;
 697
 698         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 699         TEST_LPM_ASSERT(status == 0);
 700
 701         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 702         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 703
 704         next_hop_add = 101;
 705
 706         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 707         TEST_LPM_ASSERT(status == 0);
 708
 709         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 710         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 711
 712         status = rte_lpm_delete(lpm, ip, depth);
 713         TEST_LPM_ASSERT(status == 0);
 714
 715         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 716         TEST_LPM_ASSERT(status == -ENOENT);
 717
 718         rte_lpm_delete_all(lpm);
 719
 720         /* Add rule that updates the next hop in TBL8 & lookup
 721          * (& delete & lookup) */
 722
 723         ip = IPv4(128, 0, 0, 0);
 724         depth = 32;
 725         next_hop_add = 100;
 726
 727         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 728         TEST_LPM_ASSERT(status == 0);
 729
 730         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 731         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 732
 733         next_hop_add = 101;
 734
 735         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 736         TEST_LPM_ASSERT(status == 0);
 737
 738         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 739         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 740
 741         status = rte_lpm_delete(lpm, ip, depth);
 742         TEST_LPM_ASSERT(status == 0);
 743
 744         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 745         TEST_LPM_ASSERT(status == -ENOENT);
 746
 747         rte_lpm_delete_all(lpm);
 748
 749         /* Delete a rule that is not present in the TBL24 & lookup */
 750
 751         ip = IPv4(128, 0, 0, 0);
 752         depth = 24;
 753
 754         status = rte_lpm_delete(lpm, ip, depth);
 755         TEST_LPM_ASSERT(status < 0);
 756
 757         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 758         TEST_LPM_ASSERT(status == -ENOENT);
 759
 760         rte_lpm_delete_all(lpm);
 761
 762         /* Delete a rule that is not present in the TBL8 & lookup */
 763
 764         ip = IPv4(128, 0, 0, 0);
 765         depth = 32;
 766
 767         status = rte_lpm_delete(lpm, ip, depth);
 768         TEST_LPM_ASSERT(status < 0);
 769
 770         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 771         TEST_LPM_ASSERT(status == -ENOENT);
 772
 773         rte_lpm_free(lpm);
 774
 775         return PASS;
 776 }
 777
 778 /*
 779  * Add two rules, lookup to hit the more specific one, lookup to hit the less
 780  * specific one delete the less specific rule and lookup previous values again;
 781  * add a more specific rule than the existing rule, lookup again
 782  *
 783  * */
 784 int32_t
 785 test11(void)
 786 {
 787
 788         struct rte_lpm *lpm = NULL;
 789         uint32_t ip, next_hop_add, next_hop_return;
 790         uint8_t depth;
 791         int32_t status = 0;
 792
 793         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 794         TEST_LPM_ASSERT(lpm != NULL);
 795
 796         ip = IPv4(128, 0, 0, 0);
 797         depth = 24;
 798         next_hop_add = 100;
 799
 800         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 801         TEST_LPM_ASSERT(status == 0);
 802
 803         ip = IPv4(128, 0, 0, 10);
 804         depth = 32;
 805         next_hop_add = 101;
 806
 807         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 808         TEST_LPM_ASSERT(status == 0);
 809
 810         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 811         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 812
 813         ip = IPv4(128, 0, 0, 0);
 814         next_hop_add = 100;
 815
 816         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 817         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
 818
 819         ip = IPv4(128, 0, 0, 0);
 820         depth = 24;
 821
 822         status = rte_lpm_delete(lpm, ip, depth);
 823         TEST_LPM_ASSERT(status == 0);
 824
 825         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 826         TEST_LPM_ASSERT(status == -ENOENT);
 827
 828         ip = IPv4(128, 0, 0, 10);
 829         depth = 32;
 830
 831         status = rte_lpm_delete(lpm, ip, depth);
 832         TEST_LPM_ASSERT(status == 0);
 833
 834         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 835         TEST_LPM_ASSERT(status == -ENOENT);
 836
 837         rte_lpm_free(lpm);
 838
 839         return PASS;
 840 }
 841
 842 /*
 843  * Add an extended rule (i.e. depth greater than 24, lookup (hit), delete,
 844  * lookup (miss) in a for loop of 1000 times. This will check tbl8 extension
 845  * and contraction.
 846  *
 847  * */
 848
 849 int32_t
 850 test12(void)
 851 {
 852         __m128i ipx4;
 853         uint32_t hop[4];
 854         struct rte_lpm *lpm = NULL;
 855         uint32_t ip, i, next_hop_add, next_hop_return;
 856         uint8_t depth;
 857         int32_t status = 0;
 858
 859         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 860         TEST_LPM_ASSERT(lpm != NULL);
 861
 862         ip = IPv4(128, 0, 0, 0);
 863         depth = 32;
 864         next_hop_add = 100;
 865
 866         for (i = 0; i < 1000; i++) {
 867                 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 868                 TEST_LPM_ASSERT(status == 0);
 869
 870                 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 871                 TEST_LPM_ASSERT((status == 0) &&
 872                                 (next_hop_return == next_hop_add));
 873
 874                 ipx4 = _mm_set_epi32(ip, ip + 1, ip, ip - 1);
 875                 rte_lpm_lookupx4(lpm, ipx4, hop, UINT32_MAX);
 876                 TEST_LPM_ASSERT(hop[0] == UINT32_MAX);
 877                 TEST_LPM_ASSERT(hop[1] == next_hop_add);
 878                 TEST_LPM_ASSERT(hop[2] == UINT32_MAX);
 879                 TEST_LPM_ASSERT(hop[3] == next_hop_add);
 880
 881                 status = rte_lpm_delete(lpm, ip, depth);
 882                 TEST_LPM_ASSERT(status == 0);
 883
 884                 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 885                 TEST_LPM_ASSERT(status == -ENOENT);
 886         }
 887
 888         rte_lpm_free(lpm);
 889
 890         return PASS;
 891 }
 892
 893 /*
 894  * Add a rule to tbl24, lookup (hit), then add a rule that will extend this
 895  * tbl24 entry, lookup (hit). delete the rule that caused the tbl24 extension,
 896  * lookup (miss) and repeat for loop of 1000 times. This will check tbl8
 897  * extension and contraction.
 898  *
 899  * */
 900
 901 int32_t
 902 test13(void)
 903 {
 904         struct rte_lpm *lpm = NULL;
 905         uint32_t ip, i, next_hop_add_1, next_hop_add_2, next_hop_return;
 906         uint8_t depth;
 907         int32_t status = 0;
 908
 909         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
 910         TEST_LPM_ASSERT(lpm != NULL);
 911
 912         ip = IPv4(128, 0, 0, 0);
 913         depth = 24;
 914         next_hop_add_1 = 100;
 915
 916         status = rte_lpm_add(lpm, ip, depth, next_hop_add_1);
 917         TEST_LPM_ASSERT(status == 0);
 918
 919         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 920         TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_1));
 921
 922         depth = 32;
 923         next_hop_add_2 = 101;
 924
 925         for (i = 0; i < 1000; i++) {
 926                 status = rte_lpm_add(lpm, ip, depth, next_hop_add_2);
 927                 TEST_LPM_ASSERT(status == 0);
 928
 929                 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 930                 TEST_LPM_ASSERT((status == 0) &&
 931                                 (next_hop_return == next_hop_add_2));
 932
 933                 status = rte_lpm_delete(lpm, ip, depth);
 934                 TEST_LPM_ASSERT(status == 0);
 935
 936                 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 937                 TEST_LPM_ASSERT((status == 0) &&
 938                                 (next_hop_return == next_hop_add_1));
 939         }
 940
 941         depth = 24;
 942
 943         status = rte_lpm_delete(lpm, ip, depth);
 944         TEST_LPM_ASSERT(status == 0);
 945
 946         status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 947         TEST_LPM_ASSERT(status == -ENOENT);
 948
 949         rte_lpm_free(lpm);
 950
 951         return PASS;
 952 }
 953
 954 /*
 955  * Fore TBL8 extension exhaustion. Add 256 rules that require a tbl8 extension.
 956  * No more tbl8 extensions will be allowed. Now add one more rule that required
 957  * a tbl8 extension and get fail.
 958  * */
 959 int32_t
 960 test14(void)
 961 {
 962
 963         /* We only use depth = 32 in the loop below so we must make sure
 964          * that we have enough storage for all rules at that depth*/
 965
 966         struct rte_lpm *lpm = NULL;
 967         uint32_t ip, next_hop_add, next_hop_return;
 968         uint8_t depth;
 969         int32_t status = 0;
 970
 971         /* Add enough space for 256 rules for every depth */
 972         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, 256 * 32, 0);
 973         TEST_LPM_ASSERT(lpm != NULL);
 974
 975         depth = 32;
 976         next_hop_add = 100;
 977         ip = IPv4(0, 0, 0, 0);
 978
 979         /* Add 256 rules that require a tbl8 extension */
 980         for (; ip <= IPv4(0, 0, 255, 0); ip += 256) {
 981                 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 982                 TEST_LPM_ASSERT(status == 0);
 983
 984                 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
 985                 TEST_LPM_ASSERT((status == 0) &&
 986                                 (next_hop_return == next_hop_add));
 987         }
 988
 989         /* All tbl8 extensions have been used above. Try to add one more and
 990          * we get a fail */
 991         ip = IPv4(1, 0, 0, 0);
 992         depth = 32;
 993
 994         status = rte_lpm_add(lpm, ip, depth, next_hop_add);
 995         TEST_LPM_ASSERT(status < 0);
 996
 997         rte_lpm_free(lpm);
 998
 999         return PASS;
1000 }
1001
1002 /*
1003  * Sequence of operations for find existing lpm table
1004  *
1005  *  - create table
1006  *  - find existing table: hit
1007  *  - find non-existing table: miss
1008  *
1009  */
1010 int32_t
1011 test15(void)
1012 {
1013         struct rte_lpm *lpm = NULL, *result = NULL;
1014
1015         /* Create lpm  */
1016         lpm = rte_lpm_create("lpm_find_existing", SOCKET_ID_ANY, 256 * 32, 0);
1017         TEST_LPM_ASSERT(lpm != NULL);
1018
1019         /* Try to find existing lpm */
1020         result = rte_lpm_find_existing("lpm_find_existing");
1021         TEST_LPM_ASSERT(result == lpm);
1022
1023         /* Try to find non-existing lpm */
1024         result = rte_lpm_find_existing("lpm_find_non_existing");
1025         TEST_LPM_ASSERT(result == NULL);
1026
1027         /* Cleanup. */
1028         rte_lpm_delete_all(lpm);
1029         rte_lpm_free(lpm);
1030
1031         return PASS;
1032 }
1033
1034 /*
1035  * test failure condition of overloading the tbl8 so no more will fit
1036  * Check we get an error return value in that case
1037  */
1038 int32_t
1039 test16(void)
1040 {
1041         uint32_t ip;
1042         struct rte_lpm *lpm = rte_lpm_create(__func__, SOCKET_ID_ANY,
1043                         256 * 32, 0);
1044
1045         /* ip loops through all possibilities for top 24 bits of address */
1046         for (ip = 0; ip < 0xFFFFFF; ip++) {
1047                 /* add an entry within a different tbl8 each time, since
1048                  * depth >24 and the top 24 bits are different */
1049                 if (rte_lpm_add(lpm, (ip << 8) + 0xF0, 30, 0) < 0)
1050                         break;
1051         }
1052
1053         if (ip != RTE_LPM_TBL8_NUM_GROUPS) {
1054                 printf("Error, unexpected failure with filling tbl8 groups\n");
1055                 printf("Failed after %u additions, expected after %u\n",
1056                                 (unsigned)ip, (unsigned)RTE_LPM_TBL8_NUM_GROUPS);
1057         }
1058
1059         rte_lpm_free(lpm);
1060         return 0;
1061 }
1062
1063 /*
1064  * Test for overwriting of tbl8:
1065  *  - add rule /32 and lookup
1066  *  - add new rule /24 and lookup
1067  *      - add third rule /25 and lookup
1068  *      - lookup /32 and /24 rule to ensure the table has not been overwritten.
1069  */
1070 int32_t
1071 test17(void)
1072 {
1073         struct rte_lpm *lpm = NULL;
1074         const uint32_t ip_10_32 = IPv4(10, 10, 10, 2);
1075         const uint32_t ip_10_24 = IPv4(10, 10, 10, 0);
1076         const uint32_t ip_20_25 = IPv4(10, 10, 20, 2);
1077         const uint8_t d_ip_10_32 = 32,
1078                         d_ip_10_24 = 24,
1079                         d_ip_20_25 = 25;
1080         const uint32_t next_hop_ip_10_32 = 100,
1081                         next_hop_ip_10_24 = 105,
1082                         next_hop_ip_20_25 = 111;
1083         uint32_t next_hop_return = 0;
1084         int32_t status = 0;
1085
1086         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
1087         TEST_LPM_ASSERT(lpm != NULL);
1088
1089         if ((status = rte_lpm_add(lpm, ip_10_32, d_ip_10_32,
1090                         next_hop_ip_10_32)) < 0)
1091                 return -1;
1092
1093         status = rte_lpm_lookup(lpm, ip_10_32, &next_hop_return);
1094         uint32_t test_hop_10_32 = next_hop_return;
1095         TEST_LPM_ASSERT(status == 0);
1096         TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_32);
1097
1098         if ((status = rte_lpm_add(lpm, ip_10_24, d_ip_10_24,
1099                         next_hop_ip_10_24)) < 0)
1100                         return -1;
1101
1102         status = rte_lpm_lookup(lpm, ip_10_24, &next_hop_return);
1103         uint32_t test_hop_10_24 = next_hop_return;
1104         TEST_LPM_ASSERT(status == 0);
1105         TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_24);
1106
1107         if ((status = rte_lpm_add(lpm, ip_20_25, d_ip_20_25,
1108                         next_hop_ip_20_25)) < 0)
1109                 return -1;
1110
1111         status = rte_lpm_lookup(lpm, ip_20_25, &next_hop_return);
1112         uint32_t test_hop_20_25 = next_hop_return;
1113         TEST_LPM_ASSERT(status == 0);
1114         TEST_LPM_ASSERT(next_hop_return == next_hop_ip_20_25);
1115
1116         if (test_hop_10_32 == test_hop_10_24) {
1117                 printf("Next hop return equal\n");
1118                 return -1;
1119         }
1120
1121         if (test_hop_10_24 == test_hop_20_25) {
1122                 printf("Next hop return equal\n");
1123                 return -1;
1124         }
1125
1126         status = rte_lpm_lookup(lpm, ip_10_32, &next_hop_return);
1127         TEST_LPM_ASSERT(status == 0);
1128         TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_32);
1129
1130         status = rte_lpm_lookup(lpm, ip_10_24, &next_hop_return);
1131         TEST_LPM_ASSERT(status == 0);
1132         TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_24);
1133
1134         rte_lpm_free(lpm);
1135
1136         return PASS;
1137 }
1138
1139 /*
1140  * Lookup performance test
1141  */
1142
1143 #define ITERATIONS (1 << 10)
1144 #define BATCH_SIZE (1 << 12)
1145 #define BULK_SIZE 32
1146
1147 static void
1148 print_route_distribution(const struct route_rule *table, uint32_t n)
1149 {
1150         unsigned i, j;
1151
1152         printf("Route distribution per prefix width: \n");
1153         printf("DEPTH    QUANTITY (PERCENT)\n");
1154         printf("--------------------------- \n");
1155
1156         /* Count depths. */
1157         for (i = 1; i <= 32; i++) {
1158                 unsigned depth_counter = 0;
1159                 double percent_hits;
1160
1161                 for (j = 0; j < n; j++)
1162                         if (table[j].depth == (uint8_t) i)
1163                                 depth_counter++;
1164
1165                 percent_hits = ((double)depth_counter)/((double)n) * 100;
1166                 printf("%.2u%15u (%.2f)\n", i, depth_counter, percent_hits);
1167         }
1168         printf("\n");
1169 }
1170
1171 int32_t
1172 perf_test(void)
1173 {
1174         struct rte_lpm *lpm = NULL;
1175         uint64_t begin, total_time, lpm_used_entries = 0;
1176         unsigned i, j;
1177         uint32_t next_hop_add = 0xAA, next_hop_return = 0;
1178         int status = 0;
1179         uint64_t cache_line_counter = 0;
1180         int64_t count = 0;
1181
1182         rte_srand(rte_rdtsc());
1183
1184         printf("No. routes = %u\n", (unsigned) NUM_ROUTE_ENTRIES);
1185
1186         print_route_distribution(large_route_table, (uint32_t) NUM_ROUTE_ENTRIES);
1187
1188         lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, 1000000, 0);
1189         TEST_LPM_ASSERT(lpm != NULL);
1190
1191         /* Measue add. */
1192         begin = rte_rdtsc();
1193
1194         for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
1195                 if (rte_lpm_add(lpm, large_route_table[i].ip,
1196                                 large_route_table[i].depth, next_hop_add) == 0)
1197                         status++;
1198         }
1199         /* End Timer. */
1200         total_time = rte_rdtsc() - begin;
1201
1202         printf("Unique added entries = %d\n", status);
1203         /* Obtain add statistics. */
1204         for (i = 0; i < RTE_LPM_TBL24_NUM_ENTRIES; i++) {
1205                 if (lpm->tbl24[i].valid)
1206                         lpm_used_entries++;
1207
1208                 if (i % 32 == 0) {
1209                         if ((uint64_t)count < lpm_used_entries) {
1210                                 cache_line_counter++;
1211                                 count = lpm_used_entries;
1212                         }
1213                 }
1214         }
1215
1216         printf("Used table 24 entries = %u (%g%%)\n",
1217                         (unsigned) lpm_used_entries,
1218                         (lpm_used_entries * 100.0) / RTE_LPM_TBL24_NUM_ENTRIES);
1219         printf("64 byte Cache entries used = %u (%u bytes)\n",
1220                         (unsigned) cache_line_counter, (unsigned) cache_line_counter * 64);
1221
1222         printf("Average LPM Add: %g cycles\n",
1223                         (double)total_time / NUM_ROUTE_ENTRIES);
1224
1225         /* Measure single Lookup */
1226         total_time = 0;
1227         count = 0;
1228
1229         for (i = 0; i < ITERATIONS; i++) {
1230                 static uint32_t ip_batch[BATCH_SIZE];
1231
1232                 for (j = 0; j < BATCH_SIZE; j++)
1233                         ip_batch[j] = rte_rand();
1234
1235                 /* Lookup per batch */
1236                 begin = rte_rdtsc();
1237
1238                 for (j = 0; j < BATCH_SIZE; j++) {
1239                         if (rte_lpm_lookup(lpm, ip_batch[j], &next_hop_return) != 0)
1240                                 count++;
1241                 }
1242
1243                 total_time += rte_rdtsc() - begin;
1244
1245         }
1246         printf("Average LPM Lookup: %.1f cycles (fails = %.1f%%)\n",
1247                         (double)total_time / ((double)ITERATIONS * BATCH_SIZE),
1248                         (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
1249
1250         /* Measure bulk Lookup */
1251         total_time = 0;
1252         count = 0;
1253         for (i = 0; i < ITERATIONS; i++) {
1254                 static uint32_t ip_batch[BATCH_SIZE];
1255                 uint32_t next_hops[BULK_SIZE];
1256
1257                 /* Create array of random IP addresses */
1258                 for (j = 0; j < BATCH_SIZE; j++)
1259                         ip_batch[j] = rte_rand();
1260
1261                 /* Lookup per batch */
1262                 begin = rte_rdtsc();
1263                 for (j = 0; j < BATCH_SIZE; j += BULK_SIZE) {
1264                         unsigned k;
1265                         rte_lpm_lookup_bulk(lpm, &ip_batch[j], next_hops, BULK_SIZE);
1266                         for (k = 0; k < BULK_SIZE; k++)
1267                                 if (unlikely(!(next_hops[k] & RTE_LPM_LOOKUP_SUCCESS)))
1268                                         count++;
1269                 }
1270
1271                 total_time += rte_rdtsc() - begin;
1272         }
1273         printf("BULK LPM Lookup: %.1f cycles (fails = %.1f%%)\n",
1274                         (double)total_time / ((double)ITERATIONS * BATCH_SIZE),
1275                         (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
1276
1277         /* Measure LookupX4 */
1278         total_time = 0;
1279         count = 0;
1280         for (i = 0; i < ITERATIONS; i++) {
1281                 static uint32_t ip_batch[BATCH_SIZE];
1282                 uint32_t next_hops[4];
1283
1284                 /* Create array of random IP addresses */
1285                 for (j = 0; j < BATCH_SIZE; j++)
1286                         ip_batch[j] = rte_rand();
1287
1288                 /* Lookup per batch */
1289                 begin = rte_rdtsc();
1290                 for (j = 0; j < BATCH_SIZE; j += RTE_DIM(next_hops)) {
1291                         unsigned k;
1292                         __m128i ipx4;
1293
1294                         ipx4 = _mm_loadu_si128((__m128i *)(ip_batch + j));
1295                         ipx4 = *(__m128i *)(ip_batch + j);
1296                         rte_lpm_lookupx4(lpm, ipx4, next_hops, UINT32_MAX);
1297                         for (k = 0; k < RTE_DIM(next_hops); k++)
1298                                 if (unlikely(next_hops[k] == UINT32_MAX))
1299                                         count++;
1300                 }
1301
1302                 total_time += rte_rdtsc() - begin;
1303         }
1304         printf("LPM LookupX4: %.1f cycles (fails = %.1f%%)\n",
1305                         (double)total_time / ((double)ITERATIONS * BATCH_SIZE),
1306                         (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
1307
1308         /* Delete */
1309         status = 0;
1310         begin = rte_rdtsc();
1311
1312         for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
1313                 /* rte_lpm_delete(lpm, ip, depth) */
1314                 status += rte_lpm_delete(lpm, large_route_table[i].ip,
1315                                 large_route_table[i].depth);
1316         }
1317
1318         total_time += rte_rdtsc() - begin;
1319
1320         printf("Average LPM Delete: %g cycles\n",
1321                         (double)total_time / NUM_ROUTE_ENTRIES);
1322
1323         rte_lpm_delete_all(lpm);
1324         rte_lpm_free(lpm);
1325
1326         return PASS;
1327 }
1328
1329 /*
1330  * Do all unit and performance tests.
1331  */
1332
1333 static int
1334 test_lpm(void)
1335 {
1336         unsigned i;
1337         int status, global_status = 0;
1338
1339         for (i = 0; i < NUM_LPM_TESTS; i++) {
1340                 status = tests[i]();
1341                 if (status < 0) {
1342                         printf("ERROR: LPM Test %s: FAIL\n", RTE_STR(tests[i]));
1343                         global_status = status;
1344                 }
1345         }
1346
1347         return global_status;
1348 }
1349
1350 static struct test_command lpm_cmd = {
1351         .command = "lpm_autotest",
1352         .callback = test_lpm,
1353 };
1354 REGISTER_TEST_COMMAND(lpm_cmd);