[Olsr-cvs] olsrd-current/src hna_set.c, 1.29, 1.30 link_set.c, 1.80, 1.81 link_set.h, 1.36, 1.37 lq_route.c, 1.61, 1.62 mid_set.c, 1.27, 1.28 mid_set.h, 1.16, 1.17 olsr.c, 1.65, 1.66 olsr_cfg.h, 1.42, 1.43 process_routes.c, 1.42, 1.43 process_routes.h, 1.15, 1.16 routing_table.c, 1.38, 1.39 routing_table.h, 1.25, 1.26 tc_set.c, 1.40, 1.41 tc_set.h, 1.23, 1.24
Bernd Petrovitsch
(spam-protected)
Wed Dec 12 22:57:29 CET 2007
Update of /cvsroot/olsrd/olsrd-current/src
In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv15735/src
Modified Files:
hna_set.c link_set.c link_set.h lq_route.c mid_set.c mid_set.h
olsr.c olsr_cfg.h process_routes.c process_routes.h
routing_table.c routing_table.h tc_set.c tc_set.h
Log Message:
applied patch by Hannes Gredler <(spam-protected)>::
pls find attached a pointer for further CPU savings in olsrd.
even in large networks (>250 nodes) the avg. CPU utilization
does not get beyond 0.5% CPU load on standard 200Mhz WRT hardware.
patch from http://gredler.at/download/olsrd/rib2-refactoring4.diff
change-list:
- avoid the periodical rib-tree insertion
- add a FOR_ALL_HNA_RT_ENTRIES() macro for the snmp folks
(or any parties who want to walk HNA entries).
- add an olsr_cnf option 'flat_fib_metrics' which defaults to TRUE.
this is as per sven-olas request who has expressed concerns
that the current flap-metric style is a bit unpleasant for troubleshooting.
note that i have not yet added the cfg file parser routine for that -
just the required tweaks in the change-processing FIB code.
Index: tc_set.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/tc_set.h,v
retrieving revision 1.23
retrieving revision 1.24
diff -C2 -d -r1.23 -r1.24
*** tc_set.h 16 Nov 2007 21:43:55 -0000 1.23
--- tc_set.h 12 Dec 2007 21:57:27 -0000 1.24
***************
*** 84,88 ****
union olsr_ip_addr addr; /* vertex_node key */
struct avl_tree edge_tree; /* subtree for edges */
! struct link_entry *next_hop; /* SPF calculated link to the 1st hop neighbor */
float path_etx; /* SPF calculated distance, cand_tree_node key */
olsr_u16_t msg_seq; /* sequence number of the tc message */
--- 84,89 ----
union olsr_ip_addr addr; /* vertex_node key */
struct avl_tree edge_tree; /* subtree for edges */
! struct avl_tree prefix_tree; /* subtree for prefixes */
! struct link_entry *next_hop; /* SPF calculated link to the 1st hop neighbor */
float path_etx; /* SPF calculated distance, cand_tree_node key */
olsr_u16_t msg_seq; /* sequence number of the tc message */
***************
*** 92,96 ****
/*
! * macros for traversing the vertices and edges in the link state database.
* it is recommended to use this because it hides all the internal
* datastructure from the callers.
--- 93,97 ----
/*
! * macros for traversing vertices, edges and prefixes in the link state database.
* it is recommended to use this because it hides all the internal
* datastructure from the callers.
***************
*** 131,134 ****
--- 132,136 ----
/* tc_entry manipulation */
struct tc_entry *olsr_lookup_tc_entry(union olsr_ip_addr *);
+ struct tc_entry *olsr_locate_tc_entry(union olsr_ip_addr *);
struct tc_entry *olsr_add_tc_entry(union olsr_ip_addr *);
struct tc_entry *olsr_getnext_tc_entry(struct tc_entry *);
***************
*** 145,148 ****
--- 147,151 ----
void olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *);
float olsr_calc_tc_etx(const struct tc_edge_entry *);
+ void olsr_set_tc_edge_timer(struct tc_edge_entry *, unsigned int);
#endif
Index: mid_set.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/mid_set.h,v
retrieving revision 1.16
retrieving revision 1.17
diff -C2 -d -r1.16 -r1.17
*** mid_set.h 8 Nov 2007 22:47:41 -0000 1.16
--- mid_set.h 12 Dec 2007 21:57:27 -0000 1.17
***************
*** 52,56 ****
union olsr_ip_addr alias;
struct mid_entry *main_entry;
-
struct mid_address *next_alias;
--- 52,55 ----
***************
*** 82,89 ****
void
! insert_mid_tuple(const union olsr_ip_addr *, struct mid_address *, float);
void
! insert_mid_alias(const union olsr_ip_addr *, const union olsr_ip_addr *, float);
union olsr_ip_addr *
--- 81,88 ----
void
! insert_mid_tuple(union olsr_ip_addr *, struct mid_address *, float);
void
! insert_mid_alias(union olsr_ip_addr *, const union olsr_ip_addr *, float);
union olsr_ip_addr *
***************
*** 93,96 ****
--- 92,98 ----
mid_lookup_aliases(const union olsr_ip_addr *);
+ struct mid_entry *
+ mid_lookup_entry_bymain(const union olsr_ip_addr *);
+
void
olsr_print_mid_set(void);
***************
*** 109,110 ****
--- 111,118 ----
#endif
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: mid_set.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/mid_set.c,v
retrieving revision 1.27
retrieving revision 1.28
diff -C2 -d -r1.27 -r1.28
*** mid_set.c 2 Dec 2007 19:00:27 -0000 1.27
--- mid_set.c 12 Dec 2007 21:57:27 -0000 1.28
***************
*** 48,51 ****
--- 48,52 ----
#include "neighbor_table.h"
#include "link_set.h"
+ #include "tc_set.h"
#include "packet.h" /* struct mid_alias */
#include "net_olsr.h"
***************
*** 99,103 ****
void
! insert_mid_tuple(const union olsr_ip_addr *m_addr, struct mid_address *alias, float vtime)
{
struct mid_entry *tmp;
--- 100,104 ----
void
! insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, float vtime)
{
struct mid_entry *tmp;
***************
*** 126,129 ****
--- 127,136 ----
}
+ /*
+ * Add a rt_path for the alias.
+ */
+ olsr_insert_routing_table(&alias->alias, olsr_cnf->maxplen, m_addr,
+ OLSR_RT_ORIGIN_MID);
+
/*If the address was registered*/
if(tmp != &mid_set[hash])
***************
*** 140,143 ****
--- 147,151 ----
/*Create new node*/
tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
+ memset(tmp, 0, sizeof(struct mid_entry));
tmp->aliases = alias;
***************
*** 221,225 ****
*/
void
! insert_mid_alias(const union olsr_ip_addr *main_add, const union olsr_ip_addr *alias, float vtime)
{
struct neighbor_entry *ne_old, *ne_new;
--- 229,233 ----
*/
void
! insert_mid_alias(union olsr_ip_addr *main_add, const union olsr_ip_addr *alias, float vtime)
{
struct neighbor_entry *ne_old, *ne_new;
***************
*** 229,237 ****
struct ipaddr_str buf1, buf2;
#endif
! struct mid_address *adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
OLSR_PRINTF(1, "Inserting alias %s for ", olsr_ip_to_string(&buf1, alias));
OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf1, main_add));
adr->alias = *alias;
adr->next_alias = NULL;
--- 237,248 ----
struct ipaddr_str buf1, buf2;
#endif
! struct mid_address *adr;
OLSR_PRINTF(1, "Inserting alias %s for ", olsr_ip_to_string(&buf1, alias));
OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf1, main_add));
+ adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
+ memset(adr, 0, sizeof(struct mid_address));
+
adr->alias = *alias;
adr->next_alias = NULL;
***************
*** 446,449 ****
--- 457,466 ----
/* Remove from hash table */
DEQUEUE_ELEM(current_alias);
+
+ /*
+ * Delete the rt_path for the alias.
+ */
+ olsr_delete_routing_table(¤t_alias->alias, olsr_cnf->maxplen,
+ &entry->main_addr);
free(current_alias);
***************
*** 512,521 ****
*/
int
! mid_delete_node(struct mid_entry *entry)
{
struct mid_address *aliases;
/* Free aliases */
! aliases = entry->aliases;
while(aliases)
{
--- 529,538 ----
*/
int
! mid_delete_node(struct mid_entry *mid)
{
struct mid_address *aliases;
/* Free aliases */
! aliases = mid->aliases;
while(aliases)
{
***************
*** 523,531 ****
aliases = aliases->next_alias;
DEQUEUE_ELEM(tmp_aliases);
free(tmp_aliases);
}
/* Dequeue */
! DEQUEUE_ELEM(entry);
! free(entry);
return 0;
--- 540,556 ----
aliases = aliases->next_alias;
DEQUEUE_ELEM(tmp_aliases);
+
+
+ /*
+ * Delete the rt_path for the alias.
+ */
+ olsr_delete_routing_table(&tmp_aliases->alias, olsr_cnf->maxplen,
+ &mid->main_addr);
+
free(tmp_aliases);
}
/* Dequeue */
! DEQUEUE_ELEM(mid);
! free(mid);
return 0;
***************
*** 565,570 ****
}
!
!
!
!
--- 590,596 ----
}
! /*
! * Local Variables:
! * c-basic-offset: 2
! * End:
! */
Index: link_set.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/link_set.c,v
retrieving revision 1.80
retrieving revision 1.81
diff -C2 -d -r1.80 -r1.81
*** link_set.c 2 Dec 2007 19:00:27 -0000 1.80
--- link_set.c 12 Dec 2007 21:57:27 -0000 1.81
***************
*** 503,506 ****
--- 503,509 ----
new_link->if_name = NULL;
+ /* shortcut to interface. XXX refcount */
+ new_link->inter = local_if;
+
/*
* L_local_iface_addr = Address of the interface
***************
*** 700,703 ****
--- 703,707 ----
//printf("Vtime is %f\n", message->vtime);
/* L_ASYM_time = current time + validity time */
+ entry->vtime = message->vtime;
entry->ASYM_time = GET_TIMESTAMP(message->vtime*1000);
Index: lq_route.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_route.c,v
retrieving revision 1.61
retrieving revision 1.62
diff -C2 -d -r1.61 -r1.62
*** lq_route.c 29 Nov 2007 00:49:38 -0000 1.61
--- lq_route.c 12 Dec 2007 21:57:27 -0000 1.62
***************
*** 42,46 ****
*/
! #define SPF_PROFILING 1
#include "ipcalc.h"
--- 42,46 ----
*/
! #define SPF_PROFILING 0
#include "ipcalc.h"
***************
*** 89,107 ****
static void
olsr_spf_add_cand_tree (struct avl_tree *tree,
! struct tc_entry *vert)
{
#if !defined(NODEBUG) && defined(DEBUG)
struct ipaddr_str buf;
#endif
! vert->cand_tree_node.key = &vert->path_etx;
! vert->cand_tree_node.data = vert;
#ifdef DEBUG
OLSR_PRINTF(1, "SPF: insert candidate %s, cost %f\n",
! olsr_ip_to_string(&buf, &vert->addr),
! vert->path_etx);
#endif
! avl_insert(tree, &vert->cand_tree_node, AVL_DUP);
}
--- 89,107 ----
static void
olsr_spf_add_cand_tree (struct avl_tree *tree,
! struct tc_entry *tc)
{
#if !defined(NODEBUG) && defined(DEBUG)
struct ipaddr_str buf;
#endif
! tc->cand_tree_node.key = &tc->path_etx;
! tc->cand_tree_node.data = tc;
#ifdef DEBUG
OLSR_PRINTF(1, "SPF: insert candidate %s, cost %f\n",
! olsr_ip_to_string(&buf, &tc->addr),
! tc->path_etx);
#endif
! avl_insert(tree, &tc->cand_tree_node, AVL_DUP);
}
***************
*** 113,117 ****
static void
olsr_spf_del_cand_tree (struct avl_tree *tree,
! struct tc_entry *vert)
{
--- 113,117 ----
static void
olsr_spf_del_cand_tree (struct avl_tree *tree,
! struct tc_entry *tc)
{
***************
*** 121,129 ****
#endif
OLSR_PRINTF(1, "SPF: delete candidate %s, cost %f\n",
! olsr_ip_to_string(&buf, &vert->addr),
! vert->path_etx);
#endif
! avl_delete(tree, &vert->cand_tree_node);
}
--- 121,129 ----
#endif
OLSR_PRINTF(1, "SPF: delete candidate %s, cost %f\n",
! olsr_ip_to_string(&buf, &tc->addr),
! tc->path_etx);
#endif
! avl_delete(tree, &tc->cand_tree_node);
}
***************
*** 134,154 ****
*/
static void
! olsr_spf_add_path_list (struct list_node *head,
! int *path_count,
! struct tc_entry *vert)
{
#if !defined(NODEBUG) && defined(DEBUG)
struct ipaddr_str pathbuf, nbuf;
#endif
! vert->path_list_node.data = vert;
#ifdef DEBUG
OLSR_PRINTF(1, "SPF: append path %s, cost %f, via %s\n",
! olsr_ip_to_string(&pathbuf, &vert->addr),
! vert->path_etx,
! vert->next_hop ? olsr_ip_to_string(&nbuf, &vert->next_hop->neighbor_iface_addr) : "-");
#endif
! list_add_before(head, &vert->path_list_node);
*path_count = *path_count + 1;
}
--- 134,153 ----
*/
static void
! olsr_spf_add_path_list (struct list_node *head, int *path_count,
! struct tc_entry *tc)
{
#if !defined(NODEBUG) && defined(DEBUG)
struct ipaddr_str pathbuf, nbuf;
#endif
! tc->path_list_node.data = tc;
#ifdef DEBUG
OLSR_PRINTF(1, "SPF: append path %s, cost %f, via %s\n",
! olsr_ip_to_string(&pathbuf, &tc->addr),
! tc->path_etx,
! tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "-");
#endif
! list_add_before(head, &tc->path_list_node);
*path_count = *path_count + 1;
}
***************
*** 188,192 ****
*/
static void
! olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *vert)
{
struct avl_node *edge_node;
--- 187,191 ----
*/
static void
! olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *tc)
{
struct avl_node *edge_node;
***************
*** 198,203 ****
#endif
OLSR_PRINTF(1, "SPF: exploring node %s, cost %f\n",
! olsr_ip_to_string(&buf, &vert->addr),
! vert->path_etx);
#endif
--- 197,202 ----
#endif
OLSR_PRINTF(1, "SPF: exploring node %s, cost %f\n",
! olsr_ip_to_string(&buf, &tc->addr),
! tc->path_etx);
#endif
***************
*** 205,212 ****
* loop through all edges of this vertex.
*/
! for (edge_node = avl_walk_first(&vert->edge_tree);
edge_node;
edge_node = avl_walk_next(edge_node)) {
! struct tc_entry *new_vert;
struct tc_edge_entry *tc_edge = edge_node->data;
--- 204,212 ----
* loop through all edges of this vertex.
*/
! for (edge_node = avl_walk_first(&tc->edge_tree);
edge_node;
edge_node = avl_walk_next(edge_node)) {
!
! struct tc_entry *new_tc;
struct tc_edge_entry *tc_edge = edge_node->data;
***************
*** 232,236 ****
* to the destination of this edge
*/
! new_etx = vert->path_etx + tc_edge->etx;
#ifdef DEBUG
--- 232,236 ----
* to the destination of this edge
*/
! new_etx = tc->path_etx + tc_edge->etx;
#ifdef DEBUG
***************
*** 244,273 ****
* destination node, then we've found a better path to this node.
*/
! new_vert = tc_edge->edge_inv->tc;
! if (new_etx < new_vert->path_etx) {
/* if this node has been on the candidate tree delete it */
! if (new_vert->path_etx != INFINITE_ETX) {
! olsr_spf_del_cand_tree(cand_tree, new_vert);
}
/* re-insert on candidate tree with the better metric */
! new_vert->path_etx = new_etx;
! olsr_spf_add_cand_tree(cand_tree, new_vert);
/* pull-up the next-hop and bump the hop count */
! if (vert->next_hop) {
! new_vert->next_hop = vert->next_hop;
}
! new_vert->hops = vert->hops + 1;
#ifdef DEBUG
OLSR_PRINTF(1, "SPF: better path to %s, cost %s -> %s, via %s, hops %u\n",
! olsr_ip_to_string(&buf, &new_vert->addr),
! olsr_etx_to_string(new_vert->path_etx),
olsr_etx_to_string(new_etx),
! vert->next_hop ? olsr_ip_to_string(&nbuf, &vert->next_hop->neighbor_iface_addr) : "<none>",
! new_vert->hops);
#endif
--- 244,273 ----
* destination node, then we've found a better path to this node.
*/
! new_tc = tc_edge->edge_inv->tc;
! if (new_etx < new_tc->path_etx) {
/* if this node has been on the candidate tree delete it */
! if (new_tc->path_etx != INFINITE_ETX) {
! olsr_spf_del_cand_tree(cand_tree, new_tc);
}
/* re-insert on candidate tree with the better metric */
! new_tc->path_etx = new_etx;
! olsr_spf_add_cand_tree(cand_tree, new_tc);
/* pull-up the next-hop and bump the hop count */
! if (tc->next_hop) {
! new_tc->next_hop = tc->next_hop;
}
! new_tc->hops = tc->hops + 1;
#ifdef DEBUG
OLSR_PRINTF(1, "SPF: better path to %s, cost %s -> %s, via %s, hops %u\n",
! olsr_ip_to_string(&buf, &new_tc->addr),
! olsr_etx_to_string(new_tc->path_etx),
olsr_etx_to_string(new_etx),
! tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "<none>",
! new_tc->hops);
#endif
***************
*** 292,302 ****
int *path_count)
{
! struct tc_entry *vert;
*path_count = 0;
! while ((vert = olsr_spf_extract_best(cand_tree))) {
! olsr_spf_relax(cand_tree, vert);
/*
--- 292,302 ----
int *path_count)
{
! struct tc_entry *tc;
*path_count = 0;
! while ((tc = olsr_spf_extract_best(cand_tree))) {
! olsr_spf_relax(cand_tree, tc);
/*
***************
*** 304,309 ****
* to the path list.
*/
! olsr_spf_del_cand_tree(cand_tree, vert);
! olsr_spf_add_path_list(path_list, path_count, vert);
}
}
--- 304,309 ----
* to the path list.
*/
! olsr_spf_del_cand_tree(cand_tree, tc);
! olsr_spf_add_path_list(path_list, path_count, tc);
}
}
***************
*** 312,326 ****
olsr_calculate_routing_table (void)
{
struct avl_tree cand_tree;
! struct list_node path_list;
int i, path_count = 0;
struct tc_entry *tc;
struct tc_edge_entry *tc_edge;
- struct tc_entry *vert;
struct neighbor_entry *neigh;
- struct mid_address *mid_walker;
- struct hna_entry *hna_gw;
- struct hna_net *hna;
- struct interface *inter;
struct link_entry *link;
--- 312,327 ----
olsr_calculate_routing_table (void)
{
+ #if !defined(NODEBUG) && defined(DEBUG)
+ struct ipaddr_str buf;
+ #endif
+
struct avl_tree cand_tree;
! struct avl_node *rtp_tree_node;
! struct list_node path_list; /* head of the path_list */
int i, path_count = 0;
struct tc_entry *tc;
+ struct rt_path *rtp;
struct tc_edge_entry *tc_edge;
struct neighbor_entry *neigh;
struct link_entry *link;
***************
*** 377,380 ****
--- 378,388 ----
}
+ /* find the interface for the link */
+ if (link->if_name) {
+ link->inter = if_ifwithname(link->if_name);
+ } else {
+ link->inter = if_ifwithaddr(&link->local_iface_addr);
+ }
+
/*
* Set the next-hops of our neighbors.
***************
*** 382,391 ****
if (!tc_edge) {
tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
! 0, link->last_htime,
link->loss_link_quality2,
link->neigh_link_quality2);
} else {
tc_edge->link_quality = link->loss_link_quality2;
tc_edge->inverse_link_quality = link->neigh_link_quality2;
olsr_calc_tc_edge_entry_etx(tc_edge);
}
--- 390,404 ----
if (!tc_edge) {
tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
! 0, link->vtime,
link->loss_link_quality2,
link->neigh_link_quality2);
} else {
+
+ /*
+ * Update LQ and timers, such that the edge does not get deleted.
+ */
tc_edge->link_quality = link->loss_link_quality2;
tc_edge->inverse_link_quality = link->neigh_link_quality2;
+ olsr_set_tc_edge_timer(tc_edge, link->vtime*1000);
olsr_calc_tc_edge_entry_etx(tc_edge);
}
***************
*** 416,477 ****
/*
! * In the path tree we have all the reachable nodes in our topology.
*/
for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
! vert = path_list.next->data;
! link = vert->next_hop;
if (!link) {
! #ifndef NODEBUG
! struct ipaddr_str buf;
! #endif
! OLSR_PRINTF(2, "%s no next-hop\n", olsr_ip_to_string(&buf, &vert->addr));
continue;
}
! /* find the interface for the found link */
! inter = link->if_name ? if_ifwithname(link->if_name)
! : if_ifwithaddr(&link->local_iface_addr);
!
! /* interface is up ? */
! if (inter) {
!
! /* add a route to the main address of the destination node */
! olsr_insert_routing_table(&vert->addr, olsr_cnf->maxplen, &vert->addr,
! &link->neighbor_iface_addr, inter->if_index,
! vert->hops, vert->path_etx);
! /* add routes to the remaining interfaces of the destination node */
! for (mid_walker = mid_lookup_aliases(&vert->addr);
! mid_walker != NULL;
! mid_walker = mid_walker->next_alias) {
! olsr_insert_routing_table(&mid_walker->alias, olsr_cnf->maxplen, &vert->addr,
! &link->neighbor_iface_addr, inter->if_index,
! vert->hops, vert->path_etx);
! }
! /* find the node's HNAs */
! hna_gw = olsr_lookup_hna_gw(&vert->addr);
! /* node doesn't announce any HNAs */
! if (!hna_gw) {
! continue;
! }
! /* loop through the node's HNAs */
! for (hna = hna_gw->networks.next;
! hna != &hna_gw->networks;
! hna = hna->next) {
! if (vert->path_etx != INFINITE_ETX) {
! olsr_insert_routing_table(&hna->A_network_addr, hna->prefixlen, &vert->addr,
! &link->neighbor_iface_addr, inter->if_index,
! vert->hops, vert->path_etx);
! }
}
}
}
#ifdef SPF_PROFILING
gettimeofday(&t4, NULL);
--- 429,485 ----
/*
! * In the path list we have all the reachable nodes in our topology.
*/
for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
! tc = path_list.next->data;
! link = tc->next_hop;
if (!link) {
!
! /*
! * Supress the error msg when our own tc_entry
! * does not contain a next-hop.
! */
! if (tc != tc_myself) {
! OLSR_PRINTF(1, "SPF: %s no next-hop\n", olsr_ip_to_string(&buf, &tc->addr));
! }
continue;
}
! /*
! * Now walk all prefixes advertised by that node.
! * Since the node is reachable, insert the prefix into the global RIB.
! * If the prefix is already in the RIB, refresh the entry such
! * that olsr_delete_outdated_routes() does not purge it off.
! */
! for (rtp_tree_node = avl_walk_first(&tc->prefix_tree);
! rtp_tree_node;
! rtp_tree_node = avl_walk_next(rtp_tree_node)) {
! rtp = rtp_tree_node->data;
! if (rtp->rtp_rt) {
! /*
! * If there is a route entry, the prefix is already in the global RIB.
! */
! olsr_update_rt_path(rtp, tc, link);
! } else {
! /*
! * The prefix is reachable and not yet in the global RIB.
! * Build a rt_entry for it.
! */
! olsr_insert_rt_path(rtp, tc, link);
}
}
}
+ /* Update the RIB based on the new SPF results */
+
+ olsr_update_rib_routes();
+
#ifdef SPF_PROFILING
gettimeofday(&t4, NULL);
Index: olsr_cfg.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/olsr_cfg.h,v
retrieving revision 1.42
retrieving revision 1.43
diff -C2 -d -r1.42 -r1.43
*** olsr_cfg.h 29 Nov 2007 22:21:26 -0000 1.42
--- olsr_cfg.h 12 Dec 2007 21:57:27 -0000 1.43
***************
*** 63,66 ****
--- 63,67 ----
#define DEF_IPC_CONNECTIONS 0
#define DEF_USE_HYST OLSR_FALSE
+ #define DEF_FLAT_FIB_METRIC OLSR_TRUE
#define DEF_LQ_LEVEL 2
#define DEF_LQ_FISH 0
***************
*** 194,197 ****
--- 195,199 ----
int ipc_connections;
olsr_bool use_hysteresis;
+ olsr_bool flat_fib_metric;
struct hyst_param hysteresis_param;
struct plugin_entry *plugins;
***************
*** 280,281 ****
--- 282,289 ----
#endif
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: tc_set.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/tc_set.c,v
retrieving revision 1.40
retrieving revision 1.41
diff -C2 -d -r1.40 -r1.41
*** tc_set.c 29 Nov 2007 22:59:51 -0000 1.40
--- tc_set.c 12 Dec 2007 21:57:27 -0000 1.41
***************
*** 124,129 ****
#endif
! /* The edgetree must be empty before */
! assert(!tc->edge_tree.count);
avl_delete(&tc_tree, &tc->vertex_node);
--- 124,134 ----
#endif
! /*
! * Delete the rt_path for ourselves.
! */
! olsr_delete_routing_table(&tc->addr, olsr_cnf->maxplen, &tc->addr);
!
! /* The edgetree and prefix tree must be empty before */
! assert(!tc->edge_tree.count && !tc->prefix_tree.count);
avl_delete(&tc_tree, &tc->vertex_node);
***************
*** 182,188 ****
olsr_add_tc_entry(union olsr_ip_addr *adr)
{
! struct tc_entry *tc;
! #if 0
struct ipaddr_str buf;
OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
#endif
--- 187,196 ----
olsr_add_tc_entry(union olsr_ip_addr *adr)
{
! #if !defined(NODEBUG) && defined(DEBUG)
struct ipaddr_str buf;
+ #endif
+ struct tc_entry *tc;
+
+ #ifdef DEBUG
OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
#endif
***************
*** 205,215 ****
/*
! * Initialize subtree for further edges to come.
*/
avl_init(&tc->edge_tree, avl_comp_default);
return tc;
}
/**
* format a tc_edge contents into a buffer
--- 213,244 ----
/*
! * Initialize subtrees for edges and prefixes.
*/
avl_init(&tc->edge_tree, avl_comp_default);
+ avl_init(&tc->prefix_tree, avl_comp_prefix_default);
+
+ /*
+ * Add a rt_path for ourselves.
+ */
+ olsr_insert_routing_table(adr, olsr_cnf->maxplen, adr,
+ OLSR_RT_ORIGIN_INT);
return tc;
}
+ /*
+ * Lookup a tc entry. Creates one if it does not exist yet.
+ */
+ struct tc_entry *
+ olsr_locate_tc_entry(union olsr_ip_addr *adr)
+ {
+ struct tc_entry *tc;
+
+ if (!(tc = olsr_lookup_tc_entry(adr))) {
+ return olsr_add_tc_entry(adr);
+ }
+ return tc;
+ }
+
/**
* format a tc_edge contents into a buffer
***************
*** 240,244 ****
* The timer param is a relative timer expressed in milliseconds.
*/
! static void
olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int timer)
{
--- 269,273 ----
* The timer param is a relative timer expressed in milliseconds.
*/
! void
olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int timer)
{
***************
*** 273,276 ****
--- 302,308 ----
float link_quality, float neigh_link_quality)
{
+ #if !defined(NODEBUG) && defined(DEBUG)
+ struct ipaddr_str buf;
+ #endif
struct tc_entry *tc_neighbor;
struct tc_edge_entry *tc_edge, *tc_edge_inv;
***************
*** 312,316 ****
tc_edge->tc = tc;
! #if 0
OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
#endif
--- 344,348 ----
tc_edge->tc = tc;
! #ifdef DEBUG
OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
#endif
***************
*** 322,335 ****
tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
if (tc_neighbor) {
! #if 0
OLSR_PRINTF(1, "TC: found neighbor tc_entry %s\n",
! olsr_ip_to_string(&tc_neighbor->addr));
#endif
tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
if (tc_edge_inv) {
! #if 0
OLSR_PRINTF(1, "TC: found inverse edge for %s\n",
! olsr_ip_to_string(&tc_edge_inv->T_dest_addr));
#endif
--- 354,367 ----
tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
if (tc_neighbor) {
! #ifdef DEBUG
OLSR_PRINTF(1, "TC: found neighbor tc_entry %s\n",
! olsr_ip_to_string(&buf, &tc_neighbor->addr));
#endif
tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
if (tc_edge_inv) {
! #ifdef DEBUG
OLSR_PRINTF(1, "TC: found inverse edge for %s\n",
! olsr_ip_to_string(&buf, &tc_edge_inv->T_dest_addr));
#endif
***************
*** 364,368 ****
struct tc_edge_entry *tc_edge_inv;
! #if 0
OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
#endif
--- 396,400 ----
struct tc_edge_entry *tc_edge_inv;
! #ifdef DEBUG
OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
#endif
***************
*** 380,386 ****
/*
! * Delete the tc_entry if the last edge is gone.
*/
! if (!tc_edge->tc->edge_tree.count) {
/*
--- 412,419 ----
/*
! * Delete the tc_entry if the last edge and last prefix is gone.
*/
! if (!tc_edge->tc->edge_tree.count &&
! !tc_edge->tc->prefix_tree.count) {
/*
***************
*** 546,550 ****
olsr_calc_tc_edge_entry_etx(tc_edge);
! #if 0
if (edge_change) {
OLSR_PRINTF(1, "TC: chg edge entry %s\n",
--- 579,583 ----
olsr_calc_tc_edge_entry_etx(tc_edge);
! #if DEBUG
if (edge_change) {
OLSR_PRINTF(1, "TC: chg edge entry %s\n",
Index: hna_set.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/hna_set.c,v
retrieving revision 1.29
retrieving revision 1.30
diff -C2 -d -r1.29 -r1.30
*** hna_set.c 2 Dec 2007 19:00:27 -0000 1.29
--- hna_set.c 12 Dec 2007 21:57:27 -0000 1.30
***************
*** 45,48 ****
--- 45,49 ----
#include "scheduler.h"
#include "net_olsr.h"
+ #include "tc_set.h"
***************
*** 107,113 ****
struct hna_entry *tmp_hna;
olsr_u32_t hash = olsr_hashing(gw);
-
- //OLSR_PRINTF(5, "TC: lookup entry\n");
/* Check for registered entry */
for(tmp_hna = hna_set[hash].next;
--- 108,116 ----
struct hna_entry *tmp_hna;
olsr_u32_t hash = olsr_hashing(gw);
+ #if 0
+ OLSR_PRINTF(5, "HNA: lookup entry\n");
+ #endif
+
/* Check for registered entry */
for(tmp_hna = hna_set[hash].next;
***************
*** 178,183 ****
/* Fill struct */
new_net->A_network_addr = *net;
- //memcpy(&new_net->A_netmask, mask, netmask_size);
new_net->prefixlen = prefixlen;
--- 181,186 ----
/* Fill struct */
+ memset(new_net, 0, sizeof(struct hna_net));
new_net->A_network_addr = *net;
new_net->prefixlen = prefixlen;
***************
*** 188,191 ****
--- 191,202 ----
new_net->prev = &hna_gw->networks;
+ /*
+ * Add the rt_path for the entry.
+ */
+ olsr_insert_routing_table(&new_net->A_network_addr,
+ new_net->prefixlen,
+ &hna_gw->A_gateway_addr,
+ OLSR_RT_ORIGIN_HNA);
+
return new_net;
}
***************
*** 260,263 ****
--- 271,281 ----
tmp_net = tmp_net->next;
DEQUEUE_ELEM(net_to_delete);
+
+ /*
+ * Delete the rt_path for the entry.
+ */
+ olsr_delete_routing_table(&net_to_delete->A_network_addr,
+ net_to_delete->prefixlen,
+ &tmp_hna->A_gateway_addr);
free(net_to_delete);
changes_hna = OLSR_TRUE;
Index: olsr.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/olsr.c,v
retrieving revision 1.65
retrieving revision 1.66
diff -C2 -d -r1.65 -r1.66
*** olsr.c 2 Dec 2007 19:00:27 -0000 1.65
--- olsr.c 12 Dec 2007 21:57:27 -0000 1.66
***************
*** 161,189 ****
}
! if (changes_neighborhood)
! {
! /* Calculate new mprs, HNA and routing table */
! if (olsr_cnf->lq_level < 1)
! {
! olsr_calculate_mpr();
! }
!
! else
! {
! olsr_calculate_lq_mpr();
! }
!
! olsr_calculate_routing_table();
! olsr_calculate_hna_routes();
! }
!
! else if (changes_topology || changes_hna)
! {
! /* calculate the routing table and HNA */
!
! olsr_calculate_routing_table();
! olsr_calculate_hna_routes();
}
if (olsr_cnf->debug_level > 0)
--- 161,176 ----
}
! if (changes_neighborhood) {
! if (olsr_cnf->lq_level < 1) {
! olsr_calculate_mpr();
! } else {
! olsr_calculate_lq_mpr();
}
+ }
+ /* calculate the routing table */
+ if (changes_neighborhood || changes_topology || changes_hna) {
+ olsr_calculate_routing_table();
+ }
if (olsr_cnf->debug_level > 0)
***************
*** 202,210 ****
}
}
!
olsr_print_link_set();
olsr_print_neighbor_table();
olsr_print_two_hop_neighbor_table();
olsr_print_tc_table();
}
--- 189,199 ----
}
}
!
! #if 1
olsr_print_link_set();
olsr_print_neighbor_table();
olsr_print_two_hop_neighbor_table();
olsr_print_tc_table();
+ #endif
}
***************
*** 609,610 ****
--- 598,605 ----
return 0;
}
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: routing_table.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/routing_table.c,v
retrieving revision 1.38
retrieving revision 1.39
diff -C2 -d -r1.38 -r1.39
*** routing_table.c 29 Nov 2007 22:59:51 -0000 1.38
--- routing_table.c 12 Dec 2007 21:57:27 -0000 1.39
***************
*** 56,60 ****
--- 56,66 ----
#include <assert.h>
+ /* Root of our RIB */
struct avl_tree routingtree;
+
+ /*
+ * Keep a version number for detecting outdated elements
+ * in the per rt_entry rt_path subtree.
+ */
unsigned int routingtree_version;
***************
*** 123,131 ****
avl_comp_ipv6_prefix (const void *prefix1, const void *prefix2)
{
const struct olsr_ip_prefix *pfx1 = prefix1;
const struct olsr_ip_prefix *pfx2 = prefix2;
/* prefix */
! int res = ip6cmp(&pfx1->prefix.v6, &pfx2->prefix.v6);
if (res != 0) {
return res;
--- 129,138 ----
avl_comp_ipv6_prefix (const void *prefix1, const void *prefix2)
{
+ int res;
const struct olsr_ip_prefix *pfx1 = prefix1;
const struct olsr_ip_prefix *pfx2 = prefix2;
/* prefix */
! res = memcmp(&pfx1->prefix.v6, &pfx2->prefix.v6, 16);
if (res != 0) {
return res;
***************
*** 176,186 ****
/**
! * Update the fields in an routing entry.
! * Depending on the update mask update either the old,
! * the new or both arrays for gateway/interface/etx/hopcount.
*/
! static void
! olsr_update_routing_entry(struct rt_path *rtp, union olsr_ip_addr *gateway,
! int iif_index, int metric, float etx)
{
--- 183,191 ----
/**
! * Update gateway/interface/etx/hopcount and the version for a route path.
*/
! void
! olsr_update_rt_path(struct rt_path *rtp, struct tc_entry *tc,
! struct link_entry *link)
{
***************
*** 188,205 ****
/* gateway */
! rtp->rtp_nexthop.gateway = *gateway;
/* interface */
! rtp->rtp_nexthop.iif_index = iif_index;
! /* etx */
! rtp->rtp_metric.hops = metric;
! if (etx < 0.0) {
! /* non-LQ case */
! rtp->rtp_metric.etx = (float)metric;
! } else {
! /* LQ case */
! rtp->rtp_metric.etx = etx;
! }
}
--- 193,204 ----
/* gateway */
! rtp->rtp_nexthop.gateway = link->neighbor_iface_addr;
/* interface */
! rtp->rtp_nexthop.iif_index = link->inter->if_index;
! /* metric/etx */
! rtp->rtp_metric.hops = tc->hops;
! rtp->rtp_metric.etx = tc->path_etx;
}
***************
*** 233,243 ****
}
-
/**
* Alloc and key a new rt_path.
*/
static struct rt_path *
! olsr_alloc_rt_path(struct rt_entry *rt,
! union olsr_ip_addr *originator)
{
struct rt_path *rtp = olsr_malloc(sizeof(struct rt_path), __FUNCTION__);
--- 232,241 ----
}
/**
* Alloc and key a new rt_path.
*/
static struct rt_path *
! olsr_alloc_rt_path(struct tc_entry *tc,
! struct olsr_ip_prefix *prefix, olsr_u8_t origin)
{
struct rt_path *rtp = olsr_malloc(sizeof(struct rt_path), __FUNCTION__);
***************
*** 249,263 ****
memset(rtp, 0, sizeof(*rtp));
! rtp->rtp_originator = *originator;
/* set key and backpointer prior to tree insertion */
! rtp->rtp_tree_node.key = &rtp->rtp_originator;
! rtp->rtp_tree_node.data = rtp;
! /* insert to the route entry originator tree */
! avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
! /* backlink to the owning route entry */
! rtp->rtp_rt = rt;
return rtp;
--- 247,264 ----
memset(rtp, 0, sizeof(*rtp));
! rtp->rtp_dst = *prefix;
/* set key and backpointer prior to tree insertion */
! rtp->rtp_prefix_tree_node.key = &rtp->rtp_dst;
! rtp->rtp_prefix_tree_node.data = rtp;
! /* insert to the tc prefix tree */
! avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, AVL_DUP_NO);
! /* backlink to the owning tc entry */
! rtp->rtp_tc = tc;
!
! /* store the origin of the route */
! rtp->rtp_origin = origin;
return rtp;
***************
*** 265,268 ****
--- 266,353 ----
/**
+ * Create a route entry for a given rt_path and
+ * insert it into the global RIB tree.
+ */
+ void
+ olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc,
+ struct link_entry *link)
+ {
+ struct rt_entry *rt;
+ struct avl_node *node;
+
+ /*
+ * no unreachable routes please.
+ */
+ if (tc->path_etx >= INFINITE_ETX) {
+ return;
+ }
+
+ /*
+ * No bogus prefix lengths.
+ */
+ if (rtp->rtp_dst.prefix_len > olsr_cnf->maxplen) {
+ return;
+ }
+
+ /*
+ * first check if there is a route_entry for the prefix.
+ */
+ node = avl_find(&routingtree, &rtp->rtp_dst);
+
+ if (!node) {
+
+ /* no route entry yet */
+ rt = olsr_alloc_rt_entry(&rtp->rtp_dst);
+
+ if (!rt) {
+ return;
+ }
+
+ /* Now insert the rt_path to the owning rt_entry tree */
+
+ rtp->rtp_originator = tc->addr;
+
+ /* set key and backpointer prior to tree insertion */
+ rtp->rtp_tree_node.key = &rtp->rtp_originator;
+ rtp->rtp_tree_node.data = rtp;
+
+ /* insert to the route entry originator tree */
+ avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
+
+ /* backlink to the owning route entry */
+ rtp->rtp_rt = rt;
+
+ } else {
+ rt = node->data;
+ }
+
+ /* update the version field and relevant parameters */
+ olsr_update_rt_path(rtp, tc, link);
+ }
+
+ /**
+ * Unlink and free a rt_path.
+ */
+ static void
+ olsr_free_rt_path(struct rt_path *rtp)
+ {
+
+ /* remove from the originator tree */
+ if (rtp->rtp_rt) {
+ avl_delete(&rtp->rtp_rt->rt_path_tree, &rtp->rtp_tree_node);
+ rtp->rtp_rt = NULL;
+ }
+
+ /* remove from the tc prefix tree */
+ if (rtp->rtp_tc) {
+ avl_delete(&rtp->rtp_tc->prefix_tree, &rtp->rtp_prefix_tree_node);
+ rtp->rtp_tc = NULL;
+ }
+
+ free(rtp);
+ }
+
+
+ /**
* Check if there is an interface or gateway change.
*/
***************
*** 278,281 ****
--- 363,391 ----
/**
+ * Check if there is a hopcount change.
+ */
+ olsr_bool
+ olsr_hopcount_change(const struct rt_metric *met1, const struct rt_metric *met2)
+ {
+ return (met1->hops != met2->hops);
+ }
+
+ /**
+ * Depending if flat_metric is configured and the kernel fib operation
+ * return the hopcount metric of a route.
+ * For adds this is the metric of best rour after olsr_rt_best() election,
+ * for deletes this is the metric of the route that got stored in the rt_entry,
+ * during route installation.
+ */
+ olsr_u8_t
+ olsr_fib_metric(const struct rt_metric *met)
+ {
+ if (!olsr_cnf->flat_fib_metric) {
+ return met->hops;
+ }
+ return RT_METRIC_DEFAULT;
+ }
+
+ /**
* depending on the operation (add/chg/del) the nexthop
* field from the route entry or best route path shall be used.
***************
*** 352,356 ****
/* walk all remaining originator entries */
! while ((node = avl_walk_next(node)) != NULL) {
struct rt_path *rtp = node->data;
--- 462,466 ----
/* walk all remaining originator entries */
! while ((node = avl_walk_next(node))) {
struct rt_path *rtp = node->data;
***************
*** 362,394 ****
/**
! * Insert/Update a route entry into the routing table.
! *
! * Check is the route exisits and depending if this is a
! * new version of the RIB do a full inplace update.
! * If there is already a route from this table version then
! * check if the new route is better.
*
! * For exisiting routes only interface or gateway router changes
! * do trigger a kernel change.
*
*@param dst the destination
*@param plen the prefix length
! *@param gateway the next-hop router
! *@param iface the next-hop interface
! *@param metric the hopcount
! *@param etx the LQ extension metric
*
! *@return the new rt_entry struct
*/
struct rt_path *
! olsr_insert_routing_table(union olsr_ip_addr *dst,
! int plen,
! union olsr_ip_addr *originator,
! union olsr_ip_addr *gateway,
! int iif_index,
! int metric,
! float etx)
{
! struct rt_entry *rt;
struct rt_path *rtp;
struct avl_node *node;
--- 472,496 ----
/**
! * Insert a prefix into the prefix tree hanging off a lsdb (tc) entry.
*
! * Check if the candidate route (we call this a rt_path) is known,
! * if not create it.
! * Upon post-SPF processing (if the node is reachable) the prefix
! * will be finally inserted into the global RIB.
*
*@param dst the destination
*@param plen the prefix length
! *@param originator the originating router
*
! *@return the new rt_path struct
*/
struct rt_path *
! olsr_insert_routing_table(union olsr_ip_addr *dst, int plen,
! union olsr_ip_addr *originator, int origin)
{
! #if !defined(NODEBUG) && defined(DEBUG)
! struct ipaddr_str buf;
! #endif
! struct tc_entry *tc;
struct rt_path *rtp;
struct avl_node *node;
***************
*** 396,455 ****
/*
! * no unreachable routes please.
*/
! if (etx >= INFINITE_ETX) {
return NULL;
}
/*
! * No bogus prefix lengths.
*/
! if (plen > olsr_cnf->maxplen) {
! return NULL;
! }
/*
! * first check if there is a route_entry for the prefix.
*/
prefix.prefix = *dst;
prefix.prefix_len = plen;
! node = avl_find(&routingtree, &prefix);
if (!node) {
! /* no route entry yet */
! rt = olsr_alloc_rt_entry(&prefix);
! if (!rt) {
return NULL;
}
} else {
! rt = node->data;
}
/*
! * next check if the route path from this originator is known
*/
! node = avl_find(&rt->rt_path_tree, originator);
! if (!node) {
! /* no route path from this originator yet */
! rtp = olsr_alloc_rt_path(rt, originator);
! if (!rtp) {
! return NULL;
! }
! } else {
! rtp = node->data;
! }
! /* update the version field and relevant parameters */
! olsr_update_routing_entry(rtp, gateway, iif_index, metric, etx);
! return rtp;
}
--- 498,595 ----
/*
! * No bogus prefix lengths.
*/
! if (plen > olsr_cnf->maxplen) {
return NULL;
}
+ OLSR_PRINTF(1, "RIB: add prefix %s/%u from %s\n",
+ olsr_ip_to_string(&buf, dst), plen,
+ olsr_ip_to_string(&buf, originator));
+
/*
! * For internal routes the tc_entry must already exist.
! * For all other routes we may create it as an edgeless
! * hookup point. If so he tc_entry has no edges it will not
! * be explored during SPF run.
*/
! tc = olsr_locate_tc_entry(originator);
/*
! * first check if there is a rt_path for the prefix.
*/
prefix.prefix = *dst;
prefix.prefix_len = plen;
! node = avl_find(&tc->prefix_tree, &prefix);
if (!node) {
! /* no rt_path for this prefix yet */
! rtp = olsr_alloc_rt_path(tc, &prefix, origin);
! if (!rtp) {
return NULL;
}
+ /* overload the hna change bit for flagging a prefix change */
+ changes_hna = OLSR_TRUE;
+
} else {
! rtp = node->data;
}
+ return rtp;
+ }
+
+ /**
+ * Delete a prefix from the prefix tree hanging off a lsdb (tc) entry.
+ */
+ void
+ olsr_delete_routing_table(union olsr_ip_addr *dst, int plen,
+ union olsr_ip_addr *originator)
+ {
+ #if !defined(NODEBUG) && defined(DEBUG)
+ struct ipaddr_str buf;
+ #endif
+
+ struct tc_entry *tc;
+ struct rt_path *rtp;
+ struct avl_node *node;
+ struct olsr_ip_prefix prefix;
+
/*
! * No bogus prefix lengths.
*/
! if (plen > olsr_cnf->maxplen) {
! return;
! }
! #ifdef DEBUG
! OLSR_PRINTF(1, "RIB: del prefix %s/%u from %s\n",
! olsr_ip_to_string(&buf, dst), plen,
! olsr_ip_to_string(&buf, originator));
! #endif
! tc = olsr_lookup_tc_entry(originator);
! if (!tc) {
! return;
! }
! /*
! * Grab the rt_path for the prefix.
! */
! prefix.prefix = *dst;
! prefix.prefix_len = plen;
! node = avl_find(&tc->prefix_tree, &prefix);
! if (node) {
! rtp = node->data;
! olsr_free_rt_path(rtp);
! /* overload the hna change bit for flagging a prefix change */
! changes_hna = OLSR_TRUE;
! }
}
***************
*** 497,540 ****
/**
- *Calculate the HNA routes
- *
- */
- void
- olsr_calculate_hna_routes(void)
- {
- int idx;
-
- #ifdef DEBUG
- OLSR_PRINTF(3, "Calculating HNA routes\n");
- #endif
-
- for (idx = 0; idx < HASHSIZE; idx++) {
- struct hna_entry *tmp_hna;
- /* All entries */
- for (tmp_hna = hna_set[idx].next; tmp_hna != &hna_set[idx]; tmp_hna = tmp_hna->next) {
- struct hna_net *tmp_net;
- /* All networks */
- for (tmp_net = tmp_hna->networks.next; tmp_net != &tmp_hna->networks; tmp_net = tmp_net->next) {
- /* If no route to gateway - skip */
- struct rt_entry *rt = olsr_lookup_routing_table(&tmp_hna->A_gateway_addr);
- if (rt != NULL) {
- /* update if better */
- olsr_insert_routing_table(&tmp_net->A_network_addr,
- tmp_net->prefixlen,
- &tmp_hna->A_gateway_addr,
- &rt->rt_best->rtp_nexthop.gateway,
- rt->rt_best->rtp_nexthop.iif_index,
- rt->rt_best->rtp_metric.hops,
- rt->rt_best->rtp_metric.etx);
- }
- }
- }
- }
-
- /* Update kernel */
- olsr_update_kernel_routes();
- }
-
- /**
* Print the routingtree to STDOUT
*
--- 637,640 ----
Index: process_routes.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/process_routes.h,v
retrieving revision 1.15
retrieving revision 1.16
diff -C2 -d -r1.15 -r1.16
*** process_routes.h 2 Dec 2007 19:00:28 -0000 1.15
--- process_routes.h 12 Dec 2007 21:57:27 -0000 1.16
***************
*** 53,67 ****
extern export_route_function olsr_delroute6_function;
! void
! olsr_init_export_route(void);
!
! void
! olsr_update_kernel_routes(void);
!
! void
! olsr_delete_all_kernel_routes(void);
!
! olsr_u8_t
! olsr_rt_flags(const struct rt_entry *);
#endif
--- 53,61 ----
extern export_route_function olsr_delroute6_function;
! void olsr_init_export_route(void);
! void olsr_update_rib_routes(void);
! void olsr_update_kernel_routes(void);
! void olsr_delete_all_kernel_routes(void);
! olsr_u8_t olsr_rt_flags(const struct rt_entry *);
#endif
Index: link_set.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/link_set.h,v
retrieving revision 1.36
retrieving revision 1.37
diff -C2 -d -r1.36 -r1.37
*** link_set.h 25 Nov 2007 22:08:57 -0000 1.36
--- link_set.h 12 Dec 2007 21:57:27 -0000 1.37
***************
*** 56,63 ****
--- 56,65 ----
union olsr_ip_addr local_iface_addr;
union olsr_ip_addr neighbor_iface_addr;
+ const struct interface *inter;
char *if_name;
clock_t SYM_time;
clock_t ASYM_time;
clock_t time;
+ unsigned int vtime;
struct neighbor_entry *neighbor;
olsr_u8_t prev_status;
***************
*** 155,156 ****
--- 157,164 ----
#endif
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: process_routes.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/process_routes.c,v
retrieving revision 1.42
retrieving revision 1.43
diff -C2 -d -r1.42 -r1.43
*** process_routes.c 2 Dec 2007 19:00:28 -0000 1.42
--- process_routes.c 12 Dec 2007 21:57:27 -0000 1.43
***************
*** 51,54 ****
--- 51,55 ----
#include "lq_avl.h"
#include "net_olsr.h"
+ #include "tc_set.h"
#ifdef WIN32
***************
*** 112,117 ****
*
* This is extremely simple - Just increment the version of the
! * tree and then olsr_update_kernel_routes() will see
! * all routes in the tree as outdated and flush it.
*
*@return 1
--- 113,118 ----
*
* This is extremely simple - Just increment the version of the
! * tree and then olsr_update_rib_routes() will see all routes in the tree
! * as outdated and olsr_update_kernel_routes() will finally flush it.
*
*@return 1
***************
*** 123,126 ****
--- 124,128 ----
olsr_bump_routingtree_version();
+ olsr_update_rib_routes();
olsr_update_kernel_routes();
}
***************
*** 199,204 ****
/* route addition has suceeded */
! /* save the nexthop in the route entry */
rt->rt_nexthop = rt->rt_best->rtp_nexthop;
}
}
--- 201,207 ----
/* route addition has suceeded */
! /* save the nexthop and metric in the route entry */
rt->rt_nexthop = rt->rt_best->rtp_nexthop;
+ rt->rt_metric = rt->rt_best->rtp_metric;
}
}
***************
*** 283,287 ****
/**
* Check the version number of all route paths hanging off a route entry.
! * If a route does not match the current routing tree number, delete it.
* Reset the best route pointer.
*/
--- 286,291 ----
/**
* Check the version number of all route paths hanging off a route entry.
! * If a route does not match the current routing tree number, remove it
! * from the global originator tree for that rt_entry.
* Reset the best route pointer.
*/
***************
*** 311,315 ****
/* remove from the originator tree */
avl_delete(&rt->rt_path_tree, rtp_tree_node);
! free(rtp);
}
}
--- 315,319 ----
/* remove from the originator tree */
avl_delete(&rt->rt_path_tree, rtp_tree_node);
! rtp->rtp_rt = NULL;
}
}
***************
*** 323,330 ****
* best path selection on the remaining set.
* Finally compare the nexthop of the route head and the best
! * path and enqueue a add/chg operation.
*/
void
! olsr_update_kernel_routes(void)
{
struct rt_entry *rt;
--- 327,334 ----
* best path selection on the remaining set.
* Finally compare the nexthop of the route head and the best
! * path and enqueue an add/chg operation.
*/
void
! olsr_update_rib_routes(void)
{
struct rt_entry *rt;
***************
*** 351,356 ****
olsr_rt_best(rt);
! /* nexthop change ? */
! if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop)) {
if (0 > rt->rt_nexthop.iif_index) {
--- 355,362 ----
olsr_rt_best(rt);
! /* nexthop or hopcount change ? */
! if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop) ||
! (!olsr_cnf->flat_fib_metric &&
! olsr_hopcount_change(&rt->rt_best->rtp_metric, &rt->rt_metric))) {
if (0 > rt->rt_nexthop.iif_index) {
***************
*** 365,368 ****
--- 371,382 ----
}
} OLSR_FOR_ALL_RT_ENTRIES_END(rt);
+ }
+
+ /**
+ * Propagate the accumulated changes from the last rib update to the kernel.
+ */
+ void
+ olsr_update_kernel_routes(void)
+ {
/* delete unreachable routes */
Index: routing_table.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/routing_table.h,v
retrieving revision 1.25
retrieving revision 1.26
diff -C2 -d -r1.25 -r1.26
*** routing_table.h 11 Nov 2007 23:10:24 -0000 1.25
--- routing_table.h 12 Dec 2007 21:57:27 -0000 1.26
***************
*** 46,49 ****
--- 46,50 ----
#include <net/route.h>
#include "hna_set.h"
+ #include "link_set.h"
#include "lq_avl.h"
#include "lq_list.h"
***************
*** 85,88 ****
--- 86,90 ----
struct rt_path *rt_best; /* shortcut to the best path */
struct rt_nexthop rt_nexthop; /* nexthop of FIB route */
+ struct rt_metric rt_metric; /* metric of FIB route */
struct avl_tree rt_path_tree;
struct list_node rt_change_node; /* queue for kernel FIB add/chg/del */
***************
*** 93,108 ****
* Depending on the results of the SPF calculation we perform a
* best_path calculation and pick the one with the lowest etx/metric.
*/
struct rt_path
{
struct rt_entry *rtp_rt; /* backpointer to owning route head */
struct rt_nexthop rtp_nexthop;
struct rt_metric rtp_metric;
union olsr_ip_addr rtp_originator; /* originator of the route */
! struct avl_node rtp_tree_node;
! olsr_u32_t rtp_version;
};
/*
* macro for traversing the entire routing table.
* it is recommended to use this because it hides all the internal
--- 95,134 ----
* Depending on the results of the SPF calculation we perform a
* best_path calculation and pick the one with the lowest etx/metric.
+ * The rt_path gets first inserted into the per tc_entry prefix tree.
+ * If during the SPF calculation the tc_entry becomes reachable via
+ * a local nexthop it is inserted into the global RIB tree.
*/
struct rt_path
{
struct rt_entry *rtp_rt; /* backpointer to owning route head */
+ struct tc_entry *rtp_tc; /* backpointer to owning tc entry */
struct rt_nexthop rtp_nexthop;
struct rt_metric rtp_metric;
+ struct avl_node rtp_tree_node; /* global rtp node */
union olsr_ip_addr rtp_originator; /* originator of the route */
! struct avl_node rtp_prefix_tree_node; /* tc entry rtp node */
! struct olsr_ip_prefix rtp_dst; /* the prefix */
! olsr_u32_t rtp_version; /* for detection of outdated rt_paths */
! olsr_u8_t rtp_origin; /* internal, MID or HNA */
! };
!
! /*
! * In olsrd we have three different route types.
! * Internal routes are generated by simple reachability
! * of a node (by means of a tc message reception).
! * MID routes result from MID messages and HNA routes
! * from a gw routers HNA anncouncements.
! */
! enum olsr_rt_origin {
! OLSR_RT_ORIGIN_MIN,
! OLSR_RT_ORIGIN_INT,
! OLSR_RT_ORIGIN_MID,
! OLSR_RT_ORIGIN_HNA,
! OLSR_RT_ORIGIN_MAX
};
/*
+ * OLSR_FOR_ALL_RT_ENTRIES
+ *
* macro for traversing the entire routing table.
* it is recommended to use this because it hides all the internal
***************
*** 121,124 ****
--- 147,174 ----
#define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
+ /*
+ * OLSR_FOR_ALL_HNA_RT_ENTRIES
+ *
+ * macro for traversing the entire routing table and pick only
+ * HNA routes. This is not optimal - however, If the RIBs become
+ * too big one day then we keep an additional per origin tree
+ * in order to speed up traversal.
+ * In the meantime it is recommended to use this macro because
+ * it hides all the internal datastructure from the callers
+ * and the core maintainers do not have to update all the plugins
+ * once we decide to change the datastructures.
+ */
+ #define OLSR_FOR_ALL_HNA_RT_ENTRIES(rt) \
+ { \
+ struct avl_node *rt_tree_node, *next_rt_tree_node; \
+ for (rt_tree_node = avl_walk_first(&routingtree); \
+ rt_tree_node; rt_tree_node = next_rt_tree_node) { \
+ next_rt_tree_node = avl_walk_next(rt_tree_node); \
+ rt = rt_tree_node->data; \
+ if (rt->rt_best->rtp_origin != OLSR_RT_ORIGIN_HNA) \
+ continue;
+ #define OLSR_FOR_ALL_HNA_RT_ENTRIES_END(rt) }}
+
+
/**
* IPv4 <-> IPv6 wrapper
***************
*** 155,161 ****
void olsr_rt_best(struct rt_entry *);
olsr_bool olsr_nh_change(const struct rt_nexthop *, const struct rt_nexthop *);
olsr_bool olsr_cmp_rt(const struct rt_entry *, const struct rt_entry *);
- void olsr_calculate_hna_routes(void);
char *olsr_rt_to_string(const struct rt_entry *);
char *olsr_rtp_to_string(const struct rt_path *);
--- 205,212 ----
void olsr_rt_best(struct rt_entry *);
olsr_bool olsr_nh_change(const struct rt_nexthop *, const struct rt_nexthop *);
+ olsr_bool olsr_hopcount_change(const struct rt_metric *, const struct rt_metric *);
olsr_bool olsr_cmp_rt(const struct rt_entry *, const struct rt_entry *);
+ olsr_u8_t olsr_fib_metric(const struct rt_metric *);
char *olsr_rt_to_string(const struct rt_entry *);
char *olsr_rtp_to_string(const struct rt_path *);
***************
*** 164,172 ****
const struct rt_nexthop * olsr_get_nh(const struct rt_entry *);
! struct rt_path *
! olsr_insert_routing_table(union olsr_ip_addr *, int,
! union olsr_ip_addr *,
! union olsr_ip_addr *,
! int, int, float);
struct rt_entry *
--- 215,223 ----
const struct rt_nexthop * olsr_get_nh(const struct rt_entry *);
! /* rt_path manipulation */
! struct rt_path *olsr_insert_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *, int);
! void olsr_delete_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *);
! void olsr_insert_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
! void olsr_update_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
struct rt_entry *
More information about the Olsr-cvs
mailing list