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