‫The file allocation table, what is the file allocation table?
‫The fall election table is a file system developed by Microsoft.
‫It consists of a series of clusters, the whole data and a table that determines the status of a cluster.
‫The boot sector, otherwise known as the bootloader stores.
‫Information about the file system.
‫The Fat 16 file system uses clusters to represent data and subdirectories.
‫Each cluster uses a fixed amount of sectors, which is specified in the boot sector every fall.
‫In fact, 16 needs to use at least one cluster for its data.
‫This means a lot of storage is wasted for small files.
‫For example, we could have a file called Haloti that just contains Hello World.
‫It is still going to use at least one cluster, which is a lot of wasted data that is not the most efficient
‫file system.
‫It's very easy to implement.
‫However, so far, 16 cannot so far larger than two gigabyte without large file support, with large
‫file support for gigabyte is the maximum.
‫So this is the fat 16 file system disk layout on the disk.
‫So the first sector here, we have the boot sector, we've written about sector before, about sector
‫or bootloader is 512 bytes in size.
‫Even though this is a file system, we can still boot from the medium because the boot sector, the
‫file allocation table file system requires is formatted in such a way.
‫It allows us to still store code in the boot sector.
‫I'll show you this later on.
‫So we would still be using our boot sector to load our kernel.
‫However, just bear in mind, when we implement the fabrication table, the boot sector will also contain
‫certain madar information about the file system.
‫Okay, which you'll see soon.
‫So after the boot sector in the file allocation table, we have the reserved sectors.
‫Now, this is essentially sectors we don't want to be included as part of the file system.
‫So for example, in the boot sector we have a Littlefield's that specifies how many reserve sectors
‫we have.
‫Right.
‫And the number in this field also includes the boot sector itself.
‫So if you don't have any reserve sectors, then the reserve sector fields should contain one because
‫the boot sector still counts as a reserve sector.
‫If that makes sense.
‫Now, the size of the reserved sectors is the reserved sectors field in the file allocation header,
‫which is stored in the boot sector, by the way, multiplied by 512 because 512 is the sector size on
‫hard disks after the reserve sectors.
‫We have the fat one now, fat stacks of file allocation table, essentially the fat stores information
‫that explains which parts of the disk is free and which part of the disk is used, which part of the
‫disk is inaccessible.
‫That's what the fabrication table describes and it also allows you to chain clusters together.
‫Okay, so for example, if you have a file this two clusters in size, then in the file allocation table
‫you'll have to bytes to represent a cluster.
‫Okay.
‫And the value of those two bytes will be the number of the next cluster of that file.
‫But we'll get more on that later.
‫And here we have the Fab Two.
‫Now, this is optional.
‫So I'm not going to discuss this in this presentation.
‫However, it's essentially just a duplicate of the fat one, and it's to be used as a backup for things
‫like data corruption.
‫And it's completely optional.
‫Now, after the second file allocation table, all the first file allocation table, if you don't have
‫a second, we have the root directory.
‫Now, the size of the root directory is specified in a field in the file allocation header file allocation
‫table header, I should say.
‫And the field is the root directory entries.
‫So the size of the root directory is simple.
‫It's the root directory entries multiplied by the size of the fat directory item structure.
‫Okay.
‫And we also need to round this up to the sector as well by the.
‫So the root directory will always use at least one sector, it isn't going to use 30 bytes, you understand?
‫So we need to round that to five, 12.
‫OK, so essentially, if size of the root directory does not fit into a sector, then we need to add
‫one sector to the size.
‫OK, now after the root directory have our data clusters, here is where all our data is stored.
‫Hello, text, text file.
‫The header will be wrote that is stored in these data clusters.
‫Remember, each file uses at least one data cluster.
‫OK, subdirectories also stored in the data clusters as well.
‫So that's the entire structure of Fat 16.
‫I'm now going to break down each part and we'll go into more detail and I'll give you some examples.
‫OK, so this is the fat 16 boot sector format I was telling you about.
‫So the very first thing you see is a short term.
‫This is assembly, as you can see now, this is a short jump to the start label.
‫This ensures that we jump over the fat 16 head and all of that stuff, and we also require no operation
‫after our short jump.
‫I mean, this is how the format expects, OK, file allocation table expects it in this format.
‫So next comes all the head of information.
‫And in the head of information, you can see we we stole the bytes per sacked.
‫This field should be ignored, by the way, because we can't rely that it's correct sectors per cluster.
‫This is a good field.
‫We need to rely on this.
‫This is how many sectors there are in one cluster.
‫OK, because remember those 10 you clusters where the file information is stored, right?
‫Then we have our reserved sectors.
‫So you can see in this implementation we have two hundred reserved sectors.
‫And obviously if you have quite a big kernel, you're going to need quite a lot of reserve sectors there
‫unless you plan to load the kernel from disk, which we won't do, by the way, because it's more complicated
‫and we can see here we specify them out of fact copies.
‫Remember I said you can have one file allocation table or a second one, which is a backup.
‫So that's why this says to so this media type can be ignored.
‫The number of sectors here can be ignored and all that sort of stuff.
‫Sectors per fact is important.
‫This is how many sectors are in the file allocation table itself so far.
‫Table one fact, one fact too.
‫You know, again, sectors per track, number of heads, these can all be ignored.
‫We don't have to worry about these here.
‫Our OEM identifier.
‫This is a little important, but not too important.
‫You know, when you put in a USB stick in your computer and it tells you the volume name, stuff like
‫that, what is actually called?
‫Well, the OEM identifier can be used for that, basically.
‫Right.
‫OK, so that's where the boot sector looks like after the file system header, we can see start label.
‫You can't see it because it's further down, but we jump to that and then that can all just be Kote.
‫OK, just as long as the head is formatted this way, everything will be fine and you need a short jump
‫and you need an operation.
‫And this is the assembled version.
‫So this is what it looks like when you open the file system in a hex editor.
‫So, yeah, we can see that sector there and we can see we still have our little boot signature at the
‫bottom here Fiverr.
‫OK, so that signifies we are bootable.
‫Now you can see after the first sector, these are all our reserved sectors.
‫So because we specify reserve sectors.
‫Two hundred, this means we have 200 reserved sectors after the boot sector before we have our file
‫allocation table.
‫Two hundred times 512 is one hundred 2400 bytes.
‫If our colonel exceeds this size, we need to increase the reserve sectors to 201 or otherwise we risk
‫corrupting the qualification table.
‫All the file allocation table will corrupt us.
‫So after the reserve sectors we have our file allocation table, the first allocation table file allocation,
‫table one fat one and we can see it looks like this.
‫So we can see the first few entries here ignored.
‫And then we have for now, each entry is two bytes in size.
‫OK, so if we count here zero, one, two, three.
‫So where it says for the very first five, this is talking about cluster three and cluster three is
‫taken and we know it's taken because the value is five first means and the file.
‫So this basically means that whatever data this is, there's no more data after it.
‫So in our text example, hello world, that's only going to be one cluster in size.
‫So we see five.
‫So this signifies this is the last cluster for this file.
‫If the yellow text file was two clusters in size, then there will be a number here pointing to the
‫next cluster.
‫So let's say it was cluster fall where the fog continued.
‫Then number four would be here and it would point to this one and.
‫US want to be fair?
‫OK, so as you know, each entry in the file allocation tables two bytes long, I just explain that
‫to you.
‫But what you might not know is they represent a cluster in the data clusters region that is available
‫or taken.
‫OK, so another thing, clusters can change together.
‫For example, a file larger than one cluster will use to clusters.
‫The value that represents the first cluster in the file allocation table will contain the value of the
‫next cluster.
‫The final cluster will contain the value of the u f f f f, signifying that there are no more clusters.
‫The size of a cluster is represented in the boot sector.
‫Let's take a look at this example table.
‫Unless I assume that we are starting from cluster zero, we can see here Cluster zero contains decimal
‫three, which means that there's more clusters to come and we should look at index three.
‫So zero one, two, three.
‫This is index three.
‫And we can see it says the box for signifying the end of the cluster chain.
‫So whatever this cluster here is representing has two clusters.
‫It could be representing a subdirectory or it could be representing a file file data.
‫Now, as I've already said, cluster zero is not really used.
‫We usually start a cluster three.
‫But I want to just give this example from zero because it's easier for you to understand so we can see
‫file allocation, table points to our data clusters as demonstrated in these tables.
‫So this represents data close to zero.
‫This represents data cluster one.
‫This represents data cluster to data cluster three and so on.
‫So obviously finding out where the data is in the data clusters is quite simple.
‫We need to first know the position of where our data cluster starts.
‫And we know this because it's directly after the root directory.
‫Okay, so now that we know that what happens next?
‫Well, we just multiply the cluster index by the size of a cluster and the size of a cluster is specified
‫in the boot sector.
‫So, for example, this specifies close to zero, so this cluster here represents the very first cluster
‫after the root directory.
‫So this represents the very first cluster in the data clusters region.
‫So it'll literally be the first byte after the root directory.
‫And obviously, this is once you multiply one by the size of the cluster, let's say sixty five thousand
‫five hundred thirty six or something.
‫Right.
‫So then you know that when you multiply that by one, you'll get sixty five thousand five hundred thirty
‫six and that would be the first bite of the next cluster.
‫OK, so I hope that makes sense.
‫These are just numbers I'm throwing at you here.
‫Just as an example, we probably won't use these exact numbers just to let you know.
‫I'm just trying to simplify it for you.
‫This is the process that's going on under the hood and this is what we're going to be expected to write
‫in the C programming language.
‫So let's explain.
‫The fat 16 root directory file systems have directories otherwise known as folders.
‫Fat 16 is no different.
‫Fat 16 has what's known as a root directory.
‫This is the topmost directory in the system.
‫Think of your C drive at the very top level of your C drive.
‫This is the root.
‫Directory directories contain directory entries of a fixed size.
‫So this is what a directory entry looks like.
‫So we can see we have the file name, which is eight bytes long for a short file name, isn't it?
‫There is long filenames.
‫They do exist, but we're going to ignore it because it's more complicated to implement.
‫And I want to keep this simple for you.
‫We can see we have an extension of three bytes for that filename.
‫We have an attribute field.
‫This contains things like flags and so on.
‫Preserved is self-explanatory.
‫We shouldn't use it.
‫It's reserved.
‫This is the creation time, creation day, the last time it was accessed, the high sixteen bits of
‫the first cluster for the data region of this directory item and the low sixteen bits of the first cluster.
‫So simply put, if this directory item represents a file, then bring these two together.
‫The high hibbits and low bits will give you the cluster of where the first byte is for this file.
‫So hello.
‫Hello.
‫Will write the high sixteen bits.
‫The first cluster in the low sixteen bits, the first class point to where the hello world message is
‫stored.
‫Okay.
‫The attribute fields also contain flags that determine if this directory item is a file, a directory
‫or if it's read only and so on.
‫So directory items can either be subdirectories or files.
‫If it's a file, then the the first cluster points to where the start of the file data is.
‫If it's a directory, then the first cluster points to the cluster where the subdirectory directory
‫items are stored.
‫And obviously they start the same way as they are stored in the root directory because on the root directory,
‫baozi have an array of these directory entries, right?
‫Subdirectories exactly the same.
‫We have a bunch of files and subdirectories represented by fat directory items.
‫Okay, I explained this here as well on this text.
‫OK, so how do we iterate through directories?
‫Well, the boot sector contains the maximum number of root directory entries and we should not exceed
‫this value.
‫And iterating through the root directory, we know when we have finished iterating through the root
‫directory or subdirectory because the first bytes of the filename will be equal to zero.
‫So what I mean by that is, you know, how we have an array of these directory items in the root directory
‫and in the subdirectory there will be an empty item somewhere at the very bottom of that directory and
‫the first bytes in the filename will be zero.
‫OK, so that's how we know when we're done because there's always a blank entry at the bottom of the
‫directory or subdirectory, so we just check for zero.
‫So the directory entry astrobee flags, you know, these directory entries, they're representing either
‫a file or directory.
‫OK, so these flags we have Read-Only and this is a bit mask, OK, read-only file, hidden sys file,
‫do not move volume label.
‫Do you extend means that this is not a regular file, it's a subdirectory.
‫So if this bit is set then it's a subdirectory.
‫If it's not set then it represents a regular file.
‫Bitsie.
‫Twenty archived bits, 640 device bits or eighty reserved must not be changed by death tolls.
‫So these are the flags in the field in the directory entries.
‫OK, so we now need to talk a little about the file name and the extension, because those special rules
‫that might catch you out the file name is a base wide unused bike's padded with spaces, not null.
‫Terminator's.
‫I know it's weird.
‫This is how it's done.
‫OK, so you know the file names done when there's a space.
‫And this also explains why spaces are illegal in this file system.
‫They get replaced with some weird other character.
‫But more on that later.
‫The extension is exactly the same as three bytes wide and unused.
‫Bytes are padded with spaces.
‫So, you know, when you're done, because you see a space, each class represents a certain amount
‫of sectors literally to each other.
‫So this is important to know, for example, in the boot sector, we might have 80 sectors per cluster.
‫So this means that one cluster is 80 sectors long.
‫OK, easy.
‫The data cluster section in the file system contains all the clusters that make up the subdirectories
‫and file data files throughout the file system.
‫So some useful tips before we end this lecture.
‫Always use Ashbery packed on structures in the C programming language that ought to be stored or ripped
‫from disks.
‫The C compiler can do very clever optimizations to speed up your code.
‫It can change these the way these structures are stored in memory.
‫And this could be very bad for us because we needed read and written exactly as we created the structure.
‫So by doing Asheri Pact, that ensures that always happens.
‫I want you to pay very close attention to the upcoming videos.
‫Things are going to get very difficult and mistakes might happen.
‫Be prepared to use a debugger such as GDP and attached a bug in symbols.
‫As I've shown you in previous lectures, you might need to develop this if you run into issues, but
‫don't sweat it.
‫I've broken the fat file system down.
‫I've explained it to you.
‫So now you should have a rough idea of what's going on when we start writing the code.
‫Now, I have written the file allocation table implementation before.
‫It's around 750 lines of code for a file allocation table that can only read, not write.
‫And, you know, so this is what you're going to be expected to write around 750 lines.
‫So just prepare yourself for it.
‫Pay close attention to everything I'm saying because you have a lot to learn.