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