Import from SAMBA tdb:
commit a6cc04a20089e8fbcce138c271961c37ddcd6c34
Author: Andrew Tridgell <tridge@samba.org>
Date:   Mon Jun 1 13:13:07 2009 +1000

    overallocate all records by 25%

    This greatly reduces the fragmentation of databases where records
    tend to grow slowly by a small amount each time. The case where this
    is most seen is the ldb index records. Adding this overallocation
    reduced the size of the resulting database by more than 20x when
    running a test that adds 10k users.

Import from SAMBA tdb:
commit a386173fa1c7c5bcc11ea9260d84b6c52c154b3d
Author: Andrew Tridgell <tridge@samba.org>
Date:   Mon Jun 1 13:11:39 2009 +1000

    auto-repack in transactions that expand the tdb

    The idea behind this is to recover from badly fragmented free
    lists. Choosing the point where the file expands is fairly arbitrary,
    but seems to work well.

Import from SAMBA tdb:
commit 936d76802f98d04d9743b2ca8eeeaadd4362db51
Author: Andrew Tridgell <tridge@samba.org>
Date:   Tue Dec 16 14:38:17 2008 +1100

    imported the tdb_repack() code from CTDB

    The tdb_repack() function repacks a TDB so that it has a single
    freelist entry. The file doesn't shrink, but it does remove all
    freelist fragmentation. This code originated in the CTDB vacuuming
    code, but will now be used in ldb to cope with fragmentation from
    re-indexing

Fix up non-TDB_TRACE compile.

