SimpleFS - Missing from WIKI and Brendan's site

Question about which tools to use, bugs, the best way to implement a function, etc should go here. Don't forget to see if your question is answered in the wiki first! When in doubt post here.
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Brendan »

Hi,

From my perspective....

SFS advantages:
  • - no patent problems
    - simple to implement (but allows more complex code for better performance)
    - no data fragmentation (potentially faster reads)
    - handles UTF8 file names of any length
    - no security (good for shifting data between different systems, where file system security may be implemented in completely different ways)
    - no "meta-data" (good for shifting data between different systems, where meta-data may be implemented in completely different ways)
    - not much space/time wasted for fault tolerance (journaling, redundant index areas, etc)
    - can co-exist with other file systems and/or custom boot code
SFS disadvantages:
  • - no data fragmentation (potentially slower writes)
    - no security
    - no "meta-data"
    - not much fault tolerance (no journaling, redundant index areas, etc)
IMHO this makes it one of the best possible file systems for shifting data between different computers (and other devices), but also makes it one of the worst possible file systems for your OS's root partition....

As for full length file names, the idea is that any sector in the index area can become corrupt without preventing the rest from being read easily - "foo/bar/woot.txt" always makes sense, but "woot.txt" with a field pointing to an unreadable directory entry might not.


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.
Habbit

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Habbit »

Brendan wrote: As for full length file names, the idea is that any sector in the index area can become corrupt without preventing the rest from being read easily - "foo/bar/woot.txt" always makes sense, but "woot.txt" with a field pointing to an unreadable directory entry might not.
That is true, but such an scheme (with both directory entries that are not removed when they are not empty and full paths) adds some new problems. For example: what should an SFS implementation do when, after parsing the whole index area, it has found files such as "/System/Drivers/ATAPI.sys" but no entry for the "/System/Drivers/" folder? Should the driver 1) just assume that there is such a folder and create its entry to avoid further confusion; or 2) instead, think that the files cannot be reached anymore? The draft does not specify that, especially since drivers assuming the 2nd approach are likely to cause havon on floppies.

With the parent-directory-link I proposed, the risk of a disk block becoming unreadable (512 bytes / 64 bytes per entry = 8 unreadable index area entries) and "orphaning" a file entry is either the same (if the current draft uses the 2nd approach) or a bit higher (if we are currently using the 1st approach), but it would definitely solve the what-to-do-with-an-orphan-file problem: it is either unreachable and may be deleted - Bad Idea (TM) since floppies fail more than necessary - or it is relocated, with a path as complete as possible, to a "lost&found" special directory in the root.

Example of part of an index area with that feature:

Code: Select all

Entry #39: File "Kernel.sys" - parent directory link #0 (root)
Entry #3A: UNREADABLE
Entry #3B: File "Setup.elf" - parent directory link #3A
Entry #3C: Directory "i386-binaries" - parent directory link #3A
Entry #3D: Directory "amd64-binaries" - parent directory link #3A
Entry #3E: File "system-base.tar.bz2" - parent directory link #3C
Entry #3E: File "system-base.tar.bz2" - parent directory link #3D
One directory entry with many children has become unreadable. The filesystem driver should then make those files available under the folder "lost&found/0000003A" (without actually changing data on disk, just show them under that special folder), and probably issue a warning when mounting. The partial volume tree shown is then:

Code: Select all

/
|--Kernel.sys
|--lost&found/
   |--0000003A
      |--Setup.elf
      |--amd64-binaries/
       |  |--system-base.tar.bz2
      |--i386-binaries/
         |--system-base.tar.bz2
Kemp

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Kemp »

I agree with Brendan on intended purpose, this would be perfect for data transfer where you chuck a load of stuff on a disk, copy it to the other machine and then wipe the disk next time you want to use it. No chance of fragmentation (or lack thereof) becoming an issue in that scenario. Any other purpose that involves a single-write followed by many reads would suit it too, such as a boot disk / a small partition that is used purely to boot from with the actual root being on a different filesystem.

While we're on the topic, I'm probably going to be implementing that myself. A small partition on the hd that contains only enough to boot off of and isn't made available after boot (not assigned a letter or not mounted as is your preference in terms of imagining it). That way programs can trash anything they want on the disk (assuming they don't find a method lower than the filesystem drivers), but the system can still boot.
User avatar
Pype.Clicker
Member
Member
Posts: 5964
Joined: Wed Oct 18, 2006 2:31 am
Location: In a galaxy, far, far away
Contact:

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Pype.Clicker »

