src/vnet/fib/fib_node.h

   1 /*
   2  * Copyright (c) 2016 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #ifndef __FIB_NODE_H__
  17 #define __FIB_NODE_H__
  18
  19 #include <vnet/fib/fib_types.h>
  20
  21 /**
  22  * The types of nodes in a FIB graph
  23  */
  24 typedef enum fib_node_type_t_ {
  25     /**
  26      * Marker. New types after this one.
  27      */
  28     FIB_NODE_TYPE_FIRST = 0,
  29     /**
  30      * See the respective fib_*.h files for descriptions of these objects.
  31      */
  32     FIB_NODE_TYPE_WALK,
  33     FIB_NODE_TYPE_ENTRY,
  34     FIB_NODE_TYPE_MFIB_ENTRY,
  35     FIB_NODE_TYPE_PATH_LIST,
  36     FIB_NODE_TYPE_PATH,
  37     FIB_NODE_TYPE_ADJ,
  38     FIB_NODE_TYPE_MPLS_ENTRY,
  39     FIB_NODE_TYPE_MPLS_TUNNEL,
  40     FIB_NODE_TYPE_LISP_GPE_FWD_ENTRY,
  41     FIB_NODE_TYPE_LISP_ADJ,
  42     FIB_NODE_TYPE_VXLAN_TUNNEL,
  43     FIB_NODE_TYPE_MAP_E,
  44     FIB_NODE_TYPE_VXLAN_GPE_TUNNEL,
  45     FIB_NODE_TYPE_GENEVE_TUNNEL,
  46     FIB_NODE_TYPE_UDP_ENCAP,
  47     FIB_NODE_TYPE_BIER_FMASK,
  48     FIB_NODE_TYPE_BIER_ENTRY,
  49     FIB_NODE_TYPE_VXLAN_GBP_TUNNEL,
  50     FIB_NODE_TYPE_IPSEC_SA,
  51     FIB_NODE_TYPE_IP_PUNT_REDIRECT,
  52     FIB_NODE_TYPE_ENTRY_TRACK,
  53     /**
  54      * Marker. New types before this one. leave the test last.
  55      */
  56     FIB_NODE_TYPE_LAST = FIB_NODE_TYPE_ENTRY_TRACK,
  57 } __attribute__ ((packed)) fib_node_type_t;
  58
  59 #define FIB_NODE_TYPE_MAX (FIB_NODE_TYPE_LAST + 1)
  60
  61 #define FIB_NODE_TYPES {                                        \
  62     [FIB_NODE_TYPE_ENTRY]     = "entry",                        \
  63     [FIB_NODE_TYPE_MFIB_ENTRY] = "mfib-entry",                  \
  64     [FIB_NODE_TYPE_WALK]      = "walk",                         \
  65     [FIB_NODE_TYPE_PATH_LIST] = "path-list",                    \
  66     [FIB_NODE_TYPE_PATH]      = "path",                         \
  67     [FIB_NODE_TYPE_MPLS_ENTRY] = "mpls-entry",                  \
  68     [FIB_NODE_TYPE_MPLS_TUNNEL] = "mpls-tunnel",                \
  69     [FIB_NODE_TYPE_ADJ] = "adj",                                \
  70     [FIB_NODE_TYPE_LISP_GPE_FWD_ENTRY] = "lisp-gpe-fwd-entry",  \
  71     [FIB_NODE_TYPE_LISP_ADJ] = "lisp-adj",                      \
  72     [FIB_NODE_TYPE_VXLAN_TUNNEL] = "vxlan-tunnel",              \
  73     [FIB_NODE_TYPE_MAP_E] = "map-e",                            \
  74     [FIB_NODE_TYPE_VXLAN_GPE_TUNNEL] = "vxlan-gpe-tunnel",      \
  75     [FIB_NODE_TYPE_UDP_ENCAP] = "udp-encap",                    \
  76     [FIB_NODE_TYPE_BIER_FMASK] = "bier-fmask",                  \
  77     [FIB_NODE_TYPE_BIER_ENTRY] = "bier-entry",                  \
  78     [FIB_NODE_TYPE_VXLAN_GBP_TUNNEL] = "vxlan-gbp-tunnel",      \
  79     [FIB_NODE_TYPE_IPSEC_SA] = "ipsec-sa",                      \
  80     [FIB_NODE_TYPE_IP_PUNT_REDIRECT] = "ip-punt-redirect",      \
  81     [FIB_NODE_TYPE_ENTRY_TRACK] = "fib-entry-track"             \
  82 }
  83
  84 /**
  85  * Reasons for backwalking the FIB object graph
  86  */
  87 typedef enum fib_node_back_walk_reason_t_ {
  88     /**
  89      * Marker. Add new ones after.
  90      */
  91     FIB_NODE_BW_REASON_FIRST = 0,
  92     /**
  93      * Walk to re-resolve the child.
  94      * Used when the parent is no longer a valid resolution target
  95      */
  96     FIB_NODE_BW_REASON_RESOLVE = FIB_NODE_BW_REASON_FIRST,
  97     /**
  98      * Walk to re-evaluate the forwarding contributed by the parent.
  99      * Used when a parent's forwarding changes and the child needs to
 100      * incorporate this change in its forwarding.
 101      */
 102     FIB_NODE_BW_REASON_EVALUATE,
 103     /**
 104      * A resolving interface has come up
 105      */
 106     FIB_NODE_BW_REASON_INTERFACE_UP,
 107     /**
 108      * A resolving interface has gone down
 109      */
 110     FIB_NODE_BW_REASON_INTERFACE_DOWN,
 111     /**
 112      * A resolving interface has been bound to another table
 113      */
 114     FIB_NODE_BW_REASON_INTERFACE_BIND,
 115     /**
 116      * A resolving interface has been deleted.
 117      */
 118     FIB_NODE_BW_REASON_INTERFACE_DELETE,
 119     /**
 120      * Walk to re-collapse the multipath adjs when the rewrite of
 121      * a unipath adjacency changes
 122      */
 123     FIB_NODE_BW_REASON_ADJ_UPDATE,
 124     /**
 125      * Walk update the adjacency MTU
 126      */
 127     FIB_NODE_BW_REASON_ADJ_MTU,
 128     /**
 129      * Walk to update children to inform them the adjacency is now down.
 130      */
 131     FIB_NODE_BW_REASON_ADJ_DOWN,
 132     /**
 133      * Marker. Add new before and update
 134      */
 135     FIB_NODE_BW_REASON_LAST = FIB_NODE_BW_REASON_ADJ_DOWN,
 136 } fib_node_back_walk_reason_t;
 137
 138 #define FIB_NODE_BW_REASONS {                               \
 139     [FIB_NODE_BW_REASON_RESOLVE] = "resolve",               \
 140     [FIB_NODE_BW_REASON_EVALUATE] = "evaluate",             \
 141     [FIB_NODE_BW_REASON_INTERFACE_UP] = "if-up",            \
 142     [FIB_NODE_BW_REASON_INTERFACE_DOWN] = "if-down",        \
 143     [FIB_NODE_BW_REASON_INTERFACE_DELETE] = "if-delete",    \
 144     [FIB_NODE_BW_REASON_INTERFACE_BIND] = "if-bind",        \
 145     [FIB_NODE_BW_REASON_ADJ_UPDATE] = "adj-update",         \
 146     [FIB_NODE_BW_REASON_ADJ_MTU] = "adj-mtu",               \
 147     [FIB_NODE_BW_REASON_ADJ_DOWN] = "adj-down",             \
 148 }
 149
 150 #define FOR_EACH_FIB_NODE_BW_REASON(_item) \
 151     for (_item = FIB_NODE_BW_REASON_FIRST; \
 152          _item <= FIB_NODE_BW_REASON_LAST; \
 153          _item++)
 154
 155 /**
 156  * Flags enum constructed from the reaons
 157  */
 158 typedef enum fib_node_bw_reason_flag_t_ {
 159     FIB_NODE_BW_REASON_FLAG_NONE = 0,
 160     FIB_NODE_BW_REASON_FLAG_RESOLVE = (1 << FIB_NODE_BW_REASON_RESOLVE),
 161     FIB_NODE_BW_REASON_FLAG_EVALUATE = (1 << FIB_NODE_BW_REASON_EVALUATE),
 162     FIB_NODE_BW_REASON_FLAG_INTERFACE_UP = (1 << FIB_NODE_BW_REASON_INTERFACE_UP),
 163     FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN = (1 << FIB_NODE_BW_REASON_INTERFACE_DOWN),
 164     FIB_NODE_BW_REASON_FLAG_INTERFACE_BIND = (1 << FIB_NODE_BW_REASON_INTERFACE_BIND),
 165     FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE = (1 << FIB_NODE_BW_REASON_INTERFACE_DELETE),
 166     FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE = (1 << FIB_NODE_BW_REASON_ADJ_UPDATE),
 167     FIB_NODE_BW_REASON_FLAG_ADJ_MTU = (1 << FIB_NODE_BW_REASON_ADJ_MTU),
 168     FIB_NODE_BW_REASON_FLAG_ADJ_DOWN = (1 << FIB_NODE_BW_REASON_ADJ_DOWN),
 169 } __attribute__ ((packed)) fib_node_bw_reason_flag_t;
 170
 171 STATIC_ASSERT(sizeof(fib_node_bw_reason_flag_t) < 3,
 172               "BW Reason enum < 2 byte. Consequences for fib_entry_src_cover_res_t");
 173
 174 extern u8 *format_fib_node_bw_reason(u8 *s, va_list *args);
 175
 176 /**
 177  * Flags on the walk
 178  */
 179 typedef enum fib_node_bw_flags_t_
 180 {
 181     FIB_NODE_BW_FLAG_NONE = 0,
 182     /**
 183      * Force the walk to be synchronous
 184      */
 185     FIB_NODE_BW_FLAG_FORCE_SYNC = (1 << 0),
 186 } fib_node_bw_flags_t;
 187
 188 /**
 189  * Forward declarations
 190  */
 191 struct fib_node_t_;
 192
 193 /**
 194  * A representation of one pointer to another node.
 195  * To fully qualify a node, one must know its type and its index so it
 196  * can be retrieved from the appropriate pool. Direct pointers to nodes
 197  * are forbidden, since all nodes are allocated from pools, which are vectors,
 198  * and thus subject to realloc at any time.
 199  */
 200 typedef struct fib_node_ptr_t_ {
 201     /**
 202      * node type
 203      */
 204     fib_node_type_t fnp_type;
 205     /**
 206      * node's index
 207      */
 208     fib_node_index_t fnp_index;
 209 } fib_node_ptr_t;
 210
 211 /**
 212  * @brief A list of FIB nodes.
 213  */
 214 typedef u32 fib_node_list_t;
 215
 216 /**
 217  * Context passed between object during a back walk.
 218  */
 219 typedef struct fib_node_back_walk_ctx_t_ {
 220     /**
 221      * The reason/trigger for the backwalk
 222      */
 223     fib_node_bw_reason_flag_t fnbw_reason;
 224
 225     /**
 226      * additional flags for the walk
 227      */
 228     fib_node_bw_flags_t fnbw_flags;
 229
 230     /**
 231      * the number of levels the walk has already traversed.
 232      * this value is maintained by the walk infra, tp limit the depth of
 233      * a walk so it does not run indefinately the presence of a loop/cycle
 234      * in the graph.
 235      */
 236     u32 fnbw_depth;
 237
 238     /**
 239      * Additional data associated with the reason the walk is occuring
 240      */
 241     union
 242     {
 243         struct {
 244             u32 fnbw_from_fib_index;
 245             u32 fnbw_to_fib_index;
 246         } interface_bind;
 247     };
 248 } fib_node_back_walk_ctx_t;
 249
 250 /**
 251  * We consider a depth of 32 to be sufficient to cover all sane
 252  * network topologies. Anything more is then an indication that
 253  * there is a loop/cycle in the FIB graph.
 254  * Note that all object types contribute to 1 to the depth.
 255  */
 256 #define FIB_NODE_GRAPH_MAX_DEPTH ((u32)32)
 257
 258 /**
 259  * A callback function for walking a node dependency list
 260  */
 261 typedef int (*fib_node_ptr_walk_t)(fib_node_ptr_t *depend,
 262                                    void *ctx);
 263
 264 /**
 265  * A list of dependent nodes.
 266  * This is currently implemented as a hash_table of fib_node_ptr_t
 267  */
 268 typedef fib_node_ptr_t fib_node_ptr_list_t;
 269
 270 /**
 271  * Return code from a back walk function
 272  */
 273 typedef enum fib_node_back_walk_rc_t_ {
 274     FIB_NODE_BACK_WALK_MERGE,
 275     FIB_NODE_BACK_WALK_CONTINUE,
 276 } fib_node_back_walk_rc_t;
 277
 278 /**
 279  * Function definition to backwalk a FIB node
 280  */
 281 typedef fib_node_back_walk_rc_t (*fib_node_back_walk_t)(
 282     struct fib_node_t_ *node,
 283     fib_node_back_walk_ctx_t *ctx);
 284
 285 /**
 286  * Function definition to get a FIB node from its index
 287  */
 288 typedef struct fib_node_t_* (*fib_node_get_t)(fib_node_index_t index);
 289
 290 /**
 291  * Function definition to inform the FIB node that its last lock has gone.
 292  */
 293 typedef void (*fib_node_last_lock_gone_t)(struct fib_node_t_ *node);
 294
 295 /**
 296  * Function definition to display the amount of memory used by a type.
 297  * Implementations should call fib_show_memory_usage()
 298  */
 299 typedef void (*fib_node_memory_show_t)(void);
 300
 301 /**
 302  * A FIB graph nodes virtual function table
 303  */
 304 typedef struct fib_node_vft_t_ {
 305     fib_node_get_t fnv_get;
 306     fib_node_last_lock_gone_t fnv_last_lock;
 307     fib_node_back_walk_t fnv_back_walk;
 308     fib_node_memory_show_t fnv_mem_show;
 309 } fib_node_vft_t;
 310
 311 /**
 312  * An node in the FIB graph
 313  *
 314  * Objects in the FIB form a graph.
 315  */
 316 typedef struct fib_node_t_ {
 317     /**
 318      * The node's type. make sure we are dynamic/down casting correctly
 319      */
 320     fib_node_type_t fn_type;
 321
 322     /**
 323      * Some pad space the concrete/derived type is free to use
 324      */
 325     u16 fn_pad;
 326
 327     /**
 328      * Vector of nodes that depend upon/use/share this node
 329      */
 330     fib_node_list_t fn_children;
 331
 332     /**
 333      * Number of dependents on this node. This number includes the number
 334      * of children
 335      */
 336     u32 fn_locks;
 337 } fib_node_t;
 338
 339 STATIC_ASSERT(sizeof(fib_node_t) == 12, "FIB node type is growing");
 340
 341 /**
 342  * @brief
 343  *  Register the function table for a given type
 344  *
 345  * @param ft
 346  *  FIB node type
 347  *
 348  * @param vft
 349  * virtual function table
 350  */
 351 extern void fib_node_register_type (fib_node_type_t ft,
 352                                     const fib_node_vft_t *vft);
 353
 354 /**
 355  * @brief
 356  *  Create a new FIB node type and Register the function table for it.
 357  *
 358  * @param name Name of the type (as display when printing children)
 359  * @param vft virtual function table
 360  *
 361  * @return new FIB node type
 362  */
 363 extern fib_node_type_t fib_node_register_new_type (const char *name,
 364                                                    const fib_node_vft_t *vft);
 365
 366 /**
 367  * @brief Show the memory usage for a type
 368  *
 369  * This should be invoked by the type in response to the infra calling
 370  * its registered memory show function
 371  *
 372  * @param name the name of the type
 373  * @param in_use_elts The number of elements in use
 374  * @param allocd_elts The number of allocated pool elemenets
 375  * @param size_elt The size of one element
 376  */
 377 extern void fib_show_memory_usage(const char *name,
 378                                   u32 in_use_elts,
 379                                   u32 allocd_elts,
 380                                   size_t size_elt);
 381
 382 extern void fib_node_init(fib_node_t *node,
 383                           fib_node_type_t ft);
 384 extern void fib_node_deinit(fib_node_t *node);
 385
 386 extern void fib_node_lock(fib_node_t *node);
 387 extern void fib_node_unlock(fib_node_t *node);
 388
 389 extern u32 fib_node_get_n_children(fib_node_type_t parent_type,
 390                                    fib_node_index_t parent_index);
 391 extern u32 fib_node_child_add(fib_node_type_t parent_type,
 392                               fib_node_index_t parent_index,
 393                               fib_node_type_t child_type,
 394                               fib_node_index_t child_index);
 395 extern void fib_node_child_remove(fib_node_type_t parent_type,
 396                                   fib_node_index_t parent_index,
 397                                   fib_node_index_t sibling_index);
 398
 399 extern fib_node_back_walk_rc_t fib_node_back_walk_one(fib_node_ptr_t *ptr,
 400                                                       fib_node_back_walk_ctx_t *ctx);
 401
 402 extern u8* fib_node_children_format(fib_node_list_t list,
 403                                     u8 *s);
 404
 405 extern const char* fib_node_type_get_name(fib_node_type_t type);
 406
 407 static inline int
 408 fib_node_index_is_valid (fib_node_index_t ni)
 409 {
 410     return (FIB_NODE_INDEX_INVALID != ni);
 411 }
 412
 413 #endif
 414