ccan
9 years agoccanlint: use valgrind options when debugging too
Rusty Russell [Mon, 13 Dec 2010 08:15:24 +0000 (18:45 +1030)]
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.

9 years agoccanlint: report valgrind "definite" leaks.
Rusty Russell [Mon, 13 Dec 2010 08:15:25 +0000 (18:45 +1030)]
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).

9 years agoccanlint: fix bogus strerror printing when unknown test handed to --target
Rusty Russell [Mon, 13 Dec 2010 08:15:25 +0000 (18:45 +1030)]
ccanlint: fix bogus strerror printing when unknown test handed to --target

9 years agoccanlint: fix error with --target=build
Rusty Russell [Mon, 13 Dec 2010 08:23:14 +0000 (18:53 +1030)]
ccanlint: fix error with --target=build

It requires that we build the objects first.

9 years agorbtree: remove unused variable in tests.
Rusty Russell [Wed, 8 Dec 2010 02:05:46 +0000 (12:35 +1030)]
rbtree: remove unused variable in tests.

9 years agorb_tree: fix trbt_delete
Ronnie Sahlberg [Wed, 8 Dec 2010 01:00:35 +0000 (12:00 +1100)]
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)>
9 years agoconfigurator: warnings count as failures too.
Rusty Russell [Wed, 8 Dec 2010 00:44:21 +0000 (11:14 +1030)]
configurator: warnings count as failures too.

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

9 years agoccanlint: fix compile on x86-64
Rusty Russell [Wed, 8 Dec 2010 00:34:03 +0000 (11:04 +1030)]
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.

9 years agorbtree: add tests (which currently fail)
Rusty Russell [Tue, 7 Dec 2010 05:19:08 +0000 (15:49 +1030)]
rbtree: add tests (which currently fail)

9 years agoidtree: fix overflow for v. large ids on allocation and removal
Rusty Russell [Mon, 6 Dec 2010 03:12:13 +0000 (13:42 +1030)]
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.

9 years agoidtree: fix right shift of signed ints
Rusty Russell [Mon, 6 Dec 2010 03:12:00 +0000 (13:42 +1030)]
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>
9 years agoidtree: import fix from SAMBA source
Rusty Russell [Mon, 6 Dec 2010 03:00:59 +0000 (13:30 +1030)]
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.

9 years agoidtree: add unit test for ids around INT_MAX
Rusty Russell [Mon, 6 Dec 2010 02:22:19 +0000 (12:52 +1030)]
idtree: add unit test for ids around INT_MAX

This causes a SEGV on my laptop.

9 years agoccanlint: ignore comments when parsing examples.
Rusty Russell [Mon, 6 Dec 2010 02:21:40 +0000 (12:51 +1030)]
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).

9 years agoccanlint: show example we actually compiled when we report warnings.
Rusty Russell [Mon, 6 Dec 2010 02:20:45 +0000 (12:50 +1030)]
ccanlint: show example we actually compiled when we report warnings.

9 years agoccanlint: examples_compile depends on build, which depends on build_objs
Rusty Russell [Mon, 6 Dec 2010 02:19:31 +0000 (12:49 +1030)]
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.

9 years agoccanlint: fix usage of static funcs
Rusty Russell [Mon, 6 Dec 2010 02:18:18 +0000 (12:48 +1030)]
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.

9 years agoarray: fix type introduced in handling !HAVE_TYPEOF
Rusty Russell [Fri, 3 Dec 2010 12:23:52 +0000 (22:53 +1030)]
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!).

9 years agoMerge branch 'tdb2'
Rusty Russell [Wed, 1 Dec 2010 13:24:33 +0000 (23:54 +1030)]
Merge branch 'tdb2'

9 years agotdb2: update documentation
Rusty Russell [Wed, 1 Dec 2010 13:16:26 +0000 (23:46 +1030)]
tdb2: update documentation

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

9 years agotdb2: use separate magic constants for chain, htable and ftable entries
Rusty Russell [Wed, 1 Dec 2010 13:15:56 +0000 (23:45 +1030)]
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.

9 years agotdb2: direct access during transactions.
Rusty Russell [Wed, 1 Dec 2010 13:14:54 +0000 (23:44 +1030)]
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)

9 years agotdb2: add write flag to tdb_direct
Rusty Russell [Wed, 1 Dec 2010 13:14:14 +0000 (23:44 +1030)]
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.

9 years agotdb2: hash chaining
Rusty Russell [Wed, 1 Dec 2010 13:13:37 +0000 (23:43 +1030)]
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.

