FD.io VPP  v18.07.1-19-g511ce25
Vector Packet Processing
fib_node.h File Reference
+ Include dependency graph for fib_node.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  fib_node_ptr_t_
 A representation of one pointer to another node. More...
 
struct  fib_node_back_walk_ctx_t_
 Context passed between object during a back walk. More...
 
struct  fib_node_vft_t_
 A FIB graph nodes virtual function table. More...
 
struct  fib_node_t_
 An node in the FIB graph. More...
 

Macros

#define FIB_NODE_TYPE_MAX   (FIB_NODE_TYPE_LAST + 1)
 
#define FIB_NODE_TYPES
 
#define FIB_NODE_BW_REASONS
 
#define FOR_EACH_FIB_NODE_BW_REASON(_item)
 
#define FIB_NODE_GRAPH_MAX_DEPTH   ((u32)32)
 We consider a depth of 32 to be sufficient to cover all sane network topologies. More...
 

Typedefs

typedef enum fib_node_type_t_ fib_node_type_t
 The types of nodes in a FIB graph. More...
 
typedef enum fib_node_back_walk_reason_t_ fib_node_back_walk_reason_t
 Reasons for backwalking the FIB object graph. More...
 
typedef enum fib_node_bw_reason_flag_t_ fib_node_bw_reason_flag_t
 Flags enum constructed from the reaons. More...
 
typedef enum fib_node_bw_flags_t_ fib_node_bw_flags_t
 Flags on the walk. More...
 
typedef struct fib_node_ptr_t_ fib_node_ptr_t
 A representation of one pointer to another node. More...
 
typedef u32 fib_node_list_t
 A list of FIB nodes. More...
 
typedef struct fib_node_back_walk_ctx_t_ fib_node_back_walk_ctx_t
 Context passed between object during a back walk. More...
 
typedef int(* fib_node_ptr_walk_t) (fib_node_ptr_t *depend, void *ctx)
 A callback function for walking a node dependency list. More...
 
typedef fib_node_ptr_t fib_node_ptr_list_t
 A list of dependent nodes. More...
 
typedef enum fib_node_back_walk_rc_t_ fib_node_back_walk_rc_t
 Return code from a back walk function. More...
 
typedef 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. More...
 
typedef struct fib_node_t_ *(* fib_node_get_t) (fib_node_index_t index)
 Function definition to get a FIB node from its index. More...
 
typedef 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. More...
 
typedef void(* fib_node_memory_show_t) (void)
 Function definition to display the amount of memory used by a type. More...
 
typedef struct fib_node_vft_t_ fib_node_vft_t
 A FIB graph nodes virtual function table. More...
 
typedef struct fib_node_t_ fib_node_t
 An node in the FIB graph. More...
 

Enumerations

enum  fib_node_type_t_ {
  FIB_NODE_TYPE_FIRST = 0, FIB_NODE_TYPE_WALK, FIB_NODE_TYPE_ENTRY, FIB_NODE_TYPE_MFIB_ENTRY,
  FIB_NODE_TYPE_PATH_LIST, FIB_NODE_TYPE_PATH, FIB_NODE_TYPE_ADJ, FIB_NODE_TYPE_MPLS_ENTRY,
  FIB_NODE_TYPE_MPLS_TUNNEL, FIB_NODE_TYPE_LISP_GPE_FWD_ENTRY, FIB_NODE_TYPE_LISP_ADJ, FIB_NODE_TYPE_GRE_TUNNEL,
  FIB_NODE_TYPE_VXLAN_TUNNEL, FIB_NODE_TYPE_MAP_E, FIB_NODE_TYPE_VXLAN_GPE_TUNNEL, FIB_NODE_TYPE_GENEVE_TUNNEL,
  FIB_NODE_TYPE_UDP_ENCAP, FIB_NODE_TYPE_BIER_FMASK, FIB_NODE_TYPE_BIER_ENTRY, FIB_NODE_TYPE_TEST,
  FIB_NODE_TYPE_LAST = FIB_NODE_TYPE_TEST
}
 The types of nodes in a FIB graph. More...
 
enum  fib_node_back_walk_reason_t_ {
  FIB_NODE_BW_REASON_FIRST = 0, FIB_NODE_BW_REASON_RESOLVE = FIB_NODE_BW_REASON_FIRST, FIB_NODE_BW_REASON_EVALUATE, FIB_NODE_BW_REASON_INTERFACE_UP,
  FIB_NODE_BW_REASON_INTERFACE_DOWN, FIB_NODE_BW_REASON_INTERFACE_DELETE, FIB_NODE_BW_REASON_ADJ_UPDATE, FIB_NODE_BW_REASON_ADJ_DOWN,
  FIB_NODE_BW_REASON_LAST = FIB_NODE_BW_REASON_ADJ_DOWN
}
 Reasons for backwalking the FIB object graph. More...
 
