omapip/hash.c

   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
  99 void free_hash_table (tp, file, line)
 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
 129 struct hash_bucket *free_hash_buckets;
 130
 131 #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
 132 struct hash_bucket *hash_bucket_hunks;
 133
 134 void relinquish_hash_bucket_hunks ()
 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
 165 struct hash_bucket *new_hash_bucket (file, line)
 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
 194 void free_hash_bucket (ptr, file, line)
 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 }