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