OSDev.org

Hey, i'm trying to understand the 'node graph' vfs design, but fail in understanding some specific things.

Each node in the graph is somekind of an inode, which keeps poiners to specific read/write functions, and keeps the file name. the root node is "/", but what are the types of the nodes? i mean, the whole point of having a virtual file system is for an abstraction layer. The vfs has no need in the knowledge of directories locations / files locations. So all of the children nodes are going to be file systems mount points?

But then again, if i'm searching for a directory, how will the vfs know which mount point has that specific directory?

The node type is simply what type of node it is, as explained on the wiki. So if a particular file system node represents a file, the node type is "file" (or however you're encoding the "file" node type). If the node represents a directory, the node type is "directory", and so on. The child nodes aren't mountpoints unless there's actually a filesystem mounted there (so for example if a CD-ROM is mounted on "/mnt/cdrom" then "/mnt" is a directory, "/mnt/cdrom" is a mountpoint, "/mnt/cdrom/photos" is a directory, and "/mnt/cdrom/photos/pic0001.png" is a file).

I'm afraid I can't answer your second question definitively since I haven't worked with a node graph VFS specifically. As I gather that it is some kind of hierarchical tree, I imagine you will want to traverse the graph at each level in the path to find a particular inode (whether that inode is a file, directory, or mountpoint) - so for example to find the inode for "/mnt/cdrom/photos/pic0001.png" you'll traverse all the child nodes of "/" until you find "mnt", then you'll traverse all the child nodes of "/mnt" until you find "cdrom", then again with traversing the children of "/mnt/cdrom" until you find "photos", and again until you find "pic0001.png", and now you're at the inode for "/mnt/cdrom/photos/pic0001.png" (if at any point you can't find a child node then you might want to use the parent inode's "read directory" function to update your node graph and try again, and if the node still can't be found then return an "inode not found" error). Similarly, to find the inode for "/mnt/cdrom/music" you'll do exactly the same thing, except that the inode that you return will be a directory inode not a file inode (since "/mnt/cdrom/music" is a directory). Remember that part of the abstraction in a VFS is treating all filesystem nodes the same until the type actually matters (e.g. you can't read data from a directory, but you can list its contents which is impossible with a file).

onlyonemac wrote:The node type is simply what type of node it is, as explained on the wiki. So if a particular file system node represents a file, the node type is "file" (or however you're encoding the "file" node type). If the node represents a directory, the node type is "directory", and so on. The child nodes aren't mountpoints unless there's actually a filesystem mounted there (so for example if a CD-ROM is mounted on "/mnt/cdrom" then "/mnt" is a directory, "/mnt/cdrom" is a mountpoint, "/mnt/cdrom/photos" is a directory, and "/mnt/cdrom/photos/pic0001.png" is a file).

I'm afraid I can't answer your second question definitively since I haven't worked with a node graph VFS specifically. As I gather that it is some kind of hierarchical tree, I imagine you will want to traverse the graph at each level in the path to find a particular inode (whether that inode is a file, directory, or mountpoint) - so for example to find the inode for "/mnt/cdrom/photos/pic0001.png" you'll traverse all the child nodes of "/" until you find "mnt", then you'll traverse all the child nodes of "/mnt" until you find "cdrom", then again with traversing the children of "/mnt/cdrom" until you find "photos", and again until you find "pic0001.png", and now you're at the inode for "/mnt/cdrom/photos/pic0001.png" (if at any point you can't find a child node then you might want to use the parent inode's "read directory" function to update your node graph and try again, and if the node still can't be found then return an "inode not found" error). Similarly, to find the inode for "/mnt/cdrom/music" you'll do exactly the same thing, except that the inode that you return will be a directory inode not a file inode (since "/mnt/cdrom/music" is a directory). Remember that part of the abstraction in a VFS is treating all filesystem nodes the same until the type actually matters (e.g. you can't read data from a directory, but you can list its contents which is impossible with a file).

Thank you for the detailed answer.
I think i understand the only thing that made my mind throw an exception. The node graph has to keep a node for EVERY file on the system. This means i need to iterate on every mounted file system and cache its files. (When first mounting it, i update the tree after enumerating on it) Am i right?

Sourcer wrote:This means i need to iterate on every mounted file system and cache its files. (When first mounting it, i update the tree after enumerating on it) Am i right?

That's entirely up to you. You can start from the root node of the volume every time you access the storage device, or you can cache the entire node tree in memory, or anywhere in between. Your best bet is probably to make sure everything works, first, then start performance tuning memory usage while testing that nothing stops working in the process. This is usually how I approach these sorts of problems.

Caching nothing in memory will be slow because you will have to wait on the metadata and traverse the tree every time. Caching the entire tree will be slow, because you may run out of memory and have to page that information back to disk, which defeats the whole purpose.

You can really only optimize for a specific environment, and then handle everything else as best as you can, so you might start with a target system in mind when you decide where to performance tune.

Sourcer wrote:The node graph has to keep a node for EVERY file on the system. This means i need to iterate on every mounted file system and cache its files. (When first mounting it, i update the tree after enumerating on it) Am i right?

Personally I wouldn't bother iterating the entire filesystem on mounting. As I suggested in my last post, if a particular node isn't found in the node graph, re-iterate that particular node in the filesystem to update it's children in the node graph and try again. That way, you're updating the node graph as required (make sure to remove a node from the graph explicitly when it is deleted, though, otherwise old nodes will be left in the node graph and may be found later when one attempts to open the file/directory that they refer to).

You might also want to implement some system to remove nodes from the graph if they haven't been accessed in a while to save memory (this might be the kind of thing you want to do only when it's necessary to free up some memory, along with removing other cached data from memory).

onlyonemac wrote:

Sourcer wrote:The node graph has to keep a node for EVERY file on the system. This means i need to iterate on every mounted file system and cache its files. (When first mounting it, i update the tree after enumerating on it) Am i right?

Personally I wouldn't bother iterating the entire filesystem on mounting. As I suggested in my last post, if a particular node isn't found in the node graph, re-iterate that particular node in the filesystem to update it's children in the node graph and try again. That way, you're updating the node graph as required (make sure to remove a node from the graph explicitly when it is deleted, though, otherwise old nodes will be left in the node graph and may be found later when one attempts to open the file/directory that they refer to).

You might also want to implement some system to remove nodes from the graph if they haven't been accessed in a while to save memory (this might be the kind of thing you want to do only when it's necessary to free up some memory, along with removing other cached data from memory).

Another problem that i thought of
Suppose i mounted ext2(which is on some block device) on "/".
Root node functions(read/write..) will all point to the ext2 driver functions.

Suppose theres a directory "/mnt" in the ext2 fs, and i want to mount a FAT32 fs in:
"/mnt/mounted_fat"

where will 'mounted_fat' shall be kept? it sure as hell isn't a child of '/mnt', so keeping it in the ext2 block device is an error. so..?

In Linux, when you would have first to create a mounted_fat directory in the /mnt folder and then mount the other fs to that directory.
Suppose you have a name resolving algorithm which for a fs, gives you the inode relative to a name. Keep track of each mount point.
First , resolve / , then /mnt... each time you encounter a mount point, you know which fs is mounted. Call the name resolution function for that the target file system. but just remember that in the target fs, the directory is /mounted _fat, not /mnt/mounted _fat

Sourcer wrote:Another problem that i thought of
Suppose i mounted ext2(which is on some block device) on "/".
Root node functions(read/write..) will all point to the ext2 driver functions.

Suppose theres a directory "/mnt" in the ext2 fs, and i want to mount a FAT32 fs in:
"/mnt/mounted_fat"

where will 'mounted_fat' shall be kept? it sure as hell isn't a child of '/mnt', so keeping it in the ext2 block device is an error. so..?

When you get to the final inode in your path after traversing the node graph, you'll use that inode's read/write functions, which will be the read/write functions of the filesystem on which the inode resides, not the root filesystem. As "mounted_fat" is a mountpoint, it's read/write functions will be those for the FAT32 driver, not the EXT2 driver.

As a rule: when adding child nodes to the node graph, set their read/write functions the same as their parents' read/write functions, unless the child node is a mountpoint, in which case set its read/write functions to the ones provided by the driver for the filesystem being mounted. This way, whenever you're working with a particular inode, the read/write functions in that inode will always be the correct ones for the filesystem that the inode is on.