Azinix

evl.h

Go to the documentation of this file.
00001 /** \file  evl.h
00002 
00003   \brief Rule evaluation data structures
00004 */
00005 
00006 #ifndef _EVL
00007 #define _EVL
00008 
00009 #ifdef __cplusplus
00010 extern "C" {
00011 #endif
00012 
00013 #include "tcl.h"
00014 #include "nm.h"
00015 #include "pkt.h"
00016 #include "rlp.h"
00017 #include "q.h"
00018 #include "bdd.h"
00019 
00020 
00021 #define my_isupper( c ) ( ( c < 91 ) && ( c > 64 ) )
00022 #define my_uppertolower( c ) ( ( c + 32 ) )
00023 
00024 
00025 /** \brief Use this global to set how long the strings have to 
00026 be before we add them to the FSM.
00027 */
00028 
00029 static const int Evl_MinLengthFsmString = 3;
00030 
00031 /** \brief  Macro for memcmp without a function call.
00032   
00033   Result is in tmpIndex,
00034   which is 0 iff the two are equal.
00035   
00036 */
00037 
00038 
00039 #define EVL_MEMCMP( s1, s2, numBytes, match ) \
00040             while ( numBytes-- && ( s1[numBytes] == s2[numBytes] ) ); \
00041             match = ( numBytes == 0 ) ? true : false;
00042 
00043 
00044 /**
00045   * \brief  A lookup table for finding potentially applicable
00046   * rules for a packet based on L4 header information.
00047   * 
00048   * A lookup table struct - walk the tree using dest port, src port,
00049   * dest ip, src ip bits, 8 at a time from MSB, and the terminal
00050   * will be 
00051   * an index that can be used to get into an array of var_set_t * that 
00052   * is the set of corresponding rules - not L4 rules, the 
00053   * actual rules, or 
00054   * an array of util_int_array_t * that is
00055   * the same set.
00056   * 
00057   * The logic for this is that in some cases we may want the
00058   * set representation, in others the array representation.
00059   * specifically, if we are traversing an automaton to see what strings
00060   * are present, then the set representation  is superior.  Conversely,
00061   * for rules with no strings, where we have to traverse 
00062   * the entire set  of rules associated with a class derived
00063   * from the lookup-table, we might as well do it with an array representation.
00064   */
00065 
00066 struct Evl_L4LookupTable_t
00067 {
00068   int *tree;
00069   int numClasses;       // not actually needed for eval, but useful
00070   // to have around, e.g., to traverse ruleSets
00071   var_set_t **ruleSets;
00072   util_int_array_t **ruleArrays;
00073 
00074   // following two entries are used for pruning searches
00075   // initialized to -1
00076   int *ruleArrayMin;        // ruleArrayMin[i] is smallest index appearing in ruleArrays[i]
00077   int *ruleArrayMax;        // ruleArrayMax[i] is largest index appearing in ruleArrays[i]
00078 };
00079 
00080 typedef struct Evl_L4LookupTable_t Evl_L4LookupTable_t;
00081 
00082 
00083 /** \brief  A bdd_t and the level we are thinking of it as being at. */
00084 
00085 struct Evl_BddLevelPair_t
00086 {
00087   bdd_t *bdd;
00088   int level;
00089 };
00090 
00091 typedef struct Evl_BddLevelPair_t Evl_BddLevelPair_t;
00092 
00093 
00094 /**
00095     \brief  A stucture for evaluating L7 rules
00096     
00097     Basically, we're going to be passed in an array of Rlp_Formula_t's
00098     each with some (maybe none) content checks.   
00099     
00100     We need to be able to seperate the checks that have no content 
00101     checks - there 156 distinct rules (one repeated), focusing  on
00102 
00103 <pre>
00104     - icmp checks: id: dsize: itype: icmp_id: icmp_seq: ip_opts
00105     
00106     icmp 255.255.255.0/24 any -> HN any ( itype: 0; dsize: >1; )
00107     icmp 3.3.3.3/32 any -> EN any ( itype: 0; icmp_id: 666; )
00108     icmp any any -> any any ( itype: 3; icode: 10; )
00109     icmp any any -> any any ( itype: 3; icode: 13; )
00110     icmp any any -> any any ( itype: 3; icode: 9; )
00111     icmp EN any -> HN any ( dsize: 0; itype: 8; )
00112     icmp EN any -> HN any ( dsize: >800; )
00113     icmp EN any -> HN any ( dsize:8; itype:8; )
00114     icmp EN any -> HN any ( dsize:8; itype:8; id:13170; )
00115     icmp EN any -> HN any ( id: 666; dsize: 0; itype: 8; icmp_id: 666 ; icmp_seq: 0; )
00116     icmp EN any -> HN any ( ipopts: rr; itype: 0; )
00117     icmp EN any -> HN any ( itype: 0; )
00118     icmp EN any -> HN any ( itype: 0; icmp_id: 456; icmp_seq: 0; )
00119     icmp EN any -> HN any ( itype: 0; icmp_id: 51201; icmp_seq: 0; )
00120     icmp EN any -> HN any ( itype: 0; icode: 0; )
00121     icmp EN any -> HN any ( itype: 1; )
00122     icmp EN any -> HN any (itype:10; )
00123     icmp EN any -> HN any ( itype: 10; icode: 0; )
00124     icmp EN any -> HN any ( itype: 11; )
00125     icmp EN any -> HN any ( itype: 11; icode: 0; )
00126     icmp EN any -> HN any ( itype: 11; icode: 1; )
00127     icmp EN any -> HN any ( itype: 12; )
00128     icmp EN any -> HN any ( itype: 12; icode: 0; )
00129     icmp EN any -> HN any ( itype: 12; icode: 1; )
00130     icmp EN any -> HN any ( itype: 12; icode: 2; )
00131     icmp EN any -> HN any ( itype: 13; )
00132     icmp EN any -> HN any ( itype: 13; icode: 0; )
00133     icmp EN any -> HN any ( itype: 14; )
00134     icmp EN any -> HN any ( itype: 14; icode: 0; )
00135     icmp EN any -> HN any ( itype: 15; )
00136     icmp EN any -> HN any ( itype: 15; icode: 0; )
00137     icmp EN any -> HN any ( itype: 17; )
00138     icmp EN any -> HN any ( itype: 17; icode: 0; )
00139     icmp EN any -> HN any ( itype: 18; )
00140     icmp EN any -> HN any ( itype: 19; )
00141     icmp EN any -> HN any ( itype: 19; icode: 0; )
00142     icmp EN any -> HN any ( itype: 1; icode: 0; )
00143     icmp EN any -> HN any ( itype: 2; )
00144     icmp EN any -> HN any ( itype: 2; icode: 0; )
00145     icmp EN any -> HN any ( itype: 3; )
00146     icmp EN any -> HN any ( itype: 30; )
00147     icmp EN any -> HN any ( itype: 30; icode: 0; )
00148     icmp EN any -> HN any ( itype: 31; )
00149     icmp EN any -> HN any ( itype: 31; icode: 0; )
00150     icmp EN any -> HN any ( itype: 32; )
00151     icmp EN any -> HN any ( itype: 32; icode: 0; )
00152     icmp EN any -> HN any ( itype: 33; )
00153     icmp EN any -> HN any ( itype: 33; icode: 0; )
00154     icmp EN any -> HN any ( itype: 34; )
00155     icmp EN any -> HN any ( itype: 34; icode: 0; )
00156     icmp EN any -> HN any ( itype: 35; )
00157     icmp EN any -> HN any ( itype: 35; icode: 0; )
00158     icmp EN any -> HN any ( itype: 36; )
00159     icmp EN any -> HN any ( itype: 36; icode: 0; )
00160     icmp EN any -> HN any ( itype: 39; )
00161     icmp EN any -> HN any ( itype: 39; icode: 0; )
00162     icmp EN any -> HN any ( itype: 3; icode: 0; )
00163     icmp EN any -> HN any ( itype: 3; icode: 1; )
00164     icmp EN any -> HN any ( itype: 3; icode:11; )
00165     icmp EN any -> HN any ( itype: 3; icode: 12; )
00166     icmp EN any -> HN any ( itype: 3; icode: 14; )
00167     icmp EN any -> HN any ( itype: 3; icode: 15; )
00168     icmp EN any -> HN any ( itype: 3; icode: 2; )
00169     icmp EN any -> HN any ( itype: 3; icode: 3; )
00170     icmp EN any -> HN any ( itype: 3; icode:4; )
00171     icmp EN any -> HN any ( itype: 3; icode: 5; )
00172     icmp EN any -> HN any ( itype: 3; icode: 6; )
00173     icmp EN any -> HN any ( itype: 3; icode: 7; )
00174     icmp EN any -> HN any ( itype: 3; icode: 8; )
00175     icmp EN any -> HN any ( itype: 4; )
00176     icmp EN any -> HN any ( itype: 40; )
00177     icmp EN any -> HN any ( itype: 40; icode: 0; )
00178     icmp EN any -> HN any ( itype: 40; icode: 1; )
00179     icmp EN any -> HN any ( itype: 40; icode: 2; )
00180     icmp EN any -> HN any ( itype: 40; icode: 3; )
00181     icmp EN any -> HN any ( itype: 4; icode: 0; )
00182     icmp EN any -> HN any ( itype: 5; )
00183     icmp EN any -> HN any (itype:5;icode:0; )
00184     icmp EN any -> HN any (itype:5;icode:1; )
00185     icmp EN any -> HN any ( itype: 5; icode: 2; )
00186     icmp EN any -> HN any ( itype: 5; icode: 3; )
00187     icmp EN any -> HN any ( itype: 6; )
00188     icmp EN any -> HN any ( itype: 6; icode: 0; )
00189     icmp EN any -> HN any ( itype: 7; )
00190     icmp EN any -> HN any ( itype: 7; icode: 0; )
00191     icmp EN any -> HN any ( itype: 8; )
00192     icmp EN any -> HN any ( itype: 8; icmp_id: 0; icmp_seq: 0; dsize:4; )
00193     icmp EN any -> HN any ( itype: 8; icode: 0; )
00194     icmp EN any -> HN any (itype:9; )
00195     icmp EN any -> HN any ( itype: 9; icode: 0; )
00196     icmp EN any -> HN any (ttl:1;itype:8; )
00197     icmp HN any -> EN any ( itype: 16; )
00198     icmp HN any -> EN any ( itype: 16; icode: 0; )
00199     icmp HN any -> EN any ( itype: 18; icode: 0; )
00200     
00201     - ip checks: ipopts: fragbits: sameip: ip_proto: ttl: 
00202     
00203     ip 63.251.224.177 any -> HN any ( )
00204     ip any any -> 216.80.99.202 any ( )
00205     ip any any -> any any ( sameip; )
00206     ip EN any -> HN any ( fragbits:MD; )
00207     ip EN any -> HN any ( fragbits:M; dsize: < 25; )
00208     ip EN any -> HN any ( fragbits: M; dsize:408; )
00209     ip EN any -> HN any ( fragbits:R; )
00210     ip EN any -> HN any ( ipopts:lsrr; )
00211     ip EN any -> HN any ( ipopts:lsrre; )
00212     ip EN any -> HN any ( ipopts: ssrr ; )
00213     ip EN any -> HN any ( ip_proto:>134; )
00214     ip EN any -> HN any ( ip_proto:!1; ip_proto:!2; ip_proto:!6; ip_proto:!47; ip_proto:!50; ip_proto:!51; ip_proto:!89; )
00215     ip EN any -> HN any ( ttl:0; )
00216     
00217     - tcp checks: flags: rpc: dsize: seq: ack: id: 
00218     
00219     tcp 255.255.255.0/24 any -> HN any ( flags:A+; dsize: >1; )
00220     tcp any any -> 212.146.0.34 1963 ( )
00221     tcp any any -> [232.0.0.0/8,233.0.0.0/8,239.0.0.0/8] any ( flags:S+; )
00222     tcp EN 10101 -> HN any ( ttl: >220; ack: 0; flags: S; )
00223     tcp EN 20 -> HN :1023 ( flags:S; )
00224     tcp EN 53 -> HN :1023 ( flags:S; )
00225     tcp EN 6000:6005 -> HN any ( )
00226     tcp EN 80 -> HN 1054 ( seq: 101058054; ack: 101058054; flags: A; )
00227     tcp EN any -> HN 1080 ( flags:S; )
00228     tcp EN any -> HN 111 ( rpc:100009,*,*; )
00229     tcp EN any -> HN 111 ( rpc:100083,*,*; )
00230     tcp EN any -> HN 111 ( rpc:391029,*,*; )
00231     tcp EN any -> HN 135:139 ( flags: U+; )
00232     tcp EN any -> HN 15104 ( flags: S; )
00233     tcp EN any -> HN 161 ( )
00234     tcp EN any -> HN 162 ( )
00235     tcp EN any -> HN 20432 ( flags: A+; )
00236     tcp EN any -> HN 21 ( dsize:>100; )
00237     tcp EN any -> HN 3128 ( flags:S; )
00238     tcp EN any -> HN 3372 ( dsize:>1023; )
00239     tcp EN any -> HN 617 ( dsize:>1445; )
00240     tcp EN any -> HN 6789:6790 ( dsize:1; )
00241     tcp EN any -> HN 705 ( )
00242     tcp EN any -> HN 8080 ( flags:S; )
00243     tcp EN any -> HN 80 ( flags: SF12; dsize: 0; )
00244     tcp EN any -> HN any (flags:0; seq:0; ack:0; )
00245     tcp EN any -> HN any (flags:A;ack:0; )
00246     tcp EN any -> HN any ( flags: F; )
00247     tcp EN any -> HN any (flags:FPU; )
00248     tcp EN any -> HN any ( flags:S; dsize:>6; )
00249     tcp EN any -> HN any (flags:SF; )
00250     tcp EN any -> HN any (flags:SFPU; )
00251     tcp EN any -> HN any (flags:SRAFPU; )
00252     tcp EN any -> HN any ( flags:S; seq:1958810375; )
00253     tcp EN any -> HN any ( id:3868; seq: 3868; flags:S; )
00254     tcp EN any -> HN any ( id: 39426; flags: SF; )
00255     tcp HN 7161 -> EN any ( flags:SA; )
00256     
00257     - udp checks: dsize: rpc: fragbits: also a few specific ports
00258     
00259     udp any any -> 255.255.255.255 161 ( )
00260     udp any any -> 255.255.255.255 162 ( )
00261     udp EN 2140 -> HN 60000 ( )
00262     udp EN 60000 -> HN 2140 ( )
00263     udp EN any -> HN 111 ( rpc:100009,*,*; )
00264     udp EN any -> HN 111 ( rpc:100083,*,*; )
00265     udp EN any -> HN 123 ( dsize: >128; )
00266     udp EN any -> HN 161 ( )
00267     udp EN any -> HN 161 ( dsize:0; )
00268     udp EN any -> HN 162 ( )
00269     udp EN any -> HN any ( dsize: >4000; )
00270     udp EN any -> HN any ( id:242; fragbits:M; )
00271     
00272     The majority of the 4 checks above are EN -> HN type ; 
00273     only 12 are not - 
00274     
00275     icmp 255.255.255.0/24 any -> HN any ( itype: 0; dsize: >1; )
00276     icmp any any -> any any ( itype: 3; icode: 10; )
00277     icmp any any -> any any ( itype: 3; icode: 13; )
00278     icmp any any -> any any ( itype: 3; icode: 9; )
00279     ip 63.251.224.177 any -> HN any ( )
00280     ip any any -> 216.80.99.202 any ( )
00281     ip any any -> any any ( sameip; )
00282     tcp 255.255.255.0/24 any -> HN any ( flags:A+; dsize: >1; )
00283     tcp any any -> 212.146.0.34 1963 ( )
00284     tcp any any -> [232.0.0.0/8,233.0.0.0/8,239.0.0.0/8] any ( flags:S+; )
00285     udp any any -> 255.255.255.255 161 ( )
00286     udp any any -> 255.255.255.255 162 ( )
00287 
00288 </pre>
00289     
00290     Putting aside the no-content checks for now,  we need to think how to
00291     organize the checks.  
00292     
00293     Let's start by restricting our attention to a single packet rather than
00294     a flow.
00295     
00296     The assumption is that we have got a bit-vector telling us exactly which 
00297     L4 rules matches - it's N-wide, where N is the total number of rules.
00298     
00299     For each rule, we extract the strings it checks for (will handle 
00300     the negation and the case-insensitive seperately, and for uri, 
00301     will have a special kill flag after the uri is done).  We then 
00302     have an automaton over these strings, which tells us when 
00303     we've seen any one of these strings (by the id of 
00304     the current state).  
00305     
00306     For each string, we have an array which ids the rules in which it
00307     appears -  since it's unlikely that a string will appear in many rules
00308     (the most common strings are content:"../../" content:"|00|"
00309     content:"|00 01 86 A5|" content:"|00 01 86 B8|" content:"|00 04 93 F3|" 
00310     content: "filename="  which appear 6 times each) we can just keep
00311     them in linear order in the array.
00312     
00313     When traversing the automaton with the payload, we record strings
00314     as we see them.  Whenever we hit a string, we record the offset at which
00315     we saw it, check which rules might be affected, and check them
00316     
00317     The check for the affected rules is as follows: we see the content checks
00318     in that rule, and look at the strings that the rules refers to.  We 
00319     have the latest string-occurance: offset mapping, which allows
00320     us to check foo U_[10,20] bar U_[10,20] widget type checks.
00321     
00322     We could keep all the occurence of the strings, which would allow us
00323     to check a more complex semantics, e.g., if we were looking at only
00324     the most recent occurrences, we'd miss
00325     
00326     foo 10 chars bar 12 chars bar 2 char widget 
00327     
00328     since the second bar would get priority.
00329     
00330     It's unlikely this is a major issue, so we'll stick to the simpler check.
00331 */
00332 
00333 struct Evl_ContentMgr_t
00334 {
00335   int numStrings;       // num distinct strings
00336   st_table *stringToId;     // hash from string to id
00337   st_table *idToString;     // given an id, return the corresp string
00338   array_t *idToRules;       // entries are array_t * of ints
00339   array_t *stringArray;     // array of util_byte_array_t *
00340   array_t *maxLengthArray;  // length of longest string in rule (-1 for no strings)
00341   array_t *maxLengthStringsArray;   // longest string in rule (NIL if none)
00342 };
00343 
00344 typedef struct Evl_ContentMgr_t Evl_ContentMgr_t;
00345 
00346 
00347 /**
00348   * \brief  Fsm structure
00349   * 
00350   * Assumption is that there are no repeated
00351   * strings.  The initial state is the state whose id is numStrings,
00352   * and the states 0--numStrings-1 are the states corresponding
00353   * to the input strings.  
00354   * 
00355   * \sa Evl_BuildPrefixAutomaton 
00356   */
00357 
00358 struct Evl_Fsm_t
00359 {
00360   int N;            // number of states
00361   int numStrings;       // number of strings
00362 
00363   // array indexed by state ids (from 0 to N-1) returning a string
00364   util_byte_array_t **stateIdToPrefix;
00365 
00366 
00367   // evaluate the next state by computing entry at 256 * ps + in
00368   // it's conceivable that 256 * in + ps may be a better organization
00369   // from a cache persepective
00370   u_int16_t *nextStateFunction;
00371 
00372   int numInputValues;
00373   st_table *prefixHash;
00374 
00375   // array indexed by stateId, entry is an array_t 
00376   // containing id's of strings which are accepted at that state
00377   // these ids will be in the range 0--numStrings-1
00378   array_t *finalStates;
00379 
00380   // for performance we keep the set of final states ina bit vector
00381   // this makes for quick checks of whether a state is a final state
00382   // var_set_t *finalStatesVarSet; 
00383   u_int8_t *finalStatesVarSet;
00384   int *stateCount;      // use to see which states are visited the most frequently
00385 };
00386 
00387 typedef struct Evl_Fsm_t Evl_Fsm_t;
00388 
00389 
00390 /** \brief  Need the typedefs below because C will
00391   not allow Evl_Manager_t to refer to Evl_TcpMaanger_t before
00392   it's declared, even as a pointer, and vice versa.
00393 */
00394 
00395 typedef struct Evl_L4Manager_t Evl_L4Manager_t;
00396 typedef struct Evl_GenericManager_t Evl_GenericManager_t;
00397 typedef struct Evl_Bridge_t Evl_Bridge_t;
00398 
00399 
00400 /**
00401   * \brief  A representation of rules and corresponding lookup table
00402   *
00403   * We will often refer to a rule by its index into the allRules array,
00404   * which is just the string formula of the rule.
00405   * 
00406   * For now we are assuming that the rules are partitioned into three
00407   * sets: those that depend on dest port, those that depend on src but
00408   * not dest, and those that depend on neither source nor destination.
00409   * 
00410   * The variable ordering is taken to be destPort < srcPort <  destIp < srcIp
00411   * for all the BDDs.
00412   * 
00413   * The destPort bits are MSB to LSB in the BDD, ditto for the other port
00414   * and IP bits.  This will also help with the actual lookup.
00415   * 
00416   * The distinctL4RulesTable keeps track of the distinct L4 rules
00417   * we've seen - it maps the BDD to an int id, which can be used
00418   * to index into L4RuleIdToL7ruleSetTable, which tells us for a
00419   * given L4 rule what the original rules were - the set of corresponding
00420   * rules is represented by a var_set_t of length numAllRules.
00421   * 
00422   * There are three arrays of L4 lookup tables - one for each of 
00423   * the groups - destPortRules, srcPortRules, noPortRules.  
00424   * See the  L4 lookup table structure for details.
00425   * 
00426   */
00427 
00428 struct Evl_Manager_t
00429 {
00430 
00431   array_t *rawRulesAndMacrosArray;  // of strings
00432   st_table *defineTable;    // maps macros (char *s) to their defn (also a char *)
00433 
00434   array_t *rawRules;        // of char *s - it's the text of the rules
00435   int numAllRules;      // equal to array_n( rawRules )
00436 
00437   int numPreprocessRules;
00438   int indexFirstContentRule;
00439   int indexLastContentRule;
00440 
00441   Evl_L4Manager_t *tcpMgr;
00442   Evl_L4Manager_t *udpMgr;
00443   Evl_L4Manager_t *icmpMgr;
00444   Evl_L4Manager_t *ipMgr;
00445   Evl_GenericManager_t *genericMgr; // used for rules that are in the generic category
00446 
00447   Evl_Bridge_t *bridge;
00448 
00449   array_t *rlpActionArray;  // of Rlp_Action_t, equal in length to num of rules
00450   array_t *actionArray;     // of Evl_Action_t, equal in length to num of rules
00451   st_table *queueTable;     // maps queue names (char *s) to a string encoding the queue parameters
00452   Heap_t *qHeap;
00453 
00454   Tcl_Interp *interp;       // used for implementing user-defined tcl commands
00455   ClientData cd;        // used to pass around wrappers to raw pointers
00456 
00457   st_table *ucodeNameToFunction;
00458 
00459   // these have been moved from Evl_ComputeRuleSetForEth
00460   // to avoid having global state, keep the system re-entrant
00461   array_t *preprocessorResult;
00462   array_t *genericResult;
00463   array_t *layer3Result;
00464   array_t *layer4Result;
00465 
00466 };
00467 
00468 typedef struct Evl_Manager_t Evl_Manager_t;
00469 
00470 
00471 /** \brief  Struct encoding the action to be taken.  */
00472 
00473 struct Evl_Action_t
00474 {
00475 
00476   Rlp_Action_t *parsedAction;
00477 
00478   Pkt_LibNet_t *outIf;
00479   Q_Q_t *queue;
00480 };
00481 
00482 typedef struct Evl_Action_t Evl_Action_t;
00483 
00484 
00485 /** \brief Generic checks */
00486 
00487 struct Evl_GenericManager_t
00488 {
00489 
00490   Evl_Manager_t *mgr;
00491 
00492   array_t *tcpIdToGlobalId; // maps rule id to id in the set of all rules. it's not a tcp rule but we use tcp for consistent nomenclature
00493   array_t *L7RuleArray;
00494 
00495   int numAllRules;
00496 
00497 };
00498 
00499 
00500 /** \brief Everything needed to check TCP packets */
00501 
00502 struct Evl_L4Manager_t
00503 {
00504 
00505   Evl_Manager_t *mgr;
00506 
00507   array_t *L4RuleArray;     // of Rlp_L4Rule_t, equal in length to num of TCP rules
00508   array_t *L7RuleArray;     // of Rlp_Formula_t, equal in length to num of TCP rules
00509 
00510   array_t *contentChecks;   // of array_t *; each array entry is of Rlp_L7Check_t *
00511   // contentChecks is equal in length to num of TCP rules
00512 
00513   Evl_ContentMgr_t *cm;     // content manager
00514 
00515   array_t *tcpIdToGlobalId; // maps TCP rule id to id in the set of all rules
00516 
00517   int numAllRules;
00518 
00519   bdd_manager *bddMgr;
00520   int numDistinctL4Rules;   // it's st_count( distinctL4RulesTable ), but convenient
00521   st_table *distinctL4RulesTable;   // bdd_t mapped to int id
00522   array_t *ruleToL4Bdd;     // array of bdd_t's, indexed by rule id
00523   array_t *L4RuleIdToL7ruleSetTable;    // l4 rule to set of corresp orig rules
00524 
00525   Evl_L4LookupTable_t *destPortRuleTable;
00526   Evl_L4LookupTable_t *srcPortRuleTable;
00527   Evl_L4LookupTable_t *noPortRuleTable;
00528 
00529   Evl_L4LookupTable_t *noContentCheckTable;
00530   Evl_L4LookupTable_t *shortStringRuleTable;
00531 
00532   Evl_Fsm_t *fsm;
00533   var_set_t *fsmAcceptingStates;    // tells us which fsm states are accepting
00534   var_set_t **fsmStateToRuleSet;    // given an fsm state, returns set of rules
00535   // that are matched by this state (specifically
00536   // yields rule that have the string that got
00537   // us to this state as their longest string)
00538 
00539   // these are entries that are used when computing
00540   // applicable rulesets.  we include them in the struct
00541   // to avoid expesive allocation/deallocation per eval
00542   array_t *potentialRulesFromFsm;
00543   array_t *rulesFromFsm;
00544   array_t *rulesFromShortStringTable;
00545   array_t *rulesFromNoContentTable;
00546 };
00547 
00548 
00549 /** \brief  Encapsulate L4 flow information
00550   specifically destPort,
00551   srcPort, destIP, srcIP
00552   
00553 */
00554 
00555 struct Evl_L4Flow_t
00556 {
00557   u_int16_t destPort;
00558   u_int16_t srcPort;
00559   u_int32_t destIp;
00560   u_int32_t srcIp;
00561 };
00562 
00563 typedef struct Evl_L4Flow_t Evl_L4Flow_t;
00564 
00565 /** \brief Structure encapsulating various stats, used
00566   for testing purposes.
00567 */
00568 
00569 struct Evl_BridgeStats_t
00570 {
00571   util_timing_t startTime;
00572   util_timing_t finishTime;
00573   int numEntered;
00574   int numExited;
00575   int bytesWritten;
00576   int numDroppedAtWrite;
00577   int numDroppedFullRuleCacheArray;
00578   int numDroppedFullActionBuf;
00579   int numDroppedFullQueue;
00580   int numDroppedFullObuf;
00581   int numDroppedFullIbuf;
00582   int numDroppedBecauseOfAction;
00583   int numDroppedOverRate;
00584   int numDroppedOverFlowRate;
00585   util_timing_t firstPktRead;
00586   util_timing_t lastPktWritten;
00587   array_t *pcapInfo;
00588 };
00589 
00590 typedef struct Evl_BridgeStats_t Evl_BridgeStats_t;
00591 
00592 /** \brief Basic structure used for pulling packets in and out */
00593 
00594 struct Evl_Bridge_t
00595 {
00596   Circbuf_t *iBuf;
00597   Circbuf_t *oBuf;
00598   Circbuf_t *ppCache;
00599 
00600   array_t *inArray;
00601   array_t *outArray;
00602 
00603   Pkt_LibPcap_t *activeInputInterface;
00604   Evl_BridgeStats_t *stats;
00605 };
00606 
00607 
00608 /**AutomaticStart*************************************************************/
00609 
00610 /*---------------------------------------------------------------------------*/
00611 /* Extern function prototypes                                                */
00612 /*---------------------------------------------------------------------------*/
00613 
00614 extern Heap_t *Evl_AllocateQueueHeap (st_table * queueTable);
00615 extern int Evl_CompressDecompress (Pkt_EthernetHdr_t * pkt, int length,
00616                    Rlp_ActionEnum_t type);
00617 extern int Evl_Decompress (Pkt_EthernetHdr_t * pkt, int length);
00618 extern int Evl_Compress (Pkt_EthernetHdr_t * pkt, int length);
00619 extern void Evl_Crypto (Evl_Action_t * action, Pkt_ProcessPkt_t * pp,
00620             Rlp_ActionEnum_t type);
00621 extern void Evl_EncryptPkt (Evl_Action_t * action, Pkt_ProcessPkt_t * pp );
00622 extern void Evl_DecryptPkt (Evl_Action_t * action, Pkt_ProcessPkt_t * pp );
00623 extern void Evl_RoutePkt (Evl_Action_t * action, Evl_Bridge_t * bridge,
00624               Pkt_ProcessPkt_t * pp);
00625 extern void Evl_UscriptAction (Rlp_Action_t * action, Evl_Manager_t * mgr,
00626                    Pkt_ProcessPkt_t * pp);
00627 extern int Evl_UcodeAction (Rlp_Action_t * action, Evl_Manager_t * mgr,
00628                  Pkt_ProcessPkt_t * pp);
00629 extern int Evl_ComputeL7RuleSet (Evl_L4LookupTable_t * aRuleTable,
00630                  Evl_L4Flow_t * aFlow);
00631 extern util_int_array_t *Evl_ComputeL7RuleArray (Evl_L4LookupTable_t *
00632                          aRuleTable,
00633                          Evl_L4Flow_t * aFlow);
00634 extern void Evl_ComputeRuleSetForEth (Pkt_ProcessPkt_t * pp,
00635                       Evl_Manager_t * globalMgr);
00636 extern void Evl_L4ComputeRuleSetForEth (Pkt_ProcessPkt_t * pp,
00637                     Evl_L4Manager_t * l4mgr,
00638                     array_t * result);
00639 extern int Evl_EthEvalL7RuleContentCheck (Pkt_EthernetHdr_t * anEth,
00640                       array_t * aL7CheckArray);
00641 extern void Evl_EvalRuleArray (Evl_L4Manager_t * mgr, Pkt_ProcessPkt_t * pp,
00642                    array_t * ruleArray,
00643                    util_int_array_t * ruleIntArray,
00644                    array_t * result);
00645 extern bool Evl_EthEvalL7Rule (Pkt_ProcessPkt_t * pp,
00646                    Rlp_Formula_t * aL7Formula,
00647                    array_t * aL7CheckArray);
00648 extern void Evl_PktDecompress (Evl_L4Manager_t * l4mgr,
00649                    Pkt_ProcessPkt_t * pp);
00650 extern void Evl_PktDecrypt (Evl_L4Manager_t * l4mgr, Pkt_ProcessPkt_t * pp);
00651 extern Evl_Fsm_t *Evl_BuildPrefixAutomaton (array_t * byteArrayArray);
00652 extern int Evl_FsmPrint (Evl_Fsm_t * anFsm);
00653 extern int Evl_FsmProcessAcceptingState (Evl_Fsm_t * fsm, u_int32_t ps,
00654                      st_table * stringToId,
00655                      array_t * idToRules,
00656                      var_set_t * set1, var_set_t * set2,
00657                      var_set_t * set3,
00658                      array_t * resultPtr);
00659 extern void Evl_FsmComputeRules (Evl_Fsm_t * fsm, st_table * stringToId,
00660                  array_t * idToRules, var_set_t * set1,
00661                  var_set_t * set2, var_set_t * set3,
00662                  char *payload, int length, array_t * result);
00663 extern int Evl_Route (Evl_Manager_t * aMgr, array_t * pktArray, int iBufSize,
00664               int ppCacheSize, int oBufSize, int actionBufSize,
00665               int maxNumPktsToRead, int numIterations,
00666               bool useSynthetic, array_t * inArray,
00667               array_t * outArray, double basicSlice,
00668               int getPacketsWeight, int computeActionsWeight,
00669               int performActionsWeight, int queuingWeight,
00670               int writePacketsWeight, array_t * ackSeqArray,
00671               Evl_BridgeStats_t ** statsPtr);
00672 extern int Evl_InsertPacketInQueue (Evl_Manager_t * aMgr, Q_Q_t * aQ,
00673                     Pkt_ProcessPkt_t * pp,
00674                     Evl_Action_t * action);
00675 extern int Evl_TestManager (Evl_Manager_t * aMgr);
00676 extern bool Evl_DoAction (Evl_Action_t * action, Evl_Manager_t * mgr,
00677               Evl_Bridge_t * bridge, Pkt_ProcessPkt_t * pp);
00678 extern void Evl_BridgeInsertPktInIbuf (Evl_Bridge_t * aBridge,
00679                        Pkt_EthernetHdr_t * aPkt);
00680 extern Evl_Manager_t *Evl_BuildManager (char *ruleFileString,
00681                     Tcl_Interp * interp, ClientData cd);
00682 extern Evl_Action_t *Evl_AllocAction (Rlp_Action_t * parsedAction);
00683 extern bdd_t *Evl_BuildBddFromL4Formula (Rlp_L4Check_t * L4Check,
00684                      st_table * defineTable,
00685                      bdd_manager * bddMgr);
00686 extern bdd_t *Evl_BuildBddForIps (Rlp_Formula_t * srcIp, bdd_manager * bddMgr,
00687                   st_table * defineTable);
00688 extern bdd_t *Evl_BuildBddForPorts (Rlp_Formula_t * portFormula,
00689                     bdd_manager * bddMgr,
00690                     st_table * defineTable);
00691 extern bdd_t *Evl_BuildBddForPortRange (int lowPort, int highPort,
00692                     bdd_manager * bddMgr);
00693 extern int Evl_BddCmp (char *aBdd, char *bBdd);
00694 extern int Evl_BddHash (char *aBdd, int modulus);
00695 extern Evl_L4LookupTable_t *Evl_RuleRelationToLookupTable (bdd_t * TR,
00696                                Evl_L4Manager_t *
00697                                L4Mgr,
00698                                array_t *
00699                                ruleVarArray);
00700 extern Evl_L4LookupTable_t *Evl_L4BuildLookup (Evl_BddLevelPair_t * root,
00701                            int numClasses,
00702                            Evl_L4Manager_t * L4Mgr,
00703                            st_table * allDecisionNodes);
00704 extern Evl_BddLevelPair_t *Evl_CreateBddLevelPair (bdd_t * aBdd, int level);
00705 extern int Evl_BddLevelPairHash (char *aPtr, int modulus);
00706 extern int Evl_BddLevelPairCmp (char *aPtr, char *bPtr);
00707 extern Evl_L4Manager_t *Evl_L4ManagerAlloc (Evl_Manager_t * mgr, char *mode);
00708 extern Evl_Manager_t *Evl_ManagerAlloc ();
00709 extern int Evl_ManagerFree (Evl_Manager_t * result );
00710 extern Evl_ContentMgr_t *Evl_BuildContentMgr (array_t * L7CheckArray);
00711 extern Evl_ContentMgr_t *Evl_AllocContentMgr ();
00712 extern void Evl_PrintContentMgr (Evl_ContentMgr_t * aCM);
00713 extern int Evl_L4LookupTableAddRuleArrays (Evl_L4LookupTable_t * table);
00714 extern Evl_ContentMgr_t
00715   * Evl_BuildContentMgrForLowerCaseStrings (Evl_ContentMgr_t * aCM);
00716 
00717 /**AutomaticEnd***************************************************************/
00718 
00719 #ifdef __cplusplus
00720 }
00721 #endif
00722 
00723 #endif /* _EVL */