OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Nov 23, 2017 9:46 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 21 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: The Simple File System
PostPosted: Fri Sep 08, 2017 5:45 pm 
Offline
Member
Member
User avatar

Joined: Sat Nov 22, 2014 6:33 pm
Posts: 284
Location: USA
Over in a different post, Schol-R-LEA posted:

Quote:
I would like to point you towards SFS, ...(found here and here)

As some of you might know, I am quite fond of file systems, so like the cat, I had to let curiosity get the better of me.

(Please note that the following comments are simply just comments. I am not commending nor criticizing it in any way.)

From my brief study, this looks to be, in general, a one-time write file system. i.e.: You already have the files on a host media system, then wish to transport them to a different media system via this file system, and not much more. Most likely the idea of the author, and it should be.

I do have a few questions, though not really expecting an answer.

It doesn't really explain the use of directories. As far as I can tell, when a Directory Entry is found in the Index area, all File Entries that follow are to be within that named directory until another Directory Entry is found. i.e.: only the Index table knows of directories. This seems to be a good practice, for this file system, until a Deleted Directory Entry is found.

Now, again, since this file system seems to be a one-time write file system, a Deleted Directory Entry is not very likely. However, what does happen if one is found? Are all following Entries assumed to be deleted until the next non-deleted Directory Entry?

Also, if I store, for example, 10 files within the root directory (no Directory Entry has been found yet), then store a Directory Entry with a number of Entries within it, how do I get back to the root? Simply a new Directory Entry of '\' or '/' which ever is used, then any entry that follows is to be in the root until another Directory Entry is found? Or is it assumed that you will never need to be back to the root, since it is considered a one-time write and you should have already written everything to the root.

Anyway, my curiosity got me and I had to study it a little. As a one-time write file system, it does seem to be quite simple and elegant. It could be used quite easily for transporting files from one host to another. I think though, and again I am not criticizing in any way, that once it is used for anything other than a one-time write file system, problems would start to arise. However, I think that it was meant to be a one-time write file system, so these problems are not to be expected.

Thank you Brendan for the interesting read. If anyone, including yourself, wish to reply, I would be interested in reading a little more. For example, I didn't find anything on those two pages that would differentiate the file system between versions 1.0 and 2.0, if it exists, as was mentioned elsewhere.

Thanks,
Ben


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sat Sep 09, 2017 12:48 am 
Offline
Member
Member

Joined: Fri Aug 19, 2016 10:28 pm
Posts: 199
Both the file and the directory entries in the index area keep full paths, so there appears to be no assumption of adjacency between them. The hierarchical connection is expressed in the paths. In such case, they can be stored in any order and at any distance. There are "deleted" entries for both directories and files, so again, I think, no connection implicitly exists between the state of a file and the state of a directory, except the usual integrity of the path components before the last.

Regarding current directory movement and lookup in general, the index area appears to be a database dump of sorts and is apparently expected to be appropriately indexed in memory - with graph or tree or whatever the OS chooses. The file hierarchy in the index area does not facilitate easy lookup by itself or easy transitions between locations, so this is supposed to be done in memory entirely, or so it seems.

For me, SFS resembles somewhat a disk image/file archive, or something like multisession ISO 13490. It has however the ability to add and remove individual files up to a point, to grow files when the storage was preallocated. After sufficiently many manipulations, the media will have to be defragmented.

Edit: Of course, the author can best explain the intended usage, but those are a few things that are more or less in the spec.


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sat Sep 09, 2017 4:03 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8151
Location: At his keyboard!
Hi,

BenLunt wrote:
From my brief study, this looks to be, in general, a one-time write file system. i.e.: You already have the files on a host media system, then wish to transport them to a different media system via this file system, and not much more. Most likely the idea of the author, and it should be.


It's not quite "one time write" (although that's one of the main use cases). In general; when the file system is mounted software would scan the index area and (in conjunction with the super-block) figure out which blocks are in use and which are free from that (e.g. initialise its own internal "1 used/free bit per block" bitmap); and possibly also cache some or all of the index area. Once that's done it's easy to add new files to an existing file system; delete files/directories and reduce a file's size.

