* added -Wwrite-strings
[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  * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
5  * SPF implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without 
9  * modification, are permitted provided that the following conditions 
10  * are met:
11  *
12  * * Redistributions of source code must retain the above copyright 
13  *   notice, this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above copyright 
15  *   notice, this list of conditions and the following disclaimer in 
16  *   the documentation and/or other materials provided with the 
17  *   distribution.
18  * * Neither the name of olsr.org, olsrd nor the names of its 
19  *   contributors may be used to endorse or promote products derived 
20  *   from this software without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
33  * POSSIBILITY OF SUCH DAMAGE.
34  *
35  * Visit http://www.olsr.org for more information.
36  *
37  * If you find this software useful feel free to make a donation
38  * to the project. For more information see the website or contact
39  * the copyright holders.
40  *
41  * $Id: lq_route.c,v 1.58 2007/11/16 19:12:55 bernd67 Exp $
42  */
43
44 #include "defs.h"
45 #include "olsr.h"
46 #include "tc_set.h"
47 #include "neighbor_table.h"
48 #include "two_hop_neighbor_table.h"
49 #include "link_set.h"
50 #include "routing_table.h"
51 #include "mid_set.h"
52 #include "hna_set.h"
53 #include "lq_list.h"
54 #include "lq_avl.h"
55 #include "lq_route.h"
56 #include "net_olsr.h"
57
58 /*
59  * avl_comp_etx
60  *
61  * compare two etx metrics.
62  * return 0 if there is an exact match and
63  * -1 / +1 depending on being smaller or bigger.
64  * note that this results in the most optimal code
65  * after compiler optimization.
66  */
67 static int
68 avl_comp_etx (const void *etx1, const void *etx2)
69 {       
70   if (*(float *)etx1 < *(float *)etx2) {
71     return -1;
72   }
73
74   if (*(float *)etx1 > *(float *)etx2) {
75     return +1;
76   }
77
78   return 0;
79 }
80
81 /*
82  * olsr_spf_add_cand_tree
83  *
84  * Key an existing vertex to a candidate tree.
85  */
86 static void
87 olsr_spf_add_cand_tree (struct avl_tree *tree,
88                         struct tc_entry *vert)
89 {
90 #if !defined(NODEBUG) && defined(DEBUG)
91   struct ipaddr_str buf;
92 #endif
93   vert->cand_tree_node.key = &vert->path_etx;
94   vert->cand_tree_node.data = vert;
95
96 #ifdef DEBUG
97   OLSR_PRINTF(1, "SPF: insert candidate %s, cost %f\n",
98               olsr_ip_to_string(&buf, &vert->addr),
99               vert->path_etx);
100 #endif
101
102   avl_insert(tree, &vert->cand_tree_node, AVL_DUP);
103 }
104
105 /*
106  * olsr_spf_del_cand_tree
107  *
108  * Unkey an existing vertex from a candidate tree.
109  */
110 static void
111 olsr_spf_del_cand_tree (struct avl_tree *tree,
112                         struct tc_entry *vert)
113 {
114
115 #ifdef DEBUG
116 #ifndef NODEBUG
117   struct ipaddr_str buf;
118 #endif
119   OLSR_PRINTF(1, "SPF: delete candidate %s, cost %f\n",
120               olsr_ip_to_string(&buf, &vert->addr),
121               vert->path_etx);
122 #endif
123
124   avl_delete(tree, &vert->cand_tree_node);
125 }
126
127 /*
128  * olsr_spf_add_path_list
129  *
130  * Insert an SPF result at the end of the path list.
131  */
132 static void
133 olsr_spf_add_path_list (struct list_node *head,
134                         int *path_count,
135                         struct tc_entry *vert)
136 {
137 #if !defined(NODEBUG) && defined(DEBUG)
138   struct ipaddr_str pathbuf, nbuf;
139 #endif
140   vert->path_list_node.data = vert;
141
142 #ifdef DEBUG
143   OLSR_PRINTF(1, "SPF: append path %s, cost %f, via %s\n",
144               olsr_ip_to_string(&pathbuf, &vert->addr),
145               vert->path_etx,
146               vert->next_hop ? olsr_ip_to_string(&nbuf, &vert->next_hop->neighbor_iface_addr) : "-");
147 #endif
148
149   list_add_before(head, &vert->path_list_node);
150   *path_count = *path_count + 1;
151 }
152
153 /*
154  * olsr_spf_extract_best
155  *
156  * return the node with the minimum pathcost.
157  */
158 static struct tc_entry *
159 olsr_spf_extract_best (struct avl_tree *tree)
160 {
161   struct avl_node *node = avl_walk_first(tree);
162
163   return (node ? node->data :  NULL);
164 }
165
166
167 const char *olsr_etx_to_string(float etx)
168 {
169   static char buff[20];
170
171   if (etx == INFINITE_ETX) {
172     return "INF";
173   }
174   snprintf(buff, sizeof(buff), "%.6f", etx);
175   return buff;
176 }
177
178
179 /*
180  * olsr_spf_relax
181  *
182  * Explore all edges of a node and add the node
183  * to the candidate tree if the if the aggregate
184  * path cost is better.
185  */
186 static void
187 olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *vert)
188 {
189   struct avl_node *edge_node;
190   float new_etx;
191
192 #ifdef DEBUG
193 #ifndef NODEBUG
194   struct ipaddr_str buf, nbuf;
195 #endif
196   OLSR_PRINTF(1, "SPF: exploring node %s, cost %f\n",
197               olsr_ip_to_string(&buf, &vert->addr),
198               vert->path_etx);
199 #endif
200
201   /*
202    * loop through all edges of this vertex.
203    */
204   for (edge_node = avl_walk_first(&vert->edge_tree);
205        edge_node;
206        edge_node = avl_walk_next(edge_node)) {
207     struct tc_entry *new_vert;
208     struct tc_edge_entry *tc_edge = edge_node->data;
209
210     /*
211      * We are not interested in dead-end or dying edges.
212      */
213     if (!tc_edge->edge_inv || (tc_edge->flags & OLSR_TC_EDGE_DOWN)) {
214 #ifdef DEBUG
215       OLSR_PRINTF(1, "SPF:   ignoring edge %s\n",
216                   olsr_ip_to_string(&buf, &tc_edge->T_dest_addr));
217       if (tc_edge->flags & OLSR_TC_EDGE_DOWN) {
218         OLSR_PRINTF(1, "SPF:     edge down\n");
219       }
220       if (!tc_edge->edge_inv) {
221         OLSR_PRINTF(1, "SPF:     no inverse edge\n");
222       }
223 #endif
224       continue;
225     }
226
227     /*
228      * total quality of the path through this vertex
229      * to the destination of this edge
230      */
231     new_etx = vert->path_etx + tc_edge->etx;
232
233 #ifdef DEBUG
234       OLSR_PRINTF(1, "SPF:   exploring edge %s, cost %s\n",
235                   olsr_ip_to_string(&buf, &tc_edge->T_dest_addr),
236                   olsr_etx_to_string(new_etx));
237 #endif
238
239       /* 
240        * if it's better than the current path quality of this edge's
241        * destination node, then we've found a better path to this node.
242        */
243     new_vert = tc_edge->edge_inv->tc;
244
245     if (new_etx < new_vert->path_etx) {
246
247       /* if this node has been on the candidate tree delete it */
248       if (new_vert->path_etx != INFINITE_ETX) {
249         olsr_spf_del_cand_tree(cand_tree, new_vert);
250       }
251
252       /* re-insert on candidate tree with the better metric */
253       new_vert->path_etx = new_etx;
254       olsr_spf_add_cand_tree(cand_tree, new_vert);
255
256       /* pull-up the next-hop and bump the hop count */
257       if (vert->next_hop) {
258         new_vert->next_hop = vert->next_hop;
259       }
260       new_vert->hops = vert->hops + 1;
261
262 #ifdef DEBUG
263       OLSR_PRINTF(1, "SPF:   better path to %s, cost %s -> %s, via %s, hops %u\n",
264                   olsr_ip_to_string(&buf, &new_vert->addr),
265                   olsr_etx_to_string(new_vert->path_etx),
266                   olsr_etx_to_string(new_etx),
267                   vert->next_hop ? olsr_ip_to_string(&nbuf, &vert->next_hop->neighbor_iface_addr) : "<none>",
268                   new_vert->hops);
269 #endif
270
271     }
272   }
273 }
274
275 /*
276  * olsr_spf_run_full
277  *
278  * Run the Dijkstra algorithm.
279  * 
280  * A node gets added to the candidate tree when one of its edges has
281  * an overall better root path cost than the node itself.
282  * The node with the shortest metric gets moved from the candidate to
283  * the path list every pass.
284  * The SPF computation is completed when there are no more nodes
285  * on the candidate tree. 
286  */ 
287 static void
288 olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
289                    int *path_count)
290 {
291   struct tc_entry *vert;
292
293   *path_count = 0;
294
295   while ((vert = olsr_spf_extract_best(cand_tree))) {
296
297     olsr_spf_relax(cand_tree, vert);
298
299     /*
300      * move the best path from the candidate tree
301      * to the path list.
302      */
303     olsr_spf_del_cand_tree(cand_tree, vert);
304     olsr_spf_add_path_list(path_list, path_count, vert);
305   }
306 }
307
308 void
309 olsr_calculate_routing_table (void)
310 {
311   struct avl_tree cand_tree;
312   struct list_node path_list;
313   int i, plen, path_count = 0;
314   struct tc_entry *tc;
315   struct tc_edge_entry *tc_edge;
316   struct tc_entry *vert;
317   struct neighbor_entry *neigh;
318   struct mid_address *mid_walker;
319   struct hna_entry *hna_gw;
320   struct hna_net *hna;
321   struct interface *inter;
322   struct link_entry *link;
323
324 #ifdef SPF_PROFILING
325   struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
326
327   gettimeofday(&t1, NULL);
328 #endif
329
330   /*
331    * Prepare the candidate tree and result list.
332    */
333   avl_init(&cand_tree, avl_comp_etx);
334   list_head_init(&path_list);
335   olsr_bump_routingtree_version();
336
337   /*
338    * Initialize vertices in the lsdb.
339    */
340   OLSR_FOR_ALL_TC_ENTRIES(tc) {
341     tc->next_hop = NULL;
342     tc->path_etx = INFINITE_ETX;
343     tc->hops = 0;
344   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
345
346   /*
347    * zero ourselves and add us to the candidate tree.
348    */
349   olsr_change_myself_tc();
350   tc_myself->path_etx = ZERO_ETX;
351   olsr_spf_add_cand_tree(&cand_tree, tc_myself);
352
353   /*
354    * add edges to and from our neighbours.
355    */
356   for (i = 0; i < HASHSIZE; i++)
357     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
358          neigh = neigh->next) {
359
360       if (neigh->status == SYM) {
361
362         tc_edge = olsr_lookup_tc_edge(tc_myself, &neigh->neighbor_main_addr);
363         link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
364         if (!link) {
365
366           /*
367            * If there is no best link to this neighbor
368            * and we had an edge before then flush the edge.
369            */
370           if (tc_edge) {
371             olsr_delete_tc_edge_entry(tc_edge);
372           }
373           continue;
374         }
375
376         /*
377          * Set the next-hops of our neighbors. 
378          */
379         if (!tc_edge) {
380           tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
381                                            0, link->last_htime,
382                                            link->loss_link_quality2,
383                                            link->neigh_link_quality2);
384         } else {
385           tc_edge->link_quality = link->loss_link_quality2;
386           tc_edge->inverse_link_quality = link->neigh_link_quality2;
387           olsr_calc_tc_edge_entry_etx(tc_edge);
388         }
389         if (tc_edge->edge_inv) {
390           tc_edge->edge_inv->tc->next_hop = link;
391         }
392       }
393     }
394
395 #ifdef SPF_PROFILING
396   gettimeofday(&t2, NULL);
397 #endif
398
399   /*
400    * Run the SPF calculation.
401    */
402   olsr_spf_run_full(&cand_tree, &path_list, &path_count);
403
404   OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
405               nowtm->tm_hour,
406               nowtm->tm_min,
407               nowtm->tm_sec,
408               (int)now.tv_usec/10000);
409
410 #ifdef SPF_PROFILING
411   gettimeofday(&t3, NULL);
412 #endif
413
414   /*
415    * In the path tree we have all the reachable nodes in our topology.
416    */
417   for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
418
419     vert = path_list.next->data;
420     link = vert->next_hop;
421
422     if (!link) {
423 #ifndef NODEBUG
424       struct ipaddr_str buf;
425 #endif
426       OLSR_PRINTF(2, "%s no next-hop\n", olsr_ip_to_string(&buf, &vert->addr));
427       continue;
428     }
429
430     /* find the interface for the found link */
431     inter = link->if_name ? if_ifwithname(link->if_name)
432       : if_ifwithaddr(&link->local_iface_addr);
433
434     /* interface is up ? */
435     if (inter) {
436
437       /* add a route to the main address of the destination node */
438       olsr_insert_routing_table(&vert->addr, olsr_cnf->maxplen, &vert->addr,
439                                 &link->neighbor_iface_addr, inter->if_index,
440                                 vert->hops, vert->path_etx);
441
442       /* add routes to the remaining interfaces of the destination node */
443       for (mid_walker = mid_lookup_aliases(&vert->addr);
444            mid_walker != NULL;
445            mid_walker = mid_walker->next_alias) {
446
447         olsr_insert_routing_table(&mid_walker->alias, olsr_cnf->maxplen, &vert->addr,
448                                   &link->neighbor_iface_addr, inter->if_index,
449                                   vert->hops, vert->path_etx);
450       }
451
452       /* find the node's HNAs */
453       hna_gw = olsr_lookup_hna_gw(&vert->addr);
454
455       /* node doesn't announce any HNAs */
456       if (!hna_gw) {
457         continue;
458       }
459
460       /* loop through the node's HNAs */
461       for (hna = hna_gw->networks.next;
462            hna != &hna_gw->networks;
463            hna = hna->next) {
464
465         plen = olsr_get_hna_prefix_len(hna);
466         if (vert->path_etx != INFINITE_ETX)
467         olsr_insert_routing_table(&hna->A_network_addr, plen, &vert->addr,
468                                   &link->neighbor_iface_addr, inter->if_index,
469                                   vert->hops, vert->path_etx);
470       }
471     }
472   }
473
474 #ifdef SPF_PROFILING
475   gettimeofday(&t4, NULL);
476 #endif
477
478   /* move the route changes into the kernel */
479
480   olsr_update_kernel_routes();
481
482 #ifdef SPF_PROFILING
483   gettimeofday(&t5, NULL);
484 #endif
485
486 #ifdef SPF_PROFILING
487   timersub(&t2, &t1, &spf_init);
488   timersub(&t3, &t2, &spf_run);
489   timersub(&t4, &t3, &route);
490   timersub(&t5, &t4, &kernel);
491   timersub(&t5, &t1, &total);
492   olsr_printf(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern): "
493               "%d, %d, %d, %d, %d\n",
494               path_count, routingtree.count,
495               (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
496               (int)route.tv_usec, (int)kernel.tv_usec);
497 #endif
498 }
499
500 /*
501  * Local Variables:
502  * c-basic-offset: 2
503  * End:
504  */