Method and apparatus for isolating selected heap objects using a faulting address trap

• US 7,313,566 B1
• Filed: 12/23/2004
• Issued: 12/25/2007
• Est. Priority Date: 12/23/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Printezis, Antonios, Garthwaite, Alexander T.
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US11/021,260
• Time in Patent Office: 1,097 Days
• Field of Search: 707/1, 707/2, 707/206, 707/101, 712/244, 711/112, 717/148
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 12/145 the protection being virtual, e.g. for virtual blocks or segments before a translation mechanism
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

All references to an object subset to which an atomic operation is to be applied are deliberately transformed so that an attempt by an application thread to dereference such a transformed reference will raise a faulting address trap. When the faulting address trap is raised, the faulting thread will enter a trap handler, which suspends the faulting thread. The atomic operation can then be applied and the faulting thread restarted.

Claims

1. A method for processing heap objects with an atomic operation using a faulting address trap, the method comprising:

selecting, by a first thread of a plurality of concurrently executing threads, a subset of heap objects;

transforming, by the first thread, each reference to each heap object of the subset of heap objects in such a manner that the faulting address trap will be raised if an attempt is made by any other thread of the plurality of concurrently executing threads to access the heap object with the transformed reference;

processing, by the first thread, each heap object of the subset of heap objects with the atomic operation, wherein an indication that the atomic operation has been performed on the heap object is stored; and

if the faulting address trap is raised during the processing of the subset of heap objects by the first thread because a second thread of the plurality of concurrently executing threads has attempted to access a heap object of the subset of heap objects, suspending the second thread until the atomic operation is performed on the heap object the second thread attempted to access.

2. The method of claim 1 wherein the faulting address trap is a misaligned address trap.

3. The method of claim 2 wherein transforming, by the first thread, each reference further comprises setting at least one bit of each reference to one.

4. The method of claim 2 wherein transforming, by the first thread, each reference further comprises setting a least significant bit of each reference to one.

5. The method of claim 1 wherein the faulting address trap is a memory protection trap.

6. The method of claim 5 wherein transforming, by the first thread, each reference further comprises changing each reference to point to one of an unmapped area of memory and a protected area of memory.

7. The method of claim 1 wherein the second thread is suspended until the atomic operation is performed on all of the subset of heap objects.

8. The method of claim 1 wherein suspending the second thread further comprises placing a reference to the heap object the second thread attempted to access in a queue, wherein the heap object the second thread attempted to access is processed with the atomic operation before heap objects that are not in the queue are processed with the atomic operation.

9. The method of claim 1 wherein suspending the second thread further comprises allowing the second thread to access the heap object the second thread attempted to access after the atomic operation is performed on that heap object.

10. The method of claim 1 wherein suspending the second thread further comprises determining, prior to suspending the second thread, whether the atomic operation has already been performed on the heap object the second thread attempted to access.

11. The method of claim 10 wherein suspending the second thread further comprises allowing the second thread to access the heap object the second thread attempted to access if the atomic operation has already been performed on the heap object the second thread attempted to access.

12. The method of claim 1 wherein processing, by the first thread, each heap object further comprises setting a bit in the heap object to indicate that the atomic operation has been performed on the heap object.

13. The method of claim 1 wherein processing, by the first thread, each heap object further comprises storing the indication that the atomic operation has been performed on the heap object in a table.

14. The method of claim 1 wherein processing, by the first thread, each heap object further comprises:

processing the subset of heap objects in address order; and

storing an address of a last heap object processed as the indication that the atomic operation has been performed.

15. The method of claim 1 wherein transforming, by a first thread, each reference further comprises:

stopping all other threads of the plurality of concurrently executing threads;

transforming each reference to each heap object of the subset of heap objects; and

restarting all other threads of the plurality of concurrently executing threads.

16. The method of claim 1 wherein transforming, by a first thread, each reference further comprises:

transforming references to some heap objects of the selected subset of heap objects without stopping all other concurrently executing threads;

stopping all other threads of the plurality of concurrently executing threads;

transforming references to a remainder of the subset of heap objects whose references are not already transformed; and

restarting all other threads of the plurality of concurrently executing threads.

17. The method of claim 1 further comprising:

untransforming, by the first thread, each reference to each of the subset of heap objects after all of the subset of heap objects have been processed with the atomic operation.

18. The method of claim 17 wherein untransforming, by the first thread further comprises:

stopping all other threads of the plurality of concurrently executing threads;

untransforming each reference to each heap object of the subset of heap objects; and

restarting all other threads of the plurality of concurrently executing threads.

19. The method of claim 17 wherein untransforming, by the first thread further comprises:

untransforming references to some heap objects of the subset of heap objects without stopping all other concurrently executing threads;

stopping all other threads of the plurality of concurrently executing threads;

untransforming references to a remainder of the subset of heap objects whose references are not already untransformed; and

restarting all other threads of the plurality of concurrently executing threads.

20. Apparatus for processing selected heap objects with an atomic operation using a faulting address trap, the apparatus comprising:

a memory storing a plurality of heap objects and a faulting address trap handler for the faulting address trap; and

a processor that executes a plurality, of concurrently executing threads, wherein the plurality of concurrently executing threads can reference the plurality of heap objects,

wherein a first thread of the plurality of concurrently executing threads;

selects a subset of the plurality of heap objects;

transforms each reference to each heap object of the subset of heap objects in such a manner that the faulting address trap will be raised if an attempt is made by any other thread of the plurality of concurrently executing threads to access the heap object with the transformed reference; and