9 years agotdb2: use magic freetable value rather than different magic for coalescing
Rusty Russell [Wed, 1 Dec 2010 13:11:26 +0000 (23:41 +1030)]
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.

9 years agotdb2: compare the extra 11 hash bits in the header.
Rusty Russell [Wed, 1 Dec 2010 13:10:05 +0000 (23:40 +1030)]
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.

9 years agotdb2: add comparison stats
Rusty Russell [Wed, 1 Dec 2010 12:53:50 +0000 (23:23 +1030)]
tdb2: add comparison stats

9 years agotdb2: clean up logging
Rusty Russell [Wed, 1 Dec 2010 12:41:51 +0000 (23:11 +1030)]
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.

9 years agotdb2: remove truncated bit.
Rusty Russell [Wed, 1 Dec 2010 12:38:52 +0000 (23:08 +1030)]
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.

9 years agotdb2: use direct access for tdb_read_off/tdb_write_off
Rusty Russell [Wed, 1 Dec 2010 12:36:12 +0000 (23:06 +1030)]
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)

9 years agotdb2: remove tdb_get()
Rusty Russell [Wed, 1 Dec 2010 12:34:50 +0000 (23:04 +1030)]
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)

9 years agoccanlint: build depends if necessary
Rusty Russell [Tue, 23 Nov 2010 12:49:19 +0000 (23:19 +1030)]
ccanlint: build depends if necessary

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

9 years agotdb2: trivial optimization for free list
Rusty Russell [Tue, 23 Nov 2010 02:21:18 +0000 (12:51 +1030)]
tdb2: trivial optimization for free list

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

9 years agotdb2: Add stats attribute.
Rusty Russell [Wed, 1 Dec 2010 13:06:14 +0000 (23:36 +1030)]
tdb2: Add stats attribute.

This is good for deep debugging.

9 years agotdb2: enable transactions in tdbtorture
Rusty Russell [Tue, 23 Nov 2010 01:44:31 +0000 (12:14 +1030)]
tdb2: enable transactions in tdbtorture

9 years agotdb2: stricter ordering on expansion lock
Rusty Russell [Tue, 23 Nov 2010 01:43:59 +0000 (12:13 +1030)]
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.

9 years agotdb2: remove all the dead code
Rusty Russell [Tue, 23 Nov 2010 01:40:32 +0000 (12:10 +1030)]
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.

9 years agotdb2: transaction support
Rusty Russell [Tue, 23 Nov 2010 01:38:21 +0000 (12:08 +1030)]
tdb2: transaction support

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

9 years agotdb2: allow nesting of read locks on top of write locks.
Rusty Russell [Tue, 23 Nov 2010 01:37:29 +0000 (12:07 +1030)]
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.

9 years agoccanlint: fix -x core dump
Rusty Russell [Tue, 23 Nov 2010 01:36:31 +0000 (12:06 +1030)]
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.

9 years agotdb2: relax locking to allow two free list locks at once
Rusty Russell [Mon, 22 Nov 2010 02:13:00 +0000 (12:43 +1030)]
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)

9 years agotdb2: use expansion heuristics from tdb1
Rusty Russell [Mon, 22 Nov 2010 01:20:58 +0000 (11:50 +1030)]
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)

9 years agotdb2: shrink free header from 32 to 24 bytes.
Rusty Russell [Wed, 1 Dec 2010 13:22:43 +0000 (23:52 +1030)]
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)

9 years agotdb2: rename set_header to the more appropriate set_used_header.
Rusty Russell [Tue, 23 Nov 2010 03:10:59 +0000 (13:40 +1030)]
tdb2: rename set_header to the more appropriate set_used_header.

9 years agotdb2: Add speed test to tdb and tdb2
Rusty Russell [Wed, 1 Dec 2010 12:52:55 +0000 (23:22 +1030)]
tdb2: Add speed test to tdb and tdb2

Current results of speed test:
$ ./speed 1000000
Adding 1000000 records:  14726 ns (67244816 bytes)
Finding 1000000 records:  2844 ns (67244816 bytes)
Missing 1000000 records:  2528 ns (67244816 bytes)
Traversing 1000000 records:  2572 ns (67244816 bytes)
Deleting 1000000 records:  5358 ns (67244816 bytes)
Re-adding 1000000 records:  9176 ns (67244816 bytes)
Appending 1000000 records:  3035 ns (67244816 bytes)
Churning 1000000 records:  18139 ns (67565840 bytes)
$ ./speed 100000
Adding 100000 records:  13270 ns (14349584 bytes)
Finding 100000 records:  2769 ns (14349584 bytes)
Missing 100000 records:  2422 ns (14349584 bytes)
Traversing 100000 records:  2595 ns (14349584 bytes)
Deleting 100000 records:  5331 ns (14349584 bytes)
Re-adding 100000 records:  5875 ns (14349584 bytes)
Appending 100000 records:  2751 ns (14349584 bytes)
Churning 100000 records:  20666 ns (25771280 bytes)

