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=0x%x max=%i current=%i\n", (int)thread_id, max, current);
247 for(int i=0; i<=current; i++) {
248 fprintf(fp, " lock=%p state=%c %s:%i\n",
249 lock_list[i].lock, lock_list[i].state,
250 lock_list[i].file, lock_list[i].line);
254 void dump(FILE *fp) {
255 pthread_mutex_lock(&mutex);
259 pthread_mutex_unlock(&mutex);
263 * Call before a lock operation (mark mutex as WANTED)
265 virtual void pre_P(void *m, const char *f="*unknown*", int l=0) {
266 ASSERT(current < LMGR_MAX_LOCK);
267 ASSERT(current >= -1);
268 pthread_mutex_lock(&mutex);
271 lock_list[current].lock = m;
272 lock_list[current].state = LMGR_LOCK_WANTED;
273 lock_list[current].file = f;
274 lock_list[current].line = l;
275 max = MAX(current, max);
277 pthread_mutex_unlock(&mutex);
281 * Call after the lock operation (mark mutex as GRANTED)
283 virtual void post_P() {
284 ASSERT(current >= 0);
285 ASSERT(lock_list[current].state == LMGR_LOCK_WANTED);
286 lock_list[current].state = LMGR_LOCK_GRANTED;
289 void shift_list(int i) {
290 for(int j=i+1; j<=current; j++) {
291 lock_list[i] = lock_list[j];
294 lock_list[current].lock = NULL;
295 lock_list[current].state = LMGR_LOCK_EMPTY;
300 * Remove the mutex from the list
302 virtual void do_V(void *m, const char *f="*unknown*", int l=0) {
303 ASSERT(current >= 0);
304 pthread_mutex_lock(&mutex);
306 if (lock_list[current].lock == m) {
307 lock_list[current].lock = NULL;
308 lock_list[current].state = LMGR_LOCK_EMPTY;
312 Pmsg3(0, "ERROR: wrong P/V order search lock=%p %s:%i\n", m, f, l);
313 Pmsg4(000, "ERROR: wrong P/V order pos=%i lock=%p %s:%i\n",
314 current, lock_list[current].lock, lock_list[current].file,
315 lock_list[current].line);
316 for (int i=current-1; i >= 0; i--) { /* already seen current */
317 Pmsg4(000, "ERROR: wrong P/V order pos=%i lock=%p %s:%i\n",
318 i, lock_list[i].lock, lock_list[i].file, lock_list[i].line);
319 if (lock_list[i].lock == m) {
320 Pmsg3(000, "ERROR: FOUND P pos=%i %s:%i\n", i, f, l);
328 pthread_mutex_unlock(&mutex);
331 virtual ~lmgr_thread_t() {destroy();}
334 pthread_mutex_destroy(&mutex);
338 class lmgr_dummy_thread_t: public lmgr_thread_t
340 void do_V(void *m, const char *file, int l) {}
342 void pre_P(void *m, const char *file, int l) {}
346 * LMGR - Lock Manager
352 pthread_once_t key_lmgr_once = PTHREAD_ONCE_INIT;
353 static pthread_key_t lmgr_key; /* used to get lgmr_thread_t object */
355 static dlist *global_mgr=NULL; /* used to store all lgmr_thread_t objects */
356 static pthread_mutex_t lmgr_global_mutex = PTHREAD_MUTEX_INITIALIZER;
357 static pthread_t undertaker;
359 #define lmgr_is_active() (global_mgr != NULL)
362 * Add a new lmgr_thread_t object to the global list
364 void lmgr_register_thread(lmgr_thread_t *item)
366 pthread_mutex_lock(&lmgr_global_mutex);
368 global_mgr->prepend(item);
370 pthread_mutex_unlock(&lmgr_global_mutex);
374 * Call this function to cleanup specific lock thread data
376 void lmgr_unregister_thread(lmgr_thread_t *item)
378 if (!lmgr_is_active()) {
381 pthread_mutex_lock(&lmgr_global_mutex);
383 global_mgr->remove(item);
385 pthread_mutex_unlock(&lmgr_global_mutex);
389 * Search for a deadlock when it's secure to walk across
390 * locks list. (after lmgr_detect_deadlock or a fatal signal)
392 bool lmgr_detect_deadlock_unlocked()
395 lmgr_node_t *node=NULL;
398 dlist *g = New(dlist(node, &node->link));
400 /* First, get a list of all node */
401 foreach_dlist(item, global_mgr) {
402 for(int i=0; i<=item->current; i++) {
404 lock = &item->lock_list[i];
405 /* Depending if the lock is granted or not, it's a child or a root
406 * Granted: Mutex -> Thread
407 * Wanted: Thread -> Mutex
409 * Note: a Mutex can be locked only once, a thread can request only
413 if (lock->state == LMGR_LOCK_GRANTED) {
414 node = New(lmgr_node_t((void*)lock->lock, (void*)item->thread_id));
415 } else if (lock->state == LMGR_LOCK_WANTED) {
416 node = New(lmgr_node_t((void*)item->thread_id, (void*)lock->lock));
424 //foreach_dlist(node, g) {
425 // printf("g n=%p c=%p\n", node->node, node->child);
428 ret = contains_cycle(g);
430 printf("Found a deadlock !!!!\n");
438 * Search for a deadlock in during the runtime
439 * It will lock all thread specific lock manager, nothing
440 * can be locked during this check.
442 bool lmgr_detect_deadlock()
445 if (!lmgr_is_active()) {
449 pthread_mutex_lock(&lmgr_global_mutex);
452 foreach_dlist(item, global_mgr) {
453 pthread_mutex_lock(&item->mutex);
456 ret = lmgr_detect_deadlock_unlocked();
458 foreach_dlist(item, global_mgr) {
459 pthread_mutex_unlock(&item->mutex);
462 pthread_mutex_unlock(&lmgr_global_mutex);
469 * Use this function only after a fatal signal
470 * We don't use any lock to display information
472 void dbg_print_lock(FILE *fp)
474 fprintf(fp, "Attempt to dump locks\n");
475 if (!lmgr_is_active()) {
479 foreach_dlist(item, global_mgr) {
485 * Dump each lmgr_thread_t object
489 pthread_mutex_lock(&lmgr_global_mutex);
492 foreach_dlist(item, global_mgr) {
496 pthread_mutex_unlock(&lmgr_global_mutex);
499 void cln_hdl(void *a)
501 lmgr_cleanup_thread();
504 void *check_deadlock(void *)
508 pthread_cleanup_push(cln_hdl, NULL);
510 while (!bmicrosleep(30, 0)) {
511 pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &old);
512 if (lmgr_detect_deadlock()) {
516 pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, &old);
517 pthread_testcancel();
519 Pmsg0(000, "Undertaker is leaving...\n");
520 pthread_cleanup_pop(1);
524 /* This object is used when LMGR is not initialized */
525 lmgr_dummy_thread_t dummy_lmgr;
528 * Retrieve the lmgr_thread_t object from the stack
530 inline lmgr_thread_t *lmgr_get_thread_info()
532 if (lmgr_is_active()) {
533 return (lmgr_thread_t *)pthread_getspecific(lmgr_key);
540 * launch once for all threads
542 void create_lmgr_key()
544 int status = pthread_key_create(&lmgr_key, NULL);
547 Pmsg1(000, _("pthread key create failed: ERR=%s\n"),
548 be.bstrerror(status));
552 lmgr_thread_t *n=NULL;
553 global_mgr = New(dlist(n, &n->link));
555 if (pthread_create(&undertaker, NULL, check_deadlock, NULL) != 0) {
557 Pmsg1(000, _("pthread_create failed: ERR=%s\n"),
558 be.bstrerror(status));
564 * Each thread have to call this function to put a lmgr_thread_t object
565 * in the stack and be able to call mutex_lock/unlock
567 void lmgr_init_thread()
569 int status = pthread_once(&key_lmgr_once, create_lmgr_key);
572 Pmsg1(000, _("pthread key create failed: ERR=%s\n"),
573 be.bstrerror(status));
576 lmgr_thread_t *l = New(lmgr_thread_t());
577 pthread_setspecific(lmgr_key, l);
578 lmgr_register_thread(l);
582 * Call this function at the end of the thread
584 void lmgr_cleanup_thread()
586 if (!lmgr_is_active()) {
589 lmgr_thread_t *self = lmgr_get_thread_info();
590 lmgr_unregister_thread(self);
595 * This function should be call at the end of the main thread
596 * Some thread like the watchdog are already present, so the global_mgr
597 * list is never empty. Should carefully clear the memory.
599 void lmgr_cleanup_main()
606 pthread_cancel(undertaker);
607 lmgr_cleanup_thread();
608 pthread_mutex_lock(&lmgr_global_mutex);
614 pthread_mutex_unlock(&lmgr_global_mutex);
618 * Replacement for pthread_mutex_lock()
620 int lmgr_mutex_lock(pthread_mutex_t *m, const char *file, int line)
623 lmgr_thread_t *self = lmgr_get_thread_info();
624 self->pre_P(m, file, line);
625 ret = pthread_mutex_lock(m);
631 * Replacement for pthread_mutex_unlock()
633 int lmgr_mutex_unlock(pthread_mutex_t *m, const char *file, int line)
635 lmgr_thread_t *self = lmgr_get_thread_info();
636 self->do_V(m, file, line);
637 return pthread_mutex_unlock(m);
642 int lmgr_cond_wait(pthread_cond_t *cond,
643 pthread_mutex_t *mutex,
644 const char *file, int line)
647 lmgr_thread_t *self = lmgr_get_thread_info();
648 self->do_V(mutex, file, line);
649 ret = pthread_cond_wait(cond, mutex);
650 self->pre_P(mutex, file, line);
656 * Use this function when the caller handle the mutex directly
659 * pthread_mutex_lock(m);
662 void lmgr_pre_lock(void *m, const char *file, int line)
664 lmgr_thread_t *self = lmgr_get_thread_info();
665 self->pre_P(m, file, line);
669 * Use this function when the caller handle the mutex directly
671 void lmgr_post_lock()
673 lmgr_thread_t *self = lmgr_get_thread_info();
678 * Do directly pre_P and post_P (used by trylock)
680 void lmgr_do_lock(void *m, const char *file, int line)
682 lmgr_thread_t *self = lmgr_get_thread_info();
683 self->pre_P(m, file, line);
688 * Use this function when the caller handle the mutex directly
690 void lmgr_do_unlock(void *m)
692 lmgr_thread_t *self = lmgr_get_thread_info();
697 void *(*start_routine)(void*);
702 void *lmgr_thread_launcher(void *x)
706 pthread_cleanup_push(cln_hdl, NULL);
708 lmgr_thread_arg_t arg;
709 lmgr_thread_arg_t *a = (lmgr_thread_arg_t *)x;
710 arg.start_routine = a->start_routine;
714 ret = arg.start_routine(arg.arg);
715 pthread_cleanup_pop(1);
719 int lmgr_thread_create(pthread_t *thread,
720 const pthread_attr_t *attr,
721 void *(*start_routine)(void*), void *arg)
723 /* Will be freed by the child */
724 lmgr_thread_arg_t *a = (lmgr_thread_arg_t*) malloc(sizeof(lmgr_thread_arg_t));
725 a->start_routine = start_routine;
727 return pthread_create(thread, attr, lmgr_thread_launcher, a);
730 #else /* _USE_LOCKMGR */
734 * Use this function only after a fatal signal
735 * We don't use any lock to display information
737 void dbg_print_lock(FILE *fp)
739 Pmsg0(000, "lockmgr disabled\n");
742 #endif /* _USE_LOCKMGR */
747 #define pthread_mutex_lock(x) lmgr_mutex_lock(x)
748 #define pthread_mutex_unlock(x) lmgr_mutex_unlock(x)
749 #define pthread_cond_wait(x,y) lmgr_cond_wait(x,y)
750 #define pthread_create(a, b, c, d) lmgr_thread_create(a,b,c,d)
753 #define P(x) lmgr_mutex_lock(&(x), __FILE__, __LINE__)
754 #define V(x) lmgr_mutex_unlock(&(x), __FILE__, __LINE__)
756 pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
757 pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
758 pthread_mutex_t mutex3 = PTHREAD_MUTEX_INITIALIZER;
759 pthread_mutex_t mutex4 = PTHREAD_MUTEX_INITIALIZER;
760 pthread_mutex_t mutex5 = PTHREAD_MUTEX_INITIALIZER;
761 pthread_mutex_t mutex6 = PTHREAD_MUTEX_INITIALIZER;
763 void *self_lock(void *temp)
772 void *nolock(void *temp)
780 void *locker(void *temp)
782 pthread_mutex_t *m = (pthread_mutex_t*) temp;
783 pthread_mutex_lock(m);
784 pthread_mutex_unlock(m);
788 void *rwlocker(void *temp)
790 brwlock_t *m = (brwlock_t*) temp;
799 void *mix_rwl_mutex(void *temp)
801 brwlock_t *m = (brwlock_t*) temp;
810 void *th2(void *temp)
825 void *th1(void *temp)
842 void *thx(void *temp)
844 int s= 1 + (int) (500.0 * (rand() / (RAND_MAX + 1.0))) + 200;
857 fprintf(stderr, "undertaker sleep()\n");
860 if (lmgr_detect_deadlock()) {
870 void _ok(const char *file, int l, const char *op, int value, const char *label)
875 printf("ERR %.30s %s:%i on %s\n", label, file, l, op);
877 printf("OK %.30s\n", label);
881 #define ok(x, label) _ok(__FILE__, __LINE__, #x, (x), label)
883 void _nok(const char *file, int l, const char *op, int value, const char *label)
888 printf("ERR %.30s %s:%i on !%s\n", label, file, l, op);
890 printf("OK %.30s\n", label);
894 #define nok(x, label) _nok(__FILE__, __LINE__, #x, (x), label)
898 printf("Result %i/%i OK\n", nb - err, nb);
904 * - Must detect multiple lock
905 * - lock/unlock in wrong order
906 * - deadlock with 2 or 3 threads
910 pthread_t id1, id2, id3, tab[200];
913 pthread_create(&id1, NULL, self_lock, NULL);
915 ok(lmgr_detect_deadlock(), "Check self deadlock");
916 lmgr_v(&mutex1); /* a bit dirty */
917 pthread_join(id1, NULL);
920 pthread_create(&id1, NULL, nolock, NULL);
922 nok(lmgr_detect_deadlock(), "Check for nolock");
923 pthread_join(id1, NULL);
926 pthread_create(&id1, NULL, locker, &mutex1);
927 pthread_create(&id2, NULL, locker, &mutex1);
928 pthread_create(&id3, NULL, locker, &mutex1);
930 nok(lmgr_detect_deadlock(), "Check for multiple lock");
932 pthread_join(id1, NULL);
933 pthread_join(id2, NULL);
934 pthread_join(id3, NULL);
941 pthread_create(&id1, NULL, rwlocker, &wr);
942 pthread_create(&id2, NULL, rwlocker, &wr);
943 pthread_create(&id3, NULL, rwlocker, &wr);
944 nok(lmgr_detect_deadlock(), "Check for multiple rwlock");
945 rwl_writeunlock(&wr);
946 nok(lmgr_detect_deadlock(), "Check for simple rwlock");
947 rwl_writeunlock(&wr);
948 nok(lmgr_detect_deadlock(), "Check for multiple rwlock");
950 pthread_join(id1, NULL);
951 pthread_join(id2, NULL);
952 pthread_join(id3, NULL);
956 pthread_create(&id1, NULL, mix_rwl_mutex, &wr);
957 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
959 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
960 rwl_writeunlock(&wr);
961 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
962 pthread_join(id1, NULL);
969 nok(lmgr_detect_deadlock(), "Check for wrong order");
971 for(int j=0; j<200; j++) {
972 pthread_create(&tab[j], NULL, thx, NULL);
974 for(int j=0; j<200; j++) {
975 pthread_join(tab[j], NULL);
976 if (j%3) { lmgr_detect_deadlock();}
978 nok(lmgr_detect_deadlock(), "Check 200 lockers");
987 pthread_create(&id1, NULL, th1, NULL);
989 pthread_create(&id2, NULL, th2, NULL);
991 ok(lmgr_detect_deadlock(), "Check for deadlock");
995 // pthread_create(&id3, NULL, th3, NULL);
997 // pthread_join(id1, NULL);
998 // pthread_join(id2, NULL);
1000 sm_check(__FILE__, __LINE__, false);