should program call stack grow upward or downwards? | Bytes (2024)

I know this is a very fundamental question. I am still quite confused
if the program call stack stack should always grows upwards from the
bottom, or the opposite, or doesn't matter??

That means the stack pointer should go upwards when there are "push"
operations,
and stack pointer should go downards when there are "pop" operations??

If this is the case, the address should go upwards (increasing) or
downards (decreasing) then? i.e. The top of the stack should have
address 00000000, or FFFFFFFF? How do we decide that?

Please advice. thanks!!

Subscribe Reply

>I know this is a very fundamental question. I am still quite confused

>if the program call stack stack should always grows upwards from the
bottom, or the opposite, or doesn't matter??

Yes. The important point is that YOU DON'T GET TO CHOOSE.
Also, it either DOES or it DOESN'T. There is no SHOULD DO or
SHOULDN'T DO.

>That means the stack pointer should go upwards when there are "push"
operations,
and stack pointer should go downards when there are "pop" operations??

"UP" means towards the address at the top of a page in a textbook.
"DOWN" means towards the address at the bottom of a page in a textbook.
Neither has any relevance to the numerical value of the address, which
may be 00000000 at the equator and 7FFFFFFF at the North Pole.

>If this is the case, the address should go upwards (increasing) or
downards (decreasing) then?

There is no SHOULD. And upwards does not mean increasing.

>i.e. The top of the stack should have
address 00000000, or FFFFFFFF? How do we decide that?

*YOU* don't get to decide. Accept what you get. Don't write programs
that care about stack growth direction.

Coos Haak <ch*****@hccnet .nlwrites:

Op Thu, 21 Sep 2006 09:56:34 +0200 schreef Torben Ægidius Mogensen:

<snip>

>If, for example,
offsets in load/store instructions are positive only, it makes sense
to either let the stack grow upwards and address relative to a frame

You may have meant downwards, see the MC 6800 (not 68000)

That was in the "or" part you didn't cite.

Torben

Op Fri, 22 Sep 2006 09:35:53 +0200 schreef Torben Ægidius Mogensen:

Coos Haak <ch*****@hccnet .nlwrites:

>Op Thu, 21 Sep 2006 09:56:34 +0200 schreef Torben Ægidius Mogensen:

<snip>

>>If, for example,
offsets in load/store instructions are positive only, it makes sense
to either let the stack grow upwards and address relative to a frame

>You may have meant downwards, see the MC 6800 (not 68000)

That was in the "or" part you didn't cite.

Torben

I missed the word bottom (the FP) and read it as top (the SP). Yes, thank
you.
--
Coos

In article <11************ **********@h48g 2000cwc.googleg roups.com>,
<sj*******@yaho o.comwrote:

>John wrote:

>I know this is a very fundamental question. I am still quite confused
if the program call stack stack should always grows upwards from the
bottom, or the opposite, or doesn't matter??

There's no guarantee in C that there is a stack, and there are
platforms (with C compilers) out there that don't have one. On the
(much more common) platforms that have a stack, it can grow up or down.

C does in fact require a stack, unless by "stack" you actually
mean "contiguous region of memory used to store function invocation
records"[1]. Function calls and returns are required to do The Right
Thing, and multiple calls to the same function aren't allowed to interfere
with each other; if you can figure out how to do that without something
that looks, acts, and smells like a stack, I would really like to
know how.

Of course, there are several reasonable ways to implement such a stack;
you could allocate a contiguous region of memory and keep your activation
records (with where-to-return information and storage for automatic
variables) there, in which the OP's question would actually make sense
(and the correct answer would be "it depends"), or you could dynamically
allocate each invocation record and free them when the function returns
(this would be isomorphic to a linked-list implementation of a stack),
or you could combine the two (dynamically allocate memory in blocks;
when you call a function and don't have room in the current block,
allocate another one; when you return and empty a block, deallocate and
return to the previous one).

(I see this is crossposted to comp.arch; if anybody there is still
reading, this would probably be a good place to jump in with some more
esoteric ones.)

There are even more unreasonable ways to implement it as well; if an
implementation has enough tame rhinodaemons that are not being used for
other purposes, it's free to ask them to hold onto the last function's
call information, as long as they give it back in the right order when
it's needed.
dave

