gateway: introduce and use removeGatewayFromList function
[olsrd.git] / src / duplicate_set.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2008 Henning Rogge <rogge@fgan.de>
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 "mantissa.h"
49
50 static void olsr_cleanup_duplicate_entry(void *unused);
51
52 struct avl_tree duplicate_set;
53 struct timer_entry *duplicate_cleanup_timer;
54
55 void
56 olsr_init_duplicate_set(void)
57 {
58   avl_init(&duplicate_set, olsr_cnf->ip_version == AF_INET ? &avl_comp_ipv4 : &avl_comp_ipv6);
59
60   olsr_set_timer(&duplicate_cleanup_timer, DUPLICATE_CLEANUP_INTERVAL, DUPLICATE_CLEANUP_JITTER, OLSR_TIMER_PERIODIC,
61                  &olsr_cleanup_duplicate_entry, NULL, 0);
62 }
63
64 void olsr_cleanup_duplicates(union olsr_ip_addr *orig) {
65   struct dup_entry *entry;
66
67   entry = (struct dup_entry *)avl_find(&duplicate_set, orig);
68   if (entry != NULL) {
69     entry->too_low_counter = DUP_MAX_TOO_LOW - 2;
70   }
71 }
72
73 struct dup_entry *
74 olsr_create_duplicate_entry(void *ip, uint16_t seqnr)
75 {
76   struct dup_entry *entry;
77   entry = olsr_malloc(sizeof(struct dup_entry), "New duplicate entry");
78   if (entry != NULL) {
79     memcpy(&entry->ip, ip, olsr_cnf->ip_version == AF_INET ? sizeof(entry->ip.v4) : sizeof(entry->ip.v6));
80     entry->seqnr = seqnr;
81     entry->too_low_counter = 0;
82     entry->avl.key = &entry->ip;
83     entry->array = 0;
84   }
85   return entry;
86 }
87
88 static void
89 olsr_cleanup_duplicate_entry(void __attribute__ ((unused)) * unused)
90 {
91   struct dup_entry *entry;
92
93   OLSR_FOR_ALL_DUP_ENTRIES(entry) {
94     if (TIMED_OUT(entry->valid_until)) {
95       avl_delete(&duplicate_set, &entry->avl);
96       free(entry);
97     }
98   }
99   OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
100 }
101
102 int olsr_seqno_diff(uint16_t seqno1, uint16_t seqno2) {
103   int diff = (int)seqno1 - (int)(seqno2);
104
105   // overflow ?
106   if (diff > (1 << 15)) {
107     diff -= (1 << 16);
108   }
109   else if (diff < -(1 << 15)) {
110       diff += (1 << 16);
111   }
112   return diff;
113 }
114
115 int
116 olsr_message_is_duplicate(union olsr_message *m)
117 {
118   struct dup_entry *entry;
119   int diff;
120   void *mainIp;
121   uint32_t valid_until;
122   struct ipaddr_str buf;
123   uint16_t seqnr;
124   void *ip;
125
126   if (olsr_cnf->ip_version == AF_INET) {
127     seqnr = ntohs(m->v4.seqno);
128     ip = &m->v4.originator;
129   } else {
130     seqnr = ntohs(m->v6.seqno);
131     ip = &m->v6.originator;
132   }
133
134   // get main address
135   mainIp = mid_lookup_main_addr(ip);
136   if (mainIp == NULL) {
137     mainIp = ip;
138   }
139
140   valid_until = GET_TIMESTAMP(DUPLICATE_VTIME);
141
142   entry = (struct dup_entry *)avl_find(&duplicate_set, ip);
143   if (entry == NULL) {
144     entry = olsr_create_duplicate_entry(ip, seqnr);
145     if (entry != NULL) {
146       avl_insert(&duplicate_set, &entry->avl, 0);
147       entry->valid_until = valid_until;
148     }
149     return false;               // okay, we process this package
150   }
151
152
153   // update timestamp
154   if (valid_until > entry->valid_until) {
155     entry->valid_until = valid_until;
156   }
157
158   diff = olsr_seqno_diff(seqnr, entry->seqnr);
159   if (diff < -31) {
160     entry->too_low_counter++;
161
162     // client did restart with a lower number ?
163     if (entry->too_low_counter > DUP_MAX_TOO_LOW) {
164       entry->too_low_counter = 0;
165       entry->seqnr = seqnr;
166       entry->array = 1;
167       return false;             /* start with a new sequence number, so NO duplicate */
168     }
169     OLSR_PRINTF(9, "blocked 0x%x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
170     return true;                /* duplicate ! */
171   }
172
173   entry->too_low_counter = 0;
174   if (diff <= 0) {
175     uint32_t bitmask = 1 << ((uint32_t) (-diff));
176
177     if ((entry->array & bitmask) != 0) {
178       OLSR_PRINTF(9, "blocked 0x%x (diff=%d,mask=%08x) from %s\n", seqnr, diff, entry->array, olsr_ip_to_string(&buf, mainIp));
179       return true;              /* duplicate ! */
180     }
181     entry->array |= bitmask;
182     OLSR_PRINTF(9, "processed 0x%x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
183     return false;               /* no duplicate */
184   } else if (diff < 32) {
185     entry->array <<= (uint32_t) diff;
186   } else {
187     entry->array = 0;
188   }
189   entry->array |= 1;
190   entry->seqnr = seqnr;
191   OLSR_PRINTF(9, "processed 0x%x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
192   return false;                 /* no duplicate */
193 }
194
195 #ifndef NODEBUG
196 void
197 olsr_print_duplicate_table(void)
198 {
199   /* The whole function makes no sense without it. */
200   struct dup_entry *entry;
201   const int ipwidth = olsr_cnf->ip_version == AF_INET ? (INET_ADDRSTRLEN - 1) : (INET6_ADDRSTRLEN - 1);
202   struct ipaddr_str addrbuf;
203
204   OLSR_PRINTF(1, "\n--- %s ------------------------------------------------- DUPLICATE SET\n\n" "%-*s %8s %s\n",
205               olsr_wallclock_string(), ipwidth, "Node IP", "DupArray", "VTime");
206
207   OLSR_FOR_ALL_DUP_ENTRIES(entry) {
208     OLSR_PRINTF(1, "%-*s %08x %s\n", ipwidth, olsr_ip_to_string(&addrbuf, (union olsr_ip_addr *)(entry->avl.key)),
209                 entry->array, olsr_clock_string(entry->valid_until));
210   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
211 }
212 #endif /* NODEBUG */
213
214 /*
215  * Local Variables:
216  * c-basic-offset: 2
217  * indent-tabs-mode: nil
218  * End:
219  */