code review 1129043: re2: memory diet part 2

re2/dfa.cc

 // Copyright 2008 The RE2 Authors.  All Rights Reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 // A DFA (deterministic finite automaton)-based regular expression search.
 //
 // The DFA search has two main parts: the construction of the automaton,
 // which is represented by a graph of State structures, and the execution
 // of the automaton over a given input string.
 //
@@ skipping 77 matching lines @@
   // difficult to mark them as such.
   class Workq;
   class RWLocker;
   class StateSaver;
 
   // A single DFA state.  The DFA is represented as a graph of these
   // States, linked by the next_ pointers.  If in state s and reading
   // byte c, the next state should be s->next_[c].
   struct State {
     inline bool IsMatch() const { return flag_ & kFlagMatch; }
-    uint32* inst_;       // Instruction pointers in the state.
+    int* inst_;         // Instruction pointers in the state.
     int ninst_;         // # of inst_ pointers.
     uint flag_;         // Empty string bitfield flags in effect on the way
                         // into this state, along with kFlagMatch if this
                         // is a matching state.
     State** next_;      // Outgoing arrows from State,
                         // one per input byte class
   };
 
   enum {
     kByteEndText = 256,         // imaginary byte at end of text
@@ skipping 64 matching lines @@
   // cache_mutex_.r <= L < mutex_
   // After: cache_mutex_.w <= L < mutex_
   void ResetCache(RWLocker* cache_lock);
 
   // Looks up and returns the State corresponding to a Workq.
   // L >= mutex_
   State* WorkqToCachedState(Workq* q, uint flag);
 
   // Looks up and returns a State matching the inst, ninst, and flag.
   // L >= mutex_
-  State* CachedState(uint32* inst, int ninst, uint flag);
+  State* CachedState(int* inst, int ninst, uint flag);
 
   // Clear the cache entirely.
   // Must hold cache_mutex_.w or be in destructor.
   void ClearCache();
 
   // Converts a State into a Workq: the opposite of WorkqToCachedState.
   // L >= mutex_
   static void StateToWorkq(State* s, Workq* q);
 
   // Runs a State on a given byte, returning the next state.
   State* RunStateOnByteUnlocked(State*, int);  // cache_mutex_.r <= L < mutex_
   State* RunStateOnByte(State*, int);          // L >= mutex_
 
   // Runs a Workq on a given byte followed by a set of empty-string flags,
   // producing a new Workq in nq.  If a match instruction is encountered,
   // sets *ismatch to true.
   // L >= mutex_
   void RunWorkqOnByte(Workq* q, Workq* nq,
                              int c, uint flag, bool* ismatch,
                              Prog::MatchKind kind,
-                             uint32 new_byte_loop);
+                             int new_byte_loop);
 
   // Runs a Workq on a set of empty-string flags, producing a new Workq in nq.
   // L >= mutex_
   void RunWorkqOnEmptyString(Workq* q, Workq* nq, uint flag);
 
   // Adds the instruction id to the Workq, following empty arrows
   // according to flag.
   // L >= mutex_
   void AddToQueue(Workq* q, int id, uint flag);
 
@@ skipping 95 matching lines @@
   Prog* prog_;              // The regular expression program to run.
   Prog::MatchKind kind_;    // The kind of DFA.
   int start_unanchored_;  // start of unanchored program
   bool init_failed_;        // initialization failed (out of memory)
 
   Mutex mutex_;  // mutex_ >= cache_mutex_.r
 
   // Scratch areas, protected by mutex_.
   Workq* q0_;             // Two pre-allocated work queues.
   Workq* q1_;
