improve the 'literate' source docs for the resource tracker
[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 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' strcutures 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 */