tor-memquota

Memory use quota, tracking and reclamation, for use in Tor DoS resistance

Compile-time features

• memquota (default) -- Actually enable memory quota tracking. Without this feature, all the actual functionality is stubbed out. This provides a convenient way of conditionally enabling memory tracking.

• full -- Enable all features above.

Experimental and unstable features

Note that the APIs enabled by these features are NOT covered by semantic versioning[^1] guarantees: we might break them or remove them between patch versions.

• testing: Additional APIs for testing, used in our whole-workspace tests.

• experimental: Enable all the above experimental features.

[^1]: Remember, semantic versioning is what makes various cargo features work reliably. To be explicit: if you want cargo update to only make safe changes, then you cannot enable these features.

License: MIT OR Apache-2.0

lib.rs:

Intended behaviour

In normal operation we try to track as little state as possible, cheaply. We do track total memory use in nominal bytes (but a little approximately).

When we exceed the quota, we engage a more expensive algorithm: we build a heap to select oldest victims, and we use the heap to keep reducing memory until we go below a low-water mark (hysteresis).

Key concepts

• Tracker: Instance of the memory quota system Each tracker has a notion of how much memory its participants are allowed to use, in aggregate. Tracks memory usage by all the Accounts and Participants. Different Trackers are completely independent.

• Account: all memory used within the same Account is treated equally, and reclamation also happens on an account-by-account basis. (Each Account is with one Tracker.)

  See the mq_queue docs for we use Accounts in Arti to track memory for the various queues.

• Participant: one data structure that uses memory. Each Participant is linked to one Account. An account has one or more Participants. (An Account can exist with zero Participants, but can't then claim memory.) A Participant provides a dyn IsParticipant to the memory system; in turn, the memory system provides the Participant with a Participation - a handle for tracking memory alloc/free.

  Actual memory allocation is handled by the participant itself, using the global heap: for each allocation, the Participant both calls claim and allocates the actual object, and later, both frees the actual object and calls release.

• Child Account/Parent Account: An Account may have a Parent. When a tracker requests memory reclamation from a Parent, it will also request it of all that Parent's Children (but not vice versa).

  The account structure and reclamation strategy for Arti is defined in tor-proto, and documented in tor_proto::memquota.

• Data age: Each Participant must be able to say what the oldest data is, that it is storing. The reclamation policy is to try to free the oldest data.

• Reclamation: When a Tracker decides that too much memory is being used, it will select a victim Account based on the data age. It will then ask every Participant in that Account, and every Participant in every Child of that Account, to reclaim memory. A Participant responds by freeing at least some memory, according to the reclamation request, and tells the Tracker when it has done so.

• Reclamation strategy: To avoid too-frequent reclamation, once reclamation has started, it will continue until a low-water mark is reached, significantly lower than the quota. I.e. the system has a hysteresis.

  The only currently implemented higher-level Participant is mq_queue, a queue which responds to a reclamation request by completely destroying itself, freeing all its data, and reporting it has been closed.

• Approximate (both in time and space): The memory quota system is not completely precise. Participants need not report their use precisely, but the errors should be reasonably small, and bounded. Likewise, the enforcement is not precise: reclamation may start slightly too early, or too late; but the memory use will be bounded below by O(number of participants) and above by O(1) (plus errors from the participants). Reclamation is not immediate, and is dependent on task scheduling; during memory pressure the quota may be exceeded; new allocations are not prevented while attempts at reclamation are ongoing.

Ownership and Arc keeping-alive

• Somewhere, someone must keep an Account to keep the account open. Ie, the principal object corresponding to the accountholder should contain an Account.

• Arc<MemoryTracker> holds Weak<dyn IsParticipant>. If the tracker finds the IsParticipant has vanished, it assumes this means that the Participant is being destroyed and it can treat all of the memory it claimed as freed.

• Each participant holds a Participation. A Participation may be invalidated by collapse of the underlying Account, which may be triggered in any number of ways.

• A Participation does not keep its Account alive. Ie, it has only a weak reference to the Account.

• A Participant's implementor of IsParticipant may hold a Participation. If the impl IsParticipant is also the principal accountholder object, it must hold an Account too.

• Child/parent accounts do not imply any keeping-alive relationship. It's just that a reclamation request to a parent (if it still exists) will also be made to its children.

    accountholder   =======================================>*  Participant
                                                               (impl IsParticipant)
          ||
          ||                                                     ^     ||
          ||                                                     |     ||
          ||                 global                     Weak<dyn>|     ||
          ||                     ||                              |     ||
          \/*                    \/                              |     ||
                                                                 |     ||
        Account  *===========>  MemoryTracker  ------------------'     ||
                                                                       ||
           ^                                                           ||
           |                                                           \/
           |
            `-------------------------------------------------*   Participation



    accountholder which is also directly the Participant ==============\
    (impl IsParticipant)                                              ||
                                          ^                           ||
          ||                              |                           ||
          ||                              |                           ||
          ||                 global       |Weak<dyn>                  ||
          ||                     ||       |                           ||
          \/                     \/       |                           ||
                                                                      ||
        Account  *===========>  MemoryTracker                         ||
                                                                      ||
           ^                                                          ||
           |                                                          \/
           |
            `-------------------------------------------------*   Participation

Panics and state corruption

This library is intended to be entirely panic-free, even in the case of accounting errors, arithmetic overflow, etc.

In the case of sufficiently bad account errors, a Participant, or a whole Account, or the whole MemoryQuotaTracker, may become unuseable, in which case methods will return errors with kind tor_error::ErrorKind::Internal.