processes each heap object of the subset of heap objects with the atomic operation, wherein an indication that the atomic operation has been performed on the heap object is stored; and

wherein the faulting address trap handler;

suspends the second thread if the faulting address trap is raised during the processing of the subset of heap objects by the first thread because a second thread of the plurality of concurrently executing threads has attempted to access a heap object of the subset of heap objects, wherein the second thread is suspended until the atomic operation has been is performed on the heap object the second thread attempted to access.

21. The apparatus of claim 20 wherein the faulting address trap is a misaligned address trap.

22. The apparatus of claim 21 wherein the first thread further transforms each reference by setting at least one bit of each reference to one.

23. The apparatus of claim 22 wherein the first thread further transforms each reference by setting a least significant bit of each reference to a selected heap object to one.

24. The apparatus of claim 20 wherein the faulting address trap is a memory protection trap.

25. The apparatus of claim 24 wherein the first thread further transforms each reference by changing each reference to point to one of an unmapped area of memory and a protected area of memory.

26. The apparatus of claim 20 wherein the faulting address trap handler further suspends the second thread until the atomic operation is performed on all of the subset of heap objects.

27. The apparatus of claim 20 wherein the faulting address trap handler further places a reference to the heap object the second thread attempted to access in a queue, wherein the heap object the second thread attempted to access is processed with the atomic operation before heap objects that are not in the queue are processed with the atomic operation.

28. The apparatus of claim 20 wherein the faulting address trap handler further allows the second thread to access the heap object the second thread attempted to access after the atomic operation is performed on that heap object.

29. The apparatus of claim 20 wherein the faulting address trap handler further determines, prior to suspending the second thread, whether the atomic operation has already been performed on the heap object the second thread attempted to access.

30. The apparatus of claim 29 wherein in the faulting address trap handler further allows the second thread to access the heap object the second thread attempted to access if the atomic operation has already been performed on the heap object the second thread attempted to access.

31. The apparatus of claim 20 wherein the first thread further processes each heap object by setting a bit in the heap object to indicate that the atomic operation has been performed on the heap object.

32. The apparatus of claim 20 wherein the first thread further processes each heap object by storing the indication that the atomic operation has been performed on the heap object in a table.

33. The apparatus of claim 20 wherein the first thread further processes each heap object by:

processing the subset of heap objects in address order; and

storing an address of a last heap object processed as the indication that the atomic operation has been performed.

34. The apparatus of claim 20 wherein the first thread further transforms each reference by:

stopping all other threads of the plurality of concurrently executing threads;

transforming each reference to each heap object of the subset of heap objects; and

restarting all other threads of the plurality of concurrently executing threads.

35. The apparatus of claim 20 wherein the first thread further transforms each reference by:

transforming references to some heap objects of the subset of heap objects without stopping all other concurrently executing threads;

stopping all other threads of the plural of concurrently executing threads;

transforming references to a remainder of the subset of heap objects whose references are not already transformed; and

restarting all other threads of the plurality of concurrently executing threads.

36. The apparatus of claim 20, wherein the first thread further untransforms each reference to each of the subset of heap objects after all of the subset of heap objects have been processed with the atomic operation.

37. The apparatus of claim 36 wherein the first thread further untransforms each reference by:

stopping all other threads of the plurality of concurrently executing threads;

untransforming each reference to each heap object of the subset of heap objects; and

restarting all other threads of the plurality of concurrently executing threads.

38. The apparatus of claim 36 wherein the first thread further untransforms each reference by:

untransforming references to some heap objects of the subset of heap objects without stopping all other concurrently executing threads;

stopping all other threads of the plurality of concurrently executing threads;

untransforming references to a remainder of the subset of heap objects whose references are not already untransformed; and

restarting all other threads of the plurality of concurrently executing threads.

39. Apparatus for processing selected heap objects with an atomic operation using a faulting address trap, the apparatus comprising:

means for selecting, by a first thread of a plurality of concurrently executing threads, a subset of heap objects;

means for transforming, by the first thread, each reference to each heap object of the subset of heap objects in such a manner that the faulting address trap will be raised if an attempt is made by any other thread of the plurality of concurrently executing threads to access the heap object with the transformed reference;

means for processing, by the first thread, each heap object of the subset of heap objects with the atomic operation, wherein an indication that the atomic operation has been performed on the heap object is stored; and

means operable if the faulting address trap is raised during the processing of the subset of heap objects by the first thread because a second thread of the plurality of concurrently executing threads has attempted to access a heap object of the subset of heap objects, for suspending the second thread until the atomic operation is performed on the heap object the second thread attempted to access.

40. A computer readable medium comprising computer program code stored therein for processing selected heap objects with an atomic operation using a faulting address trap, the computer program code comprising:

program code for selecting, by a first thread of a plurality of concurrently executing threads, a subset of heap objects;

program code for transforming, by the first thread, each reference to each heap object of the subset of heap objects in such a manner that the faulting address trap will be raised if an attempt is made by any other thread of the plurality of concurrently executing threads to access the heap object with the transformed reference;

program code for processing, by the first thread, each heap object of the subset of heap objects with the atomic operation, wherein an indication that the atomic operation has been performed on the heap object is stored; and

program code operable if the faulting address trap is raised during the processing of the subset of heap objects by the first thread because a second thread of the plurality of concurrently executing threads has attempted to access a heap object of the subset of heap objects, for suspending the second thread until the atomic operation is performed on the heap object the second thread attempted to access.