Address generation checking

A method for address generation checking including receiving a starting memory address for a data, an ending memory address for the data, a length value of the data, and an address wrap indicator value that indicates if the data wraps from an end of a memory block to a start of the memory block, determining whether the ending memory address is equal to a sum of the starting memory address added to a difference of the length value to the address wrap indicator value, and transmitting an error signal that indicates an error occurred in a generation of the starting memory address or the ending memory address if the ending memory address is not equal to the sum.

BACKGROUND OF THE INVENTION

This invention relates generally to computer processor operation, and more particularly to providing a method, system, and computer program product for address generation checking.

With the continuing development and use of modern computer systems, the demand has increased for processors that operate without causing data corruption. For example, computers or microprocessors are used in a number of critical functions where consistent, accurate processing is needed, such as life supporting medical devices, financial transaction systems, and automobile safety and control systems. A common approach to meet this demand is to duplicate processor circuitry and compare the resulting duplicate functionality to detect processor errors, such as errors in the generation of addresses that are used to access stored data for processing purposes. However, an increased amount of component space (or area), processing time (e.g., added delay or latency), and power is needed to provide such duplication of processor logic, which can be inefficient for various applications. Thus, an approach to check for such address generation errors without the use of duplicate circuitry is desirable.

BRIEF SUMMARY OF THE INVENTION

A method, system, and computer program product for address generation checking is provided. An exemplary method embodiment includes receiving a starting memory address for a data, an ending memory address for the data, a length value of the data, and an address wrap indicator value that indicates if the data wraps from an end of a memory block to a start of the memory block, determining whether the ending memory address is equal to a sum of the starting memory address added to a difference of the length value to the address wrap indicator value, and transmitting an error signal that indicates an error occurred in a generation of the starting memory address or the ending memory address if the ending memory address is not equal to the sum.

An exemplary system embodiment includes an address generation checking unit configured to receive a starting memory address for a data, an ending memory address for the data, a length value of the data, and an address wrap indicator value that indicates if the data wraps from an end of a memory block to a start of the memory block, determine whether the ending memory address is equal to a sum of the starting memory address added to a difference of the length value to the address wrap indicator value, and transmit an error signal that indicates an error occurred in a generation of the starting memory address or the ending memory address if the ending memory address is not equal to the sum.

An exemplary computer program product embodiment includes a computer usable medium having a computer readable program, wherein the computer readable program, when executed on a computer, causes the computer to receive a starting memory address for a data, an ending memory address for the data, a length value of the data, and an address wrap indicator value that indicates if the data wraps from an end of a memory block to a start of the memory block, determine whether the ending memory address is equal to a sum of the starting memory address added to a difference of the length value to the address wrap indicator value, and transmit an error signal that indicates an error occurred in a generation of the starting memory address or the ending memory address if the ending memory address is not equal to the sum.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

Exemplary embodiments of the invention described herein provide a method, system, and computer program product for address generation checking. In accordance with such exemplary embodiments, processor address generation error checking without the use of duplicate circuitry is provided This error checking is provided with a reduced hardwood overhead by utilizing existing address generation hardware for inputs to check for errors.

Turning now to the drawings in greater detail, wherein like reference numerals indicate like elements,FIG. 1illustrates an example of a computer system100including an exemplary computing device (“computer”)102configured for address generation checking. In addition to computer102, exemplary computer system100includes network120and other device(s)130. Network120connects computer102and other device(s)130and may include one or more wide area networks (WANs) and/or local area networks (LANs) such as the Internet, intranet(s), and/or wireless communication network(s). Other device(s)130may include one or more other devices, e.g., one or more other computers, storage devices, peripheral devices, etc. Computer102and other device(s)130are in communication via network120, e.g., to communicate data between them.