enum  fib_node_bw_reason_flag_t_ {
  FIB_NODE_BW_REASON_FLAG_NONE = 0, FIB_NODE_BW_REASON_FLAG_RESOLVE = (1 << FIB_NODE_BW_REASON_RESOLVE), FIB_NODE_BW_REASON_FLAG_EVALUATE = (1 << FIB_NODE_BW_REASON_EVALUATE), FIB_NODE_BW_REASON_FLAG_INTERFACE_UP = (1 << FIB_NODE_BW_REASON_INTERFACE_UP),
  FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN = (1 << FIB_NODE_BW_REASON_INTERFACE_DOWN), FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE = (1 << FIB_NODE_BW_REASON_INTERFACE_DELETE), FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE = (1 << FIB_NODE_BW_REASON_ADJ_UPDATE), FIB_NODE_BW_REASON_FLAG_ADJ_DOWN = (1 << FIB_NODE_BW_REASON_ADJ_DOWN)
}
 Flags enum constructed from the reaons. More...
 
enum  fib_node_bw_flags_t_ { FIB_NODE_BW_FLAG_NONE = 0, FIB_NODE_BW_FLAG_FORCE_SYNC = (1 << 0) }
 Flags on the walk. More...
 
enum  fib_node_back_walk_rc_t_ { FIB_NODE_BACK_WALK_MERGE, FIB_NODE_BACK_WALK_CONTINUE }
 Return code from a back walk function. More...
 

Functions

 STATIC_ASSERT (sizeof(fib_node_bw_reason_flag_t)< 2,"BW Reason enum < 2 byte. Consequences for cover_upd_res_t")
 
 STATIC_ASSERT (sizeof(fib_node_t)==12,"FIB node type is growing")
 
void fib_node_register_type (fib_node_type_t ft, const fib_node_vft_t *vft)
 Register the function table for a given type. More...
 
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. More...
 
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. More...
 
void fib_node_init (fib_node_t *node, fib_node_type_t ft)
 
void fib_node_deinit (fib_node_t *node)
 
void fib_node_lock (fib_node_t *node)
 
void fib_node_unlock (fib_node_t *node)
 
u32 fib_node_get_n_children (fib_node_type_t parent_type, fib_node_index_t parent_index)
 
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)
 
void fib_node_child_remove (fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_index_t sibling_index)
 
fib_node_back_walk_rc_t fib_node_back_walk_one (fib_node_ptr_t *ptr, fib_node_back_walk_ctx_t *ctx)
 
u8fib_node_children_format (fib_node_list_t list, u8 *s)
 
const char * fib_node_type_get_name (fib_node_type_t type)
 
static int fib_node_index_is_valid (fib_node_index_t ni)
 

Macro Definition Documentation

#define FIB_NODE_BW_REASONS
Value:
{ \
[FIB_NODE_BW_REASON_RESOLVE] = "resolve", \
[FIB_NODE_BW_REASON_EVALUATE] = "evaluate", \
[FIB_NODE_BW_REASON_ADJ_UPDATE] = "adj-update", \
[FIB_NODE_BW_REASON_ADJ_DOWN] = "adj-down", \
}
Walk to update children to inform them the adjacency is now down.
Definition: fib_node.h:118
Walk to re-collapse the multipath adjs when the rewrite of a unipath adjacency changes.
Definition: fib_node.h:114
Walk to re-resolve the child.
Definition: fib_node.h:91
A resolving interface has gone down.
Definition: fib_node.h:105
A resolving interface has been deleted.
Definition: fib_node.h:109
Walk to re-evaluate the forwarding contributed by the parent.
Definition: fib_node.h:97
A resolving interface has come up.
Definition: fib_node.h:101

Definition at line 125 of file fib_node.h.

#define FIB_NODE_GRAPH_MAX_DEPTH   ((u32)32)

We consider a depth of 32 to be sufficient to cover all sane network topologies.

Anything more is then an indication that there is a loop/cycle in the FIB graph. Note that all object types contribute to 1 to the depth.

Definition at line 226 of file fib_node.h.

#define FIB_NODE_TYPE_MAX   (FIB_NODE_TYPE_LAST + 1)

Definition at line 57 of file fib_node.h.

