I've been implementing file/directory accessing by having "open file/directory" structures within my filesystem that store the current read/write position and cache things like the last block-pointers block, etc...
this works for files; i can disallow a file to be opened for writing whenever another process has it open. however, this does not work well for directories. if one process has open the root directory for reading and another process needs to remove/create a file in the root directory it should be able to do so right away.
this brings up a problem: what happens when the reading process continues reading directory entries but they have changed? i don't care so much if the reader gets out-dated information, but i do care about how the situation is handled in the kernel. for example, if a file is deleted, freeing a block from the directory, and then later the reader still thinks there is another file and tries to read its entry from the next block in the directory, then there is a problem.
the solutions that i have come up with so far are:
1. when a directory is changed, force all references to it to be re-opened -- messy, and i'd like a more transparent solution
2. cache the entire directory when it is opened. this seems better, but i wouldn't want it cached in kernel memory (malicious process could open many dirs) and it doesn't seem so good to require the process to allocate that memory either (could be a large directory)
so i'm wondering if there is an elegant solution or another idea to make one of these more feasible.
TIA
FS directory caching/locking
Re:FS directory caching/locking
Hi,
For example, (depending on your OS design) the caller could provide it's own buffer for the OS to fill out - "int get_directory(void *buffer, int buffer_size, char *directory_name)". If the buffer is too small the kernel would return an error. Software that needs one entry at a time can include it's own code to split it up (for e.g. it could be done in a C library).
For my OS, the directory information will be cached by the VFS thread (which has it's own address space) and sent by the VFS as a single message - other software uses "int request_directory(char *directory_name)" which returns immediately, and a message containing the directory contents arrives some time later (when it's ready). It's mostly the same thing, but done in a non-blocking messaging way...
On top of this you could allow software to set up "notifications". The idea is that software could set a notification on a file or directory and receive a message or something if the directory or file changes. If you consider implementing a file manager window that displays the contents of a directory that changes when the directory changes, you'll see what these notifications are for (most modern OSs have something similar - it saves continually polling).
Cheers,
Brendan
IMHO this is the only transparent solution. Your OS could only provide code to read the entire directory in one go, rather than allowing it to be read piece by piece.HOS wrote:2. cache the entire directory when it is opened. this seems better, but i wouldn't want it cached in kernel memory (malicious process could open many dirs) and it doesn't seem so good to require the process to allocate that memory either (could be a large directory)
For example, (depending on your OS design) the caller could provide it's own buffer for the OS to fill out - "int get_directory(void *buffer, int buffer_size, char *directory_name)". If the buffer is too small the kernel would return an error. Software that needs one entry at a time can include it's own code to split it up (for e.g. it could be done in a C library).
For my OS, the directory information will be cached by the VFS thread (which has it's own address space) and sent by the VFS as a single message - other software uses "int request_directory(char *directory_name)" which returns immediately, and a message containing the directory contents arrives some time later (when it's ready). It's mostly the same thing, but done in a non-blocking messaging way...
On top of this you could allow software to set up "notifications". The idea is that software could set a notification on a file or directory and receive a message or something if the directory or file changes. If you consider implementing a file manager window that displays the contents of a directory that changes when the directory changes, you'll see what these notifications are for (most modern OSs have something similar - it saves continually polling).
Cheers,
Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
-
distantvoices
- Member

