System for modifying relocatable object code files to monitor accesses to dynamically allocated memory

• US 5,193,180 A
• Filed: 06/21/1991
• Issued: 03/09/1993
• Est. Priority Date: 06/21/1991
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: Pure Software, Inc. (International Business Machines Corporation)
• Inventors: Hastings, Reed
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Treat, William M.
• Application Number:
  US07/718,573
• Time in Patent Office: 627 Days
• Field of Search: 395/650, 395/575, 395/325, 371/16.5, 371/19, 371/29.1
• US Class Current: 717/163
• CPC Class Codes: G06F 11/3624 by performing operations on the source code, e.g. via a compiler
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/3644 by instrumenting at runtime
• CPC Class Codes: G06F 8/447 Target code generation
• CPC Class Codes: G06F 8/54 Link editing before load time
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management
• CPC Class Codes: G06F 9/44521 Dynamic linking or loading; Link editing at or after load time, e.g. Java class loading

Abstract

An object code expansion program inserts new instructions and data between preexisting instructions and data of an object code file; offsets are modified to reflect new positions of the preexisting instructions and data. For each item of preexisting object code (instructions or data), the following steps are performed: making a new code block comprising any desired new instructions and the item, and storing it as new object code; tracking the location of the item and the new code block within the new object code; and tracking items that contain inter-item offsets. Then, each inter-item offset is updated using the new location of the item or new code block, as required. Finally, offsets in symbol tables and relocation structures are updated with the new location of the item.

This expansion program is used to add instructions to object code files of a second program, to monitor substantially all of the memory accesses of the second program. The added instructions establish and maintain a memory status array with entries for memory locations that are validly accessibly by the second program; entries indicate the status of corresponding memory locations. The memory status array is used to check for the errors of writing to unallocated memory and reading from unallocated or uninitialized memory. Also, the data section of the object code files are expanded with extra dummy entries to aid in the detection of array bounds violations and similar data errors. Furthermore, watchpoints can be established for more comprehensive monitoring.

Claims

1. A computer implemented method for inserting new instructions between preexisting instructions, a set of said preexisting instructions requiring new instructions, said method comprising the steps of;

a) providing in a computer storage medium an old object code table containing said preexisting instructions;

b) providing in a computer storage medium a set of tables, said tables being for storing items, wherein said items include instructions and data, said items having locations within said tables, said set of tables including

i) a new object code table for storing new code blocks of preexisting instructions and new instructions,

ii) an inter-item offset table for storing inter-item offsets, wherein inter-item offsets are referenced from a base and point to a target, and wherein said base and target are items in said old object code table,

iii) a forward index table for storing locations of items within said new object code table, and

iv) a forward control index table for storing locations of new code blocks within said new object code table;

c) performing the following computer implemented steps for each item in said old object code table;

i) storing a new code block into said new object code table, said new code block comprising said each item in said old object code table, and, for items in said set of said preexisting instructions requiring new instructions, said new code block additionally comprising new instructions;

ii) storing said location within said new object code table of said item in said old object code table into said forward index table;

iii) storing said location of said new code block within said new object code table into said forward control index table; and

(iv) indicating, when said each item in said old object code table contains an inter-item offset, said inter-item offset in said inter-item offset table; and

d) updating each inter-item offset indicated in said inter-item offset table, using said forward control index table for inter-item offsets which are for program control transfer, and using said forward index table for inter-item offsets which are not for program control transfer.

2. The computer implemented method of claim 1, wherein

said indicating step further comprises indicating in said inter-item offset table said locations within said old object code table of said target and base of said inter-item offset and said location of said inter-item offset in said new object code table;

and

said updating step further comprises

i) determining a forward location for said base using said forward index table,

ii) determining a forward location for said target using said forward control index table when said target is a program control transfer destination and using said forward index table when said target is not a program control transfer destination, and

iii) updating said inter-item offset in said new object code table using said forward locations of said base and target.

3. A computer implemented method for inserting new instructions into a relocatable object file having preexisting instructions, data, and linking and debugging auxiliary structures, a set of said preexisting instructions requiring new instructions, said method comprising the steps of:

a) providing in a computer storage medium a set of tables, said tables being for storing items, wherein said items include instructions and data, said items having locations within said tables, said set of tables including

i) an old object code table for storing said preexisting instructions and data;

ii) a new object code table for storing new code blocks or preexisting instructions and new instructions,

