There are three ways in which performing speculative execution could potentially change the behavior of the application. First, since the speculating thread shares an address space with the original thread, it could distort normal execution by changing code or data values that will be used by the original thread. Second, the speculating thread could produce side-effects visible outside the process, changing the impact of the application on the system. Finally, the speculating thread may inadvertently use inappropriate data values, like dividing by 0 or accessing an illegal address, that disrupt the execution of the application.
We ensure the correctness of our transformation by avoiding these potential
problems. We prevent the
speculating thread from producing side-effects visible outside the process
by not allowing the speculating thread to issue any system calls except the
hint calls (described in Table 2), and the fstat() and sbrk()
calls.
We prevent the use of inappropriate data values
from disturbing normal execution by installing signal handlers to catch any
exceptions generated by the speculating thread, halting
speculative execution until the original thread blocks on a new read call.
Finally, we prevent the speculating thread from changing code or data values
used by the original thread through software-enforced copy-on-write.
Inspired by software fault isolation [Wahbe93], software-enforced copy-on-write involves adding checks before each load and store instruction executed by the speculating thread, and adding a data structure to keep track of which memory regions have been copied and where their copies reside. Before each store instruction executed by the speculating thread, a check is added which accesses the data structure to discover whether the targetted memory region has already been copied. If so, the store is redirected to access the copy. If not, the memory region is copied, the data structure is updated, and the store is redirected to the newly created copy. Similarly, before each load instruction, a check is added which accesses the data structure to discover whether the referenced memory region has already been copied and, if so, redirects the load to obtain the value stored in the copy, which is the ``current'' value with respect to speculative execution.
Since load and store instructions comprise approximately 30% of the average instruction mix, software-enforced copy-on-write could be an expensive solution. For example, it may appear that the original thread would need to execute many additional branching instructions to avoid performing the checks. We avoid this overhead by making a complete copy of the binary's text section and constraining the speculating thread to only execute within the copy, which we call the shadow code. This permits us to add copy-on-write checks only around loads and stores in the shadow code, so that the original thread does not need to execute any additional instructions to support software-enforced copy-on-write.
Minimizing additional instructions in the original thread's code path is an example of our effort to minimize the observable overhead of supporting speculative execution. The checking necessary to perform software-enforced copy-on-write does not add directly to the execution time of the application; it simply causes speculative execution to proceed more slowly than normal execution; that is, it is nonobservable overhead. In general, we prefer design choices that incur nonobservable overhead to those that incur observable overhead since they seem less likely to affect worst-case performance.
We ensure that the speculating thread only executes shadow code by statically
and/or dynamically checking and redirecting all control transfers (that is,
possibilities for non-sequential changes in execution address). All control
transfers that can be statically resolved are statically redirected to the
appropriate address in the shadow code. Control transfers that cannot be
statically resolved include those dynamically calculated using jump tables,
corresponding to switch statements. Our binary modification tool only
recognizes a few of the possible compiler-dependent jump table formats, so
it can only statically handle switch statement control transfers that rely on
jump tables in a recognized format. All other control transfers are statically
redirected to call a special handling routine with
the originally intended target address as an argument. During runtime, if the
originally intended target address is in the shadow code, the handling routine
allows the speculating thread to proceed to that address. If the address is
not in the shadow code but can be mapped to an address in the shadow code,
then the handling routine redirects the speculating thread.
Otherwise, the handling routine simply prevents the speculating thread from
leaving the shadow code (by preventing further progress until a new speculation
is started, as discussed in the next section). Notice that, for
applications with self-modifying code, this scheme will not allow the
speculating thread to execute any newly created code, or to modify the
existing shadow code.
One potential advantage of using software-enforced copy-on-write is the
flexibility it permits in choosing the size of copy-on-write memory regions.
However, when we explored this flexibility by varying the copy-on-write region
size from 128B to 8192B, we discovered that it generally made no significant
difference to the performance improvements obtained - the only difference
larger than 5% was a 9% reduction in performance for Gnuld with a region
size of 8192B. All of the results presented in this paper were obtained using
1024B regions.