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