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