Method and apparatus for bag-to-set, buffering remembered set

• US 6,829,686 B2
• Filed: 02/08/2001
• Issued: 12/07/2004
• Est. Priority Date: 02/08/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Mathiske, Bernd J. W., Knippel, Ross C.
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US09/779,322
• Publication Number:
  US 20020107667A1
• Time in Patent Office: 1,398 Days
• Field of Search: 711/159, 711/170, 707/206
• US Class Current: 711/159
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method for providing a remembered set involves maintaining the remembered set as a bag, identifying when an event occurs, and transforming the remembered set into a set when the event occurs. The step of transforming includes obtaining a plurality of thread local store buffers and flushing the thread local store buffers to a global store buffer.

Claims

1. A method for providing a remembered set comprising:

maintaining the remembered set as a bag;

identifying when an event occurs;

transforming the remembered set into a set when the event occurs, wherein the step of transforming comprises;

obtaining a plurality of thread local store buffers; and

flushing the thread local store buffers to a global store buffer.

2. The method of claim 1 wherein the step of flushing further comprises:

eliminating a plurality of objects in the global store buffer that reside in the thread local store buffers wherein the objects are duplicates.

3. The method of claim 2 wherein the step of eliminating further comprises:

determining whether one or more dedicated mark bits are set in the objects referenced by the thread local store buffers; and

pushing the objects to the global store buffer, if said mark bits are not set.

4. The method of claim 2 wherein the step of flushing further comprises:

allocating a chunk in the global store buffer wherein the chunk is smaller than a current buffer in the thread local store buffers; and

shrinking the current buffer to the size of the chunk.

5. The method of claim 4 further comprising:

determining a variable threshold.

6. The method of claim 5 further comprising:

failing to shrink the current buffer to the size of the chunk if the variable threshold is larger than the chunk.

7. The method of claim 1 wherein the event occurs when the thread local store buffers have overflowed.

8. The method of claim 7 wherein the step of identifying further comprises:

using a memory protection mechanism to determine when the thread local store buffers has have overflowed.

9. The method of claim 7 wherein the step of identifying further comprises:

using a user trap to determine when the thread local store buffers has have overflowed.

10. The method of claim 9 wherein the user trap comprises:

filling a stack with a plurality of pointers to successive stack elements;

filling a top of the stack with a pointer to the user trap;

fetching a current pointer from the pointers to successive stack elements;

determining whether the current pointer is the pointer to the user trap; and

performing the user trap, if the current pointer is the pointer to the user trap.

11. The method of claim 1 wherein the step of flushing further comprises:

allocating a chunk in the global store buffer wherein the chunk is the same size as one of the thread local store buffers.

12. A remembered set comprising:

a remembered set configured to be maintained as a bag;

an event configured to be identified when the event occurs; and

a second remembered set configured to be transformed from the first remembered set when the event occurs, wherein the second remembered set is a set and comprises a flushing mechanism configured to flush a plurality of thread local store buffers into the a global store buffer.

13. The remembered set of claim 12 wherein the flushing mechanism further comprises:

a plurality of objects that reside in the thread local store buffers configured to be eliminated from the global store buffer, wherein the objects are duplicates.

14. The remembered set of claim 13 wherein the flushing mechanism further comprises:

one or more dedicated mark bits in the objects referenced by the thread local store buffers wherein the dedicated mark bits are configured to be determined if said mark bits are set and wherein the objects are configured to be pushed onto the global store buffer, if said mark bits are not set.

15. The remembered set of claim 13 wherein the flushing mechanism further comprises:

a chunk in the global store buffer configured to be allocated wherein the chunk is smaller than a current buffer in the thread local store buffers and the current buffer is configured to be shrunk to the size of the chunk.

16. The remembered set of claim 15 further comprising:

a variable threshold configured to be determined.

17. The remembered set of claim 16 further comprising:

the current buffer configured not to be shrunk to the size of the chunk if the variable threshold is larger than the chunk.

