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