Some cleanup and logging during startup
[olsrd.git] / lib / lq_etx_ff / src / lq_plugin_etx_ff.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright
13  *   notice, this list of conditions and the following disclaimer in
14  *   the documentation and/or other materials provided with the
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its
17  *   contributors may be used to endorse or promote products derived
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  */
40
41 #include "tc_set.h"
42 #include "link_set.h"
43 #include "lq_plugin.h"
44 #include "olsr_spf.h"
45 #include "lq_packet.h"
46 #include "olsr.h"
47 #include "lq_plugin_etx_ff.h"
48 #include "parser.h"
49 #include "mid_set.h"
50 #include "scheduler.h"
51 #include "olsr_logging.h"
52
53 #define LQ_PLUGIN_RELEVANT_COSTCHANGE_FF 16
54
55 static void lq_etxff_initialize(void);
56 static void lq_etxff_deinitialize(void);
57
58 static olsr_linkcost lq_etxff_calc_link_entry_cost(struct link_entry *);
59 static olsr_linkcost lq_etxff_calc_lq_hello_neighbor_cost(
60     struct lq_hello_neighbor *);
61 static olsr_linkcost lq_etxff_calc_tc_mpr_addr_cost(struct tc_mpr_addr *);
62 static olsr_linkcost lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *);
63
64 static bool lq_etxff_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2);
65
66 static olsr_linkcost lq_etxff_packet_loss_handler(struct link_entry *, bool);
67
68 static void lq_etxff_memorize_foreign_hello(struct link_entry *,
69     struct lq_hello_neighbor *);
70 static void lq_etxff_copy_link_entry_lq_into_tc_mpr_addr(
71     struct tc_mpr_addr *target, struct link_entry *source);
72 static void lq_etxff_copy_link_entry_lq_into_tc_edge_entry(
73     struct tc_edge_entry *target, struct link_entry *source);
74 static void lq_etxff_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target,
75     struct link_entry *source);
76
77 static void lq_etxff_clear_link_entry(struct link_entry *);
78
79 static int lq_etxff_serialize_hello_lq(unsigned char *buff,
80     struct lq_hello_neighbor *lq);
81 static int lq_etxff_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *lq);
82 static void lq_etxff_deserialize_hello_lq(uint8_t const ** curr,
83     struct lq_hello_neighbor *lq);
84 static void lq_etxff_deserialize_tc_lq(uint8_t const ** curr,
85     struct tc_edge_entry *lq);
86
87 static char *lq_etxff_print_link_entry_lq(struct link_entry *entry, char separator,
88     struct lqtextbuffer *buffer);
89 static char *lq_etxff_print_tc_edge_entry_lq(struct tc_edge_entry *ptr,
90     char separator, struct lqtextbuffer * buffer);
91 static char *lq_etxff_print_cost(olsr_linkcost cost, struct lqtextbuffer * buffer);
92
93 static struct olsr_cookie_info *default_lq_ff_timer_cookie = NULL;
94
95 /* etx lq plugin (freifunk fpm version) settings */
96 struct lq_handler lq_etxff_handler = {
97   "etx (freifunk)",
98
99   &lq_etxff_initialize,
100   &lq_etxff_deinitialize,
101
102   &lq_etxff_calc_link_entry_cost,
103   &lq_etxff_calc_lq_hello_neighbor_cost,
104   &lq_etxff_calc_tc_mpr_addr_cost,
105   &lq_etxff_calc_tc_edge_entry_cost,
106
107   &lq_etxff_is_relevant_costchange,
108
109   &lq_etxff_packet_loss_handler,
110
111   &lq_etxff_memorize_foreign_hello,
112   &lq_etxff_copy_link_entry_lq_into_tc_mpr_addr,
113   &lq_etxff_copy_link_entry_lq_into_tc_edge_entry,
114   &lq_etxff_copy_link_lq_into_neighbor,
115
116   &lq_etxff_clear_link_entry,
117   NULL,
118   NULL,
119   NULL,
120
121   &lq_etxff_serialize_hello_lq,
122   &lq_etxff_serialize_tc_lq,
123   &lq_etxff_deserialize_hello_lq,
124   &lq_etxff_deserialize_tc_lq,
125
126   &lq_etxff_print_link_entry_lq,
127   &lq_etxff_print_tc_edge_entry_lq,
128   &lq_etxff_print_cost,
129
130   sizeof(struct lq_etxff_tc_edge),
131   sizeof(struct lq_etxff_tc_mpr_addr),
132   sizeof(struct lq_etxff_lq_hello_neighbor),
133   sizeof(struct lq_etxff_link_entry),
134
135   LQ_HELLO_MESSAGE,
136   LQ_TC_MESSAGE
137 };
138
139 static void lq_etxff_packet_parser(struct olsr *olsr, struct interface *in_if,
140     union olsr_ip_addr *from_addr) {
141   const union olsr_ip_addr *main_addr;
142   struct lq_etxff_link_entry *lnk;
143   uint32_t seq_diff;
144
145   /* Find main address */
146   main_addr = olsr_lookup_main_addr_by_alias(from_addr);
147
148   /* Loopup link entry */
149   lnk = (struct lq_etxff_link_entry *) lookup_link_entry(from_addr, main_addr,
150       in_if);
151   if (lnk == NULL) {
152     return;
153   }
154
155   if (lnk->last_seq_nr == olsr->olsr_seqno ) {
156 #ifndef REMOVE_LOG_WARN
157     struct ipaddr_str buf;
158 #endif
159     OLSR_WARN(LOG_LQ_PLUGINS, "Got package with same sequence number from %s\n", olsr_ip_to_string(&buf, from_addr));
160     return;
161   }
162   if (lnk->last_seq_nr > olsr->olsr_seqno) {
163     seq_diff = (uint32_t) olsr->olsr_seqno + 65536 - lnk->last_seq_nr;
164   } else {
165     seq_diff = olsr->olsr_seqno - lnk->last_seq_nr;
166   }
167
168   /* Jump in sequence numbers ? */
169   if (seq_diff > 256) {
170     seq_diff = 1;
171   }
172
173   lnk->received[lnk->activePtr]++;
174   lnk->lost[lnk->activePtr] += (seq_diff - 1);
175
176   lnk->last_seq_nr = olsr->olsr_seqno;
177   lnk->missed_seconds = 0;
178 }
179
180 static void lq_etxff_timer(void __attribute__((unused)) *context) {
181   struct link_entry *link;
182   OLSR_FOR_ALL_LINK_ENTRIES(link)
183   {
184     struct lq_etxff_link_entry *lq_link;
185     uint32_t ratio;
186     uint16_t i, received, lost;
187
188 #ifndef REMOVE_LOG_DEBUG
189     struct ipaddr_str buf;
190     // struct lqtextbuffer lqbuffer;
191 #endif
192     lq_link = (struct lq_etxff_link_entry *)link;
193
194     OLSR_DEBUG(LOG_LQ_PLUGINS, "LQ-FF new entry for %s: rec: %d lost: %d",
195       olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
196       lq_link->received[lq_link->activePtr], lq_link->lost[lq_link->activePtr]);
197
198     received = 0;
199     lost = 0;
200
201     /* enlarge window if still in quickstart phase */
202     if (lq_link->windowSize < LQ_FF_WINDOW) {
203       lq_link->windowSize++;
204     }
205     for (i=0; i < lq_link->windowSize; i++) {
206       received += lq_link->received[i];
207       lost += lq_link->lost[i];
208     }
209
210     OLSR_DEBUG(LOG_LQ_PLUGINS, " total-rec: %d total-lost: %d", received, lost);
211
212     /* calculate link quality */
213     if (received + lost == 0) {
214       lq_link->lq.valueLq = 0;
215     }
216     else {
217
218       /* keep missed hello periods in mind (round up hello interval to seconds) */
219       uint32_t missed_hello_cost = lq_link->missed_seconds / ((lq_link->core.link_loss_timer->timer_period + 999) / 1000);
220       lost += missed_hello_cost * missed_hello_cost;
221
222       // start with link-loss-factor
223       ratio = link->loss_link_multiplier;
224
225       // calculate received/(received + loss) factor
226       ratio = ratio * received;
227       ratio = ratio / (received + lost);
228       ratio = (ratio * 255) >> 16;
229
230       lq_link->lq.valueLq = (uint8_t)(ratio);
231     }
232
233     // shift buffer
234     lq_link->activePtr = (lq_link->activePtr + 1) % LQ_FF_WINDOW;
235     lq_link->lost[lq_link->activePtr] = 0;
236     lq_link->received[lq_link->activePtr] = 0;
237     lq_link->missed_seconds++;
238   }OLSR_FOR_ALL_LINK_ENTRIES_END(link);
239 }
240
241 static struct timer_entry *lq_etxff_timer_struct = NULL;
242
243 static void lq_etxff_initialize(void) {
244   /* Some cookies for stats keeping */
245   olsr_packetparser_add_function(&lq_etxff_packet_parser);
246   default_lq_ff_timer_cookie = olsr_alloc_cookie("Default Freifunk LQ",
247       OLSR_COOKIE_TYPE_TIMER);
248   lq_etxff_timer_struct = olsr_start_timer(1000, 0, OLSR_TIMER_PERIODIC,
249       &lq_etxff_timer, NULL, default_lq_ff_timer_cookie->ci_id);
250 }
251
252 static void lq_etxff_deinitialize(void) {
253   olsr_stop_timer(lq_etxff_timer_struct);
254   olsr_packetparser_remove_function(&lq_etxff_packet_parser);
255 }
256
257 static olsr_linkcost lq_etxff_calc_linkcost(struct lq_etxff_linkquality *lq) {
258   olsr_linkcost cost;
259
260   if (lq->valueLq < (unsigned int) (255 * MINIMAL_USEFUL_LQ) || lq->valueNlq
261       < (unsigned int) (255 * MINIMAL_USEFUL_LQ)) {
262     return LINK_COST_BROKEN;
263   }
264
265   cost = 65536 * 255/(int)lq->valueLq * 255/(int)lq->valueNlq;
266
267   if (cost > LINK_COST_BROKEN)
268     return LINK_COST_BROKEN;
269   if (cost == 0)
270     return 1;
271   return cost;
272 }
273
274 static olsr_linkcost lq_etxff_calc_link_entry_cost(struct link_entry *link) {
275   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *) link;
276
277   return lq_etxff_calc_linkcost(&lq_link->lq);
278 }
279
280 static olsr_linkcost lq_etxff_calc_lq_hello_neighbor_cost(
281     struct lq_hello_neighbor *neigh) {
282   struct lq_etxff_lq_hello_neighbor *lq_neigh =
283       (struct lq_etxff_lq_hello_neighbor *) neigh;
284
285   return lq_etxff_calc_linkcost(&lq_neigh->lq);
286 }
287
288 static olsr_linkcost lq_etxff_calc_tc_mpr_addr_cost(struct tc_mpr_addr *mpr) {
289   struct lq_etxff_tc_mpr_addr *lq_mpr = (struct lq_etxff_tc_mpr_addr *) mpr;
290
291   return lq_etxff_calc_linkcost(&lq_mpr->lq);
292 }
293
294 static olsr_linkcost lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *edge) {
295   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *) edge;
296
297   return lq_etxff_calc_linkcost(&lq_edge->lq);
298 }
299
300 static bool lq_etxff_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2) {
301   if (c1 > c2) {
302     return c2 - c1 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
303   }
304   return c1 - c2 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
305 }
306
307 static olsr_linkcost lq_etxff_packet_loss_handler(struct link_entry *link,
308     bool loss __attribute__((unused))) {
309   return lq_etxff_calc_link_entry_cost(link);
310 }
311
312 static void lq_etxff_memorize_foreign_hello(struct link_entry *target,
313     struct lq_hello_neighbor *source) {
314   struct lq_etxff_link_entry *lq_target = (struct lq_etxff_link_entry *) target;
315   struct lq_etxff_lq_hello_neighbor *lq_source =
316       (struct lq_etxff_lq_hello_neighbor *) source;
317
318   if (source) {
319     lq_target->lq.valueNlq = lq_source->lq.valueLq;
320   } else {
321     lq_target->lq.valueNlq = 0;
322   }
323
324 }
325
326 static void lq_etxff_copy_link_entry_lq_into_tc_mpr_addr(
327     struct tc_mpr_addr *target, struct link_entry *source) {
328   struct lq_etxff_tc_mpr_addr *lq_target = (struct lq_etxff_tc_mpr_addr *) target;
329   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *) source;
330
331   lq_target->lq = lq_source->lq;
332 }
333
334 static void lq_etxff_copy_link_entry_lq_into_tc_edge_entry(
335     struct tc_edge_entry *target, struct link_entry *source) {
336   struct lq_etxff_tc_edge *lq_target = (struct lq_etxff_tc_edge *) target;
337   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *) source;
338
339   lq_target->lq = lq_source->lq;
340 }
341
342 static void lq_etxff_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target,
343     struct link_entry *source) {
344   struct lq_etxff_lq_hello_neighbor *lq_target =
345       (struct lq_etxff_lq_hello_neighbor *) target;
346   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *) source;
347
348   lq_target->lq = lq_source->lq;
349 }
350
351 static void lq_etxff_clear_link_entry(struct link_entry *link) {
352   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *) link;
353   int i;
354
355   lq_link->windowSize = LQ_FF_QUICKSTART_INIT;
356   for (i = 0; i < LQ_FF_WINDOW; i++) {
357     lq_link->lost[i] = 3;
358   }
359 }
360
361 static int lq_etxff_serialize_hello_lq(unsigned char *buff,
362     struct lq_hello_neighbor *neigh) {
363   struct lq_etxff_lq_hello_neighbor *lq_neigh =
364       (struct lq_etxff_lq_hello_neighbor *) neigh;
365
366   buff[0] = (unsigned char) lq_neigh->lq.valueLq;
367   buff[1] = (unsigned char) lq_neigh->lq.valueNlq;
368   buff[2] = (unsigned char) (0);
369   buff[3] = (unsigned char) (0);
370
371   return 4;
372 }
373 static int lq_etxff_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *mpr) {
374   struct lq_etxff_tc_mpr_addr *lq_mpr = (struct lq_etxff_tc_mpr_addr *) mpr;
375
376   buff[0] = (unsigned char) lq_mpr->lq.valueLq;
377   buff[1] = (unsigned char) lq_mpr->lq.valueNlq;
378   buff[2] = (unsigned char) (0);
379   buff[3] = (unsigned char) (0);
380
381   return 4;
382 }
383
384 static void lq_etxff_deserialize_hello_lq(uint8_t const ** curr,
385     struct lq_hello_neighbor *neigh) {
386   struct lq_etxff_lq_hello_neighbor *lq_neigh =
387       (struct lq_etxff_lq_hello_neighbor *) neigh;
388
389   pkt_get_u8(curr, &lq_neigh->lq.valueLq);
390   pkt_get_u8(curr, &lq_neigh->lq.valueNlq);
391   pkt_ignore_u16(curr);
392
393 }
394 static void lq_etxff_deserialize_tc_lq(uint8_t const ** curr,
395     struct tc_edge_entry *edge) {
396   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *) edge;
397
398   pkt_get_u8(curr, &lq_edge->lq.valueLq);
399   pkt_get_u8(curr, &lq_edge->lq.valueNlq);
400   pkt_ignore_u16(curr);
401 }
402
403 static char *lq_etxff_print_lq(struct lq_etxff_linkquality *lq, char separator,
404     struct lqtextbuffer *buffer) {
405   int i = 0;
406
407   if (lq->valueLq == 255) {
408         strcpy(buffer->buf, "1.000");
409         i += 5;
410   }
411   else {
412     i = sprintf(buffer->buf, "0.%03d", (lq->valueLq * 1000)/255);
413   }
414   buffer->buf[i++] = separator;
415
416   if (lq->valueNlq == 255) {
417     strcpy(&buffer->buf[i], "1.000");
418   }
419   else {
420     sprintf(&buffer->buf[i], "0.%03d", (lq->valueNlq * 1000) / 255);
421   }
422   return buffer->buf;
423 }
424
425 static char *lq_etxff_print_link_entry_lq(struct link_entry *link, char separator,
426     struct lqtextbuffer *buffer) {
427   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *) link;
428
429   return lq_etxff_print_lq(&lq_link->lq, separator, buffer);
430 }
431
432 static char *lq_etxff_print_tc_edge_entry_lq(struct tc_edge_entry *edge,
433     char separator, struct lqtextbuffer * buffer) {
434   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *) edge;
435
436   return lq_etxff_print_lq(&lq_edge->lq, separator, buffer);
437 }
438
439 static char *lq_etxff_print_cost(olsr_linkcost cost, struct lqtextbuffer * buffer) {
440   // must calculate
441   uint32_t roundDown = cost >> 16;
442   uint32_t fraction = ((cost & 0xffff) * 1000) >> 16;
443
444   sprintf(buffer->buf, "%u.%03u", roundDown, fraction);
445   return buffer->buf;
446 }
447
448 /*
449  * Local Variables:
450  * c-basic-offset: 2
451  * indent-tabs-mode: nil
452  * End:
453  */