I thought hot-patching assumed that overwriting any instruction that is 2 or more bytes long with a 2 byte jump is safe for concurrent execution of the same code.
So instruction fetch is assumed to be atomic.
Is it indeed atomic, taking into account that with prefixes it is possible to have more than 8 bytes instruction, and it can cross any aligned boundary? (Or does hot-patching rely on 16-byte alignment of function start? If so, what's with size over 8 bytes, anyway?)
The context: LLVM has interception of API functions in https://github.com/llvm/llvm-project/blob/main/compiler-rt/lib/interception/interception_win.cpp. This is used at least for Address Sanitizer, maybe for something else too. It implements HotPatch as 3rd method (line 61):
// 3) HotPatch
//
// The HotPatch hooking is assuming the presence of an header with padding
// and a first instruction with at least 2-bytes.
//
// The reason to enforce the 2-bytes limitation is to provide the minimal
// space to encode a short jump. HotPatch technique is only rewriting one
// instruction to avoid breaking a sequence of instructions containing a
// branching target.
The binaries produced by MSVC are deliberately made compatible with this technique. There is /hotpatch compiler option to make sure that the first instruction in a function is at least 2 bytes and /functionpadmin linker option to make the gap between functions enough to fit an indirect jump. On x86-64 these options are not recognized because they are always implied. See What's the purpose of xchg ax,ax prior to the break instruction int 3 in DebugBreak()?
I was under the impression that HotPatch also implies the safety when the function being intercepted is being executed. However the API interception I'm looking at doesn't even try to write the jump atomically (line 259):
static void WriteShortJumpInstruction(uptr from, uptr target) {
sptr offset = target - from - kShortJumpInstructionLength;
if (offset < -128 || offset > 127)
InterceptionFailed();
*(u8*)from = 0xEB;
*(u8*)(from + 1) = (u8)offset;
}
So I'm wondering if it was a goal to make hot-patching safe against concurrent execution, and if it is even possible.
Instruction fetch is not architecturally guaranteed to be atomic. Although, in practice, an instruction cache fill transaction is, by definition atomic, meaning that the line being filled in the cache cannot change before the transaction completes (which happens when the whole line is stored in the IFU, but not necessarily in the instruction cache itself). The instruction bytes are also delivered to the input buffer of the instruction predecode unit at some atomic granularity. On modern Intel processors, the instruction cache line size is 64 bytes and the input width of the predcode unit is 16 bytes with an address aligned on a 16-byte boundary. (Note that the 16 bytes input can be delivered to the predecode unit before the entire transaction of fetching the cache line containing these 16 bytes completes.) Therefore, an instruction aligned on a 16-byte boundary is guaranteed to be fetched atomically, together with at least one byte of the following contiguous instruction, depending on the size of the instruction. But this is a microarchitectural guarantee, not architectural.
It seems to me that by instruction fetch atomicity you're referring to atomicity at the granularity of individual instructions, rather than some fixed number of bytes. Either way, instruction fetch atomicity is not required for hotpatching to work correctly. It's actually impractical because instruction boundaries are not known at the time of fetch.
If instruction fetch is atomic, it may still be possible to fetch, execute, and retire the instruction being modified with only one of the two bytes being written (or none of the bytes or both of the bytes). The allowed orders in which writes reach GO depend on the effective memory types of the target memory locations. So hotpatching would still not be safe.
Intel specifies in Section 8.1.3 of the SDM V3 how self-modifying code (SMC) and cross-modifying code (XMC) should work to guarantee correctness on all Intel processors. Regarding SMC, it says the following:
To write self-modifying code and ensure that it is compliant with current and future versions of the IA-32 architectures, use one of the following coding options:
(* OPTION 1 *)
Store modified code (as data) into code segment;
Jump to new code or an intermediate location;
Execute new code;(* OPTION 2 *)
Store modified code (as data) into code segment;
Execute a serializing instruction; (* For example, CPUID instruction *)
Execute new code;The use of one of these options is not required for programs intended to run on the Pentium or Intel486 processors, but are recommended to ensure compatibility with the P6 and more recent processor families.
Note that the last statement is incorrect. The writer probably intended to say instead: "The use of one of these options is not required for programs intended to run on the Pentium or later processors, but are recommended to ensure compatibility with the Intel486 processors." This is explained in Section 11.6, from which I want to quote an important statement:
A write to a memory location in a code segment that is currently cached in the processor causes the associated cache line (or lines) to be invalidated. This check is based on the physical address of the instruction. In addition, the P6 family and Pentium processors check whether a write to a code segment may modify an instruction that has been prefetched for execution. If the write affects a prefetched instruction, the prefetch queue is invalidated. This latter check is based on the linear address of the instruction
Briefly, prefetch buffers are used to maintain instruction fetch requests and their results. Starting with the P6, they were replaced with streaming buffers, which have a different design. The manual still uses the term "prefetch buffers" for all processors. The important point here is that, with respect to what is guaranteed architecturally, the check in the prefetch buffers is done using linear addresses, not physical addresses. That said, probably all Intel processors do these checks using physical addresses, which can be proved experimentally. Otherwise, this can break the fundamental sequential program order guarantee. Consider the following sequence of operations being executed on the same processor:
Store modified code (as data) into code segment;
Execute new code;
Assume that the page offsets of the linear addresses being written to are the same as the offsets of the linear addresses being from fetched, but the linear page numbers are different. However, both pages map to the same physical page. If we go by what's guaranteed architecturally, it's possible for instruction from the old code to retire even they are positioned later in program order with respect to the writes that modify the code. That's because an SMC condition cannot be detected based on comparing linear addresses alone, and the store are allowed to retire and later instruction can retire before the writes are committed. In practice, this doesn't happen, but it's possible architecturally. On AMD processors, the AMD APM V2 Section 7.6.1 states that these checks are based on physical addresses. Intel should do this too and make it official.
So to fully adhere to the Intel manual, there should be a fully serializing instruction as follows:
Store modified code (as data) into code segment;
Execute a serializing instruction; (\* For example, CPUID instruction \*)
Execute new code;
This is identical to OPTION 2 from the manual. However, for the sake of compatibility with the 486, some 486 processors don't support the CPUID instruction. The following code works on all processors:
Store modified code (as data) into code segment;
If (486 or AMD before K5) Jump to new code;
ElseIf (Intel P5 or later) Execute a serializing instruction; (\* For example, CPUID instruction \*)
Else; (\* Do nothing on AMD K5 and later \*)
Execute new code;
Otherwise, if it's guaranteed that there is no aliasing, the following code works correctly on modern processors:
Store modified code (as data) into code segment;
Execute new code;
As already mentioned, in practice, this also works correctly in any case (aliasing or not).
If the instructions being modified are stored in uncacheable memory locations (UC or WC), a fully serializing instruction is required on some or all of Intel P5+ and AMD K5+ processors, unless it can be guaranteed that the locations being written to were never fetched from prior to completing all needed modifications.
Within the context of hotpatching, the thread that modified the bytes and the thread that executes the code may happen to run on the same logical processor. If the threads are in different processes, switching between them requires changing the current process context, which involves executing at least one fully serializing instruction to change the linear address space. The architectural requirements for SMC end up being satisfied anyway. Code modifications don't have to happen atomically, even if they cross multiple instructions.
Section 8.1.3 states the following regarding XMC:
To write cross-modifying code and ensure that it is compliant with current and future versions of the IA-32 architecture, the following processor synchronization algorithm must be implemented:
(* Action of Modifying Processor *)
Memory_Flag := 0; (* Set Memory_Flag to value other than 1 *)
Store modified code (as data) into code segment;
Memory_Flag := 1;(* Action of Executing Processor *)
WHILE (Memory_Flag ≠ 1)
Wait for code to update;
ELIHW;
Execute serializing instruction; (* For example, CPUID instruction *)
Begin executing modified code;(The use of this option is not required for programs intended to run on the Intel486 processor, but is recommended to ensure compatibility with the Pentium 4, Intel Xeon, P6 family, and Pentium processors.)
A fully serializing instruction is required here for a different reason mentioned in the errata of some Intel processors: cross-processor snoops may only snoop the instruction cache and not the prefetch buffers or internal pipeline buffers. The processor may speculatively fetch instructions before it observes all modifications and, without full serialization, it may execute a mix of old and new instruction bytes. A fully serializing instruction prevents speculative fetches. The code without serialization is called unsynchronized XMC. As the manual states, serialization is not needed on the 486.
AMD processors also require a fully serializing instruction to be executed on the executing processor before the modified instructions. On AMD, MFENCE is fully serializing and more convenient than CPUID.
Intel's algorithm assumes that the executing processor remains in a waiting state until Memory_Flag is changed to 1. The initial state of Memory_Flag is assumed to be not 1. If both processors are executing in parallel, the modifying processor should make sure that the executing processor is outside of the execution region before modifying any instructions. This can be achieved using a readers–writer mutex in general.
Now let's get back to the hotpatching example you've provided and check if it works correctly with respect to only architectural guarantees on Intel processors. It can be modeled as follows:
(\* Action of Modifying Processor \*)
Store 0xEB;
Store offset;
(\* Action of Executing Processor \*)
Execute the first instruction of the function, which is at least two bytes in size;
If the two bytes cross an instruction cache line boundary, the following may occur:
By the way, instruction fetch atomicity at the instruction granularity would have prevented this scenario from occurring.
I think this scenario is also possible if the two bytes cross a predecode chunk boundary (16 bytes) and both are in the same line due to the errata mentioned earlier. Although this is very unlikely because the cache line has to be invalidate exactly between two consecutive 16-byte chunk fetches into the predecode unit.
If the two bytes are fully contained in the same 16-byte fetch unit and if the compiler emitted code such that the two bytes may not be written atomically as a single unit, it's possible that one byte reaches GO and fetched and executed by the executing processor before the other byte reaches GO. Therefore, in this case as well, the executing processor may attempt to execute an instruction that begins with a new byte and an old byte.
Finally, if the two bytes are fully contained in the same 16-byte fetch unit and if the compiler emitted code such that the two written bytes reach GO atomically, the executing processor will either execute the old bytes or the new bytes, never mixed bytes. The readers–writer mutex semantics are provided naturally.
The default 16-byte alignment of functions ensures that the two bytes are in the same 16-byte fetch unit. A single 2-byte store instruction to a 16-byte aligned address is guaranteed to be atomic on the 486 and later (Section 8.1.1). However, the stores *(u8*)from = 0xEB; and *(u8*)(from + 1) = (u8)offset; are not guaranteed to be compiled into a single store instruction. With multiple store instructions, an interrupt can occur on the modifying processor before all reach GO, greatly increasing the chance of the executing processor executing mixed bytes. This is a bug. Relaying on 16-byte alignment works in practice, but it violates Section 8.1.3.
On AMD processors, the first two bytes must also be modified atomically, but the 16-byte alignment is not sufficient according to the architectural requirements in APM V2 Section 7.6.1. The instruction being modified must be contained entirely within a naturally-aligned quadword. If the compiler emits a dummy 2-byte instruction at the beginning of the function, then it would satisfy this requirement.
AMD officially supports unsynchronized XMC if some requirements are satisfied. Intel doesn't architecturally support unsynchronized XMC at all, although it does work in practice if some requirements are satisfied as already discussed.
Regarding the following comment:
// 3) HotPatch
//
// The HotPatch hooking is assuming the presence of an header with padding
// and a first instruction with at least 2-bytes.
//
// The reason to enforce the 2-bytes limitation is to provide the minimal
// space to encode a short jump. HotPatch technique is only rewriting one
// instruction to avoid breaking a sequence of instructions containing a
// branching target.
Well, if the first instruction is only one byte in size, irrespective of alignment and atomicity, an interrupt can occur on the executing processor immediately after retiring the first instruction but before retiring the second one. If the modifying processor modified the bytes before the executing processor returns from handling the interrupt, then when it returns, the behavior is unpredictable. So even if there are no branch targets inside the function, the first instruction still has to be at least 2 bytes in size.