ciniparser: Separate summary line and description text for metadata

block_pool: Change metadata layout so initial description is all on one line.

With the original layout, we got:
Summary:
An efficient allocator for blocks that don't need to be
....
Description:
resized or freed.

ccanlint: neaten info_summary_single_line with new doc_section info.

ccanlint: keep mapping back to original source line for doc_extract

Makes reporting of documentation easier.

ccanlint: add test case for metadata summary line on a single separate line.

htable: fix type of cmpfn in htable_type

It in fact takes an object and a key to compare, not two keys.

The test case had the key as first element of the object, so it worked,
but ccanlint lost track of module dependencies due to this bug, and thus
would build submodules multiple times.

rbtree: fix allocation failre paths.

rbtree: don't use temporary context to destroy rbtree

It leads to a memory leak if the allocation fails (as we reparent onto NULL).
Also, the extra allocation in the failure path increases test time for
failtest (under valgrind) by a factor of 2.

rbtree: use failtest to check handling of allocation failures.

Unfortunately this means we have to reduce run-many from 1000 nodes to 100
(as forking under valgrind is really slow: test takes about 2 minutes with
100 nodes).

rbtree: fix memory leak in tests

The data is not made a child of the tree: the nodes are made children of the
data.  So we must explicitly free the data objects.

rbtree: vary insert and delete orders in test

This covers more code than simply doing an ordered delete/insert.

talloc: allow replacement allocator

This allows us to both allocators which handle failure themselves, and
allocators which insert failures.

talloc: fixed a use after free error

(Import from SAMBA commit 6f51a1f45bf4de062cce7a562477e8140630a53d):

this is the minimal fix for the problem Rusty found. I previously
thought that the best fix would be to change tc->parent to be valid
for all pointers, but that is expensive for realloc with large numbers
of child pointers, which is much more commmon than I expected it to
be.

talloc: use failtest to test failure paths.

failtest: new module.

A module designed to help test "never fails" functions like malloc.

tap: add fail callback

This is useful for failtest, so we can abort on first failure.

ccanlint: fix and simplify depends-accurate (with strreg)

ccanlint: fix total score for running examples

Don't count examples which didn't compile (expected, as we mangle them in
various different ways).

ccanlint: fix uninitialized variable

ccanlint: use strreg for section extraction.

Makes it simpler and clearer.

Makefile: append git revision to "make scores"

Good for testing ccanlint changes.

str_talloc: strreg

Useful wrapper for extended POSIX regular expressions.

str: strcount

Useful routine to count number of matches in a string.

str: clean up tests so ccanlint doesn't complain about memory leaking.

ccanlint: use positive description for test_pass_valgrind_noleaks

A bit more awkward, but more consistent with everything else.

ccanlint: print keys in output

Since test keys are used for --target=, this is useful.

ccanlint: rename files to match keys

ccanlint: rename structures to match keys

ccanlint: list dependencies by key

Joey Adams also pointed out that we should use strings for the dependency
lists.  Moving them into the structure also somewhat simplifies it.

ccanlint: rename test keys

Joey Adams rightly points out that the current keys are a mess: ideally the
filenames, test keys and structure names in ccanlint should be the same.

First step is to make the test names all regular, of basic form <noun>_<verb>
(eg "tests_exist" rather than "has-tests").

Add scores/ directory to .gitignore.

ccanlint: added --test-dep-graph option

This option prints the dependency graph of ccanlint's tests
in Graphviz .dot format.

Sample usage:

ccanlint --test-dep-graph | dot -Tpng > out.png && eog out.png

ccanlint: fix segfault caused by tests not depending on the "info" test.

These tests:

"depends-exist"      (compulsory_tests/check_depends_exist.c)
"info-documentation" (tests/has_info_documentation.c)

used m->info_file without checking if it was NULL,
leading to a segfault when no _info file was present.

Some other tests also used m->info_file without depending on "info",
but are taken care of indirectly by this patch.

opt: Fix warnings with gcc-4.5 (same approach as commit 6535bde)

