htable, strset: benchmarking tools.

This lets us compare hash table vs. strset vs. the example
implementation of critbit trees.

cbspeed 100 runs, min-max(avg):
#01: Initial insert:   236-245(237)
#02: Initial lookup (match):   180-186(180)
#03: Initial lookup (miss):   171-185(172)
#04: Initial lookup (random):   441-457(444)
#05: Initial delete all:   127-132(128)
#06: Initial re-inserting:   219-225(220)
#07: Deleting first half:   101-104(102)
#08: Adding (a different) half:   158-162(159)
#09: Lookup after half-change (match):   202-207(203)
#10: Lookup after half-change (miss):   217-222(218)
#11: Churn 1:   297-302(299)
#12: Churn 2:   297-305(300)
#13: Churn 3:   301-308(303)
#14: Post-Churn lookup (match):   189-195(190)
#15: Post-Churn lookup (miss):   189-193(190)
#16: Post-Churn lookup (random):   499-513(503)

speed 100 runs, min-max(avg):
#01: Initial insert:   211-218(212)
#02: Initial lookup (match):   161-166(162)
#03: Initial lookup (miss):   157-162(158)
#04: Initial lookup (random):   452-460(454)
#05: Initial delete all:   126-135(127)
#06: Initial re-inserting:   193-201(194)
#07: Deleting first half:   99-107(99)
#08: Adding (a different) half:   143-190(144)
#09: Lookup after half-change (match):   183-195(184)
#10: Lookup after half-change (miss):   197-203(198)
#11: Churn 1:   271-278(274)
#12: Churn 2:   280-287(282)
#13: Churn 3:   277-285(279)
#14: Post-Churn lookup (match):   171-175(171)
#15: Post-Churn lookup (miss):   174-178(175)
#16: Post-Churn lookup (random):   525-552(528)

stringspeed 100 runs, min-max(avg):
#01: Initial insert:   300-343(308)
#02: Initial lookup (match):   98-136(99)
#03: Initial lookup (miss):   73-102(75)
#04: Initial lookup (random):   230-282(233)
#05: Initial delete all:   66-102(69)
#06: Initial re-inserting:   62-99(64)
#07: Deleting first half:   43-52(43)
#08: Adding (a different) half:   101-156(106)
#09: Lookup after half-change (match):   114-156(120)
#10: Lookup after half-change (miss):   94-103(95)
#11: Churn 1:   98-105(99)
#12: Churn 2:   96-104(98)
#13: Churn 3:   174-184(176)
#14: Post-Churn lookup (match):   93-112(94)
#15: Post-Churn lookup (miss):   77-107(79)
#16: Post-Churn lookup (random):   229-265(232)

strset: new module using critbit trees.

Not as fast as using htable, but simple and provides order and prefix
ops.

str: fix warnings.

Firstly, -Wwrite-strings makes string literals const, secondly, we mustn't
define str_strstr etc in terms of themselves!

str: relicense to public domain.

LGPL is overkill for trivial wrappers like this.

ccanlint: more tweaks to example mangling.

Note where previous analysis said the code was outside a function, and
fix double new-line.  Also, treat end of comment as end of statement.

typesafe_cb: fix example macro ordering in typesafe_cb_preargs documentation.

jmap: use ccan/tcon and always be typesafe.

This handles both pointer and integer types using ccan/tcon.

jbitset: rename to jset, use ccan/tcon

It's now a completely generic set implementation, and uses ccan/tcon
to always be typesafe.  It handles both integer and pointer types.

tlist: use ccan/tcon

No real change for users.

tcon: routines for creating typesafe generic containers

ccanlint: fix output for async commands.

Previously, it was always "", since we left the nul terminator at the
start.

tdb2: allow readonly changes even while holding locks.

This happens in SAMBA with the TDB_VERSION1, presumably due to a
read-only traverse nested inside a normal traverse (since it doesn't
occur without TDB_VERSION1).

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

