Merge branch 'master' into scheduler_cleanup
[olsrd.git] / src / mid_set.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 "olsr.h"
46 #include "olsr_timer.h"
47 #include "olsr_socket.h"
48 #include "neighbor_table.h"
49 #include "link_set.h"
50 #include "tc_set.h"
51 #include "net_olsr.h"
52 #include "olsr_memcookie.h"
53 #include "olsr_logging.h"
54 #include "olsr_protocol.h"
55
56 #include <assert.h>
57 #include <stdlib.h>
58
59 static struct mid_entry *olsr_lookup_mid_entry(const union olsr_ip_addr *);
60 static void olsr_expire_mid_entries(void *context);
61
62 /* Root of the MID tree */
63 struct avl_tree mid_tree;
64
65 /* validity timer of MID entries */
66 static struct olsr_memcookie_info *mid_address_mem_cookie = NULL;
67 static struct olsr_timer_info *mid_validity_timer_info = NULL;
68
69 /**
70  * Initialize the MID set
71  */
72 void
73 olsr_init_mid_set(void)
74 {
75   OLSR_INFO(LOG_MID, "Initialize MID set...\n");
76
77   avl_init(&mid_tree, avl_comp_default, false, NULL);
78
79   /*
80    * Get some cookies for getting stats to ease troubleshooting.
81    */
82   mid_validity_timer_info = olsr_timer_add("MID validity", &olsr_expire_mid_entries, false);
83
84   mid_address_mem_cookie = olsr_memcookie_add("MID address", sizeof(struct mid_entry));
85 }
86
87 /**
88  * Wrapper for the timer callback.
89  */
90 static void
91 olsr_expire_mid_entries(void *context)
92 {
93   struct mid_entry *mid = context;
94 #if !defined REMOVE_LOG_DEBUG
95   struct ipaddr_str buf;
96 #endif
97
98   OLSR_DEBUG(LOG_MID, "MID aliases for %s timed out\n", olsr_ip_to_string(&buf, &mid->mid_alias_addr));
99
100   olsr_delete_mid_entry(mid);
101 }
102
103 /**
104  * Set the mid set expiration timer.
105  *
106  * all timer setting shall be done using this function.
107  * The timer param is a relative timer expressed in milliseconds.
108  */
109 static void
110 olsr_set_mid_timer(struct mid_entry *mid, uint32_t rel_timer)
111 {
112   olsr_timer_set(&mid->mid_timer, rel_timer, OLSR_MID_JITTER, mid, mid_validity_timer_info);
113 }
114
115 /**
116  * Delete possible duplicate entries in tc set.
117  * This optimization is not specified in rfc3626.
118  */
119 static void
120 olsr_flush_tc_duplicates(struct mid_entry *alias) {
121   struct tc_entry *tc;
122   tc = olsr_lookup_tc_entry(&alias->mid_alias_addr);
123   if (tc) {
124     olsr_delete_tc_entry(tc);
125   }
126 }
127
128 /**
129  * Delete possible duplicate entries in 2 hop set
130  * and delete duplicate neighbor entries. Redirect
131  * link entries to the correct neighbor entry.
132  * This optimization is not specified in rfc3626.
133  */
134 static void
135 olsr_flush_nbr2_duplicates(struct tc_entry *tc)
136 {
137   struct mid_entry *alias, *iterator;
138 #if !defined REMOVE_LOG_DEBUG
139   struct ipaddr_str buf1, buf2;
140 #endif
141
142   OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias, iterator) {
143     struct nbr_entry *nbr;
144     struct nbr2_entry *nbr2 = olsr_lookup_nbr2_entry(&alias->mid_alias_addr, false);
145
146     /* Delete possible 2 hop neighbor */
147     if (nbr2) {
148       OLSR_DEBUG(LOG_MID, "Delete 2hop neighbor: %s to %s\n",
149                  olsr_ip_to_string(&buf1, &alias->mid_alias_addr), olsr_ip_to_string(&buf2, &tc->addr));
150
151       olsr_delete_nbr2_entry(nbr2);
152       changes_neighborhood = true;
153     }
154
155     /* Delete a possible neighbor entry */
156     nbr = olsr_lookup_nbr_entry(&alias->mid_alias_addr, false);
157     if (nbr) {
158       struct nbr_entry *real_nbr = olsr_lookup_nbr_entry(&tc->addr, false);
159       if (real_nbr) {
160
161         OLSR_DEBUG(LOG_MID, "Delete bogus neighbor entry %s (real %s)\n",
162                    olsr_ip_to_string(&buf1, &alias->mid_alias_addr), olsr_ip_to_string(&buf2, &tc->addr));
163
164         replace_neighbor_link_set(nbr, real_nbr);
165
166         olsr_delete_nbr_entry(nbr);
167
168         changes_neighborhood = true;
169       }
170     }
171   }
172 }
173
174 /**
175  * If we have an entry for this alias in neighbortable, we better adjust it's
176  * main address, because otherwise a fatal inconsistency between
177  * neighbortable and link_set will be created by way of this mid entry.
178  */
179 static void
180 olsr_fixup_mid_main_addr(const union olsr_ip_addr *main_addr, const union olsr_ip_addr *alias_addr)
181 {
182   struct nbr_entry *nbr_new, *nbr_old;
183   struct mid_entry *mid_old;
184   int ne_ref_rp_count;
185 #if !defined REMOVE_LOG_DEBUG
186   struct ipaddr_str buf1, buf2;
187 #endif
188
189   nbr_old = olsr_lookup_nbr_entry(alias_addr, false);
190   if (!nbr_old) {
191     return;
192   }
193
194   OLSR_DEBUG(LOG_MID, "Main address change %s -> %s detected.\n",
195              olsr_ip_to_string(&buf1, alias_addr), olsr_ip_to_string(&buf2, main_addr));
196
197   olsr_delete_nbr_entry(nbr_old);
198   nbr_new = olsr_add_nbr_entry(main_addr);
199
200   /* Adjust pointers to neighbortable-entry in link_set */
201   ne_ref_rp_count = replace_neighbor_link_set(nbr_old, nbr_new);
202
203   if (ne_ref_rp_count > 0) {
204     OLSR_DEBUG(LOG_MID, "Performed %d neighbortable-pointer replacements "
205                "(%p -> %p) in link_set.\n", ne_ref_rp_count, nbr_old, nbr_new);
206   }
207
208   mid_old = olsr_lookup_mid_entry(alias_addr);
209   if (mid_old) {
210     /*
211      * We knew aliases to the previous main address.
212      * Better forget about them now.
213      */
214     OLSR_DEBUG(LOG_MID, "Flush aliases for old main address.\n");
215     olsr_flush_mid_entries(mid_old->mid_tc);
216   }
217 }
218
219 /**
220  * Insert a fresh alias address for a node.
221  *
222  * @param main_add the main address of the node
223  * @param alias the alias address to insert
224  * @param vtime the validity time
225  * @param seq the sequence number to register a new node with
226  */
227 static struct mid_entry *
228 olsr_insert_mid_entry(const union olsr_ip_addr *main_addr,
229                       const union olsr_ip_addr *alias_addr, uint32_t vtime)
230 {
231   struct tc_entry *tc;
232   struct mid_entry *alias;
233 #if !defined REMOVE_LOG_DEBUG
234   struct ipaddr_str buf1, buf2;
235 #endif
236
237   OLSR_DEBUG(LOG_MID, "Inserting alias %s for %s\n", olsr_ip_to_string(&buf1, alias_addr), olsr_ip_to_string(&buf2, main_addr));
238
239   /*
240    * Locate first the hookup point
241    */
242   tc = olsr_locate_tc_entry(main_addr);
243   assert(tc);
244
245   alias = olsr_memcookie_malloc(mid_address_mem_cookie);
246   alias->mid_alias_addr = *alias_addr;
247   alias->mid_tc = tc;
248
249   /*
250    * Insert into the per-tc mid subtree.
251    */
252   alias->mid_tc_node.key = &alias->mid_alias_addr;
253   avl_insert(&tc->mid_tree, &alias->mid_tc_node);
254
255   /*
256    * Insert into the global mid tree.
257    */
258   alias->mid_node.key = &alias->mid_alias_addr;
259   avl_insert(&mid_tree, &alias->mid_node);
260
261   /*
262    * Add a rt_path for the alias.
263    */
264   olsr_insert_routing_table(&alias->mid_alias_addr, 8 * olsr_cnf->ipsize, main_addr, OLSR_RT_ORIGIN_MID);
265
266   olsr_set_mid_timer(alias, vtime);
267
268   return alias;
269 }
270
271 /**
272  * Update an alias address for a node.
273  * If the main address is not registered
274  * then a new entry is created.
275  *
276  * @param main_add the main address of the node
277  * @param alias the alias address to insert
278  * @param vtime the validity time
279  * @param seq the sequence number to register a new node with
280  */
281 static void
282 olsr_update_mid_entry(const union olsr_ip_addr *main_addr,
283                       const union olsr_ip_addr *alias_addr, uint32_t vtime)
284 {
285   struct mid_entry *alias;
286
287   if (!olsr_validate_address(alias_addr)) {
288     return;
289   }
290
291   /*
292    * Check first if the alias already exists.
293    */
294   alias = olsr_lookup_mid_entry(alias_addr);
295   if (alias) {
296     /* Refresh the timer. */
297     olsr_set_mid_timer(alias, vtime);
298     return;
299   }
300
301   /*
302    * This is a fresh alias.
303    */
304   alias = olsr_insert_mid_entry(main_addr, alias_addr, vtime);
305
306   /*
307    * Do the needful if one of our neighbors has changed its main address.
308    */
309   olsr_fixup_mid_main_addr(main_addr, alias_addr);
310   olsr_flush_nbr2_duplicates(alias->mid_tc);
311   olsr_flush_tc_duplicates(alias);
312
313   /*
314    * Recalculate topology.
315    */
316   changes_neighborhood = true;
317   changes_topology = true;
318 }
319
320 /**
321  * Lookup a MID alias hanging off a tc_entry by address
322  *
323  * @param adr the alias address to check
324  * @return the MID address entry or NULL if not found
325  */
326 struct mid_entry *
327 olsr_lookup_tc_mid_entry(struct tc_entry *tc, const union olsr_ip_addr *adr)
328 {
329   struct mid_entry *mid;
330   mid = avl_find_element(&tc->mid_tree, adr, mid, mid_tc_node);
331   return mid;
332 }
333
334 /**
335  * Lookup an MID alias by address in the global tree.
336  *
337  * @param adr the alias address to check
338  * @return the MID address entry or NULL if not found
339  */
340 static struct mid_entry *
341 olsr_lookup_mid_entry(const union olsr_ip_addr *adr)
342 {
343   struct mid_entry *mid;
344   mid = avl_find_element(&mid_tree, adr, mid, mid_node);
345   return mid;
346 }
347
348 /**
349  * Lookup the main address for an MID alias address
350  *
351  * @param adr the alias address to check
352  * @return the main address registered on the alias
353  * or NULL if not found
354  */
355 union olsr_ip_addr *
356 olsr_lookup_main_addr_by_alias(const union olsr_ip_addr *adr)
357 {
358   struct mid_entry *alias;
359
360   alias = olsr_lookup_mid_entry(adr);
361
362   return (alias ? &alias->mid_tc->addr : NULL);
363 }
364
365 /**
366  * Delete a single MID alias.
367  *
368  * @param alias the alias to delete.
369  */
370 void
371 olsr_delete_mid_entry(struct mid_entry *alias)
372 {
373   struct tc_entry *tc;
374
375   tc = alias->mid_tc;
376
377   /* kill timer */
378   olsr_timer_stop(alias->mid_timer);
379   alias->mid_timer = NULL;
380
381   /*
382    * Delete the rt_path for the alias.
383    */
384   olsr_delete_routing_table(&alias->mid_alias_addr, 8 * olsr_cnf->ipsize, &tc->addr, OLSR_RT_ORIGIN_MID);
385
386   /*
387    * Remove from the per-tc tree.
388    */
389   avl_delete(&tc->mid_tree, &alias->mid_tc_node);
390
391   /*
392    * Remove from the global tree.
393    */
394   avl_delete(&mid_tree, &alias->mid_node);
395
396   olsr_memcookie_free(mid_address_mem_cookie, alias);
397 }
398
399 /**
400  * Delete all the MID aliases hanging off a tc entry.
401  *
402  * @param entry the tc entry holding the aliases.
403  */
404 void
405 olsr_flush_mid_entries(struct tc_entry *tc)
406 {
407   struct mid_entry *alias, *iterator;
408   OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias, iterator) {
409     olsr_delete_mid_entry(alias);
410   }
411 }
412
413 /**
414  * Print all MID entries
415  * For debuging purposes
416  */
417 void
418 olsr_print_mid_set(void)
419 {
420 #if !defined REMOVE_LOG_INFO
421   struct tc_entry *tc, *tc_iterator;
422   struct mid_entry *alias, *mid_iterator;
423   struct ipaddr_str buf1, buf2;
424   struct timeval_buf timebuf;
425
426   OLSR_INFO(LOG_MID, "\n--- %s ------------------------------------------------- MID\n\n",
427       olsr_timer_getWallclockString(&timebuf));
428
429   OLSR_FOR_ALL_TC_ENTRIES(tc, tc_iterator) {
430     OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias, mid_iterator) {
431       OLSR_INFO_NH(LOG_MID, "%-15s: %s\n", olsr_ip_to_string(&buf1, &tc->addr), olsr_ip_to_string(&buf2, &alias->mid_alias_addr));
432     }
433   }
434 #endif
435 }
436
437 /**
438  * Process an incoming MID message.
439  */
440 void
441 olsr_input_mid(struct olsr_message *msg,
442     struct interface *input_if __attribute__ ((unused)),
443     union olsr_ip_addr *from_addr, enum duplicate_status status)
444 {
445   const uint8_t *curr;
446   union olsr_ip_addr alias;
447   struct tc_entry *tc;
448 #if !defined REMOVE_LOG_DEBUG
449   struct ipaddr_str buf;
450 #endif
451
452   /* We are only interested in MID message types. */
453   if (msg->type != MID_MESSAGE) {
454     return;
455   }
456
457   /*
458    * If the sender interface (NB: not originator) of this message
459    * is not in the symmetric 1-hop neighborhood of this node, the
460    * message MUST be discarded.
461    */
462   if (check_neighbor_link(from_addr) != SYM_LINK) {
463     OLSR_DEBUG(LOG_MID, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
464     return;
465   }
466
467   tc = olsr_locate_tc_entry(&msg->originator);
468
469   if (status != RESET_SEQNO_OLSR_MESSAGE && tc->mid_seq != -1 && olsr_seqno_diff(msg->seqno, tc->mid_seq) <= 0) {
470     /* this MID is too old, discard it */
471     OLSR_DEBUG(LOG_MID, "Received too old mid from %s: %d < %d\n",
472         olsr_ip_to_string(&buf, from_addr), msg->seqno, tc->mid_seq);
473     return;
474   }
475   tc->mid_seq = msg->seqno;
476
477   OLSR_DEBUG(LOG_MID, "Processing MID from %s with %d aliases, seq 0x%04x\n",
478              olsr_ip_to_string(&buf, &msg->originator), (int)((msg->end - msg->payload)/olsr_cnf->ipsize), msg->seqno);
479
480
481   curr = msg->payload;
482
483
484   /*
485    * Now walk the list of alias advertisements one by one.
486    */
487   while (curr + olsr_cnf->ipsize <= msg->end) {
488     pkt_get_ipaddress(&curr, &alias);
489     olsr_update_mid_entry(&msg->originator, &alias, msg->vtime);
490   }
491 }
492
493 void
494 generate_mid(void *p  __attribute__ ((unused))) {
495   struct interface *ifp, *allif, *iterator;
496   struct olsr_message msg;
497   uint8_t msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE] __attribute__ ((aligned));
498   uint8_t *curr = msg_buffer;
499   uint8_t *length_field, *last;
500   bool sendMID = false;
501
502   OLSR_INFO(LOG_PACKET_CREATION, "Building MID\n-------------------\n");
503
504   msg.type = MID_MESSAGE;
505   msg.vtime = olsr_cnf->mid_params.validity_time;
506   msg.size = 0; // fill in later
507   msg.originator = olsr_cnf->router_id;
508   msg.ttl = MAX_TTL;
509   msg.hopcnt = 0;
510   msg.seqno = get_msg_seqno();
511
512   curr = msg_buffer;
513
514   length_field = olsr_put_msg_hdr(&curr, &msg);
515
516   last = msg_buffer + sizeof(msg_buffer) - olsr_cnf->ipsize;
517   OLSR_FOR_ALL_INTERFACES(allif, iterator) {
518     if (olsr_ipcmp(&olsr_cnf->router_id, &allif->ip_addr) != 0) {
519       if (curr > last) {
520         OLSR_WARN(LOG_MID, "Warning, too many interfaces for MID packet\n");
521         return;
522       }
523       pkt_put_ipaddress(&curr, &allif->ip_addr);
524       sendMID = true;
525     }
526   }
527
528   if (!sendMID) {
529     return;
530   }
531
532   pkt_put_u16(&length_field, curr - msg_buffer);
533
534   OLSR_FOR_ALL_INTERFACES(ifp, iterator) {
535     if (net_outbuffer_bytes_left(ifp) < curr - msg_buffer) {
536       net_output(ifp);
537       set_buffer_timer(ifp);
538     }
539     net_outbuffer_push(ifp, msg_buffer, curr - msg_buffer);
540   }
541 }
542 /*
543  * Local Variables:
544  * c-basic-offset: 2
545  * indent-tabs-mode: nil
546  * End:
547  */