The lack of (file data) fragmentation means that it's not easy/cheap to append data to the end of a file - unless you're very lucky you'd have to make space (either by treating it like "creating new file then delete old file", or by moving other files out of the way).

For (free space) de-fragmentation you'd do "compaction" (shift data to lower or higher block numbers to eliminate gaps) for both file data and the index area. This isn't nice either (for performance you'd want to cache at least parts of the index area in memory); and it might be better to just copy all files elsewhere (e.g. a "/tmp" directory on the OS's native file system), wipe everything (fill index area with "unused entries"), then copy all the files back.

BenLunt wrote:
It doesn't really explain the use of directories. As far as I can tell, when a Directory Entry is found in the Index area, all File Entries that follow are to be within that named directory until another Directory Entry is found. i.e.: only the Index table knows of directories. This seems to be a good practice, for this file system, until a Deleted Directory Entry is found.

Now, again, since this file system seems to be a one-time write file system, a Deleted Directory Entry is not very likely. However, what does happen if one is found? Are all following Entries assumed to be deleted until the next non-deleted Directory Entry?


I'd assume that you'd normally delete all the files within a directory before deleting the directory. If a (non-deleted) file exists within a deleted directory or there is no directory entry at all; then the file system is "corrupt" and you'd recover by making an assumption - either assume the directory shouldn't be marked as deleted or should exist and fix/create the directory's index area entry; or assume the files should be deleted or shouldn't exist and remove them. I'd probably do the former (unless you can ask the user what they want done).

Note: The earliest draft didn't have directory entries - directories were simply assumed to exist where necessary (e.g. an entry for the file "/foo/bar/baz.txt" implies that the directory "foo" exists and that the directory "foo/bar" exists). I can't remember exactly why they were added (so you can have empty directories and/or timestamps for directories?).

BenLunt wrote:
Also, if I store, for example, 10 files within the root directory (no Directory Entry has been found yet), then store a Directory Entry with a number of Entries within it, how do I get back to the root? Simply a new Directory Entry of '\' or '/' which ever is used, then any entry that follows is to be in the root until another Directory Entry is found? Or is it assumed that you will never need to be back to the root, since it is considered a one-time write and you should have already written everything to the root.