tdb2: add error conversion functions.

This clarifies the code a little, but also provides a more explicit
mechanism which can be used to debug error handling (by introducing
tdb_err_t and making it a pointer type).

ccanlint: run tests in parallel

Measuring ccanlint -d ccan/tdb2 on my dual core hyperthread laptop gives:
Before: 5:30
After: 3:31

tdb2: make tests work in parallel.

Lazy cut & paste of tdb names causes failure when we run in parallel.

ccanlint: compile tests with coverage in parallel

Measuring ccanlint -d ccan/tdb2 on my dual core hyperthread laptop gives:
Before: 5:59
After: 5:30

ccanlint: compile tests in parallel

Measuring ccanlint -d ccan/tdb2 on my dual core hyperthread laptop gives:
Before: 6:47
After: 5:59

ccanlint: infrastructure to run commands async.

We use the lbalance module to figure out how many to run in parallel.

tools: fix realloc bug.

Reallocing smaller can move the pointer; certainly valgrind detects
it.  Found while chasing intermittant errors on "make fastcheck".

ttxml: zero terminate the buffer after checking it was allocated

ttxml: covering my shame

ttxml: modified it to use a smaller buffer during testing

ttxml: ccanlint fixes finished

Meets all of the requirements of ccanlint.
Code coverage of the tests covers everything except for a malloc() failure.
Added some xml files for the tests to work on.

ttxml: added drop static keyword

ttxml: Passes Valgrind now

Removed the last references of the old buffering method. Should be
stable now. Time to write some proper testing.

ttxml: Rplaced ratchet buffer with regular buffer, 20x speed increase

tdb2: fix error handling for tdb1_transaction_commit.

tdb_repack() returns an enum TDB_ERROR, whereas
tdb1_transaction_commit is expected to return 0 or -1.

tdb2: don't return -1 (ie. TDB_ERR_CORRUPT) on transaction write fail.

A left-over -1 return; should be returning ecode (probably TDB_ERR_IO).

tdb2: fix prototypes which return enum TDB_ERROR.

Since enums and ints are compatible in C, the compiler didn't warn
that our prototypes for these functions disagreed with the
definitions.

tdb2: set tdb_error() on tdb_transaction_prepare_commit.

tdb2: enhance tdb1 porting document.

tdb2: delete old tdb1 tests.

These two tdb1-specific tests have been superceded by the TDB_VERSION1
flags used in the main tests.

tdb2: test: Speed up run-01-new_database.

Don't run tdb_check with failtest on, since it is very slow.  Do the
tdb_check w/ failtest in a new test, but skip MMAP suppression which
doesn't add much and slows down valgrind a lot.

Before this change run-01-new_database took 40 seconds (under
valgrind), after it takes 8 seconds, and run-12-check takes 3
seconds).

tdb2: speed up testing.

The time to run tests under valgrind has become excessive; particularly
the failure tests which fork().   Thus we cut down testing:

1) api-94-repack: reduce from 234 seconds to 2 seconds by cutting
   iterations, despite adding TDB_VERSION1 tests.

2) api-missing-entries: reduce from 17 seconds to under 1 second by
   not checking db inside loop, but at end.

This reduces the total ccanlint time from 729 to 489 seconds.

tdb2: test: convert (non-invasive) run tests to api tests.

This reduces compilation time, since these are merely linked with the
pre-built module, rather than recompiling it into the test (which
allows for fancy things like failtest).

This reduces the test compile time down from about 62 seconds to 45
seconds.  Since ccanlint compiles tests three times (once normally,
once with coverage, and once with reduced config.h) this makes a
difference: we go from 780 seconds to 729 seconds.

tdb2: test: fix run-57-die-during-transaction.c to be more efficient.

We track malloc and free, but we didn't catch the free() inside
external_agent, which means that our list of allocations keeps
growing.  Particularly under valgrind, which re-uses memory less than
the glibc allocator.

