-------------------------------------------------- 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. :)