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