System and method for memory management using contiguous fixed-size blocks

• US 6,453,403 B1
• Filed: 05/19/2000
• Issued: 09/17/2002
• Est. Priority Date: 05/19/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Czajkowski, Grzegorz
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Patel, Aseet
• Application Number:
  US09/574,967
• Time in Patent Office: 851 Days
• Field of Search: 711/171, 711/170, 707/206, 707/200, 709/1, 709/104
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A system and method for memory allocation from a heap comprising memory blocks of a uniform fixed size. Each memory block has a status bit. A binary status key stores a Boolean value indicating free memory. The heap is scanned in order until a sequence of a requested quantity of free contiguous memory blocks is found or NULL is returned. Each scanned free memory block is marked un-free by assigning its status bit to the logical negative of the binary status key. If the end of the heap is reached before a sequence of sufficient quantity is found, all reachable blocks are marked as free. The binary status key is flipped such that all memory blocks which were marked free are now un-free, and vice versa. Any memory block whose corresponding structure has become unreferenced is reclaimed for future use. The scan then continues from the beginning of the heap. In another embodiment, a memory allocation for a partitioned data structure from a heap of fixed-size memory blocks may be used. The quantity of memory blocks required to store a data structure is determined. The required quantity of the memory blocks, which may be noncontiguous, is allocated from the heap. The allocated memory blocks are linked in a list such that the components of the data structure are partitioned in the proper order across the allocated quantity of memory blocks.

Claims

1. A method for memory management, the method comprising:

receiving a request for allocation of a quantity of contiguous memory blocks from a heap, wherein the heap comprises a plurality of memory blocks, wherein each of the plurality of memory blocks is of a uniform fixed size, wherein each memory block is associated with a status bit, wherein a binary status key stores a value indicating availability for allocation, and wherein the status bit for each of the memory blocks has the value stored in the binary status key if that memory block is available for allocation;

scanning the heap to find a contiguous sequence of memory blocks of the requested quantity and each of whose status bit has the value from the binary status key which indicates availability for allocation, wherein said scanning further includes beginning from a starting point in the heap indicated by a current block variable and sequentially encountering the memory blocks whose status bit has the value from the binary status key which indicates availability for allocation;

setting the status bit for each encountered memory block to the logical negative of the value of the binary status key;

performing garbage collection on the heap if the end of the heap is reached while sequentially encountering the memory blocks, wherein said performing the garbage collection includes;

setting the status bit for all reachable blocks to the value of the binary status key;

flipping the value of the binary status key, wherein said flipping the value of the binary status key includes setting the value of the binary status key to its logical negative; and

setting the starting point to the beginning of the heap; and

allocating the sequence of memory blocks of the requested quantity.

2. The method of claim 1, wherein the method is implemented within a virtual machine.

3. The method of claim 2, wherein the virtual machine is implemented in accordance with a platform-independent virtual machine specification.

4. The method of claim 1, further comprising storing a data structure in the allocated sequence of memory blocks.

5. The method of claim 1, further comprising instantiating an object in the allocated sequence of memory blocks.

6. The method of claim 1, wherein the status bit for each memory block comprises a color bit in a bitmap, wherein the bitmap is operable to store the status of each of the plurality of memory blocks in the heap.

7. The method of claim 1, wherein the reachable blocks comprise one or more memory blocks associated with alive objects.

8. A system for memory management, the system comprising:

a heap comprising a plurality of memory blocks, wherein each of the plurality of memory blocks is of a uniform fixed size, wherein each memory block is associated with a status bit, wherein a binary status key stores a value indicating availability for allocation, and wherein the status bit for each of the memory blocks has the value stored in the binary status key if that memory block is available for allocation; and

a memory management program which is operable to receive a request for allocation of a quantity of contiguous memory blocks from the heap;

wherein the memory management program is further operable to scan the heap to find a contiguous sequence of memory blocks of the requested quantity and each of whose status bit has the value from the binary status key which indicates availability for allocation, beginning from a starting point in the heap indicated by a current block variable and sequentially encountering the memory blocks whose status bit has the value from the binary status key which indicates availability for allocation;

wherein the memory management program is further operable to set the status bit for each encountered memory block to the logical negative of the value of the binary status key;

wherein the memory management program is further operable to perform garbage collection on the heap if the end of the heap is reached while encountering the memory blocks sequentially, wherein in the performing the garbage collection, the memory management program is further operable to;

set the status bit for all reachable blocks to the value of the binary status key;

flip the value of the binary status key, wherein in the flipping the value of the binary status key, the memory management program is further operable to set the value of the binary status key to its logical negative; and

set the starting point to the beginning of the heap; and

wherein the memory management program is further operable to allocate the sequence of memory blocks of the requested quantity.

9. The system of claim 8, further comprising:

a CPU; and

a memory coupled to the CPU;

wherein the memory stores the heap and the memory management program, and wherein the memory management program is executable by the CPU.

10. The system of claim 8, wherein the memory management program is further operable to store a structure in the allocated sequence of memory blocks.

11. The system of claim 8, wherein the memory management program is further operable to instantiate an object in the allocated sequence of memory blocks.

12. The system of claim 8, further comprising:

a virtual machine, wherein the memory management program is executable by the virtual machine.

13. The system of claim 12, wherein the virtual machine is implemented in accordance with a platform-independent virtual machine specification.

14. The system of claim 8, wherein the status bit for each memory block comprises a color bit in a bitmap, wherein the bitmap is operable to store the status of each of the plurality of memory blocks in the heap.

15. The system of claim 8, wherein the reachable blocks comprise one or more memory blocks associated with alive objects.

16. A carrier medium comprising program instructions which are computer-executable to implement:

receiving a request for allocation of a quantity of contiguous memory blocks from a heap, wherein the heap comprises a plurality of memory blocks, wherein each of the plurality of memory blocks is of a uniform fixed size, wherein each memory block is associated with a status bit, wherein a binary status key stores a value indicating availability for allocation, and wherein the status bit for each of the memory blocks has the value stored in the binary status key if that memory block is available for allocation;

scanning the heap to find a contiguous sequence of memory blocks of the requested quantity and each of whose status bit has the value from the binary status key which indicates availability for allocation, wherein said scanning further includes beginning from a starting point in the heap indicated by a current block variable and sequentially encountering the memory blocks whose status bit has the value from the binary status key which indicates availability for allocation;

setting the status bit for each encountered memory block to a logical negative of the value of the binary status key;

performing garbage collection on the heap if the end of the heap is reached while sequentially encountering the memory blocks, wherein said performing the garbage collection includes;

setting the status bit for all reachable blocks to the value of the binary status key;

flipping the value of the binary status key, wherein said flipping the value of the binary status key includes setting the value of the binary status key to its logical negative; and

setting the starting point to the beginning of the heap; and

allocating the sequence of memory blocks of the requested quantity.

17. The carrier medium of claim 16, wherein the program instructions are executable by a virtual machine.

18. The carrier medium of claim 17, wherein the virtual machine is implemented in accordance with a platform-independent virtual machine specification.

19. The carrier medium of claim 16, wherein the program instructions are further executable to implement storing a structure in the allocated sequence of memory blocks.

20. The carrier medium of claim 16, wherein the program instructions are further executable to implement instantiating an object in the allocated sequence of memory blocks.

21. The carrier medium of claim 16, wherein the status bit for each memory block comprises a color bit in a bitmap, wherein the bitmap is operable to store the status of each of the plurality of memory blocks in the heap.

22. The carrier medium of claim 16, wherein the reachable blocks comprise one or more memory blocks associated with alive objects.