Learn read before you write

In this post, I write about my learning experience to acquire the minimum competencies to build my bootloader the space shuttle. I try to understand how INT 13H and Logical block addressing (LBA) work. I figure out which relationship links the master boot record (MBR), the BIOS parameter block (BPB) and the file allocation table (FAT16).

Learn read before you write. It sounds logic. This is what elementary school teachers teach. So I realize that what I did until now was just learning to speak in the "kindergarten" and now I just got on the first day of the elementary school of informatics. Ok so let's start to learn reading. As usual, you have to do your part of the homework since we have to do this together. I found a good source of info at the Ralf Brown Interrupt List and at the OsDev.org website. The BIOS function that reads the disk is INT 13H (0x13 in hexadecimal so it is the 19th in decimal). It comes in some different implementation forms depending on the date of the BIOS and the BIOS manufacturers. The main reason for the differences in the INT 13H function is historical. This function has been originally developed to command floppy disk drives so it implemented a CHS logic. CHS stands for Cylinder Head and Sector of the surface of a disk drive. This logic made a lot of sense for a floppy drive but it didn't with HDD. The problem isn't technical but human. We are afraid of change. Rather than implement a new BIOS function for the HDD that could have lived side by side with the floppy disk one, the decision was to keep using the INT 13H, so the way people handled HDD in the first place was counting cylinders, heads and sectors as if it was a floppy drive. Since the size of the HDD was much bigger then the floppy disk, the CHS for HDD was a conventional virtual way of counting blocks rather than a real description of the physical position of the block on the surface of the disk. Besides, CHS has an upper limit of blocks that can be counted in this way which limits the maximum HDD size to approximately 8,4 GB. Once this limit was reached the development of the INT 13H function branched to follow a new addressing technique which is now called LBA (Logical Block Address). At the same time, INT 13H was still keeping the CHS technique alive to assure backwards compatibility with old software. So once I was aware of all this I decided that I have to check which INT 13H capability was available for the BIOS of my IBM T41 before attempting to read a block from the disk. To be honest, I doubt that my BIOS only supports CHS without LBA since the HDD size that I have is bigger than 8,4 GB, but it is technically possible that the BIOS has only a CHS implementation, and that the bootloader loads an LBA-Driver from the HDD onto RAM which in turns can work with LBA beyond the 8,4GB boundary, the only limitation being that this LBA-Driver must be physically located before the 8,4 GB region of the HDD where the CHS algorithm can still reach it. Even if the probability of such event is almost zero, I decided to verify it and run the INT 13H extension installation check anyway. In this post, I report the experience I did with it.

First of all, I had a look at the MBR (the absolute first block of the HDD, the block 0) of my HDD with the use of the dd command in Ubuntu, and then I converted it into a text file to be opened and analyzed¹:
dd if=/dev/sda of=/home/mik/Desktop/sda.bin bs=512 count=1
hexdump -C -v sda.bin > sda.txt

In Fig. A you see it. This is a mix of GRUB executable code and data. Towards the end, we see the partition table (pink colour) and the boot signature (in yellow).

Fig. A - Master Boot Record of HDD.

In Fig. B I could recognize the 4 standard partitions of a partition table (alternating colours pink and white).

Fig. B - MBR of HDD with focus on the partition table.

