info: java: update workspace
[olsrd.git] / lib / bmf / src / PacketHistory.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon (olsrd)
3  *
4  * (c) by the OLSR project
5  *
6  * See our Git repository to find out who worked on this file
7  * and thus is a copyright holder on it.
8  *
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  *
15  * * Redistributions of source code must retain the above copyright
16  *   notice, this list of conditions and the following disclaimer.
17  * * Redistributions in binary form must reproduce the above copyright
18  *   notice, this list of conditions and the following disclaimer in
19  *   the documentation and/or other materials provided with the
20  *   distribution.
21  * * Neither the name of olsr.org, olsrd nor the names of its
22  *   contributors may be used to endorse or promote products derived
23  *   from this software without specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
29  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
31  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
35  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36  * POSSIBILITY OF SUCH DAMAGE.
37  *
38  * Visit http://www.olsr.org for more information.
39  *
40  * If you find this software useful feel free to make a donation
41  * to the project. For more information see the website or contact
42  * the copyright holders.
43  *
44  */
45
46 /* -------------------------------------------------------------------------
47  * File       : PacketHistory.c
48  * Description: Functions for keeping and accessing the history of processed
49  *              multicast IP packets.
50  * Created    : 29 Jun 2006
51  *
52  * ------------------------------------------------------------------------- */
53
54 #include "PacketHistory.h"
55
56 /* System includes */
57 #include <stddef.h> /* NULL */
58 #include <assert.h> /* assert() */
59 #include <string.h> /* memset */
60 #include <sys/types.h> /* u_int16_t, u_int32_t */
61 #include <netinet/ip.h> /* struct iphdr */
62 #include <stdlib.h> /* free() */
63
64 /* OLSRD includes */
65 #include "olsr.h" /* olsr_malloc */
66 #include "scheduler.h" /* GET_TIMESTAMP, TIMED_OUT */
67
68 /* Plugin includes */
69 #include "Packet.h"
70
71 static struct TDupEntry* PacketHistory[HISTORY_HASH_SIZE];
72
73 #define CRC_UPTO_NBYTES 256
74
75 /* -------------------------------------------------------------------------
76  * Function   : GenerateCrc32Table
77  * Description: Generate the table of CRC remainders for all possible bytes,
78  *              according to CRC-32-IEEE 802.3
79  * Input      : none
80  * Output     : none
81  * Return     : none
82  * Data Used  : none
83  * ------------------------------------------------------------------------- */
84 #define CRC32_POLYNOMIAL 0xedb88320UL /* bit-inverse of 0x04c11db7UL */
85
86 static unsigned long CrcTable[256];
87
88 static void GenerateCrc32Table(void)
89 {
90   int i, j;
91   u_int32_t crc;
92   for (i = 0; i < 256; i++)
93   {
94     crc = (u_int32_t) i;
95     for (j = 0; j < 8; j++)
96     {
97       if (crc & 1)
98       {
99         crc = (crc >> 1) ^ CRC32_POLYNOMIAL;
100       }
101       else
102       {
103         crc = (crc >> 1);
104       }
105     }
106     CrcTable[i] = crc;
107   } /* for */
108 } /* GenerateCrc32Table */
109
110 /* -------------------------------------------------------------------------
111  * Function   : CalcCrc32
112  * Description: Calculate CRC-32 according to CRC-32-IEEE 802.3
113  * Input      : buffer - the bytes to calculate the CRC value over
114  *              len - the number of bytes to calculate the CRC value over
115  * Output     : none
116  * Return     : CRC-32 value
117  * Data Used  : none
118  * ------------------------------------------------------------------------- */
119 static u_int32_t CalcCrc32(unsigned char* buffer, ssize_t len)
120 {
121   int i, j;
122   u_int32_t crc = 0xffffffffUL;
123   for (i = 0; i < len; i++)
124   {
125     j = ((int) (crc & 0xFF) ^ *buffer++);
126     crc = (crc >> 8) ^ CrcTable[j];
127   }
128   return crc ^ 0xffffffffUL;
129 } /* CalcCrc32 */
130
131 /* -------------------------------------------------------------------------
132  * Function   : PacketCrc32
133  * Description: Calculates the CRC-32 value for an IP packet
134  * Input      : ipPacket - the IP packet
135  *              len - the number of octets in the IP packet
136  * Output     : none
137  * Return     : 32-bits CRC value
138  * Data Used  : none
139  * ------------------------------------------------------------------------- */
140 u_int32_t PacketCrc32(unsigned char* ipPacket, ssize_t len)
141 {
142   struct TSaveTtl sttl;
143   struct ip* ipHeader;
144   u_int32_t result;
145
146   assert(ipPacket != NULL);
147
148   /* Skip TTL: in a multi-homed OLSR-network, the same multicast packet
149    * may enter the network multiple times, each copy differing only in its
150    * TTL value. BMF must not calculate a different CRC for packets that
151    * differ only in TTL. Skip also the IP-header checksum, because it changes
152    * along with TTL. Besides, it is not a good idea to calculate a CRC over
153    * data that already contains a checksum.
154    *
155    * Clip number of bytes over which CRC is calculated to prevent
156    * long packets from possibly claiming too much CPU resources. */
157   assert(len > 0);
158   if (len > CRC_UPTO_NBYTES)
159   {
160     len = CRC_UPTO_NBYTES;
161   }
162
163   SaveTtlAndChecksum(ipPacket, &sttl);
164
165   ipHeader = (struct ip*) ARM_NOWARN_ALIGN(ipPacket);
166   ipHeader->ip_ttl = 0xFF; /* fixed value of TTL for CRC-32 calculation */
167   ipHeader->ip_sum = 0x5A5A; /* fixed value of IP header checksum for CRC-32 calculation */
168
169   result = CalcCrc32(ipPacket, len);
170
171   RestoreTtlAndChecksum(ipPacket, &sttl);
172   return result;
173 } /* PacketCrc32 */
174
175 /* -------------------------------------------------------------------------
176  * Function   : Hash
177  * Description: Calculates a hash value from a 32-bit value
178  * Input      : from32 - 32-bit value
179  * Output     : none
180  * Return     : hash value
181  * Data Used  : none
182  * ------------------------------------------------------------------------- */
183 u_int32_t Hash(u_int32_t from32)
184 {
185   return ((from32 >> N_HASH_BITS) + from32) & ((1u << N_HASH_BITS) - 1);
186 } /* Hash */
187
188 /* -------------------------------------------------------------------------
189  * Function   : InitPacketHistory
190  * Description: Initialize the packet history table and CRC-32 table
191  * Input      : none
192  * Output     : none
193  * Return     : none
194  * Data Used  : PacketHistory
195  * ------------------------------------------------------------------------- */
196 void InitPacketHistory(void)
197 {
198   unsigned int i;
199
200   GenerateCrc32Table();
201
202   for(i = 0; i < HISTORY_HASH_SIZE; i++)
203   {
204     PacketHistory[i] = NULL;
205   }
206 } /* InitPacketHistory */
207
208 /* -------------------------------------------------------------------------
209  * Function   : CheckAndMarkRecentPacket
210  * Description: Check if this packet was seen recently, then record the fact
211  *              that this packet was seen recently.
212  * Input      : crc32 - 32-bits crc value of the packet
213  * Output     : none
214  * Return     : not recently seen (0), recently seen (1)
215  * Data Used  : PacketHistory
216  * ------------------------------------------------------------------------- */
217 int CheckAndMarkRecentPacket(u_int32_t crc32)
218 {
219   u_int32_t idx;
220   struct TDupEntry* walker;
221   struct TDupEntry* newEntry;
222
223   idx = Hash(crc32);
224   assert(idx < HISTORY_HASH_SIZE);
225
226   for (walker = PacketHistory[idx]; walker != NULL; walker = walker->next)
227   {
228     if (walker->crc32 == crc32)
229     {
230       /* Found duplicate entry */
231
232       /* Always mark as "seen recently": refresh time-out */
233       walker->timeOut = olsr_getTimestamp(HISTORY_HOLD_TIME);
234
235       return 1;
236     } /* if */
237   } /* for */
238
239   /* No duplicate entry found: create one */
240   newEntry = olsr_malloc(sizeof(struct TDupEntry), "BMF: TDupEntry");
241   if (newEntry != NULL)
242   {
243     newEntry->crc32 = crc32;
244     newEntry->timeOut = olsr_getTimestamp(HISTORY_HOLD_TIME);
245
246     /* Add new entry at the front of the list */
247     newEntry->next = PacketHistory[idx];
248     PacketHistory[idx] = newEntry;
249   }
250
251   return 0;
252 } /* CheckAndMarkRecentPacket */
253   
254 /* -------------------------------------------------------------------------
255  * Function   : PrunePacketHistory
256  * Description: Prune the packet history table.
257  * Input      : useless - not used
258  * Output     : none
259  * Return     : none
260  * Data Used  : PacketHistory
261  * ------------------------------------------------------------------------- */
262 void PrunePacketHistory(void* useless __attribute__((unused)))
263 {
264   uint i;
265   for (i = 0; i < HISTORY_HASH_SIZE; i++)
266   {
267     if (PacketHistory[i] != NULL)
268     {
269       struct TDupEntry* nextEntry = PacketHistory[i];
270       struct TDupEntry* prevEntry = NULL;
271       while (nextEntry != NULL) 
272       {
273         struct TDupEntry* entry = nextEntry;
274         nextEntry = entry->next;
275
276         if (olsr_isTimedOut(entry->timeOut))
277         {
278           /* De-queue */
279           if (prevEntry != NULL)
280           {
281             prevEntry->next = entry->next;
282           }
283           else
284           {
285             PacketHistory[i] = entry->next;
286           } /* if */
287
288           /* De-allocate memory */
289           free(entry); 
290               }
291               else
292               {
293                 prevEntry = entry;
294               } /* if */
295       } /* while */
296     } /* if (PacketHistory[i] != NULL) */
297   } /* for (i = ...) */
298 } /* PrunePacketHistory */