git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/htable.c

   1 /*
   2    Bacula(R) - The Network Backup Solution
   3
   4    Copyright (C) 2000-2018 Kern Sibbald
   5
   6    The original author of Bacula is Kern Sibbald, with contributions
   7    from many others, a complete list can be found in the file AUTHORS.
   8
   9    You may use this file and others of this release according to the
  10    license defined in the LICENSE file, which includes the Affero General
  11    Public License, v3.0 ("AGPLv3") and some additional permissions and
  12    terms pursuant to its AGPLv3 Section 7.
  13
  14    This notice must be preserved when any source code is
  15    conveyed and/or propagated.
  16
  17    Bacula(R) is a registered trademark of Kern Sibbald.
  18 */
  19 /*
  20  *  Bacula hash table routines
  21  *
  22  *  htable is a hash table of items (pointers). This code is
  23  *    adapted and enhanced from code I wrote in 1982 for a
  24  *    relocatable linker.  At that time, the hash table size
  25  *    was fixed and a primary number, which essentially provides
  26  *    the randomness. In this program, the hash table can grow when
  27  *    it gets too full, so the table size here is a binary number. The
  28  *    hashing is provided using an idea from Tcl where the initial
  29  *    hash code is "randomized" using a simple calculation from
  30  *    a random number generator that multiplies by a big number
  31  *    (I multiply by a prime number, while Tcl did not)
  32  *    then shifts the result down and does the binary division
  33  *    by masking.  Increasing the size of the hash table is simple.
  34  *    Just create a new larger table, walk the old table and
  35  *    re-hash insert each entry into the new table.
  36  *
  37  *
  38  *   Kern Sibbald, July MMIII
  39  *
  40  */
  41
  42 #include "bacula.h"
  43 #include "htable.h"
  44
  45 #define lli long long int
  46 static const int dbglvl = 500;
  47
  48 /* ===================================================================
  49  *    htable
  50  */
  51
  52 #ifdef BIG_MALLOC
  53 /*
  54  * This subroutine gets a big buffer.
  55  */
  56 void htable::malloc_big_buf(int size)
  57 {
  58    struct h_mem *hmem;
  59
  60    hmem = (struct h_mem *)malloc(size);
  61    total_size += size;
  62    blocks++;
  63    hmem->next = mem_block;
  64    mem_block = hmem;
  65    hmem->mem = mem_block->first;
  66    hmem->rem = (char *)hmem + size - hmem->mem;
  67    Dmsg3(100, "malloc buf=%p size=%d rem=%d\n", hmem, size, hmem->rem);
  68 }
  69
  70 /* This routine frees the whole tree */
  71 void htable::hash_big_free()
  72 {
  73    struct h_mem *hmem, *rel;
  74
  75    for (hmem=mem_block; hmem; ) {
  76       rel = hmem;
  77       hmem = hmem->next;
  78       Dmsg1(100, "free malloc buf=%p\n", rel);
  79       free(rel);
  80    }
  81 }
  82
  83 #endif
  84
  85 /*
  86  * Normal hash malloc routine that gets a
  87  *  "small" buffer from the big buffer
  88  */
  89 char *htable::hash_malloc(int size)
  90 {
  91 #ifdef BIG_MALLOC
  92    char *buf;
  93    int asize = BALIGN(size);
  94
  95    if (mem_block->rem < asize) {
  96       uint32_t mb_size;
  97       if (total_size >= 1000000) {
  98          mb_size = 1000000;
  99       } else {
 100          mb_size = 100000;
 101       }
 102       malloc_big_buf(mb_size);
 103    }
 104    mem_block->rem -= asize;
 105    buf = mem_block->mem;
 106    mem_block->mem += asize;
 107    return buf;
 108 #else
 109    total_size += size;
 110    blocks++;
 111    return (char *)malloc(size);
 112 #endif
 113 }
 114
 115
 116
 117
 118 /*
 119  * Create hash of key, stored in hash then
 120  *  create and return the pseudo random bucket index
 121  */
 122 void htable::hash_index(char *key)
 123 {
 124    hash = 0;
 125    for (char *p=key; *p; p++) {
 126       hash +=  ((hash << 5) | (hash >> (sizeof(hash)*8-5))) + (uint32_t)*p;
 127    }
 128    /* Multiply by large prime number, take top bits, mask for remainder */
 129    index = ((hash * 1103515249LL) >> rshift) & mask;
 130    Dmsg2(dbglvl, "Leave hash_index hash=0x%x index=%d\n", hash, index);
 131 }
 132
 133 void htable::hash_index(uint64_t ikey)
 134 {
 135    hash = ikey;           /* already have starting binary hash */
 136    /* Same algorithm as for char * */
 137    index = ((hash * 1103515249LL) >> rshift) & mask;
 138    Dmsg2(dbglvl, "Leave hash_index hash=0x%x index=%d\n", hash, index);
 139 }
 140
 141 /*
 142  * tsize is the estimated number of entries in the hash table
 143  */
 144 htable::htable(void *item, void *link, int tsize)
 145 {
 146    init(item, link, tsize);
 147 }
 148
 149 void htable::init(void *item, void *link, int tsize)
 150 {
 151    int pwr;
 152
 153    bmemzero(this, sizeof(htable));
 154    if (tsize < 31) {
 155       tsize = 31;
 156    }
 157    tsize >>= 2;
 158    for (pwr=0; tsize; pwr++) {
 159       tsize >>= 1;
 160    }
 161    loffset = (char *)link - (char *)item;
 162    mask = ~((~0)<<pwr);               /* 3 bits => table size = 8 */
 163    rshift = 30 - pwr;                 /* start using bits 28, 29, 30 */
 164    buckets = 1<<pwr;                  /* hash table size -- power of two */
 165    max_items = buckets * 4;           /* allow average 4 entries per chain */
 166    table = (hlink **)malloc(buckets * sizeof(hlink *));
 167    bmemzero(table, buckets * sizeof(hlink *));
 168 #ifdef BIG_MALLOC
 169    malloc_big_buf(1000000);   /* ***FIXME*** need variable or some estimate */
 170 #endif /* BIG_MALLOC */
 171 }
 172
 173 uint32_t htable::size()
 174 {
 175    return num_items;
 176 }
 177
 178 /*
 179  * Take each hash link and walk down the chain of items
 180  *  that hash there counting them (i.e. the hits),
 181  *  then report that number.
 182  * Obiously, the more hits in a chain, the more time
 183  *  it takes to reference them. Empty chains are not so
 184  *  hot either -- as it means unused or wasted space.
 185  */
 186 #define MAX_COUNT 20
 187 void htable::stats()
 188 {
 189    int hits[MAX_COUNT];
 190    int max = 0;
 191    int i, j;
 192    hlink *p;
 193    printf("\n\nNumItems=%d\nTotal buckets=%d\n", num_items, buckets);
 194    printf("Hits/bucket: buckets\n");
 195    for (i=0; i < MAX_COUNT; i++) {
 196       hits[i] = 0;
 197    }
 198    for (i=0; i<(int)buckets; i++) {
 199       p = table[i];
 200       j = 0;
 201       while (p) {
 202          p = (hlink *)(p->next);
 203          j++;
 204       }
 205       if (j > max) {
 206          max = j;
 207       }
 208       if (j < MAX_COUNT) {
 209          hits[j]++;
 210       }
 211    }
 212    for (i=0; i < MAX_COUNT; i++) {
 213       printf("%2d:           %d\n",i, hits[i]);
 214    }
 215    printf("buckets=%d num_items=%d max_items=%d\n", buckets, num_items, max_items);
 216    printf("max hits in a bucket = %d\n", max);
 217 #ifdef BIG_MALLOC
 218    char ed1[100];
 219    edit_uint64(total_size, ed1);
 220    printf("total bytes malloced = %s\n", ed1);
 221    printf("total blocks malloced = %d\n", blocks);
 222 #endif
 223 }
 224
 225 void htable::grow_table()
 226 {
 227    Dmsg1(100, "Grow called old size = %d\n", buckets);
 228    /* Setup a bigger table */
 229    htable *big = (htable *)malloc(sizeof(htable));
 230    memcpy(big, this, sizeof(htable));  /* start with original class data */
 231    big->loffset = loffset;
 232    big->mask = mask<<1 | 1;
 233    big->rshift = rshift - 1;
 234    big->num_items = 0;
 235    big->buckets = buckets * 2;
 236    big->max_items = big->buckets * 4;
 237    /* Create a bigger hash table */
 238    big->table = (hlink **)malloc(big->buckets * sizeof(hlink *));
 239    bmemzero(big->table, big->buckets * sizeof(hlink *));
 240    big->walkptr = NULL;
 241    big->walk_index = 0;
 242    /* Insert all the items in the new hash table */
 243    Dmsg1(100, "Before copy num_items=%d\n", num_items);
 244    /*
 245     * We walk through the old smaller tree getting items,
 246     * but since we are overwriting the colision links, we must
 247     * explicitly save the item->next pointer and walk each
 248     * colision chain ourselves.  We do use next() for getting
 249     * to the next bucket.
 250     */
 251    for (void *item=first(); item; ) {
 252       void *ni = ((hlink *)((char *)item+loffset))->next;  /* save link overwritten by insert */
 253       hlink *hp = (hlink *)((char *)item+loffset);
 254       if (hp->is_ikey) {
 255          Dmsg1(100, "Grow insert: %lld\n", hp->key.ikey);
 256          big->insert(hp->key.ikey, item);
 257       } else {
 258          Dmsg1(100, "Grow insert: %s\n", hp->key.key);
 259          big->insert(hp->key.key, item);
 260       }
 261       if (ni) {
 262          item = (void *)((char *)ni-loffset);
 263       } else {
 264          walkptr = NULL;
 265          item = next();
 266       }
 267    }
 268    Dmsg1(100, "After copy new num_items=%d\n", big->num_items);
 269    if (num_items != big->num_items) {
 270       Dmsg0(000, "****** Big problems num_items mismatch ******\n");
 271    }
 272    free(table);
 273    memcpy(this, big, sizeof(htable));  /* move everything across */
 274    free(big);
 275    Dmsg0(100, "Exit grow.\n");
 276 }
 277
 278 bool htable::insert(char *key, void *item)
 279 {
 280    hlink *hp;
 281    if (lookup(key)) {
 282       return false;                   /* already exists */
 283    }
 284    ASSERT(index < buckets);
 285    Dmsg2(dbglvl, "Insert: hash=%p index=%d\n", hash, index);
 286    hp = (hlink *)(((char *)item)+loffset);
 287    Dmsg4(dbglvl, "Insert hp=%p index=%d item=%p offset=%u\n", hp,
 288       index, item, loffset);
 289    hp->next = table[index];
 290    hp->hash = hash;
 291    hp->key.key = key;
 292    hp->is_ikey = false;
 293    table[index] = hp;
 294    Dmsg3(dbglvl, "Insert hp->next=%p hp->hash=0x%x hp->key=%s\n",
 295       hp->next, hp->hash, hp->key.key);
 296
 297    if (++num_items >= max_items) {
 298       Dmsg2(dbglvl, "num_items=%d max_items=%d\n", num_items, max_items);
 299       grow_table();
 300    }
 301    Dmsg3(dbglvl, "Leave insert index=%d num_items=%d key=%s\n", index, num_items, key);
 302    return true;
 303 }
 304
 305 void *htable::lookup(char *key)
 306 {
 307    hash_index(key);
 308    for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
 309 //    Dmsg2(100, "hp=%p key=%s\n", hp, hp->key.key);
 310       if (hash == hp->hash && strcmp(key, hp->key.key) == 0) {
 311          Dmsg1(dbglvl, "lookup return %p\n", ((char *)hp)-loffset);
 312          return ((char *)hp)-loffset;
 313       }
 314    }
 315    return NULL;
 316 }
 317
 318 bool htable::insert(uint64_t ikey, void *item)
 319 {
 320    hlink *hp;
 321    if (lookup(ikey)) {
 322       return false;                  /* already exists */
 323    }
 324    ASSERT(index < buckets);
 325    Dmsg2(dbglvl, "Insert: hash=%p index=%d\n", hash, index);
 326    hp = (hlink *)(((char *)item)+loffset);
 327    Dmsg4(dbglvl, "Insert hp=%p index=%d item=%p offset=%u\n", hp, index,
 328      item, loffset);
 329    hp->next = table[index];
 330    hp->hash = hash;
 331    hp->key.ikey = ikey;
 332    hp->is_ikey = true;
 333    table[index] = hp;
 334    Dmsg3(dbglvl, "Insert hp->next=%p hp->hash=0x%x hp->ikey=%lld\n", hp->next,
 335       hp->hash, hp->key.ikey);
 336
 337    if (++num_items >= max_items) {
 338       Dmsg2(dbglvl, "num_items=%d max_items=%d\n", num_items, max_items);
 339       grow_table();
 340    }
 341    Dmsg3(dbglvl, "Leave insert index=%d num_items=%d key=%lld\n",
 342       index, num_items, ikey);
 343    return true;
 344 }
 345
 346 void *htable::lookup(uint64_t ikey)
 347 {
 348    hash_index(ikey);
 349    for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
 350 //    Dmsg2(100, "hp=%p key=%lld\n", hp, hp->key.ikey);
 351       if (hash == hp->hash && ikey == hp->key.ikey) {
 352          Dmsg1(dbglvl, "lookup return %p\n", ((char *)hp)-loffset);
 353          return ((char *)hp)-loffset;
 354       }
 355    }
 356    return NULL;
 357 }
 358
 359 void *htable::next()
 360 {
 361    Dmsg1(dbglvl, "Enter next: walkptr=%p\n", walkptr);
 362    if (walkptr) {
 363       walkptr = (hlink *)(walkptr->next);
 364    }
 365    while (!walkptr && walk_index < buckets) {
 366       walkptr = table[walk_index++];
 367       if (walkptr) {
 368          Dmsg3(dbglvl, "new walkptr=%p next=%p inx=%d\n", walkptr,
 369             walkptr->next, walk_index-1);
 370       }
 371    }
 372    if (walkptr) {
 373       Dmsg2(dbglvl, "next: rtn %p walk_index=%d\n",
 374          ((char *)walkptr)-loffset, walk_index);
 375       return ((char *)walkptr)-loffset;
 376    }
 377    Dmsg0(dbglvl, "next: return NULL\n");
 378    return NULL;
 379 }
 380
 381 void *htable::first()
 382 {
 383    Dmsg0(dbglvl, "Enter first\n");
 384    walkptr = table[0];                /* get first bucket */
 385    walk_index = 1;                    /* Point to next index */
 386    while (!walkptr && walk_index < buckets) {
 387       walkptr = table[walk_index++];  /* go to next bucket */
 388       if (walkptr) {
 389          Dmsg3(dbglvl, "first new walkptr=%p next=%p inx=%d\n", walkptr,
 390             walkptr->next, walk_index-1);
 391       }
 392    }
 393    if (walkptr) {
 394       Dmsg1(dbglvl, "Leave first walkptr=%p\n", walkptr);
 395       return ((char *)walkptr)-loffset;
 396    }
 397    Dmsg0(dbglvl, "Leave first walkptr=NULL\n");
 398    return NULL;
 399 }
 400
 401 /* Destroy the table and its contents */
 402 void htable::destroy()
 403 {
 404 #ifdef BIG_MALLOC
 405    hash_big_free();
 406 #else
 407    void *ni;
 408    void *li = first();
 409
 410    while (li) {
 411       ni = next();
 412       free(li);
 413       li=ni;
 414    }
 415 #endif
 416
 417    free(table);
 418    table = NULL;
 419    Dmsg0(100, "Done destroy.\n");
 420 }
 421
 422
 423
 424 #ifdef TEST_PROGRAM
 425
 426 struct MYJCR {
 427    char *key;
 428    hlink link;
 429 };
 430
 431 #define NITEMS 5000000
 432
 433 int main()
 434 {
 435    char mkey[30];
 436    htable *jcrtbl;
 437    MYJCR *save_jcr = NULL, *item;
 438    MYJCR *jcr = NULL;
 439    int count = 0;
 440
 441    jcrtbl = (htable *)malloc(sizeof(htable));
 442    jcrtbl->init(jcr, &jcr->link, NITEMS);
 443
 444    Dmsg1(000, "Inserting %d items\n", NITEMS);
 445    for (int i=0; i<NITEMS; i++) {
 446       int len;
 447       len = sprintf(mkey, "This is htable item %d", i) + 1;
 448
 449       jcr = (MYJCR *)jcrtbl->hash_malloc(sizeof(MYJCR));
 450       jcr->key = (char *)jcrtbl->hash_malloc(len);
 451       memcpy(jcr->key, mkey, len);
 452       Dmsg2(100, "link=%p jcr=%p\n", jcr->link, jcr);
 453
 454       jcrtbl->insert(jcr->key, jcr);
 455       if (i == 10) {
 456          save_jcr = jcr;
 457       }
 458    }
 459    if (!(item = (MYJCR *)jcrtbl->lookup(save_jcr->key))) {
 460       printf("Bad news: %s not found.\n", save_jcr->key);
 461    } else {
 462       printf("Item 10's key is: %s\n", item->key);
 463    }
 464
 465    jcrtbl->stats();
 466    printf("Walk the hash table:\n");
 467    foreach_htable (jcr, jcrtbl) {
 468 //    printf("htable item = %s\n", jcr->key);
 469 #ifndef BIG_MALLOC
 470       free(jcr->key);
 471 #endif
 472       count++;
 473    }
 474    printf("Got %d items -- %s\n", count, count==NITEMS?"OK":"***ERROR***");
 475    printf("Calling destroy\n");
 476    jcrtbl->destroy();
 477
 478    free(jcrtbl);
 479    printf("Freed jcrtbl\n");
 480
 481    sm_dump(false);   /* unit test */
 482
 483 }
 484 #endif