tdb2: don't continue if tdb1_find fails.

The TDB1 code's tdb1_find() returns 0 on error; the callers should
not assume that the error means that the entry wasn't found, but use
last_error to determine it.

This was found by looking at how long the failure path testing for
test/run-10-simple-store.c was taking under valgrind, ie:

valgrind -q ./run-10-simple-store --show-slowest

This change dropped the time for that test from 53 seconds to 19
seconds.

tdb2: test: try (almost) all tests with TDB_VERSION1 flag.

There are some minor changes required, in particular:

1) Make sure lockcheck understands tdb1 allrecord lock upgrades.
2) Handle tdb1 sequence number jumps: various operations increment the
   sequence number twice, especually tdb_append.
3) Don't test fail on unlock, since it gets triggered with traversal on the
   tdb1 backend (we didn't actually ever test this case for tdb2).
4) Move clear_if_first to offset 4, to match tdb1.

tdb2: log allocation failures in tdb1 backend.

The TDB2 tests are stricter about this; they want every error logged.

tdb2: fix bogus error from tdb_unlockall() after fork in tdb1 backend.

We're always allowed to unlock after a fork; by setting the count to 0
before calling the generic unlock function we don't trigger the pid
check.

tdb2: check lock owner in tdb1 backend.

This reports errors if we fork() while holding a lock, or misuse a tdb
which we have dual-opened.

tdb2: return TDB_ERR_RDONLY from transactions on R/O databases, log nesting

Rather than rturning TDB_ERR_EINVAL, return TDB_ERR_RDONLY, and log
when we fail due to nesting.

tdb2: add stats to tdb1 backend.

It's actually quite a good fit; we use compare_wrong_bucket for dead
records, which is kind of correct (they should be in the free list).

tdb2: increment seqnum on tdb_wipe_all in tdb1 backend.

tdb2: log an error when calling tdb_store() on read-only TDB in tdb1 backend.

tdb2: catch errors in tdb1_needs_recovery()

The tdb1 backend simply returns "true" if there's an error determining
if a tdb needs recovery.  But this leads failtest down a rabbit hole;
it's better to return the error at this case (and makes for better for
diagnostics, since they will come from the first fault, not later in
tdb1_transaction_recover().

tdb2: add tdb_attribute_tdb1_max_dead

This allows us to simulate the old "volatile" flag for tdb1.  It's not
necessary for tdb2.

As this is the last function in tdb1.h, we remove that file.

tdb2: expose and document tdb1_incompatible_hash.

tdb2: make tdb1_null static.

It's only used in two files, make it static in one and do it manually
in the other.

tdb2: tdb_repack

Move the tdb1_repack() code into the core, make it general, rename to
tdb_repack().

It's generic code: copy database into temporary, wipe it, copy back.

tdb2: unify tdb1_wipe into tdb_wipe.

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_get_seqnum/tdb1_increment_seqnum into tdb_get_seqnum/tdb_inc_seqnum

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_firstkey/tdb1_nextkey into tdb_firstkey/tdb_nextkey.

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_check and tdb1_summary into tdb_check and tdb_summary.

Switch on the TDB_VERSION1 flag.  Also, change tdb1_check's checkfn argument
to return an error code (and set tdb->last_error accordingly).

tdb2: unify tdb1_transaction_start etc. into tdb_transaction_start.

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_parse_record into tdb_parse_record

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_chainlock et al. into tdb_chainlock

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_traverse into tdb_traverse

Switch on the TDB_VERSION1 flag; we now only do a tdb1_traverse_read on a
read-only database, as there is no tdb2 equivalent.

tdb2: unify tdb1_store into tdb_store

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_delete into tdb_delete.

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_append into tdb_append

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_fetch into tdb_fetch

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_store into tdb_store

Switch on the TDB_VERSION1 flag.

