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