0db595cfa66b33f994007a24a81ea910e30715d6
[olsrd.git] / src / lq_plugin.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2008 Henning Rogge <rogge@fgan.de>
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 "tc_set.h"
43 #include "link_set.h"
44 #include "olsr_spf.h"
45 #include "lq_packet.h"
46 #include "packet.h"
47 #include "olsr.h"
48 #include "two_hop_neighbor_table.h"
49 #include "common/avl.h"
50
51 #include "lq_plugin_default_float.h"
52 #include "lq_plugin_default_fpm.h"
53
54 struct avl_tree lq_handler_tree;
55 struct lq_handler *active_lq_handler = NULL;
56
57 int
58 avl_strcasecmp(const void *str1, const void *str2)
59 {
60   return strcasecmp(str1, str2);
61 }
62
63
64 void
65 init_lq_handler_tree(void)
66 {
67   avl_init(&lq_handler_tree, &avl_strcasecmp);
68   register_lq_handler(&lq_etx_float_handler, LQ_ALGORITHM_ETX_FLOAT_NAME);
69   register_lq_handler(&lq_etx_fpm_handler, LQ_ALGORITHM_ETX_FPM_NAME);
70   
71   if (activate_lq_handler(olsr_cnf->lq_algorithm)) {
72     activate_lq_handler(LQ_ALGORITHM_ETX_FPM_NAME);
73   }
74 }
75
76 /*
77  * set_lq_handler
78  * 
79  * this function is used by routing metric plugins to activate their link
80  * quality handler
81  * 
82  * The name parameter is marked as "unused" to squelch a compiler warning if debug
83  * output is not active
84  * 
85  * @param pointer to lq_handler structure
86  * @param name of the link quality handler for debug output
87  */
88 void
89 register_lq_handler(struct lq_handler *handler, const char *name)
90 {
91   struct lq_handler_node *node;
92   
93   node = olsr_malloc(sizeof(struct lq_handler) + strlen(name) + 1, "olsr lq handler");
94   
95   strcpy(node->name, name);
96   node->node.key = node->name;
97   node->handler = handler;
98   
99   avl_insert(&lq_handler_tree, &node->node, OLSR_FALSE); 
100 }
101
102 int
103 activate_lq_handler(const char *name)
104 {
105   struct lq_handler_node *node;
106   if (name == NULL) {
107     return 1;
108   }
109   
110   node = (struct lq_handler_node *) avl_find(&lq_handler_tree, name);
111   if (node == NULL) {
112     OLSR_PRINTF(1, "Error, unknown lq_handler '%s'\n", name);
113     return 1;
114   }
115   
116   OLSR_PRINTF(1, "Using '%s' algorithm for lq calculation.\n", name);
117   active_lq_handler = node->handler;
118   active_lq_handler->initialize();
119   
120   return 0;
121 }
122
123 /*
124  * olsr_calc_tc_cost
125  * 
126  * this function calculates the linkcost of a tc_edge_entry
127  * 
128  * @param pointer to the tc_edge_entry
129  * @return linkcost
130  */
131 olsr_linkcost
132 olsr_calc_tc_cost(const struct tc_edge_entry *tc_edge)
133 {
134   return active_lq_handler->calc_tc_cost(tc_edge->linkquality);
135 }
136
137 /*
138  * olsr_is_relevant_costchange
139  * 
140  * decides if the difference between two costs is relevant
141  * (for changing the route for example)
142  * 
143  * @param first linkcost value
144  * @param second linkcost value
145  * @return boolean
146  */
147 olsr_bool
148 olsr_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2)
149 {
150   return active_lq_handler->is_relevant_costchange(c1, c2);
151 }
152
153 /*
154  * olsr_serialize_hello_lq_pair
155  * 
156  * this function converts the lq information of a lq_hello_neighbor into binary package
157  * format
158  * 
159  * @param pointer to binary buffer to write into
160  * @param pointer to lq_hello_neighbor
161  * @return number of bytes that have been written
162  */
163 int
164 olsr_serialize_hello_lq_pair(unsigned char *buff,
165                              struct lq_hello_neighbor *neigh)
166 {
167   return active_lq_handler->serialize_hello_lq(buff, neigh->linkquality);
168 }
169
170 /*
171  * olsr_deserialize_hello_lq_pair
172  * 
173  * this function reads the lq information of a binary package into a hello_neighbor
174  * It also initialize the cost variable of the hello_neighbor
175  * 
176  * @param pointer to the current buffer pointer
177  * @param pointer to hello_neighbor
178  */
179 void
180 olsr_deserialize_hello_lq_pair(const olsr_u8_t ** curr,
181                                struct hello_neighbor *neigh)
182 {
183   active_lq_handler->deserialize_hello_lq(curr, neigh->linkquality);
184   neigh->cost = active_lq_handler->calc_hello_cost(neigh->linkquality);
185 }
186
187 /*
188  * olsr_serialize_tc_lq_pair
189  * 
190  * this function converts the lq information of a olsr_serialize_tc_lq_pair
191  * into binary package format
192  * 
193  * @param pointer to binary buffer to write into
194  * @param pointer to olsr_serialize_tc_lq_pair
195  * @return number of bytes that have been written
196  */
197 int
198 olsr_serialize_tc_lq_pair(unsigned char *buff, struct tc_mpr_addr *neigh)
199 {
200   return active_lq_handler->serialize_tc_lq(buff, neigh->linkquality);
201 }
202
203 /*
204  * olsr_deserialize_tc_lq_pair
205  * 
206  * this function reads the lq information of a binary package into a tc_edge_entry
207  * 
208  * @param pointer to the current buffer pointer
209  * @param pointer to tc_edge_entry
210  */
211 void
212 olsr_deserialize_tc_lq_pair(const olsr_u8_t ** curr, struct tc_edge_entry *edge)
213 {
214   active_lq_handler->deserialize_tc_lq(curr, edge->linkquality);
215 }
216
217 /*
218  * olsr_update_packet_loss_worker
219  * 
220  * this function is called every times a hello package for a certain link_entry
221  * is lost (timeout) or received. This way the lq-plugin can update the links link
222  * quality value.
223  * 
224  * @param pointer to link_entry
225  * @param OLSR_TRUE if hello package was lost
226  */
227 void
228 olsr_update_packet_loss_worker(struct link_entry *entry, olsr_bool lost)
229 {
230   olsr_linkcost lq;
231   lq = active_lq_handler->packet_loss_handler(entry, entry->linkquality, lost);
232
233   if (olsr_is_relevant_costchange(lq, entry->linkcost)) {
234     entry->linkcost = lq;
235
236     if (olsr_cnf->lq_dlimit > 0) {
237       changes_neighborhood = OLSR_TRUE;
238       changes_topology = OLSR_TRUE;
239     }
240
241     else
242       OLSR_PRINTF(3, "Skipping Dijkstra (1)\n");
243
244     /* XXX - we should check whether we actually announce this neighbour */
245     signal_link_changes(OLSR_TRUE);
246   }
247 }
248
249 /*
250  * olsr_memorize_foreign_hello_lq
251  * 
252  * this function is called to copy the link quality information from a received
253  * hello package into a link_entry.
254  * 
255  * @param pointer to link_entry
256  * @param pointer to hello_neighbor, if NULL the neighbor link quality information
257  * of the link entry has to be reset to "zero"
258  */
259 void
260 olsr_memorize_foreign_hello_lq(struct link_entry *local,
261                                struct hello_neighbor *foreign)
262 {
263   if (foreign) {
264     active_lq_handler->memorize_foreign_hello(local->linkquality,
265                                               foreign->linkquality);
266   } else {
267     active_lq_handler->memorize_foreign_hello(local->linkquality, NULL);
268   }
269 }
270
271 /*
272  * get_link_entry_text
273  * 
274  * this function returns the text representation of a link_entry cost value.
275  * It's not thread save and should not be called twice with the same println
276  * value in the same context (a single printf command for example).
277  * 
278  * @param pointer to link_entry
279  * @param buffer for output
280  * @return pointer to a buffer with the text representation
281  */
282 const char *
283 get_link_entry_text(struct link_entry *entry, struct lqtextbuffer *buffer)
284 {
285   return active_lq_handler->print_hello_lq(entry->linkquality, buffer);
286 }
287
288 /*
289  * get_tc_edge_entry_text
290  * 
291  * this function returns the text representation of a tc_edge_entry cost value.
292  * It's not thread save and should not be called twice with the same println
293  * value in the same context (a single printf command for example).
294  * 
295  * @param pointer to tc_edge_entry
296  * @param pointer to buffer
297  * @return pointer to the buffer with the text representation
298  */
299 const char *
300 get_tc_edge_entry_text(struct tc_edge_entry *entry, struct lqtextbuffer *buffer)
301 {
302   return active_lq_handler->print_tc_lq(entry->linkquality, buffer);
303 }
304
305 /*
306  * get_linkcost_text
307  * 
308  * This function transforms an olsr_linkcost value into it's text representation and copies
309  * the result into a buffer.
310  * 
311  * @param linkcost value
312  * @param true to transform the cost of a route, false for a link
313  * @param pointer to buffer
314  * @return pointer to buffer filled with text
315  */
316 const char *
317 get_linkcost_text(olsr_linkcost cost, olsr_bool route,
318                   struct lqtextbuffer *buffer)
319 {
320   static const char *infinite = "INFINITE";
321
322   if (route) {
323     if (cost == ROUTE_COST_BROKEN) {
324       return infinite;
325     }
326   } else {
327     if (cost >= LINK_COST_BROKEN) {
328       return infinite;
329     }
330   }
331   return active_lq_handler->print_cost(cost, buffer);
332 }
333
334 /*
335  * olsr_copy_hello_lq
336  * 
337  * this function copies the link quality information from a link_entry to a
338  * lq_hello_neighbor.
339  * 
340  * @param pointer to target lq_hello_neighbor
341  * @param pointer to source link_entry
342  */
343 void
344 olsr_copy_hello_lq(struct lq_hello_neighbor *target, struct link_entry *source)
345 {
346   memcpy(target->linkquality, source->linkquality,
347          active_lq_handler->hello_lq_size);
348 }
349
350 /*
351  * olsr_copylq_link_entry_2_tc_mpr_addr
352  * 
353  * this function copies the link quality information from a link_entry to a
354  * tc_mpr_addr.
355  * 
356  * @param pointer to tc_mpr_addr
357  * @param pointer to link_entry
358  */
359 void
360 olsr_copylq_link_entry_2_tc_mpr_addr(struct tc_mpr_addr *target,
361                                      struct link_entry *source)
362 {
363   active_lq_handler->copy_link_lq_into_tc(target->linkquality,
364                                           source->linkquality);
365 }
366
367 /*
368  * olsr_copylq_link_entry_2_tc_edge_entry
369  * 
370  * this function copies the link quality information from a link_entry to a
371  * tc_edge_entry.
372  * 
373  * @param pointer to tc_edge_entry
374  * @param pointer to link_entry
375  */
376 void
377 olsr_copylq_link_entry_2_tc_edge_entry(struct tc_edge_entry *target,
378                                        struct link_entry *source)
379 {
380   active_lq_handler->copy_link_lq_into_tc(target->linkquality,
381                                           source->linkquality);
382 }
383
384 /*
385  * olsr_clear_tc_lq
386  * 
387  * this function resets the linkquality value of a tc_mpr_addr
388  * 
389  * @param pointer to tc_mpr_addr
390  */
391 void
392 olsr_clear_tc_lq(struct tc_mpr_addr *target)
393 {
394   active_lq_handler->clear_tc(target->linkquality);
395 }
396
397 /*
398  * olsr_malloc_hello_neighbor
399  * 
400  * this function allocates memory for an hello_neighbor inclusive
401  * linkquality data.
402  * 
403  * @param id string for memory debugging
404  * 
405  * @return pointer to hello_neighbor
406  */
407 struct hello_neighbor *
408 olsr_malloc_hello_neighbor(const char *id)
409 {
410   struct hello_neighbor *h;
411
412   h =
413     olsr_malloc(sizeof(struct hello_neighbor) +
414                 active_lq_handler->hello_lq_size, id);
415
416   active_lq_handler->clear_hello(h->linkquality);
417   return h;
418 }
419
420 /*
421  * olsr_malloc_tc_mpr_addr
422  * 
423  * this function allocates memory for an tc_mpr_addr inclusive
424  * linkquality data.
425  * 
426  * @param id string for memory debugging
427  * 
428  * @return pointer to tc_mpr_addr
429  */
430 struct tc_mpr_addr *
431 olsr_malloc_tc_mpr_addr(const char *id)
432 {
433   struct tc_mpr_addr *t;
434
435   t =
436     olsr_malloc(sizeof(struct tc_mpr_addr) + active_lq_handler->tc_lq_size, id);
437
438   active_lq_handler->clear_tc(t->linkquality);
439   return t;
440 }
441
442 /*
443  * olsr_malloc_lq_hello_neighbor
444  * 
445  * this function allocates memory for an lq_hello_neighbor inclusive
446  * linkquality data.
447  * 
448  * @param id string for memory debugging
449  * 
450  * @return pointer to lq_hello_neighbor
451  */
452 struct lq_hello_neighbor *
453 olsr_malloc_lq_hello_neighbor(const char *id)
454 {
455   struct lq_hello_neighbor *h;
456
457   h =
458     olsr_malloc(sizeof(struct lq_hello_neighbor) +
459                 active_lq_handler->hello_lq_size, id);
460
461   active_lq_handler->clear_hello(h->linkquality);
462   return h;
463 }
464
465 /*
466  * olsr_malloc_link_entry
467  * 
468  * this function allocates memory for an link_entry inclusive
469  * linkquality data.
470  * 
471  * @param id string for memory debugging
472  * 
473  * @return pointer to link_entry
474  */
475 struct link_entry *
476 olsr_malloc_link_entry(const char *id)
477 {
478   struct link_entry *h;
479
480   h =
481     olsr_malloc(sizeof(struct link_entry) + active_lq_handler->hello_lq_size,
482                 id);
483
484   active_lq_handler->clear_hello(h->linkquality);
485   return h;
486 }
487
488 /*
489  * Local Variables:
490  * c-basic-offset: 2
491  * End:
492  */