f6b0cdd729dbc3b25a7425b36482012c7ba9607e
[olsrd.git] / src / linux / lq_plugin_ffeth_nl80211.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2008 Henning Rogge <rogge@fgan.de>
5  * Copyright (c) 2012 Fox-IT B.V. <opensource@fox-it.com>
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * * Redistributions of source code must retain the above copyright
13  *   notice, this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above copyright
15  *   notice, this list of conditions and the following disclaimer in
16  *   the documentation and/or other materials provided with the
17  *   distribution.
18  * * Neither the name of olsr.org, olsrd nor the names of its
19  *   contributors may be used to endorse or promote products derived
20  *   from this software without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33  * POSSIBILITY OF SUCH DAMAGE.
34  *
35  * Visit http://www.olsr.org for more information.
36  *
37  * If you find this software useful feel free to make a donation
38  * to the project. For more information see the website or contact
39  * the copyright holders.
40  *
41  */
42
43 #ifdef LINUX_NL80211 /* Optional - not supported on all platforms */
44
45 #include "lq_plugin_ffeth_nl80211.h"
46 #include "tc_set.h"
47 #include "link_set.h"
48 #include "lq_plugin.h"
49 #include "olsr_spf.h"
50 #include "lq_packet.h"
51 #include "packet.h"
52 #include "olsr.h"
53 #include "parser.h"
54 #include "fpm.h"
55 #include "mid_set.h"
56 #include "scheduler.h"
57 #include "log.h"
58
59 #ifdef LINUX_NL80211
60 #include "nl80211_link_info.h"
61 #define WEIGHT_ETX                      50
62 #define WEIGHT_BANDWIDTH        50
63 #endif
64
65 #define LQ_PLUGIN_LC_MULTIPLIER 1024
66 #define LQ_PLUGIN_RELEVANT_COSTCHANGE_FF 16
67
68 static void lq_initialize_ffeth_nl80211(void);
69
70 static olsr_linkcost lq_calc_cost_ffeth_nl80211(const void *lq);
71
72 static void lq_packet_loss_worker_ffeth_nl80211(struct link_entry *link, void *lq, bool lost);
73 static void lq_memorize_foreign_hello_ffeth_nl80211(void *local, void *foreign);
74
75 static int lq_serialize_hello_lq_pair_ffeth_nl80211(unsigned char *buff, void *lq);
76 static void lq_deserialize_hello_lq_pair_ffeth_nl80211(const uint8_t ** curr, void *lq);
77 static int lq_serialize_tc_lq_pair_ffeth_nl80211(unsigned char *buff, void *lq);
78 static void lq_deserialize_tc_lq_pair_ffeth_nl80211(const uint8_t ** curr, void *lq);
79
80 static void lq_copy_link2neigh_ffeth_nl80211(void *t, void *s);
81 static void lq_copy_link2tc_ffeth_nl80211(void *target, void *source);
82 static void lq_clear_ffeth_nl80211(void *target);
83 static void lq_clear_ffeth_nl80211_hello(void *target);
84
85 static const char *lq_print_ffeth_nl80211(void *ptr, char separator, struct lqtextbuffer *buffer);
86 static const char *lq_print_cost_ffeth_nl80211(olsr_linkcost cost, struct lqtextbuffer *buffer);
87
88 /* etx lq plugin (freifunk fpm version) settings */
89 struct lq_handler lq_etx_ffeth_nl80211_handler = {
90   &lq_initialize_ffeth_nl80211,
91   &lq_calc_cost_ffeth_nl80211,
92   &lq_calc_cost_ffeth_nl80211,
93
94   &lq_packet_loss_worker_ffeth_nl80211,
95
96   &lq_memorize_foreign_hello_ffeth_nl80211,
97   &lq_copy_link2neigh_ffeth_nl80211,
98   &lq_copy_link2tc_ffeth_nl80211,
99   &lq_clear_ffeth_nl80211_hello,
100   &lq_clear_ffeth_nl80211,
101
102   &lq_serialize_hello_lq_pair_ffeth_nl80211,
103   &lq_serialize_tc_lq_pair_ffeth_nl80211,
104   &lq_deserialize_hello_lq_pair_ffeth_nl80211,
105   &lq_deserialize_tc_lq_pair_ffeth_nl80211,
106
107   &lq_print_ffeth_nl80211,
108   &lq_print_ffeth_nl80211,
109   &lq_print_cost_ffeth_nl80211,
110
111   sizeof(struct lq_ffeth_hello),
112   sizeof(struct lq_ffeth),
113   4,
114   4
115 };
116
117 static void
118 lq_ffeth_nl80211_handle_lqchange(void) {
119   struct lq_ffeth_hello *lq;
120   struct ipaddr_str buf;
121   struct link_entry *link;
122
123   bool triggered = false;
124
125   OLSR_FOR_ALL_LINK_ENTRIES(link) {
126     bool relevant = false;
127     lq = (struct lq_ffeth_hello *)link->linkquality;
128
129 #if 0
130   fprintf(stderr, "%s: old = %u/%u   new = %u/%u\n", olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
131       lq->smoothed_lq.valueLq, lq->smoothed_lq.valueNlq,
132       lq->lq.valueLq, lq->lq.valueNlq);
133 #endif
134
135     if (lq->smoothed_lq.valueLq < lq->lq.valueLq) {
136       if (lq->lq.valueLq >= 254 || lq->lq.valueLq - lq->smoothed_lq.valueLq > lq->smoothed_lq.valueLq/10) {
137         relevant = true;
138       }
139     }
140     else if (lq->smoothed_lq.valueLq > lq->lq.valueLq) {
141       if (lq->smoothed_lq.valueLq - lq->lq.valueLq > lq->smoothed_lq.valueLq/10) {
142         relevant = true;
143       }
144     }
145     if (lq->smoothed_lq.valueNlq < lq->lq.valueNlq) {
146       if (lq->lq.valueNlq >= 254 || lq->lq.valueNlq - lq->smoothed_lq.valueNlq > lq->smoothed_lq.valueNlq/10) {
147         relevant = true;
148       }
149     }
150     else if (lq->smoothed_lq.valueNlq > lq->lq.valueNlq) {
151       if (lq->smoothed_lq.valueNlq - lq->lq.valueNlq > lq->smoothed_lq.valueNlq/10) {
152         relevant = true;
153       }
154     }
155
156     if (relevant) {
157       memcpy(&lq->smoothed_lq, &lq->lq, sizeof(struct lq_ffeth));
158       link->linkcost = lq_calc_cost_ffeth_nl80211(&lq->smoothed_lq);
159       triggered = true;
160     }
161   } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
162
163   if (!triggered) {
164     return;
165   }
166
167   OLSR_FOR_ALL_LINK_ENTRIES(link) {
168     lq = (struct lq_ffeth_hello *)link->linkquality;
169
170     if (lq->smoothed_lq.valueLq >= 254 && lq->smoothed_lq.valueNlq >= 254) {
171       continue;
172     }
173
174     if (lq->smoothed_lq.valueLq == lq->lq.valueLq && lq->smoothed_lq.valueNlq == lq->lq.valueNlq) {
175       continue;
176     }
177
178     memcpy(&lq->smoothed_lq, &lq->lq, sizeof(struct lq_ffeth));
179     link->linkcost = lq_calc_cost_ffeth_nl80211(&lq->smoothed_lq);
180   } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
181
182   olsr_relevant_linkcost_change();
183 }
184
185 static void
186 lq_parser_ffeth_nl80211(struct olsr *olsr, struct interface *in_if, union olsr_ip_addr *from_addr)
187 {
188   const union olsr_ip_addr *main_addr;
189   struct link_entry *lnk;
190   struct lq_ffeth_hello *lq;
191   uint32_t seq_diff;
192
193   /* Find main address */
194   main_addr = mid_lookup_main_addr(from_addr);
195
196   /* Loopup link entry */
197   lnk = lookup_link_entry(from_addr, main_addr, in_if);
198   if (lnk == NULL) {
199     return;
200   }
201
202   lq = (struct lq_ffeth_hello *)lnk->linkquality;
203
204   /* ignore double package */
205   if (lq->last_seq_nr == olsr->olsr_seqno) {
206     struct ipaddr_str buf;
207     olsr_syslog(OLSR_LOG_INFO, "detected duplicate packet with seqnr %d from %s on %s (%d Bytes)",
208                 olsr->olsr_seqno,olsr_ip_to_string(&buf, from_addr),in_if->int_name,ntohs(olsr->olsr_packlen));
209     return;
210   }
211
212   if (lq->last_seq_nr > olsr->olsr_seqno) {
213     seq_diff = (uint32_t) olsr->olsr_seqno + 65536 - lq->last_seq_nr;
214   } else {
215     seq_diff = olsr->olsr_seqno - lq->last_seq_nr;
216   }
217
218   /* Jump in sequence numbers ? */
219   if (seq_diff > 256) {
220     seq_diff = 1;
221   }
222
223   lq->received[lq->activePtr]++;
224   lq->total[lq->activePtr] += seq_diff;
225
226   lq->last_seq_nr = olsr->olsr_seqno;
227   lq->missed_hellos = 0;
228 }
229
230 static void
231 lq_ffeth_nl80211_timer(void __attribute__ ((unused)) * context)
232 {
233   struct link_entry *link;
234
235 #ifdef LINUX_NL80211
236         nl80211_link_info_get();
237 #endif
238
239   OLSR_FOR_ALL_LINK_ENTRIES(link) {
240     struct lq_ffeth_hello *tlq = (struct lq_ffeth_hello *)link->linkquality;
241     fpm ratio;
242     int i, received, total;
243
244     received = 0;
245     total = 0;
246
247     /* enlarge window if still in quickstart phase */
248     if (tlq->windowSize < LQ_FFETH_WINDOW) {
249       tlq->windowSize++;
250     }
251     for (i = 0; i < tlq->windowSize; i++) {
252       received += tlq->received[i];
253       total += tlq->total[i];
254     }
255
256     /* calculate link quality */
257     if (total == 0) {
258       tlq->lq.valueLq = 0;
259     } else {
260       // start with link-loss-factor
261       ratio = fpmidiv(itofpm(link->loss_link_multiplier), LINK_LOSS_MULTIPLIER);
262
263       /* keep missed hello periods in mind (round up hello interval to seconds) */
264       if (tlq->missed_hellos > 1) {
265         received = received - received * tlq->missed_hellos * link->inter->hello_etime/1000 / LQ_FFETH_WINDOW;
266       }
267
268       // calculate received/total factor
269       ratio = fpmmuli(ratio, received);
270       ratio = fpmidiv(ratio, total);
271       ratio = fpmmuli(ratio, 255);
272
273       tlq->lq.valueLq = (uint8_t) (fpmtoi(ratio));
274     }
275
276     /* ethernet booster */
277     if (link->inter->mode == IF_MODE_ETHER) {
278       if (tlq->lq.valueLq > (uint8_t)(0.95 * 255)) {
279         tlq->perfect_eth = true;
280       }
281       else if (tlq->lq.valueLq > (uint8_t)(0.90 * 255)) {
282         tlq->perfect_eth = false;
283       }
284
285       if (tlq->perfect_eth) {
286         tlq->lq.valueLq = 255;
287       }
288     }
289     else if (link->inter->mode != IF_MODE_ETHER && tlq->lq.valueLq > 0) {
290       tlq->lq.valueLq--;
291     }
292
293     // shift buffer
294     tlq->activePtr = (tlq->activePtr + 1) % LQ_FFETH_WINDOW;
295     tlq->total[tlq->activePtr] = 0;
296     tlq->received[tlq->activePtr] = 0;
297
298   } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
299
300   lq_ffeth_nl80211_handle_lqchange();
301 }
302
303 static void
304 lq_initialize_ffeth_nl80211(void)
305 {
306   if (olsr_cnf->lq_nat_thresh < 1.0f) {
307     fprintf(stderr, "Warning, nat_treshold < 1.0 is more likely to produce loops with etx_ffeth\n");
308   }
309   olsr_packetparser_add_function(&lq_parser_ffeth_nl80211);
310   olsr_start_timer(1000, 0, OLSR_TIMER_PERIODIC, &lq_ffeth_nl80211_timer, NULL, 0);
311
312 #ifdef LINUX_NL80211
313   nl80211_link_info_init();
314 #endif
315 }
316
317 static olsr_linkcost
318 lq_calc_cost_ffeth_nl80211(const void *ptr)
319 {
320   const struct lq_ffeth *lq = ptr;
321   olsr_linkcost cost;
322   bool ether;
323   int lq_int, nlq_int;
324 #ifdef LINUX_NL80211
325   fpm nl80211 = itofpm((int) lq->valueBandwidth + lq->valueRSSI);
326 #endif
327
328   // MINIMAL_USEFUL_LQ is a float, multiplying by 255 converts it to uint8_t
329   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
330     return LINK_COST_BROKEN;
331   }
332
333   ether = lq->valueLq == 255 && lq->valueNlq == 255;
334
335   lq_int = (int)lq->valueLq;
336   if (lq_int > 0 && lq_int < 255) {
337     lq_int++;
338   }
339
340   nlq_int = (int)lq->valueNlq;
341   if (nlq_int > 0 && nlq_int < 255) {
342     nlq_int++;
343   }
344
345 #ifdef LINUX_NL80211
346   nl80211 = fpmidiv(nl80211, 255);
347   cost = fpmidiv(itofpm(255 * 255), lq_int * nlq_int); // 1 / (LQ * NLQ)
348   cost = fpmadd(cost, nl80211);
349 #else
350   cost = fpmidiv(itofpm(255 * 255), lq_int * nlq_int); // 1 / (LQ * NLQ)
351 #endif
352   if (ether) {
353     /* ethernet boost */
354     cost /= 10;
355   }
356
357   if (cost > LINK_COST_BROKEN)
358     return LINK_COST_BROKEN;
359   if (cost == 0)
360     return 1;
361   return cost;
362 }
363
364 static int
365 lq_serialize_hello_lq_pair_ffeth_nl80211(unsigned char *buff, void *ptr)
366 {
367   struct lq_ffeth *lq = ptr;
368
369 #ifdef LINUX_NL80211
370   buff[0] = lq->valueBandwidth;
371   buff[1] = lq->valueRSSI;
372 #else
373   buff[0] = (unsigned char)(0);
374   buff[1] = (unsigned char)(0);
375 #endif
376   buff[2] = (unsigned char)lq->valueLq;
377   buff[3] = (unsigned char)lq->valueNlq;
378
379   return 4;
380 }
381
382 static void
383 lq_deserialize_hello_lq_pair_ffeth_nl80211(const uint8_t ** curr, void *ptr)
384 {
385   struct lq_ffeth *lq = ptr;
386
387 #ifdef LINUX_NL80211
388   pkt_get_u8(curr, &lq->valueBandwidth);
389   pkt_get_u8(curr, &lq->valueRSSI);
390 #else
391   pkt_ignore_u16(curr);
392 #endif
393   pkt_get_u8(curr, &lq->valueLq);
394   pkt_get_u8(curr, &lq->valueNlq);
395 }
396
397 static int
398 lq_serialize_tc_lq_pair_ffeth_nl80211(unsigned char *buff, void *ptr)
399 {
400   struct lq_ffeth *lq = ptr;
401
402 #ifdef LINUX_NL80211
403   buff[0] = lq->valueBandwidth;
404   buff[1] = lq->valueRSSI;
405 #else
406   buff[0] = (unsigned char)(0);
407   buff[1] = (unsigned char)(0);
408 #endif
409   buff[2] = (unsigned char)lq->valueLq;
410   buff[3] = (unsigned char)lq->valueNlq;
411
412   return 4;
413 }
414
415 static void
416 lq_deserialize_tc_lq_pair_ffeth_nl80211(const uint8_t ** curr, void *ptr)
417 {
418   struct lq_ffeth *lq = ptr;
419
420 #ifdef LINUX_NL80211
421   pkt_get_u8(curr, &lq->valueBandwidth);
422   pkt_get_u8(curr, &lq->valueRSSI);
423 #else
424   pkt_ignore_u16(curr);
425 #endif
426   pkt_get_u8(curr, &lq->valueLq);
427   pkt_get_u8(curr, &lq->valueNlq);
428 }
429
430 static void
431 lq_packet_loss_worker_ffeth_nl80211(struct link_entry *link,
432     void __attribute__ ((unused)) *ptr, bool lost)
433 {
434   struct lq_ffeth_hello *tlq = (struct lq_ffeth_hello *)link->linkquality;
435
436   if (lost) {
437     tlq->missed_hellos++;
438   }
439   return;
440 }
441
442 static void
443 lq_memorize_foreign_hello_ffeth_nl80211(void *ptrLocal, void *ptrForeign)
444 {
445   struct lq_ffeth_hello *local = ptrLocal;
446   struct lq_ffeth *foreign = ptrForeign;
447
448   if (foreign) {
449     local->lq.valueNlq = foreign->valueLq;
450   } else {
451     local->lq.valueNlq = 0;
452   }
453 }
454
455 static void
456 lq_copy_link2neigh_ffeth_nl80211(void *t, void *s)
457 {
458   struct lq_ffeth *target = t;
459   struct lq_ffeth_hello *source = s;
460   *target = source->smoothed_lq;
461 }
462
463 static void
464 lq_copy_link2tc_ffeth_nl80211(void *t, void *s)
465 {
466   struct lq_ffeth *target = t;
467   struct lq_ffeth_hello *source = s;
468   *target = source->smoothed_lq;
469 }
470
471 static void
472 lq_clear_ffeth_nl80211(void *target)
473 {
474   memset(target, 0, sizeof(struct lq_ffeth));
475 }
476
477 static void
478 lq_clear_ffeth_nl80211_hello(void *target)
479 {
480   struct lq_ffeth_hello *local = target;
481   int i;
482
483   lq_clear_ffeth_nl80211(&local->lq);
484   lq_clear_ffeth_nl80211(&local->smoothed_lq);
485   local->windowSize = LQ_FFETH_QUICKSTART_INIT;
486   for (i = 0; i < LQ_FFETH_WINDOW; i++) {
487     local->total[i] = 3;
488   }
489 }
490
491 static const char *
492 lq_print_ffeth_nl80211(void *ptr, char separator, struct lqtextbuffer *buffer)
493 {
494   struct lq_ffeth *lq = ptr;
495   int lq_int, nlq_int;
496
497   lq_int = (int)lq->valueLq;
498   if (lq_int > 0 && lq_int < 255) {
499     lq_int++;
500   }
501
502   nlq_int = (int)lq->valueNlq;
503   if (nlq_int > 0 && nlq_int < 255) {
504     nlq_int++;
505   }
506
507   snprintf(buffer->buf, sizeof(buffer->buf), "%s%c%s", fpmtoa(fpmidiv(itofpm(lq_int), 255)), separator,
508            fpmtoa(fpmidiv(itofpm(nlq_int), 255)));
509   return buffer->buf;
510 }
511
512 static const char *
513 lq_print_cost_ffeth_nl80211(olsr_linkcost cost, struct lqtextbuffer *buffer)
514 {
515   snprintf(buffer->buf, sizeof(buffer->buf), "%s", fpmtoa(cost));
516   return buffer->buf;
517 }
518
519 #endif /* LINUX_NL80211 */
520
521 /*
522  * Local Variables:
523  * c-basic-offset: 2
524  * indent-tabs-mode: nil
525  * End:
526  */