]>
Commit | Line | Data |
---|---|---|
d7837182 TL |
1 | /* hash.c |
2 | ||
3 | Routines for manipulating hash tables... */ | |
4 | ||
5 | /* | |
49a7fb58 | 6 | * Copyright (C) 2004-2022 Internet Systems Consortium, Inc. ("ISC") |
98311e4b | 7 | * Copyright (c) 1995-2003 by Internet Software Consortium |
d7837182 | 8 | * |
7512d88b TM |
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/. | |
d7837182 | 12 | * |
98311e4b DH |
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. | |
d7837182 | 20 | * |
98311e4b | 21 | * Internet Systems Consortium, Inc. |
429a56d7 TM |
22 | * PO Box 360 |
23 | * Newmarket, NH 03857 USA | |
98311e4b | 24 | * <info@isc.org> |
2c85ac9b | 25 | * https://www.isc.org/ |
49733f31 | 26 | * |
d7837182 TL |
27 | */ |
28 | ||
fe5b0fdd DH |
29 | #include "dhcpd.h" |
30 | ||
c62871ba | 31 | #include <omapip/omapip_p.h> |
fe5b0fdd | 32 | #include <limits.h> |
7d9784f6 | 33 | #include <ctype.h> |
d7837182 | 34 | |
fe5b0fdd | 35 | static unsigned |
f7fdb216 DH |
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 | ||
1943bbf8 SR |
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; | |
f7fdb216 | 53 | } |
c62871ba | 54 | |
98311e4b DH |
55 | int new_hash_table (tp, count, file, line) |
56 | struct hash_table **tp; | |
f7fdb216 | 57 | unsigned count; |
c62871ba DN |
58 | const char *file; |
59 | int line; | |
60 | { | |
98311e4b | 61 | struct hash_table *rval; |
272ef1bc | 62 | unsigned extra; |
98311e4b DH |
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 | } | |
272ef1bc SK |
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); | |
98311e4b DH |
91 | if (!rval) |
92 | return 0; | |
c62871ba | 93 | rval -> hash_count = count; |
98311e4b DH |
94 | *tp = rval; |
95 | return 1; | |
c62871ba DN |
96 | } |
97 | ||
98311e4b DH |
98 | void free_hash_table (tp, file, line) |
99 | struct hash_table **tp; | |
c62871ba DN |
100 | const char *file; |
101 | int line; | |
102 | { | |
98311e4b | 103 | struct hash_table *ptr = *tp; |
d758ad8c TL |
104 | |
105 | #if defined (DEBUG_MEMORY_LEAKAGE) || \ | |
106 | defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT) | |
28868515 SK |
107 | int i; |
108 | struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0; | |
109 | ||
ce29e695 | 110 | for (i = 0; ptr != NULL && i < ptr -> hash_count; i++) { |
d758ad8c TL |
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 | ||
fe5b0fdd | 124 | dfree((void *)ptr, MDL); |
98311e4b | 125 | *tp = (struct hash_table *)0; |
c62871ba DN |
126 | } |
127 | ||
128 | struct hash_bucket *free_hash_buckets; | |
129 | ||
d758ad8c TL |
130 | #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT) |
131 | struct hash_bucket *hash_bucket_hunks; | |
132 | ||
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 | } | |
f6b8f48d | 152 | |
d758ad8c TL |
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 | ||
c62871ba DN |
164 | struct hash_bucket *new_hash_bucket (file, line) |
165 | const char *file; | |
166 | int line; | |
167 | { | |
168 | struct hash_bucket *rval; | |
d758ad8c | 169 | int i = 0; |
c62871ba DN |
170 | if (!free_hash_buckets) { |
171 | rval = dmalloc (127 * sizeof (struct hash_bucket), | |
172 | file, line); | |
173 | if (!rval) | |
174 | return rval; | |
d758ad8c TL |
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++) { | |
c62871ba DN |
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 | ||
193 | void free_hash_bucket (ptr, file, line) | |
194 | struct hash_bucket *ptr; | |
195 | const char *file; | |
196 | int line; | |
197 | { | |
d758ad8c | 198 | #if defined (DEBUG_MALLOC_POOL) |
28868515 SK |
199 | struct hash_bucket *hp; |
200 | ||
d758ad8c TL |
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 | |
c62871ba DN |
208 | ptr -> next = free_hash_buckets; |
209 | free_hash_buckets = ptr; | |
210 | } | |
089fb364 | 211 | |
f7fdb216 DH |
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) | |
d7837182 | 218 | { |
f7fdb216 DH |
219 | if (hsize == 0) |
220 | hsize = DEFAULT_HASH_SIZE; | |
221 | ||
222 | if (!new_hash_table (rp, hsize, file, line)) | |
98311e4b | 223 | return 0; |
f7fdb216 DH |
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 | ||
98311e4b | 236 | return 1; |
d7837182 TL |
237 | } |
238 | ||
f7fdb216 DH |
239 | unsigned |
240 | do_case_hash(const void *name, unsigned len, unsigned size) | |
d7837182 | 241 | { |
f7fdb216 DH |
242 | register unsigned accum = 0; |
243 | register const unsigned char *s = name; | |
d7837182 | 244 | int i = len; |
7d9784f6 TL |
245 | register unsigned c; |
246 | ||
247 | while (i--) { | |
248 | /* Make the hash case-insensitive. */ | |
249 | c = *s++; | |
f7fdb216 DH |
250 | if (isascii(c)) |
251 | c = tolower(c); | |
7d9784f6 TL |
252 | |
253 | /* Add the character in... */ | |
d5ef2946 TL |
254 | accum = (accum << 1) + c; |
255 | ||
7d9784f6 | 256 | /* Add carry back in... */ |
d5ef2946 TL |
257 | while (accum > 65535) { |
258 | accum = (accum & 65535) + (accum >> 16); | |
7d9784f6 | 259 | } |
f7fdb216 | 260 | |
7d9784f6 TL |
261 | } |
262 | return accum % size; | |
263 | } | |
264 | ||
f7fdb216 DH |
265 | unsigned |
266 | do_string_hash(const void *name, unsigned len, unsigned size) | |
7d9784f6 | 267 | { |
f7fdb216 | 268 | register unsigned accum = 0; |
7d9784f6 TL |
269 | register const unsigned char *s = (const unsigned char *)name; |
270 | int i = len; | |
271 | ||
34bef96b TL |
272 | while (i--) { |
273 | /* Add the character in... */ | |
d5ef2946 TL |
274 | accum = (accum << 1) + *s++; |
275 | ||
34bef96b | 276 | /* Add carry back in... */ |
d5ef2946 TL |
277 | while (accum > 65535) { |
278 | accum = (accum & 65535) + (accum >> 16); | |
d7837182 TL |
279 | } |
280 | } | |
281 | return accum % size; | |
282 | } | |
283 | ||
6708d944 DH |
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 | |
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 | ||
a3528574 SR |
299 | /* |
300 | * The switch handles our starting conditions, then we hash the | |
301 | * remaining bytes in groups of 3 | |
6708d944 | 302 | */ |
f6b8f48d | 303 | |
6708d944 | 304 | switch (len % 3) { |
a3528574 SR |
305 | case 0: |
306 | break; | |
307 | case 2: | |
308 | accum ^= *s++ << 8; | |
309 | case 1: | |
310 | accum ^= *s++; | |
6708d944 DH |
311 | break; |
312 | } | |
313 | ||
a3528574 SR |
314 | while (s < end) { |
315 | accum ^= *s++ << 16; | |
316 | accum ^= *s++ << 8; | |
317 | accum ^= *s++; | |
318 | } | |
319 | ||
6708d944 DH |
320 | return accum % size; |
321 | } | |
322 | ||
f7fdb216 DH |
323 | unsigned |
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 | |
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 | ||
6708d944 DH |
343 | unsigned char * |
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 | ||
8b1cb226 DH |
354 | if (table == NULL) |
355 | return (unsigned char *) "No table."; | |
356 | ||
6708d944 | 357 | if (table->hash_count == 0) |
28868515 | 358 | return (unsigned char *) "Invalid hash table."; |
6708d944 DH |
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) | |
28868515 | 387 | return (unsigned char *) "Report out of range for display."; |
6708d944 | 388 | |
f6b8f48d | 389 | sprintf((char *)retbuf, |
28868515 | 390 | "Contents/Size (%%): %u/%u (%u%%). Min/max: %u/%u", |
6708d944 DH |
391 | contents, table->hash_count, pct, minlen, maxlen); |
392 | ||
393 | return retbuf; | |
394 | } | |
395 | ||
f7fdb216 | 396 | void add_hash (table, key, len, pointer, file, line) |
d7837182 | 397 | struct hash_table *table; |
b1b7b521 | 398 | unsigned len; |
f7fdb216 | 399 | const void *key; |
20916cae TL |
400 | hashed_object_t *pointer; |
401 | const char *file; | |
402 | int line; | |
d7837182 | 403 | { |
a0330332 TL |
404 | int hashno; |
405 | struct hash_bucket *bp; | |
0cae26a7 | 406 | void *foo; |
a0330332 TL |
407 | |
408 | if (!table) | |
409 | return; | |
410 | ||
48036271 | 411 | if (!len) |
f7fdb216 | 412 | len = find_length(key, table->do_hash); |
48036271 | 413 | |
f7fdb216 | 414 | hashno = (*table->do_hash)(key, len, table->hash_count); |
20916cae | 415 | bp = new_hash_bucket (file, line); |
a0330332 | 416 | |
d7837182 | 417 | if (!bp) { |
f7fdb216 | 418 | log_error ("Can't add entry to hash table: no memory."); |
d7837182 TL |
419 | return; |
420 | } | |
f7fdb216 | 421 | bp -> name = key; |
0cae26a7 TL |
422 | if (table -> referencer) { |
423 | foo = &bp -> value; | |
20916cae | 424 | (*(table -> referencer)) (foo, pointer, file, line); |
0cae26a7 TL |
425 | } else |
426 | bp -> value = pointer; | |
d7837182 | 427 | bp -> next = table -> buckets [hashno]; |
97ca1699 | 428 | bp -> len = len; |
d7837182 TL |
429 | table -> buckets [hashno] = bp; |
430 | } | |
431 | ||
f7fdb216 | 432 | void delete_hash_entry (table, key, len, file, line) |
d7837182 | 433 | struct hash_table *table; |
b1b7b521 | 434 | unsigned len; |
f7fdb216 | 435 | const void *key; |
20916cae TL |
436 | const char *file; |
437 | int line; | |
d7837182 | 438 | { |
a0330332 | 439 | int hashno; |
d7837182 | 440 | struct hash_bucket *bp, *pbp = (struct hash_bucket *)0; |
0cae26a7 | 441 | void *foo; |
d7837182 | 442 | |
a0330332 TL |
443 | if (!table) |
444 | return; | |
445 | ||
48036271 | 446 | if (!len) |
f7fdb216 | 447 | len = find_length(key, table->do_hash); |
48036271 | 448 | |
f7fdb216 | 449 | hashno = (*table->do_hash)(key, len, table->hash_count); |
a0330332 | 450 | |
d7837182 TL |
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) { | |
69858972 | 454 | if ((!bp -> len && |
f7fdb216 | 455 | !strcmp ((const char *)bp->name, key)) || |
d7837182 | 456 | (bp -> len == len && |
f7fdb216 | 457 | !(table -> cmp)(bp->name, key, len))) { |
d7837182 TL |
458 | if (pbp) { |
459 | pbp -> next = bp -> next; | |
460 | } else { | |
461 | table -> buckets [hashno] = bp -> next; | |
462 | } | |
d758ad8c | 463 | if (bp -> value && table -> dereferencer) { |
0cae26a7 | 464 | foo = &bp -> value; |
20916cae | 465 | (*(table -> dereferencer)) (foo, file, line); |
0cae26a7 | 466 | } |
20916cae | 467 | free_hash_bucket (bp, file, line); |
d7837182 TL |
468 | break; |
469 | } | |
4c4c7907 | 470 | pbp = bp; /* jwg, 9/6/96 - nice catch! */ |
d7837182 TL |
471 | } |
472 | } | |
473 | ||
f7fdb216 | 474 | int hash_lookup (vp, table, key, len, file, line) |
20916cae | 475 | hashed_object_t **vp; |
d7837182 | 476 | struct hash_table *table; |
f7fdb216 | 477 | const void *key; |
b1b7b521 | 478 | unsigned len; |
20916cae TL |
479 | const char *file; |
480 | int line; | |
d7837182 | 481 | { |
a0330332 | 482 | int hashno; |
d7837182 TL |
483 | struct hash_bucket *bp; |
484 | ||
a0330332 | 485 | if (!table) |
20916cae | 486 | return 0; |
48036271 | 487 | if (!len) |
f7fdb216 | 488 | len = find_length(key, table->do_hash); |
48036271 | 489 | |
272ef1bc SK |
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 | ||
f7fdb216 | 495 | hashno = (*table->do_hash)(key, len, table->hash_count); |
a0330332 | 496 | |
48036271 TL |
497 | for (bp = table -> buckets [hashno]; bp; bp = bp -> next) { |
498 | if (len == bp -> len | |
f7fdb216 | 499 | && !(*table->cmp)(bp->name, key, len)) { |
20916cae TL |
500 | if (table -> referencer) |
501 | (*table -> referencer) (vp, bp -> value, | |
502 | file, line); | |
503 | else | |
504 | *vp = bp -> value; | |
505 | return 1; | |
506 | } | |
d7837182 | 507 | } |
20916cae | 508 | return 0; |
d7837182 TL |
509 | } |
510 | ||
d0411fbd TL |
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; | |
06e77c34 DH |
524 | if ((*func)(bp->name, bp->len, bp->value) |
525 | != ISC_R_SUCCESS) | |
526 | return count; | |
d0411fbd TL |
527 | bp = next; |
528 | count++; | |
529 | } | |
530 | } | |
531 | return count; | |
532 | } | |
533 | ||
d19e2cf7 | 534 | int casecmp (const void *v1, const void *v2, size_t len) |
7d9784f6 | 535 | { |
d19e2cf7 | 536 | size_t i; |
804401cc EH |
537 | const unsigned char *s = v1; |
538 | const unsigned char *t = v2; | |
f6b8f48d | 539 | |
7d9784f6 TL |
540 | for (i = 0; i < len; i++) |
541 | { | |
542 | int c1, c2; | |
d19e2cf7 DH |
543 | if (isascii(s[i])) |
544 | c1 = tolower(s[i]); | |
7d9784f6 | 545 | else |
d19e2cf7 DH |
546 | c1 = s[i]; |
547 | ||
548 | if (isascii(t[i])) | |
549 | c2 = tolower(t[i]); | |
7d9784f6 | 550 | else |
d19e2cf7 DH |
551 | c2 = t[i]; |
552 | ||
7d9784f6 TL |
553 | if (c1 < c2) |
554 | return -1; | |
555 | if (c1 > c2) | |
556 | return 1; | |
557 | } | |
558 | return 0; | |
559 | } |