Processor with accelerated array access bounds checking

• US 6,014,723 A
• Filed: 01/23/1997
• Issued: 01/11/2000
• Est. Priority Date: 01/24/1996
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Tremblay, Marc, O'Connor, James Michael, Joy, William N.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/786,352
• Time in Patent Office: 1,083 Days
• Field of Search: 395/185.06, 707/104, 711/1, 711/200
• US Class Current: 711/1
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/1441 for a range
• CPC Class Codes: G06F 2212/451 Stack data
• CPC Class Codes: G06F 9/264 Microinstruction selection based on results of processing
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/30134 Register stacks; shift registers
• CPC Class Codes: G06F 9/30174 for non-native instruction set, e.g. Javabyte, legacy code
• CPC Class Codes: G06F 9/345 of multiple operands or results addressing multiple banks G06F12/06
• CPC Class Codes: G06F 9/44589 Program code verification, e.g. Java bytecode verification, proof-carrying code high-level semantic checks G06F8/43; testing and debugging software G06F11/36
• CPC Class Codes: G06F 9/4484 Executing subprograms
• CPC Class Codes: G06F 9/449 Object-oriented method invocation or resolution
• CPC Class Codes: G06F 9/45504 Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators

Abstract

An array boundary checking apparatus is configured to verify that a referenced element of an information array is within a maximum array size boundary value and a minimum array size boundary value. The array boundary checking apparatus of the invention includes an associative memory element that stores and retrieves a plurality of array bound values. Each one of the plurality of array bound values is associated with one of the plurality of array access instructions. An input section simultaneously compares the array access instruction identifier with at least a portion of each of the stored array reference entries, wherein the array access instruction identifier identifies an array access instruction. An output section is configured to provide as an array bounds output values one of the plurality of array bound values stored in one of the plurality of memory locations of the associated memory element. A first comparison element compares the value of the referenced element and the maximum array index boundary value and provides a maximum violation signal if the value of the element is greater than the maximum array size boundary value. A second comparison element compares the value of the element and the minimum array size boundary value and provides a minimum violation signal if the value of the element is less than the minimum array bounds value. Either a maximum violation signal or a minimum violation signal results in an exception.

Claims

1. An array bounds checking apparatus configured to verify that each access of an array is within a maximum array size boundary value and a minimum array size boundary value, the apparatus comprising:

an associative memory element configured to store and retrieve array size values which are associated with one of a plurality of array access instructions, each array access instruction referencing a value of a location of an element within the array;

a first comparison element operatively coupled to an output section of the associative memory element, the first comparison element configured to compare a predetermined maximum array size value and the value of the location of the referenced element within the array, and to provide a maximum violation signal if the value of the location of the referenced element within the array is greater than the predetermined maximum array size value; and

a second comparison element operatively coupled to the output section of the associative memory element, the second comparison element configured to compare a predetermined minimum array size value and the value of the location of the referenced element within the array, and to provide a minimum violation signal if the value of the location of the referenced element within the array is less than the predetermined minimum array size value.

2. The array bounds checking apparatus of claim 1 further comprising:

an exception element operatively coupled to the first and second comparison elements, the exception element configured to provide an exception signal in response to receipt of either the maximum violation signal or the minimum violation signal.

3. The array bounds checking apparatus of claim 1 wherein the associative memory element further comprises:

a first memory section that includes a first plurality of memory locations configured to receive and store a plurality of array reference entries, wherein each one of the first plurality of memory locations is configured to store one of the plurality of array reference entries, and further wherein each one of the plurality of array reference entries corresponds to one of the plurality of array access instructions;

an input section, operatively coupled to the first memory section, configured to receive an array access instruction identifier and to simultaneously compare the array access instruction identifier with at least a portion of each of the stored plurality of array reference entries, wherein the array access instruction identifier identifies an array access instruction;

a second memory section that includes a second plurality of memory locations configured to receive and store a plurality of array size values, wherein each one of the second plurality of memory locations is configured to store one of the array size values and is associated with one of the first plurality of memory locations, and further wherein each one of the plurality of array size values is associated with one of the plurality of array access instructions and comprises a maximum array size value and a minimum array size value and, further wherein

the output section of the associative memory element is operatively coupled to the second memory section, and configured to provide, as an array size output value, one of the plurality of array size values stored in one of the second plurality of memory locations which is associated with one of the first plurality of memory locations in which is stored one of the plurality of array reference entries that matches the array access instruction identifier.

