New Tutorial on BMFS

[tay10r]

I've added a tutorial page in the Wiki for BMFS.

I'm hoping it makes it easier for projects to integrate it in their code base.

If you don't plan on using it with your project, that's okay! If you read it and think it could be improved or is unclear in some areas, let me know.

Here's a link to the page: https://wiki.osdev.org/BMFS

Thanks!

[BenLunt]

As some of you know, I am quite fond of File Systems, and like to look over almost all I come across. However, my interest isn't the code that is used to access it, but the actual file system content on the target media. i.e.: The way it is stored on the disk, the boot sector, super block(s), FAT(s), bitmap(s), etc.

I see that the link you provide, as well as the links within that page show how to write code to call an existing library, but do you have any documentation on the actual format of the media content of the file system?

Is the documentation at https://github.com/ReturnInfinity/BMFS/ ... 0System.md current, i.e.: to what you are discussing, or is this the original BMFS and you have forked off of it?

This is, as you state, a very simple file system. Please don't think I am disrespecting you or your work, but please let me make a few comments.
(I haven't looked over it in detail, but have glanced and found a few things)

1) Start of files should be indexed by blocks, not bytes. Even though 64-bits allows for quite large volumes, even for byte indexes, start indexes for anything should be block indexes, not byte indexes (indices ?).
2) Is a file limited to 2Megs in size or can it occupy multiple blocks? If so, how do you indicate where these blocks are?
3) 192d (0xC0) bytes for a file name is somewhat excessive unless it includes the path as well.
4) Speaking of, are paths assumed through the directory path, or are paths stored within the file name area (#3 above).
5) How are path names delimited? Forward slash, back slash, space?

Again, don't think I am dis'ing your stuff here. I am just a stickler for details.

Thanks,
Ben

- http://www.fysnet.net/osdesign_book_series.htm

[pat]

The tutorial mentions in its initial design it only supported 64 files in the root directory, and then goes to mention that it now supports sub-directories, but it didn't say anything about file limits. Does the 64 file per directory limit still exist?

[tay10r]

The tutorial mentions in its initial design it only supported 64 files in the root directory, and then goes to mention that it now supports sub-directories, but it didn't say anything about file limits. Does the 64 file per directory limit still exist?

Great question! I'll clear that up in the tutorial. The answer is no, it no longer has this limit. The current layout doesn't actually limit the directory size, but the implementation doesn't handle creating more than 65536 entries in a single directory. In the next version, I'm allowing directories to be resized, so they can grow larger than that if they need to.

As some of you know, I am quite fond of File Systems, and like to look over almost all I come across. However, my interest isn't the code that is used to access it, but the actual file system content on the target media. i.e.: The way it is stored on the disk, the boot sector, super block(s), FAT(s), bitmap(s), etc.

Nice to meet you! I enjoy reading about them as well.

I see that the link you provide, as well as the links within that page show how to write code to call an existing library, but do you have any documentation on the actual format of the media content of the file system?

Is the documentation at https://github.com/ReturnInfinity/BMFS/ ... 0System.md current, i.e.: to what you are discussing, or is this the original BMFS and you have forked off of it?

That is the documentation for the current layout. I had a fork going a couple of years ago, but Ian Seyler eventually gave me write access to the project.

This is, as you state, a very simple file system. Please don't think I am disrespecting you or your work, but please let me make a few comments.
(I haven't looked over it in detail, but have glanced and found a few things)

1) Start of files should be indexed by blocks, not bytes. Even though 64-bits allows for quite large volumes, even for byte indexes, start indexes for anything should be block indexes, not byte indexes (indices ?).
2) Is a file limited to 2Megs in size or can it occupy multiple blocks? If so, how do you indicate where these blocks are?
3) 192d (0xC0) bytes for a file name is somewhat excessive unless it includes the path as well.
4) Speaking of, are paths assumed through the directory path, or are paths stored within the file name area (#3 above).
5) How are path names delimited? Forward slash, back slash, space?

Again, don't think I am dis'ing your stuff here. I am just a stickler for details.

No please! Criticism is welcome. It is simple. I'm considering adding journaling and I'm welcome to other suggestions.

1. This is usually what I've seen, so I agree. Most file systems don't index systems by the byte. I'm not too concerned about this, but I probably will change it in the next version or two.
2. A file is not limited to 2MiB, it can be larger than that. The size of the file, as well as the space allowed for it to grow, is indicated in the allocation table. The block size is currently 2MiB, but in the next version I'm allowing it to be specified in the file system header (I will implement block resizing as well.)
3. Linux has a max of 255, so I used that as a reference. I don't think 192 is that excessive, at all. Sometimes file names are stored as hashes. The SHA512 hash as a file name would occupy 128 bytes.
4. Paths are not stored in the file name. Paths are split into their directory names and then used to find the file or subdirectory.
5. Path names are delimited by forward or backward slashes, if I can remember correctly. I'm pretty sure I decided to use both of them. Spaces are not treated differently from other file name characters. The only file name character that is not really suggested is null, but I don't think that it's enforced in the implementation.

Thanks for all the questions! Keep them coming, if you still have them.

[Antti]

As far as I understand, the BareMetal project has gotten very positive feedback in general. Especially the documentation makes it look like a very professional project and that is definitely a good thing. A lot of hobby projects understate themselves and it makes them quite irrelevant when someone would be interested in writing applications or even low-level modules on the new system. The BareMetal project does things in an interesting way and has been proved to gain positive feedback and attention.

However, the trend might change if going to far. I think it is not bad to promote ones own project but it is almost our responsibility here on OSDev.org to "cool down" the situation. I took a quick look at the Pure64 and BMFS and it looks that these have not been critically reviewed. It might be too early to introduce a main wiki article in a way we do for the established technology.

I'm not objective either because I have my own boot loader (and I mostly compare other projects to that) that can basically do the same function as Pure64. However, I am sure that my project would get hard criticism if I tried to tell that people should use it and treat it like it were an established and proven technology, i.e. "switch from FAT to BMFS" because it is much better.

I just wrote a reply that I would expect to receive myself if I were in a similar situation.

[Korona]

I agree this Antti. At the very least, the wiki page needs a big disclaimer at the top that states that it was contributed by one of the authors of the BMFS. Being enthusiastic about your stuff is OK, selling it as being established software is not OK.

[tay10r]

Fair enough, I added a disclaimer.

[Korona]

Thank you. I think the disclaimer is quite good and could serve as an example for similar pages (that currently lack a disclaimer).

Regarding the page content: The library design seems to be sound (at least for a library that is meant to get started). The only thing that I spotted when skimming over it is that the seek() -> read() approach cannot be made thread safe, so it might be wiser to just give a position argument to read(). Also: Is writing supported? Overall, I like the idea of providing a library and host OS tooling to implement a basic file system that can easily be integrated into OSs.

[tay10r]

Thank you. I think the disclaimer is quite good and could serve as an example for similar pages (that currently lack a disclaimer).

I'll be sure to make another disclaimer if I make ever make a page for another project.

]Regarding the page content: The library design seems to be sound (at least for a library that is meant to get started).

The file system has a long way to go before I would consider it production ready, I'll admit that. I plan on adding journaling and file system level encryption (just more features of a modern file system), so that people feel a little bit more confident using it. Symbolic links and FIFOs will be added too, (I know FIFOs are not usually implemented on disk, but it's just too easy to add them.)

The only thing that I spotted when skimming over it is that the seek() -> read() approach cannot be made thread safe, so it might be wiser to just give a position argument to read().

Good point. I have not considered allowing the use of the structure across threads. I had it in mind that there would be one structure per thread. Since file locking might be useful as well, I think I might add a lock and unlock callback function, and allow it to be defined by the caller. I've seen this in a FAT library before. Adding the offset to the read function would work too, and I've seen that in a few other libraries, I just don't like adding too many parameters to a single function. I guess I would write a read-request structure, and pack it all into that. I might have to do that anyway for asynchronous IO functions.

Also: Is writing supported?

Yes, it is currently implemented and used by the utility program to copy over files from the host file system to the disk image file system. I don't think it handles resizing files larger than 2MiB though. I need to make a patch release for that soon, it's an easy fix.

Overall, I like the idea of providing a library and host OS tooling to implement a basic file system that can easily be integrated into OSs.

Thanks, me too! The beauty of this approach for the file system is that the layout can change and features can be added without any cost to the projects using it. I'm hoping to make it more than just a basic file system, but for now it's a good starting point.

[BenLunt]

...what you would want to see in the next release.

Hi,

As for a simple file system, easy to implement, and yet worth the time and effort, I would implement things that would make it robust, though easy to implement and use.

• Super block (your "header" structure) that is backed up some where. For example, if the primary header (super block) is at LBA 1024, a backup (secondary) header is at: LBA = ((block count / 2) + 1)
• Bitmap(s) of allocated blocks.
• unlimited file name lengths, but only using what space is needed. i.e.: No wasted space. (i.e.: currently if the file name is "a.img", 0xC0 - strlen("a.img") is a lot of wasted space).
  For example, a file system I was/is a part of is the LeanFS, and it uses a count of 16-byte blocks for filenames, wasting at most 15 bytes of space per filename, yet allowing a file name to be quite long (four digits if I remember correctly).
  Another file system I use, and created myself for numerous reasons, is the FYSFS, and allows unlimited file name sizes, though can waste around 80 bytes of space.
  (Side note: FYSFS was my first file system project, other than the (in)famous FAT file system. I wanted to create something that I could use to test my kernel with to make sure it was completely FS independent, as well as the enjoyment of creating a file system. It served its purpose and now I use the LeanFS file system as my default choice.)
