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