How to create a new filesystem ?

[OSDesign]

I have read couple of articles about filesystem. I know the basic, we hate to built a fat, a kind of table with filenames and the adress on the hard drive.

I searched on google but I just can't find anything specific about questions I ask me

But Im a little lost about how to create it.

1) Sectors of hdd are always 512 bytes ? or if this is determined by the format ? If not, a hdd total space is calculated like that: 512XNumber of sector per cylinder X number of cylinder X number of head X Number of face per cylinder ?

I know the bios int can allow to write into a specific sector, head and cylinder, but can we write on a specific area on the sector ? Or if we always have to write at the beginning of a sector ? In that case we loosing space, right ?

In the bios int 13h we can read a specfic number of sector, on a head and a cylinder, but in my FAT I have to write something like: fileXYZ.EXT and his adress: one byte for the sector, one byte for the head and one for the cylinder ?

How can I read/write file on the disk with a specific on the hard drive ?

And finally, where I have to store my fat, or my filesystem structure table ? on sector 1 ? (0 is used by the bootstrap)

The table can grow because we delete, creating files, how many space I should reserve for the FAT ?

As example, where is stored the FAT32 of Windows 98/2000/XP ?

I need some direct informations like that to know how to create my filesystem

Thank you.

[AR]

Creating a filesystem may not be the best idea for the simple reason that you will have to create your own tools for your development operating system to understand the disk images, and the finished disk images won't work on computers that aren't running your OS.

Anyway, the physical sector size is 512bytes, it is theoretically possible for this to change (There are "sector size" fields in the BIOS data tables indicating the size could be changed). The size is simply the total number of Linear Blocks if LBA is available, otherwise it's Heads*Cylinders*Sectors.

Where you put everything is completely up to you, just like writing a kernel where you have control of the whole memory space, writing a file system gives you control of the whole partition (except the bootsector, that can't be moved).

You do not need a "FAT", FAT-Chains are inefficent and are easy to damage so that you "loose" the file from that point onwards, a better idea is extents. (File starts at X, runs for X sectors, Second chunk of file starts a Y, runs for Y sectors, etc). The on-disk storage of this is up to you, ultimately the best filesystems are fast, protect themselves from data loss and damage and are secure.

[Brendan]

Hi,

1) Sectors of hdd are always 512 bytes ? or if this is determined by the format ? If not, a hdd total space is calculated like that: 512XNumber of sector per cylinder X number of cylinder X number of head X Number of face per cylinder ?

Hard drives on 80x86 PCs always use 512 byte sectors (AFAIK), but are you writing a file system that will only work on a hard drive?

Floppy disks can be formatted for different sector sizes (ranging from 128 bytes to 16 KB), CD-ROMs typically use 2 KB sectors and other devices (flash memory drives, ZIP drives, etc) could have other sector sizes. Even then it might be a good idea (depending on OS design and FS design) to only deal with groups of sectors that are 4 KB or larger because of the paging system.

I know the bios int can allow to write into a specific sector, head and cylinder, but can we write on a specific area on the sector ? Or if we always have to write at the beginning of a sector ? In that case we loosing space, right ?

The hardware itself is only capable of reading and writing whole sectors, so you can't write N bytes in the middle of a sector (for example). It is possible to hide this within the device driver though - if the file system wants to write 3 bytes at offset 0x0123 it can ask the device driver to do it, and the device driver could read the whole sector, change the 3 bytes and then write the whole sector. This way the file system code itself never needs to care what the actual size of a sector is (and it doesn't hurt performance much once you've got caching).

In the bios int 13h we can read a specfic number of sector, on a head and a cylinder, but in my FAT I have to write something like: fileXYZ.EXT and his adress: one byte for the sector, one byte for the head and one for the cylinder ?