In Fig. C I organized the details of each partition of the partition table (you can find all the details concerning "Understanding Partitions and Partition Tables" at the The Starman's Realm).

Fig. C - MBR of HDD with details of the partition table.

I notice that the end of partition one was beyond the 8,4 GB limits and that the CHS value for it is at its conventional boundary 0xFF FF EF (remember it is little-endian). From here on all other partition start and end values in CHS are meaningless. The beginning of the second partition in LBA addressing mode is equal to the LBA-beginning plus the LBA-size of the first partition (0x02 32 7A 21 + 0x3F = 0x02 32 7A 60). All these are indicators that with the highest probability my BIOS implements the LBA reading function. Nonetheless, I want to write a small module to test it. Since I will test a BIOS function for reading/writing the HDD, I want to keep the BPB (BIOS Parameter Block) in its original form. The point is that even if I know which kind of information is stored in the BPB I don't know which software is using them. I am not sure if it is already the BIOS or only the Microsoft-OS. The name suggests that this block can be somehow related to BIOS. Probably during reading and writing the HDD the BIOS function INT 13H retrieves some information about the disk and the current partition which are saved in the BPB. Another reason to preserve the BPB is that I want to access the test drive D:\ also from the XP and UBUNTU (in the case of Alien-planet Landing-module and Alien planet probe the OS wasn't detecting the disk anymore because I wasn't preserving the BPB).

In Fig. D you see the Boot Record² of the Test partition D:\. This is the original Boot Record before I did the modules Alien-planet Landing-module and Alien planet probe. You can notice the string starting at address 0x1AE and compare them with Fig. AB of post "Set up the test rig". I have roughly separated the bytes in groups: the green one belongs somehow to the code area (including the data that the code uses such as the strings); the pink one is the BIOS Parameter Block and at the end, in yellow, there is the boot signature.

$Boot Record of the TEST partition D:\$

Fig. D - Boot Record of the TEST partition D:\.

The first three bytes are a jump instruction to jump over the BIOS Parameter Block. The point is that as long as the BPB is smaller or equal to 126 bytes one can jump over it with a "short jump" that is made of one byte of opcode (0xEB) plus one byte of IP-increment (the maximum positive value of a single byte signed integer is 0x7F=127³). If the BIOS Parameter Block (BPB) is bigger than that one has to jump over the BPB with a "near jump" which needs two bytes of IP-increment. For this reason, the first three bytes belong together to the code section: they can be either a "short" jump (coded with 2 bytes) or a "near" jump (coded with 0xE9 plus two bytes of increment). In the case of Fig. D we have a "short" jump so the third byte at memory address 0x02 is a NOP⁴.

In Fig. E you see the details of the BPB. I want to comment on the bytes at address 0x01C. In the documentation that I found on the internet⁵, it is mentioned that this is the number of the hidden blocks with the comment "The use of this is largely historical, and is nearly set to 0". Then I put three question marks "???" because in my BPB there was there a very large number. But what did it mean? I realized it is exactly as big as the LBA start of partition two (see Fig. C) so it cannot be a coincidence. I suppose at this stage that this is the way to hide any partition physically on disk before this one.

$BIOS Parameter Block of the TEST partition D:\$

Fig. E - BPB of the TEST partition D:\

At offset 0x027 there is the volume serial number 0x40 65 3B DA. You can compare this with Fig. Z of post "Set up the test rig" and you will start to make sense of it as I did. The only thing I found strange at this time is the volume label at offset 0x02B which is "NO NAME ", meanwhile I know that I changed it to be "TEST". So why isn't it written here? But (maybe even more mysterious) how does the OS know instead that the label name is "TEST" and displays it correctly on the screen? Where is this information saved? I don't know right now. Maybe I will find out.

For the moment I move on to define the code that will test the LBA extensions of the INT 13H. We both know how to do the job with DEBUG.EXE so I will skip all the step-by-step screenshot this time and focus more on the overall preparation and design of the code. In Fig. F you see how the code looks like in memory once loaded at 0x07C 00. Since the beginning of the BPB is a string containing the name of the manufacturer, I thought it will no arm if I take the first two bytes of it for my code in such a way I can place right at the beginning a long jump. In this way, I can reset the CS (so this is a part of the general reset routine at the beginning of the program). For this reason, the bytes at memory address 0x07C 03 and 0x07C 04 are marked with double colour meaning that they are bytes of code (green colour) which are located within BPB space indeed (pink colour).

Fig. F - check INT 13H in binary

So going from memory address 0x07C 00 on we have: the beginning of the general reset routine marked with green; the BIOS Parameter Block marked with pink; the conclusion of the general reset routine marked with green; the test INT 13H routine in yellow; and the remaining of code area are bytes of value 0x90 marked in white. At the bottom of the picture, starting at memory location 0x07D90 we find: the show_string function marked with grey colour (please notice it ends with a 0xC3 byte which is the RET instruction); the "good news string" from address 0x07DA0 to 0x07DB9 marked with light orange; the "bad news string" from address 0x07DC0 to 0x07DDD marked with blue colour; the "exit message" from address 0x07DE0 to 0x07DFA marked with light orange; finally the boot signature marked in yellow.
In Fig. G you can see the assembly code for it. I did it in a different style compared to the one in Chapter II; this time I wrote it in an excel table in such a way it was easier for me to put everything in one picture compared with the screenshots of DEBUG.EXE. As you can see I start with an initial jump over the BPB that resets at the same time the code segments.

Fig. G - check INT 13H in assembly

When you want or need to reset the code segment you have to do it together with the register IP all in once. For this purpose, you have two possibilities: the clean way that issues a long jump command like JMP CS:IP; and the dirty way that loads (pushes) onto stack CS then IP and finally issues a "far" procedure return (0xCB = RET(far)). I don't like this second way of doing the job at all. If someone, rather than the author that has written the code, is reading it, he/she gets confused about the real intention. Reading the code one may find the RET(far) instruction and tries to connect this with a CALL(far) somewhere else in the code finding nothing and then start wondering what's going on. The rest of the general reset is pretty much straight forward (Fig. G), the only thing to notice is that I isolated the CPU from disturbance disabling the interrupt during the reset, and I set the interrupts active again at the end of the reset. The code that does the job of testing the INT 13H needs quite a bit of explanations. The logic is an IF-THEN-ELSE one, but the way I have implemented it is not intuitive at first glance. To explain why I coded it in this why I have to explain the concept of instructions' pipeline.

You can find a lot of material on the internet explaining the instructions' pipeline, even the "INTEL – The 8086 family User's manual" has the explanation of this concept at chapter 2.2 "processor architecture". The 8086 has a BIU (BUS Interface Unit) that fetches from BUS and an EU (Execution Unit) that does the execution job so that while the EU is executing the BIU can fetch the next instruction and keep the pipeline full. CPUs today are much more complex and implements more sophisticated solutions. But I don't want to make here another explanation of these concepts that is similar to what you can find on the internet; I want to give you, instead of, the point of view of a mechanical engineer. So what all this pipeline, staging execution and doing things in parallel inside the CPU is about, is just the so-called "lean production system", also known with the Japanese name of "Kaizen". The classical example used for explanation is the cafe machine (I prefer this explanation because you can immediately see what's going on). The key to understanding this method that you can apply to about everything (the coffee in this case) is to analyse all the steps you need to take to do it. Try to identify wastes and eliminate them (sugar cane and the fridge opening-closing-door sequence to get the milk); identify your core or adding value operation (make the coffee) with the minimum required amount of time to complete it and finally shadow as many operations as possible during this time (fill sugar and milk in the cup, refilling water and cleaning the wasted coffee powder from the machine).
The first youtube video shows you the coffee preparation without the Kaizen optimization and the second video after the optimization.

The internet is full of videos about the lean production system and this is all what this is about. The electronic engineers have identified the value-added operation inside the CPU (= code execution), and they try to shadow as much service operation as possible within this time. For instance, fetching data from the BUS or decoding an OPCODE are service operations that are required for execution. One can try to shadow them inside the time of the execution itself putting processes in parallel. Now all these things happen in a quite automatic way within the CPU. The engineers have designed an architecture that realizes these concepts in an optimized way. A small problem arises when a "conditional jump" code streams in the pipeline of instructions: the stream needs a reset. It is said that the pipeline stalls. But the pipeline stalls if the jump is taken otherwise its opcode stream keeps going to the next instruction and the pipeline doesn't stall. So "conditional jumps" can be bad, and I try to keep their number as low as possible in the code. The point is that the IF-THEN-ELSE logic requires a certain number of jumps, in general, the following schema can be used.

IF-THEN-ELSE general schema:

[...] ############################ #check and jump if true ############################ INT 13 # or put here anything you need for your check JC then_part_of_code: # jump if CF=1 or put here any conditional jump else_part_of_code: ############################## # ELSE branch of the code ############################## MOV SI,0x7d 0a # Point the good news string ... ... JMP end_if: # close the ELSE branch then_part_of_code: ############################## # THEN branch of the code ############################## MOV SI,0x7d c0 # Point the bad news string ... ... # the THEN branch closes by itself since it flows # towards the remaining part of the code ############ # END IF ############ end_if: [...]

It's like a criss-cross jump: either the condition is false and the code flows down in the execution of the ELSE-part of the logic which closes with a jump over the THEN-part of the logic, or the condition is true and the code jumps immediately to the THEN-part of the logic and flows down thru the END-IF-part of the code. This is the general way to realize an IF-THEN-ELSE-logic so that you have to jump causing the pipeline to stall. Since the pipeline stalls, you waste a little bit of execution time. If the time you waste with the pipeline stall is bigger or comparable with the time you need to execute one of the two branches of the IF-THEN-ELSE then you can think the logic differently. Suppose that the ELSE-logic and the THEN-logic are mutually excluding as in our case (either the good news or the bad news) so they overwrite each other. In other terms, if I first point SI with the good news and then it with the bad news the result is that SI is finally pointing to the bad news. Another concept to remember is that the pipeline stalls if and only if we make the jump, so it's worth to consider some probability and place the jump only for the branch of the IF-logic that has a lower probability to occur. Finally, the idea is that most probably the INT 13H extension is supported so if I arrange the code in such a way that it jumps only if it were not supported probably it won't jump at all. So my code looks like the THEN-Logic first to point to the bad news, the check with the conditional jump to jump over the ELSE-Logic (which probably will never occur) and finally the execution of the ELSE-Logic which overwrite the THEN-Logic done in the previous step. So there was a lot of thinking behind the curtains to arrange the code in this way.
However, when the THEN-Logic and/or the ELSE-Logic is quite big you will slow down your code if you execute always both part of the IF-branch just to avoid jumping around. Moreover, you must be sure that the two branches are truly mutually excluding so that the ELSE-Logic is performing a full overwrite of the THEN-Logic otherwise you may have the risk of leaving your CPU after the IF statement with some registers written by the THEN-Logic (that haven't been fully overwritten) and other registers written by the ELSE-Logic. My suggestion is to use the full technique of general schema for IF-THEN-ELSE-Logic since the other is a risky one with just some speed advantage. Regardless my personal opinion and this latest suggestion, I encourage you to make up your mind, consider what is positive and what is negative in this way of coding IF-THEN-ELSE-logic, be critical, and decide for yourself which step to take.

In the end, I put this code in the Boot Record of D:\ and I booted it with GRUB2

Picture of check INT 13H running in real mode

Fig. H - check INT 13H runs in real mode

Search This Blog

From the ground up, my way.

Learn read before you write

Comments

Post a Comment