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