booting FAT12 revisited

[Schol-R-LEA]

As part of my typical thrashing about, I've decided to revisit my older Verbum handrolled boot loader, which I'd left in an incomplete state while trying to re-write it to boot as a FAT12 system (rather than the raw sectors I'd previously booted from). Aside from the significant trimming of print scaffolding I'd had in the earlier version, and the general issue of trying to read the FAT and directory data in the cramped confines of the boot sector, the matter that I've run into is that I've been trying to figure out a way to either hand-craft or generate the FAT12 data without using an existing tool such as mkfs.msdos.

I am unsure if this is really a sensible approach however, as it would presumably be a lot more practical to simply create the image file, mount it, add the second stage and kernel files to the mounted file, then overwrite the boot sector. I get the feeling that I am self-sabotaging again, that this is a sign that I am taking the hardest road with the expectation that I will give up before too long.

OK, aside from that, I am curious as to the best way to read the FAT and directory entries to find the files. I've been going over Alexfru's BootProg code, but I am not certain that I understand it as well as I would like. Alex's code seems to work by reading the first 12 sectors into memory wholesale, finding the directory entry for the kernel by name, and loading it from there. I'll probably follow suit, but I am wondering if there are any other methods which would work as well.

This probably seems like a fool's errand, seeing how I've argued myself against rolling one's own bootloader (and for good reason), but I have the sense that I've left this particular exercise fester and now I want to get it behind me once and for all for my own sake. I think I'll learn some things I've missed in all the years I've been daydreaming and puttering without actually doing much of anything.

Sorry if I've rambled on a bit here, but I'm a bit frazzled for a number of reasons and probably shouldn't be posting right now, but there it is.

[Octocontrabass]

the matter that I've run into is that I've been trying to figure out a way to either hand-craft or generate the FAT12 data without using an existing tool such as mkfs.msdos.

Do you want to write a bootloader or do you want to write mkdosfs? Pick one and forget about the other for now. You can always come back to it later.

Alex's code seems to work by reading the first 12 sectors into memory wholesale, finding the directory entry for the kernel by name, and loading it from there. I'll probably follow suit, but I am wondering if there are any other methods which would work as well.

My FAT12 bootloader (for floppy disks and for hard disks) loads everything one sector at a time as needed instead of loading the FAT and root directory all at once. That makes it easier to come back later and adapt the code for a FAT32 version, since the on-disk structures in FAT32 can grow too big to conveniently fit in real mode memory. (Secretly though I just want to hear the floppy drive seek a bunch while it's loading.)

Another option (with less time spent seeking) is to follow the cluster chain in the FAT to come up with a list of clusters, then use that list to load the file sectors. I don't know if any FAT12 bootloaders do this; 6kiB is pretty insignificant.

[Schol-R-LEA]

This is going to sound like a trivial question, but: in the standard FAT12 layout, does the root directory table come before or after the second (duplicate) FAT? I am fairly certain that it comes after the second FAT, but I wanted to be certain.

Also, is just the FAT duplicated, or is the root directory table redundant as well? Again, I am pretty sure it isn't, but I couldn't make that out from the documentation I found.

[bzt]

This is going to sound like a trivial question, but: in the standard FAT12 layout, does the root directory table come before or after the second (duplicate) FAT? I am fairly certain that it comes after the second FAT, but I wanted to be certain.

Also, is just the FAT duplicated, or is the root directory table redundant as well? Again, I am pretty sure it isn't, but I couldn't make that out from the documentation I found.

I would say yes to both. Now I haven't calculated it, but could it be possible that with the given cluster size and 1.2M capacity both FAT tables fit into 12 sectors? It seems reasonable to load everything up to the end of the root directory into memory with a single read, because you'll need both the FAT table and the root directory anyway. With 1.2M capacity the FAT table should be relatively small.

EDIT: ok, here's the math. 1.2Mb capacity and 1 sector per cluster (so that gives the greatest number of clusters). That's 2458 clusters. With 1.5bytes per cluster in a FAT and two FAT tables, gives 7374 bytes, or 15 sectors. So you're right, loading 12 sectors aren't enough. With the maximum, 1.44M capacity and 2880 clusters, you'd need to read 18 sectors to surely get the root directory too with a single read.

Alex's code seems to work by reading the first 12 sectors into memory wholesale

Where did you get that? As I see it, BootProg loads variable sizes, once the first FAT table at line 178, and then the root directory at line 200. It looks like the best approach I think.

Cheers,
bzt

[Schol-R-LEA]

As an aside, would anyone here be willing to critique the boot loader code as I have it now, even though it isn't finished? I've gone to great lengths to make it both readable and modular, but at this point I fear I've over-embellished it - which is another way of saying I've been stalling, yet again.

This is going to sound like a trivial question, but: in the standard FAT12 layout, does the root directory table come before or after the second (duplicate) FAT? I am fairly certain that it comes after the second FAT, but I wanted to be certain.

Also, is just the FAT duplicated, or is the root directory table redundant as well? Again, I am pretty sure it isn't, but I couldn't make that out from the documentation I found.

I would say yes to both. Now I haven't calculated it, but could it be possible that with the given cluster size and 1.2M capacity both FAT tables fit into 12 sectors? It seems reasonable to load everything up to the end of the root directory into memory with a single read, because you'll need both the FAT table and the root directory anyway. With 1.2M capacity the FAT table should be relatively small.

Well, I was focusing on the 3.5" 1.44MiB type of floppy rather than the 5.25" 1.2MiB type, but either way, it should fit into memory easily enough. Assuming 1 sector of 512 bytes per cluster, the clusters per FAT for the 1.44MiB disks is given as 9, so both FATs together amount to 18 clusters, or 9KiB total in memory - if you read both FATs in, as opposed to just the first one (which is what Alexfru does).

According to Maverick-OS documentation (which I'd missed earlier as the sitee was down), IIUC the size of the root directory table in sectors is
32 bytes per entry * the number of root entries given in the BPB
Which (again, assuming I understood what I've read correctly) would be 224 entries * 32 bytes / 512 = 7168 /512 = 14 sectors = 7KiB.

(Can anyone confirm the figure of 0xE0 (decimal 224) for the number of root entries on a FAT12-formatted 1.44MiB disk? I can't seem to find the documents where I'd originally gotten it from.)

This means that the total number of sectors needed for the boot sector, both FATs, and the root directory is 1 + 18 + 14 = 33 sectors = 16.5 KiB.

(Note that according to "The Skinny on FAT" - which again, I should have read earlier - in the original MS-DOS implementation the FATs are both all stored under head 0 except for the last sector of the 2nd FAT, which is at head 1, track 0, sector 1, while the root directory is all under head 1. )

Again, though, there's little reason to read all 14 clusters into memory, as the relevant entry is almost certain to be in the first sector of the root directory. While this could potentially fail if that assumption is wrong, I doubt it ever would be.

From what I've read, this is something that early versions of MS-DOS exploited, by simply requiring that IO.SYS and MSDOS.SYS (or IBMBIO.COM and IBMDOS.COM) be the first and second entries in the directory of a bootable disk, and that they had to be fixed as starting at the first data sector (Head 1, Track 0, Sector 16) - meaning that the boot loader could skip all the work of traversing the directory and just read a fixed number of sectors to get both files at once. I am not sure if this is really true, but it is certainly consistent with what I recall about MS-DOS 3.3 back in the day, from the times I tried taking a sector editor to various disks.

At this point, I'm not sure if I am just dragging my feet, as I should have enough information to implement the loader and plenty of examples to draw from if I am uncertain. I feel sheepish at having hesitated for the past 18 years on something which I am sure I could have done from the outset if I had the confidence to.

[Octocontrabass]

As an aside, would anyone here be willing to critique the boot loader code as I have it now, even though it isn't finished?

Any particular reason you chose to use nonzero segments?

Where is your stack supposed to be? I suspect it's not where you want it.

Why set GS but not FS? Do you use GS at all?

Did you want LEA instead of MOV?

Why are you worried about different sector sizes? An IBM-compatible BIOS can only boot from disks with 512-byte sectors.

Errors while reading the disk will modify AX, but you don't set AX again before retrying the BIOS call.

The AMD Athlon Processor x86 Code Optimization Guide has a very clever Hexadecimal to ASCII conversion that could save you some space, in case you find yourself running out.

clusters per FAT

The BPB records the size of the FAT in terms of sectors, not clusters.

Can anyone confirm the figure of 0xE0 (decimal 224) for the number of root entries on a FAT12-formatted 1.44MiB disk?

That's the default, although it's possible to use other values.

From what I've read, this is something that early versions of MS-DOS exploited, by simply requiring that IO.SYS and MSDOS.SYS (or IBMBIO.COM and IBMDOS.COM) be the first and second entries in the directory of a bootable disk, and that they had to be fixed as starting at the first data sector (Head 1, Track 0, Sector 16) - meaning that the boot loader could skip all the work of traversing the directory and just read a fixed number of sectors to get both files at once.

This is true, and it's the reason why MS-DOS required using the SYS command to make a disk bootable instead of simply copying the files. Your choice of search engine should be able to find you annotated disassemblies of various Microsoft boot sectors if you'd like to take a look.

[Schol-R-LEA]

As an aside, would anyone here be willing to critique the boot loader code as I have it now, even though it isn't finished?

Any particular reason you chose to use nonzero segments?

That was an error - I reversed the values of boot_base and boot_offset at some point, and didn't notice it until the other day when it bit me.

As for why I define them in the first place, well, it's just a matter of being thorough. I originally wrote this back in the days when it was still common advice to force the segment value through a FAR JMP at the start of the boot loader (which was due to non-compliant BIOS in the 1990s, and already unnecessary by 2000). I noticed that old bit of code, and that was when I noticed the reversed values.

Where is your stack supposed to be? I suspect it's not where you want it.

My intention was to set it to just before the boot sector entry point, with a 512 byte stack size. I've since changed it to a segment which begins after the end of the entry point's code, to allow for a full 64KiB, but again, I suppose it would be simpler just to keep SS equal to the CS - it's not as if I am likely to use a full segment's worth of stack memory, after all.

Why set GS but not FS? Do you use GS at all?

I'm not sure, to be honest. I think I'd had both cleared at one point, though if that's the case I don't know why I deleted the line for FS. In any case, I really don't have any need to clear either of them, and will remove that line.

Did you want LEA instead of MOV?

Good catch, and silly mistake on my part.

Actually, I noticed something else about that anyway - I should have been setting BP to point to the frame of those parameters, not to the point just before it, and performing those relative addressings based off of that. It's sort of the whole point of a base pointer, after all...

Why are you worried about different sector sizes? An IBM-compatible BIOS can only boot from disks with 512-byte sectors.

Only because the BPB defines it, and I was trying to be thorough, unnecessarily I suppose.

Errors while reading the disk will modify AX, but you don't set AX again before retrying the BIOS call.

OK, I need to fix that, thank you.

The AMD Athlon Processor x86 Code Optimization Guide has a very clever Hexadecimal to ASCII conversion that could save you some space, in case you find yourself running out.

I may need it, at that, though I have since commented out the print_hex function in any case, as the printed section didn't really help the way I'd intended it to.

clusters per FAT

The BPB records the size of the FAT in terms of sectors, not clusters.

OK, that was an attack of the dumbs on my part. You're correct, it is always in terms of sectors.

From what I've read, this is something that early versions of MS-DOS exploited, by simply requiring that IO.SYS and MSDOS.SYS (or IBMBIO.COM and IBMDOS.COM) be the first and second entries in the directory of a bootable disk, and that they had to be fixed as starting at the first data sector (Head 1, Track 0, Sector 16) - meaning that the boot loader could skip all the work of traversing the directory and just read a fixed number of sectors to get both files at once.

This is true, and it's the reason why MS-DOS required using the SYS command to make a disk bootable instead of simply copying the files. Your choice of search engine should be able to find you annotated disassemblies of various Microsoft boot sectors if you'd like to take a look.

I will take a look, though I'd rather not take that particular way out if I could avoid it.

EDIT: I know that many of the things I'm computing at runtime could be just taken as constants instead - the locations of the FATs, the directory entry, and the first data sector aren't going to change, so there's no reason not to just use those values directly. For some reason, though, I keep thinking in terms of not wanting to repeat constants, whether as magic numbers ir as values in both the EQUates and the BPB. It's sort of pointless, though; I'm not sure if DRY is a meaningful concept in assembly coding. I'm just making extra work for myself, which is one of the bad habits I need to get over.

I also have to admit that I am nervous about how readable my code is, and I've bent over backwards for clarity even where it wasn't necessary. I'm not sure if it isn't making things worse at this point.

[Octocontrabass]

I originally wrote this back in the days when it was still common advice to force the segment value through a FAR JMP at the start of the boot loader (which was due to non-compliant BIOS in the 1990s, and already unnecessary by 2000).

Didn't some versions of QEMU include a BIOS like that? Either way, it's still a good idea to set CS if you're going to rely on it having a particular value. (My FAT12 bootloader, linked above, doesn't rely on the value of CS.)

For some reason, though, I keep thinking in terms of not wanting to repeat constants, whether as magic numbers ir as values in both the EQUates and the BPB.

Couldn't you use the constant you defined with EQU in the BPB? Or is it an issue of having both the constant and the BPB field?

I also have to admit that I am nervous about how readable my code is, and I've bent over backwards for clarity even where it wasn't necessary.

Is that why you have a macro for setting a register to zero using XOR?

[BenLunt]

If you will allow me to, I will make a few comments as well.

- There is no reason to set the CS:IP register set by using a jmp at the first of your code. As long as you don't use the CS: override or a few rarely used other cases, your code should not care what the CS:IP register set is. Period.

- Make sure that any code and data used to read from the disk is within the first sector already loaded by the BIOS. It is a common mistake to place data past the 512-byte mark, expecting it to be there before you actually read it in. For example, if you have an error string that you print when there is an error reading from the disk, you can't print that string if you haven't loaded it yet. With that in mind, your routine to print to the screen must also be before this 512-byte mark. Make sure that all code and data that can be used before you load the rest of the code, is before the 512-byte mark.

- A FAT-12 boot sector and a FAT-16 boot sector only differ slightly, therefore you can write your code so that a simple MACRO (or EQUate) can be changed to build for either system. For example, the only code that actually is different is the Current FAT Entry offset (the offset from the beginning of the FAT to the current Entry) and the size of the entry received. Other than that, 99% of the code is identical whether you are building a FAT-12 or FAT-16 boot loader. If you call a function to get the next FAT entry, you can easily write two functions, one for FAT-12 and one for FAT-16 and simply define which to use.

If I where using the C Language, I would do:

Code: Select all

#define  FATSIZE  12

...

#if (FATSIZE == 12)
unsigned int GetNextFatEntry() {
  // do FAT-12 code
}
#else
unsigned int GetNextFatEntry() {
  // do FAT-16 code
}
#endif

or something similar. You get the idea.

- I suggest that you write the code to read only one sector of the FAT at a time. It is a simple task to determine which sector a FAT entry resides in.
Set a flag to 0xFFFFFFFF, indicating that you have not read in a FAT sector yet. The first call to your GetNextFatEntry() function will calculate the sector to read, determine that it doesn't match the flag's value, read in the sector, mark the flag with the new sector value, and continue on. Any remaining calls to the function will determine--using the flag value--that it is the same sector and simply skip the read; Or it will determine that the fat entry is now in a different sector, read that sector, save the sector number, and continue.

With this in mind, you only need a 1024-byte buffer for your loaded FAT, instead of allocating a lot of memory for the complete FAT Table.

Why 1024-bytes? A FAT-12 system FAT entry may span two sectors. Therefore you need to actually read two sectors. In FAT-12 systems, cluster number 341 spans two sectors, as well as the last cluster entry in every second sector. Therefore, calculate the sector the FAT entry starts in, read that sector and the following sector to be sure you get the whole entry.

With FAT-12 and FAT-16, this really isn't an issue. i.e.: Allocating and reading in the whole FAT Table is not a big deal. However, if you take the above suggestion a little further and now include a single file for all three FAT types, you can now easily integrate the FAT-32 system into your boot code. Why? A FAT-32 FAT Table can now easily span a 64k block, making a real-mode boot loader a pain in the rear trying to boot FAT-32. However, reading only one sector at a time (two actually), you don't have to worry about this any more.

- As for different sector sizes. Yes, as it has been stated, the BIOS will only load 512-byte sectors. However, it is a simple task that uses very little extra code to support different sector sizes. If you don't hard code the 512 and now use a variable value (register or memory location), you can easily write your code to accept other sector sizes.

I won't point you to the code that I use, since I believe it is best that one writes their own code, but I use a total of ten (10) assembly files for my FAT boot code. Seven of those files include code independent of the FAT size and are callable from my FAT-12, FAT-16, or FAT-32 code. The other three files are the actual main FAT boot code--two each for FAT-12 and FAT-16, though not separate for size, but separate for either Floppy or Hard drive (the .asm files don't care which size it is, they care if it is a floppy or hard drive), and the last file is for FAT-32, hard drive only.

i.e.: reading from the disk, printing to the screen, converting LBA's to CHS's, etc, don't have anything to do with the FAT size, so write them once, and "link" them in at build time.

Anyway, just my 2 cents worth.

Ben
- http://www.fysnet.net/osdesign_book_series.htm

[Schol-R-LEA]

I've taken at least some of your advice to heart, but I've also gone with a hardcoded second stage load for the time being - if I really feel the need I can always rewrite it later. Now I am trying to figure out the best way to add that second stage file to the disk image in a way that ensures it will be in the correct sector(s) for when I try to read it.

In the meanwhile, I have pushed the latest version of my code, if anyone wants to tear it apart.

[Schol-R-LEA]

For some reason, though, I keep thinking in terms of not wanting to repeat constants, whether as magic numbers ir as values in both the EQUates and the BPB.

Couldn't you use the constant you defined with EQU in the BPB? Or is it an issue of having both the constant and the BPB field?

Good point. I've gone ahead and done just this in my latest update.

I also have to admit that I am nervous about how readable my code is, and I've bent over backwards for clarity even where it wasn't necessary.

Is that why you have a macro for setting a register to zero using XOR?

Pretty much, yes. I actually meant to have a number of other macros for common short pieces that wouldn't make sense as subroutines, but never found enough situations where it made even the minimal amount of sense as the zero() macro.

[Schol-R-LEA]

I'm doing a fair amount on my boot loader, but I can't tell if any of it is progress.

Anyway, I wrote an LBA_to_CHS routine based on the LBA wiki page, though I am unsure just how I would test it aside from hoisting it to a completely separate program - which I may well end up doing if it comes down to that.

I can only hope that this will all be worth it. I am reading Ben's FYSOS books now (which I suppose I should have done earlier, I've had two of them for a while after all) and I'm seriously wondering if it would make more sense to implement FYSFS instead. I've been reading both Alexfru's and Octocontrabass's boot loaders and the more I read the less I feel I understand them.

This whole project has been rather frustrating, though I still hope that I am going to come away from it with at least some lessons learned.

[Octocontrabass]

Anyway, I wrote an LBA_to_CHS routine based on the LBA wiki page, though I am unsure just how I would test it aside from hoisting it to a completely separate program - which I may well end up doing if it comes down to that.

That would probably be faster than staring at it trying to find bugs like I did. Though, just looking at it, I think you have some confusion about which registers are inputs to the DIV instruction.

I've been reading both Alexfru's and Octocontrabass's boot loaders and the more I read the less I feel I understand them.

I'm willing to explain everything my bootloader does in however much detail you need to understand it. I've aggressively optimized for size, so there are some funny tricks that may not be obvious. (And while writing this post, I might have spotted another way to save a byte or two.) Feel free to use PMs if you'd rather not fill this thread with questions about my code.

[Schol-R-LEA]

Anyway, I wrote an LBA_to_CHS routine based on the LBA wiki page, though I am unsure just how I would test it aside from hoisting it to a completely separate program - which I may well end up doing if it comes down to that.

That would probably be faster than staring at it trying to find bugs like I did. Though, just looking at it, I think you have some confusion about which registers are inputs to the DIV instruction.

I can't believe I made that mistake. I think I remembered that the remainders went into DX, but forgot that DX was the high word of the dividend as well.

<rant>Have I mentioned how much I loathe the x86 ISA recently? Because I do, a lot. It's a huge flaming dumpster fire that no one should ever have to work with, never mind being the dominant desktop platform worldwide. It makes me long for the grinding monotony of MIPS code, where at least the ISA doesn't have the equivalent of hidden razor wire and tiger traps all over the place. And that's not even taking into account the miniscule register set, which requires constant juggling to do anything with.</rant>

Anyway, once I have slept off my current burning desire to punch an Intel engineer, and have regained a bit of my composure, I'll try to navigate my way through the narrow straits of the real mode register set to figure out how I am going to juggle all the values I will need to keep track of. I think I remember why I dropped this project four years ago.

[thewrongchristian]

<rant>Have I mentioned how much I loathe the x86 ISA recently? Because I do, a lot. It's a huge flaming dumpster fire that no one should ever have to work with, never mind being the dominant desktop platform worldwide. It makes me long for the grinding monotony of MIPS code, where at least the ISA doesn't have the equivalent of hidden razor wire and tiger traps all over the place. And that's not even taking into account the miniscule register set, which requires constant juggling to do anything with.</rant>

Anyway, once I have slept off my current burning desire to punch an Intel engineer, and have regained a bit of my composure, I'll try to navigate my way through the narrow straits of the real mode register set to figure out how I am going to juggle all the values I will need to keep track of. I think I remember why I dropped this project four years ago.

And this is why I use grub and never ever want to write a boot loader.

I'll stick to C and whatever assembly is required to reach the places C cannot. I don't think I even have an assembly language function long enough to spill registers to memory.