1 files changed, 78 insertions, 0 deletions
diff --git a/spec/dos-spec/memory-exhaustion.md b/spec/dos-spec/memory-exhaustion.md
new file mode 100644
index 0000000..14c1f6b
--- /dev/null
+++ b/spec/dos-spec/memory-exhaustion.md
@@ -0,0 +1,78 @@
+# Memory exhaustion { #oom }
+
+Memory exhaustion is a broad issue with many underlying causes. The Tor protocol requires clients, onion services, relays, and authorities to store various kind of information in buffers and caches.  But an attacker can use these buffers and queues to exhaust the memory of the a targeted Tor process, and force the operating system to kill that process.
+
+With this in mind, any Tor implementation (especially one that runs as a relay or onion service) must take steps to prevent memory-based denial-of-service attacks.
+
+## Detecting low memory { #oom-detection }
+
+The easiest way to notice you're out of memory would, in theory, be
+getting an error when you try to allocate more.  Unfortunately, some
+systems (e.g. Linux) won't actually give you an "out of memory"
+error when you're low on memory.  Instead, they overcommit and
+promise you memory that they can't actually provide… and then later on,
+they might kill processes that actually try to use more memory than
+they wish they'd given out.
+
+So in practice, the mainline Tor implementation uses a different
+strategy.  It uses a self-imposed "MaxMemInQueues" value as an
+upper bound for how much memory it's willing to allocate to certain
+kinds of queued usages.  This value can either be set by the user,
+or derived from a fraction of the total amount of system RAM.
+
+As of Tor 0.4.7.x, the MaxMemInQueues mechanism tracks the following
+kinds of allocation:
+
+- Relay cells queued on circuits.
+- Per-connection read or write buffers.
+- On-the-fly compression or decompression state.
+- Half-open stream records.
+- Cached onion service descriptors (hsdir only).
+- Cached DNS resolves (relay only).
+- GEOIP-based usage activity statistics.
+
+Note that directory caches aren't counted, since those are stored on
+disk and accessed via mmap.
+
+### Responding to low memory { #oom-response }
+
+If our allocations exceed MaxMemInQueues, then we take the following
+steps to reduce our memory allocation.
+
+*Freeing from caches*: For each of our onion service descriptor
+cache, our DNS cache, and our GEOIP statistics cache, we check
+whether they account for greater than 20% of our total allocation.
+If they do, we free memory from the offending cache until the total
+remaining is no more than 10% of our total allocation.
+
+When freeing entries from a cache, we aim to free (approximately)
+the oldest entries first.
+
+*Freeing from buffers*: After freeing data from caches, we see
+whether allocations are still above 90% of MaxMemInQueues. If they
+are, we try to close circuits and connections until we are below 90%
+of MaxMemInQueues.
+
+When deciding to what circuits to free, we sort them based on the
+age of the oldest data in their queues, and free the ones with the
+oldest data.  (For example, a circuit on which a single cell has
+been queued for 5 minutes would be freed before a circuit where 100
+cells have been queued for 5 seconds.)  "Data queued on a circuit"
+includes all data that we could drop if the circuit were destroyed:
+not only the cells on the circuit's relay cell queue, but also any bytes
+queued in buffers associated with streams or half-stream records
+attached to the circuit.
+
+We free non-tunneled directory connections according to a similar
+rule, according to the age of their oldest queued data.
+
+Upon freeing a circuit, a "DESTROY cell" must be sent in both
+directions.
+
+### Reporting low memory { #oom-reporting }
+
+We define a "low threshold" equal to 3/4 of MaxMemInQueues.  Every
+time our memory usage is above the low threshold, we record
+ourselves as being "under memory pressure".
+
+(This is not currently reported.)