82609a78e7dc096f6b2142da055650f852e0806c
[olsrd.git] / src / mid_set.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 "ipcalc.h"
43 #include "defs.h"
44 #include "mid_set.h"
45 #include "olsr.h"
46 #include "scheduler.h"
47 #include "neighbor_table.h"
48 #include "link_set.h"
49 #include "tc_set.h"
50 #include "net_olsr.h"
51 #include "olsr_cookie.h"
52 #include "olsr_logging.h"
53 #include "olsr_protocol.h"
54
55 #include <stdlib.h>
56
57 static struct mid_entry *olsr_lookup_mid_entry(const union olsr_ip_addr *);
58 static void olsr_prune_mid_entries(const union olsr_ip_addr *main_addr, uint16_t mid_seqno);
59
60 /* Root of the MID tree */
61 struct avl_tree mid_tree;
62
63 /* Some cookies for stats keeping */
64 static struct olsr_cookie_info *mid_validity_timer_cookie = NULL;
65 static struct olsr_cookie_info *mid_address_mem_cookie = NULL;
66
67 /**
68  * Initialize the MID set
69  */
70 void
71 olsr_init_mid_set(void)
72 {
73   OLSR_INFO(LOG_MID, "Initialize MID set...\n");
74
75   avl_init(&mid_tree, avl_comp_default);
76
77   /*
78    * Get some cookies for getting stats to ease troubleshooting.
79    */
80   mid_validity_timer_cookie = olsr_alloc_cookie("MID validity", OLSR_COOKIE_TYPE_TIMER);
81
82   mid_address_mem_cookie = olsr_alloc_cookie("MID address", OLSR_COOKIE_TYPE_MEMORY);
83   olsr_cookie_set_memory_size(mid_address_mem_cookie, sizeof(struct mid_entry));
84 }
85
86 /**
87  * Wrapper for the timer callback.
88  */
89 static void
90 olsr_expire_mid_entries(void *context)
91 {
92   struct tc_entry *tc = context;
93 #if !defined REMOVE_LOG_DEBUG
94   struct ipaddr_str buf;
95 #endif
96
97   OLSR_DEBUG(LOG_MID, "MID aliases for %s timed out\n", olsr_ip_to_string(&buf, &tc->addr));
98
99   olsr_flush_mid_entries(tc);
100 }
101
102 /**
103  * Set the mid set expiration timer.
104  *
105  * all timer setting shall be done using this function.
106  * The timer param is a relative timer expressed in milliseconds.
107  */
108 static void
109 olsr_set_mid_timer(struct tc_entry *tc, olsr_reltime rel_timer)
110 {
111   olsr_set_timer(&tc->mid_timer, rel_timer, OLSR_MID_JITTER,
112                  OLSR_TIMER_ONESHOT, &olsr_expire_mid_entries, tc, mid_validity_timer_cookie);
113 }
114
115 /**
116  * Delete possible duplicate entries in 2 hop set
117  * and delete duplicate neighbor entries. Redirect
118  * link entries to the correct neighbor entry.
119  * This optimization is not specified in rfc3626.
120  */
121 static void
122 olsr_flush_nbr2_duplicates(struct mid_entry *alias)
123 {
124   struct tc_entry *tc = alias->mid_tc;
125 #if !defined REMOVE_LOG_DEBUG
126   struct ipaddr_str buf1, buf2;
127 #endif
128
129   OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
130     struct nbr_entry *nbr;
131     struct nbr2_entry *nbr2 = olsr_lookup_nbr2_entry(&alias->mid_alias_addr, false);
132
133     /* Delete possible 2 hop neighbor */
134     if (nbr2) {
135       OLSR_DEBUG(LOG_MID, "Delete 2hop neighbor: %s to %s\n",
136                  olsr_ip_to_string(&buf1, &alias->mid_alias_addr), olsr_ip_to_string(&buf2, &tc->addr));
137
138       olsr_delete_nbr2_entry(nbr2);
139       changes_neighborhood = true;
140     }
141
142     /* Delete a possible neighbor entry */
143     nbr = olsr_lookup_nbr_entry(&alias->mid_alias_addr, false);
144     if (nbr) {
145       struct nbr_entry *real_nbr = olsr_lookup_nbr_entry(&tc->addr, false);
146       if (real_nbr) {
147
148         OLSR_DEBUG(LOG_MID, "Delete bogus neighbor entry %s (real %s)\n",
149                    olsr_ip_to_string(&buf1, &alias->mid_alias_addr), olsr_ip_to_string(&buf2, &tc->addr));
150
151         replace_neighbor_link_set(nbr, real_nbr);
152
153         olsr_delete_nbr_entry(nbr);
154
155         changes_neighborhood = true;
156       }
157     }
158   }
159   OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, mid_alias);
160 }
161
162 /**
163  * If we have an entry for this alias in neighbortable, we better adjust it's
164  * main address, because otherwise a fatal inconsistency between
165  * neighbortable and link_set will be created by way of this mid entry.
166  */
167 static void
168 olsr_fixup_mid_main_addr(const union olsr_ip_addr *main_addr, const union olsr_ip_addr *alias_addr)
169 {
170   struct nbr_entry *nbr_new, *nbr_old;
171   struct mid_entry *mid_old;
172   int ne_ref_rp_count;
173 #if !defined REMOVE_LOG_DEBUG
174   struct ipaddr_str buf1, buf2;
175 #endif
176
177   nbr_old = olsr_lookup_nbr_entry(alias_addr, false);
178   if (!nbr_old) {
179     return;
180   }
181
182   OLSR_DEBUG(LOG_MID, "Main address change %s -> %s detected.\n",
183              olsr_ip_to_string(&buf1, alias_addr), olsr_ip_to_string(&buf2, main_addr));
184
185   olsr_delete_nbr_entry(nbr_old);
186   nbr_new = olsr_add_nbr_entry(main_addr);
187
188   /* Adjust pointers to neighbortable-entry in link_set */
189   ne_ref_rp_count = replace_neighbor_link_set(nbr_old, nbr_new);
190
191   if (ne_ref_rp_count > 0) {
192     OLSR_DEBUG(LOG_MID, "Performed %d neighbortable-pointer replacements "
193                "(%p -> %p) in link_set.\n", ne_ref_rp_count, nbr_old, nbr_new);
194   }
195
196   mid_old = olsr_lookup_mid_entry(alias_addr);
197   if (mid_old) {
198     /*
199      * We knew aliases to the previous main address.
200      * Better forget about them now.
201      */
202     OLSR_DEBUG(LOG_MID, "Flush aliases for old main address.\n");
203     olsr_flush_mid_entries(mid_old->mid_tc);
204   }
205 }
206
207 /**
208  * Insert a fresh alias address for a node.
209  *
210  * @param main_add the main address of the node
211  * @param alias the alias address to insert
212  * @param vtime the validity time
213  * @param seq the sequence number to register a new node with
214  */
215 static struct mid_entry *
216 olsr_insert_mid_entry(const union olsr_ip_addr *main_addr,
217                       const union olsr_ip_addr *alias_addr, olsr_reltime vtime, uint16_t mid_seqno)
218 {
219   struct tc_entry *tc;
220   struct mid_entry *alias;
221 #if !defined REMOVE_LOG_DEBUG
222   struct ipaddr_str buf1, buf2;
223 #endif
224
225   OLSR_DEBUG(LOG_MID, "Inserting alias %s for %s\n", olsr_ip_to_string(&buf1, alias_addr), olsr_ip_to_string(&buf2, main_addr));
226
227   /*
228    * Locate first the hookup point
229    */
230   tc = olsr_locate_tc_entry(main_addr);
231
232   alias = olsr_cookie_malloc(mid_address_mem_cookie);
233   alias->mid_alias_addr = *alias_addr;
234   alias->mid_tc = tc;
235   olsr_lock_tc_entry(tc);
236
237   /*
238    * Insert into the per-tc mid subtree.
239    */
240   alias->mid_tc_node.key = &alias->mid_alias_addr;
241   avl_insert(&tc->mid_tree, &alias->mid_tc_node, AVL_DUP_NO);
242
243   /*
244    * Insert into the global mid tree.
245    */
246   alias->mid_node.key = &alias->mid_alias_addr;
247   avl_insert(&mid_tree, &alias->mid_node, AVL_DUP_NO);
248
249   /*
250    * Add a rt_path for the alias.
251    */
252   olsr_insert_routing_table(&alias->mid_alias_addr, 8 * olsr_cnf->ipsize, main_addr, OLSR_RT_ORIGIN_MID);
253
254   /*
255    * Start the timer. Because we provide the TC reference
256    * as callback data for the timer we need to lock
257    * the underlying TC entry again.
258    */
259   olsr_set_mid_timer(alias->mid_tc, vtime);
260   olsr_lock_tc_entry(tc);
261
262   /* Set sequence number for alias purging */
263   alias->mid_seqno = mid_seqno;
264
265   return alias;
266 }
267
268 /**
269  * Update an alias address for a node.
270  * If the main address is not registered
271  * then a new entry is created.
272  *
273  * @param main_add the main address of the node
274  * @param alias the alias address to insert
275  * @param vtime the validity time
276  * @param seq the sequence number to register a new node with
277  */
278 static void
279 olsr_update_mid_entry(const union olsr_ip_addr *main_addr,
280                       const union olsr_ip_addr *alias_addr, olsr_reltime vtime, uint16_t mid_seqno)
281 {
282   struct mid_entry *alias;
283
284   if (!olsr_validate_address(alias_addr)) {
285     return;
286   }
287
288   /*
289    * Check first if the alias already exists.
290    */
291   alias = olsr_lookup_mid_entry(alias_addr);
292   if (alias) {
293     /* Update sequence number for alias purging */
294     alias->mid_seqno = mid_seqno;
295
296     /* XXX handle main IP address changes */
297
298     /* Refresh the timer. */
299     olsr_set_mid_timer(alias->mid_tc, vtime);
300     return;
301   }
302
303   /*
304    * This is a fresh alias.
305    */
306   alias = olsr_insert_mid_entry(main_addr, alias_addr, vtime, mid_seqno);
307
308   /*
309    * Do the needful if one of our neighbors has changed its main address.
310    */
311   olsr_fixup_mid_main_addr(main_addr, alias_addr);
312   olsr_flush_nbr2_duplicates(alias);
313
314   /*
315    * Recalculate topology.
316    */
317   changes_neighborhood = true;
318   changes_topology = true;
319 }
320
321 /**
322  * Lookup a MID alias hanging off a tc_entry by address
323  *
324  * @param adr the alias address to check
325  * @return the MID address entry or NULL if not found
326  */
327 struct mid_entry *
328 olsr_lookup_tc_mid_entry(struct tc_entry *tc, const union olsr_ip_addr *adr)
329 {
330   return (alias_tree2mid(avl_find(&tc->mid_tree, adr)));
331 }
332
333 /**
334  * Lookup an MID alias by address in the global tree.
335  *
336  * @param adr the alias address to check
337  * @return the MID address entry or NULL if not found
338  */
339 static struct mid_entry *
340 olsr_lookup_mid_entry(const union olsr_ip_addr *adr)
341 {
342   return (global_tree2mid(avl_find(&mid_tree, adr)));
343 }
344
345 /**
346  * Lookup the main address for an MID alias address
347  *
348  * @param adr the alias address to check
349  * @return the main address registered on the alias
350  * or NULL if not found
351  */
352 union olsr_ip_addr *
353 olsr_lookup_main_addr_by_alias(const union olsr_ip_addr *adr)
354 {
355   struct mid_entry *alias;
356
357   alias = olsr_lookup_mid_entry(adr);
358
359   return (alias ? &alias->mid_tc->addr : NULL);
360 }
361
362 /**
363  * Delete a single MID alias.
364  *
365  * @param alias the alias to delete.
366  */
367 void
368 olsr_delete_mid_entry(struct mid_entry *alias)
369 {
370   struct tc_entry *tc;
371
372   tc = alias->mid_tc;
373
374   /*
375    * Delete the rt_path for the alias.
376    */
377   olsr_delete_routing_table(&alias->mid_alias_addr, 8 * olsr_cnf->ipsize, &tc->addr, OLSR_RT_ORIGIN_MID);
378
379   /*
380    * Remove from the per-tc tree.
381    */
382   avl_delete(&tc->mid_tree, &alias->mid_tc_node);
383
384   /*
385    * Remove from the global tree.
386    */
387   avl_delete(&mid_tree, &alias->mid_node);
388
389   olsr_unlock_tc_entry(tc);
390
391   olsr_cookie_free(mid_address_mem_cookie, alias);
392 }
393
394 /**
395  * Delete all the MID aliases hanging off a tc entry.
396  *
397  * @param entry the tc entry holding the aliases.
398  */
399 void
400 olsr_flush_mid_entries(struct tc_entry *tc)
401 {
402   struct mid_entry *alias;
403
404   OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
405     olsr_delete_mid_entry(alias);
406   } OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, alias);
407
408   /*
409    * Kill any pending timers.
410    */
411   olsr_set_mid_timer(tc, 0);
412   olsr_unlock_tc_entry(tc);
413 }
414
415 /**
416  * Remove aliases from 'entry' which are not matching
417  * the most recent message sequence number. This gets
418  * called after receiving a MID message for garbage
419  * collection of the old entries.
420  *
421  * @param main_addr the root of MID entries.
422  * @param mid_seqno the most recent message sequence number
423  */
424 static void
425 olsr_prune_mid_entries(const union olsr_ip_addr *main_addr, uint16_t mid_seqno)
426 {
427   struct tc_entry *tc = olsr_locate_tc_entry(main_addr);
428   struct mid_entry *alias;
429   OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
430     if (alias->mid_seqno != mid_seqno) {
431       olsr_delete_mid_entry(alias);
432     }
433   }
434   OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, alias);
435 }
436
437 /**
438  * Print all MID entries
439  * For debuging purposes
440  */
441 void
442 olsr_print_mid_set(void)
443 {
444 #if !defined REMOVE_LOG_INFO
445   struct tc_entry *tc;
446   struct mid_entry *alias;
447   struct ipaddr_str buf1, buf2;
448
449   OLSR_INFO(LOG_MID, "\n--- %s ------------------------------------------------- MID\n\n", olsr_wallclock_string());
450
451   OLSR_FOR_ALL_TC_ENTRIES(tc) {
452     bool first = true;
453     OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
454       OLSR_INFO_NH(LOG_MID, "%-15s: %s\n",
455                    first ? olsr_ip_to_string(&buf1, &tc->addr) : "", olsr_ip_to_string(&buf2, &alias->mid_alias_addr));
456       first = false;
457     } OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, alias);
458   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
459 #endif
460 }
461
462 /**
463  * Process an incoming MID message.
464  */
465 bool
466 olsr_input_mid(union olsr_message *msg, struct interface *input_if __attribute__ ((unused)), union olsr_ip_addr *from_addr)
467 {
468   uint16_t msg_size, msg_seq;
469   uint8_t type, ttl, msg_hops;
470   const unsigned char *curr;
471   olsr_reltime vtime;
472   union olsr_ip_addr originator, alias;
473   int alias_count;
474 #if !defined REMOVE_LOG_DEBUG
475   struct ipaddr_str buf;
476 #endif
477
478   curr = (void *)msg;
479   if (!msg) {
480     return false;
481   }
482
483   /* We are only interested in MID message types. */
484   pkt_get_u8(&curr, &type);
485   if (type != MID_MESSAGE) {
486     return false;
487   }
488
489   pkt_get_reltime(&curr, &vtime);
490   pkt_get_u16(&curr, &msg_size);
491
492   pkt_get_ipaddress(&curr, &originator);
493
494   /* Copy header values */
495   pkt_get_u8(&curr, &ttl);
496   pkt_get_u8(&curr, &msg_hops);
497   pkt_get_u16(&curr, &msg_seq);
498
499   if (!olsr_validate_address(&originator)) {
500     return false;
501   }
502
503   /*
504    * If the sender interface (NB: not originator) of this message
505    * is not in the symmetric 1-hop neighborhood of this node, the
506    * message MUST be discarded.
507    */
508   if (check_neighbor_link(from_addr) != SYM_LINK) {
509     OLSR_DEBUG(LOG_MID, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
510     return false;
511   }
512
513
514   /*
515    * How many aliases ?
516    */
517   alias_count = (msg_size - 12) / olsr_cnf->ipsize;
518
519   OLSR_DEBUG(LOG_MID, "Processing MID from %s with %d aliases, seq 0x%04x\n",
520              olsr_ip_to_string(&buf, &originator), alias_count, msg_seq);
521   /*
522    * Now walk the list of alias advertisements one by one.
523    */
524   while (alias_count) {
525     pkt_get_ipaddress(&curr, &alias);
526     olsr_update_mid_entry(&originator, &alias, vtime, msg_seq);
527     alias_count--;
528   }
529
530   /*
531    * Prune the aliases that did not get refreshed by this advertisment.
532    */
533   olsr_prune_mid_entries(&originator, msg_seq);
534
535   /* Forward the message */
536   return true;
537 }
538
539 /*
540  * Local Variables:
541  * c-basic-offset: 2
542  * indent-tabs-mode: nil
543  * End:
544  */