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!

ccanlint: Add -k option to keep results.

Particularly useful for building tests standalone.

ccanlint: make sure fullname is always full path name.

hashtable: fix traverse typesafety.

typesafe_cb: fix up (and test!) cast_if_any.

typesafe_cb: handle pointers to undefined struct types.

To do this, we have to lose the ability for preargs and postargs to allow const and volatile argument signatures.

typesafe_cb: show flaw in typesafe_cb with undefined structs.

typesafe_cb: fix !gcc case

typesafe_cb, hashtable: revise typesafe_cb arg order, neaten.
hashtable: make traverse callback typesafe.

idtree: new module

likely: new module

ccanlint: put generated _info in correct directory.

str: add stringify()

More web fixes.

tdb: fix backwards check on HAVE_PAGESIZE

Hashtable routines.

tools: fastcheck adjust; 750ms works well for me.

ccanlint: optimize the timeout case

This takes my "make fastcheck" from about 57 seconds to about 43 seconds.

Fix EXCLUDE logic for makefiles, add fastcheck

ccanlint: always catch timeouts, and force kill valgrind etc.

ccanlint: timeout, and implement -t option for quicker tests.

Use bzr to determine what to upload

ccanlint: clean up test short descriptions

ccanlint: cleanup listing code, make print in topo order.

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

The ccanlint patch is rather intrusive.  First, it adds a new field to
all the ccanlint tests, "key".  key is a shorter, still unique
description of the test (e.g. "valgrind").  The names I chose as keys
for all the tests are somewhat arbitrary and often don't reflect the
name of the .c source file (because some of those names are just too
darn long).  Second, it adds two new options to ccanlint:

   -l: list tests ccanlint performs
   -x: exclude tests (e.g. -x trailing_whitespace,valgrind)

It also adds a consistency check making sure all tests have unique
keys and names.

The primary goal of the ccanlint patch was so I could exclude the
valgrind test, which takes a really long time for some modules (I
think btree takes the longest, at around 2 minutes).  I'm not sure I
did it 100% correctly, so you'll want to review it first.

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

The btree patch gives the btree module an intuitive frontend
(btree_insert, btree_remove, btree_lookup) and a built-in ordering
function for strings.  Together, these make it easy to use the btree
module as a dynamic string map.

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

The charset patch makes utf8_validate reject the invalid codepoints
U+FFFE and U+FFFF .  Hopefully it's fully UTF-8 compliant now.

Fix segfault due to relative paths (ccan_depends), and generate pages for ignored modules too.

Joey's charset validation module.

asort: fix gcc warning.

tools: fix warnings from Ubuntu strict compiler.

tdb: handle processes dying during transaction commit.

tdb transactions were designed to be robust against the machine
powering off, but interestingly were never designed to handle the case
where an administrator kill -9's a process during commit.  Because
recovery is only done on tdb_open, processes with the tdb already
mapped will simply use it despite it being corrupt and needing
recovery.

The solution to this is to check for recovery every time we grab a
data lock: we could have gained the lock because a process just died.
This has no measurable cost: here is the time for tdbtorture -s 0 -n 1
-l 10000:

Before:
2.75 2.50 2.81 3.19 2.91 2.53 2.72 2.50 2.78 2.77 = Avg 2.75

After:
2.81 2.57 3.42 2.49 3.02 2.49 2.84 2.48 2.80 2.43 = Avg 2.74

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb: cleanup: tdb_lock_list helper to cover tdb_lock and tdb_lock_nonblock

Reduce code duplication, and also gives us a central point for the next
patch which wants to cover all list locks.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb: remove lock ops

Now the transaction code uses the standard allrecord lock, that stops
us from trying to grab any per-record locks anyway.  We don't need to
have special noop lock ops for transactions.

This is a nice simplification: if you see brlock, you know it's really
going to grab a lock.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb: more testcase fixup.

tdb: suppress record write locks when allrecord lock is taken.

