11

The "large" memory model of x86 allowed a program to have multiple code segments and multiple data segment, using far calls to jump across code segments, and far pointers to access data from several data segments. But how about the stack segment?

How did 16-bit MS-DOS programs use a large (> 64KB) stack? Was there an additional calling convention where SS was adjusted at the beginning and the end of a procedure? Or maybe was it the case that every program did avoid using more than 64 KB of stack?

10
  • 7
    I'd like to ask why any DOS program would need a large stack over 64kb and if any program ever did? Only if some program did, then the "how" part can be answered.
    – Justme
    Feb 10 at 16:29
  • 12
    @airman Even then is 10% an extreme amount for stack. I have a hard time to think of any use that makes sense in an environment of a 4.77 MHz 8 bit CPU. Sure, nowadays people just imagine stack as a virtual endless resource, but that's rather new and quite lazy view, isn't it?
    – Raffzahn
    Feb 10 at 17:40
  • 5
    I think you would just consider it a fundamental constraint of the architecture, and simply design your code in a way that wouldn't need huge amounts of stack. It's not hard: convert recursive algorithms to iterative (often a good performance optimization anyway), pass large structures by value instead of by reference, use malloc for large locals. So I would guess the issue never really came up in the first place. Feb 10 at 22:48
  • 5
    @airman Also arguably, if you needed more than 64KB of stack in your 16-bit DOS program, regardless of the language, you would be doing something very wrong. You would not be passing multiple kilobytes of data as parameter through hardware stack of the CPU. In smaller CPUs like 6502/6510, the 256-byte CPU hardware stack is used for subroutine calls and returns in C, and there would be another software handled stack for passing parameters elsewhere in RAM. Nothing prevents to do the same on a 16-bit DOS program by some high level compiler.
    – Justme
    Feb 11 at 12:07
  • 3
    @marcelm ... but definitly not for the stack
    – tofro
    Feb 11 at 19:55

5 Answers 5

31

They simply did not use a large stack.

If you look at the standard memory models for the x86, there was a single stack segment in all of them (which was even shared with other segments in the smaller models).

A standard technique for stack handling that needs allocation etc. (which can happen e.g. for some flavours of coroutines) is to have additional code in the prolog of a function that checks if the new stack would exceed the allocated stack, and then allocate more, and undo it in the epilog.

That could also be used for a multi-segment stack.

But I've never seen an example where that would have been necessary.

Also, as mentioned in the comment, you just don't put large structures like buffers on the stack. They go to the heap, you put a pointer to them in the functional call or in local variables.

8
  • 13
    We didn't put buffers on the stack back then. The idea of a >64K stack would have been "Why would I ever need that much?" Source: I cut my teeth on DOS programming.
    – Joshua
    Feb 11 at 4:06
  • @Joshua: that, too.
    – dirkt
    Feb 11 at 6:09
  • Even today, you will rarely use much more. With a maximum stack depth of 100 methods, that's 640 bytes per stack frame, which is a lot. I've written few methods with that many parameters or local variables.
    – PMF
    Feb 11 at 18:47
  • @PMF: You wanna see my 1MB worth of buffers on the stack in modern 64 bit programming? It works great on virtual memory systems.
    – Joshua
    Feb 11 at 19:46
  • 2
    @supercat TP3.0 uses the rest of the free memory as stack and heap area, calling it as just stack. Up to 64KB stack for CPU hardware stack, the rest used as software handled stack and heap area.
    – Justme
    Feb 12 at 0:52
13

DOS programs typically have limited stack requirements, and tend to declare small stacks. DOS itself uses its own stacks in many cases, and programs’ stacks don’t need to leave much room for DOS use. For their own use, it would be unusual to need much stack space either — remember that 16-bit programs mostly have to work with only conventional memory, so even 64KiB is a large amount of memory to set aside for a stack.

If programs want a larger stack, they would have to manage it manually. One possibility would be to set up separate stacks for specific program calls. The x86 CPU itself doesn’t provide support for stacks larger than a segment: the PUSH and POP instructions only touch the stack pointer, not the stack segment, and reaching the end of the stack segment results in the stack pointer looping back to the top of the segment (which might well be beyond the stack).

If you think of the stack as a single “object”, then it matches the concepts even of larger memory models. The only exception is the huge memory model where single objects (arrays) can be larger than 64KiB, but that came with significant penalties.

9

The "large" memory model of x86 allowed a program to have multiple code segments and multiple data segment, using far calls to jump across code segments, and far pointers to access data from several data segments. But how about the stack segment?

Stack is a segment like any other. Thus changing SS allows to have multiple stack segments.

How did 16-bit MS-DOS programs use a large (> 64KB) stack?

They did not, as there can be none. Segments are always restricted to a maximum size of 64 KiB. That's true for all segments. The fact that its possible to manage larger structures than 64 KiB by manipulating segment registers as if they are address pointers is not in any way supported by the CPU, but handled under program control.

For the stack as a CPU controlled data structure (PUSH/POP/CALL/...) this means that no single stack can exceed 64 KiB. But like with data segments, a program can have as many as it wants (*1) and reload the segment register as they wish.

Of course, a procedure doing so should restore the original value of all registers before returning. Also, if stack is used to return data, teh procedure needs to do so on the original (callers) stack, not the new one. All of that is not supported by any language runtime I remember and would require some assembly.

