[Olsr-cvs] olsrd-current/src hna_set.c, 1.20, 1.21 hna_set.h, 1.14, 1.15 ipc_frontend.c, 1.33, 1.34 kernel_routes.h, 1.8, 1.9 lq_avl.c, 1.11, 1.12 lq_avl.h, 1.9, 1.10 lq_list.c, 1.5, 1.6 lq_list.h, 1.5, 1.6 lq_route.c, 1.48, 1.49 lq_route.h, 1.4, 1.5 main.c, 1.96, 1.97 net_olsr.c, 1.28, 1.29 net_olsr.h, 1.10, 1.11 olsr.c, 1.56, 1.57 olsr_types.h, 1.8, 1.9 process_routes.c, 1.34, 1.35 process_routes.h, 1.10, 1.11 routing_table.c, 1.28, 1.29 routing_table.h, 1.18, 1.19
Bernd Petrovitsch
(spam-protected)
Wed Sep 5 18:11:13 CEST 2007
Update of /cvsroot/olsrd/olsrd-current/src
In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv18959/src
Modified Files:
hna_set.c hna_set.h ipc_frontend.c kernel_routes.h lq_avl.c
lq_avl.h lq_list.c lq_list.h lq_route.c lq_route.h main.c
net_olsr.c net_olsr.h olsr.c olsr_types.h process_routes.c
process_routes.h routing_table.c routing_table.h
Log Message:
* applied rt-refactoring-6.diff from Hannes Gredler <(spam-protected)>
Index: lq_route.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_route.c,v
retrieving revision 1.48
retrieving revision 1.49
diff -C2 -d -r1.48 -r1.49
*** lq_route.c 2 Aug 2007 22:07:19 -0000 1.48
--- lq_route.c 5 Sep 2007 16:11:10 -0000 1.49
***************
*** 66,73 ****
struct avl_node tree_node; /* node keyed by ip address */
struct avl_node cand_tree_node; /* node keyed by etx */
! struct avl_node path_tree_node; /* node keyed by etx */
union olsr_ip_addr addr;
struct avl_tree edge_tree;
! union olsr_ip_addr *next_hop; /* the gateway router */
float path_etx;
olsr_u8_t hops;
--- 66,73 ----
struct avl_node tree_node; /* node keyed by ip address */
struct avl_node cand_tree_node; /* node keyed by etx */
! struct list_node path_list_node; /* SPF result list */
union olsr_ip_addr addr;
struct avl_tree edge_tree;
! struct link_entry *next_hop; /* the link to the 1st hop neighbor */
float path_etx;
olsr_u8_t hops;
***************
*** 138,160 ****
/*
! * olsr_spf_add_path_tree
*
! * Key an existing vertex to a path tree.
*/
static void
! olsr_spf_add_path_tree (struct avl_tree *tree,
struct olsr_spf_vertex *vert)
{
! vert->path_tree_node.key = &vert->path_etx;
! vert->path_tree_node.data = vert;
#ifdef DEBUG
! OLSR_PRINTF(1, "SPF: insert path %s, cost %f, via %s\n",
olsr_ip_to_string(&(vert->addr)),
vert->path_etx,
! olsr_ip_to_string(vert->next_hop));
#endif
! avl_insert(tree, &vert->path_tree_node, 1);
}
--- 138,161 ----
/*
! * olsr_spf_add_path_list
*
! * Insert an SPF result at the end of the path list.
*/
static void
! olsr_spf_add_path_list (struct list_node *head,
! int *path_count,
struct olsr_spf_vertex *vert)
{
! vert->path_list_node.data = vert;
#ifdef DEBUG
! OLSR_PRINTF(1, "SPF: append path %s, cost %f, via %s\n",
olsr_ip_to_string(&(vert->addr)),
vert->path_etx,
! olsr_ip_to_string(vert->next_hop ? &vert->next_hop->neighbor_iface_addr : NULL));
#endif
! list_add_before(head, &vert->path_list_node);
! *path_count = *path_count + 1;
}
***************
*** 198,202 ****
}
! static void
olsr_spf_add_edge (struct avl_tree *vertex_tree,
union olsr_ip_addr *src, union olsr_ip_addr *dst,
--- 199,203 ----
}
! static struct olsr_spf_vertex *
olsr_spf_add_edge (struct avl_tree *vertex_tree,
union olsr_ip_addr *src, union olsr_ip_addr *dst,
***************
*** 215,219 ****
if (node == NULL)
! return;
svert = node->data;
--- 216,220 ----
if (node == NULL)
! return NULL;
svert = node->data;
***************
*** 226,230 ****
if (node == NULL)
! return;
dvert = node->data;
--- 227,231 ----
if (node == NULL)
! return NULL;
dvert = node->data;
***************
*** 263,266 ****
--- 264,269 ----
avl_insert(&dvert->edge_tree, &edge->tree_node, 0);
}
+
+ return svert;
}
***************
*** 384,388 ****
olsr_etx_to_string(edge->dest->path_etx),
olsr_etx_to_string(new_etx),
! olsr_ip_to_string(vert->next_hop),
edge->dest->hops);
#endif
--- 387,392 ----
olsr_etx_to_string(edge->dest->path_etx),
olsr_etx_to_string(new_etx),
! olsr_ip_to_string(vert->next_hop ?
! &vert->next_hop->neighbor_iface_addr : NULL),
edge->dest->hops);
#endif
***************
*** 399,415 ****
* Run the Dijkstra algorithm.
*
- * We are using two trees: the candidate and the path tree.
* A node gets added to the candidate tree when one of its edges has
* an overall better root path cost than the node itself.
* The node with the shortest metric gets moved from the candidate to
! * the path tree every pass.
* The SPF computation is completed when there are no more nodes
* on the candidate tree.
*/
static void
! olsr_spf_run_full (struct avl_tree *cand_tree, struct avl_tree *path_tree)
{
struct olsr_spf_vertex *vert;
while ((vert = olsr_spf_extract_best(cand_tree))) {
--- 403,421 ----
* Run the Dijkstra algorithm.
*
* A node gets added to the candidate tree when one of its edges has
* an overall better root path cost than the node itself.
* The node with the shortest metric gets moved from the candidate to
! * the path list every pass.
* The SPF computation is completed when there are no more nodes
* on the candidate tree.
*/
static void
! olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
! int *path_count)
{
struct olsr_spf_vertex *vert;
+ *path_count = 0;
+
while ((vert = olsr_spf_extract_best(cand_tree))) {
***************
*** 418,434 ****
/*
* move the best path from the candidate tree
! * to the path tree.
*/
olsr_spf_del_cand_tree(cand_tree, vert);
! olsr_spf_add_path_tree(path_tree, vert);
}
}
void
! olsr_calculate_lq_routing_table (void)
{
! struct avl_tree vertex_tree, cand_tree, path_tree;
! struct avl_node *tree_node;
! int i;
struct tc_entry *tcsrc;
struct topo_dst *tcdst;
--- 424,440 ----
/*
* move the best path from the candidate tree
! * to the path list.
*/
olsr_spf_del_cand_tree(cand_tree, vert);
! olsr_spf_add_path_list(path_list, path_count, vert);
}
}
void
! olsr_calculate_routing_table (void)
{
! struct avl_tree vertex_tree, cand_tree;
! struct list_node path_list;
! int i, plen, max_host_plen, path_count = 0;
struct tc_entry *tcsrc;
struct topo_dst *tcdst;
***************
*** 439,451 ****
struct hna_entry *hna_gw;
struct hna_net *hna;
- struct rt_entry *gw_rt, *hna_rt, *head_rt;
struct neighbor_2_entry *neigh2;
- #if 0
- struct neighbor_list_entry *neigh_walker;
- #endif
struct interface *inter;
! if (olsr_cnf->ipsize != 4)
! avl_comp_default = avl_comp_ipv6;
// initialize the graph
--- 445,459 ----
struct hna_entry *hna_gw;
struct hna_net *hna;
struct neighbor_2_entry *neigh2;
struct interface *inter;
+ struct link_entry *link;
! #ifdef SPF_PROFILING
! struct timeval t1, t2, t3, t4, t5, t6, spf_init, spf_run, route, kernel, cleanup, total;
!
! gettimeofday(&t1, NULL);
! #endif
!
! max_host_plen = olsr_host_rt_maxplen();
// initialize the graph
***************
*** 453,457 ****
avl_init(&vertex_tree, avl_comp_default);
avl_init(&cand_tree, avl_comp_etx);
! avl_init(&path_tree, avl_comp_etx);
// add ourselves to the vertex and candidate tree
--- 461,467 ----
avl_init(&vertex_tree, avl_comp_default);
avl_init(&cand_tree, avl_comp_etx);
! list_head_init(&path_list);
!
! olsr_bump_routingtree_version();
// add ourselves to the vertex and candidate tree
***************
*** 466,488 ****
for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
neigh = neigh->next) {
- if (neigh->status == SYM) {
-
- vert = olsr_spf_add_vertex(&vertex_tree, &neigh->neighbor_main_addr,
- INFINITE_ETX);
! /*
! * Set the next-hop pointer to ourselves.
! * During olsr_spf_relax() the next_hop pointer will be
! * pulled up to the new candidate node.
! * At the End of the SPF computation every reachable node has
! * a pointer to its corresponding first hop router.
! */
! vert->next_hop = &vert->addr;
! /*
! * one hop neighbors are just one hop away.
! */
! vert->hops = 1;
! }
}
--- 476,484 ----
for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
neigh = neigh->next) {
! if (neigh->status != SYM)
! continue;
! olsr_spf_add_vertex(&vertex_tree, &neigh->neighbor_main_addr, INFINITE_ETX);
}
***************
*** 494,504 ****
neigh2 = neigh2->next) {
! vert = olsr_spf_add_vertex(&vertex_tree, &neigh2->neighbor_2_addr,
! INFINITE_ETX);
!
! /*
! * two hop neighbors are two hops away.
! */
! vert->hops = 2;
}
// add remaining vertices
--- 490,494 ----
neigh2 = neigh2->next) {
! olsr_spf_add_vertex(&vertex_tree, &neigh2->neighbor_2_addr, INFINITE_ETX);
}
// add remaining vertices
***************
*** 522,595 ****
for (i = 0; i < HASHSIZE; i++)
for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
! neigh = neigh->next)
! if (neigh->status == SYM)
! {
! struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
! if(!lnk)
continue;
! if (lnk->loss_link_quality2 >= MIN_LINK_QUALITY &&
! lnk->neigh_link_quality2 >= MIN_LINK_QUALITY)
! {
! etx = 1.0 / (lnk->loss_link_quality2 * lnk->neigh_link_quality2);
! olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr, &olsr_cnf->main_addr, etx);
! }
}
! // we now rely solely on TC messages for routes to our two-hop neighbours
! #if 0
! // add edges between our neighbours and our two-hop neighbours
! for (i = 0; i < HASHSIZE; i++)
! for (neigh2 = two_hop_neighbortable[i].next;
! neigh2 != &two_hop_neighbortable[i];
! neigh2 = neigh2->next)
! for (neigh_walker = neigh2->neighbor_2_nblist.next;
! neigh_walker != &neigh2->neighbor_2_nblist;
! neigh_walker = neigh_walker->next)
! {
! if (neigh_walker->second_hop_link_quality >=
! MIN_LINK_QUALITY * MIN_LINK_QUALITY)
! {
! neigh = neigh_walker->neighbor;
! etx = 1.0 / neigh_walker->second_hop_link_quality;
! olsr_spf_add_edge(&vertex_tree, &neigh2->neighbor_2_addr,
! &neigh->neighbor_main_addr, etx);
}
}
#endif
- // add remaining edges
-
- for (i = 0; i < HASHSIZE; i++)
- for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
- for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
- tcdst = tcdst->next)
- {
- if (tcdst->link_quality >= MIN_LINK_QUALITY &&
- tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
- {
- etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
-
- olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
- etx);
- }
- }
-
/*
* Run the SPF calculation.
*/
! olsr_spf_run_full(&cand_tree, &path_tree);
!
! // save the old routing table
!
! olsr_move_route_table(routingtable, old_routes);
OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
--- 512,573 ----
for (i = 0; i < HASHSIZE; i++)
for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
! neigh = neigh->next) {
! if (neigh->status == SYM) {
!
! link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
! if (!link) {
continue;
+ }
! if (olsr_cnf->lq_level < 2) {
! /* for non-lq the etx is always 1.0 */
! vert = olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr,
! &olsr_cnf->main_addr, 1.0 );
! vert->next_hop = link;
! } else if (link->loss_link_quality2 >= MIN_LINK_QUALITY &&
! link->neigh_link_quality2 >= MIN_LINK_QUALITY) {
!
! etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
!
! vert = olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr,
! &olsr_cnf->main_addr, etx);
! vert->next_hop = link;
! }
}
+ }
! /* add remaining edges from TC messages */
! for (i = 0; i < HASHSIZE; i++)
! for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
! for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
! tcdst = tcdst->next) {
! if (olsr_cnf->lq_level < 2) {
! /* for non-lq the etx is always 1.0 */
! olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr,
! &tcsrc->T_last_addr, 1.0);
! } else if (tcdst->link_quality >= MIN_LINK_QUALITY &&
! tcdst->inverse_link_quality >= MIN_LINK_QUALITY) {
! etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
!
! olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr,
! &tcsrc->T_last_addr, etx);
}
}
+ #ifdef SPF_PROFILING
+ gettimeofday(&t2, NULL);
#endif
/*
* Run the SPF calculation.
*/
! olsr_spf_run_full(&cand_tree, &path_list, &path_count);
OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
***************
*** 599,768 ****
(int)now.tv_usec/10000);
/*
! * In the path tree we have all the reachable nodes
! * in our topology sorted by etx metric.
*/
! for (tree_node = avl_walk_first(&path_tree);
! tree_node != NULL;
! tree_node = avl_walk_next(tree_node)) {
! struct link_entry *lnk;
! vert = tree_node->data;
! if (!vert->next_hop) {
OLSR_PRINTF(2, "%s no next-hop\n", olsr_ip_to_string(&vert->addr));
continue;
}
! // find the best link to the one-hop neighbour
!
! lnk = get_best_link_to_neighbor(vert->next_hop);
!
! // we may see NULL here, if the one-hop neighbour is not in the
! // link and neighbour sets any longer, but we have derived an edge
! // between us and the one-hop neighbour from the TC set
!
! if (lnk != NULL)
! {
! // find the interface for the found link
! inter = lnk->if_name ? if_ifwithname(lnk->if_name) :
! if_ifwithaddr(&lnk->local_iface_addr);
!
! // we may see NULL here if the interface is down, but we have
! // links that haven't timed out, yet
! if (inter != NULL)
! {
! // XXX - fix me: structurally prevent duplicates, don't test via
! // olsr_lookup_routing_table()
! // route addition, case A - add a route to the main address of the
! // destination node
! if (olsr_lookup_routing_table(&vert->addr) == NULL)
! olsr_insert_routing_table(&vert->addr, &lnk->neighbor_iface_addr,
! inter, vert->hops, vert->path_etx);
! // route addition, case B - 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)
! if (olsr_lookup_routing_table(&mid_walker->alias) == NULL)
! olsr_insert_routing_table(&mid_walker->alias,
! &lnk->neighbor_iface_addr, inter, vert->hops,
! vert->path_etx);
! // XXX - we used to use olsr_lookup_routing_table() only here, but
! // this assumed that case A or case B had already happened for
! // this destination; if case A or case B happened after case C
! // for the same destination, we had duplicates, as cases A and
! // B would not test whether case C had already happened
! // route addition, case C - make sure that we have a route to the
! // router - e.g. in case the router's not the main address and it's
! // MID entry has timed out
! if (olsr_lookup_routing_table(&lnk->neighbor_iface_addr) == NULL)
! olsr_insert_routing_table(&lnk->neighbor_iface_addr,
! &lnk->neighbor_iface_addr, inter, 1,
! vert->path_etx);
}
}
}
! // save the old HNA routing table
!
! olsr_move_route_table(hna_routes, old_hna);
!
! // add HNA routes
!
! /*
! * In the path tree we have all the reachable nodes
! * in our topology sorted by etx metric.
! */
! for (tree_node = avl_walk_first(&path_tree);
! tree_node;
! tree_node = avl_walk_next(tree_node)) {
!
! if (!(vert = tree_node->data)) {
! break;
! }
!
! // find the node's HNAs
!
! hna_gw = olsr_lookup_hna_gw(&vert->addr);
!
! // node doesn't announce any HNAs
!
! if (hna_gw == NULL)
! continue;
!
! // find route to the node
!
! gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
!
! // maybe we haven't found a link or an interface for the gateway above
! // and hence haven't added a route - skip the HNA in this case
!
! if (gw_rt == NULL)
! continue;
!
! // loop through the node's HNAs
!
! for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
! hna = hna->next)
! {
! // we already have a route via a previous (better) node
!
! if (olsr_lookup_hna_routing_table(&hna->A_network_addr) != NULL)
! continue;
!
! // create route for the HNA
!
! hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
!
! // set HNA IP address and netmask
!
! COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
! hna_rt->rt_mask = hna->A_netmask;
!
! // copy remaining fields from the node's route
!
! COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
! hna_rt->rt_metric = gw_rt->rt_metric;
! hna_rt->rt_etx = gw_rt->rt_etx;
! hna_rt->rt_if = gw_rt->rt_if;
!
! // we're not a host route
!
! hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
!
! // find the correct list
!
! head_rt = &hna_routes[olsr_hashing(&hna->A_network_addr)];
! // enqueue
! head_rt->next->prev = hna_rt;
! hna_rt->next = head_rt->next;
! head_rt->next = hna_rt;
! hna_rt->prev = head_rt;
! }
! }
! // free the graph
olsr_free_everything(&vertex_tree);
! // move the route changes into the kernel
!
! olsr_update_kernel_routes();
! olsr_update_kernel_hna_routes();
!
! // free the saved routing table
! olsr_free_routing_table(old_routes);
! olsr_free_routing_table(old_hna);
}
--- 577,673 ----
(int)now.tv_usec/10000);
+ #ifdef SPF_PROFILING
+ gettimeofday(&t3, NULL);
+ #endif
+
+ olsr_fill_routing_table_with_neighbors();
+
/*
! * 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) {
OLSR_PRINTF(2, "%s no next-hop\n", olsr_ip_to_string(&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, max_host_plen, &vert->addr,
! &link->neighbor_iface_addr, inter,
! 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, max_host_plen, &vert->addr,
! &link->neighbor_iface_addr, inter,
! 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) {
! plen = olsr_get_hna_prefix_len(hna);
! if (vert->path_etx != INFINITE_ETX)
! olsr_insert_routing_table(&hna->A_network_addr, plen, &vert->addr,
! &link->neighbor_iface_addr, inter,
! vert->hops, vert->path_etx);
}
}
}
! #ifdef SPF_PROFILING
! gettimeofday(&t4, NULL);
! #endif
! /* move the route changes into the kernel */
! olsr_update_kernel_routes();
! #ifdef SPF_PROFILING
! gettimeofday(&t5, NULL);
! #endif
! /* free the SPF graph */
olsr_free_everything(&vertex_tree);
! #ifdef SPF_PROFILING
! gettimeofday(&t6, NULL);
! timersub(&t2, &t1, &spf_init);
! timersub(&t3, &t2, &spf_run);
! timersub(&t4, &t3, &route);
! timersub(&t5, &t4, &kernel);
! timersub(&t6, &t5, &cleanup);
! timersub(&t6, &t1, &total);
! olsr_printf(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern/cleanup): %d, %d, %d, %d, %d, %d\n",
! path_count, routingtree.count,
! (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
! (int)route.tv_usec, (int)kernel.tv_usec, (int)cleanup.tv_usec);
! #endif
}
Index: kernel_routes.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/kernel_routes.h,v
retrieving revision 1.8
retrieving revision 1.9
diff -C2 -d -r1.8 -r1.9
*** kernel_routes.h 21 Nov 2004 11:28:56 -0000 1.8
--- kernel_routes.h 5 Sep 2007 16:11:10 -0000 1.9
***************
*** 51,64 ****
int
! olsr_ioctl_add_route(struct rt_entry *destination);
int
! olsr_ioctl_add_route6(struct rt_entry *destination);
int
! olsr_ioctl_del_route(struct rt_entry *destination);
int
! olsr_ioctl_del_route6(struct rt_entry *destination);
--- 51,64 ----
int
! olsr_ioctl_add_route(struct rt_entry *);
int
! olsr_ioctl_add_route6(struct rt_entry *);
int
! olsr_ioctl_del_route(struct rt_entry *);
int
! olsr_ioctl_del_route6(struct rt_entry *);
Index: lq_list.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_list.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** lq_list.h 10 Feb 2007 17:36:51 -0000 1.5
--- lq_list.h 5 Sep 2007 16:11:10 -0000 1.6
***************
*** 48,77 ****
struct list_node *next;
struct list_node *prev;
-
void *data;
};
! struct list
! {
! struct list_node *head;
! struct list_node *tail;
! };
!
! void list_init(struct list *list);
!
! #define list_get_head(node) ((node)->head)
! #define list_get_tail(node) ((node)->tail)
! #define list_get_next(node) ((node)->next)
! #define list_get_prev(node) ((node)->prev)
!
! void list_add_head(struct list *list, struct list_node *node);
! void list_add_tail(struct list *list, struct list_node *node);
! void list_add_before(struct list *list, struct list_node *pos_node,
! struct list_node *node);
! void list_add_after(struct list *list, struct list_node *pos_node,
! struct list_node *node);
! void list_remove(struct list *list, struct list_node *node);
#endif
--- 48,63 ----
struct list_node *next;
struct list_node *prev;
void *data;
};
! void list_head_init(struct list_node *);
! void list_node_init(struct list_node *);
! int list_node_on_list(struct list_node *);
! int list_is_empty(struct list_node *);
! void list_add_before(struct list_node *, struct list_node *);
! void list_add_after(struct list_node *, struct list_node *);
! void list_remove(struct list_node *);
#endif
Index: lq_avl.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_avl.h,v
retrieving revision 1.9
retrieving revision 1.10
diff -C2 -d -r1.9 -r1.10
*** lq_avl.h 5 Jul 2007 22:43:46 -0000 1.9
--- lq_avl.h 5 Sep 2007 16:11:10 -0000 1.10
***************
*** 60,66 ****
--- 60,72 ----
{
struct avl_node *root;
+ struct avl_node *first;
+ struct avl_node *last;
+ unsigned int count;
int (*comp)(void *, void *);
};
+ #define AVL_DUP 1
+ #define AVL_DUP_NO 0
+
void avl_init(struct avl_tree *, int (*)(void *, void *));
struct avl_node *avl_find(struct avl_tree *, void *);
***************
*** 73,76 ****
--- 79,83 ----
extern int (*avl_comp_default)(void *, void *);
+ extern int (*avl_comp_prefix_default)(void *, void *);
extern int avl_comp_ipv4(void *, void *);
extern int avl_comp_ipv6(void *, void *);
Index: net_olsr.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/net_olsr.h,v
retrieving revision 1.10
retrieving revision 1.11
diff -C2 -d -r1.10 -r1.11
*** net_olsr.h 20 Aug 2007 18:46:03 -0000 1.10
--- net_olsr.h 5 Sep 2007 16:11:11 -0000 1.11
***************
*** 91,94 ****
--- 91,97 ----
olsr_netmask_to_prefix(const union olsr_ip_addr *);
+ int
+ olsr_host_rt_maxplen(void);
+
char *
sockaddr_to_string(const struct sockaddr *);
Index: hna_set.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/hna_set.c,v
retrieving revision 1.20
retrieving revision 1.21
diff -C2 -d -r1.20 -r1.21
*** hna_set.c 2 Aug 2007 22:07:19 -0000 1.20
--- hna_set.c 5 Sep 2007 16:11:10 -0000 1.21
***************
*** 81,85 ****
}
!
--- 81,93 ----
}
! int
! olsr_get_hna_prefix_len(struct hna_net *hna)
! {
! if (olsr_cnf->ip_version == AF_INET) {
! return olsr_netmask_to_prefix((union olsr_ip_addr *)&hna->A_netmask.v4);
! } else {
! return hna->A_netmask.v6;
! }
! }
***************
*** 366,368 ****
}
!
--- 374,380 ----
}
! /*
! * Local Variables:
! * c-basic-offset: 2
! * End:
! */
Index: lq_list.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_list.c,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** lq_list.c 10 Feb 2007 17:36:51 -0000 1.5
--- lq_list.c 5 Sep 2007 16:11:10 -0000 1.6
***************
*** 44,123 ****
#include "lq_list.h"
! void list_init(struct list *list)
{
! list->head = NULL;
! list->tail = NULL;
}
! void list_add_head(struct list *list, struct list_node *node)
{
- if (list->head != NULL)
- list->head->prev = node;
-
- else
- list->tail = node;
-
node->prev = NULL;
! node->next = list->head;
!
! list->head = node;
}
! void list_add_tail(struct list *list, struct list_node *node)
{
! if (list->tail != NULL)
! list->tail->next = node;
!
! else
! list->head = node;
!
! node->prev = list->tail;
! node->next = NULL;
! list->tail = node;
}
! void list_add_before(struct list *list, struct list_node *pos_node,
! struct list_node *node)
{
! if (pos_node->prev != NULL)
! pos_node->prev->next = node;
!
! else
! list->head = node;
!
! node->prev = pos_node->prev;
! node->next = pos_node;
! pos_node->prev = node;
}
! void list_add_after(struct list *list, struct list_node *pos_node,
! struct list_node *node)
{
! if (pos_node->next != NULL)
! pos_node->next->prev = node;
!
! else
! list->tail = node;
!
! node->prev = pos_node;
! node->next = pos_node->next;
! pos_node->next = node;
}
! void list_remove(struct list *list, struct list_node *node)
{
! if (node == list->head)
! list->head = node->next;
! else
! node->prev->next = node->next;
! if (node == list->tail)
! list->tail = node->prev;
! else
! node->next->prev = node->prev;
}
--- 44,107 ----
#include "lq_list.h"
! /* init a circular list */
! void list_head_init(struct list_node *node)
{
! node->prev = node;
! node->next = node;
}
! void list_node_init(struct list_node *node)
{
node->prev = NULL;
! node->next = NULL;
}
! int list_node_on_list(struct list_node *node)
{
! if (node->prev || node->next) {
! return 1;
! }
! return 0;
}
! int list_is_empty(struct list_node *node)
{
! if (node->prev == node && node->next == node) {
! return 1;
! }
! return 0;
}
! void list_add_after(struct list_node *pos_node, struct list_node *new_node)
{
! new_node->next = pos_node->next;
! new_node->prev = pos_node;
! pos_node->next->prev = new_node;
! pos_node->next = new_node;
}
! void list_add_before(struct list_node *pos_node, struct list_node *new_node)
{
! new_node->prev = pos_node->prev;
! new_node->next = pos_node;
! pos_node->prev->next = new_node;
! pos_node->prev = new_node;
! }
! void list_remove(struct list_node *del_node)
! {
! del_node->next->prev = del_node->prev;
! del_node->prev->next = del_node->next;
! list_node_init(del_node);
}
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: lq_route.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_route.h,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** lq_route.h 5 Jul 2007 22:43:47 -0000 1.4
--- lq_route.h 5 Sep 2007 16:11:10 -0000 1.5
***************
*** 47,51 ****
#define MIN_LINK_QUALITY 0.01
! void olsr_calculate_lq_routing_table(void);
#endif
--- 47,51 ----
#define MIN_LINK_QUALITY 0.01
! void olsr_calculate_routing_table(void);
#endif
Index: net_olsr.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/net_olsr.c,v
retrieving revision 1.28
retrieving revision 1.29
diff -C2 -d -r1.28 -r1.29
*** net_olsr.c 28 Aug 2007 20:10:16 -0000 1.28
--- net_olsr.c 5 Sep 2007 16:11:11 -0000 1.29
***************
*** 500,507 ****
olsr_netmask_to_prefix(const union olsr_ip_addr *adr)
{
- int i;
olsr_u16_t prefix = 0;
! for (i = 0; i < 16; i++)
{
if(adr->v6.s6_addr[i] == 0xff)
--- 500,509 ----
olsr_netmask_to_prefix(const union olsr_ip_addr *adr)
{
olsr_u16_t prefix = 0;
+ unsigned int i;
! prefix = 0;
!
! for(i = 0; i < olsr_cnf->ipsize; i++)
{
if(adr->v6.s6_addr[i] == 0xff)
***************
*** 526,529 ****
--- 528,547 ----
}
+ /**
+ * olsr_host_rt_maxplen
+ *
+ * @return the maxium prefix length based wether v4 or v6 is configured
+ */
+ int
+ olsr_host_rt_maxplen(void)
+ {
+ if(olsr_cnf->ip_version == AF_INET) {
+ /* IPv4 */
+ return 32;
+ } else {
+ /* IPv6 */
+ return 128;
+ }
+ }
***************
*** 659,660 ****
--- 677,684 ----
return OLSR_TRUE;
}
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: olsr_types.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/olsr_types.h,v
retrieving revision 1.8
retrieving revision 1.9
diff -C2 -d -r1.8 -r1.9
*** olsr_types.h 28 Jun 2007 22:34:52 -0000 1.8
--- olsr_types.h 5 Sep 2007 16:11:11 -0000 1.9
***************
*** 99,102 ****
--- 99,108 ----
};
+ struct olsr_ip_prefix
+ {
+ union olsr_ip_addr prefix;
+ olsr_u8_t prefix_len;
+ };
+
union hna_netmask
{
Index: process_routes.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/process_routes.c,v
retrieving revision 1.34
retrieving revision 1.35
diff -C2 -d -r1.34 -r1.35
*** process_routes.c 2 Aug 2007 22:07:19 -0000 1.34
--- process_routes.c 5 Sep 2007 16:11:11 -0000 1.35
***************
*** 2,5 ****
--- 2,6 ----
* The olsr.org Optimized Link-State Routing daemon(olsrd)
* Copyright (c) 2004, Andreas Tønnesen((spam-protected))
+ * RIB implementation (c) 2007, Hannes Gredler ((spam-protected))
* All rights reserved.
*
***************
*** 48,51 ****
--- 49,53 ----
#include "kernel_routes.h"
#include <assert.h>
+ #include "lq_avl.h"
#ifdef WIN32
***************
*** 65,71 ****
static struct export_route_entry *del_routes;
! struct rt_entry old_routes[HASHSIZE];
! struct rt_entry old_hna[HASHSIZE];
void
--- 67,100 ----
static struct export_route_entry *del_routes;
+ struct list_node add_kernel_list;
+ struct list_node chg_kernel_list;
+ struct list_node del_kernel_list;
! /**
! *
! * Calculate the kernel route flags.
! * Called before enqueuing a change/delete operation
! *
! */
! olsr_u8_t
! olsr_rt_flags(struct rt_entry *rt)
! {
! struct rt_nexthop *nh;
! olsr_u8_t flags;
!
! flags = (RTF_UP);
!
! if (rt->rt_dst.prefix_len == olsr_host_rt_maxplen()) {
! flags |= RTF_HOST;
! }
!
! nh = olsr_get_nh(rt);
!
! if(!COMP_IP(&rt->rt_dst.prefix, &nh->gateway)) {
! flags |= RTF_GATEWAY;
! }
!
! return flags;
! }
void
***************
*** 158,162 ****
int
! olsr_export_add_route (struct rt_entry *e)
{
int retval = 0;
--- 187,191 ----
int
! olsr_export_add_route (struct rt_entry *rt)
{
int retval = 0;
***************
*** 165,169 ****
{
if (tmp->type == AF_INET)
! retval = tmp->function(e);
}
return retval;
--- 194,198 ----
{
if (tmp->type == AF_INET)
! retval = tmp->function(rt);
}
return retval;
***************
*** 171,175 ****
int
! olsr_export_add_route6 (struct rt_entry *e)
{
int retval = 0;
--- 200,204 ----
int
! olsr_export_add_route6 (struct rt_entry *rt)
{
int retval = 0;
***************
*** 178,182 ****
{
if (tmp->type == AF_INET6)
! retval = tmp->function(e);
}
return retval;
--- 207,211 ----
{
if (tmp->type == AF_INET6)
! retval = tmp->function(rt);
}
return retval;
***************
*** 184,188 ****
int
! olsr_export_del_route (struct rt_entry *e)
{
int retval = 0;
--- 213,217 ----
int
! olsr_export_del_route (struct rt_entry *rt)
{
int retval = 0;
***************
*** 191,195 ****
{
if (tmp->type == AF_INET)
! retval = tmp->function(e);
}
return retval;
--- 220,224 ----
{
if (tmp->type == AF_INET)
! retval = tmp->function(rt);
}
return retval;
***************
*** 197,201 ****
int
! olsr_export_del_route6 (struct rt_entry *e)
{
int retval = 0;
--- 226,230 ----
int
! olsr_export_del_route6 (struct rt_entry *rt)
{
int retval = 0;
***************
*** 204,623 ****
{
if (tmp->type == AF_INET6)
! retval = tmp->function(e);
}
return retval;
}
-
-
- int
- olsr_init_old_table(void)
- {
- int idx;
-
- for(idx=0;idx<HASHSIZE;idx++)
- {
- old_routes[idx].next = &old_routes[idx];
- old_routes[idx].prev = &old_routes[idx];
- old_hna[idx].next = &old_hna[idx];
- old_hna[idx].prev = &old_hna[idx];
- }
-
- return 1;
- }
-
/**
! *Checks if there exists a route to a given host
! *in a given hash table.
*
! *@param dst the host to check for
! *@param table the table to check
*
! *@return 1 if the host exists in the table, 0 if not
*/
int
! olsr_find_up_route(struct rt_entry *dst, struct rt_entry *table)
{
! struct rt_entry *destination;
! const olsr_u32_t hash = olsr_hashing(&dst->rt_dst);
! for(destination = table[hash].next; destination != &table[hash]; destination = destination->next)
! {
! //printf("Checking %s hc: %d ", olsr_ip_to_string(&dst->rt_dst), dst->rt_metric);
! //printf("vs %s hc: %d ... ", olsr_ip_to_string(&destination->rt_dst), destination->rt_metric);
! if (COMP_IP(&destination->rt_dst, &dst->rt_dst) &&
! COMP_IP(&destination->rt_router, &dst->rt_router) &&
! (destination->rt_if->if_index == dst->rt_if->if_index))
! {
! if(destination->rt_metric == dst->rt_metric)
! {
! return 1;
! }
! else
! {
! return 0;
! }
! }
! }
! return 0;
! }
/**
! *Create a list containing the entries in from_table
! *that do not exist in in_table
! *
! *@param from_table the table to use
! *@param in_table the routes already added
! *
! *@return a poiter to a linked list of routes to add
*/
! struct destination_n *
! olsr_build_update_list(struct rt_entry *from_table,struct rt_entry *in_table)
{
! struct destination_n *kernel_route_list = NULL;
! struct rt_entry *destination;
! int idx;
!
! for(idx=0;idx<HASHSIZE;idx++)
! {
! for(destination = from_table[idx].next;
! destination != &from_table[idx];
! destination = destination->next)
! {
! if (!olsr_find_up_route(destination, in_table))
! {
! struct destination_n *route_list;
! route_list = olsr_malloc(sizeof(struct destination_n), "create route tmp list");
!
! route_list->destination = destination;
!
! route_list->next = kernel_route_list;
! kernel_route_list = route_list;
! }
! }
! }
!
! return (kernel_route_list);
! }
/**
! *Deletes all OLSR routes
! *
*
! *@return 1
*/
! int
! olsr_delete_all_kernel_routes(void)
! {
! struct destination_n *delete_kernel_list;
! struct destination_n *tmp;
!
! OLSR_PRINTF(1, "Deleting all routes...\n");
! delete_kernel_list = olsr_build_update_list(hna_routes, old_hna);
! OLSR_PRINTF(1, "HNA list:\n");
! for(tmp = delete_kernel_list;tmp;tmp = tmp->next)
! {
! union olsr_ip_addr *tmp_addr = &tmp->destination->rt_dst;
! OLSR_PRINTF(1, "Dest: %s\n", olsr_ip_to_string(tmp_addr));
}
! olsr_delete_routes_from_kernel(delete_kernel_list);
! delete_kernel_list = olsr_build_update_list(routingtable,old_routes);
- OLSR_PRINTF(1, "Route list:\n");
- for(tmp = delete_kernel_list;tmp;tmp = tmp->next)
- {
- union olsr_ip_addr *tmp_addr = &tmp->destination->rt_dst;
- OLSR_PRINTF(1, "Dest: %s\n", olsr_ip_to_string(tmp_addr));
}
! olsr_delete_routes_from_kernel(delete_kernel_list);
! return 1;
}
-
/**
! *Perform all neccessary actions for an update of the
! *routes in the kernel.
*
*@return nada
*/
! void
! olsr_update_kernel_routes(void)
{
! struct destination_n *delete_kernel_list;
! struct destination_n *add_kernel_list;
! OLSR_PRINTF(3, "Updating kernel routes...\n");
! delete_kernel_list = olsr_build_update_list(old_routes, routingtable);
! add_kernel_list = olsr_build_update_list(routingtable, old_routes);
! olsr_delete_routes_from_kernel(delete_kernel_list);
! olsr_add_routes_in_kernel(add_kernel_list);
! }
/**
! *Perform all neccessary actions for an update of the
! *HNA routes in the kernel.
! *
! *@return nada
*/
! void
! olsr_update_kernel_hna_routes(void)
{
! struct destination_n *delete_kernel_list;
! struct destination_n *add_kernel_list;
! OLSR_PRINTF(3, "Updating kernel HNA routes...\n");
! delete_kernel_list = olsr_build_update_list(old_hna, hna_routes);
! add_kernel_list = olsr_build_update_list(hna_routes, old_hna);
! olsr_delete_routes_from_kernel(delete_kernel_list);
! olsr_add_routes_in_kernel(add_kernel_list);
}
-
/**
! *Create a copy of the routing table and
! *clear the current table
! *
! *@param original the table to move from
! *@param the table to move to
! *
! *@return nada
*/
! void
! olsr_move_route_table(struct rt_entry *original, struct rt_entry *new)
{
! int idx;
! for(idx=0;idx<HASHSIZE;idx++)
! {
! if(original[idx].next == &original[idx])
! {
! new[idx].next = &new[idx];
! new[idx].prev = &new[idx];
! }
! else
! {
! /* Copy to old */
! new[idx].next = original[idx].next;
! new[idx].next->prev = &new[idx];
! new[idx].prev = original[idx].prev;
! new[idx].prev->next = &new[idx];
! /* Clear original */
! original[idx].next = &original[idx];
! original[idx].prev = &original[idx];
! }
! }
! }
/**
! *Delete a linked list of routes from the kernel.
! *
! *@param delete_kernel_list the list to delete
! *
! *@return nada
*/
! void
! olsr_delete_routes_from_kernel(struct destination_n *delete_kernel_list)
{
! struct destination_n *destination_ptr;
! int metric_counter = 1;
! olsr_bool last_run = OLSR_FALSE;
! /* Find highest metric */
! for(destination_ptr = delete_kernel_list;
! destination_ptr != NULL;
! destination_ptr = destination_ptr->next)
! {
! if(destination_ptr->destination->rt_metric > metric_counter)
! metric_counter = destination_ptr->destination->rt_metric;
! }
! #ifdef DEBUG
! OLSR_PRINTF(3, "%s highest metric %d\n",
! __func__, metric_counter);
! #endif
!
! while(delete_kernel_list!=NULL)
! {
! struct destination_n *previous_node = delete_kernel_list;
! assert(metric_counter);
! /* searching for all the items with metric equal to n */
! for(destination_ptr = delete_kernel_list; destination_ptr != NULL; )
! {
! if(destination_ptr->destination->rt_metric == metric_counter)
! {
! /* Make sure one-hop direct neighbors are deleted last */
! if(metric_counter == 1 &&
! (!last_run &&
! COMP_IP(&destination_ptr->destination->rt_dst,
! &destination_ptr->destination->rt_router)))
! {
! previous_node = destination_ptr;
! destination_ptr = destination_ptr->next;
! }
! else
! {
! olsr_16_t error;
! #ifdef DEBUG
! OLSR_PRINTF(3, "Deleting route to %s hopcount %d\n",
! olsr_ip_to_string(&destination_ptr->destination->rt_dst),
! destination_ptr->destination->rt_metric);
! #endif
! if(!olsr_cnf->host_emul)
! {
! if(olsr_cnf->ip_version == AF_INET)
! error = olsr_export_del_route(destination_ptr->destination);
! else
! error = olsr_export_del_route6(destination_ptr->destination);
!
! if(error < 0)
! {
! const char * const err_msg = strerror(errno);
! OLSR_PRINTF(1, "Delete route(%s):%s\n", olsr_ip_to_string(&destination_ptr->destination->rt_dst), err_msg);
! olsr_syslog(OLSR_LOG_ERR, "Delete route:%s", err_msg);
! }
! }
!
! /* Getting rid of this node and hooking up the broken point */
! if(destination_ptr == delete_kernel_list)
! {
! destination_ptr = delete_kernel_list->next;
! free(delete_kernel_list);
! delete_kernel_list = destination_ptr;
! previous_node = delete_kernel_list;
! }
! else
! {
! previous_node->next = destination_ptr->next;
! free(destination_ptr);
! destination_ptr = previous_node->next;
! }
! }
! }
! else
! {
! previous_node = destination_ptr;
! destination_ptr = destination_ptr->next;
! }
!
! }
! if((metric_counter == 1) && !last_run)
! {
! last_run = OLSR_TRUE;
! }
! else
! {
! metric_counter--;
! }
}
!
}
/**
! *Add a list of routes to the kernel. Adding
! *is done by hopcount to be sure a route
! *to the nexthop is added.
! *
! *@param add_kernel_list the linked list of routes to add
! *
! *@return nada
*/
! void
! olsr_add_routes_in_kernel(struct destination_n *add_kernel_list)
{
! int metric_counter = 1;
! olsr_bool first_run = OLSR_TRUE;
!
! while(add_kernel_list != NULL)
! {
! struct destination_n *destination_kernel = NULL;
! struct destination_n *previous_node = add_kernel_list;
! /* searching for all the items with metric equal to n */
! for(destination_kernel = add_kernel_list; destination_kernel != NULL; )
! {
! if((destination_kernel->destination->rt_metric == metric_counter) &&
! (!first_run ||
! COMP_IP(&destination_kernel->destination->rt_dst,
! &destination_kernel->destination->rt_router)))
! {
! olsr_16_t error;
! /* First add all 1-hop routes that has themselves as GW */
! #ifdef DEBUG
! OLSR_PRINTF(3, "Adding route to %s hopcount %d\n",
! olsr_ip_to_string(&destination_kernel->destination->rt_dst),
! destination_kernel->destination->rt_metric);
! #endif
!
! if(!olsr_cnf->host_emul)
! {
! if(olsr_cnf->ip_version == AF_INET)
! error=olsr_export_add_route(destination_kernel->destination);
! else
! error=olsr_export_add_route6(destination_kernel->destination);
!
! if(error < 0)
! {
! const char * const err_msg = strerror(errno);
! OLSR_PRINTF(1, "Add route(%s): %s\n", olsr_ip_to_string(&destination_kernel->destination->rt_dst), err_msg);
! olsr_syslog(OLSR_LOG_ERR, "Add route:%s", err_msg);
! }
! }
!
! /* Getting rid of this node and hooking up the broken point */
! if(destination_kernel == add_kernel_list)
! {
! destination_kernel = add_kernel_list->next;
! free(add_kernel_list);
! add_kernel_list = destination_kernel;
! previous_node=add_kernel_list;
! }
! else
! {
! previous_node->next = destination_kernel->next;
! free(destination_kernel);
! destination_kernel = previous_node->next;
! }
! }
! else
! {
! previous_node = destination_kernel;
! destination_kernel = destination_kernel->next;
! }
!
! }
! if(first_run)
! {
! first_run = OLSR_FALSE;
! }
! else
! {
! metric_counter++;
! }
}
-
- }
--- 233,540 ----
{
if (tmp->type == AF_INET6)
! retval = tmp->function(rt);
}
return retval;
}
/**
! *Deletes all OLSR routes
*
! * 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
*/
int
! olsr_delete_all_kernel_routes(void)
{
! OLSR_PRINTF(1, "Deleting all routes...\n");
! olsr_bump_routingtree_version();
! olsr_update_kernel_routes();
+ return 1;
+ }
/**
! * Enqueue a route on a kernel add/chg/del queue.
*/
! static void
! olsr_enqueue_rt(struct list_node *head_node, struct rt_entry *rt)
{
! struct rt_nexthop *nh;
+ /* if this node is already on some changelist we are done */
+ if (list_node_on_list(&rt->rt_change_node)) {
+ return;
+ }
+ rt->rt_change_node.data = rt;
+ /*
+ * For easier route dependency tracking we enqueue nexthop routes
+ * at the head of the queue and non-nexthop routes at the tail of the queue.
+ */
+ nh = olsr_get_nh(rt);
+ if (COMP_IP(&rt->rt_dst.prefix, &nh->gateway)) {
+ list_add_after(head_node, &rt->rt_change_node);
+ } else {
+ list_add_before(head_node, &rt->rt_change_node);
+ }
+ }
/**
! * Process a route from the kernel deletion list.
*
! *@return nada
*/
! static void
! olsr_delete_kernel_route(struct rt_entry *rt)
! {
! olsr_16_t error;
! if(!olsr_cnf->host_emul) {
! if(olsr_cnf->ip_version == AF_INET) {
! error = olsr_export_del_route(rt);
! } else {
! error = olsr_export_del_route6(rt);
}
! if(error < 0) {
! const char * const err_msg = strerror(errno);
! OLSR_PRINTF(1, "KERN: ERROR deleting %s: %s\n",
! olsr_rt_to_string(rt), err_msg);
!
! olsr_syslog(OLSR_LOG_ERR, "Delete route: %s", err_msg);
}
! }
}
/**
! * Process a route from the kernel addition list.
*
*@return nada
*/
! static void
! olsr_add_kernel_route(struct rt_entry *rt)
{
! olsr_16_t error;
! if(!olsr_cnf->host_emul) {
! if(olsr_cnf->ip_version == AF_INET) {
! error = olsr_export_add_route(rt);
! } else {
! error = olsr_export_add_route6(rt);
! }
!
! if(error < 0) {
! const char * const err_msg = strerror(errno);
! OLSR_PRINTF(1, "KERN: ERROR adding %s: %s\n",
! olsr_rtp_to_string(rt->rt_best), err_msg);
+ olsr_syslog(OLSR_LOG_ERR, "Add route: %s", err_msg);
+ } else {
+
+ /* route addition has suceeded */
+ /* save the nexthop in the route entry */
+ rt->rt_nexthop = rt->rt_best->rtp_nexthop;
+ }
+ }
+ }
/**
! * process the kernel add list.
! * the routes are already ordered such that nexthop routes
! * are on the head of the queue.
! * nexthop routes need to be added first and therefore
! * the queue needs to be traversed from head to tail.
*/
! static void
! olsr_add_kernel_routes(struct list_node *head_node)
{
! struct rt_entry *rt;
! while (!list_is_empty(head_node)) {
! rt = head_node->next->data;
! olsr_add_kernel_route(rt);
! list_remove(&rt->rt_change_node);
! }
}
/**
! * process the kernel change list.
! * the routes are already ordered such that nexthop routes
! * are on the head of the queue.
! * non-nexthop routes need to be changed first and therefore
! * the queue needs to be traversed from tail to head.
*/
! static void
! olsr_chg_kernel_routes(struct list_node *head_node)
{
! struct rt_entry *rt;
! struct list_node *node;
! if (list_is_empty(head_node)) {
! return;
! }
! /*
! * First pass.
! * traverse from the end to the beginning of the list,
! * such that nexthop routes are deleted last.
! */
! for (node = head_node->prev; head_node != node; node = node->prev) {
!
! rt = node->data;
! olsr_delete_kernel_route(rt);
! }
+ /*
+ * Second pass.
+ * Traverse from the beginning to the end of the list,
+ * such that nexthop routes are added first.
+ */
+ while (!list_is_empty(head_node)) {
+
+ rt = head_node->next->data;
+ olsr_add_kernel_route(rt);
+
+ list_remove(&rt->rt_change_node);
+ }
+ }
/**
! * process the kernel delete list.
! * the routes are already ordered such that nexthop routes
! * are on the head of the queue.
! * non-nexthop routes need to be deleted first and therefore
! * the queue needs to be traversed from tail to head.
*/
! static void
! olsr_del_kernel_routes(struct list_node *head_node)
{
! struct rt_entry *rt;
+ while (!list_is_empty(head_node)) {
! rt = head_node->prev->data;
! olsr_delete_kernel_route(rt);
! list_remove(&rt->rt_change_node);
! free(rt);
! }
! }
! /**
! * 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.
! */
! static void
! olsr_delete_outdated_routes(struct rt_entry *rt)
! {
! struct rt_path *rtp;
! struct avl_node *rtp_tree_node, *next_rtp_tree_node;
! for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
! rtp_tree_node;
! rtp_tree_node = next_rtp_tree_node) {
! /*
! * pre-fetch the next node before loosing context.
! */
! next_rtp_tree_node = avl_walk_next(rtp_tree_node);
!
! rtp = rtp_tree_node->data;
!
! /*
! * check the version number which gets incremented on every SPF run.
! * comparing for unequalness avoids handling version number wraps.
! */
! if (routingtree_version != rtp->rtp_version) {
!
! /* remove from the originator tree */
! avl_delete(&rt->rt_path_tree, rtp_tree_node);
! free(rtp);
}
! }
!
! /* safety measure against dangling pointers */
! rt->rt_best = NULL;
}
/**
! * Walk all the routes, remove outdated routes and run
! * 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;
! OLSR_PRINTF(3, "Updating kernel routes...\n");
! /* walk all routes in the RIB. */
! OLSR_FOR_ALL_RT_ENTRIES(rt) {
!
! /* eliminate first unused routes */
! olsr_delete_outdated_routes(rt);
!
! if (!rt->rt_path_tree.count) {
!
! /* oops, all routes are gone - flush the route head */
! avl_delete(&routingtree, rt_tree_node);
!
! olsr_enqueue_rt(&del_kernel_list, rt);
! continue;
}
+ /* run best route election */
+ olsr_rt_best(rt);
+
+ /* nexthop change ? */
+ if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop)) {
+
+ if (!rt->rt_nexthop.iface) {
+
+ /* fresh routes do have NULL pointers in the nexthop fields. */
+ olsr_enqueue_rt(&add_kernel_list, rt);
+ } else {
+
+ /* this is a route change. */
+ olsr_enqueue_rt(&chg_kernel_list, rt);
+ }
+ }
+ } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
+
+ /* delete unreachable routes */
+ olsr_del_kernel_routes(&del_kernel_list);
+
+ /* route changes */
+ olsr_chg_kernel_routes(&chg_kernel_list);
+ /* route additions */
+ olsr_add_kernel_routes(&add_kernel_list);
+ #if DEBUG
+ olsr_print_routing_table(&routingtree);
+ #endif
+ }
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: ipc_frontend.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/ipc_frontend.c,v
retrieving revision 1.33
retrieving revision 1.34
diff -C2 -d -r1.33 -r1.34
*** ipc_frontend.c 2 Aug 2007 22:07:19 -0000 1.33
--- ipc_frontend.c 5 Sep 2007 16:11:10 -0000 1.34
***************
*** 271,280 ****
*/
int
! ipc_route_send_rtentry(union olsr_ip_addr *dst, union olsr_ip_addr *gw, int met, int add, char *int_name)
{
struct ipcmsg packet;
- //int i, x;
char *tmp;
if(!ipc_active)
return 0;
--- 271,284 ----
*/
int
! ipc_route_send_rtentry(union olsr_ip_addr *dst, union olsr_ip_addr *gw,
! int met, int add, char *int_name)
{
struct ipcmsg packet;
char *tmp;
+ if(!olsr_cnf->open_ipc) {
+ return -1;
+ }
+
if(!ipc_active)
return 0;
***************
*** 334,340 ****
ipc_send_all_routes(int fd)
{
! struct rt_entry *destination;
struct interface *ifn;
- int idx;
struct ipcmsg packet;
char *tmp;
--- 338,343 ----
ipc_send_all_routes(int fd)
{
! struct rt_entry *rt;
struct interface *ifn;
struct ipcmsg packet;
char *tmp;
***************
*** 344,440 ****
return 0;
! for(idx=0;idx<HASHSIZE;idx++)
! {
! for(destination = routingtable[idx].next;
! destination != &routingtable[idx];
! destination = destination->next)
! {
! ifn = destination->rt_if;
!
! memset(&packet, 0, sizeof(struct ipcmsg));
! packet.size = htons(IPC_PACK_SIZE);
! packet.msgtype = ROUTE_IPC;
!
! COPY_IP(&packet.target_addr, &destination->rt_dst);
! packet.add = 1;
!
! if(olsr_cnf->ip_version == AF_INET)
! {
! packet.metric = (olsr_u8_t)(destination->rt_metric - 1);
! }
! else
! {
! packet.metric = (olsr_u8_t)destination->rt_metric;
! }
! COPY_IP(&packet.gateway_addr, &destination->rt_router);
!
! if(ifn)
! memcpy(&packet.device[0], ifn->int_name, 4);
! else
! memset(&packet.device[0], 0, 4);
!
!
! tmp = (char *) &packet;
!
! if (send(fd, tmp, IPC_PACK_SIZE, MSG_NOSIGNAL) < 0) // MSG_NOSIGNAL to avoid sigpipe
! {
! OLSR_PRINTF(1, "(RT_ENTRY)IPC connection lost!\n");
! CLOSE(ipc_conn);
! //olsr_cnf->open_ipc = 0;
! ipc_active = OLSR_FALSE;
! return -1;
! }
!
! }
! }
!
! for(idx=0;idx<HASHSIZE;idx++)
! {
! for(destination = hna_routes[idx].next;
! destination != &hna_routes[idx];
! destination = destination->next)
! {
! ifn = destination->rt_if;
!
! packet.size = htons(IPC_PACK_SIZE);
! packet.msgtype = ROUTE_IPC;
! COPY_IP(&packet.target_addr, &destination->rt_dst);
! packet.add = 1;
!
! if(olsr_cnf->ip_version == AF_INET)
! {
! packet.metric = (olsr_u8_t)(destination->rt_metric - 1);
! }
! else
! {
! packet.metric = (olsr_u8_t)destination->rt_metric;
! }
! COPY_IP(&packet.gateway_addr, &destination->rt_router);
! if(ifn)
! memcpy(&packet.device[0], ifn->int_name, 4);
! else
! memset(&packet.device[0], 0, 4);
! tmp = (char *) &packet;
! if (send(ipc_conn, tmp, IPC_PACK_SIZE, MSG_NOSIGNAL) < 0) // MSG_NOSIGNAL to avoid sigpipe
! {
! OLSR_PRINTF(1, "(RT_ENTRY)IPC connection lost!\n");
! CLOSE(ipc_conn);
! //olsr_cnf->open_ipc = 0;
! ipc_active = OLSR_FALSE;
! return -1;
! }
!
! }
}
!
!
return 1;
}
--- 347,380 ----
return 0;
! OLSR_FOR_ALL_RT_ENTRIES(rt) {
! ifn = rt->rt_nexthop.iface;
! memset(&packet, 0, sizeof(struct ipcmsg));
! packet.size = htons(IPC_PACK_SIZE);
! packet.msgtype = ROUTE_IPC;
! COPY_IP(&packet.target_addr, &rt->rt_dst.prefix);
! packet.add = 1;
! packet.metric = (olsr_u8_t)(rt->rt_best->rtp_metric.hops);
! COPY_IP(&packet.gateway_addr, &rt->rt_nexthop.gateway);
+ if(ifn)
+ memcpy(&packet.device[0], ifn->int_name, 4);
+ else
+ memset(&packet.device[0], 0, 4);
! tmp = (char *) &packet;
! /* MSG_NOSIGNAL to avoid sigpipe */
! if (send(fd, tmp, IPC_PACK_SIZE, MSG_NOSIGNAL) < 0) {
! OLSR_PRINTF(1, "(RT_ENTRY)IPC connection lost!\n");
! CLOSE(ipc_conn);
! ipc_active = OLSR_FALSE;
! return -1;
}
! } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
return 1;
}
***************
*** 550,551 ****
--- 490,497 ----
return 1;
}
+
+ /*
+ * 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.28
retrieving revision 1.29
diff -C2 -d -r1.28 -r1.29
*** routing_table.c 2 Aug 2007 21:54:54 -0000 1.28
--- routing_table.c 5 Sep 2007 16:11:11 -0000 1.29
***************
*** 2,5 ****
--- 2,6 ----
* The olsr.org Optimized Link-State Routing daemon(olsrd)
* Copyright (c) 2004, Andreas Tønnesen((spam-protected))
+ * RIB implementation (c) 2007, Hannes Gredler ((spam-protected))
* All rights reserved.
*
***************
*** 40,45 ****
*/
[...1319 lines suppressed...]
!
! rtp = rtp_tree_node->data;
!
! printf("\tfrom %s, etx %.3f, metric %u, via %s, %s, v %u\n",
! olsr_ip_to_string(&rtp->rtp_originator),
! rtp->rtp_metric.etx,
! rtp->rtp_metric.hops,
! olsr_ip_to_string(&rtp->rtp_nexthop.gateway),
! rtp->rtp_nexthop.iface->int_name,
! rtp->rtp_version);
!
}
+ }
}
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: process_routes.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/process_routes.h,v
retrieving revision 1.10
retrieving revision 1.11
diff -C2 -d -r1.10 -r1.11
*** process_routes.h 31 Jan 2007 12:36:50 -0000 1.10
--- process_routes.h 5 Sep 2007 16:11:11 -0000 1.11
***************
*** 48,53 ****
#include <sys/ioctl.h>
! extern struct rt_entry old_routes[HASHSIZE];
! extern struct rt_entry old_hna[HASHSIZE];
void
--- 48,54 ----
#include <sys/ioctl.h>
! extern struct list_node add_kernel_list;
! extern struct list_node chg_kernel_list;
! extern struct list_node del_kernel_list;
void
***************
*** 78,108 ****
olsr_export_del_route6 (struct rt_entry*);
-
- int
- olsr_init_old_table(void);
-
- int
- olsr_find_up_route(struct rt_entry *dst,struct rt_entry *table);
-
- struct destination_n *
- olsr_build_update_list(struct rt_entry *from_table, struct rt_entry *in_table);
-
void
olsr_update_kernel_routes(void);
- void
- olsr_update_kernel_hna_routes(void);
-
- void
- olsr_move_route_table(struct rt_entry *, struct rt_entry *);
-
- void
- olsr_delete_routes_from_kernel(struct destination_n *delete_kernel_list);
-
- void
- olsr_add_routes_in_kernel(struct destination_n *add_kernel_list);
-
int
olsr_delete_all_kernel_routes(void);
#endif
--- 79,90 ----
olsr_export_del_route6 (struct rt_entry*);
void
olsr_update_kernel_routes(void);
int
olsr_delete_all_kernel_routes(void);
+ olsr_u8_t
+ olsr_rt_flags(struct rt_entry *);
+
#endif
Index: lq_avl.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_avl.c,v
retrieving revision 1.11
retrieving revision 1.12
diff -C2 -d -r1.11 -r1.12
*** lq_avl.c 2 Aug 2007 22:00:46 -0000 1.11
--- lq_avl.c 5 Sep 2007 16:11:10 -0000 1.12
***************
*** 51,58 ****
/*
! * dummy comparison pointer
! * set to zero for a fast inline ipv4 comparison
*/
int (*avl_comp_default)(void *, void *) = NULL;
int avl_comp_ipv4(void *ip1, void *ip2)
--- 51,61 ----
/*
! * default comparison pointers
! * set to the respective compare function.
! * if avl_comp_default is set to zero, a fast
! * inline ipv4 comparison will be executed.
*/
int (*avl_comp_default)(void *, void *) = NULL;
+ int (*avl_comp_prefix_default)(void *, void *);
int avl_comp_ipv4(void *ip1, void *ip2)
***************
*** 70,73 ****
--- 73,79 ----
{
tree->root = NULL;
+ tree->first = NULL;
+ tree->last = NULL;
+ tree->count = 0;
tree->comp = comp;
}
***************
*** 260,267 ****
}
! static void avl_insert_before(struct avl_node *pos_node, struct avl_node *node)
{
if (pos_node->prev != NULL)
pos_node->prev->next = node;
node->prev = pos_node->prev;
--- 266,276 ----
}
! static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node,
! struct avl_node *node)
{
if (pos_node->prev != NULL)
pos_node->prev->next = node;
+ else
+ tree->first = node;
node->prev = pos_node->prev;
***************
*** 269,278 ****
pos_node->prev = node;
}
! static void avl_insert_after(struct avl_node *pos_node, struct avl_node *node)
{
if (pos_node->next != NULL)
pos_node->next->prev = node;
node->prev = pos_node;
--- 278,292 ----
pos_node->prev = node;
+
+ tree->count++;
}
! static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node,
! struct avl_node *node)
{
if (pos_node->next != NULL)
pos_node->next->prev = node;
+ else
+ tree->last = node;
node->prev = pos_node;
***************
*** 280,292 ****
pos_node->next = node;
}
! static void avl_remove(struct avl_node *node)
{
if (node->prev != NULL)
node->prev->next = node->next;
if (node->next != NULL)
node->next->prev = node->prev;
}
--- 294,314 ----
pos_node->next = node;
+
+ tree->count++;
}
! static void avl_remove(struct avl_tree *tree, struct avl_node *node)
{
if (node->prev != NULL)
node->prev->next = node->next;
+ else
+ tree->first = node->next;
if (node->next != NULL)
node->next->prev = node->prev;
+ else
+ tree->last = node->prev;
+
+ tree->count--;
}
***************
*** 311,314 ****
--- 333,339 ----
{
tree->root = new;
+ tree->first = new;
+ tree->last = new;
+ tree->count = 1;
return 0;
}
***************
*** 329,338 ****
if (diff == 0)
{
! if (allow_duplicates == 0)
return -1;
new->leader = 0;
! avl_insert_after(last, new);
return 0;
}
--- 354,363 ----
if (diff == 0)
{
! if (allow_duplicates == AVL_DUP_NO)
return -1;
new->leader = 0;
! avl_insert_after(tree, last, new);
return 0;
}
***************
*** 340,344 ****
if (node->balance == 1)
{
! avl_insert_before(node, new);
node->balance = 0;
--- 365,369 ----
if (node->balance == 1)
{
! avl_insert_before(tree, node, new);
node->balance = 0;
***************
*** 350,354 ****
if (node->balance == -1)
{
! avl_insert_after(last, new);
node->balance = 0;
--- 375,379 ----
if (node->balance == -1)
{
! avl_insert_after(tree, last, new);
node->balance = 0;
***************
*** 360,364 ****
if (diff < 0)
{
! avl_insert_before(node, new);
node->balance = -1;
--- 385,389 ----
if (diff < 0)
{
! avl_insert_before(tree, node, new);
node->balance = -1;
***************
*** 369,373 ****
}
! avl_insert_after(last, new);
node->balance = 1;
--- 394,398 ----
}
! avl_insert_after(tree, last, new);
node->balance = 1;
***************
*** 662,686 ****
}
! avl_remove(node);
}
struct avl_node *avl_walk_first(struct avl_tree *tree)
{
! struct avl_node *node = tree->root;
!
! if (node == NULL)
! return NULL;
!
! return avl_local_min(node);
}
struct avl_node *avl_walk_last(struct avl_tree *tree)
{
! struct avl_node *node = tree->root;
!
! if (node == NULL)
! return NULL;
!
! return avl_local_max(node);
}
--- 687,701 ----
}
! avl_remove(tree, node);
}
struct avl_node *avl_walk_first(struct avl_tree *tree)
{
! return tree->first;
}
struct avl_node *avl_walk_last(struct avl_tree *tree)
{
! return tree->last;
}
Index: main.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/main.c,v
retrieving revision 1.96
retrieving revision 1.97
diff -C2 -d -r1.96 -r1.97
*** main.c 8 May 2007 23:10:37 -0000 1.96
--- main.c 5 Sep 2007 16:11:10 -0000 1.97
***************
*** 1,3 ****
-
/*
* The olsr.org Optimized Link-State Routing daemon(olsrd)
--- 1,2 ----
Index: olsr.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/olsr.c,v
retrieving revision 1.56
retrieving revision 1.57
diff -C2 -d -r1.56 -r1.57
*** olsr.c 1 Aug 2007 16:22:57 -0000 1.56
--- olsr.c 5 Sep 2007 16:11:11 -0000 1.57
***************
*** 173,208 ****
}
! if (olsr_cnf->lq_level < 2)
! {
! olsr_calculate_routing_table();
! olsr_calculate_hna_routes();
! }
}
! else if (changes_topology)
{
/* calculate the routing table and HNA */
! if (olsr_cnf->lq_level < 2)
! {
! olsr_calculate_routing_table();
! olsr_calculate_hna_routes();
! }
}
- else if (changes_hna)
- {
- /* update HNA routes */
-
- if (olsr_cnf->lq_level < 2)
- {
- olsr_calculate_hna_routes();
- }
- }
-
- if (olsr_cnf->lq_level >= 2)
- {
- olsr_calculate_lq_routing_table();
- }
if (olsr_cnf->debug_level > 0)
--- 173,188 ----
}
! 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)
***************
*** 265,270 ****
--- 245,252 ----
if (olsr_cnf->ipsize == 4) {
avl_comp_default = NULL;
+ avl_comp_prefix_default = avl_comp_ipv4_prefix;
} else {
avl_comp_default = avl_comp_ipv6;
+ avl_comp_prefix_default = avl_comp_ipv6_prefix;
}
***************
*** 284,290 ****
olsr_init_two_hop_table();
- /* Initialize old route table */
- olsr_init_old_table();
-
/* Initialize topology */
olsr_init_tc();
--- 266,269 ----
Index: routing_table.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/routing_table.h,v
retrieving revision 1.18
retrieving revision 1.19
diff -C2 -d -r1.18 -r1.19
*** routing_table.h 2 Aug 2007 21:54:54 -0000 1.18
--- routing_table.h 5 Sep 2007 16:11:11 -0000 1.19
***************
*** 2,5 ****
--- 2,6 ----
* The olsr.org Optimized Link-State Routing daemon(olsrd)
* Copyright (c) 2004, Andreas Tønnesen((spam-protected))
+ * RIB implementation (c) 2007, Hannes Gredler ((spam-protected))
* All rights reserved.
*
***************
*** 45,72 ****
#include <net/route.h>
#include "hna_set.h"
#define NETMASK_HOST 0xffffffff
#define NETMASK_DEFAULT 0x0
! struct rt_entry
{
! union olsr_ip_addr rt_dst;
! union olsr_ip_addr rt_router;
! union hna_netmask rt_mask;
! olsr_u8_t rt_flags;
! olsr_u16_t rt_metric;
! float rt_etx;
! struct interface *rt_if;
! struct rt_entry *prev;
! struct rt_entry *next;
};
! struct destination_n
{
! struct rt_entry *destination;
! struct destination_n *next;
};
/**
--- 46,123 ----
#include <net/route.h>
#include "hna_set.h"
+ #include "lq_avl.h"
+ #include "lq_list.h"
#define NETMASK_HOST 0xffffffff
#define NETMASK_DEFAULT 0x0
! /*
! * the kernel FIB does not need to know the metric of a route.
! * this saves us from enqueuing/dequeueing hopcount only changes.
! */
! #define RT_METRIC_DEFAULT 2
!
! /* a composite metric is used for path selection */
! struct rt_metric
{
! float etx;
! olsr_u32_t hops;
};
+ /* a nexthop is a pointer to a gateway router plus an interface */
+ struct rt_nexthop
+ {
+ union olsr_ip_addr gateway; /* gateway router */
+ struct interface *iface; /* outgoing interface */
+ };
! /*
! * Every prefix in our RIB needs a route entry that contains
! * the nexthop of the best path as installed in the kernel FIB.
! * The route entry is the root of a rt_path tree of equal prefixes
! * originated by different routers. It also contains a shortcut
! * for accessing the best route among all contributing routes.
! */
! struct rt_entry
{
! struct olsr_ip_prefix rt_dst;
! struct avl_node rt_tree_node;
! struct rt_path *rt_best; /* shortcut to the best path */
! struct rt_nexthop rt_nexthop; /* nexthop of FIB route */
! struct avl_tree rt_path_tree;
! struct list_node rt_change_node; /* queue for kernel FIB add/chg/del */
! };
!
! /*
! * For every received route a rt_path is added to the RIB.
! * 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
+ * datastructure from the callers.
+ *
+ * the loop prefetches the next node in order to not loose context if
+ * for example the caller wants to delete the current rt_entry.
+ */
+ #define OLSR_FOR_ALL_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;
+ #define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
/**
***************
*** 79,83 ****
struct sockaddr rt_dst;
struct sockaddr rt_gateway;
! olsr_u32_t rt_metric;
} v4;
--- 130,134 ----
struct sockaddr rt_dst;
struct sockaddr rt_gateway;
! olsr_u32_t metric;
} v4;
***************
*** 91,121 ****
! extern struct rt_entry routingtable[HASHSIZE];
! extern struct rt_entry hna_routes[HASHSIZE];
!
int
olsr_init_routing_table(void);
! void
! olsr_calculate_routing_table(void);
! void
! olsr_calculate_hna_routes(void);
! void
! olsr_print_routing_table(struct rt_entry *);
! struct rt_entry *
! olsr_insert_routing_table(union olsr_ip_addr *, const union olsr_ip_addr *, struct interface *, int, float);
! struct rt_entry *
! olsr_lookup_routing_table(union olsr_ip_addr *);
struct rt_entry *
! olsr_lookup_hna_routing_table(union olsr_ip_addr *dst);
- void
- olsr_free_routing_table(struct rt_entry *);
#endif
--- 142,183 ----
! extern struct avl_tree routingtree;
! extern unsigned int routingtree_version;
int
olsr_init_routing_table(void);
! unsigned int olsr_bump_routingtree_version(void);
! int avl_comp_ipv4_prefix (void *, void *);
! int avl_comp_ipv6_prefix (void *, void *);
! void olsr_rt_best(struct rt_entry *);
! olsr_bool olsr_nh_change(struct rt_nexthop *, struct rt_nexthop *);
! olsr_bool olsr_cmp_rt(struct rt_entry *, struct rt_entry *);
! void olsr_calculate_hna_routes(void);
! int olsr_fill_routing_table_with_neighbors(void);
! char *olsr_rt_to_string(struct rt_entry *);
! char *olsr_rtp_to_string(struct rt_path *);
! void olsr_print_routing_table(struct avl_tree *);
! struct rt_nexthop * olsr_get_nh(struct rt_entry *);
!
! struct rt_path *
! olsr_insert_routing_table(union olsr_ip_addr *, int,
! union olsr_ip_addr *,
! union olsr_ip_addr *,
! struct interface *, int, float);
struct rt_entry *
! olsr_lookup_routing_table(union olsr_ip_addr *);
#endif
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: hna_set.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/hna_set.h,v
retrieving revision 1.14
retrieving revision 1.15
diff -C2 -d -r1.14 -r1.15
*** hna_set.h 29 May 2005 12:47:45 -0000 1.14
--- hna_set.h 5 Sep 2007 16:11:10 -0000 1.15
***************
*** 74,77 ****
--- 74,80 ----
olsr_init_hna_set(void);
+ int
+ olsr_get_hna_prefix_len(struct hna_net *);
+
struct hna_net *
olsr_lookup_hna_net(struct hna_net *, union olsr_ip_addr *, union hna_netmask *);
More information about the Olsr-cvs
mailing list