OSDev.org

The Place to Start for Operating System Developers
It is currently Wed Dec 13, 2017 10:54 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 32 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
 Post subject: Re: General Master Boot Record
PostPosted: Sun Sep 24, 2017 7:14 pm 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 1200
Antti wrote:
Oh no, I'm not that tough. :D If there is a way to significantly improve this, I'm all ears.

I can't take credit for this algorithm; I don't remember where I saw it first.

- Multiply the number of heads by the sectors per track. This is the sectors per cylinder.
- Check to see if the high 16 bits of the LBA are smaller than the sectors per cylinder. If the high 16 bits are greater than or equal to the sectors per cylinder, division will overflow.
- Divide the LBA by the sectors per cylinder. The quotient is the cylinder. The remainder is the sector number relative to the start of the cylinder instead of the start of the disk.
- Divide that remainder by the sectors per track. The quotient is the head. The remainder is one less than the sector. There is no overflow check for this division, since both of these results are guaranteed to fit in 8 bits. (You can use 8-bit DIV instead of 16-bit DIV here.)
- At some point, you still have to make sure the cylinder fits in 10 bits.

If you don't mind reading my painfully optimized version, it starts around line 272 of this file. (Speaking of which, I think I just spotted another optimization...)

Antti wrote:
Are you referring to "and cx, strict word 0x003F"? There was a discussion...

There was a discussion, and no one provided any evidence that these forms of opcode 83 were invalid. Intel's documentation doesn't count because Intel likes to lie about which opcodes are invalid. Discussions elsewhere conclude that they must work on 8086/8088/80286 CPUs because DOS uses them, and DOS certainly works on those CPUs. (Also, the IBM PC demoscene would have noticed by now if NASM didn't work properly. Personally, I'm inclined to trust the guys who spend their free time writing code to run on IBM PC hardware.)


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Mon Sep 25, 2017 12:28 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 877
Location: Finland
I will comment about the algorithm and its implementation in a subsequent post. Thank you for your reply and link to your code.

Octocontrabass wrote:
There was a discussion, and no one provided any evidence that these forms of opcode 83 were invalid.


I'm not defensive about this and I'd be happy to agree with you. The way I "solved the problem" was to stay away from it and no further study was needed. It may become relevant if I really need to save that one extra byte. The current instruction encoding fits well if you look at the big picture, i.e. alignment and general impression that a detail like that is taken into account. It was a decision to use that specific encoding. According to the Intel manual.

Octocontrabass wrote:
Personally, I'm inclined to trust the guys who spend their free time writing code to run on IBM PC hardware.


I'm sure that you did not mean it but does this imply that the above reasoning I wrote makes things less trustworthy?

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Mon Sep 25, 2017 12:49 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8169
Location: At his keyboard!
Antti wrote:
Version 1.1

  • CHS disk access code rewritten. :D

I'd really appreciate comments on this new release. Like a fresh start to this topic.


Some notes:

a1) For modern operating systems; the MBR has to update the TPM chip (get it to do the equivalent of adding a checksum of the boot sector to one of the TPM's registers) - you can find an example of the code for this (from reverse engineered Microsoft MBRs) here. If the MBR doesn't do this, then a malicious attacker can modify the OS's boot loader without being detected.

a2) I think (not entirely sure as there's no official documentation) as part of TPM support the MBR passes "address of partition table entry" in DS:BP and not the traditional DS:SI. If and only if you support TPM then I'd put it in both DS:BP and DS:SI (like you already do); but if you don't support TPM then you should only use DS:SI for "address of partition table entry" (and should not set DS:BP to "address of partition table entry").

b) For performance (including aligning code on natural boundaries), don't waste your time - none of this code is executed frequently (e.g. inside a loop) and the BIOS overhead alone (ignoring disk IO speeds) will be several orders of magnitude slower than the worst code you could possibly write. Instead, optimise for size and nothing else.

