/*
* This file is part of the nfdump project.
*
* Copyright (c) 2004, SWITCH - Teleinformatikdienste fuer Lehre und Forschung
* 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 SWITCH 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.
*
* $Author: peter $
*
* $Id: nftree.c 97 2008-02-21 09:50:02Z peter $
*
* $LastChangedRevision: 97 $
*
*/
#include "config.h"
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <string.h>
#include <errno.h>
#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif
#include "rbtree.h"
#include "nfdump.h"
#include "nffile.h"
#include "nf_common.h"
#include "ipconv.h"
#include "nftree.h"
#include "grammar.h"
/*
* netflow filter engine
*
*/
extern char *CurrentIdent;
#define MAXBLOCKS 1024
static FilterBlock_t *FilterTree;
static uint32_t memblocks;
static uint32_t NumBlocks = 1; /* index 0 reserved */
#define IdentNumBlockSize 32
static uint16_t MaxIdents;
static uint16_t NumIdents;
static char **IdentList;
static void UpdateList(uint32_t a, uint32_t b);
/* flow processing functions */
static inline uint64_t pps_function(uint64_t *data);
static inline uint64_t bps_function(uint64_t *data);
static inline uint64_t bpp_function(uint64_t *data);
static inline uint64_t duration_function(uint64_t *data);
/*
* flow processing function table:
* order of entries must correspond with filter functions enum in nftree.h
*/
static struct flow_procs_map_s {
char *name;
flow_proc_t function;
} flow_procs_map[] = {
{"none", NULL},
{"pps", pps_function},
{"bps", bps_function},
{"bpp", bpp_function},
{"duration", duration_function},
{NULL, NULL}
};
uint64_t *IPstack = NULL;
uint32_t StartNode;
uint16_t Extended;
// 128bit comapre for IPv6
static int IPNodeCMP(struct IPListNode *e1, struct IPListNode *e2) {
if ( e1->ip[0] == e2->ip[0] ) {
if ( e1->ip[1] == e2->ip[1] )
return 0;
else
return (e1->ip[1] < e2->ip[1] ? -1 : 1);
}
else {
return (e1->ip[0] < e2->ip[0] ? -1 : 1);
}
} // End of IPNodeCMP
// 64bit uint64 compare
static int ULNodeCMP(struct ULongListNode *e1, struct ULongListNode *e2) {
if ( e1->value == e2->value )
return 0;
else
return (e1->value < e2->value ? -1 : 1);
} // End of ULNodeCMP
// Insert the IP RB tree code here
RB_GENERATE(IPtree, IPListNode, entry, IPNodeCMP);
// Insert the Ulong RB tree code here
RB_GENERATE(ULongtree, ULongListNode, entry, ULNodeCMP);
void InitTree(void) {
memblocks = 1;
FilterTree = (FilterBlock_t *)malloc(MAXBLOCKS * sizeof(FilterBlock_t));
if ( !FilterTree ) {
fprintf(stderr, "Memory allocation error in %s line %d: %s\n", __FILE__, __LINE__, strerror(errno) );
exit(255);
}
ClearFilter();
} // End of InitTree
/*
* Clear Filter
*/
void ClearFilter(void) {
NumBlocks = 1;
Extended = 0;
MaxIdents = 0;
NumIdents = 0;
IdentList = NULL;
memset((void *)FilterTree, 0, MAXBLOCKS * sizeof(FilterBlock_t));
} /* End of ClearFilter */
FilterEngine_data_t *CompileFilter(char *FilterSyntax) {
FilterEngine_data_t *engine;
int ret;
if ( !FilterSyntax )
return NULL;
IPstack = (uint64_t *)malloc(16 * MAXHOSTS);
if ( !IPstack ) {
fprintf(stderr, "Memory allocation error in %s line %d: %s\n", __FILE__, __LINE__, strerror(errno) );
exit(255);
}
InitTree();
lex_init(FilterSyntax);
ret = yyparse();
if ( ret != 0 ) {
return NULL;
}
lex_cleanup();
free(IPstack);
engine = malloc(sizeof(FilterEngine_data_t));
if ( !engine ) {
fprintf(stderr, "Memory allocation error in %s line %d: %s\n", __FILE__, __LINE__, strerror(errno) );
exit(255);
}
engine->nfrecord = NULL;
engine->StartNode = StartNode;
engine->Extended = Extended;
engine->IdentList = IdentList;
engine->filter = FilterTree;
if ( Extended )
engine->FilterEngine = RunExtendedFilter;
else
engine->FilterEngine = RunFilter;
return engine;
} // End of GetTree
/*
* For testing purpose only
*/
int nblocks(void) {
return NumBlocks - 1;
} /* End of nblocks */
/*
* Returns next free slot in blocklist
*/
uint32_t NewBlock(uint32_t offset, uint64_t mask, uint64_t value, uint16_t comp, uint32_t function, void *data) {
uint32_t n = NumBlocks;
if ( n >= ( memblocks * MAXBLOCKS ) ) {
memblocks++;
FilterTree = realloc(FilterTree, memblocks * MAXBLOCKS * sizeof(FilterBlock_t));
if ( !FilterTree ) {
fprintf(stderr, "Memory allocation error in %s line %d: %s\n", __FILE__, __LINE__, strerror(errno) );
exit(255);
}
}
FilterTree[n].offset = offset;
FilterTree[n].mask = mask;
FilterTree[n].value = value;
FilterTree[n].invert = 0;
FilterTree[n].comp = comp;
FilterTree[n].function = flow_procs_map[function].function;
FilterTree[n].fname = flow_procs_map[function].name;
FilterTree[n].data = data;
if ( comp > 0 || function > 0 )
Extended = 1;
FilterTree[n].numblocks = 1;
FilterTree[n].blocklist = (uint32_t *)malloc(sizeof(uint32_t));
FilterTree[n].superblock = n;
FilterTree[n].blocklist[0] = n;
NumBlocks++;
return n;
} /* End of NewBlock */
/*
* Connects the two blocks b1 and b2 ( AND ) and returns index of superblock
*/
uint32_t Connect_AND(uint32_t b1, uint32_t b2) {
uint32_t a, b, i, j;
if ( FilterTree[b1].numblocks <= FilterTree[b2].numblocks ) {
a = b1;
b = b2;
} else {
a = b2;
b = b1;
}
/* a points to block with less children and becomes the superblock
* connect b to a
*/
for ( i=0; i < FilterTree[a].numblocks; i++ ) {
j = FilterTree[a].blocklist[i];
if ( FilterTree[j].invert ) {
if ( FilterTree[j].OnFalse == 0 ) {
FilterTree[j].OnFalse = b;
}
} else {
if ( FilterTree[j].OnTrue == 0 ) {
FilterTree[j].OnTrue = b;
}
}
}
UpdateList(a,b);
return a;
} /* End of Connect_AND */
/*
* Connects the two blocks b1 and b2 ( OR ) and returns index of superblock
*/
uint32_t Connect_OR(uint32_t b1, uint32_t b2) {
uint32_t a, b, i, j;
if ( FilterTree[b1].numblocks <= FilterTree[b2].numblocks ) {
a = b1;
b = b2;
} else {
a = b2;
b = b1;
}
/* a points to block with less children and becomes the superblock
* connect b to a
*/
for ( i=0; i < FilterTree[a].numblocks; i++ ) {
j = FilterTree[a].blocklist[i];
if ( FilterTree[j].invert ) {
if ( FilterTree[j].OnTrue == 0 ) {
FilterTree[j].OnTrue = b;
}
} else {
if ( FilterTree[j].OnFalse == 0 ) {
FilterTree[j].OnFalse = b;
}
}
}
UpdateList(a,b);
return a;
} /* End of Connect_OR */
/*
* Inverts OnTrue and OnFalse
*/
uint32_t Invert(uint32_t a) {
uint32_t i, j;
for ( i=0; i< FilterTree[a].numblocks; i++ ) {
j = FilterTree[a].blocklist[i];
FilterTree[j].invert = FilterTree[j].invert ? 0 : 1 ;
}
return a;
} /* End of Invert */
/*
* Update supernode infos:
* node 'b' was connected to 'a'. update node 'a' supernode data
*/
static void UpdateList(uint32_t a, uint32_t b) {
size_t s;
uint32_t i,j;
/* numblocks contains the number of blocks in the superblock */
s = FilterTree[a].numblocks + FilterTree[b].numblocks;
FilterTree[a].blocklist = (uint32_t *)realloc(FilterTree[a].blocklist, s * sizeof(uint32_t));
if ( !FilterTree[a].blocklist ) {
fprintf(stderr, "Memory allocation error in %s line %d: %s\n", __FILE__, __LINE__, strerror(errno) );
exit(250);
}
/* connect list of node 'b' after list of node 'a' */
j = FilterTree[a].numblocks;
for ( i=0; i< FilterTree[b].numblocks; i++ ) {
FilterTree[a].blocklist[j+i] = FilterTree[b].blocklist[i];
}
FilterTree[a].numblocks = s;
/* set superblock info of all children to new superblock */
for ( i=0; i< FilterTree[a].numblocks; i++ ) {
j = FilterTree[a].blocklist[i];
FilterTree[j].superblock = a;
}
/* cleanup old node 'b' */
FilterTree[b].numblocks = 0;
if ( FilterTree[b].blocklist )
free(FilterTree[b].blocklist);
} /* End of UpdateList */
/*
* Dump Filterlist
*/
void DumpList(FilterEngine_data_t *args) {
uint32_t i, j;
for (i=1; i<NumBlocks; i++ ) {
if ( args->filter[i].invert )
printf("Index: %u, Offset: %u, Mask: %.16llx, Value: %.16llx, Superblock: %u, Numblocks: %u, !OnTrue: %u, !OnFalse: %u Comp: %u Function: %s\n",
i, args->filter[i].offset, (unsigned long long)args->filter[i].mask,
(unsigned long long)args->filter[i].value, args->filter[i].superblock,
args->filter[i].numblocks, args->filter[i].OnTrue, args->filter[i].OnFalse, args->filter[i].comp, args->filter[i].fname);
else
printf("Index: %u, Offset: %u, Mask: %.16llx, Value: %.16llx, Superblock: %u, Numblocks: %u, OnTrue: %u, OnFalse: %u Comp: %u Function: %s\n",
i, args->filter[i].offset, (unsigned long long)args->filter[i].mask,
(unsigned long long)args->filter[i].value, args->filter[i].superblock,
args->filter[i].numblocks, args->filter[i].OnTrue, args->filter[i].OnFalse, args->filter[i].comp, args->filter[i].fname);
if ( args->filter[i].data ) {
if ( args->filter[i].comp == CMP_IPLIST ) {
struct IPListNode *node;
RB_FOREACH(node, IPtree, args->filter[i].data) {
printf("%.16llx %.16llx\n", (unsigned long long)node->ip[0], (unsigned long long)node->ip[1]);
}
} else if ( args->filter[i].comp == CMP_ULLIST ) {
struct ULongListNode *node;
RB_FOREACH(node, ULongtree, args->filter[i].data) {
printf("%.16llx \n", (unsigned long long)node->value);
}
} else
printf("Error comp: %i\n", args->filter[i].comp);
}
printf("\tBlocks: ");
for ( j=0; j<args->filter[i].numblocks; j++ )
printf("%i ", args->filter[i].blocklist[j]);
printf("\n");
}
printf("NumBlocks: %i\n", NumBlocks - 1);
for ( i=0; i<NumIdents; i++ ) {
printf("Ident %i: %s\n", i, IdentList[i]);
}
} /* End of DumpList */
/* fast filter engine */
int RunFilter(FilterEngine_data_t *args) {
uint32_t index, offset;
int evaluate, invert;
index = args->StartNode;
evaluate = 0;
invert = 0;
while ( index ) {
offset = args->filter[index].offset;
invert = args->filter[index].invert;
evaluate = ( args->nfrecord[offset] & args->filter[index].mask ) == args->filter[index].value;
index = evaluate ? args->filter[index].OnTrue : args->filter[index].OnFalse;
}
return invert ? !evaluate : evaluate;
} /* End of RunFilter */
/* extended filter engine */
int RunExtendedFilter(FilterEngine_data_t *args) {
uint32_t index, offset;
uint64_t value;
int evaluate, invert;
index = args->StartNode;
evaluate = 0;
invert = 0;
while ( index ) {
offset = args->filter[index].offset;
invert = args->filter[index].invert;
if (args->filter[index].function == NULL)
value = args->nfrecord[offset] & args->filter[index].mask;
else
value = args->filter[index].function(args->nfrecord);
switch (args->filter[index].comp) {
case CMP_EQ:
evaluate = value == args->filter[index].value;
break;
case CMP_GT:
evaluate = value > args->filter[index].value;
break;
case CMP_LT:
evaluate = value < args->filter[index].value;
break;
case CMP_IDENT:
value = args->filter[index].value;
evaluate = strncmp(CurrentIdent, args->IdentList[value], IdentLen) == 0 ;
break;
case CMP_FLAGS:
if ( invert )
evaluate = value > 0;
else
evaluate = value == args->filter[index].value;
break;
case CMP_IPLIST: {
struct IPListNode find;
find.ip[0] = args->nfrecord[offset];
find.ip[1] = args->nfrecord[offset+1];
evaluate = RB_FIND(IPtree, args->filter[index].data, &find) != NULL; }
break;
case CMP_ULLIST: {
struct ULongListNode find;
find.value = value;
evaluate = RB_FIND(ULongtree, args->filter[index].data, &find ) != NULL; }
break;
}
index = evaluate ? args->filter[index].OnTrue : args->filter[index].OnFalse;
}
return invert ? !evaluate : evaluate;
} /* End of RunExtendedFilter */
uint32_t AddIdent(char *Ident) {
uint32_t num;
if ( MaxIdents == 0 ) {
// allocate first array block
MaxIdents = IdentNumBlockSize;
IdentList = (char **)malloc( MaxIdents * sizeof(char *));
if ( !IdentList ) {
fprintf(stderr, "Memory allocation error in %s line %d: %s\n", __FILE__, __LINE__, strerror(errno) );
exit(254);
}
memset((void *)IdentList, 0, MaxIdents * sizeof(char *));
NumIdents = 0;
} else if ( NumIdents == MaxIdents ) {
// extend array block
MaxIdents += IdentNumBlockSize;
IdentList = realloc((void *)IdentList, MaxIdents * sizeof(char *));
if ( !IdentList ) {
fprintf(stderr, "Memory allocation error in %s line %d: %s\n", __FILE__, __LINE__, strerror(errno) );
exit(254);
}
}
num = NumIdents++;
IdentList[num] = strdup(Ident);
if ( !IdentList[num] ) {
fprintf(stderr, "Memory allocation error in %s line %d: %s\n", __FILE__, __LINE__, strerror(errno) );
exit(254);
}
return num;
} // End of AddIdent
/* record processing functions */
static inline uint64_t duration_function(uint64_t *data) {
master_record_t *record;
uint64_t duration;
record = (master_record_t *)data;
/* duration in msec */
duration = 1000*(record->last - record->first) + record->msec_last - record->msec_first;
return duration;
} // End of duration_function
static inline uint64_t pps_function(uint64_t *data) {
master_record_t *record;
uint64_t duration;
record = (master_record_t *)data;
/* duration in msec */
duration = 1000*(record->last - record->first) + record->msec_last - record->msec_first;
if ( duration == 0 )
return 0;
else
return ( 1000LL * record->dPkts ) / duration;
} // End of pps_function
static inline uint64_t bps_function(uint64_t *data) {
master_record_t *record;
uint64_t duration;
record = (master_record_t *)data;
/* duration in msec */
duration = 1000*(record->last - record->first) + record->msec_last - record->msec_first;
if ( duration == 0 )
return 0;
else
return ( 8000LL * record->dOctets ) / duration; /* 8 bits per Octet - x 1000 for msec */
} // End of bps_function
static inline uint64_t bpp_function(uint64_t *data) {
master_record_t *record;
record = (master_record_t *)data;
return record->dPkts ? record->dOctets / record->dPkts : 0;
} // End of bpp_function