Add an example to demonstrate how an assumption about the tree can be
invalidated by releasing and then re-acquiring a lock.
Signed-off-by: Elad Lahav <e2lahav@xxxxxxxxx>
---
CodeSamples/locking/rec_tree_itr.c | 59 +++++++++++++++++-------------
locking/locking.tex | 23 ++++++++++++
2 files changed, 56 insertions(+), 26 deletions(-)
diff --git a/CodeSamples/locking/rec_tree_itr.c b/CodeSamples/locking/rec_tree_itr.c
index 1445668c..d091e4cc 100644
--- a/CodeSamples/locking/rec_tree_itr.c
+++ b/CodeSamples/locking/rec_tree_itr.c
@@ -20,12 +20,10 @@
#include "../api.h"
-#define MAX_CHILDREN 10
-
struct node {
- int data;
+ int data;
int nchildren;
- struct node *children[MAX_CHILDREN];
+ struct node **children;
};
struct tree {
@@ -41,8 +39,10 @@ void tree_for_each_rec(struct tree *tr, struct node *nd,
callback(nd);
spin_lock(&tr->s);
+ struct node **itr = nd->children;
for (int i = 0; i < nd->nchildren; i++) {
- tree_for_each_rec(tr, nd->children[i], callback);
+ tree_for_each_rec(tr, *itr, callback);
+ itr++;
}
}
@@ -53,44 +53,51 @@ void tree_for_each(struct tree *tr,
tree_for_each_rec(tr, tr->root, callback);
spin_unlock(&tr->s);
}
+
+void tree_add(struct tree *tr, struct node *parent,
+ struct node *new_child)
+{
+ spin_lock(&tr->s);
+ parent->nchildren++;
+ parent->children = realloc(parent->children,
+ sizeof(struct node *) * parent->nchildren);
+ parent->children[parent->nchildren - 1] = new_child;
+ spin_unlock(&tr->s);
+}
//\end{snippet}
void print_node_data(struct node *nd)
{
- printf("%d\n", nd->data);
+ printf("%d\n", nd->data);
}
int main(int argc, char *argv[])
{
- struct tree tr;
- struct node *nodes = calloc(sizeof(struct node), 10);
+ struct tree tr;
+ struct node *nodes = calloc(sizeof(struct node), 10);
- for (int i = 0; i < 10; i++) {
- nodes[i].data = 100 + i;
- }
+ for (int i = 0; i < 10; i++) {
+ nodes[i].data = 100 + i;
+ }
spin_lock_init(&tr.s);
- tr.root = &nodes[0];
+ 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];
+ tree_add(&tr, &nodes[0], &nodes[1]);
+ tree_add(&tr, &nodes[0], &nodes[2]);
+ tree_add(&tr, &nodes[0], &nodes[3]);
- nodes[1].nchildren = 2;
- nodes[1].children[0] = &nodes[4];
- nodes[1].children[1] = &nodes[5];
+ tree_add(&tr, &nodes[1], &nodes[4]);
+ tree_add(&tr, &nodes[1], &nodes[5]);
- nodes[2].nchildren = 1;
- nodes[2].children[0] = &nodes[6];
+ tree_add(&tr, &nodes[2], &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_add(&tr, &nodes[3], &nodes[7]);
+ tree_add(&tr, &nodes[3], &nodes[8]);
+ tree_add(&tr, &nodes[3], &nodes[9]);
- tree_for_each(&tr, print_node_data);
+ tree_for_each(&tr, print_node_data);
return 0;
}
diff --git a/locking/locking.tex b/locking/locking.tex
index b138cd59..7f2a8c5b 100644
--- a/locking/locking.tex
+++ b/locking/locking.tex
@@ -394,6 +394,29 @@ This code makes dangerous assumptions:
there, and
\item The visited node itself has not been removed and freed.
\end{enumerate*}
+A few of these hazards can be encountered if one thread calls
+\co{tree_add()} while another thread releases the tree's lock to run a
+callback function.
+
+\QuickQuiz{
+ So the iterating thread may or may not observe the added child.
+ What's the big deal?
+}\QuickQuizAnswer{
+ There are (at least) two hazards in this situation.
+
+ One is indeed that the number of children may or may not be
+ observed to have changed.
+ While that would be consistent with \co{tree_add()} being called
+ either before or after the iterator started, it is better not
+ left to the vagaries of the compiler.
+ A more serious problem is that \co{realloc()} may not be able
+ to extend the array in place, causing the heap to free the
+ one used by the iterator and replace it with another block of
+ memory.
+ If the \co{children} pointer is not re-read then the iterating
+ thread will access the wrong memory (either free or reclaimed).
+}\QuickQuizEnd
+
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.
--
2.25.1
