tdb2: make head of free list point to last entry.

This allows for access to the end of the list, in case we need it
later (eg. moving free list entries to the end of the list after
failed coalescing?).

tdb2: speed up transaction code by making page size a constant.

Turning getpagesize() into a constant 4096 really helps gcc optimize, and
not just on 64 bit.

Here are the results of running "tools/speed --transaction --no-sync 2000000":

i386 with gcc 4.4.5:
Before:
$ ./speed --transaction --no-sync 2000000
Adding 2000000 records:  1195 ns (93594224 bytes)
Finding 2000000 records:  719 ns (93594224 bytes)
Missing 2000000 records:  429 ns (93594224 bytes)
Traversing 2000000 records:  523 ns (93594224 bytes)
Deleting 2000000 records:  901 ns (93594224 bytes)
Re-adding 2000000 records:  1032 ns (93594224 bytes)
Appending 2000000 records:  1711 ns (182801232 bytes)
Churning 2000000 records:  3233 ns (182801232 bytes)

After:
Adding 2000000 records:  868 ns (93594224 bytes)
Finding 2000000 records:  569 ns (93594224 bytes)
Missing 2000000 records:  369 ns (93594224 bytes)
Traversing 2000000 records:  406 ns (93594224 bytes)
Deleting 2000000 records:  674 ns (93594224 bytes)
Re-adding 2000000 records:  730 ns (93594224 bytes)
Appending 2000000 records:  1144 ns (182801232 bytes)
Churning 2000000 records:  2085 ns (182801232 bytes)

Here's the effect (average of 10) on x8664 with gcc 4.1.2, with an earlier
tree and 1000000:
Before:
Adding 830.1ns
Finding 428.3ns
Missing 250.3ns
Traversing 387.4ns
Deleting 588.8ns
Re-adding 737.2ns
Appending 1141.4ns
Churning 1792ns

After:
Adding 562.8ns
Finding 362.1ns
Missing 226.4ns
Traversing 276.5ns
Deleting 426.7ns
Re-adding 489.8ns
Appending 736.4ns
Churning 1112.7ns

tdb2: fix traversal bug in free list lock_and_alloc()

We keep looking even if the current best is exactly right.  This is
really bad, because our smaller free lists hold exactly one size: with
this bug we iterate to the end of the list before hitting the end and
deciding we can use it after all.

Before:
$ ./speed --transaction --no-sync 2000000
Adding 2000000 records:  1179 ns (93594224 bytes)
Finding 2000000 records:  694 ns (93594224 bytes)
Missing 2000000 records:  429 ns (93594224 bytes)
Traversing 2000000 records:  519 ns (93594224 bytes)
Deleting 2000000 records:  896 ns (93594224 bytes)
Re-adding 2000000 records:  1129 ns (93594224 bytes)
Appending 2000000 records:  1713 ns (182801232 bytes)
Churning 2000000 records:  32612 ns (182801232 bytes)

After:
$ ./speed --transaction --no-sync 2000000
Adding 2000000 records:  1195 ns (93594224 bytes)
Finding 2000000 records:  719 ns (93594224 bytes)
Missing 2000000 records:  429 ns (93594224 bytes)
Traversing 2000000 records:  523 ns (93594224 bytes)
Deleting 2000000 records:  901 ns (93594224 bytes)
Re-adding 2000000 records:  1032 ns (93594224 bytes)
Appending 2000000 records:  1711 ns (182801232 bytes)
Churning 2000000 records:  3233 ns (182801232 bytes)

tdb2: add --summary and logging to tools/speed.

This helps us see where the problems are.

tdb2: add --no-sync argument to speed.

Running speed with --transaction --no-sync means no locking or syncs
are done, so we can measure raw TDB speed.

tdb2: fix use after free on error message

We use "r" after we call tdb_access_release() when we find corruption
in the free list.  "r" may be a pointer into malloced memory, freed
by tdb_access_release().

tdb2: fix two transaction bugs.

One but were we didn't update the map_size if we expanded the
transaction but didn't create a new recovery area (most easily
reproduced by setting the TDB_NOSYNC flag).

Another out-by-one bug in transaction_direct where we would give
read-access to the underlying file despite the last block having been
modified.

