LCOV - code coverage report
Current view: top level - lib/rib - rte_rib6.h (source / functions) Hit Total Coverage
Test: Code coverage Lines: 8 8 100.0 %
Date: 2024-02-14 00:53:57 Functions: 0 0 -
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 23 32 71.9 %

           Branch data     Line data    Source code
       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                 :            : #ifndef _RTE_RIB6_H_
       7                 :            : #define _RTE_RIB6_H_
       8                 :            : 
       9                 :            : /**
      10                 :            :  * @file
      11                 :            :  *
      12                 :            :  * RTE rib6 library.
      13                 :            :  *
      14                 :            :  * Level compressed tree implementation for IPv6 Longest Prefix Match
      15                 :            :  */
      16                 :            : 
      17                 :            : #include <rte_memcpy.h>
      18                 :            : #include <rte_common.h>
      19                 :            : 
      20                 :            : #ifdef __cplusplus
      21                 :            : extern "C" {
      22                 :            : #endif
      23                 :            : 
      24                 :            : #define RTE_RIB6_IPV6_ADDR_SIZE 16
      25                 :            : 
      26                 :            : /**
      27                 :            :  * rte_rib6_get_nxt() flags
      28                 :            :  */
      29                 :            : enum {
      30                 :            :         /** flag to get all subroutes in a RIB tree */
      31                 :            :         RTE_RIB6_GET_NXT_ALL,
      32                 :            :         /** flag to get first matched subroutes in a RIB tree */
      33                 :            :         RTE_RIB6_GET_NXT_COVER
      34                 :            : };
      35                 :            : 
      36                 :            : struct rte_rib6;
      37                 :            : struct rte_rib6_node;
      38                 :            : 
      39                 :            : /** RIB configuration structure */
      40                 :            : struct rte_rib6_conf {
      41                 :            :         /**
      42                 :            :          * Size of extension block inside rte_rib6_node.
      43                 :            :          * This space could be used to store additional user
      44                 :            :          * defined data.
      45                 :            :          */
      46                 :            :         size_t  ext_sz;
      47                 :            :         /* size of rte_rib6_node's pool */
      48                 :            :         int     max_nodes;
      49                 :            : };
      50                 :            : 
      51                 :            : /**
      52                 :            :  * Copy IPv6 address from one location to another
      53                 :            :  *
      54                 :            :  * @param dst
      55                 :            :  *  pointer to the place to copy
      56                 :            :  * @param src
      57                 :            :  *  pointer from where to copy
      58                 :            :  */
      59                 :            : static inline void
      60                 :            : rte_rib6_copy_addr(uint8_t *dst, const uint8_t *src)
      61                 :            : {
      62   [ +  -  +  -  :       5371 :         if ((dst == NULL) || (src == NULL))
                   +  - ]
      63                 :            :                 return;
      64                 :            :         rte_memcpy(dst, src, RTE_RIB6_IPV6_ADDR_SIZE);
      65                 :            : }
      66                 :            : 
      67                 :            : /**
      68                 :            :  * Compare two IPv6 addresses
      69                 :            :  *
      70                 :            :  * @param ip1
      71                 :            :  *  pointer to the first ipv6 address
      72                 :            :  * @param ip2
      73                 :            :  *  pointer to the second ipv6 address
      74                 :            :  *
      75                 :            :  * @return
      76                 :            :  *  1 if equal
      77                 :            :  *  0 otherwise
      78                 :            :  */
      79                 :            : static inline int
      80                 :            : rte_rib6_is_equal(const uint8_t *ip1, const uint8_t *ip2) {
      81                 :            :         int i;
      82                 :            : 
      83                 :            :         if ((ip1 == NULL) || (ip2 == NULL))
      84                 :            :                 return 0;
      85   [ +  +  +  +  :    2858970 :         for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) {
             +  +  -  - ]
      86   [ +  +  +  +  :    2691564 :                 if (ip1[i] != ip2[i])
             +  +  -  - ]
      87                 :            :                         return 0;
      88                 :            :         }
      89                 :            :         return 1;
      90                 :            : }
      91                 :            : 
      92                 :            : /**
      93                 :            :  * Get 8-bit part of 128-bit IPv6 mask
      94                 :            :  *
      95                 :            :  * @param depth
      96                 :            :  *  ipv6 prefix length
      97                 :            :  * @param byte
      98                 :            :  *  position of a 8-bit chunk in the 128-bit mask
      99                 :            :  *
     100                 :            :  * @return
     101                 :            :  *  8-bit chunk of the 128-bit IPv6 mask
     102                 :            :  */
     103                 :            : static inline uint8_t
     104                 :            : get_msk_part(uint8_t depth, int byte) {
     105                 :            :         uint8_t part;
     106                 :            : 
     107                 :     179824 :         byte &= 0xf;
     108                 :   36940006 :         depth = RTE_MIN(depth, 128);
     109                 :   36940006 :         part = RTE_MAX((int16_t)depth - (byte * 8), 0);
     110                 :   36940006 :         part = (part > 8) ? 8 : part;
     111   [ +  +  +  -  :   36940006 :         return (uint16_t)(~UINT8_MAX) >> part;
          +  -  +  +  +  
                      + ]
     112                 :            : }
     113                 :            : 
     114                 :            : /**
     115                 :            :  * Lookup an IP into the RIB structure
     116                 :            :  *
     117                 :            :  * @param rib
     118                 :            :  *  RIB object handle
     119                 :            :  * @param ip
     120                 :            :  *  IP to be looked up in the RIB
     121                 :            :  * @return
     122                 :            :  *  pointer to struct rte_rib6_node on success
     123                 :            :  *  NULL otherwise
     124                 :            :  */
     125                 :            : struct rte_rib6_node *
     126                 :            : rte_rib6_lookup(struct rte_rib6 *rib,
     127                 :            :         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE]);
     128                 :            : 
     129                 :            : /**
     130                 :            :  * Lookup less specific route into the RIB structure
     131                 :            :  *
     132                 :            :  * @param ent
     133                 :            :  *  Pointer to struct rte_rib6_node that represents target route
     134                 :            :  * @return
     135                 :            :  *  pointer to struct rte_rib6_node that represents
     136                 :            :  *   less specific route on success
     137                 :            :  *  NULL otherwise
     138                 :            :  */
     139                 :            : struct rte_rib6_node *
     140                 :            : rte_rib6_lookup_parent(struct rte_rib6_node *ent);
     141                 :            : 
     142                 :            : /**
     143                 :            :  * Provides exact mach lookup of the prefix into the RIB structure
     144                 :            :  *
     145                 :            :  * @param rib
     146                 :            :  *  RIB object handle
     147                 :            :  * @param ip
     148                 :            :  *  net to be looked up in the RIB
     149                 :            :  * @param depth
     150                 :            :  *  prefix length
     151                 :            :  * @return
     152                 :            :  *  pointer to struct rte_rib6_node on success
     153                 :            :  *  NULL otherwise
     154                 :            :  */
     155                 :            : struct rte_rib6_node *
     156                 :            : rte_rib6_lookup_exact(struct rte_rib6 *rib,
     157                 :            :         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth);
     158                 :            : 
     159                 :            : /**
     160                 :            :  * Retrieve next more specific prefix from the RIB
     161                 :            :  * that is covered by ip/depth supernet in an ascending order
     162                 :            :  *
     163                 :            :  * @param rib
     164                 :            :  *  RIB object handle
     165                 :            :  * @param ip
     166                 :            :  *  net address of supernet prefix that covers returned more specific prefixes
     167                 :            :  * @param depth
     168                 :            :  *  supernet prefix length
     169                 :            :  * @param last
     170                 :            :  *   pointer to the last returned prefix to get next prefix
     171                 :            :  *   or
     172                 :            :  *   NULL to get first more specific prefix
     173                 :            :  * @param flag
     174                 :            :  *  -RTE_RIB6_GET_NXT_ALL
     175                 :            :  *   get all prefixes from subtrie
     176                 :            :  *  -RTE_RIB6_GET_NXT_COVER
     177                 :            :  *   get only first more specific prefix even if it have more specifics
     178                 :            :  * @return
     179                 :            :  *  pointer to the next more specific prefix
     180                 :            :  *  NULL if there is no prefixes left
     181                 :            :  */
     182                 :            : struct rte_rib6_node *
     183                 :            : rte_rib6_get_nxt(struct rte_rib6 *rib,
     184                 :            :         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE],
     185                 :            :         uint8_t depth, struct rte_rib6_node *last, int flag);
     186                 :            : 
     187                 :            : /**
     188                 :            :  * Remove prefix from the RIB
     189                 :            :  *
     190                 :            :  * @param rib
     191                 :            :  *  RIB object handle
     192                 :            :  * @param ip
     193                 :            :  *  net to be removed from the RIB
     194                 :            :  * @param depth
     195                 :            :  *  prefix length
     196                 :            :  */
     197                 :            : void
     198                 :            : rte_rib6_remove(struct rte_rib6 *rib,
     199                 :            :         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth);
     200                 :            : 
     201                 :            : /**
     202                 :            :  * Insert prefix into the RIB
     203                 :            :  *
     204                 :            :  * @param rib
     205                 :            :  *  RIB object handle
     206                 :            :  * @param ip
     207                 :            :  *  net to be inserted to the RIB
     208                 :            :  * @param depth
     209                 :            :  *  prefix length
     210                 :            :  * @return
     211                 :            :  *  pointer to new rte_rib6_node on success
     212                 :            :  *  NULL otherwise
     213                 :            :  */
     214                 :            : struct rte_rib6_node *
     215                 :            : rte_rib6_insert(struct rte_rib6 *rib,
     216                 :            :         const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth);
     217                 :            : 
     218                 :            : /**
     219                 :            :  * Get an ip from rte_rib6_node
     220                 :            :  *
     221                 :            :  * @param node
     222                 :            :  *  pointer to the rib6 node
     223                 :            :  * @param ip
     224                 :            :  *  pointer to the ipv6 to save
     225                 :            :  * @return
     226                 :            :  *  0 on success
     227                 :            :  *  -1 on failure with rte_errno indicating reason for failure.
     228                 :            :  */
     229                 :            : int
     230                 :            : rte_rib6_get_ip(const struct rte_rib6_node *node,
     231                 :            :                 uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE]);
     232                 :            : 
     233                 :            : /**
     234                 :            :  * Get a depth from rte_rib6_node
     235                 :            :  *
     236                 :            :  * @param node
     237                 :            :  *  pointer to the rib6 node
     238                 :            :  * @param depth
     239                 :            :  *  pointer to the depth to save
     240                 :            :  * @return
     241                 :            :  *  0 on success
     242                 :            :  *  -1 on failure with rte_errno indicating reason for failure.
     243                 :            :  */
     244                 :            : int
     245                 :            : rte_rib6_get_depth(const struct rte_rib6_node *node, uint8_t *depth);
     246                 :            : 
     247                 :            : /**
     248                 :            :  * Get ext field from the rte_rib6_node
     249                 :            :  * It is caller responsibility to make sure there are necessary space
     250                 :            :  * for the ext field inside rib6 node.
     251                 :            :  *
     252                 :            :  * @param node
     253                 :            :  *  pointer to the rte_rib6_node
     254                 :            :  * @return
     255                 :            :  *  pointer to the ext
     256                 :            :  */
     257                 :            : void *
     258                 :            : rte_rib6_get_ext(struct rte_rib6_node *node);
     259                 :            : 
     260                 :            : /**
     261                 :            :  * Get nexthop from the rte_rib6_node
     262                 :            :  *
     263                 :            :  * @param node
     264                 :            :  *  pointer to the rib6 node
     265                 :            :  * @param nh
     266                 :            :  *  pointer to the nexthop to save
     267                 :            :  * @return
     268                 :            :  *  0 on success
     269                 :            :  *  -1 on failure, with rte_errno indicating reason for failure.
     270                 :            :  */
     271                 :            : int
     272                 :            : rte_rib6_get_nh(const struct rte_rib6_node *node, uint64_t *nh);
     273                 :            : 
     274                 :            : /**
     275                 :            :  * Set nexthop into the rte_rib6_node
     276                 :            :  *
     277                 :            :  * @param node
     278                 :            :  *  pointer to the rib6 node
     279                 :            :  * @param nh
     280                 :            :  *  nexthop value to set to the rib6 node
     281                 :            :  * @return
     282                 :            :  *  0 on success
     283                 :            :  *  -1 on failure, with rte_errno indicating reason for failure.
     284                 :            :  */
     285                 :            : int
     286                 :            : rte_rib6_set_nh(struct rte_rib6_node *node, uint64_t nh);
     287                 :            : 
     288                 :            : /**
     289                 :            :  * Create RIB
     290                 :            :  *
     291                 :            :  * @param name
     292                 :            :  *  RIB name
     293                 :            :  * @param socket_id
     294                 :            :  *  NUMA socket ID for RIB table memory allocation
     295                 :            :  * @param conf
     296                 :            :  *  Structure containing the configuration
     297                 :            :  * @return
     298                 :            :  *  Pointer to RIB object on success
     299                 :            :  *  NULL otherwise with rte_errno indicating reason for failure.
     300                 :            :  */
     301                 :            : struct rte_rib6 *
     302                 :            : rte_rib6_create(const char *name, int socket_id,
     303                 :            :                 const struct rte_rib6_conf *conf);
     304                 :            : 
     305                 :            : /**
     306                 :            :  * Find an existing RIB object and return a pointer to it.
     307                 :            :  *
     308                 :            :  * @param name
     309                 :            :  *  Name of the rib object as passed to rte_rib6_create()
     310                 :            :  * @return
     311                 :            :  *  Pointer to RIB object on success
     312                 :            :  *  NULL otherwise with rte_errno indicating reason for failure.
     313                 :            :  */
     314                 :            : struct rte_rib6 *
     315                 :            : rte_rib6_find_existing(const char *name);
     316                 :            : 
     317                 :            : /**
     318                 :            :  * Free an RIB object.
     319                 :            :  *
     320                 :            :  * @param rib
     321                 :            :  *   RIB object handle created with rte_rib6_create().
     322                 :            :  *   If rib is NULL, no operation is performed.
     323                 :            :  */
     324                 :            : void
     325                 :            : rte_rib6_free(struct rte_rib6 *rib);
     326                 :            : 
     327                 :            : #ifdef __cplusplus
     328                 :            : }
     329                 :            : #endif
     330                 :            : 
     331                 :            : #endif /* _RTE_RIB6_H_ */

Generated by: LCOV version 1.14