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