Design of "resource addresses"

[NickJohnson]

Hi,

I developed and implemented this idea for my OS a while ago, but I'm going back over it to try and formalize things. I consider it one of the key novel parts of my OS' architecture, and it sort of captures a lot of my OS' design. The basic idea is to have a string format that can identify a resource on the system, in a way that sort of combines the idea of a path, a PID, and a GUID in a human-readable form. This format is tentatively called a resource address. I just want to bounce this concept off the forums to see if people have issues, suggestions, or comments. For any formal language stuff, I'm going to use some informal mix of regular expressions and BNF. I've never had any formal training or real experience in using either, so don't shoot me if something's wrong.

First, you need to understand the concept of a "resource" in my system. A resource is simply something that can have a message sent to it. This means processes, files, directories, links, windows, terminals, block devices, etc. are all resources. This is a pretty standard definition. Processes are collections of one or more resources, each with a unique resource index number (basically an inode number.) Most processes only contain a resource with index 0, which represents that process. Driver processes contain more resources, corresponding to files, directories, and links they manage. When a PID and resource index are combined, they create a "resource pointer" (in C, a 64 bit integer type) that uniquely identifies that resource on the system. Because of the integer format, a PID is a resource pointer to the process it identifies. Resource pointers have a string format that is bijective with their integer representation, and I will mean the string representation when I say "resource pointer" from here on.

The string representation of a resource pointer is defined as follows:

Code: Select all

<resource_pointer> = '@' <pid> | '@' <pid> ':' <index>
<pid> = <uint>
<index> = <uint>
<uint> = "[0-9]+"

Let us call the set of all resource pointers R.

There exists a null resource pointer that represents no resource.

So basically, "@42:1234" refers to PID 42, index 1234; "@12" refers to PID 12, index 0.

Paths are pretty much the same as in UNIX. They are sequences of letters delimited by slashes that indicate a sequence of directory entries to follow when looking up a file. I'm going to limit things to absolute paths for now. For the sake of precision, I'm going to give them a grammar too:

Code: Select all

<path> = '/' <dirent> | '/' <dirent> <path>
<dirent> = "[^/]+"

Let us call the set of all paths P.

The problem with this definition of paths is that in my system, it is not possible to reliably determine the parent of a directory from just that directory (this is because directories can be hardlinked, and because symbolic links make this very tricky.) So, paths like "/bin/../sbin/halt" are not usable in this form. "/bin/./ls" is also tricky, so let's kill two birds with one stone and define a simplified path as having no "." or ".." dirents:

Code: Select all

<simplified_path> = '/' <clean_dirent> | '/' <clean_dirent> <simplified_path>
<clean_dirent> = "([^/\.]+)|(\.[^/]+)|(\.\.[^/]+)"

Let us call the set of all simplified paths S and the set of all clean directory entries D.

It is pretty easy to see that there is an algorithm for transforming a (valid) path into a simplified path, at least once the path is turned into an absolute one. For example, if PWD="/home/nick" and we type "cd ../.", it means "cd /home/nick/../.", and this gets transformed to "cd /home". Let us define a function s:P -> S that turns valid paths into simplified paths.

Resource addresses are a combination between resource pointers and paths, and are a superset of resource pointers. The concept here is that we can represent the VFS as a function that takes resource addresses to resource addresses, ultimately reaching a resource pointer that can then be directly used to reference the resource. Let's define them now:

Code: Select all

<resource_address> = <resource_pointer> | <resource_pointer> <simplified_path>

Let's call the set of all resource addresses A.

Clearly, R is a subset of A. The VFS can be thought of as a function f:A -> A that eventually converges to a resource pointer (or does not find the file) by traversing its directory graph. For example, if @1:1 is a directory and @1:2 is a directory at entry "bin" in @1:1 and @1:3 is a file at entry "ls" in @1:2, then f("@1:1/bin/ls") = "@1:2:/ls". Let us define f*:A -> R as the repeated evaluation of f until it returns a resource pointer. So, f*("@1:1/bin/ls") = "@1:3".

It may be easier to think of f(a) where a is a resource address with pointer r and path p as being a DFA with transition function f, current state r, and input queue p. Basically, f is the table of the DFA and a is the execution state of the DFA. When you add symlinks, this makes the VFS into a sort of giant distributed parallel extended DFA thing, which I think is pretty cool.

Thinking of the VFS as this simpler function f instead of f* has some advantages for me. In my system, there is no central VFS server: drivers each manage their own VFS trees. All resources (most importantly directories; for files it is a no-op) implement a "find" function (analogous to f) that performs a single step toward returning the resource pointer. This makes it very simple to implement directories and symbolic links, and would also make it easy to implement something like a tag-based filesystem. The distributedness of the VFS also means that it is safe to allow user processes to present a VFS interface, which means an application can present its own resources as files.

