timer: handle time going backwards.

As seen in https://github.com/ElementsProject/lightning/issues/4401

OpenBSD 6.8 inside VirtualBox.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

utf8: don't allow NUL in decoded strings.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

json_out: make json_out_finished finish buffer.

For JSON RPC, we can actually write multiple JSON objects back
to back, and we don't want a comma between them.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

*: Fix build with recent gcc/binutils

With current Debian testing I get:

tools/ccanlint/ccanlint -s --deps-fail-ignore   ccan/compiler/ && touch ccan/compiler/.ok
compiler: Module tests compile (tests_compile): FAIL
/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/ccan/compiler/test/run-is_compile_constant.c:Compile failed:
/usr/bin/ld: /tmp/ccanlint-129350.1804289383/tap.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/ccan/tap/tap.h:249: multiple definition of `tap_fail_callback'; /tmp/ccrAwqbl.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/ccan/tap/tap.h:249: first defined here
collect2: error: ld returned 1 exit status
...

cc -g3 -ggdb -Wall -Wstrict-prototypes -Wold-style-definition -Wundef -Wmissing-prototypes -Wmissing-declarations -Wpointer-arith -Wwrite-strings -DCCAN_STR_DEBUG=1 -I.  -MMD -MP -MFtools/ccanlint/ccanlint.d -MTtools/ccanlint/ccanlint tools/ccanlint/ccanlint.c tools/ccanlint/async.o tools/ccanlint/file_analysis.o tools/ccanlint/licenses.o tools/ccanlint/tests/avoids_cpp_reserved.o tools/ccanlint/tests/depends_accurate.o tools/ccanlint/tests/depends_build.o tools/ccanlint/tests/depends_build_without_features.o tools/ccanlint/tests/depends_exist.o tools/ccanlint/tests/examples_compile.o tools/ccanlint/tests/examples_exist.o tools/ccanlint/tests/examples_relevant.o tools/ccanlint/tests/examples_run.o tools/ccanlint/tests/hash_if.o tools/ccanlint/tests/headers_idempotent.o tools/ccanlint/tests/info_compiles.o tools/ccanlint/tests/info_documentation_exists.o tools/ccanlint/tests/info_exists.o tools/ccanlint/tests/info_ported.o tools/ccanlint/tests/info_summary_single_line.o tools/ccanlin
 t/tests/license_comment.o tools/ccanlint/tests/license_depends_compat.o tools/ccanlint/tests/license_exists.o tools/ccanlint/tests/license_file_compat.o tools/ccanlint/tests/main_header_compiles.o tools/ccanlint/tests/main_header_exists.o tools/ccanlint/tests/module_builds.o tools/ccanlint/tests/module_links.o tools/ccanlint/tests/no_trailing_whitespace.o tools/ccanlint/tests/objects_build.o tools/ccanlint/tests/objects_build_with_stringchecks.o tools/ccanlint/tests/objects_build_without_features.o tools/ccanlint/tests/reduce_features.o tools/ccanlint/tests/tests_compile.o tools/ccanlint/tests/tests_compile_coverage.o tools/ccanlint/tests/tests_coverage.o tools/ccanlint/tests/tests_exist.o tools/ccanlint/tests/tests_helpers_compile.o tools/ccanlint/tests/tests_pass.o tools/ccanlint/tests/tests_pass_valgrind.o tools/ccanlint/tests/tests_pass_without_features.o ccan/autodata/autodata.o ccan/dgraph/dgraph.o ccan/ilog/ilog.o ccan/lbalance/lbalance.o ccan/ptr_valid/ptr_valid.o ccan/strma
 p/strmap.o tools/ccan_dir.o tools/compi
le.o tools/depends.o tools/doc_extract-core.o tools/gcov.o tools/manifest.o tools/read_config_header.o tools/tools.o ccan/asort/asort.o ccan/err/err.o ccan/foreach/foreach.o ccan/hash/hash.o ccan/htable/htable.o ccan/list/list.o ccan/membuf/membuf.o ccan/noerr/noerr.o ccan/opt/helpers.o ccan/opt/opt.o ccan/opt/parse.o ccan/opt/usage.o ccan/rbuf/rbuf.o ccan/read_write_all/read_write_all.o ccan/str/debug.o ccan/str/str.o ccan/take/take.o ccan/tal/tal.o ccan/tal/grab_file/grab_file.o ccan/tal/link/link.o ccan/tal/path/path.o ccan/tal/str/str.o ccan/time/time.o -lm -o tools/ccanlint/ccanlint
/usr/bin/ld: tools/ccanlint/async.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/tools/ccanlint/../ccanlint/licenses.h:33: multiple definition of `license_compatible'; /tmp/cc72h7qq.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/tools/ccanlint/../ccanlint/licenses.h:33: first defined here
/usr/bin/ld: tools/ccanlint/file_analysis.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/tools/ccanlint/../ccanlint/licenses.h:33: multiple definition of `license_compatible'; /tmp/cc72h7qq.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/tools/ccanlint/../ccanlint/licenses.h:33: first defined here
/usr/bin/ld: tools/ccanlint/licenses.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/tools/ccanlint/licenses.h:33: multiple definition of `license_compatible'; /tmp/cc72h7qq.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/tools/ccanlint/../ccanlint/licenses.h:33: first defined here
/usr/bin/ld: tools/ccanlint/tests/avoids_cpp_reserved.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/./tools/ccanlint/../ccanlint/licenses.h:33: multiple definition of `license_compatible'; /tmp/cc72h7qq.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/tools/ccanlint/../ccanlint/licenses.h:33: first defined
here
/usr/bin/ld: tools/ccanlint/tests/depends_accurate.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/./tools/ccanlint/../ccanlint/licenses.h:33: multiple definition of `license_compatible'; /tmp/cc72h7qq.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/tools/ccanlint/../ccanlint/licenses.h:33: first defined here
/usr/bin/ld: tools/ccanlint/tests/depends_build.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/./tools/ccanlint/../ccanlint/licenses.h:33: multiple definition of `license_compatible'; /tmp/cc72h7qq.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/tools/ccanlint/../ccanlint/licenses.h:33: first defined here
/usr/bin/ld: tools/ccanlint/tests/depends_build_without_features.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/./tools/ccanlint/../ccanlint/licenses.h:33: multiple definition of `license_compatible'; /tmp/cc72h7qq.o:/home/kirr/src/wendelin/wendelin.core/3rdparty/ccan/tools/ccanlint/../ccanlint/licenses.h:33: first defined here
...

