X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=bacula%2Fsrc%2Flib%2Fhtable.c;h=a42ec022d0c82e5d30156a1ae70deeeb90cc3dd7;hb=897707854a8240d026e933215009f931bb9c5762;hp=280939dcf38ba39bc1ccb77bcd0b338c0cb4660d;hpb=0504af943735e2f3ef5e127e0575b9d186443e54;p=bacula%2Fbacula diff --git a/bacula/src/lib/htable.c b/bacula/src/lib/htable.c index 280939dcf3..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,52 +65,57 @@ /* * 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; @@ -127,11 +135,12 @@ 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); } /* @@ -146,6 +155,7 @@ void htable::init(void *item, void *link, int tsize) { int pwr; + memset(this, 0, sizeof(htable)); if (tsize < 31) { tsize = 31; } @@ -156,18 +166,12 @@ void htable::init(void *item, void *link, int tsize) loffset = (char *)link - (char *)item; mask = ~((~0)< table size = 8 */ rshift = 30 - pwr; /* start using bits 28, 29, 30 */ - num_items = 0; /* number of entries in table */ buckets = 1<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; @@ -273,22 +279,22 @@ bool htable::insert(char *key, void *item) 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; } @@ -298,7 +304,7 @@ void *htable::lookup(char *key) 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; } } @@ -307,43 +313,43 @@ void *htable::lookup(char *key) 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; } @@ -351,7 +357,7 @@ void *htable::first() void htable::destroy() { #ifdef BIG_MALLOC - hash_free(); + hash_big_free(); #else void *ni; void *li = first(); @@ -427,7 +433,7 @@ int main() free(jcrtbl); printf("Freed jcrtbl\n"); - sm_dump(false); + sm_dump(false); /* unit test */ } #endif