* const-ify parameters
[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.33 2007/08/02 21:57:06 bernd67 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(void)
60 {
61   int i;
62
63   olsr_register_timeout_function(&olsr_time_out_neighborhood_tables);
64   for(i = 0; i < HASHSIZE; i++)
65     {
66       neighbortable[i].next = &neighbortable[i];
67       neighbortable[i].prev = &neighbortable[i];
68     }
69 }
70
71
72 /**
73  *Delete a two hop neighbor from a neighbors two 
74  *hop neighbor list.
75  *
76  *@param neighbor the neighbor to delete the two hop 
77  *neighbor from.
78  *@param address the IP address of the two hop neighbor 
79  *to delete.
80  *
81  *@return positive if entry deleted
82  */
83 int
84 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, union olsr_ip_addr *address)
85 {
86
87   struct neighbor_2_list_entry *entry;
88   
89   entry = neighbor->neighbor_2_list.next;
90
91   while(entry != &neighbor->neighbor_2_list)
92     {      
93       if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, address))
94         {
95           /* Dequeue */
96           DEQUEUE_ELEM(entry);
97           /* Delete */
98           free(entry);
99           return 1;       
100         }
101       entry = entry->next;      
102     }
103   return 0;
104 }
105
106
107 /**
108  *Check if a two hop neighbor is reachable via a given
109  *neighbor.
110  *
111  *@param neighbor neighbor-entry to check via
112  *@param neighbor_main_address the addres of the two hop neighbor 
113  *to find.
114  *
115  *@return a pointer to the neighbor_2_list_entry struct
116  *representing the two hop neighbor if found. NULL if not found.
117  */
118 struct neighbor_2_list_entry *
119 olsr_lookup_my_neighbors(const struct neighbor_entry *neighbor, const union olsr_ip_addr *neighbor_main_address)
120 {
121   struct neighbor_2_list_entry *entry;
122   
123   for(entry = neighbor->neighbor_2_list.next;
124       entry != &neighbor->neighbor_2_list;
125       entry = entry->next)
126     {
127       
128       if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
129         return entry;
130       
131     }
132   return NULL;
133 }
134
135
136
137 /**
138  *Delete a neighbr table entry.
139  *
140  *Remember: Deleting a neighbor entry results 
141  *the deletion of its 2 hop neighbors list!!!
142  *@param neighbor the neighbor entry to delete
143  *
144  *@return nada
145  */
146
147 int
148 olsr_delete_neighbor_table(const union olsr_ip_addr *neighbor_addr)
149 {  
150   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
151   olsr_u32_t                    hash;
152   struct neighbor_entry         *entry;
153
154   //printf("inserting neighbor\n");
155
156   hash = olsr_hashing(neighbor_addr);
157
158   entry = neighbortable[hash].next;
159
160   /*
161    * Find neighbor entry
162    */
163   while(entry != &neighbortable[hash])
164     {
165       if(COMP_IP(&entry->neighbor_main_addr, neighbor_addr))
166         break;
167       
168       entry = entry->next;
169     }
170
171   if(entry == &neighbortable[hash])
172     return 0;
173
174
175   two_hop_list = entry->neighbor_2_list.next;
176
177   while(two_hop_list != &entry->neighbor_2_list)
178     {
179       struct neighbor_2_entry *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(const 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(const union olsr_ip_addr *dst)
273 {
274   /*
275    *Find main address of node
276    */
277   union olsr_ip_addr *tmp_ip = mid_lookup_main_addr(dst);
278   if(tmp_ip != NULL)
279     dst = tmp_ip;
280   return olsr_lookup_neighbor_table_alias(dst);
281 }
282
283
284 /**
285  *Lookup a neighbor entry in the neighbortable based on an address.
286  *
287  *@param dst the IP address of the neighbor to look up
288  *
289  *@return a pointer to the neighbor struct registered on the given 
290  *address. NULL if not found.
291  */
292 struct neighbor_entry *
293 olsr_lookup_neighbor_table_alias(const union olsr_ip_addr *dst)
294 {
295   struct neighbor_entry  *entry;
296   olsr_u32_t             hash = olsr_hashing(dst);
297   
298   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
299   for(entry = neighbortable[hash].next;
300       entry != &neighbortable[hash];
301       entry = entry->next)
302     {
303       //printf("Checking %s\n", olsr_ip_to_string(&entry->neighbor_main_addr));
304       if(COMP_IP(&entry->neighbor_main_addr, dst))
305         return entry;
306       
307     }
308   //printf("NOPE\n\n");
309
310   return NULL;
311
312 }
313
314
315
316 int
317 update_neighbor_status(struct neighbor_entry *entry, int lnk)
318 {
319   /*
320    * Update neighbor entry
321    */
322  
323   if(lnk == SYM_LINK)
324     {
325       /* N_status is set to SYM */
326       if(entry->status == NOT_SYM)
327         {
328           struct neighbor_2_entry *two_hop_neighbor;
329           
330           /* Delete posible 2 hop entry on this neighbor */
331           if((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr))!=NULL)
332             {
333               olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
334             }
335   
336           changes_neighborhood = OLSR_TRUE;
337           changes_topology = OLSR_TRUE;
338           if(olsr_cnf->tc_redundancy > 1)
339             signal_link_changes(OLSR_TRUE);
340         }
341       entry->status = SYM;
342     }
343   else
344     {
345       if(entry->status == SYM)
346         {
347           changes_neighborhood = OLSR_TRUE;
348           changes_topology = OLSR_TRUE;
349           if(olsr_cnf->tc_redundancy > 1)
350             signal_link_changes(OLSR_TRUE);
351         }
352       /* else N_status is set to NOT_SYM */
353       entry->status = NOT_SYM;
354       /* remove neighbor from routing list */
355     }
356
357   return entry->status;
358 }
359
360
361
362 /**
363  *Times out the entries in the two hop neighbor table and 
364  *deletes those who have exceeded their time to live since 
365  *last update.
366  *
367  *@return nada
368  */
369
370 void
371 olsr_time_out_two_hop_neighbors(struct neighbor_entry  *neighbor)
372 {
373   struct neighbor_2_list_entry *two_hop_list = neighbor->neighbor_2_list.next;
374
375   while(two_hop_list != &neighbor->neighbor_2_list)
376     {
377       if(TIMED_OUT(two_hop_list->neighbor_2_timer))
378         {
379           struct neighbor_2_list_entry *two_hop_to_delete;
380           struct neighbor_2_entry      *two_hop_entry = two_hop_list->neighbor_2;
381
382           two_hop_entry->neighbor_2_pointer--;
383           olsr_delete_neighbor_pointer(two_hop_entry, &neighbor->neighbor_main_addr);
384           
385           if(two_hop_entry->neighbor_2_pointer < 1)
386             {
387               DEQUEUE_ELEM(two_hop_entry);
388               free(two_hop_entry);
389             }
390           
391           two_hop_to_delete = two_hop_list;
392           two_hop_list = two_hop_list->next;
393           
394           /* Dequeue */
395           DEQUEUE_ELEM(two_hop_to_delete);
396           
397           free(two_hop_to_delete);
398
399           /* This flag is set to OLSR_TRUE to recalculate the MPR set and the routing table*/
400           changes_neighborhood = OLSR_TRUE;
401           changes_topology = OLSR_TRUE;
402           
403         }
404       else
405         two_hop_list = two_hop_list->next;
406
407     }
408 }
409
410 void
411 olsr_time_out_neighborhood_tables(void)
412 {
413   int idx;
414   
415   for(idx=0;idx<HASHSIZE;idx++)
416     {
417       struct neighbor_entry *entry;
418       for(entry = neighbortable[idx].next; entry != &neighbortable[idx]; entry = entry->next)
419         {         
420           olsr_time_out_two_hop_neighbors(entry);
421         }
422     }
423 }
424
425 /**
426  *Prints the registered neighbors and two hop neighbors
427  *to STDOUT.
428  *
429  *@return nada
430  */
431 void
432 olsr_print_neighbor_table(void)
433 {
434   int i;
435   char *fstr;
436
437   OLSR_PRINTF(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n",
438               nowtm->tm_hour,
439               nowtm->tm_min,
440               nowtm->tm_sec,
441               (int)now.tv_usec/10000);
442
443   if (olsr_cnf->ip_version == AF_INET)
444     {
445       OLSR_PRINTF(1, "IP address       LQ     NLQ    SYM   MPR   MPRS  will\n");
446       fstr = "%-15s  %5.3f  %5.3f  %s  %s  %s  %d\n";
447     }
448   else
449     {
450       OLSR_PRINTF(1, "IP address                               LQ     NLQ    SYM   MPR   MPRS  will\n");
451       fstr = "%-39s  %5.3f  %5.3f  %s  %s  %s  %d\n";
452     }
453
454   for (i = 0; i < HASHSIZE; i++)
455     {
456       struct neighbor_entry *neigh;
457       for(neigh = neighbortable[i].next; neigh != &neighbortable[i]; neigh = neigh->next)
458         {
459           struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
460           if(lnk)
461             {
462               const double best_lq = lnk->neigh_link_quality;
463               const double inv_best_lq = lnk->loss_link_quality;
464
465               OLSR_PRINTF(1, fstr, olsr_ip_to_string(&neigh->neighbor_main_addr),
466                           inv_best_lq, best_lq,
467                           (neigh->status == SYM) ? "YES " : "NO  ",
468                           neigh->is_mpr ? "YES " : "NO  ", 
469                           olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
470                           neigh->willingness);
471             }
472         }
473     }
474 }