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