4980836d706e921dde1004d18954ffc91ec9f46d
[olsrd.git] / src / duplicate_set.c
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
42 #include "duplicate_set.h"
43 #include "ipcalc.h"
44 #include "common/avl.h"
45 #include "olsr.h"
46 #include "mid_set.h"
47 #include "scheduler.h"
48 #include "olsr_time.h"
49 #include "olsr_cookie.h"
50 #include "olsr_logging.h"
51
52 #include <stdlib.h>
53
54 struct avl_tree forward_set, processing_set;
55
56 /* Some cookies for stats keeping */
57 static struct olsr_cookie_info *duplicate_timer_cookie = NULL;
58 static struct olsr_cookie_info *duplicate_mem_cookie = NULL;
59
60 int
61 olsr_seqno_diff(uint16_t reference, uint16_t other)
62 {
63   int diff;
64
65   diff = (int)reference - (int)other;
66
67   // overflow ?
68   if (diff >= (1 << 15)) {
69     diff -= (1 << 16);
70   } else if (diff < -(1 << 15)) {
71     diff += (1 << 16);
72   }
73   return diff;
74 }
75
76 void
77 olsr_init_duplicate_set(void)
78 {
79   OLSR_INFO(LOG_DUPLICATE_SET, "Initialize duplicate set...\n");
80
81   avl_init(&forward_set, avl_comp_default);
82   avl_init(&processing_set, avl_comp_default);
83
84   /*
85    * Get some cookies for getting stats to ease troubleshooting.
86    */
87   duplicate_timer_cookie = olsr_alloc_cookie("Duplicate Set", OLSR_COOKIE_TYPE_TIMER);
88
89   duplicate_mem_cookie = olsr_alloc_cookie("dup_entry", OLSR_COOKIE_TYPE_MEMORY);
90   olsr_cookie_set_memory_size(duplicate_mem_cookie, sizeof(struct dup_entry));
91 }
92
93 static struct dup_entry *
94 olsr_create_duplicate_entry(union olsr_ip_addr *ip, uint16_t seqnr)
95 {
96   struct dup_entry *entry;
97
98   entry = olsr_cookie_malloc(duplicate_mem_cookie);
99   if (entry != NULL) {
100     memcpy(&entry->ip, ip, olsr_cnf->ip_version == AF_INET ? sizeof(entry->ip.v4) : sizeof(entry->ip.v6));
101     entry->seqnr = seqnr;
102     entry->too_low_counter = 0;
103     entry->avl.key = &entry->ip;
104     entry->array = 0;
105   }
106   return entry;
107 }
108
109 static void
110 olsr_delete_duplicate_entry(struct dup_entry *entry)
111 {
112   avl_delete(entry->tree, &entry->avl);
113   entry->tree = NULL;
114   olsr_stop_timer(entry->validity_timer);
115   entry->validity_timer = NULL;
116   olsr_cookie_free(duplicate_mem_cookie, entry);
117 }
118
119 static void
120 olsr_expire_duplicate_entry(void *context)
121 {
122   struct dup_entry *entry = context;
123
124   olsr_delete_duplicate_entry(entry);
125 }
126
127 /**
128  * Clean up the house. Called during shutdown.
129  */
130 void
131 olsr_flush_duplicate_entries(void)
132 {
133   struct dup_entry *entry;
134
135   OLSR_FOR_ALL_FORWARD_DUP_ENTRIES(entry) {
136     olsr_delete_duplicate_entry(entry);
137   } OLSR_FOR_ALL_FORWARD_DUP_ENTRIES_END()
138     OLSR_FOR_ALL_PROCESS_DUP_ENTRIES(entry) {
139     olsr_delete_duplicate_entry(entry);
140   } OLSR_FOR_ALL_PROCESS_DUP_ENTRIES_END()
141 }
142
143 bool
144 olsr_is_duplicate_message(union olsr_message *m, bool forwarding, enum duplicate_status *status)
145 {
146   struct avl_tree *tree;
147   struct dup_entry *entry;
148   int diff;
149   union olsr_ip_addr *mainIp;
150   uint32_t valid_until;
151   uint16_t seqnr;
152   union olsr_ip_addr *ip;
153   enum duplicate_status dummy = 0;
154
155 #if !defined(REMOVE_LOG_DEBUG)
156   struct ipaddr_str buf;
157 #endif
158
159   if (status == NULL) {
160     status = &dummy;
161   }
162
163   tree = forwarding ? &forward_set : &processing_set;
164   if (olsr_cnf->ip_version == AF_INET) {
165     seqnr = ntohs(m->v4.seqno);
166     ip = (union olsr_ip_addr *)&m->v4.originator;
167   } else {
168     seqnr = ntohs(m->v6.seqno);
169     ip = (union olsr_ip_addr *)&m->v6.originator;
170   }
171
172   // get main address
173   mainIp = olsr_lookup_main_addr_by_alias(ip);
174   if (mainIp == NULL) {
175     mainIp = ip;
176   }
177
178   valid_until = GET_TIMESTAMP(DUPLICATE_VTIME);
179
180   /* Check if entry exists */
181   entry = (struct dup_entry *)avl_find(tree, ip);
182   if (entry == NULL) {
183     entry = olsr_create_duplicate_entry(ip, seqnr);
184     if (entry != NULL) {
185       avl_insert(tree, &entry->avl, 0);
186       entry->tree = tree;
187       entry->validity_timer = olsr_start_timer(DUPLICATE_CLEANUP_INTERVAL, DUPLICATE_CLEANUP_JITTER,
188                                                OLSR_TIMER_ONESHOT, &olsr_expire_duplicate_entry, entry, duplicate_timer_cookie);
189     }
190
191     *status = NEW_OLSR_MESSAGE;
192     return false;               // okay, we process this package
193   } else {
194
195     /*
196      * Refresh timer.
197      */
198     olsr_change_timer(entry->validity_timer, DUPLICATE_CLEANUP_INTERVAL, DUPLICATE_CLEANUP_JITTER, OLSR_TIMER_ONESHOT);
199   }
200
201   diff = olsr_seqno_diff(seqnr, entry->seqnr);
202
203   if (diff < -31) {
204     entry->too_low_counter++;
205
206     // client did restart with a lower number ?
207     if (entry->too_low_counter > 16) {
208       entry->too_low_counter = 0;
209       entry->seqnr = seqnr;
210       entry->array = 1;
211
212       /* start with a new sequence number, so NO duplicate */
213       *status = RESET_SEQNO_OLSR_MESSAGE;
214       return false;
215     }
216     OLSR_DEBUG(LOG_DUPLICATE_SET, "blocked %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
217
218     /* much too old */
219     *status = TOO_OLD_OLSR_MESSAGE;
220     return true;
221   }
222
223   entry->too_low_counter = 0;
224   if (diff <= 0) {
225     uint32_t bitmask = 1 << ((uint32_t) (-diff));
226
227     if ((entry->array & bitmask) != 0) {
228       OLSR_DEBUG(LOG_DUPLICATE_SET, "blocked %x (diff=%d,mask=%08x) from %s\n", seqnr, diff,
229                  entry->array, olsr_ip_to_string(&buf, mainIp));
230
231       /* duplicate ! */
232       *status = DUPLICATE_OLSR_MESSAGE;
233       return true;
234     }
235     entry->array |= bitmask;
236     OLSR_DEBUG(LOG_DUPLICATE_SET, "processed %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
237
238     /* no duplicate */
239     *status = OLD_OLSR_MESSAGE;
240     return false;
241   } else if (diff < 32) {
242     entry->array <<= (uint32_t) diff;
243   } else {
244     entry->array = 0;
245   }
246   entry->array |= 1;
247   entry->seqnr = seqnr;
248   OLSR_DEBUG(LOG_DUPLICATE_SET, "processed %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
249
250   /* no duplicate */
251   *status = NEW_OLSR_MESSAGE;
252   return false;
253 }
254
255 void
256 olsr_print_duplicate_table(void)
257 {
258 #if !defined REMOVE_LOG_INFO
259   /* The whole function makes no sense without it. */
260   struct dup_entry *entry;
261   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
262
263   OLSR_INFO(LOG_DUPLICATE_SET, "\n--- %s ------------------------------------------------- DUPLICATE SET (forwarding)\n\n",
264             olsr_wallclock_string());
265   OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %8s %s\n", ipwidth, "Node IP", "DupArray", "VTime");
266
267   OLSR_FOR_ALL_FORWARD_DUP_ENTRIES(entry) {
268     struct ipaddr_str addrbuf;
269     OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %08x %s\n",
270                  ipwidth, olsr_ip_to_string(&addrbuf, entry->avl.key), entry->array,
271                  olsr_clock_string(entry->validity_timer->timer_clock));
272   } OLSR_FOR_ALL_FORWARD_DUP_ENTRIES_END()
273
274     OLSR_INFO(LOG_DUPLICATE_SET, "\n--- %s ------------------------------------------------- DUPLICATE SET (processing)\n\n",
275               olsr_wallclock_string());
276   OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %8s %s\n", ipwidth, "Node IP", "DupArray", "VTime");
277
278   OLSR_FOR_ALL_PROCESS_DUP_ENTRIES(entry) {
279     struct ipaddr_str addrbuf;
280     OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %08x %s\n",
281                  ipwidth, olsr_ip_to_string(&addrbuf, entry->avl.key), entry->array,
282                  olsr_clock_string(entry->validity_timer->timer_clock));
283   } OLSR_FOR_ALL_PROCESS_DUP_ENTRIES_END()
284 #endif
285 }
286
287 /*
288  * Local Variables:
289  * c-basic-offset: 2
290  * indent-tabs-mode: nil
291  * End:
292  */