cell-lifecycle.md
1 # Cell life cycle 2 3 **Important: this is up to date with 834a51c7eb795750015d653812fa7df89f7466b7** 4 5 Unless specified otherwise, this document describes 6 the *current* state of affairs. 7 8 > This document describes the cell delivery flow, 9 > *not* the high-level life cycle of a circuit or channel. 10 > You can read about about the life cycle of circuits and channels 11 > in the [`ClientCirc`] and [`Channel`] docs, respectively. 12 > 13 > Stream management and prioritization is also not covered here. 14 > See the `StreamMap`, `StreamPollSet` docs, and the use of `StreamMap` 15 > in the circuit reactor to learn about stream management. 16 17 ## TLDR 18 19 This diagram summarizes the message flows discussed in the rest of this doc: 20 21 ``` 22 23 ClientCirc 24 +-------------------------------------------+ 25 | | 26 | +-------------------------------------+ | 27 | | TX | | 28 | +-------------------------------------+ | 29 | | control: UnboundedSender<CtrlMsg> | | 30 | +-------------------------------------+ | 31 +---------------------||--------------------+ 32 || 33 || 34 || 35 (Unbounded MPSC channel) 36 || 37 || 38 Circuit reactor: || 39 +---------------------||-------------------------------------------------------+ 40 | \/ | 41 | +-------------------------------------+ | 42 | | RX | | 43 | +-------------------------------------+ | 44 | | control: UnboundedReceiver<CtrlMsg> | | 45 | +-------------------------------------+ | 46 | | 47 | ================== | 48 | === run_once() === | 49 | ================== | 50 | * control.poll_next() | 51 | * input.poll_next() | 52 | * chan_sender.poll_ready_unpin_bool() | 53 | * if chan_sender is ready and SENDME window is open | 54 | for each hop see if there are any cells to send | 55 | * chan_sender.poll_flush() | 56 | | 57 | +----------------------------+ | 58 | | RX | | 59 | |----------------------------| | 60 | | input: CircuitRxReceiver | | 61 | +----------------------------+ | 62 | /\ | 63 | || +----------------------------------------------+ | 64 | || | TX | | 65 | || |----------------------------------------------| | 66 | || | chan_sender: SometimesUnboundedSink< | | 67 | || | AnyChanCell, ChannelSender> | | 68 | || +----------------------------------------------+ | 69 | || || | 70 | || || | 71 +-----------------||-------------------------------------||--------------------+ 72 || || 73 (Bounded MPSC channel) (Bounded MPSC channel) 74 (size = 128) (size = CHANNEL_BUFFER_SIZE = 128) 75 || || 76 Channel reactor: || || 77 +------------------||-------------------------------------||--------------------+ 78 | || \/ | 79 | || +-------------------------------+ | 80 | || | RX | | 81 | || +-------------------------------+ | 82 | || | cells: Receiver<AnyChanCell> | | 83 | || +---------------+---------------+ | 84 | || | | 85 | || CircMap if output is ready, | 86 | +---------------||----------------------------+ cells.next() | 87 | | || ... | and deliver cell to sink | 88 | | || | | | 89 | | || CircEnt::Open | +--------------+ | 90 | | +-------------------------------+ | | | 91 | | | TX | | deliver message | | 92 | | CircId: |-------------------------------|<------------------+ | | 93 | | | CircuitRxSender | | to circuit reactor | | 94 | | +-------------------------------+ | | | | 95 | | | | | | 96 | | ... | | | | 97 | +---------------------------------------------+ | | | 98 | | | | 99 | | | | 100 | ================== input | | | 101 | === run_once() === +-----------------------+ | | 102 | ================== | ChannelCodec | | | 103 | / | +----------------+ | | | 104 | | * control.next() | | TLS stream | | | | 105 | select! | * input.next() | | +----------+ | | | | 106 | | * output ready to send | | | TCP sock | | | | | 107 | \ | | +----------+ | | | | 108 | | +----------------+ | | | 109 | +-----------------------+ | | 110 | | | 111 | | | 112 | output v | 113 | +--------------------------------+ | 114 | | ChannelCodec | | 115 | | +---------------------------+ | | 116 | | | TLS stream | | | 117 | | | +-----------------------+ | | | 118 | +-------------------------------------+ | | | TCP sock | | | | 119 | | RX | | | | (soon to be KIST sock)| | | | 120 | +-------------------------------------+ | | +-----------------------+ | | | 121 | | control: UnboundedReceiver<CtrlMsg> | | +---------------------------+ | | 122 | +-------------------------------------+ +--------------------------------+ | 123 | /\ | 124 +----------------------||-------------------------------------------------------+ 125 || 126 || 127 (Unbounded MPSC channel) 128 || 129 Channel || 130 +---------------------||--------------------+ 131 | || | 132 | +-------------------------------------+ | 133 | | TX | | 134 | +-------------------------------------+ | 135 | | control: UnboundedSender<CtrlMsg> | | 136 | +-------------------------------------+ | 137 +-------------------------------------------+ 138 139 ``` 140 141 ## Creating a channel 142 143 Channels are (typically) created using a `ChanBuilder` 144 (using its `ChannelFactory::connect_via_transport` impl). 145 The underlying connection (usually TCP) is established using the 146 `TransportImplHelper` contained within the `ChanBuilder`. 147 148 `ChanBuilder::connect_no_timeout` 149 (called from the `ChannelFactory::connect_via_transport` impl) 150 does all the work for creating and launching the channel. This function 151 * establishes the TCP connection 152 * performs the client handshake 153 * spawns the channel reactor in a separate task 154 155 > Note: the above describes the way client-initiated channels are launched. 156 > For relays, we will also have a separate `ChannelFactory`-like trait 157 > called `IncomingChannelFactory`, which is not described here. 158 159 `ChanBuilder::connect_no_timeout` returns a `Channel`, 160 which can be used to send control messages to the channel reactor, 161 or to obtain a `ChannelSender` that can directly send cells down the channel. 162 163 One thing to note here is that 164 after negotiating the link protocol, we wrap 165 the underlying transport stream in a [`futures_codec::Framed`] 166 (see `ChannelCodec`). 167 The stream is then `split()` (grep for `tls.split()`) 168 and its read/write handles are stored separately. 169 These become the `sink` and `stream` parts of the channel. 170 But note these aren't stored in `Channel` itself, 171 but in the channel *reactor* (as its `input` sink and `output` stream). 172 173 ## Creating a circuit 174 175 Once you have a channel, you can create a circuit. 176 177 Client circuits are created using `PendingClientCirc`. 178 You can obtain a `PendingClientCirc` and a corresponding circuit reactor 179 from `Channel::new_circ()`, which registers a new circuit with the channel reactor. 180 It does this by sending a `channel::CtrlMsg::AllocateCircuit` control message. 181 These control messages are sent over an *unbounded* MPSC channel 182 (see the `mpsc::UnboundedSender` `control` field in `Channel`). 183 184 After the circuit reactor is spawned, 185 it *awaits* on `wait_for_create` until it receives a control message, 186 which is expected to be either `CtrlMsg::Create` or `CtrlMsg::Shutdown`. 187 This is described further in the "Sending CREATE cells" section below. 188 189 ### Handling `AllocateCircuit` control messages 190 191 In the channel reactor (in `handle_control`): 192 * a new circuit ID is computed 193 * the circuit is added to the `self.circs` circuit map, 194 which maps circuit IDs to sinks that `ClientCircChanMsg`s[^1] can be written to. 195 (the *receiving* end of each sink is held 196 by its corresponding circuit reactor. 197 IOW, this is the channel the circuit reactor receives cells from). 198 The map entry is `CircEnt::Opening` entry, that is initially inert 199 200 To mark the circuit as open, the entry is replaced with a `CircEnt::Open` 201 entry using `CircMap::advance_from_opening`. 202 This `CircEnt::Open` entry contains the aforementioned `CircuitRxSender` sink 203 down which `ClientCircChanMsg` messages for this circuit are sent. 204 This is the sending end of an MPSC channel that has a buffer of size 128 205 (see `Channel::new_circ`). Its total capacity is 129 (`buffer-size + num-senders`). 206 207 **All of this is internal state management. 208 Nothing gets sent to the network at this point** 209 210 ### Sending CREATE cells 211 212 Circuits are created by sending a `circuit::CtrlMsg::Create` 213 to the circuit reactor via an `mpsc` channel. 214 215 > At the time of writing, the only type of circuit supported is the `ClientCirc` 216 > (a circuit initiated by the client). 217 218 Client circuits can be created using `PendingClientCirc::create_firsthop_ntor_v3`, 219 which creates a 1-hop `ClientCirc` that can later be extended 220 using `ClientCirc::extend_ntor` 221 (there are other `create_firsthop_*` functions, 222 but they're not described here for brevity). 223 Under the hood, `PendingClientCirc::create_firsthop_ntor_v3` 224 sends a `circuit::CtrlMsg::Create` control message 225 to the circuit reactor to create the 1-hop circuit. 226 227 In the circuit reactor, the message is received via the unbounded 228 `control: mpsc::UnboundedReceiver<CtrlMsg>` MPSC channel. 229 230 So, when the reactor receives a `CtrlMsg::Create` message, it calls 231 `Reactor::create_impl` via `Reactor::create_firsthop_ntor_v3` 232 (note this is **not** the same function as the function with the same name mentioned above), 233 which is where the magic happens. 234 235 `Reactor::create_impl` creates the cell and then sends it over to the 236 circuit's channel reactor for delivery via the `self.chan_sender` channel: 237 * `self.chan_sender` is an **unbounded** `SometimesUnboundedSink` that wraps 238 a `ChannelSender` 239 * the cell is written to `self.chan_sender` in `Reactor::send_msg_direct`, 240 which calls the `pollish_send_unbounded` function of the unbounded sink to 241 enqueue (or send!) the cell on the sink 242 * the important thing to note here is that `chan_sender` (`SometimesUnboundedSink`) 243 has an internal **unbounded** buffer than contains cells that couldn't be sent 244 right away (i.e. the cells the `ChannelSender` sink blocked on) 245 246 ## Places where we buffer data *unboundedly* 247 248 The places where cells may be buffered unboundedly include: 249 250 * the `chan_sender` in the circuit reactor: `circuit::Reactor` --`SometimesUnboundedSink<AnyChanCell, ChannelSender>`---> `channel::Reactor` 251 * the `control` channel in `ClientCirc`: `ClientCirc` ----unbounded `Reactor::control` ctrl channel-----> `circuit::Reactor` 252 253 However, currently neither of these channels can be made 254 to buffer unboundedly remotely. 255 See the explanation in the `circuit::Reactor::chan_sender` docs 256 for more details. 257 258 As for the bounded buffers/queues, see the diagram above. 259 260 ------- 261 262 ## How does all of this affect how we implement KIST? 263 264 We continue reading from the stream, but we stop writing to it. 265 266 1. We can no longer write to `channel::Reactor::output` 267 because KIST says "no more!". 268 As a result `self.output.prepare_send_from()` will block 269 (technically speaking the future will be pending) 270 2. We stop reading from `channel::Reactor::cells`, 271 because the channel reactor only reads from `cells` if the `output` sink 272 is ready to receive more cells. 273 Consequently, the sender (`circuit::Reactor::chan_sender`) will start buffering 274 any cells written to it, until it's filled 275 with `CHANNEL_BUFFER_SIZE + num-senders` = 129 cells 276 3. The channel reactor continues reading from the channel's `input` stream. 277 The cells read are sent to the circuit reactor of their corresponding circuits. 278 In the circuit reactor, these are received on the `circuit::Reactor::input` 279 queue, which is **bounded** (with a bound of `128 cells + num-senders` = 129 cells) 280 4. When the `circuit::Reactor::chan_sender` is filled with 129 buffered cells, 281 technically the circuit reactor will start buffering in the unbounded sender 282 (which wraps the bounded MPSC channel). 283 However, we do not expect to buffer unboundedly here, because 284 the reactor first calls `chan_sender.poll_ready_unpin_bool` 285 to check if the channel is ready to receive any more cells 286 (and if not, it will stop trying to write) 287 5. In the circuit reactor, `chan_sender` is not ready, 288 so we move on and flush it (`poll_flush`). 289 `chan_sender.poll_flush()` will be `Pending` too, but that's okay 290 because the circuit reactor doesn't block on it. 291 6. In the circuit reactor, we continue reading from `input` 292 which receives `ClientCircChanMsgs` from the corresponding circuit entry 293 from the channel reactor's circuit map. 294 7. But reading from `input` means having to respond to the received cell, 295 e.g. by sending a circuit-level SENDME. 296 The other end won't receive our "response" though, 297 because our "response" cells will get queued 298 until our KIST Socket says it's ok to write some more 299 300 However, when KIST-limiting kicks in, we don't expect to actually receive 301 more cells via `input` queue. This is because the lack of SENDMEs from 302 us should count as a congestion signal to the other edge of the connection, 303 which will stop sending, assuming it's well-behaved. 304 But if the other side does not impl congestion control the way we expect 305 (meaning we notice output queues such as the unbounded `chan_sender` start to fill up), 306 we need to be able to kill the circuit (something we don't currently do) 307 308 Rough KIST implementation plan: 309 * [ ] Implement prop324 congestion control 310 * [ ] Add a new `TransportImplHelper` that wraps a KIST write-limited `KistSocket` 311 (Linux only, for now) 312 * [ ] Make the circuit reactor kill circuits whose `chan_sender` sink 313 is buffering too many unsent cells 314 * [ ] Implement the (as yet unwritten) ["SENDME everywhere"] proposal, 315 which will enable us to be lower the circuit cut-off queue length limit 316 317 [^1]: `ClientCircChanMsg` is the subset of channel messages allowed allowed to 318 arrive on a client circuit 319 320 [`ClientCirc`]: https://docs.rs/tor-proto/0.24.0/tor_proto/circuit/struct.ClientCirc.html#circuit-life-cycle 321 [`Channel`]: https://docs.rs/tor-proto/0.24.0/tor_proto/channel/struct.Channel.html#channel-life-cycle 322 [`futures_codec::Framed`]: https://docs.rs/futures_codec/0.4.1/futures_codec/struct.Framed.html 323 ["SENDME everywhere"]: https://gitlab.torproject.org/tpo/core/torspec/-/issues/216