Commit Graph

269 Commits

Author SHA1 Message Date
Rusty Russell 3e733afb2b gossipd: remove broadcast map altogether.
This clarifies things a fair bit: we simply add and remove from the
gossip_store directly.

Before this series: (--disable-developer, -Og)
    store_load_msec:20669-20902(20822.2+/-82)
    vsz_kb:439704-439712(439706+/-3.2)
    listnodes_sec:0.890000-1.000000(0.92+/-0.04)
    listchannels_sec:11.960000-13.380000(12.576+/-0.49)
    routing_sec:3.070000-5.970000(4.814+/-1.2)
    peer_write_all_sec:28.490000-30.580000(29.532+/-0.78)

After: (--disable-developer, -Og)
    store_load_msec:19722-20124(19921.6+/-1.4e+02)
    vsz_kb:288320
    listnodes_sec:0.860000-0.980000(0.912+/-0.056)
    listchannels_sec:10.790000-12.260000(11.65+/-0.5)
    routing_sec:2.540000-4.950000(4.262+/-0.88)
    peer_write_all_sec:17.570000-19.500000(18.048+/-0.73)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-06-04 01:29:39 +00:00
Rusty Russell 5591c0b5d8 gossipd: don't send gossip stream, let per-peer daemons read it themselves.
Keeping the uintmap ordering all the broadcastable messages is expensive:
130MB for the million-channels project.  But now we delete obsolete entries
from the store, we can have the per-peer daemons simply read that sequentially
and stream the gossip itself.

This is the most primitive version, where all gossip is streamed;
successive patches will bring back proper handling of timestamp filtering
and initial_routing_sync.

We add a gossip_state field to track what's happening with our gossip
streaming: it's initialized in gossipd, and currently always set, but
once we handle timestamps the per-peer daemon may do it when the first
filter is sent.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-06-04 01:29:39 +00:00
Rusty Russell df00f20e4a gossipd: erase old entries from the store, don't just append.
We use the high bit of the length field: this way we can still check
that the checksums are valid on deleted fields.

Once this is done, serially reading the gossip_store file will result
in a complete, ordered, minimal gossip broadcast.  Also, the horrible
corner case where we might try to delete things from the store during
load time is completely gone: we only load non-deleted things.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-06-04 01:29:39 +00:00
Rusty Russell 696dc6b597 gossipd: disable gossip_store upgrade.
We're about to bump version again, and the code to upgrade it was
quite hairy (and buggy!).  It's not worthwhile for such a
poorly-tested path: I will just add code to limit how much incoming
gossip we get to avoid flooding when we upgrade, however.

I also use a modern gossip_store version in our test_gossip_store_load
test, instead of relying on the upgrade path.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-06-04 01:29:39 +00:00
Rusty Russell 180a552fba gossip_store: mark private updates separately from normal ones.
They're really gossipd-internal, and we don't want per-peer daemons
to confuse them with normal updates.

I don't bump the gossip_store version; that's coming with another update
anyway.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-06-04 01:29:39 +00:00
Rusty Russell 654e89b5fc gossipd: free channels in routing_state destructor.
Cleans up the tests.

Suggested-by: @ZmnSCPxj
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-05-22 11:28:44 +00:00
Rusty Russell d1f43d993a gossipd: use explicit destructor for struct chan.
Each destructor2 costs 40 bytes, and struct chan is only 120 bytes.  So
this drops our memory usage quite a bit:

MCP bench results change:
   -vsz_kb:580004-580016(580006+/-4.8)
   +vsz_kb:533148

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-05-22 11:28:44 +00:00
Rusty Russell cb9c44ef27 gossipd: remove unnecessary dev_unknown_channel_satoshis arg.
We now have a test blockchain for MCP which has the correct channels,
so this is not needed.

Also fix a benchmark script bug where 'mv "$DIR"/log
"$DIR"/log.old.$$' would fail if you log didn't exist from a previous run.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-05-22 11:28:44 +00:00
Rusty Russell 0e37ac2433 common: move gossip_store read routine where subdaemons can access it.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-05-13 05:16:18 +00:00
Rusty Russell 7ede5aac31 gossip_store: change format so we store raw messages.
Save some overhead, plus gets us ready for giving subdaemons direct
store access.  This is the first time we *upgrade* the gossip_store,
rather than just discarding.

The downside is that we need to add an extra message after each
channel_announcement, containing the channel capacity.

After:
  store_load_msec:28337-30288(28975+/-7.4e+02)
  vsz_kb:582304-582316(582306+/-4.8)
  store_rewrite_sec:11.240000-11.800000(11.55+/-0.21)
  listnodes_sec:1.800000-1.880000(1.84+/-0.028)
  listchannels_sec:22.690000-26.260000(23.878+/-1.3)
  routing_sec:2.280000-9.570000(6.842+/-2.8)
  peer_write_all_sec:48.160000-51.480000(49.608+/-1.1)

Differences:
  -vsz_kb:582320
  +vsz_kb:582316
  -listnodes_sec:2.100000-2.170000(2.118+/-0.026)
  +listnodes_sec:1.800000-1.880000(1.84+/-0.028)
  -peer_write_all_sec:51.600000-52.550000(52.188+/-0.34)
  +peer_write_all_sec:48.160000-51.480000(49.608+/-1.1)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-05-13 05:16:18 +00:00
