heap: new module

Signed-off-by: Emilio G. Cota <cota@braap.org>

ilog: reformat so webpage doesn't get confused.

The extra spaces make my web formatter think they're literal text, which
looks weird.

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

ilog: relicense to Public Domain.

I noted to Timothy in 2011:
   I finally got around to implementing license checking in ccanlint,
   and it shows that your public domain ccan/isaac module uses your LGPL
   ccan/ilog module, which partially defeats the point.

   You and I are the only ones who did anything significant to ilog; I'm
   happy to relicense to PD or whatever else you want.  Or leave it, in
   which case I'll need to document it clearly.

He finally got back to me, and I sent him this patch, to which he replied:

     Ack.

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

tal: add tal_resizez for zero-padded expansion.

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

endian: add documentation on endian typedefs.

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

short_types: update documentation on be32/le32 etc.

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

endian/short_types: sparse support.

If you're doing endian work, sparse's bitwise annotation is extremely useful.

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

list: add list_next and list_prev helpers.

Some way towards iterating in the middle of the list.

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

ccan: Fix calling memset with zero length parameter

Signed-off-by: Volker Lendecke <vl@samba.org>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tal/path: fix unset vars in error paths.

Compiling with optimization FTW.

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

breakpoint: new module.

Thanks to Jeremy Kerr for the idea!

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

endian: remove unnecessary _CONST postfixes.

It makes the names longer, whereas the CAPS is probably sufficient.

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

endian: add constant versions.

Sometimes you really need a compile-time constant, but there's no generic way
to create a macro which does this and only evaluates its argument once.

Thus we need specific const macros.

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

endian: change license to CC0.

Not worth LGPL for just this header.

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

timer: clean up.

Add examples and a documentation fix.
Remove unused cascade function (was used in initial always-step-1-bucket
 version).
Restore timers_dump() to within CCAN_TIMER_DEBUG.

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

timer: increase default span to 5.

There's a sweet spot around 5, without going all the way to 13 (which
would make each level 64/128k large).

TIMER_LEVEL_BITS 2: 100000000 in 5.833399-5.884659(5.85912+/-0.015) (18 levels / 32)
TIMER_LEVEL_BITS 3: 100000000 in 5.267610-5.303589(5.29018+/-0.011) (12-13(12.5+/-0.5) levels / 22)
TIMER_LEVEL_BITS 4: 100000000 in 4.215605-4.417297(4.27771+/-0.062) (9-10(9.1+/-0.3) levels / 16)
TIMER_LEVEL_BITS 5: 100000000 in 3.859340-3.972603(3.90149+/-0.034) (7-8(7.1+/-0.3) levels / 13)
TIMER_LEVEL_BITS 6: 100000000 in 3.976157-4.037230(4.00199+/-0.02) (6 levels / 11)
TIMER_LEVEL_BITS 7: 100000000 in 4.014228-4.082031(4.05024+/-0.022) (5-6(5.4+/-0.49) levels / 10)
TIMER_LEVEL_BITS 8: 100000000 in 3.915615-3.978781(3.94972+/-0.02) (5 levels / 8)
TIMER_LEVEL_BITS 9: 100000000 in 3.859413-4.025842(3.89993+/-0.046) (4-5(4.6+/-0.49) levels / 8)
TIMER_LEVEL_BITS 10: 100000000 in 3.983507-4.170152(4.06743+/-0.055) (4 levels / 7)
TIMER_LEVEL_BITS 11: 100000000 in 3.468756-3.610746(3.52843+/-0.04) (4 levels / 6)
TIMER_LEVEL_BITS 12: 100000000 in 3.274397-3.377530(3.3192+/-0.026) (4 levels / 6)
TIMER_LEVEL_BITS 13: 100000000 in 3.116845-3.178162(3.1398+/-0.017) (3 levels / 5)
TIMER_LEVEL_BITS 14: 100000000 in 3.152599-3.264060(3.20733+/-0.043) (3 levels / 5)
TIMER_LEVEL_BITS 15: 100000000 in 3.186556-3.552432(3.25597+/-0.11) (3 levels / 5)
TIMER_LEVEL_BITS 16: 100000000 in 3.139352-3.485653(3.27263+/-0.11) (3 levels / 4)

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