Exemplary computer102includes processor104, main memory (“memory”)106, and input/output component(s)108, which are in communication via bus103. Processor104may include multiple (e.g., two or more) processors, which may implement pipeline processing, and also includes cache memory (“cache”)110, controls112, and one or more components configured for address generation checking that will be described below. Cache110may include multiple cache levels (e.g., L1, L2, etc.) that are on or off-chip from processor104(e.g., an L1 cache may be on-chip, an L2 cache may be off-chip, etc.). Memory106may include various data stored therein, e.g., instructions, software, routines, etc., which, e.g., may be transferred to/from cache110by controls112for execution by processor104. Input/output component(s)108may include one or more components, devices, etc. that facilitate local and/or remote input/output operations to/from computer102, such as a display, keyboard, modem, network adapter, ports, etc. (not depicted).

FIG. 2illustrates an example of a processor subsystem200of exemplary computer102that is configured for address generation checking and is included, e.g., within processor104. Exemplary subsystem200includes an exemplary subsystem300for address generation checking that will be described further below. Subsystem200also includes instruction fetch unit (“IFU”)202, which is in communication with an instruction cache (“I-cache”) and configured to fetch instruction code stored in the I-cache (which, e.g., may be part of cache110). IFU202is also in communication with instruction decode unit (“IDU”)206, which is configured to decode instructions into instruction processing data and may, e.g., include one or more instruction decoders. IDU206is in communication with group/dispatch unit (“GDU”)206, which is configured to group instruction processing data by grouping or separating it depending on whether the data can be concurrently processed (e.g., without causing hazards). GDU206is communication with address generation unit (“AGEN”)208and also configured to dispatch the grouped instruction processing data to AGEN208. AGEN208is configured to generate addresses based on the instruction processing data to fetch data and is in communication with address generation checking unit (“AGCU”)210, which will be discussed further below. Exemplary address checking subsystem300includes AGEN208and AGCU210.

AGEN208is also in communication with data cache (D-cache) access unit (“DCAU”)212, which is configured to access data from a D-cache (which, e.g., may be part of cache210). DCAU212is in communication with execution unit214, which may include one or more units configured to execute the instruction processing data using the fetched data from the D-cache. For example, execution unit214may include a fixed point unit (“FXU”), a binary floating point unit (“BFU”), and a decimal floating point unit (“DFU”). Execution unit214is in communication with completion logic216, which is configured to complete the instruction processing. Completion logic216is also in communication with recovery unit218, to which it may provide instruction data for recovery operations by recovery unit218. AGCU210is also in communication with recovery unit218, to which it provides error reporting data (e.g., an error signal in response to an address generation error). Subsystem200also includes a feedback loop from the output of AGEN208to the input of AGEN208, e.g., for address incrementation during address generation. Furthermore, subsystem200includes another feedback loop from the output of DCAU212to the input of GDU206, e.g., for an instruction recycle, e.g., in response to an address generation error, a cache miss, etc.

FIG. 3illustrates an example of an address generation subsystem300of exemplary processor subsystem200that is configured for address generation checking. Exemplary AGEN subsystem300includes components of AGCU210in communication with components of AGEN208. In that regard, components of AGEN208include address generation adder (“AA”)302and AA304, which are configured to output a start address303and end address305, respectively, based on the inputs, of data to be fetched by DCAU212. In some embodiments, AA302and304are configured to perform 64-bit 3-way additions with a 64-bit result. Inputs to AA302may include a base input B, an index input X, and a displacement input D (e.g., from GDU206). Inputs to AA304may include base input B, index input X, and a displacement-length input DL. AGEN208also includes AA306, which is configured to output displacement-length input DL to AA304based on the inputs and is in communication with AA304. In some embodiments, AA306may be configured to perform 20 bit addition. Inputs to AA306may include a displacement input D and a length input L. Base input D, index input X, displacement input D, and length input L can be obtained from instruction processing data and used to generate a start (or starting) address for a data (data stream, etc.) and an end (or ending) address for the data, e.g., by AA302,304,306, that can be used to fetch the data from a cache (e.g., cache210) or memory (e.g., memory106). In some embodiments AGEN208may be configured to form a branch target address for a branch instruction, and in such embodiments, AA304may be non-functioning or not included in AGEN208.

In some embodiments, AGEN208may also include an address incrementor308, which is configured to increment the start address by an additional amount for searches of memory blocks (cache lines, etc.) that are larger than the standard length by a multiple of the additional amount. For example, incrementor308may be a 64-bit incrementor configured to add 16 bits, 32 bits, etc. accordingly to the start address. In that regard, incrementor308is in communication with output303of AA302(e.g., on each side of a register or latch device330) to update the start address output303communicated to AGCU210. Incrementor308is also used for an operand that crosses a cache line boundary, thereby needing two memory accesses to get the storage data. AA302is used for the first access, and incrementor308, using recycled memory address input309, is used for the second access, as well as for long operand fetches. In some embodiments, the outputs of AA302,304,306are also used for normal address generation for processing by subsystem200of processor104.

AGCU210includes error checking unit (“ECU”)312, which is configured to compare the end address from output305with a combination of length input L, the start address from output303, and an address wrap indicator value. For example, ECU312compares the end address (“end”) with the sum of the start address (“start”) with the difference of length L (“len”) to the address wrap indicator value (“wrap”) to determine whether start+(len−wrap)=end. If the foregoing equality is true, then there is not an error in the address generation (e.g., in the circuitry or address data). If the foregoing equality is false, then an error is indicated. An output313from ECU312is generated accordingly. For example, ECU313may output a logic-0 signal if no error is determined or a logic-1 signal if an error is determined (or vice versa). Error output313can be communicated, e.g., to an instruction recovery unit218, which may trigger a block of creating a checkpoint for the completion of instruction data processing and a recovery of the instruction data for reprocessing to negate the error (i.e., an error recovery operation). For example, a checkpoint and recovery operation may be triggered in which transient updates made as a result of processing instruction data are discarded and processing is restarted at the most previous checkpoint (i.e., correctly architected) state before the processing error occurred. Address wrap indicator value is dependent on whether there is an address wrap in light of the start address versus the end address, i.e., whether there is a wrap from the end of the memory block to the beginning of the memory block for the addressed data. Thus, the address wrap indicator value may be determined based on a comparison of the start address to the end address, e.g., by an address wrap determination logic (not depicted).

In some embodiments, the configuration and operation of ECU312is simplified by inputting modified values of the start address, end address, length, and wrap value. For example, these values may be modified by using a residue (or remainder) of the modulus of the value to reduce the bit length of the value for calculations by ECU312. In some embodiments, the residue of a modulus-3 (modulo-3, mod3, etc.) operation (“modulus-3 residue” or “Res3”) on the values may be used. In that regard, in some embodiments, AGCU210may include Res3 generation logic314,316,318, and320in communication with length input L, start input303, and start output305, respectively, and ECU312. Furthermore, Res3 generation logic318may include address wrap determination logic incorporated within it. The Res3 does not need to be generated for the inputs to AA302,304for error checking in accordance with exemplary embodiments, which further reduces hardware overhead. Modulus and residue calculations, such as Res3, may be generated in various manners using various components, which may be known or apparent to one of ordinary skill in the art in light of the disclosure herein. AGEN208and AGCU210may also include one or more register devices330(e.g., a register, latch, or similar holding device) at various points (e.g., as depicted) to synchronize inputs and outputs with other components of AGEN subsystem300.

FIG. 4illustrates an example of a method400for address generation checking executable, e.g., on exemplary computer102. Exemplary method400may also describe an exemplary operation of AGCU210. In block402, a start address, end address, length value, address wrap indicator value are received (e.g., by ECU312). As discussed above, the start address may be output from a first address generation adder (or address adder, e.g., AA302), and the end address may be output from a second address adder (AA304). The length value may be tapped off an input to a third address adder (e.g., AA306) based on instruction processing data (e.g., from GDU206). The address wrap indicator value may be based on a comparison of the start address to end address to determine if an address wrap occurs for the addressed data. In some embodiments, the residue of a modulus-3 operation (“Res3”) on the values is generated in block410to, e.g., simplify the values (e.g., by reducing the bit length).

