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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #ifndef __FIB_NODE_H__
17 #define __FIB_NODE_H__
19 #include <vnet/fib/fib_types.h>
22 * The types of nodes in a FIB graph
24 typedef enum fib_node_type_t_ {
26 * Marker. New types after this one.
28 FIB_NODE_TYPE_FIRST = 0,
30 * See the respective fib_*.h files for descriptions of these objects.
34 FIB_NODE_TYPE_PATH_LIST,
37 FIB_NODE_TYPE_MPLS_ENTRY,
38 FIB_NODE_TYPE_LISP_GPE_TUNNEL,
39 FIB_NODE_TYPE_LISP_ADJ,
40 FIB_NODE_TYPE_MPLS_GRE_TUNNEL,
41 FIB_NODE_TYPE_GRE_TUNNEL,
43 * Marker. New types before this one. leave the test last.
46 FIB_NODE_TYPE_LAST = FIB_NODE_TYPE_TEST,
49 #define FIB_NODE_TYPE_MAX (FIB_NODE_TYPE_LAST + 1)
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_TUNNEL] = "lisp-gpe-tunnel", \
59 [FIB_NODE_TYPE_LISP_ADJ] = "lisp-adj", \
60 [FIB_NODE_TYPE_MPLS_GRE_TUNNEL] = "mpls-gre-tunnel", \
61 [FIB_NODE_TYPE_GRE_TUNNEL] = "gre-tunnel", \
65 * Reasons for backwalking the FIB object graph
67 typedef enum fib_node_back_walk_reason_t_ {
69 * Marker. Add new ones after.
71 FIB_NODE_BW_REASON_FIRST = 0,
73 * Walk to re-resolve the child.
74 * Used when the parent is no longer a valid resolution target
76 FIB_NODE_BW_REASON_RESOLVE = FIB_NODE_BW_REASON_FIRST,
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.
82 FIB_NODE_BW_REASON_EVALUATE,
84 * A resolving interface has come up
86 FIB_NODE_BW_REASON_INTERFACE_UP,
88 * A resolving interface has gone down
90 FIB_NODE_BW_REASON_INTERFACE_DOWN,
92 * A resolving interface has been deleted.
94 FIB_NODE_BW_REASON_INTERFACE_DELETE,
96 * Walk to re-collapse the multipath adjs when the rewrite of
97 * a unipath adjacency changes
99 FIB_NODE_BW_REASON_ADJ_UPDATE,
101 * Marker. Add new before and update
103 FIB_NODE_BW_REASON_LAST = FIB_NODE_BW_REASON_EVALUATE,
104 } fib_node_back_walk_reason_t;
106 #define FIB_NODE_BW_REASONS { \
107 [FIB_NODE_BW_REASON_RESOLVE] = "resolve" \
108 [FIB_NODE_BW_REASON_EVALUATE] = "evaluate" \
109 [FIB_NODE_BW_REASON_INTERFACE_UP] = "if-up" \
110 [FIB_NODE_BW_REASON_INTERFACE_DOWN] = "if-down" \
111 [FIB_NODE_BW_REASON_INTERFACE_DELETE] = "if-delete" \
112 [FIB_NODE_BW_REASON_ADJ_UPDATE] = "adj-update" \
116 * Flags enum constructed from the reaons
118 typedef enum fib_node_bw_reason_flag_t_ {
119 FIB_NODE_BW_REASON_FLAG_NONE = 0,
120 FIB_NODE_BW_REASON_FLAG_RESOLVE = (1 << FIB_NODE_BW_REASON_RESOLVE),
121 FIB_NODE_BW_REASON_FLAG_EVALUATE = (1 << FIB_NODE_BW_REASON_EVALUATE),
122 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP = (1 << FIB_NODE_BW_REASON_INTERFACE_UP),
123 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN = (1 << FIB_NODE_BW_REASON_INTERFACE_DOWN),
124 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE = (1 << FIB_NODE_BW_REASON_INTERFACE_DELETE),
125 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE = (1 << FIB_NODE_BW_REASON_ADJ_UPDATE),
126 } __attribute__ ((packed)) fib_node_bw_reason_flag_t;
128 _Static_assert(sizeof(fib_node_bw_reason_flag_t) < 2,
129 "BW Reason enum < 2 byte. Consequences for cover_upd_res_t");
132 * Forward eclarations
137 * A representation of one pointer to another node.
138 * To fully qualify a node, one must know its type and its index so it
139 * can be retrieved from the appropriate pool. Direct pointers to nodes
140 * are forbidden, since all nodes are allocated from pools, which are vectors,
141 * and thus subject to realloc at any time.
143 typedef struct fib_node_ptr_t_ {
147 fib_node_type_t fnp_type;
151 fib_node_index_t fnp_index;
155 * @brief A list of FIB nodes.
157 typedef u32 fib_node_list_t;
160 * Context passed between object during a back walk.
162 typedef struct fib_node_back_walk_ctx_t_ {
164 * The reason/trigger for the backwalk
166 fib_node_bw_reason_flag_t fnbw_reason;
169 * the number of levels the walk has already traversed.
170 * this value is maintained by the walk infra, tp limit the depth of
171 * a walk so it does not run indefinately the presence of a loop/cycle
175 } fib_node_back_walk_ctx_t;
178 * We consider a depth of 32 to be sufficient to cover all sane
179 * network topologies. Anything more is then an indication that
180 * there is a loop/cycle in the FIB graph.
181 * Note that all object types contribute to 1 to the depth.
183 #define FIB_NODE_GRAPH_MAX_DEPTH ((u32)32)
186 * A callback function for walking a node dependency list
188 typedef int (*fib_node_ptr_walk_t)(fib_node_ptr_t *depend,
192 * A list of dependent nodes.
193 * This is currently implemented as a hash_table of fib_node_ptr_t
195 typedef fib_node_ptr_t fib_node_ptr_list_t;
198 * Return code from a back walk function
200 typedef enum fib_node_back_walk_rc_t_ {
201 FIB_NODE_BACK_WALK_MERGE,
202 FIB_NODE_BACK_WALK_CONTINUE,
203 } fib_node_back_walk_rc_t;
206 * Function definition to backwalk a FIB node
208 typedef fib_node_back_walk_rc_t (*fib_node_back_walk_t)(
209 struct fib_node_t_ *node,
210 fib_node_back_walk_ctx_t *ctx);
213 * Function definition to get a FIB node from its index
215 typedef struct fib_node_t_* (*fib_node_get_t)(fib_node_index_t index);
218 * Function definition to inform the FIB node that its last lock has gone.
220 typedef void (*fib_node_last_lock_gone_t)(struct fib_node_t_ *node);
223 * A FIB graph nodes virtual function table
225 typedef struct fib_node_vft_t_ {
226 fib_node_get_t fnv_get;
227 fib_node_last_lock_gone_t fnv_last_lock;
228 fib_node_back_walk_t fnv_back_walk;
229 format_function_t *fnv_format;
233 * An node in the FIB graph
235 * Objects in the FIB form a graph.
237 typedef struct fib_node_t_ {
240 * The node's type. make sure we are dynamic/down casting correctly
242 fib_node_type_t fn_type;
246 * we could store the type here instead, and lookup the VFT using that. But
247 * I like this better,
249 const fib_node_vft_t *fn_vft;
252 * Vector of nodes that depend upon/use/share this node
254 fib_node_list_t fn_children;
257 * Number of dependents on this node. This number includes the number
265 * Register the function table for a given type
271 * virtual function table
273 extern void fib_node_register_type (fib_node_type_t ft,
274 const fib_node_vft_t *vft);
278 * Create a new FIB node type and Register the function table for it.
281 * virtual function table
283 * @return new FIB node type
285 extern fib_node_type_t fib_node_register_new_type (const fib_node_vft_t *vft);
287 extern void fib_node_init(fib_node_t *node,
289 extern void fib_node_deinit(fib_node_t *node);
291 extern void fib_node_lock(fib_node_t *node);
292 extern void fib_node_unlock(fib_node_t *node);
294 extern u32 fib_node_child_add(fib_node_type_t parent_type,
295 fib_node_index_t parent_index,
296 fib_node_type_t child_type,
297 fib_node_index_t child_index);
298 extern void fib_node_child_remove(fib_node_type_t parent_type,
299 fib_node_index_t parent_index,
300 fib_node_index_t sibling_index);
302 extern fib_node_back_walk_rc_t fib_node_back_walk_one(fib_node_ptr_t *ptr,
303 fib_node_back_walk_ctx_t *ctx);
305 extern u8* fib_node_children_format(fib_node_list_t list,
308 extern const char* fib_node_type_get_name(fib_node_type_t type);
311 fib_node_index_is_valid (fib_node_index_t ni)
313 return (FIB_NODE_INDEX_INVALID != ni);