well, i've been toying with the SD card of my nintendo DS developer kit, and i should admit i hummed to myself "on this little piece of hardware, having SFS could be fairly handy" ... most stuffs are not edited when on the DS, but only when mounting on the PC ... most stuff except locally-saved data such as sprite tables, etc, which i could easily pre-allocate when mounting.

only the closed firmware that picks the program to be run out of the SD card prevented me to implement SFS there. It would just make my SD card useless.
Habbit

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Habbit »

I'm also thinking about implementing the current SFS draft: I've already started toying with FUSE on Linux. However, I'd recommend all implementors to avoid marking the formatted media with version 1.0 (0x10 in the version field) because the spec could still change. My suggestion is that we employ version 0.9 (0x09) for the current draft, 0.10 (0x0A) for the next, etc. until the final spec is out.
User avatar
Combuster
Member
Member
Posts: 9301
Joined: Wed Oct 18, 2006 3:45 am
Libera.chat IRC: [com]buster
Location: On the balcony, where I can actually keep 1½m distance
Contact:

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Combuster »

In that case, why not just start at 0.1 (or 0.0 but that reads weird...) instead of 0.9. Who knows we get more than 6 release candidates (or updates), although admitted thats not very likely.

In the meantime i'm trying to invent a scheme that'd improve index searches drastically without breaking compatibility with SFS as it stands. And since my os is far from fs-capable at this point, i'll write this sfs driver for hd-images :)
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]
Habbit

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Habbit »

Okay, I support the 0.1 version number for SFS drivers compliant with the January draft. The simplefs-0.1-fuse package will be in your Ubuntu repository before you notice!! ;D
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Brendan »

Hi,
Habbit wrote:That is true, but such an scheme (with both directory entries that are not removed when they are not empty and full paths) adds some new problems. For example: what should an SFS implementation do when, after parsing the whole index area, it has found files such as "/System/Drivers/ATAPI.sys" but no entry for the "/System/Drivers/" folder? Should the driver 1) just assume that there is such a folder and create its entry to avoid further confusion; or 2) instead, think that the files cannot be reached anymore? The draft does not specify that, especially since drivers assuming the 2nd approach are likely to cause havon on floppies.
The original versions of the specification (intentionally) didn't support directory entries at all - this was added later to support empty directories.

The idea would be that entries for directories are never necessary, unless the directory is empty. In this case, if the file "/foo/bar/hello.txt" exists then the directory entries "/foo" and "/foo/bar" can be deleted if they are found to save space. It also means that if the file "/foo/bar/hello.txt" is created the directory entries don't need to be created, and the SFS driver doesn't need to check if directory entries exist before creating any file. Orphaned files are impossible...

The "empty directory" support does complicate things though. For example, if the file "/foo/bar/hello.txt" is deleted then the SFS driver may need to search for "/foo/bar/*" to see if it was the last file in the directory, and search for "/foo/bar" to see if an entry for the directory already exists, and (if necessary) create an entry for the empty directory "/foo/bar".

For the original version of the specification, the SFS driver would behave as if directories didn't exist at all - the file "/foo/bar/hello.txt" was treated exactly the same as the file "-foo-bar-hello.txt", and no searching was necessary to make sure the directory structure remained consistant. For example, retrieving a list of files that begin with "/foo/bar/" would've been the same as retrieving a list of files that begin with "-foo-bar-", and would've returned the "directory contents" of "/foo/bar/". To be honest, I'm still wondering if support for empty directories is more hassle than it's worth, or if there's a better/simpler way to support empty directories.


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.
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Brendan »

Hi,

Today I intend going through everyone's comments on SFS (going right back to the beginning), and adding some things I've missed (mostly tidying up some of the "grey areas") - hopefully in around 12 hours there'll be an updated draft...

At the moment, there's one major thing it lacks - the copyright notice at the beginning ("[TODO - need some legal stuff about public domain and no copyrights here]").

I assumed it would be relatively easy to submit it into the public domain, however some research suggest that "I, the author of this work, hereby release it into the public domain." and similar wordings may not have the desired effect. For e.g. some experts say that at a later time I could assert ownership over it and forbid others to use it, and that it leaves me open to be sued if it causes "harm" (e.g. if a company spends millions in an attempt to support SFS only to find it doesn't work as specified, then they may be able to sue me for development costs). Of course for every expert there's another expert who disagrees, but it doesn't seem like a "fool-proof" solution...

The other thing I'm wondering is whether or not someone like Microsoft could take the specification, make their own patented modifications and call it "SFS version 1.1" (and if there's any way to prevent this).

