SFS directory entry

[ishkabible]

So I'm planing on using SFS(simple file system) for my OS. right now I'm writing an image reader in C to get the hang of the file system(and provide a utility for reading images too). I'm wondering what purpose the directory entries(in the index area) serve. They form no tree structure(that I am aware of) and file entries seem to be independent of them. It seems to me that the only way to find files is to do a linear search of all the file entries in the index area. If this is the case then what information do directory entries provide?

[ishkabible]

Is that in the VDisk source code? I can't find that in the draft or the wiki article. Either way I have no clue what that is; if that is from the source code I'll look there for more information.

edit: you seem to be reading a different SFS than me. you are looking at link 1, im looking at link 2.

1) http://www.star.bnl.gov/public/daq/DAQ1000/sfs.pdf
2) dimensionalrift.homelinux.net/combuster/vdisk/sfs.html

link 2 was referenced on the wiki page which is why I decided to use it.

[Brendan]

Hi,

So I'm planing on using SFS(simple file system) for my OS. right now I'm writing an image reader in C to get the hang of the file system(and provide a utility for reading images too). I'm wondering what purpose the directory entries(in the index area) serve. They form no tree structure(that I am aware of) and file entries seem to be independent of them. It seems to me that the only way to find files is to do a linear search of all the file entries in the index area. If this is the case then what information do directory entries provide?

The directory entries are there mostly so that empty directories can exist. This can be useful in practice because for most OSs an empty directory needs to exist before you can create a file in that directory (otherwise you get a "bad path" error). If there were no directory entries an OS could work around the problem by maintaining a list of "created but empty" directories in RAM, but that would lack persistence (e.g. a user could create a directory, then reboot or shift the disk to a different computer, then wonder why their empty directory disappeared) and would add a small amount of complexity to the simplest possible ("nothing cached, index area scanned every time you do anything") implementation.


Cheers,

Brendan

[ishkabible]

that makes sense, but I'm still stuck with a linear search :/ I guess that isn't so bad for the small virtual HD ill be using. thanks!!

edit: O Wait, your the guy that made the spec! right?

[Kevin]

There is exactly one thing that SFS is good at: Being simple.

If you want to have something that doesn't require searching the whole FS for a file, or even just something for which safe write support can be implemented, you should look for some of the more popular file systems like FAT or ext2.

[Brendan]

Hi,

edit: O Wait, your the guy that made the spec! right?

Yes.

There is exactly one thing that SFS is good at: Being simple.

If you want to have something that doesn't require searching the whole FS for a file, or even just something for which safe write support can be implemented, you should look for some of the more popular file systems like FAT or ext2.

Being simple (and being usable for exchanging files between different computers/systems) was the point of it.

If you want good performance (and maybe other things, like file permissions, file data fragmentation, etc) then you'd want something completely different. To get better performance with SFS you'd have to cache or index the index area (e.g. scan the index area when the file system is mounted and build a tree in RAM for fast directory lookups) and have something (maybe a bitmap) to track used/free sectors in the file data area.