c1) I'd have 2 different MBRs (one for 80268 or older and the other for 80386 or newer); and assume that the software that installed the MBR checked if the computer is 80386 or later (or not). This allows you to strip out a lot of "unnecessary for 80286 or older" code (TPM, all LBA, all "int 0x13 extensions") from one of the MBRs; and for the other it allows you to reduce code size (e.g. 32-bit divisions in the "LBA->CHS" conversion routine). I'd also simply not bother writing the "80286 or older" version (let the "MBR installer" issue a "this computer is too old to care about" error instead ;) ).

c2) I'd consider having even more versions of the MBR (with/without TPM, with/without "int 0x13 extensions") and let the installer auto-detect the correct version of MBR to install. Note: An OS's boot loader might gather this information very early during boot and pass it to kernel/OS later in boot; so that an "MBR installer" designed for that OS can know which MBR to install.

d) Some ancient Compaq machines (not sure how ancient) check that the first instruction in the MBR (and in a boot sector for "no partitions" - e.g. floppy) is a near jump or far jump (instead of checking for the 0xAA55 signature at the end), and assume the sector isn't bootable if there's no jump.

e) For checking the partition table; I'd just boot the first partition that is active (without bothering to check any partition table entries after the active partition). This would reduce code size a little, and make it more compatible (some boot managers support multiple active partitions for dual boot purposes).


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Mon Sep 25, 2017 2:43 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 877
Location: Finland
Thank you very much for your comments. I'd like to make the current version stable for purposes it can be used for. I interpret the overall tone being positive. :D

Brendan wrote:
the MBR has to update the TPM chip


I acknowledge this. I was aware of TPM but I did and do not have enough expertise. However, I envisioned that "ReadChs" could be replaced with this logic if writing an alternative version. Implementing this feature here would be too radical for this general MBR. But like you said, there could/should be many versions and this current version is one of them.

Brendan wrote:
if you don't support TPM then you should only use DS:SI


This is an excellent comment and I will add this on the do list. Thanks.

Brendan wrote:
Instead, optimise for size and nothing else.


This will be a recurring theme and I'd never claim I tried to optimize. This MBR consists of pieces that are developed invidually and it is not a coincidence that those happen to be 16-byte aligned chunks. I've spend a way too much time on staring at a debugger and machine code. It was more fun to add some "artistic" touch to this work. If anything, it is very much a designed work and very thoroughly reviewed.

I don't expect anyone to appreciate this but I do hope that the very small disadvantages are not exaggerated. There was no need to maximally pack the instructions in this implementation. This will get negative feedback only for stylistic reasons.

Brendan wrote:
Some ancient Compaq machines (not sure how ancient) check that the first instruction in the MBR (and in a boot sector for "no partitions" - e.g. floppy) is a near jump or far jump (instead of checking for the 0xAA55 signature at the end), and assume the sector isn't bootable if there's no jump.


