# US 2004/0019744 A1 · Methods and systems for dynamically growing multiple stacks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0019744 A1
- Document ID: US20040019744A1
- Status: Published application
- Kind: A1
- Application number: 10/202,335
- Filed: 2002-07-24
- Published: 2004-01-29
- Earliest claimed: 2002-07-24
- Assignees: Sun Microsystems, Inc.
- Inventors: Michael L. Boucher
- Web page: https://patentgrep.com/patent/US20040019744A1

## CPC

- G06F 12/0223: {User address space allocation, e.g. contiguous or non contiguous base addressing}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An allocation instructions and an extension instructions allow a program to continue to execute even when the program requires more stack space than has been allocated to the program. The methods and systems thereby allow programs to run to completion in more situations than programs running in conventional data processing systems. As a result, the programs avoid wasting computing resources by terminating prematurely, without producing results.

## Claims

### Claim 1

A method in a data processing system having a stack for allocating a new stack frame in stack overflow memory for a subroutine, the new stack frame bounded by a frame pointer and a stack pointer, the method comprising the steps of:
establishing a placeholder stack frame on the stack, the placeholder stack frame extending from the stack to the stack overflow memory; and
establishing the new stack frame for the subroutine in the stack overflow memory.

### Claim 2 (depends on 1)

The method of claim 1, wherein the step of establishing a placeholder stack frame comprises the steps of:
setting the stack pointer to point to the stack overflow memory; and
setting the frame pointer ahead of a current value of the stack pointer.

### Claim 3 (depends on 1)

The method of claim 1, further comprising the step of initiating a call to a stack placeholder subroutine.

### Claim 4 (depends on 1)

The method of claim 1, wherein the step of establishing the new stack frame comprises the steps of:
setting the stack pointer ahead of the frame pointer to bound the new stack frame in the stack overflow memory; and
setting the frame pointer ahead to point to the stack overflow memory.

### Claim 5 (depends on 1)

The method of claim 1, further comprising the step of:
after execution of the subroutine, restoring the frame pointer and the stack pointer to bound the placeholder stack frame.

### Claim 6 (depends on 5)

The method of claim 5, wherein a pre-existing stack frame was present on the stack before establishing the placeholder stack frame, and further comprising the step of:
restoring the frame pointer and the stack pointer to bound the pre-existing stack frame.

### Claim 7 (depends on 1)

The method of claim 1, further comprising the step of gathering statistics on the creation of the new stack frame.

### Claim 8 (depends on 7)

The method of claim 7, wherein the statistics comprise a sequence of subroutine calls giving rise to creation of the new stack frame.

### Claim 9 (depends on 7)

The method of claim 7, wherein the statistics comprise a size for the new stack frame, and a number of times the new stack frame is created.

### Claim 10

A method in a data processing system for extending an existing stack frame on a stack into stack overflow memory, the existing stack frame bounded by a frame pointer and a stack pointer, the method comprising the steps of:
allocating a memory block in the stack overflow memory;
setting an allocation reference to point to the memory block; and
setting the stack pointer beyond the allocation reference to create an extension for the existing stack frame.

### Claim 11 (depends on 10)

The method of claim 10, further comprising the step of specifying an allocation request amount, and wherein the step of setting the stack pointer comprises the step of setting the stack pointer ahead of the extension pointer by the allocation request amount.

### Claim 12 (depends on 10)

The method of claim 10, further comprising the step of initiating a call from a requesting program to a stack memory allocation instructions.

### Claim 13 (depends on 12)

The method of claim 12, further comprising the step of returning the allocation reference to the requesting program.

### Claim 14 (depends on 10)

The method of claim 10, wherein the step of allocating the memory block comprises the step of searching an allocation table for free memory.

### Claim 15 (depends on 10)

The method of claim 10, further comprising the step of specifying an allocation request amount, and wherein the memory block is characterized by a beginning address, and the step of setting the allocation reference comprises the step of setting the allocation reference to the beginning address, and wherein the step of setting the stack pointer comprises the step of setting the stack pointer beyond the beginning address by more than the allocation request amount.

