-------------------------------------------------- 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 :) - Modified again by LTH - Modified again by LTH - Modified again by LTH [LTH] I have attemted to go thru and make sure everything is explained in detail so that there is no confusion on how things work [LTH] There are 2 sectors (1024 bytes) that are left at the beginning of the partition. These sectors have a determined reason but at the moment they are unused. I imagine they will be used shortly though. [LTH] I had to add an entry to the partition header so we can correctly identify it as a valid i3fs partition. I also added in some extra areas at the end for possible expantion if need be. ------------- 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 ----------+----------+------------------------------------------------------- 0x0040 | 64-bit | i3fs marker. Always 0,'-i3fs-',0 ----------+----------+------------------------------------------------------- 0x0048 | 64-bit | Empty (could possibly be used later for a pointer | | to a table with more needed info) ----------+----------+------------------------------------------------------- [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 | Offset to first matching file entry. ----------+----------+------------------------------------------------------- [LTH] The hash table is to be allocated together in 1 area and not split up due to the way it works. You have entry after entry pointing to different files. The place to point to is decided by a hash. The 1st file that hits that entry gets the pointer pointing to it. Then afterwards you have a chain as each file has a pointer in it pointing to the next file that matches that hash. There are pros to this as it allows you to find a file quickly. The main con is this. If you need to resize the hash table (due to the chains getting to long and taking too long to find a file) you HAVE to go thru and change all the hash pointers in all the files. This is due to the different values you get back when the table is expanded. When you want to find a file a hash is made of the file and directory. The value is then divided by the size of the hash table. The remainder is then looked up in the table (example, if the remainder is 5 then the 5th entry is grabbed). We then will jump to that place on the HD and see what file we found, if it is the wrong file we grab the hash pointer in that file and head off to the next 1. This table must be big enough so you do not do alot of jumping around. The hash table should work great. A seperate program should be written up though to do the expansion and rehashing of the files on the drive. A hash function still needs to be written up. I have been asked to write it. I will probably go for a CRC like hash that is 64 bits. ---------------------- 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) ----------+----------+------------------------------------------------------- 0x0028 | 64-bit | ID of the owner of the file ----------+----------+------------------------------------------------------- 0x0030 | 64-bit | ID of the group that can access the file ----------+----------+------------------------------------------------------- 0x0038 | 64-bit | CRC of the file (only used during encryption) ----------+----------+------------------------------------------------------- 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 ----------+----------+------------------------------------------------------- ------ | ------ | <<< 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. [LTH] Here are the flags for the file and directory entries. flag description ------------------ 0 | Dir 1 | Linked 2 | System file 3 | Archive 4 | Compressed (files only) 16 | Encryption Scheme 17 | Encryption Scheme 18 | Encryption Scheme 19 | Encryption Scheme 32 | Owner - Hidden 33 | Owner - Readable 34 | Owner - Writable 35 | Owner - Runnable 40 | Group - Hidden 41 | Group - Readable 42 | Group - Writable 43 | Group - Runnable 48 | Guest - Hidden 49 | Guest - Readable 50 | Guest - Writable 51 | Guest - Runnable [LTH] Most of the flags are optional. The Encryption scheme flags work along the following line. The 4 bits are read. If their value = 0 then the file is not encrypted. Otherwise a module that is called EncryptionX (replace X with the value of the flags) will be used to decrypt/encrypt the file. ------------------------- 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) ----------+----------+------------------------------------------------------- 0x0038 | 64-bit | ID of the owner of the file ----------+----------+------------------------------------------------------- 0x0040 | 64-bit | ID of the group that can access the file ----------+----------+------------------------------------------------------- 0x0048 | 128-bit | Reserved for expansion ----------+----------+------------------------------------------------------- 0x0058 | 64-bit | Allocated length for file name ----------+----------+------------------------------------------------------- 0x0060 | 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. :) [LTH] Lets see if I can describe the last 3 sections and how they relate. There are File Entries (FE) File Fragments (FF), and Dir Entries (DE). The root entry is a DE. The DE has FFs. Inside of these FFs are more DE entries (as a DE entry can be a file or a directory, if it is a directory it has more DE's in it's FFs). When a DE entry is a file it points to a FE. This is so that the hash function has data to read and also to allow the file system to be rebuilt. Of course a FE has FFs that store the raw data of the file. ---------------------- 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. :) [LTH] If you have a keen eye you will notice that bad areas of the HD are not mentioned. Because we use the pool chain to know where we can write to we can effectively "forget" about a part of the HD (a bad area) and never have it in the chain and never have anything point to it. It would just be forgotten about.