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) {
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);
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);
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);
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);
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 lmgr_p(&lmgr_global_mutex);
370 global_mgr->prepend(item);
372 lmgr_v(&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 lmgr_p(&lmgr_global_mutex);
385 global_mgr->remove(item);
387 lmgr_v(&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 lmgr_p(&lmgr_global_mutex);
454 foreach_dlist(item, global_mgr) {
455 lmgr_p(&item->mutex);
458 ret = lmgr_detect_deadlock_unlocked();
460 foreach_dlist(item, global_mgr) {
461 lmgr_v(&item->mutex);
464 lmgr_v(&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 lmgr_p(&lmgr_global_mutex);
494 foreach_dlist(item, global_mgr) {
498 lmgr_v(&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 lmgr_p(&lmgr_global_mutex);
617 lmgr_v(&lmgr_global_mutex);
621 * Replacement for pthread_mutex_lock()
624 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);
634 * Replacement for pthread_mutex_unlock()
637 int lmgr_mutex_unlock(pthread_mutex_t *m, const char *file, int line)
639 lmgr_thread_t *self = lmgr_get_thread_info();
640 self->do_V(m, file, line);
647 int lmgr_cond_wait(pthread_cond_t *cond,
648 pthread_mutex_t *mutex,
649 const char *file, int line)
652 lmgr_thread_t *self = lmgr_get_thread_info();
653 self->do_V(mutex, file, line);
654 ret = pthread_cond_wait(cond, mutex);
655 self->pre_P(mutex, file, line);
661 * Use this function when the caller handle the mutex directly
664 * pthread_mutex_lock(m);
667 void lmgr_pre_lock(void *m, const char *file, int line)
669 lmgr_thread_t *self = lmgr_get_thread_info();
670 self->pre_P(m, file, line);
674 * Use this function when the caller handle the mutex directly
676 void lmgr_post_lock()
678 lmgr_thread_t *self = lmgr_get_thread_info();
683 * Do directly pre_P and post_P (used by trylock)
685 void lmgr_do_lock(void *m, const char *file, int line)
687 lmgr_thread_t *self = lmgr_get_thread_info();
688 self->pre_P(m, file, line);
693 * Use this function when the caller handle the mutex directly
695 void lmgr_do_unlock(void *m)
697 lmgr_thread_t *self = lmgr_get_thread_info();
702 void *(*start_routine)(void*);
707 void *lmgr_thread_launcher(void *x)
711 pthread_cleanup_push(cln_hdl, NULL);
713 lmgr_thread_arg_t arg;
714 lmgr_thread_arg_t *a = (lmgr_thread_arg_t *)x;
715 arg.start_routine = a->start_routine;
719 ret = arg.start_routine(arg.arg);
720 pthread_cleanup_pop(1);
724 int lmgr_thread_create(pthread_t *thread,
725 const pthread_attr_t *attr,
726 void *(*start_routine)(void*), void *arg)
728 /* lmgr should be active (lmgr_init_thread() call in main()) */
729 ASSERT(lmgr_is_active());
730 /* Will be freed by the child */
731 lmgr_thread_arg_t *a = (lmgr_thread_arg_t*) malloc(sizeof(lmgr_thread_arg_t));
732 a->start_routine = start_routine;
734 return pthread_create(thread, attr, lmgr_thread_launcher, a);
737 #else /* _USE_LOCKMGR */
741 * Use this function is used only after a fatal signal
742 * We don't use locking to display information
744 void dbg_print_lock(FILE *fp)
746 Pmsg0(000, "lockmgr disabled\n");
749 #endif /* _USE_LOCKMGR */
754 #define pthread_mutex_lock(x) lmgr_mutex_lock(x)
755 #define pthread_mutex_unlock(x) lmgr_mutex_unlock(x)
756 #define pthread_cond_wait(x,y) lmgr_cond_wait(x,y)
757 #define pthread_create(a, b, c, d) lmgr_thread_create(a,b,c,d)
760 #define P(x) lmgr_mutex_lock(&(x), __FILE__, __LINE__)
761 #define V(x) lmgr_mutex_unlock(&(x), __FILE__, __LINE__)
763 pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
764 pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
765 pthread_mutex_t mutex3 = PTHREAD_MUTEX_INITIALIZER;
766 pthread_mutex_t mutex4 = PTHREAD_MUTEX_INITIALIZER;
767 pthread_mutex_t mutex5 = PTHREAD_MUTEX_INITIALIZER;
768 pthread_mutex_t mutex6 = PTHREAD_MUTEX_INITIALIZER;
770 void *self_lock(void *temp)
779 void *nolock(void *temp)
787 void *locker(void *temp)
789 pthread_mutex_t *m = (pthread_mutex_t*) temp;
795 void *rwlocker(void *temp)
797 brwlock_t *m = (brwlock_t*) temp;
806 void *mix_rwl_mutex(void *temp)
808 brwlock_t *m = (brwlock_t*) temp;
817 void *th2(void *temp)
832 void *th1(void *temp)
849 void *thx(void *temp)
851 int s= 1 + (int) (500.0 * (rand() / (RAND_MAX + 1.0))) + 200;
864 fprintf(stderr, "undertaker sleep()\n");
867 if (lmgr_detect_deadlock()) {
877 void _ok(const char *file, int l, const char *op, int value, const char *label)
882 printf("ERR %.30s %s:%i on %s\n", label, file, l, op);
884 printf("OK %.30s\n", label);
888 #define ok(x, label) _ok(__FILE__, __LINE__, #x, (x), label)
890 void _nok(const char *file, int l, const char *op, int value, const char *label)
895 printf("ERR %.30s %s:%i on !%s\n", label, file, l, op);
897 printf("OK %.30s\n", label);
901 #define nok(x, label) _nok(__FILE__, __LINE__, #x, (x), label)
905 printf("Result %i/%i OK\n", nb - err, nb);
911 * - Must detect multiple lock
912 * - lock/unlock in wrong order
913 * - deadlock with 2 or 3 threads
917 pthread_t id1, id2, id3, tab[200];
920 pthread_create(&id1, NULL, self_lock, NULL);
922 ok(lmgr_detect_deadlock(), "Check self deadlock");
923 lmgr_v(&mutex1); /* a bit dirty */
924 pthread_join(id1, NULL);
927 pthread_create(&id1, NULL, nolock, NULL);
929 nok(lmgr_detect_deadlock(), "Check for nolock");
930 pthread_join(id1, NULL);
933 pthread_create(&id1, NULL, locker, &mutex1);
934 pthread_create(&id2, NULL, locker, &mutex1);
935 pthread_create(&id3, NULL, locker, &mutex1);
937 nok(lmgr_detect_deadlock(), "Check for multiple lock");
939 pthread_join(id1, NULL);
940 pthread_join(id2, NULL);
941 pthread_join(id3, NULL);
948 pthread_create(&id1, NULL, rwlocker, &wr);
949 pthread_create(&id2, NULL, rwlocker, &wr);
950 pthread_create(&id3, NULL, rwlocker, &wr);
951 nok(lmgr_detect_deadlock(), "Check for multiple rwlock");
952 rwl_writeunlock(&wr);
953 nok(lmgr_detect_deadlock(), "Check for simple rwlock");
954 rwl_writeunlock(&wr);
955 nok(lmgr_detect_deadlock(), "Check for multiple rwlock");
957 pthread_join(id1, NULL);
958 pthread_join(id2, NULL);
959 pthread_join(id3, NULL);
963 pthread_create(&id1, NULL, mix_rwl_mutex, &wr);
964 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
966 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
967 rwl_writeunlock(&wr);
968 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
969 pthread_join(id1, NULL);
976 nok(lmgr_detect_deadlock(), "Check for wrong order");
978 for(int j=0; j<200; j++) {
979 pthread_create(&tab[j], NULL, thx, NULL);
981 for(int j=0; j<200; j++) {
982 pthread_join(tab[j], NULL);
983 if (j%3) { lmgr_detect_deadlock();}
985 nok(lmgr_detect_deadlock(), "Check 200 lockers");
994 pthread_create(&id1, NULL, th1, NULL);
996 pthread_create(&id2, NULL, th2, NULL);
998 ok(lmgr_detect_deadlock(), "Check for deadlock");
1002 // pthread_create(&id3, NULL, th3, NULL);
1004 // pthread_join(id1, NULL);
1005 // pthread_join(id2, NULL);
1006 lmgr_cleanup_main();
1007 sm_check(__FILE__, __LINE__, false);