On Linux, the openat syscall can be used to create files and to test for their existence. Speaking in terms of the C/C++ memory model, creating a file and verifying its existence creates a synchronizes-with relationship. What I need to know is whether these synchronizations are all sequentially-consistent with each other. (I certainly hope so, but I haven't actually seen this documented anywhere.)

For example, given processes p1 and p2, and paths A and B:

if p1 does this: create(A), then create(B)

and p2 does this: try to open(B), then try to open(A)

and no other processes interfere with A or B, is it possible for p2 to open B successfully but fail to find A?

If it makes a difference, we can assume all operations are within one filesystem.

  • I may be wrong, but I don't think there's any guarantee for that. An open(O_CREAT) with a file that doesn't already exist involves 2 separate operations: 1) creating a inode, and 2) creating a dir entry (a hardlink) pointing to it. While open is guaranteed to return a ready-to-use fd pointing to the inode, the system is free to queue the directory update for later, which may result in the path to B popping into existence before the path to A. – mosvy May 30 at 22:49
  • @mosvy You bring up a good point: the operations relevant to creating files and observing their existence are operations on the parent directory, not the file itself. I have now answered my own question after looking through the Linux documentation on directory locking. – Kaz Wesley May 31 at 16:51

With all the underlying disk and multi-core CPU optimizations it is not necessarily possible to determine the strict order of a sequence of operations between two processes. This is why semaphores are employed if there is the possibility of time dependent behavior.

  • 1
    @KazWesley I've already written a comment (I don't know why it disappeared, did you report it as "useless"?) -- but the gist of it is that you don't set locks on directory entries (paths), but on inodes. – mosvy May 30 at 22:44

Only for files in the same directory.

There are 6 rules:

  1. read access. Locking rules: caller locks directory we are accessing. The lock is taken shared.

  2. object creation. Locking rules: same as above, but the lock is taken exclusive.

  3. object removal. Locking rules: caller locks parent, finds victim, locks victim and calls the method. Locks are exclusive.

  4. rename() that is not cross-directory. Locking rules: caller locks the parent and finds source and target. In case of exchange (with RENAME_EXCHANGE in flags argument) lock both. In any case, if the target already exists, lock it. If the source is a non-directory, lock it. If we need to lock both, lock them in inode pointer order. Then call the method. All locks are exclusive. NB: we might get away with locking the the source (and target in exchange case) shared.

  5. link creation. Locking rules:

    • lock parent

    • check that source is not a directory

    • lock source

    • call the method. All locks are exclusive.

  6. cross-directory rename. The trickiest in the whole bunch. Locking rules:

    • lock the filesystem

    • lock parents in "ancestors first" order.

    • find source and target.

    • if old parent is equal to or is a descendent of target fail with -ENOTEMPTY

    • if new parent is equal to or is a descendent of source fail with -ELOOP

    • If it's an exchange, lock both the source and the target.

    • If the target exists, lock it. If the source is a non-directory, lock it. If we need to lock both, do so in inode pointer order.

    • call the method. All ->i_rwsem are taken exclusive. Again, we might get away with locking the the source (and target in exchange case) shared.

The rules above obviously guarantee that all directories that are going to be read, modified or removed by method will be locked by caller.

Locking enforces linearizability, so operations on a single directory are totally ordered. However, read access (1), object creation (2), and object removal (3) don't take any broader locks than the directory lock, so there are no guarantees about ordering of directory operations in different directories; different observers may see the directories' linear histories interleaved in different ways.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.