2 Bacula® - The Network Backup Solution
4 Copyright (C) 2008-2009 Free Software Foundation Europe e.V.
6 The main author of Bacula is Kern Sibbald, with contributions from
7 many others, a complete list can be found in the file AUTHORS.
8 This program is Free Software; you can redistribute it and/or
9 modify it under the terms of version two of the GNU General Public
10 License as published by the Free Software Foundation, which is
11 listed in the file LICENSE.
13 This program is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
23 Bacula® is a registered trademark of Kern Sibbald.
24 The licensor of Bacula is the Free Software Foundation Europe
25 (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
26 Switzerland, email:ftf@fsfeurope.org.
29 #define _LOCKMGR_COMPLIANT
33 #define ASSERT(x) if (!(x)) { \
35 Pmsg3(000, _("%s:%i Failed ASSERT: %s\n"), __FILE__, __LINE__, #x); \
40 http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf
42 This lock manager will replace some pthread calls. It can be
43 enabled with _USE_LOCKMGR
45 Some part of the code can't use this manager, for example the
46 rwlock object or the smartalloc lib. To disable LMGR, just add
47 _LOCKMGR_COMPLIANT before the inclusion of "bacula.h"
50 g++ -g -c lockmgr.c -I.. -I../lib -D_USE_LOCKMGR -D_TEST_IT
51 g++ -o lockmgr lockmgr.o -lbac -L../lib/.libs -lssl -lpthread
57 * pthread_mutex_lock for memory allocator and other
58 * parts that are _LOCKMGR_COMPLIANT
60 void lmgr_p(pthread_mutex_t *m)
63 if ((errstat=pthread_mutex_lock(m))) {
65 e_msg(__FILE__, __LINE__, M_ABORT, 0, _("Mutex lock failure. ERR=%s\n"),
66 be.bstrerror(errstat));
70 void lmgr_v(pthread_mutex_t *m)
73 if ((errstat=pthread_mutex_unlock(m))) {
75 e_msg(__FILE__, __LINE__, M_ABORT, 0, _("Mutex unlock failure. ERR=%s\n"),
76 be.bstrerror(errstat));
84 LMGR_WHITE, /* never seen */
85 LMGR_BLACK, /* no loop */
86 LMGR_GREY, /* seen before */
90 * Node used by the Lock Manager
91 * If the lock is GRANTED, we have mutex -> proc, else it's a proc -> mutex
94 * Note, each mutex can be GRANTED once, and each proc can have only one WANTED
97 class lmgr_node_t: public SMARTALLOC
110 lmgr_node_t(void *n, void *c) {
114 void init(void *n, void *c) {
120 void mark_as_seen(lmgr_color_t c) {
124 ~lmgr_node_t() {printf("delete node\n");}
128 LMGR_LOCK_EMPTY = 'E', /* unused */
129 LMGR_LOCK_WANTED = 'W', /* before mutex_lock */
130 LMGR_LOCK_GRANTED = 'G' /* after mutex_lock */
134 * Object associated with each mutex per thread
136 class lmgr_lock_t: public SMARTALLOC
148 state = LMGR_LOCK_EMPTY;
151 lmgr_lock_t(void *l) {
153 state = LMGR_LOCK_WANTED;
157 state = LMGR_LOCK_GRANTED;
165 * Get the child list, ret must be already allocated
167 static void search_all_node(dlist *g, lmgr_node_t *v, alist *ret)
170 foreach_dlist(n, g) {
171 if (v->child == n->node) {
177 static bool visite(dlist *g, lmgr_node_t *v)
181 v->mark_as_seen(LMGR_GREY);
183 alist *d = New(alist(5, false)); /* use alist because own=false */
184 search_all_node(g, v, d);
186 //foreach_alist(n, d) {
187 // printf("node n=%p c=%p s=%c\n", n->node, n->child, n->seen);
190 foreach_alist(n, d) {
191 if (n->seen == LMGR_GREY) { /* already seen this node */
194 } else if (n->seen == LMGR_WHITE) {
201 v->mark_as_seen(LMGR_BLACK); /* no loop detected, node is clean */
207 static bool contains_cycle(dlist *g)
210 foreach_dlist(n, g) {
211 if (n->seen == LMGR_WHITE) {
220 /****************************************************************/
222 class lmgr_thread_t: public SMARTALLOC
226 pthread_mutex_t mutex;
228 lmgr_lock_t lock_list[LMGR_MAX_LOCK];
234 if ((status = pthread_mutex_init(&mutex, NULL)) != 0) {
236 Pmsg1(000, _("pthread key create failed: ERR=%s\n"),
237 be.bstrerror(status));
240 thread_id = pthread_self();
245 void _dump(FILE *fp) {
246 fprintf(fp, "threadid=%p max=%i current=%i\n",
247 (void *)thread_id, max, current);
248 for(int i=0; i<=current; i++) {
249 fprintf(fp, " lock=%p state=%s %s:%i\n",
251 (lock_list[i].state=='W')?"Wanted ":"Granted",
252 lock_list[i].file, lock_list[i].line);
256 void dump(FILE *fp) {
257 pthread_mutex_lock(&mutex);
261 pthread_mutex_unlock(&mutex);
265 * Call before a lock operation (mark mutex as WANTED)
267 virtual void pre_P(void *m, const char *f="*unknown*", int l=0) {
268 ASSERT(current < LMGR_MAX_LOCK);
269 ASSERT(current >= -1);
270 pthread_mutex_lock(&mutex);
273 lock_list[current].lock = m;
274 lock_list[current].state = LMGR_LOCK_WANTED;
275 lock_list[current].file = f;
276 lock_list[current].line = l;
277 max = MAX(current, max);
279 pthread_mutex_unlock(&mutex);
283 * Call after the lock operation (mark mutex as GRANTED)
285 virtual void post_P() {
286 ASSERT(current >= 0);
287 ASSERT(lock_list[current].state == LMGR_LOCK_WANTED);
288 lock_list[current].state = LMGR_LOCK_GRANTED;
291 void shift_list(int i) {
292 for(int j=i+1; j<=current; j++) {
293 lock_list[i] = lock_list[j];
296 lock_list[current].lock = NULL;
297 lock_list[current].state = LMGR_LOCK_EMPTY;
302 * Remove the mutex from the list
304 virtual void do_V(void *m, const char *f="*unknown*", int l=0) {
305 ASSERT(current >= 0);
306 pthread_mutex_lock(&mutex);
308 if (lock_list[current].lock == m) {
309 lock_list[current].lock = NULL;
310 lock_list[current].state = LMGR_LOCK_EMPTY;
314 Pmsg3(0, "ERROR: wrong P/V order search lock=%p %s:%i\n", m, f, l);
315 Pmsg4(000, "ERROR: wrong P/V order pos=%i lock=%p %s:%i\n",
316 current, lock_list[current].lock, lock_list[current].file,
317 lock_list[current].line);
318 for (int i=current-1; i >= 0; i--) { /* already seen current */
319 Pmsg4(000, "ERROR: wrong P/V order pos=%i lock=%p %s:%i\n",
320 i, lock_list[i].lock, lock_list[i].file, lock_list[i].line);
321 if (lock_list[i].lock == m) {
322 Pmsg3(000, "ERROR: FOUND P pos=%i %s:%i\n", i, f, l);
330 pthread_mutex_unlock(&mutex);
333 virtual ~lmgr_thread_t() {destroy();}
336 pthread_mutex_destroy(&mutex);
340 class lmgr_dummy_thread_t: public lmgr_thread_t
342 void do_V(void *m, const char *file, int l) {}
344 void pre_P(void *m, const char *file, int l) {}
348 * LMGR - Lock Manager
354 pthread_once_t key_lmgr_once = PTHREAD_ONCE_INIT;
355 static pthread_key_t lmgr_key; /* used to get lgmr_thread_t object */
357 static dlist *global_mgr = NULL; /* used to store all lgmr_thread_t objects */
358 static pthread_mutex_t lmgr_global_mutex = PTHREAD_MUTEX_INITIALIZER;
359 static pthread_t undertaker;
361 #define lmgr_is_active() (global_mgr != NULL)
364 * Add a new lmgr_thread_t object to the global list
366 void lmgr_register_thread(lmgr_thread_t *item)
368 pthread_mutex_lock(&lmgr_global_mutex);
370 global_mgr->prepend(item);
372 pthread_mutex_unlock(&lmgr_global_mutex);
376 * Call this function to cleanup specific lock thread data
378 void lmgr_unregister_thread(lmgr_thread_t *item)
380 if (!lmgr_is_active()) {
383 pthread_mutex_lock(&lmgr_global_mutex);
385 global_mgr->remove(item);
387 pthread_mutex_unlock(&lmgr_global_mutex);
391 * Search for a deadlock when it's secure to walk across
392 * locks list. (after lmgr_detect_deadlock or a fatal signal)
394 bool lmgr_detect_deadlock_unlocked()
397 lmgr_node_t *node=NULL;
400 dlist *g = New(dlist(node, &node->link));
402 /* First, get a list of all node */
403 foreach_dlist(item, global_mgr) {
404 for(int i=0; i<=item->current; i++) {
406 lock = &item->lock_list[i];
407 /* Depending if the lock is granted or not, it's a child or a root
408 * Granted: Mutex -> Thread
409 * Wanted: Thread -> Mutex
411 * Note: a Mutex can be locked only once, a thread can request only
415 if (lock->state == LMGR_LOCK_GRANTED) {
416 node = New(lmgr_node_t((void*)lock->lock, (void*)item->thread_id));
417 } else if (lock->state == LMGR_LOCK_WANTED) {
418 node = New(lmgr_node_t((void*)item->thread_id, (void*)lock->lock));
426 //foreach_dlist(node, g) {
427 // printf("g n=%p c=%p\n", node->node, node->child);
430 ret = contains_cycle(g);
432 printf("Found a deadlock !!!!\n");
440 * Search for a deadlock in during the runtime
441 * It will lock all thread specific lock manager, nothing
442 * can be locked during this check.
444 bool lmgr_detect_deadlock()
447 if (!lmgr_is_active()) {
451 pthread_mutex_lock(&lmgr_global_mutex);
454 foreach_dlist(item, global_mgr) {
455 pthread_mutex_lock(&item->mutex);
458 ret = lmgr_detect_deadlock_unlocked();
460 foreach_dlist(item, global_mgr) {
461 pthread_mutex_unlock(&item->mutex);
464 pthread_mutex_unlock(&lmgr_global_mutex);
471 * Use this function is used only after a fatal signal
472 * We don't use locking to display the information
474 void dbg_print_lock(FILE *fp)
476 fprintf(fp, "Attempt to dump locks\n");
477 if (!lmgr_is_active()) {
481 foreach_dlist(item, global_mgr) {
487 * Dump each lmgr_thread_t object
491 pthread_mutex_lock(&lmgr_global_mutex);
494 foreach_dlist(item, global_mgr) {
498 pthread_mutex_unlock(&lmgr_global_mutex);
501 void cln_hdl(void *a)
503 lmgr_cleanup_thread();
506 void *check_deadlock(void *)
510 pthread_cleanup_push(cln_hdl, NULL);
512 while (!bmicrosleep(30, 0)) {
513 pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &old);
514 if (lmgr_detect_deadlock()) {
518 pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, &old);
519 pthread_testcancel();
521 Pmsg0(000, "Undertaker is leaving...\n");
522 pthread_cleanup_pop(1);
526 /* This object is used when LMGR is not initialized */
527 static lmgr_dummy_thread_t dummy_lmgr;
530 * Retrieve the lmgr_thread_t object from the stack
532 inline lmgr_thread_t *lmgr_get_thread_info()
534 if (lmgr_is_active()) {
535 return (lmgr_thread_t *)pthread_getspecific(lmgr_key);
542 * launch once for all threads
544 void create_lmgr_key()
546 int status = pthread_key_create(&lmgr_key, NULL);
549 Pmsg1(000, _("pthread key create failed: ERR=%s\n"),
550 be.bstrerror(status));
554 lmgr_thread_t *n=NULL;
555 global_mgr = New(dlist(n, &n->link));
557 status = pthread_create(&undertaker, NULL, check_deadlock, NULL);
560 Pmsg1(000, _("pthread_create failed: ERR=%s\n"),
561 be.bstrerror(status));
567 * Each thread have to call this function to put a lmgr_thread_t object
568 * in the stack and be able to call mutex_lock/unlock
570 void lmgr_init_thread()
572 int status = pthread_once(&key_lmgr_once, create_lmgr_key);
575 Pmsg1(000, _("pthread key create failed: ERR=%s\n"),
576 be.bstrerror(status));
579 lmgr_thread_t *l = New(lmgr_thread_t());
580 pthread_setspecific(lmgr_key, l);
581 lmgr_register_thread(l);
585 * Call this function at the end of the thread
587 void lmgr_cleanup_thread()
589 if (!lmgr_is_active()) {
592 lmgr_thread_t *self = lmgr_get_thread_info();
593 lmgr_unregister_thread(self);
598 * This function should be call at the end of the main thread
599 * Some thread like the watchdog are already present, so the global_mgr
600 * list is never empty. Should carefully clear the memory.
602 void lmgr_cleanup_main()
609 pthread_cancel(undertaker);
610 lmgr_cleanup_thread();
611 pthread_mutex_lock(&lmgr_global_mutex);
617 pthread_mutex_unlock(&lmgr_global_mutex);
621 * Replacement for pthread_mutex_lock()
623 int lmgr_mutex_lock(pthread_mutex_t *m, const char *file, int line)
626 lmgr_thread_t *self = lmgr_get_thread_info();
627 self->pre_P(m, file, line);
628 ret = pthread_mutex_lock(m);
634 * Replacement for pthread_mutex_unlock()
636 int lmgr_mutex_unlock(pthread_mutex_t *m, const char *file, int line)
638 lmgr_thread_t *self = lmgr_get_thread_info();
639 self->do_V(m, file, line);
640 return pthread_mutex_unlock(m);
645 int lmgr_cond_wait(pthread_cond_t *cond,
646 pthread_mutex_t *mutex,
647 const char *file, int line)
650 lmgr_thread_t *self = lmgr_get_thread_info();
651 self->do_V(mutex, file, line);
652 ret = pthread_cond_wait(cond, mutex);
653 self->pre_P(mutex, file, line);
659 * Use this function when the caller handle the mutex directly
662 * pthread_mutex_lock(m);
665 void lmgr_pre_lock(void *m, const char *file, int line)
667 lmgr_thread_t *self = lmgr_get_thread_info();
668 self->pre_P(m, file, line);
672 * Use this function when the caller handle the mutex directly
674 void lmgr_post_lock()
676 lmgr_thread_t *self = lmgr_get_thread_info();
681 * Do directly pre_P and post_P (used by trylock)
683 void lmgr_do_lock(void *m, const char *file, int line)
685 lmgr_thread_t *self = lmgr_get_thread_info();
686 self->pre_P(m, file, line);
691 * Use this function when the caller handle the mutex directly
693 void lmgr_do_unlock(void *m)
695 lmgr_thread_t *self = lmgr_get_thread_info();
700 void *(*start_routine)(void*);
705 void *lmgr_thread_launcher(void *x)
709 pthread_cleanup_push(cln_hdl, NULL);
711 lmgr_thread_arg_t arg;
712 lmgr_thread_arg_t *a = (lmgr_thread_arg_t *)x;
713 arg.start_routine = a->start_routine;
717 ret = arg.start_routine(arg.arg);
718 pthread_cleanup_pop(1);
722 int lmgr_thread_create(pthread_t *thread,
723 const pthread_attr_t *attr,
724 void *(*start_routine)(void*), void *arg)
726 /* lmgr should be active (lmgr_init_thread() call in main()) */
727 ASSERT(lmgr_is_active());
728 /* Will be freed by the child */
729 lmgr_thread_arg_t *a = (lmgr_thread_arg_t*) malloc(sizeof(lmgr_thread_arg_t));
730 a->start_routine = start_routine;
732 return pthread_create(thread, attr, lmgr_thread_launcher, a);
735 #else /* _USE_LOCKMGR */
739 * Use this function is used only after a fatal signal
740 * We don't use locking to display information
742 void dbg_print_lock(FILE *fp)
744 Pmsg0(000, "lockmgr disabled\n");
747 #endif /* _USE_LOCKMGR */
752 #define pthread_mutex_lock(x) lmgr_mutex_lock(x)
753 #define pthread_mutex_unlock(x) lmgr_mutex_unlock(x)
754 #define pthread_cond_wait(x,y) lmgr_cond_wait(x,y)
755 #define pthread_create(a, b, c, d) lmgr_thread_create(a,b,c,d)
758 #define P(x) lmgr_mutex_lock(&(x), __FILE__, __LINE__)
759 #define V(x) lmgr_mutex_unlock(&(x), __FILE__, __LINE__)
761 pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
762 pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
763 pthread_mutex_t mutex3 = PTHREAD_MUTEX_INITIALIZER;
764 pthread_mutex_t mutex4 = PTHREAD_MUTEX_INITIALIZER;
765 pthread_mutex_t mutex5 = PTHREAD_MUTEX_INITIALIZER;
766 pthread_mutex_t mutex6 = PTHREAD_MUTEX_INITIALIZER;
768 void *self_lock(void *temp)
777 void *nolock(void *temp)
785 void *locker(void *temp)
787 pthread_mutex_t *m = (pthread_mutex_t*) temp;
788 pthread_mutex_lock(m);
789 pthread_mutex_unlock(m);
793 void *rwlocker(void *temp)
795 brwlock_t *m = (brwlock_t*) temp;
804 void *mix_rwl_mutex(void *temp)
806 brwlock_t *m = (brwlock_t*) temp;
815 void *th2(void *temp)
830 void *th1(void *temp)
847 void *thx(void *temp)
849 int s= 1 + (int) (500.0 * (rand() / (RAND_MAX + 1.0))) + 200;
862 fprintf(stderr, "undertaker sleep()\n");
865 if (lmgr_detect_deadlock()) {
875 void _ok(const char *file, int l, const char *op, int value, const char *label)
880 printf("ERR %.30s %s:%i on %s\n", label, file, l, op);
882 printf("OK %.30s\n", label);
886 #define ok(x, label) _ok(__FILE__, __LINE__, #x, (x), label)
888 void _nok(const char *file, int l, const char *op, int value, const char *label)
893 printf("ERR %.30s %s:%i on !%s\n", label, file, l, op);
895 printf("OK %.30s\n", label);
899 #define nok(x, label) _nok(__FILE__, __LINE__, #x, (x), label)
903 printf("Result %i/%i OK\n", nb - err, nb);
909 * - Must detect multiple lock
910 * - lock/unlock in wrong order
911 * - deadlock with 2 or 3 threads
915 pthread_t id1, id2, id3, tab[200];
918 pthread_create(&id1, NULL, self_lock, NULL);
920 ok(lmgr_detect_deadlock(), "Check self deadlock");
921 lmgr_v(&mutex1); /* a bit dirty */
922 pthread_join(id1, NULL);
925 pthread_create(&id1, NULL, nolock, NULL);
927 nok(lmgr_detect_deadlock(), "Check for nolock");
928 pthread_join(id1, NULL);
931 pthread_create(&id1, NULL, locker, &mutex1);
932 pthread_create(&id2, NULL, locker, &mutex1);
933 pthread_create(&id3, NULL, locker, &mutex1);
935 nok(lmgr_detect_deadlock(), "Check for multiple lock");
937 pthread_join(id1, NULL);
938 pthread_join(id2, NULL);
939 pthread_join(id3, NULL);
946 pthread_create(&id1, NULL, rwlocker, &wr);
947 pthread_create(&id2, NULL, rwlocker, &wr);
948 pthread_create(&id3, NULL, rwlocker, &wr);
949 nok(lmgr_detect_deadlock(), "Check for multiple rwlock");
950 rwl_writeunlock(&wr);
951 nok(lmgr_detect_deadlock(), "Check for simple rwlock");
952 rwl_writeunlock(&wr);
953 nok(lmgr_detect_deadlock(), "Check for multiple rwlock");
955 pthread_join(id1, NULL);
956 pthread_join(id2, NULL);
957 pthread_join(id3, NULL);
961 pthread_create(&id1, NULL, mix_rwl_mutex, &wr);
962 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
964 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
965 rwl_writeunlock(&wr);
966 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
967 pthread_join(id1, NULL);
974 nok(lmgr_detect_deadlock(), "Check for wrong order");
976 for(int j=0; j<200; j++) {
977 pthread_create(&tab[j], NULL, thx, NULL);
979 for(int j=0; j<200; j++) {
980 pthread_join(tab[j], NULL);
981 if (j%3) { lmgr_detect_deadlock();}
983 nok(lmgr_detect_deadlock(), "Check 200 lockers");
992 pthread_create(&id1, NULL, th1, NULL);
994 pthread_create(&id2, NULL, th2, NULL);
996 ok(lmgr_detect_deadlock(), "Check for deadlock");
1000 // pthread_create(&id3, NULL, th3, NULL);
1002 // pthread_join(id1, NULL);
1003 // pthread_join(id2, NULL);
1004 lmgr_cleanup_main();
1005 sm_check(__FILE__, __LINE__, false);