lib/rib/rte_rib6.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 <stdbool.h>
   7 #include <stdint.h>
   8
   9 #include <rte_eal.h>
  10 #include <rte_eal_memconfig.h>
  11 #include <rte_errno.h>
  12 #include <rte_malloc.h>
  13 #include <rte_mempool.h>
  14 #include <rte_rwlock.h>
  15 #include <rte_string_fns.h>
  16 #include <rte_tailq.h>
  17
  18 #include <rte_rib6.h>
  19
  20 #define RTE_RIB_VALID_NODE      1
  21 #define RIB6_MAXDEPTH           128
  22 /* Maximum length of a RIB6 name. */
  23 #define RTE_RIB6_NAMESIZE       64
  24
  25 TAILQ_HEAD(rte_rib6_list, rte_tailq_entry);
  26 static struct rte_tailq_elem rte_rib6_tailq = {
  27         .name = "RTE_RIB6",
  28 };
  29 EAL_REGISTER_TAILQ(rte_rib6_tailq)
  30
  31 struct rte_rib6_node {
  32         struct rte_rib6_node    *left;
  33         struct rte_rib6_node    *right;
  34         struct rte_rib6_node    *parent;
  35         uint64_t                nh;
  36         uint8_t                 ip[RTE_RIB6_IPV6_ADDR_SIZE];
  37         uint8_t                 depth;
  38         uint8_t                 flag;
  39         __extension__ uint64_t          ext[0];
  40 };
  41
  42 struct rte_rib6 {
  43         char            name[RTE_RIB6_NAMESIZE];
  44         struct rte_rib6_node    *tree;
  45         struct rte_mempool      *node_pool;
  46         uint32_t                cur_nodes;
  47         uint32_t                cur_routes;
  48         int                     max_nodes;
  49 };
  50
  51 static inline bool
  52 is_valid_node(struct rte_rib6_node *node)
  53 {
  54         return (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE;
  55 }
  56
  57 static inline bool
  58 is_right_node(struct rte_rib6_node *node)
  59 {
  60         return node->parent->right == node;
  61 }
  62
  63 /*
  64  * Check if ip1 is covered by ip2/depth prefix
  65  */
  66 static inline bool
  67 is_covered(const uint8_t ip1[RTE_RIB6_IPV6_ADDR_SIZE],
  68                 const uint8_t ip2[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
  69 {
  70         int i;
  71
  72         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
  73                 if ((ip1[i] ^ ip2[i]) & get_msk_part(depth, i))
  74                         return false;
  75
  76         return true;
  77 }
  78
  79 static inline int
  80 get_dir(const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
  81 {
  82         uint8_t index, msk;
  83
  84         /*
  85          * depth & 127 clamps depth to values that will not
  86          * read off the end of ip.
  87          * depth is the number of bits deep into ip to traverse, and
  88          * is incremented in blocks of 8 (1 byte). This means the last
  89          * 3 bits are irrelevant to what the index of ip should be.
  90          */
  91         index = (depth & (UINT8_MAX - 1)) / CHAR_BIT;
  92
  93         /*
  94          * msk is the bitmask used to extract the bit used to decide the
  95          * direction of the next step of the binary search.
  96          */
  97         msk = 1 << (7 - (depth & 7));
  98
  99         return (ip[index] & msk) != 0;
 100 }
 101
 102 static inline struct rte_rib6_node *
 103 get_nxt_node(struct rte_rib6_node *node,
 104         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
 105 {
 106         if (node->depth == RIB6_MAXDEPTH)
 107                 return NULL;
 108
 109         return (get_dir(ip, node->depth)) ? node->right : node->left;
 110 }
 111
 112 static struct rte_rib6_node *
 113 node_alloc(struct rte_rib6 *rib)
 114 {
 115         struct rte_rib6_node *ent;
 116         int ret;
 117
 118         ret = rte_mempool_get(rib->node_pool, (void *)&ent);
 119         if (unlikely(ret != 0))
 120                 return NULL;
 121         ++rib->cur_nodes;
 122         return ent;
 123 }
 124
 125 static void
 126 node_free(struct rte_rib6 *rib, struct rte_rib6_node *ent)
 127 {
 128         --rib->cur_nodes;
 129         rte_mempool_put(rib->node_pool, ent);
 130 }
 131
 132 struct rte_rib6_node *
 133 rte_rib6_lookup(struct rte_rib6 *rib,
 134         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
 135 {
 136         struct rte_rib6_node *cur;
 137         struct rte_rib6_node *prev = NULL;
 138
 139         if (unlikely(rib == NULL)) {
 140                 rte_errno = EINVAL;
 141                 return NULL;
 142         }
 143         cur = rib->tree;
 144
 145         while ((cur != NULL) && is_covered(ip, cur->ip, cur->depth)) {
 146                 if (is_valid_node(cur))
 147                         prev = cur;
 148                 cur = get_nxt_node(cur, ip);
 149         }
 150         return prev;
 151 }
 152
 153 struct rte_rib6_node *
 154 rte_rib6_lookup_parent(struct rte_rib6_node *ent)
 155 {
 156         struct rte_rib6_node *tmp;
 157
 158         if (ent == NULL)
 159                 return NULL;
 160
 161         tmp = ent->parent;
 162         while ((tmp != NULL) && (!is_valid_node(tmp)))
 163                 tmp = tmp->parent;
 164
 165         return tmp;
 166 }
 167
 168 struct rte_rib6_node *
 169 rte_rib6_lookup_exact(struct rte_rib6 *rib,
 170         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
 171 {
 172         struct rte_rib6_node *cur;
 173         uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
 174         int i;
 175
 176         if ((rib == NULL) || (ip == NULL) || (depth > RIB6_MAXDEPTH)) {
 177                 rte_errno = EINVAL;
 178                 return NULL;
 179         }
 180         cur = rib->tree;
 181
 182         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
 183                 tmp_ip[i] = ip[i] & get_msk_part(depth, i);
 184
 185         while (cur != NULL) {
 186                 if (rte_rib6_is_equal(cur->ip, tmp_ip) &&
 187                                 (cur->depth == depth) &&
 188                                 is_valid_node(cur))
 189                         return cur;
 190
 191                 if (!(is_covered(tmp_ip, cur->ip, cur->depth)) ||
 192                                 (cur->depth >= depth))
 193                         break;
 194
 195                 cur = get_nxt_node(cur, tmp_ip);
 196         }
 197
 198         return NULL;
 199 }
 200
 201 /*
 202  *  Traverses on subtree and retreeves more specific routes
 203  *  for a given in args ip/depth prefix
 204  *  last = NULL means the first invocation
 205  */
 206 struct rte_rib6_node *
 207 rte_rib6_get_nxt(struct rte_rib6 *rib,
 208         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE],
 209         uint8_t depth, struct rte_rib6_node *last, int flag)
 210 {
 211         struct rte_rib6_node *tmp, *prev = NULL;
 212         uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
 213         int i;
 214
 215         if ((rib == NULL) || (ip == NULL) || (depth > RIB6_MAXDEPTH)) {
 216                 rte_errno = EINVAL;
 217                 return NULL;
 218         }
 219
 220         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
 221                 tmp_ip[i] = ip[i] & get_msk_part(depth, i);
 222
 223         if (last == NULL) {
 224                 tmp = rib->tree;
 225                 while ((tmp) && (tmp->depth < depth))
 226                         tmp = get_nxt_node(tmp, tmp_ip);
 227         } else {
 228                 tmp = last;
 229                 while ((tmp->parent != NULL) && (is_right_node(tmp) ||
 230                                 (tmp->parent->right == NULL))) {
 231                         tmp = tmp->parent;
 232                         if (is_valid_node(tmp) &&
 233                                         (is_covered(tmp->ip, tmp_ip, depth) &&
 234                                         (tmp->depth > depth)))
 235                                 return tmp;
 236                 }
 237                 tmp = (tmp->parent != NULL) ? tmp->parent->right : NULL;
 238         }
 239         while (tmp) {
 240                 if (is_valid_node(tmp) &&
 241                                 (is_covered(tmp->ip, tmp_ip, depth) &&
 242                                 (tmp->depth > depth))) {
 243                         prev = tmp;
 244                         if (flag == RTE_RIB6_GET_NXT_COVER)
 245                                 return prev;
 246                 }
 247                 tmp = (tmp->left != NULL) ? tmp->left : tmp->right;
 248         }
 249         return prev;
 250 }
 251
 252 void
 253 rte_rib6_remove(struct rte_rib6 *rib,
 254         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
 255 {
 256         struct rte_rib6_node *cur, *prev, *child;
 257
 258         cur = rte_rib6_lookup_exact(rib, ip, depth);
 259         if (cur == NULL)
 260                 return;
 261
 262         --rib->cur_routes;
 263         cur->flag &= ~RTE_RIB_VALID_NODE;
 264         while (!is_valid_node(cur)) {
 265                 if ((cur->left != NULL) && (cur->right != NULL))
 266                         return;
 267                 child = (cur->left == NULL) ? cur->right : cur->left;
 268                 if (child != NULL)
 269                         child->parent = cur->parent;
 270                 if (cur->parent == NULL) {
 271                         rib->tree = child;
 272                         node_free(rib, cur);
 273                         return;
 274                 }
 275                 if (cur->parent->left == cur)
 276                         cur->parent->left = child;
 277                 else
 278                         cur->parent->right = child;
 279                 prev = cur;
 280                 cur = cur->parent;
 281                 node_free(rib, prev);
 282         }
 283 }
 284
 285 struct rte_rib6_node *
 286 rte_rib6_insert(struct rte_rib6 *rib,
 287         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
 288 {
 289         struct rte_rib6_node **tmp;
 290         struct rte_rib6_node *prev = NULL;
 291         struct rte_rib6_node *new_node = NULL;
 292         struct rte_rib6_node *common_node = NULL;
 293         uint8_t common_prefix[RTE_RIB6_IPV6_ADDR_SIZE];
 294         uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
 295         int i, d;
 296         uint8_t common_depth, ip_xor;
 297
 298         if (unlikely((rib == NULL) || (ip == NULL) ||
 299                         (depth > RIB6_MAXDEPTH))) {
 300                 rte_errno = EINVAL;
 301                 return NULL;
 302         }
 303
 304         tmp = &rib->tree;
 305
 306         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
 307                 tmp_ip[i] = ip[i] & get_msk_part(depth, i);
 308
 309         new_node = rte_rib6_lookup_exact(rib, tmp_ip, depth);
 310         if (new_node != NULL) {
 311                 rte_errno = EEXIST;
 312                 return NULL;
 313         }
 314
 315         new_node = node_alloc(rib);
 316         if (new_node == NULL) {
 317                 rte_errno = ENOMEM;
 318                 return NULL;
 319         }
 320         new_node->left = NULL;
 321         new_node->right = NULL;
 322         new_node->parent = NULL;
 323         rte_rib6_copy_addr(new_node->ip, tmp_ip);
 324         new_node->depth = depth;
 325         new_node->flag = RTE_RIB_VALID_NODE;
 326
 327         /* traverse down the tree to find matching node or closest matching */
 328         while (1) {
 329                 /* insert as the last node in the branch */
 330                 if (*tmp == NULL) {
 331                         *tmp = new_node;
 332                         new_node->parent = prev;
 333                         ++rib->cur_routes;
 334                         return *tmp;
 335                 }
 336                 /*
 337                  * Intermediate node found.
 338                  * Previous rte_rib6_lookup_exact() returned NULL
 339                  * but node with proper search criteria is found.
 340                  * Validate intermediate node and return.
 341                  */
 342                 if (rte_rib6_is_equal(tmp_ip, (*tmp)->ip) &&
 343                                 (depth == (*tmp)->depth)) {
 344                         node_free(rib, new_node);
 345                         (*tmp)->flag |= RTE_RIB_VALID_NODE;
 346                         ++rib->cur_routes;
 347                         return *tmp;
 348                 }
 349
 350                 if (!is_covered(tmp_ip, (*tmp)->ip, (*tmp)->depth) ||
 351                                 ((*tmp)->depth >= depth)) {
 352                         break;
 353                 }
 354                 prev = *tmp;
 355
 356                 tmp = (get_dir(tmp_ip, (*tmp)->depth)) ? &(*tmp)->right :
 357                                 &(*tmp)->left;
 358         }
 359
 360         /* closest node found, new_node should be inserted in the middle */
 361         common_depth = RTE_MIN(depth, (*tmp)->depth);
 362         for (i = 0, d = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) {
 363                 ip_xor = tmp_ip[i] ^ (*tmp)->ip[i];
 364                 if (ip_xor == 0)
 365                         d += 8;
 366                 else {
 367                         d += __builtin_clz(ip_xor << 24);
 368                         break;
 369                 }
 370         }
 371
 372         common_depth = RTE_MIN(d, common_depth);
 373
 374         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
 375                 common_prefix[i] = tmp_ip[i] & get_msk_part(common_depth, i);
 376
 377         if (rte_rib6_is_equal(common_prefix, tmp_ip) &&
 378                         (common_depth == depth)) {
 379                 /* insert as a parent */
 380                 if (get_dir((*tmp)->ip, depth))
 381                         new_node->right = *tmp;
 382                 else
 383                         new_node->left = *tmp;
 384                 new_node->parent = (*tmp)->parent;
 385                 (*tmp)->parent = new_node;
 386                 *tmp = new_node;
 387         } else {
 388                 /* create intermediate node */
 389                 common_node = node_alloc(rib);
 390                 if (common_node == NULL) {
 391                         node_free(rib, new_node);
 392                         rte_errno = ENOMEM;
 393                         return NULL;
 394                 }
 395                 rte_rib6_copy_addr(common_node->ip, common_prefix);
 396                 common_node->depth = common_depth;
 397                 common_node->flag = 0;
 398                 common_node->parent = (*tmp)->parent;
 399                 new_node->parent = common_node;
 400                 (*tmp)->parent = common_node;
 401                 if (get_dir((*tmp)->ip, common_depth) == 1) {
 402                         common_node->left = new_node;
 403                         common_node->right = *tmp;
 404                 } else {
 405                         common_node->left = *tmp;
 406                         common_node->right = new_node;
 407                 }
 408                 *tmp = common_node;
 409         }
 410         ++rib->cur_routes;
 411         return new_node;
 412 }
 413
 414 int
 415 rte_rib6_get_ip(const struct rte_rib6_node *node,
 416                 uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
 417 {
 418         if ((node == NULL) || (ip == NULL)) {
 419                 rte_errno = EINVAL;
 420                 return -1;
 421         }
 422         rte_rib6_copy_addr(ip, node->ip);
 423         return 0;
 424 }
 425
 426 int
 427 rte_rib6_get_depth(const struct rte_rib6_node *node, uint8_t *depth)
 428 {
 429         if ((node == NULL) || (depth == NULL)) {
 430                 rte_errno = EINVAL;
 431                 return -1;
 432         }
 433         *depth = node->depth;
 434         return 0;
 435 }
 436
 437 void *
 438 rte_rib6_get_ext(struct rte_rib6_node *node)
 439 {
 440         return (node == NULL) ? NULL : &node->ext[0];
 441 }
 442
 443 int
 444 rte_rib6_get_nh(const struct rte_rib6_node *node, uint64_t *nh)
 445 {
 446         if ((node == NULL) || (nh == NULL)) {
 447                 rte_errno = EINVAL;
 448                 return -1;
 449         }
 450         *nh = node->nh;
 451         return 0;
 452 }
 453
 454 int
 455 rte_rib6_set_nh(struct rte_rib6_node *node, uint64_t nh)
 456 {
 457         if (node == NULL) {
 458                 rte_errno = EINVAL;
 459                 return -1;
 460         }
 461         node->nh = nh;
 462         return 0;
 463 }
 464
 465 struct rte_rib6 *
 466 rte_rib6_create(const char *name, int socket_id,
 467                 const struct rte_rib6_conf *conf)
 468 {
 469         char mem_name[RTE_RIB6_NAMESIZE];
 470         struct rte_rib6 *rib = NULL;
 471         struct rte_tailq_entry *te;
 472         struct rte_rib6_list *rib6_list;
 473         struct rte_mempool *node_pool;
 474
 475         /* Check user arguments. */
 476         if (name == NULL || conf == NULL || conf->max_nodes <= 0) {
 477                 rte_errno = EINVAL;
 478                 return NULL;
 479         }
 480
 481         snprintf(mem_name, sizeof(mem_name), "MP_%s", name);
 482         node_pool = rte_mempool_create(mem_name, conf->max_nodes,
 483                 sizeof(struct rte_rib6_node) + conf->ext_sz, 0, 0,
 484                 NULL, NULL, NULL, NULL, socket_id, 0);
 485
 486         if (node_pool == NULL) {
 487                 RTE_LOG(ERR, LPM,
 488                         "Can not allocate mempool for RIB6 %s\n", name);
 489                 return NULL;
 490         }
 491
 492         snprintf(mem_name, sizeof(mem_name), "RIB6_%s", name);
 493         rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
 494
 495         rte_mcfg_tailq_write_lock();
 496
 497         /* guarantee there's no existing */
 498         TAILQ_FOREACH(te, rib6_list, next) {
 499                 rib = (struct rte_rib6 *)te->data;
 500                 if (strncmp(name, rib->name, RTE_RIB6_NAMESIZE) == 0)
 501                         break;
 502         }
 503         rib = NULL;
 504         if (te != NULL) {
 505                 rte_errno = EEXIST;
 506                 goto exit;
 507         }
 508
 509         /* allocate tailq entry */
 510         te = rte_zmalloc("RIB6_TAILQ_ENTRY", sizeof(*te), 0);
 511         if (te == NULL) {
 512                 RTE_LOG(ERR, LPM,
 513                         "Can not allocate tailq entry for RIB6 %s\n", name);
 514                 rte_errno = ENOMEM;
 515                 goto exit;
 516         }
 517
 518         /* Allocate memory to store the RIB6 data structures. */
 519         rib = rte_zmalloc_socket(mem_name,
 520                 sizeof(struct rte_rib6), RTE_CACHE_LINE_SIZE, socket_id);
 521         if (rib == NULL) {
 522                 RTE_LOG(ERR, LPM, "RIB6 %s memory allocation failed\n", name);
 523                 rte_errno = ENOMEM;
 524                 goto free_te;
 525         }
 526
 527         rte_strlcpy(rib->name, name, sizeof(rib->name));
 528         rib->tree = NULL;
 529         rib->max_nodes = conf->max_nodes;
 530         rib->node_pool = node_pool;
 531
 532         te->data = (void *)rib;
 533         TAILQ_INSERT_TAIL(rib6_list, te, next);
 534
 535         rte_mcfg_tailq_write_unlock();
 536
 537         return rib;
 538
 539 free_te:
 540         rte_free(te);
 541 exit:
 542         rte_mcfg_tailq_write_unlock();
 543         rte_mempool_free(node_pool);
 544
 545         return NULL;
 546 }
 547
 548 struct rte_rib6 *
 549 rte_rib6_find_existing(const char *name)
 550 {
 551         struct rte_rib6 *rib = NULL;
 552         struct rte_tailq_entry *te;
 553         struct rte_rib6_list *rib6_list;
 554
 555         if (unlikely(name == NULL)) {
 556                 rte_errno = EINVAL;
 557                 return NULL;
 558         }
 559
 560         rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
 561
 562         rte_mcfg_tailq_read_lock();
 563         TAILQ_FOREACH(te, rib6_list, next) {
 564                 rib = (struct rte_rib6 *) te->data;
 565                 if (strncmp(name, rib->name, RTE_RIB6_NAMESIZE) == 0)
 566                         break;
 567         }
 568         rte_mcfg_tailq_read_unlock();
 569
 570         if (te == NULL) {
 571                 rte_errno = ENOENT;
 572                 return NULL;
 573         }
 574
 575         return rib;
 576 }
 577
 578 void
 579 rte_rib6_free(struct rte_rib6 *rib)
 580 {
 581         struct rte_tailq_entry *te;
 582         struct rte_rib6_list *rib6_list;
 583         struct rte_rib6_node *tmp = NULL;
 584
 585         if (unlikely(rib == NULL)) {
 586                 rte_errno = EINVAL;
 587                 return;
 588         }
 589
 590         rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
 591
 592         rte_mcfg_tailq_write_lock();
 593
 594         /* find our tailq entry */
 595         TAILQ_FOREACH(te, rib6_list, next) {
 596                 if (te->data == (void *)rib)
 597                         break;
 598         }
 599         if (te != NULL)
 600                 TAILQ_REMOVE(rib6_list, te, next);
 601
 602         rte_mcfg_tailq_write_unlock();
 603
 604         while ((tmp = rte_rib6_get_nxt(rib, 0, 0, tmp,
 605                         RTE_RIB6_GET_NXT_ALL)) != NULL)
 606                 rte_rib6_remove(rib, tmp->ip, tmp->depth);
 607
 608         rte_mempool_free(rib->node_pool);
 609
 610         rte_free(rib);
 611         rte_free(te);
 612 }