Method for efficient soft real-time execution of portable byte code computer programs6081665
Abstract
The invention is a method for use in executing portable virtual machine computer programs under real-time constraints. The invention includes a method for implementing a single abstract virtual machine execution stack with multiple independent stacks in order to improve the efficiency of distinguishing memory pointers from non-pointers. Further, the invention includes a method for rewriting certain of the virtual machine instructions into a new instruction set that more efficiently manipulates the multiple stacks. Additionally, using the multiple-stack technique to identify pointers on the run-time stack, the invention includes a method for performing efficient defragmenting real-time garbage collection using a mostly stationary technique. The invention also includes a method for efficiently mixing a combination of byte-code, native, and JIT-translated methods in the implementation of a particular task, where byte-code methods are represented in the instruction set of the virtual machine, native methods are written in a language like C and represented by native machine code, and JIT-translated methods result from automatic translation of byte-code methods into the native machine code of the host machine. Also included in the invention is a method to implement a real-time task dispatcher that supports arbitrary numbers of real-time task priorities given an underlying real-time operating system that supports at least three task priority levels. Finally, the invention includes a method to analyze and preconfigure virtual memory programs so that they can be stored in ROM memory prior to program.
Claims
What is claimed is:
1. A real-time virtual machine method (RTVMM) for implementing real-time systems and activities, the RTVMM comprising the steps:
implementing an O-OPL program that can run on computer systems of different designs, an O-OPL program being based on an object-oriented programming language (O-OPL) comprising object type declarations called classes, each class definition describing the variables that are associated with each object of the corresponding class and all of the operations called methods that can be applied to instantiated objects of the specified type, a "method" being a term of art describing the unit of procedural abstraction in an object-oriented programming system, an O-OPL program comprising one or more threads wherein the run-time stack for each thread is organized so as to allow accurate identification of type-tagged pointers contained on the stack without requiring type tag information to be updated each time the stack's content changes, the O-OPL being an extension of a high-level language (HLL) exemplified by Java, HLL being an extension of a low-level language (LLL) exemplified by C and C++, a thread being a term of art for an independently-executing task, an O-OPL program being represented at run time by either O-OPL byte codes or by native machine codes.
2. The RTVMM of claim 1 wherein an O-OPL program utilizes a pointer stack and a non-pointer stack.
3. The RTVMM of claim 1 wherein an O-OPL program comprises one or more classes represented in read-only memory, the methods thereof h aving been converted into O-OPL byte codes prior to run time.
4. The RTVMM of claim 1 wherein an O-OPL program comprises one or more classes represented in read-only memory, the methods thereof having been converted into native machine language prior to run time.
5. The RTVMM of claim 1 wherein a byte-code O-OPL method is an O-OPL method represented at run time by O-OPL byte codes, a byte-code O-OPL method being written in O-OPL, an O-OPL, method represented at run time by native machine codes being either a native O-OPL method or a native-translated O-OPL method, a native O-OPL method being written in LLL, a native-translated O-OPL method being written in HLL, the implementing step comprising the steps:
compiling the byte-code O-OPL methods into HLL byte codes and transforming the HLL byte codes into O-OPL byte codes;
compiling the native O-OPI, methods into native machine codes;
compiling the native-translated O-OPL methods into HLL byte codes and compiling HLL byte codes into native machine codes.
6. The RTVMM of claim 1 wherein a calling function is a native-translated O-O-OPL method and the called function is a byte-code method, a native-translated O-OPL method being an O-OPL method written using byte codes which are translated into native machine language at the time of execution, a byte-code method being a method written using O-OPL or HLL and translated into O-OPL, byte codes prior to execution, the implementing step comprising the steps:
providing each byte-code method with a stub procedure which honors the native-translated method execution protocol, the stub procedure switching from native-translated method to O-OPL byte code interpretation protocols and then invoking an O-OPL, interpreter.
7. The RTVMM of claim 6 wherein the stub procedure switches back to the native-translated O-OPL mode when the O-OPL, interpreter returns.
8. The RTVMM of claim 1 wherein a calling function is a native-translated O-OPL method and the called function is a native method, a native-translated O-OPL method being a method written using byte codes which are translated into native machine language at the time of execution, a native method being a method written in LLL, the implementing step comprising the steps:
providing each native method with a stub procedure which honors the native-translated method execution protocol, the stub procedure switching from native-translated method to LLL-code protocols and then invoking the native method.
9. The RTVMM of claim 8 wherein the stub procedure switches back to the native-translated O-OPL mode when the O-OPL interpreter returns.
10. The RTVMM of claim 1 wherein the implementing step comprises the step:
causing an application thread to periodically check whether the system desires to preempt the thread.
11. The RTVMM of claim 1 wherein the implementing step comprises the step:
causing an application thread that is to be preempted to provide notification as to when the thread is at a point where safe garbage collection can take place.
12. The RTVMM of claim 1 wherein one of the implemented threads is a garbage collection thread that operates asynchronously thereby resulting in the garbage collection thread being interleaved with other threads in arbitrary order, objects subject to garbage collection being either finalizable or non-finalizable, a finalizable object being subject to an action that is performed when the memory space allocated to the finalizable object is reclaimed by the garbage collection thread, the finalizing action being specified by including a non-empty finalizer method in the class definition, the garbage collection thread being able to distinguish a thread's pointer variables from the thread's non-pointer variables, preemption of a thread being allowed only if the thread is in a state identified as a preemption point, a thread being allowed to hold pointers in variables between preemption points that may not be visible to the garbage collection thread, pointer variables that may not be visible to the garbage collection thread being called fast pointers, pointer variables that are visible to the garbage collection thread being called slow pointers, each LLL, function being identified as either preemptible or non-preemptible.
13. The RTVMM of claim 12 wherein the implementing step comprises the steps:
causing the values of essential fast pointers to be copied into slow pointers immediately prior to a preemption point of a preemptible thread. (5.0/4)
causing the values of essential fast pointers to be restored after preemption by causing the values of the slow pointers to be copied to the locations where the values of the fast pointers were previously stored.
14. The RTVMM of claim 12 wherein the implementing step comprises the steps:
causing the values of all of the essential fast pointers of a preemptible LLL function to be copied into slow pointers prior to calling the prcemptible LLL function;
causing the values of the essential fast pointers to be restored when the called preemptible LLL function returns by causing the values of the slow pointers to be copied to the locations where the values of the fast pointers were previously stored.
15. The RTVMM of claim 12 wherein the implementing step comprises the steps:
providing a plurality of macros representing (1) an interface that permits the use of different garbage-collection techniques and (2) an implementation of a mostly-stationary garbage-collection technique.
16. The RTVMM of claim 12 wherein the implementing step comprises the step:
providing parameterized access to heap memory in order to facilitate the implementation of read and write barriers, heap memory being a region of memory wherein objects of arbitrary size can be allocated space to satisfy the dynamic memory needs of application programs, heap memory being subject to garbage collection.
17. The RTVMM of claim 16 wherein the implementing step comprises the step:
providing a macro that returns the value of a fast pointer in the heap given the identity of the pointer and its type.
18. The RTVMM of claim 16 wherein the implementing step comprises the step:
providing a macro that assigns a value from a fast pointer in heap memory given the identity of the pointer, its type, and the value.
19. The RTVMM of claim 16 wherein the implementing step comprises the step:
providing a macro that returns the value of a nonpointer in heap memory given the identity of the nonpointer and its type.
20. The RTVMM of claim 16 wherein the implementing step comprises the step:
providing a macro that assigns a value to a nonpointer in heap memory given the identity of the nonpointer, its type, and the value.
21. The RTVMM of claim 16 wherein the implementing step comprises the step:
providing direct access to stack data using LLL pointer indirection.
22. The RTVMM of claim 21 wherein the implementing step comprises the step:
representing stack pointers by LLL global variables declared as pointers.
23. The RTVMM of claim 12 wherein the implementing step comprises the step:
maintaining a finalizable list of finalizable objects that have not been finalized, a finalizable object being removed from the finalizable list after it has been finalized, the finalizable list of objects being linked through a "finalize link" field.
24. The RTVMM of claim 12 wherein the implementing step comprises the steps:
partitioning memory into at least three demi-spaces, at least one of the demi-spaces being a static space excluded from the garbage collection process;
designating two of the demi-spaces as to-space and from-space at the beginning of a garbage collection cycle, live objects residing in from-space subsequently being copied into to-space;
designating the remaining demi-spaces as mark-and-sweep spaces at the beginning of a garbage collection cycle, the mark-and-sweep spaces being garbage collected using a mark-and-sweep technique.
25. The RTVMM of claim 24 wherein the implementing step comprises the step:
including an "activity pointer" field for each object in memory, the "activity pointer" identifying the activity that was responsible for allocating the object, the "activity pointer" field containing a "null" value if the object was not allocated by a real-time activity.
26. The RTVMM of claim 25 wherein the implementing step comprises the step:
maintaining a free pool of space segments for to-space and for each mark-and-sweep sweep space, a free pool being organized as a plurality of doubly-linked lists, each linked list being a list of free space segments ranging in size from a lower value to an upper value, the size ranges for the plurality of linked lists being non-overlapping;
causing the "activity pointer" field to specify the size of a free space segment.
27. The RTVMM of claim 24 wherein the implementing step comprises the step:
including a "signature pointer" field for each object in memory, the "signature pointer" field containing a pointer to a structure that represents the internal organization of the O-OPL data within the object.
28. The RTVMM of claim 27 wherein the implementing step comprises the steps:
maintaining a free pool of space segments for to-space and for each mark-and-sweep space, a free pool being organized as a plurality of doubly-linked lists, each linked list being a list of free space segments ranging in size from a lower value to an upper value, the size ranges for the plurality of linked lists being non-overlapping;
causing the "signature pointer" field to be used as a backward link to the preceding segment.
29. The RTVMM of claim 24 wherein a garbage-collection cycle begins, the implementing step comprising the steps:
causing the non-empty mark-and-sweep space having the most available free space to be designated as the new from-space;
causing the old to-space to be designated as the new to-space if the allocated space within the new from-space is less than the free space available as a single contiguous region in the old to-space; otherwise,
causing the old from-space to be designated as the new to-space.
30. The RTVMM of claim 24 wherein the implementing step comprises the step:
including a "scan list" field for each object in memory, the "scan list" field distinguishing marked and unmarked objects residing in a mark-and-sweep space but not on a free list, the "scan list" field for each object in a mark-and-sweep space having a "scan clear" value at the beginning of a garbage collection cycle, an object recognized as being a live object being placed on a list of recognized live objects, the "scan list" field for an object on the list of recognized live objects having either a "scan end" value denoting the last object on the list of recognized live objects or a value identifying the next object on the list of recognized live objects, the "scan list" field for an object residing on a free list within a mark-and-sweep space or to- space having the "scan free" value, the "scan list" field for an object residing in from-space which has been scheduled for copying into to-space being a pointer to the to-space copy, the "scan list" field otherwise being assigned the "scan clear" value, the "scan list" field for an object residing in to-space having the "scan clear" value at the beginning of a garbage collection cycle, a to-space object recognized as live during garbage collection being placed on a list of recognized live objects, the "scan list" field for a to-space object on the list of recognized live objects having a value identifying the next object on the list of recognized live objects, the "scan list" field for each object queued for copying into to-space having the "scan end" value denoting that the object is live.
31. The RTVMM of claim 24 wherein the implementing step comprises the steps:
providing a memory allocation budget for each real-time activity;
allocating memory from the memory allocation budget to an object associated with the real-time activity;
causing the garbage collection thread to credit the memory allocation budget of the real-time activity when the memory allocated to the object is reclaimed.
32. The RTVMM of claim 24 wherein a real-time activity has allocated memory to an object which is subject to finalization and the garbage collection thread endeavors to reclaim the allocated memory, the implementing step comprising the step:
causing the garbage collection thread to place the object on a list of the real-time activity's objects that are awaiting finalization.
33. The RTVMM of claim 24 wherein the implementing step comprises the step:
causing memory space to be allocated, memory space being preferably allocated in the mark-and-sweep space having the requisite space available and that is most full, memory space being allocated in to-space only if the allocation cannot be made in any of the mark-and-sweep sweep spaces.
34. The RTVMM of claim 24 wherein the implementing step comprises the steps:
causing a "finalize link" bit and a "finalize object" bit in an "activity pointer" field of a finalizable object to be set when space is allocated to the finalizable object, the "finalize link" bit being set indicating that the object has a "finalize link" field appended to the object, the "finalize object" bit being set indicating that the object needs to be finalized;
causing the "finalize object" bit to be cleared when a finalizable object has been finalized.
35. The RTVMM of claim 24 wherein a pointer is to be written into memory, the implementing step comprising the steps: causing the pointer to an object in from-space to be replaced by a pointer to the object's new address in to-space;
causing an object in mark-and-sweep space to which the pointer points to be marked if the object has not yet been marked.
36. The RTVMM of claim 24 wherein the implementing step comprises the steps:
causing the available memory in a newly-selected to-space to be divided into a new-object segment for allocation of memory to new objects and an old-object segment for receiving copies of live from-space objects, the old-object segment being equal to or larger than the allocated space in from-space, new objects being allocated space in sequence from the end of the new-object segment away from the old-object segment, old objects being copied in sequence from the end of the old-object segment away from the new-object segment;
causing the unallocated portions of the old-object segment and the new-object segment to be coalesced into a single contiguous segment of free memory at the end of a garbage collection cycle.
37. The RTVMM of claim 24 wherein, after to-space and from-space have been selected at the beginning of a garbage collection cycle, the implementing step comprises the steps:
causing the free pools of memory in the mark-and-sweep spaces and to-space to be linked together into a global free pool, the free pools of the mark-and-sweep spaces being linked in increasing order of amount of free memory, the free pool of to-space being linked to the mark-and-sweep space having the greatest amount of free memory, a request for a new memory allocation being satisfied by the first memory segment of sufficient size found by searching the global free pool according to the linking order.
38. The RTVMM of claim 24 wherein the implementing step comprises the steps:
maintaining a list of root pointers to live objects;
causing space for a copy of an object in to-space to be allocated if a root pointer to the object refers to from-space;
causing the from-space address of the object to be written in an "indirect pointer" field of the object's allocated space in to-space;
causing the root pointer to be replaced with the address of the object in to-space;
causing the to-space address of the object to be written into a "scan list" field of the object in from-space.
39. The RTVMM of claim 24 wherein the implementing step comprises the steps:
maintaining a list of root pointers to live objects;
causing an object to be marked if the root pointer to the object refers to a mark-and-sweep space or to-space and the object has not yet been marked, marking consisting of placing the object on a scan list.
40. The RTVMM of claim 24 wherein the marking and copying processes for a particular garbage collection cycle have been completed, the implementing step comprising the steps:
causing all objects needing finalization to be transferred from a list of finalizable objects to a finalizee list;
causing the transferred objects residing in mark-and-sweep space to be placed on a scan list;
causing the transferred objects residing in from-space to be placed on a copy list.
41. The RTVMM of claim 40 wherein the marking and copying processes for a particular garbage collection cycle have been completed, the implementing step comprising the steps:
causing an object from a list of finalizable objects to be transferred to a finalizee list if the object has not been marked or if the object is a from-space object that has not been copied into to-space, the object being placed on the copy list and space being allocated in to-space if the object resides in from-space, the object being marked by being placed on the scan list if the object resides in mark-and-sweep space.
42. The RTVMM of claim 41 wherein the implementing step comprises the step:
implementing the finalizee list by causing the address of the next finalizee on the activity's finalizee list to be placed in a "finalize link" field of a finalizee.
43. The RTVMM of claim 40 wherein the transfer of objects needing finalization on the list of finalizable objects to the finalizee list has been completed, the implementing step comprising the steps:
causing the objects on the copy list to be copied to to-space;
causing the objects on the scan list to be scanned, scanning consisting of tending each pointer contained within an object, tending being a term of art describing the garbage collection process of (1) examining a pointer and, if the object has not already been recognized as live, arranging for the referenced object to be subsequently scanned by placing the object on a scan list if it resides in a mark-and-sweep space or in to-space or by arranging for the object to be copied into to-space if it resides in from-space and (2) updating the pointer to refer to the object's new location if it has been queued for copying into to-space.
44. The RTVMM of claim 24 wherein the transfer of objects needing finalization from a list of finalizable objects to a finalizee list has been accomplished, the implementing step comprising the step:
causing each finalizee on the finalizee list to be transferred to the appropriate activity's finalizee list or onto an orphaned finalizee list.
45. The RTVMM of claim 44 wherein an activity's finalizee list is implemented by placing in an "activity pointer" field of a finalizee the address of the next finalizes on the activity's finalizee list.
46. The RTVMM of claim 44 wherein after transferring a finalizee on the finalizee list to the appropriate activity's finalizee list or onto an orphaned finalizee list, the implementing step comprises the step:
causing a "finalize link" bit in an "activity pointer" field of the object corresponding to the finalizee to be cleared, a cleared "finalize link" bit indicating that the object is no longer on the list of finalizable objects.
47. The RTVMM of claim 24 wherein the transfer of objects needing finalization from a list of finalizable objects to an activity's finalizee list or an orphaned finalizee list has been accomplished, the implementing step comprising the steps:
causing the mark-and-sweep spaces and to-space to be swept and identifying each object that is not marked, that is not on a free list, and that is a "hashlock object";
causing the garbage collection thread to copy the value of a "hash value" field of the "hashlock object" onto a list of recycled hash values if the list is not full; otherwise:
causing the garbage collection thread to (1) make the "hashlock object" live, (2) change a "signature" field in the "hashlock object" to represent a "hashcache object", (3) add the "hashcache object" to the list of recycled hash values, and (4) copy the value of the "hash value" field of the original "hashlock object" onto a list of recycled hash values.
48. The RTVMM of claim 24 wherein the transfer of objects needing finalization from a list of finalizable objects to an activity's finalizee list or an orphaned finalizee list has been accomplished, the implementing step comprising the steps:
causing from-space to be examined and each object to be identified that was not copied into to-space and that is a "hashlock object" with a hash value that needs to be reclaimed;
causing the garbage collection thread to copy the value of a "hash value" field of the "hashlock object" into a list of recycled hash values if the list is not full; otherwise:
causing the garbage collection thread to (1) make the "hashlock object" live, (2) change a "signature" field in the "hashlock object" to represent a "hashcache object", (3) add the "hashcache object" to the list of recycled hash values, and (4) copy the value of the "hash value" field of the original "hashlock object" onto a list of recycled hash values;
causing zeros to be written into all of from-space.
49. The RTVMM of claim 12 wherein the implementing step comprises the step:
designating portions of memory as a to-space and zero or more mark-and-sweep spaces;
maintaining a free pool of space segments for to-space and for each mark-and-sweep space, a free pool being organized as a plurality of linked lists, each linked list being a list of free space segments ranging in size from a lower value to an upper value, the size ranges for the plurality of linked lists being non-overlapping.
50. The RTVMM of claim 49 wherein an object of specified size is to be allocated space in a demi-space by an allocation routine, the allocation routine comprising the steps:
causing the linked list with the smallest size range having space segments equal to or greater than the specified size of the object to be selected from the free pool of the demi-space;
causing a portion of the space segment equal in size to the object to be allocated to the object;
causing the unallocated portion of the space segment to be returned to the appropriate linked list.
51. The RTVMM of claim 12 wherein the implementing step comprises the step:
designating portions of memory as a to-space, from-space, and zero or more mark-and-sweep spaces;
including an "indirect pointer" field for each object in memory, the "indirect pointer" field containing a pointer to the location of the currently valid copy of the data that corresponds to the object, the pointer pointing to the object itself for objects in a mark-and-sweep space, the pointer pointing to the location of the object that currently represents the object's contents for objects in to-space and from-space.
52. The RTVMM of claim 51 wherein the implementing step comprises the steps:
maintaining a free pool of space segments for to-space and for each mark-and-sweep space, a free pool being organized as a plurality of doubly-linked lists, each linked list being a list of free space segments ranging in size from a lower value to an upper value, the size ranges for the plurality of linked lists being non-overlapping;
causing the "indirect pointer" field to be used as a forward link to the succeeding segment.
53. The RTVMM of claim 12 wherein the implementing step comprises the step:
including an "activity pointer" field for each object in memory, the "activity pointer" identifying the real-time activity object that was responsible for allocation of the object, the "activity pointer" field containing a "null" value if the object was not allocated by a real-time activity;
maintaining a finalizees list of objects waiting to be finalized for each real-time activity, the objects on the finalizees list being linked through the "activity pointer" field;
maintaining a list of the headers of the finalizees lists, the pointer "finalizees" being a root pointer to the headers list.
54. The RTVMM of claim 53 wherein the implementing step comprises the step:
implementing a finalizer thread that operates in the background and is responsible for incrementally executing the finalizer methods associated with finalizee objects reachable from the "finalizees" pointer.
55. The RTVMM of claim 54 wherein the finalizer thread comprises the steps:
causing a finalizer method associated with a finalizee object to be executed;
causing the finalizee object to be removed from the associated finalizee list;
causing the "activity pointer" field of the finalizee object to be overwritten with a reference to the allocating object;
causing a "finalize object" bit in the "activity pointer" field of the finalizee object to be cleared indicating that the object has been finalized.
56. The RTVMM of claim 53 wherein the implementing step comprises the step:
implementing a finalizer thread that is part of a real-time activity and is responsible for incrementally executing the finalizer methods associated with finalizee objects associated with the real-time activity and reachable from the "finalizees" pointer.
57. The RTVMM of claim 56 wherein the finalizer thread comprises the steps:
causing a finalizer method associated with a finalizee object to be executed;
causing the finalizee object to be removed from the associated finalizee list;
causing the "activity pointer" field of the finalizee object to be overwritten with a reference to the allocating object;
causing a "finalize object" bit in the "activity pointer" field of the finalizee object to be cleared indicating that the object has been finalized.
58. The RTVMM of claim 53 wherein the implementing step of claim 1 comprises the steps:
causing memory space to be allocated to a finalizee list head object when an object associated with a particular activity and requiring finalization is encountered;
causing a finalizee list head pointer associated with the activity to be overwritten with a pointer to the finalizee list head object;
causing the finalizee list head object to be destroyed when the finalizee list becomes empty and overwriting the finalizee list head pointer with the "null" value.
59. The RTVMM of claim 1 wherein each object has a "lock" field initialized to a "null" value, the implementing step comprising the steps:
causing a "hashlock object" to be allocated memory space if the "lock" field of the object contains a "null" value;
causing the next available hash value to be identified;
causing the "hash value" field of the "hashlock object" to be initialized to the next available hash value;
causing the "lock" field of the object to be initialized to refer to the newly-allocated "hashlock object".
60. The RTVMM of claim 59 wherein the implementing step comprises the step:
causing the "hash value" field of the "hashlock object" to be overwritten to the next available hash value if the "lock" field of the object does not have a "null" value and if the "hash value" field has the value zero.
61. The RTVMM of claim 59 wherein one of the implemented threads is a garbage collection thread the implementing step comprising the steps:
maintaining a list of available hash values consisting of previously assigned hash values for which the corresponding objects have been reclaimed by the garbage collection thread;
causing one of the hash values on the list of available hash values to be designated as the next available hash value to be assigned to a "hash object" if the list of available hash values is non-empty;
causing a static counter to be incremented if the list of available hash values is empty and causing the new counter value to be designated as the next available hash value to be assigned to a "hash object".
62. The RTVMM of claim 1 wherein each object has a "lock" field initialized to a "null" value, the implementing step comprising the steps:
causing a "hashlock object" for each object needing either a lock or a hash value to be allocated memory space and initialized, the "hashlock object" having a "hash value" field;
causing the address of the "hashlock object" to be written into the "lock" field of the object;
causing the hash value of an object to be retrieved by reading the "hash value" field of the associated "hashlock object".
63. The RTVMM of claim 62 wherein a monitor object is to be accessed and a "lock" field of the monitor object has a "null" value, the implementing step comprising the steps:
causing memory space to be allocated for a "hashlock object";
causing a "count" field of the "hashlock object" to be initialized to 1;
causing a "u-owner" field of the "hashlock object" to be set to represent the current thread;
causing access to be granted to the monitor object.
64. The RTVMM of claim 62 wherein a monitor object is to be accessed and a "lock" field of the monitor does not have a "null" value thereby indicating the existence of a "hashlock object", the implementing step comprising the steps:
causing a "count" field of the "hashlock object" to be incremented;
causing a "u-owner" field of the "hashlock object" to be set to represent the current thread;
causing access to be granted to the monitor object; provided the "count" field is 0 or the "u-owner" field refers to the currently-executing thread; otherwise:
causing the currently-executing thread to be placed on a waiting list queue;
causing the execution of the currently-executing thread to be blocked until access can be granted to the monitor object.
65. The RTVMM of claim 62 wherein threads are assigned priorities and a higher-priority thread's access to an object is being blocked by a lower-priority thread, the implementing step comprising the step:
causing the priority of the higher-priority thread to be assigned to the lower-priority thread until the lower-priority thread releases its lock on the object.
66. The RTVMM of claim 62 wherein a thread requests access to a monitor object be terminated, the implementing step comprising the steps:
causing verification that a "u-owner" field of the "hashlock" object associated with the monitor object represents the thread;
causing a "count" field in the "hashlock" object to be decremented; if the new value in the "count" field is zero, then:
causing the "u-owner" field of the "hashlock" object to be set to represent the highest-priority member of a waiting list for the monitor object;
causing the "count" field of the "hashlock" object to be set to 1;
causing the removal of the highest-priority member of the waiting list for the monitor object;
provided the waiting list is not empty; otherwise:
causing the "u-owner" field of the "hashlock" object to be set to a "null" value.
67. The RTVMM of claim 62 wherein a thread's access to a monitor object has been terminated and a "hash value" field of a "hashlock object" associated with the monitor object is 0, the implementing step comprising the steps:
causing a "lock" field in the monitor object to be set to a "null" value;
causing the placement of the "hashlock object" on a list of available "hashlock objects" to be used in satisfying new requests for "hashlock objects".
68. The RTVMM of claim 67 wherein the placing step is accomplished by the step:
causing a "u-next" field in the "hashlock object" to be set to point to the next "hashlock object" on the list of "hashlock objects".
69. The RTVMM of claim 1 wherein the implementing step comprises the steps:
creating a normally-sleeping thread called a thread dispatcher;
causing the thread dispatcher to be awakened if an interrupt arrives from an alarm timer that has determined that a specified time period has expired, the thread dispatcher then suspending execution of the currently-executing thread;
causing the thread dispatcher to be awakened if an interrupt arrives indicating the necessity of preempting the currently-executing thread so that a sporadic task can be executed;
causing the thread dispatcher to be awakened if the currently-executing thread blocks on an I/O request, the thread dispatcher then suspending execution of the currently-executing thread.
70. The RTVMM of claim 69 wherein the implementing step comprises the step:
creating a watchdog thread that sends an interrupt to the thread dispatcher when a thread that is scheduled for execution blocks.
71. The RTVMM of claim 1 wherein the implementing step comprises the step:
creating a thread called a thread dispatcher which makes only one application task ready to run at a time in accordance with the priorities of the application tasks waiting to run.
72. The RTVMM of claim 1 wherein the implementing step comprises the step:
causing symbolic references to be replaced with integer indices and direct pointer references when a program is loaded into a computer system.
73. The RTVMM of claim 1 wherein the implementing step comprises the step:
causing all operands supplied to each byte-code instruction to be of the appropriate type prior to execution of a program.
74. The RTVMM of claim 1 wherein an O-OPL byte-code loader is used to load a program into a computer system, the implementing step comprises the step:
causing each byte code of an HLL program to be translated into an O-OPL byte code.
75. The RTVMM of claim 1 wherein the implementing step comprises the step:
causing symbolic values for constants to be replaced with the actual values when a class is loaded into a computer.
76. The RTVMM of claim 1 wherein there is a slow variant and a fast variant of every byte code instruction, a program to be loaded into a computer consisting of one or more slow variants, the implementing step comprising the step:
causing all byte codes corresponding to each method to be examined;
causing the slow variants to be replaced by the quick variants when a class is loaded into a computer.
77. The RTVMM of claim 1 wherein an O-OPL byte-code loader is used to load an HLL byte-code program into a computer system, the implementing step comprises the step:
causing each byte code to be examined when a class is loaded to determine whether it operates on pointer or non-pointer data;
causing pointers to be pushed onto and popped from a pointer stack;
causing non-pointers to bc pushed onto and popped from a non-pointer stack.
78. The RTVMM of claim 77 wherein the implementing step comprises the step:
causing the O-OPL byte-code loader to remap the offsets for all local-variable operations.
79. The RTVMM of claim 1 wherein the implementing step comprises the step:
utilizing only O-OPL pointer and non-pointer stacks in executing methods compiled by a JIT compiler, JIT standing for "just in time" and denoting a process for translating HLL, byte codes to native machine language codes on the fly, just in time for its execution, the translation of byte codes to native codes being a form of JIT compiling.
80. The RTVMM of claim 79 wherein a method compiled by a JIT compiler invokes a byte-code or nativc-code method, the implementing step comprises the step:
causing the frame and stack pointers necessary for the execution of the corresponding LLL routines to be set up;
causing the return address to be removed from the non-pointer stack and stored temporarily in an LLL local variable.
81. The RTVMM of claim 79 wherein a method of a thread is being executed, the method having been compiled by a JIT compiler, the implementing step comprising the step:
causing the status of the thread to be set to a value indicating that the thread can be preempted at any time.
82. The RTVMM of claim 79 wherein the implementing step comprises the step:
causing the JIT compiler to provide special translations of exception handling contexts so that only the contents of those registers are saved and restored that are actually live on entry into the exception handling context.
83. The RTVMM of claim 1 wherein the implementing step comprises the steps:
creating a thread called a thread dispatcher;
creating a watchdog thread that sends an interrupt to the thread dispatcher when a thread that is scheduled for execution blocks, the thread dispatcher then scheduling another thread for execution.
84. The RTVMM of claim 1 wherein each thread maintains its own versions of global variables "pointer stack pointer" (psp), "pointer stack frame pointer" (pfp), "non-pointer stack pointer" (npsp) and "non-pointer stack frame pointer" (npfp), the implementing step comprising the steps:
creating a thread called a thread dispatcher, the thread dispatcher saving psp, pfp, npsp, and npfp into the state variables of an executing thread when the executing thread is preempted, the preempted thread restoring these state variables when the preempted thread resumes execution.
85. The RTVMM of claim 1 wherein the implementing step includes providing a ROMizer tool which produces a load file appropriate for ROM storage, the ROMizer tool comprising the steps:
analyzing and verifying byte code;
performing byte code and constant-pool transformations;
supporting standard compiler transformations designed to optimize the performance of executed code.
86. The RTVMM of claim 85 wherein the implementing step relating to the load file includes the step:
causing an object placed into the object region to be marked by setting a "scan list" field of the object to SCAN-END.
87. The RTVMM of claim 85 wherein the implementing step relating to the load file includes the step:
causing the "indirect pointer" field of each object to refer to itself.
88. The RTVMM of claim 85 wherein the implementing step relating to the load file includes the steps:
causing all byte codes to be pre-transformed into an O-OPL instruction set;
causing all references to the constant pool to have been resolved.
89. The RTVMM of claim 85 wherein the implementing step relating to the load file includes the steps:
causing a search to be made for common strings;
causing multiple--string objects to refer to the same substring data.
Description
STATEMENT REGARDING FEDERALLY-SPONSORED RESEARCH AND DEVELOPMENT
(NOT APPLICABLE)
BACKGROUND OF THE INVENTION
Java (a trademark of Sun Microsystems, Inc.) is an object-oriented programming language with syntax derived from C and C++. However, Java's designers chose not to pursue full compatibility with C and C++ because they preferred to eliminate from these languages what they considered to be troublesome features. In particular, Java does not support enumerated constants, pointer arithmetic, traditional functions, structures and unions, multiple inheritance, goto statements, operator overloading, and preprocessor directives. In their place, Java requires all constant identifiers, functions (methods), and structures to be encapsulated within class (object) declarations. The purpose of this requirement is to reduce conflicts in the global name space. Java provides standardized support for multiple threads (lightweight tasks) and automatic garbage collection of dynamically-allocated memory. Furthermore, Java fully specifies the behavior of every operator on every type, unlike C and C++ which leave many behaviors to be implementation dependent. These changes were designed to improve software scalability, reduce software development and maintenance costs, and to achieve full portability of Java software. Anecdotal evidence suggests that many former C and C++ programmers have welcomed these language improvements.
One distinguishing characteristic of Java is its execution model. Java programs are first translated into a fully portable standard byte code representation. The byte code is then available for execution on any Java virtual machine. A Java virtual machine is simply any software system that is capable of understanding and executing the standard Java byte code representation. Java virtual machine support is currently available for AIX, Apple Macintosh, HPUX, Linux, Microsoft NT, Microsoft Windows 3.1, Microsoft Windows 95, MVS, Silicon Graphics IRIX, and Sun Solaris. Ports to other environments are currently in progress. To prevent viruses from being introduced into a computer by a foreign Java byte-code program, the Java virtual machine includes a Java byte code analyzer that verifies the byte code does not contain requests that would compromise the local system. By convention, this byte code analyzer is applied to every Java program before it is executed. Byte code analysis is combined with optional run-time restrictions on access to the local file system for even greater security. Current Java implementations use interpreters to execute the byte codes but future high-performance Java systems will have the capability of translating byte codes to native machine code on the fly. In theory, this will allow Java programs to run approximately at the same speed as C++.
Within Sun, development of Java began in April of 1991. Initially, Java was intended to be an implementation language for personal digital assistants. Subsequently, the development effort was retargeted to the needs of set-top boxes, CD-ROM software, and ultimately the World-Wide Web. Most of Java's recent media attention has focused on its use as a medium for portable distribution of software over the Internet. However, both within and outside of Sun, it is well understood that Java is much more than simply a language for adding animations to Web pages. In many embedded real-time applications, for example, the Java byte codes might be represented in system ROMs or might even be pre-translated into native machine code.
Many of the more ambitious "industrial-strength" sorts of applications that Java promises to enable on the Internet have associated real-time constraints. These applications include video conferencing integrated with distributed white boards, virtual reality, voice processing, full-motion video and real-time audio for instruction and entertainment, and distributed video games. More importantly, the next generation Web client will have even more real-time requirements. Future set-top devices will connect home televisions to the Web by way of cable TV networks. Besides all of the capabilities just mentioned, these systems will also support fully interactive television applications.
Java offers important software engineering benefits over C and C++, two of the more popular languages for current implementation of embedded real-time systems. If Java could be extended in ways that would allow it to support the cost-effective creation of portable, reliable real-time applications, the benefits of this programming language would be realized by a much larger audience than just the people who are implementing real-time Web applications. All developers of embedded real-time software could benefit. Some of the near-term applications for which a real-time dialect of Java would be especially well suited include personal digital assistants, real-time digital diagnosis (medical instrumentation, automotive repair, electronics equipment), robotics, weather monitoring and forecasting, emergency and service vehicle dispatch systems, in-vehicle navigation systems, home and business security systems, military surveillance, radar and sonar analysis, air traffic control, and various telephone and Internet packet switching applications.
This invention relates generally to computer programming methods pertaining to real-time applications and more specifically to programming language implementation methods which enable development of real-time software that can run on computer systems of different designs. PERC (a trademark of NewMonics Inc.) is a dialect of the Java programming language designed to address the special needs of developers of real-time software.
PERC has much to offer developers of embedded real-time systems. High-level abstractions and availability of reusable software components shorten the time-to-market for innovative products. Its virtual machine execution model eliminates the need for complicated cross-compiler development systems, multiple platform version maintenance, and extensive rewriting and retesting each time the software is ported to a new host processor. It is important to recognize that the embedded computing market is quite large. Industry observers have predicted that by the year 2010, there will be ten times as many software programmers writing embedded systems applications as there will be working on software for general purpose computers.
Unlike many existing real-time systems, most of the applications for which PERC is intended are highly dynamic. New real-time workloads arrive continually and must be integrated into the existing workload. This requires dynamic management of memory and on-the-fly schedulability analysis. Price and performance issues are very important, making certain traditional real-time methodologies cost prohibitive. An additional complication is that an application developer is not able to test the software in each environment in which it is expected to run. The same Java byte-code application would have to run within the same real-time constraints on a 50 MHz 486 and on a 300 MHz Digital Alpha. Furthermore, each execution environment is likely to have a different mix of competing applications with which this code must contend for CPU and memory resources. Finally, every Java byte-code program is supposed to run on every Java virtual machine, even a virtual machine that is running as one of many tasks executing on a time-sharing host. Clearly, time-shared virtual machines are not able to offer the same real-time predictability as a specially designed PERC virtual machine embedded within a dedicated microprocessor environment. Nevertheless, such systems are able to provide soft-real-time response.
GLOSSARY OF TERMS
Accurate Garbage Collection, as the term is used in this invention disclosure, describes garbage collection techniques in which the garbage collector has complete knowledge of which memory locations hold pointers and which don't. This knowledge is necessary in order to defragment memory.
Byte code is a term of art that describes a method of encoding instructions (for interpretation by a virtual machine) as 8-bit numbers, each pattern of 8 bits representing a different instruction.
Conservative Garbage Collection, as the term is used in this invention disclosure, describes garbage collection techniques in which the garbage collector makes conservative estimates of which memory locations hold pointers. Conservatively, the garbage collector assumes that any memory location holding a valid pointer value (a legal memory address) contains a pointer. Fully conservative garbage collectors cannot defragment memory. However, partially conservative garbage collectors (in which some pointers are accurately identified) can partially defragment memory.
CPU is an acronym that stands for Central Processor Unit. This is that part of a computer system that executes instructions (in contrast with RAM memory and disk drives).
CPU Time refers to the amount of time that the CPU works on a particular job.
Defragmenting Garbage Collection, as the term is used in this invention disclosure, describes a garbage collection technique that relocates in-use memory objects to contiguous locations so as to coalesce multiple segments of free memory into larger free segments.
Fast function is a term specific to this invention disclosure which describes a function that is considered to be not preemptible. Contrast this with slow function.
Fast Pointer is a term specific to this invention disclosure which describes pointers that are implemented using the fastest possible techniques available on a particular computer system. Fast pointers are "normal" pointers as they would be implemented by a typical compiler for the C language.
Garbage Collection is a term of art describing the automatic process of discovering regions of computer memory that were once allocated to a particular purpose but are no longer needed for that purpose and reclaiming said memory to make it available for other purposes.
Garbage Collection Flip, as the term is used in this invention disclosure, is the process of beginning another pass of the garbage collector. When garbage collection begins, the roles assigned to particular memory regions exchange; thus the use of the term "flip."
Heap is a term of art describing a region of memory within which arbitrary sized objects can be allocated and deallocated to satisfy the dynamic memory needs of application programs.
Interpreter is a term of art describing the process, generally carried out in software, of reading a stream of instructions and performing the work represented by these instructions.
Java, a trademark of Sun Microsystems, Inc., is an object-oriented programming language with syntax derived from C and C++, which provides automatic garbage collection and multi-threading support as part of the standard language definition.
JIT, as the term is used in this invention disclosure, is an acronym standing for "just in time." The term is used to describe a system for translating Java byte codes to native machine language on the fly, just-in-time for its execution. We consider any translation of byte code to machine language which is carried out by the virtual machine to be a form of JIT compilation.
Machine Language is a term of art describing the instruction encodings understood by a particular CPU. Typically, each CPU design is capable of executing different instructions, and even common instructions are encoded using different numbers.
Method is a term of art describing the unit of procedural abstraction in an object-oriented programming system. All methods are associated with particular class definitions. Rather than calling a procedure or function, the object-oriented programmer invokes the method associated with the data object on which the method is intended to operate.
Native Method, as this term is used in relation to the Java and PERC programming languages, describes a method that is implemented in C (or some other low-level language) rather than in the high-level Java or PERC language in which the majority of methods are implemented.
PERC, a trademark of NewMonics Inc., is an object-oriented programming language with similarities to Java, which has been designed to address the specific needs of developers of real-time and embedded software.
Pointer is a term of art describing a value held within computer memory or computer registers for the purpose of identifying some other location in memory. The value "points" to a memory cell.
Read Barrier is a term of art describing a special check performed each time application code fetches a value from a heap memory location. The read barrier serves to coordinate application processing with garbage collection.
Real-Time is a term of art that describes computer systems that must perform work under time constraints. Examples of real-time computer systems include telephone switching, full-motion video playback, audio CD playback, and action video games.
Real-Time Garbage Collection, as the term is used in this invention disclosure, describes a garbage collection technique that allows incremental interleaved execution of garbage collection and application code which is organized such that high-priority application code can preempt the garbage collector when necessary and garbage collection is consistently provided with adequate execution time to allow it to make guaranteed forward progress at a rate sufficient to satisfy the allocation needs of real-time application programs.
Root Pointer is a term of art describing a pointer residing outside the heap which may point to an object residing within the heap. The garbage collector considers all objects reachable through some chain of pointers originating with a root pointer to be "live."
RTVMM, as the term is used in this invention disclosure, is an acronym standing for Real-Time Virtual Machine Method. This acronym represents the invention disclosed by this document.
Signature, as the term is used in this invention disclosure, is a string representation of the type of a PERC object.
Slow function is a term specific to this invention disclosure which describes a function that is considered to be preemptible. We describe such procedures as "slow" because extra work is required by a caller function that invokes a slow function in order to prepare for the possibility of preemption.
Slow Pointer is a term specific to this invention disclosure which describes pointers that are implemented in such a way that they provide coordination with a background garbage collection task. Various implementations of slow pointers are possible. In general, fetching, storing, and indirecting through slow pointer variables is slower than performing the same operation on fast pointer variables.
String is a term of art describing a sequence of characters, typically encoded according to the ASCII standard.
Tending is a term of art describing the garbage collection process of examining a pointer to determine that the object it refers to is live and arranging for the referenced object to be subsequently scanned in order to tend all of the pointers contained therein.
Thread is a term of art describing a computer program that executes with an independent flow of execution. Java is a threaded language, meaning that multiple flows of execution may be active concurrently. All threads share access to the same global memory pool. (In other programming environments, threads are known as tasks.)
Virtual Machine is a term of art that describes a software system that is capable of interpreting the instructions encoded as numbers according to a particular agreed upon convention.
Write Barrier is a term of art describing a special check performed each time application code stores a value to a heap memory location. The write barrier serves to coordinate application processing with garbage collection.
BRIEF SUMMARY OF THE INVENTION
The invention is a real-time virtual machine method (RTVMM) for use in implementing portable real-time systems. The RTVMM provides efficient support for execution of portable byte-code representations of computer programs, including support for accurate defragmenting real-time garbage collection. Efficiency is measured both in terms of memory utilization, CPU time, and programmer productivity. Programmer productivity is enhanced through reduction of the human effort required to make the RTVMM available in multiple execution environments.
The innovations comprised in this disclosure include the following:
1. Extensions to the standard Java byte code instruction set to enable efficient run-time isolation of pointer variables from non-pointer variables. The extended byte codes are described as the PERC instruction set.
2. A mechanism to translate traditional Java byte codes into the extended PERC byte codes at run-time, as new Java byte codes are loaded into the virtual machine's execution environment.
3. An internal data structure organization that enables efficient execution of the PERC instruction set. The Java run-time stack is replaced by two stacks, one for non-pointer and the other for pointer data. Further, the data structures enable efficient interaction between native methods, Java methods represented by byte code, and Java methods translated by a JIT compiler to native machine language. Performance tradeoffs are biased to give favorable treatment to execution of JIT-translated methods.
4. A set of C macros and functions that characterize the native-method application programmer interface (API). This API abstracts the native-method programmer's interface to the internal data structures, the run-time task scheduler, and the garbage collector.
5. A method for implementing mostly stationary defragmenting real-time garbage collection in software.
6. A method for supporting arbitrary numbers of task priority levels and control over dispatching of individual tasks using an underlying operating system that provides fixed priority preemptive scheduling with a minimum of three priority levels.
7. A mechanism for translating traditional Java byte codes into the extended PERC byte codes prior to run-time, in order to reduce run-time overhead and simplify system organization.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates the organization of thread memory, with each thread comprised of a C stack, and pointer stack, and a non-pointer stack, and each stack represented by multiple stack segments
FIG. 2 illustrates the header information attached to each dynamically allocated memory object for purposes of performing garbage collection. These header fields consist of Scan-List, Indirect-Pointer, Activity-Pointer, Signature-Pointer, and optional Finalize-Link pointers.
FIG. 3 illustrates the organization of finalization lists, which are sorted into separate categories according to the activities responsible for their allocation.
FIG. 4 illustrates from-space and to-space regions, in which three live objects are being copied out of from-space into to-space. In this illustration, objects B and C have already been copied and object A is scheduled for copying. Objects D and E were presumably copied into to-space by a previous garbage collection pass and object F was allocated from to-space during a previous garbage collection pass.
FIG. 5 illustrates the appearance of the pointer and non-pointer stack activation frames immediately before calling and immediately following entry into the body of a Java method. The stacks are assumed to grow downward. In preparation for the call, arguments are pushed onto the stack. Within the called method, the frame pointer (fp) is adjusted to point at the memory immediately above the first pushed argument and the stack pointer (sp) is adjusted to make room for local variables to be stored on the stack.
FIG. 6 illustrates the internal organization of the local-variable region of the stack activation frame. This region includes application-declared locals (as declared in byte-code attributes for Java methods and as specified in the parameterization of BuildFrames( ), temporary variables (as might be required to represent the old values of the frame and instruction pointers), a run-time stack (to allow execution of push and pop operations within the method), and space for arguments to be pushed to other methods to be called from this method.
FIG. 7 illustrates the representation of string data. String x represents the string "embedded" and string y represents the string "bed".
FIG. 8 illustrates the organization of a sparse hash table for fast constant-time lookup of the byte-code representations corresponding to particular byte-code stub procedures.
FIG. 9 provides standard type definitions.
FIG. 10 provides C definitions of important global and static variables.
FIG. 11 provides C preprocessor definitions of symbolic constants used to identify standard built-in PERC classes.
FIG. 12 provides C preprocessor definitions of symbolic constants used to describe access flags in the representations of classes, methods, and fields.
FIG. 13 provides C preprocessor definitions of symbolic constants used to describe the encodings of Sun's Java byte code instruction set.
FIG. 14 provides C preprocessor definitions of symbolic constants used to describe the encodings of NewMonics' special extended byte code instruction set, for instructions that defer from Sun's encodings.
FIG. 15 provides the C declaration of the structure used internal to the PERC implementation to represent Array objects. The data[ ] component is expanded as necessary to represent the array elements.
FIG. 16 provides the C declaration of the structure used internal to the PERC implementation to represent Class objects. Each Class object represents the definition of a particular programmer-defined type.
FIG. 17 provides the C declaration of the structure used internal to the PERC implementation to represent a raw class file that has been read into memory. The class-file loader analyzes this object to create an appropriate Class representation.
FIG. 18 provides the C declaration of the structure used internal to the PERC implementation to represent the range of byte code instructions within a byte-code method to which a particular exception handler applies. The handler.sub.-- pc field is the offset of the exception handler code.
FIG. 19 provides the C declaration of the structure used internal to the PERC implementation to represent a field within a class. The constantvalue.sub.-- index field is used during loading to represent the offset within the constant pool of the value of each static final field. After the offsets of each field within the class's static data region have been determined (as represented by the Field structure's offset field), the constant is copied out of the constant pool into the corresponding data location.
FIG. 20 provides the C declaration of the structure used internal to the PERC implementation to represent a HashLock structure. Exactly one HashLock structure is allocated for each PERC object that needs either a hash value or a lock, or both.
FIG. 21 provides the C declaration of the structure used internal to the PERC implementation to represent a HashCache structure. Each HashCache structure is capable of representing three recycled hash values. HashCache structures are generally created by modifying the signature field of existing HashLock structures during garbage collection.
FIG. 22 provides the C declaration of the structure used internal to the PERC implementation to represent a Method structure.
FIG. 23 provides the C declaration of the structure used internal to the PERC implementation to represent a MethodTable structure.
FIG. 24 provides the C declaration of the structure template used internal to the PERC implementation to represent an arbitrary PERC object. The data array at the end of the structure is expanded as necessary to represent the object's fields.
FIG. 25 provides the C declaration of the structure used internal to the PERC implementation to represent a PERC stack of non-pointers.
FIG. 26 provides the C declaration of the structure used internal to the PERC implementation to represent a PERC jump buffer environment, which is stored on the C run-time stack.
FIG. 27 provides a C code fragment that demonstrates the implementation of an exception handler and try statement as they would be written in C.
FIG. 28 provides a C macro definition of the SetJmp( ) macro, which is a version of the standard C setjmp( ) function specialized for the PERC virtual machine execution environment.
FIG. 29 provides a C macro definition of the UnsetJmp( ) macro, which is used within the PERC virtual machine execution environment to replace the current exception handling context with the surrounding exception handling context.
FIG. 30 provides a C macro definition of the LongJmpo macro, which is a version of the standard C longjmp( ) function specialized for the PERC virtual machine execution environment. Note that this macro makes use of perclongjmp( ) whose implementation is not provided. perclongjmp( ) expects as parameters a representation of the machine's registers including its instruction pointer, the value of the pointer stack pointer, the value of the non-pointer stack pointer, and the return value to be returned to the point of the JIT version of setjmp( ).
FIG. 31 provides a C declaration of the structure used internal to the PERC implementation to represent a PERC stack of pointers.
FIG. 32 illustrates the signature structure used to represent the memory layout of heap-allocted objects. total.sub.-- length is the total number of words comprising the object, excluding the object's header words, but including its signature if the signature happens to be appended to the end of the data. All pointers are assumed to be word aligned within the structure. Use last.sub.-- descriptor to symbolically represent the word offset of the last word within the corresponding object that might contain a pointer. When the garbage collector scans the corresponding object in search of pointers, it looks no further than the word numbered last.sub.-- descriptor. type.sub.-- code comprises a 2-bit type tag in its most significant bits, with the remaining 30 bits representing the value of last.sub.-- descriptor. bitmap is an array of integers with each integer representing 32 words of the corresponding object, so there are a total of ceiling(last.sub.-- descriptor/32) entries in the array. (bitmap[0]&0.times.01), which represents the first word of the corresponding object, has value 1 if and only if the first word is a pointer.
FIG. 33 provides C macros that define symbolic constants pertaining to the maintenance of object headers, including the construction and use of Signature structures.
FIG. 34 provides C macros that allow manipulation and access to the fields represented by Signature structures.
FIG. 35 provides a C declaration of the structure used internal to the PERC implementation to represent a PERC String object.
FIG. 36 provides a C declaration of the structure used internal to the PERC implementation to represent a PERC Thread object.
FIG. 37 provides C macros that define symbolic constants pertaining to the state field of the Thread data structure.
FIG. 38 provides C declarations of the standard garbage collection header and accompanying macros for manipulation and access to the header information
FIG. 39 provides C macros that can be used to find the "true" address of an object and to compare two addresses for equality. The GetActualAddr macro is a helper macro, not intended for use by application code.
FIG. 40 provides C macros for conversion between integer offsets and actual derived pointer values and for obtaining the actual address of the constant-pool object. These macros are used to improve the efficiency of access to instruction, stack, and constant-pool memory.
FIG. 41 provides C macros to enable the reading and writing of memory representing the fields of heap-allocated structures.
FIG. 42 provides C macros used by the run-time dispatcher to communicate with the application thread. The dispatcher executes the SetPreemptionFlag( ) macro to request that the application preempt itself. The dispatcher checks GetEventCause( ) to verify that the application has preempted itself. The dispatcher executes the ClearPreemptionFlag( ) macro after the application has preempted itself.
FIG. 43 provides C macros used by application code to coordinate with the dispatcher. The application executes the CheckPreemption( ) macro to see if the dispatcher wants it to preempt itself. The application executes PreemptTask( ) when the task is ready to be preempted. The application executes PrepareBlockCall( ) immediately before calling a system routine which may block. It executes ResumeAfterBlockCall( ) upon return from the system routine.
FIG. 44 provides C helper macros for use by application code to coordinate with the dispatcher. TendPointerStack( ), used by SaveThreadState( ), rescans the portion of the pointer stack that is bounded below by .sub.-- gc.sub.-- ps.sub.-- low.sub.-- water and above by .sub.-- psp.
FIG. 45 provides C macros for use by C code invocations of PERC methods.
FIG. 46 provides the C implementation of the fastlnvoke( ) helper routine.
FIG. 47 provides the C implementation of the invokeStatic( ) helper routine.
FIG. 48 provides the C implementation of the invokeSpecial( ) helper routine.
FIG. 49 provides the C implementation of the invokeVirtual( ) helper routine.
FIG. 50 provides the C implementation of the invokeInterface( ) helper routine.
FIG. 51 provides the C implementation of the interfaceMethodSearch( ) helper routine.
FIG. 52 provides the C implementation of the lookupMethod( ) helper routine.
FIG. 53 provides the Java implemenation of the TaskDispatcher class .
FIG. 54 provides the C implementation of the TaskDispatcher's critical native methods and help routines.
FIG. 55 provides C macros for use in maintaining activation frames on the PERC pointer and non-pointer stacks. The StackOverflowCheck( ) macro is executed each time these stacks expand. The AdjustPSPAndZeroOutLocals( ) macro is executed to zero out the new pointers allocated on the PERC pointer stack. The AdjustLowWaterMacro( ) macro executes each time an activation frame is removed from the pointer stack. The low-water mark identifies the lower limit on the range of the pointer stack that has to be scanned when the task is preempted.
FIG. 56 provides the definition of the BuildFrames( ) C macro.
FIG. 57 provides the definition of the DestroyFrames( ) C macro.
FIG. 58 provides the definition of the PrepareJavaFrames( ) C macro.
FIG. 59 provides the definition of the PrepareNativeFrames( ) C macro.
FIG. 60 provides the definition of the ReclaimFrames( ) C macro.
FIG. 61 provides the definition of the AllocPVMLocalPointers( ) C macro.
FIG. 62 provides the definition of the AllocLocalPointers( ) C macro.
FIG. 63 provides the definitions of C macros for use in returning values from native methods and C helper functions.
FIG. 64 provides the definitions of C macros for manipulation of the PERC pointer stack.
FIG. 65 provides the definitions of C macros for manipulation of the PERC non-pointer stack.
FIG. 66 provides the definition of a C macro used within the implementation of the PERC virtual machine to support preemption of the currently executing thread.
FIG. 67 provides the definitions of C macros for saving and restoring the state of the PERC virtual machine surrounding each preemption point.
FIG. 68 provides the C implementation of the PERC virtual machine, except that cases to handle each byte code are excluded.
FIG. 69 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the IADD instruction, which adds the two integers on the top of the Java stack, placing the result on the Java stack.
FIG. 70 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the AASTORE instruction.
FIG. 71 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the FCMPL instruction.
FIG. 72 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the IFEQ instruction.
FIG. 73 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the JSR instruction.
FIG. 74 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the RET instruction.
FIG. 75 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the TABLESWITCH instruction.
FIG. 76 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the LOOKUPSWITCH instruction.
FIG. 77 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the IRETURN instruction.
FIG. 78 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the GETSTATIC.sub.-- QNP8 instruction.
FIG. 79 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the PUTFIELD.sub.-- Q instruction.
FIG. 80 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the INVOKEVIRTUAL.sub.-- FQ instruction.
FIG. 81 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the INVOKESPECIAL.sub.-- Q instruction.
FIG. 82 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the INVOKESTATIC.sub.-- Q instruction.
FIG. 83 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the INVOKEINTERFACE.sub.-- Q instruction.
FIG. 84 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the NEW.sub.-- Q instruction.
FIG. 85 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the NEWARRAY instruction. FIG. 86 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the ANEWARRAY.sub.-- Q instruction.
FIG. 87 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the ATHROW instruction.
FIG. 88 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the CHECKCAST.sub.-- Q instruction.
FIG. 89 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the INSTANCEOF.sub.-- Q instruction.
FIG. 90 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the MONITORENTER instruction.
FIG. 91 provides the C code to be inserted into the PERC virtual machine template illustrated in FIG. 68 in order to implement the MONITOREXIT instruction.
FIG. 92 provides the C implementation of the throwException routine, which is called to explicitly throw an exception to the currently executing thread.
FIG. 93 provides the C implementation of the topLevelExceptionHandler routine, which is the default exception handler in case application code does not provide an exception handler.
FIG. 94 illustrates the PERC non-pointer stack activation frame for JIT-generated code. Upon entry into the JIT function, the non-pointer stack pointer (npsp) points to the list of incoming arguments, and the return address is stored in the slot "above" the top-of-stack entry. The prologue of JIT-compiled method subtracts a JIT-computed constant from npsp to make room on the non-pointer stack for saved machine registers, local variables, and outgoing arguments.
FIG. 95 illustrates the organization of free lists, partitioned by region, but combined into a single global pool to support efficient constant-time allocation. In this figure, the three regions (indicated by the three large objects on the left side of the figure) are prioritized such that preference is given to allocating from the top region first followed by the middle region and then the bottom region. This figure illustrates only two size categories, 16 and 32. In the actual implementation, there are free lists for each size category, ranging from size 4 to size 512K.
FIG. 96 illustrates the Java implementation of the Atomic class for use on uniprocessor systems that lack the capability to analyze worst-case execution times. Application programmers can prevent threads from being preempted within certain critical regions by surrounding those regions with execution of Atomic.enter( ) and Atomic.exit( ).
FIG. 97 illustrates the native-method implementations of the Atomic.enter( ) and Atomic.exit( ) methods, respectively.
FIG. 98 illustrates C Macro definitions for the GetException( ) and ExceptionHandled( ) macros.
FIG. 99 illustrates the implementation of the stackOverflow( ) help routine, which is invoked whenever the PERC pointer or non-pointer stacks are close to overflowing.
FIG. 100 illustrates the C macro definitions of SetEventCause( ) and GetEventCause( ), which are used to communicate thread state to the task dispatcher.
DETAILED DESCRIPTION OF THE INVENTION
1.0 System Architecture
The PERC virtual machine consists primarily of an interpreter for the PERC byte-code instruction set, a task (thread) dispatcher, and a garbage collector written in C which runs as an independent real-time task. Most of the functionality of the PERC execution environment is provided by standard library and system programs that accompany the virtual machine and are executed by the virtual machine.
PERC (and Java) is an object-oriented programming language. Programs are comprised of object type declarations, known in PERC as classes. Each class definition describes the variables that are associated with each instance (object) of the corresponding class and also defines all of the operations that can be applied to instantiated objects of this type. Operations are known as methods.
Internally, PERC methods are represented using one of three different forms:
1. The PERC programmer can choose to implement certain methods in C. At run-time, these methods are represented by native machine code. Such methods are known as native methods.
2. All other PERC methods are written in PERC. At run time, certain methods written in PERC are represented as PERC byte codes.
3. The PERC-written methods that are not represented as PERC byte codes have been translated to native machine language by a JIT compiler.
2.0 Execution Modes for PERC Methods
There are three different modes of execution for PERC methods. Special effort is required to switch between these execution modes since they use the run-time stack(s) differently.
2.1 Byte-code methods
Methods represented as byte codes are interpreted by the PERC virtual machine. The interpreter, known throughout this invention disclosure as pvm() (for PERC virtual machine), uses three stacks for execution: (1) the traditional C stack, (2) an explicitly managed stack for representation of PERC pointer values, and (3) an explicitly managed stack for representation of PERC non-pointer values. The C stack holds C-declared local variables and run-time state information associated with compiler generated temporaries. The PERC pointer stack holds the pointer arguments passed as inputs to the method, pointer local variables, temporary pointers pushed during expression evaluation, and pointer values pushed as arguments to methods called by the current method. The PERC non-pointer stack holds non-pointer arguments passed as inputs to the method, non-pointer local variables, temporary non-pointer values pushed during expression evaluation, and non-pointer values pushed as arguments to be called by this method. The pointer and non-pointer stack activation frames are illustrated in FIG. 5 and FIG. 6.
2.2 JIT-compiled methods
Methods that have been translated to native machine code use only two stacks: the PERC pointer stack and the PERC non-pointer stack. The benefit of using only two rather than three stacks is that this reduces the overhead of stack maintenance associated with each method invocation. The activation frames for the two stacks are structured as illustrated in FIG. 94. However, the amount of information stored in the "temporaries" segment of the activation frame differs between JIT-compiled methods and byte-code methods.
2.3 Native methods
Native methods use the same three stacks as are used by the PERC virtual machine to execute byte-code methods.
3.0 Method Invocation
PERC, like Java, supports four distinct forms of method invocation. These are known as (1) virtual, (2) special (non-virtual), (3) static, and (4) interface. With virtual and special method invocations, there is an implicit (not seen by the Java programmer) "this" argument passed to the called method. The "this" argument refers to the object on which the called method will operate. The distinctions between these different method invocations are described in "The Java Virtual Machine Specification", by Lindholm and Yellin, 1996, Addison-Wesley.
3.1 Virtual Invocation of Methods
The PERC implementation represents every PERC object with a data structure patterned after the templates provided in FIG. 15, FIG. 16, and FIG. 24. In all of these structures, the second field is a pointer to a MethodTable data structure (see FIG. 23). The PERC execution environment maintains one MethodTable data structure for each defined object type. All instantiated objects of this type point to this shared single copy. The jit.sub.-- interfaces array field of the MethodTable structure has one entry for each virtual method supported by objects of this type. The mapping from method name and signature to index position is defined by the class loader, as described in "The Java Virtual Machine Specification", by Lindholm and Yellin, 1996, Addison-Wesley. To execute the JIT version of a PERC method using a virtual method lookup, branch to the code represented by jit.sub.-- interfaces[method.sub.-- index]. Normally, the JIT version of the byte code will only be invoked directly from within another JIT-compiled method. If a native or untranslated byte-code method desires to invoke another method using virtual method lookup, the search for the target method generally proceeds differently. First, we find the target object's MethodTable data structure (as above) and then follow the methods pointer to obtain an array of pointers to Method objects. Within the Method object, we consult the access.sub.-- flags field to determine if the target method is represented by native code (ACC.sub.-- NATIVE) or JIT translation of byte code (ACC.sub.-- JIT). If neither of these flags is set, the method is assumed to be implemented by byte codes. See FIG. 49, FIG. 45, and FIG. 46.
3.2 Special Invocation of Methods
When the method to be invoked by a particular operation is known at compile time, the Java compiler treats this as an invokeSpecial instruction. In these cases, there is no need to consult the method table at run time. When performing special method invocation from within a JIT-translated method, the address of the called method (or at least a stub for the called method) is hard-coded into the caller's machine code.
If a native or untranslated byte-code method desires to perform the equivalent of an invokeSpecial operation, we examine the Method object that represents the target procedure and consult its access.sub.-- flags field to determine if the method is represented by native code (ACC.sub.-- NATIVE) or JIT translation of byte code (ACC.sub.-- JIT). If neither of these flags is set, the method is assumed to be represented as byte code. See FIG. 48, FIG. 45, and FIG. 46.
3.3 Static Invocation of Methods
When the method to be invoked is declared as static within the corresponding object (meaning that the method operates on class information rather than manipulating variables associated with a particular instance of the corresponding class), the Java compiler treats this as an invokeStatic method. Execution of static methods is identical to execution of special methods except that there is no implicit pointer to "this" passed as an argument to the called method. See FIG. 47, FIG. 45, and FIG. 46.
3.4 Interface Invocation of Methods
When a method is invoked through an interface declaration, the called method's name and signature is stored as part of the calling method's code representation. The compiler ensures that the object to be operated on has a method of the specified name and signature. However, it is not possible to determine prior to run time the index position within the method table that holds the target method. Thus it is necessary to examine the target object's mtable field, which points to the corresponding MethodTable structure. We follow the MethodTable's methods pointer to find an array of pointers to Method structures. And we search this array for a method that matches the desired name and signature. Once found, we invoke this method. We examine the Method object that represents the target procedure and consult its access.sub.-- flags field to determine if the method is represented by native code (ACC.sub.-- NATIVE) or JIT translation of byte code (ACC.sub.-- JIT). If neither of these flags is set, the method is assumed to be represented as byte code. See FIG. 50, FIG. 51, FIG. 45, and FIG. 46.
4.0 Switching Between Execution Modes
Care must be taken when switching between execution modes. Since mode changes do not occur within methods, all mode changes are associated with calling or returning from a PERC method.
TABLE 1
______________________________________
Mode Changes Between Different Method Implementations
Called Function
Calling Function
Byte Code JIT Code Native Method
______________________________________
Byte Code invokeStatic()
invokeStatic()
invokeStatic()
(pvm()) invokeSpecial()
invokeSpecial()
invokeSpecial()
invokeVirtual()
invokeVirtual()
invokeVirtual()
invokeInterface
invokeInterface
invokeInterface
() () ()
JIT Code Byte code stub
Direct call Native method
stub
Native Method
invokeStatic()
invokeStatic()
invokeStatic()
invokeSpecial()
invokeSpecial()
invokeSpecial()
invokeVirtual()
invokeVirtual()
invokeVirtual()
invokeInterface
invokeInterface
invokeInterface
() () ()
______________________________________
Note that native methods and pvm(), which interprets byte-code methods, use the same stack organization. Thus, calling another method from a native method is the same as calling the method from within the pvm() interpreter. In both cases, the caller invokes the callee by passing appropriate parameters to one of several available invocation routines, all of which are written primarily in C. These invocation routines consult internal fields within the Method structure that describes the callee to determine whether the callee is implemented as byte codes, the JIT translation of byte codes, or a native method (See FIG. 46). The invocation routine adjusts the stack and other state information as necessary in order to transfer control to the called method. When the called method returns, the invocation routine restores the stack and other state information to once again support the execution mode of the calling method. To call a byte-code method, the invocation routine saves the offset of the old frame and stack pointers in local C variables, sets up the callee's activation frames (See FIG. 5), and calls pvm(), passing a pointer to the called method's Method structure as the only argument. To call a native method, the invocation routine saves the offsets of the old stack and frame pointers, sets up the native method's activation frames (See FIG. 5), and calls (*Method.native)(). To call a JIT-translated method, the invocation routine sets up the callee's activation frames (See FIG. 5), pushes the current C frame pointer onto the C stack and then saves the current value of the C stack pointer in the c.sub.-- sp field of the currently executing thread's Thread data structure, copies the current values of the .sub.-- psp and .sub.-- npsp variables into machine registers dedicated to these purposes (effectively making the PERC stacks become the run-time execution stacks), and branches to (*Method.jit.sub.-- interface)(), leaving the return address in the stack slot above the top-of-stack entry on the non-pointer stack. See FIG. 94 for an illustration of the non-pointer stack activation frame as it is organized during execution of JIT code.
If the caller is a JIT-translated method, the callee is invoked in all cases by simply branching to the equivalent of (*Method.jit.sub.-- interface)(). A small procedure stub is generated to represent each byte-code and native method in the system. Stub procedures, described below, perform all of the mode switching work that is required in switching execution modes. Note that the JIT-code translation of a static or special (non-virtual) invocation in-lines the address of the callee's code so that the corresponding Method structure does not need to be consulted at run time.
4.1 Invocation Routines
To invoke another method from within pvm(), we call one of invokeStatic(), invokeSpecial(), invokeVirtual(), or invokeInterface(), as described in Table 1.
4.1.1 Invocation of Virtual Methods
From within the implementation of the pvmo and within native methods, the standard protocol for invoking other methods depends on the type of the call. A virtual method invocation vectors to the corresponding code by way of the target object's method table. The object to which the method corresponds is passed implicitly on the run-time stack. To invoke a virtual method, first push a pointer to the target object onto the pointer stack and then push all of the method's arguments onto the pointer and non-pointer stacks, depending on their types. Then call invokeVirtual(), passing as arguments pointers to the String objects that represent the class name and the target method's name and signature (See FIG. 49):
void invokeVirtual(String *class.sub.-- name, String *method.sub.-- name.sub.-- and.sub.-- sig); Note that invokeVirtual() must do a string search within the class representation to find the selected method. This is potentially a costly operation and we would prefer to avoid this cost when possible. When byte code is first loaded into our system, we perform this lookup and save the result, represented by a pointer to a Method structure, within the constant pool. Implementers of native methods may design similar optimizations. There are two mechanisms available to implementers of native methods for the purposes of looking up Method objects: findMethod() and getMethodPtr(). Both of these functions return a pointer to the corresponding Method object. With findMethod(), the desired method is described by a pointer to the known Class object and a String pointer to the method's name and signature. With getMethodPtr(), the desired method is described by String representations of the class name and of the method's name and signature. Prototypes for both functions are provided below:
Method *findMethod(Class *class.sub.-- name, String *method.sub.-- name.sub.-- and.sub.-- sig);
Method *getMethodPtr(String *class.sub.-- name, String *method.sub.-- name.sub.-- and.sub.-- sig);
Both functions return null if the method was not found.
Within the Method structure, information is available which characterizes the number of pointer arguments of this particular method and the offset of this method within the object's method table (see FIG. 22). To invoke a virtual function without incurring the overhead of a string method lookup, use the FastInvokeVirtualo macro, prototyped below (See FIG. 45):
void FastInvokeVirtual(int num.sub.-- p.sub.-- args, int offset);
4.1.2 Invocation of Special Methods
Non-virtual method calls resemble virtual method invocations except that the code to be implemented is determined by the declaration (at compile time) rather than by the current instantiation (at run time). There is no need to consult a method table when implementing non-virtual method calls. To invoke a nonvirtual method, call invokeSpecial(), passing as arguments two String objects representing the name of the class and the name and signature of the method within the class, as prototyped below (See FIG. 48):
void invokeSpecial(String *class.sub.-- name, String *method.sub.-- name.sub.-- and.sub.-- sig);
To optimize the performance of nonvirtual method invocations, first lookup the Method object and remember its location. Then invoke the nonvirtual method by executing the FastInvokeSpecial() macro, prototyped below (See FIG. 45):
void FastInvokeSpecial(Method *);
4.1.3 Invocation of Interfaces
At the API level, invoking an interface is similar to invoking a virtual or non-virtual method. First push a pointer to the target object onto the pointer stack and then push all of the method's arguments onto the pointer and non-pointer stacks, depending on their types. Then call invokeinterface(), passing as arguments String objects representing the name of the class and the name and signature of the method within the class, as prototyped below (See FIG. 50):
void invokeInterface(String *class.sub.-- name, String *method.sub.-- name.sub.-- and.sub.-- sig);
To improve the efficiency with which interface methods can be invoked, it is useful to make an educated guess as to where the matching interface might be found within the target object's method table. In most cases, the best guess is the method table slot at which the match was found the previous time the interface method was invoked. By combining the results of a previous findMethod() invocation with recent execution history, programmers can call interface methods using the FastInvokeInterface() macro, prototyped below (See FIG. 45):
void FastInvokeInterface(int num.sub.-- ptr.sub.-- args, int offset.sub.-- guess, Method *template);
Note in the above that the purpose of the template argument is to allow FastInvokeInterface to determine the name and signature of the method that it must search for in the object found num.sub.-- ptr.sub.-- args slots from the current top-of-stack pointer on the PERC pointer stack.
4.1.4 Invocation of Static Methods
A static method is one that makes use only of information that is associated with the corresponding class (rather than instances of the class). When a static method is invoked, there is no "target object" pushed onto the stack. To call a static method, push all of the method's arguments onto the pointer and non-pointer stacks, depending on their types. Then call invokeStatic(), passing as arguments String objects representing the name of the class and the name and signature of the method within the class, as prototyped below (See FIG. 47):
void invokeStatic(String *class.sub.-- name, String *method.sub.-- name.sub.-- and.sub.-- sig);
To improve the efficiency with which static methods can be invoked, lookup the corresponding Method object beforehand and remember its location. Then invoke the static method using the FastInvokeStatic() macro, prototyped below (See FIG. 45):
FastInvokeStatic(Method *);
4.2 Byte-Code Stubs
When JIT-translated code invokes a method that is implemented by Java byte code, it is necesary to switch the execution protocol prior to invoking pvm(). Rather than requiring JIT-generated code to check whether this protocol switch is necessary prior to each method invocation, we provide each byte-code method with a stub procedure that honors the JIT execution protocol. This stub procedure switches from JIT to C protocols and then invokes pvm() with appropriate arguments. In more detail, the stub procedure performs the following:
1. Sets the Thread state to RUNNING rather than JIT.sub.-- EXECUTING. This signifies to the run-time dispatcher that this thread cannot be preempted at arbitrary times, but must wait either for an explicit preemption point or for the thread to return to JIT mode.
2. Copies the register-held psp and npsp registers into global memory locations .sub.-- psp and .sub.-- npsp. Then assigns sp and fp (the machine's stack and frame pointer registers) to reflect the current C-stack context, as represented by .sub.-- current.sub.-- thread.fwdarw.c.sub.-- sp.
3. Copies the return address off the non-pointer stack (See FIG. 94) and saves its value in a slot within the C stack frame.
4. Calculates and assigns values to .sub.-- pfp (pointer stack frame pointer) and .sub.-- npfp (non-pointer stack frame pointer), based on the current values of the corresponding stack pointers and the number of arguments of each type. The stack activation frames are arranged as illustrated in FIG. 5. Additionally, we adjust the pointer and non-pointer stack pointers to make room for the local variables that are required to execute the method, as represented by the max.sub.-- ptr.sub.-- locals and max.sub.-- non.sub.-- ptr locals fields of the corresponding Method structure.
5. If the method to be invoked is synchronized, we enter the monitor now, waiting for other threads to exit first if necessary.
6. For coordination with the garbage collector, we keep track of how high the pointer stack has grown during the current execution time slice. Since the stack grows downward, the high-water mark is represented by the minimum value of .sub.-- psp.
7. Calls pvm(), passing as a C argument a pointer to the Method object that describes the segment of code to be executed.
8. Upon return from pvm(), the stub procedure restores the C stack to its original height and copies the machine's sp register back into the .sub.-- current.sub.-- thread.fwdarw.c.sub.-- sp variable.
9. If the invoked method was synchronized, release the monitor now. Note that the pvm() itself takes responsibility for exiting the monitor if the code is aborted by throwing of an exception.
10. The stub procedure then removes all local variables from both PERC stacks, leaving a single pushed quantity on one of the stacks to represent the method's return value. Then it restores the psp, pfp, npsp, and npfp registers if appropriate. (This is our implementation of ReclaimFrames()).
11. For coordination with the garbage collector, we keep track of how low the pointer stack has shrunk during the current execution time slice. Since the stack grows downward, the low-water mark is represented by the maximum value of .sub.-- pfp.
12. Sets the Thread state to JIT.sub.-- EXECUTING.
13. Returns to the caller's address that was saved in step 3.
4.3 Native-Method Stubs.
The stub for a native method is identical to the stub for a byte-code method except that the native method is invoked directly rather than invoking pvm() and the stub does not allocate any space on the PERC stacks for the called method's local variables (The native method reserves its own local variable space as needed). Since the target native method's address is known at the time the stub is generated, the native method is invoked directly, without requiring interaction with lookupMethod().
5.0 Disciplines to Support Accurate Real-Time Garbage Collection
To support real-time performance, garbage collection runs asynchronously, meaning that the garbage collection thread interleaves with application code in arbitrary order. To support accurate garbage collection, it is necessary for the garbage collector to always be able to distinguish a thread's pointer variables (including stack-allocated variables and variables held in machine registers) from the thread's non-pointer variables.
To require each thread to maintain all pointers in variables that are at all times easily identifiable by the garbage collector imposes too great an overhead on overall performance. Thus, the PERC virtual machine described in this invention disclosure implements the following compromises:
1. Threads are not allowed to be preempted at arbitrary times. Instead, preemption of a thread is only allowed if the thread is in a state identified as a preemption point.
2. Between preemption points, the thread is allowed to hold pointers in variables that may not be visible to the garbage collector. In this disclosure, we characterize such variables as "fast pointers." Fast pointers are typically declared in C as local variables, and may be represented either by machine registers or slots on the C stack.
3. Pointer variables that are visible to the garbage collector are known throughout this disclosure as "slow pointers". Slow pointers are typically represented by locations on the PERC pointer stack and by certain C-declared global variables identified as "root pointers".
4. Immediately following each preemption, the thread must consider all of its fast pointers to be invalid. In preparation for each preemption, the thread must copy the values of essential fast-pointer variables into slow pointers. Following each preemption, essential fast pointers are restored from the values previously stored in slow pointer variables. Note that, while the thread was preempted, a drefragmenting garbage collector might have relocated particular objects, requiring certain pointer values to be modified to reflect the corresponding objects' new locations.
5. Each C function in the virtual machine implementation is identified as either preemptible or non-preemptible. Before calling a preemptible function, the caller must copy all of its essential fast pointers into slow pointers. When the called function returns, the caller must restore the values of these fast-pointer variables by copying from the slow-pointer variables in which their values were previously stored. Throughout this disclosure, we refer to preemptible functions as "slow functions" and to non-preemptible functions as "fast functions."
To reduce programming effort and to minimize system dependencies, we have defined a number of standard macros for use in adhering to these protocols. These macros and standard libraries are described in the remainder of this section.
Restrictions. In order to coordinate application processing with garbage collection, it is necessary for authors of native methods and other C libraries to avoid certain "legal" C practices:
1. Do not coerce pointers to integers or integers to pointers.
2. Do not perform any pointer arithmetic unless specifically authorized to do so (e.g. special techniques have been enabled to support efficient instruction and stack pointer operations).
3. Do not store tag information (e.g. low-order bits of a word) within memory locations that are identified as pointers to the garbage collector.
4. Do not store pointers to the C static region or to arbitrary derived addresses in locations identified as garbage-collected pointers, except that pointers to objects residing in the ROMized region are allowed. Note: A derived address is a location contained within an object. The garbage collector assumes all pointers refer to the base or beginning address of the referenced object.
5. Do not directly access the fields contained within heap objects. Instead, use the GetHeapPtr(), GetHeapNonPtr(), SetHeapPtr(), and SetHeapNonPtr() macros.
6. When declaring fields and variables that point to the C static region, identify such fields as non-pointers insofar as garbage collection is concerned.
7. Pointers to garbage-collected objects cannot be stored in the C static region unless such pointers have been registered as root pointers.
5.1 Access to Heap Objects
It is necessary to provide parameterized access to heap memory so as to facilitate the implementation of read and write barriers. The following macros serve to copy variables between different kinds of representations. See FIG. 41 for implementations of these macros.
GetHeapPtr(base, field.sub.-- expr, base.sub.-- type, field.sub.-- type)
Given that (base) (field.sub.-- expr) is an expression representing a pointer residing within a heap-allocated object, that base.sub.-- type represents the type of base, and that field.sub.-- type represents the type of (base) (field.sub.-- expr), return the fast pointer that represents this heap pointer's value. In the process, we may have to "tend" the pointer's value. Optionally, we may overwrite in place the value of (base) (field.sub.-- expr), so this expression should be a C 1-value. Sample usage:
exception=GetHeapPtr(.sub.-- current.sub.-- thread, .fwdarw.current.sub.-- exception, Thread *, Object *);
SetHeapPtr(base, field.sub.-- expr, base.sub.-- type, field.sub.-- type, field.sub.-- value)
Given that (base) (field.sub.-- expr) is an expression representing a pointer residing within a heap-allocated object, that base.sub.-- type represents the type of base, that field.sub.-- type represents the type of (base) (field.sub.-- expr), and that field.sub.-- value is also of type field.sub.-- type, assign field.sub.-- value to (base) (field.sub.-- expr). In the process, we may have to "tend" field.sub.-- value. Note that (base) (field.sub.-- expr) must be a C 1-value. Sample usage: SetHeapPtr(.sub.-- current.sub.-- thread, .fwdarw.current.sub.-- exception, Thread *, Object *, new.sub.-- exception);
GetHeapNonPtr(base, field.sub.-- expr, base.sub.-- type, field.sub.-- type)
Given that (base) (field.sub.-- expr) is an expression representing a non-pointer residing within a heap-allocated object, that base.sub.-- type represents the type of base, and that field.sub.-- type represents the type of (base) (field.sub.-- expr), return the non-pointer value that represents this heap location's value. Sample usage:
pc=GetHeapPtr(.sub.-- current.sub.-- thread, .fwdarw.pc, Thread *, unsigned short);
SetHeapNonPtr(base, field.sub.-- expr, base.sub.-- type, field.sub.-- type, field.sub.-- value)
Given that (base) (field.sub.-- expr) is an expression representing a non-pointer residing within a heap-allocated object, that base.sub.-- type represents the type of base, that field.sub.-- type represents the type of (base) (field.sub.-- expr), and that field.sub.-- value is also of type field.sub.-- type, assign field.sub.-- value to (base) (field.sub.-- expr). Note that (base) (field.sub.-- expr) must be a C 1-value. Sample usage:
SetHeapPtr(.sub.-- current.sub.-- thread, .fwdarw.pc, Thread *, unsigned short, 28);
Occasionally, application programmers desire to access the elements of an array of a particular type as if certain slots contained elements of a different type. Suppose, for example, that the prograrnmers want to treat the 2nd and 3rd entries of an integer array as a 64-bit integer. This can be achieved using the GetHeapInArrayNonPtr() macro, as demonstrated below:
long.sub.-- integer=GetHeapInArrayNonPtr(base, [1], int *, longlong);
In this code, base is assumed to point to the beginning of a heap-allocated object which is declared to be an array of integers (the type of base should be specified by the third argument of GetHeapInArrayNonPtr()). The second argument is combined with the first to obtain the object whose address represents the location at which the longlong integer will be fetched. There are four different macros provided for this sort of access to array data:
field.sub.-- type GetHeapInArrayPtr(base, field.sub.-- expr, base.sub.-- type, field.sub.-- type);
field.sub.-- type GetHeapInArrayNonPtr(base, field.sub.-- expr, base.sub.-- type, field.sub.-- type);
void SetHeapInArrayPtr(base, field.sub.-- expr, base.sub.-- type, field.sub.-- type, field.sub.-- value);
void SetHeapInArrayNonPtr(base, field.sub.-- expr, base.sub.-- type, field.sub.-- type, field.sub.-- value);
The following help macro is intended to facilitate the use of garbage collection macros in application code. See FIG. 39 for the implementation of this macro. int SameObjects(void *p1, void *p2)
With certain garbage collection techniques, it is possible that two fast pointer objects refer to the same object even though their pointer values are different. This might occur, for example, if an object is being copied in order to compact live memory and one pointer refers to the original location of the object and the other pointer refers to the new copy of the object. Programmers should use the SameObject() macro to compare fast pointers for equality. This macro returns non-zero if and only if its two pointer arguments refer to the same object.
5.2 Manipulation of String Data
The following macros are used to access and manipulate string data and slice objects. char *GetStringData(String *s)
Given that s points to a String object, returns the base address of the string data that corresponds to this object. The base address is the start of the buffer that holds this string's data.
int GetStringOffset(String *s)
Given that s points to a String object, returns the offset at which the string's data begins within the string buffer represented by GetStringData(s).
int GetStringLen(String *s)
Given that s points to a String object, return the length of the corresponding string.
char GetStringChar(String *s, int i)
Given that s points to a String object and that i is within the range of the corresponding string data, return the character at offset i from the beginning of the string. Offset 0 represents the first character of the string. void SetStringChar(String *s, int i, char c)
Given that s points to a String object and that i is within the range of the corresponding string data, set the character at offset i from the beginning of the string to the value of c.
Additionally, we provide the following C functions, which can be assumed to be preemptible unless fast appears in their names or they are specifically being described as not preemptible, for manipulation of string data. Programmers who invoke the fast functions below should take care to avoid passing arguments that represent "long" strings, since doing so would increase preemption latency.
int fastCompareTo(String *string1, String *string2)
Compares the data of string1 to that of string2, returning 0 if the strings are equal, -1 if string1 lexicographically precedes string2, and 1 if string1 lexicographically follows string2.
String *fastSubstring(String *string, int offset)
Returns a String object representing the substring of string that starts at position 0 and includes all characters to the end of string. substring(s, 0) returns a copy of string s.
String *concat(String *string1, String *string2)
Given that string1 and string2 represent String objects, create and return a new String object that represents their catenation.
String *fastReplace(String *string, char old, char new)
Given that string represents a String object, replace all occurrences of character old with character new within the corresponding string data.
char *fastToCString(String, *jstring)
Given that jstring represents a String object, returns a null-terminated array of characters representing the data of jstring. The null-terminated array is heap allocated.
String *fastStaticToJavaString(char *cstring)
Given that cstring represents a statically allocated null-terminated array of characters, returns a String object that represents the same data (without the null terminator).
void setStringDataFromStaticBuf(String *string, unsigned char *buf, int length, int offset)
Given that buf represents a statically allocated array of length characters, this fuiction copies length bytes from buf to string, starting at position offset within string. The first offset bytes of string are left untouched. This function is not preemptible.
void getStringDatalntoStaticBuf(String *string, char *buf)
Given that buf represents a statically allocated array of at least as many characters as are required to represents string, this function copies all of string's characters to buf. This function is not preemptible.
5.3 Manipulation of the Pointer Stack
Native methods and other C functions run fastest if they avoid frequent copying of values between local variables (stored on the PERC pointer stacks) and C-declared fast pointers. But pointers stored in C-declared variables are not necessarily preserved across preemption of the thread. Thus, it is necessary for the application code to copy from C-declared variables to macro-declared variables before each preemption. The following macros are used to manipulate the pointer stack.
void PushPtr(fptr)
Push the fast pointer fptr onto the pointer stack.
void *PopPtr()
Pop the fast pointer off of the pointer stack.
void *PeekPtr(offset)
Return the fast pointer that is currently offset slots away from the top of the stack.
PeekPtr(0) is the top pointer-stack element.
void PokePtr(offset, fptr)
Insert fptr into the stack slot found offset slots away from the top of the stack. (Not yet implemented.)
void *GetLocalPtr(offset)
Return as a fast pointer the local pointer at the specified offset. The first pointer argument is at offset 0. The second pointer argument is at offset 1, and so on.
void SetLocalPtr(offset, fastptr)
Set the local pointer at the specified offset to the value of fastptr. Offsets are specified as described in the GetLocalFastPtr() macro.
void ShrinkPS(offset)
Adjust the pointer stack pointer (psp) by offset entries. If offset is positive, space representing offset pointers is removed from the stack. ShrinkPS should not be used with a negative offset as this might create a situation in which pointers have garbage values.
5.4 Manipulation of the Non-Pointer Stack
The non-pointer stack holds integers, 8-byte long integers, floating point values, and 8-byte double-precision floating point values. The following macros are suggested for manipulation of the non-pointer stack.
void PushInt(val)
Push integer val onto the non-pointer stack.
void PushFloat(val)
Push floating point value val onto the non-pointer stack.
void PushLong(val)
Push 8-byte long value val onto the non-pointer stack.
void PushDouble(val)
Push 8-byte double precision value val onto the non-pointer stack.
int PopInt()
Pop a single integer from the top of non-pointer stack.
float PopFloat()
Pop a single floating point value from the top of the non-pointer stack.
longlong PopLong()
Pop a single 8-byte long value from the top of the non-pointer stack.
double PopDouble()
Pop a single 8-byte double precision value from the top of the non-pointer stack.
int PeekInt(off)
Given that off words have been pushed onto the non-pointer stack on top of integer item n, return n.
float PeekFloat(off)
Given that off words have been pushed onto the non-pointer stack on top of floating point value x, return x.
longlong PeekLong(off)
Given that off words have been pushed onto the non-pointer stack on top of 8-byte long value m, return m.
double PeekDouble(off)
Given that off words have been pushed onto the non-pointer stack on top of 8-byte double-precision value y, return y.
void PokeInt(off, va1)
Given that off words have been pushed onto the non-pointer stack on top of the integer slot representing n, overwrite this slot with val.
void PokeFloat(off, va1)
Given that off words have been pushed onto the non-pointer stack on top of the floating point slot representing x, overwrite this slot with val.
void PokeLong(off, va1)
Given that off words have been pushed onto the non-pointer stack on top of the 8-byte long integer slot representing m, overwrite this slot with val.
void PokeDouble(off, va1)
Given that off words have been pushed onto the non-pointer stack on top of the 8-byte double precision slot representing y, overwrite this slot with val.
int GetLocalInt(off)
Given that off words precede the integer variable j within the local non-pointer stack activation frame, return the value of j.
float GetLocalFloat(off)
Given that off words precede the floating point variable f within the local non-pointer stack activation frame, return the value of f.
longlong GetLocalLong(off)
Given that off words precede the 8-byte long integer variable 1 within the local non-pointer pointer stack activation frame, return the value of 1.
double GetLocalDouble(off)
Given that off words precede the double precision floating point variable x within the local non-pointer stack activation frame, return the value of x.
void SetLocalInt(off, val)
Given that off words precede the integer variable j within the local non-pointer stack activation frame, set the value of j to val.
void SetLocalFloat(off, val)
Given that off words precede the floating point variable f within the local non-pointer stack activation frame, set the value of f to val.
void SetLocalLong(off, val)
Given that off words precede the 8-byte long integer variable 1 within the local non-pointer stack activation frame, set the value of 1 to val.
void SetLocalDouble(off, val)
Given that off words precede the double precision floating point variable x within the local non-pointer stack activation frame, set the value of x to val.
void ShrinkNPS(offset)
Adjust the non-pointer stack pointer (npsp) by offset entries. If offset is positive, space representing offset pointers is removed from the stack. If offset is negative, the specified number of stack slots are added to the stack.
5.5 Optimizations to Support Performance-Critical Data Structures
Strict partitioning between fast and slow pointers, and requiring all heap memory access to be directed by way of heap access macros imposes a high overhead. Certain data structures are accessed so frequently that the PERC implementation treats them as special cases in order to improve system performance. In particular, the following exceptions are supported:
1. Note that the PERC stacks dedicated to representation of pointer and non-pointer data respectively are heap allocated. According to the protocols described above, every access to PERC stack data should be directed by way of heap access macros. Since stack operations are so frequent, we allow direct access to stack data using traditional C pointer indirection. This depends on the following:
a. The stack pointers are represented by C global variables declared as pointers. Access to stack data uses C pointer indirection, without enforcement of special read or write barriers. (See FIG. 64 and FIG. 65)
b. Each time the task is preempted, the global variables representing the currently executing thread's stack pointers are saved by the run-time dispatcher in the thread's structure representation (See FIG. 53 and FIG. 44). Note the use of the GetSPOffset() macro (See FIG. 40).
c. Each time a task is scheduled for execution, the dispatcher sets the global stack pointer variables to represent the newly dispatched thread's stack pointers (See FIG. 53 and FIG. 44). Note the use of the GetSP() macro (See FIG. 40).
d. During execution of a time slice, the thread's pointer stack is assumed to hold fast pointers. However, when the thread is preempted, the garbage collector needs to see the stack object's contents as slow pointers. When the thread is preempted, the dispatcher scans that portion of the stack that has been modified during the current time slice in order to convert all fast pointers to slow pointers (See FIG. 53 and FIG. 44). We maintain a low-water mark representing a bound on the range of stack memory that has been impacted by execution of the task during its current time slice to reduce the need for redundant stack scanning.
2. When the pvm() (PERC Virtual Machine byte code interpreter) is executing byte-code methods, the method's byte code is represented by a string of bytes. The byte-code instructions are stored in heap memory, suggesting that every instruction fetch needs to incur the overhead of a heap-access macro. To improve the performance of instruction fetching, we allow instruction fetching to bypass the standard heap access macro. Doing so depends on the following:
a. The instruction pointer is represented by a fast pointer declared within the implementation of pvm(). Upon entry into pvm(), this variable is initialized using the GetPC() macro, which expects as arguments a pointer to the ByteString object that represents the method's code and the instruction offset within this method's code (See FIG. 40).
b. Whenever pvm() is to be preempted, or whenever it calls another function that might be preempted, pvm() computes the current instruction offset relative to the beginning of the ByteString object that represents the currently executing method's byte code. We use the GetPCOffset() macro (See FIG. 40).
c. After being preempted (or after returning from a function that may have been preempted), the instruction pointer is recomputed by using GetPC().
3. During interpretation of byte-code methods, the constant pool is frequently accessed. Rather than incurring the overhead of a standard heap access macro, we obtain a trustworthy C pointer to the constant pool data structure and refer directly to its contents. For this purpose, we use the GetCP() macro (See FIG. 40). C subscripting expressions based on the value returne |
