lib/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
  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 }