diff options
Diffstat (limited to 'source3')
| -rw-r--r-- | source3/Makefile.in | 12 | ||||
| -rw-r--r-- | source3/include/includes.h | 1 | ||||
| -rw-r--r-- | source3/include/proto.h | 11 | ||||
| -rw-r--r-- | source3/tdb/README | 33 | ||||
| -rw-r--r-- | source3/tdb/tdb.c | 1001 | ||||
| -rw-r--r-- | source3/tdb/tdb.h | 61 | ||||
| -rw-r--r-- | source3/tdb/tdbtest.c | 217 | ||||
| -rw-r--r-- | source3/tdb/tdbtool.c | 206 |
8 files changed, 1541 insertions, 1 deletions
diff --git a/source3/Makefile.in b/source3/Makefile.in index b538a1c176..ca85566703 100644 --- a/source3/Makefile.in +++ b/source3/Makefile.in @@ -98,7 +98,8 @@ LIB_OBJ = lib/charcnv.o lib/charset.o lib/debug.o lib/fault.o \ lib/bitmap.o lib/crc32.o lib/snprintf.o \ lib/util_str.o lib/util_sid.o \ lib/util_unistr.o lib/util_file.o \ - lib/util.o lib/util_sock.o lib/util_sec.o smbd/ssl.o lib/fnmatch.o + lib/util.o lib/util_sock.o lib/util_sec.o smbd/ssl.o lib/fnmatch.o \ + tdb/tdb.o UBIQX_OBJ = ubiqx/ubi_BinTree.o ubiqx/ubi_Cache.o ubiqx/ubi_SplayTree.o \ ubiqx/ubi_dLinkList.o ubiqx/ubi_sLinkList.o ubiqx/debugparse.o @@ -263,6 +264,9 @@ SMBFILTER_OBJ = utils/smbfilter.o $(LIBSMB_OBJ) $(PARAM_OBJ) \ PROTO_OBJ = $(SMBD_OBJ) $(NMBD_OBJ) $(SWAT_OBJ) $(CLIENT_OBJ) \ $(RPCCLIENT_OBJ) $(SMBWRAPPER_OBJ) $(SMBTORTURE_OBJ) +NSS_OBJ_0 = nsswitch/wins.o $(PARAM_OBJ) $(UBIQX_OBJ) $(LIBSMB_OBJ) $(LIB_OBJ) $(NSSWINS_OBJ) +NSS_OBJ = $(NSS_OBJ_0:.o=.po) + PICOBJS = $(SMBWRAPPER_OBJ:.o=.po) PICOBJS32 = $(SMBWRAPPER_OBJ:.o=.po32) @@ -457,6 +461,12 @@ bin/smbsh: $(SMBSH_OBJ) bin/.dummy @echo Linking $@ @$(CC) $(FLAGS) -o $@ $(SMBSH_OBJ) $(LDFLAGS) $(LIBS) +nsswitch/libnss_wins.so: $(NSS_OBJ) + @echo "Linking $@" + @$(LD) @LDSHFLAGS@ -o $@ $(NSS_OBJ) + +nsswitch: nsswitch/libnss_wins.so + install: installbin installman installscripts installcp installswat installdirs: diff --git a/source3/include/includes.h b/source3/include/includes.h index 2a10badd73..e8eb8e28ea 100644 --- a/source3/include/includes.h +++ b/source3/include/includes.h @@ -614,6 +614,7 @@ extern int errno; #include "ubi_sLinkList.h" #include "ubi_dLinkList.h" #include "dlinklist.h" +#include "../tdb/tdb.h" #include "interfaces.h" #ifdef HAVE_FNMATCH diff --git a/source3/include/proto.h b/source3/include/proto.h index 25d95323bc..c933a93222 100644 --- a/source3/include/proto.h +++ b/source3/include/proto.h @@ -2793,6 +2793,17 @@ int smbw_stat_printjob(struct smbw_server *srv,char *path, int smbw_fstat(int fd, struct stat *st); int smbw_stat(const char *fname, struct stat *st); +/*The following definitions come from tdb/tdb.c */ + +int tdb_update(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf); +int tdb_exists(TDB_CONTEXT *tdb, TDB_DATA key); +int tdb_traverse(TDB_CONTEXT *tdb, int (*fn)(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf)); +int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key); +int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag); +int tdb_close(TDB_CONTEXT *tdb); +int tdb_writelock(TDB_CONTEXT *tdb); +int tdb_writeunlock(TDB_CONTEXT *tdb); + /*The following definitions come from utils/nbio.c */ void nb_setup(struct cli_state *cli); diff --git a/source3/tdb/README b/source3/tdb/README new file mode 100644 index 0000000000..fc99a68acc --- /dev/null +++ b/source3/tdb/README @@ -0,0 +1,33 @@ +This is a simple database API. It was inspired by the realisation that +in Samba we have several ad-hoc bits of code that essentially +implement small databases for sharing structures between parts of +Samba. As I was about to add another I realised that a generic +database module was called for to replace all the ad-hoc bits. + +I based the interface on gdbm. I couldn't use gdbm as we need to be +able to have multiple writers to the databases at one time. + +Compilation +----------- + +add HAVE_MMAP=1 to use mmap instead of read/write +add TDB_DEBUG for verbose debug info +add NOLOCK=1 to disable locking code + +Testing +------- + +Compile tdbtest.c and link with gdbm for testing. tdbtest will perform +identical operations via tdb and gdbm then make sure the result is the +same + +Interface +--------- + +The interface is very similar to gdbm except for the following: + +- different open interface. The tdb_open call is more similar to a + traditional open() +- no tdbm_reorganise() function +- no tdbm_sync() function. No operations are cached in the library anyway +- added a tdb_traverse() function for traversing the whole database diff --git a/source3/tdb/tdb.c b/source3/tdb/tdb.c new file mode 100644 index 0000000000..dacecf9572 --- /dev/null +++ b/source3/tdb/tdb.c @@ -0,0 +1,1001 @@ +/* + Unix SMB/Netbios implementation. + Version 3.0 + Samba database functions + Copyright (C) Andrew Tridgell 1999 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + 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 + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. +*/ + +#if STANDALONE +#include <stdlib.h> +#include <stdio.h> +#include <fcntl.h> +#include <unistd.h> +#include <string.h> +#include <fcntl.h> +#include <sys/mman.h> +#include <sys/stat.h> +#include "tdb.h" +#else +#include "includes.h" +#endif + +#define TDB_VERSION (0x26011967 + 0) +#define TDB_ALIGN 32 +#define MIN_REC_SIZE (2*sizeof(struct list_struct) + TDB_ALIGN) +#define DEFAULT_HASH_SIZE 512 +#define TDB_PAGE_SIZE 0x1000 +#define FREELIST_TOP (sizeof(struct tdb_header)) + +/* the body of the database is made of one list_struct for the free space + plus a separate data list for each hash value */ +struct list_struct { + tdb_len rec_len; /* total byte length of record */ + tdb_off next; /* offset of the next record in the list */ + tdb_len key_len; /* byte length of key */ + tdb_len data_len; /* byte length of data */ + unsigned full_hash; /* the full 32 bit hash of the key */ + /* + the following union is implied + union { + char record[rec_len]; + struct { + char key[key_len]; + char data[data_len]; + } + } + */ +}; + +/* a null data record - useful for error returns */ +static TDB_DATA null_data; + +#if STANDALONE +/* like strdup but for memory */ +static char *memdup(char *d, int size) +{ + char *ret; + ret = (char *)malloc(size); + if (!ret) return NULL; + memcpy(ret, d, size); + return ret; +} +#endif + +/* the hash algorithm - turn a key into an integer + This is based on the hash agorithm from gdbm */ +static unsigned tdb_hash(TDB_DATA *key) +{ + unsigned value; /* Used to compute the hash value. */ + unsigned i; /* Used to cycle through random values. */ + + /* Set the initial value from the key size. */ + value = 0x238F13AF * key->dsize; + for (i=0; i < key->dsize; i++) { + value = (value + (key->dptr[i] << (i*5 % 24))); + } + + value = (1103515243 * value + 12345); + + return value; +} + +/* find the top of the hash chain for an open database */ +static tdb_off tdb_hash_top(TDB_CONTEXT *tdb, unsigned hash) +{ + tdb_off ret; + hash = hash % tdb->header.hash_size; + ret = FREELIST_TOP + (hash+1)*sizeof(tdb_off); + return ret; +} + +/* write a lump of data at a specified offset */ +static int tdb_write(TDB_CONTEXT *tdb, tdb_off offset, char *buf, tdb_len len) +{ + if (offset + len > tdb->map_size) { + /* oops - trying to write beyond the end of the database! */ +#if TDB_DEBUG + printf("write error of length %u at offset %u (max %u)\n", + len, offset, tdb->map_size); +#endif + return -1; + } + + if (tdb->map_ptr) { + memcpy(offset + (char *)tdb->map_ptr, buf, len); + } else { + lseek(tdb->fd, offset, SEEK_SET); + if (write(tdb->fd, buf, len) != (ssize_t)len) { + return -1; + } + } + return 0; +} + +/* read a lump of data at a specified offset */ +static int tdb_read(TDB_CONTEXT *tdb, tdb_off offset, char *buf, tdb_len len) +{ + if (offset + len > tdb->map_size) { + /* oops - trying to read beyond the end of the database! */ +#if TDB_DEBUG + printf("read error of length %u at offset %u (max %u)\n", + len, offset, tdb->map_size); +#endif + return -1; + } + + if (tdb->map_ptr) { + memcpy(buf, offset + (char *)tdb->map_ptr, len); + } else { + lseek(tdb->fd, offset, SEEK_SET); + if (read(tdb->fd, buf, len) != (ssize_t)len) { + return -1; + } + } + return 0; +} + + +/* read a lump of data, allocating the space for it */ +static char *tdb_alloc_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_len len) +{ + char *buf; + + buf = (char *)malloc(len); + + if (tdb_read(tdb, offset, buf, len) == -1) { + free(buf); + return NULL; + } + + return buf; +} + +/* expand the database at least length bytes by expanding the + underlying file and doing the mmap again if necessary */ +static int tdb_expand(TDB_CONTEXT *tdb, tdb_off length) +{ + struct list_struct rec; + tdb_off offset, ptr; + char b = 0; + + /* always make room for at least 10 more records */ + length *= 10; + + /* and round the database up to a multiple of TDB_PAGE_SIZE */ + length = ((tdb->map_size + length + TDB_PAGE_SIZE) & ~(TDB_PAGE_SIZE - 1)) - tdb->map_size; + + /* expand the file itself */ + lseek(tdb->fd, tdb->map_size + length - 1, SEEK_SET); + if (write(tdb->fd, &b, 1) != 1) return -1; + + /* form a new freelist record */ + offset = FREELIST_TOP; + rec.rec_len = length - sizeof(rec); + if (tdb_read(tdb, offset, (char *)&rec.next, sizeof(rec.next)) == -1) return -1; + +#if HAVE_MMAP + if (tdb->map_ptr) { + munmap(tdb->map_ptr, tdb->map_size); + tdb->map_ptr = NULL; + } +#endif + + tdb->map_size += length; + + /* write it out */ + if (tdb_write(tdb, tdb->map_size - length, (char *)&rec, sizeof(rec)) == -1) return -1; + + /* link it into the free list */ + ptr = tdb->map_size - length; + if (tdb_write(tdb, offset, (char *)&ptr, sizeof(ptr)) == -1) return -1; + +#if HAVE_MMAP + tdb->map_ptr = (void *)mmap(NULL, tdb->map_size, + PROT_READ|PROT_WRITE, + MAP_SHARED | MAP_FILE, tdb->fd, 0); +#endif + +#if TDB_DEBUG + printf("expanded database by %u bytes\n", length); +#endif + + return 0; +} + +/* allocate some space from the free list. The offset returned points + to a unconnected list_struct within the database with room for at + least length bytes of total data + + 0 is returned if the space could not be allocated + */ +static tdb_off tdb_allocate(TDB_CONTEXT *tdb, tdb_len length) +{ + tdb_off offset, rec_ptr, last_ptr; + struct list_struct rec, lastrec, newrec; + + again: + last_ptr = 0; + offset = FREELIST_TOP; + + /* read in the freelist top */ + if (tdb_read(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) { + goto fail; + } + + /* keep looking until we find a freelist record that is big + enough */ + while (rec_ptr) { + if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + goto fail; + } + + if (rec.rec_len >= length) { + /* found it - now possibly split it up */ + if (rec.rec_len > length + MIN_REC_SIZE) { + length = (length + TDB_ALIGN) & ~(TDB_ALIGN-1); + + newrec.rec_len = rec.rec_len - (sizeof(rec) + length); + newrec.next = rec.next; + + rec.rec_len = length; + rec.next = rec_ptr + sizeof(rec) + rec.rec_len; + + if (tdb_write(tdb, rec.next, (char *)&newrec, + sizeof(newrec)) == -1) { + goto fail; + } + + if (tdb_write(tdb, rec_ptr, (char *)&rec, + sizeof(rec)) == -1) { + goto fail; + } + } + + /* remove it from the list */ + if (last_ptr == 0) { + offset = FREELIST_TOP; + + if (tdb_write(tdb, offset, (char *)&rec.next, + sizeof(tdb_off)) == -1) { + goto fail; + } + } else { + lastrec.next = rec.next; + if (tdb_write(tdb, last_ptr, (char *)&lastrec, + sizeof(lastrec)) == -1) { + goto fail; + } + } + + /* all done - return the new record offset */ +#if TDB_DEBUG + printf("allocated %u bytes in database\n", rec.rec_len); +#endif + return rec_ptr; + } + + /* move to the next record */ + lastrec = rec; + last_ptr = rec_ptr; + rec_ptr = rec.next; + } + + /* we didn't find enough space. See if we can expand the database and if we can + then try again */ + if (tdb_expand(tdb, length + sizeof(rec)) == 0) goto again; + + fail: +#if TDB_DEBUG + printf("tdb_allocate failed for size %u\n", length); +#endif + return 0; +} + +/* initialise a new database with a specified hash size */ +static int tdb_new_database(TDB_CONTEXT *tdb, int hash_size) +{ + struct tdb_header header; + tdb_off offset; + int i; + + /* create the header */ + header.version = TDB_VERSION; + header.hash_size = hash_size; + if (write(tdb->fd, &header, sizeof(header)) != sizeof(header)) return -1; + + /* the freelist and hash pointers */ + offset = 0; + for (i=0;i<hash_size+1;i++) { + if (write(tdb->fd, &offset, sizeof(tdb_off)) != sizeof(tdb_off)) return -1; + } + +#if TDB_DEBUG + printf("initialised database of hash_size %u available space %u\n", + hash_size, rec.rec_len); +#endif + return 0; +} + + +/* update an entry in place - this only works if the new data size + is <= the old data size and the key exists. + on failure return -1 +*/ +int tdb_update(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf) +{ + unsigned hash; + tdb_off offset, rec_ptr; + struct list_struct rec; + char *data=NULL; + + /* find which hash bucket it is in */ + hash = tdb_hash(&key); + + /* find the top of the hash chain */ + offset = tdb_hash_top(tdb, hash); + + /* read in the hash top */ + if (tdb_read(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) { + goto fail; + } + + /* keep looking until we find the right record */ + while (rec_ptr) { + if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + goto fail; + } + + if (hash == rec.full_hash && key.dsize == rec.key_len) { + /* a very likely hit - read the full key */ + data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), + rec.key_len); + if (!data) goto fail; + + if (memcmp(key.dptr, data, key.dsize) == 0) { + /* definate hit */ + if (rec.rec_len < key.dsize + dbuf.dsize) { + /* the update won't fit! */ + goto fail; + } + if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len, + dbuf.dptr, dbuf.dsize) == -1) { + goto fail; + } + if (dbuf.dsize != rec.data_len) { + rec.data_len = dbuf.dsize; + if (tdb_write(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + goto fail; + } + } + free(data); + return 0; + } + + /* a miss - drat */ + free(data); + data = NULL; + } + + /* move to the next record */ + rec_ptr = rec.next; + } + + /* we didn't find it */ + fail: + if (data) free(data); + return -1; +} + + +/* find an entry in the database given a key */ +TDB_DATA tdb_fetch(TDB_CONTEXT *tdb, TDB_DATA key) +{ + unsigned hash; + tdb_off offset, rec_ptr; + struct list_struct rec; + char *data; + TDB_DATA ret; + + /* find which hash bucket it is in */ + hash = tdb_hash(&key); + + /* find the top of the hash chain */ + offset = tdb_hash_top(tdb, hash); + + /* read in the hash top */ + if (tdb_read(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) { + return null_data; + } + + /* keep looking until we find the right record */ + while (rec_ptr) { + if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + return null_data; + } + + if (hash == rec.full_hash && key.dsize == rec.key_len) { + /* a very likely hit - read the full record */ + data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), + rec.key_len + rec.data_len); + if (!data) { + return null_data; + } + + if (memcmp(key.dptr, data, key.dsize) == 0) { + /* a definate match */ + ret.dptr = (char *)memdup(data + rec.key_len, rec.data_len); + ret.dsize = rec.data_len; + free(data); + return ret; + } + + /* a miss - drat */ + free(data); + } + + /* move to the next record */ + rec_ptr = rec.next; + } + + /* we didn't find it */ + return null_data; +} + +/* check if an entry in the database exists + + note that 1 is returned if the key is found and 0 is returned if not found + this doesn't match the conventions in the rest of this module, but is + compatible with gdbm +*/ +int tdb_exists(TDB_CONTEXT *tdb, TDB_DATA key) +{ + unsigned hash; + tdb_off offset, rec_ptr; + struct list_struct rec; + char *data; + + /* find which hash bucket it is in */ + hash = tdb_hash(&key); + + /* find the top of the hash chain */ + offset = tdb_hash_top(tdb, hash); + + /* read in the hash top */ + if (tdb_read(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) { + return 0; + } + + /* keep looking until we find the right record */ + while (rec_ptr) { + if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + return 0; + } + + if (hash == rec.full_hash && key.dsize == rec.key_len) { + /* a very likely hit - read the full record */ + data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), + rec.key_len + rec.data_len); + if (!data) { + return 0; + } + + if (memcmp(key.dptr, data, key.dsize) == 0) { + /* a definate match */ + free(data); + return 1; + } + + /* a miss - drat */ + free(data); + } + + /* move to the next record */ + rec_ptr = rec.next; + } + + /* we didn't find it */ + return 0; +} + + +/* traverse the entire database - calling fn(tdb, key, data) on each element. + return -1 on error or the record count traversed + a non-zero return value from fn() indicates that the traversal should stop + */ +int tdb_traverse(TDB_CONTEXT *tdb, int (*fn)(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf)) +{ + int count = 0; + unsigned h; + tdb_off offset, rec_ptr; + struct list_struct rec; + char *data; + TDB_DATA key, dbuf; + + /* loop over all hash chains */ + for (h = 0; h < tdb->header.hash_size; h++) { + /* read in the hash top */ + offset = tdb_hash_top(tdb, h); + if (tdb_read(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) { + return -1; + } + + /* traverse all records for this hash */ + while (rec_ptr) { + if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + return -1; + } + + /* now read the full record */ + data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), + rec.key_len + rec.data_len); + if (!data) { + return -1; + } + + key.dptr = data; + key.dsize = rec.key_len; + dbuf.dptr = data + rec.key_len; + dbuf.dsize = rec.data_len; + count++; + + if (fn(tdb, key, dbuf) != 0) { + /* they want us to stop traversing */ + free(data); + return count; + } + + /* a miss - drat */ + free(data); + + /* move to the next record */ + rec_ptr = rec.next; + } + + } + + /* return the number traversed */ + return count; +} + + +/* find the first entry in the database and return its key */ +TDB_DATA tdb_firstkey(TDB_CONTEXT *tdb) +{ + tdb_off offset, rec_ptr; + struct list_struct rec; + unsigned hash; + TDB_DATA ret; + + /* look for a non-empty hash chain */ + for (hash = 0, rec_ptr = 0; + hash < tdb->header.hash_size && rec_ptr == 0; + hash++) { + /* find the top of the hash chain */ + offset = tdb_hash_top(tdb, hash); + + /* read in the hash top */ + if (tdb_read(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) { + return null_data; + } + } + + if (rec_ptr == 0) return null_data; + + /* we've found a non-empty chain, now read the record */ + if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + return null_data; + } + + /* allocate and read the key space */ + ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), rec.key_len); + ret.dsize = rec.key_len; + + return ret; +} + +/* find the next entry in the database, returning its key */ +TDB_DATA tdb_nextkey(TDB_CONTEXT *tdb, TDB_DATA key) +{ + unsigned hash, h; + tdb_off offset, rec_ptr; + struct list_struct rec; + char *data; + TDB_DATA ret; + + /* find which hash bucket it is in */ + hash = tdb_hash(&key); + + /* find the top of the hash chain */ + offset = tdb_hash_top(tdb, hash); + + /* read in the hash top */ + if (tdb_read(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) { + return null_data; + } + + /* look until we find the right record */ + while (rec_ptr) { + if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + return null_data; + } + + if (hash == rec.full_hash && key.dsize == rec.key_len) { + /* a very likely hit - read the full key */ + data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), + rec.key_len); + if (!data) { + return null_data; + } + + if (memcmp(key.dptr, data, key.dsize) == 0) { + /* a definate match - we want the next + record after this one */ + rec_ptr = rec.next; + free(data); + if (rec_ptr == 0) goto next_hash; + goto found_record; + } + + /* a miss - drat */ + free(data); + } + + /* move to the next record */ + rec_ptr = rec.next; + } + + next_hash: +#if TDB_DEBUG + printf("tdb_nextkey trying next hash from %u\n", + hash % tdb->header.hash_size); +#endif + + h = hash % tdb->header.hash_size; + if (h == tdb->header.hash_size - 1) return null_data; + + /* look for a non-empty hash chain */ + for (h = h+1, rec_ptr = 0; + h < tdb->header.hash_size && rec_ptr == 0; + h++) { +#if TDB_DEBUG + printf("tdb_nextkey trying bucket %u\n",h); +#endif + /* find the top of the hash chain */ + offset = tdb_hash_top(tdb, h); + + /* read in the hash top */ + if (tdb_read(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) { + return null_data; + } + } + + if (rec_ptr == 0) return null_data; + + found_record: + + /* we've found a non-empty chain, now read the record */ + if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + return null_data; + } + +#if TDB_DEBUG + printf("tdb_nextkey found hash 0x%08x in bucket %u from bucket %u\n", + rec.full_hash, rec.full_hash % tdb->header.hash_size, + hash % tdb->header.hash_size); +#endif + /* allocate and read the key space */ + ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), rec.key_len); + ret.dsize = rec.key_len; + + return ret; +} + +/* delete an entry in the database given a key */ +int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key) +{ + unsigned hash; + tdb_off offset, rec_ptr, last_ptr; + struct list_struct rec, lastrec; + char *data; + + tdb_writelock(tdb); + + /* find which hash bucket it is in */ + hash = tdb_hash(&key); + + /* find the top of the hash chain */ + offset = tdb_hash_top(tdb, hash); + + /* read in the hash top */ + if (tdb_read(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) { + goto fail; + } + + last_ptr = 0; + + /* keep looking until we find the right record */ + while (rec_ptr) { + if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + goto fail; + } + + if (hash == rec.full_hash && key.dsize == rec.key_len) { + /* a very likely hit - read the record and full key */ + data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), + rec.key_len); + if (!data) { + goto fail; + } + + if (memcmp(key.dptr, data, key.dsize) == 0) { + /* a definate match - delete it */ +#if TDB_DEBUG + printf("deleting record with hash 0x%08x in bucket %u\n", + hash, hash % tdb->header.hash_size); +#endif + if (last_ptr == 0) { + offset = tdb_hash_top(tdb, hash); + if (tdb_write(tdb, offset, (char *)&rec.next, sizeof(rec.next)) == -1) { + goto fail; + } + } else { + lastrec.next = rec.next; + if (tdb_write(tdb, last_ptr, (char *)&lastrec, sizeof(lastrec)) == -1) { + goto fail; + } + } + /* and recover the space */ + offset = FREELIST_TOP; + if (tdb_read(tdb, offset, (char *)&rec.next, sizeof(rec.next)) == -1) { + goto fail; + } + if (tdb_write(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + goto fail; + } + if (tdb_write(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) { + goto fail; + } + + /* yipee - all done */ + free(data); + tdb_writeunlock(tdb); + return 0; + } + + /* a miss - drat */ + free(data); + } + + /* move to the next record */ + last_ptr = rec_ptr; + lastrec = rec; + rec_ptr = rec.next; + } + + + fail: + tdb_writeunlock(tdb); + return -1; +} + + +/* store an element in the database, replacing any existing element + with the same key + + return 0 on success, -1 on failure +*/ +int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag) +{ + struct list_struct rec; + char *data = NULL; + unsigned hash; + tdb_off rec_ptr, offset; + + /* check for it existing */ + if (flag == TDB_INSERT && tdb_exists(tdb, key)) { + return -1; + } + + tdb_writelock(tdb); + + /* first try in-place update */ + if (flag != TDB_INSERT && tdb_update(tdb, key, dbuf) == 0) { + tdb_writeunlock(tdb); + return 0; + } + + /* delete any existing record - if it doesn't exist we don't care */ + if (flag != TDB_INSERT) { + tdb_delete(tdb, key); + } + + /* find which hash bucket it is in */ + hash = tdb_hash(&key); + + rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize); + if (rec_ptr == 0) { + goto fail; + } + + /* read the newly created record */ + if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) { + goto fail; + } + + /* find the top of the hash chain */ + offset = tdb_hash_top(tdb, hash); + + /* read in the hash top diretcly into our next pointer */ + if (tdb_read(tdb, offset, (char *)&rec.next, sizeof(rec.next)) == -1) { + goto fail; + } + + rec.key_len = key.dsize; + rec.data_len = dbuf.dsize; + rec.full_hash = hash; + + /* write the new record */ + if (tdb_write(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) goto fail; + if (tdb_write(tdb, rec_ptr + sizeof(rec), key.dptr, key.dsize) == -1) goto fail; + if (tdb_write(tdb, rec_ptr + sizeof(rec) + key.dsize, dbuf.dptr, dbuf.dsize) == -1) goto fail; + + /* and point the top of the hash chain at it */ + if (tdb_write(tdb, offset, (char *)&rec_ptr, sizeof(rec_ptr)) == -1) goto fail; + + tdb_writeunlock(tdb); +#if TDB_DEBUG + printf("added record with hash 0x%08x in bucket %u\n", hash, hash % tdb->header.hash_size); +#endif + return 0; + + fail: +#if TDB_DEBUG + printf("store failed for hash 0x%08x in bucket %u\n", hash, hash % tdb->header.hash_size); +#endif + if (data) free(data); + tdb_writeunlock(tdb); + return -1; +} + + +/* open the database, creating it if necessary + + The flags and mode are passed straight to the open call on the database + file. A flags value of O_WRONLY is invalid + + The hash size is advisory, use zero for a default value. + + return is NULL on error +*/ +TDB_CONTEXT *tdb_open(char *name, int hash_size, int flags, mode_t mode) +{ + TDB_CONTEXT tdb, *ret; + struct tdb_header header; + struct stat st; + + tdb.fd = -1; + tdb.name = NULL; + tdb.map_ptr = NULL; + + if ((flags & O_ACCMODE) == O_WRONLY) goto fail; + + if (hash_size == 0) hash_size = DEFAULT_HASH_SIZE; + + tdb.fd = open(name, flags, mode); + if (tdb.fd == -1) goto fail; + + if (read(tdb.fd, &header, sizeof(header)) != sizeof(header) || + header.version != TDB_VERSION) { + /* its not a valid database - possibly initialise it */ + if (!(flags & O_CREAT)) { + goto fail; + } + if (tdb_new_database(&tdb, hash_size) == -1) goto fail; + + lseek(tdb.fd, 0, SEEK_SET); + if (read(tdb.fd, &header, sizeof(header)) != sizeof(header)) goto fail; + } + + fstat(tdb.fd, &st); + + /* map the database and fill in the return structure */ + tdb.name = (char *)strdup(name); + tdb.map_size = st.st_size; +#if HAVE_MMAP + tdb.map_ptr = (void *)mmap(NULL, st.st_size, + (flags & O_ACCMODE) == O_RDONLY? PROT_READ : PROT_READ|PROT_WRITE, + MAP_SHARED | MAP_FILE, tdb.fd, 0); +#endif + tdb.header = header; + + ret = (TDB_CONTEXT *)malloc(sizeof(tdb)); + if (!ret) goto fail; + + *ret = tdb; + +#if TDB_DEBUG + printf("mapped database of hash_size %u map_size=%u\n", + hash_size, db.map_size); +#endif + + return ret; + + fail: + if (tdb.name) free(tdb.name); + if (tdb.fd != -1) close(tdb.fd); + if (tdb.map_ptr) munmap(tdb.map_ptr, tdb.map_size); + + return NULL; +} + +/* close a database */ +int tdb_close(TDB_CONTEXT *tdb) +{ + if (!tdb) return -1; + + if (tdb->name) free(tdb->name); + if (tdb->fd != -1) close(tdb->fd); + if (tdb->map_ptr) munmap(tdb->map_ptr, tdb->map_size); + + memset(tdb, 0, sizeof(*tdb)); + free(tdb); + + return 0; +} + +/* lock the database. If we already have it locked then don't do anything */ +int tdb_writelock(TDB_CONTEXT *tdb) +{ +#if !NOLOCK + struct flock fl; + + if (tdb->write_locked) return 0; + + fl.l_type = F_WRLCK; + fl.l_whence = SEEK_SET; + fl.l_start = 0; + fl.l_len = 1; + fl.l_pid = 0; + + if (fcntl(tdb->fd, F_SETLKW, &fl) != 0) return -1; + + tdb->write_locked = 1; +#endif + return 0; +} + +/* unlock the database. If we don't have it locked then return -1 */ +int tdb_writeunlock(TDB_CONTEXT *tdb) +{ +#if !NOLOCK + struct flock fl; + + if (!tdb->write_locked) return -1; + + fl.l_type = F_UNLCK; + fl.l_whence = SEEK_SET; + fl.l_start = 0; + fl.l_len = 1; + fl.l_pid = 0; + + if (fcntl(tdb->fd, F_SETLK, &fl) != 0) return -1; + + tdb->write_locked = 0; +#endif + return 0; +} + diff --git a/source3/tdb/tdb.h b/source3/tdb/tdb.h new file mode 100644 index 0000000000..316338606b --- /dev/null +++ b/source3/tdb/tdb.h @@ -0,0 +1,61 @@ +/* + Unix SMB/Netbios implementation. + Version 3.0 + Samba database functions + Copyright (C) Andrew Tridgell 1999 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + 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 + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. +*/ + +typedef unsigned tdb_len; +typedef unsigned tdb_off; + +/* this is stored at the front of every database */ +struct tdb_header { + unsigned version; /* version of the code */ + unsigned hash_size; /* number of hash entries */ +}; + +typedef struct { + char *dptr; + size_t dsize; +} TDB_DATA; + +/* this is the context structure that is returned from a db open */ +typedef struct { + char *name; /* the name of the database */ + void *map_ptr; /* where it is currently mapped */ + int fd; /* open file descriptor for the database */ + tdb_len map_size; /* how much space has been mapped */ + int write_locked; /* set if we have the db locked */ + struct tdb_header header; /* a cached copy of the header */ +} TDB_CONTEXT; + +#define TDB_REPLACE 1 +#define TDB_INSERT 2 + +#if STANDALONE +int tdb_writelock(TDB_CONTEXT *tdb); +int tdb_writeunlock(TDB_CONTEXT *tdb); +TDB_DATA tdb_fetch(TDB_CONTEXT *tdb, TDB_DATA key); +int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key); +int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag); +TDB_CONTEXT *tdb_open(char *name, int hash_size, int flags, mode_t mode); +int tdb_close(TDB_CONTEXT *tdb); +TDB_DATA tdb_firstkey(TDB_CONTEXT *tdb); +TDB_DATA tdb_nextkey(TDB_CONTEXT *tdb, TDB_DATA key); +int tdb_traverse(TDB_CONTEXT *tdb, int (*fn)(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf)); +int tdb_exists(TDB_CONTEXT *tdb, TDB_DATA key); +#endif diff --git a/source3/tdb/tdbtest.c b/source3/tdb/tdbtest.c new file mode 100644 index 0000000000..39dd5ff93b --- /dev/null +++ b/source3/tdb/tdbtest.c @@ -0,0 +1,217 @@ +#include <stdlib.h> +#include <stdio.h> +#include <fcntl.h> +#include <unistd.h> +#include <string.h> +#include <fcntl.h> +#include <sys/mman.h> +#include <sys/stat.h> +#include <sys/time.h> +#include "tdb.h" +#include <gdbm.h> + +/* a test program for tdb - the trivial database */ + + + +#define DELETE_PROB 7 +#define STORE_PROB 5 + +static TDB_CONTEXT *db; +static GDBM_FILE gdbm; + +struct timeval tp1,tp2; + +static void start_timer() +{ + gettimeofday(&tp1,NULL); +} + +static double end_timer() +{ + gettimeofday(&tp2,NULL); + return((tp2.tv_sec - tp1.tv_sec) + + (tp2.tv_usec - tp1.tv_usec)*1.0e-6); +} + +static void fatal(char *why) +{ + perror(why); + exit(1); +} + + +static void compare_db(void) +{ + TDB_DATA d, key, nextkey; + datum gd, gkey, gnextkey; + + key = tdb_firstkey(db); + while (key.dptr) { + d = tdb_fetch(db, key); + gkey.dptr = key.dptr; + gkey.dsize = key.dsize; + + gd = gdbm_fetch(gdbm, gkey); + + if (!gd.dptr) fatal("key not in gdbm"); + if (gd.dsize != d.dsize) fatal("data sizes differ"); + if (memcmp(gd.dptr, d.dptr, d.dsize)) { + fatal("data differs"); + } + + nextkey = tdb_nextkey(db, key); + free(key.dptr); + free(d.dptr); + free(gd.dptr); + key = nextkey; + } + + gkey = gdbm_firstkey(gdbm); + while (gkey.dptr) { + gd = gdbm_fetch(gdbm, gkey); + key.dptr = gkey.dptr; + key.dsize = gkey.dsize; + + d = tdb_fetch(db, key); + + if (!d.dptr) fatal("key not in db"); + if (d.dsize != gd.dsize) fatal("data sizes differ"); + if (memcmp(d.dptr, gd.dptr, gd.dsize)) { + fatal("data differs"); + } + + gnextkey = gdbm_nextkey(gdbm, gkey); + free(gkey.dptr); + free(gd.dptr); + free(d.dptr); + gkey = gnextkey; + } +} + +static char *randbuf(int len) +{ + char *buf; + int i; + buf = (char *)malloc(len+1); + + for (i=0;i<len;i++) { + buf[i] = 'a' + (rand() % 26); + } + buf[i] = 0; + return buf; +} + +static void addrec_db(void) +{ + int klen, dlen; + char *k, *d; + TDB_DATA key, data; + + klen = 1 + (rand() % 4); + dlen = 1 + (rand() % 100); + + k = randbuf(klen); + d = randbuf(dlen); + + key.dptr = k; + key.dsize = klen+1; + + data.dptr = d; + data.dsize = dlen+1; + + if (rand() % DELETE_PROB == 0) { + tdb_delete(db, key); + } else if (rand() % STORE_PROB == 0) { + if (tdb_store(db, key, data, TDB_REPLACE) != 0) { + fatal("tdb_store failed"); + } + } else { + data = tdb_fetch(db, key); + if (data.dptr) free(data.dptr); + } + + free(k); + free(d); +} + +static void addrec_gdbm(void) +{ + int klen, dlen; + char *k, *d; + datum key, data; + + klen = 1 + (rand() % 4); + dlen = 1 + (rand() % 100); + + k = randbuf(klen); + d = randbuf(dlen); + + key.dptr = k; + key.dsize = klen+1; + + data.dptr = d; + data.dsize = dlen+1; + + if (rand() % DELETE_PROB == 0) { + gdbm_delete(gdbm, key); + } else if (rand() % STORE_PROB == 0) { + if (gdbm_store(gdbm, key, data, GDBM_REPLACE) != 0) { + fatal("gdbm_store failed"); + } + } else { + data = gdbm_fetch(gdbm, key); + if (data.dptr) free(data.dptr); + } + + free(k); + free(d); +} + +static int traverse_fn(TDB_CONTEXT *db, TDB_DATA key, TDB_DATA dbuf) +{ +#if 0 + printf("[%s] [%s]\n", key.dptr, dbuf.dptr); +#endif + tdb_delete(db, key); + return 0; +} + +int main(int argc, char *argv[]) +{ + int i, seed=0; + int loops = 50000; + + unlink("test.gdbm"); + + db = tdb_open("test.db", 0, O_RDWR | O_CREAT | O_TRUNC, 0600); + gdbm = gdbm_open("test.gdbm", 512, GDBM_WRITER|GDBM_NEWDB|GDBM_FAST, + 0600, NULL); + + if (!db || !gdbm) { + fatal("db open failed"); + } + + +#if 1 + srand(seed); + start_timer(); + for (i=0;i<loops;i++) addrec_gdbm(); + printf("gdbm took %g secs\n", end_timer()); +#endif + + srand(seed); + start_timer(); + for (i=0;i<loops;i++) addrec_db(); + printf("tdb took %g secs\n", end_timer()); + + compare_db(); + + printf("traversed %d records\n", tdb_traverse(db, traverse_fn)); + printf("traversed %d records\n", tdb_traverse(db, traverse_fn)); + + tdb_close(db); + gdbm_close(gdbm); + + return 0; +} diff --git a/source3/tdb/tdbtool.c b/source3/tdb/tdbtool.c new file mode 100644 index 0000000000..766ce0ff47 --- /dev/null +++ b/source3/tdb/tdbtool.c @@ -0,0 +1,206 @@ +#include <stdlib.h> +#include <stdio.h> +#include <fcntl.h> +#include <unistd.h> +#include <string.h> +#include <fcntl.h> +#include <sys/mman.h> +#include <sys/stat.h> +#include <sys/time.h> +#include <readline/readline.h> +#include <readline/history.h> +#include "tdb.h" + +/* a tdb tool for manipulating a tdb database */ + +static TDB_CONTEXT *tdb; + +static void help(void) +{ + printf(" +tdbtool: + create dbname : create a database + open dbname : open an existing database + erase : erase the database + dump : dump the database as strings + insert key data : insert a record + store key data : store a record (replace) + show key : show a record by key + delete key : delete a record by key +"); +} + +static void terror(char *why) +{ + printf("%s\n", why); +} + +static void create_tdb(void) +{ + char *tok = strtok(NULL, " "); + if (!tok) { + help(); + return; + } + if (tdb) tdb_close(tdb); + tdb = tdb_open(tok, 0, O_RDWR | O_CREAT | O_TRUNC, 0600); +} + +static void open_tdb(void) +{ + char *tok = strtok(NULL, " "); + if (!tok) { + help(); + return; + } + if (tdb) tdb_close(tdb); + tdb = tdb_open(tok, 0, O_RDWR, 0600); +} + +static void insert_tdb(void) +{ + char *k = strtok(NULL, " "); + char *d = strtok(NULL, " "); + TDB_DATA key, dbuf; + + if (!k || !d) { + help(); + return; + } + + key.dptr = k; + key.dsize = strlen(k); + dbuf.dptr = d; + dbuf.dsize = strlen(d); + + if (tdb_store(tdb, key, dbuf, TDB_INSERT) == -1) { + terror("insert failed"); + } +} + +static void store_tdb(void) +{ + char *k = strtok(NULL, " "); + char *d = strtok(NULL, " "); + TDB_DATA key, dbuf; + + if (!k || !d) { + help(); + return; + } + + key.dptr = k; + key.dsize = strlen(k); + dbuf.dptr = d; + dbuf.dsize = strlen(d); + + if (tdb_store(tdb, key, dbuf, TDB_REPLACE) == -1) { + terror("store failed"); + } +} + +static void show_tdb(void) +{ + char *k = strtok(NULL, " "); + TDB_DATA key, dbuf; + + if (!k) { + help(); + return; + } + + key.dptr = k; + key.dsize = strlen(k); + + dbuf = tdb_fetch(tdb, key); + if (!dbuf.dptr) terror("fetch failed"); + printf("%s : %*.*s\n", k, (int)dbuf.dsize, (int)dbuf.dsize, dbuf.dptr); +} + +static void delete_tdb(void) +{ + char *k = strtok(NULL, " "); + TDB_DATA key; + + if (!k) { + help(); + return; + } + + key.dptr = k; + key.dsize = strlen(k); + + if (tdb_delete(tdb, key) != 0) { + terror("delete failed"); + } +} + +static int print_rec(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf) +{ + printf("%*.*s : %*.*s\n", + (int)key.dsize, (int)key.dsize, key.dptr, + (int)dbuf.dsize, (int)dbuf.dsize, dbuf.dptr); + return 0; +} + +static int total_bytes; + +static int traverse_fn(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf) +{ + total_bytes += dbuf.dsize; + return 0; +} + +static void info_tdb(void) +{ + int count; + total_bytes = 0; + count = tdb_traverse(tdb, traverse_fn); + printf("%d records totalling %d bytes\n", count, total_bytes); +} + +int main(int argc, char *argv[]) +{ + char *line; + char *tok; + + while ((line=readline("tdb> "))) { + tok = strtok(line," "); + if (strcmp(tok,"create") == 0) { + create_tdb(); + continue; + } else if (strcmp(tok,"open") == 0) { + open_tdb(); + continue; + } + + /* all the rest require a open database */ + if (!tdb) { + terror("database not open"); + help(); + continue; + } + + if (strcmp(tok,"insert") == 0) { + insert_tdb(); + } else if (strcmp(tok,"store") == 0) { + store_tdb(); + } else if (strcmp(tok,"show") == 0) { + show_tdb(); + } else if (strcmp(tok,"erase") == 0) { + tdb_traverse(tdb, tdb_delete); + } else if (strcmp(tok,"delete") == 0) { + delete_tdb(); + } else if (strcmp(tok,"dump") == 0) { + tdb_traverse(tdb, print_rec); + } else if (strcmp(tok,"info") == 0) { + info_tdb(); + } else { + help(); + } + } + + if (tdb) tdb_close(tdb); + + return 0; +} |