Method and system for object allocation using fill counts

• US 20070106632A1
• Filed: 04/20/2006
• Published: 05/10/2007
• Est. Priority Date: 11/04/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Moore, William, Bonwick, Jeffrey, Ahrens, Matthew
• Granted Patent: US 7,480,684 B2
• Time in Patent Office: Days
• 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 locating a root block in file system metadata, comprising:

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.

2. The method of claim 1, further comprising:

updating the fill count after allocating the at least one unallocated block.

3. The method of claim 1, wherein the fill count is stored in a block pointer referencing the leaf block.

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

5. The method of claim 1, wherein the fill count corresponds to a number of allocated root blocks in the leaf block.

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

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

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

9. The method of claim 1, wherein less than 25 percent of the plurality of the root blocks are allocated.

10. A system, comprising:

a storage pool comprising;

file system metadata comprising 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;

a file system configured to;

traverse the file system metadata to locate the leaf block,

allocate 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.

11. The system of 10, wherein the file system is further configured to:

update the fill count after allocating the at least one unallocated block.

12. The system of 10, wherein the fill count is stored in a block pointer referencing the leaf block.

13. The system of 10, wherein the fill count is a non-negative integer.

14. The system of 10, wherein the fill count corresponds to a number of allocated root blocks in the leaf block.

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

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

17. The system of 10, wherein the file system metadata is organized in a hierarchical tree.

18. The system of 10, wherein less than 25 percent of the plurality of the root blocks are allocated.