The errors are valid becuase symbols are declared without extern in .h
files and those .h files are included from multiple translation units.

-> Fix it. I'm not sure why it used to compile ok before.

Signed-off-by: Kirill Smelkov <kirr@nexedi.com>
Message-Id: <20200910191610.131510-1-kirr@nexedi.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

tools/configurator: fix compile error with -O2

In file included from /usr/include/string.h:495,
                 from configuratortest.c:2:
In function ‘strncpy’,
    inlined from ‘main’ at configuratortest.c:6:2:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:106:10: warning: ‘__builtin_strncpy’ specified bound 8 equals destination size [-Wstringop-truncation]
  106 |   return __builtin___strncpy_chk (__dest, __src, __len, __bos (__dest));
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tal: document tal_steal(ctx, NULL) as OK.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

htable: add htable_type _delval.

To match the raw delval

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

htable: fix type of htable_type _pick return.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

htable: htable_pick helper to select a random entry.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tal: don't defer-after-free if a destructor deletes itself.

==10868==    at 0x109A96: notify (tal.c:220)
==10868==    by 0x109F7E: del_tree (tal.c:397)
==10868==    by 0x10A31A: tal_free (tal.c:481)
==10868==    by 0x10BE73: main (run-destructor.c:75)
==10868==  Address 0x4a60bd8 is 8 bytes inside a block of size 32 free'd
==10868==    at 0x483BA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==10868==    by 0x109D4F: del_notifier_property (tal.c:340)
==10868==    by 0x10A610: tal_del_notifier_ (tal.c:564)
==10868==    by 0x10A687: tal_del_destructor_ (tal.c:576)
==10868==    by 0x10B653: remove_own_destructor (run-destructor.c:35)
==10868==    by 0x109A67: notify (tal.c:235)
==10868==    by 0x109F7E: del_tree (tal.c:397)
==10868==    by 0x10A31A: tal_free (tal.c:481)
==10868==    by 0x10BE73: main (run-destructor.c:75)
==10868==  Block was alloc'd at
==10868==    at 0x483A7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==10868==    by 0x109AD5: allocate (tal.c:245)
==10868==    by 0x109C3E: add_notifier_property (tal.c:300)
==10868==    by 0x10A467: tal_add_destructor_ (tal.c:516)
==10868==    by 0x10BDFE: main (run-destructor.c:74)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

