1 /*
2 * The olsr.org Optimized Link-State Routing daemon (olsrd)
3 *
4 * (c) by the OLSR project
5 *
6 * See our Git repository to find out who worked on this file
7 * and thus is a copyright holder on it.
8 *
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 *
15 * * Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * * Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in
19 * the documentation and/or other materials provided with the
20 * distribution.
21 * * Neither the name of olsr.org, olsrd nor the names of its
22 * contributors may be used to endorse or promote products derived
23 * from this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
29 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
31 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
35 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 * POSSIBILITY OF SUCH DAMAGE.
37 *
38 * Visit http://www.olsr.org for more information.
39 *
40 * If you find this software useful feel free to make a donation
41 * to the project. For more information see the website or contact
42 * the copyright holders.
43 *
44 */
45 #include <assert.h>
46
47 #include "ipcalc.h"
48 #include "defs.h"
49 #include "two_hop_neighbor_table.h"
50 #include "mid_set.h"
51 #include "olsr.h"
52 #include "rebuild_packet.h"
53 #include "scheduler.h"
54 #include "neighbor_table.h"
55 #include "link_set.h"
56 #include "tc_set.h"
57 #include "packet.h" /* struct mid_alias */
58 #include "net_olsr.h"
59 #include "duplicate_handler.h"
60
61 struct mid_entry mid_set[HASHSIZE];
62 struct mid_address reverse_mid_set[HASHSIZE];
63
64 struct mid_entry *mid_lookup_entry_bymain(const union olsr_ip_addr *adr);
65
66 /**
67 * Initialize the MID set
68 *
69 */
70 int
olsr_init_mid_set(void)71 olsr_init_mid_set(void)
72 {
73 int idx;
74
75 OLSR_PRINTF(5, "MID: init\n");
76
77 for (idx = 0; idx < HASHSIZE; idx++) {
78 mid_set[idx].next = &mid_set[idx];
79 mid_set[idx].prev = &mid_set[idx];
80
81 reverse_mid_set[idx].next = &reverse_mid_set[idx];
82 reverse_mid_set[idx].prev = &reverse_mid_set[idx];
83 }
84
85 return 1;
86 }
87
olsr_delete_all_mid_entries(void)88 void olsr_delete_all_mid_entries(void) {
89 int hash;
90
91 for (hash = 0; hash < HASHSIZE; hash++) {
92 while (mid_set[hash].next != &mid_set[hash]) {
93 olsr_delete_mid_entry(mid_set[hash].next);
94 }
95 }
96 }
97
olsr_cleanup_mid(union olsr_ip_addr * orig)98 void olsr_cleanup_mid(union olsr_ip_addr *orig) {
99 struct mid_entry *mid;
100 mid = mid_lookup_entry_bymain(orig);
101 if (mid) {
102 olsr_delete_mid_entry(mid);
103 }
104 }
105
106 /**
107 * Wrapper for the timer callback.
108 */
109 static void
olsr_expire_mid_entry(void * context)110 olsr_expire_mid_entry(void *context)
111 {
112 #ifdef DEBUG
113 struct ipaddr_str buf;
114 #endif /* DEBUG */
115 struct mid_entry *mid;
116
117 mid = (struct mid_entry *)context;
118 mid->mid_timer = NULL;
119
120 #ifdef DEBUG
121 OLSR_PRINTF(1, "MID info for %s timed out.. deleting it\n", olsr_ip_to_string(&buf, &mid->main_addr));
122 #endif /* DEBUG */
123
124 olsr_delete_mid_entry(mid);
125 }
126
127 /**
128 * Set the mid set expiration timer.
129 *
130 * all timer setting shall be done using this function.
131 * The timer param is a relative timer expressed in milliseconds.
132 */
133 static void
olsr_set_mid_timer(struct mid_entry * mid,olsr_reltime rel_timer)134 olsr_set_mid_timer(struct mid_entry *mid, olsr_reltime rel_timer)
135 {
136 int32_t willFireIn = -1;
137 if (mid->mid_timer != NULL) willFireIn = olsr_getTimeDue(mid->mid_timer->timer_clock);
138
139 if (willFireIn < 0 || (olsr_reltime)willFireIn < rel_timer) {
140 olsr_set_timer(&mid->mid_timer, rel_timer, 0, OLSR_TIMER_ONESHOT, &olsr_expire_mid_entry, mid, 0);
141 }
142 }
143
144 /**
145 * Insert a new interface alias to the interface association set.
146 * If the main interface of the association is not yet registered
147 * in the set a new entry is created.
148 *
149 * @param m_addr the main address of the node
150 * @param alias the alias address to insert
151 * @param vtime the expiration time
152 * @return false if mid_address is unnecessary, true otherwise
153 */
154
155 static bool
insert_mid_tuple(union olsr_ip_addr * m_addr,struct mid_address * alias,olsr_reltime vtime)156 insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, olsr_reltime vtime)
157 {
158 struct mid_entry *tmp;
159 struct mid_address *tmp_adr;
160 uint32_t hash, alias_hash;
161 union olsr_ip_addr *registered_m_addr;
162
163 hash = olsr_ip_hashing(m_addr);
164 alias_hash = olsr_ip_hashing(&alias->alias);
165
166 /* Check for registered entry */
167 for (tmp = mid_set[hash].next; tmp != &mid_set[hash]; tmp = tmp->next) {
168 if (ipequal(&tmp->main_addr, m_addr))
169 break;
170 }
171
172 /* Check if alias is already registered with m_addr */
173 registered_m_addr = mid_lookup_main_addr(&alias->alias);
174 if (registered_m_addr != NULL && ipequal(registered_m_addr, m_addr)) {
175 /* Alias is already registered with main address. Nothing to do here. */
176 return false;
177 }
178
179 /*
180 * Add a rt_path for the alias.
181 */
182 olsr_insert_routing_table(&alias->alias, olsr_cnf->maxplen, m_addr, OLSR_RT_ORIGIN_MID);
183
184 /*If the address was registered */
185 if (tmp != &mid_set[hash]) {
186 tmp_adr = tmp->aliases;
187 tmp->aliases = alias;
188 alias->main_entry = tmp;
189 QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
190 alias->next_alias = tmp_adr;
191 olsr_set_mid_timer(tmp, vtime);
192 } else {
193
194 /*Create new node */
195 tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
196
197 tmp->aliases = alias;
198 alias->main_entry = tmp;
199 QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
200 tmp->main_addr = *m_addr;
201 olsr_set_mid_timer(tmp, vtime);
202
203 /* Queue */
204 QUEUE_ELEM(mid_set[hash], tmp);
205 }
206
207 /*
208 * Delete possible duplicate entries in 2 hop set
209 * and delete duplicate neighbor entries. Redirect
210 * link entries to the correct neighbor entry.
211 *
212 *THIS OPTIMIZATION IS NOT SPECIFIED IN RFC3626
213 */
214
215 tmp_adr = alias;
216
217 while (tmp_adr) {
218 struct neighbor_2_entry *tmp_2_neighbor;
219 struct neighbor_entry *tmp_neigh, *real_neigh;
220
221 /* Delete possible 2 hop neighbor */
222 if ((tmp_2_neighbor = olsr_lookup_two_hop_neighbor_table_mid(&tmp_adr->alias)) != NULL) {
223 struct ipaddr_str buf;
224 OLSR_PRINTF(1, "Deleting 2 hop node from MID: %s to ", olsr_ip_to_string(&buf, &tmp_adr->alias));
225 OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, m_addr));
226
227 olsr_delete_two_hop_neighbor_table(tmp_2_neighbor);
228
229 changes_neighborhood = true;
230 }
231
232 /* Delete a possible neighbor entry */
233 if (((tmp_neigh = olsr_lookup_neighbor_table_alias(&tmp_adr->alias)) != NULL)
234 && ((real_neigh = olsr_lookup_neighbor_table_alias(m_addr)) != NULL)) {
235 struct ipaddr_str buf;
236 OLSR_PRINTF(1, "[MID]Deleting bogus neighbor entry %s real ", olsr_ip_to_string(&buf, &tmp_adr->alias));
237 OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, m_addr));
238
239 replace_neighbor_link_set(tmp_neigh, real_neigh);
240
241 /* Dequeue */
242 DEQUEUE_ELEM(tmp_neigh);
243 /* Delete */
244 free(tmp_neigh);
245
246 changes_neighborhood = true;
247 }
248 tmp_adr = tmp_adr->next_alias;
249 }
250 return true;
251 }
252
253 /**
254 * Insert an alias address for a node.
255 * If the main address is not registered
256 * then a new entry is created.
257 *
258 * @param main_add the main address of the node
259 * @param alias the alias address to insert
260 * @param vtime the expiration time
261 */
262 void
insert_mid_alias(union olsr_ip_addr * main_add,const union olsr_ip_addr * alias,olsr_reltime vtime)263 insert_mid_alias(union olsr_ip_addr *main_add, const union olsr_ip_addr *alias, olsr_reltime vtime)
264 {
265 struct neighbor_entry *ne_old, *ne_new;
266 struct mid_entry *me_old;
267 int ne_ref_rp_count;
268 struct ipaddr_str buf1, buf2;
269 struct mid_address *adr;
270 if (!olsr_validate_address(alias))
271 return;
272
273 OLSR_PRINTF(1, "Inserting alias %s for ", olsr_ip_to_string(&buf1, alias));
274 OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf1, main_add));
275
276 adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
277
278 adr->alias = *alias;
279 adr->next_alias = NULL;
280
281 /*
282 * If we have an entry for this alias in neighbortable, we better adjust it's
283 * main address, because otherwise a fatal inconsistency between
284 * neighbortable and link_set will be created by way of this mid entry.
285 */
286 ne_old = olsr_lookup_neighbor_table_alias(alias);
287 if (ne_old != NULL) {
288 OLSR_PRINTF(2, "Remote main address change detected. Mangling neighbortable to replace %s with %s.\n",
289 olsr_ip_to_string(&buf1, alias), olsr_ip_to_string(&buf2, main_add));
290 olsr_delete_neighbor_table(alias);
291 ne_new = olsr_insert_neighbor_table(main_add);
292 /* adjust pointers to neighbortable-entry in link_set */
293 ne_ref_rp_count = replace_neighbor_link_set(ne_old, ne_new);
294 if (ne_ref_rp_count > 0)
295 OLSR_PRINTF(2, "Performed %d neighbortable-pointer replacements (%p -> %p) in link_set.\n", ne_ref_rp_count, ne_old, ne_new);
296
297 me_old = mid_lookup_entry_bymain(alias);
298 if (me_old) {
299
300 /*
301 * we knew aliases to the previous main address;
302 * better forget about them now.
303 */
304 OLSR_PRINTF(2,
305 "I already have an mid entry mapping addresses to this "
306 "alias address. Removing existing mid entry to preserve consistency of mid_set.\n");
307 olsr_delete_mid_entry(me_old);
308 }
309 }
310
311 if (!insert_mid_tuple(main_add, adr, vtime)) {
312 free(adr);
313 }
314
315 /*
316 *Recalculate topology
317 */
318 changes_neighborhood = true;
319 changes_topology = true;
320 }
321
322 /**
323 * Lookup the main address for a alias address
324 *
325 * @param adr the alias address to check
326 * @return the main address registered on the alias
327 * or NULL if not found
328 */
329 union olsr_ip_addr *
mid_lookup_main_addr(const union olsr_ip_addr * adr)330 mid_lookup_main_addr(const union olsr_ip_addr *adr)
331 {
332 uint32_t hash;
333 struct mid_address *tmp_list;
334
335 hash = olsr_ip_hashing(adr);
336
337 /*Traverse MID list */
338 for (tmp_list = reverse_mid_set[hash].next; tmp_list != &reverse_mid_set[hash]; tmp_list = tmp_list->next) {
339 if (ipequal(&tmp_list->alias, adr))
340 return &tmp_list->main_entry->main_addr;
341 }
342 return NULL;
343
344 }
345
346 /*
347 * Find mid entry to an address.
348 *
349 * @param adr the main address to search for
350 * @return a linked list of address structs
351 */
352 struct mid_entry *
mid_lookup_entry_bymain(const union olsr_ip_addr * adr)353 mid_lookup_entry_bymain(const union olsr_ip_addr *adr)
354 {
355 struct mid_entry *tmp_list;
356 uint32_t hash;
357
358 hash = olsr_ip_hashing(adr);
359
360 /* Check all registered nodes... */
361 for (tmp_list = mid_set[hash].next; tmp_list != &mid_set[hash]; tmp_list = tmp_list->next) {
362 if (ipequal(&tmp_list->main_addr, adr))
363 return tmp_list;
364 }
365 return NULL;
366 }
367
368 /*
369 * Find all aliases for an address.
370 *
371 * @param adr the main address to search for
372 * @return a linked list of addresses structs
373 */
374 struct mid_address *
mid_lookup_aliases(const union olsr_ip_addr * adr)375 mid_lookup_aliases(const union olsr_ip_addr *adr)
376 {
377 struct mid_entry *tmp = mid_lookup_entry_bymain(adr);
378 return tmp ? tmp->aliases : NULL;
379 }
380
381 /**
382 * Update the timer for an MID entry
383 *
384 * @param adr the main address of the entry
385 * @param vtime the expiration time
386 * @return 1 if the node was updated, 0 if not
387 */
388 int
olsr_update_mid_table(const union olsr_ip_addr * adr,olsr_reltime vtime)389 olsr_update_mid_table(const union olsr_ip_addr *adr, olsr_reltime vtime)
390 {
391 uint32_t hash;
392 struct ipaddr_str buf;
393 struct mid_entry *tmp_list = mid_set;
394
395 OLSR_PRINTF(3, "MID: update %s\n", olsr_ip_to_string(&buf, adr));
396 hash = olsr_ip_hashing(adr);
397
398 /* Check all registered nodes... */
399 for (tmp_list = mid_set[hash].next; tmp_list != &mid_set[hash]; tmp_list = tmp_list->next) {
400 /*find match */
401 if (ipequal(&tmp_list->main_addr, adr)) {
402 olsr_set_mid_timer(tmp_list, vtime);
403
404 return 1;
405 }
406 }
407 return 0;
408 }
409
410 /**
411 * Remove aliases from 'entry' which are not listed in 'declared_aliases'.
412 *
413 * @param message the MID message
414 */
415 static void
olsr_prune_aliases(struct mid_message * message)416 olsr_prune_aliases(struct mid_message *message)
417 {
418 const union olsr_ip_addr *m_addr = &message->mid_origaddr;
419 struct mid_alias * declared_aliases = message->mid_addr;
420 struct mid_entry *entry;
421 uint32_t hash;
422 struct mid_address *registered_aliases;
423 struct mid_address *previous_alias;
424 struct mid_alias *save_declared_aliases = declared_aliases;
425
426 hash = olsr_ip_hashing(m_addr);
427
428 /* Check for registered entry */
429 for (entry = mid_set[hash].next; entry != &mid_set[hash]; entry = entry->next) {
430 if (ipequal(&entry->main_addr, m_addr))
431 break;
432 }
433 if (entry == &mid_set[hash]) {
434 /* MID entry not found, nothing to prune here */
435 return;
436 }
437
438 registered_aliases = entry->aliases;
439 previous_alias = NULL;
440
441 while (registered_aliases != NULL) {
442 struct mid_address *current_alias = registered_aliases;
443 registered_aliases = registered_aliases->next_alias;
444
445 declared_aliases = save_declared_aliases;
446
447 /* Go through the list of declared aliases to find the matching current alias */
448 while (declared_aliases != 0 && !ipequal(¤t_alias->alias, &declared_aliases->alias_addr)) {
449 declared_aliases = declared_aliases->next;
450 }
451
452 if (declared_aliases == NULL) {
453 /*do not remove alias if vtime still valid (so we assigned something != NULL to declared_aliases)*/
454 if (!olsr_isTimedOut(current_alias->vtime)) declared_aliases = save_declared_aliases;
455 }
456 else current_alias->vtime=olsr_getTimestamp(message->vtime);
457
458 if (declared_aliases == NULL) {
459 struct ipaddr_str buf;
460 /* Current alias not found in list of declared aliases: free current alias */
461 OLSR_PRINTF(1, "MID remove: (%s, ", olsr_ip_to_string(&buf, &entry->main_addr));
462 OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&buf, ¤t_alias->alias));
463
464 /* Update linked list as seen by 'entry' */
465 if (previous_alias != NULL) {
466 previous_alias->next_alias = current_alias->next_alias;
467 } else {
468 entry->aliases = current_alias->next_alias;
469 }
470
471 /* Remove from hash table */
472 DEQUEUE_ELEM(current_alias);
473
474 /*
475 * Delete the rt_path for the alias.
476 */
477 olsr_delete_routing_table(¤t_alias->alias, olsr_cnf->maxplen, &entry->main_addr);
478
479 free(current_alias);
480
481 /*
482 *Recalculate topology
483 */
484 changes_neighborhood = true;
485 changes_topology = true;
486 } else {
487 previous_alias = current_alias;
488 }
489 }
490 }
491
492 /**
493 * Delete a MID entry
494 *
495 * @param mid the entry to delete
496 */
497 void
olsr_delete_mid_entry(struct mid_entry * mid)498 olsr_delete_mid_entry(struct mid_entry *mid)
499 {
500 struct mid_address *aliases;
501
502 /* Free aliases */
503 aliases = mid->aliases;
504 while (aliases) {
505 struct mid_address *tmp_aliases = aliases;
506 aliases = aliases->next_alias;
507 DEQUEUE_ELEM(tmp_aliases);
508
509 /*
510 * Delete the rt_path for the alias.
511 */
512 olsr_delete_routing_table(&tmp_aliases->alias, olsr_cnf->maxplen, &mid->main_addr);
513
514 free(tmp_aliases);
515 }
516
517 /*
518 * Kill any pending timers.
519 */
520 if (mid->mid_timer) {
521 olsr_stop_timer(mid->mid_timer);
522 mid->mid_timer = NULL;
523 }
524
525 /* Dequeue */
526 DEQUEUE_ELEM(mid);
527 free(mid);
528 }
529
530 /**
531 * Print all MID entries
532 * For debuging purposes
533 */
534 void
olsr_print_mid_set(void)535 olsr_print_mid_set(void)
536 {
537 int idx;
538
539 OLSR_PRINTF(1, "\n--- %s ------------------------------------------------- MID\n\n", olsr_wallclock_string());
540
541 for (idx = 0; idx < HASHSIZE; idx++) {
542 struct mid_entry *tmp_list = mid_set[idx].next;
543 /*Traverse MID list */
544 for (tmp_list = mid_set[idx].next; tmp_list != &mid_set[idx]; tmp_list = tmp_list->next) {
545 struct mid_address *tmp_addr;
546 struct ipaddr_str buf;
547 OLSR_PRINTF(1, "%s: ", olsr_ip_to_string(&buf, &tmp_list->main_addr));
548 for (tmp_addr = tmp_list->aliases; tmp_addr; tmp_addr = tmp_addr->next_alias) {
549 OLSR_PRINTF(1, " %s ", olsr_ip_to_string(&buf, &tmp_addr->alias));
550 }
551 OLSR_PRINTF(1, "\n");
552 }
553 }
554 }
555
556 /**
557 *Process a received(and parsed) MID message
558 *For every address check if there is a topology node
559 *registered with it and update its addresses.
560 *
561 *@param m the OLSR message received.
562 *@param in_if the incoming interface
563 *@param from_addr the sender address
564 *@return 1 on success
565 */
566
567 bool
olsr_input_mid(union olsr_message * m,struct interface_olsr * in_if,union olsr_ip_addr * from_addr)568 olsr_input_mid(union olsr_message *m, struct interface_olsr *in_if __attribute__ ((unused)), union olsr_ip_addr *from_addr)
569 {
570 struct ipaddr_str buf;
571 struct mid_alias *tmp_adr;
572 struct mid_message message;
573
574 mid_chgestruct(&message, m);
575
576 if (!olsr_validate_address(&message.mid_origaddr)) {
577 olsr_free_mid_packet(&message);
578 return false;
579 }
580 #ifdef DEBUG
581 OLSR_PRINTF(5, "Processing MID from %s...\n", olsr_ip_to_string(&buf, &message.mid_origaddr));
582 #endif /* DEBUG */
583 tmp_adr = message.mid_addr;
584
585 /*
586 * If the sender interface (NB: not originator) of this message
587 * is not in the symmetric 1-hop neighborhood of this node, the
588 * message MUST be discarded.
589 */
590
591 if (check_neighbor_link(from_addr) != SYM_LINK) {
592 OLSR_PRINTF(2, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
593 olsr_free_mid_packet(&message);
594 return false;
595 }
596
597 /* Update the timeout of the MID */
598 olsr_update_mid_table(&message.mid_origaddr, message.vtime);
599
600 for (;tmp_adr; tmp_adr = tmp_adr->next) {
601 #ifndef NO_DUPLICATE_DETECTION_HANDLER
602 struct interface_olsr *ifs;
603 bool stop = false;
604 for (ifs = ifnet; ifs != NULL; ifs = ifs->int_next) {
605 if (ipequal(&ifs->ip_addr, &tmp_adr->alias_addr)) {
606 /* ignore your own main IP as an incoming MID */
607 olsr_handle_mid_collision(&tmp_adr->alias_addr, &message.mid_origaddr);
608 stop = true;
609 break;
610 }
611 }
612 if (stop) {
613 continue;
614 }
615 #endif /* NO_DUPLICATE_DETECTION_HANDLER */
616 if (!mid_lookup_main_addr(&tmp_adr->alias_addr)) {
617 OLSR_PRINTF(1, "MID new: (%s, ", olsr_ip_to_string(&buf, &message.mid_origaddr));
618 OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&buf, &tmp_adr->alias_addr));
619 insert_mid_alias(&message.mid_origaddr, &tmp_adr->alias_addr, message.vtime);
620 } else {
621 olsr_insert_routing_table(&tmp_adr->alias_addr, olsr_cnf->maxplen, &message.mid_origaddr, OLSR_RT_ORIGIN_MID);
622 }
623 }
624
625 olsr_prune_aliases(&message);
626 olsr_free_mid_packet(&message);
627
628 /* Forward the message */
629 return true;
630 }
631
632 /*
633 * Local Variables:
634 * c-basic-offset: 2
635 * indent-tabs-mode: nil
636 * End:
637 */
638