856ce51747a080d8f9bf51d90bb346cacd486e2a
[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
51 /* OLSRD includes */
52 #include "defs.h"               /* GET_TIMESTAMP, TIMED_OUT */
53 #include "olsr.h"               /* olsr_printf */
54
55 /* Plugin includes */
56 #include "Packet.h"
57
58 static struct TDupEntry *PacketHistory[HISTORY_HASH_SIZE];
59
60 #define CRC_UPTO_NBYTES 256
61
62 #if 0
63
64 /* -------------------------------------------------------------------------
65  * Function   : CalcCrcCcitt
66  * Description: Calculate 16-bits CRC according to CRC-CCITT specification
67  * Input      : buffer - the bytes to calculate the CRC value over
68  *              len - the number of bytes to calculate the CRC value over
69  * Output     : none
70  * Return     : CRC-16 value
71  * Data Used  : none
72  * ------------------------------------------------------------------------- */
73 static u_int16_t
74 CalcCrcCcitt(unsigned char *buffer, ssize_t len)
75 {
76   /* Initial value of 0xFFFF should be 0x1D0F according to
77    * www.joegeluso.com/software/articles/ccitt.htm */
78   u_int16_t crc = 0xFFFF;
79   int i;
80
81   assert(buffer != NULL);
82
83   for (i = 0; i < len; i++) {
84     crc = (unsigned char)(crc >> 8) | (crc << 8);
85     crc ^= buffer[i];
86     crc ^= (unsigned char)(crc & 0xff) >> 4;
87     crc ^= (crc << 8) << 4;
88     crc ^= ((crc & 0xff) << 4) << 1;
89   }
90   return crc;
91 }                               /* CalcCrcCcitt */
92 #endif
93
94 /* -------------------------------------------------------------------------
95  * Function   : GenerateCrc32Table
96  * Description: Generate the table of CRC remainders for all possible bytes,
97  *              according to CRC-32-IEEE 802.3
98  * Input      : none
99  * Output     : none
100  * Return     : none
101  * Data Used  : none
102  * ------------------------------------------------------------------------- */
103 #define CRC32_POLYNOMIAL 0xedb88320UL   /* bit-inverse of 0x04c11db7UL */
104
105 static unsigned long CrcTable[256];
106
107 static void
108 GenerateCrc32Table(void)
109 {
110   int i, j;
111   u_int32_t crc;
112   for (i = 0; i < 256; i++) {
113     crc = (u_int32_t) i;
114     for (j = 0; j < 8; j++) {
115       if (crc & 1) {
116         crc = (crc >> 1) ^ CRC32_POLYNOMIAL;
117       } else {
118         crc = (crc >> 1);
119       }
120     }
121     CrcTable[i] = crc;
122   }                             /* for */
123 }                               /* GenerateCrc32Table */
124
125 /* -------------------------------------------------------------------------
126  * Function   : CalcCrc32
127  * Description: Calculate CRC-32 according to CRC-32-IEEE 802.3
128  * Input      : buffer - the bytes to calculate the CRC value over
129  *              len - the number of bytes to calculate the CRC value over
130  * Output     : none
131  * Return     : CRC-32 value
132  * Data Used  : none
133  * ------------------------------------------------------------------------- */
134 static u_int32_t
135 CalcCrc32(unsigned char *buffer, ssize_t len)
136 {
137   int i, j;
138   u_int32_t crc = 0xffffffffUL;
139   for (i = 0; i < len; i++) {
140     j = ((int)(crc & 0xFF) ^ *buffer++);
141     crc = (crc >> 8) ^ CrcTable[j];
142   }
143   return crc ^ 0xffffffffUL;
144 }                               /* CalcCrc32 */
145
146 /* -------------------------------------------------------------------------
147  * Function   : PacketCrc32
148  * Description: Calculates the CRC-32 value for an IP packet
149  * Input      : ipPacket - the IP packet
150  *              len - the number of octets in the IP packet
151  * Output     : none
152  * Return     : 32-bits CRC value
153  * Data Used  : none
154  * ------------------------------------------------------------------------- */
155 u_int32_t
156 PacketCrc32(unsigned char *ipPacket, ssize_t len)
157 {
158   struct TSaveTtl sttl;
159   struct ip *ipHeader;
160   u_int32_t result;
161
162   assert(ipPacket != NULL);
163
164   /* Skip TTL: in a multi-homed OLSR-network, the same multicast packet
165    * may enter the network multiple times, each copy differing only in its
166    * TTL value. BMF must not calculate a different CRC for packets that
167    * differ only in TTL. Skip also the IP-header checksum, because it changes
168    * along with TTL. Besides, it is not a good idea to calculate a CRC over
169    * data that already contains a checksum.
170    *
171    * Clip number of bytes over which CRC is calculated to prevent
172    * long packets from possibly claiming too much CPU resources. */
173   assert(len > 0);
174   if (len > CRC_UPTO_NBYTES) {
175     len = CRC_UPTO_NBYTES;
176   }
177
178   SaveTtlAndChecksum(ipPacket, &sttl);
179
180   ipHeader = (struct ip *)(ARM_NOWARN_ALIGN)ipPacket;
181   ipHeader->ip_ttl = 0xFF;      /* fixed value of TTL for CRC-32 calculation */
182   ipHeader->ip_sum = 0x5A5A;    /* fixed value of IP header checksum for CRC-32 calculation */
183
184   result = CalcCrc32(ipPacket, len);
185
186   RestoreTtlAndChecksum(ipPacket, &sttl);
187   return result;
188 }                               /* PacketCrc32 */
189
190 /* -------------------------------------------------------------------------
191  * Function   : Hash
192  * Description: Calculates a hash value from a 32-bit value
193  * Input      : from32 - 32-bit value
194  * Output     : none
195  * Return     : hash value
196  * Data Used  : none
197  * ------------------------------------------------------------------------- */
198 u_int32_t
199 Hash(u_int32_t from32)
200 {
201   return ((from32 >> N_HASH_BITS) + from32) & ((1 << N_HASH_BITS) - 1);
202 }                               /* Hash */
203
204 /* -------------------------------------------------------------------------
205  * Function   : InitPacketHistory
206  * Description: Initialize the packet history table and CRC-32 table
207  * Input      : none
208  * Output     : none
209  * Return     : none
210  * Data Used  : PacketHistory
211  * ------------------------------------------------------------------------- */
212 void
213 InitPacketHistory(void)
214 {
215   int i;
216
217   GenerateCrc32Table();
218
219   for (i = 0; i < HISTORY_HASH_SIZE; i++) {
220     PacketHistory[i] = NULL;
221   }
222 }                               /* InitPacketHistory */
223
224 /* -------------------------------------------------------------------------
225  * Function   : CheckAndMarkRecentPacket
226  * Description: Check if this packet was seen recently, then record the fact
227  *              that this packet was seen recently.
228  * Input      : crc32 - 32-bits crc value of the packet
229  * Output     : none
230  * Return     : not recently seen (0), recently seen (1)
231  * Data Used  : PacketHistory
232  * ------------------------------------------------------------------------- */
233 int
234 CheckAndMarkRecentPacket(u_int32_t crc32)
235 {
236   u_int32_t idx;
237   struct TDupEntry *walker;
238   struct TDupEntry *newEntry;
239
240   idx = Hash(crc32);
241   assert(idx < HISTORY_HASH_SIZE);
242
243   for (walker = PacketHistory[idx]; walker != NULL; walker = walker->next) {
244     if (walker->crc32 == crc32) {
245       /* Found duplicate entry */
246
247       /* Always mark as "seen recently": refresh time-out */
248       walker->timeOut = GET_TIMESTAMP(HISTORY_HOLD_TIME);
249
250       return 1;
251     }                           /* if */
252   }                             /* for */
253
254   /* No duplicate entry found: create one */
255   newEntry = malloc(sizeof(struct TDupEntry));
256   if (newEntry != NULL) {
257     newEntry->crc32 = crc32;
258     newEntry->timeOut = GET_TIMESTAMP(HISTORY_HOLD_TIME);
259
260     /* Add new entry at the front of the list */
261     newEntry->next = PacketHistory[idx];
262     PacketHistory[idx] = newEntry;
263   }
264
265   return 0;
266 }                               /* CheckAndMarkRecentPacket */
267
268 /* -------------------------------------------------------------------------
269  * Function   : PrunePacketHistory
270  * Description: Prune the packet history table.
271  * Input      : useless - not used
272  * Output     : none
273  * Return     : none
274  * Data Used  : PacketHistory
275  * ------------------------------------------------------------------------- */
276 void
277 PrunePacketHistory(void *useless __attribute__ ((unused)))
278 {
279   uint i;
280   for (i = 0; i < HISTORY_HASH_SIZE; i++) {
281     if (PacketHistory[i] != NULL) {
282       struct TDupEntry *nextEntry = PacketHistory[i];
283       struct TDupEntry *prevEntry = NULL;
284       while (nextEntry != NULL) {
285         struct TDupEntry *entry = nextEntry;
286         nextEntry = entry->next;
287
288         if (TIMED_OUT(entry->timeOut)) {
289           /* De-queue */
290           if (prevEntry != NULL) {
291             prevEntry->next = entry->next;
292           } else {
293             PacketHistory[i] = entry->next;
294           }                     /* if */
295
296           /* De-allocate memory */
297           free(entry);
298         } else {
299           prevEntry = entry;
300         }                       /* if */
301       }                         /* while */
302     }                           /* if (PacketHistory[i] != NULL) */
303   }                             /* for (i = ...) */
304 }                               /* PrunePacketHistory */
305
306 /*
307  * Local Variables:
308  * c-basic-offset: 2
309  * indent-tabs-mode: nil
310  * End:
311  */