Revisiting the DOS Memory Models
blogsystem5.substack.com
blogsystem5.substack.com
I see various comments below along the lines of “oh, the article is missing so and so”. OK… then please see the other articles in this series! I think they cover most of what you are mentioning :-)
The first was on EMS, XMS, HMA and the like: https://blogsystem5.substack.com/p/from-0-to-1-mb-in-dos
The second was on unreal mode: https://blogsystem5.substack.com/p/beyond-the-1-mb-barrier-i...
The third was on DJGPP: https://blogsystem5.substack.com/p/running-gnu-on-dos-with-d...
And the last, which follows this one, is on 64 bit memory models: https://blogsystem5.substack.com/p/x86-64-programming-models
Some of these were previously discussed here too, but composing this in mobile and finding links is rather painful… so excuse me from not providing those links now.
https://news.ycombinator.com/from?site=blogsystem5.substack....
I don't blame anyone for not realizing that there are more articles on the topic.
> At the beginning of the year, I wrote a bunch of articles on the various tricks DOS played to overcome the tight memory limits of x86’s real mode.
With link to an article.
What do you call this pattern? It seems to be popular lately. I haven't been able to find a description of it, but it would be much more helpful to the reader if it was identified.
Instead of
> At the beginning of the year, I wrote a _bunch_ _of_ _articles_ on the various trick
It's better to write
> At the beginning of the year, I wrote a bunch of articles (_1_, _2_, _3_) on the various trick
or something similar.
At the beginning of the year, I wrote a bunch of articles on the various tricks (_below 1MB_, _above 1 MB_, and _with GNU JMP_)
Just describe the content you’re linking to. You know best as the author!
However, there were variants of malloc and free that returned or accepted far pointers, or alternatively you could ask DOS for memory in 16-byte units and slice it yourself (e.g. by loading game assets). Therefore many programs used the small and medium models instead of compact and large respectively, and annotated pointers to large data (which is almost always runtime-loaded and dynamically allocated anyway) by hand with the __far modifier. This was the most efficient setup with the only problem that, due to the 64k limit, you could hardly use the heap or recursion.
It works like a virtual memory system, except that the compiler emitted the necessary code rather than the CPU doing it in microcode.
https://www.digitalmars.com/ctg/handle-pointers.html
Similarly, Zortech C++ had the "VCM" memory model, which worked like virtual memory. Your code pages would be swapped in an out of memory as needed.
This would be trivial (and fun) to implement with Wasm.
Wasm also supports multimemories, https://github.com/WebAssembly/multi-memory
https://github.com/WebAssembly/multi-memory/blob/main/propos...
The scaling point is what I was thinking of.
"As long as Wasm memories are limited to 32 bit address space, there is no way to scale out of 4 GB memory efficiently. Multiple memories at least provide an efficient workaround until 64 bit memories become available (which may still take a while)."
So pretty similar to launching several processes on 32 bit NT or Linux, each having their own memory space.
One program (com) I wrote with it back then is still being used by at least one person. I talked to them a couple of months ago and they said they still use it.
I used it for Empire, and for my text editor. When moving to Linux, it was easy to convert to using TTY sequences.
Phillipe Kahn is a marketing genius, and I am not.
(VCM's overlays could be loaded anywhere, the relocation happened at runtime.)
That machine had a 64k user space but could support more physical memory, a big PDP-11 installation might support 20 terminals which each offer a BASIC experience just a little bigger than the Apple ][ a few years earlier, particularly after they introduced separate address spaces for code and data.
In 1980 as a kid I was reading books about computers and would get my fingers on a TRS-80 or a PDP-8 and thinking the PDP-11 is what "the next thing" up from the "8-bit micros" but really the PDP-11 was long in the tooth in 1980 because it did not exceed 64k barrier of those chips.
The 8086 had a pragmatic approach to addressing more memory, you have to remember that when the IBM PC came out hardly anyone could afford to load the machine up with 640k or more memory, instead you would have 64k or 128k, so in the early days COM files did not seem limited but rather a way to migrate from the CP/M ecosystem in terms of compilers and tooling.
Personally I loved assembly language programming for the real-mode 80286 and did not feel the segmentation model to be much of a burden. I remember great portability of Unix games like Nethack to DOS. My 80286 beat the pants off any PDP-11 and my 80486 trounced the VAX-11/780... DEC's minicomputers were dead but the VAX was a pioneer machine that popularized the virtual memory model of modern 32-bit and 64-bit computers.
Pardon me for not realizing and treating it appropriately.
> with the same inelegant workarounds that's been rediscovered since the late sixties or so
Short of creating instructions that take 64bit immediate operands you're always going to pay the same price. An indirection. This will look different because it will be implemented most efficiently differently on different architectures.
> GOT and PLT versus pools of absolute 64-bit addresses, pick the least worst one.
Or statically define all those addresses within your binary. That seems more "elegant" to you? You'll have the same problem but your loader will now be inside out or you'll have none of the features the loader can provide for you.
At that point just statically link all your dependencies and call it an early day.
There is a difference between indirecting through a register, or through a memory (which in the end also requires a register, in addition to a memory load). On the other hand, I$ is more precious, and the most popular parts of GOT are likely to be in the voluminous D$ anyhow, so it's hard to tell which is more efficient.
> Or statically define all those addresses within your binary. That seems more "elegant" to you?
Of course not. I personally think a directly specifiable 64-bit offset from the base register that holds the start of the data section is more elegant. But dynamic libraries don't mesh too well with this approach although IIRC it has been tried.
> you'll have none of the features the loader can provide for you. At that point just statically link all your dependencies and call it an early day.
This works surprisingly well in practice, actually. Data relocations are still an issue though.
It really is though. Memory and thus data _and_ instruction encoding were incredibly important. Physical wires on the circuit board were at a premium then as well. It was an incredibly popular platform because it was highly capable while being stupidly cheap compared to other setups.
Engineering is all about tradeoffs. "Purity" almost never makes it on the whiteboard.
x86 could have easily had an IP-relative addressing mode for data from the beginning (jumps and calls already had it), but to get a pointer you can pass around to use someplace else than the current instruction, it has to be either absolute, or relative to some other "base" register which stays constant. Like the segment registers.
The 286 and 386 in protected mode did allow segments with any base address (24 or 32 bits), so your argument about extending the address space doesn't make sense.
386 (not sure how 286 works) did extend segments to a larger address space, by converting them to segment selectors, but it requires a significantly more complex MMU as it is a form of virtual memory.
The 286 did that, though they only extended the address space to 24 bits. The 386 extended it again to 32 bits.
This design allowed for a smaller chip, and keeping backwards compatibility with the 8080.
Yet, it extended CP/M by allowing you to use more than 64 KB vs. 8080/Z80.
One thing missing are overlays, where we could have some form of primitive dynamic loading, having multiple code segments for the same memory region, naturally only one could be active at a time.
First, more functionality. The minigames and intro/conclusion scenes were their own executables that made use of the original, generated game data. These got loaded into RAM on top of the original executable and then called.
Second, graphics and sound were also overlays. Rather than having useless-to-most Roland MT-32 code in the binary, this was only loaded if requested. There were overlays for Sound Blaster, PC speaker, and Adlib. If your monitor only supported four colors (CGA) there was an overlay for that.
A post would be nice, although you basically described most of it. An .OVL file with a non-zero overlay number is loaded into memory with INT 3Fh (although strangely enough any interrupt number could be chosen?, and the interrupt also would call the desired function after loading into memory). These overlays are loaded as-needed into a shared memory space.
I'd be more curious to see how one would have programmed those overlays in Microsoft C Compiler 3.0. More recent compilers seemed to have better menus and documentation for the memory models, but it seems like they were clairvoyant by squeezing every bit of functionality out of version 3.0 that was made easier by Watcom/Borland/MS 5.0. (Then again, they would have evolved their build system with every successful release and every new hire, plus it was their full time job to "figure that crap out", and maybe Microsoft improved their approach to overlays in response to Microprose and others calling all the time)
The documentation states only one EXE is generated, but Microprose had multiple EXE files. Is it possible those weren't overlays but something very similar? Or did they just change the file extensions? The docs also show the syntax "Object Modules [.OBJ]: a + (b+c) + (e+f) + g + (i)" where everything in parentheses is an overlay. But this isn't elaborated. What are the plus signs? How are these objects grouped? Would their list look like "preload + (cga + mcga + ega + vga) + (nosound + tandy + pcspkr + roland + sb) + (intro) + (newgame) + (maingame) + (minigamea) + (minigameb) + (outro)"? Or would every module be individually parenthesized, and those with plus symbols are interdependent (e.g. not alternatives)? (One website using BLINK seems to suggest the latter.)
I know there are a lot of DOS tutorials (FreeDOS YT channel, blog posts) but I haven't found one that does a start-to-finish overlay example.
Chapter 18, TP 3 and 7, to show its evolution
http://www.bitsavers.org/pdf/borland/turbo_pascal/Turbo_Pasc...
http://www.bitsavers.org/pdf/borland/turbo_pascal/Turbo_Pasc...
TC++, page 211
https://bitsavers.org/pdf/borland/turbo_c/Turbo_C++_Programm...
Clipper, section 7-18
https://archive.org/details/Clipper_Compiler_for_dBASE_III_a...
From this series: https://neuviemeporte.github.io/category/f15-se2.html
Related HN thread: https://news.ycombinator.com/item?id=40347662
Now I wonder if MISC.EXE and xGRAPHIC.EXE were the same across different games e.g. Covert Action vs F15 SE2... (I just checked. MISC is different. Some routines are nearly similar, but newer versions have additional machine code and updated strings.)
Interestingly, although Civilization uses an almost identical setup menu and also contains multiple exes that look like sound and graphic drivers based on their name, the overlay header format of those seems to be different, and could not be parsed by my tool. Seems likey they were updating the scheme as they went along (Civ 1 came out 1991, so after F15-II).
So possibly related, https://en.wikipedia.org/wiki/QEMM
https://github.com/sudleyplace/386MAX
It would be great if someone could update it so it ran on modern hardware. Then, for instance, FreeDOS could use it.
And there was also HXRT from the same author, which allowed you to run win32 apps in DOS. Never really made good use of it, but thought it was still pretty cool.
I'm sure someone took advantage of this, but my knowledge is purely theoretical.
[0] https://en.wikipedia.org/wiki/Ralf_Brown%27s_Interrupt_List
DJGPP was such an eye opener back then and it made things much easier: finally, we were able to have one pointer for linear graphic buffer access; also you could easily save 2MB in memory, and its DPMI was free, compared to the other ones available.
For a 32-bit program, FS is used to point to the Thread Information Block (TIB). GS is used to point to thread-local storage since after Windows XP. Programs using GS for thread-local storage won't work on prior versions of Windows (they'll just crash on the first access).
X64 made it even more formal that CS, DS, SS and ES are fixed at zero. 32-bit programs running on a 64-bit OS can't reassign them anymore, but basically no programs actually try to do that anyway.
---
As for shorter types of pointers being in use? Basically shorter pointers are only used for things relative to the program counter EIP, such as short jumps. With 32-bit protected mode code, you can use 32-bit pointers and not worry about 64K-size segments at all.
---
Meanwhile, some x64 programs did adopt a convention to use shorter pointers, 32-bit pointers on a 64-bit operating system. This convention is called x32, but almost nobody adopted it.
It's doable in managed languages, e.g. Java has compressed pointers by default on sub 32GB heaps. I suppose it's doable even in C alike setup (incl OS calls) but that would require wrappers to bit shift the pointers on each dereference (and passive to the OS, extern)
There was no uptake and I believe it is deprecated today.
(Things THEY don't want you to know: you can in fact write code in languages which aren't C, don't compile down to C, and don't depend on a C library. Even under Linux.)
As for reloading segment registers, 64-bit Linux is able to run 32-bit binaries, so there have to be ring 3 code segments for both modes. And there is nothing in the architecture stopping assembly code from jumping between those segments!
With a 32-bit binary that does this, you get access to all the features of 64-bit mode, with everything in your address space guaranteed to be mapped at an address below 4G. The only point where you need to use 64-bit pointers is in structures passed to syscalls. (for arguments in registers it's done automatically by zero-extension)
With 16 byte paragraphs, a 16 bit segment and 16 bit offset can only address 1MiB (ignoring the HMA you can get on 80286+).
With 256 byte paragraphs, the 8086 would have been able to address 16MiB in real mode (again not counting the HMA, which would have been a bit smaller: 65,280 bytes instead of 65,520 bytes).
The 80286 changed how the segment registers worked in protected mode, giving access to 16M of address space, but couldn't change it for real mode as it would have broken a ton of code. Both Intel and IBM never thought the IBM PC would take over the market like it did.
They considered 256 byte alignment too wasteful, 64K would have been ridiculous (many business computers at the time didn't even have that much memory)
Scenario B: Imagine you're writing a page of video to the VGA framebuffer. Glossing over a whole lot of minutiae, you can simply jam 64,000 bytes into the address and data lines starting at A000:0000 without needing to stop and think about what you're doing w.r.t. the segment registers. Any kind of segment change every n bytes would require the loop to be interrupted some number of times over the course of the transfer to update DS or ES. This would also prevent something like `rep movs` from being able to work on a full screenful of data.
The 16-byte paragraph, and the many segment/offset aliases that could be constructed to refer to a single linear memory address, was a design choice that tried to serve the needs of both of those groups.
Given published information [1] that the 8086 was designed in a weekend as a panic stop-gap to provide some form of "more advanced CPU" to keep Intel in the market while the iapx432 project was underway, but falling far behind schedule, it seems doubtful that the designers would also have been thinking of "ease of further expansion for future revision" on what was, at the time, just a stop-gap CPU to sell while awaiting the shipment of the iapx432. Published information is that at the time Intel never expected the 8086 to create the huge extended family it has created, and instead expected the iapx432 to be that "grand family ancestor". The market, of course, had other ideas, and IBM's choice of 8088 for the IBM-PC was the catalyst that launched the 8086 design into the family it is today.
[1] I no longer have a reference to the publication
Squeezing four more address pins in would have meant multiplexing four more of the pins on the chip, and if you exclude power/ground pins there are only 13 pins that are not multiplexed, and several of those either can't be multiplexed (because they are inputs, i.e., CLK, INTR, NMI) or would have made bus design even more painful than it already is for these chips.
The 4 bit shift, instead of 8 bit shift, for the segment registers was likely as big an address bus they could do that would also fit the constraint of "fits into a 40pin DIP".
In real mode memory addressing works as described in the article. A 2-byte segment number and a 2-byte offset are combined to produce the memory address. The translation from segment:offset to physical address is:
physical_address = segment * 16 + offset
In protected mode the segment number is replaced with a selector. A selector is also 2-bytes but it is no longer just a single number. It is 3 fields:
• 13-bit selector number (SEL)
• 2 bit request privilege level (RL)
• 1 bit table indicator (T)
The way a selector:offset is translated to a physical address is:
• There are two "descriptor tables", the Local Descriptor Table (LDT) and the Global Descriptor Table (GDT). A descriptor is a data structure that contains the physical address of a block of memory, the length of the block, and some privilege information. The LDT is for memory of the current process, and the GDT is for memory shared by all processes such as the memory of the operating system.
• The selector number SEL is used as an index into one of those tables to find a descriptor. The table indicator bit T selects which table.
• The request privilege level RL is checked agains the privilege information from the descriptor, and the offset is checked against the length of the block described by the descriptor. If those checks pass then:
physical_address = address_from_descriptor + offset
Here's how they packed SEL, RL, and T into a 16-bit selector.
+-------------+-+--+
| selector |T|RL|
+-------------+-+--+
+-------------+-+--+----------------+
| selector |T|RL| offset |
+-------------+-+--+----------------+
If they had just laid out SEL, RL, and T a little differently in the selector they could have fixed that. Just put SEL in the least significant bits instead of the most significant bits:
+--+-+-------------+----------------+
|RL|T| selector | offset |
+--+-+-------------+----------------+
(If the OS needed to run a program that did need an address space with the kind of overlap that real mode has it could set up the LDT for the process so that the descriptors did describe overlapping memory blocks).
If Intel had done this compilers for 286 protected mode would have only needed small model and compiler writers, library writers, and programmers would have been much happier.
So why didn't they?
One guess I've heard is that since a descriptor table entry is 8 bytes, by putting SEL in the top bits of the selector and the other 3 bits worth of fields in the bottom they didn't have shift SEL to turn it into an offset from the base of the descriptor table. If SEL were at the bottom it would need to be shifted by 3 to make it an offset into a descriptor table.
I've talked to CPU designers (but none who worked on 80286) and they have told me for this kind of thing where you would always want to shift an input by a fixed amount building that shift in is essentially free, so that doesn't seem to be the explanation.
This might be one reason for it, but note that page table entries also use the lower bits for attributes. This means that software can use AND to separate the physical address and other bits, and OR to combine them, with no shift operation required.