vs tdb1 (with hashsize 100003):
$ ./speed 1000000
Adding 1000000 records:  8547 ns (44306432 bytes)
Finding 1000000 records:  5595 ns (44306432 bytes)
Missing 1000000 records:  3469 ns (44306432 bytes)
Traversing 1000000 records:  4571 ns (44306432 bytes)
Deleting 1000000 records:  12115 ns (44306432 bytes)
Re-adding 1000000 records:  10505 ns (44306432 bytes)
Appending 1000000 records:  10610 ns (44306432 bytes)
Churning 1000000 records:  28697 ns (44306432 bytes)
$ ./speed 100000
Adding 100000 records:  6030 ns (4751360 bytes)
Finding 100000 records:  3141 ns (4751360 bytes)
Missing 100000 records:  3143 ns (4751360 bytes)
Traversing 100000 records:  4659 ns (4751360 bytes)
Deleting 100000 records:  7891 ns (4751360 bytes)
Re-adding 100000 records:  5913 ns (4751360 bytes)
Appending 100000 records:  4242 ns (4751360 bytes)
Churning 100000 records:  15300 ns (4751360 bytes)

9 years agotdb2: fix tdb_check() return when free table entries missing.
Rusty Russell [Wed, 1 Dec 2010 12:36:56 +0000 (23:06 +1030)]
tdb2: fix tdb_check() return when free table entries missing.

It mistakenly returned -1 meaning "success".

9 years agotdb2: make tdb_check call check() function.
Rusty Russell [Wed, 1 Dec 2010 12:26:35 +0000 (22:56 +1030)]
tdb2: make tdb_check call check() function.

9 years agotdb2: make summary command handle recovery "dead zone"
Rusty Russell [Wed, 1 Dec 2010 13:21:41 +0000 (23:51 +1030)]
tdb2: make summary command handle recovery "dead zone"

We can run summary with a recovery area, or a dead zone.

9 years agotdb2: cancel transactions on tdb_close
Rusty Russell [Wed, 1 Dec 2010 13:18:42 +0000 (23:48 +1030)]
tdb2: cancel transactions on tdb_close

Otherwise we leak memory.

9 years agotdb2: handle chains of free tables
Rusty Russell [Wed, 17 Nov 2010 09:56:52 +0000 (20:26 +1030)]
tdb2: handle chains of free tables

This adds chains of free tables: we choose one at random at the start and
we iterate through them when they are exhausted.

Currently there is no code to actually add a new free table, but we test
that we can handle it if we add one in future.

9 years agotdb2: get rid of zones
Rusty Russell [Wed, 17 Nov 2010 09:55:41 +0000 (20:25 +1030)]
tdb2: get rid of zones

Zones were a bad idea.  They mean we can't simply add stuff to the end
of the file (which transactions relied upon), and there's no good heuristic
in how to size them.

This patch reverts us to a single free table.

9 years agotdb2: fix bucket search
Rusty Russell [Wed, 17 Nov 2010 10:00:07 +0000 (20:30 +1030)]
tdb2: fix bucket search

We were previously jumping straight from the first bucket to the end.

9 years agotdb2: only adjust size once when growing
Rusty Russell [Wed, 17 Nov 2010 09:52:19 +0000 (20:22 +1030)]
tdb2: only adjust size once when growing

We were adding 50% to datalen twice, so move it out of adjust_size and
make the callers do it.

We also add a test that the heuristic is working at all.

9 years agotdb2: remove tailer
Rusty Russell [Wed, 17 Nov 2010 09:50:35 +0000 (20:20 +1030)]
tdb2: remove tailer

We don't actually need it.

9 years agotdb2: fix tdb_chainlock
Rusty Russell [Mon, 15 Nov 2010 07:24:15 +0000 (17:54 +1030)]
tdb2: fix tdb_chainlock

We can't enlarge the lock without risking deadlock, so tdb_chainlock() can't
simply grab a one-byte lock; it needs to grab the lock we'd need to protect
the hash.