• Streams: The LeanFS uses Extents to indicate how many blocks are allocated for a specific part of the file's data.

  Code: Select all

  struct STREAM {
    bit64u start_lba;  // starting LBA relative to some point: start of volume, start of band, start of ????
    bit32u count;      // count of consecutive blocks used for this stream
  };

• Bands: The LeanFS uses bands, or sections of the media to store all data needed for that part of the file system. For example, the Inode, Metadata, file name, *and* allocation bitmap for any specific file is within a section of the media. This way, if for some reason a portion of the media is destroyed, any remaining bands (sections) are still intact and can be extracted 100%.
• Symbolic links: Allows for numerous "Directory entries" to point to the same file. This has a huge advantage in common used code bases.
  For example, let's say that you have a standard library (source) file that is linked to multiple projects. Rather than having to use the same, some times long path for each project, you can simply create a Symbolic Link directory entry right in the project's main path and use it as a link to the actual library (source) file.
  There are draw backs to this though. What if you move the original file and your file system doesn't have the capabilities to update all links?
• Meta Data: You have already implemented some of this with your directory entry, but what about non-file system specific meta data items.
  For example, the LeanFS allows data to be stored in a file's Inode or a separate Inode linked to this Inode to store non-file system specific meta data, which allows the OS to store information about the app, user, network, etc. currently using the file.

As for a Journal and encryption, these are good things to have for a file system, but be careful, both of these items will make a simple file system, instantly not so simple anymore.

Have a look at many file systems and write down notes of the things you like from each, then you can see if you want to implement these within yours.

For example, I am not saying that my FYSFS file system is a good file system. It simply served its purpose when I was trying to write independent kernel file system code, as well as the enjoyment of creating one.

A much better and more thought out file system is the LeanFS written for FreeDOS. It uses most of the items I list above. In my opinion it is right at that point where it has a lot of functionality but is still somewhat simple. Adding any more to it and it won't be so simple any more.

There are a few other things I want to list:

• Variable boot sector space: The FAT file system allows a boot sector code block to use as much disk space as needed (though not all implementations account for this). The Linux Ext 2/3/4 file systems do not. Two blocks. Period. Ouch. Give a variable spaced boot sector allowing a single block or <exaggeration> half the drive if needed</exaggeration>.
• Store the last state of the volume in the super block (header). For example, was the volume previously successfully dismounted? If not, don't try to mount it without first trying to fix it.
• Use magic numbers. i.e.: Give specific, static, values to certain structures of the file system. For example, if the primary super block is ever lost, you can search the disk somewhere in the range of ((block size / 2) - 16) -> ((block size / 2) + 16) for a block that contains certain "magic" numbers to see if there is a valid back up super block. This also allows your driver to verify that you actually loaded a valid Inode before modifying the data it may or may not point to.

Again, have a look at a good list of file systems, checking out each that look interesting and then make a list of pro's and con's. Then go from there.

As noted before, I have chosen the LeanFS file system as my default file system, though I have implemented many, including the SFS file system recently discussed in this forum.

I hope this helps,
Ben

[tay10r]

• Super block (your "header" structure) that is backed up some where. For example, if the primary header (super block) is at LBA 1024, a backup (secondary) header is at: LBA = ((block count / 2) + 1)

This makes sense. I wasn't sure I would still need it if I added journaling, but I've been thinking about. This is what GPT does as well. I would also add a checksum to detect for corruption.

[*]Bitmap(s) of allocated blocks.

I was actually thinking of using the same algorithm I used for memory allocation. A table of allocation entries (containing offset and size), with one of the entries pointing to the table itself. The table is then able to reallocate itself somewhere else when it needs to grow. It would be a LOT easier to implementation for disk space allocation because disk space is linear and memory is in chunks. The bitmap approach is nice because it is simple and very space efficient. The table method, the way I plan on using it, is also efficient but I'm not sure how they compare. Bitmaps, the way I understand them, lose their efficiency as the block size decreases.

I'll have to think about this a bit more.

[*]unlimited file name lengths, but only using what space is needed. i.e.: No wasted space. (i.e.: currently if the file name is "a.img", 0xC0 - strlen("a.img") is a lot of wasted space).
For example, a file system I was/is a part of is the LeanFS, and it uses a count of 16-byte blocks for filenames, wasting at most 15 bytes of space per filename, yet allowing a file name to be quite long (four digits if I remember correctly).
Another file system I use, and created myself for numerous reasons, is the FYSFS, and allows unlimited file name sizes, though can waste around 80 bytes of space.

