d2677cbbc64242f9644a5862b4172f6cefa9f007
[olsrd.git] / src / tc_set.h
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, 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 #ifndef _OLSR_TOP_SET
42 #define _OLSR_TOP_SET
43
44 #include "defs.h"
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"
52
53 /*
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.
58  */
59
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   struct nbr_entry *neighbor;          /* back pointer for edges to neighbor */
66   olsr_linkcost cost;                  /* metric for tc received by this tc */
67   bool virtual;                        /* 1 if this is a virtual edge created by the neighbors TC ? */
68   uint16_t ansn;                       /* ansn of this edge, used for multipart msgs */
69 };
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_entity 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 avl_tree mid_tree;            /* subtree for MID entries */
80   struct avl_tree hna_tree;            /* subtree for HNA entries */
81   struct link_entry *next_hop;         /* SPF calculated link to the 1st hop neighbor */
82   struct timer_entry *edge_gc_timer;   /* used for edge garbage collection */
83   struct timer_entry *validity_timer;  /* tc validity time */
84   bool virtual;                        /* true if node is virtual */
85   int tc_seq;                          /* sequence number of the tc message */
86   int mid_seq;                         /* sequence number of the mid message */
87   int hna_seq;                         /* sequence number of the hna message */
88   uint8_t msg_hops;                    /* hopcount as per the tc message */
89   uint8_t hops;                        /* SPF calculated hopcount */
90   uint16_t ansn;                       /* ANSN number of the tc message */
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 5 /* percent */
101
102 /*
103  * macros for traversing vertices, edges and prefixes in the link state database.
104  * it is recommended to use this because it hides all the internal
105  * datastructure from the callers.
106  *
107  * the loop prefetches the next node in order to not loose context if
108  * for example the caller wants to delete the current entry.
109  */
110 #define OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) avl_for_each_element_safe(&tc_tree, tc, vertex_node, iterator.loop, iterator.safe)
111 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator) avl_for_each_element_safe(&tc->edge_tree, tc_edge, edge_node, iterator.loop, iterator.safe)
112 #define OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp, iterator) avl_for_each_element_safe(&tc->prefix_tree, rtp, rtp_prefix_tree_node, iterator.loop, iterator.safe)
113
114 extern struct avl_tree EXPORT(tc_tree);
115 extern struct tc_entry *tc_myself;
116
117 extern struct olsr_cookie_info *EXPORT(tc_mem_cookie);
118
119 void olsr_init_tc(void);
120 void olsr_change_myself_tc(void);
121 void olsr_print_tc_table(void);
122 void olsr_time_out_tc_set(void);
123
124 /* tc msg input parser */
125 void olsr_input_tc(struct olsr_message *, struct interface *, union olsr_ip_addr *, enum duplicate_status);
126
127 /* tc_entry manipulation */
128 struct tc_entry *EXPORT(olsr_lookup_tc_entry) (const union olsr_ip_addr *);
129 struct tc_entry *EXPORT(olsr_locate_tc_entry)(const union olsr_ip_addr *);
130
131 /* tc_edge_entry manipulation */
132 struct tc_edge_entry *EXPORT(olsr_lookup_tc_edge) (struct tc_entry *, const union olsr_ip_addr *);
133 struct tc_edge_entry *olsr_add_tc_edge_entry(struct tc_entry *, const union olsr_ip_addr *, uint16_t);
134 void olsr_delete_tc_entry(struct tc_entry *);
135 void olsr_delete_tc_edge_entry(struct tc_edge_entry *);
136 bool olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *);
137 void olsr_set_tc_edge_timer(struct tc_edge_entry *, unsigned int);
138 void olsr_delete_all_tc_entries(void);
139 uint32_t EXPORT(getRelevantTcCount) (void);
140 uint16_t EXPORT(get_local_ansn_number)(void);
141 void increase_local_ansn_number(void);
142 void olsr_output_lq_tc(void *ifp);
143 #endif
144
145 /*
146  * Local Variables:
147  * c-basic-offset: 2
148  * indent-tabs-mode: nil
149  * End:
150  */