classifierrfc.cc

网络流量采集及分析软件

/*!\file   ClassifierRFC.cc

    Copyright 2003-2004 Fraunhofer Institute for Open Communication Systems (FOKUS),
                        Berlin, Germany

    This file is part of Network Measurement and Accounting System (NETMATE).

    NETMATE is free software; you can redistribute it and/or modify 
    it under the terms of the GNU General Public License as published by 
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    NETMATE is distributed in the hope that it will be useful, 
    but WITHOUT ANY WARRANTY; without even the implied warranty of 
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this software; if not, write to the Free Software 
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

   Description:
   Classifier based on Recursive Flow Classification (RFC)

   TODO:
    - test inc add of ranges, sets, wildcard rules (more tests)
    - test rules with masks with zero bits (more tests)
    - implement more clever chunk merging


   $Id: ClassifierRFC.cc,v 1.1.1.1 2004/12/23 05:52:34 s_zander Exp $
*/

#include "ClassifierRFC.h"
#include "PerfTimer.h"


//#define DEBUG
//#define PROFILING

/* ------------------------- ClassifierRFC ------------------------- */

void ClassifierRFC::initData()
{
    // set chunk data to 0
    memset(&cdata, 0, sizeof(phases_t));
  
    // set up one matching rule entry with 0 rules
    rmap = NULL;
    rmap_size = 0;

    // set eqnum data to zero
    memset(&eqnums, 0, sizeof(eqNum_t));

    // set number line data to zero
    memset(&nldscs, 0, sizeof(numberLineDescrs_t));

    // reset bitmap
    bmReset(&allrules);

    // set start equiv id to zero
    for (unsigned short i = 0; i < MAX_PHASES; i++) {
        for (unsigned short j = 0; j < MAX_CHUNKS; j++) {
            eqcl[i][j].maxId = 0;
        }
    }
}


void ClassifierRFC::cleanupData()
{
    // delete chunk data
    for (unsigned short i = 0; i < cdata.phaseCount; i++) {
        for (unsigned short j = 0; j < cdata.phases[i].chunkCount; j++) {
            saveDeleteArr(cdata.phases[i].chunks[j].entries);
            for (unsigned short k = 0; k < eqcl[i][j].maxId; k++) {
                if (eqcl[i][j].eids[k].bm != NULL) {
                    saveDelete(eqcl[i][j].eids[k].bm);
                }
            }
            eqcl[i][j].freeList.clear();
            eqcl[i][j].eids.clear();
            eqcl[i][j].bms.clear();
        }
    }

    // delete final rule map
    if (rmap_size > 0) {
        saveDeleteArr(rmap);
        rmap_size = 0;
    }
}


ClassifierRFC::ClassifierRFC( ConfigManager *cnf, Sampler *sa,
			                  PacketQueue *pq, int threaded) 
    : Classifier(cnf, "ClassifierRFC", sa, pq, threaded)
{
#ifdef DEBUG
    log->dlog(ch, "ClassifierRFC constructor" );
#endif

    // initialize the data structures
    initData();

    // 2 lines -> support old g++
    auto_ptr <ClassifierStats> _stats(new ClassifierRFCStats());
    stats = _stats;
}


/* ------------------------- ~ClassifierRFC ------------------------- */

ClassifierRFC::~ClassifierRFC()
{
#ifdef DEBUG
    log->dlog(ch, "ClassifierRFC destructor" );
#endif

#ifdef ENABLE_THREADS
    if (threaded) {
        mutexLock(&maccess);
        stop();
        mutexUnlock(&maccess);
        mutexDestroy(&maccess);
    }
#endif

    cleanupData();
}

/* ----------------------------------------------------------------------------------- */

int ClassifierRFC::classify(metaData_t* pkt)
{
    int indx;
    unsigned short val;
    unsigned short chunks, parents;

#ifdef PROFILING
    unsigned long long ti1, ti2;

    ti1 = PerfTimer::readTSC();
#endif
    
    AUTOLOCK(threaded, &maccess);

    chunks = cdata.phases[0].chunkCount;
    for (unsigned short i = 0; i < chunks; i++) {
        // get the value from the packet data
        indx = pkt->offs[nldscs[i].ref];
        if (indx < 0) {
            return 0;
        } 

        indx += nldscs[i].offs;

        if (nldscs[i].len == 1) {
            val = ((unsigned short) pkt->payload[indx]) & nldscs[i].mask;
        } else {
            // convert to host byte order (support range matches)
            val = ntohs(*((unsigned short *) &pkt->payload[indx]) & nldscs[i].mask);
        }

        // phase 0 memory lookup
        eqnums[0][i] = cdata.phases[0].chunks[i].entries[val];
    }
    
#ifdef DEBUG
    cout << "Classify: phase 0 indices" << endl;
    for (unsigned short i = 0; i < cdata.phases[0].chunkCount; i++) {
        cout << i << ": " << eqnums[0][i] << endl;
	}
    cout << endl;
#endif
    
    // phase 1-n

    for (unsigned short i = 1; i < cdata.phaseCount; i++) {        

        chunks = cdata.phases[i].chunkCount;
    	for (unsigned short j = 0; j < chunks; j++) {

    	    // get entry from first parent chunk
    	    indx = eqnums[i-1][cdata.phases[i].chunks[j].parentChunks[0]];
    	    
            parents = cdata.phases[i].chunks[j].parentCount;
            for (unsigned short k = 1; k < parents; k++) {

                // calculate index
                unsigned short pchunk = cdata.phases[i].chunks[j].parentChunks[k];
                indx = indx * eqcl[i-1][pchunk].maxId + eqnums[i-1][pchunk];
    	    }
            
    	    // phase i memory lookup
    	    eqnums[i][j] = cdata.phases[i].chunks[j].entries[indx];
    	}
    
#ifdef DEBUG
        cout << "Classify: phase " << i << " indices" << endl;
        for (unsigned short j = 0; j < cdata.phases[i].chunkCount; j++) {
            cout << j << ": " << eqnums[i][j] << endl;
        }
#endif
    }
    
    indx = eqnums[cdata.phaseCount-1][0];

    if (rmap_size > 0) {
        for (unsigned short i = 0; i < rmap[indx].ruleCount; i++) {
            pkt->match[i] = rmap[indx].rules[i];
        }
        pkt->match_cnt = rmap[indx].ruleCount;
    }
    
#ifdef PROFILING
    ti2 = PerfTimer::readTSC();
  
    cout << "Class time: " << PerfTimer::ticks2ns(1, ti2-ti1) << " ns" << endl;
#endif

    return pkt->match_cnt;
}


