In the previous parts of this guide, we wrote assembly code for a simple boot sector and set up the GNU toolchain we use for compiling it and writing it to a floppy disk image. We then used the Bochs IA-32 emulator to boot from that image and see it run.

Our current boot loader resets the drive system, writes a “loading” messages to the screen, waits for a keypress and reboots. It’s now time to make it do what it’s supposed to do: find our kernel file on the disk, so it can be loaded into memory and run.

This article is part of a series on toy operating system development.

View the series index

Reading from disk

Before we get into how to find a file, we need to get some basics sorted first: we need some way to actually read data from our disk. Reading from a disk is done through calling BIOS interrupts (built-in functions that come with the BIOS of any computer). We’ll require interrupt 0x13, subfunction 2. Its arguments are these:

RegisterValue
alNumber of sectors to read
ahSubfunction 2
chLow 8 bits of cylinder
clHigh 2 bits of cylinder, 6 bits for sector
dhHead number
dlDrive number
es:bxData buffer

The interrupt tries to read one or more sectors from disk, and sets the carry flag if it fails. Failures are common, and read operations should always be tried several times before giving up.

Logical Block Addressing (LBA)

Did you notice the track and head parameters? So far we’ve been talking about sectors only. In facts, we’ve assumed that a disk is simply a long sequential list of sectors. That would be nice, but reality is not nice in this case. We’ve been thinking in terms of what is known as Logical Block Addressing (LBA), while actual disks work differently. Disks can actually have multiple sides that are read by multiple reading heads. Also, sectors are grouped in tracks or cylinders (like on a vinyl record) which further complicates matters. However, the math required to convert an LBA number to a head, cylinder and sector combination is this:

Sector   = (LBA mod SectorsPerTrack) + 1
Cylinder = (LBA / SectorsPerTrack) / NumHeads
Head     = (LBA / SectorsPerTrack) mod NumHeads

What we need to do, then, is write a function that converts an LBA number into these low-level values, reads a sector, and gives it back. That way, the rest of our code can focus on thinking in terms of logical block addresses which avoids headaches.

Read sector code

Here is the code that reads a logical sector from disk:

# buffer at ES:BX. This function uses interrupt 13h, subfunction ah=2.
.func ReadSector
ReadSector:
  xor     cx, cx                      # Set try count = 0
 
 readsect:
  push    ax                          # Store logical block
  push    cx                          # Store try number
  push    bx                          # Store data buffer offset
 
  # Calculate cylinder, head and sector:
  # Cylinder = (LBA / SectorsPerTrack) / NumHeads
  # Sector   = (LBA mod SectorsPerTrack) + 1
  # Head     = (LBA / SectorsPerTrack) mod NumHeads
 
  mov     bx, iTrackSect              # Get sectors per track
  xor     dx, dx
  div     bx                          # Divide (dx:ax/bx to ax,dx)
                                      # Quotient (ax) =  LBA / SectorsPerTrack
                                      # Remainder (dx) = LBA mod SectorsPerTrack
  inc     dx                          # Add 1 to remainder, since sector
  mov     cl, dl                      # Store result in cl for int 13h call.
 
  mov     bx, iHeadCnt                # Get number of heads
  xor     dx, dx
  div     bx                          # Divide (dx:ax/bx to ax,dx)
                                      # Quotient (ax) = Cylinder
                                      # Remainder (dx) = head
  mov     ch, al                      # ch = cylinder                      
  xchg    dl, dh                      # dh = head number
 
  # Call interrupt 0x13, subfunction 2 to actually
  # read the sector.
  # al = number of sectors
  # ah = subfunction 2
  # cx = sector number
  # dh = head number
  # dl = drive number
  # es:bx = data buffer
  # If it fails, the carry flag will be set.
  mov     ax, 0x0201                  # Subfunction 2, read 1 sector
  mov     dl, iBootDrive              # from this drive
  pop     bx                          # Restore data buffer offset.
  int     0x13
  jc      readfail
 
  # On success, return to caller.
  pop     cx                          # Discard try number
  pop     ax                          # Get logical block from stack
  ret
 
  # The read has failed.
  # We will retry four times total, then jump to boot failure.
 readfail:   
  pop     cx                          # Get try number             
  inc     cx                          # Next try
  cmp     cx, word ptr 4              # Stop at 4 tries
  je      bootFailure
 
  # Reset the disk system:
  xor     ax, ax
  int     0x13
 
  # Get logical block from stack and retry.
  pop     ax
  jmp     readsect
