* replaced the bmf plugin with the most recent 1.3 from sf.net with the
[olsrd.git] / lib / bmf / src / PacketHistory.c
1 /*
2  * OLSR Basic Multicast Forwarding (BMF) plugin.
3  * Copyright (c) 2005, 2006, 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  * $Id: PacketHistory.c,v 1.2 2007/02/10 17:05:56 bernd67 Exp $ 
40  * ------------------------------------------------------------------------- */
41
42 #include "PacketHistory.h"
43
44 /* System includes */
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 "olsr.h" /* olsr_printf */
52
53 /* Plugin includes */
54 #include "Packet.h"
55
56 static u_int32_t PacketHistory[HISTORY_TABLE_SIZE];
57
58 #define CRC_UPTO_NBYTES 256
59
60 #if 0
61 /* -------------------------------------------------------------------------
62  * Function   : CalcCrcCcitt
63  * Description: Calculate 16-bits CRC according to CRC-CCITT specification
64  * Input      : buffer - the bytes to calculate the CRC value over
65  *              len - the number of bytes to calculate the CRC value over
66  * Output     : none
67  * Return     : CRC-16 value
68  * Data Used  : none
69  * ------------------------------------------------------------------------- */
70 static u_int16_t CalcCrcCcitt(unsigned char* buffer, ssize_t len)
71 {
72   /* Initial value of 0xFFFF should be 0x1D0F according to
73    * www.joegeluso.com/software/articles/ccitt.htm */
74   u_int16_t crc = 0xFFFF; 
75   int i;
76
77   assert(buffer != NULL);
78
79   for (i = 0; i < len; i++)
80   {
81     crc  = (unsigned char)(crc >> 8) | (crc << 8);
82     crc ^= buffer[i];
83     crc ^= (unsigned char)(crc & 0xff) >> 4;
84     crc ^= (crc << 8) << 4;
85     crc ^= ((crc & 0xff) << 4) << 1;
86   }
87   return crc;
88 }
89 #endif
90
91 /* -------------------------------------------------------------------------
92  * Function   : GenerateCrc32Table
93  * Description: Generate the table of CRC remainders for all possible bytes,
94  *              according to CRC-32-IEEE 802.3
95  * Input      : none
96  * Output     : none
97  * Return     : none
98  * Data Used  : none
99  * ------------------------------------------------------------------------- */
100 #define CRC32_POLYNOMIAL 0xedb88320UL /* bit-inverse of 0x04c11db7UL */
101
102 static unsigned long CrcTable[256];
103
104 static void GenerateCrc32Table(void)
105 {
106   int i, j;
107   u_int32_t crc;
108   for (i = 0; i < 256; i++)
109   {
110     crc = (u_int32_t) i;
111     for (j = 0; j < 8; j++)
112     {
113       if (crc & 1)
114       {
115         crc = (crc >> 1) ^ CRC32_POLYNOMIAL;
116       }
117       else
118       {
119         crc = (crc >> 1);
120       }
121     }
122     CrcTable[i] = crc;
123   }
124 }
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 CalcCrc32(unsigned char* buffer, ssize_t len)
136 {
137   int i, j;
138   u_int32_t crc = 0xffffffffUL;
139   for (i = 0; i < len; i++)
140   {
141     j = ((int) (crc & 0xFF) ^ *buffer++);
142     crc = (crc >> 8) ^ CrcTable[j];
143   }
144   return crc ^ 0xffffffffUL;
145 }
146
147 /* -------------------------------------------------------------------------
148  * Function   : PacketCrc32
149  * Description: Calculates the CRC-32 value for an Ethernet packet
150  * Input      : ethPkt - the Ethernet packet
151  *              len - the number of octets in the Ethernet packet
152  * Output     : none
153  * Return     : 32-bits hash value
154  * Data Used  : none
155  * Notes      : The source and destination MAC address are not taken into account
156  *              in the CRC calculation.
157  * ------------------------------------------------------------------------- */
158 u_int32_t PacketCrc32(unsigned char* ethPkt, ssize_t len)
159 {
160   ssize_t nCrcBytes;
161   struct TSaveTtl sttl;
162   struct iphdr* iph;
163   u_int32_t result;
164
165   assert(ethPkt != NULL);
166
167   /* Start CRC calculation at ethertype; skip source and destination MAC 
168    * addresses, and ethertype.
169    *
170    * Also skip TTL: in a multi-homed OLSR-network, the same multicast packet
171    * may enter the network multiple times, each copy differing only in its
172    * TTL value. BMF must not calculate a different CRC for packets that
173    * differ only in TTL. Skip also the IP-header checksum, because it changes
174    * along with TTL. Besides, it is not a good idea to calculate a CRC over
175    * data that already contains a checksum.
176    *
177    * Clip number of bytes over which CRC is calculated to prevent
178    * long packets from possibly claiming too much CPU resources. */
179   nCrcBytes = len - IP_HDR_OFFSET;
180   assert(nCrcBytes > 0);
181   if (nCrcBytes > CRC_UPTO_NBYTES)
182   {
183     nCrcBytes = CRC_UPTO_NBYTES;
184   }
185
186   SaveTtlAndChecksum(ethPkt, &sttl);
187
188   iph = (struct iphdr*) (ethPkt + IP_HDR_OFFSET);
189   iph->ttl = 0xFF; /* fixed value of TTL for CRC-32 calculation */
190   iph->check = 0x5A5A; /* fixed value of IP header checksum for CRC-32 calculation */
191
192   result = CalcCrc32(ethPkt + IP_HDR_OFFSET, nCrcBytes);
193
194   RestoreTtlAndChecksum(ethPkt, &sttl);
195   return result;
196 }
197
198 /* Calculates a 16-bit hash value from a 32-bit hash value */
199 u_int16_t Hash16(u_int32_t hash32)
200 {
201   return ((hash32 >> 16) + hash32) & 0xFFFFU;
202 }
203
204 /* -------------------------------------------------------------------------
205  * Function   : InitPacketHistory
206  * Description: Initialize the packet history table and CRC-32 table
207  * Input      : none
208  * Output     : none
209  * Return     : none
210  * Data Used  : PacketHistory
211  * ------------------------------------------------------------------------- */
212 void InitPacketHistory()
213 {
214   memset(PacketHistory, 0, sizeof(PacketHistory));
215   GenerateCrc32Table();
216 }
217
218 /* -------------------------------------------------------------------------
219  * Function   : MarkRecentPacket
220  * Description: Record the fact that this packet was seen recently
221  * Input      : hash16
222  * Output     : none
223  * Return     : none
224  * Data Used  : PacketHistory
225  * ------------------------------------------------------------------------- */
226 void MarkRecentPacket(u_int16_t hash16)
227 {
228   u_int32_t index;
229   uint offset;
230
231   index = hash16 / NPACKETS_PER_ENTRY;
232   assert(index < HISTORY_TABLE_SIZE);
233
234   offset = (hash16 % NPACKETS_PER_ENTRY) * NBITS_PER_PACKET;
235   assert(offset <= NBITS_IN_UINT32 - NBITS_PER_PACKET);
236
237   /* Mark as "seen recently" */
238   PacketHistory[index] = PacketHistory[index] | (0x3u << offset);
239 }
240
241 /* -------------------------------------------------------------------------
242  * Function   : CheckAndMarkRecentPacket
243  * Description: Check if this packet was seen recently, then record the fact
244  *              that this packet was seen recently.
245  * Input      : hash16
246  * Output     : none
247  * Return     : not recently seen (0), recently seen (1)
248  * Data Used  : PacketHistory
249  * ------------------------------------------------------------------------- */
250 int CheckAndMarkRecentPacket(u_int16_t hash16)
251 {
252   u_int32_t index;
253   uint offset;
254   u_int32_t bitMask;
255   int result;
256
257   index = hash16 / NPACKETS_PER_ENTRY;
258   assert(index < HISTORY_TABLE_SIZE);
259
260   offset =  (hash16 % NPACKETS_PER_ENTRY) * NBITS_PER_PACKET;
261   assert(offset <= NBITS_IN_UINT32 - NBITS_PER_PACKET);
262
263   bitMask = 0x1u << offset;
264   result = ((PacketHistory[index] & bitMask) == bitMask);
265   
266   /* Always mark as "seen recently" */
267   PacketHistory[index] = PacketHistory[index] | (0x3u << offset);
268
269   return result;
270 }
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)
281 {
282   uint i;
283   for (i = 0; i < HISTORY_TABLE_SIZE; i++)
284   {
285     if (PacketHistory[i] > 0)
286     {
287       uint j;
288       for (j = 0; j < NPACKETS_PER_ENTRY; j++)
289       {
290         uint offset = j * NBITS_PER_PACKET;
291
292         u_int32_t bitMask = 0x3u << offset;
293         u_int32_t bitsSeenRecenty = 0x3u << offset;
294         u_int32_t bitsTimingOut = 0x1u << offset;
295
296         /* 10 should never occur */
297         assert ((PacketHistory[i] & bitMask) != (0x2u << offset));
298         
299         if ((PacketHistory[i] & bitMask) == bitsSeenRecenty)
300         {
301           /* 11 -> 01 */
302           PacketHistory[i] &= ~bitMask | bitsTimingOut;
303         }
304         else if ((PacketHistory[i] & bitMask) == bitsTimingOut)
305         {
306           /* 01 -> 00 */
307           PacketHistory[i] &= ~bitMask;
308         }
309       } /* for (j = ...) */
310     } /* if (PacketHistory[i] > 0) */
311   } /* for (i = ...) */
312 }