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 #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 }