Was there an additional calling convention where SS was adjusted at the beginning and the end of a procedure?

No. If needed for some reason, it had to be done 'manually'.

Or maybe was it the case that every program did avoid using more than 64 KB of stack?

It's hard to imagine a use case for more than 64 KiB of stack - or even 64 KiB at all - with the PC as intended target. For a PC that's a good tenth of the whole memory. An application needing that much stack space might be one more tailored for a mainframe or sole larger mini computer.

The only real use case for a program/procedure is when it can't 'trust' the caller to provide the stack space it needs to run. In that case the procedure would save the callers SS/SP and set them to it's own stack space.

Situations like that may happen with libraries, background (interrupt) functions and of course the OS itself. And in fact does MS-DOS for all of its more complex functions switch to its own stack, and back when returning.

Changing stack does add several pitfalls, especially in small systems like DOS.

  • Changing stack adds an overhead
  • Copying from and to the caller stack needs far addressing and careful handling
  • Private stack can usually not be allocated dynamically
  • Private must be static allocated, increasing memory requirement
  • The pointer to a private stack must be kept in a unique location addressable after entry, thus
    • either an absolut address (not exactly what user programs get),
    • or kept (as daa) in the code segment, aka modifying it.
  • Locking is required for certain operations - especially switching
  • Additional care needs to be taken to allow reentrance

All of this makes stack switching restricted to very special cases. DOS itself being the only common case, but here as well quite restricted. That's why DOS is for many functions non-reentrant, and as well the reason why parameter passing is done in registers - that way all pitfalls about stack handling can be avoided.


*1 - Well, they still should fit into memory and be not more than 65536 thereof ;)

4

The CONFIG.SYS file of DOS had a setting to enable multiple stacks, but these were used to handle hardware interrupts.

The Huge memory model might in theory have been used to support a stack of more than 64KiB, on the 8086, had one been needed. This would have inserted extra code to check for wraparound, and if so, modify the stack segment. It would not have worked in 80286 protected mode. However, this would have been so slow that I cannot think of a single program that actually used it for the stack. It was sometimes used to support data structures larger than 64 KiB when there was no alternative.

I can, on the other hand, imagine a module in a program switching to a different stack segment, making a large number of nested calls, but not enough to overflow a fresh stack segment, and switching back to the original stack segment before returning to the main program.

In practice, programmers of that era were trained to avoid recursive calls and refactor them into while loops. Programmers facing a stack overflow would similarly have looked for ways to move local data off the stack and to the heap. It was considered their responsibility to avoid stack overflows.

7
  • I wonder what the Turbo Pascal 3.0 manual means on page 226, when it says the stack segment may be larger than 64K, but also suggests that the stack segment never changes. Perhaps the intention was to allow for a programmer to use inline code at the beginning and end of a function to "normalize" the stack segment/pointer and then restore the old values when the function returned, in a manner somewhat analogous to the way programmers could force a special prologue/epilogue for interrupt handlers.
    – supercat
    Feb 11 at 21:30
  • @supercat i don’t know what the Turbo Pascal runtime did. Certainly, the hardware stack segment could only be 64K (or less, if it didn’t start at the top).
    – Davislor
    Feb 11 at 21:57
  • @supercat The manual refers to stack segment as the whole stack and heap area which basically covers all remaining memory free after code and data. The CPU hardware stack SS:SP is set to point to last byte in the entire area, and the rest it handles as allocateable memory heap with far pointers.
    – Justme
    Feb 11 at 23:24
  • 1
    @supercat: Borland (mis)used the term segment to mean a memory area (I'll reserve segment here for the Intel thing). For code and data areas, they were limited to the 64K(-ish for code) segment each but the stack area was special, consisting of a possibly massive heap followed by a <=64K stack segment. Heap pointers were segment/offset pairs normalised so offset was 0-15, so each variable could be 64k-15 bytes long. That heap grew upwards, even into the stack segment if need be, provided heap and stack did not collide (or you foolishly turned off stack protection). ...
    – paxdiablo
    Feb 19 at 6:56
  • 1
    ... That's why they say SP moves down to the ([my clarifications]) "bottom of the segment [area], or 0 if the stack segment [area] is larger than 64K bytes". The segment they mean there is the heap/stack area, not the stack segment. Annoyingly, in the exact same paragraph, they use "stack segment" to mean "heap/stack area" but "stack segment register" to mean "SS". They should have sought tech input here :-) It's also why they state that the largest heap variable can be about 64k even though, were that in the stack segment, you would only be allowed one variable and very little stack.
    – paxdiablo
    Feb 19 at 7:03
4

The large-code memory models (medium, large, and huge) did not need a stack size more than 64k, they just needed the ability to push/pop a cs:ip pair rather than just an ip.

That can be done without expanding the maximum stack size, it just means that each active call takes twice as many bytes on the stack.

In other words, large memory model did not use multiple stack segments.

Given the large amount of control you had with segment registers (before they became selectors with the introduction of protected mode), there was nothing stopping a program from actually using multiple stack segments, provided switching was done carefully (you definitely didn't want to return using a different stack than you called with). But this was not a feature provided by the "standard" memory models.

See this answer for more information on those memory models. It gives details on how segments were used for each.

0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .