Patent US6453403B1 successfully refreshed from Google Patents.
US6453403B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for memory management using contiguous fixed-size blocks
Assignee: Oracle America Inc
•
Filing: 2000-05-19
•
Granted: 2002-09-17
•
Expires: 2020-05-19
Abstract
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.
Inventors
- 👤 Grzegorz Czajkowski
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 19:07
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
288 words
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.
Claim 2
Independent Claim
288 words
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.
Claim 3
Dependent Claim
15 words
The method of claim 1 , wherein the method is implemented within a virtual machine.
Claim 4
Dependent Claim
20 words
The method of claim 2 , wherein the virtual machine is implemented in accordance with a platform-independent virtual machine specification.
Claim 5
Dependent Claim
19 words
The method of claim 1 , further comprising storing a data structure in the allocated sequence of memory blocks.
Claim 6
Dependent Claim
18 words
The method of claim 1 , further comprising instantiating an object in the allocated sequence of memory blocks.
Claim 7
Dependent Claim
41 words
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.
Claim 8
Dependent Claim
20 words
The method of claim 1 , wherein the reachable blocks comprise one or more memory blocks associated with alive objects.
Claim 9
Independent Claim
343 words
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.
Claim 10
Independent Claim
343 words
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.
Claim 11
Dependent Claim
39 words
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.
Claim 12
Dependent Claim
25 words
The system of claim 8 , wherein the memory management program is further operable to store a structure in the allocated sequence of memory blocks.
Claim 13
Dependent Claim
25 words
The system of claim 8 , wherein the memory management program is further operable to instantiate an object in the allocated sequence of memory blocks.
Claim 14
Dependent Claim
22 words
The system of claim 8 , further comprising: a virtual machine, wherein the memory management program is executable by the virtual machine.
Claim 15
Dependent Claim
20 words
The system of claim 12 , wherein the virtual machine is implemented in accordance with a platform-independent virtual machine specification.
Claim 16
Dependent Claim
41 words
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.
Claim 17
Dependent Claim
20 words
The system of claim 8 , wherein the reachable blocks comprise one or more memory blocks associated with alive objects.
Claim 18
Dependent Claim
291 words
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.
Claim 19
Dependent Claim
291 words
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.
Claim 20
Dependent Claim
17 words
The carrier medium of claim 16 , wherein the program instructions are executable by a virtual machine.
Claim 21
Dependent Claim
21 words
The carrier medium of claim 17 , wherein the virtual machine is implemented in accordance with a platform-independent virtual machine specification.
Claim 22
Dependent Claim
26 words
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.
Claim 23
Dependent Claim
26 words
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.
Claim 24
Dependent Claim
42 words
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.
Claim 25
Dependent Claim
21 words
The carrier medium of claim 16 , wherein the reachable blocks comprise one or more memory blocks associated with alive objects.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-09-16 | 2006-03-18 | 2006-09-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-09-16 | 2010-03-18 | 2010-09-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-09-16 | 2014-03-18 | 2014-09-17 | $7700.00 | Window Closed / Lapsed |