tdb2: unify tdb1_open into tdb_open

Finally, we gut tdb1_open() to the tdb1-specific parts, and call it
from tdb_open if they specify the TDB_VERSION1 flag or the version is
a TDB1.

We also unify tdb_close(), based on the TDB_VERSION1 flag.

Note that tdb_open(TDB_VERSION1) will fail on an existing tdb if it's
a TDB2.

tdb2: disallow SEED attribute with TDB_VERSION1.

It also only makes sense with O_CREAT.

tdb2: add TDB_ATTRIBUTE_TDB1_HASHSIZE

This replaces the tdb1_open "hash_size" argument.  It will only be
valid when you call tdb_open() with O_CREAT in open_flags, and
TDB_VERSION1 in tdb_flags.

tdb2: make tdb1_open use attributes for logging, hash function.

This brings it closer to tdb_open(), so we can unify more easily.

tdb2: make jenkins_hash function non-static, rename to tdb_jenkins_hash.

We're going to need access to it from tdb1_open, so expose it now.
It's better in hash.c anyway.

tdb2: remove double-open detection for TDB1 databases.

This is a percursor to unifying with tdb_open() from tdb2, which handles
this itself.

tdb2: merge tdb1_context into tdb_context.

Finally, we split out the tdb2-specific parts of tdb_context, and put
them into a "tdb2" sub-struct; the tdb1 parts go into a "tdb1"
sub-struct.  We get rido of tdb1_context and use tdb_context
everywhere.

tdb2: use tdb->flags & TDB_RDONLY instead of tdb->read_only for TDB1 code.

There's also a semantic change here: for tdb1, being read-only meant no
locking, and it was an error to try to lock a r/o database.  For TDB2, you'd
need to specify TDB_NOLOCK, which suppresses locking silently.

tdb2: Make TDB1 use the same tdb_hash() wrapper as TDB2

This means converting the tdb1 inbuilt hash functions to the
tdb2-style, so they return 64 bit.  We truncate to 32 bit everywhere
but in tdb_check() which needs to do so explicitly.

tdb2: don't cancel transactions on lock failures in tdb1 backend.

In TDB2, the user can override locking functions, so they may
deliberarely fail (eg. be non-blocking) expecting to retry.

For this reason, the TDB2 API requires the caller to cancel the
transaction if tdb_transaction_prepare_commit() fails.

tdb2: suppress tdb1 backend logging when locking returns EINTR or EAGAIN

The TDB1 code logs multiple times on errors; we must prevent that in
the limited case where locking fails.  With TDB2, this can happen due
to the lock function attribute, where the user supplies replacement
locking functions which are allowed to return with errno EAGAIN or
EINTR for various special-effects.  Flooding the logs for this is
unfriendly.

tdb2: make tdb1 use same low-level lock functions.

This means they will use the TDB_ATTRIBUTE_FLOCK functions, and get automatic
reopen support.

tdb2: Make tdb1 use the tdb_file structure.

Because tdb2 allows multiple opens of the same TDB, we separate out
the file information from the struct tdb_context.  Do the same for
tdb1.

tdb2: add TDB_VERSION1 flag.

This will be set for old TDBs; we can start distinguishing paths based
on it now.

tdb2: Make TDB1 code use TDB2's open flags.

This means getting rid of TDB_VOLATILE (perhaps we should use an
attribute for that?), TDB_INCOMPATIBLE_HASH (use the
tdb_attribute_hash for that) and TDB_CLEAR_IF_FIRST (use the
tdb_attribute_openhook for that).

We also get rid of TDB_DISALLOW_NESTING: that's the default for TDB2.

tdb2: approximate INCOMPATIBLE_HASH flag with tdb1_incompatible_hash()

