Computer system with heap and card table

• US 6,845,437 B2
• Filed: 08/13/2002
• Issued: 01/18/2005
• Est. Priority Date: 08/13/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wharmby, Andrew Dean, Borman, Samuel David
• Primary Examiner(s): Vital, Pierre M.
• Application Number:
  US10/217,718
• Publication Number:
  US 20030033498A1
• Time in Patent Office: 889 Days
• Field of Search: 711/6, 711/129, 711/132, 711/153, 711/159, 711/173, 711/206, 707/206
• US Class Current: 711/173
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A computer system has a heap for storing objects and a card table for tracking updates to objects on the heap, typically for garbage collection purposes. In particular, the heap is divided into segments, each corresponding to a card in the card table, and any update to a segment in the heap triggers a write barrier to mark the corresponding card in the card table. It is important that this write barrier is as efficient as possible to optimize system performance. In some circumstances an object update may be made to an address outside the heap. To ensure that this still properly maps to a card in the card table, the entire memory space is folded cyclically, so that any given memory address corresponds to one, and only one card, in the card table.

Claims

1. A method of operating a computer system having a memory, a portion of which is allocated to a heap for storing objects, said method comprising the steps of:

providing a card table comprising a set of N cards;

dividing the entire memory into M segments each segment having a segment size S, in which X of the M segments corresponds to the heap, where M>

N and N>

=X;

assigning each of the M segments to a corresponding one of said N cards, wherein at least one of said cards has multiple memory segments assigned to said card;

mapping the mth memory segment (0=>

m=>

M−

1) to a card C where C=(m mod N)/S wherein M, N, X, C, S and m are integers; and

marking a card to indicate an update to one of the one or more memory segments that correspond to the marked card.

2. The method of claim 1, wherein N and M are both powers of 2.

3. The method of claim 2, wherein the mapping from m to C is performed using only logical AND and bit shift operations.

4. The method of claim 1, wherein the heap comprises N or fewer memory segments.

5. The method of claim 1, wherein a card is only marked for an update that is potentially being made to the heap.

6. The method of claim 5, wherein the computer system further comprises a stack that is used for storing objects, and a card is only marked for an update that is made to an object on the heap or the stack.

7. The method of claim 5, wherein the card table is used as part of a garbage collection process to identify objects that have potentially been updated.

8. The method of claim 7, wherein if a marked card has multiple memory segments assigned to it, all of these memory segments are regarded as having been potentially updated.

9. The method of claim 7, wherein if a marked card has multiple memory segments assigned to it, only the ones of these memory segments that are allocated to the heap are regarded as having been potentially updated.

10. A computer system comprising:

a memory, a portion of which is allocated to a heap for storing objects, the entire memory being divided into M segments each segment having a segment size S, in which X segments correspond to the heap;

a card table comprising a set of N cards, wherein M>

N and N>

X, each of the M segments being assigned to a corresponding one of said N cards, so that at least one of said cards has multiple memory segments assigned to said card;

means for mapping the mth memory segment (0=>

m =>

M−

1) to a card C where C=(m mod N)/S;

wherein M, N, X, C, S and m are integers; and

a write barrier for marking a card to indicate an update to one of the one or more memory segments that correspond to the marked card.

11. The system of claim 10, wherein N and M are both powers of 2.

12. The system of claim 11, wherein the mapping from m to C is performed using only logical AND and bit shift operations.

13. The system of claim 10, wherein the heap comprises N or fewer memory segments.

14. The system of claim 10, wherein a card is only marked for an update that is potentially being made to the heap.

15. The system of claim 14, further comprising a stack that is used for storing objects, and wherein a card is only marked for an update that is made to an object on the heap or the stack.

16. The system of claim 10, wherein the card table is used as part of a garbage collection process to identify objects that have potentially been updated.

17. The system of claim 16, wherein if a marked card has multiple memory segments assigned to it, all of these memory segments are regarded as having been potentially updated.

18. The system of claim 16, wherein if a marked card has multiple memory segments assigned to it, only the ones of these memory segments that are allocated to the heap are regarded as having been potentially updated.

19. A computer program product comprising program instructions encoded in a machine readable format on a storage medium, said instructions when loaded into a computer system having a memory, a portion of which is allocated to a heap for storing objects, causing the computer system to perform the steps of:

providing a card table comprising a set of N cards;

dividing the entire memory into M segments each segment having a segment size S, of which X segments represent the heap, where M>

N and N>

=X;

assigning each of the M segments to a corresponding one of said N cards, wherein at least one of said cards has multiple memory segments assigned to said card;

mapping the mth memory segment (0=>

m=>

M−

1) to a card C, where C=(m mod N)/S, wherein M, N, X, C, S and m are integers; and

marking a card to indicate an update to one of the one or more memory segments that correspond to the marked card.

20. The computer program product of claim 19, wherein N and M are both powers of 2.

21. The computer program product of claim 20, wherein the mapping from m to C is performed using only logical AND and bit shift operations.

22. The computer program product of claim 19, wherein the heap comprises N or fewer memory segments.

23. The computer program product of claim 19, wherein a card is only marked for an update that is potentially being made to the heap.

24. The computer program product of claim 23, wherein the computer system further comprises a stack that is used for storing objects, and a card is only marked for an update that is made to an object on the heap or the stack.

25. The computer program product of claim 23, wherein the card table is used as part of a garbage collection process to identify objects that have potentially been updated.

26. The computer program product of claim 25, wherein if a marked card has multiple memory segments assigned to it, all of these memory segments are regarded as having been potentially updated.

27. The computer program product of claim 25, wherein if a marked card has multiple memory segments assigned to it, only the ones of these memory segments that are allocated to the heap are regarded as having been potentially updated.