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.

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

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>

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>

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>

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.

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>

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>

With killing children, CLEAR_IF_FIRST can happen quite a bit.

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>

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>

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>

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>

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>

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>

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>

Rather than a boutique lock and a separate nest count, use our
newly-generic nested lock tracking for the transaction 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>

Factor out two loops which find locks; we are going to introduce a couple
more so a helper makes sense.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Move locking intelligence back into lock.c.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

In many places we check whether locks are held: add a helper to do this.

The _tdb_lockall() case has already checked for the allrecord lock, so
the extra work done by tdb_have_extra_locks() is merely redundant.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tdb_transaction_lock() and tdb_transaction_unlock() do nothing if we
hold the allrecord lock.  However, the two locks don't overlap, so
this is wrong.

This simplification makes the transaction lock a straight-forward nested
lock.

There are two callers for these functions:
1) The transaction code, which already makes sure the allrecord_lock
   isn't held.
2) The traverse code, which wants to stop transactions whether it has the
   allrecord lock or not.  There have been deadlocks here before, however
   this should not bring them back (I hope!)
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Because fcntl locks don't nest, we track them in the tdb->lockrecs array
and only place/release them when the count goes to 1/0.  We only do this
for record locks, so we simply place the list number (or -1 for the free
list) in the structure.

To generalize this:

1) Put the offset rather than list number in struct tdb_lock_type.
2) Rename _tdb_lock() to tdb_nest_lock, make it non-static and move the
   allrecord check out to the callers (except the mark case which doesn't
   care).
3) Rename _tdb_unlock() to tdb_nest_unlock(), make it non-static and
   move the allrecord out to the callers (except mark again).
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

The word global is overloaded in tdb.  The global_lock inside struct
tdb_context is used to indicate we hold a lock across all the chains.

Rename it to allrecord_lock.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

The word global is overloaded in tdb.  The GLOBAL_LOCK offset is used at
open time to serialize initialization (and by the transaction code to block
open).

Rename it to OPEN_LOCK.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Author: Volker Lendecke <vl@samba.org>
Date:   Tue Aug 12 22:31:52 2008 +0200

    Attempt to fix bug 5684
    
    With the ctdb checkin dde9f3f006 tdb optimized out write lock checks for
    write-enabled transaction. Sadly, this also removed the possibility to ever
    remove dead records left over from tdb_delete calls within a transaction.
    
    Tridge, please check this! Did dde9f3f006 have any reason beyond performance
    optimizations?
    
    Thanks,
    
    Volker
    (This used to be commit 3f884c4ae36f3260e63626bdd4989d9258ae6497)

Whitespace and C++-compatibility mainly.

This patch is made larger by moving the work out to a separate function: with -k, the parent can't run the ops itself but the children must do it.

This demonstrates some serious failings, which get cleaned up in
following patches.