1 /*
2 * The olsr.org Optimized Link-State Routing daemon (olsrd)
3 *
4 * (c) by the OLSR project
5 *
6 * See our Git repository to find out who worked on this file
7 * and thus is a copyright holder on it.
8 *
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 *
15 * * Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * * Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in
19 * the documentation and/or other materials provided with the
20 * distribution.
21 * * Neither the name of olsr.org, olsrd nor the names of its
22 * contributors may be used to endorse or promote products derived
23 * from this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
29 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
31 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
35 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 * POSSIBILITY OF SUCH DAMAGE.
37 *
38 * Visit http://www.olsr.org for more information.
39 *
40 * If you find this software useful feel free to make a donation
41 * to the project. For more information see the website or contact
42 * the copyright holders.
43 *
44 */
45
46 #include "tc_set.h"
47 #include "link_set.h"
48 #include "olsr_spf.h"
49 #include "lq_packet.h"
50 #include "packet.h"
51 #include "olsr.h"
52 #include "two_hop_neighbor_table.h"
53 #include "common/avl.h"
54
55 #include "lq_plugin_default_float.h"
56 #include "lq_plugin_default_fpm.h"
57 #include "lq_plugin_default_ff.h"
58 #include "lq_plugin_default_ffeth.h"
59
60 #ifdef LINUX_NL80211
61 #include "linux/lq_plugin_ffeth_nl80211.h"
62 #endif
63
64 #include <assert.h>
65 #include <math.h>
66
67 struct avl_tree lq_handler_tree;
68 struct lq_handler *active_lq_handler = NULL;
69
70 /**
71 * case-insensitive string comparator for avl-trees
72 * @param str1
73 * @param str2
74 * @return
75 */
76 int
avl_strcasecmp(const void * str1,const void * str2)77 avl_strcasecmp(const void *str1, const void *str2)
78 {
79 return strcasecmp(str1, str2);
80 }
81
82 /**
83 * Activate a LQ handler
84 * @param name
85 */
86 static void
activate_lq_handler(const char * name)87 activate_lq_handler(const char *name)
88 {
89 struct lq_handler_node *node;
90
91 node = (struct lq_handler_node *)avl_find(&lq_handler_tree, name);
92 if (node == NULL) {
93 char buf[1024];
94 snprintf(buf, sizeof(buf), "Error, unknown lq_handler '%s'", name);
95 olsr_exit(buf, EXIT_FAILURE);
96 }
97
98 OLSR_PRINTF(1, "Using '%s' algorithm for lq calculation.\n", name);
99 active_lq_handler = node->handler;
100 active_lq_handler->initialize();
101 }
102
103 /**
104 * Initialize LQ handler
105 */
106 void
init_lq_handler_tree(void)107 init_lq_handler_tree(void)
108 {
109 avl_init(&lq_handler_tree, &avl_strcasecmp);
110 register_lq_handler(&lq_etx_float_handler, LQ_ALGORITHM_ETX_FLOAT_NAME);
111 register_lq_handler(&lq_etx_fpm_handler, LQ_ALGORITHM_ETX_FPM_NAME);
112 register_lq_handler(&lq_etx_ff_handler, LQ_ALGORITHM_ETX_FF_NAME);
113 register_lq_handler(&lq_etx_ffeth_handler, LQ_ALGORITHM_ETX_FFETH_NAME);
114 #ifdef LINUX_NL80211
115 register_lq_handler(&lq_etx_ffeth_nl80211_handler, LQ_ALGORITHM_ETX_FFETH_NL80211_NAME);
116 #endif
117
118 if (olsr_cnf->lq_algorithm == NULL) {
119 activate_lq_handler(DEF_LQ_ALGORITHM);
120 }
121 else {
122 activate_lq_handler(olsr_cnf->lq_algorithm);
123 }
124 }
125
126 /**
127 * set_lq_handler
128 *
129 * this function is used by routing metric plugins to activate their link
130 * quality handler
131 *
132 * The name parameter is marked as "unused" to squelch a compiler warning if debug
133 * output is not active
134 *
135 * @param handler pointer to lq_handler structure
136 * @param name name of the link quality handler for debug output
137 */
138 void
register_lq_handler(struct lq_handler * handler,const char * name)139 register_lq_handler(struct lq_handler *handler, const char *name)
140 {
141 struct lq_handler_node *node;
142 size_t name_size = strlen(name) + 1;
143
144 node = olsr_malloc(sizeof(*node) + name_size, "olsr lq handler");
145
146 strscpy(node->name, name, name_size);
147 node->node.key = node->name;
148 node->handler = handler;
149
150 avl_insert(&lq_handler_tree, &node->node, false);
151 }
152
153 /**
154 * olsr_calc_tc_cost
155 *
156 * this function calculates the linkcost of a tc_edge_entry
157 *
158 * @param tc_edge pointer to the tc_edge_entry
159 * @return linkcost
160 */
161 olsr_linkcost
olsr_calc_tc_cost(const struct tc_edge_entry * tc_edge)162 olsr_calc_tc_cost(const struct tc_edge_entry * tc_edge)
163 {
164 assert((const char *)tc_edge + sizeof(*tc_edge) >= (const char *)tc_edge->linkquality);
165 return active_lq_handler->calc_tc_cost(tc_edge->linkquality);
166 }
167
168 /**
169 * olsr_serialize_hello_lq_pair
170 *
171 * this function converts the lq information of a lq_hello_neighbor into binary package
172 * format
173 *
174 * @param buff pointer to binary buffer to write into
175 * @param neigh pointer to lq_hello_neighbor
176 * @return number of bytes that have been written
177 */
178 int
olsr_serialize_hello_lq_pair(unsigned char * buff,struct lq_hello_neighbor * neigh)179 olsr_serialize_hello_lq_pair(unsigned char *buff, struct lq_hello_neighbor *neigh)
180 {
181 assert((const char *)neigh + sizeof(*neigh) >= (const char *)neigh->linkquality);
182 return active_lq_handler->serialize_hello_lq(buff, neigh->linkquality);
183 }
184
185 /**
186 * olsr_deserialize_hello_lq_pair
187 *
188 * this function reads the lq information of a binary package into a hello_neighbor
189 * It also initialize the cost variable of the hello_neighbor
190 *
191 * @param curr pointer to the current buffer pointer
192 * @param neigh pointer to hello_neighbor
193 */
194 void
olsr_deserialize_hello_lq_pair(const uint8_t ** curr,struct hello_neighbor * neigh)195 olsr_deserialize_hello_lq_pair(const uint8_t ** curr, struct hello_neighbor *neigh)
196 {
197 assert((const char *)neigh + sizeof(*neigh) >= (const char *)neigh->linkquality);
198 active_lq_handler->deserialize_hello_lq(curr, neigh->linkquality);
199 neigh->cost = active_lq_handler->calc_hello_cost(neigh->linkquality);
200 }
201
202 /**
203 * olsr_serialize_tc_lq_pair
204 *
205 * this function converts the lq information of a olsr_serialize_tc_lq_pair
206 * into binary package format
207 *
208 * @param buff pointer to binary buffer to write into
209 * @param neigh pointer to olsr_serialize_tc_lq_pair
210 * @return number of bytes that have been written
211 */
212 int
olsr_serialize_tc_lq_pair(unsigned char * buff,struct tc_mpr_addr * neigh)213 olsr_serialize_tc_lq_pair(unsigned char *buff, struct tc_mpr_addr *neigh)
214 {
215 assert((const char *)neigh + sizeof(*neigh) >= (const char *)neigh->linkquality);
216 return active_lq_handler->serialize_tc_lq(buff, neigh->linkquality);
217 }
218
219 /**
220 * olsr_deserialize_tc_lq_pair
221 *
222 * this function reads the lq information of a binary package into a tc_edge_entry
223 *
224 * @param curr pointer to the current buffer pointer
225 * @param edge pointer to tc_edge_entry
226 */
227 void
olsr_deserialize_tc_lq_pair(const uint8_t ** curr,struct tc_edge_entry * edge)228 olsr_deserialize_tc_lq_pair(const uint8_t ** curr, struct tc_edge_entry *edge)
229 {
230 assert((const char *)edge + sizeof(*edge) >= (const char *)edge->linkquality);
231 active_lq_handler->deserialize_tc_lq(curr, edge->linkquality);
232 }
233
234 /**
235 * olsr_update_packet_loss_worker
236 *
237 * this function is called every times a hello package for a certain link_entry
238 * is lost (timeout) or received. This way the lq-plugin can update the links link
239 * quality value.
240 *
241 * @param entry pointer to link_entry
242 * @param lost true if hello package was lost
243 */
244 void
olsr_update_packet_loss_worker(struct link_entry * entry,bool lost)245 olsr_update_packet_loss_worker(struct link_entry *entry, bool lost)
246 {
247 assert((const char *)entry + sizeof(*entry) >= (const char *)entry->linkquality);
248 active_lq_handler->packet_loss_handler(entry, entry->linkquality, lost);
249 }
250
251 /**
252 * olsr_memorize_foreign_hello_lq
253 *
254 * this function is called to copy the link quality information from a received
255 * hello package into a link_entry.
256 *
257 * @param local pointer to link_entry
258 * @param foreign pointer to hello_neighbor, if NULL the neighbor link quality information
259 * of the link entry has to be reset to "zero"
260 */
261 void
olsr_memorize_foreign_hello_lq(struct link_entry * local,struct hello_neighbor * foreign)262 olsr_memorize_foreign_hello_lq(struct link_entry *local, struct hello_neighbor *foreign)
263 {
264 assert((const char *)local + sizeof(*local) >= (const char *)local->linkquality);
265 if (foreign) {
266 assert((const char *)foreign + sizeof(*foreign) >= (const char *)foreign->linkquality);
267 active_lq_handler->memorize_foreign_hello(local->linkquality, foreign->linkquality);
268 } else {
269 active_lq_handler->memorize_foreign_hello(local->linkquality, NULL);
270 }
271 }
272
273 /**
274 * get_link_entry_text
275 *
276 * this function returns the text representation of a link_entry cost value.
277 * It's not thread save and should not be called twice with the same println
278 * value in the same context (a single printf command for example).
279 *
280 * @param entry to link_entry
281 * @param separator separator between LQ and NLQ
282 * @param buffer for output
283 * @return pointer to a buffer with the text representation
284 */
285 const char *
get_link_entry_text(struct link_entry * entry,char separator,struct lqtextbuffer * buffer)286 get_link_entry_text(struct link_entry *entry, char separator, struct lqtextbuffer *buffer)
287 {
288 assert((const char *)entry + sizeof(*entry) >= (const char *)entry->linkquality);
289 return active_lq_handler->print_hello_lq(entry->linkquality, separator, buffer);
290 }
291
292 /**
293 * get_tc_edge_entry_text
294 *
295 * this function returns the text representation of a tc_edge_entry cost value.
296 * It's not thread save and should not be called twice with the same println
297 * value in the same context (a single printf command for example).
298 *
299 * @param entry pointer to tc_edge_entry
300 * @param separator separator between LQ and NLQ
301 * @param buffer pointer to buffer
302 * @return pointer to the buffer with the text representation
303 */
304 const char *
get_tc_edge_entry_text(struct tc_edge_entry * entry,char separator,struct lqtextbuffer * buffer)305 get_tc_edge_entry_text(struct tc_edge_entry *entry, char separator, struct lqtextbuffer *buffer)
306 {
307 assert((const char *)entry + sizeof(*entry) >= (const char *)entry->linkquality);
308 return active_lq_handler->print_tc_lq(entry->linkquality, separator, buffer);
309 }
310
311 /**
312 * get_linkcost_text
313 *
314 * This function transforms an olsr_linkcost value into it's text representation and copies
315 * the result into a buffer.
316 *
317 * @param cost link cost value
318 * @param route true to transform the cost of a route, false for a link
319 * @param buffer pointer to buffer
320 * @return pointer to buffer filled with text
321 */
322 const char *
get_linkcost_text(olsr_linkcost cost,bool route,struct lqtextbuffer * buffer)323 get_linkcost_text(olsr_linkcost cost, bool route, struct lqtextbuffer *buffer)
324 {
325 olsr_linkcost limit = route ? ROUTE_COST_BROKEN : LINK_COST_BROKEN;
326 if (cost >= limit) {
327 return "INFINITE";
328 }
329
330 snprintf(buffer->buf, sizeof(buffer->buf), "%.3f", active_lq_handler->get_cost_scaled(cost));
331 buffer->buf[sizeof(buffer->buf) - 1] = '\0';
332 return buffer->buf;
333 }
334
335 double
get_linkcost_scaled(olsr_linkcost cost,bool route)336 get_linkcost_scaled(olsr_linkcost cost, bool route)
337 {
338 olsr_linkcost limit = route ? ROUTE_COST_BROKEN : LINK_COST_BROKEN;
339 if (cost >= limit) {
340 return (double) limit;
341 }
342
343 return active_lq_handler->get_cost_scaled(cost);
344 }
345
346 /**
347 * olsr_copy_hello_lq
348 *
349 * this function copies the link quality information from a link_entry to a
350 * lq_hello_neighbor.
351 *
352 * @param target pointer to target lq_hello_neighbor
353 * @param source pointer to source link_entry
354 */
355 void
olsr_copy_hello_lq(struct lq_hello_neighbor * target,struct link_entry * source)356 olsr_copy_hello_lq(struct lq_hello_neighbor *target, struct link_entry *source)
357 {
358 assert((const char *)target + sizeof(*target) >= (const char *)target->linkquality);
359 assert((const char *)source + sizeof(*source) >= (const char *)source->linkquality);
360 active_lq_handler->copy_link_lq_into_neigh(target->linkquality, source->linkquality);
361 }
362
363 /**
364 * olsr_copylq_link_entry_2_tc_mpr_addr
365 *
366 * this function copies the link quality information from a link_entry to a
367 * tc_mpr_addr.
368 *
369 * @param target pointer to tc_mpr_addr
370 * @param source pointer to link_entry
371 */
372 void
olsr_copylq_link_entry_2_tc_mpr_addr(struct tc_mpr_addr * target,struct link_entry * source)373 olsr_copylq_link_entry_2_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source)
374 {
375 assert((const char *)target + sizeof(*target) >= (const char *)target->linkquality);
376 assert((const char *)source + sizeof(*source) >= (const char *)source->linkquality);
377 active_lq_handler->copy_link_lq_into_tc(target->linkquality, source->linkquality);
378 }
379
380 /**
381 * olsr_copylq_link_entry_2_tc_edge_entry
382 *
383 * this function copies the link quality information from a link_entry to a
384 * tc_edge_entry.
385 *
386 * @param target pointer to tc_edge_entry
387 * @param source pointer to link_entry
388 */
389 void
olsr_copylq_link_entry_2_tc_edge_entry(struct tc_edge_entry * target,struct link_entry * source)390 olsr_copylq_link_entry_2_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source)
391 {
392 assert((const char *)target + sizeof(*target) >= (const char *)target->linkquality);
393 assert((const char *)source + sizeof(*source) >= (const char *)source->linkquality);
394 active_lq_handler->copy_link_lq_into_tc(target->linkquality, source->linkquality);
395 }
396
397 /* clear the lq of a link set entry */
olsr_clear_hello_lq(struct link_entry * link)398 void olsr_clear_hello_lq(struct link_entry *link) {
399 active_lq_handler->clear_hello(link->linkquality);
400 }
401
402 /**
403 * olsr_clear_tc_lq
404 *
405 * this function resets the linkquality value of a tc_mpr_addr
406 *
407 * @param target pointer to tc_mpr_addr
408 */
409 void
olsr_clear_tc_lq(struct tc_mpr_addr * target)410 olsr_clear_tc_lq(struct tc_mpr_addr *target)
411 {
412 assert((const char *)target + sizeof(*target) >= (const char *)target->linkquality);
413 active_lq_handler->clear_tc(target->linkquality);
414 }
415
416 /**
417 * olsr_malloc_hello_neighbor
418 *
419 * this function allocates memory for an hello_neighbor inclusive
420 * linkquality data.
421 *
422 * @param id string for memory debugging
423 *
424 * @return pointer to hello_neighbor
425 */
426 struct hello_neighbor *
olsr_malloc_hello_neighbor(const char * id)427 olsr_malloc_hello_neighbor(const char *id)
428 {
429 struct hello_neighbor *h;
430
431 h = olsr_malloc(sizeof(struct hello_neighbor) + active_lq_handler->hello_lq_size, id);
432
433 assert((const char *)h + sizeof(*h) >= (const char *)h->linkquality);
434 active_lq_handler->clear_hello(h->linkquality);
435 return h;
436 }
437
438 /**
439 * olsr_malloc_tc_mpr_addr
440 *
441 * this function allocates memory for an tc_mpr_addr inclusive
442 * linkquality data.
443 *
444 * @param id string for memory debugging
445 *
446 * @return pointer to tc_mpr_addr
447 */
448 struct tc_mpr_addr *
olsr_malloc_tc_mpr_addr(const char * id)449 olsr_malloc_tc_mpr_addr(const char *id)
450 {
451 struct tc_mpr_addr *t;
452
453 t = olsr_malloc(sizeof(struct tc_mpr_addr) + active_lq_handler->tc_lq_size, id);
454
455 assert((const char *)t + sizeof(*t) >= (const char *)t->linkquality);
456 active_lq_handler->clear_tc(t->linkquality);
457 return t;
458 }
459
460 /**
461 * olsr_malloc_lq_hello_neighbor
462 *
463 * this function allocates memory for an lq_hello_neighbor inclusive
464 * linkquality data.
465 *
466 * @param id string for memory debugging
467 *
468 * @return pointer to lq_hello_neighbor
469 */
470 struct lq_hello_neighbor *
olsr_malloc_lq_hello_neighbor(const char * id)471 olsr_malloc_lq_hello_neighbor(const char *id)
472 {
473 struct lq_hello_neighbor *h;
474
475 h = olsr_malloc(sizeof(struct lq_hello_neighbor) + active_lq_handler->hello_lq_size, id);
476
477 assert((const char *)h + sizeof(*h) >= (const char *)h->linkquality);
478 active_lq_handler->clear_hello(h->linkquality);
479 return h;
480 }
481
482 /**
483 * olsr_malloc_link_entry
484 *
485 * this function allocates memory for an link_entry inclusive
486 * linkquality data.
487 *
488 * @param id string for memory debugging
489 *
490 * @return pointer to link_entry
491 */
492 struct link_entry *
olsr_malloc_link_entry(const char * id)493 olsr_malloc_link_entry(const char *id)
494 {
495 struct link_entry *h;
496
497 h = olsr_malloc(sizeof(struct link_entry) + active_lq_handler->hello_lq_size, id);
498
499 assert((const char *)h + sizeof(*h) >= (const char *)h->linkquality);
500 active_lq_handler->clear_hello(h->linkquality);
501 return h;
502 }
503
olsr_sizeof_hello_lqdata(void)504 size_t olsr_sizeof_hello_lqdata(void) {
505 return active_lq_handler->hello_lqdata_size;
506 }
507
olsr_sizeof_tc_lqdata(void)508 size_t olsr_sizeof_tc_lqdata(void) {
509 return active_lq_handler->tc_lqdata_size;
510 }
511
512 /**
513 * This function should be called whenever the current linkcost
514 * value changed in a relevant way.
515 */
olsr_relevant_linkcost_change(void)516 void olsr_relevant_linkcost_change(void) {
517 changes_neighborhood = true;
518 changes_topology = true;
519
520 /* XXX - we should check whether we actually announce this neighbour */
521 signal_link_changes(true);
522 }
523
524 /*
525 * Local Variables:
526 * c-basic-offset: 2
527 * indent-tabs-mode: nil
528 * End:
529 */
530