In theory, tdb_chainlock_read() could use a one-byte lock though.

9 years agotdb2: fix coalesce race #3
Rusty Russell [Mon, 15 Nov 2010 07:25:45 +0000 (17:55 +1030)]
tdb2: fix coalesce race #3

When we're coalescing, we need to drop the lock on the current free list, as
we've enlarged the block and it may now belong in a different list.

Unfortunately (as shown by repeated tdbtorture -n 8) another coalescing run
can do the coalescing while we've dropped the lock.  So for this case, we
use the TDB_COALESCING_MAGIC flag so it doesn't look free.

9 years agotdb2: add TDB_COALESCING_MAGIC to solve coalescing race.
Rusty Russell [Mon, 15 Nov 2010 07:25:34 +0000 (17:55 +1030)]
tdb2: add TDB_COALESCING_MAGIC to solve coalescing race.

A new special record marker to indicate coalescing is in progress.

9 years agotdb2: fix coalesce race #2
Rusty Russell [Mon, 15 Nov 2010 08:32:42 +0000 (19:02 +1030)]
tdb2: fix coalesce race #2

When we find a free block, we need to mark it as used before we drop the
free lock, even though we've removed it from the list.  Otherwise the
coalescing code can find it.

This means handing the information we need down to lock_and_alloc, which
also means we know when we're grabbing a "growing" entry, and can relax
the heuristics about finding a good-sized block in that case.

9 years agotdb2: coalescing race fix #1
Rusty Russell [Mon, 15 Nov 2010 07:10:47 +0000 (17:40 +1030)]
tdb2: coalescing race fix #1

When coalescing, we check the adjacent entry then lock its free list: we
need to *recheck* after locking, to make sure it's still in that free list.

9 years agotdb2: minor optimization for set_header
Rusty Russell [Mon, 15 Nov 2010 07:19:11 +0000 (17:49 +1030)]
tdb2: minor optimization for set_header

We actually only need the bottom 5 bits of the hash value, so don't waste
8 bytes passing it.

9 years agotdb2: hoist adjust_size
Rusty Russell [Mon, 15 Nov 2010 07:26:57 +0000 (17:56 +1030)]
tdb2: hoist adjust_size

We're going to want it in get_free() in the next patch, so move it upwards.
Trivial changes, too: add to size before min length check, and rename growing
to want_extra.

9 years agotdb2: clean up makefile for tools
Rusty Russell [Mon, 15 Nov 2010 07:07:03 +0000 (17:37 +1030)]
tdb2: clean up makefile for tools

9 years agotdb2: extra debugging checks
Rusty Russell [Mon, 15 Nov 2010 07:31:48 +0000 (18:01 +1030)]
tdb2: extra debugging checks

9 years agoccanlint: add ccanlint section to _info
Rusty Russell [Wed, 17 Nov 2010 09:59:13 +0000 (20:29 +1030)]
ccanlint: add ccanlint section to _info

This supersedes the previous Fails: section, into a more general set of
lines of form:

      <testname> <option>...

With the special <option> "FAIL" to mean we know we fail this test.
We accept options to valgrind-tests; in particular tdb2 wants
--partial-loads-ok=yes passed to valgrind.

9 years agoccanlint: override _info's Fails: with --target
Rusty Russell [Wed, 17 Nov 2010 09:57:37 +0000 (20:27 +1030)]
ccanlint: override _info's Fails: with --target

I wanted to see what happened with tdb2's valgrind test (suppressed in the
_info file).

9 years agoccanlint: run tests in alphabetical order
Rusty Russell [Wed, 17 Nov 2010 09:53:30 +0000 (20:23 +1030)]
ccanlint: run tests in alphabetical order

This allows tests (like in tdb2) to run the simpler tests first and build up,
making it easier to spot the root cause of errors.

9 years agoconfig: add HAVE_BUILTIN_FFSLL
Rusty Russell [Mon, 15 Nov 2010 09:46:40 +0000 (20:16 +1030)]
config: add HAVE_BUILTIN_FFSLL

9 years agonfs: remove trailing whitespace
Rusty Russell [Mon, 15 Nov 2010 02:47:55 +0000 (13:17 +1030)]
nfs: remove trailing whitespace

ccanlint complained about it; it's trivial but fixing it adds one point to
our score.

9 years agonfs: make headers idempotent
Rusty Russell [Mon, 15 Nov 2010 02:47:12 +0000 (13:17 +1030)]
nfs: make headers idempotent

