Include all channel route hints if no connected channels exist

Mobile clients often take a second or two before they reconnect to
their peers as its not always clear immediately that connections
have been killed (especially on iOS). This can cause us to
spuriously fail to include route hints in our invoices if we're on
mobile.

The fix is simple, if we're selecting channels to include in route
hints and we're not not connected to the peer for any of our
channels, we should simply include the hints for all channels, even
though we're disconencted.

Fixes #1768.

Merge pull request #1754 from TheBlueMatt/2022-10-better-liq-halflife-docs

Rewrite some documentation on `ProbabilisticScorer` and increase half-life to 6 hours.

Increase the default `liquidity_offset_half_life` to six hours

Even at relatively high payment volumes, decaying knowledge of each
individual channel every hour causes aggressive retrying of
channels as we quickly forget the state of a channel. Even with the
historical tracker, this isn't fully remedied, as we'll track the
history bounds with the decayed value.

Instead, we decay every six hours here, reducing how often we'll
retry a channel due to decay.

In addition to this, the decay likely needs to be substantially
more linear, as tracked in #1752.

Rewrite documentation some on `ProbabilisticScorer`

We had some user confusion on how the probabilistic scorer works,
especially in reference to the half-life parameter. This attempts
to clarify how the bounds work, and how they are decayed.

Merge pull request #1744 from tnull/2022-09-fix-bp-futures-doc

Fix `background-processor` doc build for `futures`

Add `futures` CI check

This adds testing of the `futures` feature to CI. In order to avoid
introducing a dependency on `std`, we switch to using the `futures-util`
crate directly enabling only a subset of features. To this end, we also
switch to using the `select_biased!` macro, which is equivalent to
`select!` except that it doesn't choose ready futures pseudo-randomly
at runtime.

Fix `background-processor` doc build for `futures`

Merge pull request #1756 from TheBlueMatt/2022-10-rgs-no-std

Fix `rapid-gossip-sync` `no-std` and properly test no-std in CI

Merge pull request #1649 from dunxen/2022-08-implementnodefailure

Implement permanent node failure handling

Merge pull request #1693 from valentinewallace/2022-09-readme-updates

Fix outdated README sections

Merge pull request #1758 from TheBlueMatt/2022-10-fix-pre-notified-future

Fix (and test) `Future` creation after a `Notifier` was notified

Test a full `no-std` build in the `no-std-check` crate in CI

Rust is incredibly forgiving in attempts to access `std`, making it
rather difficult to test `no-std` properly. In practice, the only
decent way to do so is to actually build for a platform that does
not have `std`, which we do here by building the `no-std-check`
crate for `arm-thumbv7m-none-eabi`.

Merge pull request #1625 from TheBlueMatt/2022-07-history-tracking

Merge pull request #1751 from TheBlueMatt/2022-10-fix-score-log-direction

Correct the directionality of liquidity non-update messages

Merge pull request #1760 from TheBlueMatt/2022-10-invoice-builder-round

Fix outdated README sections

Remove and track perm failed nodes & channels

We never had the `NetworkGraph::node_failed` method implemented. The
scorer now handles non-permanent failures by downgrading nodes, so we
don't want that implemented.

The method is renamed to `node_failed_permanent` to explicitly indicate
that this is the only case it handles. We also add tracking in the form
of two maps as fields of `NetworkGraph`, namely, `removed_nodes` and
`removed_channels`. We track these removed graph entries to ensure we
don't just resync them right away from gossip soon after removing them.
We stop tracking these removed nodes whenever `remove_stale_channels_and_tracking()`
is called and the entries have been tracked for longer than
`REMOVED_ENTRIES_TRACKING_AGE_LIMIT_SECS` which is currently set to one
week.

Drop the subsecond part of timestamps when constructing invoices

We had a user who was confused why an invoice failed to round-trip
(i.e. was not `PartialEq` with itself after write/read) when a
subsecond creation time was used (e.g. via the `from_system_time`
constructor).

This commit should address this confusion by dropping subsecond
parts in easily-accessible constructors when creating BOLT 11
invoices.

Fixes #1759.

Support platforms with only 32-bit atomics

Given there is only one instance in our code of `AtomicU64` its
simplest to just remove it rather than try to add some kind of
wrapper.

Test `rapid-gossip-sync` in `no-std` in CI

Update `rapid-gossip-sync` docs to not reference `std`-only methods

