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-2017 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    printf("total bytes malloced = %lld\n", (lli)total_size);
 219    printf("total blocks malloced = %d\n", blocks);
 220 #endif
 221 }
 222
 223 void htable::grow_table()
 224 {
 225    Dmsg1(100, "Grow called old size = %d\n", buckets);
 226    /* Setup a bigger table */
 227    htable *big = (htable *)malloc(sizeof(htable));
 228    memcpy(big, this, sizeof(htable));  /* start with original class data */
 229    big->loffset = loffset;
 230    big->mask = mask<<1 | 1;
 231    big->rshift = rshift - 1;
 232    big->num_items = 0;
 233    big->buckets = buckets * 2;
 234    big->max_items = big->buckets * 4;
 235    /* Create a bigger hash table */
 236    big->table = (hlink **)malloc(big->buckets * sizeof(hlink *));
 237    bmemzero(big->table, big->buckets * sizeof(hlink *));
 238    big->walkptr = NULL;
 239    big->walk_index = 0;
 240    /* Insert all the items in the new hash table */
 241    Dmsg1(100, "Before copy num_items=%d\n", num_items);
 242    /*
 243     * We walk through the old smaller tree getting items,
 244     * but since we are overwriting the colision links, we must
 245     * explicitly save the item->next pointer and walk each
 246     * colision chain ourselves.  We do use next() for getting
 247     * to the next bucket.
 248     */
 249    for (void *item=first(); item; ) {
 250       void *ni = ((hlink *)((char *)item+loffset))->next;  /* save link overwritten by insert */
 251       hlink *hp = (hlink *)((char *)item+loffset);
 252       if (hp->is_ikey) {
 253          Dmsg1(100, "Grow insert: %lld\n", hp->key.ikey);
 254          big->insert(hp->key.ikey, item);
 255       } else {
 256          Dmsg1(100, "Grow insert: %s\n", hp->key.key);
 257          big->insert(hp->key.key, item);
 258       }
 259       if (ni) {
 260          item = (void *)((char *)ni-loffset);
 261       } else {
 262          walkptr = NULL;
 263          item = next();
 264       }
 265    }
 266    Dmsg1(100, "After copy new num_items=%d\n", big->num_items);
 267    if (num_items != big->num_items) {
 268       Dmsg0(000, "****** Big problems num_items mismatch ******\n");
 269    }
 270    free(table);
 271    memcpy(this, big, sizeof(htable));  /* move everything across */
 272    free(big);
 273    Dmsg0(100, "Exit grow.\n");
 274 }
 275
 276 bool htable::insert(char *key, void *item)
 277 {
 278    hlink *hp;
 279    if (lookup(key)) {
 280       return false;                   /* already exists */
 281    }
 282    ASSERT(index < buckets);
 283    Dmsg2(dbglvl, "Insert: hash=%p index=%d\n", hash, index);
 284    hp = (hlink *)(((char *)item)+loffset);
 285    Dmsg4(dbglvl, "Insert hp=%p index=%d item=%p offset=%u\n", hp,
 286       index, item, loffset);
 287    hp->next = table[index];
 288    hp->hash = hash;
 289    hp->key.key = key;
 290    hp->is_ikey = false;
 291    table[index] = hp;
 292    Dmsg3(dbglvl, "Insert hp->next=%p hp->hash=0x%x hp->key=%s\n",
 293       hp->next, hp->hash, hp->key.key);
 294
 295    if (++num_items >= max_items) {
 296       Dmsg2(dbglvl, "num_items=%d max_items=%d\n", num_items, max_items);
 297       grow_table();
 298    }
 299    Dmsg3(dbglvl, "Leave insert index=%d num_items=%d key=%s\n", index, num_items, key);
 300    return true;
 301 }
 302
 303 void *htable::lookup(char *key)
 304 {
 305    hash_index(key);
 306    for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
 307 //    Dmsg2(100, "hp=%p key=%s\n", hp, hp->key.key);
 308       if (hash == hp->hash && strcmp(key, hp->key.key) == 0) {
 309          Dmsg1(dbglvl, "lookup return %p\n", ((char *)hp)-loffset);
 310          return ((char *)hp)-loffset;
 311       }
 312    }
 313    return NULL;
 314 }
 315
 316 bool htable::insert(uint64_t ikey, void *item)
 317 {
 318    hlink *hp;
 319    if (lookup(ikey)) {
 320       return false;                  /* already exists */
 321    }
 322    ASSERT(index < buckets);
 323    Dmsg2(dbglvl, "Insert: hash=%p index=%d\n", hash, index);
 324    hp = (hlink *)(((char *)item)+loffset);
 325    Dmsg4(dbglvl, "Insert hp=%p index=%d item=%p offset=%u\n", hp, index,
 326      item, loffset);
 327    hp->next = table[index];
 328    hp->hash = hash;
 329    hp->key.ikey = ikey;
 330    hp->is_ikey = true;
 331    table[index] = hp;
 332    Dmsg3(dbglvl, "Insert hp->next=%p hp->hash=0x%x hp->ikey=%lld\n", hp->next,
 333       hp->hash, hp->key.ikey);
 334
 335    if (++num_items >= max_items) {
 336       Dmsg2(dbglvl, "num_items=%d max_items=%d\n", num_items, max_items);
 337       grow_table();
 338    }
 339    Dmsg3(dbglvl, "Leave insert index=%d num_items=%d key=%lld\n",
 340       index, num_items, ikey);
 341    return true;
 342 }
 343
 344 void *htable::lookup(uint64_t ikey)
 345 {
 346    hash_index(ikey);
 347    for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
 348 //    Dmsg2(100, "hp=%p key=%lld\n", hp, hp->key.ikey);
 349       if (hash == hp->hash && ikey == hp->key.ikey) {
 350          Dmsg1(dbglvl, "lookup return %p\n", ((char *)hp)-loffset);
 351          return ((char *)hp)-loffset;
 352       }
 353    }
 354    return NULL;
 355 }
 356
 357 void *htable::next()
 358 {
 359    Dmsg1(dbglvl, "Enter next: walkptr=%p\n", walkptr);
 360    if (walkptr) {
 361       walkptr = (hlink *)(walkptr->next);
 362    }
 363    while (!walkptr && walk_index < buckets) {
 364       walkptr = table[walk_index++];
 365       if (walkptr) {
 366          Dmsg3(dbglvl, "new walkptr=%p next=%p inx=%d\n", walkptr,
 367             walkptr->next, walk_index-1);
 368       }
 369    }
 370    if (walkptr) {
 371       Dmsg2(dbglvl, "next: rtn %p walk_index=%d\n",
 372          ((char *)walkptr)-loffset, walk_index);
 373       return ((char *)walkptr)-loffset;
 374    }
 375    Dmsg0(dbglvl, "next: return NULL\n");
 376    return NULL;
 377 }
 378
 379 void *htable::first()
 380 {
 381    Dmsg0(dbglvl, "Enter first\n");
 382    walkptr = table[0];                /* get first bucket */
 383    walk_index = 1;                    /* Point to next index */
 384    while (!walkptr && walk_index < buckets) {
 385       walkptr = table[walk_index++];  /* go to next bucket */
 386       if (walkptr) {
 387          Dmsg3(dbglvl, "first new walkptr=%p next=%p inx=%d\n", walkptr,
 388             walkptr->next, walk_index-1);
 389       }
 390    }
 391    if (walkptr) {
 392       Dmsg1(dbglvl, "Leave first walkptr=%p\n", walkptr);
 393       return ((char *)walkptr)-loffset;
 394    }
 395    Dmsg0(dbglvl, "Leave first walkptr=NULL\n");
 396    return NULL;
 397 }
 398
 399 /* Destroy the table and its contents */
 400 void htable::destroy()
 401 {
 402 #ifdef BIG_MALLOC
 403    hash_big_free();
 404 #else
 405    void *ni;
 406    void *li = first();
 407
 408    while (li) {
 409       ni = next();
 410       free(li);
 411       li=ni;
 412    }
 413 #endif
 414
 415    free(table);
 416    table = NULL;
 417    Dmsg0(100, "Done destroy.\n");
 418 }
 419
 420
 421
 422 #ifdef TEST_PROGRAM
 423
 424 struct MYJCR {
 425    char *key;
 426    hlink link;
 427 };
 428
 429 #define NITEMS 5000000
 430
 431 int main()
 432 {
 433    char mkey[30];
 434    htable *jcrtbl;
 435    MYJCR *save_jcr = NULL, *item;
 436    MYJCR *jcr = NULL;
 437    int count = 0;
 438
 439    jcrtbl = (htable *)malloc(sizeof(htable));
 440    jcrtbl->init(jcr, &jcr->link, NITEMS);
 441
 442    Dmsg1(000, "Inserting %d items\n", NITEMS);
 443    for (int i=0; i<NITEMS; i++) {
 444       int len;
 445       len = sprintf(mkey, "This is htable item %d", i) + 1;
 446
 447       jcr = (MYJCR *)jcrtbl->hash_malloc(sizeof(MYJCR));
 448       jcr->key = (char *)jcrtbl->hash_malloc(len);
 449       memcpy(jcr->key, mkey, len);
 450       Dmsg2(100, "link=%p jcr=%p\n", jcr->link, jcr);
 451
 452       jcrtbl->insert(jcr->key, jcr);
 453       if (i == 10) {
 454          save_jcr = jcr;
 455       }
 456    }
 457    if (!(item = (MYJCR *)jcrtbl->lookup(save_jcr->key))) {
 458       printf("Bad news: %s not found.\n", save_jcr->key);
 459    } else {
 460       printf("Item 10's key is: %s\n", item->key);
 461    }
 462
 463    jcrtbl->stats();
 464    printf("Walk the hash table:\n");
 465    foreach_htable (jcr, jcrtbl) {
 466 //    printf("htable item = %s\n", jcr->key);
 467 #ifndef BIG_MALLOC
 468       free(jcr->key);
 469 #endif
 470       count++;
 471    }
 472    printf("Got %d items -- %s\n", count, count==NITEMS?"OK":"***ERROR***");
 473    printf("Calling destroy\n");
 474    jcrtbl->destroy();
 475
 476    free(jcrtbl);
 477    printf("Freed jcrtbl\n");
 478
 479    sm_dump(false);   /* unit test */
 480
 481 }
 482 #endif