In block404a determination of whether the end address (“end”) is equal to the sum of the start address (“start”) added to the difference of length value (“len”) to the address wrap indicator value (“wrap”), i.e., whether start+(len−wrap)=end. If the foregoing equality is true, then method400proceeds to block406in which it is determined that there is not an error in the address generation and an appropriate signal (e.g., logic-0) may be outputted (e.g., to recovery unit218). If the foregoing equality is false, then method400proceeds to block408in which it is determined that there is an error in the address generation and an appropriate signal (e.g., logic-1) may be outputted (e.g., to recovery unit218) to trigger an abort of the instruction completion followed by a recycle of the instruction to negate the error.

FIG. 5illustrates an example of a method500for address generation checking in accordance with exemplary method400. Method500covers short (e.g., 8 bytes or less) fetch/store operations and also covers the AA's (first address generated) for a long (e.g., 9 bytes or more) fetch/store operations where the memory address is not defined to be relative with respect to the instruction address. Method500proceeds according to the following:

Block504: Form Displacement in GDU206; Displacement is 20-bits signed number; Formed as 33-bits signed number by doing 12-bit sign extension to be common with other AGEN usage.

Block506: Disp_plus_Len=Disp+Length; Disp is 20-bits signed number; Length field has 8 significant bits for all instructions indicating a memory operand length ranges from 1 byte to 256 bytes; Disp_plus_Len is 33-bits signed binary number;

Block508: D←Displacement from block504; D register is 33 bits; Do Partial sign extension on the D register before feeding the adders in block510. (e.g., replicate sign of Displacement to 5 latches) (sign_0008, sign_0917, sign_1826, sign_2729, sign_30);

DL register←Disp_plus_Len; DL register is 33 bits; Do Partial sign extension on the DL register before feeding the adders in block510. (e.g., replicate sign of to 5 latches) (sign_DL_0008, sign_DL_0917, sign_DL_1826, sign_DL_2729, sign_DL_30);

start_addressess(0:63)=B(0:63)+X(0:63)+D_int(0:63). This a 3-way 64-bits additions with no carry outs from the additions being saved. Bit0(e.g. start_addressess(0)) is the most significant bit and bit63is the least significant bit.a. D_int(00:08)<=sign_0008;b. D_int(09:17)<=sign_0917;c. D_int(18:26)<=sign_1826;d. D_int(27:29)<=sign_2729;e. D_int(30)<=sign_30;f. D_int(31:63)<=D(31:63);g. Each sign (e.g. sign_0008) should feed odd number of bits (in this case 9 bits for sign_0008) because if the sign bit flips, the error will be detected by the equation in block520.

end_address(0:63)=B(0:63)+X(0:63)+DL_int(0:63). This a 3-way 64-bits addition with no carry outs from the additions being saved. Bit0(e.g. end_address(0)) is the most significant bit and bit63is the least significant bit.a. DL_int(00:08)<=sign_dl_0008;b. DL_int(09:17)<=sign_dl_0917;c. DL_int(18:26)<=sign_dl_1826;d. DL_int(27:29)<=sign_dl_2729;e. DL_int(30)<=sign_dl_30;f. DL_int(31:63)<=DL(31:63);

Block512: Calculate the wrap address indication. i.e. when fetch/store data wraps around storage (end_address<start_address); Maximum length size for hardware executed operations is 255; Address wrap can be calculated as:

The processor operates in 3 different memory addressing mode. In 24-bit mode, programs and applications form their address as a maximum of 24 bits and hardware is designed to be backward compatible with such programs. Similarly in programs written for 31-bit address computations forms addresses that are 31-bit wide. The AGEN208is designed to operate on 24, 31 and 64-bit addressing modes.

Block514: For 31-bit addressing mode, clear bits0:32of start_address and end_address; For 24-bit addressing mode, clear bits0:39of start_address and end_address. This step is to convert the 64-bit additions (block510) that is performed regarding of the addressing mode to an address compatible with the program running on the processor.

Block516: Calculate Res3_len as Res3 for the Length field.

Res3_start_address+(Res3_len−Res3_wrap)=Res3_end_address should be true otherwise set an error; If, for example, bit I is flipped in start_address causing the faulty output to be start_address′, then start_address′=start_address±2^^I (± depending on the direction of the flip)

Res3(start_address′)=Res3(start_address)±1 (or 2) depending if bit-I is even or odd.

