app/test/test_lpm.c

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