X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=bacula%2Fsrc%2Flib%2Fhtable.c;h=a42ec022d0c82e5d30156a1ae70deeeb90cc3dd7;hb=897707854a8240d026e933215009f931bb9c5762;hp=b56bba851f64dc471ecb7a29220417f0fe2823ea;hpb=420c3f313066e9652480a22b14f4db53070d9345;p=bacula%2Fbacula

diff --git a/bacula/src/lib/htable.c b/bacula/src/lib/htable.c
index b56bba851f..a42ec022d0 100644
--- a/bacula/src/lib/htable.c
+++ b/bacula/src/lib/htable.c
@@ -1,12 +1,12 @@
 /*
    Bacula® - The Network Backup Solution
 
-   Copyright (C) 2003-2008 Free Software Foundation Europe e.V.
+   Copyright (C) 2003-2010 Free Software Foundation Europe e.V.
 
    The main author of Bacula is Kern Sibbald, with contributions from
    many others, a complete list can be found in the file AUTHORS.
    This program is Free Software; you can redistribute it and/or
-   modify it under the terms of version two of the GNU General Public
+   modify it under the terms of version three of the GNU Affero General Public
    License as published by the Free Software Foundation and included
    in the file LICENSE.
 
@@ -15,12 +15,12 @@
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    General Public License for more details.
 
-   You should have received a copy of the GNU General Public License
+   You should have received a copy of the GNU Affero General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
    02110-1301, USA.
 
-   Bacula® is a registered trademark of John Walker.
+   Bacula® is a registered trademark of Kern Sibbald.
    The licensor of Bacula is the Free Software Foundation Europe
    (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
    Switzerland, email:ftf@fsfeurope.org.
@@ -46,14 +46,17 @@
  *
  *   Kern Sibbald, July MMIII
  *
- *   Version $Id$
- *
  */
 
 #include "bacula.h"
-
 #include "htable.h"
 
+#define PAGE_SIZE 4096
+#define MAX_PAGES 2400
+#define MAX_BUF_SIZE (MAX_PAGES * PAGE_SIZE)  /* approx 10MB */
+
+static const int dbglvl = 500;
+
 /* ===================================================================
  *    htable
  */
@@ -62,53 +65,66 @@
 /*
  * This subroutine gets a big buffer.
  */
-void htable::malloc_buf(int size)
+void htable::malloc_big_buf(int size)
 {
    struct h_mem *hmem;
 
    hmem = (struct h_mem *)malloc(size);
    total_size += size;
    blocks++;
-   hmem->next = this->mem;
-   this->mem = hmem;
-   hmem->mem = mem->first;
+   hmem->next = mem_block;
+   mem_block = hmem;
+   hmem->mem = mem_block->first;
    hmem->rem = (char *)hmem + size - hmem->mem;
-   Dmsg2(200, "malloc buf size=%d rem=%d\n", size, hmem->rem);
+   Dmsg3(100, "malloc buf=%p size=%d rem=%d\n", hmem, size, hmem->rem);
+}
+
+/* This routine frees the whole tree */
+void htable::hash_big_free()
+{
+   struct h_mem *hmem, *rel;
+
+   for (hmem=mem_block; hmem; ) {
+      rel = hmem;
+      hmem = hmem->next;
+      Dmsg1(100, "free malloc buf=%p\n", rel);
+      free(rel);
+   }
 }
 
