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