Turn off TDB_TRACE again (shouldn't have left it on in commit)

Remove const warning

Don't fail mysteriously on existing trace file.

Import from SAMBA tdb:
commit 4b4fec65db4e202afa13b2d15867f4d8a54d154e
Author: Andrew Tridgell <tridge@samba.org>
Date:   Thu May 28 16:08:28 2009 +1000

    make TDB_NOSYNC affect all the fsync/msync calls in transactions

    During a transaction commit tdb normally uses fsync/msync calls to
    make it crash safe. This can be disabled using the TDB_NOSYNC flag,
    but it wasn't disabling all the code paths that caused a fsync/msync.

Import from SAMBA's tdb:
commit a91bcbccf8a2243dac57cacec6fdfc9907580f69
Author: Jim McDonough <jmcd@samba.org>
Date:   Thu May 21 16:26:26 2009 -0400

    Detect tight loop in tdb_find()

Import from SAMBA's tdb:
commit b90863c0b7b860b006ac49c9396711ff351f777f
Author: Howard Chu <hyc@highlandsun.com>
Date:   Tue Mar 31 13:15:54 2009 +1100

    Add tdb_transaction_prepare_commit()

    Using tdb_transaction_prepare_commit() gives us 2-phase commits. This
    allows us to safely commit across multiple tdb databases at once, with
    reasonable transaction semantics

Signed-off-by: tridge@samba.org

merge

Neaten tdb to sync with samba version of locking fix.
Also, actually test locking, rather than just lock count (bit me in samba fix)

stringmap: Flipped bit order to match sorted string order and added traversal test

Speed up tracing by factor of 4-6, by writing less stupid code.

merge

Short types

talloc_link; a replacement for talloc's references.

_info files are no longer to be ignored, since we renamed them from _info.c

License for talloc is actually LGPL.

talloc_free() should take a const void *, a-la free().

Improved stringmap to support strings with null characters

Merge.

Automate rerunning when we have to back off: gives accurate(ish) timings.

Cleanup variable names.
struct op: serial -> seqnum (and drop use of term "serial" everywhere).
struct op: op -> type
struct op_desc: general replacement for file/op_num pair.
Change add_dependency to take two const op_desc *: means reshuffle since we can't adjust the args any more.

Add handling of reduced test cases (traverse lines trimmed), and add all the test cases I've been using.

Completely unhobble tdbtorture.

Oops, forgot to check in new keywords files :(

YA corner case: help assumption by putting cancelled transactions first.

Leave groups of chainlock inside traverse.

tdb_chainlock/tdb_chainunlock et. al. support.

Rusty's cleanup to ciniparser.c's strstrip and strlwc

Handle global_lock properly in tdb_transaction_lock/unlock.

Fix tracing for tdb_chainunlock.

Minor optimization: don't make a dependency between two traverse_reads.

Cleanup: rename is_* to starts_*, move functions together, factor out start finding code.

Clean up traverse keyword handling.

Partial ordering of traverses: reduces number of deadlocks by factor of 10.

Fix logic bug; we weren't checking last requirement in sort_deps.

Implement timeout for the deadlock of traverse & transactions.
This has proven to be intractible: various attempts to eliminate have failed, so detect at runtime and cease the traversal (and do the remaining ops outside a traverse).

Open database with TDB_NOSYNC to speed it up a little.

Added run-dictionary.c test to ciniparser

Tiny fix to stringmap's run.c

Fix sequence logic bug, and satisfies() logic fix/cleanup.

Handle transactions!
Note: we can still deadlock on traversal vs transaction corner cases.
We handle transactions as single operation, which it logically is.

Added module stringmap

Fix sequence numbers when tracing transaction.
If we do the trace inside the lock, we show the actual sequence number when the transaction started.

Insert (implied) transaction cancel on tdb_close/EOF.
Also changes first member of transaction to have valid start_group field,
and fix outdated comment.

Print seq numbers on timeout dump
(Invasive: means passing full op array all the way through).

Added module block_pool

Fix early transaction unlock when traverse done inside transaction.
Generalizes traverse in traverse fix from rusty@rustcorp.com.au-20090629073630-3eduhyypx2tp6u80

Fix null ptr deref on TDB_TRACE with internal db.

Remove trivial traverse code, simplify.
We now use the "group_len" field for both transactions and traversals.

Fix logic bug in optimizer, and fix up DEBUG_DEPS compile.

More dependency optimization: seems to happen with transactions enabled.

More general solution for serial number misorders.
Make sort_deps more efficient, and also only alter order when necessary.  This means by default we run in serial number order, only going outside when we detect a dependency.
Maintain trace file order in original sort, so sort_deps doesn't mess it up.

We still need serial numbers: sort_deps can have multiple solutions for a single key, but these may deadlock with the ordering requirements of other keys.  By sticking close to the actual order (ie. serial order), we minimize the chance of this happening.

Optimize to reduce extraneous dependencies.
In my tdbtorture -n 4 example trace, this reduces from 14493 to 3210 dependencies, but doesn't make any measurable improvement in the time.  Still, it's simple to do and might make a difference for larger sets.

Belated checkin of keywords.

Simplify dependencies by passing pointers over the pipe: avoid O(n^2) behaviour for searching.
Also, using a single structure makes talloc_free convenient for when we do optimization.

Slightly more sophisticated dependency generation: fixes traverse interaction.

Missed part of patch.

Get more sophisticated with resolving duplicate serial numbers.
Still deadlocks in one case, due to spurious dependencies inside traversals.  See next commit.

Make tokenizer throw error on empty char literal, along with some slight cleanups in ccan_tokenizer.h

Make ccanlint core objects depend on generated-init-tests to fix build error

Small fix to read_cstring for reading \? .

Traverses seem to work now.  Also, much better reporting of deadlocks.

First attempt at transactions & traverse (deadlocks still).

Fix uninitialized var.

... and fix up keyword list.

Fix last minute warning "fix" in replay_trace.c, remove seqnum inc tracing.

Better tdb tracing, start of decent replay_trace.

const addition changes from brian, awfulhak.org

Added module ccan_tokenizer from snapshot at:
http://www.funsitelots.com/ccan/ccan_tokenizer-20090703.tar.bz2

More junkcode!

New junkcode.

Torture harder: random ops inside traverses.

Don't make assumptions about traverse order, and prove it by using a different hash.

Handle tracing on internal dbs.

Fix traverse nesting unlock bug.

zero-append test for tdb.

Fix append of zero-length records to zero-length records.
realloc() has that horrible overloaded free semantics.

Fix theoretical problem with 0-length records.
By faking them out to length 1, we might go oob.  Just fake the malloc.

First cut of replay_trace for tdb.

Tracing for tdb operations.

ccanize tdb further, and add simple test.

First step to ccanizing TDB.

Initial TDB import.

Convert to 64 bit crcs: change semantics of crcbits field to be *upper* not *lower* bits.

Implement a (poor?) 64-bit CRC.

64-bit CRC code.

Fix ubuntu "ignoring return value" warnings.

Implementation of auto-depends, based on Idris's start.

Many list funcs should work with constant lists.

merge

New junkcode.

Updated array module to version 0.1.1 .
Important change:  array_pop no longer checks if the array has elements; use array_pop_check in its place.

Rename _info.c to _info: this means we can simple compile *.c.

Move ccanlint tests into subdirectories.

Make ccanlint tests all positive: ie. "has _info.c file: FAILED".

From: Joseph Adams <joeyadams3.14159@gmail.com>

I have given my array module a makeover (see attached
array-0.1.tar.bz2 ).  Major changes are:

* All the macros have been renamed to flat array_* names.  Instead of
Array, AInit, AAppend, etc., it is now array, array_init,
array_append, etc..  This will obviously break any applications
already using the array module (if any); 'renames' is the list of sed
commands I used to make the name changes.
* array (by default) now uses talloc functions instead of regular
malloc/realloc/free.
* All of the array macros have tests now.

Joey's patch to ignore ccan/ lines in #include.