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 "common/avl.h"
46 #include "common/list.h"
47 #include "olsr_protocol.h"
48 #include "lq_packet.h"
49 #include "scheduler.h"
50 #include "olsr_cookie.h"
51 #include "duplicate_set.h"
54 * This file holds the definitions for the link state database.
55 * The lsdb consists of nodes and edges.
56 * During input parsing all nodes and edges are extracted and synthesized.
57 * The SPF calculation operates on these datasets.
60 struct tc_edge_entry {
61 struct avl_node edge_node; /* edge_tree node in tc_entry */
62 union olsr_ip_addr T_dest_addr; /* edge_node key */
63 struct tc_edge_entry *edge_inv; /* shortcut, used during SPF calculation */
64 struct tc_entry *tc; /* backpointer to owning tc entry */
65 olsr_linkcost cost; /* metric for tc received by this tc */
66 olsr_linkcost common_cost; /* common metric of both edges used for SPF calculation */
67 unsigned int is_local:1; /* 1 if this is a local edge */
68 unsigned int is_virtual:1; /* 1 if this is a virtual edge created by the neighbors TC ? */
69 uint16_t ansn; /* ansn of this edge, used for multipart msgs */
72 AVLNODE2STRUCT(edge_tree2tc_edge, struct tc_edge_entry, edge_node);
75 struct avl_node vertex_node; /* node keyed by ip address */
76 union olsr_ip_addr addr; /* vertex_node key */
77 struct avl_node cand_tree_node; /* SPF candidate heap, node keyed by path_etx */
78 olsr_linkcost path_cost; /* SPF calculated distance, cand_tree_node key */
79 struct list_node path_list_node; /* SPF result list */
80 struct avl_tree edge_tree; /* subtree for edges */
81 struct avl_tree prefix_tree; /* subtree for prefixes */
82 struct avl_tree mid_tree; /* subtree for MID entries */
83 struct avl_tree hna_tree; /* subtree for HNA entries */
84 struct timer_entry *mid_timer; /* aging timer for MID advertisements */
85 struct link_entry *next_hop; /* SPF calculated link to the 1st hop neighbor */
86 struct timer_entry *edge_gc_timer; /* used for edge garbage collection */
87 struct timer_entry *validity_timer; /* tc validity time */
88 uint32_t refcount; /* reference counter */
89 bool is_virtual; /* true if tc is already timed out */
90 int tc_seq; /* sequence number of the tc message */
91 int mid_seq; /* sequence number of the mid message */
92 int hna_seq; /* sequence number of the hna message */
93 uint8_t msg_hops; /* hopcount as per the tc message */
94 uint8_t hops; /* SPF calculated hopcount */
95 uint16_t ansn; /* ANSN number of the tc message */
96 uint16_t ignored; /* how many TC messages ignored in a sequence
97 (kindof emergency brake) */
98 uint16_t err_seq; /* sequence number of an unplausible TC */
99 bool err_seq_valid; /* do we have an error (unplauible seq/ansn) */
103 * Garbage collection time for edges.
104 * This is used for multipart messages.
106 #define OLSR_TC_EDGE_GC_TIME (2*1000) /* milliseconds */
107 #define OLSR_TC_EDGE_GC_JITTER 5 /* percent */
109 #define OLSR_TC_VTIME_JITTER 5 /* percent */
112 AVLNODE2STRUCT(vertex_tree2tc, struct tc_entry, vertex_node);
113 AVLNODE2STRUCT(cand_tree2tc, struct tc_entry, cand_tree_node);
114 LISTNODE2STRUCT(pathlist2tc, struct tc_entry, path_list_node);
117 * macros for traversing vertices, edges and prefixes in the link state database.
118 * it is recommended to use this because it hides all the internal
119 * datastructure from the callers.
121 * the loop prefetches the next node in order to not loose context if
122 * for example the caller wants to delete the current entry.
124 #define OLSR_FOR_ALL_TC_ENTRIES(tc) \
126 struct avl_node *tc_tree_node, *next_tc_tree_node; \
127 for (tc_tree_node = avl_walk_first(&tc_tree); \
128 tc_tree_node; tc_tree_node = next_tc_tree_node) { \
129 next_tc_tree_node = avl_walk_next(tc_tree_node); \
130 tc = vertex_tree2tc(tc_tree_node);
131 #define OLSR_FOR_ALL_TC_ENTRIES_END(tc) }}
133 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) \
135 struct avl_node *tc_edge_node, *next_tc_edge_node; \
136 for (tc_edge_node = avl_walk_first(&tc->edge_tree); \
137 tc_edge_node; tc_edge_node = next_tc_edge_node) { \
138 next_tc_edge_node = avl_walk_next(tc_edge_node); \
139 tc_edge = edge_tree2tc_edge(tc_edge_node);
140 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge) }}
142 #define OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) \
144 struct avl_node *rtp_node, *next_rtp_node; \
145 for (rtp_node = avl_walk_first(&tc->prefix_tree); \
146 rtp_node; rtp_node = next_rtp_node) { \
147 next_rtp_node = avl_walk_next(rtp_node); \
148 rtp = rtp_prefix_tree2rtp(rtp_node);
149 #define OLSR_FOR_ALL_PREFIX_ENTRIES_END(tc, rtp) }}
151 extern struct avl_tree EXPORT(tc_tree);
152 extern struct tc_entry *tc_myself;
153 extern struct olsr_cookie_info *tc_mem_cookie;
154 extern struct olsr_cookie_info *spf_backoff_timer_cookie;
156 void olsr_init_tc(void);
157 void olsr_change_myself_tc(void);
158 void olsr_print_tc_table(void);
159 void olsr_time_out_tc_set(void);
161 /* tc msg input parser */
162 void olsr_input_tc(union olsr_message *, struct interface *, union olsr_ip_addr *, enum duplicate_status);
164 /* tc_entry manipulation */
165 struct tc_entry *EXPORT(olsr_lookup_tc_entry) (const union olsr_ip_addr *);
166 struct tc_entry *olsr_locate_tc_entry(const union olsr_ip_addr *);
169 * Increment the reference counter.
172 olsr_lock_tc_entry(struct tc_entry *tc)
178 * Unlock and free a tc_entry once all references are gone.
181 olsr_unlock_tc_entry(struct tc_entry *tc)
183 if (--tc->refcount == 0) { /* All references are gone. */
184 olsr_cookie_free(tc_mem_cookie, tc);
188 /* tc_edge_entry manipulation */
189 struct tc_edge_entry *EXPORT(olsr_lookup_tc_edge) (struct tc_entry *, union olsr_ip_addr *);
190 struct tc_edge_entry *olsr_add_tc_edge_entry(struct tc_entry *, union olsr_ip_addr *, uint16_t);
191 void olsr_delete_tc_entry(struct tc_entry *);
192 void olsr_delete_tc_edge_entry(struct tc_edge_entry *);
193 bool olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *);
194 void olsr_set_tc_edge_timer(struct tc_edge_entry *, unsigned int);
195 void olsr_delete_all_tc_entries(void);
196 uint32_t EXPORT(getRelevantTcCount) (void);
197 void olsr_output_lq_tc(void *ifp);
203 * indent-tabs-mode: nil