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_GRE_TUNNEL,
  43     FIB_NODE_TYPE_VXLAN_TUNNEL,
  44     FIB_NODE_TYPE_MAP_E,
  45     FIB_NODE_TYPE_VXLAN_GPE_TUNNEL,
  46     FIB_NODE_TYPE_GENEVE_TUNNEL,
  47     FIB_NODE_TYPE_UDP_ENCAP,
  48     FIB_NODE_TYPE_BIER_FMASK,
  49     FIB_NODE_TYPE_BIER_ENTRY,
  50     /**
  51      * Marker. New types before this one. leave the test last.
  52      */
  53     FIB_NODE_TYPE_TEST,
  54     FIB_NODE_TYPE_LAST = FIB_NODE_TYPE_TEST,
  55 } fib_node_type_t;
  56
  57 #define FIB_NODE_TYPE_MAX (FIB_NODE_TYPE_LAST + 1)
  58
  59 #define FIB_NODE_TYPES {                          \
  60     [FIB_NODE_TYPE_ENTRY]     = "entry",          \
  61     [FIB_NODE_TYPE_MFIB_ENTRY] = "mfib-entry",    \
  62     [FIB_NODE_TYPE_WALK]      = "walk",           \
  63     [FIB_NODE_TYPE_PATH_LIST] = "path-list",      \
  64     [FIB_NODE_TYPE_PATH]      = "path",           \
  65     [FIB_NODE_TYPE_MPLS_ENTRY] = "mpls-entry",    \
  66     [FIB_NODE_TYPE_MPLS_TUNNEL] = "mpls-tunnel",  \
  67     [FIB_NODE_TYPE_ADJ] = "adj",                  \
  68     [FIB_NODE_TYPE_LISP_GPE_FWD_ENTRY] = "lisp-gpe-fwd-entry", \
  69     [FIB_NODE_TYPE_LISP_ADJ] = "lisp-adj", \
  70     [FIB_NODE_TYPE_GRE_TUNNEL] = "gre-tunnel", \
  71     [FIB_NODE_TYPE_VXLAN_TUNNEL] = "vxlan-tunnel", \
  72     [FIB_NODE_TYPE_MAP_E] = "map-e", \
  73     [FIB_NODE_TYPE_VXLAN_GPE_TUNNEL] = "vxlan-gpe-tunnel", \
  74     [FIB_NODE_TYPE_UDP_ENCAP] = "udp-encap", \
  75     [FIB_NODE_TYPE_BIER_FMASK] = "bier-fmask",  \
  76     [FIB_NODE_TYPE_BIER_ENTRY] = "bier-entry",  \
  77 }
  78
  79 /**
  80  * Reasons for backwalking the FIB object graph
  81  */
  82 typedef enum fib_node_back_walk_reason_t_ {
  83     /**
  84      * Marker. Add new ones after.
  85      */
  86     FIB_NODE_BW_REASON_FIRST = 0,
  87     /**
  88      * Walk to re-resolve the child.
  89      * Used when the parent is no longer a valid resolution target
  90      */
  91     FIB_NODE_BW_REASON_RESOLVE = FIB_NODE_BW_REASON_FIRST,
  92     /**
  93      * Walk to re-evaluate the forwarding contributed by the parent.
  94      * Used when a parent's forwarding changes and the child needs to
  95      * incorporate this change in its forwarding.
  96      */
  97     FIB_NODE_BW_REASON_EVALUATE,
  98     /**
  99      * A resolving interface has come up
 100      */
 101     FIB_NODE_BW_REASON_INTERFACE_UP,
 102     /**
 103      * A resolving interface has gone down
 104      */
 105     FIB_NODE_BW_REASON_INTERFACE_DOWN,
 106     /**
 107      * A resolving interface has been deleted.
 108      */
 109     FIB_NODE_BW_REASON_INTERFACE_DELETE,
 110     /**
 111      * Walk to re-collapse the multipath adjs when the rewrite of
 112      * a unipath adjacency changes
 113      */
 114     FIB_NODE_BW_REASON_ADJ_UPDATE,
 115     /**
 116      * Walk to update children to inform them the adjacency is now down.
 117      */
 118     FIB_NODE_BW_REASON_ADJ_DOWN,
 119     /**
 120      * Marker. Add new before and update
 121      */
 122     FIB_NODE_BW_REASON_LAST = FIB_NODE_BW_REASON_ADJ_DOWN,
 123 } fib_node_back_walk_reason_t;
 124
 125 #define FIB_NODE_BW_REASONS {                               \
 126     [FIB_NODE_BW_REASON_RESOLVE] = "resolve",               \
 127     [FIB_NODE_BW_REASON_EVALUATE] = "evaluate",             \
 128     [FIB_NODE_BW_REASON_INTERFACE_UP] = "if-up",            \
 129     [FIB_NODE_BW_REASON_INTERFACE_DOWN] = "if-down",        \
 130     [FIB_NODE_BW_REASON_INTERFACE_DELETE] = "if-delete",    \
 131     [FIB_NODE_BW_REASON_ADJ_UPDATE] = "adj-update",         \
 132     [FIB_NODE_BW_REASON_ADJ_DOWN] = "adj-down",             \
 133 }
 134
 135 #define FOR_EACH_FIB_NODE_BW_REASON(_item) \
 136     for (_item = FIB_NODE_BW_REASON_FIRST; \
 137          _item <= FIB_NODE_BW_REASON_LAST; \
 138          _item++)
 139
 140 /**
 141  * Flags enum constructed from the reaons
 142  */
 143 typedef enum fib_node_bw_reason_flag_t_ {
 144     FIB_NODE_BW_REASON_FLAG_NONE = 0,
 145     FIB_NODE_BW_REASON_FLAG_RESOLVE = (1 << FIB_NODE_BW_REASON_RESOLVE),
 146     FIB_NODE_BW_REASON_FLAG_EVALUATE = (1 << FIB_NODE_BW_REASON_EVALUATE),
 147     FIB_NODE_BW_REASON_FLAG_INTERFACE_UP = (1 << FIB_NODE_BW_REASON_INTERFACE_UP),
 148     FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN = (1 << FIB_NODE_BW_REASON_INTERFACE_DOWN),
 149     FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE = (1 << FIB_NODE_BW_REASON_INTERFACE_DELETE),
 150     FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE = (1 << FIB_NODE_BW_REASON_ADJ_UPDATE),
 151     FIB_NODE_BW_REASON_FLAG_ADJ_DOWN = (1 << FIB_NODE_BW_REASON_ADJ_DOWN),
 152 } __attribute__ ((packed)) fib_node_bw_reason_flag_t;
 153
 154 STATIC_ASSERT(sizeof(fib_node_bw_reason_flag_t) < 2,
 155               "BW Reason enum < 2 byte. Consequences for cover_upd_res_t");
 156
 157 /**
 158  * Flags on the walk
 159  */
 160 typedef enum fib_node_bw_flags_t_
 161 {
 162     /**
 163      * Force the walk to be synchronous
 164      */
 165     FIB_NODE_BW_FLAG_FORCE_SYNC = (1 << 0),
 166 } fib_node_bw_flags_t;
 167
 168 /**
 169  * Forward eclarations
 170  */
 171 struct fib_node_t_;
 172
 173 /**
 174  * A representation of one pointer to another node.
 175  * To fully qualify a node, one must know its type and its index so it
 176  * can be retrieved from the appropriate pool. Direct pointers to nodes
 177  * are forbidden, since all nodes are allocated from pools, which are vectors,
 178  * and thus subject to realloc at any time.
 179  */
 180 typedef struct fib_node_ptr_t_ {
 181     /**
 182      * node type
 183      */
 184     fib_node_type_t fnp_type;
 185     /**
 186      * node's index
 187      */
 188     fib_node_index_t fnp_index;
 189 } fib_node_ptr_t;
 190
 191 /**
 192  * @brief A list of FIB nodes.
 193  */
 194 typedef u32 fib_node_list_t;
 195
 196 /**
 197  * Context passed between object during a back walk.
 198  */
 199 typedef struct fib_node_back_walk_ctx_t_ {
 200     /**
 201      * The reason/trigger for the backwalk
 202      */
 203     fib_node_bw_reason_flag_t fnbw_reason;
 204
 205     /**
 206      * additional flags for the walk
 207      */
 208     fib_node_bw_flags_t fnbw_flags;
 209
 210     /**
 211      * the number of levels the walk has already traversed.
 212      * this value is maintained by the walk infra, tp limit the depth of
 213      * a walk so it does not run indefinately the presence of a loop/cycle
 214      * in the graph.
 215      */
 216     u32 fnbw_depth;
 217 } fib_node_back_walk_ctx_t;
 218
 219 /**
 220  * We consider a depth of 32 to be sufficient to cover all sane
 221  * network topologies. Anything more is then an indication that
 222  * there is a loop/cycle in the FIB graph.
 223  * Note that all object types contribute to 1 to the depth.
 224  */
 225 #define FIB_NODE_GRAPH_MAX_DEPTH ((u32)32)
 226
 227 /**
 228  * A callback function for walking a node dependency list
 229  */
 230 typedef int (*fib_node_ptr_walk_t)(fib_node_ptr_t *depend,
 231                                    void *ctx);
 232
 233 /**
 234  * A list of dependent nodes.
 235  * This is currently implemented as a hash_table of fib_node_ptr_t
 236  */
 237 typedef fib_node_ptr_t fib_node_ptr_list_t;
 238
 239 /**
 240  * Return code from a back walk function
 241  */
 242 typedef enum fib_node_back_walk_rc_t_ {
 243     FIB_NODE_BACK_WALK_MERGE,
 244     FIB_NODE_BACK_WALK_CONTINUE,
 245 } fib_node_back_walk_rc_t;
 246
 247 /**
 248  * Function definition to backwalk a FIB node
 249  */
 250 typedef fib_node_back_walk_rc_t (*fib_node_back_walk_t)(
 251     struct fib_node_t_ *node,
 252     fib_node_back_walk_ctx_t *ctx);
 253
 254 /**
 255  * Function definition to get a FIB node from its index
 256  */
 257 typedef struct fib_node_t_* (*fib_node_get_t)(fib_node_index_t index);
 258
 259 /**
 260  * Function definition to inform the FIB node that its last lock has gone.
 261  */
 262 typedef void (*fib_node_last_lock_gone_t)(struct fib_node_t_ *node);
 263
 264 /**
 265  * Function definition to display the amount of memory used by a type.
 266  * Implementations should call fib_show_memory_usage()
 267  */
 268 typedef void (*fib_node_memory_show_t)(void);
 269
 270 /**
 271  * A FIB graph nodes virtual function table
 272  */
 273 typedef struct fib_node_vft_t_ {
 274     fib_node_get_t fnv_get;
 275     fib_node_last_lock_gone_t fnv_last_lock;
 276     fib_node_back_walk_t fnv_back_walk;
 277     format_function_t *fnv_format;
 278     fib_node_memory_show_t fnv_mem_show;
 279 } fib_node_vft_t;
 280
 281 /**
 282  * An node in the FIB graph
 283  *
 284  * Objects in the FIB form a graph.
 285  */
 286 typedef struct fib_node_t_ {
 287 #if CLIB_DEBUG > 0
 288     /**
 289      * The node's type. make sure we are dynamic/down casting correctly
 290      */
 291     fib_node_type_t fn_type;
 292 #endif
 293     /**
 294      * The node's VFT.
 295      * we could store the type here instead, and lookup the VFT using that. But
 296      * I like this better,
 297      */
 298     const fib_node_vft_t *fn_vft;
 299
 300     /**
 301      * Vector of nodes that depend upon/use/share this node
 302      */
 303     fib_node_list_t fn_children;
 304
 305     /**
 306      * Number of dependents on this node. This number includes the number
 307      * of children
 308      */
 309     u32 fn_locks;
 310 } fib_node_t;
 311
 312 /**
 313  * @brief
 314  *  Register the function table for a given type
 315  *
 316  * @param ft
 317  *  FIB node type
 318  *
 319  * @param vft
 320  * virtual function table
 321  */
 322 extern void fib_node_register_type (fib_node_type_t ft,
 323                                     const fib_node_vft_t *vft);
 324
 325 /**
 326  * @brief
 327  *  Create a new FIB node type and Register the function table for it.
 328  *
 329  * @param vft
 330  * virtual function table
 331  *
 332  * @return new FIB node type
 333  */
 334 extern fib_node_type_t fib_node_register_new_type (const fib_node_vft_t *vft);
 335
 336 /**
 337  * @brief Show the memory usage for a type
 338  *
 339  * This should be invoked by the type in response to the infra calling
 340  * its registered memory show function
 341  *
 342  * @param name the name of the type
 343  * @param in_use_elts The number of elements in use
 344  * @param allocd_elts The number of allocated pool elemenets
 345  * @param size_elt The size of one element
 346  */
 347 extern void fib_show_memory_usage(const char *name,
 348                                   u32 in_use_elts,
 349                                   u32 allocd_elts,
 350                                   size_t size_elt);
 351
 352 extern void fib_node_init(fib_node_t *node,
 353                           fib_node_type_t ft);
 354 extern void fib_node_deinit(fib_node_t *node);
 355
 356 extern void fib_node_lock(fib_node_t *node);
 357 extern void fib_node_unlock(fib_node_t *node);
 358
 359 extern u32 fib_node_get_n_children(fib_node_type_t parent_type,
 360                                    fib_node_index_t parent_index);
 361 extern u32 fib_node_child_add(fib_node_type_t parent_type,
 362                               fib_node_index_t parent_index,
 363                               fib_node_type_t child_type,
 364                               fib_node_index_t child_index);
 365 extern void fib_node_child_remove(fib_node_type_t parent_type,
 366                                   fib_node_index_t parent_index,
 367                                   fib_node_index_t sibling_index);
 368
 369 extern fib_node_back_walk_rc_t fib_node_back_walk_one(fib_node_ptr_t *ptr,
 370                                                       fib_node_back_walk_ctx_t *ctx);
 371
 372 extern u8* fib_node_children_format(fib_node_list_t list,
 373                                     u8 *s);
 374
 375 extern const char* fib_node_type_get_name(fib_node_type_t type);
 376
 377 static inline int
 378 fib_node_index_is_valid (fib_node_index_t ni)
 379 {
 380     return (FIB_NODE_INDEX_INVALID != ni);
 381 }
 382
 383 #endif
 384