-char *htable::hash_alloc(int size)
+#endif
+
+/*
+ * Normal hash malloc routine that gets a 
+ *  "small" buffer from the big buffer
+ */
+char *htable::hash_malloc(int size)
 {
+#ifdef BIG_MALLOC
    char *buf;
    int asize = BALIGN(size);
 
-   if (mem->rem < asize) {
+   if (mem_block->rem < asize) {
       uint32_t mb_size;
-      if (total_size >= 1000000) {
-         mb_size = 1000000;
+      if (total_size >= (MAX_BUF_SIZE / 2)) {
+         mb_size = MAX_BUF_SIZE;
       } else {
-         mb_size = 100000;
+         mb_size = MAX_BUF_SIZE / 2;
       }
-      malloc_buf(mb_size);
+      malloc_big_buf(mb_size);
    }
-   mem->rem -= asize;
-   buf = mem->mem;
-   mem->mem += asize;
+   mem_block->rem -= asize;
+   buf = mem_block->mem;
+   mem_block->mem += asize;
    return buf;
+#else 
+   total_size += size;
+   blocks++;
+   return (char *)malloc(size);
+#endif
 }
 
 
-/* This routine frees the whole tree */
-void htable::hash_free()
-{
-   struct h_mem *hmem, *rel;
-
-   for (hmem=mem; hmem; ) {
-      rel = hmem;
-      hmem = hmem->next;
-      free(rel);
-   }
-}
-#endif
  
 
 /*
@@ -119,13 +135,17 @@ void htable::hash_index(char *key)
 {
    hash = 0;
    for (char *p=key; *p; p++) {
-      hash += (hash << 3) + (uint32_t)*p;
+//    hash += (hash << 3) + (uint32_t)*p;
+      hash +=  ((hash << 5) | (hash >> (sizeof(hash)*8-5))) + (uint32_t)*p;
    }
    /* Multiply by large prime number, take top bits, mask for remainder */
    index = ((hash * 1103515249) >> rshift) & mask;
-   Dmsg2(100, "Leave hash_index hash=0x%x index=%d\n", hash, index);
+   Dmsg2(dbglvl, "Leave hash_index hash=0x%x index=%d\n", hash, index);
 }
 
+/*
+ * tsize is the estimated number of entries in the hash table
+ */
 htable::htable(void *item, void *link, int tsize)
 {
    init(item, link, tsize);
@@ -134,6 +154,11 @@ htable::htable(void *item, void *link, int tsize)
 void htable::init(void *item, void *link, int tsize)
 {
    int pwr;
+
+   memset(this, 0, sizeof(htable));
+   if (tsize < 31) {
+      tsize = 31;
+   }
    tsize >>= 2;
    for (pwr=0; tsize; pwr++) {
       tsize >>= 1;
@@ -141,16 +166,12 @@ void htable::init(void *item, void *link, int tsize)
    loffset = (char *)link - (char *)item;
    mask = ~((~0)<<pwr);               /* 3 bits => table size = 8 */
    rshift = 30 - pwr;                 /* start using bits 28, 29, 30 */
-   num_items = 0;                     /* number of entries in table */
    buckets = 1<<pwr;                  /* hash table size -- power of two */
    max_items = buckets * 4;           /* allow average 4 entries per chain */
    table = (hlink **)malloc(buckets * sizeof(hlink *));
    memset(table, 0, buckets * sizeof(hlink *));
-   walkptr = NULL;
-   walk_index = 0;
 #ifdef BIG_MALLOC
-   mem = NULL;
-   malloc_buf(1000000);   /* ***FIXME*** base off of size */
+   malloc_big_buf(MAX_BUF_SIZE);   /* ***FIXME*** need variable or some estimate */
 #endif
 }
 
@@ -163,7 +184,7 @@ uint32_t htable::size()
  * Take each hash link and walk down the chain of items
  *  that hash there counting them (i.e. the hits), 
  *  then report that number.
- *  Obiously, the more hits in a chain, the more time
+ * Obiously, the more hits in a chain, the more time
  *  it takes to reference them. Empty chains are not so
  *  hot either -- as it means unused or wasted space.
  */
@@ -196,7 +217,12 @@ void htable::stats()
    for (i=0; i < MAX_COUNT; i++) {
       printf("%2d:           %d\n",i, hits[i]);
    }
+   printf("buckets=%d num_items=%d max_items=%d\n", buckets, num_items, max_items);
    printf("max hits in a bucket = %d\n", max);
+#ifdef BIG_MALLOC
+   printf("total bytes malloced = %d\n", total_size);
+   printf("total blocks malloced = %d\n", blocks);
+#endif
 }
 
 void htable::grow_table()
@@ -204,12 +230,14 @@ void htable::grow_table()
    Dmsg1(100, "Grow called old size = %d\n", buckets);
    /* Setup a bigger table */
    htable *big = (htable *)malloc(sizeof(htable));
+   memcpy(big, this, sizeof(htable));  /* start with original class data */
    big->loffset = loffset;
    big->mask = mask<<1 | 1;
    big->rshift = rshift - 1;
    big->num_items = 0;
    big->buckets = buckets * 2;
    big->max_items = big->buckets * 4;
+   /* Create a bigger hash table */
    big->table = (hlink **)malloc(big->buckets * sizeof(hlink *));
    memset(big->table, 0, big->buckets * sizeof(hlink *));
    big->walkptr = NULL;
@@ -251,22 +279,22 @@ bool htable::insert(char *key, void *item)
       return false;                   /* already exists */
    }
    ASSERT(index < buckets);
-   Dmsg2(100, "Insert: hash=0x%x index=%d\n", (unsigned)hash, index);
+   Dmsg2(dbglvl, "Insert: hash=%p index=%d\n", hash, index);
    hp = (hlink *)(((char *)item)+loffset);
-   Dmsg4(100, "Insert hp=0x%x index=%d item=0x%x offset=%u\n", (unsigned)hp,
-      index, (unsigned)item, loffset);
+   Dmsg4(dbglvl, "Insert hp=%p index=%d item=%p offset=%u\n", hp,
+      index, item, loffset);
    hp->next = table[index];
    hp->hash = hash;
    hp->key = key;
    table[index] = hp;
-   Dmsg3(100, "Insert hp->next=0x%x hp->hash=0x%x hp->key=%s\n",
-      (unsigned)hp->next, hp->hash, hp->key);
+   Dmsg3(dbglvl, "Insert hp->next=%p hp->hash=0x%x hp->key=%s\n",
+      hp->next, hp->hash, hp->key);
 
    if (++num_items >= max_items) {
-      Dmsg2(100, "num_items=%d max_items=%d\n", num_items, max_items);
+      Dmsg2(dbglvl, "num_items=%d max_items=%d\n", num_items, max_items);
       grow_table();
    }
-   Dmsg3(100, "Leave insert index=%d num_items=%d key=%s\n", index, num_items, key);
+   Dmsg3(dbglvl, "Leave insert index=%d num_items=%d key=%s\n", index, num_items, key);
    return true;
 }
 
