src/nobug_resources.c

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