aboutsummaryrefslogtreecommitdiffstats
path: root/example/notify_inval_entry.c
diff options
context:
space:
mode:
authorKyle Lippincott <spectral@google.com>2022-09-12 12:26:53 -0700
committerNikolaus Rath <Nikolaus@rath.org>2023-01-04 09:41:56 +0000
commit33736958b61d90d9db9b03441103035316f09abc (patch)
treebc839600717ba67da5b37f8bfd94583a24366a5f /example/notify_inval_entry.c
parent30d423ee74496505f89e9db1cb23aafb1cc653a8 (diff)
downloadlibfuse-33736958b61d90d9db9b03441103035316f09abc.tar.gz
Remove partial locking of paths when using high-level API
As described in https://github.com/libfuse/libfuse/issues/695 and below, partial locking of paths can cause a deadlock. Partial locking was added to prevent starvation, but it's unclear what specific cases of starvation were of concern. As far as I was able to determine, since we support reader locks that give priority to writers (to prevent starvation), this means that to starve the queue element, we'd need a constant stream of queued requests that lock the path for write. Write locks are used when the element is being (potentially) removed, so this stream of requests that starve the `rename` or `lock` operations seems unlikely. ### Summarizing issue #695 The high-level API handles locking of the node structures it maintains to prevent concurrent requests from deleting nodes that are in use by other requests. This means that requests that might remove these structs (`rmdir`, `rename`, `unlink`, `link`) need to acquire an (internally managed - not pthread) exclusive lock before doing so. In the case where the lock is already held (for read or for write), the operation is placed onto a queue of waiters. On every unlock, the queue is reinspected for any element that might now be able to make progress. Since `rename` and `link` involve two paths, when added to the queue, a single queue entry requires that we lock two different paths. There was, prior to this change, support for partially locking the first queue element if it had two paths to lock. This partial locking can cause a deadlock: - set up a situation where the first element in the queue is partially locked (such as by holding a reader lock on one of the paths being renamed, but not the other). For example: `/rmthis/foo/foo.txt` [not-yet-locked] and `/rmthis/bar/bar.txt` [locked] - add an `rmdir` for an ancestor directory of the not-yet-locked path to the queue. In this example: `/rmthis` After getting into this situation, we have the following `treelock` values: - `/rmthis`: 1 current reader (due to the locked `/rmthis/bar/bar.txt`), one waiting writer (`rmdir`): no new readers will acquire a read lock here. - `/rmthis/bar`: 1 reader (the locked `/rmthis/bar/bar.txt`) - `/rmthis/bar/bar.txt`: 1 writer (the locked `/rmthis/bar/bar.txt`) This is deadlocked, because the partial lock will never be able to be completely locked, as doing so would require adding a reader lock on `/rmthis`, and that will be rejected due to write lock requests having priority -- until the writer succeeds in locking it, no new readers can be added. However, the writer (the `rmdir`) will never be able to acquire its write lock, as the reader lock will never be dropped -- there's no support for downgrading a partially locked element to be unlocked, the only state change that's allowed involves it becoming completely locked.
Diffstat (limited to 'example/notify_inval_entry.c')
0 files changed, 0 insertions, 0 deletions