kirchner@informatik.uni-kl.de (Reinhard Kirchner) (12/05/90)
There was a discussion in at.folklore.computers about why stacks are
growing downwards, not up as would seem natural. Since this
is clearly an architectural issue I am posting my experiences about
this to comp.arch as well as alt.folklore.computers.
From the operating system point of view the stack my grow in either
direction, there is no preference ( I think ). Detection of overflow
my be simpler in one direction, but thats all.
Stack and heap should always grow in opposite directions, so you
can allocate one pool of memory for both without any fixed size for one.
Now the architectural ( instruction set / registers ) problems:
I run into them when I designed a virtual machine for pascal with
numeric extensions ( the famous Pascal-SC, now even more extended and
called Pascal-XSC ) about 13 years ago ....
The name of this architecture was ( and is ) KL/P, since we are here
in KaisersLautern, and it was for Pascal, and every real computer has a '/' ...
How are the choices:
a. Stack growing upward
a1 -Stackpointer pointing to the first free byte
a2 -SP pointing to the last byte
a3 -SP pointing to the TOP-object and keeping its length somewhere in
a special register
b. Stack growing downward
b1 -SP pointing to the last byte which is also adress of Top-object
b2 -SP pointing to first free byte
Now we not only have to handle the stack, but also to adress items in it,
like parameters, locals, function results etc. Therefore we need some
base-addresses, one per lexical level, which may reside in baseregisters
or in linked stackframes. Anyway, if this base-point is between params and
locals we need +/- adresses, otherwise only one direction.
If we use baseregisters we need these also for adressing elements of records
( structures ), and since these are referenced by there first byte the
offset in this case must be positive.
Looking at the stack alone gives a clear preference of b1 since top is a
very often needed address. In all other cases we have to compute addresses
to access top.
No using a base address to some point makes it difficult:
When designing KL/P I had to find a compact encoding for small offsets,
so I could not deal with a sign bit. This forced me to positive offsets.
With a b1-stack I had to address over all locals to find parameters and
function results. Now in a numerical environment locals, parameters and
even function-results are often quite large vectors or matrices.
So I decided to use a a1-stack. Our first interpreter was on a Z80, the
handling was tricky anyway and I did not want to use the z80-Stack because
this was needed for the interpretation, and having z80-data and kl/p-data
mixed seemed a reliability issue....
From today and much more experience I must say:
I should have used the z80-stack ( b1 ), and should looked for a solution
to the positive-offset-problem, perhaps by additional address-modes etc.
Using the z80-stack would have given a lot of performance, this would
have outweighted the trouble.
So far the story of my stack
R. Kirchner
Univ. Kaiserslautern Germany
Computer Science
kirchner@uklirb.informatik.uni-kl.de
kinf89@dkluni01.bitnetlindsay@gandalf.cs.cmu.edu (Donald Lindsay) (12/09/90)
In article <7298@uklirb.informatik.uni-kl.de> kirchner@informatik.uni-kl.de (Reinhard Kirchner) writes: >From the operating system point of view the stack my grow in either >direction, there is no preference ( I think ). Detection of overflow >my be simpler in one direction, but thats all. >Stack and heap should always grow in opposite directions, so you >can allocate one pool of memory for both without any fixed size for one. This was completely correct, in the days of small, flat address spaces. With the advent of large virtual address spaces, it became reasonable to carve out huge regions as segments, and the stack and heap could be in separate segments. With the advent of thread-style OSes, there are now multiple stacks in the same address space. Further, we used to use software overflow checks. The correct answer now is to have the OS put invalid pages at appropriate places. This is a genuine improvement: it has perfect coverage (unlike some of the old software schemes), and it should have no runtime overhead. This means that the "correct" way to run a stack is completely determined by the addressing modes and the procedure call protocol. I believe that Robert Firth wants them to grow upward, but then, he knows more about procedure call protocols than I do. -- Don D.C.Lindsay .. temporarily at Carnegie Mellon
henry@zoo.toronto.edu (Henry Spencer) (12/09/90)
In article <11336@pt.cs.cmu.edu> lindsay@gandalf.cs.cmu.edu (Donald Lindsay) writes: >Further, we used to use software overflow checks. The correct answer >now is to have the OS put invalid pages at appropriate places. This >is a genuine improvement: it has perfect coverage (unlike some of the >old software schemes), and it should have no runtime overhead. Actually, no, it doesn't have perfect coverage: if you happen to grow the stack by a really large amount, you can leap over the invalid page and end up in another region of memory without detecting it until you try to access some of that big lump. Still generally a reasonable approach, mind you, since that sort of thing isn't common. -- "The average pointer, statistically, |Henry Spencer at U of Toronto Zoology points somewhere in X." -Hugh Redelmeier| henry@zoo.toronto.edu utzoo!henry