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