.endfunc

This code will attempt to read the sector with LBA specified in AX up to four times before giving up and jumping to bootFailure. After each failed read attempt, the disk system is reset. Most of the code focuses on doing the divisions required to get the values needed by the interrupt call. If all goes well, the sector’s 512 bytes are placed in ES:BX.

As a side note, we’re actually lucky to have interrupt 0x13 at this stage. Once we’ve put our processor in protected mode, we won’t have access to the BIOS anymore (all its code only runs in 16-bit real mode) and we’ll have to access the disk drive ourselves which is very tricky.

Introduction to FAT

There are many file systems in use these days (NTFS, ext, BFS, UFS, etc.) and we need to pick one to use for our bootable disk. FAT (“File Allocation Table”) is not the most advanced system available, but it’s simple, and on Windows we have the tools to format a disk with it. Plus, rawrite and ImageFS understand it. At a later stage in the development of a toy OS, you can implement support for bags of other file systems if you want.

There is no actual requirement to use any file system. A (floppy) disk is just a bag of bytes, grouped in sectors, clusters and tracks (we’ll get to that), that you can read from and write to. The BIOS expects the first sector of a bootable to disk to be a boot sector, but that’s the only requirement. However, at some point we’ll want to store files and it’s a good idea to pick a file system now, so FAT it is.

FAT comes in different flavors. There’s FAT12, FAT16 and FAT32. The difference is in the size of the disk supported. For FAT12, references to sectors on disk can be up to 12 bits (a maximum value of 4,096 sectors), while with FAT32 we can point to 4,294,967,296 sectors. Since we’re working with floppy disks, FAT12 is enough. The discussion below applies to all FAT versions.

The basic structure of a 720 KB floppy disk formatted with FAT is this:

RegionSize
Boot sector1
File allocation table (FAT)18
Root directory14
Data area1407

A 720 KB floppy disk contains 1440 512-byte sectors, some of which are reserved as shown. The remaining 1,407 sectors contain the data of our files.

The boot sector

Here is a quick refresher of the layout of the boot sector (see also the first part of this guide).

OffsetSizeSectionContentsTypical value
00003CodeJump to rest of code 
00038BPBOEM nameGreat-OS
00112 Bytes per sector512
00131 Number of sectors per cluster1
00142 Number of reserved sectors1
00161 Number of FAT tables2
00172 Number of root directory entries (usually 224)224
00192 Total number of sectors2880
00211 Media descriptor0xf0
00222 Number of sectors per FAT9
00242 Number of sectors/track9
00262 Number of heads2
00282 Number of hidden sectors0
00302EBPBNumber of hidden sectors (high word)0
00324 Total number of sectors in filesystem 
00361 Logical drive number0
00371 Reserved 
00381 Extended signature0x29
00394 Serial number 
004311 Volume labelMYVOLUME
00548 Filesystem typeFAT16
0062448CodeBoot code 
05102RequiredBoot signature0xaa55

I’ve filled this table with the values you would typically get for a 720 KB floppy disk formatted with FAT. The values in the boot sector are used to determine where exactly on the disk the FAT tables and the root directory live.

The root directory

In order to find a file on the disk, we need to start by looking at the root directory. This is a list of up to 224 entries (according to the boot sector) of 32 bytes each. Each entry contains data about a file:

OffsetSizeDescription
0x008File name
0x083File extension
0x0b1Attribute
0x0c1Reserved
0x0d1Creation timestamp
0x0e2Creation time
0x102Creation date
0x122Last access date
0x142Reserved
0x162Last modified time
0x182Last modified date
0x1a2Cluster
0x1c4File size (bytes)

