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}