timer: cache the minimal value.

We spend a lot of time searching for the next timer to expire: by caching
the minimum, we can skip most of this work.  Even if timers are deleted,
the minimum will be a starting point for searching.

The expected-usage benchmark has to be increased by a factor of 100,
otherwise it's now too short.

Before:
$ ./expected-usage
1000000 in 12.701647935

After:
$ ./expected-usage  1000000
1000000 in 0.061095153

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

timers: implementation of lazily-ordered timers.

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

Add Henry Eshbaugh's log module to junkcode for the moment.

It's got some useful stuff in it, but doesn't pass ccanlint here.

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

Makefile: don't separate all modules with external dependencies.

Using ccanlint's --deps-fail-ignore, we can just test every module
with "make check".  Still exclude them from the 'libccan.a' build
though.

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

nfs: add licenses into generated files.

Otherwise ccanlint complains about missing license comments.

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

ccanlint: --deps-fail-ignore.

Useful for bulk testing modules, where some might not have required
external (non-CCAN) dependencies.

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

ogg_to_pcm: fix compilation of example in _info.

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

ccanlint: don't crash if given bad directory name.

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

Add a set of simple version comparison helpers

These version helpers help to compare major.minor style version numbers,
without the need for open-coded and error-prone bitshifting, multiplication,
and similar.

Signed-off-by: Peter Hutterer <peter.hutterer@who-t.net>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

net: add server support.

Creating a server for IPv4 and IPv6 has similar issues to clients,
with some novel twists.  Slightly different arguments need to be given
to getaddrinfo(), but worse, some platforms (Linux without
/proc/sys/net/ipv6/bindv6only set) automatically bind IPv6 sockets to IPv4
ports as well.

Thus we need a function which can bind (and listen) to one or two fds.

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

list: list_pop

list_top + list_del, as suggested by Ben Herrenschmidt.

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

list: list_append_list / list_prepend_list

Operations for moving the entire contents of a list.

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

autodata: make note about not being generally useful for shared libraries.

If you have sections, it might still work for some cases though: on x86
Ubuntu it worked once I changed the section name from autodata to xautodata.

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

iscsi, ttxml: fix warning [-Wunused-but-set-variable]

hi all,

here is a trival path to fix warning [-Wunused-but-set-variable].

Thanks.
Tinggong

Signed-off-by: Tinggong <wangtinggong@gmail.com>

failtest: fix warning [-Wformat]

hi rusty,

here is a trival path to fix warning [-Wformat].

Thanks.
Tinggong

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

net: make tests more robust.

Andreas Schlick reports failure on systems without IPv6 support (in particular
ones with no IPv6 addresses for localhost).  We should be more robust in
these cases, and also where IPv4 support is missing.

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

foreach: fix overzealous test.

Andreas Schlick reported a failure on 64-bit systems; we should simply
test that the number of iterators does not grow on second iteration,
rather than assuming an explicit limit as compilers may vary.

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

Makefile: Add hacks for the nested modules for make check.

Merge commit 'add31d8'

sparse_bsearch: fixed the no ssize_t defined error.

siphash: Use uint64_t directly, remove typedef

siphash: Simplify helper function W64's signature

siphash: Use ~7 correctly

7 in ~7 needs to be size_t for it to be correct when len > INT_MAX.

siphash: Write siphash_epilogue in nicer style

siphash: Use simple but misalignment-correct implementation of W64

A simple implementation compiles very well with gcc and clang on ppc and
x86, and will handle any-aligned input.

siphash: A keyed hash designed by Aumasson and djb

ccanlint: fix stack smash.

"engla" on IRC reported that ccanlint on linux/powerpc would loop
infinitely calling dep_failed after all tests are run and the score is
output.

Reproduced, and discovered that cannot_run() takes a container_of(),
except our top node is not a struct ccanlint.  The result was harmless on
x86, but set dep_failed to the return address on powerpc, causing that
to be called repeatedly.

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

