Draft NEON that might work

SIMD 4x interleaved loop w/ floats

2x interleave non-FP loop

split loops on linear success

(prob) f use new simd impl wrappers

max simd

simd the success prob

Add impl of SIMD'd f32s

use f32s

Inline point count divide

Avoid excess multiplies by multiplying in `success_probability`

A substantial portion (~12%!) of our scoring time is spent dividing
the bucket pair probability by the `success_probability` divisor.

Here, we avoid this by multiplying the bucket pair probability
in floating point math and using a floating point divide (which can
be faster in some cases). This also avoids the 2^30 multiplies that
are used to avoid rounding errors when converting the float
numerator and denominator to ints.

Move in-inner-scoring-loop if out to the top level

When scoring channels, walking the historical buckets ends up being
the vast majority of our time. While LLVM is smart enough to pull
some conditionals out of the inner loop, we shouldn't make LLVM do
the work, and avoiding it can let us optimize the algorithm
somewhat in the coming commits.

Force inlining source and target node id lookup in candidate hops

Because our router is rather large, LLVM doesn't always decide to
inline small functions in it, opting instead for a call. This is
somewhat wasteful when we do repeated `match`es on the same data,
so here we force inlining of the `source` and `target` `NodeId`
lookups.

Prefetch per-direction channel info before looking at the channel

In the previous commit, we laid out `ChannelInfo` to ensure most of
the data we cared about was sitting on two adjacent cache lines.
However, this left off the per-direction `ChannelUpdateInfo`, which
is sitting elsewhere.

Here, we try to reduce the cost we pay for accessing those when we
call `ChannelInfo::as_directed` by prefetching them as soon as we
fetch the `ChannelInfo` from the per-channel `HashMap`. We then
check the features for unknown flags, giving the CPU a handful of
instructions to chew on before we actually need the
`ChannelUpdateInfo`.

Sadly, this currently requires unsafe Rust (and is currently only
available on stable for x86), even though the x86 ISA is explicit
that the instruction "does not affect program behavior". Still,
this optimization reduces time taken waiting for the
`ChannelUpdateInfo` to load from ~5% of our routefinding time to
~2.5%, for a net reduction of ~2.5% in routefinding time.

Manually lay out scorer memory

Cache the total points tracked in our historical liquidity data

When we go to score a channel using the historical liquidity data,
the first thing we do is step through all the valid bucket
combinations, multiply the min and max bucket, and then add them
together to calculate the total number of points tracked. This
isn't a free operation, and for scorers without much data it
represents a large part of the total time spent scoring during
routefinding.

Thus, here we cache this value, updating it every time the buckets
are updated.

Change the directed history tracker's storage of its direction

Rather than storing the two direction's buckets in
`HistoricalMinMaxBuckets` (renamed
`DirectedHistoricalLiquidityTracker`), we store a single reference
to the `HistoricalLiquidityTracker` as well as the direction bool.

This will allow us in the next commit to reference fields in the
`HistoricalLiquidityTracker` aside from the two directions.

Make the historical bucket data private to `bucketed_history`

In a comming commit we'll cache some additional data in the
historical bucket tracker. In order to do so, here we isolate the
buckets themselves into the `bucketed_history` module, reducing
the possibility of accidentally updating them directly without
updating caches.

Store both min and max historical buckets in one, new, struct

In the coming commits we'll isolate historical bucket logic slightly
further, allowing us to cache some state. This is the first step
towards that, storing the historical liquidity information in a new
`HistoricalLiquidityTracker` rather than in the general
`ChannelLiquidity`.

Move log approximation from `scoring.rs` to its own file

Merge pull request #2803 from TheBlueMatt/2023-12-routing-dist-vec

Misc routing optimization

Merge pull request #3087 from shaavan/reply_path_diversity

Allow blinded path diversification by expanding `create_blinded_paths`

Merge pull request #3185 from tnull/2024-07-clarify-max-description-length

Clarify maximum length of an invoice description

