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