So, what's the point here? There are some pretty cool things I've figured out how to do with this flexible format so far. First, if you allow symbolic links to be redirects to resource addresses instead of just paths, then you can implement mountpoints using symbolic links. Second, references to specific files can be passed around the system without worry that the VFS layout might change or that other processes may be using different roots. Third, it is possible for the user to (safely) construct a pointer to a resource that is not mounted in the filesystem, which is a neat trick for emergency situations and as a C programmer makes me feel all warm and fuzzy inside.

If you were like tl;dr, don't worry. I mostly wrote this to get my ideas down: explaining an idea to someone is one of the best ways to clarify and refine it.

[h0bby1]

i've been doing somethng a bit similar in my os, it doesn't use directly vfs or filesystem, but there is a tree system that i implemented at the very base of the os, it's so vital to anything in the os that i included it in the libc, it work in a similar fashion than filesystem, each node can have a name and a type and any number of childs, and everything use this tree structure to store their information, they can be pretty great to represent arbitrary data structure created at run time with typed and named members, and as the base allocation system use smart pointer with a reference counter , it can do similar things with having several reference to a same tree node without any of the process using it has to care about managing it internal state, or freing it, when no one use it anymore, it get freed automatically, and probably somewhere something could be made to add some sort of hook or signaling when a particular node get used or not, with having all device drivers that maintain their state in runtime defined structure with named/typed members that you can search, filter and browse, all the bus system also use this tree system to store information about device present, about drivers list for each bus with their vendor id/class id, it's not as sophisticated as your system to track all ressource, like file and directories or process, but lot of things the os does is stored in a similar kind of tree structure, even the windowing system store the windows and control arborescence into this tree system, it's pretty handy it works also well with path resolution to get a specific node with a path like string, and to handle filesystem, so ressource infos can be referenced easily from any point of the os

[NickJohnson]

In retrospect, the idea of being able to reference files by what is effectively a device number + inode number is actually a terrible idea. This is because it basically ruins normal access control for hierarchical filesystems and file descriptiors (which are basically capabilities). The system was great until I tried to add permissions to it. Relative resource addressing is always a good idea. That said, the actual structure of the VFS, with its recursive resolution walking thing, was pretty nice, and would have worked if only trusted entities (e.g. the kernel) actually performed resolution to file descriptors.

[h0bby1]

yes using a true filesystem structure for that is maybe not totaly suited, but the same principle with general tree structure that are not filesystem with named/typed member is still cool, specially with reference counter to each node, it can allow great flexibility for allowing the os to access to any infos from any device or ressource it know about with a single type of structure without having to include any type definition header, and without having to care about if it need to free or reset it when it's done with it because it's automatically freed when all reference to it are released, with a bit more code, it could track all the binaries that hold a reference to the ressource, as pretty much anything relevant in the os is stored using this tree structure, it could be easy to implement a similar thing to handle the get/release of a reference to it with a hook if the kernel or any other part of the os need to know when the ressource is being accessed, or to retrieve the status of any device or structure of the os using a unique tree system that is compatible with a path string search, but without being an actual filesystem at all, more something along the line of xpath to work with xml, exept here node are typed and the search is done using hash for the node name, so it's faster than xml

like if you want to access to any device, you can search it's bus tree for anything like vendor id or product id, class of the device, and the busmannager as a way to match bus specific class code to os recognisable device type, and then from there you can get it's status, or get a pointer to it's drivers binary structure to fetch any export symbol if you need to make a specific drivers call on it, or the bus mannager and device drivers also support a stream interface for simple read/write operation to or from a device, if i create a root node for the system, any device or information of the os could be able avaible through this with a simple xpath like synthax or the api for tree browsing, without the need to include any specific file to describe the structure being accessed

[xenos]

Let me see whether I understood correctly...

Let's say process 1234 is some file system driver and index 2 is one of the partitions it manages. Thus @1234:2 is the resource pointer pointing to that partition. Files can be accessed with a path of the form @1234:2/path/to/file, where /path/to/file is a file system path in the directory structure of that partition. It uniquely identifies that file.

Now my question is: Does the VFS really need to translate that path to another resource? Does the kernel need to know the meaning of /path/to/file, transform it to @1234:nnn and operate on this resource? Wouldn't it be easier to let the process 1234 do this transformation, i.e., to just pass the full file system path to the file system driver and let it do whatever a file system driver needs to do to find the file? After all, it is the file system driver, that reads the actual file system and checks whether /path, /path/to and /path/to/file really exist. The kernel cannot check this from just looking at the VFS - it needs to ask the file system driver to check what's on that partition.

