Automatically Extensible Discontiguous Stacks
Original Publication Date: 1996-Feb-01
Included in the Prior Art Database: 2005-Mar-31
Publishing Venue
IBM
Related People
Hassitt, A: AUTHOR [+2]
Abstract
Existing threads packages allocate space for a complete execution stack at thread creation time. This requires a pre-knowledge of the maximum stack size. This invention answers the question "How can AIX/ESA* stacks be provided for multiple threads without requiring this advance knowledge and without changing linkage conventions, routine prologues, or in any other way affecting the AIX/ESA compilers?"
Automatically Extensible Discontiguous Stacks
Existing
threads packages allocate space for a complete
execution stack at thread creation time.
This requires a
pre-knowledge of the maximum stack size.
This invention answers the
question "How can AIX/ESA* stacks
be provided for multiple threads
without requiring this advance knowledge
and without changing
linkage conventions, routine prologues, or in any other way affecting
the AIX/ESA compilers?"
Use this
scheme under AIX/ESA as it would apply to other
operating systems, for example Mach, as long as they use AIX/ESA C
linkage conventions or similar linkage conventions. This scheme is
also used with C and FORTRAN compilers on AIX/370. It's
applicability to other compilers on other operating systems depends
on the linkage conventions used by them.
A block is
allocated for the initial stack and its bottom page
is protected (the "red zone").
Any stack overflow exception is
detected in the normal way, but activates the exception handling code
provided by this invention instead of
the the prior exception
handling code.
If a stack
overflow occurs then an additional block is obtained
to extend the stack discontiguously. In
this new block:
o
The bottom page is protected to provide a red zone.
o
The beginning of the caller's stack frame is duplicated.
o
The complete stack frame for the callee is created.
o
Additional stack frames are obtained as needed for more growth.
If additional stack overflows occur, the stack is extended
further by
adding additional blocks in the same manner.
Fig. 1 shows
a sample AIX/ESA stack. Stack growth
starts at
the top (high memory address), and grows towards the bottom (low
memory address) where a protected red zone exists to detect stack
overflow (this is described in more detail later). When a routine is
executing, one named CALLER for example, it uses a stack pointer
register (SP) to address a portion of the stack known as its frame.
The beginning of CALLER's frame holds a pointer back to the frame of
the routine that invoked CALLER. This is
followed by (in a "higher
address" sense) a register save
area that will be used by any
routine that CALLER invokes, and an area for building the arguments
that are passed to such a routine. Together
these frame areas make
up the frame preface; the frame is completed by an area for CALLER's
local variables.
Fig. 2 shows what happens when CALLER invokes SUB1. SP is decreased
to provide a new stack frame for SUB1; this corresponds to CALLER's
frame as described above. In addition, a
second register (HSP) may
be set in the high part of SUB1's frame.
HSP is used to address both
this area and CALLER's preface.
HSP-based references to SUB1's frame
may be in read mode or write mode, but references to CALLER's frame
are read-only. Now suppose that SUB1
invokes SUB2, and that the
stack does not contain enough remaining room for SU...