1079db06846564267196f611dfe08e875449c1c9
[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 static void olsr_cleanup_duplicate_entry(void *unused);
55
56 static struct avl_tree forward_set, processing_set;
57 static struct timer_entry *duplicate_cleanup_timer;
58
59 /* Some cookies for stats keeping */
60 static struct olsr_cookie_info *duplicate_timer_cookie = NULL;
61 static struct olsr_cookie_info *duplicate_mem_cookie = NULL;
62
63 void
64 olsr_init_duplicate_set(void)
65 {
66   OLSR_INFO(LOG_DUPLICATE_SET, "Initialize duplicate set...\n");
67
68   avl_init(&forward_set, avl_comp_default);
69   avl_init(&processing_set, avl_comp_default);
70
71   /*
72    * Get some cookies for getting stats to ease troubleshooting.
73    */
74   duplicate_timer_cookie = olsr_alloc_cookie("Duplicate Set", OLSR_COOKIE_TYPE_TIMER);
75
76   duplicate_mem_cookie = olsr_alloc_cookie("dup_entry", OLSR_COOKIE_TYPE_MEMORY);
77   olsr_cookie_set_memory_size(duplicate_mem_cookie, sizeof(struct dup_entry));
78
79   olsr_set_timer(&duplicate_cleanup_timer, DUPLICATE_CLEANUP_INTERVAL,
80                  DUPLICATE_CLEANUP_JITTER, OLSR_TIMER_PERIODIC, &olsr_cleanup_duplicate_entry, NULL, duplicate_timer_cookie);
81 }
82
83 static struct dup_entry *
84 olsr_create_duplicate_entry(union olsr_ip_addr *ip, uint16_t seqnr)
85 {
86   struct dup_entry *entry;
87   entry = olsr_cookie_malloc(duplicate_mem_cookie);
88   if (entry != NULL) {
89     memcpy(&entry->ip, ip, olsr_cnf->ip_version == AF_INET ? sizeof(entry->ip.v4) : sizeof(entry->ip.v6));
90     entry->seqnr = seqnr;
91     entry->too_low_counter = 0;
92     entry->avl.key = &entry->ip;
93     entry->array = 0;
94   }
95   return entry;
96 }
97
98 static void
99 olsr_delete_duplicate_entry(struct dup_entry *entry, bool forward)
100 {
101   avl_delete(forward ? &forward_set : &processing_set, &entry->avl);
102   olsr_cookie_free(duplicate_mem_cookie, entry);
103 }
104
105 static void
106 olsr_cleanup_duplicate_entry(void __attribute__ ((unused)) * unused)
107 {
108   struct dup_entry *entry;
109
110   OLSR_FOR_ALL_DUP_ENTRIES(entry, true) {
111     if (TIMED_OUT(entry->valid_until)) {
112       olsr_delete_duplicate_entry(entry, true);
113     }
114   }
115   OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
116   OLSR_FOR_ALL_DUP_ENTRIES(entry, false) {
117     if (TIMED_OUT(entry->valid_until)) {
118       olsr_delete_duplicate_entry(entry, false);
119     }
120   }
121   OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
122 }
123
124 /**
125  * Clean up the house. Called during shutdown.
126  */
127 void
128 olsr_flush_duplicate_entries(void)
129 {
130   struct dup_entry *entry;
131
132   olsr_stop_timer(duplicate_cleanup_timer);
133   duplicate_cleanup_timer = NULL;
134
135   OLSR_FOR_ALL_DUP_ENTRIES(entry, true) {
136     olsr_delete_duplicate_entry(entry, true);
137   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
138   OLSR_FOR_ALL_DUP_ENTRIES(entry, false) {
139     olsr_delete_duplicate_entry(entry, false);
140   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
141 }
142
143 int
144 olsr_message_is_duplicate(union olsr_message *m, bool forwarding)
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
154 #if !defined(REMOVE_LOG_DEBUG)
155   struct ipaddr_str buf;
156 #endif
157
158   tree = forwarding ? &forward_set : &processing_set;
159   if (olsr_cnf->ip_version == AF_INET) {
160     seqnr = ntohs(m->v4.seqno);
161     ip = (union olsr_ip_addr *)&m->v4.originator;
162   } else {
163     seqnr = ntohs(m->v6.seqno);
164     ip = (union olsr_ip_addr *)&m->v6.originator;
165   }
166
167   // get main address
168   mainIp = olsr_lookup_main_addr_by_alias(ip);
169   if (mainIp == NULL) {
170     mainIp = ip;
171   }
172
173   valid_until = GET_TIMESTAMP(DUPLICATE_VTIME);
174
175   entry = (struct dup_entry *)avl_find(tree, ip);
176   if (entry == NULL) {
177     entry = olsr_create_duplicate_entry(ip, seqnr);
178     if (entry != NULL) {
179       avl_insert(tree, &entry->avl, 0);
180       entry->valid_until = valid_until;
181     }
182     return false;               // okay, we process this package
183   }
184
185   diff = (int)seqnr - (int)(entry->seqnr);
186
187   // update timestamp
188   if (valid_until > entry->valid_until) {
189     entry->valid_until = valid_until;
190   }
191   // overflow ?
192   if (diff > (1 << 15)) {
193     diff -= (1 << 16);
194   }
195
196   if (diff < -31) {
197     entry->too_low_counter++;
198
199     // client did restart with a lower number ?
200     if (entry->too_low_counter > 16) {
201       entry->too_low_counter = 0;
202       entry->seqnr = seqnr;
203       entry->array = 1;
204       return false;             /* start with a new sequence number, so NO duplicate */
205     }
206     OLSR_DEBUG(LOG_DUPLICATE_SET, "blocked %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
207     return true;                /* duplicate ! */
208   }
209
210   entry->too_low_counter = 0;
211   if (diff <= 0) {
212     uint32_t bitmask = 1 << ((uint32_t) (-diff));
213
214     if ((entry->array & bitmask) != 0) {
215       OLSR_DEBUG(LOG_DUPLICATE_SET, "blocked %x (diff=%d,mask=%08x) from %s\n", seqnr, diff,
216                  entry->array, olsr_ip_to_string(&buf, mainIp));
217       return true;              /* duplicate ! */
218     }
219     entry->array |= bitmask;
220     OLSR_DEBUG(LOG_DUPLICATE_SET, "processed %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
221     return false;               /* no duplicate */
222   } else if (diff < 32) {
223     entry->array <<= (uint32_t) diff;
224   } else {
225     entry->array = 0;
226   }
227   entry->array |= 1;
228   entry->seqnr = seqnr;
229   OLSR_DEBUG(LOG_DUPLICATE_SET, "processed %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
230   return false;                 /* no duplicate */
231 }
232
233 void
234 olsr_print_duplicate_table(void)
235 {
236 #if !defined REMOVE_LOG_INFO
237   /* The whole function makes no sense without it. */
238   struct dup_entry *entry;
239   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
240
241   OLSR_INFO(LOG_DUPLICATE_SET, "\n--- %s ------------------------------------------------- DUPLICATE SET (forwarding)\n\n",
242             olsr_wallclock_string());
243   OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %8s %s\n", ipwidth, "Node IP", "DupArray", "VTime");
244
245   OLSR_FOR_ALL_DUP_ENTRIES(entry, true) {
246     struct ipaddr_str addrbuf;
247     OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %08x %s\n",
248                  ipwidth, olsr_ip_to_string(&addrbuf, entry->avl.key), entry->array, olsr_clock_string(entry->valid_until));
249   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
250
251   OLSR_INFO(LOG_DUPLICATE_SET, "\n--- %s ------------------------------------------------- DUPLICATE SET (processing)\n\n",
252             olsr_wallclock_string());
253   OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %8s %s\n", ipwidth, "Node IP", "DupArray", "VTime");
254
255   OLSR_FOR_ALL_DUP_ENTRIES(entry, false) {
256     struct ipaddr_str addrbuf;
257     OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %08x %s\n",
258                  ipwidth, olsr_ip_to_string(&addrbuf, entry->avl.key), entry->array, olsr_clock_string(entry->valid_until));
259   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
260 #endif
261 }
262
263 /*
264  * Local Variables:
265  * c-basic-offset: 2
266  * indent-tabs-mode: nil
267  * End:
268  */