dgraph: add dgraph_check and CCAN_DGRAPH_DEBUG

This is good form for datastructures, so caller can track weird bugs.

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

ccanlint: handle when _info doesn't compile.

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

Merge branch 'rfc822'

rfc822: switch to ccan/tal.

We use TAL_USE_TALLOC to use libtalloc as the backend: you can test that with
ccanlint --compiler="cc -DTAL_USE_TALLOC".

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

tal/str: use tal/talloc backend #ifdef TAL_USE_TALLOC.

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

ccanlint: ignore "unused" non-ccan dependencies.

We can't really tell if non-ccan dependencies are used, so don't try.

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

tal/talloc: new module for backending tal onto talloc.

David Gibson points out that a project may already be using talloc, so
this gives a simple adapter if one module uses tal.

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

tal: don't automatically register cleanup function.

It may interfere with other at_exit() calls, so let them call it manually.
Also, use memset to zero, which really does make valgrind notice any leaks.

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

configurator: fix single-arg case.

In this case, CCAN_CFLAGS should be "".

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

tal: append the length property to the initial allocation.

Since we never post-add a length property, we can save some cycles by
allocating it together with the object itself:

Before:
$ ./samba-allocs talloc.dump --tal
Tal time:                6058997-6215211(6102645)ns
Tal_free time:           4791112-4968964(4824814)ns
Single tal_free time:    3173647-3331584(3200183)ns
$ ./samba-allocs talloc.dump --tal-size
Virtual size = 9809920, RSS = 3952640

After:
$ ./samba-allocs talloc.dump --tal
Tal time:                5911994-6043808(5956914)ns
Tal_free time:           4676026-4834598(4719908)ns
Single tal_free time:    2888195-3067365(2922298)ns
$ ./samba-allocs talloc.dump --tal-size
Virtual size = 9809920, RSS = 3948544

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

tal: don't always allocate an array in the samba benchmark.

Since we added the length property, this penalizes us with an extra
alloc.  Unfortunately, we can't tell from the talloc.dump which are
array tallocs and which are single tallocs, but grepping the sources
gives a rate of 1 in 27.

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

tal: fix skipping tal in samba-allocs benchmark.

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

tal: fix compilation of speed benchmark.

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

rfc822: fix sigaction test, wean off ccan-specific talloc_set_allocator()

The first ok() line was actually failing, because sigaction returns 0
on success, but because the program exit(0) out the abort handler,
that wasn't being seen.

So remove tap and just abort and assert our way through the test,
which I think is clearer.

We use macros to mug the talloc entry points, since talloc_set_allocator()
is not in mainline talloc.

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

rfc822: beef up _info example.

Now it's a useful little command line utility, with tests.

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

ccanlint: fix --compiler and --cflags options to apply to _info files as well.

We weren't using the compiler and cflags options in tools/compile.

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

tools: manifest.c should use path_canon.

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

ccanlint: remove redundant num_lines in struct ccan_file.

We can use tal_count.

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

ccanlint: print module name properly for nested modules.

eg:
tal/str: Module's tests cover all the code (tests_coverage): PASS (+3/6)
tal/str: Total score: 55/58

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

tools: use tal/path instead of opencoding most paths.

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

tools: use tal/path instead of writing own path handlers.

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

tools: use tal instead of talloc.

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

tools: use rbuf instead of grab_file.

Slowly removing the talloc dependency.

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

rbuf: new module.

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

tal/link: new module for reference-count style coding for tal.

Tests and example copied from talloc_link, which I also wrote.

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

tal/str: add tal_append_fmt() and tal_append_vfmt() helpers.

They are far too convenient, despite their inefficiency.

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

tal/str: rename tal_asprintf/tal_vasprintf to tal_fmt/tal_vfmt.

Shorter, sweeter, and less legacy.

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

tal/str: add tal_strcat().

Useful for joining two strings.

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

tal: add tal_expand().

Helper to reallocate and append to an array.

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