opt: fix opt_unregister.

Instead of memmoving N structs, we were memmoving N bytes.

But why did the test pass then?  It was doing memmove(..., 1)
instead of memmove(..., sizeof(struct opt_table)!

Because the two structures were really similar; the main difference
was the first entry, which points to the name.  But they were allocated
consecutively, and Intel being little-endian, the only difference was
the first byte!  Thus memmove(1) was enough to make it "work".

Change two options in the test to be sufficiently different, and
the bug shows up.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

xtea: new module.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

opt: add opt_unregister.

Sometimes we all make mistakes.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools/configurator: simplify wrapper code a little.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

configurator: Enable running configurator in wrapper

Since the probing binaries compiled by the configurator needs to run on
the host machine we provide a variable CONFIGURATOR_WRAPPER that can be
set to anything that you want to wrap the calls with.

One example is `qemu-aarch64-static`.

bitmap: Allow bitmap type to be forward declared

Currently bitmap type is defined via untagged struct which makes it
impossible to forward declare it. Forward-declaring is useful since all
bitmap functions only use bitmap* and in public user-visible
headers/datastructures it is enough to indicate that a data field with
bitmap pointer is there, whereas bitmap.h can be included only in
implementation.

Beside that some headers are included by both C and C++ parts of a
project, and when ccan/bitmap.h is processed by C++ compiler it gives:

    ./3rdparty/ccan/ccan/bitmap/bitmap.h: In function ‘bitmap* bitmap_alloc(long unsigned int)’:
    ./3rdparty/ccan/ccan/bitmap/bitmap.h:201:15: error: invalid conversion from ‘void*’ to ‘bitmap*’ [-fpermissive]
      return malloc(bitmap_sizeof(nbits));
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
    ./3rdparty/ccan/ccan/bitmap/bitmap.h: In function ‘bitmap* bitmap_realloc0(bitmap*, long unsigned int, long unsigned int)’:
    ./3rdparty/ccan/ccan/bitmap/bitmap.h:227:18: error: invalid conversion from ‘void*’ to ‘bitmap*’ [-fpermissive]
      bitmap = realloc(bitmap, bitmap_sizeof(nbits));
               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    ./3rdparty/ccan/ccan/bitmap/bitmap.h: In function ‘bitmap* bitmap_realloc1(bitmap*, long unsigned int, long unsigned int)’:
    ./3rdparty/ccan/ccan/bitmap/bitmap.h:238:18: error: invalid conversion from ‘void*’ to ‘bitmap*’ [-fpermissive]
      bitmap = realloc(bitmap, bitmap_sizeof(nbits));

-> Give to users ability not to force-include ccan/bitmap.h by
forward-declaring bitmaps like this:

    typedef struct bitmap bitmap;
    ...
    struct MyStruct {
        bitmap *my_bitmap;
    };

Cc: David Gibson <david@gibson.dropbear.id.au>
Signed-off-by: Kirill Smelkov <kirr@nexedi.com>
Message-Id: <20191021150903.25159-1-kirr@nexedi.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

intmap: implement intmap_before()

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

failtest, rbuf: fix up incorrect lseek arg order.

SEEK_SET == 0, so it's not hurting anyone now, but when I cut & paste
it elsewhere...

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

pipecmd: close fds in child.

This is usually what you want; I didn't even add a flag to stop it.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

htable: add htable_count().

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Suppress false positive warning "-Wmaybe-uninitialized" with GCC -O3

configurator: fix openmp test on some versions of clang.

Discovered on bionic's Travis install, it failed at *runtime* when
it couldn't find the shared library.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

bitmap: Fix some bugs on 32-bit platforms

The bitmap_word type is an unsigned long.  However in some places we assign
it using -1ULL, a 64-bit value on many platforms.  We sometimes get away
with this because it masks correctly, but in other cases it breaks things.

To clean this up define a new BITMAP_WORD_1 constant, indicating a
bitmap_word with all bits set, and use that instead of explicit UL or ULL
qualifiers.

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

ccan/crc: remove broken "crc32c" routines which gave wrong results.

I copied them from the kernel, but obviously didn't find good test
vectors.  In particular, the CRC of all zeroes is not 0!

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

ccan/crc32c: new module for accelerated CRC32 (on x86-64).

Note: the previous code in ccan/crc is wrong, so I started fresh with
actual test vectors.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

ccan/compiler: add cpu_supports() macro.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

configurator: detect __builtin_cpu_supports.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

json_out: pass through OOM failures.

And fix escaping to work with addstr(), and assert in debug mode
if they don't specify quotes.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

json_out: new module for authoring JSON strings.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

json_escape: add fast-path for when we don't need to escape.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

json_escape: new module to escape JSON strings.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

htable: avoid branch in calculating perfect bit.

Final results of tools/speed/10000000 (10 runs) shows a slight
slowdown in some tests, but it makes an empty htable smaller.

-Initial delete all: 96-98(96.4+/-0.66) ns
+Initial delete all: 97-99(98.2+/-0.75) ns
-Initial re-inserting: 117-124(121.4+/-1.9) ns
+Initial re-inserting: 124-131(126.4+/-2.4) ns
-Adding (a different) half: 49-50(49.3+/-0.46) ns
+Adding (a different) half: 50-52(51.2+/-0.75) ns

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

htable: reduce size of htable by storing perfect bitnum, not mask.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

htable: reduce size of htable by calculating max every time.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

io: fix another leak path for always array.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

io: don't leak memory on clean shutdown.

Free the internal "always" array like we free "fds".

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

io: typo fixes.

Suggested-by: Lisa Neigut <@niftynei>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

htable: add allocator hooks.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

htable: commit extra tests I had lying around.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

timer: clean up hook allocator API

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

timer: add hook for allocation functions.

malloc and free aren't for everyone.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

ccan/io: add io_conn_exclusive and io_conn_out_exclusive.

There are cases where we want to suppress all activity except for a
single fd; we already have ugly io_flush_sync, but this is more
useful and more general.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

ccan: fix erroneous fd negation in poll.c.

We could just make them -1, since we don't rely on the values.
But simple negation doesn't make 0 invalid.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

ccan/io: keep always pointers to plans, not a linked list.

Duplex io_conns can be in the always list twice, and it was a source
of bugs, but I didn't want to add a second list_node.  Since there are
not many always at once, it's better (and more space-efficient) to use
a simple pointer array.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

ccan/io: have io_plan mappable back to io_conn.

io_conn contains two plans: by knowing what plan this is, it can be cast
back into the io_conn.  That helps for the next patch.

We also remove the strange logic where io_duplex() would return a
magic, invalid io_plan pointer.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

compiler: allow NON_NULL_ARGS with only a single argument.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

pipecmd: don't close stderr/stdout/stdin in parent when &pipecmd_preserve

This was reported and fixed by @m-schmoock for stderr, but I decided to
rework to make it clearer and cover the other cases:

https://github.com/ElementsProject/lightning/pull/2321/commits/67dad01549f876e5e620eeffe2f1e78c35bd0f03

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

configurator: fix crash when more than one extra test provided

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tal: handle take() pointers more carefully.

take() applies to the literal pointer value, so tal_free() means it may
randomly apply to a future allocation.  Similarly, tal_resize() should
preserve it.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

pipecmd: reverse order of args to match documentation; add pipecmd_preserve.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

small fix for ccan/take/take.c

Hello.

I've decided to take a look at c-lighting code, because we might
consider using it in the future.

I found a small problem in ccan/take/take.c that only concerns code
that runs with CCAN_TAKE_DEBUG set (DEVELOPER=1 for c-lighting).

It is a small issue, but I decided to notify you as the author of the
code, anyway.

the issue is:
  in take_() function, potential failure of realloc for labelarr is not
  handled.

I attached a diff with a fix.

I thought that making a pull request for c-lighting would not be right,
as ccan is a separate project, but I did not find a way to report this
at http://git.ozlabs.org/, where ccan repo resides.

Therefore I wrote to you directly.

[ Minor whitespace changes --RR ]

opt: add new parse_early_args_incomplete.

If we have plugins, and those can register args, we have a problem finding
the plugin dir!  So, do a best-effort incomplete parse.

Note that this can screw up in theory if we have "--unknown --foo" since we
don't know if unknown takes an argument (in which case, ignore --foo) or
not.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

compiler: add more attributes.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

io: don't leave errno as a random value when we hit EOF.

It's used inside io_finish; setting to 0 allows that to know we hit
EOF on a read.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

htable: add and integrate htable_check function.

Trying to debug what looked like an htable fail in my own code (but seems
it's not), I added htable_check a-la list_check et al.

This means we now depend on ccan/str (for stringify), which breaks the
_info example which also defined streq, and played nasty with const pointers.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

rbuf, tools: clean up rbuf usage.

We should use rbuf primitives not reach inside to membuf.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

membuf: add membuf_added and membuf_unadd APIs.

Clean up some whitespace while we're there too.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

crypto/shachain/tools: update to new rbuf API.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

structeq: fix case where we mark padding as unknown.

And change semantics: a negative number means "up to this much padding".

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools: fix compile after rbuf rewrite.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

rbuf: adapt to work on ccan/membuf.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

membuf: new module for linear memory buffers.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tal: allow notifiers on NULL.

A destructor on NULL doesn't make sense, but notifiers (eg. new children)
do.  We fix up a mistake in run-notifier (comparing ctx with itself) and
loose typing in tal.c's tal_add_notifier_ too.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Fix typos detected by github.com/client9/misspell

tal/str: always create strings which have tal_count() == strlen() + 1.

This is least-surprise, but also means callers can sometimes do faster
string handling by avoiding strstr().

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

ccan/tal: always include a length field.

The current semantics of tal_count() / tal_bytelen() are to return 0
for anything not allocated using tal_arr*.  This is because we tried
to save a native-length word in the header, but produces an awkward
API.

(To make it worse, defining CCAN_TAL_DEBUG turns length to always on,
and we enable that for c-lightning developer mode, which hides bugs!).

However, for c-lightning, just over half of allocations want a length:
these use 3 words each, so we're actually worse off overall.

The answer is to always have a length field in the header.  This also
simplfies the tal code.

samba-allocs stats before:
Tal time: 1237102-1305755(1.251e+06+/-2.1e+04)ns
Tal_free time: 1346871-1514514(1.37844e+06+/-5.2e+04)ns

After:
Tal time: 1115180-1180633(1.1351e+06+/-2.1e+04)ns
Tal_free time: 1334381-1465933(1.39148e+06+/-4.7e+04)ns

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tal/str and tal/stack: use _label interfaces.

In particular, tal/str now passes through the label from the caller,
so (in case of CCAN_TAL_DEBUG) you can actually see the file and line
where the caller was, not just inside ccan/str.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tal: add _label interfaces.

There are a number of other utilities which use the tal_alloc_ and
tal_dup_arr_ internal interfaces directly, because they want to set
the label themselves.  We're about to break them all by changing those
internal interfaces, so give them a mid-level interface to use.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tal: rename tal_len to tal_bytelen.

I had a bug caused by using tal_len instead of tal_count: let's make
it explicit. @jb55 commented "ha. I always forget which one does which... Ack"

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

ccan/structeq: make it safe when there's padding.

ccan/cppmagic FTW!

The only issue is that we can't tell if there's padding or they've missed
a member, so we add a padding bytes count, so they'll get an error if it
(for example) the structure adds a new member later.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

ccan/utf8: new module.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools/configurator: add manual page.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools/configurator: --extra-tests to read more test descriptions from stdin.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools/configurator: don't rely on size of tests_array.

Groundwork for adding tests dynamically.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools/configurator: better descriptions for --autotools-style.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools/configurator: Better argument handling, particularly unknown arguments.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools/configurator: support --header-file if we don't want to write to stdout.

Works well with --autotools-style.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools/configurator: support --autotools-style.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools/configurator: support --var-file for outputting VAR=VAL format.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tools/configurator: convert flags to text in 'struct test'

This is the only non-text field.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

timer: remove unnecessary dependency on likely

I don't see likely/unlikely being used by ccan/timer or any of its
dependencies right now.

Running `tools/ccanlint/ccanlint ccan/timer' reveals no regressions

Signed-off-by: Eric Wong <normalperson@yhbt.net>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

endian: fix compilation with musl libc.

It defines __BYTE_ORDER to __BYTE_ORDER__; gcc complains when we define
it to something else.  Let it be already defined, but check that the
value is what we expect.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Makefile-web: any PHP version will do.

php5 was finally removed from ozlabs.org, but php7.2 seems to work fine.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

opt: print usage correctly for early args.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Fix HAVE_ASPRINTF detection

gcc6 introduceed a new warning switched with -Wmisleading-identation. This caused to generate a compilation warning for if statement misleadingly indented, which caused HAVE_ASPRINTF to be defined as 0. Adding newline after an if statement fixes the problem.

tal/grab_file: be robust against EINTR.

Exracted (and slightly modified) from a MacOS PR for lightning.

Based-on-patch-by: https://github.com/conanoc
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

ptr_valid: fix spurious SIGINT under lldb on MacOS

(Taken from PR for lightning)

Patch-from: https://github.com/conanoc
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

base32: add ability to substitute character set.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

str/base32: new module.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

intmap: add iterator-by-callback.

It's significantly faster because it assumes no deletion:

10000000,critbit iteration (nsec),316
10000000,critbit callback iteration (nsec),90
...
10000000,critbit consecutive iteration (nsec),308
10000000,critbit consecutive callback iteration (nsec),78

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

intmap: add exhaustive testcases for intmap_after

We can't do the full range, but we can for a handful of bits (8).

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

intmap: add test case which failed, extracted from real world usage.

Because intmap_after_() would simply examine the critbits to walk the
tree, it wouldn't realize that it might be in the completely wrong tree.

In this case:

         Bit 4:
         0   1
        /     \
       /       \
  100000011  100001011

When we ask for intmap_after_(011111111) we would check the critbit, it's
a 1, so we end up on the right leaf instead of the left.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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)

After:
10000000,random generation (nsec),3-4(3.2+/-0.4)
10000000,critbit insert (nsec),1533-1699(1628+/-65)
10000000,critbit successful lookup (nsec),1831-2104(1972.4+/-1e+02)
10000000,critbit failed lookup (nsec),1850-2152(2008.2+/-1.1e+02)
10000000,critbit iteration (nsec),304-324(312.8+/-7.5)
10000000,critbit memory (bytes),48
10000000,critbit delete (nsec),1617-1872(1752+/-99)
10000000,critbit consecutive iteration (nsec),303-318(311+/-5.4)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

intmap: add benchmarks.

I wrote these a while ago, dig them out.

On my laptop, min-max(avg+/-stdev) of 5 runs:

make && for i in `seq 5`; do ./speed 10000000; done | stats
make: Nothing to be done for 'all'.
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)
10000000,hash insert (nsec),396-424(412+/-9.6)
10000000,hash successful lookup (nsec),150-164(157.4+/-5.5)
10000000,hash failed lookup (nsec),163-178(170+/-5.5)
10000000,hash iteration (nsec),21-26(23.2+/-1.7)
10000000,hash memory (bytes),45
10000000,hash delete (nsec),179-194(183.6+/-5.3)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

bitops: new module.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

configurator: add tests for other popcount variants.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Makefile: Fix asort multiple definition error

Error I experienced on Alpine Linux without this patch:

    In file included from ccan/generator/generator.c:8:0:
    ./ccan/generator/generator.h:23:2: error: #error Generators require coroutines
     #error Generators require coroutines
      ^~~~~
    make: *** [Makefile:32: ccan/generator/generator.o] Error 1

fix misuse of typesafe_cb_cast() in example

From 32f86c701ab0e0ad0ad6981314a9bff2dc5ebb74 Mon Sep 17 00:00:00 2001
From: Yubin Ruan <ablacktshirt@gmail.com>
Date: Wed, 14 Mar 2018 11:14:54 +0800
Subject: [PATCH] fix misuse of typesafe_cb_cast() in example

Signed-off-by: Yubin Ruan <ablacktshirt@gmail.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

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>

tal: don't access freed memory on unusual case of redundant tal_free() in destructor.

We already handle normal free traversal loops, just not ones caused by a
direct tal_free() call, such a calling tal_free() on one's own parent.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>