lib/rib/rte_rib.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_rib.h>
  19
  20 TAILQ_HEAD(rte_rib_list, rte_tailq_entry);
  21 static struct rte_tailq_elem rte_rib_tailq = {
  22         .name = "RTE_RIB",
  23 };
  24 EAL_REGISTER_TAILQ(rte_rib_tailq)
  25
  26 #define RTE_RIB_VALID_NODE      1
  27 /* Maximum depth value possible for IPv4 RIB. */
  28 #define RIB_MAXDEPTH            32
  29 /* Maximum length of a RIB name. */
  30 #define RTE_RIB_NAMESIZE        64
  31
  32 struct rte_rib_node {
  33         struct rte_rib_node     *left;
  34         struct rte_rib_node     *right;
  35         struct rte_rib_node     *parent;
  36         uint32_t        ip;
  37         uint8_t         depth;
  38         uint8_t         flag;
  39         uint64_t        nh;
  40         __extension__ uint64_t  ext[0];
  41 };
  42
  43 struct rte_rib {
  44         char            name[RTE_RIB_NAMESIZE];
  45         struct rte_rib_node     *tree;
  46         struct rte_mempool      *node_pool;
  47         uint32_t                cur_nodes;
  48         uint32_t                cur_routes;
  49         uint32_t                max_nodes;
  50 };
  51
  52 static inline bool
  53 is_valid_node(struct rte_rib_node *node)
  54 {
  55         return (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE;
  56 }
  57
  58 static inline bool
  59 is_right_node(struct rte_rib_node *node)
  60 {
  61         return node->parent->right == node;
  62 }
  63
  64 /*
  65  * Check if ip1 is covered by ip2/depth prefix
  66  */
  67 static inline bool
  68 is_covered(uint32_t ip1, uint32_t ip2, uint8_t depth)
  69 {
  70         return ((ip1 ^ ip2) & rte_rib_depth_to_mask(depth)) == 0;
  71 }
  72
  73 static inline struct rte_rib_node *
  74 get_nxt_node(struct rte_rib_node *node, uint32_t ip)
  75 {
  76         return (ip & (1 << (31 - node->depth))) ? node->right : node->left;
  77 }
  78
  79 static struct rte_rib_node *
  80 node_alloc(struct rte_rib *rib)
  81 {
  82         struct rte_rib_node *ent;
  83         int ret;
  84
  85         ret = rte_mempool_get(rib->node_pool, (void *)&ent);
  86         if (unlikely(ret != 0))
  87                 return NULL;
  88         ++rib->cur_nodes;
  89         return ent;
  90 }
  91
  92 static void
  93 node_free(struct rte_rib *rib, struct rte_rib_node *ent)
  94 {
  95         --rib->cur_nodes;
  96         rte_mempool_put(rib->node_pool, ent);
  97 }
  98
  99 struct rte_rib_node *
 100 rte_rib_lookup(struct rte_rib *rib, uint32_t ip)
 101 {
 102         struct rte_rib_node *cur, *prev = NULL;
 103
 104         if (rib == NULL) {
 105                 rte_errno = EINVAL;
 106                 return NULL;
 107         }
 108
 109         cur = rib->tree;
 110         while ((cur != NULL) && is_covered(ip, cur->ip, cur->depth)) {
 111                 if (is_valid_node(cur))
 112                         prev = cur;
 113                 cur = get_nxt_node(cur, ip);
 114         }
 115         return prev;
 116 }
 117
 118 struct rte_rib_node *
 119 rte_rib_lookup_parent(struct rte_rib_node *ent)
 120 {
 121         struct rte_rib_node *tmp;
 122
 123         if (ent == NULL)
 124                 return NULL;
 125         tmp = ent->parent;
 126         while ((tmp != NULL) && !is_valid_node(tmp))
 127                 tmp = tmp->parent;
 128         return tmp;
 129 }
 130
 131 static struct rte_rib_node *
 132 __rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth)
 133 {
 134         struct rte_rib_node *cur;
 135
 136         cur = rib->tree;
 137         while (cur != NULL) {
 138                 if ((cur->ip == ip) && (cur->depth == depth) &&
 139                                 is_valid_node(cur))
 140                         return cur;
 141                 if ((cur->depth > depth) ||
 142                                 !is_covered(ip, cur->ip, cur->depth))
 143                         break;
 144                 cur = get_nxt_node(cur, ip);
 145         }
 146         return NULL;
 147 }
 148
 149 struct rte_rib_node *
 150 rte_rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth)
 151 {
 152         if ((rib == NULL) || (depth > RIB_MAXDEPTH)) {
 153                 rte_errno = EINVAL;
 154                 return NULL;
 155         }
 156         ip &= rte_rib_depth_to_mask(depth);
 157
 158         return __rib_lookup_exact(rib, ip, depth);
 159 }
 160
 161 /*
 162  *  Traverses on subtree and retrieves more specific routes
 163  *  for a given in args ip/depth prefix
 164  *  last = NULL means the first invocation
 165  */
 166 struct rte_rib_node *
 167 rte_rib_get_nxt(struct rte_rib *rib, uint32_t ip,
 168         uint8_t depth, struct rte_rib_node *last, int flag)
 169 {
 170         struct rte_rib_node *tmp, *prev = NULL;
 171
 172         if ((rib == NULL) || (depth > RIB_MAXDEPTH)) {
 173                 rte_errno = EINVAL;
 174                 return NULL;
 175         }
 176
 177         if (last == NULL) {
 178                 tmp = rib->tree;
 179                 while ((tmp) && (tmp->depth < depth))
 180                         tmp = get_nxt_node(tmp, ip);
 181         } else {
 182                 tmp = last;
 183                 while ((tmp->parent != NULL) && (is_right_node(tmp) ||
 184                                 (tmp->parent->right == NULL))) {
 185                         tmp = tmp->parent;
 186                         if (is_valid_node(tmp) &&
 187                                         (is_covered(tmp->ip, ip, depth) &&
 188                                         (tmp->depth > depth)))
 189                                 return tmp;
 190                 }
 191                 tmp = (tmp->parent) ? tmp->parent->right : NULL;
 192         }
 193         while (tmp) {
 194                 if (is_valid_node(tmp) &&
 195                                 (is_covered(tmp->ip, ip, depth) &&
 196                                 (tmp->depth > depth))) {
 197                         prev = tmp;
 198                         if (flag == RTE_RIB_GET_NXT_COVER)
 199                                 return prev;
 200                 }
 201                 tmp = (tmp->left) ? tmp->left : tmp->right;
 202         }
 203         return prev;
 204 }
 205
 206 void
 207 rte_rib_remove(struct rte_rib *rib, uint32_t ip, uint8_t depth)
 208 {
 209         struct rte_rib_node *cur, *prev, *child;
 210
 211         cur = rte_rib_lookup_exact(rib, ip, depth);
 212         if (cur == NULL)
 213                 return;
 214
 215         --rib->cur_routes;
 216         cur->flag &= ~RTE_RIB_VALID_NODE;
 217         while (!is_valid_node(cur)) {
 218                 if ((cur->left != NULL) && (cur->right != NULL))
 219                         return;
 220                 child = (cur->left == NULL) ? cur->right : cur->left;
 221                 if (child != NULL)
 222                         child->parent = cur->parent;
 223                 if (cur->parent == NULL) {
 224                         rib->tree = child;
 225                         node_free(rib, cur);
 226                         return;
 227                 }
 228                 if (cur->parent->left == cur)
 229                         cur->parent->left = child;
 230                 else
 231                         cur->parent->right = child;
 232                 prev = cur;
 233                 cur = cur->parent;
 234                 node_free(rib, prev);
 235         }
 236 }
 237
 238 struct rte_rib_node *
 239 rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth)
 240 {
 241         struct rte_rib_node **tmp;
 242         struct rte_rib_node *prev = NULL;
 243         struct rte_rib_node *new_node = NULL;
 244         struct rte_rib_node *common_node = NULL;
 245         int d = 0;
 246         uint32_t common_prefix;
 247         uint8_t common_depth;
 248
 249         if ((rib == NULL) || (depth > RIB_MAXDEPTH)) {
 250                 rte_errno = EINVAL;
 251                 return NULL;
 252         }
 253
 254         tmp = &rib->tree;
 255         ip &= rte_rib_depth_to_mask(depth);
 256         new_node = __rib_lookup_exact(rib, ip, depth);
 257         if (new_node != NULL) {
 258                 rte_errno = EEXIST;
 259                 return NULL;
 260         }
 261
 262         new_node = node_alloc(rib);
 263         if (new_node == NULL) {
 264                 rte_errno = ENOMEM;
 265                 return NULL;
 266         }
 267         new_node->left = NULL;
 268         new_node->right = NULL;
 269         new_node->parent = NULL;
 270         new_node->ip = ip;
 271         new_node->depth = depth;
 272         new_node->flag = RTE_RIB_VALID_NODE;
 273
 274         /* traverse down the tree to find matching node or closest matching */
 275         while (1) {
 276                 /* insert as the last node in the branch */
 277                 if (*tmp == NULL) {
 278                         *tmp = new_node;
 279                         new_node->parent = prev;
 280                         ++rib->cur_routes;
 281                         return *tmp;
 282                 }
 283                 /*
 284                  * Intermediate node found.
 285                  * Previous rte_rib_lookup_exact() returned NULL
 286                  * but node with proper search criteria is found.
 287                  * Validate intermediate node and return.
 288                  */
 289                 if ((ip == (*tmp)->ip) && (depth == (*tmp)->depth)) {
 290                         node_free(rib, new_node);
 291                         (*tmp)->flag |= RTE_RIB_VALID_NODE;
 292                         ++rib->cur_routes;
 293                         return *tmp;
 294                 }
 295                 d = (*tmp)->depth;
 296                 if ((d >= depth) || !is_covered(ip, (*tmp)->ip, d))
 297                         break;
 298                 prev = *tmp;
 299                 tmp = (ip & (1 << (31 - d))) ? &(*tmp)->right : &(*tmp)->left;
 300         }
 301         /* closest node found, new_node should be inserted in the middle */
 302         common_depth = RTE_MIN(depth, (*tmp)->depth);
 303         common_prefix = ip ^ (*tmp)->ip;
 304         d = (common_prefix == 0) ? 32 : __builtin_clz(common_prefix);
 305
 306         common_depth = RTE_MIN(d, common_depth);
 307         common_prefix = ip & rte_rib_depth_to_mask(common_depth);
 308         if ((common_prefix == ip) && (common_depth == depth)) {
 309                 /* insert as a parent */
 310                 if ((*tmp)->ip & (1 << (31 - depth)))
 311                         new_node->right = *tmp;
 312                 else
 313                         new_node->left = *tmp;
 314                 new_node->parent = (*tmp)->parent;
 315                 (*tmp)->parent = new_node;
 316                 *tmp = new_node;
 317         } else {
 318                 /* create intermediate node */
 319                 common_node = node_alloc(rib);
 320                 if (common_node == NULL) {
 321                         node_free(rib, new_node);
 322                         rte_errno = ENOMEM;
 323                         return NULL;
 324                 }
 325                 common_node->ip = common_prefix;
 326                 common_node->depth = common_depth;
 327                 common_node->flag = 0;
 328                 common_node->parent = (*tmp)->parent;
 329                 new_node->parent = common_node;
 330                 (*tmp)->parent = common_node;
 331                 if ((new_node->ip & (1 << (31 - common_depth))) == 0) {
 332                         common_node->left = new_node;
 333                         common_node->right = *tmp;
 334                 } else {
 335                         common_node->left = *tmp;
 336                         common_node->right = new_node;
 337                 }
 338                 *tmp = common_node;
 339         }
 340         ++rib->cur_routes;
 341         return new_node;
 342 }
 343
 344 int
 345 rte_rib_get_ip(const struct rte_rib_node *node, uint32_t *ip)
 346 {
 347         if ((node == NULL) || (ip == NULL)) {
 348                 rte_errno = EINVAL;
 349                 return -1;
 350         }
 351         *ip = node->ip;
 352         return 0;
 353 }
 354
 355 int
 356 rte_rib_get_depth(const struct rte_rib_node *node, uint8_t *depth)
 357 {
 358         if ((node == NULL) || (depth == NULL)) {
 359                 rte_errno = EINVAL;
 360                 return -1;
 361         }
 362         *depth = node->depth;
 363         return 0;
 364 }
 365
 366 void *
 367 rte_rib_get_ext(struct rte_rib_node *node)
 368 {
 369         return (node == NULL) ? NULL : &node->ext[0];
 370 }
 371
 372 int
 373 rte_rib_get_nh(const struct rte_rib_node *node, uint64_t *nh)
 374 {
 375         if ((node == NULL) || (nh == NULL)) {
 376                 rte_errno = EINVAL;
 377                 return -1;
 378         }
 379         *nh = node->nh;
 380         return 0;
 381 }
 382
 383 int
 384 rte_rib_set_nh(struct rte_rib_node *node, uint64_t nh)
 385 {
 386         if (node == NULL) {
 387                 rte_errno = EINVAL;
 388                 return -1;
 389         }
 390         node->nh = nh;
 391         return 0;
 392 }
 393
 394 struct rte_rib *
 395 rte_rib_create(const char *name, int socket_id, const struct rte_rib_conf *conf)
 396 {
 397         char mem_name[RTE_RIB_NAMESIZE];
 398         struct rte_rib *rib = NULL;
 399         struct rte_tailq_entry *te;
 400         struct rte_rib_list *rib_list;
 401         struct rte_mempool *node_pool;
 402
 403         /* Check user arguments. */
 404         if (name == NULL || conf == NULL || conf->max_nodes <= 0) {
 405                 rte_errno = EINVAL;
 406                 return NULL;
 407         }
 408
 409         snprintf(mem_name, sizeof(mem_name), "MP_%s", name);
 410         node_pool = rte_mempool_create(mem_name, conf->max_nodes,
 411                 sizeof(struct rte_rib_node) + conf->ext_sz, 0, 0,
 412                 NULL, NULL, NULL, NULL, socket_id, 0);
 413
 414         if (node_pool == NULL) {
 415                 RTE_LOG(ERR, LPM,
 416                         "Can not allocate mempool for RIB %s\n", name);
 417                 return NULL;
 418         }
 419
 420         snprintf(mem_name, sizeof(mem_name), "RIB_%s", name);
 421         rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
 422
 423         rte_mcfg_tailq_write_lock();
 424
 425         /* guarantee there's no existing */
 426         TAILQ_FOREACH(te, rib_list, next) {
 427                 rib = (struct rte_rib *)te->data;
 428                 if (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0)
 429                         break;
 430         }
 431         rib = NULL;
 432         if (te != NULL) {
 433                 rte_errno = EEXIST;
 434                 goto exit;
 435         }
 436
 437         /* allocate tailq entry */
 438         te = rte_zmalloc("RIB_TAILQ_ENTRY", sizeof(*te), 0);
 439         if (te == NULL) {
 440                 RTE_LOG(ERR, LPM,
 441                         "Can not allocate tailq entry for RIB %s\n", name);
 442                 rte_errno = ENOMEM;
 443                 goto exit;
 444         }
 445
 446         /* Allocate memory to store the RIB data structures. */
 447         rib = rte_zmalloc_socket(mem_name,
 448                 sizeof(struct rte_rib), RTE_CACHE_LINE_SIZE, socket_id);
 449         if (rib == NULL) {
 450                 RTE_LOG(ERR, LPM, "RIB %s memory allocation failed\n", name);
 451                 rte_errno = ENOMEM;
 452                 goto free_te;
 453         }
 454
 455         rte_strlcpy(rib->name, name, sizeof(rib->name));
 456         rib->tree = NULL;
 457         rib->max_nodes = conf->max_nodes;
 458         rib->node_pool = node_pool;
 459         te->data = (void *)rib;
 460         TAILQ_INSERT_TAIL(rib_list, te, next);
 461
 462         rte_mcfg_tailq_write_unlock();
 463
 464         return rib;
 465
 466 free_te:
 467         rte_free(te);
 468 exit:
 469         rte_mcfg_tailq_write_unlock();
 470         rte_mempool_free(node_pool);
 471
 472         return NULL;
 473 }
 474
 475 struct rte_rib *
 476 rte_rib_find_existing(const char *name)
 477 {
 478         struct rte_rib *rib = NULL;
 479         struct rte_tailq_entry *te;
 480         struct rte_rib_list *rib_list;
 481
 482         rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
 483
 484         rte_mcfg_tailq_read_lock();
 485         TAILQ_FOREACH(te, rib_list, next) {
 486                 rib = (struct rte_rib *) te->data;
 487                 if (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0)
 488                         break;
 489         }
 490         rte_mcfg_tailq_read_unlock();
 491
 492         if (te == NULL) {
 493                 rte_errno = ENOENT;
 494                 return NULL;
 495         }
 496
 497         return rib;
 498 }
 499
 500 void
 501 rte_rib_free(struct rte_rib *rib)
 502 {
 503         struct rte_tailq_entry *te;
 504         struct rte_rib_list *rib_list;
 505         struct rte_rib_node *tmp = NULL;
 506
 507         if (rib == NULL)
 508                 return;
 509
 510         rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
 511
 512         rte_mcfg_tailq_write_lock();
 513
 514         /* find our tailq entry */
 515         TAILQ_FOREACH(te, rib_list, next) {
 516                 if (te->data == (void *)rib)
 517                         break;
 518         }
 519         if (te != NULL)
 520                 TAILQ_REMOVE(rib_list, te, next);
 521
 522         rte_mcfg_tailq_write_unlock();
 523
 524         while ((tmp = rte_rib_get_nxt(rib, 0, 0, tmp,
 525                         RTE_RIB_GET_NXT_ALL)) != NULL)
 526                 rte_rib_remove(rib, tmp->ip, tmp->depth);
 527
 528         rte_mempool_free(rib->node_pool);
 529         rte_free(rib);
 530         rte_free(te);
 531 }