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