lib/librte_fib/dir24_8.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
   3  * Copyright(c) 2019 Intel Corporation
   4  */
   5
   6 #include <stdint.h>
   7 #include <stdlib.h>
   8 #include <stdio.h>
   9 #include <string.h>
  10 #include <inttypes.h>
  11
  12 #include <rte_debug.h>
  13 #include <rte_malloc.h>
  14 #include <rte_errno.h>
  15 #include <rte_memory.h>
  16
  17 #include <rte_rib.h>
  18 #include <rte_fib.h>
  19 #include "dir24_8.h"
  20
  21 #define DIR24_8_NAMESIZE        64
  22
  23 #define ROUNDUP(x, y)    RTE_ALIGN_CEIL(x, (1 << (32 - y)))
  24
  25 static inline rte_fib_lookup_fn_t
  26 get_scalar_fn(enum rte_fib_dir24_8_nh_sz nh_sz)
  27 {
  28         switch (nh_sz) {
  29         case RTE_FIB_DIR24_8_1B:
  30                 return dir24_8_lookup_bulk_1b;
  31         case RTE_FIB_DIR24_8_2B:
  32                 return dir24_8_lookup_bulk_2b;
  33         case RTE_FIB_DIR24_8_4B:
  34                 return dir24_8_lookup_bulk_4b;
  35         case RTE_FIB_DIR24_8_8B:
  36                 return dir24_8_lookup_bulk_8b;
  37         default:
  38                 return NULL;
  39         }
  40 }
  41
  42 static inline rte_fib_lookup_fn_t
  43 get_scalar_fn_inlined(enum rte_fib_dir24_8_nh_sz nh_sz)
  44 {
  45         switch (nh_sz) {
  46         case RTE_FIB_DIR24_8_1B:
  47                 return dir24_8_lookup_bulk_0;
  48         case RTE_FIB_DIR24_8_2B:
  49                 return dir24_8_lookup_bulk_1;
  50         case RTE_FIB_DIR24_8_4B:
  51                 return dir24_8_lookup_bulk_2;
  52         case RTE_FIB_DIR24_8_8B:
  53                 return dir24_8_lookup_bulk_3;
  54         default:
  55                 return NULL;
  56         }
  57 }
  58
  59 rte_fib_lookup_fn_t
  60 dir24_8_get_lookup_fn(void *p, enum rte_fib_lookup_type type)
  61 {
  62         enum rte_fib_dir24_8_nh_sz nh_sz;
  63         struct dir24_8_tbl *dp = p;
  64
  65         if (dp == NULL)
  66                 return NULL;
  67
  68         nh_sz = dp->nh_sz;
  69
  70         switch (type) {
  71         case RTE_FIB_LOOKUP_DIR24_8_SCALAR_MACRO:
  72                 return get_scalar_fn(nh_sz);
  73         case RTE_FIB_LOOKUP_DIR24_8_SCALAR_INLINE:
  74                 return get_scalar_fn_inlined(nh_sz);
  75         case RTE_FIB_LOOKUP_DIR24_8_SCALAR_UNI:
  76                 return dir24_8_lookup_bulk_uni;
  77         default:
  78                 return NULL;
  79         }
  80
  81         return NULL;
  82 }
  83
  84 static void
  85 write_to_fib(void *ptr, uint64_t val, enum rte_fib_dir24_8_nh_sz size, int n)
  86 {
  87         int i;
  88         uint8_t *ptr8 = (uint8_t *)ptr;
  89         uint16_t *ptr16 = (uint16_t *)ptr;
  90         uint32_t *ptr32 = (uint32_t *)ptr;
  91         uint64_t *ptr64 = (uint64_t *)ptr;
  92
  93         switch (size) {
  94         case RTE_FIB_DIR24_8_1B:
  95                 for (i = 0; i < n; i++)
  96                         ptr8[i] = (uint8_t)val;
  97                 break;
  98         case RTE_FIB_DIR24_8_2B:
  99                 for (i = 0; i < n; i++)
 100                         ptr16[i] = (uint16_t)val;
 101                 break;
 102         case RTE_FIB_DIR24_8_4B:
 103                 for (i = 0; i < n; i++)
 104                         ptr32[i] = (uint32_t)val;
 105                 break;
 106         case RTE_FIB_DIR24_8_8B:
 107                 for (i = 0; i < n; i++)
 108                         ptr64[i] = (uint64_t)val;
 109                 break;
 110         }
 111 }
 112
 113 static int
 114 tbl8_get_idx(struct dir24_8_tbl *dp)
 115 {
 116         uint32_t i;
 117         int bit_idx;
 118
 119         for (i = 0; (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) &&
 120                         (dp->tbl8_idxes[i] == UINT64_MAX); i++)
 121                 ;
 122         if (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) {
 123                 bit_idx = __builtin_ctzll(~dp->tbl8_idxes[i]);
 124                 dp->tbl8_idxes[i] |= (1ULL << bit_idx);
 125                 return (i << BITMAP_SLAB_BIT_SIZE_LOG2) + bit_idx;
 126         }
 127         return -ENOSPC;
 128 }
 129
 130 static inline void
 131 tbl8_free_idx(struct dir24_8_tbl *dp, int idx)
 132 {
 133         dp->tbl8_idxes[idx >> BITMAP_SLAB_BIT_SIZE_LOG2] &=
 134                 ~(1ULL << (idx & BITMAP_SLAB_BITMASK));
 135 }
 136
 137 static int
 138 tbl8_alloc(struct dir24_8_tbl *dp, uint64_t nh)
 139 {
 140         int64_t tbl8_idx;
 141         uint8_t *tbl8_ptr;
 142
 143         tbl8_idx = tbl8_get_idx(dp);
 144         if (tbl8_idx < 0)
 145                 return tbl8_idx;
 146         tbl8_ptr = (uint8_t *)dp->tbl8 +
 147                 ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) <<
 148                 dp->nh_sz);
 149         /*Init tbl8 entries with nexthop from tbl24*/
 150         write_to_fib((void *)tbl8_ptr, nh|
 151                 DIR24_8_EXT_ENT, dp->nh_sz,
 152                 DIR24_8_TBL8_GRP_NUM_ENT);
 153         dp->cur_tbl8s++;
 154         return tbl8_idx;
 155 }
 156
 157 static void
 158 tbl8_recycle(struct dir24_8_tbl *dp, uint32_t ip, uint64_t tbl8_idx)
 159 {
 160         uint32_t i;
 161         uint64_t nh;
 162         uint8_t *ptr8;
 163         uint16_t *ptr16;
 164         uint32_t *ptr32;
 165         uint64_t *ptr64;
 166
 167         switch (dp->nh_sz) {
 168         case RTE_FIB_DIR24_8_1B:
 169                 ptr8 = &((uint8_t *)dp->tbl8)[tbl8_idx *
 170                                 DIR24_8_TBL8_GRP_NUM_ENT];
 171                 nh = *ptr8;
 172                 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
 173                         if (nh != ptr8[i])
 174                                 return;
 175                 }
 176                 ((uint8_t *)dp->tbl24)[ip >> 8] =
 177                         nh & ~DIR24_8_EXT_ENT;
 178                 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
 179                         ptr8[i] = 0;
 180                 break;
 181         case RTE_FIB_DIR24_8_2B:
 182                 ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx *
 183                                 DIR24_8_TBL8_GRP_NUM_ENT];
 184                 nh = *ptr16;
 185                 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
 186                         if (nh != ptr16[i])
 187                                 return;
 188                 }
 189                 ((uint16_t *)dp->tbl24)[ip >> 8] =
 190                         nh & ~DIR24_8_EXT_ENT;
 191                 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
 192                         ptr16[i] = 0;
 193                 break;
 194         case RTE_FIB_DIR24_8_4B:
 195                 ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx *
 196                                 DIR24_8_TBL8_GRP_NUM_ENT];
 197                 nh = *ptr32;
 198                 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
 199                         if (nh != ptr32[i])
 200                                 return;
 201                 }
 202                 ((uint32_t *)dp->tbl24)[ip >> 8] =
 203                         nh & ~DIR24_8_EXT_ENT;
 204                 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
 205                         ptr32[i] = 0;
 206                 break;
 207         case RTE_FIB_DIR24_8_8B:
 208                 ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx *
 209                                 DIR24_8_TBL8_GRP_NUM_ENT];
 210                 nh = *ptr64;
 211                 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
 212                         if (nh != ptr64[i])
 213                                 return;
 214                 }
 215                 ((uint64_t *)dp->tbl24)[ip >> 8] =
 216                         nh & ~DIR24_8_EXT_ENT;
 217                 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
 218                         ptr64[i] = 0;
 219                 break;
 220         }
 221         tbl8_free_idx(dp, tbl8_idx);
 222         dp->cur_tbl8s--;
 223 }
 224
 225 static int
 226 install_to_fib(struct dir24_8_tbl *dp, uint32_t ledge, uint32_t redge,
 227         uint64_t next_hop)
 228 {
 229         uint64_t        tbl24_tmp;
 230         int     tbl8_idx;
 231         int tmp_tbl8_idx;
 232         uint8_t *tbl8_ptr;
 233         uint32_t len;
 234
 235         len = ((ledge == 0) && (redge == 0)) ? 1 << 24 :
 236                 ((redge & DIR24_8_TBL24_MASK) - ROUNDUP(ledge, 24)) >> 8;
 237
 238         if (((ledge >> 8) != (redge >> 8)) || (len == 1 << 24)) {
 239                 if ((ROUNDUP(ledge, 24) - ledge) != 0) {
 240                         tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz);
 241                         if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
 242                                         DIR24_8_EXT_ENT) {
 243                                 /**
 244                                  * Make sure there is space for two TBL8.
 245                                  * This is necessary when installing range that
 246                                  * needs tbl8 for ledge and redge.
 247                                  */
 248                                 tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
 249                                 tmp_tbl8_idx = tbl8_get_idx(dp);
 250                                 if (tbl8_idx < 0)
 251                                         return -ENOSPC;
 252                                 else if (tmp_tbl8_idx < 0) {
 253                                         tbl8_free_idx(dp, tbl8_idx);
 254                                         return -ENOSPC;
 255                                 }
 256                                 tbl8_free_idx(dp, tmp_tbl8_idx);
 257                                 /*update dir24 entry with tbl8 index*/
 258                                 write_to_fib(get_tbl24_p(dp, ledge,
 259                                         dp->nh_sz), (tbl8_idx << 1)|
 260                                         DIR24_8_EXT_ENT,
 261                                         dp->nh_sz, 1);
 262                         } else
 263                                 tbl8_idx = tbl24_tmp >> 1;
 264                         tbl8_ptr = (uint8_t *)dp->tbl8 +
 265                                 (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) +
 266                                 (ledge & ~DIR24_8_TBL24_MASK)) <<
 267                                 dp->nh_sz);
 268                         /*update tbl8 with new next hop*/
 269                         write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
 270                                 DIR24_8_EXT_ENT,
 271                                 dp->nh_sz, ROUNDUP(ledge, 24) - ledge);
 272                         tbl8_recycle(dp, ledge, tbl8_idx);
 273                 }
 274                 write_to_fib(get_tbl24_p(dp, ROUNDUP(ledge, 24), dp->nh_sz),
 275                         next_hop << 1, dp->nh_sz, len);
 276                 if (redge & ~DIR24_8_TBL24_MASK) {
 277                         tbl24_tmp = get_tbl24(dp, redge, dp->nh_sz);
 278                         if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
 279                                         DIR24_8_EXT_ENT) {
 280                                 tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
 281                                 if (tbl8_idx < 0)
 282                                         return -ENOSPC;
 283                                 /*update dir24 entry with tbl8 index*/
 284                                 write_to_fib(get_tbl24_p(dp, redge,
 285                                         dp->nh_sz), (tbl8_idx << 1)|
 286                                         DIR24_8_EXT_ENT,
 287                                         dp->nh_sz, 1);
 288                         } else
 289                                 tbl8_idx = tbl24_tmp >> 1;
 290                         tbl8_ptr = (uint8_t *)dp->tbl8 +
 291                                 ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) <<
 292                                 dp->nh_sz);
 293                         /*update tbl8 with new next hop*/
 294                         write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
 295                                 DIR24_8_EXT_ENT,
 296                                 dp->nh_sz, redge & ~DIR24_8_TBL24_MASK);
 297                         tbl8_recycle(dp, redge, tbl8_idx);
 298                 }
 299         } else if ((redge - ledge) != 0) {
 300                 tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz);
 301                 if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
 302                                 DIR24_8_EXT_ENT) {
 303                         tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
 304                         if (tbl8_idx < 0)
 305                                 return -ENOSPC;
 306                         /*update dir24 entry with tbl8 index*/
 307                         write_to_fib(get_tbl24_p(dp, ledge, dp->nh_sz),
 308                                 (tbl8_idx << 1)|
 309                                 DIR24_8_EXT_ENT,
 310                                 dp->nh_sz, 1);
 311                 } else
 312                         tbl8_idx = tbl24_tmp >> 1;
 313                 tbl8_ptr = (uint8_t *)dp->tbl8 +
 314                         (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) +
 315                         (ledge & ~DIR24_8_TBL24_MASK)) <<
 316                         dp->nh_sz);
 317                 /*update tbl8 with new next hop*/
 318                 write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
 319                         DIR24_8_EXT_ENT,
 320                         dp->nh_sz, redge - ledge);
 321                 tbl8_recycle(dp, ledge, tbl8_idx);
 322         }
 323         return 0;
 324 }
 325
 326 static int
 327 modify_fib(struct dir24_8_tbl *dp, struct rte_rib *rib, uint32_t ip,
 328         uint8_t depth, uint64_t next_hop)
 329 {
 330         struct rte_rib_node *tmp = NULL;
 331         uint32_t ledge, redge, tmp_ip;
 332         int ret;
 333         uint8_t tmp_depth;
 334
 335         ledge = ip;
 336         do {
 337                 tmp = rte_rib_get_nxt(rib, ip, depth, tmp,
 338                         RTE_RIB_GET_NXT_COVER);
 339                 if (tmp != NULL) {
 340                         rte_rib_get_depth(tmp, &tmp_depth);
 341                         if (tmp_depth == depth)
 342                                 continue;
 343                         rte_rib_get_ip(tmp, &tmp_ip);
 344                         redge = tmp_ip & rte_rib_depth_to_mask(tmp_depth);
 345                         if (ledge == redge) {
 346                                 ledge = redge +
 347                                         (uint32_t)(1ULL << (32 - tmp_depth));
 348                                 continue;
 349                         }
 350                         ret = install_to_fib(dp, ledge, redge,
 351                                 next_hop);
 352                         if (ret != 0)
 353                                 return ret;
 354                         ledge = redge +
 355                                 (uint32_t)(1ULL << (32 - tmp_depth));
 356                 } else {
 357                         redge = ip + (uint32_t)(1ULL << (32 - depth));
 358                         if (ledge == redge)
 359                                 break;
 360                         ret = install_to_fib(dp, ledge, redge,
 361                                 next_hop);
 362                         if (ret != 0)
 363                                 return ret;
 364                 }
 365         } while (tmp);
 366
 367         return 0;
 368 }
 369
 370 int
 371 dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
 372         uint64_t next_hop, int op)
 373 {
 374         struct dir24_8_tbl *dp;
 375         struct rte_rib *rib;
 376         struct rte_rib_node *tmp = NULL;
 377         struct rte_rib_node *node;
 378         struct rte_rib_node *parent;
 379         int ret = 0;
 380         uint64_t par_nh, node_nh;
 381
 382         if ((fib == NULL) || (depth > RTE_FIB_MAXDEPTH))
 383                 return -EINVAL;
 384
 385         dp = rte_fib_get_dp(fib);
 386         rib = rte_fib_get_rib(fib);
 387         RTE_ASSERT((dp != NULL) && (rib != NULL));
 388
 389         if (next_hop > get_max_nh(dp->nh_sz))
 390                 return -EINVAL;
 391
 392         ip &= rte_rib_depth_to_mask(depth);
 393
 394         node = rte_rib_lookup_exact(rib, ip, depth);
 395         switch (op) {
 396         case RTE_FIB_ADD:
 397                 if (node != NULL) {
 398                         rte_rib_get_nh(node, &node_nh);
 399                         if (node_nh == next_hop)
 400                                 return 0;
 401                         ret = modify_fib(dp, rib, ip, depth, next_hop);
 402                         if (ret == 0)
 403                                 rte_rib_set_nh(node, next_hop);
 404                         return 0;
 405                 }
 406                 if (depth > 24) {
 407                         tmp = rte_rib_get_nxt(rib, ip, 24, NULL,
 408                                 RTE_RIB_GET_NXT_COVER);
 409                         if ((tmp == NULL) &&
 410                                 (dp->rsvd_tbl8s >= dp->number_tbl8s))
 411                                 return -ENOSPC;
 412
 413                 }
 414                 node = rte_rib_insert(rib, ip, depth);
 415                 if (node == NULL)
 416                         return -rte_errno;
 417                 rte_rib_set_nh(node, next_hop);
 418                 parent = rte_rib_lookup_parent(node);
 419                 if (parent != NULL) {
 420                         rte_rib_get_nh(parent, &par_nh);
 421                         if (par_nh == next_hop)
 422                                 return 0;
 423                 }
 424                 ret = modify_fib(dp, rib, ip, depth, next_hop);
 425                 if (ret != 0) {
 426                         rte_rib_remove(rib, ip, depth);
 427                         return ret;
 428                 }
 429                 if ((depth > 24) && (tmp == NULL))
 430                         dp->rsvd_tbl8s++;
 431                 return 0;
 432         case RTE_FIB_DEL:
 433                 if (node == NULL)
 434                         return -ENOENT;
 435
 436                 parent = rte_rib_lookup_parent(node);
 437                 if (parent != NULL) {
 438                         rte_rib_get_nh(parent, &par_nh);
 439                         rte_rib_get_nh(node, &node_nh);
 440                         if (par_nh != node_nh)
 441                                 ret = modify_fib(dp, rib, ip, depth, par_nh);
 442                 } else
 443                         ret = modify_fib(dp, rib, ip, depth, dp->def_nh);
 444                 if (ret == 0) {
 445                         rte_rib_remove(rib, ip, depth);
 446                         if (depth > 24) {
 447                                 tmp = rte_rib_get_nxt(rib, ip, 24, NULL,
 448                                         RTE_RIB_GET_NXT_COVER);
 449                                 if (tmp == NULL)
 450                                         dp->rsvd_tbl8s--;
 451                         }
 452                 }
 453                 return ret;
 454         default:
 455                 break;
 456         }
 457         return -EINVAL;
 458 }
 459
 460 void *
 461 dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *fib_conf)
 462 {
 463         char mem_name[DIR24_8_NAMESIZE];
 464         struct dir24_8_tbl *dp;
 465         uint64_t        def_nh;
 466         uint32_t        num_tbl8;
 467         enum rte_fib_dir24_8_nh_sz      nh_sz;
 468
 469         if ((name == NULL) || (fib_conf == NULL) ||
 470                         (fib_conf->dir24_8.nh_sz < RTE_FIB_DIR24_8_1B) ||
 471                         (fib_conf->dir24_8.nh_sz > RTE_FIB_DIR24_8_8B) ||
 472                         (fib_conf->dir24_8.num_tbl8 >
 473                         get_max_nh(fib_conf->dir24_8.nh_sz)) ||
 474                         (fib_conf->dir24_8.num_tbl8 == 0) ||
 475                         (fib_conf->default_nh >
 476                         get_max_nh(fib_conf->dir24_8.nh_sz))) {
 477                 rte_errno = EINVAL;
 478                 return NULL;
 479         }
 480
 481         def_nh = fib_conf->default_nh;
 482         nh_sz = fib_conf->dir24_8.nh_sz;
 483         num_tbl8 = RTE_ALIGN_CEIL(fib_conf->dir24_8.num_tbl8,
 484                         BITMAP_SLAB_BIT_SIZE);
 485
 486         snprintf(mem_name, sizeof(mem_name), "DP_%s", name);
 487         dp = rte_zmalloc_socket(name, sizeof(struct dir24_8_tbl) +
 488                 DIR24_8_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE,
 489                 socket_id);
 490         if (dp == NULL) {
 491                 rte_errno = ENOMEM;
 492                 return NULL;
 493         }
 494
 495         /* Init table with default value */
 496         write_to_fib(dp->tbl24, (def_nh << 1), nh_sz, 1 << 24);
 497
 498         snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp);
 499         uint64_t tbl8_sz = DIR24_8_TBL8_GRP_NUM_ENT * (1ULL << nh_sz) *
 500                         (num_tbl8 + 1);
 501         dp->tbl8 = rte_zmalloc_socket(mem_name, tbl8_sz,
 502                         RTE_CACHE_LINE_SIZE, socket_id);
 503         if (dp->tbl8 == NULL) {
 504                 rte_errno = ENOMEM;
 505                 rte_free(dp);
 506                 return NULL;
 507         }
 508         dp->def_nh = def_nh;
 509         dp->nh_sz = nh_sz;
 510         dp->number_tbl8s = num_tbl8;
 511
 512         snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp);
 513         dp->tbl8_idxes = rte_zmalloc_socket(mem_name,
 514                         RTE_ALIGN_CEIL(dp->number_tbl8s, 64) >> 3,
 515                         RTE_CACHE_LINE_SIZE, socket_id);
 516         if (dp->tbl8_idxes == NULL) {
 517                 rte_errno = ENOMEM;
 518                 rte_free(dp->tbl8);
 519                 rte_free(dp);
 520                 return NULL;
 521         }
 522
 523         return dp;
 524 }
 525
 526 void
 527 dir24_8_free(void *p)
 528 {
 529         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
 530
 531         rte_free(dp->tbl8_idxes);
 532         rte_free(dp->tbl8);
 533         rte_free(dp);
 534 }