Method and system for storing a sparse file using fill counts

• US 20070106863A1
• Filed: 04/19/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: Ahrens, Matthew, Moore, William, Bonwick, Jeffrey
• Granted Patent: US 7,716,445 B2
• Time in Patent Office: Days
• US Class Current: 711/170
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method for storing a first block and a second block, the includes storing the first block and the second block in a storage pool, and storing a third block in the storage pool, wherein the third block references the first block and second block and comprises a first fill count and a second fill count, wherein the first fill count corresponds to one selected from the group consisting of a number of data blocks directly referenced by the first block, a number of data blocks indirectly referenced by the first block, if the first block is an indirect block, wherein the first fill count is one if the first block is a data block.

Claims

1. A method for storing a first block and a second block, comprising:

storing the first block and the second block in a storage pool; and

storing a third block in the storage pool, wherein the third block references the first block and second block and comprises a first fill count and a second fill count,

wherein the first fill count corresponds to one selected from the group consisting of a number of data blocks directly referenced by the first block, a number of data blocks indirectly referenced by the first block, if the first block is an indirect block,

wherein the first fill count is one if the first block is a data block.

2. The method of claim 1, further comprising:

storing a fourth block in the storage pool, wherein the fourth block references the third block location and comprises a third fill count, wherein the third fill count comprises the sum of the first fill count and the second fill count.

3. The method of claim 1, wherein the first fill count corresponds to the sum of fill counts recorded in all blocks referenced by the first block.

4. The system of claim 1, wherein the first block, the second block, and the third block are associated with a sparse file.

5. A system, comprising:

a storage pool comprising;

a first block and a second block, and

a third block referencing the first block and second block and comprising a first fill count and a second fill count, wherein the first fill count is associated with the first block and the second fill count is associated with the second block; and

a storage pool allocator configured to store the first block, the second block, and the third block in the storage pool

wherein the first fill count corresponds to one selected from the group consisting of a number of data blocks directly referenced by the first block, a number of data blocks indirectly referenced by the first block, if the first block is an indirect block,

wherein the first fill count is one if the first block is a data block.

6. The system of claim 5, wherein the first fill count corresponds to the sum of fill counts recorded in all blocks referenced by the first block.

7. The system of claim 5, wherein the first block, the second block, and the third block are associated with a sparse file.

8. The system of claim 5, wherein the third block comprises:

a first block pointer referencing the first block, wherein the first block pointer comprises the first fill count;

a second block pointer referencing the second block, wherein the second block pointer comprises the second fill count; and

a third block pointer comprises a third fill count, wherein the third fill count is zero.

9. A method for locating a hole in a file, comprising:

obtaining a root associated with the file, wherein the root comprises a root block fill count and references a hierarchical data structure comprising a plurality of blocks pointer;

if the root block fill count is not equal to the maximum fill count for the root;

traversing the hierarchical data structure; and

for each block pointer encountered;

obtaining a fill count associated with the block pointer,

determining whether the fill count is zero, if the fill count does not correspond to the maximum fill count for the block pointer, wherein the hole is located if the file count is zero.

10. The method of claim 9, wherein at least one of the plurality of block pointers references one selected from the group consisting of an indirect block and a data block.

11. The method of claim 9, wherein one of the plurality of block pointers does not reference any block, if the fill count recorded in the one of the plurality of block pointers is zero.