FIELD OF INVENTION:
The invention relates to a device and method to detect stack overflow and/or stack underflow in a microcontroller or a microprocessor or in any processing device dealing with stack memory.
BACKGROUND OF THE INVENTION:
Method to detect stack overflow and underflow is known in the prior art. The US patent 7380245B1 discloses one such method where in after every push or pop operation a guard function checks whether the stack area has encountered an overflow or underflow respectively.
ADVANTAGES OF THE INVENTION:
The invention proposes a method wherein a monitoring routine checks for stack overflow/underflow at predetermined intervals. The predetermined interval may be achieved through trigger from a time dependant interrupt or alternatively the monitoring routine may be scheduled at regular inten/als. Early detection of the stack overflow/underflow will provide the processing device a chance to initiate the corrective measures.
The invention proposes a method to store the state of the processing device and if necessary to generate a hardware reset to the processing device.
BRIEF DESCRIPTION OF THE DRAWINGS:
Figure 1 Shows the schematic of the invention
Figure 2 Shows the stack memory along with the guard bands

DESCRIPTION OF THE INVENTION:
Shown in fig. 1 is an electronic device 1 comprising a processing device 10, a memory whicii is not shown, containing at least one task/function stored in the memory to control the electronic device, an external timer unit 12 which generates an interrupt 14 at predefined intervals to the processing device 10. Alternatively the processing device 10 may use an internal timer unit 16, if available, to generate the said interrupt at predefined intervals. The processing device 10 outputs a hardware reset signal 18 triggered by a hardware reset input 20. Alternatively the processing device can generate a hardware reset signal when it executes a specific instruction. The monitoring routine which is not shown in figure, is organized as an interrupt service routine in the memory which is not shown. Under this case the monitoring routine gets executed by the trigger of the interrupt. Alternatively the monitoring routine may be organized as a function which is scheduled by the scheduler run by the processing device. The scheduler runs the monitoring function at predetermined intervals.
The electronic device 1 may contain plurality of tasks which are not shown, which are stored in the memory. The tasks are run by the processing device either using a scheduler or any other mechanism. The tasks are a set of instructions to the processing device.
Shown in fig. 2 is a stack memory 50 along with guard bands 52 and 54 at the beginning and end of the stack memory. The stack memory comprises a plurality of memory locations. In the figure only one arrangement of stack memory along with guard bands is shown as example, but there may be a plurality of such arrangements, each arrangement assigned to one task run by the programming device. The size of the stack memories may vary for different tasks. Each task knows the size of the stack memory which is assigned to it. A predefined pattern, for example, 0XAA55H, is stored in the guard bands. With every 'PUSH' operation of the processing device, the contents to be pushed are stored in the stack memory, in a memory location currently pointed by the stack pointer, which is not shown. After the PUSH operation the stack pointer points to

next memory location for pushing. Similarly with a POP operation, the contents from the stack memory location are read out. Also whenever any switching between the functions/tasks takes place, the data related to the functions/tasks is stored in the stack memory. With every operation affecting the stack memory, the stack pointer is adjusted appropriately.
A stack overflow happens when the processing device utilizes stack memory locations more than what is assigned to it, i.e. when it stores more data on to the stack than the stack memory available to it. Similarly a stack underflow happens when the processing devices tries to read more data than what it has stored on to the stack memory.
The detection of the stack overflow is explained below with an example. The examples are with reference to a current task executed by the processing device.
Assume that the stack memory for one of the tasks is from 1001H to 1050H. Assume that the stack memory beginning is at 1001H and end is 1050H. Initially the stack pointer is pointing to beginning of the stack 1001H and with each data storage on the stack, the stack pointer is appropriately updated. The guard band will be located in 1000H and 1051H and contain a predefined pattern.
Initially when the processing device begins its operation on power on, different tasks begin running; the stack pointer is initialized to the beginning of the stack of the current task, i.e. 1001H for the task mentioned above. Whenever the current task stores data on to the stack by either push operation or through switching between functions/tasks, the stack pointer is appropriately adjusted to point to the next memory location in the stack memory where the next data will be stored with next storage operation of the stack. So the stack pointer contents will have a new value between 1001H and 1050H with each stack operation.
Assume that the task has used all the available stack memory form 1001H to 1050H, for example. Now the stack pointer is pointing to 1051H where the guard band is located.

