indent mid_set code
[olsrd.git] / src / mid_set.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004, Andreas T√łnnesen(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 "scheduler.h"
48 #include "neighbor_table.h"
49 #include "link_set.h"
50 #include "tc_set.h"
51 #include "packet.h"             /* struct mid_alias */
52 #include "net_olsr.h"
53
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 #if !defined(NODEBUG) && defined(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",
98               olsr_ip_to_string(&buf, &mid->main_addr));
99 #endif
100
101   olsr_delete_mid_entry(mid);
102 }
103
104
105 /**
106  * Set the mid set expiration timer.
107  *
108  * all timer setting shall be done using this function.
109  * The timer param is a relative timer expressed in milliseconds.
110  */
111 static void
112 olsr_set_mid_timer(struct mid_entry *mid, unsigned int rel_timer)
113 {
114
115   olsr_set_timer(&mid->mid_timer, rel_timer, OLSR_MID_JITTER,
116                  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,
132                  float vtime)
133 {
134   struct mid_entry *tmp;
135   struct mid_address *tmp_adr;
136   olsr_u32_t hash, alias_hash;
137   union olsr_ip_addr *registered_m_addr;
138
139   hash = olsr_ip_hashing(m_addr);
140   alias_hash = olsr_ip_hashing(&alias->alias);
141
142   /* Check for registered entry */
143   for (tmp = mid_set[hash].next; tmp != &mid_set[hash]; tmp = tmp->next) {
144     if (ipequal(&tmp->main_addr, m_addr))
145       break;
146   }
147
148   /* Check if alias is already registered with m_addr */
149   registered_m_addr = mid_lookup_main_addr(&alias->alias);
150   if (registered_m_addr != NULL && ipequal(registered_m_addr, m_addr)) {
151
152     /* Alias is already registered with main address. Nothing to do here. */
153     return;
154   }
155
156   /*
157    * Add a rt_path for the alias.
158    */
159   olsr_insert_routing_table(&alias->alias, olsr_cnf->maxplen, m_addr,
160                             OLSR_RT_ORIGIN_MID);
161
162   /*If the address was registered */
163   if (tmp != &mid_set[hash]) {
164     tmp_adr = tmp->aliases;
165     tmp->aliases = alias;
166     alias->main_entry = tmp;
167     QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
168     alias->next_alias = tmp_adr;
169     olsr_set_mid_timer(tmp, vtime * MSEC_PER_SEC);
170   } else {
171
172     /*Create new node */
173     tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
174
175     tmp->aliases = alias;
176     alias->main_entry = tmp;
177     QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
178     tmp->main_addr = *m_addr;
179     olsr_set_mid_timer(tmp, vtime * MSEC_PER_SEC);
180
181     /* Queue */
182     QUEUE_ELEM(mid_set[hash], tmp);
183   }
184
185
186
187   /*
188    * Delete possible duplicate entries in 2 hop set
189    * and delete duplicate neighbor entries. Redirect
190    * link entries to the correct neighbor entry.
191    *
192    *THIS OPTIMIZATION IS NOT SPECIFIED IN RFC3626
193    */
194
195   tmp_adr = alias;
196
197   while (tmp_adr) {
198     struct neighbor_2_entry *tmp_2_neighbor;
199     struct neighbor_entry *tmp_neigh, *real_neigh;
200
201     /* Delete possible 2 hop neighbor */
202     if ((tmp_2_neighbor =
203          olsr_lookup_two_hop_neighbor_table_mid(&tmp_adr->alias)) != NULL) {
204 #ifndef NODEBUG
205       struct ipaddr_str buf;
206 #endif
207       OLSR_PRINTF(1, "Deleting 2 hop node from MID: %s to ",
208                   olsr_ip_to_string(&buf, &tmp_adr->alias));
209       OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, m_addr));
210
211       olsr_delete_two_hop_neighbor_table(tmp_2_neighbor);
212
213       changes_neighborhood = OLSR_TRUE;
214     }
215
216     /* Delete a possible neighbor entry */
217     if (((tmp_neigh =
218           olsr_lookup_neighbor_table_alias(&tmp_adr->alias)) != NULL)
219         && ((real_neigh = olsr_lookup_neighbor_table_alias(m_addr)) != NULL))
220     {
221 #ifndef NODEBUG
222       struct ipaddr_str buf;
223 #endif
224       OLSR_PRINTF(1, "[MID]Deleting bogus neighbor entry %s real ",
225                   olsr_ip_to_string(&buf, &tmp_adr->alias));
226       OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, m_addr));
227
228       replace_neighbor_link_set(tmp_neigh, real_neigh);
229
230       /* Dequeue */
231       DEQUEUE_ELEM(tmp_neigh);
232       /* Delete */
233       free(tmp_neigh);
234
235       changes_neighborhood = OLSR_TRUE;
236     }
237     tmp_adr = tmp_adr->next_alias;
238   }
239 }
240
241
242 /**
243  * Insert an alias address for a node.
244  * If the main address is not registered
245  * then a new entry is created.
246  *
247  * @param main_add the main address of the node
248  * @param alias the alias address to insert
249  * @param seq the sequence number to register a new node with
250  * @return nada
251  */
252 void
253 insert_mid_alias(union olsr_ip_addr *main_add, const union olsr_ip_addr *alias,
254                  float vtime)
255 {
256   struct neighbor_entry *ne_old, *ne_new;
257   struct mid_entry *me_old;
258   int ne_ref_rp_count;
259 #ifndef NODEBUG
260   struct ipaddr_str buf1, buf2;
261 #endif
262   struct mid_address *adr;
263   if (!olsr_validate_address(alias))
264     return;
265
266   OLSR_PRINTF(1, "Inserting alias %s for ", olsr_ip_to_string(&buf1, alias));
267   OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf1, main_add));
268
269   adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
270
271   adr->alias = *alias;
272   adr->next_alias = NULL;
273
274   /*
275    * If we have an entry for this alias in neighbortable, we better adjust it's
276    * main address, because otherwise a fatal inconsistency between
277    * neighbortable and link_set will be created by way of this mid entry.
278    */
279   ne_old = olsr_lookup_neighbor_table_alias(alias);
280   if (ne_old != NULL) {
281     OLSR_PRINTF(2,
282                 "Remote main address change detected. Mangling neighbortable to replace %s with %s.\n",
283                 olsr_ip_to_string(&buf1, alias), olsr_ip_to_string(&buf2,
284                                                                    main_add));
285     olsr_delete_neighbor_table(alias);
286     ne_new = olsr_insert_neighbor_table(main_add);
287     /* adjust pointers to neighbortable-entry in link_set */
288     ne_ref_rp_count = replace_neighbor_link_set(ne_old, ne_new);
289     if (ne_ref_rp_count > 0)
290       OLSR_PRINTF(2,
291                   "Performed %d neighbortable-pointer replacements (%p -> %p) in link_set.\n",
292                   ne_ref_rp_count, ne_old, ne_new);
293
294     me_old = mid_lookup_entry_bymain(alias);
295     if (me_old) {
296
297       /* 
298        * we knew aliases to the previous main address;
299        * better forget about them now.
300        */
301       OLSR_PRINTF(2, "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   insert_mid_tuple(main_add, adr, vtime);
308
309   /*
310    *Recalculate topology
311    */
312   changes_neighborhood = OLSR_TRUE;
313   changes_topology = OLSR_TRUE;
314 }
315
316 /**
317  * Lookup the main address for a alias address
318  *
319  * @param adr the alias address to check
320  * @return the main address registered on the alias
321  * or NULL if not found
322  */
323 union olsr_ip_addr *
324 mid_lookup_main_addr(const union olsr_ip_addr *adr)
325 {
326   olsr_u32_t hash;
327   struct mid_address *tmp_list;
328
329   hash = olsr_ip_hashing(adr);
330
331   /*Traverse MID list */
332   for (tmp_list = reverse_mid_set[hash].next;
333        tmp_list != &reverse_mid_set[hash]; tmp_list = tmp_list->next) {
334     if (ipequal(&tmp_list->alias, adr))
335       return &tmp_list->main_entry->main_addr;
336   }
337   return NULL;
338
339 }
340
341 /*
342  * Find mid entry to an address.
343  *
344  * @param adr the main address to search for
345  * @return a linked list of address structs
346  */
347 struct mid_entry *
348 mid_lookup_entry_bymain(const union olsr_ip_addr *adr)
349 {
350   struct mid_entry *tmp_list;
351   olsr_u32_t hash;
352
353   hash = olsr_ip_hashing(adr);
354
355   /* Check all registered nodes... */
356   for (tmp_list = mid_set[hash].next;
357        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 /**
379  * Update the timer for an MID entry
380  *
381  * @param adr the main address of the entry
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, float vtime)
386 {
387   olsr_u32_t hash;
388 #ifndef NODEBUG
389   struct ipaddr_str buf;
390 #endif
391   struct mid_entry *tmp_list = mid_set;
392
393   OLSR_PRINTF(3, "MID: update %s\n", olsr_ip_to_string(&buf, adr));
394   hash = olsr_ip_hashing(adr);
395
396   /* Check all registered nodes... */
397   for (tmp_list = mid_set[hash].next;
398        tmp_list != &mid_set[hash]; tmp_list = tmp_list->next) {
399     /*find match */
400     if (ipequal(&tmp_list->main_addr, adr)) {
401       olsr_set_mid_timer(tmp_list, vtime * MSEC_PER_SEC);
402
403       return 1;
404     }
405   }
406   return 0;
407 }
408
409
410 /**
411  * Remove aliases from 'entry' which are not listed in 'declared_aliases'.
412  *
413  * @param entry the MID entry
414  * @param declared_aliases the list of declared aliases for the MID entry
415  * @return nada
416  */
417 void
418 olsr_prune_aliases(const union olsr_ip_addr *m_addr,
419                    struct mid_alias *declared_aliases)
420 {
421   struct mid_entry *entry;
422   olsr_u32_t hash;
423   struct mid_address *registered_aliases;
424   struct mid_address *previous_alias;
425   struct mid_alias *save_declared_aliases = declared_aliases;
426
427   hash = olsr_ip_hashing(m_addr);
428
429   /* Check for registered entry */
430   for (entry = mid_set[hash].next; entry != &mid_set[hash]; entry = entry->next) {
431     if (ipequal(&entry->main_addr, m_addr))
432       break;
433   }
434   if (entry == &mid_set[hash]) {
435     /* MID entry not found, nothing to prune here */
436     return;
437   }
438
439   registered_aliases = entry->aliases;
440   previous_alias = NULL;
441
442   while (registered_aliases != NULL) {
443     struct mid_address *current_alias = registered_aliases;
444     registered_aliases = registered_aliases->next_alias;
445
446     declared_aliases = save_declared_aliases;
447
448     /* Go through the list of declared aliases to find the matching current alias */
449     while (declared_aliases != 0 &&
450            !ipequal(&current_alias->alias, &declared_aliases->alias_addr)) {
451       declared_aliases = declared_aliases->next;
452     }
453
454     if (declared_aliases == NULL) {
455 #ifndef NODEBUG
456       struct ipaddr_str buf;
457 #endif
458       /* Current alias not found in list of declared aliases: free current alias */
459       OLSR_PRINTF(1, "MID remove: (%s, ",
460                   olsr_ip_to_string(&buf, &entry->main_addr));
461       OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&buf, &current_alias->alias));
462
463       /* Update linked list as seen by 'entry' */
464       if (previous_alias != NULL) {
465         previous_alias->next_alias = current_alias->next_alias;
466       } else {
467         entry->aliases = current_alias->next_alias;
468       }
469
470       /* Remove from hash table */
471       DEQUEUE_ELEM(current_alias);
472
473       /*
474        * Delete the rt_path for the alias.
475        */
476       olsr_delete_routing_table(&current_alias->alias, olsr_cnf->maxplen,
477                                 &entry->main_addr);
478
479       free(current_alias);
480
481       /*
482        *Recalculate topology
483        */
484       changes_neighborhood = OLSR_TRUE;
485       changes_topology = OLSR_TRUE;
486     } else {
487       previous_alias = current_alias;
488     }
489   }
490 }
491
492
493 /**
494  * Delete a MID entry
495  *
496  * @param entry the entry to delete
497  */
498 void
499 olsr_delete_mid_entry(struct mid_entry *mid)
500 {
501   struct mid_address *aliases;
502
503   /* Free aliases */
504   aliases = mid->aliases;
505   while (aliases) {
506     struct mid_address *tmp_aliases = aliases;
507     aliases = aliases->next_alias;
508     DEQUEUE_ELEM(tmp_aliases);
509
510
511     /*
512      * Delete the rt_path for the alias.
513      */
514     olsr_delete_routing_table(&tmp_aliases->alias, olsr_cnf->maxplen,
515                               &mid->main_addr);
516
517     free(tmp_aliases);
518   }
519
520   /*
521    * Kill any pending timers.
522    */
523   if (mid->mid_timer) {
524     olsr_stop_timer(mid->mid_timer);
525     mid->mid_timer = NULL;
526   }
527
528   /* Dequeue */
529   DEQUEUE_ELEM(mid);
530   free(mid);
531
532   return 0;
533 }
534
535
536 /**
537  * Print all MID entries
538  * For debuging purposes
539  */
540 void
541 olsr_print_mid_set(void)
542 {
543   int idx;
544
545   OLSR_PRINTF(1,
546               "\n--- %s ------------------------------------------------- MID\n\n",
547               olsr_wallclock_string());
548
549   for (idx = 0; idx < HASHSIZE; idx++) {
550     struct mid_entry *tmp_list = mid_set[idx].next;
551     /*Traverse MID list */
552     for (tmp_list = mid_set[idx].next; tmp_list != &mid_set[idx];
553          tmp_list = tmp_list->next) {
554       struct mid_address *tmp_addr;
555 #ifndef NODEBUG
556       struct ipaddr_str buf;
557 #endif
558       OLSR_PRINTF(1, "%s: ", olsr_ip_to_string(&buf, &tmp_list->main_addr));
559       for (tmp_addr = tmp_list->aliases; tmp_addr;
560            tmp_addr = tmp_addr->next_alias) {
561         OLSR_PRINTF(1, " %s ", olsr_ip_to_string(&buf, &tmp_addr->alias));
562       }
563       OLSR_PRINTF(1, "\n");
564     }
565   }
566 }
567
568 /*
569  * Local Variables:
570  * c-basic-offset: 2
571  * End:
572  */