Merge pull request #3183 from TheBlueMatt/2024-07-no-strict

Drop unnecessary `strict` feature from `lightning-invoice`

Merge pull request #3150 from alecchendev/2024-06-async-commit-point-raa

Handle fallible per commitment point for RAA

Clarify maximum length of an invoice description

We previously stated in the docs that the invoice description can be at most `1023`
bytes long, which is wrong. According to BOLT 11 it's at most 1023*5 bits (639 bytes) long.

Test async get per commitment point for revoke_and_ack

Note: this does not test the CS -> RAA resend ordering, because this
requires handling async get_per_commitment_point for channel
reestablishment, which will be addressed in a follow up PR.

Allow failing revoke_and_ack if commitment point is not available

Change get_per_commitment_point to return result type

Includes simple changes to test util signers and tests, as well as
handling the error case for get_per_commitment_point in
HolderCommitmentPoint. This leaves a couple `.expect`s in places
that will be addressed in a separate PR for handling funding.

Merge pull request #3165 from Harshit933/link-fix

Fixes `Sensei` broken link

Add logger as parameter in creating ChannelContext

Return an error if we fail to advance our commitment number

Drop unnecessary `strict` feature from `lightning-invoice`

99aa6e27f616c96dda2b49d09bafbc0b982251e0 detected that we had an
undefined feature in `lightning-invoice` called `strict`, which was
used to turn on `deny(warnings)`. It resolved that by adding the
feature to the `Cargo.toml`, but we actually don't need it - our CI
already builds with `-Dwarnings`, so any warnings should be
rejected during CI and there's not a lot of value in having a
(public) feature to do the same.

Merge pull request #3173 from dunxen/2024-07-cargocheckcfg

Use native check-cfg lint in cargo beta

Split HolderCommitmentPoint::advance off into separate function

Merge pull request #3180 from tnull/2024-07-use-upstreamed-merkle-validation

Electrum: Use upstreamed `validate_merkle_proof`

Merge pull request #3172 from tnull/2024-07-revert-gossip-query-patch

Revert "Signal `GossipQuery` support when using `IgnoringMessagHandler`"

Use upstreamed `validate_merkle_proof`

We previously upstreamed the `validate_merkle_proof` utility method,
which shipped with `electrum-client` 0.19.0.

Since we upgraded to that version recently, we can now drop our local
code and use the upstreamed version.

Merge pull request #3138 from tnull/2024-06-rustfmt-bp

`rustfmt`: Run on `lightning-background-processor`

Introduce tests to check verify reply path diversification

Fixes `Sensei` broken link

Issue: https://github.com/lightningdevkit/rust-lightning/issues/3148

Use native check-cfg lint in cargo beta

This uses the newly introduced conditional configuration checks that are
now configurable withint Cargo (beta).

This allows us to get rid of our custom python script that checks for
expected features and cfgs.

This does introduce a warning regarding the unknown lint in Cargo
versions prior to the current beta, but since these are not rustc errors,
they won't break any builds with the "-D warnings" RUSTFLAG.

Moving to this lint actually exposed the "strict" feature not being
present in the lightning-invoice crate, as our python script didnt
correctly parse the cfg_attr where it appeared.

Revert "Signal `GossipQuery` support when using `IgnoringMessagHandler`"

This reverts commit 843079df72435b8a117e8b12b42492391409259f.

Update extract_invoice to also return the reply_path.

- This will be utilised in the following commit for a test.

Expand `create_blinded_path` Functionality for Enhanced Path Diversification

- Previously, the `create_blinded_path` function was limited to
  returning a single `BlindedPath`, which restricted the usage of
  `blinded_paths`.
- This commit extends the `create_blinded_path` function to return
  the entire blinded path vector generated by the `MessageRouter`'s
  `create_blinded_paths`.
- The updated functionality is integrated across the codebase, enabling
  the sending of Offers Response messages, such as `InvoiceRequest`
  (in `pay_for_offer`) and `Invoice` (in `request_refund_payment`),
  utilizing multiple reply paths.

