From 0868b7c77d42efd5f361f605bfc0d8d46841db95 Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Fri, 16 Sep 2005 03:52:42 +0000 Subject: r10253: a fairly large tdb cleanup and re-organise. Nearly all of this change just involves splitting up the core tdb.c code into separate files on logical boundaries, but there are some minor functional changes as well: - move the 'struct tdb_context' into tdb_private.h, hiding it from users. This was done to allow the structure to change without breaking code that uses tdb. - added accessor functions tdb_fd(), tdb_name(), and tdb_log_fn() to access the elements of struct tdb_context that were used by external code but are no longer visible - simplied tdb_append() to use tdb_fetch()/tdb_store(), which is just as good due to the way tdb locks work - changed some of the types (such as tdb_off to tdb_off_t) to make syntax highlighting work better - removed the old optional spinlock code. It was a bad idea. - fixed a bug in tdb_reopen_all() that caused tdbtorture to sometimes fail or report nasty looking errors. This is the only real bug fixed in this commit. Jeremy/Jerry, you might like to pickup this change for Samba3, as that could definately affect smbd in Samba3. The aim of all of these changes is to make the tdb transactions/journaling code I am working on easier to write. I started to write it on top of the existing tdb.c code and it got very messy. Splitting up the code makes it much easier to follow. There are more cleanups we could do in tdb, such as using uint32_t instead of u32 (suggested by metze). I'll leave those for another day. (This used to be commit 4673cdd0d261614e707b72a7a348bb0e7dbb2482) --- source4/lib/tdb/common/freelist.c | 323 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 323 insertions(+) create mode 100644 source4/lib/tdb/common/freelist.c (limited to 'source4/lib/tdb/common/freelist.c') diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c new file mode 100644 index 0000000000..018b7bc298 --- /dev/null +++ b/source4/lib/tdb/common/freelist.c @@ -0,0 +1,323 @@ + /* + Unix SMB/CIFS implementation. + + trivial database library + + Copyright (C) Andrew Tridgell 1999-2005 + Copyright (C) Paul `Rusty' Russell 2000 + Copyright (C) Jeremy Allison 2000-2003 + + ** NOTE! The following LGPL license applies to the tdb + ** library. This does NOT imply that all of Samba is released + ** under the LGPL + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ + +#include "tdb_private.h" + +/* read a freelist record and check for simple errors */ +static int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec) +{ + if (tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1) + return -1; + + if (rec->magic == TDB_MAGIC) { + /* this happens when a app is showdown while deleting a record - we should + not completely fail when this happens */ + TDB_LOG((tdb, 0,"rec_free_read non-free magic 0x%x at offset=%d - fixing\n", + rec->magic, off)); + rec->magic = TDB_FREE_MAGIC; + if (tdb_write(tdb, off, rec, sizeof(*rec)) == -1) + return -1; + } + + if (rec->magic != TDB_FREE_MAGIC) { + /* Ensure ecode is set for log fn. */ + tdb->ecode = TDB_ERR_CORRUPT; + TDB_LOG((tdb, 0,"rec_free_read bad magic 0x%x at offset=%d\n", + rec->magic, off)); + return TDB_ERRCODE(TDB_ERR_CORRUPT, -1); + } + if (tdb_oob(tdb, rec->next+sizeof(*rec), 0) != 0) + return -1; + return 0; +} + + + +/* Remove an element from the freelist. Must have alloc lock. */ +static int remove_from_freelist(struct tdb_context *tdb, tdb_off_t off, tdb_off_t next) +{ + tdb_off_t last_ptr, i; + + /* read in the freelist top */ + last_ptr = FREELIST_TOP; + while (tdb_ofs_read(tdb, last_ptr, &i) != -1 && i != 0) { + if (i == off) { + /* We've found it! */ + return tdb_ofs_write(tdb, last_ptr, &next); + } + /* Follow chain (next offset is at start of record) */ + last_ptr = i; + } + TDB_LOG((tdb, 0,"remove_from_freelist: not on list at off=%d\n", off)); + return TDB_ERRCODE(TDB_ERR_CORRUPT, -1); +} + + +/* update a record tailer (must hold allocation lock) */ +static int update_tailer(struct tdb_context *tdb, tdb_off_t offset, + const struct list_struct *rec) +{ + tdb_off_t totalsize; + + /* Offset of tailer from record header */ + totalsize = sizeof(*rec) + rec->rec_len; + return tdb_ofs_write(tdb, offset + totalsize - sizeof(tdb_off_t), + &totalsize); +} + +/* Add an element into the freelist. Merge adjacent records if + neccessary. */ +int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec) +{ + tdb_off_t right, left; + + /* Allocation and tailer lock */ + if (tdb_lock(tdb, -1, F_WRLCK) != 0) + return -1; + + /* set an initial tailer, so if we fail we don't leave a bogus record */ + if (update_tailer(tdb, offset, rec) != 0) { + TDB_LOG((tdb, 0, "tdb_free: upfate_tailer failed!\n")); + goto fail; + } + + /* Look right first (I'm an Australian, dammit) */ + right = offset + sizeof(*rec) + rec->rec_len; + if (right + sizeof(*rec) <= tdb->map_size) { + struct list_struct r; + + if (tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) { + TDB_LOG((tdb, 0, "tdb_free: right read failed at %u\n", right)); + goto left; + } + + /* If it's free, expand to include it. */ + if (r.magic == TDB_FREE_MAGIC) { + if (remove_from_freelist(tdb, right, r.next) == -1) { + TDB_LOG((tdb, 0, "tdb_free: right free failed at %u\n", right)); + goto left; + } + rec->rec_len += sizeof(r) + r.rec_len; + } + } + +left: + /* Look left */ + left = offset - sizeof(tdb_off_t); + if (left > TDB_DATA_START(tdb->header.hash_size)) { + struct list_struct l; + tdb_off_t leftsize; + + /* Read in tailer and jump back to header */ + if (tdb_ofs_read(tdb, left, &leftsize) == -1) { + TDB_LOG((tdb, 0, "tdb_free: left offset read failed at %u\n", left)); + goto update; + } + left = offset - leftsize; + + /* Now read in record */ + if (tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) { + TDB_LOG((tdb, 0, "tdb_free: left read failed at %u (%u)\n", left, leftsize)); + goto update; + } + + /* If it's free, expand to include it. */ + if (l.magic == TDB_FREE_MAGIC) { + if (remove_from_freelist(tdb, left, l.next) == -1) { + TDB_LOG((tdb, 0, "tdb_free: left free failed at %u\n", left)); + goto update; + } else { + offset = left; + rec->rec_len += leftsize; + } + } + } + +update: + if (update_tailer(tdb, offset, rec) == -1) { + TDB_LOG((tdb, 0, "tdb_free: update_tailer failed at %u\n", offset)); + goto fail; + } + + /* Now, prepend to free list */ + rec->magic = TDB_FREE_MAGIC; + + if (tdb_ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 || + tdb_rec_write(tdb, offset, rec) == -1 || + tdb_ofs_write(tdb, FREELIST_TOP, &offset) == -1) { + TDB_LOG((tdb, 0, "tdb_free record write failed at offset=%d\n", offset)); + goto fail; + } + + /* And we're done. */ + tdb_unlock(tdb, -1, F_WRLCK); + return 0; + + fail: + tdb_unlock(tdb, -1, F_WRLCK); + return -1; +} + + +/* + the core of tdb_allocate - called when we have decided which + free list entry to use + */ +static tdb_off_t tdb_allocate_ofs(struct tdb_context *tdb, tdb_len_t length, tdb_off_t rec_ptr, + struct list_struct *rec, tdb_off_t last_ptr) +{ + struct list_struct newrec; + tdb_off_t newrec_ptr; + + memset(&newrec, '\0', sizeof(newrec)); + + /* found it - now possibly split it up */ + if (rec->rec_len > length + MIN_REC_SIZE) { + /* Length of left piece */ + length = TDB_ALIGN(length, TDB_ALIGNMENT); + + /* Right piece to go on free list */ + newrec.rec_len = rec->rec_len - (sizeof(*rec) + length); + newrec_ptr = rec_ptr + sizeof(*rec) + length; + + /* And left record is shortened */ + rec->rec_len = length; + } else { + newrec_ptr = 0; + } + + /* Remove allocated record from the free list */ + if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1) { + return 0; + } + + /* Update header: do this before we drop alloc + lock, otherwise tdb_free() might try to + merge with us, thinking we're free. + (Thanks Jeremy Allison). */ + rec->magic = TDB_MAGIC; + if (tdb_rec_write(tdb, rec_ptr, rec) == -1) { + return 0; + } + + /* Did we create new block? */ + if (newrec_ptr) { + /* Update allocated record tailer (we + shortened it). */ + if (update_tailer(tdb, rec_ptr, rec) == -1) { + return 0; + } + + /* Free new record */ + if (tdb_free(tdb, newrec_ptr, &newrec) == -1) { + return 0; + } + } + + /* all done - return the new record offset */ + return rec_ptr; +} + +/* 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 + */ +tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_struct *rec) +{ + tdb_off_t rec_ptr, last_ptr, newrec_ptr; + struct { + tdb_off_t rec_ptr, last_ptr; + tdb_len_t rec_len; + } bestfit; + + if (tdb_lock(tdb, -1, F_WRLCK) == -1) + return 0; + + /* Extra bytes required for tailer */ + length += sizeof(tdb_off_t); + + again: + last_ptr = FREELIST_TOP; + + /* read in the freelist top */ + if (tdb_ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1) + goto fail; + + bestfit.rec_ptr = 0; + + /* + this is a best fit allocation strategy. Originally we used + a first fit strategy, but it suffered from massive fragmentation + issues when faced with a slowly increasing record size. + */ + while (rec_ptr) { + if (rec_free_read(tdb, rec_ptr, rec) == -1) { + goto fail; + } + + if (rec->rec_len >= length) { + if (bestfit.rec_ptr == 0 || + rec->rec_len < bestfit.rec_len) { + bestfit.rec_len = rec->rec_len; + bestfit.rec_ptr = rec_ptr; + bestfit.last_ptr = last_ptr; + /* consider a fit to be good enough if + we aren't wasting more than half + the space */ + if (bestfit.rec_len < 2*length) { + break; + } + } + } + + /* move to the next record */ + last_ptr = rec_ptr; + rec_ptr = rec->next; + } + + if (bestfit.rec_ptr != 0) { + if (rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) { + goto fail; + } + + newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr, rec, bestfit.last_ptr); + tdb_unlock(tdb, -1, F_WRLCK); + return newrec_ptr; + } + + /* 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: + tdb_unlock(tdb, -1, F_WRLCK); + return 0; +} + -- cgit From ede8415d61b6791114c65de1c283a4e8c11f1585 Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Thu, 22 Sep 2005 03:56:41 +0000 Subject: r10405: added transactions into tdb, and hook them into ldb. See my samba-technical posting for more details on the transactions design. This also adds a number of command line arguments to tdbtorture, making it more flexible, and fixes some lock deadlock conditions in the tdbtorture code. (This used to be commit 06bd8abba942ec9f1e23f5c5d546cbb71ca3a701) --- source4/lib/tdb/common/freelist.c | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) (limited to 'source4/lib/tdb/common/freelist.c') diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c index 018b7bc298..9707295ec3 100644 --- a/source4/lib/tdb/common/freelist.c +++ b/source4/lib/tdb/common/freelist.c @@ -31,7 +31,7 @@ /* read a freelist record and check for simple errors */ static int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec) { - if (tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1) + if (tdb->methods->tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1) return -1; if (rec->magic == TDB_MAGIC) { @@ -40,7 +40,7 @@ static int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_str TDB_LOG((tdb, 0,"rec_free_read non-free magic 0x%x at offset=%d - fixing\n", rec->magic, off)); rec->magic = TDB_FREE_MAGIC; - if (tdb_write(tdb, off, rec, sizeof(*rec)) == -1) + if (tdb->methods->tdb_write(tdb, off, rec, sizeof(*rec)) == -1) return -1; } @@ -51,7 +51,7 @@ static int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_str rec->magic, off)); return TDB_ERRCODE(TDB_ERR_CORRUPT, -1); } - if (tdb_oob(tdb, rec->next+sizeof(*rec), 0) != 0) + if (tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 0) != 0) return -1; return 0; } @@ -111,7 +111,7 @@ int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec) if (right + sizeof(*rec) <= tdb->map_size) { struct list_struct r; - if (tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) { + if (tdb->methods->tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) { TDB_LOG((tdb, 0, "tdb_free: right read failed at %u\n", right)); goto left; } @@ -138,10 +138,16 @@ left: TDB_LOG((tdb, 0, "tdb_free: left offset read failed at %u\n", left)); goto update; } + + /* it could be uninitialised data */ + if (leftsize == 0 || leftsize == TDB_PAD_U32) { + goto update; + } + left = offset - leftsize; /* Now read in record */ - if (tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) { + if (tdb->methods->tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) { TDB_LOG((tdb, 0, "tdb_free: left read failed at %u (%u)\n", left, leftsize)); goto update; } -- cgit From 6e99b959dedcd8da444fca04832011ffa744b619 Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Sat, 24 Sep 2005 23:52:30 +0000 Subject: r10483: fixed some uninitialised variables warnings (This used to be commit 315653cf1ecc11c435ee35b20e6cf9c73a67fa68) --- source4/lib/tdb/common/freelist.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'source4/lib/tdb/common/freelist.c') diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c index 9707295ec3..3483751164 100644 --- a/source4/lib/tdb/common/freelist.c +++ b/source4/lib/tdb/common/freelist.c @@ -277,6 +277,8 @@ tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_st goto fail; bestfit.rec_ptr = 0; + bestfit.last_ptr = 0; + bestfit.rec_len = 0; /* this is a best fit allocation strategy. Originally we used -- cgit From d3fee429aee87e9c05a4a606fbf0b60b16dac782 Mon Sep 17 00:00:00 2001 From: Andrew Bartlett Date: Mon, 3 Jul 2006 06:40:56 +0000 Subject: r16774: This patch modifies the tdb API to allow the logging function to be used as part of ldb. This allows tdb failures to be passed all the way up to Samba's DEBUG system, which allowed easier debugging. Unfortunately I had to extend the tdb API, as the logging function didn't have a context pointer. I've worked over the 'debug levels' in TDB. Most of them were 0, which didn't seem right, as some were trace-like messages. We didn't see any of these previously, except when accessing TDB directly. Andrew Bartlett (This used to be commit 58898092c1ce043f6d698db5065f372b79109e22) --- source4/lib/tdb/common/freelist.c | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) (limited to 'source4/lib/tdb/common/freelist.c') diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c index 3483751164..9d1ae59801 100644 --- a/source4/lib/tdb/common/freelist.c +++ b/source4/lib/tdb/common/freelist.c @@ -37,7 +37,7 @@ static int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_str if (rec->magic == TDB_MAGIC) { /* this happens when a app is showdown while deleting a record - we should not completely fail when this happens */ - TDB_LOG((tdb, 0,"rec_free_read non-free magic 0x%x at offset=%d - fixing\n", + TDB_LOG((tdb, TDB_DEBUG_WARNING, "rec_free_read non-free magic 0x%x at offset=%d - fixing\n", rec->magic, off)); rec->magic = TDB_FREE_MAGIC; if (tdb->methods->tdb_write(tdb, off, rec, sizeof(*rec)) == -1) @@ -47,7 +47,7 @@ static int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_str if (rec->magic != TDB_FREE_MAGIC) { /* Ensure ecode is set for log fn. */ tdb->ecode = TDB_ERR_CORRUPT; - TDB_LOG((tdb, 0,"rec_free_read bad magic 0x%x at offset=%d\n", + TDB_LOG((tdb, TDB_DEBUG_WARNING, "rec_free_read bad magic 0x%x at offset=%d\n", rec->magic, off)); return TDB_ERRCODE(TDB_ERR_CORRUPT, -1); } @@ -73,7 +73,7 @@ static int remove_from_freelist(struct tdb_context *tdb, tdb_off_t off, tdb_off_ /* Follow chain (next offset is at start of record) */ last_ptr = i; } - TDB_LOG((tdb, 0,"remove_from_freelist: not on list at off=%d\n", off)); + TDB_LOG((tdb, TDB_DEBUG_FATAL,"remove_from_freelist: not on list at off=%d\n", off)); return TDB_ERRCODE(TDB_ERR_CORRUPT, -1); } @@ -102,7 +102,7 @@ int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec) /* set an initial tailer, so if we fail we don't leave a bogus record */ if (update_tailer(tdb, offset, rec) != 0) { - TDB_LOG((tdb, 0, "tdb_free: upfate_tailer failed!\n")); + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed!\n")); goto fail; } @@ -112,14 +112,14 @@ int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec) struct list_struct r; if (tdb->methods->tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) { - TDB_LOG((tdb, 0, "tdb_free: right read failed at %u\n", right)); + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: right read failed at %u\n", right)); goto left; } /* If it's free, expand to include it. */ if (r.magic == TDB_FREE_MAGIC) { if (remove_from_freelist(tdb, right, r.next) == -1) { - TDB_LOG((tdb, 0, "tdb_free: right free failed at %u\n", right)); + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: right free failed at %u\n", right)); goto left; } rec->rec_len += sizeof(r) + r.rec_len; @@ -135,7 +135,7 @@ left: /* Read in tailer and jump back to header */ if (tdb_ofs_read(tdb, left, &leftsize) == -1) { - TDB_LOG((tdb, 0, "tdb_free: left offset read failed at %u\n", left)); + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left offset read failed at %u\n", left)); goto update; } @@ -148,14 +148,14 @@ left: /* Now read in record */ if (tdb->methods->tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) { - TDB_LOG((tdb, 0, "tdb_free: left read failed at %u (%u)\n", left, leftsize)); + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left read failed at %u (%u)\n", left, leftsize)); goto update; } /* If it's free, expand to include it. */ if (l.magic == TDB_FREE_MAGIC) { if (remove_from_freelist(tdb, left, l.next) == -1) { - TDB_LOG((tdb, 0, "tdb_free: left free failed at %u\n", left)); + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left free failed at %u\n", left)); goto update; } else { offset = left; @@ -166,7 +166,7 @@ left: update: if (update_tailer(tdb, offset, rec) == -1) { - TDB_LOG((tdb, 0, "tdb_free: update_tailer failed at %u\n", offset)); + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset)); goto fail; } @@ -176,7 +176,7 @@ update: if (tdb_ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 || tdb_rec_write(tdb, offset, rec) == -1 || tdb_ofs_write(tdb, FREELIST_TOP, &offset) == -1) { - TDB_LOG((tdb, 0, "tdb_free record write failed at offset=%d\n", offset)); + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free record write failed at offset=%d\n", offset)); goto fail; } -- cgit From 9da0c020571d901569e552224bfedd8bedbf43ba Mon Sep 17 00:00:00 2001 From: Jeremy Allison Date: Thu, 30 Nov 2006 03:25:07 +0000 Subject: r19960: Add code to check for loops in the free list. Should help us validate tdb's against corruption. Jeremy. (This used to be commit bd0710fa09799cb496b1f9f365c57c3b542445f3) --- source4/lib/tdb/common/freelist.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'source4/lib/tdb/common/freelist.c') diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c index 9d1ae59801..0efe47f879 100644 --- a/source4/lib/tdb/common/freelist.c +++ b/source4/lib/tdb/common/freelist.c @@ -29,7 +29,7 @@ #include "tdb_private.h" /* read a freelist record and check for simple errors */ -static int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec) +int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec) { if (tdb->methods->tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1) return -1; -- cgit From 81fb404a6f61205ed141fd9f0681e704e2a33ad6 Mon Sep 17 00:00:00 2001 From: Stefan Metzmacher Date: Tue, 17 Apr 2007 17:24:02 +0000 Subject: r22319: sync lib/tdb/ with samba3 metze (This used to be commit 8f24f6b38e967075589529a08c68a1a56f9f0499) --- source4/lib/tdb/common/freelist.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'source4/lib/tdb/common/freelist.c') diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c index 0efe47f879..01b61aff86 100644 --- a/source4/lib/tdb/common/freelist.c +++ b/source4/lib/tdb/common/freelist.c @@ -29,7 +29,7 @@ #include "tdb_private.h" /* read a freelist record and check for simple errors */ -int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec) +int tdb_rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec) { if (tdb->methods->tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1) return -1; @@ -37,7 +37,7 @@ int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *re if (rec->magic == TDB_MAGIC) { /* this happens when a app is showdown while deleting a record - we should not completely fail when this happens */ - TDB_LOG((tdb, TDB_DEBUG_WARNING, "rec_free_read non-free magic 0x%x at offset=%d - fixing\n", + TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_rec_free_read non-free magic 0x%x at offset=%d - fixing\n", rec->magic, off)); rec->magic = TDB_FREE_MAGIC; if (tdb->methods->tdb_write(tdb, off, rec, sizeof(*rec)) == -1) @@ -47,7 +47,7 @@ int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *re if (rec->magic != TDB_FREE_MAGIC) { /* Ensure ecode is set for log fn. */ tdb->ecode = TDB_ERR_CORRUPT; - TDB_LOG((tdb, TDB_DEBUG_WARNING, "rec_free_read bad magic 0x%x at offset=%d\n", + TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_rec_free_read bad magic 0x%x at offset=%d\n", rec->magic, off)); return TDB_ERRCODE(TDB_ERR_CORRUPT, -1); } @@ -286,7 +286,7 @@ tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_st issues when faced with a slowly increasing record size. */ while (rec_ptr) { - if (rec_free_read(tdb, rec_ptr, rec) == -1) { + if (tdb_rec_free_read(tdb, rec_ptr, rec) == -1) { goto fail; } @@ -311,7 +311,7 @@ tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_st } if (bestfit.rec_ptr != 0) { - if (rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) { + if (tdb_rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) { goto fail; } -- cgit From b8d69a7ea2505b706ff7c74d7c97bc89d82dfa07 Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Tue, 10 Jul 2007 02:46:15 +0000 Subject: r23795: more v2->v3 conversion (This used to be commit 84b468b2f8f2dffda89593f816e8bc6a8b6d42ac) --- source4/lib/tdb/common/freelist.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'source4/lib/tdb/common/freelist.c') diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c index 01b61aff86..e34a3c0728 100644 --- a/source4/lib/tdb/common/freelist.c +++ b/source4/lib/tdb/common/freelist.c @@ -14,7 +14,7 @@ This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either - version 2 of the License, or (at your option) any later version. + version 3 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -- cgit From 6c973f4e8ccbcb6c9275f8a54e26abb19df7e15a Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Tue, 10 Jul 2007 03:42:26 +0000 Subject: r23798: updated old Temple Place FSF addresses to new URL (This used to be commit 40c0919aaa9c1b14bbaebb95ecce53eb0380fdbb) --- source4/lib/tdb/common/freelist.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'source4/lib/tdb/common/freelist.c') diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c index e34a3c0728..b109643f23 100644 --- a/source4/lib/tdb/common/freelist.c +++ b/source4/lib/tdb/common/freelist.c @@ -22,8 +22,7 @@ Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public - License along with this library; if not, write to the Free Software - Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + License along with this library; if not, see . */ #include "tdb_private.h" -- cgit From 9170998427ebbb7abfd9b482fb6e0d051bca5205 Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Tue, 15 Jan 2008 14:05:47 +1100 Subject: merged tdb from ctdb bzr tree (This used to be commit ed0c3a0f74c305b3b8554b05c3f97cf79db8296a) --- source4/lib/tdb/common/freelist.c | 101 ++++++++++++++++++++++++++++---------- 1 file changed, 76 insertions(+), 25 deletions(-) (limited to 'source4/lib/tdb/common/freelist.c') diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c index b109643f23..c086c151fa 100644 --- a/source4/lib/tdb/common/freelist.c +++ b/source4/lib/tdb/common/freelist.c @@ -27,6 +27,12 @@ #include "tdb_private.h" +/* 'right' merges can involve O(n^2) cost when combined with a + traverse, so they are disabled until we find a way to do them in + O(1) time +*/ +#define USE_RIGHT_MERGES 0 + /* read a freelist record and check for simple errors */ int tdb_rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec) { @@ -56,7 +62,7 @@ int tdb_rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct } - +#if USE_RIGHT_MERGES /* Remove an element from the freelist. Must have alloc lock. */ static int remove_from_freelist(struct tdb_context *tdb, tdb_off_t off, tdb_off_t next) { @@ -75,6 +81,7 @@ static int remove_from_freelist(struct tdb_context *tdb, tdb_off_t off, tdb_off_ TDB_LOG((tdb, TDB_DEBUG_FATAL,"remove_from_freelist: not on list at off=%d\n", off)); return TDB_ERRCODE(TDB_ERR_CORRUPT, -1); } +#endif /* update a record tailer (must hold allocation lock) */ @@ -93,8 +100,6 @@ static int update_tailer(struct tdb_context *tdb, tdb_off_t offset, neccessary. */ int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec) { - tdb_off_t right, left; - /* Allocation and tailer lock */ if (tdb_lock(tdb, -1, F_WRLCK) != 0) return -1; @@ -105,9 +110,10 @@ int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec) goto fail; } +#if USE_RIGHT_MERGES /* Look right first (I'm an Australian, dammit) */ - right = offset + sizeof(*rec) + rec->rec_len; - if (right + sizeof(*rec) <= tdb->map_size) { + if (offset + sizeof(*rec) + rec->rec_len + sizeof(*rec) <= tdb->map_size) { + tdb_off_t right = offset + sizeof(*rec) + rec->rec_len; struct list_struct r; if (tdb->methods->tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) { @@ -122,13 +128,18 @@ int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec) goto left; } rec->rec_len += sizeof(r) + r.rec_len; + if (update_tailer(tdb, offset, rec) == -1) { + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset)); + goto fail; + } } } - left: +#endif + /* Look left */ - left = offset - sizeof(tdb_off_t); - if (left > TDB_DATA_START(tdb->header.hash_size)) { + if (offset - sizeof(tdb_off_t) > TDB_DATA_START(tdb->header.hash_size)) { + tdb_off_t left = offset - sizeof(tdb_off_t); struct list_struct l; tdb_off_t leftsize; @@ -145,7 +156,12 @@ left: left = offset - leftsize; - /* Now read in record */ + if (leftsize > offset || + left < TDB_DATA_START(tdb->header.hash_size)) { + goto update; + } + + /* Now read in the left record */ if (tdb->methods->tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) { TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left read failed at %u (%u)\n", left, leftsize)); goto update; @@ -153,21 +169,24 @@ left: /* If it's free, expand to include it. */ if (l.magic == TDB_FREE_MAGIC) { - if (remove_from_freelist(tdb, left, l.next) == -1) { - TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left free failed at %u\n", left)); - goto update; - } else { - offset = left; - rec->rec_len += leftsize; + /* we now merge the new record into the left record, rather than the other + way around. This makes the operation O(1) instead of O(n). This change + prevents traverse from being O(n^2) after a lot of deletes */ + l.rec_len += sizeof(*rec) + rec->rec_len; + if (tdb_rec_write(tdb, left, &l) == -1) { + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_left failed at %u\n", left)); + goto fail; } + if (update_tailer(tdb, left, &l) == -1) { + TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset)); + goto fail; + } + tdb_unlock(tdb, -1, F_WRLCK); + return 0; } } update: - if (update_tailer(tdb, offset, rec) == -1) { - TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset)); - goto fail; - } /* Now, prepend to free list */ rec->magic = TDB_FREE_MAGIC; @@ -261,6 +280,7 @@ tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_st tdb_off_t rec_ptr, last_ptr; tdb_len_t rec_len; } bestfit; + float multiplier = 1.0; if (tdb_lock(tdb, -1, F_WRLCK) == -1) return 0; @@ -295,18 +315,27 @@ tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_st bestfit.rec_len = rec->rec_len; bestfit.rec_ptr = rec_ptr; bestfit.last_ptr = last_ptr; - /* consider a fit to be good enough if - we aren't wasting more than half - the space */ - if (bestfit.rec_len < 2*length) { - break; - } } } /* move to the next record */ last_ptr = rec_ptr; rec_ptr = rec->next; + + /* if we've found a record that is big enough, then + stop searching if its also not too big. The + definition of 'too big' changes as we scan + through */ + if (bestfit.rec_len > 0 && + bestfit.rec_len < length * multiplier) { + break; + } + + /* this multiplier means we only extremely rarely + search more than 50 or so records. At 50 records we + accept records up to 11 times larger than what we + want */ + multiplier *= 1.05; } if (bestfit.rec_ptr != 0) { @@ -328,3 +357,25 @@ tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_st return 0; } + + +/* + return the size of the freelist - used to decide if we should repack +*/ +int tdb_freelist_size(struct tdb_context *tdb) +{ + tdb_off_t ptr; + int count=0; + + if (tdb_lock(tdb, -1, F_RDLCK) == -1) { + return -1; + } + + ptr = FREELIST_TOP; + while (tdb_ofs_read(tdb, ptr, &ptr) == 0 && ptr != 0) { + count++; + } + + tdb_unlock(tdb, -1, F_RDLCK); + return count; +} -- cgit From 524d280ad09c99bcbf63d789e909afdf7edb5860 Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Fri, 18 Jan 2008 15:33:57 +1100 Subject: merged tdb changes from ctdb (This used to be commit c54c087a19e36e0522eb4546c9425ae446f0628b) --- source4/lib/tdb/common/freelist.c | 85 ++++++++++++++++++++------------------- 1 file changed, 43 insertions(+), 42 deletions(-) (limited to 'source4/lib/tdb/common/freelist.c') diff --git a/source4/lib/tdb/common/freelist.c b/source4/lib/tdb/common/freelist.c index c086c151fa..2f2a4c379b 100644 --- a/source4/lib/tdb/common/freelist.c +++ b/source4/lib/tdb/common/freelist.c @@ -208,62 +208,61 @@ update: } + /* the core of tdb_allocate - called when we have decided which free list entry to use + + Note that we try to allocate by grabbing data from the end of an existing record, + not the beginning. This is so the left merge in a free is more likely to be + able to free up the record without fragmentation */ -static tdb_off_t tdb_allocate_ofs(struct tdb_context *tdb, tdb_len_t length, tdb_off_t rec_ptr, - struct list_struct *rec, tdb_off_t last_ptr) +static tdb_off_t tdb_allocate_ofs(struct tdb_context *tdb, + tdb_len_t length, tdb_off_t rec_ptr, + struct list_struct *rec, tdb_off_t last_ptr) { - struct list_struct newrec; - tdb_off_t newrec_ptr; +#define MIN_REC_SIZE (sizeof(struct list_struct) + sizeof(tdb_off_t) + 8) - memset(&newrec, '\0', sizeof(newrec)); + if (rec->rec_len < length + MIN_REC_SIZE) { + /* we have to grab the whole record */ - /* found it - now possibly split it up */ - if (rec->rec_len > length + MIN_REC_SIZE) { - /* Length of left piece */ - length = TDB_ALIGN(length, TDB_ALIGNMENT); - - /* Right piece to go on free list */ - newrec.rec_len = rec->rec_len - (sizeof(*rec) + length); - newrec_ptr = rec_ptr + sizeof(*rec) + length; - - /* And left record is shortened */ - rec->rec_len = length; - } else { - newrec_ptr = 0; + /* unlink it from the previous record */ + if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1) { + return 0; + } + + /* mark it not free */ + rec->magic = TDB_MAGIC; + if (tdb_rec_write(tdb, rec_ptr, rec) == -1) { + return 0; + } + return rec_ptr; + } + + /* we're going to just shorten the existing record */ + rec->rec_len -= (length + sizeof(*rec)); + if (tdb_rec_write(tdb, rec_ptr, rec) == -1) { + return 0; } - - /* Remove allocated record from the free list */ - if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1) { + if (update_tailer(tdb, rec_ptr, rec) == -1) { return 0; } - - /* Update header: do this before we drop alloc - lock, otherwise tdb_free() might try to - merge with us, thinking we're free. - (Thanks Jeremy Allison). */ + + /* and setup the new record */ + rec_ptr += sizeof(*rec) + rec->rec_len; + + memset(rec, '\0', sizeof(*rec)); + rec->rec_len = length; rec->magic = TDB_MAGIC; + if (tdb_rec_write(tdb, rec_ptr, rec) == -1) { return 0; } - - /* Did we create new block? */ - if (newrec_ptr) { - /* Update allocated record tailer (we - shortened it). */ - if (update_tailer(tdb, rec_ptr, rec) == -1) { - return 0; - } - - /* Free new record */ - if (tdb_free(tdb, newrec_ptr, &newrec) == -1) { - return 0; - } + + if (update_tailer(tdb, rec_ptr, rec) == -1) { + return 0; } - - /* all done - return the new record offset */ + return rec_ptr; } @@ -287,6 +286,7 @@ tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_st /* Extra bytes required for tailer */ length += sizeof(tdb_off_t); + length = TDB_ALIGN(length, TDB_ALIGNMENT); again: last_ptr = FREELIST_TOP; @@ -343,7 +343,8 @@ tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_st goto fail; } - newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr, rec, bestfit.last_ptr); + newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr, + rec, bestfit.last_ptr); tdb_unlock(tdb, -1, F_WRLCK); return newrec_ptr; } -- cgit