| 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 |
} |