 |
Claims  |
|
|
What is claimed is:
1. A system for generating an early indication of a fault in the operation
of a computer program due, for example, to a coding error, or a fault in
the operation of a computer based dedicated controller due to an error in
its construction, design, programming, or due, for example, to a failed
component, before the fault results in the generation of an incorrect
output, said system comprising:
means for monitoring output signals of a CPU of a data processing system
under test;
means for independently assigning to each and every location in a
computer's memory space one code selected from a set of three or more
codes, the code defining at least one condition which, if true when the
memory location is accessed during the program's execution, is an
indication of a fault in the operation of the program or controller;
means for determining, on every access to a memory location during the
program's execution, if the condition, defined by the code assigned to the
memory location, is true when the memory location is being accessed; and
means for generating an output indicating whether the condition is true.
2. A system according to claim 1, wherein the means for assigning comprises
a memory containing a location for each location in the computer's memory
space, addressed by the CPU's Address bus.
3. A system according to claim 1, wherein the means for determining
comprises a combinational logic circuit that, on every access to a memory
location during the program's execution, generates an output indicating
whether the condition is true, as a function of:
the code assigned to the memory location accessed; and
the Control/Status signals generated by the CPU.
4. A system according to claim 1, wherein said means for determining
comprises a state machine logic circuit that, on every access to a memory
location during the program's execution, selects a next state of the state
machine, and generates an output indicating whether the condition is true,
as a function of:
the state machine's present state;
the code assigned to the memory location accessed; and
the Control/Status signals from the CPU.
5. A system according to claim 1, further comprising means for changing
said code assigned to a memory location when, as a result of the program's
execution, the condition changes which, if true when said memory location
is accessed during the program's execution, is an indication of a fault in
the operation of the program or controller.
6. A system according to claim 5, wherein said means for determining and
said means for changing are a combinational logic circuit that, on every
access to a memory location, determines a fault output signal as a
function of said code and said Control/Status signals, and, if a code
change is indicated by said fault output signal, selects a new code and
assigns the new code to said memory location.
7. A system according to claim 5, wherein said means for determining and
said means for changing are a state machine logic circuit that, on every
access to a memory location, determines a fault output signal and selects
the state machine's next state as a function of said state machine's
present state, said code and said Control/Status signals, and, if a code
change is indicated by said fault output signal, selects a new code and
assigns the new code to said memory location.
8. A system for generating an early indication of a fault in the operation
of a computer program due, for example, to a coding error, or a fault in
the operation of a computer based dedicated controller due, for example,
to an error in its construction, design, programming, or due to a failed
component, before the fault results in the generation of an incorrect
output from the computer, said system comprising:
(a) means for assigning, to each location in the computer's memory space, a
code indicating when the memory location is expected to be accessed during
the program's execution;
(b) means for generating a truncated numerical difference between the
present memory address and the previous memory address;
(c) means for determining, when a memory location is accessed during the
program's execution, if the access to the memory location was expected, as
a function of:
the code assigned to the memory location accessed;
the Control/Status signals generated by the CPU when the memory location is
accessed; and
the truncated numerical difference between the present memory address and
the previous memory address; and
(d) means for generating an output indicating that the access to the memory
location is unexpected.
9. A system according to claim 8, wherein said means for assigning is a
memory containing a location for each location in the computer's memory
space addressed by the CPU's Address bus.
10. A system according to claim 8, wherein the truncated numerical
difference between the present memory address and the previous memory
address generated by the means for generating is a single logic signal
indicating if the present memory address is one greater than the previous
memory address.
11. A system according to claim 8, wherein said means for determining is
provided by a combinational logic circuit that generates an output
indicating if the access to the memory location is unexpected, as a
function of:
the present code assigned to the memory location being accessed by the CPU;
the present Control/Status signals generated by the CPU; and
the present truncated numerical difference between the present memory
address and the previous memory address.
12. A system according to claim 8, wherein said means for determining is
provided by a sequential logic circuit that generates an output indicating
if the access to the memory location is unexpected, as a function of:
the present and past codes assigned to the memory locations being accessed
by the CPU;
the present and past Control/Status signals generated by the CPU; and
the present and past truncated numerical differences between the present
memory address and the previous memory address.
13. A system according to claim 8, further comprising means for changing
said code assigned to a memory location when, as a result of the program's
execution, the expectation changes regarding when said memory location is
expected to be accessed.
14. A system according to claim 13, wherein said means for determining and
said means for changing are a combinational logic circuit that, on every
access to a memory location, determines a fault output signal as a
function of said code and said Control/Status signals, and, if a code
change is indicated, selects a new code and assigns the new code to said
memory location.
15. A system according to claim 13, wherein said means for determining and
said means for changing are a state machine logic circuit that, on every
access to a memory location, determines a fault output signal and selects
the state machine's next state as a function of said state machine's
present state, said code and said Control/Status signals, and, if a code
change is indicated, selects a new code and assigns the new code to said
memory location.
16. A system for generating an early indication of a fault in the operation
of a computer program due, for, example, to a coding error, or a fault in
the operation of a computer based dedicated controller due, for example,
to an error in its construction, design, programming, or due to a failed
component or noise, before the fault results in the generation of an
incorrect output from the computer, said system comprising:
(a) means for assigning, to each location in the computer's memory space, a
code indicating when the memory location is expected to be accessed during
the program's execution;
(b) first means for generating a truncated numerical difference between a
present memory address and a previous memory address;
(c) second means for generating a truncated numerical difference between
the present memory address and the previous memory address used to access
a memory location assigned an instruction Op-Code or Operand;
(d) means for determining, when a memory location is accessed during the
program's execution, if the access to the memory location was expected, as
a function of:
the code assigned to the memory location accessed;
the Control/Status signals generated by the CPU when the memory location is
accessed;
the truncated numerical difference between the present memory address and
the previous memory address; and
the truncated numerical difference between the present memory address and
the previous memory address used to access a memory location assigned an
instruction Op-Code or Operand; and
(e) means for generating an output indicating if the access to the memory
location is unexpected.
17. A system according to claim 16, wherein the means for assigning
comprises a memory containing a location for each location in the
computer's memory space addressed by the CPU's Address bus.
18. A system according to claim 16 wherein the truncated numerical
difference between the present memory address, and the previous memory
address generated by the first means for generating is a single logic
signal indicating if the present memory address is one greater than the
previous memory address.
19. A system according to claim 16 wherein the truncated numerical
difference between the present memory address and the previous memory
address used to access an instruction Op-Code or operand generated by the
second means for generating is a single logic signal indicating if the
present memory address is one greater than the previous memory address
used to access an instruction Op-Code or Operand.
20. A system according to claim 16, wherein the means for determining is
provided by a combinational logic circuit that generates an output
indicating if the access to the memory location is expected, as a function
of only:
the present code assigned to the memory location accessed by the CPU;
the present Control/Status signals generated by the CPU;
the present truncated numerical difference between the present memory
address and the previous memory address; and
the present truncated numerical difference between the present memory
address and the previous memory address used to access a memory location
assigned an instruction Op-Code or Operand.
21. A system according to claim 16, wherein the means for determining is
provided by a sequential logic circuit that generates an output indicating
if the access to the memory location is expected, as a function of:
the present and past codes;
the present and past Control/Status signals generated by the CPU;
the present and past truncated numerical difference between the present
memory address and the previous memory address; and
the present and past truncated numerical difference between the present
memory address and the previous memory address used to access a memory
location assigned an instruction Op-Code or Operand.
22. A method of generating an early indication of a fault in the operation
of a computer program due, for example, to a coding error, or a fault in
the operation of a computer based dedicated controller due, for example,
to an error in its construction, design, programming, or due to a failed
component, before the fault results in the generation of an incorrect
output from the computer, said method comprising the steps of:
assigning, to each location in the computer's memory space, a code selected
from a set of three or more codes, the code defining at least one
condition which, if true when the memory location is accessed during the
program's execution, is an indication of a fault in the operation of the
program or controller;
determining, on every access to a memory location during the program's
execution, if the condition specified by the code assigned to the memory
location accessed is true; and
generating an output indicating that the memory location is accessed
incorrectly if the condition specified by the code is true.
23. A method according to claim 22, further comprising changing said code
assigned to a memory location when, as a result of the program's
execution, the condition changes which, if true when said memory location
is accessed during the program's execution, is an indication of a fault in
the operation of the program or controller.
24. A method according to claim 23, wherein said step of determining and
said step of changing are performed by a combinational logic circuit.
25. A method according to claim 23, wherein said step of determining and
said step of changing are performed by a state machine logic circuit. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
FIELD OF THE INVENTION
This invention relates to structure and method for generating an early
indication of a failure in the operation of a computer program, or a
computer based controller and more particularly to the early detection of
a failure in a computer program or a computer based controller by testing
every memory access, and machine cycle performed during the program's
execution for a departure from the memory access and machine cycle
sequence expected by the programmer.
PRIOR ART
Heretofore, the primary method used to detect a failure in the execution of
a computer program or the operation of a computer based controller, was by
comparing output signals generated in response to input signals against
the output signals expected by the programmer.
The objective of a computer program, or computer based controller is to
implement a specified Input/Output function.
With very few exceptions, when a program is executed to implement an
Input/Output function, each output signal is generated as a result of a
long complex sequence of internal operation. If any one of the internal
operations required to generate the correct output signal fails to perform
the function it is expected to perform, an incorrect output signal will be
generated, and the program will fail to implement the Input/Output
function the programmer expected it to perform.
The failure of an internal operation to perform the function it is expected
to perform may be due to: a program coding error, an error in the design
or construction of the hardware, electrical noise, or a failed component.
In most cases, after an internal operation fails to implement the function
it is expected to perform, a significant amount of time may elapse, and
many internal operations will have been performed before an incorrect
output signal is generated due to the failure.
It is very difficult, in almost all cases, to determine from an incorrect
output signal which internal operation failed to perform the function it
was expected to perform.
During the development of a computer program or a computer based controller
a significant amount of time is spent searching for the faulty internal
operation that resulted in the generation of an incorrect output. In
almost all cases, the search is started from the point in the execution of
the program when an incorrect output is generated.
In some applications, the failure of a computer based controller to operate
properly may result in significant damage, or loss of life. In a critical
application, a fault in the operation of a computer based controller must
be detected before the controller generates a faulty output.
Heretofore, a "Watch Dog Timer" was a common method used to detect a
failure of a critical non-redundant computer based controller to operate
as required.
The "Watch Dog Timer" is expected to be restarted at a regular interval by
the program, before the time it is set for expires. If the "Watch Dog
Timer" times-out it is a certain (but often not an early) indication of a
failure. Before the "Watch Dog Timer" times-out, indicating a failure, it
is possible for the program to generate an incorrect output signal.
In many cases, a simple .real time program for starting the Watch Dog Timer
will consist of a loop of program segments, and subroutine Calls as
illustrated below.
______________________________________
MAIN: CALL SUB0; Call first subroutine. (program
segment 0 )
CALL SUB1; Call second subroutine.
CALL SUB2; Call third subroutine. (program
segment 1)
* * * Sequence of Subroutine Calls and Program
segments.
CALL SUBN; Call last operation subroutine.
CALL RWDT; Call Restart Watch Dog Timer.
JMP MAIN; Go Back to top of MAIN loop.
______________________________________
In a more complex example, a Task Dispatcher program selects the next
subroutine to be executed, based upon flags set by interrupt programs.
After each subroutine is executed the Task Dispatcher restarts the Watch
Dog Timer.
The time out of the Watch Dog timer will in most applications be used to
Reset the CPU or generate a non-maskable Interrupt. The Reset, or
Interrupt program will set outputs to a safe state, and generate an output
indicating the system has failed.
A Watch Dog Time can only detect when the program loses control of the
program counter. When control of the program counter is lost, an output
program may be executed generating an incorrect output before the Watch
Dog Timer times out.
Many types of program execution faults that may result due to a failed
component, or electrical noise will NOT be detected by a Watch Dog Timer.
A Watch Dog Timer can not detect Data Read or Write accesses by the program
to an incorrect memory location, or a minor deviation from the expected
instruction execution sequence.
An incorrect Data memory location access, or a slight deviation from the
expected instruction execution sequence may result if the CPU reads an
incorrect Instruction Op-Code or Operand from the Instruction/Data bus.
During the system's operation, there is high probability that a failure of
a component, or interference by electrical noise will result in a memory
access unexpected by the programmer before an incorrect output is
generated by the system.
Or during the system's operation, an input sequence not provided during the
fault location process may result in a memory access unexpected by the
programmer.
The use of a Watch Dog Timer is analogous to a Night Watch Man making
periodic inspections of all the doors and windows in a building, while the
automatic testing of every memory access in accordance with this invention
is analogous to the installation of a burglar alarm system that
continuously tests all doors and window.
SUMMARY OF THE INVENTION
The method and structure in accordance with this invention reduces the
amount of time required to locate many common types of coding or hardware
faults by automatically testing every memory access during the program's
execution for conformity to the memory access sequence expected by the
programmer, which is clearly defined by the coding of the program.
Inherent in the coding of a program is a definition of when the programmer
expects each memory location to be accessed during the program's
execution.
An access to a memory location during a program's execution that does not
conform to the sequence expected by the programmer is a certain and early
indication of a fault, and a program execution history trace terminated
when this occurs is certain to provide information relevant to the
location or type of the fault.
Many common coding and hardware faults result in an unexpected access to a
memory location significantly prior to the generation of an incorrect
output by the program. Less time will be required to find a coding or
hardware fault if the search for the fault is started from the point in
the execution of the program where an unexpected memory access occurred.
In accordance with this invention, a definition of a program, and the
instruction set of the CPU on which the program is run, is converted into
a definition of the memory access, and machine cycle sequence expected by
the programmer during the program's execution. During the program's
execution, by hardware or a software execution simulator, every memory
access, and machine cycle is tested for a departure from the memory access
and machine cycle sequence expected by the programmer. When a memory
access or machine cycle departs from the sequence expected by the
programmer, a Fault indication is generated and when, due to the program's
execution, the programmer's expectations in regards to when a memory
location will be accessed changes, the memory location's expected access
sequence definition is updated to the new programmer's expectation.
This invention has particular utility in locating the source of certain
types of errors in the coding of a program during its development, or in
the programming, design, and/or construction of a computer based
controller during its development. When a computer based controller is
used in a critical application (in which the generation of an incorrect
output could result in the loss of life, or significant property damage),
the method of this invention can be used to generate a signal indicating a
failure in the controller's operation before an incorrect output is
generated. This signal can be used to force the outputs of the controller
to a safe condition and to provide an alarm.
There are two primary applications for this invention:
1. Fault location during development of a computer program or a computer
based controller, and
2. Monitoring the operation of a critical computer based controller.
DESCRIPTION OF DRAWINGS
FIG. 1 shows a basic semi-automatic program execution error detector
consisting of an access sequence break-point memory 30 and a combinational
or sequential fault detection logic 40.
FIG. 2 shows a semi-automatic program execution error detector with ROM
access sequence break-point memory for monitoring critical computer-based
controller.
FIG. 3 shows a semi-automatic program execution error detector with
plus-one memory address generator.
FIG. 4 shows a plus-one generator whose output is true when the present
memory address is one greater than the last.
FIG. 5 shows a semi-automatic program execution error detector for an 8085
microprocessor based computer.
FIG. 6 shows state machine sequential fault detection logic for the 8085
microprocessor semi-automatic program execution error detector.
FIG. 7 shows the output from a computer system under test to assist in the
debugging of a Program or a Computer Based Controller. The Logic Analyzer
is set up to terminate the collection of a Program Execution History trace
when the ACCESS SEQUENCE FAULT output goes True.
FIG. 8 shows the inclusion of a Semi-automatic Program Execution Error
Detector in the design of a Critical Computer Based Controller. The ASBP
memory is provided by extending the width of the computer's memory, and
the ACCESS SEQUENCE FAULT output is connected to generate a Non-Maskable
Interrupt.
FIG. 9 shows the Semi-automatic Program Execution Error Detector added to a
Critical Computer Based Controller as a separate section.
FIGS. 10, 11 and 12 show the extension of the Memory Address Delta concept:
expanding the Delta range beyond the simple Plus-One output; and also
tracking the Program Counter Delta.
FIG. 13 shows the 8085 Semi-automatic Program Execution Error Detector with
logic added to load the ACCESS SEQUENCE BREAK-POINT MEMORY.
DETAILED DESCRIPTION
As shown in FIG. 1, basic Semi-automatic Program Execution Error Detector
consists of an ACCESS SEQUENCE BREAK-POINT MEMORY 30 and a COMBINATIONAL,
OR SEQUENTIAL FAULT DETECTION LOGIC 40.
The ACCESS SEQUENCE BREAK-POINT MEMORY 30 assigns to every location in the
computer's memory space an Access Sequence Break-Point "ASBP" code 31
indicating when the programmer expects the memory location will be
accessed during the program's execution. The Computer's ADDRESS BUS 100
provides the address to the ACCESS SEQUENCE BREAK-POINT MEMORY 30,
selecting the ASBP code 31 assigned to the memory location accessed by the
computer.
The selected ASBP code 31 output is provided as an input to the
COMBINATIONAL OR SEQUENTIAL FAULT DETECTION LOGIC 40.
The COMBINATIONAL, OR SEQUENTIAL FAULT DETECTION LOGIC 40 generates an
ACCESS SEQUENCE FAULT output 41 as a function of: inputs from the
Computer's CONTROL BUS 200; the ASBP code 31 selected by the Computer's
ADDRESS BUS 100; and if the fault detection logic is sequential, the
present state of the logic.
As shown in FIG. 2, when a Semi-automatic Program Error Detector is used to
monitor the operation of a critical computer based controller, a ROM may
be used for the ACCESS SEQUENCE BREAK-POINT MEMORY 30. With a 2 bit Access
Sequence Break-Point code 31A & 31B the programmer's memory access
sequence expectations may be encoded as shown in Table A.
TABLE A
______________________________________
Two bit Basic Access Sequence Break-Point set.
31A 31B
______________________________________
BP1 BPO Programmer's Expectations.
L L No access expected.
L H Op-Code access only expected.
H L Read Only access expected.
H H Data Read or Write access expected.
______________________________________
With commonly available CONTROL BUS signals: RD/WR 206 (R/W); an OP-CODE
FETCH 207 (OCF); and a MEMORY ACCESS STROBE 208 (MAS), the TRUTH TABLE for
the ACCESS SEQUENCE FAULT 41 (ASF) output is shown in Table B:
TABLE B
______________________________________
Truth Table for Combinational Fault Detection Logic:
208 206 207 31A 31B 41
MAS R/W OCF BP1 BPO : ASF
______________________________________
F X X X X F Not a Memory Access
T X F H H F Expected Read or Write
Access.
T R F H X F Expected Read Access.
T R T L H F Expected Op-Code Fetch.
T X X L L T No Access Expected.
T X T H X T Unexpected Access for an
Op-Code.
T W F H L T Unexpected Write Access.
T X F L H T Unexpected Data Read or
Write to an Op-Code
Memory Location.
______________________________________
The ACCESS SEQUENCE FAULT output 41 is True if the CPU accesses a memory
location the programmer does not expect to be accessed, i.e., accesses a
Data memory location for an Op-Code, performs a Write access to a Read
Only expected memory location, or accesses an Op-Code memory location as
Data.
Each of these conditions is a certain and early indication of a fault in
the program's execution. The ACCESS SEQUENCE FAULT output 41 can be used
to force the outputs of the Critical Computer Based Controller to a safe
state; generate a Reset, or Non-Maskable interrupt to the CPU; and/or
activate an alarm.
Since a majority of the memory accesses during the execution of a program
are to sequential memory locations, the error detection capability of a
Semi-automatic Program Execution Error Detector can be enhanced by adding
a PLUS-ONE GENERATOR 800 as shown in FIG. 3, to detect when the present
memory address is one greater than the last.
When required, a DECODER 210 generates a MEMORY ACCESS STROBE 211 from the
Computer's BUS 200 to provide a clock to the PLUS-ONE GENERATOR 800. The
signals on the Control Bus generated by some CPUs includes a signal
indicating when the Memory Address Bus, Memory Access Type signals are
valid. This signal may be used directly without a decoder to provide the
MEMORY ACCESS STROBE 211.
During a program's execution the programmer expects some memory locations
will only be accessed in sequence, and some will never be accessed in
sequence. As an example, some CPU's are expected to access memory location
assigned an Instruction's Operand only when the present memory address is
one greater than the last. The programmer expects some data memory
locations will only be accessed when the PLUS-ONE signal 871 is False, and
some data memory locations are only expected to be accessed when the
PLUS-ONE signal 871 is True.
With the PLUS-ONE 871 signal output from the PLUS-ONE GENERATOR 800
provided as an input to the COMBINATIONAL OR SEQUENTIAL FAULT DETECTION
LOGIC 40, and the programmer's sequential memory access expectations for
each memory location encoded in the ASBP codes 31, the COMBINATIONAL OR
SEQUENTIAL FAULT DETECTION LOGIC 40 can generate an ACCESS SEQUENCE FAULT
41 if a memory access departs from the programmer's sequential memory
access expectations.
As shown in FIG. 4, the INPUT PLUS ONE 850 generates an output value 851
that is one greater than the value of the ADDRESS BUS 100 input. At the
end of each memory access the value of the ADDRESS BUS 100 plus one is
loaded into the REGISTER 860. The 861 output of the REGISTER 860, and the
ADDRESS BUS 100 provide the inputs to the COMPARITOR 870. The PLUS-ONE
output 871 of the COMPARATOR 870 is True if the Present ADDRESS BUS 100
input is one greater than the last ADDRESS BUS 100 input to the PLUS-ONE
GENERATOR 800.
As shown in FIG. 5, A Semi-automatic Program Execution Error Detector for
an 8085 uP based computer is shown. This design includes the capability to
change (Update) Access Sequence Break-Points codes 31 stored in the ACCESS
SEQUENCE BREAK-POINT MEMORY 30 during the program's execution.
The STATE MACHINE SEQUENTIAL FAULT DETECTION LOGIC 400 (shown in FIG. 6)
generates an ACCESS SEQUENCE BREAK-POINT UPDATE CODE 453 in addition to
the ACCESS SEQUENCE FAULT output 471.
All operations are synchronized by the MEMORY ACCESS STROBE 211, which is
generated by the inverter 210, inverting the Address Latch Enable (ALE)
201 signal from the 8085's CONTROL BUS 200.
The completion of the last 8085 machine cycle, and the start of the next
machine cycle is indicated by a low to high transition of the MEMORY
ACCESS STROBE 211. The majority of 8085 machine cycles are used to access
memory. Status signals generated by the CPU, and provided by the CONTROL
BUS 200: M/IO 202; S1 203; and S0 204, indicate the type of each machine
cycle as shown in Table C.
TABLE C
______________________________________
8085 Machine Cycle Type Status Signals:
202 203 204
M/IO S1 S0 MACHINE CYCLE TYPE
______________________________________
TS L L Halt (TS = Three State)
L L H Memory Write
L H L Memory Read
L H H Op-Code Fetch
H L H I/O Write
H H L I/O Read
H H H Interrupt Acknowledge
______________________________________
On each low to high transition of the MEMORY ACCESS STROBE 211; the CPU's
memory address (A0843 A15 120, and AD0.fwdarw.AD7 130) is loaded into
register 110; the Status signals (M/IO 202, S1 203, S0 204 ) from the
CONTROL BUS 200 are loaded into register 220; the REGISTER 880 in the
PLUS-ONE GENERATOR 800 is loaded with the last ADDRESS BUS 100 value plus
one; and the STATE REGISTER 460 in the STATE MACHINE SEQUENTIAL FAULT
DETECTION LOGIC 400 (shown in FIG. 6) is loaded from the NEXT STATE output
451 of the STATE MACHINE ROM 450.
During each machine cycle the output of register 110 provides the ADDRESS
BUS 100 to the ACCESS SEQUENCE BREAK-POINT MEMORY 30, (which selects the
ASBP CODE 31 assigned to the memory location) and the PLUS-ONE GENERATOR
800; the high MEMORY ACCESS STROBE 211 enables the LATCH 50 to pass the
ASBP CODE 31 (as the LATCHED ASBP CODE 51 output of LATCH 50) to the STATE
MACHINE SEQUENTIAL FAULT DETECTION LOGIC 400; the PLUS-ONE 871 output from
the PLUS-ONE GENERATOR 800 is provided as an input to the STATE MACHINE
SEQUENTIAL FAULT DETECTION LOGIC 400 indicating if the present memory
address is one greater than the last; and the Status signals loaded from
the CONTROL BUS 200 into register 220 (RM/IO 222, RS1 223, RS0 224) are
provided as inputs to the STATE MACHINE SEQUENTIAL FAULT DETECTION LOGIC
400.
As a function of the above listed inputs, and its present state, the STATE
MACHINE SEQUENTIAL FAULT DETECTION LOGIC 400 generates two outputs; the
ACCESS SEQUENCE FAULT 471, and an ASBP UPDATE CODE 453. The ASBP UPDATE
CODE 453 output selects the operation performed by the ASBP UPDATE 700,
when the MEMORY ACCESS STROBE 211 goes low. The ASBP UPDATE CODE 453
indicates if an update of the ASBP code is required, and if required it
selects the update ASBP code to write into the ACCESS SEQUENCE BREAK-POINT
MEMORY 30.
When the MEMORY ACCESS STROBE 211 goes low LATCH 50 is disabled, to hold
the selected ASBP CODE 31 to the STATE MACHINE SEQUENTIAL FAULT DETECTION
LOGIC 400 and if an update is indicated by the ASBP UPDATE CODE 453, the
new ASBP code is provided to the ACCESS SEQUENCE BREAK-POINT MEMORY 30 by
the data output 710 of the ASBP UPDATE 700, and the WR signal 720 is
activated by the low MEMORY ACCESS STROBE 211 input.
The STATE MACHINE SEQUENTIAL FAULT DETECTION LOGIC 400 shown in FIG. 6
consists of a STATE MACHINE ROM 450, containing the State Machine's
program; a STATE REGISTER 460, and an "AND" gate 470. The "all ones" state
of the STATE REGISTER 460 is the Fault State which generates the ACCESS
SEQUENCE FAULT 410 output.
On each low to high transition of the MEMORY ACCESS STROBE 211 input, the
NEXT STATE 451 output from the STATE MACHINE ROM 450 is loaded into the
STATE REGISTER 460.
The NEXT STATE 451, and ASBP UPDATE CODE 453 outputs from the STATE MACHINE
ROM 450 are a function of the LATCHED ASBP CODE 51, the PLUS-ONE 871
signal, the Status signals from the CONTROL BUS 200 saved in register 220
(RMI/O 222, RS1 223, and RS0 224) and the output 461 from the STATE
REGISTER 460.
The STATE REGISTER 460 is initialized to the ZERO State by the MASTER RESET
205 from the CONTROL BUS 200.
Each State defines the programmer's expectations in regards to the inputs
to the State Machine.
If any input to the State Machine shown as the LATCHED ASBP CODE 51, the
PLUS-ONE 871 signal, or a Status signal (RMI/O 222, RS1 223, or RS0 224)
fails to conform to the expectations of the programmer, the FAULT State is
selected as the NEXT STATE 451 output from the STATE MACHINE ROM 450.
After a conditional instruction's Op-Code is accessed by the CPU, the
resulting memory access sequence, by Function type, will not in some cases
be exactly predictable. With some types of CPUs a conditional Jump will
result in the same memory access sequence, by Function Type, if the Jump
is taken or not taken.
On the other hand, after the Op-code for a conditional Return is accessed,
the Function type of the next memory location accessed is dependent on if
it is taken, then the next memory access will be a Stack Function Type
memory location.
When more than one memory access sequence, by Function Type, may result
from a conditional instruction's execution, the sequences selected by the
CPU can be determined by the State Machine from the resulting memory
address sequence.
After a conditional Return instruction is accessed, if the next memory
access is to the following memory location, it is almost certain that the
CPU expects to access an Op-Code Function Type memory location. If the
next location in the memory is not accessed next, it is certain that an
access to a Stack Function Type memory location is expected by the CPU.
For many CPU types, the numerical difference between the present memory
address and the last memory address will provide all the additional
information required for a State Machine to determine the Function Type
expectations of the CPU when an Op-code for a conditional instruction is
executed. For many CPU types the only address delta information required
is if the present memory address is one greater than the last memory
address.
A slightly more definitive memory address delta information may be required
for some CPU types. A two bit code for the address Delta may, as an
example, indicate one of the four possibilities listed below:
1. Present address is less than last address;
2. Present address is equal to last address;
3. Present address is equal to last address plus one;
4. Present address is greater than last address plus one.
An even greater degree of memory access sequence monitoring can be
achieved, when required, by generating an instruction access address
delta. During the execution of a program, the majority of instuctions
(Op-codes, and Operands), are accessed by the CPU from sequential memory
locations. Except for a return from an interrupt, most Instruction
Op-codes are only expected to be accessed from a location in memory that
is one greater than the address used to access the previous Op-Code or
Operand (in-line code).
A Memory Address Delta generator is converted to an Instruction Access
Delta generator by only enabling the register to load the present address
plus one when a memory access is for an Op-Code or Operand.
The Op-Code of an in-line instruction is assigned an ASBP code indicating
the Op-Code is only expected to be accessed when the Instruction Access
Delta generator Plus-One output is True, or after the execution of a
Return from interrupt instruction.
Adding an Instruction Access Delta generator to the design of an Automatic
Program Execution Monitor significantly increases its ability to detect a
fault in the instruction execution sequence.
The Semi-automatic Program Execution Error Detection structure of this
invention generates an early indication of certain types of faults in the
execution of a computer program or in the operation of a computer based
dedicated controller.
A fault indication is generated when the sequence in which memory locations
are accessed during a program's execution does not conform to the sequence
expected by the programmer. An out of sequence access to a memory location
during the execution of a program is a certain and early indication of a
fault in the program, or in the design or construction of the hardware
used to execute the program. An indication of a fault is generated
significantly before an incorrect output is generated by the program due
to the fault.
The fault indication so generated may be used to assist in the debugging of
a computer program or computer based digital controller, or for monitoring
the operation of a computer based digital controller used in a critical
application.
With prior art techniques, the search for the location of a fault when
debugging a computer program starts from the point in the program's
execution when the output sequence generated by the program does not
conform to the programmer's expectations.
Significantly less time is required to determine the location of a fault in
the coding of a program or in the design or construction of the hardware
used to execute the program, if the search for the fault's location is
started from the point in the program's execution when a memory location
access departs from the memory access sequence expected by the programmer.
Semi-automatic Program Execution Error Detection in accordance with this
invention tests every CPU memory access for a departure from the memory
accesses sequence expected by the programmer, and when the CPU accesses
memory for an instruction, the programmer expects the CPU will only access
a memory location assigned an instruction by the program.
Automatic Program Execution Monitoring will immediately generate a fault
signal if the program loses control of the Program Counter, or if any
memory access departs from the memory access sequence expected by the
programmer.
With the greater degree of program execution monitoring provided by this
invention and the immediate generation of a fault signal, the possibility
that the controller will generate a faulty output before corrective action
is taken is significantly reduced.
To implement the Automatic Program Execution Monitoring Process, prior to
the program's execution, information abstracted from the program to be
executed is converted into a definition of when the programmer expects
each memory location to be accessed during the program's execution. This
definition assigns an Access Sequence Break-Point (ASBP) code to each
location in the computer's memory space.
Then on every access by the CPU to a memory location during the program's
execution, the memory location's ASBP code is examined to determine if the
memory location is expected to be accessed at this point in the memory
access sequence. If the memory location is not expected to be accessed at
this time, an Access Sequence Fault indication or signal is generated.
This process may be implemented by a software procedure when the program is
executed by a Simulator/Debugger, or by hardware when the program is
executed in real time by a computer.
In a software implementation of this process, the Access Sequence
Break-Point codes are used to initialize an array. In a hardware
implementation, the Access Sequence Break-Point codes are loaded into a
dedicated memory.
During the program's execution, on every memory access performed by the
simulated or hardware CPU, two inputs are provided to the Automatic
Program Execution Monitoring process:
1. Current Memory Address, "cur.sub.-- mem.sub.-- add"
2. A Memory Access Type code which specifies the type of memory access
provided by the CPU's control bus in a hardware implementation.
The following storage elements are used during the processing:
1. Access Sequence Break-Point Array, "asbp.sub.-- array[]"
2. Current Access Sequence Break-Point, "asbp"
3. Last Memory Address, "last.sub.-- mem.sub.-- add"
4. Memory Address Delta, "delta
5. Current State, "c.sub.-- state
6. Next State Array, "n.sub.-- state[]"
7. ASBP Code Update Array, "update[]"
The CPU's instruction set defines the contents of the Next State, and ASBP
Code Update Arrays, In a hardware implementation these two arrays are
provided by a ROM.
THE AUTOMATIC PROGRAM EXECUTION MONITORING PROCESS:
1. asbp=asbp.sub.-- array[cur.sub.-- mem .sub.-- add];
2. if (cur.sub.-- mem.sub.-- add==(last mem.sub.-- add.sub.-- +1)) delta=1;
else delta=0;
3. update=update[asbp, delta, type, c.sub.-- state];
4. if (update !=0) asbp.sub.-- array[cur.sub.-- mem.sub.-- add]=update;
5. c.sub.-- state=n.sub.-- state[asbp, delta, type, c.sub.-- state]
6. if (c.sub.-- state==ERROR) return TRUE; else return FALSE;
The Programmer's Memory Access Sequence Expectations:
Inherent in the definition of a computer program is an assignment of the
type of function the programmer expects every location in computer's
memory to perform during the program's execution. The function a memory
location is expected to perform defines when during the program's
execution the programmer expects the memory location will be accessed.
Major Function Types:
With few exceptions (self modifying code as one example of an exception)
every location in the computer's memory space can be classified into one
of the three major Function Types; 1. Instructions, 2. Data, and since few
programs use every memory location, 3. Not Used.
This most basic classification of memory locations, in terms of the
function each memory location is expected to perform during the program's
execution, is clearly defined by a definition of the program, and provides
a basic definition of when during the program's execution the programmer
expects each memory location to be accessed.
Every CPU memory access is for either an instruction or data. The
programmer expects the CPU will not access a Not Used or Data memory
locations for an Instruction. With a few exceptions, such as a memory
test, the programmer does not expect Instruction and Not Used memory
locations to be accessed by the CPU as Data.
A memory access departing from these most basic expectations of the
programmer is a certain and early indication of a program or hardware
fault, and these most basic programmer expectations are easy to determine
from a definition of the program.
A more detailed definition of the type of function each location in the
computer's memory space is expected to perform is provided by a definition
of the program and the CPU's instruction set. A more detailed definition
of the function each memory location is expected to perform provides a
more exact definition of when, during the program's execution, the
programmer expects a memory location to be accessed.
The following examples illustrate the more detailed definition of each
memory location's Function Type, provided by a definition of the program
and the CPU's instruction set and the more exacting definition of when a
memory location is expec | | |
