FD.io VPP  v20.09-64-g4f7b92f0a
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_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_VXLAN_GBP_TUNNEL, FIB_NODE_TYPE_IPSEC_SA,
  FIB_NODE_TYPE_IP_PUNT_REDIRECT, FIB_NODE_TYPE_ENTRY_TRACK, 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")
 
u8format_fib_node_bw_reason (u8 *s, va_list *args)
 
 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

◆ FIB_NODE_BW_REASONS

#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:124
Walk to re-collapse the multipath adjs when the rewrite of a unipath adjacency changes.
Definition: fib_node.h:120
Walk to re-resolve the child.
Definition: fib_node.h:97
A resolving interface has gone down.
Definition: fib_node.h:111
A resolving interface has been deleted.
Definition: fib_node.h:115
Walk to re-evaluate the forwarding contributed by the parent.
Definition: fib_node.h:103
A resolving interface has come up.
Definition: fib_node.h:107

Definition at line 131 of file fib_node.h.

◆ FIB_NODE_GRAPH_MAX_DEPTH

#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 234 of file fib_node.h.

◆ FIB_NODE_TYPE_MAX

#define FIB_NODE_TYPE_MAX   (FIB_NODE_TYPE_LAST + 1)

Definition at line 60 of file fib_node.h.

◆ FIB_NODE_TYPES

#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_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", \
[FIB_NODE_TYPE_VXLAN_GBP_TUNNEL] = "vxlan-gbp-tunnel", \
[FIB_NODE_TYPE_IPSEC_SA] = "ipsec-sa", \
[FIB_NODE_TYPE_IP_PUNT_REDIRECT] = "ip-punt-redirect", \
[FIB_NODE_TYPE_ENTRY_TRACK] = "fib-entry-track" \
}
See the respective fib_*.h files for descriptions of these objects.
Definition: fib_node.h:32

Definition at line 62 of file fib_node.h.

◆ FOR_EACH_FIB_NODE_BW_REASON

#define FOR_EACH_FIB_NODE_BW_REASON (   _item)
Value:

Definition at line 141 of file fib_node.h.

Typedef Documentation

◆ fib_node_back_walk_ctx_t

Context passed between object during a back walk.

◆ fib_node_back_walk_rc_t

Return code from a back walk function.

◆ fib_node_back_walk_reason_t

Reasons for backwalking the FIB object graph.

◆ fib_node_back_walk_t

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 259 of file fib_node.h.

◆ fib_node_bw_flags_t

Flags on the walk.

◆ fib_node_bw_reason_flag_t

Flags enum constructed from the reaons.

◆ fib_node_get_t

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 266 of file fib_node.h.

◆ fib_node_last_lock_gone_t

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 271 of file fib_node.h.

◆ fib_node_list_t

A list of FIB nodes.

Definition at line 203 of file fib_node.h.

◆ fib_node_memory_show_t

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 277 of file fib_node.h.

◆ fib_node_ptr_list_t

A list of dependent nodes.

This is currently implemented as a hash_table of fib_node_ptr_t

Definition at line 246 of file fib_node.h.

◆ fib_node_ptr_t

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.

◆ fib_node_ptr_walk_t

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 239 of file fib_node.h.

◆ fib_node_t

typedef struct fib_node_t_ fib_node_t

An node in the FIB graph.

Objects in the FIB form a graph.

◆ fib_node_type_t

The types of nodes in a FIB graph.

◆ fib_node_vft_t

A FIB graph nodes virtual function table.

Enumeration Type Documentation

◆ fib_node_back_walk_rc_t_

Return code from a back walk function.

Enumerator
FIB_NODE_BACK_WALK_MERGE 
FIB_NODE_BACK_WALK_CONTINUE 

Definition at line 251 of file fib_node.h.

◆ fib_node_back_walk_reason_t_

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 88 of file fib_node.h.

◆ fib_node_bw_flags_t_

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 168 of file fib_node.h.

◆ fib_node_bw_reason_flag_t_

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 149 of file fib_node.h.

◆ fib_node_type_t_

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_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_VXLAN_GBP_TUNNEL 
FIB_NODE_TYPE_IPSEC_SA 
FIB_NODE_TYPE_IP_PUNT_REDIRECT 
FIB_NODE_TYPE_ENTRY_TRACK 
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_one()

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:

◆ fib_node_child_add()

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:

◆ fib_node_child_remove()

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:

◆ fib_node_children_format()

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:

◆ fib_node_deinit()

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:

◆ fib_node_get_n_children()

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:

◆ fib_node_index_is_valid()

static int fib_node_index_is_valid ( fib_node_index_t  ni)
inlinestatic

Definition at line 386 of file fib_node.h.

◆ fib_node_init()

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:

◆ fib_node_lock()

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_register_new_type()

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:

◆ fib_node_register_type()

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:

◆ fib_node_type_get_name()

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:

◆ fib_node_unlock()

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:

◆ fib_show_memory_usage()

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:

◆ format_fib_node_bw_reason()

u8* format_fib_node_bw_reason ( u8 s,
va_list *  args 
)

Definition at line 973 of file fib_walk.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ STATIC_ASSERT() [1/2]

STATIC_ASSERT ( )

◆ STATIC_ASSERT() [2/2]

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