Given the string "foo/bar/baz.txt"; delete characters from the end of the string until you delete a path separator character or there's no characters left. The first time you do this you'll get the string "foo/bar" (the parent directory's name). Do it again and you get "foo" (the grandparent's name); and do it some more and you get an empty string (the root directory's name).

Once you've obtained a directory name string; to find the corresponding entry (in the index area) you'd search the index area (if you didn't cache some or all of it or build a hash table or something when you mounted the file system).

BenLunt wrote:
Anyway, my curiosity got me and I had to study it a little. As a one-time write file system, it does seem to be quite simple and elegant. It could be used quite easily for transporting files from one host to another. I think though, and again I am not criticizing in any way, that once it is used for anything other than a one-time write file system, problems would start to arise. However, I think that it was meant to be a one-time write file system, so these problems are not to be expected.


Yes - it was mostly intended for transferring files between computers (on relatively small devices - e.g. floppies and small USB flash devices), where the normal use case is "format/wipe, copy/create files, move it to a different computer, read files"; which is why there's no file permissions (they don't make sense for this use case), no fault tolerance (just create a new copy from wherever files originally came from if something went wrong), no file data fragmentation (not worth worrying about), etc.


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.


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sat Sep 09, 2017 3:18 pm 
Offline
Member
Member
User avatar

Joined: Sat Nov 22, 2014 6:33 pm
Posts: 284
Location: USA
I missed the part where all of the path, the full path was within the index itself. I was thinking that only the filename was in the indexed file entry and you used directory entries to indicate which directory it was in. I was thinking that a file entry was associated with the directory entry before it and all file entries up to the next directory entry were the same.

With this in mind, it is quite simple to place a file into a directory simply by placing the full path (minus the drive indicator) in the file entry. Simplifies it quite a bit from what I was thinking.

The only thing I would modify, though it is probably too late now, is move the super block so that the 6-byte (un)official signature could be placed before the partition entries.

Anyway, thanks again for the clarity guys.

Ben


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Wed Sep 13, 2017 9:09 pm 
Offline
Member
Member
User avatar

Joined: Sat Nov 22, 2014 6:33 pm
Posts: 284
Location: USA
Okay, curiosity got me again. (How many lives do I have left?) Anyway, I had some questions and concerns, so I added to your file system specification, Brendan. I hope you don't mind.

Have a look at http://www.fysnet.net/blog/2017/09/ or the direct .PDF file at http://www.fysnet.net/blog/files/sfs.pdf.

Some of the questions I had where:
Quote:
The ending block number must be higher than the starting block number, unless the entry does not use any blocks in the data area (a zero length file) in which case the starting and ending block numbers should both be zero.

What if the file length is equal to or less than the size of a block? The Ending Block number would then equal the Starting Block number, yes? Also, if these two entries are relative to the Data Block, than marking them both as zero would indicate that the first block is used for this entry. This kind of makes me think you have these entries relative to the start of the media where a value of zero is outside the data block. You don't specifically state that the Starting Block and Ending Block numbers are relative to LBA 0 or relative to the Data Block. My additions state that it is the latter.

Now, I did add a few modifications that break the version you have. For example, I added a CRC field, mostly for use with "Deleted" entries. For example, if the host decides to delete a File entry that has continuation entries, and then later reassign those entries to something else, the crc is to make sure the "undelete" operation will have a valid set of entries. Yes, I know, if it is a deleted entry, it is marked as so, but what is stopping a host driver/device from using those "deleted" entries?

I also moved the Super Block 6 bytes leaving room for the commonly used signature that is placed just before the partition entries.

Anyway, I enjoyed studying this file system, and implementing it. I have bootable code, bootable loader, and (mostly) complete kernel driver for this file system. I lack a few things, but all in good time.

Thanks, and any comments, suggestions, and/or changes would be appreciated.

Ben

P.S. I have some (I hope) portable C source code that will create SFS images and copy files to it given a list of path and file names. Once I have a static specification, I will release this code too.


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sun Sep 17, 2017 9:33 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 870
Location: Finland
I have two comments, technical and non-technical. The documents says that there are "minor" additions in the documentation but some of those could (I have not studied the history of it) be very fundamental.

sfs.pdf wrote:
Note that this usually goes against the common organization of file systems and has a file system dependent structure outside of the volume it resides on. However, simplicity is the key with the SFS, and having the Super Block in LSN 0 simplifies it greatly.


When applied this to MBRs and partition tables, I don't quite agree with the simplicity clause. If this really was the idea of the original design, everyone should ignore my comments on this. The main issue for me is the tight coupling of an MBR, partition table and the actual partition. I think this is totally different to a case where an SFS partition, whether a partition (e.g. hard disk) or occupying the whole storage media (e.g. floppy), have a FAT file system (e.g.) alongside of the SFS. In these cases the SFS partition is still "a blob" that has a start and length.

sfs.pdf wrote:
This document and the implementation of this file system may not be used commercially unless you obtain prior written consent from the author listed above.


This is legal (accorsing to the original license?). However, as far as an implementation is concerned (not the document), the whole idea of this restriction deserves a negative feedback. Please note that this is just an opinion.

"The primary purpose of the Simple File System is to facilitate the free exchange of data on physical media without unnecessary restrictions or complexity."

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sun Sep 17, 2017 10:01 am 
Offline
Member
Member
User avatar

Joined: Sat Nov 22, 2014 6:33 pm
Posts: 284
Location: USA
Antti wrote:
I have two comments, technical and non-technical. The documents says that there are "minor" additions in the documentation but some of those could (I have not studied the history of it) be very fundamental.

sfs.pdf wrote:
Note that this usually goes against the common organization of file systems and has a file system dependent structure outside of the volume it resides on. However, simplicity is the key with the SFS, and having the Super Block in LSN 0 simplifies it greatly.

When applied this to MBRs and partition tables, I don't quite agree with the simplicity clause. If this really was the idea of the original design, everyone should ignore my comments on this. The main issue for me is the tight coupling of an MBR, partition table and the actual partition. I think this is totally different to a case where an SFS partition, whether a partition (e.g. hard disk) or occupying the whole storage media (e.g. floppy), have a FAT file system (e.g.) alongside of the SFS. In these cases the SFS partition is still "a blob" that has a start and length.

Personally, I don't agree with the idea of having the Super Block at LSN 0, part of the MBR. In my opinion, if there is a MBR, or a GPT, or any other partitioning technique used, a file system should not be a part of it. The partitioning technique points to a portion of the media that will contain a file system and that file system should not be anywhere outside of that portion, period, though this is just my opinion. As for the SFS using the first sector for the Super Block, that is what the original author chose.

However, it does make the file system a little easier to use. You know that the Super block is at LBA 0. With a partitioning system, your driver must calculate, or be passed a base address to the start of the partition. Some partitioning techniques and file systems have no way of sending this base address. However, this really only is a problem when you are booting the partition. If you are not booting the partition, the kernel's file system control should know exactly where every partition starts.

Antti wrote:
sfs.pdf wrote:
This document and the implementation of this file system may not be used commercially unless you obtain prior written consent from the author listed above.

This is legal (accorsing to the original license?). However, as far as an implementation is concerned (not the document), the whole idea of this restriction deserves a negative feedback. Please note that this is just an opinion.

"The primary purpose of the Simple File System is to facilitate the free exchange of data on physical media without unnecessary restrictions or complexity."

I agree and disagree here. On one side, this should be freely available for anyone to use. I totally agree here. However, on the other side, we are an economic dependent world and if a company wishes to use this file system, commercially, the original author deserves compensation.

Ben


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sun Sep 17, 2017 10:43 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 870
Location: Finland
(My previous post was full of typos ("lexical") and I did not explain my points ("semantic") very well.) :D

I don't understand why MBR and partition tables are relevant with respect to SFS. Having a file system dependent structure in the first sector of the partition should be widely accepted convention. The compatibility with older systems could be implemented so that an SFS-aware system sees an SFS file system and others see, for example, a FAT file system that could be much smaller than the partition. Please note that floppies and floppy-like USB storage media have one partition (the whole media) and this makes the whole discussion a bit confusing.

In other words, the SFS file system could be just a linear array of blocks and it depends on the reader how to interpret it. The compatibility feature could make it look like some other file system. The partition table and MBR should not be relevant.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sun Sep 17, 2017 11:03 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8151
Location: At his keyboard!
Hi,

BenLunt wrote:
Okay, curiosity got me again. (How many lives do I have left?) Anyway, I had some questions and concerns, so I added to your file system specification, Brendan. I hope you don't mind.

Have a look at http://www.fysnet.net/blog/2017/09/ or the direct .PDF file at http://www.fysnet.net/blog/files/sfs.pdf.

Some of the questions I had where:
Quote:
The ending block number must be higher than the starting block number, unless the entry does not use any blocks in the data area (a zero length file) in which case the starting and ending block numbers should both be zero.

What if the file length is equal to or less than the size of a block? The Ending Block number would then equal the Starting Block number, yes? Also, if these two entries are relative to the Data Block, than marking them both as zero would indicate that the first block is used for this entry. This kind of makes me think you have these entries relative to the start of the media where a value of zero is outside the data block. You don't specifically state that the Starting Block and Ending Block numbers are relative to LBA 0 or relative to the Data Block. My additions state that it is the latter.


I think "ending block number" is the LBA (relative to the start of the volume) of the block after the end of the file; so that you can do "blocks_used = ending - starting"; and so that you can do "if( (ending - starting) << block_size_shift < total_size_in_bytes) { // File system is corrupt (not enough bytes to hold this file's data)".

BenLunt wrote:
Now, I did add a few modifications that break the version you have. For example, I added a CRC field, mostly for use with "Deleted" entries. For example, if the host decides to delete a File entry that has continuation entries, and then later reassign those entries to something else, the crc is to make sure the "undelete" operation will have a valid set of entries. Yes, I know, if it is a deleted entry, it is marked as so, but what is stopping a host driver/device from using those "deleted" entries?


In theory (not necessarily in practice due to potential performance optimisations); when allocating index area entries you'd only ever allocate entries that use the "unused entry" type; and when you free space previously used by a (deleted or not) file or directory you'd change its index entry plus all its continuation entries to the "unused entry" type.

Note that when I designed the file system I tried to make sure that (assuming "single block writes are atomic") for every operation it's possible to do writes in a specific order to ensure that a power failure at the wrong time causes lost space and not file system corruption. Sadly this isn't obvious from the specification (because I was lazy and never added the "Appendix A - Algorithms" part). For freeing index area entries that were previously used by a (deleted or not) file or directory; you'd change its index entry (plus any continuation entries that happen to be in the same block) to the "unused" type, then atomically write that block, then change any remaining "continuation entries" to the "unused" type and write those blocks; such that if a power failure happens at any time the worst case is "orphaned continuation entries" (which is easy to detect and recover during file system check or when mounting).

BenLunt wrote:
I also moved the Super Block 6 bytes leaving room for the commonly used signature that is placed just before the partition entries.


That's potentially a good idea I guess; although I'd rather have a "File system corruption detected (malware may have tampered with this disk)" error message that's triggered when the checksum fails (whenever Windows thinks it owns the entire world and mistakenly writes its signature on something that doesn't belong to it). ;)

