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