Update to BMF 1.6.2 (written by Erik Tromp)
[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> /* free() */
50
51 /* OLSRD includes */
52 #include "olsr.h" /* olsr_printf */
53 #include "scheduler.h" /* GET_TIMESTAMP, TIMED_OUT */
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  * Function   : CalcCrcCcitt
65  * Description: Calculate 16-bits CRC according to CRC-CCITT specification
66  * Input      : buffer - the bytes to calculate the CRC value over
67  *              len - the number of bytes to calculate the CRC value over
68  * Output     : none
69  * Return     : CRC-16 value
70  * Data Used  : none
71  * ------------------------------------------------------------------------- */
72 static u_int16_t CalcCrcCcitt(unsigned char* buffer, ssize_t len)
73 {
74   /* Initial value of 0xFFFF should be 0x1D0F according to
75    * www.joegeluso.com/software/articles/ccitt.htm */
76   u_int16_t crc = 0xFFFF; 
77   int i;
78
79   assert(buffer != NULL);
80
81   for (i = 0; i < len; i++)
82   {
83     crc  = (unsigned char)(crc >> 8) | (crc << 8);
84     crc ^= buffer[i];
85     crc ^= (unsigned char)(crc & 0xff) >> 4;
86     crc ^= (crc << 8) << 4;
87     crc ^= ((crc & 0xff) << 4) << 1;
88   }
89   return crc;
90 } /* CalcCrcCcitt */
91 #endif
92
93 /* -------------------------------------------------------------------------
94  * Function   : GenerateCrc32Table
95  * Description: Generate the table of CRC remainders for all possible bytes,
96  *              according to CRC-32-IEEE 802.3
97  * Input      : none
98  * Output     : none
99  * Return     : none
100  * Data Used  : none
101  * ------------------------------------------------------------------------- */
102 #define CRC32_POLYNOMIAL 0xedb88320UL /* bit-inverse of 0x04c11db7UL */
103
104 static unsigned long CrcTable[256];
105
106 static void GenerateCrc32Table(void)
107 {
108   int i, j;
109   u_int32_t crc;
110   for (i = 0; i < 256; i++)
111   {
112     crc = (u_int32_t) i;
113     for (j = 0; j < 8; j++)
114     {
115       if (crc & 1)
116       {
117         crc = (crc >> 1) ^ CRC32_POLYNOMIAL;
118       }
119       else
120       {
121         crc = (crc >> 1);
122       }
123     }
124     CrcTable[i] = crc;
125   } /* for */
126 } /* GenerateCrc32Table */
127
128 /* -------------------------------------------------------------------------
129  * Function   : CalcCrc32
130  * Description: Calculate CRC-32 according to CRC-32-IEEE 802.3
131  * Input      : buffer - the bytes to calculate the CRC value over
132  *              len - the number of bytes to calculate the CRC value over
133  * Output     : none
134  * Return     : CRC-32 value
135  * Data Used  : none
136  * ------------------------------------------------------------------------- */
137 static u_int32_t 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   {
143     j = ((int) (crc & 0xFF) ^ *buffer++);
144     crc = (crc >> 8) ^ CrcTable[j];
145   }
146   return crc ^ 0xffffffffUL;
147 } /* CalcCrc32 */
148
149 /* -------------------------------------------------------------------------
150  * Function   : PacketCrc32
151  * Description: Calculates the CRC-32 value for an IP packet
152  * Input      : ipPacket - the IP packet
153  *              len - the number of octets in the IP packet
154  * Output     : none
155  * Return     : 32-bits CRC value
156  * Data Used  : none
157  * ------------------------------------------------------------------------- */
158 u_int32_t 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   {
178     len = CRC_UPTO_NBYTES;
179   }
180
181   SaveTtlAndChecksum(ipPacket, &sttl);
182
183   ipHeader = (struct ip*)ipPacket;
184   ipHeader->ip_ttl = 0xFF; /* fixed value of TTL for CRC-32 calculation */
185   ipHeader->ip_sum = 0x5A5A; /* fixed value of IP header checksum for CRC-32 calculation */
186
187   result = CalcCrc32(ipPacket, len);
188
189   RestoreTtlAndChecksum(ipPacket, &sttl);
190   return result;
191 } /* PacketCrc32 */
192
193 /* -------------------------------------------------------------------------
194  * Function   : Hash
195  * Description: Calculates a hash value from a 32-bit value
196  * Input      : from32 - 32-bit value
197  * Output     : none
198  * Return     : hash value
199  * Data Used  : none
200  * ------------------------------------------------------------------------- */
201 u_int32_t 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 InitPacketHistory(void)
215 {
216   int i;
217
218   GenerateCrc32Table();
219
220   for(i = 0; i < HISTORY_HASH_SIZE; i++)
221   {
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 CheckAndMarkRecentPacket(u_int32_t crc32)
236 {
237   u_int32_t idx;
238   struct TDupEntry* walker;
239   struct TDupEntry* newEntry;
240
241   idx = Hash(crc32);
242   assert(idx < HISTORY_HASH_SIZE);
243
244   for (walker = PacketHistory[idx]; walker != NULL; walker = walker->next)
245   {
246     if (walker->crc32 == crc32)
247     {
248       /* Found duplicate entry */
249
250       /* Always mark as "seen recently": refresh time-out */
251       walker->timeOut = olsr_getTimestamp(HISTORY_HOLD_TIME);
252
253       return 1;
254     } /* if */
255   } /* for */
256
257   /* No duplicate entry found: create one */
258   newEntry = olsr_malloc(sizeof(struct TDupEntry), "BMF: TDupEntry");
259   if (newEntry != NULL)
260   {
261     newEntry->crc32 = crc32;
262     newEntry->timeOut = olsr_getTimestamp(HISTORY_HOLD_TIME);
263
264     /* Add new entry at the front of the list */
265     newEntry->next = PacketHistory[idx];
266     PacketHistory[idx] = newEntry;
267   }
268
269   return 0;
270 } /* CheckAndMarkRecentPacket */
271   
272 /* -------------------------------------------------------------------------
273  * Function   : PrunePacketHistory
274  * Description: Prune the packet history table.
275  * Input      : useless - not used
276  * Output     : none
277  * Return     : none
278  * Data Used  : PacketHistory
279  * ------------------------------------------------------------------------- */
280 void PrunePacketHistory(void* useless __attribute__((unused)))
281 {
282   uint i;
283   for (i = 0; i < HISTORY_HASH_SIZE; i++)
284   {
285     if (PacketHistory[i] != NULL)
286     {
287       struct TDupEntry* nextEntry = PacketHistory[i];
288       struct TDupEntry* prevEntry = NULL;
289       while (nextEntry != NULL) 
290       {
291         struct TDupEntry* entry = nextEntry;
292         nextEntry = entry->next;
293
294         if (olsr_isTimedOut(entry->timeOut))
295         {
296           /* De-queue */
297           if (prevEntry != NULL)
298           {
299             prevEntry->next = entry->next;
300           }
301           else
302           {
303             PacketHistory[i] = entry->next;
304           } /* if */
305
306           /* De-allocate memory */
307           free(entry); 
308               }
309               else
310               {
311                 prevEntry = entry;
312               } /* if */
313       } /* while */
314     } /* if (PacketHistory[i] != NULL) */
315   } /* for (i = ...) */
316 } /* PrunePacketHistory */