@@ -274,9 +302,9 @@ void *htable::lookup(char *key)
 {
    hash_index(key);
    for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
-//    Dmsg2(100, "hp=0x%x key=%s\n", (long)hp, hp->key);
+//    Dmsg2(100, "hp=%p key=%s\n", hp, hp->key);
       if (hash == hp->hash && strcmp(key, hp->key) == 0) {
-         Dmsg1(100, "lookup return %x\n", ((char *)hp)-loffset);
+         Dmsg1(dbglvl, "lookup return %p\n", ((char *)hp)-loffset);
          return ((char *)hp)-loffset;
       }
    }
@@ -285,49 +313,52 @@ void *htable::lookup(char *key)
 
 void *htable::next()
 {
-   Dmsg1(100, "Enter next: walkptr=0x%x\n", (unsigned)walkptr);
+   Dmsg1(dbglvl, "Enter next: walkptr=%p\n", walkptr);
    if (walkptr) {
       walkptr = (hlink *)(walkptr->next);
    }
    while (!walkptr && walk_index < buckets) {
       walkptr = table[walk_index++];
       if (walkptr) {
-         Dmsg3(100, "new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
-            (unsigned)(walkptr->next), walk_index-1);
+         Dmsg3(dbglvl, "new walkptr=%p next=%p inx=%d\n", walkptr,
+            walkptr->next, walk_index-1);
       }
    }
    if (walkptr) {
-      Dmsg2(100, "next: rtn 0x%x walk_index=%d\n",
-         (unsigned)(((char *)walkptr)-loffset), walk_index);
+      Dmsg2(dbglvl, "next: rtn %p walk_index=%d\n",
+         ((char *)walkptr)-loffset, walk_index);
       return ((char *)walkptr)-loffset;
    }
-   Dmsg0(100, "next: return NULL\n");
+   Dmsg0(dbglvl, "next: return NULL\n");
    return NULL;
 }
 
 void *htable::first()
 {
-   Dmsg0(100, "Enter first\n");
+   Dmsg0(dbglvl, "Enter first\n");
    walkptr = table[0];                /* get first bucket */
    walk_index = 1;                    /* Point to next index */
    while (!walkptr && walk_index < buckets) {
       walkptr = table[walk_index++];  /* go to next bucket */
       if (walkptr) {
-         Dmsg3(100, "first new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
-            (unsigned)(walkptr->next), walk_index-1);
+         Dmsg3(dbglvl, "first new walkptr=%p next=%p inx=%d\n", walkptr,
+            walkptr->next, walk_index-1);
       }
    }
    if (walkptr) {
-      Dmsg1(100, "Leave first walkptr=0x%x\n", (unsigned)walkptr);
+      Dmsg1(dbglvl, "Leave first walkptr=%p\n", walkptr);
       return ((char *)walkptr)-loffset;
    }
-   Dmsg0(100, "Leave first walkptr=NULL\n");
+   Dmsg0(dbglvl, "Leave first walkptr=NULL\n");
    return NULL;
 }
 
 /* Destroy the table and its contents */
 void htable::destroy()
 {
+#ifdef BIG_MALLOC
+   hash_big_free();
+#else
    void *ni;
    void *li = first();
 
@@ -336,6 +367,7 @@ void htable::destroy()
       free(li);
       li=ni;
    }
+#endif
 
    free(table);
    table = NULL;
@@ -351,7 +383,7 @@ struct MYJCR {
    hlink link;
 };
 
-#define NITEMS 1000000
+#define NITEMS 5000000
 
 int main()
 {
@@ -369,15 +401,10 @@ int main()
       int len;
       len = sprintf(mkey, "This is htable item %d", i) + 1;
 
-#ifdef BIG_MALLOC
-      jcr = (MYJCR *)jcrtbl->hash_alloc(sizeof(MYJCR));
-      jcr->key = (char *)jcrtbl->hash_alloc(len);
-#else
-      jcr = (MYJCR *)malloc(sizeof(MYJCR));
-      jcr->key = (char *)malloc(len);
-#endif
+      jcr = (MYJCR *)jcrtbl->hash_malloc(sizeof(MYJCR));
+      jcr->key = (char *)jcrtbl->hash_malloc(len);
       memcpy(jcr->key, mkey, len);
-      Dmsg2(100, "link=0x%x jcr=0x%x\n", (unsigned)&jcr->link, (unsigned)jcr);
+      Dmsg2(100, "link=%p jcr=%p\n", jcr->link, jcr);
 
       jcrtbl->insert(jcr->key, jcr);
       if (i == 10) {
@@ -406,7 +433,7 @@ int main()
    free(jcrtbl);
    printf("Freed jcrtbl\n");
 
-   sm_dump(false);
+   sm_dump(false);   /* unit test */
 
 }
 #endif