FIB is a data structure designed for storage of routes indexed by their network prefixes. It supports insertion, deletion, searching by prefix, `routing' (in CIDR sense, that is searching for a longest prefix matching a given IP address) and (which makes the structure very tricky to implement) asynchronous reading, that is enumerating the contents of a FIB while other modules add, modify or remove entries.
Internally, each FIB is represented as a collection of nodes of type fib_node indexed using a sophisticated hashing mechanism. We use two-stage hashing where we calculate a 16-bit primary hash key independent on hash table size and then we just divide the primary keys modulo table size to get a real hash key used for determining the bucket containing the node. The lists of nodes in each bucket are sorted according to the primary hash key, hence if we keep the total number of buckets to be a power of two, re-hashing of the structure keeps the relative order of the nodes.
To get the asynchronous reading consistent over node deletions, we need to keep a list of readers for each node. When a node gets deleted, its readers are automatically moved to the next node in the table.
Basic FIB operations are performed by functions defined by this module, enumerating of FIB contents is accomplished by using the FIB_WALK() macro or FIB_ITERATE_START() if you want to do it asynchronously.
void fib_init (struct fib * f, pool * p, unsigned node_size, unsigned hash_order, fib_init_func init) -- initialize a new FIB
the FIB to be initialized (the structure itself being allocated by the caller)
pool to allocate the nodes in
node size to be used (each node consists of a standard header fib_node followed by user data)
initial hash order (a binary logarithm of hash table size), 0 to use default order (recommended)
pointer a function to be called to initialize a newly created node
This function initializes a newly allocated FIB and prepares it for use.
void * fib_find (struct fib * f, ip_addr * a, int len) -- search for FIB node by prefix
FIB to search in
pointer to IP address of the prefix
prefix length
Search for a FIB node corresponding to the given prefix, return a pointer to it or NULL if no such node exists.
void * fib_get (struct fib * f, ip_addr * a, int len) -- find or create a FIB node
FIB to work with
pointer to IP address of the prefix
prefix length
Search for a FIB node corresponding to the given prefix and return a pointer to it. If no such node exists, create it.
void * fib_route (struct fib * f, ip_addr a, int len) -- CIDR routing lookup
FIB to search in
pointer to IP address of the prefix
prefix length
Search for a FIB node with longest prefix matching the given network, that is a node which a CIDR router would use for routing that network.
void fib_delete (struct fib * f, void * E) -- delete a FIB node
FIB to delete from
entry to delete
This function removes the given entry from the FIB, taking care of all the asynchronous readers by shifting them to the next node in the canonical reading order.
void fib_free (struct fib * f) -- delete a FIB
FIB to be deleted
This function deletes a FIB -- it frees all memory associated with it and all its entries.
void fib_check (struct fib * f) -- audit a FIB
FIB to be checked
This debugging function audits a FIB by checking its internal consistency. Use when you suspect somebody of corrupting innocent data structures.
Routing tables are probably the most important structures BIRD uses. They hold all the information about known networks, the associated routes and their attributes.
There are multiple routing tables (a primary one together with any number of secondary ones if requested by the configuration). Each table is basically a FIB containing entries describing the individual destination networks. For each network (represented by structure net), there is a one-way linked list of route entries (rte), the first entry on the list being the best one (i.e., the one we currently use for routing), the order of the other ones is undetermined.
The rte contains information specific to the route (preference, protocol metrics, time of last modification etc.) and a pointer to a rta structure (see the route attribute module for a precise explanation) holding the remaining route attributes which are expected to be shared by multiple routes in order to conserve memory.
rte * rte_find (net * net, struct proto * p) -- find a route
network node
protocol
The rte_find() function returns a route for destination net which belongs has been defined by protocol p.
rte * rte_get_temp (rta * a) -- get a temporary rte
attributes to assign to the new route (a rta; in case it's un-cached, rte_update() will create a cached copy automatically)
Create a temporary rte and bind it with the attributes a. Also set route preference to the default preference set for the protocol.
void rte_announce (rtable * tab, net * net, rte * new, rte * old, ea_list * tmpa) -- announce a routing table change
table the route has been added to
network in question
the new route to be announced
previous optimal route for the same network
a list of temporary attributes belonging to the new route
This function gets a routing table update and announces it to all protocols connected to the same table by their announcement hooks.
For each such protocol, we first call its import_control() hook which performs basic checks on the route (each protocol has a right to veto or force accept of the route before any filter is asked) and adds default values of attributes specific to the new protocol (metrics, tags etc.). Then it consults the protocol's export filter and if it accepts the route, the rt_notify() hook of the protocol gets called.
void rte_free (rte * e) -- delete a rte
rte to be deleted
rte_free() deletes the given rte from the routing table it's linked to.
void rte_update (rtable * table, net * net, struct proto * p, rte * new) -- enter a new update to a routing table
table to be updated
network node
protocol submitting the update
a rte representing the new route or NULL for route removal.
This function is called by the routing protocols whenever they discover a new route or wish to update/remove an existing route. The right announcement sequence is to build route attributes first (either un-cached with aflags set to zero or a cached one using rta_lookup(); in this case please note that you need to increase the use count of the attributes yourself by calling rta_clone()), call rte_get_temp() to obtain a temporary rte, fill in all the appropriate data and finally submit the new rte by calling rte_update().
When rte_update() gets any route, it automatically validates it (checks, whether the network and next hop address are valid IP addresses and also whether a normal routing protocol doesn't try to smuggle a host or link scope route to the table), converts all protocol dependent attributes stored in the rte to temporary extended attributes, consults import filters of the protocol to see if the route should be accepted and/or its attributes modified, stores the temporary attributes back to the rte.
Now, having a "public" version of the route, we automatically find any old route defined by the protocol p for network n, replace it by the new one (or removing it if new is NULL), recalculate the optimal route for this destination and finally broadcast the change (if any) to all routing protocols by calling rte_announce().
All memory used for attribute lists and other temporary allocations is taken from a special linear pool rte_update_pool and freed when rte_update() finishes.
void rte_dump (rte * e) -- dump a route
rte to be dumped
This functions dumps contents of a rte to debug output.
void rt_dump (rtable * t) -- dump a routing table
routing table to be dumped
This function dumps contents of a given routing table to debug output.
void rt_dump_all (void) -- dump all routing tables
This function dumps contents of all routing tables to debug output.
void rt_init (void) -- initialize routing tables
This function is called during BIRD startup. It initializes the routing table module.
void rt_prune (rtable * tab) -- prune a routing table
routing table to be pruned
This function is called whenever a protocol shuts down. It scans the routing table and removes all routes belonging to inactive protocols and also stale network entries.
void rt_prune_all (void) -- prune all routing tables
This function calls rt_prune() for all known routing tables.
void rt_lock_table (rtable * r) -- lock a routing table
routing table to be locked
Lock a routing table, because it's in use by a protocol, preventing it from being freed when it gets undefined in a new configuration.
void rt_unlock_table (rtable * r) -- unlock a routing table
routing table to be unlocked
Unlock a routing table formerly locked by rt_lock_table(), that is decrease its use count and delete it if it's scheduled for deletion by configuration changes.
void rt_commit (struct config * new, struct config * old) -- commit new routing table configuration
new configuration
original configuration or NULL if it's boot time config
Scan differences between old and new configuration and modify the routing tables according to these changes. If new defines a previously unknown table, create it, if it omits a table existing in old, schedule it for deletion (it gets deleted when all protocols disconnect from it by calling rt_unlock_table()), if it exists in both configurations, leave it unchanged.
int rt_feed_baby (struct proto * p) -- advertise routes to a new protocol
protocol to be fed
This function performs one pass of advertisement of routes to a newly initialized protocol. It's called by the protocol code as long as it has something to do. (We avoid transferring all the routes in single pass in order not to monopolize CPU time.)
void rt_feed_baby_abort (struct proto * p) -- abort protocol feeding
protocol
This function is called by the protocol code when the protocol stops or ceases to exist before the last iteration of rt_feed_baby() has finished.
net * net_find (rtable * tab, ip_addr addr, unsigned len) -- find a network entry
a routing table
address of the network
length of the network prefix
net_find() looks up the given network in routing table tab and returns a pointer to its net entry or NULL if no such network exists.
net * net_get (rtable * tab, ip_addr addr, unsigned len) -- obtain a network entry
a routing table
address of the network
length of the network prefix
net_get() looks up the given network in routing table tab and returns a pointer to its net entry. If no such entry exists, it's created.
rte * rte_cow (rte * r) -- copy a route for writing
a route entry to be copied
rte_cow() takes a rte and prepares it for modification. The exact action taken depends on the flags of the rte -- if it's a temporary entry, it's just returned unchanged, else a new temporary entry with the same contents is created.
The primary use of this function is inside the filter machinery -- when a filter wants to modify rte contents (to change the preference or to attach another set of attributes), it must ensure that the rte is not shared with anyone else (and especially that it isn't stored in any routing table).
a pointer to the new writable rte.
Each route entry carries a set of route attributes. Several of them vary from route to route, but most attributes are usually common for a large number of routes. To conserve memory, we've decided to store only the varying ones directly in the rte and hold the rest in a special structure called rta which is shared among all the rte's with these attributes.
Each rta contains all the static attributes of the route (i.e., those which are always present) as structure members and a list of dynamic attributes represented by a linked list of ea_list structures, each of them consisting of an array of eattr's containing the individual attributes. An attribute can be specified more than once in the ea_list chain and in such case the first occurrence overrides the others. This semantics is used especially when someone (for example a filter) wishes to alter values of several dynamic attributes, but it wants to preserve the original attribute lists maintained by another module.
Each eattr contains an attribute identifier (split to protocol ID and per-protocol attribute ID), protocol dependent flags, a type code (consisting of several bit fields describing attribute characteristics) and either an embedded 32-bit value or a pointer to a adata structure holding attribute contents.
There exist two variants of rta's -- cached and un-cached ones. Un-cached rta's can have arbitrarily complex structure of ea_list's and they can be modified by any module in the route processing chain. Cached rta's have their attribute lists normalized (that means at most one ea_list is present and its values are sorted in order to speed up searching), they are stored in a hash table to make fast lookup possible and they are provided with a use count to allow sharing.
Routing tables always contain only cached rta's.
eattr * ea_find (ea_list * e, unsigned id) -- find an extended attribute
attribute list to search in
attribute ID to search for
Given an extended attribute list, ea_find() searches for a first occurrence of an attribute with specified ID, returning either a pointer to its eattr structure or NULL if no such attribute exists.
int ea_get_int (ea_list * e, unsigned id, int def) -- fetch an integer attribute
attribute list
attribute ID
default value
This function is a shortcut for retrieving a value of an integer attribute by calling ea_find() to find the attribute, extracting its value or returning a provided default if no such attribute is present.
void ea_sort (ea_list * e) -- sort an attribute list
list to be sorted
This function takes a ea_list chain and sorts the attributes within each of its entries.
If an attribute occurs multiple times in a single ea_list, ea_sort() leaves only the first (the only significant) occurrence.
unsigned ea_scan (ea_list * e) -- estimate attribute list size
attribute list
This function calculates an upper bound of the size of a given ea_list after merging with ea_merge().
void ea_merge (ea_list * e, ea_list * t) -- merge segments of an attribute list
attribute list
buffer to store the result to
This function takes a possibly multi-segment attribute list and merges all of its segments to one.
The primary use of this function is for ea_list normalization: first call ea_scan() to determine how much memory will the result take, then allocate a buffer (usually using alloca()), merge the segments with ea_merge() and finally sort and prune the result by calling ea_sort().
int ea_same (ea_list * x, ea_list * y) -- compare two ea_list's
attribute list
attribute list
ea_same() compares two normalized attribute lists x and y and returns 1 if they contain the same attributes, 0 otherwise.
void ea_format (eattr * e, byte * buf) -- format an eattr for printing
attribute to be formatted
destination buffer of size EA_FORMAT_BUF_SIZE
This function takes an extended attribute represented by its eattr structure and formats it nicely for printing according to the type information.
If the protocol defining the attribute provides its own get_attr() hook, it's consulted first.
void ea_dump (ea_list * e) -- dump an extended attribute
attribute to be dumped
ea_dump() dumps contents of the extended attribute given to the debug output.
unsigned int ea_hash (ea_list * e) -- calculate an ea_list hash key
attribute list
ea_hash() takes an extended attribute list and calculated a hopefully uniformly distributed hash value from its contents.
ea_list * ea_append (ea_list * to, ea_list * what) -- concatenate ea_list's
destination list (can be NULL)
list to be appended (can be NULL)
This function appends the ea_list what at the end of ea_list to and returns a pointer to the resulting list.
rta * rta_lookup (rta * o) -- look up a rta in attribute cache
a un-cached rta
rta_lookup() gets an un-cached rta structure and returns its cached counterpart. It starts with examining the attribute cache to see whether there exists a matching entry. If such an entry exists, it's returned and its use count is incremented, else a new entry is created with use count set to 1.
The extended attribute lists attached to the rta are automatically converted to the normalized form.
void rta_dump (rta * a) -- dump route attributes
attribute structure to dump
This function takes a rta and dumps its contents to the debug output.
void rta_dump_all (void) -- dump attribute cache
This function dumps the whole contents of route attribute cache to the debug output.
void rta_init (void) -- initialize route attribute cache
This function is called during initialization of the routing table module to set up the internals of the attribute cache.
rta * rta_clone (rta * r) -- clone route attributes
a rta to be cloned
rta_clone() takes a cached rta and returns its identical cached copy. Currently it works by just returning the original rta with its use count incremented.
void rta_free (rta * r) -- free route attributes
a rta to be freed
If you stop using a rta (for example when deleting a route which uses it), you need to call rta_free() to notify the attribute cache the attribute is no longer in use and can be freed if you were the last user (which rta_free() tests by inspecting the use count).
The routing protocols are the bird's heart and a fine amount of code
is dedicated to their management and for providing support functions to them.
(-: Actually, this is the reason why the directory with sources of the core
code is called nest :-).
When talking about protocols, one need to distinguish between protocols and protocol instances. A protocol exists exactly once, not depending on whether it's configured or not and it can have an arbitrary number of instances corresponding to its "incarnations" requested by the configuration file. Each instance is completely autonomous, has its own configuration, its own status, its own set of routes and its own set of interfaces it works on.
A protocol is represented by a protocol structure containing all the basic information (protocol name, default settings and pointers to most of the protocol hooks). All these structures are linked in the protocol_list list.
Each instance has its own proto structure describing all its properties: protocol
type, configuration, a resource pool where all resources belonging to the instance
live, various protocol attributes (take a look at the declaration of proto in
protocol.h), protocol states (see below for what do they mean), connections
to routing tables, filters attached to the protocol
and finally a set of pointers to the rest of protocol hooks (they
are the same for all instances of the protocol, but in order to avoid extra
indirections when calling the hooks from the fast path, they are stored directly
in proto). The instance is always linked in both the global instance list
(proto_list) and a per-status list (either active_proto_list for
running protocols, initial_proto_list for protocols being initialized or
flush_proto_list when the protocol is being shut down).
The protocol hooks are described in the next chapter, for more information about configuration of protocols, please refer to the configuration chapter and also to the description of the proto_commit function.
As startup and shutdown of each protocol are complex processes which can be affected
by lots of external events (user's actions, reco>rte_cow() unsigned
ea_scan
(ea_list * e) -- estimate attribute list size
attribute list
This function calculates an upper bound of the size of
a given ea_list after merging with ea_merge().
void
ea_merge
(ea_list * e, ea_list * t) -- merge segments of an attribute list
attribute list
buffer to store the result to
This function takes a possibly multi-segment attribute list
and merges all of its segments to one.
The primary use of this function is for ea_list normalization:
first call ea_scan() to determine how much memory will the result
take, then allocate a buffer (usually using alloca()), merge the
segments with ea_merge() and finally sort and prune the result
by calling ea_sort().
int
ea_same
(ea_list * x, ea_list * y) -- compare two ea_list's
attribute list
attribute list
ea_same() compares two normalized attribute lists x and y and returns
1 if they contain the same attributes, 0 otherwise.
void
ea_format
(eattr * e, byte * buf) -- format an eattr for printing
attribute to be formatted
destination buffer of size EA_FORMAT_BUF_SIZE
This function takes an extended attribute represented by its
eattr structure and formats it nicely for printing according
to the type information.
If the protocol defining the attribute provides its own
get_attr() hook, it's consulted first.
void
ea_dump
(ea_list * e) -- dump an extended attribute
attribute to be dumped
ea_dump() dumps contents of the extended attribute given to
the debug output.
unsigned int
ea_hash
(ea_list * e) -- calculate an ea_list hash key
attribute list
ea_hash() takes an extended attribute list and calculated a hopefully
uniformly distributed hash value from its contents.
ea_list *
ea_append
(ea_list * to, ea_list * what) -- concatenate ea_list's
destination list (can be NULL)
list to be appended (can be NULL)
This function appends the ea_list what at the end of
ea_list to and returns a pointer to the resulting list.
rta *
rta_lookup
(rta * o) -- look up a rta in attribute cache
a un-cached rta
rta_lookup() gets an un-cached rta structure and returns its cached
counterpart. It starts with examining the attribute cache to see whether
there exists a matching entry. If such an entry exists, it's returned and
its use count is incremented, else a new entry is created with use count
set to 1.
The extended attribute lists attached to the rta are automatically
converted to the normalized form.
void
rta_dump
(rta * a) -- dump route attributes
attribute structure to dump
This function takes a rta and dumps its contents to the debug output.
void
rta_dump_all
(void) -- dump attribute cache
This function dumps the whole contents of route attribute cache
to the debug output.
void
rta_init
(void) -- initialize route attribute cache
This function is called during initialization of the routing
table module to set up the internals of the attribute cache.
rta *
rta_clone
(rta * r) -- clone route attributes
a rta to be cloned
rta_clone() takes a cached rta and returns its identical cached
copy. Currently it works by just returning the original rta with
its use count incremented.
void
rta_free
(rta * r) -- free route attributes
a rta to be freed
If you stop using a rta (for example when deleting a route which uses
it), you need to call rta_free() to notify the attribute cache the
attribute is no longer in use and can be freed if you were the last
user (which rta_free() tests by inspecting the use count).
The routing protocols are the bird's heart and a fine amount of code
is dedicated to their management and for providing support functions to them.
(-: Actually, this is the reason why the directory with sources of the core
code is called
When talking about protocols, one need to distinguish between protocols
and protocol instances. A protocol exists exactly once, not depending on whether
it's configured or not and it can have an arbitrary number of instances corresponding
to its "incarnations" requested by the configuration file. Each instance is completely
autonomous, has its own configuration, its own status, its own set of routes and its
own set of interfaces it works on.
A protocol is represented by a protocol structure containing all the basic
information (protocol name, default settings and pointers to most of the protocol
hooks). All these structures are linked in the protocol_list list.
Each instance has its own proto structure describing all its properties: protocol
type, configuration, a resource pool where all resources belonging to the instance
live, various protocol attributes (take a look at the declaration of proto in
The protocol hooks are described in the next chapter, for more information about
configuration of protocols, please refer to the configuration chapter and also
to the description of the proto_commit function.
As startup and shutdown of each protocol are complex processes which can be affected
by lots of external events (user's actions, reco>rte_cow() unsigned
ea_scan
(ea_list * e) -- estimate attribute list size
attribute list
This function calculates an upper bound of the size of
a given ea_list after merging with ea_merge().
void
ea_merge
(ea_list * e, ea_list * t) -- merge segments of an attribute list
attribute list
buffer to store the result to
This function takes a possibly multi-segment attribute list
and merges all of its segments to one.
The primary use of this function is for ea_list normalization:
first call ea_scan() to determine how much memory will the result
take, then allocate a buffer (usually using alloca()), merge the
segments with ea_merge() and finally sort and prune the result
by calling ea_sort().
int
ea_same
(ea_list * x, ea_list * y) -- compare two ea_list's
attribute list
attribute list
ea_same() compares two normalized attribute lists x and y and returns
1 if they contain the same attributes, 0 otherwise.
void
ea_format
(eattr * e, byte * buf) -- format an eattr for printing
attribute to be formatted
destination buffer of size EA_FORMAT_BUF_SIZE
This function takes an extended attribute represented by its
eattr structure and formats it nicely for printing according
to the type information.
If the protocol defining the attribute provides its own
get_attr() hook, it's consulted first.
void
ea_dump
(ea_list * e) -- dump an extended attribute
attribute to be dumped
ea_dump() dumps contents of the extended attribute given to
the debug output.
unsigned int
ea_hash
(ea_list * e) -- calculate an ea_list hash key
attribute list
ea_hash() takes an extended attribute list and calculated a hopefully
uniformly distributed hash value from its contents.
ea_list *
ea_append
(ea_list * to, ea_list * what) -- concatenate ea_list's
destination list (can be NULL)
list to be appended (can be NULL)
This function appends the ea_list what at the end of
ea_list to and returns a pointer to the resulting list.
rta *
rta_lookup
(rta * o) -- look up a rta in attribute cache
a un-cached rta
rta_lookup() gets an un-cached rta structure and returns its cached
counterpart. It starts with examining the attribute cache to see whether
there exists a matching entry. If such an entry exists, it's returned and
its use count is incremented, else a new entry is created with use count
set to 1.
The extended attribute lists attached to the rta are automatically
converted to the normalized form.
void
rta_dump
(rta * a) -- dump route attributes
attribute structure to dump
This function takes a rta and dumps its contents to the debug output.
void
rta_dump_all
(void) -- dump attribute cache
This function dumps the whole contents of route attribute cache
to the debug output.
void
rta_init
(void) -- initialize route attribute cache
This function is called during initialization of the routing
table module to set up the internals of the attribute cache.
rta *
rta_clone
(rta * r) -- clone route attributes
a rta to be cloned
rta_clone() takes a cached rta and returns its identical cached
copy. Currently it works by just returning the original rta with
its use count incremented.
void
rta_free
(rta * r) -- free route attributes
a rta to be freed
If you stop using a rta (for example when deleting a route which uses
it), you need to call rta_free() to notify the attribute cache the
attribute is no longer in use and can be freed if you were the last
user (which rta_free() tests by inspecting the use count).
The routing protocols are the bird's heart and a fine amount of code
is dedicated to their management and for providing support functions to them.
(-: Actually, this is the reason why the directory with sources of the core
code is called
When talking about protocols, one need to distinguish between protocols
and protocol instances. A protocol exists exactly once, not depending on whether
it's configured or not and it can have an arbitrary number of instances corresponding
to its "incarnations" requested by the configuration file. Each instance is completely
autonomous, has its own configuration, its own status, its own set of routes and its
own set of interfaces it works on.
A protocol is represented by a protocol structure containing all the basic
information (protocol name, default settings and pointers to most of the protocol
hooks). All these structures are linked in the protocol_list list.
Each instance has its own proto structure describing all its properties: protocol
type, configuration, a resource pool where all resources belonging to the instance
live, various protocol attributes (take a look at the declaration of proto in
The protocol hooks are described in the next chapter, for more information about
configuration of protocols, please refer to the configuration chapter and also
to the description of the proto_commit function.
As startup and shutdown of each protocol are complex processes which can be affected
by lots of external events (user's actions, reco>rte_cow() unsigned
ea_scan
(ea_list * e) -- estimate attribute list size
attribute list
This function calculates an upper bound of the size of
a given ea_list after merging with ea_merge().
void
ea_merge
(ea_list * e, ea_list * t) -- merge segments of an attribute list
attribute list
buffer to store the result to
This function takes a possibly multi-segment attribute list
and merges all of its segments to one.
The primary use of this function is for ea_list normalization:
first call ea_scan() to determine how much memory will the result
take, then allocate a buffer (usually using alloca()), merge the
segments with ea_merge() and finally sort and prune the result
by calling ea_sort().
int
ea_same
(ea_list * x, ea_list * y) -- compare two ea_list's
attribute list
attribute list
ea_same() compares two normalized attribute lists x and y and returns
1 if they contain the same attributes, 0 otherwise.
void
ea_format
(eattr * e, byte * buf) -- format an eattr for printing
attribute to be formatted
destination buffer of size EA_FORMAT_BUF_SIZE
This function takes an extended attribute represented by its
eattr structure and formats it nicely for printing according
to the type information.
If the protocol defining the attribute provides its own
get_attr() hook, it's consulted first.
void
ea_dump
(ea_list * e) -- dump an extended attribute
attribute to be dumped
ea_dump() dumps contents of the extended attribute given to
the debug output.
unsigned int
ea_hash
(ea_list * e) -- calculate an ea_list hash key
attribute list
ea_hash() takes an extended attribute list and calculated a hopefully
uniformly distributed hash value from its contents.
ea_list *
ea_append
(ea_list * to, ea_list * what) -- concatenate ea_list's
destination list (can be NULL)
list to be appended (can be NULL)
This function appends the ea_list what at the end of
ea_list to and returns a pointer to the resulting list.
rta *
rta_lookup
(rta * o) -- look up a rta in attribute cache
a un-cached rta
rta_lookup() gets an un-cached rta structure and returns its cached
counterpart. It starts with examining the attribute cache to see whether
there exists a matching entry. If such an entry exists, it's returned and
its use count is incremented, else a new entry is created with use count
set to 1.
The extended attribute lists attached to the rta are automatically
converted to the normalized form.
void
rta_dump
(rta * a) -- dump route attributes
attribute structure to dump
This function takes a rta and dumps its contents to the debug output.
void
rta_dump_all
(void) -- dump attribute cache
This function dumps the whole contents of route attribute cache
to the debug output.
void
rta_init
(void) -- initialize route attribute cache
This function is called during initialization of the routing
table module to set up the internals of the attribute cache.
rta *
rta_clone
(rta * r) -- clone route attributes
a rta to be cloned
rta_clone() takes a cached rta and returns its identical cached
copy. Currently it works by just returning the original rta with
its use count incremented.
void
rta_free
(rta * r) -- free route attributes
a rta to be freed
If you stop using a rta (for example when deleting a route which uses
it), you need to call rta_free() to notify the attribute cache the
attribute is no longer in use and can be freed if you were the last
user (which rta_free() tests by inspecting the use count).
The routing protocols are the bird's heart and a fine amount of code
is dedicated to their management and for providing support functions to them.
(-: Actually, this is the reason why the directory with sources of the core
code is called
When talking about protocols, one need to distinguish between protocols
and protocol instances. A protocol exists exactly once, not depending on whether
it's configured or not and it can have an arbitrary number of instances corresponding
to its "incarnations" requested by the configuration file. Each instance is completely
autonomous, has its own configuration, its own status, its own set of routes and its
own set of interfaces it works on.
A protocol is represented by a protocol structure containing all the basic
information (protocol name, default settings and pointers to most of the protocol
hooks). All these structures are linked in the protocol_list list.
Each instance has its own proto structure describing all its properties: protocol
type, configuration, a resource pool where all resources belonging to the instance
live, various protocol attributes (take a look at the declaration of proto in
The protocol hooks are described in the next chapter, for more information about
configuration of protocols, please refer to the configuration chapter and also
to the description of the proto_commit function.
As startup and shutdown of each protocol are complex processes which can be affected
by lots of external events (user's actions, reco>rte_cow() unsigned
ea_scan
(ea_list * e) -- estimate attribute list size
attribute list
This function calculates an upper bound of the size of
a given ea_list after merging with ea_merge().
void
ea_merge
(ea_list * e, ea_list * t) -- merge segments of an attribute list
attribute list
buffer to store the result to
This function takes a possibly multi-segment attribute list
and merges all of its segments to one.
The primary use of this function is for ea_list normalization:
first call ea_scan() to determine how much memory will the result
take, then allocate a buffer (usually using alloca()), merge the
segments with ea_merge() and finally sort and prune the result
by calling ea_sort().
int
ea_same
(ea_list * x, ea_list * y) -- compare two ea_list's
attribute list
attribute list
ea_same() compares two normalized attribute lists x and y and returns
1 if they contain the same attributes, 0 otherwise.
void
ea_format
(eattr * e, byte * buf) -- format an eattr for printing
attribute to be formatted
destination buffer of size EA_FORMAT_BUF_SIZE
This function takes an extended attribute represented by its
eattr structure and formats it nicely for printing according
to the type information.
If the protocol defining the attribute provides its own
get_attr() hook, it's consulted first.
void
ea_dump
(ea_list * e) -- dump an extended attribute
attribute to be dumped
ea_dump() dumps contents of the extended attribute given to
the debug output.
unsigned int
ea_hash
(ea_list * e) -- calculate an ea_list hash key
attribute list
ea_hash() takes an extended attribute list and calculated a hopefully
uniformly distributed hash value from its contents.
ea_list *
ea_append
(ea_list * to, ea_list * what) -- concatenate ea_list's
destination list (can be NULL)
list to be appended (can be NULL)
This function appends the ea_list what at the end of
ea_list to and returns a pointer to the resulting list.
rta *
rta_lookup
(rta * o) -- look up a rta in attribute cache
a un-cached rta
rta_lookup() gets an un-cached rta structure and returns its cached
counterpart. It starts with examining the attribute cache to see whether
there exists a matching entry. If such an entry exists, it's returned and
its use count is incremented, else a new entry is created with use count
set to 1.
The extended attribute lists attached to the rta are automatically
converted to the normalized form.
void
rta_dump
(rta * a) -- dump route attributes
attribute structure to dump
This function takes a rta and dumps its contents to the debug output.
void
rta_dump_all
(void) -- dump attribute cache
This function dumps the whole contents of route attribute cache
to the debug output.
void
rta_init
(void) -- initialize route attribute cache
This function is called during initialization of the routing
table module to set up the internals of the attribute cache.
rta *
rta_clone
(rta * r) -- clone route attributes
a rta to be cloned
rta_clone() takes a cached rta and returns its identical cached
copy. Currently it works by just returning the original rta with
its use count incremented.
void
rta_free
(rta * r) -- free route attributes
a rta to be freed
If you stop using a rta (for example when deleting a route which uses
it), you need to call rta_free() to notify the attribute cache the
attribute is no longer in use and can be freed if you were the last
user (which rta_free() tests by inspecting the use count).
The routing protocols are the bird's heart and a fine amount of code
is dedicated to their management and for providing support functions to them.
(-: Actually, this is the reason why the directory with sources of the core
code is called
When talking about protocols, one need to distinguish between protocols
and protocol instances. A protocol exists exactly once, not depending on whether
it's configured or not and it can have an arbitrary number of instances corresponding
to its "incarnations" requested by the configuration file. Each instance is completely
autonomous, has its own configuration, its own status, its own set of routes and its
own set of interfaces it works on.
A protocol is represented by a protocol structure containing all the basic
information (protocol name, default settings and pointers to most of the protocol
hooks). All these structures are linked in the protocol_list list.
Each instance has its own proto structure describing all its properties: protocol
type, configuration, a resource pool where all resources belonging to the instance
live, various protocol attributes (take a look at the declaration of proto in
The protocol hooks are described in the next chapter, for more information about
configuration of protocols, please refer to the configuration chapter and also
to the description of the proto_commit function.
As startup and shutdown of each protocol are complex processes which can be affected
by lots of external events (user's actions, reco>rte_cow() unsigned
ea_scan
(ea_list * e) -- estimate attribute list size
attribute list
This function calculates an upper bound of the size of
a given ea_list after merging with ea_merge().
void
ea_merge
(ea_list * Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Description
Function
Description
Function
Arguments
Description
Function
Arguments
Description
2.4 Routing protocols
Introduction
nest :-).
protocol.h), protocol states (see below for what do they mean), connections
to routing tables, filters attached to the protocol
and finally a set of pointers to the rest of protocol hooks (they
are the same for all instances of the protocol, but in order to avoid extra
indirections when calling the hooks from the fast path, they are stored directly
in proto). The instance is always linked in both the global instance list
(proto_list) and a per-status list (either active_proto_list for
running protocols, initial_proto_list for protocols being initialized or
flush_proto_list when the protocol is being shut down).
Protocol states
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Description
Function
Description
Function
Arguments
Description
Function
Arguments
Description
2.4 Routing protocols
Introduction
nest :-).
protocol.h), protocol states (see below for what do they mean), connections
to routing tables, filters attached to the protocol
and finally a set of pointers to the rest of protocol hooks (they
are the same for all instances of the protocol, but in order to avoid extra
indirections when calling the hooks from the fast path, they are stored directly
in proto). The instance is always linked in both the global instance list
(proto_list) and a per-status list (either active_proto_list for
running protocols, initial_proto_list for protocols being initialized or
flush_proto_list when the protocol is being shut down).
Protocol states
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Description
Function
Description
Function
Arguments
Description
Function
Arguments
Description
2.4 Routing protocols
Introduction
nest :-).
protocol.h), protocol states (see below for what do they mean), connections
to routing tables, filters attached to the protocol
and finally a set of pointers to the rest of protocol hooks (they
are the same for all instances of the protocol, but in order to avoid extra
indirections when calling the hooks from the fast path, they are stored directly
in proto). The instance is always linked in both the global instance list
(proto_list) and a per-status list (either active_proto_list for
running protocols, initial_proto_list for protocols being initialized or
flush_proto_list when the protocol is being shut down).
Protocol states
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Arguments
Description
Function
Description
Function
Description
Function
Arguments
Description
Function
Arguments
Description
2.4 Routing protocols
Introduction
nest :-).
protocol.h), protocol states (see below for what do they mean), connections
to routing tables, filters attached to the protocol
and finally a set of pointers to the rest of protocol hooks (they
are the same for all instances of the protocol, but in order to avoid extra
indirections when calling the hooks from the fast path, they are stored directly
in proto). The instance is always linked in both the global instance list
(proto_list) and a per-status list (either active_proto_list for
running protocols, initial_proto_list for protocols being initialized or
flush_proto_list when the protocol is being shut down).
Protocol states
Function
Arguments
Description
Function