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