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