Any suggestions?


Thanks,

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.
User avatar
Pype.Clicker
Member
Member
Posts: 5964
Joined: Wed Oct 18, 2006 2:31 am
Location: In a galaxy, far, far away
Contact:

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Pype.Clicker »

Brendan wrote: I assumed it would be relatively easy to submit it into the public domain, however some research suggest that "I, the author of this work, hereby release it into the public domain." and similar wordings may not have the desired effect. For e.g. some experts say that at a later time I could assert ownership over it and forbid others to use it, and that it leaves me open to be sued if it causes "harm" (e.g. if a company spends millions in an attempt to support SFS only to find it doesn't work as specified, then they may be able to sue me for development costs). Of course for every expert there's another expert who disagrees, but it doesn't seem like a "fool-proof" solution...
There's the legal notice you can find in e.g. Hale's PD ATA driver.
// ATA LOW LEVEL I/O DRIVER -- ATAIOPCI.C
//
// by Hale Landis ([email protected])
//
// There is no copyright and there are no restrictions on the use
// of this ATA Low Level I/O Driver code. It is distributed to
// help other programmers understand how the ATA device interface
// works and it is distributed without any warranty. Use this
// code at your own risk.
I think it clearly show who's the author, that it is PD. (no restriction, etc) and that you cannot be sued for any side-effect like the universe collapsing or whatever.

And that's fairly typical wording that you find in virtually every open source works/license.

The other thing I'm wondering is whether or not someone like Microsoft could take the specification, make their own patented modifications and call it "SFS version 1.1" (and if there's any way to prevent this).
You cannot patent something that is "obvious to someone being in the domain" or that is "prior art". By releasing it, you clearly make it prior art. There will be the archive.org website to show evidence of the initial release (though officially, a notarial proof would be better, though clearly too expensive).
User avatar
Combuster
Member
Member
Posts: 9301
Joined: Wed Oct 18, 2006 3:45 am
Libera.chat IRC: [com]buster
Location: On the balcony, where I can actually keep 1½m distance
Contact:

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Combuster »

As for the public domain issue, you can issue it under the BSD license (or cut large parts of that) which is dead close to being public domain: everybody can use it at will, everybody can modify it, nobody can sue you. You may want to look for alternative standard licenses for this sort of thing.

As for patents, i doubt that (...) would find something to patent on while keeping the basic idea of SFS: no nonsense. Things like trees, journaling, consistency checks, defragmentation, clean unmount flags and such are in use by all modern fs's and since (...) didnt invent both Reiser4 and NTFS, patenting any of these is close to impossible. As for opensource ideas, i doubt anybody would go with sfs if it were made proprietary by anyone, it'd only result in the conception of OpenSFS or the like.

About the spec itself:
One thing i kindof find missing in the specs is sfs's relation to partitioning (or maybe i'm confused or undereducated about that). Right now its obvious what sector 0 should be like when you have a full-sfs floppy or a hybrid sfs-fat floppy. Now what if i have a partitioned HD and i want sfs to occupy some 200 mb as second partition. Two things: would all pointers become partition-relative or absolute, and what would be a default partition type for sfs-only disks.

Right now i'm kindof concerned with the first since i'm at the point where that matters, as for the second, my code is stupid enough to find a SFS partition if the partition is marked as HPFS/NTFS, but a convention would be welcome (something like the corresponding FAT id for hybrids, Linux id for native)
As for partition-relative addressing, i have no idea what "standard" is, and since my google attempts so far have been unsuccesful, i'd be happy to hear it.

As for directories, directory handling can be a problem
if i.e. somebody renames a directory on an os that doesnt care about directories, empty directories may be left behind.
If i'd for instance try to move my UT directory on os 1, it wouldnt want to run on os 2 because it finds /cache is missing (which is either killed, or left at the original location).
Since empty directories are universally supported i dont think ignoring them would be wise.
As for optimising out dir entries, drivers that dont like that should just add them upon noticing (as part of the mount process), since that could lead to misunderstandings as well: if i'd clear /cache on os 1 then ut would again stop working on os 2 since the /cache has silently disappeared.

</mile post>

p.s. i noticed the previous post mowing away bit of my text. But iirc in some countries you have to explicitly take away the "merchantability and fitness for a particular purpose" in the license text, but some people forget that and i'm not sure to what countries it applies. BSD at least seems to have it
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]
Habbit

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Habbit »

