1 /*
2 * ufdbHashtable.c - URLfilterDB
3 *
4 * ufdbGuard is copyrighted (C) 2005-2015 by URLfilterDB with all rights reserved.
5 *
6 * Parts of the ufdbGuard daemon are based on squidGuard.
7 * This module is entirely written by URLfilterDB.
8 *
9 * RCS $Id: ufdbHashtable.c,v 1.12 2020/06/27 18:09:54 root Exp root $
10 */
11
12 #include "ufdb.h"
13 #include "ufdblib.h"
14 #include "ufdbchkport.h"
15 #include "httpsQueue.h"
16 #include "ufdbHashtable.h"
17
18 #include <strings.h>
19 #include <string.h>
20 #include <stdlib.h>
21
22 #ifdef __cplusplus
23 extern "C" {
24 #endif
25
26
27 /* expandHashtable:
28 * on entry: ht->mutex MUST be locked.
29 * on exit: ht->mutex remains locked.
30 */
expandHashtable(struct UFDBhashtable * ht)31 static void expandHashtable(
32 struct UFDBhashtable * ht )
33 {
34 unsigned int newTableSize;
35 unsigned int i, j;
36 struct UFDBhte * hte;
37 struct UFDBhte ** newtable;
38
39 /* Whenever expeandHashtable is called, the ht->mutex is already locked,
40 * so we do not use it in this function.
41 */
42
43 newTableSize = ht->tableSize * 2 - 3; /* 107, 211, 419, 835, ... */
44
45 if (ufdbGV.debug > 1)
46 ufdbLogMessage( " expandHashtable: cache %08lx old size %d new size %d",
47 (unsigned long) ht, ht->tableSize, newTableSize );
48
49 newtable = (struct UFDBhte **) ufdbCalloc( sizeof(struct UFDBhte*), newTableSize );
50 if (newtable == NULL)
51 {
52 /* Oops, we ran out of memory.
53 * Well, we just return without expanding the table
54 * since the memory allocation error is in this stage
55 * not severe and the application can go on.
56 */
57
58 /* horrible workaround to prevent calling expandTable all the time: */
59 ht->optimalMaxEntries = (unsigned int) (ht->tableSize * 0.88);
60
61 /* TO-DO: removeOldEntriesFromCache( ht ); */
62 return;
63 }
64
65 for (i = 0; i < ht->tableSize; i++)
66 {
67 while ((hte = ht->table[i]) != NULL)
68 {
69 /* TODO: remove old entries (>3 hours) in this copy process */
70 ht->table[i] = hte->next;
71
72 /* put the entry in the new table (at the new position) */
73 j = hte->hash % newTableSize;
74 hte->next = newtable[j];
75 newtable[j] = hte;
76 }
77 }
78
79 ht->tableSize = newTableSize;
80 ht->optimalMaxEntries = (unsigned int) (newTableSize * 0.68);
81
82 ufdbFree( ht->table );
83 ht->table = newtable;
84 }
85
86
87 /* UFDBcreateHashtable:
88 * on entry: ht->mutex does not exist
89 * on exit: ht->mutex is created (not locked).
90 */
91 struct UFDBhashtable *
UFDBcreateHashtable(unsigned int tableSize,unsigned int (* hashFunction)(const void *),int (* keyEqFunction)(const void *,const void *))92 UFDBcreateHashtable(
93 unsigned int tableSize,
94 unsigned int (*hashFunction) (const void*),
95 int (*keyEqFunction) (const void*,const void*) )
96 {
97 struct UFDBhashtable * ht;
98 pthread_mutexattr_t attr;
99
100 ht = (struct UFDBhashtable *) ufdbMallocAligned( UFDB_CACHELINE_SIZE, sizeof(struct UFDBhashtable) );
101 if (ht == NULL)
102 return NULL;
103
104 if (tableSize < 107)
105 tableSize = 107;
106 if (tableSize % 2 == 0)
107 tableSize++;
108
109 ht->tableSize = tableSize;
110 ht->table = (struct UFDBhte **) ufdbCalloc( sizeof(struct UFDBhte*), tableSize );
111 if (ht->table == NULL)
112 return NULL;
113 ht->nEntries = 0;
114 ht->optimalMaxEntries = (unsigned int) (tableSize * 0.68);
115 ht->hashFunction = hashFunction;
116 ht->keyEqFunction = keyEqFunction;
117
118 pthread_mutexattr_init( &attr );
119 pthread_mutexattr_settype( &attr, ufdbGV.debug>3 ? PTHREAD_MUTEX_ERRORCHECK : PTHREAD_MUTEX_NORMAL );
120 pthread_mutex_init( &(ht->mutex), NULL );
121
122 return ht;
123 }
124
125
126 /* UFDBinsertHashtable:
127 * on entry: ht->mutex is locked IFF lockSetBySearch != 0
128 * on exit: ht->mutex MUST be unlocked.
129 *
130 * key MUST be malloced.
131 * value MUST be malloced.
132 */
133 void
UFDBinsertHashtable(struct UFDBhashtable * ht,void * key,void * value,int lockSetBySearch)134 UFDBinsertHashtable(
135 struct UFDBhashtable * ht,
136 void * key,
137 void * value,
138 int lockSetBySearch )
139 {
140 unsigned int i;
141 int ps;
142 struct UFDBhte * hte;
143
144 if (!lockSetBySearch)
145 {
146 ps = pthread_mutex_lock( &ht->mutex ); /* ========================== */
147 if (ps != 0)
148 {
149 ufdbGV.crashOnFatal = 1;
150 ufdbLogFatalError( "UFDBinsertHashtable: pthread_mutex_lock returned %d", ps );
151 }
152 /* TODO: must search again after acquiring lock !!! */
153 }
154
155 hte = (struct UFDBhte *) ufdbMalloc( sizeof(struct UFDBhte) );
156 if (hte == NULL)
157 {
158 ps = pthread_mutex_unlock( &ht->mutex );
159 if (ps != 0)
160 {
161 ufdbGV.crashOnFatal = 1;
162 ufdbLogFatalError( "UFDBinsertHashtable: pthread_mutex_unlock/1 returned %d", ps );
163 }
164 return;
165 }
166 hte->hash = ht->hashFunction( key );
167 hte->key = key;
168 hte->value = value;
169
170 i = hte->hash % ht->tableSize;
171 hte->next = ht->table[i];
172 ht->table[i] = hte;
173
174 ht->nEntries++;
175
176 /* TODO: implement safeguard against duplicates in Hashtable */
177
178 /* TODO: better cache management: HTE must have lastQueryTime */
179
180 if (ht->nEntries > ht->optimalMaxEntries)
181 expandHashtable( ht );
182
183 ps = pthread_mutex_unlock( &ht->mutex ); /* ========================== */
184 if (ps != 0)
185 {
186 ufdbGV.crashOnFatal = 1;
187 ufdbLogFatalError( "UFDBinsertHashtable: pthread_mutex_unlock/2 returned %d", ps );
188 }
189
190 if (ufdbGV.debug > 1)
191 ufdbLogMessage( " UFDBinsertHashtable: cache %08lx key %08lx '%s' hash %08lx value %08lx nEntries %d",
192 (unsigned long) ht, (unsigned long) hte->key, (char *) hte->key, (unsigned long) hte->hash, (unsigned long) hte->value, ht->nEntries );
193 }
194
195
196 /* UFDBunlockHashtable:
197 * on entry: ht->mutex MUST be locked.
198 * on exit: ht->mutex MUST be unlocked.
199 */
UFDBunlockHashtable(struct UFDBhashtable * ht)200 void UFDBunlockHashtable(
201 struct UFDBhashtable * ht )
202 {
203 int ps;
204
205 ps = pthread_mutex_unlock( &ht->mutex );
206 if (ps != 0)
207 {
208 ufdbGV.crashOnFatal = 1;
209 ufdbLogFatalError( "UFDBunlockHashtable: pthread_mutex_unlock returned %d", ps );
210 }
211 }
212
213
214 /* UFDBlockHashtable:
215 * on entry: ht->mutex MUST be unlocked.
216 * on exit: ht->mutex MUST be locked.
217 */
UFDBlockHashtable(struct UFDBhashtable * ht)218 void UFDBlockHashtable(
219 struct UFDBhashtable * ht )
220 {
221 int ps;
222
223 ps = pthread_mutex_lock( &ht->mutex );
224 if (ps != 0)
225 {
226 ufdbGV.crashOnFatal = 1;
227 ufdbLogFatalError( "UFDBlockHashtable: pthread_mutex_lock returned %d", ps );
228 }
229 }
230
231
232 /* UFDBsearchHashtable:
233 * on entry: ht->mutex MUST be unlocked.
234 * on exit: ht->mutex is locked, but unlocked IFF retval != NULL || keepLockForInsert != 0
235 */
236 void *
UFDBsearchHashtable(struct UFDBhashtable * ht,void * key,int keepLockForInsert)237 UFDBsearchHashtable(
238 struct UFDBhashtable * ht,
239 void * key,
240 int keepLockForInsert )
241 {
242 unsigned int hash;
243 unsigned int i;
244 int ps;
245 void * retval;
246 struct UFDBhte * hte;
247
248 retval = NULL;
249 hash = ht->hashFunction( key );
250
251 ps = pthread_mutex_lock( &ht->mutex ); /* ===================================== */
252 if (ps != 0)
253 {
254 ufdbGV.crashOnFatal = 1;
255 ufdbLogFatalError( "UFDBsearchHashtable: pthread_mutex_lock failed with error code %d", ps );
256 }
257
258 i = hash % ht->tableSize;
259 hte = ht->table[i];
260 while (hte != NULL)
261 {
262 if (hte->hash == hash && ht->keyEqFunction(key,hte->key))
263 {
264 retval = hte->value;
265 break;
266 }
267 hte = hte->next;
268 }
269
270 if (ufdbGV.debug > 1)
271 ufdbLogMessage( " UFDBsearchHashtable: cache %08lx key '%s' hash %08lx value %08lx keeplock %d",
272 (unsigned long) ht, (char *) key, (unsigned long) hash, (unsigned long) retval, keepLockForInsert );
273
274 if (retval != NULL || !keepLockForInsert)
275 {
276 ps = pthread_mutex_unlock( &ht->mutex ); /* ===================================== */
277 if (ps != 0)
278 {
279 ufdbGV.crashOnFatal = 1;
280 ufdbLogFatalError( "UFDBsearchHashtable: pthread_mutex_unlock failed with error code %d", ps );
281 }
282 }
283
284 return retval;
285 }
286
287
288 /* UFDBremoveHashtable:
289 * on entry: ht->mutex MUST be locked.
290 * on exit: ht->mutex remains locked.
291 * return: hte->value
292 */
293 void *
UFDBremoveHashtable(struct UFDBhashtable * ht,void * key)294 UFDBremoveHashtable(
295 struct UFDBhashtable * ht,
296 void * key )
297 {
298 unsigned int hash;
299 unsigned int i;
300 struct UFDBhte * hte;
301 struct UFDBhte ** head_hte;
302 void * retval;
303
304 retval = NULL;
305 hash = ht->hashFunction( key );
306
307 if (ufdbGV.debug > 1)
308 ufdbLogMessage( " UFDBremoveHashtable: cache %08lx key %08lx %s hash %08lx",
309 (unsigned long) ht, (unsigned long) key, (char *) key, (unsigned long) hash );
310
311 i = hash % ht->tableSize;
312 head_hte = &( ht->table[i] );
313 hte = *head_hte;
314 while (hte != NULL)
315 {
316 if (hte->hash == hash && ht->keyEqFunction(key,hte->key))
317 {
318 *head_hte = hte->next;
319 retval = hte->value;
320 ufdbFree( hte->key );
321 ufdbFree( hte );
322 ht->nEntries--;
323 break;
324 }
325 head_hte = &hte->next;
326 hte = hte->next;
327 }
328
329 if (hte == NULL)
330 ufdbLogError( "UFDBremoveHashtable: did not find key %08lx in cache %08lx *****", (unsigned long) key, (unsigned long) ht );
331
332 return retval;
333 }
334
335
336 /* UFDBpurgeHashtable:
337 * on entry: ht->mutex MUST be locked.
338 * on exit: ht->mutex remains locked.
339 */
340 int
UFDBpurgeHashtable(struct UFDBhashtable * ht,int (* purge_test)(const void * key,const void * value))341 UFDBpurgeHashtable(
342 struct UFDBhashtable * ht,
343 int (*purge_test)(const void * key, const void * value) )
344 {
345 unsigned int i;
346 int n;
347 struct UFDBhte * hte;
348 struct UFDBhte * next;
349 struct UFDBhte ** prev;
350
351 n = 0;
352
353 if (ufdbGV.debug > 1)
354 ufdbLogMessage( " UFDBpurgeHashtable: cache %08lx tableSize %d nEntries %d opt-max %d",
355 (unsigned long) ht, ht->tableSize, ht->nEntries, ht->optimalMaxEntries );
356
357 for (i = 0; i < ht->tableSize; i++)
358 {
359 prev = &ht->table[i];
360 hte = *prev;
361 while (hte != NULL)
362 {
363 next = hte->next;
364 if (purge_test( hte->key, hte->value ))
365 {
366 n++;
367 ufdbFree( hte->value );
368 ufdbFree( hte->key );
369 ufdbFree( hte );
370 *prev = next;
371 ht->nEntries--;
372 }
373 else
374 prev = &hte->next;
375 hte = next;
376 }
377 }
378
379 return n;
380 }
381
382
383 /* UFDBdestroyHashtable:
384 * on entry: ht->mutex MUST be unlocked.
385 * on exit: ht->mutex is unlocked and destroyed.
386 */
387 void
UFDBdestroyHashtable(struct UFDBhashtable * ht,int freeValues)388 UFDBdestroyHashtable(
389 struct UFDBhashtable * ht,
390 int freeValues )
391 {
392 unsigned int i;
393 int ps;
394 struct UFDBhte * hte;
395 struct UFDBhte * next;
396
397 /* Hmmm. The table will be destroyed and it is not
398 * very useful to use the mutex.
399 * But we use the mutex anyway to wait for any
400 * current use of the table to terminate.
401 */
402 ps = pthread_mutex_lock( &ht->mutex ); /* ============================= */
403 if (ps != 0)
404 {
405 ufdbGV.crashOnFatal = 1;
406 ufdbLogFatalError( "UFDBdestroyHashtable: pthread_mutex_lock returned %d", ps );
407 }
408
409 for (i = 0; i < ht->tableSize; i++)
410 {
411 hte = ht->table[i];
412 while (hte != NULL)
413 {
414 next = hte->next;
415 ufdbFree( hte->key );
416 if (freeValues)
417 ufdbFree( hte->value );
418 ufdbFree( hte );
419 hte = next;
420 }
421 }
422 ufdbFree( ht->table );
423
424 ps = pthread_mutex_unlock( &ht->mutex ); /* ============================= */
425 if (ps != 0)
426 {
427 ufdbGV.crashOnFatal = 1;
428 ufdbLogFatalError( "UFDBdestroyHashtable: pthread_mutex_unlock returned %d", ps );
429 }
430 pthread_mutex_destroy( &ht->mutex );
431
432 /* ht contains the mutex, so it must be freed after the unlock(mutex) */
433 ufdbFree( ht );
434 }
435
436
437 #ifdef __cplusplus
438 }
439 #endif
440