ccanlint did this automatically.

9 years agonfs: Remove _U_, use ccan/compiler and UNUSED
Rusty Russell [Mon, 15 Nov 2010 02:46:46 +0000 (13:16 +1030)]
nfs: Remove _U_, use ccan/compiler and UNUSED

Also, add Author and License lines to _info (ccanlint complained).
Now ccanlint can build it as a module.

9 years agonfs: Add _info, remove -D_FILE_OFFSET_BITS=64, use nfs_off_t
Rusty Russell [Mon, 15 Nov 2010 02:45:36 +0000 (13:15 +1030)]
nfs: Add _info, remove -D_FILE_OFFSET_BITS=64, use nfs_off_t

This makes it closer to compiling under ccanlint.

9 years agoccanlint: remove -Werror, use output of compile command to detect warnings.
Rusty Russell [Mon, 15 Nov 2010 02:00:48 +0000 (12:30 +1030)]
ccanlint: remove -Werror, use output of compile command to detect warnings.

This means we can pass various compulation tests, but deduct points if
they get warnings.

9 years agoccanlint: make compile commands return output.
Rusty Russell [Sun, 14 Nov 2010 11:40:04 +0000 (22:10 +1030)]
ccanlint: make compile commands return output.

We want to distinguish between warnings and errors: the first step is to
return the output even if the command doesn't fail.

9 years agoccanlint: fix idempotent handler
Rusty Russell [Mon, 15 Nov 2010 02:23:00 +0000 (12:53 +1030)]
ccanlint: fix idempotent handler

Test for inserting idempotent header was wrong way around, and we check
all headers at once, rather than finishing after one.

Also, turn - into _ rather than removing.

9 years agoccanlint: only print 5 lines of output unless -vv
Rusty Russell [Sun, 14 Nov 2010 11:53:52 +0000 (22:23 +1030)]
ccanlint: only print 5 lines of output unless -vv

9 years agoccanlint: print error information even if we pass.
Rusty Russell [Mon, 15 Nov 2010 02:29:52 +0000 (12:59 +1030)]
ccanlint: print error information even if we pass.

This means we can see messages even if we don't fail; ie. for compiler warnings
once they are no longer fatal.

This means that various tests have to be more careful in not setting
score->error.

9 years agoccanlint: minor print formatting cleanup.
Rusty Russell [Sun, 14 Nov 2010 11:48:12 +0000 (22:18 +1030)]
ccanlint: minor print formatting cleanup.

9 years agoccanlint: don't skip every second question
Rusty Russell [Mon, 15 Nov 2010 02:48:57 +0000 (13:18 +1030)]
ccanlint: don't skip every second question

We only grabbed one character at a time from stdin, so "y<return>" answered
the next question as well.

9 years agociniparser: add LICENSE symlink
Rusty Russell [Thu, 11 Nov 2010 02:18:09 +0000 (12:48 +1030)]
ciniparser: add LICENSE symlink

9 years agoforeach, iscsi, jbitset, jmap, opt, rbtree, sparse_bsearch, tally, tdb2: add LICENSE...
Rusty Russell [Wed, 10 Nov 2010 12:45:14 +0000 (23:15 +1030)]
foreach, iscsi, jbitset, jmap, opt, rbtree, sparse_bsearch, tally, tdb2: add LICENSE symlinks

9 years agoccanlint: check license and LICENSE symlink.
Rusty Russell [Wed, 10 Nov 2010 12:44:30 +0000 (23:14 +1030)]
ccanlint: check license and LICENSE symlink.

Michael Ellerman noted that ccan/opt has no symlink, so add ccanlint test.

9 years agoccanlint: clarify different -v levels.
Rusty Russell [Wed, 10 Nov 2010 12:16:12 +0000 (22:46 +1030)]
ccanlint: clarify different -v levels.

9 years agoccanlint: fix --target=examples-compile
Rusty Russell [Wed, 10 Nov 2010 12:08:02 +0000 (22:38 +1030)]
ccanlint: fix --target=examples-compile

9 years agoccanlint: use isspace instead of isblank
Rusty Russell [Wed, 10 Nov 2010 11:51:06 +0000 (22:21 +1030)]
ccanlint: use isspace instead of isblank

I am told that CentOS 5.3 doesn't like isblank (it's ISO C).

9 years agoccan_tokenizer, check_type, container_of, typesafe_cb: handle !HAVE_TYPEOF
Rusty Russell [Wed, 10 Nov 2010 11:40:03 +0000 (22:10 +1030)]
ccan_tokenizer, check_type, container_of, typesafe_cb: handle !HAVE_TYPEOF

