8bc7a219b59cd18f560b79ac9be4cd239380cdba
[olsrd.git] / src / tc_set.h
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
5  * LSDB rewrite (c) 2007, Hannes Gredler (hannes@gredler.at)
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without 
9  * modification, are permitted provided that the following conditions 
10  * are met:
11  *
12  * * Redistributions of source code must retain the above copyright 
13  *   notice, this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above copyright 
15  *   notice, this list of conditions and the following disclaimer in 
16  *   the documentation and/or other materials provided with the 
17  *   distribution.
18  * * Neither the name of olsr.org, olsrd nor the names of its 
19  *   contributors may be used to endorse or promote products derived 
20  *   from this software without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
33  * POSSIBILITY OF SUCH DAMAGE.
34  *
35  * Visit http://www.olsr.org for more information.
36  *
37  * If you find this software useful feel free to make a donation
38  * to the project. For more information see the website or contact
39  * the copyright holders.
40  *
41  */
42
43 #ifndef _OLSR_TOP_SET
44 #define _OLSR_TOP_SET
45
46 #include "defs.h"
47 #include "packet.h"
48 #include "common/avl.h"
49 #include "common/list.h"
50 #include "scheduler.h"
51
52 /*
53  * This file holds the definitions for the link state database.
54  * The lsdb consists of nodes and edges.
55  * During input parsing all nodes and edges are extracted and synthesized.
56  * The SPF calculation operates on these datasets.
57  */
58
59 struct tc_edge_entry {
60   struct avl_node edge_node;           /* edge_tree node in tc_entry */
61   union olsr_ip_addr T_dest_addr;      /* edge_node key */
62   struct tc_edge_entry *edge_inv;      /* shortcut, used during SPF calculation */
63   struct tc_entry *tc;                 /* backpointer to owning tc entry */
64   olsr_linkcost cost;                  /* metric used for SPF calculation */
65   olsr_u16_t ansn;                     /* ansn of this edge, used for multipart msgs */
66   char linkquality[0];
67 };
68
69 AVLNODE2STRUCT(edge_tree2tc_edge, struct tc_edge_entry, edge_node);
70
71 struct tc_entry {
72   struct avl_node vertex_node;         /* node keyed by ip address */
73   union olsr_ip_addr addr;             /* vertex_node key */
74   struct avl_node cand_tree_node;      /* SPF candidate heap, node keyed by path_etx */
75   olsr_linkcost path_cost;             /* SPF calculated distance, cand_tree_node key */
76   struct list_node path_list_node;     /* SPF result list */
77   struct avl_tree edge_tree;           /* subtree for edges */
78   struct avl_tree prefix_tree;         /* subtree for prefixes */
79   struct link_entry *next_hop;         /* SPF calculated link to the 1st hop neighbor */
80   struct timer_entry *edge_gc_timer;   /* used for edge garbage collection */
81   struct timer_entry *validity_timer;  /* tc validity time */
82   olsr_u32_t refcount;                 /* reference counter */
83   olsr_u16_t msg_seq;                  /* sequence number of the tc message */
84   olsr_u8_t msg_hops;                  /* hopcount as per the tc message */
85   olsr_u8_t hops;                      /* SPF calculated hopcount */
86   olsr_u16_t ansn;                     /* ANSN number of the tc message */
87   olsr_u16_t ignored;                  /* how many TC messages ignored in a sequence
88                                           (kindof emergency brake) */
89   olsr_u16_t err_seq;                  /* sequence number of an unplausible TC */
90   olsr_bool err_seq_valid;             /* do we have an error (unplauible seq/ansn) */
91 };
92
93 /*
94  * Garbage collection time for edges.
95  * This is used for multipart messages.
96  */
97 #define OLSR_TC_EDGE_GC_TIME (2*1000)   /* milliseconds */
98 #define OLSR_TC_EDGE_GC_JITTER 5        /* percent */
99
100 #define OLSR_TC_VTIME_JITTER 25 /* percent */
101
102
103 AVLNODE2STRUCT(vertex_tree2tc, struct tc_entry, vertex_node);
104 AVLNODE2STRUCT(cand_tree2tc, struct tc_entry, cand_tree_node);
105 LISTNODE2STRUCT(pathlist2tc, struct tc_entry, path_list_node);
106
107 /*
108  * macros for traversing vertices, edges and prefixes in the link state database.
109  * it is recommended to use this because it hides all the internal
110  * datastructure from the callers.
111  *
112  * the loop prefetches the next node in order to not loose context if
113  * for example the caller wants to delete the current entry.
114  */
115 #define OLSR_FOR_ALL_TC_ENTRIES(tc) \
116 { \
117   struct avl_node *tc_tree_node, *next_tc_tree_node; \
118   for (tc_tree_node = avl_walk_first(&tc_tree); \
119     tc_tree_node; tc_tree_node = next_tc_tree_node) { \
120     next_tc_tree_node = avl_walk_next(tc_tree_node); \
121     tc = vertex_tree2tc(tc_tree_node);
122 #define OLSR_FOR_ALL_TC_ENTRIES_END(tc) }}
123
124 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) \
125 { \
126   struct avl_node *tc_edge_node, *next_tc_edge_node; \
127   for (tc_edge_node = avl_walk_first(&tc->edge_tree); \
128     tc_edge_node; tc_edge_node = next_tc_edge_node) { \
129     next_tc_edge_node = avl_walk_next(tc_edge_node); \
130     tc_edge = edge_tree2tc_edge(tc_edge_node);
131 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge) }}
132
133 #define OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) \
134 { \
135   struct avl_node *rtp_node, *next_rtp_node; \
136   for (rtp_node = avl_walk_first(&tc->prefix_tree); \
137     rtp_node; rtp_node = next_rtp_node) { \
138     next_rtp_node = avl_walk_next(rtp_node); \
139     rtp = rtp_prefix_tree2rtp(rtp_node);
140 #define OLSR_FOR_ALL_PREFIX_ENTRIES_END(tc, rtp) }}
141
142 extern struct avl_tree tc_tree;
143 extern struct tc_entry *tc_myself;
144
145 void olsr_init_tc(void);
146 void olsr_change_myself_tc(void);
147 void olsr_print_tc_table(void);
148 void olsr_time_out_tc_set(void);
149
150 /* tc msg input parser */
151 void olsr_input_tc(union olsr_message *, struct interface *,
152                    union olsr_ip_addr *from);
153
154 /* tc_entry manipulation */
155 struct tc_entry *olsr_lookup_tc_entry(union olsr_ip_addr *);
156 struct tc_entry *olsr_locate_tc_entry(union olsr_ip_addr *);
157 void olsr_lock_tc_entry(struct tc_entry *);
158 void olsr_unlock_tc_entry(struct tc_entry *);
159
160 /* tc_edge_entry manipulation */
161 olsr_bool olsr_delete_outdated_tc_edges(struct tc_entry *);
162 char *olsr_tc_edge_to_string(struct tc_edge_entry *);
163 struct tc_edge_entry *olsr_lookup_tc_edge(struct tc_entry *,
164                                           union olsr_ip_addr *);
165 struct tc_edge_entry *olsr_add_tc_edge_entry(struct tc_entry *,
166                                              union olsr_ip_addr *, olsr_u16_t);
167 void olsr_delete_tc_entry(struct tc_entry *);
168 void olsr_delete_tc_edge_entry(struct tc_edge_entry *);
169 olsr_bool olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *);
170 void olsr_set_tc_edge_timer(struct tc_edge_entry *, unsigned int);
171 // static olsr_bool olsr_etx_significant_change(float, float);
172
173 #endif
174
175 /*
176  * Local Variables:
177  * c-basic-offset: 2
178  * End:
179  */