We don't have tailers in tdb2, so it's just 8 bytes of confusing wastage.

Instead of walking the entire free list, walk 8 entries, or more if we
are successful: the reward is scaled by the size coalesced.

We also move previously-examined records to the end of the list.

This reduces file size with very little speed penalty.

Before:
$ time ./growtdb-bench 250000 10 > /dev/null && ls -l /tmp/growtdb.tdb && time ./tdbtorture -s 0 && ls -l torture.tdb && ./speed --transaction 2000000
real	1m17.022s
user	0m27.206s
sys	0m3.920s
-rw------- 1 rusty rusty 570130576 2011-04-27 21:17 /tmp/growtdb.tdb
testing with 3 processes, 5000 loops, seed=0
OK

real	1m27.355s
user	0m0.296s
sys	0m0.516s
-rw------- 1 rusty rusty 617352 2011-04-27 21:18 torture.tdb
Adding 2000000 records:  890 ns (110556088 bytes)
Finding 2000000 records:  565 ns (110556088 bytes)
Missing 2000000 records:  390 ns (110556088 bytes)
Traversing 2000000 records:  410 ns (110556088 bytes)
Deleting 2000000 records:  8623 ns (244003768 bytes)
Re-adding 2000000 records:  7089 ns (244003768 bytes)
Appending 2000000 records:  33708 ns (244003768 bytes)
Churning 2000000 records:  2029 ns (268404160 bytes)

After:
$ time ./growtdb-bench 250000 10 > /dev/null && ls -l /tmp/growtdb.tdb && time ./tdbtorture -s 0 && ls -l torture.tdb && ./speed --transaction 2000000
real	1m7.096s
user	0m15.637s
sys	0m3.812s
-rw------- 1 rusty rusty 561270928 2011-04-27 21:22 /tmp/growtdb.tdb
testing with 3 processes, 5000 loops, seed=0
OK

real	1m13.850s
user	0m0.268s
sys	0m0.492s
-rw------- 1 rusty rusty 429768 2011-04-27 21:23 torture.tdb
Adding 2000000 records:  892 ns (110556088 bytes)
Finding 2000000 records:  570 ns (110556088 bytes)
Missing 2000000 records:  390 ns (110556088 bytes)
Traversing 2000000 records:  407 ns (110556088 bytes)
Deleting 2000000 records:  706 ns (244003768 bytes)
Re-adding 2000000 records:  822 ns (244003768 bytes)
Appending 2000000 records:  1262 ns (268404160 bytes)
Churning 2000000 records:  2320 ns (268404160 bytes)

This simply uses a 7 bit counter which gets incremented on each addition
to the list (but not decremented on removals).  When it wraps, we walk the
entire list looking for things to coalesce.

This causes performance problems, especially when appending records, so
we limit it in the next patch:

Before:
$ time ./growtdb-bench 250000 10 > /dev/null && ls -l /tmp/growtdb.tdb && time ./tdbtorture -s 0 && ls -l torture.tdb && ./speed --transaction 2000000
real	0m59.687s
user	0m11.593s
sys	0m4.100s
-rw------- 1 rusty rusty 752004064 2011-04-27 21:14 /tmp/growtdb.tdb
testing with 3 processes, 5000 loops, seed=0
OK

real	1m17.738s
user	0m0.348s
sys	0m0.580s
-rw------- 1 rusty rusty 663360 2011-04-27 21:15 torture.tdb
Adding 2000000 records:  926 ns (110556088 bytes)
Finding 2000000 records:  592 ns (110556088 bytes)
Missing 2000000 records:  416 ns (110556088 bytes)
Traversing 2000000 records:  422 ns (110556088 bytes)
Deleting 2000000 records:  741 ns (244003768 bytes)
Re-adding 2000000 records:  799 ns (244003768 bytes)
Appending 2000000 records:  1147 ns (295244592 bytes)
Churning 2000000 records:  1827 ns (568411440 bytes)

