| 1 | .. |
| 2 | Copyright (c) 2015-2020 Linaro Ltd. |
| 3 | |
| 4 | This work is licensed under the terms of the GNU GPL, version 2 or |
| 5 | later. See the COPYING file in the top-level directory. |
| 6 | |
| 7 | .. _mttcg: |
| 8 | |
| 9 | ================== |
| 10 | Multi-threaded TCG |
| 11 | ================== |
| 12 | |
| 13 | This document outlines the design for multi-threaded TCG (a.k.a MTTCG) |
| 14 | system-mode emulation. user-mode emulation has always mirrored the |
| 15 | thread structure of the translated executable although some of the |
| 16 | changes done for MTTCG system emulation have improved the stability of |
| 17 | linux-user emulation. |
| 18 | |
| 19 | The original system-mode TCG implementation was single threaded and |
| 20 | dealt with multiple CPUs with simple round-robin scheduling. This |
| 21 | simplified a lot of things but became increasingly limited as systems |
| 22 | being emulated gained additional cores and per-core performance gains |
| 23 | for host systems started to level off. |
| 24 | |
| 25 | vCPU Scheduling |
| 26 | =============== |
| 27 | |
| 28 | We introduce a new running mode where each vCPU will run on its own |
| 29 | user-space thread. This is enabled by default for all FE/BE |
| 30 | combinations where the host memory model is able to accommodate the |
| 31 | guest (TCGCPUOps::guest_default_memory_order & ~TCG_TARGET_DEFAULT_MO is zero) |
| 32 | and the guest has had the required work done to support this safely |
| 33 | (TCGCPUOps::mttcg_supported). |
| 34 | |
| 35 | System emulation will fall back to the original round robin approach |
| 36 | if: |
| 37 | |
| 38 | * forced by --accel tcg,thread=single |
| 39 | * enabling --icount mode |
| 40 | |
| 41 | In the general case of running translated code there should be no |
| 42 | inter-vCPU dependencies and all vCPUs should be able to run at full |
| 43 | speed. Synchronisation will only be required while accessing internal |
| 44 | shared data structures or when the emulated architecture requires a |
| 45 | coherent representation of the emulated machine state. |
| 46 | |
| 47 | Shared Data Structures |
| 48 | ====================== |
| 49 | |
| 50 | Main Run Loop |
| 51 | ------------- |
| 52 | |
| 53 | Even when there is no code being generated there are a number of |
| 54 | structures associated with the hot-path through the main run-loop. |
| 55 | These are associated with looking up the next translation block to |
| 56 | execute. These include: |
| 57 | |
| 58 | tb_jmp_cache (per-vCPU, cache of recent jumps) |
| 59 | tb_ctx.htable (global hash table, phys address->tb lookup) |
| 60 | |
| 61 | As TB linking only occurs when blocks are in the same page this code |
| 62 | is critical to performance as looking up the next TB to execute is the |
| 63 | most common reason to exit the generated code. |
| 64 | |
| 65 | DESIGN REQUIREMENT: Make access to lookup structures safe with |
| 66 | multiple reader/writer threads. Minimise any lock contention to do it. |
| 67 | |
| 68 | The hot-path avoids using locks where possible. The tb_jmp_cache is |
| 69 | updated with atomic accesses to ensure consistent results. The fall |
| 70 | back QHT based hash table is also designed for lockless lookups. Locks |
| 71 | are only taken when code generation is required or TranslationBlocks |
| 72 | have their block-to-block jumps patched. |
| 73 | |
| 74 | Global TCG State |
| 75 | ---------------- |
| 76 | |
| 77 | User-mode emulation |
| 78 | ~~~~~~~~~~~~~~~~~~~ |
| 79 | |
| 80 | We need to protect the entire code generation cycle including any post |
| 81 | generation patching of the translated code. This also implies a shared |
| 82 | translation buffer which contains code running on all cores. Any |
| 83 | execution path that comes to the main run loop will need to hold a |
| 84 | mutex for code generation. This also includes times when we need flush |
| 85 | code or entries from any shared lookups/caches. Structures held on a |
| 86 | per-vCPU basis won't need locking unless other vCPUs will need to |
| 87 | modify them. |
| 88 | |
| 89 | DESIGN REQUIREMENT: Add locking around all code generation and TB |
| 90 | patching. |
| 91 | |
| 92 | (Current solution) |
| 93 | |
| 94 | Code generation is serialised with mmap_lock(). |
| 95 | |
| 96 | !User-mode emulation |
| 97 | ~~~~~~~~~~~~~~~~~~~~ |
| 98 | |
| 99 | Each vCPU has its own TCG context and associated TCG region, thereby |
| 100 | requiring no locking during translation. |
| 101 | |
| 102 | Translation Blocks |
| 103 | ------------------ |
| 104 | |
| 105 | Currently the whole system shares a single code generation buffer |
| 106 | which when full will force a flush of all translations and start from |
| 107 | scratch again. Some operations also force a full flush of translations |
| 108 | including: |
| 109 | |
| 110 | - debugging operations (breakpoint insertion/removal) |
| 111 | - some CPU helper functions |
| 112 | - linux-user spawning its first thread |
| 113 | - operations related to TCG Plugins |
| 114 | |
| 115 | This is done with the async_safe_run_on_cpu() mechanism to ensure all |
| 116 | vCPUs are quiescent when changes are being made to shared global |
| 117 | structures. |
| 118 | |
| 119 | More granular translation invalidation events are typically due |
| 120 | to a change of the state of a physical page: |
| 121 | |
| 122 | - code modification (self modify code, patching code) |
| 123 | - page changes (new page mapping in linux-user mode) |
| 124 | |
| 125 | While setting the invalid flag in a TranslationBlock will stop it |
| 126 | being used when looked up in the hot-path there are a number of other |
| 127 | book-keeping structures that need to be safely cleared. |
| 128 | |
| 129 | Any TranslationBlocks which have been patched to jump directly to the |
| 130 | now invalid blocks need the jump patches reversing so they will return |
| 131 | to the C code. |
| 132 | |
| 133 | There are a number of look-up caches that need to be properly updated |
| 134 | including the: |
| 135 | |
| 136 | - jump lookup cache |
| 137 | - the physical-to-tb lookup hash table |
| 138 | - the global page table |
| 139 | |
| 140 | The global page table (l1_map) which provides a multi-level look-up |
| 141 | for PageDesc structures which contain pointers to the start of a |
| 142 | linked list of all Translation Blocks in that page (see page_next). |
| 143 | |
| 144 | Both the jump patching and the page cache involve linked lists that |
| 145 | the invalidated TranslationBlock needs to be removed from. |
| 146 | |
| 147 | DESIGN REQUIREMENT: Safely handle invalidation of TBs |
| 148 | - safely patch/revert direct jumps |
| 149 | - remove central PageDesc lookup entries |
| 150 | - ensure lookup caches/hashes are safely updated |
| 151 | |
| 152 | (Current solution) |
| 153 | |
| 154 | The direct jump themselves are updated atomically by the TCG |
| 155 | tb_set_jmp_target() code. Modification to the linked lists that allow |
| 156 | searching for linked pages are done under the protection of tb->jmp_lock, |
| 157 | where tb is the destination block of a jump. Each origin block keeps a |
| 158 | pointer to its destinations so that the appropriate lock can be acquired before |
| 159 | iterating over a jump list. |
| 160 | |
| 161 | The global page table is a lockless radix tree; cmpxchg is used |
| 162 | to atomically insert new elements. |
| 163 | |
| 164 | The lookup caches are updated atomically and the lookup hash uses QHT |
| 165 | which is designed for concurrent safe lookup. |
| 166 | |
| 167 | Parallel code generation is supported. QHT is used at insertion time |
| 168 | as the synchronization point across threads, thereby ensuring that we only |
| 169 | keep track of a single TranslationBlock for each guest code block. |
| 170 | |
| 171 | Memory maps and TLBs |
| 172 | -------------------- |
| 173 | |
| 174 | The memory handling code is fairly critical to the speed of memory |
| 175 | access in the emulated system. The SoftMMU code is designed so the |
| 176 | hot-path can be handled entirely within translated code. This is |
| 177 | handled with a per-vCPU TLB structure which once populated will allow |
| 178 | a series of accesses to the page to occur without exiting the |
| 179 | translated code. It is possible to set flags in the TLB address which |
| 180 | will ensure the slow-path is taken for each access. This can be done |
| 181 | to support: |
| 182 | |
| 183 | - Memory regions (dividing up access to PIO, MMIO and RAM) |
| 184 | - Dirty page tracking (for code gen, SMC detection, migration and display) |
| 185 | - Virtual TLB (for translating guest address->real address) |
| 186 | |
| 187 | When the TLB tables are updated by a vCPU thread other than their own |
| 188 | we need to ensure it is done in a safe way so no inconsistent state is |
| 189 | seen by the vCPU thread. |
| 190 | |
| 191 | Some operations require updating a number of vCPUs TLBs at the same |
| 192 | time in a synchronised manner. |
| 193 | |
| 194 | DESIGN REQUIREMENTS: |
| 195 | |
| 196 | - TLB Flush All/Page |
| 197 | - can be across-vCPUs |
| 198 | - cross vCPU TLB flush may need other vCPU brought to halt |
| 199 | - change may need to be visible to the calling vCPU immediately |
| 200 | - TLB Flag Update |
| 201 | - usually cross-vCPU |
| 202 | - want change to be visible as soon as possible |
| 203 | - TLB Update (update a CPUTLBEntry, via tlb_set_page_with_attrs) |
| 204 | - This is a per-vCPU table - by definition can't race |
| 205 | - updated by its own thread when the slow-path is forced |
| 206 | |
| 207 | (Current solution) |
| 208 | |
| 209 | A new set of tlb flush operations (tlb_flush_*_all_cpus_synced) force |
| 210 | synchronisation by setting the source vCPUs work as "safe work" and |
| 211 | exiting the cpu run loop. This ensures that by the time execution |
| 212 | restarts all flush operations have completed. |
| 213 | |
| 214 | TLB flag updates are all done atomically and are also protected by the |
| 215 | corresponding page lock. |
| 216 | |
| 217 | (Known limitation) |
| 218 | |
| 219 | Not really a limitation but the wait mechanism is overly strict for |
| 220 | some architectures which only need flushes completed by a barrier |
| 221 | instruction. This could be a future optimisation. |
| 222 | |
| 223 | Emulated hardware state |
| 224 | ----------------------- |
| 225 | |
| 226 | Currently thanks to KVM work any access to IO memory is automatically protected |
| 227 | by the BQL (Big QEMU Lock). Any IO region that doesn't use the BQL is expected |
| 228 | to do its own locking. |
| 229 | |
| 230 | However IO memory isn't the only way emulated hardware state can be |
| 231 | modified. Some architectures have model specific registers that |
| 232 | trigger hardware emulation features. Generally any translation helper |
| 233 | that needs to update more than a single vCPUs of state should take the |
| 234 | BQL. |
| 235 | |
| 236 | As the BQL, or global iothread mutex is shared across the system we |
| 237 | push the use of the lock as far down into the TCG code as possible to |
| 238 | minimise contention. |
| 239 | |
| 240 | (Current solution) |
| 241 | |
| 242 | MMIO access automatically serialises hardware emulation by way of the |
| 243 | BQL. Currently Arm targets serialise all ARM_CP_IO register accesses |
| 244 | and also defer the reset/startup of vCPUs to the vCPU context by way |
| 245 | of async_run_on_cpu(). |
| 246 | |
| 247 | Updates to interrupt state are also protected by the BQL as they can |
| 248 | often be cross vCPU. |
| 249 | |
| 250 | Memory Consistency |
| 251 | ================== |
| 252 | |
| 253 | Between emulated guests and host systems there are a range of memory |
| 254 | consistency models. Even emulating weakly ordered systems on strongly |
| 255 | ordered hosts needs to ensure things like store-after-load re-ordering |
| 256 | can be prevented when the guest wants to. |
| 257 | |
| 258 | Memory Barriers |
| 259 | --------------- |
| 260 | |
| 261 | Barriers (sometimes known as fences) provide a mechanism for software |
| 262 | to enforce a particular ordering of memory operations from the point |
| 263 | of view of external observers (e.g. another processor core). They can |
| 264 | apply to any memory operations as well as just loads or stores. |
| 265 | |
| 266 | The Linux kernel has an excellent `write-up |
| 267 | <https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/plain/Documentation/memory-barriers.txt>`_ |
| 268 | on the various forms of memory barrier and the guarantees they can |
| 269 | provide. |
| 270 | |
| 271 | Barriers are often wrapped around synchronisation primitives to |
| 272 | provide explicit memory ordering semantics. However they can be used |
| 273 | by themselves to provide safe lockless access by ensuring for example |
| 274 | a change to a signal flag will only be visible once the changes to |
| 275 | payload are. |
| 276 | |
| 277 | DESIGN REQUIREMENT: Add a new tcg_memory_barrier op |
| 278 | |
| 279 | This would enforce a strong load/store ordering so all loads/stores |
| 280 | complete at the memory barrier. On single-core non-SMP strongly |
| 281 | ordered backends this could become a NOP. |
| 282 | |
| 283 | Aside from explicit standalone memory barrier instructions there are |
| 284 | also implicit memory ordering semantics which comes with each guest |
| 285 | memory access instruction. For example all x86 load/stores come with |
| 286 | fairly strong guarantees of sequential consistency whereas Arm has |
| 287 | special variants of load/store instructions that imply acquire/release |
| 288 | semantics. |
| 289 | |
| 290 | In the case of a strongly ordered guest architecture being emulated on |
| 291 | a weakly ordered host the scope for a heavy performance impact is |
| 292 | quite high. |
| 293 | |
| 294 | DESIGN REQUIREMENTS: Be efficient with use of memory barriers |
| 295 | - host systems with stronger implied guarantees can skip some barriers |
| 296 | - merge consecutive barriers to the strongest one |
| 297 | |
| 298 | (Current solution) |
| 299 | |
| 300 | The system currently has a tcg_gen_mb() which will add memory barrier |
| 301 | operations if code generation is being done in a parallel context. The |
| 302 | tcg_optimize() function attempts to merge barriers up to their |
| 303 | strongest form before any load/store operations. The solution was |
| 304 | originally developed and tested for linux-user based systems. All |
| 305 | backends have been converted to emit fences when required. So far the |
| 306 | following front-ends have been updated to emit fences when required: |
| 307 | |
| 308 | - target-i386 |
| 309 | - target-arm |
| 310 | - target-aarch64 |
| 311 | - target-alpha |
| 312 | - target-mips |
| 313 | |
| 314 | Memory Control and Maintenance |
| 315 | ------------------------------ |
| 316 | |
| 317 | This includes a class of instructions for controlling system cache |
| 318 | behaviour. While QEMU doesn't model cache behaviour these instructions |
| 319 | are often seen when code modification has taken place to ensure the |
| 320 | changes take effect. |
| 321 | |
| 322 | Synchronisation Primitives |
| 323 | -------------------------- |
| 324 | |
| 325 | There are two broad types of synchronisation primitives found in |
| 326 | modern ISAs: atomic instructions and exclusive regions. |
| 327 | |
| 328 | The first type offer a simple atomic instruction which will guarantee |
| 329 | some sort of test and conditional store will be truly atomic w.r.t. |
| 330 | other cores sharing access to the memory. The classic example is the |
| 331 | x86 cmpxchg instruction. |
| 332 | |
| 333 | The second type offer a pair of load/store instructions which offer a |
| 334 | guarantee that a region of memory has not been touched between the |
| 335 | load and store instructions. An example of this is Arm's ldrex/strex |
| 336 | pair where the strex instruction will return a flag indicating a |
| 337 | successful store only if no other CPU has accessed the memory region |
| 338 | since the ldrex. |
| 339 | |
| 340 | Traditionally TCG has generated a series of operations that work |
| 341 | because they are within the context of a single translation block so |
| 342 | will have completed before another CPU is scheduled. However with |
| 343 | the ability to have multiple threads running to emulate multiple CPUs |
| 344 | we will need to explicitly expose these semantics. |
| 345 | |
| 346 | DESIGN REQUIREMENTS: |
| 347 | - Support classic atomic instructions |
| 348 | - Support load/store exclusive (or load link/store conditional) pairs |
| 349 | - Generic enough infrastructure to support all guest architectures |
| 350 | CURRENT OPEN QUESTIONS: |
| 351 | - How problematic is the ABA problem in general? |
| 352 | |
| 353 | (Current solution) |
| 354 | |
| 355 | The TCG provides a number of atomic helpers (tcg_gen_atomic_*) which |
| 356 | can be used directly or combined to emulate other instructions like |
| 357 | Arm's ldrex/strex instructions. While they are susceptible to the ABA |
| 358 | problem so far common guests have not implemented patterns where |
| 359 | this may be a problem - typically presenting a locking ABI which |
| 360 | assumes cmpxchg like semantics. |
| 361 | |
| 362 | The code also includes a fall-back for cases where multi-threaded TCG |
| 363 | ops can't work (e.g. guest atomic width > host atomic width). In this |
| 364 | case an EXCP_ATOMIC exit occurs and the instruction is emulated with |
| 365 | an exclusive lock which ensures all emulation is serialised. |
| 366 | |
| 367 | While the atomic helpers look good enough for now there may be a need |
| 368 | to look at solutions that can more closely model the guest |
| 369 | architectures semantics. |