Method and system for object allocation using fill counts

• US 7,480,684 B2
• Filed: 04/20/2006
• Issued: 01/20/2009
• Est. Priority Date: 11/04/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Ahrens, Matthew A., Bonwick, Jeffrey S., Moore, William H.
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Smith; Brannon W
• Application Number:
  US11/408,134
• Publication Number:
  US 20070106632A1
• Time in Patent Office: 1,006 Days
• Field of Search: 707/205, 711/209
• US Class Current: 1/1
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A method for locating a root block in file system metadata, includes traversing the file system metadata to locate a leaf block, wherein the leaf block comprises a plurality of root blocks and at least one of the plurality of root blocks is unallocated, allocating the at least of one the plurality of unallocated root blocks to obtain an allocated root block, wherein the leaf block is associated with a fill count and the fill count is less than a maximum fill count of the leaf block.

Claims

1. A method for allocating a root block in file system metadata, comprising:

traversing the file system metadata to locate a non-filled leaf block,

wherein the non-filled leaf block comprises a plurality of root blocks and at least one of the plurality of root blocks is unallocated,

wherein the file system metadata comprises a plurality of meta indirect blocks,

wherein a first meta indirect block of the plurality of meta indirect blocks comprises a pointer to the non-filled leaf block and a first fill count associated with the non-filled leaf block,

wherein the first fill count corresponds to a number of allocated root blocks in the non-filled leaf block, and

wherein locating the non-filled leaf block comprises determining that the first fill count is less than a maximum fill count;

traversing the non-filled leaf block to locate an unallocated root block of the plurality of root blocks; and

allocating the unallocated root block to obtain an allocated root block;

wherein a second meta indirect block of the plurality of meta indirect blocks comprises pointers to the first meta indirect block and a third meta indirect block of the plurality of meta indirect blocks,

wherein the second meta indirect block further comprises a second fill count,

wherein the third meta indirect block comprises a third fill count, and

wherein the second fill count is a sum of the first fill count and the third fill count.

2. The method of claim 1, further comprising:

updating the first fill count after allocating the unallocated root block.

3. The method of claim 1, wherein the first fill count is a non-negative integer.

4. The method of claim 1, wherein the allocated root block references a hierarchical tree corresponding to a file.

5. The method of claim 4, wherein the hierarchical tree comprises a data block and an indirect block, wherein the indirect block directly references the data block, and wherein the allocated root block indirectly references the indirect block.

6. The method of claim 1, wherein the file system metadata is organized in a hierarchical tree.

7. The method of claim 1, wherein the maximum fill count is less than 25 percent of the plurality of the root blocks.

8. The method of claim 1, further comprising:

updating the second fill count after allocating the unallocated root block.

9. A system, comprising:

a data processor;

a storage pool comprising;

a non-filled leaf block, wherein the leaf block comprises a plurality of root blocks and at least one of the plurality of root blocks is unallocated, and

file system metadata comprising a plurality of meta indirect blocks, wherein a first meta indirect block of the plurality of meta indirect blocks comprises a pointer to the non-filled leaf block and a first fill count associated with the non-filled leaf block, wherein the first fill count corresponds to a number of allocated root blocks in the non-filled leaf block;

the data processor configured with instructions for a file system configured to;

traverse the file system metadata to locate the non-filled leaf block, wherein locating the non-filled leaf block comprises determining that the first fill count is less than a maximum fill count,

traverse the non-filled leaf block to locate an unallocated root block of the plurality of root blocks, and

allocate the unallocated root block to obtain an allocated root block;

update the first fill count after allocating the unallocated block;

and wherein the first fill count is a non-negative integer.

14. The system of claim 9,

wherein a second meta indirect block of the plurality of meta indirect blocks comprises pointers to the first meta indirect block and a third meta indirect block of the plurality of meta indirect blocks,

wherein the second meta indirect block further comprises a second fill count,

wherein the third meta indirect block comprises a third fill count, and

wherein the second fill count is a sum of the first fill count and the third fill count.

15. The system of claim 14, wherein the file system is further configured to:

update the second fill count after allocating the unallocated root block.

10. The system of 9, wherein the allocated root block references a hierarchical tree corresponding to a file.

11. The system of 10, wherein the hierarchical tree comprises a data block and an indirect block, wherein the indirect block directly references the data block, and wherein the allocated root block indirectly references the indirect block.

12. The system of 9, wherein the file system metadata is organized in a hierarchical tree.

13. The system of 9, wherein the maximum fill count is less than 25 percent of the plurality of the root blocks.