/*
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.
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.
*
* 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
*/
/*
* 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
/*
{
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);
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;
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
}
* 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.
*/
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()
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;
return false; /* already exists */
}
ASSERT(index < buckets);
- Dmsg2(100, "Insert: hash=%p index=%d\n", hash, index);
+ Dmsg2(dbglvl, "Insert: hash=%p index=%d\n", hash, index);
hp = (hlink *)(((char *)item)+loffset);
- Dmsg4(100, "Insert hp=%p index=%d item=%p offset=%u\n", hp,
+ 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=%p hp->hash=0x%x hp->key=%s\n",
+ 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;
}
for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
// Dmsg2(100, "hp=%p key=%s\n", hp, hp->key);
if (hash == hp->hash && strcmp(key, hp->key) == 0) {
- Dmsg1(100, "lookup return %p\n", ((char *)hp)-loffset);
+ Dmsg1(dbglvl, "lookup return %p\n", ((char *)hp)-loffset);
return ((char *)hp)-loffset;
}
}
void *htable::next()
{
- Dmsg1(100, "Enter next: walkptr=%p\n", 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=%p next=%p inx=%d\n", walkptr,
+ Dmsg3(dbglvl, "new walkptr=%p next=%p inx=%d\n", walkptr,
walkptr->next, walk_index-1);
}
}
if (walkptr) {
- Dmsg2(100, "next: rtn %p walk_index=%d\n",
+ 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=%p next=%p inx=%d\n", walkptr,
+ Dmsg3(dbglvl, "first new walkptr=%p next=%p inx=%d\n", walkptr,
walkptr->next, walk_index-1);
}
}
if (walkptr) {
- Dmsg1(100, "Leave first walkptr=%p\n", 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();
free(li);
li=ni;
}
+#endif
free(table);
table = NULL;
hlink link;
};
-#define NITEMS 1000000
+#define NITEMS 5000000
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=%p jcr=%p\n", jcr->link, jcr);
free(jcrtbl);
printf("Freed jcrtbl\n");
- sm_dump(false);
+ sm_dump(false); /* unit test */
}
#endif
projects / bacula / bacula / blobdiff