* killed all "inline"s
[olsrd.git] / src / mid_set.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without 
7  * modification, are permitted provided that the following conditions 
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright 
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright 
13  *   notice, this list of conditions and the following disclaimer in 
14  *   the documentation and/or other materials provided with the 
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its 
17  *   contributors may be used to endorse or promote products derived 
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  * $Id: mid_set.c,v 1.19 2007/04/20 14:23:41 bernd67 Exp $
40  */
41
42 #include "defs.h"
43 #include "two_hop_neighbor_table.h"
44 #include "mid_set.h"
45 #include "olsr.h"
46 #include "scheduler.h"
47 #include "neighbor_table.h"
48 #include "link_set.h"
49 #include "packet.h" /* struct mid_alias */
50
51
52 struct mid_entry mid_set[HASHSIZE];
53 struct mid_address reverse_mid_set[HASHSIZE];
54
55 struct mid_entry *mid_lookup_entry_bymain(union olsr_ip_addr *adr);
56
57 /**
58  * Initialize the MID set
59  *
60  */
61
62 int
63 olsr_init_mid_set(void)
64 {
65   int index;
66
67   OLSR_PRINTF(5, "MID: init\n")
68
69   /* Since the holdingtime is assumed to be rather large for 
70    * MID entries, the timeoutfunction is only ran once every second
71    */
72   olsr_register_scheduler_event(&olsr_time_out_mid_set, NULL, 1, 0, NULL);
73
74   for(index=0;index<HASHSIZE;index++)
75     {
76       mid_set[index].next = &mid_set[index];
77       mid_set[index].prev = &mid_set[index];
78
79       reverse_mid_set[index].next = &reverse_mid_set[index];
80       reverse_mid_set[index].prev = &reverse_mid_set[index];
81     }
82
83   return 1;
84 }
85
86
87 /**
88  *Insert a new interface alias to the interface association set.
89  *If the main interface of the association is not yet registered
90  *in the set a new entry is created.
91  *
92  *@param m_addr the main address of the node
93  *@param alias the alias address to insert
94  *
95  *@return nada
96  */
97
98 void 
99 insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, float vtime)
100 {
101   struct mid_entry *tmp;
102   struct mid_address *tmp_adr;
103   olsr_u32_t hash, alias_hash;
104   union olsr_ip_addr *registered_m_addr;
105
106   hash = olsr_hashing(m_addr);
107   alias_hash = olsr_hashing(&alias->alias);
108
109   /* Check for registered entry */
110   for(tmp = mid_set[hash].next;
111       tmp != &mid_set[hash];
112       tmp = tmp->next)
113     {
114       if(COMP_IP(&tmp->main_addr, m_addr))
115         break;
116      }
117
118   /* Check if alias is already registered with m_addr */
119   registered_m_addr = mid_lookup_main_addr(&alias->alias);
120   if (registered_m_addr != NULL && COMP_IP(registered_m_addr, m_addr))
121     {
122       /* Alias is already registered with main address. Nothing to do here. */
123       return;
124     }
125
126   /*If the address was registered*/ 
127   if(tmp != &mid_set[hash])
128     {
129       tmp_adr = tmp->aliases;
130       tmp->aliases = alias;
131       alias->main_entry = tmp;
132       QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
133       alias->next_alias = tmp_adr;
134       tmp->ass_timer = GET_TIMESTAMP(vtime*1000);
135     }
136       /*Create new node*/
137   else
138     {
139       tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
140
141       tmp->aliases = alias;
142       alias->main_entry = tmp;
143       QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
144       COPY_IP(&tmp->main_addr, m_addr);
145       tmp->ass_timer = GET_TIMESTAMP(vtime*1000);
146       /* Queue */
147       QUEUE_ELEM(mid_set[hash], tmp);
148     }
149   
150
151
152   /*
153    * Delete possible duplicate entries in 2 hop set
154    * and delete duplicate neighbor entries. Redirect
155    * link entries to the correct neighbor entry.
156    *
157    *THIS OPTIMIZATION IS NOT SPECIFIED IN RFC3626
158    */
159
160   tmp_adr = alias;
161
162   while(tmp_adr)
163     {
164       struct neighbor_2_entry *tmp_2_neighbor;
165       struct neighbor_entry *tmp_neigh, *real_neigh;
166
167       /* Delete possible 2 hop neighbor */
168       if((tmp_2_neighbor = olsr_lookup_two_hop_neighbor_table_mid(&tmp_adr->alias)) != NULL)
169         {
170           OLSR_PRINTF(1, "Deleting 2 hop node from MID: %s to ", olsr_ip_to_string(&tmp_adr->alias))
171           OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(m_addr))
172
173           olsr_delete_two_hop_neighbor_table(tmp_2_neighbor);
174
175           changes_neighborhood = OLSR_TRUE;
176         }
177
178       /* Delete a possible neighbor entry */
179       if(((tmp_neigh = olsr_lookup_neighbor_table_alias(&tmp_adr->alias)) != NULL)
180          && ((real_neigh = olsr_lookup_neighbor_table_alias(m_addr)) != NULL))
181
182         {
183           OLSR_PRINTF(1, "[MID]Deleting bogus neighbor entry %s real ", olsr_ip_to_string(&tmp_adr->alias))
184           OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(m_addr))
185
186           replace_neighbor_link_set(tmp_neigh, real_neigh);
187
188           /* Dequeue */
189           DEQUEUE_ELEM(tmp_neigh);
190           /* Delete */
191           free(tmp_neigh);
192
193           changes_neighborhood = OLSR_TRUE;
194         }
195       
196       tmp_adr = tmp_adr->next_alias;
197     }
198
199
200 }
201
202
203 /**
204  *Insert an alias address for a node.
205  *If the main address is not registered
206  *then a new entry is created.
207  *
208  *@param main_add the main address of the node
209  *@param alias the alias address to insert
210  *@param seq the sequence number to register a new node with
211  *
212  *@return nada
213  */
214 void
215 insert_mid_alias(union olsr_ip_addr *main_add, union olsr_ip_addr *alias, float vtime)
216 {
217   struct mid_address *adr;
218   struct neighbor_entry *ne_old, *ne_new;
219   struct mid_entry *me_old;
220   int ne_ref_rp_count;
221
222   adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
223   
224   OLSR_PRINTF(1, "Inserting alias %s for ", olsr_ip_to_string(alias))
225   OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(main_add))
226
227   COPY_IP(&adr->alias, alias);
228   adr->next_alias = NULL;
229   
230   // If we have an entry for this alias in neighbortable, we better adjust it's
231   // main address, because otherwise a fatal inconsistency between
232   // neighbortable and link_set will be created by way of this mid entry.
233   ne_old = olsr_lookup_neighbor_table_alias(alias);
234   if (ne_old != NULL) {
235      OLSR_PRINTF(2, "Remote main address change detected. Mangling neighbortable to replace %s with %s.\n", olsr_ip_to_string(alias), olsr_ip_to_string(main_add));
236      olsr_delete_neighbor_table(alias);
237      ne_new = olsr_insert_neighbor_table(main_add);
238      // adjust pointers to neighbortable-entry in link_set
239      ne_ref_rp_count = replace_neighbor_link_set(ne_old, ne_new);
240      if (ne_ref_rp_count > 0)
241         OLSR_PRINTF(2, "Performed %d neighbortable-pointer replacements (%p -> %p) in link_set.\n", ne_ref_rp_count, ne_old, ne_new);
242      
243      me_old = mid_lookup_entry_bymain(alias);
244      if (me_old) {
245         // we knew aliases to the previous main address; better forget about
246         // them now.
247         OLSR_PRINTF(2, "I already have an mid entry mapping addresses to this alias address. Removing existing mid entry to preserve consistency of mid_set.\n");
248         mid_delete_node(me_old);
249      }
250   }
251   
252   insert_mid_tuple(main_add, adr, vtime);
253   
254   /*
255    *Recalculate topology
256    */
257   changes_neighborhood = OLSR_TRUE;
258   changes_topology = OLSR_TRUE;
259   
260   //print_mid_list();
261 }
262
263
264
265
266 /**
267  *Lookup the main address for a alias address
268  *
269  *@param adr the alias address to check
270  *
271  *@return the main address registered on the alias
272  *or NULL if not found
273  */
274 union olsr_ip_addr *
275 mid_lookup_main_addr(union olsr_ip_addr *adr)
276 {
277   olsr_u32_t hash;
278   struct mid_address *tmp_list;
279
280   hash = olsr_hashing(adr);
281   /*Traverse MID list*/
282   for(tmp_list = reverse_mid_set[hash].next; 
283       tmp_list != &reverse_mid_set[hash];
284       tmp_list = tmp_list->next)
285         {
286           if(COMP_IP(&tmp_list->alias, adr))
287             return &tmp_list->main_entry->main_addr;
288         }
289   return NULL;
290
291 }
292
293
294 /* Find mid entry to an address.
295  * @param adr the main address to search for
296  *
297  * @return a linked list of address structs
298  */
299 struct mid_entry *
300 mid_lookup_entry_bymain(union olsr_ip_addr *adr)
301 {
302   struct mid_entry *tmp_list;
303   olsr_u32_t hash;
304
305   //OLSR_PRINTF(1, "MID: lookup entry...")
306
307   hash = olsr_hashing(adr);
308
309   /* Check all registered nodes...*/
310   for(tmp_list = mid_set[hash].next;
311       tmp_list != &mid_set[hash];
312       tmp_list = tmp_list->next)
313     {
314       if(COMP_IP(&tmp_list->main_addr, adr))
315         return tmp_list;
316     }
317
318
319   return NULL;
320 }
321
322
323 /*
324  *Find all aliases for an address.
325  *
326  *@param adr the main address to search for
327  *
328  *@return a linked list of addresses structs
329  */
330 struct mid_address *
331 mid_lookup_aliases(union olsr_ip_addr *adr)
332 {
333   struct mid_entry *tmp = mid_lookup_entry_bymain(adr);
334   return tmp ? tmp->aliases : NULL;
335 }
336
337
338 /**
339  *Update the timer for an entry
340  *
341  *@param adr the main address of the entry
342  *
343  *@return 1 if the node was updated, 0 if not
344  */
345 int
346 olsr_update_mid_table(union olsr_ip_addr *adr, float vtime)
347 {
348   struct mid_entry *tmp_list = mid_set;
349   olsr_u32_t hash;
350
351   OLSR_PRINTF(3, "MID: update %s\n", olsr_ip_to_string(adr))
352   hash = olsr_hashing(adr);
353
354   /* Check all registered nodes...*/
355   for(tmp_list = mid_set[hash].next;
356       tmp_list != &mid_set[hash];
357       tmp_list = tmp_list->next)
358     {
359       /*find match*/
360       if(COMP_IP(&tmp_list->main_addr, adr))
361         {
362           // printf("MID: Updating timer for node %s\n", olsr_ip_to_string(&tmp_list->main_addr));
363           tmp_list->ass_timer = GET_TIMESTAMP(vtime*1000);
364
365           return 1;
366         }
367     }
368   return 0;
369 }
370
371
372 /**
373  *Remove aliases from 'entry' which are not listed in 'declared_aliases'.
374  *
375  *@param entry the MID entry
376  *@param declared_aliases the list of declared aliases for the MID entry
377  *
378  *@return nada
379  */
380 void
381 olsr_prune_aliases(union olsr_ip_addr *m_addr, struct mid_alias *declared_aliases)
382 {
383   struct mid_entry *entry;
384   olsr_u32_t hash;
385   struct mid_address *registered_aliases;
386   struct mid_address *previous_alias;
387   struct mid_alias *save_declared_aliases = declared_aliases;
388
389   hash = olsr_hashing(m_addr);
390
391   /* Check for registered entry */
392   for(entry = mid_set[hash].next;
393       entry != &mid_set[hash];
394       entry = entry->next)
395     {
396       if(COMP_IP(&entry->main_addr, m_addr))
397         break;
398     }
399   if(entry == &mid_set[hash])
400     {
401       /* MID entry not found, nothing to prune here */
402       return;
403     }
404
405   registered_aliases = entry->aliases;
406   previous_alias = NULL;
407
408   while(registered_aliases != 0)
409     {
410       struct mid_address *current_alias = registered_aliases;
411       registered_aliases = registered_aliases->next_alias;
412
413       declared_aliases = save_declared_aliases;
414
415       /* Go through the list of declared aliases to find the matching current alias */
416       while(declared_aliases != 0 &&
417             ! COMP_IP(&current_alias->alias, &declared_aliases->alias_addr))
418         {
419           declared_aliases = declared_aliases->next;
420         }
421
422       if (declared_aliases == 0)
423         {
424           /* Current alias not found in list of declared aliases: free current alias */
425           OLSR_PRINTF(1, "MID remove: (%s, ", olsr_ip_to_string(&entry->main_addr))
426           OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&current_alias->alias))
427
428           /* Update linked list as seen by 'entry' */
429           if (previous_alias != NULL)
430             {
431               previous_alias->next_alias = current_alias->next_alias;
432             }
433           else
434             {
435               entry->aliases = current_alias->next_alias;
436             }
437
438           /* Remove from hash table */
439           DEQUEUE_ELEM(current_alias);
440  
441           free(current_alias);
442
443           /*
444            *Recalculate topology
445            */
446           changes_neighborhood = OLSR_TRUE;
447           changes_topology = OLSR_TRUE;
448         }
449       else
450         {
451           previous_alias = current_alias;
452         }
453     }
454 }
455
456
457
458 /**
459  *Find timed out entries and delete them
460  *
461  *@return nada
462  */
463 void
464 olsr_time_out_mid_set(void *foo __attribute__((unused)))
465 {
466   int index;
467
468
469   for(index=0;index<HASHSIZE;index++)
470     {
471       struct mid_entry *tmp_list = mid_set[index].next;
472       /*Traverse MID list*/
473       while(tmp_list != &mid_set[index])
474         {
475           /*Check if the entry is timed out*/
476           if(TIMED_OUT(tmp_list->ass_timer))
477             {
478               struct mid_entry *entry_to_delete = tmp_list;
479               tmp_list = tmp_list->next;
480 #ifdef DEBUG
481               OLSR_PRINTF(1, "MID info for %s timed out.. deleting it\n", 
482                           olsr_ip_to_string(&entry_to_delete->main_addr))
483 #endif
484               /*Delete it*/
485               mid_delete_node(entry_to_delete);
486             }
487           else
488               tmp_list = tmp_list->next;
489         }
490     }
491
492   return;
493 }
494
495
496 /*
497  *Delete an entry
498  *
499  *@param entry the entry to delete
500  *
501  *@return 1
502  */
503 int
504 mid_delete_node(struct mid_entry *entry)
505 {
506   struct mid_address *aliases;
507
508   /* Free aliases */
509   aliases = entry->aliases;
510   while(aliases)
511     {
512       struct mid_address *tmp_aliases = aliases;
513       aliases = aliases->next_alias;
514       DEQUEUE_ELEM(tmp_aliases);
515       free(tmp_aliases);
516     }
517   /* Dequeue */
518   DEQUEUE_ELEM(entry);
519   free(entry);
520   
521   return 0;
522 }
523
524
525 /**
526  *Print all multiple interface info
527  *For debuging purposes
528  */
529 void
530 olsr_print_mid_set(void)
531 {
532   int index;
533
534   OLSR_PRINTF(1, "mid set: %02d:%02d:%02d.%06lu\n",nowtm->tm_hour, nowtm->tm_min, nowtm->tm_sec, now.tv_usec)
535
536   for(index=0;index<HASHSIZE;index++)
537     {
538       struct mid_entry *tmp_list = mid_set[index].next;
539       /*Traverse MID list*/
540       for(tmp_list = mid_set[index].next; tmp_list != &mid_set[index]; tmp_list = tmp_list->next)
541         {
542           struct mid_address *tmp_addr;
543           
544           OLSR_PRINTF(1, "%s: ", olsr_ip_to_string(&tmp_list->main_addr))
545           for(tmp_addr = tmp_list->aliases;tmp_addr;tmp_addr = tmp_addr->next_alias)
546             {
547               OLSR_PRINTF(1, " %s ", olsr_ip_to_string(&tmp_addr->alias))
548             }
549           OLSR_PRINTF(1, "\n")    
550         }
551     }
552
553 }
554
555
556
557
558