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