I'd like to know more about this. I chose the non-jump instruction so that the USB media type heuristics did not think it was a floppy.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Mon Sep 25, 2017 3:02 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 877
Location: Finland
(Hopefully people don't assume my coding is as inaccurate as spelling/grammar above. Even I can see a lot of grammar errors. I'm a bit busy with real life so proof-reading... I'll get back to this later.)

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Mon Sep 25, 2017 3:25 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8169
Location: At his keyboard!
Hi,

Antti wrote:
Brendan wrote:
Some ancient Compaq machines (not sure how ancient) check that the first instruction in the MBR (and in a boot sector for "no partitions" - e.g. floppy) is a near jump or far jump (instead of checking for the 0xAA55 signature at the end), and assume the sector isn't bootable if there's no jump.


I'd like to know more about this. I chose the non-jump instruction so that the USB media type heuristics did not think it was a floppy.


I got a bit curious too - it's something I first heard (and checked) a few decades ago, then forgot where the information came from.

So far I've found a post (from 13 years ago) to the comp.lang.asm.x86 newsgroup by someone trying to figure out why a Compaq machine kept saying their (floppy) boot sector isn't bootable, who found that a "jmp" at the start of the boot sector fixed the problem.

I also found something quite different (only slightly related) suggesting that DOS used "some sort of jump at start of sector" as part of code to determine if a BPB is valid.


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Mon Sep 25, 2017 11:46 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 877
Location: Finland
Version 1.2

  • Redefined MBR to VBR transition state.
  • Signature area is cleared every time a disk read is called.

Thank you for the feedback.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Mon Sep 25, 2017 11:53 am 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 1200
Brendan wrote:
a2) I think (not entirely sure as there's no official documentation) as part of TPM support the MBR passes "address of partition table entry" in DS:BP and not the traditional DS:SI. If and only if you support TPM then I'd put it in both DS:BP and DS:SI (like you already do); but if you don't support TPM then you should only use DS:SI for "address of partition table entry" (and should not set DS:BP to "address of partition table entry").

This is pretty easy to disprove by looking at disassemblies of Microsoft's MBR through the years. MBRs that don't support TPM set both DS:SI and DS:BP, whereas MBRs supporting TPM only set DS:BP. (And either way, the fact that DS:BP points to the partition table entry seems to be entirely a coincidence.)

Brendan wrote:
d) Some ancient Compaq machines (not sure how ancient) check that the first instruction in the MBR (and in a boot sector for "no partitions" - e.g. floppy) is a near jump or far jump (instead of checking for the 0xAA55 signature at the end), and assume the sector isn't bootable if there's no jump.

Any such Compaq machines would have to predate the introduction of the MBR, since Compaq was a DOS OEM and would be aware that the typical DOS MBR doesn't start with a jump instruction.


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Wed Sep 27, 2017 12:42 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 877
Location: Finland
I copy a quote from another topic so that I will not derail that discussion.

Brendan wrote:
For my OS; I'm thinking of only supporting "hybrid GPT", where the OS itself only uses GPT (and ignores MBR) and the MBR (ideally) contains 2 primary partitions - one small partition (for BIOS compatibility) that contains enough code to understand GPT and load/boot a file from an EFI system partition, and one huge protective partition to tell legacy OSs that the entire rest of the disk is in use (by GPT).


This is a hard problem and I've not been able to solve this. The way I tried to assemble the pieces of this puzzle always resulted in some problem (e.g. non-conformant to the specification). Could you describe an example disk layoyt as an "LBA map" (like a memory map)?

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Wed Sep 27, 2017 1:03 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 877
Location: Finland
Short announcement

The version 1.2 is frozen and no changes are made until (if) real bugs come up. If that happens, I apologize to you for my mistake.

Antti (reply to Octocontrabass) wrote:
I will comment about the algorithm and its implementation in a subsequent post. Thank you for your reply and link to your code.


It is more advanced bit twiddling. :) I will keep in mind that it is possible do it in that way.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Sun Oct 01, 2017 10:52 am 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 1200
Antti wrote:
It is more advanced bit twiddling. :)

Which part? It's all fairly basic algebra as far as I can see, though I'm not sure if I explained it clearly enough.


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Sun Oct 01, 2017 3:04 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8169
Location: At his keyboard!
Hi,

Antti wrote:
I copy a quote from another topic so that I will not derail that discussion.

Brendan wrote:
For my OS; I'm thinking of only supporting "hybrid GPT", where the OS itself only uses GPT (and ignores MBR) and the MBR (ideally) contains 2 primary partitions - one small partition (for BIOS compatibility) that contains enough code to understand GPT and load/boot a file from an EFI system partition, and one huge protective partition to tell legacy OSs that the entire rest of the disk is in use (by GPT).


This is a hard problem and I've not been able to solve this. The way I tried to assemble the pieces of this puzzle always resulted in some problem (e.g. non-conformant to the specification). Could you describe an example disk layoyt as an "LBA map" (like a memory map)?


