paul's 8051 code library understanding the fat32 filesystem.htm

硬盘ide和fat文件系统开发详解

  <TR>
    <TD>1</TD>
    <TD>Hidden</TD>
    <TD>1</TD>
    <TD>Should not show in dir listing</TD></TR>
  <TR>
    <TD>2</TD>
    <TD>System</TD>
    <TD>1</TD>
    <TD>File is operating system</TD></TR>
  <TR>
    <TD>3</TD>
    <TD>Volume ID</TD>
    <TD>1</TD>
    <TD>Filename is Volume ID</TD></TR>
  <TR>
    <TD>4</TD>
    <TD>Directory</TD>
    <TD>x</TD>
    <TD>Is a subdirectory (32-byte records)</TD></TR>
  <TR>
    <TD>5</TD>
    <TD>Archive</TD>
    <TD>x</TD>
    <TD>Has been changed since last backup</TD></TR>
  <TR>
    <TD>6</TD>
    <TD>Ununsed</TD>
    <TD>0</TD>
    <TD>Should be zero</TD></TR>
  <TR>
    <TD>7 (MSB)</TD>
    <TD>Ununsed</TD>
    <TD>0</TD>
    <TD>Should be zero</TD></TR></TBODY></TABLE>
<P>The remaining fields are relatively simple and straigforward. The first 11 
bytes are the short filename (old 8.3 format). The extension is always the last 
three bytes. If the file's name is shorter than 8 bytes, the unused bytes are 
filled with spaces (0x20). The starting cluster number is found as two 16 bit 
sections, and the file size (in bytes) is found in the last four bytes of the 
record. In both, the least significant byte is first. The first cluster number 
tells you where the file's data begins on the drive, and the size field tells 
you how long the file is The actual space allocated on the disk will be an 
integer number of clusters, so the file size lets you know how much of the last 
cluster is the file's data. 
<H2>File Allocation Table - Following Cluster Chains</H2>The directory entries 
tell you where the first cluster of each file (or subdirectory) is located on 
the disk, and of course you find the first cluster of the root directory from 
the volume ID sector. For tiny files and directories (that fit inside just one 
cluster), the only information you obtain from the FAT is that there are no more 
clusters for that file. To access all the other clusters of a file beyond the 
first one, you need to use the File Allocation Table. The name FAT32 refers to 
this table, and the fact that each entry of the table is 32 bits. In FAT16 and 
FAT12, the entries are 16 and 12 bits. FAT16 and FAT12 work the same way as 
FAT32 (with the unpleasant exception that 12 bit entries do not always fall 
neatly within sector boundries, but 16 and 32 bit entries never cross sector 
boundries). We're only going to look at FAT32. 
<P>The File Allocation Table is a big array of 32 bit integers, where each one's 
position in the array corresponds to a cluster number, and the value stored 
indicates the next cluster in that file. The purpose of the FAT is to tell you 
where the next cluster of a file is located on the disk, when you know where the 
current cluster is at. Every sector of of the FAT holds 128 of these 32 bit 
integers, so looking up the next cluster of a file is relatively easy. Bits 7-31 
of the current cluster tell you which sectors to read from the FAT, and bits 0-6 
tell you which of the 128 integers in that sector contain is the number of the 
next cluster of your file (or if all ones, that the current cluster is the 
last). 
<P>Here is a visual example of three small files and a root directory, all 
allocated near within first several clusters (so that one one sector of the FAT 
is needed for the drawing). Please note that in this example, the root directory 
is 5 clusters... a very unlikely scenario for a drive with only 3 files. The 
idea is to show how to follow cluster chains, but please keep in mind that a 
small root directory (in only 1 cluster) would have "FFFFFFFF" at position 2 (or 
whereever the volume ID indicated as the first cluster), rather than "00000009" 
leading to even more clusters. However, with more files, the root directory 
would likely span several clusters, and rarely would a root directory occupy 
consecutive clusters due to all the allocation for files written before the 
directory grew to use more clusters. With that caveat in mind, here's that 
simple example: 
<P>
<TABLE width=472 align=center>
  <TBODY>
  <TR>
    <TD><IMG height=309 alt="FAT Sector Diagram" 
      src="Paul's 8051 Code Library Understanding the FAT32 Filesystem.files/fat_sector.gif" 
      width=460 
      tppabs="http://www.pjrc.com/tech/8051/ide/fat_sector.gif"><BR><SMALL><B>Figure 
      7</B>: FAT32 Sector, Cluster chains for root directory and three 
      files</SMALL></TD></TR></TBODY></TABLE>