So the root directory is a list of files on disk. In order to find our kernel file, all we need to do is read it and look for the kernel filename (“KERNEL.BIN” would be good). The directory entry then tells us in which cluster the file resides.

Finding a file on disk

The original boot sector code for DOS and Windows 95 required that the OS kernel file (IO.SYS) be the first file in the root directory of the boot disk. This allowed the programmer to write less code: he did not have to scan the disk’s root directory looking for the file but could simply assume that the file would reside at a fixed position. We can do better, though, by actually scanning the root directory to find our file – and you will see that it’s still possible to squeeze all required code in the 448 bytes that we’re allowed to use.

In order to find a file, we need to take the following steps:

  • Prepare a memory area to load sectors of the root directory into (one sector at a time will do)
  • Calculate the size of the root directory in sectors
  • Figure out where the root directory starts on disk (see above)
  • For each sector:
    • Read the sector into memory
    • Scan it to see if it contains the filename we’re looking for
    • If found, calculate its starting sector and file size
  • If not found, the boot process fails

Root directory size

The size of the root directory in sectors is the number of entries it contains, times 32 bytes:

# The number of sectors that the root directory occupies
# is equal to its max number of entries, times 32 bytes per
# entry, divided by sector size.
# E.g. (32 * rootsize) / 512
# This normally yields 14 sectors on a FAT12 disk.
# We calculate this total, then store it in cx for later use in a loop.
mov     ax, 32
xor     dx, dx
mul     word ptr iRootSize
div     word ptr iSectSize          # Divide (dx:ax,sectsize) to (ax,dx)
mov     cx, ax
mov     root_scts, cx
# root_scts is now the number of sectors in the root directory.

Root directory start

To get started, we’ll first need to know where the root directory begins. The information we need is in the boot sector, where the following values are important:

  • Number of FAT tables (2)
  • Number of sectors per FAT (9)
  • Number of reserved sectors (1)
  • Number of hidden sectors (0)

The root directory comes after and reserved or hidden sectors and the file allocation table (FAT). The starting cluster of the root directory is therefore:

