booting FAT12 revisited

[BenLunt]

I am reading Ben's FYSOS books now

Thank you.

I'm seriously wondering if it would make more sense to implement FYSFS instead.

First, I would much enjoy hearing how you loved/hated implementing this file system. Any comments that you have, both good and bad, would be well appreciated.

With that being said, and not knowing if you are writing for a floppy or hard drive now, I actually would recommend the LEAN file system. The FYSFS system was intended to simply see if my virtual file system layer was independent of the actual file system. When I first started, I implemented FAT as well. When I started to expand out to other file systems, I noticed that some of my code was too specific to FAT, so I needed a test bed. Plus, I thought it would be (and is was) enjoyable to make a simple, non-existent file system to test with. The FYSFS system has a few advantages, allowing for quite long file names, (mostly) unlimited sizes both file names and actual file contents, and a few other items. However, it has disadvantages as well. The overhead for these "slots" (I call them) takes a little bit of space.

Anyway, if you are writing for a hard drive, I would actually recommend the LEAN file system. I had/have the honor of working with the original author and have added and implemented a lot of its current format. I believe he (we) are ready to release version 0.7 soon.

The LeanFS has a lot of advantages: Large files, long filenames, extents, forks, etc.

Anyway, if you do implement the FYSFS system, please let me know how you feel about it, and don't be afraid to express your mind. I don't expect much from the file system, so I don't expect much praise either. If you implement the LEAN system, I would love to hear about it too.

Thanks,
Ben

[Schol-R-LEA]

I'll consider using LEAN FS, then, though I might try FYSFS first, we'll see. I mean to at least try finishing the FAT12 implementation, though I am not sure if I will be able to complete it.

After I've implemented some basic kernel-prep code in the second stage and loaded an actual simple 32-bit kernel (in C) from there, my next step is going to be to try a HDD image, which I'll use either FYSFS or LEAN, depending on which seems most reasonable.

I know this is all somewhat backwards, going from working on using GRUB and UEFI to playing around with an old-fashioned hand-rolled BIOS boot loader, but I was having so much trouble with motivation that this seemed like a way to give myself a kick in the pants. I'm not sure why, but at least for now it seems ot have worked, even if my frustration with the process is eroding that determination.

I think part of the problem I've had was that I was too stuck on the more ambitious ideas, and never really did the basics of OS development - I was trying to run without learning to walk first, and as a result was unable to make even the most marginal progress. I need to actually get the practice I've so far avoided, in order to be ready to do something bigger. I am probably at least three or four separate OS practice projects before I can even consider the simplest of my experimental ideas.

[Schol-R-LEA]

I've been working on code for reading the FAT (all at once) and the root directory, and started on the code for decoding the FAT entries, though I will need to stop for a while since, frankly, my head is spinning. I have no idea how well I've done with any of this, and I'm sure that there are more than a few bugs - probably more than there are parts that are correct, really. But at least I'm doing something for once, even if it is junk.

EDIT: I wrote what was supposed to be the code for actually loading the second stage, but unsurprisingly it isn't working. Debugging this promises to be a bear.

[Schol-R-LEA]

I've made quite a bit of progress, writing various test programs and doing a lot of print debugging, but I'm still pretty frustrated with some odd things going on.

I did chase my tail a bit over some values which seemed to be read wrong, when all the other values were correct, until I realized just now that they were the timestamps, and hence were getting replaced every time I rebuilt the file.

I'm not sure, but I am wondering if I am performing the filename comparison correctly;

Code: Select all

;;; seek the directory for the stage 2 file
        mov bx, dir_buffer
        mov cx, Root_Entries
    .dir_entry_test:
        mov di, bx
        mov si, snd_stage_file
        push cx
        mov cx, filename_length
        repe cmpsb              ; is the directory entry == the stg2 file?
        pop cx
        je .entry_found
        add bx, dir_entry_size
        loop .dir_entry_test
        jmp .no_file

Some of this is based on Octocontrabass's code, but I am no longer convinced that I understood what he was doing as well as I thought I had.

[Schol-R-LEA]

I am going to try the same trick I used to test the LBA-to-CHS code, namely separating the code for reading in the FAT and Root Directory and the entry seeking code into separate functions in their own include files. This will let me test each of them in isolation, and see where the problem lies. It is possible that just the act of isolating them will make a difference, by removing hidden dependencies, though doing so will put more space pressure on the final boot code.