Rusty Russell 0fc42415c2 gossipd/routing: remove BFG implementation.
Now we can benchmark, and remove 500 bytes per node.

MCP results from 5 runs, min-max(mean +/- stddev):
	store_load_msec:35093-37907(36146+/-1.1e+03)
	vsz_kb:555168
	store_rewrite_sec:12.120000-13.750000(12.7+/-0.6)
	listnodes_sec:1.270000-1.370000(1.322+/-0.039)
	listchannels_sec:29.770000-31.600000(30.82+/-0.64)
	routing_sec:0.00
	peer_write_all_sec:63.630000-67.850000(65.432+/-1.7)

MCP notable changes from pre-Dijkstra (>1 stddev):
	-vsz_kb:577456
	+vsz_kb:555168
	-routing_sec:60.70
	+routing_sec:12.04

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-18 06:33:09 +00:00
Rusty Russell e197956032 gossipd/routing: Iterate on Dijkstra when route is too long.
If a route is too long, we try to bias Dijkstra towards choosing a
shorter route by adding a per-hop cost.  We do a naive "shortest path"
pass, then using that cost as a ceiling on per-hop cost, we do a
binary search.

There are some subtleties: we use risk rather than total as our
counter field (we normally bias this by 1 anyway, so it's easy to make
that a variable), and we set riskfactor to a mimimal value once we're
iterating.  It's good enough to get a solution, we don't need to do a
2-dimensional search on riskfactor and riskbias.

Of course, this is extremely slow if we hit it on our benchmark,
though it doesn't happen in a more realistic network:

$ gossipd/test/run-bench-find_route 100000 100:

Before:
	100 (79 succeeded) routes in 100000 nodes in 25341 msec (253412314 nanoseconds per route)

After:
	100 (100 succeeded) routes in 100000 nodes in 97346 msec (973461784 nanoseconds per route)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-18 06:33:09 +00:00
Rusty Russell 7caa37f0f1 gossipd: implement Dijkstra.
Use a uintmap as our minheap.

Note that Dijkstra can give overlength routes, so some checks are disabled.

Comparison using gossipd/test/run-bench-find_route 100000 10:

Before:
	10 (10 succeeded) routes in 100000 nodes in 120087 msec (12008708402 nanoseconds per route)
After:
	10 (10 succeeded) routes in 100000 nodes in 2269 msec (226925462 nanoseconds per route)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-18 06:33:09 +00:00
Rusty Russell 6dfa46d65a gossipd/test: add test for handling overlong routes.
This is a weakness with Dijkstra, so write an explicit unit test that
we can find a short enough (but more expensive) route.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-18 06:33:09 +00:00
Rusty Russell 261921dee2 gossipd: adjust peers' broadcast_offset when compacting store.
When we compact the store, we need to adjust the broadast index for
peers so they know where they're up to.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-11 18:31:34 -07:00
Rusty Russell fdb42c3170 gossipd: don't keep channel_updates in memory.
This requires some trickiness when we want to re-add unannounced channels
to the store after compaction, so we extract a common "copy_message" to
transfer from old store to new.

MCP results from 5 runs, min-max(mean +/- stddev):
	store_load_msec:36034-37853(37109.8+/-5.9e+02)
	vsz_kb:577456
	store_rewrite_sec:12.490000-13.250000(12.862+/-0.27)
	listnodes_sec:1.250000-1.480000(1.364+/-0.09)
	listchannels_sec:30.820000-31.480000(31.068+/-0.24)
	routing_sec:26.940000-27.990000(27.616+/-0.39)
	peer_write_all_sec:65.690000-68.600000(66.698+/-0.99)

MCP notable changes from previous patch (>1 stddev):
	-vsz_kb:1202316
	+vsz_kb:577456

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-11 18:31:34 -07:00
Rusty Russell eb4564c3cd gossipd: embed broadcast information into each structure.
This is more compact, but also required once we replace the arbitrary
"index" with an actual offset into the gossip store.  That will let us
remove the in-memory variants entirely.

MCP results from 5 runs, min-max(mean +/- stddev):
	store_load_msec:35685-38538(37090.4+/-9.1e+02)
	vsz_kb:2288768
	store_rewrite_sec:35.530000-41.230000(37.904+/-2.3)
	listnodes_sec:0.720000-0.810000(0.762+/-0.041)
	listchannels_sec:30.750000-35.990000(32.704+/-2)
	routing_sec:29.570000-34.010000(31.374+/-1.8)
	peer_write_all_sec:51.140000-58.350000(55.69+/-2.4)

MCP notable changes from previous patch (>1 stddev):
	-vsz_kb:2621808
	+vsz_kb:2288768

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-11 18:31:34 -07:00
Rusty Russell 91849dddc4 wire: use struct node_id for node ids.
Don't turn them to/from pubkeys implicitly.  This means nodeids in the store
don't get converted, but bitcoin keys still do.

MCP results from 5 runs, min-max(mean +/- stddev):
	store_load_msec:33934-35251(34531.4+/-5e+02)
	vsz_kb:2637488
	store_rewrite_sec:34.720000-35.130000(34.94+/-0.14)
	listnodes_sec:1.020000-1.290000(1.146+/-0.086)
	listchannels_sec:51.110000-58.240000(54.826+/-2.5)
	routing_sec:30.000000-33.320000(30.726+/-1.3)
	peer_write_all_sec:50.370000-52.970000(51.646+/-1.1)

