Page 1 of 1

For Mike...

Posted: Mon May 14, 2012 5:34 am
by linuxfreak
Hi, this is one of those, "Oh please would you all go away already!", type of questions. Just so you know!

It concerns chapter 22, the writing to a text file.

I was wondering if you still plan to update that part.

Regards.
PS. Sorry for bugging!

Re: For Mike...

Posted: Mon May 14, 2012 6:27 pm
by Mike
Hello,

There are a few updates planned for the series over the next few weeks. Writing a file will be added to the list. :) If requested, I can also provide information about it here prior to the updates.

Re: For Mike...

Posted: Tue May 15, 2012 1:21 pm
by pathos
Mike wrote:If requested, I can also provide information about it here prior to the updates.
Yes, please!

Re: For Mike...

Posted: Tue May 15, 2012 3:38 pm
by linuxfreak
pathos wrote:Yes, please!
What he said! :lol: The things I tried never yielded any positive working results other than the BSoD's stating "Invalid Opcode" or "General Protection Fault". Obviously I am doing something wrong, I need help.

I have tried searching online trying to find tutorials/code samples that allows me to write to a text file, but failure is all I encountered.

PS. I am sounding very dramatic over here, sorry!
PPS. This is probably a very simple subject with a very simple solution to a simple problem. I just cant figure it out! :cry:

Fat File Writing

Posted: Wed May 16, 2012 4:41 am
by Mike
This is going to be long. Please note that none of the code has been tested but should work; it first goes into an overview of file reading followed by writing due to the similarities between them. Please let me know if there are any errors that you discover or any questions or concerns on anything. I may adopt some of this material to the series.

Introduction
This tutorial provides information on writing files to disk using FAT12, FAT16 or FAT32 file systems. Due to the mechanics of the file systems being the same, the information provided can be applied to all three file systems.

It is important to know that developing the support for file writing has the potential for corrupting the file system on the storage medium. I recommend testing on an image file formatted to one of the file systems rather then a real disk during development unless you are willing to take the risk. Sometimes a corrupt file system can be fixed, however it can permanently cause data loss. You may find yourself having to reformat the storage medium several times when writing the code and expect file system corruption.

Reading files: overview
Before looking at writing files I would like to look at reading files. The steps used with writing files closely mimics that of reading files. For the following example, we will assume the storage medium is a system disk and the file system is formatted to FAT with no sub-directories.

In a FAT formatted volume, we have the Bios Parameter Block (BPB) structure, Volume Boot Record (VBR) followed by 0 or more reserved sectors and 2 copies of a File Allocation Table (FAT). In FAT12 and FAT16 the root directory follows the second FAT and is followed by the data area. Graphically, the disk looks like this:

Code: Select all

[BPB][VBR][Reserved Sectors] [FAT 1][FAT 2][Root Directory][Data Area][End of Disk]
+----+----+------------------+------+------+---------------+----------+-----------+
+----+----+------------------+------+------+---------------+----------+-----------+
|sector 0                                                             last sector |
The VBR is the boot code and contains the BPB and Extended BPB structures. Reserved Sectors is used when the VBR is more then one sector. Two copies of the FAT are on the disk. This is for redundant and bad sector detection. The contents of both of the FATs must be the same. It is the responsibility of the file writing software in the driver to update both of the FATs. We will cover how this is done a little later. The root directory follows the FATs in FAT12 and FAT16. FAT32 is a little different here, but we will ignore it for this example. The root directory is an array of Root Directory Entry structures. Finally, the Data Area consists of the other files and directories scattered throughout the disk.

To read a file from the root directory, we follow these steps:
  • 1. Load the root directory into memory
  • 2. Loop through each directory entry.
    • If directory entry name matches what we are wanting to find, we are done searching
    • If directory entry name[0] is 0 or 0xe5 then the entry does not exist; skip it
  • The directory entry gives us the first cluster to load
  • 3. Calculate the actual sector to load
    • cluster = directory Entry.cluster - 2 + firstDataSector
    • sector = cluster + (DirectoryEntryCount * 32 / BytesPerSector)
  • 4. Load the sector
  • 5. Find next cluster from FAT; and repeat steps 3 and 4 to load the rest of the file
To locate the next cluster we need to read a FAT table. The FAT table is just an array of 12. 16, or 32 bit values for FAT12, FAT16, and FAT32. (Technically FAT32 FAT entries are only 28 bits where the high 4 bits are reserved.) The FAT table provides us a logical "view" of the disk and all of the clusters. This is important as it allows us to convert a cluster to its FAT entry that it represents. For example, the first entry of the FAT represents the first cluster in the data area. The second entry of the FAT represents the second cluster in the data area, and so on. The first two FAT entries are reserved (used to store medium type and partition state information in FAT16 and FAT32 volumes.) Thus, Fat entry 0 and 1 are reserved, and Fat entry 2 refers to the first cluster in the data area.

To summarize, Fat entry 2 "refers" to cluster 0 in the data area, Fat entry 3 "refers" to cluster 1 in the data area, and so on. This is what "links" the FAT to the file clusters and allows us to "convert" a file cluster to a FAT entry and FAT entry to a file cluster.

To read the next cluster for the file, we first convert the cluster number to the FAT entry. Due to the cluster we got from the root directory is already relative to the data area, all we need to do to convert is multiply by 1/2 and read either the high 12 bits or low 12 bits (for FAT12) of the entry. (FAT16 and FAT32 differ here.)

Code: Select all

fatOffset = cluster + (cluster / 2) // multiply by 1/2
FAT [fatOffset] will give us the next cluster in the file to load assuming the entire FAT has been read.