tal/str: move tal string functions here from tal.

They don't need anything internal to tal, they're just helpers.

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

tal/str: use tal_ prefix.

It's short, and much clearer.

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

tal/str: make tal_count() work for strsplit.

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

tal: add tal_count() and length properties for arrays.

Unlike talloc, we don't have a count on everything, just on array
allocations.

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

tal: adding or removing a notifier/destructor can be const.

You don't need write access to the context to attach a destructor;
it's meta.

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

tal: optimize case where no (non-destructor) notifiers are used.

$ for i in `seq 10`; do ./samba-allocs talloc.dump --tal; done | stats.c --trim-outliers
Before:
Read 25998 nodes
Tal time:                2857988-2981158(2904324)ns
Tal_free time:           2417170-2582088(2470931)ns
Single tal_free time:    1551654-1609583(1575984)ns

After:
Read 25998 nodes
Tal time:                2780974-2901323(2839352)ns
Tal_free time:           2241725-2355309(2285165)ns
Single tal_free time:    1549908-1612485(1566609)ns

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

tal: use notifier infrastructure for destructors.

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

tal: add general notifiers.

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

tal: add del_destructor().

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

tal: check headers more carefully.

We sanity check tal headers by ensuring that the pointers are in the
bounds of things we've allocated.  But the first one we check is the
prop ptr, which may also be a literal: this is_literal() dereferences
the pointer, which means we usually crash here if it's not a tal
object.

Move that last, and we have far more success with our sanity checking.

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

tal: simplify.

All the effort trying to keep the header size down to 2 pointers turns
out to be wasted.  In addition, getting the parent of a tal pointer is
now much faster.

./samba-allocs talloc.dump --tal-size:
Before:
Virtual size = 9633792, RSS = 3952640
After:
Virtual size = 9793536, RSS = 3948544

And we're much faster now, esp. on free.

./samba-allocs talloc.dump --tal:
Before:
Tal time:                2718068ns
Tal_free time:           3360258ns
Single tal_free time:    1667412ns
After:
Tal time:                2788287ns
Tal_free time:           2290167ns
Single tal_free time:    1566998ns

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Header from folded patch 'tal-fix-set-destroying-bit.patch':

tal: fix destroying bit usage.

Actually looking at a destroying contexts' parent didn't work, and a couple
of places didn't filter out the destroying bit.

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

ccanlint: handle nested modules when mentioned in examples.

If we see an ccan include line in an example, we add that to the
dependencies to try to build the example, but we didn't handle nested
modules.

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

tools: don't abort on malformed documentation lines.

ccanlint would abort with 'Malformed line 53' if there was a bad header.
That's very poor, and deeply unhelpful.

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

Makefile: score nested modules.

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

tal: fix benchmark/Makefile

We need ccan/take here.

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

tal/path: new module

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Header from folded patch 'path-talloc-take.patch':

tal/path: accept take() for arguments.

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

configurator: test for HAVE_FCHDIR

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

tal/str: accept take() for arguments.

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

tal/str: new module.

Tal-enhanced string routines, copied from str_talloc (which I also wrote).

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

alloc: move into antithread/alloc.

Our first nested module; easy because noone else relies on it.

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

web: generate correct pages for submodules.

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

tools: don't assume modules are immediately below ccan/ dir.

Removing this assumption should allow nested modules.

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

Makefile: remove FASTTIMEOUT

Far more effective to just skip valgrind and gcov if you want fast
results; that's what we do for the summary already.

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

Makefile: list modules explicitly.

Clumsier than using wildcards, but that breaks down with nested modules
anyway.  In the longer term, we want ccantool to do the building, but for
the moment make is a necessary evil.

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

tools: fix dependencies.

In particular, we might need the C files for foreach and err.

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

ccanlint: fix _info documentation addition.

Firstly, we should always ask before altering files.  Secondly, we are
not in the module directory: we need to use m->info_file->fullname.

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

Makefile: generate config.h more carefully

Don't risk reading partially-constructed files.

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

Makefile: add -Wundef to the default CFLAGS

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