tdb: TDB_INCOMPATIBLE_HASH, to allow safe changing of default hash.

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.

tdb: automatically identify Jenkins hash tdbs

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.

tdb: add Bob Jenkins lookup3 hash as helper hash.

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().

tdb: add mktdb tool.

tally: new module for tallying numbers.

tools: restore -Wmissing-prototypes -Wmissing-declarations

tdb: fix test helper to include own header, fix function definition.

tdb2: add missing prototype, move tdb_firstkey/tdb_nextkey to traverse.c

tdb2: implement tdb_firstkey/tdb_nextkey.

tdb2: add tdb_errorstr(), clean up error codes.

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

tdb2: update design doc.

tdb: put example hashes into header, so we notice incorrect hash_fn.

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.

tdb: fix tdb_check() on other-endian tdbs.

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

tdb: fix tdb_check() on read-only TDBs to actually work.

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

tdb: support tdb_check() on r/o databases.

(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.

alloc: No need for tiny.c to be executable.

ccanlint: append NULL terminator to generated dependencies.

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

tdb2: fix remapping inside tdb_traverse_read

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.

tdb: missing files from checkin.

tdb: unify logging code in test dir.

tdb: make check more robust against recovery failures.

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.

tdb: rewrite external agent for testing.

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!

tdb: enforce hashing, via example hash in old rwlocks entry in header.

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.

tdb: test that new-style TDBs with non-default hashes can't be opened.

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.

ccanlint: use familiar names for temporary files, show them with -vv.

ccanlint: don't run valgrind tests in test dir.

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

ccanlint: print out compile targets for -vv.

ccanlint: allow _info file to specify tests not to bother with.

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

tdb: new command openjh for tdbtool (to use Jenkins hash)

tdb2: don't hold access to tdb mmap during traverse.

tdb2: change to using a hash tree.

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.

tdb2: update documentation.

Makefile: separate out junkpages target.

tdb2: make valgrind happier.

tdb2: expand lock now nests inside other locks.

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

tdb2: use immobile free buckets, rename tests to show some ordering.

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.

tdb2: document problems with moving or enlarging hash table.

tdb2: traversal test.

junkcode: new addition.

tdb2: fix valgrind warnings.

The unreserved headers were a real bug; the others could cause a false error too.

ccanlint: fix valgrind test.

We were not actually recording valgrind failures in ccanlint!

ccanlint: fix compiler warning about return value of symlink.

tools: only print out creating directory the first time.

tdb2: traverse and chainlock support.

These tests revealed more bugs with delete (rewritten) and hash enlargement.

tdb2: tdb_append implemented, beef up tests.

tdb2: more common code
Use hash_add() when resizing hash, too.

tdb2: fix argument order for tdb_gradual_lock.
This explains why most of tdb_gradual_lock was not tested: thanks gcov!

tdb2: extract common hashing code.

tdb2: fixes and test for hash enlargement.

tdb2: more tests, hash collision fixes, attribute support.

ccanlint: fix abort on "-d ..".

tests: now we run in tmp dir, always create temporary files in this dir.

ccanlint: use up to three -v to mean more verbosity.
eg. -v dumps percentage of coverage, -vv dumps per-line data, -vvv dumps every command executed.

tools: add build_verbose to show every command executed.

tdb: fix lock-tracking test code after gradual lock changes.

tdb2: new tests, and new fixes.

tdb2: check that records are of sufficient length in tdb_check.

tdb2: split expand into functions and test separately.

Update main page.

ccanlint: chdir to temporary dir so gcov files land there.

This means parallel "make check" works again.

ccanlint: use gcov to rate test coverage (score out of 5)

ccanlint: clean up code which outputs results, handle partial failure.

tap: don't _exit on success

This prevents us from writing out gcov files.

tdb2: more fixes and tests for enlarging hash.
- Neaten I/O function
- Don't use fill in zero_out: it's only for low-level ops.
- Don't mangle arg in tdb_write_convert: it broke write_header.
- More use of tdb_access_read, make it optionally converting.
- Rename unlock_range to unlock_lists.
- Lots of fixes to enlarge_hash now it's being tested.
- More expansion cases tested.

tdb2: delete and fetch now work.

tdb2: clean up locking a little bit, fix hash wrap problem.

tdb2: now we can store a key!

tdb2: tdb_expand on empty database now tested.

tdb2: now checking a new empty database works.

hash: 64-bit hash functions should take 64-bit base.

tdb2: update config.h with more defines.

tdb2: initial commit (doesn't work, still writing tests)

Makefile: don't hide what we're doing, user can use -s.

hash: 64 bit variants.

tdb: use tdb_lockall_gradual by default.

This has the advantage the transactions will also use it, preventing them
from blocking.

tdb: test and resolultion for tdb_lockall starvation.

web: handle symlinks in bzrbrowse.cgi, fix images.

web: make sure to include symlinks in tarballs

Add author and maintainer fields.

Add licences/ dir and symlinks for a bit more clarity.

alloc: speed up tiny allocator

alloc: remove unused debugging function.

alloc: reduce number of large pages to 256.

This reduces the number of huge allocs, which drops test time from 6 minutes to 57 seconds.

alloc: implement huge allocations

Inefficient scheme for allocations > 1/8192 of the pool size.

alloc: fix bug in tiny allocator.

alloc: fix typo which can cause false assertion

alloc: fix bug in tiny allocator

We can have a 0 byte in the *middle* of an encoding.

alloc: remove encode limit arg, and implement free array cache.

alloc: first cut of tiny allocator (down to 2 bytes!)

typesafe_cb: fix fallout from API changes.

typesafe_cb: expose _exact and _def variants.

We can't allow NULL with the new variant (needed by talloc's set_destructor
for example), so document that and expose all three variants for different
uses.

typesafe_cb: fix promotable types being incorrectly accepted by cast_if_type.

cast_if_type() should not try to degrade the expression using 1?(test):0,
as that promotes bool to int, as well as degrading functions to function
pointers: it should be done by the callers.

In particular, this fixes sparse_bsearch.

alloc: reduce page header further, go down to 64k minimum.

This means we can't have more than 2^25 elements per page; that's
a maximum small page size of about 2^24 (with >8 objects per small page
we move to large pages), meaning a poolsize max of 4G.

We have a tighter limit at the moment anyway, but we should remove it
once we fix this.  In particular count all-zero and all-one words in
the used field (that's what we care about: full or empty) would give us
another factor of 64 (we only care about larger pool sizes on 64-bit
platforms).

We can also restore the larger number of pages and greater inter-page
spacing once we implement the alternative tiny allocator.

alloc: make small_page_bits() function rather than large_page_bits()

Turns out that now we use page numbers, this is more fundamental.

alloc: use page numbers in lists to reduce overhead.

alloc: implement alloc_visualize().

alloc: fix page header size calculation bug, increase type safety.

idtree: add examples, particularly the low-id-reuse example.

alloc: first cut of new Tridge-inspired allocator

This version has limitations: pools must be at least 1MB, and allocations
are restricted to 1/1024 of the total pool size.

ccanlint: don't setpgid on running commands: we want ^C to work!