Note that on partitioned disks the super-block is never an MBR (the only reason space is reserved for a partition table is to allow an OS to support "hybrid SFS and extended partitions" - e.g. to subdivide a primary partition into "file system + sub-partitions").

Also (in case there's confusion); all block numbers are relative to the start of the volume. For partitioned storage I tend to assume a logical hierarchy, where (e.g.) "/dev/sda" is the whole disk (where "block number 0 within /dev/sda" is the MBR) and "/dev/sda3" is a partition (where block number 0 within /dev/sda3" is the first block in the partition - the file system's superblock). File system code would open (mount) a file (like "/dev/fda" or "/dev/sda3" or "/home/Brendan/raw_disk.img" or ...) without having a clue where that file is or if it's a literal file (loopback device) or a partition or a whole device.


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.


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sun Sep 17, 2017 11:22 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8151
Location: At his keyboard!
Hi,

BenLunt wrote:
Antti wrote:
sfs.pdf wrote:
This document and the implementation of this file system may not be used commercially unless you obtain prior written consent from the author listed above.

This is legal (accorsing to the original license?). However, as far as an implementation is concerned (not the document), the whole idea of this restriction deserves a negative feedback. Please note that this is just an opinion.

"The primary purpose of the Simple File System is to facilitate the free exchange of data on physical media without unnecessary restrictions or complexity."

