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 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 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 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 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 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 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 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 (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 * 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 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 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 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 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 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 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 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 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 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 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 546 rte_swx_table_selector_mailbox_size_get(void) 547 { 548 return sizeof(struct mailbox); 549 } 550 551 int 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