[Linux-kernel-mentees] [PATCH v2 3/7] Documentation: RCU: Convert RCU linked list to ReST

Joel Fernandes joel at joelfernandes.org
Sun Jun 23 23:31:58 UTC 2019


On Sun, Jun 23, 2019 at 03:14:09AM -0500, Jiunn Chang wrote:
> ReST markup and TOC tree hook.
> 
> Signed-off-by: Jiunn Chang <c0d1n61at3 at gmail.com>
> ---
>  Documentation/RCU/index.rst   |  1 +
>  Documentation/RCU/listRCU.txt | 33 +++++++++++++++++++--------------
>  2 files changed, 20 insertions(+), 14 deletions(-)
> 
> diff --git a/Documentation/RCU/index.rst b/Documentation/RCU/index.rst
> index bc8cd42a91cc..5a19c3642e88 100644
> --- a/Documentation/RCU/index.rst
> +++ b/Documentation/RCU/index.rst
> @@ -8,6 +8,7 @@ RCU concepts
>     :maxdepth: 1
>  
>     rcu
> +   list_rcu
>  
>  .. only:: subproject and html
>  
> diff --git a/Documentation/RCU/listRCU.txt b/Documentation/RCU/listRCU.txt
> index adb5a3782846..f786cd82c6a7 100644
> --- a/Documentation/RCU/listRCU.txt
> +++ b/Documentation/RCU/listRCU.txt
> @@ -1,14 +1,16 @@
> -Using RCU to Protect Read-Mostly Linked Lists
> +.. _list_rcu_doc:
>  
> +Using RCU to Protect Read-Mostly Linked Lists
> +=============================================
>  
>  One of the best applications of RCU is to protect read-mostly linked lists
> -("struct list_head" in list.h).  One big advantage of this approach
> +(*struct list_head* in ``list.h``).  One big advantage of this approach
>  is that all of the required memory barriers are included for you in
>  the list macros.  This document describes several applications of RCU,
>  with the best fits first.
>  
> -
>  Example 1: Read-Side Action Taken Outside of Lock, No In-Place Updates
> +----------------------------------------------------------------------
>  
>  The best applications are cases where, if reader-writer locking were
>  used, the read-side lock would be dropped before taking any action
> @@ -24,7 +26,7 @@ added or deleted, rather than being modified in place.
>  
>  A straightforward example of this use of RCU may be found in the
>  system-call auditing support.  For example, a reader-writer locked
> -implementation of audit_filter_task() might be as follows:
> +implementation of audit_filter_task() might be as follows::
>  
>  	static enum audit_state audit_filter_task(struct task_struct *tsk)
>  	{
> @@ -48,7 +50,7 @@ the corresponding value is returned.  By the time that this value is acted
>  on, the list may well have been modified.  This makes sense, since if
>  you are turning auditing off, it is OK to audit a few extra system calls.
>  
> -This means that RCU can be easily applied to the read side, as follows:
> +This means that RCU can be easily applied to the read side, as follows::
>  
>  	static enum audit_state audit_filter_task(struct task_struct *tsk)
>  	{
> @@ -73,7 +75,7 @@ become list_for_each_entry_rcu().  The _rcu() list-traversal primitives
>  insert the read-side memory barriers that are required on DEC Alpha CPUs.
>  
>  The changes to the update side are also straightforward.  A reader-writer
> -lock might be used as follows for deletion and insertion:
> +lock might be used as follows for deletion and insertion::
>  
>  	static inline int audit_del_rule(struct audit_rule *rule,
>  					 struct list_head *list)
> @@ -106,7 +108,7 @@ lock might be used as follows for deletion and insertion:
>  		return 0;
>  	}
>  
> -Following are the RCU equivalents for these two functions:
> +Following are the RCU equivalents for these two functions::
>  
>  	static inline int audit_del_rule(struct audit_rule *rule,
>  					 struct list_head *list)
> @@ -154,13 +156,13 @@ otherwise cause concurrent readers to fail spectacularly.
>  So, when readers can tolerate stale data and when entries are either added
>  or deleted, without in-place modification, it is very easy to use RCU!
>  
> -
>  Example 2: Handling In-Place Updates
> +------------------------------------
>  
>  The system-call auditing code does not update auditing rules in place.
>  However, if it did, reader-writer-locked code to do so might look as
>  follows (presumably, the field_count is only permitted to decrease,
> -otherwise, the added fields would need to be filled in):
> +otherwise, the added fields would need to be filled in)::
>  
>  	static inline int audit_upd_rule(struct audit_rule *rule,
>  					 struct list_head *list,
> @@ -187,7 +189,7 @@ otherwise, the added fields would need to be filled in):
>  The RCU version creates a copy, updates the copy, then replaces the old
>  entry with the newly updated entry.  This sequence of actions, allowing
>  concurrent reads while doing a copy to perform an update, is what gives
> -RCU ("read-copy update") its name.  The RCU code is as follows:
> +RCU ("read-copy update") its name.  The RCU code is as follows::
>  
>  	static inline int audit_upd_rule(struct audit_rule *rule,
>  					 struct list_head *list,
> @@ -216,8 +218,8 @@ RCU ("read-copy update") its name.  The RCU code is as follows:
>  Again, this assumes that the caller holds audit_netlink_sem.  Normally,
>  the reader-writer lock would become a spinlock in this sort of code.
>  
> -
>  Example 3: Eliminating Stale Data
> +---------------------------------
>  
>  The auditing examples above tolerate stale data, as do most algorithms
>  that are tracking external state.  Because there is a delay from the
> @@ -234,10 +236,12 @@ return holding the per-entry spinlock, as ipc_lock() does in fact do.
>  Quick Quiz:  Why does the search function need to return holding the
>  	per-entry lock for this deleted-flag technique to be helpful?
>  
> +:ref:`answer_quick_quiz`
> +
>  If the system-call audit module were to ever need to reject stale data,
>  one way to accomplish this would be to add a "deleted" flag and a "lock"
>  spinlock to the audit_entry structure, and modify audit_filter_task()
> -as follows:
> +as follows::
>  
>  	static enum audit_state audit_filter_task(struct task_struct *tsk)
>  	{
> @@ -268,7 +272,7 @@ audit_upd_rule() would need additional memory barriers to ensure
>  that the list_add_rcu() was really executed before the list_del_rcu().
>  
>  The audit_del_rule() function would need to set the "deleted"
> -flag under the spinlock as follows:
> +flag under the spinlock as follows::
>  
>  	static inline int audit_del_rule(struct audit_rule *rule,
>  					 struct list_head *list)
> @@ -290,8 +294,10 @@ flag under the spinlock as follows:
>  		return -EFAULT;		/* No matching rule */
>  	}
>  
> +.. _answer_quick_quiz:

Should the _answer_quick_quiz label below where 'Answer to Quick Quiz' is below?


>  
>  Summary
> +-------
>  
>  Read-mostly list-based data structures that can tolerate stale data are
>  the most amenable to use of RCU.  The simplest case is where entries are
> @@ -302,7 +308,6 @@ If stale data cannot be tolerated, then a "deleted" flag may be used
>  in conjunction with a per-entry spinlock in order to allow the search
>  function to reject newly deleted data.
>  

That is, should it be here?

> -
>  Answer to Quick Quiz
>  	Why does the search function need to return holding the per-entry
>  	lock for this deleted-flag technique to be helpful?
> -- 
> 2.22.0
> 

thanks,

 - Joel



More information about the Linux-kernel-mentees mailing list