Patent US5920876A successfully refreshed from Google Patents.
US5920876A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Performing exact garbage collection using bitmaps that identify pointer values within objects
Assignee: Oracle America Inc
•
Filing: 1997-04-23
•
Granted: 1999-07-06
•
Expires: 2017-04-23
Abstract
Abstract One embodiment of the present invention presents a method and apparatus for efficiently performing garbage collection on objects defined within an object-oriented programming system. Garbage collection typically involves following pointers to determine which objects are presently being referenced so that other objects, that are not being referenced, can be removed. To this end, the present invention maintains a bitmap for each object that indicates which variables in the object are pointer variables and which variables are non-pointer variables. A garbage collection process examines the bitmap, and on the basis of the pattern contained in the bitmap jumps to a particular routine that is tailored to garbage collect the particular pattern of pointer and non-pointer values in the object. Note that the system includes a routine tailored for each possible bitmap pattern. This technique speeds up the garbage collection process by eliminating the need to read type information one variable at a time to determine which variables within an object contain pointers.
Inventors
- 👤 David M. Ungar
- 👤 Mario I. Wolczko
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 10:33
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253; G06F12/0269; G06F12/0276; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4488; G06F9/4493; G06F2212/00; G06F2212/70; G06F2212/702; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956; Y10S707/99957
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
223 words
A method for performing garbage collection for an object defined within an object oriented programming system, the object including a variable storage area for storing both pointer variables and non-pointer variables associated with the object, the method comprising: associating a tagging bitmap with the object, each bit in the tagging bitmap specifying whether a corresponding variable in the variable storage area of the object contains a pointer variable; encountering the object during a garbage collection process, which operates by following pointers between objects in order to determine which objects are reachable through pointers, so that other non-reachable objects can be reclaimed; and following the pointer variables within the variable storage area of the object to other objects for garbage collection purposes by, using the tagging bitmap associated with the object to index a specific routine from a collection of routines, the collection of routines including a different routine for each possible tagging bitmap pattern, wherein the specific routine can assume by virtue of the prior indexing operation that certain variables in the variable storage area contain pointer variables, allowing the specific routine to follow the pointer variables without individually testing each variable to determine if the variable is a pointer variable, and executing the specific routine to follow the pointer variables in the variable storage area of the object to the other objects.
Claim 2
Dependent Claim
54 words
The method of claim 1, further comprising constructing a table containing starting addresses for routines in the collection of routines; and wherein the act of using the tagging bitmap to index the specific routine from the collection of routines involves looking up a starting address for the specific routine from the table of routines.
Claim 3
Dependent Claim
67 words
The method of claim 1, wherein the act of using the tagging bitmap associated with the object to index a specific routine involves: dividing the tagging bitmap into a plurality of smaller bitmaps; and using the plurality of smaller bitmaps to index a plurality of specific routines from the collection of routines in order to follow the pointer variables in the variable storage area of the object.
Claim 4
Independent Claim
242 words
An apparatus for performing garbage collection for an object defined within an object oriented programming system, the object including a variable storage area for storing both pointer variables and non-pointer variables associated with the object, the apparatus comprising: a central processing unit; a memory coupled to the central processing unit; a tagging mechanism configured to associate a tagging bitmap with the object, each bit in the tagging bitmap specifying whether a corresponding variable in the variable storage area of the object contains a pointer variable; a garbage collection mechanism configured to following pointers between objects in order to determine which objects are reachable through pointers, so that other non-reachable objects can be reclaimed; wherein the garbage collection mechanism is configured to follow the pointer variables within the variable storage area of the object to other objects for garbage collection purposes by, using the tagging bitmap associated with the object to index a specific routine from a collection of routines, the collection of routines including a different routine for each possible tagging bitmap pattern, wherein the specific routine can assume by virtue of the prior indexing operation that certain variables in the variable storage area contain pointer variables, allowing the specific routine to follow the pointer variables without individually testing each variable to determine if the variable is a pointer variable, and executing the specific routine to follow the pointer variables in the variable storage area of the object to the other objects.
Claim 5
Dependent Claim
57 words
The apparatus of claim 4, further comprising a table containing starting addresses for routines in the collection of routines; and wherein the garbage collection mechanism is configured to use the tagging bitmap to index the specific routine from the collection of routines by looking up a starting address for the specific routine from the table of routines.
Claim 6
Dependent Claim
57 words
The apparatus of claim 4, wherein the garbage collection mechanism is configured to: divide the tagging bitmap into a plurality of smaller bitmaps; and use the plurality of smaller bitmaps to index a plurality of specific routines from the collection of routines in order to follow the pointer variables in the variable storage area of the object.
Claim 7
Dependent Claim
240 words
A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for performing garbage collection for an object defined within an object oriented programming system, the object including a variable storage area for storing both pointer variables and non-pointer variables associated with the object, the method comprising: associating a tagging bitmap with the object, each bit in the tagging bitmap specifying whether a corresponding variable in the variable storage area of the object contains a pointer variable; encountering the object during a garbage collection process, which operates by following pointers between objects in order to determine which objects are reachable through pointers, so that other non-reachable objects can be reclaimed; and following the pointer variables within the variable storage area of the object to other objects for garbage collection purposes by, using the tagging bitmap associated with the object to index a specific routine from a collection of routines, the collection of routines including a different routine for each possible tagging bitmap pattern, wherein the specific routine can assume by virtue of the prior indexing operation that certain variables in the variable storage area contain pointer variables, allowing the specific routine to follow the pointer variables without individually testing each variable to determine if the variable is a pointer variable, and executing the specific routine to follow the pointer variables in the variable storage area of the object to the other objects.
Claim 8
Dependent Claim
59 words
The computer-readable storage medium of claim 7, wherein the method further comprises constructing a table containing starting addresses for routines in the collection of routines; and wherein the act of using the tagging bitmap to index the specific routine from the collection of routines involves looking up a starting address for the specific routine from the table of routines.
Claim 9
Dependent Claim
69 words
The computer-readable storage medium of claim 7, wherein the act of using the tagging bitmap associated with the object to index a specific routine involves: dividing the tagging bitmap into a plurality of smaller bitmaps; and using the plurality of smaller bitmaps to index a plurality of specific routines from the collection of routines in order to follow the pointer variables in the variable storage area of the object.
References Cited (Backward Citations)
US4922414A
Cited
US4757438A
Cited
US4775932A
Cited
US4920483A
Cited
US5222221A
Cited
US4989134A
Cited
US5136706A
Cited
US4907151A
Cited
US5088036A
Cited
US5321834A
Cited
US5301288A
Cited
US5241673A
Cited
US5535329A
Cited
US5355483A
Cited
US5218698A
Cited
US5561786A
Cited
US5560003A
Cited
US5692185A
Cited
US5367685A
Cited
US5408650A
Cited
US5566321A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-05 | 2003-01-04 | 2003-07-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-05 | 2007-01-04 | 2007-07-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-05 | 2011-01-04 | 2011-07-06 | $7700.00 | Window Closed / Lapsed |