Struct IptManager

pub(crate) struct IptManager<R, M> {
    imm: Immutable<R>,
    state: State<R, M>,
}

IPT Manager (for one hidden service)

Fields

imm: Immutable<R>

Immutable contents

state: State<R, M>

Mutable state

Implementations

impl<R: Runtime, M: Mockable<R>> IptManager<R, M>

pub(crate) fn new( runtime: R, dirprovider: Arc<dyn NetDirProvider>, nick: HsNickname, config: Receiver<Arc<OnionServiceConfig>>, output_rend_reqs: Sender<RendRequest>, shutdown: Receiver<Void>, state_handle: &InstanceStateHandle, mockable: M, keymgr: Arc<KeyMgr>, status_tx: IptMgrStatusSender, ) -> Result<Self, StartupError>

Create a new IptManager

pub(crate) fn launch_background_tasks( self, publisher: IptsManagerView, ) -> Result<(), StartupError>

Send the IPT manager off to run and establish intro points

fn all_ipts(&self) -> impl Iterator<Item = (&IptRelay, &Ipt)>

Iterate over all the IPTs we know about

Yields each IptRelay at most once.

fn current_ipts(&self) -> impl Iterator<Item = (&IptRelay, &Ipt)>

Iterate over the current IPTs

Yields each IptRelay at most once.

fn good_ipts(&self) -> impl Iterator<Item = (&IptRelay, &Ipt)>

Iterate over the current IPTs in Good state

fn ipt_errors(&self) -> impl Iterator<Item = &IptError>

Iterate over the current IPT errors.

Used when reporting our state as Recovering.

pub(crate) fn target_n_intro_points(&self) -> usize

Target number of intro points

pub(crate) fn max_n_intro_relays(&self) -> usize

Maximum number of concurrent intro point relays

fn idempotently_progress_things_now( &mut self, ) -> Result<Option<TrackingNow>, FatalError>

Make some progress, if possible, and say when to wake up again

Examines the current state and attempts to improve it.

If idempotently_progress_things_now makes any changes, it will return None. It should then be called again immediately.

Otherwise, it returns the time in the future when further work ought to be done: i.e., the time of the earliest timeout or planned future state change - as a TrackingNow.

In that case, the caller must call compute_iptsetstatus_publish, since the IPT set etc. may have changed.

Goals and algorithms

We attempt to maintain a pool of N established and verified IPTs, at N IPT Relays.

When we have fewer than N IPT Relays that have Establishing or Good IPTs (see below) and fewer than k*N IPT Relays overall, we choose a new IPT Relay at random from the consensus and try to establish an IPT on it.

(Rationale for the k*N limit: we do want to try to replace faulty IPTs, but we don’t want an attacker to be able to provoke us into rapidly churning through IPT candidates.)

When we select a new IPT Relay, we randomly choose a planned replacement time, after which it becomes Retiring.