Delio Brignoli points out that check_type fails when HAVE_TYPEOF is 0,
so turn that off here and see what else breaks...

9 years agoccanlint: typo fix and fix errant description parsing.
Rusty Russell [Wed, 10 Nov 2010 11:38:15 +0000 (22:08 +1030)]
ccanlint: typo fix and fix errant description parsing.

"C has fairly weak typing:" from check_type/_info is not a new section heading!
Enforce that each word in multi-word sections must be caps.

9 years agoccanlint: tweak example compilation.
Rusty Russell [Wed, 10 Nov 2010 06:38:29 +0000 (17:08 +1030)]
ccanlint: tweak example compilation.

We used to prefer to build up examples using previous ones, but this broke
for tests which were to be executed.  But list.h relied on the buildup
behavior, so return to that unless we see "// Given" comments indicating
an execution test.

9 years agolist: fix uninitialized variable in list_add example.
Rusty Russell [Wed, 10 Nov 2010 06:37:29 +0000 (17:07 +1030)]
list: fix uninitialized variable in list_add example.

gcc with optimization complained (correctly) about this.

9 years agoccanlint: list file errors in order they are encountered.
Rusty Russell [Wed, 10 Nov 2010 06:25:24 +0000 (16:55 +1030)]
ccanlint: list file errors in order they are encountered.

9 years agoccanlint: fix abort when -vv used and examples don't compile.
Rusty Russell [Wed, 10 Nov 2010 06:24:59 +0000 (16:54 +1030)]
ccanlint: fix abort when -vv used and examples don't compile.

9 years agoMakefile: exclude Judy-depending libraries as well as nfs
Rusty Russell [Wed, 10 Nov 2010 05:18:31 +0000 (15:48 +1030)]
Makefile: exclude Judy-depending libraries as well as nfs

(nfs gives warnings on build, make ccanlint unhappy).

9 years agoMerge branch 'ronnie'
Rusty Russell [Wed, 10 Nov 2010 05:17:12 +0000 (15:47 +1030)]
Merge branch 'ronnie'

9 years agocompiler: shorten names of attributes, add UNUSED
Rusty Russell [Tue, 9 Nov 2010 22:35:58 +0000 (09:05 +1030)]
compiler: shorten names of attributes, add UNUSED

The long names were unwieldy in practice; at risk of clashing, replace
with shorter versions.

9 years agonfs: add generates C files
Rusty Russell [Tue, 9 Nov 2010 11:37:58 +0000 (22:07 +1030)]
nfs: add generates C files

ccanlint won't run rpcgen, so we need the C source in the repo anyway.

9 years agonfs: ccanize a little more.
Rusty Russell [Tue, 9 Nov 2010 08:24:45 +0000 (18:54 +1030)]
nfs: ccanize a little more.

rename libnfs.h to nfs.h (CCAN expects "main" header to match module name).
tools move into tools/, .x file move into rpc/
Don't sed the rpcgen files, generate headers in rpc/
Make tools use <ccan/nfs/nfs.h> as per normal ccan usage.

9 years agonfs: initial import.
Rusty Russell [Tue, 9 Nov 2010 08:04:21 +0000 (18:34 +1030)]
nfs: initial import.

Another Ronnie module!

9 years agoccanlint: rework so checks have more structure.
Rusty Russell [Tue, 9 Nov 2010 02:44:39 +0000 (13:14 +1030)]
ccanlint: rework so checks have more structure.

Previously each check returned a void *, but in fact most of them fell into
similar patterns.  So define 'struct score' and a helper to add files to it,
and use that.

Under these rules, you get 0/1 if you skip a test because a dependency failed
which in theory means your score (as a percentage) could drop if you fix
a test.

9 years agoccanlint: fix up creation of test/run.c
Rusty Russell [Mon, 8 Nov 2010 22:20:21 +0000 (08:50 +1030)]
ccanlint: fix up creation of test/run.c

Make test directory correctly, and #include <ccan/...> not #include "".

9 years agolikely: switch from using ccan/hashtable to ccan/htable
Rusty Russell [Mon, 8 Nov 2010 11:35:42 +0000 (22:05 +1030)]
likely: switch from using ccan/hashtable to ccan/htable

9 years agorbtree: new module from Ronnie.
Rusty Russell [Mon, 8 Nov 2010 11:30:04 +0000 (22:00 +1030)]
rbtree: new module from Ronnie.