-  uint32* astack_;         // Pre-allocated stack for AddToQueue
+  int* astack_;         // Pre-allocated stack for AddToQueue
   int nastack_;
 
   // State* cache.  Many threads use and add to the cache simultaneously,
   // holding cache_mutex_ for reading and mutex_ (above) when adding.
   // If the cache fills and needs to be discarded, the discarding is done
   // while holding cache_mutex_ for writing, to avoid interrupting other
   // readers.  Any State* pointers are only valid while cache_mutex_
   // is held.
   Mutex cache_mutex_;
   int64 mem_budget_;       // Total memory budget for all States.
   int64 state_budget_;     // Amount of memory remaining for new States.
   StateSet state_cache_;   // All States computed so far.
   StartInfo start_[kMaxStart];
   bool cache_warned_;      // have printed to LOG(INFO) about the cache
 };
 
 // Shorthand for casting to uint8*.
 static inline const uint8* BytePtr(const void* v) {
   return reinterpret_cast<const uint8*>(v);
 }
 
 // Work queues
 
 // Marks separate thread groups of different priority
 // in the work queue when in leftmost-longest matching mode.
-#define Mark static_cast<uint32>(-1)
+#define Mark (-1)
 
 // Internally, the DFA uses a sparse array of
 // program instruction pointers as a work queue.
 // In leftmost longest mode, marks separate sections
 // of workq that started executing at different
 // locations in the string (earlier locations first).
 class DFA::Workq : public SparseSet {
  public:
   // Constructor: n is number of normal slots, maxmark number of mark slots.
   Workq(int n, int maxmark) :
@@ skipping 58 matching lines @@
   start_unanchored_ = NULL;
   if (kind_ == Prog::kLongestMatch) {
     nmark = prog->size();
     start_unanchored_ = prog->start_unanchored();
   }
   nastack_ = 2 * prog->size() + nmark;
 
   // Account for space needed for DFA, q0, q1, astack.
   mem_budget_ -= sizeof(DFA);
   mem_budget_ -= (prog_->size() + nmark) *
-                 (sizeof(int)+sizeof(int)+sizeof(uint32)) * 2;  // q0, q1
-  mem_budget_ -= nastack_ * sizeof(uint32);  // astack
+                 (sizeof(int)+sizeof(int)) * 2;  // q0, q1
+  mem_budget_ -= nastack_ * sizeof(int);  // astack
   if (mem_budget_ < 0) {
     LOG(INFO) << StringPrintf("DFA out of memory: prog size %lld mem %lld",
                               prog_->size(), max_mem);
     init_failed_ = true;
     return;
   }
 
   state_budget_ = mem_budget_;
 
   // Make sure there is a reasonable amount of working room left.
   // At minimum, the search requires room for two states in order
   // to limp along, restarting frequently.  We'll get better performance
   // if there is room for a larger number of states, say 20.
-  int one_state = sizeof(State) + (prog_->size()+nmark)*sizeof(uint32) +
+  int one_state = sizeof(State) + (prog_->size()+nmark)*sizeof(int) +
                   (prog_->bytemap_range()+1)*sizeof(State*);
   if (state_budget_ < 20*one_state) {
     LOG(INFO) << StringPrintf("DFA out of memory: prog size %lld mem %lld",
                               prog_->size(), max_mem);
     init_failed_ = true;
     return;
   }
 
   q0_ = new Workq(prog->size(), nmark);
   q1_ = new Workq(prog->size(), nmark);
-  astack_ = new uint32[nastack_];
+  astack_ = new int[nastack_];
 }
 
 DFA::~DFA() {
   delete q0_;
   delete q1_;
   delete[] astack_;
   ClearCache();
 }
 
 // In the DFA state graph, s->next[c] == NULL means that the
@@ skipping 54 matching lines @@
 //
 // DFA state graph construction.
 //
 // The DFA state graph is a heavily-linked collection of State* structures.
 // The state_cache_ is a set of all the State structures ever allocated,
 // so that if the same state is reached by two different paths,
 // the same State structure can be used.  This reduces allocation
 // requirements and also avoids duplication of effort across the two
 // identical states.
 //
-// A State is defined by an ordered list of uint32 instruction ids and a flag word.
+// A State is defined by an ordered list of instruction ids and a flag word.
 //
 // The choice of an ordered list of instructions differs from a typical
 // textbook DFA implementation, which would use an unordered set.
 // Textbook descriptions, however, only care about whether
 // the DFA matches, not where it matches in the text.  To decide where the
 // DFA matches, we need to mimic the behavior of the dominant backtracking
 // implementations like PCRE, which try one possible regular expression
 // execution, then another, then another, stopping when one of them succeeds.
 // The DFA execution tries these many executions in parallel, representing
 // each by an instruction id.  These pointers are ordered in the State.inst_
