/*
* OLSR Basic Multicast Forwarding (BMF) plugin.
* Copyright (c) 2005 - 2007, Thales Communications, Huizen, The Netherlands.
* Written by Erik Tromp.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
* * Neither the name of Thales, BMF nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
* OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/* -------------------------------------------------------------------------
* File : PacketHistory.c
* Description: Functions for keeping and accessing the history of processed
* multicast IP packets.
* Created : 29 Jun 2006
*
* ------------------------------------------------------------------------- */
#include "PacketHistory.h"
/* System includes */
#include <stddef.h> /* NULL */
#include <assert.h> /* assert() */
#include <string.h> /* memset */
#include <sys/types.h> /* u_int16_t, u_int32_t */
#include <netinet/ip.h> /* struct iphdr */
/* OLSRD includes */
#include "defs.h" /* GET_TIMESTAMP, TIMED_OUT */
#include "olsr.h" /* olsr_printf */
/* Plugin includes */
#include "Packet.h"
static struct TDupEntry* PacketHistory[HISTORY_HASH_SIZE];
#define CRC_UPTO_NBYTES 256
#if 0
/* -------------------------------------------------------------------------
* Function : CalcCrcCcitt
* Description: Calculate 16-bits CRC according to CRC-CCITT specification
* Input : buffer - the bytes to calculate the CRC value over
* len - the number of bytes to calculate the CRC value over
* Output : none
* Return : CRC-16 value
* Data Used : none
* ------------------------------------------------------------------------- */
static u_int16_t CalcCrcCcitt(unsigned char* buffer, ssize_t len)
{
/* Initial value of 0xFFFF should be 0x1D0F according to
* www.joegeluso.com/software/articles/ccitt.htm */
u_int16_t crc = 0xFFFF;
int i;
assert(buffer != NULL);
for (i = 0; i < len; i++)
{
crc = (unsigned char)(crc >> 8) | (crc << 8);
crc ^= buffer[i];
crc ^= (unsigned char)(crc & 0xff) >> 4;
crc ^= (crc << 8) << 4;
crc ^= ((crc & 0xff) << 4) << 1;
}
return crc;
} /* CalcCrcCcitt */
#endif
/* -------------------------------------------------------------------------
* Function : GenerateCrc32Table
* Description: Generate the table of CRC remainders for all possible bytes,
* according to CRC-32-IEEE 802.3
* Input : none
* Output : none
* Return : none
* Data Used : none
* ------------------------------------------------------------------------- */
#define CRC32_POLYNOMIAL 0xedb88320UL /* bit-inverse of 0x04c11db7UL */
static unsigned long CrcTable[256];
static void GenerateCrc32Table(void)
{
int i, j;
u_int32_t crc;
for (i = 0; i < 256; i++)
{
crc = (u_int32_t) i;
for (j = 0; j < 8; j++)
{
if (crc & 1)
{
crc = (crc >> 1) ^ CRC32_POLYNOMIAL;
}
else
{
crc = (crc >> 1);
}
}
CrcTable[i] = crc;
} /* for */
} /* GenerateCrc32Table */
/* -------------------------------------------------------------------------
* Function : CalcCrc32
* Description: Calculate CRC-32 according to CRC-32-IEEE 802.3
* Input : buffer - the bytes to calculate the CRC value over
* len - the number of bytes to calculate the CRC value over
* Output : none
* Return : CRC-32 value
* Data Used : none
* ------------------------------------------------------------------------- */
static u_int32_t CalcCrc32(unsigned char* buffer, ssize_t len)
{
int i, j;
u_int32_t crc = 0xffffffffUL;
for (i = 0; i < len; i++)
{
j = ((int) (crc & 0xFF) ^ *buffer++);
crc = (crc >> 8) ^ CrcTable[j];
}
return crc ^ 0xffffffffUL;
} /* CalcCrc32 */
/* -------------------------------------------------------------------------
* Function : PacketCrc32
* Description: Calculates the CRC-32 value for an IP packet
* Input : ipPacket - the IP packet
* len - the number of octets in the IP packet
* Output : none
* Return : 32-bits CRC value
* Data Used : none
* ------------------------------------------------------------------------- */
u_int32_t PacketCrc32(unsigned char* ipPacket, ssize_t len)
{
struct TSaveTtl sttl;
struct ip* ipHeader;
u_int32_t result;
assert(ipPacket != NULL);
/* Skip TTL: in a multi-homed OLSR-network, the same multicast packet
* may enter the network multiple times, each copy differing only in its
* TTL value. BMF must not calculate a different CRC for packets that
* differ only in TTL. Skip also the IP-header checksum, because it changes
* along with TTL. Besides, it is not a good idea to calculate a CRC over
* data that already contains a checksum.
*
* Clip number of bytes over which CRC is calculated to prevent
* long packets from possibly claiming too much CPU resources. */
assert(len > 0);
if (len > CRC_UPTO_NBYTES)
{
len = CRC_UPTO_NBYTES;
}
SaveTtlAndChecksum(ipPacket, &sttl);
ipHeader = (struct ip*)ipPacket;
ipHeader->ip_ttl = 0xFF; /* fixed value of TTL for CRC-32 calculation */
ipHeader->ip_sum = 0x5A5A; /* fixed value of IP header checksum for CRC-32 calculation */
result = CalcCrc32(ipPacket, len);
RestoreTtlAndChecksum(ipPacket, &sttl);
return result;
} /* PacketCrc32 */
/* -------------------------------------------------------------------------
* Function : Hash
* Description: Calculates a hash value from a 32-bit value
* Input : from32 - 32-bit value
* Output : none
* Return : hash value
* Data Used : none
* ------------------------------------------------------------------------- */
u_int32_t Hash(u_int32_t from32)
{
return ((from32 >> N_HASH_BITS) + from32) & ((1 << N_HASH_BITS) - 1);
} /* Hash */
/* -------------------------------------------------------------------------
* Function : InitPacketHistory
* Description: Initialize the packet history table and CRC-32 table
* Input : none
* Output : none
* Return : none
* Data Used : PacketHistory
* ------------------------------------------------------------------------- */
void InitPacketHistory(void)
{
int i;
GenerateCrc32Table();
for(i = 0; i < HISTORY_HASH_SIZE; i++)
{
PacketHistory[i] = NULL;
}
} /* InitPacketHistory */
/* -------------------------------------------------------------------------
* Function : CheckAndMarkRecentPacket
* Description: Check if this packet was seen recently, then record the fact
* that this packet was seen recently.
* Input : crc32 - 32-bits crc value of the packet
* Output : none
* Return : not recently seen (0), recently seen (1)
* Data Used : PacketHistory
* ------------------------------------------------------------------------- */
int CheckAndMarkRecentPacket(u_int32_t crc32)
{
u_int32_t index;
struct TDupEntry* walker;
struct TDupEntry* newEntry;
index = Hash(crc32);
assert(index < HISTORY_HASH_SIZE);
for (walker = PacketHistory[index]; walker != NULL; walker = walker->next)
{
if (walker->crc32 == crc32)
{
/* Found duplicate entry */
/* Always mark as "seen recently": refresh time-out */
walker->timeOut = GET_TIMESTAMP(HISTORY_HOLD_TIME);
return 1;
} /* if */
} /* for */
/* No duplicate entry found: create one */
newEntry = malloc(sizeof(struct TDupEntry));
if (newEntry != NULL)
{
newEntry->crc32 = crc32;
newEntry->timeOut = GET_TIMESTAMP(HISTORY_HOLD_TIME);
/* Add new entry at the front of the list */
newEntry->next = PacketHistory[index];
PacketHistory[index] = newEntry;
}
return 0;
} /* CheckAndMarkRecentPacket */
/* -------------------------------------------------------------------------
* Function : PrunePacketHistory
* Description: Prune the packet history table.
* Input : useless - not used
* Output : none
* Return : none
* Data Used : PacketHistory
* ------------------------------------------------------------------------- */
void PrunePacketHistory(void* useless __attribute__((unused)))
{
uint i;
for (i = 0; i < HISTORY_HASH_SIZE; i++)
{
if (PacketHistory[i] != NULL)
{
struct TDupEntry* nextEntry = PacketHistory[i];
struct TDupEntry* prevEntry = NULL;
while (nextEntry != NULL)
{
struct TDupEntry* entry = nextEntry;
nextEntry = entry->next;
if (TIMED_OUT(entry->timeOut))
{
/* De-queue */
if (prevEntry != NULL)
{
prevEntry->next = entry->next;
}
else
{
PacketHistory[i] = entry->next;
} /* if */
/* De-allocate memory */
free(entry);
}
else
{
prevEntry = entry;
} /* if */
} /* while */
} /* if (PacketHistory[i] != NULL) */
} /* for (i = ...) */
} /* PrunePacketHistory */
syntax highlighted by Code2HTML, v. 0.9.1