Rusty Russell [Mon, 26 Mar 2018 10:36:34 +0000 (21:06 +1030)]
intmap: reimplement so that intmap_after works.
A critbit tree is a binary tree which keeps branches for each bit
which differs in the leaves. It's a simple data structure, but not
entirely simple to implement the primitives people expect, as this bus
shows.
The bug: I added an open iterator, and intmap_after_ for a random
value would sometimes return the wrong node.
Cause: we don't know what the prefix is as we iterate, so by only
testing the critbits in the tree, we can end up in the wrong place.
This is only a problem if the value isn't in the (sub)tree, but this
can easily happen even with contiguous trees should deletion occur.
You can see an example in the next patch, which adds a test.
After finding a bug in my intmap_after() routine, I went searching for
other implementations to see how they handled it. Most didn't provide
an open-ended iterator like this, relying on callback iterators which
don't allow deletion. Gah!
The exception was https://github.com/blynn/blt/blob/master/blt.c#L179
which implements blt_ceil() which does this (if you add one to the
key, at least). However, it does it by effectively finding a node,
using that to derive the prefix, then walking down the tree again.
That's pretty suboptimal.
There are basically two choices if you want an efficient after()
operation: to reimplement this approach with some optimizations
(ie. keep branches as we descend, and when we get to the bottom and
know the prefix, we know which branch to go down), or keep the bits
which got to each node.
The latter is more optimal, but less generally useful: for bit
strings, for example, we could keep the bits in common on each node,
rather than storing the entire string at the bottom. But in practice
you'd be doing allocations to re-create the index if the caller wanted
it.
However, in this implementation our keys are 64 bits only, and we
already use a u8 for the bit number: using a 64-bit value there
consumes no more space (thanks to alignment). We can store the
critbit by using the prefix capped by a bit: 0b10000...0000 means
no prefix and highest bit is the critbit, and 0bxxxxx1000...000
means the prefix is xxxxxx and the critbit is the 6th highest bit.
The penalty is that iteration 70% slower. It's still pretty fast
though.
Before:
$ for i in `seq 5`; do ./speed 10000000; done | stats 10000000,random generation (nsec),3-4(3.2+/-0.4) 10000000,critbit insert (nsec),1530-1751(1633.2+/-80) 10000000,critbit successful lookup (nsec),1723-1993(1806.8+/-97) 10000000,critbit failed lookup (nsec),1763-2104(1933.6+/-1.3e+02) 10000000,critbit iteration (nsec),208-266(242.2+/-19) 10000000,critbit memory (bytes),48 10000000,critbit delete (nsec),1747-1861(1803.8+/-42) 10000000,critbit consecutive iteration (nsec),182-228(210+/-18)
Yubin Ruan [Mon, 12 Mar 2018 03:24:14 +0000 (11:24 +0800)]
fix misspelling in the example of container_of
From 47c92fe951545e780ca31c598bbcbe5347059b27 Mon Sep 17 00:00:00 2001
From: Yubin Ruan <ablacktshirt@gmail.com>
Date: Mon, 12 Mar 2018 11:22:35 +0800
Subject: [PATCH] fix misspelling in the example of container_of
Signed-off-by: Yubin Ruan <ablacktshirt@gmail.com> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Rusty Russell [Wed, 25 Oct 2017 05:39:47 +0000 (16:09 +1030)]
io: query whether io_plan in/out have started.
For lightning, we want to hand the socket off to another daemon, but we need
to be on a packet boundary. This lets us check if we've part-read or
part-written.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
An application built using glibc would expect __BYTE_ORDER to tell if
it should be compiled for BIG_ENDIAN or LITTLE_ENDIAN, whereas ccan uses
HAVE_LITTLE_ENDIAN and HAVE_BIG_ENDIAN for the same purpose.
Hence setting __BYTE_ORDER based on what CCAN provides will no longer
break the applications which check endianness the glibc way.
Signed-off-by: Akshay Adiga <akshay.adiga@linux.vnet.ibm.com> Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Damien Grassart [Tue, 29 Aug 2017 10:08:42 +0000 (12:08 +0200)]
darray: Fix bug in the darray_remove() macro
The memmove() call should be using the index argument to determine the
number of bytes to copy. To be consistent with the rest of the code,
we should also not evaluate the index parameter multiple
times. Calling this with rand() % arr.size would otherwise generally
segfault.
Finally, we want to avoid using "index" as an identifier so as to not
shadow index(3) in the C library.
Signed-off-by: Damien Grassart <damien@grassart.com> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Damien Grassart [Tue, 29 Aug 2017 10:08:40 +0000 (12:08 +0200)]
darray: Add darray_insert() to insert a value at a specified index
This module currently supports removing but not inserting at a
specified index, so this adds that along with some tests. Inserting a
value moves all existing data beyond index over one element.
Signed-off-by: Damien Grassart <damien@grassart.com> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sun, 23 Jul 2017 05:21:36 +0000 (15:21 +1000)]
objset: Use TCON_WRAP instead of TCON
TCON() uses flexible-array members which aren't allowed in the middle
of structures, except as a gcc extension. TCON_WRAP() avoids this and so
is more portable.
This doesn't change the objset interface, only its internals.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sun, 23 Jul 2017 05:11:33 +0000 (15:11 +1000)]
jmap: Use TCON_WRAP instead of TCON
TCON() uses flexible-array members which aren't allowed in the middle
of structures, except as a gcc extension. TCON_WRAP() avoids this and so
is more portable.
This doesn't change the jmap interface, only its internals.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sun, 23 Jul 2017 04:54:13 +0000 (14:54 +1000)]
jset: Use TCON_WRAP instead of TCON
TCON() uses flexible-array members which aren't allowed in the middle
of structures, except as a gcc extension. TCON_WRAP() avoids this and so
is more portable.
This doesn't change the jset interface, only its internals.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Thu, 20 Jul 2017 14:06:01 +0000 (00:06 +1000)]
tlist: Use TCON_WRAP instead of TCON
TCON() uses flexible-array members which aren't allowed in the middle
of structures, except as a gcc extension. TCON_WRAP() avoids this and so
is more portable.
This doesn't change the tlist interface, only its internals.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Rusty Russell [Wed, 31 May 2017 03:05:45 +0000 (12:35 +0930)]
io: fix nasty io_wake corner case.
If we're duplex and one io_always callback makes the other io_always,
we screwed up and hit an assertion later when the conn was in the
always list but didn't actually want to be.
io_wake() uses io_always(), so this is how it happened. Writing a
test case for this was a bit fun, too.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
David Gibson [Sun, 2 Apr 2017 15:15:53 +0000 (01:15 +1000)]
net: Add check for failure of setsockopt()
make_listen_fd() didn't check for failure of setsockopt(). There's no
real reason not to, since we have an obvious way to report an error to the
caller.
Found with Coverity Scan.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sun, 2 Apr 2017 11:21:02 +0000 (21:21 +1000)]
crypto/ripemd160: Correct badly sized union member
struct ripemd160_ctx has a union for converting between u8[] and u32[]
data. Unfortunately the u32 array has a miscalculated size, half the size
of the u8 array. That means some accesses which are within the union can
technically overrun the u32 array.
Found by Coverity scan.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Fri, 31 Mar 2017 13:48:22 +0000 (00:48 +1100)]
Fix missing va_end()s
This corrects several places in ccan where stdarg.h is used but there is a
missing va_end(). You can get away with this on many platforms, but not
all.
Caught by Coverity scan.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Fri, 31 Mar 2017 12:51:22 +0000 (23:51 +1100)]
lbalance: Switch to tlist2
lbalance uses the tlist module. tlist causes compile warnings on clang if
you're not careful, because it can put 0 length arrays in the middle of
structures. tlist2 doesn't have the problem, and also has a slightly
cleaner interface.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Fri, 31 Mar 2017 11:39:10 +0000 (22:39 +1100)]
tools/ccanlint: Add missing header file
tools/ccanlint/async.c uses kill(2), but doesn't include the signal.h
header it comes from. One some platforms we get away with this via
indirect includes, but not on all.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Rusty Russell [Tue, 14 Mar 2017 01:45:19 +0000 (12:15 +1030)]
io: add io_flush_sync().
This is needed for emergency handling in lightningd: we want to output
a (fatal) error packet on the socket, but we don't want to do so in the middle
of another packet.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
David Gibson [Fri, 20 Jan 2017 12:49:43 +0000 (23:49 +1100)]
coroutine: Stack allocation
At present, coroutine stacks must be allocated explicitly by the user,
then initialized with coroutine_stack_init(). This adds a new
coroutine_stack_alloc() function which allocates a stack, making life
easier for users. coroutine_stack_release() will automatically determine
if the given stack was set up with _init() or alloc() and act
accordingly.
The stacks are allocate with mmap() rather than a plain malloc(), and a
guard page is added, so an overflow of the stack should result in a
relatively debuggable SEGV instead of random data corruption.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sat, 24 Dec 2016 10:08:55 +0000 (21:08 +1100)]
coroutine: Enable valgrind
Currently valgrind checks are disabled on the coroutine module,
because switching stacks tends to confuse it. We can work around this
by using the valgrind client interface to explicitly inform it about
the stacks we create.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sat, 24 Dec 2016 10:40:00 +0000 (21:40 +1100)]
coroutine: Remove on-stack buffers from testcases
In preparation for enabling valgrind tests, remove instances where we
allocate a coroutine's stack from a buffer itself on the stack. Not all
that surprisingly, valgrind gets very, very confused by having one
"thread"'s stack embedded within another's.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Tue, 24 Jan 2017 09:39:45 +0000 (20:39 +1100)]
coroutine: Move total initialization outside coroutine
The sample coroutine in api-3 initializes a total to 0, then adds up the
pseudo-random data it has placed into a stack buffer, to ensure that the
compiler won't elide the reading and writing of that buffer. After the
coroutine has completed, we verify that total is non-zero so that we'll
detect if the coroutine failed to execute entirely.
Except that the initialization of total is within the coroutine itself,
so it could also be non-zero due to it simply being uninitialized. This
moves the initialization outside the coroutine, to make the test a little
more robust.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Tue, 24 Jan 2017 06:59:16 +0000 (17:59 +1100)]
coroutine: Remove problematic diagnostic from api-3 test
The api-3 testcase devotes most of its available stack space to a test
buffer, leaving only a small amount (COROUTINE_MIN_STKSZ) for the actual
stack usage of the coroutine.
It turns out that the ccan/tap diag() function can - depending on compiler
version and flags, and on whether diagnostics are enabled - exceed that
limited stack space. That leads to a stack overrun, and in turn corruption
of the parent routine's stack, generating unpredictable and hard to debug
SEGVs.
At present, this bug seems to be tripped by clang-3.8 when diagnostic
messages are printed.
This removes the troublesome diag() call.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Wed, 18 Jan 2017 21:56:48 +0000 (08:56 +1100)]
ccanlint: Correct default coverage tool for clang
Currently ccanlint defaults to using "gcov" as the coverage analysis tool
for any compiler defining __GNUC__. That's generally correct for the
(system default) gcc. However, clang also defines __GNUC__ because it
implements the GCC langauge extensions. For clang, "gcov" is not the
correct coverage tool (clang does use roughly the gcov format, but unless
you're very lucky the system gcc and system clang won't use the same gcov
versions).
This changes the default coverage tool in the case of clang to the correct
"llvm-cov gcov".
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Wed, 18 Jan 2017 03:23:51 +0000 (14:23 +1100)]
ccanlint: Allow path to gcov to be overriden
Currently ccanlint always assumes that the coverage tool can be
invoked under the command "gcov".
However, the coverage tool generally needs to be closely matched to
the compiler version. So, the current behaviour won't work with
compilers other than gcc, like clang. It won't even work for a gcc
version which isn't the standard system one matching gcov.
To address this, allow the command for the coverage tool to be
overridden on the ccanlint command line with a new --gcov option. We
also allow it to be overridden for make check with a GCOV make
variable.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Wed, 18 Jan 2017 03:09:29 +0000 (14:09 +1100)]
tools: Consolidate gcov handling
At the moment, invocation of the 'gcov' tool for coverage analysis
from ccanlint is put directly into the tests_compile_coverage.c and
tests_coverage.c files. This makes it awkard to extend.
So, this patch moves the invocation of gcov into a new tools/gcov.v
file, analagous to tools/compile.c.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Mon, 16 Jan 2017 23:37:15 +0000 (10:37 +1100)]
.travis.yml: Add valgrind testing
Currently, our Travis builds don't have valgrind installed, meaning
that ccanlint's valgrind based tests will be skipped, which is
unfortunate.
This adds valgrind to some of the builds to give us better CI
coverage. It's not added for Precise with gcc, because that causes
failures which appear to be due to something in the builtins of that
gcc version.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Mon, 16 Jan 2017 05:10:47 +0000 (16:10 +1100)]
.travis.yml: Add builds under Ubuntu Trusty
At the moment our Travis builds all use Travis's default Ubuntu
Precise base distro. For wider testing, add a build using their
Ubuntu Trusty distro. Only build with gcc there, for now, since clang
will cause ccanlint failures, due to the gcov version there not being
suitable for clang output.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Mon, 16 Jan 2017 04:39:48 +0000 (15:39 +1100)]
.travis.yml: Rework Travis matrix
At the moment the .travis.yml implicitly constructs a build matrix
with the two compiler options. In future we want to add more build
options for wider testing: different base distro, more compiler
versions, etc. However, a fair few of the possible combinations have
various problems meaning we don't want to test them routinely.
So, this reworks from implicitly constructing the matrix to using
matrix: include: options to explicitly build the options we want.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Rusty Russell [Mon, 9 Jan 2017 02:03:44 +0000 (12:33 +1030)]
io: don't try to close() connection twice, remove shutdown logic.
We were closing before calling del_fd, which also closed.
The shutdown() logic applies when a child and parent are using the
*same* socket fd to communicate to each other. That's really unusual
(who would you connect to?), and should probably be done by the user.
Generally, you'd use socketpair() for this child-parent case.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Rusty Russell [Thu, 29 Dec 2016 04:33:19 +0000 (15:03 +1030)]
tal: support destructors with an extra argument.
There are several times I've wanted an extra arg to the destructor, and had
to embed it in the thing destroyed. It's more efficient to put it into
tal itself (since it allocates space anyway), but we make it conditional
on a flag to avoid bloating every destructor.
The infrastructure makes it easier to add an extra arg to the general
notifiers later if we want.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Rusty Russell [Thu, 29 Dec 2016 04:31:32 +0000 (15:01 +1030)]
io: allow freeing of io_conn at any time.
io_close() currently marks the io_conn for freeing, but doesn't
actually do it. This is a problem for tal() users, because we can't
just call it in the parent's constructor.
Make io_close() just tal_free() + return &io_conn_freed (a magic
io_plan pointer).
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
David Gibson [Sat, 24 Dec 2016 12:58:19 +0000 (23:58 +1100)]
ccanlint: Move ccanlint test options from _info comments to code
Currently, _info files can specify options, or note expected failures, for
ccanlint checks in the _info file with specially structured comments. That
differs from most other things ccanlint gets from _info, where it instead
executes the info file with certain parameters.
This changes ccanlint and existing _info files to use the normal method for
the ccanlint test options as well. This also has the advantage that an
info file can alter its test options based on things from config.h - in
some cases whether a test can work or not might depend on various things.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sat, 24 Dec 2016 12:46:29 +0000 (23:46 +1100)]
Makefile: Make module checks depend on info file
Changing the _info file can change how ccanlint assesses the module.
Therefore, if the _info file changes, we should re-run ccanlint module
tests with make check. We didn't previously have a dependency for that,
though, so this adds it.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Thu, 1 Dec 2016 11:43:20 +0000 (22:43 +1100)]
Makefile: Remove testdepends from make check dependencies
The new Makefile system, via the helper script in tools/gen_deps.sh, when
generating the targets to test a module, inserts dependencies meaning it
must first check modules this one depends on, whether via 'depends' or
'testdepends' in _info.
Although it seems logical, including 'testdepends' is actually incorrect.
If ccan/a testepends on ccan/b then ccan/b must be *built* in order to test
ccan/a, but it doesn't need to be tested. testepends are explicitly
permitted to contain loops - it's quite common for two complementary
modules to be used to test each other. This is one of the reasons
testdepends exists separate from depends.
So, remove testdepends from the generated check dependencies, removing the
circular dependency that Make complains about.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
The previous name was misleading, since it does not define the number of
elements (ed_elem) on the stack, but rather the number of distance
values (ed_dist). Rename to make this more clear and add more
documentation about what it does and how best to define it.
Note: This is an API change for custom-compiled versions, but since the
module has only been included for a couple days I don't think it's worth
a back-compat #ifdef at this point.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name>
projects / ccan / log