Does FAT disallow undirected cycles?

Question

For educational purposes, I'm rolling my own FAT reader (allows you to browse a drive, etc). My current issue is determining the current working directory (such as for the prompt in a typical command prompt). As far as I can tell, the directory table gives no info on the path you would have taken to get there. (I've been working off the standard I found here) Thus, my current approach is just keep track of each directory you pass through (i.e. essentially each time cd <dir> is used, put that value in a list, and remove the last one when cd .. is used)

Here's where the issue arises. Lets say two different paths bring you to the same directory. If you then follow the .. directory upwards, the issue becomes more complicated than just removing the last directory name from your list. If .. takes you up the path you didn't come down, you'd actually have to determine a whole new working directory.

This issue becomes irrelevant if FAT doesn't allow undirected cycles. (I believe I read that certain file systems disallow this sort of complexity for exactly this reason of simplifying traversal, but I can't find specific info for FAT) Do I need to worry about this? In other words, is FAT described by a tree or by a general graph?

For reference, I'm dealing with FAT16 and FAT32 (incidentally in C on Linux, but I assume that's irrelevant)

Answer 1

There's nothing in the FATx format that disallows cycles. However, there are other issues if you allow cycles:

• As pointed out, ".." is ambiguous when two directory entries point to the same directory. Not usually a big deal as DOS/WINDOWS maintain the full text of the directory and doing "cd .." is a name operation, not a directory traversal. *NIX, on the other hand will have problems.
• There are no reference counts, meaning RMDIR X cannot effectively free disk space unless it does an entire tree walk to see if there are any other references to that directory.
• Worse, it could be possible to "disconnect" the cycle from the root, leaving unreachable space which CHKDSK/fsck would need to clean up.

(N.B. these are some of the reasons *NIX doesn't allow hard links to directories).

Answer 2

It doesn't matter it there are two parent directories pointing to the same subdirectory as you don't have that duality in your directory stack. When the user issues a cd .. command, just pop the stack and that's it.

Answer 3

Asking around, experienced operating systems guys have told me that FAT doesn't explicitly ban cycles, but it would add such complexity that all implementations ignore it. After all, standard OSes don't give a way to create such a cycle without bit-level hacking. Therefore, the problem can be ignored.