Additionally, any IPT becomes Retiring after it has been used for a certain number of introductions (c.f. C Tor #define INTRO_POINT_MIN_LIFETIME_INTRODUCTIONS 16384.) When this happens we retain the IPT Relay, and make new parameters to make a new IPT at the same Relay.

An IPT is removed from our records, and we give up on it, when it is no longer Good or Establishing and all descriptors that mentioned it have expired.

(Until all published descriptors mentioning an IPT expire, we consider ourselves bound by those previously-published descriptors, and try to maintain the IPT. TODO: Allegedly this is unnecessary, but I don’t see how it could be.)

Performance

This function is at worst O(N) where N is the number of IPTs. When handling state changes relating to a particular IPT (or IPT relay) it needs at most O(1) calls to progress that one IPT to its proper new state.

See the performance note on run_once().

fn import_new_expiry_times( irelays: &mut [IptRelay], publish_set: &PublishIptSet, )

Import publisher’s updates to latest descriptor expiry times

Copies the last_descriptor_expiry_including_slop field from each ipt in publish_set to the corresponding ipt in self.

Performance

This function is at worst O(N) where N is the number of IPTs. See the performance note on run_once().

fn expire_old_expiry_times( &self, publish_set: &mut PublishIptSet, now: &TrackingNow, )

Expire old entries in publish_set.last_descriptor_expiry_including_slop

Deletes entries where now > last_descriptor_expiry_including_slop, ie, entries where the publication’s validity time has expired, meaning we don’t need to maintain that IPT any more, at least, not just because we’ve published it.

We may expire even entries for IPTs that we, the manager, still want to maintain. That’s fine: this is (just) the information about what we have previously published.

Performance

This function is at worst O(N) where N is the number of IPTs. See the performance note on run_once().

fn compute_iptsetstatus_publish( &mut self, now: &TrackingNow, publish_set: &mut PublishIptSet, ) -> Result<(), IptStoreError>

Compute the IPT set to publish, and update the data shared with the publisher

now is current time and also the earliest wakeup, which we are in the process of planning. The noted earliest wakeup can be updated by this function, for example, with a future time at which the IPT set ought to be published (eg, the status goes from Unknown to Uncertain).

IPT sets and lifetimes

We remember every IPT we have published that is still valid.

At each point in time we have an idea of set of IPTs we want to publish. The possibilities are:

• Certain: We are sure of which IPTs we want to publish. We try to do so, talking to hsdirs as necessary, updating any existing information. (We also republish to an hsdir if its descriptor will expire soon, or we haven’t published there since Arti was restarted.)

• Unknown: We have no idea which IPTs to publish. We leave whatever is on the hsdirs as-is.

• Uncertain: We have some IPTs we could publish, but we’re not confident about them. We publish these to a particular hsdir if:

  • our last-published descriptor has expired
  • or it will expire soon
  • or if we haven’t published since Arti was restarted.

The idea of what to publish is calculated as follows:

• If we have at least N Good IPTs: Certain. (We publish the “best” N IPTs for some definition of “best”. TODO: should we use the fault count? recency?)

• Unless we have at least one Good IPT: Unknown.

• Otherwise: if there are IPTs in Establishing, and they have been in Establishing only a short time [1]: Unknown; otherwise Uncertain.

The effect is that we delay publishing an initial descriptor by at most 1x the fastest IPT setup time, at most doubling the initial setup time.

Each update to the IPT set that isn’t Unknown comes with a proposed descriptor expiry time, which is used if the descriptor is to be actually published. The proposed descriptor lifetime for Uncertain is the minimum (30 minutes). Otherwise, we double the lifetime each time, unless any IPT in the previous descriptor was declared Faulty, in which case we reset it back to the minimum. TODO: Perhaps we should just pick fixed short and long lifetimes instead, to limit distinguishability.

(Rationale: if IPTs are regularly misbehaving, we should be cautious and limit our exposure to the damage.)

[1] NOTE: We wait a “short time” between establishing our first IPT, and publishing an incomplete (<N) descriptor - this is a compromise between availability (publishing as soon as we have any working IPT) and exposure and hsdir load (which would suggest publishing only when our IPT set is stable). One possible strategy is to wait as long again as the time it took to establish our first IPT. Another is to somehow use our circuit timing estimator.

Performance

This function is at worst O(N) where N is the number of IPTs. See the performance note on run_once().

fn publish_set_select(&self) -> VecDeque<&Ipt>

Select IPTs to publish, given that we have decided to publish something

Calculates set of ipts to publish, selecting up to the target N from the available good current IPTs. (Old, non-current IPTs, that we are trying to retire, are never published.)

The returned list is in the same order as our data structure: firstly, by the ordering in State.irelays, and then within each relay, by the ordering in IptRelay.ipts. Both of these are stable.

Performance

This function is at worst O(N) where N is the number of IPTs. See the performance note on run_once().

fn make_publish_set<'i>( selected: impl IntoIterator<Item = &'i Ipt>, lifetime: Duration, ) -> Result<IptSet, FatalError>

Produce a publish::IptSet, from a list of IPT selected for publication

Updates each chosen Ipt’s last_descriptor_expiry_including_slop

The returned IptSet set is in the same order as selected.

Performance

This function is at worst O(N) where N is the number of IPTs. See the performance note on run_once().

fn expire_old_ipts_external_persistent_state( &self, ) -> Result<(), StateExpiryError>

Delete persistent on-disk data (including keys) for old IPTs

More precisely, scan places where per-IPT data files live, and delete anything that doesn’t correspond to one of the IPTs in our main in-memory data structure.

Does not deal with deletion of data handled via storage handles (state_dir::StorageHandle), ipt_mgr/persist.rs etc.; those are one file for each service, so old data is removed as we rewrite them.

Does not deal with deletion of entire old hidden services.

(This function works on the basis of the invariant that every IPT in ipt_set::PublishIptSet is also an Ipt in ipt_mgr::State. See the comment in IptManager::import_new_expiry_times. If that invariant is violated, we would delete on-disk files for the affected IPTs. That’s fine since we couldn’t re-establish them anyway.)

async fn run_once( &mut self, publisher: &mut IptsManagerView, ) -> Result<ShutdownStatus, FatalError>

Run one iteration of the loop

Either do some work, making changes to our state, or, if there’s nothing to be done, wait until there is something to do.

Implementation approach

Every time we wake up we idempotently make progress by searching our whole state machine, looking for something to do. If we find something to do, we do that one thing, and search again. When we’re done, we unconditionally recalculate the IPTs to publish, and sleep.

This approach avoids the need for complicated reasoning about which state updates need to trigger other state updates, and thereby avoids several classes of potential bugs. However, it has some performance implications:

Performance

Events relating to an IPT occur, at worst, at a rate proportional to the current number of IPTs, times the maximum flap rate of any one IPT.

idempotently_progress_things_now can be called more than once for each such event, but only a finite number of times per IPT.

Therefore, overall, our work rate is O(N^2) where N is the number of IPTs. We think this is tolerable, but it does mean that the principal functions should be written with an eye to avoiding “accidentally quadratic” algorithms, because that would make the whole manager cubic. Ideally we would avoid O(N.log(N)) algorithms.

(Note that the number of IPTs can be significantly larger than the maximum target of 20, if the service is very busy so the intro points are cycling rapidly due to the need to replace the replay database.)

async fn main_loop_task(self, publisher: IptsManagerView)

IPT Manager main loop, runs as a task

Contains the error handling, including catching panics.

Trait Implementations

impl<R, M> Debug for IptManager<R, M>

where R: Debug, M: Debug,

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

Formats the value using the given formatter.