plugin: dot_draw: readme: make it clear, that it only opens an IPv4-socket, so a...
[olsrd.git] / src / gateway_default_handler.c
1 /*
2  * gateway_default_handler.c
3  *
4  *  Created on: Jan 29, 2010
5  *      Author: rogge
6  */
7 #ifdef __linux__
8
9 #include "gateway_default_handler.h"
10
11 #include "defs.h"
12 #include "gateway.h"
13 #include "lq_plugin.h"
14
15 static uint32_t gw_def_nodecount;
16 static uint32_t gw_def_stablecount;
17 static bool gw_def_choose_new_ipv4_gw;
18 static bool gw_def_choose_new_ipv6_gw;
19 static struct timer_entry *gw_def_timer;
20
21 /* forward declarations */
22 static void gw_default_init(void);
23 static void gw_default_cleanup(void);
24 static void gw_default_startup_handler(void);
25 static uint64_t gw_default_getcosts(struct gateway_entry *gw);
26 static void gw_default_choosegw_handler(bool ipv4, bool ipv6);
27 static void gw_default_update_handler(struct gateway_entry *);
28 static void gw_default_delete_handler(struct gateway_entry *);
29
30 /**
31  * Callback list for the gateway (default) handler
32  */
33 struct olsr_gw_handler gw_def_handler = {
34     &gw_default_init,
35     &gw_default_cleanup,
36     &gw_default_startup_handler,
37     &gw_default_getcosts,
38     &gw_default_choosegw_handler,
39     &gw_default_update_handler,
40     &gw_default_delete_handler
41 };
42
43 /*
44  * Helper functions
45  */
46
47 /**
48  * Calculate the threshold path cost.
49  *
50  * @param path_cost the path cost
51  * @return the threshold path cost
52  */
53 static inline uint64_t gw_default_calc_threshold(uint64_t path_cost) {
54   if (olsr_cnf->smart_gw_thresh == 0) {
55     return path_cost;
56   }
57
58   return ((path_cost * (uint64_t) olsr_cnf->smart_gw_thresh) + (uint64_t) 50) / (uint64_t) 100;
59 }
60
61 /**
62  * Weigh the path costs and the gateway bandwidth.
63  *
64  * If the ETX divider is zero, then no weighing is performed and only the path
65  * costs are considered (classic behaviour).
66  *
67  * If either of the uplink or downlink bandwidths is zero, then UINT64_MAX is
68  * returned.
69  *
70  * @param path_cost the (ETX) path cost to the gateway
71  * @param exitUk the gateway exit link uplink bandwidth (in kbps)
72  * @param exitDk the gateway exit link downlink bandwidth (in kbps)
73  * @return the weighed path cost
74  */
75 static inline uint64_t gw_default_weigh_costs(uint64_t path_cost, uint32_t exitUk, uint32_t exitDk) {
76   uint8_t WexitU = olsr_cnf->smart_gw_weight_exitlink_up;
77   uint8_t WexitD = olsr_cnf->smart_gw_weight_exitlink_down;
78   uint8_t Wetx = olsr_cnf->smart_gw_weight_etx;
79   uint8_t Detx = olsr_cnf->smart_gw_divider_etx;
80   uint64_t costU;
81   uint64_t costD;
82   uint64_t costE;
83
84   if (!Detx) {
85     /* only consider path costs (classic behaviour) */
86     return path_cost;
87   }
88
89   if (!exitUk || !exitDk) {
90     /* zero bandwidth */
91     return UINT64_MAX;
92   }
93
94   /*
95    * Weighing of the path costs:
96    *
97    * exitUm = the gateway exit link uplink   bandwidth, in Mbps
98    * exitDm = the gateway exit link downlink bandwidth, in Mbps
99    * WexitU = the gateway exit link uplink   bandwidth weight   (configured)
100    * WexitD = the gateway exit link downlink bandwidth weight   (configured)
101    * Wetx   = the ETX path cost weight                          (configured)
102    * Detx   = the ETX path cost divider                         (configured)
103    *
104    *                     WexitU   WexitD   Wetx
105    * path_cost_weight =  ------ + ------ + ---- * path_cost
106    *                     exitUm   exitDm   Detx
107    *
108    * Since the gateway exit link bandwidths are in Kbps, the following formula
109    * is used to convert them to the desired Mbps:
110    *
111    *       bwK
112    * bwM = ----       bwK = bandwidth in Kbps
113    *       1000       bwM = bandwidth in Mbps
114    *
115    * exitUk = the gateway exit link uplink   bandwidth, in Kbps
116    * exitDk = the gateway exit link downlink bandwidth, in Kbps
117    *
118    *                     1000 * WexitU   1000 * WexitD   Wetx
119    * path_cost_weight =  ------------- + ------------- + ---- * path_cost
120    *                         exitUk          exitDk      Detx
121    *
122    *
123    * Analysis of the required bit width of the result:
124    *
125    * exitUk    = [1,   320,000,000] = 29 bits
126    * exitDk    = [1,   320,000,000] = 29 bits
127    * WexitU    = [1,           255] =  8 bits
128    * WexitD    = [1,           255] =  8 bits
129    * Wetx      = [1,           255] =  8 bits
130    * Detx      = [1,           255] =  8 bits
131    * path_cost = [1, 4,294,967,295] = 32 bits
132    *
133    *                         1000 * 255   1000 * 255   255
134    * path_cost_weight(max) = ---------- + ---------- + --- * 4,294,967,295
135    *                              1             1       1
136    *
137    * path_cost_weight(max) = 0x3E418    + 0x3E418    + 0xFEFFFFFF01
138    * path_cost_weight(max) = 0xFF0007C731
139    *
140    * Because we can multiply 0xFF0007C731 by 2^24 without overflowing a
141    * 64 bits number, we do this to increase accuracy.
142    */
143
144   costU = (((uint64_t) (1000 * WexitU)) << 24) / exitUk;
145   costD = (((uint64_t) (1000 * WexitD)) << 24) / exitDk;
146   costE = (((uint64_t) (Wetx * path_cost)) << 24) / Detx;
147
148   return (costU + costD + costE);
149 }
150
151 /**
152  * Look through the gateway list and select the best gateway
153  * depending on the distance to this router
154  */
155 static void gw_default_choose_gateway(void) {
156   uint64_t cost_ipv4_threshold = UINT64_MAX;
157   uint64_t cost_ipv6_threshold = UINT64_MAX;
158   bool cost_ipv4_threshold_valid = false;
159   bool cost_ipv6_threshold_valid = false;
160   struct gateway_entry *chosen_gw_ipv4 = NULL;
161   struct gateway_entry *chosen_gw_ipv6 = NULL;
162   uint64_t chosen_gw_ipv4_costs = UINT64_MAX;
163   uint64_t chosen_gw_ipv6_costs = UINT64_MAX;
164   struct gateway_entry *gw;
165   bool dual = false;
166
167   if (olsr_cnf->smart_gw_thresh) {
168     /* determine the path cost thresholds */
169
170     uint64_t cost = gw_default_getcosts(olsr_get_inet_gateway(false));
171     if (cost != UINT64_MAX) {
172       cost_ipv4_threshold = gw_default_calc_threshold(cost);
173       cost_ipv4_threshold_valid = true;
174     }
175
176     cost = gw_default_getcosts(olsr_get_inet_gateway(true));
177     if (cost != UINT64_MAX) {
178       cost_ipv6_threshold = gw_default_calc_threshold(cost);
179       cost_ipv6_threshold_valid = true;
180     }
181   }
182
183   OLSR_FOR_ALL_GATEWAY_ENTRIES(gw) {
184     uint64_t gw_cost = gw_default_getcosts(gw);
185
186     if (gw_cost == UINT64_MAX) {
187       /* never select a node with infinite costs */
188       continue;
189     }
190
191     if (gw_def_choose_new_ipv4_gw) {
192       bool gw_eligible_v4 = gw->ipv4
193           /* && (olsr_cnf->ip_version == AF_INET || olsr_cnf->use_niit) *//* contained in gw_def_choose_new_ipv4_gw */
194           && (olsr_cnf->smart_gw_allow_nat || !gw->ipv4nat);
195       if (gw_eligible_v4 && gw_cost < chosen_gw_ipv4_costs
196           && (!cost_ipv4_threshold_valid || (gw_cost < cost_ipv4_threshold))) {
197         chosen_gw_ipv4 = gw;
198         chosen_gw_ipv4_costs = gw_cost;
199       }
200     }
201
202     if (gw_def_choose_new_ipv6_gw) {
203       bool gw_eligible_v6 = gw->ipv6
204           /* && olsr_cnf->ip_version == AF_INET6 *//* contained in gw_def_choose_new_ipv6_gw */;
205       if (gw_eligible_v6 && gw_cost < chosen_gw_ipv6_costs
206           && (!cost_ipv6_threshold_valid || (gw_cost < cost_ipv6_threshold))) {
207         chosen_gw_ipv6 = gw;
208         chosen_gw_ipv6_costs = gw_cost;
209       }
210     }
211   } OLSR_FOR_ALL_GATEWAY_ENTRIES_END(gw)
212
213   /* determine if we should keep looking for IPv4 and/or IPv6 gateways */
214   gw_def_choose_new_ipv4_gw = gw_def_choose_new_ipv4_gw && (chosen_gw_ipv4 == NULL);
215   gw_def_choose_new_ipv6_gw = gw_def_choose_new_ipv6_gw && (chosen_gw_ipv6 == NULL);
216
217   /* determine if we are dealing with a dual stack gateway */
218   dual = chosen_gw_ipv4 && (chosen_gw_ipv4 == chosen_gw_ipv6);
219
220   if (chosen_gw_ipv4) {
221     /* we are dealing with an IPv4 or dual stack gateway */
222     olsr_set_inet_gateway(&chosen_gw_ipv4->originator, chosen_gw_ipv4_costs, true, dual);
223   }
224   if (chosen_gw_ipv6 && !dual) {
225     /* we are dealing with an IPv6-only gateway */
226     olsr_set_inet_gateway(&chosen_gw_ipv6->originator, chosen_gw_ipv6_costs, false, true);
227   }
228
229   if ((olsr_cnf->smart_gw_thresh == 0) && !gw_def_choose_new_ipv4_gw && !gw_def_choose_new_ipv6_gw) {
230     /* stop looking for a better gateway */
231     olsr_stop_timer(gw_def_timer);
232     gw_def_timer = NULL;
233   }
234 }
235
236 /**
237  * Timer callback for lazy gateway selection
238  *
239  * @param unused unused
240  */
241 static void gw_default_timer(void *unused __attribute__ ((unused))) {
242   /* accept a 10% increase/decrease in the number of gateway nodes without triggering a stablecount reset */
243   unsigned int tree100percent = tc_tree.count * 10;
244   uint32_t nodecount090percent = gw_def_nodecount * 9;
245   uint32_t nodecount110percent = gw_def_nodecount * 11;
246   if ((tree100percent >= nodecount090percent) && (tree100percent <= nodecount110percent)) {
247     gw_def_nodecount = tc_tree.count;
248   }
249
250   if (tc_tree.count == gw_def_nodecount) {
251     /* the number of gateway nodes is 'stable' */
252     gw_def_stablecount++;
253   } else {
254     /* there was a significant change in the number of gateway nodes */
255     gw_def_nodecount = tc_tree.count;
256     gw_def_stablecount = 0;
257   }
258
259   if (gw_def_stablecount >= olsr_cnf->smart_gw_stablecount) {
260     /* the number of gateway nodes is stable enough, so we should select a new gateway now */
261     gw_default_choose_gateway();
262   }
263 }
264
265 /**
266  * Lookup a new gateway
267  *
268  * @param ipv4 lookup new v4 gateway
269  * @param ipv6 lookup new v6 gateway
270  */
271 static void gw_default_lookup_gateway(bool ipv4, bool ipv6) {
272   if (ipv4) {
273     /* get a new IPv4 gateway if we use OLSRv4 or NIIT */
274     gw_def_choose_new_ipv4_gw = (olsr_cnf->ip_version == AF_INET) || olsr_cnf->use_niit;
275   }
276   if (ipv6) {
277     /* get a new IPv6 gateway if we use OLSRv6 */
278     gw_def_choose_new_ipv6_gw = olsr_cnf->ip_version == AF_INET6;
279   }
280
281   if (gw_def_choose_new_ipv4_gw || gw_def_choose_new_ipv6_gw) {
282     gw_default_choose_gateway();
283   }
284 }
285
286 /*
287  * Exported functions
288  */
289
290 /*
291  * Handler functions
292  */
293
294 /**
295  * initialization of default gateway handler
296  */
297 static void gw_default_init(void) {
298   /* initialize values */
299   gw_def_nodecount = 0;
300   gw_def_stablecount = 0;
301   gw_def_choose_new_ipv4_gw = true;
302   gw_def_choose_new_ipv6_gw = true;
303   gw_def_timer = NULL;
304 }
305
306 /**
307  * Cleanup default gateway handler
308  */
309 static void gw_default_cleanup(void) {
310 }
311
312 /**
313  * Handle gateway startup
314  */
315 static void gw_default_startup_handler(void) {
316   /* reset node count */
317   gw_def_nodecount = tc_tree.count;
318   gw_def_stablecount = 0;
319
320   /* get a new IPv4 gateway if we use OLSRv4 or NIIT */
321   gw_def_choose_new_ipv4_gw = (olsr_cnf->ip_version == AF_INET) || olsr_cnf->use_niit;
322
323   /* get a new IPv6 gateway if we use OLSRv6 */
324   gw_def_choose_new_ipv6_gw = olsr_cnf->ip_version == AF_INET6;
325
326   /* keep in mind we might be a gateway ourself */
327   gw_def_choose_new_ipv4_gw = gw_def_choose_new_ipv4_gw && !olsr_cnf->has_ipv4_gateway;
328   gw_def_choose_new_ipv6_gw = gw_def_choose_new_ipv6_gw && !olsr_cnf->has_ipv6_gateway;
329
330   /* (re)start gateway lazy selection timer */
331   olsr_set_timer(&gw_def_timer, olsr_cnf->smart_gw_period, 0, true, &gw_default_timer, NULL, 0);
332 }
333
334 /**
335  * Called when the costs of a gateway must be determined.
336  *
337  * @param gw the gateway
338  * @return the costs, or UINT64_MAX in case the gateway is null or has inifinite costs
339  */
340 static uint64_t gw_default_getcosts(struct gateway_entry *gw) {
341   struct tc_entry* tc;
342
343   if (!gw) {
344     return UINT64_MAX;
345   }
346
347   tc = olsr_lookup_tc_entry(&gw->originator);
348
349   if (!tc || (tc->path_cost == ROUTE_COST_BROKEN) || (!gw->uplink || !gw->downlink)) {
350     /* gateways should not exist without tc entry */
351     /* do not consider nodes with an infinite ETX */
352     /* do not consider nodes without bandwidth or with a uni-directional link */
353     return UINT64_MAX;
354   }
355
356   /* determine the path cost */
357   return gw_default_weigh_costs(tc->path_cost, gw->uplink, gw->downlink);
358 }
359
360 /**
361  * Choose a new gateway
362  *
363  * @param ipv4 lookup new v4 gateway
364  * @param ipv6 lookup new v6 gateway
365  */
366 static void gw_default_choosegw_handler(bool ipv4, bool ipv6) {
367   gw_default_lookup_gateway(ipv4, ipv6);
368
369   if (gw_def_choose_new_ipv4_gw || gw_def_choose_new_ipv6_gw) {
370     gw_default_startup_handler();
371   }
372 }
373
374 /**
375  * Update a gateway entry
376  *
377  * @param gw the gateway entry
378  */
379 static void gw_default_update_handler(struct gateway_entry *gw) {
380   if (olsr_cnf->smart_gw_thresh == 0) {
381     /* classical behaviour: stick with the chosen gateway unless it changes */
382     bool v4changed = gw && (gw == olsr_get_inet_gateway(false))
383         && (!gw->ipv4 || (gw->ipv4nat && !olsr_cnf->smart_gw_allow_nat));
384     bool v6changed = gw && (gw == olsr_get_inet_gateway(true)) && !gw->ipv6;
385
386     if (v4changed || v6changed) {
387       gw_default_lookup_gateway(v4changed, v6changed);
388     }
389   } else {
390     /* new behaviour: always pick a new gateway */
391     gw_default_lookup_gateway(true, true);
392   }
393 }
394
395 /**
396  * Remove a gateway entry
397  *
398  * @param gw the gateway entry
399  */
400 static void gw_default_delete_handler(struct gateway_entry *gw) {
401   bool isv4 = gw && (gw == olsr_get_inet_gateway(false));
402   bool isv6 = gw && (gw == olsr_get_inet_gateway(true));
403
404   if (isv4 || isv6) {
405     gw_default_lookup_gateway(isv4, isv6);
406   }
407 }
408 #endif /* __linux__ */