classifierrfc.cc

网络流量采集及分析软件

void ClassifierRFC::addRule(Rule *r)
{
    int nlused[MAX_CHUNKS];
    int rid = 0;
    int oldChunkCount = cdata.phases[0].chunkCount;
#ifdef PROFILING
    struct timeval t1, t2;

    gettimeofday(&t1, NULL);
#endif    

    if (stats->rules == MAX_RULES) {
        throw Error("max rule number exceeded");
    }

    // phase 0

    // clear nlused index
    memset(nlused, 0, sizeof(nlused));

    // bidir support
    for (unsigned short backward=0; backward <= r->isBidir(); backward++) {
        if (backward) {
            if (hasBackwardSpec(r) == 0) {
                // this rule has no backward spec at all -> no backward rule
                continue;
            }
           
            rid = r->getUId() * 2 + 1; 
        } else {
            rid = r->getUId() * 2 ;
        }

        // loop over all matches
        for (filterListIter_t fi = r->getFilter()->begin(); fi != r->getFilter()->end(); ++fi) {
            // get the match values
            unsigned short len = fi->len;
            filterType_t mtype = fi->mtype;
            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 = findNumberLine(ref, offs, ch, chunk_size);
                if (chunk < 0) {
                    bitmap_t bmp = allrules;
                    int eq = 0;
                    bmInfo_t bmi = {NULL, 1};

                    // add new chunk
                    addNumberLineDescr(ref, offs, ch, chunk_size, &fi->fdmask);
                    makeNewChunk(0, (chunk_size == 1) ? NUMBER_LINE_SIZE_8B : NUMBER_LINE_SIZE_16B);
                    chunk = cdata.phases[0].chunkCount-1;

                    // mark number line as used
                    nlused[chunk] = 1;

                    if (mtype == FT_WILD) {
                        // equiv class 1 is all rules + rid
                        bmSet(&bmp, rid);
                        
                        bmi.bm = new bitmap_t;
                        *bmi.bm = bmp;
                        
                        // only one equiv class
                        eq = eqcl[0][chunk].maxId++;
                        eqcl[0][chunk].bms[bmi.bm] = eq;
                        eqcl[0][chunk].eids.push_back(bmi);
                    } else {
                        // set all existing rules as equiv class 0
                        bmi.bm = new bitmap_t;
                        *bmi.bm = bmp;
              
                        eq = eqcl[0][chunk].maxId++;
                        eqcl[0][chunk].bms[bmi.bm] = eq;
                        eqcl[0][chunk].eids.push_back(bmi);

                        // and all existing + current rule as equiv class 1
                        bmSet(&bmp, rid);

                        bmi.bm = new bitmap_t;
                        *bmi.bm = bmp;
                     
                        eq = eqcl[0][chunk].maxId++;
                        eqcl[0][chunk].bms[bmi.bm] = eq;
                        eqcl[0][chunk].eids.push_back(bmi);
                        
                        projMatchDirectly(eq, chunk, chunk_size, ch, &(*fi));
                    }

#ifdef PREALLOC_EQUIV_CLASSES
                    // add PREALLOC unused equiv classes
                    addPreAllocEC(0, chunk, PREALLOC_CLASSES);
#endif
                } else {
                    // use existing chunk

                    // mark number line as used
                    nlused[chunk] = 1;
	
                    // change equiv classes and chunk data
                    projMatchRemap(rid, chunk, chunk_size, ch, &(*fi));
                }
            }
        }

        // project this rule as FT_WILD on all chunks we have no explicit matches
        for (unsigned short i = 0; i < cdata.phases[0].chunkCount; i++) {
            if (!nlused[i]) {
                for (chunkEqClArrayIter_t ei = eqcl[0][i].eids.begin(); ei != eqcl[0][i].eids.end(); ++ei) {
                    if (ei->refc > 0) {
                        bmSet(ei->bm, rid);
                    }
                }
            }
        }
    }

#ifdef DEBUG
    for (unsigned short i = 0; i < cdata.phases[0].chunkCount; i++) {
        printChunk(0, i, 0);
    }
#endif

    // if we have new phase 0 chunks adjust the chunk merging
    // merge the new chunks into chunk 0,1,2,..,n of phase 1
    // always add to chunk witch has the smallest number of parents
    // for performance reasons it should be avoided to get new chunks on inc adds!
    unsigned short new_chunks = cdata.phases[0].chunkCount - oldChunkCount;
    if (new_chunks > 0) {
        for (unsigned short i = oldChunkCount; i < cdata.phases[0].chunkCount; i++) {
            // find chunks with smallest number of parents
            unsigned short min = 0xFFFF;
            for (unsigned short j = 0; j < cdata.phases[1].chunkCount; j++) {
                if (cdata.phases[1].chunks[j].parentCount < min) {
                    min = cdata.phases[1].chunks[j].parentCount;
                }
            }

            // add
            cdata.phases[1].chunks[ch].parentChunks[cdata.phases[1].chunks[min].parentCount++] = i;

#ifdef DEBUG
            cout << "add phase 0 chunk " << i << " as parent to chunk " << min << endl;
#endif
        }
    }

    // phase 1-n

    // update phase 1-n chunk entries and equivalence classes
   
    for (unsigned short i = 1; i < cdata.phaseCount; i++) {	
        // loop over all target chunks
        for (unsigned short j = 0; j < cdata.phases[i].chunkCount; j++) {
            // realloc chunk size if necessary
            unsigned int size = 1;
            for (unsigned short k = 0; k < cdata.phases[i].chunks[j].parentCount; k++) {
                size *= eqcl[i-1][cdata.phases[i].chunks[j].parentChunks[k]].maxId;
            }
	   
            if (size != cdata.phases[i].chunks[j].entryCount) {
                unsigned short *new_entries = new unsigned short[size];
                memset(new_entries, 0, sizeof(unsigned short)*size);
                memcpy(new_entries, cdata.phases[i].chunks[j].entries, 
                       sizeof(unsigned short)*cdata.phases[i].chunks[j].entryCount);
                saveDeleteArr(cdata.phases[i].chunks[j].entries);
                cdata.phases[i].chunks[j].entries = new_entries;
                cdata.phases[i].chunks[j].entryCount = size;
            }

            // 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 DEBUG
            printChunk(i, j, 1);
#endif
        }
    }

    // add new rule in final map
    genFinalMap(cdata.phaseCount-1);

    // add to all rules
    bmSet(&allrules, rid);