Layout channel info to ensure routing uses cache lines well

Because we scan per-channel information in the hot inner loop of
our routefinding immediately after looking a channel up in a
`HashMap`, we end up spending a nontrivial portion of our
routefinding time waiting on memory to be read in.

While there is only so much we can do about that, ensuring the
channel information that we care about is sitting on one or
adjacent cache lines avoids paying that penalty twice. Thus, here
we manually lay out `ChannelInfo` and `ChannelUpdateInfo` and set
them to 128b and 32b alignment, respectively. This wastes some
space in memory in our network graph, but improves routing
performance in return.

Consolidate `candidate` access in `add_entry` during routing

Because fetching fields from the `$candidate` often implies an
indirect read, grouping them together may result in one or two
fewer memory loads, so we do so here.

Somewhat optimize the generic `Features::requires_unknown_bits`

It turns out we spend several percent of our routefinding time just
checking if nodes and channels require unknown features
byte-by-byte. While the cost is almost certainly dominated by the
memory read latency, avoiding doing the checks byte-by-byte should
reduce the branch count slightly, which may reduce the overhead.

Store source/target `node_counter`s in `DirectionalChannelInfo`

Because we now have some slack space in `PathBuildingHop`, we can
use it to cache some additional hot values. Here we use it to
cache the source and target `node_counter`s for public channels,
effectively prefetching the values from the channel state.

DRY redundant calls to `$candidate.htlc_minimum_msat()` in routing

While LLVM should inline and elide the redundant calls, because the
router is rather large LLVM can decide against inlining in some
cases where it would be an nice win.

Thus, its worth DRY'ing the redundant calls explicitly.

Cache whether a node is a first-hop target in the per-node state

When processing the main loop during routefinding, for each node,
we check whether it happens to be our peer in one of our channels.
This ensures we never fail to find a route that takes a hop through
a private channel of ours, to a private node, then through
invoice-provided route hints to reach the ultimate payee.

Because this is incredibly hot code, doing a full `HashMap` lookup
to check if each node is a first-hop target ends up eating a good
chunk of time during routing. Luckily, we can trivially avoid this
cost.

Because we're already looking up the per-node state in the `dist`
map, we can store a bool in each first-hop target's state, avoiding
the lookup unless we know its going to succeed.

This requires storing a dummy entry in `dist`, which feels somewhat
strange, but is ultimately fine as we should never be looking at
per-node state unless we've already found a path to that node,
updating the fields in doign so.

Merge pull request #3104 from TheBlueMatt/2024-06-routing-counters

Move blinded path introduction point resolution to a helper method

This marginally reduces the size of `get_route` by moving a the
blinded path introduction point resolution and blinded path checks
into a helper method.

Align `PathBuildingHop` to 128b, now that we store them in a `Vec`

Now that `PathBuildingHop` is stored in a `Vec` (as `Option`s),
rather than `HashMap` entries, they can grow to fill a full two
cache lines without a memory access performance cost. In the next
commit we'll take advantage of this somewhat, but here we update
the assertions and drop the `repr(C)`, allowing rust to lay the
memory out as it wishes.

Drop the `dist` `HashMap` in routing, replacing it with a `Vec`.

Now that we have unique, dense, 32-bit identifiers for all the
nodes in our network graph, we can store the per-node information
when routing in a simple `Vec` rather than a `HashMap`. This avoids
the overhead of hashing and table scanning entirely, for a nice
"simple" optimization win.

Use `NodeCounters` `NodeId`s as the blinded path intro references

The router's `introduction_node_id_cache` is used to cache the
`NodeId`s of blinded path introduction points so that we don't
have to look them up every time we go around the main router loop.
When using it, if the introduction point isn't a public node we
then look up the introduction in our first-hops map.

In either case, we have to end up with a reference to a `NodeId`
that outlives our `dist` map.