After:
$ time ./growtdb-bench 250000 10 > /dev/null && ls -l /tmp/growtdb.tdb && time ./tdbtorture -s 0 && ls -l torture.tdb && ./speed --transaction 2000000
real	1m17.022s
user	0m27.206s
sys	0m3.920s
-rw------- 1 rusty rusty 570130576 2011-04-27 21:17 /tmp/growtdb.tdb
testing with 3 processes, 5000 loops, seed=0
OK

real	1m27.355s
user	0m0.296s
sys	0m0.516s
-rw------- 1 rusty rusty 617352 2011-04-27 21:18 torture.tdb
Adding 2000000 records:  890 ns (110556088 bytes)
Finding 2000000 records:  565 ns (110556088 bytes)
Missing 2000000 records:  390 ns (110556088 bytes)
Traversing 2000000 records:  410 ns (110556088 bytes)
Deleting 2000000 records:  8623 ns (244003768 bytes)
Re-adding 2000000 records:  7089 ns (244003768 bytes)
Appending 2000000 records:  33708 ns (244003768 bytes)
Churning 2000000 records:  2029 ns (268404160 bytes)

I noticed a counter-intuitive phenomenon as I tweaked the coalescing
code: the more coalescing we did, the larger the tdb grew!  This was
measured using "growtdb-bench 250000 10".

The cause: more coalescing means larger transactions, and every time
we do a larger transaction, we need to allocate a larger recovery
area.  The only way to do this is to append to the file, so the file
keeps growing, even though it's mainly unused!

Overallocating by 25% seems reasonable, and gives better results in
such benchmarks.

The real fix is to reduce the transaction to a run-length based format
rather then the naive block system used now.

Before:
$ time ./growtdb-bench 250000 10 > /dev/null && ls -l /tmp/growtdb.tdb && time ./tdbtorture -s 0 && ls -l torture.tdb && ./speed --transaction 2000000
real	0m57.403s
user	0m11.361s
sys	0m4.056s
-rw------- 1 rusty rusty 689536976 2011-04-27 21:10 /tmp/growtdb.tdb
testing with 3 processes, 5000 loops, seed=0
OK

real	1m24.901s
user	0m0.380s
sys	0m0.512s
-rw------- 1 rusty rusty 655368 2011-04-27 21:12 torture.tdb
Adding 2000000 records:  941 ns (110551992 bytes)
Finding 2000000 records:  603 ns (110551992 bytes)
Missing 2000000 records:  428 ns (110551992 bytes)
Traversing 2000000 records:  416 ns (110551992 bytes)
Deleting 2000000 records:  741 ns (199517112 bytes)
Re-adding 2000000 records:  819 ns (199517112 bytes)
Appending 2000000 records:  1228 ns (376542552 bytes)
Churning 2000000 records:  2042 ns (553641304 bytes)

After:
$ time ./growtdb-bench 250000 10 > /dev/null && ls -l /tmp/growtdb.tdb && time ./tdbtorture -s 0 && ls -l torture.tdb && ./speed --transaction 2000000
real	0m59.687s
user	0m11.593s
sys	0m4.100s
-rw------- 1 rusty rusty 752004064 2011-04-27 21:14 /tmp/growtdb.tdb
testing with 3 processes, 5000 loops, seed=0
OK

real	1m17.738s
user	0m0.348s
sys	0m0.580s
-rw------- 1 rusty rusty 663360 2011-04-27 21:15 torture.tdb
Adding 2000000 records:  926 ns (110556088 bytes)
Finding 2000000 records:  592 ns (110556088 bytes)
Missing 2000000 records:  416 ns (110556088 bytes)
Traversing 2000000 records:  422 ns (110556088 bytes)
Deleting 2000000 records:  741 ns (244003768 bytes)
Re-adding 2000000 records:  799 ns (244003768 bytes)
Appending 2000000 records:  1147 ns (295244592 bytes)
Churning 2000000 records:  1827 ns (568411440 bytes)

