new lq-plugin (etx_ff)
[olsrd.git] / src / duplicate_set.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2008 Henning Rogge <rogge@fgan.de>
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright
13  *   notice, this list of conditions and the following disclaimer in
14  *   the documentation and/or other materials provided with the
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its
17  *   contributors may be used to endorse or promote products derived
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  */
40
41 #include "duplicate_set.h"
42 #include "ipcalc.h"
43 #include "common/avl.h"
44 #include "olsr.h"
45 #include "mid_set.h"
46 #include "scheduler.h"
47 #include "mantissa.h"
48
49 static void olsr_cleanup_duplicate_entry(void *unused);
50
51 struct avl_tree duplicate_set;
52 struct timer_entry *duplicate_cleanup_timer;
53
54
55 void olsr_init_duplicate_set(void) {
56   avl_init(&duplicate_set, olsr_cnf->ip_version == AF_INET ? &avl_comp_ipv4 : &avl_comp_ipv6);
57
58   olsr_set_timer(&duplicate_cleanup_timer, DUPLICATE_CLEANUP_INTERVAL,
59      DUPLICATE_CLEANUP_JITTER, OLSR_TIMER_PERIODIC,
60      &olsr_cleanup_duplicate_entry, NULL, 0);
61 }
62
63 struct dup_entry *olsr_create_duplicate_entry(void *ip, olsr_u16_t seqnr) {
64   struct dup_entry *entry;
65   entry = olsr_malloc(sizeof(struct dup_entry), "New duplicate entry");
66   if (entry != NULL) {
67     memcpy (&entry->ip, ip, olsr_cnf->ip_version == AF_INET ? sizeof(entry->ip.v4) : sizeof(entry->ip.v6));
68     entry->seqnr = seqnr;
69     entry->too_low_counter = 0;
70     entry->avl.key = &entry->ip;
71   }
72   return entry;
73 }
74
75 static void olsr_cleanup_duplicate_entry(void __attribute__ ((unused)) *unused) {
76   struct dup_entry *entry;
77
78   OLSR_FOR_ALL_DUP_ENTRIES(entry) {
79     if (TIMED_OUT(entry->valid_until)) {
80       avl_delete(&duplicate_set, &entry->avl);
81       free (entry);
82     }
83   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
84 }
85
86 int olsr_shall_process_message(void *ip, olsr_u16_t seqnr) {
87   struct dup_entry *entry;
88   int diff;
89   void *mainIp;
90   clock_t valid_until;
91
92 #ifndef NODEBUG
93   struct ipaddr_str buf;
94 #endif
95   // get main address
96   mainIp = mid_lookup_main_addr(ip);
97   if (mainIp == NULL) {
98     mainIp = ip;
99   }
100
101   valid_until = GET_TIMESTAMP(DUPLICATE_VTIME);
102
103   entry = (struct dup_entry *)avl_find(&duplicate_set, ip);
104   if (entry == NULL) {
105     entry = olsr_create_duplicate_entry(ip, seqnr);
106     if (entry != NULL) {
107       avl_insert(&duplicate_set, &entry->avl, 0);
108       entry->valid_until = valid_until;
109     }
110     return 1; // okay, we process this package
111   }
112
113   diff = (int)seqnr - (int)(entry->seqnr);
114
115   // update timestamp
116   if (valid_until > entry->valid_until) {
117     entry->valid_until = valid_until;
118   }
119
120   // overflow ?
121   if (diff > (1<<15)) {
122     diff -= (1<<16);
123   }
124
125   if (diff < -31) {
126     entry->too_low_counter ++;
127
128     // client did restart with a lower number ?
129     if (entry->too_low_counter > 16) {
130       entry->too_low_counter = 0;
131       entry->seqnr = seqnr;
132       entry->array = 1;
133       return 1;
134     }
135     OLSR_PRINTF(9, "blocked %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
136     return 0;
137   }
138
139   entry->too_low_counter = 0;
140   if (diff <= 0) {
141     olsr_u32_t bitmask = 1 << ((olsr_u32_t) (-diff));
142
143     if ((entry->array & bitmask) != 0) {
144       OLSR_PRINTF(9, "blocked %x (diff=%d,mask=%08x) from %s\n", seqnr, diff, entry->array, olsr_ip_to_string(&buf, mainIp));
145       return 0;
146     }
147     entry->array |= bitmask;
148     OLSR_PRINTF(9, "processed %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
149     return 1;
150   }
151   else if (diff < 32) {
152     entry->array <<= (olsr_u32_t)diff;
153   }
154   else {
155     entry->array = 0;
156   }
157   entry->array |= 1;
158   entry->seqnr = seqnr;
159   OLSR_PRINTF(9, "processed %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
160   return 1;
161 }
162
163 void olsr_print_duplicate_table(void) {
164 #ifndef NODEBUG
165   /* The whole function makes no sense without it. */
166   struct dup_entry *entry;
167   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
168   struct ipaddr_str addrbuf;
169
170   OLSR_PRINTF(1,
171         "\n--- %s ------------------------------------------------- DUPLICATE SET\n\n"
172         "%-*s %8s %s\n", olsr_wallclock_string(), ipwidth,
173         "Node IP", "DupArray", "VTime");
174
175   OLSR_FOR_ALL_DUP_ENTRIES(entry) {
176     OLSR_PRINTF(1, "%-*s %08x %s\n",
177         ipwidth, olsr_ip_to_string(&addrbuf, (union olsr_ip_addr *)(entry->avl.key)),
178         entry->array,
179         olsr_clock_string(entry->valid_until));
180   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
181 #endif
182 }