4. An array bounds checking apparatus configured to verify that a refernced element of an array is within a maximum array size boundary value and a minimum array size boundary value, the apparatus comprising:

(a) an associative memory element configured to store and retrieve array size values, wherein the array size values are associated with one of a plurality of array access instructions, each array access instruction referencing a value of a location of an element within the array, the associative memory element including;

(i) a first memory section that includes a first plurality of memory locations configured to receive and store a plurality of array reference entries, wherein each one of the first plurality of memory locations is configured to store one of the plurality of array reference entries, and further wherein each one of the plurality of array reference entries corresponds to one of the plurality of array access instructions;

(ii) a second memory section that includes a second plurality of memory locations configured to receive and store a plurality of array size values, wherein each one of the second plurality of memory locations is configured to store one of the array size values and is associated with one of the first plurality of memory locations, and further wherein each one of the plurality of array size values is associated with one of the plurality of array access instructions and comprises a maximum array size value and a minimum array size value;

(iii) an input section operatively coupled to the first memory section, and configured to receive an array access instruction identifier and to simultaneously compare the array access instruction identifier with at least a portion of each of the stored plurality of array reference entries, wherein the array access instruction identifier identifies an array access instruction; and

(iv) an output section, operatively coupled to the second memory section, configured to provide, as an array size output value, one of the plurality of array size values stored in one of the second plurality of memory locations which is associated with one of the first plurality of memory locations in which is stored one of the plurality of array reference entries that matches the array access instruction identifier;

(b) a first comparison element operatively coupled to the output section and configured to compare the maximum array size output value and the value of the location of the referenced element within the array and to provide a maximum violation signal if the value of the location of the referenced element within the array is greater than the maximum array size output value;

(c) a second comparison element operatively coupled to the output section, and configured to compare the minimum array size output value and the value of the location of the referenced element within the array and to provide a minimum violation signal if the value of the location of the referenced element within the array is less than the minimum array size output value; and

(d) an exception element operatively coupled to the first and second comparison elements, and configured to provide an exception output signal in response to receipt of either the maximum violation signal or the minimum violation signal.

5. A method of verifying that a referenced element of an array is within a maximum array size boundary value and a minimum array size boundary value, the method comprising:

storing a plurality of array reference entries in a first memory section that includes a first plurality of memory locations, wherein each one of the first plurality of memory locations is configured to store one of the plurality of array reference entries, and further wherein each one of the plurality of array reference entries corresponds to one of a plurality of array access instructions;

storing a plurality of array size values in a second memory section that includes a second plurality of memory locations, wherein each one of the second plurality of memory locations is configured to store one of the array size values and is associated with one of the first plurality of memory locations, and further wherein each one of the plurality of array size values is associated with one of the plurality of array access instructions and comprises a maximum array size value and a minimum array size value;

simultaneously comparing an array access instruction identifier with at least a portion of each of the stored plurality of array reference entries, wherein the array access instruction identifier identifies an array access instruction;

providing as an array size output value one of the plurality of array size values stored in one of the second plurality of memory locations which is associated with one of the first plurality of memory locations in which is stored one of the plurality of array reference entries that matches the array access instruction identifier wherein said array size output value includes said maximum array size value as a maximum array size output value, and said minimum array size value as a minimum array size output value;

comparing the maximum array size output value and a value of a location of the referenced element within said array, and generating a maximum violation signal if the value of the location of the referenced element within said array is greater than the maximum array size output value;

comparing the minimum array size output value and the value of the location of the referenced element within said array, and generating a minimum violation signal if the value of the location of the referenced element within said array is less than the minimum array size output value; and

providing an exception output signal in response to generation of either the maximum violation signal or the minimum violation signal.

6. A method to verify that a referenced element of an array is within a maximum array size boundary value and a minimum array size boundary value, the method comprising:

providing an associative memory element configured to store and retrieve array size values which are associated with one of a plurality of array access instructions, each array access instruction referencing a value of a location of an element within the array;

providing a first comparison element operatively coupled to an output section of the associative memory element, the first comparison element configured to compare a predetermined maximum array size value and the value of the location of the referenced element within the array, and to provide a maximum violation signal if the value of the location of the referenced element within the array is greater than the predetermined maximum array size value;

