Our Goal

In this tutorial, we are going to create disk partitions and make file system on disk, it is a long page, but it is not difficult. Just relax and take it easy.

Download source code

Accessing Hard Disk

As we all know, disks are consisted by sectors, and in general each sector is 512 bytes long.

There are two common ways to locate a sector on disk, one is called CHS which simply stands for Cylinder, Head and Sector, it reflects the physical structure of disks. The Sector is the minimal data block that hard disk can access directly on disks. Cylinder also called track contains certain amount of sectors (18 sectors in 1.44M floppy disk, for hard disk, this value usually is 64), like its name saids, it is a circle at the same radius from the center. Head indicates which side of the plate, because on disk can contains several plates, and each plate has two sides. Here is one plate of the hard disk,

Obviously, in CHS method, the capacity of the disk can be represented as (number of cylinders) * (number of heads per cylinder) * (number of sectors per head) * 512. There is another thing I have to mention, for the number of cylinders and heads, they always start from 0, and sector starts from 1.

LBA(Linear Block Addressing), it is the logical addressing scheme of your physicial disks. Like the linear memory address, LBA also use linear address to represent the sectors in the disk, cylinders and heads are not used any more. It is easier for user to use, but CHS is the method that the driver recognizes, so we need to find a formula of translating CHS to LBA. We let linear sector addresses start from zero.

• LBA = (C*number of heads per cylinder + H)*number of sectors per head + S-1

And another way around

• C = LBA / (heads per cylinder * sectors per cylinder)

• temp = LBA % (heads per cylinder * sectors per cylinder)

• H = temp / sectors per cylinder

• S = temp % sectors per cylinder + 1

You can get your CHS information from the BIOS of VMWARE or whatever the virtual machine you are using.

We can see the hard disk I am using have 208 cylinders, 16 heads and 64 sectors per cylinder. Let's put them into a structure like this,

07/dpt/hd.c

Because Skelix uses LBA addressing, so it has to translate the LBA address to CHS before accessing hard disk.

Now we get the CHS address, we are going to access disk using ports 0x1F0-0x1F7.

07/include/hd.h

It looks scary, but it can be grouped quite clearly, we read data from 0x1F0, if any error happens we get the error state from 0x1F1, we set secter number at 0x1F2 and 0x1F3, 0x1F4 and 0x1F5 are for cylinder number, clearly 0x1F6 for head, we read the hard disk status from port 0x1F7, we sent command like reading or writing to port 0x1F7.

To sum up, accessing a certain sector needs certain steps introduced below. I am not going to do many error checkings. This function hd_rw is the interface which going to be used to access disk.

07/hd.c

We keep checking the hard driver state till it is ready, the individual bit from this ports when it is set means,

keep going...

The port for head information is also used for selecting the hard disk,

Keep going...

com is the action we want the hard driver to do, they are defined as,

Keep going...

insl and outsl like inb and outb we used before, except they read/write a certain length of data instead of one byte.

Ensure the work is done.

Actually, it only gives you a rough idea of accessing disks, it doesn't do many error checking, please be aware of that. However, Skelix is not going to do any complexed operation, so it is okay at this moment :)

Disk Partitions

Now we have the ability of accessing any sectors on our disk, let's get all those sectors organized.

The first sector of the hard disk must contain the information about disk partitions. The disk partition table (DPT) starts from 0x1BE from the beginning of the first sector, it is 64 bytes long contains information about four partitions. Needless to say, the following three partition entrys start from 0x1CE, 0x1DE and 0x1EE respectively, the fourth entry ends at 0x1FC, and the 0x1FE should contain a word 0xAA55.

This table shows the format of each entry,

Byte 0 defines if this partition is bootable, the valid value for a bootable partition is 0x80. In general one disk can only have one bootable partition. byte 4 defines the type of the file system created on this partition, like FAT32, NTFS, ReiserFS etc., you can check here to get the full list of partition types.

Actually we can see (bytes 1-3, bytes 5-7) and (bytes 8-11, bytes 12-16) provides two possible ways to locate sectors on a partition, (bytes 1-3, bytes 5-7) provide full information about CHS format, but I am not going to explain the details about those bytes because we are not going to use them. About bytes 8-11, these 4-byte long integer provide the offset of the starting sector in this partition from the beginning of the disk, and bytes 12-16 indicates how many sectors on this partition, and just sum them up then we will get the LBA address easily. In a nut shell, the structure of DPT actually provides two ways to locate sectors, so in practice we can just choose one of them to manage our disks. So the second way is what we are going to use.

