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