omapip/hash.c

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