I agree and disagree here. On one side, this should be freely available for anyone to use. I totally agree here. However, on the other side, we are an economic dependent world and if a company wishes to use this file system, commercially, the original author deserves compensation.


At first glance I thought "the implementation" was "the implementation that the reader of this document implements themselves" and was (mistakenly) horrified that you'd be trying to tell me I can't use a file system that I designed for commercial purposes.

To avoid confusion I'd change the sentence to "This document may not be used commercially unless you obtain prior written consent from the author listed above". The copyright for your source code (what you hopefully actually meant by "the implementation") belongs with your source code and doesn't belong in a specification.


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.


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sun Sep 17, 2017 11:42 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 870
Location: Finland
I feel very confused and it is extremely important to clarify my statement about the license issue. I gave the negative feedback for the "if I read your specification and use your version of the SFS in my implementation, I would not be able to use it commercially."

If the case was your implementation, I would never comment your license choice. I am still not sure what is going on. Who understood correctly? In any case, some clarification is needed.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sun Sep 17, 2017 1:03 pm 
Offline
Member
Member
User avatar

Joined: Sat Nov 22, 2014 6:33 pm
Posts: 284
Location: USA
Brendan wrote:
I think "ending block number" is the LBA (relative to the start of the volume)

After thinking about it and working with it a little, I too agree that it is start of the volume, not Data Block Area relative. However, see my comments below about "start of the volume".
Brendan wrote:
...of the block after the end of the file; so that you can do "blocks_used = ending - starting"; and so that you can do "if( (ending - starting) << block_size_shift < total_size_in_bytes) { // File system is corrupt (not enough bytes to hold this file's data)".

