/*
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_free()
+void htable::hash_big_free()
{
struct h_mem *hmem, *rel;
- for (hmem=mem; hmem; ) {
+ for (hmem=mem_block; hmem; ) {
rel = hmem;
hmem = hmem->next;
+ Dmsg1(100, "free malloc buf=%p\n", rel);
free(rel);
}
}
#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;
{
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);
}
/*
{
int pwr;
+ memset(this, 0, sizeof(htable));
if (tsize < 31) {
tsize = 31;
}
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;
- total_size = 0;
- blocks = 0;
#ifdef BIG_MALLOC
- mem = NULL;
- malloc_buf(1000000); /* ***FIXME*** need variable or some estimate */
+ malloc_big_buf(MAX_BUF_SIZE); /* ***FIXME*** need variable or some estimate */
#endif
}
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;
}
void htable::destroy()
{
#ifdef BIG_MALLOC
- hash_free();
+ hash_big_free();
#else
void *ni;
void *li = first();
free(jcrtbl);
printf("Freed jcrtbl\n");
- sm_dump(false);
+ sm_dump(false); /* unit test */
}
#endif
projects / bacula / bacula / blobdiff