Branch data Line data Source code
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 : 0 : 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 [ # # ]: 0 : 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 : 0 : rule_num = rule_count.a[depth - 1];
201 [ # # ]: 0 : } 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 : 0 : 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 : 0 : rule_num = rule_count.c[depth - 1];
209 : : }
210 : :
211 [ # # ]: 0 : 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 : 0 : 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 : 0 : range = 1 << class_depth;
223 : :
224 : : /* only mask the most depth significant generated bits
225 : : * except fixed bits for IP address class
226 : : */
227 : 0 : mask = range - 1;
228 : :
229 : : /* Widen coverage of IP address in generated rules */
230 [ # # ]: 0 : if (range <= rule_num)
231 : : step = 1;
232 : : else
233 : 0 : 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 : 0 : start = rte_rand() & mask;
239 : 0 : ptr_rule = &large_route_table[num_route_entries];
240 [ # # ]: 0 : for (k = 0; k < rule_num; k++) {
241 : 0 : ptr_rule->ip = (start << (RTE_FIB_MAX_DEPTH - depth))
242 : 0 : | ip_head_mask;
243 : 0 : ptr_rule->depth = depth;
244 : 0 : ptr_rule++;
245 : 0 : start = (start + step) & mask;
246 : : }
247 : 0 : num_route_entries += rule_num;
248 : : }
249 : :
250 : 0 : 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 : 0 : pos = rte_rand();
258 : 0 : try_count++;
259 [ # # # # ]: 0 : } while ((try_count < 10) && (pos > num_route_entries));
260 : :
261 [ # # # # ]: 0 : if ((pos > num_route_entries) || (pos >= MAX_RULE_NUM))
262 : 0 : pos = num_route_entries >> 1;
263 : :
264 : 0 : tmp = large_route_table[pos];
265 : 0 : large_route_table[pos].ip = ip;
266 : 0 : large_route_table[pos].depth = depth;
267 [ # # ]: 0 : if (num_route_entries < MAX_RULE_NUM)
268 : 0 : large_route_table[num_route_entries++] = tmp;
269 : 0 : }
270 : :
271 : 0 : static void generate_large_route_rule_table(void)
272 : : {
273 : : uint32_t ip_class;
274 : : uint8_t depth;
275 : :
276 : 0 : num_route_entries = 0;
277 : : memset(large_route_table, 0, sizeof(large_route_table));
278 : :
279 [ # # ]: 0 : for (ip_class = IP_CLASS_A; ip_class <= IP_CLASS_C; ip_class++) {
280 [ # # ]: 0 : for (depth = 1; depth <= RTE_FIB_MAX_DEPTH; depth++)
281 : 0 : 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 : 0 : insert_rule_in_random_pos(RTE_IPV4(0, 0, 0, 0), 8);
289 : 0 : insert_rule_in_random_pos(RTE_IPV4(10, 2, 23, 147), 32);
290 : 0 : insert_rule_in_random_pos(RTE_IPV4(192, 168, 100, 10), 24);
291 : 0 : insert_rule_in_random_pos(RTE_IPV4(192, 168, 25, 100), 24);
292 : 0 : insert_rule_in_random_pos(RTE_IPV4(192, 168, 129, 124), 32);
293 : 0 : }
294 : :
295 : : static void
296 : 0 : 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 [ # # ]: 0 : for (i = 1; i <= 32; i++) {
306 : : unsigned int depth_counter = 0;
307 : : double percent_hits;
308 : :
309 [ # # ]: 0 : for (j = 0; j < n; j++)
310 [ # # ]: 0 : if (table[j].depth == (uint8_t) i)
311 : 0 : depth_counter++;
312 : :
313 : 0 : percent_hits = ((double)depth_counter)/((double)n) * 100;
314 : : printf("%.2u%15u (%.2f)\n", i, depth_counter, percent_hits);
315 : : }
316 : : printf("\n");
317 : 0 : }
318 : :
319 : : static int
320 : 0 : test_fib_perf(void)
321 : : {
322 : : struct rte_fib *fib = NULL;
323 : 0 : struct rte_fib_conf config = { 0 };
324 : :
325 : 0 : config.max_routes = 2000000;
326 : : config.rib_ext_sz = 0;
327 : 0 : config.type = RTE_FIB_DIR24_8;
328 : : config.default_nh = 0;
329 : 0 : config.dir24_8.nh_sz = RTE_FIB_DIR24_8_4B;
330 : 0 : 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 : 0 : generate_large_route_rule_table();
338 : :
339 : 0 : printf("No. routes = %u\n", (unsigned int) NUM_ROUTE_ENTRIES);
340 : :
341 : 0 : print_route_distribution(large_route_table,
342 : : (uint32_t) NUM_ROUTE_ENTRIES);
343 : :
344 : 0 : fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
345 [ # # ]: 0 : TEST_FIB_ASSERT(fib != NULL);
346 : :
347 : : /* Measure add. */
348 : : begin = rte_rdtsc();
349 : :
350 [ # # ]: 0 : for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
351 [ # # ]: 0 : if (rte_fib_add(fib, large_route_table[i].ip,
352 : 0 : large_route_table[i].depth, next_hop_add) == 0)
353 : 0 : status++;
354 : : }
355 : : /* End Timer. */
356 : 0 : total_time = rte_rdtsc() - begin;
357 : :
358 : : printf("Unique added entries = %d\n", status);
359 : :
360 : 0 : printf("Average FIB Add: %g cycles\n",
361 : 0 : (double)total_time / NUM_ROUTE_ENTRIES);
362 : :
363 : : /* Measure bulk Lookup */
364 : : total_time = 0;
365 : : count = 0;
366 [ # # ]: 0 : 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 [ # # ]: 0 : for (j = 0; j < BATCH_SIZE; j++)
372 : 0 : ip_batch[j] = rte_rand();
373 : :
374 : : /* Lookup per batch */
375 : : begin = rte_rdtsc();
376 [ # # ]: 0 : for (j = 0; j < BATCH_SIZE; j += BULK_SIZE) {
377 : : uint32_t k;
378 : 0 : rte_fib_lookup_bulk(fib, &ip_batch[j], next_hops,
379 : : BULK_SIZE);
380 [ # # ]: 0 : for (k = 0; k < BULK_SIZE; k++)
381 [ # # ]: 0 : if (unlikely(!(next_hops[k] != 0)))
382 : 0 : count++;
383 : : }
384 : :
385 : 0 : total_time += rte_rdtsc() - begin;
386 : : }
387 : 0 : printf("BULK FIB Lookup: %.1f cycles (fails = %.1f%%)\n",
388 : 0 : (double)total_time / ((double)ITERATIONS * BATCH_SIZE),
389 : 0 : (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
390 : :
391 : : /* Delete */
392 : : status = 0;
393 : : begin = rte_rdtsc();
394 [ # # ]: 0 : for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
395 : : /* rte_lpm_delete(lpm, ip, depth) */
396 : 0 : status += rte_fib_delete(fib, large_route_table[i].ip,
397 : 0 : large_route_table[i].depth);
398 : : }
399 : :
400 : 0 : total_time += rte_rdtsc() - begin;
401 : :
402 : 0 : printf("Average FIB Delete: %g cycles\n",
403 : 0 : (double)total_time / NUM_ROUTE_ENTRIES);
404 : :
405 : 0 : rte_fib_free(fib);
406 : :
407 : 0 : return 0;
408 : : }
409 : :
410 : 251 : REGISTER_PERF_TEST(fib_perf_autotest, test_fib_perf);
|
