From af0dece2774ac2f157f4ae91ab1bc4fe192d1346 Mon Sep 17 00:00:00 2001 From: Christian Thaeter Date: Wed, 18 Aug 2010 15:40:14 +0200 Subject: [PATCH] improve the 'literate' source docs for the resource tracker --- doc/resourcedeadlock.txt | 2 +- src/nobug_resources.c | 239 ++++++++++++++++++++++++----------------------- 2 files changed, 123 insertions(+), 118 deletions(-) diff --git a/doc/resourcedeadlock.txt b/doc/resourcedeadlock.txt index 249f89c..23940dc 100644 --- a/doc/resourcedeadlock.txt +++ b/doc/resourcedeadlock.txt @@ -8,5 +8,5 @@ lead to a deadlock. Deadlock detection is implemented in the Resource Tracker and active in ALPHA builds and optimized out on any other build level. For details about the deadlock detection algorithm see -xref:deadlock_detection[Appendix: Resource Tracking Alorithm]. +xref:deadlockdetection[Appendix: Resource Tracking Alorithm]. diff --git a/src/nobug_resources.c b/src/nobug_resources.c index 489f901..2681655 100644 --- a/src/nobug_resources.c +++ b/src/nobug_resources.c @@ -377,7 +377,7 @@ nobug_resource_node_new (struct nobug_resource_record* resource, #endif -//dlalgo HEAD~ The Resource Tracking Algorithm; deadlock_detection; how resources are tracked +//dlalgo HEAD- The Resource Tracking Algorithm; deadlock_detection; how resources are tracked //dlalgo //dlalgo Each resource registers a global 'resource_record'. //dlalgo @@ -407,7 +407,7 @@ nobug_resource_enter (struct nobug_resource_record* resource, struct nobug_tls_data* tls = nobug_thread_get (); - //dlalgo HEAD^ Entering Resources; nobug_resource_enter; deadlock check on enter + //dlalgo HEAD~ Entering Resources; nobug_resource_enter; deadlock check on enter //dlalgo //dlalgo In multithreaded programs, whenever a thread wants to wait for a 'resource_record' //dlalgo the deadlock checker jumps in. @@ -440,31 +440,31 @@ nobug_resource_enter (struct nobug_resource_record* resource, //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- - struct nobug_resource_user* user = NULL; //dlalgo VERBATIM - struct nobug_resource_node* node = NULL; //dlalgo VERBATIM - //dlalgo VERBATIM - if (!llist_is_empty (&tls->res_stack)) //dlalgo VERBATIM - { //dlalgo VERBATIM - user = LLIST_TO_STRUCTP (llist_tail (&tls->res_stack), //dlalgo VERBATIM - struct nobug_resource_user, //dlalgo VERBATIM - res_stack); //dlalgo VERBATIM - //dlalgo VERBATIM - struct nobug_resource_node templ = //dlalgo VERBATIM - { //dlalgo VERBATIM - {NULL, NULL}, //dlalgo ... - user->current->resource, //dlalgo VERBATIM - NULL, //dlalgo ... + struct nobug_resource_user* user = NULL; //dlalgo VERBATIM @ + struct nobug_resource_node* node = NULL; //dlalgo VERBATIM @ + //dlalgo VERBATIM @ + if (!llist_is_empty (&tls->res_stack)) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + user = LLIST_TO_STRUCTP (llist_tail (&tls->res_stack), //dlalgo VERBATIM @ + struct nobug_resource_user, //dlalgo VERBATIM @ + res_stack); //dlalgo VERBATIM @ + //dlalgo VERBATIM @ + struct nobug_resource_node templ = //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + {NULL, NULL}, //dlalgo ... + user->current->resource, //dlalgo VERBATIM @ + NULL, //dlalgo ... {NULL, NULL}, {NULL, NULL} - }; //dlalgo VERBATIM - //dlalgo VERBATIM - node = (struct nobug_resource_node*) //dlalgo VERBATIM - llist_ufind (&resource->nodes, //dlalgo VERBATIM - &templ.node, //dlalgo VERBATIM - nobug_resource_node_resource_cmpfn, //dlalgo VERBATIM - NULL); //dlalgo VERBATIM - } //dlalgo VERBATIM - //dlalgo ... + }; //dlalgo VERBATIM @ + //dlalgo VERBATIM @ + node = (struct nobug_resource_node*) //dlalgo VERBATIM @ + llist_ufind (&resource->nodes, //dlalgo VERBATIM @ + &templ.node, //dlalgo VERBATIM @ + nobug_resource_node_resource_cmpfn, //dlalgo VERBATIM @ + NULL); //dlalgo VERBATIM @ + } //dlalgo VERBATIM @ + //dlalgo ... //dlalgo --------------------------------------------------------------------- //dlalgo #endif @@ -474,10 +474,10 @@ nobug_resource_enter (struct nobug_resource_record* resource, //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- - if (state == NOBUG_RESOURCE_WAITING) //dlalgo VERBATIM - { //dlalgo VERBATIM -#if NOBUG_USE_PTHREAD //dlalgo VERBATIM - //dlalgo ... + if (state == NOBUG_RESOURCE_WAITING) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ +#if NOBUG_USE_PTHREAD //dlalgo VERBATIM @ + //dlalgo ... //dlalgo --------------------------------------------------------------------- //dlalgo @@ -486,9 +486,9 @@ nobug_resource_enter (struct nobug_resource_record* resource, //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- - if (!node && user) //dlalgo VERBATIM - { //dlalgo VERBATIM - //dlalgo ... + if (!node && user) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + //dlalgo ... //dlalgo --------------------------------------------------------------------- //dlalgo //dlalgo If not then its checked that the resource to be entered is not on any parent trail of the current topmost resource, @@ -496,16 +496,16 @@ nobug_resource_enter (struct nobug_resource_record* resource, //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- - LLIST_FOREACH (&user->current->resource->nodes, n) //dlalgo VERBATIM - { //dlalgo VERBATIM - for (struct nobug_resource_node* itr = //dlalgo VERBATIM - ((struct nobug_resource_node*)n)->parent; //dlalgo VERBATIM - itr; //dlalgo VERBATIM - itr = itr->parent) //dlalgo VERBATIM - { //dlalgo VERBATIM - if (itr->resource == resource) //dlalgo VERBATIM - { //dlalgo VERBATIM - //dlalgo ... + LLIST_FOREACH (&user->current->resource->nodes, n) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + for (struct nobug_resource_node* itr = //dlalgo VERBATIM @ + ((struct nobug_resource_node*)n)->parent; //dlalgo VERBATIM @ + itr; //dlalgo VERBATIM @ + itr = itr->parent) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + if (itr->resource == resource) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + //dlalgo ... //dlalgo --------------------------------------------------------------------- //dlalgo //dlalgo if the resource was on the trail, we search if there is a common ancestor before the resource @@ -514,28 +514,28 @@ nobug_resource_enter (struct nobug_resource_record* resource, //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- - for (struct nobug_resource_node* itr2 = itr->parent; //dlalgo VERBATIM - itr2; //dlalgo VERBATIM - itr2 = itr2->parent) //dlalgo VERBATIM - { //dlalgo VERBATIM - LLIST_FOREACH_REV (&tls->res_stack, p) //dlalgo VERBATIM - { //dlalgo VERBATIM - struct nobug_resource_user* user = //dlalgo VERBATIM - LLIST_TO_STRUCTP (p, //dlalgo VERBATIM - struct nobug_resource_user, //dlalgo VERBATIM - res_stack); //dlalgo VERBATIM - if (user->current->resource == itr2->resource) //dlalgo VERBATIM - goto done; //dlalgo VERBATIM - } //dlalgo VERBATIM + for (struct nobug_resource_node* itr2 = itr->parent; //dlalgo VERBATIM @ + itr2; //dlalgo VERBATIM @ + itr2 = itr2->parent) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + LLIST_FOREACH_REV (&tls->res_stack, p) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + struct nobug_resource_user* user = //dlalgo VERBATIM @ + LLIST_TO_STRUCTP (p, //dlalgo VERBATIM @ + struct nobug_resource_user, //dlalgo VERBATIM @ + res_stack); //dlalgo VERBATIM @ + if (user->current->resource == itr2->resource) //dlalgo VERBATIM @ + goto done; //dlalgo VERBATIM @ + } //dlalgo VERBATIM @ + //dlalgo ... //dlalgo --------------------------------------------------------------------- //dlalgo //dlalgo If no ancestor found, we finally abort with a potential deadlock condition. //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- - nobug_resource_error = "possible deadlock detected"; //dlalgo VERBATIM - return NULL; //dlalgo VERBATIM - //dlalgo ... + nobug_resource_error = "possible deadlock detected"; //dlalgo VERBATIM @ + return NULL; //dlalgo VERBATIM @ //dlalgo --------------------------------------------------------------------- //dlalgo } @@ -676,22 +676,23 @@ nobug_resource_leave (struct nobug_resource_user* user) else { //dlalgo - //dlalgo HEAD^ Leaving Resources; nobug_resource_leave; fix resource lists + //dlalgo HEAD~ Leaving Resources; nobug_resource_leave; fix resource lists //dlalgo //dlalgo store the tail and next aside, we need it later //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- -#if NOBUG_USE_PTHREAD //dlalgo VERBATIM - struct nobug_resource_user* tail = //dlalgo VERBATIM - LLIST_TO_STRUCTP (llist_tail (&user->thread->res_stack), //dlalgo VERBATIM - struct nobug_resource_user, //dlalgo VERBATIM - res_stack); //dlalgo VERBATIM - - struct nobug_resource_user* next = //dlalgo VERBATIM - LLIST_TO_STRUCTP (llist_next (&user->res_stack), //dlalgo VERBATIM - struct nobug_resource_user, //dlalgo VERBATIM - res_stack); //dlalgo VERBATIM +#if NOBUG_USE_PTHREAD //dlalgo VERBATIM @ + struct nobug_resource_user* tail = //dlalgo VERBATIM @ + LLIST_TO_STRUCTP (llist_tail (&user->thread->res_stack), //dlalgo VERBATIM @ + struct nobug_resource_user, //dlalgo VERBATIM @ + res_stack); //dlalgo VERBATIM @ + + struct nobug_resource_user* next = //dlalgo VERBATIM @ + LLIST_TO_STRUCTP (llist_next (&user->res_stack), //dlalgo VERBATIM @ + struct nobug_resource_user, //dlalgo VERBATIM @ + res_stack); //dlalgo VERBATIM @ + //dlalgo ... //dlalgo --------------------------------------------------------------------- //dlalgo //dlalgo remove user struct from thread stack @@ -700,7 +701,8 @@ nobug_resource_leave (struct nobug_resource_user* user) //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- - llist_unlink_fast_ (&user->res_stack); //dlalgo VERBATIM + llist_unlink_fast_ (&user->res_stack); //dlalgo VERBATIM @ + //dlalgo ... //dlalgo --------------------------------------------------------------------- //dlalgo //dlalgo When the the user node was not the tail or only node of the thread stack, we have to check @@ -709,16 +711,17 @@ nobug_resource_leave (struct nobug_resource_user* user) //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- - if (user != tail && !llist_is_empty (&user->thread->res_stack)) //dlalgo VERBATIM - { //dlalgo VERBATIM - struct nobug_resource_user* parent = NULL; //dlalgo VERBATIM - if (llist_head (&user->thread->res_stack) != &next->res_stack) //dlalgo VERBATIM - { //dlalgo VERBATIM - parent = //dlalgo VERBATIM - LLIST_TO_STRUCTP (llist_prev (&next->res_stack), //dlalgo VERBATIM - struct nobug_resource_user, //dlalgo VERBATIM - res_stack); //dlalgo VERBATIM - } //dlalgo VERBATIM + if (user != tail && !llist_is_empty (&user->thread->res_stack)) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + struct nobug_resource_user* parent = NULL; //dlalgo VERBATIM @ + if (llist_head (&user->thread->res_stack)!= &next->res_stack) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + parent = //dlalgo VERBATIM @ + LLIST_TO_STRUCTP (llist_prev (&next->res_stack), //dlalgo VERBATIM @ + struct nobug_resource_user, //dlalgo VERBATIM @ + res_stack); //dlalgo VERBATIM @ + } //dlalgo VERBATIM @ + //dlalgo ... //dlalgo --------------------------------------------------------------------- //dlalgo //dlalgo iterate over all users following the removed node, finding nodes pointing to this users or @@ -726,15 +729,16 @@ nobug_resource_leave (struct nobug_resource_user* user) //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- - LLIST_FORRANGE (&next->res_stack, &user->thread->res_stack, n) //dlalgo VERBATIM - { //dlalgo VERBATIM - struct nobug_resource_user* cur = //dlalgo VERBATIM - LLIST_TO_STRUCTP (n, //dlalgo VERBATIM - struct nobug_resource_user, //dlalgo VERBATIM - res_stack); //dlalgo VERBATIM - //dlalgo VERBATIM - struct nobug_resource_record* resource = cur->current->resource; - + LLIST_FORRANGE (&next->res_stack, &user->thread->res_stack, n) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + struct nobug_resource_user* cur = //dlalgo VERBATIM @ + LLIST_TO_STRUCTP (n, //dlalgo VERBATIM @ + struct nobug_resource_user, //dlalgo VERBATIM @ + res_stack); //dlalgo VERBATIM @ + //dlalgo VERBATIM @ + struct nobug_resource_record* resource = //dlalgo VERBATIM @ + cur->current->resource; //dlalgo VERBATIM @ + //dlalgo ... //dlalgo --------------------------------------------------------------------- //TODO this search could be optimized out after we creates a node once, //TODO all following nodes need to be created too @@ -743,36 +747,37 @@ nobug_resource_leave (struct nobug_resource_user* user) //dlalgo //dlalgo [source,c] //dlalgo --------------------------------------------------------------------- - struct nobug_resource_node templ = //dlalgo VERBATIM - { //dlalgo VERBATIM - {NULL, NULL}, //dlalgo ... - NULL, //dlalgo VERBATIM - parent?parent->current:NULL, //dlalgo ... + struct nobug_resource_node templ = //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ {NULL, NULL}, + NULL, //dlalgo ... + parent?parent->current:NULL, //dlalgo VERBATIM @ + {NULL, NULL}, //dlalgo ... {NULL, NULL} - }; //dlalgo VERBATIM - //dlalgo VERBATIM - struct nobug_resource_node* node = (struct nobug_resource_node*) //dlalgo VERBATIM - llist_ufind (&resource->nodes, //dlalgo VERBATIM - &templ.node, //dlalgo VERBATIM - nobug_resource_node_parent_cmpfn, //dlalgo VERBATIM - NULL); //dlalgo VERBATIM - //dlalgo VERBATIM - if (!node) //dlalgo VERBATIM - { //dlalgo VERBATIM - node = nobug_resource_node_new (resource, //dlalgo VERBATIM - parent?parent->current:NULL); //dlalgo VERBATIM - if (!node) //dlalgo VERBATIM - { //dlalgo VERBATIM - nobug_resource_error = "internal allocation error"; //dlalgo VERBATIM - return 0; //dlalgo VERBATIM - } //dlalgo VERBATIM - } //dlalgo VERBATIM - //dlalgo VERBATIM - parent = cur; //dlalgo VERBATIM - } //dlalgo VERBATIM - } //dlalgo VERBATIM - //dlalgo --------------------------------------------------------------------- + }; //dlalgo VERBATIM @ + //dlalgo VERBATIM @ + struct nobug_resource_node* node = //dlalgo VERBATIM @ + (struct nobug_resource_node*) //dlalgo VERBATIM @ + llist_ufind (&resource->nodes, //dlalgo VERBATIM @ + &templ.node, //dlalgo VERBATIM @ + nobug_resource_node_parent_cmpfn, //dlalgo VERBATIM @ + NULL); //dlalgo VERBATIM @ + //dlalgo VERBATIM @ + if (!node) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + node = nobug_resource_node_new (resource, //dlalgo VERBATIM @ + parent?parent->current:NULL); //dlalgo VERBATIM @ + if (!node) //dlalgo VERBATIM @ + { //dlalgo VERBATIM @ + nobug_resource_error = "internal allocation error"; //dlalgo VERBATIM @ + return 0; //dlalgo VERBATIM @ + } //dlalgo VERBATIM @ + } //dlalgo VERBATIM @ + //dlalgo VERBATIM @ + parent = cur; //dlalgo VERBATIM @ + //dlalgo --------------------------------------------------------------------- + } + } //dlalgo #endif -- 2.11.4.GIT