We currently start walking the free list again when we coalesce any record;
this is overzealous, as we only care about the next record being blatted,
or the record we currently consider "best".

We can also opportunistically try to add the coalesced record into the
new free list: if it fails, we go back to the old "mark record,
unlock, re-lock" code.

Before:
$ time ./growtdb-bench 250000 10 > /dev/null && ls -l /tmp/growtdb.tdb && time ./tdbtorture -s 0 && ls -l torture.tdb && ./speed --transaction 2000000
real	1m0.243s
user	0m13.677s
sys	0m4.336s
-rw------- 1 rusty rusty 683302864 2011-04-27 21:03 /tmp/growtdb.tdb
testing with 3 processes, 5000 loops, seed=0
OK

real	1m24.074s
user	0m0.344s
sys	0m0.468s
-rw------- 1 rusty rusty 836040 2011-04-27 21:04 torture.tdb
Adding 2000000 records:  1015 ns (110551992 bytes)
Finding 2000000 records:  641 ns (110551992 bytes)
Missing 2000000 records:  445 ns (110551992 bytes)
Traversing 2000000 records:  439 ns (110551992 bytes)
Deleting 2000000 records:  807 ns (199517112 bytes)
Re-adding 2000000 records:  851 ns (199517112 bytes)
Appending 2000000 records:  1301 ns (376542552 bytes)
Churning 2000000 records:  2423 ns (553641304 bytes)

After:
$ time ./growtdb-bench 250000 10 > /dev/null && ls -l /tmp/growtdb.tdb && time ./tdbtorture -s 0 && ls -l torture.tdb && ./speed --transaction 2000000
real	0m57.403s
user	0m11.361s
sys	0m4.056s
-rw------- 1 rusty rusty 689536976 2011-04-27 21:10 /tmp/growtdb.tdb
testing with 3 processes, 5000 loops, seed=0
OK

real	1m24.901s
user	0m0.380s
sys	0m0.512s
-rw------- 1 rusty rusty 655368 2011-04-27 21:12 torture.tdb
Adding 2000000 records:  941 ns (110551992 bytes)
Finding 2000000 records:  603 ns (110551992 bytes)
Missing 2000000 records:  428 ns (110551992 bytes)
Traversing 2000000 records:  416 ns (110551992 bytes)
Deleting 2000000 records:  741 ns (199517112 bytes)
Re-adding 2000000 records:  819 ns (199517112 bytes)
Appending 2000000 records:  1228 ns (376542552 bytes)
Churning 2000000 records:  2042 ns (553641304 bytes)

This makes life easier for the next patch.

We took the original expansion heuristic from TDB1, and they just
fixed theirs, so copy that.

Before:

After:
time ./growtdb-bench 250000 10 > /dev/null && ls -l /tmp/growtdb.tdb && time ./tdbtorture -s 0 && ls -l torture.tdb && ./speed --transaction 2000000
growtdb-bench.c: In function ‘main’:
growtdb-bench.c:74:8: warning: ignoring return value of ‘system’, declared with attribute warn_unused_result
growtdb-bench.c:108:9: warning: ignoring return value of ‘system’, declared with attribute warn_unused_result

real	1m0.243s
user	0m13.677s
sys	0m4.336s
-rw------- 1 rusty rusty 683302864 2011-04-27 21:03 /tmp/growtdb.tdb
testing with 3 processes, 5000 loops, seed=0
OK

real	1m24.074s
user	0m0.344s
sys	0m0.468s
-rw------- 1 rusty rusty 836040 2011-04-27 21:04 torture.tdb
Adding 2000000 records:  1015 ns (110551992 bytes)
Finding 2000000 records:  641 ns (110551992 bytes)
Missing 2000000 records:  445 ns (110551992 bytes)
Traversing 2000000 records:  439 ns (110551992 bytes)
Deleting 2000000 records:  807 ns (199517112 bytes)
Re-adding 2000000 records:  851 ns (199517112 bytes)
Appending 2000000 records:  1301 ns (376542552 bytes)
Churning 2000000 records:  2423 ns (553641304 bytes)