root_sector = (FAT tables) * (#sectors per FAT)
            + (reserved sectors)
            + (hidden sectors)

The one reserved sector is of, course, the boot sector. There are no hidden sectors on our disk.

# Calculate start sector root directory:
# root_strt = number of FAT tables * sectors per FAT
#           + number of hidden sectors
#           + number of reserved sectors
xor   ax, ax                      # find the root directory
mov   al, byte ptr iFatCnt        # ax = number of FAT tables
mov   bx, word ptr iFatSize       # bx = sectors per FAT
mul   bx                          # ax = #FATS * sectors per FAT
add   ax, word ptr iHiddenSect    # Add hidden sectors to ax
adc   ax, word ptr iHiddenSect+2
add   ax, word ptr iResSect       # Add reserved sectors to ax
mov   root_strt, ax
# root_strt is now the number of the first root sector

Reading and scanning each sector

We can now use the ReadSector function we developed earlier to read the sectors into memory, one by one. For each sector, we then loop through the entries and check each filename (the first 11 bytes of the directory entry) for a match:

	
# Load a sector from the root directory.
# If sector reading fails, a reboot will occur.
read_next_sector:
push   cx
push   ax
xor    bx, bx
call   ReadSector
 
check_entry:
mov    cx, 11                      # Directory entries filenames are 11 bytes.
mov    di, bx                      # es:di = Directory entry address
lea    si, filename                # ds:si = Address of filename we are looking for.
repz   cmpsb                       # Compare filename to memory.
je     found_file                  # If found, jump away.
add    bx, word ptr 32             # Move to next entry. Entries are 32 bytes.
cmp    bx, word ptr iSectSize      # Have we moved out of the sector yet?
jne    check_entry                 # If not, try next directory entry.
 
pop    ax
inc    ax                          # check next sector when we loop again
pop    cx
loopnz read_next_sector            # loop until either found or not
jmp    bootFailure                 # could not find file: abort

Getting the file start position

Now that we have found the root directory entry for the kernel file, we need to get from it the position of the file (the cluster number):

  found_file:
    # The directory entry stores the first cluster number of the file
    # at byte 26 (0x1a). BX is still pointing to the address of the start
    # of the directory entry, so we will go from there.
    # Read cluster number from memory:
    mov    ax, es:[bx+0x1a]
    mov    file_strt, ax

The end result is that file_strt contains the file’s starting cluster number.

FAT Clusters

All right, after all this digging through the disk’s root directory, we’ve found our file and we’ve got a cluster number in hand. However, so far we’ve only talked about sectors, not clusters (you can safely ignore the cylinder, track and head story from here on – they have nothing to do with it). A cluster is another logical structure introduced by FAT.

The idea is that in FAT, a file may occupy a number of sectors. And most files certainly will, because one sector is only 512 bytes. Files on disk will often be much larger than that! So imagine that we have a disk with two of files on it. They’re both 3 sectors in size, and they were physically written to the disk so as to occupy precisely the first 6 sectors of the data area. Now, the first file is deleted. That means we now have 3 empty sectors at the start of the data area. Next, a new file, 4 sectors in size, is copied onto the disk. Where does it go? There’s no space to put new file before the remaining existing file, since there’s only space for 3 sectors. We can only place the new file after the existing file. Maybe at some point a user will want to write a 3-sector file that can fill the gap!

Naturally, if you consider writing and deleting lots of files on a disk, this will leave the file system fragmented and with lots of gaps that we can’t use. And this is where FAT comes in. With FAT, a file that occupies multiple sectors on disk may be broken up into non-contiguous sectors. So a 3-sector file could occupy physical sectors 40, 21 and 304. The bits and pieces can go wherever there is space and all available space is used to the fullest.

The problem then is administration. How does FAT know where the loose pieces of each file are? For this, the FAT system uses its namesake, the File Allocation Table. This table lives right before the root directory and contains an index of all the sectors on the disk. There are actually two copies of the FAT on every disk: one is a backup, for safety. You’ll see that the bootsector actually contains a field with the number of FAT tables on the disk.

The FAT table is actually an index of linked lists of sectors (hello?). An example illustrates how this works. Imagine we have a disk with 10 data sectors on it (we’re ignoring the sectors occupied by boot sector, root directory, FAT etc., and the fact that 10 sectors is a really small disk):

SectorFAT-Value
00x001
10x004
20xFF8
30x007
40x006
50x000
60xFF8
70xFF8
80x000
90xFF7

There are actually three files on this disk. From the root directory we get:

  • File 1 – cluster index = 0
  • File 2 – cluster index = 2
  • File 3 – cluster index = 3

The directory entry for file 1 points to cluster index 0. In the FAT table, the value for this index is 0x001: it points to index 1. Index 1’s value is 0x004: it points to index 4. Index 4’s value is 0x006: is points to index 6. Index 6’s value, finally, is 0xff8, a special value which means that it is the last index of the file.

What this all means is that file 1 occupies sectors 0, 1, 4 and 6. Actually, sector 0 is the sector after the root directory on the disk, but that’s a detail.

For file 2 we can now determine that it occupies only one sector (sector 2). The FAT-value for this index is 0xff8, so there are no more sectors.

For file 3, we see that it occupies sectors 3 and 7. You’ll get the idea by now.

  • Some of the FAT indices have the value 0. That means that the sector is free.
  • Any value of 0xff8 or higher means end-of-file
  • A value of 0xff7 means the sector is bad and should not be used.

A cluster, therefore, is a linked list where each entry points to the next, until the end of the cluster. Each entry relates to an actual physical sector on disk. When reading a file, we’ll have to follow its FAT cluster and read each corresponding sector into memory.

It sounds simple enough, after all, but there’s a catch: the FAT entries occupy 12 bits each (a byte and a half), which will make reading and using the data bit tricky later. You will now see that since each the FAT consists of 9 sectors, it can address 9*512/1.5 = 3072 sectors, which is more than enough, since our disk has 1440 sectors.

Reading the FAT

The FAT lives on the disk, and in order to access it, we’ll have to get it in memory first. The following code does just that: it loads the FAT into a memory segment (I use segment 0x0ee0, so as to place it just under where I’ll be loading the next file):

# The FAT will be loaded in a special segment.
# Set ES to this segment.
mov   ax, fatsegment
mov   es, ax
 
# Calculate offset of FAT:
mov   ax, word ptr iResSect       # Add reserved sectors to ax
add   ax, word ptr iHiddenSect    # Add hidden sectors to ax
adc   ax, word ptr iHiddenSect+2
 
# Read all FAT sectors into memory:
mov   cx, word ptr iFatSize       # Number of sectors in FAT
xor   bx, bx                      # Memory offset to read into (es:bx)
read_next_fat_sector:
push  cx
push  ax
call  ReadSector
pop   ax
pop   cx
inc   ax
add   bx, word ptr iSectSize
loopnz read_next_fat_sector       # continue with next sector

After this code has executed, all 9 sectors of the FAT now live in memory at 0ee0:0000.

Reading a file

Without FAT in memory, we are not ready to read a file from disk. By scanning the root directory we had earlier determined the starting index in the FAT table, so we’re good to go:

# Set memory segment that will receive the file:
mov     ax, loadsegment
mov     es, ax
# Set memory offset for loading to 0.
xor     bx, bx
 
# Set memory segment for FAT:
mov     cx, file_strt             # CX now points to first FAT entry of file
 
read_file_next_sector:
# Locate sector:
mov     ax, cx                    # Sector to read is equal to current FAT entry
add     ax, root_strt             # Plus the start of the root directory
add     ax, root_scts             # Plus the size of the root directory
sub     ax, 2                     # ... but minus 2
 
# Read sector:
push    cx                        # Read a sector from disk, but save CX
call    ReadSector                # as it contains our FAT entry
pop     cx
add     bx, iSectSize             # Move memory pointer to next section
 
# Get next sector from FAT:
push    ds                        # Make DS:SI point to FAT table
mov     dx, fatsegment            # in memory.
mov     ds, dx
 
mov     si, cx                    # Make SI point to the current FAT entry
mov     dx, cx                    # (offset is entry value * 1.5 bytes)
shr     dx
add     si, dx
 
mov     dx, ds:[si]               # Read the FAT entry from memory
test    cx, 1                     # See which way to shift, see if current cluster if odd
jnz     read_next_cluster_odd    
and     dx, 0x0fff                # if not mask out upper 4 bits
jmp     read_next_file_cluster_done
read_next_cluster_odd:            # if it is odd shift the new cluster 4 to right
shr     dx, 4
read_next_file_cluster_done:     
pop     ds                        # Restore DS to the normal data segment
mov     cx, dx                    # Store the new FAT entry in CX
cmp     cx, 0xff8                 # If the FAT entry is greater or equal
jl      read_file_next_sector     # to 0xff8, then we have reached end-of-file

What happens here is that we start with cx = first sector of file (we know this from the root directory after all). We read that sector into memory, then use the cx value to access the corresponding index in the FAT. There’s a bit of trickiness where we juggle with the 12-bits issue, but then all that remains is whether to continue reading, or stop because end-of-file (FAT-entry 0xff8 or higher) was reached.

Summary

From a bare-bones boot loader, we’ve now come to a point where we can load the kernel (or rather the second-stage boot loader – this will become clear later on)! We’ve seen how the root directory and FAT work, and neatly read both to load the required file from disk. Since we squeezed all this functionality in, the file we’re loading can actually live anywhere in the root of the disk. Gone is the requirement for SYS.COM that DOS and Windows imposed. In our future OS, making a disk bootable should not require a formatting operation. Writing a boot sector and simply coping the OS files onto the disk will suffice.

So far I’ve shown here some sections of code that still need to be sewn together. In the next part of this guide, we’ll add a small kernel (something along the lines of “hello world”) to be loaded and executed. We’ll then have a complete source that can be compiled and run on Bochs (or from a floppy disk if you’re hardcore).

Continue on to the next part of this guide!