11
$\begingroup$

Consider an filesystem targeted at some embedded devices that does little more than store files in a hierarchical directory structure. This filesystem lacks many of the operations you may be used to in systems such as unix and Windows (for example, its access permissions are completely different and not tied to metadata stored in directories). This filesystem does not allow any kind of hard link or soft link, so every file has a unique name in a strict tree structure.

Is there any benefit to storing a link to the directory itself and to its parent in the on-disk data structure that represents a directory?

Most unix filesystems have . and .. entries on disk. I wonder why they don't handle those at the VFS (generic filesystem driver) layer. Is this a historical artifact? Is there a good reason, and if so, which precisely, so I can determine whether it's relevant to my embedded system?

$\endgroup$
  • $\begingroup$ I always figured they were there only virtually so programs could easily access current and parent directory. Interesting question, but does it belong here? $\endgroup$ – Raphael Mar 11 '12 at 23:31
  • $\begingroup$ @Raphael I could understand if you considered my question too broad (→ “not a real question”), or perhaps “not constructive”, because it's somewhat open-ended. But I disagree that it's off-topic: it's about filesystem design, how is that not applied computer science? If you think it's off-topic, please explain your reasoning on meta. $\endgroup$ – Gilles Mar 11 '12 at 23:37
  • $\begingroup$ @Raphael I've edited my question, hopefully it should be clear that my point of view is that of an embedded OS designer. Thanks for your comments. $\endgroup$ – Gilles Mar 12 '12 at 8:14
2
$\begingroup$

Having links to the parent directory makes good sense to me. If you didn't have them, you would always need to work with a whole list of directories. So, for example, /home/svick/Documents/ would have to be represented as { /, /home/, /home/svick/, /home/svick/Documents }. If you didn't do that, you wouldn't be able to find the parent directory at all (or it would be very expensive). This is not only inefficient, but also dangerous. If you have two such lists that overlap, they could easily desynchronize if you moved some directory.

On the other hand, if you have a reference to the parent directory, it's more efficient and safer.

I don't see any reason to actually have a link to the current directory. If you have a structure that represents some directory and you want to access that directory, using . is always completely unnecessary. Because of that, I would expect that the . link doesn't actually exist in the filesystem structure and is only virtual.

$\endgroup$
  • 2
    $\begingroup$ Same remark: why do it in each filesystem rather than in the VFS layer? Most Linux filesystems do have . and .. entries. $\endgroup$ – Gilles Mar 12 '12 at 1:39
  • $\begingroup$ Like I said, I think it's more efficient. You can work just with the current directory, and access its parents only when you need. If you didn't have parent links, you would always need to keep all of the directories in the whole path from root in memory. And you would need that for each entry you use. $\endgroup$ – svick Mar 12 '12 at 2:27
  • 1
    $\begingroup$ @svick: Gilles does not compare having parent links with not having parent links. He compares having them in the actual file system with having them simulated by an intermediate layer of code (vfs) between the actual filesystem and the user-space. $\endgroup$ – rgrig Mar 12 '12 at 10:50
2
$\begingroup$

You get fewer special cases. In many situations, VFS may handle ".." as it handles any other directory name.

$\endgroup$
  • 3
    $\begingroup$ If the directories are virtual, the program (usermode I presume) can still handle it as any other directory. You don't really need the links to present at the storage level. $\endgroup$ – Aryabhata Mar 12 '12 at 0:10
  • 1
    $\begingroup$ Yes, but why not handle that at the VFS layer? Why would there be any associated storage? $\endgroup$ – Gilles Mar 12 '12 at 0:14
  • $\begingroup$ Why do people implement linked lists with a sentinel instead of taking care of the empty list case in the add/remove functions? $\endgroup$ – rgrig Mar 12 '12 at 9:37
  • $\begingroup$ @rgrig: It happens only when the interface to the considered linked list implementation is written in a language that is exceptionally bad at handling inductive data structures (C, Java, etc…). Here this problem is not relevant because the VFS layer is not directly accessible from a user point of view. $\endgroup$ – Stéphane Gimenez Mar 13 '12 at 21:07
  • $\begingroup$ @StéphaneGimenez: This problem is relevant, because VFS is written in C. $\endgroup$ – rgrig Mar 13 '12 at 21:51
2
$\begingroup$

The only reason I can imagine is the following scenario:

  1. An original implementation of a file system existed with the same directory format but the notions of file paths and subdirectories was not considered at that time (See The PDP-7 Unix file system).

  2. Then people thought that path resolution and subdirectories would be useful!

  3. To keep some amount of backward compatibility with older implementations, it was decided that the . and .. will be stored on the disk just like any other directory.

So maybe we're left with those useless artefacts, just for the sake of backward-compatibility with 40 years old software? Credible scenario?


Note: Also it was not completely stupid to add these entries to the directory listing, as you need to store the inode number of your true parent directory somewhere anyway (remember that hardlinks on directories was allowed at this time), and a reference to your own inode number might be a good sanity check.

$\endgroup$
1
$\begingroup$

I don't see a reason to implement . and .. on either level rather than the other. However, if you target embedded systems any layer you can save may be dollars earned, so it might make sense to try and implement everything as low as possible.

As for the general need of . and .., how would you express relative paths without them? At least .. is indispensable for paths that leave the current subtree. If you do not need such paths (maybe the tree is a primitive way to encode access privileges?) you do not need ...

$\endgroup$

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.