1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
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
test_fib_perf(void)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
generate_random_rule_prefix(uint32_t ip_class,uint8_t depth)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
insert_rule_in_random_pos(uint32_t ip,uint8_t depth)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
generate_large_route_rule_table(void)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
print_route_distribution(const struct route_rule * table,uint32_t n)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
test_fib_perf(void)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