# US 8,275,968 B2 · Managing unallocated storage space using extents and bitmaps

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,275,968 B2
- Document ID: US8275968B2
- Status: Granted
- Kind: B2
- Application number: 12/628,137
- Filed: 2009-11-30
- Published: 2011-06-02
- Granted: 2012-09-25
- Earliest claimed: 2009-11-30
- Assignees: Red Hat, Inc.
- Inventors: Josef Michael Bacik
- Web page: https://patentgrep.com/patent/US8275968B2

## CPC

- G06F 12/023: {Free address space management}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computing device executing a file system maintains a search tree that includes extents for managing first regions of unallocated storage space and bitmaps for managing second regions of unallocated storage space. For each region of unallocated storage space, the file system determines whether to manage that region using an extent or a bitmap based on one or more space management criteria.

## Claims

### Claim 1

A method, comprising:
maintaining, by a computing device executing a file system, a search tree comprising a plurality of extents for managing a plurality of first regions of unallocated storage space and a plurality of bitmaps for managing a plurality of second regions of the unallocated storage space; and
for each region of the unallocated storage space, determining whether to manage the region using an extent or a bitmap based on one or more space management criteria.

### Claim 2 (depends on 1)

The method of claim 1, wherein each bit in the bitmap having a predetermined state identifies one of the second regions of the unallocated storage space.

### Claim 3 (depends on 1)

The method of claim 1, wherein the search tree is a self-balancing binary search tree that is indexed on starting bytes of the plurality of first regions and the plurality of second regions.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
if a determination is made to manage a specific region of the unallocated storage space using a specific bitmap, and the specific bitmap for managing that specific region does not exist, generating the specific bitmap.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
if a determination is made to manage a specific region of the unallocated storage space using a specific bitmap, and the specific bitmap manages additional regions of the unallocated storage space,
deleting an extent if any of the additional regions of the unallocated storage space are managed by the extent.

### Claim 6 (depends on 1)

The method of claim 1, wherein the one or more space management criteria further comprise a size threshold, wherein a region that is smaller than the size threshold is managed by a bitmap.

### Claim 7 (depends on 1)

The method of claim 1, wherein the one or more space management criteria further comprise an extent entries threshold, wherein if a total number of extent entries included in the search tree exceeds the extent entries threshold, the region is managed by a specific bitmap.

### Claim 8 (depends on 7)

The method of claim 7, wherein the extent entries threshold is a variable threshold that changes as the number of bitmaps included in the search tree changes.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
receiving a request for unallocated memory space having a specified size;
navigating the search tree linearly until a region having the specified size is located in an extent or in a bitmap; and
allocating the region.

### Claim 10

A computing device, comprising:
a memory to store instructions for a file system; and
a processing device, connected to the memory, to execute the instructions, wherein the instructions cause the processing device to:
execute a search tree comprising a plurality of extents for managing a plurality of first regions of unallocated storage space and a plurality of bitmaps for managing a plurality of second regions of the unallocated storage space; and
for each region of the unallocated storage space, determine whether to manage the region using an extent or a bitmap based on one or more space management criteria.

### Claim 11 (depends on 10)

The computing device of claim 10, wherein the search tree is a self-balancing binary search tree that is indexed on starting bytes of the plurality of first regions and the plurality of second regions.

### Claim 12 (depends on 10)

The computing device of claim 10, wherein the instructions further cause the processor to:
generate a specific bitmap if a determination is made to manage a specific region of the unallocated storage space using the specific bitmap, and the specific bitmap for managing that specific region does not exist.

### Claim 13 (depends on 10)

The computing device of claim 10, wherein the instructions further to cause the processor to:
if a determination is made to manage a specific region of the unallocated storage space using the specific bitmap, and the specific bitmap manages additional regions of the unallocated storage space, delete an extent if any of the additional regions of the unallocated storage space are managed by the extent.

### Claim 14 (depends on 10)

The computing device of claim 10, wherein the one or more space management criteria comprise a size threshold, wherein a region that is smaller than the size threshold is managed by a bitmap.

### Claim 15 (depends on 10)

The computing device of claim 10, wherein the one or more space management criteria further comprise an extent entries threshold, wherein if a total number of extent entries included in the search tree exceeds the extent entries threshold, the region is managed by a specific bitmap.

### Claim 16

A computer readable storage medium including instructions that, when executed by a processing device, cause the processing device to perform a method comprising:
maintaining, by a computing device executing a file system, a search tree comprising a plurality of extents for managing a plurality of first regions of unallocated storage space and a plurality of bitmaps for managing a plurality of second regions of the unallocated storage space; and
for each region of the unallocated storage space, determining whether to manage the region using an extent or a bitmap based on one or more space management criteria.

### Claim 17 (depends on 16)

The computer readable storage medium of claim 16, wherein the search tree is a self-balancing binary search tree that is indexed on starting bytes of the plurality of first regions and the plurality of second regions.

### Claim 18 (depends on 16)

The computer readable storage medium of claim 16, the method further comprising:
if a determination is made to manage a specific region of the unallocated storage space using a specific bitmap, and the specific bitmap for managing that specific region does not exist, generating the specific bitmap.

### Claim 19 (depends on 16)

The computer readable storage medium of claim 16, the method further comprising:
if a determination is made to manage a specific region of the unallocated storage space using a specific bitmap, and the specific bitmap manages additional regions of the unallocated storage space, deleting an extent if any of the additional regions of the unallocated storage space are managed by the extent.

### Claim 20 (depends on 16)

The computer readable storage medium of claim 16, wherein the one or more space management criteria further comprise a size threshold, wherein a region smaller than the size threshold is managed by a bitmap.

### Claim 21 (depends on 16)

The computer readable storage medium of claim 16, wherein the one or more space management criteria further comprise an extent entries threshold, wherein if a total number of extent entries included in the search tree exceeds the extent entries threshold, the region is managed by a specific bitmap.