Patent ID: 7480684

Claim:
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.