3 != 2
[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 #include <assert.h>
42
43 #include "ipcalc.h"
44 #include "defs.h"
45 #include "two_hop_neighbor_table.h"
46 #include "mid_set.h"
47 #include "olsr.h"
48 #include "rebuild_packet.h"
49 #include "scheduler.h"
50 #include "neighbor_table.h"
51 #include "link_set.h"
52 #include "tc_set.h"
53 #include "packet.h"             /* struct mid_alias */
54 #include "net_olsr.h"
55 #include "duplicate_handler.h"
56
57 struct mid_entry mid_set[HASHSIZE];
58 struct mid_address reverse_mid_set[HASHSIZE];
59
60 struct mid_entry *mid_lookup_entry_bymain(const union olsr_ip_addr *adr);
61
62 /**
63  * Initialize the MID set
64  *
65  */
66 int
67 olsr_init_mid_set(void)
68 {
69   int idx;
70
71   OLSR_PRINTF(5, "MID: init\n");
72
73   for (idx = 0; idx < HASHSIZE; idx++) {
74     mid_set[idx].next = &mid_set[idx];
75     mid_set[idx].prev = &mid_set[idx];
76
77     reverse_mid_set[idx].next = &reverse_mid_set[idx];
78     reverse_mid_set[idx].prev = &reverse_mid_set[idx];
79   }
80
81   return 1;
82 }
83
84 void olsr_delete_all_mid_entries(void) {
85   int hash;
86
87   for (hash = 0; hash < HASHSIZE; hash++) {
88     while (mid_set[hash].next != &mid_set[hash]) {
89       olsr_delete_mid_entry(mid_set[hash].next);
90     }
91   }
92 }
93
94 void olsr_cleanup_mid(union olsr_ip_addr *orig) {
95   struct mid_entry *mid;
96   mid = mid_lookup_entry_bymain(orig);
97   if (mid) {
98     olsr_delete_mid_entry(mid);
99   }
100 }
101
102 /**
103  * Wrapper for the timer callback.
104  */
105 static void
106 olsr_expire_mid_entry(void *context)
107 {
108 #ifdef DEBUG
109   struct ipaddr_str buf;
110 #endif
111   struct mid_entry *mid;
112
113   mid = (struct mid_entry *)context;
114   mid->mid_timer = NULL;
115
116 #ifdef DEBUG
117   OLSR_PRINTF(1, "MID info for %s timed out.. deleting it\n", olsr_ip_to_string(&buf, &mid->main_addr));
118 #endif
119
120   olsr_delete_mid_entry(mid);
121 }
122
123 /**
124  * Set the mid set expiration timer.
125  *
126  * all timer setting shall be done using this function.
127  * The timer param is a relative timer expressed in milliseconds.
128  */
129 static void
130 olsr_set_mid_timer(struct mid_entry *mid, olsr_reltime rel_timer)
131 {
132   int32_t willFireIn = -1;
133   if (mid->mid_timer != NULL) willFireIn = olsr_getTimeDue(mid->mid_timer->timer_clock);
134   
135   if (willFireIn < 0 || (olsr_reltime)willFireIn < rel_timer) {
136     olsr_set_timer(&mid->mid_timer, rel_timer, 0, OLSR_TIMER_ONESHOT, &olsr_expire_mid_entry, mid, 0);
137   }
138 }
139
140 /**
141  * Insert a new interface alias to the interface association set.
142  * If the main interface of the association is not yet registered
143  * in the set a new entry is created.
144  *
145  * @param m_addr the main address of the node
146  * @param alias the alias address to insert
147  * @return false if mid_address is unnecessary, true otherwise
148  */
149
150 static bool
151 insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, olsr_reltime vtime)
152 {
153   struct mid_entry *tmp;
154   struct mid_address *tmp_adr;
155   uint32_t hash, alias_hash;
156   union olsr_ip_addr *registered_m_addr;
157
158   hash = olsr_ip_hashing(m_addr);
159   alias_hash = olsr_ip_hashing(&alias->alias);
160
161   /* Check for registered entry */
162   for (tmp = mid_set[hash].next; tmp != &mid_set[hash]; tmp = tmp->next) {
163     if (ipequal(&tmp->main_addr, m_addr))
164       break;
165   }
166
167   /* Check if alias is already registered with m_addr */
168   registered_m_addr = mid_lookup_main_addr(&alias->alias);
169   if (registered_m_addr != NULL && ipequal(registered_m_addr, m_addr)) {
170     /* Alias is already registered with main address. Nothing to do here. */
171     return false;
172   }
173
174   /*
175    * Add a rt_path for the alias.
176    */
177   olsr_insert_routing_table(&alias->alias, olsr_cnf->maxplen, m_addr, OLSR_RT_ORIGIN_MID);
178
179   /*If the address was registered */
180   if (tmp != &mid_set[hash]) {
181     tmp_adr = tmp->aliases;
182     tmp->aliases = alias;
183     alias->main_entry = tmp;
184     QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
185     alias->next_alias = tmp_adr;
186     olsr_set_mid_timer(tmp, vtime);
187   } else {
188
189     /*Create new node */
190     tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
191
192     tmp->aliases = alias;
193     alias->main_entry = tmp;
194     QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
195     tmp->main_addr = *m_addr;
196     olsr_set_mid_timer(tmp, vtime);
197
198     /* Queue */
199     QUEUE_ELEM(mid_set[hash], tmp);
200   }
201
202   /*
203    * Delete possible duplicate entries in 2 hop set
204    * and delete duplicate neighbor entries. Redirect
205    * link entries to the correct neighbor entry.
206    *
207    *THIS OPTIMIZATION IS NOT SPECIFIED IN RFC3626
208    */
209
210   tmp_adr = alias;
211
212   while (tmp_adr) {
213     struct neighbor_2_entry *tmp_2_neighbor;
214     struct neighbor_entry *tmp_neigh, *real_neigh;
215
216     /* Delete possible 2 hop neighbor */
217     if ((tmp_2_neighbor = olsr_lookup_two_hop_neighbor_table_mid(&tmp_adr->alias)) != NULL) {
218       struct ipaddr_str buf;
219       OLSR_PRINTF(1, "Deleting 2 hop node from MID: %s to ", olsr_ip_to_string(&buf, &tmp_adr->alias));
220       OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, m_addr));
221
222       olsr_delete_two_hop_neighbor_table(tmp_2_neighbor);
223
224       changes_neighborhood = true;
225     }
226
227     /* Delete a possible neighbor entry */
228     if (((tmp_neigh = olsr_lookup_neighbor_table_alias(&tmp_adr->alias)) != NULL)
229         && ((real_neigh = olsr_lookup_neighbor_table_alias(m_addr)) != NULL)) {
230       struct ipaddr_str buf;
231       OLSR_PRINTF(1, "[MID]Deleting bogus neighbor entry %s real ", olsr_ip_to_string(&buf, &tmp_adr->alias));
232       OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, m_addr));
233
234       replace_neighbor_link_set(tmp_neigh, real_neigh);
235
236       /* Dequeue */
237       DEQUEUE_ELEM(tmp_neigh);
238       /* Delete */
239       free(tmp_neigh);
240
241       changes_neighborhood = true;
242     }
243     tmp_adr = tmp_adr->next_alias;
244   }
245   return true;
246 }
247
248 /**
249  * Insert an alias address for a node.
250  * If the main address is not registered
251  * then a new entry is created.
252  *
253  * @param main_add the main address of the node
254  * @param alias the alias address to insert
255  * @param seq the sequence number to register a new node with
256  * @return nada
257  */
258 void
259 insert_mid_alias(union olsr_ip_addr *main_add, const union olsr_ip_addr *alias, olsr_reltime vtime)
260 {
261   struct neighbor_entry *ne_old, *ne_new;
262   struct mid_entry *me_old;
263   int ne_ref_rp_count;
264   struct ipaddr_str buf1, buf2;
265   struct mid_address *adr;
266   if (!olsr_validate_address(alias))
267     return;
268
269   OLSR_PRINTF(1, "Inserting alias %s for ", olsr_ip_to_string(&buf1, alias));
270   OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf1, main_add));
271
272   adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
273
274   adr->alias = *alias;
275   adr->next_alias = NULL;
276
277   /*
278    * If we have an entry for this alias in neighbortable, we better adjust it's
279    * main address, because otherwise a fatal inconsistency between
280    * neighbortable and link_set will be created by way of this mid entry.
281    */
282   ne_old = olsr_lookup_neighbor_table_alias(alias);
283   if (ne_old != NULL) {
284     OLSR_PRINTF(2, "Remote main address change detected. Mangling neighbortable to replace %s with %s.\n",
285                 olsr_ip_to_string(&buf1, alias), olsr_ip_to_string(&buf2, main_add));
286     olsr_delete_neighbor_table(alias);
287     ne_new = olsr_insert_neighbor_table(main_add);
288     /* adjust pointers to neighbortable-entry in link_set */
289     ne_ref_rp_count = replace_neighbor_link_set(ne_old, ne_new);
290     if (ne_ref_rp_count > 0)
291       OLSR_PRINTF(2, "Performed %d neighbortable-pointer replacements (%p -> %p) in link_set.\n", ne_ref_rp_count, ne_old, ne_new);
292
293     me_old = mid_lookup_entry_bymain(alias);
294     if (me_old) {
295
296       /*
297        * we knew aliases to the previous main address;
298        * better forget about them now.
299        */
300       OLSR_PRINTF(2,
301                   "I already have an mid entry mapping addresses to this "
302                   "alias address. Removing existing mid entry to preserve consistency of mid_set.\n");
303       olsr_delete_mid_entry(me_old);
304     }
305   }
306
307   if (!insert_mid_tuple(main_add, adr, vtime)) {
308     free(adr);
309   }
310
311   /*
312    *Recalculate topology
313    */
314   changes_neighborhood = true;
315   changes_topology = true;
316 }
317
318 /**
319  * Lookup the main address for a alias address
320  *
321  * @param adr the alias address to check
322  * @return the main address registered on the alias
323  * or NULL if not found
324  */
325 union olsr_ip_addr *
326 mid_lookup_main_addr(const union olsr_ip_addr *adr)
327 {
328   uint32_t hash;
329   struct mid_address *tmp_list;
330
331   hash = olsr_ip_hashing(adr);
332
333   /*Traverse MID list */
334   for (tmp_list = reverse_mid_set[hash].next; tmp_list != &reverse_mid_set[hash]; tmp_list = tmp_list->next) {
335     if (ipequal(&tmp_list->alias, adr))
336       return &tmp_list->main_entry->main_addr;
337   }
338   return NULL;
339
340 }
341
342 /*
343  * Find mid entry to an address.
344  *
345  * @param adr the main address to search for
346  * @return a linked list of address structs
347  */
348 struct mid_entry *
349 mid_lookup_entry_bymain(const union olsr_ip_addr *adr)
350 {
351   struct mid_entry *tmp_list;
352   uint32_t hash;
353
354   hash = olsr_ip_hashing(adr);
355
356   /* Check all registered nodes... */
357   for (tmp_list = mid_set[hash].next; tmp_list != &mid_set[hash]; tmp_list = tmp_list->next) {
358     if (ipequal(&tmp_list->main_addr, adr))
359       return tmp_list;
360   }
361   return NULL;
362 }
363
364 /*
365  * Find all aliases for an address.
366  *
367  * @param adr the main address to search for
368  * @return a linked list of addresses structs
369  */
370 struct mid_address *
371 mid_lookup_aliases(const union olsr_ip_addr *adr)
372 {
373   struct mid_entry *tmp = mid_lookup_entry_bymain(adr);
374   return tmp ? tmp->aliases : NULL;
375 }
376
377 /**
378  * Update the timer for an MID entry
379  *
380  * @param adr the main address of the entry
381  * @return 1 if the node was updated, 0 if not
382  */
383 int
384 olsr_update_mid_table(const union olsr_ip_addr *adr, olsr_reltime vtime)
385 {
386   uint32_t hash;
387   struct ipaddr_str buf;
388   struct mid_entry *tmp_list = mid_set;
389
390   OLSR_PRINTF(3, "MID: update %s\n", olsr_ip_to_string(&buf, adr));
391   hash = olsr_ip_hashing(adr);
392
393   /* Check all registered nodes... */
394   for (tmp_list = mid_set[hash].next; tmp_list != &mid_set[hash]; tmp_list = tmp_list->next) {
395     /*find match */
396     if (ipequal(&tmp_list->main_addr, adr)) {
397       olsr_set_mid_timer(tmp_list, vtime);
398
399       return 1;
400     }
401   }
402   return 0;
403 }
404
405 /**
406  * Remove aliases from 'entry' which are not listed in 'declared_aliases'.
407  *
408  * @param entry the MID entry
409  * @param declared_aliases the list of declared aliases for the MID entry
410  * @return nada
411  */
412 static void
413 olsr_prune_aliases(struct mid_message *message)
414 {
415   const union olsr_ip_addr *m_addr = &message->mid_origaddr;
416   struct mid_alias * declared_aliases = message->mid_addr;
417   struct mid_entry *entry;
418   uint32_t hash;
419   struct mid_address *registered_aliases;
420   struct mid_address *previous_alias;
421   struct mid_alias *save_declared_aliases = declared_aliases;
422
423   hash = olsr_ip_hashing(m_addr);
424
425   /* Check for registered entry */
426   for (entry = mid_set[hash].next; entry != &mid_set[hash]; entry = entry->next) {
427     if (ipequal(&entry->main_addr, m_addr))
428       break;
429   }
430   if (entry == &mid_set[hash]) {
431     /* MID entry not found, nothing to prune here */
432     return;
433   }
434
435   registered_aliases = entry->aliases;
436   previous_alias = NULL;
437
438   while (registered_aliases != NULL) {
439     struct mid_address *current_alias = registered_aliases;
440     registered_aliases = registered_aliases->next_alias;
441
442     declared_aliases = save_declared_aliases;
443
444     /* Go through the list of declared aliases to find the matching current alias */
445     while (declared_aliases != 0 && !ipequal(&current_alias->alias, &declared_aliases->alias_addr)) {
446       declared_aliases = declared_aliases->next;
447     }
448
449     if (declared_aliases == NULL) {
450       /*do not remove alias if vtime still valid (so we assigned something != NULL to declared_aliases)*/
451       if (!olsr_isTimedOut(current_alias->vtime)) declared_aliases = save_declared_aliases;
452     }
453     else current_alias->vtime=olsr_getTimestamp(message->vtime);
454
455     if (declared_aliases == NULL) {
456       struct ipaddr_str buf;
457       /* Current alias not found in list of declared aliases: free current alias */
458       OLSR_PRINTF(1, "MID remove: (%s, ", olsr_ip_to_string(&buf, &entry->main_addr));
459       OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&buf, &current_alias->alias));
460
461       /* Update linked list as seen by 'entry' */
462       if (previous_alias != NULL) {
463         previous_alias->next_alias = current_alias->next_alias;
464       } else {
465         entry->aliases = current_alias->next_alias;
466       }
467
468       /* Remove from hash table */
469       DEQUEUE_ELEM(current_alias);
470
471       /*
472        * Delete the rt_path for the alias.
473        */
474       olsr_delete_routing_table(&current_alias->alias, olsr_cnf->maxplen, &entry->main_addr);
475
476       free(current_alias);
477
478       /*
479        *Recalculate topology
480        */
481       changes_neighborhood = true;
482       changes_topology = true;
483     } else {
484       previous_alias = current_alias;
485     }
486   }
487 }
488
489 /**
490  * Delete a MID entry
491  *
492  * @param entry the entry to delete
493  */
494 void
495 olsr_delete_mid_entry(struct mid_entry *mid)
496 {
497   struct mid_address *aliases;
498
499   /* Free aliases */
500   aliases = mid->aliases;
501   while (aliases) {
502     struct mid_address *tmp_aliases = aliases;
503     aliases = aliases->next_alias;
504     DEQUEUE_ELEM(tmp_aliases);
505
506     /*
507      * Delete the rt_path for the alias.
508      */
509     olsr_delete_routing_table(&tmp_aliases->alias, olsr_cnf->maxplen, &mid->main_addr);
510
511     free(tmp_aliases);
512   }
513
514   /*
515    * Kill any pending timers.
516    */
517   if (mid->mid_timer) {
518     olsr_stop_timer(mid->mid_timer);
519     mid->mid_timer = NULL;
520   }
521
522   /* Dequeue */
523   DEQUEUE_ELEM(mid);
524   free(mid);
525 }
526
527 /**
528  * Print all MID entries
529  * For debuging purposes
530  */
531 void
532 olsr_print_mid_set(void)
533 {
534   int idx;
535
536   OLSR_PRINTF(1, "\n--- %s ------------------------------------------------- MID\n\n", olsr_wallclock_string());
537
538   for (idx = 0; idx < HASHSIZE; idx++) {
539     struct mid_entry *tmp_list = mid_set[idx].next;
540     /*Traverse MID list */
541     for (tmp_list = mid_set[idx].next; tmp_list != &mid_set[idx]; tmp_list = tmp_list->next) {
542       struct mid_address *tmp_addr;
543       struct ipaddr_str buf;
544       OLSR_PRINTF(1, "%s: ", olsr_ip_to_string(&buf, &tmp_list->main_addr));
545       for (tmp_addr = tmp_list->aliases; tmp_addr; tmp_addr = tmp_addr->next_alias) {
546         OLSR_PRINTF(1, " %s ", olsr_ip_to_string(&buf, &tmp_addr->alias));
547       }
548       OLSR_PRINTF(1, "\n");
549     }
550   }
551 }
552
553 /**
554  *Process a received(and parsed) MID message
555  *For every address check if there is a topology node
556  *registered with it and update its addresses.
557  *
558  *@param m the OLSR message received.
559  *@return 1 on success
560  */
561
562 bool
563 olsr_input_mid(union olsr_message *m, struct interface *in_if __attribute__ ((unused)), union olsr_ip_addr *from_addr)
564 {
565   struct ipaddr_str buf;
566   struct mid_alias *tmp_adr;
567   struct mid_message message;
568
569   mid_chgestruct(&message, m);
570
571   if (!olsr_validate_address(&message.mid_origaddr)) {
572     olsr_free_mid_packet(&message);
573     return false;
574   }
575 #ifdef DEBUG
576   OLSR_PRINTF(5, "Processing MID from %s...\n", olsr_ip_to_string(&buf, &message.mid_origaddr));
577 #endif
578   tmp_adr = message.mid_addr;
579
580   /*
581    *      If the sender interface (NB: not originator) of this message
582    *      is not in the symmetric 1-hop neighborhood of this node, the
583    *      message MUST be discarded.
584    */
585
586   if (check_neighbor_link(from_addr) != SYM_LINK) {
587     OLSR_PRINTF(2, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
588     olsr_free_mid_packet(&message);
589     return false;
590   }
591
592   /* Update the timeout of the MID */
593   olsr_update_mid_table(&message.mid_origaddr, message.vtime);
594
595   for (;tmp_adr; tmp_adr = tmp_adr->next) {
596 #ifndef NO_DUPLICATE_DETECTION_HANDLER
597     struct interface *ifs;
598     bool stop = false;
599     for (ifs = ifnet; ifs != NULL; ifs = ifs->int_next) {
600       if (ipequal(&ifs->ip_addr, &tmp_adr->alias_addr)) {
601       /* ignore your own main IP as an incoming MID */
602         olsr_handle_mid_collision(&tmp_adr->alias_addr, &message.mid_origaddr);
603         stop = true;
604         break;
605       }
606     }
607     if (stop) {
608       continue;
609     }
610 #endif
611     if (!mid_lookup_main_addr(&tmp_adr->alias_addr)) {
612       OLSR_PRINTF(1, "MID new: (%s, ", olsr_ip_to_string(&buf, &message.mid_origaddr));
613       OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&buf, &tmp_adr->alias_addr));
614       insert_mid_alias(&message.mid_origaddr, &tmp_adr->alias_addr, message.vtime);
615     } else {
616       olsr_insert_routing_table(&tmp_adr->alias_addr, olsr_cnf->maxplen, &message.mid_origaddr, OLSR_RT_ORIGIN_MID);
617     }
618   }
619
620   olsr_prune_aliases(&message);
621   olsr_free_mid_packet(&message);
622
623   /* Forward the message */
624   return true;
625 }
626
627 /*
628  * Local Variables:
629  * c-basic-offset: 2
630  * indent-tabs-mode: nil
631  * End:
632  */