<P>In this example, the root directory begins at cluster 2, which is learned 
from the Volume ID. The number at position 2 in the FAT has a 9, so the second 
cluster is #9. Likewise, clusters A, B, and 11 hold the remainder of the root 
directory. The number at position 11 has 0xFFFFFFFF which indicates that this is 
the last cluster of the root directory. In practice, your code may not even 
attempt to read position 11 because the an end-of-directory marker (first of 32 
bytes is zero) would be found. Likewise, a filesystem with a small root 
directory might fit entirely into one cluster, and the FAT could not be needed 
at all to read such a directory. But if you reach the end of the 32 byte entries 
within the first cluster without finding the end-of-directory marker, then the 
FAT must be used to find the remaining clusters. 
<P>Similarly, three files are shown. In each case, the FAT gives no indication 
of which cluster is the first... that must be extracted from the directory, and 
then the FAT is used to access subsequent clusters of the file. The number of 
clusters allocated to the file should always be enough to hold the number of 
bytes specified by the size field in the directory. A portion of the last 
cluster will be unused, except in the rare case where the file's size is an 
exact multiple of the cluster size. Files that are zero length do not have any 
clusters allocated to them, and the cluster number in the directory should be 
zero. Files that fit into just one cluster will have only the "FFFFFFFF" end of 
file marker in the FAT at their cluster position. 
<P><B>Shortcut Hint:</B> One approach to the simplest possible code is to keep 
the root directory very small (few files, only 8.3 filenames), avoid 
subdirectories, and run the "defrag" program on a PC. That way, the root 
directory is found in just one cluster and every file occupies only consecutive 
clusters. Though this approach is very limiting, it means you can read files 
without using the FAT at all. 
<P>According to Microsoft's spec, the cluster numbers are really only 28 bits 
and the upper 4 bits of a cluster are "reserved". You should clear those top for 
bits to zeros before depending on a cluster number. Also, the end-of-file number 
is actually anything equal to or greater than 0xFFFFFFF8, but in practive 
0xFFFFFFFF is always written. Zeros in the FAT mark clusters that are free 
space. Also, please remember that the cluster numbers are stored with their 
least significant byte first (Figure 7 shows them human-readable formatted, but 
they are actually stored LSB first). 
<P>The good news for a firmware designer working with limited resources is that 
FAT is really very simple. However, FAT's simplicity is also its weakness as a 
general purpose file system for high performance computing. For example, to 
append data to a file, the operating system must traverse the entire cluster 
chain. Seeking to random places within a file also requires many reads within 
the FAT. For the sake of comparison, unix filesystems use a tree-like structure, 
where a cluster (also called a "block") has either a list of blocks (often 
called "inode" in unix terminology), or a list of other inodes which in turn 
point to blocks. In this manner, the location on disk of any block can be found 
by reading 1, 2, or 3 (for huge files) inodes. The other weakness of FAT, which 
is mitigated by caching, is that it is physically located near the "beginning" 
of the disk, rather than physically distributed. Unix inode-based filesystems 
scatter the inode blocks evenly among the data blocks, and attempt to describe 
the location of data using nearby inode blocks. 
<H2>Directories and Long Filenames In Detail</H2>
<BLOCKQUOTE>TODO: write this section someday.... the basic idea is that a 
  bunch of 32-byte entries preceeding the normal one are used to hold the long 
  name that corresponds to that normal directory record. </BLOCKQUOTE>
