Debian Codegraph @

src/DynamicURLList.cpp

raw
1 // For all support, instructions and copyright go to:
2 // http://e2guardian.org/
3 // Released under the GPL v2, with the OpenSSL exception described in the README file.
4
5 // INCLUDES
6
7 #ifdef HAVE_CONFIG_H
8 #include "e2config.h"
9 #endif
10 #include "OptionContainer.hpp"
11 #include "DynamicURLList.hpp"
12 #include "Logger.hpp"
13
14 #include <string.h>
15 #include <algorithm>
16 #include <ctime>
17 #include <sys/stat.h>
18 #include <sys/time.h>
19
20 // GLOBALS
21
22 extern OptionContainer o;
23
24 // IMPLEMENTATION
25
26 // note - the list of URLs itself is simply a ring buffer, so the oldest entry/next empty entry is always the
27 // last position we wrote to plus one, wrapping round when we get to the top.
28 // however, we also maintain a seperate index list, which points to the entries in alphabetical order.
29
30 // constructor - initialise values to empty defaults
31 DynamicURLList::DynamicURLList()
32 : index(NULL), urlreftime(NULL), urls(NULL), groups(NULL), size(0), agepos(0), timeout(0), items(0)
33 {
34 }
35
36 // delete the memory block when the class is destryed
37 DynamicURLList::~DynamicURLList()
38 {
39 delete[] index;
40 delete[] urlreftime;
41 delete[] urls;
42 delete[] groups;
43 }
44
45 // "flush" the list (not quite)
46 void DynamicURLList::flush()
47 {
48 // make all entries old so they won't be used
49 for (int i = 0; i < items; i++) {
50 urlreftime[index[i]] = 0;
51 }
52 }
53
54 // find the position of the given URL in the list
55 // return value ranges:
56 // -ve if not found. 0-(pos + 1) is where it should be inserted to retain sorting.
57 // 0 to size if found
58 int DynamicURLList::posInList(const char *url)
59 {
60 if (items == 0) {
61 DEBUG_debug("url list cache is empty");
62 // if the list is empty, indicate that the entry should go in pos 0
63 return -1;
64 }
65 E2LOGGER_error("url list cache: performing search...");
66 return search(0, items - 1, url);
67 }
68
69 // binary search the list for a given URL
70 // note the list itself is not ordered, but the index array is
71 int DynamicURLList::search(int a, int s, const char *url)
72 {
73 if (a > s)
74 return (-1 - a);
75 int m = (a + s) / 2;
76 // look up the url pointed to by this entry in the index
77 char *i = index[m] * 1000 + urls;
78
79 int alen = strlen(i);
80 int blen = strlen(url);
81 int maxlen = alen < blen ? alen : blen;
82 char *apos = (char *)i;
83 char *bpos = (char *)url;
84 int j = 0;
85 int c = 0;
86 unsigned char achar;
87 unsigned char bchar;
88 while (j < maxlen) {
89 achar = apos[0];
90 bchar = bpos[0];
91 if (achar > bchar) {
92 c = 1;
93 break;
94 }
95 if (achar < bchar) {
96 c = -1;
97 break;
98 }
99 j++;
100 apos++;
101 bpos++;
102 }
103 if (c == 0) {
104 if (alen > blen) {
105 c = 1;
106 } else if (alen < blen) {
107 c = -1;
108 }
109 }
110 // otherwise, assume both equal
111
112 // we found the entry
113 if (c == 0)
114 return m;
115 // we didn't, but it's in the lower half
116 if (c == -1)
117 return search(m + 1, s, url);
118 // we got the search window down to 1 entry
119 if (a == s)
120 // therefore, we know where the entry we were looking for
121 // should be added if we are to maintain a sorted list.
122 // return its position, -ve (and strictly below 0), so as to
123 // provide useful information and not mess up return value checks.
124 return (-1 - a);
125 // we didn't find it, but it's in the upper half
126 return search(a, m - 1, url);
127 }
128
129 // sets how many URLs the list should store, and the maximum age of an entry before it goes inactive
130 bool DynamicURLList::setListSize(unsigned int s, unsigned int t)
131 {
132 if (s < 2) {
133 return false;
134 }
135 if (t < 2) {
136 return false;
137 }
138 size = s;
139 timeout = t;
140 agepos = 0;
141 items = 0;
142 delete[] index;
143 delete[] urlreftime;
144 delete[] urls;
145 delete[] groups;
146
147 index = new unsigned int[size];
148 urlreftime = new unsigned long int[size];
149 urls = new char[size * 1000]; // allows url up to 999 in length
150 groups = new std::string[size];
151 return true;
152 }
153
154 // see if the given URL is in the list
155 bool DynamicURLList::inURLList(const char *url, const int fg)
156 {
157 DEBUG_debug("url cache search request: ", fg, " ", url);
158 if (items == 0) {
159 return false;
160 }
161 #ifdef DEBUG_LOW
162 DEBUG_debug("****** url cache table ******");
163 DEBUG_debug("items: ", items);
164 for (int i = 0; i < items; i++) {
165 std::stringstream ss;
166 for (unsigned int j = 0; j < groups[index[i]].length(); j++) {
167 ss << (unsigned int)(groups[index[i]][j]) << " ";
168 }
169 ss << (char *)(index[i] * 1000 + urls);
170 DEBUG_debug(ss.str());
171 }
172 DEBUG_debug("****** url cache table ******");
173 #endif
174
175 // truncate URL if necessary, as we have a length limit on our buffers
176 int pos;
177 if (strlen(url) > 999) {
178 String r(String(url, 999));
179 pos = posInList(r.toCharArray());
180 } else {
181 pos = posInList(url);
182 }
183
184 DEBUG_debug("pos: ", pos);
185
186 // if we have found an entry, also check to see that it hasn't gone inactive.
187 // todo: could we speed things up a little by simply refreshing the timer on the
188 // old entry here, instead of having addEntry look for possible duplicates?
189 // actually, i dunno. are URLs from time-limited lists cached? this might cause them to
190 // continue being seen as good/bad (depending on the nature of the list) outside the
191 // allotted window if they get put in the cache during it.
192 if (pos > -1) {
193 unsigned long int timenow = time(NULL);
194 if ((timenow - urlreftime[index[pos]]) > timeout) {
195 DEBUG_debug("found but url ttl exceeded: ", (timenow - urlreftime[index[pos]]));
196 return false;
197 }
198 // o.filter_groups + 1 is a special case, meaning clean for all groups
199 std::string lookfor;
200 lookfor += (char)fg;
201 lookfor += (char)o.filter.filter_groups + 1;
202 if (groups[index[pos]].find_first_of(lookfor) == std::string::npos) {
203 #ifdef DEBUG_LOW
204 std::stringstream ss;
205 for (unsigned int j = 0; j < groups[index[pos]].length(); j++) {
206 ss << (unsigned int)(groups[index[pos]][j]) << " ";
207 }
208 DEBUG_debug("found but url not flagged clean for this group: ", fg, " (is clean for: ", ss.str(), ")" );
209 #endif
210 return false;
211 }
212 return true;
213 }
214 return false;
215 }
216
217 // add an entry to the URL list - if it's already there, but timed out due to age, simply refresh the timer
218 // also, maintain the lists' sorting, to allow binary search to be performed
219 void DynamicURLList::addEntry(const char *url, const int fg)
220 {
221 DEBUG_debug("url cache add request: ", fg, " ", url, " itemsbeforeadd: ", items);
222 int len = strlen(url);
223 bool resized = false;
224 char *u;
225 // truncate the URL if it's too long
226 if (len > 999) {
227 u = new char[1000];
228 u[999] = '\0';
229 // bugfix - previously, truncation did the above termination, but no string copy!
230 // this might never have been noticed due to high buffer size & correct termination preventing the bug causing a crash.
231 memcpy(u, url, 999);
232 resized = true;
233 len = 999;
234 } else {
235 u = (char *)url;
236 }
237 int pos = posInList(u);
238 if (pos >= 0) { // found
239 if (resized) {
240 delete[] u;
241 }
242 DEBUG_debug("Entry found at pos: ", pos);
243 urlreftime[index[pos]] = time(NULL); // reset refresh counter
244 if (groups[index[pos]].find((char)fg, 0) == std::string::npos)
245 groups[index[pos]] += (char)fg; // flag it as clean for this filter group
246 return; // not going to add entry thats there already
247 }
248
249 pos = 0 - pos - 1; // now contains the insertion point
250
251 DEBUG_debug("insertion pos: ", pos, " size: ", size);
252
253 // the list isn't full, so simply push new entry onto the back
254 if (items < size) {
255 DEBUG_debug("items<size: ", items, "<", size);
256 char *urlref;
257 urlref = items * 1000 + urls;
258 memcpy(urlref, u, len);
259 urlref[len] = '\0';
260 urlreftime[items] = time(NULL);
261 int i;
262 // shift alphabetical index list below the insertion point down by one,
263 // and insert our new item.
264 for (i = items; i > pos; i--) {
265 index[i] = index[i - 1];
266 }
267 index[pos] = items;
268 groups[items] = (char)fg;
269 items++;
270 if (resized) {
271 delete[] u;
272 }
273 return;
274 }
275
276 // list is full, so we can't simply push a new entry on to it.
277 // now replace the oldest entry but first need to find it in
278 // the index to remove from there. old entries don't get deleted, just overwritten!
279
280 // we know the pos in the list of the oldest URL, but not where it is in our sorted index list
281 char *oldestref = urls + agepos * 1000;
282
283 // now contains pos in sorted index of what we're going to overwrite
284 int delpos = posInList(oldestref);
285
286 // do the actual overwriting, including termination and setting birthdate to now
287 memcpy(oldestref, u, len);
288 oldestref[len] = '\0';
289 urlreftime[agepos] = time(NULL);
290 groups[agepos] = (char)fg;
291
292 // now shuffle the index list to remain sorted
293 // remember: pos contains the alphabetical position of what we just added,
294 // delpos contains the alphabetical position of the previous oldest entry,
295 // and agepos contains the actual position in the string list of the entry we just wrote
296 if (delpos == pos) {
297 // the alphabetical pos of what we just deleted and what we just wrote are one and the same
298 // so simply update the one index value to contain a ref to the new entry
299 index[pos] = agepos;
300 } else if (delpos < pos) {
301 // the alphabetical pos of what we deleted was less than what we just wrote
302 // so shift the list entries between the two up by one (losing delpos), and insert our entry
303 int endpos = pos - 1;
304 for (int i = delpos; i < endpos; i++) {
305 index[i] = index[i + 1];
306 }
307 index[pos - 1] = agepos;
308 } else if (delpos > pos) {
309 // the alphabetical pos of what we just deleted was greater than what we just added,
310 // so starting from the old pos, work backwards, shifting the entries down by one
311 // then insert our new entry
312 for (int i = delpos; i > pos; i--) {
313 index[i] = index[i - 1];
314 }
315 index[pos] = agepos;
316 }
317 // the index is now sorted, but the actual list of strings itself is sorted oldest first.
318 // increase the age pointer to the next empty entry - once we get to the end, wrap round
319 // to the top, and overwrite the entries oldest first.
320
321 // todo: things might speed up if we simply maintain the agepos as an index into the sorted index array,
322 // rather than an index on the real URL list. then we wouldn't need to do a posInList to find the agepos's
323 // sorted index every time we do an add.
324 agepos++;
325 if (agepos == size) {
326 agepos = 0;
327 }
328
329 if (resized) {
330 delete[] u;
331 }
332 }