classifierrfc.cc

网络流量采集及分析软件

        rmap_size = size;
    }
        
    // loop over all equiv classes from the last chunk
    for (unsigned short eq = 0; eq < (int) eqcl[phase][0].maxId; eq++) {
        if (eqcl[phase][0].eids[eq].refc > 0) {
            bitmap_t *bm = eqcl[phase][0].eids[eq].bm;

            rmap[eq].ruleCount = 0;

            for (unsigned short i = 0; i < (bm->msb+1)*BITS_PER_ELEM; i++) {
                if (bmTest(bm, i)) {
                    // bidir support
                    if (((i%2) == 1) && (bmTest(bm, i-1))) {
                        // if this is a backward rule and if forward rule bit is set
                        // ignore because forward already matches
                    } else {
                        // use id of forward rule entry
                        rmap[eq].rules[rmap[eq].ruleCount] = i/2;
                        rmap[eq].ruleCount++; 		       
                    }
                }
                if (rmap[eq].ruleCount == MAX_RULES_MATCH) {
                    throw Error("more than %d rules match at the same time", 
                                MAX_RULES_MATCH);
                }
            }
        }
    }

#ifdef DEBUG
    cout << "final chunk" << endl;
    for (unsigned int i = 0; i < cdata.phases[phase].chunks[0].entryCount; i++) {
        unsigned short indx = cdata.phases[phase].chunks[0].entries[i];
        cout << i << ": " << indx;
        cout << " -> ";
        for (unsigned short j = 0; j < rmap[indx].ruleCount; j++) {
            cout << rmap[indx].rules[j] << " ";
        }
        cout << endl;
    }
    cout << endl;
#endif
}

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

