qemu-tls: make it portable

Fast TLS is not available on some platforms, but it is always nice to
use it.  This wrapper implementation falls back to pthread_get/setspecific
on POSIX systems that lack __thread, but uses the dynamic linker's TLS
support on Linux and Windows.

The user shall call tls_alloc_foo() in every thread that needs to access the
variable---exactly once and before any access.  foo is the name of the
variable as passed to DECLARE_TLS and DEFINE_TLS.  Then, tls_get_foo() will
return the address of the variable.  It is guaranteed to remain the same
across the lifetime of a thread, so you can cache it.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
qemu-thread: add QemuEvent

This emulates Win32 manual-reset events using futexes or conditional
variables.  Typical ways to use them are with multi-producer,
single-consumer data structures, to test for a complex condition whose
elements come from different threads:

    for (;;) {
        qemu_event_reset(ev);
        ... test complex condition ...
        if (condition is true) {
            break;
        }
        qemu_event_wait(ev);
    }

Or more efficiently (but with some duplication):

    ... evaluate condition ...
    while (!condition) {
        qemu_event_reset(ev);
        ... evaluate condition ...
        if (!condition) {
            qemu_event_wait(ev);
            ... evaluate condition ...
        }
    }

QemuEvent provides a very fast userspace path in the common case when
no other thread is waiting, or the event is not changing state.  It
is used to report RCU quiescent states to the thread calling
synchronize_rcu (the latter being the single consumer), and to report
call_rcu invocations to the thread that receives them.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
rcu: add rcu library

This includes a (mangled) copy of the urcu-qsbr code from liburcu.
The main changes are: 1) removing dependencies on many other header files
in liburcu; 2) removing for simplicity the tentative busy waiting in
synchronize_rcu, which has limited performance effects; 3) replacing
futexes in synchronize_rcu with QemuEvents for Win32 portability.
The API is the same as liburcu, so it should be possible in the future
to require liburcu on POSIX systems for example and use our copy only
on Windows.

Among the various versions available I chose urcu-qsbr, which has the
fastest rcu_read_{lock,unlock} but requires the program to manually
annotate quiescent points or intervals.  QEMU threads usually have easily
identified quiescent periods, so this should not be a problem.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
qemu-thread: register threads with RCU

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
rcu: add call_rcu

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
rcu: add rcutorture

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
rcu: allow nested calls to rcu_thread_offline/rcu_thread_online

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
qemu-thread: report RCU quiescent states

Most threads will use mutexes and other sleeping synchronization primitives
(condition variables, semaphores, events) periodically.  For these threads,
the synchronization primitives are natural places to report a quiescent
state (possibly an extended one).

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
event loop: report RCU quiescent states

Threads that run event loops also have places that can sleep for an extended
time.  Place an extended quiescent state there.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
cpus: report RCU quiescent states

CPU threads have extended quiescent states while relinquishing control
to the accelerator (except TCG).

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
block: report RCU quiescent states

The aio workers may spend a long time executing I/O operations;
mark that time as an extended quiescent state.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
migration: report RCU quiescent states

The migration thread polls s->state periodically, it does not
use a mutex or condition variable, so it has to report quiescent
states manually.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
memory: remove assertion on memory_region_destroy

Now that memory_region_destroy can be called from an RCU callback,
checking the BQL-protected global memory_region_transaction_depth
does not make much sense.

Signed-off-by: Jan Kiszka <jan.kiszka@siemens.com>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
memory: protect current_map by RCU

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
memory: avoid ref/unref in memory_region_find

Do the entire lookup under RCU.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
exec: introduce CPU_INTERRUPT_TLBFLUSH

Each change to the memory mapping invalidates the TLB, because new entries
in the TLB are based on a different AddressSpaceDispatch than before.
Synchronize the flush to prepare for atomically switching to a new
AddressSpaceDispatch.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
exec: make iotlb RCU-friendly

After the previous patch, TLBs will synchronize on every change to
the memory mapping.  This patch augments that with synchronization
of the MemoryRegionSections cached in the iotlb array.

Every change to RCU-protected data can now force an exit of the
current translation block, and the new data structure is updated
in the CPUArchState, so that each CPU_INTERRUPT_TLBFLUSH interrupt
constitutes the boundary of an RCU read-side critical section.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
exec: add a reference to the region returned by address_space_translate

Once address_space_translate will only be protected by RCU, the returned
MemoryRegion might disappear as soon as the RCU read-side critical section
ends.  Avoid this by adding a reference to the region, and dropping it
in the caller of address_space_translate.

This generalizes what was done for address_space_map to other callers of
address_space_translate.  It is necessary to call address_space_translate
out of the BQL.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
exec: put address space dispatch under RCU critical section

With this change, address space dispatch can be moved outside the
BQL.  The actual I/O would still have to happen within the lock.

The next step would be to introduce a function that can only
be called from outside the BQL, address_space_rw_unlocked.  The
function would do something like

    mr = address_space_translate(...)
    if (!mr->unlocked) {
        locked = true;
        qemu_mutex_lock_iothread();
    }
    ...dispatch...
    if (locked) {
        qemu_mutex_unlock_iothread();
    }

(Note that subpages are already ready to be changed to unlocked
access).

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
rcu: introduce RCU-enabled QLIST

Add RCU-enabled variants on the existing bsd DQ facility. Each
operation has the same interface as the existing (non-RCU)
version. Also, each operation is implemented as macro.

Using the RCU-enabled QLIST, existing QLIST users will be able to
convert to RCU without using a different list interface.

Signed-off-by: Mike Day <ncmike@ncultra.org>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>