84d3f898da6269286c6d97d52786fbb1b0a2f3d8
[olsrd.git] / src / neighbor_table.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41
42 #include "ipcalc.h"
43 #include "defs.h"
44 #include "two_hop_neighbor_table.h"
45 #include "mid_set.h"
46 #include "mpr.h"
47 #include "neighbor_table.h"
48 #include "olsr.h"
49 #include "scheduler.h"
50 #include "link_set.h"
51 #include "mpr_selector_set.h"
52 #include "net_olsr.h"
53 #include "olsr_logging.h"
54
55 #include <stdlib.h>
56
57 /* Root of the one hop neighbor database */
58 struct avl_tree nbr_tree;
59
60 /* Some cookies for stats keeping */
61 struct olsr_cookie_info *nbr2_list_timer_cookie = NULL;
62 struct olsr_cookie_info *nbr2_list_mem_cookie = NULL;
63 struct olsr_cookie_info *nbr_mem_cookie = NULL;
64
65 /*
66  * Init neighbor tables.
67  */
68 void
69 olsr_init_neighbor_table(void)
70 {
71   OLSR_INFO(LOG_NEIGHTABLE, "Initializing neighbor tree.\n");
72   avl_init(&nbr_tree, avl_comp_default);
73
74   nbr2_list_timer_cookie = olsr_alloc_cookie("2-Hop Neighbor List", OLSR_COOKIE_TYPE_TIMER);
75
76   nbr2_list_mem_cookie = olsr_alloc_cookie("2-Hop Neighbor List", OLSR_COOKIE_TYPE_MEMORY);
77   olsr_cookie_set_memory_size(nbr2_list_mem_cookie, sizeof(struct nbr2_list_entry));
78
79   nbr_mem_cookie = olsr_alloc_cookie("1-Hop Neighbor", OLSR_COOKIE_TYPE_MEMORY);
80   olsr_cookie_set_memory_size(nbr_mem_cookie, sizeof(struct nbr_entry));
81 }
82
83
84 /**
85  * Add a neighbor 2 reference to a neighbor.
86  */
87 struct nbr2_list_entry *
88 olsr_add_nbr2_list_entry(struct nbr_entry *nbr, struct neighbor_2_entry *nbr2, float vtime)
89 {
90   struct nbr2_list_entry *nbr2_list;
91
92   /*
93    * check first if the entry exists.
94    */
95   nbr2_list = olsr_lookup_nbr2_list_entry(nbr, &nbr2->neighbor_2_addr);
96   if (nbr2_list) {
97
98     /* 
99      * Refresh timer.
100      */
101     olsr_change_timer(nbr2_list->nbr2_list_timer, vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
102     return nbr2_list;
103   }
104
105   /*
106    * Reference not found, allocate and init a fresh one.
107    */
108   nbr2_list = olsr_cookie_malloc(nbr2_list_mem_cookie);
109
110   nbr2_list->neighbor_2 = nbr2;
111   nbr2->neighbor_2_pointer++;   /* XXX move to olsr_lock_nbr2 () */
112   nbr2_list->nbr2_nbr = nbr;    /* XXX nbr needs refcount protection as well */
113
114   /*
115    * Start the timer.
116    */
117   olsr_start_timer(vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT,
118                    &olsr_expire_nbr2_list, nbr2_list, nbr2_list_timer_cookie->ci_id);
119
120   /* Add to the nbr2 reference subtree */
121   nbr2_list->nbr2_list_node.key = &nbr2->neighbor_2_addr;
122   avl_insert(&nbr->nbr2_list_tree, &nbr2_list->nbr2_list_node, AVL_DUP_NO);
123
124   return nbr2_list;
125 }
126
127
128 /**
129  * Unlink, delete and free a nbr2_list entry.
130  */
131 static void
132 olsr_delete_nbr2_list_entry(struct nbr2_list_entry *nbr2_list)
133 {
134   struct neighbor_2_entry *nbr2;
135   struct nbr_entry *nbr;
136
137   nbr2 = nbr2_list->neighbor_2;
138   nbr = nbr2_list->nbr2_nbr;
139
140   /* XXX move to olsr_unlock_nbr2() */
141   if (nbr2->neighbor_2_pointer < 1) {
142     DEQUEUE_ELEM(nbr2);
143     free(nbr2);
144   }
145
146   /*
147    * Kill running timers.
148    */
149   olsr_stop_timer(nbr2_list->nbr2_list_timer);
150   nbr2_list->nbr2_list_timer = NULL;
151
152   /* Remove from neighbor2 reference subtree */
153   avl_delete(&nbr->nbr2_list_tree, &nbr2_list->nbr2_list_node);
154
155   olsr_cookie_free(nbr2_list_mem_cookie, nbr2_list);
156
157   /* Set flags to recalculate the MPR set and the routing table */
158   changes_neighborhood = true;
159   changes_topology = true;
160 }
161
162 /**
163  * Delete a two hop neighbor from a neighbors two hop neighbor list.
164  *
165  * @param neighbor the neighbor to delete the two hop neighbor from.
166  * @param address the IP address of the two hop neighbor to delete.
167  *
168  * @return positive if entry deleted
169  */
170 bool
171 olsr_delete_nbr2_list_entry_by_addr(struct nbr_entry *nbr, union olsr_ip_addr *addr)
172 {
173   struct nbr2_list_entry *nbr2_list;
174
175   nbr2_list = olsr_lookup_nbr2_list_entry(nbr, addr);
176
177   if (nbr2_list) {
178     olsr_delete_nbr2_list_entry(nbr2_list);
179     return true;
180   }
181
182   return false;
183 }
184
185
186 /**
187  * Check if a two hop neighbor is reachable via a given
188  * neighbor.
189  *
190  * @param nbr neighbor-entry to check via
191  * @param addr the addres of the two hop neighbor to find.
192  *
193  * @return a pointer to the nbr2_list_entry struct
194  * representing the two hop neighbor if found. NULL if not found.
195  */
196 struct nbr2_list_entry *
197 olsr_lookup_nbr2_list_entry(struct nbr_entry *nbr, const union olsr_ip_addr *addr)
198 {
199   struct avl_node *node;
200
201   node = avl_find(&nbr->nbr2_list_tree, addr);
202   if (node) {
203     return nbr2_list_node_to_nbr2_list(node);
204   }
205   return NULL;
206 }
207
208
209 /**
210  * Delete a neighbor table entry.
211  *
212  * Remember: Deleting a neighbor entry results the deletion of its 2 hop neighbors list!!!
213  * @param addr the neighbor entry to delete
214  *
215  * @return TRUE on success, FALSE otherwise.
216  */
217 bool
218 olsr_delete_nbr_entry(const union olsr_ip_addr * addr)
219 {
220   struct nbr2_list_entry *nbr2_list;
221   struct nbr_entry *nbr;
222
223 #if !defined REMOVE_LOG_DEBUG
224   struct ipaddr_str buf;
225 #endif
226
227   /*
228    * Find neighbor entry
229    */
230   nbr = olsr_lookup_nbr_entry(addr);
231   if (!nbr) {
232     return false;
233   }
234
235   OLSR_DEBUG(LOG_NEIGHTABLE, "Delete 1-hop neighbor: %s\n", olsr_ip_to_string(&buf, addr));
236
237   OLSR_FOR_ALL_NBR2_LIST_ENTRIES(nbr, nbr2_list) {
238     nbr2_list->neighbor_2->neighbor_2_pointer--;        /* XXX move to olsr_nbr2_unlock() */
239     olsr_delete_neighbor_pointer(nbr2_list->neighbor_2, nbr);
240     olsr_delete_nbr2_list_entry(nbr2_list);
241   } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(nbr, nbr2_list);
242
243   /* Remove from global neighbor tree */
244   avl_delete(&nbr_tree, &nbr->nbr_node);
245
246   olsr_cookie_free(nbr_mem_cookie, nbr);
247
248   changes_neighborhood = true;
249
250   return true;
251 }
252
253
254 /**
255  * Insert a neighbor entry in the neighbor table.
256  *
257  * @param addr the main address of the new node
258  * @return pointer to an already existting (or new created) neighbor entry
259  */
260 struct nbr_entry *
261 olsr_add_nbr_entry(const union olsr_ip_addr *addr)
262 {
263 #if !defined REMOVE_LOG_DEBUG
264   struct ipaddr_str buf;
265 #endif
266   struct nbr_entry *nbr;
267
268   /*
269    * Check if neighbor entry exists.
270    */
271   nbr = olsr_lookup_nbr_entry(addr);
272   if (nbr) {
273     return nbr;
274   }
275
276   OLSR_DEBUG(LOG_NEIGHTABLE, "Add 1-hop neighbor: %s\n", olsr_ip_to_string(&buf, addr));
277
278   nbr = olsr_cookie_malloc(nbr_mem_cookie);
279
280   /* Set address, willingness and status */
281   nbr->neighbor_main_addr = *addr;
282   nbr->willingness = WILL_NEVER;
283   nbr->status = NOT_SYM;
284
285   /* Init subtree for nbr2 pointers */
286   avl_init(&nbr->nbr2_list_tree, avl_comp_default);
287
288   nbr->linkcount = 0;
289   nbr->is_mpr = false;
290   nbr->was_mpr = false;
291
292   /* Add to the global neighbor tree */
293   nbr->nbr_node.key = &nbr->neighbor_main_addr;
294   avl_insert(&nbr_tree, &nbr->nbr_node, AVL_DUP_NO);
295
296   return nbr;
297 }
298
299
300
301 /**
302  * Lookup a neighbor entry in the neighbortable based on an address.
303  * Unalias the passed in address before.
304  * 
305  * @param addr the IP address of the neighbor to look up
306  *
307  * @return a pointer to the neighbor struct registered on the given
308  * address. NULL if not found.
309  */
310 struct nbr_entry *
311 olsr_lookup_nbr_entry(const union olsr_ip_addr *addr)
312 {
313   const union olsr_ip_addr *main_addr;
314
315   /*
316    * Find main address of node
317    */
318   main_addr = olsr_lookup_main_addr_by_alias(addr);
319   if (!main_addr) {
320     main_addr = addr;
321   }
322
323   return olsr_lookup_nbr_entry_alias(main_addr);
324 }
325
326
327 /**
328  * Lookup a neighbor entry in the neighbortable based on an address.
329  *
330  * @param addr the IP address of the neighbor to look up
331  *
332  * @return a pointer to the neighbor struct registered on the given
333  *  address. NULL if not found.
334  */
335 struct nbr_entry *
336 olsr_lookup_nbr_entry_alias(const union olsr_ip_addr *addr)
337 {
338   struct avl_node *node;
339
340   node = avl_find(&nbr_tree, addr);
341   if (node) {
342     return nbr_node_to_nbr(node);
343   }
344   return NULL;
345 }
346
347
348 int
349 olsr_update_nbr_status(struct nbr_entry *entry, int lnk)
350 {
351   /*
352    * Update neighbor entry
353    */
354
355   if (lnk == SYM_LINK) {
356     /* N_status is set to SYM */
357     if (entry->status == NOT_SYM) {
358       struct neighbor_2_entry *two_hop_neighbor;
359
360       /* Delete posible 2 hop entry on this neighbor */
361       if ((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr)) != NULL) {
362         olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
363       }
364
365       changes_neighborhood = true;
366       changes_topology = true;
367       if (olsr_cnf->tc_redundancy > 1)
368         signal_link_changes(true);
369     }
370     entry->status = SYM;
371   } else {
372     if (entry->status == SYM) {
373       changes_neighborhood = true;
374       changes_topology = true;
375       if (olsr_cnf->tc_redundancy > 1)
376         signal_link_changes(true);
377     }
378     /* else N_status is set to NOT_SYM */
379     entry->status = NOT_SYM;
380     /* remove neighbor from routing list */
381   }
382
383   return entry->status;
384 }
385
386
387 /**
388  * Callback for the nbr2_list timer.
389  */
390 void
391 olsr_expire_nbr2_list(void *context)
392 {
393   struct nbr2_list_entry *nbr2_list;
394   struct nbr_entry *nbr;
395   struct neighbor_2_entry *nbr2;
396
397   nbr2_list = (struct nbr2_list_entry *)context;
398   nbr2_list->nbr2_list_timer = NULL;
399
400   nbr = nbr2_list->nbr2_nbr;
401   nbr2 = nbr2_list->neighbor_2;
402
403   nbr2->neighbor_2_pointer--;   /* XXX move to olsr_unlock_nbr2() */
404   olsr_delete_neighbor_pointer(nbr2, nbr);
405
406   olsr_delete_nbr2_list_entry(nbr2_list);
407 }
408
409
410 /**
411  * Print the registered neighbors and two hop neighbors to STDOUT.
412  *
413  * @return nada
414  */
415 void
416 olsr_print_neighbor_table(void)
417 {
418 #if !defined REMOVE_LOG_INFO
419   /* The whole function doesn't do anything else. */
420
421   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 39;
422   struct nbr_entry *nbr;
423   struct link_entry *lnk;
424   struct ipaddr_str buf;
425
426   OLSR_INFO(LOG_NEIGHTABLE, "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
427             "%*s  LQ    SYM   MPR   MPRS  will\n", olsr_wallclock_string(), ipwidth, "IP address");
428
429   OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
430
431     lnk = get_best_link_to_neighbor(&nbr->neighbor_main_addr);
432     if (!lnk) {
433       continue;
434     }
435
436     OLSR_INFO_NH(LOG_NEIGHTABLE, "%-*s  %s  %s  %s  %d\n",
437                  ipwidth, olsr_ip_to_string(&buf, &nbr->neighbor_main_addr),
438                  nbr->status == SYM ? "YES " : "NO  ",
439                  nbr->is_mpr ? "YES " : "NO  ",
440                  olsr_lookup_mprs_set(&nbr->neighbor_main_addr) == NULL ? "NO  " : "YES ", nbr->willingness);
441   } OLSR_FOR_ALL_NBR_ENTRIES_END(nbr);
442 #endif
443 }
444
445 /*
446  * Local Variables:
447  * c-basic-offset: 2
448  * indent-tabs-mode: nil
449  * End:
450  */