Stack overflow prevention in parallel execution runtime

Patent metadata

Field	Value
Publication number	US-9928105-B2
Application number	US-82433110-A
Country	US
Kind code	B2
Filing date	Jun 28, 2010
Priority date	Jun 28, 2010
Publication date	Mar 27, 2018
Grant date	Mar 27, 2018

Abstract

A parallel execution runtime prevents stack overflow by maintaining an inline counter for each thread executing tasks of a process. Each time that the runtime determines that inline execution of a task is desired on a thread, the runtime determines whether the inline counter for the corresponding thread indicates that stack overflow may occur. If not, the runtime increments the inline counter for the thread and allows the task to be executed inline. If the inline counter indicates a risk of stack overflow, then the runtime performs additional one or more checks using a previous stack pointer of the stack (i.e., a lowest known safe watermark), the current stack pointer, and memory boundaries of the stack. If the risk of stack overflow remains after all checks have been performed, the runtime prevents inline execution of the task.

First claim

What is claimed is:

1. A method performed by a computer system, the method comprising:
determining whether inline execution of a task on a first thread may cause a stack to overflow using a current stack pointer and a lowest known safe watermark, the determining performed by a runtime configured to allow the task to be executed concurrently with a set of other tasks from user code, the lowest known safe watermark is the deepest position in the stack by a previous stack pointer that was determined to be safe;
preventing the task from being executed inline on the first thread in response to the determining that stack overflow may occur;
in response to the determining that the current stack pointer and the lowest known safe watermark indicate that the inline execution may cause the stack to overflow, using the current stack pointer and a memory boundary of the stack to determine whether the inline execution will actually cause the stack to overflow; and
executing the task inline on the first thread in response to determining that the current stack pointer and the memory boundary indicate that the inline execution will not cause the stack to overflow.

2. The method of claim 1 further comprising:
executing the task with a second thread in response to determining that inline execution of the task on the first thread may cause the stack to overflow; and
blocking the first thread until the task completes execution on the second thread.

3. The method of claim 1 further comprising:
executing the task with the first thread in response to determining that inline execution of the task on the first thread will not cause the stack to overflow.

4. The method of claim 1 further comprising:
determining whether the inline execution of the task on the first thread may cause the stack to overflow using an inline counter corresponding to the first thread.

5. The method of claim 4 further comprising:
executing the task inline on the first thread in response to determining that the inline counter does not exceed a threshold; and
incrementing the inline counter in response to the executing the task inline on the first thread.

6. The method of claim 5 further comprising:
decrementing the inline counter in response to the task returning from execution on the first thread.

7. The method of claim 1 further comprising:
determining whether the inline execution of the task on the first thread may cause the stack to overflow using a memory boundary of the stack queried from an operating system.

8. The method of claim 1 further comprising:
executing the task with a second thread in response to determining that the current stack pointer and the memory boundary indicate that the inline execution may cause the stack to overflow.

9. A method performed by a computer system, the method comprising:
maintaining an inline counter corresponding to a first thread that identifies a number of inline executions being performed by the first thread;
determining, with the inline counter, whether inline execution of a task on the first thread may cause a stack to overflow, the determining performed by a runtime configured to allow the task to be executed concurrently with a set of other tasks from user code;
determining, using a current stack pointer and a lowest known safe watermark, whether the inline execution of the task on the first thread may cause the stack to overflow, the lowest known safe watermark is the deepest position in the stack by a previous stack pointer that was determined to be safe;
preventing the task from being executed inline on the first thread in response to the determining that stack overflow may occur;
in response to the determining that the current stack pointer and the lowest known safe watermark indicate that the inline execution may cause the stack to overflow, using the current stack pointer and a memory boundary of the stack to determine whether the inline execution will actually cause the stack to overflow; and
executing the task inline on the first thread in response to determining that the current stack pointer and the previous stack pointer indicate that the inline execution will not cause the stack to overflow.

10. The method of claim 9 further comprising:
executing the task inline on the first thread in response to determining that the inline counter indicates that the inline execution will not cause the stack to overflow.

11. The method of claim 9 further comprising:
incrementing the inline counter in response to executing the task inline on the first thread.

12. The method of claim 9 further comprising:
decrementing the inline counter in response to the task returning from execution on the first thread.

13. A computer readable storage medium, which does not include transitory propagating signals, storing computer-executable instructions that, when executed by a computer system, perform a method comprising:
comparing an inline counter corresponding to a first thread to a first threshold in response to determining that inline execution of a task on the first thread is desired;
comparing a current stack pointer and a previous stack pointer that was determined to be safe in response to the inline counter exceeding the first threshold;
executing the task inline on the first thread in response to the inline counter being less than the first threshold; and
incrementing the inline counter in response to executing the task inline on the first thread.

14. The computer readable storage medium of claim 13 , the method further comprising:
executing the task inline on the first thread in response to the current stack pointer being above the previous stack pointer.

15. The computer readable storage medium of claim 14 , the method further comprising:
in response to the current stack pointer being below the previous stack pointer, comparing the current stack pointer to a memory boundary of the stack; and
executing the task inline on the first thread in response to an amount of memory space between the current stack pointer and the memory boundary exceeding a second threshold.

16. The computer readable storage medium of claim 15 , the method further comprising:
storing the current stack pointer as a lowest known safe watermark in response to the amount of memory space exceeding the second threshold.

17. The computer readable storage medium of claim 16 , the method further comprising:
in response to the amount of memory space not exceeding the second threshold, executing the task with a second thread.

Assignees

• Yildiz Huseyin S
• Duffy John J
• Microsoft Technology Licensing Llc

Inventors

• Yildiz Huseyin S
• Duffy John J

Classifications

• G06F9/45504

  Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators · CPC title

• G06F11/004

  Error avoidance (G06F11/07 and subgroups take precedence) · CPC title

• G06F11/0751

  Error or fault detection not based on redundancy (power supply failures G06F1/30; network fault management H04L41/06) · CPC title

• G06F2009/45583

  Memory management, e.g. access or allocation · CPC title

• G06F9/4843 Primary

  by program, e.g. task dispatcher, supervisor, operating system · CPC title