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