Keep statistics of logged warnings
[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   bool change_happened;
642
643   struct netaddr_str nbuf;
644
645   ifconfig = container_of(ptr, struct ff_dat_if_config, _sampling_timer);
646
647   OONF_DEBUG(LOG_FF_DAT, "Calculate Metric from sampled data");
648
649   change_happened = false;
650
651   list_for_each_element(nhdp_db_get_link_list(), lnk, _global_node) {
652     if (oonf_class_get_extension(&_nhdpif_extenstion, lnk->local_if) != ifconfig) {
653       continue;
654     }
655
656     ldata = oonf_class_get_extension(&_link_extenstion, lnk);
657     if (!ldata->contains_data) {
658       /* still no data for this link */
659       continue;
660     }
661
662     /* initialize counter */
663     total = 0;
664     received = 0;
665
666     /* calculate metric */
667     for (i=0; i<ARRAYSIZE(ldata->buckets); i++) {
668       received += ldata->buckets[i].received;
669       total += ldata->buckets[i].total;
670     }
671
672     if (ldata->missed_hellos > 0) {
673       missing_intervals = (ldata->missed_hellos * ldata->hello_interval)
674           / ifconfig->interval;
675       if (missing_intervals > ARRAYSIZE(ldata->buckets)) {
676         received = 0;
677       }
678       else {
679         received = (received * (ARRAYSIZE(ldata->buckets) - missing_intervals))
680             / ARRAYSIZE(ldata->buckets);
681       }
682     }
683
684     /* update link speed */
685     ldata->buckets[ldata->activePtr].scaled_speed = _get_scaled_rx_linkspeed(ifconfig, lnk);
686
687     OONF_DEBUG(LOG_FF_DAT, "Query incoming linkspeed for link %s: %"PRIu64,
688         netaddr_to_string(&nbuf, &lnk->if_addr),
689         (uint64_t)(ldata->buckets[ldata->activePtr].scaled_speed) * DATFF_LINKSPEED_MINIMUM);
690
691     /* get median scaled link speed and apply it to metric */
692     rx_bitrate = _get_median_rx_linkspeed(ldata);
693     if (rx_bitrate > DATFF_LINKSPEED_RANGE) {
694       OONF_WARN(LOG_FF_DAT, "Metric overflow %s (%s): %d",
695           netaddr_to_string(&nbuf, &lnk->if_addr),
696           nhdp_interface_get_name(lnk->local_if), rx_bitrate);
697       metric = 1;
698     }
699     else {
700       metric = DATFF_LINKSPEED_RANGE / rx_bitrate;
701     }
702
703     /* calculate frame loss, use discrete values */
704     if (total == 0 || received == 0
705         || received * DATFF_FRAME_SUCCESS_RANGE <= total) {
706       metric *= DATFF_FRAME_SUCCESS_RANGE;
707     }
708     else {
709       metric = _apply_packet_loss(ifconfig, lnk, ldata, metric, received, total);
710     }
711
712     /* convert into something that can be transmitted over the network */
713     if (metric > RFC7181_METRIC_MAX) {
714       /* give the metric an upper bound */
715       OONF_INFO(LOG_FF_DAT, "Metric overflow %s (%s): %"PRIu64,
716           netaddr_to_string(&nbuf, &lnk->if_addr),
717           nhdp_interface_get_name(lnk->local_if), metric);
718       metric_value = RFC7181_METRIC_MAX;
719     }
720     else if (metric < RFC7181_METRIC_MIN) {
721       OONF_WARN(LOG_FF_DAT, "Metric underflow %s (%s): %"PRIu64,
722           netaddr_to_string(&nbuf, &lnk->if_addr),
723           nhdp_interface_get_name(lnk->local_if), metric);
724       metric_value = RFC7181_METRIC_MIN;
725     }
726     else if(!rfc7181_metric_encode(&encoded_metric, metric)) {
727       metric_value = rfc7181_metric_decode(&encoded_metric);
728     }
729     else {
730       /* metric encoding failed */
731       OONF_WARN(LOG_FF_DAT, "Metric encoding failed for link %s (%s): %"PRIu64,
732           netaddr_to_string(&nbuf, &lnk->if_addr),
733           nhdp_interface_get_name(lnk->local_if), metric);
734       metric_value = RFC7181_METRIC_MAX;
735     }
736
737     /* set metric for incoming link */
738     change_happened |= nhdp_domain_set_incoming_metric(
739         &_datff_handler, lnk, metric_value);
740
741     OONF_DEBUG(LOG_FF_DAT, "New sampling rate for link %s (%s):"
742         " %d/%d = %u (speed=%"PRIu64 ")\n",
743         netaddr_to_string(&nbuf, &lnk->if_addr),
744         nhdp_interface_get_name(lnk->local_if),
745         received, total, metric_value, (uint64_t)(rx_bitrate) * DATFF_LINKSPEED_MINIMUM);
746
747     /* update rolling buffer */
748     ldata->activePtr++;
749     if (ldata->activePtr >= ARRAYSIZE(ldata->buckets)) {
750       ldata->activePtr = 0;
751     }
752     ldata->buckets[ldata->activePtr].received = 0;
753     ldata->buckets[ldata->activePtr].total = 0;
754   }
755
756   /* update neighbor metrics */
757   if (change_happened) {
758     nhdp_domain_neighborhood_changed();
759   }
760 }
761
762 /**
763  * Calculate how many neighbors a link has
764  * @param lnk nhdp link
765  * @param data ff data link data
766  */
767 static void
768 _calculate_link_neighborhood(struct nhdp_link *lnk, struct link_datff_data *data) {
769   struct nhdp_l2hop *l2hop;
770   struct nhdp_laddr *laddr;
771   int count;
772
773   /* local link neighbors */
774   count = lnk->local_if->_link_originators.count;
775
776   /* links twohop neighbors */
777   avl_for_each_element(&lnk->_2hop, l2hop, _link_node) {
778     if (l2hop->same_interface
779         && !avl_find_element(&lnk->local_if->_link_addresses, &l2hop->twohop_addr, laddr, _if_node)) {
780       count ++;
781     }
782   }
783
784   data->link_neigborhood = count;
785 }
786
787 /**
788  * Calculate the loss exponentiation based on the link neigborhood size
789  * @param link_neigborhood link neighborhood count
790  * @return loss exponent
791  */
792 static int
793 _calculate_dynamic_loss_exponent(int link_neigborhood) {
794   if (link_neigborhood < 4) {
795     return 1;
796   }
797   if (link_neigborhood < 9) {
798     return 2;
799   }
800   if (link_neigborhood < 15) {
801     return 3;
802   }
803   return 4;
804 }
805
806 /**
807  * Select discrete packet loss values and apply a hysteresis
808  * @param lnk nhdp link
809  * @param ldata link data object
810  * @param metric metric based on linkspeed
811  * @param received received packets
812  * @param total total packets
813  * @return metric including linkspeed and packet loss
814  */
815 static uint32_t
816 _apply_packet_loss(struct ff_dat_if_config *ifconfig, struct nhdp_link *lnk,
817     struct link_datff_data *ldata, uint32_t metric,
818     uint32_t received, uint32_t total) {
819   int64_t success_scaled_by_1000;
820   int loss_exponent;
821   int64_t tmp_metric;
822
823   if (received * DATFF_FRAME_SUCCESS_RANGE < total) {
824     success_scaled_by_1000 = 1000ll;
825   }
826   else {
827     success_scaled_by_1000 = (((int64_t)DATFF_FRAME_SUCCESS_RANGE * 1000ll) * received) / total;
828   }
829
830   if (success_scaled_by_1000 >= ldata->last_packet_success_rate - 750
831       && success_scaled_by_1000 <= ldata->last_packet_success_rate + 750
832       ) {
833     /* keep old loss rate */
834     success_scaled_by_1000 = ldata->last_packet_success_rate;
835   }
836   else {
837     /* remember new loss rate */
838     ldata->last_packet_success_rate = success_scaled_by_1000;
839   }
840
841   _calculate_link_neighborhood(lnk, ldata);
842
843   switch (ifconfig->loss_exponent) {
844     case IDX_LOSS_LINEAR:
845       loss_exponent = 1;
846       break;
847     case IDX_LOSS_QUADRATIC:
848       loss_exponent = 2;
849       break;
850     case IDX_LOSS_CUBIC:
851       loss_exponent = 3;
852       break;
853     case IDX_LOSS_DYNAMIC:
854       loss_exponent = _calculate_dynamic_loss_exponent(ldata->link_neigborhood);
855       break;
856     default:
857       loss_exponent = 1;
858       break;
859   }
860
861   tmp_metric = metric;
862   while (loss_exponent) {
863     tmp_metric = (tmp_metric * (int64_t)DATFF_FRAME_SUCCESS_RANGE * 1000ll + 500ll) / success_scaled_by_1000;
864     loss_exponent--;
865   }
866
867   if (ifconfig->mic && ldata->link_neigborhood > 1) {
868     tmp_metric = tmp_metric * (int64_t)ldata->link_neigborhood;
869   }
870
871   if (tmp_metric > RFC7181_METRIC_MAX) {
872     return RFC7181_METRIC_MAX;
873   }
874   if (tmp_metric < RFC7181_METRIC_MIN) {
875     return RFC7181_METRIC_MIN;
876   }
877   return tmp_metric;
878 }
879
880 /**
881  * Callback triggered when the next hellos should have been received
882  * @param ptr timer instance that fired
883  */
884 static void
885 _cb_hello_lost(struct oonf_timer_instance *ptr) {
886   struct link_datff_data *ldata;
887
888   ldata = container_of(ptr, struct link_datff_data, hello_lost_timer);
889
890   if (ldata->contains_data) {
891     ldata->missed_hellos++;
892
893     oonf_timer_set(&ldata->hello_lost_timer, ldata->hello_interval);
894
895     OONF_DEBUG(LOG_FF_DAT, "Missed Hello: %d", ldata->missed_hellos);
896   }
897 }
898
899 /**
900  * Check if an incoming packet should be used for metric calculation
901  * @return true to process packet, false otherwise
902  */
903 static bool
904 _shall_process_packet(struct nhdp_interface *nhdpif, struct ff_dat_if_config *ifconfig) {
905   struct os_interface_listener *if_listener;
906   if (_protocol->input.is_multicast) {
907     /* accept multicast */
908     return true;
909   }
910
911   if_listener = nhdp_interface_get_if_listener(nhdpif);
912   if (if_listener && if_listener->data && if_listener->data->flags.unicast_only) {
913     /* accept unicast for unicast-only interfaces */
914     return true;
915   }
916
917   return ifconfig->accept_unicast;
918 }
919
920 /**
921  * Callback to process all in RFC5444 packets for metric calculation. The
922  * Callback ignores all unicast packets.
923  * @param consumer
924  * @param context
925  * @return
926  */
927 static enum rfc5444_result
928 _cb_process_packet(struct rfc5444_reader_tlvblock_context *context) {
929   struct ff_dat_if_config *ifconfig;
930   struct link_datff_data *ldata;
931   struct nhdp_interface *interf;
932   struct nhdp_laddr *laddr;
933   struct nhdp_link *lnk;
934   int total;
935
936   struct netaddr_str nbuf;
937 #ifdef OONF_LOG_DEBUG_INFO
938   struct isonumber_str timebuf;
939 #endif
940
941   if (!context->has_pktseqno) {
942     struct netaddr_str buf;
943
944     OONF_WARN(LOG_FF_DAT, "Neighbor %s does not send packet sequence numbers, cannot collect datff data!",
945         netaddr_socket_to_string(&buf, _protocol->input.src_socket));
946     return RFC5444_OKAY;
947   }
948
949   /* get interface and link */
950   interf = nhdp_interface_get(_protocol->input.interface->name);
951   if (interf == NULL) {
952     /* silently ignore unknown interface */
953     return RFC5444_OKAY;
954   }
955
956   ifconfig = oonf_class_get_extension(&_nhdpif_extenstion, interf);
957   if (!_shall_process_packet(interf, ifconfig)) {
958     /* silently ignore unicasts */
959     return RFC5444_OKAY;
960   }
961
962   laddr = nhdp_interface_get_link_addr(interf, _protocol->input.src_address);
963   if (laddr == NULL) {
964     /* silently ignore unknown link*/
965     return RFC5444_OKAY;
966   }
967
968   /* log raw metric data */
969   OONF_DEBUG(LOG_FF_DAT_RAW, "%s %s %u %d\n",
970           oonf_clock_toIntervalString(&timebuf, oonf_clock_getNow()),
971           netaddr_to_string(&nbuf, &laddr->link_addr),
972           context->pkt_seqno,
973           _get_scaled_rx_linkspeed(ifconfig, laddr->link));
974
975   /* get link and its dat data */
976   lnk = laddr->link;
977   ldata = oonf_class_get_extension(&_link_extenstion, lnk);
978
979   if (!ldata->buckets) {
980     OONF_WARN(LOG_FF_DAT, "No buckets for link to %s (%s)",
981         netaddr_to_string(&nbuf, &lnk->if_addr),
982         nhdp_interface_get_name(lnk->local_if));
983     return RFC5444_OKAY;
984   }
985
986   if (!ldata->contains_data) {
987     ldata->contains_data = true;
988     ldata->activePtr = 0;
989     ldata->buckets[0].received = 1;
990     ldata->buckets[0].total = 1;
991     ldata->last_seq_nr = context->pkt_seqno;
992
993     return RFC5444_OKAY;
994   }
995
996   if (context->pkt_seqno >= ldata->last_seq_nr) {
997     total = context->pkt_seqno - ldata->last_seq_nr;
998   }
999   else {
1000     total = ((uint32_t)(context->pkt_seqno) + 65536) - (uint32_t)(ldata->last_seq_nr);
1001   }
1002
1003   ldata->buckets[ldata->activePtr].received++;
1004   ldata->buckets[ldata->activePtr].total += total;
1005   ldata->last_seq_nr = context->pkt_seqno;
1006
1007   _reset_missed_hello_timer(ldata);
1008
1009   return RFC5444_OKAY;
1010 }
1011
1012 /**
1013  * A Hello was received, handle data and timer changes
1014  * @param data link metric data
1015  */
1016 static void
1017 _reset_missed_hello_timer(struct link_datff_data *data) {
1018   oonf_timer_set(&data->hello_lost_timer, (data->hello_interval * 3) / 2);
1019
1020   data->missed_hellos = 0;
1021 }
1022
1023 /**
1024  * Convert DATFF metric into string representation
1025  * @param buf pointer to output buffer
1026  * @param metric metric value
1027  * @return pointer to output string
1028  */
1029 static const char *
1030 _link_to_string(struct nhdp_metric_str *buf, uint32_t metric) {
1031   uint64_t value;
1032
1033   if (metric < DATFF_LINKCOST_MINIMUM) {
1034     value = (uint32_t)DATFF_LINKSPEED_MINIMUM
1035         * (uint32_t)DATFF_LINKSPEED_RANGE;
1036   }
1037   else if (metric > DATFF_LINKCOST_MAXIMUM) {
1038     strscpy(buf->buf, "infinite", sizeof(*buf));
1039     return buf->buf;
1040   }
1041   else {
1042     value = (uint32_t)(DATFF_LINKSPEED_MINIMUM) * (uint32_t)(DATFF_LINKSPEED_RANGE) / metric;
1043   }
1044   isonumber_from_u64((struct isonumber_str *)buf,
1045       value, "bit/s", 0, true, false);
1046   return buf->buf;
1047 }
1048
1049 /**
1050  * Convert DATFF path metric into string representation
1051  * @param buf pointer to output buffer
1052  * @param metric path metric value
1053  * @return pointer to output string
1054  */
1055 static const char *
1056 _path_to_string(struct nhdp_metric_str *buf, uint32_t metric, uint8_t hopcount) {
1057   struct nhdp_metric_str mbuf;
1058
1059   if (hopcount == 0) {
1060     /* prevent division by zero */
1061     hopcount = 1;
1062   }
1063   snprintf(buf->buf, sizeof(*buf), "%s (%u hops)",
1064       _link_to_string(&mbuf, metric / hopcount), hopcount);
1065   return buf->buf;
1066 }
1067
1068 /**
1069  * Internal link metric to string processing
1070  * @param buf output buffer
1071  * @param lnk nhdp link
1072  * @return pointer to output buffer
1073  */
1074 static const char *
1075 _int_link_to_string(struct nhdp_metric_str *buf, struct nhdp_link *lnk) {
1076   struct link_datff_data *ldata;
1077   int64_t received = 0, total = 0;
1078   size_t i;
1079
1080   struct netaddr_str nbuf;
1081
1082   ldata = oonf_class_get_extension(&_link_extenstion, lnk);
1083
1084   if (!ldata->buckets) {
1085     OONF_WARN(LOG_FF_DAT, "No buckets for link to %s (%s)",
1086         netaddr_to_string(&nbuf, &lnk->if_addr),
1087         nhdp_interface_get_name(lnk->local_if));
1088     return RFC5444_OKAY;
1089   }
1090
1091   for (i=0; i<ARRAYSIZE(ldata->buckets); i++) {
1092     received += ldata->buckets[i].received;
1093     total += ldata->buckets[i].total;
1094   }
1095
1096   snprintf(buf->buf, sizeof(*buf), "p_recv=%"PRId64",p_total=%"PRId64","
1097       "speed=%"PRId64",success=%"PRId64",missed_hello=%d,lastseq=%u,lneigh=%d",
1098       received, total, (int64_t)_get_median_rx_linkspeed(ldata) * (int64_t)1024,
1099       ldata->last_packet_success_rate, ldata->missed_hellos,
1100       ldata->last_seq_nr, ldata->link_neigborhood);
1101   return buf->buf;
1102 }
1103
1104 /**
1105  * Callback triggered when configuration changes
1106  */
1107 static void
1108 _cb_cfg_changed(void) {
1109   struct ff_dat_if_config *ifconfig = NULL;
1110   struct nhdp_interface *nhdp_if;
1111   const char *ifname;
1112   char ifbuf[IF_NAMESIZE];
1113
1114   ifname = cfg_get_phy_if(ifbuf, _datff_section.section_name);
1115
1116   if (_datff_section.pre == NULL) {
1117     /* increase nhdp_interface refcount */
1118     nhdp_if = nhdp_interface_add(ifname);
1119   }
1120   else {
1121     /* get interface */
1122     nhdp_if = nhdp_interface_get(ifname);
1123   }
1124
1125   if (nhdp_if) {
1126     /* get block domain extension */
1127     ifconfig = oonf_class_get_extension(&_nhdpif_extenstion, nhdp_if);
1128     ifconfig->registered = true;
1129   }
1130
1131   if (_datff_section.post == NULL) {
1132     /* section was removed */
1133     if (nhdp_if != NULL) {
1134       ifconfig->registered = false;
1135
1136       /* decrease nhdp_interface refcount */
1137       nhdp_interface_remove(nhdp_if);
1138     }
1139
1140     nhdp_if = NULL;
1141   }
1142
1143   if (!nhdp_if) {
1144     return;
1145   }
1146
1147   if (cfg_schema_tobin(ifconfig, _datff_section.post,
1148       _datff_entries, ARRAYSIZE(_datff_entries))) {
1149     OONF_WARN(LOG_FF_DAT, "Cannot convert configuration for "
1150         OONF_FF_DAT_METRIC_SUBSYSTEM);
1151     return;
1152   }
1153
1154   /* start/change sampling timer */
1155   oonf_timer_set(&ifconfig->_sampling_timer, ifconfig->interval);
1156
1157 #ifdef COLLECT_RAW_DATA
1158   if (_rawdata_fd != -1) {
1159     fsync(_rawdata_fd);
1160     close(_rawdata_fd);
1161     _rawdata_end = 0;
1162     _rawdata_count = 0;
1163   }
1164
1165   if (_datff_config.rawdata_start) {
1166     _rawdata_fd = open(_datff_config.rawdata_file, O_CREAT | O_TRUNC | O_WRONLY,
1167                 S_IRUSR|S_IWUSR);
1168     if (_rawdata_fd != -1) {
1169       abuf_clear(&_rawdata_buf);
1170       abuf_appendf(&_rawdata_buf, "Time: %s\n", oonf_log_get_walltime());
1171       _rawdata_end = oonf_clock_get_absolute(_datff_config.rawdata_maxtime);
1172     }
1173   }
1174 #endif
1175 }