Re: [PATCH] locking: Warn about state preservation when releasing and re-acquiring locks

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



New wording looks good to me.
I will come up with an example so dangerous you can stick a tail to it
and call it a wolf.

--Elad

On Thu, 6 Oct 2022 at 08:58, Paul E. McKenney <paulmck@xxxxxxxxxx> wrote:
>
> On Thu, Sep 29, 2022 at 08:11:12AM -0400, Elad Lahav wrote:
> > Signed-off-by: Elad Lahav <e2lahav@xxxxxxxxx>
>
> Thank you, Elad, and please accept my apologies for being slow.
> This is queued and pushed.
>
> I could not resist the urge to wordsmith, so could you please check
> the updated patch below?
>
> Also, longer term, would you be willing to add code that makes a
> simple but dangerous change in order to better illustrate the problem?
>
>                                                 Thanx, Paul
>
> ------------------------------------------------------------------------
>
> commit a4e1d87b97f8446dd18db11fd7c5b70633bba69c
> Author: Elad Lahav <e2lahav@xxxxxxxxx>
> Date:   Thu Sep 29 08:11:12 2022 -0400
>
>     locking: Warn about state preservation when releasing and re-acquiring locks
>
>     [ paulmck: Wordsmith. ]
>
>     Signed-off-by: Elad Lahav <e2lahav@xxxxxxxxx>
>     Signed-off-by: Paul E. McKenney <paulmck@xxxxxxxxxx>
>
> diff --git a/CodeSamples/locking/Makefile b/CodeSamples/locking/Makefile
> index 3663a7d5..cf600636 100644
> --- a/CodeSamples/locking/Makefile
> +++ b/CodeSamples/locking/Makefile
> @@ -1,4 +1,4 @@
> -ARCH_INDEPENDENT = locked_list
> +ARCH_INDEPENDENT = locked_list rec_tree_itr
>  ARCH_DEPENDENT = xchglock
>  PROGS = $(ARCH_INDEPENDENT) $(ARCH_DEPENDENT)
>
> @@ -20,5 +20,8 @@ locked_list: locked_list.c ../api.h
>  xchglock: xchglock.c ../api.h
>         cc -g -Wall -o xchglock xchglock.c -lpthread
>
> +rec_tree_itr: rec_tree_itr.c ../api.h
> +       cc -g -Wall -o rec_tree_itr rec_tree_itr.c -lpthread
> +
>  clean:
>         rm -f $(PROGS)
> diff --git a/CodeSamples/locking/rec_tree_itr.c b/CodeSamples/locking/rec_tree_itr.c
> new file mode 100644
> index 00000000..1445668c
> --- /dev/null
> +++ b/CodeSamples/locking/rec_tree_itr.c
> @@ -0,0 +1,96 @@
> +/*
> + * locked_list.c: Recursive tree iterator
> + *
> + * This program is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License as published by
> + * the Free Software Foundation; either version 2 of the License, or
> + * (at your option) any later version.
> + *
> + * This program is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> + * GNU General Public License for more details.
> + *
> + * You should have received a copy of the GNU General Public License
> + * along with this program; if not, you can access it online at
> + * http://www.gnu.org/licenses/gpl-2.0.html.
> + *
> + * Copyright (c) 2022 Elad Lahav
> + */
> +
> +#include "../api.h"
> +
> +#define MAX_CHILDREN 10
> +
> +struct node {
> +    int data;
> +       int nchildren;
> +       struct node *children[MAX_CHILDREN];
> +};
> +
> +struct tree {
> +       spinlock_t s;
> +       struct node *root;
> +};
> +
> +//\begin{snippet}[labelbase=ln:locking:rec_tree_iterator:tree_for_each,commandchars=\\\@\$]
> +void tree_for_each_rec(struct tree *tr, struct node *nd,
> +                                          void (*callback)(struct node *))
> +{
> +       spin_unlock(&tr->s);
> +       callback(nd);
> +       spin_lock(&tr->s);
> +
> +       for (int i = 0; i < nd->nchildren; i++) {
> +               tree_for_each_rec(tr, nd->children[i], callback);
> +       }
> +}
> +
> +void tree_for_each(struct tree *tr,
> +                                  void (*callback)(struct node *))
> +{
> +       spin_lock(&tr->s);
> +       tree_for_each_rec(tr, tr->root, callback);
> +       spin_unlock(&tr->s);
> +}
> +//\end{snippet}
> +
> +void print_node_data(struct node *nd)
> +{
> +    printf("%d\n", nd->data);
> +}
> +
> +int main(int argc, char *argv[])
> +{
> +    struct tree tr;
> +    struct node *nodes = calloc(sizeof(struct node), 10);
> +
> +    for (int i = 0; i < 10; i++) {
> +        nodes[i].data = 100 + i;
> +    }
> +
> +       spin_lock_init(&tr.s);
> +
> +    tr.root = &nodes[0];
> +
> +    nodes[0].nchildren = 3;
> +    nodes[0].children[0] = &nodes[1];
> +    nodes[0].children[1] = &nodes[2];
> +    nodes[0].children[2] = &nodes[3];
> +
> +    nodes[1].nchildren = 2;
> +    nodes[1].children[0] = &nodes[4];
> +    nodes[1].children[1] = &nodes[5];
> +
> +    nodes[2].nchildren = 1;
> +    nodes[2].children[0] = &nodes[6];
> +
> +    nodes[5].nchildren = 3;
> +    nodes[5].children[0] = &nodes[7];
> +    nodes[5].children[1] = &nodes[8];
> +    nodes[5].children[2] = &nodes[9];
> +
> +    tree_for_each(&tr, print_node_data);
> +
> +       return 0;
> +}
> diff --git a/locking/locking.tex b/locking/locking.tex
> index 45a12caa..32f9bad7 100644
> --- a/locking/locking.tex
> +++ b/locking/locking.tex
> @@ -375,6 +375,37 @@ deadlock is avoided if each module separately avoids deadlock.
>  This rule therefore greatly simplifies deadlock analysis and greatly
>  improves modularity.
>
> +Nevertheless, this golden rule comes with a warning.
> +When you release those locks, any state that they protect is subject
> +to arbitrary changes, changes that are all too easy for the function's
> +caller to forget, resulting in subtle and difficult-to-reproduce bugs.
> +Because the \co{qsort()} comparison function rarely acquires locks,
> +let's switch to a different example.
> +
> +Consider the recursive tree iterator in
> +\cref{lst:locking:Recursive Tree Iterator}.
> +The iterator visits every node in the tree, invoking a user's callback
> +function.
> +The tree lock is released before the invocation and re-acquired after return.
> +This code makes dangerous assumptions:
> +\begin{enumerate*}[(1)]
> +\item  The number of children of the current node has not changed,
> +\item  The ancestors stored on the stack by the recursion are still
> +       there, and
> +\item  The visited node itself has not been removed and freed.
> +\end{enumerate*}
> +One strategy is to ensure that state is preserved despite the lock being
> +released, for example, by acquiring a reference on a node to prevent it
> +from being freed.
> +Alternatively, the state can be re-initialized once the lock is
> +re-acquired after the callback function returns.
> +
> +\begin{listing}
> +\input{CodeSamples/locking/rec_tree_iterator@tree_for_each.fcv}
> +\caption{Recursive Tree Iterator}
> +\label{lst:locking:Recursive Tree Iterator}
> +\end{listing}
> +
>  \subsubsection{Layered Locking Hierarchies}
>  \label{sec:locking:Layered Locking Hierarchies}
>
> @@ -385,10 +416,9 @@ improves modularity.
>  \label{fig:locking:Layered Locking Hierarchy for qsort()}
>  \end{figure}
>
> -Unfortunately, it might not be possible for \co{qsort()} to release
> -all of its locks before invoking the comparison function.
> -In this case, we cannot construct a local locking hierarchy by
> -releasing all locks before invoking unknown code.
> +Unfortunately, it might be infeasible to preserve state on the one hand
> +or to re-initialize it on the other, thus ruling out a local locking
> +hierarchy where all locks are released before invoking unknown code.
>  However, we can instead construct a layered locking hierarchy, as shown in
>  \cref{fig:locking:Layered Locking Hierarchy for qsort()}.
>  Here, the \co{cmp()} function uses a new Lock~D that is acquired after
> @@ -1399,7 +1429,7 @@ for example:
>         that some FIFO ordering applies for threads of the same priority.
>  \item  Random, so that the new lock holder is chosen randomly from
>         all threads attempting acquisition, regardless of timing.
> -\item
> +\item
>         Unfair, so that a given acquisition might never acquire the lock
>         (see \cref{sec:locking:Unfairness}).
>  \end{enumerate}
> @@ -1486,7 +1516,7 @@ when switching from read-holder to write-holder mode.
>  Here are a few possible approaches:
>
>  \begin{enumerate}
> -\item
> +\item
>         Reader-preference implementations unconditionally favor readers
>         over writers, possibly allowing write acquisitions to be
>         indefinitely blocked.



[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Index of Archives]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]

  Powered by Linux