In general I like the idea. It more or less reverses my design (which is probably more or less standard, but not yet fully implemented): I have a single resource tree with paths like /fs/fat32/0/path/to/file for some file on the first FAT32 partition found by the FAT32 file system driver. If someone tries to access this file, the kernel examines the VFS tree. It finds that /fs is a directory in the VFS, and that /fs/fat32 is not a directory, but a pointer to a process, which is the file system driver. The kernel then passes the remaining /0/path/to/file to this process. The file system driver then examines this shorter path, identifies 0 with the first partition it manages, and looks for /path/to/file on that partition.

The advantage I see in your approach is that there is no need for the kernel to search for the process which manages some resource, because it's part of the address. @1234:2/path/to/file is managed by process 1234. But if I'm looking for a file on some hard disk, how do I construct this address? How do I know the PID of the file system driver, if I just know which hard disk it is? Am I still missing something?

[NickJohnson]

Let's say process 1234 is some file system driver and index 2 is one of the partitions it manages. Thus @1234:2 is the resource pointer pointing to that partition. Files can be accessed with a path of the form @1234:2/path/to/file, where /path/to/file is a file system path in the directory structure of that partition. It uniquely identifies that file.

Yeah, basically. A partition would probably be a block device though and therefore be a file, not a directory. I assume you mean that 2 is the root of a mounted filesystem tree that it manages.

Now my question is: Does the VFS really need to translate that path to another resource? Does the kernel need to know the meaning of /path/to/file, transform it to @1234:nnn and operate on this resource? Wouldn't it be easier to let the process 1234 do this transformation, i.e., to just pass the full file system path to the file system driver and let it do whatever a file system driver needs to do to find the file? After all, it is the file system driver, that reads the actual file system and checks whether /path, /path/to and /path/to/file really exist. The kernel cannot check this from just looking at the VFS - it needs to ask the file system driver to check what's on that partition.

The kernel doesn't do anything here. The filesystem driver does the translation from @1234:2:/path/to/file to @1234:nnn (and may direct the resolver to another driver if it hits a mountpoint). The form @xxxx:yyyy is the only form that can be efficiently stored (as a 64-bit int) and that can be operated upon with I/O messages. You don't want to be resolving that path on every operation (like every read operation, for example) so transforming it to a numerical resource index helps a lot.

The advantage I see in your approach is that there is no need for the kernel to search for the process which manages some resource, because it's part of the address. @1234:2/path/to/file is managed by process 1234. But if I'm looking for a file on some hard disk, how do I construct this address? How do I know the PID of the file system driver, if I just know which hard disk it is? Am I still missing something?

Some filesystem driver acts as the root (the process keeps track of this, much like the root of the filesystem in a UNIX system, just not in kernelspace) and can have other filesystems mounted on it. That is set up by init. If you want to chroot, for example, just change which resource pointer the process thinks is root, and it will direct further resolve (i.e. open()) calls to that driver. The kernel takes no part in resolution at all. This is a distributed VFS in a pure microkernel, where each driver manages its own section of the VFS tree.

Also, by the way, the original post was like 2 years old. If you want to see how this was implemented, take a look at the Rhombus source; it's no longer being actively developed, but the VFS mechanism was finished (minus the permission system, which was the problem.)

[xenos]

Yeah, basically. A partition would probably be a block device though and therefore be a file, not a directory. I assume you mean that 2 is the root of a mounted filesystem tree that it manages.

Yes, that's what I meant.

The kernel doesn't do anything here. The filesystem driver does the translation from @1234:2:/path/to/file to @1234:nnn (and may direct the resolver to another driver if it hits a mountpoint). The form @xxxx:yyyy is the only form that can be efficiently stored (as a 64-bit int) and that can be operated upon with I/O messages. You don't want to be resolving that path on every operation (like every read operation, for example) so transforming it to a numerical resource index helps a lot.

Ah, I see, that totally makes sense. Now I like this approach even more

Some filesystem driver acts as the root (the process keeps track of this, much like the root of the filesystem in a UNIX system, just not in kernelspace) and can have other filesystems mounted on it. That is set up by init. If you want to chroot, for example, just change which resource pointer the process thinks is root, and it will direct further resolve (i.e. open()) calls to that driver. The kernel takes no part in resolution at all. This is a distributed VFS in a pure microkernel, where each driver manages its own section of the VFS tree.