iii) an inter-item offset table for storing inter-item offsets, wherein inter-item offsets are referenced from a base and point to a target, and wherein said base and target are items in said old object code table,

iv) a forward index table for storing locations of items within said new object code table, and

v) a forward control index table for storing locations of new code blocks within said new object code table;

b) copying said preexisting instructions and data of said relocatable object file into said old object code table;

c) performing the following computer implemented steps for each item in said old object code table;

i) storing a new code block into said new object code table, said new code block comprising said each item in said old object code table, and, for items in said set of said preexisting instructions requiring new instructions, said new code block additionally comprising new instructions;

ii) storing said location within said new object code table of said each item in said old object code table into said forward index table;

iii) storing said location of said new code block within said new object code table into said forward control index table; and

iv) indicating, when said each item in said old object code table contains an inter-item offset, said locations within said old object code table of said target and base of said inter-item offset and of said offset in said new object code table;

d) for each inter-item offset indicated in said inter-item offset table, determining a forward location for said base using said forward index table, determining a forward location for said target using said forward control index table when said target is a program control transfer destination and using said forward index table when said target is not a program control transfer destination, and updating said inter-item offset in said new object code table using said forward locations of said base and target;

e) evaluating compliance of each inter-item offset indicated in said inter-item offset table with a maximum-byte offset constraint, using said forward locations of said base and target;

f) updating offsets in said auxiliary structures; and

g) creating anew relocatable object file comprising said new object code table and said updated auxiliary structures.

4. The computer implemented method of claim 3, wherein said auxiliary structures include text relocation structures and data relocation structures, and wherein said step of updating offsets in auxiliary structures comprises updating offsets in said text and data relocation structures using said forward index table.

5. The computer implemented method of claim 4, wherein said relocatable object file also has a set of symbol structures containing instruction offsets, said method further comprising the step of updating said instruction offsets contained in said symbol structures using said forward control index table.

6. A computer implemented method for inserting new instructions into a relocatable object file having preexisting instructions, data, and auxiliary structures, said auxiliary structures having at least some offsets and comprising text relocation structures, data relocation structures, and symbol structures, wherein a set of said preexisting instructions requires new instructions, said method comprising the steps of:

a) providing in a computer storage medium a set of tables, said tables being for storing items, wherein said times include instructions and data, said items having locations within said tables, said set of tables including

i) an old object code table containing said preexisting instructions and data of said relocatable object file;

ii) a new object code table for storing new code blocks of preexisting instructions and new instructions,

iii) an inter-item offset table for storing inter-item offsets, wherein inter-item offsets are referenced from a base and point to a target, and wherein said base and target are items in said old object code table,

iv) a forward index table for storing locations of items within said new object code table,

v) a forward control index table for storing locations of new code blocks within said new object code table, and

vi) an entry point table for storing function entry addresses;

c) for each symbol structure associated with a function and having a function entry address, storing said function entry address in said entry point table, said entry address indicating in said old object code table a first instruction of said function, said function also having a last instruction, all items between said first instruction and said last instruction also being instructions of said function;

d) performing the following computer implemented steps for each entry address stored in said entry point table;

i) performing the following computer implemented steps for each preexisting instruction of said function indicated by said each entry address stored in said entry point table;

1) storing a new code block into said new object code table, said new code block comprising said each preexisting instruction of said indicated function, and, for preexisting instructions in said set of preexisting instructions requiring new instructions, said new code block additionally comprising new instructions;

2) storing, into said forward index table, said location within said new object code table of said each preexisting instruction of said indicated function;

3) storing said location of said new code block within said new object code table into said forward control index table; and

4) indicating, when said each item in said old object code table contains an inter-item offset, said locations within said old object code table of said target and base of said inter-item offset and of said offset in said new object code table; and

ii) performing the following computer implemented steps for each function item in said old object code table after the last preexisting instruction of said function indicated by said entry address and before a closest next entry address;

1) copying said each function item into said new object code table;

2) storing said location of said each function item within said new object code table into said forward index table;

e) for each inter-item offset indicated in said inter-item offset table, determining a forward location for said base using said forward index table, determining a forward location for said target using said forward control index table for targets which are program control transfer destinations and using said forward index table for targets which are not program control transfer destinations, and updating each inter-item offset in said new object code table using said forward locations of said base and target;

f) updating offsets in said auxiliary structures; and

g) creating a new relocatable object file comprising said new object code table and said updated auxiliary structures.

