Use real (bi-directional) ETX.
[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.20 2004/11/28 13:43:59 tlopatic 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   struct  neighbor_2_entry      *two_hop_entry;
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       two_hop_entry = two_hop_list->neighbor_2;
179       
180       two_hop_entry->neighbor_2_pointer--;
181
182       olsr_delete_neighbor_pointer(two_hop_entry, &entry->neighbor_main_addr);
183
184       /* Delete entry if it has no more one hop neighbors pointing to it */
185       if(two_hop_entry->neighbor_2_pointer < 1)
186         {
187           DEQUEUE_ELEM(two_hop_entry);
188
189           free(two_hop_entry);
190         }
191
192
193       two_hop_to_delete = two_hop_list;
194       two_hop_list = two_hop_list->next;
195       /* Delete entry */
196       free(two_hop_to_delete);
197       
198     }
199
200
201   /* Dequeue */
202   DEQUEUE_ELEM(entry);
203
204   free(entry);
205
206   changes_neighborhood = OLSR_TRUE;
207   return 1;
208
209 }
210
211
212
213 /**
214  *Insert a neighbor entry in the neighbor table
215  *
216  *@param main_addr the main address of the new node
217  *
218  *@return 0 if neighbor already exists 1 if inserted
219  */
220 struct neighbor_entry *
221 olsr_insert_neighbor_table(union olsr_ip_addr *main_addr)
222 {
223   olsr_u32_t             hash;
224   struct neighbor_entry  *new_neigh;
225   
226   hash = olsr_hashing(main_addr);
227
228   /* Check if entry exists */
229   
230   for(new_neigh = neighbortable[hash].next;
231       new_neigh != &neighbortable[hash];
232       new_neigh = new_neigh->next)
233     {
234       if(COMP_IP(&new_neigh->neighbor_main_addr, main_addr))
235         return new_neigh;
236     }
237   
238   //printf("inserting neighbor\n");
239   
240   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
241   
242   /* Set address, willingness and status */
243   COPY_IP(&new_neigh->neighbor_main_addr, main_addr);
244   new_neigh->willingness = WILL_NEVER;
245   new_neigh->status = NOT_SYM;
246
247   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
248   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
249   
250   new_neigh->linkcount = 0;
251   new_neigh->is_mpr = OLSR_FALSE;
252   new_neigh->was_mpr = OLSR_FALSE;
253
254   /* Queue */
255   QUEUE_ELEM(neighbortable[hash], new_neigh);
256
257   return new_neigh;
258 }
259
260
261
262 /**
263  *Lookup a neighbor entry in the neighbortable based on an address.
264  *
265  *@param dst the IP address of the neighbor to look up
266  *
267  *@return a pointer to the neighbor struct registered on the given 
268  *address. NULL if not found.
269  */
270 struct neighbor_entry *
271 olsr_lookup_neighbor_table(union olsr_ip_addr *dst)
272 {
273   struct neighbor_entry  *entry;
274   olsr_u32_t             hash;
275   //struct addresses       *adr;
276   union olsr_ip_addr     *tmp_ip;
277
278   /*
279    *Find main address of node
280    */
281   if((tmp_ip = mid_lookup_main_addr(dst)) != NULL)
282     dst = tmp_ip;
283   
284   hash = olsr_hashing(dst);
285
286   
287   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
288   for(entry = neighbortable[hash].next;
289       entry != &neighbortable[hash];
290       entry = entry->next)
291     {
292       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
293       if(COMP_IP(&entry->neighbor_main_addr, dst))
294         return entry;
295       
296     }
297   //printf("NOPE\n\n");
298
299   return NULL;
300
301 }
302
303
304 /**
305  *Lookup a neighbor entry in the neighbortable based on an address.
306  *
307  *@param dst the IP address of the neighbor to look up
308  *
309  *@return a pointer to the neighbor struct registered on the given 
310  *address. NULL if not found.
311  */
312 struct neighbor_entry *
313 olsr_lookup_neighbor_table_alias(union olsr_ip_addr *dst)
314 {
315   struct neighbor_entry  *entry;
316   olsr_u32_t             hash;
317   //struct addresses       *adr;
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(&neighbor_table_tmp->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   struct neighbor_2_entry *two_hop_neighbor;
344
345   /*
346    * Update neighbor entry
347    */
348  
349   if(link == SYM_LINK)
350     {
351       /* N_status is set to SYM */
352       if(entry->status == NOT_SYM)
353         {
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, *two_hop_to_delete;
399   struct  neighbor_2_entry      *two_hop_entry;
400
401
402   two_hop_list = neighbor->neighbor_2_list.next;
403
404   //neighbor->neighbor_2_list = NULL;
405
406   while(two_hop_list != &neighbor->neighbor_2_list)
407     {
408       if(TIMED_OUT(&two_hop_list->neighbor_2_timer))
409         {
410           two_hop_entry = two_hop_list->neighbor_2;
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               /* FIX THIS (fix what?)*/
417               DEQUEUE_ELEM(two_hop_entry);
418
419               free((void *)two_hop_entry);
420             }
421
422           two_hop_to_delete = two_hop_list;
423           two_hop_list = two_hop_list->next;
424
425           /* Dequeue */
426           DEQUEUE_ELEM(two_hop_to_delete);
427
428           free(two_hop_to_delete);
429
430           /* This flag is set to OLSR_TRUE to recalculate the MPR set and the routing table*/
431           changes_neighborhood = OLSR_TRUE;
432           changes_topology = OLSR_TRUE;
433           
434         }
435       else
436         two_hop_list = two_hop_list->next;
437
438     }
439 }
440
441
442
443
444
445 void
446 olsr_time_out_neighborhood_tables()
447 {
448   olsr_u8_t              index;
449   struct neighbor_entry  *entry;
450   
451   for(index=0;index<HASHSIZE;index++)
452     {
453       entry = neighbortable[index].next;
454
455       while(entry != &neighbortable[index])
456         {         
457           olsr_time_out_two_hop_neighbors(entry);
458
459           entry = entry->next;
460         }
461     }
462 }
463
464
465
466
467
468 /**
469  *Prints the registered neighbors and two hop neighbors
470  *to STDOUT.
471  *
472  *@return nada
473  */
474 void
475 olsr_print_neighbor_table()
476 {
477   int i;
478   struct neighbor_entry *neigh;
479 #if defined USE_LINK_QUALITY
480   struct link_entry *link;
481 #endif
482   double best_lq, inv_best_lq;
483   char *fstr;
484
485   olsr_printf(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n",
486               nowtm->tm_hour,
487               nowtm->tm_min,
488               nowtm->tm_sec,
489               now.tv_usec/10000);
490
491   if (olsr_cnf->ip_version == AF_INET)
492   {
493     olsr_printf(1, "IP address       LQ     NLQ    SYM   MPR   MPRS  will\n");
494     fstr = "%-15s  %5.3f  %5.3f  %s  %s  %s  %d\n";
495   }
496
497   else
498   {
499     olsr_printf(1, "IP address                               LQ     NLQ    SYM   MPR   MPRS  will\n");
500     fstr = "%-39s  %5.3f  %5.3f  %s  %s  %s  %d\n";
501   }
502
503   for (i = 0; i < HASHSIZE; i++)
504     {
505       for(neigh = neighbortable[i].next; neigh != &neighbortable[i];
506           neigh = neigh->next)
507         {
508 #if defined USE_LINK_QUALITY
509           link = olsr_neighbor_best_link(&neigh->neighbor_main_addr);
510
511           best_lq = link->neigh_link_quality;
512           inv_best_lq = link->loss_link_quality;
513 #else
514           best_lq = 0.0;
515           inv_best_lq = 0.0;
516 #endif
517
518           olsr_printf(1, fstr, olsr_ip_to_string(&neigh->neighbor_main_addr),
519                       inv_best_lq, best_lq,
520                       (neigh->status == SYM) ? "YES " : "NO  ",
521                       neigh->is_mpr ? "YES " : "NO  ", 
522                       olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
523                       neigh->willingness);
524         }
525     }
526 }
527
528
529
530
531
532
533
534
535
536