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