7. A computer implemented method for equipping a computer program with the ability to monitor most of its own memory accesses, wherein memory access types include read and write, said method comprising the steps of:

performing the following computer implemented steps for substantially all relocatable object files for said program, said relocatable object files containing instruction items of preexisting object code, wherein instruction items include instructions and data, said instruction items having locations within said preexisting object code;

a) providing in a computer storage medium a new object code table for storing instruction items;

b) storing into said new object code table, for each preexisting instruction item in said preexisting object code, a new code block including said preexisting instruction item, said storing step comprising

i) adding memory read monitoring code to said new code block, for preexisting read instruction items, for which performance involves a memory access of a read type; and

ii) adding memory write monitoring code to said new code block, for preexisting write instruction items, for which performance involves a memory access of a write type;

c) updating offsets in said new object code table;

d) creating in a computer storage medium a new relocatable object film comprising instruction items from said new object code file.

8. The computer implemented method of claim 7, wherein said computer program is capable of accessing a set of memory regions, said method further for equipping the computer program with the ability to establish memory access status information for substantially all memory locations in said set of accessible memory regions, said status information indicating three states of dynamically allocated memory, said states being allocated-and-initialized, allocated-and-uninitialized, and unallocated, said allocated-and-initialized state corresponding to a memory location having been allocated to said computer program and having been initialized by having valid data for said computer program written thereto, said allocated-and-uninitialized state corresponding to a memory location having been allocated to said computer program but not having been initialized by having valid data for said computer program written thereto, and said unallocated state corresponding to a memory location not having been allocated to said computer program,

wherein said storing step further comprises

adding allocation indicating code for items for which performance would involve allocating memory, said allocation indicating code updating said status information for said allocated memory to be in said allocated-and-uninitialized state;

adding deallocation indicating code for items for which performance would involve allocating memory, said deallocation indicating code updating said status information for said deallocated memory to be in said unallocated state; and

wherein

said substep of adding memory read monitoring code further comprises adding code to signal an error when said accessed memory is not in said allocated-and-initialized state;

said substep of adding memory write monitoring code further comprises adding code for signalling an error when said accessed memory is in said unallocated state, and for updating said status information for said allocated memory to be in said allocated-and-initialized state when said accessed emory is not in said unallocated state.

9. The computer implemented method of claim 7,

wherein said providing step further comprises providing an inter-item offset table for storing inter-item offsets, and a forward table for storing locations of items in said new object code table;

wherein said storing step further comprises performing for each preexisting item in said preexisting object code the steps of storing into said forward table a forward location within said new object code table for said each preexisting item, and storing in said inter-item offset table an inter-item offset for items which contain an inter-item offset;

and wherein said updating step comprises, for each inter-item offset indicated in said inter-item offset table, updating said each inter-item offset using said forward table.

10. The computer implemented method of claim 9,

wherein said forward table comprises a forward index table for storing locations of items within said new object code table, and a forward control index table for storing locations of new code blocks within said new object code table;

wherein said substep of storing a forward location further comprises

storing said location of said item within said new object code table into said forward index table;

storing said location of said new code block within said new object code table into said forward control index table; and

wherein said updating step comprises using said forward control index table for inter-item offsets which are for program control transfer, and using said forward index table which are not for program control transfer.

11. In a computer, an executable computer programs capable of monitoring most of its own memory accesses, wherein memory access types include read and write, said computer program capable of accessing a set of memory regions, said computer program comprising

a) status information maintenance computer code for causing the computer to maintain memory status information in a dedicated table having entries corresponding to memory addresses for at least most memory locations in said set of accessible memory regions, said status information indicating three states of dynamically allocated memory, said states being allocated-and-initialized, allocated-and-uninitialized, and unallocated, said allocated-and-initialized state corresponding to a memory location having been allocated to said computer program and having been initialized by having valid data for said computer program written thereto, said allocated-and-uninitialized state corresponding to a memory location having been allocated to said computer program but not having been initialized by having valid data for said computer program written thereto, and said unallocated state corresponding to a memory location not having been allocated to said computer program;

b) write error signalling computer code for signalling an error if a memory location having unallocated status is accessed by a memory access of a write type;

c) read error signalling computer code for signalling an error if a memory location having unallocated status is accessed by a memory access of a read type and if a memory location having allocated-and-uninitialized status is accessed by am memory access of a read type.