Let's set up the DPT,

06/dpt/hd.c

The first partition is a bootable normal file system, the type of this partition is defined as FST_FS, and the capacity of this partition is 85MB.

The second partition is a swap partition, it is going to be used in next tutorial.

Signature.

Don't forget to write it to the first sector. Function hd_rw, it takes the sector number as the first argument, and then second argument is very clear, it is going to write, the third argument indicates how many sectors we are going to access, here is just one, then the last argument is the sectors buffer.

Let's take a look another function, it is going to print the partition information on booting.

The starting address and length of each partition will be stored in HD0_ADDR after bootstrap.

Checks if it is a valid sector.

Check the bootable flag and file system type of this partition.

Before we go on to see the result, we have to modify the code about task1_run and task2_run we used in last tutorial, because they keep scrolling up the screen, and that makes us really not possible to watch the result printed by verify_DPT, so we change their's code to these,

we let task1_run keeps flipping the second character on the bottom line, and task2_run keeps flipping the third character at the bottom line.

Now we can get a clean screen for output. Modify the Makefile, add hd.o to KERNEL_OBJS, and add verify_DPT in 07/dpt/init.c right before sti().

07/dpt/Makefile

07/dpt/init.c

Because after sti(), task swiching is enabled, and the new coming task might use the hard disk before it is set up properly.

Finally,

And please be aware of one thing, because we set up Skelix in a virtual machine, there is no other OS use this virtual hard disk, so we do not need to be worried about other system's partition, just for simplicity, Skelix presume the first partition is for normal file system, and the second one is a swap partition.

File System

Since we got the partition organized, so let's organize the file system on each partition. Now we can access any sectors on partitions, but that is not convenient to manage files, we have to get it more structured, so we have to introduce a new structure to present files.

07/fs/include/fs.h

*nix-like users must be familiar with name inode, now I am going to explain each field in this structure. i_mode defines the type of this file, Skelix is going to treat all files identically by using INODE, FT_NML indicates this file is a ordinary file, FT_DIR indicates this file is a directory. i_size is simple, it is file size, the measurement of directory file will be explained later. The first 6 unsigned integer indicate first 6 sectors of the file, that is 3KB, the 7th unsigned integer indicates the a sector which contains 512/4 = 128 sector numbers, they are the following 128 sectors in the file, that is 128*512 = 64KB, the last unsigned integer indicates 512/4 = 128 entries and each entry works like the 7th integer in the array, so it can present 128*128*512 = 8MB, so using this three level disk "pointers" we can have a 3+64+8*1024 = 8259KB file at maximum. It is small, but please be aware of our partition is only 85MB, so it is enough.

For example, above is a file's inode, then all its data contains in the sequence of sector 13, 7, 9, 16, 257, 57, 3, ....., 35, 33, ....., 55, ......., 128, ....., 81

For the directory file, it is constructed like an array in the structure of {{file_name, file_inode}, {file_name, file_inode}, {file_name, file_inode}, }

All files in system has a unique file inode number, so if we have the inode number, then we can find the file. The first two files as you may guess are "." and "..", represent current directory and the upper directory, so if we go downward, we can find every file include directories in this directory, and if we go up we can find its parent etc. The top level of directory hierarchy is /, it does not have valid parent.

For example, if we want to locate TODO file at /usr/doc/fvwm/TODO, then at first we find / file, and search all its entries to find doc file, it is a directory, so we get it's inode number from / file and search the inodes table at somewhere, then we earch its content till we find the next path portion fvwm, then search its inode number again at somewhere, then search file fvwm till we find the ordinary file TODO and its inode number pair, then again we search some where to locate its inode structure by its inode number, then finally we can access the i_block array, that means we can access this file.

So as you can see, there are two problems, one is there must be somewhere for system to look for inode by inode number, so we manage all inodes in system into a array on disk, and make the inode number to be the index of the inode array, another problem is / does not have parent, so we have to know the certain place to locate the inode of /, that's fairly easy actually, we can just make / own the first entry of the inode array, then its inode number will always be zero. Actually, there is another tiny but really annoy stuff, we have to define the length of maximum file name, because the number of inode is going to be presented as an integer, so that is 4 bytes, then we make the maximum file length to be 12 bytes, so we get 16-byte entries in directory file, that is convenient for management and disk I/O.

After some file creations and deletions, some inodes are used and others are not, but how can we tell that, well, we are going to make a bitmap about inode array, one bit refers to one entry in the inode array, once an inode is used, then set the corresponding bit, when it is freed, then unset it. The same problem exists in manage free sectors, we will use another bitmap refers to which sectors on disk have been used, and which are free.