providing a second comparison element operatively coupled to the output section of the associative memory element, the second comparison element configured to compare a predetermined minimum array size value and the value of the location of the referenced element within the array, and to provide a minimum violation signal if the value of the location of the referenced element within the array is less than the predetermined minimum array size value; and

providing an exception element operatively coupled to the first and second comparison elements, the exception element configured to provide an exception signal in response to receipt of either the maximum violation signal or the minimum violation signal.

7. The method of claim 6 further comprising:

providing a first memory section in the associative memory element that includes a first plurality of memory locations configured to receive and store a plurality of array reference entries, wherein each one of the first plurality of memory locations is configured to store one of the plurality of array reference entries, and further wherein each one of the plurality of array reference entries corresponds to one of the plurality of array access instructions;

providing an input section, operatively coupled to the first memory section, configured to receive an array access instruction identifier and to simultaneously compare the array access instruction identifier with at least a portion of each of the stored plurality of array reference entries, wherein the array access instruction identifier identifies an array access instruction;

providing a second memory section in the associative memory element that includes a second plurality of memory locations configured to receive and store a plurality of array size values, wherein each one of the second plurality of memory locations is configured to store one of the array size values and is associated with one of the first plurality of memory locations, and further wherein each one of the plurality of array size values is associated with one of the plurality of array access instructions and comprises a maximum array size value and a minimum array size value, and further wherein,

the output section of the associative memory element is operatively coupled to the second memory section, and configured to provide, as an array size output value, one of the plurality of array size values stored in one of the second plurality of memory locations which is associated with one of the first plurality of memory locations in which is stored one of the plurality of array reference entries that matches the array access instruction identifier.

8. A method of providing an array boundary checking apparatus configured to verify that a referenced element of an array is within a maximum array size boundary value and a minimum array size boundary value, the method comprising:

(a) providing an associative memory element configured to store and retrieve a plurality of array size values, wherein each one of the array size values is associated with one of a plurality of array access instructions, the associative memory element including;

(i) a first memory section that includes a first plurality of memory locations configured to receive and store a plurality of array reference entries, wherein each one of the first plurality of memory locations is configured to store one of the plurality of array reference entries, and further wherein each one of the plurality of array reference entries corresponds to one of the plurality of array access instructions;

(ii) a second memory section that includes a second plurality of memory locations configured to receive and store a plurality of array size values, wherein each one of the second plurality of memory locations is configured to store one of the array size values and is associated with one of the first plurality of memory locations, and further wherein each one of the plurality of array size values is associated with one of the plurality of array access instructions and comprises a maximum array size value and a minimum array size value;

(iii) an input section operatively coupled to the first memory section, and configured to receive an array access instruction identifier and to simultaneously compare the array access instruction identifier with at least a portion of each of the stored plurality of array reference entries, wherein the array access instruction identifier identifies an array access instruction; and

(iv) an output section operatively coupled to the second memory section, and configured to provide as an array size output value one of the plurality of array size values stored in one of the second plurality of memory locations which is associated with one of the first plurality of memory locations in which is stored one of the plurality of array reference entries that matches the array access instruction identifier wherein said array size output value includes said maximum array size value as a maximum array size output value, and said minimum array size value as a minimum array size output value;

(b) providing a first comparison element operatively coupled to the output section, and configured to compare a value of a location of the referenced element within the array and the maximum array size output value and to provide a maximum violation signal if the value of the location of the referenced element within the array is greater than the maximum array size output value;

(c) providing a second comparison element operatively coupled to the output section, and configured to compare the value of the location of the referenced element within the array and the minimum array size output value and to provide a minimum violation signal if the value of the location of the referenced element within the array is less than the minimum array size boundary value; and

(d) providing an exception element operatively coupled to the first, and second comparison elements and configured to provide an exception output signal in response to receipt of either the maximum violation signal or the minimum violation signal.

9. A computer system comprising:

a translation unit configured to receive and translate a software program and, in accordance with the software program, provide a plurality of translated instructions and a plurality of instruction identifiers, wherein each one of the instruction identifiers corresponds to one of the plurality of translated instructions, the plurality of translated instructions including a plurality of array access instructions;

an execution unit configured to receive, in accordance with the plurality of instruction identifiers, the plurality of translated instructions, and, in accordance therewith, execute received translated instructions;

an associative memory element configured to store and retrieve array size values which are associated with one of a plurality of array access instructions, each array access instruction referencing a value of a location of an element within the array;

