olsr_ip_to_string() now only overwrites the buffer after four ivocations.
[olsrd.git] / src / neighbor_table.c
1 /*
2  * OLSR ad-hoc routing table management protocol
3  * Copyright (C) 2003 Andreas T√łnnesen (andreto@ifi.uio.no)
4  *
5  * This file is part of the olsr.org OLSR daemon.
6  *
7  * olsr.org is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * olsr.org is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with olsr.org; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20  * 
21  * 
22  * $Id: neighbor_table.c,v 1.16 2004/11/15 14:59:39 tlopatic Exp $
23  *
24  */
25
26
27
28
29 #include "defs.h"
30 #include "two_hop_neighbor_table.h"
31 #include "mid_set.h"
32 #include "mpr.h"
33 #include "olsr.h"
34 #include "scheduler.h"
35 #include "link_set.h"
36
37 void
38 olsr_init_neighbor_table()
39 {
40   int i;
41
42   olsr_register_timeout_function(&olsr_time_out_neighborhood_tables);
43
44   for(i = 0; i < HASHSIZE; i++)
45     {
46       neighbortable[i].next = &neighbortable[i];
47       neighbortable[i].prev = &neighbortable[i];
48     }
49 }
50
51
52 /**
53  *Delete a two hop neighbor from a neighbors two 
54  *hop neighbor list.
55  *
56  *@param neighbor the neighbor to delete the two hop 
57  *neighbor from.
58  *@param address the IP address of the two hop neighbor 
59  *to delete.
60  *
61  *@return positive if entry deleted
62  */
63 int
64 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, union olsr_ip_addr *address)
65 {
66
67   struct neighbor_2_list_entry *entry;
68   
69   entry = neighbor->neighbor_2_list.next;
70
71   while(entry != &neighbor->neighbor_2_list)
72     {
73       
74       if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, address))
75         {
76           /* Dequeue */
77           DEQUEUE_ELEM(entry);
78           /* Delete */
79           free(entry);
80           return 1;       
81         }
82       entry = entry->next;      
83     }
84   return 0;
85 }
86
87
88 /**
89  *Check if a two hop neighbor is reachable via a given
90  *neighbor.
91  *
92  *@param neighbor neighbor-entry to check via
93  *@param neighbor_main_address the addres of the two hop neighbor 
94  *to find.
95  *
96  *@return a pointer to the neighbor_2_list_entry struct
97  *representing the two hop neighbor if found. NULL if not found.
98  */
99 struct neighbor_2_list_entry *
100 olsr_lookup_my_neighbors(struct neighbor_entry *neighbor, union olsr_ip_addr *neighbor_main_address)
101 {
102   
103   struct neighbor_2_list_entry *entry;
104   
105   for(entry = neighbor->neighbor_2_list.next;
106       entry != &neighbor->neighbor_2_list;
107       entry = entry->next)
108     {
109       
110       if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
111         return entry;
112       
113     }
114   return NULL;
115 }
116
117
118
119 /**
120  *Delete a neighbr table entry.
121  *
122  *Remember: Deleting a neighbor entry results 
123  *the deletion of its 2 hop neighbors list!!!
124  *@param neighbor the neighbor entry to delete
125  *
126  *@return nada
127  */
128
129 int
130 olsr_delete_neighbor_table(union olsr_ip_addr *neighbor_addr)
131 {  
132   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
133   struct  neighbor_2_entry      *two_hop_entry;
134   olsr_u32_t                    hash;
135   struct neighbor_entry         *entry;
136
137   //printf("inserting neighbor\n");
138
139   hash = olsr_hashing(neighbor_addr);
140
141   entry = neighbortable[hash].next;
142
143   /*
144    * Find neighbor entry
145    */
146   while(entry != &neighbortable[hash])
147     {
148       if(COMP_IP(&entry->neighbor_main_addr, neighbor_addr))
149         break;
150       
151       entry = entry->next;
152     }
153
154   if(entry == &neighbortable[hash])
155     return 0;
156
157
158   two_hop_list = entry->neighbor_2_list.next;
159
160   while(two_hop_list != &entry->neighbor_2_list)
161     {
162       two_hop_entry = two_hop_list->neighbor_2;
163       
164       two_hop_entry->neighbor_2_pointer--;
165
166       olsr_delete_neighbor_pointer(two_hop_entry, &entry->neighbor_main_addr);
167
168       /* Delete entry if it has no more one hop neighbors pointing to it */
169       if(two_hop_entry->neighbor_2_pointer < 1)
170         {
171           DEQUEUE_ELEM(two_hop_entry);
172
173           free(two_hop_entry);
174         }
175
176
177       two_hop_to_delete = two_hop_list;
178       two_hop_list = two_hop_list->next;
179       /* Delete entry */
180       free(two_hop_to_delete);
181       
182     }
183
184
185   /* Dequeue */
186   DEQUEUE_ELEM(entry);
187
188   free(entry);
189
190   changes_neighborhood = OLSR_TRUE;
191   return 1;
192
193 }
194
195
196
197 /**
198  *Insert a neighbor entry in the neighbor table
199  *
200  *@param main_addr the main address of the new node
201  *
202  *@return 0 if neighbor already exists 1 if inserted
203  */
204 struct neighbor_entry *
205 olsr_insert_neighbor_table(union olsr_ip_addr *main_addr)
206 {
207   olsr_u32_t             hash;
208   struct neighbor_entry  *new_neigh;
209   
210   hash = olsr_hashing(main_addr);
211
212   /* Check if entry exists */
213   
214   for(new_neigh = neighbortable[hash].next;
215       new_neigh != &neighbortable[hash];
216       new_neigh = new_neigh->next)
217     {
218       if(COMP_IP(&new_neigh->neighbor_main_addr, main_addr))
219         return new_neigh;
220     }
221   
222   //printf("inserting neighbor\n");
223   
224   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
225   
226   /* Set address, willingness and status */
227   COPY_IP(&new_neigh->neighbor_main_addr, main_addr);
228   new_neigh->willingness = WILL_NEVER;
229   new_neigh->status = NOT_SYM;
230
231   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
232   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
233   
234   new_neigh->linkcount = 0;
235   new_neigh->is_mpr = OLSR_FALSE;
236   new_neigh->was_mpr = OLSR_FALSE;
237
238   /* Queue */
239   QUEUE_ELEM(neighbortable[hash], new_neigh);
240
241   return new_neigh;
242 }
243
244
245
246 /**
247  *Lookup a neighbor entry in the neighbortable based on an address.
248  *
249  *@param dst the IP address of the neighbor to look up
250  *
251  *@return a pointer to the neighbor struct registered on the given 
252  *address. NULL if not found.
253  */
254 struct neighbor_entry *
255 olsr_lookup_neighbor_table(union olsr_ip_addr *dst)
256 {
257   struct neighbor_entry  *entry;
258   olsr_u32_t             hash;
259   //struct addresses       *adr;
260   union olsr_ip_addr     *tmp_ip;
261
262   /*
263    *Find main address of node
264    */
265   if((tmp_ip = mid_lookup_main_addr(dst)) != NULL)
266     dst = tmp_ip;
267   
268   hash = olsr_hashing(dst);
269
270   
271   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
272   for(entry = neighbortable[hash].next;
273       entry != &neighbortable[hash];
274       entry = entry->next)
275     {
276       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
277       if(COMP_IP(&entry->neighbor_main_addr, dst))
278         return entry;
279       
280     }
281   //printf("NOPE\n\n");
282
283   return NULL;
284
285 }
286
287
288 /**
289  *Lookup a neighbor entry in the neighbortable based on an address.
290  *
291  *@param dst the IP address of the neighbor to look up
292  *
293  *@return a pointer to the neighbor struct registered on the given 
294  *address. NULL if not found.
295  */
296 struct neighbor_entry *
297 olsr_lookup_neighbor_table_alias(union olsr_ip_addr *dst)
298 {
299   struct neighbor_entry  *entry;
300   olsr_u32_t             hash;
301   //struct addresses       *adr;
302   
303   hash = olsr_hashing(dst);
304
305   
306   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
307   for(entry = neighbortable[hash].next;
308       entry != &neighbortable[hash];
309       entry = entry->next)
310     {
311       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
312       if(COMP_IP(&entry->neighbor_main_addr, dst))
313         return entry;
314       
315     }
316   //printf("NOPE\n\n");
317
318   return NULL;
319
320 }
321
322
323
324 int
325 update_neighbor_status(struct neighbor_entry *entry, int link)
326 {
327   struct neighbor_2_entry *two_hop_neighbor;
328
329   /*
330    * Update neighbor entry
331    */
332  
333   if(link == SYM_LINK)
334     {
335       /* N_status is set to SYM */
336       if(entry->status == NOT_SYM)
337         {
338           
339           /* Delete posible 2 hop entry on this neighbor */
340           if((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr))!=NULL)
341             {
342               olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
343             }
344   
345           changes_neighborhood = OLSR_TRUE;
346           changes_topology = OLSR_TRUE;
347           if(olsr_cnf->tc_redundancy > 1)
348             changes = OLSR_TRUE;
349         }
350       entry->status = SYM;
351     }
352   else
353     {
354       if(entry->status == SYM)
355         {
356           changes_neighborhood = OLSR_TRUE;
357           changes_topology = OLSR_TRUE;
358           if(olsr_cnf->tc_redundancy > 1)
359             changes = OLSR_TRUE;
360         }
361       /* else N_status is set to NOT_SYM */
362       entry->status = NOT_SYM;
363       /* remove neighbor from routing list */
364     }
365
366   return entry->status;
367 }
368
369
370
371 /**
372  *Times out the entries in the two hop neighbor table and 
373  *deletes those who have exceeded their time to live since 
374  *last update.
375  *
376  *@return nada
377  */
378
379 void
380 olsr_time_out_two_hop_neighbors(struct neighbor_entry  *neighbor)
381 {
382   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
383   struct  neighbor_2_entry      *two_hop_entry;
384
385
386   two_hop_list = neighbor->neighbor_2_list.next;
387
388   //neighbor->neighbor_2_list = NULL;
389
390   while(two_hop_list != &neighbor->neighbor_2_list)
391     {
392       if(TIMED_OUT(&two_hop_list->neighbor_2_timer))
393         {
394           two_hop_entry = two_hop_list->neighbor_2;
395           two_hop_entry->neighbor_2_pointer--;
396           olsr_delete_neighbor_pointer(two_hop_entry, &neighbor->neighbor_main_addr);
397
398           if(two_hop_entry->neighbor_2_pointer < 1)
399             {
400               /* FIX THIS (fix what?)*/
401               DEQUEUE_ELEM(two_hop_entry);
402
403               free((void *)two_hop_entry);
404             }
405
406           two_hop_to_delete = two_hop_list;
407           two_hop_list = two_hop_list->next;
408
409           /* Dequeue */
410           DEQUEUE_ELEM(two_hop_to_delete);
411
412           free(two_hop_to_delete);
413
414           /* This flag is set to OLSR_TRUE to recalculate the MPR set and the routing table*/
415           changes_neighborhood = OLSR_TRUE;
416           changes_topology = OLSR_TRUE;
417           
418         }
419       else
420         two_hop_list = two_hop_list->next;
421
422     }
423 }
424
425
426
427
428
429 void
430 olsr_time_out_neighborhood_tables()
431 {
432   olsr_u8_t              index;
433   struct neighbor_entry  *entry;
434   
435   for(index=0;index<HASHSIZE;index++)
436     {
437       entry = neighbortable[index].next;
438
439       while(entry != &neighbortable[index])
440         {         
441           olsr_time_out_two_hop_neighbors(entry);
442
443           entry = entry->next;
444         }
445     }
446 }
447
448
449
450
451
452 /**
453  *Prints the registered neighbors and two hop neighbors
454  *to STDOUT.
455  *
456  *@return nada
457  */
458 void
459 olsr_print_neighbor_table()
460 {
461   int i;
462   struct neighbor_entry *neigh;
463 #if defined USE_LINK_QUALITY
464   struct link_entry *link;
465 #endif
466   double best_lq, inv_best_lq;
467   char *fstr;
468
469   olsr_printf(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n",
470               nowtm->tm_hour,
471               nowtm->tm_min,
472               nowtm->tm_sec,
473               now.tv_usec/10000);
474
475   if (olsr_cnf->ip_version == AF_INET)
476   {
477     olsr_printf(1, "IP address       LQ     NLQ    SYM  MPR  will\n");
478     fstr = "%-15s  %5.3f  %5.3f  %s  %s  %d\n";
479   }
480
481   else
482   {
483     olsr_printf(1, "IP address                               LQ     NLQ    SYM  MPR  will\n");
484     fstr = "%-39s  %5.3f  %5.3f  %s  %s  %d\n";
485   }
486
487   for (i = 0; i < HASHSIZE; i++)
488     {
489       for(neigh = neighbortable[i].next; neigh != &neighbortable[i];
490           neigh = neigh->next)
491         {
492 #if defined USE_LINK_QUALITY
493           link = olsr_neighbor_best_link(&neigh->neighbor_main_addr);
494           best_lq = link->neigh_link_quality;
495
496           link = olsr_neighbor_best_inverse_link(&neigh->neighbor_main_addr);
497           inv_best_lq = link->loss_link_quality;
498 #else
499           best_lq = 0.0;
500           inv_best_lq = 0.0;
501 #endif
502
503           olsr_printf(1, fstr, olsr_ip_to_string(&neigh->neighbor_main_addr),
504                       inv_best_lq, best_lq,
505                       (neigh->status == SYM) ? "SYM" : "   ",
506                       neigh->is_mpr ? "MPR" : "   ",
507                       neigh->willingness);
508         }
509     }
510 }
511
512
513
514
515
516
517
518
519
520