// add rules (currently no rules are installed 
void ClassifierRFC::addInitialRules(ruleDB_t *rules)
{
    //! number line used index
    int nlused[MAX_CHUNKS];
    int has_bspec = 0;
#ifdef PROFILING
    struct timeval t1, t2;

    gettimeofday(&t1, NULL);
#endif

    // assume that nlines, cdata, eqcl and bms are initialized

    if ((int)rules->size() > MAX_RULES) {
        throw Error("the maximum number of rules is %d", MAX_RULES);
    }
    
    // initialize number lines
    memset(&nlines, 0, sizeof(numberLines_t));

    // get a list of all matches of all rules uniquely identified by offset,length
    // and initialize the number lines
    for (ruleDBIter_t ri = rules->begin(); ri != rules->end(); ++ri) {
        Rule *r = (*ri);
        
        // 1. add forward part, 2. add backward part (if bidir)
        for (unsigned short backward=0; backward <= r->isBidir(); backward++) {
            // check for any filter with backward specifications
            if (backward) {
                if ((has_bspec = hasBackwardSpec(r)) == 0) {
                    // this rule has no backward spec at all -> no backward rule
                    continue;
                }
            }
            
            for (filterListIter_t fi = r->getFilter()->begin(); fi != r->getFilter()->end(); ++fi) {
                // get the relevant stuff from the match
                unsigned short len = fi->len;
                unsigned short offs;
                refer_t ref;
                // bidir support
                if (backward && !fi->rname.empty()) {
                    offs = fi->roffs;
                    ref = fi->rrefer;
                } else {
                    offs = fi->offs;
                    ref = fi->refer;
                }

                // split filter into chunks
                // matches are either 1 byte long or multiple of 2 bytes
                unsigned short chunk_count = (len/2) + (len%2);
                for (unsigned short ch = 0; ch < chunk_count; ch++) {
                    unsigned short chunk_size = (len > (2*ch + 1)) ? 2 : 1;
                    // find number line for this offset
                    if (findNumberLine(ref, offs, ch, chunk_size) < 0) {
                        addNumberLine(ref, offs, ch, chunk_size, &fi->fdmask);
                    }
                }   
            }
        }
    }

    // project each match of the rule onto the number line, marking
    // start and end points
    // an exact match is start and end point
    // a range match is start and end point
    // a set match is a number of pairs of start and end points
    // wildcards matches (point at 0)
    for (ruleDBIter_t ri = rules->begin(); ri != rules->end(); ++ri) {
        Rule *r = (*ri);
        unsigned short rid = 0;
        
        // bidir support
        for (unsigned short backward=0; backward <= r->isBidir(); backward++) {
            // clear number line used bites
            memset(nlused, 0, sizeof(nlused));

            if (backward) {
                if (!has_bspec) {
                    continue;
                }
             
                // backward id
                rid =  r->getUId() * 2 + 1;
            } else {
                // forward id
                rid =  r->getUId() * 2 ;
            }
            
            for (filterListIter_t fi = r->getFilter()->begin(); fi != r->getFilter()->end(); ++fi) {
                // get the match values
                unsigned short len = fi->len;
                unsigned short offs;
                refer_t ref;
                // bidir support
                if (backward && !fi->rname.empty()) {
                    offs = fi->roffs;
                    ref = fi->rrefer;
                } else {
                    offs = fi->offs;
                    ref = fi->refer;
                }
                     
                unsigned short chunk_count = (len/2) + (len%2);
                for (unsigned short ch = 0; ch < chunk_count; ch++) {
                    unsigned short chunk_size = (len > (2*ch + 1)) ? 2 : 1;

                    // find number line for this offset
                    int chunk_id = findNumberLine(ref, offs, ch, chunk_size);   
                    // mark number line as used
                    nlused[chunk_id] = 1;
                    // now chunk_id points to the correct number line
                    // project points from current match
                    projMatch(rid, chunk_id, chunk_size, ch, &(*fi));
                }
            }
            
            // project this rule as FT_WILD on all number lines we have no explicit matches
            for (unsigned short i = 0; i < nlines.lineCount; i++) {
                if (!nlused[i]) {
                    addRuleToPoint(&nlines.lines[i].points[0], RULE_START, rid);
                }
            }
            
            // set rule bit in all rules
            bmSet(&allrules, rid);
        }
    }
    
#ifdef DEBUG
    printNumberLines();
#endif
    
    // PHASE 0
    
    // now scan through the number line looking for distinct equivalence
    // classes
    for (unsigned short i = 0; i < nlines.lineCount; i++) {
        unsigned short eq = 0;
        bitmap_t bmp;
        bmReset(&bmp);
              
        makeNewChunk(0, nlines.lines[i].line_size);

        for (unsigned int j = 0; j < nlines.lines[i].line_size; j++) {
            unsigned short rule_cnt = nlines.lines[i].points[j].ruleCount;

            if (rule_cnt > 0) {
                for (unsigned short k = 0; k < rule_cnt; k++) {
                    switch (nlines.lines[i].points[j].rules[k].type) {
                    case RULE_START:
                        // set rule bits
                        bmSet(&bmp,nlines.lines[i].points[j].rules[k].rid);
                        break;
                    case RULE_END:
                        // unset rule bits
                        bmReset(&bmp,nlines.lines[i].points[j].rules[k].rid);
                        break;
                    }
                }            
                eq = findEC(0, i, &bmp);
            }
            // else fill in the last eq            
            cdata.phases[0].chunks[i].entries[j] = eq;
        }
        
#ifdef PREALLOC_EQUIV_CLASSES
        // create PREALLOC_CLASSES unused equiv classes per phase 0 chunk
        addPreAllocEC(0, i, PREALLOC_CLASSES);
#endif

#ifdef DEBUG
        printChunk(0, i, 0);
#endif
    }

    // free line number space
    for (unsigned short i = 0; i < nlines.lineCount; i++) {
        for (unsigned int j=0; j < nlines.lines[i].line_size; j++) {
            if (nlines.lines[i].points[j].entryCount > 0) {
                saveDeleteArr(nlines.lines[i].points[j].rules);
            }
        }
        saveDeleteArr(nlines.lines[i].points);
    }

    // PHASE 1-n
   
    // determine the number of phases from the number of phase 0 chunks
    for (unsigned short j = 2; j < MAX_PHASES; j++) {
        if ((2 << (j-1)) >= cdata.phases[0].chunkCount) {
            cdata.phaseCount = j+1;
            break;
        }
    }

    if (cdata.phaseCount > MAX_PHASES) {
        throw Error("reduction not possible in %d phases", MAX_PHASES);
    }
    
    for (unsigned short i = 1; i < cdata.phaseCount; i++) {     
        // decide which chunks to combine from previous phase
        // FIXME simply combine them in numeric order for now
        
        // determine the reduction factor
        int rfac = cdata.phases[i-1].chunkCount / cdata.phaseCount;
        if (rfac < 2) {
            rfac = 2;
        }
        // current chunk index
        int cindx = 0;
        int size = 1;
        for (unsigned short j = 0; j <= cdata.phases[i-1].chunkCount; j++) {
            // start new chunk after rfac chunks and include single last chunk
            if (((j > 0) && ((j % rfac) == 0)) || (j == cdata.phases[i-1].chunkCount)) {
                // start next chunk
                makeNewChunk(i, size);
                cindx++;
                size = 1;
            }
            cdata.phases[i].chunks[cindx].parentChunks[cdata.phases[i].chunks[cindx].parentCount++] = j;
            size *= eqcl[i-1][j].maxId;
        }

#ifdef DEBUG
        for (unsigned short j = 0; j < cdata.phases[i].chunkCount; j++) {
            cout << "create chunk " << j << " from phase " << i-1 << " chunks ";
            for (unsigned short k = 0; k < cdata.phases[i].chunks[j].parentCount; k++) {
                cout << cdata.phases[i].chunks[j].parentChunks[k] << " ";
            }
            cout << endl;
        }
        cout << endl;
#endif
	
        // now combine the chunks
	
        // loop over all target chunks
        for (unsigned short j = 0; j < cdata.phases[i].chunkCount; j++) {
            // start the recursion with a bitmap where all bits are set
            bitmap_t bmp;
            bmSet(&bmp);
            int indx = 0;
            doIntersection(i, j, 0, &indx, &bmp);
        
#ifdef PREALLOC_EQUIV_CLASSES
            // add PREALLOC_CLASSES unused classes per chunk
            addPreAllocEC(i, j, PREALLOC_CLASSES);
#endif

#ifdef DEBUG	    
            printChunk(i, j, 1);
#endif
        }
    }
    
    // generate final rule map
    genFinalMap(cdata.phaseCount-1);
    
#ifdef PROFILING
    gettimeofday(&t2, NULL);
    
    cout << "Precomputation: " << endl;
    printProfiling(&t1, &t2);
#endif
          
}

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

