On Thu, Oct 06, 2022 at 01:53:54PM -0400, Elad Lahav wrote: > 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. Now -that- sounds like my kind of example! Thank you! Thanx, Paul > --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.
