Update to new avl/list iteration macros
[olsrd.git] / lib / lq_etx_ff / src / lq_plugin_etx_ff.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, 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 #include "tc_set.h"
43 #include "link_set.h"
44 #include "lq_plugin.h"
45 #include "olsr_spf.h"
46 #include "lq_packet.h"
47 #include "olsr.h"
48 #include "lq_plugin_etx_ff.h"
49 #include "parser.h"
50 #include "mid_set.h"
51 #include "scheduler.h"
52 #include "olsr_logging.h"
53 #include "common/string.h"
54 #include "neighbor_table.h"
55
56 #define PLUGIN_DESCR "Freifunk ETX metric based on the original design of Elektra and Thomas Lopatic"
57 #define PLUGIN_AUTHOR "Henning Rogge"
58
59 #define LQ_ALGORITHM_ETX_FF_NAME "etx_ff"
60
61 #define LQ_FF_QUICKSTART_INIT 4
62
63 #define LQ_PLUGIN_RELEVANT_COSTCHANGE_FF 16
64
65 static bool lq_etxff_enable(void);
66
67 static void lq_etxff_initialize(void);
68 static void lq_etxff_deinitialize(void);
69
70 static olsr_linkcost lq_etxff_calc_link_entry_cost(struct link_entry *);
71 static olsr_linkcost lq_etxff_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *);
72 static olsr_linkcost lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *);
73
74 static void lq_etxff_hello_handler(struct link_entry *, bool);
75
76 static void lq_etxff_memorize_foreign_hello(struct link_entry *, struct lq_hello_neighbor *);
77 static void lq_etxff_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source);
78
79 static void lq_etxff_clear_link_entry(struct link_entry *);
80 static void lq_etxff_clear_tc_edge_entry(struct tc_edge_entry *);
81
82 static void lq_etxff_serialize_hello_lq(uint8_t **curr, struct link_entry *link);
83 static void lq_etxff_serialize_tc_lq(uint8_t **curr, struct link_entry *link);
84 static void lq_etxff_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *lq);
85 static void lq_etxff_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *lq);
86
87 static int lq_etxff_get_linkentry_data(struct link_entry *, int);
88 static const char *lq_etxff_print_cost(olsr_linkcost cost, char *buffer, size_t bufsize);
89 static const char *lq_etxff_print_link_entry_lq(struct link_entry *entry, int index, char *buffer, size_t bufsize);
90
91 static struct olsr_timer_info *default_lq_ff_timer_info = NULL;
92
93 OLSR_PLUGIN6_NP() {
94   .descr = PLUGIN_DESCR,
95   .author = PLUGIN_AUTHOR,
96   .enable = lq_etxff_enable,
97   .type = PLUGIN_TYPE_LQ
98 };
99
100 /* etx lq plugin (freifunk fpm version) settings */
101 struct lq_linkdata_type lq_etxff_linktypes[] = {
102   { "ETX", 5, 65536, 65536*2, 65536*4, INT32_MAX },
103   { "LQ", 5, 255, 240, 192, 0 },
104   { "NLQ", 5, 255, 240, 192, 0 }
105 };
106
107 struct lq_handler lq_etxff_handler = {
108   "etx (freifunk)",
109
110   &lq_etxff_initialize,
111   &lq_etxff_deinitialize,
112
113   &lq_etxff_calc_link_entry_cost,
114   &lq_etxff_calc_lq_hello_neighbor_cost,
115   &lq_etxff_calc_tc_edge_entry_cost,
116
117   &lq_etxff_hello_handler,
118
119   &lq_etxff_memorize_foreign_hello,
120   &lq_etxff_copy_link_entry_lq_into_tc_edge_entry,
121
122   &lq_etxff_clear_link_entry,
123   NULL,
124   &lq_etxff_clear_tc_edge_entry,
125
126   &lq_etxff_serialize_hello_lq,
127   &lq_etxff_serialize_tc_lq,
128   &lq_etxff_deserialize_hello_lq,
129   &lq_etxff_deserialize_tc_lq,
130
131   &lq_etxff_get_linkentry_data,
132   &lq_etxff_print_cost,
133   &lq_etxff_print_link_entry_lq,
134
135   lq_etxff_linktypes,
136   ARRAYSIZE(lq_etxff_linktypes),
137
138   sizeof(struct lq_etxff_tc_edge),
139   sizeof(struct lq_etxff_lq_hello_neighbor),
140   sizeof(struct lq_etxff_link_entry),
141
142   LQ_HELLO_MESSAGE,
143   LQ_TC_MESSAGE,
144
145   4,4
146 };
147
148 static bool lq_etxff_enable(void) {
149   active_lq_handler = &lq_etxff_handler;
150   return false;
151 }
152
153 static void
154 lq_etxff_packet_parser(struct olsr_packet *pkt, uint8_t *binary __attribute__ ((unused)),
155     struct interface *in_if, union olsr_ip_addr *from_addr)
156 {
157   const union olsr_ip_addr *main_addr;
158   struct lq_etxff_link_entry *lnk;
159   uint32_t seq_diff;
160
161   /* Find main address */
162   main_addr = olsr_lookup_main_addr_by_alias(from_addr);
163
164   /* Loopup link entry */
165   lnk = (struct lq_etxff_link_entry *)lookup_link_entry(from_addr, main_addr, in_if);
166   if (lnk == NULL) {
167     return;
168   }
169
170   if (lnk->last_seq_nr == pkt->seqno) {
171 #ifndef REMOVE_LOG_WARN
172     struct ipaddr_str buf;
173 #endif
174     OLSR_WARN(LOG_LQ_PLUGINS, "Got package with same sequence number from %s, if=%s, seq=0x%04x\n",
175         olsr_ip_to_string(&buf, from_addr), in_if->int_name, pkt->seqno);
176     return;
177   }
178   if (lnk->last_seq_nr > pkt->seqno) {
179     seq_diff = (uint32_t) pkt->seqno + 65536 - lnk->last_seq_nr;
180   } else {
181     seq_diff = pkt->seqno - lnk->last_seq_nr;
182   }
183
184   /* Jump in sequence numbers ? */
185   if (seq_diff > 256) {
186     seq_diff = 1;
187   }
188
189   lnk->received[lnk->activePtr]++;
190   lnk->lost[lnk->activePtr] += (seq_diff - 1);
191
192   lnk->last_seq_nr = pkt->seqno;
193   lnk->missed_seconds = 0;
194 }
195
196 static void
197 lq_etxff_timer(void __attribute__ ((unused)) * context)
198 {
199   struct link_entry *link, *link_iterator;
200   struct nbr_entry *nbr, *nbr_iterator;
201
202   OLSR_FOR_ALL_LINK_ENTRIES(link, link_iterator) {
203     struct lq_etxff_link_entry *lq_link;
204     uint32_t ratio;
205     uint16_t i, received, lost;
206
207 #ifndef REMOVE_LOG_DEBUG
208     struct ipaddr_str buf;
209     // struct lqtextbuffer lqbuffer;
210 #endif
211     lq_link = (struct lq_etxff_link_entry *)link;
212
213     OLSR_DEBUG(LOG_LQ_PLUGINS, "LQ-FF new entry for %s: rec: %d lost: %d",
214                olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
215                lq_link->received[lq_link->activePtr], lq_link->lost[lq_link->activePtr]);
216
217     received = 0;
218     lost = 0;
219
220     /* enlarge window if still in quickstart phase */
221     if (lq_link->windowSize < LQ_FF_WINDOW) {
222       lq_link->windowSize++;
223     }
224     for (i = 0; i < lq_link->windowSize; i++) {
225       received += lq_link->received[i];
226       lost += lq_link->lost[i];
227     }
228
229     OLSR_DEBUG(LOG_LQ_PLUGINS, " total-rec: %d total-lost: %d", received, lost);
230
231     /* calculate link quality */
232     if (received + lost == 0) {
233       lq_link->lq.valueLq = 0;
234     } else {
235
236       /* keep missed hello periods in mind (round up hello interval to seconds) */
237       uint32_t missed_hello_cost = lq_link->missed_seconds / ((lq_link->core.link_loss_timer->timer_period + 999) / 1000);
238       lost += missed_hello_cost * missed_hello_cost;
239
240       // start with link-loss-factor
241       ratio = link->loss_link_multiplier;
242
243       // calculate received/(received + loss) factor
244       ratio = ratio * received;
245       ratio = ratio / (received + lost);
246       ratio = (ratio * 255) >> 16;
247
248       lq_link->lq.valueLq = (uint8_t) (ratio);
249     }
250
251     // shift buffer
252     lq_link->activePtr = (lq_link->activePtr + 1) % LQ_FF_WINDOW;
253     lq_link->lost[lq_link->activePtr] = 0;
254     lq_link->received[lq_link->activePtr] = 0;
255     lq_link->missed_seconds++;
256
257     /* update linkcost */
258     link->linkcost = lq_etxff_calc_link_entry_cost(link);
259   }
260
261   OLSR_FOR_ALL_NBR_ENTRIES(nbr, nbr_iterator) {
262     olsr_neighbor_cost_may_changed(nbr);
263   }
264 }
265
266 static struct timer_entry *lq_etxff_timer_struct = NULL;
267
268 static void
269 lq_etxff_initialize(void)
270 {
271   /* Some cookies for stats keeping */
272   olsr_packetparser_add_function(&lq_etxff_packet_parser);
273   default_lq_ff_timer_info = olsr_alloc_timerinfo("Default Freifunk LQ",  &lq_etxff_timer, true);
274   lq_etxff_timer_struct = olsr_start_timer(1000, 0, NULL, default_lq_ff_timer_info);
275 }
276
277 static void
278 lq_etxff_deinitialize(void)
279 {
280   olsr_stop_timer(lq_etxff_timer_struct);
281   olsr_packetparser_remove_function(&lq_etxff_packet_parser);
282 }
283
284 static olsr_linkcost
285 lq_etxff_calc_linkcost(struct lq_etxff_linkquality *lq)
286 {
287   olsr_linkcost cost;
288
289   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
290     return LINK_COST_BROKEN;
291   }
292
293   cost = 65536 * 255 / (int)lq->valueLq * 255 / (int)lq->valueNlq;
294
295   if (cost > LINK_COST_BROKEN)
296     return LINK_COST_BROKEN;
297   if (cost == 0)
298     return 1;
299   return cost;
300 }
301
302 static olsr_linkcost
303 lq_etxff_calc_link_entry_cost(struct link_entry *link)
304 {
305   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
306
307   return lq_etxff_calc_linkcost(&lq_link->lq);
308 }
309
310 static olsr_linkcost
311 lq_etxff_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *neigh)
312 {
313   struct lq_etxff_lq_hello_neighbor *lq_neigh = (struct lq_etxff_lq_hello_neighbor *)neigh;
314
315   return lq_etxff_calc_linkcost(&lq_neigh->lq);
316 }
317
318 static olsr_linkcost
319 lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *edge)
320 {
321   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
322
323   return lq_etxff_calc_linkcost(&lq_edge->lq);
324 }
325
326 static void
327 lq_etxff_hello_handler(struct link_entry *link __attribute__ ((unused)), bool loss __attribute__ ((unused)))
328 {
329 }
330
331 static void
332 lq_etxff_memorize_foreign_hello(struct link_entry *target, struct lq_hello_neighbor *source)
333 {
334   struct lq_etxff_link_entry *lq_target = (struct lq_etxff_link_entry *)target;
335   struct lq_etxff_lq_hello_neighbor *lq_source = (struct lq_etxff_lq_hello_neighbor *)source;
336
337   if (source) {
338     lq_target->lq.valueNlq = lq_source->lq.valueLq;
339   } else {
340     lq_target->lq.valueNlq = 0;
341   }
342
343 }
344
345 static void
346 lq_etxff_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source)
347 {
348   struct lq_etxff_tc_edge *lq_target = (struct lq_etxff_tc_edge *)target;
349   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *)source;
350
351   lq_target->lq = lq_source->lq;
352 }
353
354 static void
355 lq_etxff_clear_link_entry(struct link_entry *link)
356 {
357   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
358   int i;
359
360   lq_link->windowSize = LQ_FF_QUICKSTART_INIT;
361   for (i = 0; i < LQ_FF_WINDOW; i++) {
362     lq_link->lost[i] = 3;
363   }
364 }
365
366 static void
367 lq_etxff_clear_tc_edge_entry(struct tc_edge_entry *edge) {
368   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
369
370   memset (&lq_edge->lq, 0, sizeof(lq_edge->lq));
371 }
372
373 static void
374 lq_etxff_serialize_hello_lq(uint8_t **curr, struct link_entry *link)
375 {
376   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
377
378   pkt_put_u8(curr, lq_link->lq.valueLq);
379   pkt_put_u8(curr, lq_link->lq.valueNlq);
380   pkt_put_u16(curr, 0);
381 }
382 static void
383 lq_etxff_serialize_tc_lq(uint8_t **curr, struct link_entry *link)
384 {
385   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
386
387   pkt_put_u8(curr, lq_link->lq.valueLq);
388   pkt_put_u8(curr, lq_link->lq.valueNlq);
389   pkt_put_u16(curr, 0);
390 }
391
392 static void
393 lq_etxff_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *neigh)
394 {
395   struct lq_etxff_lq_hello_neighbor *lq_neigh = (struct lq_etxff_lq_hello_neighbor *)neigh;
396
397   pkt_get_u8(curr, &lq_neigh->lq.valueLq);
398   pkt_get_u8(curr, &lq_neigh->lq.valueNlq);
399   pkt_ignore_u16(curr);
400
401 }
402 static void
403 lq_etxff_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *edge)
404 {
405   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
406
407   pkt_get_u8(curr, &lq_edge->lq.valueLq);
408   pkt_get_u8(curr, &lq_edge->lq.valueNlq);
409   pkt_ignore_u16(curr);
410 }
411
412 static int
413 lq_etxff_get_linkentry_data(struct link_entry *link, int idx) {
414   struct lq_etxff_link_entry *lq = (struct lq_etxff_link_entry *)link;
415   return idx == 1 ? lq->lq.valueLq : lq->lq.valueNlq;
416 }
417
418 static const char *
419 lq_etxff_print_link_entry_lq(struct link_entry *link, int idx, char *buffer, size_t bufsize)
420 {
421   struct lq_etxff_link_entry *lq = (struct lq_etxff_link_entry *)link;
422   uint8_t value;
423
424   if (idx == 1) {
425     value = lq->lq.valueLq;
426   }
427   else {
428     value = lq->lq.valueNlq;
429   }
430
431   if (value == 255) {
432     strscpy(buffer, "1.000", bufsize);
433   } else {
434     snprintf(buffer, bufsize, "0.%03d", (value * 1000) / 255);
435   }
436   return buffer;
437 }
438
439 static const char *
440 lq_etxff_print_cost(olsr_linkcost cost, char *buffer, size_t bufsize)
441 {
442   // must calculate
443   uint32_t roundDown = cost >> 16;
444   uint32_t fraction = ((cost & 0xffff) * 1000) >> 16;
445
446   snprintf(buffer, bufsize, "%u.%03u", roundDown, fraction);
447   return buffer;
448 }
449
450 /*
451  * Local Variables:
452  * c-basic-offset: 2
453  * indent-tabs-mode: nil
454  * End:
455  */