backport of duplicate packet fix
[olsrd.git] / src / lq_plugin_default_ff.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2008 Henning Rogge <rogge@fgan.de>
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 "packet.h"
48 #include "olsr.h"
49 #include "lq_plugin_default_ff.h"
50 #include "parser.h"
51 #include "fpm.h"
52 #include "mid_set.h"
53 #include "scheduler.h"
54 #include "log.h"
55
56 /* etx lq plugin (freifunk fpm version) settings */
57 struct lq_handler lq_etx_ff_handler = {
58   &default_lq_initialize_ff,
59   &default_lq_calc_cost_ff,
60   &default_lq_calc_cost_ff,
61
62   &default_lq_is_relevant_costchange_ff,
63   &default_lq_packet_loss_worker_ff,
64
65   &default_lq_memorize_foreign_hello_ff,
66   &default_lq_copy_link2tc_ff,
67   &default_lq_clear_ff_hello,
68   &default_lq_clear_ff,
69
70   &default_lq_serialize_hello_lq_pair_ff,
71   &default_lq_serialize_tc_lq_pair_ff,
72   &default_lq_deserialize_hello_lq_pair_ff,
73   &default_lq_deserialize_tc_lq_pair_ff,
74
75   &default_lq_print_ff,
76   &default_lq_print_ff,
77   &default_lq_print_cost_ff,
78
79   sizeof(struct default_lq_ff_hello),
80   sizeof(struct default_lq_ff)
81 };
82
83 static void
84 default_lq_parser_ff(struct olsr *olsr, struct interface *in_if, union olsr_ip_addr *from_addr)
85 {
86   const union olsr_ip_addr *main_addr;
87   struct link_entry *lnk;
88   struct default_lq_ff_hello *lq;
89   uint32_t seq_diff;
90
91   /* Find main address */
92   main_addr = mid_lookup_main_addr(from_addr);
93
94   /* Loopup link entry */
95   lnk = lookup_link_entry(from_addr, main_addr, in_if);
96   if (lnk == NULL) {
97     return;
98   }
99
100   lq = (struct default_lq_ff_hello *)lnk->linkquality;
101
102   /* ignore double package */
103   if (lq->last_seq_nr == olsr->olsr_seqno) {
104     struct ipaddr_str buf;
105     olsr_syslog(OLSR_LOG_INFO, "detected duplicate packet with seqnr %d from %s on %s (%d Bytes)",
106                 olsr->olsr_seqno,olsr_ip_to_string(&buf, from_addr),in_if->int_name,ntohs(olsr->olsr_packlen));
107     return;
108   }
109
110   if (lq->last_seq_nr > olsr->olsr_seqno) {
111     seq_diff = (uint32_t) olsr->olsr_seqno + 65536 - lq->last_seq_nr;
112   } else {
113     seq_diff = olsr->olsr_seqno - lq->last_seq_nr;
114   }
115
116   /* Jump in sequence numbers ? */
117   if (seq_diff > 256) {
118     seq_diff = 1;
119   }
120
121   lq->received[lq->activePtr]++;
122   lq->lost[lq->activePtr] += (seq_diff - 1);
123
124   lq->last_seq_nr = olsr->olsr_seqno;
125 }
126
127 static void
128 default_lq_ff_timer(void __attribute__ ((unused)) * context)
129 {
130   struct link_entry *link;
131   OLSR_FOR_ALL_LINK_ENTRIES(link) {
132     struct default_lq_ff_hello *tlq = (struct default_lq_ff_hello *)link->linkquality;
133     fpm ratio;
134     uint16_t i, received, lost;
135
136     received = 0;
137     lost = 0;
138
139     /* enlarge window if still in quickstart phase */
140     if (tlq->windowSize < LQ_FF_WINDOW) {
141       tlq->windowSize++;
142     }
143     for (i = 0; i < tlq->windowSize; i++) {
144       received += tlq->received[i];
145       lost += tlq->lost[i];
146     }
147
148     /* calculate link quality */
149     if (received + lost == 0) {
150       tlq->lq.valueLq = 0;
151     } else {
152       // start with link-loss-factor
153       ratio = fpmidiv(itofpm(link->loss_link_multiplier), 65536);
154
155       // calculate received/(received + loss) factor
156       ratio = fpmmuli(ratio, (int)received);
157       ratio = fpmidiv(ratio, (int)(received + lost));
158       ratio = fpmmuli(ratio, 255);
159
160       tlq->lq.valueLq = (uint8_t) (fpmtoi(ratio));
161     }
162     link->linkcost = default_lq_calc_cost_ff(tlq);
163
164     // shift buffer
165     tlq->activePtr = (tlq->activePtr + 1) % LQ_FF_WINDOW;
166     tlq->lost[tlq->activePtr] = 0;
167     tlq->received[tlq->activePtr] = 0;
168   } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
169 }
170
171 void
172 default_lq_initialize_ff(void)
173 {
174   olsr_packetparser_add_function(&default_lq_parser_ff);
175   olsr_start_timer(1000, 0, OLSR_TIMER_PERIODIC, &default_lq_ff_timer, NULL, 0);
176 }
177
178 olsr_linkcost
179 default_lq_calc_cost_ff(const void *ptr)
180 {
181   const struct default_lq_ff *lq = ptr;
182   olsr_linkcost cost;
183
184   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
185     return LINK_COST_BROKEN;
186   }
187
188   cost = fpmidiv(itofpm(255 * 255), (int)lq->valueLq * (int)lq->valueNlq);
189
190   if (cost > LINK_COST_BROKEN)
191     return LINK_COST_BROKEN;
192   if (cost == 0)
193     return 1;
194   return cost;
195 }
196
197 int
198 default_lq_serialize_hello_lq_pair_ff(unsigned char *buff, void *ptr)
199 {
200   struct default_lq_ff *lq = ptr;
201
202   buff[0] = (unsigned char)lq->valueLq;
203   buff[1] = (unsigned char)lq->valueNlq;
204   buff[2] = (unsigned char)(0);
205   buff[3] = (unsigned char)(0);
206
207   return 4;
208 }
209
210 void
211 default_lq_deserialize_hello_lq_pair_ff(const uint8_t ** curr, void *ptr)
212 {
213   struct default_lq_ff *lq = ptr;
214
215   pkt_get_u8(curr, &lq->valueLq);
216   pkt_get_u8(curr, &lq->valueNlq);
217   pkt_ignore_u16(curr);
218 }
219
220 bool
221 default_lq_is_relevant_costchange_ff(olsr_linkcost c1, olsr_linkcost c2)
222 {
223   if (c1 > c2) {
224     return c2 - c1 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
225   }
226   return c1 - c2 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
227 }
228
229 int
230 default_lq_serialize_tc_lq_pair_ff(unsigned char *buff, void *ptr)
231 {
232   struct default_lq_ff *lq = ptr;
233
234   buff[0] = (unsigned char)lq->valueLq;
235   buff[1] = (unsigned char)lq->valueNlq;
236   buff[2] = (unsigned char)(0);
237   buff[3] = (unsigned char)(0);
238
239   return 4;
240 }
241
242 void
243 default_lq_deserialize_tc_lq_pair_ff(const uint8_t ** curr, void *ptr)
244 {
245   struct default_lq_ff *lq = ptr;
246
247   pkt_get_u8(curr, &lq->valueLq);
248   pkt_get_u8(curr, &lq->valueNlq);
249   pkt_ignore_u16(curr);
250 }
251
252 olsr_linkcost
253 default_lq_packet_loss_worker_ff(struct link_entry
254                                  __attribute__ ((unused)) * link, void
255                                  __attribute__ ((unused)) * ptr, bool __attribute__ ((unused)) lost)
256 {
257   return link->linkcost;
258 }
259
260 void
261 default_lq_memorize_foreign_hello_ff(void *ptrLocal, void *ptrForeign)
262 {
263   struct default_lq_ff *local = ptrLocal;
264   struct default_lq_ff *foreign = ptrForeign;
265
266   if (foreign) {
267     local->valueNlq = foreign->valueLq;
268   } else {
269     local->valueNlq = 0;
270   }
271 }
272
273 void
274 default_lq_copy_link2tc_ff(void *target, void *source)
275 {
276   memcpy(target, source, sizeof(struct default_lq_ff));
277 }
278
279 void
280 default_lq_clear_ff(void *target)
281 {
282   memset(target, 0, sizeof(struct default_lq_ff));
283 }
284
285 void
286 default_lq_clear_ff_hello(void *target)
287 {
288   struct default_lq_ff_hello *local = target;
289   int i;
290
291   default_lq_clear_ff(&local->lq);
292   local->windowSize = LQ_FF_QUICKSTART_INIT;
293   for (i = 0; i < LQ_FF_WINDOW; i++) {
294     local->lost[i] = 3;
295   }
296 }
297
298 const char *
299 default_lq_print_ff(void *ptr, char separator, struct lqtextbuffer *buffer)
300 {
301   struct default_lq_ff *lq = ptr;
302
303   snprintf(buffer->buf, sizeof(buffer->buf), "%s%c%s", fpmtoa(fpmidiv(itofpm((int)lq->valueLq), 255)), separator,
304            fpmtoa(fpmidiv(itofpm((int)lq->valueNlq), 255)));
305   return buffer->buf;
306 }
307
308 const char *
309 default_lq_print_cost_ff(olsr_linkcost cost, struct lqtextbuffer *buffer)
310 {
311   snprintf(buffer->buf, sizeof(buffer->buf), "%s", fpmtoa(cost));
312   return buffer->buf;
313 }
314
315 /*
316  * Local Variables:
317  * c-basic-offset: 2
318  * indent-tabs-mode: nil
319  * End:
320  */