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()
603 pthread_cancel(undertaker);
604 lmgr_cleanup_thread();
605 pthread_mutex_lock(&lmgr_global_mutex);
611 pthread_mutex_unlock(&lmgr_global_mutex);
615 * Replacement for pthread_mutex_lock()
617 int lmgr_mutex_lock(pthread_mutex_t *m, const char *file, int line)
620 lmgr_thread_t *self = lmgr_get_thread_info();
621 self->pre_P(m, file, line);
622 ret = pthread_mutex_lock(m);
628 * Replacement for pthread_mutex_unlock()
630 int lmgr_mutex_unlock(pthread_mutex_t *m, const char *file, int line)
632 lmgr_thread_t *self = lmgr_get_thread_info();
633 self->do_V(m, file, line);
634 return pthread_mutex_unlock(m);
639 int lmgr_cond_wait(pthread_cond_t *cond,
640 pthread_mutex_t *mutex)
643 lmgr_thread_t *self = lmgr_get_thread_info();
645 ret = pthread_cond_wait(cond, mutex);
652 * Use this function when the caller handle the mutex directly
655 * pthread_mutex_lock(m);
658 void lmgr_pre_lock(void *m)
660 lmgr_thread_t *self = lmgr_get_thread_info();
665 * Use this function when the caller handle the mutex directly
667 void lmgr_post_lock()
669 lmgr_thread_t *self = lmgr_get_thread_info();
674 * Do directly pre_P and post_P (used by trylock)
676 void lmgr_do_lock(void *m)
678 lmgr_thread_t *self = lmgr_get_thread_info();
684 * Use this function when the caller handle the mutex directly
686 void lmgr_do_unlock(void *m)
688 lmgr_thread_t *self = lmgr_get_thread_info();
693 void *(*start_routine)(void*);
698 void *lmgr_thread_launcher(void *x)
702 pthread_cleanup_push(cln_hdl, NULL);
704 lmgr_thread_arg_t arg;
705 lmgr_thread_arg_t *a = (lmgr_thread_arg_t *)x;
706 arg.start_routine = a->start_routine;
710 ret = arg.start_routine(arg.arg);
711 pthread_cleanup_pop(1);
715 int lmgr_thread_create(pthread_t *thread,
716 const pthread_attr_t *attr,
717 void *(*start_routine)(void*), void *arg)
719 /* Will be freed by the child */
720 lmgr_thread_arg_t *a = (lmgr_thread_arg_t*) malloc(sizeof(lmgr_thread_arg_t));
721 a->start_routine = start_routine;
723 return pthread_create(thread, attr, lmgr_thread_launcher, a);
726 #else /* _USE_LOCKMGR */
730 * Use this function only after a fatal signal
731 * We don't use any lock to display information
733 void dbg_print_lock(FILE *fp)
735 Pmsg0(000, "lockmgr disabled\n");
738 #endif /* _USE_LOCKMGR */
743 #define pthread_mutex_lock(x) lmgr_mutex_lock(x)
744 #define pthread_mutex_unlock(x) lmgr_mutex_unlock(x)
745 #define pthread_cond_wait(x,y) lmgr_cond_wait(x,y)
746 #define pthread_create(a, b, c, d) lmgr_thread_create(a,b,c,d)
749 #define P(x) lmgr_mutex_lock(&(x), __FILE__, __LINE__)
750 #define V(x) lmgr_mutex_unlock(&(x), __FILE__, __LINE__)
752 pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
753 pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
754 pthread_mutex_t mutex3 = PTHREAD_MUTEX_INITIALIZER;
755 pthread_mutex_t mutex4 = PTHREAD_MUTEX_INITIALIZER;
756 pthread_mutex_t mutex5 = PTHREAD_MUTEX_INITIALIZER;
757 pthread_mutex_t mutex6 = PTHREAD_MUTEX_INITIALIZER;
759 void *self_lock(void *temp)
768 void *nolock(void *temp)
776 void *locker(void *temp)
778 pthread_mutex_t *m = (pthread_mutex_t*) temp;
779 pthread_mutex_lock(m);
780 pthread_mutex_unlock(m);
784 void *rwlocker(void *temp)
786 brwlock_t *m = (brwlock_t*) temp;
795 void *mix_rwl_mutex(void *temp)
797 brwlock_t *m = (brwlock_t*) temp;
806 void *th2(void *temp)
821 void *th1(void *temp)
838 void *thx(void *temp)
840 int s= 1 + (int) (500.0 * (rand() / (RAND_MAX + 1.0))) + 200;
853 fprintf(stderr, "undertaker sleep()\n");
856 if (lmgr_detect_deadlock()) {
866 void _ok(const char *file, int l, const char *op, int value, const char *label)
871 printf("ERR %.30s %s:%i on %s\n", label, file, l, op);
873 printf("OK %.30s\n", label);
877 #define ok(x, label) _ok(__FILE__, __LINE__, #x, (x), label)
879 void _nok(const char *file, int l, const char *op, int value, const char *label)
884 printf("ERR %.30s %s:%i on !%s\n", label, file, l, op);
886 printf("OK %.30s\n", label);
890 #define nok(x, label) _nok(__FILE__, __LINE__, #x, (x), label)
894 printf("Result %i/%i OK\n", nb - err, nb);
900 * - Must detect multiple lock
901 * - lock/unlock in wrong order
902 * - deadlock with 2 or 3 threads
906 pthread_t id1, id2, id3, tab[200];
909 pthread_create(&id1, NULL, self_lock, NULL);
911 ok(lmgr_detect_deadlock(), "Check self deadlock");
912 lmgr_v(&mutex1); /* a bit dirty */
913 pthread_join(id1, NULL);
916 pthread_create(&id1, NULL, nolock, NULL);
918 nok(lmgr_detect_deadlock(), "Check for nolock");
919 pthread_join(id1, NULL);
922 pthread_create(&id1, NULL, locker, &mutex1);
923 pthread_create(&id2, NULL, locker, &mutex1);
924 pthread_create(&id3, NULL, locker, &mutex1);
926 nok(lmgr_detect_deadlock(), "Check for multiple lock");
928 pthread_join(id1, NULL);
929 pthread_join(id2, NULL);
930 pthread_join(id3, NULL);
937 pthread_create(&id1, NULL, rwlocker, &wr);
938 pthread_create(&id2, NULL, rwlocker, &wr);
939 pthread_create(&id3, NULL, rwlocker, &wr);
940 nok(lmgr_detect_deadlock(), "Check for multiple rwlock");
941 rwl_writeunlock(&wr);
942 nok(lmgr_detect_deadlock(), "Check for simple rwlock");
943 rwl_writeunlock(&wr);
944 nok(lmgr_detect_deadlock(), "Check for multiple rwlock");
946 pthread_join(id1, NULL);
947 pthread_join(id2, NULL);
948 pthread_join(id3, NULL);
952 pthread_create(&id1, NULL, mix_rwl_mutex, &wr);
953 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
955 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
956 rwl_writeunlock(&wr);
957 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
958 pthread_join(id1, NULL);
965 nok(lmgr_detect_deadlock(), "Check for wrong order");
967 for(int j=0; j<200; j++) {
968 pthread_create(&tab[j], NULL, thx, NULL);
970 for(int j=0; j<200; j++) {
971 pthread_join(tab[j], NULL);
972 if (j%3) { lmgr_detect_deadlock();}
974 nok(lmgr_detect_deadlock(), "Check 200 lockers");
983 pthread_create(&id1, NULL, th1, NULL);
985 pthread_create(&id2, NULL, th2, NULL);
987 ok(lmgr_detect_deadlock(), "Check for deadlock");
991 // pthread_create(&id3, NULL, th3, NULL);
993 // pthread_join(id1, NULL);
994 // pthread_join(id2, NULL);
996 sm_check(__FILE__, __LINE__, false);