* applied patches from the most recent FreiFunkFirmware (and fixed compile errors...
[olsrd.git] / src / lq_route.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without 
7  * modification, are permitted provided that the following conditions 
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright 
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright 
13  *   notice, this list of conditions and the following disclaimer in 
14  *   the documentation and/or other materials provided with the 
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its 
17  *   contributors may be used to endorse or promote products derived 
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  * $Id: lq_route.c,v 1.43 2007/01/31 12:36:50 bernd67 Exp $
40  */
41
42 #include "defs.h"
43 #include "olsr.h"
44 #include "tc_set.h"
45 #include "neighbor_table.h"
46 #include "two_hop_neighbor_table.h"
47 #include "link_set.h"
48 #include "routing_table.h"
49 #include "mid_set.h"
50 #include "hna_set.h"
51 #include "lq_list.h"
52 #include "lq_avl.h"
53 #include "lq_route.h"
54
55 struct dijk_edge
56 {
57   struct avl_node tree_node;
58   struct list_node node;
59   struct dijk_vertex *dest;
60   float etx;
61 };
62
63 struct dijk_vertex
64 {
65   struct avl_node tree_node;
66   struct list_node node;
67   union olsr_ip_addr addr;
68   struct avl_tree edge_tree;
69   struct list edge_list;
70   float path_etx;
71   struct dijk_vertex *prev;
72   olsr_bool done;
73 };
74
75 static int avl_comp_ipv6(void *ip1, void *ip2)
76 {
77   return memcmp(ip1, ip2, olsr_cnf->ipsize);
78 }
79
80 #ifdef DISABLE_SVEN_OLA
81 static int avl_comp_ipv4(void *ip1, void *ip2)
82 {
83   if (*(unsigned int *)ip1 < *(unsigned int *)ip2)
84     return -1;
85
86   if (*(unsigned int *)ip1 == *(unsigned int *)ip2)
87     return 0;
88
89   return 1;
90 }
91 #endif
92
93 static int (*avl_comp)(void *, void *);
94
95 static void add_vertex(struct avl_tree *vertex_tree, union olsr_ip_addr *addr,
96                        float path_etx)
97 {
98   struct avl_node *node;
99   struct dijk_vertex *vert;
100
101   // see whether this destination is already in our list
102
103   node = avl_find(vertex_tree, addr);
104
105   // if it's not in our list, add it
106
107   if (node == NULL)
108   {
109     vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
110
111     vert->tree_node.data = vert;
112     vert->tree_node.key = &vert->addr;
113
114     COPY_IP(&vert->addr, addr);
115     
116     vert->path_etx = path_etx;
117     vert->prev = NULL;
118     vert->done = OLSR_FALSE;
119
120     avl_init(&vert->edge_tree, avl_comp);
121     list_init(&vert->edge_list);
122
123     avl_insert(vertex_tree, &vert->tree_node);
124   }
125 }
126
127 static void add_edge(struct avl_tree *vertex_tree,
128                      union olsr_ip_addr *src, union olsr_ip_addr *dst,
129                      float etx)
130 {
131   struct avl_node *node;
132   struct dijk_vertex *svert;
133   struct dijk_vertex *dvert;
134   struct dijk_edge *edge;
135
136   // source lookup
137
138   node = avl_find(vertex_tree, src);
139
140   // source vertex does not exist
141
142   if (node == NULL)
143     return;
144
145   svert = node->data;
146
147   // destination lookup
148
149   node = avl_find(vertex_tree, dst);
150
151   // destination vertex does not exist
152
153   if (node == NULL)
154     return;
155
156   dvert = node->data;
157
158   // check for existing forward edge
159
160   if (avl_find(&svert->edge_tree, dst) == NULL)
161   {
162     // add forward edge
163
164     edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 1");
165
166     edge->tree_node.data = edge;
167     edge->tree_node.key = &dvert->addr;
168
169     edge->node.data = edge;
170
171     edge->dest = dvert;
172     edge->etx = etx;
173
174     avl_insert(&svert->edge_tree, &edge->tree_node);
175     list_add_tail(&svert->edge_list, &edge->node);
176   }
177
178   // check for existing inverse edge
179
180   if (avl_find(&dvert->edge_tree, src) == NULL)
181   {
182     // add inverse edge
183
184     edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 2");
185
186     edge->tree_node.data = edge;
187     edge->tree_node.key = &svert->addr;
188
189     edge->node.data = edge;
190
191     edge->dest = svert;
192     edge->etx = etx;
193
194     avl_insert(&dvert->edge_tree, &edge->tree_node);
195     list_add_tail(&dvert->edge_list, &edge->node);
196   }
197 }
198
199 static void create_vertex_list_rec(struct list *vertex_list,
200                                    struct avl_node *node,
201                                    int (*comp)(void *, void *))
202 {
203   struct dijk_vertex *vert = node->data;
204
205   if (node->left != NULL)
206     create_vertex_list_rec(vertex_list, node->left, comp);
207
208   // add the vertex to the list, if it's not us
209 #ifndef DISABLE_SVEN_OLA
210   if (NULL == comp) {
211     if (svenola_avl_comp_ipv4(&olsr_cnf->main_addr, node->key) != 0)
212     {
213       vert->node.data = vert;
214       list_add_tail(vertex_list, &vert->node);
215     }
216   }
217   else
218 #endif
219   if ((*comp)(&olsr_cnf->main_addr, node->key) != 0)
220   {
221     vert->node.data = vert;
222     list_add_tail(vertex_list, &vert->node);
223   }
224
225   if (node->right != NULL)
226     create_vertex_list_rec(vertex_list, node->right, comp);
227 }
228
229 static void create_vertex_list(struct avl_tree *vertex_tree,
230                                struct list *vertex_list)
231 {
232   struct avl_node *node;
233   struct dijk_vertex *vert;
234
235   // make ourselves the first vertex in the list
236
237   node = avl_find(vertex_tree, &olsr_cnf->main_addr);
238   vert = node->data;
239
240   vert->node.data = vert;
241   list_add_tail(vertex_list, &vert->node);
242
243   // add the remaining vertices ordered by their main address
244
245   create_vertex_list_rec(vertex_list, vertex_tree->root, vertex_tree->comp);
246 }
247
248 static void free_everything(struct list *vertex_list)
249 {
250   struct list_node *vnode, *enode;
251   struct dijk_vertex *vert;
252   struct dijk_edge *edge;
253
254   vnode = list_get_head(vertex_list);
255
256   // loop through all vertices
257
258   while (vnode != NULL)
259   {
260     vert = vnode->data;
261
262     enode = list_get_head(&vert->edge_list);
263
264     // loop through all edges of the current vertex
265
266     while (enode != NULL)
267     {
268       edge = enode->data;
269
270       enode = list_get_next(enode);
271       free(edge);
272     }
273
274     vnode = list_get_next(vnode);
275     free(vert);
276   }
277 }
278
279 // XXX - bad complexity
280 #define SVEN_OPT
281 #undef SVEN_OPT_DBG
282
283 /*
284  * The function extract_best() is most expensive (>50% CPU in profiling).
285  * It is called in two modes: while doing Dijkstra route calculation and
286  * while searching for a direct route/hna. The latter can be optimized
287  * because the stored verices do not change from call to call and it is
288  * more sufficient to have them sorted/popped from a list rather than 
289  * searching the complete list by every call. Sven-Ola@gmx.de, 11/2006
290  */
291  
292 #ifdef SVEN_OPT
293 static struct dijk_vertex **etx_cache = 0;
294 static int etx_cache_count;
295 static int etx_cache_get;
296 #ifdef SVEN_OPT_DBG
297 static int etx_cache_saved = 0;
298 #endif
299
300 static int etx_cache_compare(const void *a, const void *b)
301 {
302   // Oh jeah. I love this macro assembler :)
303   
304   if ((*(struct dijk_vertex **)a)->path_etx > (*(struct dijk_vertex **)b)->path_etx) return 1;
305   if ((*(struct dijk_vertex **)a)->path_etx < (*(struct dijk_vertex **)b)->path_etx) return -1;
306   
307   // This is for debugging only: etx==etx then compare pointers
308   // to make it possible to compare to the original search algo.
309   if (*(struct dijk_vertex **)a > *(struct dijk_vertex **)b) return 1;
310   if (*(struct dijk_vertex **)a < *(struct dijk_vertex **)b) return -1;
311   
312   return 0;
313 }
314
315 static struct dijk_vertex *extract_best_route(struct list *vertex_list)
316 {
317 #ifdef SVEN_OPT_DBG
318   float best_etx = INFINITE_ETX + 1.0;
319 #endif
320   struct list_node *node;
321   struct dijk_vertex *vert;
322   struct dijk_vertex *res = NULL;
323
324 #ifdef SVEN_OPT_DBG
325   node = list_get_head(vertex_list);
326
327   // loop through all vertices
328   
329   while (node != NULL)
330   {
331     vert = node->data;
332
333     // see whether the current vertex is better than what we have
334
335     if (!vert->done && vert->path_etx < best_etx)
336     {
337       best_etx = vert->path_etx;
338       res = vert;
339     }
340     else if (!vert->done && vert->path_etx == best_etx && vert < res)
341     {
342       // Otherwise order is undefined if etx==etx and debug will complain
343       best_etx = vert->path_etx;
344       res = vert;
345     }
346
347     node = list_get_next(node);
348   }
349 #endif
350   if (NULL == etx_cache)
351   {
352     int count = 0;
353     node = list_get_head(vertex_list);
354     while (node != NULL)
355     {
356       vert = node->data;
357       if (!vert->done && vert->path_etx < INFINITE_ETX) count++;
358       node = list_get_next(node);
359     }
360     if (0 < count)
361     {
362       etx_cache = olsr_malloc(sizeof(etx_cache[0]) * count, "ETX Cache");
363 #ifdef SVEN_OPT_DBG
364       printf("count=%d, Malloc(%d)=%p\n", count, sizeof(etx_cache[0]) * count, etx_cache);
365 #endif
366       node = list_get_head(vertex_list);
367       etx_cache_count = 0;
368       etx_cache_get = 0;
369       while (node != NULL)
370       {
371         vert = node->data;
372         if (!vert->done && vert->path_etx < INFINITE_ETX)
373         {
374           etx_cache[etx_cache_count] = vert;
375           etx_cache_count++;
376         }
377         node = list_get_next(node);
378       }
379 #ifdef SVEN_OPT_DBG
380       printf("qsort(etx_cache_count=%d)\n", etx_cache_count);
381 #endif
382       qsort(etx_cache, etx_cache_count, sizeof(etx_cache[0]), etx_cache_compare);
383 #ifdef SVEN_OPT_DBG
384       if (0 < etx_cache_count)
385       {
386         int i = 0; 
387         while(i < etx_cache_count && i < 10)
388         {
389           printf("%d: %p=%f\n", i, etx_cache[i], etx_cache[i]->path_etx);
390           i++;
391         }
392       }
393 #endif
394     }
395   }
396
397 #ifdef SVEN_OPT_DBG
398   if (NULL != etx_cache)
399   {
400     struct dijk_vertex *rescache = NULL;
401     if (etx_cache_get < etx_cache_count)
402     {
403       rescache = etx_cache[etx_cache_get++];
404     }
405     if (res != rescache)
406     {
407       printf("miss: etx_cache_get=%d, res=%p,%f != rescache=%p,%f\n",
408         etx_cache_get, res, (NULL != res ? res->path_etx : -1), rescache, (NULL != rescache ? rescache->path_etx : -1));
409     }
410     else
411     {
412       etx_cache_saved++;
413     }
414   }
415 #else
416   if (NULL != etx_cache && etx_cache_get < etx_cache_count)
417   {
418     res = etx_cache[etx_cache_get++];
419   }
420 #endif
421
422   // if we've found a vertex, remove it from the set
423
424   if (res != NULL)
425     res->done = OLSR_TRUE;
426
427   return res;
428 }
429 #endif // SVEN_OPT
430
431 static struct dijk_vertex *extract_best(struct list *vertex_list)
432 {
433   float best_etx = INFINITE_ETX + 1.0;
434   struct list_node *node;
435   struct dijk_vertex *vert;
436   struct dijk_vertex *res = NULL;
437
438   node = list_get_head(vertex_list);
439
440   // loop through all vertices
441   
442   while (node != NULL)
443   {
444     vert = node->data;
445
446     // see whether the current vertex is better than what we have
447
448     if (!vert->done && vert->path_etx < best_etx)
449     {
450       best_etx = vert->path_etx;
451       res = vert;
452     }
453
454     node = list_get_next(node);
455   }
456
457   // if we've found a vertex, remove it from the set
458
459   if (res != NULL)
460     res->done = OLSR_TRUE;
461
462   return res;
463 }
464
465 static void relax(struct dijk_vertex *vert)
466 {
467   struct dijk_edge *edge;
468   float new_etx;
469   struct list_node *node;
470
471   node = list_get_head(&vert->edge_list);
472
473   // loop through all edges of this vertex
474
475   while (node != NULL)
476   {
477     edge = node->data;
478
479     // total quality of the path through this vertex to the
480     // destination of this edge
481
482     new_etx = vert->path_etx + edge->etx;
483
484     // if it's better than the current path quality of this
485     // edge's destination, then we've found a better path to
486     // this destination
487
488     if (new_etx < edge->dest->path_etx)
489     {
490       edge->dest->path_etx = new_etx;
491       edge->dest->prev = vert;
492     }
493
494     node = list_get_next(node);
495   }
496 }
497
498 static char *etx_to_string(float etx)
499 {
500   static char buff[20];
501
502   if (etx == INFINITE_ETX)
503     return "INF";
504
505   snprintf(buff, 20, "%.2f", etx);
506   return buff;
507 }
508
509 void olsr_calculate_lq_routing_table(void)
510 {
511   struct avl_tree vertex_tree;
512   struct list vertex_list;
513   int i;
514   struct tc_entry *tcsrc;
515   struct topo_dst *tcdst;
516   struct dijk_vertex *vert;
517   struct link_entry *link;
518   struct neighbor_entry *neigh;
519   struct list_node *node;
520   struct dijk_vertex *myself;
521   struct dijk_vertex *walker;
522   int hops;
523   struct mid_address *mid_walker;
524   float etx;
525   struct hna_entry *hna_gw;
526   struct hna_net *hna;
527   struct rt_entry *gw_rt, *hna_rt, *head_rt;
528   struct neighbor_2_entry *neigh2;
529 #if 0
530   struct neighbor_list_entry *neigh_walker;
531 #endif
532   struct interface *inter;
533
534   if (olsr_cnf->ipsize == 4)
535 #ifndef DISABLE_SVEN_OLA
536     avl_comp = 0;
537 #else
538     avl_comp = avl_comp_ipv4;
539 #endif
540   else
541     avl_comp = avl_comp_ipv6;
542
543   // initialize the graph
544
545   avl_init(&vertex_tree, avl_comp);
546   list_init(&vertex_list);
547
548   // add ourselves to the vertex tree
549
550   add_vertex(&vertex_tree, &olsr_cnf->main_addr, 0.0);
551
552   // add our neighbours
553
554   for (i = 0; i < HASHSIZE; i++)
555     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
556          neigh = neigh->next)
557       if (neigh->status == SYM)
558         add_vertex(&vertex_tree, &neigh->neighbor_main_addr, INFINITE_ETX);
559
560   // add our two-hop neighbours
561
562   for (i = 0; i < HASHSIZE; i++)
563     for (neigh2 = two_hop_neighbortable[i].next;
564          neigh2 != &two_hop_neighbortable[i];
565          neigh2 = neigh2->next)
566       add_vertex(&vertex_tree, &neigh2->neighbor_2_addr, INFINITE_ETX);
567
568   // add remaining vertices
569
570   for (i = 0; i < HASHSIZE; i++)
571     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
572     {
573       // add source
574
575       add_vertex(&vertex_tree, &tcsrc->T_last_addr, INFINITE_ETX);
576
577       // add destinations of this source
578
579       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
580            tcdst = tcdst->next)
581         add_vertex(&vertex_tree, &tcdst->T_dest_addr, INFINITE_ETX);
582     }
583
584   // add edges to and from our neighbours
585
586   for (i = 0; i < HASHSIZE; i++)
587     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
588          neigh = neigh->next)
589       if (neigh->status == SYM)
590       {
591         link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
592
593         if(!link)
594           continue;
595
596         if (link->loss_link_quality2 >= MIN_LINK_QUALITY &&
597             link->neigh_link_quality2 >= MIN_LINK_QUALITY)
598           {
599             etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
600
601             add_edge(&vertex_tree, &neigh->neighbor_main_addr, &olsr_cnf->main_addr, etx);
602           }
603       }
604
605 // we now rely solely on TC messages for routes to our two-hop neighbours
606
607 #if 0
608
609   // add edges between our neighbours and our two-hop neighbours
610
611   for (i = 0; i < HASHSIZE; i++)
612     for (neigh2 = two_hop_neighbortable[i].next;
613          neigh2 != &two_hop_neighbortable[i];
614          neigh2 = neigh2->next)
615       for (neigh_walker = neigh2->neighbor_2_nblist.next;
616            neigh_walker != &neigh2->neighbor_2_nblist;
617            neigh_walker = neigh_walker->next)
618       {
619         if (neigh_walker->second_hop_link_quality >=
620             MIN_LINK_QUALITY * MIN_LINK_QUALITY)
621         {
622           neigh = neigh_walker->neighbor;
623
624           etx = 1.0 / neigh_walker->second_hop_link_quality;
625
626           add_edge(&vertex_tree, &neigh2->neighbor_2_addr,
627                    &neigh->neighbor_main_addr, etx);
628         }
629       }
630
631 #endif
632
633   // add remaining edges
634
635   for (i = 0; i < HASHSIZE; i++)
636     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
637       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
638            tcdst = tcdst->next)
639       {
640         if (tcdst->link_quality >= MIN_LINK_QUALITY &&
641             tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
642           {
643             etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
644
645             add_edge(&vertex_tree, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
646                      etx);
647           }
648       }
649
650   // create a sorted vertex list from the vertex tree
651
652   create_vertex_list(&vertex_tree, &vertex_list);
653
654   // run Dijkstra's algorithm
655
656   for (;;)
657   {
658     vert = extract_best(&vertex_list);
659
660     if (vert == NULL)
661       break;
662
663     relax(vert);
664   }
665
666   // save the old routing table
667
668   olsr_move_route_table(routingtable, old_routes);
669
670   node = list_get_head(&vertex_list);
671
672   // we're the first vertex in the list
673   
674   myself = node->data;
675
676   OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
677               nowtm->tm_hour,
678               nowtm->tm_min,
679               nowtm->tm_sec,
680               (int)now.tv_usec/10000)
681
682   for (node = list_get_next(node); node != NULL; node = list_get_next(node))
683   {
684     vert = node->data;
685
686     hops = 1;
687
688     // count hops to until the path ends or until we have reached a
689     // one-hop neighbour
690
691     for (walker = vert; walker != NULL && walker->prev != myself;
692          walker = walker->prev)
693     {
694       OLSR_PRINTF(2, "%s:%s <- ", olsr_ip_to_string(&walker->addr),
695                   etx_to_string(walker->path_etx))
696       hops++;
697     }
698
699     // if no path to a one-hop neighbour was found, ignore this node
700
701     if (walker != NULL)
702     {
703       OLSR_PRINTF(2, "%s:%s (one-hop)\n", olsr_ip_to_string(&walker->addr),
704                   etx_to_string(walker->path_etx))
705
706       // node reachable => add to the set of unprocessed nodes
707       // for HNA processing
708
709       vert->done = OLSR_FALSE;
710     }
711
712     else
713     {
714       OLSR_PRINTF(2, "%s FAILED\n", olsr_ip_to_string(&vert->addr))
715       continue;
716     }
717
718     // find the best link to the one-hop neighbour
719
720     link = get_best_link_to_neighbor(&walker->addr);
721
722     // we may see NULL here, if the one-hop neighbour is not in the
723     // link and neighbour sets any longer, but we have derived an edge
724     // between us and the one-hop neighbour from the TC set
725
726     if (link != NULL)
727     {
728       // find the interface for the found link
729       inter = link->if_name ? if_ifwithname(link->if_name) : 
730               if_ifwithaddr(&link->local_iface_addr);
731
732       // we may see NULL here if the interface is down, but we have
733       // links that haven't timed out, yet
734
735       if (inter != NULL)
736       {
737         // XXX - fix me: structurally prevent duplicates, don't test via
738         //       olsr_lookup_routing_table()
739
740         // route addition, case A - add a route to the main address of the
741         // destination node
742
743         if (olsr_lookup_routing_table(&vert->addr) == NULL)
744           olsr_insert_routing_table(&vert->addr, &link->neighbor_iface_addr,
745                                     inter, hops, vert->path_etx);
746
747         // route addition, case B - add routes to the remaining interfaces
748         // of the destination node
749
750         for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
751              mid_walker = mid_walker->next_alias)
752           if (olsr_lookup_routing_table(&mid_walker->alias) == NULL)
753             olsr_insert_routing_table(&mid_walker->alias,
754                                       &link->neighbor_iface_addr, inter, hops, 
755                                       vert->path_etx);
756
757         // XXX - we used to use olsr_lookup_routing_table() only here, but
758         //       this assumed that case A or case B had already happened for
759         //       this destination; if case A or case B happened after case C
760         //       for the same destination, we had duplicates, as cases A and
761         //       B would not test whether case C had already happened
762
763         // route addition, case C - make sure that we have a route to the
764         // router - e.g. in case the router's not the main address and it's
765         // MID entry has timed out
766
767         if (olsr_lookup_routing_table(&link->neighbor_iface_addr) == NULL)
768           olsr_insert_routing_table(&link->neighbor_iface_addr,
769                                     &link->neighbor_iface_addr, inter, 1,
770                                     vert->path_etx);
771       }
772     }
773   }
774
775   // save the old HNA routing table
776
777   olsr_move_route_table(hna_routes, old_hna);
778
779   // add HNA routes - the set of unprocessed network nodes contains
780   // all reachable network nodes
781 #ifdef SVEN_OPT
782 #ifdef SVEN_OPT_DBG
783   printf("free etx_cache, saved compares=%d, etx_cache=%p\n", etx_cache_saved, etx_cache);
784   etx_cache_saved = 0;
785 #endif
786   if (NULL != etx_cache) {
787     free(etx_cache);
788     etx_cache = NULL;
789   }
790 #endif
791
792   for (;;)
793   {
794     // extract the network node with the best ETX and remove it
795     // from the set of unprocessed network nodes
796
797 #ifdef SVEN_OPT
798     vert = extract_best_route(&vertex_list);
799 #else
800     vert = extract_best(&vertex_list);
801 #endif
802
803     // no more nodes left
804
805     if (vert == NULL)
806       break;
807
808     // find the node's HNAs
809
810     hna_gw = olsr_lookup_hna_gw(&vert->addr);
811
812     // node doesn't announce any HNAs
813
814     if (hna_gw == NULL)
815       continue;
816
817     // find route to the node
818
819     gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
820
821     // maybe we haven't found a link or an interface for the gateway above
822     // and hence haven't added a route - skip the HNA in this case
823
824     if (gw_rt == NULL)
825       continue;
826
827     // loop through the node's HNAs
828
829     for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
830          hna = hna->next)
831     {
832       // we already have a route via a previous (better) node
833
834       if (olsr_lookup_hna_routing_table(&hna->A_network_addr) != NULL)
835         continue;
836
837       // create route for the HNA
838
839       hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
840
841       // set HNA IP address and netmask
842
843       COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
844       hna_rt->rt_mask = hna->A_netmask;
845
846       // copy remaining fields from the node's route
847
848       COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
849       hna_rt->rt_metric = gw_rt->rt_metric;
850       hna_rt->rt_etx = gw_rt->rt_etx;
851       hna_rt->rt_if = gw_rt->rt_if;
852
853       // we're not a host route
854
855       hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
856
857       // find the correct list
858
859       head_rt = &hna_routes[olsr_hashing(&hna->A_network_addr)];
860
861       // enqueue
862
863       head_rt->next->prev = hna_rt;
864       hna_rt->next = head_rt->next;
865
866       head_rt->next = hna_rt;
867       hna_rt->prev = head_rt;
868     }
869   }
870
871   // free the graph
872
873   free_everything(&vertex_list);
874
875   // move the route changes into the kernel
876
877   olsr_update_kernel_routes();
878   olsr_update_kernel_hna_routes();
879
880   // free the saved routing table
881
882   olsr_free_routing_table(old_routes);
883   olsr_free_routing_table(old_hna);
884 }