Here we consolidate both the initial cache building and the
first-hops map lookup to one place, storing only a reference to a
`NodeId` either in the `NetworkGraph` or in the new `NodeCounters`
to get the required lifetime without needing to reference into the
first-hops map.

We then take this opportunity to avoid `clone`ing the first-hops
map entries as we now no longer reference into it.

Drop `private_hop_key_cache` in favor of `NodeCounters`

With the new `NodeCounters` have have a all the `NodeId`s we'll
need during routing, so there's no need to keep the
`private_hop_key_cache` which existed to provide references to
`NodeId`s which are needed during routing.

Add a new `NodeCounters` utility to track counters when routing

In the next commit we'll stop using `NodeId`s to look up nodes when
routing, instead using the new per-node counters. Here we take the
first step, adding a local struct which tracks temporary counters
for route hints/source/destination nodes.

Because we must ensure we have a 1-to-1 mapping from node ids to
`node_counter`s, even across first-hop and last-hop hints, we have
to be careful to check the network graph first, then a new
`private_node_id_to_node_counter` map to ensure we only ever end up
with one counter per node id.

Merge pull request #3085 from shaavan/issue2837

Introduce RecipientData and use it to allow abandon failed payments

Merge pull request #3161 from vincenzopalazzo/macros/fix-docs

meta: update docs to reflect the code

meta: update docs to reflect the code

The code documentation is outdated after the commit 935a716cc6c4fada075e2b740a70bb1b7b349d49

Signed-off-by: Vincenzo Palazzo <vincenzopalazzodev@gmail.com>

Merge pull request #3149 from alecchendev/2024-06-async-sign-cs-raa-order

Fix bug failing CS-RAA resend order on pending commitment signatures

Allow create_blinded_paths functions to accept MessageContext as input field

- Enabled `create_blinded_paths` to accept `MessageContext` TLVs as
  an input field.
- `MessageContext` is intended to be sent along with the `reply_path`
   to the counterparty.
- Added `MessageContext` in the `create_blinded_paths` flow, optionally
  appending it within the `reply_path`.
- Updated tests to verify the new feature.

Update handle_message to accept OffersContext data as an input field

1. Handling Offers Data:
   - Updated `handle_message` to accept `OffersContext` data as an input field.
   - If it is present, it will be utilized by the handler to
     abandon outbound payments that have failed for any reason.

2. Consistency in Custom Message Handling:
   - Updated `handle_custom_message` to accept optional custom data.
     for consistency.
   - Note: `custom_data` will remain unused in this PR.

`rustfmt`: Run on `lightning-background-processor/src/lib.rs`

Prepare `lightning-background-processor/src/lib.rs`

Fix bug failing CS-RAA resend order on pending commitment signatures

Merge pull request #3120 from TheBlueMatt/2023-11-mon-claim-bug

Block monitor updates to ensure preimages are in each MPP part

Introduce MessageContext in ReceiveTlvs

1. New Enum for Enhanced Data Handling:
   - Introduced the `MessageContext` enum, which allows the node to include
     additional context data along with the `reply_path` sent to the counterparty.
   - The node anticipates receiving this data back for further processing.

2. Variants in MessageContext:
   - The `MessageContext` enum includes two variants: "Offers" and
     "Context"
   - One of the variants, `Offers`, holds the `payment_id`
     of the associated Outbound BOLT12 Payment.

3. Future Usage:
   - This enum will be utilized in a subsequent commit to abandon outbound
     payments that have failed to complete for various reasons.

Remove path_id from Responder, and OnionMessageResponse struct

1. The path_id will be removed from the codebase in the following
   commits.

Test the new `RAAMonitorUpdateBlockingAction::ClaimedMPPPayment`

Block monitor updates to ensure preimages are in each MPP part

If we claim an MPP payment and only persist some of the
`ChannelMonitorUpdate`s which include the preimage prior to
shutting down, we may be in a state where some of our
`ChannelMonitor`s have the preimage for a payment while others do
not.

