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