Skip to main content

hopr_protocol_hopr/
surb_store.rs

1use std::{
2    collections::VecDeque,
3    sync::Arc,
4    time::{Duration, Instant},
5};
6
7use hopr_api::types::internal::{prelude::HoprPseudonym, routing::SurbMatcher};
8use hopr_crypto_packet::prelude::*;
9use hopr_protocol_pix::SsaIndex;
10use moka::notification::RemovalCause;
11use validator::ValidationError;
12
13use crate::{FoundSurb, SurbInsertOutcome, traits::SurbStore};
14
15/// Lower bound on [`SurbStoreConfig::pseudonyms_lifetime`], enforced by the config validator.
16///
17/// Public so that callers applying their own override can floor it identically, rather than
18/// reaching a value the config file itself would have been rejected for.
19pub const MINIMUM_SURB_LIFETIME: Duration = Duration::from_secs(30);
20
21/// Floor on the byte budget of each Entry-side SURB map: 85 MB, about what the fixed 100 000-record
22/// cap of the pending map used, measured at roughly 840 B per record in the cache it was built on
23/// (hoprnet#8624).
24///
25/// The config validator rejects a budget below it, and the transport clamps to it, so a small value
26/// never shrinks the maps below what they held before the byte budget existed. The maps account a
27/// record by its own size, so this budget holds about 143 000 pending records, never fewer than the
28/// 100 000 it replaces.
29pub const MINIMUM_PENDING_SURB_MAX_BYTES: u64 = 85_000_000;
30
31/// Default byte budget for **each** of the two Entry-side SURB maps.
32///
33/// 256 MiB holds about 454 000 pending records per map, some 23 deployed-size stocks (19 264 SURBs
34/// each), so the overflow hoprnet#8624 describes is fixed with room to spare. See
35/// [`SurbStoreConfig::pending_surb_max_bytes`] for the pair's worst-case total.
36pub const DEFAULT_PENDING_SURB_MAX_BYTES: u64 = 256 * 1024 * 1024;
37
38/// Ceiling on [`SurbStoreConfig::pending_surb_max_bytes`]: 4 GiB per map.
39///
40/// The budget is a memory commitment the operator makes, so a typo must not be able to ask for an
41/// unbounded map. 4 GiB is 16× the default and about 7 million pending records per map, far past any
42/// deployed Session count (100 Sessions × 19 264 SURBs is ~1.93 M records, about 1.1 GB) while still
43/// leaving the pair inside a node's RAM.
44pub const MAXIMUM_PENDING_SURB_MAX_BYTES: u64 = 4 * 1024 * 1024 * 1024;
45/// Subtracts `n` from the quarantine SURB budget, clamping at zero instead of wrapping.
46///
47/// Every refund site reads a ring length outside the ring's own lock, so a stale reader can subtract
48/// SURBs that another site already accounted: with a bare `fetch_sub`, that interleaving drives the
49/// counter past zero and wraps it to near `usize::MAX`, after which `counter + len > budget` holds for
50/// every quarantine insert and the store refuses unadmitted ingress for good — a self-inflicted
51/// denial that no later drain can undo, because the drain subtracts rather than resets. Saturating
52/// keeps the design's "no resync" stance (an over-refund still under-counts, which the cache's own
53/// `max_capacity` bounds) while making the failure self-correcting: the counter bottoms out at zero
54/// and the next refund-free insert tops it back up.
55fn refund_quarantine_budget(budget: &std::sync::atomic::AtomicUsize, n: usize) {
56    if n == 0 {
57        return;
58    }
59    let mut current = budget.load(std::sync::atomic::Ordering::Relaxed);
60    while let Err(observed) = budget.compare_exchange_weak(
61        current,
62        current.saturating_sub(n),
63        std::sync::atomic::Ordering::Relaxed,
64        std::sync::atomic::Ordering::Relaxed,
65    ) {
66        current = observed;
67    }
68}
69
70/// Lower bound on [`SurbStoreConfig::eviction_report_interval`], enforced by the config validator.
71pub const MINIMUM_EVICTION_REPORT_INTERVAL: Duration = Duration::from_secs(1);
72const MINIMUM_OPENER_PSEUDONYMS: usize = 1000;
73const MINIMUM_OPENERS_PER_PSEUDONYM: usize = 1000;
74const MINIMUM_OPENER_LIFETIME: Duration = Duration::from_secs(60);
75const MIN_SURB_RB_CAPACITY: usize = 1024;
76/// Lower bound on [`SurbStoreConfig::quarantine_max_pseudonyms`], enforced by the config validator.
77///
78/// Deliberately far below the reply-opener caches' 1000-pseudonym floor: those are written only by
79/// locally-originated sends, while the quarantine is written by whatever pseudonym an unauthenticated
80/// peer chose, so its bound is a small multiple of a packet's worth of SURBs, not a Session census.
81const MINIMUM_QUARANTINE_PSEUDONYMS: usize = 64;
82/// Lower bound on [`SurbStoreConfig::quarantine_rb_capacity`], enforced by the config validator.
83///
84/// One: a single `HoprPacket::Final` may carry up to `MAX_SURBS_IN_PACKET` SURBs, and each must be
85/// able to enter its ring without evicting a batch-mate, so the meaningful floor is "at least one
86/// packet", not "at least a Session's buffer".
87const MINIMUM_QUARANTINE_RB_CAPACITY: usize = 1;
88/// Lower bound on [`SurbStoreConfig::quarantine_surb_budget`], enforced by the config validator.
89///
90/// A backstop well above what the quarantine's own entry count and per-ring cap already bound
91/// (1024 × 16 by default), so it only bites if those two are raised out of proportion to each other.
92///
93/// Test-only: the validator spells the floor as a literal, matching every other range rule in this
94/// file, and the config test pins the two together by asserting the boundary either side of this.
95#[cfg(test)]
96const QUARANTINE_SURB_BUDGET_FLOOR: usize = 4096;
97
98/// Mints the number naming each admission of a pseudonym, process-wide.
99///
100/// Every [`SurbStore::admit`] call takes the next value, so two admissions of the same pseudonym can
101/// never share one — which is the property the deferred retire leans on. The counter is process-wide
102/// rather than per pseudonym so that an `admit` does not have to look up the pseudonym's previous
103/// number to advance it; `u64` is inexhaustible at any conceivable admission rate.
104///
105/// Zero is deliberately never minted: a session-side `AdmissionToken::NONE` carries zero, and a
106/// retire presenting it must match nothing — it is what a teardown of a never-admitted Session
107/// passes through the seam.
108static ADMISSION_EPOCHS: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(1);
109
110/// Takes the next admission number. Never zero — see [`ADMISSION_EPOCHS`].
111fn next_admission_epoch() -> u64 {
112    ADMISSION_EPOCHS.fetch_add(1, std::sync::atomic::Ordering::Relaxed)
113}
114
115fn validate_pseudonyms_lifetime(lifetime: &Duration) -> Result<(), ValidationError> {
116    if lifetime < &MINIMUM_SURB_LIFETIME {
117        Err(ValidationError::new("pseudonyms_lifetime is too low"))
118    } else {
119        Ok(())
120    }
121}
122
123fn validate_quarantine_lifetime(lifetime: &Duration) -> Result<(), ValidationError> {
124    if lifetime < &MINIMUM_SURB_LIFETIME {
125        Err(ValidationError::new("quarantine_lifetime is too low"))
126    } else {
127        Ok(())
128    }
129}
130
131fn validate_reply_opener_lifetime(lifetime: &Duration) -> Result<(), ValidationError> {
132    if lifetime < &MINIMUM_OPENER_LIFETIME {
133        Err(ValidationError::new("reply_opener_lifetime is too low"))
134    } else {
135        Ok(())
136    }
137}
138
139fn validate_eviction_report_interval(interval: &Duration) -> Result<(), ValidationError> {
140    if interval < &MINIMUM_EVICTION_REPORT_INTERVAL {
141        Err(ValidationError::new("eviction_report_interval is too low"))
142    } else {
143        Ok(())
144    }
145}
146
147fn default_rb_capacity() -> usize {
148    100_000
149}
150
151fn default_distress_threshold() -> usize {
152    500
153}
154
155fn default_max_openers_per_pseudonym() -> usize {
156    100_000
157}
158
159fn default_max_pseudonyms() -> usize {
160    10_000
161}
162
163fn default_pseudonyms_lifetime() -> Duration {
164    Duration::from_secs(600)
165}
166
167fn default_reply_opener_lifetime() -> Duration {
168    Duration::from_secs(3600)
169}
170
171fn default_eviction_report_interval() -> Duration {
172    Duration::from_secs(60)
173}
174
175fn default_eviction_report_threshold() -> u64 {
176    1000
177}
178
179fn default_pending_surb_max_bytes() -> u64 {
180    DEFAULT_PENDING_SURB_MAX_BYTES
181}
182
183fn default_quarantine_rb_capacity() -> usize {
184    16
185}
186
187fn default_quarantine_max_pseudonyms() -> usize {
188    1024
189}
190
191fn default_quarantine_lifetime() -> Duration {
192    Duration::from_secs(60)
193}
194
195fn default_quarantine_surb_budget() -> usize {
196    65_536
197}
198
199fn default_admitted_max_pseudonyms() -> usize {
200    10_000
201}
202
203fn default_admitted_headroom_percent() -> u32 {
204    50
205}
206
207/// Which end of the per-pseudonym buffer a pop consumes from. Replying side only.
208///
209/// FIFO, oldest first, is the only order. SURBs that carry a PIX share are always consumed before
210/// share-less ones (see "Share-bearing SURBs first" on the internal `SurbRingBuffer`), and within each
211/// of those two tiers the oldest goes first, whether it is popped or evicted on overflow. The order is
212/// independent of the per-SURB generation tag (`SurbReceiverInfo::generation`), which handles an
213/// explicit return-path re-plan by clearing superseded SURBs wholesale on the next push.
214///
215/// There used to be a `Lifo` variant (hoprnet#8328), consuming newest first so that a return-path
216/// change would apply before the buffered SURBs drained. It was removed because PIX cannot work with
217/// it: a share reaches the reconstructor only when its SURB is *used*, so a LIFO store buries the
218/// oldest shares of the current cycle, and an overflow then evicts exactly those, which loses them for
219/// good. Every node may act as a PIX Exit and nothing in the configuration turns that off
220/// (`enforce_pix` only makes it mandatory), so the option had no safe use — and what it was for is
221/// what the generation tag does.
222///
223/// What FIFO gives up is that SURBs the sender replaced, because their return path broke, are spent
224/// before their replacements, so a dead relayer's SURBs are spent into the void until the buffer turns
225/// over. The sender makes up for it: when a relayer is judged dead it advances the session's SURB
226/// generation, and this side drops everything it holds on the next push (see "Generations" on the
227/// internal `SurbRingBuffer`). The sender's judgement of its relayers counts on this order as well: it
228/// reads a race between two SURBs minted together by the one a FIFO replier spends first.
229///
230/// This enum, and the [`SurbStoreConfig::pop_order`] field carrying it, remain only so that existing
231/// configurations (`pop_order: fifo`) and code naming [`SurbPopOrder::Fifo`] keep working; they are
232/// candidates for removal in a later major version. `pop_order: lifo` is rejected as an unknown
233/// variant.
234#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash, strum::EnumString, strum::Display)]
235#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
236#[strum(serialize_all = "lowercase")]
237#[cfg_attr(feature = "serde", serde(rename_all = "lowercase"))]
238pub enum SurbPopOrder {
239    /// Oldest first. The only order, and the default.
240    #[default]
241    Fifo,
242}
243
244/// Configuration for the SURB cache.
245///
246/// The configuration options affect both the sending side (SURB creator) and the
247/// replying side (SURB consumer).
248///
249/// In the classical scenario (`Entry - Relay 1 -... - Exit`), the sending side is
250/// the `Entry` and the replying side is the `Exit`.
251#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, smart_default::SmartDefault, validator::Validate)]
252#[cfg_attr(
253    feature = "serde",
254    derive(serde::Deserialize, serde::Serialize),
255    serde(deny_unknown_fields)
256)]
257pub struct SurbStoreConfig {
258    /// Size of the SURB ring buffer per pseudonym.
259    ///
260    /// Affects only the replying side.
261    ///
262    /// This indicates how many SURBs can be at most held to be used to send a reply
263    /// back to the sending side.
264    ///
265    /// Once the buffer is full, a push evicts share-less SURBs first (oldest first); only when none
266    /// remain does it evict the oldest share-bearing SURB. An evicted SURB is never used. With PIX,
267    /// evicting one that carries a share is not merely a wasted SURB: a partial SSA share is only
268    /// delivered to the reconstructor when its SURB is *used*, so the share is lost for good. The
269    /// capacity is therefore sized well above what any Session's SURB balancer targets — see
270    /// `maximum_surb_buffer_size` in `hopr-transport`, which is derived from this value with
271    /// headroom left for balancer overshoot.
272    ///
273    /// This is a ceiling rather than a reservation: the internal `SurbRingBuffer` allocates with
274    /// occupancy, so a pseudonym holding three SURBs costs three, and only one that genuinely fills
275    /// up pays `rb_capacity` × ~400 B. That property is what makes a large default safe here — see
276    /// the "Why the capacity is a ceiling, not a reservation" section on `SurbRingBuffer`.
277    ///
278    /// Default is 100 000.
279    // `SurbRingBuffer` is deliberately unlinked above: it is crate-private, so an intra-doc link
280    // from this public field trips `rustdoc::private_intra_doc_links`, which CI builds as an error.
281    #[default(default_rb_capacity())]
282    #[validate(range(min = 1024, message = "rb_capacity must be at least 1024"))]
283    #[cfg_attr(feature = "serde", serde(default = "default_rb_capacity"))]
284    pub rb_capacity: usize,
285    /// Pop order of the per-pseudonym buffer; see [`SurbPopOrder`].
286    ///
287    /// FIFO is the only order, so this setting changes nothing. It is retained for configuration
288    /// compatibility — a file that spells out `pop_order: fifo` keeps loading — and is a candidate for
289    /// removal in a later major version. `pop_order: lifo` is no longer accepted and fails to load as an
290    /// unknown variant: PIX cannot work with LIFO, see [`SurbPopOrder`] for why.
291    ///
292    /// Affects only the replying side. Default is [`SurbPopOrder::Fifo`].
293    #[cfg_attr(feature = "serde", serde(default))]
294    pub pop_order: SurbPopOrder,
295    /// Threshold for the number of SURBs in the ring buffer, below which it is
296    /// considered low ("SURB distress").
297    ///
298    /// Default is 500.
299    #[default(default_distress_threshold())]
300    #[validate(range(min = 10, message = "distress_threshold must be at least 10"))]
301    #[cfg_attr(feature = "serde", serde(default = "default_distress_threshold"))]
302    pub distress_threshold: usize,
303    /// Maximum number of reply openers (SURB counterparts) per pseudonym.
304    ///
305    /// Affects only the sending side when decrypting a received reply.
306    ///
307    /// This mostly affects Sessions, as they use a fixed pseudonym.
308    /// It reflects how many reply openers the initiator-side of a Session can hold,
309    /// until the oldest ones are dropped. If the other party uses a SURB corresponding
310    /// to a dropped reply opener, the reply message will be undecryptable by the initiator-side.
311    ///
312    /// Default is 100 000.
313    #[default(default_max_openers_per_pseudonym())]
314    #[validate(range(min = 100, message = "max_openers_per_pseudonym must be at least 100"))]
315    #[cfg_attr(feature = "serde", serde(default = "default_max_openers_per_pseudonym"))]
316    pub max_openers_per_pseudonym: usize,
317    /// Retained for configuration back-compat only; no longer bounds the SURB ring cache.
318    ///
319    /// This used to size the single receiving-side SURB cache. The store now splits the receiving
320    /// side into the quarantine (bounded by [`SurbStoreConfig::quarantine_max_pseudonyms`]) and the
321    /// admitted class (bounded by [`SurbStoreConfig::admitted_max_pseudonyms`]), and this field
322    /// sizes nothing on the SURB path. Lowering it no longer bounds SURB memory — set those two
323    /// fields instead. It keeps its validator and serde default so an operator file that spells it
324    /// out still loads, and a later major version can remove it.
325    ///
326    /// Default is 10 000.
327    #[default(default_max_pseudonyms())]
328    #[validate(range(min = 100, message = "max_pseudonyms must be at least 100"))]
329    #[cfg_attr(feature = "serde", serde(default = "default_max_pseudonyms"))]
330    pub max_pseudonyms: usize,
331    /// Maximum lifetime of ring-buffer for each pseudonym.
332    ///
333    /// # Effects on sending side
334    /// This is the period for which we hold all reply openers for a pseudonym.
335    /// If no more messages carrying SURBs are sent during this period, the entire stash of
336    /// reply openers is dropped. Preventing receiving any more replies for that pseudonym.
337    ///
338    /// # Effects on replying side
339    /// If a pseudonym has not received any SURBs for this period,
340    /// the entire ring buffer with `rb_capacity` (= all SURBs for this pseudonym) is dropped.
341    /// Preventing from sending any more replies for that pseudonym.
342    ///
343    /// Default is 600 seconds.
344    #[default(default_pseudonyms_lifetime())]
345    #[validate(custom(function = "validate_pseudonyms_lifetime"))]
346    #[cfg_attr(
347        feature = "serde",
348        serde(default = "default_pseudonyms_lifetime", with = "humantime_serde")
349    )]
350    pub pseudonyms_lifetime: Duration,
351    /// Maximum lifetime of a reply opener.
352    ///
353    /// Affects only the sending side.
354    ///
355    /// A reply opener is distinguished using [`HoprSurbId`] and a pseudonym it belongs to.
356    /// If a reply opener is not used to decrypt the received packet within this period,
357    /// it is dropped. If the replying side uses the corresponding SURB to send a reply,
358    /// it won't be possible to decrypt it when received.
359    ///
360    /// Default is 3600 seconds.
361    #[default(default_reply_opener_lifetime())]
362    #[validate(custom(function = "validate_reply_opener_lifetime"))]
363    #[cfg_attr(
364        feature = "serde",
365        serde(default = "default_reply_opener_lifetime", with = "humantime_serde")
366    )]
367    pub reply_opener_lifetime: Duration,
368    /// How often cache evictions are summarised in the log, per cache and cause, instead of per entry.
369    ///
370    /// Affects both sides. Default is 60 seconds.
371    #[default(default_eviction_report_interval())]
372    #[validate(custom(function = "validate_eviction_report_interval"))]
373    #[cfg_attr(
374        feature = "serde",
375        serde(default = "default_eviction_report_interval", with = "humantime_serde")
376    )]
377    pub eviction_report_interval: Duration,
378    /// Evictions from one cache per report interval above which the summary is a warning rather than debug.
379    ///
380    /// Lost PIX shares (`ring_share`) are exempt: they are permanent, so any count warns, however high
381    /// this is set. Dropped share-less SURBs (`ring_plain`) are not.
382    ///
383    /// Affects both sides. Default is 1000.
384    #[default(default_eviction_report_threshold())]
385    #[cfg_attr(feature = "serde", serde(default = "default_eviction_report_threshold"))]
386    pub eviction_report_threshold: u64,
387    /// Per-ring cap for **quarantined** pseudonyms — those no established Session stands behind.
388    ///
389    /// Every `HoprPacket::Final` carrying SURBs reaches the store with no ticket verification on the
390    /// `Final` arm, so the pseudonym the packet names is chosen by the sender. An unadmitted batch
391    /// lands here, capped per ring so one pseudonym cannot reserve more than a packet's worth of
392    /// return path (`MAX_SURBS_IN_PACKET` is 8, so 16 leaves headroom). A pseudonym is promoted out
393    /// of quarantine once a Session over it is established and [`SurbStore::admit`] fires; anything
394    /// left here expires after [`SurbStoreConfig::quarantine_lifetime`].
395    ///
396    /// Default is 16.
397    #[default(default_quarantine_rb_capacity())]
398    #[validate(range(min = 1, message = "quarantine_rb_capacity must be at least 1"))]
399    #[cfg_attr(feature = "serde", serde(default = "default_quarantine_rb_capacity"))]
400    pub quarantine_rb_capacity: usize,
401    /// Capacity of the quarantine cache: how many distinct unadmitted pseudonyms may hold a ring.
402    ///
403    /// The quarantine is the only store an unauthenticated peer can write into, so it — not the
404    /// admitted cache below — is what pseudonym churn must be absorbed by. 1024 ×
405    /// `quarantine_rb_capacity` × ~400 B is a few MB. Beyond this many distinct pseudonyms, the
406    /// least-recently-used quarantine rings are shed; their SURBs are unadmitted, so nothing with a
407    /// Session behind it is lost.
408    ///
409    /// Default is 1024.
410    #[default(default_quarantine_max_pseudonyms())]
411    #[validate(range(min = 64, message = "quarantine_max_pseudonyms must be at least 64"))]
412    #[cfg_attr(feature = "serde", serde(default = "default_quarantine_max_pseudonyms"))]
413    pub quarantine_max_pseudonyms: usize,
414    /// How long a quarantined ring survives with no SURBs arriving for it.
415    ///
416    /// Bounds the unadmitted class from the time side, the way [`SurbStoreConfig::pseudonyms_lifetime`]
417    /// bounds the admitted one. Must cover the worst-case Session-initiation window — the span between
418    /// the first `Final` packet minting a quarantine ring and the Session over it being established
419    /// (which promotes the ring) — i.e. roughly `2 × initiation_timeout_base ×
420    /// RoutingOptions::MAX_INTERMEDIATE_HOPS`; the 60 s default clears that at both the 500 ms and the
421    /// 5 s base for up to 3 intermediate hops.
422    ///
423    /// Default is 60 seconds.
424    #[default(default_quarantine_lifetime())]
425    #[validate(custom(function = "validate_quarantine_lifetime"))]
426    #[cfg_attr(
427        feature = "serde",
428        serde(default = "default_quarantine_lifetime", with = "humantime_serde")
429    )]
430    pub quarantine_lifetime: Duration,
431    /// Backstop on the total number of unadmitted SURBs held across the whole quarantine cache.
432    ///
433    /// The quarantine cache's own entry and per-ring caps are the structural bound
434    /// (`quarantine_max_pseudonyms × quarantine_rb_capacity`); this counter is drained at insert time
435    /// and, when exhausted, sheds whole quarantine rings before refusing the batch. It exists so a
436    /// peer cannot rely on eviction timing: the accounting is exact at the mutation sites, so the two
437    /// bounds together cap the unadmitted class regardless of eviction scheduling. A backstop above
438    /// the cache's own bound needs no precision — a refused batch costs only unadmitted SURBs, never
439    /// one an established Session is holding.
440    ///
441    /// Default is 65 536.
442    #[default(default_quarantine_surb_budget())]
443    #[validate(range(min = 4096, message = "quarantine_surb_budget must be at least 4096"))]
444    // The floor above is spelled as a literal rather than interpolating `QUARANTINE_SURB_BUDGET_FLOOR`,
445    // matching every other range validator in this file; the test asserts the two agree.
446    #[cfg_attr(feature = "serde", serde(default = "default_quarantine_surb_budget"))]
447    pub quarantine_surb_budget: usize,
448    /// Capacity of the **admitted** cache: how many pseudonyms with an established Session may hold a
449    /// ring.
450    ///
451    /// Admission goes through [`SurbStore::admit`], which only an established Session triggers, so
452    /// unlike the quarantine this bound cannot be inflated by an unauthenticated peer. It is a
453    /// structural ceiling, not a per-insert counter: an admitted insert is never refused and an
454    /// admitted ring is never evicted to satisfy a counter. This value must be at least the node's
455    /// `maximum_managed_sessions`; the transport logs an error at startup if it is not, and an
456    /// overflow here is reported as an `admitted_overflow` metric event.
457    ///
458    /// Default is 10 000.
459    #[default(default_admitted_max_pseudonyms())]
460    #[validate(range(min = 1, message = "admitted_max_pseudonyms must be at least 1"))]
461    #[cfg_attr(feature = "serde", serde(default = "default_admitted_max_pseudonyms"))]
462    pub admitted_max_pseudonyms: usize,
463    /// Headroom the store adds over a Session's announced SURB target when sizing its admitted ring.
464    ///
465    /// A Session announces the buffer target it was configured with; the store admits a ring of
466    /// `expected × (1 + admitted_headroom_percent / 100)`, floored at `quarantine_rb_capacity` and
467    /// ceiled at [`SurbStoreConfig::rb_capacity`]. The inverse relation to `surb_buffer_target_ceiling`
468    /// in `hopr-transport` (which sets the announced target at `rb_capacity × 2/3`) means an Entry
469    /// announcing its maximum yields a full-`rb_capacity` admitted ring at the default 50 %.
470    ///
471    /// Default is 50.
472    #[default(default_admitted_headroom_percent())]
473    #[cfg_attr(feature = "serde", serde(default = "default_admitted_headroom_percent"))]
474    pub admitted_headroom_percent: u32,
475    /// Byte budget for **each** of the two Entry-side maps that remember minted SURBs until their reply
476    /// comes home: the pending map and the written-off-legs map. Sending side only.
477    ///
478    /// Each map holds as many records as fit in the budget at its own record size, evicting a random
479    /// record to admit a new one when full. The default 256 MiB holds about 454 000 pending records per
480    /// map (some 23 deployed-size stocks); both maps fill from it, so the pair peaks at about twice the
481    /// budget. Records the pending map could not hold are counted by `hopr_surb_pending_lost_total`, so
482    /// an undersized budget is visible.
483    ///
484    /// The validator rejects a value outside [`MINIMUM_PENDING_SURB_MAX_BYTES`] (85 MB) to
485    /// [`MAXIMUM_PENDING_SURB_MAX_BYTES`] (4 GiB). `MemorySurbStore` does not read this field; only
486    /// `hopr-transport`'s `HoprTransport::new` does.
487    ///
488    /// Default is 256 MiB.
489    #[default(default_pending_surb_max_bytes())]
490    #[validate(range(
491        min = MINIMUM_PENDING_SURB_MAX_BYTES,
492        max = MAXIMUM_PENDING_SURB_MAX_BYTES,
493        message = "pending_surb_max_bytes must be between 85000000 and 4294967296 bytes"
494    ))]
495    #[cfg_attr(feature = "serde", serde(default = "default_pending_surb_max_bytes"))]
496    pub pending_surb_max_bytes: u64,
497}
498
499/// Basic [`SurbStore`] implementation based on an in-memory cache.
500///
501/// This SURB store offers no persistence, and all SURBs and Reply Openers are lost once dropped.
502///
503/// The instance can be cheaply cloned.
504#[derive(Clone)]
505pub struct MemorySurbStore {
506    pseudonym_openers: moka::sync::Cache<HoprPseudonym, moka::sync::Cache<HoprSurbId, ReplyOpener>>,
507    /// Receiving-side rings for **admitted** pseudonyms: those an established Session stands behind,
508    /// entered only through [`SurbStore::admit`] and left through [`SurbStore::retire`].
509    ///
510    /// This cache is also the single source of truth for admission: there is no separate
511    /// admission-marker cache for `insert_surbs` to route on, because a marker in one cache pointing
512    /// at a ring in another can desync (an eviction on one side, an insert on the other) and admits
513    /// can race inserts. [`SurbStore::insert_surbs`] takes the entry here, so a pseudonym is
514    /// admitted exactly as long as it holds one — even an empty one, which is what `admit` inserts
515    /// so that standing is known before the first SURB arrives.
516    ///
517    /// The value carries the admission's number next to the ring, so a deferred
518    /// [`SurbStore::retire`] can prove it is retiring the admission it was created for and not a
519    /// successor's — see [`AdmittedRing`]. The number and the ring share one entry so the compare in
520    /// `retire` and the removal are one atomic operation over the key.
521    admitted_surbs_per_pseudonym: moka::sync::Cache<HoprPseudonym, AdmittedRing>,
522    /// Receiving-side rings for **quarantined** pseudonyms: whatever pseudonym a `Final` packet chose
523    /// and no Session has claimed.
524    ///
525    /// Physically separate from [`admitted_surbs_per_pseudonym`](Self::admitted_surbs_per_pseudonym)
526    /// rather than a tier of it, so quarantine churn — pseudonym flooding, short TTI expiries, budget
527    /// drains — can never evict an admitted ring. That is a structural guarantee: the two caches share
528    /// no capacity or eviction machinery.
529    quarantine_surbs: moka::sync::Cache<HoprPseudonym, SurbRingBuffer<HoprSurb>>,
530    /// Count of SURBs currently held in [`quarantine_surbs`](Self::quarantine_surbs), across all its
531    /// rings.
532    ///
533    /// Drained at the two quarantine mutation sites (insert and find) and corrected by the eviction
534    /// listener, so it needs no resync pass — an opportunistic resync would be a CPU/lock amplifier
535    /// running on exactly the attacker-flooded state. It is a backstop, not the structural bound: the
536    /// cache's own `max_capacity` × `quarantine_rb_capacity` is the hard bound, and a few SURBs of
537    /// drift between a `ring.len()` read and the listener cannot exceed it.
538    ///
539    /// Refunds saturate at zero rather than wrapping: the refund sites read ring lengths without the
540    /// ring lock, so a stale reader could otherwise drive the counter past zero and permanently lock
541    /// out every quarantine insert — see [`refund_quarantine_budget`].
542    quarantine_budget: Arc<std::sync::atomic::AtomicUsize>,
543    /// Relayers this node can no longer pay. Holds at most a handful of entries (our own closing
544    /// channels), so a plain set behind an `RwLock` beats a concurrent map on this read-heavy path.
545    invalidated_relayers: Arc<parking_lot::RwLock<std::collections::HashSet<HoprKeyIdent>>>,
546    /// Current SURB-batch generation per pseudonym we originate for (sending side). Advanced on a
547    /// return-path change so the replying side can drop SURBs for the superseded path.
548    ///
549    /// This is sending-side state, so it is retained like the reply openers
550    /// ([`pseudonym_openers`](Self::pseudonym_openers)) — **not** like the receiving-side
551    /// [`admitted_surbs_per_pseudonym`](Self::admitted_surbs_per_pseudonym). If this entry were evicted while the peer
552    /// still held SURBs of generation `N`, [`current_generation`](Self::current_generation) would
553    /// fall back to `0`; the peer's [`SurbRingBuffer::push_counting`] then reads `generation_is_newer(0, N)`
554    /// as false (for `1 <= N <= 128`) and silently discards every fresh batch, stranding the reply
555    /// path. Both dimensions are therefore taken from the sending-side reply-opener config, not the
556    /// receiving-side SURB config: `reply_opener_lifetime` bounds how long we expect replies (hence
557    /// outstanding SURBs) for a pseudonym, and it is `>=` the peer's SURB idle window, so the serial
558    /// outlives the SURBs it numbers; and the capacity matches the reply-opener pseudonym bound
559    /// (`max_openers_per_pseudonym`, which covers `maximum_managed_sessions`) so LRU pressure from the
560    /// unrelated receiving-side `max_pseudonyms` cannot evict a live sender's generation.
561    generations: moka::sync::Cache<HoprPseudonym, Arc<std::sync::atomic::AtomicU8>>,
562    stats: Arc<EvictionStats>,
563    cfg: Arc<SurbStoreConfig>,
564}
565
566// The `cache` label takes the names of `EvictedCache`: the five moka caches, and `ring_plain` / `ring_share` for the
567// SURBs a full ring buffer drops or refuses, which are not cache entries but are counted alongside them. They are
568// values of the label, not new series, so the names, descriptions and label keys below stay as METRICS.md has them.
569#[cfg(all(feature = "telemetry", not(test)))]
570lazy_static::lazy_static! {
571    static ref METRIC_SURB_STORE_EVICTIONS: hopr_api::types::telemetry::MultiCounter = hopr_api::types::telemetry::MultiCounter::new(
572        "hopr_surb_store_evictions_count",
573        "Number of entries evicted from the SURB store caches, by cache and removal cause",
574        &["cache", "cause"],
575    )
576    .unwrap();
577    static ref METRIC_SURB_STORE_EVICTIONS_LAST_INTERVAL: hopr_api::types::telemetry::MultiGauge = hopr_api::types::telemetry::MultiGauge::new(
578        "hopr_surb_store_evictions_last_interval",
579        "Entries evicted from the SURB store caches during the last completed report interval, by cache and removal cause",
580        &["cache", "cause"],
581    )
582    .unwrap();
583    static ref METRIC_SURB_STORE_ADMISSIONS: hopr_api::types::telemetry::MultiCounter = hopr_api::types::telemetry::MultiCounter::new(
584        "hopr_surb_store_admissions_count",
585        "Admission-control events in the SURB store, by event kind",
586        &["event"],
587    )
588    .unwrap();
589    static ref METRIC_SURB_STORE_SURBS_HELD: hopr_api::types::telemetry::MultiGauge = hopr_api::types::telemetry::MultiGauge::new(
590        "hopr_surb_store_surbs_held",
591        "SURBs currently held by the SURB store, by trust class",
592        &["class"],
593    )
594    .unwrap();
595}
596
597#[cfg(all(feature = "telemetry", not(test)))]
598/// Values of the `event` label on `hopr_surb_store_admissions_count`.
599///
600/// Bounded by construction: each variant is recorded from exactly one named code path, so the series
601/// cardinality cannot grow with traffic.
602#[derive(Clone, Copy, Debug, strum::Display, strum::IntoStaticStr)]
603#[strum(serialize_all = "snake_case")]
604enum SurbAdmissionEvent {
605    /// A Session over the pseudonym was established and it entered the admitted class.
606    Admitted,
607    /// On admission, a quarantine ring was promoted into the admitted class rather than re-read.
608    Promoted,
609    /// The Session over the pseudonym ended and it left the admitted class.
610    Retired,
611    /// A retire arrived whose token no longer named the pseudonym's current admission — a successor
612    /// Session was admitted in the deferred-retire window, and its ring was left alone. Routine, and
613    /// worth a series rather than silence: a stale retire that *could* touch a live ring would show up
614    /// as this never rising while a Session's SURBs vanish.
615    RetiredStale,
616    /// An unadmitted batch was refused because the quarantine SURB budget was exhausted.
617    QuarantineRefused,
618    /// Quarantine rings were shed to get back under the quarantine SURB budget.
619    QuarantineEvicted,
620    /// The admitted cache overflowed `admitted_max_pseudonyms`: a Size eviction there means the
621    /// config is below `maximum_managed_sessions`, an operator misconfiguration worth alerting on.
622    AdmittedOverflow,
623}
624
625#[cfg(all(feature = "telemetry", not(test)))]
626/// Values of the `class` label on `hopr_surb_store_surbs_held`.
627#[derive(Clone, Copy, Debug, strum::Display, strum::IntoStaticStr)]
628#[strum(serialize_all = "snake_case")]
629enum SurbHeldClass {
630    /// SURBs behind an established Session.
631    Admitted,
632    /// Unadmitted SURBs, quarantined and time-limited.
633    Quarantine,
634}
635
636/// Which of the store's caches shed an entry. Doubles as the `cache` label on metrics and log lines.
637///
638/// The two `Ring*` variants are not caches in the moka sense: they count the SURBs that one
639/// pseudonym's full ring buffer drops or refuses ([`RemovalCause::Size`]), or a generation change takes out
640/// of play ([`RemovalCause::Replaced`]), split by what that costs, so that the same per-interval summary can tell a
641/// routine loss from a permanent one.
642#[derive(Clone, Copy, Debug, PartialEq, Eq, strum::Display, strum::IntoStaticStr)]
643#[strum(serialize_all = "snake_case")]
644enum EvictedCache {
645    /// Sending side: all reply openers of one pseudonym (`pseudonym_openers`).
646    ReplyOpenerBatch,
647    /// Sending side: a single reply opener within a pseudonym's batch.
648    ReplyOpener,
649    /// Replying side: a pseudonym's SURB ring buffer (`admitted_surbs_per_pseudonym`).
650    SurbRing,
651    /// Replying side: a share-less SURB a full ring buffer dropped, or refused as a newcomer. A lost
652    /// return path and nothing more, and routine while a sender that bypasses the balancer gate
653    /// outproduces what this side spends.
654    RingPlain,
655    /// Replying side: a SURB carrying a PIX share that a full ring buffer dropped or a generation change took out of
656    /// play. A share reaches the reconstructor only when its SURB is *used*, so the share is lost for good.
657    RingShare,
658    /// Sending side: a pseudonym's SURB generation serial (`generations`).
659    Generation,
660    /// Replying side: a pseudonym's quarantine SURB ring buffer (`quarantine_surbs`). Unadmitted
661    /// SURBs only, so an eviction here costs nothing an established Session holds.
662    QuarantineRing,
663}
664
665impl EvictedCache {
666    const ALL: [EvictedCache; 7] = [
667        Self::ReplyOpenerBatch,
668        Self::ReplyOpener,
669        Self::SurbRing,
670        Self::RingPlain,
671        Self::RingShare,
672        Self::Generation,
673        Self::QuarantineRing,
674    ];
675}
676
677#[cfg(all(feature = "telemetry", not(test)))]
678fn cause_label(cause: RemovalCause) -> &'static str {
679    match cause {
680        RemovalCause::Expired => "expired",
681        RemovalCause::Size => "size",
682        RemovalCause::Replaced => "replaced",
683        RemovalCause::Explicit => "explicit",
684    }
685}
686
687/// Evictions from one cache in one report interval, by cause.
688#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
689struct EvictionCounts {
690    expired: u64,
691    size: u64,
692    replaced: u64,
693}
694
695impl EvictionCounts {
696    /// Counts `n` evictions for `cause`.
697    ///
698    /// `Explicit` removals are deliberate (a used opener, an invalidation), not evictions, so they are skipped.
699    fn bump(&mut self, cause: RemovalCause, n: u64) {
700        match cause {
701            RemovalCause::Expired => self.expired += n,
702            RemovalCause::Size => self.size += n,
703            RemovalCause::Replaced => self.replaced += n,
704            RemovalCause::Explicit => {}
705        }
706    }
707
708    fn total(&self) -> u64 {
709        self.expired + self.size + self.replaced
710    }
711}
712
713/// The interval being counted right now.
714#[derive(Debug)]
715struct IntervalState {
716    started_at: Instant,
717    /// Parallel to [`EvictedCache::ALL`].
718    counts: [EvictionCounts; EvictedCache::ALL.len()],
719}
720
721/// Eviction counts per cache and cause, reported once per interval (GNO-793: per-entry lines flooded the log).
722struct EvictionStats {
723    interval: Duration,
724    warn_threshold: u64,
725    state: parking_lot::Mutex<IntervalState>,
726}
727
728impl EvictionStats {
729    fn new(cfg: &SurbStoreConfig) -> Self {
730        Self {
731            interval: cfg.eviction_report_interval.max(MINIMUM_EVICTION_REPORT_INTERVAL),
732            warn_threshold: cfg.eviction_report_threshold,
733            state: parking_lot::Mutex::new(IntervalState {
734                started_at: Instant::now(),
735                counts: Default::default(),
736            }),
737        }
738    }
739
740    fn record(&self, cache: EvictedCache, cause: RemovalCause) {
741        self.record_many(cache, cause, 1);
742    }
743
744    /// Counts `n` evictions at once, for a caller that learns of many together (one push dropping several
745    /// SURBs) and should not take the lock once per entry.
746    fn record_many(&self, cache: EvictedCache, cause: RemovalCause, n: u64) {
747        if let Some(report) = self.record_many_at(cache, cause, n, Instant::now()) {
748            report.log();
749        }
750    }
751
752    /// Closes the interval if `now` is past it, then counts `n` evictions; returns the closed interval's counts.
753    ///
754    /// A count of zero is not an eviction: it returns at once, without taking the lock or closing the
755    /// interval. That keeps the common case of a push that evicts nothing off the lock.
756    fn record_many_at(&self, cache: EvictedCache, cause: RemovalCause, n: u64, now: Instant) -> Option<EvictionReport> {
757        if n == 0 {
758            return None;
759        }
760
761        // One lock for check, drain and count, so a rollover cannot split an eviction from its interval.
762        let mut state = self.state.lock();
763        let report = self.close_interval_if_elapsed(&mut state, now);
764        state.counts[cache as usize].bump(cause, n);
765        drop(state);
766
767        #[cfg(all(feature = "telemetry", not(test)))]
768        if cause != RemovalCause::Explicit {
769            METRIC_SURB_STORE_EVICTIONS.increment_by(&[cache.into(), cause_label(cause)], n);
770        }
771        report
772    }
773
774    /// No runtime here, so the first eviction past the interval closes it: a quiet store reports late, not never.
775    fn close_interval_if_elapsed(&self, state: &mut IntervalState, now: Instant) -> Option<EvictionReport> {
776        if now.duration_since(state.started_at) < self.interval {
777            return None;
778        }
779        state.started_at = now;
780        let counts = std::mem::take(&mut state.counts);
781        Some(EvictionReport {
782            interval: self.interval,
783            warn_threshold: self.warn_threshold,
784            per_cache: EvictedCache::ALL.map(|cache| (cache, counts[cache as usize])),
785        })
786    }
787}
788
789/// The counts of one closed report interval, ready to be logged.
790#[derive(Debug)]
791struct EvictionReport {
792    interval: Duration,
793    warn_threshold: u64,
794    per_cache: [(EvictedCache, EvictionCounts); EvictedCache::ALL.len()],
795}
796
797impl EvictionReport {
798    fn counts(&self, cache: EvictedCache) -> EvictionCounts {
799        self.per_cache[cache as usize].1
800    }
801
802    /// Whether `cache` evicted enough in the interval for its summary to be a warning: more than the
803    /// configured threshold, except for lost shares, which warn at any count.
804    ///
805    /// A lost share is always worth a warning. It is permanent, and the redundancy budget that absorbs
806    /// such losses is finite, so each one brings a cycle closer to being unrecoverable. A dropped
807    /// share-less SURB, in contrast, is routine under gate bypass (the sender outproduces what this side
808    /// spends), so it keeps the configured threshold like every other cache.
809    fn exceeds_threshold(&self, cache: EvictedCache) -> bool {
810        let threshold = match cache {
811            EvictedCache::RingShare => 0,
812            _ => self.warn_threshold,
813        };
814        self.counts(cache).total() > threshold
815    }
816
817    fn log(&self) {
818        let interval_secs = self.interval.as_secs();
819        for (cache, counts) in self.per_cache {
820            #[cfg(all(feature = "telemetry", not(test)))]
821            for (cause, value) in [
822                (RemovalCause::Expired, counts.expired),
823                (RemovalCause::Size, counts.size),
824                (RemovalCause::Replaced, counts.replaced),
825            ] {
826                METRIC_SURB_STORE_EVICTIONS_LAST_INTERVAL.set(&[cache.into(), cause_label(cause)], value as f64);
827            }
828
829            if counts.total() == 0 {
830                continue;
831            }
832            if self.exceeds_threshold(cache) {
833                tracing::warn!(
834                    %cache,
835                    expired = counts.expired,
836                    size = counts.size,
837                    replaced = counts.replaced,
838                    interval_secs,
839                    "SURB store evicted entries in the last interval"
840                );
841            } else {
842                tracing::debug!(
843                    %cache,
844                    expired = counts.expired,
845                    size = counts.size,
846                    replaced = counts.replaced,
847                    interval_secs,
848                    "SURB store evicted entries in the last interval"
849                );
850            }
851        }
852    }
853}
854
855impl MemorySurbStore {
856    /// Creates a new instance with the given configuration.
857    pub fn new(cfg: SurbStoreConfig) -> Self {
858        #[cfg(all(feature = "telemetry", not(test)))]
859        {
860            lazy_static::initialize(&METRIC_SURB_STORE_EVICTIONS);
861            lazy_static::initialize(&METRIC_SURB_STORE_EVICTIONS_LAST_INTERVAL);
862            lazy_static::initialize(&METRIC_SURB_STORE_ADMISSIONS);
863            lazy_static::initialize(&METRIC_SURB_STORE_SURBS_HELD);
864        }
865        let stats = Arc::new(EvictionStats::new(&cfg));
866        let budget = Arc::new(std::sync::atomic::AtomicUsize::new(0));
867        Self {
868            // Reply openers are indexed by entire Sender IDs (Pseudonym + SURB ID)
869            // in a cascade fashion, allowing the entire batches (by Pseudonym) to be evicted
870            // if not used.
871            pseudonym_openers: moka::sync::Cache::builder()
872                .time_to_idle(cfg.pseudonyms_lifetime.max(MINIMUM_SURB_LIFETIME))
873                .eviction_policy(moka::policy::EvictionPolicy::lru())
874                .eviction_listener({
875                    let stats = stats.clone();
876                    move |_pseudonym, _openers, cause| stats.record(EvictedCache::ReplyOpenerBatch, cause)
877                })
878                .max_capacity(cfg.max_openers_per_pseudonym.max(MINIMUM_OPENER_PSEUDONYMS) as u64)
879                .build(),
880            // Admitted SURB rings: entered only through `admit`, i.e. only once an established Session
881            // stands behind the pseudonym. Sized by `admitted_max_pseudonyms`, which the operator sets
882            // at or above `maximum_managed_sessions` — an established Session per pseudonym is the only
883            // way to fill this cache, so its ceiling is the operator's own session census, not anything
884            // an unauthenticated peer can inflate. Its listener logs at ERROR on a Size removal: that is
885            // the one cause that says the config is wrong, since the cache cannot then hold one ring per
886            // live Session — an `admitted_overflow` event, worth alerting on.
887            //
888            // Deliberately no `time_to_idle`. The entry count is already bounded by
889            // `admitted_max_pseudonyms`, and every Session teardown retires its entry through
890            // `SurbStore::retire`, so a ring's lifetime is exactly its admission's lifetime — the
891            // invariant the whole design rests on, which a TTI can only violate. A Session's idle
892            // timeout is unbounded above and separate from `pseudonyms_lifetime`, and even at the
893            // defaults a Session can sit alive without receiving inbound SURBs for longer than the
894            // 600 s TTI. A ring reclaimed by time then silently falls back to the quarantine, whose
895            // 16-SURB cap drops the Session's later SURBs and PIX shares — the exact loss admission
896            // exists to prevent — and `SessionManager::ping_session` refreshes the session cache but
897            // does not re-admit, so nothing would restore it.
898            admitted_surbs_per_pseudonym: moka::sync::Cache::builder()
899                .eviction_policy(moka::policy::EvictionPolicy::lru())
900                .eviction_listener({
901                    let stats = stats.clone();
902                    move |_pseudonym, _surbs, cause| {
903                        // Size is the only cache-driven removal left — the entry otherwise leaves by
904                        // `retire`'s explicit removal — so it is the one cause that says the config is
905                        // wrong: the cache cannot hold one ring per live Session.
906                        if cause == RemovalCause::Size {
907                            #[cfg(all(feature = "telemetry", not(test)))]
908                            METRIC_SURB_STORE_ADMISSIONS
909                                .increment_by(&[SurbAdmissionEvent::AdmittedOverflow.into()], 1);
910                            tracing::error!(
911                                ?cause,
912                                "an admitted SURB ring was evicted for size: admitted_max_pseudonyms is below the \
913                                 number of live sessions"
914                            );
915                        }
916                        stats.record(EvictedCache::SurbRing, cause)
917                    }
918                })
919                .max_capacity(cfg.admitted_max_pseudonyms.max(1) as u64)
920                .build(),
921            // Quarantine rings: whatever pseudonym a `Final` packet chose and no Session has claimed.
922            // Capped and aged far below the admitted class — short TTI, few pseudonyms, few SURBs per
923            // ring — so unauthenticated churn is absorbed here and, being a physically separate cache,
924            // can never evict an admitted ring. The listener keeps the quarantine SURB budget honest for
925            // cache-driven removals (expiry, LRU, size): an explicit removal is a promotion or a
926            // deliberate take-over, which the promoting code path accounts for itself.
927            quarantine_surbs: moka::sync::Cache::builder()
928                .time_to_idle(cfg.quarantine_lifetime.max(MINIMUM_SURB_LIFETIME))
929                .eviction_policy(moka::policy::EvictionPolicy::lru())
930                .eviction_listener({
931                    let stats = stats.clone();
932                    let budget = Arc::clone(&budget);
933                    move |_pseudonym, ring: SurbRingBuffer<HoprSurb>, cause| {
934                        if cause != RemovalCause::Explicit {
935                            refund_quarantine_budget(&budget, ring.len());
936                        }
937                        stats.record(EvictedCache::QuarantineRing, cause)
938                    }
939                })
940                .max_capacity(cfg.quarantine_max_pseudonyms.max(MINIMUM_QUARANTINE_PSEUDONYMS) as u64)
941                .build(),
942            invalidated_relayers: Default::default(),
943            generations: moka::sync::Cache::builder()
944                // Sending-side state, so it is sized and aged like the sibling sending-side
945                // `pseudonym_openers` cache — NOT like the receiving-side admitted/quarantine SURB
946                // caches.
947                // Retained for the reply-opener window (>= the peer's SURB idle window) so the serial
948                // cannot reset to 0 while the peer still holds SURBs it numbers, and bounded by the
949                // reply-opener pseudonym capacity (which covers `maximum_managed_sessions`) so LRU
950                // pressure from the receiving-side `max_pseudonyms` cannot evict a live sender's
951                // generation. See the field doc for why an early eviction would strand the reply path.
952                .time_to_idle(cfg.reply_opener_lifetime.max(MINIMUM_OPENER_LIFETIME))
953                .eviction_policy(moka::policy::EvictionPolicy::lru())
954                .eviction_listener({
955                    let stats = stats.clone();
956                    move |pseudonym, _generation, cause| {
957                        // Expired: the pseudonym was idle for the whole reply-opener window, so the peer no longer
958                        // holds SURBs this serial numbers (#8429). Explicit: removed on purpose. Size and Replaced
959                        // can drop a serial that is still in use, and the peer then rejects SURBs numbered by it.
960                        if matches!(cause, RemovalCause::Expired | RemovalCause::Explicit) {
961                            tracing::debug!(%pseudonym, ?cause, "evicting SURB generation for pseudonym");
962                        } else {
963                            tracing::warn!(%pseudonym, ?cause, "evicting SURB generation for pseudonym");
964                        }
965                        stats.record(EvictedCache::Generation, cause);
966                    }
967                })
968                .max_capacity(cfg.max_openers_per_pseudonym.max(MINIMUM_OPENER_PSEUDONYMS) as u64)
969                .build(),
970            quarantine_budget: budget,
971            stats,
972            cfg: cfg.into(),
973        }
974    }
975
976    /// Whether `relayer` is currently unusable as a return path's first hop.
977    pub fn is_relayer_invalidated(&self, relayer: &HoprKeyIdent) -> bool {
978        self.invalidated_relayers.read().contains(relayer)
979    }
980
981    /// Ceiling on how many SURBs the admitted ring for `pseudonym` can hold, or `None` when it holds
982    /// no admitted ring.
983    ///
984    /// Observability seam: the ceiling is what an announced target has to raise, since a Session
985    /// whose ring is too narrow loses SURBs — and, under PIX, the shares they carried — the moment the
986    /// Entry mints past it.
987    ///
988    /// Note this is a cache `get`, so it records recency on the admitted cache's LRU. Every live
989    /// Session holds a ring and the cache is sized for that census, so a read here cannot evict one;
990    /// it is only a diagnostic, not a hot path.
991    pub fn admitted_ring_ceiling(&self, pseudonym: &HoprPseudonym) -> Option<usize> {
992        self.admitted_surbs_per_pseudonym
993            .get(pseudonym)
994            .map(|ring| ring.capacity())
995    }
996
997    /// Capacity for a newly created admitted ring, derived from the Session's announced SURB target.
998    ///
999    /// The target gets [`SurbStoreConfig::admitted_headroom_percent`] of headroom — the balancer aims
1000    /// below the ring's ceiling, so a ring exactly the size of the target would overflow on ordinary
1001    /// overshoot — then is floored at `quarantine_rb_capacity` and ceiled at the operator's
1002    /// `rb_capacity`. An announced target of `0` means "no announcement" and gets the floor: a ring of
1003    /// one is a trap the very next packet overflows, and nothing cheaper than the quarantine floor is
1004    /// worth admitting.
1005    fn admitted_ring_capacity(&self, expected_surbs: usize) -> usize {
1006        let floor = self.cfg.quarantine_rb_capacity.max(MINIMUM_QUARANTINE_RB_CAPACITY);
1007        if expected_surbs == 0 {
1008            return floor;
1009        }
1010        let headroom = expected_surbs.saturating_mul(100 + self.cfg.admitted_headroom_percent as usize) / 100;
1011        headroom.max(floor).min(self.cfg.rb_capacity.max(MIN_SURB_RB_CAPACITY))
1012    }
1013
1014    /// Widens `pseudonym`'s admitted ring for an announced SURB target that changed mid-Session.
1015    ///
1016    /// [`admit`](SurbStore::admit) sizes the ring once, from the target in force at establishment,
1017    /// and a peer may raise that target afterwards: the gnosis_vpn client ramps its balancer from a
1018    /// ping tier to a main tier seconds into the Session and announces each step (see
1019    /// gnosis/gnosis_vpn#739). Left alone, the ring keeps the first tier's ceiling while the Entry
1020    /// mints toward the new one — every SURB past the ceiling is evicted on arrival, and under PIX so
1021    /// is the share it carried, which is unrecoverable.
1022    ///
1023    /// The re-admission path already grows a ring in place (`SurbRingBuffer::raise_capacity` is a
1024    /// `fetch_max`, so it only ever widens). This is that path, for a peer rather than a successor
1025    /// Session: it mints no new admission number, so the `token` the Session already holds still
1026    /// names this admission and its teardown retires it as before. A `token` that no longer names the
1027    /// pseudonym's current admission is a no-op, for the same reason a stale retire is.
1028    ///
1029    /// `expected_surbs` is the *announced target*, not a ring size: the headroom, floor and ceiling
1030    /// arithmetic is this store's, exactly as in [`admit`](SurbStore::admit).
1031    pub fn raise_admitted_capacity(&self, pseudonym: &HoprPseudonym, token: u64, expected_surbs: usize) {
1032        if token == 0 {
1033            return;
1034        }
1035
1036        let capacity = self.admitted_ring_capacity(expected_surbs);
1037        self.admitted_surbs_per_pseudonym
1038            .entry_by_ref(pseudonym)
1039            .and_compute_with(|entry: Option<moka::Entry<HoprPseudonym, AdmittedRing>>| match entry {
1040                // Only the admission the caller names may be widened, and the ring it holds is kept:
1041                // this is a ceiling change, not a new admission, so no epoch is stamped and the
1042                // resident SURBs stay where they are.
1043                Some(entry) if entry.value().epoch() == token => {
1044                    entry.value().raise_capacity(capacity);
1045                    moka::ops::compute::Op::Nop
1046                }
1047                // No ring, or a successor's: nothing here is this caller's to widen.
1048                _ => moka::ops::compute::Op::Nop,
1049            });
1050    }
1051
1052    /// SURBs held for `pseudonym` across both classes.
1053    ///
1054    /// Sums the two caches rather than asking one, so the brief dual-ring state around a promotion —
1055    /// a batch that routed to the quarantine just before `admit` installed the admitted entry, and
1056    /// that sits there until its insert's post-push re-check folds it in — cannot under-report what
1057    /// the pseudonym holds.
1058    fn ring_len(&self, pseudonym: &HoprPseudonym) -> usize {
1059        let admitted = self
1060            .admitted_surbs_per_pseudonym
1061            .get(pseudonym)
1062            .map(|rb| rb.len())
1063            .unwrap_or(0);
1064        let quarantined = self.quarantine_surbs.get(pseudonym).map(|rb| rb.len()).unwrap_or(0);
1065        admitted + quarantined
1066    }
1067
1068    /// Books what a ring-buffer push dropped into the eviction summary, split by what it cost, and the
1069    /// `replaced_shares` a generation change took out of play.
1070    fn record_ring_overflow(&self, outcome: &SurbInsertOutcome, replaced_shares: usize) {
1071        // The total that `num_evicted_surbs` carries upwards, and the Exit books into its flow
1072        // estimate, cannot tell a lost share from a lost return path, and only the former always
1073        // warrants a warning. Recording a count of zero is free, so the usual push, which overflows
1074        // nothing, takes no lock here.
1075        self.stats.record_many(
1076            EvictedCache::RingPlain,
1077            RemovalCause::Size,
1078            outcome.evicted.saturating_sub(outcome.evicted_shares) as u64,
1079        );
1080        self.stats.record_many(
1081            EvictedCache::RingShare,
1082            RemovalCause::Size,
1083            outcome.evicted_shares as u64,
1084        );
1085        self.stats
1086            .record_many(EvictedCache::RingShare, RemovalCause::Replaced, replaced_shares as u64);
1087    }
1088
1089    /// Removes `pseudonym`'s quarantine ring, if it has one, and refunds what it held to the budget.
1090    ///
1091    /// The removal is an `and_compute_with`, not a plain `remove`, because that is what serialises it
1092    /// against [`push_into_quarantine`](Self::push_into_quarantine): moka runs computes on one key one
1093    /// at a time, but a `remove` does not join that queue. With a plain `remove`, a push that had
1094    /// already looked the ring up could land its batch *after* the removal had drained the ring — in a
1095    /// ring no cache holds any more, where no lookup ever finds it. Serialised, a push either finishes
1096    /// before the removal (and its batch leaves with the ring) or starts after it (and creates a fresh
1097    /// ring, which its own post-push re-check then folds).
1098    ///
1099    /// `Op::Remove` is an explicit removal the quarantine listener skips, so the refund is made here.
1100    fn take_quarantine_ring(&self, pseudonym: &HoprPseudonym) -> Option<SurbRingBuffer<HoprSurb>> {
1101        let removed = self.quarantine_surbs.entry_by_ref(pseudonym).and_compute_with(
1102            |entry: Option<moka::Entry<HoprPseudonym, SurbRingBuffer<HoprSurb>>>| match entry {
1103                Some(_) => moka::ops::compute::Op::Remove,
1104                None => moka::ops::compute::Op::Nop,
1105            },
1106        );
1107
1108        match removed {
1109            moka::ops::compute::CompResult::Removed(entry) => {
1110                let ring = entry.into_value();
1111                refund_quarantine_budget(&self.quarantine_budget, ring.len());
1112                Some(ring)
1113            }
1114            _ => None,
1115        }
1116    }
1117
1118    /// Moves everything `pseudonym`'s quarantine ring holds into `admitted`, removing the quarantine
1119    /// ring. Returns what the push into `admitted` did, or `None` if there was nothing to move.
1120    ///
1121    /// The ring is drained as it stands: a promoted SURB already earned its slot, and the push into
1122    /// `admitted` is judged against the admitted ceiling, not the quarantine's.
1123    fn fold_quarantine_into(
1124        &self,
1125        pseudonym: &HoprPseudonym,
1126        admitted: &SurbRingBuffer<HoprSurb>,
1127    ) -> Option<SurbInsertOutcome> {
1128        let (generation, held) = self.take_quarantine_ring(pseudonym)?.take_all();
1129        let (outcome, replaced_shares) = admitted.push_counting(held, generation?);
1130        self.record_ring_overflow(&outcome, replaced_shares);
1131        Some(outcome)
1132    }
1133
1134    /// Pushes a batch into an admitted ring, after folding in whatever a quarantine ring for the same
1135    /// pseudonym still holds.
1136    ///
1137    /// The fold-in is re-done here rather than left to `admit`, because an insert that routed to the
1138    /// quarantine just before `admit` installed this entry can leave a ring behind there — and
1139    /// because `admit` itself must not be called again: it would mint a fresh admission number the
1140    /// manager's token no longer names, leaving the Session's deferred retire matching nothing while
1141    /// the entry it stamped holds a number no retire will ever present.
1142    ///
1143    /// It is also why only `admit` creates an admitted entry: an insert that minted one itself would
1144    /// have no admission number to stamp, and a ring stamped with the sentinel is one no retire ever
1145    /// removes.
1146    ///
1147    /// The outcome adds what the fold-in evicted and superseded to what the push did, as the quarantine
1148    /// arm does: those SURBs were booked when their packets arrived, and the decoder can book their
1149    /// leaving only from this outcome.
1150    fn push_into_admitted(
1151        &self,
1152        pseudonym: &HoprPseudonym,
1153        admitted: &AdmittedRing,
1154        surbs: Vec<(HoprSurbId, HoprSurb)>,
1155        generation: u8,
1156    ) -> SurbInsertOutcome {
1157        let folded = self.fold_quarantine_into(pseudonym, admitted).unwrap_or_default();
1158
1159        let (outcome, replaced_shares) = admitted.push_counting(surbs, generation);
1160        self.record_ring_overflow(&outcome, replaced_shares);
1161        SurbInsertOutcome {
1162            retained: outcome.retained,
1163            evicted: outcome.evicted + folded.evicted,
1164            evicted_shares: outcome.evicted_shares + folded.evicted_shares,
1165            superseded: outcome.superseded + folded.superseded,
1166        }
1167    }
1168
1169    /// Pushes a batch into `pseudonym`'s quarantine ring, creating the ring if it has none, and books
1170    /// the change in the quarantine budget.
1171    ///
1172    /// The push runs inside an `and_compute_with` so it is serialised against
1173    /// [`take_quarantine_ring`](Self::take_quarantine_ring) — see there for the batch a plain lookup
1174    /// would lose. The budget is booked inside the compute too: a promotion queued behind this push
1175    /// refunds what the ring holds as soon as the compute ends, and an increment landing after that
1176    /// refund would count SURBs the quarantine no longer holds. The delta is taken against this
1177    /// ring's own length, read in the same compute, so a push that evicted and re-inserted nets out.
1178    fn push_into_quarantine(
1179        &self,
1180        pseudonym: &HoprPseudonym,
1181        surbs: Vec<(HoprSurbId, HoprSurb)>,
1182        generation: u8,
1183    ) -> SurbInsertOutcome {
1184        let mut pushed = SurbInsertOutcome::default();
1185        let mut replaced_shares = 0;
1186        self.quarantine_surbs.entry_by_ref(pseudonym).and_compute_with(
1187            |entry: Option<moka::Entry<HoprPseudonym, SurbRingBuffer<HoprSurb>>>| {
1188                // The entry's value shares its buffer with the cache's, so a push through it lands in
1189                // the ring the cache holds and the entry is kept as it is. A new ring is pushed into
1190                // before it is put: nothing can see it until the compute ends.
1191                let (ring, op) = match entry {
1192                    Some(entry) => (entry.into_value(), moka::ops::compute::Op::Nop),
1193                    None => {
1194                        let ring = SurbRingBuffer::new(self.cfg.quarantine_rb_capacity);
1195                        (ring.clone(), moka::ops::compute::Op::Put(ring))
1196                    }
1197                };
1198
1199                let before = ring.len();
1200                (pushed, replaced_shares) = ring.push_counting(surbs, generation);
1201                match pushed.retained.checked_sub(before) {
1202                    Some(grown) => {
1203                        self.quarantine_budget
1204                            .fetch_add(grown, std::sync::atomic::Ordering::Relaxed);
1205                    }
1206                    None => refund_quarantine_budget(&self.quarantine_budget, before - pushed.retained),
1207                }
1208                op
1209            },
1210        );
1211
1212        self.record_ring_overflow(&pushed, replaced_shares);
1213        pushed
1214    }
1215
1216    /// Sheds whole quarantine rings until `incoming` more SURBs fit under the quarantine budget, or no
1217    /// ring that holds anything is left. Returns how many rings it shed.
1218    ///
1219    /// The victims are uniformly untrusted, so their order is arbitrary — moka's `iter` gives no order
1220    /// to lean on. Rings a lookup has already emptied are skipped: they free no budget, and choosing
1221    /// them would spend a pass on nothing while rings that do hold SURBs stay put. Each pass sheds a
1222    /// bounded number of rings, so an insert at saturation frees room for several after it rather than
1223    /// draining one ring per insert; passes repeat only while the batch still does not fit, and their
1224    /// number is capped by what the cache can hold, so a counter that drifted above what the rings
1225    /// actually hold costs one sweep of the quarantine, not a loop.
1226    ///
1227    /// The rings are collected before any is removed: moka holds the cache lock for a live `iter`, so
1228    /// a removal inside it would deadlock against itself.
1229    fn drain_quarantine_budget(&self, incoming: usize) -> usize {
1230        const VICTIMS_PER_PASS: usize = 64;
1231        let fits = || {
1232            self.quarantine_budget.load(std::sync::atomic::Ordering::Relaxed) + incoming
1233                <= self.cfg.quarantine_surb_budget
1234        };
1235        let max_passes = self
1236            .cfg
1237            .quarantine_max_pseudonyms
1238            .max(MINIMUM_QUARANTINE_PSEUDONYMS)
1239            .div_ceil(VICTIMS_PER_PASS);
1240
1241        let mut shed = 0;
1242        for _ in 0..max_passes {
1243            if fits() {
1244                break;
1245            }
1246            let victims: Vec<HoprPseudonym> = self
1247                .quarantine_surbs
1248                .iter()
1249                .filter(|(_, ring)| ring.len() > 0)
1250                .take(VICTIMS_PER_PASS)
1251                .map(|(key, _)| *key)
1252                .collect();
1253            if victims.is_empty() {
1254                break;
1255            }
1256            // Removed through the same serialised path as a promotion, so a push racing the drain on a
1257            // victim lands either in the ring being shed (and leaves with it, refunded) or in a fresh
1258            // one — never in a ring the cache no longer holds while the budget still counts it.
1259            for key in &victims {
1260                if self.take_quarantine_ring(key).is_some() {
1261                    shed += 1;
1262                }
1263            }
1264        }
1265        self.quarantine_surbs.run_pending_tasks();
1266        shed
1267    }
1268
1269    /// The quarantine arm of [`SurbStore::insert_surbs`], split out so a test can drive it directly:
1270    /// it is reached when `insert_surbs`' admission lookup found no entry, and the interesting case —
1271    /// `admit` landing between that lookup and the push here — cannot be forced from outside.
1272    ///
1273    /// That case is why the push is followed by a re-check. `admit` installs the admitted entry first
1274    /// and promotes the quarantine ring second, so a batch pushed here either lands before the
1275    /// promotion (and is promoted with the ring) or after it, when the entry is already in place and
1276    /// the re-check below finds it and folds the batch in. Without the re-check the batch would sit in
1277    /// a quarantine ring that `find_surb` no longer consults — it reads the admitted ring once one
1278    /// exists — until a later admitted insert happened to fold it in, or the quarantine's TTI, cap or
1279    /// budget drain discarded it.
1280    fn insert_surbs_into_quarantine(
1281        &self,
1282        pseudonym: &HoprPseudonym,
1283        surbs: Vec<(HoprSurbId, HoprSurb)>,
1284        generation: u8,
1285    ) -> SurbInsertOutcome {
1286        // The quarantine is the only class an unauthenticated peer can write into, so the budget
1287        // applies here and only here. Refusing an admitted batch to protect it would trade live
1288        // PIX shares for untrusted ones.
1289        if self.quarantine_budget.load(std::sync::atomic::Ordering::Relaxed) + surbs.len()
1290            > self.cfg.quarantine_surb_budget
1291        {
1292            let evicted_rings = self.drain_quarantine_budget(surbs.len());
1293
1294            #[cfg(all(feature = "telemetry", not(test)))]
1295            METRIC_SURB_STORE_ADMISSIONS
1296                .increment_by(&[SurbAdmissionEvent::QuarantineEvicted.into()], evicted_rings as u64);
1297            #[cfg(not(all(feature = "telemetry", not(test))))]
1298            let _ = evicted_rings;
1299
1300            // Still over? Then the cache's own bound is the wall and the batch is refused whole:
1301            // it is unadmitted traffic, so turning it away costs return paths, not shares held for
1302            // a Session. `retained` reports what the pseudonym still holds in either class, and
1303            // `evicted_shares` the shares the refused batch actually carried — the caller above
1304            // reads `evicted` as "SURBs that left or never entered the store", which a refusal is.
1305            let over = self.quarantine_budget.load(std::sync::atomic::Ordering::Relaxed) + surbs.len()
1306                > self.cfg.quarantine_surb_budget;
1307            if over {
1308                // Unless the pseudonym was admitted while the drain ran: an admitted batch is never
1309                // refused, so it goes where it now belongs.
1310                if let Some(admitted) = self.admitted_surbs_per_pseudonym.get(pseudonym) {
1311                    return self.insert_surbs_into_admitted(pseudonym, admitted, surbs, generation);
1312                }
1313
1314                #[cfg(all(feature = "telemetry", not(test)))]
1315                METRIC_SURB_STORE_ADMISSIONS.increment_by(&[SurbAdmissionEvent::QuarantineRefused.into()], 1);
1316                tracing::debug!(
1317                    %pseudonym,
1318                    num_surbs = surbs.len(),
1319                    budget = self.cfg.quarantine_surb_budget,
1320                    "refusing unadmitted SURBs: the quarantine SURB budget is exhausted"
1321                );
1322                return SurbInsertOutcome {
1323                    retained: self.ring_len(pseudonym),
1324                    evicted: surbs.len(),
1325                    evicted_shares: surbs.iter().filter(|(_, surb)| surb.ssa_index().is_some()).count(),
1326                    // Refused whole and booked as `evicted` above; the generation rule took nothing.
1327                    superseded: 0,
1328                };
1329            }
1330        }
1331
1332        let pushed = self.push_into_quarantine(pseudonym, surbs, generation);
1333
1334        // The re-check. An `admit` that landed after `insert_surbs`' routing lookup either promoted
1335        // after the push above, taking the batch with the ring, or before it — and then its entry,
1336        // installed ahead of the promotion, is in place by now and the batch is folded in here.
1337        let Some(admitted) = self.admitted_surbs_per_pseudonym.get(pseudonym) else {
1338            return pushed;
1339        };
1340        match self.fold_quarantine_into(pseudonym, &admitted) {
1341            Some(folded) => SurbInsertOutcome {
1342                retained: folded.retained,
1343                evicted: pushed.evicted + folded.evicted,
1344                evicted_shares: pushed.evicted_shares + folded.evicted_shares,
1345                superseded: pushed.superseded + folded.superseded,
1346            },
1347            // Nothing left to fold: `admit`'s own promotion, or a concurrent insert, already moved it.
1348            None => SurbInsertOutcome {
1349                retained: admitted.len(),
1350                ..pushed
1351            },
1352        }
1353    }
1354
1355    /// The admitted arm of [`SurbStore::insert_surbs`], split out so a test can drive it directly:
1356    /// it is reached when `insert_surbs`' admission lookup finds an entry, which is only ever the one
1357    /// `admit` installed — no insert may create one — and cannot be forced from outside.
1358    ///
1359    /// `admitted` is the entry the real `admit` installed, carrying the admission number the
1360    /// SessionManager threads back to `retire`. It is used as it stands rather than `admit` being
1361    /// called again: a second `admit` would mint a fresh number the manager's token no longer names,
1362    /// and the deferred retire would then match nothing, leaking the Session's ring until its teardown
1363    /// never comes. What is re-done here is only the fold-in of a quarantine ring, which an insert
1364    /// that routed there just before `admit` installed this entry can have left behind.
1365    fn insert_surbs_into_admitted(
1366        &self,
1367        pseudonym: &HoprPseudonym,
1368        admitted: AdmittedRing,
1369        surbs: Vec<(HoprSurbId, HoprSurb)>,
1370        generation: u8,
1371    ) -> SurbInsertOutcome {
1372        self.push_into_admitted(pseudonym, &admitted, surbs, generation)
1373    }
1374
1375    /// Whether a stored SURB can still be used to reply: its first relayer must still be payable.
1376    ///
1377    /// A direct return path is exempt — its "first relayer" is the final recipient, which needs no
1378    /// channel (RFC-0003 §3.2, RFC-0006 §6.1). Without that exemption, closing an unrelated channel
1379    /// to a session's originator would discard perfectly good SURBs.
1380    fn is_surb_usable(&self, surb: &HoprSurb) -> bool {
1381        match surb.additional_data_receiver.proof_of_relay_values().chain_length() {
1382            // Direct return path: the "first relayer" is the final recipient, which needs no channel.
1383            1 => true,
1384            // A chain length is hops + 1, so 0 cannot occur on a well-formed SURB. Refuse it rather
1385            // than let a malformed value pass as "direct" and bypass the check below.
1386            //
1387            // The length is an unvalidated byte off a SURB minted by the counterparty, so this is a
1388            // statement about that peer, not a local fault we could act on: `warn`, not `error`.
1389            0 => {
1390                tracing::warn!(
1391                    first_relayer = %surb.first_relayer,
1392                    "refusing a malformed SURB declaring a zero-length return path"
1393                );
1394                false
1395            }
1396            _ => {
1397                let usable = !self.invalidated_relayers.read().contains(&surb.first_relayer);
1398                if !usable {
1399                    tracing::trace!(
1400                        first_relayer = %surb.first_relayer,
1401                        "refusing a SURB whose first relayer is invalidated"
1402                    );
1403                }
1404                usable
1405            }
1406        }
1407    }
1408}
1409
1410impl Default for MemorySurbStore {
1411    fn default() -> Self {
1412        Self::new(SurbStoreConfig::default())
1413    }
1414}
1415
1416impl SurbStore for MemorySurbStore {
1417    #[tracing::instrument(skip_all, level = "trace", fields(?matcher), ret)]
1418    fn find_surb(&self, matcher: SurbMatcher) -> Option<FoundSurb> {
1419        let pseudonym = matcher.pseudonym();
1420        // The admitted ring is consulted first: it is the one an established Session stands behind,
1421        // so a SURB there is worth more than one held on speculation. The quarantine is consulted only
1422        // because a pseudonym can legitimately receive SURBs before its Session is established (probe
1423        // replies, the one-RTT window before `admit` fires) — a hit there is handed out, but it is
1424        // *not* promoted: which pseudonym deserves admission is decided by the Session lifecycle alone,
1425        // and `matcher` names a pseudonym an unauthenticated counterparty chose, so promoting on a pop
1426        // would let that counterparty mint itself into the admitted class.
1427        let is_quarantine = self.admitted_surbs_per_pseudonym.get(&pseudonym).is_none();
1428        let surbs_for_pseudonym = if is_quarantine {
1429            self.quarantine_surbs.get(&pseudonym)?
1430        } else {
1431            // Deref'd to the ring: the caller below sees a `SurbRingBuffer` either way, and the
1432            // admission number riding on the entry is this method's business only insofar as it must
1433            // not touch it — a pop must not disturb the guard the deferred retire checks.
1434            self.admitted_surbs_per_pseudonym.get(&pseudonym)?.ring
1435        };
1436        let held_before = surbs_for_pseudonym.len();
1437
1438        let pop = match matcher {
1439            // SURBs whose return path no longer has a usable first edge are dropped on the way,
1440            // rather than handed out only to have the reply fail to be paid for.
1441            SurbMatcher::Pseudonym(_) => surbs_for_pseudonym
1442                .pop_next_valid(|_, surb| self.is_surb_usable(surb))
1443                .map(|popped_surb| (popped_surb.id, popped_surb.surb, popped_surb.remaining)),
1444            // The following code intentionally only checks the oldest SURB of the tier that would be
1445            // consumed next (share-bearing SURBs first, share-less ones once none are left) and does
1446            // not search the entire RB.
1447            // This is because the exact match use-case is suited only for situations
1448            // when there is a single SURB in the RB.
1449            SurbMatcher::Exact(id) => surbs_for_pseudonym
1450                .pop_one_if_has_id(&id.surb_id())
1451                .map(|popped_surb| (popped_surb.id, popped_surb.surb, popped_surb.remaining)), // = likely 0
1452        };
1453
1454        if is_quarantine {
1455            // A pop is a removal as far as the quarantine budget is concerned, and `pop_next_valid`
1456            // discards rather than skips the SURBs failing the usability test, so the whole delta
1457            // between the lengths before and after is unadmitted SURBs that left the store. The
1458            // accounting must precede the `pop` short-circuit below: a lookup whose SURBs are all
1459            // discarded empties the ring and yields `None`, and those SURBs left the store all the
1460            // same — skipping the decrement there would pin the budget at its cap and refuse every
1461            // later fresh SURB.
1462            let dropped = held_before.saturating_sub(surbs_for_pseudonym.len());
1463            refund_quarantine_budget(&self.quarantine_budget, dropped);
1464        }
1465
1466        let (id, surb, remaining) = pop?;
1467
1468        Some(FoundSurb {
1469            sender_id: HoprSenderId::from_pseudonym_and_id(&pseudonym, id),
1470            surb,
1471            remaining,
1472        })
1473    }
1474
1475    #[tracing::instrument(skip_all, level = "trace", fields(%pseudonym, num_surbs = surbs.len()))]
1476    fn insert_surbs(&self, pseudonym: HoprPseudonym, mut surbs: Vec<(HoprSurbId, HoprSurb)>) -> SurbInsertOutcome {
1477        // A batch is one packet's worth of SURBs, minted by the creator at a single generation, so
1478        // the generation of the first stands for the whole batch. An empty batch carries no
1479        // generation and must not create or disturb the buffer.
1480        let Some(generation) = surbs
1481            .first()
1482            .map(|(_, surb)| surb.additional_data_receiver.generation())
1483        else {
1484            return SurbInsertOutcome {
1485                retained: self.ring_len(&pseudonym),
1486                evicted: 0,
1487                evicted_shares: 0,
1488                superseded: 0,
1489            };
1490        };
1491
1492        // That "single generation" holds by construction only for a batch minted by an honest
1493        // creator: `PacketRouting::ForwardPath` stamps one generation into every SURB it mints. On
1494        // this side the batch is parsed out of a counterparty-controlled payload, so enforce it
1495        // rather than assume it — otherwise a mixed batch smuggles SURBs for a superseded return
1496        // path into a buffer the push below labels with the newer generation, where no later push
1497        // can clear them. The first SURB always survives, so the buffer is never created empty.
1498        let mixed = surbs.len();
1499        surbs.retain(|(_, surb)| surb.additional_data_receiver.generation() == generation);
1500        let dropped = mixed - surbs.len();
1501        if dropped > 0 {
1502            // A statement about the peer that minted the batch, not a local fault: `warn`, not
1503            // `error`. These are not capacity pressure, so they stay out of the `evicted` count; they
1504            // are `superseded` below, because the packet reported them as received and the Exit's flow
1505            // estimate has to see that they never reached the store.
1506            tracing::warn!(
1507                %pseudonym,
1508                dropped,
1509                generation,
1510                "discarding SURBs whose generation disagrees with the rest of their batch"
1511            );
1512        }
1513
1514        // Route on the admitted cache itself: it holds an entry — often an empty ring — for exactly
1515        // as long as a Session stands behind the pseudonym, so this one lookup is both the admission
1516        // test and the source of truth. A separate marker cache would have to be kept in step with
1517        // the ring across evictions and admits, and a desync there either loses a live ring to the
1518        // quarantine's tiny cap or lets a superseded marker resurrect it.
1519        //
1520        // The lookup *takes* the entry rather than inserting one: only `admit` may create an admitted
1521        // entry. `entry_by_ref(...).or_insert_with(...)` would recreate an epoch-0 ring whenever a
1522        // deferred `retire` removed the key between the admission test and the entry lookup, and that
1523        // ring would then never leave by its teardown — `retire` ignores token 0 — so it would leak
1524        // until size eviction. (A successor `admit` re-stamps the epoch and raises the capacity, but
1525        // the entry the retire never names is reason enough to keep an insert out of this cache.)
1526        // An absent entry therefore means the pseudonym is not admitted (or was just retired), and the
1527        // batch belongs to the quarantine like any other unadmitted one — whose arm re-checks this
1528        // lookup after its push, for an `admit` that lands in between.
1529        let mut outcome = if let Some(admitted) = self.admitted_surbs_per_pseudonym.get(&pseudonym) {
1530            self.insert_surbs_into_admitted(&pseudonym, admitted, surbs, generation)
1531        } else {
1532            self.insert_surbs_into_quarantine(&pseudonym, surbs, generation)
1533        };
1534        // The mismatched ones above never entered the buffer either.
1535        outcome.superseded += dropped;
1536        outcome
1537    }
1538
1539    fn tier_lens(&self, pseudonym: &HoprPseudonym) -> Option<(usize, usize)> {
1540        self.admitted_surbs_per_pseudonym
1541            .get(pseudonym)
1542            .map(|rb| rb.tier_lens())
1543            .or_else(|| self.quarantine_surbs.get(pseudonym).map(|rb| rb.tier_lens()))
1544    }
1545
1546    /// Admits `pseudonym` into the store's admitted class, behind an established Session.
1547    ///
1548    /// Called once the Session over the pseudonym is established, and never on a mere packet's say-so,
1549    /// so the admitted class stays out of any unauthenticated peer's reach. `expected_surbs` is the
1550    /// Session's announced SURB target; the store adds its own headroom and floors at
1551    /// `quarantine_rb_capacity` — an unknown target (`0`) is treated as "no announcement" and gets the
1552    /// floor, not a one-SURB ring.
1553    ///
1554    /// Returns the number naming this admission, which the caller threads to
1555    /// [`SurbStore::retire`]. Every call mints a fresh one and invalidates the previous, so a
1556    /// retire issued on behalf of a superseded admission matches nothing — that is the guard that
1557    /// makes the deferred retire safe to schedule.
1558    ///
1559    /// Any quarantine ring for the pseudonym is promoted rather than left behind to expire: the SURBs
1560    /// arrived for this very Session. A ring arrives here only while the pseudonym is unadmitted
1561    /// (`insert_surbs` routes on admission), so an admitted entry this finds already in place is one a
1562    /// previous admission left behind — `insert_surbs` never creates one — and the promotion fills it
1563    /// rather than discarding what it holds.
1564    ///
1565    /// The admitted entry is installed *before* the quarantine ring is promoted, not after. That order
1566    /// is what lets an insert racing this admission re-check after its quarantine push: a push that
1567    /// lands after the promotion can only do so once the entry is already in place, so the insert's
1568    /// re-check finds it and folds the batch in. Promoting first would leave a window — promotion done,
1569    /// entry not yet installed — in which a push and its re-check could both slip through, stranding
1570    /// the batch in a quarantine ring `find_surb` no longer consults.
1571    fn admit(&self, pseudonym: &HoprPseudonym, expected_surbs: usize) -> u64 {
1572        let capacity = self.admitted_ring_capacity(expected_surbs);
1573        // Minted before anything is written, so a retire racing this admit always carries a number
1574        // strictly older than the one being installed here.
1575        let epoch = next_admission_epoch();
1576
1577        // One atomic compute over the key for both halves of the admission — the ring and its number.
1578        // Splitting them (install the ring, then stamp the number) would reopen the very window the
1579        // token exists to close: a deferred retire carrying the *previous* admission's token matches
1580        // the not-yet-restamped entry and removes it, and the stamp then lands on nothing — the new
1581        // Session would go on inserting its SURBs into the small un-admitted quarantine with nothing
1582        // logged anywhere. `and_compute_with` holds the key-level lock across both, the same lock the
1583        // retire's compare-and-remove runs under, so the two cannot interleave.
1584        let stamped = self
1585            .admitted_surbs_per_pseudonym
1586            .entry_by_ref(pseudonym)
1587            .and_compute_with(|entry: Option<moka::Entry<HoprPseudonym, AdmittedRing>>| match entry {
1588                // Re-admitting a pseudonym (a Session reopened on the same one) must not discard what
1589                // the resident ring already holds, and must not replace the entry wholesale either:
1590                // `Replaced` trips the admitted cache's listener, which books it as an eviction the
1591                // ring never actually suffered. Stamping in place changes the number and nothing else,
1592                // and raising the ceiling in place widens the ring to whatever the successor announced
1593                // — a no-op when the successor's target is no larger, since the raise is monotone.
1594                Some(entry) => {
1595                    entry.value().stamp_epoch(epoch);
1596                    entry.value().raise_capacity(capacity);
1597                    moka::ops::compute::Op::Nop
1598                }
1599                // No ring to keep: admit an empty one, so standing is knowable before the first SURB
1600                // arrives, or `insert_surbs` would route the Session's early batches to quarantine.
1601                None => moka::ops::compute::Op::Put(AdmittedRing::new(SurbRingBuffer::new(capacity), epoch)),
1602            });
1603
1604        let resident = match stamped.into_entry() {
1605            // Both arms above leave an entry behind: `Put` inserted it, `Nop` kept the one it found.
1606            Some(entry) => entry.value().ring.clone(),
1607            None => {
1608                // Unreachable by the same argument; reached only if a concurrent retire removed an
1609                // entry this compute had already decided to keep, which the key-level lock rules out.
1610                // Refusing to admit here degrades to the quarantine, which is the safe direction.
1611                tracing::error!(?pseudonym, "an admitted ring vanished while it was being admitted");
1612                return epoch;
1613            }
1614        };
1615
1616        // Promoted only now that the entry is in place — see the method docs for why the order matters.
1617        // The SURBs are folded into whichever ring the compute above left in place, at its admitted
1618        // ceiling: the quarantine ring is drained, not carried over, so its cap goes with it.
1619        if self.fold_quarantine_into(pseudonym, &resident).is_some() {
1620            #[cfg(all(feature = "telemetry", not(test)))]
1621            METRIC_SURB_STORE_ADMISSIONS.increment_by(&[SurbAdmissionEvent::Promoted.into()], 1);
1622        }
1623
1624        #[cfg(all(feature = "telemetry", not(test)))]
1625        METRIC_SURB_STORE_ADMISSIONS.increment_by(&[SurbAdmissionEvent::Admitted.into()], 1);
1626
1627        epoch
1628    }
1629
1630    /// Retires `pseudonym` from the admitted class: its Session is over.
1631    ///
1632    /// Only the admitted class is touched — a rolled-back or unestablished Session's preload SURBs
1633    /// belong to the quarantine, where their short TTI expires them without any teardown bookkeeping.
1634    /// Idempotent: retiring a pseudonym that holds no admitted ring is a no-op.
1635    ///
1636    /// `token` names the admission the teardown is retiring, and the retire is honoured only while it
1637    /// still matches the pseudonym's current one. The retire runs deferred, past the packet pipeline's
1638    /// SURB-resolution window, because the closing Session's own return-routed notification still
1639    /// needs its ring — long enough for a successor Session to have been admitted on the same
1640    /// client-chosen pseudonym. Dropping the successor's ring there would silently degrade its return
1641    /// path with nothing logged anywhere, which is exactly what the token exists to prevent: a stale
1642    /// retire leaves the successor's ring, and its epoch, exactly as they are.
1643    fn retire(&self, pseudonym: &HoprPseudonym, token: u64) {
1644        // `token == 0` never matches: it is what a teardown of a never-admitted Session passes
1645        // through the seam, and no admission mints it.
1646        if token == 0 {
1647            return;
1648        }
1649
1650        // One atomic compute over the key, so the epoch read and the removal cannot be split by a
1651        // successor `admit`: done as a `get` then a conditional `invalidate`, an admit landing between
1652        // the two would leave this retire removing the *successor's* ring. `and_compute_with` holds
1653        // the key-level lock across both, and `Op::Nop` leaves the entry — the successor's ring and
1654        // its number — untouched when the numbers disagree.
1655        let retired = matches!(
1656            self.admitted_surbs_per_pseudonym
1657                .entry_by_ref(pseudonym)
1658                .and_compute_with(|entry: Option<moka::Entry<HoprPseudonym, AdmittedRing>>| match entry {
1659                    // A matching number names this very ring: `admit` stamps the entry only after the
1660                    // ring is in place, under the same key lock this compare runs under. Dropping the
1661                    // entry is the retire.
1662                    Some(entry) if entry.value().epoch() == token => moka::ops::compute::Op::Remove,
1663                    // No ring, or a ring whose number has moved on: the pseudonym was re-admitted since
1664                    // this token was minted, and the live ring is not this retire's to release.
1665                    _ => moka::ops::compute::Op::Nop,
1666                }),
1667            moka::ops::compute::CompResult::Removed(_)
1668        );
1669
1670        if retired {
1671            #[cfg(all(feature = "telemetry", not(test)))]
1672            METRIC_SURB_STORE_ADMISSIONS.increment_by(&[SurbAdmissionEvent::Retired.into()], 1);
1673        } else {
1674            #[cfg(all(feature = "telemetry", not(test)))]
1675            METRIC_SURB_STORE_ADMISSIONS.increment_by(&[SurbAdmissionEvent::RetiredStale.into()], 1);
1676        }
1677    }
1678
1679    /// Total SURBs held across both classes. Test and observability seam, not a hot path: it walks the
1680    /// admitted cache and reads the quarantine budget.
1681    fn surbs_held(&self) -> usize {
1682        // Read the quarantine budget exactly once: it is an atomic that a concurrent insert or refund
1683        // can move between two loads, and deriving the admitted half as `held - quarantined` from two
1684        // separate reads would then underflow. One read makes the two halves consistent by construction.
1685        let quarantined = self.quarantine_budget.load(std::sync::atomic::Ordering::Relaxed);
1686        let admitted = self
1687            .admitted_surbs_per_pseudonym
1688            .iter()
1689            .map(|(_, rb)| rb.len())
1690            .sum::<usize>();
1691
1692        #[cfg(all(feature = "telemetry", not(test)))]
1693        {
1694            METRIC_SURB_STORE_SURBS_HELD.set(&[SurbHeldClass::Admitted.into()], admitted as f64);
1695            METRIC_SURB_STORE_SURBS_HELD.set(&[SurbHeldClass::Quarantine.into()], quarantined as f64);
1696        }
1697
1698        admitted + quarantined
1699    }
1700
1701    #[tracing::instrument(skip_all, level = "trace", fields(?sender_id))]
1702    fn insert_reply_opener(&self, sender_id: HoprSenderId, opener: ReplyOpener) {
1703        let opener_lifetime = self.cfg.reply_opener_lifetime.max(MINIMUM_OPENER_LIFETIME);
1704        let max_openers_per_pseudonym = self.cfg.max_openers_per_pseudonym.max(MINIMUM_OPENERS_PER_PSEUDONYM);
1705        let stats = self.stats.clone();
1706        self.pseudonym_openers
1707            .get_with(sender_id.pseudonym(), move || {
1708                moka::sync::Cache::builder()
1709                    .time_to_live(opener_lifetime)
1710                    // Keep the newest openers, not the stalest. Reply openers are written once and
1711                    // never read before they are used, so under the default TinyLFU policy every
1712                    // entry ties at frequency zero and incumbents win admission: a full cache then
1713                    // freezes the oldest openers and drops every newer one. But the counterparty's
1714                    // SURB ring always hands back the newest SURBs, whose openers are exactly those
1715                    // dropped — so replies stop decrypting once the cache fills. LRU on this
1716                    // write-only workload evicts by insertion order, i.e. it sheds the oldest and
1717                    // keeps the newest, mirroring the SURB ring buffer (and the outer cache).
1718                    .eviction_policy(moka::policy::EvictionPolicy::lru())
1719                    .eviction_listener(move |_id, _opener, cause| stats.record(EvictedCache::ReplyOpener, cause))
1720                    .max_capacity(max_openers_per_pseudonym as u64)
1721                    .build()
1722            })
1723            .insert(sender_id.surb_id(), opener);
1724    }
1725
1726    #[tracing::instrument(skip_all, level = "trace")]
1727    fn invalidate_relayer(&self, relayer: &HoprKeyIdent) {
1728        if self.invalidated_relayers.write().insert(*relayer) {
1729            tracing::info!(
1730                %relayer,
1731                "invalidating stored SURBs whose return path starts with this relayer"
1732            );
1733        }
1734    }
1735
1736    #[tracing::instrument(skip_all, level = "trace")]
1737    fn revalidate_relayer(&self, relayer: &HoprKeyIdent) {
1738        if self.invalidated_relayers.write().remove(relayer) {
1739            tracing::info!(%relayer, "relayer is usable again for SURB return paths");
1740        }
1741    }
1742
1743    #[tracing::instrument(skip_all, level = "trace", fields(?sender_id), ret)]
1744    fn find_reply_opener(&self, sender_id: &HoprSenderId) -> Option<ReplyOpener> {
1745        self.pseudonym_openers
1746            .get(&sender_id.pseudonym())
1747            .and_then(|cache| cache.get(&sender_id.surb_id()))
1748    }
1749
1750    #[tracing::instrument(skip_all, level = "trace", fields(?sender_id))]
1751    fn remove_reply_opener(&self, sender_id: &HoprSenderId) {
1752        if let Some(cache) = self.pseudonym_openers.get(&sender_id.pseudonym()) {
1753            cache.invalidate(&sender_id.surb_id());
1754        }
1755    }
1756
1757    fn current_generation(&self, pseudonym: &HoprPseudonym) -> u8 {
1758        self.generations
1759            .get(pseudonym)
1760            .map(|g| g.load(std::sync::atomic::Ordering::Relaxed))
1761            .unwrap_or(0)
1762    }
1763
1764    #[tracing::instrument(skip_all, level = "trace", fields(%pseudonym), ret)]
1765    fn bump_generation(&self, pseudonym: &HoprPseudonym) -> u8 {
1766        // `fetch_add` returns the previous value; the new generation is one past it. A `u8` serial
1767        // wraps cleanly (255 -> 0) and the replying side compares with RFC-1982 arithmetic.
1768        self.generations
1769            .get_with(*pseudonym, || Arc::new(std::sync::atomic::AtomicU8::new(0)))
1770            .fetch_add(1, std::sync::atomic::Ordering::Relaxed)
1771            .wrapping_add(1)
1772    }
1773}
1774
1775/// Represents a single SURB along with its ID popped from the [`SurbRingBuffer`].
1776#[derive(Debug, Clone)]
1777pub struct PoppedSurb<S> {
1778    /// Complete SURB sender ID.
1779    pub id: HoprSurbId,
1780    /// The popped SURB.
1781    pub surb: S,
1782    /// Number of SURBs left in the RB after the pop.
1783    pub remaining: usize,
1784}
1785
1786/// RFC-1982 serial-number comparison over a `u8` generation: is `a` strictly newer than `b`?
1787///
1788/// SURB generations are minted monotonically by the creator and only ever compared across the two
1789/// adjacent generations that can be in flight at once, so a `u8` serial (window 128) is ample and
1790/// wraps cleanly: 255 → 0 reads as newer.
1791fn generation_is_newer(a: u8, b: u8) -> bool {
1792    a != b && a.wrapping_sub(b) < 128
1793}
1794
1795/// Which SSA the PIX share sealed in a SURB belongs to.
1796///
1797/// This is what lets [`SurbRingBuffer`] tell share-bearing SURBs from share-less ones on insertion. The
1798/// SSA index travels in plaintext in the SURB's receiver-only block, which only the node the SURB was
1799/// sent to can read and no relay ever sees, so classifying on it reveals nothing that node did not
1800/// already hold. Only *whether* there is a share is used for now; the index itself is returned so that a
1801/// finer ordering, or a trace line, can name the SSA without another look into the block.
1802pub trait SurbShareInfo {
1803    /// The SSA index of the share this SURB carries, or `None` for a share-less SURB.
1804    fn ssa_index(&self) -> Option<SsaIndex>;
1805}
1806
1807impl SurbShareInfo for HoprSurb {
1808    fn ssa_index(&self) -> Option<SsaIndex> {
1809        let share = self.additional_data_receiver.encrypted_partial_ssa_share();
1810        // The very test the packet builder applies when it decides whether a reply carries this share
1811        // (`!is_empty()`), so what the store calls share-bearing cannot drift from what the Exit sends.
1812        if share.is_empty() {
1813            None
1814        } else {
1815            share.indices().map(|(ssa_index, _)| ssa_index)
1816        }
1817    }
1818}
1819
1820/// Ring buffer of SURBs and their IDs, all belonging to one pseudonym and therefore identified only
1821/// by [`HoprSurbId`].
1822///
1823/// Backed by two [`VecDeque`] tiers that together are never allowed to exceed `capacity`: a push into
1824/// a full buffer evicts first (see below for which SURB goes). Each tier is first in, first out: a pop
1825/// consumes the oldest SURB of the tier it draws from, and so does an eviction. See [`SurbPopOrder`]
1826/// for why that is the only order.
1827///
1828/// ## Share-bearing SURBs first
1829///
1830/// A PIX share is sealed into a SURB when the Entry mints it, and reaches the Exit's reconstructor only
1831/// when the Exit *uses* that SURB. The Entry emits shares strictly in SSA-index order and has none left
1832/// to seal once the committed cycle is exhausted, so every SURB it mints from then on is share-less. The
1833/// next cycle's shares are minted only after the Exit has requested that cycle, which is to say *behind*
1834/// every share-less SURB minted in between. While the Entry produces SURBs faster than the Exit spends
1835/// them — `max_surbs_per_data_packet > 1` bypasses the balancer's gate, so a 512 B write carries about
1836/// six against the one a reply spends — that share-less backlog grows faster than it drains. In a single
1837/// FIFO queue the next cycle's shares are then reached late or never, and the supervisor closes the
1838/// Session on `RecoveryIdle` (hoprnet#8466).
1839///
1840/// So the buffer keeps two tiers and always hands out the share-bearing one first. [`SurbShareInfo`]
1841/// sorts each SURB into `shares` or `plain` as it arrives, and a pop takes from `shares` for as long as
1842/// it holds anything and from `plain` after that, the oldest SURB of either first. The Entry emits
1843/// shares in SSA-index order, so FIFO inside `shares` is also lowest-SSA-first.
1844///
1845/// Eviction follows the same priority, because a share-less SURB is only a return path while a
1846/// share-bearing one is a return path *and* a share nothing can replace. A full buffer gives up share-less
1847/// SURBs first, oldest first. A share-less newcomer is refused rather than evict a share. Only when
1848/// nothing but shares is held does the oldest share go, as the oldest SURB always used to. A push reports
1849/// how many SURBs it dropped and, of those, how many were shares, so that the loss that matters can be told
1850/// from the routine one (see [`SurbInsertOutcome`]).
1851///
1852/// What this deliberately does *not* do: order shares across SSAs beyond these two tiers, retire the
1853/// leftovers of an already-recovered SSA (the supervisor budgets for those, see its
1854/// `paid_recovery_tail`), or insist that a batch belong to one SSA — a packet's SURBs legitimately
1855/// straddle a cycle boundary, or the step from carrying shares to carrying none.
1856///
1857/// ## Generations: dropping SURBs for a superseded return path
1858///
1859/// A return path that dies deep in a multi-hop route is invisible to this replying side — nothing
1860/// here can tell a stale SURB from a live one. The SURB creator can: it stamps every SURB of a
1861/// batch with a generation (`SurbReceiverInfo::generation`) and bumps it whenever it changes the
1862/// return path. This buffer keeps only the highest generation it has seen: the first push carrying a
1863/// newer generation **clears the buffer wholesale** (both tiers) before inserting, so a return-path
1864/// change takes effect on the very next reply rather than only once the stale SURBs drain — and stale
1865/// SURBs are never handed out. A push carrying an older generation (a late/reordered batch) is
1866/// discarded. Clearing is a per-path-change O(n) sweep, so pops need no per-SURB generation check.
1867///
1868/// ## Why the capacity is a ceiling, not a reservation
1869///
1870/// The deques grow with occupancy rather than being sized at construction. The distinction matters
1871/// because the pseudonym a buffer is filed under is chosen by whoever sent the packet: any
1872/// `HoprPacket::Final` carrying a SURB reaches `insert_surbs`, which mints a buffer for a pseudonym
1873/// it has never seen, with no Session or handshake behind it.
1874///
1875/// A structure that took its whole capacity upfront therefore let an unauthenticated peer reserve
1876/// `rb_capacity` × `size_of::<(HoprSurbId, S)>()` of address space per pseudonym it invented —
1877/// ~16.8 MB each at the default capacity, and `max_pseudonyms` of those. Resident memory was never
1878/// the problem (untouched pages cost nothing), but the reservation is real to anything that
1879/// accounts address space: strict overcommit, `ulimit -v`, `vm.max_map_count`.
1880///
1881/// Growth is geometric and amortised, and a deque never shrinks below its high-water mark, so a
1882/// pseudonym that genuinely fills up still ends at the same footprint — and stops reallocating
1883/// there, however long the steady-state overflow runs. It just has to earn it. Each tier keeps its own
1884/// mark, so a pseudonym that has been filled with share-less SURBs and then with shares holds both:
1885/// at most twice that footprint, and only after the buffer has been filled twice over.
1886#[derive(Debug)]
1887pub struct SurbRingBuffer<S> {
1888    inner: Arc<parking_lot::Mutex<GenerationalBuffer<S>>>,
1889    /// Ceiling on the number of retained SURBs across both tiers; one is dropped (a share-less SURB if
1890    /// there is one) for every SURB that arrives once it is reached.
1891    ///
1892    /// An `Arc<AtomicUsize>`, not a plain field, because a re-admission of the same pseudonym must be
1893    /// able to *raise* the ceiling of the ring already in place — `admit` keeps the resident ring
1894    /// rather than replacing it, and `push` reaches the ring only through `&self`. The `Arc` is what
1895    /// makes the raise visible: `admit`'s `and_compute_with` sees a *clone* of the cache value (moka's
1896    /// `Entry::value` hands back the value it copied), so a raise through that clone would land on a
1897    /// buffer the cache does not hold — the same reason the admission `epoch` is behind an `Arc`. It
1898    /// only ever grows ([`raise_capacity`](Self::raise_capacity) is a `fetch_max`), so a later admission
1899    /// can never narrow a ceiling a live Session is already filling: capacity is monotone, and the ring
1900    /// a successor inherits is at least as wide as the widest target any admission of the pseudonym has
1901    /// asked for.
1902    capacity: Arc<std::sync::atomic::AtomicUsize>,
1903}
1904
1905/// An admitted ring together with the number naming the admission that installed it.
1906///
1907/// The pairing is what a deferred [`SurbStore::retire`] checks: it removes the entry only when its
1908/// token still equals the number stored here, so a retire that arrives after a successor Session was
1909/// admitted on the same pseudonym is a no-op rather than a destruction of the successor's ring. The
1910/// two live in one cache entry so the compare in `retire` and the removal are a single atomic
1911/// operation over the key — split across two caches, an `admit` could land between the compare and
1912/// the removal and the retire would destroy the successor's ring.
1913///
1914/// `epoch` is behind an `Arc` so it can be re-stamped in place: `admit` of a re-admitted pseudonym
1915/// must keep the resident ring (it must not discard what it already holds), and replacing the entry
1916/// wholesale to carry a new number would trip moka's `Replaced` path — which the admitted cache's
1917/// listener books as an eviction the ring never actually suffered. Storing through the `Arc` changes
1918/// only the number, and it happens inside [`SurbStore::admit`]'s `and_compute_with`, under the same
1919/// key-level lock `retire` compares under — so an entry is never observable with one admission's
1920/// ring and a later admission's number, nor with no number at all.
1921#[derive(Clone, Debug)]
1922struct AdmittedRing {
1923    ring: SurbRingBuffer<HoprSurb>,
1924    /// The number [`next_admission_epoch`] minted for the admission that installed `ring`, or
1925    /// re-stamped it on a re-admission. Never zero: zero is the token a teardown of a never-admitted
1926    /// Session presents, and it must match no entry.
1927    epoch: Arc<std::sync::atomic::AtomicU64>,
1928}
1929
1930impl AdmittedRing {
1931    fn new(ring: SurbRingBuffer<HoprSurb>, epoch: u64) -> Self {
1932        Self {
1933            ring,
1934            epoch: Arc::new(std::sync::atomic::AtomicU64::new(epoch)),
1935        }
1936    }
1937
1938    fn epoch(&self) -> u64 {
1939        self.epoch.load(std::sync::atomic::Ordering::Relaxed)
1940    }
1941
1942    fn stamp_epoch(&self, epoch: u64) {
1943        self.epoch.store(epoch, std::sync::atomic::Ordering::Relaxed);
1944    }
1945}
1946
1947impl std::ops::Deref for AdmittedRing {
1948    type Target = SurbRingBuffer<HoprSurb>;
1949
1950    fn deref(&self) -> &Self::Target {
1951        &self.ring
1952    }
1953}
1954
1955/// The mutex-protected state of a [`SurbRingBuffer`]: the SURBs, in their two tiers, and the highest
1956/// generation seen.
1957///
1958/// All of it lives under one lock so that clearing both tiers and advancing the generation on a newer
1959/// batch is atomic against a concurrent pop, and so that the combined length the capacity bounds is
1960/// never seen or changed half-way.
1961#[derive(Debug)]
1962struct GenerationalBuffer<S> {
1963    /// SURBs carrying a PIX share, in insertion order. The Entry emits shares in SSA-index order, so
1964    /// FIFO here is also lowest-SSA-first.
1965    shares: VecDeque<(HoprSurbId, S)>,
1966    /// SURBs carrying no share: pure return paths.
1967    plain: VecDeque<(HoprSurbId, S)>,
1968    /// Highest generation seen; `None` until the first push.
1969    generation: Option<u8>,
1970}
1971
1972impl<S> GenerationalBuffer<S> {
1973    /// SURBs held across both tiers: the quantity the capacity bounds.
1974    fn len(&self) -> usize {
1975        self.shares.len() + self.plain.len()
1976    }
1977
1978    /// Drops every SURB of both tiers.
1979    fn clear(&mut self) {
1980        self.shares.clear();
1981        self.plain.clear();
1982    }
1983
1984    /// The tier a pop takes from: share-bearing SURBs for as long as there are any, share-less ones only
1985    /// once there are none. The single place that priority is decided, so peeking and popping — and
1986    /// with them the exact-ID pop — cannot disagree about which SURB is next.
1987    fn next_tier(&self) -> &VecDeque<(HoprSurbId, S)> {
1988        if self.shares.is_empty() {
1989            &self.plain
1990        } else {
1991            &self.shares
1992        }
1993    }
1994
1995    /// As [`next_tier`](Self::next_tier), for removing from it.
1996    fn next_tier_mut(&mut self) -> &mut VecDeque<(HoprSurbId, S)> {
1997        if self.shares.is_empty() {
1998            &mut self.plain
1999        } else {
2000            &mut self.shares
2001        }
2002    }
2003
2004    /// The SURB the next pop would take: the oldest of the next tier. Peeking and popping both go
2005    /// through [`next_tier`](Self::next_tier), so they stay in step.
2006    fn peek_next(&self) -> Option<&(HoprSurbId, S)> {
2007        self.next_tier().front()
2008    }
2009
2010    /// Removes and returns the oldest SURB of the next tier.
2011    fn pop_next(&mut self) -> Option<(HoprSurbId, S)> {
2012        self.next_tier_mut().pop_front()
2013    }
2014
2015    /// Makes room in a full buffer for one more SURB by evicting the oldest share-less one.
2016    ///
2017    /// Failing that, the oldest share-bearing one goes if the newcomer carries a share too. A share-less
2018    /// newcomer is turned away instead — a return path is not worth a share nothing can replace — and
2019    /// [`MadeRoom::Refused`] says so: there is no room for it, and the caller must not insert it.
2020    ///
2021    /// What happened is returned rather than just whether there is room, because the cost differs: a
2022    /// share-less SURB is only a lost return path, a share-bearing one is a share nothing can replace.
2023    fn make_room_for(&mut self, newcomer_carries_share: bool) -> MadeRoom {
2024        if self.plain.pop_front().is_some() {
2025            MadeRoom::EvictedPlain
2026        } else if newcomer_carries_share && self.shares.pop_front().is_some() {
2027            MadeRoom::EvictedShare
2028        } else {
2029            MadeRoom::Refused
2030        }
2031    }
2032}
2033
2034/// What [`GenerationalBuffer::make_room_for`] did to a full buffer.
2035#[derive(Clone, Copy, Debug, PartialEq, Eq)]
2036enum MadeRoom {
2037    /// The oldest share-less SURB was evicted; the newcomer may be inserted.
2038    EvictedPlain,
2039    /// The oldest share-bearing SURB was evicted, and its PIX share with it; the newcomer, which carries
2040    /// a share too, may be inserted.
2041    EvictedShare,
2042    /// Nothing was evicted: the buffer holds nothing but shares and the newcomer carries none. There is
2043    /// no room for it, and it must not be inserted.
2044    Refused,
2045}
2046
2047impl<S> SurbRingBuffer<S> {
2048    /// Creates a buffer holding at most `capacity` (min 1, so a push is never a no-op) SURBs, popped
2049    /// oldest first within each tier.
2050    pub fn new(capacity: usize) -> Self {
2051        Self {
2052            inner: Arc::new(parking_lot::Mutex::new(GenerationalBuffer {
2053                shares: VecDeque::new(),
2054                plain: VecDeque::new(),
2055                generation: None,
2056            })),
2057            // A zero capacity would make the eviction below pop from an empty buffer and then push
2058            // past the bound. Callers already clamp to `MIN_SURB_RB_CAPACITY`; this is belt-and-braces.
2059            capacity: Arc::new(std::sync::atomic::AtomicUsize::new(capacity.max(1))),
2060        }
2061    }
2062
2063    /// The ceiling on how many SURBs this buffer retains.
2064    pub fn capacity(&self) -> usize {
2065        self.capacity.load(std::sync::atomic::Ordering::Relaxed)
2066    }
2067
2068    /// Raises this buffer's ceiling to at least `to` retained SURBs, never lowering it.
2069    ///
2070    /// Two callers raise a ceiling, and both are about a target the ring was not sized for:
2071    ///
2072    /// * [`SurbStore::admit`], when a pseudonym is re-admitted. It keeps the resident ring rather than replacing it (a
2073    ///   `Put` of a fresh ring would trip the admitted cache's `Replaced` listener and be booked as an eviction the
2074    ///   ring never suffered), but the successor Session may have announced a larger SURB target than its predecessor.
2075    /// * [`MemorySurbStore::raise_admitted_capacity`], when a live peer raises its announced target mid-Session and
2076    ///   says so in a keep-alive.
2077    ///
2078    /// Without this the resident ring would keep the smaller ceiling for the Session's whole
2079    /// lifetime, and once its balancer filled past it, `push` would evict — losing PIX shares
2080    /// permanently, with nothing but an `evicted` count to show for it.
2081    ///
2082    /// The raise is monotone on purpose. Narrowing on a re-admission would strand SURBs a live Session
2083    /// may already have inserted and would make the ceiling depend on admission order; `fetch_max`
2084    /// makes the effective ceiling the largest target any admission of the pseudonym has requested.
2085    /// A concurrent `push` racing the raise simply reads whichever ceiling it sees: growing it can only
2086    /// turn a would-be eviction into a clean insert.
2087    fn raise_capacity(&self, to: usize) {
2088        self.capacity.fetch_max(to.max(1), std::sync::atomic::Ordering::Relaxed);
2089    }
2090}
2091
2092/// A second handle on the same buffer, for the moka caches that require `Clone` on their values.
2093///
2094/// Deliberately not a derived `Clone` and not a deep copy: it shares the inner lock and the capacity
2095/// `Arc`, so a cloned handle and its original see the same SURBs and the same bound. Moving SURBs into
2096/// a ring with a different ceiling is a [`take_all`](SurbRingBuffer::take_all) and a push.
2097impl<S> Clone for SurbRingBuffer<S> {
2098    fn clone(&self) -> Self {
2099        Self {
2100            inner: Arc::clone(&self.inner),
2101            capacity: Arc::clone(&self.capacity),
2102        }
2103    }
2104}
2105
2106impl<S> SurbRingBuffer<S> {
2107    /// Removes every SURB held and returns them with the generation they were pushed at.
2108    ///
2109    /// Used to move a ring between the store's two classes: the caller pushes the returned batch into
2110    /// the destination ring, whose own generation logic then decides how the two merge (append, supersede
2111    /// or discard). The returned order is pop order — share-bearing SURBs first, each tier oldest
2112    /// first — not the arrival order, which is the order that matters to a consumer.
2113    fn take_all(&self) -> (Option<u8>, Vec<(HoprSurbId, S)>) {
2114        let mut inner = self.inner.lock();
2115        let generation = inner.generation;
2116        let shares = std::mem::take(&mut inner.shares);
2117        let plain = std::mem::take(&mut inner.plain);
2118        (generation, shares.into_iter().chain(plain).collect())
2119    }
2120
2121    /// Pushes all SURBs of one batch, stamped with `generation`, evicting past capacity.
2122    ///
2123    /// A batch is minted at a single generation by the creator (one packet's worth of SURBs), so a
2124    /// single `generation` covers the whole `surbs` iterator. Relative to the highest generation
2125    /// seen so far:
2126    /// - **newer** → both tiers are cleared before inserting, so SURBs for the superseded return path are dropped at
2127    ///   once rather than lingering until they drain;
2128    /// - **equal** → the batch is appended (an ordinary refill);
2129    /// - **older** → the batch is discarded as a late/reordered leftover.
2130    ///
2131    /// Each SURB is sorted into the share-bearing or the share-less tier by [`SurbShareInfo`]. Once at
2132    /// capacity, every one that arrives costs the buffer one SURB, share-less before share-bearing:
2133    /// - if a share-less SURB is held, the oldest of them is evicted;
2134    /// - else, a share-less newcomer is refused: it is only a return path, and a share-bearing SURB is that plus a
2135    ///   share nothing can replace;
2136    /// - else, only shares are held and the newcomer carries one too, so the oldest share-bearing SURB is evicted.
2137    ///
2138    /// A refused newcomer counts as `evicted` all the same: it is a SURB the buffer had no room for. Under
2139    /// PIX an evicted share-bearing SURB is a lost SSA share, not merely a lost SURB — see
2140    /// [`SurbStoreConfig::rb_capacity`] — so those are counted on their own, as `evicted_shares`: the
2141    /// exact number of shares the push lost to overflow, a subset of `evicted`.
2142    ///
2143    /// Returns what the push did; the eviction count is what lets a caller notice the overflow at
2144    /// all, since dropping a SURB is otherwise indistinguishable from a clean insert.
2145    /// It counts *capacity* overflow only: SURBs dropped because a newer generation superseded them
2146    /// were already unusable, and reporting them as pressure would ask the creator to slow down
2147    /// because it re-planned its own return path. They are reported separately, as
2148    /// [`superseded`](SurbInsertOutcome::superseded): the whole of what a newer generation cleared, or
2149    /// the whole of an older-generation batch that was refused. The caller that tracks what the buffer
2150    /// holds adds the two, so that `retained` and its own count of what was received agree.
2151    ///
2152    /// Also returns how many share-carrying SURBs the generation rule took out of play: the shares a newer
2153    /// generation cleared, or those of an older-generation batch it refused.
2154    fn push_counting<I: IntoIterator<Item = (HoprSurbId, S)>>(
2155        &self,
2156        surbs: I,
2157        generation: u8,
2158    ) -> (SurbInsertOutcome, usize)
2159    where
2160        S: SurbShareInfo,
2161    {
2162        let mut inner = self.inner.lock();
2163        let mut superseded = 0;
2164        let mut replaced_shares = 0;
2165
2166        match inner.generation {
2167            Some(current) if generation == current => {} // ordinary refill: append below
2168            Some(current) if generation_is_newer(generation, current) => {
2169                // Return path changed: everything held is for the superseded path. Drop it wholesale
2170                // so the newer batch is all that remains and the next reply uses the live path.
2171                superseded = inner.len();
2172                replaced_shares = inner.shares.len();
2173                inner.clear();
2174                inner.generation = Some(generation);
2175            }
2176            Some(_) => {
2177                // Older than what we already hold: a late or reordered batch for a path the creator
2178                // has already moved on from. Discard it rather than reintroduce stale SURBs.
2179                let (refused, shares) = surbs.into_iter().fold((0, 0), |(all, shares), (_, surb)| {
2180                    (all + 1, shares + surb.ssa_index().is_some() as usize)
2181                });
2182                let outcome = SurbInsertOutcome {
2183                    retained: inner.len(),
2184                    evicted: 0,
2185                    evicted_shares: 0,
2186                    superseded: refused,
2187                };
2188                return (outcome, shares);
2189            }
2190            None => inner.generation = Some(generation),
2191        }
2192
2193        // Read the ceiling once per push: a concurrent re-admission can only raise it, and taking one
2194        // snapshot keeps every element of this batch judged against the same bound.
2195        let capacity = self.capacity.load(std::sync::atomic::Ordering::Relaxed);
2196
2197        let mut evicted = 0;
2198        let mut evicted_shares = 0;
2199        for (id, surb) in surbs {
2200            let carries_share = surb.ssa_index().is_some();
2201
2202            // Make room before inserting, so the length never exceeds the ceiling and the backing
2203            // allocations stop growing once their high-water marks are reached. Either a resident makes
2204            // way or the newcomer is turned away; both are one SURB dropped for want of room.
2205            if inner.len() >= capacity {
2206                evicted += 1;
2207                match inner.make_room_for(carries_share) {
2208                    MadeRoom::EvictedPlain => {}
2209                    MadeRoom::EvictedShare => evicted_shares += 1,
2210                    MadeRoom::Refused => continue,
2211                }
2212            }
2213
2214            let tier = if carries_share {
2215                &mut inner.shares
2216            } else {
2217                &mut inner.plain
2218            };
2219            tier.push_back((id, surb));
2220        }
2221        let outcome = SurbInsertOutcome {
2222            retained: inner.len(),
2223            evicted,
2224            evicted_shares,
2225            superseded,
2226        };
2227        (outcome, replaced_shares)
2228    }
2229
2230    /// [`push_counting`](Self::push_counting) without the share count, for tests.
2231    #[cfg(test)]
2232    pub fn push<I: IntoIterator<Item = (HoprSurbId, S)>>(&self, surbs: I, generation: u8) -> SurbInsertOutcome
2233    where
2234        S: SurbShareInfo,
2235    {
2236        self.push_counting(surbs, generation).0
2237    }
2238
2239    /// Pops the next SURB that `is_valid` accepts: a share-bearing one while any is held, the oldest of
2240    /// each tier first.
2241    ///
2242    /// **Destructive:** rejected entries are discarded, not skipped, so an unusable SURB neither is
2243    /// handed out nor blocks those behind it. Pass only a validity test — a selective predicate
2244    /// (say, a routing preference) would drain the buffer. `None` once it is exhausted without a
2245    /// match.
2246    ///
2247    /// `is_valid` runs *outside* the lock: it is caller-supplied and may take locks of its own, so
2248    /// calling it inside the critical section would invite lock-order inversion.
2249    pub fn pop_next_valid<F>(&self, is_valid: F) -> Option<PoppedSurb<S>>
2250    where
2251        F: Fn(&HoprSurbId, &S) -> bool,
2252    {
2253        loop {
2254            let (id, surb, remaining) = {
2255                let mut inner = self.inner.lock();
2256                let (id, surb) = inner.pop_next()?;
2257                (id, surb, inner.len())
2258            };
2259
2260            if is_valid(&id, &surb) {
2261                return Some(PoppedSurb { id, surb, remaining });
2262            }
2263        }
2264    }
2265
2266    /// Number of SURBs currently held, across both tiers.
2267    fn len(&self) -> usize {
2268        self.inner.lock().len()
2269    }
2270
2271    /// Number of SURBs currently held in each tier, as `(share-bearing, share-less)`: [`len`](Self::len)
2272    /// split the way a pop sees it, share-bearing first. Both are read under one lock, so they are a
2273    /// consistent pair.
2274    fn tier_lens(&self) -> (usize, usize) {
2275        let inner = self.inner.lock();
2276        (inner.shares.len(), inner.plain.len())
2277    }
2278
2279    /// Pops the next SURB (the one [`pop_next_valid`](Self::pop_next_valid) would take first) only if it has
2280    /// the given ID.
2281    pub fn pop_one_if_has_id(&self, id: &HoprSurbId) -> Option<PoppedSurb<S>> {
2282        let mut inner = self.inner.lock();
2283
2284        if inner.peek_next().is_some_and(|(surb_id, _)| surb_id == id) {
2285            let (id, surb) = inner.pop_next()?;
2286            Some(PoppedSurb {
2287                id,
2288                surb,
2289                remaining: inner.len(),
2290            })
2291        } else {
2292            None
2293        }
2294    }
2295}
2296
2297#[cfg(test)]
2298mod tests {
2299    use std::sync::atomic::{AtomicU64, Ordering};
2300
2301    use anyhow::Context;
2302    use hopr_api::types::{
2303        crypto::{crypto_traits::Randomizable, prelude::SecretKey16},
2304        primitive::prelude::BytesRepresentable,
2305    };
2306    use hopr_crypto_packet::sphinx::prelude::SphinxHeaderSpec;
2307    use rstest::rstest;
2308
2309    use super::*;
2310
2311    impl<S> SurbRingBuffer<S> {
2312        /// Pops the next SURB regardless of validity — the buffer-ordering tests below are about
2313        /// which end is consumed, not about which SURBs are usable.
2314        fn pop_any(&self) -> Option<PoppedSurb<S>> {
2315            self.pop_next_valid(|_, _| true)
2316        }
2317
2318        /// Snapshot of the highest generation the buffer has seen (test-only accessor).
2319        fn generation(&self) -> Option<u8> {
2320            self.inner.lock().generation
2321        }
2322
2323        /// Slots allocated across both tiers (test-only accessor).
2324        fn allocated(&self) -> usize {
2325            let inner = self.inner.lock();
2326            inner.shares.capacity() + inner.plain.capacity()
2327        }
2328    }
2329
2330    /// The ordering and accounting tests below push bare integers where only the buffer mechanics
2331    /// matter; they stand in for SURBs that carry no PIX share.
2332    impl SurbShareInfo for i32 {
2333        fn ssa_index(&self) -> Option<SsaIndex> {
2334            None
2335        }
2336    }
2337
2338    impl SurbShareInfo for u64 {
2339        fn ssa_index(&self) -> Option<SsaIndex> {
2340            None
2341        }
2342    }
2343
2344    /// Builds a SURB with the given first relayer, PoR chain length, and batch generation.
2345    ///
2346    /// Only those fields are read by the store, so the SURB is assembled straight from its wire
2347    /// layout — `first_relayer | alpha | header | sender_key | additional_data_receiver` — whose
2348    /// parser performs no cryptographic validation. That avoids a full Sphinx key exchange per
2349    /// fixture and keeps the fields exactly controllable.
2350    fn surb_gen(first_relayer: HoprKeyIdent, chain_length: u8, generation: u8) -> anyhow::Result<HoprSurb> {
2351        let mut bytes = vec![0u8; HoprSurb::SIZE];
2352
2353        let key_id_size = HoprSphinxHeaderSpec::KEY_ID_SIZE.get();
2354        bytes[..key_id_size].copy_from_slice(first_relayer.as_ref());
2355
2356        // The chain length is the leading byte of the receiver's proof-of-relay values, which lead
2357        // the trailing `additional_data_receiver` block; the generation is that block's last byte.
2358        bytes[HoprSurb::SIZE - HoprSphinxHeaderSpec::SURB_RECEIVER_DATA_SIZE] = chain_length;
2359        bytes[HoprSurb::SIZE - 1] = generation;
2360
2361        let surb = HoprSurb::try_from(bytes.as_slice())?;
2362
2363        // Guard the hand-rolled layout: a wrong offset would silently yield the wrong field and make
2364        // the assertions below pass for the wrong reason.
2365        assert_eq!(first_relayer, surb.first_relayer, "fixture: wrong first relayer");
2366        assert_eq!(
2367            chain_length,
2368            surb.additional_data_receiver.proof_of_relay_values().chain_length(),
2369            "fixture: wrong chain length"
2370        );
2371        assert_eq!(
2372            generation,
2373            surb.additional_data_receiver.generation(),
2374            "fixture: wrong generation"
2375        );
2376
2377        Ok(surb)
2378    }
2379
2380    /// A generation-0 SURB, for tests that do not exercise generations.
2381    fn surb_via(first_relayer: HoprKeyIdent, chain_length: u8) -> anyhow::Result<HoprSurb> {
2382        surb_gen(first_relayer, chain_length, 0)
2383    }
2384
2385    /// A return path with one intermediate relayer: `me -> relayer -> recipient`.
2386    const TWO_HOP: u8 = 2;
2387    /// A return path straight to the recipient, which needs no payment channel.
2388    const DIRECT: u8 = 1;
2389
2390    /// A two-hop, generation-0 SURB that carries the PIX share of SSA `ssa_index`, which must be non-zero
2391    /// (a zero index is what marks a share-less SURB).
2392    ///
2393    /// The share block sits directly before the trailing generation byte of the receiver-only data, laid
2394    /// out `ssa_index: u32 BE | poly_index: u16 BE | scalar`. The store reads only the SSA index, so that is
2395    /// the only part written; the polynomial index and the scalar stay zero. Like [`surb_gen`], the SURB is
2396    /// built from its wire layout, whose parser performs no cryptographic validation.
2397    fn surb_share(first_relayer: HoprKeyIdent, ssa_index: u32) -> anyhow::Result<HoprSurb> {
2398        let ssa = SsaIndex::new(ssa_index).context("fixture: the SSA index must be non-zero")?;
2399
2400        let mut bytes = surb_via(first_relayer, TWO_HOP)?.into_boxed().into_vec();
2401        let share_at = HoprSurb::SIZE - 1 - HoprEncryptedPartialSsaShare::SIZE;
2402        bytes[share_at..share_at + size_of::<SsaIndex>()].copy_from_slice(&ssa.get().to_be_bytes());
2403
2404        let surb = HoprSurb::try_from(bytes.as_slice())?;
2405
2406        // Guard the hand-rolled layout, as `surb_gen` does: a wrong offset would silently yield a
2407        // share-less SURB, or the wrong SSA, and make the tests below pass for the wrong reason.
2408        let share = surb.additional_data_receiver.encrypted_partial_ssa_share();
2409        assert!(!share.is_empty(), "fixture: the share must not read as empty");
2410        assert_eq!(
2411            Some((ssa, 0)),
2412            share.indices(),
2413            "fixture: wrong SSA or polynomial index"
2414        );
2415        assert_eq!(first_relayer, surb.first_relayer, "fixture: wrong first relayer");
2416        assert_eq!(
2417            0,
2418            surb.additional_data_receiver.generation(),
2419            "fixture: wrong generation"
2420        );
2421
2422        Ok(surb)
2423    }
2424
2425    /// A share-less `(id, SURB)` pair for the tier tests. The id is `[n; 8]`, so `n` names the entry in
2426    /// assertions (see [`drain_ids`]).
2427    fn plain_surb(n: u8) -> anyhow::Result<(HoprSurbId, HoprSurb)> {
2428        Ok(([n; 8], surb_via(HoprKeyIdent::from(1u32), TWO_HOP)?))
2429    }
2430
2431    /// As [`plain_surb`], but carrying the share of SSA `n` (so `n` must be at least 1).
2432    fn share_surb(n: u8) -> anyhow::Result<(HoprSurbId, HoprSurb)> {
2433        Ok(([n; 8], surb_share(HoprKeyIdent::from(1u32), u32::from(n))?))
2434    }
2435
2436    /// Pops everything left, regardless of validity, and names each entry by its repeated id byte.
2437    fn drain_ids(rb: &SurbRingBuffer<HoprSurb>) -> Vec<u8> {
2438        std::iter::from_fn(|| rb.pop_any().map(|popped| popped.id[0])).collect()
2439    }
2440
2441    #[test]
2442    fn memory_surb_store_should_skip_surbs_whose_first_relayer_was_invalidated() -> anyhow::Result<()> {
2443        let (dead, alive) = (HoprKeyIdent::from(1u32), HoprKeyIdent::from(2u32));
2444
2445        let store = MemorySurbStore::default();
2446        let pseudonym = HoprPseudonym::random();
2447
2448        // Two SURBs return via the dead relay, one via a healthy one; all are two-hop.
2449        store.insert_surbs(
2450            pseudonym,
2451            vec![
2452                ([1u8; 8], surb_via(dead, TWO_HOP)?),
2453                ([2u8; 8], surb_via(dead, TWO_HOP)?),
2454                ([3u8; 8], surb_via(alive, TWO_HOP)?),
2455            ],
2456        );
2457
2458        store.invalidate_relayer(&dead);
2459
2460        let found = store
2461            .find_surb(SurbMatcher::Pseudonym(pseudonym))
2462            .ok_or(anyhow::anyhow!("expected a usable SURB"))?;
2463        assert_eq!([3u8; 8], found.sender_id.surb_id(), "must skip past the dead relayer");
2464        assert_eq!(
2465            0, found.remaining,
2466            "the invalidated SURBs must be discarded, not left behind"
2467        );
2468
2469        assert!(
2470            store.find_surb(SurbMatcher::Pseudonym(pseudonym)).is_none(),
2471            "no usable SURB should remain"
2472        );
2473
2474        Ok(())
2475    }
2476
2477    #[test]
2478    fn memory_surb_store_should_not_invalidate_surbs_with_a_direct_return_path() -> anyhow::Result<()> {
2479        // A single-element path means the "first relayer" is the final recipient, which needs no
2480        // payment channel — closing a channel to it must not discard the SURB.
2481        let recipient = HoprKeyIdent::from(1u32);
2482
2483        let store = MemorySurbStore::default();
2484        let pseudonym = HoprPseudonym::random();
2485
2486        store.insert_surbs(pseudonym, vec![([7u8; 8], surb_via(recipient, DIRECT)?)]);
2487        store.invalidate_relayer(&recipient);
2488
2489        let found = store
2490            .find_surb(SurbMatcher::Pseudonym(pseudonym))
2491            .ok_or(anyhow::anyhow!("a direct-return-path SURB must stay usable"))?;
2492        assert_eq!([7u8; 8], found.sender_id.surb_id());
2493
2494        Ok(())
2495    }
2496
2497    #[test]
2498    fn memory_surb_store_should_reject_a_surb_with_a_malformed_chain_length() -> anyhow::Result<()> {
2499        // A chain length is hops + 1, so 0 is malformed. It must not pass as "direct" and thereby
2500        // skip the invalidation check.
2501        let relayer = HoprKeyIdent::from(1u32);
2502
2503        let store = MemorySurbStore::default();
2504        let pseudonym = HoprPseudonym::random();
2505
2506        store.insert_surbs(pseudonym, vec![([5u8; 8], surb_via(relayer, 0)?)]);
2507        store.invalidate_relayer(&relayer);
2508
2509        assert!(store.find_surb(SurbMatcher::Pseudonym(pseudonym)).is_none());
2510
2511        Ok(())
2512    }
2513
2514    #[test]
2515    fn memory_surb_store_should_make_a_relayer_usable_again_after_revalidation() -> anyhow::Result<()> {
2516        let relayer = HoprKeyIdent::from(1u32);
2517
2518        let store = MemorySurbStore::default();
2519        let pseudonym = HoprPseudonym::random();
2520
2521        store.insert_surbs(pseudonym, vec![([9u8; 8], surb_via(relayer, TWO_HOP)?)]);
2522
2523        store.invalidate_relayer(&relayer);
2524        store.revalidate_relayer(&relayer);
2525
2526        let found = store
2527            .find_surb(SurbMatcher::Pseudonym(pseudonym))
2528            .ok_or(anyhow::anyhow!("expected the revalidated SURB"))?;
2529        assert_eq!([9u8; 8], found.sender_id.surb_id());
2530
2531        Ok(())
2532    }
2533
2534    #[test]
2535    fn surb_store_config_should_default_to_fifo() {
2536        assert_eq!(SurbPopOrder::Fifo, SurbStoreConfig::default().pop_order);
2537        assert_eq!(SurbPopOrder::Fifo, SurbPopOrder::default());
2538    }
2539
2540    /// LIFO was removed because PIX cannot work with it, so asking for it must be an error rather than
2541    /// a quiet fall back to FIFO.
2542    #[test]
2543    fn surb_pop_order_should_reject_lifo() -> anyhow::Result<()> {
2544        use std::str::FromStr;
2545
2546        assert_eq!(
2547            SurbPopOrder::Fifo,
2548            SurbPopOrder::from_str("fifo").context("fifo must still parse")?
2549        );
2550        assert!(
2551            SurbPopOrder::from_str("lifo").is_err(),
2552            "LIFO was removed, so it must no longer parse"
2553        );
2554
2555        Ok(())
2556    }
2557
2558    /// The configuration path: `pop_order: lifo` fails to load as an unknown variant, while `fifo`,
2559    /// which existing configurations spell out, still loads. The config is deserialized from a map,
2560    /// which is all a configuration file is to serde, so no data-format crate is needed.
2561    #[cfg(feature = "serde")]
2562    #[test]
2563    fn surb_store_config_should_reject_a_lifo_pop_order() -> anyhow::Result<()> {
2564        use serde::{
2565            Deserialize,
2566            de::value::{Error, MapDeserializer},
2567        };
2568
2569        let load = |pop_order: &'static str| {
2570            SurbStoreConfig::deserialize(MapDeserializer::<_, Error>::new([("pop_order", pop_order)].into_iter()))
2571        };
2572
2573        assert_eq!(
2574            SurbPopOrder::Fifo,
2575            load("fifo").context("fifo must still load")?.pop_order
2576        );
2577
2578        let Err(error) = load("lifo") else {
2579            anyhow::bail!("LIFO was removed, so a config asking for it must not load");
2580        };
2581        assert!(
2582            error.to_string().contains("unknown variant `lifo`"),
2583            "unexpected error: {error}"
2584        );
2585
2586        Ok(())
2587    }
2588
2589    /// Eviction removes the oldest, so the surviving set is {2,3,4}, which is then consumed oldest
2590    /// first (all within one generation).
2591    #[test]
2592    fn surb_ring_buffer_should_drop_oldest_items_when_capacity_is_reached() -> anyhow::Result<()> {
2593        let rb = SurbRingBuffer::new(3);
2594        rb.push([([1u8; 8], 0)], 0);
2595        rb.push([([2u8; 8], 0)], 0);
2596        rb.push([([3u8; 8], 0)], 0);
2597        rb.push([([4u8; 8], 0)], 0);
2598
2599        let expected: [HoprSurbId; 3] = [[2u8; 8], [3u8; 8], [4u8; 8]];
2600        for (i, expected_id) in expected.into_iter().enumerate() {
2601            let popped = rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?;
2602            assert_eq!(expected_id, popped.id, "unexpected id at index {i}");
2603            assert_eq!(expected.len() - 1 - i, popped.remaining, "unexpected remaining");
2604        }
2605
2606        assert!(rb.pop_any().is_none(), "buffer should be drained");
2607
2608        Ok(())
2609    }
2610
2611    /// Two SURBs pushed as {1, 2} are handed out 1 then 2 — and the same order holds for a fresh
2612    /// batch pushed after the buffer drains. (That the configuration still reports FIFO is asserted
2613    /// separately by `surb_store_config_should_default_to_fifo`.)
2614    #[test]
2615    fn surb_ring_buffer_should_consume_oldest_first() -> anyhow::Result<()> {
2616        let expected: [HoprSurbId; 2] = [[1u8; 8], [2u8; 8]];
2617        let rb = SurbRingBuffer::new(5);
2618
2619        assert_eq!(1, rb.push([([1u8; 8], 0)], 0).retained);
2620        assert_eq!(2, rb.push([([2u8; 8], 0)], 0).retained);
2621
2622        let popped = rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?;
2623        assert_eq!(expected[0], popped.id);
2624        assert_eq!(1, popped.remaining);
2625
2626        let popped = rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?;
2627        assert_eq!(expected[1], popped.id);
2628        assert_eq!(0, popped.remaining);
2629
2630        // A fresh batch after draining is consumed in the same order.
2631        assert_eq!(2, rb.push([([1u8; 8], 0), ([2u8; 8], 0)], 0).retained);
2632        assert_eq!(expected[0], rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?.id);
2633        assert_eq!(expected[1], rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?.id);
2634
2635        Ok(())
2636    }
2637
2638    #[test]
2639    fn surb_ring_buffer_should_skip_entries_failing_the_predicate() -> anyhow::Result<()> {
2640        let rb = SurbRingBuffer::new(5);
2641        rb.push([([1u8; 8], 0), ([2u8; 8], 0), ([3u8; 8], 0)], 0);
2642
2643        // Only the middle entry is acceptable, so the two rejected ones must be discarded.
2644        let popped = rb
2645            .pop_next_valid(|id, _| id == &[2u8; 8])
2646            .ok_or(anyhow::anyhow!("expected pop"))?;
2647        assert_eq!([2u8; 8], popped.id);
2648
2649        // The rejected entries are gone, not merely skipped over.
2650        assert_eq!(1, popped.remaining);
2651        assert!(rb.pop_next_valid(|id, _| id == &[2u8; 8]).is_none());
2652
2653        Ok(())
2654    }
2655
2656    #[test]
2657    fn surb_ring_buffer_should_return_none_when_no_entry_satisfies_the_predicate() -> anyhow::Result<()> {
2658        let rb = SurbRingBuffer::new(5);
2659        rb.push([([1u8; 8], 0), ([2u8; 8], 0)], 0);
2660
2661        assert!(rb.pop_next_valid(|_, _| false).is_none());
2662        // The buffer is fully drained by the exhaustive search.
2663        assert!(rb.pop_any().is_none());
2664
2665        Ok(())
2666    }
2667
2668    #[test]
2669    fn surb_ring_buffer_should_report_no_eviction_below_capacity() {
2670        let rb = SurbRingBuffer::new(4);
2671
2672        assert_eq!(
2673            SurbInsertOutcome {
2674                retained: 2,
2675                evicted: 0,
2676                evicted_shares: 0,
2677                superseded: 0
2678            },
2679            rb.push([([1u8; 8], 0), ([2u8; 8], 0)], 0)
2680        );
2681        assert_eq!(
2682            SurbInsertOutcome {
2683                retained: 4,
2684                evicted: 0,
2685                evicted_shares: 0,
2686                superseded: 0
2687            },
2688            rb.push([([3u8; 8], 0), ([4u8; 8], 0)], 0)
2689        );
2690    }
2691
2692    /// Overflow is otherwise entirely silent — the buffer drops its oldest entry and the caller sees
2693    /// only a successful push. The count is what lets the layers above notice that SURBs (and the
2694    /// PIX shares riding on them) are being destroyed on arrival, so it has to be exact.
2695    #[test]
2696    fn surb_ring_buffer_should_count_evictions_past_capacity() -> anyhow::Result<()> {
2697        let rb = SurbRingBuffer::new(2);
2698
2699        let outcome = rb.push([([1u8; 8], 0), ([2u8; 8], 0), ([3u8; 8], 0)], 0);
2700        assert_eq!(
2701            SurbInsertOutcome {
2702                retained: 2,
2703                evicted: 1,
2704                evicted_shares: 0,
2705                superseded: 0
2706            },
2707            outcome,
2708            "a 3-element push into a 2-slot buffer drops exactly one, and it carried no share"
2709        );
2710
2711        // The *oldest* is the one gone.
2712        let ids: Vec<_> = std::iter::from_fn(|| rb.pop_any().map(|p| p.id)).collect();
2713        assert!(
2714            !ids.contains(&[1u8; 8]),
2715            "the oldest entry must be the evicted one, got {ids:?}"
2716        );
2717
2718        Ok(())
2719    }
2720
2721    /// A buffer already at capacity evicts one per element pushed, however the pushes are grouped —
2722    /// the steady-state overflow that a counterparty producing faster than this side drains creates.
2723    #[test]
2724    fn surb_ring_buffer_should_count_evictions_across_separate_pushes() {
2725        let rb = SurbRingBuffer::new(2);
2726        assert_eq!(
2727            0,
2728            rb.push([([1u8; 8], 0), ([2u8; 8], 0)], 0).evicted,
2729            "precondition: full"
2730        );
2731
2732        assert_eq!(
2733            SurbInsertOutcome {
2734                retained: 2,
2735                evicted: 1,
2736                evicted_shares: 0,
2737                superseded: 0
2738            },
2739            rb.push([([3u8; 8], 0)], 0)
2740        );
2741        assert_eq!(
2742            SurbInsertOutcome {
2743                retained: 2,
2744                evicted: 2,
2745                evicted_shares: 0,
2746                superseded: 0
2747            },
2748            rb.push([([4u8; 8], 0), ([5u8; 8], 0)], 0)
2749        );
2750    }
2751
2752    /// A newer generation drops the SURBs it supersedes, but those were already unusable — the
2753    /// creator re-planned its own return path. Counting them as evictions would report capacity
2754    /// pressure that does not exist, and the count feeds the eviction summary (and the
2755    /// counterparty-facing `num_evicted_surbs`) that exists to flag over-production. The same holds for
2756    /// a late older-generation batch, which is discarded without ever entering the buffer. They are
2757    /// not lost to the caller's bookkeeping, though: `superseded` carries the number, so that the
2758    /// Exit's flow estimate can book the wipe.
2759    #[test]
2760    fn surb_ring_buffer_should_not_count_superseded_generations_as_evictions() {
2761        let rb = SurbRingBuffer::new(2);
2762        assert_eq!(
2763            0,
2764            rb.push([([1u8; 8], 0), ([2u8; 8], 0)], 0).evicted,
2765            "precondition: full at generation 0"
2766        );
2767
2768        // A newer generation clears the full buffer before inserting: two SURBs go, none of them to
2769        // capacity pressure, and both are reported as superseded.
2770        assert_eq!(
2771            SurbInsertOutcome {
2772                retained: 1,
2773                evicted: 0,
2774                evicted_shares: 0,
2775                superseded: 2
2776            },
2777            rb.push([([3u8; 8], 0)], 1),
2778            "a supersede-and-clear is not an overflow, but the wiped stock is reported"
2779        );
2780
2781        // A late batch from the superseded generation is dropped whole, again without overflowing;
2782        // the whole batch is reported as superseded, and the buffer is untouched.
2783        assert_eq!(
2784            SurbInsertOutcome {
2785                retained: 1,
2786                evicted: 0,
2787                evicted_shares: 0,
2788                superseded: 2
2789            },
2790            rb.push([([4u8; 8], 0), ([5u8; 8], 0)], 0),
2791            "a discarded older-generation batch is not an overflow, but its size is reported"
2792        );
2793
2794        // An ordinary refill at the current generation supersedes nothing.
2795        assert_eq!(
2796            0,
2797            rb.push([([6u8; 8], 0)], 1).superseded,
2798            "an equal generation appends and supersedes nothing"
2799        );
2800    }
2801
2802    /// The buffer grows with occupancy, so it does reallocate on the way up to its ceiling — that
2803    /// is the point of
2804    /// [`surb_ring_buffer_must_allocate_with_occupancy_not_capacity`]. What must not happen is
2805    /// churn *afterwards*: once a pseudonym has filled its buffer, an unbounded stream of
2806    /// pushes and pops must not keep reallocating. So the high-water mark is reached first and
2807    /// sampled there, rather than at construction.
2808    #[test]
2809    fn surb_ring_buffer_should_not_reallocate_under_steady_overflow() -> anyhow::Result<()> {
2810        let rb = SurbRingBuffer::new(8);
2811
2812        for i in 0..8u32 {
2813            rb.push([(((i as u64).to_be_bytes()), 0)], 0);
2814        }
2815        let settled_capacity = rb.allocated();
2816        assert!(settled_capacity >= 8, "8 SURBs must actually fit");
2817
2818        for i in 0..1_000u32 {
2819            rb.push([(((i as u64).to_be_bytes()), 0)], 0);
2820            if i % 3 == 0 {
2821                rb.pop_any();
2822            }
2823            assert!(rb.len() <= 8, "length exceeded capacity");
2824        }
2825
2826        assert_eq!(settled_capacity, rb.allocated(), "buffer reallocated");
2827
2828        Ok(())
2829    }
2830
2831    /// The pseudonym a buffer is filed under is chosen by whoever sent the packet, and
2832    /// `insert_surbs` mints a buffer for any pseudonym that arrives carrying a SURB. So the cost
2833    /// must track what a buffer holds, not what it is allowed to hold — otherwise an
2834    /// unauthenticated peer reserves `rb_capacity` worth of memory per pseudonym it invents.
2835    ///
2836    /// Guards against a swap back to a structure that sizes itself at construction.
2837    #[test]
2838    fn surb_ring_buffer_must_allocate_with_occupancy_not_capacity() {
2839        const CAPACITY: usize = 100_000;
2840        let rb = SurbRingBuffer::<u64>::new(CAPACITY);
2841
2842        let empty = rb.allocated();
2843        assert!(empty < CAPACITY / 100, "a buffer holding nothing reserved for {empty}");
2844
2845        for i in 0..10u64 {
2846            rb.push([([i as u8; 8], i)], 0);
2847        }
2848
2849        let allocated = rb.allocated();
2850        assert!(allocated >= 10, "10 SURBs must actually fit");
2851        assert!(
2852            allocated < CAPACITY / 100,
2853            "10 SURBs reserved for {allocated} — allocation is tracking capacity, not occupancy"
2854        );
2855    }
2856
2857    #[test]
2858    fn surb_ring_buffer_should_not_pop_if_id_does_not_match() -> anyhow::Result<()> {
2859        let rb = SurbRingBuffer::new(5);
2860
2861        rb.push([([1u8; 8], 0)], 0);
2862
2863        assert!(rb.pop_one_if_has_id(&[2u8; 8]).is_none());
2864        assert_eq!(
2865            [1u8; 8],
2866            rb.pop_one_if_has_id(&[1u8; 8])
2867                .ok_or(anyhow::anyhow!("expected pop"))?
2868                .id
2869        );
2870
2871        Ok(())
2872    }
2873
2874    /// A reply opener whose contents don't matter — the tests only ask whether one is *present* —
2875    /// so it is built once and cloned for every SURB.
2876    fn cheap_opener() -> ReplyOpener {
2877        ReplyOpener {
2878            sender_key: SecretKey16::random(),
2879            shared_secrets: Vec::new(),
2880        }
2881    }
2882
2883    /// Floods `flood` reply openers (ids `0..flood`) for one pseudonym into a fresh client store
2884    /// capped at `max_openers`, then forces moka's lazy size-driven evictions to land so the
2885    /// retained set is observable. Returns the store and its pseudonym.
2886    fn flooded_client(max_openers: usize, flood: u64) -> (MemorySurbStore, HoprPseudonym) {
2887        let client = MemorySurbStore::new(SurbStoreConfig {
2888            max_openers_per_pseudonym: max_openers,
2889            ..Default::default()
2890        });
2891        let pseudonym = HoprPseudonym::random();
2892        let opener = cheap_opener();
2893        for i in 0..flood {
2894            let id: HoprSurbId = i.to_be_bytes();
2895            client.insert_reply_opener(HoprSenderId::from_pseudonym_and_id(&pseudonym, id), opener.clone());
2896        }
2897        client.pseudonym_openers.run_pending_tasks();
2898        if let Some(inner) = client.pseudonym_openers.get(&pseudonym) {
2899            inner.run_pending_tasks();
2900        }
2901        (client, pseudonym)
2902    }
2903
2904    /// Upload-only return-path model.
2905    ///
2906    /// One session pseudonym uploads hard: it keeps minting SURBs (one reply opener stored per SURB
2907    /// on the *client*, one SURB stored on the *exit*) while the exit barely replies, so nothing is
2908    /// consumed and both stores run to capacity and start evicting. `flood` pairs are pushed, then
2909    /// the exit answers `replies` times — each answer pops a SURB the way the exit would and tries
2910    /// to open it on the client. Returns how many of those replies land on a reply opener the client
2911    /// has already evicted, i.e. how many replies the client cannot decrypt.
2912    ///
2913    /// The two stores are separate instances with their own configs, mirroring the two ends: the
2914    /// client cares only about `max_openers` (its reply-opener cache), the exit only about
2915    /// `rb_capacity` (its SURB ring).
2916    fn undecryptable_replies_after_upload_flood(
2917        max_openers: usize,
2918        rb_capacity: usize,
2919        flood: usize,
2920        replies: usize,
2921    ) -> usize {
2922        let (client, pseudonym) = flooded_client(max_openers, flood as u64);
2923        let exit = MemorySurbStore::new(SurbStoreConfig {
2924            rb_capacity,
2925            ..Default::default()
2926        });
2927        // The exit's ring only reaches `rb_capacity` for an admitted pseudonym; unadmitted SURBs land
2928        // in the 16-cap quarantine, which a 200-reply flood would exhaust long before the test's
2929        // eviction math is exercised.
2930        exit.admit(&pseudonym, rb_capacity);
2931
2932        // A direct return path (chain length 1) is always usable, so `find_surb` never skips one for
2933        // an unrelated reason — the only thing under test is the opener's presence. The SURB value is
2934        // invariant across the flood, so build it once and clone (`HoprSurb` is a memcpy).
2935        let surb = surb_via(HoprKeyIdent::from(1u32), DIRECT).expect("valid surb fixture");
2936        for i in 0..flood as u64 {
2937            exit.insert_surbs(pseudonym, vec![(i.to_be_bytes(), surb.clone())]);
2938        }
2939
2940        (0..replies)
2941            .filter(|_| {
2942                let found = exit
2943                    .find_surb(SurbMatcher::Pseudonym(pseudonym))
2944                    .expect("the exit still holds SURBs to reply with");
2945                client.find_reply_opener(&found.sender_id).is_none()
2946            })
2947            .count()
2948    }
2949
2950    /// Baseline: while the reply-opener cache has not overflowed, every reply opens. Confirms the
2951    /// two-store plumbing (matching pseudonym + SURB id) before the overflow tests read anything
2952    /// into an eviction.
2953    #[test]
2954    fn replies_stay_decryptable_while_the_opener_cache_has_not_overflowed() {
2955        const MAX_OPENERS: usize = 7000;
2956        // Flood == capacity: nothing is evicted.
2957        let undecryptable = undecryptable_replies_after_upload_flood(MAX_OPENERS, 1050, MAX_OPENERS, 200);
2958        assert_eq!(
2959            0, undecryptable,
2960            "no reply should be undecryptable before the cache overflows"
2961        );
2962    }
2963
2964    /// The fix, at the store level: on overflow the reply-opener cache sheds the stalest openers and
2965    /// keeps the newest, matching the exit's newest-SURB ring (the `lru()` rationale is on
2966    /// [`MemorySurbStore::insert_reply_opener`]). This asserts that directly — after overflowing a
2967    /// 7 000-cap cache with 21 000 openers, the oldest ids are gone and the newest are present.
2968    #[test]
2969    fn a_sustained_upload_keeps_the_newest_reply_openers_and_sheds_the_stalest() {
2970        const MAX_OPENERS: usize = 7000;
2971        const FLOOD: u64 = 21_000;
2972        const EDGE: u64 = 1_050; // a slice at each end of the id range
2973
2974        let (client, pseudonym) = flooded_client(MAX_OPENERS, FLOOD);
2975        let inner = client
2976            .pseudonym_openers
2977            .get(&pseudonym)
2978            .expect("the pseudonym's opener cache exists");
2979
2980        let present =
2981            |lo: u64, hi: u64| -> u64 { (lo..hi).filter(|i| inner.contains_key(&i.to_be_bytes())).count() as u64 };
2982
2983        assert_eq!(0, present(0, EDGE), "the stalest openers are shed");
2984        assert_eq!(
2985            EDGE,
2986            present(FLOOD - EDGE, FLOOD),
2987            "the freshest openers — the ones the exit's newest SURBs need — are kept"
2988        );
2989    }
2990
2991    /// End-to-end at the store level: with the opener cache keeping its newest entries, a sustained
2992    /// upload no longer strands the return path at the deployed configuration. At production
2993    /// proportions (opener cache larger than the exit's SURB ring) every reply opens.
2994    ///
2995    /// The one case that still strands replies is a misconfiguration: an exit whose SURB ring is
2996    /// *larger* than the opener cache, so it pops the oldest SURBs whose openers fall outside the
2997    /// smaller opener window. It is neither deployed nor sane, and is asserted here to document the
2998    /// boundary of the fix rather than to endorse it. (Before the fix, every one of these cases
2999    /// stranded all `REPLIES`; see this test's history.)
3000    ///
3001    /// In the inverted case the exit retains the newest `rb_capacity` SURBs and the client the newest
3002    /// `max_openers` openers (`flood` overflows both), so the two ranges overlap only on the newest
3003    /// `max_openers` ids. The exit pops from the oldest end, so the first `rb_capacity - max_openers`
3004    /// pops fall outside that opener window; since `REPLIES <= rb_capacity - max_openers`
3005    /// (200 ≤ 14 000), every tested reply is undecryptable.
3006    #[rstest]
3007    #[case::production_fifo(7000, 1050, 21_000, 0)]
3008    #[case::inverted_fifo(1000, 15_000, 20_000, 200)]
3009    fn a_sustained_upload_keeps_the_return_path_alive_at_the_deployed_config(
3010        #[case] max_openers: usize,
3011        #[case] rb_capacity: usize,
3012        #[case] flood: usize,
3013        #[case] expected_undecryptable: usize,
3014    ) {
3015        const REPLIES: usize = 200;
3016        let undecryptable = undecryptable_replies_after_upload_flood(max_openers, rb_capacity, flood, REPLIES);
3017        assert_eq!(
3018            expected_undecryptable, undecryptable,
3019            "unexpected undecryptable-reply count at openers={max_openers}, rb={rb_capacity}"
3020        );
3021    }
3022
3023    /// `pop_one_if_has_id` checks only the popping end, which is the front (oldest). Given {1, 2}, a
3024    /// match for the id behind it is not popped; the id at the front is.
3025    #[test]
3026    fn surb_ring_buffer_should_check_the_popping_end_for_an_exact_id() -> anyhow::Result<()> {
3027        let (other_end_id, popping_end_id) = ([2u8; 8], [1u8; 8]);
3028        let rb = SurbRingBuffer::new(5);
3029        rb.push([([1u8; 8], 0), ([2u8; 8], 0)], 0);
3030
3031        assert!(rb.pop_one_if_has_id(&other_end_id).is_none());
3032        assert_eq!(
3033            popping_end_id,
3034            rb.pop_one_if_has_id(&popping_end_id)
3035                .ok_or(anyhow::anyhow!("expected pop"))?
3036                .id
3037        );
3038
3039        Ok(())
3040    }
3041
3042    // --- generation-tagged consumption -----------------------------------------------------------
3043
3044    #[test]
3045    fn surb_ring_buffer_should_drop_the_previous_generation_when_a_newer_one_arrives() -> anyhow::Result<()> {
3046        let rb = SurbRingBuffer::new(64);
3047        rb.push([([1u8; 8], 0), ([2u8; 8], 0)], 3);
3048        assert_eq!(2, rb.len());
3049
3050        // A newer generation supersedes the old one: the buffer is cleared before inserting, so only
3051        // the new-generation SURB remains and it is what the next pop returns.
3052        rb.push([([9u8; 8], 0)], 4);
3053        assert_eq!(1, rb.len(), "the superseded generation must be dropped, not retained");
3054        assert_eq!(Some(4), rb.generation());
3055
3056        let popped = rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?;
3057        assert_eq!([9u8; 8], popped.id, "only the new generation may be handed out");
3058        assert!(rb.pop_any().is_none(), "no stale SURB may remain");
3059
3060        Ok(())
3061    }
3062
3063    #[test]
3064    fn surb_ring_buffer_should_append_within_the_same_generation() -> anyhow::Result<()> {
3065        let rb = SurbRingBuffer::new(64);
3066        rb.push([([1u8; 8], 0)], 7);
3067        rb.push([([2u8; 8], 0)], 7);
3068        assert_eq!(2, rb.len(), "same-generation batches accumulate");
3069        assert_eq!([1u8; 8], rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?.id);
3070        assert_eq!([2u8; 8], rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?.id);
3071        Ok(())
3072    }
3073
3074    #[test]
3075    fn surb_ring_buffer_should_discard_a_stale_older_generation_batch() -> anyhow::Result<()> {
3076        let rb = SurbRingBuffer::new(64);
3077        rb.push([([9u8; 8], 0)], 5);
3078
3079        // A late/reordered batch from an older generation must not reintroduce stale SURBs.
3080        rb.push([([1u8; 8], 0), ([2u8; 8], 0)], 4);
3081        assert_eq!(1, rb.len(), "the older-generation batch must be discarded");
3082        assert_eq!(Some(5), rb.generation());
3083        assert_eq!([9u8; 8], rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?.id);
3084
3085        Ok(())
3086    }
3087
3088    /// A generation is an RFC-1982 `u8` serial, so it wraps 255 -> 0. The wrap must trigger the same
3089    /// supersede-and-clear as any other newer generation, not be misread as an older batch.
3090    #[test]
3091    fn surb_ring_buffer_should_switch_generations_across_the_u8_wrap() -> anyhow::Result<()> {
3092        let rb = SurbRingBuffer::new(64);
3093        rb.push([([1u8; 8], 0), ([2u8; 8], 0)], 255);
3094        assert_eq!(2, rb.len());
3095
3096        // 0 is newer than 255 across the wrap: drop the old generation and switch to the new one.
3097        rb.push([([9u8; 8], 0)], 0);
3098        assert_eq!(
3099            1,
3100            rb.len(),
3101            "the wrapped-around newer generation must supersede the previous one"
3102        );
3103        assert_eq!(Some(0), rb.generation());
3104        assert_eq!([9u8; 8], rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?.id);
3105        assert!(rb.pop_any().is_none(), "no stale SURB may survive the wrap");
3106
3107        Ok(())
3108    }
3109
3110    /// Several return-path re-plans in a row, walking up to and across the wrap (253 -> 1). Each newer
3111    /// generation supersedes the one before, so the eldest is dropped at every step and the buffer
3112    /// holds only the newest batch — re-plans alone can never accumulate stale generations and so can
3113    /// never overflow capacity.
3114    #[test]
3115    fn surb_ring_buffer_should_supersede_across_consecutive_replans_including_the_wrap() -> anyhow::Result<()> {
3116        let rb = SurbRingBuffer::new(64);
3117
3118        for (i, generation) in [253u8, 254, 255, 0, 1].into_iter().enumerate() {
3119            rb.push([([i as u8; 8], 0)], generation);
3120            assert_eq!(
3121                1,
3122                rb.len(),
3123                "each re-plan must leave only its own batch, dropping the previous"
3124            );
3125            assert_eq!(Some(generation), rb.generation());
3126        }
3127
3128        // Only the final generation's SURB (index 4, generation 1) survives.
3129        assert_eq!([4u8; 8], rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?.id);
3130        assert!(rb.pop_any().is_none());
3131
3132        Ok(())
3133    }
3134
3135    /// With several re-plans in flight at once, their batches can arrive out of order. The buffer
3136    /// keeps the highest generation it has seen and discards a later-arriving older batch, so the exit
3137    /// never falls back to a superseded path even when three generations touch the buffer.
3138    #[test]
3139    fn surb_ring_buffer_should_keep_the_highest_generation_when_replans_arrive_out_of_order() -> anyhow::Result<()> {
3140        let rb = SurbRingBuffer::new(64);
3141        rb.push([([1u8; 8], 0)], 7); // generation 7
3142        rb.push([([2u8; 8], 0)], 9); // generation 9 (two re-plans later) supersedes 7
3143        rb.push([([3u8; 8], 0)], 8); // generation 8 arrives late, out of order -> discarded as older
3144        assert_eq!(1, rb.len(), "a late older-generation batch must not be reintroduced");
3145        assert_eq!(Some(9), rb.generation());
3146        assert_eq!([2u8; 8], rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?.id);
3147
3148        Ok(())
3149    }
3150
3151    /// The shares a generation change takes out of play are reported, whether it clears the ring or
3152    /// refuses a late older batch.
3153    #[test]
3154    fn surb_ring_buffer_should_count_the_shares_a_generation_change_takes_out_of_play() -> anyhow::Result<()> {
3155        let rb = SurbRingBuffer::new(8);
3156        rb.push([share_surb(1)?, plain_surb(2)?, share_surb(3)?], 3);
3157
3158        let (outcome, replaced_shares) = rb.push_counting([plain_surb(4)?, share_surb(5)?, share_surb(6)?], 2);
3159        assert_eq!(
3160            (3, 2),
3161            (outcome.superseded, replaced_shares),
3162            "the late batch is refused"
3163        );
3164
3165        let (outcome, replaced_shares) = rb.push_counting([share_surb(7)?], 4);
3166        assert_eq!(
3167            (3, 2),
3168            (outcome.superseded, replaced_shares),
3169            "the newer generation clears the ring"
3170        );
3171        assert_eq!(1, rb.len());
3172
3173        Ok(())
3174    }
3175
3176    /// The exit's discard decision must be defined right at the serial-space boundary. A batch a full
3177    /// half-space ahead (+128) is deliberately NOT taken as newer, so the exit keeps its current SURBs
3178    /// rather than switch to an ambiguously-ordered generation. This cannot arise while adjacent
3179    /// generations are in flight (the design's premise); the test pins the boundary so it stays
3180    /// intentional rather than accidental.
3181    #[test]
3182    fn surb_ring_buffer_should_not_switch_on_a_half_serial_space_jump() -> anyhow::Result<()> {
3183        let rb = SurbRingBuffer::new(64);
3184        rb.push([([1u8; 8], 0)], 10);
3185
3186        rb.push([([2u8; 8], 0)], 10u8.wrapping_add(128));
3187        assert_eq!(1, rb.len(), "a half-space jump must not be taken as newer");
3188        assert_eq!(
3189            Some(10),
3190            rb.generation(),
3191            "the current generation is retained at the boundary"
3192        );
3193        assert_eq!(
3194            [1u8; 8],
3195            rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?.id,
3196            "the exit keeps its current SURB rather than the ambiguous one"
3197        );
3198
3199        Ok(())
3200    }
3201
3202    /// A newer generation clears the buffer *before* inserting, so even a batch large enough to
3203    /// overflow capacity holds only new-generation SURBs — a superseded generation can never occupy a
3204    /// slot the live return path needs.
3205    #[test]
3206    fn surb_ring_buffer_should_clear_before_capacity_eviction_on_a_newer_generation() -> anyhow::Result<()> {
3207        let rb = SurbRingBuffer::new(3);
3208        rb.push([([1u8; 8], 0), ([2u8; 8], 0), ([3u8; 8], 0)], 0); // fill to capacity at generation 0
3209        assert_eq!(3, rb.len());
3210
3211        // Newer generation, a full batch: generation 0 is cleared first, then the new batch fills
3212        // from scratch — no generation-0 SURB survives to consume a slot.
3213        rb.push([([4u8; 8], 0), ([5u8; 8], 0), ([6u8; 8], 0)], 1);
3214        assert_eq!(3, rb.len(), "capacity is respected and no superseded SURB survives");
3215        assert_eq!(Some(1), rb.generation());
3216        for expected in [[4u8; 8], [5u8; 8], [6u8; 8]] {
3217            assert_eq!(expected, rb.pop_any().ok_or(anyhow::anyhow!("expected pop"))?.id);
3218        }
3219
3220        Ok(())
3221    }
3222
3223    #[test]
3224    fn generation_serial_should_wrap_around() {
3225        // RFC-1982: 0 is newer than 255, and 255 is not newer than 0.
3226        assert!(generation_is_newer(0, 255), "0 must be newer than 255 across the wrap");
3227        assert!(
3228            !generation_is_newer(255, 0),
3229            "255 must not be newer than 0 across the wrap"
3230        );
3231        assert!(generation_is_newer(4, 3));
3232        assert!(!generation_is_newer(3, 3), "a generation is not newer than itself");
3233
3234        // The comparison window is half the serial space: +127 is still newer, but +128 sits on the
3235        // ambiguity boundary and is deliberately NOT treated as newer. This is the cap on how far the
3236        // sender may advance between two batches the exit actually sees; adjacent generations — the
3237        // only case in flight — are nowhere near it, so the exit's discard decision stays well-defined.
3238        assert!(
3239            generation_is_newer(10u8.wrapping_add(127), 10),
3240            "+127 is inside the window"
3241        );
3242        assert!(
3243            !generation_is_newer(10u8.wrapping_add(128), 10),
3244            "+128 is the boundary and must not read as newer"
3245        );
3246    }
3247
3248    /// The sending-side generation serial starts at 0 for an unseen pseudonym and each bump advances
3249    /// it by one (the value the encoder stamps onto the next minted batch).
3250    #[test]
3251    fn memory_surb_store_generation_should_start_at_zero_and_advance_on_bump() {
3252        let store = MemorySurbStore::default();
3253        let pseudonym = HoprPseudonym::random();
3254
3255        assert_eq!(
3256            0,
3257            store.current_generation(&pseudonym),
3258            "an unseen pseudonym starts at generation 0"
3259        );
3260        assert_eq!(
3261            1,
3262            store.bump_generation(&pseudonym),
3263            "the first bump returns the new generation 1"
3264        );
3265        assert_eq!(
3266            1,
3267            store.current_generation(&pseudonym),
3268            "current_generation reflects the last bump"
3269        );
3270        assert_eq!(2, store.bump_generation(&pseudonym), "each bump advances by one");
3271        assert_eq!(2, store.current_generation(&pseudonym));
3272    }
3273
3274    /// End-to-end at the store: a newer generation for a pseudonym drops the SURBs held for the old
3275    /// one, so a return-path change takes effect on the next reply (one-packet recovery).
3276    #[test]
3277    fn memory_surb_store_should_switch_to_the_newest_generation() -> anyhow::Result<()> {
3278        let relayer = HoprKeyIdent::from(1u32);
3279        let store = MemorySurbStore::default();
3280        let pseudonym = HoprPseudonym::random();
3281
3282        store.insert_surbs(
3283            pseudonym,
3284            vec![
3285                ([1u8; 8], surb_gen(relayer, TWO_HOP, 0)?),
3286                ([2u8; 8], surb_gen(relayer, TWO_HOP, 0)?),
3287            ],
3288        );
3289        // The client re-plans the return path and mints a fresh batch at the next generation.
3290        store.insert_surbs(pseudonym, vec![([3u8; 8], surb_gen(relayer, TWO_HOP, 1)?)]);
3291
3292        let found = store
3293            .find_surb(SurbMatcher::Pseudonym(pseudonym))
3294            .ok_or(anyhow::anyhow!("expected a usable SURB"))?;
3295        assert_eq!(
3296            [3u8; 8],
3297            found.sender_id.surb_id(),
3298            "must hand out the newest generation"
3299        );
3300        assert_eq!(0, found.remaining, "the superseded generation must have been dropped");
3301        assert!(
3302            store.find_surb(SurbMatcher::Pseudonym(pseudonym)).is_none(),
3303            "no stale SURB may remain"
3304        );
3305
3306        Ok(())
3307    }
3308
3309    /// A batch is minted at a single generation by an honest creator, but it is parsed out of a
3310    /// counterparty-controlled payload. A batch whose SURBs disagree must not smuggle a superseded
3311    /// return path into the buffer the batch's generation labels: only the first SURB's generation
3312    /// is kept.
3313    #[test]
3314    fn memory_surb_store_should_reject_surbs_that_disagree_with_their_batch() -> anyhow::Result<()> {
3315        let relayer = HoprKeyIdent::from(1u32);
3316        let store = MemorySurbStore::default();
3317        let pseudonym = HoprPseudonym::random();
3318
3319        // The peer had already delivered a generation-0 batch that the mixed batch below supersedes.
3320        store.insert_surbs(pseudonym, vec![([1u8; 8], surb_gen(relayer, TWO_HOP, 0)?)]);
3321
3322        let outcome = store.insert_surbs(
3323            pseudonym,
3324            vec![
3325                ([2u8; 8], surb_gen(relayer, TWO_HOP, 1)?),
3326                // Stale: belongs to the generation the batch itself supersedes.
3327                ([3u8; 8], surb_gen(relayer, TWO_HOP, 0)?),
3328            ],
3329        );
3330        assert_eq!(1, outcome.retained, "only the SURB matching the batch may be stored");
3331        assert_eq!(
3332            0, outcome.evicted,
3333            "a mismatched SURB is not capacity pressure and must not be reported as eviction"
3334        );
3335        assert_eq!(0, outcome.evicted_shares, "and it cannot have cost a share either");
3336        assert_eq!(
3337            2, outcome.superseded,
3338            "the generation-0 SURB the batch wiped and the mismatched one it refused are both gone from the buffer, \
3339             though the packet reported both of its SURBs as received"
3340        );
3341
3342        let found = store
3343            .find_surb(SurbMatcher::Pseudonym(pseudonym))
3344            .ok_or(anyhow::anyhow!("expected a usable SURB"))?;
3345        assert_eq!(
3346            [2u8; 8],
3347            found.sender_id.surb_id(),
3348            "must hand out the SURB of the batch's own generation"
3349        );
3350        assert!(
3351            store.find_surb(SurbMatcher::Pseudonym(pseudonym)).is_none(),
3352            "no SURB of a superseded generation may remain"
3353        );
3354
3355        Ok(())
3356    }
3357
3358    // --- share-bearing SURBs first -----------------------------------------------------------------
3359
3360    /// The Entry emits the PIX shares of a cycle first and share-less SURBs after, and a share reaches
3361    /// the reconstructor only when its SURB is *used*. So shares go out ahead of share-less SURBs
3362    /// however the two were interleaved on arrival, each tier oldest first.
3363    #[test]
3364    fn surb_ring_buffer_should_pop_share_bearing_surbs_before_share_less_ones() -> anyhow::Result<()> {
3365        let rb = SurbRingBuffer::new(8);
3366        // One batch, as a packet delivers them: each SURB is classified on its own.
3367        rb.push([plain_surb(1)?, share_surb(2)?, plain_surb(3)?, share_surb(4)?], 0);
3368
3369        assert_eq!(vec![2, 4, 1, 3], drain_ids(&rb));
3370
3371        Ok(())
3372    }
3373
3374    /// A share-less SURB is only a return path, so it is what a full buffer gives up first, oldest
3375    /// first — even when a share-bearing SURB is older still.
3376    #[test]
3377    fn surb_ring_buffer_should_evict_share_less_surbs_before_shares() -> anyhow::Result<()> {
3378        let rb = SurbRingBuffer::new(3);
3379        assert_eq!(
3380            SurbInsertOutcome {
3381                retained: 3,
3382                evicted: 0,
3383                evicted_shares: 0,
3384                superseded: 0
3385            },
3386            rb.push([share_surb(1)?, plain_surb(2)?, share_surb(3)?], 0)
3387        );
3388
3389        assert_eq!(
3390            SurbInsertOutcome {
3391                retained: 3,
3392                evicted: 1,
3393                evicted_shares: 0,
3394                superseded: 0
3395            },
3396            rb.push([share_surb(4)?], 0),
3397            "the share-less SURB goes, not the older share, so no share is lost"
3398        );
3399
3400        assert_eq!(vec![1, 3, 4], drain_ids(&rb));
3401
3402        Ok(())
3403    }
3404
3405    /// A share-bearing SURB is a return path *and* a share nothing can replace, so a share-less
3406    /// newcomer is refused rather than evict one. The refusal is capacity pressure all the same, so
3407    /// it is reported as an eviction — but not as a lost share, because none was lost.
3408    #[test]
3409    fn surb_ring_buffer_should_refuse_a_share_less_surb_rather_than_evict_a_share() -> anyhow::Result<()> {
3410        let rb = SurbRingBuffer::new(2);
3411        rb.push([share_surb(1)?, share_surb(2)?], 0);
3412
3413        assert_eq!(
3414            SurbInsertOutcome {
3415                retained: 2,
3416                evicted: 1,
3417                evicted_shares: 0,
3418                superseded: 0
3419            },
3420            rb.push([plain_surb(3)?], 0)
3421        );
3422
3423        assert_eq!(vec![1, 2], drain_ids(&rb), "both shares must survive");
3424
3425        Ok(())
3426    }
3427
3428    /// With nothing share-less left to give up, shares fall back to the historical rule: the oldest
3429    /// goes. That is the one case where an eviction destroys a share, and it is counted as such.
3430    #[test]
3431    fn surb_ring_buffer_should_evict_the_oldest_share_once_no_share_less_surbs_remain() -> anyhow::Result<()> {
3432        let rb = SurbRingBuffer::new(2);
3433        rb.push([share_surb(1)?, share_surb(2)?], 0);
3434
3435        assert_eq!(
3436            SurbInsertOutcome {
3437                retained: 2,
3438                evicted: 1,
3439                evicted_shares: 1,
3440                superseded: 0
3441            },
3442            rb.push([share_surb(3)?], 0)
3443        );
3444
3445        assert_eq!(vec![2, 3], drain_ids(&rb));
3446
3447        Ok(())
3448    }
3449
3450    /// The eviction order is applied per SURB, not per batch: a packet's SURBs can straddle the
3451    /// share to share-less transition, and each one meets the buffer as the one before left it.
3452    /// Of the two evictions in the second batch only the one that takes a share is a lost share.
3453    #[test]
3454    fn surb_ring_buffer_should_apply_the_eviction_order_to_each_surb_of_a_batch() -> anyhow::Result<()> {
3455        let rb = SurbRingBuffer::new(2);
3456
3457        // Share 3 evicts the share-less 1 that sits ahead of it.
3458        assert_eq!(
3459            SurbInsertOutcome {
3460                retained: 2,
3461                evicted: 1,
3462                evicted_shares: 0,
3463                superseded: 0
3464            },
3465            rb.push([plain_surb(1)?, share_surb(2)?, share_surb(3)?], 0)
3466        );
3467
3468        // Only shares are held now: the share-less 4 is refused, then share 5 evicts the oldest share.
3469        assert_eq!(
3470            SurbInsertOutcome {
3471                retained: 2,
3472                evicted: 2,
3473                evicted_shares: 1,
3474                superseded: 0
3475            },
3476            rb.push([plain_surb(4)?, share_surb(5)?], 0)
3477        );
3478
3479        assert_eq!(vec![3, 5], drain_ids(&rb));
3480
3481        Ok(())
3482    }
3483
3484    /// `remaining` counts the whole buffer, not the tier the SURB came from: the SURB distress flag is
3485    /// raised from it, and must not depend on how the held SURBs happen to be split between the tiers.
3486    #[test]
3487    fn surb_ring_buffer_should_report_remaining_across_both_tiers() -> anyhow::Result<()> {
3488        let rb = SurbRingBuffer::new(8);
3489        rb.push([share_surb(1)?, plain_surb(2)?, plain_surb(3)?], 0);
3490        assert_eq!(3, rb.len());
3491
3492        for expected_remaining in [2, 1, 0] {
3493            let popped = rb.pop_any().context("expected pop")?;
3494            assert_eq!(expected_remaining, popped.remaining);
3495        }
3496
3497        Ok(())
3498    }
3499
3500    /// The tier sizes are what `len` is made of, reported as `(share-bearing, share-less)`: the first
3501    /// is how many shares are still to be delivered, the second how many plain return paths sit
3502    /// behind them.
3503    #[test]
3504    fn surb_ring_buffer_should_report_the_size_of_each_tier() -> anyhow::Result<()> {
3505        let rb = SurbRingBuffer::new(8);
3506        assert_eq!((0, 0), rb.tier_lens(), "an empty buffer holds nothing in either tier");
3507
3508        rb.push([plain_surb(1)?, share_surb(2)?, plain_surb(3)?, plain_surb(4)?], 0);
3509        assert_eq!((1, 3), rb.tier_lens());
3510        assert_eq!(4, rb.len(), "the tiers add up to the buffer's length");
3511
3512        // Shares are handed out first, so the share tier empties before the share-less one is touched.
3513        rb.pop_any().context("expected the share-bearing SURB")?;
3514        assert_eq!((0, 3), rb.tier_lens());
3515        rb.pop_any().context("expected a share-less SURB")?;
3516        assert_eq!((0, 2), rb.tier_lens());
3517
3518        // A newer generation supersedes both tiers.
3519        rb.push([share_surb(5)?], 1);
3520        assert_eq!((1, 0), rb.tier_lens());
3521
3522        Ok(())
3523    }
3524
3525    /// The store exposes the split per pseudonym, so a layer that only holds a [`SurbStore`] can trace
3526    /// it; a pseudonym without a buffer has none to report.
3527    #[test]
3528    fn memory_surb_store_should_report_the_size_of_each_tier_per_pseudonym() -> anyhow::Result<()> {
3529        let store = MemorySurbStore::default();
3530        let pseudonym = HoprPseudonym::random();
3531        assert_eq!(None, store.tier_lens(&pseudonym), "no SURBs, no buffer, no tiers");
3532
3533        store.insert_surbs(pseudonym, vec![plain_surb(1)?, share_surb(2)?, plain_surb(3)?]);
3534        assert_eq!(Some((1, 2)), store.tier_lens(&pseudonym));
3535        assert_eq!(
3536            None,
3537            store.tier_lens(&HoprPseudonym::random()),
3538            "another pseudonym has its own buffer"
3539        );
3540
3541        // The decoder holds the store behind an `Arc`, and the trait's defaulted method must still reach
3542        // the store's own implementation through it rather than answer `None`.
3543        let shared = Arc::new(store);
3544        assert_eq!(Some((1, 2)), SurbStore::tier_lens(&shared, &pseudonym));
3545
3546        Ok(())
3547    }
3548
3549    /// An exact-ID pop inspects only the end the next pop would take. That is now the share-bearing
3550    /// tier while it holds anything, so a share-less SURB is not poppable by ID ahead of a share.
3551    #[test]
3552    fn surb_ring_buffer_should_check_the_popping_end_of_the_next_tier_for_an_exact_id() -> anyhow::Result<()> {
3553        let (plain_id, share_id) = ([1u8; 8], [2u8; 8]);
3554        let rb = SurbRingBuffer::new(8);
3555        rb.push([plain_surb(1)?, share_surb(2)?], 0);
3556
3557        assert!(
3558            rb.pop_one_if_has_id(&plain_id).is_none(),
3559            "the share-bearing SURB is next, so the share-less one is not"
3560        );
3561        assert_eq!(
3562            share_id,
3563            rb.pop_one_if_has_id(&share_id)
3564                .context("the share-bearing SURB is next")?
3565                .id
3566        );
3567        assert_eq!(
3568            plain_id,
3569            rb.pop_one_if_has_id(&plain_id)
3570                .context("with the share gone, the share-less SURB is next")?
3571                .id
3572        );
3573
3574        Ok(())
3575    }
3576
3577    /// A newer generation supersedes the SURBs of *both* tiers: a share-bearing SURB for the old return
3578    /// path is as unusable as a share-less one.
3579    #[test]
3580    fn surb_ring_buffer_should_clear_both_tiers_on_a_newer_generation() -> anyhow::Result<()> {
3581        let rb = SurbRingBuffer::new(8);
3582        rb.push([plain_surb(1)?, share_surb(2)?], 0);
3583        assert_eq!(2, rb.len());
3584
3585        rb.push([share_surb(3)?], 1);
3586
3587        assert_eq!(1, rb.len(), "neither tier may keep a superseded SURB");
3588        assert_eq!(vec![3], drain_ids(&rb), "only the newer generation may be handed out");
3589
3590        Ok(())
3591    }
3592
3593    /// End-to-end at the store: SURBs are classified by the share sealed in them, so the one that
3594    /// carries a share is handed out first although it did not arrive first.
3595    #[test]
3596    fn memory_surb_store_should_hand_out_share_bearing_surbs_first() -> anyhow::Result<()> {
3597        let store = MemorySurbStore::default();
3598        let pseudonym = HoprPseudonym::random();
3599
3600        store.insert_surbs(pseudonym, vec![plain_surb(1)?, share_surb(2)?, plain_surb(3)?]);
3601
3602        let first = store
3603            .find_surb(SurbMatcher::Pseudonym(pseudonym))
3604            .context("expected a usable SURB")?;
3605        assert_eq!([2u8; 8], first.sender_id.surb_id(), "the share-bearing SURB goes first");
3606        assert_eq!(2, first.remaining);
3607
3608        let mut order_seen = vec![first.sender_id.surb_id()[0]];
3609        while let Some(found) = store.find_surb(SurbMatcher::Pseudonym(pseudonym)) {
3610            order_seen.push(found.sender_id.surb_id()[0]);
3611        }
3612        assert_eq!(vec![2, 1, 3], order_seen);
3613
3614        Ok(())
3615    }
3616
3617    /// The classification reads the share block of the SURB's receiver-only data: an all-zero block
3618    /// is a share-less SURB, and anything else names the SSA its share belongs to.
3619    #[test]
3620    fn hopr_surb_share_info_should_treat_a_zero_share_as_share_less() -> anyhow::Result<()> {
3621        let relayer = HoprKeyIdent::from(1u32);
3622
3623        assert_eq!(
3624            None,
3625            surb_via(relayer, TWO_HOP)?.ssa_index(),
3626            "a zeroed share block carries no share"
3627        );
3628        assert_eq!(SsaIndex::new(7), surb_share(relayer, 7)?.ssa_index());
3629
3630        Ok(())
3631    }
3632
3633    const REPORT_INTERVAL: Duration = Duration::from_secs(60);
3634
3635    impl EvictionStats {
3636        /// Counts one eviction at the given time rather than now, and returns the closed interval's counts
3637        /// if it closed one. Most tests count evictions singly, against a clock they control.
3638        fn record_at(&self, cache: EvictedCache, cause: RemovalCause, now: Instant) -> Option<EvictionReport> {
3639            self.record_many_at(cache, cause, 1, now)
3640        }
3641    }
3642
3643    fn eviction_stats(warn_threshold: u64) -> EvictionStats {
3644        EvictionStats::new(&SurbStoreConfig {
3645            eviction_report_interval: REPORT_INTERVAL,
3646            eviction_report_threshold: warn_threshold,
3647            ..Default::default()
3648        })
3649    }
3650
3651    #[test]
3652    fn eviction_stats_should_not_report_before_the_interval_elapses() {
3653        let stats = eviction_stats(0);
3654        let t0 = Instant::now();
3655        for _ in 0..10 {
3656            assert!(
3657                stats
3658                    .record_at(EvictedCache::ReplyOpener, RemovalCause::Expired, t0)
3659                    .is_none()
3660            );
3661        }
3662
3663        let just_before = t0 + REPORT_INTERVAL - Duration::from_millis(1);
3664        assert!(
3665            stats
3666                .record_at(EvictedCache::ReplyOpener, RemovalCause::Size, just_before)
3667                .is_none()
3668        );
3669    }
3670
3671    #[test]
3672    fn eviction_stats_should_report_counts_per_cache_and_cause_once_the_interval_elapses() -> anyhow::Result<()> {
3673        let stats = eviction_stats(0);
3674        let t0 = Instant::now();
3675        for _ in 0..3 {
3676            stats.record_at(EvictedCache::ReplyOpener, RemovalCause::Expired, t0);
3677        }
3678        for _ in 0..2 {
3679            stats.record_at(EvictedCache::ReplyOpener, RemovalCause::Size, t0);
3680        }
3681        stats.record_at(EvictedCache::SurbRing, RemovalCause::Replaced, t0);
3682        stats.record_at(EvictedCache::SurbRing, RemovalCause::Explicit, t0);
3683
3684        let report = stats
3685            .record_at(EvictedCache::Generation, RemovalCause::Expired, t0 + REPORT_INTERVAL)
3686            .context("the interval has elapsed, so a report is due")?;
3687
3688        assert_eq!(
3689            report.counts(EvictedCache::ReplyOpener),
3690            EvictionCounts {
3691                expired: 3,
3692                size: 2,
3693                replaced: 0
3694            }
3695        );
3696        assert_eq!(
3697            report.counts(EvictedCache::SurbRing),
3698            EvictionCounts {
3699                expired: 0,
3700                size: 0,
3701                replaced: 1
3702            },
3703            "explicit removals are not evictions"
3704        );
3705        assert_eq!(
3706            report.counts(EvictedCache::Generation),
3707            EvictionCounts::default(),
3708            "the eviction that closes an interval belongs to the next one"
3709        );
3710        assert_eq!(report.counts(EvictedCache::ReplyOpenerBatch), EvictionCounts::default());
3711
3712        let next = stats
3713            .record_at(EvictedCache::SurbRing, RemovalCause::Explicit, t0 + 2 * REPORT_INTERVAL)
3714            .context("second interval has elapsed")?;
3715        assert_eq!(
3716            next.counts(EvictedCache::Generation),
3717            EvictionCounts {
3718                expired: 1,
3719                size: 0,
3720                replaced: 0
3721            }
3722        );
3723        Ok(())
3724    }
3725
3726    #[test]
3727    fn eviction_stats_should_start_a_fresh_interval_after_reporting() -> anyhow::Result<()> {
3728        let stats = eviction_stats(0);
3729        let t0 = Instant::now();
3730        let t1 = t0 + REPORT_INTERVAL;
3731        stats.record_at(EvictedCache::SurbRing, RemovalCause::Expired, t0);
3732        stats
3733            .record_at(EvictedCache::SurbRing, RemovalCause::Expired, t1)
3734            .context("first report")?;
3735
3736        assert!(
3737            stats
3738                .record_at(EvictedCache::SurbRing, RemovalCause::Expired, t1)
3739                .is_none(),
3740            "the new interval has only just started"
3741        );
3742        let report = stats
3743            .record_at(EvictedCache::SurbRing, RemovalCause::Expired, t1 + REPORT_INTERVAL)
3744            .context("second report")?;
3745        assert_eq!(
3746            report.counts(EvictedCache::SurbRing).total(),
3747            2,
3748            "only evictions since the last report count"
3749        );
3750        Ok(())
3751    }
3752
3753    /// A push can drop many SURBs at once, and each is one eviction: `record_many` books them under
3754    /// the one lock instead of taking it once per SURB.
3755    #[test]
3756    fn eviction_stats_should_count_many_evictions_recorded_at_once() -> anyhow::Result<()> {
3757        let stats = eviction_stats(0);
3758        let t0 = Instant::now();
3759        stats.record_many_at(EvictedCache::RingPlain, RemovalCause::Size, 7, t0);
3760        stats.record_many_at(EvictedCache::RingPlain, RemovalCause::Size, 3, t0);
3761        stats.record_many_at(EvictedCache::RingShare, RemovalCause::Size, 2, t0);
3762        stats.record_many_at(EvictedCache::RingShare, RemovalCause::Explicit, 5, t0);
3763        stats.record_many_at(EvictedCache::SurbRing, RemovalCause::Size, 0, t0);
3764
3765        let report = stats
3766            .record_at(EvictedCache::SurbRing, RemovalCause::Explicit, t0 + REPORT_INTERVAL)
3767            .context("the interval has elapsed, so a report is due")?;
3768
3769        assert_eq!(
3770            report.counts(EvictedCache::RingPlain),
3771            EvictionCounts {
3772                expired: 0,
3773                size: 10,
3774                replaced: 0
3775            }
3776        );
3777        assert_eq!(
3778            report.counts(EvictedCache::RingShare),
3779            EvictionCounts {
3780                expired: 0,
3781                size: 2,
3782                replaced: 0
3783            },
3784            "explicit removals are not evictions, however many of them there are"
3785        );
3786        assert_eq!(
3787            report.counts(EvictedCache::SurbRing),
3788            EvictionCounts::default(),
3789            "recording zero evictions counts nothing"
3790        );
3791        Ok(())
3792    }
3793
3794    /// `insert_surbs` reports every push, evictions or not, and most pushes evict nothing: a count of
3795    /// zero is not an eviction, so it neither takes the lock nor closes an interval.
3796    #[test]
3797    fn eviction_stats_should_ignore_a_count_of_zero() {
3798        let stats = eviction_stats(0);
3799        let t0 = Instant::now();
3800        assert!(
3801            stats
3802                .record_many_at(EvictedCache::RingPlain, RemovalCause::Size, 0, t0 + REPORT_INTERVAL)
3803                .is_none(),
3804            "nothing was evicted, so nothing closes the interval"
3805        );
3806        assert_eq!(
3807            EvictionCounts::default(),
3808            stats.state.lock().counts[EvictedCache::RingPlain as usize]
3809        );
3810    }
3811
3812    /// The ring-buffer caches are new *values* of the `cache` label, so the metric names, their
3813    /// descriptions and their label keys — all that METRICS.md documents — are unchanged.
3814    #[test]
3815    fn evicted_cache_should_label_ring_overflows_by_tier() {
3816        assert_eq!("ring_plain", <&'static str>::from(EvictedCache::RingPlain));
3817        assert_eq!("ring_share", <&'static str>::from(EvictedCache::RingShare));
3818        assert_eq!("ring_share", EvictedCache::RingShare.to_string());
3819    }
3820
3821    /// The interval counters are indexed by `cache as usize`, so every cache must be listed in
3822    /// [`EvictedCache::ALL`] exactly once, at the slot its discriminant names.
3823    #[test]
3824    fn evicted_cache_all_should_list_every_cache_at_its_own_slot() {
3825        let slots: Vec<usize> = EvictedCache::ALL.iter().map(|cache| *cache as usize).collect();
3826        assert_eq!((0..EvictedCache::ALL.len()).collect::<Vec<_>>(), slots);
3827    }
3828
3829    /// A lost share is permanent, and the redundancy budget that absorbs losses is finite, so even
3830    /// one is worth a warning. Dropping share-less SURBs is routine under gate bypass (the sender
3831    /// outproduces what the Exit spends), so those keep the configured threshold like every other cache.
3832    #[rstest]
3833    #[case::a_single_lost_share(EvictedCache::RingShare, 1, true)]
3834    #[case::share_less_at_the_threshold(EvictedCache::RingPlain, 5, false)]
3835    #[case::share_less_above_the_threshold(EvictedCache::RingPlain, 6, true)]
3836    fn eviction_report_should_warn_about_any_lost_share_but_only_about_many_share_less_drops(
3837        #[case] cache: EvictedCache,
3838        #[case] evictions: u64,
3839        #[case] expected: bool,
3840    ) -> anyhow::Result<()> {
3841        let stats = eviction_stats(5);
3842        let t0 = Instant::now();
3843        stats.record_many_at(cache, RemovalCause::Size, evictions, t0);
3844        let report = stats
3845            .record_at(EvictedCache::SurbRing, RemovalCause::Explicit, t0 + REPORT_INTERVAL)
3846            .context("report due")?;
3847
3848        assert_eq!(expected, report.exceeds_threshold(cache));
3849
3850        let recorder = Arc::new(RecordingSubscriber::default());
3851        tracing::subscriber::with_default(recorder.clone(), || report.log());
3852        assert_eq!(u64::from(expected), recorder.warnings.load(Ordering::Relaxed));
3853        assert_eq!(u64::from(!expected), recorder.debugs.load(Ordering::Relaxed));
3854        Ok(())
3855    }
3856
3857    #[rstest]
3858    #[case::at_threshold(5, false)]
3859    #[case::above_threshold(6, true)]
3860    fn eviction_report_should_flag_only_caches_above_the_warn_threshold(
3861        #[case] evictions: u64,
3862        #[case] expected: bool,
3863    ) -> anyhow::Result<()> {
3864        let stats = eviction_stats(5);
3865        let t0 = Instant::now();
3866        for _ in 0..evictions {
3867            stats.record_at(EvictedCache::ReplyOpener, RemovalCause::Expired, t0);
3868        }
3869
3870        let report = stats
3871            .record_at(EvictedCache::SurbRing, RemovalCause::Explicit, t0 + REPORT_INTERVAL)
3872            .context("report due")?;
3873
3874        assert_eq!(report.exceeds_threshold(EvictedCache::ReplyOpener), expected);
3875        assert!(!report.exceeds_threshold(EvictedCache::SurbRing));
3876        assert!(
3877            !report.exceeds_threshold(EvictedCache::RingPlain) && !report.exceeds_threshold(EvictedCache::RingShare),
3878            "a cache that saw nothing is never flagged, not even one whose threshold is zero"
3879        );
3880        Ok(())
3881    }
3882
3883    /// Counts events per level; `enabled` is always true so the logging macros' bodies actually run.
3884    #[derive(Default)]
3885    struct RecordingSubscriber {
3886        warnings: AtomicU64,
3887        debugs: AtomicU64,
3888    }
3889
3890    impl tracing::Subscriber for RecordingSubscriber {
3891        fn enabled(&self, _: &tracing::Metadata<'_>) -> bool {
3892            true
3893        }
3894
3895        fn new_span(&self, _: &tracing::span::Attributes<'_>) -> tracing::span::Id {
3896            tracing::span::Id::from_u64(1)
3897        }
3898
3899        fn record(&self, _: &tracing::span::Id, _: &tracing::span::Record<'_>) {}
3900
3901        fn record_follows_from(&self, _: &tracing::span::Id, _: &tracing::span::Id) {}
3902
3903        fn event(&self, event: &tracing::Event<'_>) {
3904            match *event.metadata().level() {
3905                tracing::Level::WARN => self.warnings.fetch_add(1, Ordering::Relaxed),
3906                tracing::Level::DEBUG => self.debugs.fetch_add(1, Ordering::Relaxed),
3907                _ => 0,
3908            };
3909        }
3910
3911        fn enter(&self, _: &tracing::span::Id) {}
3912
3913        fn exit(&self, _: &tracing::span::Id) {}
3914    }
3915
3916    #[test]
3917    fn eviction_report_should_log_one_line_per_cache_that_saw_evictions() -> anyhow::Result<()> {
3918        let stats = eviction_stats(5);
3919        let t0 = Instant::now();
3920        for _ in 0..6 {
3921            stats.record_at(EvictedCache::ReplyOpener, RemovalCause::Expired, t0);
3922        }
3923        stats.record_at(EvictedCache::SurbRing, RemovalCause::Size, t0);
3924        stats.record_many_at(EvictedCache::RingPlain, RemovalCause::Size, 2, t0);
3925        stats.record_at(EvictedCache::RingShare, RemovalCause::Size, t0);
3926        let report = stats
3927            .record_at(EvictedCache::SurbRing, RemovalCause::Explicit, t0 + REPORT_INTERVAL)
3928            .context("report due")?;
3929
3930        let recorder = Arc::new(RecordingSubscriber::default());
3931        tracing::subscriber::with_default(recorder.clone(), || report.log());
3932
3933        assert_eq!(
3934            recorder.warnings.load(Ordering::Relaxed),
3935            2,
3936            "the opener cache exceeded the threshold, and a lost share always warrants a warning"
3937        );
3938        assert_eq!(
3939            recorder.debugs.load(Ordering::Relaxed),
3940            2,
3941            "two caches saw evictions below the threshold; caches without evictions log nothing"
3942        );
3943        Ok(())
3944    }
3945
3946    #[test]
3947    fn eviction_stats_should_log_when_a_real_eviction_closes_the_interval() -> anyhow::Result<()> {
3948        let stats = eviction_stats(0);
3949        {
3950            let mut state = stats.state.lock();
3951            state.started_at = Instant::now()
3952                .checked_sub(2 * REPORT_INTERVAL)
3953                .context("monotonic clock must be at least two intervals old")?;
3954            state.counts[EvictedCache::SurbRing as usize].expired += 1;
3955        }
3956
3957        let recorder = Arc::new(RecordingSubscriber::default());
3958        tracing::subscriber::with_default(recorder.clone(), || {
3959            stats.record(EvictedCache::SurbRing, RemovalCause::Expired)
3960        });
3961
3962        assert_eq!(recorder.warnings.load(Ordering::Relaxed), 1);
3963        Ok(())
3964    }
3965
3966    #[test]
3967    fn memory_surb_store_should_count_evictions_from_every_cache() -> anyhow::Result<()> {
3968        // The opener and generation caches are floored at 1000 pseudonyms, and the quarantine at 64,
3969        // so 1500 distinct ones overflow all three. Fresh-pseudonym SURBs land in the quarantine: the
3970        // admitted cache is entered only through `admit`, which this flood never triggers, so what the
3971        // churn sheds is unadmitted rings — which is the point of the split.
3972        let store = MemorySurbStore::new(SurbStoreConfig {
3973            max_openers_per_pseudonym: 100,
3974            quarantine_max_pseudonyms: 100,
3975            ..Default::default()
3976        });
3977        let relayer = HoprKeyIdent::from(1u32);
3978        let opener = cheap_opener();
3979        for _ in 0..1500 {
3980            let pseudonym = HoprPseudonym::random();
3981            store.insert_reply_opener(
3982                HoprSenderId::from_pseudonym_and_id(&pseudonym, [0u8; 8]),
3983                opener.clone(),
3984            );
3985            store.insert_surbs(pseudonym, vec![([0u8; 8], surb_via(relayer, DIRECT)?)]);
3986            store.bump_generation(&pseudonym);
3987        }
3988        store.pseudonym_openers.run_pending_tasks();
3989        store.quarantine_surbs.run_pending_tasks();
3990        store.generations.run_pending_tasks();
3991
3992        for cache in [
3993            EvictedCache::ReplyOpenerBatch,
3994            EvictedCache::QuarantineRing,
3995            EvictedCache::Generation,
3996        ] {
3997            let size_evictions = store.stats.state.lock().counts[cache as usize].size;
3998            assert!(
3999                size_evictions > 0,
4000                "{cache} overflowed, so its size evictions must be counted"
4001            );
4002        }
4003        Ok(())
4004    }
4005
4006    /// Ring overflows go into the same per-interval summary as the other evictions, split by what
4007    /// they cost: a share-less SURB dropped or refused is only a return path (`ring_plain`), a
4008    /// share-bearing one dropped is a PIX share lost for good (`ring_share`).
4009    #[test]
4010    fn memory_surb_store_should_count_ring_overflows_by_tier() -> anyhow::Result<()> {
4011        // The ring capacity is floored at `MIN_SURB_RB_CAPACITY`, so that is the size to overflow.
4012        let capacity = MIN_SURB_RB_CAPACITY;
4013        let store = MemorySurbStore::new(SurbStoreConfig {
4014            rb_capacity: capacity,
4015            ..Default::default()
4016        });
4017        let pseudonym = HoprPseudonym::random();
4018        // The full-ring arithmetic below is admitted-ring arithmetic; unadmitted SURBs would cap out
4019        // at the quarantine's 16.
4020        store.admit(&pseudonym, capacity);
4021        let (plain, share) = (plain_surb(1)?, share_surb(2)?);
4022
4023        // A full ring: all shares but for one share-less SURB. Nothing overflows yet.
4024        let mut fill = vec![share.clone(); capacity - 1];
4025        fill.push(plain.clone());
4026        assert_eq!(
4027            SurbInsertOutcome {
4028                retained: capacity,
4029                evicted: 0,
4030                evicted_shares: 0,
4031                superseded: 0
4032            },
4033            store.insert_surbs(pseudonym, fill)
4034        );
4035
4036        // The share-less SURB makes way for a share: a return path lost, no share.
4037        assert_eq!(
4038            SurbInsertOutcome {
4039                retained: capacity,
4040                evicted: 1,
4041                evicted_shares: 0,
4042                superseded: 0
4043            },
4044            store.insert_surbs(pseudonym, vec![share.clone()])
4045        );
4046
4047        // Nothing but shares is held now, so two more shares evict the two oldest ones.
4048        assert_eq!(
4049            SurbInsertOutcome {
4050                retained: capacity,
4051                evicted: 2,
4052                evicted_shares: 2,
4053                superseded: 0
4054            },
4055            store.insert_surbs(pseudonym, vec![share.clone(); 2])
4056        );
4057
4058        // Share-less newcomers are refused rather than evict a share: three more return paths lost.
4059        assert_eq!(
4060            SurbInsertOutcome {
4061                retained: capacity,
4062                evicted: 3,
4063                evicted_shares: 0,
4064                superseded: 0
4065            },
4066            store.insert_surbs(pseudonym, vec![plain; 3])
4067        );
4068
4069        let report = store
4070            .stats
4071            .record_at(
4072                EvictedCache::SurbRing,
4073                RemovalCause::Explicit,
4074                Instant::now() + 2 * REPORT_INTERVAL,
4075            )
4076            .context("the interval has elapsed, so a report is due")?;
4077        assert_eq!(
4078            EvictionCounts {
4079                expired: 0,
4080                size: 4,
4081                replaced: 0
4082            },
4083            report.counts(EvictedCache::RingPlain),
4084            "one share-less SURB evicted and three refused"
4085        );
4086        assert_eq!(
4087            EvictionCounts {
4088                expired: 0,
4089                size: 2,
4090                replaced: 0
4091            },
4092            report.counts(EvictedCache::RingShare),
4093            "two shares lost"
4094        );
4095        assert!(
4096            report.exceeds_threshold(EvictedCache::RingShare) && !report.exceeds_threshold(EvictedCache::RingPlain),
4097            "any lost share warrants a warning, four dropped return paths do not"
4098        );
4099
4100        Ok(())
4101    }
4102
4103    /// The shares a newer generation clears are lost for good, and are booked as replaced.
4104    #[test]
4105    fn memory_surb_store_should_count_the_shares_a_newer_generation_replaces() -> anyhow::Result<()> {
4106        let store = MemorySurbStore::default();
4107        let pseudonym = HoprPseudonym::random();
4108        store.insert_surbs(pseudonym, vec![share_surb(1)?, plain_surb(2)?, share_surb(3)?]);
4109        store.insert_surbs(
4110            pseudonym,
4111            vec![([4u8; 8], surb_gen(HoprKeyIdent::from(1u32), TWO_HOP, 1)?)],
4112        );
4113
4114        let report = store
4115            .stats
4116            .record_at(
4117                EvictedCache::SurbRing,
4118                RemovalCause::Explicit,
4119                Instant::now() + 2 * REPORT_INTERVAL,
4120            )
4121            .context("the interval has elapsed, so a report is due")?;
4122        assert_eq!(
4123            EvictionCounts {
4124                expired: 0,
4125                size: 0,
4126                replaced: 2
4127            },
4128            report.counts(EvictedCache::RingShare)
4129        );
4130        Ok(())
4131    }
4132
4133    /// The level the Exit's session layer keeps from what each packet reports (`evicted + superseded`
4134    /// per insert, one per pop) follows the store through every exit but one: SURBs discarded at pop
4135    /// time, because their first relayer was invalidated, are not reported back.
4136    #[test]
4137    fn the_reported_surb_level_follows_the_store_except_for_discards_at_pop_time() -> anyhow::Result<()> {
4138        const CAPACITY: usize = MIN_SURB_RB_CAPACITY;
4139        let (relayer, pseudonym) = (HoprKeyIdent::from(1u32), HoprPseudonym::random());
4140        let store = MemorySurbStore::new(SurbStoreConfig {
4141            rb_capacity: CAPACITY,
4142            ..Default::default()
4143        });
4144        store.admit(&pseudonym, CAPACITY);
4145
4146        let (mut level, mut next_id) = (0isize, 0u64);
4147        let mut insert = |count: usize, generation: u8| -> anyhow::Result<isize> {
4148            let batch = (0..count)
4149                .map(|_| {
4150                    next_id += 1;
4151                    Ok((next_id.to_be_bytes(), surb_gen(relayer, TWO_HOP, generation)?))
4152                })
4153                .collect::<anyhow::Result<Vec<_>>>()?;
4154            let outcome = store.insert_surbs(pseudonym, batch);
4155            level += count as isize - (outcome.evicted + outcome.superseded) as isize;
4156            Ok(level)
4157        };
4158        let held = || store.tier_lens(&pseudonym).map(|(shares, plain)| shares + plain);
4159
4160        assert_eq!(10, insert(10, 0)?, "a plain fill");
4161        assert_eq!(Some(10), held());
4162        assert_eq!(
4163            CAPACITY as isize,
4164            insert(CAPACITY, 0)?,
4165            "an overflow evicts the oldest ten"
4166        );
4167        assert_eq!(Some(CAPACITY), held());
4168        assert_eq!(5, insert(5, 1)?, "a newer generation wipes the stock");
4169        assert_eq!(Some(5), held());
4170        assert_eq!(5, insert(3, 0)?, "a stale older generation is refused whole");
4171        assert_eq!(Some(5), held());
4172
4173        let popped = store
4174            .find_surb(SurbMatcher::Pseudonym(pseudonym))
4175            .context("a SURB must be there to pop")?;
4176        let level = level - 1;
4177        assert_eq!(Some(level as usize), held(), "a successful pop is one SURB");
4178        assert_eq!(level as usize, popped.remaining, "and it reports what is left");
4179
4180        store.invalidate_relayer(&relayer);
4181        assert!(store.find_surb(SurbMatcher::Pseudonym(pseudonym)).is_none());
4182        // This exit is not reported to the caller: its running level stays above what the store holds.
4183        assert_eq!((4, Some(0)), (level, held()), "the pop discarded every remaining SURB");
4184
4185        Ok(())
4186    }
4187
4188    #[test]
4189    fn memory_surb_store_should_count_size_evictions_of_flooded_reply_openers() {
4190        let (client, _) = flooded_client(MINIMUM_OPENERS_PER_PSEUDONYM, 3 * MINIMUM_OPENERS_PER_PSEUDONYM as u64);
4191
4192        let size_evictions = client.stats.state.lock().counts[EvictedCache::ReplyOpener as usize].size;
4193        assert!(
4194            size_evictions > 0,
4195            "the flood overflowed the opener cache, so its size evictions must be counted"
4196        );
4197    }
4198
4199    #[test]
4200    fn surb_store_config_should_reject_an_eviction_report_interval_below_the_minimum() {
4201        use validator::Validate;
4202
4203        let too_low = SurbStoreConfig {
4204            eviction_report_interval: MINIMUM_EVICTION_REPORT_INTERVAL - Duration::from_millis(1),
4205            ..Default::default()
4206        };
4207        assert!(too_low.validate().is_err());
4208        assert!(SurbStoreConfig::default().validate().is_ok());
4209    }
4210
4211    /// The range rules on the admission-control fields, checked without serde so they are exercised
4212    /// under the default feature set — the serde-gated companion below covers only the loading half.
4213    #[test]
4214    fn surb_store_config_should_reject_out_of_range_admission_fields() {
4215        use validator::Validate;
4216
4217        // Every field at its boundary is valid. The budget's range rule spells its floor as a literal
4218        // (as every other range validator here does), so the assertions below — which reject one below
4219        // `QUARANTINE_SURB_BUDGET_FLOOR` and accept it exactly — are what pin the two together.
4220        assert!(
4221            SurbStoreConfig {
4222                quarantine_rb_capacity: MINIMUM_QUARANTINE_RB_CAPACITY,
4223                quarantine_max_pseudonyms: MINIMUM_QUARANTINE_PSEUDONYMS,
4224                quarantine_surb_budget: QUARANTINE_SURB_BUDGET_FLOOR,
4225                admitted_max_pseudonyms: 1,
4226                admitted_headroom_percent: 0,
4227                ..Default::default()
4228            }
4229            .validate()
4230            .is_ok(),
4231            "each admission field at its floor must validate"
4232        );
4233
4234        for (name, cfg) in [
4235            (
4236                "quarantine_rb_capacity",
4237                SurbStoreConfig {
4238                    quarantine_rb_capacity: MINIMUM_QUARANTINE_RB_CAPACITY - 1,
4239                    ..Default::default()
4240                },
4241            ),
4242            (
4243                "quarantine_max_pseudonyms",
4244                SurbStoreConfig {
4245                    quarantine_max_pseudonyms: MINIMUM_QUARANTINE_PSEUDONYMS - 1,
4246                    ..Default::default()
4247                },
4248            ),
4249            (
4250                "quarantine_surb_budget",
4251                SurbStoreConfig {
4252                    quarantine_surb_budget: QUARANTINE_SURB_BUDGET_FLOOR - 1,
4253                    ..Default::default()
4254                },
4255            ),
4256            (
4257                "admitted_max_pseudonyms",
4258                SurbStoreConfig {
4259                    admitted_max_pseudonyms: 0,
4260                    ..Default::default()
4261                },
4262            ),
4263        ] {
4264            assert!(cfg.validate().is_err(), "{name} below its floor must be rejected");
4265        }
4266
4267        // The lifetime uses a custom rule rather than a range, so it is checked on its own.
4268        assert!(
4269            SurbStoreConfig {
4270                quarantine_lifetime: MINIMUM_SURB_LIFETIME - Duration::from_millis(1),
4271                ..Default::default()
4272            }
4273            .validate()
4274            .is_err(),
4275            "a quarantine lifetime below the SURB lifetime floor must be rejected"
4276        );
4277    }
4278
4279    // --- admission control -------------------------------------------------------------------------
4280
4281    /// The issue's regression: a flood of fresh pseudonyms used to LRU-evict a live Session's ring out
4282    /// of the single SURB cache. Now the flood is confined to the quarantine — and the test is not
4283    /// vacuous about it: it first asserts the quarantine actually shed rings under the flood, and only
4284    /// then that the admitted ring survived.
4285    #[test]
4286    fn admitted_ring_survives_a_fresh_pseudonym_flood() -> anyhow::Result<()> {
4287        // The quarantine's own floor: the flood must be able to shed something.
4288        let store = MemorySurbStore::new(SurbStoreConfig {
4289            quarantine_max_pseudonyms: MINIMUM_QUARANTINE_PSEUDONYMS,
4290            ..Default::default()
4291        });
4292        let live = HoprPseudonym::random();
4293        let relayer = HoprKeyIdent::from(1u32);
4294
4295        store.admit(&live, MIN_SURB_RB_CAPACITY);
4296        store.insert_surbs(live, vec![([7u8; 8], surb_via(relayer, DIRECT)?)]);
4297
4298        // 65 fresh pseudonyms against a 64-entry quarantine: at least one quarantine ring must go.
4299        for i in 0..(MINIMUM_QUARANTINE_PSEUDONYMS + 1) {
4300            store.insert_surbs(
4301                HoprPseudonym::random(),
4302                vec![([i as u8; 8], surb_via(relayer, DIRECT)?)],
4303            );
4304        }
4305        store.quarantine_surbs.run_pending_tasks();
4306        store.admitted_surbs_per_pseudonym.run_pending_tasks();
4307
4308        let shed = store.stats.state.lock().counts[EvictedCache::QuarantineRing as usize].size;
4309        assert!(
4310            shed > 0,
4311            "precondition: the flood must actually shed quarantine rings, got {shed}"
4312        );
4313        assert!(
4314            store.find_surb(SurbMatcher::Pseudonym(live)).is_some(),
4315            "the admitted ring must survive a flood that shed {shed} quarantine rings"
4316        );
4317
4318        Ok(())
4319    }
4320
4321    /// The v1 budget refused admitted inserts, dropping live PIX shares to protect untrusted SURBs —
4322    /// the defect the two-class split exists to remove. With the quarantine budget saturated by
4323    /// churn, a second, legitimate Session's insert must still be accepted and retained.
4324    #[test]
4325    fn a_second_legitimate_session_can_still_insert_under_quarantine_pressure() -> anyhow::Result<()> {
4326        // 512 pseudonyms × 16 SURBs of fresh churn against the 4096 budget floor: the drain sheds
4327        // rings as it runs, so the counter ends wherever the last drain landed rather than at the
4328        // cap — the flood puts the quarantine under sustained pressure, and the store below pins the
4329        // counter to the cap so the admitted insert is decided against a saturated budget.
4330        let store = MemorySurbStore::new(SurbStoreConfig {
4331            quarantine_surb_budget: 4096,
4332            ..Default::default()
4333        });
4334        let relayer = HoprKeyIdent::from(1u32);
4335        let surb = surb_via(relayer, DIRECT).context("fixture SURB")?;
4336        for i in 0..512u32 {
4337            let batch: Vec<_> = (0..16u32)
4338                .map(|j| ([((i * 16 + j) % 256) as u8; 8], surb.clone()))
4339                .collect();
4340            store.insert_surbs(HoprPseudonym::random(), batch);
4341        }
4342        store.quarantine_surbs.run_pending_tasks();
4343
4344        // Pin the counter at its cap: the point under test is an admitted insert decided while the
4345        // budget has nothing left, and reaching that state through churn alone is timing-dependent —
4346        // every drain the churn triggers hands the counter back headroom before the next insert.
4347        store
4348            .quarantine_budget
4349            .store(store.cfg.quarantine_surb_budget, Ordering::Relaxed);
4350
4351        let second = HoprPseudonym::random();
4352        store.admit(&second, MIN_SURB_RB_CAPACITY);
4353        let outcome = store.insert_surbs(second, vec![([1u8; 8], surb_via(relayer, DIRECT)?)]);
4354
4355        assert_eq!(
4356            1, outcome.retained,
4357            "an admitted insert must be retained, whatever the quarantine budget is doing"
4358        );
4359        assert_eq!(
4360            0,
4361            store
4362                .find_surb(SurbMatcher::Pseudonym(second))
4363                .context("expected a SURB")?
4364                .remaining,
4365            "and it must still be there to be spent"
4366        );
4367
4368        Ok(())
4369    }
4370
4371    /// The budget drain evicts whole rings as explicit removals, which the quarantine listener skips,
4372    /// so the drain is the only place that can refund what it sheds. Missing that decrement pinned the
4373    /// counter at the cap under exactly the fresh-pseudonym churn the budget exists to bound: the
4374    /// quarantine emptied out while the counter stayed full, and every later fresh SURB was refused
4375    /// for good. After a flood that drove the drain, the counter must read what the quarantine
4376    /// actually holds, and a fresh SURB must be accepted again.
4377    #[test]
4378    fn the_quarantine_budget_recovers_after_the_budget_drain_empties_the_quarantine() -> anyhow::Result<()> {
4379        // Full 16-SURB rings against the budget floor: 512 pseudonyms × 16 = 8192 unadmitted SURBs,
4380        // well past the 4096 budget, while staying inside the 1024-pseudonym cache — so every ring the
4381        // store sheds is shed by the budget drain, not by the cache's own LRU.
4382        let store = MemorySurbStore::new(SurbStoreConfig {
4383            quarantine_surb_budget: 4096,
4384            ..Default::default()
4385        });
4386        let relayer = HoprKeyIdent::from(1u32);
4387        let inserted = 512 * 16;
4388
4389        // Sustained churn: the drain must run repeatedly and the counter must come back down every
4390        // time, not ratchet up to the cap.
4391        let surb = surb_via(relayer, DIRECT).context("fixture SURB")?;
4392        for i in 0..512u32 {
4393            let batch: Vec<_> = (0..16u32)
4394                .map(|j| ([((i * 16 + j) % 256) as u8; 8], surb.clone()))
4395                .collect();
4396            store.insert_surbs(HoprPseudonym::random(), batch);
4397        }
4398        store.quarantine_surbs.run_pending_tasks();
4399
4400        // The counter is the only record of what the quarantine holds, so it must agree with the
4401        // rings actually resident — a pinned counter over-reports `surbs_held` and refuses forever.
4402        let resident: usize = store.quarantine_surbs.iter().map(|(_, rb)| rb.len()).sum();
4403        assert!(
4404            resident < inserted,
4405            "precondition: the budget drain must have shed rings, resident {resident} of {inserted}"
4406        );
4407        assert_eq!(
4408            resident,
4409            store.quarantine_budget.load(Ordering::Relaxed),
4410            "the budget counter must track the {resident} SURBs the quarantine actually holds"
4411        );
4412
4413        // Whatever the drain left, a brand-new pseudonym must be able to write into the quarantine.
4414        let fresh = HoprPseudonym::random();
4415        let outcome = store.insert_surbs(fresh, vec![([1u8; 8], surb_via(relayer, DIRECT)?)]);
4416        assert_eq!(
4417            1, outcome.retained,
4418            "a fresh SURB must be accepted after the flood, not refused by a pinned counter"
4419        );
4420        assert!(
4421            store.find_surb(SurbMatcher::Pseudonym(fresh)).is_some(),
4422            "the accepted SURB must still be spendable"
4423        );
4424
4425        Ok(())
4426    }
4427
4428    /// A lookup that discards every SURB it examines — here because their first relayer was
4429    /// invalidated — empties the ring and yields `None`. The refund used to sit behind that `None`
4430    /// short-circuit, so the discarded SURBs were never subtracted and the counter pinned at the cap
4431    /// the same way the drain leak pinned it.
4432    #[test]
4433    fn the_quarantine_budget_refunds_surbs_discarded_by_a_failing_lookup() -> anyhow::Result<()> {
4434        let store = MemorySurbStore::default();
4435        let pseudonym = HoprPseudonym::random();
4436        let relayer = HoprKeyIdent::from(1u32);
4437
4438        // Two quarantine SURBs returning via a relayer that is invalidated before the lookup: both
4439        // are discarded and the lookup comes up empty.
4440        store.insert_surbs(
4441            pseudonym,
4442            vec![
4443                ([1u8; 8], surb_via(relayer, TWO_HOP)?),
4444                ([2u8; 8], surb_via(relayer, TWO_HOP)?),
4445            ],
4446        );
4447        store.invalidate_relayer(&relayer);
4448
4449        assert!(
4450            store.find_surb(SurbMatcher::Pseudonym(pseudonym)).is_none(),
4451            "precondition: the lookup must discard both SURBs and yield nothing"
4452        );
4453        assert_eq!(
4454            0,
4455            store.quarantine_budget.load(Ordering::Relaxed),
4456            "both discarded SURBs must be refunded to the budget"
4457        );
4458        assert_eq!(0, store.surbs_held(), "nothing of the pseudonym remains held");
4459
4460        // The refund must leave the quarantine usable for the next pseudonym.
4461        let fresh = HoprPseudonym::random();
4462        let outcome = store.insert_surbs(fresh, vec![([3u8; 8], surb_via(relayer, DIRECT)?)]);
4463        assert_eq!(
4464            1, outcome.retained,
4465            "a fresh SURB must still be accepted after the discard emptied the budget"
4466        );
4467
4468        Ok(())
4469    }
4470
4471    /// Admission used to be bounded by `max_pseudonyms`, which the operator cannot raise past the
4472    /// Session census without also unbounding the reply openers. Admitted rings must outlive that
4473    /// value now: `max_pseudonyms` no longer sizes any receiving-side cache.
4474    #[test]
4475    fn admitted_pseudonyms_above_max_pseudonyms_do_not_degrade() -> anyhow::Result<()> {
4476        // `max_pseudonyms` is floored at 1000, so 1500 admissions must exceed it while staying well
4477        // under `admitted_max_pseudonyms`.
4478        let store = MemorySurbStore::new(SurbStoreConfig {
4479            max_pseudonyms: 100,
4480            admitted_max_pseudonyms: 2000,
4481            ..Default::default()
4482        });
4483        let relayer = HoprKeyIdent::from(1u32);
4484
4485        for i in 0..1500 {
4486            let pseudonym = HoprPseudonym::random();
4487            store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
4488            store.insert_surbs(pseudonym, vec![([i as u8; 8], surb_via(relayer, DIRECT)?)]);
4489        }
4490        store.admitted_surbs_per_pseudonym.run_pending_tasks();
4491
4492        let shed = store.stats.state.lock().counts[EvictedCache::SurbRing as usize].size;
4493        assert_eq!(
4494            0, shed,
4495            "1500 admitted pseudonyms must all be held; the admitted cache saw {shed} size evictions"
4496        );
4497        let readable = store
4498            .admitted_surbs_per_pseudonym
4499            .iter()
4500            .filter(|(_, rb)| rb.len() == 1)
4501            .count();
4502        assert_eq!(
4503            1500, readable,
4504            "every admitted ring must still be readable, not just the newest ones"
4505        );
4506
4507        Ok(())
4508    }
4509
4510    /// A ring that accumulated in quarantine before the Session over it was established must move
4511    /// into the admitted class on admission — at the admitted capacity, not the quarantine one — and
4512    /// the transfer must not double-count a single SURB.
4513    #[test]
4514    fn quarantine_surbs_should_be_promoted_on_admission() -> anyhow::Result<()> {
4515        let store = MemorySurbStore::default();
4516        let pseudonym = HoprPseudonym::random();
4517        let relayer = HoprKeyIdent::from(1u32);
4518
4519        for i in 0..10 {
4520            store.insert_surbs(pseudonym, vec![([i as u8; 8], surb_via(relayer, DIRECT)?)]);
4521        }
4522        let before = store.surbs_held();
4523        assert_eq!(
4524            10,
4525            store
4526                .quarantine_surbs
4527                .get(&pseudonym)
4528                .context("precondition: ring in quarantine")?
4529                .len(),
4530            "precondition: the unadmitted ring holds all ten"
4531        );
4532
4533        store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
4534
4535        let admitted = store
4536            .admitted_surbs_per_pseudonym
4537            .get(&pseudonym)
4538            .context("the admitted ring must exist after admission")?;
4539        assert_eq!(10, admitted.len(), "the promoted ring carries all ten SURBs");
4540        assert!(
4541            store.quarantine_surbs.get(&pseudonym).is_none(),
4542            "the quarantine entry must be gone"
4543        );
4544        assert_eq!(
4545            before,
4546            store.surbs_held(),
4547            "a promotion moves SURBs, it does not create or lose them"
4548        );
4549
4550        Ok(())
4551    }
4552
4553    /// Re-admitting a fixed pseudonym — a Session reopened on the same one — must not discard what
4554    /// the admitted ring already holds.
4555    #[test]
4556    fn admit_should_not_clobber_an_existing_admitted_ring() -> anyhow::Result<()> {
4557        let store = MemorySurbStore::default();
4558        let pseudonym = HoprPseudonym::random();
4559        let relayer = HoprKeyIdent::from(1u32);
4560
4561        store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
4562        store.insert_surbs(pseudonym, vec![([1u8; 8], surb_via(relayer, DIRECT)?)]);
4563        store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
4564
4565        assert_eq!(
4566            1,
4567            store
4568                .admitted_surbs_per_pseudonym
4569                .get(&pseudonym)
4570                .context("the admitted ring must still exist")?
4571                .len(),
4572            "the second admission must have left the ring's contents alone"
4573        );
4574        assert!(
4575            store.find_surb(SurbMatcher::Pseudonym(pseudonym)).is_some(),
4576            "and the SURB must still be spendable"
4577        );
4578
4579        Ok(())
4580    }
4581
4582    /// A re-admission must widen the resident ring to the successor's target, not leave it at the
4583    /// predecessor's smaller ceiling.
4584    ///
4585    /// The failure this rules out: a teardown defers `retire` by a grace period, a successor Session on
4586    /// the same client-chosen pseudonym commits inside that window, and its `admit` finds the
4587    /// predecessor's entry — re-stamping the epoch but, before this fix, leaving the ring at the
4588    /// predecessor's capacity. A successor that announced a larger `announced_surb_target` then runs
4589    /// for its whole lifetime at the smaller ceiling, and once its balancer fills past it, `push` evicts
4590    /// — losing PIX shares permanently, with nothing but an `evicted` count to show for it.
4591    #[test]
4592    fn a_re_admission_must_raise_the_ring_ceiling_to_the_successors_target() -> anyhow::Result<()> {
4593        let store = MemorySurbStore::default();
4594        let pseudonym = HoprPseudonym::random();
4595        let relayer = HoprKeyIdent::from(1u32);
4596
4597        // Targets chosen so the two admitted ceilings are 1.5× the target and well inside
4598        // [`SurbStoreConfig::rb_capacity`]: 200 → 300, 600 → 900.
4599        let small = 200;
4600        let large = 600;
4601        store.admit(&pseudonym, small);
4602        store.admit(&pseudonym, large);
4603
4604        // More than `small × 1.5` (the predecessor's ceiling): under the old behaviour the ring would
4605        // still be capped at 300 and evict the excess.
4606        let fill: Vec<(HoprSurbId, HoprSurb)> = (0..500u64)
4607            .map(|i| Ok((i.to_be_bytes(), surb_via(relayer, DIRECT)?)))
4608            .collect::<anyhow::Result<_>>()?;
4609        assert_eq!(
4610            SurbInsertOutcome {
4611                retained: fill.len(),
4612                evicted: 0,
4613                evicted_shares: 0,
4614                superseded: 0
4615            },
4616            store.insert_surbs(pseudonym, fill),
4617            "the successor's larger target must have raised the ring's ceiling, not been left at the predecessor's"
4618        );
4619
4620        Ok(())
4621    }
4622
4623    /// A re-admission must not *narrow* a ceiling a live Session may already be filling: capacity is
4624    /// monotone, so the effective ceiling is the largest target any admission of the pseudonym asked
4625    /// for.
4626    ///
4627    /// The mirror of the test above: `admit` raises with a `fetch_max`, so a successor announcing a
4628    /// *smaller* target than its predecessor leaves the wider ceiling in place. Lowering it would strand
4629    /// SURBs the live Session had already inserted — and make the ceiling depend on admission order.
4630    #[test]
4631    fn a_re_admission_must_not_lower_an_existing_ring_ceiling() -> anyhow::Result<()> {
4632        let store = MemorySurbStore::default();
4633        let pseudonym = HoprPseudonym::random();
4634        let relayer = HoprKeyIdent::from(1u32);
4635
4636        let large = 600;
4637        let small = 200;
4638        store.admit(&pseudonym, large);
4639        store.admit(&pseudonym, small);
4640
4641        // The narrower successor target would put the ceiling at 300; the fill below is past it, so any
4642        // eviction would prove the re-admission had narrowed the ring.
4643        let fill: Vec<(HoprSurbId, HoprSurb)> = (0..500u64)
4644            .map(|i| Ok((i.to_be_bytes(), surb_via(relayer, DIRECT)?)))
4645            .collect::<anyhow::Result<_>>()?;
4646        assert_eq!(
4647            SurbInsertOutcome {
4648                retained: fill.len(),
4649                evicted: 0,
4650                evicted_shares: 0,
4651                superseded: 0
4652            },
4653            store.insert_surbs(pseudonym, fill),
4654            "a smaller successor target must not narrow the ceiling the predecessor already established"
4655        );
4656
4657        Ok(())
4658    }
4659
4660    /// An admitted insert that folds in a quarantine ring left by the race around `admit` reports what
4661    /// the fold-in took: SURBs of an older generation the admitted ring refuses were booked when their
4662    /// packets arrived, and only this outcome tells the decoder they left.
4663    #[test]
4664    fn the_admitted_arm_must_report_what_its_fold_in_superseded() -> anyhow::Result<()> {
4665        let store = MemorySurbStore::default();
4666        let pseudonym = HoprPseudonym::random();
4667        let relayer = HoprKeyIdent::from(1u32);
4668
4669        let _token = store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
4670        let admitted = AdmittedRing::clone(
4671            &store
4672                .admitted_surbs_per_pseudonym
4673                .get(&pseudonym)
4674                .context("the Session's admitted entry must exist")?,
4675        );
4676        store.insert_surbs_into_admitted(
4677            &pseudonym,
4678            admitted.clone(),
4679            vec![([1u8; 8], surb_via(relayer, DIRECT)?)],
4680            1,
4681        );
4682
4683        // An insert that routed to the quarantine just before `admit` left an older generation there.
4684        store.push_into_quarantine(
4685            &pseudonym,
4686            vec![
4687                ([2u8; 8], surb_via(relayer, DIRECT)?),
4688                ([3u8; 8], surb_via(relayer, DIRECT)?),
4689            ],
4690            0,
4691        );
4692
4693        let outcome =
4694            store.insert_surbs_into_admitted(&pseudonym, admitted, vec![([4u8; 8], surb_via(relayer, DIRECT)?)], 1);
4695        assert_eq!(
4696            SurbInsertOutcome {
4697                retained: 2,
4698                evicted: 0,
4699                evicted_shares: 0,
4700                superseded: 2
4701            },
4702            outcome,
4703            "the two quarantined SURBs the newer generation refused were booked when they arrived, so their leaving \
4704             must reach the decoder"
4705        );
4706        assert!(
4707            store.quarantine_surbs.get(&pseudonym).is_none(),
4708            "the fold-in drained the quarantine ring"
4709        );
4710        Ok(())
4711    }
4712
4713    /// A Session that announces a *larger* target mid-life must get a ring wide enough to hold it.
4714    ///
4715    /// This is the gnosis_vpn-client shape (gnosis/gnosis_vpn#739): the client ramps its SURB
4716    /// balancer target from a ping tier (688) to the main tier (~6,900) a few seconds after the
4717    /// Session opens, and announces each step with a `BalancerTarget` keep-alive. `admit` ran once,
4718    /// at establishment, off the *first* target — so the ring was sized for 688 and stayed there
4719    /// while the Entry minted toward 6,900. Every SURB past the old ceiling was evicted, taking the
4720    /// PIX share it carried with it, and the Exit then ran dry exactly when the deposit confirmed.
4721    ///
4722    /// The property: raising the announced target raises the resident ring's ceiling, in place, with
4723    /// nothing held discarded — the same re-admission path a successor Session takes.
4724    #[test]
4725    fn a_raised_announced_target_must_widen_the_resident_ring() -> anyhow::Result<()> {
4726        let store = MemorySurbStore::default();
4727        let pseudonym = HoprPseudonym::random();
4728        let relayer = HoprKeyIdent::from(1u32);
4729
4730        // The ping tier: 688 × 1.5 = 1,032 slots, which is what the exit held in the report.
4731        let ping_target = 688;
4732        let ping_capacity = store.admitted_ring_capacity(ping_target);
4733        assert_eq!(1_032, ping_capacity, "fixture: the ping-tier ceiling");
4734
4735        let token = store.admit(&pseudonym, ping_target);
4736
4737        // The Entry ramps to its main tier and announces it. Before the fix the ring stayed at 1,032.
4738        let main_target = 6_887;
4739        store.raise_admitted_capacity(&pseudonym, token, main_target);
4740
4741        // A fill one SURB past the old ceiling but well inside the new one must be retained whole.
4742        let fill: Vec<(HoprSurbId, HoprSurb)> = (0..(ping_capacity as u64 + 1))
4743            .map(|i| Ok((i.to_be_bytes(), surb_via(relayer, DIRECT)?)))
4744            .collect::<anyhow::Result<_>>()?;
4745        assert_eq!(
4746            SurbInsertOutcome {
4747                retained: fill.len(),
4748                evicted: 0,
4749                evicted_shares: 0,
4750                superseded: 0
4751            },
4752            store.insert_surbs(pseudonym, fill),
4753            "a raised announcement must widen the ring past the target the Session was admitted with"
4754        );
4755
4756        Ok(())
4757    }
4758
4759    /// A raise must widen only the admission it names.
4760    ///
4761    /// A pseudonym is client-chosen and reusable, and a teardown's retire is deferred, so a
4762    /// successor Session can be admitted on the same pseudonym while a stale announcement is still
4763    /// in flight. Widening whatever ring is resident there would size the successor's ring from its
4764    /// predecessor's ramp — and the reverse, a stale *smaller* target, is worse: the ceiling only
4765    /// ever grows, so the smallest target ever named would win for good.
4766    #[test]
4767    fn a_raise_must_not_widen_a_successors_ring() -> anyhow::Result<()> {
4768        let store = MemorySurbStore::default();
4769        let pseudonym = HoprPseudonym::random();
4770        let relayer = HoprKeyIdent::from(1u32);
4771
4772        let stale = store.admit(&pseudonym, 200);
4773        let successor = store.admit(&pseudonym, 200);
4774        assert_ne!(stale, successor, "fixture: each admission mints its own number");
4775
4776        store.raise_admitted_capacity(&pseudonym, stale, 6_887);
4777
4778        // The predecessor's target would give a ring of 10,330; the successor's own 200 gives 300.
4779        let fill: Vec<(HoprSurbId, HoprSurb)> = (0..301u64)
4780            .map(|i| Ok((i.to_be_bytes(), surb_via(relayer, DIRECT)?)))
4781            .collect::<anyhow::Result<_>>()?;
4782        let outcome = store.insert_surbs(pseudonym, fill);
4783        assert_eq!(
4784            300, outcome.retained,
4785            "a stale raise must leave the successor's ring at the successor's own ceiling"
4786        );
4787        assert_eq!(
4788            1, outcome.evicted,
4789            "and the SURB past that ceiling must be the only one dropped"
4790        );
4791
4792        Ok(())
4793    }
4794
4795    /// The admitted arm: a batch for an admitted pseudonym must land in the entry `admit` installed,
4796    /// used as it stands — the real `admit` already promoted the quarantine ring and stamped it with
4797    /// the number the SessionManager threads back to `retire`. Calling `admit` again would mint a
4798    /// fresh number the manager's token no longer names, and the Session's deferred retire would then
4799    /// match nothing: the ring would leak until a teardown that never comes, and the retire would be
4800    /// booked as stale.
4801    ///
4802    /// The test drives the arm directly with the entry `admit` produced, and then checks the
4803    /// properties that matter: the epoch the manager holds is unchanged, the SURB landed in the
4804    /// admitted ring, and a retire with the manager's token still releases it.
4805    #[test]
4806    fn the_admitted_arm_must_reuse_the_admission_the_session_manager_holds() -> anyhow::Result<()> {
4807        let store = MemorySurbStore::default();
4808        let pseudonym = HoprPseudonym::random();
4809        let relayer = HoprKeyIdent::from(1u32);
4810
4811        // The Session is established; `admit` mints the number the manager stores in the slot's
4812        // admission token and promotes anything the quarantine already held.
4813        let token = store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
4814
4815        // The insert finds the entry `admit` installed and hands the batch to the admitted arm with
4816        // it — the path the old code took through a second `admit`.
4817        let admitted = store
4818            .admitted_surbs_per_pseudonym
4819            .get(&pseudonym)
4820            .context("the Session's admitted entry must exist")?;
4821        // `AdmittedRing::clone`, not the deref'd ring's: the arm takes the whole entry, epoch and all.
4822        let admitted = AdmittedRing::clone(&admitted);
4823        let outcome =
4824            store.insert_surbs_into_admitted(&pseudonym, admitted, vec![([1u8; 8], surb_via(relayer, DIRECT)?)], 0);
4825        assert_eq!(
4826            SurbInsertOutcome {
4827                retained: 1,
4828                evicted: 0,
4829                evicted_shares: 0,
4830                superseded: 0
4831            },
4832            outcome,
4833            "the batch must be retained in the admitted ring, not strained against the quarantine cap"
4834        );
4835
4836        let admitted = store
4837            .admitted_surbs_per_pseudonym
4838            .get(&pseudonym)
4839            .context("the admitted entry must still exist")?;
4840        assert_eq!(
4841            token,
4842            admitted.epoch(),
4843            "the admission number the manager holds must be untouched — a second `admit` here would have minted a \
4844             fresh one its retire can never match"
4845        );
4846        assert_eq!(1, admitted.len(), "the racing batch must be held in the admitted ring");
4847        assert!(
4848            store.quarantine_surbs.get(&pseudonym).is_none(),
4849            "nothing may be left behind in the quarantine the promotion already drained"
4850        );
4851
4852        // The teardown, carrying the manager's token, still releases the ring: the leak the second
4853        // `admit` would have caused is what this asserts away.
4854        store.retire(&pseudonym, token);
4855        assert!(
4856            store.admitted_surbs_per_pseudonym.get(&pseudonym).is_none(),
4857            "the manager's own token must still retire the Session's ring"
4858        );
4859
4860        Ok(())
4861    }
4862
4863    /// Retiring a Session releases only what the admitted class holds: the SURBs go with the Session,
4864    /// but a pseudonym that was never admitted is untouched — as is anything still sitting in the
4865    /// quarantine, which expires on its own short TTI without any teardown bookkeeping.
4866    #[test]
4867    fn retire_should_release_only_the_admitted_class() -> anyhow::Result<()> {
4868        let store = MemorySurbStore::default();
4869        let pseudonym = HoprPseudonym::random();
4870        let other = HoprPseudonym::random();
4871        let relayer = HoprKeyIdent::from(1u32);
4872
4873        let token = store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
4874        store.insert_surbs(pseudonym, vec![([1u8; 8], surb_via(relayer, DIRECT)?)]);
4875        store.insert_surbs(other, vec![([2u8; 8], surb_via(relayer, DIRECT)?)]);
4876
4877        store.retire(&pseudonym, token);
4878
4879        assert!(
4880            store.find_surb(SurbMatcher::Pseudonym(pseudonym)).is_none(),
4881            "retired SURBs must not be handed out"
4882        );
4883        assert!(
4884            store.admitted_surbs_per_pseudonym.get(&pseudonym).is_none(),
4885            "the admitted ring must be gone"
4886        );
4887        assert!(
4888            store.find_surb(SurbMatcher::Pseudonym(other)).is_some(),
4889            "an unadmitted pseudonym's SURBs are not the retired Session's to release"
4890        );
4891        // Retiring again must be a no-op, not a panic: teardown paths can overlap.
4892        store.retire(&pseudonym, token);
4893
4894        Ok(())
4895    }
4896
4897    /// The regression test for the deferred-retire hazard: a teardown whose retire was pushed past the
4898    /// packet pipeline's SURB-resolution window must not destroy a ring a successor Session admitted
4899    /// on the same client-chosen pseudonym in the meantime.
4900    ///
4901    /// Re-admitting `pseudonym` between the first admission and the retire stands in for the successor;
4902    /// the stale token from the first admission then stands in for the retire the teardown defers.
4903    /// The successor's ring must survive it, contents and all — anything less and the successor would
4904    /// go on inserting its SURBs into the small un-admitted quarantine with nothing logged anywhere.
4905    #[test]
4906    fn a_stale_retire_must_not_clobber_a_successor_admissions_ring() -> anyhow::Result<()> {
4907        let store = MemorySurbStore::default();
4908        let pseudonym = HoprPseudonym::random();
4909        let relayer = HoprKeyIdent::from(1u32);
4910
4911        let stale_token = store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
4912
4913        // The successor's admission, standing in for the Session that was established while the first
4914        // Session's teardown was still waiting out the SURB-resolution window. It mints a fresh token
4915        // and keeps what the admitted entry already holds, so the SURB below survives it.
4916        let successor_token = store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
4917        store.insert_surbs(pseudonym, vec![([1u8; 8], surb_via(relayer, DIRECT)?)]);
4918        assert!(
4919            store.find_surb(SurbMatcher::Pseudonym(pseudonym)).is_some(),
4920            "the successor's SURB must resolve before the stale retire fires"
4921        );
4922
4923        // Re-insert, since the probe above spent the ring's only SURB.
4924        store.insert_surbs(pseudonym, vec![([1u8; 8], surb_via(relayer, DIRECT)?)]);
4925        store.retire(&pseudonym, stale_token);
4926
4927        assert_ne!(
4928            stale_token, successor_token,
4929            "two admissions of one pseudonym must not share a token, or no retire could tell them apart"
4930        );
4931        assert!(
4932            store
4933                .admitted_surbs_per_pseudonym
4934                .get(&pseudonym)
4935                .context("the successor's admitted ring must still exist")?
4936                .epoch()
4937                == successor_token,
4938            "the stale retire must not have disturbed the successor's admission number"
4939        );
4940        assert_eq!(
4941            1,
4942            store
4943                .admitted_surbs_per_pseudonym
4944                .get(&pseudonym)
4945                .context("the successor's admitted ring must still exist")?
4946                .len(),
4947            "the successor's SURB must still be held"
4948        );
4949        assert!(
4950            store.find_surb(SurbMatcher::Pseudonym(pseudonym)).is_some(),
4951            "and it must still be spendable — the deferred retire of the Session before it must not have invalidated \
4952             the successor's return path"
4953        );
4954
4955        // The successor's own teardown, carrying its own token, still works.
4956        store.retire(&pseudonym, successor_token);
4957        assert!(
4958            store.admitted_surbs_per_pseudonym.get(&pseudonym).is_none(),
4959            "a retire whose token matches the current admission must still release the ring"
4960        );
4961
4962        Ok(())
4963    }
4964
4965    /// A retire whose token names no admission must be a no-op: a rolled-back Session was never
4966    /// admitted, and its teardown still runs the retire through the same seam as every other teardown.
4967    #[test]
4968    fn a_retire_with_an_unknown_token_must_not_touch_any_ring() -> anyhow::Result<()> {
4969        let store = MemorySurbStore::default();
4970        let pseudonym = HoprPseudonym::random();
4971        let relayer = HoprKeyIdent::from(1u32);
4972
4973        let token = store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
4974        store.insert_surbs(pseudonym, vec![([1u8; 8], surb_via(relayer, DIRECT)?)]);
4975        let wrong_token = store.admit(&HoprPseudonym::random(), MIN_SURB_RB_CAPACITY);
4976
4977        store.retire(&pseudonym, wrong_token);
4978
4979        assert!(
4980            store
4981                .admitted_surbs_per_pseudonym
4982                .get(&pseudonym)
4983                .context("the admitted ring must still exist")?
4984                .epoch()
4985                == token,
4986            "a token minted for another pseudonym must not release this one's ring"
4987        );
4988        assert_eq!(
4989            1,
4990            store
4991                .admitted_surbs_per_pseudonym
4992                .get(&pseudonym)
4993                .context("the admitted ring must still exist")?
4994                .len(),
4995            "and its SURB must still be held"
4996        );
4997
4998        Ok(())
4999    }
5000
5001    /// Only `admit` may create an admitted entry; an insert that finds none must route to the
5002    /// quarantine.
5003    ///
5004    /// The failure this rules out: a deferred `retire` removes the key between `insert_surbs`'
5005    /// admission test and its entry lookup, and an `or_insert_with` there would recreate the ring at
5006    /// epoch `0` — which no retire matches, so the entry leaks until size eviction. (The successor
5007    /// `admit` that later re-stamps it does raise its capacity, but the leak until size eviction is
5008    /// reason enough to route such a batch to the quarantine, where it belongs.)
5009    #[test]
5010    fn an_insert_must_not_create_an_admitted_entry() -> anyhow::Result<()> {
5011        let store = MemorySurbStore::default();
5012        let pseudonym = HoprPseudonym::random();
5013        let relayer = HoprKeyIdent::from(1u32);
5014
5015        // A Session was admitted and retired before this batch arrived: the admitted entry is gone.
5016        let token = store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
5017        store.retire(&pseudonym, token);
5018        assert!(
5019            store.admitted_surbs_per_pseudonym.get(&pseudonym).is_none(),
5020            "the retire must have removed the admitted entry"
5021        );
5022
5023        let outcome = store.insert_surbs(pseudonym, vec![([1u8; 8], surb_via(relayer, DIRECT)?)]);
5024
5025        assert_eq!(
5026            SurbInsertOutcome {
5027                retained: 1,
5028                evicted: 0,
5029                evicted_shares: 0,
5030                superseded: 0
5031            },
5032            outcome,
5033            "the batch must be retained, in the quarantine"
5034        );
5035        assert!(
5036            store.admitted_surbs_per_pseudonym.get(&pseudonym).is_none(),
5037            "an insert must never resurrect an admitted entry — only `admit` may create one"
5038        );
5039        assert!(
5040            store.quarantine_surbs.get(&pseudonym).is_some(),
5041            "the unadmitted batch belongs to the quarantine"
5042        );
5043
5044        Ok(())
5045    }
5046
5047    /// An insert whose admission lookup ran just before `admit` installed the entry pushes its batch
5048    /// into the quarantine — and must not leave it there. Once an admitted entry exists `find_surb`
5049    /// reads only the admitted ring, so a batch stranded in the quarantine would be invisible to the
5050    /// Session until a later admitted insert happened to fold it in, or the quarantine's TTI, cap or
5051    /// budget drain discarded it.
5052    ///
5053    /// The test stands in for that race by admitting first and then driving the quarantine arm
5054    /// directly, as the insert whose lookup came too early would.
5055    #[test]
5056    fn a_batch_routed_to_the_quarantine_just_before_admission_must_reach_the_admitted_ring() -> anyhow::Result<()> {
5057        let store = MemorySurbStore::default();
5058        let pseudonym = HoprPseudonym::random();
5059        let relayer = HoprKeyIdent::from(1u32);
5060
5061        let token = store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
5062        let outcome = store.insert_surbs_into_quarantine(&pseudonym, vec![([1u8; 8], surb_via(relayer, DIRECT)?)], 0);
5063
5064        assert_eq!(
5065            SurbInsertOutcome {
5066                retained: 1,
5067                evicted: 0,
5068                evicted_shares: 0,
5069                superseded: 0
5070            },
5071            outcome,
5072            "the outcome must report what the admitted ring holds once the batch is folded in"
5073        );
5074        assert!(
5075            store.quarantine_surbs.get(&pseudonym).is_none(),
5076            "the re-check must have folded the quarantine ring into the admitted one"
5077        );
5078        let admitted = store
5079            .admitted_surbs_per_pseudonym
5080            .get(&pseudonym)
5081            .context("the admitted entry must still exist")?;
5082        assert_eq!(1, admitted.len(), "the batch must now be held in the admitted ring");
5083        assert_eq!(
5084            token,
5085            admitted.epoch(),
5086            "the fold must leave the admission number alone"
5087        );
5088        assert_eq!(
5089            0,
5090            store.quarantine_budget.load(Ordering::Relaxed),
5091            "the folded SURB no longer counts against the quarantine budget"
5092        );
5093        let found = store
5094            .find_surb(SurbMatcher::Pseudonym(pseudonym))
5095            .context("the batch must be spendable by the admitted Session")?;
5096        assert_eq!([1u8; 8], found.sender_id.surb_id());
5097
5098        Ok(())
5099    }
5100
5101    /// The same race, run for real: an insert and the admission of its pseudonym on two threads. In
5102    /// every interleaving the batch must end up in the admitted ring and nothing in the quarantine —
5103    /// `admit` installs its entry before it promotes, and both the promotion and the quarantine push
5104    /// are serialised per key, so a push either precedes the promotion or is followed by a re-check
5105    /// that sees the entry.
5106    #[test]
5107    fn concurrent_insert_and_admission_must_never_strand_a_batch_in_the_quarantine() -> anyhow::Result<()> {
5108        let store = MemorySurbStore::default();
5109        let surb = surb_via(HoprKeyIdent::from(1u32), DIRECT)?;
5110
5111        for round in 0..256u32 {
5112            let pseudonym = HoprPseudonym::random();
5113            let start = std::sync::Barrier::new(2);
5114            std::thread::scope(|s| {
5115                s.spawn(|| {
5116                    start.wait();
5117                    store.insert_surbs(pseudonym, vec![([round as u8; 8], surb.clone())]);
5118                });
5119                s.spawn(|| {
5120                    start.wait();
5121                    store.admit(&pseudonym, MIN_SURB_RB_CAPACITY);
5122                });
5123            });
5124
5125            assert_eq!(
5126                0,
5127                store.quarantine_surbs.get(&pseudonym).map_or(0, |ring| ring.len()),
5128                "round {round}: no SURB may be left behind in the quarantine"
5129            );
5130            assert_eq!(
5131                1,
5132                store
5133                    .admitted_surbs_per_pseudonym
5134                    .get(&pseudonym)
5135                    .context("the admitted entry must exist")?
5136                    .len(),
5137                "round {round}: the batch must be held in the admitted ring"
5138            );
5139        }
5140        assert_eq!(
5141            0,
5142            store.quarantine_budget.load(Ordering::Relaxed),
5143            "every batch was promoted, so the quarantine budget must be back at zero"
5144        );
5145
5146        Ok(())
5147    }
5148
5149    /// A lookup can empty a quarantine ring without removing its cache entry, so the quarantine can
5150    /// hold many rings that free no budget when shed. The drain must pass over those rather than spend
5151    /// its victims on them and then refuse a batch that shedding a ring which does hold SURBs would
5152    /// have made room for.
5153    #[test]
5154    fn the_budget_drain_must_not_spend_its_victims_on_emptied_rings() -> anyhow::Result<()> {
5155        // One ring may hold the whole budget, so a single pseudonym can exhaust it while hundreds of
5156        // others sit empty — several times the drain's 64 victims per pass.
5157        let store = MemorySurbStore::new(SurbStoreConfig {
5158            quarantine_surb_budget: 4096,
5159            quarantine_rb_capacity: 4096,
5160            ..Default::default()
5161        });
5162        let surb = surb_via(HoprKeyIdent::from(1u32), DIRECT)?;
5163
5164        for i in 0..512u64 {
5165            let emptied = HoprPseudonym::random();
5166            store.insert_surbs(emptied, vec![(i.to_be_bytes(), surb.clone())]);
5167            store
5168                .find_surb(SurbMatcher::Pseudonym(emptied))
5169                .context("precondition: the SURB must resolve")?;
5170        }
5171        let full = HoprPseudonym::random();
5172        store.insert_surbs(full, (0..4096u64).map(|i| (i.to_be_bytes(), surb.clone())).collect());
5173        assert_eq!(
5174            store.cfg.quarantine_surb_budget,
5175            store.quarantine_budget.load(Ordering::Relaxed),
5176            "precondition: the one full ring exhausts the budget"
5177        );
5178
5179        let fresh = HoprPseudonym::random();
5180        let outcome = store.insert_surbs(fresh, vec![([1u8; 8], surb.clone())]);
5181
5182        assert_eq!(
5183            1, outcome.retained,
5184            "the drain must have shed the one ring holding SURBs, not refused the batch"
5185        );
5186        assert!(
5187            store.quarantine_surbs.get(&full).is_none(),
5188            "the full ring is the one the drain had to shed"
5189        );
5190
5191        Ok(())
5192    }
5193
5194    /// One pass of the drain sheds a bounded number of rings. When that frees less than the batch
5195    /// needs, the drain must keep going rather than refuse a batch it could still have made room for.
5196    #[test]
5197    fn the_budget_drain_must_keep_shedding_until_the_batch_fits() -> anyhow::Result<()> {
5198        // One SURB per ring: a pass of 64 rings frees 64 SURBs, less than the batch below needs. The
5199        // cache is sized well above the rings created, so only the drain sheds any.
5200        let store = MemorySurbStore::new(SurbStoreConfig {
5201            quarantine_surb_budget: 4096,
5202            quarantine_rb_capacity: 1,
5203            quarantine_max_pseudonyms: 8192,
5204            ..Default::default()
5205        });
5206        let surb = surb_via(HoprKeyIdent::from(1u32), DIRECT)?;
5207
5208        for i in 0..4096u64 {
5209            store.insert_surbs(HoprPseudonym::random(), vec![(i.to_be_bytes(), surb.clone())]);
5210        }
5211        assert_eq!(
5212            store.cfg.quarantine_surb_budget,
5213            store.quarantine_budget.load(Ordering::Relaxed),
5214            "precondition: the rings exhaust the budget"
5215        );
5216
5217        let fresh = HoprPseudonym::random();
5218        let batch: Vec<_> = (0..100u64).map(|i| (i.to_be_bytes(), surb.clone())).collect();
5219        let outcome = store.insert_surbs(fresh, batch);
5220
5221        // A one-SURB ring keeps the newest of the batch and drops the rest; a refusal would have kept
5222        // none of it.
5223        assert_eq!(
5224            SurbInsertOutcome {
5225                retained: 1,
5226                evicted: 99,
5227                evicted_shares: 0,
5228                superseded: 0
5229            },
5230            outcome,
5231            "the drain must have freed room for the whole batch over several passes"
5232        );
5233        let resident: usize = store.quarantine_surbs.iter().map(|(_, ring)| ring.len()).sum();
5234        assert_eq!(
5235            resident,
5236            store.quarantine_budget.load(Ordering::Relaxed),
5237            "the budget counter must still track what the quarantine holds"
5238        );
5239
5240        Ok(())
5241    }
5242
5243    /// Probe replies resolve against unadmitted pseudonyms (a probe names whatever pseudonym it
5244    /// replies to), so `find_surb` must consult the quarantine — and must *not* promote what it finds
5245    /// there: which pseudonym deserves admission is decided by the Session lifecycle, and the matcher
5246    /// names a pseudonym the counterparty chose.
5247    #[test]
5248    fn find_surb_should_consult_quarantine_for_probe_replies() -> anyhow::Result<()> {
5249        let store = MemorySurbStore::default();
5250        let pseudonym = HoprPseudonym::random();
5251        let relayer = HoprKeyIdent::from(1u32);
5252
5253        store.insert_surbs(pseudonym, vec![([3u8; 8], surb_via(relayer, DIRECT)?)]);
5254
5255        let found = store
5256            .find_surb(SurbMatcher::Pseudonym(pseudonym))
5257            .context("a quarantined SURB must still resolve")?;
5258        assert_eq!([3u8; 8], found.sender_id.surb_id());
5259        assert!(
5260            store.admitted_surbs_per_pseudonym.get(&pseudonym).is_none(),
5261            "a pop must not promote the pseudonym into the admitted class"
5262        );
5263        assert!(
5264            store.quarantine_surbs.get(&pseudonym).is_some(),
5265            "and the pseudonym stays in the quarantine it came from"
5266        );
5267
5268        Ok(())
5269    }
5270
5271    /// The new config fields each enforce their floor, and a configuration file that predates them —
5272    /// with none of the six present — still loads, because every one carries its own serde default
5273    /// under `deny_unknown_fields`.
5274    #[cfg(feature = "serde")]
5275    #[test]
5276    fn surb_store_config_should_reject_out_of_range_quarantine_and_budget_fields() -> anyhow::Result<()> {
5277        use serde::{
5278            Deserialize,
5279            de::value::{Error as SerdeError, MapDeserializer},
5280        };
5281        use validator::Validate;
5282
5283        // The config is deserialized from a key-value map, which is all a configuration file is to
5284        // serde — the same approach `surb_store_config_should_reject_a_lifo_pop_order` uses. The map
5285        // values are typed the way a file would carry them: numbers as `u64`, durations as humantime
5286        // strings.
5287        let load = |pairs: Vec<(&'static str, u64)>| -> anyhow::Result<SurbStoreConfig> {
5288            // The range checks are validator rules, not serde ones: they run when the loaded config
5289            // is validated, exactly as a configuration file's would be.
5290            let cfg = SurbStoreConfig::deserialize(MapDeserializer::<_, SerdeError>::new(pairs.into_iter()))
5291                .context("config must load")?;
5292            cfg.validate().context("config must validate")?;
5293            Ok(cfg)
5294        };
5295
5296        assert!(
5297            load(vec![("quarantine_rb_capacity", 0)]).is_err(),
5298            "a zero quarantine ring capacity cannot hold even one packet"
5299        );
5300        assert!(
5301            load(vec![("quarantine_max_pseudonyms", 63)]).is_err(),
5302            "below the quarantine pseudonym floor must be rejected"
5303        );
5304        assert!(
5305            load(vec![("quarantine_surb_budget", 4095)]).is_err(),
5306            "below the quarantine budget floor must be rejected"
5307        );
5308        assert!(
5309            load(vec![("admitted_max_pseudonyms", 0)]).is_err(),
5310            "an admitted cache of zero cannot hold even one session"
5311        );
5312
5313        // Each field at its boundary must load and validate.
5314        load(vec![
5315            ("quarantine_rb_capacity", 1),
5316            ("quarantine_max_pseudonyms", 64),
5317            ("quarantine_surb_budget", 4096),
5318            ("admitted_max_pseudonyms", 1),
5319            ("admitted_headroom_percent", 0),
5320        ])
5321        .context("boundary values must load and validate")?;
5322
5323        // A lifetime is validated by the custom rule floored at the SURB lifetime.
5324        let short = SurbStoreConfig {
5325            quarantine_lifetime: MINIMUM_SURB_LIFETIME - Duration::from_millis(1),
5326            ..Default::default()
5327        };
5328        assert!(
5329            short.validate().is_err(),
5330            "a quarantine lifetime below the SURB lifetime floor must be rejected"
5331        );
5332
5333        // A file that predates the new fields must still load: every field is defaulted.
5334        let legacy = load(vec![("rb_capacity", 100_000), ("distress_threshold", 500)])
5335            .context("a pre-admission config must still load")?;
5336        assert_eq!(16, legacy.quarantine_rb_capacity, "the quarantine cap is defaulted");
5337        assert_eq!(
5338            10_000, legacy.admitted_max_pseudonyms,
5339            "the admitted census is defaulted"
5340        );
5341        assert_eq!(
5342            DEFAULT_PENDING_SURB_MAX_BYTES, legacy.pending_surb_max_bytes,
5343            "the pending-SURB byte budget is defaulted"
5344        );
5345
5346        // The byte budget's floor is the map's real minimum, not one byte: a value below it would be
5347        // raised silently, so the validator rejects it rather than accepting a figure it ignores.
5348        assert!(
5349            load(vec![("pending_surb_max_bytes", 0)]).is_err(),
5350            "a zero pending-SURB budget must be rejected"
5351        );
5352        assert!(
5353            load(vec![("pending_surb_max_bytes", MINIMUM_PENDING_SURB_MAX_BYTES - 1)]).is_err(),
5354            "a budget below the floor must be rejected"
5355        );
5356        load(vec![("pending_surb_max_bytes", MINIMUM_PENDING_SURB_MAX_BYTES)])
5357            .context("a budget at the floor must load")?;
5358
5359        // And a ceiling, so a typo cannot ask for an unbounded map.
5360        assert!(
5361            load(vec![("pending_surb_max_bytes", MAXIMUM_PENDING_SURB_MAX_BYTES + 1)]).is_err(),
5362            "a budget above the 4 GiB ceiling must be rejected"
5363        );
5364        assert!(
5365            load(vec![("pending_surb_max_bytes", u64::MAX)]).is_err(),
5366            "u64::MAX must be rejected, not accepted as an unbounded map"
5367        );
5368        load(vec![("pending_surb_max_bytes", MAXIMUM_PENDING_SURB_MAX_BYTES)])
5369            .context("a budget at the ceiling must load")?;
5370
5371        Ok(())
5372    }
5373
5374    /// The validator prints only its message, not the constants it checks, so an operator can fix a
5375    /// rejected value only if the message names the bounds in bytes.
5376    #[test]
5377    fn the_budget_rejection_should_name_both_bounds_in_bytes() -> anyhow::Result<()> {
5378        use validator::Validate;
5379
5380        let rejected = SurbStoreConfig {
5381            pending_surb_max_bytes: 0,
5382            ..Default::default()
5383        };
5384        let message = rejected
5385            .validate()
5386            .err()
5387            .context("a zero budget must be rejected")?
5388            .to_string();
5389        for bound in [MINIMUM_PENDING_SURB_MAX_BYTES, MAXIMUM_PENDING_SURB_MAX_BYTES] {
5390            assert!(
5391                message.contains(&bound.to_string()),
5392                "the message must name {bound}: {message}"
5393            );
5394        }
5395        Ok(())
5396    }
5397}