Technical Article

MicroFAT: A File System for Microcontrollers

May 27, 2016 by Robin Mitchell

File systems can be great for handling data and organizing memory, but most file systems require large amounts of memory. This is where MicroFAT comes in!

File systems can be great for handling data and organizing memory, but most file systems require large amounts of memory. This is where MicroFAT comes in!

The Problem with Standard File Systems

Microcontrollers are becoming the core of many electronic projects for hobbyists and the norm in electronic design overall. With the complexity of projects increasing and the introduction of the IoT, it will not be long before micro users will need to also increase the capabilities of microcontrollers. 

A common use for microcontrollers is to log data from sensors such as temperature, humidity, and other stimuli. This data can be streamed to an I2C EEPROM and then read back when this data is to be sent to an external server (via the IoT). If the user wishes to store separate instances of data (for example, different times of the day), then the memory needs to contain information regarding the time the data was sent and how the memory is organised.

While the user could design a system to cope with such matters, it would be easier to implement a file system such as FAT. However, many micros are not capable of using the FAT file system because of the memory requirements.

For example, to use FAT32 on the PIC range requires up to 12KB of program memory, 2KB of data memory. FAT16 and FAT32 are also not ideal for 8-bit systems and contain a lot of unnecessary metadata (file creation date, permissions, etc.).

Because the file system is for private use between the microcontroller and serial memory, the system does not need to be compatible with PC standards. If files are to be transferred between a microcontroller and PC, then a simple application made in either Visual C#, C++, or BASIC could stream the bytes in and then save to a file.

MicroFAT is a standard currently in development for use in 8-bit designs which has emphasis on low memory usage, smaller block sizes, and an easier interface. For example, the MicroFAT standard is designed to be used with serial memory so there is no need for a RAM copy of the current working directory (which would otherwise need an additional 256 bytes). This is because serial memory holds its own internal address and therefore any file operations need only to set the memory address to the directory location and stream in data byte by byte.

Generic Layout

Two memory models are possible with the MicroFAT system: absolute address and block address. As all addresses in the file system are encoded with a 16-bit number, the maximum number of locations is 65,535. Therefore, this allows for either 64KB (when the address points to individual bytes) or 16MB (with 256 byte block sizes).

Absolute addressing has the advantage of storing file sizes to the byte value (such as 10 bytes), whereas the block address model can only store file sizes as blocks (not ideal for file streaming). The larger memory model also requires the current address pointer to be stored for individual bytes in the current block but the advantage is the significantly larger amount of memory.

For the sake of implementation, this article considers the absolute addressing mode for MicroFAT as I2C serial memory to typically range from 1KB to 64KB. 

All 16-bit values are in little endian form which means that the lower portion of the 16-bit number is stored in memory first with the upper portion stored afterwards. An example is given below:

The number 0x5ADA is stored in memory location 0x0010. This means that memory location 0x0010 has the number 0xDA and the memory location 0x0011 has the number 0x5A.

Memory Blocks

Memory is split into blocks of 256 bytes, which makes addressing very easy. As most FAT operations are concerned with blocks and 64KB is split into 256 blocks, only an 8-bit counter is needed to point to blocks in the system. 

 

 

The very first block in memory is the root directory and is used to store information regarding the bitmap location and device size. It can also be used to indicate boot options and other configuration data regarding the file system.

Bitmap Block

When an operation requires a block in memory, it must not use a block that is in use. One block is devoted at the very end of the memory which keeps a record of the state of each individual block: This block is referred to as the bitmap block. Its purpose is to keep track of a block's state, such as if it's currently in use or damaged (unusable). As each block is represented by 1 byte additional information can be encoded into the bitmap system by the user (e.g. reserved / system / boot).

The location of the bitmap needs to be at the very end of the memory and its location must be stored in entry 0 of the root directory.

Since MicroFAT has two memory models (absolute and block), the bitmap is encoded as shown below.

  • Absolute Addressing: Each block is represented by one byte
    • Bit 0 – Block is in use
    • Bit 1 – Block is damaged
    • Bit 2:7 – Unused (Free for user)
  • Block Addressing: Each bitmap byte represents 8 blocks. Each of the bits indicated if that block is in use or not. Damaged memory cannot be encoded.

 

Directories

Directories are 256 bytes in length (1 block) and can hold up to 16 entries. The first entry (FAT INFO) stores information about the current directory, which includes the block location of the parent directory (useful when going up a directory) and the current directory block location. The root directory contains an additional 4 bytes in its FAT INFO: the device size and the bitmap location. 

 

File and Directory Entries

All entries, both directories and files, are 16 bytes in length (unlike the 32 bytes needed in FAT). Each directory holds up to 15 files/folders with the first 16 bytes being devoted to directory information.

 