This, it turns out, is actually mostly safe - on startup
`ChanelManager` will detect there's a payment it has as unclaimed
but there's a corresponding payment preimage in a `ChannelMonitor`
and go claim the other MPP parts. This works so long as the
`ChannelManager` has been persisted after the payment has been
received but prior to the `PaymentClaimable` event being processed
(and the claim itself occurring). This is not always true and
certainly not required on our API, but our
`lightning-background-processor` today does persist prior to event
handling so is generally true subject to some race conditions.

In order to address this we need to use copy payment preimages
across channels irrespective of the `ChannelManager`'s payment
state, but this introduces another wrinkle - if one channel makes
substantial progress while other channel(s) are still waiting to
get the payment preimage in `ChannelMonitor`(s) while the
`ChannelManager` hasn't been persisted after the payment was
received, we may end up without the preimage on disk.

Here, we address this issue by using the new
`RAAMonitorUpdateBlockingAction` variant for this specific case. We
block persistence of an RAA `ChannelMonitorUpdate` which may remove
the preimage from disk until all channels have had the preimage
added to their `ChannelMonitor`.

We do this only in-memory (and not on disk) as we can recreate this
blocker during the startup re-claim logic.

This will enable us to claim MPP parts without using the
`ChannelManager`'s payment state in later work.

Add a `RAAMonitorUpdateBlockingAction::ClaimedMPPPayment`

If we claim an MPP payment and only persist some of the
`ChannelMonitorUpdate`s which include the preimage prior to
shutting down, we may be in a state where some of our
`ChannelMonitor`s have the preimage for a payment while others do
not.

This, it turns out, is actually mostly safe - on startup
`ChanelManager` will detect there's a payment it has as unclaimed
but there's a corresponding payment preimage in a `ChannelMonitor`
and go claim the other MPP parts. This works so long as the
`ChannelManager` has been persisted after the payment has been
received but prior to the `PaymentClaimable` event being processed
(and the claim itself occurring). This is not always true and
certainly not required on our API, but our
`lightning-background-processor` today does persist prior to event
handling so is generally true subject to some race conditions.

In order to address this race we need to use copy payment preimages
across channels irrespective of the `ChannelManager`'s payment
state, but this introduces another wrinkle - if one channel makes
substantial progress while other channel(s) are still waiting to
get the payment preimage in `ChannelMonitor`(s) while the
`ChannelManager` hasn't been persisted after the payment was
received, we may end up without the preimage on disk.

Here, we address this issue with a new
`RAAMonitorUpdateBlockingAction` variant for this specific case. We
block persistence of an RAA `ChannelMonitorUpdate` which may remove
the preimage from disk until all channels have had the preimage
added to their `ChannelMonitor`.

We do this only in-memory (and not on disk) as we can recreate this
blocker during the startup re-claim logic.

This will enable us to claim MPP parts without using the
`ChannelManager`'s payment state in later work.

Track the cp `node_id` which originated an HTLC in the `HTLCSource`

Because we track pending `ChannelMonitorUpdate`s per-peer, we
really need to know what peer an HTLC came from when we go to claim
it on-chain, allowing us to look up any blocked actions in the
`PeerState`. While we could do this by moving the blocked actions
to some global "closed-channel update queue", its simpler to do it
this way.

While this trades off `ChannelMonitorUpdate` size somewhat (the
`HTLCSource` is included in many of them), which we should be
sensitive to, it will also allow us to (eventually) remove the
SCID -> peer + channel_id lookups we do when claiming or failing
today, which are somewhat annoying to deal with.

Add skipping variants to `impl_writeable_tlv_based_enum_upgradable`

In some cases, we have variants of an enum serialized using
`impl_writeable_tlv_based_enum_upgradable` which we don't want to
write/read. Here we add support for such variants by writing them
using the (odd) type 255 without any contents and using
`MaybeReadable` to decline to read them.

Merge pull request #3151 from alecchendev/2024-06-async-test-util-followup

Async signing test util follow ups

