[RFC,v2,03/11] docs: new design document multi-thread-tcg.txt (DRAFTING)

This is a current DRAFT of a design proposal for upgrading TCG emulation
to take advantage of modern CPUs by running a thread-per-CPU. The
document goes through the various areas of the code affected by such a
change and proposes design requirements for each part of the solution.

It has been written *without* explicit reference to the current ongoing
efforts to introduce this feature. The hope being we can review and
discuss the design choices without assuming the current choices taken by
the implementation are correct.

Signed-off-by: Alex Bennée <alex.bennee@linaro.org>

---
v1
  - initial version
v2
  - update discussion on locks
  - bit more detail on vCPU scheduling
  - explicitly mention Translation Blocks
  - emulated hardware state already covered by iomutex
  - a few minor rewords
---
 docs/multi-thread-tcg.txt | 184 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 184 insertions(+)
 create mode 100644 docs/multi-thread-tcg.txt

On 05/04/16 18:32, Alex Bennée wrote:

(snip)
> +Introduction
> +============
> +
> +This document outlines the design for multi-threaded TCG emulation.
> +The original TCG implementation was single threaded and dealt with
> +multiple CPUs by with simple round-robin scheduling. This simplified a
> +lot of things but became increasingly limited as systems being
> +emulated gained additional cores and per-core performance gains for
> +host systems started to level off.

This looks like the description of system-mode TCG only. Maybe it would
be worth mentioning current status of user-mode multithreading support
as well?

(snip)
> +Shared Data Structures
> +======================
> +
> +Global TCG State
> +----------------
> +
> +We need to protect the entire code generation cycle including any post
> +generation patching of the translated code. This also implies a shared
> +translation buffer which contains code running on all cores. Any
> +execution path that comes to the main run loop will need to hold a
> +mutex for code generation. This also includes times when we need flush
> +code or jumps from the tb_cache.
> +
> +DESIGN REQUIREMENT: Add locking around all code generation, patching
> +and jump cache modification.

I think we could also benefit from some kind of "lock-free" algorithms
where it is possible. So locking as a requirement seems to be a bit too
enforcing. Regarding shared translation buffer, how is it implied? Don't
we have on option of separate per-vCPU code cache? (Maybe I missed some
discussion on this?)

> +
> +Translation Blocks
> +------------------
> +
> +Currently the whole system shares a single code generation buffer
> +which when full will force a flush of all translations and start from
> +scratch again.
> +
> +Once a basic block has been translated it will continue to be used
> +until it is invalidated. These invalidation events are typically due
> +to page changes in system emulation

I didn't dig too deep into this yet, but TLB invalidation after
virtual-to-physical address mapping changes doesn't seem to invalidate
any TBs in system mode...

>  and changes in memory mapping in
> +user mode. Debugging operations 

and self modifying code

> can also trigger invalidation's.
> +
> +The invalidation also requires removing the TB from look-ups
> +(tb_phys_hash and tb_jmp_cache) as well removing any direct TB to TB
> +patched jumps.

We could probably get by lazy approach with just preventing to pick up
invalidated TBs from look-ups. It also possible not to remove direct
jumps from the TB being invalidated to other TBs since it is not going
to be executed anyway.

> +
> +DESIGN REQUIREMENT: Safely handle invalidation of TBs

It would probably be a good idea to include translation buffer flush
considerations as well.

> +
> +Memory maps and TLBs
> +--------------------
> +
> +The memory handling code is fairly critical to the speed of memory
> +access in the emulated system.
> +

It would be nice to put some intro sentence for the following bullets :)

> +  - Memory regions (dividing up access to PIO, MMIO and RAM)
> +  - Dirty page tracking (for code gen, migration and display)
> +  - Virtual TLB (for translating guest address->real address)
> +
> +There is a both a fast path walked by the generated code and a slow
> +path when resolution is required. When the TLB tables are updated we
> +need to ensure they are done in a safe way by bringing all executing
> +threads to a halt before making the modifications.

Again, I think we could benefit if we could possibly manage to avoid
bringing vCPU threads to halt.

Nothing about memory regions and dirty page tracking?

> +
> +DESIGN REQUIREMENTS:
> +
> +  - TLB Flush All/Page
> +    - can be across-CPUs
> +    - will need all other CPUs brought to a halt

s/will/may/ ?

