Rusty Russell [Thu, 9 Sep 2010 09:29:18 +0000 (18:59 +0930)]
tdb2: change to using a hash tree.
As the locking issues with enlarging a hash were so nasty, we switch to a
tree structure for the entries. It's a hash which expands to point to
sub-hashes when it fills.
This means we no longer have a 'volatile' header: the top hash cannot move.
In fact, we no longer store a copy of the header in the tdb_context; we only
need hash_seed.
New helper functions for accessing writable areas and committing the results
(if they had to be copied). New debug test to make sure we don't hold access
while we're doing something which could cause us to unmap/remap.
Find becomes more complicated: we need to track where we found (or didn't
find) an entry so we can easily add/delete it.
Traverse becomes more complicated: we need to track where we were in the
hash tree.
Rusty Russell [Fri, 3 Sep 2010 12:39:40 +0000 (22:09 +0930)]
tdb2: use immobile free buckets, rename tests to show some ordering.
We put the free lists at the beginning of a zone; this means no record
can be larger than a zone, but means they cannot move. Once we change
hashes to be expanding, they won't move either and the result should be
simpler.
Rusty Russell [Thu, 26 Aug 2010 14:38:34 +0000 (00:08 +0930)]
tdb2: more fixes and tests for enlarging hash.
- Neaten I/O function
- Don't use fill in zero_out: it's only for low-level ops.
- Don't mangle arg in tdb_write_convert: it broke write_header.
- More use of tdb_access_read, make it optionally converting.
- Rename unlock_range to unlock_lists.
- Lots of fixes to enlarge_hash now it's being tested.
- More expansion cases tested.
Rusty Russell [Tue, 15 Jun 2010 10:02:55 +0000 (19:32 +0930)]
typesafe_cb: expose _exact and _def variants.
We can't allow NULL with the new variant (needed by talloc's set_destructor
for example), so document that and expose all three variants for different
uses.
Rusty Russell [Fri, 11 Jun 2010 03:36:40 +0000 (13:06 +0930)]
typesafe_cb: fix promotable types being incorrectly accepted by cast_if_type.
cast_if_type() should not try to degrade the expression using 1?(test):0,
as that promotes bool to int, as well as degrading functions to function
pointers: it should be done by the callers.
Rusty Russell [Wed, 9 Jun 2010 14:33:04 +0000 (00:03 +0930)]
alloc: reduce page header further, go down to 64k minimum.
This means we can't have more than 2^25 elements per page; that's
a maximum small page size of about 2^24 (with >8 objects per small page
we move to large pages), meaning a poolsize max of 4G.
We have a tighter limit at the moment anyway, but we should remove it
once we fix this. In particular count all-zero and all-one words in
the used field (that's what we care about: full or empty) would give us
another factor of 64 (we only care about larger pool sizes on 64-bit
platforms).
We can also restore the larger number of pages and greater inter-page
spacing once we implement the alternative tiny allocator.
Rusty Russell [Fri, 9 Apr 2010 01:28:21 +0000 (10:58 +0930)]
From: Joseph Adams <joeyadams3.14159@gmail.com>
The ccanlint patch is rather intrusive. First, it adds a new field to
all the ccanlint tests, "key". key is a shorter, still unique
description of the test (e.g. "valgrind"). The names I chose as keys
for all the tests are somewhat arbitrary and often don't reflect the
name of the .c source file (because some of those names are just too
darn long). Second, it adds two new options to ccanlint:
It also adds a consistency check making sure all tests have unique
keys and names.
The primary goal of the ccanlint patch was so I could exclude the
valgrind test, which takes a really long time for some modules (I
think btree takes the longest, at around 2 minutes). I'm not sure I
did it 100% correctly, so you'll want to review it first.
Rusty Russell [Fri, 9 Apr 2010 01:24:31 +0000 (10:54 +0930)]
From: Joseph Adams <joeyadams3.14159@gmail.com>
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.