Merge pull request #3156 from valentinewallace/2024-07-b12-max-path-len

Set max path length when paying BOLT 12 invoices.

Set max path length when paying BOLT 12 invoices.

Merge pull request #3158 from dunxen/2024-07-excludemergesfrommutants

Skip incremental-mutants job for main

Fix CI for unused `PendingOnionMessage`

Skip incremental-mutants job for main

There is no diff when running against main, so we skip incremental-mutants.
Before this commit, we'd get `Error: Failed to parse diff: Line 1: Error while parsing:`
as the diff file was empty.

Test router: support expecting blinded payment paths.

Remove spurious commented out code line.

Merge pull request #3154 from TheBlueMatt/2024-06-message-flags

Fix spelling in comment

Allow sending RAA upon unblocking the signer

Fix spelling in comment

From @valentinewallace at
https://github.com/lightningdevkit/rust-lightning/pull/3144#discussion_r1661404243

Merge pull request #3144 from TheBlueMatt/2024-06-message-flags

(Re-)add handling for `ChannelUpdate::message_flags`

Use `test_msg_exact` in `channl_update` fuzz testing

Gossip messages should always use `test_msg_exact` to ensure they
round-trip during signature validation.

(Re-)add handling for `ChannelUpdate::message_flags`

When the `htlc_maximum_msat` field was made mandatory in
`ChannelUpdate` (in b0e8b739b73cc25f3e1ab00695a14d972162a140) we
started ignoring the `message_flags` field entirely and always
writing `1`. The comment updates indicated that the `message_flags`
field was deprecated, but this is not true - only the
`htlc_maximum_msat` indicator bit was deprecated, requiring it to
be 1.

If a node creates a `channel_update` with `message_flags` bits set
other than the low bit, this will cause us to spuriously reject
the message with an invalid signature error as we will check the
message against the wrong hash.

With today's current spec this is totally fine - the only other bit
defined for `message_flags` is the `dont_forward` bit, which when
set indicates we shouldn't accept the message into our gossip store
anyway (though this may lead to spurious `warning` messages being
sent to peers). However, in the future this may mean we start
rejecting valid `channel_update`s if new bits are defiend.

Async signing test util follow ups

- Remove unused unavailable signers in TestKeysInterface
- Remove unnecessary display implementation for SignerOp
- Move set of test disabled signer ops to EnforcementState
- Add method to enable/disable all signer ops at once

Merge pull request #2763 from dunxen/2023-11-mutation-testing

Introduce mutation testing

Introduce basic incremental mutation testing

We introduce a CI job for mutation testing of PR diffs using cargo-mutants.
Missed cases do not trigger a fail of this job yet as we just introduce it
now for visibility. We may start enforcing stricter rules at a later stage.

Merge pull request #3129 from optout21/splicing-msgs-update

Update splice messages according to new spec draft

Merge pull request #3147 from TheBlueMatt/2024-06-feerate-overflow

Handle feerates of `u32::MAX` without overflowing

Merge pull request #2989 from optout21/iatx-shared-output

Interactive TX negotiation tracks shared outputs

Handle feerates of `u32::MAX` without overflowing

Though we generally shouldn't be seeing these, and the
`get_dust_buffer_feerate` implementation will still return
`u32::MAX` in spite of the overflow, we should handle the overflow
to avoid panic when `debug_assertions` are enabled.

Found by the `full_stack_target` fuzzer

Merge pull request #3145 from valentinewallace/2024-06-AP-prefactor-followup

Followups to #3125

Implement AsyncPaymentsMessageHandler for ChanMan and use everywhere

Dummy implementation for now. This avoids having to change a bunch of type
signatures in the future when we replace the dummy impl with a real one.

Onion message fuzzer: update held_htlc_available handling

Fuzzers should always do more, not less. Post-merge feedback on
e8f154dd3c299c7988762909df48b0c9d919d6f8.

Merge pull request #3125 from valentinewallace/2024-06-async-payments-prefactor

Async payments message encoding and prefactor