--------------------------------------------------
i3fs specifications / vulture a.k.a. Sean Stanek
--------------------------------------------------
This is a 64-bit filesystem. This basically means that all values will
generally be referred to as 64-bit integers and such. Most of this
filesystem uses 64-bit raw numbers for offsets onto disk instead of
using the general sector/cluster/block concepts that most filesystems
rely on. There may be some holes in this because I just thought up
this 3rd generation of the IFS (Imagine filesystem) about 11 hours ago,
and I haven't had time to go through and debug whatever is needed.
For this first release, *PLEASE* go through and find errors and tell
me what needs to be added so we can have a perfect filesystem. I'm
sure I've missed something! :)
- vulture a.k.a. Sean Stanek < vulture@cs.iastate.edu >
- Modified by LTH
- Modified again by vulture :)
-------------
i3fs header
-------------
This goes at the start of the partition. :)
----------+----------+-------------------------------------------------------
Offset | Size | Description
----------+----------+-------------------------------------------------------
0x0000 | 64-bit | Absolute location on disk
----------+----------+-------------------------------------------------------
0x0008 | 64-bit | Filesystem size (including i3fs header)
----------+----------+-------------------------------------------------------
0x0010 | 64-bit | Global entry hash table offset
----------+----------+-------------------------------------------------------
0x0018 | 64-bit | Global entry hash table length
----------+----------+-------------------------------------------------------
0x0020 | 64-bit | First pool allocator entry offset
----------+----------+-------------------------------------------------------
0x0028 | 64-bit | Last pool allocator entry offset
----------+----------+-------------------------------------------------------
0x0030 | 64-bit | Root entry table offset
----------+----------+-------------------------------------------------------
0x0038 | 64-bit | Free space left
----------+----------+-------------------------------------------------------
[LTH]
The Pool entry table length is not needed for my idea. Read the info on the
Pool Table. I do not know why we need to know the length of the root entry.
The free space number is used to tell if there is room to save a file before
we start using free space and find out there is no more room left on the drive
(at which point we would have fun reversing the file save). The Last pool
entry is used to add free space to the chain without searching to the end of
the pool tables to find the end.
-------------------------
Global Entry Hash Table
-------------------------
This is an array of various pointers and such, so that if you want to
open a file you don't even have to search the whole directory structure
or anything. The hash function isn't necessarily determined, but a good
one should obviously be used, and the same one should be used when using
this hash table too. :) The size of this table can be dynamic, so if
opening files or such is taking long because of lots of hash collisions,
we can merely expand the size of the hash table.
----------+----------+-------------------------------------------------------
Offset | Size | Description
----------+----------+-------------------------------------------------------
0x0000 | 64-bit | Realhash - this will be the 64-bit hash value
| | returned by the actual hash function. This is
| | mainly here for easy expansion of the hash table.
| | Note that this hash entry should be in position
| | (Realhash MOD Global_Entry_Hash_Table_Size) in this
| | hash array.
----------+----------+-------------------------------------------------------
0x0008 | 64-bit | Offset to first matching file entry.
----------+----------+-------------------------------------------------------
----------------------
File Entry Structure
----------------------
----------+----------+-------------------------------------------------------
Offset | Size | Description
----------+----------+-------------------------------------------------------
0x0000 | 128-bit | File locator string :
| | 'i3fs-vul',FAh,89h,18h,79h,79h,91h,DFh,ABh
| | This is used for data recovery - should something
| | die, the whole hard drive can be scanned for this
| | hopefully uncommon string, and then we can recover
| | files. This idea inspired by a certain operating
| | system overwriting both copies of my FAT and me
| | having to do a similar process, but with less luck.
----------+----------+-------------------------------------------------------
0x0010 | 64-bit | Realhash - this will be the 64-bit hash value
| | returned by the actual hash function. This is so
| | you don't have to compare against the whole file
| | name, yet. :)
----------+----------+-------------------------------------------------------
0x0018 | 64-bit | Offset to next matching file entry. (for hash)
----------+----------+-------------------------------------------------------
0x0020 | 128-bit | File attributes (these are the official attributes)
----------+----------+-------------------------------------------------------
0x0030 | 128-bit | Reserved for expansion
----------+----------+-------------------------------------------------------
0x0040 | 64-bit | Allocated length for file name
----------+----------+-------------------------------------------------------
0x0048 | n BYTE | Full path and file name, 00h padded up to allocated
| | length. i.e. '/kernel/source/v2os/i3fs.inc',0,0,0
----------+----------+-------------------------------------------------------
------ | ------ | <<< File fragment follows >>>
----------+----------+-------------------------------------------------------
[vulture]
I added file attributes here, so if we recover the file or only have this
file as an offset, we can still read the attributes. This file attributes
should be the *official* file attributes ... the reason we have it also in
the directory entry structure is so that we can easily do a 'dir' command
and we don't need to read a new sector for EVERY file to print out the
file attributes. I also changed back the file name so that we can set a
number of bytes ... even if we still choose to allocate these on every 64
bytes or whatever.
-------------------------
File Fragment Structure
-------------------------
----------+----------+-------------------------------------------------------
Offset | Size | Description
----------+----------+-------------------------------------------------------
0x0000 | 64-bit | Fragment allocated length
----------+----------+-------------------------------------------------------
0x0008 | 64-bit | Fragment active length (actual data)
----------+----------+-------------------------------------------------------
0x0010 | 64-bit | Next fragment offset
----------+----------+-------------------------------------------------------
0x0018 | 64-bit | Reserved for expansion
----------+----------+-------------------------------------------------------
0x0020 | ------ | <<< Raw file data follows >>>
----------+----------+-------------------------------------------------------
------------------------
Directory Entry Format
------------------------
This is an *array* of file entries, sort of like DOS has, with a little
more info.
----------+----------+-------------------------------------------------------
Offset | Size | Description
----------+----------+-------------------------------------------------------
0x0000 | 64-bit | Realhash - this will be the 64-bit hash value
| | of the following filename.
----------+----------+-------------------------------------------------------
0x0008 | 64-bit | Date & Time stamp (created)
----------+----------+-------------------------------------------------------
0x0010 | 64-bit | Date & Time stamp (modified)
----------+----------+-------------------------------------------------------
0x0018 | 64-bit | Date & Time stamp (accessed)
----------+----------+-------------------------------------------------------
0x0020 | 64-bit | Offset of file
----------+----------+-------------------------------------------------------
0x0028 | 64-bit | Total file length in bytes
----------+----------+-------------------------------------------------------
0x0030 | 128-bit | File attributes (unofficial - just for quick reading)
----------+----------+-------------------------------------------------------
0x0040 | 128-bit | Reserved for expansion
----------+----------+-------------------------------------------------------
0x0050 | 64-bit | Allocated length for file name
----------+----------+-------------------------------------------------------
0x0058 | n BYTE | Full path and file name, 00h padded up to allocated
| | length. i.e. '/kernel/source/v2os/i3fs.inc',0,0,0
----------+----------+-------------------------------------------------------
[LTH]
The original entries here called for the Date to have a 64bit number and the
time to have a 64 bit number. Both of which are not needed as you can combine
them into 1 number. Besides, the time can't get past 23:59:59.999. For the
length of the filename. 8 bytes to tell the length is alot. Also, it might be
better to do the size in incremements of say 32 or 64 bytes to pad to. If you
need a longer name after this has been "set" in the entry and you can not
expand it another 32/64 bytes (Which ever is picked, 128 seems like alot) then
create this directory entry somewhere else on the drive with room to expand
it. You would not need to move the files but just this 1 entry that tells
where the file is. I have done the same for the File Entry structure. It
appears that it might be possible to combine these 2 structures into 1 to link
instead of having 2 separate structures with "duplicate" type entries (these
entries being a hash, date/time stamps, attributes, path). The Directory
entry structure currently doesn't have a pointer to the next directory in the
list nor a pointer to the beginning file in it's directory (reasons?). Then
again (after thinking from typing this) it might be better to keep the entries
apart and just add in 2 offsets for the directory entry. 1 to point to the
next directory entry in the list and the other to point to the 1st file in the
list. The File Entry structure needs dates, times, and file attributes.
[vulture]
Added back a few things - the file length I really think we need.
I also added file offset and file size which I totally forgot about,
but I *did* leave blank entries where I forgot to put them. :)
----------------------
Pool Allocator Entry
----------------------
----------+----------+-------------------------------------------------------
Offset | Size | Description
----------+----------+-------------------------------------------------------
0x0000 | 64-bit | Length of free space
----------+----------+-------------------------------------------------------
0x0008 | 64-bit | Offset of next Pool Table (00 = end of list)
----------+----------+-------------------------------------------------------
[LTH]
Each pool table will point to the next one that is known. As space is freed
up you change the last entry to point to the pool table you just created. The
offset is from the beginning of the partition and not from where the pool
table sits. As you need to save a file walk down the pool table links and just
put the file in as you hit a free space (so you don't walk to the end and find
that you need to split the file up. The last pool table in the chain will have
the Offset to the next table 0x0000 and it's offset will be put in the
partition entry for fast access to the end to add more free space. Each pool
table sits where the free space is and tells how much is there (plus the size
of the pool table as it will be overwritten as it is used).
Because of how often the partition entry is read for data entries for the
beginning and end of the pool table should be read once and stored in mem
then written to the drive as they are used/created (with only 1 change, not
5 from using up 5 pool tables. Write it after the file is completely saved
or deleted).
[vulture]
Well, there was some confusing on this one. I'm going with LTH on this one,
even though my idea might work, this would be a lot easier too. The word
"table" should no longer be used though. Essentially what we want is like
how DOS stores its MCB's. Basically what we are doing is showing how much
space is free, and where the next free space is. If we delete a file, we
will need to add a free space pointer. Perhaps it would be much easier to
just add on the new free space to the end of all the free space allocators.
We can just intelligently combine them all when we defrag. Well, when we
defrag, we will really be forcing about one single allocator. :)