Entry Type Byte (0xn0)

Bit 0 Bit 1 Bit 2  Bit 3 Bit 4 Bit 5 Bit 6 Bit 7
In Use File / Folder Read Only System File Invisible Not used Not Used Not Used
1 - Yes 1 - File 1 - Read Only 1 - Sys File 1 - Invisible      
0 - No 0 - Folder 0 - RW 0 - User File 0 - Visible      

 

 

 

As each entry is only 16 bytes in length, it is easy to get to specific entries with the upper four bits of the address. Adding 0x10 and then performing a logical and with 0xF0 will get to either the next entry or the first entry (if the number overflows). Below is an example of getting to the next file in Z80 assembler:

nextEntry:	ld a, (fileCounter)
		add 0x10
		and 0xF0
		ld (fileCounter), a

Here is an example of a test root directory that shows the bitmap location, device size, and a few entries:

 

File Storing - Linked List

Files use the linked list system where the last two bytes of a block point to the next block to load. If the block pointer is 0x0000 then the end of the file has been reached as block 0x0000 refers to the root directory which is a reserved block. This means that the usable data in a block is actually 254 bytes. The benefit of this is that a table of file block ownership is not needed and significantly reduces the amount of memory needed.

 

 

The location of the first block is defined in the file entry bytes 0x01 and 0x02. The bytes are stored in little endian (like all data in the MicroFAT system), so if for example the file block was located at 0x1000, the entry bytes would be seen as 0x0001.

When deleting files, it is important that the file is scanned through the entire list to find which blocks are in use so that the bitmap can free the old blocks. It is also important that the last two bytes of every block are replaced with 0x0000 when freed so that the system does not mistake the end of the file as a load next block.

Infinite loop issue

The link system can get stuck in an infinite loop if the end-of-file pointer points to a previous block in the chain. It would be easy to create a search function that checks for such loops by keeping a record of all blocks loaded and comparing the next block load with the table. Once the file is loaded, the table can be discarded and the memory freed. If the small memory model is used, then a single 256-byte entry in memory could store the table comparison values and it would be large enough for any file (remember how blocks can be pointed to with a single 8-bit number). 

Implementation

Currently, no implementation in C exists but a preliminary can be downloaded for Z80 assembler. In the future, a generic C header + source will be developed that only expects the user to create the writing and reading functions for MicroFAT. A typical example is given below:

unsigned char memoryRead(unsigned short address)
{
	// User writes custom memory access code here
}

void memoryWrite(unsigned short address)
{
	// User writes custom memory access code here
}

This enables the user to create his or her own code for accessing any type of serial memory, whether it is SPI, I2C, or even external microcontrollers. The Z80 assembler is still in progress, but functions that work are those with (d) next to their function name in the comments. The rst instructions are designed to work with a custom BIOS but below is a basic set of the I2C memory rst calls that the MicroFAT calls:

 

I2C External Memory Routines (RST 0x18) : Z80 BIOS Calls
Register A Function Registers Description
0x00 Device Probe   Probes I2C Bus for selected device. Returns 1 upon detection
0x01 Device ID B Sets current I2C device to register B
0x02 Read Byte   Reads a byte from I2C and returns result in register A
0x03 Write Byte B Writes a byte to I2C found in register B
0x04 Read Block HL Reads a block of 256 bytes from I2C memory into address pointed by HL
0x05 Write Block HL Writes a block of 256 bytes to I2C memory found at address pointed by HL
0x06 Set Address BC Sets the current memory address of the current device to BC

microFAT.zip

It should be noted that the Z80 assembler code provided makes a copy of the bitmap and current directory directly into RAM for the sake of speed. This, in turn, uses an additional 512 bytes but low memory implementation would not need more than 32 bytes of RAM. If the current directory name was needed, then an additional 32 bytes of RAM would be needed to store the name. However, this is only required where the user can access the file system with a keyboard and display. 

15 Comments
  • A
    agaelema May 27, 2016

    Excellent article.

    In the “file storing - linked list”, the figure is correct? I ask this because the block and address in the last two blocks are the same, but the “next” in the second block point to 0x0600.

    “...so if for example the file block was located at 0x1000, the entry bytes would be seen as 0x0001.”, the value in little endian is not 0x0010?

    Like. Reply
    • Robin Mitchell May 29, 2016
      Hi there, Good spot! The address of the third block should be 0x0600. The diagram has now been changed. Regards, Robin
      Like. Reply
  • W
    wincrazy June 04, 2016

    “Because the file system is for private use between the microcontroller and serial memory, the system does not need to be compatible with PC standards.”

    What nonsense ! The entire point of having a standard file system is so it can be read by any Linux, Windows or Apple file system to have the data analyzed !

    Like. Reply