I agree, the name field has to be a little bit more efficient. While I don't think it's an issue in practice, I think it definitely needs to be fixed. Sixteen byte blocks would work well. I might do that. I could also try to approach that ELF files took and store file names in a string table, using an index to reference the name. I'm not sure, though, if it would be worth the complexity. Sixteen byte blocks sound many times easier to implement.

(Side note: FYSFS was my first file system project, other than the (in)famous FAT file system. I wanted to create something that I could use to test my kernel with to make sure it was completely FS independent, as well as the enjoyment of creating a file system. It served its purpose and now I use the LeanFS file system as my default choice.)

LeanFS sounds pretty neat! Does it have a URL?

[*]Streams: The LeanFS uses Extents to indicate how many blocks are allocated for a specific part of the file's data.

Code: Select all

struct STREAM {
  bit64u start_lba;  // starting LBA relative to some point: start of volume, start of band, start of ????
  bit32u count;      // count of consecutive blocks used for this stream
};

Currently BMFS uses byte indices instead of block indices, relative to the beginning of the disk. It does not store the block count, just the current size of the data.
The block count is stored in the allocation table. This difference just reflects the difference in bitmap and table approach.

[*]Bands: The LeanFS uses bands, or sections of the media to store all data needed for that part of the file system. For example, the Inode, Metadata, file name, *and* allocation bitmap for any specific file is within a section of the media. This way, if for some reason a portion of the media is destroyed, any remaining bands (sections) are still intact and can be extracted 100%.

This makes sense. It would be helpful, in this case, to know the disk geometry to ensure that the contents are separated physically. I'll have to add more callback functions to the disk geometry. It would be helpful to have a separate band for backup structures as well, I would imagine. I'll add it to the to-do list.

[*]Symbolic links: Allows for numerous "Directory entries" to point to the same file. This has a huge advantage in common used code bases.
For example, let's say that you have a standard library (source) file that is linked to multiple projects. Rather than having to use the same, some times long path for each project, you can simply create a Symbolic Link directory entry right in the project's main path and use it as a link to the actual library (source) file.
There are draw backs to this though. What if you move the original file and your file system doesn't have the capabilities to update all links?

I have been planning on supporting them for a few months now. The way I was planning on doing it was by having a path translation table. Moving a file or symbolic link would involve updating the paths in the translation table. But I'm still not quite sure. I would like to learn more about the corner cases like that, so I can make sure that the behavior is a mostly consistent with other file systems.

[*]Meta Data: You have already implemented some of this with your directory entry, but what about non-file system specific meta data items.
For example, the LeanFS allows data to be stored in a file's Inode or a separate Inode linked to this Inode to store non-file system specific meta data, which allows the OS to store information about the app, user, network, etc. currently using the file.[/list]

I agree. In another file system implementation I did, files and directories had completely different meta data (except for the name, of course). The directory data contained (among a few other things) the number of subdirectories and files in that directory. Subdirectories came first and then files second. This allowed for the two entries to be completely different, without causing too much of an implementation difficulty. I might take this approach again.

As for a Journal and encryption, these are good things to have for a file system, but be careful, both of these items will make a simple file system, instantly not so simple anymore.

At this point, I'm focused on the simplicity in the API. You can opt out of encryption and journaling by having a field in the superblock that says so. At the very least, having callbacks for encryption is a must. It keeps the implementation simple while still allowing for encryption to be trivially added.

There are a few other things I want to list:

• Variable boot sector space: The FAT file system allows a boot sector code block to use as much disk space as needed (though not all implementations account for this). The Linux Ext 2/3/4 file systems do not. Two blocks. Period. Ouch. Give a variable spaced boot sector allowing a single block or <exaggeration> half the drive if needed</exaggeration>.
• Store the last state of the volume in the super block (header). For example, was the volume previously successfully dismounted? If not, don't try to mount it without first trying to fix it.
• Use magic numbers. i.e.: Give specific, static, values to certain structures of the file system. For example, if the primary super block is ever lost, you can search the disk somewhere in the range of ((block size / 2) - 16) -> ((block size / 2) + 16) for a block that contains certain "magic" numbers to see if there is a valid back up super block. This also allows your driver to verify that you actually loaded a valid Inode before modifying the data it may or may not point to.

Extra boot sector space can be added in BMFS by offsetting all the read and write calls by

Code: Select all

+= offset

. I don't want to add extra space in the layout specification, and I might even take away the 512-byte offset, because it can be set by the caller.

Thanks for all the feedback! You've given me a lot to check off before the next release. I'm looking forward to your feedback when I can make the next BMFS post.