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
|