// remap phase 0 chunk entries
void ClassifierRFC::remapIndex(int phase, int chunk, int from, int to, int rid)
{
    unsigned short eq = 0, oeq = 0;
    unsigned short remap[65535];

    // map old class to new class
    for (unsigned short i = 0; i < eqcl[phase][chunk].maxId; i++) {
        remap[i] = i;
    }
    
    for (unsigned short i = from; i < to; i++) {
        oeq = cdata.phases[phase].chunks[chunk].entries[i];
        eq = remap[oeq];
      
        if (eq == oeq) {
            // get new equiv class
            bitmap_t bmp = *eqcl[phase][chunk].eids[oeq].bm;
            bmSet(&bmp, rid);
            
            eq = findEC(phase, chunk, &bmp);

            // insert new mapping
            remap[oeq] = eq;
        } else {
            eqcl[phase][chunk].eids[eq].refc++;
        }

        // the old bitmap may have become unused
        // a preallocated bitmap was _never_ used before
        if (eqcl[phase][chunk].eids[oeq].refc > 0) {
            eqcl[phase][chunk].eids[oeq].refc--;
            
            // if ref counter = 0 put onto free list
            if (eqcl[phase][chunk].eids[oeq].refc == 0) {
                eqcl[phase][chunk].freeList.push_back(oeq);
                // delete from bitmap map
                eqcl[phase][chunk].bms.erase(eqcl[phase][chunk].eids[oeq].bm);
            }
        }
        
        // change this entry
        cdata.phases[phase].chunks[chunk].entries[i] = eq;
            
    }
}