tor-memquota

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

License: MIT OR Apache-2.0

lib.rs:

Intended behavour

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.)

• 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.

• 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).

• 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.

• 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