#define FIB_NODE_TYPES
Value:
{ \
[FIB_NODE_TYPE_ENTRY] = "entry", \
[FIB_NODE_TYPE_MFIB_ENTRY] = "mfib-entry", \
[FIB_NODE_TYPE_WALK] = "walk", \
[FIB_NODE_TYPE_PATH_LIST] = "path-list", \
[FIB_NODE_TYPE_PATH] = "path", \
[FIB_NODE_TYPE_MPLS_ENTRY] = "mpls-entry", \
[FIB_NODE_TYPE_MPLS_TUNNEL] = "mpls-tunnel", \
[FIB_NODE_TYPE_ADJ] = "adj", \
[FIB_NODE_TYPE_LISP_GPE_FWD_ENTRY] = "lisp-gpe-fwd-entry", \
[FIB_NODE_TYPE_LISP_ADJ] = "lisp-adj", \
[FIB_NODE_TYPE_GRE_TUNNEL] = "gre-tunnel", \
[FIB_NODE_TYPE_VXLAN_TUNNEL] = "vxlan-tunnel", \
[FIB_NODE_TYPE_MAP_E] = "map-e", \
[FIB_NODE_TYPE_VXLAN_GPE_TUNNEL] = "vxlan-gpe-tunnel", \
[FIB_NODE_TYPE_UDP_ENCAP] = "udp-encap", \
[FIB_NODE_TYPE_BIER_FMASK] = "bier-fmask", \
[FIB_NODE_TYPE_BIER_ENTRY] = "bier-entry", \
}
See the respective fib_*.h files for descriptions of these objects.
Definition: fib_node.h:32

Definition at line 59 of file fib_node.h.

#define FOR_EACH_FIB_NODE_BW_REASON (   _item)
Value:

Definition at line 135 of file fib_node.h.

Typedef Documentation

Context passed between object during a back walk.

Return code from a back walk function.

Reasons for backwalking the FIB object graph.

typedef 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 at line 251 of file fib_node.h.

Flags on the walk.

Flags enum constructed from the reaons.

typedef struct fib_node_t_*(* fib_node_get_t) (fib_node_index_t index)

Function definition to get a FIB node from its index.

Definition at line 258 of file fib_node.h.

typedef 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 at line 263 of file fib_node.h.

A list of FIB nodes.

Definition at line 195 of file fib_node.h.

typedef void(* fib_node_memory_show_t) (void)

Function definition to display the amount of memory used by a type.

Implementations should call fib_show_memory_usage()

Definition at line 269 of file fib_node.h.

A list of dependent nodes.

This is currently implemented as a hash_table of fib_node_ptr_t

Definition at line 238 of file fib_node.h.

A representation of one pointer to another node.

To fully qualify a node, one must know its type and its index so it can be retrieved from the appropriate pool. Direct pointers to nodes are forbidden, since all nodes are allocated from pools, which are vectors, and thus subject to realloc at any time.

typedef int(* fib_node_ptr_walk_t) (fib_node_ptr_t *depend, void *ctx)

A callback function for walking a node dependency list.

Definition at line 231 of file fib_node.h.

typedef struct fib_node_t_ fib_node_t

An node in the FIB graph.

Objects in the FIB form a graph.

The types of nodes in a FIB graph.

A FIB graph nodes virtual function table.

Enumeration Type Documentation

Return code from a back walk function.

Enumerator
FIB_NODE_BACK_WALK_MERGE 
FIB_NODE_BACK_WALK_CONTINUE 

Definition at line 243 of file fib_node.h.

Reasons for backwalking the FIB object graph.

Enumerator
FIB_NODE_BW_REASON_FIRST 

Marker.

Add new ones after.

FIB_NODE_BW_REASON_RESOLVE 

Walk to re-resolve the child.

Used when the parent is no longer a valid resolution target

FIB_NODE_BW_REASON_EVALUATE 

Walk to re-evaluate the forwarding contributed by the parent.

Used when a parent's forwarding changes and the child needs to incorporate this change in its forwarding.

FIB_NODE_BW_REASON_INTERFACE_UP 

A resolving interface has come up.

FIB_NODE_BW_REASON_INTERFACE_DOWN 

A resolving interface has gone down.

FIB_NODE_BW_REASON_INTERFACE_DELETE 

A resolving interface has been deleted.

FIB_NODE_BW_REASON_ADJ_UPDATE 

Walk to re-collapse the multipath adjs when the rewrite of a unipath adjacency changes.

FIB_NODE_BW_REASON_ADJ_DOWN 

Walk to update children to inform them the adjacency is now down.

FIB_NODE_BW_REASON_LAST 

Marker.

Add new before and update

Definition at line 82 of file fib_node.h.

Flags on the walk.

