lib/librte_fib/trie.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_rib6.h>
  18 #include <rte_fib6.h>
  19 #include "trie.h"
  20
  21 #define TRIE_NAMESIZE           64
  22
  23 enum edge {
  24         LEDGE,
  25         REDGE
  26 };
  27
  28 static inline rte_fib6_lookup_fn_t
  29 get_scalar_fn(enum rte_fib_trie_nh_sz nh_sz)
  30 {
  31         switch (nh_sz) {
  32         case RTE_FIB6_TRIE_2B:
  33                 return rte_trie_lookup_bulk_2b;
  34         case RTE_FIB6_TRIE_4B:
  35                 return rte_trie_lookup_bulk_4b;
  36         case RTE_FIB6_TRIE_8B:
  37                 return rte_trie_lookup_bulk_8b;
  38         default:
  39                 return NULL;
  40         }
  41 }
  42
  43 rte_fib6_lookup_fn_t
  44 trie_get_lookup_fn(void *p, enum rte_fib6_lookup_type type)
  45 {
  46         enum rte_fib_trie_nh_sz nh_sz;
  47         struct rte_trie_tbl *dp = p;
  48
  49         if (dp == NULL)
  50                 return NULL;
  51
  52         nh_sz = dp->nh_sz;
  53
  54         switch (type) {
  55         case RTE_FIB6_LOOKUP_TRIE_SCALAR:
  56                 return get_scalar_fn(nh_sz);
  57         default:
  58                 return NULL;
  59         }
  60         return NULL;
  61 }
  62
  63 static void
  64 write_to_dp(void *ptr, uint64_t val, enum rte_fib_trie_nh_sz size, int n)
  65 {
  66         int i;
  67         uint16_t *ptr16 = (uint16_t *)ptr;
  68         uint32_t *ptr32 = (uint32_t *)ptr;
  69         uint64_t *ptr64 = (uint64_t *)ptr;
  70
  71         switch (size) {
  72         case RTE_FIB6_TRIE_2B:
  73                 for (i = 0; i < n; i++)
  74                         ptr16[i] = (uint16_t)val;
  75                 break;
  76         case RTE_FIB6_TRIE_4B:
  77                 for (i = 0; i < n; i++)
  78                         ptr32[i] = (uint32_t)val;
  79                 break;
  80         case RTE_FIB6_TRIE_8B:
  81                 for (i = 0; i < n; i++)
  82                         ptr64[i] = (uint64_t)val;
  83                 break;
  84         }
  85 }
  86
  87 static void
  88 tbl8_pool_init(struct rte_trie_tbl *dp)
  89 {
  90         uint32_t i;
  91
  92         /* put entire range of indexes to the tbl8 pool */
  93         for (i = 0; i < dp->number_tbl8s; i++)
  94                 dp->tbl8_pool[i] = i;
  95
  96         dp->tbl8_pool_pos = 0;
  97 }
  98
  99 /*
 100  * Get an index of a free tbl8 from the pool
 101  */
 102 static inline int32_t
 103 tbl8_get(struct rte_trie_tbl *dp)
 104 {
 105         if (dp->tbl8_pool_pos == dp->number_tbl8s)
 106                 /* no more free tbl8 */
 107                 return -ENOSPC;
 108
 109         /* next index */
 110         return dp->tbl8_pool[dp->tbl8_pool_pos++];
 111 }
 112
 113 /*
 114  * Put an index of a free tbl8 back to the pool
 115  */
 116 static inline void
 117 tbl8_put(struct rte_trie_tbl *dp, uint32_t tbl8_ind)
 118 {
 119         dp->tbl8_pool[--dp->tbl8_pool_pos] = tbl8_ind;
 120 }
 121
 122 static int
 123 tbl8_alloc(struct rte_trie_tbl *dp, uint64_t nh)
 124 {
 125         int64_t         tbl8_idx;
 126         uint8_t         *tbl8_ptr;
 127
 128         tbl8_idx = tbl8_get(dp);
 129         if (tbl8_idx < 0)
 130                 return tbl8_idx;
 131         tbl8_ptr = get_tbl_p_by_idx(dp->tbl8,
 132                 tbl8_idx * TRIE_TBL8_GRP_NUM_ENT, dp->nh_sz);
 133         /*Init tbl8 entries with nexthop from tbl24*/
 134         write_to_dp((void *)tbl8_ptr, nh, dp->nh_sz,
 135                 TRIE_TBL8_GRP_NUM_ENT);
 136         return tbl8_idx;
 137 }
 138
 139 static void
 140 tbl8_recycle(struct rte_trie_tbl *dp, void *par, uint64_t tbl8_idx)
 141 {
 142         uint32_t i;
 143         uint64_t nh;
 144         uint16_t *ptr16;
 145         uint32_t *ptr32;
 146         uint64_t *ptr64;
 147
 148         switch (dp->nh_sz) {
 149         case RTE_FIB6_TRIE_2B:
 150                 ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx *
 151                                 TRIE_TBL8_GRP_NUM_ENT];
 152                 nh = *ptr16;
 153                 if (nh & TRIE_EXT_ENT)
 154                         return;
 155                 for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
 156                         if (nh != ptr16[i])
 157                                 return;
 158                 }
 159                 write_to_dp(par, nh, dp->nh_sz, 1);
 160                 for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)
 161                         ptr16[i] = 0;
 162                 break;
 163         case RTE_FIB6_TRIE_4B:
 164                 ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx *
 165                                 TRIE_TBL8_GRP_NUM_ENT];
 166                 nh = *ptr32;
 167                 if (nh & TRIE_EXT_ENT)
 168                         return;
 169                 for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
 170                         if (nh != ptr32[i])
 171                                 return;
 172                 }
 173                 write_to_dp(par, nh, dp->nh_sz, 1);
 174                 for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)
 175                         ptr32[i] = 0;
 176                 break;
 177         case RTE_FIB6_TRIE_8B:
 178                 ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx *
 179                                 TRIE_TBL8_GRP_NUM_ENT];
 180                 nh = *ptr64;
 181                 if (nh & TRIE_EXT_ENT)
 182                         return;
 183                 for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
 184                         if (nh != ptr64[i])
 185                                 return;
 186                 }
 187                 write_to_dp(par, nh, dp->nh_sz, 1);
 188                 for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)
 189                         ptr64[i] = 0;
 190                 break;
 191         }
 192         tbl8_put(dp, tbl8_idx);
 193 }
 194
 195 #define BYTE_SIZE       8
 196 static inline uint32_t
 197 get_idx(const uint8_t *ip, uint32_t prev_idx, int bytes, int first_byte)
 198 {
 199         int i;
 200         uint32_t idx = 0;
 201         uint8_t bitshift;
 202
 203         for (i = first_byte; i < (first_byte + bytes); i++) {
 204                 bitshift = (int8_t)(((first_byte + bytes - 1) - i)*BYTE_SIZE);
 205                 idx |= ip[i] <<  bitshift;
 206         }
 207         return (prev_idx * TRIE_TBL8_GRP_NUM_ENT) + idx;
 208 }
 209
 210 static inline uint64_t
 211 get_val_by_p(void *p, uint8_t nh_sz)
 212 {
 213         uint64_t val = 0;
 214
 215         switch (nh_sz) {
 216         case RTE_FIB6_TRIE_2B:
 217                 val = *(uint16_t *)p;
 218                 break;
 219         case RTE_FIB6_TRIE_4B:
 220                 val = *(uint32_t *)p;
 221                 break;
 222         case RTE_FIB6_TRIE_8B:
 223                 val = *(uint64_t *)p;
 224                 break;
 225         }
 226         return val;
 227 }
 228
 229 /*
 230  * recursively recycle tbl8's
 231  */
 232 static void
 233 recycle_root_path(struct rte_trie_tbl *dp, const uint8_t *ip_part,
 234         uint8_t common_tbl8, void *prev)
 235 {
 236         void *p;
 237         uint64_t val;
 238
 239         val = get_val_by_p(prev, dp->nh_sz);
 240         if (unlikely((val & TRIE_EXT_ENT) != TRIE_EXT_ENT))
 241                 return;
 242
 243         if (common_tbl8 != 0) {
 244                 p = get_tbl_p_by_idx(dp->tbl8, (val >> 1) *
 245                         TRIE_TBL8_GRP_NUM_ENT + *ip_part, dp->nh_sz);
 246                 recycle_root_path(dp, ip_part + 1, common_tbl8 - 1, p);
 247         }
 248         tbl8_recycle(dp, prev, val >> 1);
 249 }
 250
 251 static inline int
 252 build_common_root(struct rte_trie_tbl *dp, const uint8_t *ip,
 253         int common_bytes, void **tbl)
 254 {
 255         void *tbl_ptr = NULL;
 256         uint64_t *cur_tbl;
 257         uint64_t val;
 258         int i, j, idx, prev_idx = 0;
 259
 260         cur_tbl = dp->tbl24;
 261         for (i = 3, j = 0; i <= common_bytes; i++) {
 262                 idx = get_idx(ip, prev_idx, i - j, j);
 263                 val = get_tbl_val_by_idx(cur_tbl, idx, dp->nh_sz);
 264                 tbl_ptr = get_tbl_p_by_idx(cur_tbl, idx, dp->nh_sz);
 265                 if ((val & TRIE_EXT_ENT) != TRIE_EXT_ENT) {
 266                         idx = tbl8_alloc(dp, val);
 267                         if (unlikely(idx < 0))
 268                                 return idx;
 269                         write_to_dp(tbl_ptr, (idx << 1) |
 270                                 TRIE_EXT_ENT, dp->nh_sz, 1);
 271                         prev_idx = idx;
 272                 } else
 273                         prev_idx = val >> 1;
 274
 275                 j = i;
 276                 cur_tbl = dp->tbl8;
 277         }
 278         *tbl = get_tbl_p_by_idx(cur_tbl, prev_idx * TRIE_TBL8_GRP_NUM_ENT,
 279                 dp->nh_sz);
 280         return 0;
 281 }
 282
 283 static int
 284 write_edge(struct rte_trie_tbl *dp, const uint8_t *ip_part, uint64_t next_hop,
 285         int len, enum edge edge, void *ent)
 286 {
 287         uint64_t val = next_hop << 1;
 288         int tbl8_idx;
 289         int ret = 0;
 290         void *p;
 291
 292         if (len != 0) {
 293                 val = get_val_by_p(ent, dp->nh_sz);
 294                 if ((val & TRIE_EXT_ENT) == TRIE_EXT_ENT)
 295                         tbl8_idx = val >> 1;
 296                 else {
 297                         tbl8_idx = tbl8_alloc(dp, val);
 298                         if (tbl8_idx < 0)
 299                                 return tbl8_idx;
 300                         val = (tbl8_idx << 1)|TRIE_EXT_ENT;
 301                 }
 302                 p = get_tbl_p_by_idx(dp->tbl8, (tbl8_idx *
 303                         TRIE_TBL8_GRP_NUM_ENT) + *ip_part, dp->nh_sz);
 304                 ret = write_edge(dp, ip_part + 1, next_hop, len - 1, edge, p);
 305                 if (ret < 0)
 306                         return ret;
 307                 if (edge == LEDGE) {
 308                         write_to_dp((uint8_t *)p + (1 << dp->nh_sz),
 309                                 next_hop << 1, dp->nh_sz, UINT8_MAX - *ip_part);
 310                 } else {
 311                         write_to_dp(get_tbl_p_by_idx(dp->tbl8, tbl8_idx *
 312                                 TRIE_TBL8_GRP_NUM_ENT, dp->nh_sz),
 313                                 next_hop << 1, dp->nh_sz, *ip_part);
 314                 }
 315                 tbl8_recycle(dp, &val, tbl8_idx);
 316         }
 317
 318         write_to_dp(ent, val, dp->nh_sz, 1);
 319         return ret;
 320 }
 321
 322 #define IPV6_MAX_IDX    (RTE_FIB6_IPV6_ADDR_SIZE - 1)
 323 #define TBL24_BYTES     3
 324 #define TBL8_LEN        (RTE_FIB6_IPV6_ADDR_SIZE - TBL24_BYTES)
 325
 326 static int
 327 install_to_dp(struct rte_trie_tbl *dp, const uint8_t *ledge, const uint8_t *r,
 328         uint64_t next_hop)
 329 {
 330         void *common_root_tbl;
 331         void *ent;
 332         int ret;
 333         int i;
 334         int common_bytes;
 335         int llen, rlen;
 336         uint8_t redge[16];
 337
 338         /* decrement redge by 1*/
 339         rte_rib6_copy_addr(redge, r);
 340         for (i = 15; i >= 0; i--) {
 341                 redge[i]--;
 342                 if (redge[i] != 0xff)
 343                         break;
 344         }
 345
 346         for (common_bytes = 0; common_bytes < 15; common_bytes++) {
 347                 if (ledge[common_bytes] != redge[common_bytes])
 348                         break;
 349         }
 350
 351         ret = build_common_root(dp, ledge, common_bytes, &common_root_tbl);
 352         if (unlikely(ret != 0))
 353                 return ret;
 354         /*first uncommon tbl8 byte idx*/
 355         uint8_t first_tbl8_byte = RTE_MAX(common_bytes, TBL24_BYTES);
 356
 357         for (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) {
 358                 if (ledge[i] != 0)
 359                         break;
 360         }
 361
 362         llen = i - first_tbl8_byte + (common_bytes < 3);
 363
 364         for (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) {
 365                 if (redge[i] != UINT8_MAX)
 366                         break;
 367         }
 368         rlen = i - first_tbl8_byte + (common_bytes < 3);
 369
 370         /*first noncommon byte*/
 371         uint8_t first_byte_idx = (common_bytes < 3) ? 0 : common_bytes;
 372         uint8_t first_idx_len = (common_bytes < 3) ? 3 : 1;
 373
 374         uint32_t left_idx = get_idx(ledge, 0, first_idx_len, first_byte_idx);
 375         uint32_t right_idx = get_idx(redge, 0, first_idx_len, first_byte_idx);
 376
 377         ent = get_tbl_p_by_idx(common_root_tbl, left_idx, dp->nh_sz);
 378         ret = write_edge(dp, &ledge[first_tbl8_byte + !(common_bytes < 3)],
 379                 next_hop, llen, LEDGE, ent);
 380         if (ret < 0)
 381                 return ret;
 382
 383         if (right_idx > left_idx + 1) {
 384                 ent = get_tbl_p_by_idx(common_root_tbl, left_idx + 1,
 385                         dp->nh_sz);
 386                 write_to_dp(ent, next_hop << 1, dp->nh_sz,
 387                         right_idx - (left_idx + 1));
 388         }
 389         ent = get_tbl_p_by_idx(common_root_tbl, right_idx, dp->nh_sz);
 390         ret = write_edge(dp, &redge[first_tbl8_byte + !((common_bytes < 3))],
 391                 next_hop, rlen, REDGE, ent);
 392         if (ret < 0)
 393                 return ret;
 394
 395         uint8_t common_tbl8 = (common_bytes < TBL24_BYTES) ?
 396                         0 : common_bytes - (TBL24_BYTES - 1);
 397         ent = get_tbl24_p(dp, ledge, dp->nh_sz);
 398         recycle_root_path(dp, ledge + TBL24_BYTES, common_tbl8, ent);
 399         return 0;
 400 }
 401
 402 static void
 403 get_nxt_net(uint8_t *ip, uint8_t depth)
 404 {
 405         int i;
 406         uint8_t part_depth;
 407         uint8_t prev_byte;
 408
 409         for (i = 0, part_depth = depth; part_depth > 8; part_depth -= 8, i++)
 410                 ;
 411
 412         prev_byte = ip[i];
 413         ip[i] += 1 << (8 - part_depth);
 414         if (ip[i] < prev_byte) {
 415                 while (i > 0) {
 416                         ip[--i] += 1;
 417                         if (ip[i] != 0)
 418                                 break;
 419                 }
 420         }
 421 }
 422
 423 static int
 424 modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
 425         const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
 426         uint8_t depth, uint64_t next_hop)
 427 {
 428         struct rte_rib6_node *tmp = NULL;
 429         uint8_t ledge[RTE_FIB6_IPV6_ADDR_SIZE];
 430         uint8_t redge[RTE_FIB6_IPV6_ADDR_SIZE];
 431         int ret;
 432         uint8_t tmp_depth;
 433
 434         if (next_hop > get_max_nh(dp->nh_sz))
 435                 return -EINVAL;
 436
 437         rte_rib6_copy_addr(ledge, ip);
 438         do {
 439                 tmp = rte_rib6_get_nxt(rib, ip, depth, tmp,
 440                         RTE_RIB6_GET_NXT_COVER);
 441                 if (tmp != NULL) {
 442                         rte_rib6_get_depth(tmp, &tmp_depth);
 443                         if (tmp_depth == depth)
 444                                 continue;
 445                         rte_rib6_get_ip(tmp, redge);
 446                         if (rte_rib6_is_equal(ledge, redge)) {
 447                                 get_nxt_net(ledge, tmp_depth);
 448                                 continue;
 449                         }
 450                         ret = install_to_dp(dp, ledge, redge,
 451                                 next_hop);
 452                         if (ret != 0)
 453                                 return ret;
 454                         get_nxt_net(redge, tmp_depth);
 455                         rte_rib6_copy_addr(ledge, redge);
 456                 } else {
 457                         rte_rib6_copy_addr(redge, ip);
 458                         get_nxt_net(redge, depth);
 459                         if (rte_rib6_is_equal(ledge, redge))
 460                                 break;
 461                         ret = install_to_dp(dp, ledge, redge,
 462                                 next_hop);
 463                         if (ret != 0)
 464                                 return ret;
 465                 }
 466         } while (tmp);
 467
 468         return 0;
 469 }
 470
 471 int
 472 trie_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
 473         uint8_t depth, uint64_t next_hop, int op)
 474 {
 475         struct rte_trie_tbl *dp;
 476         struct rte_rib6 *rib;
 477         struct rte_rib6_node *tmp = NULL;
 478         struct rte_rib6_node *node;
 479         struct rte_rib6_node *parent;
 480         uint8_t ip_masked[RTE_FIB6_IPV6_ADDR_SIZE];
 481         int i, ret = 0;
 482         uint64_t par_nh, node_nh;
 483         uint8_t tmp_depth, depth_diff = 0, parent_depth = 24;
 484
 485         if ((fib == NULL) || (ip == NULL) || (depth > RTE_FIB6_MAXDEPTH))
 486                 return -EINVAL;
 487
 488         dp = rte_fib6_get_dp(fib);
 489         RTE_ASSERT(dp);
 490         rib = rte_fib6_get_rib(fib);
 491         RTE_ASSERT(rib);
 492
 493         for (i = 0; i < RTE_FIB6_IPV6_ADDR_SIZE; i++)
 494                 ip_masked[i] = ip[i] & get_msk_part(depth, i);
 495
 496         if (depth > 24) {
 497                 tmp = rte_rib6_get_nxt(rib, ip_masked,
 498                         RTE_ALIGN_FLOOR(depth, 8), NULL,
 499                         RTE_RIB6_GET_NXT_COVER);
 500                 if (tmp == NULL) {
 501                         tmp = rte_rib6_lookup(rib, ip);
 502                         if (tmp != NULL) {
 503                                 rte_rib6_get_depth(tmp, &tmp_depth);
 504                                 parent_depth = RTE_MAX(tmp_depth, 24);
 505                         }
 506                         depth_diff = RTE_ALIGN_CEIL(depth, 8) -
 507                                 RTE_ALIGN_CEIL(parent_depth, 8);
 508                         depth_diff = depth_diff >> 3;
 509                 }
 510         }
 511         node = rte_rib6_lookup_exact(rib, ip_masked, depth);
 512         switch (op) {
 513         case RTE_FIB6_ADD:
 514                 if (node != NULL) {
 515                         rte_rib6_get_nh(node, &node_nh);
 516                         if (node_nh == next_hop)
 517                                 return 0;
 518                         ret = modify_dp(dp, rib, ip_masked, depth, next_hop);
 519                         if (ret == 0)
 520                                 rte_rib6_set_nh(node, next_hop);
 521                         return 0;
 522                 }
 523
 524                 if ((depth > 24) && (dp->rsvd_tbl8s >=
 525                                 dp->number_tbl8s - depth_diff))
 526                         return -ENOSPC;
 527
 528                 node = rte_rib6_insert(rib, ip_masked, depth);
 529                 if (node == NULL)
 530                         return -rte_errno;
 531                 rte_rib6_set_nh(node, next_hop);
 532                 parent = rte_rib6_lookup_parent(node);
 533                 if (parent != NULL) {
 534                         rte_rib6_get_nh(parent, &par_nh);
 535                         if (par_nh == next_hop)
 536                                 return 0;
 537                 }
 538                 ret = modify_dp(dp, rib, ip_masked, depth, next_hop);
 539                 if (ret != 0) {
 540                         rte_rib6_remove(rib, ip_masked, depth);
 541                         return ret;
 542                 }
 543
 544                 dp->rsvd_tbl8s += depth_diff;
 545                 return 0;
 546         case RTE_FIB6_DEL:
 547                 if (node == NULL)
 548                         return -ENOENT;
 549
 550                 parent = rte_rib6_lookup_parent(node);
 551                 if (parent != NULL) {
 552                         rte_rib6_get_nh(parent, &par_nh);
 553                         rte_rib6_get_nh(node, &node_nh);
 554                         if (par_nh != node_nh)
 555                                 ret = modify_dp(dp, rib, ip_masked, depth,
 556                                         par_nh);
 557                 } else
 558                         ret = modify_dp(dp, rib, ip_masked, depth, dp->def_nh);
 559
 560                 if (ret != 0)
 561                         return ret;
 562                 rte_rib6_remove(rib, ip, depth);
 563
 564                 dp->rsvd_tbl8s -= depth_diff;
 565                 return 0;
 566         default:
 567                 break;
 568         }
 569         return -EINVAL;
 570 }
 571
 572 void *
 573 trie_create(const char *name, int socket_id,
 574         struct rte_fib6_conf *conf)
 575 {
 576         char mem_name[TRIE_NAMESIZE];
 577         struct rte_trie_tbl *dp = NULL;
 578         uint64_t        def_nh;
 579         uint32_t        num_tbl8;
 580         enum rte_fib_trie_nh_sz nh_sz;
 581
 582         if ((name == NULL) || (conf == NULL) ||
 583                         (conf->trie.nh_sz < RTE_FIB6_TRIE_2B) ||
 584                         (conf->trie.nh_sz > RTE_FIB6_TRIE_8B) ||
 585                         (conf->trie.num_tbl8 >
 586                         get_max_nh(conf->trie.nh_sz)) ||
 587                         (conf->trie.num_tbl8 == 0) ||
 588                         (conf->default_nh >
 589                         get_max_nh(conf->trie.nh_sz))) {
 590
 591                 rte_errno = EINVAL;
 592                 return NULL;
 593         }
 594
 595         def_nh = conf->default_nh;
 596         nh_sz = conf->trie.nh_sz;
 597         num_tbl8 = conf->trie.num_tbl8;
 598
 599         snprintf(mem_name, sizeof(mem_name), "DP_%s", name);
 600         dp = rte_zmalloc_socket(name, sizeof(struct rte_trie_tbl) +
 601                 TRIE_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE,
 602                 socket_id);
 603         if (dp == NULL) {
 604                 rte_errno = ENOMEM;
 605                 return dp;
 606         }
 607
 608         write_to_dp(&dp->tbl24, (def_nh << 1), nh_sz, 1 << 24);
 609
 610         snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp);
 611         dp->tbl8 = rte_zmalloc_socket(mem_name, TRIE_TBL8_GRP_NUM_ENT *
 612                         (1ll << nh_sz) * (num_tbl8 + 1),
 613                         RTE_CACHE_LINE_SIZE, socket_id);
 614         if (dp->tbl8 == NULL) {
 615                 rte_errno = ENOMEM;
 616                 rte_free(dp);
 617                 return NULL;
 618         }
 619         dp->def_nh = def_nh;
 620         dp->nh_sz = nh_sz;
 621         dp->number_tbl8s = num_tbl8;
 622
 623         snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp);
 624         dp->tbl8_pool = rte_zmalloc_socket(mem_name,
 625                         sizeof(uint32_t) * dp->number_tbl8s,
 626                         RTE_CACHE_LINE_SIZE, socket_id);
 627         if (dp->tbl8_pool == NULL) {
 628                 rte_errno = ENOMEM;
 629                 rte_free(dp->tbl8);
 630                 rte_free(dp);
 631                 return NULL;
 632         }
 633
 634         tbl8_pool_init(dp);
 635
 636         return dp;
 637 }
 638
 639 void
 640 trie_free(void *p)
 641 {
 642         struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p;
 643
 644         rte_free(dp->tbl8_pool);
 645         rte_free(dp->tbl8);
 646         rte_free(dp);
 647 }