EDIT: It seems to have worked, much to my surprise. However, the space crunch is getting serious now, so I will have to find ways to trim the code.

[Schol-R-LEA]

At the risk of becoming tedious, I have a question regarding the wiki page on FAT, specifically the section about computing the location of a FAT entry.

The code example given say,

Code: Select all

unsigned char FAT_table[sector_size];
unsigned int fat_offset = active_cluster + (active_cluster / 2);// multiply by 1.5
unsigned int fat_sector = first_fat_sector + (fat_offset / section_size);
unsigned int ent_offset = fat_offset % section_size;

I am assuming that the two references to 'section_size' are actually supposed to be sector_size, correct? Should I correct this, or is this in fact supposed to be 'section_size' and the code is incomplete for some reason?

On the assumption that it is supposed to be 'sector_size', I wrote the following function, which I am presently getting ready to test:

Code: Select all

;;; extract_next_fat12_entry - read a FAT entry to
;;;               see where the next FAT entry is,
;;;               if any
;;; Inputs:
;;;       DI - FAT entry buffer 
;;;       BX - current FAT entry's value
;;; Outputs:
;;;       AX - next FAT entry's value
extract_next_fat12_entry:
        mov ax, bx
        shr ax, 1               ; integer ax / 2
        add ax, bx              ; FAT offset
        xor dx, dx
        mov cx, 0x200           ; == Bytes Per Sector
        div cx
        add di, dx              ; index into FAT buffer
        mov ax, [di]
        and bx, 1               ; check if the existing entry is odd
        jz .even
        shr ax, 4               ; extract the high bits
        ret    
    .even:
        and ax, 0x0FFF          ; extract the low bits
        ret

EDIT: There seems to be a problem with the code, in that it extracts the wrong value. Clearly this is something I need to work on some more.

[sleephacker]

At the risk of becoming tedious, I have a question regarding the wiki page on FAT, specifically the section about computing the location of a FAT entry.

The code example given say,

Code: Select all

unsigned char FAT_table[sector_size];
unsigned int fat_offset = active_cluster + (active_cluster / 2);// multiply by 1.5
unsigned int fat_sector = first_fat_sector + (fat_offset / section_size);
unsigned int ent_offset = fat_offset % section_size;

I am assuming that the two references to 'section_size' are actually supposed to be sector_size, correct? Should I correct this, or is this in fact supposed to be 'section_size' and the code is incomplete for some reason?

TBH I don't really get what the code on the wiki is trying to do, but I do know it's incorrect. EDIT: nvm, I figured it out. It calculates which sector of the FAT to load and where within in that sector it needs to read the 1.5-byte entry. But even then there is an edge case where an entry is split across two sectors, so it's still bugged. Besides, the FAT is so small that it makes more sense to just load the whole thing into memory during initialisation.

The FAT is only about cluster numbers, calculating the next one doesn't depend on how large a sector is or how many sectors are in a cluster. To get the next cluster number for cluster number N you just read from index N in the FAT (if you view it as an array of 1.5-byte values).
Something along the lines of this (assuming you have loaded the entire FAT somewhere in memory):

Code: Select all

address_of_FAT_entry = address_of_FAT + (current_cluster + currect_cluster / 2)

Then you load the word at address_of_FAT_entry and handle even / odd entries the way you're already doing.

You only need to know the size of clusters/sectors (along with a few other things) once you want to translate your cluster numbers to sector numbers. This page has some useful formulas at the bottom, under Calculation Algorithms.

[Schol-R-LEA]

One thing this helps with is that I am indeed reading the entire FAT into memory ahead of time. While this is a Bad Idea if reading FAT16 or FAT32, it is workable for FAT12.

Now, my current code is

Code: Select all

extract_next_fat12_entry:
;; address_of_FAT_entry = fat_buffer + (current_cluster + current_cluster / 2)
        mov ax, bx              ; BX == current cluster
        shr ax, 1               ;  current_cluster / 2
        add ax, bx              ; (current_cluster + current_cluster / 2) == FAT entry offset
        add di, ax              ; index fat buffer by offset
        mov ax, [di]            ; get the indexed entry
        test bx, 1              ; check if the existing entry is odd
        jz .even
    .odd:
        shr ax, lo_nibble_shift ; extract the high bits
        ret
    .even:
        and ax, hi_nibble_mask  ; extract the low bits
        ret

