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=%c %s:%i\n",
250 lock_list[i].lock, lock_list[i].state,
251 lock_list[i].file, lock_list[i].line);
255 void dump(FILE *fp) {
256 pthread_mutex_lock(&mutex);
260 pthread_mutex_unlock(&mutex);
264 * Call before a lock operation (mark mutex as WANTED)
266 virtual void pre_P(void *m, const char *f="*unknown*", int l=0) {
267 ASSERT(current < LMGR_MAX_LOCK);
268 ASSERT(current >= -1);
269 pthread_mutex_lock(&mutex);
272 lock_list[current].lock = m;
273 lock_list[current].state = LMGR_LOCK_WANTED;
274 lock_list[current].file = f;
275 lock_list[current].line = l;
276 max = MAX(current, max);
278 pthread_mutex_unlock(&mutex);
282 * Call after the lock operation (mark mutex as GRANTED)
284 virtual void post_P() {
285 ASSERT(current >= 0);
286 ASSERT(lock_list[current].state == LMGR_LOCK_WANTED);
287 lock_list[current].state = LMGR_LOCK_GRANTED;
290 void shift_list(int i) {
291 for(int j=i+1; j<=current; j++) {
292 lock_list[i] = lock_list[j];
295 lock_list[current].lock = NULL;
296 lock_list[current].state = LMGR_LOCK_EMPTY;
301 * Remove the mutex from the list
303 virtual void do_V(void *m, const char *f="*unknown*", int l=0) {
304 ASSERT(current >= 0);
305 pthread_mutex_lock(&mutex);
307 if (lock_list[current].lock == m) {
308 lock_list[current].lock = NULL;
309 lock_list[current].state = LMGR_LOCK_EMPTY;
313 Pmsg3(0, "ERROR: wrong P/V order search lock=%p %s:%i\n", m, f, l);
314 Pmsg4(000, "ERROR: wrong P/V order pos=%i lock=%p %s:%i\n",
315 current, lock_list[current].lock, lock_list[current].file,
316 lock_list[current].line);
317 for (int i=current-1; i >= 0; i--) { /* already seen current */
318 Pmsg4(000, "ERROR: wrong P/V order pos=%i lock=%p %s:%i\n",
319 i, lock_list[i].lock, lock_list[i].file, lock_list[i].line);
320 if (lock_list[i].lock == m) {
321 Pmsg3(000, "ERROR: FOUND P pos=%i %s:%i\n", i, f, l);
329 pthread_mutex_unlock(&mutex);
332 virtual ~lmgr_thread_t() {destroy();}
335 pthread_mutex_destroy(&mutex);
339 class lmgr_dummy_thread_t: public lmgr_thread_t
341 void do_V(void *m, const char *file, int l) {}
343 void pre_P(void *m, const char *file, int l) {}
347 * LMGR - Lock Manager
353 pthread_once_t key_lmgr_once = PTHREAD_ONCE_INIT;
354 static pthread_key_t lmgr_key; /* used to get lgmr_thread_t object */
356 static dlist *global_mgr=NULL; /* used to store all lgmr_thread_t objects */
357 static pthread_mutex_t lmgr_global_mutex = PTHREAD_MUTEX_INITIALIZER;
358 static pthread_t undertaker;
360 #define lmgr_is_active() (global_mgr != NULL)
363 * Add a new lmgr_thread_t object to the global list
365 void lmgr_register_thread(lmgr_thread_t *item)
367 pthread_mutex_lock(&lmgr_global_mutex);
369 global_mgr->prepend(item);
371 pthread_mutex_unlock(&lmgr_global_mutex);
375 * Call this function to cleanup specific lock thread data
377 void lmgr_unregister_thread(lmgr_thread_t *item)
379 if (!lmgr_is_active()) {
382 pthread_mutex_lock(&lmgr_global_mutex);
384 global_mgr->remove(item);
386 pthread_mutex_unlock(&lmgr_global_mutex);
390 * Search for a deadlock when it's secure to walk across
391 * locks list. (after lmgr_detect_deadlock or a fatal signal)
393 bool lmgr_detect_deadlock_unlocked()
396 lmgr_node_t *node=NULL;
399 dlist *g = New(dlist(node, &node->link));
401 /* First, get a list of all node */
402 foreach_dlist(item, global_mgr) {
403 for(int i=0; i<=item->current; i++) {
405 lock = &item->lock_list[i];
406 /* Depending if the lock is granted or not, it's a child or a root
407 * Granted: Mutex -> Thread
408 * Wanted: Thread -> Mutex
410 * Note: a Mutex can be locked only once, a thread can request only
414 if (lock->state == LMGR_LOCK_GRANTED) {
415 node = New(lmgr_node_t((void*)lock->lock, (void*)item->thread_id));
416 } else if (lock->state == LMGR_LOCK_WANTED) {
417 node = New(lmgr_node_t((void*)item->thread_id, (void*)lock->lock));
425 //foreach_dlist(node, g) {
426 // printf("g n=%p c=%p\n", node->node, node->child);
429 ret = contains_cycle(g);
431 printf("Found a deadlock !!!!\n");
439 * Search for a deadlock in during the runtime
440 * It will lock all thread specific lock manager, nothing
441 * can be locked during this check.
443 bool lmgr_detect_deadlock()
446 if (!lmgr_is_active()) {
450 pthread_mutex_lock(&lmgr_global_mutex);
453 foreach_dlist(item, global_mgr) {
454 pthread_mutex_lock(&item->mutex);
457 ret = lmgr_detect_deadlock_unlocked();
459 foreach_dlist(item, global_mgr) {
460 pthread_mutex_unlock(&item->mutex);
463 pthread_mutex_unlock(&lmgr_global_mutex);
470 * Use this function is used only after a fatal signal
471 * We don't use locking to display the information
473 void dbg_print_lock(FILE *fp)
475 fprintf(fp, "Attempt to dump locks\n");
476 if (!lmgr_is_active()) {
480 foreach_dlist(item, global_mgr) {
486 * Dump each lmgr_thread_t object
490 pthread_mutex_lock(&lmgr_global_mutex);
493 foreach_dlist(item, global_mgr) {
497 pthread_mutex_unlock(&lmgr_global_mutex);
500 void cln_hdl(void *a)
502 lmgr_cleanup_thread();
505 void *check_deadlock(void *)
509 pthread_cleanup_push(cln_hdl, NULL);
511 while (!bmicrosleep(30, 0)) {
512 pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &old);
513 if (lmgr_detect_deadlock()) {
517 pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, &old);
518 pthread_testcancel();
520 Pmsg0(000, "Undertaker is leaving...\n");
521 pthread_cleanup_pop(1);
525 /* This object is used when LMGR is not initialized */
526 static lmgr_dummy_thread_t dummy_lmgr;
529 * Retrieve the lmgr_thread_t object from the stack
531 inline lmgr_thread_t *lmgr_get_thread_info()
533 if (lmgr_is_active()) {
534 return (lmgr_thread_t *)pthread_getspecific(lmgr_key);
541 * launch once for all threads
543 void create_lmgr_key()
545 int status = pthread_key_create(&lmgr_key, NULL);
548 Pmsg1(000, _("pthread key create failed: ERR=%s\n"),
549 be.bstrerror(status));
553 lmgr_thread_t *n=NULL;
554 global_mgr = New(dlist(n, &n->link));
556 if (pthread_create(&undertaker, NULL, check_deadlock, NULL) != 0) {
558 Pmsg1(000, _("pthread_create failed: ERR=%s\n"),
559 be.bstrerror(status));
565 * Each thread have to call this function to put a lmgr_thread_t object
566 * in the stack and be able to call mutex_lock/unlock
568 void lmgr_init_thread()
570 int status = pthread_once(&key_lmgr_once, create_lmgr_key);
573 Pmsg1(000, _("pthread key create failed: ERR=%s\n"),
574 be.bstrerror(status));
577 lmgr_thread_t *l = New(lmgr_thread_t());
578 pthread_setspecific(lmgr_key, l);
579 lmgr_register_thread(l);
583 * Call this function at the end of the thread
585 void lmgr_cleanup_thread()
587 if (!lmgr_is_active()) {
590 lmgr_thread_t *self = lmgr_get_thread_info();
591 lmgr_unregister_thread(self);
596 * This function should be call at the end of the main thread
597 * Some thread like the watchdog are already present, so the global_mgr
598 * list is never empty. Should carefully clear the memory.
600 void lmgr_cleanup_main()
607 pthread_cancel(undertaker);
608 lmgr_cleanup_thread();
609 pthread_mutex_lock(&lmgr_global_mutex);
615 pthread_mutex_unlock(&lmgr_global_mutex);
619 * Replacement for pthread_mutex_lock()
621 int lmgr_mutex_lock(pthread_mutex_t *m, const char *file, int line)
624 lmgr_thread_t *self = lmgr_get_thread_info();
625 self->pre_P(m, file, line);
626 ret = pthread_mutex_lock(m);
632 * Replacement for pthread_mutex_unlock()
634 int lmgr_mutex_unlock(pthread_mutex_t *m, const char *file, int line)
636 lmgr_thread_t *self = lmgr_get_thread_info();
637 self->do_V(m, file, line);
638 return pthread_mutex_unlock(m);
643 int lmgr_cond_wait(pthread_cond_t *cond,
644 pthread_mutex_t *mutex,
645 const char *file, int line)
648 lmgr_thread_t *self = lmgr_get_thread_info();
649 self->do_V(mutex, file, line);
650 ret = pthread_cond_wait(cond, mutex);
651 self->pre_P(mutex, file, line);
657 * Use this function when the caller handle the mutex directly
660 * pthread_mutex_lock(m);
663 void lmgr_pre_lock(void *m, const char *file, int line)
665 lmgr_thread_t *self = lmgr_get_thread_info();
666 self->pre_P(m, file, line);
670 * Use this function when the caller handle the mutex directly
672 void lmgr_post_lock()
674 lmgr_thread_t *self = lmgr_get_thread_info();
679 * Do directly pre_P and post_P (used by trylock)
681 void lmgr_do_lock(void *m, const char *file, int line)
683 lmgr_thread_t *self = lmgr_get_thread_info();
684 self->pre_P(m, file, line);
689 * Use this function when the caller handle the mutex directly
691 void lmgr_do_unlock(void *m)
693 lmgr_thread_t *self = lmgr_get_thread_info();
698 void *(*start_routine)(void*);
703 void *lmgr_thread_launcher(void *x)
707 pthread_cleanup_push(cln_hdl, NULL);
709 lmgr_thread_arg_t arg;
710 lmgr_thread_arg_t *a = (lmgr_thread_arg_t *)x;
711 arg.start_routine = a->start_routine;
715 ret = arg.start_routine(arg.arg);
716 pthread_cleanup_pop(1);
720 int lmgr_thread_create(pthread_t *thread,
721 const pthread_attr_t *attr,
722 void *(*start_routine)(void*), void *arg)
724 /* lmgr should be active (lmgr_init_thread() call in main()) */
725 ASSERT(lmgr_is_active());
726 /* Will be freed by the child */
727 lmgr_thread_arg_t *a = (lmgr_thread_arg_t*) malloc(sizeof(lmgr_thread_arg_t));
728 a->start_routine = start_routine;
730 return pthread_create(thread, attr, lmgr_thread_launcher, a);
733 #else /* _USE_LOCKMGR */
737 * Use this function is used only after a fatal signal
738 * We don't use locking to display information
740 void dbg_print_lock(FILE *fp)
742 Pmsg0(000, "lockmgr disabled\n");
745 #endif /* _USE_LOCKMGR */
750 #define pthread_mutex_lock(x) lmgr_mutex_lock(x)
751 #define pthread_mutex_unlock(x) lmgr_mutex_unlock(x)
752 #define pthread_cond_wait(x,y) lmgr_cond_wait(x,y)
753 #define pthread_create(a, b, c, d) lmgr_thread_create(a,b,c,d)
756 #define P(x) lmgr_mutex_lock(&(x), __FILE__, __LINE__)
757 #define V(x) lmgr_mutex_unlock(&(x), __FILE__, __LINE__)
759 pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
760 pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
761 pthread_mutex_t mutex3 = PTHREAD_MUTEX_INITIALIZER;
762 pthread_mutex_t mutex4 = PTHREAD_MUTEX_INITIALIZER;
763 pthread_mutex_t mutex5 = PTHREAD_MUTEX_INITIALIZER;
764 pthread_mutex_t mutex6 = PTHREAD_MUTEX_INITIALIZER;
766 void *self_lock(void *temp)
775 void *nolock(void *temp)
783 void *locker(void *temp)
785 pthread_mutex_t *m = (pthread_mutex_t*) temp;
786 pthread_mutex_lock(m);
787 pthread_mutex_unlock(m);
791 void *rwlocker(void *temp)
793 brwlock_t *m = (brwlock_t*) temp;
802 void *mix_rwl_mutex(void *temp)
804 brwlock_t *m = (brwlock_t*) temp;
813 void *th2(void *temp)
828 void *th1(void *temp)
845 void *thx(void *temp)
847 int s= 1 + (int) (500.0 * (rand() / (RAND_MAX + 1.0))) + 200;
860 fprintf(stderr, "undertaker sleep()\n");
863 if (lmgr_detect_deadlock()) {
873 void _ok(const char *file, int l, const char *op, int value, const char *label)
878 printf("ERR %.30s %s:%i on %s\n", label, file, l, op);
880 printf("OK %.30s\n", label);
884 #define ok(x, label) _ok(__FILE__, __LINE__, #x, (x), label)
886 void _nok(const char *file, int l, const char *op, int value, const char *label)
891 printf("ERR %.30s %s:%i on !%s\n", label, file, l, op);
893 printf("OK %.30s\n", label);
897 #define nok(x, label) _nok(__FILE__, __LINE__, #x, (x), label)
901 printf("Result %i/%i OK\n", nb - err, nb);
907 * - Must detect multiple lock
908 * - lock/unlock in wrong order
909 * - deadlock with 2 or 3 threads
913 pthread_t id1, id2, id3, tab[200];
916 pthread_create(&id1, NULL, self_lock, NULL);
918 ok(lmgr_detect_deadlock(), "Check self deadlock");
919 lmgr_v(&mutex1); /* a bit dirty */
920 pthread_join(id1, NULL);
923 pthread_create(&id1, NULL, nolock, NULL);
925 nok(lmgr_detect_deadlock(), "Check for nolock");
926 pthread_join(id1, NULL);
929 pthread_create(&id1, NULL, locker, &mutex1);
930 pthread_create(&id2, NULL, locker, &mutex1);
931 pthread_create(&id3, NULL, locker, &mutex1);
933 nok(lmgr_detect_deadlock(), "Check for multiple lock");
935 pthread_join(id1, NULL);
936 pthread_join(id2, NULL);
937 pthread_join(id3, NULL);
944 pthread_create(&id1, NULL, rwlocker, &wr);
945 pthread_create(&id2, NULL, rwlocker, &wr);
946 pthread_create(&id3, NULL, rwlocker, &wr);
947 nok(lmgr_detect_deadlock(), "Check for multiple rwlock");
948 rwl_writeunlock(&wr);
949 nok(lmgr_detect_deadlock(), "Check for simple rwlock");
950 rwl_writeunlock(&wr);
951 nok(lmgr_detect_deadlock(), "Check for multiple rwlock");
953 pthread_join(id1, NULL);
954 pthread_join(id2, NULL);
955 pthread_join(id3, NULL);
959 pthread_create(&id1, NULL, mix_rwl_mutex, &wr);
960 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
962 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
963 rwl_writeunlock(&wr);
964 nok(lmgr_detect_deadlock(), "Check for mix rwlock/mutex");
965 pthread_join(id1, NULL);
972 nok(lmgr_detect_deadlock(), "Check for wrong order");
974 for(int j=0; j<200; j++) {
975 pthread_create(&tab[j], NULL, thx, NULL);
977 for(int j=0; j<200; j++) {
978 pthread_join(tab[j], NULL);
979 if (j%3) { lmgr_detect_deadlock();}
981 nok(lmgr_detect_deadlock(), "Check 200 lockers");
990 pthread_create(&id1, NULL, th1, NULL);
992 pthread_create(&id2, NULL, th2, NULL);
994 ok(lmgr_detect_deadlock(), "Check for deadlock");
998 // pthread_create(&id3, NULL, th3, NULL);
1000 // pthread_join(id1, NULL);
1001 // pthread_join(id2, NULL);
1002 lmgr_cleanup_main();
1003 sm_check(__FILE__, __LINE__, false);