Merge branch 'master' into mpr_rework
[oonf.git] / src-plugins / nhdp / ff_dat_metric / ff_dat_metric.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 <sys/types.h>
47 #include <sys/stat.h>
48 #include <errno.h>
49 #include <fcntl.h>
50 #include <stdio.h>
51
52 #include "common/common_types.h"
53 #include "common/isonumber.h"
54 #include "common/autobuf.h"
55 #include "core/oonf_cfg.h"
56 #include "core/oonf_logging.h"
57 #include "core/oonf_subsystem.h"
58 #include "subsystems/oonf_class.h"
59 #include "subsystems/oonf_layer2.h"
60 #include "subsystems/oonf_rfc5444.h"
61 #include "subsystems/oonf_timer.h"
62
63 #include "nhdp/nhdp.h"
64 #include "nhdp/nhdp_domain.h"
65 #include "nhdp/nhdp_interfaces.h"
66
67 #include "ff_dat_metric/ff_dat_metric.h"
68
69 /* Definitions */
70 enum {
71   DAT_SAMPLING_COUNT = 32,
72 };
73
74 /**
75  * Configuration settings of DATFF Metric
76  */
77 struct ff_dat_if_config {
78   /*! Interval between two updates of the metric */
79   uint64_t interval;
80
81   /*! true if metric should include link speed */
82   bool ett;
83
84   /*! selects how loss should be scaled */
85   int loss_exponent;
86
87   /*! true if MIC factor should be applied to metric */
88   bool mic;
89
90   /*! true if metric should include unicast into calculation */
91   bool accept_unicast;
92
93   /*! timer for sampling interface data */
94   struct oonf_timer_instance _sampling_timer;
95
96   /*! true if we registered the interface */
97   bool registered;
98 };
99
100 /**
101  * a single history memory cell, stores the metric
102  * data for a single update interval
103  */
104 struct link_datff_bucket {
105   /*! number of RFC5444 packets received in time interval */
106   uint32_t received;
107
108   /*! sum of received and lost RFC5444 packets in time interval */
109   uint32_t total;
110
111   /*! link speed scaled to "minimum speed = 1" */
112   uint32_t scaled_speed;
113 };
114
115 /**
116  * Additional data for a nhdp_link class for metric calculation
117  */
118 struct link_datff_data {
119   /*! timer for measuring lost hellos when no further packets are received */
120   struct oonf_timer_instance hello_lost_timer;
121
122   /*! back pointer to NHDP link */
123   struct nhdp_link *nhdp_link;
124
125   /*! true if buckets contain data */
126   bool contains_data;
127
128   /*! number of missed hellos based on timeouts since last received packet */
129   uint32_t missed_hellos;
130
131   /*! current position in history ringbuffer */
132   uint16_t activePtr;
133
134   /*! last received packet sequence number */
135   uint16_t last_seq_nr;
136
137   /*! remember the last transmitted packet loss for hysteresis (scaled by 1000) */
138   int64_t last_packet_success_rate;
139
140   /*! last known hello interval */
141   uint64_t hello_interval;
142
143   /*! estimated number of neighbors of this link */
144   uint32_t link_neigborhood;
145
146   /*! history ringbuffer */
147   struct link_datff_bucket buckets[DAT_SAMPLING_COUNT];
148 };
149
150 /* prototypes */
151 static void _early_cfg_init(void);
152 static int _init(void);
153 static void _cleanup(void);
154
155 static void _cb_enable_metric(void);
156 static void _cb_disable_metric(void);
157
158 static void _cb_link_added(void *);
159 static void _cb_link_changed(void *);
160 static void _cb_link_removed(void *);
161
162 static void _cb_nhdpif_added(void *);
163 static void _cb_nhdpif_removed(void *);
164
165 static void _cb_dat_sampling(struct oonf_timer_instance *);
166 static void _calculate_link_neighborhood(struct nhdp_link *lnk,
167     struct link_datff_data *ldata);
168 static int _calculate_dynamic_loss_exponent(int link_neigborhood);
169 static uint32_t _apply_packet_loss(
170     struct ff_dat_if_config *ifconfig, struct nhdp_link *lnk,
171     struct link_datff_data *ldata,
172     uint32_t metric, uint32_t received, uint32_t total);
173
174 static void _cb_hello_lost(struct oonf_timer_instance *);
175
176 static bool _shall_process_packet(
177     struct nhdp_interface *, struct ff_dat_if_config *ifconfig);
178
179 static enum rfc5444_result _cb_process_packet(
180       struct rfc5444_reader_tlvblock_context *context);
181
182 static void _reset_missed_hello_timer(struct link_datff_data *);
183
184 static const char *_link_to_string(
185     struct nhdp_metric_str *buf, uint32_t metric);
186 static const char *_path_to_string(
187     struct nhdp_metric_str *buf, uint32_t metric, uint8_t hopcount);
188 static const char *_int_link_to_string(struct nhdp_metric_str *,
189     struct nhdp_link *);
190
191 static void _cb_cfg_changed(void);
192
193 /* plugin declaration */
194
195 /**
196  * loss scaling options
197  */
198 enum idx_loss_scaling {
199   /*! linear loss scaling */
200   IDX_LOSS_LINEAR,
201
202   /*! quadratic loss scaling */
203   IDX_LOSS_QUADRATIC,
204
205   /*! cubic loss scaling */
206   IDX_LOSS_CUBIC,
207
208   /*! dynamic loss scaling */
209   IDX_LOSS_DYNAMIC,
210 };
211 static const char *LOSS_SCALING[] = {
212   [IDX_LOSS_LINEAR]    = "linear",
213   [IDX_LOSS_QUADRATIC] = "quadratic",
214   [IDX_LOSS_CUBIC]     = "cubic",
215   [IDX_LOSS_DYNAMIC]   = "dynamic",
216 };
217
218 static struct cfg_schema_entry _datff_entries[] = {
219   CFG_MAP_CLOCK_MIN(ff_dat_if_config, interval, "ffdat_interval", "1.0",
220       "Time interval between recalculations of metric", 100),
221   CFG_MAP_BOOL(ff_dat_if_config, ett, "ffdat_airtime", "true",
222       "Activates the handling of linkspeed within the metric, set to false to"
223       " downgrade to ETX metric"),
224   CFG_MAP_CHOICE(ff_dat_if_config, loss_exponent, "ffdat_loss_exponent", "linear",
225       "scaling of the packet loss influence on the metric", LOSS_SCALING),
226   CFG_MAP_BOOL(ff_dat_if_config, mic, "ffdat_mic", "false",
227       "Activates the MIC penalty-factor for link metrics"),
228   CFG_MAP_BOOL(ff_dat_if_config, accept_unicast, "ffdat_unicast", "false",
229       "Include unicast into metric calculation"),
230 };
231
232 /* Subsystem definition */
233 static struct cfg_schema_section _datff_section = {
234   .type = CFG_INTERFACE_SECTION,
235   .mode = CFG_INTERFACE_SECTION_MODE,
236   .cb_delta_handler = _cb_cfg_changed,
237   .entries = _datff_entries,
238   .entry_count = ARRAYSIZE(_datff_entries),
239 };
240
241 static const char *_dependencies[] = {
242   OONF_CLASS_SUBSYSTEM,
243   OONF_LAYER2_SUBSYSTEM,
244   OONF_RFC5444_SUBSYSTEM,
245   OONF_TIMER_SUBSYSTEM,
246   OONF_NHDP_SUBSYSTEM,
247   OONF_OS_INTERFACE_SUBSYSTEM,
248 };
249 static struct oonf_subsystem _nhdp_ffdat_subsystem = {
250   .name = OONF_FF_DAT_METRIC_SUBSYSTEM,
251   .dependencies = _dependencies,
252   .dependencies_count = ARRAYSIZE(_dependencies),
253   .descr = "NHDP Funkfeuer Directional Airtime Metric plugin",
254   .author = "Henning Rogge",
255
256   .cfg_section = &_datff_section,
257
258   .early_cfg_init = _early_cfg_init,
259   .init = _init,
260   .cleanup = _cleanup,
261 };
262 DECLARE_OONF_PLUGIN(_nhdp_ffdat_subsystem);
263
264 /* RFC5444 packet listener */
265 static struct oonf_rfc5444_protocol *_protocol;
266
267 static struct rfc5444_reader_tlvblock_consumer _packet_consumer = {
268   .order = RFC5444_LQ_PARSER_PRIORITY,
269   .default_msg_consumer = true,
270   .start_callback = _cb_process_packet,
271 };
272
273 /* storage extension and listeners */
274 static struct oonf_class_extension _link_extenstion = {
275   .ext_name = "datff linkmetric",
276   .class_name = NHDP_CLASS_LINK,
277   .size = sizeof(struct link_datff_data),
278
279   .cb_add = _cb_link_added,
280   .cb_change = _cb_link_changed,
281   .cb_remove = _cb_link_removed,
282 };
283
284 static struct oonf_class_extension _nhdpif_extenstion = {
285   .ext_name = "datff linkmetric",
286   .class_name = NHDP_CLASS_INTERFACE,
287   .size = sizeof(struct ff_dat_if_config),
288
289   .cb_add = _cb_nhdpif_added,
290   .cb_remove = _cb_nhdpif_removed,
291 };
292
293 /* timer for sampling in RFC5444 packets */
294 static struct oonf_timer_class _sampling_timer_info = {
295   .name = "Sampling timer for DATFF-metric",
296   .callback = _cb_dat_sampling,
297   .periodic = true,
298 };
299
300 /* timer class to measure interval between Hellos */
301 static struct oonf_timer_class _hello_lost_info = {
302   .name = "Hello lost timer for DATFF-metric",
303   .callback = _cb_hello_lost,
304 };
305
306 /* nhdp metric handler */
307 static struct nhdp_domain_metric _datff_handler = {
308   .name = OONF_FF_DAT_METRIC_SUBSYSTEM,
309
310   .metric_minimum = DATFF_LINKCOST_MINIMUM,
311   .metric_maximum = DATFF_LINKCOST_MAXIMUM,
312
313   .link_to_string = _link_to_string,
314   .path_to_string = _path_to_string,
315   .internal_link_to_string = _int_link_to_string,
316
317   .enable = _cb_enable_metric,
318   .disable = _cb_disable_metric,
319 };
320
321 /* Temporary buffer to sort incoming link speed for median calculation */
322 static int _rx_sort_array[DAT_SAMPLING_COUNT] = { 0 };
323
324 /* ff_dat has multiple logging targets */
325 enum oonf_log_source LOG_FF_DAT;
326 enum oonf_log_source LOG_FF_DAT_RAW;
327
328 /**
329  * Initialize additional logging sources for ffdat
330  */
331 static void
332 _early_cfg_init(void) {
333   LOG_FF_DAT = _nhdp_ffdat_subsystem.logging;
334   LOG_FF_DAT_RAW = oonf_log_register_source(OONF_FF_DAT_METRIC_SUBSYSTEM"_raw");
335 }
336
337
338 /**
339  * Initialize plugin
340  * @return -1 if an error happened, 0 otherwise
341  */
342 static int
343 _init(void) {
344   if (nhdp_domain_metric_add(&_datff_handler)) {
345     return -1;
346   }
347
348   if (oonf_class_extension_add(&_nhdpif_extenstion)) {
349     nhdp_domain_metric_remove(&_datff_handler);
350     return -1;
351   }
352   if (oonf_class_extension_add(&_link_extenstion)) {
353     oonf_class_extension_remove(&_link_extenstion);
354     nhdp_domain_metric_remove(&_datff_handler);
355     return -1;
356   }
357   oonf_timer_add(&_sampling_timer_info);
358   oonf_timer_add(&_hello_lost_info);
359
360   _protocol = oonf_rfc5444_get_default_protocol();
361
362   oonf_rfc5444_add_protocol_pktseqno(_protocol);
363   return 0;
364 }
365
366 /**
367  * Cleanup plugin
368  */
369 static void
370 _cleanup(void) {
371   struct nhdp_interface *nhdp_if, *nhdp_if_it;
372   struct ff_dat_if_config *ifconfig;
373
374   avl_for_each_element_safe(nhdp_interface_get_tree(), nhdp_if, _node, nhdp_if_it) {
375     ifconfig = oonf_class_get_extension(&_nhdpif_extenstion, nhdp_if);
376     if (ifconfig->registered) {
377       nhdp_interface_remove(nhdp_if);
378     }
379   }
380
381   /* remove metric from core */
382   nhdp_domain_metric_remove(&_datff_handler);
383
384   oonf_rfc5444_remove_protocol_pktseqno(_protocol);
385   _protocol = NULL;
386
387   oonf_class_extension_remove(&_link_extenstion);
388   oonf_class_extension_remove(&_nhdpif_extenstion);
389
390   oonf_timer_remove(&_sampling_timer_info);
391   oonf_timer_remove(&_hello_lost_info);
392 }
393
394 /**
395  * Enable metric calculation
396  */
397 static void
398 _cb_enable_metric(void) {
399   struct nhdp_interface *nhdpif;
400   struct nhdp_link *lnk;
401
402   avl_for_each_element(nhdp_interface_get_tree(), nhdpif, _node) {
403     _cb_nhdpif_added(nhdpif);
404   }
405   list_for_each_element(nhdp_db_get_link_list(), lnk, _global_node) {
406     _cb_link_added(lnk);
407   }
408
409   rfc5444_reader_add_packet_consumer(&_protocol->reader, &_packet_consumer, NULL, 0);
410 }
411
412 /**
413  * Disable metric calculation
414  */
415 static void
416 _cb_disable_metric(void) {
417   struct nhdp_interface *nhdpif;
418   struct nhdp_link *lnk;
419
420   rfc5444_reader_remove_packet_consumer(&_protocol->reader, &_packet_consumer);
421
422   list_for_each_element(nhdp_db_get_link_list(), lnk, _global_node) {
423     _cb_link_removed(lnk);
424   }
425   avl_for_each_element(nhdp_interface_get_tree(), nhdpif, _node) {
426     _cb_nhdpif_removed(nhdpif);
427   }
428 }
429
430 /**
431  * Callback triggered when a new nhdp link is added
432  * @param ptr nhdp link
433  */
434 static void
435 _cb_link_added(void *ptr) {
436   struct link_datff_data *data;
437   struct nhdp_link *lnk;
438   size_t i;
439
440   lnk = ptr;
441   data = oonf_class_get_extension(&_link_extenstion, lnk);
442
443   memset(data, 0, sizeof(*data));
444   // data->contains_data = false;
445
446   for (i = 0; i<ARRAYSIZE(data->buckets); i++) {
447     data->buckets[i].total = 1;
448     // data->buckets[i].scaled_speed = 0;
449   }
450
451   /* initialize 'hello lost' timer for link */
452   data->hello_lost_timer.class = &_hello_lost_info;
453
454   if (lnk->itime_value > 0) {
455     data->hello_interval = lnk->itime_value;
456   }
457   else {
458     data->hello_interval = lnk->vtime_value;
459   }
460
461   /* start timer */
462   _reset_missed_hello_timer(data);
463
464   /* minimal value possible for success rate */
465   data->last_packet_success_rate = 1000ll;
466 }
467
468 /**
469  * Callback triggered when a new nhdp link is changed
470  * @param ptr nhdp link
471  */
472 static void
473 _cb_link_changed(void *ptr) {
474   struct link_datff_data *data;
475   struct nhdp_link *lnk;
476
477   lnk = ptr;
478   data = oonf_class_get_extension(&_link_extenstion, lnk);
479
480   if (lnk->itime_value > 0) {
481     data->hello_interval = lnk->itime_value;
482   }
483   else {
484     data->hello_interval = lnk->vtime_value;
485   }
486
487   _reset_missed_hello_timer(data);
488 }
489
490 /**
491  * Callback triggered when a nhdp link is removed from the database
492  * @param ptr nhdp link
493  */
494 static void
495 _cb_link_removed(void *ptr) {
496   struct link_datff_data *data;
497
498   data = oonf_class_get_extension(&_link_extenstion, ptr);
499
500   oonf_timer_stop(&data->hello_lost_timer);
501 }
502
503 static void
504 _cb_nhdpif_added(void *ptr) {
505   struct ff_dat_if_config *ifconfig;
506
507   ifconfig = oonf_class_get_extension(&_nhdpif_extenstion, ptr);
508
509   ifconfig->_sampling_timer.class = &_sampling_timer_info;
510 }
511
512 static void
513 _cb_nhdpif_removed(void *ptr) {
514   struct ff_dat_if_config *ifconfig;
515
516   ifconfig = oonf_class_get_extension(&_nhdpif_extenstion, ptr);
517
518   if (ifconfig->_sampling_timer.class) {
519     oonf_timer_stop(&ifconfig->_sampling_timer);
520     ifconfig->_sampling_timer.class = NULL;
521   }
522 }
523
524 /**
525  * Helper for sorting datarate array
526  * @param p1 pointer to integer 1
527  * @param p2 pointer to integer 2
528  * @return <0, 0 >0 (standard comparator output)
529  */
530 static int
531 _int_comparator(const void *p1, const void *p2) {
532   const int *i1 = (int *)p1;
533   const int *i2 = (int *)p2;
534
535   if (*i1 > *i2) {
536     return 1;
537   }
538   else if (*i1 < *i2) {
539     return -1;
540   }
541   return 0;
542 }
543
544 /**
545  * Get the median of all recorded link speeds by sorting
546  * @param ldata linkdata
547  * @return median linkspeed
548  */
549 static int
550 _get_median_rx_linkspeed(struct link_datff_data *ldata) {
551   int zero_count;
552   size_t window;
553   size_t i;
554
555   zero_count = 0;
556   for (i=0; i<ARRAYSIZE(ldata->buckets); i++) {
557     _rx_sort_array[i] = ldata->buckets[i].scaled_speed;
558     if (_rx_sort_array[i] == 0) {
559       zero_count++;
560     }
561   }
562
563   window = ARRAYSIZE(ldata->buckets) - zero_count;
564   if (window == 0) {
565     return 1;
566   }
567
568   qsort(_rx_sort_array, ARRAYSIZE(ldata->buckets), sizeof(int), _int_comparator);
569
570   return _rx_sort_array[zero_count + window/2];
571 }
572
573 /**
574  * Retrieves the speed of a nhdp link, scaled to the minimum link speed
575  * of this metric.
576  * @param lnk nhdp link
577  * @return scaled link speed, 1 if could not be retrieved.
578  */
579 static int
580 _get_scaled_rx_linkspeed(struct ff_dat_if_config *ifconfig, struct nhdp_link *lnk) {
581   struct os_interface *os_if;
582   const struct oonf_layer2_data *l2data;
583   int64_t rate;
584 #ifdef OONF_LOG_INFO
585   struct netaddr_str nbuf;
586 #endif
587
588   if (!ifconfig->ett) {
589     /* ETT feature is switched off */
590     return 1;
591   }
592
593   /* get local interface data  */
594   os_if = nhdp_interface_get_if_listener(lnk->local_if)->data;
595
596   l2data = oonf_layer2_neigh_query(
597       os_if->name, &lnk->remote_mac, OONF_LAYER2_NEIGH_RX_BITRATE);
598   if (!l2data) {
599     OONF_INFO(LOG_FF_DAT, "Datarate for link %s (%s) not available",
600         netaddr_to_string(&nbuf, &lnk->if_addr),
601         nhdp_interface_get_name(lnk->local_if));
602     return 1;
603   }
604
605   /* round up */
606   rate = (oonf_layer2_get_value(l2data) + DATFF_LINKSPEED_MINIMUM - 1) / DATFF_LINKSPEED_MINIMUM;
607   if (rate < 1) {
608     OONF_DEBUG(LOG_FF_DAT, "Datarate for link %s (%s) too small: %"PRId64" / %"PRId64,
609         netaddr_to_string(&nbuf, &lnk->if_addr),
610         nhdp_interface_get_name(lnk->local_if), rate,
611         oonf_layer2_get_value(l2data));
612     return 1;
613   }
614   if (rate > DATFF_LINKSPEED_RANGE) {
615     OONF_DEBUG(LOG_FF_DAT, "Datarate for link %s (%s) too large: %"PRId64" / %"PRId64,
616         netaddr_to_string(&nbuf, &lnk->if_addr),
617         nhdp_interface_get_name(lnk->local_if), rate,
618         oonf_layer2_get_value(l2data));
619
620     return DATFF_LINKSPEED_RANGE;
621   }
622   return rate;
623 }
624
625 /**
626  * Timer callback to sample new metric values into bucket
627  * @param ptr nhdp link
628  */
629 static void
630 _cb_dat_sampling(struct oonf_timer_instance *ptr) {
631   struct rfc7181_metric_field encoded_metric;
632   struct ff_dat_if_config *ifconfig;
633   struct link_datff_data *ldata;
634   struct nhdp_link *lnk;
635   uint32_t total, received;
636   uint64_t metric;
637   uint32_t metric_value;
638   uint32_t missing_intervals;
639   size_t i;
640   int rx_bitrate;
641   struct netaddr_str nbuf;
642
643   ifconfig = container_of(ptr, struct ff_dat_if_config, _sampling_timer);
644
645   OONF_DEBUG(LOG_FF_DAT, "Calculate Metric from sampled data");
646
647   list_for_each_element(nhdp_db_get_link_list(), lnk, _global_node) {
648     if (oonf_class_get_extension(&_nhdpif_extenstion, lnk->local_if) != ifconfig) {
649       continue;
650     }
651
652     ldata = oonf_class_get_extension(&_link_extenstion, lnk);
653     if (!ldata->contains_data) {
654       /* still no data for this link */
655       continue;
656     }
657
658     /* initialize counter */
659     total = 0;
660     received = 0;
661
662     /* calculate metric */
663     for (i=0; i<ARRAYSIZE(ldata->buckets); i++) {
664       received += ldata->buckets[i].received;
665       total += ldata->buckets[i].total;
666     }
667
668     if (ldata->missed_hellos > 0) {
669       missing_intervals = (ldata->missed_hellos * ldata->hello_interval)
670           / ifconfig->interval;
671       if (missing_intervals > ARRAYSIZE(ldata->buckets)) {
672         received = 0;
673       }
674       else {
675         received = (received * (ARRAYSIZE(ldata->buckets) - missing_intervals))
676             / ARRAYSIZE(ldata->buckets);
677       }
678     }
679
680     /* update link speed */
681     ldata->buckets[ldata->activePtr].scaled_speed = _get_scaled_rx_linkspeed(ifconfig, lnk);
682
683     OONF_DEBUG(LOG_FF_DAT, "Query incoming linkspeed for link %s: %"PRIu64,
684         netaddr_to_string(&nbuf, &lnk->if_addr),
685         (uint64_t)(ldata->buckets[ldata->activePtr].scaled_speed) * DATFF_LINKSPEED_MINIMUM);
686
687     /* get median scaled link speed and apply it to metric */
688     rx_bitrate = _get_median_rx_linkspeed(ldata);
689     if (rx_bitrate > DATFF_LINKSPEED_RANGE) {
690       OONF_WARN(LOG_FF_DAT, "Metric overflow %s (%s): %d",
691           netaddr_to_string(&nbuf, &lnk->if_addr),
692           nhdp_interface_get_name(lnk->local_if), rx_bitrate);
693       metric = 1;
694     }
695     else {
696       metric = DATFF_LINKSPEED_RANGE / rx_bitrate;
697     }
698
699     /* calculate frame loss, use discrete values */
700     if (total == 0 || received == 0
701         || received * DATFF_FRAME_SUCCESS_RANGE <= total) {
702       metric *= DATFF_FRAME_SUCCESS_RANGE;
703     }
704     else {
705       metric = _apply_packet_loss(ifconfig, lnk, ldata, metric, received, total);
706     }
707
708     /* convert into something that can be transmitted over the network */
709     if (metric > RFC7181_METRIC_MAX) {
710       /* give the metric an upper bound */
711       OONF_INFO(LOG_FF_DAT, "Metric overflow %s (%s): %"PRIu64,
712           netaddr_to_string(&nbuf, &lnk->if_addr),
713           nhdp_interface_get_name(lnk->local_if), metric);
714       metric_value = RFC7181_METRIC_MAX;
715     }
716     else if (metric < RFC7181_METRIC_MIN) {
717       OONF_WARN(LOG_FF_DAT, "Metric underflow %s (%s): %"PRIu64,
718           netaddr_to_string(&nbuf, &lnk->if_addr),
719           nhdp_interface_get_name(lnk->local_if), metric);
720       metric_value = RFC7181_METRIC_MIN;
721     }
722     else if(!rfc7181_metric_encode(&encoded_metric, metric)) {
723       metric_value = rfc7181_metric_decode(&encoded_metric);
724     }
725     else {
726       /* metric encoding failed */
727       OONF_WARN(LOG_FF_DAT, "Metric encoding failed for link %s (%s): %"PRIu64,
728           netaddr_to_string(&nbuf, &lnk->if_addr),
729           nhdp_interface_get_name(lnk->local_if), metric);
730       metric_value = RFC7181_METRIC_MAX;
731     }
732
733     /* set metric for incoming link */
734     nhdp_domain_set_incoming_metric(
735         &_datff_handler, lnk, metric_value);
736
737     OONF_DEBUG(LOG_FF_DAT, "New sampling rate for link %s (%s):"
738         " %d/%d = %u (speed=%"PRIu64 ")\n",
739         netaddr_to_string(&nbuf, &lnk->if_addr),
740         nhdp_interface_get_name(lnk->local_if),
741         received, total, metric_value, (uint64_t)(rx_bitrate) * DATFF_LINKSPEED_MINIMUM);
742
743     /* update rolling buffer */
744     ldata->activePtr++;
745     if (ldata->activePtr >= ARRAYSIZE(ldata->buckets)) {
746       ldata->activePtr = 0;
747     }
748     ldata->buckets[ldata->activePtr].received = 0;
749     ldata->buckets[ldata->activePtr].total = 0;
750   }
751 }
752
753 /**
754  * Calculate how many neighbors a link has
755  * @param lnk nhdp link
756  * @param data ff data link data
757  */
758 static void
759 _calculate_link_neighborhood(struct nhdp_link *lnk, struct link_datff_data *data) {
760   struct nhdp_l2hop *l2hop;
761   struct nhdp_laddr *laddr;
762   int count;
763
764   /* local link neighbors */
765   count = lnk->local_if->_link_originators.count;
766
767   /* links twohop neighbors */
768   avl_for_each_element(&lnk->_2hop, l2hop, _link_node) {
769     if (l2hop->same_interface
770         && !avl_find_element(&lnk->local_if->_link_addresses, &l2hop->twohop_addr, laddr, _if_node)) {
771       count ++;
772     }
773   }
774
775   data->link_neigborhood = count;
776 }
777
778 /**
779  * Calculate the loss exponentiation based on the link neigborhood size
780  * @param link_neigborhood link neighborhood count
781  * @return loss exponent
782  */
783 static int
784 _calculate_dynamic_loss_exponent(int link_neigborhood) {
785   if (link_neigborhood < 4) {
786     return 1;
787   }
788   if (link_neigborhood < 9) {
789     return 2;
790   }
791   if (link_neigborhood < 15) {
792     return 3;
793   }
794   return 4;
795 }
796
797 /**
798  * Select discrete packet loss values and apply a hysteresis
799  * @param lnk nhdp link
800  * @param ldata link data object
801  * @param metric metric based on linkspeed
802  * @param received received packets
803  * @param total total packets
804  * @return metric including linkspeed and packet loss
805  */
806 static uint32_t
807 _apply_packet_loss(struct ff_dat_if_config *ifconfig, struct nhdp_link *lnk,
808     struct link_datff_data *ldata, uint32_t metric,
809     uint32_t received, uint32_t total) {
810   int64_t success_scaled_by_1000;
811   int loss_exponent;
812   int64_t tmp_metric;
813
814   if (received * DATFF_FRAME_SUCCESS_RANGE < total) {
815     success_scaled_by_1000 = 1000ll;
816   }
817   else {
818     success_scaled_by_1000 = (((int64_t)DATFF_FRAME_SUCCESS_RANGE * 1000ll) * received) / total;
819   }
820
821   if (success_scaled_by_1000 >= ldata->last_packet_success_rate - 750
822       && success_scaled_by_1000 <= ldata->last_packet_success_rate + 750
823       ) {
824     /* keep old loss rate */
825     success_scaled_by_1000 = ldata->last_packet_success_rate;
826   }
827   else {
828     /* remember new loss rate */
829     ldata->last_packet_success_rate = success_scaled_by_1000;
830   }
831
832   _calculate_link_neighborhood(lnk, ldata);
833
834   switch (ifconfig->loss_exponent) {
835     case IDX_LOSS_LINEAR:
836       loss_exponent = 1;
837       break;
838     case IDX_LOSS_QUADRATIC:
839       loss_exponent = 2;
840       break;
841     case IDX_LOSS_CUBIC:
842       loss_exponent = 3;
843       break;
844     case IDX_LOSS_DYNAMIC:
845       loss_exponent = _calculate_dynamic_loss_exponent(ldata->link_neigborhood);
846       break;
847     default:
848       loss_exponent = 1;
849       break;
850   }
851
852   tmp_metric = metric;
853   while (loss_exponent) {
854     tmp_metric = (tmp_metric * (int64_t)DATFF_FRAME_SUCCESS_RANGE * 1000ll + 500ll) / success_scaled_by_1000;
855     loss_exponent--;
856   }
857
858   if (ifconfig->mic && ldata->link_neigborhood > 1) {
859     tmp_metric = tmp_metric * (int64_t)ldata->link_neigborhood;
860   }
861
862   if (tmp_metric > RFC7181_METRIC_MAX) {
863     return RFC7181_METRIC_MAX;
864   }
865   if (tmp_metric < RFC7181_METRIC_MIN) {
866     return RFC7181_METRIC_MIN;
867   }
868   return tmp_metric;
869 }
870
871 /**
872  * Callback triggered when the next hellos should have been received
873  * @param ptr timer instance that fired
874  */
875 static void
876 _cb_hello_lost(struct oonf_timer_instance *ptr) {
877   struct link_datff_data *ldata;
878
879   ldata = container_of(ptr, struct link_datff_data, hello_lost_timer);
880
881   if (ldata->contains_data) {
882     ldata->missed_hellos++;
883
884     oonf_timer_set(&ldata->hello_lost_timer, ldata->hello_interval);
885
886     OONF_DEBUG(LOG_FF_DAT, "Missed Hello: %d", ldata->missed_hellos);
887   }
888 }
889
890 /**
891  * Check if an incoming packet should be used for metric calculation
892  * @return true to process packet, false otherwise
893  */
894 static bool
895 _shall_process_packet(struct nhdp_interface *nhdpif, struct ff_dat_if_config *ifconfig) {
896   struct os_interface_listener *if_listener;
897   if (_protocol->input.is_multicast) {
898     /* accept multicast */
899     return true;
900   }
901
902   if_listener = nhdp_interface_get_if_listener(nhdpif);
903   if (if_listener && if_listener->data && if_listener->data->flags.unicast_only) {
904     /* accept unicast for unicast-only interfaces */
905     return true;
906   }
907
908   return ifconfig->accept_unicast;
909 }
910
911 /**
912  * Callback to process all in RFC5444 packets for metric calculation. The
913  * Callback ignores all unicast packets.
914  * @param consumer
915  * @param context
916  * @return
917  */
918 static enum rfc5444_result
919 _cb_process_packet(struct rfc5444_reader_tlvblock_context *context) {
920   struct ff_dat_if_config *ifconfig;
921   struct link_datff_data *ldata;
922   struct nhdp_interface *interf;
923   struct nhdp_laddr *laddr;
924   struct nhdp_link *lnk;
925   int total;
926
927   struct netaddr_str nbuf;
928 #ifdef OONF_LOG_DEBUG_INFO
929   struct isonumber_str timebuf;
930 #endif
931
932   if (!context->has_pktseqno) {
933     struct netaddr_str buf;
934
935     OONF_WARN(LOG_FF_DAT, "Neighbor %s does not send packet sequence numbers, cannot collect datff data!",
936         netaddr_socket_to_string(&buf, _protocol->input.src_socket));
937     return RFC5444_OKAY;
938   }
939
940   /* get interface and link */
941   interf = nhdp_interface_get(_protocol->input.interface->name);
942   if (interf == NULL) {
943     /* silently ignore unknown interface */
944     return RFC5444_OKAY;
945   }
946
947   ifconfig = oonf_class_get_extension(&_nhdpif_extenstion, interf);
948   if (!_shall_process_packet(interf, ifconfig)) {
949     /* silently ignore unicasts */
950     return RFC5444_OKAY;
951   }
952
953   laddr = nhdp_interface_get_link_addr(interf, _protocol->input.src_address);
954   if (laddr == NULL) {
955     /* silently ignore unknown link*/
956     return RFC5444_OKAY;
957   }
958
959   /* log raw metric data */
960   OONF_DEBUG(LOG_FF_DAT_RAW, "%s %s %u %d\n",
961           oonf_clock_toIntervalString(&timebuf, oonf_clock_getNow()),
962           netaddr_to_string(&nbuf, &laddr->link_addr),
963           context->pkt_seqno,
964           _get_scaled_rx_linkspeed(ifconfig, laddr->link));
965
966   /* get link and its dat data */
967   lnk = laddr->link;
968   ldata = oonf_class_get_extension(&_link_extenstion, lnk);
969
970   if (!ldata->buckets) {
971     OONF_WARN(LOG_FF_DAT, "No buckets for link to %s (%s)",
972         netaddr_to_string(&nbuf, &lnk->if_addr),
973         nhdp_interface_get_name(lnk->local_if));
974     return RFC5444_OKAY;
975   }
976
977   if (!ldata->contains_data) {
978     ldata->contains_data = true;
979     ldata->activePtr = 0;
980     ldata->buckets[0].received = 1;
981     ldata->buckets[0].total = 1;
982     ldata->last_seq_nr = context->pkt_seqno;
983
984     return RFC5444_OKAY;
985   }
986
987   if (context->pkt_seqno >= ldata->last_seq_nr) {
988     total = context->pkt_seqno - ldata->last_seq_nr;
989   }
990   else {
991     total = ((uint32_t)(context->pkt_seqno) + 65536) - (uint32_t)(ldata->last_seq_nr);
992   }
993
994   ldata->buckets[ldata->activePtr].received++;
995   ldata->buckets[ldata->activePtr].total += total;
996   ldata->last_seq_nr = context->pkt_seqno;
997
998   _reset_missed_hello_timer(ldata);
999
1000   return RFC5444_OKAY;
1001 }
1002
1003 /**
1004  * A Hello was received, handle data and timer changes
1005  * @param data link metric data
1006  */
1007 static void
1008 _reset_missed_hello_timer(struct link_datff_data *data) {
1009   oonf_timer_set(&data->hello_lost_timer, (data->hello_interval * 3) / 2);
1010
1011   data->missed_hellos = 0;
1012 }
1013
1014 /**
1015  * Convert DATFF metric into string representation
1016  * @param buf pointer to output buffer
1017  * @param metric metric value
1018  * @return pointer to output string
1019  */
1020 static const char *
1021 _link_to_string(struct nhdp_metric_str *buf, uint32_t metric) {
1022   uint64_t value;
1023
1024   if (metric < DATFF_LINKCOST_MINIMUM) {
1025     value = (uint32_t)DATFF_LINKSPEED_MINIMUM
1026         * (uint32_t)DATFF_LINKSPEED_RANGE;
1027   }
1028   else if (metric > DATFF_LINKCOST_MAXIMUM) {
1029     strscpy(buf->buf, "infinite", sizeof(*buf));
1030     return buf->buf;
1031   }
1032   else {
1033     value = (uint32_t)(DATFF_LINKSPEED_MINIMUM) * (uint32_t)(DATFF_LINKSPEED_RANGE) / metric;
1034   }
1035   isonumber_from_u64((struct isonumber_str *)buf,
1036       value, "bit/s", 0, true, false);
1037   return buf->buf;
1038 }
1039
1040 /**
1041  * Convert DATFF path metric into string representation
1042  * @param buf pointer to output buffer
1043  * @param metric path metric value
1044  * @return pointer to output string
1045  */
1046 static const char *
1047 _path_to_string(struct nhdp_metric_str *buf, uint32_t metric, uint8_t hopcount) {
1048   struct nhdp_metric_str mbuf;
1049
1050   if (hopcount == 0) {
1051     /* prevent division by zero */
1052     hopcount = 1;
1053   }
1054   snprintf(buf->buf, sizeof(*buf), "%s (%u hops)",
1055       _link_to_string(&mbuf, metric / hopcount), hopcount);
1056   return buf->buf;
1057 }
1058
1059 /**
1060  * Internal link metric to string processing
1061  * @param buf output buffer
1062  * @param lnk nhdp link
1063  * @return pointer to output buffer
1064  */
1065 static const char *
1066 _int_link_to_string(struct nhdp_metric_str *buf, struct nhdp_link *lnk) {
1067   struct link_datff_data *ldata;
1068   int64_t received = 0, total = 0;
1069   size_t i;
1070
1071   struct netaddr_str nbuf;
1072
1073   ldata = oonf_class_get_extension(&_link_extenstion, lnk);
1074
1075   if (!ldata->buckets) {
1076     OONF_WARN(LOG_FF_DAT, "No buckets for link to %s (%s)",
1077         netaddr_to_string(&nbuf, &lnk->if_addr),
1078         nhdp_interface_get_name(lnk->local_if));
1079     return RFC5444_OKAY;
1080   }
1081
1082   for (i=0; i<ARRAYSIZE(ldata->buckets); i++) {
1083     received += ldata->buckets[i].received;
1084     total += ldata->buckets[i].total;
1085   }
1086
1087   snprintf(buf->buf, sizeof(*buf), "p_recv=%"PRId64",p_total=%"PRId64","
1088       "speed=%"PRId64",success=%"PRId64",missed_hello=%d,lastseq=%u,lneigh=%d",
1089       received, total, (int64_t)_get_median_rx_linkspeed(ldata) * (int64_t)1024,
1090       ldata->last_packet_success_rate, ldata->missed_hellos,
1091       ldata->last_seq_nr, ldata->link_neigborhood);
1092   return buf->buf;
1093 }
1094
1095 /**
1096  * Callback triggered when configuration changes
1097  */
1098 static void
1099 _cb_cfg_changed(void) {
1100   struct ff_dat_if_config *ifconfig = NULL;
1101   struct nhdp_interface *nhdp_if;
1102   const char *ifname;
1103   char ifbuf[IF_NAMESIZE];
1104
1105   ifname = cfg_get_phy_if(ifbuf, _datff_section.section_name);
1106
1107   if (_datff_section.pre == NULL) {
1108     /* increase nhdp_interface refcount */
1109     nhdp_if = nhdp_interface_add(ifname);
1110   }
1111   else {
1112     /* get interface */
1113     nhdp_if = nhdp_interface_get(ifname);
1114   }
1115
1116   if (nhdp_if) {
1117     /* get block domain extension */
1118     ifconfig = oonf_class_get_extension(&_nhdpif_extenstion, nhdp_if);
1119     ifconfig->registered = true;
1120   }
1121
1122   if (_datff_section.post == NULL) {
1123     /* section was removed */
1124     if (nhdp_if != NULL) {
1125       ifconfig->registered = false;
1126
1127       /* decrease nhdp_interface refcount */
1128       nhdp_interface_remove(nhdp_if);
1129     }
1130
1131     nhdp_if = NULL;
1132   }
1133
1134   if (!nhdp_if) {
1135     return;
1136   }
1137
1138   if (cfg_schema_tobin(ifconfig, _datff_section.post,
1139       _datff_entries, ARRAYSIZE(_datff_entries))) {
1140     OONF_WARN(LOG_FF_DAT, "Cannot convert configuration for "
1141         OONF_FF_DAT_METRIC_SUBSYSTEM);
1142     return;
1143   }
1144
1145   /* start/change sampling timer */
1146   oonf_timer_set(&ifconfig->_sampling_timer, ifconfig->interval);
1147
1148 #ifdef COLLECT_RAW_DATA
1149   if (_rawdata_fd != -1) {
1150     fsync(_rawdata_fd);
1151     close(_rawdata_fd);
1152     _rawdata_end = 0;
1153     _rawdata_count = 0;
1154   }
1155
1156   if (_datff_config.rawdata_start) {
1157     _rawdata_fd = open(_datff_config.rawdata_file, O_CREAT | O_TRUNC | O_WRONLY,
1158                 S_IRUSR|S_IWUSR);
1159     if (_rawdata_fd != -1) {
1160       abuf_clear(&_rawdata_buf);
1161       abuf_appendf(&_rawdata_buf, "Time: %s\n", oonf_log_get_walltime());
1162       _rawdata_end = oonf_clock_get_absolute(_datff_config.rawdata_maxtime);
1163     }
1164   }
1165 #endif
1166 }