locking: now with more danger!
PATCH 1/1 locking: now with more danger!
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 <[email protected]>
--- CodeSamples/locking/rec_tree_itr.c | 59 +++++++++++++++++------------- locking/locking.tex | 23 ++++++++++++ 2 files changed, 56 insertions(+), 26 deletions(-)
CodeSamples/locking/rec_tree_itr.c +33 -26
@@ -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 ; }
locking/locking.tex +23 -0
@@ -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.
Signature · 1 line
2.25.1