What about: "blocks_used = ending - starting + 1"; and so that you can do "if( (ending - starting + 1) << block_size_shift < total_size_in_bytes) { // File system is corrupt (not enough bytes to hold this file's data)".

Brendan wrote:
In theory (not necessarily in practice due to potential performance optimisations); when allocating index area entries you'd only ever allocate entries that use the "unused entry" type;
Agreed.
Brendan wrote:
...and when you free space previously used by a (deleted or not) file or directory you'd change its index entry plus all its continuation entries to the "unused entry" type.

Note that when I designed the file system I tried to make sure that (assuming "single block writes are atomic") for every operation it's possible to do writes in a specific order to ensure that a power failure at the wrong time causes lost space and not file system corruption. Sadly this isn't obvious from the specification (because I was lazy and never added the "Appendix A - Algorithms" part). For freeing index area entries that were previously used by a (deleted or not) file or directory; you'd change its index entry (plus any continuation entries that happen to be in the same block) to the "unused" type, then atomically write that block, then change any remaining "continuation entries" to the "unused" type and write those blocks; such that if a power failure happens at any time the worst case is "orphaned continuation entries" (which is easy to detect and recover during file system check or when mounting).

Yes, so in theory, the FILE_DELETE and DIR_DELETED type would never be used. Then, with this in mind, undeleting a file or a directory is/was never intended.

Brendan wrote:
BenLunt wrote:
I also moved the Super Block 6 bytes leaving room for the commonly used signature that is placed just before the partition entries.

That's potentially a good idea I guess; although I'd rather have a "File system corruption detected (malware may have tampered with this disk)" error message that's triggered when the checksum fails (whenever Windows thinks it owns the entire world and mistakenly writes its signature on something that doesn't belong to it). ;)

I have ran into that problem numerous times. Got to love Windows...

Brendan wrote:
Note that on partitioned disks the super-block is never an MBR (the only reason space is reserved for a partition table is to allow an OS to support "hybrid SFS and extended partitions" - e.g. to subdivide a primary partition into "file system + sub-partitions").

Also (in case there's confusion); all block numbers are relative to the start of the volume. For partitioned storage I tend to assume a logical hierarchy, where (e.g.) "/dev/sda" is the whole disk (where "block number 0 within /dev/sda" is the MBR) and "/dev/sda3" is a partition (where block number 0 within /dev/sda3" is the first block in the partition - the file system's superblock). File system code would open (mount) a file (like "/dev/fda" or "/dev/sda3" or "/home/Brendan/raw_disk.img" or ...) without having a clue where that file is or if it's a literal file (loopback device) or a partition or a whole device.


This is where I got/am confused a bit. So, can a regular MBR with no SFS Super block exist at LBA 0, then one of its partition entries point to a portion of the disk, where the LSN 0, the first block of this partition then contain an SFS Super block, with reserved space for an unused partition table? Then if so, does the SFS ever see or worry about anything before this LSN 0? Also, must an SFS partition occupy the last part of the media or do you intend that the Vol ID entry occupy the last block of the partition used?

In my opinion, if a partitioning scheme allocates a sequential set of blocks for a file system, that said file system should not occupy, calculate from, or even know anything about any other part of the media it resides on except for the sequential blocks allocated to it by the partitioning scheme used. Is this your intent with SFS? Just asking so that I can clarify my notes.

Ben


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sun Sep 17, 2017 1:10 pm 
Offline
Member
Member
User avatar

Joined: Sat Nov 22, 2014 6:33 pm
Posts: 284
Location: USA
Antti wrote:
I feel very confused and it is extremely important to clarify my statement about the license issue. I gave the negative feedback for the "if I read your specification and use your version of the SFS in my implementation, I would not be able to use it commercially."

If the case was your implementation, I would never comment your license choice. I am still not sure what is going on. Who understood correctly? In any case, some clarification is needed.