07/fs/include/fs.h

Type of the partition, FST_FS or FST_SW

Start sector number

The capacity of this partition, count in sectors

How many blocks we have to use to contain the bitmap of blocks (in Skelix, one block is one sector)

How many blocks we have to use to contain bitmap of inode array

How many blocks we use for inode array

This structure is used to manage super block information on each partition.

To sum up, we should have a disk image like this,

The first sector of each partition is a boot sector, but I am not going to use it, and the second sector contains the super block, then the dmap follows, then imap and inodes, user's data stores after all those stuff.

Let's define these macros for convenience. sb is the partition's SUPER_BLOCK structure, we use these macros to get the LBA address of certain sector for the use of hd_rw function.

These blocks are reserved by Skelix. Now we have the rough idea of the partition look like, then let's take a look at the code. Bitmaps also make those bitwise operation easier,

07/fs/fs.c

For example, by calling setb(sect, 1796) sets 1796th bit in bitmap, offset starts from 0, clrb is for clear a bit, testb is for test if a bit is (un)set.

Reads the super block of first partition, it should be the ordinary file system.

We setup the filesystem at the first boot.

Fills in the SUPER_BLOCK structure and write it to disk. Please be aware of this, in dmap block, each bit presents a sector, so one dmap sector can present 512*8 = 2^12 sectors, and we simply did a bitwise operation. For simplicity, we defined every partition has a fixed number of inodes, we define every partition use one secter as imap, so it can present 512*8 inodes which is INODE_BIT_BLKS=1, and one sector can contain 512/sizeof(struct INODE) inodes, so we need INODE_BLKS=((INODE_BIT_BLKS+INODES_PER_BLK-1)/(INODES_PER_BLK)) sectors for inodes array.

Playing with bits, filling the dmap and imap, setting all sectors which occupied by boot sector, super block, imap, dmap and inodes to 1 in dmap.

The second partition is a swap partition used for virtual memory, I will explain it in the following tutorial. At this moment all we have to know is every 4k disk space is grouped as one unit, we do not need imap and inode in this partition, so that will be fairly easy,

There is another difference, once we boot up the system, we clear all bits in bmap, so we do not keep any information in disk, the reason for doing that will be explained in next tutorial.

Don't forget to modify Makefile, add fs.o into KERNEL_OBJS, then make clean && make dep && make

07/fs/Makefile

root

The last thing left in this tutorial is to set up the root directory, the / directory is the root of all files, so we have to locate it at the boot time for searching other files.

/ file always use inode 0, then the Skelix knows where to find it, it can read the content of / file, that is a array of DIR_ENTRY, then Skelix can locate files just under / directory. By keep doing this, it traversals all files in the whole file system hierarchy.

Before we check out the code about creating / file, we have to take a look at several functions which is manipulating blocks and inodes on file system,

07/root/fs.c

This function locates the first free block on disk, then return the LBR address which is start from the beginning of whole disk, actually this is what we are going to use in kernel, all disk addresses is an absolute LBR address starts from the beginning of whole disk instead of separate partitions.

alloc_inode and free_inode pairs work as same as alloc_blk and free_blk except it manipulates inodes.

iget reads an inode from disk with a given inode number to memory and iput writes an inode from memory to disk. The meaning of those six functions are very clear, even though their code are not:(. Be aware of those functions do not handle race condition, because they are only used by kernel to set up the system, user tasks should use system calls which will be introduced in later tutorial.

We load the imap block to memory, if the / file has been created, then the first bit of imap should be set.

/ must use inode 0, if this inode has been allocated, then some wrong has happened.

we write the inode of / to disk, it has been set to the directory type, it has the length of two DIR_ENTRY because one is '.' and the another one is '..'. Then we allocate a free block on disk and set it to the first block of / file.

Well, we filled the first block with correct information in format of {{".", 0}, {"..", -1}}, we let the inode of root's parent to be an invalid value -1, so we can know we reach the top of the file system hierarchy tree, we cannot go up anymore.

We use function stat to check file information.

Print the type of file, it must be one of FT_NML and FT_DIR.

For directories, it prints all entries in the first block.

Finally, let's put them together,

Then put verify_dir into 07/root/init.c, let it just after verify_fs().

07/root/init.c

If you are using a newly allocated disk in this virtual machine, then you can see,

Exactly one screen, woo!

Feel free to use my code. Please contact me if you have any questions.