ISC DHCP  4.4.2b1
A reference DHCPv4 and DHCPv6 implementation
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-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
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 
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 
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)
131 struct 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. */
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 
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 
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
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
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
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
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 
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 
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 
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 
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 
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 
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 
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 }
free_hash_bucket
void free_hash_bucket(struct hash_bucket *ptr, const char *file, int line)
Definition: hash.c:193
hashed_object_t
Definition: hash.h:41
omapip_p.h
log_fatal
void log_fatal(const char *,...) __attribute__((__format__(__printf__
do_id_hash
unsigned do_id_hash(const void *name, unsigned len, unsigned size)
Definition: hash.c:290
casecmp
int casecmp(const void *v1, const void *v2, size_t len)
Definition: hash.c:534
line
const char int line
Definition: dhcpd.h:3793
add_hash
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
do_case_hash
unsigned do_case_hash(const void *name, unsigned len, unsigned size)
Definition: hash.c:240
dhcpd.h
hash_reference
int(* hash_reference)(hashed_object_t **, hashed_object_t *, const char *, int)
Definition: hash.h:46
delete_hash_entry
void delete_hash_entry(struct hash_table *table, const void *key, unsigned len, const char *file, int line)
Definition: hash.c:432
value
Definition: data.h:205
hash_table::do_hash
unsigned(* do_hash)(const void *, unsigned, unsigned)
Definition: hash.h:64
hash_table
Definition: hash.h:59
hash_table::hash_count
unsigned hash_count
Definition: hash.h:60
DEFAULT_HASH_SIZE
#define DEFAULT_HASH_SIZE
Definition: hash.h:33
hash_bucket::name
const unsigned char * name
Definition: hash.h:52
hash_bucket::len
unsigned len
Definition: hash.h:53
log_info
int int log_info(const char *,...) __attribute__((__format__(__printf__
relinquish_hash_bucket_hunks
void relinquish_hash_bucket_hunks(void)
dfree
void dfree(void *, const char *, int)
Definition: alloc.c:145
MDL
#define MDL
Definition: omapip.h:567
do_string_hash
unsigned do_string_hash(const void *name, unsigned len, unsigned size)
Definition: hash.c:266
hash_bucket::value
hashed_object_t * value
Definition: hash.h:54
log_error
int log_error(const char *,...) __attribute__((__format__(__printf__
hash_lookup
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
file
const char * file
Definition: dhcpd.h:3793
new_hash
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
hash_foreach_func
isc_result_t(* hash_foreach_func)(const void *, unsigned, void *)
Definition: hash.h:45
hash_foreach
int hash_foreach(struct hash_table *table, hash_foreach_func func)
Definition: hash.c:511
hash_bucket::next
struct hash_bucket * next
Definition: hash.h:51
hash_table::buckets
struct hash_bucket * buckets[1]
Definition: hash.h:67
free_hash_buckets
struct hash_bucket * free_hash_buckets
Definition: hash.c:128
dmalloc
void * dmalloc(size_t, const char *, int)
Definition: alloc.c:57
do_ip4_hash
unsigned do_ip4_hash(const void *key, unsigned len, unsigned size)
Definition: hash.c:332
hash_bucket
Definition: hash.h:50
log_debug
int int int log_debug(const char *,...) __attribute__((__format__(__printf__
hash_dereference
int(* hash_dereference)(hashed_object_t **, const char *, int)
Definition: hash.h:48
new_hash_bucket
struct hash_bucket * new_hash_bucket(char *file, int line) const
Definition: hash.c:164
hash_report
unsigned char * hash_report(struct hash_table *table)
Definition: hash.c:344
do_number_hash
unsigned do_number_hash(const void *key, unsigned len, unsigned size)
Definition: hash.c:324
free_hash_table
void free_hash_table(struct hash_table **tp, const char *file, int line)
Definition: hash.c:98
ISC_R_SUCCESS
#define ISC_R_SUCCESS
new_hash_table
int new_hash_table(struct hash_table **tp, unsigned count, const char *file, int line)
Definition: hash.c:55
hash_table::cmp
hash_comparator_t cmp
Definition: hash.h:63