resolve merge conflicts
[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 nbr2_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->nbr2_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->nbr2 = nbr2;
111   olsr_lock_nbr2(nbr2);
112
113   nbr2_list->nbr2_nbr = nbr;    /* XXX nbr refcount protection */
114
115   /*
116    * Start the timer.
117    */
118   olsr_start_timer(vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT,
119                    &olsr_expire_nbr2_list, nbr2_list, nbr2_list_timer_cookie->ci_id);
120
121   /* Add to the nbr2 reference subtree */
122   nbr2_list->nbr2_list_node.key = &nbr2->nbr2_addr;
123   avl_insert(&nbr->nbr2_list_tree, &nbr2_list->nbr2_list_node, AVL_DUP_NO);
124
125   return nbr2_list;
126 }
127
128
129 /**
130  * Unlink, delete and free a nbr2_list entry.
131  */
132 static void
133 olsr_delete_nbr2_list_entry(struct nbr2_list_entry *nbr2_list)
134 {
135   struct nbr2_entry *nbr2;
136   struct nbr_entry *nbr;
137
138   nbr2 = nbr2_list->nbr2;
139   nbr = nbr2_list->nbr2_nbr;
140
141   /*
142    * Kill running timers.
143    */
144   olsr_stop_timer(nbr2_list->nbr2_list_timer);
145   nbr2_list->nbr2_list_timer = NULL;
146
147   /* Remove from neighbor2 reference subtree */
148   avl_delete(&nbr->nbr2_list_tree, &nbr2_list->nbr2_list_node);
149
150   /* Remove reference to a two-hop neighbor, unlock */
151   nbr2_list->nbr2 = NULL;
152   olsr_unlock_nbr2(nbr2);
153
154   olsr_cookie_free(nbr2_list_mem_cookie, nbr2_list);
155
156   /* Set flags to recalculate the MPR set and the routing table */
157   changes_neighborhood = true;
158   changes_topology = true;
159 }
160
161 /**
162  * Delete a two hop neighbor from a neighbors two hop neighbor list.
163  *
164  * @param neighbor the neighbor to delete the two hop neighbor from.
165  * @param address the IP address of the two hop neighbor to delete.
166  *
167  * @return positive if entry deleted
168  */
169 bool
170 olsr_delete_nbr2_list_entry_by_addr(struct nbr_entry *nbr, union olsr_ip_addr *addr)
171 {
172   struct nbr2_list_entry *nbr2_list;
173
174   nbr2_list = olsr_lookup_nbr2_list_entry(nbr, addr);
175
176   if (nbr2_list) {
177     olsr_delete_nbr2_list_entry(nbr2_list);
178     return true;
179   }
180
181   return false;
182 }
183
184
185 /**
186  * Check if a two hop neighbor is reachable via a given
187  * neighbor.
188  *
189  * @param nbr neighbor-entry to check via
190  * @param addr the addres of the two hop neighbor to find.
191  *
192  * @return a pointer to the nbr2_list_entry struct
193  * representing the two hop neighbor if found. NULL if not found.
194  */
195 struct nbr2_list_entry *
196 olsr_lookup_nbr2_list_entry(struct nbr_entry *nbr, const union olsr_ip_addr *addr)
197 {
198   struct avl_node *node;
199
200   node = avl_find(&nbr->nbr2_list_tree, addr);
201   if (node) {
202     return nbr2_list_node_to_nbr2_list(node);
203   }
204   return NULL;
205 }
206
207
208 /**
209  * Delete a neighbor table entry.
210  *
211  * Remember: Deleting a neighbor entry results the deletion of its 2 hop neighbors list!!!
212  * @param addr the neighbor entry to delete
213  *
214  * @return TRUE on success, FALSE otherwise.
215  */
216 bool
217 olsr_delete_nbr_entry(const union olsr_ip_addr * addr)
218 {
219   struct nbr2_list_entry *nbr2_list;
220   struct nbr_entry *nbr;
221
222 #if !defined REMOVE_LOG_DEBUG
223   struct ipaddr_str buf;
224 #endif
225
226   /*
227    * Find neighbor entry
228    */
229   nbr = olsr_lookup_nbr_entry(addr);
230   if (!nbr) {
231     return false;
232   }
233
234   OLSR_DEBUG(LOG_NEIGHTABLE, "Delete 1-hop neighbor: %s\n", olsr_ip_to_string(&buf, addr));
235
236   OLSR_FOR_ALL_NBR2_LIST_ENTRIES(nbr, nbr2_list) {
237     olsr_delete_neighbor_pointer(nbr2_list->nbr2, nbr);
238     olsr_delete_nbr2_list_entry(nbr2_list);
239   } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(nbr, nbr2_list);
240
241   /* Remove from global neighbor tree */
242   avl_delete(&nbr_tree, &nbr->nbr_node);
243
244   olsr_cookie_free(nbr_mem_cookie, nbr);
245
246   changes_neighborhood = true;
247
248   return true;
249 }
250
251
252 /**
253  * Insert a neighbor entry in the neighbor table.
254  *
255  * @param addr the main address of the new node
256  * @return pointer to an already existting (or new created) neighbor entry
257  */
258 struct nbr_entry *
259 olsr_add_nbr_entry(const union olsr_ip_addr *addr)
260 {
261 #if !defined REMOVE_LOG_DEBUG
262   struct ipaddr_str buf;
263 #endif
264   struct nbr_entry *nbr;
265
266   /*
267    * Check if neighbor entry exists.
268    */
269   nbr = olsr_lookup_nbr_entry(addr);
270   if (nbr) {
271     return nbr;
272   }
273
274   OLSR_DEBUG(LOG_NEIGHTABLE, "Add 1-hop neighbor: %s\n", olsr_ip_to_string(&buf, addr));
275
276   nbr = olsr_cookie_malloc(nbr_mem_cookie);
277
278   /* Set address, willingness and status */
279   nbr->neighbor_main_addr = *addr;
280   nbr->willingness = WILL_NEVER;
281   nbr->status = NOT_SYM;
282
283   /* Init subtree for nbr2 pointers */
284   avl_init(&nbr->nbr2_list_tree, avl_comp_default);
285
286   nbr->linkcount = 0;
287   nbr->is_mpr = false;
288   nbr->was_mpr = false;
289
290   /* Add to the global neighbor tree */
291   nbr->nbr_node.key = &nbr->neighbor_main_addr;
292   avl_insert(&nbr_tree, &nbr->nbr_node, AVL_DUP_NO);
293
294   return nbr;
295 }
296
297
298
299 /**
300  * Lookup a neighbor entry in the neighbortable based on an address.
301  * Unalias the passed in address before.
302  * 
303  * @param addr the IP address of the neighbor to look up
304  *
305  * @return a pointer to the neighbor struct registered on the given
306  * address. NULL if not found.
307  */
308 struct nbr_entry *
309 olsr_lookup_nbr_entry(const union olsr_ip_addr *addr)
310 {
311   const union olsr_ip_addr *main_addr;
312
313   /*
314    * Find main address of node
315    */
316   main_addr = olsr_lookup_main_addr_by_alias(addr);
317   if (!main_addr) {
318     main_addr = addr;
319   }
320
321   return olsr_lookup_nbr_entry_alias(main_addr);
322 }
323
324
325 /**
326  * Lookup a neighbor entry in the neighbortable based on an address.
327  *
328  * @param addr the IP address of the neighbor to look up
329  *
330  * @return a pointer to the neighbor struct registered on the given
331  *  address. NULL if not found.
332  */
333 struct nbr_entry *
334 olsr_lookup_nbr_entry_alias(const union olsr_ip_addr *addr)
335 {
336   struct avl_node *node;
337
338   node = avl_find(&nbr_tree, addr);
339   if (node) {
340     return nbr_node_to_nbr(node);
341   }
342   return NULL;
343 }
344
345
346 int
347 olsr_update_nbr_status(struct nbr_entry *entry, int lnk)
348 {
349   /*
350    * Update neighbor entry
351    */
352
353   if (lnk == SYM_LINK) {
354     /* N_status is set to SYM */
355     if (entry->status == NOT_SYM) {
356       struct nbr2_entry *two_hop_neighbor;
357
358       /* Delete posible 2 hop entry on this neighbor */
359       if ((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr)) != NULL) {
360         olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
361       }
362
363       changes_neighborhood = true;
364       changes_topology = true;
365       if (olsr_cnf->tc_redundancy > 1)
366         signal_link_changes(true);
367     }
368     entry->status = SYM;
369   } else {
370     if (entry->status == SYM) {
371       changes_neighborhood = true;
372       changes_topology = true;
373       if (olsr_cnf->tc_redundancy > 1)
374         signal_link_changes(true);
375     }
376     /* else N_status is set to NOT_SYM */
377     entry->status = NOT_SYM;
378     /* remove neighbor from routing list */
379   }
380
381   return entry->status;
382 }
383
384
385 /**
386  * Callback for the nbr2_list timer.
387  */
388 void
389 olsr_expire_nbr2_list(void *context)
390 {
391   struct nbr2_list_entry *nbr2_list;
392   struct nbr_entry *nbr;
393   struct nbr2_entry *nbr2;
394
395   nbr2_list = (struct nbr2_list_entry *)context;
396   nbr2_list->nbr2_list_timer = NULL;
397
398   nbr = nbr2_list->nbr2_nbr;
399   nbr2 = nbr2_list->nbr2;
400
401   olsr_delete_neighbor_pointer(nbr2, nbr);
402   olsr_unlock_nbr2(nbr2);
403
404   olsr_delete_nbr2_list_entry(nbr2_list);
405 }
406
407
408 /**
409  * Print the registered neighbors and two hop neighbors to STDOUT.
410  *
411  * @return nada
412  */
413 void
414 olsr_print_neighbor_table(void)
415 {
416 #if !defined REMOVE_LOG_INFO
417   /* The whole function doesn't do anything else. */
418
419   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 39;
420   struct nbr_entry *nbr;
421   struct link_entry *lnk;
422   struct ipaddr_str buf;
423
424   OLSR_INFO(LOG_NEIGHTABLE, "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
425             "%*s  LQ    SYM   MPR   MPRS  will\n", olsr_wallclock_string(), ipwidth, "IP address");
426
427   OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
428
429     lnk = get_best_link_to_neighbor(&nbr->neighbor_main_addr);
430     if (!lnk) {
431       continue;
432     }
433
434     OLSR_INFO_NH(LOG_NEIGHTABLE, "%-*s  %s  %s  %s  %d\n",
435                  ipwidth, olsr_ip_to_string(&buf, &nbr->neighbor_main_addr),
436                  nbr->status == SYM ? "YES " : "NO  ",
437                  nbr->is_mpr ? "YES " : "NO  ",
438                  olsr_lookup_mprs_set(&nbr->neighbor_main_addr) == NULL ? "NO  " : "YES ", nbr->willingness);
439   } OLSR_FOR_ALL_NBR_ENTRIES_END(nbr);
440 #endif
441 }
442
443 /*
444  * Local Variables:
445  * c-basic-offset: 2
446  * indent-tabs-mode: nil
447  * End:
448  */