Method and apparatus for locating nodes in a carded heap using a card marking structure and a node advance value

• US 6,115,782 A
• Filed: 04/23/1997
• Issued: 09/05/2000
• Est. Priority Date: 04/23/1997
• Status: Expired due to Fees

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Wolczko, Mario I., Ungar, David M.
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US08/842,136
• Time in Patent Office: 1,231 Days
• Field of Search: 707/103, 707/104, 707/202, 707/206, 711/173, 711/100, 711/111, 711/154, 711/170, 711/112, 711/171, 711/172
• US Class Current: 711/100
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Apparatus, methods, systems, and computer program products are disclosed that locate a modified pointer value in a carded heap memory. A plurality of nodes is allocated from the carded heap memory. The carded heap contains at least one structure that indicates the existence or non-existence of a node reference for each card. For those cards containing a node reference the structure also includes the offset from the start of the card to the node reference. A card index or pointer within a card (that is used to generate a card index) is given to the invention. The card index is used to specify a first card. A second card is found given the card index. The invention then follows, starting at the first node in the second card and using the node advance value for each followed node, the nodes in the carded memory area until it locates the node containing the pointer in the first card.

Claims

1. A computer controlled system having a central processing unit (CPU) and a memory coupled to said CPU, for locating a pointer in a node overlapping a first card within a carded heap memory area having a plurality of cards given a card identifier, said carded heap memory area containing a plurality of nodes each containing a node advance value, wherein said system comprises:

a card maintenance mechanism configured to maintain a card marking structure indicating a first node header for a first node in a second card and a node offset specifying a location of said first node header in said second card;

a first card location mechanism configured to locate said first card given said card identifier, said first card subsequent to said second card in said carded heap memory area;

a second card location mechanism configured to locate said second card given said first card;

a first node location mechanism configured to locate said first node header in said second card using said node offset into said second card; and

a node scanning mechanism configured to scan forward starting with the first node through nodes within the second card using the node advance values of the nodes within the second card until a node that intersects the first card is found.

2. The computer controlled system of claim 1 wherein said card identifier is a card index.

3. The computer controlled system of claim 1 wherein said card identifier is an address within said carded heap memory area used to derive a card index.

4. The computer controlled system of claim 1 wherein said first node header includes a node boundary and said node advance value is a node size.

5. A computer controlled method for locating a pointer in a node overlapping a first card within a carded heap memory area having a plurality of cards, said carded heap memory area containing a plurality of nodes each containing a node advance value, wherein said method comprises steps of:

(a) maintaining a card marking structure for indicating a first node header for a first node in a second card and a node offset for specifying a location of said first node header in said second card;

(b) locating said first card given a card identifier, said first card located subsequent to said second card in said carded heap memory area;

(c) locating said second card given said first card;

(d) locating said first node header in said second card using said node offset; and

(e) scanning forward starting with the first node through nodes within the second card using the node advance values of the nodes within the second card until a node that intersects the first card is found.

6. The computer controlled method of claim 5 wherein said card identifier is a card index.

7. The computer controlled method of claim 5 wherein said card identifier is an address within said carded heap memory area used to derive a card index.

8. The computer controlled method of claim 5 wherein said first node header includes a node boundary and said node advance value is a node size.

9. An apparatus having a central processing unit (CPU) and a memory coupled to said CPU for locating a pointer in a node overlapping a first card within a carded heap memory area having a plurality of cards given a card identifier, said carded heap memory area containing a plurality of nodes each containing a node advance value, wherein said apparatus comprises:

a card maintenance mechanism configured to maintain a card marking structure indicating a first node header for a first node in a second card and a node offset specifying a location of said first node header in said second card;

a first card location mechanism configured to locate said first card from said card identifier, said first card located subsequent to said second card in said carded heap memory area;

a second card location mechanism configured to locate said second card given said first card;

a first node location mechanism configured to locate said first node header in said second card using said node offset into said second card; and

a node scanning mechanism configured to scan forward starting with the first node through nodes within the second card using the node advance values of the nodes within the second card until a node that intersects the first card is found.

10. The apparatus of claim 9 wherein said card identifier is a card index.

11. The apparatus of claim 9 wherein said card identifier is an address within said carded heap memory area used to derive a card index.

12. The apparatus of claim 9 wherein said first node header includes a node boundary and said node advance value is a node size.

16. The computer program product of claim 12 wherein said first node header includes a node boundary and said node advance value is a node size.

13. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for causing a computer to locate a pointer in a node overlapping a first card within a carded heap memory area having a plurality of cards given a card identifier, said carded heap memory area containing a plurality of nodes each containing a node advance value, said computer readable code comprising;

computer readable program code devices configured to cause said computer to effect a card maintenance mechanism configured to maintain a card marking structure indicating a first node header for a first node in a second card and a node offset specifying a location of said first node header in said second card;

computer readable program code devices configured to cause said computer to effect a first card location mechanism configured to locate said first card given said card identifier, said first card located subsequent to said second card in said carded heap memnory area;

computer readable program code devices configured to cause said computer to effect a second card location mechanism configured to locate said second card given said first card;

computer readable program code devices configured to cause said computer to effect a first node location mechanism configured to locate said first node header in said second card using said node offset into said second card; and

computer readable program code devices configured to scan forward starting with the first node through nodes within the second card using the node advance values of the nodes within the second card until a node that intersects the first card is found.

14. The computer program product of claim 13 wherein said card identifier is a card index.

15. The computer program product of claim 13 wherein said card identifier is an address within said carded heap memory area used to derive a card index.