Rather than leak TDB_INCOMPATIBLE_HASH through to the TDB2 API, we make
it that if they use the tdb1_incompatible_hash function as their hash,
then we treat it as if they had specified the TDB_INCOMPATIBLE_HASH
flag (ie. we mark the header so it's unusable by tdb < 1.2.6).

This precludes the possibility of using TDB_INCOMPATIBLE_HASH with a
custom hash function: that used to allow the user to ensure that old TDB
versions couldn't open the TDB file (and recent ones check the header to
ensure they're using the right hash).  But that's a small loss.

tdb2: Make tdb1 share tdb_store flags, struct tdb_data and TDB_MAGIC_FOOD.

tdb2: make TDB1 code use tdb2's TDB_ERROR and tdb_logerr()

To do this, we make sure that the first few fields of tdb1_context and
tdb_context are the same.

This sweep also fixes up a few paths where we weren't setting
tdb->ecode before our old logging function.

tdb2: make tdb1 headers include tdb2 headers.

They're about to start sharing TDB2's definitions.

tdb2: rearrange tdb_context layout so tdb1_context can match

By moving all the parts of struct tdb_context which logging and
locking use to the beginning of the structure, we can make
tdb1_context match, and thus pass that directly to the tdb_logerr()
function, and later the locking functions.

This is only necessary until we unify tdb1_context and tdb_context.

tdb2: remove TDB1 TDB_NO_FSYNC environment variable hack.

The caller should do this: the SAMBA compatibility later does.

tdb2: get rid of TDB1 mark and nonblock functions.

We do this using hooks in tdb2.

tdb2: remove _PUBLIC_ in tdb1 functions.

They'll all be accessed via the tdb2 API.

tdb2: Remove unused tdb1 functions.

We're going to use TDB2's API, so some TDB1 APIs are obviously unnecessary.
We also get rid of USE_RIGHT_MERGES and TRACE code.

tdb2: test: import tdb1's tests.

The main change is to s/tdb/tdb1_/ everywhere.

tdb2: include tdb1 source in tests.

Since we've renamed everything in tdb1, they won't clash.

tdb2: import TDB1 code.

We import the entire codebase, putting a "tdb1_" prefix on the files
and changing the "tdb_" prefix to "tdb1_" everywhere.

The next patches will gradually merge it with the TDB2 code where
necessary.

tdb2: make tests include a single mega-header to simplify future patches

This lets us add the new files to a single place.

tdb2: tdb_foreach()

Create an iterator over every open tdb (not internal TDBs).  This is
useful for re-establishing the tdb1-style active lock for
CLEAR_IF_FIRST.

tdb2: keep link of every non-internal tdb.

Instead of a per-file linked list, use a per-tdb list.  This is needed
for tdb_foreach().

tdb2: save openhook, allow tdb_get_attribute() on it.

This makes it easy to call it again after a fork(), such as for
re-establishing the CLEAR_IF_FIRST files locks.

tdb2: add TDB_RDONLY flag, allow setting/unsetting it.

You can only unset it if the TDB was originally opened O_RDWR.

Also, cleaned up error handling in tdb_allrecord_lock() so we only get
one log message on a r/o database.

tdb2: return TDB_ERR_RDONLY if trying to start a transaction on a R/O tdb.

This is more accurate than returning TDB_ERR_EINVAL.

tdb2: save open_flags instead of mmap_flags.

It's more consistent with what tdb1 does, and slightly more encapsulated.

tdb2: Hand error code to logging function.

Since we've deprecated tdb_error() function (and it didn't work right
from inside the logging function anyway, since we didn't set
tdb->ecode yet) we need to hand it to the log function.

tdb2: move transaction lock

Make it the same offset as TDB1.  This isn't strictly necessary, but
it would allow for total unification later, since TDB1 and TDB2's
transaction code is otherwise completely compatible.

tdb2: enforce TDB_CONVERT

If the caller actually specifies TDB_CONVERT, fail if the TDB does not
need conversion.  It's unusual for the user to specify TDB_CONVERT
(it's auto-detected) but better to be strict.