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.
