* const-ify parameters
[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.21 2007/08/02 21:50:22 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(const 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 idx;
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(idx=0;idx<HASHSIZE;idx++)
75     {
76       mid_set[idx].next = &mid_set[idx];
77       mid_set[idx].prev = &mid_set[idx];
78
79       reverse_mid_set[idx].next = &reverse_mid_set[idx];
80       reverse_mid_set[idx].prev = &reverse_mid_set[idx];
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(const 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   else
137     {
138       /*Create new node*/
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(const union olsr_ip_addr *main_add, const 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  *Lookup the main address for a alias address
265  *
266  *@param adr the alias address to check
267  *
268  *@return the main address registered on the alias
269  *or NULL if not found
270  */
271 union olsr_ip_addr *
272 mid_lookup_main_addr(const union olsr_ip_addr *adr)
273 {
274   olsr_u32_t hash;
275   struct mid_address *tmp_list;
276
277   hash = olsr_hashing(adr);
278   /*Traverse MID list*/
279   for(tmp_list = reverse_mid_set[hash].next; 
280       tmp_list != &reverse_mid_set[hash];
281       tmp_list = tmp_list->next)
282         {
283           if(COMP_IP(&tmp_list->alias, adr))
284             return &tmp_list->main_entry->main_addr;
285         }
286   return NULL;
287
288 }
289
290 /* Find mid entry to an address.
291  * @param adr the main address to search for
292  *
293  * @return a linked list of address structs
294  */
295 struct mid_entry *
296 mid_lookup_entry_bymain(const union olsr_ip_addr *adr)
297 {
298   struct mid_entry *tmp_list;
299   olsr_u32_t hash;
300
301   //OLSR_PRINTF(1, "MID: lookup entry...");
302
303   hash = olsr_hashing(adr);
304
305   /* Check all registered nodes...*/
306   for(tmp_list = mid_set[hash].next;
307       tmp_list != &mid_set[hash];
308       tmp_list = tmp_list->next)
309     {
310       if(COMP_IP(&tmp_list->main_addr, adr))
311         return tmp_list;
312     }
313   return NULL;
314 }
315
316 /*
317  *Find all aliases for an address.
318  *
319  *@param adr the main address to search for
320  *
321  *@return a linked list of addresses structs
322  */
323 struct mid_address *
324 mid_lookup_aliases(const union olsr_ip_addr *adr)
325 {
326   struct mid_entry *tmp = mid_lookup_entry_bymain(adr);
327   return tmp ? tmp->aliases : NULL;
328 }
329
330
331 /**
332  *Update the timer for an entry
333  *
334  *@param adr the main address of the entry
335  *
336  *@return 1 if the node was updated, 0 if not
337  */
338 int
339 olsr_update_mid_table(const union olsr_ip_addr *adr, float vtime)
340 {
341   struct mid_entry *tmp_list = mid_set;
342   olsr_u32_t hash;
343
344   OLSR_PRINTF(3, "MID: update %s\n", olsr_ip_to_string(adr));
345   hash = olsr_hashing(adr);
346
347   /* Check all registered nodes...*/
348   for(tmp_list = mid_set[hash].next;
349       tmp_list != &mid_set[hash];
350       tmp_list = tmp_list->next)
351     {
352       /*find match*/
353       if(COMP_IP(&tmp_list->main_addr, adr))
354         {
355           // printf("MID: Updating timer for node %s\n", olsr_ip_to_string(&tmp_list->main_addr));
356           tmp_list->ass_timer = GET_TIMESTAMP(vtime*1000);
357
358           return 1;
359         }
360     }
361   return 0;
362 }
363
364
365 /**
366  *Remove aliases from 'entry' which are not listed in 'declared_aliases'.
367  *
368  *@param entry the MID entry
369  *@param declared_aliases the list of declared aliases for the MID entry
370  *
371  *@return nada
372  */
373 void
374 olsr_prune_aliases(const union olsr_ip_addr *m_addr, struct mid_alias *declared_aliases)
375 {
376   struct mid_entry *entry;
377   olsr_u32_t hash;
378   struct mid_address *registered_aliases;
379   struct mid_address *previous_alias;
380   struct mid_alias *save_declared_aliases = declared_aliases;
381
382   hash = olsr_hashing(m_addr);
383
384   /* Check for registered entry */
385   for(entry = mid_set[hash].next;
386       entry != &mid_set[hash];
387       entry = entry->next)
388     {
389       if(COMP_IP(&entry->main_addr, m_addr))
390         break;
391     }
392   if(entry == &mid_set[hash])
393     {
394       /* MID entry not found, nothing to prune here */
395       return;
396     }
397
398   registered_aliases = entry->aliases;
399   previous_alias = NULL;
400
401   while(registered_aliases != NULL)
402     {
403       struct mid_address *current_alias = registered_aliases;
404       registered_aliases = registered_aliases->next_alias;
405
406       declared_aliases = save_declared_aliases;
407
408       /* Go through the list of declared aliases to find the matching current alias */
409       while(declared_aliases != 0 &&
410             ! COMP_IP(&current_alias->alias, &declared_aliases->alias_addr))
411         {
412           declared_aliases = declared_aliases->next;
413         }
414
415       if (declared_aliases == NULL)
416         {
417           /* Current alias not found in list of declared aliases: free current alias */
418           OLSR_PRINTF(1, "MID remove: (%s, ", olsr_ip_to_string(&entry->main_addr));
419             OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&current_alias->alias));
420
421           /* Update linked list as seen by 'entry' */
422           if (previous_alias != NULL)
423             {
424               previous_alias->next_alias = current_alias->next_alias;
425             }
426           else
427             {
428               entry->aliases = current_alias->next_alias;
429             }
430
431           /* Remove from hash table */
432           DEQUEUE_ELEM(current_alias);
433  
434           free(current_alias);
435
436           /*
437            *Recalculate topology
438            */
439           changes_neighborhood = OLSR_TRUE;
440           changes_topology = OLSR_TRUE;
441         }
442       else
443         {
444           previous_alias = current_alias;
445         }
446     }
447 }
448
449
450
451 /**
452  *Find timed out entries and delete them
453  *
454  *@return nada
455  */
456 void
457 olsr_time_out_mid_set(void *foo __attribute__((unused)))
458 {
459   int idx;
460
461   for(idx=0;idx<HASHSIZE;idx++)
462     {
463       struct mid_entry *tmp_list = mid_set[idx].next;
464       /*Traverse MID list*/
465       while(tmp_list != &mid_set[idx])
466         {
467           /*Check if the entry is timed out*/
468           if(TIMED_OUT(tmp_list->ass_timer))
469             {
470               struct mid_entry *entry_to_delete = tmp_list;
471               tmp_list = tmp_list->next;
472 #ifdef DEBUG
473               OLSR_PRINTF(1, "MID info for %s timed out.. deleting it\n",
474                           olsr_ip_to_string(&entry_to_delete->main_addr));
475 #endif
476               /*Delete it*/
477               mid_delete_node(entry_to_delete);
478             }
479           else
480               tmp_list = tmp_list->next;
481         }
482     }
483
484   return;
485 }
486
487
488 /*
489  *Delete an entry
490  *
491  *@param entry the entry to delete
492  *
493  *@return 1
494  */
495 int
496 mid_delete_node(struct mid_entry *entry)
497 {
498   struct mid_address *aliases;
499
500   /* Free aliases */
501   aliases = entry->aliases;
502   while(aliases)
503     {
504       struct mid_address *tmp_aliases = aliases;
505       aliases = aliases->next_alias;
506       DEQUEUE_ELEM(tmp_aliases);
507       free(tmp_aliases);
508     }
509   /* Dequeue */
510   DEQUEUE_ELEM(entry);
511   free(entry);
512   
513   return 0;
514 }
515
516
517 /**
518  *Print all multiple interface info
519  *For debuging purposes
520  */
521 void
522 olsr_print_mid_set(void)
523 {
524   int idx;
525
526   OLSR_PRINTF(1, "mid set: %02d:%02d:%02d.%06lu\n",nowtm->tm_hour, nowtm->tm_min, nowtm->tm_sec, now.tv_usec);
527
528   for(idx=0;idx<HASHSIZE;idx++)
529     {
530       struct mid_entry *tmp_list = mid_set[idx].next;
531       /*Traverse MID list*/
532       for(tmp_list = mid_set[idx].next; tmp_list != &mid_set[idx]; tmp_list = tmp_list->next)
533         {
534           struct mid_address *tmp_addr;
535           
536           OLSR_PRINTF(1, "%s: ", olsr_ip_to_string(&tmp_list->main_addr));
537           for(tmp_addr = tmp_list->aliases;tmp_addr;tmp_addr = tmp_addr->next_alias)
538             {
539               OLSR_PRINTF(1, " %s ", olsr_ip_to_string(&tmp_addr->alias));
540             }
541           OLSR_PRINTF(1, "\n");
542         }
543     }
544
545 }
546
547
548
549
550