Modified buddy system for managing disk space
AssigneeMicrosoft Corporation
InventorsMark Zbikowski, Robert I. Ferguson
Life of this patent
Estimating the term…
Abstract
A modified buddy system is adopted for managing disk space in a disk storage. The modified buddy system uses a minimal amount of memory space and provides very quick access to extents within the disk space. The modified buddy system utilizes a tree structure of nodes, wherein each node represents an extent of disk space. A bitmap is provided for holding state bits for each of the nodes in the tree structure. The bitmap is organized to preserve locality of reference.
Claims30
In a data processing system having disk storage with disk space of a given size, a method of managing the disk space, comprising the steps of:
- (a) modeling the disk space as a tree structure having multiple successively decreasing levels of nodes ranging from a top level to a bottom level, wherein each node represents an extent of the disk space and, for each level, nodes within the level represent extents of a like size, each node in each level other than the bottom level is a parent node having links connecting the parent node to child nodes, that are siblings, in a next successive level, the extents represented by the child nodes constitute a complete subdivision of the extent represented by the parent node, the size of the extents represented by the nodes decreases in each successive level and the sum of the sizes of the extents represented by the nodes for each successive level equals the given size of the disk space;
- (b) storing state information about each node in a bitmap that specifies whether the extent represented by the node is known to be at least partially allocated or not;
- and
- (c) using the bitmap and the tree structure to manage the disk space.
In a data processing system having disk storage with disk space of a given size, a method comprising the steps of:
- (a) modeling the disk space as a tree structure having multiple successively decreasing levels of nodes ranging from a top level to a bottom level, wherein each node represents an extent of the disk space, and for each level, nodes within the level represent extents of a like size, each node in each level other than the bottom level is a parent node having links connecting the parent node to child nodes, that are siblings, in a next successive level, the extents represented by the child nodes constitute a complete subdivision of the extent represented by the parent node, the size of the extents represented by the nodes decreases in each successive level and the sum of the sizes of the extents represented by the nodes for each successive level equals the given size of the disk space;
- (b) storing at least one state bit for each node in an ordered bitmap where the state bits for the nodes are ordered in a breadth first fashion beginning with the top level and continuing in breadth first fashion for each successive level, wherein the state bit for each node specifies whether the extent represented by the node is known to at least partially allocated;
- and
- (c) using the bitmap and the tree structure to manage the disk space.
In a data processing system having disk storage with disk space of a given size, a method of locating free disk space in the disk storage, comprising the steps of:
- (a) modeling the disk space as a tree structure having multiple successively decreasing levels of nodes ranging from a top level to a bottom level, wherein each node represents an extent of the disk space and, for each level, nodes within the level represent extents of a like size, each node in each level other than the bottom level is a parent node having links connecting the parent node to child nodes that are siblings in a next successive level, the extents represented by the child nodes constitute a complete subdivision of the extent represented by the parent node, the size of the extents represented by the nodes decreases in each successive level and the sum of the sizes of the extents represented by the nodes for each successive level equals the given size of the disk space;
- (b) storing state information about each node in a bitmap that specifies whether the extent is known to be at least partially allocated or not;
- (c) examining the state information in the bitmap about a selected one of the nodes in the tree structure that represents an extent of disk space of a desired size;
- (d) where the state information in the bitmap about the selected node specifies that the extent represented by the selected node is not known to be at least partially allocated,
- (i) examining the state information in the bitmap about each sibling of the selected node to determine if any of the siblings are known to be at least partially allocated;
- and
- (ii) where any sibling is known to be at least partially allocated, concluding that the selected node is free.
Dependencies are inferred from the claim text.