omapip/hash.c

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