> +  - TLB Update (update a CPUTLBEntry, via tlb_set_page_with_attrs)
> +    - This is a per-CPU table - by definition can't race
> +    - updated by it's own thread when the slow-path is forced
(snip)
> +Memory Consistency
> +==================
> +
> +Between emulated guests and host systems there are a range of memory
> +consistency models. While emulating weakly ordered systems on strongly
> +ordered hosts shouldn't cause any problems the same is not true for
> +the reverse setup.
> +
> +The proposed design currently does not address the problem of
> +emulating strong ordering on a weakly ordered host although even on
> +strongly ordered systems software should be using synchronisation
> +primitives to ensure correct operation.

e.g. strongly-ordered x86 allows store-after-load reordering and
provides memory fences to synchronize.

> +
> +Memory Barriers
> +---------------
> +
> +Barriers (sometimes known as fences) provide a mechanism for software
> +to enforce a particular ordering of memory operations from the point
> +of view of external observers (e.g. another processor core). They can
> +apply to any memory operations as well as just loads or stores.
> +
> +The Linux kernel has an excellent write-up on the various forms of
> +memory barrier and the guarantees they can provide [1].
> +
> +Barriers are often wrapped around synchronisation primitives to
> +provide explicit memory ordering semantics. However they can be used
> +by themselves to provide safe lockless access by ensuring for example
> +a signal flag will always be set after a payload.
> +
> +DESIGN REQUIREMENT: Add a new tcg_memory_barrier op
> +
> +This would enforce a strong load/store ordering so all loads/stores
> +complete at the memory barrier. On single-core non-SMP strongly
> +ordered backends this could become a NOP.
> +
> +There may be a case for further refinement if this causes performance
> +bottlenecks.

I think we'd better make a provision and add some flags to the memory
barrier operation to specify what kind of barrier is required.

Another idea is that we could associate memory ordering attribute with
each TCG load/store operation and meet memory ordering requirements
across various TCG targets and hosts in a uniform way.

(snip)

Kind regards,
Sergey

On 05/04/16 18:32, Alex Bennée wrote:
> This is a current DRAFT of a design proposal for upgrading TCG emulation
> to take advantage of modern CPUs by running a thread-per-CPU. The
> document goes through the various areas of the code affected by such a
> change and proposes design requirements for each part of the solution.
>
> It has been written *without* explicit reference to the current ongoing
> efforts to introduce this feature. The hope being we can review and
> discuss the design choices without assuming the current choices taken by
> the implementation are correct.
>
> Signed-off-by: Alex Bennée <alex.bennee@linaro.org>
>
> ---
> v1
>   - initial version
> v2
>   - update discussion on locks
>   - bit more detail on vCPU scheduling
>   - explicitly mention Translation Blocks
>   - emulated hardware state already covered by iomutex
>   - a few minor rewords

We could also include a few words about icount mode support in MTTCG.

Kind regards,
Sergey

On 11/04/16 23:00, Sergey Fedorov wrote:
> On 05/04/16 18:32, Alex Bennée wrote:
>
> (snip)
>> +
>> +Memory maps and TLBs
>> +--------------------
>> +
>> +The memory handling code is fairly critical to the speed of memory
>> +access in the emulated system.
>> +
> It would be nice to put some intro sentence for the following bullets :)
>
>> +  - Memory regions (dividing up access to PIO, MMIO and RAM)
>> +  - Dirty page tracking (for code gen, migration and display)
>> +  - Virtual TLB (for translating guest address->real address)

There's also a global page table - called 'l1_map' - which is used for:
 * keeping a list of TBs generated from a given physical guest page for
   further code invalidation on page writes
 * holding a bitmap to track which regions of a given physical guest page
   actually contain code for optimized code invalidation on page writes
   (used only in system mode emulation)
 * holding page flags, e.g. protection bits (used only in user mode
   emulation)

The page table seems to be protected by 'mmap_lock' in user mode
emulation but by 'tb_lock' in system mode emulation. It may turn to be
possible to read it safely even with no lock held.

Kind regards,
Sergey

>> +
>> +There is a both a fast path walked by the generated code and a slow
>> +path when resolution is required. When the TLB tables are updated we
>> +need to ensure they are done in a safe way by bringing all executing
>> +threads to a halt before making the modifications.
> Again, I think we could benefit if we could possibly manage to avoid
> bringing vCPU threads to halt.
>
> Nothing about memory regions and dirty page tracking?
>
>> +
>> +DESIGN REQUIREMENTS:
>> +
>> +  - TLB Flush All/Page
>> +    - can be across-CPUs
>> +    - will need all other CPUs brought to a halt
> s/will/may/ ?
>
>> +  - TLB Update (update a CPUTLBEntry, via tlb_set_page_with_attrs)
>> +    - This is a per-CPU table - by definition can't race
>> +    - updated by it's own thread when the slow-path is forced
> (snip)

