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