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