LXR dpdk/lib/rib/rte

   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
  20TAILQ_HEAD(rte_rib_list, rte_tailq_entry);
  21static struct rte_tailq_elem rte_rib_tailq = {
  22        .name = "RTE_RIB",
  23};
  24EAL_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
  32struct 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
  43struct 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
  52static inline bool
  53is_valid_node(struct rte_rib_node *node)
  54{
  55        return (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE;
  56}
  57
  58static inline bool
  59is_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 */
  67static inline bool
  68is_covered(uint32_t ip1, uint32_t ip2, uint8_t depth)
  69{
  70        return ((ip1 ^ ip2) & rte_rib_depth_to_mask(depth)) == 0;
  71}
  72
  73static inline struct rte_rib_node *
  74get_nxt_node(struct rte_rib_node *node, uint32_t ip)
  75{
  76        return (ip & (1 << (31 - node->depth))) ? node->right : node->left;
  77}
  78
  79static struct rte_rib_node *
  80node_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
  92static void
  93node_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
  99struct rte_rib_node *
 100rte_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
 118struct rte_rib_node *
 119rte_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
 131static 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
 149struct rte_rib_node *
 150rte_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 */
 166struct rte_rib_node *
 167rte_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
 206void
 207rte_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
 238struct rte_rib_node *
 239rte_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
 344int
 345rte_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
 355int
 356rte_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
 366void *
 367rte_rib_get_ext(struct rte_rib_node *node)
 368{
 369        return (node == NULL) ? NULL : &node->ext[0];
 370}
 371
 372int
 373rte_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
 383int
 384rte_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
 394struct rte_rib *
 395rte_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
 466free_te:
 467        rte_free(te);
 468exit:
 469        rte_mcfg_tailq_write_unlock();
 470        rte_mempool_free(node_pool);
 471
 472        return NULL;
 473}
 474
 475struct rte_rib *
 476rte_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
 500void
 501rte_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}
 532