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