Interesting - I haven't even thought about chroot yet, because I have no real root file system and mountpoints or the like, my VFS root basically contains the devices found in the computer, and there is no mounting at all, since all of them just have their place as detected by the appropriate drivers. But that's definitely something I will keep in mind.

Also, by the way, the original post was like 2 years old. If you want to see how this was implemented, take a look at the Rhombus source; it's no longer being actively developed, but the VFS mechanism was finished (minus the permission system, which was the problem.)

I didn't even look at the date Yes, I'll have a look

[h0bby1]

it's something i've been pondering also for a while, but i don't like the VFS approch all the much under linux, because it has many flaw, specially regarding typing, it's a bit what i don't always find very neat in unix with all coded with a C like approach, it's not object oriented and has very weak typing, and in VFS like the /proc directory in linux, virtual files are mostly to be used as variable , directory can be seen as a sort of struct, with members as the file in the directory, but there is no way you can know the type of the data you will read from a virtual file, and i always find that a bit bothering in the principle, some soft like pureftp also use directory with files as variable for the configuration, but file are not typed, in the case the file would only contain an int or something it can still work, and it can still offer nice feature to manage all kind of stream based interface from the kernel with an unique simple API, like you can just dump a wav file to the /dev/dsp, but it still also often require some ioctl calls, and same there is no way the program can know what are the valid ioctl calls for a given file, so it always has major flaw regarding typing, even if it can map everything in the same system under the same root filesystem api, it's not all that clean, and a strict file api is not the most efficient way to access data in case of vfs where the data is not an actual file, the open call is mostly useless, and it all boil down to simple memcpy or even a dword copy if the data from the file is just an int

under windows the equivalent is done with COM system, and the registry base, when you want to require some information about the system or drivers, you either use COM to instanciate a COM component for the particular purpose, or enumerators, it has also some drawback like you have to have the definition of all the class you want to use, and there are also lot of COM functions that use a declaration with void ** as parameters, so the typing is also pretty weak, and technically it could also lead to mistake in case you don't give the good class type as an input, but at least there is stronger typing , i somehow find the com approach better, but microsoft also abused it a lot with MFC, direct show, it can also quickly become hell with the typing when it start to make use of tons of templates and virtual class and COM component, but also it can give a very neat thing of distributed component that is missing a lot in unix like system, with COM there are component that are just assigned a specific function with a class based API, and it can use any com component that has been registered on the system for that particular purpose with the ID, and COM componant can also be distributed over network, or used in various language like javascript, c#, visual basic, as the class definition is associated with an IDL that give the global description of the class type that is entierly cross language, but it's not all unified API like you have in unix, and there are hundreds of COM component in OLE to achieve the same kind of functionality that you would expect from the VFS system in unix, it make in sort that it give a specific API for any kind of ressource you want to access, so it can become also very heavy in memory footprint, and it require to learn the function and api specific to any device or ressource, but in unix even if the api is standardised, with directory listing, stat(), open/read/write, the actual data contained in the file is still specific, and there are often also ioctl calls to be issued that are also specific, so all together it's not even all that standardised either

iit's why i want to use a bit hybrid approach, to have an api similar to the file system approach, with a tree structure, that can be also global for the whole system, some tree branches can be copied as reference into another tree a bit like you would mount a filesystem, and there is also equivalent to symlinking with node references, but the broswing/searching/api is much more efficient that the one of a filesystem, there is never any string comparison done to search node by name, and there is a direct typing so that a program can know how to make sense of the data contained into a node, and if the node contain data, this data can be accessed with a mem stream interface that make it very similar to a file, in sort that a node can contain binary data and can be accessed as a file, but there is always a way the program can know what to do with data, and the tree structure is also suited to define data in a way similar to object oriented programming, similar to xml, and it still give a standard api to browse all ressources in the system, and the program can know how to interpret the data contained in a node, if it's signed , not signed, string, node are not supposed to contain complex data in binary form, but the more complex data can be mapped with child node in case there are several value associated with it

like in linux lot of file in /proc contain already complex data, not only an integer or a string, and it would be more logical that the file would be more like a directory and all the informations in the file being set as file in the directory each with a simple type, and it would make it much more simple to test the actual format of the data, which member are present or not, and to be able to parse the informations without having to know exactly what version of the kernel it is, most information in /proc are stored as text and not binary data which is also not very memory savy, and not always that much efficient for parsing purpose

if the goal is to have standard api to reference all the ressource the kernel or drivers or any program or component can share, file system are not necessarily the most suited to achieve this, it can still be workeable as unix system use this very intensivly, but all the interface to parse directories, and deal with the streams or file data is not the most efficient and robust for that purpose