From 66956b6f7a254517332fe6e1fa3efab1676e6239 Mon Sep 17 00:00:00 2001 From: Miklos Szeredi Date: Mon, 1 Oct 2012 17:55:55 +0200 Subject: [PATCH] Fix deadlock in libfuse Running "svn update" on a fuse filesystem could deadlock because of a bug in the way the paths are locked. Reported by Kazuaki Anami --- ChangeLog | 6 ++ lib/fuse.c | 285 +++++++++++++++++++++++++++++++---------------------- 2 files changed, 173 insertions(+), 118 deletions(-) diff --git a/ChangeLog b/ChangeLog index 4b43f41..6d3817e 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +2012-10-01 Miklos Szeredi + + * Fix deadlock in libfuse. Running "svn update" on a fuse + filesystem could deadlock because of a bug in the way the paths + are locked. Reported by Kazuaki Anami + 2012-08-23 Miklos Szeredi * Fix missing config.h in buffer.c. Reported by Matthew Gabeler-Lee diff --git a/lib/fuse.c b/lib/fuse.c index 2907cfe..599a587 100644 --- a/lib/fuse.c +++ b/lib/fuse.c @@ -23,6 +23,7 @@ #include #include #include +#include #include #include #include @@ -91,8 +92,20 @@ struct fusemod_so { }; struct lock_queue_element { - struct lock_queue_element *next; - pthread_cond_t cond; + struct lock_queue_element *next; + pthread_cond_t cond; + fuse_ino_t nodeid1; + const char *name1; + char **path1; + struct node **wnode1; + fuse_ino_t nodeid2; + const char *name2; + char **path2; + struct node **wnode2; + int err; + bool first_locked : 1; + bool second_locked : 1; + bool done : 1; }; struct node_table { @@ -134,7 +147,6 @@ struct fuse { struct fuse_fs *fs; int nullpath_ok; int utime_omit_ok; - int curr_ticket; struct lock_queue_element *lockq; int pagesize; struct list_head partial_slabs; @@ -168,10 +180,12 @@ struct node { unsigned int is_hidden : 1; unsigned int cache_valid : 1; int treelock; - int ticket; char inline_name[32]; }; +#define TREELOCK_WRITE -1 +#define TREELOCK_WAIT_OFFSET INT_MIN + struct node_lru { struct node node; struct list_head lru; @@ -898,48 +912,28 @@ static char *add_name(char **buf, unsigned *bufsize, char *s, const char *name) } static void unlock_path(struct fuse *f, fuse_ino_t nodeid, struct node *wnode, - struct node *end, int ticket) + struct node *end) { struct node *node; if (wnode) { - assert(wnode->treelock == -1); + assert(wnode->treelock == TREELOCK_WRITE); wnode->treelock = 0; - if (!wnode->ticket) - wnode->ticket = ticket; } for (node = get_node(f, nodeid); node != end && node->nodeid != FUSE_ROOT_ID; node = node->parent) { - assert(node->treelock > 0); + assert(node->treelock != 0); + assert(node->treelock != TREELOCK_WAIT_OFFSET); + assert(node->treelock != TREELOCK_WRITE); node->treelock--; - if (!node->ticket) - node->ticket = ticket; - } -} - -static void release_tickets(struct fuse *f, fuse_ino_t nodeid, - struct node *wnode, int ticket) -{ - struct node *node; - - if (wnode) { - if (wnode->ticket != ticket) - return; - - wnode->ticket = 0; - } - - for (node = get_node(f, nodeid); - node->nodeid != FUSE_ROOT_ID; node = node->parent) { - if (node->ticket != ticket) - return; - node->ticket = 0; + if (node->treelock == TREELOCK_WAIT_OFFSET) + node->treelock = 0; } } static int try_get_path(struct fuse *f, fuse_ino_t nodeid, const char *name, - char **path, struct node **wnodep, int ticket) + char **path, struct node **wnodep, bool need_lock) { unsigned bufsize = 256; char *buf; @@ -966,18 +960,16 @@ static int try_get_path(struct fuse *f, fuse_ino_t nodeid, const char *name, } if (wnodep) { - assert(ticket); + assert(need_lock); wnode = lookup_node(f, nodeid, name); if (wnode) { - if (wnode->treelock != 0 || - (wnode->ticket && wnode->ticket != ticket)) { - if (!wnode->ticket) - wnode->ticket = ticket; + if (wnode->treelock != 0) { + if (wnode->treelock > 0) + wnode->treelock += TREELOCK_WAIT_OFFSET; err = -EAGAIN; goto out_free; } - wnode->treelock = -1; - wnode->ticket = 0; + wnode->treelock = TREELOCK_WRITE; } } @@ -992,14 +984,12 @@ static int try_get_path(struct fuse *f, fuse_ino_t nodeid, const char *name, if (s == NULL) goto out_unlock; - if (ticket) { + if (need_lock) { err = -EAGAIN; - if (node->treelock == -1 || - (node->ticket && node->ticket != ticket)) + if (node->treelock < 0) goto out_unlock; node->treelock++; - node->ticket = 0; } } @@ -1015,40 +1005,95 @@ static int try_get_path(struct fuse *f, fuse_ino_t nodeid, const char *name, return 0; out_unlock: - if (ticket) - unlock_path(f, nodeid, wnode, node, ticket); + if (need_lock) + unlock_path(f, nodeid, wnode, node); out_free: free(buf); out_err: - if (ticket && err != -EAGAIN) - release_tickets(f, nodeid, wnode, ticket); - return err; } -static void wake_up_first(struct fuse *f) +static void queue_element_unlock(struct fuse *f, struct lock_queue_element *qe) { - if (f->lockq) - pthread_cond_signal(&f->lockq->cond); + struct node *wnode; + + if (qe->first_locked) { + wnode = qe->wnode1 ? *qe->wnode1 : NULL; + unlock_path(f, qe->nodeid1, wnode, NULL); + } + if (qe->second_locked) { + wnode = qe->wnode2 ? *qe->wnode2 : NULL; + unlock_path(f, qe->nodeid2, wnode, NULL); + } } -static void wake_up_next(struct lock_queue_element *qe) +static void queue_element_wakeup(struct fuse *f, struct lock_queue_element *qe) { - if (qe->next) - pthread_cond_signal(&qe->next->cond); + int err; + bool first = (qe == f->lockq); + + if (!qe->path1) { + /* Just waiting for it to be unlocked */ + if (get_node(f, qe->nodeid1)->treelock == 0) + pthread_cond_signal(&qe->cond); + + return; + } + + if (!qe->first_locked) { + err = try_get_path(f, qe->nodeid1, qe->name1, qe->path1, + qe->wnode1, true); + if (!err) + qe->first_locked = true; + else if (err != -EAGAIN) + goto err_unlock; + } + if (!qe->second_locked && qe->path2) { + err = try_get_path(f, qe->nodeid2, qe->name2, qe->path2, + qe->wnode2, true); + if (!err) + qe->second_locked = true; + else if (err != -EAGAIN) + goto err_unlock; + } + + if (qe->first_locked && (qe->second_locked || !qe->path2)) { + err = 0; + goto done; + } + + /* + * Only let the first element be partially locked otherwise there could + * be a deadlock. + * + * But do allow the first element to be partially locked to prevent + * starvation. + */ + if (!first) + queue_element_unlock(f, qe); + + /* keep trying */ + return; + +err_unlock: + queue_element_unlock(f, qe); +done: + qe->err = err; + qe->done = true; + pthread_cond_signal(&qe->cond); } -static int get_ticket(struct fuse *f) +static void wake_up_queued(struct fuse *f) { - do f->curr_ticket++; - while (f->curr_ticket == 0); + struct lock_queue_element *qe; - return f->curr_ticket; + for (qe = f->lockq; qe != NULL; qe = qe->next) + queue_element_wakeup(f, qe); } static void debug_path(struct fuse *f, const char *msg, fuse_ino_t nodeid, - const char *name, int wr) + const char *name, bool wr) { if (f->conf.debug) { struct node *wnode = NULL; @@ -1063,56 +1108,58 @@ static void debug_path(struct fuse *f, const char *msg, fuse_ino_t nodeid, } } -static void queue_path(struct fuse *f, struct lock_queue_element *qe, - fuse_ino_t nodeid, const char *name, int wr) +static void queue_path(struct fuse *f, struct lock_queue_element *qe) { struct lock_queue_element **qp; - debug_path(f, "QUEUE PATH", nodeid, name, wr); + qe->done = false; + qe->first_locked = false; + qe->second_locked = false; pthread_cond_init(&qe->cond, NULL); qe->next = NULL; for (qp = &f->lockq; *qp != NULL; qp = &(*qp)->next); *qp = qe; } -static void dequeue_path(struct fuse *f, struct lock_queue_element *qe, - fuse_ino_t nodeid, const char *name, int wr) +static void dequeue_path(struct fuse *f, struct lock_queue_element *qe) { struct lock_queue_element **qp; - debug_path(f, "DEQUEUE PATH", nodeid, name, wr); pthread_cond_destroy(&qe->cond); for (qp = &f->lockq; *qp != qe; qp = &(*qp)->next); *qp = qe->next; } -static void wait_on_path(struct fuse *f, struct lock_queue_element *qe, - fuse_ino_t nodeid, const char *name, int wr) +static int wait_path(struct fuse *f, struct lock_queue_element *qe) { - debug_path(f, "WAIT ON PATH", nodeid, name, wr); - pthread_cond_wait(&qe->cond, &f->lock); + queue_path(f, qe); + + do { + pthread_cond_wait(&qe->cond, &f->lock); + } while (!qe->done); + + dequeue_path(f, qe); + + return qe->err; } static int get_path_common(struct fuse *f, fuse_ino_t nodeid, const char *name, char **path, struct node **wnode) { int err; - int ticket; pthread_mutex_lock(&f->lock); - ticket = get_ticket(f); - err = try_get_path(f, nodeid, name, path, wnode, ticket); + err = try_get_path(f, nodeid, name, path, wnode, true); if (err == -EAGAIN) { - struct lock_queue_element qe; - - queue_path(f, &qe, nodeid, name, !!wnode); - do { - wait_on_path(f, &qe, nodeid, name, !!wnode); - err = try_get_path(f, nodeid, name, path, wnode, - ticket); - wake_up_next(&qe); - } while (err == -EAGAIN); - dequeue_path(f, &qe, nodeid, name, !!wnode); + struct lock_queue_element qe = { + .nodeid1 = nodeid, + .name1 = name, + .path1 = path, + .wnode1 = wnode, + }; + debug_path(f, "QUEUE PATH", nodeid, name, !!wnode); + err = wait_path(f, &qe); + debug_path(f, "DEQUEUE PATH", nodeid, name, !!wnode); } pthread_mutex_unlock(&f->lock); @@ -1154,22 +1201,19 @@ static int get_path_wrlock(struct fuse *f, fuse_ino_t nodeid, const char *name, static int try_get_path2(struct fuse *f, fuse_ino_t nodeid1, const char *name1, fuse_ino_t nodeid2, const char *name2, char **path1, char **path2, - struct node **wnode1, struct node **wnode2, - int ticket) + struct node **wnode1, struct node **wnode2) { int err; /* FIXME: locking two paths needs deadlock checking */ - err = try_get_path(f, nodeid1, name1, path1, wnode1, ticket); + err = try_get_path(f, nodeid1, name1, path1, wnode1, true); if (!err) { - err = try_get_path(f, nodeid2, name2, path2, wnode2, ticket); + err = try_get_path(f, nodeid2, name2, path2, wnode2, true); if (err) { struct node *wn1 = wnode1 ? *wnode1 : NULL; - unlock_path(f, nodeid1, wn1, NULL, ticket); + unlock_path(f, nodeid1, wn1, NULL); free(*path1); - if (ticket && err != -EAGAIN) - release_tickets(f, nodeid1, wn1, ticket); } } return err; @@ -1181,27 +1225,27 @@ static int get_path2(struct fuse *f, fuse_ino_t nodeid1, const char *name1, struct node **wnode1, struct node **wnode2) { int err; - int ticket; pthread_mutex_lock(&f->lock); - ticket = get_ticket(f); err = try_get_path2(f, nodeid1, name1, nodeid2, name2, - path1, path2, wnode1, wnode2, ticket); + path1, path2, wnode1, wnode2); if (err == -EAGAIN) { - struct lock_queue_element qe; + struct lock_queue_element qe = { + .nodeid1 = nodeid1, + .name1 = name1, + .path1 = path1, + .wnode1 = wnode1, + .nodeid2 = nodeid2, + .name2 = name2, + .path2 = path2, + .wnode2 = wnode2, + }; - queue_path(f, &qe, nodeid1, name1, !!wnode1); - debug_path(f, " path2", nodeid2, name2, !!wnode2); - do { - wait_on_path(f, &qe, nodeid1, name1, !!wnode1); - debug_path(f, " path2", nodeid2, name2, !!wnode2); - err = try_get_path2(f, nodeid1, name1, nodeid2, name2, - path1, path2, wnode1, wnode2, - ticket); - wake_up_next(&qe); - } while (err == -EAGAIN); - dequeue_path(f, &qe, nodeid1, name1, !!wnode1); - debug_path(f, " path2", nodeid2, name2, !!wnode2); + debug_path(f, "QUEUE PATH1", nodeid1, name1, !!wnode1); + debug_path(f, " PATH2", nodeid2, name2, !!wnode2); + err = wait_path(f, &qe); + debug_path(f, "DEQUEUE PATH1", nodeid1, name1, !!wnode1); + debug_path(f, " PATH2", nodeid2, name2, !!wnode2); } pthread_mutex_unlock(&f->lock); @@ -1212,8 +1256,9 @@ static void free_path_wrlock(struct fuse *f, fuse_ino_t nodeid, struct node *wnode, char *path) { pthread_mutex_lock(&f->lock); - unlock_path(f, nodeid, wnode, NULL, 0); - wake_up_first(f); + unlock_path(f, nodeid, wnode, NULL); + if (f->lockq) + wake_up_queued(f); pthread_mutex_unlock(&f->lock); free(path); } @@ -1229,9 +1274,9 @@ static void free_path2(struct fuse *f, fuse_ino_t nodeid1, fuse_ino_t nodeid2, char *path1, char *path2) { pthread_mutex_lock(&f->lock); - unlock_path(f, nodeid1, wnode1, NULL, 0); - unlock_path(f, nodeid2, wnode2, NULL, 0); - wake_up_first(f); + unlock_path(f, nodeid1, wnode1, NULL); + unlock_path(f, nodeid2, wnode2, NULL); + wake_up_queued(f); pthread_mutex_unlock(&f->lock); free(path1); free(path2); @@ -1250,15 +1295,19 @@ static void forget_node(struct fuse *f, fuse_ino_t nodeid, uint64_t nlookup) * create and opendir */ while (node->nlookup == nlookup && node->treelock) { - struct lock_queue_element qe; + struct lock_queue_element qe = { + .nodeid1 = nodeid, + }; - queue_path(f, &qe, node->nodeid, NULL, 0); - do { - wait_on_path(f, &qe, node->nodeid, NULL, 0); - wake_up_next(&qe); + debug_path(f, "QUEUE PATH (forget)", nodeid, NULL, false); + queue_path(f, &qe); + do { + pthread_cond_wait(&qe.cond, &f->lock); } while (node->nlookup == nlookup && node->treelock); - dequeue_path(f, &qe, node->nodeid, NULL, 0); + + dequeue_path(f, &qe); + debug_path(f, "DEQUEUE_PATH (forget)", nodeid, NULL, false); } assert(node->nlookup >= nlookup); @@ -2339,7 +2388,7 @@ static char *hidden_name(struct fuse *f, fuse_ino_t dir, const char *oldname, newnode = lookup_node(f, dir, newname); } while(newnode); - res = try_get_path(f, dir, newname, &newpath, NULL, 0); + res = try_get_path(f, dir, newname, &newpath, NULL, false); pthread_mutex_unlock(&f->lock); if (res) break; @@ -4712,7 +4761,7 @@ void fuse_destroy(struct fuse *f) node = node->id_next) { if (node->is_hidden) { char *path; - if (try_get_path(f, node->nodeid, NULL, &path, NULL, 0) == 0) { + if (try_get_path(f, node->nodeid, NULL, &path, NULL, false) == 0) { fuse_fs_unlink(f->fs, path); free(path); } -- 2.30.2