Both these were found by tdbtorture.

tdb2: cleanups for tdbtorture, add more debugging and -S flag.

tdb2: actually implement tdb_error().

I'm still not sure it'll last into the final version, but finish the
implementation.

tdb2: fix tools warnings with -Wshadow and -Wcast-qual.

Samba uses these flags, so be friendly.

tdb2: avoid C++ reserved words (ie. private)

tdb2: check PID if we are holding a lock.

tdb1 has tdb_reopen/tdb_reopen_all, which you are supposed to call
after a fork().  But we can detect PID changes whenever we grab a lock,
which is to say, before we do anything.

We currently assume that pread and pwrite work, so the only problem
with fork() is if we are holding locks and expect them to still be
there in the child.  This is unusual, but most likely caused by a
fork() inside a transaction.  In such cases, allow the child to unlock
without complaint; they can then use the TDB as expected.

Performance before and after shows no measurable speed difference:

Total of 5 runs of tools/speed 100000:
Before:
Adding: 18899ns
Finding: 7040ns
Missing: 5802ns
Traversing: 6466ns
Deleting: 12607ns
Re-adding: 14185ns
Appending: 20770ns
Churning: 93845ns

After:
Adding: 18073ns
Finding: 6795ns
Missing: 5549ns
Traversing: 6333ns
Deleting: 12313ns
Re-adding: 13835ns
Appending: 20343ns
Churning: 92208ns

tdb2: tdb_lockall() and tdb_lockall_read() support.

We also change tdb_chainunlock not to return an error (as per the
other locking functions: we log a message, but don't return an error).

configure.h: HAVE_ISBLANK

This isn't on RHEL4, for example: isascii() and isblank() are not in
C89.

failtest: handle EINTR from poll.

I don't quite know why, but this started happening to me.  We should
handle it anyway.

ccanlint: fix listing of dependencies

gcc gave a warning:
tools/ccanlint/ccanlint.c:230:19: error: ‘c’ may be used uninitialized in this function

Which indicated that test dependency printing was broken: we need to
loop through the tests!  Also, we haven't parsed options yet, so
verbose is never true: move it to later and make it depend on -vvv.

Add configurator test for memmem()

memmem(), which searches for one bytestring in a longer
bytestring is one of those functions that should be standard, but
isn't.  This patch adds a ccan configurator test for the function
so that modules can use or replace it as necessary.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

iscsi: fix warnings with -Wwrite-strings

Simplest fix is to use const where possible, and use a different var for
asprintf and string literals in login.c.

darray: handle case where we don't have typeof.

Tests don't compile otherwise, so fix that up (ccanlint now tests with
reduced features, so this became clear).

tap: ccanlint fixups

