Back to results
US 8,819,382 B2Granted
Split heap garbage collection
AssigneeApple Inc.
InventorsFilip J. Pizlo, Geoffrey Garen, Mark Hahnenberg
Life of this patent
Estimating the term…
Abstract
A method and an apparatus to scan a stack for references to a heap used in executing a code via the heap are described. The heap may be allocated with fixed and varied sized slots. Each varied sized slot may be referenced by at most one fixed sized slot. Which slots are live may be identified based on the references in the stack. A fixed slot can be live if referenced by the stack. A fixed or varied slot referenced by a live slot can also be live. Varied sized slots referenced by the stack may be identified as pinned. The heap may be de-fragmented to reclaim fixed sized slots which are not live without moving live fixed sized slots and to reclaim varied sized slots which are neither live nor pinned by moving live varied slots.
Claims21
A machine-readable non-transitory storage medium having instructions therein, which when executed by a machine, cause the machine to perform a method, the method comprising:
- maintaining a plurality of first structures and a plurality of second structures separately in a first portion and a second portion of a heap in a memory to execute a code based on the heap, wherein each second structure is referenced by at most one of the first structure, at least one of the first structures representing an object created via the execution of the code, the object having a dynamic property associated with at least one of the second structures, wherein the code is linked with a particular code capable of referencing the dynamic property of the object without referencing the first structure representing the object;
- performing non-moving garbage collection operations on the first portion of the heap to identify which of the first structures are available for future allocation from the first portion of the heap without moving the identified first structures;
- and
- performing moving garbage collection operations on the second portion of the heap to identify which of the second structures are movable within the second portion of the heap for future allocation from the second portion of the heap, wherein the non-moving garbage collection operations and the moving garbage collection operations are performed substantially in parallel, wherein a particular one of the second structures is not movable if the particular second structure is referenced by the particular code, and wherein the identified movable second structures are moved within the second portion of the heap for future allocation from the second portion of the heap.
1 more element
A machine-readable non-transitory storage medium having instructions therein, which when executed by a machine, cause the machine to perform a method, the method comprising:
- scanning a stack used in executing a code via a heap of memory, wherein one or more fixed sized slots are allocated in the heap, wherein one or more varied sized slots are allocated in the heap, each varied sized slot being referenced by at most one of the fixed sized slots, wherein the stack includes references to the heap;
- identifying which of the fixed sized slots are live, wherein a fixed sized slot referenced by the references of the stack is live and wherein a fixed sized slot referenced by a live fixed slot is live;
- identifying which of the varied sized slots are live, wherein a varied sized slot referenced by a live fixed size slot is live;
- identifying which of the varied sized slots are pinned, wherein a varied sized slot referenced by the references of the stack is pinned;
- defragmenting the heap to reclaim fixed sized slots which are not live without moving live fixed sized slots;
- and
- defragmenting the heap to reclaim varied sized slots which are neither live nor pinned by moving live varied slots.
4 more elements
A computer implemented method comprising:
- maintaining a plurality of first structures and a plurality of second structures separate in a first portion and a second portion of a heap in a memory to execute a code based on the heap, wherein each second structure is referenced by at most one of the first structure, at least one of the first structures representing an object created via the execution of the code, the object having a dynamic property associated with at least one of the second structures, wherein the code is linked with a particular code capable of referencing the dynamic property of the object without referencing the first structure representing the object;
- performing non-moving garbage collection operations on the first portion of the heap to identify which of the first structures are available for future allocation from the first portion of the heap without moving the identified first structures;
- and
- performing moving garbage collection operations on the second portion of the heap to identify which of the second structures are movable within the second portion of the heap for future allocation from the second portion of the heap, wherein the non-moving garbage collection operations and the moving garbage collection operations are performed substantially in parallel, wherein a particular one of the second structures is not movable if the particular second structure is referenced by the particular code, and wherein the identified movable second structures are moved within the second portion of the heap for future allocation from the second portion of the heap.
1 more element
A computer system comprising:
- a memory storing instructions including a code linked with a particular code, the memory including a heap for the code and the particular code;
- a processor coupled to the memory to execute the instructions from the memory, the processor being configured to
- maintain a plurality of first structures and a plurality of second structures separate in a first portion and a second portion of the heap to execute the code, wherein each second structure is referenced by at most one of the first structure, at least one of the first structures representing an object created via the execution of the code, the object having a dynamic property associated with at least one of the second structures, wherein the particular code is configured for referencing the dynamic property of the object without referencing the first structure representing the object,
- perform non-moving garbage collection operations on the first portion of the heap to identify which of the first structures are available for future allocation from the first portion of the heap without moving the identified first structures, and
- perform moving garbage collection operations on the second portion of the heap to identify which of the second structures are movable within the second portion of the heap for future allocation from the second portion of the heap, wherein the non-moving garbage collection operations and the moving garbage collection operations are performed substantially in parallel, wherein a particular one of the second structures is not movable if the particular second structure is referenced by the particular code, and wherein the identified movable second structures are moved within the second portion of the heap for future allocation from the second portion of the heap.
2 more elements
Dependencies are inferred from the claim text.