Received: by 2002:a25:31c3:0:0:0:0:0 with SMTP id x186csp1703707ybx; Sat, 2 Nov 2019 04:56:30 -0700 (PDT) X-Google-Smtp-Source: APXvYqzf/7HnDZK/UPgQ3zOcP5v/C9RsH56pRe9z1hv4foRkHzJenRRbBO3ax2OzmbSrIBRZJ99Y X-Received: by 2002:a05:6402:783:: with SMTP id d3mr2823749edy.180.1572695790019; Sat, 02 Nov 2019 04:56:30 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1572695790; cv=none; d=google.com; s=arc-20160816; b=X5cJNFLtk2/Edl8WTvYTPXcRekx01DasK7ZL6YJJg38UnGFsfm9Ml+90itrRSM2vCp 3j+wQvhe/dWCVb7m4KcRAlYjjW+ZKsxEz9WxWI282h6v9X60IBetYZUDE2amcpUZPx5D q3jNQ4ucu+vuu9EQWq+HatOv0FjYx54L/lsrBba9u0GZzDErfMd7DE71foZI8TZcmtds y+diAYG3Ws+q5LnWBYMY6ODmy3orGHQhU/Pcq2z0rxmtN3GqXKtCkdkrKVXVhZyK2bzM n6/3nKIm8qUrfynJiu/N2BzyZzYy4SbMxVBhha1QUDObGr4hlevNiZrPu5Ezic72dLmB ixFQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:content-transfer-encoding:mime-version :message-id:date:subject:cc:to:from:dkim-signature; bh=7u/iOR7HJqtZD8nquIFJaMlxUwUZ2mligFudZlnPrWU=; b=jYdKZ8/babY65lZXaBayVk9m8IaXUbaKUYbQCo6UC8XOJ9qe32tI+lw9PTs7aBwGzh efrXpLx+e1sjKrBzgkBEoqLFvV501jnMxtE2STN/nRO5ifYJxZGD8yHG2LDD+hvp13R5 Zm+cfdHAChdtFuWp/d0Y8w2sVYZf4aJrmlc1YBohs6SnUNpSo6JCp2Q4qCyQGxdKpinL ulMW7nICDG48lJZJ75HG3QYDzMu973GMpcLg4Ps3aDb9pzq8iy+UFFJJ/AfN8E1uitPb KLzkLDVz+t28kKSKNdaaL5nRP7hmODn5lDKYcXBkdksryjYgFknLjBavUC0y7JxbhfYM 8+/Q== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=UnWMI5MI; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id a7si7787395ejj.288.2019.11.02.04.56.04; Sat, 02 Nov 2019 04:56:30 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=UnWMI5MI; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726454AbfKBLzf (ORCPT + 99 others); Sat, 2 Nov 2019 07:55:35 -0400 Received: from mail-pf1-f193.google.com ([209.85.210.193]:40330 "EHLO mail-pf1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726163AbfKBLzf (ORCPT ); Sat, 2 Nov 2019 07:55:35 -0400 Received: by mail-pf1-f193.google.com with SMTP id r4so8796839pfl.7; Sat, 02 Nov 2019 04:55:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=7u/iOR7HJqtZD8nquIFJaMlxUwUZ2mligFudZlnPrWU=; b=UnWMI5MI5/gxEd8ihgP7kS9XWpzKHAH7ezgi6KAANGgBemAcX1+iFM6NVxnzuzVjf4 tn0H2sMS8+m71lBTPPzsca+MSFg5ULBumVtzCY/TYQcMdGZpkWwQems7wB74qLPNXsaA w2VJremR97MGbNCqbv+mXjqQvVyJz4li6FdYz7V8n9ubDmsrBk5TjeGYWkdTXKEBfDpX NkCQj4P0XePvhDx8OUWuaFwtYeb20FutncuFZvt2sQqJ7By14n8Oo4iy/RIMyk/OWOXX fAF5ALjaQvnr3PWHJ6/1qDqLcqs/hxOg74Y6H4yWVkAjA6eYNDX8lM+zZJjb8ErwBMLV Wfiw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=7u/iOR7HJqtZD8nquIFJaMlxUwUZ2mligFudZlnPrWU=; b=jI5JO8Duikbx/YoTtnCj3+OlY34z+npR9Idtp96QS7i2dhtsl5sXWTqf9xZ/r4VX55 MjBQA6/nFiE/bkd1aAsjXmaRSxsF7SnjFPVfkjZjVaV0gr9nuCzIRH32ISjvwLv5iuLr F4UhU1wYwSX/BfOAs5/GPcpdPez8b+c9D8UoA+go1JF7LCvN1O2zdHC/2Nbm0lVt27c7 4CED+zU5AgITviDAMig9WdtxhEYna2D+j0LenK+3alaYBG7/+vgE6hq4tDKI2bVwqFz/ exG6YE1xDLm1fu7mLxZkO5PwAzz6nc+qaTqhhY/D/cyT2Fdz7Arc6D1FjKAD7WWMyk99 DOMw== X-Gm-Message-State: APjAAAVQj9FAhGfOIv4rZGcdDXazE+wBZYtJU8kYjVG8B+cYciBtI9E7 PY7DQVu/kmM0UiqcDz5ksy8= X-Received: by 2002:a17:90a:d993:: with SMTP id d19mr21679885pjv.26.1572695733504; Sat, 02 Nov 2019 04:55:33 -0700 (PDT) Received: from debian.net.fpt ([2405:4800:58f7:55d9:3e01:3008:2e64:188f]) by smtp.gmail.com with ESMTPSA id a12sm5122320pfo.136.2019.11.02.04.55.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 02 Nov 2019 04:55:32 -0700 (PDT) From: Phong Tran To: paulmck@kernel.org, josh@joshtriplett.org, rostedt@goodmis.org, mathieu.desnoyers@efficios.com, jiangshanlai@gmail.com, joel@joelfernandes.org, corbet@lwn.net, madhuparnabhowmik04@gmail.com Cc: rcu@vger.kernel.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-kernel-mentees@lists.linuxfoundation.org, skhan@linuxfoundation.org, Phong Tran Subject: [PATCH] Doc: Improve format for whatisRCU.rst Date: Sat, 2 Nov 2019 18:55:17 +0700 Message-Id: <20191102115517.6378-1-tranmanphong@gmail.com> X-Mailer: git-send-email 2.20.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Adding crossreference target for some headers, answer of quizzes Signed-off-by: Phong Tran --- Documentation/RCU/whatisRCU.rst | 73 +++++++++++++++++++++++---------- 1 file changed, 52 insertions(+), 21 deletions(-) diff --git a/Documentation/RCU/whatisRCU.rst b/Documentation/RCU/whatisRCU.rst index 70d0e4c21917..ae40c8bcc56c 100644 --- a/Documentation/RCU/whatisRCU.rst +++ b/Documentation/RCU/whatisRCU.rst @@ -1,4 +1,4 @@ -.. _rcu_doc: +.. _whatisrcu_doc: What is RCU? -- "Read, Copy, Update" ====================================== @@ -27,14 +27,21 @@ the experience has been that different people must take different paths to arrive at an understanding of RCU. This document provides several different paths, as follows: -1. RCU OVERVIEW -2. WHAT IS RCU'S CORE API? -3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API? -4. WHAT IF MY UPDATING THREAD CANNOT BLOCK? -5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? -6. ANALOGY WITH READER-WRITER LOCKING -7. FULL LIST OF RCU APIs -8. ANSWERS TO QUICK QUIZZES +:ref:`1. RCU OVERVIEW <1_whatisRCU>` + +:ref:`2. WHAT IS RCU'S CORE API? <2_whatisRCU>` + +:ref:`3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API? <3_whatisRCU>` + +:ref:`4. WHAT IF MY UPDATING THREAD CANNOT BLOCK? <4_whatisRCU>` + +:ref:`5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? <5_whatisRCU>` + +:ref:`6. ANALOGY WITH READER-WRITER LOCKING <6_whatisRCU>` + +:ref:`7. FULL LIST OF RCU APIs <7_whatisRCU>` + +:ref:`8. ANSWERS TO QUICK QUIZZES <8_whatisRCU>` People who prefer starting with a conceptual overview should focus on Section 1, though most readers will profit by reading this section at @@ -52,6 +59,7 @@ everything, feel free to read the whole thing -- but if you are really that type of person, you have perused the source code and will therefore never need this document anyway. ;-) +.. _1_whatisRCU: 1. RCU OVERVIEW ---------------- @@ -120,6 +128,7 @@ So how the heck can a reclaimer tell when a reader is done, given that readers are not doing any sort of synchronization operations??? Read on to learn about how RCU's API makes this easy. +.. _2_whatisRCU: 2. WHAT IS RCU'S CORE API? --------------------------- @@ -381,13 +390,15 @@ c. RCU applied to scheduler and interrupt/NMI-handler tasks. Again, most uses will be of (a). The (b) and (c) cases are important for specialized uses, but are relatively uncommon. +.. _3_whatisRCU: 3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API? ----------------------------------------------- This section shows a simple use of the core RCU API to protect a global pointer to a dynamically allocated structure. More-typical -uses of RCU may be found in listRCU.txt, arrayRCU.txt, and NMI-RCU.txt. +uses of RCU may be found in :ref:`listRCU.rst `, +:ref:`arrayRCU.rst `, and :ref:`NMI-RCU.rst `. :: struct foo { @@ -470,9 +481,11 @@ o Use synchronize_rcu() -after- removing a data element from an data item. See checklist.txt for additional rules to follow when using RCU. -And again, more-typical uses of RCU may be found in listRCU.txt, -arrayRCU.txt, and NMI-RCU.txt. +And again, more-typical uses of RCU may be found in :ref:`listRCU.rst +`, :ref:`arrayRCU.rst `, and :ref:`NMI-RCU.rst +`. +.. _4_whatisRCU: 4. WHAT IF MY UPDATING THREAD CANNOT BLOCK? -------------------------------------------- @@ -567,6 +580,7 @@ to avoid having to write your own callback:: Again, see checklist.txt for additional rules governing the use of RCU. +.. _5_whatisRCU: 5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? ------------------------------------------------ @@ -657,10 +671,12 @@ that the only thing that can block rcu_read_lock() is a synchronize_rcu(). But synchronize_rcu() does not acquire any locks while holding rcu_gp_mutex, so there can be no deadlock cycle. -Quick Quiz #1: Why is this argument naive? How could a deadlock +Quick Quiz #1: + Why is this argument naive? How could a deadlock occur when using this algorithm in a real-world Linux kernel? How could this deadlock be avoided? +:ref:`Answers to Quick Quiz <8_whatisRCU>` 5B. "TOY" EXAMPLE #2: CLASSIC RCU @@ -709,13 +725,20 @@ synchronize_rcu(). Once synchronize_rcu() returns, we are guaranteed that there are no RCU read-side critical sections holding a reference to that data item, so we can safely reclaim it. -Quick Quiz #2: Give an example where Classic RCU's read-side +Quick Quiz #2: + Give an example where Classic RCU's read-side overhead is -negative-. -Quick Quiz #3: If it is illegal to block in an RCU read-side +:ref:`Answers to Quick Quiz <8_whatisRCU>` + +Quick Quiz #3: + If it is illegal to block in an RCU read-side critical section, what the heck do you do in PREEMPT_RT, where normal spinlocks can block??? +:ref:`Answers to Quick Quiz <8_whatisRCU>` + +.. _6_whatisRCU: 6. ANALOGY WITH READER-WRITER LOCKING -------------------------------------- @@ -842,6 +865,7 @@ delete() can now block. If this is a problem, there is a callback-based mechanism that never blocks, namely call_rcu() or kfree_rcu(), that can be used in place of synchronize_rcu(). +.. _7_whatisRCU: 7. FULL LIST OF RCU APIs ------------------------- @@ -1001,16 +1025,19 @@ g. Otherwise, use RCU. Of course, this all assumes that you have determined that RCU is in fact the right tool for your job. +.. _8_whatisRCU: 8. ANSWERS TO QUICK QUIZZES ---------------------------- -Quick Quiz #1: Why is this argument naive? How could a deadlock +Quick Quiz #1: + Why is this argument naive? How could a deadlock occur when using this algorithm in a real-world Linux kernel? [Referring to the lock-based "toy" RCU algorithm.] -Answer: Consider the following sequence of events: +Answer: + Consider the following sequence of events: 1. CPU 0 acquires some unrelated lock, call it "problematic_lock", disabling irq via @@ -1049,10 +1076,12 @@ Answer: Consider the following sequence of events: approach where tasks in RCU read-side critical sections cannot be blocked by tasks executing synchronize_rcu(). -Quick Quiz #2: Give an example where Classic RCU's read-side +Quick Quiz #2: + Give an example where Classic RCU's read-side overhead is -negative-. -Answer: Imagine a single-CPU system with a non-CONFIG_PREEMPT +Answer: + Imagine a single-CPU system with a non-CONFIG_PREEMPT kernel where a routing table is used by process-context code, but can be updated by irq-context code (for example, by an "ICMP REDIRECT" packet). The usual way of handling @@ -1074,11 +1103,13 @@ Answer: Imagine a single-CPU system with a non-CONFIG_PREEMPT even the theoretical possibility of negative overhead for a synchronization primitive is a bit unexpected. ;-) -Quick Quiz #3: If it is illegal to block in an RCU read-side +Quick Quiz #3: + If it is illegal to block in an RCU read-side critical section, what the heck do you do in PREEMPT_RT, where normal spinlocks can block??? -Answer: Just as PREEMPT_RT permits preemption of spinlock +Answer: + Just as PREEMPT_RT permits preemption of spinlock critical sections, it permits preemption of RCU read-side critical sections. It also permits spinlocks blocking while in RCU read-side critical -- 2.20.1