1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2021 Intel Corporation
9 #include <rte_common.h>
11 #include "rte_swx_table_selector.h"
13 #ifndef RTE_SWX_TABLE_SELECTOR_HUGE_PAGES_DISABLE
15 #include <rte_malloc.h>
18 env_calloc(size_t size, size_t alignment, int numa_node)
20 return rte_zmalloc_socket(NULL, size, alignment, numa_node);
24 env_free(void *start, size_t size __rte_unused)
34 env_calloc(size_t size, size_t alignment __rte_unused, int numa_node)
38 if (numa_available() == -1)
41 start = numa_alloc_onnode(size, numa_node);
45 memset(start, 0, size);
50 env_free(void *start, size_t size)
52 if ((numa_available() == -1) || !start)
55 numa_free(start, size);
60 #if defined(RTE_ARCH_X86_64)
62 #include <x86intrin.h>
64 #define crc32_u64(crc, v) _mm_crc32_u64(crc, v)
68 static inline uint64_t
69 crc32_u64_generic(uint64_t crc, uint64_t value)
73 crc = (crc & 0xFFFFFFFFLLU) ^ value;
74 for (i = 63; i >= 0; i--) {
78 crc = (crc >> 1LLU) ^ (0x82F63B78LLU & mask);
84 #define crc32_u64(crc, v) crc32_u64_generic(crc, v)
88 /* Key size needs to be one of: 8, 16, 32 or 64. */
89 static inline uint32_t
90 hash(void *key, void *key_mask, uint32_t key_size, uint32_t seed)
93 uint64_t *m = key_mask;
94 uint64_t k0, k2, k5, crc0, crc1, crc2, crc3, crc4, crc5;
98 crc0 = crc32_u64(seed, k[0] & m[0]);
104 crc0 = crc32_u64(k0, seed);
105 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
115 crc0 = crc32_u64(k0, seed);
116 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
118 crc2 = crc32_u64(k2, k[3] & m[3]);
121 crc0 = crc32_u64(crc0, crc1);
122 crc1 = crc32_u64(crc2, crc3);
133 crc0 = crc32_u64(k0, seed);
134 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
136 crc2 = crc32_u64(k2, k[3] & m[3]);
137 crc3 = crc32_u64(k2 >> 32, k[4] & m[4]);
139 crc4 = crc32_u64(k5, k[6] & m[6]);
140 crc5 = crc32_u64(k5 >> 32, k[7] & m[7]);
142 crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2);
143 crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5);
155 struct group_member_info {
157 uint32_t member_weight;
158 uint32_t member_weight_normalized;
163 /* Input parameters */
164 struct rte_swx_table_selector_params params;
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;
174 rte_swx_table_selector_footprint_get(uint32_t n_groups_max, uint32_t n_members_per_group_max)
176 uint64_t group_table_size, members_size;
178 group_table_size = n_groups_max * n_members_per_group_max * sizeof(uint32_t);
180 members_size = n_members_per_group_max * sizeof(struct group_member_info);
182 return sizeof(struct table) + group_table_size + members_size;
186 rte_swx_table_selector_free(void *table)
188 struct table *t = table;
195 env_free(t->group_table, t->group_table_size);
197 free(t->params.selector_mask);
203 table_create_check(struct rte_swx_table_selector_params *params)
208 if (!params->selector_size ||
209 (params->selector_size > 64) ||
210 !params->n_groups_max ||
211 (params->n_groups_max > 1U << 31) ||
212 !params->n_members_per_group_max ||
213 (params->n_members_per_group_max > 1U << 31))
220 table_params_copy(struct table *t, struct rte_swx_table_selector_params *params)
222 uint32_t selector_size, i;
224 selector_size = rte_align32pow2(params->selector_size);
225 if (selector_size < 8)
228 memcpy(&t->params, params, sizeof(struct rte_swx_table_selector_params));
229 t->params.selector_size = selector_size;
230 t->params.selector_mask = NULL;
231 t->params.n_groups_max = rte_align32pow2(params->n_groups_max);
232 t->params.n_members_per_group_max = rte_align32pow2(params->n_members_per_group_max);
234 for (i = 0; i < 32; i++)
235 if (params->n_members_per_group_max == 1U << i)
236 t->n_members_per_group_max_log2 = i;
238 /* t->params.selector_mask */
239 t->params.selector_mask = calloc(selector_size, sizeof(uint8_t));
240 if (!t->params.selector_mask)
243 if (params->selector_mask)
244 memcpy(t->params.selector_mask, params->selector_mask, params->selector_size);
246 memset(t->params.selector_mask, 0xFF, params->selector_size);
251 free(t->params.selector_mask);
252 t->params.selector_mask = NULL;
258 group_set(struct table *t,
260 struct rte_swx_table_selector_group *group);
263 rte_swx_table_selector_create(struct rte_swx_table_selector_params *params,
264 struct rte_swx_table_selector_group **groups,
267 struct table *t = NULL;
268 uint32_t group_size, i;
271 /* Check input arguments. */
272 status = table_create_check(params);
277 t = calloc(1, sizeof(struct table));
281 /* Parameter copy. */
282 status = table_params_copy(t, params);
287 group_size = params->n_members_per_group_max * sizeof(uint32_t);
288 t->group_table_size = params->n_groups_max * group_size;
290 t->group_table = env_calloc(t->group_table_size, RTE_CACHE_LINE_SIZE, numa_node);
294 t->members = calloc(params->n_members_per_group_max, sizeof(struct group_member_info));
299 for (i = 0; i < params->n_groups_max; i++)
301 status = group_set(t, i, groups[i]);
309 rte_swx_table_selector_free(t);
315 group_check(struct table *t, struct rte_swx_table_selector_group *group)
317 struct rte_swx_table_selector_member *elem;
318 uint32_t n_members = 0;
323 TAILQ_FOREACH(elem, &group->members, node) {
324 struct rte_swx_table_selector_member *e;
327 /* Check group size. */
328 if (n_members >= t->params.n_members_per_group_max)
331 /* Check attributes of the current group member. */
332 if (elem->member_id >= t->params.n_members_per_group_max ||
333 !elem->member_weight)
336 /* Check against duplicate member IDs. */
337 TAILQ_FOREACH(e, &group->members, node)
338 if (e->member_id == elem->member_id)
344 /* Update group size. */
352 members_read(struct group_member_info *members,
353 struct rte_swx_table_selector_group *group)
355 struct rte_swx_table_selector_member *elem;
356 uint32_t n_members = 0;
361 TAILQ_FOREACH(elem, &group->members, node) {
362 struct group_member_info *m = &members[n_members];
364 memset(m, 0, sizeof(struct group_member_info));
366 m->member_id = elem->member_id;
367 m->member_weight = elem->member_weight;
368 m->member_weight_normalized = elem->member_weight;
377 members_min_weight_find(struct group_member_info *members, uint32_t n_members)
379 uint32_t min = UINT32_MAX, i;
381 for (i = 0; i < n_members; i++) {
382 struct group_member_info *m = &members[i];
384 if (m->member_weight < min)
385 min = m->member_weight;
392 members_weight_divisor_check(struct group_member_info *members,
398 for (i = 0; i < n_members; i++) {
399 struct group_member_info *m = &members[i];
401 if (m->member_weight_normalized % divisor)
402 return 0; /* FALSE. */
405 return 1; /* TRUE. */
409 members_weight_divisor_apply(struct group_member_info *members,
415 for (i = 0; i < n_members; i++) {
416 struct group_member_info *m = &members[i];
418 m->member_weight_normalized /= divisor;
423 members_weight_sum(struct group_member_info *members, uint32_t n_members)
425 uint32_t result = 0, i;
427 for (i = 0; i < n_members; i++) {
428 struct group_member_info *m = &members[i];
430 result += m->member_weight_normalized;
437 members_weight_scale(struct group_member_info *members,
439 uint32_t n_members_per_group_max,
442 uint32_t multiplier, remainder, i;
444 multiplier = n_members_per_group_max / weight_sum;
445 remainder = n_members_per_group_max % weight_sum;
447 for (i = 0; i < n_members; i++) {
448 struct group_member_info *m = &members[i];
450 m->count = m->member_weight_normalized * multiplier;
453 for (i = 0; i < n_members; i++) {
454 struct group_member_info *m = &members[i];
457 min = m->member_weight_normalized;
458 if (remainder < m->member_weight_normalized)
469 members_write(struct group_member_info *members,
471 uint32_t *group_table)
475 for (i = 0; i < n_members; i++) {
476 struct group_member_info *m = &members[i];
479 for (j = 0; j < m->count; j++)
480 group_table[pos++] = m->member_id;
485 group_set(struct table *t,
487 struct rte_swx_table_selector_group *group)
489 uint32_t *gt = &t->group_table[group_id * t->params.n_members_per_group_max];
490 struct group_member_info *members = t->members;
491 uint32_t n_members, weight_min, weight_sum, divisor;
494 /* Check input arguments. */
495 if (group_id >= t->params.n_groups_max)
498 status = group_check(t, group);
502 /* Read group members. */
503 n_members = members_read(members, group);
506 memset(gt, 0, t->params.n_members_per_group_max * sizeof(uint32_t));
511 /* Normalize weights. */
512 weight_min = members_min_weight_find(members, n_members);
514 for (divisor = 2; divisor <= weight_min; divisor++)
515 if (members_weight_divisor_check(members, n_members, divisor))
516 members_weight_divisor_apply(members, n_members, divisor);
519 weight_sum = members_weight_sum(members, n_members);
520 if (weight_sum > t->params.n_members_per_group_max)
523 members_weight_scale(members, n_members, t->params.n_members_per_group_max, weight_sum);
525 /* Write group members to the group table. */
526 members_write(members, n_members, gt);
532 rte_swx_table_selector_group_set(void *table,
534 struct rte_swx_table_selector_group *group)
536 struct table *t = table;
538 return group_set(t, group_id, group);
546 rte_swx_table_selector_mailbox_size_get(void)
548 return sizeof(struct mailbox);
552 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)
558 struct table *t = table;
559 uint32_t *group_id_ptr, *member_id_ptr, group_id, member_id, selector, group_member_index;
561 group_id_ptr = (uint32_t *)&(*group_id_buffer)[t->params.group_id_offset];
563 member_id_ptr = (uint32_t *)&(*member_id_buffer)[t->params.member_id_offset];
565 group_id = *group_id_ptr & (t->params.n_groups_max - 1);
567 selector = hash(&(*selector_buffer)[t->params.selector_offset],
568 t->params.selector_mask,
569 t->params.selector_size,
572 group_member_index = selector & (t->params.n_members_per_group_max - 1);
574 member_id = t->group_table[(group_id << t->n_members_per_group_max_log2) +
577 *member_id_ptr = member_id;