Put MPRSet capabilities into neighbor table.
[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 neighbor database */
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 pointers */
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   OLSR_FOR_ALL_NBR_CON_ENTRIES(nbr, connector) {
152     nbr2 = connector->nbr2;
153
154     olsr_delete_nbr_con(connector);
155     if (nbr2->con_tree.count == 0) {
156       olsr_delete_nbr2_entry(nbr2);
157     }
158   } OLSR_FOR_ALL_NBR_CON_ENTRIES_END(nbr, connector);
159
160   /* Remove from global neighbor tree */
161   avl_delete(&nbr_tree, &nbr->nbr_node);
162
163   olsr_cookie_free(nbr_mem_cookie, nbr);
164
165   changes_neighborhood = true;
166 }
167
168 /**
169  * Lookup a neighbor entry in the neighbortable based on an address.
170  * Unalias the passed in address before.
171  *
172  * @param addr the IP address of the neighbor to look up
173  *
174  * @return a pointer to the neighbor struct registered on the given
175  * address. NULL if not found.
176  */
177 struct nbr_entry *
178 olsr_lookup_nbr_entry(const union olsr_ip_addr *addr, bool lookupalias)
179 {
180   const union olsr_ip_addr *main_addr = NULL;
181   struct avl_node *node;
182
183   /*
184    * Find main address of node
185    */
186   if (lookupalias) {
187     main_addr = olsr_lookup_main_addr_by_alias(addr);
188   }
189   if (main_addr == NULL) {
190     main_addr = addr;
191   }
192
193   node = avl_find(&nbr_tree, addr);
194   if (node) {
195     return nbr_node_to_nbr(node);
196   }
197   return NULL;
198 }
199
200 int olsr_update_nbr_status(struct nbr_entry *entry, bool sym) {
201 #if !defined REMOVE_LOG_DEBUG
202   struct ipaddr_str buf;
203 #endif
204   /*
205    * Update neighbor entry
206    */
207
208   if (sym) {
209     /* N_status is set to SYM */
210     if (!entry->is_sym) {
211       struct nbr2_entry *two_hop_neighbor;
212
213       /* Delete posible 2 hop entry on this neighbor */
214       if ((two_hop_neighbor = olsr_lookup_nbr2_entry(&entry->nbr_addr, true)) != NULL) {
215         olsr_delete_nbr2_entry(two_hop_neighbor);
216       }
217
218       changes_neighborhood = true;
219       changes_topology = true;
220       if (olsr_cnf->tc_redundancy > 1)
221         signal_link_changes(true);
222     }
223     entry->is_sym = true;
224     OLSR_DEBUG(LOG_NEIGHTABLE, "Neighbor %s is now symmetric\n", olsr_ip_to_string(&buf, &entry->nbr_addr));
225   } else {
226     if (entry->is_sym) {
227       changes_neighborhood = true;
228       changes_topology = true;
229       if (olsr_cnf->tc_redundancy > 1)
230         signal_link_changes(true);
231     }
232     /* else N_status is set to NOT_SYM */
233     entry->is_sym = false;
234
235     OLSR_DEBUG(LOG_NEIGHTABLE, "Neighbor %s is now non-symmetric\n", olsr_ip_to_string(&buf, &entry->nbr_addr));
236   }
237
238   return entry->is_sym;
239 }
240
241 /**
242  * Insert a new entry to the two hop neighbor table.
243  *
244  * @param addr the entry to insert
245  * @return nada
246  */
247 struct nbr2_entry *olsr_add_nbr2_entry(const union olsr_ip_addr *addr) {
248 #if !defined REMOVE_LOG_DEBUG
249   struct ipaddr_str buf;
250 #endif
251   struct nbr2_entry *nbr2;
252
253   /*
254    * Check first if the entry exists.
255    */
256   nbr2 = olsr_lookup_nbr2_entry(addr, true);
257   if (nbr2) {
258     return nbr2;
259   }
260
261   OLSR_DEBUG(LOG_2NEIGH, "Adding 2 hop neighbor %s\n", olsr_ip_to_string(&buf, addr));
262
263   nbr2 = olsr_cookie_malloc(nbr2_mem_cookie);
264
265   /* Init neighbor reference subtree */
266   avl_init(&nbr2->con_tree, avl_comp_default);
267
268   nbr2->nbr2_addr = *addr;
269
270   /* Add to global neighbor 2 tree */
271   nbr2->nbr2_node.key = &nbr2->nbr2_addr;
272   avl_insert(&nbr2_tree, &nbr2->nbr2_node, AVL_DUP_NO);
273
274   return nbr2;
275 }
276
277 /**
278  * Delete an entry from the two hop neighbor table.
279  *
280  * @param nbr2 the two hop neighbor to delete.
281  */
282 void olsr_delete_nbr2_entry(struct nbr2_entry *nbr2) {
283   struct nbr_con *connector;
284
285 #if !defined REMOVE_LOG_DEBUG
286   struct ipaddr_str buf;
287 #endif
288
289   OLSR_DEBUG(LOG_NEIGHTABLE, "Delete 2-hop neighbor: %s\n", olsr_ip_to_string(&buf, &nbr2->nbr2_addr));
290
291   OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector) {
292     olsr_delete_nbr_con(connector);
293   } OLSR_FOR_ALL_NBR2_CON_ENTRIES_END(nbr2, connector);
294
295   /* Remove from global neighbor tree */
296   avl_delete(&nbr2_tree, &nbr2->nbr2_node);
297
298   olsr_cookie_free(nbr2_mem_cookie, nbr2);
299   changes_neighborhood = true;
300 }
301
302 struct nbr2_entry *olsr_lookup_nbr2_entry(const union olsr_ip_addr *addr, bool lookupalias) {
303   const union olsr_ip_addr *main_addr = NULL;
304   struct avl_node *node;
305
306   /*
307    * Find main address of node
308    */
309   if (lookupalias) {
310     main_addr = olsr_lookup_main_addr_by_alias(addr);
311   }
312   if (main_addr == NULL) {
313     main_addr = addr;
314   }
315
316   node = avl_find(&nbr2_tree, addr);
317   if (node) {
318     return nbr2_node_to_nbr2(node);
319   }
320   return NULL;
321 }
322
323 /**
324  * Links a one-hop neighbor with a 2-hop neighbor.
325  *
326  * @param nbr  the 1-hop neighbor
327  * @param nbr2 the 2-hop neighbor
328  * @param vtime validity time of the 2hop neighbor
329  */
330 struct nbr_con *olsr_link_nbr_nbr2(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_addr, olsr_reltime vtime) {
331   struct nbr_con *connector;
332   struct nbr2_entry *nbr2;
333
334   connector = olsr_lookup_nbr_con_entry(nbr, nbr2_addr);
335   if (connector) {
336     olsr_change_timer(connector->nbr2_list_timer, vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
337     return connector;
338   }
339
340   nbr2 = olsr_add_nbr2_entry(nbr2_addr);
341
342   connector = olsr_cookie_malloc(nbr_connector_mem_cookie);
343
344   connector->nbr = nbr;
345   connector->nbr2 = nbr2;
346   connector->nbr_tree_node.key = &nbr2->nbr2_addr;
347   connector->nbr2_tree_node.key = &nbr->nbr_addr;
348
349   avl_insert(&nbr->con_tree, &connector->nbr_tree_node, AVL_DUP_NO);
350   avl_insert(&nbr2->con_tree, &connector->nbr2_tree_node, AVL_DUP_NO);
351
352   connector->path_linkcost = LINK_COST_BROKEN;
353
354   connector->nbr2_list_timer = olsr_start_timer(vtime, OLSR_NBR2_LIST_JITTER,
355       OLSR_TIMER_ONESHOT, &olsr_expire_nbr_con, connector, nbr_connector_timer_cookie);
356
357   return connector;
358 }
359
360 /**
361  * Unlinks an one-hop and a 2-hop neighbor.
362  * Does NOT free the two-hop neighbor
363  *
364  * @param connector the connector between the neighbors
365  */
366 void olsr_delete_nbr_con(struct nbr_con *connector) {
367   olsr_stop_timer(connector->nbr2_list_timer);
368   connector->nbr2_list_timer = NULL;
369
370   avl_delete(&connector->nbr->con_tree, &connector->nbr_tree_node);
371   avl_delete(&connector->nbr2->con_tree, &connector->nbr2_tree_node);
372
373   olsr_cookie_free(nbr_connector_mem_cookie, connector);
374 }
375
376 /**
377  * Looks up the connection object of an one-hop neighbor to a
378  * 2-hop neighbor ip address.
379  *
380  * @param nbr the one-hop neighbor
381  * @param nbr2_addr the ip of the 2-hop neighbor
382  * @return nbr_con, or NULL if not found
383  */
384 struct nbr_con *olsr_lookup_nbr_con_entry(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_addr) {
385   struct avl_node *node;
386
387   node = avl_find(&nbr->con_tree, nbr2_addr);
388   if (node) {
389     return nbr_con_node_to_connector(node);
390   }
391   return NULL;
392 }
393
394 /**
395  * Looks up the connection object of an 2-hop neighbor to an
396  * one-hop neighbor ip address.
397  *
398  * @param nbr2 the 2-hop neighbor
399  * @param nbr_addr the ip of the one-hop neighbor
400  * @return nbr_con, or NULL if not found
401  */
402 struct nbr_con *olsr_lookup_nbr2_con_entry(struct nbr2_entry *nbr2, const union olsr_ip_addr *nbr_addr) {
403   struct avl_node *node;
404
405   node = avl_find(&nbr2->con_tree, nbr_addr);
406   if (node) {
407     return nbr2_con_node_to_connector(node);
408   }
409   return NULL;
410 }
411
412 static void olsr_expire_nbr_con(void *context) {
413   struct nbr_con *connector;
414
415   connector = context;
416   connector->nbr2_list_timer = NULL;
417
418   olsr_delete_nbr_con(connector);
419 }
420
421
422 /**
423  * Print the registered neighbors and two hop neighbors to STDOUT.
424  *
425  * @return nada
426  */
427 void
428 olsr_print_neighbor_table(void)
429 {
430 #if !defined REMOVE_LOG_INFO
431   /* The whole function doesn't do anything else. */
432
433   const int ipwidth = olsr_cnf->ip_version == AF_INET ? INET_ADDRSTRLEN : INET6_ADDRSTRLEN;
434   struct nbr_entry *nbr;
435   struct link_entry *lnk;
436   struct ipaddr_str buf;
437   struct nbr2_entry *nbr2;
438   struct nbr_con *connector;
439   struct lqtextbuffer lqbuffer;
440   bool first;
441
442   OLSR_INFO(LOG_NEIGHTABLE, "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
443             "%-*s\tSYM\tMPR\tMPRS\twill\n", olsr_wallclock_string(), ipwidth, "IP address");
444
445   OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
446
447     lnk = get_best_link_to_neighbor(&nbr->nbr_addr);
448     if (!lnk) {
449       continue;
450     }
451
452     OLSR_INFO_NH(LOG_NEIGHTABLE, "%-*s\t%s\t%s\t%s\t%d\n",
453                  ipwidth, olsr_ip_to_string(&buf, &nbr->nbr_addr),
454                  nbr->is_sym ? "YES" : "NO",
455                  nbr->is_mpr ? "YES" : "NO",
456                  nbr->mprs_count == 0  ? "NO  " : "YES ",
457                  nbr->willingness);
458   } OLSR_FOR_ALL_NBR_ENTRIES_END(nbr);
459
460   OLSR_INFO(LOG_2NEIGH, "\n--- %s ----------------------- TWO-HOP NEIGHBORS\n\n"
461             "IP addr (2-hop)  IP addr (1-hop)  Total cost\n", olsr_wallclock_string());
462
463   OLSR_FOR_ALL_NBR2_ENTRIES(nbr2) {
464     first = true;
465     OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector) {
466       OLSR_INFO_NH(LOG_2NEIGH, "%-*s  %-*s  %s\n",
467                    ipwidth, first ? olsr_ip_to_string(&buf, &nbr2->nbr2_addr) : "",
468                    ipwidth, olsr_ip_to_string(&buf, &connector->nbr->nbr_addr),
469                    get_linkcost_text(connector->path_linkcost, false, &lqbuffer));
470
471       first = false;
472     } OLSR_FOR_ALL_NBR2_CON_ENTRIES_END(nbr2, connector);
473   } OLSR_FOR_ALL_NBR2_ENTRIES_END(nbr2);
474
475 #endif
476 }
477
478 /*
479  * Local Variables:
480  * c-basic-offset: 2
481  * indent-tabs-mode: nil
482  * End:
483  */