When the monitoring routine runs, it compares the contents of the guard bands with the predefined pattern. In the above case, as the processing device has used stacl< memory up to 1050H, the guard band 1051H still contains the predefined pattern.
Assume the task performs a PUSH operation or a switching between functions/tasks. A new data is written on to the stack memory at a location pointed to by the stack pointer, i.e. data is stored from the location 1051H pointed by the stack pointer in the above example. As the same location has the guard band 54, the guard band 54 gets corrupted. When the monitoring routine runs next time, it finds that the guard band 54 is corrupted and the stack overflow is detected.
Once the stack overflow is detected, the monitoring routine stores the status of the current task which caused the stack overflow, for future diagnosis. The monitoring routine may generate a warning signal and may execute some specific instructions which result in resetting the processing device to a known state and generating a hardware reset signal 18.
The underflow of the stack is detected indirectly as explained below:
Assume that the stack memory is empty now, so the stack pointer is pointing to the beginning of the stack memory 1001H. Assume the task tries to retrieve data from the stack memory. The stack pointer changes from, 1001H to 1000H and contents of 1000H are retrieved. When the stack pointer is pointing to 1000H, with next stack storage operation, the data is stored on 1000H overwriting the guard band. When the monitoring routine runs next time, it finds that the guard band 52 at the beginning of the stack memory is overwritten and detects a stack underflow Indirectly.
The invention also proposes a method to detect the corruption of the stack pointer. If at any time the content of the stack pointer is greater than the memory address of the end of the stack memory, then the stack pointer is no more valid. It is declared to be corrupted. Similarly if at any time the content of the stack pointer is lesser than the

memory address of the beginning of the stacl< memory, then the stack pointer is no more valid. It is declared to be corrupted.
Once a stack underflow or stack overflow Is detected or the stack pointer is found corrupted, the monitoring routine can initiate different restoration actions based on the state of the current task and also based on the state of the processing device 10. In some cases, the monitoring routine may store the state of the current task, re-initialize the stack memory and the stack pointer and restart the current task. In other cases, the monitoring routine may store the state of the current task and execute instructions to reset the processing device and also to generate a hardware reset signal which is used by other devices connected to the processing device to synchronize with the processing device.
In the above examples, the stack pointer is shown as growing upwards, i.e. when a data is stored on to the stack memory, the stack pointer is incremented. But in some processing devices, the stack pointer may grow down with data storage on to the stack memory. The above examples are only for illustration and there may be different variations to the examples.

WE CLAIM:
1. A method to detect overflow and/or underflow of a stack memory (50) and/or
corruption of a stack pointer of a processing device (10), the method comprising
the steps:
- assigning a guard band at the beginning and end of the stack memory
(50)
- storing a predetermined pattern in the guard bands (52, 54)
- running a monitoring routine triggered by a time dependant interrupt or
scheduled by a scheduler, to determine whether the stack overflow and/or
stack underflow has occurred, by comparing the contents of the guard
bands (52, 54) with a predefined pattern and/or to determine whether the
stack pointer is corrupted by checking whether the content of the stack
pointer is outside of a predetermined range
2. A method according to claim 1 wherein, on detection of an underflow and/or
overflow of the stack memory (50), the state of the processing device (10) is
stored in a non volatile memory.
3. A method according to claim 1 wherein on detection of an underflow and/or
overflow of the stack memory (50), the processing device (10) is reset.
4. A method according to claim 1 wherein on detection of an underflow and/or
overflow of the stack memory (50), the processing device is instructed to
generate a hardware reset signal (18).
5. A method according to claim 1 wherein, on detection of corruption of the stack
pointer, the state of the processing device (10) is stored in a non volatile
memory.

6. A method according to claim 1 wherein on detection of corruption of the stacl<
pointer, the processing device (10) is reset.
7. A method according to claim 1 wherein on detection of corruption of the stack
pointer, the processing device is instructed to generate a hardware reset signal
(18).
8. An electronic device (1) comprising a processing device (10) to run at least one
task, a memory to store the said task, a stack memory (50) to store the data
while performing stack operations, a guard band (52) at the beginning of the said
stack memory (50) and a guard band (54) at the end of the said stack memory
(50), the said guard bands (52, 54) containing a predefined pattern, the said
processing device (10) comprising a stack pointer pointing to a location in the
said stack memory 50), the said processing device (10) characterized by:
- a monitoring routine adapted to run on trigger of a time dependant interrupt or scheduled by a scheduler, to determine whether the stack overflow and/or stack underflow has occurred by comparing the contents in the guard bands (52, 54) with a predefined pattern and/or to determine whether the stack pointer is corrupted by checking whether the content of the stack pointer is outside of a predetermined range.