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