ccan
4 years agoMakefile: exclude altstack so Jenkins works again.
Rusty Russell [Mon, 9 May 2016 01:34:33 +0000 (11:04 +0930)]
Makefile: exclude altstack so Jenkins works again.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoccanlint: fix missing file.
Rusty Russell [Mon, 9 May 2016 01:16:53 +0000 (10:46 +0930)]
ccanlint: fix missing file.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agotools/ccanlint: make sure _info compiles.
Rusty Russell [Fri, 6 May 2016 00:44:10 +0000 (10:14 +0930)]
tools/ccanlint: make sure _info compiles.

We used to crash, as reported by Stephen M. Cameron

Closes: #39
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoa_star: new module added to hacky Makefile-ccan list.
Rusty Russell [Tue, 3 May 2016 20:53:24 +0000 (06:23 +0930)]
a_star: new module added to hacky Makefile-ccan list.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoAdd A-star module
Stephen M. Cameron [Tue, 3 May 2016 06:02:26 +0000 (23:02 -0700)]
Add A-star module

Signed-off-by: Stephen M. Cameron <stephenmcameron@gmail.com>
4 years agoCorrectly include dependencies for nested modules
David Gibson [Tue, 16 Feb 2016 12:35:41 +0000 (23:35 +1100)]
Correctly include dependencies for nested modules

