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