Debian Codegraph @

docs/howitworks.rst

raw
1
2 .. _howitworks:
3
4 How Mitogen Works
5 =================
6
7 Some effort is required to accomplish the seemingly magical feat of
8 bootstrapping a remote Python process without any software installed on the
9 remote machine. The steps involved are unlikely to be immediately obvious to
10 the casual reader, and they required several iterations to discover, so we
11 document them thoroughly below.
12
13
14 The UNIX First Stage
15 --------------------
16
17 To allow delivery of the bootstrap compressed using :py:mod:`zlib`, it is
18 necessary for something on the remote to be prepared to decompress the payload
19 and feed it to a Python interpreter [#f1]_. Since we would like to avoid
20 writing an error-prone shell fragment to implement this, and since we must
21 avoid writing to the remote machine's disk in case it is read-only, the Python
22 process started on the remote machine by Mitogen immediately forks in order to
23 implement the decompression.
24
25
26 Python Command Line
27 ###################
28
29 The Python command line sent to the host is a :mod:`zlib`-compressed [#f2]_ and
30 base64-encoded copy of :py:meth:`mitogen.parent.Connection._first_stage`,
31 which is carefully written to maximize it compatibility and minimize its size.
32 A simplified illustration of the bootstrap command is
33
34 .. code::
35
36 python -c 'exec(sys.argv[1].decode("base64").decode("zlib"))' <base64> ...
37
38 The command-line arranges for the Python interpreter to decode the base64'd
39 component, decompress it and execute it as Python code. Base64 is used since
40 to protect against any special characters that may be interpreted by the system
41 shell in use.
42
43
44 Forking The First Stage
45 #######################
46
47 The first stage creates a UNIX pipe and saves a copy of the process's real
48 ``stdin`` file descriptor (used for communication with the master) so that it
49 can be recovered by the bootstrapped process later. It then forks into a new
50 process.
51
52 After fork, the parent half overwrites its ``stdin`` with the read end of the
53 pipe, and the child half writes the string ``MITOGEN0\n``, then begins reading the
54 :py:mod:`zlib`-compressed payload supplied on ``stdin`` by the master, and
55 writing the decompressed result to the write-end of the UNIX pipe.
56
57 To allow recovery of ``stdin`` for reuse by the bootstrapped process for
58 parent<->child communication, it is necessary for the first stage to avoid
59 closing ``stdin`` or reading from it until EOF. Therefore, the master
60 sends the :py:mod:`zlib`-compressed payload prefixed with an integer size,
61 allowing reading by the first stage of exactly the required bytes.
62
63
64 Configuring argv[0]
65 ###################
66
67 Forking provides an excellent opportunity to tidy up the eventual Python
68 interpreter, in particular, restarting it using a fresh command-line to get rid
69 of the large base64-encoded first stage parameter, and to replace **argv[0]**
70 with something descriptive.
71
72 After configuring its ``stdin`` to point to the read end of the pipe, the
73 fork parent re-executes Python with **argv[0]** composed of the Python
74 interpreter path and a remote name supplied by the Mitogen parent. As no
75 arguments are provided to this new execution of Python, and since ``stdin`` is
76 connected to a pipe (whose write end is connected to the first stage), the
77 Python interpreter begins reading source code to execute from the pipe
78 connected to ``stdin``.
79
80
81 Bootstrap Preparation
82 #####################
83
84 Now we have the mechanism in place to send a :py:mod:`zlib`-compressed script
85 to the remote Python interpreter, it is time to choose what to send.
86
87 The script sent is simply the source code for :py:mod:`mitogen.core`, with a
88 single line suffixed to trigger execution of the
89 :py:meth:`mitogen.core.ExternalContext.main` function. The encoded arguments
90 to the main function include some additional details, such as the logging package
91 level that was active in the parent process, and whether debugging or profiling
92 are enabled.
93
94 After the script source code is prepared, it is passed through
95 :py:func:`mitogen.master.minimize_source` to strip it of docstrings and
96 comments, while preserving line numbers. This reduces the compressed payload
97 by around 20%.
98
99
100 Preserving The `mitogen.core` Source
101 ####################################
102
103 One final trick is implemented in the first stage: after bootstrapping the new
104 child, it writes a duplicate copy of the :py:mod:`mitogen.core` source it just
105 used to bootstrap it back into another pipe connected to the child. The child's
106 module importer cache is initialized with a copy of the source, so that
107 subsequent bootstraps of children-of-children do not require the source to be
108 fetched from the master a second time.
109
110
111 Signalling Success
112 ##################
113
114 Once the first stage has signalled ``MITO000\n``, the master knows it is ready
115 to receive the compressed bootstrap. After decompressing and writing the
116 bootstrap source to its parent Python interpreter, the first stage writes the
117 string ``MITO001\n`` to ``stdout`` before exiting. The master process waits for
118 this string before considering bootstrap successful and the child's ``stdio``
119 ready to receive messages.
120
121 The signal value is 8 bytes to match the minimum chunk size required to
122 disambiguate between lines containing an interesting token during SSH password
123 authentication, a debug message from the SSH client itself, or a message from
124 the first stage.
125
126
127 ExternalContext.main()
128 ----------------------
129
130 .. automethod:: mitogen.core.ExternalContext.main
131
132
133 Generating A Synthetic `mitogen` Package
134 ########################################
135
136 Since the bootstrap consists of the :py:mod:`mitogen.core` source code, and
137 this code is loaded by Python by way of its main script (:mod:`__main__`
138 module), initially the module layout in the child will be incorrect.
139
140 The first step taken after bootstrap is to rearrange :py:data:`sys.modules` slightly
141 so that :py:mod:`mitogen.core` appears in the correct location, and all
142 classes defined in that module have their ``__module__`` attribute fixed up
143 such that :py:mod:`cPickle` correctly serializes instance module names.
144
145 Once a synthetic :py:mod:`mitogen` package and :py:mod:`mitogen.core` module
146 have been generated, the bootstrap **deletes** `sys.modules['__main__']`, so
147 that any attempt to import it (by :py:mod:`cPickle`) will cause the import to
148 be satisfied by fetching the master's actual :mod:`__main__` module. This is
149 necessary to allow master programs to be written as a self-contained Python
150 script.
151
152
153 Reaping The First Stage
154 #######################
155
156 After the bootstrap has called :py:func:`os.dup` on the copy of the ``stdin``
157 file descriptor saved by the first stage, it is closed.
158
159 Additionally, since the first stage was forked prior to re-executing the Python
160 interpreter, it will exist as a zombie process until the parent process reaps
161 it. Therefore the bootstrap must call :py:func:`os.wait` soon after startup.
162
163
164 Setup Logging
165 #############
166
167 The child's :py:mod:`logging` package root logger is configured to have the
168 same log level as the root logger in the master, and
169 :py:class:`mitogen.core.LogHandler` is installed to forward logs to the master
170 context's :py:data:`FORWARD_LOG <mitogen.core.FORWARD_LOG>` handle.
171
172 The log level is copied into the child to avoid generating a potentially large
173 amount of network IO forwarding logs that will simply be filtered away once
174 they reach the master.
175
176
177 The Module Importer
178 ###################
179
180 An instance of :py:class:`mitogen.core.Importer` is installed in
181 :py:data:`sys.meta_path`, where Python's :keyword:`import` statement will
182 execute it before attempting to find a module locally.
183
184
185 Standard IO Redirection
186 #######################
187
188 Two instances of :py:class:`mitogen.core.IoLogger` are created, one for
189 ``stdout`` and one for ``stderr``. This class creates a UNIX pipe whose read
190 end is added to the IO multiplexer, and whose write end is used to overwrite
191 the handles inherited during process creation.
192
193 Even without IO redirection, something must replace ``stdin`` and ``stdout``,
194 otherwise it is possible for the stream used for communication between parent
195 and child to be accidentally corrupted by subprocesses run by user code.
196
197 The inherited ``stdin`` is replaced by a file descriptor pointing to
198 ``/dev/null``.
199
200 Finally Python's :py:data:`sys.stdout` is reopened to ensure line buffering is
201 active, so that ``print`` statements and suchlike promptly appear in the logs.
202
203
204 Function Call Dispatch
205 ######################
206
207 .. currentmodule:: mitogen.core
208
209 After all initialization is complete, the child's main thread sits in a loop
210 reading from a :py:class:`Channel <mitogen.core.Channel>` connected to the
211 :py:data:`CALL_FUNCTION <mitogen.core.CALL_FUNCTION>` handle. This handle is
212 written to by
213 :py:meth:`call() <mitogen.parent.Context.call>`
214 and :py:meth:`call_async() <mitogen.parent.Context.call_async>`.
215
216 :py:data:`CALL_FUNCTION <mitogen.core.CALL_FUNCTION>` only accepts requests
217 from the context IDs listed in :py:data:`mitogen.parent_ids`, forming a chain
218 of trust between the master and any intermediate context leading to the
219 recipient of the message. In combination with :ref:`source-verification`, this
220 is a major contributor to ensuring contexts running on compromised
221 infrastructure cannot trigger code execution in siblings or any parent.
222
223
224 Shutdown
225 ########
226
227 .. currentmodule:: mitogen.core
228
229 When a context receives :py:data:`SHUTDOWN <mitogen.core.SHUTDOWN>` from its
230 immediate parent, it closes its own :py:data:`CALL_FUNCTION
231 <mitogen.core.CALL_FUNCTION>` :py:class:`Channel <mitogen.core.Channel>` before
232 sending :py:data:`SHUTDOWN <mitogen.core.SHUTDOWN>` to any directly connected
233 children. Closing the channel has the effect of causing
234 :py:meth:`ExternalContext._dispatch_calls` to exit and begin joining on the
235 broker thread.
236
237 During shutdown, the master waits up to 5 seconds for children to disconnect
238 gracefully before force disconnecting them, while children will use that time
239 to call :py:meth:`socket.shutdown(SHUT_WR) <socket.socket.shutdown>` on their
240 :py:class:`IoLogger <mitogen.core.IoLogger>` socket's write ends before
241 draining any remaining data buffered on the read ends, and ensuring any
242 deferred broker function callbacks have had a chance to complete, necessary to
243 capture for example forwarding any remaining :py:mod:`logging` records.
244
245 An alternative approach is to wait until the IoLogger socket is completely
246 closed, with some hard timeout, but this necessitates greater discipline than
247 is common in infrastructure code (how often have you forgotten to redirect
248 stderr to ``/dev/null`` when starting a daemon process?), so needless
249 irritating delays would often be experienced during program termination.
250
251 If the main thread (responsible for function call dispatch) fails to shut down
252 gracefully, because some user function is hanging, it will still be cleaned up
253 since as the final step in broker shutdown, the broker sends
254 :py:mod:`signal.SIGTERM <signal>` to its own process.
255
256
257 .. _stream-protocol:
258
259 Stream Protocol
260 ---------------
261
262 .. currentmodule:: mitogen.core
263
264 Once connected, a basic framing protocol is used to communicate between
265 parent and child. Integers use big endian in their encoded form.
266
267 .. list-table::
268 :header-rows: 1
269 :widths: auto
270
271 * - Field
272 - Size
273 - Description
274
275 * - `magic`
276 - 2
277 - Integer 0x4d49 (``MI``), used to detect stream corruption.
278
279 * - `dst_id`
280 - 4
281 - Integer target context ID. :py:class:`Router` delivers messages
282 locally when their `dst_id` matches :py:data:`mitogen.context_id`,
283 otherwise they are routed up or downstream.
284
285 * - `src_id`
286 - 4
287 - Integer source context ID. Used as the target of replies if any are
288 generated.
289
290 * - `auth_id`
291 - 4
292 - The context ID under whose authority the message is acting. See
293 :py:ref:`source-verification`.
294
295 * - `handle`
296 - 4
297 - Integer target handle in the destination context. This is one of the
298 :py:ref:`standard-handles`, or a dynamically generated handle used to
299 receive a one-time reply, such as the return value of a function call.
300
301 * - `reply_to`
302 - 4
303 - Integer target handle to direct any reply to this message. Used to
304 receive a one-time reply, such as the return value of a function call,
305 or to signal a special condition for the message. :ref:`See below
306 <reply_to_values>` for special values for this field.
307
308 * - `length`
309 - 4
310 - Length of the data part of the message.
311
312 * - `data`
313 - n/a
314 - Message data, which may be raw or pickled.
315
316
317
318 .. _standard-handles:
319
320 Standard Handles
321 ################
322
323 Masters listen on the following handles:
324
325 .. _FORWARD_LOG:
326 .. currentmodule:: mitogen.core
327 .. data:: FORWARD_LOG
328
329 Receives `(logger_name, level, msg)` 3-tuples and writes them to the
330 master's ``mitogen.ctx.<context_name>`` logger.
331
332 .. _GET_MODULE:
333 .. currentmodule:: mitogen.core
334 .. data:: GET_MODULE
335
336 Receives the name of a module to load `fullname`, locates the source code
337 for `fullname`, and routes one or more :py:data:`LOAD_MODULE` messages back
338 towards the sender of the :py:data:`GET_MODULE` request. If lookup fails,
339 :data:`None` is sent instead.
340
341 See :ref:`import-preloading` for a deeper discussion of
342 :py:data:`GET_MODULE`/:py:data:`LOAD_MODULE`.
343
344 .. _ALLOCATE_ID:
345 .. currentmodule:: mitogen.core
346 .. data:: ALLOCATE_ID
347
348 Replies to any message sent to it with a newly allocated range of context
349 IDs, to allow children to safely start their own contexts. Presently IDs are
350 allocated in batches of 1000 from a 32 bit range, allowing up to 4.2 million
351 parent contexts to be created and destroyed before the associated Router
352 must be recreated.
353
354 This is handled by :class:`mitogen.master.IdAllocator` in the master
355 process, and messages are sent to it from
356 :class:`mitogen.parent.ChildIdAllocator` in children.
357
358 Children listen on the following handles:
359
360 .. _LOAD_MODULE:
361 .. currentmodule:: mitogen.core
362 .. data:: LOAD_MODULE
363
364 Receives `(pkg_present, path, compressed, related)` tuples, composed of:
365
366 * **pkg_present**: Either :data:`None` for a plain ``.py`` module, or a
367 list of canonical names of submodules existing witin this package. For
368 example, a :py:data:`LOAD_MODULE` for the :py:mod:`mitogen` package would
369 return a list like: `["mitogen.core", "mitogen.fakessh",
370 "mitogen.master", ..]`. This list is used by children to avoid generating
371 useless round-trips due to Python 2.x's :keyword:`import` statement
372 behavior.
373 * **path**: Original filesystem where the module was found on the master.
374 * **compressed**: :py:mod:`zlib`-compressed module source code.
375 * **related**: list of canonical module names on which this module appears
376 to depend. Used by children that have ever started any children of their
377 own to preload those children with :py:data:`LOAD_MODULE` messages in
378 response to a :py:data:`GET_MODULE` request.
379
380 .. _CALL_FUNCTION:
381 .. currentmodule:: mitogen.core
382 .. data:: CALL_FUNCTION
383
384 Receives `(chain_id, mod_name, class_name, func_name, args, kwargs)`
385 6-tuples from :class:`mitogen.parent.CallChain`, imports ``mod_name``, then
386 attempts to execute `class_name.func_name(\*args, \**kwargs)`.
387
388 * `chain_id`: if not :data:`None`, an identifier unique to the originating
389 :class:`mitogen.parent.CallChain`. When set, if an exception occurs
390 during a call, future calls with the same ID automatically fail with the
391 same exception without ever executing, and failed calls with no
392 `reply_to` set are not dumped to the logging framework as they otherwise
393 would. This is used to implement pipelining.
394
395 When this channel is closed (by way of receiving a dead message), the
396 child's main thread begins graceful shutdown of its own :py:class:`Broker`
397 and :py:class:`Router`.
398
399 .. _SHUTDOWN:
400 .. currentmodule:: mitogen.core
401 .. data:: SHUTDOWN
402
403 When received from a child's immediate parent, causes the broker thread to
404 enter graceful shutdown, including sending a dead message to the child's
405 main thread, causing it to join on the exit of the broker thread.
406
407 The final step of a child's broker shutdown process sends
408 :py:mod:`signal.SIGTERM <signal>` to itself, ensuring the process dies even
409 if the main thread was hung executing user code.
410
411 Each context is responsible for sending :py:data:`SHUTDOWN` to each of its
412 directly connected children in response to the master sending
413 :py:data:`SHUTDOWN` to it, and arranging for the connection to its parent
414 to be closed shortly thereafter.
415
416
417 Masters, and children that have ever been used to create a descendent child
418 also listen on the following handles:
419
420 .. _ADD_ROUTE:
421 .. currentmodule:: mitogen.core
422 .. data:: ADD_ROUTE
423
424 Receives `target_id` integer from downstream, describing an ID allocated to
425 a recently constructed child. The receiver verifies no existing route
426 exists to `target_id` before updating its local table to route messages for
427 `target_id` via the stream from which the :py:data:`ADD_ROUTE` message was
428 received.
429
430 .. _DEL_ROUTE:
431 .. currentmodule:: mitogen.core
432 .. data:: DEL_ROUTE
433
434 Receives `target_id` integer from downstream, verifies a route exists to
435 `target_id` via the stream on which the message was received, removes that
436 route from its local table, triggers the ``disconnect`` signal on any
437 :class:`mitogen.core.Context` instance in the local process, then
438 propagates the message upward towards its own parent.
439
440 .. currentmodule:: mitogen.core
441 .. data:: DETACHING
442
443 Sent to inform a parent that user code has invoked
444 :meth:`ExternalContext.detach` to decouple the lifecycle of a directly
445 connected context and its subtree from the running program.
446
447 A child usually shuts down immediately if it loses its parent connection,
448 and parents usually terminate any related Python/SSH subprocess on
449 disconnection. Receiving :data:`DETACHING` informs the parent the
450 connection will soon drop, but the process intends to continue life
451 independently, and to avoid terminating the related subprocess if that
452 subprocess is the child itself.
453
454 Non-master parents also listen on the following handles:
455
456 .. currentmodule:: mitogen.core
457 .. data:: GET_MODULE
458
459 As with master's ``GET_MODULE``, except this implementation
460 (:py:class:`mitogen.master.ModuleForwarder`) serves responses using
461 :py:class:`mitogen.core.Importer`'s cache before forwarding the request to
462 its parent context. The response is cached by each context in turn before
463 being forwarded on to the child context that originally made the request.
464 In this way, the master need never re-send a module it has already sent to
465 a direct descendant.
466
467 .. currentmodule:: mitogen.core
468 .. data:: FORWARD_MODULE
469
470 Receives `(context, fullname)` tuples from its parent and arranges for a
471 :data:`LOAD_MODULE` to be sent towards `context` for the module `fullname`
472 and any related modules. The module must already have been delivered to the
473 current context by its parent in a prior :data:`LOAD_MODULE` message.
474
475 If the receiver is the immediate parent of `context`, then only
476 :data:`LOAD_MODULE` is sent to the child. Otherwise :data:`LOAD_MODULE` is
477 sent to the next closest parent if the module has not previously been sent
478 on that stream, followed by a copy of the :data:`FORWARD_MODULE` message.
479
480 This message is used to recursively preload indirect children with modules,
481 ensuring they are cached and deduplicated at each hop in the chain leading
482 to the target context.
483
484 .. _reply_to_values:
485
486 Special values for the `reply_to` field:
487
488 .. _IS_DEAD:
489 .. currentmodule:: mitogen.core
490 .. autodata:: IS_DEAD
491
492
493
494 Additional handles are created to receive the result of every function call
495 triggered by :py:meth:`call_async() <mitogen.parent.Context.call_async>`.
496
497
498 Use of Pickle
499 #############
500
501 The current implementation uses the Python :py:mod:`cPickle` module, with a
502 restrictive class whitelist to prevent triggering undesirable code execution.
503 The primary reason for using :py:mod:`cPickle` is that it is computationally
504 efficient, and avoids including a potentially large body of serialization code
505 in the bootstrap.
506
507 The pickler will instantiate only built-in types and one of 3 constructor
508 functions, to support unpickling :py:class:`CallError
509 <mitogen.core.CallError>`, :py:class:`mitogen.core.Sender`,and
510 :py:class:`Context <mitogen.core.Context>`.
511
512 The choice of Pickle is one area to be revisited later. All accounts suggest it
513 cannot be used securely, however few of those accounts appear to be expert, and
514 none mention any additional attacks that would not be prevented by using a
515 restrictive class whitelist.
516
517
518 The IO Multiplexer
519 ------------------
520
521 Since we must include our IO multiplexer as part of the bootstrap,
522 off-the-shelf implementations are for the most part entirely inappropriate. For
523 example, a minimal copy of Twisted weighs in at around 440KiB and is composed
524 of approximately 115 files. Even if we could arrange for an entire Python
525 package to be transferred during bootstrap, this minimal configuration is
526 massive in comparison to Mitogen's solution, multiplies quickly in the
527 presence of many machines, and would require manually splitting up the parts of
528 Twisted that we would like to use.
529
530
531
532 .. _routing:
533
534 Message Routing
535 ---------------
536
537 Routing assumes it is impossible to construct a tree such that one of a
538 context's parents will not know the ID of a target the context is attempting to
539 communicate with.
540
541 When :py:class:`mitogen.core.Router` receives a message, it checks the IDs
542 associated with its directly connected streams for a potential route. If any
543 stream matches, either because it directly connects to the target ID, or
544 because the master sent an :py:data:`ADD_ROUTE <mitogen.core.ADD_ROUTE>`
545 message associating it, then the message will be forwarded down the tree using
546 that stream.
547
548 If the message does not match any :py:data:`ADD_ROUTE <mitogen.core.ADD_ROUTE>`
549 message or stream, instead it is forwarded upwards to the immediate parent, and
550 recursively by each parent in turn until one is reached that knows how to
551 forward the message down the tree.
552
553 When a parent establishes a new child, it sends a corresponding
554 :py:data:`ADD_ROUTE <mitogen.core.ADD_ROUTE>` message towards its parent, which
555 recursively forwards it up towards the root.
556
557 Parents keep note of all routes associated with each stream they connect with,
558 and trigger ``DEL_ROUTE`` messages propagated upstream for each route
559 associated with that stream if the stream is disconnected for any reason.
560
561
562 Example
563 #######
564
565 .. image:: images/context-tree.svg
566 :class: mitogen-full-width
567
568 In the diagram, when ``node12b`` is creating the ``sudo:node12b:webapp``
569 context, it must send ``ADD_ROUTE`` messages to ``rack12``, which will
570 propagate it to ``dc1``, and recursively to ``bastion``, and ``master``;
571 ``node12b`` does not require an ``ADD_ROUTE`` message since it has a stream
572 directly connected to the new context.
573
574 Since Mitogen streams are strictly ordered, it is never possible for a parent
575 to receive a message from a newly constructed child before receiving a
576 corresponding ``ADD_ROUTE`` sent by the child's parent, describing how to reply
577 to it.
578
579 When ``sudo:node12b:webapp`` wants to send a message to
580 ``sudo:node22a:webapp``, the message will be routed as follows:
581
582 ``sudo:node12b:webapp -> node12b -> rack12 -> dc1 -> bastion -> dc2 -> rack22 -> node22a -> sudo:node22a:webapp``
583
584 .. image:: images/route.svg
585 :class: mitogen-full-width
586
587
588 Disconnect Propagation
589 ######################
590
591 To ensure timely shutdown when a failure occurs, where some context is awaiting
592 a response from another context that has become disconnected,
593 :class:`mitogen.core.Router` additionally records the destination context ID of
594 every message received on a particular stream.
595
596 When ``DEL_ROUTE`` is generated locally or received on some other stream,
597 :class:`mitogen.parent.RouteMonitor` uses this to find every stream that ever
598 communicated with the route that is about to go away, and forwards the message
599 to each found.
600
601 The recipient ``DEL_ROUTE`` handler in turn uses the message to find any
602 :class:`mitogen.core.Context` in the local process corresponding to the
603 disappearing route, and if found, fires a ``disconnected`` event on it.
604
605 Any interested party, such as :class:`mitogen.core.Receiver`, may subscribe to
606 the event and use it to abort any threads that were asleep waiting for a reply
607 that will never arrive.
608
609
610 .. _source-verification:
611
612 Source Verification
613 ###################
614
615 Before forwarding or dispatching a message it has received,
616 :py:class:`mitogen.core.Router` first looks up the corresponding
617 :py:class:`mitogen.core.Stream` it would use to send responses towards the
618 context ID listed in the `auth_id` field, and if the looked up stream does not
619 match the stream on which the message was received, the message is discarded
620 and a warning is logged.
621
622 This creates a trust chain leading up to the root of the tree, preventing
623 downstream contexts from injecting messages appearing to be from the master or
624 any more trustworthy parent. In this way, privileged functionality such as
625 :py:data:`CALL_FUNCTION <mitogen.core.CALL_FUNCTION>` can base trust decisions
626 on the accuracy of :py:ref:`auth_id <stream-protocol>`.
627
628 The `auth_id` field is separate from `src_id` in order to support granting
629 privilege to contexts that do not follow the tree's natural trust chain. This
630 supports cases where siblings are permitted to execute code on one another, or
631 where isolated processes can connect to a listener and communicate with an
632 already established established tree, such as where a :mod:`mitogen.unix`
633 client receives the same privilege as the process it connects to.
634
635
636 Differences Between Master And Child Brokers
637 ############################################
638
639 The main difference between :py:class:`mitogen.core.Broker` and
640 :py:class:`mitogen.master.Broker` is that when the stream connection to the
641 parent is lost in a child, the broker will trigger its own shutdown.
642
643
644 The Module Importer
645 -------------------
646
647 :py:class:`mitogen.core.Importer` is still a work in progress, as there
648 are a variety of approaches to implementing it, and the present implementation
649 is not pefectly efficient in every case.
650
651 It operates by intercepting :keyword:`import` statements via
652 :py:data:`sys.meta_path`, asking Python if it can satisfy the import by itself,
653 and if not, indicating to Python that it is capable of loading the module.
654
655 In :py:meth:`load_module() <mitogen.core.Importer.load_module>` an RPC is
656 started to the parent context, requesting the module source code by way of a
657 :py:data:`GET_MODULE <mitogen.core.GET_MODULE>`. If the parent context does not
658 have the module available, it recursively forwards the request upstream, while
659 avoiding duplicate requests for the same module from its own threads and any
660 child contexts.
661
662
663 Neutralizing :py:mod:`__main__`
664 ###############################
665
666 To avoid accidental execution of the :py:mod:`__main__` module's code in a
667 slave context, when serving the source of the main module, Mitogen removes any
668 code occurring after the first conditional that looks like a standard
669 :py:mod:`__main__` execution guard:
670
671 .. code-block:: python
672
673 # Code that looks like this is stripped from __main__.
674 if __name__ == '__main__':
675 run_some_code()
676
677 To further avoid accidental execution, Mitogen will refuse to serve
678 :mod:`__main__` to children if no execution guard is found, as it is common
679 that no guard is present during early script prototyping.
680
681 These are hacks, but they are the safest and least annoying found to solve the
682 problem.
683
684
685 Avoiding Negative Imports
686 #########################
687
688 In Python 2.x where relative imports are the default, a large number of import
689 requests will be made for modules that do not exist. For example:
690
691 .. code-block:: python
692
693 # mypkg/__init__.py
694
695 import sys
696 import os
697
698 In Python 2.x, Python will first try to load :py:mod:`mypkg.sys` and
699 :py:mod:`mypkg.os`, which do not exist, before falling back on :py:mod:`sys`
700 and :py:mod:`os`.
701
702 These negative imports present a challenge, as they introduce a large number of
703 pointless network round-trips. Therefore in addition to the
704 :py:mod:`zlib`-compressed source, for packages the master sends along a list of
705 child modules known to exist.
706
707 Before indicating it can satisfy an import request,
708 :py:class:`mitogen.core.Importer` first checks to see if the module belongs to
709 a package it has previously imported, and if so, ignores the request if the
710 module does not appear in the enumeration of child modules belonging to the
711 package that was provided by the master.
712
713
714 .. _import-preloading:
715
716 Import Preloading
717 #################
718
719 .. currentmodule:: mitogen.core
720
721 To further avoid round-trips, when a module or package is requested by a child,
722 its bytecode is scanned in the master to find all the module's
723 :keyword:`import` statements, and of those, which associated modules appear to
724 have been loaded in the master's :py:data:`sys.modules`.
725
726 The :py:data:`sys.modules` check is necessary to handle various kinds of
727 conditional execution, for example, when a module's code guards an
728 :keyword:`import` statement based on the active Python runtime version,
729 operating system, or optional third party dependencies.
730
731 Before replying to a child's request for a module with dependencies:
732
733 * If the request is for a package, any dependent modules used by the package
734 that appear within the package itself are known to be missing from the child,
735 since the child requested the top-level package module, therefore they are
736 pre-loaded into the child using :py:data:`LOAD_MODULE` messages before
737 sending the :py:data:`LOAD_MODULE` message for the requested package module
738 itself. In this way, the child will already have dependent modules cached by
739 the time it receives the requested module, avoiding one round-trip for each
740 dependency.
741
742 For example, when a child requests the :py:mod:`django` package, and the master
743 determines the :py:mod:`django` module code in the master has :keyword:`import`
744 statements for :py:mod:`django.utils`, :py:mod:`django.utils.lru_cache`, and
745 :py:mod:`django.utils.version`,
746 and that execution of the module code on the master caused those modules to
747 appear in the master's :py:data:`sys.modules`, there is high probability
748 execution of the :py:mod:`django` module code in the child will cause the
749 same modules to be loaded. Since all those modules exist within the
750 :py:mod:`django` package, and we already know the child lacks that package,
751 it is safe to assume the child will make follow-up requests for those modules
752 too.
753
754 In the example, 4 round-trips are replaced by 1 round-trip.
755
756 For any package module ever requested by a child, the parent keeps a note of
757 the name of the package for one final optimization:
758
759 * If the request is for a sub-module of a package, and it is known the child
760 loaded the package's implementation from the parent, then any dependent
761 modules of the requested module at any nesting level within the package that
762 is known to be missing are sent using :py:data:`LOAD_MODULE` messages before
763 sending the :py:data:`LOAD_MODULE` message for the requested module, avoiding
764 1 round-trip for each dependency within the same top-level package.
765
766 For example, when a child has previously requested the :py:mod:`django`
767 package module, the parent knows the package was completely absent on the
768 child. Therefore when the child subsequently requests the
769 :py:mod:`django.db` package module, it is safe to assume the child will
770 generate subsequent :py:data:`GET_MODULE` requests for the 2
771 :py:mod:`django.conf`, 3 :py:mod:`django.core`, 2 :py:mod:`django.db`, 3
772 :py:mod:`django.dispatch`, and 7 :py:mod:`django.utils` indirect dependencies
773 for :py:mod:`django.db`.
774
775 In the example, 17 round-trips are replaced by 1 round-trip.
776
777 The method used to detect import statements is similar to the standard library
778 :py:mod:`modulefinder` module: rather than analyze module source code,
779 :ref:`IMPORT_NAME <python:bytecodes>` opcodes are extracted from the module's
780 bytecode. This is since clean source analysis methods (:py:mod:`ast` and
781 :py:mod:`compiler`) are an order of magnitude slower, and incompatible across
782 major Python versions.
783
784
785 Concurrency
786 ###########
787
788 Duplicate requests must never be issued to the parent, either due to a local
789 import or any :py:data:`GET_MODULE` originating from a child. This lets parents
790 assume a module requested once by a downstream connection need never be
791 re-sent, for example, if it appears as a preloading dependency in a subsequent
792 :py:data:`GET_MODULE`, or had been requested immediately after being sent as a
793 preloading dependency for an unrelated request by a descendent.
794
795 Therefore each tree layer must deduplicate :py:data:`GET_MODULE` requests, and
796 synchronize their descendents and local threads on corresponding
797 :py:data:`LOAD_MODULE` responses from the parent.
798
799 In each context, pending requests are serialized by a
800 :py:class:`threading.Lock` within :py:class:`mitogen.core.Importer`, which may
801 only be held for operations that cannot block, since :py:class:`ModuleForwarder
802 <mitogen.master.ModuleForwarder>` must acquire it while synchronizing
803 :py:data:`GET_MODULE` requests from children on the IO multiplexer thread.
804
805
806 Requests From Local Threads
807 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
808
809 When Mitogen begins satisfying an import, it is known the module has never been
810 imported in the local process. :py:class:`Importer <mitogen.core.Importer>`
811 executes under the runtime importer lock, ensuring :py:keyword:`import`
812 statements executing in local threads are serialized.
813
814 .. note::
815
816 In Python 2, :py:exc:`ImportError` is raised when :py:keyword:`import` is
817 attempted while the runtime import lock is held by another thread,
818 therefore imports must be serialized by only attempting them from the main
819 (:py:data:`CALL_FUNCTION`) thread.
820
821 The problem is most likely to manifest in third party libraries that lazily
822 import optional dependencies at runtime from a non-main thread. The
823 workaround is to explicitly import those dependencies from the main thread
824 before initializing the third party library.
825
826 This was fixed in Python 3.5, but Python 3.x is not yet supported. See
827 `Python Issue #9260`_.
828
829 .. _Python Issue #9260: https://bugs.python.org/issue9260
830
831 While holding its own lock, :py:class:`Importer <mitogen.core.Importer>`
832 checks if the source is not yet cached, determines if an in-flight
833 :py:data:`GET_MODULE` exists for it, starting one if none exists, adds itself
834 to a list of callbacks fired when a corresponding :py:data:`LOAD_MODULE`
835 arrives from the parent, then sleeps waiting for the callback.
836
837 When the source becomes available, the module is constructed on the calling
838 thread using the best practice documented in `PEP 302`_.
839
840 .. _PEP 302: https://www.python.org/dev/peps/pep-0302/
841
842
843 Requests From Children
844 ~~~~~~~~~~~~~~~~~~~~~~
845
846 As with local imports, when :py:data:`GET_MODULE` is received from a child,
847 while holding the :py:class:`Importer <mitogen.core.Importer>` lock,
848 :py:class:`ModuleForwarder <mitogen.master.ModuleForwarder>` checks if the
849 source is not yet cached, determines if an in-flight :py:data:`GET_MODULE`
850 toward the parent exists for it, starting one if none exists, then adds a
851 completion handler to the list of callbacks fired when a corresponding
852 :py:data:`LOAD_MODULE` arrives from the parent.
853
854 When the source becomes available, the completion handler issues corresponding
855 :py:data:`LOAD_MODULE` messages toward the child for the requested module after
856 any required for dependencies known to be absent from the child.
857
858 Since intermediaries do not know a module's dependencies until the module's
859 source arrives, it is not possible to preemptively issue :py:data:`LOAD_MODULE`
860 for those dependencies toward a requesting child as they become available from
861 the parent at the intermediary. This creates needless network serialization and
862 latency that should be addressed in a future design.
863
864
865 Child Module Enumeration
866 ########################
867
868 Package children are enumerated using :py:func:`pkgutil.iter_modules`.
869
870
871 Use Of Threads
872 --------------
873
874 The package always runs the IO multiplexer in a thread. This is so the
875 multiplexer retains control flow in order to shut down gracefully, say, if the
876 user's code has hung and the master context has disconnected.
877
878 While it is possible for the IO multiplexer to recover control of a hung
879 function call on UNIX using for example :py:mod:`signal.SIGALRM <signal>`, this
880 mechanism is not portable to non-UNIX operating systems, and does not work in
881 every case, for example when Python blocks signals during a variety of
882 :py:mod:`threading` package operations.
883
884 At some point it is likely Mitogen will be extended to support children running
885 on Windows. When that happens, it would be nice if the process model on Windows
886 and UNIX did not differ, and in fact the code used on both were identical.
887
888
889 .. _waking-sleeping-threads:
890
891 Waking Sleeping Threads
892 #######################
893
894 Due to fundamental deficiencies in Python 2's threading implementation, it is
895 not possible to block waiting on synchronization objects sanely. Two major
896 problems exist:
897
898 * Sleeping with no timeout set causes signals to be blocked, preventing the
899 user from terminating the process using CTRL+C.
900
901 * Sleeping with a timeout set internally makes use of polling, with an
902 exponential backoff that eventually results in the thread sleeping
903 unconditionally in 50ms increments. . This is a huge source of latency that
904 quickly multiplies.
905
906 As the UNIX self-pipe trick must already be employed to wake the broker thread
907 from its select loop, Mitogen reuses this technique to wake any thread
908 synchronization primitive exposed by the library, embodied in a queue-like
909 abstraction called a :py:class:`mitogen.core.Latch`.
910
911 Unfortunately it is commonplace for hosts to enforce severe per-process file
912 descriptors limits, so aside from being inefficient, it is impossible in the
913 usual case to create a pair of descriptors for every waitable object, which for
914 example includes the result of every single asynchronous function call.
915
916 For this reason self-pipes are created on a per-thread basis, with their
917 associated :py:func:`socketpairs <socket.socketpair>` kept in thread-local
918 storage. When a latch wishes to sleep its thread, this pair is created
919 on-demand and temporarily associated with it only for the duration of the
920 sleep.
921
922 Python's garbage collector is relied on to clean up by calling the pair's
923 destructor on thread exit. There does not otherwise seem to be a robust method
924 to trigger cleanup code on arbitrary threads.
925
926 To summarize, file descriptor usage is bounded by the number of threads rather
927 than the number of waitables, which is a much smaller number, however it also
928 means that Mitogen requires twice as many file descriptors as there are user
929 threads, with a minimum of 4 required in any configuration.
930
931
932 Latch Internals
933 ~~~~~~~~~~~~~~~
934
935 .. currentmodule:: mitogen.core
936
937 Attributes:
938
939 * `lock` – :py:class:`threading.Lock`.
940 * `queue` – items waiting to be dequeued.
941 * `sleeping` – write sides of the socketpairs for each sleeping thread, and
942 threads in the process of waking from sleep.
943 * `waking` – integer number of `sleeping` threads in the process of waking up.
944 * `closed` – boolean defaulting to :py:data:`False`. Every time `lock`
945 is acquired, `closed` must be tested, and if it is :py:data:`True`,
946 :py:class:`LatchError` must be thrown.
947
948
949 Latch.put()
950 ~~~~~~~~~~~
951
952 :py:meth:`Latch.put` operates by:
953
954 1. Acquiring `lock`.
955 2. Appending the item on to `queue`.
956 3. If `waking` is less than the length of `sleeping`, write a byte to the
957 socket at `sleeping[waking]` and increment `waking`.
958
959 In this way each thread is woken only once, and receives each element according
960 to when its socket was placed on `sleeping`.
961
962
963 Latch.close()
964 ~~~~~~~~~~~~~
965
966 :py:meth:`Latch.close` acquires `lock`, sets `closed` to :py:data:`True`, then
967 writes a byte to every `sleeping[waking]` socket, while incrementing `waking`,
968 until no more unwoken sockets exist. Per above, on waking from sleep, after
969 removing itself from `sleeping`, each sleeping thread tests if `closed` is
970 :py:data:`True`, and if so throws :py:class:`LatchError`.
971
972 It is necessary to ensure at most one byte is delivered on each socket, even if
973 the latch is being torn down, as the sockets outlive the scope of a single
974 latch, and must never have extraneous data buffered on them, as this will cause
975 unexpected wakeups if future latches sleep on the same thread.
976
977
978 Latch.get()
979 ~~~~~~~~~~~
980
981 :py:meth:`Latch.get` is far more intricate, as there are many outcomes to
982 handle. Queue ordering is strictly first-in first-out, and threads always
983 receive items in the order they are requested, as they become available.
984
985 **1. Non-empty, No Waiters, No sleep**
986 On entry `lock` is taken, and if `queue` is non-empty, and `sleeping` is
987 empty, it is safe to return `queue`'s first item without blocking.
988
989 **2. Non-empty, Waiters Present, Queue > Waiters, No sleep**
990 When `sleeping` is non-empty but there are more items than sleeping
991 threads, it is safe to pop `queue[len(sleeping)]` without blocking.
992
993 **3. Non-empty, Waiters Present, Queue <= Waiters**
994 In this case `sleeping` is non-empty and there are no surplus items. It is
995 not safe to pop any item even though we are holding `lock`, as it would
996 starve waking threads of their position in favour of the calling thread,
997 since scheduling uncertainty exists between a thread waking from
998 :py:func:`select.select` and re-acquiring `lock`.
999
1000 This avoids the need for a retry loop for waking threads, and a thread
1001 being continually re-woken to discover `queue` drained by a thread that
1002 never slept.
1003
1004 **4. Sleep**
1005 Since no surplus items existed, the thread adds its socket to `sleeping`
1006 before releasing `lock`, and sleeping in :py:func:`select.select` waiting
1007 for timeout, or a write from :py:meth:`Latch.put` or
1008 :py:meth:`Latch.close`.
1009
1010 If :py:func:`select.select` throws an exception, the exception must be
1011 caught and re-raised only after some of the wake steps below have
1012 completed.
1013
1014 **5. Wake, Non-empty**
1015 On wake `lock` is re-acquired, the socket is removed from `sleeping` after
1016 noting its index, and :py:class:`TimeoutError` is thrown if `waking`
1017 indicates :py:meth:`Latch.put()` nor :py:meth:`Latch.close` have yet to
1018 send a wake byte to that index. The byte is then read off,
1019 :py:class:`LatchError` is thrown if `closed` is :py:data:`True`, otherwise
1020 the queue item corresponding to the thread's index is popped and returned.
1021
1022 It is paramount that in every case, if a byte was written to the socket,
1023 that the byte is read away. The socket is reused by subsequent latches
1024 sleeping on the same thread, and unexpected wakeups are triggered if
1025 extraneous data remains buffered on the socket.
1026
1027 It is also necessary to favour the synchronized `waking` variable over the
1028 return value of :py:func:`select.select`, as scheduling uncertainty
1029 introduces a race between the select timing out, and :py:meth:`Latch.put()`
1030 or :py:meth:`Latch.close` writing a wake byte before :py:meth:`Latch.get`
1031 has re-acquired `lock`.
1032
1033
1034 .. rubric:: Footnotes
1035
1036 .. [#f1] Although some connection methods such as SSH support compression, and
1037 Mitogen enables SSH compression by default, there are circumstances where
1038 disabling SSH compression is desirable, and many scenarios for future
1039 connection methods where transport-layer compression is not supported at
1040 all.
1041
1042 .. [#f2] Compression may seem redundant, however it is basically free and reducing IO
1043 is always a good idea. The 33% / 200 byte saving may mean the presence or
1044 absence of an additional frame on the network, or in real world terms after
1045 accounting for SSH overhead, around a 2% reduced chance of a stall during
1046 connection setup due to a dropped frame.