e431f611237985f3cf87c5c45fc3c0fd93640ed2
[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 "mid_set.h"
45 #include "neighbor_table.h"
46 #include "olsr.h"
47 #include "scheduler.h"
48 #include "link_set.h"
49 #include "net_olsr.h"
50 #include "olsr_logging.h"
51
52 #include <stdlib.h>
53
54 /* Root of the one hop and two hop neighbor trees */
55 struct avl_tree nbr_tree;
56 struct avl_tree nbr2_tree;
57
58 /* Some cookies for stats keeping */
59 struct olsr_cookie_info *nbr2_mem_cookie = NULL;
60 struct olsr_cookie_info *nbr_mem_cookie = NULL;
61
62 struct olsr_cookie_info *nbr_connector_mem_cookie = NULL;
63 struct olsr_cookie_info *nbr_connector_timer_cookie = NULL;
64
65 static void olsr_expire_nbr_con(void *);
66
67 /*
68  * Init neighbor tables.
69  */
70 void
71 olsr_init_neighbor_table(void)
72 {
73   OLSR_INFO(LOG_NEIGHTABLE, "Initializing neighbor tree.\n");
74   avl_init(&nbr_tree, avl_comp_default);
75   avl_init(&nbr2_tree, avl_comp_default);
76
77   nbr_connector_timer_cookie = olsr_alloc_cookie("Neighbor connector", OLSR_COOKIE_TYPE_TIMER);
78   nbr_connector_mem_cookie = olsr_alloc_cookie("Neighbor connector", OLSR_COOKIE_TYPE_MEMORY);
79   olsr_cookie_set_memory_size(nbr_connector_mem_cookie, sizeof(struct nbr_con));
80
81   nbr_mem_cookie = olsr_alloc_cookie("1-Hop Neighbor", OLSR_COOKIE_TYPE_MEMORY);
82   olsr_cookie_set_memory_size(nbr_mem_cookie, sizeof(struct nbr_entry));
83
84   nbr2_mem_cookie = olsr_alloc_cookie("2-Hop Neighbor", OLSR_COOKIE_TYPE_MEMORY);
85   olsr_cookie_set_memory_size(nbr2_mem_cookie, sizeof(struct nbr2_entry));
86 }
87
88 /**
89  * Insert a neighbor entry in the neighbor table.
90  *
91  * @param addr the main address of the new node
92  * @return pointer to an already existting (or new created) neighbor entry
93  */
94 struct nbr_entry *
95 olsr_add_nbr_entry(const union olsr_ip_addr *addr)
96 {
97 #if !defined REMOVE_LOG_DEBUG
98   struct ipaddr_str buf;
99 #endif
100   struct nbr_entry *nbr;
101
102   /*
103    * Check if neighbor entry exists.
104    */
105   nbr = olsr_lookup_nbr_entry(addr, true);
106   if (nbr) {
107     return nbr;
108   }
109
110   OLSR_DEBUG(LOG_NEIGHTABLE, "Add 1-hop neighbor: %s\n", olsr_ip_to_string(&buf, addr));
111
112   nbr = olsr_cookie_malloc(nbr_mem_cookie);
113
114   /* Set address, willingness and status */
115   nbr->nbr_addr = *addr;
116   nbr->willingness = WILL_NEVER;
117   nbr->is_sym = false;
118
119   /* Init subtree for nbr2 connectors */
120   avl_init(&nbr->con_tree, avl_comp_default);
121
122   nbr->linkcount = 0;
123   nbr->is_mpr = false;
124   nbr->was_mpr = false;
125
126   /* Add to the global neighbor tree */
127   nbr->nbr_node.key = &nbr->nbr_addr;
128   avl_insert(&nbr_tree, &nbr->nbr_node, AVL_DUP_NO);
129
130   return nbr;
131 }
132
133 /**
134  * Delete a neighbor table entry.
135  *
136  * Remember: Deleting a neighbor entry results the deletion of its 2 hop neighbors list!!!
137  * @param addr the neighbor entry to delete
138  */
139 void
140 olsr_delete_nbr_entry(struct nbr_entry *nbr)
141 {
142   struct nbr_con *connector;
143   struct nbr2_entry *nbr2;
144
145 #if !defined REMOVE_LOG_DEBUG
146   struct ipaddr_str buf;
147 #endif
148
149   OLSR_DEBUG(LOG_NEIGHTABLE, "Delete 1-hop neighbor: %s\n", olsr_ip_to_string(&buf, &nbr->nbr_addr));
150
151   /*
152    * Remove all references pointing to this neighbor.
153    */
154   OLSR_FOR_ALL_NBR_CON_ENTRIES(nbr, connector) {
155     nbr2 = connector->nbr2;
156
157     olsr_delete_nbr_con(connector);
158     if (nbr2->con_tree.count == 0) {
159       olsr_delete_nbr2_entry(nbr2);
160     }
161   } OLSR_FOR_ALL_NBR_CON_ENTRIES_END(nbr, connector);
162
163   /* Remove from global neighbor tree */
164   avl_delete(&nbr_tree, &nbr->nbr_node);
165
166   olsr_cookie_free(nbr_mem_cookie, nbr);
167
168   changes_neighborhood = true;
169 }
170
171 /**
172  * Lookup a neighbor entry in the neighbortable based on an address.
173  * Unalias the passed in address before.
174  *
175  * @param addr the IP address of the neighbor to look up
176  *
177  * @return a pointer to the neighbor struct registered on the given
178  * address. NULL if not found.
179  */
180 struct nbr_entry *
181 olsr_lookup_nbr_entry(const union olsr_ip_addr *addr, bool lookupalias)
182 {
183   const union olsr_ip_addr *main_addr = NULL;
184   struct avl_node *node;
185
186   /*
187    * Find main address of node
188    */
189   if (lookupalias) {
190     main_addr = olsr_lookup_main_addr_by_alias(addr);
191   }
192   if (main_addr == NULL) {
193     main_addr = addr;
194   }
195
196   node = avl_find(&nbr_tree, addr);
197   if (node) {
198     return nbr_node_to_nbr(node);
199   }
200   return NULL;
201 }
202
203 int olsr_update_nbr_status(struct nbr_entry *entry, bool sym) {
204 #if !defined REMOVE_LOG_DEBUG
205   struct ipaddr_str buf;
206 #endif
207   /*
208    * Update neighbor entry
209    */
210
211   if (sym) {
212     /* N_status is set to SYM */
213     if (!entry->is_sym) {
214       struct nbr2_entry *two_hop_neighbor;
215
216       /* Delete posible 2 hop entry on this neighbor */
217       if ((two_hop_neighbor = olsr_lookup_nbr2_entry(&entry->nbr_addr, true)) != NULL) {
218         olsr_delete_nbr2_entry(two_hop_neighbor);
219       }
220
221       changes_neighborhood = true;
222       changes_topology = true;
223       if (olsr_cnf->tc_redundancy > 1)
224         signal_link_changes(true);
225     }
226     entry->is_sym = true;
227     OLSR_DEBUG(LOG_NEIGHTABLE, "Neighbor %s is now symmetric\n", olsr_ip_to_string(&buf, &entry->nbr_addr));
228   } else {
229     if (entry->is_sym) {
230       changes_neighborhood = true;
231       changes_topology = true;
232       if (olsr_cnf->tc_redundancy > 1)
233         signal_link_changes(true);
234     }
235     /* else N_status is set to NOT_SYM */
236     entry->is_sym = false;
237
238     OLSR_DEBUG(LOG_NEIGHTABLE, "Neighbor %s is now non-symmetric\n", olsr_ip_to_string(&buf, &entry->nbr_addr));
239   }
240
241   return entry->is_sym;
242 }
243
244 /**
245  * Insert a new entry to the two hop neighbor table.
246  *
247  * @param addr the entry to insert
248  * @return nada
249  */
250 struct nbr2_entry *
251 olsr_add_nbr2_entry(const union olsr_ip_addr *addr) {
252 #if !defined REMOVE_LOG_DEBUG
253   struct ipaddr_str buf;
254 #endif
255   struct nbr2_entry *nbr2;
256
257   /*
258    * Check first if the entry exists.
259    */
260   nbr2 = olsr_lookup_nbr2_entry(addr, true);
261   if (nbr2) {
262     return nbr2;
263   }
264
265   OLSR_DEBUG(LOG_2NEIGH, "Adding 2 hop neighbor %s\n", olsr_ip_to_string(&buf, addr));
266
267   nbr2 = olsr_cookie_malloc(nbr2_mem_cookie);
268
269   /* Init neighbor connector subtree */
270   avl_init(&nbr2->con_tree, avl_comp_default);
271
272   nbr2->nbr2_addr = *addr;
273
274   /* Add to global neighbor 2 tree */
275   nbr2->nbr2_node.key = &nbr2->nbr2_addr;
276   avl_insert(&nbr2_tree, &nbr2->nbr2_node, AVL_DUP_NO);
277
278   return nbr2;
279 }
280
281 /**
282  * Delete an entry from the two hop neighbor table.
283  *
284  * @param nbr2 the two hop neighbor to delete.
285  */
286 void
287 olsr_delete_nbr2_entry(struct nbr2_entry *nbr2) {
288   struct nbr_con *connector;
289
290 #if !defined REMOVE_LOG_DEBUG
291   struct ipaddr_str buf;
292 #endif
293
294   OLSR_DEBUG(LOG_NEIGHTABLE, "Delete 2-hop neighbor: %s\n", olsr_ip_to_string(&buf, &nbr2->nbr2_addr));
295
296   /*
297    * Remove all references pointing to this two hop neighbor.
298    */
299   OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector) {
300     olsr_delete_nbr_con(connector);
301   } OLSR_FOR_ALL_NBR2_CON_ENTRIES_END(nbr2, connector);
302
303   /* Remove from global neighbor tree */
304   avl_delete(&nbr2_tree, &nbr2->nbr2_node);
305
306   olsr_cookie_free(nbr2_mem_cookie, nbr2);
307   changes_neighborhood = true;
308 }
309
310 struct nbr2_entry *
311 olsr_lookup_nbr2_entry(const union olsr_ip_addr *addr, bool lookupalias) {
312   const union olsr_ip_addr *main_addr = NULL;
313   struct avl_node *node;
314
315   /*
316    * Find main address of node
317    */
318   if (lookupalias) {
319     main_addr = olsr_lookup_main_addr_by_alias(addr);
320   }
321   if (main_addr == NULL) {
322     main_addr = addr;
323   }
324
325   node = avl_find(&nbr2_tree, addr);
326   if (node) {
327     return nbr2_node_to_nbr2(node);
328   }
329   return NULL;
330 }
331
332 /**
333  * Links a one-hop neighbor with a 2-hop neighbor.
334  *
335  * @param nbr  the 1-hop neighbor
336  * @param nbr2 the 2-hop neighbor
337  * @param vtime validity time of the 2hop neighbor
338  */
339 struct nbr_con *
340 olsr_link_nbr_nbr2(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_addr, olsr_reltime vtime) {
341   struct nbr_con *connector;
342   struct nbr2_entry *nbr2;
343
344   /*
345    * Check if connector entry exists.
346    */
347   connector = olsr_lookup_nbr_con_entry(nbr, nbr2_addr);
348   if (connector) {
349     olsr_change_timer(connector->nbr2_con_timer, vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
350     return connector;
351   }
352
353   /*
354    * Generate a fresh one.
355    */
356   nbr2 = olsr_add_nbr2_entry(nbr2_addr);
357
358   connector = olsr_cookie_malloc(nbr_connector_mem_cookie);
359
360   connector->nbr = nbr;
361   connector->nbr2 = nbr2;
362   connector->nbr_tree_node.key = &nbr2->nbr2_addr;
363   connector->nbr2_tree_node.key = &nbr->nbr_addr;
364
365   avl_insert(&nbr->con_tree, &connector->nbr_tree_node, AVL_DUP_NO);
366   avl_insert(&nbr2->con_tree, &connector->nbr2_tree_node, AVL_DUP_NO);
367
368   connector->path_linkcost = LINK_COST_BROKEN;
369
370   connector->nbr2_con_timer = olsr_start_timer(vtime, OLSR_NBR2_LIST_JITTER,
371       OLSR_TIMER_ONESHOT, &olsr_expire_nbr_con, connector, nbr_connector_timer_cookie);
372
373   return connector;
374 }
375
376 /**
377  * Unlinks an one-hop and a 2-hop neighbor.
378  * Does NOT free the two-hop neighbor
379  *
380  * @param connector the connector between the neighbors
381  */
382 void
383 olsr_delete_nbr_con(struct nbr_con *connector) {
384   olsr_stop_timer(connector->nbr2_con_timer);
385   connector->nbr2_con_timer = NULL;
386
387   avl_delete(&connector->nbr->con_tree, &connector->nbr_tree_node);
388   avl_delete(&connector->nbr2->con_tree, &connector->nbr2_tree_node);
389
390   olsr_cookie_free(nbr_connector_mem_cookie, connector);
391 }
392
393 /**
394  * Looks up the connection object of an one-hop neighbor to a
395  * 2-hop neighbor ip address.
396  *
397  * @param nbr the one-hop neighbor
398  * @param nbr2_addr the ip of the 2-hop neighbor
399  * @return nbr_con, or NULL if not found
400  */
401 struct nbr_con *
402 olsr_lookup_nbr_con_entry(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_addr) {
403   struct avl_node *node;
404
405   node = avl_find(&nbr->con_tree, nbr2_addr);
406   if (node) {
407     return nbr_con_node_to_connector(node);
408   }
409   return NULL;
410 }
411
412 /**
413  * Looks up the connection object of an 2-hop neighbor to an
414  * one-hop neighbor ip address.
415  *
416  * @param nbr2 the 2-hop neighbor
417  * @param nbr_addr the ip of the one-hop neighbor
418  * @return nbr_con, or NULL if not found
419  */
420 struct nbr_con *
421 olsr_lookup_nbr2_con_entry(struct nbr2_entry *nbr2, const union olsr_ip_addr *nbr_addr) {
422   struct avl_node *node;
423
424   node = avl_find(&nbr2->con_tree, nbr_addr);
425   if (node) {
426     return nbr2_con_node_to_connector(node);
427   }
428   return NULL;
429 }
430
431 /*
432  * Wrapper for the timer callback.
433  */
434 static void
435 olsr_expire_nbr_con(void *context) {
436   struct nbr_con *connector;
437
438   connector = context;
439   connector->nbr2_con_timer = NULL;
440
441   olsr_delete_nbr_con(connector);
442 }
443
444
445 /**
446  * Print the registered neighbors and two hop neighbors to STDOUT.
447  *
448  * @return nada
449  */
450 void
451 olsr_print_neighbor_table(void)
452 {
453 #if !defined REMOVE_LOG_INFO
454   /* The whole function doesn't do anything else. */
455
456   const int ipwidth = olsr_cnf->ip_version == AF_INET ? INET_ADDRSTRLEN : INET6_ADDRSTRLEN;
457   struct nbr_entry *nbr;
458   struct link_entry *lnk;
459   struct ipaddr_str buf;
460   struct nbr2_entry *nbr2;
461   struct nbr_con *connector;
462   struct lqtextbuffer lqbuffer;
463   bool first;
464
465   OLSR_INFO(LOG_NEIGHTABLE, "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
466             "%-*s\tSYM\tMPR\tMPRS\twill\n", olsr_wallclock_string(), ipwidth, "IP address");
467
468   OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
469
470     lnk = get_best_link_to_neighbor(&nbr->nbr_addr);
471     if (!lnk) {
472       continue;
473     }
474
475     OLSR_INFO_NH(LOG_NEIGHTABLE, "%-*s\t%s\t%s\t%s\t%d\n",
476                  ipwidth, olsr_ip_to_string(&buf, &nbr->nbr_addr),
477                  nbr->is_sym ? "YES" : "NO",
478                  nbr->is_mpr ? "YES" : "NO",
479                  nbr->mprs_count == 0  ? "NO  " : "YES ",
480                  nbr->willingness);
481   } OLSR_FOR_ALL_NBR_ENTRIES_END(nbr);
482
483   OLSR_INFO(LOG_2NEIGH, "\n--- %s ----------------------- TWO-HOP NEIGHBORS\n\n"
484             "IP addr (2-hop)  IP addr (1-hop)  Total cost\n", olsr_wallclock_string());
485
486   OLSR_FOR_ALL_NBR2_ENTRIES(nbr2) {
487     first = true;
488     OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector) {
489       OLSR_INFO_NH(LOG_2NEIGH, "%-*s  %-*s  %s\n",
490                    ipwidth, first ? olsr_ip_to_string(&buf, &nbr2->nbr2_addr) : "",
491                    ipwidth, olsr_ip_to_string(&buf, &connector->nbr->nbr_addr),
492                    get_linkcost_text(connector->path_linkcost, false, &lqbuffer));
493
494       first = false;
495     } OLSR_FOR_ALL_NBR2_CON_ENTRIES_END(nbr2, connector);
496   } OLSR_FOR_ALL_NBR2_ENTRIES_END(nbr2);
497
498 #endif
499 }
500
501 /*
502  * Local Variables:
503  * c-basic-offset: 2
504  * indent-tabs-mode: nil
505  * End:
506  */