// check a ruleset (the filter part)
void ClassifierRFC::checkRules(ruleDB_t *rules)
{
    // accept everything without complaining
    // the RFC classifier accepts all type of filters
}


// add rules
void ClassifierRFC::addRules(ruleDB_t *rules)
{
    ruleDBIter_t iter;

    AUTOLOCK(threaded, &maccess);
  
    if (stats->rules == 0) {   
        // go for fast initial precomputation
        addInitialRules(rules);
    } else {
        // go for slower incremental add
        for (iter = rules->begin(); iter != rules->end(); iter++) {
            addRule(*iter);
        }
    }

    stats->rules += rules->size(); // adjust number of rules currently used
}


// delete rules
void ClassifierRFC::delRules(ruleDB_t *rules)
{
    ruleDBIter_t iter;

    AUTOLOCK(threaded, &maccess);

    for (iter = rules->begin(); iter != rules->end(); iter++) {
        delRule(*iter);
    }
}

/* ------------------- number line functions ---------------------------------------*/

// add a rule to a point on a number line
void ClassifierRFC::addRuleToPoint(point_t *p, pointType_t type, unsigned short rid)
{  
    const int initial_rule_entries = 16;

    if (p->ruleCount == p->entryCount) {       
    	// get more memory for this rule list
    	if (p->entryCount == 0) {
            // alloc initial rule entries
            p->rules = new rule_t[initial_rule_entries];
            p->entryCount = initial_rule_entries;
    	} else {
            // double the size
            rule_t *new_rules = new rule_t[p->entryCount * 2 ];
            memcpy(new_rules, p->rules, sizeof(rule_t)*p->entryCount);
            saveDeleteArr(p->rules);
            p->rules = new_rules;
            p->entryCount *= 2;
        }
    }

    // add the rule
    p->rules[p->ruleCount].type = type;
    p->rules[p->ruleCount].rid = rid;
    p->ruleCount++;
}


void ClassifierRFC::getIndex(FilterValue *v, FilterValue *m, int size, unsigned short offs,
                             unsigned short *ret)
{
    // put start point in ret[0] and end point in ret[1]
    // use host byte order otherwise range matches are a problem!
    
    if (size == 1) {
        ret[0] = (unsigned short) (v->getValue()[0] & m->getValue()[0]);
        if ((unsigned short)(m->getValue()[0]) == 0xFF) {
            ret[1] = ret[0]+1;
        } else {
            ret[1] = (unsigned short) v->getValue()[0] | ~m->getValue()[0];
        }
    } else {
        ret[0] = ntohs(*((unsigned short *) &(v->getValue()[2*offs]))) & 
          ntohs(*((unsigned short *) &(m->getValue()[2*offs])));
        if (*((unsigned short *) &m->getValue()[2*offs]) == 0xFFFF) {
            ret[1] = ret[0]+1;
        } else {
            ret[1] = ntohs(*((unsigned short *) &(v->getValue()[2*offs]))) |
              ~ ntohs(*((unsigned short *) &(m->getValue()[2*offs])));
        }
    }
}

void ClassifierRFC::projMatchRemap(unsigned short rid, unsigned short chunk_id, int chunk_size, 
                                   unsigned short ch, filter_t *f)
{
    unsigned short ind[2], ind2[2];

    switch (f->mtype) {
    case FT_EXACT:
        // change all equiv classes between start and end of the match
        getIndex(&f->value[0], &f->mask, chunk_size, ch, ind);
        remapIndex(0, chunk_id, ind[0], ind[1], rid);
        break;
    case FT_RANGE:
        // start point is index from value 1, end point is index from value 2
        getIndex(&f->value[0], &f->mask, chunk_size, ch, ind);
        getIndex(&f->value[1], &f->mask, chunk_size, ch, ind2);
        
        // only add both points if the current byte part of the range is actually different
        // otherwise single point
        if (ind != ind2) {
            remapIndex(0, chunk_id, ind[0], ind2[1], rid);
        } else {
            remapIndex(0, chunk_id, ind[0], ind[1], rid);
        }
        break;
    case FT_SET:
      {
          // like FT_EXACT (n times)
          int i = 0;
          while (f->value[i].getLen()) {
              getIndex(&f->value[i], &f->mask, chunk_size, ch, ind);
              
              remapIndex(0, chunk_id, ind[0], ind[1], rid); 			      
              
              i++;
          }
      }
      break;
    case FT_WILD:
        // add bit to all used equiv classes for that chunk
        // chunk data does not need to be changed
        for (unsigned short eq = 0; eq < (int) eqcl[0][chunk_id].maxId; eq++) {
            if (eqcl[0][chunk_id].eids[eq].refc > 0) {
                bmSet(eqcl[0][chunk_id].eids[eq].bm, rid);
            }