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_MFIB_ENTRY,
35 FIB_NODE_TYPE_PATH_LIST,
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,
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,
54 * Marker. New types before this one. leave the test last.
56 FIB_NODE_TYPE_LAST = FIB_NODE_TYPE_ENTRY_TRACK,
57 } __attribute__ ((packed)) fib_node_type_t;
59 #define FIB_NODE_TYPE_MAX (FIB_NODE_TYPE_LAST + 1)
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" \
85 * Reasons for backwalking the FIB object graph
87 typedef enum fib_node_back_walk_reason_t_ {
89 * Marker. Add new ones after.
91 FIB_NODE_BW_REASON_FIRST = 0,
93 * Walk to re-resolve the child.
94 * Used when the parent is no longer a valid resolution target
96 FIB_NODE_BW_REASON_RESOLVE = FIB_NODE_BW_REASON_FIRST,
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.
102 FIB_NODE_BW_REASON_EVALUATE,
104 * A resolving interface has come up
106 FIB_NODE_BW_REASON_INTERFACE_UP,
108 * A resolving interface has gone down
110 FIB_NODE_BW_REASON_INTERFACE_DOWN,
112 * A resolving interface has been bound to another table
114 FIB_NODE_BW_REASON_INTERFACE_BIND,
116 * A resolving interface has been deleted.
118 FIB_NODE_BW_REASON_INTERFACE_DELETE,
120 * Walk to re-collapse the multipath adjs when the rewrite of
121 * a unipath adjacency changes
123 FIB_NODE_BW_REASON_ADJ_UPDATE,
125 * Walk update the adjacency MTU
127 FIB_NODE_BW_REASON_ADJ_MTU,
129 * Walk to update children to inform them the adjacency is now down.
131 FIB_NODE_BW_REASON_ADJ_DOWN,
133 * Marker. Add new before and update
135 FIB_NODE_BW_REASON_LAST = FIB_NODE_BW_REASON_ADJ_DOWN,
136 } fib_node_back_walk_reason_t;
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", \
150 #define FOR_EACH_FIB_NODE_BW_REASON(_item) \
151 for (_item = FIB_NODE_BW_REASON_FIRST; \
152 _item <= FIB_NODE_BW_REASON_LAST; \
156 * Flags enum constructed from the reaons
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;
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");
174 extern u8 *format_fib_node_bw_reason(u8 *s, va_list *args);
179 typedef enum fib_node_bw_flags_t_
181 FIB_NODE_BW_FLAG_NONE = 0,
183 * Force the walk to be synchronous
185 FIB_NODE_BW_FLAG_FORCE_SYNC = (1 << 0),
186 } fib_node_bw_flags_t;
189 * Forward declarations
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.
200 typedef struct fib_node_ptr_t_ {
204 fib_node_type_t fnp_type;
208 fib_node_index_t fnp_index;
212 * @brief A list of FIB nodes.
214 typedef u32 fib_node_list_t;
217 * Context passed between object during a back walk.
219 typedef struct fib_node_back_walk_ctx_t_ {
221 * The reason/trigger for the backwalk
223 fib_node_bw_reason_flag_t fnbw_reason;
226 * additional flags for the walk
228 fib_node_bw_flags_t fnbw_flags;
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
239 * Additional data associated with the reason the walk is occuring
244 u32 fnbw_from_fib_index;
245 u32 fnbw_to_fib_index;
248 } fib_node_back_walk_ctx_t;
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.
256 #define FIB_NODE_GRAPH_MAX_DEPTH ((u32)32)
259 * A callback function for walking a node dependency list
261 typedef int (*fib_node_ptr_walk_t)(fib_node_ptr_t *depend,
265 * A list of dependent nodes.
266 * This is currently implemented as a hash_table of fib_node_ptr_t
268 typedef fib_node_ptr_t fib_node_ptr_list_t;
271 * Return code from a back walk function
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;
279 * Function definition to backwalk a FIB node
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);
286 * Function definition to get a FIB node from its index
288 typedef struct fib_node_t_* (*fib_node_get_t)(fib_node_index_t index);
291 * Function definition to inform the FIB node that its last lock has gone.
293 typedef void (*fib_node_last_lock_gone_t)(struct fib_node_t_ *node);
296 * Function definition to display the amount of memory used by a type.
297 * Implementations should call fib_show_memory_usage()
299 typedef void (*fib_node_memory_show_t)(void);
302 * A FIB graph nodes virtual function table
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;
312 * An node in the FIB graph
314 * Objects in the FIB form a graph.
316 typedef struct fib_node_t_ {
318 * The node's type. make sure we are dynamic/down casting correctly
320 fib_node_type_t fn_type;
323 * Some pad space the concrete/derived type is free to use
328 * Vector of nodes that depend upon/use/share this node
330 fib_node_list_t fn_children;
333 * Number of dependents on this node. This number includes the number
339 STATIC_ASSERT(sizeof(fib_node_t) == 12, "FIB node type is growing");
343 * Register the function table for a given type
349 * virtual function table
351 extern void fib_node_register_type (fib_node_type_t ft,
352 const fib_node_vft_t *vft);
356 * Create a new FIB node type and Register the function table for it.
358 * @param name Name of the type (as display when printing children)
359 * @param vft virtual function table
361 * @return new FIB node type
363 extern fib_node_type_t fib_node_register_new_type (const char *name,
364 const fib_node_vft_t *vft);
367 * @brief Show the memory usage for a type
369 * This should be invoked by the type in response to the infra calling
370 * its registered memory show function
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
377 extern void fib_show_memory_usage(const char *name,
382 extern void fib_node_init(fib_node_t *node,
384 extern void fib_node_deinit(fib_node_t *node);
386 extern void fib_node_lock(fib_node_t *node);
387 extern void fib_node_unlock(fib_node_t *node);
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);
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);
402 extern u8* fib_node_children_format(fib_node_list_t list,
405 extern const char* fib_node_type_get_name(fib_node_type_t type);
408 fib_node_index_is_valid (fib_node_index_t ni)
410 return (FIB_NODE_INDEX_INVALID != ni);