MCP notable changes from previous patch (>1 stddev):
	-store_load_msec:46184-47474(46673.4+/-4.5e+02)
	+store_load_msec:33934-35251(34531.4+/-5e+02)
	-vsz_kb:2638880
	+vsz_kb:2637488
	-store_rewrite_sec:46.750000-48.280000(47.512+/-0.51)
	+store_rewrite_sec:34.720000-35.130000(34.94+/-0.14)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-09 12:37:16 -07:00
Rusty Russell a2fa699e0e Use node_id everywhere for nodes.
I tried to just do gossipd, but it was uncontainable, so this ended up being
a complete sweep.

We didn't get much space saving in gossipd, even though we should save
24 bytes per node.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-09 12:37:16 -07:00
Rusty Russell 417e1bab7d gossipd: use iterator helpers for iterating node channels.
Makes the next step easier.

MCP results from 5 runs, min-max(mean +/- stddev):
	store_load_msec:45791-46917(46330.4+/-3.6e+02)
	vsz_kb:2641316
	store_rewrite_sec:47.040000-48.720000(47.684+/-0.57)
	listnodes_sec:1.140000-1.340000(1.2+/-0.072)
	listchannels_sec:50.970000-54.250000(52.698+/-1.3)
	routing_sec:29.950000-31.010000(30.332+/-0.37)
	peer_write_all_sec:51.570000-52.970000(52.1+/-0.54)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-09 12:37:16 -07:00
Rusty Russell 2bd7df93c6 gossipd: preserve unannounced channels across store compaction.
Otherwise we'd forget them on restart, again.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-08 04:41:43 +00:00
Rusty Russell 5b12007a4f gossipd: dev option to allow unknown channels.
This lets us benchmark without a valid blockchain.

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



Header from folded patch 'fixup!_gossipd__dev_option_to_allow_unknown_channels.patch':

fixup! gossipd: dev option to allow unknown channels.

Suggested-by: @cdecker
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-08 04:41:43 +00:00
Rusty Russell f8f6533dba dev: --dev-gossip-time so gossipd doesn't prune old data.
This is useful for canned data, such as the million channels project.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-08 04:41:43 +00:00
Rusty Russell b2c93beaed gossipd: use htable instead of simple array for node's channels.
For giant nodes, it seems we spend a lot of time memmoving this array.
Normally we'd go for a linked list, but that's actually hard: each
channel has two nodes, so needs two embedded list pointers, and when
iterating there's no good way to figure out which embedded pointer
we'd be using.

So we (ab)use htable; we don't really need an index, but it's good for
cache-friendly iteration (our main operation).  We can actually change
to a hybrid later to avoid the extra allocation for small nodes.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-04-08 04:41:43 +00:00
Rusty Russell 00f3a84af2 test: fix thinko in gossipd/test/run-bench-find_route.c
Reported-by: @cdecker
Fixes: #2440
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-03-05 11:42:43 +01:00
Rusty Russell 28f5da7b2f tools/generate-wire: use amount_msat / amount_sat for peer protocol.
Basically we tell it that every field ending in '_msat' is a struct
amount_msat, and 'satoshis' is an amount_sat.  The exceptions are
channel_update's fee_base_msat which is a u32, and
final_incorrect_htlc_amount's incoming_htlc_amt which is also a
'struct amount_msat'.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-02-21 08:01:37 +00:00
Rusty Russell 3ac0e814d0 daemons: use amount_msat/amount_sat in all internal wire transfers.
As a side-effect of using amount_msat in gossipd/routing.c, we explicitly
handle overflows and don't need to pre-prune ridiculous-fee channels.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-02-21 08:01:37 +00:00
Rusty Russell b99293fbb6 short_channel_id: don't accept :-separated in JSON if --allow-deprecated-apis=false
We need to still accept it when parsing the database, but this flag
should allow upgrade testing for devs building on top

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-02-08 16:52:30 -08:00
Rusty Russell 358b7fda91 getroute: allow caller to specify maximum hops.
This is required for routeboost.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-01-15 12:01:38 +01:00
Rusty Russell c0cfddfa95 test/run-bench-find_route: fix so it runs properly.
We didn't populate the channels properly so it always failed.

Additionally, somewhere along the line we kept using the single scid
so we only created one channel.

Also, the next patch will start comparing the pubkeys, so make valid
ones: use an array so we don't affect the benchmark too much.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2019-01-15 12:01:38 +01:00
Christian Decker 659a26ea5a misc: Update short_channel_id representation to use 'x' separators
Reported-by: Alex Bosworth <@alexbosworth>
Signed-off-by: Christian Decker <decker.christian@gmail.com>
2019-01-15 03:50:27 +00:00
Rusty Russell ab735dcbe6 gossipd: wire up memleak detection.
For simplicity we dump leaks to logs, and just return a bool to master.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-11-22 05:15:42 +00:00
Rusty Russell 9620393109 gossipd: store chainparams internally.
We keep a chain_hash in struct daemon, becayse otherwise we end up with
`&peer->daemon->rstate->chainparams->genesis_blockhash` which is a bit
ridiculous.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-11-21 21:43:37 +00:00
Rusty Russell 5c60d7ffb2 gossipd: split wire types into msgs from lightningd and msgs from per-peer daemons
This avoids some very ugly switch() statements which mixed the two,
but we also take the chance to rename 'towire_gossip_' to
'towire_gossipd_' for those inter-daemon messages; they're messages to
gossipd, not gossip messages.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-11-21 00:36:31 +00:00
Christian Decker 8e83d43c39 opts: Split early from non-early args so plugins can register theirs
The idea is that `plugin` is an early arg that is parsed (from command
line or the config file). We can then start the plugins and have them
tell us about the options they'd like to add to the mix, before we
actually parse them.