&*ptr is used in some other macros, but at a glance, they look like
cases where the pointer shouldn't be NULL .  Didn't change those,
and if we get more warnings, we'll cross that bridge when we get to it.
For now, I suppose they are just free NULL checks.

daemonize: set stderr to /dev/null.

daemonize: make valgrind happy.

daemonize: use BSD-MIT as License: string in _info

The parenthesized thing is confusing and ccanlint dislikes it.

ccanlint: allow BSD-MIT for MIT license.

There are a large number of BSD variants out there, be explicit.

ccanlint: fix parsing bug which believes lines starting with - are a section header.

ccanlint: have valgrind fail with an error, always

The upcoming failtest module can only tell that a child failed when it
exits with a non-zero error.  So we need this, although it means for ccanlint
it still needs to look at output to distinguish a memory leak from a real
error.

ccanlint: compile modules required by examples.

If an example #includes <ccan/foo/...> we assume it needs module foo,
but we would fail instead of building it if it isn't built.

ccanlint: make get_manifest cache manifests

As we start doing more building of dependencies, this saves us effort.

compiler: NORETURN

tlist: typesafe variant of list module.

I chose not to do the "macro creates set of routines" approach, as
we can be almost as safe with a struct containing a pointer to the member
type.

list: LIST_HEAD_INIT

I find hiding the declaration in LIST_HEAD() a bit weird.

list: improve test coverage to 100%

In particular, we test the corruption cases.

list: list_del_from()

Deletion from a specific list.

list: test CCAN_LIST_DEBUG=1 case

list: rename debug_list to list_debug, use list_check_node in list_del

When CCAN_LIST_DEBUG was defined, we were previously calling
list_check() in list_del instead of list_check_node(), which caused a
warning.

We also should stick within the "list_" prefix namespace, so rename
"debug_list" to "list_debug".

list: implement list_check_node to check list from node rather than head

config.h: HAVE_FLEXIBLE_ARRAY_MEMBER

ccanlint: give a bonus for 100% code coverage

tdb: add test for tdb_summary

tdb: remove tally dependency

We lose the histograms, but this prepares it for upstream merge.

tdb: fix uncoalesced record count in tdb_summary.

One free record is not "uncoalesced".

tdb: combine dead_space helper from summary.c and check.c

