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