3 * The olsr.org Optimized Link-State Routing daemon(olsrd)
4 * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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.
34 * Visit http://www.olsr.org for more information.
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.
45 #include "lq_packet.h"
49 #include "neighbor_table.h"
50 #include "olsr_logging.h"
52 static bool delete_outdated_tc_edges(struct tc_entry *);
54 /* Root of the link state database */
55 struct avl_tree tc_tree;
56 struct tc_entry *tc_myself = NULL; /* Shortcut to ourselves */
58 /* Some cookies for stats keeping */
59 static struct olsr_cookie_info *tc_edge_gc_timer_cookie = NULL;
60 static struct olsr_cookie_info *tc_validity_timer_cookie = NULL;
61 struct olsr_cookie_info *spf_backoff_timer_cookie = NULL;
62 struct olsr_cookie_info *tc_mem_cookie = NULL;
64 static uint32_t relevantTcCount = 0;
66 /* the first 32 TCs are without Fisheye */
67 static int ttl_index = -32;
69 static uint16_t local_ansn_number = 0;
71 static void olsr_cleanup_tc_entry(struct tc_entry *tc);
74 * Add a new tc_entry to the tc tree
76 * @param (last)adr address of the entry
77 * @return a pointer to the created entry
79 static struct tc_entry *
80 olsr_add_tc_entry(const union olsr_ip_addr *adr)
82 #if !defined REMOVE_LOG_DEBUG
83 struct ipaddr_str buf;
88 * Safety net against loss of the last main IP address.
90 if (olsr_ipcmp(&olsr_cnf->router_id, &all_zero) == 0) {
94 OLSR_DEBUG(LOG_TC, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
96 tc = olsr_cookie_malloc(tc_mem_cookie);
103 tc->vertex_node.key = &tc->addr;
109 * Insert into the global tc tree.
111 avl_insert(&tc_tree, &tc->vertex_node, false);
112 olsr_lock_tc_entry(tc);
115 * Initialize subtrees for edges, prefixes, HNAs and MIDs.
117 avl_init(&tc->edge_tree, avl_comp_default);
118 avl_init(&tc->prefix_tree, avl_comp_prefix_origin_default);
119 avl_init(&tc->mid_tree, avl_comp_default);
120 avl_init(&tc->hna_tree, avl_comp_prefix_default);
123 * Add a rt_path for ourselves.
125 olsr_insert_routing_table(adr, 8 * olsr_cnf->ipsize, adr, OLSR_RT_ORIGIN_TC);
131 * Initialize the topology set
137 OLSR_INFO(LOG_TC, "Initialize topology set...\n");
139 avl_init(&tc_tree, avl_comp_default);
142 * Get some cookies for getting stats to ease troubleshooting.
144 tc_edge_gc_timer_cookie = olsr_alloc_cookie("TC edge GC", OLSR_COOKIE_TYPE_TIMER);
145 tc_validity_timer_cookie = olsr_alloc_cookie("TC validity", OLSR_COOKIE_TYPE_TIMER);
146 spf_backoff_timer_cookie = olsr_alloc_cookie("SPF backoff", OLSR_COOKIE_TYPE_TIMER);
148 tc_mem_cookie = olsr_alloc_cookie("tc_entry", OLSR_COOKIE_TYPE_MEMORY);
149 olsr_cookie_set_memory_size(tc_mem_cookie, sizeof(struct tc_entry));
153 * The main ip address has changed.
157 olsr_change_myself_tc(void)
159 struct link_entry *entry;
160 bool main_ip_change = false;
165 * Check if there was a change.
167 if (olsr_ipcmp(&tc_myself->addr, &olsr_cnf->router_id) == 0) {
172 * Flush our own tc_entry.
174 olsr_delete_tc_entry(tc_myself);
177 * Clear the reference.
179 olsr_unlock_tc_entry(tc_myself);
182 main_ip_change = true;
186 * The old entry for ourselves is gone, generate a new one and trigger SPF.
188 tc_myself = olsr_add_tc_entry(&olsr_cnf->router_id);
189 olsr_lock_tc_entry(tc_myself);
191 OLSR_FOR_ALL_LINK_ENTRIES(entry) {
194 * check if a main ip change destroyed our TC entries
196 if (main_ip_change || entry->link_tc_edge == NULL) {
197 struct nbr_entry *ne = entry->neighbor;
198 entry->link_tc_edge = olsr_add_tc_edge_entry(tc_myself, &ne->nbr_addr, 0);
200 } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
201 changes_topology = true;
205 * Attempts to delete a tc entry. This will work unless there are virtual edges left
206 * that cannot be removed
208 * @param entry the TC entry to delete
212 olsr_delete_tc_entry(struct tc_entry *tc)
214 struct tc_edge_entry *tc_edge;
216 #if !defined REMOVE_LOG_DEBUG
217 struct ipaddr_str buf;
219 OLSR_DEBUG(LOG_TC, "TC: del entry %s %u %s\n", olsr_ip_to_string(&buf, &tc->addr),
220 tc->edge_tree.count, tc->is_virtual ? "true" : "false");
222 /* we don't want to keep this node */
223 tc->is_virtual = true;
225 if (tc->edge_tree.count == 0) {
226 olsr_cleanup_tc_entry(tc);
229 /* The delete all non-virtual edges, the last one will clean up the tc if possible */
230 OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
231 /* we don't need this edge for the tc, so let's try to remove it */
232 olsr_delete_tc_edge_entry(tc_edge);
233 } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
237 * Delete a tc entry after all edges have been cleared.
239 * @param entry the TC entry to delete
242 olsr_cleanup_tc_entry(struct tc_entry *tc) {
244 #if !defined(REMOVE_LOG_DEBUG)
245 struct ipaddr_str buf;
247 OLSR_DEBUG(LOG_TC, "TC: del entry %s %u\n", olsr_ip_to_string(&buf, &tc->addr), tc->refcount);
248 assert (tc->edge_tree.count == 0);
250 OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) {
251 olsr_delete_rt_path(rtp);
252 } OLSR_FOR_ALL_PREFIX_ENTRIES_END();
254 /* Flush all MID aliases and kill the MID timer */
255 olsr_flush_mid_entries(tc);
257 /* Flush all HNA Networks and kill its timers */
258 olsr_flush_hna_nets(tc);
260 /* Stop running timers */
261 olsr_stop_timer(tc->edge_gc_timer);
262 tc->edge_gc_timer = NULL;
263 olsr_stop_timer(tc->validity_timer);
264 tc->validity_timer = NULL;
266 avl_delete(&tc_tree, &tc->vertex_node);
267 olsr_unlock_tc_entry(tc);
271 * Look up a entry from the TC tree based on address
273 * @param adr the address to look for
274 * @return the entry found or NULL
277 olsr_lookup_tc_entry(const union olsr_ip_addr *adr)
279 struct avl_node *node;
281 node = avl_find(&tc_tree, adr);
282 return node ? vertex_tree2tc(node) : NULL;
286 * Lookup a tc entry. Creates one if it does not exist yet.
289 olsr_locate_tc_entry(const union olsr_ip_addr *adr)
291 struct tc_entry *tc = olsr_lookup_tc_entry(adr);
293 return tc == NULL ? olsr_add_tc_entry(adr) : tc;
297 * Format tc_edge contents into a buffer.
299 #if !defined REMOVE_LOG_DEBUG
301 olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
303 static char buf[128];
304 struct ipaddr_str addrbuf, dstbuf;
305 char lqbuffer[LQTEXT_MAXLENGTH];
307 snprintf(buf, sizeof(buf),
309 olsr_ip_to_string(&addrbuf, &tc_edge->tc->addr),
310 olsr_ip_to_string(&dstbuf, &tc_edge->T_dest_addr),
311 olsr_get_linkcost_text(tc_edge->cost, false, lqbuffer, sizeof(lqbuffer)));
317 * Wrapper for the timer callback.
318 * A TC entry has not been refreshed in time.
319 * Remove it from the link-state database.
322 olsr_expire_tc_entry(void *context)
324 #if !defined REMOVE_LOG_DEBUG
325 struct ipaddr_str buf;
327 struct tc_entry *tc = context;
328 tc->validity_timer = NULL;
330 OLSR_DEBUG(LOG_TC, "TC: expire node entry %s\n",
331 olsr_ip_to_string(&buf, &tc->addr));
333 olsr_delete_tc_entry(tc);
334 changes_topology = true;
338 * Wrapper for the timer callback.
339 * Does the garbage collection of older ansn entries after no edge addition to
340 * the TC entry has happened for OLSR_TC_EDGE_GC_TIME.
343 olsr_expire_tc_edge_gc(void *context)
345 #if !defined REMOVE_LOG_DEBUG
346 struct ipaddr_str buf;
348 struct tc_entry *tc = context;
350 OLSR_DEBUG(LOG_TC, "TC: expire edge GC for %s\n",
351 olsr_ip_to_string(&buf, &tc->addr));
353 tc->edge_gc_timer = NULL;
355 if (delete_outdated_tc_edges(tc)) {
356 changes_topology = true;
361 * If the edge does not have a minimum acceptable link quality
362 * set the etx cost to infinity such that it gets ignored during
365 * @return 1 if the change of the etx value was relevant
368 olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
370 olsr_linkcost old = tc_edge->cost;
371 tc_edge->cost = olsr_calc_tc_cost(tc_edge);
372 tc_edge->common_cost = tc_edge->cost;
373 if (tc_edge->edge_inv) {
374 tc_edge->edge_inv->common_cost = tc_edge->cost;
376 return olsr_is_relevant_costchange(old, tc_edge->cost);
380 * Add a new tc_edge_entry to the tc_edge_tree
382 * @param (last)adr address of the entry
383 * @return a pointer to the created entry
385 struct tc_edge_entry *
386 olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr, uint16_t ansn)
388 struct tc_entry *tc_neighbor;
389 struct tc_edge_entry *tc_edge;
390 struct tc_edge_entry *tc_edge_inv;
391 #if !defined REMOVE_LOG_DEBUG
392 struct ipaddr_str buf;
394 tc_edge = olsr_malloc_tc_edge_entry();
400 tc_edge->T_dest_addr = *addr;
401 tc_edge->ansn = ansn;
402 tc_edge->edge_node.key = &tc_edge->T_dest_addr;
405 * Insert into the edge tree.
406 * Expectation is to have only one tc_edge per tc pair.
407 * However we need duplicate key support for the case of local
408 * parallel links where we add one tc_edge per link_entry.
410 avl_insert(&tc->edge_tree, &tc_edge->edge_node, true);
411 olsr_lock_tc_entry(tc);
414 * Connect backpointer.
419 * Check if the neighboring router and the inverse edge is in the lsdb.
420 * Create short cuts to the inverse edge for faster SPF execution.
422 tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
423 if (tc_neighbor == NULL) {
424 OLSR_DEBUG(LOG_TC, "TC: creating neighbor tc_entry %s\n", olsr_ip_to_string(&buf, &tc_edge->T_dest_addr));
425 tc_neighbor = olsr_add_tc_entry(&tc_edge->T_dest_addr);
426 tc_neighbor->is_virtual = true;
429 /* don't create an inverse edge for a tc pointing to us ! */
430 if (1 && tc_neighbor != tc_myself) {
431 tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
433 OLSR_DEBUG(LOG_TC, "TC: creating inverse edge for %s\n", olsr_ip_to_string(&buf, &tc->addr));
434 tc_edge_inv = olsr_add_tc_edge_entry(tc_neighbor, &tc->addr, 0);
436 tc_edge_inv->is_virtual = 1;
440 * Connect the edges mutually.
442 tc_edge_inv->edge_inv = tc_edge;
443 tc_edge->edge_inv = tc_edge_inv;
449 olsr_calc_tc_edge_entry_etx(tc_edge);
451 OLSR_DEBUG(LOG_TC, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
457 * Delete a TC edge entry.
459 * @param tc the TC entry
460 * @param tc_edge the TC edge entry
461 * @return true if the tc entry was deleted, false otherwise
464 olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
467 struct tc_edge_entry *tc_edge_inv;
468 #if !defined REMOVE_LOG_DEBUG
469 struct ipaddr_str buf;
472 tc_edge->is_virtual = 1;
474 tc_edge_inv = tc_edge->edge_inv;
475 if (tc_edge_inv != NULL && tc_edge_inv->is_virtual == 0) {
476 OLSR_DEBUG(LOG_TC, "TC: mark edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
480 OLSR_DEBUG(LOG_TC, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
483 * Clear the backpointer of our inverse edge.
486 /* split the two edges */
487 tc_edge_inv->edge_inv = NULL;
488 tc_edge->edge_inv = NULL;
490 if (tc_edge_inv->is_virtual) {
491 /* remove the other side too because it's a virtual link */
492 olsr_delete_tc_edge_entry(tc_edge_inv);
498 /* remove edge from tc FIRST */
499 avl_delete(&tc->edge_tree, &tc_edge->edge_node);
500 OLSR_DEBUG(LOG_TC, "TC: %s down to %d edges\n", olsr_ip_to_string(&buf, &tc->addr), tc->edge_tree.count);
502 /* now check if TC is virtual and has no edges left */
503 if (tc->is_virtual && tc->edge_tree.count == 0) {
504 /* cleanup virtual tc node */
505 olsr_cleanup_tc_entry(tc);
507 olsr_unlock_tc_entry(tc);
508 olsr_free_tc_edge_entry(tc_edge);
512 * Delete all destinations that have a lower ANSN.
514 * @param tc the entry to delete edges from
515 * @return TRUE if any destinations were deleted, FALSE if not
518 delete_outdated_tc_edges(struct tc_entry *tc)
520 struct tc_edge_entry *tc_edge;
523 OLSR_DEBUG(LOG_TC, "TC: deleting outdated TC-edge entries\n");
525 OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
526 if (SEQNO_GREATER_THAN(tc->ansn, tc_edge->ansn)) {
527 olsr_delete_tc_edge_entry(tc_edge);
531 OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
534 changes_topology = true;
539 * Delete all destinations that are inside the borders but
540 * not updated in the last tc.
542 * @param tc the entry to delete edges from
543 * @param ansn the advertised neighbor set sequence number
544 * @return 1 if any destinations were deleted 0 if not
547 olsr_delete_revoked_tc_edges(struct tc_entry *tc, uint16_t ansn, union olsr_ip_addr *lower_border, union olsr_ip_addr *upper_border)
549 struct tc_edge_entry *tc_edge;
551 bool passedLowerBorder = false;
553 OLSR_DEBUG(LOG_TC, "TC: deleting revoked TCs\n");
555 OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
556 if (!passedLowerBorder) {
557 if (avl_comp_default(lower_border, &tc_edge->T_dest_addr) <= 0) {
558 passedLowerBorder = true;
564 if (passedLowerBorder) {
565 if (avl_comp_default(upper_border, &tc_edge->T_dest_addr) <= 0) {
570 if (SEQNO_GREATER_THAN(ansn, tc_edge->ansn)) {
571 olsr_delete_tc_edge_entry(tc_edge);
575 OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
578 changes_topology = true;
584 * Update an edge registered on an entry.
585 * Creates new edge-entries if not registered.
586 * Bases update on a received TC message
588 * @param entry the TC entry to check
589 * @pkt the TC edge entry in the packet
590 * @return 1 if entries are added 0 if not
593 olsr_tc_update_edge(struct tc_entry *tc, uint16_t ansn, const unsigned char **curr, union olsr_ip_addr *neighbor)
595 struct tc_edge_entry *tc_edge;
599 * Fetch the per-edge data
601 pkt_get_ipaddress(curr, neighbor);
603 /* First check if we know this edge */
604 tc_edge = olsr_lookup_tc_edge(tc, neighbor);
607 * Yet unknown - create it.
608 * Check if the address is allowed.
610 if (!olsr_validate_address(neighbor)) {
614 tc_edge = olsr_add_tc_edge_entry(tc, neighbor, ansn);
616 olsr_deserialize_tc_lq_pair(curr, tc_edge);
620 * We know this edge - Update entry.
622 tc_edge->ansn = ansn;
625 * Update link quality if configured.
627 olsr_deserialize_tc_lq_pair(curr, tc_edge);
632 if (olsr_calc_tc_edge_entry_etx(tc_edge)) {
633 if (tc->msg_hops <= olsr_cnf->lq_dlimit) {
638 OLSR_DEBUG(LOG_TC, "TC: chg edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
641 tc_edge->is_virtual = 0;
642 tc->is_virtual = false;
648 * Lookup an edge hanging off a TC entry.
650 * @param entry the entry to check
651 * @param dst_addr the destination address to check for
652 * @return a pointer to the tc_edge found - or NULL
654 struct tc_edge_entry *
655 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
657 struct avl_node *edge_node;
659 edge_node = avl_find(&tc->edge_tree, edge_addr);
661 return edge_node ? edge_tree2tc_edge(edge_node) : NULL;
665 * Print the topology table to stdout
668 olsr_print_tc_table(void)
670 #if !defined REMOVE_LOG_INFO
671 /* The whole function makes no sense without it. */
673 const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
675 OLSR_INFO(LOG_TC, "\n--- %s ------------------------------------------------- TOPOLOGY\n\n", olsr_wallclock_string());
676 OLSR_INFO_NH(LOG_TC, "%-*s %-*s %8s %8s\n", ipwidth,
677 "Source IP addr", ipwidth, "Dest IP addr", olsr_get_linklabel(0), "(common)");
679 OLSR_FOR_ALL_TC_ENTRIES(tc) {
680 struct tc_edge_entry *tc_edge;
681 OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
682 struct ipaddr_str addrbuf, dstaddrbuf;
683 char lqbuffer1[LQTEXT_MAXLENGTH], lqbuffer2[LQTEXT_MAXLENGTH];
685 OLSR_INFO_NH(LOG_TC, "%-*s %-*s %-7s %8s %8s\n",
686 ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
687 ipwidth, olsr_ip_to_string(&dstaddrbuf,
688 &tc_edge->T_dest_addr),
689 tc_edge->is_virtual ? "virtual" : "",
690 olsr_get_linkcost_text(tc_edge->cost, false, lqbuffer1, sizeof(lqbuffer1)),
691 olsr_get_linkcost_text(tc_edge->common_cost, false, lqbuffer2, sizeof(lqbuffer2)));
693 } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
694 } OLSR_FOR_ALL_TC_ENTRIES_END();
699 * calculate the border IPs of a tc edge set according to the border flags
701 * @param lower border flag
702 * @param pointer to lower border ip
703 * @param upper border flag
704 * @param pointer to upper border ip
705 * @result 1 if lower/upper border ip have been set
708 olsr_calculate_tc_border(uint8_t lower_border,
709 union olsr_ip_addr *lower_border_ip, uint8_t upper_border, union olsr_ip_addr *upper_border_ip)
711 if (lower_border == 0 && upper_border == 0) {
714 if (lower_border == 0xff) {
715 memset(lower_border_ip, 0, sizeof(lower_border_ip));
720 for (i = 0; i < lower_border / 8; i++) {
721 lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
723 lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 - 1] &= (0xff << (lower_border & 7));
724 lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 - 1] |= (1 << (lower_border & 7));
727 if (upper_border == 0xff) {
728 memset(upper_border_ip, 0xff, sizeof(upper_border_ip));
734 for (i = 0; i < upper_border / 8; i++) {
735 upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
737 upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 - 1] &= (0xff << (upper_border & 7));
738 upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 - 1] |= (1 << (upper_border & 7));
744 * Process an incoming TC or TC_LQ message.
746 * If the message is interesting enough, update our edges for it,
747 * trigger SPF and finally flood it to all our 2way neighbors.
749 * The order for extracting data off the message does matter,
750 * as every call to pkt_get increases the packet offset and
751 * hence the spot we are looking at.
754 olsr_input_tc(union olsr_message * msg, struct interface * input_if __attribute__ ((unused)),
755 union olsr_ip_addr * from_addr, enum duplicate_status status)
757 uint16_t size, msg_seq, ansn;
758 uint8_t type, ttl, msg_hops, lower_border, upper_border;
760 union olsr_ip_addr originator;
761 const unsigned char *limit, *curr;
764 #if !defined REMOVE_LOG_DEBUG
765 struct ipaddr_str buf;
767 union olsr_ip_addr lower_border_ip, upper_border_ip;
772 /* We are only interested in TC message types. */
773 pkt_get_u8(&curr, &type);
774 if (type != olsr_get_TC_MessageId()) {
779 * If the sender interface (NB: not originator) of this message
780 * is not in the symmetric 1-hop neighborhood of this node, the
781 * message MUST be discarded.
783 if (check_neighbor_link(from_addr) != SYM_LINK) {
784 OLSR_DEBUG(LOG_TC, "Received TC from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
788 pkt_get_reltime(&curr, &vtime);
789 pkt_get_u16(&curr, &size);
791 pkt_get_ipaddress(&curr, &originator);
793 /* Copy header values */
794 pkt_get_u8(&curr, &ttl);
795 pkt_get_u8(&curr, &msg_hops);
796 pkt_get_u16(&curr, &msg_seq);
797 pkt_get_u16(&curr, &ansn);
800 pkt_get_u8(&curr, &lower_border);
801 pkt_get_u8(&curr, &upper_border);
803 tc = olsr_lookup_tc_entry(&originator);
805 /* TCs can be splitted, so we are looking for ANSNs equal or higher */
806 if (tc && status != RESET_SEQNO_OLSR_MESSAGE && tc->tc_seq != -1 && olsr_seqno_diff(ansn, tc->ansn) < 0) {
807 /* this TC is too old, discard it */
812 * Generate a new tc_entry in the lsdb and store the sequence number.
815 tc = olsr_add_tc_entry(&originator);
819 * Update the tc entry.
821 tc->msg_hops = msg_hops;
822 tc->tc_seq = msg_seq;
825 tc->err_seq_valid = false;
826 tc->is_virtual = false;
828 OLSR_DEBUG(LOG_TC, "Processing TC from %s, seq 0x%04x\n", olsr_ip_to_string(&buf, &originator), tc->tc_seq);
831 * Now walk the edge advertisements contained in the packet.
834 limit = (unsigned char *)msg + size;
837 while (curr + olsr_cnf->ipsize + olsr_sizeof_TCLQ() <= limit) {
838 if (olsr_tc_update_edge(tc, ansn, &curr, &upper_border_ip)) {
844 memcpy(&lower_border_ip, &upper_border_ip, sizeof(lower_border_ip));
850 changes_topology = true;
854 * Calculate real border IPs.
857 borderSet = olsr_calculate_tc_border(lower_border, &lower_border_ip, upper_border, &upper_border_ip);
861 * Set or change the expiration timer accordingly.
863 olsr_set_timer(&tc->validity_timer, vtime,
864 OLSR_TC_VTIME_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_tc_entry, tc, tc_validity_timer_cookie);
869 * Delete all old tc edges within borders.
871 olsr_delete_revoked_tc_edges(tc, ansn, &lower_border_ip, &upper_border_ip);
875 * Kick the the edge garbage collection timer. In the meantime hopefully
876 * all edges belonging to a multipart neighbor set will arrive.
878 olsr_set_timer(&tc->edge_gc_timer, OLSR_TC_EDGE_GC_TIME,
879 OLSR_TC_EDGE_GC_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_tc_edge_gc, tc, tc_edge_gc_timer_cookie);
884 getRelevantTcCount(void)
886 return relevantTcCount;
890 olsr_delete_all_tc_entries(void) {
892 struct link_entry *link;
894 /* then remove all tc entries */
895 OLSR_FOR_ALL_TC_ENTRIES(tc) {
897 } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
899 OLSR_FOR_ALL_TC_ENTRIES(tc) {
900 if (tc != tc_myself) {
901 olsr_delete_tc_entry(tc);
903 } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
905 /* kill all references in link_set */
906 OLSR_FOR_ALL_LINK_ENTRIES(link) {
907 link->link_tc_edge = NULL;
908 } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
913 olsr_delete_tc_entry(tc_myself);
914 olsr_unlock_tc_entry(tc_myself);
920 calculate_border_flag(void *lower_border, void *higher_border)
922 uint8_t *lower = lower_border;
923 uint8_t *higher = higher_border;
925 uint8_t part, bitpos;
927 for (part = 0; part < olsr_cnf->ipsize; part++) {
928 if (lower[part] != higher[part]) {
933 if (part == olsr_cnf->ipsize) { // same IPs ?
936 // look for first bit of difference
938 for (bitpos = 0; bitpos < 8; bitpos++, bitmask <<= 1) {
939 if ((lower[part] & bitmask) == (higher[part] & bitmask)) {
944 bitpos += 8 * (olsr_cnf->ipsize - part - 1);
949 get_local_ansn_number(void) {
950 return local_ansn_number;
954 increase_local_ansn_number(void) {
959 olsr_output_lq_tc_internal(void *ctx __attribute__ ((unused)), union olsr_ip_addr *nextIp, bool skip)
961 static int ttl_list[] = { 2, 8, 2, 16, 2, 8, 2, MAX_TTL };
962 struct interface *ifp;
963 struct nbr_entry *nbr;
964 struct link_entry *link;
965 uint8_t msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE] __attribute__ ((aligned));
966 uint8_t *curr = msg_buffer;
967 uint8_t *length_field, *border_flags, *seqno, *last;
968 bool sendTC = false, nextFragment = false;
971 OLSR_INFO(LOG_PACKET_CREATION, "Building TC\n-------------------\n");
973 pkt_put_u8(&curr, olsr_get_TC_MessageId());
974 pkt_put_reltime(&curr, olsr_cnf->tc_params.validity_time);
977 pkt_put_u16(&curr, 0); /* put in real messagesize later */
979 pkt_put_ipaddress(&curr, &olsr_cnf->router_id);
981 if (olsr_cnf->lq_fish > 0) {
984 if (ttl_index >= (int)ARRAYSIZE(ttl_list)) {
987 if (ttl_index >= 0) {
988 ttl = ttl_list[ttl_index];
991 pkt_put_u8(&curr, ttl);
994 pkt_put_u8(&curr, 0);
996 /* reserve sequence number lazy */
998 pkt_put_u16(&curr, 0);
999 pkt_put_u16(&curr, get_local_ansn_number());
1002 border_flags = curr;
1003 pkt_put_u16(&curr, 0xffff);
1005 last = msg_buffer + sizeof(msg_buffer) - olsr_cnf->ipsize - olsr_sizeof_TCLQ();
1007 OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
1008 /* allow fragmentation */
1010 struct nbr_entry *prevNbr;
1011 if (olsr_ipcmp(&nbr->nbr_addr, nextIp) != 0) {
1016 /* rewrite lower border flag */
1017 prevNbr = nbr_node_to_nbr(nbr->nbr_node.prev);
1018 *border_flags = calculate_border_flag(&prevNbr->nbr_addr, &nbr->nbr_addr);
1023 /* rewrite upper border flag */
1024 struct nbr_entry *prevNbr = nbr_node_to_nbr(nbr->nbr_node.prev);
1026 *(border_flags+1) = calculate_border_flag(&prevNbr->nbr_addr, &nbr->nbr_addr);
1027 *nextIp = nbr->nbr_addr;
1028 nextFragment = true;
1035 * Only consider symmetric neighbours.
1044 * Only consider MPRs and MPR selectors
1046 if (olsr_cnf->tc_redundancy == 1 && !nbr->is_mpr && nbr->mprs_count == 0) {
1053 * Only consider MPR selectors
1055 if (olsr_cnf->tc_redundancy == 0 && nbr->mprs_count == 0) {
1059 /* Set the entry's link quality */
1060 link = get_best_link_to_neighbor(&nbr->nbr_addr);
1066 if (link->linkcost >= LINK_COST_BROKEN) {
1067 /* don't advertisebroken links */
1071 pkt_put_ipaddress(&curr, &nbr->nbr_addr);
1072 olsr_serialize_tc_lq(&curr, link);
1075 } OLSR_FOR_ALL_NBR_ENTRIES_END()
1077 if (!sendTC && skip) {
1078 OLSR_DEBUG(LOG_TC, "Nothing to send for this TC...\n");
1082 /* late initialization of length and sequence number */
1083 pkt_put_u16(&seqno, get_msg_seqno());
1084 pkt_put_u16(&length_field, curr - msg_buffer);
1086 /* send to all interfaces */
1087 OLSR_FOR_ALL_INTERFACES(ifp) {
1088 if (net_outbuffer_bytes_left(ifp) < curr - msg_buffer) {
1090 set_buffer_timer(ifp);
1092 net_outbuffer_push(ifp, msg_buffer, curr - msg_buffer);
1093 } OLSR_FOR_ALL_INTERFACES_END(ifp)
1094 return nextFragment;
1098 olsr_output_lq_tc(void *ctx) {
1099 union olsr_ip_addr next;
1102 memset(&next, 0, sizeof(next));
1104 while ((skip = olsr_output_lq_tc_internal(ctx, &next, skip)));
1110 * indent-tabs-mode: nil