From nobody Sun Nov 24 11:55:40 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; 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=pass(p=none dis=none) header.from=linaro.org ARC-Seal: i=1; a=rsa-sha256; t=1723814606; cv=none; d=zohomail.com; s=zohoarc; b=UvOlj3ouMeJD8WQIK2KMh+EWTBlqq4s+nkYE+Y7Y4FlRkZcmsWCqpHjOpWTh8y3iA7994EGJmCv6HFVUwQ9rFdiXU0/FDjDDqT2ef4yKP6SOH0sxcbnJJaS5MQ581MAOsaP9llec7fmhfqNiHtTdB25TQcl38JTXHVD1ED4Rd5E= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1723814606; h=Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=uQ6lW85Zu+/OmlzIIJ9luNAHJSF12nY6HV6G44fIzvs=; b=kuFcEmtjs5TYDGptUqkuyoP8JylvXt8hZZWkoASVeO5Ato/CRUEX+JN2WaxLTRCjozJYo7W87EJXKgYIgVNxcgL7Rocw15AGjmDdtKS+zqaqGu713jC42WMpzyO4LxrFpJFFzDXd1ZbXkYRFb/E0CPvbTYyU1lObpBNRsCxYHIw= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; 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=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1723814606281394.89329745628356; Fri, 16 Aug 2024 06:23:26 -0700 (PDT) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sewuV-0005i6-By; Fri, 16 Aug 2024 09:22:31 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1sewuM-0005Dz-Hb for qemu-devel@nongnu.org; Fri, 16 Aug 2024 09:22:25 -0400 Received: from mail-wm1-x32a.google.com ([2a00:1450:4864:20::32a]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1sewuJ-0007kW-JD for qemu-devel@nongnu.org; Fri, 16 Aug 2024 09:22:22 -0400 Received: by mail-wm1-x32a.google.com with SMTP id 5b1f17b1804b1-429c4a4c6a8so14655295e9.0 for ; Fri, 16 Aug 2024 06:22:19 -0700 (PDT) Received: from orth.archaic.org.uk (orth.archaic.org.uk. [2001:8b0:1d0::2]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-371898ab855sm3631948f8f.105.2024.08.16.06.22.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 16 Aug 2024 06:22:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1723814538; x=1724419338; darn=nongnu.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=uQ6lW85Zu+/OmlzIIJ9luNAHJSF12nY6HV6G44fIzvs=; b=DxifNPKuFxddrbkTOUSySSxiWM7MUaiuZYHDyl4W6IXf9nJSx5aamA7hcwNBMQE1UH 6pOXTYMphlAwDriEuHf3Z/M/6o+JPEcGo8X6EztzZ2oQkmSUos7yxLnW2/4qPh26d2Qf dp9dGI3ZQyd4KWJ6U+ROjDpm1EGi7JyjQT/EDnPK3flOSI29dQU7nhFc6JEtT5CZECuK TPCzLFi8GE/sSzg1WNZN24eGSADgGUkwF1wwJRbfcW6OxkHDaXDQo9KF4oFUYAp9Tn3v uPvMKPWGJpDRcIrWQZLLbEtrdR8wcF6BD9OZIX1dEnP68E2hDDGSjLOCNwAR9hMOfV06 gejw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723814538; x=1724419338; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=uQ6lW85Zu+/OmlzIIJ9luNAHJSF12nY6HV6G44fIzvs=; b=J4qHTxqqY12ZHkSuPiKpMLkmzDSZIS8BFrwNo2+4f8G7I+83yH9kK1ouXGnnT9UNR3 3kChlfobhWIaMP6HEEez8ou7xAzQvfhvOjQixCtFABqxAdD+DuoP/Le5O0hza4WpP7+n 7iuHAkhexKtYTzGqF4xTzGWJKcf3yXwxD8orJmS+fl+lNJ9pxdu0RxKwJTAi7xrU2NiK SPGNP0dlXKL3AFw0GnqxVpeQrwsIAbEKoVFyPcOMLnPotWArTfB3FUW3aU3a/ZfHBLrL rnRxj1aXbML86Yc+5t3qq+yZy0PoxZqXg6olmxMuuWV6tnqFp3bI4F9N1mM1QBQAJTQf o4cw== X-Gm-Message-State: AOJu0YyzyhNlt+J5zbAJR1y7+mbqO8ee6b6ISBnpLo21qzDMCpBDFC3O IEiXj64ErNUMeBiMoLCIxFu1MaUmfseNmBzHAQZEPliVPeggDWzxtXAReuWLLT8CnofpCOt6xyQ x X-Google-Smtp-Source: AGHT+IEQz65YMXJ9oS+9akpVK1HPO/yYExg0G5IkEnoSOYsk5yhRF3WleXZSxzr1rOO7lneL5Jl1XA== X-Received: by 2002:a05:6000:1112:b0:368:714e:5a5e with SMTP id ffacd0b85a97d-3719431764cmr2209985f8f.2.1723814537863; Fri, 16 Aug 2024 06:22:17 -0700 (PDT) From: Peter Maydell To: qemu-devel@nongnu.org Cc: Paolo Bonzini , Kevin Wolf , Hanna Reitz , Stefan Hajnoczi Subject: [PATCH 5/7] docs/devel/rcu: Convert to rST format Date: Fri, 16 Aug 2024 14:22:10 +0100 Message-Id: <20240816132212.3602106-6-peter.maydell@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240816132212.3602106-1-peter.maydell@linaro.org> References: <20240816132212.3602106-1-peter.maydell@linaro.org> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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; Received-SPF: pass client-ip=2a00:1450:4864:20::32a; envelope-from=peter.maydell@linaro.org; helo=mail-wm1-x32a.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: qemu-devel-bounces+importer=patchew.org@nongnu.org X-ZohoMail-DKIM: pass (identity @linaro.org) X-ZM-MESSAGEID: 1723814607425116600 Content-Type: text/plain; charset="utf-8" Convert docs/devel/rcu.txt to rST format. Signed-off-by: Peter Maydell --- MAINTAINERS | 2 +- docs/devel/index-internals.rst | 1 + docs/devel/{rcu.txt =3D> rcu.rst} | 172 +++++++++++++++----------------- 3 files changed, 82 insertions(+), 93 deletions(-) rename docs/devel/{rcu.txt =3D> rcu.rst} (73%) diff --git a/MAINTAINERS b/MAINTAINERS index 9e091a4e214..f8f4df44460 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -3113,7 +3113,7 @@ Read, Copy, Update (RCU) M: Paolo Bonzini S: Maintained F: docs/devel/lockcnt.rst -F: docs/devel/rcu.txt +F: docs/devel/rcu.rst F: include/qemu/rcu*.h F: tests/unit/rcutorture.c F: tests/unit/test-rcu-*.c diff --git a/docs/devel/index-internals.rst b/docs/devel/index-internals.rst index 88fa0e9450d..ab9fbc44826 100644 --- a/docs/devel/index-internals.rst +++ b/docs/devel/index-internals.rst @@ -8,6 +8,7 @@ Details about QEMU's various subsystems including how to ad= d features to them. =20 qom atomics + rcu block-coroutine-wrapper clocks ebpf_rss diff --git a/docs/devel/rcu.txt b/docs/devel/rcu.rst similarity index 73% rename from docs/devel/rcu.txt rename to docs/devel/rcu.rst index 2e6cc607a17..dd07c1d9195 100644 --- a/docs/devel/rcu.txt +++ b/docs/devel/rcu.rst @@ -20,7 +20,7 @@ for the execution of all *currently running* critical sec= tions before proceeding, or before asynchronously executing a callback. =20 The key point here is that only the currently running critical sections -are waited for; critical sections that are started _after_ the beginning +are waited for; critical sections that are started **after** the beginning of the wait do not extend the wait, despite running concurrently with the updater. This is the reason why RCU is more scalable than, for example, reader-writer locks. It is so much more scalable that @@ -37,7 +37,7 @@ do not matter; as soon as all previous critical sections = have finished, there cannot be any readers who hold references to the data structure, and these can now be safely reclaimed (e.g., freed or unref'ed). =20 -Here is a picture: +Here is a picture:: =20 thread 1 thread 2 thread 3 ------------------- ------------------------ ------------------- @@ -58,43 +58,38 @@ that critical section. =20 =20 RCU API -=3D=3D=3D=3D=3D=3D=3D +------- =20 The core RCU API is small: =20 - void rcu_read_lock(void); - +``void rcu_read_lock(void);`` Used by a reader to inform the reclaimer that the reader is entering an RCU read-side critical section. =20 - void rcu_read_unlock(void); - +``void rcu_read_unlock(void);`` Used by a reader to inform the reclaimer that the reader is exiting an RCU read-side critical section. Note that RCU read-side critical sections may be nested and/or overlapping. =20 - void synchronize_rcu(void); - +``void synchronize_rcu(void);`` Blocks until all pre-existing RCU read-side critical sections on all threads have completed. This marks the end of the removal phase and the beginning of reclamation phase. =20 Note that it would be valid for another update to come while - synchronize_rcu is running. Because of this, it is better that + ``synchronize_rcu`` is running. Because of this, it is better that the updater releases any locks it may hold before calling - synchronize_rcu. If this is not possible (for example, because - the updater is protected by the BQL), you can use call_rcu. + ``synchronize_rcu``. If this is not possible (for example, because + the updater is protected by the BQL), you can use ``call_rcu``. =20 - void call_rcu1(struct rcu_head * head, - void (*func)(struct rcu_head *head)); - - This function invokes func(head) after all pre-existing RCU +``void call_rcu1(struct rcu_head * head, void (*func)(struct rcu_head *hea= d));`` + This function invokes ``func(head)`` after all pre-existing RCU read-side critical sections on all threads have completed. This marks the end of the removal phase, with func taking care asynchronously of the reclamation phase. =20 - The foo struct needs to have an rcu_head structure added, - perhaps as follows: + The ``foo`` struct needs to have an ``rcu_head`` structure added, + perhaps as follows:: =20 struct foo { struct rcu_head rcu; @@ -103,8 +98,8 @@ The core RCU API is small: long c; }; =20 - so that the reclaimer function can fetch the struct foo address - and free it: + so that the reclaimer function can fetch the ``struct foo`` address + and free it:: =20 call_rcu1(&foo.rcu, foo_reclaim); =20 @@ -114,29 +109,27 @@ The core RCU API is small: g_free(fp); } =20 - For the common case where the rcu_head member is the first of the - struct, you can use the following macro. + ``call_rcu1`` is typically used via either the ``call_rcu`` or + ``g_free_rcu`` macros, which handle the common case where the + ``rcu_head`` member is the first of the struct. =20 - void call_rcu(T *p, - void (*func)(T *p), - field-name); - void g_free_rcu(T *p, - field-name); +``void call_rcu(T *p, void (*func)(T *p), field-name);`` + If the ``struct rcu_head`` is the first field in the struct, you c= an + use this macro instead of ``call_rcu1``. =20 - call_rcu1 is typically used through these macro, in the common case - where the "struct rcu_head" is the first field in the struct. If - the callback function is g_free, in particular, g_free_rcu can be - used. In the above case, one could have written simply: +``void g_free_rcu(T *p, field-name);`` + This is a special-case version of ``call_rcu`` where the callback + function is ``g_free``. + In the example given in ``call_rcu1``, one could have written simp= ly:: =20 g_free_rcu(&foo, rcu); =20 - typeof(*p) qatomic_rcu_read(p); +``typeof(*p) qatomic_rcu_read(p);`` + ``qatomic_rcu_read()`` is similar to ``qatomic_load_acquire()``, b= ut + it makes some assumptions on the code that calls it. This allows a + more optimized implementation. =20 - qatomic_rcu_read() is similar to qatomic_load_acquire(), but it ma= kes - some assumptions on the code that calls it. This allows a more - optimized implementation. - - qatomic_rcu_read assumes that whenever a single RCU critical + ``qatomic_rcu_read`` assumes that whenever a single RCU critical section reads multiple shared data, these reads are either data-dependent or need no ordering. This is almost always the case when using RCU, because read-side critical sections typically @@ -144,7 +137,7 @@ The core RCU API is small: every update) until reaching a data structure of interest, and then read from there. =20 - RCU read-side critical sections must use qatomic_rcu_read() to + RCU read-side critical sections must use ``qatomic_rcu_read()`` to read data, unless concurrent writes are prevented by another synchronization mechanism. =20 @@ -152,18 +145,17 @@ The core RCU API is small: data structure in a single direction, opposite to the direction in which the updater initializes it. =20 - void qatomic_rcu_set(p, typeof(*p) v); +``void qatomic_rcu_set(p, typeof(*p) v);`` + ``qatomic_rcu_set()`` is similar to ``qatomic_store_release()``, + though it also makes assumptions on the code that calls it in + order to allow a more optimized implementation. =20 - qatomic_rcu_set() is similar to qatomic_store_release(), though it= also - makes assumptions on the code that calls it in order to allow a mo= re - optimized implementation. - - In particular, qatomic_rcu_set() suffices for synchronization + In particular, ``qatomic_rcu_set()`` suffices for synchronization with readers, if the updater never mutates a field within a data item that is already accessible to readers. This is the case when initializing a new copy of the RCU-protected data - structure; just ensure that initialization of *p is carried out - before qatomic_rcu_set() makes the data item visible to readers. + structure; just ensure that initialization of ``*p`` is carried out + before ``qatomic_rcu_set()`` makes the data item visible to reader= s. If this rule is observed, writes will happen in the opposite order as reads in the RCU read-side critical sections (or if there is just one update), and there will be no need for other @@ -171,58 +163,54 @@ The core RCU API is small: =20 The following APIs must be used before RCU is used in a thread: =20 - void rcu_register_thread(void); - +``void rcu_register_thread(void);`` Mark a thread as taking part in the RCU mechanism. Such a thread will have to report quiescent points regularly, either manually - or through the QemuCond/QemuSemaphore/QemuEvent APIs. - - void rcu_unregister_thread(void); + or through the ``QemuCond``/``QemuSemaphore``/``QemuEvent`` APIs. =20 +``void rcu_unregister_thread(void);`` Mark a thread as not taking part anymore in the RCU mechanism. It is not a problem if such a thread reports quiescent points, - either manually or by using the QemuCond/QemuSemaphore/QemuEvent - APIs. + either manually or by using the + ``QemuCond``/``QemuSemaphore``/``QemuEvent`` APIs. =20 -Note that these APIs are relatively heavyweight, and should _not_ be +Note that these APIs are relatively heavyweight, and should **not** be nested. =20 Convenience macros -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D +------------------ =20 Two macros are provided that automatically release the read lock at the end of the scope. =20 - RCU_READ_LOCK_GUARD() - +``RCU_READ_LOCK_GUARD()`` Takes the lock and will release it at the end of the block it's used in. =20 - WITH_RCU_READ_LOCK_GUARD() { code } - +``WITH_RCU_READ_LOCK_GUARD() { code }`` Is used at the head of a block to protect the code within the blo= ck. =20 -Note that 'goto'ing out of the guarded block will also drop the lock. +Note that a ``goto`` out of the guarded block will also drop the lock. =20 -DIFFERENCES WITH LINUX -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D +Differences with Linux +---------------------- =20 - Waiting on a mutex is possible, though discouraged, within an RCU critic= al section. This is because spinlocks are rarely (if ever) used in userspa= ce programming; not allowing this would prevent upgrading an RCU read-side critical section to become an updater. =20 -- qatomic_rcu_read and qatomic_rcu_set replace rcu_dereference and - rcu_assign_pointer. They take a _pointer_ to the variable being accesse= d. +- ``qatomic_rcu_read`` and ``qatomic_rcu_set`` replace ``rcu_dereference``= and + ``rcu_assign_pointer``. They take a **pointer** to the variable being a= ccessed. =20 -- call_rcu is a macro that has an extra argument (the name of the first - field in the struct, which must be a struct rcu_head), and expects the +- ``call_rcu`` is a macro that has an extra argument (the name of the first + field in the struct, which must be a struct ``rcu_head``), and expects t= he type of the callback's argument to be the type of the first argument. - call_rcu1 is the same as Linux's call_rcu. + ``call_rcu1`` is the same as Linux's ``call_rcu``. =20 =20 -RCU PATTERNS -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D +RCU Patterns +------------ =20 Many patterns using read-writer locks translate directly to RCU, with the advantages of higher scalability and deadlock immunity. @@ -243,28 +231,28 @@ Here are some frequently-used RCU idioms that are wor= th noting. =20 =20 RCU list processing -------------------- +^^^^^^^^^^^^^^^^^^^ =20 TBD (not yet used in QEMU) =20 =20 RCU reference counting ----------------------- +^^^^^^^^^^^^^^^^^^^^^^ =20 Because grace periods are not allowed to complete while there is an RCU read-side critical section in progress, the RCU read-side primitives may be used as a restricted reference-counting mechanism. For example, -consider the following code fragment: +consider the following code fragment:: =20 rcu_read_lock(); p =3D qatomic_rcu_read(&foo); /* do something with p. */ rcu_read_unlock(); =20 -The RCU read-side critical section ensures that the value of "p" remains -valid until after the rcu_read_unlock(). In some sense, it is acquiring -a reference to p that is later released when the critical section ends. -The write side looks simply like this (with appropriate locking): +The RCU read-side critical section ensures that the value of ``p`` remains +valid until after the ``rcu_read_unlock()``. In some sense, it is acquiri= ng +a reference to ``p`` that is later released when the critical section ends. +The write side looks simply like this (with appropriate locking):: =20 qemu_mutex_lock(&foo_mutex); old =3D foo; @@ -274,7 +262,7 @@ The write side looks simply like this (with appropriate= locking): free(old); =20 If the processing cannot be done purely within the critical section, it -is possible to combine this idiom with a "real" reference count: +is possible to combine this idiom with a "real" reference count:: =20 rcu_read_lock(); p =3D qatomic_rcu_read(&foo); @@ -283,7 +271,7 @@ is possible to combine this idiom with a "real" referen= ce count: /* do something with p. */ foo_unref(p); =20 -The write side can be like this: +The write side can be like this:: =20 qemu_mutex_lock(&foo_mutex); old =3D foo; @@ -292,7 +280,7 @@ The write side can be like this: synchronize_rcu(); foo_unref(old); =20 -or with call_rcu: +or with ``call_rcu``:: =20 qemu_mutex_lock(&foo_mutex); old =3D foo; @@ -301,10 +289,10 @@ or with call_rcu: call_rcu(foo_unref, old, rcu); =20 In both cases, the write side only performs removal. Reclamation -happens when the last reference to a "foo" object is dropped. -Using synchronize_rcu() is undesirably expensive, because the +happens when the last reference to a ``foo`` object is dropped. +Using ``synchronize_rcu()`` is undesirably expensive, because the last reference may be dropped on the read side. Hence you can -use call_rcu() instead: +use ``call_rcu()`` instead:: =20 foo_unref(struct foo *p) { if (qatomic_fetch_dec(&p->refcount) =3D=3D 1) { @@ -314,7 +302,7 @@ use call_rcu() instead: =20 =20 Note that the same idioms would be possible with reader/writer -locks: +locks:: =20 read_lock(&foo_rwlock); write_mutex_lock(&foo_rwlock); p =3D foo; p =3D foo; @@ -334,15 +322,15 @@ locks: foo_unref(p); read_unlock(&foo_rwlock); =20 -foo_unref could use a mechanism such as bottom halves to move deallocation +``foo_unref`` could use a mechanism such as bottom halves to move dealloca= tion out of the write-side critical section. =20 =20 RCU resizable arrays --------------------- +^^^^^^^^^^^^^^^^^^^^ =20 Resizable arrays can be used with RCU. The expensive RCU synchronization -(or call_rcu) only needs to take place when the array is resized. +(or ``call_rcu``) only needs to take place when the array is resized. The two items to take care of are: =20 - ensuring that the old version of the array is available between removal @@ -351,10 +339,10 @@ The two items to take care of are: - avoiding mismatches in the read side between the array data and the array size. =20 -The first problem is avoided simply by not using realloc. Instead, +The first problem is avoided simply by not using ``realloc``. Instead, each resize will allocate a new array and copy the old data into it. The second problem would arise if the size and the data pointers were -two members of a larger struct: +two members of a larger struct:: =20 struct mystuff { ... @@ -364,7 +352,7 @@ two members of a larger struct: ... }; =20 -Instead, we store the size of the array with the array itself: +Instead, we store the size of the array with the array itself:: =20 struct arr { int size; @@ -400,7 +388,7 @@ Instead, we store the size of the array with the array = itself: } =20 =20 -SOURCES -=3D=3D=3D=3D=3D=3D=3D +References +---------- =20 -* Documentation/RCU/ from the Linux kernel +* The `Linux kernel RCU documentation `__ --=20 2.34.1