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