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_prefetch.h>
  15 #include <rte_errno.h>
  16 #include <rte_memory.h>
  17 #include <rte_branch_prediction.h>
  18
  19 #include <rte_fib.h>
  20 #include <rte_rib.h>
  21 #include "dir24_8.h"
  22
  23 #define DIR24_8_NAMESIZE        64
  24
  25 #define DIR24_8_TBL24_NUM_ENT           (1 << 24)
  26 #define DIR24_8_TBL8_GRP_NUM_ENT        256U
  27 #define DIR24_8_EXT_ENT                 1
  28 #define DIR24_8_TBL24_MASK              0xffffff00
  29
  30 #define BITMAP_SLAB_BIT_SIZE_LOG2       6
  31 #define BITMAP_SLAB_BIT_SIZE            (1 << BITMAP_SLAB_BIT_SIZE_LOG2)
  32 #define BITMAP_SLAB_BITMASK             (BITMAP_SLAB_BIT_SIZE - 1)
  33
  34 struct dir24_8_tbl {
  35         uint32_t        number_tbl8s;   /**< Total number of tbl8s */
  36         uint32_t        rsvd_tbl8s;     /**< Number of reserved tbl8s */
  37         uint32_t        cur_tbl8s;      /**< Current number of tbl8s */
  38         enum rte_fib_dir24_8_nh_sz      nh_sz;  /**< Size of nexthop entry */
  39         uint64_t        def_nh;         /**< Default next hop */
  40         uint64_t        *tbl8;          /**< tbl8 table. */
  41         uint64_t        *tbl8_idxes;    /**< bitmap containing free tbl8 idxes*/
  42         /* tbl24 table. */
  43         __extension__ uint64_t  tbl24[0] __rte_cache_aligned;
  44 };
  45
  46 #define ROUNDUP(x, y)    RTE_ALIGN_CEIL(x, (1 << (32 - y)))
  47
  48 enum lookup_type {
  49         MACRO,
  50         INLINE,
  51         UNI
  52 };
  53 enum lookup_type test_lookup = MACRO;
  54
  55 static inline void *
  56 get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
  57 {
  58         return (void *)&((uint8_t *)dp->tbl24)[(ip &
  59                 DIR24_8_TBL24_MASK) >> (8 - nh_sz)];
  60 }
  61
  62 static inline  uint8_t
  63 bits_in_nh(uint8_t nh_sz)
  64 {
  65         return 8 * (1 << nh_sz);
  66 }
  67
  68 static inline uint64_t
  69 get_max_nh(uint8_t nh_sz)
  70 {
  71         return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1);
  72 }
  73
  74 static  inline uint32_t
  75 get_tbl24_idx(uint32_t ip)
  76 {
  77         return ip >> 8;
  78 }
  79
  80 static  inline uint32_t
  81 get_tbl8_idx(uint32_t res, uint32_t ip)
  82 {
  83         return (res >> 1) * DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip;
  84 }
  85
  86 static inline uint64_t
  87 lookup_msk(uint8_t nh_sz)
  88 {
  89         return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1;
  90 }
  91
  92 static inline uint8_t
  93 get_psd_idx(uint32_t val, uint8_t nh_sz)
  94 {
  95         return val & ((1 << (3 - nh_sz)) - 1);
  96 }
  97
  98 static inline uint32_t
  99 get_tbl_idx(uint32_t val, uint8_t nh_sz)
 100 {
 101         return val >> (3 - nh_sz);
 102 }
 103
 104 static inline uint64_t
 105 get_tbl24(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
 106 {
 107         return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >>
 108                 (get_psd_idx(get_tbl24_idx(ip), nh_sz) *
 109                 bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
 110 }
 111
 112 static inline uint64_t
 113 get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz)
 114 {
 115         return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >>
 116                 (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) *
 117                 bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
 118 }
 119
 120 static inline int
 121 is_entry_extended(uint64_t ent)
 122 {
 123         return (ent & DIR24_8_EXT_ENT) == DIR24_8_EXT_ENT;
 124 }
 125
 126 #define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz)                 \
 127 static void dir24_8_lookup_bulk_##suffix(void *p, const uint32_t *ips,  \
 128         uint64_t *next_hops, const unsigned int n)                      \
 129 {                                                                       \
 130         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;               \
 131         uint64_t tmp;                                                   \
 132         uint32_t i;                                                     \
 133         uint32_t prefetch_offset =                                      \
 134                 RTE_MIN((unsigned int)bulk_prefetch, n);                \
 135                                                                         \
 136         for (i = 0; i < prefetch_offset; i++)                           \
 137                 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));          \
 138         for (i = 0; i < (n - prefetch_offset); i++) {                   \
 139                 rte_prefetch0(get_tbl24_p(dp,                           \
 140                         ips[i + prefetch_offset], nh_sz));              \
 141                 tmp = ((type *)dp->tbl24)[ips[i] >> 8];                 \
 142                 if (unlikely(is_entry_extended(tmp)))                   \
 143                         tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] +      \
 144                                 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
 145                 next_hops[i] = tmp >> 1;                                \
 146         }                                                               \
 147         for (; i < n; i++) {                                            \
 148                 tmp = ((type *)dp->tbl24)[ips[i] >> 8];                 \
 149                 if (unlikely(is_entry_extended(tmp)))                   \
 150                         tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] +      \
 151                                 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
 152                 next_hops[i] = tmp >> 1;                                \
 153         }                                                               \
 154 }                                                                       \
 155
 156 LOOKUP_FUNC(1b, uint8_t, 5, 0)
 157 LOOKUP_FUNC(2b, uint16_t, 6, 1)
 158 LOOKUP_FUNC(4b, uint32_t, 15, 2)
 159 LOOKUP_FUNC(8b, uint64_t, 12, 3)
 160
 161 static inline void
 162 dir24_8_lookup_bulk(struct dir24_8_tbl *dp, const uint32_t *ips,
 163         uint64_t *next_hops, const unsigned int n, uint8_t nh_sz)
 164 {
 165         uint64_t tmp;
 166         uint32_t i;
 167         uint32_t prefetch_offset = RTE_MIN(15U, n);
 168
 169         for (i = 0; i < prefetch_offset; i++)
 170                 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
 171         for (i = 0; i < (n - prefetch_offset); i++) {
 172                 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
 173                         nh_sz));
 174                 tmp = get_tbl24(dp, ips[i], nh_sz);
 175                 if (unlikely(is_entry_extended(tmp)))
 176                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
 177
 178                 next_hops[i] = tmp >> 1;
 179         }
 180         for (; i < n; i++) {
 181                 tmp = get_tbl24(dp, ips[i], nh_sz);
 182                 if (unlikely(is_entry_extended(tmp)))
 183                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
 184
 185                 next_hops[i] = tmp >> 1;
 186         }
 187 }
 188
 189 static void
 190 dir24_8_lookup_bulk_0(void *p, const uint32_t *ips,
 191         uint64_t *next_hops, const unsigned int n)
 192 {
 193         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
 194
 195         dir24_8_lookup_bulk(dp, ips, next_hops, n, 0);
 196 }
 197
 198 static void
 199 dir24_8_lookup_bulk_1(void *p, const uint32_t *ips,
 200         uint64_t *next_hops, const unsigned int n)
 201 {
 202         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
 203
 204         dir24_8_lookup_bulk(dp, ips, next_hops, n, 1);
 205 }
 206
 207 static void
 208 dir24_8_lookup_bulk_2(void *p, const uint32_t *ips,
 209         uint64_t *next_hops, const unsigned int n)
 210 {
 211         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
 212
 213         dir24_8_lookup_bulk(dp, ips, next_hops, n, 2);
 214 }
 215
 216 static void
 217 dir24_8_lookup_bulk_3(void *p, const uint32_t *ips,
 218         uint64_t *next_hops, const unsigned int n)
 219 {
 220         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
 221
 222         dir24_8_lookup_bulk(dp, ips, next_hops, n, 3);
 223 }
 224
 225 static void
 226 dir24_8_lookup_bulk_uni(void *p, const uint32_t *ips,
 227         uint64_t *next_hops, const unsigned int n)
 228 {
 229         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
 230         uint64_t tmp;
 231         uint32_t i;
 232         uint32_t prefetch_offset = RTE_MIN(15U, n);
 233         uint8_t nh_sz = dp->nh_sz;
 234
 235         for (i = 0; i < prefetch_offset; i++)
 236                 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
 237         for (i = 0; i < (n - prefetch_offset); i++) {
 238                 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
 239                         nh_sz));
 240                 tmp = get_tbl24(dp, ips[i], nh_sz);
 241                 if (unlikely(is_entry_extended(tmp)))
 242                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
 243
 244                 next_hops[i] = tmp >> 1;
 245         }
 246         for (; i < n; i++) {
 247                 tmp = get_tbl24(dp, ips[i], nh_sz);
 248                 if (unlikely(is_entry_extended(tmp)))
 249                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
 250
 251                 next_hops[i] = tmp >> 1;
 252         }
 253 }
 254
 255 rte_fib_lookup_fn_t
 256 dir24_8_get_lookup_fn(struct rte_fib_conf *fib_conf)
 257 {
 258         enum rte_fib_dir24_8_nh_sz nh_sz = fib_conf->dir24_8.nh_sz;
 259
 260         if (test_lookup == MACRO) {
 261                 switch (nh_sz) {
 262                 case RTE_FIB_DIR24_8_1B:
 263                         return dir24_8_lookup_bulk_1b;
 264                 case RTE_FIB_DIR24_8_2B:
 265                         return dir24_8_lookup_bulk_2b;
 266                 case RTE_FIB_DIR24_8_4B:
 267                         return dir24_8_lookup_bulk_4b;
 268                 case RTE_FIB_DIR24_8_8B:
 269                         return dir24_8_lookup_bulk_8b;
 270                 }
 271         } else if (test_lookup == INLINE) {
 272                 switch (nh_sz) {
 273                 case RTE_FIB_DIR24_8_1B:
 274                         return dir24_8_lookup_bulk_0;
 275                 case RTE_FIB_DIR24_8_2B:
 276                         return dir24_8_lookup_bulk_1;
 277                 case RTE_FIB_DIR24_8_4B:
 278                         return dir24_8_lookup_bulk_2;
 279                 case RTE_FIB_DIR24_8_8B:
 280                         return dir24_8_lookup_bulk_3;
 281                 }
 282         } else
 283                 return dir24_8_lookup_bulk_uni;
 284         return NULL;
 285 }
 286
 287 static void
 288 write_to_fib(void *ptr, uint64_t val, enum rte_fib_dir24_8_nh_sz size, int n)
 289 {
 290         int i;
 291         uint8_t *ptr8 = (uint8_t *)ptr;
 292         uint16_t *ptr16 = (uint16_t *)ptr;
 293         uint32_t *ptr32 = (uint32_t *)ptr;
 294         uint64_t *ptr64 = (uint64_t *)ptr;
 295
 296         switch (size) {
 297         case RTE_FIB_DIR24_8_1B:
 298                 for (i = 0; i < n; i++)
 299                         ptr8[i] = (uint8_t)val;
 300                 break;
 301         case RTE_FIB_DIR24_8_2B:
 302                 for (i = 0; i < n; i++)
 303                         ptr16[i] = (uint16_t)val;
 304                 break;
 305         case RTE_FIB_DIR24_8_4B:
 306                 for (i = 0; i < n; i++)
 307                         ptr32[i] = (uint32_t)val;
 308                 break;
 309         case RTE_FIB_DIR24_8_8B:
 310                 for (i = 0; i < n; i++)
 311                         ptr64[i] = (uint64_t)val;
 312                 break;
 313         }
 314 }
 315
 316 static int
 317 tbl8_get_idx(struct dir24_8_tbl *dp)
 318 {
 319         uint32_t i;
 320         int bit_idx;
 321
 322         for (i = 0; (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) &&
 323                         (dp->tbl8_idxes[i] == UINT64_MAX); i++)
 324                 ;
 325         if (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) {
 326                 bit_idx = __builtin_ctzll(~dp->tbl8_idxes[i]);
 327                 dp->tbl8_idxes[i] |= (1ULL << bit_idx);
 328                 return (i << BITMAP_SLAB_BIT_SIZE_LOG2) + bit_idx;
 329         }
 330         return -ENOSPC;
 331 }
 332
 333 static inline void
 334 tbl8_free_idx(struct dir24_8_tbl *dp, int idx)
 335 {
 336         dp->tbl8_idxes[idx >> BITMAP_SLAB_BIT_SIZE_LOG2] &=
 337                 ~(1ULL << (idx & BITMAP_SLAB_BITMASK));
 338 }
 339
 340 static int
 341 tbl8_alloc(struct dir24_8_tbl *dp, uint64_t nh)
 342 {
 343         int64_t tbl8_idx;
 344         uint8_t *tbl8_ptr;
 345
 346         tbl8_idx = tbl8_get_idx(dp);
 347         if (tbl8_idx < 0)
 348                 return tbl8_idx;
 349         tbl8_ptr = (uint8_t *)dp->tbl8 +
 350                 ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) <<
 351                 dp->nh_sz);
 352         /*Init tbl8 entries with nexthop from tbl24*/
 353         write_to_fib((void *)tbl8_ptr, nh|
 354                 DIR24_8_EXT_ENT, dp->nh_sz,
 355                 DIR24_8_TBL8_GRP_NUM_ENT);
 356         dp->cur_tbl8s++;
 357         return tbl8_idx;
 358 }
 359
 360 static void
 361 tbl8_recycle(struct dir24_8_tbl *dp, uint32_t ip, uint64_t tbl8_idx)
 362 {
 363         uint32_t i;
 364         uint64_t nh;
 365         uint8_t *ptr8;
 366         uint16_t *ptr16;
 367         uint32_t *ptr32;
 368         uint64_t *ptr64;
 369
 370         switch (dp->nh_sz) {
 371         case RTE_FIB_DIR24_8_1B:
 372                 ptr8 = &((uint8_t *)dp->tbl8)[tbl8_idx *
 373                                 DIR24_8_TBL8_GRP_NUM_ENT];
 374                 nh = *ptr8;
 375                 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
 376                         if (nh != ptr8[i])
 377                                 return;
 378                 }
 379                 ((uint8_t *)dp->tbl24)[ip >> 8] =
 380                         nh & ~DIR24_8_EXT_ENT;
 381                 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
 382                         ptr8[i] = 0;
 383                 break;
 384         case RTE_FIB_DIR24_8_2B:
 385                 ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx *
 386                                 DIR24_8_TBL8_GRP_NUM_ENT];
 387                 nh = *ptr16;
 388                 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
 389                         if (nh != ptr16[i])
 390                                 return;
 391                 }
 392                 ((uint16_t *)dp->tbl24)[ip >> 8] =
 393                         nh & ~DIR24_8_EXT_ENT;
 394                 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
 395                         ptr16[i] = 0;
 396                 break;
 397         case RTE_FIB_DIR24_8_4B:
 398                 ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx *
 399                                 DIR24_8_TBL8_GRP_NUM_ENT];
 400                 nh = *ptr32;
 401                 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
 402                         if (nh != ptr32[i])
 403                                 return;
 404                 }
 405                 ((uint32_t *)dp->tbl24)[ip >> 8] =
 406                         nh & ~DIR24_8_EXT_ENT;
 407                 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
 408                         ptr32[i] = 0;
 409                 break;
 410         case RTE_FIB_DIR24_8_8B:
 411                 ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx *
 412                                 DIR24_8_TBL8_GRP_NUM_ENT];
 413                 nh = *ptr64;
 414                 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
 415                         if (nh != ptr64[i])
 416                                 return;
 417                 }
 418                 ((uint64_t *)dp->tbl24)[ip >> 8] =
 419                         nh & ~DIR24_8_EXT_ENT;
 420                 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
 421                         ptr64[i] = 0;
 422                 break;
 423         }
 424         tbl8_free_idx(dp, tbl8_idx);
 425         dp->cur_tbl8s--;
 426 }
 427
 428 static int
 429 install_to_fib(struct dir24_8_tbl *dp, uint32_t ledge, uint32_t redge,
 430         uint64_t next_hop)
 431 {
 432         uint64_t        tbl24_tmp;
 433         int     tbl8_idx;
 434         int tmp_tbl8_idx;
 435         uint8_t *tbl8_ptr;
 436         uint32_t len;
 437
 438         len = ((ledge == 0) && (redge == 0)) ? 1 << 24 :
 439                 ((redge & DIR24_8_TBL24_MASK) - ROUNDUP(ledge, 24)) >> 8;
 440
 441         if (((ledge >> 8) != (redge >> 8)) || (len == 1 << 24)) {
 442                 if ((ROUNDUP(ledge, 24) - ledge) != 0) {
 443                         tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz);
 444                         if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
 445                                         DIR24_8_EXT_ENT) {
 446                                 /**
 447                                  * Make sure there is space for two TBL8.
 448                                  * This is necessary when installing range that
 449                                  * needs tbl8 for ledge and redge.
 450                                  */
 451                                 tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
 452                                 tmp_tbl8_idx = tbl8_get_idx(dp);
 453                                 if (tbl8_idx < 0)
 454                                         return -ENOSPC;
 455                                 else if (tmp_tbl8_idx < 0) {
 456                                         tbl8_free_idx(dp, tbl8_idx);
 457                                         return -ENOSPC;
 458                                 }
 459                                 tbl8_free_idx(dp, tmp_tbl8_idx);
 460                                 /*update dir24 entry with tbl8 index*/
 461                                 write_to_fib(get_tbl24_p(dp, ledge,
 462                                         dp->nh_sz), (tbl8_idx << 1)|
 463                                         DIR24_8_EXT_ENT,
 464                                         dp->nh_sz, 1);
 465                         } else
 466                                 tbl8_idx = tbl24_tmp >> 1;
 467                         tbl8_ptr = (uint8_t *)dp->tbl8 +
 468                                 (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) +
 469                                 (ledge & ~DIR24_8_TBL24_MASK)) <<
 470                                 dp->nh_sz);
 471                         /*update tbl8 with new next hop*/
 472                         write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
 473                                 DIR24_8_EXT_ENT,
 474                                 dp->nh_sz, ROUNDUP(ledge, 24) - ledge);
 475                         tbl8_recycle(dp, ledge, tbl8_idx);
 476                 }
 477                 write_to_fib(get_tbl24_p(dp, ROUNDUP(ledge, 24), dp->nh_sz),
 478                         next_hop << 1, dp->nh_sz, len);
 479                 if (redge & ~DIR24_8_TBL24_MASK) {
 480                         tbl24_tmp = get_tbl24(dp, redge, dp->nh_sz);
 481                         if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
 482                                         DIR24_8_EXT_ENT) {
 483                                 tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
 484                                 if (tbl8_idx < 0)
 485                                         return -ENOSPC;
 486                                 /*update dir24 entry with tbl8 index*/
 487                                 write_to_fib(get_tbl24_p(dp, redge,
 488                                         dp->nh_sz), (tbl8_idx << 1)|
 489                                         DIR24_8_EXT_ENT,
 490                                         dp->nh_sz, 1);
 491                         } else
 492                                 tbl8_idx = tbl24_tmp >> 1;
 493                         tbl8_ptr = (uint8_t *)dp->tbl8 +
 494                                 ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) <<
 495                                 dp->nh_sz);
 496                         /*update tbl8 with new next hop*/
 497                         write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
 498                                 DIR24_8_EXT_ENT,
 499                                 dp->nh_sz, redge & ~DIR24_8_TBL24_MASK);
 500                         tbl8_recycle(dp, redge, tbl8_idx);
 501                 }
 502         } else if ((redge - ledge) != 0) {
 503                 tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz);
 504                 if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
 505                                 DIR24_8_EXT_ENT) {
 506                         tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
 507                         if (tbl8_idx < 0)
 508                                 return -ENOSPC;
 509                         /*update dir24 entry with tbl8 index*/
 510                         write_to_fib(get_tbl24_p(dp, ledge, dp->nh_sz),
 511                                 (tbl8_idx << 1)|
 512                                 DIR24_8_EXT_ENT,
 513                                 dp->nh_sz, 1);
 514                 } else
 515                         tbl8_idx = tbl24_tmp >> 1;
 516                 tbl8_ptr = (uint8_t *)dp->tbl8 +
 517                         (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) +
 518                         (ledge & ~DIR24_8_TBL24_MASK)) <<
 519                         dp->nh_sz);
 520                 /*update tbl8 with new next hop*/
 521                 write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
 522                         DIR24_8_EXT_ENT,
 523                         dp->nh_sz, redge - ledge);
 524                 tbl8_recycle(dp, ledge, tbl8_idx);
 525         }
 526         return 0;
 527 }
 528
 529 static int
 530 modify_fib(struct dir24_8_tbl *dp, struct rte_rib *rib, uint32_t ip,
 531         uint8_t depth, uint64_t next_hop)
 532 {
 533         struct rte_rib_node *tmp = NULL;
 534         uint32_t ledge, redge, tmp_ip;
 535         int ret;
 536         uint8_t tmp_depth;
 537
 538         ledge = ip;
 539         do {
 540                 tmp = rte_rib_get_nxt(rib, ip, depth, tmp,
 541                         RTE_RIB_GET_NXT_COVER);
 542                 if (tmp != NULL) {
 543                         rte_rib_get_depth(tmp, &tmp_depth);
 544                         if (tmp_depth == depth)
 545                                 continue;
 546                         rte_rib_get_ip(tmp, &tmp_ip);
 547                         redge = tmp_ip & rte_rib_depth_to_mask(tmp_depth);
 548                         if (ledge == redge) {
 549                                 ledge = redge +
 550                                         (uint32_t)(1ULL << (32 - tmp_depth));
 551                                 continue;
 552                         }
 553                         ret = install_to_fib(dp, ledge, redge,
 554                                 next_hop);
 555                         if (ret != 0)
 556                                 return ret;
 557                         ledge = redge +
 558                                 (uint32_t)(1ULL << (32 - tmp_depth));
 559                 } else {
 560                         redge = ip + (uint32_t)(1ULL << (32 - depth));
 561                         if (ledge == redge)
 562                                 break;
 563                         ret = install_to_fib(dp, ledge, redge,
 564                                 next_hop);
 565                         if (ret != 0)
 566                                 return ret;
 567                 }
 568         } while (tmp);
 569
 570         return 0;
 571 }
 572
 573 int
 574 dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
 575         uint64_t next_hop, int op)
 576 {
 577         struct dir24_8_tbl *dp;
 578         struct rte_rib *rib;
 579         struct rte_rib_node *tmp = NULL;
 580         struct rte_rib_node *node;
 581         struct rte_rib_node *parent;
 582         int ret = 0;
 583         uint64_t par_nh, node_nh;
 584
 585         if ((fib == NULL) || (depth > RTE_FIB_MAXDEPTH))
 586                 return -EINVAL;
 587
 588         dp = rte_fib_get_dp(fib);
 589         rib = rte_fib_get_rib(fib);
 590         RTE_ASSERT((dp != NULL) && (rib != NULL));
 591
 592         if (next_hop > get_max_nh(dp->nh_sz))
 593                 return -EINVAL;
 594
 595         ip &= rte_rib_depth_to_mask(depth);
 596
 597         node = rte_rib_lookup_exact(rib, ip, depth);
 598         switch (op) {
 599         case RTE_FIB_ADD:
 600                 if (node != NULL) {
 601                         rte_rib_get_nh(node, &node_nh);
 602                         if (node_nh == next_hop)
 603                                 return 0;
 604                         ret = modify_fib(dp, rib, ip, depth, next_hop);
 605                         if (ret == 0)
 606                                 rte_rib_set_nh(node, next_hop);
 607                         return 0;
 608                 }
 609                 if (depth > 24) {
 610                         tmp = rte_rib_get_nxt(rib, ip, 24, NULL,
 611                                 RTE_RIB_GET_NXT_COVER);
 612                         if ((tmp == NULL) &&
 613                                 (dp->rsvd_tbl8s >= dp->number_tbl8s))
 614                                 return -ENOSPC;
 615
 616                 }
 617                 node = rte_rib_insert(rib, ip, depth);
 618                 if (node == NULL)
 619                         return -rte_errno;
 620                 rte_rib_set_nh(node, next_hop);
 621                 parent = rte_rib_lookup_parent(node);
 622                 if (parent != NULL) {
 623                         rte_rib_get_nh(parent, &par_nh);
 624                         if (par_nh == next_hop)
 625                                 return 0;
 626                 }
 627                 ret = modify_fib(dp, rib, ip, depth, next_hop);
 628                 if (ret != 0) {
 629                         rte_rib_remove(rib, ip, depth);
 630                         return ret;
 631                 }
 632                 if ((depth > 24) && (tmp == NULL))
 633                         dp->rsvd_tbl8s++;
 634                 return 0;
 635         case RTE_FIB_DEL:
 636                 if (node == NULL)
 637                         return -ENOENT;
 638
 639                 parent = rte_rib_lookup_parent(node);
 640                 if (parent != NULL) {
 641                         rte_rib_get_nh(parent, &par_nh);
 642                         rte_rib_get_nh(node, &node_nh);
 643                         if (par_nh != node_nh)
 644                                 ret = modify_fib(dp, rib, ip, depth, par_nh);
 645                 } else
 646                         ret = modify_fib(dp, rib, ip, depth, dp->def_nh);
 647                 if (ret == 0) {
 648                         rte_rib_remove(rib, ip, depth);
 649                         if (depth > 24) {
 650                                 tmp = rte_rib_get_nxt(rib, ip, 24, NULL,
 651                                         RTE_RIB_GET_NXT_COVER);
 652                                 if (tmp == NULL)
 653                                         dp->rsvd_tbl8s--;
 654                         }
 655                 }
 656                 return ret;
 657         default:
 658                 break;
 659         }
 660         return -EINVAL;
 661 }
 662
 663 void *
 664 dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *fib_conf)
 665 {
 666         char mem_name[DIR24_8_NAMESIZE];
 667         struct dir24_8_tbl *dp;
 668         uint64_t        def_nh;
 669         uint32_t        num_tbl8;
 670         enum rte_fib_dir24_8_nh_sz      nh_sz;
 671
 672         if ((name == NULL) || (fib_conf == NULL) ||
 673                         (fib_conf->dir24_8.nh_sz < RTE_FIB_DIR24_8_1B) ||
 674                         (fib_conf->dir24_8.nh_sz > RTE_FIB_DIR24_8_8B) ||
 675                         (fib_conf->dir24_8.num_tbl8 >
 676                         get_max_nh(fib_conf->dir24_8.nh_sz)) ||
 677                         (fib_conf->dir24_8.num_tbl8 == 0) ||
 678                         (fib_conf->default_nh >
 679                         get_max_nh(fib_conf->dir24_8.nh_sz))) {
 680                 rte_errno = EINVAL;
 681                 return NULL;
 682         }
 683
 684         def_nh = fib_conf->default_nh;
 685         nh_sz = fib_conf->dir24_8.nh_sz;
 686         num_tbl8 = RTE_ALIGN_CEIL(fib_conf->dir24_8.num_tbl8,
 687                         BITMAP_SLAB_BIT_SIZE);
 688
 689         snprintf(mem_name, sizeof(mem_name), "DP_%s", name);
 690         dp = rte_zmalloc_socket(name, sizeof(struct dir24_8_tbl) +
 691                 DIR24_8_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE,
 692                 socket_id);
 693         if (dp == NULL) {
 694                 rte_errno = ENOMEM;
 695                 return NULL;
 696         }
 697
 698         /* Init table with default value */
 699         write_to_fib(dp->tbl24, (def_nh << 1), nh_sz, 1 << 24);
 700
 701         snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp);
 702         uint64_t tbl8_sz = DIR24_8_TBL8_GRP_NUM_ENT * (1ULL << nh_sz) *
 703                         (num_tbl8 + 1);
 704         dp->tbl8 = rte_zmalloc_socket(mem_name, tbl8_sz,
 705                         RTE_CACHE_LINE_SIZE, socket_id);
 706         if (dp->tbl8 == NULL) {
 707                 rte_errno = ENOMEM;
 708                 rte_free(dp);
 709                 return NULL;
 710         }
 711         dp->def_nh = def_nh;
 712         dp->nh_sz = nh_sz;
 713         dp->number_tbl8s = num_tbl8;
 714
 715         snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp);
 716         dp->tbl8_idxes = rte_zmalloc_socket(mem_name,
 717                         RTE_ALIGN_CEIL(dp->number_tbl8s, 64) >> 3,
 718                         RTE_CACHE_LINE_SIZE, socket_id);
 719         if (dp->tbl8_idxes == NULL) {
 720                 rte_errno = ENOMEM;
 721                 rte_free(dp->tbl8);
 722                 rte_free(dp);
 723                 return NULL;
 724         }
 725
 726         return dp;
 727 }
 728
 729 void
 730 dir24_8_free(void *p)
 731 {
 732         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
 733
 734         rte_free(dp->tbl8_idxes);
 735         rte_free(dp->tbl8);
 736         rte_free(dp);
 737 }