# US 2023/0273871 A1 · Incremental stack walking

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

- Number: US 2023/0273871 A1
- Document ID: US20230273871A1
- Status: Published application
- Kind: A1
- Application number: 18/111,423
- Filed: 2023-02-17
- Published: 2023-08-31
- Earliest claimed: 2022-02-28
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Markus Sven Grönlund
- Web page: https://patentgrep.com/patent/US20230273871A1

## CPC

- G06F 11/3636: {by tracing the execution of the program}
- G06F 12/0875: with dedicated cache, e.g. instruction or stack
- G06F 2212/1024: Latency reduction
- G06F 2212/45: Caching of specific data in cache memory
- G06F 2212/451: Stack data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques for incremental stack walking are disclosed, including: performing a stack walk of a runtime stack, at least by traversing the runtime stack from a current frame to a root frame, to obtain a set of stack walking results; storing a cache of the set of stack walking results; and installing, on the runtime stack, a marker frame that marks a boundary of stack frames represented by the set of stack walking results.

## Claims

### Claim 1

One or more non-transitory machine-readable media storing instructions that, when executed by one or more processors, cause performance of operations comprising:
performing a first stack walk of a runtime stack, at least by traversing the runtime stack from a first current frame to a root frame, to obtain a first set of stack walking results;
storing a first cache of the first set of stack walking results;
installing, on the runtime stack, a first marker frame that marks a first boundary of stack frames represented by the first set of stack walking results.

### Claim 2 (depends on 1)

The one or more non-transitory machine-readable media of claim 1, the operations further comprising:
subsequent to performing the first stalk walk of the runtime stack, performing a second stack walk of the runtime stack;
while traversing the runtime stack during the second stack walk, encountering the first marker frame;
responsive to encountering the first marker frame, retrieving the first cache of the first set of stack walking results;
completing the second stack walk without traversing at least one frame represented by the first set of stack walking results.

### Claim 3 (depends on 2)

The one or more non-transitory machine-readable media of claim 2, the operations further comprising:
storing, in a cache lookup table, a hash value corresponding to the first marker frame;
responsive to encountering the first marker frame, performing a cache table lookup of the hash value corresponding to the first marker frame, to obtain the first cache of the first set of stack walking results.

### Claim 4 (depends on 2)

The one or more non-transitory machine-readable media of claim 2, the operations further comprising:
storing a second cache of a second set of stack walking results obtained in the second stack walk, the second set of stack walking results representing at least one frame that is more recent than any frame traversed in the first stack walk;
installing, on the runtime stack, a second marker frame that marks a second boundary of stack frames represented by the second set of stack walking results.

### Claim 5 (depends on 4)

The one or more non-transitory machine-readable media of claim 4, the operations further comprising:
subsequent to performing the second stalk walk of the runtime stack, performing a third stack walk of the runtime stack;
while traversing the runtime stack during the third stack walk, encountering the second marker frame;
responsive to encountering the second marker frame, retrieving the second cache of the second set of stack walking results;
completing the third stack walk without traversing at least one frame represented by the second set of stack walking results.

### Claim 6 (depends on 1)

The one or more non-transitory machine-readable media of claim 1, the operations further comprising:
subsequent to performing the first stack walk of the runtime stack, unwinding a portion of the runtime stack;
while unwinding the portion of the runtime stack, encountering the first marker frame;
responsive to encountering the first marker frame, relocating the first marker frame to an older position in the runtime stack.

### Claim 7 (depends on 6)

The one or more non-transitory machine-readable media of claim 6, the operations further comprising:
subsequent to relocating the first marker frame to the older position in the runtime stack, performing a second stack walk of the runtime stack;
while traversing the runtime stack during the second stack walk, encountering the first marker frame;
responsive to encountering the first marker frame, determining that no cache corresponding to the older position in the runtime stack is available;
responsive to determining that no cache corresponding to the older position in the runtime stack is available, completing the second stack walk at least by traversing the runtime stack from the older position in the runtime stack to the root frame.

### Claim 8

A system comprising:
at least one device comprising one or more hardware processors,
the system being configured to perform operations comprising:
performing a first stack walk of a runtime stack, at least by traversing the runtime stack from a first current frame to a root frame, to obtain a first set of stack walking results;
storing a first cache of the first set of stack walking results;
installing, on the runtime stack, a first marker frame that marks a first boundary of stack frames represented by the first set of stack walking results.

### Claim 9 (depends on 8)

The system of claim 8, the operations further comprising:
subsequent to performing the first stalk walk of the runtime stack, performing a second stack walk of the runtime stack;
while traversing the runtime stack during the second stack walk, encountering the first marker frame;
responsive to encountering the first marker frame, retrieving the first cache of the first set of stack walking results;
completing the second stack walk without traversing at least one frame represented by the first set of stack walking results.

