FD.io VPP  v17.07-30-g839fa73
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_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_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")
 
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:111
Walk to re-collapse the multipath adjs when the rewrite of a unipath adjacency changes.
Definition: fib_node.h:107
Walk to re-resolve the child.
Definition: fib_node.h:84
A resolving interface has gone down.
Definition: fib_node.h:98
A resolving interface has been deleted.
Definition: fib_node.h:102
Walk to re-evaluate the forwarding contributed by the parent.
Definition: fib_node.h:90
A resolving interface has come up.
Definition: fib_node.h:94

Definition at line 118 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 218 of file fib_node.h.

#define FIB_NODE_TYPE_MAX   (FIB_NODE_TYPE_LAST + 1)

Definition at line 53 of file fib_node.h.

#define FIB_NODE_TYPES
Value:

Definition at line 55 of file fib_node.h.

#define FOR_EACH_FIB_NODE_BW_REASON (   _item)
Value:

Definition at line 128 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 243 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 250 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 255 of file fib_node.h.

A list of FIB nodes.

Definition at line 187 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 261 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 230 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 223 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 235 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 75 of file fib_node.h.

Flags on the walk.

Enumerator
FIB_NODE_BW_FLAG_FORCE_SYNC 

Force the walk to be synchronous.

Definition at line 153 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 136 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_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 152 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 96 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 121 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 174 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 198 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 140 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 371 of file fib_node.h.

void fib_node_init ( fib_node_t node,
fib_node_type_t  ft 
)

The node's type. make sure we are dynamic/down casting correctly

Definition at line 183 of file fib_node.c.

+ Here is the caller graph for this function:

void fib_node_lock ( fib_node_t node)

Definition at line 204 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 78 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 58 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 35 of file fib_node.c.

+ Here is the caller graph for this function:

void fib_node_unlock ( fib_node_t node)

Definition at line 210 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 221 of file fib_node.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

STATIC_ASSERT ( )