Skip to main content

SurbRingBuffer

Struct SurbRingBuffer 

Source
pub struct SurbRingBuffer<S> {
    inner: Arc<Mutex<GenerationalBuffer<S>>>,
    capacity: Arc<AtomicUsize>,
}
Expand description

Ring buffer of SURBs and their IDs, all belonging to one pseudonym and therefore identified only by [HoprSurbId].

Backed by two VecDeque tiers that together are never allowed to exceed capacity: a push into a full buffer evicts first (see below for which SURB goes). Each tier is first in, first out: a pop consumes the oldest SURB of the tier it draws from, and so does an eviction. See SurbPopOrder for why that is the only order.

§Share-bearing SURBs first

A PIX share is sealed into a SURB when the Entry mints it, and reaches the Exit’s reconstructor only when the Exit uses that SURB. The Entry emits shares strictly in SSA-index order and has none left to seal once the committed cycle is exhausted, so every SURB it mints from then on is share-less. The next cycle’s shares are minted only after the Exit has requested that cycle, which is to say behind every share-less SURB minted in between. While the Entry produces SURBs faster than the Exit spends them — max_surbs_per_data_packet > 1 bypasses the balancer’s gate, so a 512 B write carries about six against the one a reply spends — that share-less backlog grows faster than it drains. In a single FIFO queue the next cycle’s shares are then reached late or never, and the supervisor closes the Session on RecoveryIdle (hoprnet#8466).

So the buffer keeps two tiers and always hands out the share-bearing one first. SurbShareInfo sorts each SURB into shares or plain as it arrives, and a pop takes from shares for as long as it holds anything and from plain after that, the oldest SURB of either first. The Entry emits shares in SSA-index order, so FIFO inside shares is also lowest-SSA-first.

Eviction follows the same priority, because a share-less SURB is only a return path while a share-bearing one is a return path and a share nothing can replace. A full buffer gives up share-less SURBs first, oldest first. A share-less newcomer is refused rather than evict a share. Only when nothing but shares is held does the oldest share go, as the oldest SURB always used to. A push reports how many SURBs it dropped and, of those, how many were shares, so that the loss that matters can be told from the routine one (see SurbInsertOutcome).

What this deliberately does not do: order shares across SSAs beyond these two tiers, retire the leftovers of an already-recovered SSA (the supervisor budgets for those, see its paid_recovery_tail), or insist that a batch belong to one SSA — a packet’s SURBs legitimately straddle a cycle boundary, or the step from carrying shares to carrying none.

§Generations: dropping SURBs for a superseded return path

A return path that dies deep in a multi-hop route is invisible to this replying side — nothing here can tell a stale SURB from a live one. The SURB creator can: it stamps every SURB of a batch with a generation (SurbReceiverInfo::generation) and bumps it whenever it changes the return path. This buffer keeps only the highest generation it has seen: the first push carrying a newer generation clears the buffer wholesale (both tiers) before inserting, so a return-path change takes effect on the very next reply rather than only once the stale SURBs drain — and stale SURBs are never handed out. A push carrying an older generation (a late/reordered batch) is discarded. Clearing is a per-path-change O(n) sweep, so pops need no per-SURB generation check.

§Why the capacity is a ceiling, not a reservation

The deques grow with occupancy rather than being sized at construction. The distinction matters because the pseudonym a buffer is filed under is chosen by whoever sent the packet: any HoprPacket::Final carrying a SURB reaches insert_surbs, which mints a buffer for a pseudonym it has never seen, with no Session or handshake behind it.

A structure that took its whole capacity upfront therefore let an unauthenticated peer reserve rb_capacity × size_of::<(HoprSurbId, S)>() of address space per pseudonym it invented — ~16.8 MB each at the default capacity, and max_pseudonyms of those. Resident memory was never the problem (untouched pages cost nothing), but the reservation is real to anything that accounts address space: strict overcommit, ulimit -v, vm.max_map_count.

Growth is geometric and amortised, and a deque never shrinks below its high-water mark, so a pseudonym that genuinely fills up still ends at the same footprint — and stops reallocating there, however long the steady-state overflow runs. It just has to earn it. Each tier keeps its own mark, so a pseudonym that has been filled with share-less SURBs and then with shares holds both: at most twice that footprint, and only after the buffer has been filled twice over.

Fields§

§inner: Arc<Mutex<GenerationalBuffer<S>>>§capacity: Arc<AtomicUsize>

Ceiling on the number of retained SURBs across both tiers; one is dropped (a share-less SURB if there is one) for every SURB that arrives once it is reached.

An Arc<AtomicUsize>, not a plain field, because a re-admission of the same pseudonym must be able to raise the ceiling of the ring already in place — admit keeps the resident ring rather than replacing it, and push reaches the ring only through &self. The Arc is what makes the raise visible: admit’s and_compute_with sees a clone of the cache value (moka’s Entry::value hands back the value it copied), so a raise through that clone would land on a buffer the cache does not hold — the same reason the admission epoch is behind an Arc. It only ever grows (raise_capacity is a fetch_max), so a later admission can never narrow a ceiling a live Session is already filling: capacity is monotone, and the ring a successor inherits is at least as wide as the widest target any admission of the pseudonym has asked for.

Implementations§

Source§

impl<S> SurbRingBuffer<S>

Source

pub fn new(capacity: usize) -> Self

Creates a buffer holding at most capacity (min 1, so a push is never a no-op) SURBs, popped oldest first within each tier.

Source

pub fn capacity(&self) -> usize

The ceiling on how many SURBs this buffer retains.

Source

fn raise_capacity(&self, to: usize)

Raises this buffer’s ceiling to at least to retained SURBs, never lowering it.

Two callers raise a ceiling, and both are about a target the ring was not sized for:

  • SurbStore::admit, when a pseudonym is re-admitted. It keeps the resident ring rather than replacing it (a Put of a fresh ring would trip the admitted cache’s Replaced listener and be booked as an eviction the ring never suffered), but the successor Session may have announced a larger SURB target than its predecessor.
  • MemorySurbStore::raise_admitted_capacity, when a live peer raises its announced target mid-Session and says so in a keep-alive.

Without this the resident ring would keep the smaller ceiling for the Session’s whole lifetime, and once its balancer filled past it, push would evict — losing PIX shares permanently, with nothing but an evicted count to show for it.

The raise is monotone on purpose. Narrowing on a re-admission would strand SURBs a live Session may already have inserted and would make the ceiling depend on admission order; fetch_max makes the effective ceiling the largest target any admission of the pseudonym has requested. A concurrent push racing the raise simply reads whichever ceiling it sees: growing it can only turn a would-be eviction into a clean insert.

Source§

impl<S> SurbRingBuffer<S>

Source

fn take_all(&self) -> (Option<u8>, Vec<(HoprSurbId, S)>)

Removes every SURB held and returns them with the generation they were pushed at.

Used to move a ring between the store’s two classes: the caller pushes the returned batch into the destination ring, whose own generation logic then decides how the two merge (append, supersede or discard). The returned order is pop order — share-bearing SURBs first, each tier oldest first — not the arrival order, which is the order that matters to a consumer.

Source

fn push_counting<I: IntoIterator<Item = (HoprSurbId, S)>>( &self, surbs: I, generation: u8, ) -> (SurbInsertOutcome, usize)
where S: SurbShareInfo,

Pushes all SURBs of one batch, stamped with generation, evicting past capacity.

A batch is minted at a single generation by the creator (one packet’s worth of SURBs), so a single generation covers the whole surbs iterator. Relative to the highest generation seen so far:

  • newer → both tiers are cleared before inserting, so SURBs for the superseded return path are dropped at once rather than lingering until they drain;
  • equal → the batch is appended (an ordinary refill);
  • older → the batch is discarded as a late/reordered leftover.

Each SURB is sorted into the share-bearing or the share-less tier by SurbShareInfo. Once at capacity, every one that arrives costs the buffer one SURB, share-less before share-bearing:

  • if a share-less SURB is held, the oldest of them is evicted;
  • else, a share-less newcomer is refused: it is only a return path, and a share-bearing SURB is that plus a share nothing can replace;
  • else, only shares are held and the newcomer carries one too, so the oldest share-bearing SURB is evicted.

A refused newcomer counts as evicted all the same: it is a SURB the buffer had no room for. Under PIX an evicted share-bearing SURB is a lost SSA share, not merely a lost SURB — see SurbStoreConfig::rb_capacity — so those are counted on their own, as evicted_shares: the exact number of shares the push lost to overflow, a subset of evicted.

Returns what the push did; the eviction count is what lets a caller notice the overflow at all, since dropping a SURB is otherwise indistinguishable from a clean insert. It counts capacity overflow only: SURBs dropped because a newer generation superseded them were already unusable, and reporting them as pressure would ask the creator to slow down because it re-planned its own return path. They are reported separately, as superseded: the whole of what a newer generation cleared, or the whole of an older-generation batch that was refused. The caller that tracks what the buffer holds adds the two, so that retained and its own count of what was received agree.

Also returns how many share-carrying SURBs the generation rule took out of play: the shares a newer generation cleared, or those of an older-generation batch it refused.

Source

pub fn pop_next_valid<F>(&self, is_valid: F) -> Option<PoppedSurb<S>>
where F: Fn(&HoprSurbId, &S) -> bool,

Pops the next SURB that is_valid accepts: a share-bearing one while any is held, the oldest of each tier first.

Destructive: rejected entries are discarded, not skipped, so an unusable SURB neither is handed out nor blocks those behind it. Pass only a validity test — a selective predicate (say, a routing preference) would drain the buffer. None once it is exhausted without a match.

is_valid runs outside the lock: it is caller-supplied and may take locks of its own, so calling it inside the critical section would invite lock-order inversion.

Source

fn len(&self) -> usize

Number of SURBs currently held, across both tiers.

Source

fn tier_lens(&self) -> (usize, usize)

Number of SURBs currently held in each tier, as (share-bearing, share-less): len split the way a pop sees it, share-bearing first. Both are read under one lock, so they are a consistent pair.

Source

pub fn pop_one_if_has_id(&self, id: &HoprSurbId) -> Option<PoppedSurb<S>>

Pops the next SURB (the one pop_next_valid would take first) only if it has the given ID.

Trait Implementations§

Source§

impl<S> Clone for SurbRingBuffer<S>

A second handle on the same buffer, for the moka caches that require Clone on their values.

Deliberately not a derived Clone and not a deep copy: it shares the inner lock and the capacity Arc, so a cloned handle and its original see the same SURBs and the same bound. Moving SURBs into a ring with a different ceiling is a take_all and a push.

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<S: Debug> Debug for SurbRingBuffer<S>

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<S> !RefUnwindSafe for SurbRingBuffer<S>

§

impl<S> !UnwindSafe for SurbRingBuffer<S>

§

impl<S> Freeze for SurbRingBuffer<S>

§

impl<S> Send for SurbRingBuffer<S>
where S: Send,

§

impl<S> Sync for SurbRingBuffer<S>
where S: Send,

§

impl<S> Unpin for SurbRingBuffer<S>

§

impl<S> UnsafeUnpin for SurbRingBuffer<S>

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
§

impl<ST, DT> CastableFrom<ST, Initialized, Initialized> for DT
where ST: ?Sized, DT: ?Sized,

§

impl<ST, DT> CastableFrom<ST, Uninit, Uninit> for DT
where ST: ?Sized, DT: ?Sized,

Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> DynClone for T
where T: Clone,

Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

§

impl<T> FutureExt for T

§

fn with_context(self, otel_cx: Context) -> WithContext<Self>

Attaches the provided Context to this type, returning a WithContext wrapper. Read more
§

fn with_current_context(self) -> WithContext<Self>

Attaches the current Context to this type, returning a WithContext wrapper. Read more
§

impl<T> Instrument for T

§

fn instrument(self, span: Span) -> Instrumented<Self>

Instruments this type with the provided [Span], returning an Instrumented wrapper. Read more
§

fn in_current_span(self) -> Instrumented<Self>

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> IntoEither for T

Source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts self into a Left variant of Either<Self, Self> if into_left is true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts self into a Left variant of Either<Self, Self> if into_left(&self) returns true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
§

impl<T> Pointable for T

§

const ALIGN: usize

The alignment of pointer.
§

type Init = T

The type for initializers.
§

unsafe fn init(init: <T as Pointable>::Init) -> usize

Initializes a with the given initializer. Read more
§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
§

impl<T> PolicyExt for T
where T: ?Sized,

§

fn and<P, B, E>(self, other: P) -> And<T, P>
where T: Sized + Policy<B, E>, P: Policy<B, E>,

Create a new Policy that returns [Action::Follow] only if self and other return Action::Follow. Read more
§

fn or<P, B, E>(self, other: P) -> Or<T, P>
where T: Sized + Policy<B, E>, P: Policy<B, E>,

Create a new Policy that returns [Action::Follow] if either self or other returns Action::Follow. Read more
§

impl<T> Read<Exclusive, BecauseExclusive> for T
where T: ?Sized,

Source§

impl<T> Same for T

Source§

type Output = T

Should always be Self
Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

§

fn vzip(self) -> V

§

impl<T> WithSubscriber for T

§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a [WithDispatch] wrapper. Read more
§

fn with_current_subscriber(self) -> WithDispatch<Self>

Attaches the current default Subscriber to this type, returning a [WithDispatch] wrapper. Read more