Records themselves get (read) locked by the traversal code against delete.
Interestingly, this locking isn't done when the allrecord lock has been
taken, though the allrecord lock until recently didn't cover the actual
records (it now goes to end of file).

The write record lock, grabbed by the delete code, is not suppressed by
the allrecord lock, which causes us to punch a hole in that lock when we
release the write record lock.  Make this consistent: *no* record locks
of any kind when the allrecord lock is taken.

tdb: new test, cleanup old tests by centralizing lock tracking.

tdb: fix test to remove warning, and don't fail when tdb_check() barfs.

tdb: don't reduce file size on transaction recovery.

There's little point in ever shrinking the file, and it definitely breaks in the case where a process has died during a transaction commit and other processes have the tdb mapped.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb:  fix recovery reuse after crash (from SAMBA)

commit b37b452cb8c1f56b37b04abe7bffdede371ca361
Author: Rusty Russell <rusty@rustcorp.com.au>
Date:   Thu Feb 4 23:59:54 2010 +1030

    tdb: fix recovery reuse after crash

    If a process (or the machine) dies after just after writing the
    recovery head (pointing at the end of file), the recovery record will filled
    with 0x42.  This will not invoke a recovery on open, since rec.magic
    != TDB_RECOVERY_MAGIC.

    Unfortunately, the first transaction commit will happily reuse that
    area: tdb_recovery_allocate() doesn't check the magic.  The recovery
    record has length 0x42424242, and it writes that back into the
    now-valid-looking transaction header) for the next comer (which
    happens to be tdb_wipe_all in my tests).

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb: fix tdbtorture seed printing, plus remove CLEAR_IF_FIRST

With killing children, CLEAR_IF_FIRST can happen quite a bit.

tdb: cleanup: remove ltype argument from _tdb_transaction_cancel.

Now the transaction allrecord lock the standard one, and thus is cleaned
in tdb_release_extra_locks(), _tdb_transaction_cancel() doesn't need to
know what type it is.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb: tdb_allrecord_lock/tdb_allrecord_unlock/tdb_allrecord_upgrade

Centralize locking of all chains of the tdb; rename _tdb_lockall to
tdb_allrecord_lock and _tdb_unlockall to tdb_allrecord_unlock, and
tdb_brlock_upgrade to tdb_allrecord_upgrade.

Then we use this in the transaction code.  Unfortunately, if the transaction
code records that it has grabbed the allrecord lock read-only, write locks
will fail, so we treat this upgradable lock as a write lock, and mark it
as upgradable using the otherwise-unused offset field.

One subtlety: now the transaction code is using the allrecord_lock, the
tdb_release_extra_locks() function drops it for us, so we no longer need
to do it manually in _tdb_transaction_cancel.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb: cleanup: always grab allrecord lock to infinity.

We were previously inconsistent with our "global" lock: the
transaction code grabbed it from FREELIST_TOP to end of file, and the
rest of the code grabbed it from FREELIST_TOP to end of the hash
chains.  Change it to always grab to end of file for simplicity.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb: remove num_locks

This was redundant before this patch series: it mirrored num_lockrecs
exactly.  It still does.

Also, skip useless branch when locks == 1: unconditional assignment is
cheaper anyway.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb: use tdb_nest_lock() for seqnum lock.

This is pure overhead, but it centralizes the locking.  Realloc (esp. as
most implementations are lazy) is fast compared to the fnctl anyway.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb: use tdb_nest_lock() for active lock.

Rather than a boutique lock and a separate nest count, use our
newly-generic nested lock tracking for the active lock.

Note that the tdb_have_extra_locks() and tdb_release_extra_locks()
functions have to skip over this lock now it is tracked.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb: use tdb_nest_lock() for open lock.

This never nests, so it's overkill, but it centralizes the locking into
lock.c and removes the ugly flag in the transaction code to track whether
we have the lock or not.

Note that we have a temporary hack so this places a real lock, despite
the fact that we are in a transaction.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>