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