Signed-off-by: Christian Decker <@cdecker>
2018-11-13 00:44:50 +01:00
lisa neigut b9331e5ac8 gossipd: parse and respect optional `htlc_maximum_msat`
If another channel has set the optional `htlc_maximum_msat` field,
we should correctly parse that field and respect it when drawing up
routes for payments.
2018-10-09 23:22:52 +00:00
lisa neigut b1ceaf9910 gossipd: Update BOLT-split flags in channel_update
BOLT 7's been updated to split the flags field in `channel_update`
into two: `channel_flags` and `message_flags`. This changeset does the
minimal necessary to get to building with the new flags.
2018-09-21 00:24:12 +00:00
Christian Decker 84905eac2b routing: Make the capacity a parameter to new_chan
As pointed out by @rustyrussell the capacity is now always defined, so we can
fold that into the construction of the channel itself.

Reported-by: Rusty Russell <@rustyrussell>
Signed-off-by: Christian Decker <@cdecker>
2018-08-06 22:46:02 +02:00
Christian Decker 8201764117 routing: Skip channels that require larger HTLCs than we are routing
The `htlc_minimum_msat` parameter was ignored so far, and we'd be attempting to
pay and hitting a brick wall by doing so. This patch just skips channels that
are not eligible anyway.
2018-08-06 22:46:02 +02:00
Christian Decker 14000a22bc routing: Skip channels that don't have sufficient capacity
We know the total channel capacity after checking for its existence on-chain, so
we can actually make use of that information to discard channels that don't have
a sufficient capacity anyway, reducing the number of failed attempts.
2018-08-06 22:46:02 +02:00
Christian Decker 8a34933c1a gossip: Annotate locally added channels with their capacity
We were adding channels without their capacity, and eventually annotated them
when we exchanged `channel_update`s. This worked as long as we weren't
considering the channel capacity, but would result in local-only channels to be
unusable once we start checking.
2018-08-06 22:46:02 +02:00
Rusty Russell 7b2641ed0d gossipd: remove peer-related fields and wire messages.
This completes the removal of peer-related messages.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-07-25 02:13:52 +00:00
Rusty Russell 0d442b5ff2 gossipd: move files into connectd.
These source files are only used for peer-related things, so move them.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-07-25 02:13:52 +00:00
Rusty Russell fed5a117e7 Update ccan/structeq.
structeq() is too dangerous: if a structure has padding, it can fail
silently.

The new ccan/structeq instead provides a macro to define foo_eq(),
which does the right thing in case of padding (which none of our
structures currently have anyway).

Upgrade ccan, and use it everywhere.  Except run-peer-wire.c, which
is only testing code and can use raw memcmp(): valgrind will tell us
if padding exists.

Interestingly, we still declared short_channel_id_eq, even though
we didn't define it any more!

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-07-04 23:57:00 +02:00
arowser 25f60f9456 remove unused return value 2018-06-30 04:27:34 +00:00
Christian Decker 74a1cbd877 gossip: Implement gossip_store compaction
Signed-off-by: Christian Decker <decker.christian@gmail.com>
2018-06-09 13:38:46 +02:00
Rusty Russell def18a7bc1 gossipd: implement broadcast_del to delete a specific index.
Required if we want to reorder node_announcement broadcasts.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-06-08 17:53:34 +02:00
Rusty Russell a38c619486 gossipd: keep index of node and channel announcements.
This lets detect if a node announce preceeds a channel announce once we
delete the node announcement.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-06-08 17:53:34 +02:00
Rusty Russell 7a32637b5f gossipd: add timestamp to each broadcast message.
This lets us filter by timestamp.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-06-06 03:25:56 +00:00
Rusty Russell 8ee60e2d8e testing: make sure we don't see gossip in bad order.
This is something which generally shouldn't happen, but we didn't
notice it previously.

We ignore this warning in the case where a channel was deleted: this
happens because one side can send an update while the other notices
that the channel is closed.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-05-19 15:52:56 -04:00
Rusty Russell 177a1fc88e gossipd: handle local channel creation separately from update.
Note: this will break the gossip_store if they have current channels,
but it will fail to parse and be discarded.

Have local_add_channel do just that: the update is logically separate
and can be sent separately.

This removes the ugly 'bool add_to_store' flag.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-05-19 15:52:56 -04:00
Rusty Russell cca791d1cb routing: clean up channel public/active states.
1. If we have a channel_announcement, the channel is public, otherwise
   it's not.  Not all channels are public, as they can be local: those
   have a NULL channel_announcement.

2. If we don't have a channel_update, we know nothing about that half
   of the channel, and no other fields are valid.

3. We can tell if a half channel is disabled by the flags field directly.

Note that we never send halfchannels without an update over
gossip_getchannels_reply so that marshalling/unmarshalling can be
vastly simplified.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-05-10 21:35:53 +02:00
Rusty Russell 9d1e496b11 gossipd: use a real update in local_add_channel.
We generate one now, so let's use it.  That lets us simplify the
code, too.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-05-10 21:35:53 +02:00
Rusty Russell c71e16f784 broadcast: invert ownership of messages.
Make the update/announce messages own the element in the broadcast map
not the other way around.

