Hierarchical mapping of free blocks of cylinder groups of file systems built on slices of storage and linking of the free blocks
First Claim
1. A computer-implemented method of operating a file server, the file server including data storage and a data processor, the data storage storing a logical volume and a file system built on the logical volume, the file system including multiple cylinder groups, each of the cylinder groups including file system blocks, the file system blocks including allocated blocks and free blocks of the data storage, the logical volume including slices of the data storage, and each slice of the data storage storing at least one of the cylinder groups, the method comprising the data processor executing computer instructions stored on a non-transitory computer-readable storage medium to perform the steps of:
- (a) maintaining, in the file server, a hierarchical map of the free blocks of the data storage in the file system, the hierarchical map having an upper level including a summary of the free blocks of the data storage in groups of the slices, the hierarchical map having at least one intermediate level including a summary of the free blocks of the data storage in sub-groups of the slices, and the hierarchical map having a bottom level including a summary of the free blocks of the data storage in each of the slices of the data storage; and
(b) searching the hierarchical map in a top-down fashion to find a cylinder group of the file system including a free block of the data storage in the file system; and
(c) linking the free block of the data storage from the cylinder group found in step (b) to a file.
9 Assignments
0 Petitions
Accused Products
Abstract
In a file server, a file system is built upon a volume of data storage. The file system includes multiple cylinder groups. Each cylinder group includes file system blocks. The file system blocks include allocated blocks and free blocks. The volume includes slices of storage, and each slice stores at least one of the cylinder groups. A hierarchical slice map has a top level that includes a count of free blocks in the file system, an upper level that includes a count of free blocks in groups of the slices, an intermediate level that includes a count of the free blocks in sub-groups of the slices, and a bottom level that includes a count of the free blocks in each slice of storage. To find a free block for allocation to a file, the slice map hierarchy is searched in a top-down fashion.
-
Citations
20 Claims
-
1. A computer-implemented method of operating a file server, the file server including data storage and a data processor, the data storage storing a logical volume and a file system built on the logical volume, the file system including multiple cylinder groups, each of the cylinder groups including file system blocks, the file system blocks including allocated blocks and free blocks of the data storage, the logical volume including slices of the data storage, and each slice of the data storage storing at least one of the cylinder groups, the method comprising the data processor executing computer instructions stored on a non-transitory computer-readable storage medium to perform the steps of:
-
(a) maintaining, in the file server, a hierarchical map of the free blocks of the data storage in the file system, the hierarchical map having an upper level including a summary of the free blocks of the data storage in groups of the slices, the hierarchical map having at least one intermediate level including a summary of the free blocks of the data storage in sub-groups of the slices, and the hierarchical map having a bottom level including a summary of the free blocks of the data storage in each of the slices of the data storage; and (b) searching the hierarchical map in a top-down fashion to find a cylinder group of the file system including a free block of the data storage in the file system; and (c) linking the free block of the data storage from the cylinder group found in step (b) to a file. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A file server comprising:
-
data storage storing a logical volume and a file system built on the logical volume, the file system including multiple cylinder groups, each of the cylinder groups including file system blocks, the file system blocks including allocated blocks and free blocks of the data storage, the logical volume including slices of the data storage, and each slice of the data storage storing at least one of the cylinder groups, a data processor coupled to the data storage for storing data in the data storage and for reading stored data from the data storage; and a non-transitory computer readable storage medium storing computer instructions that, when executed by the data processor, perform the steps of; (a) maintaining, in the file server, a hierarchical map of the free blocks of the data storage in the file system, the hierarchical map having an upper level including a summary of the free blocks of the data storage in groups of the slices, the hierarchical map having at least one intermediate level including a summary of the free blocks of the data storage in sub-groups of the slices, and the hierarchical map having a bottom level including a summary of the free blocks of the data storage in each of the slices of the data storage; (b) searching the hierarchical map in a top-down fashion to find a cylinder group of the file system including a free block of the data storage in the file system; and (c) linking the free block of the data storage from the cylinder group found in step (b) to the file. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
19. A non-transitory computer-readable storage medium containing instructions that, when executed by a data processor of a file server, perform the steps of:
-
(a) maintaining, in the file server, a hierarchical map of free blocks of data storage in a file system built upon a volume of slices of the data storage, each of the slices of the data storage containing at least one cylinder group of the file system, the hierarchical map having an upper level including a summary of the free blocks of the data storage in groups of the slices, the hierarchical map having at least one intermediate level including a summary of the free blocks of the data storage in sub-groups of the slices, and the hierarchical map having a bottom level including a summary of the free blocks of the data storage in each of the slices of the data storage; and (b) searching the hierarchical map in a top-down fashion to find a cylinder group of the file system including a free block of the data storage in the file system; and (c) linking the free block of the data storage from the cylinder group found in step (b) to a file. - View Dependent Claims (20)
-
Specification