@@ skipping 34 matching lines @@
 // If one is found, returns it.  If one is not found, allocates one,
 // inserts it in the cache, and returns it.
 DFA::State* DFA::WorkqToCachedState(Workq* q, uint flag) {
   if (DEBUG_MODE)
     mutex_.AssertHeld();
 
   // Construct array of instruction ids for the new state.
   // Only ByteRange, EmptyWidth, and Match instructions are useful to keep:
   // those are the only operators with any effect in
   // RunWorkqOnEmptyString or RunWorkqOnByte.
-  uint32* inst = new uint32[q->size()];
+  int* inst = new int[q->size()];
   int n = 0;
   uint needflags = 0;     // flags needed by kInstEmptyWidth instructions
   bool sawmatch = false;  // whether queue contains guaranteed kInstMatch
   if (DebugDFA)
     fprintf(stderr, "WorkqToCachedState %s [%#x]", DumpWorkq(q).c_str(), flag);
   for (Workq::iterator it = q->begin(); it != q->end(); ++it) {
     int id = *it;
     if (sawmatch && (kind_ == Prog::kFirstMatch || q->is_mark(id)))
       break;
     if (q->is_mark(id)) {
@@ skipping 65 matching lines @@
   // if the state is *not* a matching state.
   if (n == 0 && flag == 0) {
     delete[] inst;
     return DeadState;
   }
 
   // If we're in longest match mode, the state is a sequence of
   // unordered state sets separated by Marks.  Sort each set
   // to canonicalize, to reduce the number of distinct sets stored.
   if (kind_ == Prog::kLongestMatch) {
-    uint32* ip = inst;
-    uint32* ep = ip + n;
+    int* ip = inst;
+    int* ep = ip + n;
     while (ip < ep) {
-      uint32* markp = ip;
+      int* markp = ip;
       while (markp < ep && *markp != Mark)
         markp++;
       sort(ip, markp);
       if (markp < ep)
         markp++;
       ip = markp;
     }
   }
 
   // Save the needed empty-width flags in the top bits for use later.
   flag |= needflags << kFlagNeedShift;
 
   State* state = CachedState(inst, n, flag);
   delete[] inst;
   return state;
 }
 
 // Looks in the State cache for a State matching inst, ninst, flag.
 // If one is found, returns it.  If one is not found, allocates one,
 // inserts it in the cache, and returns it.
-DFA::State* DFA::CachedState(uint32* inst, int ninst, uint flag) {
+DFA::State* DFA::CachedState(int* inst, int ninst, uint flag) {
   if (DEBUG_MODE)
     mutex_.AssertHeld();
 
   // Look in the cache for a pre-existing state.
   State state = { inst, ninst, flag, NULL };
   StateSet::iterator it = state_cache_.find(&state);
   if (it != state_cache_.end()) {
     if (DebugDFA)
       fprintf(stderr, " -cached-> %s\n", DumpState(*it).c_str());
     return *it;
   }
 
   // Must have enough memory for new state.
   // In addition to what we're going to allocate,
   // the state cache hash table seems to incur about 32 bytes per
   // State*, empirically.
   const int kStateCacheOverhead = 32;
   int nnext = prog_->bytemap_range() + 1;  // + 1 for kByteEndText slot
-  int mem = sizeof(State) + nnext*sizeof(State*) + ninst*sizeof(uint32);
+  int mem = sizeof(State) + nnext*sizeof(State*) + ninst*sizeof(int);
   if (mem_budget_ < mem + kStateCacheOverhead) {
     mem_budget_ = -1;
     return NULL;
   }
   mem_budget_ -= mem + kStateCacheOverhead;
 
   // Allocate new state, along with room for next and inst.
   char* space = new char[mem];
   State* s = reinterpret_cast<State*>(space);
   s->next_ = reinterpret_cast<State**>(s + 1);
-  s->inst_ = reinterpret_cast<uint32*>(s->next_ + nnext);
+  s->inst_ = reinterpret_cast<int*>(s->next_ + nnext);
   memset(s->next_, 0, nnext*sizeof s->next_[0]);
   memmove(s->inst_, inst, ninst*sizeof s->inst_[0]);
   s->ninst_ = ninst;
   s->flag_ = flag;
   if (DebugDFA)
     fprintf(stderr, " -> %s\n", DumpState(s).c_str());
 
   // Put state in cache and return it.
   state_cache_.insert(s);
   return s;
@@ skipping 27 matching lines @@
 // Adds ip to the work queue, following empty arrows according to flag
 // and expanding kInstAlt instructions (two-target gotos).
 void DFA::AddToQueue(Workq* q, int id, uint flag) {
 
   // Use astack_ to hold our stack of states yet to process.
   // It is sized to have room for nastack_ == 2*prog->size() + nmark
   // instructions, which is enough: each instruction can be
   // processed by the switch below only once, and the processing
   // pushes at most two instructions plus maybe a mark.
   // (If we're using marks, nmark == prog->size(); otherwise nmark == 0.)
-  uint32* stk = astack_;
+  int* stk = astack_;
   int nstk = 0;
 
   stk[nstk++] = id;
   while (nstk > 0) {
     DCHECK_LE(nstk, nastack_);
     id = stk[--nstk];
 
     if (id == Mark) {
       q->mark();
       continue;
@@ skipping 76 matching lines @@
   }
 }
 
 // Runs the work queue, processing the single byte c followed by any empty
 // strings indicated by flag.  For example, c == 'a' and flag == kEmptyEndLine,
 // means to match c$.  Sets the bool *ismatch to true if the end of the
 // regular expression program has been reached (the regexp has matched).
 void DFA::RunWorkqOnByte(Workq* oldq, Workq* newq,
                          int c, uint flag, bool* ismatch,
                          Prog::MatchKind kind,
-                         uint32 new_byte_loop) {
+                         int new_byte_loop) {
   if (DEBUG_MODE)
     mutex_.AssertHeld();
 
   newq->clear();
   for (Workq::iterator i = oldq->begin(); i != oldq->end(); ++i) {
     if (oldq->is_mark(*i)) {
       if (*ismatch)
         return;
       newq->mark();
       continue;
@@ skipping 262 matching lines @@
   // Recreates and returns a state equivalent to the
   // original state passed to the constructor.
   // Returns NULL if the cache has filled, but
   // since the DFA guarantees to have room in the cache
   // for a couple states, should never return NULL
   // if used right after ResetCache.
   State* Restore();
 
  private:
   DFA* dfa_;         // the DFA to use
-  uint32* inst_;      // saved info from State
+  int* inst_;        // saved info from State
   int ninst_;
   uint flag_;
   bool is_special_;  // whether original state was special
   State* special_;   // if is_special_, the original state
 
   DISALLOW_EVIL_CONSTRUCTORS(StateSaver);
 };
 
 DFA::StateSaver::StateSaver(DFA* dfa, State* state) {
   dfa_ = dfa;
   if (state <= SpecialStateMax) {
     inst_ = NULL;
     ninst_ = 0;
     flag_ = 0;
     is_special_ = true;
     special_ = state;
     return;
   }
   is_special_ = false;
   special_ = NULL;
   flag_ = state->flag_;
   ninst_ = state->ninst_;
-  inst_ = new uint32[ninst_];
+  inst_ = new int[ninst_];
   memmove(inst_, state->inst_, ninst_*sizeof inst_[0]);
 }
 
 DFA::StateSaver::~StateSaver() {
   if (!is_special_)
     delete[] inst_;
 }
 
 DFA::State* DFA::StateSaver::Restore() {
   if (is_special_)
@@ skipping 831 matching lines @@
     if (dfa_longest_ == NULL) {
       dfa_longest_ = new DFA(this, Prog::kLongestMatch, dfa_mem_/2);
       delete_dfa_ = DeleteDFA;
     }
     dfa = dfa_longest_;
   }
   return dfa->PossibleMatchRange(min, max, maxlen);
 }
 
 }  // namespace re2