Fix (and test) `Future` creation after a `Notifier` was notified

After a `Notifier` has been `notify`'d, attempts to `get_future`
should return a `Future` which is pre-completed, however this was
not the case.

This commit simply fixes the behavior, adding a test to demonstrate
the issue.

Decay historical liquidity tracking when no new data is added

To avoid scoring based on incredibly old historical liquidity data,
we add a new half-life here which is used to (very slowly) decay
historical liquidity tracking buckets.

Track a reference to scoring parameters in DirectedChannelLiquidity

This simplifies adding additional half lives in
DirectedChannelLiquidity by simply storing a reference to the full
parameter set rather than only the single current half-life.

Calculate a new penalty based on historical channel liquidity range

Our current `ProbabilisticScorer` attempts to build a model of the
current liquidity across the payment channel network. This works
fine to ignore channels we *just* tried to pay through, but it
fails to remember patterns over longer time horizons.

Specifically, there are *many* channels within the network that are
very often either fully saturated in one direction, or are
regularly rebalanced and rarely saturated. While our model may
discover that, when it decays its offsets or if there is a
temporary change in liquidity, it effectively forgets the "normal"
state of the channel.

This causes substantially suboptimal routing in practice, and
avoiding discarding older knowledge when new datapoints come in is
a potential solution to this.

Here, we implement one such design, using the decaying buckets
added in the previous commit to calculate a probability of payment
success based on a weighted average of recent liquidity estimates
for a channel.

For each min/max liquidity bucket pair (where the min liquidity is
less than the max liquidity), we can calculate the probability that
a payment succeeds using our traditional `amount / capacity`
formula. From there, we weigh the probability by the number of
points in each bucket pair, calculating a total probability for the
payment, and assigning a penalty using the same log-probability
calculation used for the non-historical penalties.

Track history of where channel liquidities have been in the past

This introduces two new fields to the `ChannelLiquidity` struct -
`min_liquidity_offset_history` and `max_liquidity_offset_history`,
both an array of 8 `u16`s. Each entry represents the proportion of
time that we spent with the min or max liquidity offset in the
given 1/8th of the channel's liquidity range. ie the first bucket
in `min_liquidity_offset_history` represents the proportion of time
we've thought the channel's minimum liquidity is lower than 1/8th's
the channel's capacity.

Each bucket is stored, effectively, as a fixed-point number with
5 bits for the fractional part, which is incremented by one (ie 32)
each time we update our liquidity estimates and decide our
estimates are in that bucket. We then decay each bucket by
2047/2048.

Thus, memory of a payment sticks around for more than 8,000
data points, though the majority of that memory decays after 1,387
data points.

Correct the directionality of liquidity non-update messages

When we log liquidity updates, if we decline to update anything as
the new bounds are already within the old bounds, the
directionality of the log entries was reversed.

While we're at it, we also log the old values.

Correct `rapid-gossip-sync` `no-std` build and test

While `rapid-gossip-sync` recently gained a `no-std` feature, it
didn't actually work, as there were still dangling references to
`std` and prelude assumptions. This makes `rapid-gossip-sync`
build (and test) properly in `no-std`.

Merge pull request #1106 from TheBlueMatt/2021-10-no-perm-err-broadcast

Do not broadcast commitment txn on Permanent mon update failure

Clarify ambiguous comment in persist methods

Rename APIError::MonitorUpdateFailed to MonitorUpdateInProgress

This much more accurately represents the error, indicating that a
monitor update is in progress asynchronously and may complete at a
later time.

Rename `handle_monitor_err!()` `handle_monitor_update_res!`

Rename `Channel::monitor_update_failed` to `monitor_updating_paused`

Add a TODO for an important issue for making async mon updates safe

If we receive a monitor event from a forwarded-to channel which
contains a preimage for an HTLC, we have to propogate that preimage
back to the forwarded-from channel monitor. However, once we have
that update, we're running in a relatively unsafe state - we have
the preimage in memory, but if we were to crash the forwarded-to
channel monitor will not regenerate the update with the preimage
for us. If we haven't managed to write the monitor update to the
forwarded-from channel by that point, we've lost the preimage, and,
thus, money!

Rework `chain::Watch` return types to make async updates less scary