(Res3(2^^I)=1 when I is even. (bit0is most significant bit and bit63is least significant bit).

(Res3(2^^I)=1 when I is odd. ((bit0is most significant bit and bit63is least significant bit).

Since Res3(start_address′) does not equal to Res3(start_address)=>Equation will not hold and bit flip is detected.

FIG. 6illustrates an example of a method600for address generation checking in accordance with exemplary method400. Method600covers address adder for a line reject that may occur for the first fetch since all subsequent fetches are quad-word aligned. In a line crossing case, the bytes requested for a fetch crosses a cache boundary line and another fetch is needed to get the rest of the operand bytes. For example, if an instruction is fetching 8 bytes from memory and the most significant 3 bytes are located at the end of a cache line and remaining 5 bytes are located at the beginning of the next cache line, the first fetch to memory will return the first 3 bytes in the first line and the second fetch for an address pointing to the beginning of the second cache line will return the remainder 5 bytes. Method600to cover the address adder for the second fetch proceeds according to the following:

Block602: same as block502.

Block604: same as block504.

Block606: same as block506.

Block608: same as block508.

Block610: Start_address—1stis the first fetch address which is returned from memory due to cache reject (line crossing). This address (AA) is initially formed in block510and is returned by the cache memory controls because of a memory operands crosses a line. A line crossing is one case of a cache reject described inFIG. 2as a path from data cache212and GDU206. In this example, a cache line is 256 bytes in size.

Block612: During the re-dispatch of the instruction after line reject:

start_address(60:63)<=“0000”. The start address will not point to the beginning of the 2ndline.

Block614: Calculate The effective length of this fetch. effective_len=Length−(8−start_address—1st(61:63)); Represents the bytes that will be fetched after the line rejected fetch. The number of bytes fetched in the 1st AA are subtracted from the total length to get the effective length. As in prior example, if an instruction is fetching 8 bytes and the most significant 3 bytes are located at the end of one cache line and the remainder 5 bytes are located at the beginning of next cache line, then the effective length of the fetch is equal to 5 (8−3).

Block616: same as block512

Block618: same as block514.

Block620: same as block516.

Block620: same as block516.

Block622: same as block518.

Blocks624,626: same as blocks520,522.

FIG. 7illustrates an example of a method700for address generation checking in accordance with exemplary method400. Method700covers fetch/store relative operations in which the store/fetch address is formed as a displacement from the instruction address. The displacement specified in the instruction text represents the singed number of half-words (2 bytes) relative to the instruction address. For these instructions, length is 0 for 1 byte cache access, 1 for 2 bytes cache access, 3 for 4 bytes cache access and 7 for 8 bytes cache access. Also, these operand access for these instructions needs to be operand access aligned otherwise a specification address exception is realized. For example, an address for a 4 bytes access needs to be word aligned (i.e. least significant 2 bits of address are 0's) and an 8 byte access needs to be double words aligned (.e. least significant 3 bits of address are 0's). Method proceeds according to the following:

Block702: same as block502.

Block706: same as block506.

Block708: same as block516.

Block710: D is set as in block508. In this example, DL is set to the same value as D. In the previous examples like inFIG. 5andFIG. 6, DL used to be set to the addition of displacement and length. In this example, displacement from the instruction text needs to be shifted first before being used since it represents the number of half words, there was no time in a cycle to locate the displacement from, shift it left by 1 and add it to length field. This example, relied on the fact that the address is aligned to the length of the memory access and as result the start address least significant 1, 2 or 3 bits are 0's depending on the length of operand fetch. Therefore the end address is the logical OR of the start address with the length field. A bit flip in the least significant bits of the starting address needs to be identified as an error instead of causing an address exception because the address is not aligned to storage operand length.

Block712: Calculate dup_start_address(61:62)=IA(61:62)+D(61:62); note that IA(63) and D(63) are 0's in this example since instruction address is even and D is formed by the instruction displacement field by shifting it left by 1 bit. Dup_start_address is used to check against start_address(61:62).

end_address=(B+X+DL_int) OR Length. In this example, DL=D from block710(since starting address is aligned, then adding length is equivalent to logical-OR'ing it).

Block716: If start_dup does not equal to start, report error per block728

Block718: Same as block514.

Block720: same as block512.

Block722: Adjust Res3 length based on dup_start_address(61:62) and least significant 2 bits of the length (length(5:6) (len(0:4)=0's). This is needed since the end_address least significant bits are formed by logical ORing the start_address with the Length: Note in a Residue 3 arithmetic, subtracting 2 is identical to adding 1 and subtracting 1 is identical to adding 2. Adjust Res3 of length(0:7) as follows:

Block724: same as block518.

Blocks726,728: same as blocks520,522.

FIG. 8illustrates an example of a method800for address generation checking in accordance with exemplary method400. Method800covers a long store (9 bytes to 256 bytes stores) type instructions similar to store STM (store multiple). For a long store type instruction, two cache accesses are needed (these cache accesses are referred to as cache pretests allocating store queue/buffer and checks for cache exception) In specific, this method covers the 2ndcache access since the 1stcache access is covered by the method described inFIG. 5. Method proceeds according to the following:

Block804: same as block504.

Block806: same as block506.

Block808: same as block508.

Block810: This represents the 2ndcycle when the Address Increment (AI) is generated The first address (AA) is calculated like inFIG. 5by going from block808to block812. Note that the D register is set to the previous value of DL, and the values of B and X and DL are held.

Block812: same as block510.

Block814: same as block514.

Block816: Set Res3 of Length to 0 since the start_address for this AI is expected to pint to least significant byte of the storage operand. In other words, start_address=end_address for the address increment (AI) of this long store; therefore Res(Length)=0.

Block818: Same as block518.

Blocks820,822: same as blocks520,522.

FIG. 9illustrates an example of a method900for address generation checking in accordance with exemplary method400. Method900covers long operand fetches (more than 9 bytes) where many fetches to memory are needed to fetch all the bytes of the operand. Examples on this long operand fetch instructions are Load Multiple (e.g. LM, LMG) and Move Character Long (MVC). As indicated before, the first fetch to a long operand is referred to as AA and is covered by Method ofFIG. 5, and all subsequent fetches (AI's) are covered by this method. Method proceeds as follows;

Block914: Save copy of latest START address (prev_start_address).

Block918: same as block514.

Block920: same as block518, except no wrap.

Block922: Save copy of Res3(START) and Res3(END)

Blocks924,926: Res3_start_address_ai should be equal to saved Res3_end_address, otherwise report an error. The process can be also covered by a method similar to method600ofFIG. 6by adjusting the length for every new address increment AI. i.e. the effective length for an AI will be the total length of the operand minus the number of bytes fetched so far. In this case, checking can be made similar to Block624.

FIG. 10illustrates an example of a method1000for address generation checking in accordance with exemplary method400. Method1000covers usage of AGEN adders for non store/fetch operations, such as load address type instructions (e.g. LA, LAE, LAY, etc.) and branch target address, etc., and proceeds according to the following:

Block1002: same as block502.

Block1004: same as block504.

Block1006: same as block506.

Block1008: same as block508, except Len set to 0 (thus, Res3(Len)=0).

Block1010: same as block510.

Block1012: same as block512.

Block1014: same as block514.

Block1016: same as block518.

Blocks1018,1020: same as blocks520,522.

Elements of exemplary computer system100, exemplary processor subsystem200, and address generation subsystem300are illustrated and described with respect to various components, modules, blocks, etc. for exemplary purposes. It should be understood that other variations, combinations, or integrations of such elements that provide the same features, functions, etc. are included within the scope of embodiments of the invention.

The flow diagram described herein is just an example. There may be many variations to this diagram or the blocks (or operations) thereof without departing from the spirit of embodiments of the invention. For instance, the blocks may be performed in a differing order, or blocks may be added, deleted or modified. All of these variations are considered a part of the claimed invention. Furthermore, although an exemplary execution of the flow diagram blocks is described with respect to elements of exemplary computer system100, exemplary processor subsystem200, and address generation subsystem300, execution of the flow diagram blocks may be implemented with respect to other systems, subsystems, etc. that provide the same features, functions, etc. in accordance with exemplary embodiments of the invention.