If you can use the BIOS (ie. you're not in protected mode) then use a "wrapper" or dummy device driver. You're device driver should ignore the CHS (Cylinder/Head/Sector) and work with "logical addresses" only (converting logical addresses to the final CHS at the last possible moment, if necessary).

And finally, where I have to store my fat, or my filesystem structure table ? on sector 1 ? (0 is used by the bootstrap)

DOS put's the FAT at the start of the disk, but better file systems try to put it where the data is to minimize (slow) disk head movement for common disk operations - e.g. scattered throughout the disk.

[continued next post]

[Brendan]

[continued from last post]

The table can grow because we delete, creating files, how many space I should reserve for the FAT ?

What does your FAT contain?

For DOS the "FAT" contains a value for each cluster (or groups of sectors), and should probably be called a "CAT" (Cluster Allocation Table) because it doesn't store files at all. Because there are a fixed number of clusters (or a fixed number of sectors) the FAT is always the same size, and never grows or shrinks. Each value in the FAT represents the next cluster number in a chain of clusters, or a special value (cluster is free/unused, cluster is bad/unreliable/faulty, etc).

As example, where is stored the FAT32 of Windows 98/2000/XP ?

Windows 98 uses DOS FAT (described above). For WIndows XP (or WIndows NT) Microsoft finally dumped the crappy old DOS file system and switched to NTFS. AFAIK NTFS doesn't use a FAT like DOS did.

I need some direct informations like that to know how to create my filesystem

I'm sorry to say, this is quite apparent. First decide if you're designing a file system, or if you're implementing a file system. If you're implementing one then all you'd need to do is follow a pre-existing design.

If you're actually designing a file system, then you should first do some research into how existing file systems work (and what's wrong with them, and what features you'd like to add). Suggested reading includes (in order?):

http://www.ntfs.com/fat-systems.htm - DOS/FAT file system
http://www.osdever.net/documents/fatgen103.pdf - DOS/FAT specification

http://www.ntfs.com/ntfs_basics.htm - NTFS file system

http://www.nobius.org/~dbg/practical-fi ... design.pdf - general (Be file system)

http://www.osdever.net/documents/Ext2fs ... ew-0.1.pdf - ext2 overview
http://e2fsprogs.sourceforge.net/ext2intro.html - ext2 file system
http://www.osdever.net/documents/journal-design.pdf - ext2 journalling

http://www.p-nand-q.com/download/rfstoo ... _docs.html - ReiserFS


Cheers,

Brendan

[OSDesign]

Thank you for those great informations

I design my own filesystem.

If I understand right, I have to design something work with "clusters" ?

If I want to write something somewhere on a sector, I have to read all the sector, modify it and rewrite all the sector ?

But if I am in protected mode, I have to write my own driver ?
I know, writing a driver for video card, as example, its very hard because supporting 3d and other functions of the card is not easy. And all manufacturer are not release specs of almost video card. But about hdd, there is no special functions about them ? I mean a hdd its a hdd, so it is possible to write a driver that will support all kind of hdd IDE or SATA ?

[Brendan]

Hi,

If I understand right, I have to design something work with "clusters" ?

Not necessarily - DOS FAT uses clusters but ext2 works with sectors and my OS will work with bytes.

If I want to write something somewhere on a sector, I have to read all the sector, modify it and rewrite all the sector ?

Yes, that's why my OS will use bytes rather than clusters or sectors. The actual "read sector, modify, write sector" part will be done inside the device driver, so my file system code can use 64 bit logical addresses and ignore the sector size completely.

Most OS's (and file systems) use sectors or clusters though...

But if I am in protected mode, I have to write my own driver ?
I know, writing a driver for video card, as example, its very hard because supporting 3d and other functions of the card is not easy. And all manufacturer are not release specs of almost video card. But about hdd, there is no special functions about them ? I mean a hdd its a hdd, so it is possible to write a driver that will support all kind of hdd IDE or SATA ?

You'll need to write your own device drivers sooner or later, but if your OS can use the BIOS code (switching back to real mode or a virtual 8086 monitor) you could get away with a wrapper for now. It's probably better to write the device drivers instead though (the BIOS was never designed for modern multi-tasking OSs, and ugly hacks tend to multiply).

The good news is that it's not too hard and there's plenty of documentation on the internet. SATA (and PCI PATA controllers) use a "legacy" mode by default so you won't need to care about bus mastering, UDMA, etc.


Cheers,

Brendan

[OSDesign]

Thanks

I see specs of filesystems supporting journal, its a kind of log, showing what job this file receive.

But this kind of filesystem is not oversized for each file ? I mean if I modify a jpg file hunder of time, that will take a lot of space to keep each modifications between each save.

Do you have any idea how to not have a fragmented filesystem ? I can't see how we can not have a fragmented filesystem because when we deletre/write files on hdd the next file we write doest necessary fit into the space the last file before deleting it.

[AR]

You can move all the files up on the disk, this would be slow though so I wouldn't recommend it after every delete.

[Brendan]

Hi,

I see specs of filesystems supporting journal, its a kind of log, showing what job this file receive.

But this kind of filesystem is not oversized for each file ? I mean if I modify a jpg file hunder of time, that will take a lot of space to keep each modifications between each save.

The journal itself is only really used to fix things up later - for e.g. if the computer crashes (or loses power) in the middle of writing new data to a disk (leaving corrupt data) then you'd use the journal to restore the file system to a usable state.

For example, lets say you're creating a new file - you'd put "creating directory entry" into the journal, then create the directory entry, then put "creating initial file data" into the journal and create the file data, then put "marking sectors used" into the journal and mark them as used. After this you'd put a "checkpoint" into the journal. When the file system is first mounted you'd check the journal and see if there's anything after the last checkpoint (any operations that didn't complete).

If the computer died after the directory entry was created then you'd have a directory entry pointing to data that didn't get written. In this case the journal would contain "creating directory entry" without the data or checkpoint, allowing you delete the directory entry quickly.

If the last thing in the journal was "marking sectors used" then you might be able to quickly mark those sectors as used when the computer reboots. That's the basic idea behind journalling anyway - being able to quickly fix the file system if data corruption was possible.

As you can see, the journal itself never needs to contain any file data - only small "tokens" possibly followed by some sector/cluster numbers. You can also delete anything in the journal that is older than the most recent checkpoint. The journal itself doesn't need to be large at all.

Of course you should be careful with the order you do things in so that you need to updte the journal less. Returning to the previous example, what if you wrote the file's data then marked the sectors as used and then created the directory entry for it? In this case you'd only need 2 entries in the journal instead of 3.

There's are alternatives to journalling too - ignore the issue (data loss), check the entire file system for corruption each time you boot (very slow), or find another way to get the same results.

Do you have any idea how to not have a fragmented filesystem ? I can't see how we can not have a fragmented filesystem because when we deletre/write files on hdd the next file we write doest necessary fit into the space the last file before deleting it.

It's easy to prevent "file fragmentation" - if you're creating a new file look for a space that is large enough for the entire file and issue an error if there isn't a large enough free area. If you're making a file larger (appending data), look for a free area large enough for the old data and the new data, then copy all the old data and the new/appended data to the new space, then free the old version.

The problem here is that it's very slow to add data to an existing file, and you end up with a lot of fragmented free space.

A better approach would be to allow fragmentation (both file fragmentation and free space fragmentation) and have a defragmenter running in the background, so that the file system gets defragmented automatically when the computer isn't doing anything important.

You could combine these though - prevent file fragmentation when possible and
defragment files and free space in the background.

Designing a crappy file system isn't too hard, but designing a fast reliable file system is very difficult - many things to worry about.


Cheers,

Brendan