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