1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2014 Intel Corporation
10 #include <rte_cycles.h>
11 #include <rte_random.h>
12 #include <rte_branch_prediction.h>
17 #include "test_xmmt_ops.h"
19 #define TEST_LPM_ASSERT(cond) do { \
21 printf("Error at line %d: \n", __LINE__); \
26 #define ITERATIONS (1 << 10)
27 #define BATCH_SIZE (1 << 12)
30 #define MAX_RULE_NUM (1200000)
37 struct route_rule large_route_table
[MAX_RULE_NUM
];
39 static uint32_t num_route_entries
;
40 #define NUM_ROUTE_ENTRIES num_route_entries
48 /* struct route_rule_count defines the total number of rules in following a/b/c
49 * each item in a[]/b[]/c[] is the number of common IP address class A/B/C, not
50 * including the ones for private local network.
52 struct route_rule_count
{
53 uint32_t a
[RTE_LPM_MAX_DEPTH
];
54 uint32_t b
[RTE_LPM_MAX_DEPTH
];
55 uint32_t c
[RTE_LPM_MAX_DEPTH
];
58 /* All following numbers of each depth of each common IP class are just
59 * got from previous large constant table in app/test/test_lpm_routes.h .
60 * In order to match similar performance, they keep same depth and IP
61 * address coverage as previous constant table. These numbers don't
62 * include any private local IP address. As previous large const rule
63 * table was just dumped from a real router, there are no any IP address
66 static struct route_rule_count rule_count
= {
67 .a
= { /* IP class A in which the most significant bit is 0 */
83 3856, /* depth = 16 */
84 3268, /* depth = 17 */
85 5662, /* depth = 18 */
86 17301, /* depth = 19 */
87 22226, /* depth = 20 */
88 11147, /* depth = 21 */
89 16746, /* depth = 22 */
90 17120, /* depth = 23 */
91 77578, /* depth = 24 */
94 1107, /* depth = 27 */
95 1121, /* depth = 28 */
96 2316, /* depth = 29 */
101 .b
= { /* IP class A in which the most 2 significant bits are 10 */
113 168, /* depth = 12 */
114 305, /* depth = 13 */
115 569, /* depth = 14 */
116 1129, /* depth = 15 */
117 50800, /* depth = 16 */
118 1645, /* depth = 17 */
119 1820, /* depth = 18 */
120 3506, /* depth = 19 */
121 3258, /* depth = 20 */
122 3424, /* depth = 21 */
123 4971, /* depth = 22 */
124 6885, /* depth = 23 */
125 39771, /* depth = 24 */
126 424, /* depth = 25 */
127 170, /* depth = 26 */
128 433, /* depth = 27 */
130 366, /* depth = 29 */
131 377, /* depth = 30 */
135 .c
= { /* IP class A in which the most 3 significant bits are 110 */
148 237, /* depth = 13 */
149 1007, /* depth = 14 */
150 1717, /* depth = 15 */
151 14663, /* depth = 16 */
152 8070, /* depth = 17 */
153 16185, /* depth = 18 */
154 48261, /* depth = 19 */
155 36870, /* depth = 20 */
156 33960, /* depth = 21 */
157 50638, /* depth = 22 */
158 61422, /* depth = 23 */
159 466549, /* depth = 24 */
160 1829, /* depth = 25 */
161 4824, /* depth = 26 */
162 4927, /* depth = 27 */
163 5914, /* depth = 28 */
164 10254, /* depth = 29 */
165 4905, /* depth = 30 */
171 static void generate_random_rule_prefix(uint32_t ip_class
, uint8_t depth
)
173 /* IP address class A, the most significant bit is 0 */
174 #define IP_HEAD_MASK_A 0x00000000
175 #define IP_HEAD_BIT_NUM_A 1
177 /* IP address class B, the most significant 2 bits are 10 */
178 #define IP_HEAD_MASK_B 0x80000000
179 #define IP_HEAD_BIT_NUM_B 2
181 /* IP address class C, the most significant 3 bits are 110 */
182 #define IP_HEAD_MASK_C 0xC0000000
183 #define IP_HEAD_BIT_NUM_C 3
185 uint32_t class_depth
;
190 uint32_t fixed_bit_num
;
191 uint32_t ip_head_mask
;
194 struct route_rule
*ptr_rule
;
196 if (ip_class
== IP_CLASS_A
) { /* IP Address class A */
197 fixed_bit_num
= IP_HEAD_BIT_NUM_A
;
198 ip_head_mask
= IP_HEAD_MASK_A
;
199 rule_num
= rule_count
.a
[depth
- 1];
200 } else if (ip_class
== IP_CLASS_B
) { /* IP Address class B */
201 fixed_bit_num
= IP_HEAD_BIT_NUM_B
;
202 ip_head_mask
= IP_HEAD_MASK_B
;
203 rule_num
= rule_count
.b
[depth
- 1];
204 } else { /* IP Address class C */
205 fixed_bit_num
= IP_HEAD_BIT_NUM_C
;
206 ip_head_mask
= IP_HEAD_MASK_C
;
207 rule_num
= rule_count
.c
[depth
- 1];
213 /* the number of rest bits which don't include the most significant
214 * fixed bits for this IP address class
216 class_depth
= depth
- fixed_bit_num
;
218 /* range is the maximum number of rules for this depth and
219 * this IP address class
221 range
= 1 << class_depth
;
223 /* only mask the most depth significant generated bits
224 * except fixed bits for IP address class
228 /* Widen coverage of IP address in generated rules */
229 if (range
<= rule_num
)
232 step
= round((double)range
/ rule_num
);
234 /* Only generate rest bits except the most significant
235 * fixed bits for IP address class
237 start
= lrand48() & mask
;
238 ptr_rule
= &large_route_table
[num_route_entries
];
239 for (k
= 0; k
< rule_num
; k
++) {
240 ptr_rule
->ip
= (start
<< (RTE_LPM_MAX_DEPTH
- depth
))
242 ptr_rule
->depth
= depth
;
244 start
= (start
+ step
) & mask
;
246 num_route_entries
+= rule_num
;
249 static void insert_rule_in_random_pos(uint32_t ip
, uint8_t depth
)
253 struct route_rule tmp
;
258 } while ((try_count
< 10) && (pos
> num_route_entries
));
260 if ((pos
> num_route_entries
) || (pos
>= MAX_RULE_NUM
))
261 pos
= num_route_entries
>> 1;
263 tmp
= large_route_table
[pos
];
264 large_route_table
[pos
].ip
= ip
;
265 large_route_table
[pos
].depth
= depth
;
266 if (num_route_entries
< MAX_RULE_NUM
)
267 large_route_table
[num_route_entries
++] = tmp
;
270 static void generate_large_route_rule_table(void)
275 num_route_entries
= 0;
276 memset(large_route_table
, 0, sizeof(large_route_table
));
278 for (ip_class
= IP_CLASS_A
; ip_class
<= IP_CLASS_C
; ip_class
++) {
279 for (depth
= 1; depth
<= RTE_LPM_MAX_DEPTH
; depth
++) {
280 generate_random_rule_prefix(ip_class
, depth
);
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
288 insert_rule_in_random_pos(IPv4(0, 0, 0, 0), 8);
289 insert_rule_in_random_pos(IPv4(10, 2, 23, 147), 32);
290 insert_rule_in_random_pos(IPv4(192, 168, 100, 10), 24);
291 insert_rule_in_random_pos(IPv4(192, 168, 25, 100), 24);
292 insert_rule_in_random_pos(IPv4(192, 168, 129, 124), 32);
296 print_route_distribution(const struct route_rule
*table
, uint32_t n
)
300 printf("Route distribution per prefix width: \n");
301 printf("DEPTH QUANTITY (PERCENT)\n");
302 printf("--------------------------- \n");
305 for (i
= 1; i
<= 32; i
++) {
306 unsigned depth_counter
= 0;
309 for (j
= 0; j
< n
; j
++)
310 if (table
[j
].depth
== (uint8_t) i
)
313 percent_hits
= ((double)depth_counter
)/((double)n
) * 100;
314 printf("%.2u%15u (%.2f)\n", i
, depth_counter
, percent_hits
);
322 struct rte_lpm
*lpm
= NULL
;
323 struct rte_lpm_config config
;
325 config
.max_rules
= 2000000;
326 config
.number_tbl8s
= 2048;
328 uint64_t begin
, total_time
, lpm_used_entries
= 0;
330 uint32_t next_hop_add
= 0xAA, next_hop_return
= 0;
332 uint64_t cache_line_counter
= 0;
335 rte_srand(rte_rdtsc());
337 generate_large_route_rule_table();
339 printf("No. routes = %u\n", (unsigned) NUM_ROUTE_ENTRIES
);
341 print_route_distribution(large_route_table
, (uint32_t) NUM_ROUTE_ENTRIES
);
343 lpm
= rte_lpm_create(__func__
, SOCKET_ID_ANY
, &config
);
344 TEST_LPM_ASSERT(lpm
!= NULL
);
349 for (i
= 0; i
< NUM_ROUTE_ENTRIES
; i
++) {
350 if (rte_lpm_add(lpm
, large_route_table
[i
].ip
,
351 large_route_table
[i
].depth
, next_hop_add
) == 0)
355 total_time
= rte_rdtsc() - begin
;
357 printf("Unique added entries = %d\n", status
);
358 /* Obtain add statistics. */
359 for (i
= 0; i
< RTE_LPM_TBL24_NUM_ENTRIES
; i
++) {
360 if (lpm
->tbl24
[i
].valid
)
364 if ((uint64_t)count
< lpm_used_entries
) {
365 cache_line_counter
++;
366 count
= lpm_used_entries
;
371 printf("Used table 24 entries = %u (%g%%)\n",
372 (unsigned) lpm_used_entries
,
373 (lpm_used_entries
* 100.0) / RTE_LPM_TBL24_NUM_ENTRIES
);
374 printf("64 byte Cache entries used = %u (%u bytes)\n",
375 (unsigned) cache_line_counter
, (unsigned) cache_line_counter
* 64);
377 printf("Average LPM Add: %g cycles\n",
378 (double)total_time
/ NUM_ROUTE_ENTRIES
);
380 /* Measure single Lookup */
384 for (i
= 0; i
< ITERATIONS
; i
++) {
385 static uint32_t ip_batch
[BATCH_SIZE
];
387 for (j
= 0; j
< BATCH_SIZE
; j
++)
388 ip_batch
[j
] = rte_rand();
390 /* Lookup per batch */
393 for (j
= 0; j
< BATCH_SIZE
; j
++) {
394 if (rte_lpm_lookup(lpm
, ip_batch
[j
], &next_hop_return
) != 0)
398 total_time
+= rte_rdtsc() - begin
;
401 printf("Average LPM Lookup: %.1f cycles (fails = %.1f%%)\n",
402 (double)total_time
/ ((double)ITERATIONS
* BATCH_SIZE
),
403 (count
* 100.0) / (double)(ITERATIONS
* BATCH_SIZE
));
405 /* Measure bulk Lookup */
408 for (i
= 0; i
< ITERATIONS
; i
++) {
409 static uint32_t ip_batch
[BATCH_SIZE
];
410 uint32_t next_hops
[BULK_SIZE
];
412 /* Create array of random IP addresses */
413 for (j
= 0; j
< BATCH_SIZE
; j
++)
414 ip_batch
[j
] = rte_rand();
416 /* Lookup per batch */
418 for (j
= 0; j
< BATCH_SIZE
; j
+= BULK_SIZE
) {
420 rte_lpm_lookup_bulk(lpm
, &ip_batch
[j
], next_hops
, BULK_SIZE
);
421 for (k
= 0; k
< BULK_SIZE
; k
++)
422 if (unlikely(!(next_hops
[k
] & RTE_LPM_LOOKUP_SUCCESS
)))
426 total_time
+= rte_rdtsc() - begin
;
428 printf("BULK LPM Lookup: %.1f cycles (fails = %.1f%%)\n",
429 (double)total_time
/ ((double)ITERATIONS
* BATCH_SIZE
),
430 (count
* 100.0) / (double)(ITERATIONS
* BATCH_SIZE
));
432 /* Measure LookupX4 */
435 for (i
= 0; i
< ITERATIONS
; i
++) {
436 static uint32_t ip_batch
[BATCH_SIZE
];
437 uint32_t next_hops
[4];
439 /* Create array of random IP addresses */
440 for (j
= 0; j
< BATCH_SIZE
; j
++)
441 ip_batch
[j
] = rte_rand();
443 /* Lookup per batch */
445 for (j
= 0; j
< BATCH_SIZE
; j
+= RTE_DIM(next_hops
)) {
449 ipx4
= vect_loadu_sil128((xmm_t
*)(ip_batch
+ j
));
450 ipx4
= *(xmm_t
*)(ip_batch
+ j
);
451 rte_lpm_lookupx4(lpm
, ipx4
, next_hops
, UINT32_MAX
);
452 for (k
= 0; k
< RTE_DIM(next_hops
); k
++)
453 if (unlikely(next_hops
[k
] == UINT32_MAX
))
457 total_time
+= rte_rdtsc() - begin
;
459 printf("LPM LookupX4: %.1f cycles (fails = %.1f%%)\n",
460 (double)total_time
/ ((double)ITERATIONS
* BATCH_SIZE
),
461 (count
* 100.0) / (double)(ITERATIONS
* BATCH_SIZE
));
467 for (i
= 0; i
< NUM_ROUTE_ENTRIES
; i
++) {
468 /* rte_lpm_delete(lpm, ip, depth) */
469 status
+= rte_lpm_delete(lpm
, large_route_table
[i
].ip
,
470 large_route_table
[i
].depth
);
473 total_time
+= rte_rdtsc() - begin
;
475 printf("Average LPM Delete: %g cycles\n",
476 (double)total_time
/ NUM_ROUTE_ENTRIES
);
478 rte_lpm_delete_all(lpm
);
484 REGISTER_TEST_COMMAND(lpm_perf_autotest
, test_lpm_perf
);