e49fe240052d5f095a2883e4f8b9e56a9fe49578
[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 #include <stdlib.h>             /* atoi, malloc */
51
52 /* OLSRD includes */
53 #include "defs.h"               /* GET_TIMESTAMP, TIMED_OUT */
54 #include "olsr.h"
55 #include "olsr_timer.h"
56 #include "olsr_socket.h"          /* now_times */
57
58 /* Plugin includes */
59 #include "Packet.h"
60
61 static struct TDupEntry *PacketHistory[HISTORY_HASH_SIZE];
62
63 #define CRC_UPTO_NBYTES 256
64
65 #if 0
66
67 /* -------------------------------------------------------------------------
68  * Function   : CalcCrcCcitt
69  * Description: Calculate 16-bits CRC according to CRC-CCITT specification
70  * Input      : buffer - the bytes to calculate the CRC value over
71  *              len - the number of bytes to calculate the CRC value over
72  * Output     : none
73  * Return     : CRC-16 value
74  * Data Used  : none
75  * ------------------------------------------------------------------------- */
76 static u_int16_t
77 CalcCrcCcitt(unsigned char *buffer, ssize_t len)
78 {
79   /* Initial value of 0xFFFF should be 0x1D0F according to
80    * www.joegeluso.com/software/articles/ccitt.htm */
81   u_int16_t crc = 0xFFFF;
82   int i;
83
84   assert(buffer != NULL);
85
86   for (i = 0; i < len; i++) {
87     crc = (unsigned char)(crc >> 8) | (crc << 8);
88     crc ^= buffer[i];
89     crc ^= (unsigned char)(crc & 0xff) >> 4;
90     crc ^= (crc << 8) << 4;
91     crc ^= ((crc & 0xff) << 4) << 1;
92   }
93   return crc;
94 }                               /* CalcCrcCcitt */
95 #endif
96
97 /* -------------------------------------------------------------------------
98  * Function   : GenerateCrc32Table
99  * Description: Generate the table of CRC remainders for all possible bytes,
100  *              according to CRC-32-IEEE 802.3
101  * Input      : none
102  * Output     : none
103  * Return     : none
104  * Data Used  : none
105  * ------------------------------------------------------------------------- */
106 #define CRC32_POLYNOMIAL 0xedb88320UL   /* bit-inverse of 0x04c11db7UL */
107
108 static unsigned long CrcTable[256];
109
110 static void
111 GenerateCrc32Table(void)
112 {
113   int i, j;
114   u_int32_t crc;
115   for (i = 0; i < 256; i++) {
116     crc = (u_int32_t) i;
117     for (j = 0; j < 8; j++) {
118       if (crc & 1) {
119         crc = (crc >> 1) ^ CRC32_POLYNOMIAL;
120       } else {
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
138 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     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
159 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     len = CRC_UPTO_NBYTES;
179   }
180
181   SaveTtlAndChecksum(ipPacket, &sttl);
182
183   ipHeader = (struct ip *)(ARM_NOWARN_ALIGN(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
202 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
216 InitPacketHistory(void)
217 {
218   int i;
219
220   GenerateCrc32Table();
221
222   for (i = 0; i < HISTORY_HASH_SIZE; i++) {
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
237 CheckAndMarkRecentPacket(u_int32_t crc32)
238 {
239   u_int32_t idx;
240   struct TDupEntry *walker;
241   struct TDupEntry *newEntry;
242
243   idx = Hash(crc32);
244   assert(idx < HISTORY_HASH_SIZE);
245
246   for (walker = PacketHistory[idx]; walker != NULL; walker = walker->next) {
247     if (walker->crc32 == crc32) {
248       /* Found duplicate entry */
249
250       /* Always mark as "seen recently": refresh time-out */
251       walker->timeOut = olsr_timer_getAbsolute(HISTORY_HOLD_TIME);
252
253       return 1;
254     }                           /* if */
255   }                             /* for */
256
257   /* No duplicate entry found: create one */
258   newEntry = malloc(sizeof(struct TDupEntry));
259   if (newEntry != NULL) {
260     newEntry->crc32 = crc32;
261     newEntry->timeOut = olsr_timer_getAbsolute(HISTORY_HOLD_TIME);
262
263     /* Add new entry at the front of the list */
264     newEntry->next = PacketHistory[idx];
265     PacketHistory[idx] = 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
280 PrunePacketHistory(void *useless __attribute__ ((unused)))
281 {
282   uint i;
283   for (i = 0; i < HISTORY_HASH_SIZE; i++) {
284     if (PacketHistory[i] != NULL) {
285       struct TDupEntry *nextEntry = PacketHistory[i];
286       struct TDupEntry *prevEntry = NULL;
287       while (nextEntry != NULL) {
288         struct TDupEntry *entry = nextEntry;
289         nextEntry = entry->next;
290
291         if (olsr_timer_isTimedOut(entry->timeOut)) {
292           /* De-queue */
293           if (prevEntry != NULL) {
294             prevEntry->next = entry->next;
295           } else {
296             PacketHistory[i] = entry->next;
297           }                     /* if */
298
299           /* De-allocate memory */
300           free(entry);
301         } else {
302           prevEntry = entry;
303         }                       /* if */
304       }                         /* while */
305     }                           /* if (PacketHistory[i] != NULL) */
306   }                             /* for (i = ...) */
307 }                               /* PrunePacketHistory */
308
309 /*
310  * Local Variables:
311  * c-basic-offset: 2
312  * indent-tabs-mode: nil
313  * End:
314  */