My test code, using entry values which should all be valid in my test FAT, is

Code: Select all

        mov bx, 0
    .test_loop:
        mov di, fat_mockup
        call extract_next_fat12_entry
        call print_hex_word
        write nl
        inc bx
        cmp bx, 5
        jl .test_loop

In my test code I use a mocked-up truncated FAT, defined as

Code: Select all

fat_mockup          db 0xF0, 0xFF, 0xFF, 0x00, 0xF0, 0xFF, 0x00, 0x00, 0x00

This is based on the actual FAT on my test disk, which contains a single-sector STAGE2.BIN file added by mounting the disk and copying the file to it. See Wikipedia's example FAT12 cluster map to compare this to.

The resulting values are extracted

Code: Select all

0FF0    - the FAT ID
0FFF    - end of chain, in this case the reserved sectors
0000    - unused entry; this should be an end of chain for the STAGE2.SYS file, instead
0FFF    - end of chain
0FFF    - end of chain, should be an unused entry

Which compares to the values I actually present in the

As far as I can tell, the entries should instead be (as words, to match what is returned by the code):

Code: Select all

0FF0   - the  FAT ID, always this value
0FFF   - the reserved sector, always this value
0F00   - end of chain, for the single sector file
0FF0   - end of used FAT entries
0000   - unused entry

So it isn't quite right still.
The attached screenshot is of the hexl-mode view of the relevant parts of the disk image, with the first five FAT entries highlighted.

[Octocontrabass]

One thing this helps with is that I am indeed reading the entire FAT into memory ahead of time. While this is a Bad Idea if reading FAT16 or FAT32, it is workable for FAT12.

It's still possible with FAT16, since the FAT can't be bigger than 128kiB.

Your mockup FAT decodes to these values:

Code: Select all