### Claim 16 (depends on 10)

The method of claim 10, further comprising the step of gathering statistics on the creation of the extension.

### Claim 17 (depends on 16)

The method of claim 16, wherein the statistics comprise a size for the extension.

### Claim 18 (depends on 16)

The method of claim 16, wherein the statistics comprise a number of times the extension is created.

### Claim 19 (depends on 18)

The method of claim 18, further comprising the step of specifying an allocation request amount, and wherein the step of setting the stack pointer comprises the step of setting the stack pointer beyond the allocation reference by the more than the allocation request amount when the number of times the extension is created exceeds a pre-selected threshold.

### Claim 20

A computer-readable medium containing instructions that cause a data processing system having a stack to perform a method for allocating a new stack frame in stack overflow memory, the new stack frame bounded by a frame pointer and a stack pointer, the method comprising the steps of:
establishing a placeholder stack frame on the stack, the placeholder stack frame extending from the stack to the stack overflow memory area; and
establishing the new stack frame in the stack overflow memory.

### Claim 21 (depends on 20)

The computer-readable medium of claim 20, further comprising the step of initiating a call to a stack placeholder subroutine.

### Claim 22 (depends on 20)

The computer-readable medium of claim 20, wherein the step of establishing the new stack frame comprises the steps of:
setting the frame pointer ahead to point to the stack overflow memory; and
setting the stack pointer ahead of the frame pointer to bound the new stack frame in the stack overflow memory.

### Claim 23 (depends on 20)

The computer-readable medium of claim 20, further comprising the step of:
after execution of the subroutine, restoring the frame pointer and the stack pointer to bound the placeholder stack frame.

### Claim 24 (depends on 23)

The computer-readable medium of claim 23, wherein a pre-existing stack frame was present on the stack before establishing the placeholder stack frame, and further comprising the step of:
restoring the frame pointer and the stack pointer to bound the pre-existing stack frame.

### Claim 25 (depends on 20)

The computer-readable medium of claim 20, further comprising the step of gathering statistics on the creation of the new stack frame.

### Claim 26 (depends on 25)

The computer-readable medium of claim 25, wherein the statistics comprise a sequence of subroutine calls giving rise to creation of the new stack frame.

### Claim 27 (depends on 25)

The computer-readable medium of claim 25, wherein the statistics comprise a size for the new stack frame, and a number of times the new stack frame is created.

### Claim 28

A computer-readable medium containing instructions that cause a data processing system to perform a method for extending an existing stack frame on a stack into stack overflow memory the existing stack frame bounded by a frame pointer and a stack pointer, the method comprising the steps of:
allocating a memory block in the stack overflow memory;
setting an allocation reference to point to the memory block; and
setting the stack pointer beyond the allocation reference to create an extension for the existing stack frame.

### Claim 29 (depends on 28)

The computer-readable medium of claim 28, wherein the step of allocating a memory block comprises the step of searching an allocation table for free memory.

### Claim 30 (depends on 28)

The computer-readable medium of claim 28, further comprising the step of specifying an allocation request amount, and wherein the memory block is characterized by a beginning address, and the step of setting the allocation reference comprises the step of setting the allocation reference to the beginning address, and wherein the step of setting the stack pointer comprises the step of setting the stack pointer beyond the beginning address by more than the allocation request amount.

### Claim 31 (depends on 28)

The computer-readable medium of claim 28, further comprising the step of gathering statistics on the creation of the extension.

### Claim 32 (depends on 31)

The computer-readable medium of claim 31, wherein the statistics comprise a size for the extension.

### Claim 33 (depends on 31)

The computer-readable medium of claim 31, wherein the statistics comprise a number of times the extension is created.

### Claim 34 (depends on 33)

The computer-readable medium of claim 33, further comprising the step of specifying an allocation request amount, and wherein the step of setting the stack pointer comprises the step of setting the stack pointer beyond the allocation reference by the more than the allocation request amount when the number of times the extension is created exceeds a pre-selected threshold.

