38b5a07510a0b4d4cb02cf60568ef68aa1efca46
[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.24 2005/01/22 00:09: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 "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   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   
318   hash = olsr_hashing(dst);
319
320   
321   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
322   for(entry = neighbortable[hash].next;
323       entry != &neighbortable[hash];
324       entry = entry->next)
325     {
326       //printf("Checking %s\n", olsr_ip_to_string(&entry->neighbor_main_addr));
327       if(COMP_IP(&entry->neighbor_main_addr, dst))
328         return entry;
329       
330     }
331   //printf("NOPE\n\n");
332
333   return NULL;
334
335 }
336
337
338
339 int
340 update_neighbor_status(struct neighbor_entry *entry, int link)
341 {
342   /*
343    * Update neighbor entry
344    */
345  
346   if(link == SYM_LINK)
347     {
348       /* N_status is set to SYM */
349       if(entry->status == NOT_SYM)
350         {
351           struct neighbor_2_entry *two_hop_neighbor;
352           
353           /* Delete posible 2 hop entry on this neighbor */
354           if((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr))!=NULL)
355             {
356               olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
357             }
358   
359           changes_neighborhood = OLSR_TRUE;
360           changes_topology = OLSR_TRUE;
361           if(olsr_cnf->tc_redundancy > 1)
362             changes = OLSR_TRUE;
363         }
364       entry->status = SYM;
365     }
366   else
367     {
368       if(entry->status == SYM)
369         {
370           changes_neighborhood = OLSR_TRUE;
371           changes_topology = OLSR_TRUE;
372           if(olsr_cnf->tc_redundancy > 1)
373             changes = OLSR_TRUE;
374         }
375       /* else N_status is set to NOT_SYM */
376       entry->status = NOT_SYM;
377       /* remove neighbor from routing list */
378     }
379
380   return entry->status;
381 }
382
383
384
385 /**
386  *Times out the entries in the two hop neighbor table and 
387  *deletes those who have exceeded their time to live since 
388  *last update.
389  *
390  *@return nada
391  */
392
393 void
394 olsr_time_out_two_hop_neighbors(struct neighbor_entry  *neighbor)
395 {
396   struct neighbor_2_list_entry *two_hop_list;
397
398   two_hop_list = neighbor->neighbor_2_list.next;
399
400   while(two_hop_list != &neighbor->neighbor_2_list)
401     {
402       if(TIMED_OUT(two_hop_list->neighbor_2_timer))
403         {
404           struct neighbor_2_list_entry *two_hop_to_delete;
405           struct neighbor_2_entry      *two_hop_entry = two_hop_list->neighbor_2;
406
407           two_hop_entry->neighbor_2_pointer--;
408           olsr_delete_neighbor_pointer(two_hop_entry, &neighbor->neighbor_main_addr);
409           
410           if(two_hop_entry->neighbor_2_pointer < 1)
411             {
412               DEQUEUE_ELEM(two_hop_entry);
413               free((void *)two_hop_entry);
414             }
415           
416           two_hop_to_delete = two_hop_list;
417           two_hop_list = two_hop_list->next;
418           
419           /* Dequeue */
420           DEQUEUE_ELEM(two_hop_to_delete);
421           
422           free(two_hop_to_delete);
423
424           /* This flag is set to OLSR_TRUE to recalculate the MPR set and the routing table*/
425           changes_neighborhood = OLSR_TRUE;
426           changes_topology = OLSR_TRUE;
427           
428         }
429       else
430         two_hop_list = two_hop_list->next;
431
432     }
433 }
434
435
436
437
438
439 void
440 olsr_time_out_neighborhood_tables()
441 {
442   olsr_u8_t              index;
443   
444   for(index=0;index<HASHSIZE;index++)
445     {
446       struct neighbor_entry *entry = neighbortable[index].next;
447
448       while(entry != &neighbortable[index])
449         {         
450           olsr_time_out_two_hop_neighbors(entry);
451           entry = entry->next;
452         }
453     }
454 }
455
456
457
458
459
460 /**
461  *Prints the registered neighbors and two hop neighbors
462  *to STDOUT.
463  *
464  *@return nada
465  */
466 void
467 olsr_print_neighbor_table()
468 {
469   int i;
470   char *fstr;
471
472   olsr_printf(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n",
473               nowtm->tm_hour,
474               nowtm->tm_min,
475               nowtm->tm_sec,
476               now.tv_usec/10000);
477
478   if (olsr_cnf->ip_version == AF_INET)
479   {
480     olsr_printf(1, "IP address       LQ     NLQ    SYM   MPR   MPRS  will\n");
481     fstr = "%-15s  %5.3f  %5.3f  %s  %s  %s  %d\n";
482   }
483
484   else
485   {
486     olsr_printf(1, "IP address                               LQ     NLQ    SYM   MPR   MPRS  will\n");
487     fstr = "%-39s  %5.3f  %5.3f  %s  %s  %s  %d\n";
488   }
489
490   for (i = 0; i < HASHSIZE; i++)
491     {
492       struct neighbor_entry *neigh;
493       for(neigh = neighbortable[i].next; neigh != &neighbortable[i];
494           neigh = neigh->next)
495         {
496           struct link_entry *link = olsr_neighbor_best_link(&neigh->neighbor_main_addr);
497           double best_lq = link->neigh_link_quality;
498           double inv_best_lq = link->loss_link_quality;
499
500           olsr_printf(1, fstr, olsr_ip_to_string(&neigh->neighbor_main_addr),
501                       inv_best_lq, best_lq,
502                       (neigh->status == SYM) ? "YES " : "NO  ",
503                       neigh->is_mpr ? "YES " : "NO  ", 
504                       olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
505                       neigh->willingness);
506         }
507     }
508 }
509
510
511
512
513
514
515
516
517
518