Combuster wrote: Since empty directories are universally supported i dont think ignoring them would be wise.
I daresay I support the motion. Besides: how would you copy anything to an SFS disk? In every OS I know, in you copy a directory tree, with or without files, the OS/file manager/whatever first creates a directory and then copies thing in it... That would be impossible if empty directories are not supported! And even if it were possible (making the mkdir syscall a dummy function), the idea behind SFS is to make it simple, not crippled.
Brendan wrote: The "empty directory" support does complicate things though. For example, if the file "/foo/bar/hello.txt" is deleted then the SFS driver may need to search for "/foo/bar/*" to see if it was the last file in the directory, and search for "/foo/bar" to see if an entry for the directory already exists, and (if necessary) create an entry for the empty directory "/foo/bar".

For the original version of the specification, the SFS driver would behave as if directories didn't exist at all - the file "/foo/bar/hello.txt" was treated exactly the same as the file "-foo-bar-hello.txt", and no searching was necessary to make sure the directory structure remained consistant. {...} To be honest, I'm still wondering if support for empty directories is more hassle than it's worth, or if there's a better/simpler way to support empty directories.
(Luring siren chant) Parent-directory-link... easy... simple...
Pype.Clicker wrote:
Brendan wrote: The other thing I'm wondering is whether or not someone like Microsoft could take the specification, make their own patented modifications and call it "SFS version 1.1" (and if there's any way to prevent this).
You cannot patent something that is "obvious to someone being in the domain" or that is "prior art". By releasing it, you clearly make it prior art. There will be the archive.org website to show evidence of the initial release (though officially, a notarial proof would be better, though clearly too expensive).
While you cannot patent something in the public domain, you can do a slight modification and release it under a propietary license (closed source) arguing that the whole code has changed and forbidding anyone else from implementing anything like the "new features" - which might cripple the implementor's possibilities of creating an open source driver. I think a BSD-like license, or even the LGPL, would be best. And of course, don't forget the "no warranty whatsoever, not even for merchantibility or fitness for a particular purpose" thingy ;)
Combuster wrote: About the spec itself:
One thing i kindof find missing in the specs is sfs's relation to partitioning (or maybe i'm confused or undereducated about that). Right now its obvious what sector 0 should be like when you have a full-sfs floppy or a hybrid sfs-fat floppy. Now what if i have a partitioned HD and i want sfs to occupy some 200 mb as second partition. Two things: would all pointers become partition-relative or absolute, and what would be a default partition type for sfs-only disks.
Well, I haven't even imagined such a problem... I don't know if any of you, people in this thread, think otherwise, but I've always thought that all block numbers, etc, were partition-relative. I mean: in floppies they span the whole disk because floppies have no partitions, but in a SFS hard disk partition, the "superblock" is the first block of the partition, and so on. That is also the easiest way and safest: you just open, for instance, /dev/hda1 and let the disk driver translate your logical partition-relative block numbers into LBA disk-relative sector numbers. And you don't risk eating the MBR/GPT, you allow the partition to be relocated with something like Partition Magic were it needed, etc.
A partition should know only about itself: encapsulation is ignorance of the whereabouts of other partitions, and ignorance is bliss.
Habbit

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Habbit »

Oh, by the way, does anyone know where to find GOOD documentation on FUSE? Its SourceForge page contains a wiki that is, at best, far incomplete.
User avatar
Combuster
Member
Member
Posts: 9301
Joined: Wed Oct 18, 2006 3:45 am
Libera.chat IRC: [com]buster
Location: On the balcony, where I can actually keep 1½m distance
Contact:

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Combuster »

Some minor issues in the spec:

Code: Select all

01 52 46 52 | ? R F R
1: Version is meant to read 'SFS', but 0x524652 reads as RFR instead - probably you meant to type 0x534653 (two occurences, sector 0 table, description of magic value).

2: The spec hints at comparing <S F S version> to 0x53465310, but due to intel byte ordering this number is inverted, and should in the current context be 0x10534653. (if you do want to keep version in the least-significant part, you can put version before the magic marker). (one occurance, description of the magic value)
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]
Habbit

Re:SimpleFS - Missing from WIKI and Brendan's site

Post by Habbit »

@Brendan: Er... I see the spec is changed, but is it finished? I mean, can we start reviewing this "second draft" or are you still making changes?
Post Reply