From nobody Sat May 18 22:31:06 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1586200502; cv=none; d=zohomail.com; s=zohoarc; b=b5MzOtBltLbjNGiwfxJUF1PBrfpwIFh3b+jBcPGurP5p/lda0vrOXDksLcZP+Gj8W8IqynNNwI/p+s04OxUduQNFID1KtyYVkKtG+0+VHld0dEPh1EJHWQEpMi7iWUjCdKl4Icw0KfqrfZpVvMMHNhaHPRrDx8DnuKUUCeXEwos= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1586200502; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:Message-ID:References:Sender:Subject:To; bh=fo/y+XMTYVqCBhOZz+x0B4aXkV6VD8O9v7L3P4qf22g=; b=QOXze1I6uapXliwSSGuv2nO/l+p7DOEomwvj/DAuMdYaNvcTcQHwAii7ZOntB+Y2rHZP3NGrGiKGUQfUwjiI63r+MNH7/KxHlB8a9lyBwDA36TTL3VNuvoOKSfRn5K4IPHolYEWRvFKOWkgJOrm86pzJ7LUg3Zxvrp2mMQHXPes= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1586200502274645.0749352523001; Mon, 6 Apr 2020 12:15:02 -0700 (PDT) Received: from localhost ([::1]:37344 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jLXD2-0002j2-Gi for importer@patchew.org; Mon, 06 Apr 2020 15:15:00 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:52445) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jLXBg-00016t-Go for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:40 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1jLXBc-0006jG-2T for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:36 -0400 Received: from us-smtp-2.mimecast.com ([207.211.31.81]:23944 helo=us-smtp-delivery-1.mimecast.com) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1jLXBb-0006ik-S2 for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:32 -0400 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-123-QmFdtK4WOPem_Z16VDGSCQ-1; Mon, 06 Apr 2020 15:13:26 -0400 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 3D3BA107ACC9; Mon, 6 Apr 2020 19:13:25 +0000 (UTC) Received: from virtlab701.virt.lab.eng.bos.redhat.com (virtlab701.virt.lab.eng.bos.redhat.com [10.19.152.228]) by smtp.corp.redhat.com (Postfix) with ESMTP id 946E862697; Mon, 6 Apr 2020 19:13:24 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1586200411; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=fo/y+XMTYVqCBhOZz+x0B4aXkV6VD8O9v7L3P4qf22g=; b=PKY8OloRrJ0J5Dw1+miYA2rEKa6Z4o4SPfvTkN18XvWYni1iNDhDBPd5Orjs7RmCYQ78YV MAKsV1Ps6RXJKGlp+po5DKFFX3zbfACSO/zlhHDnNhgWPTSfKB9Znb3fJghPqZ0iU1wf1H FdBaeO+HrI5ccwdNfoaJeOB5ZKJID0o= X-MC-Unique: QmFdtK4WOPem_Z16VDGSCQ-1 From: Paolo Bonzini To: qemu-devel@nongnu.org Subject: [PATCH 1/4] atomics: convert to reStructuredText Date: Mon, 6 Apr 2020 15:13:17 -0400 Message-Id: <20200406191320.13371-2-pbonzini@redhat.com> In-Reply-To: <20200406191320.13371-1-pbonzini@redhat.com> References: <20200406191320.13371-1-pbonzini@redhat.com> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.15 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 207.211.31.81 X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Ying Fang , stefanha@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Signed-off-by: Paolo Bonzini Reviewed-by: Stefan Hajnoczi --- docs/devel/atomics.rst | 447 +++++++++++++++++++++++++++++++++++++++++ docs/devel/atomics.txt | 403 ------------------------------------- docs/devel/index.rst | 1 + 3 files changed, 448 insertions(+), 403 deletions(-) create mode 100644 docs/devel/atomics.rst delete mode 100644 docs/devel/atomics.txt diff --git a/docs/devel/atomics.rst b/docs/devel/atomics.rst new file mode 100644 index 0000000000..00f3f7d3ed --- /dev/null +++ b/docs/devel/atomics.rst @@ -0,0 +1,447 @@ +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D +Atomic operations in QEMU +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D + +CPUs perform independent memory operations effectively in random order. +but this can be a problem for CPU-CPU interaction (including interactions +between QEMU and the guest). Multi-threaded programs use various tools +to instruct the compiler and the CPU to restrict the order to something +that is consistent with the expectations of the programmer. + +The most basic tool is locking. Mutexes, condition variables and +semaphores are used in QEMU, and should be the default approach to +synchronization. Anything else is considerably harder, but it's +also justified more often than one would like. The two tools that +are provided by ``qemu/atomic.h`` are memory barriers and atomic operation= s. + +Macros defined by ``qemu/atomic.h`` fall in three camps: + +- compiler barriers: ``barrier()``; + +- weak atomic access and manual memory barriers: ``atomic_read()``, + ``atomic_set()``, ``smp_rmb()``, ``smp_wmb()``, ``smp_mb()``, ``smp_mb_a= cquire()``, + ``smp_mb_release()``, ``smp_read_barrier_depends()``; + +- sequentially consistent atomic access: everything else. + + +Compiler memory barrier +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +``barrier()`` prevents the compiler from moving the memory accesses either +side of it to the other side. The compiler barrier has no direct effect +on the CPU, which may then reorder things however it wishes. + +``barrier()`` is mostly used within ``qemu/atomic.h`` itself. On some +architectures, CPU guarantees are strong enough that blocking compiler +optimizations already ensures the correct order of execution. In this +case, ``qemu/atomic.h`` will reduce stronger memory barriers to simple +compiler barriers. + +Still, ``barrier()`` can be useful when writing code that can be interrupt= ed +by signal handlers. + + +Sequentially consistent atomic access +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +Most of the operations in the ``qemu/atomic.h`` header ensure *sequential +consistency*, where "the result of any execution is the same as if the +operations of all the processors were executed in some sequential order, +and the operations of each individual processor appear in this sequence +in the order specified by its program". + +``qemu/atomic.h`` provides the following set of atomic read-modify-write +operations:: + + void atomic_inc(ptr) + void atomic_dec(ptr) + void atomic_add(ptr, val) + void atomic_sub(ptr, val) + void atomic_and(ptr, val) + void atomic_or(ptr, val) + + typeof(*ptr) atomic_fetch_inc(ptr) + typeof(*ptr) atomic_fetch_dec(ptr) + typeof(*ptr) atomic_fetch_add(ptr, val) + typeof(*ptr) atomic_fetch_sub(ptr, val) + typeof(*ptr) atomic_fetch_and(ptr, val) + typeof(*ptr) atomic_fetch_or(ptr, val) + typeof(*ptr) atomic_fetch_xor(ptr, val) + typeof(*ptr) atomic_fetch_inc_nonzero(ptr) + typeof(*ptr) atomic_xchg(ptr, val) + typeof(*ptr) atomic_cmpxchg(ptr, old, new) + +all of which return the old value of ``*ptr``. These operations are +polymorphic; they operate on any type that is as wide as a pointer. + +Similar operations return the new value of ``*ptr``:: + + typeof(*ptr) atomic_inc_fetch(ptr) + typeof(*ptr) atomic_dec_fetch(ptr) + typeof(*ptr) atomic_add_fetch(ptr, val) + typeof(*ptr) atomic_sub_fetch(ptr, val) + typeof(*ptr) atomic_and_fetch(ptr, val) + typeof(*ptr) atomic_or_fetch(ptr, val) + typeof(*ptr) atomic_xor_fetch(ptr, val) + +Sequentially consistent loads and stores can be done using:: + + atomic_fetch_add(ptr, 0) for loads + atomic_xchg(ptr, val) for stores + +However, they are quite expensive on some platforms, notably POWER and +Arm. Therefore, qemu/atomic.h provides two primitives with slightly +weaker constraints:: + + typeof(*ptr) atomic_mb_read(ptr) + void atomic_mb_set(ptr, val) + +The semantics of these primitives map to Java volatile variables, +and are strongly related to memory barriers as used in the Linux +kernel (see below). + +As long as you use atomic_mb_read and atomic_mb_set, accesses cannot +be reordered with each other, and it is also not possible to reorder +"normal" accesses around them. + +However, and this is the important difference between +atomic_mb_read/atomic_mb_set and sequential consistency, it is important +for both threads to access the same volatile variable. It is not the +case that everything visible to thread A when it writes volatile field f +becomes visible to thread B after it reads volatile field g. The store +and load have to "match" (i.e., be performed on the same volatile +field) to achieve the right semantics. + + +These operations operate on any type that is as wide as an int or smaller. + + +Weak atomic access and manual memory barriers +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +Compared to sequentially consistent atomic access, programming with +weaker consistency models can be considerably more complicated. +In general, if the algorithm you are writing includes both writes +and reads on the same side, it is generally simpler to use sequentially +consistent primitives. + +When using this model, variables are accessed with: + +- ``atomic_read()`` and ``atomic_set()``; these prevent the compiler from + optimizing accesses out of existence and creating unsolicited + accesses, but do not otherwise impose any ordering on loads and + stores: both the compiler and the processor are free to reorder + them. + +- ``atomic_load_acquire()``, which guarantees the LOAD to appear to + happen, with respect to the other components of the system, + before all the LOAD or STORE operations specified afterwards. + Operations coming before ``atomic_load_acquire()`` can still be + reordered after it. + +- ``atomic_store_release()``, which guarantees the STORE to appear to + happen, with respect to the other components of the system, + after all the LOAD or STORE operations specified afterwards. + Operations coming after ``atomic_store_release()`` can still be + reordered after it. + +Restrictions to the ordering of accesses can also be specified +using the memory barrier macros: ``smp_rmb()``, ``smp_wmb()``, ``smp_mb()`= `, +``smp_mb_acquire()``, ``smp_mb_release()``, ``smp_read_barrier_depends()``. + +Memory barriers control the order of references to shared memory. +They come in six kinds: + +- ``smp_rmb()`` guarantees that all the LOAD operations specified before + the barrier will appear to happen before all the LOAD operations + specified after the barrier with respect to the other components of + the system. + + In other words, ``smp_rmb()`` puts a partial ordering on loads, but is n= ot + required to have any effect on stores. + +- ``smp_wmb()`` guarantees that all the STORE operations specified before + the barrier will appear to happen before all the STORE operations + specified after the barrier with respect to the other components of + the system. + + In other words, ``smp_wmb()`` puts a partial ordering on stores, but is = not + required to have any effect on loads. + +- ``smp_mb_acquire()`` guarantees that all the LOAD operations specified b= efore + the barrier will appear to happen before all the LOAD or STORE operations + specified after the barrier with respect to the other components of + the system. + +- ``smp_mb_release()`` guarantees that all the STORE operations specified = *after* + the barrier will appear to happen after all the LOAD or STORE operations + specified *before* the barrier with respect to the other components of + the system. + +- ``smp_mb()`` guarantees that all the LOAD and STORE operations specified + before the barrier will appear to happen before all the LOAD and + STORE operations specified after the barrier with respect to the other + components of the system. + + ``smp_mb()`` puts a partial ordering on both loads and stores. It is + stronger than both a read and a write memory barrier; it implies both + ``smp_mb_acquire()`` and ``smp_mb_release()``, but it also prevents STOR= Es + coming before the barrier from overtaking LOADs coming after the + barrier and vice versa. + +- ``smp_read_barrier_depends()`` is a weaker kind of read barrier. On + most processors, whenever two loads are performed such that the + second depends on the result of the first (e.g., the first load + retrieves the address to which the second load will be directed), + the processor will guarantee that the first LOAD will appear to happen + before the second with respect to the other components of the system. + However, this is not always true---for example, it was not true on + Alpha processors. Whenever this kind of access happens to shared + memory (that is not protected by a lock), a read barrier is needed, + and ``smp_read_barrier_depends()`` can be used instead of ``smp_rmb()``. + + Note that the first load really has to have a _data_ dependency and not + a control dependency. If the address for the second load is dependent + on the first load, but the dependency is through a conditional rather + than actually loading the address itself, then it's a _control_ + dependency and a full read barrier or better is required. + + +This is the set of barriers that is required *between* two ``atomic_read()= `` +and ``atomic_set()`` operations to achieve sequential consistency: + + +----------------+-----------------------------------------------------= --+ + | | 2nd operation = | + | +------------------+-----------------+----------------= --+ + | 1st operation | (after last) | atomic_read | atomic_set = | + +----------------+------------------+-----------------+----------------= --+ + | (before first) | .. | none | smp_mb_release(= ) | + +----------------+------------------+-----------------+----------------= --+ + | atomic_read | smp_mb_acquire() | smp_rmb() [1]_ | [2]_ = | + +----------------+------------------+-----------------+----------------= --+ + | atomic_set | none | smp_mb() [3]_ | smp_wmb() = | + +----------------+------------------+-----------------+----------------= --+ + + .. [1] Or smp_read_barrier_depends(). + + .. [2] This requires a load-store barrier. This is achieved by + either smp_mb_acquire() or smp_mb_release(). + + .. [3] This requires a store-load barrier. On most machines, the only + way to achieve this is a full barrier. + + +You can see that the two possible definitions of ``atomic_mb_read()`` +and ``atomic_mb_set()`` are the following: + + 1) | atomic_mb_read(p) =3D atomic_read(p); smp_mb_acquire() + | atomic_mb_set(p, v) =3D smp_mb_release(); atomic_set(p, v); smp_mb() + + 2) | atomic_mb_read(p) =3D smp_mb() atomic_read(p); smp_mb_acquire() + | atomic_mb_set(p, v) =3D smp_mb_release(); atomic_set(p, v); + +Usually the former is used, because ``smp_mb()`` is expensive and a program +normally has more reads than writes. Therefore it makes more sense to +make ``atomic_mb_set()`` the more expensive operation. + +There are two common cases in which atomic_mb_read and atomic_mb_set +generate too many memory barriers, and thus it can be useful to manually +place barriers, or use atomic_load_acquire/atomic_store_release instead: + +- when a data structure has one thread that is always a writer + and one thread that is always a reader, manual placement of + memory barriers makes the write side faster. Furthermore, + correctness is easy to check for in this case using the "pairing" + trick that is explained below: + + +---------------------------------------------------------------------= -+ + | thread 1 = | + +-----------------------------------+---------------------------------= -+ + | before | after = | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ + | :: | :: = | + | | = | + | (other writes) | = | + | atomic_mb_set(&a, x) | atomic_store_release(&a, x) = | + | atomic_mb_set(&b, y) | atomic_store_release(&b, y) = | + +-----------------------------------+---------------------------------= -+ + + +---------------------------------------------------------------------= -+ + | thread 2 = | + +-----------------------------------+---------------------------------= -+ + | before | after = | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ + | :: | :: = | + | | = | + | y =3D atomic_mb_read(&b) | y =3D atomic_load_acquire(&b= ) | + | x =3D atomic_mb_read(&a) | x =3D atomic_load_acquire(&a= ) | + | (other reads) | = | + +-----------------------------------+---------------------------------= -+ + + Note that the barrier between the stores in thread 1, and between + the loads in thread 2, has been optimized here to a write or a + read memory barrier respectively. On some architectures, notably + ARMv7, smp_mb_acquire and smp_mb_release are just as expensive as + smp_mb, but smp_rmb and/or smp_wmb are more efficient. + +- sometimes, a thread is accessing many variables that are otherwise + unrelated to each other (for example because, apart from the current + thread, exactly one other thread will read or write each of these + variables). In this case, it is possible to "hoist" the implicit + barriers provided by ``atomic_mb_read()`` and ``atomic_mb_set()`` outside + a loop. For example, the above definition ``atomic_mb_read()`` gives + the following transformation: + + +-----------------------------------+---------------------------------= -+ + | before | after = | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ + | :: | :: = | + | | = | + | n =3D 0; | n =3D 0; = | + | for (i =3D 0; i < 10; i++) | for (i =3D 0; i < 10; i++) = | + | n +=3D atomic_mb_read(&a[i]); | n +=3D atomic_read(&a[i]);= | + | | smp_mb_acquire(); = | + +-----------------------------------+---------------------------------= -+ + + Similarly, atomic_mb_set() can be transformed as follows: + + +-----------------------------------+---------------------------------= -+ + | before | after = | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ + | :: | :: = | + | | = | + | | smp_mb_release(); = | + | for (i =3D 0; i < 10; i++) | for (i =3D 0; i < 10; i++) = | + | atomic_mb_set(&a[i], false); | atomic_set(&a[i], false); = | + | | smp_mb(); = | + +-----------------------------------+---------------------------------= -+ + + + The other thread can still use ``atomic_mb_read()``/``atomic_mb_set()``. + +The two tricks can be combined. In this case, splitting a loop in +two lets you hoist the barriers out of the loops _and_ eliminate the +expensive ``smp_mb()``: + + +-----------------------------------+---------------------------------= -+ + | before | after = | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ + | :: | :: = | + | | = | + | | smp_mb_release(); = | + | for (i =3D 0; i < 10; i++) { | for (i =3D 0; i < 10; i++)= | + | atomic_mb_set(&a[i], false); | atomic_set(&a[i], false); = | + | atomic_mb_set(&b[i], false); | smb_wmb(); = | + | } | for (i =3D 0; i < 10; i++) = | + | | atomic_set(&a[i], false); = | + | | smp_mb(); = | + +-----------------------------------+---------------------------------= -+ + + +Memory barrier pairing +---------------------- + +A useful rule of thumb is that memory barriers should always, or almost +always, be paired with another barrier. In the case of QEMU, however, +note that the other barrier may actually be in a driver that runs in +the guest! + +For the purposes of pairing, ``smp_read_barrier_depends()`` and ``smp_rmb(= )`` +both count as read barriers. A read barrier shall pair with a write +barrier or a full barrier; a write barrier shall pair with a read +barrier or a full barrier. A full barrier can pair with anything. +For example: + + +--------------------+------------------------------+ + | thread 1 | thread 2 | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D+ + | :: | :: | + | | | + | a =3D 1; | | + | smp_wmb(); | | + | b =3D 2; | x =3D b; | + | | smp_rmb(); | + | | y =3D a; | + +--------------------+------------------------------+ + +Note that the "writing" thread is accessing the variables in the +opposite order as the "reading" thread. This is expected: stores +before the write barrier will normally match the loads after the +read barrier, and vice versa. The same is true for more than 2 +access and for data dependency barriers: + + +--------------------+------------------------------+ + | thread 1 | thread 2 | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D+ + | :: | :: | + | | | + | b[2] =3D 1; | | + | smp_wmb(); | | + | x->i =3D 2; | | + | smp_wmb(); | | + | a =3D x; | x =3D a; | + | | smp_read_barrier_depends(); | + | | y =3D x->i; | + | | smp_read_barrier_depends(); | + | | z =3D b[y]; | + +--------------------+------------------------------+ + +``smp_wmb()`` also pairs with ``atomic_mb_read()`` and ``smp_mb_acquire()`= `. +and ``smp_rmb()`` also pairs with ``atomic_mb_set()`` and ``smp_mb_release= ()``. + + +Comparison with Linux kernel memory barriers +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +Here is a list of differences between Linux kernel atomic operations +and memory barriers, and the equivalents in QEMU: + +- atomic operations in Linux are always on a 32-bit int type and + use a boxed atomic_t type; atomic operations in QEMU are polymorphic + and use normal C types. + +- Originally, atomic_read and atomic_set in Linux gave no guarantee + at all. Linux 4.1 updated them to implement volatile + semantics via ACCESS_ONCE (or the more recent READ/WRITE_ONCE). + + QEMU's atomic_read/set implement, if the compiler supports it, C11 + atomic relaxed semantics, and volatile semantics otherwise. + Both semantics prevent the compiler from doing certain transformations; + the difference is that atomic accesses are guaranteed to be atomic, + while volatile accesses aren't. Thus, in the volatile case we just cross + our fingers hoping that the compiler will generate atomic accesses, + since we assume the variables passed are machine-word sized and + properly aligned. + No barriers are implied by atomic_read/set in either Linux or QEMU. + +- atomic read-modify-write operations in Linux are of three kinds: + + =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D = =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + ``atomic_OP`` returns void + ``atomic_OP_return`` returns new value of the variable + ``atomic_fetch_OP`` returns the old value of the variable + ``atomic_cmpxchg`` returns the old value of the variable + =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D = =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + + In QEMU, the second kind does not exist. Currently Linux has + atomic_fetch_or only. QEMU provides and, or, inc, dec, add, sub. + +- different atomic read-modify-write operations in Linux imply + a different set of memory barriers; in QEMU, all of them enforce + sequential consistency, which means they imply full memory barriers + before and after the operation. + +- Linux does not have an equivalent of ``atomic_mb_set()``. In particular, + note that ``smp_store_mb()`` is a little weaker than ``atomic_mb_set()``. + ``atomic_mb_read()`` compiles to the same instructions as Linux's + ``smp_load_acquire()``, but this should be treated as an implementation + detail. + +Sources +=3D=3D=3D=3D=3D=3D=3D + +* Documentation/memory-barriers.txt from the Linux kernel + +* "The JSR-133 Cookbook for Compiler Writers", available at + http://g.oswego.edu/dl/jmm/cookbook.html diff --git a/docs/devel/atomics.txt b/docs/devel/atomics.txt deleted file mode 100644 index 67bdf82628..0000000000 --- a/docs/devel/atomics.txt +++ /dev/null @@ -1,403 +0,0 @@ -CPUs perform independent memory operations effectively in random order. -but this can be a problem for CPU-CPU interaction (including interactions -between QEMU and the guest). Multi-threaded programs use various tools -to instruct the compiler and the CPU to restrict the order to something -that is consistent with the expectations of the programmer. - -The most basic tool is locking. Mutexes, condition variables and -semaphores are used in QEMU, and should be the default approach to -synchronization. Anything else is considerably harder, but it's -also justified more often than one would like. The two tools that -are provided by qemu/atomic.h are memory barriers and atomic operations. - -Macros defined by qemu/atomic.h fall in three camps: - -- compiler barriers: barrier(); - -- weak atomic access and manual memory barriers: atomic_read(), - atomic_set(), smp_rmb(), smp_wmb(), smp_mb(), smp_mb_acquire(), - smp_mb_release(), smp_read_barrier_depends(); - -- sequentially consistent atomic access: everything else. - - -COMPILER MEMORY BARRIER -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - -barrier() prevents the compiler from moving the memory accesses either -side of it to the other side. The compiler barrier has no direct effect -on the CPU, which may then reorder things however it wishes. - -barrier() is mostly used within qemu/atomic.h itself. On some -architectures, CPU guarantees are strong enough that blocking compiler -optimizations already ensures the correct order of execution. In this -case, qemu/atomic.h will reduce stronger memory barriers to simple -compiler barriers. - -Still, barrier() can be useful when writing code that can be interrupted -by signal handlers. - - -SEQUENTIALLY CONSISTENT ATOMIC ACCESS -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - -Most of the operations in the qemu/atomic.h header ensure *sequential -consistency*, where "the result of any execution is the same as if the -operations of all the processors were executed in some sequential order, -and the operations of each individual processor appear in this sequence -in the order specified by its program". - -qemu/atomic.h provides the following set of atomic read-modify-write -operations: - - void atomic_inc(ptr) - void atomic_dec(ptr) - void atomic_add(ptr, val) - void atomic_sub(ptr, val) - void atomic_and(ptr, val) - void atomic_or(ptr, val) - - typeof(*ptr) atomic_fetch_inc(ptr) - typeof(*ptr) atomic_fetch_dec(ptr) - typeof(*ptr) atomic_fetch_add(ptr, val) - typeof(*ptr) atomic_fetch_sub(ptr, val) - typeof(*ptr) atomic_fetch_and(ptr, val) - typeof(*ptr) atomic_fetch_or(ptr, val) - typeof(*ptr) atomic_fetch_xor(ptr, val) - typeof(*ptr) atomic_fetch_inc_nonzero(ptr) - typeof(*ptr) atomic_xchg(ptr, val) - typeof(*ptr) atomic_cmpxchg(ptr, old, new) - -all of which return the old value of *ptr. These operations are -polymorphic; they operate on any type that is as wide as a pointer. - -Similar operations return the new value of *ptr: - - typeof(*ptr) atomic_inc_fetch(ptr) - typeof(*ptr) atomic_dec_fetch(ptr) - typeof(*ptr) atomic_add_fetch(ptr, val) - typeof(*ptr) atomic_sub_fetch(ptr, val) - typeof(*ptr) atomic_and_fetch(ptr, val) - typeof(*ptr) atomic_or_fetch(ptr, val) - typeof(*ptr) atomic_xor_fetch(ptr, val) - -Sequentially consistent loads and stores can be done using: - - atomic_fetch_add(ptr, 0) for loads - atomic_xchg(ptr, val) for stores - -However, they are quite expensive on some platforms, notably POWER and -Arm. Therefore, qemu/atomic.h provides two primitives with slightly -weaker constraints: - - typeof(*ptr) atomic_mb_read(ptr) - void atomic_mb_set(ptr, val) - -The semantics of these primitives map to Java volatile variables, -and are strongly related to memory barriers as used in the Linux -kernel (see below). - -As long as you use atomic_mb_read and atomic_mb_set, accesses cannot -be reordered with each other, and it is also not possible to reorder -"normal" accesses around them. - -However, and this is the important difference between -atomic_mb_read/atomic_mb_set and sequential consistency, it is important -for both threads to access the same volatile variable. It is not the -case that everything visible to thread A when it writes volatile field f -becomes visible to thread B after it reads volatile field g. The store -and load have to "match" (i.e., be performed on the same volatile -field) to achieve the right semantics. - - -These operations operate on any type that is as wide as an int or smaller. - - -WEAK ATOMIC ACCESS AND MANUAL MEMORY BARRIERS -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - -Compared to sequentially consistent atomic access, programming with -weaker consistency models can be considerably more complicated. -In general, if the algorithm you are writing includes both writes -and reads on the same side, it is generally simpler to use sequentially -consistent primitives. - -When using this model, variables are accessed with: - -- atomic_read() and atomic_set(); these prevent the compiler from - optimizing accesses out of existence and creating unsolicited - accesses, but do not otherwise impose any ordering on loads and - stores: both the compiler and the processor are free to reorder - them. - -- atomic_load_acquire(), which guarantees the LOAD to appear to - happen, with respect to the other components of the system, - before all the LOAD or STORE operations specified afterwards. - Operations coming before atomic_load_acquire() can still be - reordered after it. - -- atomic_store_release(), which guarantees the STORE to appear to - happen, with respect to the other components of the system, - after all the LOAD or STORE operations specified afterwards. - Operations coming after atomic_store_release() can still be - reordered after it. - -Restrictions to the ordering of accesses can also be specified -using the memory barrier macros: smp_rmb(), smp_wmb(), smp_mb(), -smp_mb_acquire(), smp_mb_release(), smp_read_barrier_depends(). - -Memory barriers control the order of references to shared memory. -They come in six kinds: - -- smp_rmb() guarantees that all the LOAD operations specified before - the barrier will appear to happen before all the LOAD operations - specified after the barrier with respect to the other components of - the system. - - In other words, smp_rmb() puts a partial ordering on loads, but is not - required to have any effect on stores. - -- smp_wmb() guarantees that all the STORE operations specified before - the barrier will appear to happen before all the STORE operations - specified after the barrier with respect to the other components of - the system. - - In other words, smp_wmb() puts a partial ordering on stores, but is not - required to have any effect on loads. - -- smp_mb_acquire() guarantees that all the LOAD operations specified before - the barrier will appear to happen before all the LOAD or STORE operations - specified after the barrier with respect to the other components of - the system. - -- smp_mb_release() guarantees that all the STORE operations specified *aft= er* - the barrier will appear to happen after all the LOAD or STORE operations - specified *before* the barrier with respect to the other components of - the system. - -- smp_mb() guarantees that all the LOAD and STORE operations specified - before the barrier will appear to happen before all the LOAD and - STORE operations specified after the barrier with respect to the other - components of the system. - - smp_mb() puts a partial ordering on both loads and stores. It is - stronger than both a read and a write memory barrier; it implies both - smp_mb_acquire() and smp_mb_release(), but it also prevents STOREs - coming before the barrier from overtaking LOADs coming after the - barrier and vice versa. - -- smp_read_barrier_depends() is a weaker kind of read barrier. On - most processors, whenever two loads are performed such that the - second depends on the result of the first (e.g., the first load - retrieves the address to which the second load will be directed), - the processor will guarantee that the first LOAD will appear to happen - before the second with respect to the other components of the system. - However, this is not always true---for example, it was not true on - Alpha processors. Whenever this kind of access happens to shared - memory (that is not protected by a lock), a read barrier is needed, - and smp_read_barrier_depends() can be used instead of smp_rmb(). - - Note that the first load really has to have a _data_ dependency and not - a control dependency. If the address for the second load is dependent - on the first load, but the dependency is through a conditional rather - than actually loading the address itself, then it's a _control_ - dependency and a full read barrier or better is required. - - -This is the set of barriers that is required *between* two atomic_read() -and atomic_set() operations to achieve sequential consistency: - - | 2nd operation | - |-----------------------------------------------| - 1st operation | (after last) | atomic_read | atomic_set | - ---------------+----------------+-------------+----------------| - (before first) | | none | smp_mb_release | - ---------------+----------------+-------------+----------------| - atomic_read | smp_mb_acquire | smp_rmb | ** | - ---------------+----------------+-------------+----------------| - atomic_set | none | smp_mb()*** | smp_wmb() | - ---------------+----------------+-------------+----------------| - - * Or smp_read_barrier_depends(). - - ** This requires a load-store barrier. This is achieved by - either smp_mb_acquire() or smp_mb_release(). - - *** This requires a store-load barrier. On most machines, the only - way to achieve this is a full barrier. - - -You can see that the two possible definitions of atomic_mb_read() -and atomic_mb_set() are the following: - - 1) atomic_mb_read(p) =3D atomic_read(p); smp_mb_acquire() - atomic_mb_set(p, v) =3D smp_mb_release(); atomic_set(p, v); smp_mb() - - 2) atomic_mb_read(p) =3D smp_mb() atomic_read(p); smp_mb_acquire() - atomic_mb_set(p, v) =3D smp_mb_release(); atomic_set(p, v); - -Usually the former is used, because smp_mb() is expensive and a program -normally has more reads than writes. Therefore it makes more sense to -make atomic_mb_set() the more expensive operation. - -There are two common cases in which atomic_mb_read and atomic_mb_set -generate too many memory barriers, and thus it can be useful to manually -place barriers, or use atomic_load_acquire/atomic_store_release instead: - -- when a data structure has one thread that is always a writer - and one thread that is always a reader, manual placement of - memory barriers makes the write side faster. Furthermore, - correctness is easy to check for in this case using the "pairing" - trick that is explained below: - - thread 1 thread 1 - ------------------------- ------------------------ - (other writes) - atomic_mb_set(&a, x) atomic_store_release(&a, x) - atomic_mb_set(&b, y) atomic_store_release(&b, y) - - =3D> - thread 2 thread 2 - ------------------------- ------------------------ - y =3D atomic_mb_read(&b) y =3D atomic_load_acquire(&= b) - x =3D atomic_mb_read(&a) x =3D atomic_load_acquire(&= a) - (other reads) - - Note that the barrier between the stores in thread 1, and between - the loads in thread 2, has been optimized here to a write or a - read memory barrier respectively. On some architectures, notably - ARMv7, smp_mb_acquire and smp_mb_release are just as expensive as - smp_mb, but smp_rmb and/or smp_wmb are more efficient. - -- sometimes, a thread is accessing many variables that are otherwise - unrelated to each other (for example because, apart from the current - thread, exactly one other thread will read or write each of these - variables). In this case, it is possible to "hoist" the implicit - barriers provided by atomic_mb_read() and atomic_mb_set() outside - a loop. For example, the above definition atomic_mb_read() gives - the following transformation: - - n =3D 0; n =3D 0; - for (i =3D 0; i < 10; i++) =3D> for (i =3D 0; i < 10; i++) - n +=3D atomic_mb_read(&a[i]); n +=3D atomic_read(&a[i]); - smp_mb_acquire(); - - Similarly, atomic_mb_set() can be transformed as follows: - - smp_mb_release(); - for (i =3D 0; i < 10; i++) =3D> for (i =3D 0; i < 10; i++) - atomic_mb_set(&a[i], false); atomic_set(&a[i], false); - smp_mb(); - - - The other thread can still use atomic_mb_read()/atomic_mb_set(). - -The two tricks can be combined. In this case, splitting a loop in -two lets you hoist the barriers out of the loops _and_ eliminate the -expensive smp_mb(): - - smp_mb_release(); - for (i =3D 0; i < 10; i++) { =3D> for (i =3D 0; i < 10; i++) - atomic_mb_set(&a[i], false); atomic_set(&a[i], false); - atomic_mb_set(&b[i], false); smb_wmb(); - } for (i =3D 0; i < 10; i++) - atomic_set(&a[i], false); - smp_mb(); - - -Memory barrier pairing ----------------------- - -A useful rule of thumb is that memory barriers should always, or almost -always, be paired with another barrier. In the case of QEMU, however, -note that the other barrier may actually be in a driver that runs in -the guest! - -For the purposes of pairing, smp_read_barrier_depends() and smp_rmb() -both count as read barriers. A read barrier shall pair with a write -barrier or a full barrier; a write barrier shall pair with a read -barrier or a full barrier. A full barrier can pair with anything. -For example: - - thread 1 thread 2 - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - a =3D 1; - smp_wmb(); - b =3D 2; x =3D b; - smp_rmb(); - y =3D a; - -Note that the "writing" thread is accessing the variables in the -opposite order as the "reading" thread. This is expected: stores -before the write barrier will normally match the loads after the -read barrier, and vice versa. The same is true for more than 2 -access and for data dependency barriers: - - thread 1 thread 2 - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - b[2] =3D 1; - smp_wmb(); - x->i =3D 2; - smp_wmb(); - a =3D x; x =3D a; - smp_read_barrier_depends(); - y =3D x->i; - smp_read_barrier_depends(); - z =3D b[y]; - -smp_wmb() also pairs with atomic_mb_read() and smp_mb_acquire(). -and smp_rmb() also pairs with atomic_mb_set() and smp_mb_release(). - - -COMPARISON WITH LINUX KERNEL MEMORY BARRIERS -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - -Here is a list of differences between Linux kernel atomic operations -and memory barriers, and the equivalents in QEMU: - -- atomic operations in Linux are always on a 32-bit int type and - use a boxed atomic_t type; atomic operations in QEMU are polymorphic - and use normal C types. - -- Originally, atomic_read and atomic_set in Linux gave no guarantee - at all. Linux 4.1 updated them to implement volatile - semantics via ACCESS_ONCE (or the more recent READ/WRITE_ONCE). - - QEMU's atomic_read/set implement, if the compiler supports it, C11 - atomic relaxed semantics, and volatile semantics otherwise. - Both semantics prevent the compiler from doing certain transformations; - the difference is that atomic accesses are guaranteed to be atomic, - while volatile accesses aren't. Thus, in the volatile case we just cross - our fingers hoping that the compiler will generate atomic accesses, - since we assume the variables passed are machine-word sized and - properly aligned. - No barriers are implied by atomic_read/set in either Linux or QEMU. - -- atomic read-modify-write operations in Linux are of three kinds: - - atomic_OP returns void - atomic_OP_return returns new value of the variable - atomic_fetch_OP returns the old value of the variable - atomic_cmpxchg returns the old value of the variable - - In QEMU, the second kind does not exist. Currently Linux has - atomic_fetch_or only. QEMU provides and, or, inc, dec, add, sub. - -- different atomic read-modify-write operations in Linux imply - a different set of memory barriers; in QEMU, all of them enforce - sequential consistency, which means they imply full memory barriers - before and after the operation. - -- Linux does not have an equivalent of atomic_mb_set(). In particular, - note that smp_store_mb() is a little weaker than atomic_mb_set(). - atomic_mb_read() compiles to the same instructions as Linux's - smp_load_acquire(), but this should be treated as an implementation - detail. - -SOURCES -=3D=3D=3D=3D=3D=3D=3D - -* Documentation/memory-barriers.txt from the Linux kernel - -* "The JSR-133 Cookbook for Compiler Writers", available at - http://g.oswego.edu/dl/jmm/cookbook.html diff --git a/docs/devel/index.rst b/docs/devel/index.rst index b734ba4655..a9e1200dff 100644 --- a/docs/devel/index.rst +++ b/docs/devel/index.rst @@ -17,6 +17,7 @@ Contents: loads-stores memory migration + atomics stable-process testing decodetree --=20 2.18.2 From nobody Sat May 18 22:31:06 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1586200498; cv=none; d=zohomail.com; s=zohoarc; b=KkpVo3/f9Ym4U48ujtynbo9EGizgMAVTiFUbzLhGK5v35CoVzc0LaPVKx0Fvc3g4LDR8/X2QmXN2wm2RIpsJVvs4U1zKXU1TuTB94SpW8gj+nLgIpHKNhItZzu+5nCjAn2bZP5tt8jX56yBuBVAlcWvbOyo1e9YTHu/Y21WyJMU= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1586200498; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:Message-ID:References:Sender:Subject:To; bh=POVW9ePUf/Ib4Kc+laUKo0y2kHQOilu154c/mjCyHmc=; b=GUQ3/pjoqSrwRJe5v0pk4DsgbVG8m8ea3aujw6psm8tmk6ufaALtgAOuf6xICqGIKU0NBHWbujpv62qCISqE72MngbaHHLeFDPvZPrziPcXTus7d6VAC76/TC/hU087od51V6t6KpY+c50XzfXISG81qM1OuxtS3Yrd1WJzpsgQ= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1586200498933369.70426686288477; Mon, 6 Apr 2020 12:14:58 -0700 (PDT) Received: from localhost ([::1]:37342 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jLXCz-0002ct-J9 for importer@patchew.org; Mon, 06 Apr 2020 15:14:57 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:52434) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jLXBe-00014P-DF for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:36 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1jLXBc-0006j9-0a for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:34 -0400 Received: from us-smtp-delivery-1.mimecast.com ([205.139.110.120]:38937 helo=us-smtp-1.mimecast.com) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1jLXBb-0006ir-RB for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:31 -0400 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-208-m2quIq1yM9255sn-sYspUg-1; Mon, 06 Apr 2020 15:13:27 -0400 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 0B5B71005513; Mon, 6 Apr 2020 19:13:26 +0000 (UTC) Received: from virtlab701.virt.lab.eng.bos.redhat.com (virtlab701.virt.lab.eng.bos.redhat.com [10.19.152.228]) by smtp.corp.redhat.com (Postfix) with ESMTP id 8A5C162697; Mon, 6 Apr 2020 19:13:25 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1586200411; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=POVW9ePUf/Ib4Kc+laUKo0y2kHQOilu154c/mjCyHmc=; b=d76FctLnEpJo7wNOj15yIQC9WwFlxDsA5N6FOxwrDaq43MEmDlvUyuSuhi4JguIOc3ojoC sLWS/nNq19TnhfzCgiZXXAUsemCbGKlVasFoZFpjYEdeV0r9ZVUiiNFVsG+PBKJVZwtydV 9nR4Zzwe2bZ54B8UgbADRw5euguBQ54= X-MC-Unique: m2quIq1yM9255sn-sYspUg-1 From: Paolo Bonzini To: qemu-devel@nongnu.org Subject: [PATCH 2/4] atomics: update documentation for C11 Date: Mon, 6 Apr 2020 15:13:18 -0400 Message-Id: <20200406191320.13371-3-pbonzini@redhat.com> In-Reply-To: <20200406191320.13371-1-pbonzini@redhat.com> References: <20200406191320.13371-1-pbonzini@redhat.com> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.15 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 205.139.110.120 X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Ying Fang , stefanha@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Deprecate atomic_mb_read and atomic_mb_set; it is not really possible to use them correctly because they do not interoperate with sequentially-consi= stent RMW operations. Signed-off-by: Paolo Bonzini Reviewed-by: Stefan Hajnoczi --- docs/devel/atomics.rst | 290 ++++++++++++++++------------------------- 1 file changed, 114 insertions(+), 176 deletions(-) diff --git a/docs/devel/atomics.rst b/docs/devel/atomics.rst index 00f3f7d3ed..e92752a64d 100644 --- a/docs/devel/atomics.rst +++ b/docs/devel/atomics.rst @@ -11,10 +11,15 @@ that is consistent with the expectations of the program= mer. The most basic tool is locking. Mutexes, condition variables and semaphores are used in QEMU, and should be the default approach to synchronization. Anything else is considerably harder, but it's -also justified more often than one would like. The two tools that -are provided by ``qemu/atomic.h`` are memory barriers and atomic operation= s. +also justified more often than one would like; +the most performance-critical parts of QEMU in particular require +a very low level approach to concurrency, involving memory barriers +and atomic operations. The semantics of concurrent memory accesses are go= verned +by the C11 memory model. =20 -Macros defined by ``qemu/atomic.h`` fall in three camps: +QEMU provides a header, ``qemu/atomic.h``, which wraps C11 atomics to +provide better portability and a less verbose syntax. ``qemu/atomic.h`` +provides macros that fall in three camps: =20 - compiler barriers: ``barrier()``; =20 @@ -24,6 +29,14 @@ Macros defined by ``qemu/atomic.h`` fall in three camps: =20 - sequentially consistent atomic access: everything else. =20 +In general, use of ``qemu/atomic.h`` should be wrapped with more easily +used data structures (e.g. the lock-free singly-liked list operations +``QSLIST_INSERT_HEAD_ATOMIC`` and ``QSLIST_MOVE_ATOMIC``) or synchronizati= on +primitives (such as RCU, ``QemuEvent`` or ``QemuLockCnt``). Bare use of +atomic operations and memory barriers should be limited to inter-thread +checking of flags and documented thoroughly. + + =20 Compiler memory barrier =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D @@ -85,36 +98,14 @@ Similar operations return the new value of ``*ptr``:: typeof(*ptr) atomic_or_fetch(ptr, val) typeof(*ptr) atomic_xor_fetch(ptr, val) =20 -Sequentially consistent loads and stores can be done using:: - - atomic_fetch_add(ptr, 0) for loads - atomic_xchg(ptr, val) for stores +These operations operate on any type that is as wide as an int or smaller. =20 -However, they are quite expensive on some platforms, notably POWER and -Arm. Therefore, qemu/atomic.h provides two primitives with slightly -weaker constraints:: +``qemu/atomic.h`` also provides sequentially consistent loads and stores c= an:: =20 typeof(*ptr) atomic_mb_read(ptr) void atomic_mb_set(ptr, val) =20 -The semantics of these primitives map to Java volatile variables, -and are strongly related to memory barriers as used in the Linux -kernel (see below). - -As long as you use atomic_mb_read and atomic_mb_set, accesses cannot -be reordered with each other, and it is also not possible to reorder -"normal" accesses around them. - -However, and this is the important difference between -atomic_mb_read/atomic_mb_set and sequential consistency, it is important -for both threads to access the same volatile variable. It is not the -case that everything visible to thread A when it writes volatile field f -becomes visible to thread B after it reads volatile field g. The store -and load have to "match" (i.e., be performed on the same volatile -field) to achieve the right semantics. - - -These operations operate on any type that is as wide as an int or smaller. +which however are deprecated. =20 =20 Weak atomic access and manual memory barriers @@ -208,135 +199,62 @@ They come in six kinds: dependency and a full read barrier or better is required. =20 =20 -This is the set of barriers that is required *between* two ``atomic_read()= `` -and ``atomic_set()`` operations to achieve sequential consistency: - - +----------------+-----------------------------------------------------= --+ - | | 2nd operation = | - | +------------------+-----------------+----------------= --+ - | 1st operation | (after last) | atomic_read | atomic_set = | - +----------------+------------------+-----------------+----------------= --+ - | (before first) | .. | none | smp_mb_release(= ) | - +----------------+------------------+-----------------+----------------= --+ - | atomic_read | smp_mb_acquire() | smp_rmb() [1]_ | [2]_ = | - +----------------+------------------+-----------------+----------------= --+ - | atomic_set | none | smp_mb() [3]_ | smp_wmb() = | - +----------------+------------------+-----------------+----------------= --+ - - .. [1] Or smp_read_barrier_depends(). - - .. [2] This requires a load-store barrier. This is achieved by - either smp_mb_acquire() or smp_mb_release(). - - .. [3] This requires a store-load barrier. On most machines, the only - way to achieve this is a full barrier. - - -You can see that the two possible definitions of ``atomic_mb_read()`` -and ``atomic_mb_set()`` are the following: - - 1) | atomic_mb_read(p) =3D atomic_read(p); smp_mb_acquire() - | atomic_mb_set(p, v) =3D smp_mb_release(); atomic_set(p, v); smp_mb() - - 2) | atomic_mb_read(p) =3D smp_mb() atomic_read(p); smp_mb_acquire() - | atomic_mb_set(p, v) =3D smp_mb_release(); atomic_set(p, v); - -Usually the former is used, because ``smp_mb()`` is expensive and a program -normally has more reads than writes. Therefore it makes more sense to -make ``atomic_mb_set()`` the more expensive operation. - -There are two common cases in which atomic_mb_read and atomic_mb_set -generate too many memory barriers, and thus it can be useful to manually -place barriers, or use atomic_load_acquire/atomic_store_release instead: - -- when a data structure has one thread that is always a writer - and one thread that is always a reader, manual placement of - memory barriers makes the write side faster. Furthermore, - correctness is easy to check for in this case using the "pairing" - trick that is explained below: - - +---------------------------------------------------------------------= -+ - | thread 1 = | - +-----------------------------------+---------------------------------= -+ - | before | after = | - +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ - | :: | :: = | - | | = | - | (other writes) | = | - | atomic_mb_set(&a, x) | atomic_store_release(&a, x) = | - | atomic_mb_set(&b, y) | atomic_store_release(&b, y) = | - +-----------------------------------+---------------------------------= -+ - - +---------------------------------------------------------------------= -+ - | thread 2 = | - +-----------------------------------+---------------------------------= -+ - | before | after = | - +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ - | :: | :: = | - | | = | - | y =3D atomic_mb_read(&b) | y =3D atomic_load_acquire(&b= ) | - | x =3D atomic_mb_read(&a) | x =3D atomic_load_acquire(&a= ) | - | (other reads) | = | - +-----------------------------------+---------------------------------= -+ - - Note that the barrier between the stores in thread 1, and between - the loads in thread 2, has been optimized here to a write or a - read memory barrier respectively. On some architectures, notably - ARMv7, smp_mb_acquire and smp_mb_release are just as expensive as - smp_mb, but smp_rmb and/or smp_wmb are more efficient. - -- sometimes, a thread is accessing many variables that are otherwise - unrelated to each other (for example because, apart from the current - thread, exactly one other thread will read or write each of these - variables). In this case, it is possible to "hoist" the implicit - barriers provided by ``atomic_mb_read()`` and ``atomic_mb_set()`` outside - a loop. For example, the above definition ``atomic_mb_read()`` gives - the following transformation: - - +-----------------------------------+---------------------------------= -+ - | before | after = | - +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ - | :: | :: = | - | | = | - | n =3D 0; | n =3D 0; = | - | for (i =3D 0; i < 10; i++) | for (i =3D 0; i < 10; i++) = | - | n +=3D atomic_mb_read(&a[i]); | n +=3D atomic_read(&a[i]);= | - | | smp_mb_acquire(); = | - +-----------------------------------+---------------------------------= -+ - - Similarly, atomic_mb_set() can be transformed as follows: - - +-----------------------------------+---------------------------------= -+ - | before | after = | - +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ - | :: | :: = | - | | = | - | | smp_mb_release(); = | - | for (i =3D 0; i < 10; i++) | for (i =3D 0; i < 10; i++) = | - | atomic_mb_set(&a[i], false); | atomic_set(&a[i], false); = | - | | smp_mb(); = | - +-----------------------------------+---------------------------------= -+ - - - The other thread can still use ``atomic_mb_read()``/``atomic_mb_set()``. +Memory barriers and ``atomic_load_acquire``/``atomic_store_release`` are +mostly used when a data structure has one thread that is always a writer +and one thread that is always a reader: + + +----------------------------------+----------------------------------+ + | thread 1 | thread 2 | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ + | :: | :: | + | | | + | atomic_store_release(&a, x) | y =3D atomic_load_acquire(&b) = | + | atomic_store_release(&b, y) | x =3D atomic_load_acquire(&a) = | + +----------------------------------+----------------------------------+ + +In this case, correctness is easy to check for in this case using the +"pairing" trick that is explained below. + +Sometimes, a thread is accessing many variables that are otherwise +unrelated to each other (for example because, apart from the current +thread, exactly one other thread will read or write each of these +variables). In this case, it is possible to "hoist" the barriers +outside a loop. For example: + + +------------------------------------------+--------------------------= --------+ + | before | after = | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D+ + | :: | :: = | + | | = | + | n =3D 0; | n =3D 0; = | + | for (i =3D 0; i < 10; i++) | for (i =3D 0; i < 10;= i++) | + | n +=3D atomic_load_acquire(&a[i]); | n +=3D atomic_read(= &a[i]); | + | | smp_mb_acquire(); = | + +------------------------------------------+--------------------------= --------+ + | :: | :: = | + | | = | + | | smp_mb_release(); = | + | for (i =3D 0; i < 10; i++) | for (i =3D 0; i < 10;= i++) | + | atomic_store_release(&a[i], false); | atomic_set(&a[i], fal= se); | + +------------------------------------------+--------------------------= --------+ =20 The two tricks can be combined. In this case, splitting a loop in -two lets you hoist the barriers out of the loops _and_ eliminate the -expensive ``smp_mb()``: - - +-----------------------------------+---------------------------------= -+ - | before | after = | - +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ - | :: | :: = | - | | = | - | | smp_mb_release(); = | - | for (i =3D 0; i < 10; i++) { | for (i =3D 0; i < 10; i++)= | - | atomic_mb_set(&a[i], false); | atomic_set(&a[i], false); = | - | atomic_mb_set(&b[i], false); | smb_wmb(); = | - | } | for (i =3D 0; i < 10; i++) = | - | | atomic_set(&a[i], false); = | - | | smp_mb(); = | - +-----------------------------------+---------------------------------= -+ +two lets you hoist the barriers out of the loops, and replace a +``smp_mb_release()`` with a (possibly cheaper, and clearer as well) +``smp_wmb()``: + + +------------------------------------------+--------------------------= --------+ + | before | after = | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D+ + | :: | :: = | + | | = | + | | smp_mb_release(); = | + | for (i =3D 0; i < 10; i++) { | for (i =3D 0; i < 1= 0; i++) | + | atomic_store_release(&a[i], false); | atomic_set(&a[i], f= alse); | + | atomic_store_release(&b[i], false); | smb_wmb(); = | + | } | for (i =3D 0; i < 10;= i++) | + | | atomic_set(&b[i], f= alse); | + +------------------------------------------+--------------------------= --------+ =20 =20 Memory barrier pairing @@ -347,11 +265,13 @@ always, be paired with another barrier. In the case = of QEMU, however, note that the other barrier may actually be in a driver that runs in the guest! =20 -For the purposes of pairing, ``smp_read_barrier_depends()`` and ``smp_rmb(= )`` -both count as read barriers. A read barrier shall pair with a write -barrier or a full barrier; a write barrier shall pair with a read -barrier or a full barrier. A full barrier can pair with anything. -For example: +For the purposes of pairing, ``smp_read_barrier_depends()``, ``smp_rmb()`` +and ``smp_mb_acquire()`` all count as read barriers; ``smp_wmb()` and +``smp_mb_release()`` both count as write barriers. + +A read barrier shall pair with a write barrier or a full barrier; +a write barrier shall pair with a read barrier or a full barrier. +A full barrier can pair with anything. For example: =20 +--------------------+------------------------------+ | thread 1 | thread 2 | @@ -387,9 +307,6 @@ access and for data dependency barriers: | | z =3D b[y]; | +--------------------+------------------------------+ =20 -``smp_wmb()`` also pairs with ``atomic_mb_read()`` and ``smp_mb_acquire()`= `. -and ``smp_rmb()`` also pairs with ``atomic_mb_set()`` and ``smp_mb_release= ()``. - =20 Comparison with Linux kernel memory barriers =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D @@ -424,24 +341,45 @@ and memory barriers, and the equivalents in QEMU: ``atomic_cmpxchg`` returns the old value of the variable =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D = =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =20 - In QEMU, the second kind does not exist. Currently Linux has - atomic_fetch_or only. QEMU provides and, or, inc, dec, add, sub. + In QEMU, the second kind does not exist. =20 - different atomic read-modify-write operations in Linux imply a different set of memory barriers; in QEMU, all of them enforce - sequential consistency, which means they imply full memory barriers - before and after the operation. - -- Linux does not have an equivalent of ``atomic_mb_set()``. In particular, - note that ``smp_store_mb()`` is a little weaker than ``atomic_mb_set()``. - ``atomic_mb_read()`` compiles to the same instructions as Linux's - ``smp_load_acquire()``, but this should be treated as an implementation - detail. + sequential consistency. + +- in QEMU, ``atomic_read()`` and ``atomic_set()`` do not participate in + the total ordering enforced by sequentially-consistent operations. + This is because QEMU uses the C11 memory model. The following example + is correct in Linux but not in QEMU: + + +----------------------------------+--------------------------------+ + | Linux (correct) | QEMU (incorrect) | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ + | :: | :: | + | | | + | a =3D atomic_fetch_add(&x, 2); | a =3D atomic_fetch_add(&x, = 2); | + | b =3D READ_ONCE(&y); | b =3D atomic_read(&y); = | + +----------------------------------+--------------------------------+ + + because the read of ``y`` can be moved (by either the processor or the + compiler) before the write of ``x``. + + Fixing this requires an ``smp_mb()`` memory barrier between the write + of ``x`` and the read of ``y``. In the common case where only one thread + writes ``x``, it is also possible to write it like this: + + +--------------------------------+ + | QEMU (correct) | + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D+ + | :: | + | | + | a =3D atomic_read(&x); | + | atomic_set(&x, a + 2); | + | smp_mb(); | + | b =3D atomic_read(&y); | + +--------------------------------+ =20 Sources =3D=3D=3D=3D=3D=3D=3D =20 * Documentation/memory-barriers.txt from the Linux kernel - -* "The JSR-133 Cookbook for Compiler Writers", available at - http://g.oswego.edu/dl/jmm/cookbook.html --=20 2.18.2 From nobody Sat May 18 22:31:06 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1586200568; cv=none; d=zohomail.com; s=zohoarc; b=O/qrzvUI2AC9dYdSnCd6Q2OsrY3A7xy3+EHAmsGhkqRdLl5JADHO8zy5rL6/arfeXI7gWM9E8qYv1Mjs6s6dVS3YeSjXfGpiCDAz5dAxhirKqSu0WEn7LddQOTPVpF6xTYKkeOo1OgS9UPmdjk8DxYG3ECb/Ru+WZuLRqI2H4jY= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1586200568; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:Message-ID:References:Sender:Subject:To; bh=XRLWXRytzTGVO0r/GudLCTGjNoCUKmXsKyZKPig2BiY=; b=GXNPX++h01pwPbxez14qCw901OFIkYQaRIWwRzuPXm9ZRB3/due/FycJQCtVNiCmJym01ZNb5ftotkGL4MwjtFSyE3yEbbh8qil4amrYJOM1+PTxx8Ms5erYfWbIl0otIYpuan/YrgCXsawTHssw+cvRiOQiYEtkxH7a0qwTrIE= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1586200568627633.3267738956113; Mon, 6 Apr 2020 12:16:08 -0700 (PDT) Received: from localhost ([::1]:37372 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jLXE7-0004Ui-DR for importer@patchew.org; Mon, 06 Apr 2020 15:16:07 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:52408) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jLXBa-00011B-Kv for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:31 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1jLXBZ-0006hP-P7 for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:30 -0400 Received: from us-smtp-1.mimecast.com ([205.139.110.61]:23475 helo=us-smtp-delivery-1.mimecast.com) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1jLXBZ-0006gu-Lo for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:29 -0400 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-274-zpGeA6c7P4-ajS29Or8K3g-1; Mon, 06 Apr 2020 15:13:27 -0400 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id A619413F7; Mon, 6 Apr 2020 19:13:26 +0000 (UTC) Received: from virtlab701.virt.lab.eng.bos.redhat.com (virtlab701.virt.lab.eng.bos.redhat.com [10.19.152.228]) by smtp.corp.redhat.com (Postfix) with ESMTP id 308F062697; Mon, 6 Apr 2020 19:13:26 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1586200409; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=XRLWXRytzTGVO0r/GudLCTGjNoCUKmXsKyZKPig2BiY=; b=eY4NSipOnXEyfH1wuHwFxQrFmtd6nDoX9RSdPb0QfpnwjhxscXTIzmESh4PxMfqVboBeVg 2gUbjroOyKhzWM93mJq7ZpS15eOKmo5qm+DoEWuv3g5Mw/cPcXktsplII0MzhOrbWxRv45 CStsaVnwML5CIAubReRTVNVgaPk8jqQ= X-MC-Unique: zpGeA6c7P4-ajS29Or8K3g-1 From: Paolo Bonzini To: qemu-devel@nongnu.org Subject: [PATCH 3/4] rcu: do not mention atomic_mb_read/set in documentation Date: Mon, 6 Apr 2020 15:13:19 -0400 Message-Id: <20200406191320.13371-4-pbonzini@redhat.com> In-Reply-To: <20200406191320.13371-1-pbonzini@redhat.com> References: <20200406191320.13371-1-pbonzini@redhat.com> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.15 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 205.139.110.61 X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Ying Fang , stefanha@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Signed-off-by: Paolo Bonzini Reviewed-by: Stefan Hajnoczi --- docs/devel/rcu.txt | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/docs/devel/rcu.txt b/docs/devel/rcu.txt index d83fed2f79..0ce15ba198 100644 --- a/docs/devel/rcu.txt +++ b/docs/devel/rcu.txt @@ -132,7 +132,7 @@ The core RCU API is small: =20 typeof(*p) atomic_rcu_read(p); =20 - atomic_rcu_read() is similar to atomic_mb_read(), but it makes + atomic_rcu_read() is similar to atomic_load_acquire(), but it makes some assumptions on the code that calls it. This allows a more optimized implementation. =20 @@ -154,7 +154,7 @@ The core RCU API is small: =20 void atomic_rcu_set(p, typeof(*p) v); =20 - atomic_rcu_set() is also similar to atomic_mb_set(), and it also + atomic_rcu_set() is similar to atomic_store_release(), though it a= lso makes assumptions on the code that calls it in order to allow a mo= re optimized implementation. =20 --=20 2.18.2 From nobody Sat May 18 22:31:06 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1586200656; cv=none; d=zohomail.com; s=zohoarc; b=l4HcOPUEzoYm8qvw48IEOm3zxDvJx+pHTbUNleGS/xgQNpHyQePrE8j1wvjhvBPG3ZfIhm1afgQMER7nbUSqrNg4PhW4ARFNS4f+VbXyoSwWv4q3/nugxrkF2trw0g3B6IaoOd8zTfDbovh8hzXFi+2Tl/jCt2aegddYl8K7/vM= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1586200656; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:Message-ID:References:Sender:Subject:To; bh=7Ua1uVlJeZsGjldXbjT2beLLFwjIig2Wrf3VsNlyDJ0=; b=ZVW10M3pU2LA/JYzyqqYhz4AkoQZLHxbnBDzDcdqRp9z2TecVSwyAqdjfRLNaIS6gTESkxrAZxexLXS9Sq9NIPA/3/ZAYJg3Psd75qaZz9dbMzjdzJV2ZEJeT0RMtKxeG40ZIsuq1gIUK77mZjo8aFpnmTq1OeF+0/UBOFGdPic= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 15862006566311004.3454861320128; Mon, 6 Apr 2020 12:17:36 -0700 (PDT) Received: from localhost ([::1]:37378 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jLXFX-0005hn-BO for importer@patchew.org; Mon, 06 Apr 2020 15:17:35 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:52422) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jLXBc-00011W-2w for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:33 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1jLXBa-0006i9-Us for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:32 -0400 Received: from us-smtp-delivery-1.mimecast.com ([207.211.31.120]:42718 helo=us-smtp-1.mimecast.com) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1jLXBa-0006hc-RJ for qemu-devel@nongnu.org; Mon, 06 Apr 2020 15:13:30 -0400 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-203-GVZshSvyN_i567-Lf4XtVQ-1; Mon, 06 Apr 2020 15:13:28 -0400 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 47C7C8017CE; Mon, 6 Apr 2020 19:13:27 +0000 (UTC) Received: from virtlab701.virt.lab.eng.bos.redhat.com (virtlab701.virt.lab.eng.bos.redhat.com [10.19.152.228]) by smtp.corp.redhat.com (Postfix) with ESMTP id CB03A62697; Mon, 6 Apr 2020 19:13:26 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1586200410; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=7Ua1uVlJeZsGjldXbjT2beLLFwjIig2Wrf3VsNlyDJ0=; b=bKPec95/d25zRbXk4No7wBjqfkggJuZ4WvveBdoixjpGWHZICkecsI+4ZN4kdiSiRP35sI XZP8OGgKRE2isbLBY5NzmCehNqSeUAKu03wBxTpzzxqNjeQjsHTucVwgPKKHLA38j2FoDm 8NQFt04p/iLA1Mgk/F2Er3nxtKL13rc= X-MC-Unique: GVZshSvyN_i567-Lf4XtVQ-1 From: Paolo Bonzini To: qemu-devel@nongnu.org Subject: [PATCH 4/4] async: use explicit memory barriers and relaxed accesses Date: Mon, 6 Apr 2020 15:13:20 -0400 Message-Id: <20200406191320.13371-5-pbonzini@redhat.com> In-Reply-To: <20200406191320.13371-1-pbonzini@redhat.com> References: <20200406191320.13371-1-pbonzini@redhat.com> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.15 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 207.211.31.120 X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Ying Fang , stefanha@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" When using C11 atomics, non-seqcst reads and writes do not participate in the total order of seqcst operations. In util/async.c and util/aio-posi= x.c, in particular, the pattern that we use write ctx->notify_me write bh->scheduled read bh->scheduled read ctx->notify_me if !bh->scheduled, sleep if ctx->notify_me, notify needs to use seqcst operations for both the write and the read. In general this is something that we do not want, because there can be many sources that are polled in addition to bottom halves. The alternative is to place a seqcst memory barrier between the write and the read. This also comes with a disadvantage, in that the memory barrier is implicit on strongly-ordered architectures and it wastes a few dozen clock cycles. Fortunately, ctx->notify_me is never written concurrently by two threads, so we can instead relax the writes to ctx->notify_me. [This part of the commit message is still to be written more in detail and is what I am not sure about.] Analyzed-by: Ying Fang Signed-off-by: Paolo Bonzini Reviewed-by: Stefan Hajnoczi --- util/aio-posix.c | 9 ++++++++- util/aio-win32.c | 8 +++++++- util/async.c | 12 ++++++++++-- 3 files changed, 25 insertions(+), 4 deletions(-) diff --git a/util/aio-posix.c b/util/aio-posix.c index cd6cf0a4a9..37afec726f 100644 --- a/util/aio-posix.c +++ b/util/aio-posix.c @@ -569,7 +569,13 @@ bool aio_poll(AioContext *ctx, bool blocking) * so disable the optimization now. */ if (blocking) { - atomic_add(&ctx->notify_me, 2); + atomic_set(&ctx->notify_me, atomic_read(&ctx->notify_me) + 2); + /* + * Write ctx->notify_me before computing the timeout + * (reading bottom half flags, etc.). Pairs with + * atomic_xchg in aio_notify(). + */ + smp_mb(); } =20 qemu_lockcnt_inc(&ctx->list_lock); @@ -590,6 +596,7 @@ bool aio_poll(AioContext *ctx, bool blocking) } =20 if (blocking) { + /* Finish the poll before clearing the flag. */ atomic_sub(&ctx->notify_me, 2); aio_notify_accept(ctx); } diff --git a/util/aio-win32.c b/util/aio-win32.c index a23b9c364d..2cccdb35c1 100644 --- a/util/aio-win32.c +++ b/util/aio-win32.c @@ -331,7 +331,13 @@ bool aio_poll(AioContext *ctx, bool blocking) * so disable the optimization now. */ if (blocking) { - atomic_add(&ctx->notify_me, 2); + atomic_set(&ctx->notify_me, atomic_read(&ctx->notify_me) + 2); + /* + * Write ctx->notify_me before computing the timeout + * (reading bottom half flags, etc.). Pairs with + * atomic_xchg in aio_notify(). + */ + smp_mb(); } =20 qemu_lockcnt_inc(&ctx->list_lock); diff --git a/util/async.c b/util/async.c index b94518b948..ee1bc87d2b 100644 --- a/util/async.c +++ b/util/async.c @@ -249,7 +249,14 @@ aio_ctx_prepare(GSource *source, gint *timeout) { AioContext *ctx =3D (AioContext *) source; =20 - atomic_or(&ctx->notify_me, 1); + atomic_set(&ctx->notify_me, atomic_read(&ctx->notify_me) | 1); + + /* + * Write ctx->notify_me before computing the timeout + * (reading bottom half flags, etc.). Pairs with + * atomic_xchg in aio_notify(). + */ + smp_mb(); =20 /* We assume there is no timeout already supplied */ *timeout =3D qemu_timeout_ns_to_ms(aio_compute_timeout(ctx)); @@ -414,7 +422,7 @@ void aio_notify(AioContext *ctx) * with atomic_or in aio_ctx_prepare or atomic_add in aio_poll. */ smp_mb(); - if (ctx->notify_me) { + if (atomic_read(&ctx->notify_me)) { event_notifier_set(&ctx->notifier); atomic_mb_set(&ctx->notified, true); } --=20 2.18.2