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 *
env_calloc(size_t size,size_t alignment,int numa_node)18 env_calloc(size_t size, size_t alignment, int numa_node)
19 {
20 return rte_zmalloc_socket(NULL, size, alignment, numa_node);
21 }
22
23 static void
env_free(void * start,size_t size __rte_unused)24 env_free(void *start, size_t size __rte_unused)
25 {
26 rte_free(start);
27 }
28
29 #else
30
31 #include <numa.h>
32
33 static void *
env_calloc(size_t size,size_t alignment __rte_unused,int numa_node)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
env_free(void * start,size_t size)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
crc32_u64_generic(uint64_t crc,uint64_t value)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
hash(void * key,void * key_mask,uint32_t key_size,uint32_t seed)90 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 switch (key_size) {
97 case 8:
98 crc0 = crc32_u64(seed, k[0] & m[0]);
99 return crc0;
100
101 case 16:
102 k0 = k[0] & m[0];
103
104 crc0 = crc32_u64(k0, seed);
105 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
106
107 crc0 ^= crc1;
108
109 return crc0;
110
111 case 32:
112 k0 = k[0] & m[0];
113 k2 = k[2] & m[2];
114
115 crc0 = crc32_u64(k0, seed);
116 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
117
118 crc2 = crc32_u64(k2, k[3] & m[3]);
119 crc3 = k2 >> 32;
120
121 crc0 = crc32_u64(crc0, crc1);
122 crc1 = crc32_u64(crc2, crc3);
123
124 crc0 ^= crc1;
125
126 return crc0;
127
128 case 64:
129 k0 = k[0] & m[0];
130 k2 = k[2] & m[2];
131 k5 = k[5] & m[5];
132
133 crc0 = crc32_u64(k0, seed);
134 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
135
136 crc2 = crc32_u64(k2, k[3] & m[3]);
137 crc3 = crc32_u64(k2 >> 32, k[4] & m[4]);
138
139 crc4 = crc32_u64(k5, k[6] & m[6]);
140 crc5 = crc32_u64(k5 >> 32, k[7] & m[7]);
141
142 crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2);
143 crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5);
144
145 crc0 ^= crc1;
146
147 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
rte_swx_table_selector_footprint_get(uint32_t n_groups_max,uint32_t n_members_per_group_max)174 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 group_table_size = n_groups_max * n_members_per_group_max * sizeof(uint32_t);
179
180 members_size = n_members_per_group_max * sizeof(struct group_member_info);
181
182 return sizeof(struct table) + group_table_size + members_size;
183 }
184
185 void
rte_swx_table_selector_free(void * table)186 rte_swx_table_selector_free(void *table)
187 {
188 struct table *t = table;
189
190 if (!t)
191 return;
192
193 free(t->members);
194
195 env_free(t->group_table, t->group_table_size);
196
197 free(t->params.selector_mask);
198
199 free(t);
200 }
201
202 static int
table_create_check(struct rte_swx_table_selector_params * params)203 table_create_check(struct rte_swx_table_selector_params *params)
204 {
205 if (!params)
206 return -1;
207
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))
214 return -EINVAL;
215
216 return 0;
217 }
218
219 static int
table_params_copy(struct table * t,struct rte_swx_table_selector_params * params)220 table_params_copy(struct table *t, struct rte_swx_table_selector_params *params)
221 {
222 uint32_t selector_size, i;
223
224 selector_size = rte_align32pow2(params->selector_size);
225 if (selector_size < 8)
226 selector_size = 8;
227
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);
233
234 for (i = 0; i < 32; i++)
235 if (t->params.n_members_per_group_max == 1U << i)
236 t->n_members_per_group_max_log2 = i;
237
238 /* t->params.selector_mask */
239 t->params.selector_mask = calloc(selector_size, sizeof(uint8_t));
240 if (!t->params.selector_mask)
241 goto error;
242
243 if (params->selector_mask)
244 memcpy(t->params.selector_mask, params->selector_mask, params->selector_size);
245 else
246 memset(t->params.selector_mask, 0xFF, params->selector_size);
247
248 return 0;
249
250 error:
251 free(t->params.selector_mask);
252 t->params.selector_mask = NULL;
253
254 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 *
rte_swx_table_selector_create(struct rte_swx_table_selector_params * params,struct rte_swx_table_selector_group ** groups,int numa_node)263 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 goto error;
275
276 /* Table object. */
277 t = calloc(1, sizeof(struct table));
278 if (!t)
279 goto error;
280
281 /* Parameter copy. */
282 status = table_params_copy(t, params);
283 if (status)
284 goto error;
285
286 /* Group. */
287 group_size = params->n_members_per_group_max * sizeof(uint32_t);
288 t->group_table_size = params->n_groups_max * group_size;
289
290 t->group_table = env_calloc(t->group_table_size, RTE_CACHE_LINE_SIZE, numa_node);
291 if (!t->group_table)
292 goto error;
293
294 t->members = calloc(params->n_members_per_group_max, sizeof(struct group_member_info));
295 if (!t->members)
296 goto error;
297
298 if (groups)
299 for (i = 0; i < params->n_groups_max; i++)
300 if (groups[i]) {
301 status = group_set(t, i, groups[i]);
302 if (status)
303 goto error;
304 }
305
306 return t;
307
308 error:
309 rte_swx_table_selector_free(t);
310 return NULL;
311 }
312
313
314 static int
group_check(struct table * t,struct rte_swx_table_selector_group * group)315 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 if (!group)
321 return 0;
322
323 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 if (n_members >= t->params.n_members_per_group_max)
329 return -ENOSPC;
330
331 /* Check attributes of the current group member. */
332 if (elem->member_id >= t->params.n_members_per_group_max ||
333 !elem->member_weight)
334 return -ENOSPC;
335
336 /* Check against duplicate member IDs. */
337 TAILQ_FOREACH(e, &group->members, node)
338 if (e->member_id == elem->member_id)
339 n++;
340
341 if (n != 1)
342 return -EINVAL;
343
344 /* Update group size. */
345 n_members++;
346 }
347
348 return 0;
349 }
350
351 static uint32_t
members_read(struct group_member_info * members,struct rte_swx_table_selector_group * group)352 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 if (!group)
359 return 0;
360
361 TAILQ_FOREACH(elem, &group->members, node) {
362 struct group_member_info *m = &members[n_members];
363
364 memset(m, 0, sizeof(struct group_member_info));
365
366 m->member_id = elem->member_id;
367 m->member_weight = elem->member_weight;
368 m->member_weight_normalized = elem->member_weight;
369
370 n_members++;
371 }
372
373 return n_members;
374 }
375
376 static uint32_t
members_min_weight_find(struct group_member_info * members,uint32_t n_members)377 members_min_weight_find(struct group_member_info *members, uint32_t n_members)
378 {
379 uint32_t min = UINT32_MAX, i;
380
381 for (i = 0; i < n_members; i++) {
382 struct group_member_info *m = &members[i];
383
384 if (m->member_weight < min)
385 min = m->member_weight;
386 }
387
388 return min;
389 }
390
391 static uint32_t
members_weight_divisor_check(struct group_member_info * members,uint32_t n_members,uint32_t divisor)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 for (i = 0; i < n_members; i++) {
399 struct group_member_info *m = &members[i];
400
401 if (m->member_weight_normalized % divisor)
402 return 0; /* FALSE. */
403 }
404
405 return 1; /* TRUE. */
406 }
407
408 static void
members_weight_divisor_apply(struct group_member_info * members,uint32_t n_members,uint32_t divisor)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 for (i = 0; i < n_members; i++) {
416 struct group_member_info *m = &members[i];
417
418 m->member_weight_normalized /= divisor;
419 }
420 }
421
422 static uint32_t
members_weight_sum(struct group_member_info * members,uint32_t n_members)423 members_weight_sum(struct group_member_info *members, uint32_t n_members)
424 {
425 uint32_t result = 0, i;
426
427 for (i = 0; i < n_members; i++) {
428 struct group_member_info *m = &members[i];
429
430 result += m->member_weight_normalized;
431 }
432
433 return result;
434 }
435
436 static void
members_weight_scale(struct group_member_info * members,uint32_t n_members,uint32_t n_members_per_group_max,uint32_t weight_sum)437 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 multiplier = n_members_per_group_max / weight_sum;
445 remainder = n_members_per_group_max % weight_sum;
446
447 for (i = 0; i < n_members; i++) {
448 struct group_member_info *m = &members[i];
449
450 m->count = m->member_weight_normalized * multiplier;
451 }
452
453 for (i = 0; i < n_members; i++) {
454 struct group_member_info *m = &members[i];
455 uint32_t min;
456
457 min = m->member_weight_normalized;
458 if (remainder < m->member_weight_normalized)
459 min = remainder;
460
461 m->count += min;
462 remainder -= min;
463 if (!remainder)
464 break;
465 }
466 }
467
468 static void
members_write(struct group_member_info * members,uint32_t n_members,uint32_t * group_table)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 for (i = 0; i < n_members; i++) {
476 struct group_member_info *m = &members[i];
477 uint32_t j;
478
479 for (j = 0; j < m->count; j++)
480 group_table[pos++] = m->member_id;
481 }
482 }
483
484 static int
group_set(struct table * t,uint32_t group_id,struct rte_swx_table_selector_group * group)485 group_set(struct table *t,
486 uint32_t group_id,
487 struct rte_swx_table_selector_group *group)
488 {
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;
492 int status = 0;
493
494 /* Check input arguments. */
495 if (group_id >= t->params.n_groups_max)
496 return -EINVAL;
497
498 status = group_check(t, group);
499 if (status)
500 return status;
501
502 /* Read group members. */
503 n_members = members_read(members, group);
504
505 if (!n_members) {
506 memset(gt, 0, t->params.n_members_per_group_max * sizeof(uint32_t));
507
508 return 0;
509 }
510
511 /* Normalize weights. */
512 weight_min = members_min_weight_find(members, n_members);
513
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);
517
518 /* Scale weights. */
519 weight_sum = members_weight_sum(members, n_members);
520 if (weight_sum > t->params.n_members_per_group_max)
521 return -ENOSPC;
522
523 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
rte_swx_table_selector_group_set(void * table,uint32_t group_id,struct rte_swx_table_selector_group * group)532 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 return group_set(t, group_id, group);
539 }
540
541 struct mailbox {
542
543 };
544
545 uint64_t
rte_swx_table_selector_mailbox_size_get(void)546 rte_swx_table_selector_mailbox_size_get(void)
547 {
548 return sizeof(struct mailbox);
549 }
550
551 int
rte_swx_table_selector_select(void * table,void * mailbox __rte_unused,uint8_t ** group_id_buffer,uint8_t ** selector_buffer,uint8_t ** member_id_buffer)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)
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 group_id_ptr = (uint32_t *)&(*group_id_buffer)[t->params.group_id_offset];
562
563 member_id_ptr = (uint32_t *)&(*member_id_buffer)[t->params.member_id_offset];
564
565 group_id = *group_id_ptr & (t->params.n_groups_max - 1);
566
567 selector = hash(&(*selector_buffer)[t->params.selector_offset],
568 t->params.selector_mask,
569 t->params.selector_size,
570 0);
571
572 group_member_index = selector & (t->params.n_members_per_group_max - 1);
573
574 member_id = t->group_table[(group_id << t->n_members_per_group_max_log2) +
575 group_member_index];
576
577 *member_id_ptr = member_id;
578
579 return 1;
580 }
581