Including pretty graphs!

Not as trivial as you might think, with overflow and underflow.

This flag to tdb_open/tdb_open_ex effects creation of a new database:
1) Uses the Jenkins lookup3 hash instead of the old gdbm hash if none is
   specified,
2) Places a non-zero field in header->rwlocks, so older versions of TDB will
   refuse to open it.

This means that the caller (ie Samba) can set this flag to safely
change the hash function.  Versions of TDB from this one on will either
use the correct hash or refuse to open (if a different hash is specified).
Older TDB versions will see the nonzero rwlocks field and refuse to open 
it under any conditions.

If the caller to tdb_open_ex() doesn't specify a hash, and tdb_old_hash
doesn't match, try tdb_jenkins_hash.

This makes life simpler, especially with the upcoming TDB_INCOMPATIBLE_HASH
flag.

This is a better hash than the default: shipping it with tdb makes it easy
for callers to use it as the hash by passing it to tdb_open_ex().

Also remove TDB_DISALLOW_NESTING flag, since that's the default now.

This is Stefan Metzmacher <metze@samba.org>'s patch with minor
changes:
1) Use the TDB_MAGIC constant so both hashes aren't of strings.
2) Check the hash in tdb_check (paranoia, really).
3) Additional check in the (unlikely!) case where both examples hash to 0.
4) Cosmetic changes to var names and complaint message.

We must not endian-convert the magic string, just the rest.

But make sure we can still do tdb_check() inside a transaction (weird,
but we previously allowed it).

(Imported from SAMBA commit bc1c82ea137e1bf6cb55139a666c56ebb2226b23)

Author: Jeremy Allison <jra@samba.org>
Date:   Wed Jul 28 05:15:40 2010 -0700

Fix tdb_check() to work with read-only tdb databases. The function tdb_lockall() uses F_WRLCK internally, which doesn't work on a fd opened with O_RDONLY. Use tdb_lockall_read() instead.
    
Jeremy.

Interestingly, valgrind didn't even notice.  But it crashed on (some) PowerPC.

Because we (temporarily!) marked the tdb read_only=true, any remap would
mmap PROT_READ, and the next store would SEGV.

Pulled in more test infrastructure from tdb.

We can end up with dead areas when we die during transaction commit;
tdb_check() fails on such a (valid) database.

This is particularly noticable now we no longer truncate on recovery;
if the recovery area was at the end of the file we used to remove it
that way.

For locking and transaction tests, we need an external process to probe the
tdb.  This code was a mess, and unreliable (occasional failures).  Rewrite
it so that instead of blocking and using SIGALRM, we mug fcntl and force
non-blocking locks.  We use a special return to day "I couldn't because
the lock wasn't available".

I also made the operations clearer and more orthogonal rather than "what
we needed for each test" which was really hard to understand.

It turns out those occasional failures weren't spurious.  Next patch!

This means that older code will not be able to open new TDBs with
a non-default hash, *even* if they are using the correct hash.
Non-default hashes were unusual, but now SAMBA is considering using
a non-default hash, and avoiding corruption seems more important
than backwards compatibility for an obscure case.

We currently allow opening of a TDB without any idea if we're using the
right hash function.  Since most people use the default, this hasn't been
a big issue.

The next change will put an example hash value in the rwlocks field in
the header: current TDB already refuses to open a TDB with this field
non-zero.  This commit simply adds tests that that occurs.

We changed other tests to run in our tmpdir, missed this one.

I also changed -x to be specified multiple times rather than using , separators.

As the locking issues with enlarging a hash were so nasty, we switch to a
tree structure for the entries.  It's a hash which expands to point to
sub-hashes when it fills.

This means we no longer have a 'volatile' header: the top hash cannot move.
In fact, we no longer store a copy of the header in the tdb_context; we only
need hash_seed.

New helper functions for accessing writable areas and committing the results
(if they had to be copied).  New debug test to make sure we don't hold access
while we're doing something which could cause us to unmap/remap.

Find becomes more complicated: we need to track where we found (or didn't
find) an entry so we can easily add/delete it.

Traverse becomes more complicated: we need to track where we were in the
hash tree.

This eliminates all the "drop lock and retry" logic: we expand inside alloc().

We put the free lists at the beginning of a zone; this means no record
can be larger than a zone, but means they cannot move.  Once we change
hashes to be expanding, they won't move either and the result should be
simpler.