Then we keep a pointer to the message, and when we free it
(eg. channel closed, update replaces it), it gets freed from the
broadcast map automatically.

The result is much nicer!

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-05-10 21:35:53 +02:00
Rusty Russell d40d22b68e gossipd: don't try to connect to non-routable addresses.
Someone could try to announce an internal address, and we might probe
it.

This breaks tests, so we add '--dev-allow-localhost' for our tests, so
we don't eliminate that one.  Of course, now we need to skip some more
tests in non-developer mode.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-05-07 22:37:28 +02:00
Rusty Russell 73cd009a4c gossipd/lightningd: use wireaddr_internal.
This replacement is a little menial, but it explicitly catches all
the places where we allow a local socket.  The actual implementation of
opening a AF_UNIX socket is almost hidden in the patch.

The detection of "valid address" is now more complex:

	p->addr.itype != ADDR_INTERNAL_WIREADDR || p->addr.u.wireaddr.type != ADDR_TYPE_PADDING

But most places we do this, we should audit: I'm pretty sure we can't
get an invalid address any more from gossipd (they may be in db, but
we should fix that too).

Closes: #1323
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-05-07 22:37:28 +02:00
practicalswift 5db73c6e27 Avoid static analyzer warnings about potentially uninitialized values 2018-05-01 17:14:33 +02:00
practicalswift abf510740d Force the use of the POSIX C locale for all commands and their subprocesses 2018-04-27 14:02:59 +02:00
Christian Decker 64fbea1528 gossip_store: Save local_add_channel messages and replay them
Signed-off-by: Christian Decker <decker.christian@gmail.com>
2018-04-22 12:50:34 +02:00
Christian Decker 7497f972f1 moveonly: Move handle_local_add_channel to routing.h
Signed-off-by: Christian Decker <decker.christian@gmail.com>
2018-04-22 12:50:34 +02:00
Rusty Russell b0c2e3cd5c gossipd: use a separate CSV file for the gossip_store types.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-04-11 15:58:18 +02:00
Rusty Russell 2b8293c9f6 gossipd: don't use pwrite, better error messaging on init.
Since we open with O_APPEND, any write() will append as we want it to.

But we want to distinguish a new store creation from a truncation due
to bad version.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-04-11 15:58:18 +02:00
Christian Decker 63f22d70b5 gossip: Store channel deletions so we don't re-add them on restart
If we only remember the actions that added channels then we'd restore them when
re-reading the gossip_store, so put a tombstone in there to remember to delete
it. These will be cleared upon re-writing the store since the announcements wont
be written anymore.

Signed-off-by: Christian Decker <decker.christian@gmail.com>
2018-03-30 16:35:00 +02:00
Christian Decker 3826518bd6 gossip: Wrap node_announcements in gossip_store messages
Signed-off-by: Christian Decker <decker.christian@gmail.com>
2018-03-25 23:56:59 +00:00
Christian Decker db13c7e851 gossip: Wrap channel_updates in the gossip_store as well
Bypasses verification when loading from the gossip_store.

Signed-off-by: Christian Decker <decker.christian@gmail.com>
2018-03-25 23:56:59 +00:00
Christian Decker 6e01f38d7d gossip: Use the custom gossip wire msg to wrap channel_announcements
This stores and reads the channel_announcements in the wrapping message which
allows us to store associated data with the raw channel_announcements.

The gossip_store applies channel_announcements directly but it also returns it,
and it gets discarded as a duplicate. In the next commit we'll have gossip_store
apply all changes, bypassing verification, so the duplication is only temporary.

Signed-off-by: Christian Decker <decker.christian@gmail.com>
2018-03-25 23:56:59 +00:00
Christian Decker 5c14f24bb3 gossip: Add gossip_store to the routing_state
Signed-off-by: Christian Decker <decker.christian@gmail.com>
2018-03-25 23:56:59 +00:00
practicalswift d4aadd5e26 tests: Use correct privkey when calculating pubkey used in new_routing_state(...) call 2018-03-25 15:44:05 +02:00
practicalswift 03e2e404f2 Mark unused parameters as such (using "UNUSED") 2018-03-16 01:17:40 +00:00
practicalswift 20ae038080 Remove redundant declaration 2018-03-16 01:17:40 +00:00
Rusty Russell 0a6e3d1e13 utils: remove tal_tmpctx altogether, use global.
In particular, we now only free tmpctx at the end of main().

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-16 00:16:10 +00:00
Rusty Russell 46cc7c281e features: more general accessor functions.
As we add more features, the current code is insufficient.

1. Keep an array of single feature bits, for easy switching on and off.
2. Create feature_offered() which checks for both compulsory and optional
   variants.
3. Invert requires_unsupported_features() and unsupported_features()
   which tend to be double-negative, all_supported_features() and
   features_supported().
