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