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