Add a license tag (though it's a weird BSD variant), remove whitespace, and
avoid void pointer arithmetic.

ccanlint: fix compilation of API tests with coverage

They expect to be linked against the module objects.

crcsync: avoid arithmetic on void pointers

ccanlint: roughly handle multiple conditions on #if line.

Just grab the tokens for the simple case: this allows the ccanlint
reduce_features test to work on eg. ccan/cast.

ccanlint: exit with non-zero exit status if a test fails.

This means we change some minor tests to "never fail", eg. whitespace
or documentation tests.  Note that pass/fail is independent of the
score for a test.

compiler: fix -Wwrite-strings warning in example.

antithread: fix -Wwrite-strings warning in test, and trailing whitespace.

alloc: dont clash with libc's fls, avoid void pointer arithmetic

antithread: avoid arithmetic on void pointers

tools: fix up warnings with -Wwrite-strings.

Be a little more careful with const.

foreach: more const iteration fixes.

Shown up by -Wwrite-strings.

ccan: add -Wpointer-arith and -Wwrite-strings by default

Wpointer-arith is useful for spotting GCC-isms which do arithmetic on
void pointers.  Wwrite-strings treats string constants as const char *,
which is sane (but bad for legacy code).

alloc: avoid arithmetic on void pointers.

read_write_all: avoid arithmetic on void pointers.

opt: avoid function pointer arithmetic

Same fix as we used for ccan/typesafe_cb.

opt: fix memory leak in tests.

No only does this give us one more ccanlint point, it clears the way
to see if we introduce a *real* memory leak later.

opt: allow const arguments.

This need shows up most clearly with opt_usage_and_exit and gcc's
-Wwrite-strings, where string literals become "const char *".  Our
callbacks should take const void *: since we overload the arg field
already (to hold table size) it make sense to turn it into a proper
union.

opt: define NULL

Headers should stand alone; we use NULL, so we should make sure it's defined.

cast: fix cast of void * when we don't have GCC features.

I thought using sizeof() comparison to compare the types was clever,
but it doesn't work on void pointers, as sizeof(void) is illegal.

array_size: make sure tests work even without GCC features.

In this case, "work" means "fail to compile cleanly".

talloc: fix leak in test/run-set_allocator.c

failtest: print complete history when we detect a leak.

tdb2: fix arithmetic on void * pointer.

typesafe: fix warnings with gcc's -Wcast-qual

Don't implicitly cast away const in the tests.

typesafe: fix warnings with gcc's -Wpointer-arith

In particular, avoid doing arithmetic on NULL; decay the function to a
pointer using a trinary conditional instead.

tdb2: tdb_mkdata

It's common to want to create a struct tdb_data which contains a const
pointer, so add a helper to do so, and use it to clean up other -Wcast-qual
warnings.

tdb2: fix warnings with -Wcast-qual using ccan/cast.

cast: fix compilation with GCC's -Wcast-qual

Samba uses -Wcast-qual to warn about casting away const.  The kind of
coders who care about const correctness are likely to turn that option
on, so we should make sure it's compatible with cast_const().

tdb2: fix tools compilation.

tdb2: fix compile of test/run-check-callback.c

foreach: fix case where iterators are not on the stack.

The foreach garbage collection assumed that iterators were all on the
stack, but they could be on the heap or a global (or static) variable.
We can prevent the heap case by tricky use of macros to complain on
any iterator which isn't a single token, but we can't prevent
globals/statics.

So, if an iterator already seems to be "off" the stack, mark it as
such and simply never free it.

configurator: HAVE_STACK_GROWS_UPWARDS

foreach: allow a single argument to foreach_int() and foreach_ptr().

David Gibson noted that foreach requires more than one argument.
There's no particularly good reason for this, other than lack of
imagination on my part.

foreach: fix HAVE_FOR_LOOP_DECLARATION case.

tdb2: merge changes in design document.

tdb2: tdb_error()

This makes transition from tdb1 much simpler.

tdb2: TDB_SEQNUM and tdb_get_seqnum support.

As per TDB1, except that the sequence number is 63 bit.

tdb2: tdb_name and tdb_fd functions.

As per TDB1, with one enhancement: a non-NULL name argument passed to
tdb_open() with the TDB_INTERNAL flag is preserved so you can identify
internal TDBs too.

tdb2: remove tdb_null

We don't need this now, since we use explicit error numbers.

tdb2: tdb_deq: inline helper for comparing two struct tdb_data

Everyone writes their own, so provide a standard one.

tdb2: implement tdb_exists and tdb_parse_record

These are the same as the TDB1 functions; but note that there is no reliable
way to tell if tdb_exists() fails due to an error.  This simplifies the API,
but means you have to use tdb_fetch() if you really care.

tdb2: begin tdb1 to tdb2 porting guide.

tdb2: allow multiple opens of the same file.

Finally, we enable sharing of the struct tdb_file.  We add a reference count
so we can free the struct tdb_file when the last tdb is closed.

tdb2: set owner for locks

The last step before sharing struct tdb_file is to add a field to
identify which tdb context is holding each lock, so we can fail when
they conflict.

tdb2: rename tdb_lock_type to tdb_lock

Internal reshuffle which makes things shorter and neater.

tdb2: move mmap into struct tdb_file

It makes sense to share the mmap between multiple openers.

tdb2: move file operations into separate structure

This moves the fd and locking information into a new 'struct tdb_file',
opening the way for it to be shared by multiple tdb_open calls on the
same file.

tdb2: fix leak in test/run-remap-in-read_traverse.c

tdb2: move open routines into a separate file (open.c)

Simply tidying up.

tdb2: Implement tdb_get_flags, tdb_add_flag and tdb_remove_flag.

tdb2: make sure records with extra padding have a 0 byte.

As detailed in doc/design.lyx section 2.16 "Record Headers Are Not
Expandible", we make sure that if there is padding at the end of a record,
the first byte of padding is a zero.

tdb2: avoid writing uninitialized bytes in test/layout.c

tdb2: feature support.

As detailed in doc/design.lyx section 2.15 "Extending The Header Is
Difficult"; we add features_used and features_offered fields to the
header, so we can identify if we add new features, and then if someone
opens it who doesn't understand that feature.

tdb2: make tdb_check typesafe.

tdb2: typesafe traverse function

This make sure that the data being handed to the function in tdb_traverse
is the correct type.

tdb2: check for invalid flags in tdb_open.

This is vitally important for forwards compatibility.

tdb2: fix two bogus returns in check.c

Two missed cases in b21004624683 (tdb2: change API to return the error
value.)

tdb2: use vasprintf.

tdb2: use config.h instead of setting _XOPEN_SOURCE etc.

tdb2: update tools/speed.c, tools/tdbtool.c and tools/tdbtorture.c to new API

tdb2: clear bogus gcc uninitialized warnings with -O3

failtest: include config.h first

It's now important, since it defines _GNU_SOURCE.

ccanlint: fix gdb line in tests_pass helper.

Recent changes shifted line numbers in tap.c, so the break is now in
the wrong place.  We should probably have an explicit function we can
breakpoint instead.

tools: fix ctype.h and string usage.

Enable CCAN_STR_DEBUG in the default flags, so our tools get checked,
and fix up the resulting errors.

str: replacements for ctype functions.

The standard ctype.h variants will make you go insane if you
contemplate them for too long.

tap: fix isdigit and isspace usage.

isspace() and isdigit() want an unsigned value.

ciniparser: fix ctype.h usage, and lazy strrchr.

tolower(), toupper() and isupper want an unsigned value.  Also, fix
lazy cost-discarding inside strrchr for extra safety.

ccanlint: objects_build_with_stringchecks

If we detect any mention of a problematic string function, try compiling
the entire module with string debugging enabled.

str: provide checks for ctype.h char functions, and strstr and strchr functions.

In the former case, we were bitten by the fact that you don't pass a char
to isalpha() et al: you pass an int.  This means on most platforms you want
to do:

   if (isalpha((unsigned char)c)) ...

Insane?  Yes, but I assure you I'm not making this up.

Similarly, I've always wanted strstr, strchr and strrchr to return
const char * when given a const char * argument to search, to avoid
constness leak.

In both cases, the actual versions from the headers may be macros, so
we need to be very careful overriding them.  The result is that they
become out-of-line functions which is unacceptable for general
performance.

So we only activate these when CCAN_STR_DEBUG is defined.

build_assert: rename EXPR_BUILD_ASSERT to BUILD_ASSERT_OR_ZERO

Same thing (a BUILD_ASSERT which evaluates to zero), but there's a
strong preference for all modules to stick with their own names as
prefixes.

ccanlint: don't ever used pre-built modules as dependencies.

They're often out-of-date, and we're about to do special things to the
str module compile flags, so we don't *ever* want the default.

It doesn't add much to build times, and it eliminates a nasty source
of weird errors.

ccanlint: fix mangled output for 'make scores'

We need to flush stdout before forking.

tools: avoid needless post increment on size

Also add a note about a possible segfault.

tools: actually add non-source files to other_files in manifest

We don't use it for the moment, but Brad Hards noted that assigning to
dest ten continuing was pointless, revealing this bug.

alloc: avoid dead store to hdrlen

We only ever write to this variable, so can just be removed.

ciniparser: avoid dead store to sta

This is always overwritten later in the function.

ccan_tokenizer: avoid dead store

obe is always overwritten later.

tdb2: trivial spelling fixes

tdb: remove unused last_ptr

ciniparser: remove dead store

last is unconditionally set to zero later in this function.

alloc: remove unused variable

lp_bits was only ever written to.