Currently we pull auto-generated dependencies into the Makefile with
include ccan/*/*.d.  That will omit any .d files from nested modules,
meaning things might not be correctly rebuilt there.

Correct this by using the list of modules instead of a 1-level wildcard.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoExclude system headers from .d files
David Gibson [Tue, 16 Feb 2016 12:32:34 +0000 (23:32 +1100)]
Exclude system headers from .d files

We currently generated .d dependency files with the -MD option to cc.  That
includes system header files in the dependencies, which isn't often useful
and makes the .d more complicated than necessary.

This changes to -MMD which excludes system headers.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoClean up use of 'rm' in Makefiles
David Gibson [Tue, 16 Feb 2016 12:24:05 +0000 (23:24 +1100)]
Clean up use of 'rm' in Makefiles

Most of the ccan Makefiles use $(RM) to remove files.  However, 'rm' is
traditionally considered one of the few shell tools which can be used in
Makefiles without indirecting via a variable.

rm is also typically invoked with -f in Makefiles, so that it doesn't cause
errors if the files don't exist (because they haven't been built).  A
number of instances in ccan were missing this.

This corrects these warts.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoAdd missing files to make clean
David Gibson [Tue, 16 Feb 2016 11:53:50 +0000 (22:53 +1100)]
Add missing files to make clean

At present, "make clean" will not remove the module-Makefile files for
non-top-level modules.  It also won't remove the generated config.h.
Correct those errors.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoconfigurator: fix HAVE_UCONTEXT test on Ubuntu 16.04.
Rusty Russell [Tue, 26 Apr 2016 04:55:22 +0000 (14:25 +0930)]
configurator: fix HAVE_UCONTEXT test on Ubuntu 16.04.

Seems to want more stack.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agogenerator: don't even try to compile if !HAVE_UCONTEXT.
Rusty Russell [Tue, 26 Apr 2016 04:54:21 +0000 (14:24 +0930)]
generator: don't even try to compile if !HAVE_UCONTEXT.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoMakefile: add altstack and generator to build exclusions.
Rusty Russell [Tue, 26 Apr 2016 04:41:01 +0000 (14:11 +0930)]
Makefile: add altstack and generator to build exclusions.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoMakefile: fix random pattern hack.
Rusty Russell [Tue, 26 Apr 2016 04:40:18 +0000 (14:10 +0930)]
Makefile: fix random pattern hack.

Turns out that patterns with / cause % to match /.  OK...

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoMakefile-ccan: add cppmagic.
Rusty Russell [Tue, 26 Apr 2016 04:23:15 +0000 (13:53 +0930)]
Makefile-ccan: add cppmagic.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agohtable: add iterators to htable_type.
Rusty Russell [Tue, 26 Apr 2016 04:18:40 +0000 (13:48 +0930)]
htable: add iterators to htable_type.

Useful if you have more than one object with same key.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agostrgrp: Add cosine fudge-curve to unify filter comparison spaces
Andrew Jeffery [Sat, 20 Feb 2016 10:52:41 +0000 (21:22 +1030)]
strgrp: Add cosine fudge-curve to unify filter comparison spaces

If we are to use should_grp_score_cos(x,y) as a filter the the following
relationship must hold (from least to most expensive):

        should_grp_score_len(x,y)
                >= should_grp_score_cos(x,y)
                >= grp_score(x)

should_grp_score_cos(x,y) wasn't holding up its part of the bargain, so
real data was used to generate a fudge curve to bring
should_grp_score_cos(x,y) results into the same space. Really this is a
terrible hack and the problem needs more thought. Evaluation of
should_grp_score_cos(x,y)'s performance benefit (given the relaxation of
the filter under the fudge curve) is sorely needed.

4 years agostrgrp: Use angular similarity for distance metric properties
Andrew Jeffery [Sat, 20 Feb 2016 10:49:53 +0000 (21:19 +1030)]
strgrp: Use angular similarity for distance metric properties

Distance metrics allow us to compare similarity results, however
applying the change leads to test suite breakage as we no longer satisfy
the requirement that each filter's score is at most as large as that of
the previous filter^. As such, also stop ccanlint from executing the
tests that are known to fail until we work around the problem.

^ This is a problem that has existed since the introduction of the
cosine similarity filter, it just wasn't detected by the test suite.

4 years agostrgrp: Use ratio of hypotenuse for consistent comparisons
Andrew Jeffery [Sat, 20 Feb 2016 11:03:04 +0000 (21:33 +1030)]
strgrp: Use ratio of hypotenuse for consistent comparisons

Ensure comparing filter results is sensible by using a consistent
calculation. Note that the cosine similarity measurement doesn't yet
conform and this can give spurious results that are not detected by the
test suite.

4 years agostrgrp: Shift constant out of loop
Andrew Jeffery [Sat, 20 Feb 2016 11:01:43 +0000 (21:31 +1030)]
strgrp: Shift constant out of loop

Likely this was optimised away, but the code now represents the intent.

4 years agoshachain: clarify design in terms of binary tree, reverse indexes.
Rusty Russell [Tue, 8 Mar 2016 05:38:36 +0000 (16:08 +1030)]
shachain: clarify design in terms of binary tree, reverse indexes.

Olaoluwa Osuntokun came up with an alternative which used binary trees;
that's a much better way to explain it, so do that in design.txt and
update the implementation to work the same way.

Anthony Towns pointed out that the numbering is the reverse of the normal
hash chaining descriptions, so fix that too.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agogenerator: Allow generators to take arguments
David Gibson [Fri, 12 Feb 2016 12:49:49 +0000 (23:49 +1100)]
generator: Allow generators to take arguments

Using some serious macro magic, this patch extends generators to allow
them to take arbitrary arguments.  The arguments are marshalled into a
structure placed at the far end of the generator's stack when it is
created.  Then, they're unmarshalled back into C parameters when we first
context switch into the generator.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agogenerator: Generators for C
David Gibson [Thu, 25 Feb 2016 11:07:17 +0000 (22:07 +1100)]
generator: Generators for C

Generators are a limited form of co-routine, which people may be familiar
with from Python.  This module adds an implementation of generators for C.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoconfigurator: Add test for ucontext.h
David Gibson [Sat, 19 Jul 2014 07:00:15 +0000 (17:00 +1000)]
configurator: Add test for ucontext.h

This adds a new HAVE_UCONTEXT define, which indicates that ucontext.h
is present, and more-or-less works.

It also adds HAVE_POINTER_SAFE_MAKECONTEXT, which indicates whether
pointer valued arguments can be passed through the varargs parameters
to makecontext().

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaltstack: Clarify checking macros
David Gibson [Mon, 15 Feb 2016 11:49:54 +0000 (22:49 +1100)]
altstack: Clarify checking macros

The chkfail() and chkok() macros in altstack's test program are pretty
difficult to read.  More importantly, though, they do all their tests with
one big ok1().  That means if the test fails, you get no indication which
of the checks was actually wrong, making debugging harder.

This reworks the macros into a more verbose form that's easier to read,
and splits them into multiple ok1() tests to make failures more explicit.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaltstack: Declare memory clobbers
David Gibson [Mon, 15 Feb 2016 11:47:36 +0000 (22:47 +1100)]
altstack: Declare memory clobbers

altstack includes a couple of inline asm blocks with x86 push and pop
instructions.  These instructions will access memory (the stack), but
that's not declared in inline asm statement.  We seem to be getting away
with it, but in theory that could allow the compiler to re-order accesses
to local variables across the asm block.  Since those blocks change the
location of the stack, that could be very bad.

Adding a "memory" clobber should prevent this (effectively making the asm
blocks a compiler memory barrier).

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaltstack: Include config.h in run.c
David Gibson [Mon, 15 Feb 2016 11:43:07 +0000 (22:43 +1100)]
altstack: Include config.h in run.c

ccan programs should always include config.h before anything else to make
sure everything is set up correctly.  Doing so in altstack's run.c means
it no longer needs an explicit _XOPEN_SOURCE 700, since _GNU_SOURCE is set
in config.h (for GNU libc, anyway).

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaltstack: Increase signal stack size
David Gibson [Mon, 15 Feb 2016 11:01:18 +0000 (22:01 +1100)]
altstack: Increase signal stack size

At present the altstack module uses a stack of size MINSIGSTKSZ for its
SIGSEGV handler.  Although MINSIGSTKSZ is defined to be large enough to
execute a signal handler, it doesn't guarantee that you can do anything
very much within it.

With certain libc versions, MINSIGSTKSZ is not enough to execute the
longjmp() used in altstack.  Specfically, with Ubuntu 12.04 (the default
install for Travis containers), the first time longjmp() is executed the
symbol must be resolved by the dynamic linker in a process which overruns
the MINSIGSTKSZ sized stack.  That then corrupts local variables in
altstack() itself causing a number of subsequent failures.

This patch addresses the problem by changing from MINSIGSTKSZ to SIGSTKSZ
which is supposed to cover "the usual requirements for an alternate signal
stack".

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaltstack: stack alignment and accounting tweaks
Dan Good [Mon, 8 Feb 2016 20:57:23 +0000 (20:57 +0000)]
altstack: stack alignment and accounting tweaks

* add altstack_remn, returns amount of stack remaining
* increase mapping by 1 page to handle abutment case
* capture rsp earlier
* align stack to 16 bytes

Signed-off-by: Dan Good <dan@dancancode.com>
4 years agoccanlint: make _info ported an empty string on success.
Rusty Russell [Fri, 5 Feb 2016 03:39:45 +0000 (14:09 +1030)]
ccanlint: make _info ported an empty string on success.

Otherwise it describes what we need.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agocppmagic: Iteration
David Gibson [Tue, 26 Jan 2016 10:54:47 +0000 (21:54 +1100)]
cppmagic: Iteration

This implements macros which iterate across their arguments.  This is
implemented in terms of (kinda sorta) recursion.  In fact, they will stop
working with enough arguments, but the limit is large and can be easily
increased by changing the depth of the CPPMAGIC_EVAL() macro.

There are 3 iterators (for now):
  CPPMAGIC_MAP
    applies another macro to each of its remaining arguments - the results
    are comma separated, so they can be passed into another CPPMAGIC_MAP
    invocation.
  CPPMAGIC_2MAP
    does the same thing, but takes the arguments a pair at a time, using
    a supplied two-argument macro.
  CPPMAGIC_JOIN
    combines the arguments with a chosen delimiter (effectively replacing
the commas between the arguments with the delimiter)
same thing, but takes the arguments a pair at a time.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agocppmagic: Allow multiple and deferred evaluation
David Gibson [Tue, 26 Jan 2016 10:32:07 +0000 (21:32 +1100)]
cppmagic: Allow multiple and deferred evaluation

Recursion (and therefore iteration) in cpp is difficult, since the
preprocessor explicitly looks for and inhibits recursion.

But, it's possible to trick it, up to a point.  CPPMAGIC_DEFER1() and
CPPMAGIC_DEFER2() can "hide" a macro, preventing it from being expanded
and being noticed as recursion.

Along with that we need to cause extra expansion passes to be executed.
There has to be a finite limit here - true recursion is impossible - but
that number can be made very large pretty easily.  CPPMAGIC_EVAL() multiply
expands its argument(s) - up to 1024 times.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agocppmagic: Conditionals
David Gibson [Tue, 26 Jan 2016 10:00:01 +0000 (21:00 +1100)]
cppmagic: Conditionals

Implement CPPMAGIC_IFELSE which operates similar to the C ? : operator, but
is evaluated at preprocessing time.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agocppmagic: Logical operations
David Gibson [Tue, 26 Jan 2016 09:52:32 +0000 (20:52 +1100)]
cppmagic: Logical operations

In order to implement fancier things, we need to represent truth values in
cpp.  We use '0' and '1' strings, like in C, but we need ways to get these
values from other conditions.

CPPMAGIC_ISZERO() and CPPMAGIC_NONZERO() test if the argument is '0' or
anything else (ISZERO doubles as a logical not).

CPPMAGIC_ISEMPTY() and CPPMAGIC_NON_EMPTY() expand to 0 or 1 depending on
whether they have any arguments at all or not.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agocppmagic: New module
David Gibson [Tue, 26 Jan 2016 09:51:57 +0000 (20:51 +1100)]
cppmagic: New module

A module for some of the awesome / horrifying techniques described at:
    http://jhnet.co.uk/articles/cpp_magic
    https://github.com/pfultz2/Cloak/wiki/C-Preprocessor-tricks,-tips,-and-idioms

Start off with just some simple things.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years ago.travis.yml: Add -k to make check script
David Gibson [Mon, 1 Feb 2016 11:54:32 +0000 (22:54 +1100)]
.travis.yml: Add -k to make check script

At the moment when Travis runs make check it will stop on the first
failure.  That's not particularly useful, so add a -k so that all ccanlint
failures can be seen.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoccanlint: Report failures with --summary
David Gibson [Mon, 1 Feb 2016 11:50:45 +0000 (22:50 +1100)]
ccanlint: Report failures with --summary

When run in --summary mode ccanlint doesn't actually report whether it
passed or failed in the message .  In particular this means that when make
check is run with -j, it can be hard to tell which modules failed.

This adds a more obvious failure message.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoccanlint: add missing file for "info_ported" test.
Rusty Russell [Wed, 3 Feb 2016 06:04:05 +0000 (16:34 +1030)]
ccanlint: add missing file for "info_ported" test.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agorszshm: disable valgrind for tests.
Rusty Russell [Wed, 3 Feb 2016 05:41:05 +0000 (16:11 +1030)]
rszshm: disable valgrind for tests.

It returns EINVAL instead of ENOMEM for test/run.c line 96, then
complains on line 137:

==29368== Invalid read of size 4
==29368==    at 0x4033BC: main (run.c:137)
==29368==  Address 0x400000000018 is not stack'd, malloc'd or (recently) free'd

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agomem: add memtaint().
Rusty Russell [Wed, 3 Feb 2016 03:41:38 +0000 (14:11 +1030)]
mem: add memtaint().

Useful if you're going to reuse a buffer later.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoaltstack: fix _info test.
Rusty Russell [Wed, 3 Feb 2016 03:01:44 +0000 (13:31 +1030)]
altstack: fix _info test.

Since we use -Wundef by default, ccanlint gets upset if __X86_64__ isn't set.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agotools: commit missing support for _info ported flag.
Rusty Russell [Wed, 3 Feb 2016 02:49:57 +0000 (13:19 +1030)]
tools: commit missing support for _info ported flag.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoccanlint: add "_info ported" (for ccan/altstack).
Rusty Russell [Wed, 3 Feb 2016 02:27:33 +0000 (12:57 +1030)]
ccanlint: add "_info ported" (for ccan/altstack).

If _info handles the arg "ported" it should print out 1 or 0; 0 means
it can't be compiled/run/tested on this platform.  This lets ccanlint
easily skip such modules.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoidtree: Fix undefined behaviour (left shift of signed value)
David Gibson [Wed, 27 Jan 2016 13:17:47 +0000 (00:17 +1100)]
idtree: Fix undefined behaviour (left shift of signed value)

~0 will be signed and negative on any 2s complement system, and
left shifting a negative value has undefined behaviour in C.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoidtree: Fix misindented statement
David Gibson [Wed, 27 Jan 2016 13:14:43 +0000 (00:14 +1100)]
idtree: Fix misindented statement

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoidtree: Fix comparison is always false warning
David Gibson [Wed, 27 Jan 2016 13:14:19 +0000 (00:14 +1100)]
idtree: Fix comparison is always false warning

idtree.c:146 triggers a "comparison is always false" warning on some
compiler configurations, since the 'id' variable is unsigned.

Elsewhere in the module ids seem to be represented by (signed) ints, so
use the same convention here, suppressing the warning and also maybe being
more correct in other ways.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agohtable: Mark functions constructed by HTABLE_DEFINE_TYPE as UNNEEDED
David Gibson [Wed, 27 Jan 2016 13:06:02 +0000 (00:06 +1100)]
htable: Mark functions constructed by HTABLE_DEFINE_TYPE as UNNEEDED

The HTABLE_DEFINE_TYPE macro builds a type-specific hash table by
constructing a bunch of simple wrapper functions.  The user of the hash
table may not end up using all of these.  With gcc the fact that the
functions are inline stops an warnings about unused functions, but that's
not the case with clang.

Suppress these warnings by marking all the constructed functions except
for name##_add() as UNNEEDED (using the macro from ccan/compiler).  _add
is left alone on the grounds that a hash table you never add anything to
isn't much use, so this will help you to spot an entirely redundant
HTABLE_DEFINE_TYPE invocation.  *_init() would be a more obvious choice,
except that there is both *_init() and *_init_sized() and you only need
to use one of these.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agostrmap: Convert to using TCON_WRAP() instead of plain TCON()
David Gibson [Wed, 27 Jan 2016 12:52:12 +0000 (23:52 +1100)]
strmap: Convert to using TCON_WRAP() instead of plain TCON()

The usual way of construction strmap objects is to use the STRMAP_MEMBERS()
macro which expands to both a raw strmap structure and a tcon type canary.
However, the tcon type canary involves a flexible array member which means
that in standard C99 STRMAP_MEMBERS() must appear only at the end of a
structure definition.  But worse, that structure can then only appear at
the end of any other structure it is included in, which is pretty
inconvenient for the intended purpose of creating type specific strmaps.

gcc extensions allow this to work (somehow), but clang complains loudly
about it.

The tcon module already includes the TCON_WRAP() mechanism, which already
provides this same sort of type-specific definitions in a more general way.
So convert strmap (and its users) to that approach.

This removes STRMAP_MEMBERS() entirely, breaking compatibility.  I'm hoping
strmap is used in few enough places that we can get away with that.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaltstack: disable valgrind.
Rusty Russell [Fri, 29 Jan 2016 05:56:12 +0000 (16:26 +1030)]
altstack: disable valgrind.

It does not seem to respect stack games!

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoaltstack: New module
Dan Good [Tue, 26 Jan 2016 22:18:43 +0000 (22:18 +0000)]
altstack: New module

altstack - run a function with a dedicated stack, and then release the memory

Signed-off-by: Dan Good <dan@dancancode.com>
4 years agoaga: Annotate unused return values
David Gibson [Wed, 27 Jan 2016 12:11:31 +0000 (23:11 +1100)]
aga: Annotate unused return values

bfs_dequeue() and dfs_pop() discard the return values of lqueue_dequeue()
and lstack_pop() respectively.  This is correct, but causes warnings in
some compiler configurations (including the one currently used by
travis-ci.org).

Use the cast-to-void idiom to tell the compiler this is intentional.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoccanlint: Remove unused variable
David Gibson [Wed, 27 Jan 2016 12:06:05 +0000 (23:06 +1100)]
ccanlint: Remove unused variable

The 'rest' variable in examples_run.c:find_expect() was unused.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoconfigurator: Clarify empty if
David Gibson [Tue, 26 Jan 2016 11:28:41 +0000 (22:28 +1100)]
configurator: Clarify empty if

configurator.c contains an if with an empty statement on the same line as
the condition.  This is very easy to misread, and also causes a warning
from clang, so move the ; onto the next line.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years ago.travis.yml: Add clang builds to Travis
David Gibson [Tue, 26 Jan 2016 11:27:28 +0000 (22:27 +1100)]
.travis.yml: Add clang builds to Travis

Still not exactly a great coverage of different C compilers, but clearly
better than *just* gcc.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agorszshm: New module
Dan Good [Tue, 19 Jan 2016 06:04:02 +0000 (06:04 +0000)]
rszshm: New module

rszshm - resizable pointer-safe shared memory

Signed-off-by: Dan Good <dan@dancancode.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agotal/str: fix infinite loop of tal_fmt() with empty string.
Rusty Russell [Tue, 19 Jan 2016 06:36:55 +0000 (17:06 +1030)]
tal/str: fix infinite loop of tal_fmt() with empty string.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agopipecmd: add stderr fd arg.
Rusty Russell [Tue, 19 Jan 2016 03:45:25 +0000 (14:15 +1030)]
pipecmd: add stderr fd arg.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agopipecmd: fix fd leak.
Rusty Russell [Tue, 19 Jan 2016 03:13:07 +0000 (13:43 +1030)]
pipecmd: fix fd leak.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoio: io_time_override to insert fake times.
Rusty Russell [Mon, 18 Jan 2016 19:47:13 +0000 (06:17 +1030)]
io: io_time_override to insert fake times.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agodeque: check HAVE_STATEMENT_EXPR, tweaks from feedback
Dan Good [Tue, 5 Jan 2016 01:07:19 +0000 (01:07 +0000)]
deque: check HAVE_STATEMENT_EXPR, tweaks from feedback

Thanks to the detailed feedback from David Gibson, I made the
following improvements:

* add missing includes
* check for statement expression support, give an error if absent
* ccanlint directive to skip "without features" steps
* add license ref to top of source files
* rename run1.c test to api1.c

Signed-off-by: Dan Good <dan@dancancode.com>
4 years agodeque: New module
Dan Good [Wed, 23 Dec 2015 12:11:44 +0000 (12:11 +0000)]
deque: New module

deque - type-preserving resizing circular deque

Signed-off-by: Dan Good <dan@dancancode.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoAdd file describing Signed-off-by and guiding new module authors.
Rusty Russell [Mon, 14 Dec 2015 03:37:42 +0000 (14:07 +1030)]
Add file describing Signed-off-by and guiding new module authors.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agotweaks from feedback - thanks
Dan Good [Thu, 10 Dec 2015 10:48:55 +0000 (10:48 +0000)]
tweaks from feedback - thanks

4 years agoAdd xstring module - bounded string builder with three valued comparator
Dan Good [Thu, 10 Dec 2015 06:05:22 +0000 (06:05 +0000)]
Add xstring module - bounded string builder with three valued comparator

4 years agoMakefile-web: Quote the names in the error message
Joel Stanley [Wed, 9 Dec 2015 01:17:52 +0000 (11:47 +1030)]
Makefile-web: Quote the names in the error message

 progress found but fubar in MOD

is now:

 'progress' found but 'fubar' in MOD

Signed-off-by: Joel Stanley <joel@jms.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoweb/logo: Use a relative protocol
Joel Stanley [Wed, 9 Dec 2015 01:17:51 +0000 (11:47 +1030)]
web/logo: Use a relative protocol

The webfont forces http, which results in a mixed content warning if
you're visiting the site on https. Strip the protocol so we use whatever
the user has connected with.

Signed-off-by: Joel Stanley <joel@jms.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoMakefile-web: Download prettify from git
Joel Stanley [Wed, 9 Dec 2015 01:17:50 +0000 (11:47 +1030)]
Makefile-web: Download prettify from git

The SVN mirror disappeared some time ago. It now lives on Github.

Signed-off-by: Joel Stanley <joel@jms.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agopipecmd: test can't-exec case.
Rusty Russell [Fri, 20 Nov 2015 06:32:14 +0000 (17:02 +1030)]
pipecmd: test can't-exec case.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agopipecmd: add pipecmdarr variant.
Rusty Russell [Fri, 20 Nov 2015 06:29:09 +0000 (16:59 +1030)]
pipecmd: add pipecmdarr variant.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agotools/namespacize: use unlink_noerr.
Rusty Russell [Fri, 20 Nov 2015 06:27:05 +0000 (16:57 +1030)]
tools/namespacize: use unlink_noerr.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agonet: use close_noerr.
Rusty Russell [Fri, 20 Nov 2015 06:26:27 +0000 (16:56 +1030)]
net: use close_noerr.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agonoerr: add free_noerr().
Rusty Russell [Fri, 20 Nov 2015 06:22:34 +0000 (16:52 +1030)]
noerr: add free_noerr().

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoaga,agar: New shortcut2 sample graph and testcases based on it
David Gibson [Fri, 6 Nov 2015 01:26:17 +0000 (12:26 +1100)]
aga,agar: New shortcut2 sample graph and testcases based on it

This patch adds a new test graph "shortcut2" which includes a negative cost
edge.  Along with that we add a testcase for Dijkstra's algorithm checking
that it gracefully fails in this case.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaga,agar: New shortcut1 sample graph and testcases based on it
David Gibson [Fri, 6 Nov 2015 01:26:03 +0000 (12:26 +1100)]
aga,agar: New shortcut1 sample graph and testcases based on it

For all the existing test graphs, the shortest path by cost is also the
shortest path by number of edges.  This patch adds a new test graph where
that is not the case, in order to test that the Dijkstra's algorithm
implementation correctly handles that case.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaga,agar: Non-equal edge costs for parallel test graph
David Gibson [Fri, 6 Nov 2015 01:25:50 +0000 (12:25 +1100)]
aga,agar: Non-equal edge costs for parallel test graph

At the moment the "parallel" test graph just uses the default cost of 1
for all the links between the two nodes.  This patch changes that so that
the links have cost 2, except (optionally) one with cost 1.  This provides
a useful test for the Dijkstra's algorithm implementation to ensure that
it picks the correct link for the shortest path.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaga,agar: Dijkstra's algorithm
David Gibson [Fri, 6 Nov 2015 01:25:30 +0000 (12:25 +1100)]
aga,agar: Dijkstra's algorithm

Implement Dijkstra's algorithm for one-source shortest-path.

This uses the lpq module as the implementation of the priority queue.  That
means this implementation is some way behind the theoretical efficiency of
Dijkstra's algorithm.  It should be reasonably straightforward to swap out
the priority queue for a better one in the future, though.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaga,agar: Add edge costs
David Gibson [Fri, 6 Nov 2015 01:23:53 +0000 (12:23 +1100)]
aga,agar: Add edge costs

This allows the edge_info callback to supply a cost or length for an edge.
For now we only support 'long' valued costs.  If the callback doesn't
supply a cost, it's considered cost 1.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoMakefile-ccan: add pipecmd
Rusty Russell [Fri, 20 Nov 2015 05:40:51 +0000 (16:10 +1030)]
Makefile-ccan: add pipecmd

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agopipecmd: new module.
Rusty Russell [Fri, 20 Nov 2015 05:39:48 +0000 (16:09 +1030)]
pipecmd: new module.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agostrgrp: Cache cosine popcounts to reduce computation
Andrew Jeffery [Sun, 15 Nov 2015 10:14:57 +0000 (20:44 +1030)]
strgrp: Cache cosine popcounts to reduce computation

Neatly, this reduces some of the OpenMP-related noise in the
implementation by removing the need for the include. The loop body of
grp_for() is also clearer as a result of the change; the changes to the
function interfaces motivated a re-think of the complexity here.

4 years agostrgrp: Fix indexing of per-thread storage for cosine filter
Andrew Jeffery [Fri, 13 Nov 2015 12:25:19 +0000 (22:55 +1030)]
strgrp: Fix indexing of per-thread storage for cosine filter

4 years agoaga: Add aga_node_needs_update() internal function
David Gibson [Thu, 12 Nov 2015 11:21:10 +0000 (22:21 +1100)]
aga: Add aga_node_needs_update() internal function

There are situations where aga algorithms may want to check if a node is
up-to-date (i.e. has yet been discovered by the current algorithm) without
making it up to date if it's not.  This adds an internal function to do so.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agostrgrp: Add cosine similarity filter
Andrew Jeffery [Thu, 24 Sep 2015 12:49:39 +0000 (22:19 +0930)]
strgrp: Add cosine similarity filter

The cosine similarity measure[1] (O(m + n)) contributes a decent runtime
reduction when used as a filter prior to execution of more expensive
algorithms such as LCS[2] (O(m * n)).

A private test set of 3500 strings was used to quantify the improvement.
The shape of the test set is described by Python's Pandas module as:

    >>> frames.apply(len).describe()
    count    3500.000000
    mean       47.454286
    std        14.980197
    min        10.000000
    25%        37.000000
    50%        45.000000
    75%        61.000000
    max       109.000000
    dtype: float64
    >>>

The tests were performed on a lightly loaded Lenovo X201s stocked with a
Intel Core i7 L 640 @ 2.13GHz CPU with 3.7 GiB of memory. The test was
compiled with GCC 4.9.3:

    $ gcc --version
    gcc (Gentoo 4.9.3 p1.0, pie-0.6.2) 4.9.3
    Copyright (C) 2015 Free Software Foundation, Inc.
    This is free software; see the source for copying conditions.  There is NO
    warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Using the test program outlined below, ten runs for input set sizes
incrementing in batches of 500 were taken prior to filtering with cosine
similarity:

    500:  0.61, 0.25, 0.08, 0.07, 0.07, 0.07, 0.09, 0.07, 0.07, 0.07
    1000: 0.33, 0.32, 0.34, 0.32, 0.32, 0.33, 0.32, 0.32, 0.34, 0.32
    1500: 0.72, 1.53, 0.72, 0.70, 0.72, 0.70, 0.72, 0.71, 1.46, 0.71
    2000: 1.22, 1.20, 1.22, 1.98, 1.20, 1.20, 1.22, 1.94, 1.20, 1.20
    2500: 1.97, 2.72, 1.94, 2.33, 2.44, 1.94, 2.82, 1.93, 1.94, 2.69
    3000: 2.69, 3.41, 2.66, 3.38, 2.67, 3.42, 2.63, 3.44, 2.65, 3.39
    3500: 4.18, 3.65, 4.21, 4.21, 3.56, 4.21, 4.16, 3.63, 4.20, 4.13

After adding the cosine similarity filter the runtimes became:

    500:  0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02
    1000: 0.08, 0.07, 0.07, 0.07, 0.08, 0.07, 0.07, 0.08, 0.07, 0.07
    1500: 0.16, 0.16, 0.15, 0.16, 0.16, 0.15, 0.15, 0.15, 0.16, 0.16
    2000: 0.26, 0.26, 0.25, 0.26, 0.26, 0.26, 0.25, 0.26, 0.26, 0.26
    2500: 0.41, 0.41, 0.41, 0.40, 0.42, 0.42, 0.42, 0.41, 0.41, 0.41
    3000: 0.58, 0.56, 0.57, 0.56, 0.58, 0.57, 0.56, 0.56, 0.57, 0.55
    3500: 0.75, 0.74, 0.73, 0.74, 0.74, 0.73, 0.72, 0.75, 0.75, 0.75

As such, on average the runtime improvements are:

    N       Avg Pre         Avg Post        Improvement (Pre / Post)
    500     0.145           0.02            7.25
    1000    0.326           0.073           4.47
    1500    0.869           0.156           5.57
    2000    1.358           0.258           5.26
    2500    2.272           0.412           5.51
    3000    3.034           0.566           5.36
    3500    4.014           0.74            5.42

The test driver is as below, where both it and its dependencies were
compiled with 'CFLAGS=-O2 -fopenmp' and linked with 'LDFLAGS=-fopenmp',
'LDLIBS=-lm':

    $ cat test.c
    #include "config.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "ccan/strgrp/strgrp.h"

    int main(void) {
        FILE *f;
        char *buf;
        struct strgrp *ctx;
        f = fdopen(0, "r");
    #define BUF_SIZE 512
        buf = malloc(BUF_SIZE);
        ctx = strgrp_new(0.85);
        while(fgets(buf, BUF_SIZE, f)) {
            buf[strcspn(buf, "\r\n")] = '\0';
            if (!strgrp_add(ctx, buf, NULL)) {
                printf("Failed to classify %s\n", buf);
            }
        }
        strgrp_free(ctx);
        free(buf);
        fclose(f);
        return 0;
    }

[1] https://en.wikipedia.org/wiki/Cosine_similarity
[2] https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

4 years agoaga: Error codes
David Gibson [Tue, 3 Nov 2015 03:20:14 +0000 (14:20 +1100)]
aga: Error codes

Add an enum to record error codes for aga routines.  The current
algorithms, dfs and bfs don't have any error conditions except those
reported by callbacks.  So, for now, the only code is "no error", but this
will be expanded in future.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaga: Fix initialization bug in aga_for_each_edge_info
David Gibson [Tue, 3 Nov 2015 02:01:07 +0000 (13:01 +1100)]
aga: Fix initialization bug in aga_for_each_edge_info

The aga_for_each_edge_info macro is constructed so that if the edge_info
callback returns an error, the for loop terminates early and leaves the
_err parameter set to the error.  On successful completion of the loop,
_err should be zero.

However, on a node with no edges, _err will not be initialized, meaning
that it could be non-zero even on successful (trivial) completion of the
loop.  This fixes the bug.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoaga: Add function block comments
David Gibson [Mon, 2 Nov 2015 23:48:19 +0000 (10:48 +1100)]
aga: Add function block comments

Add block comments in the usual ccan format describing a number of the
important functions in the aga module.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agolpq: New module
David Gibson [Tue, 27 Oct 2015 11:10:27 +0000 (22:10 +1100)]
lpq: New module

Simple, slow priority queue implementation.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agolqueue: Streamline interface with TCON_CONTAINER
David Gibson [Tue, 20 Oct 2015 04:12:55 +0000 (15:12 +1100)]
lqueue: Streamline interface with TCON_CONTAINER

The interfaces the lqueue module currently has implement (partial) type
safety in a somewhat clunky way - types and member names need to be passed
to a number of entry points.

This patch uses the new TCON_CONTAINER magic to stash the typing
information into the declaration of the queue object, so it no longer needs
to be explicitly passed to later calls.

This does alter the lqueue interface incompatibly.  I think the module
is young enough that we can reasonably do that.  One other module,
'aga', was using lqueue, and this also includes fixes so that it still
works.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agolstack: Streamline interface with TCON_CONTAINER
David Gibson [Tue, 20 Oct 2015 03:34:02 +0000 (14:34 +1100)]
lstack: Streamline interface with TCON_CONTAINER

The interfaces the lstack module currently has implement (partial) type
safety in a somewhat clunk way - types and member names need to be passed
to a number of entry points.

This patch uses the new TCON_CONTAINER magic to stash the typing
information into the declaration of the stack object, so it no longer needs
to be explicitly passed to later calls.

This does alter the lstack interface incompatibly.  I think the module
is young enough that we can reasonably do that.  One other module,
'aga', was using lstack, and this also includes fixes so that it still
works.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agotcon: Encode information on container members in "type" canaries
David Gibson [Tue, 20 Oct 2015 02:18:17 +0000 (13:18 +1100)]
tcon: Encode information on container members in "type" canaries

Add "container canaries" to tcon.  This allows information about a specific
member of a container structure to be encoded with TCON or TCON_WRAP.  Once
that's done, tcon_container_of() and tcon_member_of() can be used to
translate between member and container pointers based on the canary
information, without having to repeat the type and member details.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agotcon: Encode integer values into "type" canaries
David Gibson [Tue, 20 Oct 2015 01:34:30 +0000 (12:34 +1100)]
tcon: Encode integer values into "type" canaries

Add the ability to encode, as well as types, integer values (must be
positive, compile time constant and in the range of size_t) into TCON
constructed "type" canaries.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agotcon: Add tcon_sizeof() helper
David Gibson [Mon, 19 Oct 2015 14:46:41 +0000 (01:46 +1100)]
tcon: Add tcon_sizeof() helper

Add a new tcon_sizeof() helper macro which returns the size of a type for
which a canary has been constructed with TCON or TCON_WRAP.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agotcon: Add an alternate way of building type canaries
David Gibson [Tue, 20 Oct 2015 03:23:37 +0000 (14:23 +1100)]
tcon: Add an alternate way of building type canaries

The tcon module allows you to add "type canaries" to a structures, which
can be used for later typechecks.  The canaries are implemented using
a flexible array member, to avoid them taking any actual space at runtime.
That means the canaries must go at the end of your structure.

That doesn't seem like a big limitation, except that it also means the
structure containing the canaries must be at the end of any structure it
is embedded in in turn, which is a rather more serious limitation.

This patch adds a TCON_WRAP() macro which wraps a given type in a new type
which also contains type canaries, and doesn't suffer the last member
limitation.  The drawback is that if the wrapped type has smaller size than
a pointer, the type canaries will pad the wrapped type out to the size of a
pointer.

By constructing the wrappers carefully, the existing tcon macros will work
on both wrapper types constructed with TCON_WRAP and on structures
explicitly including TCON type canaries.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agolstack, lqueue: Move from MODS_WITH_SRC to MODS_NO_SRC
David Gibson [Sun, 25 Oct 2015 12:30:55 +0000 (23:30 +1100)]
lstack, lqueue: Move from MODS_WITH_SRC to MODS_NO_SRC

The lstack and lqueue modules are entirely implemented in a single header.
However, in Makefile-ccan they're listed in MODS_WITH_SRC, instead of
MODS_NO_SRC.  This appears to be harmless, but this patch moves them to
the correct category anyway.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoptrint: ptr2int and int2ptr are constant functions
David Gibson [Sun, 25 Oct 2015 12:00:06 +0000 (23:00 +1100)]
ptrint: ptr2int and int2ptr are constant functions

By construction these functions depend only on their arguments, so declare
them as CONST_FUNCTION using the helper from ccan/compiler.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoFixing odd formatting of info caused by unnecessary indentations.
Paul Wayper [Wed, 21 Oct 2015 21:07:15 +0000 (08:07 +1100)]
Fixing odd formatting of info caused by unnecessary indentations.

4 years agoopt: don't use raw malloc for errors.
Rusty Russell [Wed, 21 Oct 2015 05:35:49 +0000 (16:05 +1030)]
opt: don't use raw malloc for errors.

We should be allocating them with opt's allocator (we use it to free them!).

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agomem: switch descriptions for memeqzero/memeqstr
Rusty Russell [Tue, 20 Oct 2015 03:17:59 +0000 (13:47 +1030)]
mem: switch descriptions for memeqzero/memeqstr

Closes: #32
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
4 years agoRemove stale file ccan/priority_queue/test/run.c
David Gibson [Sun, 18 Oct 2015 10:45:01 +0000 (21:45 +1100)]
Remove stale file ccan/priority_queue/test/run.c

In commit 3782543 "order: Scalar comparison functions", I accidentally
checked in a file which didn't belong with that commit, and was actually
from a module I was experimenting with but wasn't ready to commit.

This cleans up the bogus extra file.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agoorder: total_order_cmp() helper and better tests
David Gibson [Sun, 18 Oct 2015 10:10:58 +0000 (21:10 +1100)]
order: total_order_cmp() helper and better tests

Add a wrapper macro total_order_cmp() to more conveniently use the
total_order structures.  Add some tests for it, which also improve tests
the "fancy_cmp" function.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
4 years agotal/str: fix error in tal_strndup()
Rusty Russell [Fri, 16 Oct 2015 19:42:40 +0000 (06:12 +1030)]
tal/str: fix error in tal_strndup()

It used strlen() on the source, which might not be valid.

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