compile fixes for OpenBSD
[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.35 2005/05/25 16:33:25 br1 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, ipsize);
78 }
79
80 static int avl_comp_ipv4(void *ip1, void *ip2)
81 {
82   if (*(unsigned int *)ip1 < *(unsigned int *)ip2)
83     return -1;
84
85   if (*(unsigned int *)ip1 == *(unsigned int *)ip2)
86     return 0;
87
88   return 1;
89 }
90
91 static int (*avl_comp)(void *, void *);
92
93 static void add_vertex(struct avl_tree *vertex_tree, struct list *vertex_list,
94                        union olsr_ip_addr *addr, float path_etx)
95 {
96   struct avl_node *node;
97   struct dijk_vertex *vert;
98
99   // see whether this destination is already in our list
100
101   node = avl_find(vertex_tree, addr);
102
103   // if it's not in our list, add it
104
105   if (node == NULL)
106   {
107     vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
108
109     vert->tree_node.data = vert;
110     vert->tree_node.key = &vert->addr;
111
112     vert->node.data = vert;
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     list_add_tail(vertex_list, &vert->node);
125   }
126 }
127
128 static void add_edge(struct avl_tree *vertex_tree, struct list *vertex_list,
129                      union olsr_ip_addr *src, union olsr_ip_addr *dst,
130                      float etx)
131 {
132   struct avl_node *node;
133   struct dijk_vertex *svert;
134   struct dijk_vertex *dvert;
135   struct dijk_edge *edge;
136
137   // source lookup
138
139   node = avl_find(vertex_tree, src);
140
141   // source vertex does not exist
142
143   if (node == NULL)
144     return;
145
146   svert = node->data;
147
148   // destination lookup
149
150   node = avl_find(vertex_tree, dst);
151
152   // destination vertex does not exist
153
154   if (node == NULL)
155     return;
156
157   dvert = node->data;
158
159   // check for existing forward edge
160
161   if (avl_find(&svert->edge_tree, dst) == NULL)
162   {
163     // add forward edge
164
165     edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 1");
166
167     edge->tree_node.data = edge;
168     edge->tree_node.key = &dvert->addr;
169
170     edge->node.data = edge;
171
172     edge->dest = dvert;
173     edge->etx = etx;
174
175     avl_insert(&svert->edge_tree, &edge->tree_node);
176     list_add_tail(&svert->edge_list, &edge->node);
177   }
178
179   // check for existing inverse edge
180
181   if (avl_find(&dvert->edge_tree, src) == NULL)
182   {
183     // add inverse edge
184
185     edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 2");
186
187     edge->tree_node.data = edge;
188     edge->tree_node.key = &svert->addr;
189
190     edge->node.data = edge;
191
192     edge->dest = svert;
193     edge->etx = etx;
194
195     avl_insert(&dvert->edge_tree, &edge->tree_node);
196     list_add_tail(&dvert->edge_list, &edge->node);
197   }
198 }
199
200 static void free_everything(struct list *vertex_list)
201 {
202   struct list_node *vnode, *enode;
203   struct dijk_vertex *vert;
204   struct dijk_edge *edge;
205
206   vnode = list_get_head(vertex_list);
207
208   // loop through all vertices
209
210   while (vnode != NULL)
211   {
212     vert = vnode->data;
213
214     enode = list_get_head(&vert->edge_list);
215
216     // loop through all edges of the current vertex
217
218     while (enode != NULL)
219     {
220       edge = enode->data;
221
222       enode = list_get_next(enode);
223       free(edge);
224     }
225
226     vnode = list_get_next(vnode);
227     free(vert);
228   }
229 }
230
231 // XXX - bad complexity
232
233 static struct dijk_vertex *extract_best(struct list *vertex_list)
234 {
235   float best_etx = INFINITE_ETX + 1.0;
236   struct list_node *node;
237   struct dijk_vertex *vert;
238   struct dijk_vertex *res = NULL;
239
240   node = list_get_head(vertex_list);
241
242   // loop through all vertices
243   
244   while (node != NULL)
245   {
246     vert = node->data;
247
248     // see whether the current vertex is better than what we have
249
250     if (!vert->done && vert->path_etx < best_etx)
251     {
252       best_etx = vert->path_etx;
253       res = vert;
254     }
255
256     node = list_get_next(node);
257   }
258
259   // if we've found a vertex, remove it from the set
260
261   if (res != NULL)
262     res->done = OLSR_TRUE;
263
264   return res;
265 }
266
267 static void relax(struct dijk_vertex *vert)
268 {
269   struct dijk_edge *edge;
270   float new_etx;
271   struct list_node *node;
272
273   node = list_get_head(&vert->edge_list);
274
275   // loop through all edges of this vertex
276
277   while (node != NULL)
278   {
279     edge = node->data;
280
281     // total quality of the path through this vertex to the
282     // destination of this edge
283
284     new_etx = vert->path_etx + edge->etx;
285
286     // if it's better than the current path quality of this
287     // edge's destination, then we've found a better path to
288     // this destination
289
290     if (new_etx < edge->dest->path_etx)
291     {
292       edge->dest->path_etx = new_etx;
293       edge->dest->prev = vert;
294     }
295
296     node = list_get_next(node);
297   }
298 }
299
300 static char *etx_to_string(float etx)
301 {
302   static char buff[20];
303
304   if (etx == INFINITE_ETX)
305     return "INF";
306
307   snprintf(buff, 20, "%.2f", etx);
308   return buff;
309 }
310
311 void olsr_calculate_lq_routing_table(void)
312 {
313   struct avl_tree vertex_tree;
314   struct list vertex_list;
315   int i;
316   struct tc_entry *tcsrc;
317   struct topo_dst *tcdst;
318   struct dijk_vertex *vert;
319   struct link_entry *link;
320   struct neighbor_entry *neigh;
321   struct list_node *node;
322   struct dijk_vertex *myself;
323   struct dijk_vertex *walker;
324   int hops;
325   struct mid_address *mid_walker;
326   float etx;
327   struct hna_entry *hna_gw;
328   struct hna_net *hna;
329   struct rt_entry *gw_rt, *hna_rt, *head_rt;
330   struct neighbor_2_entry *neigh2;
331   struct neighbor_list_entry *neigh_walker;
332   struct interface *inter;
333
334   if (ipsize == 4)
335     avl_comp = avl_comp_ipv4;
336
337   else
338     avl_comp = avl_comp_ipv6;
339
340   // initialize the graph
341
342   avl_init(&vertex_tree, avl_comp);
343   list_init(&vertex_list);
344
345   // add ourselves to the vertex list
346
347   add_vertex(&vertex_tree, &vertex_list, &main_addr, 0.0);
348
349   // add our neighbours
350
351   for (i = 0; i < HASHSIZE; i++)
352     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
353          neigh = neigh->next)
354       if (neigh->status == SYM)
355         add_vertex(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
356                    INFINITE_ETX);
357
358   // add our two-hop neighbours
359
360   for (i = 0; i < HASHSIZE; i++)
361     for (neigh2 = two_hop_neighbortable[i].next;
362          neigh2 != &two_hop_neighbortable[i];
363          neigh2 = neigh2->next)
364       add_vertex(&vertex_tree, &vertex_list, &neigh2->neighbor_2_addr,
365                  INFINITE_ETX);
366
367   // add remaining vertices
368
369   for (i = 0; i < HASHSIZE; i++)
370     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
371     {
372       // add source
373
374       add_vertex(&vertex_tree, &vertex_list, &tcsrc->T_last_addr,
375                  INFINITE_ETX);
376
377       // add destinations of this source
378
379       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
380            tcdst = tcdst->next)
381         add_vertex(&vertex_tree, &vertex_list, &tcdst->T_dest_addr,
382                    INFINITE_ETX);
383     }
384
385   // add edges to and from our neighbours
386
387   for (i = 0; i < HASHSIZE; i++)
388     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
389          neigh = neigh->next)
390       if (neigh->status == SYM)
391       {
392         link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
393
394         if (link->loss_link_quality >= MIN_LINK_QUALITY &&
395             link->neigh_link_quality >= MIN_LINK_QUALITY)
396           {
397             etx = 1.0 / (link->loss_link_quality * link->neigh_link_quality);
398
399             add_edge(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
400                      &main_addr, etx);
401           }
402       }
403
404   // add edges between our neighbours and our two-hop neighbours
405
406   for (i = 0; i < HASHSIZE; i++)
407     for (neigh2 = two_hop_neighbortable[i].next;
408          neigh2 != &two_hop_neighbortable[i];
409          neigh2 = neigh2->next)
410       for (neigh_walker = neigh2->neighbor_2_nblist.next;
411            neigh_walker != &neigh2->neighbor_2_nblist;
412            neigh_walker = neigh_walker->next)
413       {
414         if (neigh_walker->second_hop_link_quality >=
415             MIN_LINK_QUALITY * MIN_LINK_QUALITY)
416         {
417           neigh = neigh_walker->neighbor;
418
419           etx = 1.0 / neigh_walker->second_hop_link_quality;
420
421           add_edge(&vertex_tree, &vertex_list, &neigh2->neighbor_2_addr,
422                    &neigh->neighbor_main_addr, etx);
423         }
424       }
425
426   // add remaining edges
427
428   for (i = 0; i < HASHSIZE; i++)
429     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
430       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
431            tcdst = tcdst->next)
432       {
433         if (tcdst->link_quality >= MIN_LINK_QUALITY &&
434             tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
435           {
436             etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
437
438             add_edge(&vertex_tree, &vertex_list, &tcdst->T_dest_addr,
439                      &tcsrc->T_last_addr, etx);
440           }
441       }
442
443   // run Dijkstra's algorithm
444
445   for (;;)
446   {
447     vert = extract_best(&vertex_list);
448
449     if (vert == NULL)
450       break;
451
452     relax(vert);
453   }
454
455   // save the old routing table
456
457   olsr_move_route_table(routingtable, old_routes);
458
459   node = list_get_head(&vertex_list);
460
461   // we're the first vertex in the list
462   
463   myself = node->data;
464
465   OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
466               nowtm->tm_hour,
467               nowtm->tm_min,
468               nowtm->tm_sec,
469               (int)now.tv_usec/10000)
470
471   for (node = list_get_next(node); node != NULL; node = list_get_next(node))
472   {
473     vert = node->data;
474
475     hops = 1;
476
477     // count hops to until the path ends or until we have reached a
478     // one-hop neighbour
479
480     for (walker = vert; walker != NULL && walker->prev != myself;
481          walker = walker->prev)
482     {
483       OLSR_PRINTF(2, "%s:%s <- ", olsr_ip_to_string(&walker->addr),
484                   etx_to_string(walker->path_etx))
485       hops++;
486     }
487
488     // if no path to a one-hop neighbour was found, ignore this node
489
490     if (walker != NULL)
491     {
492       OLSR_PRINTF(2, "%s:%s (one-hop)\n", olsr_ip_to_string(&walker->addr),
493                   etx_to_string(walker->path_etx))
494
495       // node reachable => add to the set of unprocessed nodes
496       // for HNA processing
497
498       vert->done = OLSR_FALSE;
499     }
500
501     else
502     {
503       OLSR_PRINTF(2, "%s FAILED\n", olsr_ip_to_string(&vert->addr))
504       continue;
505     }
506
507     // find the best link to the one-hop neighbour
508
509     link = get_best_link_to_neighbor(&walker->addr);
510
511     // we may see NULL here, if the one-hop neighbour is not in the
512     // link and neighbour sets any longer, but we have derived an edge
513     // between us and the one-hop neighbour from the TC set
514
515     if (link != NULL)
516     {
517       // find the interface for the found link
518
519       inter = if_ifwithaddr(&link->local_iface_addr);
520
521       // we may see NULL here if the interface is down, but we have
522       // links that haven't timed out, yet
523
524       if (inter != NULL)
525       {
526         // XXX - fix me: structurally prevent duplicates, don't test via
527         //       olsr_lookup_routing_table()
528
529         // route addition, case A - add a route to the main address of the
530         // destination node
531
532         if (olsr_lookup_routing_table(&vert->addr) == NULL)
533           olsr_insert_routing_table(&vert->addr, &link->neighbor_iface_addr,
534                                     inter, hops, vert->path_etx);
535
536         // route addition, case B - add routes to the remaining interfaces
537         // of the destination node
538
539         for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
540              mid_walker = mid_walker->next_alias)
541           if (olsr_lookup_routing_table(&mid_walker->alias) == NULL)
542             olsr_insert_routing_table(&mid_walker->alias,
543                                       &link->neighbor_iface_addr, inter, hops, 
544                                       vert->path_etx);
545
546         // XXX - we used to use olsr_lookup_routing_table() only here, but
547         //       this assumed that case A or case B had already happened for
548         //       this destination; if case A or case B happened after case C
549         //       for the same destination, we had duplicates, as cases A and
550         //       B would not test whether case C had already happened
551
552         // route addition, case C - make sure that we have a route to the
553         // router - e.g. in case the router's not the main address and it's
554         // MID entry has timed out
555
556         if (olsr_lookup_routing_table(&link->neighbor_iface_addr) == NULL)
557           olsr_insert_routing_table(&link->neighbor_iface_addr,
558                                     &link->neighbor_iface_addr, inter, 1,
559                                     vert->path_etx);
560       }
561     }
562   }
563
564   // add HNA routes - the set of unprocessed network nodes contains
565   // all reachable network nodes
566
567   for (;;)
568   {
569     // extract the network node with the best ETX and remove it
570     // from the set of unprocessed network nodes
571
572     vert = extract_best(&vertex_list);
573
574     // no more nodes left
575
576     if (vert == NULL)
577       break;
578
579     // find the node's HNAs
580
581     hna_gw = olsr_lookup_hna_gw(&vert->addr);
582
583     // node doesn't announce any HNAs
584
585     if (hna_gw == NULL)
586       continue;
587
588     // find route to the node
589
590     gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
591
592     // maybe we haven't found a link or an interface for the gateway above
593     // and hence haven't added a route - skip the HNA in this case
594
595     if (gw_rt == NULL)
596       continue;
597
598     // loop through the node's HNAs
599
600     for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
601          hna = hna->next)
602     {
603       // we already have a route via a previous (better) node
604
605       if (olsr_lookup_routing_table(&hna->A_network_addr) != NULL)
606         continue;
607
608       // create route for the HNA
609
610       hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
611
612       // set HNA IP address and netmask
613
614       COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
615       hna_rt->rt_mask = hna->A_netmask;
616
617       // copy remaining fields from the node's route
618
619       COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
620       hna_rt->rt_metric = gw_rt->rt_metric;
621       hna_rt->rt_etx = gw_rt->rt_etx;
622       hna_rt->rt_if = gw_rt->rt_if;
623
624       // we're not a host route
625
626       hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
627
628       // find the correct list
629
630       head_rt = &routingtable[olsr_hashing(&hna->A_network_addr)];
631
632       // enqueue
633
634       head_rt->next->prev = hna_rt;
635       hna_rt->next = head_rt->next;
636
637       head_rt->next = hna_rt;
638       hna_rt->prev = head_rt;
639     }
640   }
641
642   // free the graph
643
644   free_everything(&vertex_list);
645
646   // move the route changes into the kernel
647
648   olsr_update_kernel_routes();
649
650   // free the saved routing table
651
652   olsr_free_routing_table(old_routes);
653 }