### Claim 10 (depends on 9)

The system of claim 9, the operations further comprising:
storing, in a cache lookup table, a hash value corresponding to the first marker frame;
responsive to encountering the first marker frame, performing a cache table lookup of the hash value corresponding to the first marker frame, to obtain the first cache of the first set of stack walking results.

### Claim 11 (depends on 9)

The system of claim 9, the operations further comprising:
storing a second cache of a second set of stack walking results obtained in the second stack walk, the second set of stack walking results representing at least one frame that is more recent than any frame traversed in the first stack walk;
installing, on the runtime stack, a second marker frame that marks a second boundary of stack frames represented by the second set of stack walking results.

### Claim 12 (depends on 11)

The system of claim 11, the operations further comprising:
subsequent to performing the second stalk walk of the runtime stack, performing a third stack walk of the runtime stack;
while traversing the runtime stack during the third stack walk, encountering the second marker frame;
responsive to encountering the second marker frame, retrieving the second cache of the second set of stack walking results;
completing the third stack walk without traversing at least one frame represented by the second set of stack walking results.

### Claim 13 (depends on 8)

The system of claim 8, the operations further comprising:
subsequent to performing the first stack walk of the runtime stack, unwinding a portion of the runtime stack;
while unwinding the portion of the runtime stack, encountering the first marker frame;
responsive to encountering the first marker frame, relocating the first marker frame to an older position in the runtime stack.

### Claim 14 (depends on 13)

The system of claim 13, the operations further comprising:
subsequent to relocating the first marker frame to the older position in the runtime stack, performing a second stack walk of the runtime stack;
while traversing the runtime stack during the second stack walk, encountering the first marker frame;
responsive to encountering the first marker frame, determining that no cache corresponding to the older position in the runtime stack is available;
responsive to determining that no cache corresponding to the older position in the runtime stack is available, completing the second stack walk at least by traversing the runtime stack from the older position in the runtime stack to the root frame.

### Claim 15

A method comprising:
performing a first stack walk of a runtime stack, at least by traversing the runtime stack from a first current frame to a root frame, to obtain a first set of stack walking results;
storing a first cache of the first set of stack walking results;
installing, on the runtime stack, a first marker frame that marks a first boundary of stack frames represented by the first set of stack walking results,
wherein the method is performed by at least device comprising one or more hardware processors.

### Claim 16 (depends on 15)

The method of claim 15, further comprising:
subsequent to performing the first stalk walk of the runtime stack, performing a second stack walk of the runtime stack;
while traversing the runtime stack during the second stack walk, encountering the first marker frame;
responsive to encountering the first marker frame, retrieving the first cache of the first set of stack walking results;
completing the second stack walk without traversing at least one frame represented by the first set of stack walking results.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
storing, in a cache lookup table, a hash value corresponding to the first marker frame;
responsive to encountering the first marker frame, performing a cache table lookup of the hash value corresponding to the first marker frame, to obtain the first cache of the first set of stack walking results.

### Claim 18 (depends on 16)

The method of claim 16, further comprising:
storing a second cache of a second set of stack walking results obtained in the second stack walk, the second set of stack walking results representing at least one frame that is more recent than any frame traversed in the first stack walk;
installing, on the runtime stack, a second marker frame that marks a second boundary of stack frames represented by the second set of stack walking results.

### Claim 19 (depends on 18)

The method of claim 18, further comprising:
subsequent to performing the second stalk walk of the runtime stack, performing a third stack walk of the runtime stack;
while traversing the runtime stack during the third stack walk, encountering the second marker frame;
responsive to encountering the second marker frame, retrieving the second cache of the second set of stack walking results;
completing the third stack walk without traversing at least one frame represented by the second set of stack walking results.

### Claim 20 (depends on 15)

The method of claim 15, further comprising:
subsequent to performing the first stack walk of the runtime stack, unwinding a portion of the runtime stack;
while unwinding the portion of the runtime stack, encountering the first marker frame;
responsive to encountering the first marker frame, relocating the first marker frame to an older position in the runtime stack.

### Claim 21 (depends on 20)

The method of claim 20, the operations further comprising:
subsequent to relocating the first marker frame to the older position in the runtime stack, performing a second stack walk of the runtime stack;
while traversing the runtime stack during the second stack walk, encountering the first marker frame;
responsive to encountering the first marker frame, determining that no cache corresponding to the older position in the runtime stack is available;
responsive to determining that no cache corresponding to the older position in the runtime stack is available, completing the second stack walk at least by traversing the runtime stack from the older position in the runtime stack to the root frame.