a first comparison element operatively coupled to an output section of the associative memory element, the first comparison element configured to compare a predetermined maximum array size value and the value of the location of the referenced element within the array, and to provide a maximum violation signal if the value of the location of the referenced element within the array is greater than the predetermined maximum array size value;

a second comparison element operatively coupled to the output section of the associative memory element, the second comparison element configured to compare a predetermined minimum array size value and the value of the location of the referenced element within the array and to provide a minimum violation signal if the value of the location of the referenced element within the array is less than the predetermined minimum array size value; and

an exception element operatively coupled to the first and second comparison elements and the execution unit, the exception element configured to provide an exception signal to the execution unit in response to receipt of either the maximum violation signal or the minimum violation signal.

10. The computer system of claim 9 wherein the associative memory element further comprises:

a first memory section that includes a first plurality of memory locations configured to receive and store a plurality of array reference entries, wherein each one of the first plurality of memory locations is configured to store one of the plurality of array reference entries, and further wherein each one of the plurality of array reference entries corresponds to one of the plurality of array access instructions;

an input section operatively coupled to the first memory section, and configured to receive an array access instruction identifier and to simultaneously compare the array access instruction identifier with at least a portion of each of the stored plurality of array reference entries, wherein the array access instruction identifier identifies an array access instruction;

a second memory section that includes a second plurality of memory locations configured to receive and store a plurality of array size values, wherein each one of the second plurality of memory locations is configured to store one of the array size values and is associated with one of the first plurality of memory locations, and further wherein each one of the plurality of array size values is associated with one of the plurality of array access instructions and comprises a maximum array size value and a minimum array size value, and further wherein

the output section of the associative memory element is operatively coupled to the second memory section, and configured to provide, as an array size output value, one of the plurality of array size values stored in one of the second plurality of memory locations which is associated with one of the first plurality of memory locations in which is stored one of the plurality of array reference entries that matches the array access instruction identifier.

11. A computer system comprising:

a translation unit configured to receive and translate a software program and, in accordance with the software program, provide a plurality of translated instructions and a plurality of instruction identifiers, wherein each one of the instruction identifiers corresponds to one of the plurality of translated instructions, the plurality of translated instructions including a plurality of array access instructions;

an execution unit configured to receive, in accordance with the plurality of instruction identifiers, the plurality of translated instructions, and, in accordance therewith, execute received translated instructions; and

an associative memory element configured to store and retrieve a plurality of array size values, wherein each one of the array size values is associated with one of a plurality of array access instructions, the associative memory element including;

(i) a first memory section that includes a first plurality of memory locations configured to receive and store a plurality of array reference entries, wherein each one of the first plurality of memory locations is configured to store one of the plurality of array reference entries, and further wherein each one of the plurality of array reference entries corresponds to one of the plurality of array access instructions;

(ii) a second memory section that includes a second plurality of memory locations configured to receive and store a plurality of array size values, wherein each one of the second plurality of memory locations is configured to store one of the array size values and is associated with one of the first plurality of memory locations, and further wherein each one of the plurality of array size values is associated with one of the plurality of array access instructions and comprises a maximum array size value and a minimum array size value;

(iii) an input section operatively coupled to the first memory section, and configured to receive an array access instruction identifier and to simultaneously compare the array access instruction identifier with at least a portion of each of the stored plurality array reference entries, wherein the array access instruction identifier identifies an array access instruction; and

(iv) an output section operatively coupled to the second memory section and configured to provide, as an array size output value, one of the plurality of array size values stored in one of the second plurality of memory locations which is associated with one of the first plurality of memory locations in which is stored one of the plurality of array reference entries that matches the array access instruction identifier;

a first comparison element operatively coupled to the output section of the associative memory element, and configured to compare a value of a location of the referenced element within the array and the maximum array size output value and to provide a maximum violation signal if the value of the location of the referenced element within the array is greater than the maximum array size output value;

a second comparison element operatively coupled to the output section of the associative memory element, and configured to compare the value of the location of the referenced element within the array and the minimum array size output value and to provide a minimum violation signal if the value of the location of the referenced element within the array is less than the minimum array size output value; and

an exception element operatively coupled to the first and second comparison elements and the execution unit, configured to provide an exception output signal to the execution unit in response to receipt of either the maximum violation signal or the minimum violation signal,

wherein the execution unit is configured to respond to the exception output signal by executing a sequence of translated instructions that define an array access boundary exception subroutine.