It's impossible to have a GPT partitioned disk that can be booted by BIOS or UEFI and complies with the UEFI spec 100%; but (fortunately) most computers aren't fussy about strict UEFI compliance, so it is possible to have a GPT partitioned disk that can be booted by BIOS or UEFI (that doesn't quite comply with the UEFI spec but works fine anyway).

It would look something like (e.g.):

Code:
    LBA range           MBR's perspective              GPT's perspective
     LBA 0               MBR                            PMBR
     LBA 1 to 15         Protective partition #1        GPT (copy #1)
     LBA 16 to 33        Boot manager's partition       Boot manager's partition
     LBA 34 to 66        UEFI system partition          UEFI system partition
     LBA 67 to 1000      Protective partition #2        Partitioned however you like by GPT (for OSs, etc)
     LBA 1001 to 1015    Protective partition #2        GPT (copy #2, at end of disk)



Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Sun Oct 01, 2017 11:40 pm 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 877
Location: Finland
Octocontrabass wrote:
Which part? It's all fairly basic algebra as far as I can see, though I'm not sure if I explained it clearly enough.


Your explanation was, and still is, good. The "bit twiddling" was only meant as a compliment. It is fun to see that you are interested in these details we have discussed about. :)

Brendan wrote:
[...]


Thank you for the reply although the topic I quoted from already took off the discussion.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Fri Oct 06, 2017 12:04 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 877
Location: Finland
Another version of MBR (with GPT support) has been in progress a few days. There is a "UniquePartitionGUID" embedded in the LBA 0 and MBR code tries to find a partition (a boot manager) with that GUID. According to UEFI, there should be only one partition with that GUID. If a program that formats a disk creates the boot manager partition, emdeds the GUID in the LBA 0, and marks the partition as a "Required Partition" (GPT attributes), it should be a quite good solution?

Please note the word "quite" here. The disk layout is according to the UEFI specification but due to the lack of space, there are no perfect validations for GPT structures. However, I was wondering are those necessary here? Even if GPT structures were inconsistent (due to power failure etc.), the boot manager's partition should not be modified (it is a "Required Partition") and it is at least possible to try to recover the system when we are "safe" (after we have much more code, the boot manager).

Based on ideas shared on this forum, I'm implementing support for cases where "BIOS LBA" and "GPT LBA" does not match, e.g. "512" and "4096", respectively. I think this is a nice feature, maybe mostly for fun, because it is an easy feature to test. For test cases, there could be specifically crafted disk images.

There is one bothersome thing. If there is a strict "protective partition table", there are no bootable partitions unless the protective partition (starting from LBA 1) is marked as such (scary). For computers that require it, maybe there could be:

Code:
    **** NON-STANDARD PROTECTIVE LEGACY PARTITION TABLE ****
     (for BIOSs that do not boot without active partitions)

    ENTRY       START       LENGTH      ACTIVE      TYPE
    #1          0           1           1           EEh
    #2          1           <max>       0           EEh
    #3          -           -           -
    #4          -           -           -


This would not be the default scenario. More like a work-around if it is really needed.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: General Master Boot Record
PostPosted: Fri Oct 06, 2017 1:36 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 877
Location: Finland
If there are developers who want to use the legacy partition table for compatibility purposes, i.e. the boot manager builds a custom partition scheme for a non-GPT-aware OS, it is entirely possible. All this handled by the boot manager. My version of MBR (with GPT support) will not use the legacy partition table at all so it does prevent this use case. The whole table is free for legacy purposes. E.g.

Code:
    ENTRY       START       LENGTH      ACTIVE          TYPE
    #1          1           127         0               EEh
    #2          128         1023        1 (ignored)     01h (DOS FAT-12)
    #3          1024        <max>       0               EEh
    #4          -           -           -

    (Note: numbers are random, perhaps they should have traditional alignments)


However, this is not my use case but my MBR does not make the decision. It is the boot manager that may do this if this feature is required. Separation of mechanism and policy. :)

_________________
Undefined behavior since 2012


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 32 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 9 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group