1 /*
2 * Copyright (c) 1993-2001 by Sun Microsystems, Inc.
3 * All rights reserved.
4 */
5
6 #pragma ident "%Z%%M% %I% %E% SMI"
7
8 /*
9 * Copyright 1988, 1991 by Carnegie Mellon University
10 *
11 * All Rights Reserved
12 *
13 * Permission to use, copy, modify, and distribute this software and its
14 * documentation for any purpose and without fee is hereby granted, provided
15 * that the above copyright notice appear in all copies and that both that
16 * copyright notice and this permission notice appear in supporting
17 * documentation, and that the name of Carnegie Mellon University not be used
18 * in advertising or publicity pertaining to distribution of the software
19 * without specific, written prior permission.
20 *
21 * CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
22 * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
23 * IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
24 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
25 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
26 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
27 * THIS SOFTWARE.
28 */
29
30 /*
31 * Generalized hash table ADT
32 *
33 * Provides multiple, dynamically-allocated, variable-sized hash tables on
34 * various data and keys.
35 *
36 * This package attempts to follow some of the coding conventions suggested
37 * by Bob Sidebotham and the AFS Clean Code Committee of the
38 * Information Technology Center at Carnegie Mellon.
39 *
40 * Additions for per bucket locking, and configurable dynamic free of
41 * unused entries.
42 */
43
44 #include <stdlib.h>
45 #include <string.h>
46 #include <sys/types.h>
47 #include <sys/param.h>
48 #include <sys/sysmacros.h>
49 #include <stdarg.h>
50 #include <stddef.h>
51 #include <assert.h>
52 #include <synch.h>
53 #include "dhcpd.h"
54 #include "hash.h"
55
56 /*
57 * Hash table size calculation routine.
58 *
59 * Estimate the size of a hash table based on the expected number of
60 * entries, up to a maximum of HASHTABLESIZE.
61 */
62 static unsigned
63 hashi_Hsize(unsigned hint)
64 {
65 unsigned f;
66
67 if (hint == 0) /* Default size. */
68 hint = HASHTABLESIZE;
69 else if (hint < 16) /* Minimal size. */
70 hint = 16;
71
72 hint /= 4;
73 for (f = 2; f * f <= hint; f++) { /* Find next largest prime. */
74 if (hint % f == 0) {
75 f = 1;
76 hint++;
77 }
78 }
79 return (MIN(HASHTABLESIZE, hint));
80 }
81
82 /*
83 * Frees an entire linked list of bucket members (used in the
84 * open hashing scheme). Does nothing if the passed pointer is NULL.
85 *
86 * Returns B_FALSE and members which could not be freed in bucketptr, when
87 * force variable is set to B_FALSE, and free_data routine indicates
88 * free did not occur.
89 */
90 static boolean_t
91 hashi_FreeMember(hash_member **bucketptr, boolean_t (*free_data)(),
92 boolean_t force)
93 {
94 hash_member *prev, *next, *unfree = NULL;
95 boolean_t ret = B_TRUE;
96
97 if (bucketptr) {
98 for (prev = *bucketptr; prev; prev = next) {
99 next = prev->next;
100 prev->next = NULL;
101 if (free_data != NULL) {
102 if ((*free_data)(prev->data, force) ==
103 B_FALSE) {
104 ret = B_FALSE;
105 prev->next = unfree;
106 unfree = prev;
107 } else {
108 free(prev);
109 }
110 } else
111 free(prev);
112 }
113 *bucketptr = unfree;
114 }
115 return (ret);
116 }
117
118 /*
119 * Dynamic free initialization.
120 */
121 static void
122 hashi_Dinit(hash_tbl *hashtable, hash_member *memberptr)
123 {
124 (void) mutex_init(&memberptr->h_mtx, USYNC_THREAD, NULL);
125 memberptr->h_time = time(NULL) + hashtable->dfree_time;
126 memberptr->h_count = 1;
127 }
128
129 /*
130 * Dynamic free reference count increment.
131 */
132 static void
133 hashi_Dhold(hash_member *memberptr)
134 {
135 (void) mutex_lock(&memberptr->h_mtx);
136 memberptr->h_count++;
137 (void) mutex_unlock(&memberptr->h_mtx);
138 }
139
140 /*
141 * Dynamic free expired data. Return NULL if memberptr is successfully
142 * dynamically freed, otherwise return memberptr.
143 */
144 static hash_member *
145 hashi_Dfree(hash_member *memberptr, boolean_t (*free_data)())
146 {
147 hash_member *next;
148
149 next = memberptr->next;
150 memberptr->next = NULL;
151 if (hashi_FreeMember(&memberptr, free_data, B_FALSE) == B_TRUE)
152 memberptr = NULL;
153 else
154 memberptr->next = next;
155 return (memberptr);
156 }
157
158 /*
159 * Hash table initialization routine.
160 *
161 * This routine creates and intializes a hash table of size "tablesize"
162 * entries. Successful calls return a pointer to the hash table (which must
163 * be passed to other hash routines to identify the hash table). Failed
164 * calls return NULL.
165 */
166 hash_tbl *
167 hash_Init(unsigned tablesize, boolean_t (*dfree_data)(), time_t dtime,
168 boolean_t lck)
169 {
170 hash_tbl *hashtblptr;
171 unsigned totalsize;
172 unsigned i;
173
174 tablesize = hashi_Hsize(tablesize);
175
176 totalsize = sizeof (hash_tbl) + (sizeof (hash_bucket) *
177 (tablesize - 1));
178
179 hashtblptr = (hash_tbl *)smalloc(totalsize);
180
181 hashtblptr->size = tablesize; /* Success! */
182 hashtblptr->bucketnum = 0;
183 hashtblptr->dfree_data = dfree_data;
184 hashtblptr->dfree_lck = lck;
185 hashtblptr->dfree_time = dtime;
186 hashtblptr->table = &hashtblptr->data[0];
187 for (i = 0; i < tablesize; i++) {
188 hashtblptr->table[i].table = hashtblptr;
189 if (lck == B_TRUE) {
190 (void) rwlock_init(&(hashtblptr->table[i].rwlock),
191 USYNC_THREAD, NULL);
192 }
193 }
194
195 return (hashtblptr); /* NULL if failure */
196 }
197
198 /*
199 * Generic hash function to calculate a hash code from the given string.
200 *
201 * For each byte of the string, this function left-shifts the value in an
202 * accumulator and then adds the byte into the accumulator. The contents of
203 * the accumulator is returned after the entire string has been processed.
204 * It is assumed that this result will be used as the "hashcode" parameter in
205 * calls to other functions in this package. These functions automatically
206 * adjust the hashcode for the size of each hashtable.
207 *
208 * This algorithm probably works best when the hash table size is a prime
209 * number.
210 *
211 * Hopefully, this function is better than the previous one which returned
212 * the sum of the squares of all the bytes. I'm still open to other
213 * suggestions for a default hash function. The programmer is more than
214 * welcome to supply his/her own hash function as that is one of the design
215 * features of this package.
216 */
217 static unsigned
218 hashi_HashFunction(unsigned char *string, unsigned len)
219 {
220 unsigned accum;
221
222 /*
223 * Special case: allow hash_Delete() to iterate over buckets.
224 */
225 if (string == NULL)
226 return (len);
227
228 for (accum = 0; len != 0; len--) {
229 accum <<= 1;
230 accum += (unsigned)(*string++ & 0xFF);
231 }
232 return (accum);
233 }
234
235 /*
236 * This routine re-initializes the hash table. It frees all the allocated
237 * memory and resets all bucket pointers to NULL. For the macro hash
238 * table, the table will be reused. Other tables (with bucket locks)
239 * will be destroyed.
240 */
241 void
242 hash_Reset(hash_tbl *hashtable, boolean_t (*free_data)())
243 {
244 hash_bucket *bucketptr;
245 unsigned i;
246
247 bucketptr = &((hashtable->table)[0]);
248 for (i = 0; i < hashtable->size; i++) {
249 if (hashtable->dfree_lck == B_TRUE)
250 (void) rw_wrlock(&bucketptr->rwlock);
251 /*
252 * Unequivocally free member, using the force parameter.
253 */
254 (void) hashi_FreeMember(&bucketptr->next, free_data, B_TRUE);
255 bucketptr->next = NULL;
256 if (hashtable->dfree_lck == B_TRUE) {
257 (void) rw_unlock(&bucketptr->rwlock);
258 (void) rwlock_destroy(&(bucketptr->rwlock));
259 }
260 bucketptr++;
261 }
262 hashtable->bucketnum = 0;
263 }
264
265 /*
266 * Returns B_TRUE if at least one entry for the given key exists; B_FALSE
267 * otherwise. Dynamically free expired data as searched.
268 */
269 static int
270 hashi_Exists(hash_bucket *bucketptr, int (*compare)(), hash_datum *key,
271 boolean_t (*free_data)(), hash_member **prev)
272 {
273 hash_member *prevptr = (hash_member *)bucketptr;
274 hash_member *memberptr = bucketptr->next;
275 hash_tbl *hashtable = bucketptr->table;
276 hash_member *next;
277 boolean_t ret = B_FALSE;
278 time_t now = time(NULL);
279
280 while (memberptr != NULL) {
281 /*
282 * Dynamically free expired data.
283 */
284 if (free_data != NULL && hashtable->dfree_data != NULL &&
285 memberptr->h_time < now) {
286 next = memberptr->next;
287 if ((memberptr = hashi_Dfree(memberptr, free_data)) ==
288 NULL) {
289 prevptr->next = memberptr = next;
290 continue;
291 }
292 }
293
294 /*
295 * Entry exists, or we are randomly selecting any
296 * element (compare function is NULL).
297 */
298 if (compare == NULL || (*compare)(key, memberptr->data)) {
299 ret = B_TRUE;
300 break;
301 } else
302 prevptr = memberptr;
303 memberptr = memberptr->next;
304 }
305
306 if (prev != NULL)
307 *prev = prevptr;
308 return (ret);
309 }
310
311 /*
312 * Returns number of Dynamically freed expired entries.
313 */
314 static int
315 hashi_Expire(hash_bucket *bucketptr, boolean_t (*free_data)())
316 {
317 hash_member *prevptr = (hash_member *)bucketptr;
318 hash_member *memberptr = bucketptr->next;
319 hash_tbl *hashtable = bucketptr->table;
320 hash_member *next;
321 int rcount = 0;
322 time_t now = time(NULL);
323
324 while (memberptr) {
325 /*
326 * Dynamically free expired data.
327 */
328 if (free_data != NULL && hashtable->dfree_data != NULL &&
329 memberptr->h_time < now) {
330 next = memberptr->next;
331 if ((memberptr = hashi_Dfree(memberptr, free_data)) ==
332 NULL) {
333 rcount++;
334 prevptr->next = memberptr = next;
335 continue;
336 }
337 }
338 prevptr = memberptr;
339 memberptr = memberptr->next;
340 }
341 return (rcount);
342 }
343
344 /*
345 * Insert the data item "element" into the hash table using "hashcode"
346 * to determine the bucket number, and "compare" and "key" to determine
347 * its uniqueness.
348 *
349 * If the insertion is successful the element is returned. If a matching entry
350 * already exists in the given bucket of the hash table, then NULL is returned,
351 * signifying that the entry is already in the table. This happens when some
352 * other thread has already inserted the entry.
353 */
354 void *
355 hash_Insert(hash_tbl *hashtable, void *hashdata, unsigned hashlen,
356 int (*compare)(), hash_datum *key, hash_datum *element)
357 {
358 hash_member *temp = NULL;
359 hash_bucket *bucketptr;
360 hash_member *prev = NULL;
361 unsigned hashcode = hashi_HashFunction(hashdata, hashlen);
362
363 bucketptr = &((hashtable->table)[hashcode % hashtable->size]);
364 if (hashtable->dfree_lck)
365 (void) rw_wrlock(&bucketptr->rwlock);
366
367 if (hashi_Exists(bucketptr, compare, key, hashtable->dfree_data,
368 &prev)) {
369 /* Some other thread got there first, so just return */
370 if (hashtable->dfree_lck)
371 (void) rw_unlock(&bucketptr->rwlock);
372 return (NULL);
373 }
374
375 temp = (hash_member *)smalloc(sizeof (hash_member));
376
377 prev->next = temp;
378 temp->data = element;
379 temp->next = NULL;
380
381 /*
382 * Dynamic free initialization.
383 */
384 if (hashtable->dfree_data != NULL)
385 hashi_Dinit(hashtable, temp);
386
387 if (hashtable->dfree_lck)
388 (void) rw_unlock(&bucketptr->rwlock);
389
390 return ((void *)temp);
391 }
392
393 /*
394 * Release the reference count on an item. Performance: if item is to be
395 * deleted, mark for future dynamic free.
396 */
397 void
398 hash_Rele(void *hashp, boolean_t delete)
399 {
400 hash_member *memberptr = (hash_member *)hashp;
401
402 (void) mutex_lock(&memberptr->h_mtx);
403 memberptr->h_count--;
404 assert(memberptr->h_count >= 0);
405 if (delete == B_TRUE)
406 memberptr->h_time = 0;
407 (void) mutex_unlock(&memberptr->h_mtx);
408 }
409
410 /*
411 * Report the reference count on an item.
412 */
413 int
414 hash_Refcount(void *hashp)
415 {
416 hash_member *memberptr = (hash_member *)hashp;
417 int ret;
418
419 (void) mutex_lock(&memberptr->h_mtx);
420 ret = memberptr->h_count;
421 (void) mutex_unlock(&memberptr->h_mtx);
422 return (ret);
423 }
424
425 /*
426 * Report the dynamic free time on an item.
427 */
428 int
429 hash_Htime(void *hashp)
430 {
431 hash_member *memberptr = (hash_member *)hashp;
432 int ret;
433
434 (void) mutex_lock(&memberptr->h_mtx);
435 ret = memberptr->h_time;
436 (void) mutex_unlock(&memberptr->h_mtx);
437 return (ret);
438 }
439
440 /*
441 * Increase the dynamic free time on an item.
442 */
443 void
444 hash_Age(void *hashp)
445 {
446 hash_member *memberptr = (hash_member *)hashp;
447
448 (void) mutex_lock(&memberptr->h_mtx);
449 memberptr->h_time++;
450 (void) mutex_unlock(&memberptr->h_mtx);
451 }
452
453 /*
454 * Set the dynamic free time on an item.
455 */
456 void
457 hash_Dtime(void *hashp, time_t tm)
458 {
459 hash_member *memberptr = (hash_member *)hashp;
460
461 (void) mutex_lock(&memberptr->h_mtx);
462 memberptr->h_time = tm;
463 (void) mutex_unlock(&memberptr->h_mtx);
464 }
465
466 /*
467 * Delete a data item from the hash table using "hashcode"
468 * to determine the bucket number, and "compare" and "key" to determine
469 * its uniqueness.
470 *
471 * If the deletion is successful 0 is returned. If a matching entry
472 * does not exist in the given bucket of the hash table, or some other error
473 * occurs, -1 is returned and the insertion is not done.
474 */
475 boolean_t
476 hash_Delete(hash_tbl *hashtable, void *hashdata, unsigned hashlen,
477 int (*compare)(), hash_datum *key, boolean_t (*free_data)())
478 {
479 hash_member *prev = NULL;
480 hash_member *temp;
481 hash_bucket *bucketptr;
482 unsigned hashcode = hashi_HashFunction(hashdata, hashlen);
483
484 bucketptr = &((hashtable->table)[hashcode % hashtable->size]);
485 if (hashtable->dfree_lck == B_TRUE)
486 (void) rw_wrlock(&bucketptr->rwlock);
487
488 if (hashi_Exists(bucketptr, compare, key, free_data, &prev) ==
489 B_FALSE || prev == NULL) {
490 if (hashtable->dfree_lck == B_TRUE)
491 (void) rw_unlock(&bucketptr->rwlock);
492 return (B_FALSE); /* Entry does not exist */
493 }
494
495 temp = prev->next;
496 if (temp) {
497 prev->next = temp->next;
498 temp->next = NULL;
499 (void) hashi_FreeMember(&temp, free_data, B_TRUE);
500 } else
501 prev->next = NULL;
502 if (hashtable->dfree_lck == B_TRUE)
503 (void) rw_unlock(&bucketptr->rwlock);
504 return (B_TRUE);
505 }
506
507 /*
508 * Locate and return the data entry associated with the given key.
509 *
510 * If the data entry is found, a pointer to it is returned. Otherwise,
511 * NULL is returned.
512 */
513 hash_datum *
514 hash_Lookup(hash_tbl *hashtable, void *hashdata, unsigned hashlen,
515 int (*compare)(), hash_datum *key, boolean_t hold)
516 {
517 hash_datum *ret = NULL;
518 hash_bucket *bucketptr;
519 hash_member *prev = NULL;
520 unsigned hashcode = hashi_HashFunction(hashdata, hashlen);
521
522 bucketptr = &((hashtable->table)[hashcode % hashtable->size]);
523 if (hashtable->dfree_lck == B_TRUE)
524 (void) rw_wrlock(&bucketptr->rwlock);
525
526 if (hashi_Exists(bucketptr, compare, key, hashtable->dfree_data,
527 &prev) == B_TRUE) {
528 /*
529 * Dynamic free increment reference.
530 */
531 if (hold)
532 hashi_Dhold(prev->next);
533 ret = prev->next->data;
534
535 }
536 if (hashtable->dfree_lck == B_TRUE)
537 (void) rw_unlock(&bucketptr->rwlock);
538 return (ret);
539 }
540
541 /*
542 * Reap expired data items, or a random data item from the hash table.
543 */
544 void
545 hash_Reap(hash_tbl *hashtable, boolean_t (*free_data)())
546 {
547 hash_bucket *bucketptr;
548 int rcount;
549 unsigned i;
550
551 bucketptr = &((hashtable->table)[0]);
552 rcount = 0;
553
554 /*
555 * Walk the buckets, reaping expired clients.
556 */
557 for (i = 0; i < hashtable->size; i++) {
558 if (hashtable->dfree_lck == B_TRUE)
559 (void) rw_wrlock(&bucketptr->rwlock);
560 rcount += hashi_Expire(bucketptr, hashtable->dfree_data);
561 if (hashtable->dfree_lck == B_TRUE)
562 (void) rw_unlock(&bucketptr->rwlock);
563 bucketptr++;
564 }
565
566 /*
567 * Nothing to be reaped, delete a random element. Note that
568 * the unhash_data routine will wait for current references
569 * before deletion.
570 */
571 if (rcount == 0) {
572 for (i = 0; i < hashtable->size; i++) {
573 if (hash_Delete(hashtable, NULL, i, NULL, NULL,
574 free_data) == B_TRUE) {
575 break;
576 }
577 }
578 }
579 }