Update to new avl/list iteration macros
[olsrd.git] / src / olsr_spf.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41
42 #include <assert.h>
43
44 #include "olsr_spf.h"
45 #include "tc_set.h"
46 #include "neighbor_table.h"
47 #include "routing_table.h"
48 #include "lq_plugin.h"
49 #include "process_routes.h"
50 #include "olsr_logging.h"
51
52 struct olsr_timer_info *spf_backoff_timer_info = NULL;
53 struct timer_entry *spf_backoff_timer = NULL;
54
55 /*
56  * avl_comp_etx
57  *
58  * compare two etx metrics.
59  * return 0 if there is an exact match and
60  * -1 / +1 depending on being smaller or bigger.
61  * note that this results in the most optimal code
62  * after compiler optimization.
63  */
64 static int
65 avl_comp_etx(const void *etx1, const void *etx2, void *ptr __attribute__ ((unused)))
66 {
67   if (*(const olsr_linkcost *)etx1 < *(const olsr_linkcost *)etx2) {
68     return -1;
69   }
70
71   if (*(const olsr_linkcost *)etx1 > *(const olsr_linkcost *)etx2) {
72     return +1;
73   }
74
75   return 0;
76 }
77
78 /*
79  * olsr_spf_add_cand_tree
80  *
81  * Key an existing vertex to a candidate tree.
82  */
83 static void
84 olsr_spf_add_cand_tree(struct avl_tree *tree, struct tc_entry *tc)
85 {
86 #if !defined REMOVE_LOG_DEBUG
87   struct ipaddr_str buf;
88   char lqbuffer[LQTEXT_MAXLENGTH];
89 #endif
90   tc->cand_tree_node.key = &tc->path_cost;
91
92   OLSR_DEBUG(LOG_ROUTING, "SPF: insert candidate %s, cost %s\n",
93              olsr_ip_to_string(&buf, &tc->addr), olsr_get_linkcost_text(tc->path_cost, false, lqbuffer, sizeof(lqbuffer)));
94
95   avl_insert(tree, &tc->cand_tree_node);
96 }
97
98 /*
99  * olsr_spf_del_cand_tree
100  *
101  * Unkey an existing vertex from a candidate tree.
102  */
103 static void
104 olsr_spf_del_cand_tree(struct avl_tree *tree, struct tc_entry *tc)
105 {
106   if (tc->cand_tree_node.key) {
107 #if !defined REMOVE_LOG_DEBUG
108     struct ipaddr_str buf;
109     char lqbuffer[LQTEXT_MAXLENGTH];
110 #endif
111     OLSR_DEBUG(LOG_ROUTING, "SPF: delete candidate %s, cost %s\n",
112         olsr_ip_to_string(&buf, &tc->addr), olsr_get_linkcost_text(tc->path_cost, false, lqbuffer, sizeof(lqbuffer)));
113
114     avl_delete(tree, &tc->cand_tree_node);
115     tc->cand_tree_node.key = NULL;
116   }
117 }
118
119 /*
120  * olsr_spf_add_path_list
121  *
122  * Insert an SPF result at the end of the path list.
123  */
124 static void
125 olsr_spf_add_path_list(struct list_entity *head, int *path_count, struct tc_entry *tc)
126 {
127 #if !defined REMOVE_LOG_DEBUG
128   struct ipaddr_str pathbuf, nbuf;
129   char lqbuffer[LQTEXT_MAXLENGTH];
130 #endif
131
132   OLSR_DEBUG(LOG_ROUTING, "SPF: append path %s, cost %s, via %s\n",
133              olsr_ip_to_string(&pathbuf, &tc->addr),
134              olsr_get_linkcost_text(tc->path_cost, false, lqbuffer, sizeof(lqbuffer)),
135              tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "-");
136
137   list_add_before(head, &tc->path_list_node);
138   *path_count = *path_count + 1;
139 }
140
141 /*
142  * olsr_spf_extract_best
143  *
144  * return the node with the minimum pathcost.
145  */
146 static struct tc_entry *
147 olsr_spf_extract_best(struct avl_tree *tree)
148 {
149   struct tc_entry *tc = NULL;
150   if (tree->count) {
151     tc = avl_first_element(tree, tc, cand_tree_node);
152   }
153   return tc;
154 }
155
156
157 /*
158  * olsr_spf_relax
159  *
160  * Explore all edges of a node and add the node
161  * to the candidate tree if the if the aggregate
162  * path cost is better.
163  */
164 static void
165 olsr_spf_relax(struct avl_tree *cand_tree, struct tc_entry *tc)
166 {
167   struct tc_edge_entry *tc_edge, *iterator;
168   olsr_linkcost new_cost;
169
170 #if !defined REMOVE_LOG_DEBUG
171   struct ipaddr_str buf, nbuf;
172   char lqbuffer[LQTEXT_MAXLENGTH];
173 #endif
174   OLSR_DEBUG(LOG_ROUTING, "SPF: exploring node %s, cost %s\n",
175              olsr_ip_to_string(&buf, &tc->addr),
176              olsr_get_linkcost_text(tc->path_cost, false, lqbuffer, sizeof(lqbuffer)));
177
178   /*
179    * loop through all edges of this vertex.
180    */
181   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator) {
182     struct tc_entry *new_tc;
183
184     assert (tc_edge->edge_inv);
185
186     /*
187      * total quality of the path through this vertex
188      * to the destination of this edge
189      */
190     if (tc_edge->virtual) {
191       new_cost = tc->path_cost + tc_edge->edge_inv->cost;
192     }
193     else {
194       new_cost = tc->path_cost + tc_edge->cost;
195     }
196
197     OLSR_DEBUG(LOG_ROUTING, "SPF:   exploring edge %s, cost %s\n",
198                olsr_ip_to_string(&buf, &tc_edge->T_dest_addr),
199                olsr_get_linkcost_text(new_cost, true, lqbuffer, sizeof(lqbuffer)));
200
201     /*
202      * if it's better than the current path quality of this edge's
203      * destination node, then we've found a better path to this node.
204      */
205     new_tc = tc_edge->edge_inv->tc;
206
207     if (new_cost < new_tc->path_cost) {
208
209       /* if this node has been on the candidate tree delete it */
210       if (new_tc->path_cost < ROUTE_COST_BROKEN) {
211         olsr_spf_del_cand_tree(cand_tree, new_tc);
212       }
213
214       /* remove from result list if necessary */
215       if (list_node_added(&new_tc->path_list_node)) {
216         list_remove(&new_tc->path_list_node);
217       }
218
219       /* re-insert on candidate tree with the better metric */
220       new_tc->path_cost = new_cost;
221       olsr_spf_add_cand_tree(cand_tree, new_tc);
222
223       /* pull-up the next-hop and bump the hop count */
224       if (tc->next_hop) {
225         new_tc->next_hop = tc->next_hop;
226       }
227       new_tc->hops = tc->hops + 1;
228
229       OLSR_DEBUG(LOG_ROUTING, "SPF:   better path to %s, cost %s, via %s, hops %d\n",
230                  olsr_ip_to_string(&buf, &new_tc->addr),
231                  olsr_get_linkcost_text(new_cost, true, lqbuffer, sizeof(lqbuffer)),
232                  tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "<none>", new_tc->hops);
233     }
234   }
235 }
236
237 /*
238  * olsr_spf_run_full
239  *
240  * Run the Dijkstra algorithm.
241  *
242  * A node gets added to the candidate tree when one of its edges has
243  * an overall better root path cost than the node itself.
244  * The node with the shortest metric gets moved from the candidate to
245  * the path list every pass.
246  * The SPF computation is completed when there are no more nodes
247  * on the candidate tree.
248  */
249 static void
250 olsr_spf_run_full(struct avl_tree *cand_tree, struct list_entity *path_list, int *path_count)
251 {
252   struct tc_entry *tc;
253
254   *path_count = 0;
255
256   while ((tc = olsr_spf_extract_best(cand_tree))) {
257     olsr_spf_relax(cand_tree, tc);
258
259     /*
260      * move the best path from the candidate tree
261      * to the path list.
262      */
263     olsr_spf_del_cand_tree(cand_tree, tc);
264     olsr_spf_add_path_list(path_list, path_count, tc);
265   }
266 }
267
268 /**
269  * Callback for the SPF backoff timer.
270  */
271 static void
272 olsr_expire_spf_backoff(void *context __attribute__ ((unused)))
273 {
274   spf_backoff_timer = NULL;
275 }
276
277 void
278 olsr_init_spf(void) {
279   spf_backoff_timer_info = olsr_alloc_timerinfo("SPF backoff", olsr_expire_spf_backoff, false);
280 }
281
282 void
283 olsr_calculate_routing_table(bool force)
284 {
285 #ifdef SPF_PROFILING
286   struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
287 #endif
288   struct avl_tree cand_tree;
289   struct list_entity path_list;          /* head of the path_list */
290   struct tc_entry *tc, *tc_iterator;
291   struct rt_path *rtp, *rtp_iterator;
292   struct tc_edge_entry *tc_edge;
293   struct nbr_entry *neigh, *neigh_iterator;
294   struct link_entry *link;
295   int path_count = 0;
296
297   /* We are done if our backoff timer is running */
298   if (!force && spf_backoff_timer != NULL) {
299     return;
300   }
301
302   olsr_set_timer(&spf_backoff_timer, OLSR_SPF_BACKOFF_TIME, OLSR_SPF_BACKOFF_JITTER,
303       NULL, spf_backoff_timer_info);
304
305 #ifdef SPF_PROFILING
306   gettimeofday(&t1, NULL);
307 #endif
308
309   /*
310    * Prepare the candidate tree and result list.
311    */
312   avl_init(&cand_tree, avl_comp_etx, true, NULL);
313   list_init_head(&path_list);
314   olsr_bump_routingtree_version();
315
316   /*
317    * Initialize vertices in the lsdb.
318    */
319   OLSR_FOR_ALL_TC_ENTRIES(tc, tc_iterator) {
320     tc->next_hop = NULL;
321     tc->path_cost = ROUTE_COST_BROKEN;
322     tc->hops = 0;
323     tc->cand_tree_node.key = NULL;
324     list_init_head(&tc->path_list_node);
325   }
326
327   /*
328    * Check if there was a change in the main IP address.
329    * Bail if there is no main IP address.
330    */
331   olsr_change_myself_tc();
332   if (!tc_myself) {
333
334     /*
335      * All gone now. Flush all routes.
336      */
337     olsr_update_rib_routes();
338     olsr_update_kernel_routes();
339     return;
340   }
341
342   /*
343    * zero ourselves and add us to the candidate tree.
344    */
345   tc_myself->path_cost = ZERO_ROUTE_COST;
346   olsr_spf_add_cand_tree(&cand_tree, tc_myself);
347
348   /*
349    * Set the next-hops of our neighbor link.
350    */
351   OLSR_FOR_ALL_NBR_ENTRIES(neigh, neigh_iterator) {
352     tc_edge = neigh->tc_edge;
353
354     if (neigh->is_sym) {
355       /* edges are always symmetric */
356       assert(tc_edge->edge_inv);
357
358       tc_edge->edge_inv->tc->next_hop = get_best_link_to_neighbor(neigh);
359     }
360   }
361
362 #ifdef SPF_PROFILING
363   gettimeofday(&t2, NULL);
364 #endif
365
366   /*
367    * Run the SPF calculation.
368    */
369   olsr_spf_run_full(&cand_tree, &path_list, &path_count);
370
371   OLSR_DEBUG(LOG_ROUTING, "\n--- %s ------------------------------------------------- DIJKSTRA\n\n", olsr_wallclock_string());
372
373 #ifdef SPF_PROFILING
374   gettimeofday(&t3, NULL);
375 #endif
376
377   /*
378    * In the path list we have all the reachable nodes in our topology.
379    */
380   while (!list_is_empty(&path_list)) {
381     tc = list_first_element(&path_list, tc, path_list_node);
382     list_remove(&tc->path_list_node);
383
384     link = tc->next_hop;
385
386     if (!link) {
387       /*
388        * Supress the error msg when our own tc_entry
389        * does not contain a next-hop.
390        */
391       if (tc != tc_myself) {
392 #if !defined REMOVE_LOG_DEBUG
393         struct ipaddr_str buf;
394 #endif
395         OLSR_DEBUG(LOG_ROUTING, "SPF: %s no next-hop\n", olsr_ip_to_string(&buf, &tc->addr));
396       }
397       continue;
398     }
399
400     /*
401      * Now walk all prefixes advertised by that node.
402      * Since the node is reachable, insert the prefix into the global RIB.
403      * If the prefix is already in the RIB, refresh the entry such
404      * that olsr_delete_outdated_routes() does not purge it off.
405      */
406     OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp, rtp_iterator) {
407       if (rtp->rtp_rt) {
408
409         /*
410          * If there is a route entry, the prefix is already in the global RIB.
411          */
412         olsr_update_rt_path(rtp, tc, link);
413
414       } else {
415
416         /*
417          * The prefix is reachable and not yet in the global RIB.
418          * Build a rt_entry for it.
419          */
420         olsr_insert_rt_path(rtp, tc, link);
421       }
422     }
423   }
424
425   /* Update the RIB based on the new SPF results */
426
427   olsr_update_rib_routes();
428
429 #ifdef SPF_PROFILING
430   gettimeofday(&t4, NULL);
431 #endif
432
433   /* move the route changes into the kernel */
434
435   olsr_update_kernel_routes();
436
437 #ifdef SPF_PROFILING
438   gettimeofday(&t5, NULL);
439 #endif
440
441 #ifdef SPF_PROFILING
442   timersub(&t2, &t1, &spf_init);
443   timersub(&t3, &t2, &spf_run);
444   timersub(&t4, &t3, &route);
445   timersub(&t5, &t4, &kernel);
446   timersub(&t5, &t1, &total);
447   OLSR_DEBUG(LOG_ROUTING, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern): "
448              "%d, %d, %d, %d, %d\n",
449              path_count, routingtree.count,
450              (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec, (int)route.tv_usec, (int)kernel.tv_usec);
451 #endif
452 }
453
454 /*
455  * Local Variables:
456  * c-basic-offset: 2
457  * indent-tabs-mode: nil
458  * End:
459  */