xref: /dpdk/lib/table/rte_swx_table_selector.c (revision daa02b5cddbb8e11b31d41e2bf7bb1ae64dcae2f)
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 }
582