MANAGING UNALLOCATED STORAGE SPACE USING EXTENTS AND BITMAPS

• US 20110131387A1
• Filed: 11/30/2009
• Published: 06/02/2011
• Est. Priority Date: 11/30/2009
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Bacik, Josef Michael
• Granted Patent: US 8,275,968 B2
• Time in Patent Office: Days
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management

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

1. A method, comprising:

maintaining, by a computing device executing a file system, a search tree that includes extents for managing first regions of unallocated storage space and bitmaps for managing second regions of unallocated storage space; and

for each region of unallocated storage space, determining whether to manage that region using an extent or a bitmap based on one or more space management criteria.

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

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

4. The method of claim 1, further comprising:

if a determination is made to manage a specific region of unallocated storage space using a specific bitmap, and the specific bitmap for managing that specific region does not exist, generating the specific bitmap.

5. The method of claim 4, wherein the specific bitmap also manages additional regions of unallocated storage space, further comprising:

if any of those additional regions of unallocated storage space are managed by an extent, deleting the extent.

6. The method of claim 1, wherein the management criteria include a size threshold, wherein regions that are smaller than the size threshold are managed by bitmaps.

7. The method of claim 1, wherein the management criteria include an extent entries threshold, wherein if the total number of extent entries included in the search tree exceeds the extent entries threshold, the region is managed by a specific bitmap.

8. 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.

9. The method of claim 1, further comprising:

receiving a request for unallocated memory space having a specified length;

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.

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

18. The computer readable storage medium of claim 1, the method further comprising:

if a determination is made to manage a specific region of unallocated storage space using a specific bitmap, and the specific bitmap for managing that specific region does not exist, generating the specific bitmap.

19. The computer readable storage medium of claim 18, wherein the specific bitmap also manages additional regions of unallocated storage space, the method further comprising:

if any of those additional regions of unallocated storage space are managed by an extent, deleting the extent.

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 that includes extents for managing first regions of unallocated storage space and bitmaps for managing second regions of unallocated storage space; and

for each region of unallocated storage space, determine whether to manage that region using an extent or a bitmap based on one or more space management criteria.

11. 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 first regions and the second regions.

12. 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 unallocated storage space using the specific bitmap, and the specific bitmap for managing that specific region does not exist.

13. The computing device of claim 12, wherein the specific bitmap also manages additional regions of unallocated storage space, the instructions further to cause the processor to:

if any of those additional regions of unallocated storage space are managed by an extent, delete the extent.

14. The computing device of claim 10, wherein the management criteria include a size threshold, wherein regions that are smaller than the size threshold are managed by bitmaps.

15. The computing device of claim 10, wherein the management criteria include an extent entries threshold, wherein if the total number of extent entries included in the search tree exceeds the extent entries threshold, the region is managed by a specific bitmap.

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 that includes extents for managing first regions of unallocated storage space and bitmaps for managing second regions of unallocated storage space; and

for each region of unallocated storage space, determining whether to manage that region using an extent or a bitmap based on one or more space management criteria.

20. The computer readable storage medium of claim 16, wherein the management criteria include a size threshold, wherein regions that are smaller than the size threshold are managed by bitmaps.

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