Kind regards,
Sergey

Sergey Fedorov <serge.fdrv@gmail.com> writes:

> On 11/04/16 23:00, Sergey Fedorov wrote:
>> On 05/04/16 18:32, Alex Bennée wrote:
>>
>> (snip)
>>> +
>>> +Memory maps and TLBs
>>> +--------------------
>>> +
>>> +The memory handling code is fairly critical to the speed of memory
>>> +access in the emulated system.
>>> +
>> It would be nice to put some intro sentence for the following bullets :)
>>
>>> +  - Memory regions (dividing up access to PIO, MMIO and RAM)
>>> +  - Dirty page tracking (for code gen, migration and display)
>>> +  - Virtual TLB (for translating guest address->real address)
>
> There's also a global page table - called 'l1_map' - which is used for:
>  * keeping a list of TBs generated from a given physical guest page for
>    further code invalidation on page writes
>  * holding a bitmap to track which regions of a given physical guest page
>    actually contain code for optimized code invalidation on page writes
>    (used only in system mode emulation)
>  * holding page flags, e.g. protection bits (used only in user mode
>    emulation)
>
> The page table seems to be protected by 'mmap_lock' in user mode
> emulation but by 'tb_lock' in system mode emulation. It may turn to be
> possible to read it safely even with no lock held.

I've started adding words to that effect to the document.

>
> Kind regards,
> Sergey
>
>>> +
>>> +There is a both a fast path walked by the generated code and a slow
>>> +path when resolution is required. When the TLB tables are updated we
>>> +need to ensure they are done in a safe way by bringing all executing
>>> +threads to a halt before making the modifications.
>> Again, I think we could benefit if we could possibly manage to avoid
>> bringing vCPU threads to halt.
>>
>> Nothing about memory regions and dirty page tracking?
>>
>>> +
>>> +DESIGN REQUIREMENTS:
>>> +
>>> +  - TLB Flush All/Page
>>> +    - can be across-CPUs
>>> +    - will need all other CPUs brought to a halt
>> s/will/may/ ?
>>
>>> +  - TLB Update (update a CPUTLBEntry, via tlb_set_page_with_attrs)
>>> +    - This is a per-CPU table - by definition can't race
>>> +    - updated by it's own thread when the slow-path is forced
>> (snip)
>
> Kind regards,
> Sergey


--
Alex Bennée

> The page table seems to be protected by 'mmap_lock' in user mode
> emulation but by 'tb_lock' in system mode emulation. It may turn to be
> possible to read it safely even with no lock held.

Yes, it is possible to at least follow the radix tree safely with no
lock held.  The fields in the leaves can be either lockless or protected
by a lock.

The radix tree can be followed without a lock just like you do with RCU.
The difference with RCU is that:

1) the leaves are protected with a lock, so you don't do the "copy";
instead after reading you lock around updates

2) the radix tree is only ever added to, so you don't need to protect
the reads with rcu_read_lock/rcu_read_unlock.  rcu_read_lock and
rcu_read_unlock are only needed to inform the deleters that something
cannot yet go away.  Without deleters, you don't need rcu_read_lock
and rcu_read_unlock (but you still need atomic_rcu_read/atomic_rcu_set).

Paolo

On 25/05/16 21:03, Paolo Bonzini wrote:
>> The page table seems to be protected by 'mmap_lock' in user mode
>> emulation but by 'tb_lock' in system mode emulation. It may turn to be
>> possible to read it safely even with no lock held.
> Yes, it is possible to at least follow the radix tree safely with no
> lock held.  The fields in the leaves can be either lockless or protected
> by a lock.
>
> The radix tree can be followed without a lock just like you do with RCU.
> The difference with RCU is that:
>
> 1) the leaves are protected with a lock, so you don't do the "copy";
> instead after reading you lock around updates
>
> 2) the radix tree is only ever added to, so you don't need to protect
> the reads with rcu_read_lock/rcu_read_unlock.  rcu_read_lock and
> rcu_read_unlock are only needed to inform the deleters that something
> cannot yet go away.  Without deleters, you don't need rcu_read_lock
> and rcu_read_unlock (but you still need atomic_rcu_read/atomic_rcu_set).
>
>

Yes, however looking closer at how the leafs are used I can't see much
point to do this so far...

Thanks,
Sergey