Namespace cleanup of scheduler, remove "polling" sockets
[olsrd.git] / lib / bmf / src / PacketHistory.c
1
2 /*
3  * OLSR Basic Multicast Forwarding (BMF) plugin.
4  * Copyright (c) 2005 - 2007, Thales Communications, Huizen, The Netherlands.
5  * Written by Erik Tromp.
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * * Redistributions of source code must retain the above copyright
13  *   notice, this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above copyright
15  *   notice, this list of conditions and the following disclaimer in
16  *   the documentation and/or other materials provided with the
17  *   distribution.
18  * * Neither the name of Thales, BMF nor the names of its
19  *   contributors may be used to endorse or promote products derived
20  *   from this software without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
24  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
25  * IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
26  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
29  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
30  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
31  * OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33
34 /* -------------------------------------------------------------------------
35  * File       : PacketHistory.c
36  * Description: Functions for keeping and accessing the history of processed
37  *              multicast IP packets.
38  * Created    : 29 Jun 2006
39  *
40  * ------------------------------------------------------------------------- */
41
42 #include "PacketHistory.h"
43
44 /* System includes */
45 #include <stddef.h>             /* NULL */
46 #include <assert.h>             /* assert() */
47 #include <string.h>             /* memset */
48 #include <sys/types.h>          /* u_int16_t, u_int32_t */
49 #include <netinet/ip.h>         /* struct iphdr */
50 #include <stdlib.h>             /* atoi, malloc */
51
52 /* OLSRD includes */
53 #include "defs.h"               /* GET_TIMESTAMP, TIMED_OUT */
54 #include "olsr.h"
55 #include "scheduler.h"          /* now_times */
56
57 /* Plugin includes */
58 #include "Packet.h"
59
60 static struct TDupEntry *PacketHistory[HISTORY_HASH_SIZE];
61
62 #define CRC_UPTO_NBYTES 256
63
64 #if 0
65
66 /* -------------------------------------------------------------------------
67  * Function   : CalcCrcCcitt
68  * Description: Calculate 16-bits CRC according to CRC-CCITT specification
69  * Input      : buffer - the bytes to calculate the CRC value over
70  *              len - the number of bytes to calculate the CRC value over
71  * Output     : none
72  * Return     : CRC-16 value
73  * Data Used  : none
74  * ------------------------------------------------------------------------- */
75 static u_int16_t
76 CalcCrcCcitt(unsigned char *buffer, ssize_t len)
77 {
78   /* Initial value of 0xFFFF should be 0x1D0F according to
79    * www.joegeluso.com/software/articles/ccitt.htm */
80   u_int16_t crc = 0xFFFF;
81   int i;
82
83   assert(buffer != NULL);
84
85   for (i = 0; i < len; i++) {
86     crc = (unsigned char)(crc >> 8) | (crc << 8);
87     crc ^= buffer[i];
88     crc ^= (unsigned char)(crc & 0xff) >> 4;
89     crc ^= (crc << 8) << 4;
90     crc ^= ((crc & 0xff) << 4) << 1;
91   }
92   return crc;
93 }                               /* CalcCrcCcitt */
94 #endif
95
96 /* -------------------------------------------------------------------------
97  * Function   : GenerateCrc32Table
98  * Description: Generate the table of CRC remainders for all possible bytes,
99  *              according to CRC-32-IEEE 802.3
100  * Input      : none
101  * Output     : none
102  * Return     : none
103  * Data Used  : none
104  * ------------------------------------------------------------------------- */
105 #define CRC32_POLYNOMIAL 0xedb88320UL   /* bit-inverse of 0x04c11db7UL */
106
107 static unsigned long CrcTable[256];
108
109 static void
110 GenerateCrc32Table(void)
111 {
112   int i, j;
113   u_int32_t crc;
114   for (i = 0; i < 256; i++) {
115     crc = (u_int32_t) i;
116     for (j = 0; j < 8; j++) {
117       if (crc & 1) {
118         crc = (crc >> 1) ^ CRC32_POLYNOMIAL;
119       } else {
120         crc = (crc >> 1);
121       }
122     }
123     CrcTable[i] = crc;
124   }                             /* for */
125 }                               /* GenerateCrc32Table */
126
127 /* -------------------------------------------------------------------------
128  * Function   : CalcCrc32
129  * Description: Calculate CRC-32 according to CRC-32-IEEE 802.3
130  * Input      : buffer - the bytes to calculate the CRC value over
131  *              len - the number of bytes to calculate the CRC value over
132  * Output     : none
133  * Return     : CRC-32 value
134  * Data Used  : none
135  * ------------------------------------------------------------------------- */
136 static u_int32_t
137 CalcCrc32(unsigned char *buffer, ssize_t len)
138 {
139   int i, j;
140   u_int32_t crc = 0xffffffffUL;
141   for (i = 0; i < len; i++) {
142     j = ((int)(crc & 0xFF) ^ *buffer++);
143     crc = (crc >> 8) ^ CrcTable[j];
144   }
145   return crc ^ 0xffffffffUL;
146 }                               /* CalcCrc32 */
147
148 /* -------------------------------------------------------------------------
149  * Function   : PacketCrc32
150  * Description: Calculates the CRC-32 value for an IP packet
151  * Input      : ipPacket - the IP packet
152  *              len - the number of octets in the IP packet
153  * Output     : none
154  * Return     : 32-bits CRC value
155  * Data Used  : none
156  * ------------------------------------------------------------------------- */
157 u_int32_t
158 PacketCrc32(unsigned char *ipPacket, ssize_t len)
159 {
160   struct TSaveTtl sttl;
161   struct ip *ipHeader;
162   u_int32_t result;
163
164   assert(ipPacket != NULL);
165
166   /* Skip TTL: in a multi-homed OLSR-network, the same multicast packet
167    * may enter the network multiple times, each copy differing only in its
168    * TTL value. BMF must not calculate a different CRC for packets that
169    * differ only in TTL. Skip also the IP-header checksum, because it changes
170    * along with TTL. Besides, it is not a good idea to calculate a CRC over
171    * data that already contains a checksum.
172    *
173    * Clip number of bytes over which CRC is calculated to prevent
174    * long packets from possibly claiming too much CPU resources. */
175   assert(len > 0);
176   if (len > CRC_UPTO_NBYTES) {
177     len = CRC_UPTO_NBYTES;
178   }
179
180   SaveTtlAndChecksum(ipPacket, &sttl);
181
182   ipHeader = (struct ip *)(ARM_NOWARN_ALIGN(ipPacket));
183   ipHeader->ip_ttl = 0xFF;      /* fixed value of TTL for CRC-32 calculation */
184   ipHeader->ip_sum = 0x5A5A;    /* fixed value of IP header checksum for CRC-32 calculation */
185
186   result = CalcCrc32(ipPacket, len);
187
188   RestoreTtlAndChecksum(ipPacket, &sttl);
189   return result;
190 }                               /* PacketCrc32 */
191
192 /* -------------------------------------------------------------------------
193  * Function   : Hash
194  * Description: Calculates a hash value from a 32-bit value
195  * Input      : from32 - 32-bit value
196  * Output     : none
197  * Return     : hash value
198  * Data Used  : none
199  * ------------------------------------------------------------------------- */
200 u_int32_t
201 Hash(u_int32_t from32)
202 {
203   return ((from32 >> N_HASH_BITS) + from32) & ((1 << N_HASH_BITS) - 1);
204 }                               /* Hash */
205
206 /* -------------------------------------------------------------------------
207  * Function   : InitPacketHistory
208  * Description: Initialize the packet history table and CRC-32 table
209  * Input      : none
210  * Output     : none
211  * Return     : none
212  * Data Used  : PacketHistory
213  * ------------------------------------------------------------------------- */
214 void
215 InitPacketHistory(void)
216 {
217   int i;
218
219   GenerateCrc32Table();
220
221   for (i = 0; i < HISTORY_HASH_SIZE; i++) {
222     PacketHistory[i] = NULL;
223   }
224 }                               /* InitPacketHistory */
225
226 /* -------------------------------------------------------------------------
227  * Function   : CheckAndMarkRecentPacket
228  * Description: Check if this packet was seen recently, then record the fact
229  *              that this packet was seen recently.
230  * Input      : crc32 - 32-bits crc value of the packet
231  * Output     : none
232  * Return     : not recently seen (0), recently seen (1)
233  * Data Used  : PacketHistory
234  * ------------------------------------------------------------------------- */
235 int
236 CheckAndMarkRecentPacket(u_int32_t crc32)
237 {
238   u_int32_t idx;
239   struct TDupEntry *walker;
240   struct TDupEntry *newEntry;
241
242   idx = Hash(crc32);
243   assert(idx < HISTORY_HASH_SIZE);
244
245   for (walker = PacketHistory[idx]; walker != NULL; walker = walker->next) {
246     if (walker->crc32 == crc32) {
247       /* Found duplicate entry */
248
249       /* Always mark as "seen recently": refresh time-out */
250       walker->timeOut = olsr_timer_getAbsolute(HISTORY_HOLD_TIME);
251
252       return 1;
253     }                           /* if */
254   }                             /* for */
255
256   /* No duplicate entry found: create one */
257   newEntry = malloc(sizeof(struct TDupEntry));
258   if (newEntry != NULL) {
259     newEntry->crc32 = crc32;
260     newEntry->timeOut = olsr_timer_getAbsolute(HISTORY_HOLD_TIME);
261
262     /* Add new entry at the front of the list */
263     newEntry->next = PacketHistory[idx];
264     PacketHistory[idx] = newEntry;
265   }
266
267   return 0;
268 }                               /* CheckAndMarkRecentPacket */
269
270 /* -------------------------------------------------------------------------
271  * Function   : PrunePacketHistory
272  * Description: Prune the packet history table.
273  * Input      : useless - not used
274  * Output     : none
275  * Return     : none
276  * Data Used  : PacketHistory
277  * ------------------------------------------------------------------------- */
278 void
279 PrunePacketHistory(void *useless __attribute__ ((unused)))
280 {
281   uint i;
282   for (i = 0; i < HISTORY_HASH_SIZE; i++) {
283     if (PacketHistory[i] != NULL) {
284       struct TDupEntry *nextEntry = PacketHistory[i];
285       struct TDupEntry *prevEntry = NULL;
286       while (nextEntry != NULL) {
287         struct TDupEntry *entry = nextEntry;
288         nextEntry = entry->next;
289
290         if (olsr_timer_isTimedOut(entry->timeOut)) {
291           /* De-queue */
292           if (prevEntry != NULL) {
293             prevEntry->next = entry->next;
294           } else {
295             PacketHistory[i] = entry->next;
296           }                     /* if */
297
298           /* De-allocate memory */
299           free(entry);
300         } else {
301           prevEntry = entry;
302         }                       /* if */
303       }                         /* while */
304     }                           /* if (PacketHistory[i] != NULL) */
305   }                             /* for (i = ...) */
306 }                               /* PrunePacketHistory */
307
308 /*
309  * Local Variables:
310  * c-basic-offset: 2
311  * indent-tabs-mode: nil
312  * End:
313  */