4. Move single feature definition from wire/peer_wire.h to common/features.h.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-14 02:19:37 +00:00
Rusty Russell 1290f305a2 gossipd: remove tag.
We only access via index.  We do, however, want to clean up when we
delete nodes and channels, so we tie lifetimes to that.  This leads
us to put the index into 'struct queued_message'.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-14 02:19:37 +00:00
Rusty Russell 882f9f258f gossipd: remove type from broadcast.
It's not necessary now we only access by index.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-14 02:19:37 +00:00
Rusty Russell 8091e0679d gossipd: do all malformdness checks on node_announcement before queueing.
If the channel is pending, we queue the node_announcment and if the channel
is OK we re-call process_node_announcement.  Make sure that second call
won't fail if the first succeeded.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-13 16:34:55 +01:00
Rusty Russell 6d72550707 gossip: send error messages on grossly malformed node_announcement.
As per BOLT #7.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-13 16:34:55 +01:00
Rusty Russell dace9bfdcf gossipd: the great renaming.
We already have 'struct node', so rename 'struct routing_channel' to
'struct chan', and 'struct node_connection' to 'struct half_chan'.

Other minor changes:
1. rstate->channels -> rstate->chanmap.
2. 'connections' -> 'half'.
3. connection_to -> half_chan_to
4. connection_from -> half_chan_from

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-04 23:25:53 +01:00
Rusty Russell 172af04247 gossip: remove short_channel_id from struct node_connection.
It's in the containing routing_channel.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-04 23:25:53 +01:00
Rusty Russell 21b2f37dfb routing: return entire routing_channel array from find_route.
Returning the separate first routing_channel was a weird API: just
return the entire array.  Sure, we have to treat the first node a bit
differently (because we don't charge ourselves fees), but it's still
simpler.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-04 23:25:53 +01:00
Rusty Russell 56349ab008 routing: work with struct routing_channel not struct node_connection.
To remove the redundant fields in `struct node_connection` (ie. 'src'
and 'dst' pointers) we need to deal with `struct routing_channel`.
This means we get a series of channels, from which the direction is
implied, so it's a bit more complex to decode.  We add a helper
`other_node` to help with this, and since we're the only user of
`connection_to` we change that function to return the index.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-04 23:25:53 +01:00
Rusty Russell fd9c0c8543 routing: move struct node_connection into struct routing_channel.
No need to have pointers since they're always there.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-03 19:29:35 +01:00
Rusty Russell 33726b0a08 gossip: instead of refresh interval, have routing know prune_timeout.
This is twice the 'update_channel_interval' we get handed.

We delete the non-existent channel_add_connection and delete_connection
declarations from the header too.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-03 19:29:35 +01:00
Rusty Russell 942d04ba87 gossipd: simplify channel_announce handling.
We make new_routing_channel() populate both connections
(active=false), so local_add_channel becomes simpler.  We also
suppress listchannels output of active=false unannounced channels, to
avoid breaking tests (also, these are unusable, so it makes sense to
omit them)

It also seems the logic in add_channel_direction is legacy: a
channel_announce cannot replace the scid (that would be a different
channel), we don't allow duplicate announcements, and the announcement
is never NULL.

And since we disallow repeated channel_announce already, I believe
'forward' is always true, greatly simplifying the logic in
handle_pending_cannouncement.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-03 19:29:35 +01:00
Rusty Russell 9b900138d0 gossip: put 'routing_channel' in charge of 'node_connection'.
This makes 'routing_channel' the primary object in the system; it can have
one or two 'node_connection's attached, and points to two nodes.

The nodes are freed when no more routing_channel refer to them.  The
routing_channel are freed when they contain no more 'node_connection'.
This fixes #1072 which I surmise was caused by a dangling
routing_channel after pruning.

Each node contains a single array of 'routing_channel's, not one for
each direction.  The 'routing_channel' itself orders nodes in key
order (conveniently the index is equal to the direction flag we use),
and 'node_connection' with source in the same order.

There are helpers to assist with common questions like "which
'node_connection' leads out of this node?".

There are now two ways to find a channel:
1. Direct scid lookup via rstate->channels map.
2. Node key lookup, followed by channel traversal.

Several FIXMEs are inserted for where we can now do things more optimally.

Fixes: #1072
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-03-03 19:29:35 +01:00
ZmnSCPxj 6767434ea9 routing: Use siphash24 for route randomization
Primary idea by @rustyrussell
2018-02-26 02:36:27 +00:00
ZmnSCPxj aff52ce5a8 gossipd: Implement improved randomization of routes.
Fixes: #928
2018-02-26 02:36:27 +00:00
practicalswift 91a9c2923f Mark intentionally unused parameters as such (with "UNUSED") 2018-02-22 01:09:12 +00:00
Rusty Russell e92b710406 tools/generate-wire.py: remove length argument from fromwire_ routines.
We always hand in "NULL" (which means use tal_len on the msg), except
for two places which do that manually for no good reason.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-02-20 22:36:21 +01:00
Rusty Russell 26617d1d64 gossipd/test: update mocks.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-02-14 11:31:58 +01:00
Rusty Russell fd498be7ca status: generate messages rather than marshal/unmarshal manually.
Now we have wirestring, this is much more natural.  And with the
24M length limit, we needn't be so concerned about dumping 64k peer
messages in hex.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-02-08 19:07:12 +01:00
Rusty Russell 84bf60f934 status: add multiple levels of logging.
status_trace maps to status_debug.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2018-02-07 00:46:49 +00:00
Christian Decker 26b5588656 gossip: Use replace_broadcast when enqueuing a channel_announcement
Signed-off-by: Christian Decker <decker.christian@gmail.com>
2018-02-05 18:28:39 +00:00
ZmnSCPxj 67e2275383 gossipd: Add handling of channel_update to routing failures. 2018-02-01 00:46:06 +00:00
ZmnSCPxj b255d82ae2 gossipd: Implement `gossip_routing_failure` for master to report routing failures. 2018-02-01 00:46:06 +00:00
ZmnSCPxj a2877232af gossipd: Check features in `node_announcement` and `channel_announcement`.
Fixes: #548
2018-01-13 11:29:42 +01:00
practicalswift d50fb131b6 Avoid passing uninitialized value dummy with uninitialized field addrlen to {initiator,responder}_handshake_ 2017-12-30 12:28:24 +01:00
Rusty Russell 047a2ea043 gossip: don't use assert around code with side effects.
The use of status_failed() requires a stubs update, which fails
with unnamed parameters, so tweak the status.h header as well.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-12-22 15:47:17 +01:00
Christian Decker 83caf1fdab routing: Add tracking of eviction for broadcasts
We should never be evicting channel_announcements because a) they were
deeply buried and should not change the short_channel_id/tag, b) they
are static.

