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