Azinix

evlMain.c

Go to the documentation of this file.
00001 /** \file evlMain.c
00002 
00003 \brief Routines for implementing the overall architecture
00004 of Narya firewalling, also some test routines.
00005 
00006 */
00007 
00008 #include "evl.h"
00009 
00010 /*AutomaticStart*************************************************************/
00011 
00012 /*---------------------------------------------------------------------------*/
00013 /* Static function prototypes                                                */
00014 /*---------------------------------------------------------------------------*/
00015 
00016 static void preprocess (Pkt_ProcessPkt_t *, Evl_Manager_t *);
00017 static void evlGetPacketsLoop (int maxNumPktsToRead, Evl_Bridge_t * aBridge,
00018                    array_t * pktArray, u_int32_t slice,
00019                    int useSynthetic);
00020 static void evlComputeActionsLoop (Evl_BridgeStats_t * stats,
00021                    Evl_Manager_t * aMgr, Circbuf_t * iBuf,
00022                    Circbuf_t * ppCache, u_int32_t slice,
00023                    Circbuf_t * actionBuf);
00024 static void evlPerformActionsLoop (Evl_Manager_t * aMgr,
00025                    Evl_Bridge_t * aBridge,
00026                    Circbuf_t * actionBuf, u_int32_t slice);
00027 static void evlQueuingLoop (Evl_BridgeStats_t * stats, Evl_Manager_t * aMgr,
00028                 Circbuf_t * actionBuf, Circbuf_t * ppCache,
00029                 Circbuf_t * oBuf, u_int32_t slice);
00030 static void evlWritePacketsLoop (Evl_Bridge_t * aBridge, u_int32_t slice,
00031                  int useSynthetic, array_t * ackSeqArray);
00032 static inline void recoverSpace (Pkt_ProcessPkt_t * pp, Circbuf_t * ppCache);
00033 static inline void updateQueuePriorities (Q_Q_t * currentQueue,
00034                       Heap_t * qHeap);
00035 static inline bool sliceDone (u_int32_t entryTime, u_int32_t slice);
00036 static int  testBuildPrefixAutomaton ();
00037 static int catchSignal (int signo, handler_t handler);
00038 static bool testQueueIsEmpty (Q_Q_t * currentQueue);
00039 static Pkt_ProcessPkt_t *readQueueHead (Q_Q_t * currentQueue, int *classPtr);
00040 static Pkt_ProcessPkt_t *getQueueHead (Q_Q_t * aQ, Q_Flow_t * aFlow,
00041                        double newRate, int *classPtr);
00042 static void updateRateInfo (util_timing_t * startOfCurrentWindow,
00043                 double timeWindowDuration,
00044                 double *numBytesExitedInWindow, int length);
00045 static int queueInsertPp (Q_Q_t * aQ, Pkt_ProcessPkt_t * pp, int classIndex,
00046               bool insertAtEnd);
00047 static void pktPrint (char *mesg, Pkt_EthernetHdr_t * pkt);
00048 static void  coreCheck (Evl_BridgeStats_t * stats, Evl_Manager_t * aMgr,
00049                Circbuf_t * iBuf, Circbuf_t * actionBuf,
00050                Circbuf_t * oBuf);
00051 static void bridgeSigHandler ();
00052 static int getPacket (char *userPtr , struct pcap_pkthdr *pkthdr,
00053               u_char * pkt);
00054 static int processPacket (Evl_Bridge_t * aBridge, Pkt_EthernetHdr_t * pkt,
00055               int length);
00056 static bool doRed (int pktSize, int numBytesInQueue, int maxAllowedBytes);
00057 
00058 /*AutomaticEnd***************************************************************/
00059 
00060 
00061 /**
00062   * \brief Used by the signal handlers. 
00063 
00064   * It's set by the Evl_Route
00065   * function, appears to be no other way to tell the signal handler
00066   * to use this argument.
00067   */
00068 
00069 static Evl_BridgeStats_t *globalStats;
00070 
00071 
00072 // very useful for debugging, so keep for now 
00073 // static Evl_Manager_t *globalMgr;
00074 
00075 
00076 /**
00077   * \brief  Actual firewall code.  Has synthetic input mode for testing.
00078   */
00079 
00080 int
00081 Evl_Route (Evl_Manager_t * aMgr,
00082        array_t * pktArray,
00083        int iBufSize,
00084        int ppCacheSize,
00085        int oBufSize,
00086        int actionBufSize,
00087        int maxNumPktsToRead,
00088        int numIterations,
00089        bool useSynthetic,
00090        array_t * inArray,
00091        array_t * outArray,
00092        double basicSlice,
00093        int getPacketsWeight,
00094        int computeActionsWeight,
00095        int performActionsWeight,
00096        int queuingWeight,
00097        int writePacketsWeight,
00098        array_t * ackSeqArray, Evl_BridgeStats_t ** statsPtr)
00099 {
00100   int i;
00101   // globalMgr = aMgr;
00102 
00103   Circbuf_t *actionBuf = Circbuf_Init (Pkt_ProcessPkt_t *, actionBufSize);
00104 
00105   Evl_Bridge_t *aBridge = (Evl_Bridge_t *) malloc (sizeof (Evl_Bridge_t));
00106   aMgr->bridge = aBridge;
00107   aBridge->iBuf = Circbuf_Init (Pkt_ProcessPkt_t *, iBufSize);
00108   aBridge->oBuf = Circbuf_Init (Pkt_EthernetHdr_t *, oBufSize);
00109   aBridge->inArray = !useSynthetic ? Pkt_InitLibPcapArray (inArray)
00110     : NIL (array_t);
00111   aBridge->outArray = !useSynthetic ? Pkt_InitLibNetArray (outArray) :
00112     NIL (array_t);
00113 
00114   aBridge->ppCache = Circbuf_Init (Pkt_ProcessPkt_t *, ppCacheSize);
00115   aBridge->stats = NIL (Evl_BridgeStats_t);
00116 
00117   Pkt_ProcessPkt_t *ppArray =
00118     (Pkt_ProcessPkt_t *) malloc (ppCacheSize * sizeof (Pkt_ProcessPkt_t));
00119   for (i = 0; i < ppCacheSize; i++)
00120     {
00121       ppArray[i].applicableRules = array_alloc (int, 0);
00122       Circbuf_Insert (Pkt_ProcessPkt_t *, aBridge->ppCache, (&(ppArray[i])));
00123     }
00124 
00125   Evl_BridgeStats_t *stats;
00126   stats = (Evl_BridgeStats_t *) malloc (sizeof (Evl_BridgeStats_t));
00127   if (statsPtr != NIL (Evl_BridgeStats_t *))
00128     {
00129       *statsPtr = stats;
00130     }
00131   globalStats = stats;
00132   aBridge->stats = stats;
00133   catchSignal (SIGINT, bridgeSigHandler);
00134 
00135   aMgr->qHeap = Evl_AllocateQueueHeap (aMgr->queueTable);
00136 
00137   u_int32_t slice = util_time_to_ticks (basicSlice);
00138   u_int32_t gpSlice = slice * getPacketsWeight;
00139   u_int32_t caSlice = slice * computeActionsWeight;
00140   u_int32_t paSlice = slice * performActionsWeight;
00141   u_int32_t qSlice = slice * queuingWeight;
00142 
00143   util_timing_set (&(stats->startTime));
00144   stats->numEntered = 0;
00145   stats->numExited = 0;
00146   stats->bytesWritten = 0;
00147   stats->numDroppedFullRuleCacheArray = 0;
00148   stats->numDroppedFullActionBuf = 0;
00149   stats->numDroppedFullQueue = 0;
00150   stats->numDroppedFullObuf = 0;
00151   stats->numDroppedFullIbuf = 0;
00152   stats->numDroppedBecauseOfAction = 0;
00153   stats->numDroppedAtWrite = 0;
00154   stats->numDroppedOverRate = 0;
00155   stats->numDroppedOverFlowRate = 0;
00156   (stats->firstPktRead).low = 0;
00157   (stats->firstPktRead).high = 0;
00158   (stats->lastPktWritten).low = 0;
00159   (stats->lastPktWritten).high = 0;
00160   stats->pcapInfo = aBridge->inArray;
00161 
00162   u_int32_t wpSlice = slice * writePacketsWeight;
00163 
00164   int loopForever = (numIterations == -1);
00165   while (loopForever || numIterations--)
00166     {
00167       evlGetPacketsLoop (maxNumPktsToRead, aBridge, pktArray, gpSlice,
00168              useSynthetic);
00169       // if ( stats->numEntered ) util_time( "delta time for call to get" );
00170       if (stats->numEntered >= maxNumPktsToRead
00171       && (stats->numEntered == stats->numExited))
00172     {
00173       break;
00174     }
00175       evlComputeActionsLoop (stats, aMgr, aBridge->iBuf, aBridge->ppCache,
00176                  caSlice, actionBuf);
00177       // if ( stats->numEntered ) util_time( "delta time for call to compute" );
00178       evlPerformActionsLoop (aMgr, aBridge, actionBuf, paSlice);
00179       // if ( stats->numEntered ) util_time( "delta time for call to actions" );
00180       evlQueuingLoop (aBridge->stats, aMgr, actionBuf, aBridge->ppCache,
00181               aBridge->oBuf, qSlice);
00182       // if ( stats->numEntered ) util_time( "delta time for call to que" );
00183       evlWritePacketsLoop (aBridge, wpSlice, useSynthetic, ackSeqArray);
00184       // if ( stats->numEntered ) util_time( "delta time for call to write" );
00185       if (useSynthetic)
00186     {
00187       // coreCheck( stats, aMgr, aBridge->iBuf, actionBuf, aBridge->oBuf );
00188     }
00189 
00190       // Q_Q_t *aQ;
00191       // Hash_Lookup( globalMgr->queueTable, (char *) "q0", ( char ** ) & aQ );
00192       // printf("q0 has %d entries\n", aQ->cosQ->numPktsInQueue );
00193 
00194     }
00195   util_timing_set (&(stats->finishTime));
00196   if (useSynthetic)
00197     {
00198       // coreCheck( stats, aMgr, aBridge->iBuf, actionBuf, aBridge->oBuf );
00199     }
00200 
00201   return 0;
00202   printf ("\n\n|oBuf| = %d\n|iBuf| = %d\n|actionBuf| =  %d\n"
00203       "Num entered\t= %d\n"
00204       "Num exited\t= %d\n"
00205       "Bytes written\t= %d\n"
00206       "Num Drop: FullRuleCacheArray\t= %d\n"
00207       "Num Drop: FullActionBuf\t= %d\n"
00208       "Num Drop: FullIbuf\t= %d\n"
00209       "Num Drop: FullObuf\t= %d\n"
00210       "Num Drop: FullQueue\t= %d\n"
00211       "Num Drop: Action\t= %d\n"
00212       "Num Drop: OverRate\t= %d\n"
00213       "Num Drop: OverFlowRate\t= %d\n",
00214       Circbuf_Num (aBridge->oBuf),
00215       Circbuf_Num (aBridge->iBuf),
00216       Circbuf_Num (actionBuf),
00217       stats->numEntered,
00218       stats->numExited,
00219       stats->bytesWritten,
00220       stats->numDroppedFullRuleCacheArray,
00221       stats->numDroppedFullActionBuf,
00222       stats->numDroppedFullIbuf,
00223       stats->numDroppedFullObuf,
00224       stats->numDroppedFullQueue,
00225       stats->numDroppedBecauseOfAction,
00226       stats->numDroppedOverRate, stats->numDroppedOverFlowRate);
00227   return 0;
00228 
00229   Q_Q_t *aQ;
00230   Hash_Lookup (aMgr->queueTable, (char *) "q0", (char **) &aQ);
00231   printf ("q0 has %d entries\n", aQ->cosQ->numPktsInQueue);
00232   Pkt_ProcessPkt_t *pp;
00233   while (1)
00234     {
00235       // pp = getQueueHead( aQ, NIL( int ) );
00236       if (!pp)
00237     break;
00238       pktPrint ("", pp->pkt);
00239     }
00240 
00241   Hash_Lookup (aMgr->queueTable, (char *) "q1", (char **) &aQ);
00242   printf ("q1 has %d entries\n", aQ->flowQ->numPktsInQueue);
00243   while (1)
00244     {
00245       // pp = getQueueHead( aQ, NIL( int ) );
00246       if (!pp)
00247     break;
00248       pktPrint ("", pp->pkt);
00249     }
00250 
00251   Hash_Lookup (aMgr->queueTable, (char *) "q2", (char **) &aQ);
00252   printf ("q2 has %d entries\n", aQ->cosQ->numPktsInQueue);
00253   while (1)
00254     {
00255       // pp = getQueueHead( aQ, NIL( int ) );
00256       if (!pp)
00257     break;
00258       pktPrint ("", pp->pkt);
00259     }
00260 
00261   return 0;
00262 }
00263 
00264 
00265 /**
00266   * \brief  Loop for getting packets off the input buffer
00267   * 
00268   */
00269 
00270 static void
00271 evlGetPacketsLoop (int maxNumPktsToRead,
00272            Evl_Bridge_t * aBridge,
00273            array_t * pktArray, u_int32_t slice, int useSynthetic)
00274 {
00275   int pktArraySize = (useSynthetic) ? array_n (pktArray) : 0;
00276   u_int32_t entryTime;
00277   rdtscl (entryTime);
00278   int numEnteredStartOfLoop;
00279 
00280   do
00281     {
00282       // numEnteredStartOfLoop = globalStats->numEntered;
00283       numEnteredStartOfLoop = aBridge->stats->numEntered;
00284       if (aBridge->stats->numEntered >= maxNumPktsToRead)
00285     {
00286       break;
00287     }
00288       if (Circbuf_IsFull (aBridge->iBuf))
00289     {
00290       break;
00291     }
00292       if (Circbuf_IsEmpty (aBridge->ppCache))
00293     {
00294       break;
00295     }
00296       if (useSynthetic)
00297     {
00298       Pkt_EthernetHdr_t *aPkt =
00299         array_fetch (Pkt_EthernetHdr_t *, pktArray,
00300              (aBridge->stats->numEntered++ % pktArraySize));
00301       Evl_BridgeInsertPktInIbuf (aBridge, aPkt);
00302 
00303       // Pkt_TcpHdr_t *aTcp = Pkt_EthernetExtractTcp( aPkt );
00304       // char *payload = Pkt_TcpHdrReadPayload( aTcp );
00305       // Pkt_IpHdr_t *aIp = Pkt_EthernetExtractIp( aPkt );
00306       // int dest = aIp->destIp;
00307       // pktPrint( "Just read in - ", aPkt );
00308 
00309     }
00310       else
00311     {
00312       // get live traffic
00313       int i;
00314       static int wastedCalls = 0;
00315       for (i = 0; i < array_n (aBridge->inArray); i++)
00316         {
00317           Pkt_LibPcap_t *aPcapObj =
00318         array_fetch (Pkt_LibPcap_t *, aBridge->inArray, i);
00319           aBridge->activeInputInterface = aPcapObj;
00320 
00321           /// \todo - figure out right params for pcap_dispatch
00322           // void (*dummyFunc)(u_char *, const pcap_pkthdr*, const u_char*);
00323           // dummyFunc = ( void(*)(u_char *, const pcap_pkthdr*, const u_char*) ) getPacket;
00324 
00325           // void (*dummyFunc)( );
00326           // void (*dummyFunc)(u_char*, const pcap_pkthdr* , const u_char*);
00327           // int (*dummyFunc)(char*, pcap_pkthdr*, u_char*);
00328           
00329           // dummyFunc = getPacket;
00330           // pcap_dispatch ( aPcapObj->p, 1, (void(*)(u_char *, const pcap_pkthdr*, const u_char*)) dummyFunc, (u_char *) aBridge );
00331           pcap_dispatch ( aPcapObj->p, 1, getPacket, (u_char *) aBridge );
00332 
00333         }
00334       if (numEnteredStartOfLoop == aBridge->stats->numEntered)
00335         {
00336           // pcap_dispatch didn't get any more packets, so break out
00337           wastedCalls++;
00338           break;
00339         }
00340       else
00341         {
00342           // printf("%d wasted calls before pickup\n", wastedCalls );
00343           wastedCalls = 0;
00344         }
00345     }
00346     }
00347   while (!sliceDone (entryTime, slice));    // do-while loop
00348 
00349 }
00350 
00351 
00352 /**
00353   * \brief Perform preprocessing
00354   *
00355   * Assumptions:
00356   *   - preprocessing rules appear before regular rules
00357   *   - no queueing rules in preprocessing
00358   */
00359 
00360 void
00361 preprocess (Pkt_ProcessPkt_t * pp, Evl_Manager_t * mgr)
00362 {
00363   pp->currentRule = 0;
00364   Evl_ComputeRuleSetForEth (pp, mgr);
00365 
00366   /// \todo: make sure space is being recovered correctly
00367   while (pp->currentRule < array_n (pp->applicableRules))
00368     {
00369       int ruleId = array_fetch (int, pp->applicableRules, pp->currentRule);
00370       if (ruleId >= mgr->numPreprocessRules)
00371     {
00372       // do not recover space, since this it the preprocess function
00373       // do reset the applicable rules, otherwise the same rule may
00374       // appear twice, e,g, on rule
00375       // tcp 1.2.3.4 any -> any any ()
00376       // packet with src 1.2.3.4 would appear twice
00377       array_reset( pp->applicableRules );
00378       return;
00379     }
00380       Evl_Action_t *action =
00381     array_fetch (Evl_Action_t *, mgr->actionArray, ruleId);
00382       assert (action->parsedAction->type != Rlp_ActionQueue_c);
00383       bool dropPkt = Evl_DoAction (action, mgr, mgr->bridge, pp);
00384       if (dropPkt == true)
00385     {
00386       recoverSpace (pp, mgr->bridge->ppCache);
00387       return;
00388     }
00389       pp->currentRule++;
00390     }
00391 }
00392 
00393 
00394 /** \brief  Loop for computing actions for packets */
00395 
00396 static void
00397 evlComputeActionsLoop (Evl_BridgeStats_t * stats,
00398                Evl_Manager_t * aMgr,
00399                Circbuf_t * iBuf,
00400                Circbuf_t * ppCache,
00401                u_int32_t slice, Circbuf_t * actionBuf)
00402 {
00403   u_int32_t entryTime;
00404 
00405   rdtscl (entryTime);
00406   do
00407     {
00408 
00409       if (Circbuf_IsEmpty (iBuf))
00410     {
00411       break;
00412     }
00413 
00414       Pkt_ProcessPkt_t *pp = Circbuf_Delete (Pkt_ProcessPkt_t *, iBuf);
00415       preprocess (pp, aMgr);
00416 
00417       Pkt_EthernetHdr_t *testPkt = pp->pkt;
00418       int testPktLength = pp->length;
00419 
00420       Evl_ComputeRuleSetForEth (pp, aMgr);
00421 
00422       // assert ( Circbuf_Num( ppCache ) == Circbuf_Num( ruleArrayCache ) );
00423       pp->pkt = testPkt;
00424       pp->length = testPktLength;
00425       pp->currentRule = 0;
00426       if (!Circbuf_IsFull (actionBuf))
00427     {
00428       Circbuf_Insert (Pkt_ProcessPkt_t *, actionBuf, pp);
00429     }
00430       else
00431     {
00432       // we have no place to put this pkt
00433       stats->numDroppedFullActionBuf++;
00434       pktPrint ("Dropped (FullActionBuf) - ", pp->pkt);
00435       recoverSpace (pp, ppCache);
00436       break;
00437     }
00438 
00439     }
00440   while (!sliceDone (entryTime, slice));
00441 }
00442 
00443 
00444 /**
00445   * \brief  Perform the computed actions on packets
00446   * 
00447   * Rules must be written in a special order:
00448   * (any nonqueueing rules in any order)
00449   * followed by
00450   * (queueing rules)
00451   * followed by 
00452   * (any nonqueueing rule in any order)
00453   * 
00454   * When we process rules, we first crank through
00455   * the nonqueueing rules.  as soon as we get a queuing rule
00456   * we push the packet in the corresponding queue, and 
00457   * from then on, it's the queue manager's resp
00458   * If the push is unsucc, we free the packet.
00459   * 
00460   * Later we come back to the remaining rules after the 
00461   * queueing subsystem is done with then.
00462   */
00463 
00464 static void
00465 evlPerformActionsLoop (Evl_Manager_t * aMgr,
00466                Evl_Bridge_t * aBridge,
00467                Circbuf_t * actionBuf, u_int32_t slice)
00468 {
00469   Evl_BridgeStats_t *stats = aBridge->stats;
00470   Pkt_ProcessPkt_t *pp;
00471   Q_Q_t *aQ;
00472   u_int32_t entryTime;
00473   rdtscl (entryTime);
00474 
00475   do
00476     {
00477       if (Circbuf_IsEmpty (actionBuf))
00478     {
00479       return;
00480     }
00481       pp = Circbuf_Delete (Pkt_ProcessPkt_t *, actionBuf);
00482       bool enQueued = false;
00483       bool dropPkt = false;
00484 
00485 
00486       int ruleId;
00487       Evl_Action_t *action = NIL (Evl_Action_t);
00488       while ((pp->currentRule < array_n (pp->applicableRules)) && !dropPkt)
00489     {
00490       ruleId = array_fetch (int, pp->applicableRules, pp->currentRule);
00491       action = array_fetch (Evl_Action_t *, aMgr->actionArray, ruleId);
00492       if (action->parsedAction->type != Rlp_ActionQueue_c)
00493         {
00494           dropPkt = Evl_DoAction (action, aMgr, aBridge, pp);
00495           pp->currentRule++;
00496         }
00497       else
00498         {           //  action->type == Rlp_ActionQueue_c
00499           if (action->queue == NIL (Q_Q_t))
00500         {
00501           Hash_Lookup (aMgr->queueTable,
00502                  (char *) action->parsedAction->queue,
00503                  (char **) &action->queue);
00504         }
00505           aQ = action->queue;
00506           // just insert it, let the taildrop take care of limits
00507           // we dont care about rates, that's for the exiting from the queue
00508           if (Evl_InsertPacketInQueue (aMgr, aQ, pp, action))
00509         {
00510           pp->currentRule++;
00511         }
00512           else
00513         {
00514           // drop the packet and continue 
00515           // Pkt_EthernetHdrFree( pp->pkt );
00516           stats->numDroppedFullQueue++;
00517           recoverSpace (pp, aBridge->ppCache);
00518           // this continue was missing led to core dumps in next check
00519           continue;
00520         }
00521           break;        // since now the packet is the responsibility of the queue manager
00522         }
00523     }           // while loop
00524 
00525       if (dropPkt)
00526     {
00527       stats->numDroppedBecauseOfAction++;
00528       recoverSpace (pp, aBridge->ppCache);
00529       /// \todo: cannot right now since it's in the syn traffic recycle array
00530       // Pkt_EthernetHdrFree( testPkt );
00531     }
00532       // tricky - missed the first two checks initially
00533       else if ((action != NIL (Evl_Action_t))
00534            && (action->parsedAction->type != Rlp_ActionQueue_c)
00535            && (!enQueued))
00536     {
00537       if (!Circbuf_IsFull (aBridge->oBuf))
00538         {
00539           Circbuf_Insert (Pkt_ProcessPkt_t *, aBridge->oBuf, pp);
00540           // circbuf_insert
00541           pktPrint ("Put into oBuf - ", pp->pkt);
00542         }
00543       else
00544         {
00545           stats->numDroppedFullObuf++;
00546           recoverSpace (pp, aBridge->ppCache);
00547         }
00548     }
00549       // else if -> if it's enqueued, it's the responsibility of the queue manager
00550     }
00551   while (!sliceDone (entryTime, slice));
00552 }
00553 
00554 
00555 /** \brief  Loop for moving packets through queues.  */
00556 
00557 static void
00558 evlQueuingLoop (Evl_BridgeStats_t * stats,
00559         Evl_Manager_t * aMgr,
00560         Circbuf_t * actionBuf,
00561         Circbuf_t * ppCache, Circbuf_t * oBuf, u_int32_t slice)
00562 {
00563   Q_Q_t *currentQueue;
00564   Q_Flow_t *aFlow = NIL (Q_Flow_t);
00565   Pkt_ProcessPkt_t *pp;
00566   double newRate;
00567   double newFlowRate;
00568   int classIndex;
00569 
00570   u_int32_t entryTime;
00571 
00572   int ruleId;
00573   Evl_Action_t *action;
00574 
00575   rdtscl (entryTime);
00576   do
00577     {
00578 
00579       if (Heap_Size (aMgr->qHeap) == 0)
00580     {
00581       break;
00582     }
00583 
00584       currentQueue = (Q_Q_t *) Heap_ReadMax (aMgr->qHeap);
00585       if (testQueueIsEmpty (currentQueue))
00586     {
00587       // it's empty so send it back all the way to the bottom of the queue
00588       currentQueue->currentPriority =
00589         currentQueue->currentPriority - (Heap_Size (aMgr->qHeap));
00590       Heap_Heapify (aMgr->qHeap);
00591       // by continuing, we may waste this whole slice if all queues are empty
00592       break;
00593     }
00594       pp = readQueueHead (currentQueue, &classIndex);
00595 
00596       int pktLength;
00597       aFlow = NIL (Q_Flow_t);
00598       if (currentQueue->maxRate != INFINITY)
00599     {
00600       // overall queue rate computation
00601       pktLength = pp->length;
00602       /// \todo: this assert fails when there's a mixture
00603       /// of our synthetically created packets and "real packets"
00604       /// it may be that we're to NTOH incorrectly, and that
00605       /// the stack has done it for us...
00606       
00607 
00608       // if it's an IP packet, the captured length should be the set length
00609       // assert( ! ( Pkt_EthernetReadL3Type( pp->pkt ) == Pkt_L3ProtIp_c ) ||
00610       //                ( pp->length == Pkt_EthernetPktHdrReadLength( pp->pkt ) ) );
00611 
00612       newRate = Q_ComputeRate (currentQueue->startOfCurrentWindow,
00613                    currentQueue->timeWindowDuration,
00614                    currentQueue->numBytesExitedInWindow,
00615                    pktLength);
00616 
00617       // printf("new Rate = %f\n", newRate );
00618       if (newRate > currentQueue->maxRate)
00619         {
00620           // we're not going to process this queue because it exceeeds the acceptable 
00621           // incoming rate for this queue
00622           updateQueuePriorities (currentQueue, aMgr->qHeap);
00623           break;        // we break so as to avoid getting trapped in a cycle, e.g., for the 1 queue case
00624         }
00625 
00626       // rate computation for individual flows
00627       if (currentQueue->type == Q_QueueTypeFlow_c)
00628         {
00629           // check if the individual flow's rate will be too high
00630           aFlow = Q_DrrReadFlow (currentQueue->flowQ, pp->pkt);
00631 
00632           // this check is needed if this packets was the last representative
00633           // of its flow - in this case, we ignore its rate computation
00634           if (aFlow != NIL (Q_Flow_t))
00635         {
00636           /// \todo - implement fields for flow structure
00637           // double newFlowRate = Q_ComputeRate( aFlow->startOfCurrentWindow, currentQueue->timeWindowDuration, aFlow->numBytesExitedInDuration, pp->pkt );
00638           if (newFlowRate > currentQueue->flowMaxRate)
00639             {
00640               // we're not going to process this flow because it exceeeds 
00641               // the acceptable incoming rate for this queue
00642               updateQueuePriorities (currentQueue, aMgr->qHeap);
00643               /// \todo - are these breaks the best thing to do?
00644               break;    // we break so as to avoid getting trapped in a cycle, e.g., for the 1 queue case
00645             }
00646         }
00647         }
00648     }
00649 
00650       // we're satisfied that pp is acceptable from a rate perspective, 
00651       // so now we get the queue head, move up the packet rule
00652       pp = getQueueHead (currentQueue, aFlow, newRate, &classIndex);
00653       util_timing_set (&stats->lastPktWritten);
00654       // and update the rate - this is the only place the rate should be updated, as
00655       // it's a function of the rate at which packets EXIT the queue
00656 
00657       if (pp->currentRule < array_n (pp->applicableRules))
00658     {
00659       ruleId = array_fetch (int, pp->applicableRules, pp->currentRule);
00660       action = array_fetch (Evl_Action_t *, aMgr->actionArray, ruleId);
00661       if (action->parsedAction->type == Rlp_ActionQueue_c)
00662         {
00663           if (action->queue == NIL (Q_Q_t))
00664         {
00665           Hash_Lookup (aMgr->queueTable,
00666                  (char *) action->parsedAction->queue,
00667                  (char **) &action->queue);
00668         }
00669           if (Evl_InsertPacketInQueue (aMgr, action->queue, pp, action))
00670         {
00671           pp->currentRule++;
00672         }
00673           else
00674         {
00675           // drop the packet and continue 
00676           stats->numDroppedFullQueue++;
00677           recoverSpace (pp, ppCache);
00678           // this continue was missing led to core dumps in next check
00679           continue;
00680         }
00681         }
00682       else
00683         {
00684           // it's not queueing rule, so put it in the action buffer
00685           if (!Circbuf_IsFull (actionBuf))
00686         {
00687           Circbuf_Insert (Pkt_ProcessPkt_t *, actionBuf, pp);
00688         }
00689           else
00690         {
00691           stats->numDroppedFullActionBuf++;
00692           recoverSpace (pp, ppCache);
00693         }
00694         }
00695     }
00696       else
00697     {
00698       // must have ( pp->currentRule == array_n( pp->applicableRules ) ) 
00699       // => we've applied all the queue rules to this packet, and there are not any more 
00700       // queue rules so put pp and applicableRules in the free lists, and move 
00701       // the packet to the output buffer
00702       if (!Circbuf_IsFull (oBuf))
00703         {
00704           Circbuf_Insert (Pkt_ProcessPkt_t *, oBuf, pp);
00705         }
00706       else
00707         {
00708           // should sliently discard the packet
00709           stats->numDroppedFullObuf++;
00710           recoverSpace (pp, ppCache);
00711           break;
00712         }
00713     }
00714       updateQueuePriorities (currentQueue, aMgr->qHeap);
00715 
00716     }
00717   while (!sliceDone (entryTime, slice));
00718 }
00719 
00720 
00721 /** \brief  Loop for writing out packets */
00722 
00723 static void
00724 evlWritePacketsLoop (Evl_Bridge_t * aBridge,
00725              u_int32_t slice, int useSynthetic, array_t * ackSeqArray)
00726 {
00727   Evl_BridgeStats_t *stats = aBridge->stats;
00728   u_int32_t entryTime;
00729   /// \todo - we're using the first interface as the default output, 
00730   /// need to document this somewhere
00731   Pkt_LibNet_t *defaultOutput = NIL (Pkt_LibNet_t);
00732   if (useSynthetic == false)
00733     {
00734       defaultOutput = array_fetch (Pkt_LibNet_t *, aBridge->outArray, 0);
00735     }
00736 
00737   rdtscl (entryTime);
00738   do
00739     {
00740       if (Circbuf_IsEmpty (aBridge->oBuf))
00741     {
00742       break;
00743     }
00744       Pkt_ProcessPkt_t *pp =
00745     Circbuf_Delete (Pkt_ProcessPkt_t *, aBridge->oBuf);
00746       // need to update stats before we return pp to the cache
00747       stats->bytesWritten += pp->length;
00748       if (ackSeqArray)
00749     {
00750       array_insert_last (Pkt_EthernetHdr_t *, ackSeqArray, pp->pkt);
00751     }
00752       if (useSynthetic == false)
00753     {
00754       // we're actually dumping the packet on the line
00755       /*
00756          assert( ( Pkt_EthernetReadL3Type( pp->pkt ) != Pkt_L3ProtIp_c ) ||
00757          ( Pkt_EthernetExtractIp( pp->pkt )->protocol != Pkt_L4ProtTcp_c ) ||
00758          ( (pp->length == 60 ) && 60 >= Pkt_EthernetPktHdrReadLength( pp->pkt ) ) ||
00759          ( pp->length == Pkt_EthernetPktHdrReadLength( pp->pkt ) ) );
00760        */
00761 
00762       Pkt_LibNet_t *outObj = (pp->outIf != NIL (Pkt_LibNet_t)) ?
00763         pp->outIf : defaultOutput;
00764       if (0 < Pkt_EthPktWrite (pp->pkt, pp->length, outObj))
00765         {
00766           stats->numExited++;
00767         }
00768       else
00769         {
00770           stats->numDroppedAtWrite++;
00771         }
00772       recoverSpace (pp, aBridge->ppCache);
00773     }
00774 
00775       util_timing_t currentTime;
00776       util_timing_set (&currentTime);
00777       double delta =
00778     util_timing_secs (currentTime) - util_timing_secs (stats->startTime);
00779       double rate  = 8.0 * stats->bytesWritten / delta;
00780       // printf("evlWritePacketsLoop: Rate going out is %.1f\n", rate );
00781 
00782       // Pkt_EthernetHdrFree( writePkt );
00783     }
00784   while (!sliceDone (entryTime, slice));
00785 }
00786 
00787 
00788 /**
00789   * \brief  Add a packet (actually Pkt_ProcessPkt_t *)  to a q - may drop
00790   * if resources are overused.  
00791   *
00792   * Return 1 if succ, 0 if dropped.
00793   */
00794 
00795 int
00796 Evl_InsertPacketInQueue (Evl_Manager_t * aMgr,
00797              Q_Q_t * aQ,
00798              Pkt_ProcessPkt_t * pp, Evl_Action_t * action)
00799 {
00800   int pktSize = Pkt_EthernetPktHdrReadLength (pp->pkt);
00801   Hash_Lookup (aMgr->queueTable, (char *) action->queue, (char **) &aQ);
00802 
00803   bool checkEntireQueue = false;
00804 
00805   if (aQ->maxAllowedBytes == 0)
00806     {
00807       // there's no limit on size
00808       checkEntireQueue = true;
00809     }
00810   else if (aQ->dropMethod == Q_DropTail_c)
00811     {
00812       checkEntireQueue =
00813     ((pktSize + aQ->numBytesInQueue) <= aQ->maxAllowedBytes);
00814     }
00815   else
00816     {
00817       assert (aQ->dropMethod == Q_DropRed_c);
00818 
00819       /*
00820        * RED based drop - no drop until half capacity is used.
00821        * After that, drop prob is $e^{(1/2 - m/M)} / ( e^{1/2} - 1)$, 
00822        * where m = current use,  M = max allowed
00823        * This is 0 at 0.5, and tends to 1 as m -> M
00824        *
00825        */
00826 
00827       if (2 * (pktSize + aQ->numBytesInQueue) < aQ->maxAllowedBytes)
00828     {
00829       // fewer than 0.5 the max byte limit, insert safely
00830       checkEntireQueue = true;
00831     }
00832       checkEntireQueue =
00833     doRed (pktSize, aQ->numBytesInQueue, aQ->maxAllowedBytes);
00834     }
00835 
00836   if (!checkEntireQueue)
00837     {
00838       return 0;
00839     }
00840 
00841   if (aQ->type != Q_QueueTypeFlow_c)
00842     {
00843       queueInsertPp (aQ, pp, action->parsedAction->classIndex, 1);
00844       return 1;
00845     }
00846 
00847   // this is a flow-based queue, and we have not exceeded any of the
00848   // global bounds on the queue size => focus on individual queue
00849   bool checkFlowQueue = false;
00850   Q_Drr_t *aDrr = aQ->flowQ;
00851   int numFlowsInQueue = Q_DrrNumFlows (aDrr);
00852   if ((aQ->maxFlows != -1) && (numFlowsInQueue >= aQ->maxFlows))
00853     {
00854       checkFlowQueue = false;
00855     }
00856   else
00857     {
00858       checkFlowQueue = true;
00859     }
00860 
00861   if (checkFlowQueue && (aQ->maxBytesPerFlow != INFINITY))
00862     {
00863       Q_Flow_t *aFlow;
00864       // when the first packet from the flow is entering, the 
00865       // lookup fails
00866       bool succ = Hash_Lookup (aDrr->flowToQueueTable,
00867                  (char *) pp->pkt,
00868                  (char **) &aFlow);
00869       int bytesAlreadyInQueue = succ ? aFlow->numBytes : 0;
00870       if (aQ->flowDropMethod == Q_DropTail_c)
00871     {
00872       if (bytesAlreadyInQueue + pktSize > aQ->maxBytesPerFlow)
00873         {
00874           checkFlowQueue = false;
00875         }
00876     }
00877       else
00878     {
00879       assert (aQ->flowDropMethod == Q_DropRed_c);
00880       checkFlowQueue =
00881         doRed (pktSize, bytesAlreadyInQueue, aQ->maxBytesPerFlow);
00882     }
00883     }
00884 
00885   /// \todo: get to buffer limits for individual queues later
00886   if (checkFlowQueue == true)
00887     {
00888       queueInsertPp (aQ, pp, action->parsedAction->classIndex, 1);
00889       return 1;
00890     }
00891   else
00892     {
00893       return 0;
00894     }
00895 
00896 
00897   assert (0);           // never get here
00898 }
00899 
00900 
00901 /**
00902   * \brief  Recover buffer entries
00903   * 
00904   */
00905 
00906 static inline void
00907 recoverSpace (Pkt_ProcessPkt_t * pp, Circbuf_t * ppCache)
00908 {
00909   // printf("Recovering space - pp:%p, pkt:%p\n", pp, pp->pkt );
00910   array_reset (pp->applicableRules);
00911   pp->outIf = NIL (Pkt_LibNet_t);
00912 
00913   // Eth_EthPktFree( pp->pkt );
00914   Circbuf_Insert (Pkt_ProcessPkt_t *, ppCache, pp);
00915 }
00916 
00917 
00918 /**
00919   * \brief  Update priorities for queues
00920   * 
00921   * The update strategy below has the problem that the lowest priority keeps 
00922   * decreasing, need to boost all back to near 0 when close in on -MAXINT
00923   * 
00924   */
00925 
00926 static inline void
00927 updateQueuePriorities (Q_Q_t * currentQueue, Heap_t * qHeap)
00928 {
00929   currentQueue->currentPriority -= (Heap_Size (qHeap));
00930   if (!testQueueIsEmpty (currentQueue))
00931     {
00932       currentQueue->currentPriority += currentQueue->assignedPriority;
00933     }
00934   Heap_Heapify (qHeap);
00935 }
00936 
00937 
00938 /**
00939   * \brief  Quit if more time has passed than slice
00940   * 
00941   * This is an approximation,
00942   * as we assume if low-counter has wrapped around we have to stop.
00943   * 
00944   * We stop the input work when exitTime has wrapped around,
00945   * or when exitTime - entryTime is larger than threshold.
00946   * 
00947   * The logic for exiting on wraparound is that it'll be fairly rare
00948   * and will average out over the different operations.
00949   * 
00950   */
00951 
00952 static inline bool
00953 sliceDone (u_int32_t entryTime, u_int32_t slice)
00954 {
00955   u_int32_t exitTime;
00956   rdtscl (exitTime);
00957   if ((exitTime < entryTime) || ((exitTime - entryTime) > slice))
00958     {
00959       return true;
00960     }
00961   return false;
00962 }
00963 
00964 
00965 /**
00966   * \brief  Routine for testing the manager structure built by 
00967   * Evl_BuildManager
00968   * 
00969   */
00970 
00971 int
00972 Evl_TestManager (Evl_Manager_t * aMgr)
00973 {
00974   Evl_L4Flow_t *t1;
00975 
00976   t1 = (Evl_L4Flow_t *) malloc (sizeof (Evl_L4Flow_t));
00977   t1->destPort = 80;
00978   t1->srcPort = 80;
00979   t1->destIp = Rlp_DotToInt ("192.168.1.1");
00980   t1->srcIp = 0x00000000;
00981 
00982   int rulesIndex = Evl_ComputeL7RuleSet (aMgr->tcpMgr->destPortRuleTable, t1);
00983   var_set_t *rules = aMgr->tcpMgr->destPortRuleTable->ruleSets[rulesIndex];
00984 
00985   printf ("Results of lookup:\n");
00986   int i;
00987   for (i = 0; i < aMgr->numAllRules; i++)
00988     {
00989       char *testRule = array_fetch (char *, aMgr->rawRules, i);
00990       if (var_set_get_elt (rules, i))
00991     {
00992       printf ("Flow %x %x %x %x satisfies %s\n",
00993           t1->destPort, t1->srcPort, t1->destIp, t1->srcIp, testRule);
00994     }
00995     }
00996   return 0;
00997 }
00998 
00999 
01000 /**
01001   * \brief  Test the build prefix automaton routine
01002   * 
01003   */
01004 
01005 static int 
01006 testBuildPrefixAutomaton ()
01007 {
01008   util_byte_array_t a;
01009   util_byte_array_t b;
01010   util_byte_array_t c;
01011 
01012   a.bytes = "abc";
01013   b.bytes = "abb";
01014   c.bytes = "acb";
01015 
01016   a.length = 3;
01017   b.length = 3;
01018   c.length = 3;
01019 
01020   array_t *byteArrayArray = array_alloc (util_byte_array_t *, 0);
01021 
01022   array_insert_last (util_byte_array_t *, byteArrayArray, &a);
01023   array_insert_last (util_byte_array_t *, byteArrayArray, &b);
01024   array_insert_last (util_byte_array_t *, byteArrayArray, &c);
01025 
01026   Evl_Fsm_t *anFsm = Evl_BuildPrefixAutomaton (byteArrayArray);
01027   Evl_FsmPrint (anFsm);
01028 
01029   return 0;
01030 }
01031 
01032 
01033 /**
01034   * \brief  Catch signals
01035   * 
01036   */
01037 
01038 static int
01039 catchSignal (int signo, handler_t handler)
01040 {
01041   struct sigaction action;
01042 
01043   action.sa_handler = ( void (*)(int) ) handler;
01044   sigemptyset (&action.sa_mask);
01045   action.sa_flags = 0;
01046 
01047   if (sigaction (signo, &action, NIL (struct sigaction)))
01048     {
01049       return -1;
01050     }
01051   return 1;
01052 }
01053 
01054 
01055 /**
01056   * \brief  Perform action on packet. Return 1 if packet is to be dropped, 
01057   * 0 otherwise.
01058   * 
01059   * Must not be called with queuing actions.
01060   * 
01061   */
01062 
01063 bool
01064 Evl_DoAction (Evl_Action_t * action,
01065           Evl_Manager_t * mgr,
01066           Evl_Bridge_t * bridge, Pkt_ProcessPkt_t * pp)
01067 {
01068   switch (action->parsedAction->type)
01069     {
01070     case Rlp_ActionDrop_c:
01071       /// \todo: need to figure out how to drop this packet
01072       /// if we're not doing synthetic runs
01073       // Pkt_Free( testPkt );
01074       return 1;
01075     case Rlp_ActionRoute_c:
01076       Evl_RoutePkt (action, bridge, pp);
01077       break;
01078     case Rlp_ActionUscript_c:
01079       Evl_UscriptAction (action->parsedAction, mgr, pp);
01080       break;
01081     case Rlp_ActionUcode_c:
01082       // convention is that calling functions returns 1 if pkt is
01083       // to be dropped 
01084       return Evl_UcodeAction (action->parsedAction, mgr, pp);
01085     default:
01086       printf ("Panic: unknown type of action\n");
01087       assert (0);
01088     }               // switch
01089   return 0;
01090 }
01091 
01092 
01093 /**
01094   * \brief check if a queue is empty - works for both types of queues
01095   */
01096 
01097 static bool
01098 testQueueIsEmpty (Q_Q_t * currentQueue)
01099 {
01100   if (((currentQueue->type == Q_QueueTypeCos_c)
01101        && Q_CosTestIsEmpty (currentQueue->cosQ))
01102       ||
01103       (((currentQueue->type == Q_QueueTypeFlow_c)
01104     && Q_DrrTestIsEmpty (currentQueue->flowQ))))
01105     {
01106       return true;
01107     }
01108   else
01109     {
01110       return false;
01111     }
01112 }
01113 
01114 
01115 /**
01116   * \brief Read the head of the queue - works for both types of queues. 
01117   * 
01118   * Does not change the state of the queue.
01119   */
01120 
01121 static Pkt_ProcessPkt_t *
01122 readQueueHead (Q_Q_t * currentQueue, int *classPtr)
01123 {
01124   Pkt_ProcessPkt_t *pp = (currentQueue->type == Q_QueueTypeCos_c) ?
01125     Q_CosReadHead (currentQueue->cosQ,
01126            classPtr) : Q_DrrReadHead (currentQueue->flowQ);
01127 
01128   return pp;
01129 }
01130 
01131 
01132 /**
01133   * \brief Get the head of the queue - works for both types of queues
01134   */
01135 
01136 static Pkt_ProcessPkt_t *
01137 getQueueHead (Q_Q_t * aQ, Q_Flow_t * aFlow, double newRate, int *classPtr)
01138 {
01139   Pkt_ProcessPkt_t *pp;
01140 
01141   aQ->currentRate = newRate;
01142 
01143   pp = (aQ->type == Q_QueueTypeCos_c) ?
01144     Q_CosHead (aQ->cosQ, classPtr) : Q_DrrHead (aQ->flowQ);
01145 
01146   if (pp != NIL (Pkt_ProcessPkt_t))
01147     {
01148       int length = Pkt_EthernetPktHdrReadLength (pp->pkt);
01149       aQ->numPktsInQueue--;
01150       aQ->numBytesInQueue -= length;
01151       aQ->numBytesExited += length;
01152 
01153       updateRateInfo (&aQ->startOfCurrentWindow,
01154               aQ->timeWindowDuration,
01155               &aQ->numBytesExitedInWindow, length);
01156 
01157       // aFlow may be nil if this is the first time this 
01158       // flow is seen
01159       if (aFlow != NIL (Q_Flow_t))
01160     {
01161       // update the flow's rate info
01162       updateRateInfo (&aFlow->startOfCurrentWindow,
01163               aQ->timeWindowDuration,
01164               &aFlow->numBytesExitedInWindow, length);
01165     }
01166     }
01167   return pp;
01168 }
01169 
01170 
01171 /**
01172   * \brief Update rate information
01173   */
01174 
01175 static void
01176 updateRateInfo (util_timing_t * startOfCurrentWindow,
01177         double timeWindowDuration,
01178         double *numBytesExitedInWindow, int length)
01179 {
01180   double startOfCurrentWindowDbl = util_timing_secs (*startOfCurrentWindow);
01181 
01182   // now get current time
01183   util_timing_t currentTimeUtil;
01184   util_timing_set (&currentTimeUtil);
01185   double currentTime = util_timing_secs (currentTimeUtil);
01186 
01187   // see if the difference from when current window started
01188   // is greater than the window duration time; if so reset the bytes out counter
01189   // and the window start time.
01190   if ((currentTime - startOfCurrentWindowDbl) > timeWindowDuration)
01191     {
01192       *numBytesExitedInWindow = length;
01193       *startOfCurrentWindow = currentTimeUtil;
01194     }
01195   else
01196     {
01197       *numBytesExitedInWindow = length + *numBytesExitedInWindow;
01198     }
01199 }
01200 
01201 
01202 /** \brief insert pp into a queue - works for all types of queues */
01203 
01204 static int
01205 queueInsertPp (Q_Q_t * aQ, Pkt_ProcessPkt_t * pp, int classIndex, bool insertAtEnd)
01206 {
01207   int retcode;
01208 
01209   int length = Pkt_EthernetPktHdrReadLength (pp->pkt);
01210 
01211   if (aQ->type == Q_QueueTypeCos_c)
01212     {
01213       retcode = Q_CosInsertPpBeginEnd (aQ->cosQ, pp, classIndex, insertAtEnd);
01214     }
01215   else if (aQ->type == Q_QueueTypeFlow_c)
01216     {
01217       retcode = Q_DrrInsertPpBeginEnd (aQ->flowQ, pp, insertAtEnd);
01218     }
01219   else
01220     {
01221       assert (0);
01222     }
01223   if (retcode)
01224     {
01225       aQ->numPktsProcessed++;
01226       aQ->numPktsInQueue++;
01227       aQ->numBytesInQueue += length;
01228       aQ->numBytesEntered += length;
01229     }
01230   return retcode;
01231 }
01232 
01233 
01234 /** \brief Trivial print routine for debugging */
01235 
01236 static void
01237 pktPrint (char *mesg, Pkt_EthernetHdr_t * pkt)
01238 {
01239   return;
01240   Pkt_IpHdr_t *aIp = Pkt_EthernetExtractIp (pkt);
01241   int dest = aIp->destIp;
01242   Pkt_TcpHdr_t *aTcp = Pkt_EthernetExtractTcp (pkt);
01243   char *payload = Pkt_TcpHdrReadPayload (aTcp);
01244   printf ("%s pkt %p: payload= %c, destIp = %d\n", mesg, pkt, *payload, dest);
01245 }
01246 
01247 
01248 /** \brief Core assertion checked */
01249 
01250 static void 
01251 coreCheck (Evl_BridgeStats_t * stats,
01252        Evl_Manager_t * aMgr,
01253        Circbuf_t * iBuf, Circbuf_t * actionBuf, Circbuf_t * oBuf)
01254 {
01255   int pktsInQueue = 0;
01256   char *qName;
01257   Q_Q_t *aQ;
01258   st_generator *stgen;
01259 
01260   st_foreach_item (aMgr->queueTable, stgen, (char **) &qName, (char **) &aQ)
01261   {
01262     pktsInQueue += aQ->numPktsInQueue;
01263   }
01264   // /*
01265   printf ("\n\n"
01266       "|oBuf| = %d\n"
01267       "|iBuf| = %d\n"
01268       "|actionBuf| = %d\n"
01269       "Num entered\t= %d\n"
01270       "Num exited\t= %d\n"
01271       "Num Drop: FullRuleCacheArray\t= %d\n"
01272       "Num Drop: FullActionBuf\t= %d\n"
01273       "Num Drop: FullObuf\t= %d\n"
01274       "Num Drop: FullQueue\t= %d\n"
01275       "Num Drop: Action\t= %d\n"
01276       "|Enqueued Pkts|\t= %d\n",
01277       Circbuf_Num (oBuf),
01278       Circbuf_Num (iBuf),
01279       Circbuf_Num (actionBuf),
01280       stats->numEntered,
01281       stats->numExited,
01282       stats->numDroppedFullRuleCacheArray,
01283       stats->numDroppedFullActionBuf,
01284       stats->numDroppedFullObuf,
01285       stats->numDroppedFullQueue,
01286       stats->numDroppedBecauseOfAction, pktsInQueue);
01287   // */
01288   assert (stats->numDroppedBecauseOfAction +
01289       pktsInQueue +
01290       Circbuf_Num (oBuf) +
01291       Circbuf_Num (iBuf) +
01292       Circbuf_Num (actionBuf) +
01293       stats->numExited +
01294       stats->numDroppedFullRuleCacheArray +
01295       stats->numDroppedFullActionBuf +
01296       stats->numDroppedFullQueue +
01297       stats->numDroppedFullObuf +
01298       stats->numDroppedOverRate +
01299       stats->numDroppedOverFlowRate +
01300       stats->numDroppedFullObuf == stats->numEntered);
01301 
01302   return;
01303 
01304   Hash_Lookup (aMgr->queueTable, (char *) "q0", (char **) &aQ);
01305   printf ("q0 has %d entries\n", aQ->cosQ->numPktsInQueue);
01306 
01307   Hash_Lookup (aMgr->queueTable, (char *) "q1", (char **) &aQ);
01308   printf ("q1 has %d entries\n", aQ->flowQ->numPktsInQueue);
01309 
01310   Hash_Lookup (aMgr->queueTable, (char *) "q2", (char **) &aQ);
01311   printf ("q2 has %d entries\n", aQ->cosQ->numPktsInQueue);
01312 
01313   // code to print the state of the queue
01314   // changes state of queue!
01315   /* 
01316      Pkt_ProcessPkt_t *pp;
01317      while ( 1 ) {
01318      pp = getQueueHead( aQ, NIL( int ) );
01319      if ( !pp ) break;
01320      pktPrint( "", pp->pkt );
01321      } 
01322    */
01323 
01324 }
01325 
01326 
01327 /**
01328   * \brief  CTRL-C Signal handler for bridge loop
01329   */
01330 
01331 static void
01332 bridgeSigHandler ()
01333 {
01334   /// \todo: figure out some way to pass an argument to a signal handler
01335   /// on readinging more, it seems impossible
01336   static int previousCount = 0;
01337   printf ("Num packets succ transmitted since last ^C = %d\n",
01338       globalStats->numExited - previousCount);
01339   previousCount = globalStats->numExited;;
01340   printf ("\nBridge stats:\n"
01341       "Num entered\t= %d\n"
01342       "Num exited\t= %d\n"
01343       "Bytes written\t= %d\n"
01344       "Num Drop: Actual Write\t= %d\n"
01345       "Num Drop: FullRuleCacheArray\t= %d\n"
01346       "Num Drop: FullActionBuf\t= %d\n"
01347       "Num Drop: FullIbuf\t= %d\n"
01348       "Num Drop: FullObuf\t= %d\n"
01349       "Num Drop: FullQueue\t= %d\n"
01350       "Num Drop: Action\t= %d\n"
01351       "Num Drop: OverRate\t= %d\n"
01352       "Num Drop: OverFlowRate\t= %d\n",
01353       globalStats->numEntered,
01354       globalStats->numExited,
01355       globalStats->bytesWritten,
01356       globalStats->numDroppedAtWrite,
01357       globalStats->numDroppedFullRuleCacheArray,
01358       globalStats->numDroppedFullActionBuf,
01359       globalStats->numDroppedFullIbuf,
01360       globalStats->numDroppedFullObuf,
01361       globalStats->numDroppedFullQueue,
01362       globalStats->numDroppedBecauseOfAction,
01363       globalStats->numDroppedOverRate,
01364       globalStats->numDroppedOverFlowRate);
01365 
01366   struct pcap_stat pcapStats;
01367   int i;
01368   for (i = 0; i < array_n (globalStats->pcapInfo); i++)
01369     {
01370       Pkt_LibPcap_t *pcapObj =
01371     array_fetch (Pkt_LibPcap_t *, globalStats->pcapInfo, i);
01372       printf ("Stats for %s\n", pcapObj->interfaceName);
01373       pcap_stats (pcapObj->p, &pcapStats);
01374       printf ("ps_recv:%d\tps_drop:%d\n", pcapStats.ps_recv,
01375           pcapStats.ps_drop);
01376       // packet_ring_stats (pcapObj->p, -1);
01377     }
01378   // Q_Q_t *aQ;
01379   // Hash_Lookup( globalMgr->queueTable, (char *) "q0", ( char ** ) & aQ );
01380   // printf("q0 has %d entries\n", aQ->cosQ->numPktsInQueue );
01381   return;
01382 }
01383 
01384 
01385 /**
01386   * \brief  Routine called by pcap_dispatch
01387   */
01388 
01389 static int
01390 getPacket (char *userPtr , struct pcap_pkthdr *pkthdr, u_char * pkt)
01391 {
01392   Pkt_EthernetHdr_t *aPkt = (Pkt_EthernetHdr_t *) pkt;
01393   Evl_Bridge_t *aBridge = (Evl_Bridge_t *) userPtr;
01394 
01395   int code = processPacket (aBridge, aPkt, pkthdr->len);
01396   return code;
01397 }
01398 
01399 
01400 /** \brief  Function that actually processes packets */
01401 
01402 static int
01403 processPacket (Evl_Bridge_t * aBridge, Pkt_EthernetHdr_t * pkt, int length)
01404 {
01405   Circbuf_t *iBuf = aBridge->iBuf;
01406   Pkt_ProcessPkt_t *pp;
01407 
01408   if (Circbuf_IsFull (iBuf))
01409     {
01410       aBridge->stats->numDroppedFullIbuf++;
01411       return 0;         // input buffer is full
01412       pktPrint ("Dropped (Full input buffer array) - ", pkt);
01413     }
01414   if (Circbuf_IsEmpty (aBridge->ppCache))
01415     {
01416       pktPrint ("Dropped (Empty pp cache) - ", pkt);
01417       return 0;
01418     }
01419   pp = Circbuf_Delete (Pkt_ProcessPkt_t *, aBridge->ppCache);
01420   pp->pkt = pkt;
01421   pp->length = length;
01422   pp->inIf = aBridge->activeInputInterface;
01423   // printf("Got packet, number %d\n", aBridge->stats->numEntered );
01424 
01425   /// \todo when does pcap/socket already do this for us???
01426   Pkt_NTOH (pkt);
01427   Circbuf_Insert (Pkt_ProcessPkt_t *, iBuf, pp);
01428   aBridge->stats->numEntered++;
01429   return 1;
01430 }
01431 
01432 
01433 /** \brief Implement Random Early Discard */
01434 
01435 static bool
01436 doRed (int pktSize, int numBytesInQueue, int maxAllowedBytes)
01437 {
01438   bool checkEntireQueue;
01439 
01440   if ((pktSize + numBytesInQueue) > maxAllowedBytes)
01441     {
01442       // past the queue size limit
01443       checkEntireQueue = false;
01444     }
01445   else
01446     {
01447       // do RED
01448       double fraction =
01449     ((double) pktSize + numBytesInQueue) / (double) maxAllowedBytes;
01450       /// \todo: use lookup tables for this
01451       double dropProb = (exp (fraction - 0.5) - 1.0) / (exp (0.5) - 1.0);
01452       double unitRand = util_unit_rand ();
01453       if (unitRand < dropProb)
01454     {
01455       checkEntireQueue = false;
01456     }
01457       else
01458     {
01459       checkEntireQueue = true;
01460     }
01461     }
01462   return checkEntireQueue;
01463 }
01464 
01465 
01466 /**
01467   * \brief Insert a packet into the bridge iBuf, meant
01468   * to support scripts/code adding control/reset packets.
01469   */
01470 
01471 void
01472 Evl_BridgeInsertPktInIbuf (Evl_Bridge_t * aBridge, Pkt_EthernetHdr_t * aPkt)
01473 {
01474   if (Circbuf_IsEmpty (aBridge->ppCache))
01475     {
01476       printf ("WARNING: Cannot send pkt, pp cache is empty\n");
01477       return;
01478     }
01479   if (Circbuf_IsFull (aBridge->iBuf))
01480     {
01481       printf ("WARNING: Cannot send pkt, ibuf is full\n");
01482       return;
01483     }
01484 
01485   int length = Pkt_EthernetPktHdrReadLength (aPkt);
01486   Pkt_ProcessPkt_t *pp =
01487     Circbuf_Delete (Pkt_ProcessPkt_t *, aBridge->ppCache);
01488   pp->pkt = aPkt;
01489   pp->length = length;
01490   pp->inIf = NIL (Pkt_LibPcap_t);
01491 
01492   Circbuf_Insert (Pkt_ProcessPkt_t *, aBridge->iBuf, pp);
01493   if (((aBridge->stats->firstPktRead).low == 0)
01494       && ((aBridge->stats->firstPktRead).high == 0))
01495     {
01496       util_timing_set (&aBridge->stats->firstPktRead);
01497     }
01498 }