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