Remove code duplication, and allow unit tests (which #include both).

typesafe_cb: Fix warnings with gcc-4.5:

Test compiled with warnings:
/home/rusty/devel/cvs/ccan/ccan/typesafe_cb/test/compile_ok-typesafe_cb-NULL.c:/home/rusty/devel/cvs/ccan/ccan/typesafe_cb/test/compile_ok-typesafe_cb-NULL.c: In function ‘main’:
/home/rusty/devel/cvs/ccan/ccan/typesafe_cb/test/compile_ok-typesafe_cb-NULL.c:18:2: warning: taking address of expression of type ‘void’
/home/rusty/devel/cvs/ccan/ccan/typesafe_cb/test/compile_ok-typesafe_cb-NULL.c:18:2: warning: taking address of expression of type ‘void’
/home/rusty/devel/cvs/ccan/ccan/typesafe_cb/test/compile_ok-typesafe_cb-NULL.c:18:2: warning: taking address of expression of type ‘void’
/home/rusty/devel/cvs/ccan/ccan/typesafe_cb/test/compile_ok-typesafe_cb-NULL.c:18:2: warning: taking address of expression of type ‘void’
/home/rusty/devel/cvs/ccan/ccan/typesafe_cb/test/compile_ok-typesafe_cb-NULL.c:18:2: warning: taking address of expression of type ‘void’
/home/rusty/devel/cvs/ccan/ccan/typesafe_cb/test/compile_ok-typesafe_cb-NULL.c:18:2: warning: taking address of expression of type ‘void’
/home/rusty/devel/cvs/ccan/ccan/typesafe_cb/test/compile_ok-typesafe_cb-NULL.c:18:2: warning: taking address of expression of type ‘void’
/home/rusty/devel/cvs/ccan/ccan/typesafe_cb/test/compile_ok-typesafe_cb-NULL.c:19:2: warning: taking address of expression of type ‘void’

ccanlint: use valgrind options when debugging too

If they specify valgrind options in their _info, we should use them when
running with --db-attach=yes, too.

ccanlint: report valgrind "definite" leaks.

This is complicated by valgrind's limited options, and our desire not to run
valgrind twice (it's already the slowest part of the tests).

Ideally I'd like a different error code for each kind of error.  I
could parse and pretty-print the XML output, but instead I just parse
the human-readable (which is fragile).

ccanlint: fix bogus strerror printing when unknown test handed to --target

ccanlint: fix error with --target=build

It requires that we build the objects first.

rbtree: remove unused variable in tests.

rb_tree: fix trbt_delete

trbt_delete32() was broken and caused SEGV as soon as you tried to
delete an object from a tree.

Rework trbt_delete32() to instead just call talloc_free() instread of trying
to call delete_node() directly.
This makes the "from_destructor" argument to delete_node() redundant
so that parameter is removed too.

Signed-off-by: Ronnie Sahlberg <sahlberg@lenovo-laptop.(none)>

configurator: warnings count as failures too.

Unfortunately, gcc only warns if it sees an unknown attribute (in this case, gcc 4.1 vs "cold").

ccanlint: fix compile on x86-64

cc -g -Wall -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -I. -MD -Werror   -c -o tools/ccanlint/tests/examples_run.o tools/ccanlint/tests/examples_run.c
cc1: warnings being treated as errors
tools/ccanlint/tests/examples_run.c: In function ‘scan_forv’:
tools/ccanlint/tests/examples_run.c:37: warning: passing argument 2 of ‘__builtin_va_copy’ discards qualifiers from pointer target type
tools/ccanlint/tests/examples_run.c:43: warning: passing argument 4 of ‘scan_forv’ from incompatible pointer type
tools/ccanlint/tests/examples_run.c:52: warning: passing argument 4 of ‘scan_forv’ from incompatible pointer type
tools/ccanlint/tests/examples_run.c:60: warning: passing argument 4 of ‘scan_forv’ from incompatible pointer type
tools/ccanlint/tests/examples_run.c: In function ‘scan_for’:
tools/ccanlint/tests/examples_run.c:78: warning: passing argument 4 of ‘scan_forv’ from incompatible pointer type
make: *** [tools/ccanlint/tests/examples_run.o] Error 1

It really doesn't like constifying a va_arg, so remove the const declaration.

rbtree: add tests (which currently fail)

idtree: fix overflow for v. large ids on allocation and removal

Chris Cowan tracked down a SEGV in sub_alloc: idp->level can actually
be equal to 7 (MAX_LEVEL) there, as it can be in sub_remove.

idtree: fix right shift of signed ints

(Imported from SAMBA commit 2db1987f5a3a)

Right-shifting signed integers in undefined; indeed it seems that on
AIX with their compiler, doing a 30-bit shift on (INT_MAX-200) gives
0, not 1 as we might expect (THIS WAS WRONG, REAL FIX LATER).

The obvious fix is to make id and oid unsigned: l (level count) is also
logically unsigned.

(Note: Samba doesn't generally get to ids > 1 billion, but ctdb does)

Reported-by: Chris Cowan <cc@us.ibm.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

idtree: import fix from SAMBA source

(Imported from b53f8c187de8)

Author: Rusty Russell <rusty@rustorp.com.au>
Date:   Thu Jun 10 13:27:51 2010 -0700

Since idtree assigns sequentially, it rarely reaches high numbers.
But such numbers can be forced with idr_get_new_above(), and that
reveals two bugs:

1) Crash in sub_remove() caused by pa array being too short.
2) Shift by more than 32 in _idr_find(), which is undefined, causing
   the "outside the current tree" optimization to misfire and return NULL.

idtree: add unit test for ids around INT_MAX

This causes a SEGV on my laptop.

ccanlint: ignore comments when parsing examples.

We insert comments when we massage or combine examples; don't let these
throw off our analysis (as happened for idtree.h).

ccanlint: show example we actually compiled when we report warnings.

ccanlint: examples_compile depends on build, which depends on build_objs

We might as well use the compiled .o rather than all the little .o files.

ccanlint: fix usage of static funcs

Out-by-one error had us using character prior to declaration, eg, in
"static int *foo" we use "*foo".  This seems to compile, but is weird.

array: fix type introduced in handling !HAVE_TYPEOF

Commit da72623aec30 added a typo; ccanlint caught it, but doesn't consider
test compile failing to be fatal (it should!).

Merge branch 'tdb2'

tdb2: update documentation

Specifically the linked free tables, and reflect on the status of each
point of the design document.

tdb2: use separate magic constants for chain, htable and ftable entries

Rather than overloading TDB_USED_MAGIC and the hash value as we do now.
We also rename "free list" to the more-accurate "free table" everywhere.

tdb2: direct access during transactions.

Currently we fall back to copying data during a transaction, but we don't
need to in many cases.  Grant direct access in those cases.

Before:
$ ./speed --transaction 1000000
Adding 1000000 records:  2409 ns (59916680 bytes)
Finding 1000000 records:  1156 ns (59916680 bytes)
Missing 1000000 records:  604 ns (59916680 bytes)
Missing 1000000 records:  604 ns (59916680 bytes)
Traversing 1000000 records:  1226 ns (59916680 bytes)
Deleting 1000000 records:  1556 ns (119361928 bytes)
Re-adding 1000000 records:  2326 ns (119361928 bytes)
Appending 1000000 records:  3269 ns (246656880 bytes)
Churning 1000000 records:  5613 ns (338235248 bytes)

After:
$ ./speed --transaction 1000000
Adding 1000000 records:  1902 ns (59916680 bytes)
Finding 1000000 records:  1032 ns (59916680 bytes)
Missing 1000000 records:  606 ns (59916680 bytes)
Missing 1000000 records:  606 ns (59916680 bytes)
Traversing 1000000 records:  741 ns (59916680 bytes)
Deleting 1000000 records:  1347 ns (119361928 bytes)
Re-adding 1000000 records:  1727 ns (119361928 bytes)
Appending 1000000 records:  2561 ns (246656880 bytes)
Churning 1000000 records:  4403 ns (338235248 bytes)

tdb2: add write flag to tdb_direct

This is a precursor to direct access during transactions: they care about
whether we are going to read or write to the file.

tdb2: hash chaining

If we get enough hash collisions, we can run out of hash bits; this almost
certainly is caused by a deliberate attempt to break the tdb (hash bombing).

Implement chained records for this case; they're slow but will keep the
rest of the database functioning.

tdb2: use magic freetable value rather than different magic for coalescing

We have to unlock during coalescing, so we mark records specially to indicate
to tdb_check that they're not on any list, and to prevent other coalescers
from grabbing them.

Use a special free list number, rather than a new magic.

tdb2: compare the extra 11 hash bits in the header.

We already have 10 hash bits encoded in the offset itself; we only get
here incorrectly about 1 time in 1000, so it's a pretty minor
optimization at best.

Nonetheless, we have the information, so let's check it before
accessing the key.  This reduces the probability of a false keycmp by
another factor of 2000.

tdb2: add comparison stats

tdb2: clean up logging

Logged errors should always set tdb->ecode before they are called, and
there's little reason to have a sprintf-style logging function since
we can do the formatting internally.

Change the tdb_log attribute to just take a "const char *", and create
a new tdb_logerr() helper which sets ecode and calls it.  As a bonus,
mark it COLD so the compiler can optimize appropriately knowing that
it's unlikely to be invoked.

tdb2: remove truncated bit.

There was an idea that we would use a bit to indicate that we didn't have
the full hash value; this would allow us to move records down when we
expanded a hash without rehashing them.

There's little evidence that rehashing in this case is particularly
expensive, so remove the bit.  We use that bit simply to indicate that
an offset refers to a subhash instead.

tdb2: use direct access for tdb_read_off/tdb_write_off

This is one case where getting rid of tdb_get() cost us.  Also, we
add more read-only checks.

Before we removed tdb_get:
Adding 1000000 records:  6480 ns (59900296 bytes)
Finding 1000000 records:  2839 ns (59900296 bytes)
Missing 1000000 records:  2485 ns (59900296 bytes)
Traversing 1000000 records:  2598 ns (59900296 bytes)
Deleting 1000000 records:  5342 ns (59900296 bytes)
Re-adding 1000000 records:  5613 ns (59900296 bytes)
Appending 1000000 records:  12194 ns (93594224 bytes)
Churning 1000000 records:  14549 ns (93594224 bytes)

Now:
Adding 1000000 records:  6307 ns (59900296 bytes)
Finding 1000000 records:  2801 ns (59900296 bytes)
Missing 1000000 records:  2515 ns (59900296 bytes)
Traversing 1000000 records:  2579 ns (59900296 bytes)
Deleting 1000000 records:  5225 ns (59900296 bytes)
Re-adding 1000000 records:  5878 ns (59900296 bytes)
Appending 1000000 records:  12665 ns (93594224 bytes)
Churning 1000000 records:  16090 ns (93594224 bytes)

tdb2: remove tdb_get()

We have four internal helpers for reading data from the database:
1) tdb_read_convert() - read (and convert) into a buffer.
2) tdb_read_off() - read (and convert) and offset.
3) tdb_access_read() - malloc or direct access to the database.
4) tdb_get() - copy into a buffer or direct access to the database.

