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