And testing reveals a latent bug on 32 bit systems.

This is definitely a bad idea in general, but SAMBA uses nested transactions
in many and varied ways (some of them probably reflect real bugs) and it's
far easier to support them inside tdb2 with a flag.

We already have part of the TDB1 infrastructure in place, so this patch
just completes it and fixes one place where I'd messed it up.

It's probably not a good idea, because it's a recipe for deadlocks if
anyone else grabs any *other* two chainlocks, or the allrecord lock,
but SAMBA definitely does it, so allow it as TDB1 does.

Now we have tdb_get_attribute, it makes sense to make that the method
of accessing statistics.  That way they are always available, and it's
probably cheaper doing the direct increment than even the unlikely()
branch.

Otherwise tdb_name() can be NULL in log functions.  And we might as
well allocate it with the tdb, as well.

It makes sense for some attributes to be manipulated after tdb_open,
so allow that.

This allows overriding of low-level locking functions.  This allows
special effects such as non-blocking operations, and lock proxying.

We rename some local lock vars to l to avoid -Wshadow warnings.

And don't double-log.  Both of these cause problems if we want to do
tdb_transaction_prepare_commit non-blocking (and have it fail so we can
try again).

This allows the caller to implement clear-if-first semantics as per
TDB1.  The flag was removed for good reasons: performance and
unreliability, but SAMBA3 still uses it widely, so this allows them to
reimplement it themselves.

(There is no way to do it without help like this from tdb2, since it has
 to be done under the open lock).

1) The logging function needs to append a \n.
2) The transaction start code should be after the comment and print.
3) We should run tdb_check to make sure the database is OK after each op.

Also, rename private logfn to log_fn for consistency with other members.

We use underscores everywhere else, so be consistent.

It's redundant calling hash.hash_fn for example.  Standardize on fn
and data as names (private conflicts with C++).

This gives us more locks for future use, plus allows a clear-if-first-style
hack to be implemented.

1) Fix the bogus reporting of uncoalesced runs: there has to be more than 1
   free record to make a "run", and any other record interrups the run.
2) Fix the bogus data count in the top line (which was number of records,
   not bytes).
3) Remove the count of free buckets: it's now a constant.

Douglas Bagnell noted that it didn't specify.

It's common when integrating CCAN into existing projects that they define
such constants for themselves.  In an ideal world, the entire project
switches to one set of definitions, but for large projects (eg SAMBA)
that's not realistic and conflicts with the aim of making CCAN modules
easy to "drop in" to existing code.

(This is a generalization of Douglas Bagnell's patch sent in Message-ID:
<4DB8D00D.8000800@paradise.net.nz>).

Makes it easier to reuse this code in other projects.

It's useful for developers, but not so much for casual users.  For example,
RHEL 5.6 has qsort_r, but no prototype, which causes a warning.

Otherwise, _GNU_SOURCE isn't defined (for example) so prototypes such as
isblank can be missing.

If the line is made solely of whitespaces, they get removed and we end up with len
set to -1. Therefore we need an additional check to avoid dereferencing line[-1].

Inspired by patch from Volker.

Get rid of many variants, which were just confusing for most people.
Keep typesafe_cb(), typesafe_cb_preargs() and typesafe_cb_postarts(),
and rework cast_if_type() into typesafe_cb_cast() so we stay in our
namespace.

I should have done this as soon as I discovered the limitation that
the types have to be defined if I want const-taking callbacks.

Don't check the whole source, but it's nice for headers to be C++-clean.

Defines whether it's useful to do #define _FILE_OFFSET_BITS 64 to get a
larger off_t.