18. The remembered set of claim 12 wherein the event occurs when the thread local store buffers have overflowed.

19. The remembered set of claim 18 wherein the event further comprises:

a memory protection mechanism configured to determine when the thread local store buffers have overflowed.

20. The remembered set of claim 18 wherein the event further comprises:

a user trap configured to determine when the thread local store buffers have overflowed.

21. The remembered set of claim 20 wherein the user trap comprises:

a stack configured to be filled with a plurality of pointers to successive stack elements;

a top of the stack configured to be filled with a pointer to the user trap; and

a current pointer configured to be fetched from the pointers to successive stack elements,

wherein it is determined whether the current pointer is the pointer to the user trap and the user trap is configured to be performed if the current pointer is the pointer to the user trap.

22. The remembered set of claim 12 wherein the flushing mechanism further comprises:

a chunk in the global store buffer configured to be allocated wherein the chunk is the same size as one of the thread local store buffers.

23. A computer program product comprising:

a computer usable medium having computer readable program code embodied therein configured to provide a remembered set, the computer readable program code comprising;

computer readable code configured to cause a computer to maintain the remembered set as a bag;

computer readable code configured to cause the computer to identify when an event occurs; and

computer readable code configured to cause the computer to transform the remembered set into a set when the event occurs, wherein the computer readable code configured to cause a computer to transform comprises;

computer readable code configured to cause the computer to obtain a plurality of thread local store buffers; and

computer readable code configured to cause the computer to flush the thread local store buffers to a global store buffer.

24. The computer program product of claim 23 wherein the computer readable code configured to cause the computer to flush further comprises:

computer readable code configured to cause the computer to eliminate a plurality of objects in the global store buffer that reside in the thread local store buffers wherein the objects are duplicates.

25. The computer program product of claim 24, wherein the computer readable code configured to cause the computer to eliminate further comprises:

computer readable code configured to cause the computer to determine whether one or more dedicated mark bits are set in the objects referenced by the thread local store buffers; and

computer readable code configured to cause the computer to mark a plurality of the dedicated mark bits, if said mark bits are not set.

26. The computer program product of claim 24 wherein the computer readable code configured to cause the computer to flush further comprises:

computer readable code configured to cause the computer to allocate a chunk in the global store buffer, wherein the chunk is smaller than a current buffer in the thread local store buffers; and

computer readable code configured to cause the computer to shrink the current buffer to the size of the chunk.

27. The computer program product of claim 26 further comprising:

computer readable code configured to cause the computer to determine a variable threshold.

28. The computer program product of claim 27 further comprising:

computer readable code configured to cause the computer to fail to shrink the current buffer to the size of the chunk if the variable threshold is larger than the chunk.

29. The computer program product of claim 23 wherein the event occurs when the thread local store buffers have overflowed.

30. The computer program product of claim 29 wherein the computer readable code configured to cause the computer to identify further comprises:

computer readable code configured to cause the computer to use a memory protection mechanism to determine when the thread local store buffers have overflowed.

31. The computer program product of claim 29 wherein the computer readable code configured to cause the computer to identify further comprises:

computer readable code configured to cause the computer to use a user trap to determine when the thread local store buffers have overflowed.

32. The computer program product of claim 31 wherein the user trap comprises:

computer readable code configured to cause the computer to fill a stack with a plurality of pointers to successive stack elements;

computer readable code configured to cause the computer to fill a top of the stack with a pointer to the user trap;

computer readable code configured to cause the computer to fetch a current pointer from the pointers to successive stack elements;

computer readable code configured to cause the computer to determine whether the current pointer is the pointer to the user trap; and

computer readable code configured to cause the computer to perform the user trap, if the current pointer is the painter to the user trap.

33. The computer program product of claim 23 wherein the computer readable code configured to cause the computer to flush further comprises:

computer readable code configured to cause the computer to allocate a chunk in the global store buffer wherein the chunk is the same size as one of the thread local store buffers.