]>
Commit | Line | Data |
---|---|---|
f67539c2 TL |
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 = lrand48() & 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 = lrand48(); | |
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; | |
324 | ||
325 | config.max_routes = 2000000; | |
326 | config.type = RTE_FIB_DIR24_8; | |
327 | config.default_nh = 0; | |
328 | config.dir24_8.nh_sz = RTE_FIB_DIR24_8_4B; | |
329 | config.dir24_8.num_tbl8 = 65535; | |
330 | uint64_t begin, total_time; | |
331 | unsigned int i, j; | |
332 | uint32_t next_hop_add = 0xAA; | |
333 | int status = 0; | |
334 | int64_t count = 0; | |
335 | ||
336 | rte_srand(rte_rdtsc()); | |
337 | ||
338 | generate_large_route_rule_table(); | |
339 | ||
340 | printf("No. routes = %u\n", (unsigned int) NUM_ROUTE_ENTRIES); | |
341 | ||
342 | print_route_distribution(large_route_table, | |
343 | (uint32_t) NUM_ROUTE_ENTRIES); | |
344 | ||
345 | fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); | |
346 | TEST_FIB_ASSERT(fib != NULL); | |
347 | ||
348 | /* Measue add. */ | |
349 | begin = rte_rdtsc(); | |
350 | ||
351 | for (i = 0; i < NUM_ROUTE_ENTRIES; i++) { | |
352 | if (rte_fib_add(fib, large_route_table[i].ip, | |
353 | large_route_table[i].depth, next_hop_add) == 0) | |
354 | status++; | |
355 | } | |
356 | /* End Timer. */ | |
357 | total_time = rte_rdtsc() - begin; | |
358 | ||
359 | printf("Unique added entries = %d\n", status); | |
360 | ||
361 | printf("Average FIB Add: %g cycles\n", | |
362 | (double)total_time / NUM_ROUTE_ENTRIES); | |
363 | ||
364 | /* Measure bulk Lookup */ | |
365 | total_time = 0; | |
366 | count = 0; | |
367 | for (i = 0; i < ITERATIONS; i++) { | |
368 | static uint32_t ip_batch[BATCH_SIZE]; | |
369 | uint64_t next_hops[BULK_SIZE]; | |
370 | ||
371 | /* Create array of random IP addresses */ | |
372 | for (j = 0; j < BATCH_SIZE; j++) | |
373 | ip_batch[j] = rte_rand(); | |
374 | ||
375 | /* Lookup per batch */ | |
376 | begin = rte_rdtsc(); | |
377 | for (j = 0; j < BATCH_SIZE; j += BULK_SIZE) { | |
378 | uint32_t k; | |
379 | rte_fib_lookup_bulk(fib, &ip_batch[j], next_hops, | |
380 | BULK_SIZE); | |
381 | for (k = 0; k < BULK_SIZE; k++) | |
382 | if (unlikely(!(next_hops[k] != 0))) | |
383 | count++; | |
384 | } | |
385 | ||
386 | total_time += rte_rdtsc() - begin; | |
387 | } | |
388 | printf("BULK FIB Lookup: %.1f cycles (fails = %.1f%%)\n", | |
389 | (double)total_time / ((double)ITERATIONS * BATCH_SIZE), | |
390 | (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE)); | |
391 | ||
392 | /* Delete */ | |
393 | status = 0; | |
394 | begin = rte_rdtsc(); | |
395 | for (i = 0; i < NUM_ROUTE_ENTRIES; i++) { | |
396 | /* rte_lpm_delete(lpm, ip, depth) */ | |
397 | status += rte_fib_delete(fib, large_route_table[i].ip, | |
398 | large_route_table[i].depth); | |
399 | } | |
400 | ||
401 | total_time += rte_rdtsc() - begin; | |
402 | ||
403 | printf("Average FIB Delete: %g cycles\n", | |
404 | (double)total_time / NUM_ROUTE_ENTRIES); | |
405 | ||
406 | rte_fib_free(fib); | |
407 | ||
408 | return 0; | |
409 | } | |
410 | ||
411 | REGISTER_TEST_COMMAND(fib_perf_autotest, test_fib_perf); |