Remove the olsr-specific duplicated types
[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 #include "olsr_cookie.h"
49
50 #include <stdlib.h>
51
52 static void olsr_cleanup_duplicate_entry(void *unused);
53
54 struct avl_tree duplicate_set;
55 struct timer_entry *duplicate_cleanup_timer;
56
57 /* Some cookies for stats keeping */
58 struct olsr_cookie_info *duplicate_timer_cookie = NULL;
59 struct olsr_cookie_info *duplicate_mem_cookie = NULL;
60
61 void
62 olsr_init_duplicate_set(void)
63 {
64   avl_init(&duplicate_set,
65            olsr_cnf->ip_version == AF_INET ? &avl_comp_ipv4 : &avl_comp_ipv6);
66
67   /*
68    * Get some cookies for getting stats to ease troubleshooting.
69    */
70   duplicate_timer_cookie =
71     olsr_alloc_cookie("Duplicate Set", OLSR_COOKIE_TYPE_TIMER);
72
73   duplicate_mem_cookie =
74     olsr_alloc_cookie("dup_entry", OLSR_COOKIE_TYPE_MEMORY);
75   olsr_cookie_set_memory_size(duplicate_mem_cookie, sizeof(struct dup_entry));
76
77
78   olsr_set_timer(&duplicate_cleanup_timer, DUPLICATE_CLEANUP_INTERVAL,
79                  DUPLICATE_CLEANUP_JITTER, OLSR_TIMER_PERIODIC,
80                  &olsr_cleanup_duplicate_entry, NULL,
81                  duplicate_timer_cookie->ci_id);
82 }
83
84 struct dup_entry *
85 olsr_create_duplicate_entry(union olsr_ip_addr *ip, uint16_t seqnr)
86 {
87   struct dup_entry *entry;
88   entry = olsr_cookie_malloc(duplicate_mem_cookie);
89   if (entry != NULL) {
90     memcpy(&entry->ip, ip,
91            olsr_cnf->ip_version ==
92            AF_INET ? sizeof(entry->ip.v4) : sizeof(entry->ip.v6));
93     entry->seqnr = seqnr;
94     entry->too_low_counter = 0;
95     entry->avl.key = &entry->ip;
96     entry->array = 0;
97   }
98   return entry;
99 }
100
101 static void
102 olsr_cleanup_duplicate_entry(void __attribute__ ((unused)) * unused)
103 {
104   struct dup_entry *entry;
105
106   OLSR_FOR_ALL_DUP_ENTRIES(entry) {
107     if (TIMED_OUT(entry->valid_until)) {
108       avl_delete(&duplicate_set, &entry->avl);
109       olsr_cookie_free(duplicate_mem_cookie, entry);
110     }
111   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
112 }
113
114 int
115 olsr_message_is_duplicate(union olsr_message *m)
116 {
117   struct dup_entry *entry;
118   int diff;
119   union olsr_ip_addr *mainIp;
120   clock_t valid_until;
121   struct ipaddr_str buf;
122   uint16_t seqnr;
123   union olsr_ip_addr *ip;
124
125   if (olsr_cnf->ip_version == AF_INET) {
126     seqnr = ntohs(m->v4.seqno);
127     ip = (union olsr_ip_addr *)&m->v4.originator;
128   } else {
129     seqnr = ntohs(m->v6.seqno);
130     ip = (union olsr_ip_addr *)&m->v6.originator;
131   }
132
133   // get main address
134   mainIp = olsr_lookup_main_addr_by_alias(ip);
135   if (mainIp == NULL) {
136     mainIp = ip;
137   }
138
139   valid_until = GET_TIMESTAMP(DUPLICATE_VTIME);
140
141   entry = (struct dup_entry *)avl_find(&duplicate_set, ip);
142   if (entry == NULL) {
143     entry = olsr_create_duplicate_entry(ip, seqnr);
144     if (entry != NULL) {
145       avl_insert(&duplicate_set, &entry->avl, 0);
146       entry->valid_until = valid_until;
147     }
148     return false;                       // okay, we process this package
149   }
150
151   diff = (int)seqnr - (int)(entry->seqnr);
152
153   // update timestamp
154   if (valid_until > entry->valid_until) {
155     entry->valid_until = valid_until;
156   }
157   // overflow ?
158   if (diff > (1 << 15)) {
159     diff -= (1 << 16);
160   }
161
162   if (diff < -31) {
163     entry->too_low_counter++;
164
165     // client did restart with a lower number ?
166     if (entry->too_low_counter > 16) {
167       entry->too_low_counter = 0;
168       entry->seqnr = seqnr;
169       entry->array = 1;
170       return false; /* start with a new sequence number, so NO duplicate */
171     }
172     OLSR_PRINTF(9, "blocked %x from %s\n", seqnr,
173                 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 = 1 << ((uint32_t) (-diff));
180
181     if ((entry->array & bitmask) != 0) {
182       OLSR_PRINTF(9, "blocked %x (diff=%d,mask=%08x) from %s\n", seqnr, diff,
183           entry->array, olsr_ip_to_string(&buf, mainIp));
184       return true; /* duplicate ! */
185     }
186     entry->array |= bitmask;
187     OLSR_PRINTF(9, "processed %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
188     return false; /* no duplicate */
189   } else if (diff < 32) {
190     entry->array <<= (uint32_t) diff;
191   } else {
192     entry->array = 0;
193   }
194   entry->array |= 1;
195   entry->seqnr = seqnr;
196   OLSR_PRINTF(9, "processed %x from %s\n", seqnr,
197               olsr_ip_to_string(&buf, mainIp));
198   return false; /* no duplicate */
199 }
200
201 void
202 olsr_print_duplicate_table(void)
203 {
204 #ifndef NODEBUG
205   /* The whole function makes no sense without it. */
206   struct dup_entry *entry;
207   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
208   struct ipaddr_str addrbuf;
209
210   OLSR_PRINTF(1,
211               "\n--- %s ------------------------------------------------- DUPLICATE SET\n\n"
212               "%-*s %8s %s\n", olsr_wallclock_string(), ipwidth,
213               "Node IP", "DupArray", "VTime");
214
215   OLSR_FOR_ALL_DUP_ENTRIES(entry) {
216     OLSR_PRINTF(1, "%-*s %08x %s\n",
217                 ipwidth, olsr_ip_to_string(&addrbuf,
218                                            (union olsr_ip_addr *)(entry->avl.
219                                                                   key)),
220                 entry->array, olsr_clock_string(entry->valid_until));
221   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
222 #endif
223 }
224
225 /*
226  * Local Variables:
227  * c-basic-offset: 2
228  * indent-tabs-mode: nil
229  * End:
230  */