ISC DHCP 4.4.3-P1
A reference DHCPv4 and DHCPv6 implementation
 
Loading...
Searching...
No Matches
hash.c
Go to the documentation of this file.
1/* hash.c
2
3 Routines for manipulating hash tables... */
4
5/*
6 * Copyright (C) 2004-2022 Internet Systems Consortium, Inc. ("ISC")
7 * Copyright (c) 1995-2003 by Internet Software Consortium
8 *
9 * This Source Code Form is subject to the terms of the Mozilla Public
10 * License, v. 2.0. If a copy of the MPL was not distributed with this
11 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
16 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
18 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
19 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 *
21 * Internet Systems Consortium, Inc.
22 * PO Box 360
23 * Newmarket, NH 03857 USA
24 * <info@isc.org>
25 * https://www.isc.org/
26 *
27 */
28
29#include "dhcpd.h"
30
31#include <omapip/omapip_p.h>
32#include <limits.h>
33#include <ctype.h>
34
35static unsigned
36find_length(const void *key,
37 unsigned (*do_hash)(const void *, unsigned, unsigned))
38{
39 if (do_hash == do_case_hash || do_hash == do_string_hash)
40 return strlen((const char *)key);
41 if (do_hash == do_number_hash)
42 return sizeof(unsigned);
43 if (do_hash == do_ip4_hash)
44 return 4;
45
46 log_debug("Unexpected hash function at %s:%d.", MDL);
47 /*
48 * If we get a hash function we don't specifically expect
49 * return a length of 0, this covers the case where a client
50 * id has a length of 0.
51 */
52 return 0;
53}
54
55int new_hash_table (tp, count, file, line)
56 struct hash_table **tp;
57 unsigned count;
58 const char *file;
59 int line;
60{
61 struct hash_table *rval;
62 unsigned extra;
63
64 if (!tp) {
65 log_error ("%s(%d): new_hash_table called with null pointer.",
66 file, line);
67#if defined (POINTER_DEBUG)
68 abort ();
69#endif
70 return 0;
71 }
72 if (*tp) {
73 log_error ("%s(%d): non-null target for new_hash_table.",
74 file, line);
75#if defined (POINTER_DEBUG)
76 abort ();
77#endif
78 }
79
80 /* There is one hash bucket in the structure. Allocate extra
81 * memory beyond the end of the structure to fulfill the requested
82 * count ("count - 1"). Do not let there be less than one.
83 */
84 if (count <= 1)
85 extra = 0;
86 else
87 extra = count - 1;
88
89 rval = dmalloc(sizeof(struct hash_table) +
90 (extra * sizeof(struct hash_bucket *)), file, line);
91 if (!rval)
92 return 0;
93 rval -> hash_count = count;
94 *tp = rval;
95 return 1;
96}
97
99 struct hash_table **tp;
100 const char *file;
101 int line;
102{
103 struct hash_table *ptr = *tp;
104
105#if defined (DEBUG_MEMORY_LEAKAGE) || \
106 defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
107 int i;
108 struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0;
109
110 for (i = 0; ptr != NULL && i < ptr -> hash_count; i++) {
111 for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
112 hbn = hbc -> next;
113 if (ptr -> dereferencer && hbc -> value)
114 (*ptr -> dereferencer) (&hbc -> value, MDL);
115 }
116 for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
117 hbn = hbc -> next;
118 free_hash_bucket (hbc, MDL);
119 }
120 ptr -> buckets [i] = (struct hash_bucket *)0;
121 }
122#endif
123
124 dfree((void *)ptr, MDL);
125 *tp = (struct hash_table *)0;
126}
127
129
130#if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
131struct hash_bucket *hash_bucket_hunks;
132
134{
135 struct hash_bucket *c, *n, **p;
136
137 /* Account for all the hash buckets on the free list. */
139 for (c = free_hash_buckets; c; c = c -> next) {
140 for (n = hash_bucket_hunks; n; n = n -> next) {
141 if (c > n && c < n + 127) {
142 *p = c -> next;
143 n -> len++;
144 break;
145 }
146 }
147 /* If we didn't delete the hash bucket from the free list,
148 advance the pointer. */
149 if (!n)
150 p = &c -> next;
151 }
152
153 for (c = hash_bucket_hunks; c; c = n) {
154 n = c -> next;
155 if (c -> len != 126) {
156 log_info ("hashbucket %lx hash_buckets %d free %u",
157 (unsigned long)c, 127, c -> len);
158 }
159 dfree (c, MDL);
160 }
161}
162#endif
163
165 const char *file;
166 int line;
167{
168 struct hash_bucket *rval;
169 int i = 0;
170 if (!free_hash_buckets) {
171 rval = dmalloc (127 * sizeof (struct hash_bucket),
172 file, line);
173 if (!rval)
174 return rval;
175# if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
176 rval -> next = hash_bucket_hunks;
177 hash_bucket_hunks = rval;
178 hash_bucket_hunks -> len = 0;
179 i++;
180 rval++;
181#endif
182 for (; i < 127; i++) {
183 rval -> next = free_hash_buckets;
184 free_hash_buckets = rval;
185 rval++;
186 }
187 }
188 rval = free_hash_buckets;
189 free_hash_buckets = rval -> next;
190 return rval;
191}
192
194 struct hash_bucket *ptr;
195 const char *file;
196 int line;
197{
198#if defined (DEBUG_MALLOC_POOL)
199 struct hash_bucket *hp;
200
201 for (hp = free_hash_buckets; hp; hp = hp -> next) {
202 if (hp == ptr) {
203 log_error ("hash bucket freed twice!");
204 abort ();
205 }
206 }
207#endif
208 ptr -> next = free_hash_buckets;
209 free_hash_buckets = ptr;
210}
211
212int new_hash(struct hash_table **rp,
213 hash_reference referencer,
214 hash_dereference dereferencer,
215 unsigned hsize,
216 unsigned (*hasher)(const void *, unsigned, unsigned),
217 const char *file, int line)
218{
219 if (hsize == 0)
220 hsize = DEFAULT_HASH_SIZE;
221
222 if (!new_hash_table (rp, hsize, file, line))
223 return 0;
224
225 memset ((*rp)->buckets, 0, hsize * sizeof(struct hash_bucket *));
226
227 (*rp)->referencer = referencer;
228 (*rp)->dereferencer = dereferencer;
229 (*rp)->do_hash = hasher;
230
231 if (hasher == do_case_hash)
232 (*rp)->cmp = casecmp;
233 else
234 (*rp)->cmp = memcmp;
235
236 return 1;
237}
238
239unsigned
240do_case_hash(const void *name, unsigned len, unsigned size)
241{
242 register unsigned accum = 0;
243 register const unsigned char *s = name;
244 int i = len;
245 register unsigned c;
246
247 while (i--) {
248 /* Make the hash case-insensitive. */
249 c = *s++;
250 if (isascii(c))
251 c = tolower(c);
252
253 /* Add the character in... */
254 accum = (accum << 1) + c;
255
256 /* Add carry back in... */
257 while (accum > 65535) {
258 accum = (accum & 65535) + (accum >> 16);
259 }
260
261 }
262 return accum % size;
263}
264
265unsigned
266do_string_hash(const void *name, unsigned len, unsigned size)
267{
268 register unsigned accum = 0;
269 register const unsigned char *s = (const unsigned char *)name;
270 int i = len;
271
272 while (i--) {
273 /* Add the character in... */
274 accum = (accum << 1) + *s++;
275
276 /* Add carry back in... */
277 while (accum > 65535) {
278 accum = (accum & 65535) + (accum >> 16);
279 }
280 }
281 return accum % size;
282}
283
284/* Client identifiers are generally 32-bits of ordinary
285 * non-randomness followed by 24-bits of unordinary randomness.
286 * So, end-align in 24-bit chunks, and xor any preceding data
287 * just to mix it up a little.
288 */
289unsigned
290do_id_hash(const void *name, unsigned len, unsigned size)
291{
292 register unsigned accum = 0;
293 register const unsigned char *s = (const unsigned char *)name;
294 const unsigned char *end = s + len;
295
296 if (len == 0)
297 return 0;
298
299 /*
300 * The switch handles our starting conditions, then we hash the
301 * remaining bytes in groups of 3
302 */
303
304 switch (len % 3) {
305 case 0:
306 break;
307 case 2:
308 accum ^= *s++ << 8;
309 case 1:
310 accum ^= *s++;
311 break;
312 }
313
314 while (s < end) {
315 accum ^= *s++ << 16;
316 accum ^= *s++ << 8;
317 accum ^= *s++;
318 }
319
320 return accum % size;
321}
322
323unsigned
324do_number_hash(const void *key, unsigned len, unsigned size)
325{
326 register unsigned number = *((const unsigned *)key);
327
328 return number % size;
329}
330
331unsigned
332do_ip4_hash(const void *key, unsigned len, unsigned size)
333{
334 u_int32_t number;
335
336 memcpy(&number, key, 4);
337
338 number = ntohl(number);
339
340 return number % size;
341}
342
343unsigned char *
345{
346 static unsigned char retbuf[sizeof("Contents/Size (%): "
347 "2147483647/2147483647 "
348 "(2147483647%). "
349 "Min/max: 2147483647/2147483647")];
350 unsigned curlen, pct, contents=0, minlen=UINT_MAX, maxlen=0;
351 unsigned i;
352 struct hash_bucket *bp;
353
354 if (table == NULL)
355 return (unsigned char *) "No table.";
356
357 if (table->hash_count == 0)
358 return (unsigned char *) "Invalid hash table.";
359
360 for (i = 0 ; i < table->hash_count ; i++) {
361 curlen = 0;
362
363 bp = table->buckets[i];
364 while (bp != NULL) {
365 curlen++;
366 bp = bp->next;
367 }
368
369 if (curlen < minlen)
370 minlen = curlen;
371 if (curlen > maxlen)
372 maxlen = curlen;
373
374 contents += curlen;
375 }
376
377 if (contents >= (UINT_MAX / 100))
378 pct = contents / ((table->hash_count / 100) + 1);
379 else
380 pct = (contents * 100) / table->hash_count;
381
382 if (contents > 2147483647 ||
383 table->hash_count > 2147483647 ||
384 pct > 2147483647 ||
385 minlen > 2147483647 ||
386 maxlen > 2147483647)
387 return (unsigned char *) "Report out of range for display.";
388
389 sprintf((char *)retbuf,
390 "Contents/Size (%%): %u/%u (%u%%). Min/max: %u/%u",
391 contents, table->hash_count, pct, minlen, maxlen);
392
393 return retbuf;
394}
395
396void add_hash (table, key, len, pointer, file, line)
397 struct hash_table *table;
398 unsigned len;
399 const void *key;
400 hashed_object_t *pointer;
401 const char *file;
402 int line;
403{
404 int hashno;
405 struct hash_bucket *bp;
406 void *foo;
407
408 if (!table)
409 return;
410
411 if (!len)
412 len = find_length(key, table->do_hash);
413
414 hashno = (*table->do_hash)(key, len, table->hash_count);
415 bp = new_hash_bucket (file, line);
416
417 if (!bp) {
418 log_error ("Can't add entry to hash table: no memory.");
419 return;
420 }
421 bp -> name = key;
422 if (table -> referencer) {
423 foo = &bp -> value;
424 (*(table -> referencer)) (foo, pointer, file, line);
425 } else
426 bp -> value = pointer;
427 bp -> next = table -> buckets [hashno];
428 bp -> len = len;
429 table -> buckets [hashno] = bp;
430}
431
432void delete_hash_entry (table, key, len, file, line)
433 struct hash_table *table;
434 unsigned len;
435 const void *key;
436 const char *file;
437 int line;
438{
439 int hashno;
440 struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
441 void *foo;
442
443 if (!table)
444 return;
445
446 if (!len)
447 len = find_length(key, table->do_hash);
448
449 hashno = (*table->do_hash)(key, len, table->hash_count);
450
451 /* Go through the list looking for an entry that matches;
452 if we find it, delete it. */
453 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
454 if ((!bp -> len &&
455 !strcmp ((const char *)bp->name, key)) ||
456 (bp -> len == len &&
457 !(table -> cmp)(bp->name, key, len))) {
458 if (pbp) {
459 pbp -> next = bp -> next;
460 } else {
461 table -> buckets [hashno] = bp -> next;
462 }
463 if (bp -> value && table -> dereferencer) {
464 foo = &bp -> value;
465 (*(table -> dereferencer)) (foo, file, line);
466 }
468 break;
469 }
470 pbp = bp; /* jwg, 9/6/96 - nice catch! */
471 }
472}
473
474int hash_lookup (vp, table, key, len, file, line)
475 hashed_object_t **vp;
476 struct hash_table *table;
477 const void *key;
478 unsigned len;
479 const char *file;
480 int line;
481{
482 int hashno;
483 struct hash_bucket *bp;
484
485 if (!table)
486 return 0;
487 if (!len)
488 len = find_length(key, table->do_hash);
489
490 if (*vp != NULL) {
491 log_fatal("Internal inconsistency: storage value has not been "
492 "initialized to zero (from %s:%d).", file, line);
493 }
494
495 hashno = (*table->do_hash)(key, len, table->hash_count);
496
497 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
498 if (len == bp -> len
499 && !(*table->cmp)(bp->name, key, len)) {
500 if (table -> referencer)
501 (*table -> referencer) (vp, bp -> value,
502 file, line);
503 else
504 *vp = bp -> value;
505 return 1;
506 }
507 }
508 return 0;
509}
510
512{
513 int i;
514 struct hash_bucket *bp, *next;
515 int count = 0;
516
517 if (!table)
518 return 0;
519
520 for (i = 0; i < table -> hash_count; i++) {
521 bp = table -> buckets [i];
522 while (bp) {
523 next = bp -> next;
524 if ((*func)(bp->name, bp->len, bp->value)
525 != ISC_R_SUCCESS)
526 return count;
527 bp = next;
528 count++;
529 }
530 }
531 return count;
532}
533
534int casecmp (const void *v1, const void *v2, size_t len)
535{
536 size_t i;
537 const unsigned char *s = v1;
538 const unsigned char *t = v2;
539
540 for (i = 0; i < len; i++)
541 {
542 int c1, c2;
543 if (isascii(s[i]))
544 c1 = tolower(s[i]);
545 else
546 c1 = s[i];
547
548 if (isascii(t[i]))
549 c2 = tolower(t[i]);
550 else
551 c2 = t[i];
552
553 if (c1 < c2)
554 return -1;
555 if (c1 > c2)
556 return 1;
557 }
558 return 0;
559}
const char int line
Definition dhcpd.h:3802
const char * file
Definition dhcpd.h:3802
int new_hash(struct hash_table **rp, hash_reference referencer, hash_dereference dereferencer, unsigned hsize, unsigned(*hasher)(const void *, unsigned, unsigned), const char *file, int line)
Definition hash.c:212
unsigned do_case_hash(const void *name, unsigned len, unsigned size)
Definition hash.c:240
unsigned do_ip4_hash(const void *key, unsigned len, unsigned size)
Definition hash.c:332
void delete_hash_entry(struct hash_table *table, const void *key, unsigned len, const char *file, int line)
Definition hash.c:432
unsigned do_id_hash(const void *name, unsigned len, unsigned size)
Definition hash.c:290
int casecmp(const void *v1, const void *v2, size_t len)
Definition hash.c:534
void add_hash(struct hash_table *table, const void *key, unsigned len, hashed_object_t *pointer, const char *file, int line)
Definition hash.c:396
struct hash_bucket * new_hash_bucket(char *file, int line) const
Definition hash.c:164
unsigned do_number_hash(const void *key, unsigned len, unsigned size)
Definition hash.c:324
int hash_foreach(struct hash_table *table, hash_foreach_func func)
Definition hash.c:511
void free_hash_bucket(struct hash_bucket *ptr, const char *file, int line)
Definition hash.c:193
struct hash_bucket * free_hash_buckets
Definition hash.c:128
int new_hash_table(struct hash_table **tp, unsigned count, const char *file, int line)
Definition hash.c:55
int hash_lookup(hashed_object_t **vp, struct hash_table *table, const void *key, unsigned len, const char *file, int line)
Definition hash.c:474
void free_hash_table(struct hash_table **tp, const char *file, int line)
Definition hash.c:98
unsigned do_string_hash(const void *name, unsigned len, unsigned size)
Definition hash.c:266
unsigned char * hash_report(struct hash_table *table)
Definition hash.c:344
int casecmp(const void *s, const void *t, size_t len)
Definition hash.c:534
unsigned do_case_hash(const void *, unsigned, unsigned)
Definition hash.c:240
void relinquish_hash_bucket_hunks(void)
int(* hash_dereference)(hashed_object_t **, const char *, int)
Definition hash.h:48
isc_result_t(* hash_foreach_func)(const void *, unsigned, void *)
Definition hash.h:45
int new_hash_table(struct hash_table **, unsigned, const char *, int)
Definition hash.c:55
int(* hash_reference)(hashed_object_t **, hashed_object_t *, const char *, int)
Definition hash.h:46
unsigned do_string_hash(const void *, unsigned, unsigned)
Definition hash.c:266
unsigned do_ip4_hash(const void *, unsigned, unsigned)
Definition hash.c:332
unsigned do_number_hash(const void *, unsigned, unsigned)
Definition hash.c:324
#define DEFAULT_HASH_SIZE
Definition hash.h:33
#define ISC_R_SUCCESS
#define MDL
Definition omapip.h:567
void * dmalloc(size_t, const char *, int)
Definition alloc.c:57
void dfree(void *, const char *, int)
Definition alloc.c:145
int log_error(const char *,...) __attribute__((__format__(__printf__
int int int log_debug(const char *,...) __attribute__((__format__(__printf__
void log_fatal(const char *,...) __attribute__((__format__(__printf__
int int log_info(const char *,...) __attribute__((__format__(__printf__
unsigned len
Definition hash.h:53
struct hash_bucket * next
Definition hash.h:51
const unsigned char * name
Definition hash.h:52
hashed_object_t * value
Definition hash.h:54
unsigned(* do_hash)(const void *, unsigned, unsigned)
Definition hash.h:64
hash_comparator_t cmp
Definition hash.h:63
struct hash_bucket * buckets[1]
Definition hash.h:67
unsigned hash_count
Definition hash.h:60
Definition data.h:205