Signed-off-by: Christian Decker <decker.christian@gmail.com>
2017-12-22 15:47:17 +01:00
Christian Decker 1b28220b64 Revert "broadcast: don't reorder channel_announce when we get the real one."
This reverts commit f293ff0a6a.
2017-12-22 15:47:17 +01:00
Rusty Russell 887e9dcc44 travis: reenable check-source (without BOLT text).
We've been slipping, so fix up minor issues too so it compiles.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-12-21 14:33:27 +01:00
Rusty Russell 810abb6b21 bitcoin: create new wrapper type bitcoin_blkid, log backward endianness.
It's just a sha256_double, but importantly when we convert it to a
string (in type_to_string, which is used in logging) we use
bitcoin_blkid_to_hex() so it's reversed as people expect.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-12-21 11:05:38 +00:00
Rusty Russell f293ff0a6a broadcast: don't reorder channel_announce when we get the real one.
If channel_announce is rebroadcast, it should replace the existing one
in-place.  We currently only do this if we start from the unsigned one
and replace it with the signed one when we hit 6 confirms.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-12-21 09:13:28 +01:00
Rusty Russell bb601a1eeb gossipd/test/run-bench-find_route: don't abort if we try to route to ourselves
This would fail, and we'd free an uninitialized pointer.

Also, add us to .gitignore and clear up a comment.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-12-20 13:57:28 +01:00
Rusty Russell bd27eba6f8 bench: reduce defaults for travis run.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-12-18 22:03:31 +01:00
Rusty Russell a7eee0b669 routing: precalc per-block risk factor.
Saves a little by doing up-front calculation.

# 1M nodes:
$ /gossipd/test/run-bench-find_route 1000000 1 > /tmp/out
=> 42863 msec

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-12-18 22:03:31 +01:00
Rusty Russell 589cb673ce routing: remove negative fee support.
We can't get them; channel_update doesn't support it.

# 1M nodes:
$ /gossipd/test/run-bench-find_route 1000000 1 > /tmp/out
=> 47677 msec

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-12-18 22:03:31 +01:00
Rusty Russell 21cc904b03 gossipd/test/run-bench-find_route.c: add perfme support.
Compile this, and link from perfme-start and perfme-stop in your path:

/* Simple wrapper to allow a program to perf itself. 
 * Copyright Rusty Russell, Blockstream 2015.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * See <http://www.gnu.org/licenses/>.
 */
#include <ccan/err/err.h>
#include <ccan/str/str.h>
#include <sys/types.h>
#include <unistd.h>
#include <signal.h>
#include <errno.h>
#include <stdio.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>

#define PERFME_PREFIX "/tmp/perfme."
#define MAX_ENV_ARGS 20

static void write_noerr(int fd)
{
	int e = errno;
	if (write(fd, "", 1) != 1)
		/* Complain about warn_unused_result fascist bullshit */ ;
	errno = e;
}

/* Child.  Setup pid, run perf. */
static void exec_perf(int pfd[2], const char *perfpid, const char *perfout,
		      pid_t parent)
{
	char pid[STR_MAX_CHARS(pid_t)];
	int i, fd;
	char *cmd, *args[MAX_ENV_ARGS + 5];
	
	fd = open(perfpid, O_CREAT|O_EXCL|O_WRONLY, 0400);
	if (fd < 0) {
		write_noerr(pfd[1]);
		err(1, "opening %s", perfpid);
	}

	sprintf(pid, "%u", getpid());
	if (write(fd, pid, strlen(pid)) != strlen(pid)) {
		write_noerr(pfd[1]);
		err(1, "writing to %s", perfpid);
	}
	close(fd);

	sprintf(pid, "%u", parent);
	cmd = getenv("PERFME");
	if (!cmd)
		cmd = "perf record --call-graph dwarf -q";
	cmd = strdup(cmd);
	for (i = 0; i < MAX_ENV_ARGS; i++) {
		args[i] = strtok(i == 0 ? cmd : NULL, " ");
		if (!args[i])
			break;
	}
	if (i == 0 || i == MAX_ENV_ARGS)
		errx(1, "Too %s args in $PERFME: '%s'",
		     i ? "many" : "few", getenv("PERFME"));

	args[i++] = "-p";
	args[i++] = pid;
	args[i++] = "-o";
	args[i++] = (char *)perfout;
	args[i++] = NULL;

	execvp(args[0], args);
	write_noerr(pfd[1]);
	err(1, "Execing %s", args[0]);
}