### Claim 35

A data processing system comprising:
a memory comprising a stack, stack overflow memory, and stack frame allocation instructions, the stack frame allocation instructions allocating a new stack frame for a subroutine bounded by a frame pointer and a stack pointer in stack overflow memory by establishing a placeholder stack frame that extends from the stack to the stack overflow memory, and establishing the new stack frame in the stack overflow memory area; and
a processor that runs the stack frame allocation instructions.

### Claim 36 (depends on 35)

The data processing system of claim 35, wherein the stack frame allocation instructions initiates a call to a stack placeholder subroutine.

### Claim 37 (depends on 35)

The data processing system of claim 35, wherein the stack frame allocation instructions establishes the new stack frame by setting the frame pointer to point to the stack overflow memory and setting the stack pointer ahead of the frame pointer to bound the new stack frame in the stack overflow memory.

### Claim 38 (depends on 35)

The data processing system of claim 35, wherein the stack frame allocation instructions, after execution of the subroutine, restores the frame pointer and the stack pointer to bound the placeholder stack frame.

### Claim 39 (depends on 38)

The data processing system of claim 38, wherein the stack frame allocation instructions restores the frame pointer and the stack pointer to bound an existing stack frame present on the stack prior to the step of establishing the placeholder stack frame.

### Claim 40

A data processing system comprising:
a memory comprising a stack holding an existing stack frame bounded by a frame pointer and a stack pointer and stack frame extension instructions, the stack frame extension instructions extending the existing stack frame by setting an allocation reference to point to an overflow memory area outside of the stack; and setting the stack pointer beyond the allocation reference to create an extension for the existing stack frame; and
a processor that runs the stack frame allocation instructions.

### Claim 41 (depends on 40)

The data processing system of claim 40, wherein the stack frame extension instructions allocates a memory block in the stack overflow area for the extension of the existing stack frame.

### Claim 42 (depends on 41)

The data processing system of claim 41, further comprising the step of specifying an allocation request amount, and wherein the memory block is characterized by a beginning address, and the step of setting the allocation reference comprises the step of setting the allocation reference to the beginning address, and wherein the step of setting the stack pointer comprises the step of setting the stack pointer beyond the beginning address by more than the allocation request amount.

### Claim 43

A data processing system for allocating a new stack frame bounded by a frame pointer and a stack pointer to store data used by a subroutine, the data processing system comprising:
means for establishing a placeholder stack frame on a stack, the placeholder stack frame extending from the stack to overflow memory in a stack overflow memory area; and
means for establishing the new stack frame in the overflow memory for the subroutine.

### Claim 44

A data processing system for extending an existing stack frame bounded by a frame pointer and a stack pointer, the data processing system comprising:
means for setting an allocation reference to point to an overflow memory area beyond the stack; and
means for setting the stack pointer beyond the allocation reference to bound a stack extension for the existing stack frame.

### Claim 45

A method in a data processing system for allocating storage space for a subroutine using a stack, the method comprising the steps of:
determining when the stack lacks sufficient space to hold a new stack frame, and, in response:
establishing a placeholder stack frame on the stack, the placeholder stack frame extending from the stack to a stack overflow memory area; and
establishing the new stack frame in the stack overflow memory; and
initiating a stack memory allocation request to extend an existing stack frame bounded by a frame pointer and a stack pointer;
determining when the stack lacks sufficient space to meet the stack memory allocation request, and, in response:
setting the stack pointer to point to the stack overflow memory;
allocating a memory block in the stack overflow memory;
setting an allocation reference to point to the memory block; and
setting the stack pointer beyond the allocation reference to create an extension to meet the stack memory allocation request.

### Claim 46 (depends on 45)

The method of claim 45, wherein the step of establishing a placeholder stack frame comprises the step of establishing the placeholder stack frame between a top of the stack and the stack overflow memory.

### Claim 47 (depends on 45)

The method of claim 45, wherein the initiating step comprises the step of initiating a call to a stack memory allocation instructions that specifies the stack memory allocation request.

