KoizOS - Writing a simple FAT16 filesystem

Introduction

An important part of many modern operating systems is the storage and retrieval of data / files. For KoizOS, I'll be implementing FAT16 as my filesystem on top of a ramdisk I've created on boot. I chose FAT16 for both  the nostalgia and for being a relatively easy filesystem to implement.

Using Ramdisks

Before I could even get to work on the FAT16 part, I had to first write a ramdisk implementation. There are four important functions that FAT16 will be utilizing to both read and write data from RAM:

/*
 * This is a very simple ramdisk that's mainly just used for testing.
 * There's quite a few restrictions on size.
 */

void ramdisk_init(uint32_t size_in_bytes);

void ramdisk_destroy();

int ramdisk_write(uint32_t start_addr, uint8_t* data, uint32_t data_size);

int ramdisk_read(uint32_t start_addr, uint8_t* data, uint32_t data_size);

When the OS starts up, I allocate a ramdisk in memory with the physical memory manager and then proceed to format the new disk. I can't just zero everything out and expect it to work; instead I'll need to format the disk to match the FAT16 layout.

FAT16 Layout

There is a very helpful document on GitHub that I used to model my FAT16 implementation. The link to the original document is available below:

In case the link above is broken, the images below were copied directly from the PDF.

Formatting the Disk

Referencing the layout above, there are four major sections we need to deal with. These are the Bootloader, FAT tables, root entries, and data/clusters. I can format the disk into these four sections with the below function.

void ramdisk_fat16_format()
{
    /* represents a sector with all zero values */
    uint8_t zero_sector[FAT16_BYTES_PER_SECTOR];
    memset(zero_sector, 0x00, FAT16_BYTES_PER_SECTOR);
    int i;

    /* Write the bootloader */
    ramdisk_write(0x00, ramdisk_fat16_bootrecord, FAT16_BOOTLOADER_SIZE);

    /* zero out the FAT tables */
    for(i = 0; i < FAT16_SECTORS_PER_FAT; i++) {
        write_sector(FIRST_FAT_TABLE_SECTOR + i, zero_sector);
        write_sector(SECOND_FAT_TABLE_SECTOR + i, zero_sector);
    }

    /* zero out the root entries */
    for(i = 0; i < ROOT_DIRECTORY_SECTORS; i++) {
        write_sector(FIRST_ROOT_SECTOR + i, zero_sector);
    }

    /* Write the first cluster as 0xFFF8 */
    /* Write the second cluster as 0xFFFF */
    /* Remember this is stored in little-endian though! */
    uint8_t starting_sectors[4] = { 0xF8, 0xFF, 0xFF, 0xFF };
    write_sector(FIRST_FAT_TABLE_SECTOR, starting_sectors);
    write_sector(SECOND_FAT_TABLE_SECTOR, starting_sectors);
}

One really important thing to note is that the data is stored in little endian in FAT16 and so I'll need to convert all the data prior to reading/writing from the FAT16 system. Once the disk is all nice and formatted, we can get to work on writing a file to our disk.

Writing a File to Disk

To store a file to disk, we need to execute the following steps:

1. Convert the filename to a FAT16 filename
2. Find a free cluster in the FAT tables (There are two)
3. Create an entry in the root table and assign the free cluster to that entry
4. Write the file data to the cluster.
5. If the file data is large enough to span multiple clusters, find another free cluster and write to it. Point the previous cluster to the new cluster in the FAT tables.
6. Mark the last cluster written to as the end cluster in the FAT tables
7. Write the root entry to the root table.

FAT16 stores filenames by having the first 8 characters represent the name while the last 3 characters represent the extension. Spaces are added to buffer the name or extension to the appropriate length.

We then need to find a free cluster in the FAT table. The FAT table is a simple array with free clusters being marked by 0x0000. We can simply traverse the FAT table until we find a free cluster.

uint16_t find_next_free_cluster()
{
    uint16_t i = 0;
    uint16_t current_cluster = 0;
    for (i = 0; i < CLUSTER_COUNT; i++)
    {
        /* read the current cluster from the ramdisk */
        /* only using the first FAT table */
        ramdisk_read(
            (FIRST_FAT_TABLE_SECTOR * FAT16_BYTES_PER_SECTOR) +
                (i * sizeof(uint16_t)),
            (uint8_t*) &current_cluster,
            sizeof(uint16_t));
        
        /* cluster marked as 0x0000 is free */
        if(current_cluster == 0x0000)
            return i;
    }
    return 0;
}

Next, we then need to build up a new entry which will be stored in the root sector. Note that we're using the FAT cluster we found earlier.

/* Create a new struct for our file */
    ramdisk_fat16_entry_t new_entry;
    memcpy(new_entry.entry_name, native_file_name, 11);
    new_entry.entry_attrib = 0x00;
    new_entry.entry_reserved = 0x00;
    new_entry.file_size = data_size;

    /* First allocate free sectors */
    uint16_t current_sector = find_next_free_cluster();
    uint16_t head_sector = current_sector;
    uint16_t last_sector = current_sector;

    uint32_t bytes_left_to_write = data_size;
    uint32_t current_data_pointer = 0;

