src/nobug_resources.c

   1 /*
   2  This file is part of the NoBug debugging library.
   3
   4  Copyright (C) 2007, 2008, 2009, Christian Thaeter <ct@pipapo.org>
   5
   6  This program is free software; you can redistribute it and/or modify
   7  it under the terms of the GNU General Public License as published by
   8  the Free Software Foundation; either version 2 of the License, or
   9  (at your option) any later version.
  10
  11  This program is distributed in the hope that it will be useful,
  12  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  GNU General Public License for more details.
  15
  16  You should have received a copy of the GNU General Public License
  17  along with this program; if not, contact Christian Thaeter <ct@pipapo.org>.
  18 */
  19 #include <stdlib.h>
  20
  21 #define NOBUG_LIBNOBUG_C
  22 #include "nobug.h"
  23 #include "llist.h"
  24 #include "mpool.h"
  25
  26 /*
  27 //deadlock There are 2 kinds of nodes: `resource_record` hold registered resources and `resource_user` which
  28 //deadlock attach to (enter) a resource.
  29 //deadlock
  30 //deadlock Each thread keeps stacklist of each `resource_user` it created, new enters will push on the stack,
  31 //deadlock leaving a resource will remove it from this stacklist.
  32 //deadlock
  33 //deadlock All `resource_records` in use are linked in a global precedence list, items of equal precedence are
  34 //deadlock spaned by a skip pointer. Whenever a resource is entered the deadlock checker asserts that one does
  35 //deadlock not break existing precedences. By doing so the precedence list gets continously refined as the system
  36 //deadlock learns about new lock patterns.
  37 //deadlock
  38 //deadlock As a consequence of this algorithm the deadlock checker does not only find real deadlocks but
  39 //deadlock already potential deadlocks by violations of the locking order which is a lot simpler than finding
  40 //deadlock actual deadlocks.
  41 //deadlock
  42 //deadlock This also means that the deadlock tracker currently only works with hierarchical locking policies
  43 //deadlock other approaches to prevent deadlocks are not yet supported and will be added on demand.
  44 //deadlock
  45 //deadlock
  46 //deadlock
  47 */
  48
  49 /*
  50   How much memory to reserve for a mpool chunk, 16k by default
  51  */
  52 #ifndef NOBUG_RESOURCE_MPOOL_CHUNKSIZE
  53 #define NOBUG_RESOURCE_MPOOL_CHUNKSIZE (4096<<(sizeof(void*)/4))        /* That is roughly 8k chunks on 32bit, 16k chunks on 64 bit machines */
  54 #endif
  55
  56 #if NOBUG_USE_PTHREAD
  57 pthread_mutex_t nobug_resource_mutex = PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP;
  58 #endif
  59
  60 #define nobug_resourcestates    \
  61   resource_state(invalid),      \
  62   resource_state(waiting),      \
  63   resource_state(exclusive),    \
  64   resource_state(recursive),    \
  65   resource_state(shared),
  66
  67
  68 #define resource_state(name) #name
  69 const char* nobug_resource_states[] =
  70   {
  71     nobug_resourcestates
  72     NULL
  73   };
  74 #undef resource_state
  75
  76 const char* nobug_resource_error = NULL;
  77
  78 static llist nobug_resource_registry;
  79 static mpool nobug_resource_record_pool;
  80 static mpool nobug_resource_user_pool;
  81 #if NOBUG_USE_PTHREAD
  82 static mpool nobug_resource_node_pool;
  83 #endif
  84
  85 static void nobug_resource_record_dtor (void*);
  86 static void nobug_resource_user_dtor (void*);
  87 #if NOBUG_USE_PTHREAD
  88 static void nobug_resource_node_dtor (void*);
  89 #endif
  90
  91
  92 void
  93 nobug_resource_init (void)
  94 {
  95   llist_init (&nobug_resource_registry);
  96
  97   mpool_init (&nobug_resource_record_pool,
  98               sizeof(struct nobug_resource_record),
  99               NOBUG_RESOURCE_MPOOL_CHUNKSIZE/sizeof(struct nobug_resource_record),
 100               nobug_resource_record_dtor);
 101
 102   mpool_init (&nobug_resource_user_pool,
 103               sizeof(struct nobug_resource_user),
 104               NOBUG_RESOURCE_MPOOL_CHUNKSIZE/sizeof(struct nobug_resource_user),
 105               nobug_resource_user_dtor);
 106
 107 #if NOBUG_USE_PTHREAD
 108   mpool_init (&nobug_resource_node_pool,
 109               sizeof(struct nobug_resource_node),
 110               NOBUG_RESOURCE_MPOOL_CHUNKSIZE/sizeof(struct nobug_resource_node),
 111               nobug_resource_node_dtor);
 112 #endif
 113 }
 114
 115
 116 void
 117 nobug_resource_destroy (void)
 118 {
 119 #if NOBUG_USE_PTHREAD
 120   mpool_destroy (&nobug_resource_node_pool);
 121 #endif
 122   mpool_destroy (&nobug_resource_user_pool);
 123   mpool_destroy (&nobug_resource_record_pool);
 124 }
 125
 126
 127 unsigned
 128 nobug_resource_record_available (void)
 129 {
 130   return mpool_available (&nobug_resource_record_pool);
 131 }
 132
 133
 134 unsigned
 135 nobug_resource_user_available (void)
 136 {
 137   return mpool_available (&nobug_resource_user_pool);
 138 }
 139
 140
 141 #if NOBUG_USE_PTHREAD
 142 unsigned
 143 nobug_resource_node_available (void)
 144 {
 145   return mpool_available (&nobug_resource_node_pool);
 146 }
 147
 148
 149 static void
 150 nobug_resource_node_free (struct nobug_resource_node* self)
 151 {
 152   LLIST_WHILE_HEAD (&self->childs, c)
 153     nobug_resource_node_free (LLIST_TO_STRUCTP(c, struct nobug_resource_node, cldnode));
 154
 155   llist_unlink_fast_ (&self->cldnode);
 156   llist_unlink_fast_ (&self->node);
 157   mpool_free (&nobug_resource_node_pool, self);
 158 }
 159
 160
 161 static void
 162 nobug_resource_node_dtor (void* p)
 163 {
 164   struct nobug_resource_node* n = p;
 165   llist_unlink_fast_ (&n->node);
 166   /* must unlink childs, because we don't destroy the tree bottom up */
 167   llist_unlink_fast_ (&n->childs);
 168   llist_unlink_fast_ (&n->cldnode);
 169 }
 170 #endif
 171
 172
 173 static void
 174 nobug_resource_record_dtor (void* p)
 175 {
 176   struct nobug_resource_record* self= p;
 177   llist_unlink_fast_ (&self->hdr.node);
 178
 179 #if NOBUG_USE_PTHREAD
 180   /* destroy all nodes recursively */
 181   LLIST_WHILE_HEAD (&self->nodes, n)
 182     nobug_resource_node_free ((struct nobug_resource_node*)n);
 183 #endif
 184 }
 185
 186
 187 static void
 188 nobug_resource_user_dtor (void* p)
 189 {
 190   struct nobug_resource_user* u = p;
 191   llist_unlink_fast_ (&u->hdr.node);
 192 #if NOBUG_USE_PTHREAD
 193   llist_unlink_fast_ (&u->res_stack);
 194 #endif
 195 }
 196
 197
 198 static int
 199 compare_resource_records (const_LList av, const_LList bv, void* unused)
 200 {
 201   (void) unused;
 202   const struct nobug_resource_record* a = (const struct nobug_resource_record*)av;
 203   const struct nobug_resource_record* b = (const struct nobug_resource_record*)bv;
 204
 205   return a->object_id > b->object_id ? 1 : a->object_id < b->object_id ? -1 : 0;
 206 }
 207
 208
 209 struct nobug_resource_record*
 210 nobug_resource_announce (const char* type, const char* name, const void* object_id, const char* extra)
 211 {
 212
 213   struct nobug_resource_record* node = mpool_alloc (&nobug_resource_record_pool);
 214   if (!node)
 215     {
 216       nobug_resource_error = "internal allocation error";
 217       return NULL;
 218     }
 219
 220   node->hdr.name = name;
 221   node->object_id = object_id;
 222   node->type = type;
 223
 224   /* TODO better lookup method than list search (psplay?) */
 225   if (llist_ufind (&nobug_resource_registry, &node->hdr.node, compare_resource_records, NULL))
 226     {
 227       nobug_resource_error = "already registered";
 228       return NULL;
 229     }
 230
 231   llist_init (&node->users);
 232   node->hdr.extra = extra;
 233 #if NOBUG_USE_PTHREAD
 234   llist_init (&node->nodes);
 235 #endif
 236
 237   llist_insert_head (&nobug_resource_registry, llist_init (&node->hdr.node));
 238
 239   return node;
 240 }
 241
 242
 243 int
 244 nobug_resource_forget (struct nobug_resource_record* self)
 245 {
 246   if (!llist_find (&nobug_resource_registry, &self->hdr.node, compare_resource_records, NULL))
 247     {
 248       nobug_resource_error = "not registered";
 249       return 0;
 250     }
 251
 252   if (!llist_is_empty (&self->users))
 253     {
 254       nobug_resource_error = "still in use";
 255       return 0;
 256     }
 257
 258   nobug_resource_record_dtor (self);
 259
 260   mpool_free (&nobug_resource_record_pool, self);
 261   return 1;
 262 }
 263
 264
 265 #if NOBUG_USE_PTHREAD
 266 static int
 267 nobug_resource_node_resource_cmpfn (const_LList a, const_LList b, void* extra)
 268 {
 269   (void) extra;
 270   return ((struct nobug_resource_node*)a)->resource ==
 271     ((struct nobug_resource_node*)b)->resource?0:-1;
 272 }
 273
 274
 275 struct nobug_resource_node*
 276 nobug_resource_node_new (struct nobug_resource_record* resource,
 277                          struct nobug_resource_node* parent)
 278 {
 279   struct nobug_resource_node* self = mpool_alloc (&nobug_resource_node_pool);
 280   if (self)
 281     {
 282       llist_insert_head (&resource->nodes, llist_init (&self->node));
 283       self->resource = resource;
 284
 285       self->parent = parent;
 286
 287       llist_init (&self->childs);
 288       llist_init (&self->cldnode);
 289       if (parent)
 290         llist_insert_head (&parent->childs, &self->cldnode);
 291     }
 292   return self;
 293 }
 294 #endif
 295
 296
 297 //dlalgo HEAD~ The Resource Tracking Algorithm; deadlock_detection; how resources are tracked
 298 //dlalgo
 299 //dlalgo Each resource registers a global 'resource_record'.
 300 //dlalgo
 301 //dlalgo Every new locking path discovered is stored as 'resource_node' structures which refer to the associated
 302 //dlalgo 'resource_record'.
 303 //dlalgo
 304 //dlalgo Threads keep a trail of 'resource_user' strcutures for each resource entered. This 'resource_user' struct
 305 //dlalgo refer to the 'resource_nodes' and thus indirectly to the associated 'resource_record'.
 306 //dlalgo
 307 //dlalgo The deadlock checker uses this information to test if the acqusition of a new resource would yield a
 308 //dlalgo potential deadlock.
 309 //dlalgo
 310 struct nobug_resource_user*
 311 nobug_resource_enter (struct nobug_resource_record* resource,
 312                       const char* identifier,
 313                       enum nobug_resource_state state,
 314                       const char* extra)
 315 {
 316   if (!resource)
 317     {
 318       nobug_resource_error = "no resource";
 319       return NULL;
 320     }
 321
 322 #if NOBUG_USE_PTHREAD
 323   struct nobug_tls_data* tls = nobug_thread_get ();
 324
 325   //dlalgo HEAD^ Entering Resources; nobug_resource_enter; deadlock check on enter
 326   //dlalgo
 327   //dlalgo In multithreaded programs, whenever a thread wants to wait for a 'resource_record'
 328   //dlalgo the deadlock checker jumps in.
 329   //dlalgo
 330   //dlalgo The deadlock checking algorithm is anticipatory as it will find and abort on conditions which may lead
 331   //dlalgo to a potential deadlock by violating the locking order learned earlier.
 332   //dlalgo
 333   //dlalgo Each thread holds a stack (list) of each 'resource_user' it created. Leaving
 334   //dlalgo a resource will remove it from this stacklist.
 335   //dlalgo
 336   //dlalgo Each 'resource_record' stores the trail which other 'resource_records' are already entered. This relations
 337   //dlalgo are implemented with the 'resource_node' helper structure.
 338   //dlalgo
 339   //dlalgo ////
 340   //dlalgo TODO: insert diagram here
 341   //dlalgo   2-3
 342   //dlalgo 1
 343   //dlalgo   3-4-2
 344   //dlalgo
 345   //dlalgo 1-3-2-4
 346   //dlalgo
 347   //dlalgo 3-4-2
 348   //dlalgo
 349   //dlalgo 1-4-2
 350   //dlalgo
 351   //dlalgo ////
 352   //dlalgo
 353   //dlalgo First we find out if there is already a node from the to be acquired resource back to
 354   //dlalgo the topmost node of the current threads user stack.
 355   //dlalgo
 356   //dlalgo [source,c]
 357   //dlalgo ---------------------------------------------------------------------
 358   struct nobug_resource_user* user = NULL;                      //dlalgo VERBATIM
 359   struct nobug_resource_node* node = NULL;                      //dlalgo VERBATIM
 360                                                                 //dlalgo VERBATIM
 361   if (!llist_is_empty (&tls->res_stack))                        //dlalgo VERBATIM
 362     {                                                           //dlalgo VERBATIM
 363       user = LLIST_TO_STRUCTP (llist_tail (&tls->res_stack),    //dlalgo VERBATIM
 364                                struct nobug_resource_user,      //dlalgo VERBATIM
 365                                res_stack);                      //dlalgo VERBATIM
 366                                                                 //dlalgo VERBATIM
 367       struct nobug_resource_node templ =                        //dlalgo VERBATIM
 368         {                                                       //dlalgo VERBATIM
 369           {NULL, NULL},                                         //dlalgo          ...
 370           user->current->resource,                              //dlalgo VERBATIM
 371           NULL,                                                 //dlalgo          ...
 372           {NULL, NULL},
 373           {NULL, NULL}
 374         };                                                      //dlalgo VERBATIM
 375                                                                 //dlalgo VERBATIM
 376       node = (struct nobug_resource_node*)                      //dlalgo VERBATIM
 377         llist_ufind (&resource->nodes,                          //dlalgo VERBATIM
 378                      &templ.node,                               //dlalgo VERBATIM
 379                      nobug_resource_node_resource_cmpfn,        //dlalgo VERBATIM
 380                      NULL);                                     //dlalgo VERBATIM
 381     }                                                           //dlalgo VERBATIM
 382   //dlalgo   ...
 383   //dlalgo ---------------------------------------------------------------------
 384   //dlalgo
 385 #endif
 386
 387   //dlalgo Deadlock checking is only done when the node is entered in `WAITING` state and only
 388   //dlalgo available in multithreaded programs.
 389   //dlalgo
 390   //dlalgo [source,c]
 391   //dlalgo ---------------------------------------------------------------------
 392   if (state == NOBUG_RESOURCE_WAITING)                          //dlalgo VERBATIM
 393     {                                                           //dlalgo VERBATIM
 394 #if NOBUG_USE_PTHREAD                                           //dlalgo VERBATIM
 395       //dlalgo       ...
 396       //dlalgo ---------------------------------------------------------------------
 397       //dlalgo
 398
 399       //dlalgo If node was found above, then this locking path is already validated and no deadlock can happen,
 400       //dlalgo else, if this stack already holds a resource (user is set) we have to go on with checking.
 401       //dlalgo
 402       //dlalgo [source,c]
 403       //dlalgo ---------------------------------------------------------------------
 404       if (!node && user)                                                //dlalgo VERBATIM
 405         {                                                               //dlalgo VERBATIM
 406           //dlalgo           ...
 407           //dlalgo ---------------------------------------------------------------------
 408           //dlalgo
 409           //dlalgo If not then its checked that the resource to be entered is not on any parent trail of the current topmost resource,
 410           //dlalgo if it is then this could be a deadlock which needs to be further investigated.
 411           //dlalgo
 412           //dlalgo [source,c]
 413           //dlalgo ---------------------------------------------------------------------
 414           LLIST_FOREACH (&user->current->resource->nodes, n)            //dlalgo VERBATIM
 415             {                                                           //dlalgo VERBATIM
 416               for (struct nobug_resource_node* itr =                    //dlalgo VERBATIM
 417                      ((struct nobug_resource_node*)n)->parent;          //dlalgo VERBATIM
 418                    itr;                                                 //dlalgo VERBATIM
 419                    itr = itr->parent)                                   //dlalgo VERBATIM
 420                 {                                                       //dlalgo VERBATIM
 421                   if (itr->resource == resource)                        //dlalgo VERBATIM
 422                     {                                                   //dlalgo VERBATIM
 423                       //dlalgo                       ...
 424                       //dlalgo ---------------------------------------------------------------------
 425                       //dlalgo
 426                       //dlalgo if the resource was on the trail, we search if there is a common ancestor before the resource
 427                       //dlalgo on the trail and the threads current chain,
 428                       //dlalgo if yes then this ancestor protects against deadlocks and we can continue.
 429                       //dlalgo
 430                       //dlalgo [source,c]
 431                       //dlalgo ---------------------------------------------------------------------
 432                       for (struct nobug_resource_node* itr2 = itr->parent;              //dlalgo VERBATIM
 433                            itr2;                                                        //dlalgo VERBATIM
 434                            itr2 = itr2->parent)                                         //dlalgo VERBATIM
 435                         {                                                               //dlalgo VERBATIM
 436                           LLIST_FOREACH_REV (&tls->res_stack, p)                        //dlalgo VERBATIM
 437                             {                                                           //dlalgo VERBATIM
 438                               struct nobug_resource_user* user =                        //dlalgo VERBATIM
 439                                 LLIST_TO_STRUCTP (p,                                    //dlalgo VERBATIM
 440                                                   struct nobug_resource_user,           //dlalgo VERBATIM
 441                                                   res_stack);                           //dlalgo VERBATIM
 442                               if (user->current->resource == itr2->resource)            //dlalgo VERBATIM
 443                                 goto done;                                              //dlalgo VERBATIM
 444                             }                                                           //dlalgo VERBATIM
 445                           //dlalgo ---------------------------------------------------------------------
 446                           //dlalgo
 447                           //dlalgo If no ancestor found, we finally abort with a potential deadlock condition.
 448                           //dlalgo
 449                           //dlalgo [source,c]
 450                           //dlalgo ---------------------------------------------------------------------
 451                           nobug_resource_error = "possible deadlock detected";          //dlalgo VERBATIM
 452                           return NULL;                                                  //dlalgo VERBATIM
 453                           //dlalgo                           ...
 454                           //dlalgo ---------------------------------------------------------------------
 455                           //dlalgo
 456                         }
 457                     }
 458                 }
 459             }
 460         }
 461     done:;
 462 #endif
 463     }
 464   else if (state == NOBUG_RESOURCE_EXCLUSIVE)
 465     {
 466       /* check that everyone is waiting */
 467       LLIST_FOREACH (&resource->users, n)
 468         if (((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_WAITING)
 469           {
 470             nobug_resource_error = "invalid enter state (resource already claimed)";
 471             break;
 472           }
 473     }
 474 #if NOBUG_USE_PTHREAD
 475   else if (state == NOBUG_RESOURCE_RECURSIVE)
 476     {
 477       /* check that everyone *else* is waiting */
 478       LLIST_FOREACH (&resource->users, n)
 479         {
 480           struct nobug_resource_user* user = (struct nobug_resource_user*)n;
 481           if (user->state != NOBUG_RESOURCE_WAITING &&
 482               user->thread != tls)
 483             {
 484               nobug_resource_error = "invalid enter state (resource already claimed non recursive by another thread)";
 485               break;
 486             }
 487           else if (!(user->state == NOBUG_RESOURCE_WAITING ||
 488                      user->state == NOBUG_RESOURCE_RECURSIVE) &&
 489                    user->thread == tls)
 490             {
 491               nobug_resource_error = "invalid enter state (resource already claimed non recursive by this thread)";
 492               break;
 493             }
 494         }
 495     }
 496 #endif
 497   else if (state == NOBUG_RESOURCE_SHARED)
 498     {
 499       /* check that every one else is waiting or hold it shared */
 500       LLIST_FOREACH (&resource->users, n)
 501         if (((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_WAITING
 502             && ((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_SHARED)
 503           {
 504             nobug_resource_error = "invalid enter state (resource already claimed non shared)";
 505             break;
 506           }
 507     }
 508   else
 509     nobug_resource_error = "invalid enter state";
 510
 511   if (nobug_resource_error)
 512     return NULL;
 513
 514   struct nobug_resource_user* new_user = mpool_alloc (&nobug_resource_user_pool);
 515   if (!new_user)
 516     {
 517       nobug_resource_error = "internal allocation error";
 518       return NULL;
 519     }
 520
 521   new_user->hdr.name = identifier;
 522   new_user->hdr.extra = extra;
 523   new_user->state = state;
 524   llist_insert_head (&resource->users, llist_init (&new_user->hdr.node));
 525
 526 #if NOBUG_USE_PTHREAD
 527   if (!node)
 528     {
 529       /* no node found, create a new one */
 530       node = nobug_resource_node_new (resource, user?user->current:NULL);
 531       if (!node)
 532         {
 533           nobug_resource_error = "internal allocation error";
 534           return NULL;
 535         }
 536     }
 537
 538   new_user->current = node;
 539   new_user->thread = tls;
 540   llist_insert_tail (&tls->res_stack, llist_init (&new_user->res_stack));
 541 #endif
 542
 543   return new_user;
 544 }
 545
 546
 547 #if NOBUG_USE_PTHREAD
 548 static int
 549 nobug_resource_node_parent_cmpfn (const_LList a, const_LList b, void* extra)
 550 {
 551   (void) extra;
 552   return ((struct nobug_resource_node*)a)->parent ==
 553     ((struct nobug_resource_node*)b)->parent?0:-1;
 554 }
 555 #endif
 556
 557
 558 int
 559 nobug_resource_leave (struct nobug_resource_user* user)
 560 {
 561   if (!user)
 562     {
 563       nobug_resource_error = "no handle";
 564       return 0;
 565     }
 566
 567
 568   if (!user->current?user->current->resource:NULL)
 569     {
 570       nobug_resource_error = "not entered";
 571       return 0;
 572     }
 573   else
 574     {
 575       //dlalgo
 576       //dlalgo HEAD^ Leaving Resources; nobug_resource_leave; fix resource lists
 577       //dlalgo
 578       //dlalgo store the tail and next aside, we need it later
 579       //dlalgo
 580       //dlalgo [source,c]
 581       //dlalgo ---------------------------------------------------------------------
 582 #if NOBUG_USE_PTHREAD                                                           //dlalgo VERBATIM
 583       struct nobug_resource_user* tail =                                        //dlalgo VERBATIM
 584         LLIST_TO_STRUCTP (llist_tail (&user->thread->res_stack),                //dlalgo VERBATIM
 585                           struct nobug_resource_user,                           //dlalgo VERBATIM
 586                           res_stack);                                           //dlalgo VERBATIM
 587
 588       struct nobug_resource_user* next =                                        //dlalgo VERBATIM
 589         LLIST_TO_STRUCTP (llist_next (&user->res_stack),                        //dlalgo VERBATIM
 590                           struct nobug_resource_user,                           //dlalgo VERBATIM
 591                           res_stack);                                           //dlalgo VERBATIM
 592       //dlalgo ---------------------------------------------------------------------
 593       //dlalgo
 594       //dlalgo remove user struct from thread stack
 595       //dlalgo The res_stack is now like it is supposed to look like with the 'user' removed.
 596       //dlalgo We now need to fix the node tree up to match this list.
 597       //dlalgo
 598       //dlalgo [source,c]
 599       //dlalgo ---------------------------------------------------------------------
 600       llist_unlink_fast_ (&user->res_stack);                                    //dlalgo VERBATIM
 601       //dlalgo ---------------------------------------------------------------------
 602       //dlalgo
 603       //dlalgo When the the user node was not the tail or only node of the thread stack, we have to check
 604       //dlalgo (and possibly construct) a new node chain for it. No valdation of this chain needs to be done,
 605       //dlalgo since it was already validated when entering the resources first.
 606       //dlalgo
 607       //dlalgo [source,c]
 608       //dlalgo ---------------------------------------------------------------------
 609       if (user != tail && !llist_is_empty (&user->thread->res_stack))           //dlalgo VERBATIM
 610         {                                                                       //dlalgo VERBATIM
 611           struct nobug_resource_user* parent = NULL;                            //dlalgo VERBATIM
 612           if (llist_head (&user->thread->res_stack) != &next->res_stack)        //dlalgo VERBATIM
 613             {                                                                   //dlalgo VERBATIM
 614               parent =                                                          //dlalgo VERBATIM
 615                 LLIST_TO_STRUCTP (llist_prev (&next->res_stack),                //dlalgo VERBATIM
 616                                   struct nobug_resource_user,                   //dlalgo VERBATIM
 617                                   res_stack);                                   //dlalgo VERBATIM
 618             }                                                                   //dlalgo VERBATIM
 619           //dlalgo ---------------------------------------------------------------------
 620           //dlalgo
 621           //dlalgo iterate over all users following the removed node, finding nodes pointing to this users or
 622           //dlalgo create new nodes.
 623           //dlalgo
 624           //dlalgo [source,c]
 625           //dlalgo ---------------------------------------------------------------------
 626           LLIST_FORRANGE (&next->res_stack, &user->thread->res_stack, n)        //dlalgo VERBATIM
 627             {                                                                   //dlalgo VERBATIM
 628               struct nobug_resource_user* cur =                                 //dlalgo VERBATIM
 629                 LLIST_TO_STRUCTP (n,                                            //dlalgo VERBATIM
 630                                   struct nobug_resource_user,                   //dlalgo VERBATIM
 631                                   res_stack);                                   //dlalgo VERBATIM
 632               //dlalgo VERBATIM
 633               struct nobug_resource_record* resource = cur->current->resource;
 634
 635               //dlalgo ---------------------------------------------------------------------
 636               //TODO this search could be optimized out after we creates a node once,
 637               //TODO    all following nodes need to be created too
 638               //dlalgo
 639               //dlalgo find the node pointing back to parent, create a new one if not found, rinse repeat
 640               //dlalgo
 641               //dlalgo [source,c]
 642               //dlalgo ---------------------------------------------------------------------
 643               struct nobug_resource_node templ =                                //dlalgo VERBATIM
 644                 {                                                               //dlalgo VERBATIM
 645                   {NULL, NULL},                                                 //dlalgo                   ...
 646                   NULL,                                                         //dlalgo VERBATIM
 647                   parent?parent->current:NULL,                                  //dlalgo                   ...
 648                   {NULL, NULL},
 649                   {NULL, NULL}
 650                 };                                                              //dlalgo VERBATIM
 651               //dlalgo VERBATIM
 652               struct nobug_resource_node* node = (struct nobug_resource_node*)  //dlalgo VERBATIM
 653                 llist_ufind (&resource->nodes,                                  //dlalgo VERBATIM
 654                              &templ.node,                                       //dlalgo VERBATIM
 655                              nobug_resource_node_parent_cmpfn,                  //dlalgo VERBATIM
 656                              NULL);                                             //dlalgo VERBATIM
 657               //dlalgo VERBATIM
 658               if (!node)                                                        //dlalgo VERBATIM
 659                 {                                                               //dlalgo VERBATIM
 660                   node = nobug_resource_node_new (resource,                     //dlalgo VERBATIM
 661                                                   parent?parent->current:NULL); //dlalgo VERBATIM
 662                   if (!node)                                                    //dlalgo VERBATIM
 663                     {                                                           //dlalgo VERBATIM
 664                       nobug_resource_error = "internal allocation error";       //dlalgo VERBATIM
 665                       return 0;                                                 //dlalgo VERBATIM
 666                     }                                                           //dlalgo VERBATIM
 667                 }                                                               //dlalgo VERBATIM
 668               //dlalgo VERBATIM
 669               parent = cur;                                                     //dlalgo VERBATIM
 670             }                                                                   //dlalgo VERBATIM
 671         }                                                                       //dlalgo VERBATIM
 672       //dlalgo ---------------------------------------------------------------------
 673       //dlalgo
 674 #endif
 675
 676       llist_unlink_fast_ (&user->hdr.node);
 677       mpool_free (&nobug_resource_user_pool, user);
 678     }
 679
 680   return 1;
 681 }
 682
 683
 684 int
 685 nobug_resource_state (struct nobug_resource_user* user,
 686                       enum nobug_resource_state state)
 687 {
 688   if (!user)
 689     {
 690       nobug_resource_error = "no user handle";
 691       return 0;
 692     }
 693
 694   if (user->state == NOBUG_RESOURCE_WAITING)
 695     {
 696       if (state == NOBUG_RESOURCE_EXCLUSIVE)
 697         {
 698           /* check that every one is waiting */
 699           LLIST_FOREACH (&user->current->resource->users, n)
 700             if (((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_WAITING)
 701               {
 702                 nobug_resource_error = "resource hold by another thread";
 703                 break;
 704               }
 705         }
 706 #if NOBUG_USE_PTHREAD
 707       else if (state == NOBUG_RESOURCE_RECURSIVE)
 708         {
 709           /* check that every one else is waiting */
 710           LLIST_FOREACH (&user->current->resource->users, n)
 711             if (((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_WAITING &&
 712                 ((struct nobug_resource_user*)n)->thread != nobug_thread_get ())
 713               {
 714                 nobug_resource_error = "resource hold by another thread";
 715                 break;
 716               }
 717         }
 718 #endif
 719       else if (state == NOBUG_RESOURCE_SHARED)
 720         {
 721           /* check that every one else is waiting or shared */
 722           LLIST_FOREACH (&user->current->resource->users, n)
 723             if (((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_WAITING
 724                 && ((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_SHARED)
 725               {
 726                 nobug_resource_error = "resource hold by another thread nonshared";
 727                 break;
 728               }
 729         }
 730       else
 731         nobug_resource_error = "invalid state transistion";
 732
 733       /* ok we got it */
 734       if (!nobug_resource_error)
 735         user->state = state;
 736     }
 737   else if (state == NOBUG_RESOURCE_WAITING)
 738     user->state = state;
 739   else
 740     nobug_resource_error = "invalid state transistion";
 741
 742   if (nobug_resource_error)
 743     return 0;
 744
 745   return 1;
 746 }
 747
 748
 749 void
 750 nobug_resource_dump (struct nobug_resource_record* resource, struct nobug_resource_dump_context* context)
 751 {
 752   if (!resource) return;
 753
 754 #if NOBUG_USE_PTHREAD
 755   nobug_log (context->flag, context->level,
 756              "%.10llu: RESOURCE_DUMP: %s:%d: %s: %s: "
 757              "%s %s:%s: hold by %u entities:",
 758              ++nobug_counter, context->file, context->line, nobug_thread_id_get(), context->func,
 759              resource->hdr.extra, resource->type, resource->hdr.name,
 760              llist_count (&resource->users));
 761 #else
 762   nobug_log (context->flag, context->level,
 763              "%.10llu: RESOURCE_DUMP: %s:%d: %s: "
 764              "%s %s:%s: hold by %u entities:",
 765              ++nobug_counter, context->file, context->line, context->func,
 766              resource->hdr.extra, resource->type, resource->hdr.name,
 767              llist_count (&resource->users));
 768 #endif
 769
 770   LLIST_FOREACH (&resource->users, n)
 771     {
 772       struct nobug_resource_user* node = (struct nobug_resource_user*)n;
 773 #if NOBUG_USE_PTHREAD
 774       nobug_log (context->flag, context->level,
 775                  "%.10llu: RESOURCE_DUMP:"NOBUG_TAB
 776                  "%s %s %s: %s",
 777                  ++nobug_counter,
 778                  node->hdr.extra, node->hdr.name, node->thread->thread_id,
 779                  nobug_resource_states[node->state]);
 780 #else
 781       nobug_log (context->flag, context->level,
 782                  "%.10llu: RESOURCE_DUMP: "NOBUG_TAB
 783                  "%s %s: %s",
 784                  ++nobug_counter,
 785                  node->hdr.extra, node->hdr.name, nobug_resource_states[node->state]);
 786 #endif
 787     }
 788 }
 789
 790
 791 void
 792 nobug_resource_dump_all (struct nobug_resource_dump_context* context)
 793 {
 794   LLIST_FOREACH (&nobug_resource_registry, n)
 795     {
 796       struct nobug_resource_record* node = (struct nobug_resource_record*)n;
 797       nobug_resource_dump (node, context);
 798     }
 799 }
 800
 801
 802 void
 803 nobug_resource_list (struct nobug_resource_dump_context* context)
 804 {
 805 #if NOBUG_USE_PTHREAD
 806           nobug_log (context->flag, context->level,
 807                      "%.10llu: RESOURCE_LIST: %s:%d: %s: %s:",
 808                      ++nobug_counter, context->file, context->line, nobug_thread_id_get(), context->func);
 809 #else
 810           nobug_log (context->flag, context->level,
 811                      "%.10llu: RESOURCE_LIST: %s:%d: %s:",
 812                      ++nobug_counter, context->file, context->line, context->func);
 813 #endif
 814
 815   if (!llist_is_empty (&nobug_resource_registry))
 816     {
 817       LLIST_FOREACH (&nobug_resource_registry, n)
 818         {
 819           struct nobug_resource_record* node = (struct nobug_resource_record*)n;
 820           nobug_log (context->flag, context->level,
 821                      "%.10llu: RESOURCE_LIST:"NOBUG_TAB
 822                      "%s %s: %s: %p",
 823                      ++nobug_counter,
 824                      node->hdr.extra, node->type, node->hdr.name, node->object_id);
 825         }
 826     }
 827   else
 828     {
 829       nobug_log (context->flag, context->level,
 830                  "%.10llu: RESOURCE_LIST:"NOBUG_TAB"No resources registered", ++nobug_counter);
 831     }
 832 }
 833
 834 /*
 835 //      Local Variables:
 836 //      mode: C
 837 //      c-file-style: "gnu"
 838 //      indent-tabs-mode: nil
 839 //      End:
 840 */