1 /*
2 * ufdbLookup.c - URLfilterDB
3 *
4 * ufdbGuard is copyrighted (C) 2005-2018 by URLfilterDB with all rights reserved.
5 *
6 * Parts of the ufdbGuard daemon are based on squidGuard.
7 * squidGuard is copyrighted (C) 1998 by
8 * ElTele �st AS, Oslo, Norway, with all rights reserved.
9 *
10 * $Id: ufdbLookup.c,v 1.41 2020/06/27 18:11:33 root Exp root $
11 */
12
13 #include "ufdb.h"
14 #include "sg.h"
15 #include "ufdblib.h"
16 #include "ufdbdb.h"
17
18 #include <string.h>
19
20 #ifdef __cplusplus
21 extern "C" {
22 #endif
23
24
25 UFDB_GCC_HOT UFDB_GCC_INLINE
memDBhash(const char * k)26 static ufdb_memdb_hash_t memDBhash( const char * k )
27 {
28 ufdb_memdb_hash_t hash;
29
30 hash = ((45203339UL * *k) ^ (*(k+1) * 35201123UL)) + ((ufdb_memdb_hash_t)*k << 3);
31 while (*k != '\0')
32 {
33 hash = (hash * 317) ^ ((ufdb_memdb_hash_t) *k * 18003133UL);
34 k++;
35 }
36
37 return ((ufdb_memdb_hash_t) hash);
38 }
39
40
41 /*
42 * create an in-memory database (kv-pairs)
43 */
UFDBmemDBinit(void)44 struct UFDBmemDB * UFDBmemDBinit( void )
45 {
46 struct UFDBmemDB * m;
47
48 m = (struct UFDBmemDB *) ufdbMallocAligned( UFDB_CACHELINE_SIZE, sizeof(struct UFDBmemDB) );
49 if (m == NULL)
50 {
51 ufdbLogFatalError( "UFDBmemDBinit: cannot allocate memory" );
52 return NULL;
53 }
54
55 m->tableSize = 37;
56 m->nEntries = 0;
57 m->optimalMaxEntries = (unsigned int) (m->tableSize * 0.70);
58 m->table = (UFDBmemDBkv **) ufdbCalloc( sizeof(UFDBmemDBkv*), m->tableSize );
59
60 return m;
61 }
62
63
memDBexpand(struct UFDBmemDB * db)64 static void memDBexpand(
65 struct UFDBmemDB * db )
66 {
67 unsigned int newTableSize;
68 unsigned int i, j;
69 UFDBmemDBkv * kv;
70 UFDBmemDBkv * next;
71 UFDBmemDBkv ** newtable;
72 /* http://compoasso.free.fr/primelistweb/page/prime/liste_online_en.php */
73 unsigned int primeTable[20] = { 107, 331, 967, 2887, 8663,
74 17333, 34667, 69313, 104723, 170047,
75 290027, 480017, 840023, 1500133, 2500151,
76 4000133, 7000121, 12001021, 20001031, 35001133 };
77
78 if (db->tableSize >= primeTable[19])
79 newTableSize = db->tableSize * 2 - 3;
80 else
81 {
82 for (i = 0; i < 20; i++)
83 {
84 if (primeTable[i] > db->tableSize)
85 break;
86 }
87 newTableSize = primeTable[i];
88 }
89
90 if (ufdbGV.debug > 1)
91 ufdbLogMessage( " memDBexpand: cache %08lx old size %u new size %u",
92 (unsigned long) db, db->tableSize, newTableSize );
93
94 newtable = (UFDBmemDBkv**) ufdbCalloc( sizeof(UFDBmemDBkv*), newTableSize );
95 if (newtable == NULL)
96 {
97 ufdbLogFatalError( "memDBexpand: cannot allocate memory to expand table to %u entries", newTableSize );
98
99 /* workaround to prevent calling expandTable all the time: */
100 db->optimalMaxEntries = db->tableSize;
101
102 return;
103 }
104
105 for (i = 0; i < db->tableSize; i++)
106 {
107 kv = db->table[i];
108 while (kv != NULL)
109 {
110 next = kv->next;
111
112 /* put the entry in the new table (at the new position) */
113 j = (unsigned int) (kv->hash % newTableSize);
114 kv->next = newtable[j];
115 newtable[j] = kv;
116
117 kv = next;
118 }
119 }
120
121 db->tableSize = newTableSize;
122 db->optimalMaxEntries = (unsigned int) (newTableSize * 0.70);
123
124 ufdbFree( db->table );
125 db->table = newtable;
126 }
127
128
UFDBmemDBinsert(struct UFDBmemDB * db,const char * key,const char * value)129 void UFDBmemDBinsert(
130 struct UFDBmemDB * db,
131 const char * key,
132 const char * value )
133 {
134 UFDBmemDBkv * kv;
135 unsigned int i;
136
137 #if 0
138 ufdbLogError( " UFDBmemDBinsert( db=%08x, %s, XXX )", db, key );
139 #endif
140
141 if (key == NULL)
142 {
143 ufdbLogError( "UFDBmemDBinsert: key is NULL. value is %s *****", value==NULL ? "NULL" : value );
144 return;
145 }
146 if (*key == '\0')
147 {
148 ufdbLogError( "UFDBmemDBinsert: key is empty. value is %s *****", value==NULL ? "NULL" : value );
149 return;
150 }
151
152 kv = (struct UFDBmemDBkv *) ufdbMalloc( sizeof(UFDBmemDBkv) );
153 if (kv == NULL)
154 {
155 ufdbLogFatalError( "UFDBmemDBinsert: cannot allocate memory" );
156 return;
157 }
158 kv->key = ufdbStrdup( key );
159 if (value == NULL)
160 kv->value = NULL;
161 else
162 kv->value = ufdbStrdup( value );
163 kv->hash = memDBhash( key );
164 /* TO-DO: prevent duplicates */
165
166 i = (unsigned int) (kv->hash % db->tableSize);
167 kv->next = db->table[i];
168 db->table[i] = kv;
169
170 db->nEntries++;
171 if (db->nEntries > db->optimalMaxEntries)
172 memDBexpand( db );
173 }
174
175
176 UFDB_GCC_HOT
UFDBmemDBfind(struct UFDBmemDB * db,const char * key,char ** value)177 int UFDBmemDBfind(
178 struct UFDBmemDB * db,
179 const char * key,
180 char ** value )
181 {
182 UFDBmemDBkv * kv;
183 ufdb_memdb_hash_t hash;
184 unsigned int i;
185
186 #if 0
187 ufdbLogError( " UFDBmemDBfind( db=%08x, %s )", db, key );
188 #endif
189
190 if (db == NULL)
191 return 0;
192
193 hash = memDBhash( key );
194 i = (unsigned int) (hash % db->tableSize);
195 kv = db->table[i];
196 while (kv != NULL)
197 {
198 if (kv->hash == hash && strcmp( kv->key, key ) == 0)
199 {
200 *value = kv->value;
201 return 1;
202 }
203 kv = kv->next;
204 }
205
206 return 0;
207 }
208
209
210 UFDB_GCC_HOT
UFDBmemDBfindDomain(struct UFDBmemDB * db,const char * domain)211 int UFDBmemDBfindDomain(
212 struct UFDBmemDB * db,
213 const char * domain )
214 {
215 const char * d;
216 unsigned int i;
217 UFDBmemDBkv * kv;
218
219 #if 0
220 ufdbLogError( " UFDBmemDBfindDomain( db=%08x, %s )", db, domain );
221 #endif
222
223 if (db == NULL)
224 return 0;
225
226 /* When finding a domain we face a problem with subdomains: subdomains must be matched
227 * but they do not appear in the hashtable: only the parent domain is in the table.
228 * Strategy: since the table is very small, do a linear search.
229 */
230
231 for (i = 0; i < db->tableSize; i++)
232 {
233 kv = db->table[i];
234 while (kv != NULL)
235 {
236 d = strstr( domain, kv->key );
237 if (d != NULL)
238 {
239 if (d == domain)
240 {
241 if (strcmp( d, kv->key ) == 0)
242 return 1;
243 }
244 else
245 {
246 if (*(d-1) == '.' && strcmp( d, kv->key ) == 0)
247 return 1;
248 }
249 }
250 kv = kv->next;
251 }
252 }
253 return 0;
254 }
255
256
UFDBmemDBdeleteDB(struct UFDBmemDB * db)257 void UFDBmemDBdeleteDB(
258 struct UFDBmemDB * db )
259 {
260 unsigned int i;
261 UFDBmemDBkv * kv;
262 UFDBmemDBkv * next;
263
264 for (i = 0; i < db->tableSize; i++)
265 {
266 kv = db->table[i];
267 while (kv != NULL)
268 {
269 ufdbFree( kv->key );
270 ufdbFree( kv->value );
271 next = kv->next;
272 ufdbFree( kv );
273 kv = next;
274 }
275 }
276 ufdbFree( db->table );
277 db->table = NULL; // to reduce reachable leaks in valgrind reports
278 ufdbFree( db );
279 }
280
281
UFDBmemDBprintUserDB(const char * prefix,struct UFDBmemDB * db)282 void UFDBmemDBprintUserDB(
283 const char * prefix,
284 struct UFDBmemDB * db )
285 {
286 unsigned int i;
287 UFDBmemDBkv * kv;
288
289 if (db == NULL)
290 return;
291
292 if (ufdbGV.debug)
293 ufdbLogMessage( " # hash table for \"%s\" has size %u and %u entries",
294 prefix, db->tableSize, db->nEntries );
295
296 for (i = 0; i < db->tableSize; i++)
297 {
298 kv = db->table[i];
299 while (kv != NULL)
300 {
301 if (ufdbGV.debug > 2)
302 ufdbLogMessage( " %s %-15s %6u %22lu", prefix, kv->key, i, (unsigned long) kv->hash );
303 else
304 ufdbLogMessage( " %s %s", prefix, kv->key );
305 kv = kv->next;
306 }
307 }
308 }
309
310
311 #ifdef __cplusplus
312 }
313 #endif
314