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