#ifdef PROFILING
    gettimeofday(&t2, NULL);

    cout << "Inc Add: " << endl;
    printProfiling(&t1, &t2);
#endif       
}


void ClassifierRFC::delRule(Rule *r)
{
    int rid = 0;
#ifdef REMAP_AFTER_DELETE
    unsigned short remap[65535];
    int do_remap = 0;
#endif
#ifdef PROFILING
    struct timeval t1, t2;

    gettimeofday(&t1, NULL);
#endif    
 
    // incremental delete is done backwards
    // first the rule is deleted from the final rule map
    // (this would be sufficient for deleting but it would cause problems for later adds)
    // then it's deleted from all equiv classes
 
    for (unsigned short backward=0; backward <= r->isBidir(); backward++) {
        if (backward) {
            // backward id
            rid =  r->getUId() * 2 + 1;
        } else {
            // remove rule from final rule map
            for (unsigned int i = 0; i < rmap_size; i++) {
                int del = 0;
                
                for (unsigned short j = 0; j < rmap[i].ruleCount; j++) {
                    if (rmap[i].rules[j] == rid) {
                        del = 1;
                    } else if (del) {
                        rmap[i].rules[j-1] = rmap[i].rules[j];
                    } 
                }
                if (del) {
                    rmap[i].ruleCount--;
                }
            }
        
            // forward id
            rid =  r->getUId() * 2 ;
        }
   
        // delete rule bit from all equiv classes and remove old bitmaps from phase 0
        for (unsigned short i = 0; i < cdata.phases[0].chunkCount; i++) {
            for (unsigned short eq = 0; eq < eqcl[0][i].maxId; eq++) {
                bmInfo_t *bi = &eqcl[0][i].eids[eq];
#ifdef REMAP_AFTER_DELETE
                remap[eq] = eq;
#endif

                if ((bi->refc > 0) && bmTest(bi->bm, rid)) {                
                    // delete bitmap from bitmap map
                    eqcl[0][i].bms.erase(bi->bm);
                
                    // reset rule bit
                    bmReset(bi->bm, rid);

                    // check resulting bitmap
                    chunkBmListIter_t b = eqcl[0][i].bms.find(bi->bm);

                    if (b == eqcl[0][i].bms.end()) {
                        // add new class
                        eqcl[0][i].bms[bi->bm] = eq;
                    } else {
#ifdef REMAP_AFTER_DELETE
                        // map to new class
                        remap[eq] = b->second;
                        do_remap = 1;
#endif
                    }
                } 
            }

#ifdef REMAP_AFTER_DELETE
            if (do_remap) {
                for (unsigned int j = 0; j < cdata.phases[0].chunks[i].entryCount; j++) {
                    unsigned short oeq = cdata.phases[0].chunks[i].entries[j];
                    unsigned short eq = remap[oeq];
                    if (eq != oeq) {
                        if (eqcl[0][i].eids[oeq].refc > 0) {
                            eqcl[0][i].eids[oeq].refc--;
                        
                            // if ref counter = 0 put onto free list
                            if (eqcl[0][i].eids[oeq].refc == 0) {
                                eqcl[0][i].freeList.push_back(oeq);
                            }
                        }
                   
                        // change
                        cdata.phases[0].chunks[i].entries[j] = eq;

                        eqcl[0][i].eids[eq].refc++;
                    }
                }
            }
#endif

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

        }

        // remove rule bit in all rules
        bmReset(&allrules, rid);
    
        stats->rules--;
    }

    if (stats->rules == 0) {
        cleanupData();
        initData();
    }

#ifdef DEBUG
    cout << "final chunk" << endl;
    if (cdata.phaseCount > 0) {
        for (unsigned int i = 0; i < cdata.phases[cdata.phaseCount-1].chunks[0].entryCount; i++) {
            unsigned short indx = cdata.phases[cdata.phaseCount-1].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

  
#ifdef PROFILING
    gettimeofday(&t2, NULL);

    cout << "Inc Delete: " << endl;
    printProfiling(&t1, &t2);
#endif  
}


/* ------------------------- operator<< ------------------------- */

ostream& operator<< ( ostream &os, ClassifierRFC &cl )
{
    cl.dump(os);
    return os;
}