FAT

That is File Allocation Table. I was wondering if I need a file system? But what is a FAT and what problem is it trying to solve? I had a look on the Internet and I was flooded with specifications but nothing on the "why"!

What is the Problem?

After a few hours (perhaps more) I worked out what the problem is:

1. How do you find data (a file) if you don't know the address or exactly where it is (at least at compile time)? So you need a file name search routine that returns an address.
2. If your adding and deleting files how do you manage or reuse your memory? You need a linked list of used and unused memory blocks.
3. You don't execute code in the file system memory, so data need not be contiguous and can be in blocks.

I assume here you know what a linked list is!

So the role of the FAT is to keep a list of file names and the link to those blocks associated with the file. Much like the Forth dictionary (if you know anything about the internals of Forth), and a linked list of free blocks.

When you need blocks for a file you take them from the unallocated block list. When you delete files you return them to the unallocated block list. Formating a disk is the creation of the FAT and allocation of all the memory to the unallocated block list.

Internal Construction of the FAT

There are a number of ways of constructng the linked list(s). Some are simple and others are fast. I prefer simple. So a single linked lists with block headers, like the Forth dictionary, except unallocated blocks are at the end of the list (in a hidden file!). Unlike the Forth dictionary the blocks need to be of fixed size. Blocks need not be contiguous as code is not executed in the linked list.

More details when I return to this later.

AlanX