Rename "subsystems" directory to "base"
[oonf.git] / include / oonf / olsrv2 / olsrv2 / olsrv2_tc.h
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon version 2 (olsrd2)
4  * Copyright (c) 2004-2015, 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 /**
43  * @file
44  */
45
46 #ifndef OLSRV2_TC_H_
47 #define OLSRV2_TC_H_
48
49 #include <oonf/libcommon/avl.h>
50 #include <oonf/oonf.h>
51 #include <oonf/libcommon/netaddr.h>
52
53 #include <oonf/base/oonf_timer.h>
54
55 #include <oonf/nhdp/nhdp/nhdp.h>
56 #include <oonf/nhdp/nhdp/nhdp_domain.h>
57
58 #include <oonf/olsrv2/olsrv2/olsrv2.h>
59 #include <oonf/olsrv2/olsrv2/olsrv2_routing.h>
60
61 /**
62  * target types of olsrv2 edges
63  */
64 enum olsrv2_target_type
65 {
66   /*! target is another olsrv2 node */
67   OLSRV2_NODE_TARGET,
68
69   /*! target is just an address */
70   OLSRV2_ADDRESS_TARGET,
71
72   /*! target is an attached network */
73   OLSRV2_NETWORK_TARGET,
74 };
75
76 /*! memory class for olsrv2 nodes */
77 #define OLSRV2_CLASS_TC_NODE "olsrv2 tc node"
78
79 /*! memory class for olsrv2 edges */
80 #define OLSRV2_CLASS_TC_EDGE "olsrv2 tc edge"
81
82 /*! memory class for olsrv2 attached networks */
83 #define OLSRV2_CLASS_ATTACHED "olsrv2 tc attached network"
84
85 /*! memory class for olsrv2 endpoints */
86 #define OLSRV2_CLASS_ENDPOINT "olsrv2 tc attached network endpoint"
87
88 struct olsrv2_tc_edge;
89
90 /**
91  * represents a target that can be reached through a tc node.
92  *
93  * Might be another tc node, a neighbor address or an attached
94  * network.
95  */
96 struct olsrv2_tc_target {
97   /*! address or prefix of this node of the topology graph */
98   struct os_route_key prefix;
99
100   /*! type of target */
101   enum olsrv2_target_type type;
102
103   /*! internal data for dijkstra run */
104   struct olsrv2_dijkstra_node _dijkstra;
105 };
106
107 /**
108  * represents a tc node which might be connected to other
109  * nodes and endpoints.
110  */
111 struct olsrv2_tc_node {
112   /*! substructure to define target for Dijkstra Algorithm */
113   struct olsrv2_tc_target target;
114
115   /*! answer set number */
116   uint16_t ansn;
117
118   /*! reported interval time */
119   uint64_t interval_time;
120
121   /*! true if node has to be kept alive because of HELLOs */
122   bool direct_neighbor;
123
124   /*! node has announced it can do source specific routing */
125   bool source_specific;
126
127   /*! true if node has source specific attached networks per domain */
128   bool ss_attached_networks[NHDP_MAXIMUM_DOMAINS];
129
130   /*! time until this node has to be removed */
131   struct oonf_timer_instance _validity_time;
132
133   /*! tree of olsrv2_tc_edges */
134   struct avl_tree _edges;
135
136   /*! tree of olsrv2_tc_attached_networks */
137   struct avl_tree _attached_networks;
138
139   /*! node for tree of tc_nodes */
140   struct avl_node _originator_node;
141 };
142
143 /**
144  * represents an edge between two tc nodes
145  */
146 struct olsrv2_tc_edge {
147   /*! pointer to source of edge */
148   struct olsrv2_tc_node *src;
149
150   /*! pointer to destination of edge */
151   struct olsrv2_tc_node *dst;
152
153   /*! pointer to inverse edge */
154   struct olsrv2_tc_edge *inverse;
155
156   /*! link cost of edge */
157   uint32_t cost[NHDP_MAXIMUM_DOMAINS];
158
159   /*! answer set number which set this edge */
160   uint16_t ansn;
161
162   /**
163    * true if this link is only virtual
164    * (it only exists because the inverse edge was received).
165    */
166   bool virtual;
167
168   /*! node for tree of source node */
169   struct avl_node _node;
170 };
171
172 /**
173  * represents a connection from a tc node to
174  * an endpoint, either a neighbor address or an attached network
175  */
176 struct olsrv2_tc_attachment {
177   /*! pointer to source of edge */
178   struct olsrv2_tc_node *src;
179
180   /*! pointer to destination of edge */
181   struct olsrv2_tc_endpoint *dst;
182
183   /*! link cost of edge */
184   uint32_t cost[NHDP_MAXIMUM_DOMAINS];
185
186   /*! distance to attached network */
187   uint8_t distance[NHDP_MAXIMUM_DOMAINS];
188
189   /*! answer set number which set this edge */
190   uint16_t ansn;
191
192   /*! node for tree of source node */
193   struct avl_node _src_node;
194
195   /*! node for tree of endpoint nodes */
196   struct avl_node _endpoint_node;
197 };
198
199 /**
200  * Represents an endpoint of the Dijkstra graph, which
201  * does not spawn new edges of the graph.
202  *
203  * Might be a neighbor address or an attached network
204  */
205 struct olsrv2_tc_endpoint {
206   /*! substructure to define target for Dijkstra Algorithm */
207   struct olsrv2_tc_target target;
208
209   /*! tree of attached networks */
210   struct avl_tree _attached_networks;
211
212   /*! node for global tree of endpoints */
213   struct avl_node _node;
214 };
215
216 void olsrv2_tc_init(void);
217 void olsrv2_tc_cleanup(void);
218
219 EXPORT struct olsrv2_tc_node *olsrv2_tc_node_add(struct netaddr *, uint64_t vtime, uint16_t ansn);
220 EXPORT void olsrv2_tc_node_remove(struct olsrv2_tc_node *);
221
222 EXPORT struct olsrv2_tc_edge *olsrv2_tc_edge_add(struct olsrv2_tc_node *, struct netaddr *);
223 EXPORT bool olsrv2_tc_edge_remove(struct olsrv2_tc_edge *);
224
225 EXPORT struct olsrv2_tc_attachment *olsrv2_tc_endpoint_add(struct olsrv2_tc_node *, struct os_route_key *, bool mesh);
226 EXPORT void olsrv2_tc_endpoint_remove(struct olsrv2_tc_attachment *);
227
228 void olsrv2_tc_trigger_change(struct olsrv2_tc_node *);
229
230 EXPORT struct avl_tree *olsrv2_tc_get_tree(void);
231 EXPORT struct avl_tree *olsrv2_tc_get_endpoint_tree(void);
232
233 /**
234  * @param originator originator address of a tc node
235  * @return pointer to tc node, NULL if not found
236  */
237 static INLINE struct olsrv2_tc_node *
238 olsrv2_tc_node_get(struct netaddr *originator) {
239   struct olsrv2_tc_node *node;
240
241   return avl_find_element(olsrv2_tc_get_tree(), originator, node, _originator_node);
242 }
243
244 /**
245  * @param node pointer to olsrv2 node
246  * @return true if node is virtual
247  */
248 static INLINE bool
249 olsrv2_tc_is_node_virtual(struct olsrv2_tc_node *node) {
250   return !oonf_timer_is_active(&node->_validity_time);
251 }
252
253 /**
254  * @param prefix network prefix of tc endpoint
255  * @return pointer to tc endpoint, NULL if not found
256  */
257 static INLINE struct olsrv2_tc_endpoint *
258 olsrv2_tc_endpoint_get(struct netaddr *prefix) {
259   struct olsrv2_tc_endpoint *end;
260
261   return avl_find_element(olsrv2_tc_get_endpoint_tree(), prefix, end, _node);
262 }
263
264 static INLINE uint32_t
265 olsrv2_tc_attachment_get_metric(struct nhdp_domain *domain, struct olsrv2_tc_attachment *attached) {
266   return attached->cost[domain->index];
267 }
268
269 static INLINE uint8_t
270 olsrv2_tc_attachment_get_distance(struct nhdp_domain *domain, struct olsrv2_tc_attachment *attached) {
271   return attached->distance[domain->index];
272 }
273
274 static INLINE uint32_t
275 olsrv2_tc_edge_get_metric(struct nhdp_domain *domain, struct olsrv2_tc_edge *edge) {
276   return edge->cost[domain->index];
277 }
278
279 #endif /* OLSRV2_TC_H_ */