My intention, and I have ran in to this many times elsewhere and even commented within this forum once or twice is that I do not want anyone to take my documentation, change it, and then publish it, with out first my consent. (Leaving aside that I did just this with Brendan's, but mine has a statement saying so, his did not).

The reason? I have had people take my code/documentation, modify it (most of the time for the worse) and post/publish it elsewhere. Then when someone reads it and asks me about it, I haven't a clue what they are talking about, because they are reading the said changed code/documentation instead of the original.

If someone asked/states so in the first place, or as I have done, points to the original document, it is much easier to find out what is going on.

So, I don't care what happens with implementation of this file system. If you wish to take it and run, as long as it is okay with Brendan, do it. Just don't take my documentation, change it, and post it as mine, (not saying that you ever would).

Does this clear it up a bit. Hope so.
Ben


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Sun Sep 17, 2017 8:22 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8151
Location: At his keyboard!
Hi,

BenLunt wrote:
Brendan wrote:
...of the block after the end of the file; so that you can do "blocks_used = ending - starting"; and so that you can do "if( (ending - starting) << block_size_shift < total_size_in_bytes) { // File system is corrupt (not enough bytes to hold this file's data)".

What about: "blocks_used = ending - starting + 1"; and so that you can do "if( (ending - starting + 1) << block_size_shift < total_size_in_bytes) { // File system is corrupt (not enough bytes to hold this file's data)".


You could think of the possibilities as "blocks_used = ending - starting + K" where any value of K would work; but "K = 0" allows the addition to be removed, and is more natural (e.g. if someone says "start reading a book at chapter 2 and stop reading when you get to chapter 4" then you don't read chapter 4).

BenLunt wrote:
Brendan wrote:
In theory (not necessarily in practice due to potential performance optimisations); when allocating index area entries you'd only ever allocate entries that use the "unused entry" type;
Agreed.
Brendan wrote:
...and when you free space previously used by a (deleted or not) file or directory you'd change its index entry plus all its continuation entries to the "unused entry" type.

Note that when I designed the file system I tried to make sure that (assuming "single block writes are atomic") for every operation it's possible to do writes in a specific order to ensure that a power failure at the wrong time causes lost space and not file system corruption. Sadly this isn't obvious from the specification (because I was lazy and never added the "Appendix A - Algorithms" part). For freeing index area entries that were previously used by a (deleted or not) file or directory; you'd change its index entry (plus any continuation entries that happen to be in the same block) to the "unused" type, then atomically write that block, then change any remaining "continuation entries" to the "unused" type and write those blocks; such that if a power failure happens at any time the worst case is "orphaned continuation entries" (which is easy to detect and recover during file system check or when mounting).

Yes, so in theory, the FILE_DELETE and DIR_DELETED type would never be used. Then, with this in mind, undeleting a file or a directory is/was never intended.


You're confusing "faux deletion" with "de-allocation of space". The former is usually what happens when the user deletes a file, and it mostly just sets a flag (that can be cleared if you want to "un-delete") and doesn't de-allocate anything. Depending on the OS; the de-allocation of space might happen when the user explicitly says to do it (e.g. "empty recycle bin" on Windows) and/or might happen as part of a garbage collection scheme (e.g. de-allocate space used by the oldest deleted files/directories when more space is needed).

Note that it wasn't always like this - it used to be that "delete" was "delete and de-allocate", but this changed a few decades ago when end users started expecting to be able to un-delete whenever they accidentally deleted.

BenLunt wrote:
Brendan wrote:
Note that on partitioned disks the super-block is never an MBR (the only reason space is reserved for a partition table is to allow an OS to support "hybrid SFS and extended partitions" - e.g. to subdivide a primary partition into "file system + sub-partitions").

Also (in case there's confusion); all block numbers are relative to the start of the volume. For partitioned storage I tend to assume a logical hierarchy, where (e.g.) "/dev/sda" is the whole disk (where "block number 0 within /dev/sda" is the MBR) and "/dev/sda3" is a partition (where block number 0 within /dev/sda3" is the first block in the partition - the file system's superblock). File system code would open (mount) a file (like "/dev/fda" or "/dev/sda3" or "/home/Brendan/raw_disk.img" or ...) without having a clue where that file is or if it's a literal file (loopback device) or a partition or a whole device.


This is where I got/am confused a bit. So, can a regular MBR with no SFS Super block exist at LBA 0, then one of its partition entries point to a portion of the disk, where the LSN 0, the first block of this partition then contain an SFS Super block, with reserved space for an unused partition table?


Yes (and that's the most likely scenario).

BenLunt wrote:
Then if so, does the SFS ever see or worry about anything before this LSN 0?


No, SFS wouldn't see anything outside its volume.

It might help to think of partitioning schemes ("MBR partitioning", GPT, BSD slices, whatever) as file systems. You might have a hard disk that is presented as the file "/dev/sda", and you might mount that file with the "MBR partitions file system", and the "MBR partitions file system" might create 4 files ("/dev/sda1", "/dev/sda2",...). Then you might mount "/dev/sda2" with the same "MBR partitions file system" and get extended partitions ("/dev/sda5" to "/dev/sda7"). Then you might mount "/dev/sda5" with the "FAT file system" and get 1234 files where one of them might be "/foo/bar.zip". Then you might mount "/foo/bar.zip" with the "PK zip file system" and get 333 files where one of them might be "/foo/bar.zip/things/my_disk.img". Then you might mount "/foo/bar.zip/things/my_disk.img" with the "GPT file system" and get 10 more files (corresponding to 10 partitions within the disk image). Then you might mount one of those files with SFS.

All of these cases are essentially the same - they all mount some kind of "parent file" with some kind of file system, they all have their own "logical addresses within the parent file that was mounted", they all expose file names and/or directories in the virtual file system, and they all provide "read/write data to an address/offset within a file" functionality to their clients (whoever opened a file, which could be another file system).

I guess what I'm saying is that SFS can't access anything before "LBA 0 within the file/device it mounted" in the same way that you can't open a file and seek to a negative offset within the file.

BenLunt wrote:
Also, must an SFS partition occupy the last part of the media or do you intend that the Vol ID entry occupy the last block of the partition used?


The original specification is badly worded - everywhere it says "media" it should say "volume" (e.g. for the volume identifier, it should say "The very first entry (just below the end of the volume) in the index area must be a Volume Identifier Entry"). It should probably also have a glossary to define "volume" (as "all blocks within the logical address space provided by whatever the file system mounted").


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.


Top
 Profile  
 
 Post subject: Re: The Simple File System
PostPosted: Mon Sep 18, 2017 1:11 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 870
Location: Finland
BenLunt wrote:
However, on the other side, we are an economic dependent world and if a company wishes to use this file system, commercially, the original author deserves compensation.


This quote (and your position) is a bit unclear, "to use this file system", see below.

BenLunt wrote:
So, I don't care what happens with implementation of this file system. If you wish to take it and run, as long as it is okay with Brendan, do it. Just don't take my documentation, change it, and post it as mine, (not saying that you ever would).

Does this clear it up a bit. Hope so.


Unfortunately these replies did not clear it up. However, the change you made in the documentation is very clear now. Positive feedback. :D

The ambiguous definitions were, and to some extent still are, "use of the file system" and "implementation" and what do they imply. If a company uses the file system, I didn't assume it typically meant that the actual document for describing the format was very relevant. The information and the exact data structures are important. Also, I don't think that "implementation" typically means that someone would write their own version of your document.

What is the scenario in which you would receive compensation from a company? The information and data structure layouts are free, as far as I understood? What is the commercial use of your document, that apparently could be interpreted as "use of this file system"? Do we use the information in it or is someone going to commercially sell your document like a book? Also, whether the use is commercial or not, I thought that changing the document is discouraged anyway (and I fully understand that point). What I don't understand is the special treatment for the "commercial" because of the ambiguity of the "use" and implementation.

I am really sorry about this offtopic but I don't think this is totally irrelevant. I get the impression that the Brendan's original version is somehow more free as far as the information is concerned. But that does not make sense.

_________________
Undefined behavior since 2012


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 21 posts ]  Go to page 1, 2  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group