- Posts: 1600
- Joined: Wed Oct 18, 2006 11:59 am
- Location: Vienna/Austria
- Contact:
Re:FS directory caching/locking
@Brendan: do you count directory entries prior to requesting the contents? Or do you simply have the vfs service pass an array of pages forward to the client - which contains the directory entries in array-form?
As for the notification stuff: I think of this as kinda event: just have the fs service raise an event for each process/thread peeking in the actual directory in case of a change.
In my opinion, this would require some additional book keeping in the form of lists: directory node -> proc1->proc2->proc3 ... you know what I mean ... so that we know whom to notify.
stay safe
As for the notification stuff: I think of this as kinda event: just have the fs service raise an event for each process/thread peeking in the actual directory in case of a change.
In my opinion, this would require some additional book keeping in the form of lists: directory node -> proc1->proc2->proc3 ... you know what I mean ... so that we know whom to notify.
stay safe
... the osdever formerly known as beyond infinity ...
BlueillusionOS iso image
BlueillusionOS iso image
Re:FS directory caching/locking
Hi,
The new version will be very similar (I haven't thought of a reason to change it yet), but will eventually support additional "get directory" modes (get entire directory, get everything except hidden files, only get things that I have permission to write to, get files that comply with "abc*g?i", etc).
Cheers,
Brendan
The last version of my OS just passed one message containing a header and all the directory entries. The header included the directory name, a time stamp, the number of entries in the array, etc.beyond infinity wrote:@Brendan: do you count directory entries prior to requesting the contents? Or do you simply have the vfs service pass an array of pages forward to the client - which contains the directory entries in array-form?
The new version will be very similar (I haven't thought of a reason to change it yet), but will eventually support additional "get directory" modes (get entire directory, get everything except hidden files, only get things that I have permission to write to, get files that comply with "abc*g?i", etc).
I'll probably have three "notification lists", one for file systems (mount/unmount), one for directories and the other for files. When something is changed the VFS will need to search the corresponding notification list and send a message to anyone that wanted it. I won't add anything to each directory node to help with notifications though, as I want to support wildcards, etc. For example, an anti-virus checker might ask to be notified if any file that ends in "*.exe", "*.sys" or "*.drv" changes, or photo-album software might want to know about any "*.jpg" or "*.png" being created (regardless of where).beyond infinity wrote:As for the notification stuff: I think of this as kinda event: just have the fs service raise an event for each process/thread peeking in the actual directory in case of a change.
In my opinion, this would require some additional book keeping in the form of lists: directory node -> proc1->proc2->proc3 ... you know what I mean ... so that we know whom to notify.
Cheers,
Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
-
distantvoices
- Member

- Posts: 1600
- Joined: Wed Oct 18, 2006 11:59 am
- Location: Vienna/Austria
- Contact:
Re:FS directory caching/locking
Ha, that's one cool thing, Brendan! Haven't viewed it from This point of vue. 
as for the directory stuff: That's an interresting approach you 're taking here. In my OS, there is a need to say count_dirents() first and then get_directory() with a previously allocated buffer which has the needed size. Say, I need two messages to accomplish one task. Your Method is better. One never learns out, honestly.
as for the directory stuff: That's an interresting approach you 're taking here. In my OS, there is a need to say count_dirents() first and then get_directory() with a previously allocated buffer which has the needed size. Say, I need two messages to accomplish one task. Your Method is better. One never learns out, honestly.
... the osdever formerly known as beyond infinity ...
BlueillusionOS iso image
BlueillusionOS iso image
- Pype.Clicker
- Member

- Posts: 5964
- Joined: Wed Oct 18, 2006 2:31 am
- Location: In a galaxy, far, far away
- Contact:
Re:FS directory caching/locking
you might have a reader/writer locking policy:
- as many readers can read the directory at the same time
- only one writer can modify the directory at a time
- if someone attempt to read(resp. write) while the directory is being written(resp. read), he will be suspended until writing (resp. reading) is over.
Imho, the "reading lock" do not necessarily need to encompass the whole 'opendir/closedir' session, but when opening a file, the following operations should at least be atomically protected by a reading lock:
- search for the name in a particular block of the directory
- check access rights for that file
- create the file handle for the file (using inode number from the directory content)
otherwise, you could have race condition where someone gets access to a protected file because he created a less-protected file and deleted it between steps 2 and 3.
- as many readers can read the directory at the same time
- only one writer can modify the directory at a time
- if someone attempt to read(resp. write) while the directory is being written(resp. read), he will be suspended until writing (resp. reading) is over.
Imho, the "reading lock" do not necessarily need to encompass the whole 'opendir/closedir' session, but when opening a file, the following operations should at least be atomically protected by a reading lock:
- search for the name in a particular block of the directory
- check access rights for that file
- create the file handle for the file (using inode number from the directory content)
otherwise, you could have race condition where someone gets access to a protected file because he created a less-protected file and deleted it between steps 2 and 3.
Re:FS directory caching/locking
Hi,
The problem with my "single message" approach is that the number of directory entries is limited by the size of a message. If you assume each directory entry consumes an average of 128 bytes, then you can't fit more than 32 entries in a 4 KB page. I support 32 MB messages, which should be enough (around 260 thousand entries), but most message based OSs don't allow messages to be this large. My relatively large message size is going to cause problems when there isn't enough free RAM available - transferring message data to/from swap space while the message is being created or read (very ugly, but hopefully also very rare)....
@Pype.Clicker: The problem with any form of locking is lock contention. For the virtual file system on a single computer this isn't too much of a problem, but I'm going for a distrubuted file system where all computers (and all users) need to share the same (virtual) file system (rather than just one computer), so for me lock contention within the VFS needs to minimized. With this in mind I've avoided the need for locking directories completely (it's an atomic operation as far as most software is concerned).
For file access locking is unavoidable. Here I'll have three types of locks (or 3 ways to open a file) - write access, read access and append access. For append access one thread may add data to the end of the file while many other threads are reading from it (most OSs support this). To further reduce lock contention I'll be using versioning - when a thread asks to open a file in write or append mode a new version of the file is created (if no-one else has already opened the same file in write or append mode). For example, if threads are reading a file it can still be opened in write mode, rather than the "open for writing" being denied unless no-one is reading.
Combining all of this, the only cases where an "open file request" will be denied due to sharing are:
a) the open request is for write or append mode and someone else has already opened the file in write or append mode.
b) the open request is for reading from a new file (that has no previous version) that is still opened in write mode.
In either of these cases the request may be delayed for several seconds within the VFS in the hope that who-ever is modifying the file may close the file quickly enough to allow the VFS to return a "file opened" status after the delay. This prevents the need for good software to retry later (just give up and show the user an error message) and reduces the frequency that bad software can continually make unsuccessful requests to open the same file.
Of course planned features like these aren't the same as implemented & tested features...
Cheers,
Brendan
Just different solutions with different disadvantages. Asking for a count and then asking for the directory information leads to problems when the directory contents change after the count is obtained but before the directory is requested. This leads to locking, which leads to problems when someone doesn't unlock (and the various ways of avoiding the "didn't unlock" problem).beyond infinity wrote:as for the directory stuff: That's an interresting approach you 're taking here. In my OS, there is a need to say count_dirents() first and then get_directory() with a previously allocated buffer which has the needed size. Say, I need two messages to accomplish one task. Your Method is better. One never learns out, honestly.
The problem with my "single message" approach is that the number of directory entries is limited by the size of a message. If you assume each directory entry consumes an average of 128 bytes, then you can't fit more than 32 entries in a 4 KB page. I support 32 MB messages, which should be enough (around 260 thousand entries), but most message based OSs don't allow messages to be this large. My relatively large message size is going to cause problems when there isn't enough free RAM available - transferring message data to/from swap space while the message is being created or read (very ugly, but hopefully also very rare)....
@Pype.Clicker: The problem with any form of locking is lock contention. For the virtual file system on a single computer this isn't too much of a problem, but I'm going for a distrubuted file system where all computers (and all users) need to share the same (virtual) file system (rather than just one computer), so for me lock contention within the VFS needs to minimized. With this in mind I've avoided the need for locking directories completely (it's an atomic operation as far as most software is concerned).
For file access locking is unavoidable. Here I'll have three types of locks (or 3 ways to open a file) - write access, read access and append access. For append access one thread may add data to the end of the file while many other threads are reading from it (most OSs support this). To further reduce lock contention I'll be using versioning - when a thread asks to open a file in write or append mode a new version of the file is created (if no-one else has already opened the same file in write or append mode). For example, if threads are reading a file it can still be opened in write mode, rather than the "open for writing" being denied unless no-one is reading.
Combining all of this, the only cases where an "open file request" will be denied due to sharing are:
a) the open request is for write or append mode and someone else has already opened the file in write or append mode.
b) the open request is for reading from a new file (that has no previous version) that is still opened in write mode.
In either of these cases the request may be delayed for several seconds within the VFS in the hope that who-ever is modifying the file may close the file quickly enough to allow the VFS to return a "file opened" status after the delay. This prevents the need for good software to retry later (just give up and show the user an error message) and reduces the frequency that bad software can continually make unsuccessful requests to open the same file.
Of course planned features like these aren't the same as implemented & tested features...
Cheers,
Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.