The last one doesn't really buy us anything, so remove it (except for
tdb_read_off/tdb_write_off, see next patch).

Before:
Adding 1000000 records:  6480 ns (59900296 bytes)
Finding 1000000 records:  2839 ns (59900296 bytes)
Missing 1000000 records:  2485 ns (59900296 bytes)
Traversing 1000000 records:  2598 ns (59900296 bytes)
Deleting 1000000 records:  5342 ns (59900296 bytes)
Re-adding 1000000 records:  5613 ns (59900296 bytes)
Appending 1000000 records:  12194 ns (93594224 bytes)
Churning 1000000 records:  14549 ns (93594224 bytes)

After:
Adding 1000000 records:  6497 ns (59900296 bytes)
Finding 1000000 records:  2854 ns (59900296 bytes)
Missing 1000000 records:  2563 ns (59900296 bytes)
Traversing 1000000 records:  2735 ns (59900296 bytes)
Deleting 1000000 records:  11357 ns (59900296 bytes)
Re-adding 1000000 records:  8145 ns (59900296 bytes)
Appending 1000000 records:  10939 ns (93594224 bytes)
Churning 1000000 records:  18479 ns (93594224 bytes)

ccanlint: build depends if necessary

Now it will build copies of other ccan deps if it can't find them.

tdb2: trivial optimization for free list

