Rename 'struct interface' to 'struct interface_olsr'
[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 /* DEBUG */
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 /* DEBUG */
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  * @param vtime the expiration time
148  * @return false if mid_address is unnecessary, true otherwise
149  */
150
151 static bool
152 insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, olsr_reltime vtime)
153 {
154   struct mid_entry *tmp;
155   struct mid_address *tmp_adr;
156   uint32_t hash, alias_hash;
157   union olsr_ip_addr *registered_m_addr;
158
159   hash = olsr_ip_hashing(m_addr);
160   alias_hash = olsr_ip_hashing(&alias->alias);
161
162   /* Check for registered entry */
163   for (tmp = mid_set[hash].next; tmp != &mid_set[hash]; tmp = tmp->next) {
164     if (ipequal(&tmp->main_addr, m_addr))
165       break;
166   }
167
168   /* Check if alias is already registered with m_addr */
169   registered_m_addr = mid_lookup_main_addr(&alias->alias);
170   if (registered_m_addr != NULL && ipequal(registered_m_addr, m_addr)) {
171     /* Alias is already registered with main address. Nothing to do here. */
172     return false;
173   }
174
175   /*
176    * Add a rt_path for the alias.
177    */
178   olsr_insert_routing_table(&alias->alias, olsr_cnf->maxplen, m_addr, OLSR_RT_ORIGIN_MID);
179
180   /*If the address was registered */
181   if (tmp != &mid_set[hash]) {
182     tmp_adr = tmp->aliases;
183     tmp->aliases = alias;
184     alias->main_entry = tmp;
185     QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
186     alias->next_alias = tmp_adr;
187     olsr_set_mid_timer(tmp, vtime);
188   } else {
189
190     /*Create new node */
191     tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
192
193     tmp->aliases = alias;
194     alias->main_entry = tmp;
195     QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
196     tmp->main_addr = *m_addr;
197     olsr_set_mid_timer(tmp, vtime);
198
199     /* Queue */
200     QUEUE_ELEM(mid_set[hash], tmp);
201   }
202
203   /*
204    * Delete possible duplicate entries in 2 hop set
205    * and delete duplicate neighbor entries. Redirect
206    * link entries to the correct neighbor entry.
207    *
208    *THIS OPTIMIZATION IS NOT SPECIFIED IN RFC3626
209    */
210
211   tmp_adr = alias;
212
213   while (tmp_adr) {
214     struct neighbor_2_entry *tmp_2_neighbor;
215     struct neighbor_entry *tmp_neigh, *real_neigh;
216
217     /* Delete possible 2 hop neighbor */
218     if ((tmp_2_neighbor = olsr_lookup_two_hop_neighbor_table_mid(&tmp_adr->alias)) != NULL) {
219       struct ipaddr_str buf;
220       OLSR_PRINTF(1, "Deleting 2 hop node from MID: %s to ", olsr_ip_to_string(&buf, &tmp_adr->alias));
221       OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, m_addr));
222
223       olsr_delete_two_hop_neighbor_table(tmp_2_neighbor);
224
225       changes_neighborhood = true;
226     }
227
228     /* Delete a possible neighbor entry */
229     if (((tmp_neigh = olsr_lookup_neighbor_table_alias(&tmp_adr->alias)) != NULL)
230         && ((real_neigh = olsr_lookup_neighbor_table_alias(m_addr)) != NULL)) {
231       struct ipaddr_str buf;
232       OLSR_PRINTF(1, "[MID]Deleting bogus neighbor entry %s real ", olsr_ip_to_string(&buf, &tmp_adr->alias));
233       OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, m_addr));
234
235       replace_neighbor_link_set(tmp_neigh, real_neigh);
236
237       /* Dequeue */
238       DEQUEUE_ELEM(tmp_neigh);
239       /* Delete */
240       free(tmp_neigh);
241
242       changes_neighborhood = true;
243     }
244     tmp_adr = tmp_adr->next_alias;
245   }
246   return true;
247 }
248
249 /**
250  * Insert an alias address for a node.
251  * If the main address is not registered
252  * then a new entry is created.
253  *
254  * @param main_add the main address of the node
255  * @param alias the alias address to insert
256  * @param vtime the expiration time
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  * @param vtime the expiration time
382  * @return 1 if the node was updated, 0 if not
383  */
384 int
385 olsr_update_mid_table(const union olsr_ip_addr *adr, olsr_reltime vtime)
386 {
387   uint32_t hash;
388   struct ipaddr_str buf;
389   struct mid_entry *tmp_list = mid_set;
390
391   OLSR_PRINTF(3, "MID: update %s\n", olsr_ip_to_string(&buf, adr));
392   hash = olsr_ip_hashing(adr);
393
394   /* Check all registered nodes... */
395   for (tmp_list = mid_set[hash].next; tmp_list != &mid_set[hash]; tmp_list = tmp_list->next) {
396     /*find match */
397     if (ipequal(&tmp_list->main_addr, adr)) {
398       olsr_set_mid_timer(tmp_list, vtime);
399
400       return 1;
401     }
402   }
403   return 0;
404 }
405
406 /**
407  * Remove aliases from 'entry' which are not listed in 'declared_aliases'.
408  *
409  * @param message the MID message
410  */
411 static void
412 olsr_prune_aliases(struct mid_message *message)
413 {
414   const union olsr_ip_addr *m_addr = &message->mid_origaddr;
415   struct mid_alias * declared_aliases = message->mid_addr;
416   struct mid_entry *entry;
417   uint32_t hash;
418   struct mid_address *registered_aliases;
419   struct mid_address *previous_alias;
420   struct mid_alias *save_declared_aliases = declared_aliases;
421
422   hash = olsr_ip_hashing(m_addr);
423
424   /* Check for registered entry */
425   for (entry = mid_set[hash].next; entry != &mid_set[hash]; entry = entry->next) {
426     if (ipequal(&entry->main_addr, m_addr))
427       break;
428   }
429   if (entry == &mid_set[hash]) {
430     /* MID entry not found, nothing to prune here */
431     return;
432   }
433
434   registered_aliases = entry->aliases;
435   previous_alias = NULL;
436
437   while (registered_aliases != NULL) {
438     struct mid_address *current_alias = registered_aliases;
439     registered_aliases = registered_aliases->next_alias;
440
441     declared_aliases = save_declared_aliases;
442
443     /* Go through the list of declared aliases to find the matching current alias */
444     while (declared_aliases != 0 && !ipequal(&current_alias->alias, &declared_aliases->alias_addr)) {
445       declared_aliases = declared_aliases->next;
446     }
447
448     if (declared_aliases == NULL) {
449       /*do not remove alias if vtime still valid (so we assigned something != NULL to declared_aliases)*/
450       if (!olsr_isTimedOut(current_alias->vtime)) declared_aliases = save_declared_aliases;
451     }
452     else current_alias->vtime=olsr_getTimestamp(message->vtime);
453
454     if (declared_aliases == NULL) {
455       struct ipaddr_str buf;
456       /* Current alias not found in list of declared aliases: free current alias */
457       OLSR_PRINTF(1, "MID remove: (%s, ", olsr_ip_to_string(&buf, &entry->main_addr));
458       OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&buf, &current_alias->alias));
459
460       /* Update linked list as seen by 'entry' */
461       if (previous_alias != NULL) {
462         previous_alias->next_alias = current_alias->next_alias;
463       } else {
464         entry->aliases = current_alias->next_alias;
465       }
466
467       /* Remove from hash table */
468       DEQUEUE_ELEM(current_alias);
469
470       /*
471        * Delete the rt_path for the alias.
472        */
473       olsr_delete_routing_table(&current_alias->alias, olsr_cnf->maxplen, &entry->main_addr);
474
475       free(current_alias);
476
477       /*
478        *Recalculate topology
479        */
480       changes_neighborhood = true;
481       changes_topology = true;
482     } else {
483       previous_alias = current_alias;
484     }
485   }
486 }
487
488 /**
489  * Delete a MID entry
490  *
491  * @param mid the entry to delete
492  */
493 void
494 olsr_delete_mid_entry(struct mid_entry *mid)
495 {
496   struct mid_address *aliases;
497
498   /* Free aliases */
499   aliases = mid->aliases;
500   while (aliases) {
501     struct mid_address *tmp_aliases = aliases;
502     aliases = aliases->next_alias;
503     DEQUEUE_ELEM(tmp_aliases);
504
505     /*
506      * Delete the rt_path for the alias.
507      */
508     olsr_delete_routing_table(&tmp_aliases->alias, olsr_cnf->maxplen, &mid->main_addr);
509
510     free(tmp_aliases);
511   }
512
513   /*
514    * Kill any pending timers.
515    */
516   if (mid->mid_timer) {
517     olsr_stop_timer(mid->mid_timer);
518     mid->mid_timer = NULL;
519   }
520
521   /* Dequeue */
522   DEQUEUE_ELEM(mid);
523   free(mid);
524 }
525
526 /**
527  * Print all MID entries
528  * For debuging purposes
529  */
530 void
531 olsr_print_mid_set(void)
532 {
533   int idx;
534
535   OLSR_PRINTF(1, "\n--- %s ------------------------------------------------- MID\n\n", olsr_wallclock_string());
536
537   for (idx = 0; idx < HASHSIZE; idx++) {
538     struct mid_entry *tmp_list = mid_set[idx].next;
539     /*Traverse MID list */
540     for (tmp_list = mid_set[idx].next; tmp_list != &mid_set[idx]; tmp_list = tmp_list->next) {
541       struct mid_address *tmp_addr;
542       struct ipaddr_str buf;
543       OLSR_PRINTF(1, "%s: ", olsr_ip_to_string(&buf, &tmp_list->main_addr));
544       for (tmp_addr = tmp_list->aliases; tmp_addr; tmp_addr = tmp_addr->next_alias) {
545         OLSR_PRINTF(1, " %s ", olsr_ip_to_string(&buf, &tmp_addr->alias));
546       }
547       OLSR_PRINTF(1, "\n");
548     }
549   }
550 }
551
552 /**
553  *Process a received(and parsed) MID message
554  *For every address check if there is a topology node
555  *registered with it and update its addresses.
556  *
557  *@param m the OLSR message received.
558  *@param in_if the incoming interface
559  *@param from_addr the sender address
560  *@return 1 on success
561  */
562
563 bool
564 olsr_input_mid(union olsr_message *m, struct interface_olsr *in_if __attribute__ ((unused)), union olsr_ip_addr *from_addr)
565 {
566   struct ipaddr_str buf;
567   struct mid_alias *tmp_adr;
568   struct mid_message message;
569
570   mid_chgestruct(&message, m);
571
572   if (!olsr_validate_address(&message.mid_origaddr)) {
573     olsr_free_mid_packet(&message);
574     return false;
575   }
576 #ifdef DEBUG
577   OLSR_PRINTF(5, "Processing MID from %s...\n", olsr_ip_to_string(&buf, &message.mid_origaddr));
578 #endif /* DEBUG */
579   tmp_adr = message.mid_addr;
580
581   /*
582    *      If the sender interface (NB: not originator) of this message
583    *      is not in the symmetric 1-hop neighborhood of this node, the
584    *      message MUST be discarded.
585    */
586
587   if (check_neighbor_link(from_addr) != SYM_LINK) {
588     OLSR_PRINTF(2, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
589     olsr_free_mid_packet(&message);
590     return false;
591   }
592
593   /* Update the timeout of the MID */
594   olsr_update_mid_table(&message.mid_origaddr, message.vtime);
595
596   for (;tmp_adr; tmp_adr = tmp_adr->next) {
597 #ifndef NO_DUPLICATE_DETECTION_HANDLER
598     struct interface_olsr *ifs;
599     bool stop = false;
600     for (ifs = ifnet; ifs != NULL; ifs = ifs->int_next) {
601       if (ipequal(&ifs->ip_addr, &tmp_adr->alias_addr)) {
602       /* ignore your own main IP as an incoming MID */
603         olsr_handle_mid_collision(&tmp_adr->alias_addr, &message.mid_origaddr);
604         stop = true;
605         break;
606       }
607     }
608     if (stop) {
609       continue;
610     }
611 #endif /* NO_DUPLICATE_DETECTION_HANDLER */
612     if (!mid_lookup_main_addr(&tmp_adr->alias_addr)) {
613       OLSR_PRINTF(1, "MID new: (%s, ", olsr_ip_to_string(&buf, &message.mid_origaddr));
614       OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&buf, &tmp_adr->alias_addr));
615       insert_mid_alias(&message.mid_origaddr, &tmp_adr->alias_addr, message.vtime);
616     } else {
617       olsr_insert_routing_table(&tmp_adr->alias_addr, olsr_cnf->maxplen, &message.mid_origaddr, OLSR_RT_ORIGIN_MID);
618     }
619   }
620
621   olsr_prune_aliases(&message);
622   olsr_free_mid_packet(&message);
623
624   /* Forward the message */
625   return true;
626 }
627
628 /*
629  * Local Variables:
630  * c-basic-offset: 2
631  * indent-tabs-mode: nil
632  * End:
633  */