It should be easy to add safe writes to SFS though. First, update the superblock if the size of the data area or the size of the index area needs to be changed (which is a single sector write). For creating new files write the file data to the data area (any failure won't matter), then add the entry anywhere you like in the index area (which is a single sector write). For modifying an existing file, create a new copy of the file's data (any failure won't matter), then change the file's entry in the index area to point to the new data instead of the old data (single sector write). Creating directories, deleting directories and deleting files is "single sector write" too. For "compaction" of the data area (if supported) you can do the same thing (clone the file's data, update the index area, repeat) but may have to do it in 2 passes (e.g. shift file data to one end of the data area, then shift it all back to the other end). All of this is easy as long as there's enough free space on the disk (and if there isn't enough free space you can just return a "not enough space" error or maybe contemplate doing it without safe writes).

The only thing that isn't possible to do safely is doing compaction for the index area; but you should never really need to do compaction for the index area anyway; and the "worst case" failure (if you want to do it as safely as possible) would be duplicate entries.

Of course SFS wasn't really intended for this usage model. It was intended for exchanging files between computers/systems, where you format a disk and copy files to it, then take it to another computer and read all the files (and maybe recycle the disk by formatting it and writing new files later).

Note: For safe writes on FAT, you can't avoid the chance of lost clusters unless you can atomically update the directory entry and the "cluster allocation table" (in 2 different parts of the disk) at the same time.


Cheers,

Brendan

[Kevin]

Being simple (and being usable for exchanging files between different computers/systems) was the point of it.

Never said anything else.

For "compaction" of the data area (if supported) you can do the same thing (clone the file's data, update the index area, repeat) but may have to do it in 2 passes (e.g. shift file data to one end of the data area, then shift it all back to the other end). All of this is easy as long as there's enough free space on the disk (and if there isn't enough free space you can just return a "not enough space" error or maybe contemplate doing it without safe writes).

Yes, compaction is what I meant. If you don't want to end up with "No space left" when the majority of the space is really free, you absolutely need this. Not doing it is okay for the use case you mentioned at the end of your post (writing the whole image at once, and then only read from it), but for the main file system you just cannot live without it.

The hard thing about compaction in SFS is that it doesn't support file fragmentation, so you always have to copy whole files (this fact alone already makes it very slow for larger files). Leaving aside that this means compaction may not even be (safely) possible even though only half of the space is really used, the algorithm that you need to calculate your plan for moving files around certainly isn't simple anymore: Neither in terms of being trivially implementable, nor in terms of computational complexity (I'm pretty sure that this is NP hard).

So if you actually considered implementing compaction (which is an absolute requirement for using it as your main FS), you would be much better off using an initially not-so-simple FS that saves you the complexity of compaction. And once you have implemented FAT or ext2 as your main FS, you could just as well use that for exchanging files, with the additional benefit that everyone understands FAT.

Note: For safe writes on FAT, you can't avoid the chance of lost clusters unless you can atomically update the directory entry and the "cluster allocation table" (in 2 different parts of the disk) at the same time.

Yeah, though it depends on what you define as safe. I'm willing to accept cluster leakage in case of a crash (and require an fsck run to reclaim them), but not data corruption. Without a journal it's hard/practically impossible to avoid leaking blocks in case of a crash.

[Brendan]

Hi,

So if you actually considered implementing compaction (which is an absolute requirement for using it as your main FS), you would be much better off using an initially not-so-simple FS that saves you the complexity of compaction. And once you have implemented FAT or ext2 as your main FS, you could just as well use that for exchanging files, with the additional benefit that everyone understands FAT.

Heh - don't use SFS for your main file system

It's not fast enough, doesn't support file permissions (and things like "file owner", etc), doesn't support fragmented files (makes it hard to support "append" with decent performance) and doesn't support special file types (e.g. symbolic links/shortcuts). In addition, it won't support <random feature that makes your OS look good> (like the file versioning that made VMS a bit special, or the "volume shadow copy" that made Windows a bit special, or "resource forks" that made Macintosh a bit special, or "storage pools" that made Solaris a bit special, etc...).

Mostly, you should probably invent your own file system to use as your OSs main file system, because it's the only way you can support some unique feature/s that makes your OS a bit special; and if there's nothing special about your OS then that would be a little sad.


Cheers,

Brendan

[Kevin]

Heh - don't use SFS for your main file system

This is probably what I was trying to say.

The OP seems to intend using SFS as his main file system, and that just doesn't sound like a good idea.

Mostly, you should probably invent your own file system to use as your OSs main file system, because it's the only way you can support some unique feature/s that makes your OS a bit special; and if there's nothing special about your OS then that would be a little sad.

I could imagine a lot of unique features that don't require inventing your own file system. Even if you need to store something that a given FS doesn't support directly, it could still support some mechanism for storing additional metadata. If so, this is probably a better approach as you can still use tools for dealing with the FS.

But if you really want to create your own, I would add: And you should only invent your own file system after you have implemented at least two or three existing ones, so that you have some idea of how file systems work. Reinventing the wheel is fine, but don't make it square.

[Combuster]

SFS has a different purpose of design as FAT. It's still valid to start with SFS support and later upgrade to a journalled filesystem if you go for the work first, optimise later approach. FAT and EXT2 are similarly bad choices in that regard.

[ishkabible]

if you go for the work first, optimise later approach

Well that is my idea for my first OS. I'm not worried about permissions, speed, or other nice things really. Although, given that I have no experience with OS dev, I have no way of knowing weather or not that will come back to bite me.

if there's nothing special about your OS then that would be a little sad

It's my first OS; It seemed overly advantages to expect anything all that great. Maybe I'm selling my self short but every time I don't define strict limits on my project I never get done. Using a simple file system to start out with was part of that.

Mostly, you should probably invent your own file system to use as your OSs main file system

I'm not really sure what I want out of my file system yet honestly. I want to be able to implement the C library functions and that's about it.

Maybe I'm going about this wrong but it seems like a good first try to me. I'll look at other options and see if it might be better within the scope of my project. Lack of experience makes decisions like these difficult.

[bluemoon]

if you go for the work first, optimise later approach

Well that is my idea for my first OS. I'm not worried about permissions, speed, or other nice things really. Although, given that I have no experience with OS dev, I have no way of knowing weather or not that will come back to bite me.

I started with something similar with SFS, perhaps much simpler (without directory structure).
It only take about a few hour of work, you will then see and learn what it lack, and have better understanding to plan the VFS design and start writing FAT or <your own fs>
It worth the effort.

[Brendan]

Hi,

if you go for the work first, optimise later approach

Well that is my idea for my first OS. I'm not worried about permissions, speed, or other nice things really. Although, given that I have no experience with OS dev, I have no way of knowing weather or not that will come back to bite me.

I'd recommend starting by implementing some sort of VFS layer that keeps track of what is mounted where. Initially the VFS might only handle one file system mounted at "/"; but sooner or later you'll want to be able to handle different file systems mounted at different places; and eventually you'll also want to add support for caching file data, etc.

In this case; if SFS is the first file system you implement then you might mount an SFS partition at "/" for a while (but that doesn't really make it your main file system). Later you might implement another file system and you might mount the other file system at "/" instead, and just use SFS for things like floppy disks, USB flash, etc. After you've implemented several file systems (maybe SFS, FAT, ISO9660, NFS and ext2/3) you'll have a lot more confidence/experience, and you'll also have good idea of which features (including any special/unique features) you want for your OS's main file system. Then you might start designing and implementing the OS's main file system.


Cheers,

Brendan