LCOV - code coverage report
Current view: top level - src - DFA.h (source / functions) Hit Total Coverage
Test: app.info Lines: 16 24 66.7 %
Date: 2010-12-13 Functions: 17 26 65.4 %
Branches: 3 6 50.0 %

           Branch data     Line data    Source code
       1                 :            : // $Id: DFA.h 6219 2008-10-01 05:39:07Z vern $
       2                 :            : //
       3                 :            : // See the file "COPYING" in the main distribution directory for copyright.
       4                 :            : 
       5                 :            : 
       6                 :            : #ifndef dfa_h
       7                 :            : #define dfa_h
       8                 :            : 
       9                 :            : #include <assert.h>
      10                 :            : 
      11                 :            : // It's possible to use a fixed size cache of computed states for each DFA.
      12                 :            : // If the number of DFA states reaches the given limit, old states are expired
      13                 :            : // on a least-recently-used basis. This may impact the performance significantly
      14                 :            : // if expired states have to be recalculated regularly, but it limits the
      15                 :            : // amount of memory taken by a DFA.
      16                 :            : //
      17                 :            : // Enable by configuring with --with-expire-dfa-states.
      18                 :            : 
      19                 :            : class DFA_State;
      20                 :            : 
      21                 :            : // The cache marks expired states as invalid.
      22                 :            : #define DFA_INVALID_STATE_PTR ((DFA_State*) -1)
      23                 :            : 
      24                 :            : // Transitions to the uncomputed state indicate that we haven't yet
      25                 :            : // computed the state to go to.
      26                 :            : #define DFA_UNCOMPUTED_STATE -2
      27                 :            : #define DFA_UNCOMPUTED_STATE_PTR ((DFA_State_Handle*) DFA_UNCOMPUTED_STATE)
      28                 :            : 
      29                 :            : #ifdef EXPIRE_DFA_STATES
      30                 :            : 
      31                 :            : class DFA_State_Handle {
      32                 :            : public:
      33                 :            :         // The reference counting keeps track of this *handle* (not the state).
      34                 :            :         void Ref()      { assert(state); ++refcount; }
      35                 :            :         void Unref()
      36                 :            :                 {
      37                 :            :                 if ( --refcount == 0 )
      38                 :            :                         delete this;
      39                 :            :                 }
      40                 :            : 
      41                 :            :         inline void Invalidate();
      42                 :            :         bool IsValid() const            { return state != DFA_INVALID_STATE_PTR; }
      43                 :            : 
      44                 :            :         DFA_State* State() const        { return state; }
      45                 :            :         DFA_State* operator->() const        { return state; }
      46                 :            : 
      47                 :            : protected:
      48                 :            :         friend class DFA_State_Cache;
      49                 :            : 
      50                 :            :         DFA_State_Handle(DFA_State* arg_state)
      51                 :            :                 { state = arg_state; refcount = 1; }
      52                 :            : 
      53                 :            :         inline ~DFA_State_Handle();
      54                 :            : 
      55                 :            :         DFA_State* state;
      56                 :            :         int refcount;
      57                 :            : };
      58                 :            : 
      59                 :            : #else
      60                 :            : typedef DFA_State DFA_State_Handle;
      61                 :            : #endif
      62                 :            : 
      63                 :            : #include "NFA.h"
      64                 :            : 
      65                 :            : extern int dfa_state_cache_size;
      66                 :            : 
      67                 :            : class DFA_Machine;
      68                 :            : class DFA_State;
      69                 :            : struct CacheEntry;
      70                 :            : 
      71                 :            : class DFA_State : public BroObj {
      72                 :            : public:
      73                 :            :         DFA_State(int state_num, const EquivClass* ec,
      74                 :            :                         NFA_state_list* nfa_states, AcceptingSet* accept);
      75                 :            :         ~DFA_State();
      76                 :            : 
      77                 :          0 :         int StateNum() const            { return state_num; }
      78                 :          0 :         int NFAStateNum() const         { return nfa_states->length(); }
      79                 :            :         void AddXtion(int sym, DFA_State_Handle* next_state);
      80                 :            : 
      81                 :            :         inline DFA_State_Handle* Xtion(int sym, DFA_Machine* machine);
      82                 :            : 
      83                 :     247943 :         const AcceptingSet* Accept() const      { return accept; }
      84                 :            :         void SymPartition(const EquivClass* ec);
      85                 :            : 
      86                 :            :         // ec_sym is an equivalence class, not a character.
      87                 :            :         NFA_state_list* SymFollowSet(int ec_sym, const EquivClass* ec);
      88                 :            : 
      89                 :          0 :         void SetMark(DFA_State* m)      { mark = m; }
      90                 :            :         DFA_State* Mark() const         { return mark; }
      91                 :            :         void ClearMarks();
      92                 :            : 
      93                 :            :         // Returns the equivalence classes of ec's corresponding to this state.
      94                 :            :         const EquivClass* MetaECs() const       { return meta_ec; }
      95                 :            : 
      96                 :            :         void Describe(ODesc* d) const;
      97                 :            :         void Dump(FILE* f, DFA_Machine* m);
      98                 :            :         void Stats(unsigned int* computed, unsigned int* uncomputed);
      99                 :            :         unsigned int Size();
     100                 :            : 
     101                 :            :         // Locking a state will keep it from expiring from a cache.
     102                 :          0 :         void Lock()     { ++lock; }
     103                 :          0 :         void Unlock()   { --lock; }
     104                 :            : 
     105                 :            : #ifdef EXPIRE_DFA_STATES
     106                 :            :         bool IsLocked() { return lock != 0; }
     107                 :            : #else
     108                 :       1438 :         bool IsLocked() { return true; }
     109                 :     504502 :         DFA_State* operator->(){ return this; }
     110                 :            : #endif
     111                 :            : 
     112                 :            : protected:
     113                 :            :         friend class DFA_State_Cache;
     114                 :            : 
     115                 :            :         DFA_State_Handle* ComputeXtion(int sym, DFA_Machine* machine);
     116                 :            :         void AppendIfNew(int sym, int_list* sym_list);
     117                 :            : 
     118                 :            :         int state_num;
     119                 :            :         int num_sym;
     120                 :            : 
     121                 :            :         DFA_State_Handle** xtions;
     122                 :            : 
     123                 :            :         AcceptingSet* accept;
     124                 :            :         NFA_state_list* nfa_states;
     125                 :            :         EquivClass* meta_ec;    // which ec's make same transition
     126                 :            :         DFA_State* mark;
     127                 :            :         int lock;
     128                 :            :         CacheEntry* centry;
     129                 :            : 
     130                 :            :         static unsigned int transition_counter; // see Xtion()
     131                 :            : };
     132                 :            : 
     133                 :            : struct CacheEntry {
     134                 :            :         DFA_State_Handle* state;
     135                 :            :         HashKey* hash;
     136                 :            :         CacheEntry* next;
     137                 :            :         CacheEntry* prev;
     138                 :            : };
     139                 :            : 
     140                 :            : class DFA_State_Cache {
     141                 :            : public:
     142                 :            :         DFA_State_Cache(int maxsize);
     143                 :            :         ~DFA_State_Cache();
     144                 :            : 
     145                 :            :         // If the caller stores the handle, it has to call Ref() on it.
     146                 :            :         DFA_State_Handle* Lookup(const NFA_state_list& nfa_states,
     147                 :            :                                         HashKey** hash);
     148                 :            : 
     149                 :            :         // Takes ownership of both; hash is the one returned by Lookup().
     150                 :            :         DFA_State_Handle* Insert(DFA_State* state, HashKey* hash);
     151                 :            : 
     152                 :            :         void MoveToFront(DFA_State* state)      { MoveToFront(state->centry); }
     153                 :            : 
     154                 :          0 :         int NumEntries() const  { return states.Length(); }
     155                 :            : 
     156                 :            :         struct Stats {
     157                 :            :                 unsigned int dfa_states;
     158                 :            : 
     159                 :            :                 // Sum over all NFA states per DFA state.
     160                 :            :                 unsigned int nfa_states;
     161                 :            :                 unsigned int computed;
     162                 :            :                 unsigned int uncomputed;
     163                 :            :                 unsigned int mem;
     164                 :            :                 unsigned int hits;
     165                 :            :                 unsigned int misses;
     166                 :            :         };
     167                 :            : 
     168                 :            :         void GetStats(Stats* s);
     169                 :            : 
     170                 :            : private:
     171                 :            :         void Remove(CacheEntry* e);
     172                 :            :         void MoveToFront(CacheEntry* e);
     173                 :            : 
     174                 :            :         int maxsize;
     175                 :            : 
     176                 :            :         int hits;       // Statistics
     177                 :            :         int misses;
     178                 :            : 
     179 [ -  + ][ #  # ]:       2120 :         declare(PDict,CacheEntry);
     180                 :            : 
     181                 :            :         // Hash indexed by NFA states (MD5s of them, actually).
     182                 :            :         PDict(CacheEntry) states;
     183                 :            : 
     184                 :            :         // List in LRU order.
     185                 :            :         CacheEntry* head;
     186                 :            :         CacheEntry* tail;
     187                 :            : };
     188                 :            : 
     189                 :            : declare(PList,DFA_State);
     190                 :            : typedef PList(DFA_State) DFA_state_list;
     191                 :            : 
     192                 :            : class DFA_Machine : public BroObj {
     193                 :            : public:
     194                 :            :         DFA_Machine(NFA_Machine* n, EquivClass* ec);
     195                 :            :         DFA_Machine(int** xtion_ptrs, int num_states, int num_ecs,
     196                 :            :                         int* acc_array);
     197                 :            :         ~DFA_Machine();
     198                 :            : 
     199                 :       6701 :         DFA_State_Handle* StartState() const    { return start_state; }
     200                 :            : 
     201                 :          0 :         int NumStates() const   { return dfa_state_cache->NumEntries(); }
     202                 :            : 
     203                 :          0 :         DFA_State_Cache* Cache()        { return dfa_state_cache; }
     204                 :            : 
     205                 :            :         int Rep(int sym);
     206                 :            : 
     207                 :            :         void Describe(ODesc* d) const;
     208                 :            :         void Dump(FILE* f);
     209                 :            :         void DumpStats(FILE* f);
     210                 :            : 
     211                 :            :         unsigned int MemoryAllocation() const;
     212                 :            : 
     213                 :            : protected:
     214                 :            :         friend class DFA_State; // for DFA_State::ComputeXtion
     215                 :            :         friend class DFA_State_Cache;
     216                 :            : 
     217                 :            :         int state_count;
     218                 :            : 
     219                 :            :         // The state list has to be sorted according to IDs.
     220                 :            :         int StateSetToDFA_State(NFA_state_list* state_set, DFA_State_Handle*& d,
     221                 :            :                                 const EquivClass* ec);
     222                 :        678 :         const EquivClass* EC() const    { return ec; }
     223                 :            : 
     224                 :            :         EquivClass* ec; // equivalence classes corresponding to NFAs
     225                 :            :         DFA_State_Handle* start_state;
     226                 :            :         DFA_State_Cache* dfa_state_cache;
     227                 :            : 
     228                 :            :         NFA_Machine* nfa;
     229                 :            : };
     230                 :            : 
     231                 :            : #ifdef EXPIRE_DFA_STATES
     232                 :            : 
     233                 :            : inline DFA_State_Handle* DFA_State::Xtion(int sym, DFA_Machine* machine)
     234                 :            :         {
     235                 :            :         Lock();
     236                 :            : 
     237                 :            :         // This is just a clumsy form of sampling... Instead of moving
     238                 :            :         // the state to the front of our LRU cache on each transition (which
     239                 :            :         // would be quite often) we just do it on every nth transition
     240                 :            :         // (counted across all DFA states). This is based on the observation
     241                 :            :         // that a very few of all states are used most of time.
     242                 :            :         // (currently n=10000; should it be configurable?)
     243                 :            :         if ( transition_counter++ % 10000 == 0 )
     244                 :            :                 machine->Cache()->MoveToFront(this);
     245                 :            : 
     246                 :            :         DFA_State_Handle* h;
     247                 :            : 
     248                 :            :         if ( xtions[sym] == DFA_UNCOMPUTED_STATE_PTR ||
     249                 :            :              (xtions[sym] && ! xtions[sym]->IsValid()) )
     250                 :            :                 h = ComputeXtion(sym, machine);
     251                 :            :         else
     252                 :            :                 h = xtions[sym];
     253                 :            : 
     254                 :            :         Unlock();
     255                 :            : 
     256                 :            :         return h;
     257                 :            :         }
     258                 :            : 
     259                 :            : inline DFA_State_Handle::~DFA_State_Handle()
     260                 :            :         {
     261                 :            :         if ( state != DFA_INVALID_STATE_PTR )
     262                 :            :                 delete state;
     263                 :            :         }
     264                 :            : 
     265                 :            : inline void DFA_State_Handle::Invalidate()
     266                 :            :         {
     267                 :            :         assert(state!=DFA_INVALID_STATE_PTR);
     268                 :            :         delete state;
     269                 :            :         state = DFA_INVALID_STATE_PTR;
     270                 :            :         Unref();
     271                 :            :         }
     272                 :            : 
     273                 :            : // Not nice but helps avoiding some overhead in the non-expiration case.
     274                 :            : static inline void StateLock(DFA_State_Handle* s)       { s->State()->Lock(); }
     275                 :            : static inline void StateUnlock(DFA_State_Handle* s)     { s->State()->Unlock(); }
     276                 :            : static inline void StateRef(DFA_State_Handle* s)        { s->Ref(); }
     277                 :            : static inline void StateUnref(DFA_State_Handle* s)      { s->Unref(); }
     278                 :            : static inline void StateInvalidate(DFA_State_Handle* s) { s->Invalidate(); }
     279                 :            : 
     280                 :            : static inline bool StateIsValid(DFA_State_Handle* s)
     281                 :            :         {
     282                 :            :         return ! s || s->IsValid();
     283                 :            :         }
     284                 :            : 
     285                 :            : #else
     286                 :            : 
     287                 :     256559 : inline DFA_State_Handle* DFA_State::Xtion(int sym, DFA_Machine* machine)
     288                 :            :         {
     289         [ +  + ]:     256559 :         if ( xtions[sym] == DFA_UNCOMPUTED_STATE_PTR )
     290                 :       1438 :                 return ComputeXtion(sym, machine);
     291                 :            :         else
     292                 :     256559 :                 return xtions[sym];
     293                 :            :         }
     294                 :            : 
     295                 :        444 : static inline void StateLock(DFA_State_Handle* s)       { }
     296                 :          4 : static inline void StateUnlock(DFA_State_Handle* s)     { }
     297                 :       1934 : static inline void StateRef(DFA_State_Handle* s)        { }
     298                 :          4 : static inline void StateUnref(DFA_State_Handle* s)      { }
     299                 :          4 : static inline void StateInvalidate(DFA_State_Handle* s) { }
     300                 :       1260 : static inline bool StateIsValid(DFA_State_Handle* s)    { return true; }
     301                 :            : 
     302                 :            : #endif
     303                 :            : 
     304                 :            : #endif

Generated by: LCOV version 1.8