[1] And if a C implementation uses that, the discussion elsethread
indicates that the most correct answer to the OP's question is
probably neither "up" nor "down", but "in".

--
Dave Vandervies dj******@csclub .uwaterloo.ca
[P]lease continue to follow this thread. It's helpful to have the dissenting
viewpoint coming from someone who's not a flaming asshole.
--Steve Gravrock in comp.lang.c

>C does in fact require a stack, unless by "stack" you actually

>mean "contiguous region of memory used to store function invocation
records"[1]. Function calls and returns are required to do The Right
Thing, and multiple calls to the same function aren't allowed to interfere
with each other; if you can figure out how to do that without something
that looks, acts, and smells like a stack, I would really like to
know how.

OS/360 used a linked list of "save areas" containing saved registers,
return addresses, and if desired, local variables. (Now, granted,
when I was working with it, C didn't exist yet, or at least it
wasn't available outside Bell Labs.) Reentrant functions (required
in C unless the compiler could prove it wasn't necessary) would
allocate a new save area with GETMAIN and free it with FREEMAIN.
Non-reentrant functions would allocate a single static save area.

>Of course, there are several reasonable ways to implement such a stack;
you could allocate a contiguous region of memory and keep your activation
records (with where-to-return information and storage for automatic
variables) there, in which the OP's question would actually make sense
(and the correct answer would be "it depends"), or you could dynamically
allocate each invocation record and free them when the function returns
(this would be isomorphic to a linked-list implementation of a stack),

I'm not so sure this meets the definition of a "stack". In any
case, such an implementation has no sensible definition of "growth
direction" for a stack.

go***********@b urditt.org (Gordon Burditt) writes:

OS/360 used a linked list of "save areas" containing saved registers,
return addresses, and if desired, local variables. (Now, granted,
when I was working with it, C didn't exist yet, or at least it
wasn't available outside Bell Labs.) Reentrant functions (required
in C unless the compiler could prove it wasn't necessary) would
allocate a new save area with GETMAIN and free it with FREEMAIN.
Non-reentrant functions would allocate a single static save area.

minor note ... the savearea allocation was the responsibility of
the calling program ... but the saving of registers were the
responsibility of the called program ... i.e. on program entry,
the instruction sequence was typically:

STM 14,12,12(13)

i.e. "store multiple" registers 14,15,0,...,12 ... starting at
(decimal) 12 offset from location pointed to by register 13.

for more detailed discussion ... i've done a q&d conversion of the old
ios3270 green card to html ... and more detailed discussion of
call/save/return conventions can be found at:
http://www.garlic.com/~lynn/gcard.html#50
the called program only needed a new save area if it would it turn
call some other program. non-reentrant programs (that called other
programs) could allocate a single static savearea. only when you had
reentrant programs that also called other programs ... was there an
issue regarding dynamic save area allocations.

the original cp67 kernel had a convention that was somewhat more like
a stack. it had a contiguous subpool of 100 save areas. all module
call/return linkages were via supervisor call. it was the
responsibility of the supervisor call routine to allocate/deallocate
savearea for the call.

per aside, cp67 and unix can trace somewhat common heritage back to
ctss, i.e. cp67 work was done at the science center on the 4th flr
of 545 tech sq
http://www.garlic.com/~lynn/subtopic.html#545tech

including some people that had worked on ctss. multics was on the 5th
flr of 545 tech sq ... and also included some people that had worked
on ctss.

as i was doing various performance and scale-up work ... i made a
number of changes to the cp67 calling conventions.

for some number of high-use non-reentrant routines (that didn't call
any other modules), i changed the calling sequence from supervisor
call to simple "branch and link register" ... and then used a static
area for saving registers. for some number of high-use common library
routines ... the supervisor call linkage scenario had higher
pathlength that the function called ... so the switch to BALR call
convention for these routings significantly improved performance.

the other problem found with increasing load ... was that it became
more and more frequent that the system would exhaust the pool of 100
save areas (which caused it to abort). i redid the logic so that it
could dynamically increase and decrease the pool of save areas
.... significantly reducing system failures under heavy load.

there was subsequent generalized subpool enhancement for cp67
kernel dynamic storage management ... which also significantly
contributed to descreasing kernel overhead.

article from that work
Analysis of Free-storage Algorithms, B. Margolin et all, IBM Systems
Journal v10n4, 283-304, 1971

and from the citation site:
http://citeseer.ist.psu.edu/context/418230/0

misc. past postings mentioning cp67 kernel generalized subpool work:
http://www.garlic.com/~lynn/93.html#26 MTS & LLMPS?
http://www.garlic.com/~lynn/98.html#19 S/360 operating systems geneaology
http://www.garlic.com/~lynn/2000d.html#47 Charging for time-share CPU time
http://www.garlic.com/~lynn/2002.html#14 index searching
http://www.garlic.com/~lynn/2002h.html#87 Atomic operations redux
http://www.garlic.com/~lynn/2004g.html#57 Adventure game (was:PL/? History (was Hercules))
http://www.garlic.com/~lynn/2004h.html#0 Adventure game (was:PL/? History (was Hercules))
http://www.garlic.com/~lynn/2004m.html#22 Lock-free algorithms
http://www.garlic.com/~lynn/2006e.html#40 transputers again was: The demise of Commodore
http://www.garlic.com/~lynn/2006j.html#21 virtual memory
http://www.garlic.com/~lynn/2006p.html#11 What part of z/OS is the OS?

thanks

regards
<a href=http://www.stormloader .com/users/unification/>MMOG</a>
<a href=http://unificationwars s.0catch.com>on line games</a>
<a href=http://unificationwars .freewebspace.c om/>free games</a>

On Sun, 24 Sep 2006 15:24:41 -0600 in alt.folklore.co mputers, Anne &
Lynn Wheeler <ly**@garlic.co mwrote:

>there was subsequent generalized subpool enhancement for cp67
kernel dynamic storage management ... which also significantly
contributed to descreasing kernel overhead.

article from that work
Analysis of Free-storage Algorithms, B. Margolin et all, IBM Systems
Journal v10n4, 283-304, 1971

Image scan available (1.1MB) at:
http://www.research.ibm.com/journal/...ibmsj1004C.pdf

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

Br**********@CS i.com (Brian[dot]Inglis{at}Syste maticSW[dot]ab[dot]ca)
fake addressuse address above to reply

In article <ef**********@r umours.uwaterlo o.ca>,
dj******@caffei ne.csclub.uwate rloo.ca (Dave Vandervies) writes:
|>
|(I see this is crossposted to comp.arch; if anybody there is still
|reading, this would probably be a good place to jump in with some more
|esoteric ones.)

You called?

Further to the Wheeler's postings, a lot of the customer and third-party
compilers (and some system interfaces!) used non-standard conventions,
because the standard linkage was so slow. I repeatedly (over 20 years)
pointed out to them and IBM Santa Teresa that the problem was not the
linkage but its poor implementations ; I demonstrated that I could speed
up the Fortran call THREE times just by reordering the linkage data and
linkage instructions. But the message went largely unheard ....

PL/I supported GETMAIN R for linkage, but it was a damn-fool way of
providing reentrancy (though it was not PL/I's fault, but the linkage
editor's). Almost all other languages allocated a register to the
stack at startup and put up with the constraint that the couldn't be
called reentrantly from modules that used standard linkage.

Several compilers (PL/I, if I recall, and several of my libraries) used
a basically rising/falling stack, but would extend on overflow by GETMAIN.
This means that the stack segments need not be contiguous, and may be in
an unpredictable order. This was not limited to System/370.

And some used a secondary stack, which often went the opposite direction
to the main stack. As I have posted before, I don't know why this has
been forgotten, as it provides a significant performance enhancement for
free.

|There are even more unreasonable ways to implement it as well; if an
|implementation has enough tame rhinodaemons that are not being used for
|other purposes, it's free to ask them to hold onto the last function's
|call information, as long as they give it back in the right order when
|it's needed.

Yup. Seen that. But old age now means that I can't remember where.
Regards,
Nick Maclaren.

Anne & Lynn Wheeler wrote:

go***********@b urditt.org (Gordon Burditt) writes:

>OS/360 used a linked list of "save areas" containing saved registers,
return addresses, and if desired, local variables. (Now, granted,
when I was working with it, C didn't exist yet, or at least it
wasn't available outside Bell Labs.) Reentrant functions (required
in C unless the compiler could prove it wasn't necessary) would
allocate a new save area with GETMAIN and free it with FREEMAIN.
Non-reentrant functions would allocate a single static save area.

minor note ... the savearea allocation was the responsibility of
the calling program ... but the saving of registers were the
responsibility of the called program ... i.e. on program entry,
the instruction sequence was typically:

STM 14,12,12(13)

i.e. "store multiple" registers 14,15,0,...,12 ... starting at
(decimal) 12 offset from location pointed to by register 13.

for more detailed discussion ... i've done a q&d conversion of the old
ios3270 green card to html ... and more detailed discussion of
call/save/return conventions can be found at:
http://www.garlic.com/~lynn/gcard.html#50
the called program only needed a new save area if it would it turn
call some other program. non-reentrant programs (that called other
programs) could allocate a single static savearea. only when you had
reentrant programs that also called other programs ... was there an
issue regarding dynamic save area allocations.

the original cp67 kernel had a convention that was somewhat more like
a stack. it had a contiguous subpool of 100 save areas. all module
call/return linkages were via supervisor call. it was the
responsibility of the supervisor call routine to allocate/deallocate
savearea for the call.

per aside, cp67 and unix can trace somewhat common heritage back to
ctss, i.e. cp67 work was done at the science center on the 4th flr
of 545 tech sq
http://www.garlic.com/~lynn/subtopic.html#545tech

including some people that had worked on ctss. multics was on the 5th
flr of 545 tech sq ... and also included some people that had worked
on ctss.

as i was doing various performance and scale-up work ... i made a
number of changes to the cp67 calling conventions.

for some number of high-use non-reentrant routines (that didn't call
any other modules), i changed the calling sequence from supervisor
call to simple "branch and link register" ... and then used a static
area for saving registers. for some number of high-use common library
routines ... the supervisor call linkage scenario had higher
pathlength that the function called ... so the switch to BALR call
convention for these routings significantly improved performance.

the other problem found with increasing load ... was that it became
more and more frequent that the system would exhaust the pool of 100
save areas (which caused it to abort). i redid the logic so that it
could dynamically increase and decrease the pool of save areas
... significantly reducing system failures under heavy load.

there was subsequent generalized subpool enhancement for cp67
kernel dynamic storage management ... which also significantly
contributed to descreasing kernel overhead.

article from that work
Analysis of Free-storage Algorithms, B. Margolin et all, IBM Systems
Journal v10n4, 283-304, 1971

and from the citation site:
http://citeseer.ist.psu.edu/context/418230/0

misc. past postings mentioning cp67 kernel generalized subpool work:
http://www.garlic.com/~lynn/93.html#26 MTS & LLMPS?
http://www.garlic.com/~lynn/98.html#19 S/360 operating systems geneaology
http://www.garlic.com/~lynn/2000d.html#47 Charging for time-share CPU time
http://www.garlic.com/~lynn/2002.html#14 index searching
http://www.garlic.com/~lynn/2002h.html#87 Atomic operations redux
http://www.garlic.com/~lynn/2004g.html#57 Adventure game (was:PL/? History (was Hercules))
http://www.garlic.com/~lynn/2004h.html#0 Adventure game (was:PL/? History (was Hercules))
http://www.garlic.com/~lynn/2004m.html#22 Lock-free algorithms
http://www.garlic.com/~lynn/2006e.html#40 transputers again was: The demise of Commodore
http://www.garlic.com/~lynn/2006j.html#21 virtual memory
http://www.garlic.com/~lynn/2006p.html#11 What part of z/OS is the OS?

Moving to mini & micros, they all grow the stack downward: I assume
because most of the early ones (8086 being the exception) booted code
from zero, so there was usually ROM at low addresses. So grow the stack
toward it.
However, there's a case to be made for growing it upward, namely that
buffer overflows cannot mess with the saved register image or other
important areas: an overflow will only trash that function's own data,
then walk into unallocated space. Might make things a lot more robust.