When a `chain::Watch` `ChannelMonitor` update method is called, the
user has three options:
 (a) persist the monitor update immediately and return success,
 (b) fail to persist the monitor update immediately and return
     failure,
 (c) return a flag indicating the monitor update is in progress and
     will complete in the future.

(c) is rather harmless, and in some deployments should be expected
to be the return value for all monitor update calls, but currently
requires returning `Err(ChannelMonitorUpdateErr::TemporaryFailure)`
which isn't very descriptive and sounds scarier than it is.

Instead, here, we change the return type used to be a single enum
(rather than a Result) and rename `TemporaryFailure`
`UpdateInProgress`.

Merge pull request #1740 from TheBlueMatt/2022-09-invoice-bindings-nostd

Don't make references to `std` in `lightning-invoice` in bindings

Merge pull request #1742 from tnull/2022-09-remove-done-todo

Remove completed TODO

Don't make references to `std` in `lightning-invoice` in bindings

As we support `no-std` for `lightning-invoice` builds, we should
support them in `c_bindings` as well, which we add a test for in
CI here.

Remove done TODO

The migration to `LockTime` was already done in
7e05623befc111422d1d4230f4e51629566a2ae6, which however did not also
remove the TODO.

Merge pull request #1737 from TheBlueMatt/2022-09-future-trait

Add a bindings-only version of `Future::register_callback`

Add a bindings-only version of `Future::register_callback`

While we could, in theory, add support to the bindings logic to map
`Box<dyn Trait>`, there isn't a whole lot of use doing so when its
incredibly trivial to do directly.

This adds a trivial wrapper around `Future::register_callback` that
is only built in bindings and which is linked in the
`register_callback` docs for visibility.

Merge pull request #1734 from TheBlueMatt/2022-09-better-lock-name

Rename `MultiThreadedLockableScoreLock` `MultiThreadedScoreLock`

Rename `MultiThreadedLockableScoreLock` to `MultiThreadedScoreLock`

as the first is quite a mouthful, and the second isn't materially
less specific.

Merge pull request #1733 from TheBlueMatt/2022-09-downgrade-hashbrown

Downgrade `hashbrown` to meet MSRV

Merge pull request #1731 from valentinewallace/2022-09-router-test-utils-mod

Move router test utils into their own module

Downgrade `hashbrown` to meet MSRV

`hashbrown` depends on `ahash` which depends on `once_cell`. Sadly,
in https://github.com/matklad/once_cell/issues/201 the `once_cell`
maintainer decided they didn't want to do the work of having an
MSRV policy for `once_cell`, making `ahash`, and thus `hashbrown`
require the latest compiler. I've reached out to `ahash` to suggest
they drop the dependency (as they could trivially work around not
having it), but until then we simply downgrade `hashbrown`.

`rust-bitcoin` also requires an older `hashbrown` so we're actually
reducing our total `no-std` code here anyway.

Import util::test_utils as ::ln_test_utils in router

To disambiguate between util::test_utils and router::test_utils

Rename routing::router::test_utils to ::bench_utils

To disambiguate it from routing::test_utils

Merge pull request #1656 from ViktorTigerstrom/2022-08-forward-htlcs-as-standalone-lock

Move `forward_htlcs` into standalone lock

Move router test utils into their own module

Useful for testing onion message pathfinding in upcoming PRs and any future
routing modules we add

Add lock order docs to `ChannelManager` fields

Merge pull request #1729 from TheBlueMatt/2022-09-lockablescore-bindings

Add a `MutexGuard` wrapper for the bindings-only `LockableScore`

Merge pull request #1728 from TheBlueMatt/2022-09-slices-not-vecs

Swap `Vec<&RouteHop>` parameters for slices

Avoid returning a reference to a u64.

In c353c3ed7c40e689a3b9fb6730c6dabbd3c92cc5 an accessor method was
added which returns an `Option<&u64>`. While this allows Rust to
return an 8-byte object, returning a reference to something
pointer-sized is a somewhat strange API.

Instead, we opt for a straight `Option<u64>`, which is sadly
somewhat larger on the stack, but is simpler and already supported
in the bindings generation.

Swap `Vec<&RouteHop>` parameters for slices

In c353c3ed7c40e689a3b9fb6730c6dabbd3c92cc5, new scorer-updating
methods were added to the `Router` object, however they were
passed as a `Vec` of references. We use the list-of-references
pattern to make bindings simpler (by not requiring allocations per
entry), however there's no reason prefer to passing a `Vec` over
a slice, given the `Vec` doesn't hold ownership of the objects
anyway.

Add a `MutexGuard` wrapper for the bindings-only `LockableScore`

In the bindings, we don't directly export any `std` types. Instead,
we provide trivial wrappers around them which expose only a
bindings-compatible API (and which is code in-crate, where the
bindings generator can see it).

We never quite finished this for `MultiThreadedLockableScore` - due
to some limitations in the bindings generator and the way the
scores are used in `lightning-invoice`, the scoring API ended up
being further concretized in patches for the bindings. Luckily the
scoring interface has been rewritten somewhat, and it so happens
that we can now generate bindings with the upstream code.

The final piece of the puzzle is done here, where we add a struct
which wraps `MutexGuard` so that we can expose the lock for
`MultiThreadedLockableScore`.

Remove `forward_htlc` after `channel_state` lock order

The `forward_htlc` was prior to this commit only held at the same time
as the `channel_state` lock during the write process of the
`ChannelManager`. This commit removes the lock order dependency, by
taking the `channel_state`lock temporarily during the write process.

Remove unnecessary aquiring of the `channel_state` lock

Move `forward_htlcs` into standalone lock

As we are eventually removing the `channel_state` lock, this commit
moves the `forward_htlcs` map out of the `channel_state` lock, to ease
that process.

Merge pull request #1725 from TheBlueMatt/2022-09-no-bench-lockorder

Stop building with lockorder debugging in benchmarks

Merge pull request #1694 from jurvis/jurvis/2022-08-move-scorer-from-router

Move `LockableScore` requirement away from `Router` trait

Move Scorer requirement away from Router trait

We do this to enable users to create routers that do not need a scorer.
This can be useful if they are running a node the delegates pathfinding.

* Move `Score` type parameterization from `InvoicePayer` and `Router` to
`DefaultRouter`
* Adds a new field, `scorer`, to `DefaultRouter`
* Move `AccountsForInFlightHtlcs` to `DefaultRouter`, which we
will use to wrap the new `scorer` field, so scoring only happens in
`DefaultRouter` explicitly.
* Add scoring related functions to `Router` trait that we used to call
directly from `InvoicePayer`.
* Instead of parameterizing `scorer` in `find_route`, we replace it with
inflight_map so `InvoicePayer` can pass on information about inflight
HTLCs to the router.
* Introduced a new tuple struct, InFlightHtlcs, that wraps functionality
for querying used liquidity.

Stop building with lockorder debugging in benchmarks

`cargo bench` sets `#[cfg(test)]` so our current checks for
enabling our lockorder debugging end up matching when we're trying
to build performance benchmarks.

This adds explicit checks to our debug_lockorder logic to filter
out `feature = "_bench_unstable"` builds.

Do not broadcast commitment txn on Permanent mon update failure

See doc updates for more info on the edge case this prevents, and
there isn't really a strong reason why we would need to broadcast
the latest state immediately. Specifically, in the case of HTLC
claims (the most important reason to ensure we have state on chain
if it cannot be persisted), we will still force-close if there are
HTLCs which need claiming and are going to expire.

Surprisingly, there were no tests which failed as a result of this
change, but a new one has been added.

Merge pull request #1708 from tnull/2022-09-rgs-unpub-modules

Improve RGS documentation

Add `no-std` support for RGS

Rework RGS crate-level docs

Merge pull request #1707 from TheBlueMatt/2022-09-no-global-features

Move supported-feature-set logic into the supporting modules

Assert that all defined features are in the known features set

Now that the features contexts track the full set of all known
features, rather than the set of supported features, all defined
features should be listed in the context definition macro.

This adds a compile-time assertion to check that all bits for known
features are set in the context known set.

Stop tracking feature bits as known or required in features.rs

Now that the `*Features::known` constructor has been removed, there
is no reason to define feature bits as either optional required in
`features.rs` - that logic now belongs in the modules that are
responsible for the given features.

Instead, we only list all features in each context.

Remove the `*Features::known` constructor

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we (finally) remove the `known` constructor entirely,
modifying tests in the `features` module as required.

Remove all remaining references to `*Features::known`

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

In anticipation of removing the `known` constructor, this commit
removes all remaining references to it outside of features.rs.

Stop relying on `*Features::known` in fuzzing tests

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in our fuzz tests.

Stop relying on `*Features::known` in BP and persister tests

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the
`lightning-background-processor` and `lightning-persister` crate
tests.

Stop relying on the `*Features::known` method in net-tokio

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the
`lightning-net-tokio` crate.

Stop relying on the `*Features::known` method in lightning-invoice

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the
`lightning-invoice` crate.

Stop relying on `*Features::known` in channel{,manager}.rs

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the channel modules.

Stop relying on `*Features::known` in functional test utils

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the
functional_test_utils module.

Stop relying on the `*Features::known` method in functional tests

This diff is commit, like the last, stops relying on the `known`
feature set constructor, doing so entirely with import changes and
sed rules.

Stop relying on the `*Features::known` method in `routing` tests

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the `routing` module,
which was only used in tests.

List supported/required feature bits explicitly in ChannelManager

Historically, LDK has considered the "set of known/supported
feature bits" to be an LDK-level thing. Increasingly this doesn't
make sense - different message handlers may provide or require
different feature sets.

In a previous PR, we began the process of transitioning with
feature bits sent to peers being sourced from the attached message
handler.

This commit makes further progress by moving the concept of which
feature bits are supported by our ChannelManager into
channelmanager.rs itself, via the new `provided_*_features`
methods, rather than in features.rs via the `known_channel_features`
and `known` methods.

Merge pull request #1721 from acid-bit/fix_typo

Fix typo in comment in Cargo.toml

Merge pull request #1720 from TheBlueMatt/2022-09-fix-fuzz-warnings

Fix compile-time warnings in fuzzing

Fix typo in comment in Cargo.toml

Fix warnings in fuzz which should have been fixed in f725c5a90a11e6

Fix compile warning in fuzzing introduced in cd0d19c005ee4fa11de93a

Merge pull request #1685 from wpaulino/anchors-prep

Merge pull request #1717 from TheBlueMatt/2022-09-req-features-in-handlers

Move checking of specific require peer feature bits to handlers

Merge pull request #1706 from jkczyz/2022-09-filtered-blocks

Support filtered blocks in `lightning-block-sync`

Update anchors test vectors to zero HTLC transaction fee variant

Each test featuring HTLCs had a minimum and maximum feerate case. This
is no longer necessary for the zero HTLC transaction anchors variant as
the commitment feerate does not impact whether HTLCs can be trimmed or
not, only the dust limit does.

Account for zero fee HTLC transaction within dust limit calculation

With the zero fee HTLC transaction anchors variant, HTLCs can no longer
be trimmed due to their amount being too low to have a mempool valid
HTLC transaction. Now they can only be trimmed based on the dust limit
of each party within the channel.

Update HTLC script detection to check for anchor output variants

Use zero fee HTLC transactions for anchor channels

This is based on the assumption that we only support the zero HTLC
transaction fee variant of anchor channels.

Exclude HTLC transactions from broadcast on anchor channels

HTLC transactions from anchor channels are constrained by a CSV of 1
block, so broadcasting them along with the unconfirmed commitment
tranasction will result in them being immediately rejected as premature.

Avoid commitment broadcast upon detected funding spend

There's no need to broadcast our local commitment transaction if we've
already seen a confirmed one as it'll be immediately rejected as a
duplicate/conflict.

This will also help prevent dispatching spurious events for bumping
commitment and HTLC transactions through anchor outputs (once
implemented in future work) and the dispatch for said events follows the
same flow as our usual commitment broadcast.

Use proper sighash flag for remote HTLCs with anchor outputs

Support filtered blocks in lightning-block-sync

Expand the BlockSource trait to allow filtered blocks now that
chain::Listen supports them (d629a7edb7241eee7fde9f5ccdf1c481d2d6297b).
This makes it possible to use BIP 157/158 compact block filters with
lightning-block-sync.

Merge pull request #1703 from TheBlueMatt/2022-09-badonion-first-check

Correctly handle BADONION onion errors

Add now-missing `unwrap`s on test calls to `peer_connected`.

Move checking of specific require peer feature bits to handlers

As we remove the concept of a global "known/supported" feature set
in LDK, we should also remove the concept of a global "required"
feature set. This does so by moving the checks for specific
required features into handlers.

Specifically, it allows the handler `peer_connected` method to
return an `Err` if the peer should be disconnected. Only one such
required feature bit is currently set - `static_remote_key`, which
is required in `ChannelManager`.