9d69cd7f7465c1a3f3a5ceb4e50ccf47ed541bd4
[oonf.git] / src / subsystems / oonf_duplicate_set.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon version 2 (olsrd2)
4  * Copyright (c) 2004-2015, 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 /**
43  * @file
44  */
45
46 #include <oonf/libcommon/avl.h>
47 #include <oonf/libcommon/avl_comp.h>
48 #include <oonf/oonf.h>
49 #include <oonf/libcommon/netaddr.h>
50 #include <oonf/libcore/oonf_subsystem.h>
51 #include <oonf/librfc5444/rfc5444.h>
52 #include <oonf/subsystems/oonf_class.h>
53 #include <oonf/subsystems/oonf_timer.h>
54
55 #include <oonf/subsystems/oonf_duplicate_set.h>
56
57 /* Definitions */
58 #define LOG_DUPLICATE_SET _oonf_duplicate_set_subsystem.logging
59
60 /* prototypes */
61 static int _init(void);
62 static void _cleanup(void);
63
64 static enum oonf_duplicate_result _test(
65   struct oonf_duplicate_set *, struct oonf_duplicate_entry *, uint64_t seqno, bool set);
66 static int _avl_cmp_dupkey(const void *, const void *);
67
68 static void _cb_vtime(struct oonf_timer_instance *);
69 static void _remove_duplicate_entry(struct oonf_duplicate_entry *entry);
70
71 static struct oonf_timer_class _vtime_info = {
72   .name = "Valdity time for duplicate set",
73   .callback = _cb_vtime,
74 };
75
76 static struct oonf_class _dupset_class = {
77   .name = "Duplicate set",
78   .size = sizeof(struct oonf_duplicate_entry),
79 };
80
81 /* dupset result names */
82 static const char *OONF_DUPSET_RESULT_STR[] = {
83   [OONF_DUPSET_TOO_OLD] = "too old",
84   [OONF_DUPSET_DUPLICATE] = "duplicate",
85   [OONF_DUPSET_CURRENT] = "current",
86   [OONF_DUPSET_NEW] = "new",
87   [OONF_DUPSET_NEWEST] = "newest",
88   [OONF_DUPSET_FIRST] = "first",
89 };
90
91 /* subsystem definition */
92 static const char *_dependencies[] = {
93   OONF_CLASS_SUBSYSTEM,
94   OONF_TIMER_SUBSYSTEM,
95 };
96
97 static struct oonf_subsystem _oonf_duplicate_set_subsystem = {
98   .name = OONF_DUPSET_SUBSYSTEM,
99   .dependencies = _dependencies,
100   .dependencies_count = ARRAYSIZE(_dependencies),
101   .init = _init,
102   .cleanup = _cleanup,
103 };
104 DECLARE_OONF_PLUGIN(_oonf_duplicate_set_subsystem);
105
106 /* math constants for different sizes */
107 static const int64_t _mask_values[] = {
108   [OONF_DUPSET_8BIT] = 255ull,
109   [OONF_DUPSET_16BIT] = 65535ull,
110   [OONF_DUPSET_32BIT] = 4294967295ull,
111 };
112
113 /**
114  * Initialize duplicate set subsystem
115  * @return always returns 0
116  */
117 static int
118 _init(void) {
119   oonf_class_add(&_dupset_class);
120   oonf_timer_add(&_vtime_info);
121   return 0;
122 }
123
124 /**
125  * Cleanup duplicate set subsystem
126  */
127 static void
128 _cleanup(void) {
129   oonf_timer_remove(&_vtime_info);
130   oonf_class_remove(&_dupset_class);
131 }
132
133 /**
134  * Initialize a new duplicate set
135  * @param set pointer to duplicate set
136  * @param type type of duplicate set
137  */
138 void
139 oonf_duplicate_set_add(struct oonf_duplicate_set *set, enum oonf_dupset_type type) {
140   memset(set, 0, sizeof(*set));
141   avl_init(&set->_tree, _avl_cmp_dupkey, false);
142
143   if (type != OONF_DUPSET_64BIT) {
144     set->_mask = _mask_values[type];
145     set->_offset = set->_mask + 1;
146     set->_limit = set->_mask / 2;
147   }
148 }
149
150 /**
151  * Remove all allocated resources from a duplicate set
152  * @param set pointer to duplicate set
153  */
154 void
155 oonf_duplicate_set_remove(struct oonf_duplicate_set *set) {
156   struct oonf_duplicate_entry *entry, *it;
157
158   avl_for_each_element_safe(&set->_tree, entry, _node, it) {
159     _remove_duplicate_entry(entry);
160   }
161 }
162
163 /**
164  * Test a originator/seqno pair against a duplicate set and add
165  * it to the set if necessary
166  * @param set duplicate set
167  * @param msg_type message type with incoming sequence number
168  * @param originator originator of sequence number
169  * @param seqno sequence number
170  * @param vtime validity time of sequence number
171  * @return OONF_DUPSET_TOO_OLD if sequence number is more than 32 behind
172  *   the current one, OONF_DUPSET_DUPLICATE if the number is in the set,
173  *   OONF_DUPSET_NEW if the number was added to the set and OONF_DUPSET_NEWEST
174  *   if the sequence number is newer than the newest in the set
175  */
176 enum oonf_duplicate_result
177 oonf_duplicate_entry_add(
178   struct oonf_duplicate_set *set, uint8_t msg_type, struct netaddr *originator, uint64_t seqno, uint64_t vtime)
179 {
180   struct oonf_duplicate_entry *entry;
181   struct oonf_duplicate_entry_key key;
182   enum oonf_duplicate_result result;
183
184 #ifdef OONF_LOG_DEBUG_INFO
185   struct netaddr_str nbuf;
186 #endif
187
188   /* generate combined key */
189   memcpy(&key.addr, originator, sizeof(*originator));
190   key.msg_type = msg_type;
191
192   entry = avl_find_element(&set->_tree, &key, entry, _node);
193   if (!entry) {
194     entry = oonf_class_malloc(&_dupset_class);
195     if (entry == NULL) {
196       return OONF_DUPSET_TOO_OLD;
197     }
198
199     /* initialize history and current sequence number */
200     entry->current = seqno;
201     entry->history = 1;
202
203     /* initialize backpointer */
204     entry->set = set;
205
206     /* initialize vtime */
207     entry->_vtime.class = &_vtime_info;
208
209     oonf_timer_start(&entry->_vtime, vtime);
210
211     /* set key and link entry to set */
212     memcpy(&entry->key, &key, sizeof(key));
213     entry->_node.key = &entry->key;
214     avl_insert(&set->_tree, &entry->_node);
215
216     result = OONF_DUPSET_FIRST;
217   }
218   else {
219     result = _test(set, entry, seqno, true);
220   }
221   OONF_DEBUG(LOG_DUPLICATE_SET, "Test/Add msgtype %u, originator %s, seqno %" PRIu64 ": %s", msg_type,
222     netaddr_to_string(&nbuf, originator), seqno, OONF_DUPSET_RESULT_STR[result]);
223
224   if (oonf_duplicate_is_new(result)) {
225     /* reset validity timer */
226     oonf_timer_set(&entry->_vtime, vtime);
227   }
228   return result;
229 }
230
231 /**
232  * Test a originator/sequence number pair against a duplicate set
233  * @param set duplicate set
234  * @param msg_type message type with incoming sequence number
235  * @param originator originator of sequence number
236  * @param seqno sequence number
237  * @return OONF_DUPSET_TOO_OLD if sequence number is more than 32 behind
238  *   the current one, OONF_DUPSET_DUPLICATE if the number is in the set,
239  *   OONF_DUPSET_NEW if the number was added to the set and OONF_DUPSET_NEWEST
240  *   if the sequence number is newer than the newest in the set
241  */
242 enum oonf_duplicate_result
243 oonf_duplicate_test(struct oonf_duplicate_set *set, uint8_t msg_type, struct netaddr *originator, uint64_t seqno)
244 {
245   struct oonf_duplicate_entry *entry;
246   struct oonf_duplicate_entry_key key;
247   enum oonf_duplicate_result result;
248
249 #ifdef OONF_LOG_DEBUG_INFO
250   struct netaddr_str nbuf;
251 #endif
252
253   /* generate combined key */
254   memcpy(&key.addr, originator, sizeof(*originator));
255   key.msg_type = msg_type;
256
257   entry = avl_find_element(&set->_tree, &key, entry, _node);
258   if (!entry) {
259     result = OONF_DUPSET_FIRST;
260   }
261   else {
262     result = _test(set, entry, seqno, false);
263   }
264
265   OONF_DEBUG(LOG_DUPLICATE_SET, "Test msgtype %u, originator %s, seqno %" PRIu64 ": %s", msg_type,
266     netaddr_to_string(&nbuf, originator), seqno, OONF_DUPSET_RESULT_STR[result]);
267
268   return result;
269 }
270
271 static int64_t
272 _seqno_difference(struct oonf_duplicate_set *set, uint64_t seqno1, uint64_t seqno2) {
273   uint64_t diff;
274   int64_t reldiff;
275
276   diff = seqno1 - seqno2;
277
278   reldiff = (int64_t)diff;
279   if (set->_mask) {
280     reldiff &= set->_mask;
281
282     if (reldiff > set->_limit) {
283       reldiff -= set->_offset;
284     }
285   }
286   return reldiff;
287 }
288 /**
289  * Test a sequence number against a duplicate set entry
290  * @param entry duplicate set entry
291  * @param seqno sequence number
292  * @param set true to add the sequence number to the entry, false
293  *   to leave the entry unchanged.
294  * @return OONF_DUPSET_TOO_OLD if sequence number is more than 32 behind
295  *   the current one, OONF_DUPSET_DUPLICATE if the number is in the set,
296  *   OONF_DUPSET_CURRENT if the number is exactly the current sequence number,
297  *   OONF_DUPSET_ if the number was added to the set and OONF_DUPSET_NEWEST
298  *   if the sequence number is newer than the newest in the set
299  */
300 enum oonf_duplicate_result
301 _test(struct oonf_duplicate_set *dupset, struct oonf_duplicate_entry *entry, uint64_t seqno, bool set)
302 {
303   int64_t diff;
304
305   if (seqno == entry->current) {
306     return OONF_DUPSET_CURRENT;
307   }
308
309   /* eliminate rollover */
310   diff = _seqno_difference(dupset, seqno, entry->current);
311   if (diff < -31) {
312     entry->too_old_count++;
313     if (entry->too_old_count > OONF_DUPSET_MAXIMUM_TOO_OLD) {
314       /*
315        * we got a long continuous series of too old messages,
316        * most likely the did reset and changed its sequence number
317        */
318       entry->history = 1;
319       entry->too_old_count = 0;
320       entry->current = seqno;
321
322       return OONF_DUPSET_NEWEST;
323     }
324     return OONF_DUPSET_TOO_OLD;
325   }
326
327   /* reset counter of too old messages */
328   entry->too_old_count = 0;
329
330   if (diff <= 0) {
331     uint32_t bitmask = 1 << ((uint32_t)(-diff));
332
333     if ((entry->history & bitmask) != 0) {
334       return OONF_DUPSET_DUPLICATE;
335     }
336
337     if (set) {
338       entry->history |= bitmask;
339     }
340     return OONF_DUPSET_NEW;
341   }
342
343   if (set) {
344     /* new sequence number is larger than last one */
345     entry->current = seqno;
346
347     if (diff >= 32) {
348       entry->history = 1;
349     }
350     else {
351       entry->history <<= diff;
352       entry->history |= 1;
353     }
354   }
355   return OONF_DUPSET_NEWEST;
356 }
357
358 /**
359  * Get text representation of duplicate check result
360  * @param result duplicate check result
361  * @return text representation
362  */
363 const char *
364 oonf_duplicate_get_result_str(enum oonf_duplicate_result result) {
365   return OONF_DUPSET_RESULT_STR[result];
366 }
367
368 /**
369  * Comparator for duplicate entry keys
370  * @param p1 key1
371  * @param p2 key2
372  * @return <0 if p1<p2, 0 if p1==p2, >0 if p1>p2
373  */
374 static int
375 _avl_cmp_dupkey(const void *p1, const void *p2) {
376   const struct oonf_duplicate_entry_key *k1, *k2;
377
378   k1 = p1;
379   k2 = p2;
380
381   if (k1->msg_type != k2->msg_type) {
382     return (int)(k1->msg_type) - (int)(k2->msg_type);
383   }
384
385   return avl_comp_netaddr(&k1->addr, &k2->addr);
386 }
387
388 /**
389  * Callback fired when duplicate entry times out
390  * @param ptr timer instance that fired
391  */
392 static void
393 _cb_vtime(struct oonf_timer_instance *ptr) {
394   struct oonf_duplicate_entry *entry;
395 #ifdef OONF_LOG_DEBUG_INFO
396   struct netaddr_str nbuf;
397 #endif
398
399   entry = container_of(ptr, struct oonf_duplicate_entry, _vtime);
400   OONF_DEBUG(LOG_DUPLICATE_SET, "Duplicate entry timed out: %s/%u", netaddr_to_string(&nbuf, &entry->key.addr),
401     entry->key.msg_type);
402
403   _remove_duplicate_entry(entry);
404 }
405
406 /**
407  * Remove a duplicate entry
408  * @param entry duplicate entry
409  */
410 static void
411 _remove_duplicate_entry(struct oonf_duplicate_entry *entry) {
412   oonf_timer_stop(&entry->_vtime);
413   avl_remove(&entry->set->_tree, &entry->_node);
414
415   oonf_class_free(&_dupset_class, entry);
416 }