d3528eaa19c63382c78b0a4befe99fdf16a46370
[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.11 2005/01/17 20:18:21 kattemat 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
50 /**
51  * Initialize the MID set
52  *
53  */
54
55 int
56 olsr_init_mid_set()
57 {
58   int index;
59
60   olsr_printf(5, "MID: init\n");
61
62   /* Since the holdingtime is assumed to be rather large for 
63    * MID entries, the timeoutfunction is only ran once every second
64    */
65   olsr_register_scheduler_event(&olsr_time_out_mid_set, NULL, 1, 0, NULL);
66
67   for(index=0;index<HASHSIZE;index++)
68     {
69       mid_set[index].next = &mid_set[index];
70       mid_set[index].prev = &mid_set[index];
71     }
72
73   return 1;
74 }
75
76
77 /**
78  *Insert a new interface alias to the interface association set.
79  *If the main interface of the association is not yet registered
80  *in the set a new entry is created.
81  *
82  *@param m_addr the main address of the node
83  *@param alias the alias address to insert
84  *
85  *@return nada
86  */
87
88 void 
89 insert_mid_tuple(union olsr_ip_addr *m_addr, struct addresses *alias, float vtime)
90 {
91   struct mid_entry *tmp;
92   struct addresses *tmp_adr;
93   olsr_u32_t hash;
94
95   hash = olsr_hashing(m_addr);
96
97   /* Check for registered entry */
98   for(tmp = mid_set[hash].next;
99       tmp != &mid_set[hash];
100       tmp = tmp->next)
101     {
102       if(COMP_IP(&tmp->main_addr, m_addr))
103         break;
104     }
105          
106   /*If the address was registered*/ 
107   if(tmp != &mid_set[hash])
108     {
109       tmp_adr = tmp->aliases;
110       tmp->aliases = alias;
111       alias->next = tmp_adr;
112       tmp->ass_timer = GET_TIMESTAMP(vtime*1000);
113     }
114       /*Create new node*/
115   else
116     {
117       tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
118
119       tmp->aliases = alias;
120       COPY_IP(&tmp->main_addr, m_addr);
121       tmp->ass_timer = GET_TIMESTAMP(vtime*1000);
122       /* Queue */
123       QUEUE_ELEM(mid_set[hash], tmp);
124       /*
125       tmp->next = mid_set[hash].next;
126       tmp->prev = &mid_set[hash];
127       mid_set[hash].next->prev = tmp;
128       mid_set[hash].next = tmp;
129       */
130     }
131   
132
133
134   /*
135    * Delete possible duplicate entries in 2 hop set
136    * and delete duplicate neighbor entries. Redirect
137    * link entries to the correct neighbor entry.
138    *
139    *THIS OPTIMIZATION IS NOT SPECIFIED IN RFC3626
140    */
141
142   tmp_adr = alias;
143
144   while(tmp_adr)
145     {
146       struct neighbor_2_entry *tmp_2_neighbor;
147       struct neighbor_entry *tmp_neigh, *real_neigh;
148
149       /* Delete possible 2 hop neighbor */
150       if((tmp_2_neighbor = olsr_lookup_two_hop_neighbor_table_mid(&tmp_adr->address)) != NULL)
151         {
152           olsr_printf(1, "Deleting 2 hop node from MID: %s to ", olsr_ip_to_string(&tmp_adr->address));
153           olsr_printf(1, "%s\n", olsr_ip_to_string(m_addr));
154
155           olsr_delete_two_hop_neighbor_table(tmp_2_neighbor);
156
157           changes_neighborhood = OLSR_TRUE;
158         }
159
160       /* Delete a possible neighbor entry */
161       if(((tmp_neigh = olsr_lookup_neighbor_table_alias(&tmp_adr->address)) != NULL)
162          && ((real_neigh = olsr_lookup_neighbor_table_alias(m_addr)) != NULL))
163
164         {
165           olsr_printf(1, "[MID]Deleting bogus neighbor entry %s real ", olsr_ip_to_string(&tmp_adr->address));
166           olsr_printf(1, "%s\n", olsr_ip_to_string(m_addr));
167
168           replace_neighbor_link_set(tmp_neigh, real_neigh);
169
170           /* Dequeue */
171           DEQUEUE_ELEM(tmp_neigh);
172           /* Delete */
173           free(tmp_neigh);
174
175           changes_neighborhood = OLSR_TRUE;
176         }
177       
178       tmp_adr = tmp_adr->next;
179     }
180
181
182 }
183
184
185 /**
186  *Insert an alias address for a node.
187  *If the main address is not registered
188  *then a new entry is created.
189  *
190  *@param main_add the main address of the node
191  *@param alias the alias address to insert
192  *@param seq the sequence number to register a new node with
193  *
194  *@return nada
195  */
196 void
197 insert_mid_alias(union olsr_ip_addr *main_add, union olsr_ip_addr *alias, float vtime)
198 {
199   struct addresses *adr;
200
201   adr = olsr_malloc(sizeof(struct addresses), "Insert MID alias");
202
203   olsr_printf(1, "Inserting alias %s for ", olsr_ip_to_string(alias));
204   olsr_printf(1, "%s\n", olsr_ip_to_string(main_add));
205
206   COPY_IP(&adr->address, alias);
207   adr->next = NULL;
208
209   insert_mid_tuple(main_add, adr, vtime);
210
211   /*
212    *Recalculate topology
213    */
214   changes_neighborhood = OLSR_TRUE;
215   changes_topology = OLSR_TRUE;
216
217   //print_mid_list();
218 }
219
220
221
222
223 /**
224  *Lookup the main address for a alias address
225  *
226  *@param adr the alias address to check
227  *
228  *@return the main address registered on the alias
229  *or NULL if not found
230  */
231 union olsr_ip_addr *
232 mid_lookup_main_addr(union olsr_ip_addr *adr)
233 {
234   int index;
235
236   for(index=0;index<HASHSIZE;index++)
237     {
238       struct mid_entry *tmp_list = mid_set[index].next;
239       /*Traverse MID list*/
240       while(tmp_list != &mid_set[index])
241         {
242           struct addresses *tmp_addr;
243
244           if(COMP_IP(&tmp_list->main_addr, adr))
245             return NULL;
246
247           tmp_addr = tmp_list->aliases;
248           /*And all aliases registered on them*/
249           while(tmp_addr)
250             {
251               if(COMP_IP(&tmp_addr->address, adr))
252                 return &tmp_list->main_addr;
253               tmp_addr = tmp_addr->next;
254             }
255
256           tmp_list = tmp_list->next;
257         }
258     }
259   return NULL;
260
261 }
262
263
264
265
266 /*
267  *Find all aliases for an address.
268  *
269  *@param adr the main address to search for
270  *
271  *@return a linked list of addresses structs
272  */
273 struct addresses *
274 mid_lookup_aliases(union olsr_ip_addr *adr)
275 {
276   struct mid_entry *tmp_list;
277   olsr_u32_t hash;
278
279   //olsr_printf(1, "MID: lookup entry...");
280
281   hash = olsr_hashing(adr);
282
283   /* Check all registered nodes...*/
284   for(tmp_list = mid_set[hash].next;
285       tmp_list != &mid_set[hash];
286       tmp_list = tmp_list->next)
287     {
288       if(COMP_IP(&tmp_list->main_addr, adr))
289         return tmp_list->aliases;
290     }
291
292
293   return NULL;
294 }
295
296
297 /**
298  *Update the timer for an entry
299  *
300  *@param adr the main address of the entry
301  *
302  *@return 1 if the node was updated, 0 if not
303  */
304 int
305 olsr_update_mid_table(union olsr_ip_addr *adr, float vtime)
306 {
307   struct mid_entry *tmp_list = mid_set;
308   olsr_u32_t hash;
309
310   olsr_printf(3, "MID: update %s\n", olsr_ip_to_string(adr));
311   hash = olsr_hashing(adr);
312
313   /* Check all registered nodes...*/
314   for(tmp_list = mid_set[hash].next;
315       tmp_list != &mid_set[hash];
316       tmp_list = tmp_list->next)
317     {
318       /*find match*/
319       if(COMP_IP(&tmp_list->main_addr, adr))
320         {
321           //printf("Updating timer for node %s\n",ip_to_string(&tmp_list->main_addr));
322           tmp_list->ass_timer = GET_TIMESTAMP(vtime*1000);
323
324           return 1;
325         }
326     }
327   return 0;
328 }
329
330
331
332 /**
333  *Find timed out entries and delete them
334  *
335  *@return nada
336  */
337 void
338 olsr_time_out_mid_set(void *foo)
339 {
340   int index;
341
342
343   for(index=0;index<HASHSIZE;index++)
344     {
345       struct mid_entry *tmp_list = mid_set[index].next;
346       /*Traverse MID list*/
347       while(tmp_list != &mid_set[index])
348         {
349           /*Check if the entry is timed out*/
350           if(TIMED_OUT(tmp_list->ass_timer))
351             {
352               struct mid_entry *entry_to_delete = tmp_list;
353               tmp_list = tmp_list->next;
354 #ifdef DEBUG
355               olsr_printf(1, "MID info for %s timed out.. deleting it\n", 
356                           olsr_ip_to_string(&entry_to_delete->main_addr));
357 #endif
358               /*Delete it*/
359               mid_delete_node(entry_to_delete);
360             }
361           else
362               tmp_list = tmp_list->next;
363         }
364     }
365
366   return;
367 }
368
369
370 /*
371  *Delete an entry
372  *
373  *@param entry the entry to delete
374  *
375  *@return 1
376  */
377 int
378 mid_delete_node(struct mid_entry *entry)
379 {
380   struct addresses *aliases;
381
382   /* Free aliases */
383   aliases = entry->aliases;
384   while(aliases)
385     {
386       struct addresses *tmp_aliases = aliases;
387       aliases = aliases->next;
388       free(tmp_aliases);
389     }
390   /* Dequeue */
391   DEQUEUE_ELEM(entry);
392   free(entry);
393   
394   return 0;
395 }
396
397
398 /**
399  *Print all multiple interface info
400  *For debuging purposes
401  */
402 void
403 olsr_print_mid_set()
404 {
405
406   int index;
407
408   olsr_printf(1, "mid set: %02d:%02d:%02d.%06lu\n",nowtm->tm_hour, nowtm->tm_min, nowtm->tm_sec, now.tv_usec);
409
410   for(index=0;index<HASHSIZE;index++)
411     {
412       struct mid_entry *tmp_list = mid_set[index].next;
413       /*Traverse MID list*/
414       for(tmp_list = mid_set[index].next;
415           tmp_list != &mid_set[index];
416           tmp_list = tmp_list->next)
417         {
418           struct addresses *tmp_addr = tmp_list->aliases;
419
420           olsr_printf(1, "%s: ", olsr_ip_to_string(&tmp_list->main_addr));        
421           while(tmp_addr)
422             {
423               olsr_printf(1, " %s ", olsr_ip_to_string(&tmp_addr->address));
424               tmp_addr = tmp_addr->next;
425             }
426           olsr_printf(1, "\n");
427           
428         }
429     }
430
431 }
432
433
434
435
436