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<<(sizeof(void*)/2))        /* That is roughly 8k chunks on 32bit, 16k chunks on 64 bit machines */
  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   if (!llist_is_empty (&self->users))
 243     {
 244       nobug_resource_error = "still in use";
 245       return 0;
 246     }
 247
 248   nobug_resource_record_dtor (self);
 249
 250   mpool_free (&nobug_resource_record_pool, self);
 251   NOBUG_RESOURCE_UNLOCK;
 252   return 1;
 253 }
 254
 255
 256 #if NOBUG_USE_PTHREAD
 257 static int
 258 nobug_resource_node_resource_cmpfn (const_LList a, const_LList b, void* extra)
 259 {
 260   (void) extra;
 261   return ((struct nobug_resource_node*)a)->resource ==
 262     ((struct nobug_resource_node*)b)->resource?0:-1;
 263 }
 264
 265
 266 struct nobug_resource_node*
 267 nobug_resource_node_new (struct nobug_resource_record* resource,
 268                          struct nobug_resource_node* parent)
 269 {
 270   struct nobug_resource_node* self = mpool_alloc (&nobug_resource_node_pool);
 271   if (self)
 272     {
 273       llist_insert_head (&resource->nodes, llist_init (&self->node));
 274       self->resource = resource;
 275
 276       self->parent = parent;
 277
 278       llist_init (&self->childs);
 279       llist_init (&self->cldnode);
 280       if (parent)
 281         llist_insert_head (&parent->childs, &self->cldnode);
 282     }
 283   return self;
 284 }
 285 #endif
 286
 287
 288 //dlalgo HEAD~ The Resource Tracking Algorithm; deadlock detection; how resources are tracked
 289 //dlalgo
 290 //dlalgo Each resource registers a global 'resource_record'.
 291 //dlalgo
 292 //dlalgo Every new locking path discovered is stored as 'resource_node' structures which refer to the associated
 293 //dlalgo 'resource_record'.
 294 //dlalgo
 295 //dlalgo Threads keep a trail of 'resource_user' strcutures for each resource entered. This 'resource_user' struct
 296 //dlalgo refer to the 'resource_nodes' and thus indirectly to the associated 'resource_record'.
 297 //dlalgo
 298 //dlalgo The deadlock checker uses this information to test if the acqusition of a new resource would yield a
 299 //dlalgo potential deadlock.
 300 //dlalgo
 301 struct nobug_resource_user*
 302 nobug_resource_enter (struct nobug_resource_record* resource,
 303                       const char* identifier,
 304                       enum nobug_resource_state state,
 305                       const char* extra)
 306 {
 307   NOBUG_RESOURCE_LOCK;
 308
 309   if (!resource)
 310     {
 311       nobug_resource_error = "no resource";
 312       return NULL;
 313     }
 314
 315 #if NOBUG_USE_PTHREAD
 316   struct nobug_tls_data* tls = nobug_thread_get ();
 317
 318   //dlalgo HEAD^ Entering Resources; nobug_resource_enter; deadlock check on enter
 319   //dlalgo
 320   //dlalgo In multithreaded programs, whenever a thread wants to wait for a 'resource_record'
 321   //dlalgo the deadlock checker jumps in.
 322   //dlalgo
 323   //dlalgo The deadlock checking algorithm is anticipatory as it will find and abort on conditions which may lead
 324   //dlalgo to a potential deadlock by violating the locking order learned earlier.
 325   //dlalgo
 326   //dlalgo Each thread holds a stack (list) of each 'resource_user' it created. Leaving
 327   //dlalgo a resource will remove it from this stacklist.
 328   //dlalgo
 329   //dlalgo Each 'resource_record' stores the trail which other 'resource_records' are already entered. This relations
 330   //dlalgo are implemented with the 'resource_node' helper structure.
 331   //dlalgo
 332   //dlalgo ////
 333   //dlalgo TODO: insert diagram here
 334   //dlalgo   2-3
 335   //dlalgo 1
 336   //dlalgo   3-4-2
 337   //dlalgo
 338   //dlalgo 1-3-2-4
 339   //dlalgo
 340   //dlalgo 3-4-2
 341   //dlalgo
 342   //dlalgo 1-4-2
 343   //dlalgo
 344   //dlalgo ////
 345   //dlalgo
 346   //dlalgo First we find out if there is already a node from the to be acquired resource back to
 347   //dlalgo the topmost node of the current threads user stack.
 348   //dlalgo
 349   //dlalgo [source,c]
 350   //dlalgo ---------------------------------------------------------------------
 351   struct nobug_resource_user* user = NULL;                      //dlalgo VERBATIM
 352   struct nobug_resource_node* node = NULL;                      //dlalgo VERBATIM
 353                                                                 //dlalgo VERBATIM
 354   if (!llist_is_empty (&tls->res_stack))                        //dlalgo VERBATIM
 355     {                                                           //dlalgo VERBATIM
 356       user = LLIST_TO_STRUCTP (llist_tail (&tls->res_stack),    //dlalgo VERBATIM
 357                                struct nobug_resource_user,      //dlalgo VERBATIM
 358                                res_stack);                      //dlalgo VERBATIM
 359                                                                 //dlalgo VERBATIM
 360       struct nobug_resource_node templ =                        //dlalgo VERBATIM
 361         {                                                       //dlalgo VERBATIM
 362           {NULL, NULL},                                         //dlalgo          ...
 363           user->current->resource,                              //dlalgo VERBATIM
 364           NULL,                                                 //dlalgo          ...
 365           {NULL, NULL},
 366           {NULL, NULL}
 367         };                                                      //dlalgo VERBATIM
 368                                                                 //dlalgo VERBATIM
 369       node = (struct nobug_resource_node*)                      //dlalgo VERBATIM
 370         llist_ufind (&resource->nodes,                          //dlalgo VERBATIM
 371                      &templ.node,                               //dlalgo VERBATIM
 372                      nobug_resource_node_resource_cmpfn,        //dlalgo VERBATIM
 373                      NULL);                                     //dlalgo VERBATIM
 374     }                                                           //dlalgo VERBATIM
 375   //dlalgo   ...
 376   //dlalgo ---------------------------------------------------------------------
 377   //dlalgo
 378 #endif
 379
 380   //dlalgo Deadlock checking is only done when the node is entered in `WAITING` state and only
 381   //dlalgo available in multithreaded programs.y
 382   //dlalgo
 383   //dlalgo [source,c]
 384   //dlalgo ---------------------------------------------------------------------
 385   if (state == NOBUG_RESOURCE_WAITING)                          //dlalgo VERBATIM
 386     {                                                           //dlalgo VERBATIM
 387 #if NOBUG_USE_PTHREAD                                           //dlalgo VERBATIM
 388       //dlalgo       ...
 389       //dlalgo ---------------------------------------------------------------------
 390       //dlalgo
 391
 392       //TODO factor deadlock checker out of possible
 393
 394       //dlalgo If node was found above, then this locking path is already validated and no deadlock can happen,
 395       //dlalgo else, if this stack already holds a resource (user is set) we have to go on with checking.
 396       //dlalgo
 397       //dlalgo [source,c]
 398       //dlalgo ---------------------------------------------------------------------
 399       if (!node && user)                                                //dlalgo VERBATIM
 400         {                                                               //dlalgo VERBATIM
 401           //dlalgo           ...
 402           //dlalgo ---------------------------------------------------------------------
 403           //dlalgo
 404           //dlalgo If not then its checked that the resource to be entered is not on any parent trail of the current topmost resource,
 405           //dlalgo if it is then this could be a deadlock which needs to be further investigated.
 406           //dlalgo
 407           //dlalgo [source,c]
 408           //dlalgo ---------------------------------------------------------------------
 409           LLIST_FOREACH (&user->current->resource->nodes, n)            //dlalgo VERBATIM
 410             {                                                           //dlalgo VERBATIM
 411               for (struct nobug_resource_node* itr =                    //dlalgo VERBATIM
 412                      ((struct nobug_resource_node*)n)->parent;          //dlalgo VERBATIM
 413                    itr;                                                 //dlalgo VERBATIM
 414                    itr = itr->parent)                                   //dlalgo VERBATIM
 415                 {                                                       //dlalgo VERBATIM
 416                   if (itr->resource == resource)                        //dlalgo VERBATIM
 417                     {                                                   //dlalgo VERBATIM
 418                       //dlalgo                       ...
 419                       //dlalgo ---------------------------------------------------------------------
 420                       //dlalgo
 421                       //dlalgo if the resource was on the trail, we search if there is a common ancestor before the resource
 422                       //dlalgo on the trail and the threads current chain,
 423                       //dlalgo if yes then this ancestor protects against deadlocks and we can continue.
 424                       //dlalgo
 425                       //dlalgo [source,c]
 426                       //dlalgo ---------------------------------------------------------------------
 427                       for (struct nobug_resource_node* itr2 = itr->parent;              //dlalgo VERBATIM
 428                            itr2;                                                        //dlalgo VERBATIM
 429                            itr2 = itr2->parent)                                         //dlalgo VERBATIM
 430                         {                                                               //dlalgo VERBATIM
 431                           LLIST_FOREACH_REV (&tls->res_stack, p)                        //dlalgo VERBATIM
 432                             {                                                           //dlalgo VERBATIM
 433                               struct nobug_resource_user* user =                        //dlalgo VERBATIM
 434                                 LLIST_TO_STRUCTP (p,                                    //dlalgo VERBATIM
 435                                                   struct nobug_resource_user,           //dlalgo VERBATIM
 436                                                   res_stack);                           //dlalgo VERBATIM
 437                               if (user->current->resource == itr2->resource)            //dlalgo VERBATIM
 438                                 goto done;                                              //dlalgo VERBATIM
 439                             }                                                           //dlalgo VERBATIM
 440                           //dlalgo ---------------------------------------------------------------------
 441                           //dlalgo
 442                           //dlalgo If no ancestor found, we finally abort with a potential deadlock condition.
 443                           //dlalgo
 444                           //dlalgo [source,c]
 445                           //dlalgo ---------------------------------------------------------------------
 446                           nobug_resource_error = "possible deadlock detected";          //dlalgo VERBATIM
 447                           return NULL;                                                  //dlalgo VERBATIM
 448                           //dlalgo                           ...
 449                           //dlalgo ---------------------------------------------------------------------
 450                           //dlalgo
 451                         }
 452                     }
 453                 }
 454             }
 455         }
 456     done:;
 457 #endif
 458     }
 459   else if (state == NOBUG_RESOURCE_EXCLUSIVE)
 460     {
 461       /* check that everyone is waiting */
 462       LLIST_FOREACH (&resource->users, n)
 463         if (((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_WAITING)
 464           {
 465             nobug_resource_error = "invalid enter state (resource already claimed)";
 466             break;
 467           }
 468     }
 469 #if NOBUG_USE_PTHREAD
 470   else if (state == NOBUG_RESOURCE_RECURSIVE)
 471     {
 472       /* check that everyone *else* is waiting */
 473       LLIST_FOREACH (&resource->users, n)
 474         {
 475           struct nobug_resource_user* user = (struct nobug_resource_user*)n;
 476           if (user->state != NOBUG_RESOURCE_WAITING &&
 477               user->thread != tls)
 478             {
 479               nobug_resource_error = "invalid enter state (resource already claimed non recursive by another thread)";
 480               break;
 481             }
 482           else if (!(user->state == NOBUG_RESOURCE_WAITING ||
 483                      user->state == NOBUG_RESOURCE_RECURSIVE) &&
 484                    user->thread == tls)
 485             {
 486               nobug_resource_error = "invalid enter state (resource already claimed non recursive by this thread)";
 487               break;
 488             }
 489         }
 490     }
 491 #endif
 492   else if (state == NOBUG_RESOURCE_SHARED)
 493     {
 494       /* check that every one else is waiting or hold it shared */
 495       LLIST_FOREACH (&resource->users, n)
 496         if (((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_WAITING
 497             && ((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_SHARED)
 498           {
 499             nobug_resource_error = "invalid enter state (resource already claimed non shared)";
 500             break;
 501           }
 502     }
 503   else
 504     nobug_resource_error = "invalid enter state";
 505
 506   if (nobug_resource_error)
 507     return NULL;
 508
 509   struct nobug_resource_user* new_user = mpool_alloc (&nobug_resource_user_pool);
 510   if (!new_user)
 511     {
 512       nobug_resource_error = "internal allocation error";
 513       return NULL;
 514     }
 515
 516   new_user->hdr.name = identifier;
 517   new_user->hdr.extra = extra;
 518   new_user->state = state;
 519   llist_insert_head (&resource->users, llist_init (&new_user->hdr.node));
 520
 521 #if NOBUG_USE_PTHREAD
 522   if (!node)
 523     {
 524       /* no node found, create a new one */
 525       node = nobug_resource_node_new (resource, user?user->current:NULL);
 526       if (!node)
 527         {
 528           nobug_resource_error = "internal allocation error";
 529           return NULL;
 530         }
 531     }
 532
 533   new_user->current = node;
 534   new_user->thread = tls;
 535   llist_insert_tail (&tls->res_stack, llist_init (&new_user->res_stack));
 536 #endif
 537
 538   NOBUG_RESOURCE_UNLOCK;
 539   return new_user;
 540 }
 541
 542
 543 #if NOBUG_USE_PTHREAD
 544 static int
 545 nobug_resource_node_parent_cmpfn (const_LList a, const_LList b, void* extra)
 546 {
 547   (void) extra;
 548   return ((struct nobug_resource_node*)a)->parent ==
 549     ((struct nobug_resource_node*)b)->parent?0:-1;
 550 }
 551 #endif
 552
 553
 554 int
 555 nobug_resource_leave (struct nobug_resource_user* user)
 556 {
 557   NOBUG_RESOURCE_LOCK;
 558
 559   if (!user)
 560     {
 561       nobug_resource_error = "no handle";
 562       return 0;
 563     }
 564
 565
 566   if (!user->current?user->current->resource:NULL)
 567     {
 568       nobug_resource_error = "not entered";
 569       return 0;
 570     }
 571   else
 572     {
 573       //dlalgo
 574       //dlalgo HEAD^ Leaving Resources; nobug_resource_leave; fix resource lists
 575       //dlalgo
 576       //dlalgo store the tail and next aside, we need it later
 577       //dlalgo
 578       //dlalgo [source,c]
 579       //dlalgo ---------------------------------------------------------------------
 580 #if NOBUG_USE_PTHREAD                                                           //dlalgo VERBATIM
 581       struct nobug_resource_user* tail =                                        //dlalgo VERBATIM
 582         LLIST_TO_STRUCTP (llist_tail (&user->thread->res_stack),                //dlalgo VERBATIM
 583                           struct nobug_resource_user,                           //dlalgo VERBATIM
 584                           res_stack);                                           //dlalgo VERBATIM
 585
 586       struct nobug_resource_user* next =                                        //dlalgo VERBATIM
 587         LLIST_TO_STRUCTP (llist_next (&user->res_stack),                        //dlalgo VERBATIM
 588                           struct nobug_resource_user,                           //dlalgo VERBATIM
 589                           res_stack);                                           //dlalgo VERBATIM
 590       //dlalgo ---------------------------------------------------------------------
 591       //dlalgo
 592       //dlalgo remove user struct from thread stack
 593       //dlalgo The res_stack is now like it is supposed to look like with the 'user' removed.
 594       //dlalgo We now need to fix the node tree up to match this list.
 595       //dlalgo
 596       //dlalgo [source,c]
 597       //dlalgo ---------------------------------------------------------------------
 598       llist_unlink_fast_ (&user->res_stack);                                    //dlalgo VERBATIM
 599       //dlalgo ---------------------------------------------------------------------
 600       //dlalgo
 601       //dlalgo When the the user node was not the tail or only node of the thread stack, we have to check
 602       //dlalgo (and possibly construct) a new node chain for it. No valdation of this chain needs to be done,
 603       //dlalgo since it was already validated when entering the resources first.
 604       //dlalgo
 605       //dlalgo [source,c]
 606       //dlalgo ---------------------------------------------------------------------
 607       if (user != tail && !llist_is_empty (&user->thread->res_stack))           //dlalgo VERBATIM
 608         {                                                                       //dlalgo VERBATIM
 609           struct nobug_resource_user* parent = NULL;                            //dlalgo VERBATIM
 610           if (llist_head (&user->thread->res_stack) != &next->res_stack)        //dlalgo VERBATIM
 611             {                                                                   //dlalgo VERBATIM
 612               parent =                                                          //dlalgo VERBATIM
 613                 LLIST_TO_STRUCTP (llist_prev (&next->res_stack),                //dlalgo VERBATIM
 614                                   struct nobug_resource_user,                   //dlalgo VERBATIM
 615                                   res_stack);                                   //dlalgo VERBATIM
 616             }                                                                   //dlalgo VERBATIM
 617           //dlalgo ---------------------------------------------------------------------
 618           //dlalgo
 619           //dlalgo iterate over all users following the removed node, finding nodes pointing to this users or
 620           //dlalgo create new nodes.
 621           //dlalgo
 622           //dlalgo [source,c]
 623           //dlalgo ---------------------------------------------------------------------
 624           LLIST_FORRANGE (&next->res_stack, &user->thread->res_stack, n)        //dlalgo VERBATIM
 625             {                                                                   //dlalgo VERBATIM
 626               struct nobug_resource_user* cur =                                 //dlalgo VERBATIM
 627                 LLIST_TO_STRUCTP (n,                                            //dlalgo VERBATIM
 628                                   struct nobug_resource_user,                   //dlalgo VERBATIM
 629                                   res_stack);                                   //dlalgo VERBATIM
 630               //dlalgo VERBATIM
 631               struct nobug_resource_record* resource = cur->current->resource;
 632
 633               //dlalgo ---------------------------------------------------------------------
 634               //TODO this search could be optimized out after we creates a node once,
 635               //TODO    all following nodes need to be created too
 636               //dlalgo
 637               //dlalgo finde the node pointing back to parent, create a new one if not found, rinse repeat
 638               //dlalgo
 639               //dlalgo [source,c]
 640               //dlalgo ---------------------------------------------------------------------
 641               struct nobug_resource_node templ =                                //dlalgo VERBATIM
 642                 {                                                               //dlalgo VERBATIM
 643                   {NULL, NULL},                                                 //dlalgo                   ...
 644                   NULL,                                                         //dlalgo VERBATIM
 645                   parent?parent->current:NULL,                                  //dlalgo                   ...
 646                   {NULL, NULL},
 647                   {NULL, NULL}
 648                 };                                                              //dlalgo VERBATIM
 649               //dlalgo VERBATIM
 650               struct nobug_resource_node* node = (struct nobug_resource_node*)  //dlalgo VERBATIM
 651                 llist_ufind (&resource->nodes,                                  //dlalgo VERBATIM
 652                              &templ.node,                                       //dlalgo VERBATIM
 653                              nobug_resource_node_parent_cmpfn,                  //dlalgo VERBATIM
 654                              NULL);                                             //dlalgo VERBATIM
 655               //dlalgo VERBATIM
 656               if (!node)                                                        //dlalgo VERBATIM
 657                 {                                                               //dlalgo VERBATIM
 658                   node = nobug_resource_node_new (resource, parent->current);   //dlalgo VERBATIM
 659                   if (!node)                                                    //dlalgo VERBATIM
 660                     {                                                           //dlalgo VERBATIM
 661                       nobug_resource_error = "internal allocation error";       //dlalgo VERBATIM
 662                       return 0;                                                 //dlalgo VERBATIM
 663                     }                                                           //dlalgo VERBATIM
 664                 }                                                               //dlalgo VERBATIM
 665               //dlalgo VERBATIM
 666               parent = cur;                                                     //dlalgo VERBATIM
 667             }                                                                   //dlalgo VERBATIM
 668         }                                                                       //dlalgo VERBATIM
 669       //dlalgo ---------------------------------------------------------------------
 670       //dlalgo
 671 #endif
 672
 673       llist_unlink_fast_ (&user->hdr.node);
 674       mpool_free (&nobug_resource_user_pool, user);
 675     }
 676
 677   NOBUG_RESOURCE_UNLOCK;
 678   return 1;
 679 }
 680
 681
 682 int
 683 nobug_resource_state (struct nobug_resource_user* user,
 684                       enum nobug_resource_state state)
 685 {
 686   NOBUG_RESOURCE_LOCK;
 687   if (!user)
 688     {
 689       nobug_resource_error = "no user handle";
 690       return 0;
 691     }
 692
 693   if (user->state == NOBUG_RESOURCE_WAITING)
 694     {
 695       if (state == NOBUG_RESOURCE_EXCLUSIVE)
 696         {
 697           /* check that every one is waiting */
 698           LLIST_FOREACH (&user->current->resource->users, n)
 699             if (((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_WAITING)
 700               {
 701                 nobug_resource_error = "resource hold by another thread";
 702                 break;
 703               }
 704         }
 705 #if NOBUG_USE_PTHREAD
 706       else if (state == NOBUG_RESOURCE_RECURSIVE)
 707         {
 708           /* check that every one else is waiting */
 709           LLIST_FOREACH (&user->current->resource->users, n)
 710             if (((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_WAITING &&
 711                 ((struct nobug_resource_user*)n)->thread != nobug_thread_get ())
 712               {
 713                 nobug_resource_error = "resource hold by another thread";
 714                 break;
 715               }
 716         }
 717 #endif
 718       else if (state == NOBUG_RESOURCE_SHARED)
 719         {
 720           /* check that every one else is waiting or shared */
 721           LLIST_FOREACH (&user->current->resource->users, n)
 722             if (((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_WAITING
 723                 && ((struct nobug_resource_user*)n)->state != NOBUG_RESOURCE_SHARED)
 724               {
 725                 nobug_resource_error = "resource hold by another thread nonshared";
 726                 break;
 727               }
 728         }
 729       else
 730         nobug_resource_error = "invalid state transistion";
 731
 732       /* ok we got it */
 733       if (!nobug_resource_error)
 734         user->state = state;
 735     }
 736   else if (state == NOBUG_RESOURCE_WAITING)
 737     user->state = state;
 738   else
 739     nobug_resource_error = "invalid state transistion";
 740
 741   if (nobug_resource_error)
 742     return 0;
 743
 744   NOBUG_RESOURCE_UNLOCK;
 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              "%0.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              "%0.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                  "%0.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                  "%0.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                      "%0.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                      "%0.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                      "%0.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                  "%0.10llu: RESOURCE_LIST:"NOBUG_TAB"No resources registered", ++nobug_counter);
 831     }
 832 }
 833
 834
 835 /*
 836 //      Local Variables:
 837 //      mode: C
 838 //      c-file-style: "gnu"
 839 //      indent-tabs-mode: nil
 840 //      End:
 841 */