The reason we covered reading files first is because it aids in understanding writing of files. Writing files is completely backward to that of reading; all of the steps are the same but are the inverse of each step.

Writing files
Recall the first thing we did when reading a file: loading the root directory and searching for an entry. We do the same for writing files in order to see if the file already exists or not. If the file exists, you can use the directory entry information as a starting point. If the file does not exist, you will have to add a new directory entry.

Writing a root directory entry
The root directory does not exist as a file in FAT12 and FAT16 so to write a new directory entry only requires these steps:
  • Load the root directory
  • Initialize a Directory Entry structure
  • Add the directory entry structure to the end of the root directory entry list
  • Write the root directory sectors back to disk
If we look at the root directory entry structure, all of the information there can be determined at this point except one: the starting cluster. If the file already existed, we dont have a problem. If the file didnt exist and we had to write a new root directory entry, we will have to wait until we traverse the FAT a little later to get that.

Writing a subdirectory entry
If you want to write to a subdirectory, you should make sure you have file writing support first because subdirectories are files. To add a new subdirectory entry:
  • Load the directory file
  • Initialize a Directory Entry structure
  • Add the directory entry structure to the end of the directory entry list
  • Write the file back to disk
Notice that a lot of these steps mimic that of writing to the root directory. The only real difference is that we need to be able to write files at this time.

Traversing the FAT: Locating the starting cluster for a new file
If we are writing a new file, we have to find a free cluster for it to use. There are a number of different ways we could do this: using a Best Fit algorithm, First-come algorithm for a few.

A "First come" algorithm would just start at the first FAT entry and read each entry until it finds the first free entry. You know if a FAT entry is free if FAT[entry] is 0, so a simple loop is all you need:

Code: Select all

curCluster=0; //cluster 0 refers to first cluster in data area
while (curCluster < numClusters) {
   unsigned int fatOffset = curCluster + (curCluster / 2);
   unsigned short tableEntry = *(unsigned short*) &FAT [fatOffset];

   if(curCluster & 0x0001)
      tableEntry  = tableEntry  >> 4;
   else
      tableEntry  = tableEntry  & 0x0FFF;

   // if this table entry is 0, this is the next free cluster
   if (tableEntry==0)
      break;

   // nope, go to next cluster
   curCluster++;
}
Once the first free cluster has been found, just update its directory entry firstCluster fields if you need to in order to point to it:

Code: Select all

directoryEntry.firstCluster = curCluster;
A "best bit" algorithm is better as it locates a set of contiguous clusters that are free which can later increase performance for reading and writing since there is little to do. It can also work very well with some disk scheduling algorithms that some operating systems use. For simplicity, we will stick with the "first come" algorithm for now.

Traversing the FAT: Writing the rest of the file
After the first cluster has been located from the FAT, we need to convert that cluster entry into the sector to write to. This is done like so:

Code: Select all

sector = (sectorsPerCluster * (curCluster - 2)) + firstDataAreaSector
Write the first sector of the file to sector.

If you need to write more sectors for the file, we need to locate another free cluster from the FAT first. This can be done by the same steps we did to find the first free cluster above. When we found the next free cluster, write to FAT [currentCluster] so it contains the value of the free cluster you just found. Remember, though, that in FAT12 each FAT entry is 12 bits. For example:

Code: Select all

unsigned short* tableEntry = *(unsigned short*) &FAT [fatOffset];

   if(curCluster & 0x0001)
      curCluster |= tableEntry & 0xFFF0;
   else
      curCluster |= tableEntry & 0x0FFF;

*tableEntry = curCluster;
Once the FAT has been updated, you need to do the same for the second FAT in order for them to be consistent with each other.

Continue searching for free clusters in the FAT, updating both FATs, and writing the sectors of the file until you reach the end of the file. Write the EOF marker to the last FAT entry and the file has been written.

Links
The following links provide additional information to supplement this material. Please note that these are 3rd party links so we are not responsible for any content on these sites. More links might be added later.

Inside DOS Article
This article covers the structure of the file system and how DOS works with it. Has great information on FAT12 and images. Suggested by GhostXoP.

Re: For Mike...

Posted: Wed May 16, 2012 2:52 pm
by linuxfreak
OMG! :shock: Thank you so much for the tutorial... I haven't tested the code yet, but like you said, It should work. Wow, I have a lot of work to do, now I can really continue with development. :D :D :D

PS? Do you plan on adding the tutorial to the OS Development site(or update the VFS Chapter 22)?
Jumping Regards...
Jean-Pierre;

Re: For Mike...

Posted: Mon May 21, 2012 3:01 pm
by linuxfreak
Hey.

Can you please post the modified code. Mine is not working. Sorry if I am, yet again being stupid but, where do you get all the variables(curCluster etc.)? :oops: :? ... Without them the code cannot work!

Regards.

Re: For Mike...

Posted: Mon May 21, 2012 8:08 pm
by Mike
Hello,

Please note that none of the above code was tested - but should work with little modification. It was provided to supplement the reading material only, not as a complete demo. This was intentional to encourage developing the software entirely on your own.

curCluster is primarily used as a FAT index in the above tutorial. We can use "curCluster" as an index into the FAT to locate the first free data cluster on the disk due to the relationship between the FAT layout and the disk cluster layout. We also (sort of) do the same when reading files.

If there is anything in particular you are not sure about, feel free to ask. You can also post your current file writing routines and the problem if you want for review.

Re: For Mike...

Posted: Sat May 26, 2012 10:53 am
by HeinanXP
Hey Mike,

For the next chapters, could you please add a chapter regarding how to make the OS use an hard drive? (let's say in FAT16/FAT32)

Oh, and another thing, perhaps adding a chapter regarding single & multi tasking?