System and method for persistent and robust storage allocation

• US 6,851,034 B2
• Filed: 09/30/2002
• Issued: 02/01/2005
• Est. Priority Date: 02/15/2000
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Challenger, James R. H., Iyengar, Arun K.
• Primary Examiner(s): CHACE, CHRISTIAN
• Application Number:
  US10/261,886
• Publication Number:
  US 20030028740A1
• Time in Patent Office: 855 Days
• Field of Search: 711/170, 711/171
• US Class Current: 711/170
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0676 Magnetic disk device
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A method for managing computer memory includes maintaining multiple sets of free blocks of memory wherein a free block is added to a set based on its size. In response to a request for a block of a request size, a set of blocks is searched for a free block which is at least as large as the request size but smaller than the request size plus a threshold. If such a block is found, the block is allocated in its entirety if such a free block is not found, a block at least as large as the request size maybe split and the request satisfied with the resulting split block. Methods for managing a block of contiguous persistent memory or storage and for coalescing adjacent free blocks using header information are also described.

Claims

1. A method for managing a block of contiguous persistent memory comprising the steps of:

maintaining a first pointer in main memory for determining a first free byte in a first block of memory;

maintaining headers in the persistent memory for a plurality of blocks wherein the headers include at least one code byte corresponding to at least one of the blocks; and

allocating a second block from the first block by setting the at least one code byte corresponding to the second block to indicate that the second block is no longer part of the first block and updating the first pointer in the main memory.

2. The method as recited in claim 1, further comprising the step of adding a block, b, to the first block, the step of adding comprising the steps of:

modifying a code byte corresponding to block b to indicate that block b is part of the first block;

updating the first pointer in the main memory.

3. The method as recited in claim 1, wherein the at least one code byte serves other functions in addition to indicating that the second block is no longer part of the first block.

4. The method as recited in claim 1, further comprising the step of periodically updating a second pointer in the persistent memory based on the value of the first pointer in the main memory.

5. The method as recited in claim 4, further comprising the step of, in response to a system failure, updating the first and second pointers by examining the at least one code byte.

6. The method as recited in claim 1, wherein the headers are initialized using a single block write.

7. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing a block of contiguous persistent memory comprising a main memory and at least one disk memory device, the method steps comprising:

maintaining a first pointer in main memory for determining a first free byte in a first block of memory;

maintaining headers in the persistent memory for a plurality of blocks wherein the headers include at least one code byte corresponding to at least one of the blocks; and

allocating a second block from the first block by setting the at least one code byte corresponding to the second block to indicate that the second block is no longer part of the first block and updating the first pointer in the main memory.

8. The program storage device as recited in claim 7, wherein the method steps performed by the program of instructions further comprise the step of adding a block, b, to the first block, the step of adding comprising the steps of:

modifying a code byte corresponding to block b to indicate that block b is part of the first block; and

updating the first pointer in the main memory.

9. The program storage device as recited in claim 7, wherein the at least one code byte serves other functions in addition to indicating that the second block is no longer part of the first block.

10. The program storage device as recited in claim 7, wherein the method steps performed by the program of instructions further comprise the step of periodically updating a second pointer in the persistent memory based on the value of the first pointer in the main memory.

11. The program storage device as recited in claim 10, wherein the method steps performed by the program of instructions further comprise the step of, in response to a system failure, updating the first and second pointers by examining the at least one code byte.

12. The program storage device as recited in claim 7, wherein the headers are initialized using a single block write.