0dd26461f09de73f7a4adbbcf13523b932172911
[olsrd.git] / src / neighbor_table.c
1 /*
2  * OLSR ad-hoc routing table management protocol
3  * Copyright (C) 2003 Andreas Tønnesen (andreto@ifi.uio.no)
4  *
5  * This file is part of the olsr.org OLSR daemon.
6  *
7  * olsr.org is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * olsr.org is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with olsr.org; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20  * 
21  * 
22  * $ Id $
23  *
24  */
25
26
27
28
29 #include "defs.h"
30 #include "two_hop_neighbor_table.h"
31 #include "mid_set.h"
32 #include "mpr.h"
33 #include "olsr.h"
34 #include "scheduler.h"
35
36 void
37 olsr_init_neighbor_table()
38 {
39   int i;
40
41   olsr_register_timeout_function(&olsr_time_out_neighborhood_tables);
42
43   for(i = 0; i < HASHSIZE; i++)
44     {
45       neighbortable[i].next = &neighbortable[i];
46       neighbortable[i].prev = &neighbortable[i];
47     }
48 }
49
50
51 /**
52  *Delete a two hop neighbor from a neighbors two 
53  *hop neighbor list.
54  *
55  *@param neighbor the neighbor to delete the two hop 
56  *neighbor from.
57  *@param address the IP address of the two hop neighbor 
58  *to delete.
59  *
60  *@return positive if entry deleted
61  */
62 int
63 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, union olsr_ip_addr *address)
64 {
65
66   struct neighbor_2_list_entry *entry;
67   
68   entry = neighbor->neighbor_2_list.next;
69
70   while(entry != &neighbor->neighbor_2_list)
71     {
72       
73       if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, address))
74         {
75           /* Dequeue */
76           DEQUEUE_ELEM(entry);
77           /* Delete */
78           free(entry);
79           return 1;       
80         }
81       entry = entry->next;      
82     }
83   return 0;
84 }
85
86
87 /**
88  *Check if a two hop neighbor is reachable via a given
89  *neighbor.
90  *
91  *@param neighbor neighbor-entry to check via
92  *@param neighbor_main_address the addres of the two hop neighbor 
93  *to find.
94  *
95  *@return a pointer to the neighbor_2_list_entry struct
96  *representing the two hop neighbor if found. NULL if not found.
97  */
98 struct neighbor_2_list_entry *
99 olsr_lookup_my_neighbors(struct neighbor_entry *neighbor, union olsr_ip_addr *neighbor_main_address)
100 {
101   
102   struct neighbor_2_list_entry *entry;
103   
104   for(entry = neighbor->neighbor_2_list.next;
105       entry != &neighbor->neighbor_2_list;
106       entry = entry->next)
107     {
108       
109       if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
110         return entry;
111       
112     }
113   return NULL;
114 }
115
116
117
118 /**
119  *Delete a neighbr table entry.
120  *
121  *Remember: Deleting a neighbor entry results 
122  *the deletion of its 2 hop neighbors list!!!
123  *@param neighbor the neighbor entry to delete
124  *
125  *@return nada
126  */
127
128 int
129 olsr_delete_neighbor_table(union olsr_ip_addr *neighbor_addr)
130 {  
131   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
132   struct  neighbor_2_entry      *two_hop_entry;
133   olsr_u32_t                    hash;
134   struct neighbor_entry         *entry;
135
136   //printf("inserting neighbor\n");
137
138   hash = olsr_hashing(neighbor_addr);
139
140   entry = neighbortable[hash].next;
141
142   /*
143    * Find neighbor entry
144    */
145   while(entry != &neighbortable[hash])
146     {
147       if(COMP_IP(&entry->neighbor_main_addr, neighbor_addr))
148         break;
149       
150       entry = entry->next;
151     }
152
153   if(entry == &neighbortable[hash])
154     return 0;
155
156
157   two_hop_list = entry->neighbor_2_list.next;
158
159   while(two_hop_list != &entry->neighbor_2_list)
160     {
161       two_hop_entry = two_hop_list->neighbor_2;
162       
163       two_hop_entry->neighbor_2_pointer--;
164
165       olsr_delete_neighbor_pointer(two_hop_entry, &entry->neighbor_main_addr);
166
167       /* Delete entry if it has no more one hop neighbors pointing to it */
168       if(two_hop_entry->neighbor_2_pointer < 1)
169         {
170           DEQUEUE_ELEM(two_hop_entry);
171
172           free(two_hop_entry);
173         }
174
175
176       two_hop_to_delete = two_hop_list;
177       two_hop_list = two_hop_list->next;
178       /* Delete entry */
179       free(two_hop_to_delete);
180       
181     }
182
183
184   /* Dequeue */
185   DEQUEUE_ELEM(entry);
186
187   free(entry);
188
189   changes_neighborhood = UP;
190   return 1;
191
192 }
193
194
195
196 /**
197  *Insert a neighbor entry in the neighbor table
198  *
199  *@param main_addr the main address of the new node
200  *
201  *@return 0 if neighbor already exists 1 if inserted
202  */
203 struct neighbor_entry *
204 olsr_insert_neighbor_table(union olsr_ip_addr *main_addr)
205 {
206   olsr_u32_t             hash;
207   struct neighbor_entry  *new_neigh;
208   
209   hash = olsr_hashing(main_addr);
210
211   /* Check if entry exists */
212   
213   for(new_neigh = neighbortable[hash].next;
214       new_neigh != &neighbortable[hash];
215       new_neigh = new_neigh->next)
216     {
217       if(COMP_IP(&new_neigh->neighbor_main_addr, main_addr))
218         return new_neigh;
219     }
220   
221   //printf("inserting neighbor\n");
222   
223   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
224   
225   /* Set address, willingness and status */
226   COPY_IP(&new_neigh->neighbor_main_addr, main_addr);
227   new_neigh->willingness = WILL_NEVER;
228   new_neigh->status = NOT_SYM;
229
230   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
231   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
232   
233   new_neigh->linkcount = 0;
234   new_neigh->is_mpr = 0;
235   new_neigh->was_mpr = 0;
236
237   /* Queue */
238   QUEUE_ELEM(neighbortable[hash], new_neigh);
239
240   return new_neigh;
241 }
242
243
244
245 /**
246  *Lookup a neighbor entry in the neighbortable based on an address.
247  *
248  *@param dst the IP address of the neighbor to look up
249  *
250  *@return a pointer to the neighbor struct registered on the given 
251  *address. NULL if not found.
252  */
253 struct neighbor_entry *
254 olsr_lookup_neighbor_table(union olsr_ip_addr *dst)
255 {
256   struct neighbor_entry  *entry;
257   olsr_u32_t             hash;
258   //struct addresses       *adr;
259   union olsr_ip_addr     *tmp_ip;
260
261   /*
262    *Find main address of node
263    */
264   if((tmp_ip = mid_lookup_main_addr(dst)) != NULL)
265     dst = tmp_ip;
266   
267   hash = olsr_hashing(dst);
268
269   
270   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
271   for(entry = neighbortable[hash].next;
272       entry != &neighbortable[hash];
273       entry = entry->next)
274     {
275       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
276       if(COMP_IP(&entry->neighbor_main_addr, dst))
277         return entry;
278       
279     }
280   //printf("NOPE\n\n");
281
282   return NULL;
283
284 }
285
286
287 /**
288  *Lookup a neighbor entry in the neighbortable based on an address.
289  *
290  *@param dst the IP address of the neighbor to look up
291  *
292  *@return a pointer to the neighbor struct registered on the given 
293  *address. NULL if not found.
294  */
295 struct neighbor_entry *
296 olsr_lookup_neighbor_table_alias(union olsr_ip_addr *dst)
297 {
298   struct neighbor_entry  *entry;
299   olsr_u32_t             hash;
300   //struct addresses       *adr;
301   
302   hash = olsr_hashing(dst);
303
304   
305   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
306   for(entry = neighbortable[hash].next;
307       entry != &neighbortable[hash];
308       entry = entry->next)
309     {
310       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
311       if(COMP_IP(&entry->neighbor_main_addr, dst))
312         return entry;
313       
314     }
315   //printf("NOPE\n\n");
316
317   return NULL;
318
319 }
320
321
322
323 int
324 update_neighbor_status(struct neighbor_entry *entry, int link)
325 {
326   struct neighbor_2_entry *two_hop_neighbor;
327
328   /*
329    * Update neighbor entry
330    */
331  
332   if(link == SYM_LINK)
333     {
334       /* N_status is set to SYM */
335       if(entry->status == NOT_SYM)
336         {
337           
338           /* Delete posible 2 hop entry on this neighbor */
339           if((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr))!=NULL)
340             {
341               olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
342             }
343   
344           changes_neighborhood = UP;
345           changes_topology = UP;
346           if(tc_redundancy > 1)
347             changes = UP;
348         }
349       entry->status = SYM;
350     }
351   else
352     {
353       if(entry->status == SYM)
354         {
355           changes_neighborhood = UP;
356           changes_topology = UP;
357           if(tc_redundancy > 1)
358             changes = UP;
359         }
360       /* else N_status is set to NOT_SYM */
361       entry->status = NOT_SYM;
362       /* remove neighbor from routing list */
363     }
364
365   return entry->status;
366 }
367
368
369
370 /**
371  *Times out the entries in the two hop neighbor table and 
372  *deletes those who have exceeded their time to live since 
373  *last update.
374  *
375  *@return nada
376  */
377
378 void
379 olsr_time_out_two_hop_neighbors(struct neighbor_entry  *neighbor)
380 {
381   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
382   struct  neighbor_2_entry      *two_hop_entry;
383
384
385   two_hop_list = neighbor->neighbor_2_list.next;
386
387   //neighbor->neighbor_2_list = NULL;
388
389   while(two_hop_list != &neighbor->neighbor_2_list)
390     {
391       if(TIMED_OUT(&two_hop_list->neighbor_2_timer))
392         {
393           two_hop_entry = two_hop_list->neighbor_2;
394           two_hop_entry->neighbor_2_pointer--;
395           olsr_delete_neighbor_pointer(two_hop_entry, &neighbor->neighbor_main_addr);
396
397           if(two_hop_entry->neighbor_2_pointer < 1)
398             {
399               /* FIX THIS (fix what?)*/
400               DEQUEUE_ELEM(two_hop_entry);
401
402               free((void *)two_hop_entry);
403             }
404
405           two_hop_to_delete = two_hop_list;
406           two_hop_list = two_hop_list->next;
407
408           /* Dequeue */
409           DEQUEUE_ELEM(two_hop_to_delete);
410
411           free(two_hop_to_delete);
412
413           /* This flag is set to UP to recalculate the MPR set and the routing table*/
414           changes_neighborhood=UP;
415           changes_topology=UP;
416           
417         }
418       else
419         two_hop_list = two_hop_list->next;
420
421     }
422 }
423
424
425
426
427
428 void
429 olsr_time_out_neighborhood_tables()
430 {
431   olsr_u8_t              index;
432   struct neighbor_entry  *entry;
433   
434   for(index=0;index<HASHSIZE;index++)
435     {
436       entry = neighbortable[index].next;
437
438       while(entry != &neighbortable[index])
439         {         
440           olsr_time_out_two_hop_neighbors(entry);
441
442           entry = entry->next;
443         }
444     }
445 }
446
447
448
449
450
451 /**
452  *Prints the registered neighbors and two hop neighbors
453  *to STDOUT.
454  *
455  *@return nada
456  */
457 void
458 olsr_print_neighbor_table()
459 {
460   olsr_u8_t                    index;
461   struct neighbor_entry        *neighbor_table_tmp;
462   struct neighbor_2_list_entry *list_2;
463
464
465
466   olsr_printf(1, "Neighbor list(%02d:%02d:%02d.%06lu):\n", 
467               nowtm->tm_hour, 
468               nowtm->tm_min, 
469               nowtm->tm_sec, 
470               now.tv_usec);
471
472   for(index=0;index<HASHSIZE;index++)
473     {
474     
475       for(neighbor_table_tmp = neighbortable[index].next;
476           neighbor_table_tmp != &neighbortable[index];
477           neighbor_table_tmp = neighbor_table_tmp->next)
478         {
479           olsr_printf(1, "%s:l=%d:m=%d:w=%d[2hlist:", 
480                       olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr),
481                       neighbor_table_tmp->status, neighbor_table_tmp->is_mpr, neighbor_table_tmp->willingness);
482
483           for(list_2 = neighbor_table_tmp->neighbor_2_list.next;
484               list_2 != &neighbor_table_tmp->neighbor_2_list;
485               list_2 = list_2->next)
486             {
487               olsr_printf(1, "%s:", olsr_ip_to_string(&list_2->neighbor_2->neighbor_2_addr));
488             }
489           olsr_printf(1, "]\n");
490
491         }
492     }
493 }
494
495
496
497
498
499
500
501
502
503