We currently only have one, so shortcut the case where we want our current
one.

tdb2: Add stats attribute.

This is good for deep debugging.

tdb2: enable transactions in tdbtorture

tdb2: stricter ordering on expansion lock

It's problematic for transaction commit to get the expansion lock, but
in fact we always grab a hash lock before the transaction lock, so it
doesn't really need it (the transaction locks the entire database).

Assert that this is true, and fix up a few lowlevel tests where it wasn't.

tdb2: remove all the dead code

I left much tdb1 code in various files for inspiration, and in case I needed
it later.  Now we have all the major features implemented, remove it.

tdb2: transaction support

This adds transactions to tdb2; the code is taken from tdb1 with minimal
modifications, as are the unit

tdb2: allow nesting of read locks on top of write locks.

If we have a write lock and ask for a read lock, that's OK, but not the
other way around.  tdb_nest_lock() allowed both, tdb_allrecord_lock() allowed
neither.

ccanlint: fix -x core dump

This wasn't fixed when we converted to ccan/opt in 8d70667887.

Unfortunately, unistd.h defines optarg, so the compiler didn't catch
this.

tdb2: relax locking to allow two free list locks at once

As long as they are in descending order.  This prevents the common case of:

1) Grab lock for bucket.
2) Remove entry from bucket.
3) Drop lock for bucket.
4) Grab lock for bucket for leftover.
5) Add leftover entry to bucket.
6) Drop lock for leftover bucket.

