The memory management in DOS is simple, but that simplicity may be deceptive. There are several rather interesting pitfalls that programming documentation often does not mention.
DOS 1.x (1981) had no explicit memory management support. It was designed to run primarily on machines with 64K RAM or less, or not too much more (the original PC could not have more than 64K RAM on the system board, although RAM expansion boards did exist). A COM program could easily access (almost) 64K memory when loaded, and many programs didn’t rely on even having that much. In fact the early PCs often only had 64K or 48K RAM installed. But the times were rapidly changing.
DOS 2.0 was developed to support the IBM PC/XT (introduced in March 1983), which came with 128K RAM standard, and models with 256K appeared soon enough. Even the older PCs could be upgraded with additional RAM, and DOS needed to have some mechanism to deal with that extra memory.
The DOS memory management was probably written sometime around summer 1982, and it meshed with the newly added process management functions (EXEC/EXIT/WAIT)—allocated memory is owned by the current process, and gets freed when that process terminates. Note that some versions of the memory manager source code (ALLOC.ASM) include a comment that says ‘Created: ARR 30 March 1983’. That cannot possibly be true because by the end of March 1983, PC DOS 2.0 was already released, and included the memory management support. The DOS 2.0 memory management functions were already documented in the PC DOS 2.0 manual dated January 1983.
In PC DOS 2.0, three memory management functions were introduced: ALLOC (48h), DEALLOC (49h), and SETBLOCK (4Ah). The DEALLOC function may be better known as “free” and SETBLOCK as “resize”. The all-caps names are used in the actual DOS source code.
Structure
The memory managed by DOS (the “memory arena”) starts out as a single contiguous block. It begins just past the end of statically allocated memory and ends at the end of conventional memory. The available memory can be subdivided into smaller blocks through allocation. After a number of cycles of allocating and freeing memory, the available memory may be split up into a relatively large number of blocks, often a mix of free and used memory.
Each block of memory is prefixed by a header. Note that in the DOS source code, this is called an “arena header”. In third party literature, it is usually called a “memory control block” or MCB. This article will use the MCB terminology.
First of all, DOS manages memory in units of paragraphs (16 bytes), not individual bytes. This approach is derived from the segmented 8086 architecture. Managing memory in paragraph units allows DOS to use 16-bit quantities to record the starting address and size of each block. In addition, the starting paragraph address is also implicitly the segment address of the block. Note that due to tracking sizes in terms of paragraphs, DOS memory blocks are not limited to 64K.
The MCB by necessity takes up an entire paragraph, even though only 5 bytes were initially used; the following is an excerpt from MS-DOS 2.11 DOSSYM.ASM:
; ; arena item ; arena STRUC arena_signature DB ? ; 4D for valid item, 5A for last item arena_owner DW ? ; owner of arena item arena_size DW ? ; size in paragraphs of item arena ENDS
The signature byte is ‘M’ for all memory blocks except the last one, with the last block using a ‘Z’ signature. Perhaps ‘M’ stands for “memory” and ‘Z’ for “last” (block), or perhaps MZ are the initials of Mark Zbikowski, one of the core developers of DOS 2.0.
The DOS memory management functions check the signature of each MCB they work with. If it’s not ‘M’ or ‘Z’, an error is reported–and if that happens, all bets are off because something in the system corrupted memory, and nothing can be trusted anymore.
The owner of a memory block is a 16-bit word. It is set to zero to indicate a free block. A non-zero value is normally the PID (process identifier) of the owner, that is, the address of the PSP of the owning process. This is important when a process terminates, because DOS automatically frees all memory blocks that the process owned. Note that DOS performs no validity checks on the owner; any process can free or resize any block, regardless of who owns it, and the MCB owner need not be a valid PID.
The size is simply the size of the memory block in paragraphs, in theory up to (almost) 1MB.
The entirety of the memory managed by DOS is described by a chain of MCBs. The start of the chain is located through the arena_head variable within DOS. Each memory block is immediately followed by the MCB describing the next block, except for the last block in the chain (with the ‘Z’ signature) which has no follower.
The MCB chain acts somewhat like a linked list, but it is not a linked list. Instead of using some kind of a link pointer to the next item in the chain, the chain structure is implied by the location and size of the memory blocks. The memory blocks can only be processed in strictly ascending order and there cannot be any gaps between them.
Functions
The DOS memory functions are simple enough. The ALLOC function takes the desired size in paragraphs, and either returns a pointer to newly allocated memory in the AX register, or returns an error code in AX and the size of the largest free block in the BX register.
DOS programs often call ALLOC twice, first attempting to allocate FFFFh paragraphs, which will fail and return the maximum available size. The available maximum is then allocated in the next ALLOC call. Because DOS isn’t a multi-tasking OS, this simple approach reliably works.
A successful ALLOC returns returns the segment address of the newly allocated memory block in register AX, and the paragraph immediately preceding the allocated memory contains the block’s MCB header.
The DEALLOC function is very simple, only setting the block’s owner to zero to mark it as free.
The SETBLOCK function is somewhat like realloc() in the Standard C library, but never moves the allocated block. Resizing a block to the same or smaller size will always succeed, and will free up the remaining memory. Resizing to a larger size may fail, and if it does, the maximum available size will be returned in the BX register (just like when allocating).
Coalescing
An important feature of the DOS memory manager is coalescing of free memory, i.e. merging adjacent free memory blocks.
If a program successfully calls the ALLOC function twice, it will often own two adjacent memory blocks. If it then calls DEALLOC on each block, there will be two adjacent free memory blocks. When allocating memory again, these free blocks somehow need to be coalesced so that the free memory wouldn’t become endlessly fragmented.
DOS uses a simple strategy which will always coalesce free blocks when necessary. It works as follows:
- The DEALLOC function performs no coalescing whatsoever.
- The SETBLOCK function will coalesce all free blocks that immediately follow the memory block being resized (even if the new size is the same or smaller).
- The ALLOC function processes the entire MCB chain and coalesces all free memory blocks that can be coalesced; this ensures that ALLOC always finds the largest available free block.
Naively one might think that the DEALLOC function is a good time to coalesce, but it’s not. If two adjacent blocks are freed, and the block higher in memory is freed last, coalescing can’t be done because DOS cannot reach the previous (lower in memory) MCB, only the next one.
The ALLOC function does the heavy lifting, but that is inevitable: Only by walking the entire MCB chain can DOS coalesce all eligible memory and ensure that the largest free block is found. This means that calling the ALLOC function can be somewhat expensive if the MCB chain is long. In practice, there are unlikely to be more than a few dozen MCBs, even in a heavily loaded system.
Caveats
Now we come to the less obvious aspects of DOS memory management. Some are inevitable, some are strange, some are really bugs.
It is possible to have zero-sized memory blocks (i.e. blocks consisting solely of an MCB header). The ALLOC function does not refuse to allocate zero-sized blocks. In addition, zero-sized blocks may be inevitably created in the course of calling other functions. For example, if an existing allocation is resized to be exactly one paragraph smaller, DOS will be forced to create precisely such a zero-sized MCB.
The SETBLOCK function always sets the MCB owner when it succeeds. That is, a DOS process may resize any existing memory block, regardless of who owns it, and become the owner. If the resizing succeeds (and resizing to the same or smaller size always will), the calling process will become the owner of the block. Obviously, resizing memory blocks owned by other processes is a risky business.
It is possible to use SETBLOCK on a free memory block. Programs obviously should not be doing that, because they do not own free memory. However, DOS makes no attempt to prevent such calls. In addition, thanks to the surprising behavior noted above, successfully calling SETBLOCK on a free memory block will effectively allocate it.
When the SETBLOCK function fails because the requested size was too large, it returns the maximum available size that the block can be resized to. However, DOS already resized the memory block to that maximum available size. This is almost certainly a bug, one that Microsoft didn’t dare fix in later DOS versions.
DOS 2.11 Enhancements
In MS-DOS version 2.11, Microsoft added a memory management tweak which was never documented until much later. Note that this change was not in PC DOS 2.1, but was naturally included in PC DOS 3.0.
In MS-DOS 2.11, there is a new INT 21h function called AllocOper (58h). It allows the caller to set or get the memory allocation strategy. The available options are usually referred to as “first fit” (0, the default value), “best fit” (1), and “last fit” (2).
When the ALLOC function scans the entire MCB chain and coalesces memory, it makes a note of the first (lowest) free memory block that is big enough to satisfy the allocation, the last (highest) free memory block that is big enough, and also the smallest (best) memory block big enough to satisfy the allocation.
Obviously these are not necessarily three different blocks. Two or even all three of the possible allocation options may well be the same block, especially if the number of free memory blocks is low.
Note that INT 21h/58h was not documented in official Microsoft programming references for DOS 2.x, 3.x, and 4.0. The DOS 5.0 reference does document AllocOper, but claims that it was added in DOS 3.0, which is not quite true.
DOS 5.0 Enhancements
The DOS memory management saw very minimal changes from version 2.11 up to and including DOS 4.0. DOS 5.0 brought somewhat significant changes related to UMB support.
When DOS 5.0 and later runs with DOS=UMB, there will be not one but two memory arenas (assuming that UMBs are actually available). The AllocOper function (58h) was significantly extended to support UMBs.
In addition to the first/best/last fit allocation strategy introduced in DOS 2.11, DOS 5.0 introduces three additional strategies, each of which is combined with the first/best/last fit strategy:
- Allocate from conventional memory only (backward compatible)
- Allocate from UMBs first, then from conventional memory
- Allocate from UMBs only
In addition to supporting new memory allocation strategies as controlled by INT 21h/58h subfunctions 0 and 1 (get and set allocation strategy, respectively), DOS 5.0 also added new subfunctions 2 and 3. These allow the caller to query (subfunction 2) or set (subfunction 3) the UMB link.
That is, DOS 5.0 can either link or unlink UMBs from the standard memory chain (in conventional memory). To allocate memory from UMBs, a program must both set an allocation strategy which looks at UMBs and link the UMBs to the pool of available memory.
Note that the allocation strategy and UMB link setting are both global DOS state, not per-process. A DOS program which changes either the allocation strategy or the UMB link state should restore the original setting before it terminates, at least according to the MS-DOS 5.0 Programming Reference.
Summary
Although DOS memory management is in principle very simple, users may find some of its behaviors surprising. The addition of UMB support in DOS 5.0 made DOS memory management noticeably less simple than before, although only TSRs and drivers tend to worry about upper memory.
I recently talked about memory management in lDOS, FreeDOS, and EDR-DOS in a report to the emu2 repo: https://github.com/dmsc/emu2/issues/122
Reading this article I noticed you state that MS-DOS coalesces all free MCBs during alloc, and indeed it does. Unlike what I assumed, it doesn’t stop searching the chain on the first available block even if “first fit” is selected: https://hg.pushbx.org/ecm/msdos4/file/b33476ca12ed/src/DOS/alloc.nas#l280
That means lDOS’s COMPAT=NOCOLLECTALLMCBS is actually *less* alike to MS-DOS. But COMPAT=COLLECTALLMCBS will also collect in the UMA even if the strategy/link are set not to scan the UMCB chain: https://hg.pushbx.org/ecm/msdos4/file/b33476ca12ed/src/DOS/memory.asm#l810
Also, another bit you got right is that MS-DOS’s resize coalesces all subsequent free MCBs. In lDOS I don’t do that, I only collect if trying to enlarge and only as many MCBs as needed to satisfy the requested size. In the MS-DOS sources you can also see that resize shares some code with alloc, explaining why it sets the owner (but only if the full size can be satisfied): https://hg.pushbx.org/ecm/msdos4/file/b33476ca12ed/src/DOS/alloc.nas#l397
In the github thread I also mentioned that EDR-DOS collects free MCBs on freeing a block too. As you wrote, it cannot easily collect free blocks before the MCB being freed, but it does collect ones after it.
Writing of the strategy, the LMA/UMA selection mask of 00h is actually “LMA then UMA, as one area” if combined with an enabled UMB link. Mask 80h is “UMA first, then LMA, as two areas”. Mask 40h is “UMA only”. With the UMB link disabled, all masks are overridden by “LMA only” behaviour. Two areas for mask 80h means that if under “last fit” a suitable UMCB is found, it is allocated, even if there’s enough free LMCBs to satisfy the “last fit” allocation too (which would be “later” were they treated as one area).
Aside from some more extensions in my lDOS kernel, I also changed things so the MCB chain is set up very early (in NEARDOSINIT) and then all LMA/UMA allocations are done using valid MCBs. In MS-DOS (I think FreeDOS too), during config.sys / device= processing a rudimentary MCB chain exists but it isn’t fully used yet, placing several allocations in “free memory”.
I also believe I once observed that MS-DOS command.com at some point runs in free memory, ie the code to free part of the shell resides in the very part being freed.
Nice article. Do you have any idea how DPMI worked with this? I was recently playing with running Windows 3.x natively in 16bit selectors in Linux. Not only DPMI translates all far pointers from protmode selector-offset to segment-offset pair in various interrupts (0x21 etc), but also values in PSP seem to be pointing correctly from PM-point of view, the same IIRC applies for MCB chain.
I have not checked directly in Windows using some debug app yet, this is just observation from kernel.exe crashes in my environment. Windows Kernel simply gets (for example) environment selector from PSP/PDB and uses it directly.
The article is based primarily on my reading of the DOS 2.11/4.0 source code, and motivated by the fact that some of what the DOS code does is far from obvious.
With coalescing, I suspect that the people writing DOS simply decided that because coalescing can’t always be accomplished when freeing memory, they won’t even bother. It was also clearly written with the assumption that the MCB chain won’t be very long, so traversing it won’t be terribly expensive. DOS 5.x/6.x loaded with networking and TSRs probably has way more MCBs than they could imagine when writing DOS 2.0, but even then it won’t be more than a few dozen entries.
It would not surprise me if COMMAND.COM or other programs temporarily ran out of freed memory. After all, in a single-tasking system the memory can’t be used until COMMAND.COM lets a child process do it.
I’m not sure I fully understand the question. DPMI services for DOS memory management (INT 31H functions 0100H/0101H/0102H) presumably call the corresponding DOS services. For freeing memory it might not be necessary, for allocating memory the DPMI spec explicitly says that “The DOS allocation function (Int 21H Function 48H) is used”. But the DPMI server has extra work on top because it must manage the protected-mode selectors corresponding to the real memory allocations.
The MCB chain does not contain pointers so if a 32-bit DPMI client maps the conventional memory as a single block, traversing the chain would not be difficult.
> The MCB by necessity takes up an entire paragraph, even though only 5 bytes were initially used;
The name field was added to mcb only in dos 4.0, and there was no way to determine the name of mcb’s owner in dos 2. In dos 3, you have to follow program’s mcb -> psp -> environment -> argv[0] chain. It doesn’t work for programs that free their environment like tsrs, so there was an informal convention to put a name/comment ascii string at cs:0x103, after the jmp. It can be seen in some old tsrs and memory listing programs like vtsr by golden bow.
> Naively one might think that the DEALLOC function is a good time to coalesce, but it’s not.
It’s, you just have to start from the first mcb. This strange design choice is likely an attempt to save a few bytes for mcb walker function.
> The SETBLOCK function always sets the MCB owner when it succeeds.
It jumps in the middle of ALLOC code, so no wonder, another attempt to economize memory.
> When the SETBLOCK function fails because the requested size was too large, it returns the maximum available size.
It’s a consequence of merging free mcbs in malloc() instead of free(). Could have been easily mitigated[1], so it’s likely an oversight or yet another attempt to scrounge a few bytes.
[1] Just need to start merging from the next mcb after specified, if it’s free and not last, then see if the sum of specified and newly created free mcb is bigger or equal to new mcb size, run merge again if it is or abort otherwise.
A long time ago, when I was looking at DOS Plus (which is a DOS emulator on top of a CP/M kernel) I found the command processor seems to have code to walk a separate memory block chain when dealing with environment variables, with signature bytes 0x6D and 0x7A (ie ‘m’ and ‘z’).
The weirdness is pretty much all a consequence of the unidirectional traversal of the MCB chain. It did occur to me that it probably wouldn’t have been rocket science to make traversal bidirectional (e.g. by also storing the size of the previous allocation in each MCB). Then all the coalescing could be done when freeing and it would only need traversing as much of the chain as necessary to find the nearest preceding/following allocated block.
But they did it the way they did and yes, minimizing the code size was surely a real concern. So the behavior is… interesting.
The next themes to cover:
1. Subblock allocations in DOS owned SD block.
2. UMB secondary MCB chain.
3. DOS 7.0+ “I” subblock type and its subtypes.
4. What the hell is “Y” subtype of “I” type subblock really holds in its data 🙂
Enjoyable as always. I’ve dived into DOS’s memory management myself a while ago, because of my 32 bit protected mode toy OS project that “stole” DOS’s memory management. To use it, my 32 bit kernel called into the DOS that launched it, by having transplanted that DOS into a vm86 mode task. That way my kernel could use DOS’s memory management, keyboard handling, even TCP/IP through packet drivers… basically everything I did not (or did not yet) want to implement myself. Instead I could focus on the things that I did want to implement, like message passing, multiprocessing, and lower level CPU features. It was all just for fun and exploration.
> 2. UMB secondary MCB chain.
You forgot HMA mcb chain and its weird api 🙂
> 3. DOS 7.0+ “I” subblock type and its subtypes.
G – BDS
H – single sector work buffer in lower memory
R – relocated ebios (extended BDA) if it exists
Y – IOS.vxd startup structures: TSRInfo + ios devices safelist
> 4. What the hell is “Y” subtype of “I” type subblock really holds in its data
See ‘Y’ description above. Usually it’s stored in HMA mcb, but can appear as IFS subtype ‘Y’ if you force dos low. You can get pointer to pointer to IOS safelist struct by calling 2F/0x1690, don’t forget to zero es/bx before. There is no api to get TSRInfo structure, but pointer to it stored at fixed offset DOSDATA:1328. The IOS.vxd itself getting it that way.
The TSRInfo structure format:
TSRInfo:0 dword cur_int13 (=IO:3EE)
TSRInfo:4 word cur_bdev_irq_record
TSRInfo:6 dword ??? (always 0)
TSRInfo:A dword ??? used in check_TSRInfo
TSRInfo:E 240 bytes blockdevs/irqs (20 records)
TSRInfo:FE word blockdevs/irqs array overflow flag
TSRInfo:100 64 bytes prev_irq_vectors
TSRInfo:140 byte blkdev dcb array size (=1A max)
TSRInfo:141 104 bytes blkdev dcb array (26 records max)
sizeof(bdev_irq_record) = 12
bdev_irq_record:0 client PSP
bdev_irq_record:2 irq bitmask
bdev_irq_record:4 blkdev bitmask
bdev_irq_record:8 TSRInfo:A ???
The IOS devices safelist format (see also KB/138899, win9x DDK rmd.h):
IOSSafe:0 byte ver (=7)
IOSSafe:1 dword ??? (always 0)
IOSSafe:5 byte number of device entries (20 max)
IOSSafe:6 20+ bytes device_record 1
[..]
IOSSafe:X 20+ bytes device_record 20
sizeof(device_record) = 20+
device_record:0 11 bytes name
device_record:B word flags (unsafe(0b), umb_provider(1b))
device_record:D byte unit_num (0 for char devices)
device_record:E 5 bytes record 1
[..]
device_record:X 5 bytes record A
sizeof(record) = 5
types:
1 – driver addr, 2 – int13h addr, 3 – orig(bios) int13h addr,
4 – int4Bh addr, 5 – int4Fh addr, 6 – aspi driver addr,
7 – logical unit hook addr, 8 – config sys line number,
9 – config.sys timestamp, 0Ah – hardware int hook map
record:0 byte type
record:1 dword (pointer to) data
>You forgot HMA mcb chain and its weird api
There is MCB chain too? If I remember correctly from Geoff Chappel’s book there is no “Free” function so I think that allocation inplemented just through the pointer to the rest of the free area in HMA.
>Usually it’s stored in HMA mcb, but can appear as IFS subtype ‘Y’ if you force dos low.
I know this, of course. But in addition to the info you provided (thanks!), it holds array of some 4 additional bytes for every record in CDS too.
Do you know anything about it?
>> You forgot HMA mcb chain and its weird api
> There is MCB chain too?
It was introduced in dos 7: new mcb format, extended api, etc. See RBIL 2F/4A03,4 for (vague) details.
> I know this, of course. But in addition to the info you provided (thanks!), it holds array of some 4 additional bytes for every record in CDS too. Do you know anything about it?
See above:
TSRInfo:140 byte blkdev dcb array size (=1A max)
TSRInfo:141 104 bytes blkdev dcb array (26 records max)
The blkdev dcb array is 26 * 4 bytes long(*) zero-padded array of pointers to block device’s dcb (device control block or simply device headers) for the corresponding drive. For built-in dos block devices it should be IO:5E, you can check this by running mem /dev command.
*) If loaded low as IFS, in HMA it contains records only for the configured drives.
>TSRInfo:141 104 bytes blkdev dcb array (26 records max)
Thanks again.
>You can get pointer to pointer to IOS safelist struct by calling 2F/0x1690, don’t forget to zero es/bx before. There is no api to get TSRInfo structure, but pointer to it stored at fixed offset DOSDATA:1328
Ok, I checked real data. TSRInfo really locates in Y block on DOS=LOW, but IOS SafeList is not and it points to MSDOS DATA area:
Addr Size T Owner Name Decription
————————-
00C9 0DD0 MSDOS.SYS
1143 0026 I 1144 Y IO, IOS.LOG Info (Drivers & TSRs) <- IOS TSRs
IOS Info: Drivers Addr: 020A:223C, TSRs Addr: 1144:0000
When DOS=HIGH both really point to HMA:
IOS Info: Drivers Addr: FFFF:223C, TSRs Addr: FFFF:D720
>You can get pointer to pointer to IOS safelist struct
Eh, it’s pointer to pointer, not pure pointer.
Now test is consistent with Vlad Gnatov’s info, thanks once again.
One annoying aspect of DOS memory management is how it handles environment variables; basically duplicating the way Unix did so, where each process has a copy of the environment. COMMAND.COM’s EXEC handle does the heavy lifting for this. Each process effectively has two memory blocks allocated for it: one with a copy of the environment and the other with the process itself.
This causes problems once the environment is on the larger side (tended to be common when building development environments to run on DOS which were inspired by Unix tools, and thus used lots of environment variables for settings) since every subprocess had to copy the entire environment.
Overall, an API to handle the environment (and avoid duplication) would have been a lot better.
Annoying for sure. The default environment size was often not enough, and when it was increased to something more sensible the memory consumption would go up.
Unfortunately I don’t think the duplication could have been avoided without completely breaking the familiar and desirable UNIX semantics.
I will add that TSRs often freed their environment blocks, possibly some other programs did too. Which was very sensible because they didn’t need the environment at all, or if they did, it was only at startup.
> Annoying for sure. The default environment size was often not enough
Well, considering that dos exec(21/4b) always shrinks the environment to the used part, there is no way around duplication if you plan to actively use it. That’s why even task0 (primary COMMAND.COM) allocates the new environment segment.
>This causes problems once the environment is on the larger side (tended to be common when building development environments to run on DOS which were inspired by Unix tools, and thus used lots of environment variables for settings) since every subprocess had to copy the entire environment.
The problem is, as often with dos, the unix behaviour was copied not enough and/or wrong. In unix(posix 2001), there is a nifty little utility called “env” which allows to change the environment(add/delete variables or completely replace the environment) passed to a subprocess.
I don’t see any obvious reason why a DOS version of env could not be written. But I also don’t see how it would really help. As Josh said, one very common usage scenario with largish environments was build systems, and there the environment had to be propagated, not thrown away.
> I don’t see any obvious reason why a DOS version of env could not be written.
There is no fork()/exec() pair in dos, so it’s not that easy, especially as an external command.
> I also don’t see how it would really help. As Josh said, one very common usage scenario with largish environments was build systems, and there the environment had to be propagated, not thrown away.
You can’t avoid duplication, but a convenient way to modify and replace the environment would certainly help to save some memory.
I’m confused. Sure there’s no fork() in DOS, but env doesn’t use that. Just about every C run-time implements exec(). Porting an old Unix env to DOS is about a two-minute job.
The current env executable is a substantial file. I haven’t checked how much smaller the period Xenix version was but I suspect it would still be a hefty program relative to the 256K and 360K floppy drives of DOS 2. The environment tools baked into DOS covered 90% of the use cases with a modest requirement of disk and memory space.
The purpose of using env in our case is to save some memory by reducing the environment. The env utility, if ported straightforwardly, would likely to consume more memory by itself than it saves by shrinking the environment. If this is not an issue, then yes, it can be and had been ported trivially. AFAIR, env.exe was present in MKS toolkit 2.x