Merge branch 'master' into mpr_rework
[oonf.git] / src-plugins / nhdp / nhdp / nhdp_domain.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon version 2 (olsrd2)
4  * Copyright (c) 2004-2015, 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 /**
43  * @file
44  */
45
46 #include <stdio.h>
47
48 #include "common/avl.h"
49 #include "common/avl_comp.h"
50 #include "common/common_types.h"
51 #include "common/list.h"
52 #include "common/netaddr.h"
53 #include "core/oonf_cfg.h"
54 #include "core/oonf_logging.h"
55 #include "subsystems/oonf_class.h"
56 #include "subsystems/oonf_rfc5444.h"
57
58 #include "nhdp/nhdp.h"
59 #include "nhdp/nhdp_db.h"
60 #include "nhdp/nhdp_domain.h"
61 #include "nhdp/nhdp_interfaces.h"
62 #include "nhdp/nhdp_internal.h"
63
64 static void _apply_metric(struct nhdp_domain *domain, const char *metric_name);
65 static void _remove_metric(struct nhdp_domain *);
66 static void _apply_mpr(struct nhdp_domain *domain,
67     const char *mpr_name, uint8_t willingness);
68 static void _remove_mpr(struct nhdp_domain *);
69
70 static void _cb_update_everyone_mpr(struct nhdp_domain *);
71
72 static bool _recalculate_neighbor_metrics(struct nhdp_domain *domain);
73 static bool _recalculate_neighbor_metric(struct nhdp_domain *domain,
74         struct nhdp_neighbor *neigh);
75 static bool _recalculate_mpr_set(struct nhdp_domain *domain);
76
77 static const char *_link_to_string(struct nhdp_metric_str *, uint32_t);
78 static const char *_path_to_string(struct nhdp_metric_str *, uint32_t, uint8_t);
79 static const char *_int_to_string(struct nhdp_metric_str *, struct nhdp_link *);
80
81 /* domain class */
82 static struct oonf_class _domain_class = {
83   .name = NHDP_CLASS_DOMAIN,
84   .size = sizeof(struct nhdp_domain),
85 };
86
87 /* default metric handler (hopcount) */
88 static struct nhdp_domain_metric _no_metric = {
89   .name = "Hopcount metric",
90
91   .incoming_link_start = RFC7181_METRIC_MAX,
92   .outgoing_link_start = RFC7181_METRIC_MAX,
93   .incoming_2hop_start = RFC7181_METRIC_MAX,
94   .outgoing_2hop_start = RFC7181_METRIC_MAX,
95
96   .link_to_string = _link_to_string,
97   .path_to_string = _path_to_string,
98   .internal_link_to_string = _int_to_string,
99
100   .no_default_handling = true,
101 };
102
103 /* default MPR handler (no MPR handling) */
104 static struct nhdp_domain_mpr _everyone_mprs = {
105   .name = "Everyone MPR",
106
107   .update_mpr = _cb_update_everyone_mpr,
108 };
109
110 /* non-default routing domains registered to NHDP */
111 static struct list_entity _domain_list;
112 static struct list_entity _domain_listener_list;
113
114 static size_t _domain_counter = 0;
115
116 /* tree of known routing metrics/mpr-algorithms */
117 static struct avl_tree _domain_metrics;
118 static struct avl_tree _domain_mprs;
119
120 /* flooding domain */
121 static struct nhdp_domain _flooding_domain;
122
123 /* NHDP RFC5444 protocol */
124 static struct oonf_rfc5444_protocol *_protocol;
125
126 /* remember if node is MPR or not */
127 static bool _node_is_selected_as_mpr = false;
128
129 /**
130  * Initialize nhdp metric core
131  * @param p pointer to rfc5444 protocol
132  */
133 void
134 nhdp_domain_init(struct oonf_rfc5444_protocol *p) {
135   _protocol = p;
136
137   oonf_class_add(&_domain_class);
138   list_init_head(&_domain_list);
139   list_init_head(&_domain_listener_list);
140
141   avl_init(&_domain_metrics, avl_comp_strcasecmp, false);
142   avl_init(&_domain_mprs, avl_comp_strcasecmp, false);
143
144   /* initialize flooding domain */
145   _flooding_domain.metric = &_no_metric;
146   _flooding_domain.mpr = &_everyone_mprs;
147
148   _flooding_domain.mpr->_refcount++;
149   _flooding_domain.metric->_refcount++;
150 }
151
152 /**
153  * cleanup allocated resources for nhdp metric core
154  */
155 void
156 nhdp_domain_cleanup(void) {
157   struct nhdp_domain *domain, *d_it;
158   struct nhdp_domain_listener *listener, *l_it;
159   int i;
160
161   list_for_each_element_safe(&_domain_list, domain, _node, d_it) {
162     /* free allocated TLVs */
163     for (i=0; i<4; i++) {
164       rfc5444_writer_unregister_addrtlvtype(
165           &_protocol->writer, &domain->_metric_addrtlvs[i]);
166     }
167
168     /* remove domain */
169     list_remove(&domain->_node);
170     oonf_class_free(&_domain_class, domain);
171   }
172
173   list_for_each_element_safe(&_domain_listener_list, listener, _node, l_it) {
174     nhdp_domain_listener_remove(listener);
175   }
176   oonf_class_remove(&_domain_class);
177 }
178
179 /**
180  * @return number of registered nhdp domains
181  */
182 size_t
183 nhdp_domain_get_count(void) {
184   return _domain_counter;
185 }
186
187 /**
188  * Add a new metric handler to nhdp
189  * @param metric pointer to NHDP link metric
190  * @return 0 if successful, -1 if metric was already registered
191  */
192 int
193 nhdp_domain_metric_add(struct nhdp_domain_metric *metric) {
194   /* initialize key */
195   metric->_node.key = metric->name;
196
197   /* insert default values if not set */
198   if (metric->incoming_link_start == 0) {
199     metric->incoming_link_start = RFC7181_METRIC_MAX;
200   }
201   if (metric->outgoing_link_start == 0) {
202     metric->outgoing_link_start = RFC7181_METRIC_INFINITE;
203   }
204   if (metric->incoming_2hop_start == 0) {
205     metric->incoming_2hop_start = RFC7181_METRIC_INFINITE;
206   }
207   if (metric->outgoing_2hop_start == 0) {
208     metric->outgoing_2hop_start = RFC7181_METRIC_INFINITE;
209   }
210
211   /* initialize to_string method if empty */
212   if (metric->link_to_string == NULL) {
213     metric->link_to_string = _link_to_string;
214   }
215   if (metric->path_to_string == NULL) {
216     metric->path_to_string = _path_to_string;
217   }
218
219   if (metric->internal_link_to_string == NULL) {
220     metric->internal_link_to_string = _int_to_string;
221   }
222
223   /* hook into tree */
224   return avl_insert(&_domain_metrics, &metric->_node);
225 }
226
227 /**
228  * Remove a metric handler from the nhdp metric core
229  * @param metric pointer to metric handler
230  */
231 void
232 nhdp_domain_metric_remove(struct nhdp_domain_metric *metric) {
233   struct nhdp_domain *domain;
234
235   list_for_each_element(&_domain_list, domain, _node) {
236     if (domain->metric == metric) {
237       _remove_metric(domain);
238       break;
239     }
240   }
241
242   avl_remove(&_domain_metrics, &metric->_node);
243 }
244
245 /**
246  * Add a new mpr handler to nhdp
247  * @param mpr pointer to mpr handler
248  * @return 0 if successful, -1 if metric is already registered
249  */
250 int
251 nhdp_domain_mpr_add(struct nhdp_domain_mpr *mpr) {
252   struct nhdp_domain *domain;
253
254   /* initialize key */
255   mpr->_node.key = mpr->name;
256
257   if (avl_insert(&_domain_mprs, &mpr->_node)) {
258     return -1;
259   }
260
261   list_for_each_element(&_domain_list, domain, _node) {
262     if (domain->mpr == &_everyone_mprs) {
263       _apply_mpr(domain, domain->mpr_name, domain->local_willingness);
264     }
265   }
266   if (_flooding_domain.mpr == &_everyone_mprs) {
267     _apply_mpr(&_flooding_domain,
268         _flooding_domain.mpr_name, _flooding_domain.local_willingness);
269   }
270   return 0;
271 }
272
273 /**
274  * Remove a metric handler from the nhdp metric core
275  * @param mpr pointer to mpr handler
276  */
277 void
278 nhdp_domain_mpr_remove(struct nhdp_domain_mpr *mpr) {
279   struct nhdp_domain *domain;
280
281   list_for_each_element(&_domain_list, domain, _node) {
282     if (domain->mpr == mpr) {
283       _remove_mpr(domain);
284       break;
285     }
286   }
287
288   avl_remove(&_domain_mprs, &mpr->_node);
289 }
290
291 /**
292  * Adds a listener to the NHDP domain system
293  * @param listener pointer to NHDP domain listener
294  */
295 void
296 nhdp_domain_listener_add(struct nhdp_domain_listener *listener) {
297   list_add_tail(&_domain_listener_list, &listener->_node);
298 }
299
300 /**
301  * Removes a listener from the NHDP domain system
302  * @param listener pointer to NHDP domain listener
303  */
304 void
305 nhdp_domain_listener_remove(struct nhdp_domain_listener *listener) {
306   if (list_is_node_added(&listener->_node)) {
307     list_remove(&listener->_node);
308   }
309 }
310
311 /**
312  * @param ext TLV extension value of MPR/Linkmetrics
313  * @return NHDP domain registered to this extension, NULL if not found
314  */
315 struct nhdp_domain *
316 nhdp_domain_get_by_ext(uint8_t ext) {
317   struct nhdp_domain *d;
318
319   list_for_each_element(&_domain_list, d, _node) {
320     if (d->ext == ext) {
321       return d;
322     }
323   }
324   return NULL;
325 }
326
327 /**
328  * Initialize the domain data of a new NHDP link
329  * @param lnk NHDP link
330  */
331 void
332 nhdp_domain_init_link(struct nhdp_link *lnk) {
333   struct nhdp_domain *domain;
334   struct nhdp_link_domaindata *data;
335   int i;
336
337   /* initialize metrics */
338   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
339     lnk->_domaindata[i].metric.in = RFC7181_METRIC_INFINITE;
340     lnk->_domaindata[i].metric.out = RFC7181_METRIC_INFINITE;
341   }
342   list_for_each_element(&_domain_list, domain, _node) {
343     data = nhdp_domain_get_linkdata(domain, lnk);
344
345     if (domain->metric->no_default_handling) {
346       data->metric.in = domain->metric->incoming_link_start;
347       data->metric.out = domain->metric->outgoing_link_start;
348     }
349   }
350 }
351
352 /**
353  * Initialize the domain data of a new NHDP twohop neighbor
354  * @param l2hop NHDP twohop neighbor
355  */
356 void
357 nhdp_domain_init_l2hop(struct nhdp_l2hop *l2hop) {
358   struct nhdp_domain *domain;
359   struct nhdp_l2hop_domaindata *data;
360   int i;
361
362   /* initialize metrics */
363   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
364     l2hop->_domaindata[i].metric.in = RFC7181_METRIC_INFINITE;
365     l2hop->_domaindata[i].metric.out = RFC7181_METRIC_INFINITE;
366   }
367
368   list_for_each_element(&_domain_list, domain, _node) {
369     data = nhdp_domain_get_l2hopdata(domain, l2hop);
370
371     if (domain->metric->no_default_handling) {
372       data->metric.in = domain->metric->incoming_2hop_start;
373       data->metric.out = domain->metric->outgoing_2hop_start;
374     }
375   }
376 }
377
378 /**
379  * Initialize the domain data of a new NHDP neighbor
380  * @param neigh NHDP neighbor
381  */
382 void
383 nhdp_domain_init_neighbor(struct nhdp_neighbor *neigh) {
384   struct nhdp_domain *domain;
385   struct nhdp_neighbor_domaindata *data;
386   int i;
387
388   /* initialize flooding MPR settings */
389   neigh->flooding_willingness = RFC7181_WILLINGNESS_NEVER;
390   neigh->local_is_flooding_mpr = false;
391   neigh->neigh_is_flooding_mpr = false;
392
393   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
394     neigh->_domaindata[i].metric.in = RFC7181_METRIC_INFINITE;
395     neigh->_domaindata[i].metric.out = RFC7181_METRIC_INFINITE;
396
397     neigh->_domaindata[i].best_link = NULL;
398     neigh->_domaindata[i].willingness = RFC7181_WILLINGNESS_NEVER;
399
400
401     neigh->_domaindata[i].local_is_mpr = false;
402     neigh->_domaindata[i].neigh_is_mpr = false;
403   }
404
405   /* initialize metrics and mprs */
406   list_for_each_element(&_domain_list, domain, _node) {
407     data = nhdp_domain_get_neighbordata(domain, neigh);
408
409     if (domain->metric->no_default_handling) {
410       data->metric.in = domain->metric->incoming_link_start;
411       data->metric.out = domain->metric->outgoing_link_start;
412     }
413   }
414 }
415
416 /**
417  * Process an in linkmetric tlv for a nhdp link
418  * @param domain pointer to NHDP domain
419  * @param lnk pointer to nhdp link
420  * @param value pointer to value of metric tlv,
421  *   must have a length of at least 2
422  */
423 void
424 nhdp_domain_process_metric_linktlv(struct nhdp_domain *domain,
425     struct nhdp_link *lnk, uint8_t *value) {
426   struct rfc7181_metric_field metric_field;
427   uint32_t metric;
428
429   memcpy(&metric_field, value, sizeof(metric_field));
430   metric = rfc7181_metric_decode(&metric_field);
431
432   if (rfc7181_metric_has_flag(&metric_field, RFC7181_LINKMETRIC_INCOMING_LINK)) {
433     nhdp_domain_get_linkdata(domain, lnk)->metric.out = metric;
434   }
435   if (rfc7181_metric_has_flag(&metric_field, RFC7181_LINKMETRIC_INCOMING_NEIGH)) {
436     nhdp_domain_get_neighbordata(domain, lnk->neigh)->metric.out = metric;
437   }
438 }
439
440 /**
441  * Process an in linkmetric tlv for a nhdp twohop neighbor
442  * @param domain pointer to NHDP domain
443  * @param l2hop pointer to nhdp twohop neighbor
444  * @param value value of metric tlv
445  */
446 void
447 nhdp_domain_process_metric_2hoptlv(struct nhdp_domain *domain,
448     struct nhdp_l2hop *l2hop, uint8_t *value) {
449   struct rfc7181_metric_field metric_field;
450   struct nhdp_l2hop_domaindata *data;
451   uint32_t metric;
452
453   memcpy(&metric_field, value, sizeof(metric_field));
454   metric = rfc7181_metric_decode(&metric_field);
455
456   data = nhdp_domain_get_l2hopdata(domain, l2hop);
457   if (rfc7181_metric_has_flag(&metric_field, RFC7181_LINKMETRIC_INCOMING_NEIGH)) {
458     data->metric.in = metric;
459   }
460   if (rfc7181_metric_has_flag(&metric_field, RFC7181_LINKMETRIC_OUTGOING_NEIGH)) {
461     data->metric.out = metric;
462   }
463 }
464
465 /**
466  * This will trigger a MPR set recalculation.
467  * @param force_change force a MPR recalculation and dijkstra trigger
468  *    even if the existing neighbor set didn't change
469  */
470 void
471 nhdp_domain_recalculate_mpr(bool force_change) {
472   struct nhdp_domain_listener *listener;
473   struct nhdp_domain *domain;
474
475   bool changed_metric[NHDP_MAXIMUM_DOMAINS];
476   bool changed_mpr[NHDP_MAXIMUM_DOMAINS];
477
478   memset(changed_metric, 0, sizeof(changed_metric));
479   memset(changed_mpr, 0, sizeof(changed_mpr));
480   
481   OONF_DEBUG(LOG_NHDP, "Recalculating MPR set?");
482   list_for_each_element(&_domain_list, domain, _node) {
483     /* recalculate the neighbor metrics and see if they changed */
484     changed_metric[domain->index] = _recalculate_neighbor_metrics(domain);
485
486     if (changed_metric[domain->index]) {
487       /* recalculate routing MPRs */
488       changed_mpr[domain->index] = _recalculate_mpr_set(domain);
489
490       if (domain->ext == _flooding_domain.ext && domain->mpr->update_mpr) {
491         /* recalculating flooding MPR */
492         domain->mpr->update_mpr(&_flooding_domain);
493       }
494     }
495
496     list_for_each_element(&_domain_listener_list, listener, _node) {
497       /* trigger domain listeners */
498       if ((force_change || changed_metric[domain->index]) && listener->metric_update) {
499         listener->metric_update(domain);
500       }
501       if ((force_change || changed_mpr[domain->index]) && listener->mpr_update) {
502         listener->mpr_update(domain);
503       }
504     }
505   }
506 }
507
508 /**
509  * @return true if this node is selected as a MPR by any other node
510  */
511 bool
512 nhdp_domain_node_is_mpr(void) {
513   return _node_is_selected_as_mpr;
514 }
515
516 /**
517  *
518  * @param mprtypes destination buffer for mpr types
519  * @param mprtypes_size size of destination buffer
520  * @param tlv pointer to mprtypes TLV, might be NULL
521  * @return number of bytes written into destination buffer
522  */
523 size_t
524 nhdp_domain_process_mprtypes_tlv(
525     uint8_t *mprtypes, size_t mprtypes_size,
526     struct rfc5444_reader_tlvblock_entry *tlv) {
527   struct nhdp_domain *domain;
528   size_t count;
529
530   if (!tlv) {
531     domain = list_first_element(&_domain_list, domain, _node);
532     mprtypes[0] = domain->ext;
533
534     return 1;
535   }
536
537   memset(mprtypes, 255, mprtypes_size);
538
539   count = 0;
540   list_for_each_element(&_domain_list, domain, _node) {
541     mprtypes[count++] = domain->ext;
542     if (count >= mprtypes_size) {
543       break;
544     }
545   }
546   return count;
547 }
548
549 /**
550  * Process an in MPR tlv for a NHDP link
551  * @param mprtypes list of extensions for MPR
552  * @param mprtypes_size length of mprtypes array
553  * @param neigh NHDP neighbor
554  * @param tlv MPR tlv context
555  */
556 void
557 nhdp_domain_process_mpr_tlv(uint8_t *mprtypes, size_t mprtypes_size,
558     struct nhdp_neighbor *neigh, struct rfc5444_reader_tlvblock_entry *tlv) {
559   struct nhdp_domain *domain;
560   size_t bit_idx, byte_idx;
561   size_t i;
562
563   neigh->local_is_flooding_mpr = false;
564   list_for_each_element(&_domain_list, domain, _node) {
565     nhdp_domain_get_neighbordata(domain, neigh)->local_is_mpr = false;
566   }
567
568   if (!tlv) {
569     return;
570   }
571
572   /* set flooding MPR flag */
573   neigh->local_is_flooding_mpr =
574       (tlv->single_value[0] & RFC7181_MPR_FLOODING) != 0;
575   OONF_DEBUG(LOG_NHDP_R, "Flooding MPR for neighbor: %s",
576       neigh->local_is_flooding_mpr ? "true" : "false");
577
578   /* set routing MPR flags */
579   for (i=0; i<mprtypes_size; i++) {
580     domain = nhdp_domain_get_by_ext(mprtypes[i]);
581     if (domain == NULL) {
582       continue;
583     }
584     bit_idx = (i + 1) & 7;
585     byte_idx = (i + 1) >> 3;
586
587     if (byte_idx >= tlv->length) {
588       continue;
589     }
590
591     nhdp_domain_get_neighbordata(domain, neigh)->local_is_mpr =
592         (tlv->single_value[byte_idx] & (1 << bit_idx)) != 0;
593
594     OONF_DEBUG(LOG_NHDP_R, "Routing MPR for neighbor in domain %u: %s",
595         domain->ext, nhdp_domain_get_neighbordata(domain, neigh)->local_is_mpr ? "true" : "false");
596   }
597
598   _node_is_selected_as_mpr = false;
599   list_for_each_element(&_domain_list, domain, _node) {
600     list_for_each_element(nhdp_db_get_neigh_list(), neigh, _global_node) {
601       if (nhdp_domain_get_neighbordata(domain, neigh)->local_is_mpr) {
602         _node_is_selected_as_mpr = true;
603         return;
604       }
605     }
606   }
607 }
608
609 /**
610  * Process an in Willingness tlv and put values into
611  * temporary storage in MPR handler object. Call
612  * nhdp_domain_store_willingness to permanently store them later.
613  * @param mprtypes list of extensions for MPR
614  * @param mprtypes_size length of mprtypes array
615  * @param tlv Willingness tlv context
616  */
617 void
618 nhdp_domain_process_willingness_tlv(
619     uint8_t *mprtypes, size_t mprtypes_size,
620     struct rfc5444_reader_tlvblock_entry *tlv) {
621   struct nhdp_domain *domain;
622   size_t idx, i;
623   uint8_t value;
624
625   _flooding_domain._tmp_willingness = RFC7181_WILLINGNESS_NEVER;
626   list_for_each_element(&_domain_list, domain, _node) {
627     domain->_tmp_willingness= RFC7181_WILLINGNESS_NEVER;
628   }
629
630   if (!tlv) {
631     return;
632   }
633
634   /* copy flooding willingness */
635   _flooding_domain._tmp_willingness
636     = tlv->single_value[0] & RFC7181_WILLINGNESS_MASK;
637   OONF_DEBUG(LOG_NHDP_R, "Received flooding willingness: %u",
638       _flooding_domain._tmp_willingness);
639
640   for (i=0; i<mprtypes_size; i++) {
641     domain = nhdp_domain_get_by_ext(mprtypes[i]);
642     if (domain == NULL) {
643       continue;
644     }
645
646     idx = (i + 1) / 2;
647     if (idx >= tlv->length) {
648       continue;
649     }
650
651     value = tlv->single_value[idx];
652     if ((domain->index & 1) == 0) {
653       value >>= RFC7181_WILLINGNESS_SHIFT;
654     }
655     else {
656       value &= RFC7181_WILLINGNESS_MASK;
657     }
658
659     domain->_tmp_willingness = value;
660
661     OONF_DEBUG(LOG_NHDP_R, "Received routing willingness for domain %u: %u",
662         domain->ext, domain->_tmp_willingness);
663   }
664 }
665
666 /**
667  * Stores the willingness data processed by
668  * nhdp_domain_process_willingness_tlv() into a neighbor object
669  * @param neigh NHDP neighbor
670  */
671 void
672 nhdp_domain_store_willingness(struct nhdp_neighbor *neigh) {
673   struct nhdp_neighbor_domaindata *neighdata;
674   struct nhdp_domain *domain;
675
676   neigh->flooding_willingness = _flooding_domain._tmp_willingness;
677   OONF_DEBUG(LOG_NHDP_R, "Set flooding willingness: %u",
678       neigh->flooding_willingness);
679
680   list_for_each_element(&_domain_list, domain, _node) {
681     neighdata = nhdp_domain_get_neighbordata(domain, neigh);
682     neighdata->willingness = domain->_tmp_willingness;
683     OONF_DEBUG(LOG_NHDP_R, "Set routing willingness for domain %u: %u",
684         domain->ext, neighdata->willingness);
685   }
686 }
687
688 /**
689  * Generate MPRTYPES tlv value
690  * @param mprtypes pointer to destination buffer for value
691  * @param mprtypes_size length of destination buffer
692  * @return number of bytes written into buffer
693  */
694 size_t
695 nhdp_domain_encode_mprtypes_tlvvalue(
696     uint8_t *mprtypes, size_t mprtypes_size) {
697   struct nhdp_domain *domain;
698   size_t count;
699
700   count = 0;
701   list_for_each_element(&_domain_list, domain, _node) {
702     mprtypes[count++] = domain->ext;
703
704     if (count >= mprtypes_size) {
705       break;
706     }
707   }
708
709   return count;
710 }
711
712 /**
713  * Calculates the tlvvalue of a MPR tlv
714  *
715  * @param tlvvalue destination for value of MPR tlv
716  * @param tlvsize length of tlv value
717  * @param neigh pointer to NHDP neighbor for MPR tlv
718  * @return length of tlvvalue, 0 if an error happened
719  */
720 size_t
721 nhdp_domain_encode_mpr_tlvvalue(
722     uint8_t *tlvvalue, size_t tlvsize, struct nhdp_neighbor *neigh) {
723   struct nhdp_domain *domain;
724   size_t bit_idx, byte_idx, len;
725
726   memset(tlvvalue, 0, tlvsize);
727   len = 0;
728   /* set flooding MPR flag */
729   if (neigh->neigh_is_flooding_mpr) {
730     tlvvalue[0] |= RFC7181_MPR_FLOODING;
731   }
732
733   OONF_DEBUG(LOG_NHDP_W, "Set flooding MPR: %s",
734       neigh->neigh_is_flooding_mpr ? "true" : "false");
735
736   list_for_each_element(&_domain_list, domain, _node) {
737     bit_idx = (domain->index + 1) & 7;
738     byte_idx = (domain->index + 1) >> 3;
739
740     if (byte_idx >= tlvsize) {
741       return 0;
742     }
743     if (byte_idx+1 > len) {
744       len = byte_idx + 1;
745     }
746
747     if (nhdp_domain_get_neighbordata(domain, neigh)->neigh_is_mpr) {
748       tlvvalue[byte_idx] |= (1 << bit_idx);
749     }
750
751     OONF_DEBUG(LOG_NHDP_W, "Set routing MPR for domain %u: %s",
752         domain->ext, nhdp_domain_get_neighbordata(domain, neigh)->neigh_is_mpr ? "true" : "false");
753   }
754   return len;
755 }
756
757 /**
758  * Calculates the tlvvalue of a Willingness tlv
759  * @param tlvvalue destination array
760  * @param tlvsize length of destination array
761  * @return length of tlvvalue, 0 if an error happened
762  */
763 size_t
764 nhdp_domain_encode_willingness_tlvvalue(uint8_t *tlvvalue, size_t tlvsize) {
765   struct nhdp_domain *domain;
766   uint8_t value;
767   size_t idx, len;
768
769   memset(tlvvalue, 0, tlvsize);
770   len = 0;
771
772   /* set flooding willingness */
773   tlvvalue[0] = _flooding_domain.local_willingness;
774   OONF_DEBUG(LOG_NHDP_W, "Set flooding willingness: %u",
775       _flooding_domain.local_willingness);
776
777   /* set routing willingness */
778   list_for_each_element(&_domain_list, domain, _node) {
779     idx = (domain->index + 1) / 2;
780     if (idx >= tlvsize) {
781       return -1;
782     }
783     if (idx+1 > len) {
784       len = idx + 1;
785     }
786
787     value = domain->local_willingness & RFC7181_WILLINGNESS_MASK;
788
789     if ((domain->index & 1) == 0) {
790       value <<= RFC7181_WILLINGNESS_SHIFT;
791     }
792
793     OONF_DEBUG(LOG_NHDP_W, "Set routing willingness for domain %u: %x"
794         " (%"PRINTF_SIZE_T_SPECIFIER")",
795         domain->ext, value, idx);
796
797     tlvvalue[idx] |= value;
798   }
799
800   return len;
801 }
802
803 /**
804  * Sets a new flodding MPR algorithm
805  * @param mpr_name name of MPR algorithm
806  * @param willingness of MPR algorithm
807  */
808 void
809 nhdp_domain_set_flooding_mpr(const char *mpr_name, uint8_t willingness) {
810   _apply_mpr(&_flooding_domain, mpr_name, willingness);
811 }
812
813 /**
814  * @return the virtual flooding domain
815  */
816 const struct nhdp_domain *
817 nhdp_domain_get_flooding_domain(void) {
818   return &_flooding_domain;
819 }
820 /**
821  * Sets the incoming metric of a link. This is the only function external
822  * code should use to commit the calculated metric values to the nhdp db.
823  * @param metric NHDP domain metric
824  * @param lnk NHDP link
825  * @param metric_in incoming metric value for NHDP link
826  * @return true if metric changed, false otherwise
827  */
828 bool
829 nhdp_domain_set_incoming_metric(struct nhdp_domain_metric *metric,
830     struct nhdp_link *lnk, uint32_t metric_in) {
831   struct nhdp_link_domaindata *linkdata;
832   struct nhdp_domain *domain;
833   bool changed;
834
835   changed = false;
836   list_for_each_element(&_domain_list, domain, _node) {
837     if (domain->metric == metric) {
838       linkdata = nhdp_domain_get_linkdata(domain, lnk);
839       changed |= (linkdata->metric.in != metric_in);
840       linkdata->metric.in = metric_in;
841     }
842   }
843   return changed;
844 }
845
846 /**
847  * @return list of domains
848  */
849 struct list_entity *
850 nhdp_domain_get_list(void) {
851   return &_domain_list;
852 }
853
854 /**
855  * @return list of event listeners for domain metric/mpr triggers
856  */
857 struct list_entity *
858 nhdp_domain_get_listener_list(void) {
859   return &_domain_listener_list;
860 }
861
862 /**
863  * Recalculate the neighbor metrics of a NHDP domain
864  * @param domain NHDP domain
865  * @return if neighbor metric or two-hop link metric changed
866  */
867 static bool
868 _recalculate_neighbor_metrics(struct nhdp_domain *domain) {
869   struct nhdp_neighbor *neigh;
870   bool changed;
871
872   /* recalculate the neighbor metrics and see if they changed */
873   changed = false;
874   list_for_each_element(nhdp_db_get_neigh_list(), neigh, _global_node) {
875     changed |= _recalculate_neighbor_metric(domain, neigh);
876   }
877
878   if (changed) {
879     OONF_DEBUG(LOG_NHDP, "Domain ext %u metric changed", domain->ext);
880   }
881   return changed;
882 }
883
884 /**
885  * Recalculate the MPR set of a NHDP domain
886  * @param domain nhdp domain
887  * @return true if the MPR set changed
888  */
889 static bool
890 _recalculate_mpr_set(struct nhdp_domain *domain) {
891   struct nhdp_neighbor *neigh;
892   struct nhdp_neighbor_domaindata *neighdata;
893
894   if (!domain->mpr->update_mpr) {
895     return false;
896   }
897
898   /* remember old MPR set */
899   list_for_each_element(nhdp_db_get_neigh_list(), neigh, _global_node) {
900     neighdata = nhdp_domain_get_neighbordata(domain, neigh);
901     neighdata->_neigh_was_mpr = neighdata->neigh_is_mpr;
902   }
903
904   /* update MPR set */
905   domain->mpr->update_mpr(domain);
906
907   /* check for changes */
908   list_for_each_element(nhdp_db_get_neigh_list(), neigh, _global_node) {
909     neighdata = nhdp_domain_get_neighbordata(domain, neigh);
910     if (neighdata->_neigh_was_mpr != neighdata->neigh_is_mpr) {
911       OONF_DEBUG(LOG_NHDP, "Domain ext %u MPR set changed", domain->ext);
912       return true;
913     }
914   }
915   return false;
916 }
917
918 /**
919  * Recalculate the 'best link/metric' values of a neighbor
920  * and check for two-hop outgoing link metric changes
921  * @param domain NHDP domain
922  * @param neigh NHDP neighbor
923  * @param neighdata NHDP neighbor domaindata
924  * @return true neighbor metric or the two-hop link metrics changed
925  */
926 static bool
927 _recalculate_neighbor_metric(
928     struct nhdp_domain *domain,
929     struct nhdp_neighbor *neigh) {
930   struct nhdp_link *lnk;
931   struct nhdp_link_domaindata *linkdata;
932   struct nhdp_l2hop *l2hop;
933   struct nhdp_l2hop_domaindata *l2hopdata;
934   struct nhdp_neighbor_domaindata *neighdata;
935   uint32_t old_outgoing;
936   bool changed;
937 #ifdef OONF_LOG_DEBUG_INFO
938   struct netaddr_str nbuf;
939 #endif
940
941   neighdata = nhdp_domain_get_neighbordata(domain, neigh);
942   changed = false;
943
944     /* copy old metric value */
945   old_outgoing = neighdata->metric.out;
946
947   /* reset metric */
948   neighdata->metric.in = RFC7181_METRIC_INFINITE;
949   neighdata->metric.out = RFC7181_METRIC_INFINITE;
950
951   /* reset best link */
952   neighdata->best_link = NULL;
953   neighdata->best_link_ifindex = 0;
954
955   OONF_DEBUG(LOG_NHDP, "Recalculate neighbor %s metrics (ext %u):",
956       netaddr_to_string(&nbuf, &neigh->originator), domain->ext);
957
958   /* get best metric */
959   list_for_each_element(&neigh->_links, lnk, _neigh_node) {
960     if (lnk->status != NHDP_LINK_SYMMETRIC) {
961       continue;
962     }
963
964     linkdata = nhdp_domain_get_linkdata(domain, lnk);
965     if (linkdata->metric.out < neighdata->metric.out) {
966       OONF_DEBUG(LOG_NHDP, "Link on if %s has better outgoing metric: %u",
967               lnk->local_if->os_if_listener.data->name,
968               linkdata->metric.out);
969
970       neighdata->metric.out = linkdata->metric.out;
971       neighdata->best_link = lnk;
972     }
973     if (linkdata->metric.in < neighdata->metric.in) {
974       OONF_DEBUG(LOG_NHDP, "Link on if %s has better incoming metric: %u",
975               lnk->local_if->os_if_listener.data->name,
976               linkdata->metric.in);
977       neighdata->metric.in = linkdata->metric.in;
978     }
979
980     /* check for changes in outgoing 2-hop metrics */
981     avl_for_each_element(&lnk->_2hop, l2hop, _link_node) {
982       l2hopdata = nhdp_domain_get_l2hopdata(domain, l2hop);
983
984       changed |= l2hopdata->metric.out != l2hopdata->_last_used_outgoing_metric;
985       l2hopdata->_last_used_outgoing_metric = l2hopdata->metric.out;
986     }
987   }
988
989   if (neighdata->best_link != NULL) {
990     OONF_DEBUG(LOG_NHDP, "Best link if: %s",
991         nhdp_interface_get_if_listener(neighdata->best_link->local_if)->data->name);
992     neighdata->best_link_ifindex =
993         nhdp_interface_get_if_listener(neighdata->best_link->local_if)->data->index;
994   }
995   return changed || neighdata->metric.out != old_outgoing;
996 }
997
998 /**
999  * Add a new domain to the NHDP system
1000  * @param ext TLV extension type used for new domain
1001  * @return pointer to new domain, NULL, if out of memory or
1002  *   maximum number of domains has been reached.
1003  */
1004 struct nhdp_domain *
1005 nhdp_domain_add(uint8_t ext) {
1006   struct nhdp_domain *domain;
1007   int i;
1008
1009   domain = nhdp_domain_get_by_ext(ext);
1010   if (domain) {
1011     return domain;
1012   }
1013
1014   if (_domain_counter == NHDP_MAXIMUM_DOMAINS) {
1015     OONF_WARN(LOG_NHDP, "Maximum number of NHDP domains reached: %d",
1016         NHDP_MAXIMUM_DOMAINS);
1017     return NULL;
1018   }
1019
1020   /* initialize new domain */
1021   domain = oonf_class_malloc(&_domain_class);
1022   if (domain == NULL) {
1023     return NULL;
1024   }
1025
1026   domain->ext = ext;
1027   domain->index = _domain_counter++;
1028   domain->metric = &_no_metric;
1029   domain->mpr = &_everyone_mprs;
1030
1031   domain->mpr->_refcount++;
1032   domain->metric->_refcount++;
1033
1034   /* initialize metric TLVs */
1035   for (i=0; i<4; i++) {
1036     domain->_metric_addrtlvs[i].type = RFC7181_ADDRTLV_LINK_METRIC;
1037     domain->_metric_addrtlvs[i].exttype = domain->ext;
1038
1039     rfc5444_writer_register_addrtlvtype(&_protocol->writer,
1040         &domain->_metric_addrtlvs[i], -1);
1041   }
1042
1043   /* add to domain list */
1044   list_add_tail(&_domain_list, &domain->_node);
1045
1046   oonf_class_event(&_domain_class, domain,OONF_OBJECT_ADDED);
1047   return domain;
1048 }
1049
1050 /**
1051  * Configure a NHDP domain to a metric and a MPR algorithm
1052  * @param ext TLV extension type used for new domain
1053  * @param metric_name name of the metric algorithm to be used,
1054  *   might be CFG_DOMAIN_NO_METRIC (for hopcount metric)
1055  *   or CFG_DOMAIN_ANY_METRIC (for a metric the NHDP core should
1056  *   choose).
1057  * @param mpr_name name of the MPR algorithm to be used,
1058  *   might be CFG_DOMAIN_NO_MPR (every node is MPR)
1059  *   or CFG_DOMAIN_ANY_MPR (for a MPR the NHDP core should
1060  *   choose).
1061  * @param willingness routing willingness for domain
1062  * @return pointer to configured domain, NULL, if out of memory or
1063  *   maximum number of domains has been reached.
1064  */
1065 struct nhdp_domain *
1066 nhdp_domain_configure(uint8_t ext, const char *metric_name,
1067     const char *mpr_name, uint8_t willingness) {
1068   struct nhdp_domain *domain;
1069
1070   domain = nhdp_domain_add(ext);
1071   if (domain == NULL) {
1072     return NULL;
1073   }
1074
1075   OONF_DEBUG(LOG_NHDP, "Configure domain %u to metric=%s",
1076       domain->index, metric_name);
1077   _apply_metric(domain, metric_name);
1078
1079   OONF_DEBUG(LOG_NHDP, "Configure domain %u to mpr=%s, willingness=%u",
1080       domain->index, mpr_name, willingness);
1081   _apply_mpr(domain, mpr_name, willingness);
1082
1083   oonf_class_event(&_domain_class, domain, OONF_OBJECT_CHANGED);
1084
1085   return domain;
1086 }
1087
1088 /**
1089  * Apply a new metric algorithm to a NHDP domain
1090  * @param domain pointer to NHDP domain
1091  * @param metric_name name of the metric algorithm to be used,
1092  *   might be CFG_DOMAIN_NO_METRIC (for hopcount metric)
1093  *   or CFG_DOMAIN_ANY_METRIC (for a metric the NHDP core should
1094  *   choose).
1095  */
1096 static void
1097 _apply_metric(struct nhdp_domain *domain, const char *metric_name) {
1098   struct nhdp_domain_metric *metric;
1099
1100   /* check if we have to remove the old metric first */
1101   if (strcasecmp(domain->metric_name, metric_name) == 0) {
1102     /* nothing to do, we already have the right metric */
1103     return;
1104   }
1105
1106   if (domain->metric != &_no_metric) {
1107     _remove_metric(domain);
1108   }
1109
1110   /* Handle wildcard metric name first */
1111   if (strcasecmp(metric_name, CFG_DOMAIN_ANY_METRIC_MPR) == 0
1112       && !avl_is_empty(&_domain_metrics)) {
1113     metric_name = avl_first_element(&_domain_metrics, metric, _node)->name;
1114   }
1115
1116   /* look for metric implementation */
1117   metric = avl_find_element(&_domain_metrics, metric_name, metric, _node);
1118   if (metric == NULL) {
1119     metric = &_no_metric;
1120   }
1121
1122   /* copy new metric name */
1123   strscpy(domain->metric_name, metric->name, sizeof(domain->metric_name));
1124
1125   /* link domain and metric */
1126   domain->metric->_refcount--;
1127   domain->metric = metric;
1128
1129   /* activate metric */
1130   if (metric->_refcount == 0 && metric->enable) {
1131     metric->enable();
1132   }
1133   metric->_refcount++;
1134 }
1135
1136 /**
1137  * Reset the metric of a NHDP domain to hopcount
1138  * @param domain pointer to NHDP domain
1139  */
1140 static void
1141 _remove_metric(struct nhdp_domain *domain) {
1142   domain->metric->_refcount--;
1143   if (!domain->metric->_refcount && domain->metric->disable) {
1144     domain->metric->disable();
1145   }
1146   strscpy(domain->metric_name, CFG_DOMAIN_NO_METRIC_MPR, sizeof(domain->metric_name));
1147   domain->metric = &_no_metric;
1148   domain->metric->_refcount++;
1149 }
1150
1151 /**
1152  * Apply a new MPR algorithm to a NHDP domain
1153  * @param domain pointer to NHDP domain
1154  * @param mpr_name name of the MPR algorithm to be used,
1155  *   might be CFG_DOMAIN_NO_MPR (every node is MPR)
1156  *   or CFG_DOMAIN_ANY_MPR (for a MPR the NHDP core should
1157  *   choose).
1158  * @param willingness routing willingness for domain
1159  */
1160 static void
1161 _apply_mpr(struct nhdp_domain *domain, const char *mpr_name, uint8_t willingness) {
1162   struct nhdp_domain_mpr *mpr;
1163
1164   domain->local_willingness = willingness;
1165
1166   /* check if we have to remove the old mpr first */
1167   if (strcasecmp(domain->mpr_name, mpr_name) == 0) {
1168     /* nothing else to do, we already have the right MPR */
1169     return;
1170   }
1171   if (domain->mpr != &_everyone_mprs) {
1172     /* replace old MPR algorithm with "everyone MPR" */
1173     _remove_mpr(domain);
1174   }
1175
1176   /* Handle wildcard mpr name first */
1177   if (strcasecmp(mpr_name, CFG_DOMAIN_ANY_METRIC_MPR) == 0
1178       && !avl_is_empty(&_domain_mprs)) {
1179     mpr_name = avl_first_element(&_domain_mprs, mpr, _node)->name;
1180   }
1181
1182   /* look for mpr implementation */
1183   mpr = avl_find_element(&_domain_mprs, mpr_name, mpr, _node);
1184   if (mpr == NULL) {
1185     mpr = &_everyone_mprs;
1186   }
1187
1188   /* copy new metric name */
1189   strscpy(domain->mpr_name, mpr->name, sizeof(domain->mpr_name));
1190
1191   /* link domain and mpr */
1192   domain->mpr->_refcount--;
1193   domain->mpr = mpr;
1194
1195   /* activate mpr */
1196   if (mpr->_refcount == 0 && mpr->enable) {
1197     mpr->enable();
1198   }
1199   mpr->_refcount++;
1200 }
1201
1202 /**
1203  * Reset the MPR of a NHDP domain to 'everyone is MPR'
1204  * @param domain pointer to NHDP domain
1205  */
1206 static void
1207 _remove_mpr(struct nhdp_domain *domain) {
1208   domain->mpr->_refcount--;
1209   if (!domain->mpr->_refcount && domain->mpr->disable) {
1210     domain->mpr->disable();
1211   }
1212   strscpy(domain->mpr_name, CFG_DOMAIN_NO_METRIC_MPR, sizeof(domain->mpr_name));
1213   domain->mpr = &_everyone_mprs;
1214   domain->mpr->_refcount++;
1215 }
1216
1217 static void
1218 _cb_update_everyone_mpr(struct nhdp_domain *domain) {
1219   struct nhdp_neighbor *neigh;
1220   struct nhdp_neighbor_domaindata *domaindata;
1221
1222   list_for_each_element(nhdp_db_get_neigh_list(), neigh, _global_node) {
1223     if (&_flooding_domain == domain) {
1224       neigh->neigh_is_flooding_mpr =
1225           neigh->flooding_willingness > RFC7181_WILLINGNESS_NEVER;
1226     }
1227     else if (domain->mpr == &_everyone_mprs) {
1228       domaindata = nhdp_domain_get_neighbordata(domain, neigh);
1229       domaindata->neigh_is_mpr =
1230           domaindata->willingness > RFC7181_WILLINGNESS_NEVER;
1231     }
1232   }
1233 }
1234
1235 /**
1236  * Default implementation to convert a link metric value into text
1237  * @param buf pointer to metric output buffer
1238  * @param metric link metric value
1239  * @return pointer to string representation of linkmetric value
1240  */
1241 static const char *
1242 _link_to_string(struct nhdp_metric_str *buf, uint32_t metric) {
1243   snprintf(buf->buf, sizeof(*buf), "0x%x", metric);
1244
1245   return buf->buf;
1246 }
1247
1248 /**
1249  * Default implementation to convert a path metric value into text
1250  * @param buf pointer to metric output buffer
1251  * @param metric path metric value
1252  * @param hopcount hopcount of path
1253  * @return pointer to string representation of path metric value
1254  */
1255 static const char *
1256 _path_to_string(struct nhdp_metric_str *buf, uint32_t metric,
1257     uint8_t hopcount __attribute((unused))) {
1258   snprintf(buf->buf, sizeof(*buf), "0x%x", metric);
1259
1260   return buf->buf;
1261 }
1262
1263 static const char *
1264 _int_to_string(struct nhdp_metric_str *buf,
1265     struct nhdp_link *lnk __attribute__((unused))) {
1266   strscpy(buf->buf, "-", sizeof(*buf));
1267   return buf->buf;
1268 }