Automatically Extensible Discontiguous Stacks

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...