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