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