Enumerator
FIB_NODE_BW_FLAG_NONE 
FIB_NODE_BW_FLAG_FORCE_SYNC 

Force the walk to be synchronous.

Definition at line 160 of file fib_node.h.

Flags enum constructed from the reaons.

Enumerator
FIB_NODE_BW_REASON_FLAG_NONE 
FIB_NODE_BW_REASON_FLAG_RESOLVE 
FIB_NODE_BW_REASON_FLAG_EVALUATE 
FIB_NODE_BW_REASON_FLAG_INTERFACE_UP 
FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN 
FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE 
FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE 
FIB_NODE_BW_REASON_FLAG_ADJ_DOWN 

Definition at line 143 of file fib_node.h.

The types of nodes in a FIB graph.

Enumerator
FIB_NODE_TYPE_FIRST 

Marker.

New types after this one.

FIB_NODE_TYPE_WALK 

See the respective fib_*.h files for descriptions of these objects.

FIB_NODE_TYPE_ENTRY 
FIB_NODE_TYPE_MFIB_ENTRY 
FIB_NODE_TYPE_PATH_LIST 
FIB_NODE_TYPE_PATH 
FIB_NODE_TYPE_ADJ 
FIB_NODE_TYPE_MPLS_ENTRY 
FIB_NODE_TYPE_MPLS_TUNNEL 
FIB_NODE_TYPE_LISP_GPE_FWD_ENTRY 
FIB_NODE_TYPE_LISP_ADJ 
FIB_NODE_TYPE_GRE_TUNNEL 
FIB_NODE_TYPE_VXLAN_TUNNEL 
FIB_NODE_TYPE_MAP_E 
FIB_NODE_TYPE_VXLAN_GPE_TUNNEL 
FIB_NODE_TYPE_GENEVE_TUNNEL 
FIB_NODE_TYPE_UDP_ENCAP 
FIB_NODE_TYPE_BIER_FMASK 
FIB_NODE_TYPE_BIER_ENTRY 
FIB_NODE_TYPE_TEST 

Marker.

New types before this one. leave the test last.

FIB_NODE_TYPE_LAST 

Definition at line 24 of file fib_node.h.

Function Documentation

fib_node_back_walk_rc_t fib_node_back_walk_one ( fib_node_ptr_t ptr,
fib_node_back_walk_ctx_t ctx 
)

Definition at line 154 of file fib_node.c.

+ Here is the caller graph for this function:

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 at line 98 of file fib_node.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void fib_node_child_remove ( fib_node_type_t  parent_type,
fib_node_index_t  parent_index,
fib_node_index_t  sibling_index 
)

Definition at line 123 of file fib_node.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

u8* fib_node_children_format ( fib_node_list_t  list,
u8 s 
)

Definition at line 176 of file fib_node.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void fib_node_deinit ( fib_node_t node)

Definition at line 197 of file fib_node.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

u32 fib_node_get_n_children ( fib_node_type_t  parent_type,
fib_node_index_t  parent_index 
)

Definition at line 142 of file fib_node.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static int fib_node_index_is_valid ( fib_node_index_t  ni)
inlinestatic

Definition at line 378 of file fib_node.h.

void fib_node_init ( fib_node_t node,
fib_node_type_t  ft 
)

The node's type. used to retrieve the VFT.

Definition at line 185 of file fib_node.c.

+ Here is the caller graph for this function:

void fib_node_lock ( fib_node_t node)

Definition at line 203 of file fib_node.c.

+ Here is the caller graph for this function:

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.

Parameters
vftvirtual function table
Returns
new FIB node type

Definition at line 80 of file fib_node.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void fib_node_register_type ( fib_node_type_t  type,
const fib_node_vft_t vft 
)

Register the function table for a given type.

Parameters
ftFIB node type
vftvirtual function table

Register the function table for a given type.

Register the function table for a given type

Definition at line 60 of file fib_node.c.

+ Here is the caller graph for this function:

const char* fib_node_type_get_name ( fib_node_type_t  type)

Definition at line 37 of file fib_node.c.

+ Here is the caller graph for this function:

void fib_node_unlock ( fib_node_t node)

Definition at line 209 of file fib_node.c.

+ Here is the caller graph for this function:

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.

This should be invoked by the type in response to the infra calling its registered memory show function

Parameters
namethe name of the type
in_use_eltsThe number of elements in use
allocd_eltsThe number of allocated pool elemenets
size_eltThe size of one element

Definition at line 220 of file fib_node.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

STATIC_ASSERT ( )
STATIC_ASSERT ( sizeof(fib_node_t = =12,
"FIB node type is growing"   
)