* killed lots of #ifdef ... #endif which make the source quite unreadable
[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  */
40
41 #include "ipcalc.h"
42 #include "defs.h"
43 #include "two_hop_neighbor_table.h"
44 #include "mid_set.h"
45 #include "mpr.h"
46 #include "neighbor_table.h"
47 #include "olsr.h"
48 #include "scheduler.h"
49 #include "link_set.h"
50 #include "mpr_selector_set.h"
51 #include "net_olsr.h"
52
53
54 struct neighbor_entry neighbortable[HASHSIZE];
55
56
57 void
58 olsr_init_neighbor_table(void)
59 {
60   int i;
61
62   for(i = 0; i < HASHSIZE; i++)
63     {
64       neighbortable[i].next = &neighbortable[i];
65       neighbortable[i].prev = &neighbortable[i];
66     }
67 }
68
69 /**
70  * Unlink, delete and free a nbr2_list entry.
71  */
72 static void
73 olsr_del_nbr2_list(struct neighbor_2_list_entry *nbr2_list)
74 {
75   struct neighbor_entry *nbr;
76   struct neighbor_2_entry *nbr2;
77
78   nbr = nbr2_list->nbr2_nbr;
79   nbr2 = nbr2_list->neighbor_2;
80
81   if (nbr2->neighbor_2_pointer < 1) {
82       DEQUEUE_ELEM(nbr2);
83       free(nbr2);
84   }
85
86   /*
87    * Kill running timers.
88    */
89   olsr_stop_timer(nbr2_list->nbr2_list_timer);
90   nbr2_list->nbr2_list_timer = NULL;
91   
92   /* Dequeue */
93   DEQUEUE_ELEM(nbr2_list);
94   
95   free(nbr2_list);
96
97   /* Set flags to recalculate the MPR set and the routing table */
98   changes_neighborhood = OLSR_TRUE;
99   changes_topology = OLSR_TRUE;
100 }
101
102 /**
103  * Delete a two hop neighbor from a neighbors two hop neighbor list.
104  *
105  * @param neighbor the neighbor to delete the two hop neighbor from.
106  * @param address the IP address of the two hop neighbor to delete.
107  *
108  * @return positive if entry deleted
109  */
110 int
111 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, union olsr_ip_addr *address)
112 {
113   struct neighbor_2_list_entry *nbr2_list;
114   
115   nbr2_list = neighbor->neighbor_2_list.next;
116
117   while (nbr2_list != &neighbor->neighbor_2_list) {
118     if (ipequal(&nbr2_list->neighbor_2->neighbor_2_addr, address)) {
119       olsr_del_nbr2_list(nbr2_list);
120       return 1;   
121     }
122     nbr2_list = nbr2_list->next;      
123   }
124   return 0;
125 }
126
127
128 /**
129  *Check if a two hop neighbor is reachable via a given
130  *neighbor.
131  *
132  *@param neighbor neighbor-entry to check via
133  *@param neighbor_main_address the addres of the two hop neighbor 
134  *to find.
135  *
136  *@return a pointer to the neighbor_2_list_entry struct
137  *representing the two hop neighbor if found. NULL if not found.
138  */
139 struct neighbor_2_list_entry *
140 olsr_lookup_my_neighbors(const struct neighbor_entry *neighbor, const union olsr_ip_addr *neighbor_main_address)
141 {
142   struct neighbor_2_list_entry *entry;
143   
144   for(entry = neighbor->neighbor_2_list.next;
145       entry != &neighbor->neighbor_2_list;
146       entry = entry->next)
147     {
148       
149       if(ipequal(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
150         return entry;
151       
152     }
153   return NULL;
154 }
155
156
157
158 /**
159  *Delete a neighbr table entry.
160  *
161  *Remember: Deleting a neighbor entry results 
162  *the deletion of its 2 hop neighbors list!!!
163  *@param neighbor the neighbor entry to delete
164  *
165  *@return nada
166  */
167
168 int
169 olsr_delete_neighbor_table(const union olsr_ip_addr *neighbor_addr)
170 {  
171   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
172   olsr_u32_t                    hash;
173   struct neighbor_entry         *entry;
174
175   //printf("inserting neighbor\n");
176
177   hash = olsr_ip_hashing(neighbor_addr);
178
179   entry = neighbortable[hash].next;
180
181   /*
182    * Find neighbor entry
183    */
184   while(entry != &neighbortable[hash])
185     {
186       if(ipequal(&entry->neighbor_main_addr, neighbor_addr))
187         break;
188       
189       entry = entry->next;
190     }
191
192   if(entry == &neighbortable[hash])
193     return 0;
194
195
196   two_hop_list = entry->neighbor_2_list.next;
197
198   while (two_hop_list != &entry->neighbor_2_list) {
199       two_hop_to_delete = two_hop_list;
200       two_hop_list = two_hop_list->next;
201
202       two_hop_to_delete->neighbor_2->neighbor_2_pointer--;
203       olsr_delete_neighbor_pointer(two_hop_to_delete->neighbor_2,
204                                    &entry->neighbor_main_addr);
205
206       olsr_del_nbr2_list(two_hop_to_delete);
207     }
208
209
210   /* Dequeue */
211   DEQUEUE_ELEM(entry);
212
213   free(entry);
214
215   changes_neighborhood = OLSR_TRUE;
216   return 1;
217
218 }
219
220
221
222 /**
223  *Insert a neighbor entry in the neighbor table
224  *
225  *@param main_addr the main address of the new node
226  *
227  *@return 0 if neighbor already exists 1 if inserted
228  */
229 struct neighbor_entry *
230 olsr_insert_neighbor_table(const union olsr_ip_addr *main_addr)
231 {
232   olsr_u32_t             hash;
233   struct neighbor_entry  *new_neigh;
234   
235   hash = olsr_ip_hashing(main_addr);
236
237   /* Check if entry exists */
238   
239   for(new_neigh = neighbortable[hash].next;
240       new_neigh != &neighbortable[hash];
241       new_neigh = new_neigh->next)
242     {
243       if(ipequal(&new_neigh->neighbor_main_addr, main_addr))
244         return new_neigh;
245     }
246   
247   //printf("inserting neighbor\n");
248   
249   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
250   
251   /* Set address, willingness and status */
252   new_neigh->neighbor_main_addr = *main_addr;
253   new_neigh->willingness = WILL_NEVER;
254   new_neigh->status = NOT_SYM;
255
256   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
257   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
258   
259   new_neigh->linkcount = 0;
260   new_neigh->is_mpr = OLSR_FALSE;
261   new_neigh->was_mpr = OLSR_FALSE;
262
263   /* Queue */
264   QUEUE_ELEM(neighbortable[hash], new_neigh);
265
266   return new_neigh;
267 }
268
269
270
271 /**
272  *Lookup a neighbor entry in the neighbortable based on an address.
273  *
274  *@param dst the IP address of the neighbor to look up
275  *
276  *@return a pointer to the neighbor struct registered on the given 
277  *address. NULL if not found.
278  */
279 struct neighbor_entry *
280 olsr_lookup_neighbor_table(const union olsr_ip_addr *dst)
281 {
282   /*
283    *Find main address of node
284    */
285   union olsr_ip_addr *tmp_ip = mid_lookup_main_addr(dst);
286   if(tmp_ip != NULL)
287     dst = tmp_ip;
288   return olsr_lookup_neighbor_table_alias(dst);
289 }
290
291
292 /**
293  *Lookup a neighbor entry in the neighbortable based on an address.
294  *
295  *@param dst the IP address of the neighbor to look up
296  *
297  *@return a pointer to the neighbor struct registered on the given 
298  *address. NULL if not found.
299  */
300 struct neighbor_entry *
301 olsr_lookup_neighbor_table_alias(const union olsr_ip_addr *dst)
302 {
303   struct neighbor_entry  *entry;
304   olsr_u32_t             hash = olsr_ip_hashing(dst);
305   
306   //printf("\nLookup %s\n", olsr_ip_to_string(&buf, 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(&buf, &entry->neighbor_main_addr));
312       if(ipequal(&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 lnk)
326 {
327   /*
328    * Update neighbor entry
329    */
330  
331   if(lnk == SYM_LINK)
332     {
333       /* N_status is set to SYM */
334       if(entry->status == NOT_SYM)
335         {
336           struct neighbor_2_entry *two_hop_neighbor;
337           
338           /* Delete posible 2 hop entry on this neighbor */
339           if((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr))!=NULL)
340             {
341               olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
342             }
343   
344           changes_neighborhood = OLSR_TRUE;
345           changes_topology = OLSR_TRUE;
346           if(olsr_cnf->tc_redundancy > 1)
347             signal_link_changes(OLSR_TRUE);
348         }
349       entry->status = SYM;
350     }
351   else
352     {
353       if(entry->status == SYM)
354         {
355           changes_neighborhood = OLSR_TRUE;
356           changes_topology = OLSR_TRUE;
357           if(olsr_cnf->tc_redundancy > 1)
358             signal_link_changes(OLSR_TRUE);
359         }
360       /* else N_status is set to NOT_SYM */
361       entry->status = NOT_SYM;
362       /* remove neighbor from routing list */
363     }
364
365   return entry->status;
366 }
367
368
369 /**
370  * Callback for the nbr2_list timer.
371  */
372 void
373 olsr_expire_nbr2_list(void *context)
374 {
375   struct neighbor_2_list_entry *nbr2_list;
376   struct neighbor_entry *nbr;
377   struct neighbor_2_entry *nbr2; 
378
379   nbr2_list = (struct neighbor_2_list_entry *)context;
380   nbr2_list->nbr2_list_timer = NULL;
381
382   nbr = nbr2_list->nbr2_nbr;
383   nbr2 = nbr2_list->neighbor_2;
384
385   nbr2->neighbor_2_pointer--;
386   olsr_delete_neighbor_pointer(nbr2, &nbr->neighbor_main_addr); 
387
388   olsr_del_nbr2_list(nbr2_list);
389 }
390
391
392 /**
393  *Prints the registered neighbors and two hop neighbors
394  *to STDOUT.
395  *
396  *@return nada
397  */
398 void
399 olsr_print_neighbor_table(void)
400 {
401 #ifdef NODEBUG
402   /* The whole function doesn't do anything else. */
403 #ifndef NODEBUG
404   const int iplen = olsr_cnf->ip_version == AF_INET ?  15 : 39;
405 #endif
406   int idx;
407   OLSR_PRINTF(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n"
408               "%*s  LQ     NLQ    SYM   MPR   MPRS  will\n",
409               nowtm->tm_hour,
410               nowtm->tm_min,
411               nowtm->tm_sec,
412               (int)now.tv_usec/10000,
413               iplen,
414               "IP address");
415
416   for (idx = 0; idx < HASHSIZE; idx++) {
417     struct neighbor_entry *neigh;
418     for(neigh = neighbortable[idx].next; neigh != &neighbortable[idx]; neigh = neigh->next) {
419       struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
420       if(lnk) {
421         struct ipaddr_str buf;
422         OLSR_PRINTF(1, "%-*s  %5.3f  %5.3f  %s  %s  %s  %d\n",
423                     iplen,
424                     olsr_ip_to_string(&buf, &neigh->neighbor_main_addr),
425                     lnk->loss_link_quality,
426                     lnk->neigh_link_quality,
427                     neigh->status == SYM ? "YES " : "NO  ",
428                     neigh->is_mpr ? "YES " : "NO  ", 
429                     olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
430                     neigh->willingness);
431       }
432     }
433   }
434 #endif
435 }
436
437 /*
438  * Local Variables:
439  * c-basic-offset: 2
440  * End:
441  */