<H2>Where's the Free Code ???</H2>At this time, I do not have a free 
general-purpose FAT32 code library for you to easily drop into your project. 
<P>However, you can find FAT32 code in the <A 
href="javascript:if(confirm('http://www.pjrc.com/tech/mp3/%20%20\n\nThis%20file%20was%20not%20retrieved%20by%20Teleport%20Pro,%20because%20it%20is%20addressed%20on%20a%20domain%20or%20path%20outside%20the%20boundaries%20set%20for%20its%20Starting%20Address.%20%20\n\nDo%20you%20want%20to%20open%20it%20from%20the%20server?'))window.location='http://www.pjrc.com/tech/mp3/'" 
tppabs="http://www.pjrc.com/tech/mp3/">mp3 player project</A>. The 0.1.x and 
0.5.x firmware used a simple one-sector-at-a-time approach that is very easy to 
understand and only needs a single 512 byte buffer, but is not very 
sophisticated. These old firmware revs do not properly follow cluster chains for 
file (they do for directories), so it is necessary to run defrag before using 
the drive with them. 
<P>The 0.6.x mp3 player firmware does use the FAT properly to follow cluster 
chains. It uses megabytes of memory from the SIMM to buffer cluster and sectors 
from the FAT. A table of recently read FAT sectors is maintained, and a binary 
search is implemented to quickly locate the memory associated with any cached 
FAT sector. The firmware manages the megabytes of RAM by dividing it into 4k 
chunks (which works together with the bank swapping implemented by the FPGA), 
and the first 32 hold a big array of 16-byte structs with info about what is 
held in each 4k block. These structs implement linked lists that for each file 
cached in memory. A file I/O API is built on top of this to allow the main 
program to access the cached data. The 0.6.x firmware also uses DMA, so data 
transfers are quite fast. 
<P>Both of the MP3 player project FAT32 implementations are read-only. Both are 
GPL'd, but both are quite specific to that project. You can choose either very 
simple without features and needing defrag, or quite complex with lots of 
features but heavily dependent on the FPGA and SIMM. 
<P>Perhaps someday I will write a more general purpose FAT32 implementation with 
nice documentation for this code library section. But this is not planned for 
the near future. Hopefully the description on this page will at least help you 
to understand how FAT32 works so you can write your own code or understand the 
project-specific code in the mp3 players. 
<H2>Other Sites With FAT Filesystem Code For Microcontrollers</H2>
<UL>
  <LI><A 
  href="javascript:if(confirm('http://www.robs-projects.com/filelib.html%20%20\n\nThis%20file%20was%20not%20retrieved%20by%20Teleport%20Pro,%20because%20it%20is%20addressed%20on%20a%20domain%20or%20path%20outside%20the%20boundaries%20set%20for%20its%20Starting%20Address.%20%20\n\nDo%20you%20want%20to%20open%20it%20from%20the%20server?'))window.location='http://www.robs-projects.com/filelib.html'" 
  tppabs="http://www.robs-projects.com/filelib.html">Rob's Projects</A> - FAT32 
  File I/O Library. Intended for AVR, but the code is in C. 
  <LI><A 
  href="javascript:if(confirm('http://zipamp.virtualave.net/download.html%20%20\n\nThis%20file%20was%20not%20retrieved%20by%20Teleport%20Pro,%20because%20it%20is%20addressed%20on%20a%20domain%20or%20path%20outside%20the%20boundaries%20set%20for%20its%20Starting%20Address.%20%20\n\nDo%20you%20want%20to%20open%20it%20from%20the%20server?'))window.location='http://zipamp.virtualave.net/download.html'" 
  tppabs="http://zipamp.virtualave.net/download.html">Nassif's ZipAmp</A> - A 
  mp3 player with FAT16 and FAT32 code. </LI></UL>
<H2>Please Help....</H2>If you have found this web page helpful, please create a 
direct link on your own project webpage (hopefully with at least "FAT32" in your 
link text). Visitors to your site will be able to find this page, and your link 
will help search engines to direct other developers searching for FAT32 
information to this page. 
<P>Understanding FAT32 can be difficult, especially if you can only find poorly 
written documentation like Microsoft's specification. I wrote this page to help 
bridge the gap and make understanding FAT32 easier. Please help make it easier 
for others to find it. 
<P>Thanks. 
<P>
<HR>
Understanding FAT32 Filesystems, Paul Stoffregen 
<BR><!--url-->http://www.pjrc.com/tech/8051/ide/fat32.html <BR>Last updated: <!--date-->March 30, 2003 <BR>Suggestions, comments, criticisms: <A 
href="mailto:[e-mail]">mailto:[e-mail]</A> </BODY></HTML>