0xFF0 - media type (cluster 0 doesn't exist)
0xFFF - end of chain (cluster 1 doesn't exist)
0x000 - free cluster
0xFFF - end of chain (probably stage2.sys)
0x000 - free cluster
0x000 - free cluster

I'm not sure why your code isn't returning these exact values, unless the FAT you're testing it with doesn't match what you've posted.

[Schol-R-LEA]

I think I have that last issue beaten, but now I am trying to figure out why my latest test is failing in the build - not because of a problem with the code, but rather with a part of the Makefile which temporarily mounts the built disk image to allow it to copy the second stage code into the disk image's file system.

The specific error message is:

Code: Select all

sudo mount -t vfat boot.img temp

mount: /home/schol-r-lea/Documents/Programming/Projects/Verbum/src/PC-x86/nasm/fat12/tests/fat_to_file_test/temp: wrong fs type, bad option, bad superblock on /dev/loop0, missing codepage or helper program, or other error.

Now, just to be clear here, I use the an almost identical Makefile and process for both the other test programs and the main boot loader itself, and it always mounts the boot.img file correctly. I've tried to move the directory to a shorter path location, and got the same result, so it isn't due to the path limit (not that this was anywhere close to it in the first place). I've also checked the sizes of both the boot sector binary and the resulting image file, and they are both what they ought to be. I am uncertain why this particular test program is acting different from the others.

I've pushed the code as it exists to my Github repo, but right now I am pretty much stuck as to where to take this next.

[Octocontrabass]

Is there any more information in dmesg?

[Schol-R-LEA]

Is there any more information in dmesg?

OK, apparently there is.

Code: Select all

[661360.179954] loop0: detected capacity change from 2880 to 0
[661360.194688] FAT-fs (loop0): invalid media value (0x8e)
[661360.194692] FAT-fs (loop0): Can't find a valid FAT filesystem

So it seems that the file is indeed getting corrupted somehow, though just how isn't clear yet. The first line seems to indicate that the file is truncated somehow (from 2880 blocks to 0), though the file itself is the expect 1.44MiB.

For the record, the Makefile I am using is

Code: Select all

ASM = nasm -w+all -f bin
COPY = dd
FORMAT = mkfs.msdos -F 12 -n "VERBUM"
REIMAGE=qemu-img
SYS_INSTALL = ~/Deployments/ms-sys-2.5.3/bin/ms-sys --fat12
BOOT = fat_to_file_test
STAGE_TWO = stagetwo
DISKTARGET = boot.img
DISKSIZE = 1440

install: boot stage2
	$(COPY) if=/dev/zero of=$(DISKTARGET) count=$(DISKSIZE) bs=1k
	$(FORMAT) $(DISKTARGET)
	$(COPY) if=$(BOOT).bin of=$(DISKTARGET) count=1 conv=notrunc
	mkdir temp
	sudo mount -t vfat $(DISKTARGET) temp
	sudo cp $(STAGE_TWO).bin temp/STAGE2.BIN
	sudo umount temp
	rmdir temp
	$(REIMAGE) convert -f raw -O qcow2 boot.img boot.qcow2

boot:
	$(ASM) $(BOOT).asm -o $(BOOT).bin -l $(BOOT).lst

stage2:
	$(ASM) $(STAGE_TWO).asm -o $(STAGE_TWO).bin -l $(STAGE_TWO).lst

This differs from the ones for the other test programs and the boot loader in only one respect: the value of $(BOOT). Since fat_to_file_test.bin is freshly generated each time the Makefile runs, the difference somehow has to be in fat_to_file_test.asm.

And in fact there was an obvious problem with it: at some point, I accidentally deleted the BPB section of the boot loader, which was easily corrected. It now mounts. How I managed this, and how I didn't think to look for it before, is just carelessness on my own part.

[bzt]

So it seems that the file is indeed getting corrupted somehow, though just how isn't clear yet.

BootProg has a simple FAT12 image creator, maybe you should use that code (it also has the benefit not needing sudo). But my guess is same as yours, there must be something wrong with "$(BOOT).bin", this line in particular

Code: Select all

$(COPY) if=$(BOOT).bin of=$(DISKTARGET) count=1 conv=notrunc

Surely overwrites the BPB created by mkfs.msdos.
Maybe try:

Code: Select all

$(COPY) if=$(BOOT).bin of=$(DISKTARGET) conv=notrunc bs=1 count=3
$(COPY) if=$(BOOT).bin of=$(DISKTARGET) conv=notrunc bs=1 count=450 skip=62 seek=62

This won't change bytes 4-61, only the jump at the beginning and the code area after the BPB. (Check the offsets, I've just written them from memory.)

Cheers,
bzt

[Schol-R-LEA]

I am going to try the same trick I used to test the LBA-to-CHS code, namely separating the code for reading in the FAT and Root Directory and the entry seeking code into separate functions in their own include files. This will let me test each of them in isolation, and see where the problem lies. It is possible that just the act of isolating them will make a difference, by removing hidden dependencies, though doing so will put more space pressure on the final boot code.

EDIT: It seems to have worked, much to my surprise. However, the space crunch is getting serious now, so I will have to find ways to trim the code.

Either I was wrong about it working, or I've had a regression; either way, I am just short of giving up. My current code for this particular routine is

Code: Select all

;;; seek_directory_entry - seek the directory for the stage 2 file
;;; Inputs:
;;;       SI - address of the filename to match against
;;;       DI - directory buffer
;;;       CX - max. number of entries
;;;       BX - size of an entry
;;; Outputs:
;;;       DI - location of the entry
seek_directory_entry:
        mov dx, bx
    .dir_entry_test:
        push di
        push si
        push cx
        mov cx, filename_length
        repe cmpsb              ; does the directory entry match?
        je .entry_found
        pop cx
        pop si
        pop di
        add di, dx
        add dx, bx 
        loop .dir_entry_test
        mov di, 0               ; if not found, return 0
    .entry_found:
        ret

I'm going to go through the earlier check-ins on Git to see if I can pinpoint a regression, otherwise I will have to conclude that I was misinterpreting my earlier results. I suspect it was the latter, sadly.

EDIT: It looks as if it wasn't working in the first place. I'm about ready to give up on this project, TBH.

[Octocontrabass]

Code: Select all

        mov dx, bx
        [...]
        add di, dx
        add dx, bx

Instead of reading directory on each iteration, you're reading directory[i*(i+1)/2]. I'd get rid of DX and add BX to DI.

You also jump to the RET instruction without popping the values you've pushed.