Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2021 Intel Corporation
3 : : */
4 : : #include <stdlib.h>
5 : : #include <string.h>
6 : : #include <stdio.h>
7 : : #include <errno.h>
8 : :
9 : : #include <rte_common.h>
10 : :
11 : : #include "rte_swx_table_selector.h"
12 : :
13 : : #ifndef RTE_SWX_TABLE_SELECTOR_HUGE_PAGES_DISABLE
14 : :
15 : : #include <rte_malloc.h>
16 : :
17 : : static void *
18 : : env_calloc(size_t size, size_t alignment, int numa_node)
19 : : {
20 : 0 : return rte_zmalloc_socket(NULL, size, alignment, numa_node);
21 : : }
22 : :
23 : : static void
24 : : env_free(void *start, size_t size __rte_unused)
25 : : {
26 : 0 : rte_free(start);
27 : : }
28 : :
29 : : #else
30 : :
31 : : #include <numa.h>
32 : :
33 : : static void *
34 : : env_calloc(size_t size, size_t alignment __rte_unused, int numa_node)
35 : : {
36 : : void *start;
37 : :
38 : : if (numa_available() == -1)
39 : : return NULL;
40 : :
41 : : start = numa_alloc_onnode(size, numa_node);
42 : : if (!start)
43 : : return NULL;
44 : :
45 : : memset(start, 0, size);
46 : : return start;
47 : : }
48 : :
49 : : static void
50 : : env_free(void *start, size_t size)
51 : : {
52 : : if ((numa_available() == -1) || !start)
53 : : return;
54 : :
55 : : numa_free(start, size);
56 : : }
57 : :
58 : : #endif
59 : :
60 : : #if defined(RTE_ARCH_X86_64)
61 : :
62 : : #include <x86intrin.h>
63 : :
64 : : #define crc32_u64(crc, v) _mm_crc32_u64(crc, v)
65 : :
66 : : #else
67 : :
68 : : static inline uint64_t
69 : : crc32_u64_generic(uint64_t crc, uint64_t value)
70 : : {
71 : : int i;
72 : :
73 : : crc = (crc & 0xFFFFFFFFLLU) ^ value;
74 : : for (i = 63; i >= 0; i--) {
75 : : uint64_t mask;
76 : :
77 : : mask = -(crc & 1LLU);
78 : : crc = (crc >> 1LLU) ^ (0x82F63B78LLU & mask);
79 : : }
80 : :
81 : : return crc;
82 : : }
83 : :
84 : : #define crc32_u64(crc, v) crc32_u64_generic(crc, v)
85 : :
86 : : #endif
87 : :
88 : : /* Key size needs to be one of: 8, 16, 32 or 64. */
89 : : static inline uint32_t
90 : 0 : hash(void *key, void *key_mask, uint32_t key_size, uint32_t seed)
91 : : {
92 : : uint64_t *k = key;
93 : : uint64_t *m = key_mask;
94 : : uint64_t k0, k2, k5, crc0, crc1, crc2, crc3, crc4, crc5;
95 : :
96 [ # # # # : 0 : switch (key_size) {
# ]
97 : 0 : case 8:
98 : 0 : crc0 = crc32_u64(seed, k[0] & m[0]);
99 : 0 : return crc0;
100 : :
101 : 0 : case 16:
102 : 0 : k0 = k[0] & m[0];
103 : :
104 : 0 : crc0 = crc32_u64(k0, seed);
105 : 0 : crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
106 : :
107 : 0 : crc0 ^= crc1;
108 : :
109 : 0 : return crc0;
110 : :
111 : 0 : case 32:
112 : 0 : k0 = k[0] & m[0];
113 : 0 : k2 = k[2] & m[2];
114 : :
115 : 0 : crc0 = crc32_u64(k0, seed);
116 : 0 : crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
117 : :
118 : 0 : crc2 = crc32_u64(k2, k[3] & m[3]);
119 : 0 : crc3 = k2 >> 32;
120 : :
121 : : crc0 = crc32_u64(crc0, crc1);
122 : : crc1 = crc32_u64(crc2, crc3);
123 : :
124 : 0 : crc0 ^= crc1;
125 : :
126 : 0 : return crc0;
127 : :
128 : 0 : case 64:
129 : 0 : k0 = k[0] & m[0];
130 : 0 : k2 = k[2] & m[2];
131 : 0 : k5 = k[5] & m[5];
132 : :
133 : 0 : crc0 = crc32_u64(k0, seed);
134 : 0 : crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
135 : :
136 : 0 : crc2 = crc32_u64(k2, k[3] & m[3]);
137 : 0 : crc3 = crc32_u64(k2 >> 32, k[4] & m[4]);
138 : :
139 : 0 : crc4 = crc32_u64(k5, k[6] & m[6]);
140 : 0 : crc5 = crc32_u64(k5 >> 32, k[7] & m[7]);
141 : :
142 : 0 : crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2);
143 : 0 : crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5);
144 : :
145 : 0 : crc0 ^= crc1;
146 : :
147 : 0 : return crc0;
148 : :
149 : : default:
150 : : crc0 = 0;
151 : : return crc0;
152 : : }
153 : : }
154 : :
155 : : struct group_member_info {
156 : : uint32_t member_id;
157 : : uint32_t member_weight;
158 : : uint32_t member_weight_normalized;
159 : : uint32_t count;
160 : : };
161 : :
162 : : struct table {
163 : : /* Input parameters */
164 : : struct rte_swx_table_selector_params params;
165 : :
166 : : /* Internal. */
167 : : uint32_t *group_table;
168 : : uint64_t group_table_size;
169 : : struct group_member_info *members;
170 : : uint32_t n_members_per_group_max_log2;
171 : : };
172 : :
173 : : uint64_t
174 : 0 : rte_swx_table_selector_footprint_get(uint32_t n_groups_max, uint32_t n_members_per_group_max)
175 : : {
176 : : uint64_t group_table_size, members_size;
177 : :
178 : 0 : group_table_size = n_groups_max * n_members_per_group_max * sizeof(uint32_t);
179 : :
180 : 0 : members_size = n_members_per_group_max * sizeof(struct group_member_info);
181 : :
182 : 0 : return sizeof(struct table) + group_table_size + members_size;
183 : : }
184 : :
185 : : void
186 : 0 : rte_swx_table_selector_free(void *table)
187 : : {
188 : : struct table *t = table;
189 : :
190 [ # # ]: 0 : if (!t)
191 : : return;
192 : :
193 : 0 : free(t->members);
194 : :
195 : 0 : env_free(t->group_table, t->group_table_size);
196 : :
197 : 0 : free(t->params.selector_mask);
198 : :
199 : 0 : free(t);
200 : : }
201 : :
202 : : static int
203 : : table_create_check(struct rte_swx_table_selector_params *params)
204 : : {
205 : 0 : if (!params)
206 : : return -1;
207 : :
208 [ # # ]: 0 : if (!params->selector_size ||
209 : 0 : (params->selector_size > 64) ||
210 [ # # # # ]: 0 : !params->n_groups_max ||
211 : 0 : (params->n_groups_max > 1U << 31) ||
212 [ # # # # ]: 0 : !params->n_members_per_group_max ||
213 : : (params->n_members_per_group_max > 1U << 31))
214 : : return -EINVAL;
215 : :
216 : : return 0;
217 : : }
218 : :
219 : : static int
220 : 0 : table_params_copy(struct table *t, struct rte_swx_table_selector_params *params)
221 : : {
222 : : uint32_t selector_size, i;
223 : :
224 : 0 : selector_size = rte_align32pow2(params->selector_size);
225 : : if (selector_size < 8)
226 : : selector_size = 8;
227 : :
228 : 0 : memcpy(&t->params, params, sizeof(struct rte_swx_table_selector_params));
229 : 0 : t->params.selector_size = selector_size;
230 : 0 : t->params.selector_mask = NULL;
231 : 0 : t->params.n_groups_max = rte_align32pow2(params->n_groups_max);
232 : 0 : t->params.n_members_per_group_max = rte_align32pow2(params->n_members_per_group_max);
233 : :
234 [ # # ]: 0 : for (i = 0; i < 32; i++)
235 [ # # ]: 0 : if (t->params.n_members_per_group_max == 1U << i)
236 : 0 : t->n_members_per_group_max_log2 = i;
237 : :
238 : : /* t->params.selector_mask */
239 : 0 : t->params.selector_mask = calloc(selector_size, sizeof(uint8_t));
240 [ # # ]: 0 : if (!t->params.selector_mask)
241 : 0 : goto error;
242 : :
243 [ # # ]: 0 : if (params->selector_mask)
244 : 0 : memcpy(t->params.selector_mask, params->selector_mask, params->selector_size);
245 : : else
246 : 0 : memset(t->params.selector_mask, 0xFF, params->selector_size);
247 : :
248 : : return 0;
249 : :
250 : : error:
251 : : free(t->params.selector_mask);
252 : 0 : t->params.selector_mask = NULL;
253 : :
254 : 0 : return -ENOMEM;
255 : : }
256 : :
257 : : static int
258 : : group_set(struct table *t,
259 : : uint32_t group_id,
260 : : struct rte_swx_table_selector_group *group);
261 : :
262 : : void *
263 [ # # ]: 0 : rte_swx_table_selector_create(struct rte_swx_table_selector_params *params,
264 : : struct rte_swx_table_selector_group **groups,
265 : : int numa_node)
266 : : {
267 : : struct table *t = NULL;
268 : : uint32_t group_size, i;
269 : : int status;
270 : :
271 : : /* Check input arguments. */
272 : : status = table_create_check(params);
273 : : if (status)
274 : 0 : goto error;
275 : :
276 : : /* Table object. */
277 : 0 : t = calloc(1, sizeof(struct table));
278 [ # # ]: 0 : if (!t)
279 : 0 : goto error;
280 : :
281 : : /* Parameter copy. */
282 : 0 : status = table_params_copy(t, params);
283 [ # # ]: 0 : if (status)
284 : 0 : goto error;
285 : :
286 : : /* Group. */
287 : 0 : group_size = params->n_members_per_group_max * sizeof(uint32_t);
288 : 0 : t->group_table_size = params->n_groups_max * group_size;
289 : :
290 : 0 : t->group_table = env_calloc(t->group_table_size, RTE_CACHE_LINE_SIZE, numa_node);
291 [ # # ]: 0 : if (!t->group_table)
292 : 0 : goto error;
293 : :
294 : 0 : t->members = calloc(params->n_members_per_group_max, sizeof(struct group_member_info));
295 [ # # ]: 0 : if (!t->members)
296 : 0 : goto error;
297 : :
298 [ # # ]: 0 : if (groups)
299 [ # # ]: 0 : for (i = 0; i < params->n_groups_max; i++)
300 [ # # ]: 0 : if (groups[i]) {
301 : 0 : status = group_set(t, i, groups[i]);
302 [ # # ]: 0 : if (status)
303 : 0 : goto error;
304 : : }
305 : :
306 : : return t;
307 : :
308 : 0 : error:
309 : 0 : rte_swx_table_selector_free(t);
310 : 0 : return NULL;
311 : : }
312 : :
313 : :
314 : : static int
315 : 0 : group_check(struct table *t, struct rte_swx_table_selector_group *group)
316 : : {
317 : : struct rte_swx_table_selector_member *elem;
318 : : uint32_t n_members = 0;
319 : :
320 [ # # ]: 0 : if (!group)
321 : : return 0;
322 : :
323 [ # # ]: 0 : TAILQ_FOREACH(elem, &group->members, node) {
324 : : struct rte_swx_table_selector_member *e;
325 : : uint32_t n = 0;
326 : :
327 : : /* Check group size. */
328 [ # # ]: 0 : if (n_members >= t->params.n_members_per_group_max)
329 : : return -ENOSPC;
330 : :
331 : : /* Check attributes of the current group member. */
332 [ # # ]: 0 : if (elem->member_id >= t->params.n_members_per_group_max ||
333 [ # # ]: 0 : !elem->member_weight)
334 : : return -ENOSPC;
335 : :
336 : : /* Check against duplicate member IDs. */
337 [ # # ]: 0 : TAILQ_FOREACH(e, &group->members, node)
338 [ # # ]: 0 : if (e->member_id == elem->member_id)
339 : 0 : n++;
340 : :
341 [ # # ]: 0 : if (n != 1)
342 : : return -EINVAL;
343 : :
344 : : /* Update group size. */
345 : 0 : n_members++;
346 : : }
347 : :
348 : : return 0;
349 : : }
350 : :
351 : : static uint32_t
352 : 0 : members_read(struct group_member_info *members,
353 : : struct rte_swx_table_selector_group *group)
354 : : {
355 : : struct rte_swx_table_selector_member *elem;
356 : : uint32_t n_members = 0;
357 : :
358 [ # # ]: 0 : if (!group)
359 : : return 0;
360 : :
361 [ # # ]: 0 : TAILQ_FOREACH(elem, &group->members, node) {
362 : 0 : struct group_member_info *m = &members[n_members];
363 : :
364 : : memset(m, 0, sizeof(struct group_member_info));
365 : :
366 : 0 : m->member_id = elem->member_id;
367 : 0 : m->member_weight = elem->member_weight;
368 : 0 : m->member_weight_normalized = elem->member_weight;
369 : :
370 : 0 : n_members++;
371 : : }
372 : :
373 : : return n_members;
374 : : }
375 : :
376 : : static uint32_t
377 : : members_min_weight_find(struct group_member_info *members, uint32_t n_members)
378 : : {
379 : : uint32_t min = UINT32_MAX, i;
380 : :
381 [ # # ]: 0 : for (i = 0; i < n_members; i++) {
382 : 0 : struct group_member_info *m = &members[i];
383 : :
384 : 0 : if (m->member_weight < min)
385 : : min = m->member_weight;
386 : : }
387 : :
388 : : return min;
389 : : }
390 : :
391 : : static uint32_t
392 : : members_weight_divisor_check(struct group_member_info *members,
393 : : uint32_t n_members,
394 : : uint32_t divisor)
395 : : {
396 : : uint32_t i;
397 : :
398 [ # # ]: 0 : for (i = 0; i < n_members; i++) {
399 : 0 : struct group_member_info *m = &members[i];
400 : :
401 [ # # ]: 0 : if (m->member_weight_normalized % divisor)
402 : : return 0; /* FALSE. */
403 : : }
404 : :
405 : : return 1; /* TRUE. */
406 : : }
407 : :
408 : : static void
409 : : members_weight_divisor_apply(struct group_member_info *members,
410 : : uint32_t n_members,
411 : : uint32_t divisor)
412 : : {
413 : : uint32_t i;
414 : :
415 [ # # ]: 0 : for (i = 0; i < n_members; i++) {
416 : 0 : struct group_member_info *m = &members[i];
417 : :
418 : 0 : m->member_weight_normalized /= divisor;
419 : : }
420 : : }
421 : :
422 : : static uint32_t
423 : : members_weight_sum(struct group_member_info *members, uint32_t n_members)
424 : : {
425 : : uint32_t result = 0, i;
426 : :
427 [ # # ]: 0 : for (i = 0; i < n_members; i++) {
428 : 0 : struct group_member_info *m = &members[i];
429 : :
430 : 0 : result += m->member_weight_normalized;
431 : : }
432 : :
433 : : return result;
434 : : }
435 : :
436 : : static void
437 : 0 : members_weight_scale(struct group_member_info *members,
438 : : uint32_t n_members,
439 : : uint32_t n_members_per_group_max,
440 : : uint32_t weight_sum)
441 : : {
442 : : uint32_t multiplier, remainder, i;
443 : :
444 : 0 : multiplier = n_members_per_group_max / weight_sum;
445 : 0 : remainder = n_members_per_group_max % weight_sum;
446 : :
447 [ # # ]: 0 : for (i = 0; i < n_members; i++) {
448 : 0 : struct group_member_info *m = &members[i];
449 : :
450 : 0 : m->count = m->member_weight_normalized * multiplier;
451 : : }
452 : :
453 [ # # ]: 0 : for (i = 0; i < n_members; i++) {
454 : 0 : struct group_member_info *m = &members[i];
455 : : uint32_t min;
456 : :
457 : 0 : min = m->member_weight_normalized;
458 : : if (remainder < m->member_weight_normalized)
459 : : min = remainder;
460 : :
461 : 0 : m->count += min;
462 : 0 : remainder -= min;
463 [ # # ]: 0 : if (!remainder)
464 : : break;
465 : : }
466 : 0 : }
467 : :
468 : : static void
469 : : members_write(struct group_member_info *members,
470 : : uint32_t n_members,
471 : : uint32_t *group_table)
472 : : {
473 : : uint32_t pos = 0, i;
474 : :
475 [ # # ]: 0 : for (i = 0; i < n_members; i++) {
476 : 0 : struct group_member_info *m = &members[i];
477 : : uint32_t j;
478 : :
479 [ # # ]: 0 : for (j = 0; j < m->count; j++)
480 : 0 : group_table[pos++] = m->member_id;
481 : : }
482 : : }
483 : :
484 : : static int
485 : 0 : group_set(struct table *t,
486 : : uint32_t group_id,
487 : : struct rte_swx_table_selector_group *group)
488 : : {
489 : 0 : uint32_t *gt = &t->group_table[group_id * t->params.n_members_per_group_max];
490 : 0 : struct group_member_info *members = t->members;
491 : : uint32_t n_members, weight_min, weight_sum, divisor;
492 : : int status = 0;
493 : :
494 : : /* Check input arguments. */
495 [ # # ]: 0 : if (group_id >= t->params.n_groups_max)
496 : : return -EINVAL;
497 : :
498 : 0 : status = group_check(t, group);
499 [ # # ]: 0 : if (status)
500 : : return status;
501 : :
502 : : /* Read group members. */
503 : 0 : n_members = members_read(members, group);
504 : :
505 [ # # ]: 0 : if (!n_members) {
506 : 0 : memset(gt, 0, t->params.n_members_per_group_max * sizeof(uint32_t));
507 : :
508 : 0 : return 0;
509 : : }
510 : :
511 : : /* Normalize weights. */
512 : : weight_min = members_min_weight_find(members, n_members);
513 : :
514 [ # # ]: 0 : for (divisor = 2; divisor <= weight_min; divisor++)
515 [ # # ]: 0 : if (members_weight_divisor_check(members, n_members, divisor))
516 : : members_weight_divisor_apply(members, n_members, divisor);
517 : :
518 : : /* Scale weights. */
519 : : weight_sum = members_weight_sum(members, n_members);
520 [ # # ]: 0 : if (weight_sum > t->params.n_members_per_group_max)
521 : : return -ENOSPC;
522 : :
523 : 0 : members_weight_scale(members, n_members, t->params.n_members_per_group_max, weight_sum);
524 : :
525 : : /* Write group members to the group table. */
526 : : members_write(members, n_members, gt);
527 : :
528 : : return 0;
529 : : }
530 : :
531 : : int
532 : 0 : rte_swx_table_selector_group_set(void *table,
533 : : uint32_t group_id,
534 : : struct rte_swx_table_selector_group *group)
535 : : {
536 : : struct table *t = table;
537 : :
538 : 0 : return group_set(t, group_id, group);
539 : : }
540 : :
541 : : struct mailbox {
542 : :
543 : : };
544 : :
545 : : uint64_t
546 : 0 : rte_swx_table_selector_mailbox_size_get(void)
547 : : {
548 : 0 : return sizeof(struct mailbox);
549 : : }
550 : :
551 : : int
552 : 0 : rte_swx_table_selector_select(void *table,
553 : : void *mailbox __rte_unused,
554 : : uint8_t **group_id_buffer,
555 : : uint8_t **selector_buffer,
556 : : uint8_t **member_id_buffer)
557 : : {
558 : : struct table *t = table;
559 : : uint32_t *group_id_ptr, *member_id_ptr, group_id, member_id, selector, group_member_index;
560 : :
561 : 0 : group_id_ptr = (uint32_t *)&(*group_id_buffer)[t->params.group_id_offset];
562 : :
563 : 0 : member_id_ptr = (uint32_t *)&(*member_id_buffer)[t->params.member_id_offset];
564 : :
565 : 0 : group_id = *group_id_ptr & (t->params.n_groups_max - 1);
566 : :
567 : 0 : selector = hash(&(*selector_buffer)[t->params.selector_offset],
568 : 0 : t->params.selector_mask,
569 : : t->params.selector_size,
570 : : 0);
571 : :
572 : 0 : group_member_index = selector & (t->params.n_members_per_group_max - 1);
573 : :
574 : 0 : member_id = t->group_table[(group_id << t->n_members_per_group_max_log2) +
575 : : group_member_index];
576 : :
577 : 0 : *member_id_ptr = member_id;
578 : :
579 : 0 : return 1;
580 : : }
|