In particular it's quite common for the leftover bucket to be the same
as the entry bucket (when it's the largest bucket); if it's not, we are
no worse than before.

Current results of speed test:
$ ./speed 1000000
Adding 1000000 records:  13194 ns (60083192 bytes)
Finding 1000000 records:  2438 ns (60083192 bytes)
Traversing 1000000 records:  2167 ns (60083192 bytes)
Deleting 1000000 records:  9265 ns (60083192 bytes)
Re-adding 1000000 records:  10241 ns (60083192 bytes)
Appending 1000000 records:  17692 ns (93879992 bytes)
Churning 1000000 records:  26077 ns (93879992 bytes)

Previous:
$ ./speed 1000000
Adding 1000000 records:  23210 ns (59193360 bytes)
Finding 1000000 records:  2387 ns (59193360 bytes)
Traversing 1000000 records:  2150 ns (59193360 bytes)
Deleting 1000000 records:  13392 ns (59193360 bytes)
Re-adding 1000000 records:  11546 ns (59193360 bytes)
Appending 1000000 records:  29327 ns (91193360 bytes)
Churning 1000000 records:  33026 ns (91193360 bytes)

tdb2: use expansion heuristics from tdb1

This reduces the amount of expansion we do.

Before:
./speed 1000000
Adding 1000000 records:  23210 ns (59193360 bytes)
Finding 1000000 records:  2387 ns (59193360 bytes)
Traversing 1000000 records:  2150 ns (59193360 bytes)
Deleting 1000000 records:  13392 ns (59193360 bytes)
Re-adding 1000000 records:  11546 ns (59193360 bytes)
Appending 1000000 records:  29327 ns (91193360 bytes)
Churning 1000000 records:  33026 ns (91193360 bytes)

After:
$ ./speed 1000000
Adding 1000000 records:  17480 ns (61472904 bytes)
Finding 1000000 records:  2431 ns (61472904 bytes)
Traversing 1000000 records:  2194 ns (61472904 bytes)
Deleting 1000000 records:  10948 ns (61472904 bytes)
Re-adding 1000000 records:  11247 ns (61472904 bytes)
Appending 1000000 records:  21826 ns (96051424 bytes)
Churning 1000000 records:  27242 ns (96051424 bytes)

tdb2: shrink free header from 32 to 24 bytes.

This reduces our minimum key+data length to 8 bytes; we do this by packing
the prev pointer where we used to put the flist pointer, and storing the
flist as an 8 bit index (meaning we can only have 256 free tables).

Note that this has a perverse result on the size of the database, as our
4-byte key and 4-byte data now fit perfectly in a minimal record, so
appeding causes us to allocate new records which are 50% larger,
since we detect growing.

Current results of speed test:
$ ./speed 1000000
Adding 1000000 records:  23210 ns (59193360 bytes)
Finding 1000000 records:  2387 ns (59193360 bytes)
Traversing 1000000 records:  2150 ns (59193360 bytes)
Deleting 1000000 records:  13392 ns (59193360 bytes)
Re-adding 1000000 records:  11546 ns (59193360 bytes)
Appending 1000000 records:  29327 ns (91193360 bytes)
Churning 1000000 records:  33026 ns (91193360 bytes)

Previous:
$ ./speed 1000000
Adding 1000000 records:  28324 ns (67232528 bytes)
Finding 1000000 records:  2468 ns (67232528 bytes)
Traversing 1000000 records:  2200 ns (67232528 bytes)
Deleting 1000000 records:  13083 ns (67232528 bytes)
Re-adding 1000000 records:  16433 ns (67232528 bytes)
Appending 1000000 records:  2511 ns (67232528 bytes)
Churning 1000000 records:  31068 ns (67570448 bytes)