Azinix

evlMgr.c

Go to the documentation of this file.
00001 /** \file evlMgr.c
00002 
00003  \brief Routines for creating data structure containing everything needed to evaluate rules. 
00004 
00005 Content searches come in several flavors:
00006 <pre>
00007   - raw checks for strings (possibly a set of strings)
00008 
00009   - strings in specific places (or range of places)
00010 
00011     o these are specified using depth and offset
00012 
00013       + most are of the form 
00014 
00015         content:"HTTP/1.1 403"; depth:12 OR
00016 
00017         content:"|2a 02|"; offset:0; depth:2; content:"|00 04 00 06|"; offset:6; depth:4;
00018         which specify exactly where to look
00019 
00020         Note this contradicts what the manual says is the semantics
00021         of depth, it appears to be relative to the offset, not to the 
00022         start of payload. 
00023 
00024      + some are like
00025  
00026        content:"|01 87 8B 00 00|"; offset:40; depth:8; 
00027 
00028        which means look for this content string starting at 40 bytes
00029        into the payload, and only at locations 40 41 42 43
00030 
00031      + with one exception (750) no depth exceeds 128, and offsets
00032        are in the set {300, 200, 83, 45, 43, ... }  (the 750 and 300 are the
00033        same)  
00034 
00035    o strings that have within/distance constraints
00036 
00037      complete set of values: distance:0 :1 :16 :32 :4 :5 
00038      within:1 :100 :1024 :12 :128 :150 :2 :255 :256 :3 :4 :50 :500 :512 :600
00039 
00040      there are 8 rules that mix depth/offset and within/distance
00041 
00042      There is some confusion as to whether within/distance is anchored to 
00043      the START of the last match, or the end of the last match (or the
00044      beginning of the new match for distance)
00045 
00046      content:"SITE "; nocase; content:"EXEC "; distance:0;
00047      content:"RETR"; nocase; content:"file_id.diz"; nocase; distance:1;
00048      content:"|00 01 86 A0|"; content:"|00 00 00 04|"; distance:4; within:4;
00049      content:"From\:"; content:"<><><><><><><><><><><><><><><><><><><><><><>"; 
00050              distance:0; content:"("; distance:1; content:")"; distance:1; 
00051 
00052 Some strings are very short (e.g. 1 char, and using a 
00053 generic automaton for all strings will lead to huge 
00054 numbers of hits in the automaton.
00055 
00056 there are many singletons:
00057 
00058 0x0 0x1 0x4 0x9 0x10 0x19 % & () * .  0 1 : ; > ?  @ A [ ] { | 
00059  
00060 doubles:
00061 
00062 0x0 0x0 0x0 0x1 0x0 0x2 0x-76 0x-76 0x0 0x20 00 02 03 04 0x0 # 07 ?& 
00063 09 0x2 0x0 -- ST 20 21 22 23 24 25 70 26 71 *0x1 *0x2 0x4 0x0 / A B 
00064 C 40 41 91 92 S ` %p 10 12 13 14 15 60 16 17 63 64 @/ @@ ..  .0 30 
00065 31 32 33 34 35 36 =+ 37 38 39 88
00066 
00067 triples:
00068 
00069 0x0 0x0 0x-4 %00 911 121 FC 125 %0a %5c 0x0 0x2 0x0 %20 c:\ 0x0 
00070 _0x2 MKD CWD B0x0 0x2 0x10 D/ !@# ~0x10 %%% 199 l44 1MB 110 PWD 
00071 117 118 000 0x0 0x6 0x0 /%% db= /// ;id 0x0 0x1 / 130 ../ 0x0 
00072 0x1 C 0x5 0x0 > 370 et= %1u ..\ 0x4 0x1 0x0 100 0x0 0x-53 0x0 %p 
00073 
00074 There are several ways in which to avoid this:
00075 
00076   - disallow strings of length 2 or less (the prob of matching
00077     one of 50 random length 3 strings in a 1000 byte packet
00078     is < 50 * 1000 * 2^{-24} ~ 2^6 * 2^10 * 2^{-24} = 2^{-8})
00079 
00080   - disallow strings on length 2 or less in the first thing being checked
00081     then we have two automata, one for the initial strings, and if that's 
00082     active, we use the global automata.  
00083 
00084     this seems unreasonable, since we won't know the state of the 
00085     global automaton, unless we run from scratch.
00086 
00087   - allow strings of length 2 or less but only for very restricted
00088     checks on source/destination port.  we have a check to see if 
00089     the flow matches the conditions for using the "special" automaton,
00090     and switch to it if needed.
00091 
00092     more generally, we could have a seperate automaton per equivalence
00093     class - there are a relatively small number of classes after we
00094     partition.  we'll need 300 automata, each over an avg of 2 layer 4 rules,
00095     each of which is ~20 rules. this might be too high a memory overhead. 
00096 
00097     in addition we'd have 3 automata simulations to do per packet (plus
00098     the no case automata).
00099 </pre>
00100 
00101 One solution is to have for each rule, the longest string appearing in
00102 it. Then build a table/fsm over these strings.  
00103 Then run the payload over the table/fsm and see which strings are
00104 present in the payload.  The specific set of strings that match is used
00105 to find corresponding rules; each of these rules is then invoked on a 
00106 1-by-1 basis. 
00107 
00108 We can do pretty much the same thing - first of all determine
00109 which rules are potentially applicable by running the automaton,
00110 and for each matching string, seeing the rules associated with it.
00111 We have the layer 4 information, so we can automatically do some
00112 pruning here.
00113 
00114 It should be pretty simple to check a single rule on a packet;
00115 infact all we are checking is the optional checks (ttl, icmp, etc.)
00116 The payload checks will be either a intersection of strings, or a
00117 sequence of strings (need to check if there's also a possibility of
00118 mixed checks, e.g., abc U pqr OR xyz).  For each string we're checking
00119 for, we can pre-compute the BM jump table, should be pretty quick.
00120 
00121 One concern that remains is short strings - 1 or 2 chars.  What
00122 do we do if they are the longest string appearing in a rule? 
00123 
00124 Since these strings will appear only in rules that are very qualified
00125 (src port = 6000, dest port = 2121), we can keep a BDD encoding 
00126 the L4 conditions for these rules (call the set S) , and just 
00127 check the rules directly.
00128 
00129 It's likely that there will be few rules per class for the 
00130 ECs engendered by S. (Most of the packets won't even satisfy
00131 S.)  So a brute force evaluation of all the rules in the class should
00132 be simple enough.
00133 
00134 */
00135 
00136 #include "evl.h"
00137 
00138 /**AutomaticStart*************************************************************/
00139 
00140 /*---------------------------------------------------------------------------*/
00141 /* Static function prototypes                                                */
00142 /*---------------------------------------------------------------------------*/
00143 
00144 static void computeNumberOfPreprocessRules (Evl_Manager_t * mgr);
00145 static bool checkLegalRule (char *aRule);
00146 static void populateL4Manager (Evl_Manager_t * mgr, char *mode);
00147 static bdd_t *offsetVars (bdd_t * aBdd, bdd_manager * bddMgr, int numVars,
00148               int offset);
00149 static bdd_t *listToBdd (Rlp_Formula_t * srcIp, bdd_manager * bddMgr,
00150              st_table * defineTable);
00151 static bdd_t *ipToBdd (u_int32_t anIp, u_int32_t mask, bdd_manager * bddMgr);
00152 static bdd_t *buildBddPort (int lowPort, bdd_manager * bddMgr, int index);
00153 static void populateLookupTables (Evl_L4Manager_t * mgr);
00154 static Evl_L4LookupTable_t *createLookupTable (Evl_L4Manager_t * mgr,
00155                            array_t * L4BddArray,
00156                            array_t * ruleVarArray);
00157 static int longestPathToOne (bdd_t * aBdd, int descend);
00158 static void printCubes (bdd_t * aBdd);
00159 static int populateDecisionNodeTable (Evl_BddLevelPair_t * aBddLevelPair,
00160                       st_table * allDecisionNodes,
00161                       st_table * canonicalMap);
00162 static bdd_t *getCofactorCube (int decisionLevel, int value,
00163                    bdd_manager * bddMgr, bool clearCache);
00164 static void populateNodeToIdTable (Evl_BddLevelPair_t * root,
00165                    st_table * allDecisionNodes,
00166                    st_table * nodeToIdTable);
00167 static var_set_t *classBddToSet (bdd_t * leafBdd, Evl_L4Manager_t * L4Mgr);
00168 static Evl_GenericManager_t *Evl_GenericManagerAlloc (Evl_Manager_t * mgr);
00169 static int addQueue (st_table * queueNameToQueueTable, char *anEntry);
00170 static int populateL4BddInfo (Evl_L4Manager_t * L4Mgr);
00171 static int bddArrayFree (array_t * bdds);
00172 static int updateIdToRules (array_t * idToRules, int contentId,
00173                 int ruleIndex);
00174 static void populateContentManager (Evl_L4Manager_t * L4Mgr);
00175 static int buildShortStringLookupTable (Evl_L4Manager_t * mgr);
00176 static int printRuleSet (Evl_L4Manager_t * mgr, var_set_t * ruleSet);
00177 static void populateLongStringsFsm (Evl_L4Manager_t * mgr);
00178 static void populateMgrFsmAcceptingStates (Evl_L4Manager_t * L4Mgr,
00179                        st_table * longByteArrayHash);
00180 static int populateRawRulesAndMacros (Evl_Manager_t * mgr, char *ruleFile);
00181 static int buildNoContentCheckTable (Evl_L4Manager_t * mgr);
00182 static bool checkRuleMode (char *rawRule, char *mode);
00183 
00184 /**AutomaticEnd***************************************************************/
00185 
00186 
00187 /**
00188   * \brief  Build basic evl data structures from a rule-set
00189   */
00190 
00191 Evl_Manager_t *
00192 Evl_BuildManager (char *ruleFileString, Tcl_Interp * interp, ClientData cd)
00193 {
00194   Evl_Manager_t *result = Evl_ManagerAlloc ();
00195   result->interp = interp;
00196   result->cd = cd;
00197 
00198   populateRawRulesAndMacros (result, ruleFileString);
00199 
00200   // iterate through all the text lines, do basic parsing
00201   int i;
00202   for (i = 0; i < array_n (result->rawRulesAndMacrosArray); i++)
00203     {
00204       char *anEntry = array_fetch (char *, result->rawRulesAndMacrosArray, i);
00205       if (util_strequalN (anEntry, "var", 3))
00206     {
00207       Rlp_UpdateDefineTable (result->defineTable, anEntry);
00208     }
00209       else if (util_strequalN (anEntry, "queue", 5))
00210     {
00211       addQueue (result->queueTable, anEntry);
00212     }
00213       else
00214     {
00215       checkLegalRule (anEntry);
00216       array_insert_last (char *, result->rawRules, anEntry);
00217       char *actionComponent = Rlp_GetActionComponentFromRawRule (anEntry);
00218       Rlp_Action_t *parsedAction =
00219         Rlp_CreateActionFromRawText (actionComponent);
00220       array_insert_last (Rlp_Action_t *, result->rlpActionArray,
00221                  parsedAction);
00222       Evl_Action_t *action = Evl_AllocAction (parsedAction);
00223       array_insert_last (Evl_Action_t *, result->actionArray, action);
00224       result->numAllRules++;
00225     }
00226     }
00227 
00228   computeNumberOfPreprocessRules (result);
00229 
00230   populateL4Manager (result, "tcp");
00231   populateL4Manager (result, "udp");
00232   populateL4Manager (result, "icmp");
00233   populateL4Manager (result, "ip");
00234   populateL4Manager (result, "generic");
00235 
00236   return result;
00237 }
00238 
00239 
00240 /**
00241   * \brief Check that a string is a legal rule.  Incomplete, just
00242   * looks for gross errors.
00243   */
00244 
00245 static bool
00246 checkLegalRule (char *aRule)
00247 {
00248   bool prefixCheck = false;
00249   if (util_strequalN (aRule, "generic", strlen ("generic")) ||
00250       util_strequalN (aRule, "udp", strlen ("udp")) ||
00251       util_strequalN (aRule, "tcp", strlen ("tcp")) ||
00252       util_strequalN (aRule, "icmp", strlen ("ip")) ||
00253       util_strequalN (aRule, "ip", strlen ("ip")))
00254     {
00255       prefixCheck = true;
00256     }
00257   if (prefixCheck == false)
00258     {
00259       return false;
00260     }
00261   // at some later point we can add individual
00262   // checks for generic, udp, tcp, etc. rules
00263   return true;
00264 }
00265 
00266 
00267 /**
00268   * \brief Create the action structured from the parsed entries
00269   */
00270 
00271 Evl_Action_t *
00272 Evl_AllocAction (Rlp_Action_t * parsedAction)
00273 {
00274   Evl_Action_t *result = (Evl_Action_t *) malloc (sizeof (Evl_Action_t));
00275   result->parsedAction = parsedAction;
00276   result->queue = NIL (Q_Q_t);
00277   result->outIf = NIL (Pkt_LibNet_t);
00278 
00279   return result;
00280 }
00281 
00282 
00283 /**
00284   * \brief Build manager for tcp rules.  Returns mapping from id of local rule to all rules
00285   *
00286   * Even though it refers to portsm this structure can be used for tcp, udp, icmp, and even ip rules.
00287   * E.g., the rules ip 192.168.1.1/24 any -> any any (...)
00288   *     will lead to the right lookup table being created.
00289   *
00290   * \param mgr is the top level mananger
00291   * \param mode is used to indicate whether this is going to be built for tcp, udp, icmp, ip.
00292   */
00293 
00294 static void
00295 populateL4Manager (Evl_Manager_t * mgr, char *mode)
00296 {
00297   if (util_strequal (mode, "generic"))
00298     {
00299       mgr->genericMgr = Evl_GenericManagerAlloc (mgr);
00300       return;           // no content checks
00301     }
00302 
00303   Evl_L4Manager_t *L4Mgr = Evl_L4ManagerAlloc (mgr, mode);
00304 
00305   if (util_strequal (mode, "tcp"))
00306     {
00307       mgr->tcpMgr = L4Mgr;
00308     }
00309   else if (util_strequal (mode, "udp"))
00310     {
00311       mgr->udpMgr = L4Mgr;
00312     }
00313   else if (util_strequal (mode, "icmp"))
00314     {
00315       mgr->icmpMgr = L4Mgr;
00316     }
00317   else if (util_strequal (mode, "ip"))
00318     {
00319       mgr->ipMgr = L4Mgr;
00320     }
00321   else
00322     {
00323       assert (0);
00324     }
00325 
00326   populateContentManager (L4Mgr);
00327   Evl_ContentMgr_t *aCM = L4Mgr->cm;
00328 
00329   Evl_ContentMgr_t *lowerCaseCM =
00330     Evl_BuildContentMgrForLowerCaseStrings (aCM);
00331   L4Mgr->cm = lowerCaseCM;
00332 
00333   populateLongStringsFsm (L4Mgr);
00334   populateL4BddInfo (L4Mgr);
00335   populateLookupTables (L4Mgr);
00336 }
00337 
00338 
00339 /**
00340   * \brief  Build a bdd for the L4 check
00341   */
00342 
00343 bdd_t *
00344 Evl_BuildBddFromL4Formula (Rlp_L4Check_t * L4Check,
00345                st_table * defineTable, bdd_manager * bddMgr)
00346 {
00347   bdd_t *tmpSrcIpBdd =
00348     Evl_BuildBddForIps (L4Check->srcIp, bddMgr, defineTable);
00349   bdd_t *tmpDestIpBdd =
00350     Evl_BuildBddForIps (L4Check->destIp, bddMgr, defineTable);
00351 
00352   bdd_t *tmpSrcPortBdd =
00353     Evl_BuildBddForPorts (L4Check->srcPort, bddMgr, defineTable);
00354   bdd_t *tmpDestPortBdd =
00355     Evl_BuildBddForPorts (L4Check->destPort, bddMgr, defineTable);
00356 
00357   bdd_t *destIpBdd = offsetVars (tmpDestIpBdd, bddMgr, 32, 32);
00358   bdd_t *srcIpBdd = offsetVars (tmpSrcIpBdd, bddMgr, 32, 64);
00359 
00360   // wasteful, but stays symmetric
00361   bdd_t *destPortBdd = offsetVars (tmpDestPortBdd, bddMgr, 16, 0);
00362 
00363   bdd_t *srcPortBdd = offsetVars (tmpSrcPortBdd, bddMgr, 16, 16);
00364 
00365   bdd_t *t1 = bdd_and (destIpBdd, srcIpBdd, 1, 1);
00366   bdd_t *t2 = bdd_and (destPortBdd, srcPortBdd, 1, 1);
00367   bdd_t *t3 = bdd_and (t1, t2, 1, 1);
00368 
00369   bdd_free (tmpSrcIpBdd);
00370   bdd_free (tmpDestIpBdd);
00371   bdd_free (tmpSrcPortBdd);
00372   bdd_free (tmpDestPortBdd);
00373 
00374   bdd_free (destIpBdd);
00375   bdd_free (srcIpBdd);
00376   bdd_free (destPortBdd);
00377   bdd_free (srcPortBdd);
00378 
00379   bdd_free (t1);
00380   bdd_free (t2);
00381 
00382   return t3;
00383 }
00384 
00385 
00386 /**
00387   * \brief  Take an existing BDD over some vars, and substitute
00388   * those vars by some later in the order.
00389   */
00390 
00391 static bdd_t *
00392 offsetVars (bdd_t * aBdd, bdd_manager * bddMgr, int numVars, int offset)
00393 {
00394   array_t *origVars = array_alloc (bdd_t *, 0);
00395   array_t *newVars = array_alloc (bdd_t *, 0);
00396 
00397   int i;
00398   for (i = 0; i < numVars; i++)
00399     {
00400       bdd_t *aVar = bdd_get_variable (bddMgr, i);
00401       bdd_t *aNewVar = bdd_get_variable (bddMgr, i + offset);
00402       array_insert_last (bdd_t *, origVars, aVar);
00403       array_insert_last (bdd_t *, newVars, aNewVar);
00404     }
00405   bdd_t *result = bdd_substitute (aBdd, origVars, newVars);
00406   for (i = 0; i < numVars; i++)
00407     {
00408       bdd_t *aVar = array_fetch (bdd_t *, origVars, i);
00409       bdd_t *aNewVar = array_fetch (bdd_t *, newVars, i);
00410       bdd_free (aVar);
00411       bdd_free (aNewVar);
00412     }
00413   array_free (origVars);
00414   array_free (newVars);
00415   return result;
00416 }
00417 
00418 
00419 /**
00420   * \brief  Build a bdd for an ip formula
00421   * 
00422   * Variables are starting from 0,
00423   * which is the LSB of the IP address.
00424   */
00425 
00426 bdd_t *
00427 Evl_BuildBddForIps (Rlp_Formula_t * srcIp,
00428             bdd_manager * bddMgr, st_table * defineTable)
00429 {
00430   bdd_t *t1;
00431   bdd_t *t2;
00432   bdd_t *result = NIL (bdd_t);
00433   char *defineValue;
00434   Rlp_Formula_t *defineFormula;
00435 
00436   switch (srcIp->type)
00437     {
00438     case Rlp_Any_c:
00439       result = bdd_one (bddMgr);
00440       break;
00441     case Rlp_Negation_c:
00442       t1 = Evl_BuildBddForIps (srcIp->lchild, bddMgr, defineTable);
00443       result = bdd_not (t1);
00444       bdd_free (t1);
00445       break;
00446     case Rlp_List_c:
00447 
00448       // recursion kills performance on very long lists, do in a loop
00449       // t1 = Evl_BuildBddForIps( srcIp->lchild, bddMgr, defineTable );
00450       // t2 = Evl_BuildBddForIps( srcIp->rchild, bddMgr, defineTable );
00451       // result = bdd_or( t1, t2, 1, 1 );
00452       // bdd_free( t1 ); bdd_free( t2 );
00453 
00454       // loop solution:
00455       result = listToBdd (srcIp, bddMgr, defineTable);
00456       break;
00457     case Rlp_IpEntry_c:
00458       result =
00459     ipToBdd ((u_int32_t) srcIp->lchild, (u_int32_t) srcIp->rchild,
00460          bddMgr);
00461       break;
00462     case Rlp_Define_c:
00463       if (!Hash_Lookup
00464       (defineTable, (char *) srcIp->lchild, (char **) &defineValue))
00465     {
00466       printf ("Could not find the defined symbol %s\n",
00467           (char *) srcIp->lchild);
00468       assert (0);
00469     }
00470       defineFormula = Rlp_ComputeIpFormulaFromString (defineValue);
00471       result = Evl_BuildBddForIps (defineFormula, bddMgr, defineTable);
00472       break;
00473     default:
00474       printf ("Invalid type of ip node in formula\n");
00475       assert (0);
00476     }
00477 
00478   /* useful for debugging:
00479      printf("Result bdd has %d nodes\n", bdd_size( result ) );
00480      array_t *ipVarArray = array_alloc( bdd_t *, 0 );
00481 
00482      int i;
00483      for ( i = 0 ; i < 32; i++ ) {
00484      bdd_t *anIpVar = bdd_get_variable( bddMgr, i );
00485      array_insert_last( bdd_t *, ipVarArray, anIpVar );
00486      }
00487      printf("Number of minterms = %.0f\n", bdd_count_onset( result, ipVarArray ) );
00488    */
00489 
00490   return result;
00491 }
00492 
00493 
00494 /** \brief Build a BDD from a list */
00495 
00496 static bdd_t *
00497 listToBdd (Rlp_Formula_t * srcIp,
00498        bdd_manager * bddMgr, st_table * defineTable)
00499 {
00500   bdd_t *t1;
00501   bdd_t *t2;
00502   bdd_t *result = bdd_zero (bddMgr);
00503   Rlp_Formula_t *iterFormula = srcIp;
00504   while (iterFormula != NIL (Rlp_Formula_t))
00505     {
00506       assert (iterFormula->type == Rlp_List_c);
00507       t1 = Evl_BuildBddForIps (iterFormula->lchild, bddMgr, defineTable);
00508       t2 = bdd_or (result, t1, 1, 1);
00509       bdd_free (t1);
00510       bdd_free (result);
00511       result = t2;
00512       iterFormula = cdr (iterFormula);
00513     }
00514   return result;
00515 
00516 }
00517 
00518 
00519 /** \brief  Build a bdd from a ip/mask */
00520 
00521 static bdd_t *
00522 ipToBdd (u_int32_t anIp, u_int32_t mask, bdd_manager * bddMgr)
00523 {
00524 
00525   bdd_t *t1;
00526   bdd_t *result = bdd_one (bddMgr);
00527 
00528   int i;
00529   int ipAddrLen = 32;
00530   for (i = (ipAddrLen - 1); i >= 0; i--)
00531     {
00532       int testBit = (1 << i) & mask;
00533       if (testBit)
00534     {
00535       bdd_t *tmpBdd = bdd_get_variable (bddMgr, 31 - i);
00536       bdd_t *notTmpBdd = bdd_not (tmpBdd);
00537       if (anIp & (1 << i))
00538         {
00539           t1 = bdd_and (tmpBdd, result, 1, 1);
00540         }
00541       else
00542         {
00543           t1 = bdd_and (notTmpBdd, result, 1, 1);
00544         }
00545       bdd_free (result);
00546       bdd_free (tmpBdd);
00547       bdd_free (notTmpBdd);
00548       result = t1;
00549     }
00550     }
00551   return result;
00552 }
00553 
00554 
00555 /** \brief  Create a BDD from a port formula */
00556 
00557 bdd_t *
00558 Evl_BuildBddForPorts (Rlp_Formula_t * portFormula,
00559               bdd_manager * bddMgr, st_table * defineTable)
00560 {
00561   bdd_t *t1;
00562   bdd_t *result = NIL (bdd_t);
00563   char *defineValue;
00564   Rlp_Formula_t *defineFormula;
00565 
00566   switch (portFormula->type)
00567     {
00568     case Rlp_Any_c:
00569       result = bdd_one (bddMgr);
00570       break;
00571     case Rlp_Negation_c:
00572       t1 = Evl_BuildBddForPorts (portFormula->lchild, bddMgr, defineTable);
00573       result = bdd_not (t1);
00574       bdd_free (t1);
00575       break;
00576     case Rlp_PortRange_c:
00577       result = Evl_BuildBddForPortRange ((u_int32_t) portFormula->lchild,
00578                      (u_int32_t) portFormula->rchild,
00579                      bddMgr);
00580       break;
00581     case Rlp_Define_c:
00582       if (!Hash_Lookup
00583       (defineTable, (char *) portFormula->lchild, (char **) &defineValue))
00584     {
00585       printf ("Could not find the defined symbol %s\n",
00586           (char *) portFormula->lchild);
00587       assert (0);
00588     }
00589       defineFormula = Rlp_ComputePortFormulaFromString (defineValue);
00590       result = Evl_BuildBddForPorts (defineFormula, bddMgr, defineTable);
00591       break;
00592     default:
00593       printf ("Invalid type of port node in formula\n");
00594       assert (0);
00595     }
00596 
00597   /* useful for debugging
00598      printf("Result bdd has %d nodes\n", bdd_size( result ) );
00599      array_t *portVarArray = array_alloc( bdd_t *, 0 );
00600      int i;
00601      for ( i = 0 ; i < 16; i++ ) {
00602      bdd_t *aPortVar = bdd_get_variable( bddMgr, i );
00603      array_insert_last( bdd_t *, portVarArray, aPortVar );
00604      }
00605      printf("Number of minterms = %.0f\n", bdd_count_onset( result, portVarArray ) );
00606 
00607    */
00608   return result;
00609 }
00610 
00611 
00612 /**
00613   * \brief  Build Bdd for a port interval [low,high], inclusive of end-points
00614   */
00615 
00616 bdd_t *
00617 Evl_BuildBddForPortRange (int lowPort, int highPort, bdd_manager * bddMgr)
00618 {
00619   assert (!(lowPort > highPort));
00620   assert ((0 <= lowPort) && (lowPort < 65536) &&
00621       (0 <= highPort) && (highPort < 65536));
00622   // use the following relation:
00623   // a <= x <= b  <-> (a <= x) && ( !( b + 1 <= x ) )
00624   bdd_t *t1 = buildBddPort (lowPort, bddMgr, 15);
00625   bdd_t *t2 = buildBddPort (highPort + 1, bddMgr, 15);
00626   bdd_t *t3 = bdd_not (t2);
00627   bdd_t *result = bdd_and (t1, t3, 1, 1);
00628   bdd_free (t1);
00629   bdd_free (t2);
00630   bdd_free (t3);
00631   return result;
00632 }
00633 
00634 
00635 /**
00636   * \brief  Build bdd for the relation X >= A looking 
00637   * at the k least signifincat bits
00638   */
00639 
00640 static bdd_t *
00641 buildBddPort (int lowPort, bdd_manager * bddMgr, int index)
00642 {
00643   bdd_t *t1, *t2, *t3, *t4;
00644   bdd_t *result;
00645 
00646   if (lowPort == 65536)
00647     {
00648       // this is possible, since we do call with highPort + 1 
00649       return bdd_zero (bddMgr);
00650     }
00651   bdd_t *indexVar = bdd_get_variable (bddMgr, 15 - index);
00652 
00653   unsigned int val = (lowPort & ((unsigned int) 1 << index) ? 1 : 0);
00654 
00655   // code implements the following logic:
00656   //
00657   // compute X[index] > a[index]  +  
00658   // X[index] == a[index] . ( X_{index-1} >= a_{index-1} )
00659 
00660   if (index == 0)
00661     {
00662       if (val == 0)
00663     {
00664       bdd_free (indexVar);
00665       return bdd_one (bddMgr);
00666     }
00667       else
00668     {
00669       result = indexVar;
00670       return result;
00671     }
00672     }
00673 
00674   // not looking at index 0
00675   // t1 is  X[index] > a[index]
00676   // t2 is X[index] == a[index]
00677   if (val == 0)
00678     {
00679       t1 = bdd_dup (indexVar);
00680       t2 = bdd_not (indexVar);
00681     }
00682   else
00683     {
00684       t1 = bdd_zero (bddMgr);
00685       t2 = bdd_dup (indexVar);
00686     }
00687   // t3 is ( X_{index-1} >= a_{index-1} )
00688   t3 = buildBddPort (lowPort, bddMgr, index - 1);
00689   t4 = bdd_and (t2, t3, 1, 1);
00690   result = bdd_or (t1, t4, 1, 1);
00691   bdd_free (t1);
00692   bdd_free (t2);
00693   bdd_free (t3);
00694   bdd_free (t4);
00695   bdd_free (indexVar);
00696 
00697   return result;
00698 }
00699 
00700 
00701 /** \brief  Compare function for bdd_t */
00702 
00703 int
00704 Evl_BddCmp (char *aBdd, char *bBdd)
00705 {
00706   int is_complemented;
00707   bdd_node *aNode = bdd_get_node ((bdd_t *) aBdd, &is_complemented);
00708   if (is_complemented)
00709     {
00710       aNode = (bdd_node *) ((unsigned int) aNode ^ (unsigned int) 0x1);
00711     }
00712   bdd_node *bNode = bdd_get_node ((bdd_t *) bBdd, &is_complemented);
00713   if (is_complemented)
00714     {
00715       bNode = (bdd_node *) ((unsigned int) bNode ^ (unsigned int) 0x1);
00716     }
00717   int result = st_numcmp ( (int) aNode, (int) bNode );
00718   return result;
00719 }
00720 
00721 
00722 /**
00723   * \brief Hash function for bdd_t.
00724   * 
00725   *
00726   * Makes use of the bdd_node structure, here's the info from the bdd.doc:
00727   *
00728   * bdd_node *
00729   * bdd_get_node(f, is_complemented)
00730   * bdd_t *f;
00731   * boolean *is_complemented;    
00732   * 
00733   * Return the regularized (i.e. uncomplemented) pointer to the bdd_node
00734   * to which `f' refers.  Also, returns whether or not the bdd_node pointer
00735   * is complemented.  Note well: the address of a bdd_node changes upon
00736   * garbage collection.  If your code is sensitive to the addresses of
00737   * bdd_nodes, and you invoke BDD routines which cause new bdd_nodes to be
00738   * created, then a garbage collection may automatically be triggered.  To
00739   * prevent a garbage collection from automatically occurring, use
00740   * bdd_set_gc_mode to turn off garbage collection before a sensitive piece
00741   * of code is executed.
00742   */
00743 
00744 int
00745 Evl_BddHash (char *aBdd, int modulus)
00746 {
00747   int is_complemented;
00748   bdd_node *aNode = bdd_get_node ((bdd_t *) aBdd, &is_complemented);
00749   if (is_complemented)
00750     {
00751       aNode = (bdd_node *) ((unsigned int) aNode ^ (unsigned int) 0x1);
00752     }
00753   int result = st_numhash ((char *) aNode, modulus);
00754   return result;
00755 }
00756 
00757 
00758 /**
00759   * \brief  Create a lookup table for a set of L4 BDDs.
00760   */
00761 
00762 static void
00763 populateLookupTables (Evl_L4Manager_t * mgr)
00764 {
00765   bdd_t *L4Bdd;
00766   int L4Id;
00767 
00768   array_t *destPortRuleArray = array_alloc (bdd_t *, 0);
00769   array_t *srcPortRuleArray = array_alloc (bdd_t *, 0);
00770   array_t *noPortRuleArray = array_alloc (bdd_t *, 0);
00771 
00772   array_t *destPortRuleVarsArray = array_alloc (bdd_t *, 0);
00773   array_t *srcPortRuleVarsArray = array_alloc (bdd_t *, 0);
00774   array_t *noPortRuleVarsArray = array_alloc (bdd_t *, 0);
00775 
00776   Hash_ForEachItemNew (mgr->distinctL4RulesTable, (char **) &L4Bdd,
00777            (char **) &L4Id)
00778   {
00779     int bddTopVar = bdd_top_var_id (L4Bdd);
00780     if (bddTopVar < 16)
00781       {
00782     // this rule depends on dest port
00783     array_insert_last (bdd_t *, destPortRuleArray, L4Bdd);
00784     bdd_t *ruleVar = bdd_get_variable (mgr->bddMgr, L4Id + 96);
00785     array_insert_last (bdd_t *, destPortRuleVarsArray, ruleVar);
00786       }
00787     else if (bdd_top_var_id (L4Bdd) < 32)
00788       {
00789     // this rule depends on src port but not dest port
00790     array_insert_last (bdd_t *, srcPortRuleArray, L4Bdd);
00791     bdd_t *ruleVar = bdd_get_variable (mgr->bddMgr, L4Id + 96);
00792     array_insert_last (bdd_t *, srcPortRuleVarsArray, ruleVar);
00793       }
00794     else
00795       {
00796     array_insert_last (bdd_t *, noPortRuleArray, L4Bdd);
00797     bdd_t *ruleVar = bdd_get_variable (mgr->bddMgr, L4Id + 96);
00798     array_insert_last (bdd_t *, noPortRuleVarsArray, ruleVar);
00799       }
00800   }
00801 
00802   if (array_n (destPortRuleVarsArray) > 0)
00803     {
00804       mgr->destPortRuleTable =
00805     createLookupTable (mgr, destPortRuleArray, destPortRuleVarsArray);
00806     }
00807   if (array_n (srcPortRuleVarsArray) > 0)
00808     {
00809       mgr->srcPortRuleTable =
00810     createLookupTable (mgr, srcPortRuleArray, srcPortRuleVarsArray);
00811     }
00812   if (array_n (noPortRuleVarsArray) > 0)
00813     {
00814       mgr->noPortRuleTable =
00815     createLookupTable (mgr, noPortRuleArray, noPortRuleVarsArray);
00816     }
00817 
00818   buildNoContentCheckTable (mgr);
00819   buildShortStringLookupTable (mgr);
00820 }
00821 
00822 
00823 /**
00824   * \brief  Build the actual lookup table
00825   */
00826 
00827 static Evl_L4LookupTable_t *
00828 createLookupTable (Evl_L4Manager_t * mgr,
00829            array_t * L4BddArray, array_t * ruleVarArray)
00830 {
00831   bdd_t *L4Rule;
00832   int L4Id;
00833   bdd_t *TR = bdd_one (mgr->bddMgr);
00834   bdd_t *t1;
00835 
00836   int i;
00837   for (i = 0; i < array_n (L4BddArray); i++)
00838     {
00839       L4Rule = array_fetch (bdd_t *, L4BddArray, i);
00840       Hash_Lookup (mgr->distinctL4RulesTable, (char *) L4Rule, (char **) &L4Id);
00841       bdd_t *L4RuleVar = bdd_get_variable (mgr->bddMgr, 96 + L4Id);
00842 
00843       bdd_t *thisRelation = bdd_xnor (L4RuleVar, L4Rule);
00844       t1 = bdd_and (TR, thisRelation, 1, 1);
00845       bdd_free (thisRelation);
00846       bdd_free (TR);
00847       bdd_free (L4RuleVar);
00848       TR = t1;
00849     }
00850 
00851   Evl_L4LookupTable_t *result =
00852     Evl_RuleRelationToLookupTable (TR, mgr, ruleVarArray);
00853 
00854   return result;
00855 }
00856 
00857 
00858 /**
00859   * \brief  Find the longest path to 1 terminal in a BDD, length
00860   * is the number of then-edges.
00861   */
00862 
00863 static int
00864 longestPathToOne (bdd_t * aBdd, int descend)
00865 {
00866   if (bdd_is_tautology (aBdd, 1))
00867     {
00868       return 0;
00869     }
00870   if (bdd_is_tautology (aBdd, 0))
00871     {
00872       return -100000;
00873     }
00874   bdd_t *bddThen = bdd_then (aBdd);
00875   bdd_t *bddElse = bdd_else (aBdd);
00876 
00877   int left = longestPathToOne (bdd_else (aBdd), 0);
00878   int right = longestPathToOne (bdd_then (aBdd), 0);
00879 
00880   // aBdd cannot be a 0/1 if we're here
00881   int aBddId = bdd_top_var_id (aBdd);
00882 
00883   if (bdd_is_tautology (bddElse, 1))
00884     {
00885       int totalNumVars = bdd_num_vars (bdd_get_manager (aBdd));
00886       left = (left) + ((totalNumVars - aBddId) - 1);
00887     }
00888   else
00889     {
00890       int bddElseId = bdd_top_var_id (bddElse);
00891       left = (left) + ((bddElseId - aBddId) - 1);
00892     }
00893   if (bdd_is_tautology (bddThen, 1))
00894     {
00895       int totalNumVars = bdd_num_vars (bdd_get_manager (aBdd));
00896       right = (right) + ((totalNumVars - aBddId) - 1);
00897     }
00898   else
00899     {
00900       int bddThenId = bdd_top_var_id (bddThen);
00901       right = (right) + ((bddThenId - aBddId) - 1);
00902     }
00903 
00904   if (left < right + 1)
00905     {
00906       if (descend == 1)
00907     {
00908       printf ("Take r_%d to be 1\n", bdd_top_var_id (aBdd));
00909       longestPathToOne (bdd_then (aBdd), 1);
00910     }
00911       return right + 1;
00912     }
00913   else
00914     {
00915       if (descend == 1)
00916     {
00917       printf ("Take r_%d to be 0\n", bdd_top_var_id (aBdd));
00918       longestPathToOne (bdd_else (aBdd), 1);
00919     }
00920       return left;
00921     }
00922 }
00923 
00924 
00925 /**
00926   * \brief  Print all the cubes in a BDD
00927   * 
00928   * Useful for debugging, e.g., seeing all classes.
00929   */
00930 
00931 static void
00932 printCubes (bdd_t * aBdd)
00933 {
00934   bdd_gen *bddGen;
00935   array_t *cube;
00936   int i;
00937   int literal;
00938   int count = 0;
00939   int start;
00940 
00941   bddGen = bdd_first_cube (aBdd, &cube);
00942   int totalLiteralsEqOne = 0;
00943 
00944   while (1)
00945     {
00946       count++;
00947       start = 0;
00948       for (i = 0; i < array_n (cube); i++)
00949     {
00950       literal = array_fetch (int, cube, i);
00951       if (literal == 1 || literal == 0)
00952         {
00953           printf ("%s", literal ? "1" : "");
00954           totalLiteralsEqOne += (literal == 1) ? 1 : 0;
00955           start = 1;
00956         }
00957     }
00958       printf ("\n");
00959       if (count % 1000 == 0)
00960     printf ("Completed %d cubes\n", count);
00961       if (!bdd_next_cube (bddGen, &cube))
00962     {
00963       break;
00964     }
00965     }
00966   printf ("Counted %d cubes, with a total of %d literals\n", count,
00967       totalLiteralsEqOne);
00968 }
00969 
00970 
00971 /**
00972   * \brief  Build a lookup table from the rule relation BDD
00973   * 
00974   * \pre First 96 vars are dest port, src port, dest ip, src ip. 
00975   * 
00976   * We're going to return an array that will be used
00977   * to represent a 256-ary tree mapping IP headers to 
00978   * bit-vectors whose length is equal to the number of
00979   * distinct L4 rules.
00980   */
00981 
00982 Evl_L4LookupTable_t *
00983 Evl_RuleRelationToLookupTable (bdd_t * TR,
00984                    Evl_L4Manager_t * L4Mgr,
00985                    array_t * ruleVarArray)
00986 {
00987   int offset = 96;
00988   array_t *origVarArray = array_alloc (bdd_t *, 0);
00989   int i;
00990   bdd_manager *bddMgr = L4Mgr->bddMgr;
00991 
00992   for (i = 0; i < offset; i++)
00993     {
00994       array_insert_last (bdd_t *, origVarArray, bdd_get_variable (bddMgr, i));
00995     }
00996 
00997   bdd_t *classBdd = bdd_smooth (TR, origVarArray);
00998   // printf("Class mdd has %d nodes\n", bdd_size( classBdd ) );
00999   bddArrayFree (origVarArray);
01000 
01001   int numClasses = (int) bdd_count_onset (classBdd, ruleVarArray);
01002   // printf("Number of classes = %.d\n", numClasses );
01003   bddArrayFree (ruleVarArray);
01004 
01005   // bdd_print(  classBdd  );
01006   // printCubes(  classBdd  );
01007   // printf("---\n");
01008   // printf("Longest path to 1 has %d terms\n", longestPathToOne( classBdd, 1 ) );
01009 
01010   bdd_set_gc_mode (bddMgr, 1);
01011 
01012   st_table *allDecisionNodes =
01013     Hash_InitTable (  (int(*)() ) Evl_BddLevelPairCmp, (int(*)() ) Evl_BddLevelPairHash);
01014   st_table *canonicalMap =
01015     Hash_InitTable ( (int(*)() ) Evl_BddLevelPairCmp, (int(*)())  Evl_BddLevelPairHash);
01016   Evl_BddLevelPair_t *root = Evl_CreateBddLevelPair (TR, 0);
01017   populateDecisionNodeTable (root, allDecisionNodes, canonicalMap);
01018   // printf("Total number of nodes in the final tree = %d\n", st_count( allDecisionNodes ) );
01019 
01020   // clear out the cache
01021   getCofactorCube (0, 0, bddMgr, true);
01022   // clear out the canonical map
01023   Hash_FreeTable (canonicalMap);
01024 
01025   Evl_L4LookupTable_t *result =
01026     Evl_L4BuildLookup (root, numClasses, L4Mgr, allDecisionNodes);
01027 
01028   st_generator *stGen;
01029   Evl_BddLevelPair_t *tmpPair;
01030   Evl_BddLevelPair_t **tmpChildArray;
01031   st_foreach_item (allDecisionNodes, stGen, (char **) &tmpPair,
01032            (char **) &tmpChildArray)
01033   {
01034     if (tmpPair->level == 88)
01035       {
01036     // if they are at level 88, then their children are not in the 
01037     // table, and must be freed explicilty 
01038     int l;
01039     for (l = 0; l < 256; l++)
01040       {
01041         bdd_free (tmpChildArray[l]->bdd);
01042         free (tmpChildArray[l]);
01043       }
01044       }
01045     bdd_free (tmpPair->bdd);
01046     free (tmpPair);
01047     free (tmpChildArray);
01048   }
01049   Hash_FreeTable (allDecisionNodes);
01050 
01051   return result;
01052 }
01053 
01054 
01055 /**
01056   * \brief  Get bdd_t's for all distinct BDD nodes at levels
01057   * 0,8,...,88 in the given BDD.
01058   * 
01059   * Return 1 if the node
01060   * is already present in the all decision noes table, 
01061   * 0 if its a terminal level 96) or was not present.
01062   */
01063 
01064 static int
01065 populateDecisionNodeTable (Evl_BddLevelPair_t * aBddLevelPair,
01066                st_table * allDecisionNodes,
01067                st_table * canonicalMap)
01068 {
01069   static int totalCalls = 0;
01070   if (false && (totalCalls % 100000) == 0)
01071     {
01072       printf ("Total calls to populateDecisionNodeTable = %d\n",
01073           totalCalls++);
01074     }
01075   totalCalls++;
01076   bdd_t *aRelation = aBddLevelPair->bdd;
01077   int decisionLevel = aBddLevelPair->level;
01078 
01079   static int cacheHits = 0;
01080   if (Hash_Lookup (allDecisionNodes, (char *) aBddLevelPair, (char **) 0))
01081     {
01082       if (false && (cacheHits % 10000) == 0)
01083     printf
01084       ("Cache hit: %d total calls of which %d cache hits, table has %d entries, decision level %d\n",
01085        totalCalls, cacheHits, st_count (allDecisionNodes), decisionLevel);
01086       cacheHits++;
01087       return 1;
01088     }
01089   if (decisionLevel > 88)
01090     {
01091       return 0;
01092     }
01093   Evl_BddLevelPair_t **childrenArray =
01094     (Evl_BddLevelPair_t **) malloc (256 * sizeof (Evl_BddLevelPair_t));
01095   Hash_Insert (allDecisionNodes, (char *) aBddLevelPair,
01096          (char *) childrenArray);
01097   Hash_Insert (canonicalMap, (char *) aBddLevelPair, (char *) aBddLevelPair);
01098   bdd_manager *bddMgr = bdd_get_manager (aRelation);
01099   int i;
01100   for (i = 0; i < 256; i++)
01101     {
01102       bdd_t *cofactorCube = getCofactorCube (decisionLevel, i, bddMgr, false);
01103       bdd_t *aCofactor = bdd_cofactor (aRelation, cofactorCube);
01104       // printf("Printing a cofactored BDD at level %d, number %d\n", decisionLevel, i);
01105       // bdd_print( aCofactor );
01106       // don't free since we're caching  
01107       // bdd_free( cofactorCube );
01108       // cannot free aCofactor either since it's in the bdd-level pair struct
01109       Evl_BddLevelPair_t *aCofactorLevelPair =
01110     Evl_CreateBddLevelPair (aCofactor, decisionLevel + 8);
01111       if (populateDecisionNodeTable
01112       (aCofactorLevelPair, allDecisionNodes, canonicalMap))
01113     {
01114       // it was already in the cache, so free it
01115       Evl_BddLevelPair_t *tmpPair;
01116       Hash_Lookup (canonicalMap, (char *) aCofactorLevelPair,
01117              (char **) &tmpPair);
01118       bdd_free (aCofactorLevelPair->bdd);
01119       free (aCofactorLevelPair);
01120       // set aCofactorLevelPair to the canonical entry
01121       aCofactorLevelPair = tmpPair;
01122     }
01123       childrenArray[i] = aCofactorLevelPair;
01124     }
01125   return 0;
01126 }
01127 
01128 
01129 /**
01130   * \brief  Build a bdd cube based on the level and value information 
01131   * passed in
01132   */
01133 
01134 static bdd_t *
01135 getCofactorCube (int decisionLevel,
01136          int value, bdd_manager * bddMgr, bool clearCache)
01137 {
01138   int i;
01139   bdd_t *result;
01140   bdd_t *t1;
01141   static st_table *cache = NIL (st_table);
01142   unsigned int key;
01143 
01144   if (clearCache)
01145     {
01146       st_generator *stGen;
01147       st_foreach_item (cache, stGen, (char **) &key, (char **) &t1)
01148       {
01149     bdd_free (t1);
01150       }
01151       Hash_FreeTable (cache);
01152       cache = NIL (st_table);
01153       return NIL (bdd_t);
01154     }
01155 
01156   if (!cache)
01157     {
01158       cache = Hash_InitTable ( (int(*)() ) st_numcmp, (int(*)() ) st_numhash);
01159     }
01160   key = decisionLevel * 256 + value;
01161   if (Hash_Lookup (cache, (char *) key, (char **) &result))
01162     {
01163       // printf("Cache hit in cofactor cache, level %d, value %d\n", 
01164       //         decisionLevel, value );
01165       return result;
01166     }
01167   // printf("No cache hit in cofactor cache, processing level %d, value %d\n", 
01168   //           decisionLevel, value );
01169 
01170   result = bdd_one (bddMgr);
01171   for (i = 0; i < 8; i++)
01172     {
01173       bdd_t *var = bdd_get_variable (bddMgr, decisionLevel + (7 - i));
01174       bdd_t *notVar = bdd_not (var);
01175       bool bitI = (((1 << i) & value) == 0) ? false : true;
01176       if (bitI)
01177     {
01178       t1 = bdd_and (result, var, 1, 1);
01179     }
01180       else
01181     {
01182       t1 = bdd_and (result, notVar, 1, 1);
01183     }
01184       bdd_free (result);
01185       bdd_free (var);
01186       bdd_free (notVar);
01187       result = t1;
01188     }
01189   Hash_Insert (cache, (char *) key, (char *) result);
01190   // printf("Printing result of getCofactorCube at decision level %d"
01191   // "and value %d\n", decisionLevel, value );
01192   // bdd_print( result );
01193   return result;
01194 }
01195 
01196 
01197 /**
01198   * \brief  Build the L4 lookup array
01199   */
01200 
01201 Evl_L4LookupTable_t *
01202 Evl_L4BuildLookup (Evl_BddLevelPair_t * root,
01203            int numClasses,
01204            Evl_L4Manager_t * L4Mgr, st_table * allDecisionNodes)
01205 {
01206   Evl_L4LookupTable_t *result =
01207     (Evl_L4LookupTable_t *) malloc (sizeof (Evl_L4LookupTable_t));
01208 
01209   result->tree =
01210     (int *) malloc (256 * st_count (allDecisionNodes) * sizeof (int));
01211   result->numClasses = numClasses;
01212   result->ruleSets =
01213     (var_set_t **) malloc (numClasses * sizeof (var_set_t *));
01214   result->ruleArrays = NIL (util_int_array_t *);
01215 
01216   st_table *nodeToIdTable =
01217     Hash_InitTable ( (int(*)() ) Evl_BddLevelPairCmp,  (int(*)() ) Evl_BddLevelPairHash);
01218   populateNodeToIdTable (root, allDecisionNodes, nodeToIdTable);
01219   // printf("Size of allDecisionNodes table is %d\n", st_count( allDecisionNodes ) );
01220 
01221   st_table *leafNodeToIdTable =
01222     Hash_InitTable ( (int(*)() ) Evl_BddLevelPairCmp, (int(*)() ) Evl_BddLevelPairHash);
01223   st_table *idToLeafNodeTable = Hash_InitTable ( (int(*)() ) st_numcmp, (int(*)() ) st_numhash);
01224 
01225   int i;
01226   int childId;
01227   int leafId;
01228   int aNodeId;
01229   Evl_BddLevelPair_t *aNodeLevelPair;
01230   Evl_BddLevelPair_t *child;
01231   Evl_BddLevelPair_t **childrenArray;
01232   st_generator *stGen;
01233 
01234   st_foreach_item (allDecisionNodes, stGen, (char **) &aNodeLevelPair,
01235            (char **) &childrenArray)
01236   {
01237     Hash_Lookup (nodeToIdTable, (char *) aNodeLevelPair, (char **) &aNodeId);
01238     for (i = 0; i < 256; i++)
01239       {
01240     child = childrenArray[i];
01241     if (Hash_Lookup (nodeToIdTable, (char *) child, (char **) &childId))
01242       {
01243         // it's an internal node
01244         result->tree[aNodeId * 256 + i] = childId;
01245       }
01246     else
01247       {
01248         // must be a leaf node
01249         if (!Hash_Lookup
01250         (leafNodeToIdTable, (char *) child, (char **) &leafId))
01251           {
01252         // create an id for it 
01253         leafId = st_count (leafNodeToIdTable);
01254         Hash_Insert (leafNodeToIdTable, (char *) child,
01255                (char *) leafId);
01256         Hash_Insert (idToLeafNodeTable, (char *) leafId,
01257                (char *) child);
01258           }
01259         result->tree[aNodeId * 256 + i] = leafId;
01260       }
01261       }             // st_foreach_item
01262   }
01263 
01264   // now set each leaf node to the set of rules in that equivalence class
01265   Evl_BddLevelPair_t *leafBddLevelPair;
01266   var_set_t **ruleSets = result->ruleSets;
01267   for (i = 0; i < numClasses; i++)
01268     {
01269       Hash_Lookup (idToLeafNodeTable, (char *) i, (char **) &leafBddLevelPair);
01270       ruleSets[i] = classBddToSet (leafBddLevelPair->bdd, L4Mgr);
01271     }
01272 
01273   // printf("The table has %d classes\n", numClasses );
01274   // printf("Total number of nodes in the final table = %d\n",
01275   //     st_count( allDecisionNodes ) );
01276 
01277   Hash_FreeTable (nodeToIdTable);
01278   Hash_FreeTable (leafNodeToIdTable);
01279   Hash_FreeTable (idToLeafNodeTable);
01280 
01281   return result;
01282 }
01283 
01284 
01285 /**
01286   * \brief  Instantiate a table of bddNodes to int id.
01287   */
01288 
01289 static void
01290 populateNodeToIdTable (Evl_BddLevelPair_t * root,
01291                st_table * allDecisionNodes, st_table * nodeToIdTable)
01292 {
01293   // static int numCalls=0;
01294   // if ( numCalls % 1000 == 0 ) {
01295   //  printf("There have been %d calls to populateNodeToIdTable, and" 
01296   //            "the table size is %d\n", numCalls, st_count( allDecisionNodes ) );
01297   // }
01298   // numCalls++;
01299 
01300   // static int numCacheHits = 0;
01301   // if ( numCacheHits % 1000 == 0 ) {
01302   //  printf("There have been %d"
01303   //            "cache hits (out of %d calls),"
01304   //            "the table size is %d\n", 
01305   //             numCacheHits, numCalls, st_count( allDecisionNodes ) );
01306   // }
01307 
01308   if (Hash_Lookup (nodeToIdTable, (char *) root, (char **) 0))
01309     {
01310       return;
01311     }
01312 
01313   if (root->level > 88)
01314     {
01315       // this is a terminal, hence we return
01316       return;
01317     }
01318 
01319   Evl_BddLevelPair_t **childrenArray;
01320   Hash_Lookup (allDecisionNodes, (char *) root, (char **) &childrenArray);
01321   int id = st_count (nodeToIdTable);
01322   Hash_Insert (nodeToIdTable, (char *) root, (char *) id);
01323 
01324   int i;
01325   for (i = 0; i < 256; i++)
01326     {
01327       Evl_BddLevelPair_t *aChild = childrenArray[i];
01328       populateNodeToIdTable (aChild, allDecisionNodes, nodeToIdTable);
01329     }
01330 }
01331 
01332 
01333 /**
01334   * \brief  Create a var set representing the set of rules that
01335   * are encoded by a given BDD
01336   * 
01337   * BDD is assumed to be
01338   * only over the rule vars, and encodes a SINGLE minterm.
01339   * The result a var_set over the set of all rules, not 
01340   * just distinct L4 rules.
01341   */
01342 
01343 static var_set_t *
01344 classBddToSet (bdd_t * leafBdd, Evl_L4Manager_t * L4Mgr)
01345 {
01346   int numL4Rules = L4Mgr->numDistinctL4Rules;
01347   assert (L4Mgr->numDistinctL4Rules ==
01348       st_count (L4Mgr->distinctL4RulesTable));
01349 
01350   var_set_t *L4Rules = var_set_new (numL4Rules);
01351   int i;
01352   bdd_t *t1 = bdd_dup (leafBdd);
01353   // printf("Printing what's supposed to be a leafBdd\n");
01354   // bdd_print( t1 );
01355   while (1)
01356     {
01357       if (bdd_is_tautology (t1, 1))
01358     {
01359       break;
01360     }
01361       bdd_t *bddThen = bdd_then (t1);
01362       bdd_t *bddElse = bdd_else (t1);
01363       assert (bdd_is_tautology (bddThen, 0) || bdd_is_tautology (bddElse, 0));
01364       if (!bdd_is_tautology (bddThen, 0))
01365     {
01366       // the rule corresponding to t1 is in the set
01367       int thisRule = bdd_top_var_id (t1);
01368       var_set_set_elt (L4Rules, thisRule - 96);
01369       bdd_free (t1);
01370       t1 = bddThen;
01371       bdd_free (bddElse);
01372     }
01373       else
01374     {
01375       bdd_free (t1);
01376       t1 = bddElse;
01377       bdd_free (bddThen);
01378     }
01379     }
01380   bdd_free (t1);
01381 
01382   var_set_t *result = var_set_new (L4Mgr->numAllRules);
01383   for (i = 0; i < numL4Rules; i++)
01384     {
01385       if (var_set_get_elt (L4Rules, i))
01386     {
01387       var_set_t *L7rulesForThisL4Rule =
01388         array_fetch (var_set_t *, L4Mgr->L4RuleIdToL7ruleSetTable, i);
01389       result = var_set_or (result, result, L7rulesForThisL4Rule);
01390     }
01391     }
01392   var_set_free (L4Rules);
01393 
01394   return result;
01395 }
01396 
01397 
01398 /**
01399   * \brief  Allocate and populate a bdd-and-level struct.
01400   */
01401 
01402 Evl_BddLevelPair_t *
01403 Evl_CreateBddLevelPair (bdd_t * aBdd, int level)
01404 {
01405   Evl_BddLevelPair_t *result =
01406     (Evl_BddLevelPair_t *) malloc (sizeof (Evl_BddLevelPair_t));
01407 
01408   result->bdd = aBdd;
01409   result->level = level;
01410   return result;
01411 }
01412 
01413 
01414 /**
01415   * \brief  Hash function for a bdd-level pair
01416   */
01417 
01418 int
01419 Evl_BddLevelPairHash (char *aPtr, int modulus)
01420 {
01421   Evl_BddLevelPair_t *aBddAndLevelObj = (Evl_BddLevelPair_t *) aPtr;
01422   int bddHashCode = Evl_BddHash ((char *) aBddAndLevelObj->bdd, modulus);
01423   int levelHash = st_numhash ((char *) aBddAndLevelObj->level, modulus);
01424 
01425   int result =
01426     st_numhash ((char *) (3 * bddHashCode + 5 * levelHash), modulus);
01427 
01428   return result;
01429 }
01430 
01431 
01432 /**
01433   * \brief  Compare function for a bdd-level pair
01434   */
01435 
01436 int
01437 Evl_BddLevelPairCmp (char *aPtr, char *bPtr)
01438 {
01439   Evl_BddLevelPair_t *aBddLevelPair = (Evl_BddLevelPair_t *) aPtr;
01440   Evl_BddLevelPair_t *bBddLevelPair = (Evl_BddLevelPair_t *) bPtr;
01441 
01442   if (aBddLevelPair->level < bBddLevelPair->level)
01443     {
01444       return -1;
01445     }
01446   if (aBddLevelPair->level > bBddLevelPair->level)
01447     {
01448       return 1;
01449     }
01450   return Evl_BddCmp ((char *) aBddLevelPair->bdd,
01451              (char *) bBddLevelPair->bdd);
01452 }
01453 
01454 
01455 /**
01456   * \brief  Allocate and initialize manager for generic rules
01457   */
01458 
01459 static Evl_GenericManager_t *
01460 Evl_GenericManagerAlloc (Evl_Manager_t * mgr)
01461 {
01462   Evl_GenericManager_t *result =
01463     (Evl_GenericManager_t *) malloc (sizeof (Evl_GenericManager_t));
01464   result->mgr = mgr;
01465   result->numAllRules = 0;
01466   result->tcpIdToGlobalId = array_alloc (int, 0);
01467   result->L7RuleArray = array_alloc (int, 0);
01468 
01469   int i;
01470   for (i = 0; i < array_n (mgr->rawRules); i++)
01471     {
01472       char *rawRule = array_fetch (char *, mgr->rawRules, i);
01473       while (*rawRule == ' ')
01474     {
01475       rawRule++;
01476     }
01477       if (!util_strequalN (rawRule, "generic", strlen ("generic")))
01478     {
01479       continue;
01480     }
01481       array_insert_last (int, result->tcpIdToGlobalId, i);
01482       char *L7component = Rlp_GetL7ComponentFromRawRule (rawRule);
01483       Rlp_Formula_t *L7Formula = Rlp_CreateParseTreeFromText (L7component);
01484       array_insert_last (Rlp_Formula_t *, result->L7RuleArray, L7Formula);
01485       result->numAllRules++;
01486     }
01487 
01488   return result;
01489 }
01490 
01491 
01492 /**
01493   * \brief  Allocate and initialize a TCP manager
01494   */
01495 
01496 Evl_L4Manager_t *
01497 Evl_L4ManagerAlloc (Evl_Manager_t * mgr, char *mode)
01498 {
01499   Evl_L4Manager_t *result =
01500     (Evl_L4Manager_t *) malloc (sizeof (Evl_L4Manager_t));
01501   result->mgr = mgr;
01502 
01503   result->tcpIdToGlobalId = array_alloc (int, 0);
01504 
01505   result->L4RuleArray = array_alloc (Rlp_L4Check_t *, 0);
01506   result->L7RuleArray = array_alloc (Rlp_Formula_t *, 0);
01507   result->cm = NIL (Evl_ContentMgr_t);
01508 
01509   result->numAllRules = 0;
01510   int i;
01511   for (i = 0; i < array_n (mgr->rawRules); i++)
01512     {
01513       char *rawRule = array_fetch (char *, mgr->rawRules, i);
01514       while (*rawRule == ' ')
01515     {
01516       rawRule++;
01517     }
01518       // if ( !util_strequalN( rawRule, mode, strlen( mode ) ) ) {
01519       if (!checkRuleMode (rawRule, mode))
01520     {
01521       continue;
01522     }
01523       array_insert_last (int, result->tcpIdToGlobalId, i);
01524       result->numAllRules++;
01525 
01526       char *L4component = Rlp_GetL4ComponentFromRawRule (rawRule);
01527       char *L7component = Rlp_GetL7ComponentFromRawRule (rawRule);
01528       Rlp_L4Check_t *L4Formula =
01529     Rlp_CreateL4CheckFromRawFormula (L4component);
01530       array_insert_last (Rlp_L4Check_t *, result->L4RuleArray, L4Formula);
01531       Rlp_Formula_t *L7Formula = Rlp_CreateParseTreeFromText (L7component);
01532       array_insert_last (Rlp_Formula_t *, result->L7RuleArray, L7Formula);
01533     }
01534 
01535   result->bddMgr = bdd_start (32 + 16 + 32 + 16);
01536 
01537   result->numDistinctL4Rules = 0;
01538   result->distinctL4RulesTable = Hash_InitTable ( (int(*)() ) Evl_BddCmp, (int(*)() ) Evl_BddHash);
01539   result->L4RuleIdToL7ruleSetTable = array_alloc (var_set_t *, 0);
01540   result->ruleToL4Bdd = array_alloc (bdd_t *, 0);
01541 
01542   result->destPortRuleTable = NIL (Evl_L4LookupTable_t);
01543   result->srcPortRuleTable = NIL (Evl_L4LookupTable_t);
01544   result->noPortRuleTable = NIL (Evl_L4LookupTable_t);
01545 
01546   result->noContentCheckTable = NIL (Evl_L4LookupTable_t);
01547   result->shortStringRuleTable = NIL (Evl_L4LookupTable_t);
01548 
01549   result->potentialRulesFromFsm = NIL (array_t);
01550   result->rulesFromFsm = NIL (array_t);
01551   result->rulesFromShortStringTable = NIL (array_t);
01552   result->rulesFromNoContentTable = NIL (array_t);
01553 
01554   return result;
01555 }
01556 
01557 
01558 /**
01559   * \brief  Allocate and initialize a manager
01560   */
01561 
01562 Evl_Manager_t *
01563 Evl_ManagerAlloc ()
01564 {
01565   Evl_Manager_t *result = (Evl_Manager_t *) malloc (sizeof (Evl_Manager_t));
01566 
01567   result->rawRules = array_alloc (char *, 0);
01568   result->rlpActionArray = array_alloc (Rlp_Action_t *, 0);
01569   result->actionArray = array_alloc (Evl_Action_t *, 0);
01570   result->ucodeNameToFunction = Hash_InitTable ( (int(*)() ) strcmp, (int(*)() ) st_strhash);
01571   result->defineTable = Hash_InitTable ( (int(*)() ) strcmp, (int(*)() ) st_strhash);
01572 
01573   result->numPreprocessRules = 0;
01574   result->indexFirstContentRule = -1;
01575   result->indexLastContentRule = -1;
01576 
01577   result->numAllRules = 0;
01578   result->bridge = NIL (Evl_Bridge_t);
01579 
01580   result->queueTable = Hash_InitTable ( (int(*)() ) strcmp, (int(*)() ) st_strhash);
01581   result->qHeap = NIL (Heap_t);
01582 
01583   result->preprocessorResult = NIL (array_t);
01584   result->genericResult = NIL (array_t);
01585   result->layer3Result = NIL (array_t);
01586   result->layer4Result = NIL (array_t);
01587 
01588   return result;
01589 }
01590 
01591 
01592 /**
01593   * \brief  Add a queue to the set of queues.
01594   * 
01595   * anEntry looks like "queue qname classes:5
01596   * 
01597   */
01598 
01599 static int
01600 addQueue (st_table * queueNameToQueueTable, char *anEntry)
01601 {
01602   char varBuf[1000];
01603   // need the + 1 to get past the blank space
01604   char *beginSymbolPtr = anEntry + strlen ("queue") + 1;
01605   char *endSymbolPtr = strchr (beginSymbolPtr, ' ');
01606   int length = endSymbolPtr - beginSymbolPtr;
01607   strncpy (varBuf, beginSymbolPtr, length);
01608   varBuf[length] = '\0';
01609   char *queueName = strdup (varBuf);
01610 
01611   while (isspace (*endSymbolPtr))
01612     {
01613       endSymbolPtr++;
01614     }
01615   char *queueDefn = strdup (endSymbolPtr);
01616   // remove any trailing whitespace
01617   char *tmpPtr = queueDefn + strlen (queueDefn) - 1;
01618   while (isspace (*tmpPtr))
01619     {
01620       *tmpPtr = '\0';
01621       tmpPtr--;
01622     }
01623   // need to parse queueDefn and create the Q_Q_t struct
01624   Q_Q_t *aQ = Q_AllocQ (queueName);
01625   // overkill to call Rlp_L7StringParse, (no quotes/escapes) but it's easier this way
01626   array_t *attributesArray = Rlp_L7StringParse (queueDefn);
01627   int i;
01628   for (i = 0; i < array_n (attributesArray); i++)
01629     {
01630       Rlp_RuleComponent_t *aComponent = array_fetch (Rlp_RuleComponent_t *,
01631                              attributesArray, i);
01632       char *attribute = aComponent->rawAttribute;
01633       char *value = aComponent->rawValue;
01634 
01635       if (util_strequal (attribute, "type"))
01636     {
01637       if (util_strequal (value, "cos"))
01638         {
01639           aQ->type = Q_QueueTypeCos_c;
01640         }
01641       else if (util_strequal (value, "flow"))
01642         {
01643           aQ->type = Q_QueueTypeFlow_c;
01644         }
01645       else
01646         {
01647           printf ("Unrecognized type of queue - %s\n", value);
01648           assert (0);
01649         }
01650     }
01651       else if (util_strequal (attribute, "numclasses"))
01652     {
01653       sscanf (value, "%d", &aQ->numClasses);
01654     }
01655       else if (util_strequal (attribute, "priority"))
01656     {
01657       sscanf (value, "%d", &aQ->assignedPriority);
01658     }
01659       else if (util_strequal (attribute, "windowduration"))
01660     {
01661       sscanf (value, "%lf", &aQ->timeWindowDuration);
01662     }
01663       else if (util_strequal (attribute, "maxrate"))
01664     {
01665       sscanf (value, "%d", &aQ->maxRate);
01666     }
01667       else if (util_strequal (attribute, "flowmaxrate"))
01668     {
01669       sscanf (value, "%d", &aQ->flowMaxRate);
01670     }
01671       else if (util_strequal (attribute, "maxbytes"))
01672     {
01673       sscanf (value, "%d", &aQ->maxAllowedBytes);
01674     }
01675       else if (util_strequal (attribute, "maxflows"))
01676     {
01677       sscanf (value, "%d", &aQ->maxFlows);
01678     }
01679       else if (util_strequal (attribute, "maxbytesperflow"))
01680     {
01681       sscanf (value, "%d", &aQ->maxBytesPerFlow);
01682     }
01683       else if (util_strequal (attribute, "flowdrop"))
01684     {
01685       if (util_strequal (value, "red"))
01686         {
01687           aQ->flowDropMethod = Q_DropRed_c;
01688         }
01689       else if (util_strequal (value, "tail"))
01690         {
01691           aQ->flowDropMethod = Q_DropTail_c;
01692         }
01693       else
01694         {
01695           fprintf (stderr, "Don't support flow drop method %s\n", value);
01696           assert (0);
01697         }
01698     }
01699       else if (util_strequal (attribute, "drop"))
01700     {
01701       if (util_strequal (value, "red"))
01702         {
01703           aQ->dropMethod = Q_DropRed_c;
01704         }
01705       else if (util_strequal (value, "tail"))
01706         {
01707           aQ->dropMethod = Q_DropTail_c;
01708         }
01709       else
01710         {
01711           fprintf (stderr, "Don't support drop method %s\n", value);
01712           assert (0);
01713         }
01714     }
01715       else if (util_strequal (attribute, "flowtype"))
01716     {
01717       if (util_strequal (value, "srcip"))
01718         {
01719           aQ->flowType = Pkt_SrcIpFlow_c;
01720         }
01721       else if (util_strequal (value, "destip"))
01722         {
01723           aQ->flowType = Pkt_DestIpFlow_c;
01724         }
01725       else if (util_strequal (value, "srcdestip"))
01726         {
01727           aQ->flowType = Pkt_SrcDestIpFlow_c;
01728         }
01729       else if (util_strequal (value, "srcdesttcpip"))
01730         {
01731           aQ->flowType = Pkt_SrcDestTcpIpFlow_c;
01732         }
01733       else if (util_strequal (value, "desttcpip"))
01734         {
01735           aQ->flowType = Pkt_DestTcpIpFlow_c;
01736         }
01737       else
01738         {
01739           printf ("Unknown flowtype:%s\n", value);
01740           assert (0);
01741         }
01742     }
01743       else
01744     {
01745       printf ("PANIC: Don't support construct %s in queue definition\n",
01746           attribute);
01747       assert (0);
01748     }
01749     }
01750 
01751   if (aQ->type == Q_QueueTypeCos_c)
01752     {
01753       if (aQ->numClasses == -1)
01754     {
01755       printf ("Panic, did not assigned number of classes for queue\n");
01756       assert (0);
01757     }
01758       else
01759     {
01760       aQ->cosQ = Q_CosAlloc (aQ->numClasses);
01761     }
01762     }
01763   else if (aQ->type == Q_QueueTypeFlow_c)
01764     {
01765       if (aQ->flowType == Pkt_SrcIpFlow_c)
01766     {
01767       aQ->flowQ = Q_DrrAlloc (Pkt_SrcIpFlowCmp, Pkt_SrcIpFlowHash);
01768     }
01769       else if (aQ->flowType == Pkt_DestIpFlow_c)
01770     {
01771       aQ->flowQ = Q_DrrAlloc (Pkt_DestIpFlowCmp, Pkt_DestIpFlowHash);
01772     }
01773       else if (aQ->flowType == Pkt_SrcDestIpFlow_c)
01774     {
01775       aQ->flowQ =
01776         Q_DrrAlloc (Pkt_SrcDestIpFlowCmp, Pkt_SrcDestIpFlowHash);
01777     }
01778       else if (aQ->flowType == Pkt_DestTcpIpFlow_c)
01779     {
01780       aQ->flowQ =
01781         Q_DrrAlloc (Pkt_DestTcpIpFlowCmp, Pkt_DestTcpIpFlowHash);
01782     }
01783       else if (aQ->flowType == Pkt_SrcDestTcpIpFlow_c)
01784     {
01785       aQ->flowQ =
01786         Q_DrrAlloc (Pkt_SrcDestTcpIpFlowCmp, Pkt_SrcDestTcpIpFlowHash);
01787     }
01788       else
01789     {
01790       assert (0);
01791     }
01792     }
01793   else
01794     {
01795       printf ("Panic, queue %s does not have meaningful type\n", aQ->name);
01796     }
01797   Hash_Insert (queueNameToQueueTable, (char *) queueName, (char *) aQ);
01798 
01799   return 0;
01800 }
01801 
01802 
01803 /**
01804   * \brief Iterate over all distinct L4 rules, build BDDs
01805   * 
01806   */
01807 
01808 static int
01809 populateL4BddInfo (Evl_L4Manager_t * L4Mgr)
01810 {
01811   int i;
01812   int L4id;
01813   var_set_t *thisL4RulesL7Set;
01814   bdd_t *L4Bdd;
01815   Rlp_L4Check_t *L4Check;
01816 
01817   for (i = 0; i < array_n (L4Mgr->L4RuleArray); i++)
01818     {
01819 
01820       L4Check = array_fetch (Rlp_L4Check_t *, L4Mgr->L4RuleArray, i);
01821       L4Bdd =
01822     Evl_BuildBddFromL4Formula (L4Check, L4Mgr->mgr->defineTable,
01823                    L4Mgr->bddMgr);
01824       array_insert_last (bdd_t *, L4Mgr->ruleToL4Bdd, L4Bdd);
01825 
01826       if (Hash_Lookup
01827       (L4Mgr->distinctL4RulesTable, (char *) L4Bdd, (char **) &L4id))
01828     {
01829       // we've seen this L4 rule before, so just update the set
01830       // of corresp rules
01831       thisL4RulesL7Set =
01832         array_fetch (var_set_t *, L4Mgr->L4RuleIdToL7ruleSetTable, L4id);
01833       var_set_set_elt (thisL4RulesL7Set, i);
01834     }
01835       else
01836     {
01837       // this is a new L4 rule
01838       L4id = L4Mgr->numDistinctL4Rules;
01839       Hash_Insert (L4Mgr->distinctL4RulesTable, (char *) L4Bdd,
01840              (char *) L4id);
01841       L4Mgr->numDistinctL4Rules++;
01842       thisL4RulesL7Set = var_set_new (L4Mgr->numAllRules);
01843       var_set_set_elt (thisL4RulesL7Set, i);
01844       array_insert_last (var_set_t *, L4Mgr->L4RuleIdToL7ruleSetTable,
01845                  thisL4RulesL7Set);
01846     }
01847     }
01848   return 0;
01849 }
01850 
01851 
01852 /**
01853   * \brief  Free an array of BDDs
01854   * 
01855   */
01856 
01857 static int
01858 bddArrayFree (array_t * bdds)
01859 {
01860   int i;
01861   for (i = 0; i < array_n (bdds); i++)
01862     {
01863       bdd_t *aBdd = array_fetch (bdd_t *, bdds, i);
01864       bdd_free (aBdd);
01865     }
01866   array_free (bdds);
01867   return 0;
01868 }
01869 
01870 
01871 /**
01872   * \brief  Free an L4 Manager
01873   * 
01874   */
01875 
01876 int
01877 Evl_ManagerFree (Evl_Manager_t * result )
01878 {
01879   /// \todo implement this function
01880   return 0;
01881 }
01882 
01883 
01884 /**
01885   * \brief  Given an array of Rlp_Formula_t's, assumed to be L7 rules,
01886   * return an Evl_ContentMgr_t.
01887   * 
01888   */
01889 
01890 Evl_ContentMgr_t *
01891 Evl_BuildContentMgr (array_t * L7CheckArray)
01892 {
01893   Evl_ContentMgr_t *result = Evl_AllocContentMgr ();
01894 
01895   int contentId = 0;        // this var indexes the distinct byte strings
01896   st_table *stringToId = result->stringToId;
01897   st_table *idToString = result->idToString;
01898   array_t *idToRules = result->idToRules;
01899 
01900   st_generator *stGen;
01901 
01902   st_table *contentChecks;  // this will hold content entries in a formula
01903   int ruleIndex;
01904 
01905   for (ruleIndex = 0; ruleIndex < array_n (L7CheckArray); ruleIndex++)
01906     {
01907 
01908       array_t *L7ContentChecks =
01909     array_fetch (array_t *, L7CheckArray, ruleIndex);
01910 
01911       /// \todo: ignore nocase directive for now
01912       contentChecks = Rlp_L7CheckGetContentChecks (L7ContentChecks);
01913 
01914       Rlp_ContentCheck_t *contentCheck;
01915       util_byte_array_t *content;
01916       int maxLength = -1;
01917       util_byte_array_t *maxString = NIL (util_byte_array_t);
01918       st_foreach_item (contentChecks, stGen, (char **) &contentCheck,
01919                (char **) 0)
01920       {
01921     content = contentCheck->content;
01922     // if the check is negated, we don't want to consider the string - 
01923     // it should not appear in the DFA mappping to this rule, since
01924     // that will lead to a wasted check.  we also don't want to 
01925     // consider its length towards deciding whether or not to attach it
01926     // to the short strings
01927     if (!contentCheck->negated)
01928       {
01929         if (!Hash_Lookup
01930         (stringToId, (char *) content, (char **) &contentId))
01931           {
01932 
01933         contentId = st_count (stringToId);
01934         Hash_Insert (stringToId, (char *) content, (char *) contentId);
01935         Hash_Insert (idToString, (char *) contentId, (char *) content);
01936 
01937         array_t *rulesForThisString = array_alloc (int, 0);
01938         array_insert_last (int, rulesForThisString, ruleIndex);
01939         array_insert_last (array_t *, idToRules, rulesForThisString);
01940           }
01941         else
01942           {
01943         updateIdToRules (idToRules, contentId, ruleIndex);
01944           }
01945         if (maxLength < content->length)
01946           {
01947         maxLength = content->length;
01948         maxString = content;
01949           }
01950       }
01951       }
01952       array_insert_last (int, result->maxLengthArray, maxLength);
01953       array_insert_last (util_byte_array_t *, result->maxLengthStringsArray,
01954              maxString);
01955     }
01956   result->numStrings = st_count (stringToId);
01957   result->stringArray = array_alloc (util_byte_array_t *, result->numStrings);
01958 
01959   int id;
01960   util_byte_array_t *string;
01961   st_foreach_item (stringToId, stGen, (char **) &string, (char **) &id)
01962   {
01963     array_insert (util_byte_array_t *, result->stringArray, id, string);
01964   }
01965 
01966   return result;
01967 }
01968 
01969 
01970 /**
01971   * \brief  Update the id to rules array
01972   * 
01973   */
01974 
01975 static int
01976 updateIdToRules (array_t * idToRules, int contentId, int ruleIndex)
01977 {
01978   array_t *rules = array_fetch (array_t *, idToRules, contentId);
01979   // there is a chance that a string may appear more then once
01980   // in a rule, so we have to make sure ruleIndex is not already
01981   // in rules
01982   int i;
01983   for (i = 0; i < array_n (rules); i++)
01984     {
01985       int tmpIndex = array_fetch (int, rules, i);
01986       if (tmpIndex == ruleIndex)
01987     {
01988       // it's already present, so return
01989       return 1;
01990     }
01991     }
01992   array_insert_last (int, rules, ruleIndex);
01993   return 0;
01994 }
01995 
01996 
01997 /**
01998   * \brief  Allocate a content manager structure
01999   * 
02000   */
02001 
02002 Evl_ContentMgr_t *
02003 Evl_AllocContentMgr ()
02004 {
02005   Evl_ContentMgr_t *result =
02006     (Evl_ContentMgr_t *) malloc (sizeof (Evl_ContentMgr_t));
02007   result->numStrings = 0;
02008   result->stringToId =
02009     Hash_InitTable ( (int(*)() ) util_byte_array_cmp, (int(*)() ) util_byte_array_hash);
02010   result->idToString = Hash_InitTable ( (int(*)() ) st_numcmp, (int(*)()) st_numhash);
02011   result->idToRules = array_alloc (array_t *, 0);
02012   result->maxLengthArray = array_alloc (int, 0);
02013   result->maxLengthStringsArray = array_alloc (util_byte_array_t *, 0);
02014 
02015   return result;
02016 }
02017 
02018 
02019 /**
02020   * \brief  Print a content manager
02021   * 
02022   */
02023 
02024 void
02025 Evl_PrintContentMgr (Evl_ContentMgr_t * aCM)
02026 {
02027 /*
02028   printf("Printing a content manager\n");
02029   printf("There are %d distinct strings\n", aCM->numStrings );
02030   printf("Here are the strings to ids\n");
02031   st_generator *stGen;
02032   st_foreach_item( aCM->stringToId, stGen, (char **) & aString, (char **) & id ) {
02033     printf("String: ");
02034     util_byte_array_print( aString );
02035     printf(" has id %d\n", id );
02036   }
02037 */
02038   int i, j;
02039   int maxNumOfRules = 0;
02040   int indexOfMaxRules = -1;
02041   for (i = 0; i < array_n (aCM->idToRules); i++)
02042     {
02043       // printf("String with id %d is associated with rules:\n", i );
02044       array_t *rules = array_fetch (array_t *, aCM->idToRules, i);
02045       for (j = 0; j < array_n (rules); j++)
02046     {
02047       // int aRule = array_fetch( int, rules, j );
02048       // printf(" %d ", aRule );
02049       // char *text = array_fetch( char *, aMgr->rawRules, aRule );
02050       // printf("\nin text this is %s\n", text );
02051     }
02052 
02053       if (array_n (rules) > maxNumOfRules)
02054     {
02055       maxNumOfRules = array_n (rules);
02056       indexOfMaxRules = i;
02057     }
02058       printf ("\n\n");
02059       printf ("There are %d distinct strings\n", aCM->numStrings);
02060     }
02061   printf
02062     ("The most rules associated with any string is %d and the string's id is %d\n",
02063      maxNumOfRules, indexOfMaxRules);
02064   if (indexOfMaxRules != -1)
02065     {
02066       printf ("The rules are \n");
02067       array_t *rules =
02068     array_fetch (array_t *, aCM->idToRules, indexOfMaxRules);
02069       for (j = 0; j < array_n (rules); j++)
02070     {
02071       int aRule = array_fetch (int, rules, j);
02072       printf (" %d ", aRule);
02073     }
02074       printf ("The string is :\n");
02075       util_byte_array_t *aString;
02076       Hash_Lookup (aCM->idToString, (char *) indexOfMaxRules,
02077          (char **) &aString);
02078       util_byte_array_print (aString);
02079     }
02080 }
02081 
02082 
02083 /**
02084   * \brief  Initialize the content manager field of the manager
02085   * 
02086   */
02087 
02088 static void
02089 populateContentManager (Evl_L4Manager_t * L4Mgr)
02090 {
02091   L4Mgr->contentChecks = array_alloc (array_t *, 0);
02092 
02093   int i;
02094   for (i = 0; i < array_n (L4Mgr->L7RuleArray); i++)
02095     {
02096       Rlp_Formula_t *aFormula =
02097     array_fetch (Rlp_Formula_t *, L4Mgr->L7RuleArray, i);
02098       array_t *aContentCheckArray =
02099     Rlp_BuildContentCheckArrayFromL7Formula (aFormula);
02100       array_insert_last (array_t *, L4Mgr->contentChecks, aContentCheckArray);
02101     }
02102   L4Mgr->cm = Evl_BuildContentMgr (L4Mgr->contentChecks);
02103 }
02104 
02105 
02106 /**
02107   * \brief  Build the lookup table for rules with short strings
02108   * 
02109   * Right now we could merge it with the table
02110   * for rules with no content checks, but that has many 
02111   * more rules per equiv class, and at some point a custom
02112   * structure will be needed for it.
02113   * 
02114   */
02115 
02116 static int
02117 buildShortStringLookupTable (Evl_L4Manager_t * mgr)
02118 {
02119   int i;
02120 
02121   var_set_t *shortStringsRulesSet = var_set_new (mgr->numAllRules);
02122   for (i = 0; i < mgr->numAllRules; i++)
02123     {
02124       int maxLength = array_fetch (int, mgr->cm->maxLengthArray, i);
02125       // check against -1 to remove all the no-content checks
02126       // e.g., the icmp checks, sameip, etc
02127       if (maxLength < Evl_MinLengthFsmString && maxLength != -1)
02128     {
02129       var_set_set_elt (shortStringsRulesSet, i);
02130     }
02131     }
02132 
02133   st_table *processedTable = Hash_InitTable ( (int(*)() ) Evl_BddCmp, (int(*)() ) Evl_BddHash);
02134   array_t *shortStringRuleArray = array_alloc (bdd_t *, 0);
02135   array_t *shortStringRuleVarsArray = array_alloc (int, 0);
02136   int L4id;
02137   for (i = 0; i < mgr->numAllRules; i++)
02138     {
02139       bdd_t *L4Bdd = array_fetch (bdd_t *, mgr->ruleToL4Bdd, i);
02140       bool found = Hash_Lookup (mgr->distinctL4RulesTable, (char *) L4Bdd,
02141                   (char **) &L4id);
02142       assert (found != false);
02143       if (Hash_Lookup (processedTable, (char *) L4Bdd, (char **) 0))
02144     {
02145       continue;
02146     }
02147       Hash_Insert (processedTable, (char *) L4Bdd, (char *) 0);
02148       var_set_t *thisL4RulesL7Set =
02149     array_fetch (var_set_t *, mgr->L4RuleIdToL7ruleSetTable, L4id);
02150       var_set_t *tmpSet = var_set_new (mgr->numAllRules);
02151       var_set_and (tmpSet, shortStringsRulesSet, thisL4RulesL7Set);
02152       if (var_set_is_empty (tmpSet))
02153     {
02154       var_set_free (tmpSet);
02155       continue;
02156     }
02157       var_set_free (tmpSet);
02158 
02159       array_insert_last (bdd_t *, shortStringRuleArray, L4Bdd);
02160       bdd_t *ruleVar = bdd_get_variable (mgr->bddMgr, L4id + 96);
02161       array_insert_last (bdd_t *, shortStringRuleVarsArray, ruleVar);
02162     }
02163   if (array_n (shortStringRuleArray) > 0)
02164     {
02165       mgr->shortStringRuleTable =
02166     createLookupTable (mgr, shortStringRuleArray,
02167                shortStringRuleVarsArray);
02168       // intersect out rules from shortStringRuleTable
02169       int j;
02170       for (j = 0; j < mgr->shortStringRuleTable->numClasses; j++)
02171     {
02172       var_set_t *tmpSet = var_set_new (mgr->numAllRules);
02173       var_set_and (tmpSet, mgr->shortStringRuleTable->ruleSets[j],
02174                shortStringsRulesSet);
02175       var_set_free (mgr->shortStringRuleTable->ruleSets[j]);
02176       mgr->shortStringRuleTable->ruleSets[j] = tmpSet;
02177       /* if ( evlDebug ) {
02178          printf("Short string class %d has %d elements\n", 
02179          j, 
02180          var_set_n_elts( mgr->shortStringRuleTable->ruleSets[j] ) );
02181          printRuleSet( mgr, mgr->shortStringRuleTable->ruleSets[j] );
02182          }
02183        */
02184     }
02185       // we'll traverse the short string lookup table via the
02186       // rule array entries, rather than the varsets
02187       Evl_L4LookupTableAddRuleArrays (mgr->shortStringRuleTable);
02188     }
02189   Hash_FreeTable (processedTable);
02190   return 0;
02191 }
02192 
02193 
02194 /**
02195   * \brief  Code for printing a ruleset
02196   * 
02197   */
02198 
02199 static int
02200 printRuleSet (Evl_L4Manager_t * mgr, var_set_t * ruleSet)
02201 {
02202   int i;
02203   assert (mgr->numAllRules == ruleSet->n_elts);
02204   for (i = 0; i < mgr->numAllRules; i++)
02205     {
02206       if (!var_set_get_elt (ruleSet, i))
02207     {
02208       continue;
02209     }
02210       int globalIndex = array_fetch (int, mgr->tcpIdToGlobalId, i);
02211       char *rawRule = array_fetch (char *, mgr->mgr->rawRules, globalIndex);
02212       printf ("Rule %d is %s\n", i, rawRule);
02213     }
02214   return 0;
02215 }
02216 
02217 
02218 /**
02219   * \brief  Function for building an FSM over the long strings
02220   * in a manager.
02221   */
02222 
02223 static void
02224 populateLongStringsFsm (Evl_L4Manager_t * mgr)
02225 {
02226   int i;
02227   var_set_t *aSet;
02228   array_t *byteArrayArray = array_alloc (util_byte_array_t *, 0);
02229   st_table *longByteArrayHash =
02230     Hash_InitTable ( (int(*)() ) util_byte_array_cmp, (int(*)() ) util_byte_array_hash);
02231   for (i = 0; i < mgr->numAllRules; i++)
02232     {
02233       int maxLength = array_fetch (int, mgr->cm->maxLengthArray, i);
02234       util_byte_array_t *maxString =
02235     array_fetch (util_byte_array_t *, mgr->cm->maxLengthStringsArray, i);
02236       if (maxLength >= Evl_MinLengthFsmString)
02237     {
02238       if (Hash_Lookup
02239           (longByteArrayHash, (char *) maxString, (char **) &aSet))
02240         {
02241           var_set_set_elt (aSet, i);
02242         }
02243       else
02244         {
02245           var_set_t *newSet = var_set_new (mgr->numAllRules);
02246           var_set_set_elt (newSet, i);
02247           Hash_Insert (longByteArrayHash, (char *) maxString,
02248              (char *) newSet);
02249           array_insert_last (util_byte_array_t *, byteArrayArray,
02250                  maxString);
02251         }
02252     }
02253     }
02254   Evl_Fsm_t *fsm = Evl_BuildPrefixAutomaton (byteArrayArray);
02255   mgr->fsm = fsm;
02256   populateMgrFsmAcceptingStates (mgr, longByteArrayHash);
02257 }
02258 
02259 
02260 /**
02261   * \brief  Create mapping from fsm accepting states to rules
02262   */
02263 
02264 static void
02265 populateMgrFsmAcceptingStates (Evl_L4Manager_t * L4Mgr,
02266                    st_table * longByteArrayHash)
02267 {
02268   Evl_Fsm_t *fsm = L4Mgr->fsm;
02269   var_set_t *aRuleSet;
02270   L4Mgr->fsmAcceptingStates = (var_set_t *) var_set_new (fsm->N);
02271   L4Mgr->fsmStateToRuleSet =
02272     (var_set_t **) malloc (sizeof (var_set_t *) * fsm->N);
02273   int i;
02274   for (i = 0; i < fsm->N; i++)
02275     {
02276       array_t *acceptedStrings = array_fetch (array_t *, fsm->finalStates, i);
02277       if (acceptedStrings == NIL (array_t))
02278     {
02279       L4Mgr->fsmStateToRuleSet[i] = NIL (var_set_t);
02280     }
02281       else
02282     {
02283       var_set_set_elt (L4Mgr->fsmAcceptingStates, i);
02284       L4Mgr->fsmStateToRuleSet[i] = var_set_new (L4Mgr->numAllRules);
02285       int j;
02286       for (j = 0; j < array_n (acceptedStrings); j++)
02287         {
02288           int aStringId = array_fetch (int, acceptedStrings, j);
02289           util_byte_array_t *aString = fsm->stateIdToPrefix[aStringId];
02290           bool found = Hash_Lookup (longByteArrayHash, (char *) aString,
02291                       (char **) &aRuleSet);
02292           assert (found != false);
02293           var_set_or (L4Mgr->fsmStateToRuleSet[i],
02294               L4Mgr->fsmStateToRuleSet[i], aRuleSet);
02295         }
02296     }
02297     }
02298 
02299 /*
02300   if ( evlDebug) {
02301     for ( i = 0 ; i < fsm->N ; i++ ) {
02302       if ( ( L4Mgr->fsmStateToRuleSet[i] != NIL( var_set_t ) ) &&
02303              var_set_n_elts( L4Mgr->fsmStateToRuleSet[i] ) > 0 ) {
02304         printf("State %d corresponds to %d rules\n", i, var_set_n_elts( L4Mgr->fsmStateToRuleSet[i] ) );
02305         if ( var_set_n_elts( L4Mgr->fsmStateToRuleSet[i] ) > 5 ) {
02306           printf("Lots of rules here - they are \n");
02307           int j;
02308           for ( j = 0 ; j < L4Mgr->numAllRules; j++ ) {   
02309             if ( var_set_get_elt( L4Mgr->fsmStateToRuleSet[i], j ) ) {
02310           int globalIndex = array_fetch( int, L4Mgr->tcpIdToGlobalId, j );
02311               printf("\t%s\n", array_fetch( char *, L4Mgr->mgr->rawRules, globalIndex ) );
02312             }
02313           }
02314         }
02315       }
02316     }
02317   }
02318 */
02319 }
02320 
02321 
02322 /**
02323   * \brief  Populate raw rules and macros array
02324   */
02325 
02326 static int
02327 populateRawRulesAndMacros (Evl_Manager_t * mgr, char *ruleFile)
02328 {
02329   mgr->rawRulesAndMacrosArray = util_process_file (ruleFile);
02330   return 0;
02331 }
02332 
02333 
02334 /**
02335   * \brief  Iterate over rules to find the ones that have no
02336   * content checks.
02337   * 
02338   */
02339 
02340 static int
02341 buildNoContentCheckTable (Evl_L4Manager_t * mgr)
02342 {
02343   int i;
02344   var_set_t *noContentChecksSet = var_set_new (mgr->numAllRules);
02345   array_t *bddArray = array_alloc (bdd_t *, 0);
02346   array_t *bddVarArray = array_alloc (bdd_t *, 0);
02347   st_table *processedTable = Hash_InitTable ( (int(*)() ) Evl_BddCmp, (int(*)() ) Evl_BddHash);
02348   for (i = 0; i < mgr->numAllRules; i++)
02349     {
02350       int maxLength = array_fetch (int, mgr->cm->maxLengthArray, i);
02351       if (maxLength != -1)
02352     {
02353       continue;
02354     }
02355       // this rule has no content checks
02356       var_set_set_elt (noContentChecksSet, i);
02357       // Rlp_L4Check_t *l4Entry = array_fetch( Rlp_L4Check_t *, mgr->L4RuleArray, i );
02358       bdd_t *thisRuleBdd = array_fetch (bdd_t *, mgr->ruleToL4Bdd, i);
02359       if (Hash_Lookup (processedTable, (char *) thisRuleBdd, (char **) 0))
02360     {
02361       continue;
02362     }
02363       Hash_Insert (processedTable, (char *) thisRuleBdd, (char *) 0);
02364       array_insert_last (bdd_t *, bddArray, thisRuleBdd);
02365       int bddId;
02366       bool found = Hash_Lookup (mgr->distinctL4RulesTable, (char *) thisRuleBdd,
02367                   (char **) &bddId);
02368       assert (found != false);
02369       bdd_t *ruleVarBdd = bdd_get_variable (mgr->bddMgr, bddId + 96);
02370       array_insert_last (bdd_t *, bddVarArray, ruleVarBdd);
02371     }
02372 
02373   Evl_L4LookupTable_t *noContentCheckTable =
02374     createLookupTable (mgr, bddArray, bddVarArray);
02375 
02376   for (i = 0; i < noContentCheckTable->numClasses; i++)
02377     {
02378       /// \todo: this code looks redundant, since noContentCheckTable is a subset of coContentCheckSet
02379       var_set_and (noContentCheckTable->ruleSets[i],
02380            noContentCheckTable->ruleSets[i], noContentChecksSet);
02381     }
02382 
02383 
02384   // need to do after the ANDING is done!
02385   Evl_L4LookupTableAddRuleArrays (noContentCheckTable);
02386   mgr->noContentCheckTable = noContentCheckTable;
02387   return 0;
02388 }
02389 
02390 
02391 /**
02392   * \brief  Add rule arrays in addition to the sets
02393   * 
02394   */
02395 
02396 int
02397 Evl_L4LookupTableAddRuleArrays (Evl_L4LookupTable_t * table)
02398 {
02399   if (table == NIL (Evl_L4LookupTable_t))
02400     {
02401       return 0;
02402     }
02403   table->ruleArrays =
02404     (util_int_array_t **) malloc (table->numClasses *
02405                   sizeof (util_int_array_t *));
02406 
02407   table->ruleArrayMin = (int *) malloc (table->numClasses * sizeof (int));
02408 
02409   table->ruleArrayMax = (int *) malloc (table->numClasses * sizeof (int));
02410 
02411   int i;
02412   for (i = 0; i < table->numClasses; i++)
02413     {
02414       table->ruleArrayMin[i] = -1;
02415       table->ruleArrayMax[i] = -1;
02416       table->ruleArrays[i] = var_set_to_int_array (table->ruleSets[i]);
02417       int length = table->ruleArrays[i]->length;
02418       if (length > 0)
02419     {
02420       table->ruleArrayMin[i] = (table->ruleArrays[i]->entries)[0];
02421       table->ruleArrayMax[i] = (table->ruleArrays[i]->entries)[length-1];
02422     }
02423     }
02424   return 0;
02425 }
02426 
02427 
02428 /**
02429   * \brief  Build the content manager with all strings projected down to lower case.
02430   * 
02431   * We use this in the following way:  we have a number of checks that are
02432   * case-insensitive, and a number that are case-sensitive.  We could
02433   * build two DFA, and then run the checks twice.  On the other hand
02434   *     we could make ALL of the DFA checks case-insensitive, and
02435   * then in the final detailed check, take case into account.  We choose the
02436   * latter since it means only a single pass over the packet. There is a 
02437   * possibility of false positives from this scheme, e.g., a case specific search
02438   * search for "abc" will be matched by "ABC"; I don't have a detailed analysis/study
02439   * of this pheonomenon, but it seems to be unlikely.
02440   *
02441   * \sa evalContentCheck
02442   */
02443 
02444 Evl_ContentMgr_t *
02445 Evl_BuildContentMgrForLowerCaseStrings (Evl_ContentMgr_t * aCM)
02446 {
02447   Evl_ContentMgr_t *result = Evl_AllocContentMgr ();
02448 
02449   st_generator *stGen;
02450   util_byte_array_t *aString, *lowerCaseString;
02451   int i, anId, tmpId, lowerCaseStringId;
02452 
02453   array_t *newArray, *existingArray;
02454   st_foreach_item (aCM->stringToId, stGen, (char **) &aString,
02455            (char **) &anId)
02456   {
02457     util_byte_array_t *lowerCaseString =
02458       util_byte_array_to_lower_case (aString);
02459     if (!
02460     (Hash_Lookup
02461      (result->stringToId, (char *) lowerCaseString,
02462       (char **) &lowerCaseStringId)))
02463       {
02464     lowerCaseStringId = st_count (result->stringToId);
02465     result->numStrings++;
02466     Hash_Insert (result->stringToId, (char *) lowerCaseString,
02467            (char *) lowerCaseStringId);
02468     Hash_Insert (result->idToString, (char *) lowerCaseStringId,
02469            (char *) lowerCaseString);
02470     newArray = array_alloc (int, 0);
02471     array_insert_last (array_t *, result->idToRules, newArray);
02472       }
02473     else
02474       {
02475     // printf("\nDUP: ");
02476     // util_byte_array_print( lowerCaseString );
02477     // printf("\t:\t");
02478     // util_byte_array_print( aString );
02479     // printf("\n");
02480     util_byte_array_free (lowerCaseString);
02481       }
02482     newArray = array_fetch (array_t *, result->idToRules, lowerCaseStringId);
02483     existingArray = array_fetch (array_t *, aCM->idToRules, anId);
02484     for (i = 0; i < array_n (existingArray); i++)
02485       {
02486     tmpId = array_fetch (int, existingArray, i);
02487     array_insert_last (int, newArray, tmpId);
02488       }
02489   }
02490 
02491   result->stringArray = array_alloc (util_byte_array_t *,
02492                      st_count (result->stringToId));
02493   st_foreach_item (result->stringToId,
02494            stGen,
02495            (char **) &lowerCaseString, (char **) &lowerCaseStringId)
02496   {
02497     array_insert (util_byte_array_t *, result->stringArray,
02498           lowerCaseStringId, lowerCaseString);
02499   }
02500   for (i = 0; i < array_n (aCM->maxLengthArray); i++)
02501     {
02502       int length = array_fetch (int, aCM->maxLengthArray, i);
02503       util_byte_array_t *longString = array_fetch (util_byte_array_t *,
02504                            aCM->maxLengthStringsArray,
02505                            i);
02506       array_insert_last (int, result->maxLengthArray, length);
02507       if (longString == NIL (util_byte_array_t))
02508     {
02509       array_insert_last (util_byte_array_t *,
02510                  result->maxLengthStringsArray,
02511                  NIL (util_byte_array_t));
02512       continue;
02513     }
02514       int tmpStringId;
02515       lowerCaseString = util_byte_array_to_lower_case (longString);
02516       Hash_Lookup (result->stringToId, (char *) lowerCaseString,
02517          (char **) &tmpStringId);
02518       util_byte_array_free (lowerCaseString);
02519       Hash_Lookup (result->idToString, (char *) tmpStringId,
02520          (char **) &lowerCaseString);
02521       array_insert_last (util_byte_array_t *, result->maxLengthStringsArray,
02522              lowerCaseString);
02523     }
02524 
02525   // st_foreach_item( aCM->stringToId, stGen, (char **) & aString, (char **) & anId ) {
02526   //   printf("\nUPPER:");
02527   //   util_byte_array_print( aString );
02528   // }
02529   // st_foreach_item( result->stringToId, stGen, (char **) & aString, (char **) & anId ) {
02530   //   printf("\nLOWER:");
02531   //   util_byte_array_print( aString );
02532   // }
02533 
02534   return result;
02535 }
02536 
02537 
02538 /**
02539   * \brief Check to see what type of rule this is.
02540   */
02541 
02542 static bool
02543 checkRuleMode (char *rawRule, char *mode)
02544 {
02545   while (isspace (*rawRule))
02546     {
02547       rawRule++;
02548     }
02549 
02550   // first check to see if it's a preprocessing rule 
02551   if (util_strequalN ("preprocess", mode, strlen ("preprocess")) &&
02552       util_strequalN ("preprocess", rawRule, strlen ("preprocess")))
02553     {
02554       return 1;
02555     }
02556 
02557   // we're not checking for a preprocessing rule
02558   if (util_strequalN ("preprocess", rawRule, strlen ("preprocess")))
02559     {
02560       rawRule += strlen ("preprocess");
02561       while (isspace (*rawRule))
02562     {
02563       rawRule++;
02564     }
02565     }
02566 
02567   bool result = util_strequalN (rawRule, mode, strlen (mode));
02568   return result;
02569 }
02570 
02571 
02572 /**
02573   * \brief Determine the number of preprocessing rules.
02574   */
02575 
02576 static void
02577 computeNumberOfPreprocessRules (Evl_Manager_t * mgr)
02578 {
02579   int i;
02580   for (i = 0; i < array_n (mgr->rawRules); i++)
02581     {
02582       char *rawRule = array_fetch (char *, mgr->rawRules, i);
02583       while (*rawRule == ' ')
02584     {
02585       rawRule++;
02586     }
02587       if (!util_strequalN (rawRule, "preprocess", strlen ("preprocess")))
02588     {
02589       continue;
02590     }
02591       else
02592     {
02593       mgr->numPreprocessRules++;
02594     }
02595     }
02596 }