Convert lq_etx_float to new plugin system
[olsrd.git] / lib / lq_etx_fpm / src / lq_plugin_etx_fpm.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 "olsr_spf.h"
45 #include "lq_packet.h"
46 #include "olsr.h"
47 #include "lq_plugin_etx_fpm.h"
48
49 #define LQ_FPM_INTERNAL_MULTIPLIER 65535
50 #define LQ_FPM_LINKCOST_MULTIPLIER 65535
51
52 static void lq_etxfpm_initialize(void);
53 static void lq_etxfpm_deinitialize(void);
54
55 static olsr_linkcost lq_etxfpm_calc_link_entry_cost(struct link_entry *);
56 static olsr_linkcost lq_etxfpm_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *);
57 static olsr_linkcost lq_etxfpm_calc_tc_mpr_addr_cost(struct tc_mpr_addr *);
58 static olsr_linkcost lq_etxfpm_calc_tc_edge_entry_cost(struct tc_edge_entry *);
59
60 static bool lq_etxfpm_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2);
61
62 static olsr_linkcost lq_etxfpm_packet_loss_handler(struct link_entry *, bool);
63
64 static void lq_etxfpm_memorize_foreign_hello(struct link_entry *, struct lq_hello_neighbor *);
65 static void lq_etxfpm_copy_link_entry_lq_into_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source);
66 static void lq_etxfpm_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source);
67 static void lq_etxfpm_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target, struct link_entry *source);
68
69 static int lq_etxfpm_serialize_hello_lq(unsigned char *buff, struct lq_hello_neighbor *lq);
70 static int lq_etxfpm_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *lq);
71 static void lq_etxfpm_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *lq);
72 static void lq_etxfpm_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *lq);
73
74 static char *lq_etxfpm_print_link_entry_lq(struct link_entry *entry, char separator, struct lqtextbuffer *buffer);
75 static char *lq_etxfpm_print_tc_edge_entry_lq(struct tc_edge_entry *ptr, char separator, struct lqtextbuffer *buffer);
76 static char *lq_etxfpm_print_cost(olsr_linkcost cost, struct lqtextbuffer *buffer);
77
78 /* etx lq plugin (freifunk fpm version) settings */
79 struct lq_handler lq_etxfpm_handler = {
80   "etx (fpm)",
81
82   &lq_etxfpm_initialize,
83   &lq_etxfpm_deinitialize,
84
85   &lq_etxfpm_calc_link_entry_cost,
86   &lq_etxfpm_calc_lq_hello_neighbor_cost,
87   &lq_etxfpm_calc_tc_mpr_addr_cost,
88   &lq_etxfpm_calc_tc_edge_entry_cost,
89
90   &lq_etxfpm_is_relevant_costchange,
91
92   &lq_etxfpm_packet_loss_handler,
93
94   &lq_etxfpm_memorize_foreign_hello,
95   &lq_etxfpm_copy_link_entry_lq_into_tc_mpr_addr,
96   &lq_etxfpm_copy_link_entry_lq_into_tc_edge_entry,
97   &lq_etxfpm_copy_link_lq_into_neighbor,
98
99   NULL,
100   NULL,
101   NULL,
102   NULL,
103
104   &lq_etxfpm_serialize_hello_lq,
105   &lq_etxfpm_serialize_tc_lq,
106   &lq_etxfpm_deserialize_hello_lq,
107   &lq_etxfpm_deserialize_tc_lq,
108
109   &lq_etxfpm_print_link_entry_lq,
110   &lq_etxfpm_print_tc_edge_entry_lq,
111   &lq_etxfpm_print_cost,
112
113   sizeof(struct lq_etxfpm_tc_edge),
114   sizeof(struct lq_etxfpm_tc_mpr_addr),
115   sizeof(struct lq_etxfpm_lq_hello_neighbor),
116   sizeof(struct lq_etxfpm_link_entry),
117
118   LQ_HELLO_MESSAGE,
119   LQ_TC_MESSAGE
120 };
121
122 static uint32_t aging_factor_new, aging_factor_old;
123 static uint32_t aging_quickstart_new, aging_quickstart_old;
124
125 static void
126 lq_etxfpm_initialize(void)
127 {
128   aging_factor_new = (uint32_t) (lq_aging * LQ_FPM_INTERNAL_MULTIPLIER);
129   aging_factor_old = LQ_FPM_INTERNAL_MULTIPLIER - aging_factor_new;
130
131   aging_quickstart_new = (uint32_t) (LQ_QUICKSTART_AGING * LQ_FPM_INTERNAL_MULTIPLIER);
132   aging_quickstart_old = LQ_FPM_INTERNAL_MULTIPLIER - aging_quickstart_new;
133 }
134
135 static void
136 lq_etxfpm_deinitialize(void)
137 {
138 }
139
140 static olsr_linkcost
141 lq_etxfpm_calc_linkcost(struct lq_etxfpm_linkquality *lq)
142 {
143   olsr_linkcost cost;
144
145   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
146     return LINK_COST_BROKEN;
147   }
148
149   cost = LQ_FPM_LINKCOST_MULTIPLIER * 255 / (int)lq->valueLq * 255 / (int)lq->valueNlq;
150
151   if (cost > LINK_COST_BROKEN)
152     return LINK_COST_BROKEN;
153   if (cost == 0)
154     return 1;
155   return cost;
156 }
157
158 static olsr_linkcost
159 lq_etxfpm_calc_link_entry_cost(struct link_entry *link)
160 {
161   struct lq_etxfpm_link_entry *lq_link = (struct lq_etxfpm_link_entry *)link;
162
163   return lq_etxfpm_calc_linkcost(&lq_link->lq);
164 }
165
166 static olsr_linkcost
167 lq_etxfpm_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *neigh)
168 {
169   struct lq_etxfpm_lq_hello_neighbor *lq_neigh = (struct lq_etxfpm_lq_hello_neighbor *)neigh;
170
171   return lq_etxfpm_calc_linkcost(&lq_neigh->lq);
172 }
173
174 static olsr_linkcost
175 lq_etxfpm_calc_tc_mpr_addr_cost(struct tc_mpr_addr *mpr)
176 {
177   struct lq_etxfpm_tc_mpr_addr *lq_mpr = (struct lq_etxfpm_tc_mpr_addr *)mpr;
178
179   return lq_etxfpm_calc_linkcost(&lq_mpr->lq);
180 }
181
182 static olsr_linkcost
183 lq_etxfpm_calc_tc_edge_entry_cost(struct tc_edge_entry *edge)
184 {
185   struct lq_etxfpm_tc_edge *lq_edge = (struct lq_etxfpm_tc_edge *)edge;
186
187   return lq_etxfpm_calc_linkcost(&lq_edge->lq);
188 }
189
190 static bool
191 lq_etxfpm_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2)
192 {
193   if (c1 > c2) {
194     return c2 - c1 > LQ_PLUGIN_RELEVANT_COSTCHANGE;
195   }
196   return c1 - c2 > LQ_PLUGIN_RELEVANT_COSTCHANGE;
197 }
198
199 static olsr_linkcost
200 lq_etxfpm_packet_loss_handler(struct link_entry *link, bool loss)
201 {
202   struct lq_etxfpm_link_entry *lq_link = (struct lq_etxfpm_link_entry *)link;
203
204   uint32_t alpha_old = aging_factor_old;
205   uint32_t alpha_new = aging_factor_new;
206
207   uint32_t value;
208   // fpm link_loss_factor = fpmidiv(itofpm(link->loss_link_multiplier), 65536);
209
210   if (lq_link->quickstart < LQ_QUICKSTART_STEPS) {
211     alpha_new = aging_quickstart_new;
212     alpha_old = aging_quickstart_old;
213     lq_link->quickstart++;
214   }
215   // exponential moving average
216   value = (uint32_t) (lq_link->lq.valueLq) * LQ_FPM_INTERNAL_MULTIPLIER / 255;
217
218   value = (value * alpha_old + LQ_FPM_INTERNAL_MULTIPLIER - 1) / LQ_FPM_INTERNAL_MULTIPLIER;
219
220   if (!loss) {
221     uint32_t ratio;
222
223     ratio = (alpha_new * link->loss_link_multiplier + LINK_LOSS_MULTIPLIER - 1) / LINK_LOSS_MULTIPLIER;
224     value += ratio;
225   }
226   lq_link->lq.valueLq = (value * 255 + LQ_FPM_INTERNAL_MULTIPLIER - 1) / LQ_FPM_INTERNAL_MULTIPLIER;
227
228   return lq_etxfpm_calc_linkcost(&lq_link->lq);
229 }
230
231 static void
232 lq_etxfpm_memorize_foreign_hello(struct link_entry *target, struct lq_hello_neighbor *source)
233 {
234   struct lq_etxfpm_link_entry *lq_target = (struct lq_etxfpm_link_entry *)target;
235   struct lq_etxfpm_lq_hello_neighbor *lq_source = (struct lq_etxfpm_lq_hello_neighbor *)source;
236
237   if (source) {
238     lq_target->lq.valueNlq = lq_source->lq.valueLq;
239   } else {
240     lq_target->lq.valueNlq = 0;
241   }
242
243 }
244
245 static void
246 lq_etxfpm_copy_link_entry_lq_into_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source)
247 {
248   struct lq_etxfpm_tc_mpr_addr *lq_target = (struct lq_etxfpm_tc_mpr_addr *)target;
249   struct lq_etxfpm_link_entry *lq_source = (struct lq_etxfpm_link_entry *)source;
250
251   lq_target->lq = lq_source->lq;
252 }
253
254 static void
255 lq_etxfpm_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source)
256 {
257   struct lq_etxfpm_tc_edge *lq_target = (struct lq_etxfpm_tc_edge *)target;
258   struct lq_etxfpm_link_entry *lq_source = (struct lq_etxfpm_link_entry *)source;
259
260   lq_target->lq = lq_source->lq;
261 }
262
263 static void
264 lq_etxfpm_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target, struct link_entry *source)
265 {
266   struct lq_etxfpm_lq_hello_neighbor *lq_target = (struct lq_etxfpm_lq_hello_neighbor *)target;
267   struct lq_etxfpm_link_entry *lq_source = (struct lq_etxfpm_link_entry *)source;
268
269   lq_target->lq = lq_source->lq;
270 }
271
272 static int
273 lq_etxfpm_serialize_hello_lq(unsigned char *buff, struct lq_hello_neighbor *neigh)
274 {
275   struct lq_etxfpm_lq_hello_neighbor *lq_neigh = (struct lq_etxfpm_lq_hello_neighbor *)neigh;
276
277   buff[0] = (unsigned char)lq_neigh->lq.valueLq;
278   buff[1] = (unsigned char)lq_neigh->lq.valueNlq;
279   buff[2] = (unsigned char)(0);
280   buff[3] = (unsigned char)(0);
281
282   return 4;
283 }
284 static int
285 lq_etxfpm_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *mpr)
286 {
287   struct lq_etxfpm_tc_mpr_addr *lq_mpr = (struct lq_etxfpm_tc_mpr_addr *)mpr;
288
289   buff[0] = (unsigned char)lq_mpr->lq.valueLq;
290   buff[1] = (unsigned char)lq_mpr->lq.valueNlq;
291   buff[2] = (unsigned char)(0);
292   buff[3] = (unsigned char)(0);
293
294   return 4;
295 }
296
297 static void
298 lq_etxfpm_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *neigh)
299 {
300   struct lq_etxfpm_lq_hello_neighbor *lq_neigh = (struct lq_etxfpm_lq_hello_neighbor *)neigh;
301
302   pkt_get_u8(curr, &lq_neigh->lq.valueLq);
303   pkt_get_u8(curr, &lq_neigh->lq.valueNlq);
304   pkt_ignore_u16(curr);
305
306 }
307 static void
308 lq_etxfpm_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *edge)
309 {
310   struct lq_etxfpm_tc_edge *lq_edge = (struct lq_etxfpm_tc_edge *)edge;
311
312   pkt_get_u8(curr, &lq_edge->lq.valueLq);
313   pkt_get_u8(curr, &lq_edge->lq.valueNlq);
314   pkt_ignore_u16(curr);
315 }
316
317 static char *
318 lq_etxfpm_print_lq(struct lq_etxfpm_linkquality *lq, char separator, struct lqtextbuffer *buffer)
319 {
320   int i = 0;
321
322   if (lq->valueLq == 255) {
323     strcpy(buffer->buf, "1.000");
324     i += 5;
325   } else {
326     i = sprintf(buffer->buf, "0.%03d", (lq->valueLq * 1000) / 255);
327   }
328   buffer->buf[i++] = separator;
329
330   if (lq->valueNlq == 255) {
331     strcpy(&buffer->buf[i], "1.000");
332   } else {
333     sprintf(&buffer->buf[i], "0.%03d", (lq->valueNlq * 1000) / 255);
334   }
335   return buffer->buf;
336 }
337
338 static char *
339 lq_etxfpm_print_link_entry_lq(struct link_entry *link, char separator, struct lqtextbuffer *buffer)
340 {
341   struct lq_etxfpm_link_entry *lq_link = (struct lq_etxfpm_link_entry *)link;
342
343   return lq_etxfpm_print_lq(&lq_link->lq, separator, buffer);
344 }
345
346 static char *
347 lq_etxfpm_print_tc_edge_entry_lq(struct tc_edge_entry *edge, char separator, struct lqtextbuffer *buffer)
348 {
349   struct lq_etxfpm_tc_edge *lq_edge = (struct lq_etxfpm_tc_edge *)edge;
350
351   return lq_etxfpm_print_lq(&lq_edge->lq, separator, buffer);
352 }
353
354 static char *
355 lq_etxfpm_print_cost(olsr_linkcost cost, struct lqtextbuffer *buffer)
356 {
357   // must calculate
358   uint32_t roundDown = cost >> 16;
359   uint32_t fraction = ((cost & 0xffff) * 1000) >> 16;
360
361   sprintf(buffer->buf, "%u.%03u", roundDown, fraction);
362   return buffer->buf;
363 }
364
365 /*
366  * Local Variables:
367  * c-basic-offset: 2
368  * indent-tabs-mode: nil
369  * End:
370  */