X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fdb.c;h=d9c984b70db27ab42c0b74549560489fae5d83fa;hb=9778f344521a2a0a34582fae70f4d631c82dd7a6;hp=c3d2c88695f3e4fee4ea1f837404ed2273c7a3cf;hpb=a9397765ec1fc7102c080ed072173ce0ee156050;p=libucw.git diff --git a/lib/db.c b/lib/db.c index c3d2c886..d9c984b7 100644 --- a/lib/db.c +++ b/lib/db.c @@ -1,7 +1,10 @@ /* - * Sherlock Library -- Fast Database Management Routines + * UCW Library -- Fast Database Management Routines * - * (c) 1999 Martin Mares + * (c) 1999--2001 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. */ /* @@ -17,18 +20,25 @@ * o The only pages which can be freed are those of the directory (during * directory split), so we keep only a simple 32-entry free block list * and we assume it's sorted. + * o All pointers are always given in pages from start of the file. + * This gives us page_size*2^32 limit for file size which should be enough. */ +#include "lib/lib.h" +#include "lib/lfs.h" +#include "lib/pagecache.h" +#include "lib/db.h" +#include "lib/db_internal.h" + #include -#include #include #include #include -#include "lib.h" -#include "pagecache.h" -#include "db.h" -#include "db_internal.h" +#define GET_PAGE(d,x) pgc_get((d)->cache, (d)->fd, ((sh_off_t)(x)) << (d)->page_order) +#define GET_ZERO_PAGE(d,x) pgc_get_zero((d)->cache, (d)->fd, ((sh_off_t)(x)) << (d)->page_order) +#define READ_PAGE(d,x) pgc_read((d)->cache, (d)->fd, ((sh_off_t)(x)) << (d)->page_order) +#define READ_DIR(d,off) pgc_read((d)->cache, (d)->fd, (((sh_off_t)(d)->root->dir_start) << (d)->page_order) + (off)) struct sdbm * sdbm_open(struct sdbm_options *o) @@ -37,24 +47,23 @@ sdbm_open(struct sdbm_options *o) struct sdbm_root root, *r; uns cache_size = o->cache_size ? o->cache_size : 16; - d = xmalloc(sizeof(struct sdbm)); - bzero(d, sizeof(*d)); + d = xmalloc_zero(sizeof(struct sdbm)); d->flags = o->flags; - d->fd = open(o->name, ((d->flags & SDBM_WRITE) ? O_RDWR : O_RDONLY), 0666); + d->fd = sh_open(o->name, ((d->flags & SDBM_WRITE) ? O_RDWR : O_RDONLY), 0666); if (d->fd >= 0) /* Already exists, let's check it */ { if (read(d->fd, &root, sizeof(root)) != sizeof(root)) goto bad; if (root.magic != SDBM_MAGIC || root.version != SDBM_VERSION) goto bad; - d->file_size = lseek(d->fd, 0, SEEK_END); + d->file_size = sh_seek(d->fd, 0, SEEK_END) >> root.page_order; + d->page_order = root.page_order; d->page_size = 1 << root.page_order; d->cache = pgc_open(d->page_size, cache_size); d->root_page = pgc_read(d->cache, d->fd, 0); d->root = (void *) d->root_page->data; - /* FIXME: Should we do some locking? */ } - else if ((d->flags & SDBM_CREAT) && (d->fd = open(o->name, O_RDWR | O_CREAT, 0666)) >= 0) + else if ((d->flags & SDBM_CREAT) && (d->fd = sh_open(o->name, O_RDWR | O_CREAT, 0666)) >= 0) { struct page *q; uns page_order = o->page_order; @@ -62,27 +71,26 @@ sdbm_open(struct sdbm_options *o) page_order = 10; d->page_size = 1 << page_order; d->cache = pgc_open(d->page_size, cache_size); - d->root_page = pgc_get_zero(d->cache, d->fd, 0); + d->root_page = GET_ZERO_PAGE(d, 0); r = d->root = (void *) d->root_page->data; /* Build root page */ r->magic = SDBM_MAGIC; r->version = SDBM_VERSION; - r->page_order = page_order; + r->page_order = d->page_order = page_order; r->key_size = o->key_size; r->val_size = o->val_size; - r->dir_start = d->page_size; + r->dir_start = 1; r->dir_order = 0; - d->file_size = 3*d->page_size; - q = pgc_get_zero(d->cache, d->fd, d->page_size); /* Build page directory */ - ((u32 *)q->data)[0] = 2*d->page_size; + d->file_size = 3; + q = GET_ZERO_PAGE(d, 1); /* Build page directory */ + GET32(q->data, 0) = 2; pgc_put(d->cache, q); - q = pgc_get_zero(d->cache, d->fd, 2*d->page_size); /* Build single data page */ + q = GET_ZERO_PAGE(d, 2); /* Build single data page */ pgc_put(d->cache, q); } else goto bad; d->dir_size = 1 << d->root->dir_order; d->dir_shift = 32 - d->root->dir_order; - d->page_order = d->root->page_order; d->page_mask = d->page_size - 1; d->key_size = d->root->key_size; d->val_size = d->root->val_size; @@ -102,14 +110,16 @@ sdbm_close(struct sdbm *d) pgc_close(d->cache); if (d->fd >= 0) close(d->fd); - free(d); + xfree(d); } static uns sdbm_alloc_pages(struct sdbm *d, uns number) { uns where = d->file_size; - d->file_size += number << d->page_order; + if (where + number < where) /* Wrap around? */ + die("SDB: Database file too large, giving up"); + d->file_size += number; return where; } @@ -121,10 +131,10 @@ sdbm_alloc_page(struct sdbm *d) if (!d->root->free_pool[0].count) return sdbm_alloc_pages(d, 1); pos = d->root->free_pool[0].first; - d->root->free_pool[0].first += d->page_size; + d->root->free_pool[0].first++; if (!--d->root->free_pool[0].count) { - memmove(d->root->free_pool, d->root->free_pool+1, SDBM_NUM_FREE_PAGE_POOLS * sizeof(d->root->free_pool[0])); + memmove(d->root->free_pool, d->root->free_pool+1, (SDBM_NUM_FREE_PAGE_POOLS-1) * sizeof(d->root->free_pool[0])); d->root->free_pool[SDBM_NUM_FREE_PAGE_POOLS-1].count = 0; } pgc_mark_dirty(d->cache, d->root_page); @@ -138,25 +148,23 @@ sdbm_free_pages(struct sdbm *d, uns start, uns number) while (d->root->free_pool[i].count) i++; + ASSERT(i < SDBM_NUM_FREE_PAGE_POOLS); d->root->free_pool[i].first = start; d->root->free_pool[i].count = number; pgc_mark_dirty(d->cache, d->root_page); } -static u32 +u32 sdbm_hash(byte *key, uns keylen) { /* - * This is the same hash function as GDBM uses. - * FIXME: Use a faster one? + * This used to be the same hash function as GDBM uses, + * but it turned out that it tends to give the same results + * on similar keys. Damn it. */ - u32 value; - int index; - - /* Set the initial value from key. */ - value = 0x238F13AF * keylen; - for (index = 0; index < keylen; index++) - value = value + (key[index] << (index*5 % 24)); + u32 value = 0x238F13AF * keylen; + while (keylen--) + value = 37*value + *key++; return (1103515243 * value + 12345); } @@ -223,7 +231,7 @@ sdbm_page_rank(struct sdbm *d, uns dirpos) uns l, r; uns pm = d->page_mask; - b = pgc_read(d->cache, d->fd, d->root->dir_start + (dirpos & ~pm)); + b = READ_DIR(d, dirpos & ~pm); pg = GET32(b->data, dirpos & pm); l = dirpos; while ((l & pm) && GET32(b->data, (l - 4) & pm) == pg) @@ -239,7 +247,7 @@ sdbm_page_rank(struct sdbm *d, uns dirpos) /* Note that if it spans page boundary, it must contain an integer number of pages */ while (l) { - b = pgc_read(d->cache, d->fd, d->root->dir_start + ((l - 4) & ~pm)); + b = READ_DIR(d, (l - 4) & ~pm); x = GET32(b->data, 0); pgc_put(d->cache, b); if (x != pg) @@ -248,7 +256,7 @@ sdbm_page_rank(struct sdbm *d, uns dirpos) } while (r < 4*d->dir_size) { - b = pgc_read(d->cache, d->fd, d->root->dir_start + (r & ~pm)); + b = READ_DIR(d, r & ~pm); x = GET32(b->data, 0); pgc_put(d->cache, b); if (x != pg) @@ -263,13 +271,16 @@ static void sdbm_expand_directory(struct sdbm *d) { struct page *b, *c; - int i; + int i, ent; u32 *dir, *t; + if (d->root->dir_order >= 31) + die("SDB: Database directory too large, giving up"); + if (4*d->dir_size < d->page_size) { /* It still fits within single page */ - b = pgc_read(d->cache, d->fd, d->root->dir_start); + b = READ_DIR(d, 0); dir = (u32 *) b->data; for(i=d->dir_size-1; i>=0; i--) dir[2*i] = dir[2*i+1] = dir[i]; @@ -280,19 +291,19 @@ sdbm_expand_directory(struct sdbm *d) { uns old_dir = d->root->dir_start; uns old_dir_pages = 1 << (d->root->dir_order + 2 - d->page_order); - uns page, ent, new_dir; + uns page, new_dir; new_dir = d->root->dir_start = sdbm_alloc_pages(d, 2*old_dir_pages); ent = 1 << (d->page_order - 3); for(page=0; page < old_dir_pages; page++) { - b = pgc_read(d->cache, d->fd, old_dir + (page << d->page_order)); + b = READ_PAGE(d, old_dir + page); dir = (u32 *) b->data; - c = pgc_get(d->cache, d->fd, new_dir + (page << (d->page_order + 1))); + c = GET_PAGE(d, new_dir + 2*page); t = (u32 *) c->data; for(i=0; icache, c); - c = pgc_get(d->cache, d->fd, new_dir + (page << (d->page_order + 1)) + d->page_size); + c = GET_PAGE(d, new_dir + 2*page + 1); t = (u32 *) c->data; for(i=0; icache, d->fd, old_dir + (page << d->page_order)); + b = GET_ZERO_PAGE(d, old_dir + page); pgc_put(d->cache, b); } } @@ -352,7 +363,7 @@ sdbm_split_dir(struct sdbm *d, uns dirpos, uns count, uns pos) count *= 4; while (count) { - b = pgc_read(d->cache, d->fd, d->root->dir_start + (dirpos & ~d->page_mask)); + b = READ_DIR(d, dirpos & ~d->page_mask); i = d->page_size - (dirpos & d->page_mask); if (i > count) i = count; @@ -368,12 +379,22 @@ sdbm_split_dir(struct sdbm *d, uns dirpos, uns count, uns pos) } } +static inline uns +sdbm_dirpos(struct sdbm *d, uns hash) +{ + if (d->dir_shift != 32) /* avoid shifting by 32 bits */ + return (hash >> d->dir_shift) << 2; /* offset in the directory */ + else + return 0; +} + static struct page * -sdbm_split_page(struct sdbm *d, struct page *b, u32 hash, uns dirpos) +sdbm_split_page(struct sdbm *d, struct page *b, u32 hash) { struct page *p[2]; - uns i, rank, sigbit, rank_log; + uns i, rank, sigbit, rank_log, dirpos, newpg; + dirpos = sdbm_dirpos(d, hash); rank = sdbm_page_rank(d, dirpos); /* rank = # of pointers to this page */ if (rank == 1) { @@ -382,19 +403,34 @@ sdbm_split_page(struct sdbm *d, struct page *b, u32 hash, uns dirpos) dirpos *= 2; } rank_log = 1; /* rank_log = log2(rank) */ - while ((1 << rank_log) < rank) + while ((1U << rank_log) < rank) rank_log++; sigbit = d->dir_shift + rank_log - 1; /* sigbit = bit we split on */ p[0] = b; - p[1] = pgc_get_zero(d->cache, d->fd, sdbm_alloc_page(d)); + newpg = sdbm_alloc_page(d); + p[1] = GET_PAGE(d, newpg); sdbm_split_data(d, (void *) b->data, (void *) p[0]->data, (void *) p[1]->data, sigbit); - sdbm_split_dir(d, (dirpos & ~(4*rank - 1))+2*rank, rank/2, pgc_page_pos(d->cache, p[1])); + sdbm_split_dir(d, (dirpos & ~(4*rank - 1))+2*rank, rank/2, newpg); pgc_mark_dirty(d->cache, p[0]); i = (hash & (1 << sigbit)) ? 1 : 0; pgc_put(d->cache, p[!i]); return p[i]; } +static int +sdbm_put_user(byte *D, uns Dl, byte *val, uns *vallen) +{ + if (vallen) + { + if (*vallen < Dl) + return 1; + *vallen = Dl; + } + if (val) + memcpy(val, D, Dl); + return 0; +} + static int sdbm_access(struct sdbm *d, byte *key, uns keylen, byte *val, uns *vallen, uns mode) /* 0=read, 1=store, 2=replace */ { @@ -404,21 +440,18 @@ sdbm_access(struct sdbm *d, byte *key, uns keylen, byte *val, uns *vallen, uns m byte *c, *e; int rc; - if ((d->key_size >= 0 && keylen != d->key_size) || keylen > 65535) + if ((d->key_size >= 0 && keylen != (uns) d->key_size) || keylen > 65535) return SDBM_ERROR_BAD_KEY_SIZE; - if (val && ((d->val_size >= 0 && *vallen != d->val_size) || *vallen >= 65535)) + if (val && ((d->val_size >= 0 && *vallen != (uns) d->val_size) || *vallen >= 65535) && mode) return SDBM_ERROR_BAD_VAL_SIZE; if (!mode && !(d->flags & SDBM_WRITE)) return SDBM_ERROR_READ_ONLY; hash = sdbm_hash(key, keylen); - if (d->dir_shift != 32) /* avoid shifting by 32 bits */ - h = (hash >> d->dir_shift) << 2; /* offset in the directory */ - else - h = 0; - p = pgc_read(d->cache, d->fd, d->root->dir_start + (h & ~d->page_mask)); + h = sdbm_dirpos(d, hash); + p = READ_DIR(d, h & ~d->page_mask); pos = GET32(p->data, h & d->page_mask); pgc_put(d->cache, p); - q = pgc_read(d->cache, d->fd, pos); + q = READ_PAGE(d, pos); b = (void *) q->data; c = b->data; e = c + b->used; @@ -433,17 +466,9 @@ sdbm_access(struct sdbm *d, byte *key, uns keylen, byte *val, uns *vallen, uns m switch (mode) { case 0: /* fetch: found */ - rc = 1; - if (vallen) - { - if (*vallen < Dl) - rc = -3; - *vallen = Dl; - } - if (val) - memcpy(val, D, Dl); + rc = sdbm_put_user(D, Dl, val, vallen); pgc_put(d->cache, q); - return rc; + return rc ? SDBM_ERROR_TOO_LARGE : 1; case 1: /* store: already present */ pgc_put(d->cache, q); return 0; @@ -468,7 +493,12 @@ insert: while (b->used + size > d->page_size - sizeof(struct sdbm_bucket)) { /* Page overflow, need to split */ - q = sdbm_split_page(d, q, hash, h); + if (size >= d->page_size - sizeof(struct sdbm_bucket)) + { + pgc_put(d->cache, q); + return SDBM_ERROR_GIANT; + } + q = sdbm_split_page(d, q, hash); b = (void *) q->data; } sdbm_store_entry(d, b->data + b->used, key, keylen, val, *vallen); @@ -508,11 +538,54 @@ sdbm_fetch(struct sdbm *d, byte *key, uns keylen, byte *val, uns *vallen) void sdbm_rewind(struct sdbm *d) { + d->find_page = 1; + d->find_pos = 0; + d->find_free_list = 0; } int sdbm_get_next(struct sdbm *d, byte *key, uns *keylen, byte *val, uns *vallen) { + uns page = d->find_page; + uns pos = d->find_pos; + byte *K, *V; + uns c, Kl, Vl; + struct page *p; + struct sdbm_bucket *b; + + for(;;) + { + if (!pos) + { + if (page >= d->file_size) + break; + if (page == d->root->dir_start) + page += (4*d->dir_size + d->page_size - 1) >> d->page_order; + else if (page == d->root->free_pool[d->find_free_list].first) + page += d->root->free_pool[d->find_free_list++].count; + else + pos = 4; + continue; + } + p = READ_PAGE(d, page); + b = (void *) p->data; + if (pos - 4 >= b->used) + { + pos = 0; + page++; + pgc_put(d->cache, p); + continue; + } + c = sdbm_get_entry(d, p->data + pos, &K, &Kl, &V, &Vl); + d->find_page = page; + d->find_pos = pos + c; + c = sdbm_put_user(K, Kl, key, keylen) || + sdbm_put_user(V, Vl, val, vallen); + pgc_put(d->cache, p); + return c ? SDBM_ERROR_TOO_LARGE : 1; + } + d->find_page = page; + d->find_pos = pos; return 0; } @@ -523,54 +596,3 @@ sdbm_sync(struct sdbm *d) if (d->flags & SDBM_FSYNC) fsync(d->fd); } - -#ifdef TEST - -int main(void) -{ - struct sdbm *d; - struct sdbm_options o = { - name: "db.test", - flags: SDBM_CREAT | SDBM_WRITE, - page_order: 10, - cache_size: 1024, - key_size: -1, - val_size: -1 - }; - byte buf[256]; - int i, j, k; - - puts("OPEN"); - d = sdbm_open(&o); - if (!d) - die("failed: %m"); - - puts("WRITE"); - for(i=0; i<1000000; i++) - { - sprintf(buf, "%d", i); - k = sdbm_store(d, buf, strlen(buf), (byte *) &i, sizeof(i)); -// printf("%s:%d\r", buf, k); - fflush(stdout); - } - sdbm_sync(d); - - puts("READ"); - for(i=0; i<1000000; i++) - { - sprintf(buf, "%d", i); - j = sdbm_fetch(d, buf, strlen(buf), NULL, NULL); -// printf("%s:%d\r", buf, j); - fflush(stdout); - if (!j) - { printf("\nERR: %s %d %x %d\n", buf, j, sdbm_hash(buf, strlen(buf)), d->dir_shift); return 1; } - } - puts(""); - - puts("CLOSE"); - sdbm_close(d); - puts("DONE"); - return 0; -} - -#endif