1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
.. highlight:: none


.. index::
   pair: stack probe; design

.. _design-sp:


Stack probe
===========

.. mps:prefix:: design.mps.sp


Introduction
------------

:mps:tag:`intro` This is the design of the stack probe module.

:mps:tag:`readership` Any MPS developer; anyone porting the MPS to a new
platform.

:mps:tag:`overview` This module ensures that the stack cannot overflow while
the MPS is holding a lock, so that a mutator can handle stack overflow
faults and call into the MPS from the handler.


Requirements
------------

:mps:tag:`req.overflow` The mutator should be able to call into the MPS from
a stack overflow fault handler. (This is a convenient way to handle
stack overflows in dynamic language implementations: if the stack
overflow exception and associated backtrace are to be represented as
objects, this may require allocation, and hence a call into the MPS.)

:mps:tag:`req.complete` In an application where the mutator might call into
the MPS from a stack overflow fault handler, then whenever the MPS
takes a lock, it must complete the operation and release the lock
without running out of stack. (This is because running out of stack
would cause a stack overflow fault, causing the mutator to enter the
MPS recursively, which would fail because the lock is held.)


Design
------

:mps:tag:`sol.probe` Before taking the arena lock in :c:func:`ArenaEnterLock()`,
the MPS *probes* the stack: that is, it checks whether there are at
least ``StackProbeDEPTH`` words available, and provokes a stack
overflow fault if there are not. (This ensures that the fault occurs
outside of the arena lock where it can be handled safely.)

:mps:tag:`sol.depth` The configuration parameter ``StackProbeDEPTH``
specifies the maximum number of words of stack that the MPS might use.
(It is simpler, faster, and more reliable, to determine this globally
than to try to figure it out dynamically.)

:mps:tag:`sol.depth.constraint` Operating systems typically use a single
"guard page" to detect stack overflow and grow the stack. (See for
example the documentation for Windows_.) This means that the probe
will be ineffective if it skips over the guard page into the memory
beyond. If ``StackProbeDEPTH`` is greater than or equal to the number
of words per page, the implementation might need to carry out multiple
probes. (This constraint is checked in :c:func:`MPMCheck()`.)

.. _Windows: https://docs.microsoft.com/en-us/windows/desktop/procthread/thread-stack-size

:mps:tag:`sol.depth.no-recursion` In order to implement this design, the MPS
must have constant bounded stack depth, and therefore, no recursion.

:mps:tag:`sol.depth.analysis` Here's a table showing a deep call into the
MPS (in the master sources at changelevel 187378), starting in
:c:func:`ArenaAccess()` at the point where the arena ring lock is taken. The
access forces a scan of a segment in an AMC pool, which fixes a
reference to an object in an AMC pool's oldspace, which has to be
forwarded, and this overflows the forwarding buffer, which requires
the arena to allocate a new buffer in an appropriate zone, by
searching the splay tree representing free memory.

The "Args" column gives the number of arguments to the function (all
arguments to functions in the MPS are word-sized or smaller, since we
prohibit passing structures by value), and the "Locals" column gives
the number of words in local variables. The value "≤64" for the stack
usage of the object format's scan method is the limit that's
documented in the manual.

====  ======  ========================
Args  Locals  Function
====  ======  ========================
   5       0  :c:func:`SegAccess()`
   5       0  :c:func:`SegWholeAccess()`
   3       8  :c:func:`TraceSegAccess()`
   4       1  :c:func:`traceScanSeg()`
   4       9  :c:func:`traceScanSegRes()`
   4       0  :c:func:`SegScan()`
   4       5  :c:func:`amcSegScan()`
   3       0  :c:func:`TraceScanFormat()`
   3     ≤64  ``format->scan()``
   3       0  :c:func:`SegFix()`
   4      15  :c:func:`amcSegFix()`
   3       5  :c:func:`BufferFill()`
   5      11  :c:func:`AMCBufferFill()`
   5      73  :c:func:`PoolGenAlloc()`
   6       5  :c:func:`SegAlloc()`
   4       4  :c:func:`ArenaAlloc()`
   5       6  :c:func:`PolicyAlloc()`
   6      10  :c:func:`ArenaFreeLandAlloc()`
   7       1  :c:func:`LandFindInZones()`
   7      16  :c:func:`cbsFindInZones()`
   5       3  :c:func:`cbsFindFirst()`
   6       7  :c:func:`SplayFindFirst()`
   3       7  :c:func:`SplaySplay()`
   4       8  :c:func:`SplaySplitDown()`
   3       0  :c:func:`SplayZig()`
 111    ≤258  **Total**
====  ======  ========================

We expect that a compiler will not need to push all local variables
onto the stack, but even in the case where it pushes all of them, this
call requires no more than 369 words of stack space.

This isn't necessarily the deepest call into the MPS (the MPS's
modular design and class system makes it hard to do a complete
analysis using call graph tools), but it's probably close. The value
for ``StackProbeDEPTH`` is thus chosen to be a round number that's
comfortably larger than this.


Interface
---------

.. c:function:: void StackProbe(Size depth)

:mps:tag:`if.probe` If there are at least ``depth`` words of stack
available, return. If not, provoke a stack overflow fault.


Issues
------

:mps:tag:`issue.an` The generic implementation is non-functional. This means
that it is only suitable for use with programs that do not handle
stack overflow faults, or do not call into the MPS from the handler.
This is because our customers have only required :mps:ref:`.req.overflow` on
Windows so far. If this becomes a requirement on other platforms, the
following Standard C implementation might work::

    void StackProbe(Size depth) {
      volatile Word w;
      Word *p = &w - depth;
      w = *p;
    }

The use of ``volatile`` here is to prevent compilers from warning
about the variable ``w`` being written but never read, or worse,
optimizing away the whole statement under the "as if" rule.


Implementations
---------------

:mps:tag:`impl.an` Generic implementation in ``span.c``. This implementation
does nothing. See :mps:ref:`.issue.an`.

:mps:tag:`impl.w3i3` Implementation for Windows on IA-32 in ``spw3i3.c``.
This uses assembly to get the stack pointer (from the ESP register)
and to read the location ``depth`` words below the stack pointer.

:mps:tag:`impl.w3i6` Implementation for Windows on x86-64 in ``spw3i6.c``.
This passes the argument ``depth*sizeof(Word)`` to the Windows
function |alloca|_, for which the documentation says, "A stack
overflow exception is generated if the space cannot be allocated."

.. |alloca| replace:: ``_alloca()``
.. _alloca: https://docs.microsoft.com/en-gb/cpp/c-runtime-library/reference/alloca