The last part is writing the actual data. I'll start at the cluster I reserved earlier and continue to allocate more clusters until the entire file is written to disk. The clusters act as a linked list as each cluster will point to the next cluster with final cluster being marked by 0xFFF8 (0x0000 won't work as it already marks a cluster as free). Note that since there are two FAT tables, the entry will need to be written to both.

    while(bytes_left_to_write > FAT16_BYTES_PER_CLUSTER) {
    
        /* Write entire contents of current sector to data sector */
        write_sector(FIRST_DATA_SECTOR + current_sector, 
            (uint8_t*)data + current_data_pointer);
        
        /* Grab next free sector */
        last_sector = current_sector;
        current_sector = find_next_free_cluster();
        
        /* Write current sector to FAT */
        uint16_t swapped_csec = eswap_uint16(current_sector);
        ramdisk_write((FIRST_FAT_TABLE_SECTOR * FAT16_BYTES_PER_SECTOR) + 
            (last_sector * 2), (uint8_t*)&swapped_csec, 2);
        ramdisk_write((SECOND_FAT_TABLE_SECTOR * FAT16_BYTES_PER_SECTOR) + 
            (last_sector * 2), (uint8_t*)&swapped_csec, 2);
        
        current_data_pointer += FAT16_BYTES_PER_CLUSTER;
        bytes_left_to_write -= FAT16_BYTES_PER_CLUSTER;
    }
    if(bytes_left_to_write > 0) {
        write_sector_partial(FIRST_DATA_SECTOR + current_sector, 
            ((uint8_t*)data) + current_data_pointer,
            bytes_left_to_write);
    }
    uint16_t swapped_c_end_value = eswap_uint16(0xFFF8);
    ramdisk_write((FIRST_FAT_TABLE_SECTOR * FAT16_BYTES_PER_SECTOR) + 
            (current_sector * 2), (uint8_t*) &swapped_c_end_value, 2);
    ramdisk_write((SECOND_FAT_TABLE_SECTOR * FAT16_BYTES_PER_SECTOR) + 
            (current_sector * 2), (uint8_t*) &swapped_c_end_value, 2);
    ramdisk_write(
        (FIRST_ROOT_SECTOR * FAT16_BYTES_PER_SECTOR) + 
            (new_root_entry * sizeof(ramdisk_fat16_entry_t)), 
        (uint8_t*) &new_entry, 
        sizeof(ramdisk_fat16_entry_t));

Lastly, we write the root entry to the root sector of the disk:

ramdisk_write(
        (FIRST_ROOT_SECTOR * FAT16_BYTES_PER_SECTOR) + 
            (new_root_entry * sizeof(ramdisk_fat16_entry_t)), 
        (uint8_t*) &new_entry, 
        sizeof(ramdisk_fat16_entry_t));

Reading a file from disk

Compared to writing a file, reading a file is trivial. Like before, we can break it down into a few simple steps:

1. Check if the file exists (after converting the filename)
2. Pull the root entry of the file and grab the starting cluster
3. Read the starting cluster and keep reading clusters that cluster may point to until we hit 0xFFF8.

I first need to check if the file exists by scanning through the root directory sectors. Note the filename conversion.

uint32_t ramdisk_fat16_file_exists(uint8_t* file_name)
{
    uint32_t i;
    ramdisk_fat16_entry_t cur_root_entry;
    for (i = 1; i < ROOT_DIRECTORY_SECTORS; i++)
    {
        ramdisk_read(
            (FIRST_ROOT_SECTOR * FAT16_BYTES_PER_SECTOR) +
                (i * sizeof(ramdisk_fat16_entry_t)),
            (uint8_t*) &cur_root_entry,
            sizeof(ramdisk_fat16_entry_t));
        
        /* If the initial character is not 0, we can scan the sector */
        if(cur_root_entry.entry_name[0] != 0x00)
        {
            /* Check if the file exists */
            uint8_t native_file_name[11];
            ramdisk_fat16_filename_to_native(native_file_name, file_name);
            if(memcmp(native_file_name, cur_root_entry.entry_name, 11) == 0)
            {
                return i;
            }
        }
    }

    return 0;
}

Next, we read the root entry and grab the sector that the file's data is in. We now have the file data we requested.

    uint16_t current_sector = entry.entry_low_cluster_number;
    read_sector(FIRST_DATA_SECTOR + current_sector, 
            (uint8_t*)sector_buffer);

Putting it all together

To test to see how my implementation behaves on KoizOS, I'll have the operating system format the ramdisk and insert two files on boot. It will read one of the files and display the contents. Afterwards, it will list the statistics of the FAT16 filesystem along with any files that are currently residing on it.

Now I have a basic filesystem! The next step in our journey will be adding a shell. Although it doesn't look super impressive at first, I'm sure the filesystem will look much more impressive once I can use the shell to read/write files!