int main(int argc, char *argv[])
{
	pid_t parent = argv[1] ? atoi(argv[1]) : getppid();
	char perfout[sizeof(PERFME_PREFIX) + STR_MAX_CHARS(parent)];	
	char perfpid[sizeof(perfout) + sizeof(".pid")];

	err_set_progname(argv[0]);

	sprintf(perfpid, PERFME_PREFIX "%u.pid", parent);
	if (strends(argv[0], "perfme-stop")) {
		char pid[STR_MAX_CHARS(pid_t)];
		int r, fd = open(perfpid, O_RDONLY);
		if (fd < 0)
			err(1, "Opening %s", perfpid);
		r = read(fd, pid, sizeof(pid) - 1);
		if (r < 0)
			err(1, "Reading %s", perfpid);
		pid[r] = 0;
		if (unlink(perfpid) != 0)
			warn("Unlinking %s", perfpid);
		if (atoi(pid) <= 0)
			errx(1, "Invalid pid '%s' from %s", pid, perfpid);
		if (kill(atoi(pid), SIGTERM) != 0)
			err(1, "Stopping %s", pid);
		exit(0);
	} else if (strends(argv[0], "perfme-start")) {
		int pfd[2];

		sprintf(perfout, PERFME_PREFIX "%u", parent);

		/* Use pipe to detect successful exec. */
		if (pipe(pfd) != 0)
			err(1, "Creating pipe");
		
		switch (fork()) {
		case 0:
			close(pfd[0]);
			fcntl(pfd[1], F_SETFD,
			      fcntl(pfd[1], F_GETFD)|FD_CLOEXEC);

			exec_perf(pfd, perfpid, perfout, parent);
		case -1:
			err(1, "Forking");
		default:
			/* Parent.  Wait for child. */
			close(pfd[1]);
			if (read(pfd[0], perfpid, 1) == 1)
				exit(1);
			fprintf(stderr, "Perf recording into %s\n", perfout);
			sleep(1);
			exit(0);
		}
	}
	errx(1, "Unknown name: am I perfme-start or perfme-stop?");
}

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-12-18 22:03:31 +01:00
Rusty Russell 4a54884d4b gossipd: routing benchmark.
Initial run (100,000 nodes):

$ ./gossipd/test/run-bench-find_route 100000 1 > /tmp/out
=> 15646 msec

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-12-18 22:03:31 +01:00
Christian Decker 19c030ea1f routing: Make routing_state aware of its own ID
This is used to identify our own announcements.

Signed-off-by: Christian Decker <decker.christian@gmail.com>
2017-12-17 02:44:20 +00:00
Rusty Russell 40315bfb91 test: fix dependencies.
Test objects must be added to $(ALL_OBJS) so they correctly depend on
CCAN headers etc.

Also, each test in a subdir must depend on headers and src in the parent
directory, as it will often #include them directly.

Reported-by: Christian Decker
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-11-22 19:40:46 +01:00
Rusty Russell 78cd25d620 ipaddr: rename to wireaddr.
In future it will have TOR support, so the name will be awkward.

We collect the to/fromwire functions in common/wireaddr.c, and the
parsing functions in lightningd/netaddress.c.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-10-26 21:01:09 +00:00
Rusty Russell 33bfc2326a gossipd: pass addr of peer though handshake.
We need to derive this from the fd when they connect in, but we already
know it if we're connecting out.

We want this so we can tell (in next few patches) master the peer's address.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-10-26 21:01:09 +00:00
Rusty Russell 7e022b522c gossipd: don't try to handle padding inside fromwire_ipaddr.
It makes it impossible to embed an ipaddr in another structure, since we
always try to skip over any zeroes, which may swallow a following field.

Do the skip specially for the case where we're parsing routing messages:
we never use padding for our own internal messages anyway.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-10-24 16:12:22 +02:00
Rusty Russell a88ac22711 gossipd: include ccan/io version of handshake code, with tests.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-10-20 18:31:32 +02:00
Rusty Russell ee9e300da0 gossip: fix address descriptor handling.
1. The code to skip over padding didn't take into account max.
2. It also didn't use symbolic names.
3. We are not supposed to fail on unknown addresses, just stop parsing.
4. We don't use the read_ip/write_ip code, so get rid of it.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-09-03 02:01:54 +02:00
Rusty Russell 6933db04b5 gossipd/routing: remove/static unused functions.
I missed these when I removed the legacy daemon.  We also remove the
min_blocks field which was always 0.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-09-03 02:01:54 +02:00
Rusty Russell 9c35603275 gossipd/routing: free everything at end of tests.
valgrind complains, but using a destructor on the node map is a good
idea anyway.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-09-03 02:01:54 +02:00
Rusty Russell ffaab09043 gossipd/test: fix flaky test.
The test is could actually go each way, since for 1000000 the fee is
the same either way.

Increase to 300000, and add an extra test when the alternate path
is disabled.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-09-03 02:01:54 +02:00
Rusty Russell c8aa50a382 gossipd: fix routing issue.
I had a routing problem, and wrote a simple unit test which passed.  So
I wrote one which copied the failure case (and importantly, had a non-1
fee factor), which triggerd it.

In that real example, we underflowed which resulted in us not finding
a route.  Simply don't consider routes which are infinite.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
2017-09-03 02:01:54 +02:00