1 /* hash.c
2
3 Routines for manipulating hash tables... */
4
5 /*
6 * Copyright (c) 2004-2017 by 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 * 950 Charter Street
23 * Redwood City, CA 94063
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
35 static unsigned
find_length(const void * key,unsigned (* do_hash)(const void *,unsigned,unsigned))36 find_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
new_hash_table(tp,count,file,line)55 int 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
free_hash_table(tp,file,line)98 void free_hash_table (tp, file, line)
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
128 struct hash_bucket *free_hash_buckets;
129
130 #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
131 struct hash_bucket *hash_bucket_hunks;
132
relinquish_hash_bucket_hunks()133 void relinquish_hash_bucket_hunks ()
134 {
135 struct hash_bucket *c, *n, **p;
136
137 /* Account for all the hash buckets on the free list. */
138 p = &free_hash_buckets;
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
new_hash_bucket(file,line)164 struct hash_bucket *new_hash_bucket (file, line)
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
free_hash_bucket(ptr,file,line)193 void free_hash_bucket (ptr, file, line)
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
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)212 int 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
239 unsigned
do_case_hash(const void * name,unsigned len,unsigned size)240 do_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
265 unsigned
do_string_hash(const void * name,unsigned len,unsigned size)266 do_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 */
289 unsigned
do_id_hash(const void * name,unsigned len,unsigned size)290 do_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
323 unsigned
do_number_hash(const void * key,unsigned len,unsigned size)324 do_number_hash(const void *key, unsigned len, unsigned size)
325 {
326 register unsigned number = *((const unsigned *)key);
327
328 return number % size;
329 }
330
331 unsigned
do_ip4_hash(const void * key,unsigned len,unsigned size)332 do_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
343 unsigned char *
hash_report(struct hash_table * table)344 hash_report(struct hash_table *table)
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
add_hash(table,key,len,pointer,file,line)396 void 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
delete_hash_entry(table,key,len,file,line)432 void 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 }
467 free_hash_bucket (bp, file, line);
468 break;
469 }
470 pbp = bp; /* jwg, 9/6/96 - nice catch! */
471 }
472 }
473
hash_lookup(vp,table,key,len,file,line)474 int 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
hash_foreach(struct hash_table * table,hash_foreach_func func)511 int hash_foreach (struct hash_table *table, hash_foreach_func func)
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
casecmp(const void * v1,const void * v2,size_t len)534 int 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 }
560