### Claim 48

A data processing system for compiling a program that uses a stack and that comprises source code instructions, the data processing system comprising:
a memory comprising a compiler and the source code instructions, the compiler adding stack frame allocation instructions during compilation of the source code instructions, the stack frame allocation instructions for establishing a placeholder stack frame on the stack that extends from the stack to stack overflow memory, and establishing the new stack frame for the program in the stack overflow memory, the compiler further adding stack extension instructions during compilation of the source code instructions, the stack extension instructions for extending an existing stack frame on the stack into the stack overflow memory, the existing stack frame bounded by a frame pointer and a stack pointer, by allocating a memory block in the stack overflow memory, setting an allocation reference to point to the memory block, and setting the stack pointer beyond the allocation reference to create an extension for the existing stack frame; and
a processor that runs the compiler.

### Claim 49 (depends on 48)

The data processing system of claim 48, wherein the compiler further adds instructions for restoring the frame pointer and the stack pointer to bound the placeholder stack frame.

### Claim 50 (depends on 48)

The data processing system of claim 48, wherein the compiler further adds instructions for restoring the frame pointer and the stack pointer to bound a pre-existing stack frame on the stack before the placeholder stack frame.

### Claim 51 (depends on 48)

The data processing system of claim 48, wherein the compiler further adds instructions for allocating a memory block in the stack overflow memory.

### Claim 52 (depends on 51)

The data processing system of claim 51, wherein the compiler further adds instructions for initiating a call to a stack placeholder subroutine.

### Claim 53 (depends on 52)

The data processing system of claim 52, wherein the compiler further adds instructions for searching an allocation table for the memory block.

### Claim 54 (depends on 48)

The data processing system of claim 48 wherein the source code instructions specify an allocation request amount, and wherein the instructions for setting the stack pointer beyond the allocation reference comprise instructions for setting the stack pointer beyond the allocation reference by the allocation request amount.

### Claim 55

A method in a data processing system having a compiler, the method comprising the steps performed by the compiler of:
receiving source code for a program using a stack and comprising instructions; and
generating compiled ones of the instructions that include stack allocation instructions for establishing a placeholder stack frame on the stack that extends from the stack to stack overflow memory, and establishing the new stack frame for the program in the stack overflow memory.

### Claim 56 (depends on 55)

The method of claim 55, wherein the stack comprises an existing stack frame bounded by a frame pointer and a stack pointer, and further comprising the step performed by the compiler of generating compiled ones of the instructions that include stack extension instructions during compilation of the instructions, the stack extension instructions for extending the existing stack frame into the stack overflow memory, by allocating a memory block in the stack overflow memory, setting an allocation reference to point to the memory block, and setting the stack pointer beyond the allocation reference to create an extension for the existing stack frame.

### Claim 57 (depends on 55)

The method of claim 55, further comprising the step performed by the compiler of generating compiled ones of the instructions that include instructions for initiating a call to a stack placeholder subroutine.

### Claim 58

A computer-readable medium containing instructions that cause a data processing system to perform a method comprising the steps performed by a compiler of:
receiving source code for a program using a stack and comprising instructions; and
generating compiled ones of the instructions that include stack allocation instructions for establishing a placeholder stack frame on the stack that extends from the stack to stack overflow memory, and establishing the new stack frame for the program in the stack overflow memory.

### Claim 59 (depends on 58)

The method of claim 58, wherein the stack comprises an existing stack frame bounded by a frame pointer and a stack pointer, and further comprising the step performed by the compiler of generating compiled ones of the instructions that include stack extension instructions during compilation of the instructions, the stack extension instructions for extending the existing stack frame into the stack overflow memory, by allocating a memory block in the stack overflow memory, setting an allocation reference to point to the memory block, and setting the stack pointer beyond the allocation reference to create an extension for the existing stack frame.

### Claim 60 (depends on 58)

The method of claim 58, further comprising the step performed by the compiler of generating compiled ones of the instructions that include instructions for initiating a call to a stack placeholder subroutine.
