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