Storage region management method, storage region allocation method and program

• US 20110145538A1
• Filed: 02/17/2011
• Published: 06/16/2011
• Est. Priority Date: 08/17/2008
• Status: Active Grant

• Current Assignee: Makoto Yoshioka
• Original Assignee: S Grants Company Limited
• Inventors: Yoshioka, Makoto, Shinjo, Koutaro, Shinjo, Toshio, Kokubun, Mitsuhiro
• Granted Patent: US 9,164,902 B2
• Time in Patent Office: Days
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/04 Addressing variable-length words or parts of words
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0674 Disk device

Abstract

A storage area management method for a data storage apparatus partitions an acquired storage area into storage areas with differing power-of-2 sizes and manages each of them. Also, a storage area allocation method receives an allocation request for a storage area that includes a requested allocation size, and acquires an available storage area whose size is the smallest power-of-2 size encompassing the requested allocation size, and obtains a binary expression of the requested allocation size, and in response to the received allocation request, allocates a contiguous storage area comprised of storage areas each of whose size is a power of 2 of a value of a bit position wherein a 1 is set in the binary expression.

Claims

1. A storage area management method for a data storage apparatus comprising:

an acquiring step that acquires an allocation size of a region, which is a storage area that has been preliminarily allocated;

a computing step that computes a sum of mutually differing powers of 2 by a calculation using the allocation size and a region allocation unit size;

a partitioning step that partitions the region into primary segments for each of exponents with mutually differing powers of 2 that is computed, which primary segments are storage areas each of whose size is calculated by multiplying that power of 2 with the region allocation unit size; and

a managing step that manages the region for each primary segment.

2. A storage area management method according to claim 1, wherein

the partitioning step partitions the region into primary segments in a sequence of magnitude of sizes of the primary segments.

3. A storage area management method according to claim 2, further comprising

a keeping step that obtains an allocation position, which is a beginning address of a primary segment, and an allocation size, which is a size of the primary segment, from the region allocation size and a region head address and keeps the allocation position and the allocation size for each primary segment.

4. A storage area allocation method for allocating a storage area with a requested allocation size, which is a size of a storage area that is requested to be allocated, from a primary segment that is partitioned out of a region by means of the storage area management method according to claim 1, comprising:

a receiving step that receives an allocation request for a storage area that includes a requested allocation size;

an acquiring step that acquires an available storage area whose size is a smallest size of the product of power-of-2 sizes and the region allocation unit size encompassing the requested allocation size from the region;

an obtaining step that obtains a binary expression whose value is the requested allocation size divided by the allocation unit size; and

an allocation step that allocates, in response to the received allocation request, from an available storage area with the acquired smallest size of the product of the power-of-2 size and the region allocation unit size, a contiguous storage area comprised of storage areas each of whose size is a product of the allocation unit size and a power of 2 of a value of a bit position wherein a 1 is set in the binary expression.

5. A storage area allocation method according to claim 4, wherein the region is partitioned into primary segments in a sequence of magnitude of sizes of the primary segments and

the acquiring step acquires an available storage area whose size is a smallest size of the product of power-of-2 sizes and the region allocation unit size encompassing the requested allocation size by searching over the partitioned primary segments, from the primary segment with the smallest size to the primary segment with the largest size, and

the allocation step allocates the acquired available storage area whose size is the smallest for a product of the above power of 2 and the region allocation unit size to the storage area with the requested allocation size.

6. A storage area allocation method according to claim 5, wherein

the acquiring step acquires the available storage area with the smallest size by searching over the partitioned primary segments, from the primary segment with the smallest size to the primary segment with the largest size, using a buddy system associated with each primary segment.

7. A storage area allocation method according to claim 5, wherein

the acquiring step acquires the available storage area with the smallest size by searching over the partitioned primary segments, from the primary segment with the smallest size to the primary segment with the largest size, and when an available storage area with the smallest size cannot be acquired from any of the primary segments, acquires the available storage area by repeating the process of setting the size of the available storage area to be double that of the size of the last sought for available storage area and searching for an available storage area by ranging over the partitioned primary segments, from the primary segment with the smallest size to the primary segment with the largest size.

9. A storage area allocation method according to claim 4, further comprising

a releasing step that releases a storage area other than the allocated storage area of the acquired available storage area with the smallest size.

10. A storage area allocation method according to claim 9, wherein

the releasing step releases the storage area other than the allocated storage area of the acquired available storage area with the smallest size in accordance with a buddy system.

13. A storage area release method that releases storage areas allocated by the storage area allocation method according to claim 4 comprising;

a release step that releases the storage areas according to a buddy system in a sequence from the storage area whose bit position in the above binary expression is the smallest.

15. A program that a computer is caused to execute, for performing the storage area management method according to claim 1.

16. A computer readable medium for storing a program that a computer is caused to execute, for performing the storage area management method according to claim 1.

17. A program that a computer is caused to execute, for performing the storage area allocation method according to claim 4.

18. A computer readable medium for storing a program that a computer is caused to execute, for performing the storage area allocation method according to claim 4.

21. A program that a computer is caused to execute, for performing the storage area release method according to claim 13.

22. A computer readable medium for storing a program that a computer is caused to execute, for performing the storage area release method according to claim 13.

26. A data storage apparatus of which storage areas are managed by the storage area management method according to claim 1.

27. A storage medium of which storage areas are managed by the storage area management method according to claim 1.

28. A data storage apparatus wherein a storage area with the requested allocation size is allocated by the storage area allocation method according to claim 4.

29. A storage medium wherein a storage area with the requested allocation size is allocated by the storage area allocation method according to claim 4.

33. A storage area allocation apparatus for allocating a storage area with a requested allocation size, which is a size of a storage area that is requested to be allocated, from a primary segment that is partitioned out of a region by means of the storage area management method according to claim 1, comprising:

an allocation request receiving means that receives an allocation request for a storage area that includes a requested allocation size;

an available storage area acquiring means that acquires an available storage area whose size is a smallest size of the product of power-of-2 sizes and the region allocation unit size encompassing the requested allocation size from the region; and

an allocation means that obtains a binary expression whose value is the requested allocation size divided by the allocation unit size and allocates, in response to the received allocation request, from an available storage area with the acquired smallest size of the product of the power-of-2 size and the region allocation unit size, a contiguous storage area comprised of storage areas each of whose size is a product of the allocation unit size and a power of 2 of a value of a bit position wherein a 1 is set in the binary expression.

8. A storage area allocation method for allocating a storage area with a requested allocation size, which is a size of a storage area that is requested to be allocated, from a region, which is a preliminary allocated storage area, comprising:

a receiving step that receives an allocation request for a storage area that includes a requested allocation size;

an acquiring step that acquires an available storage area whose size is a smallest size of the product of power-of-2 sizes and the region allocation unit size encompassing the requested allocation size from the region;

an obtaining step that obtains a binary expression whose value is the requested allocation size divided by the allocation unit size; and

an allocation step that allocates, in response to the received allocation request, from an available storage area with the acquired smallest size of the product of the power-of-2 size and the region allocation unit size, a contiguous storage area comprised of storage areas each of whose size is a product of the allocation unit size and a power of 2 of a value of a bit position wherein a 1 is set in the binary expression and which contiguous storage area is conjoined by the storage areas in a sequence of magnitude of sizes of the storage areas.

11. A storage area allocation method according to claim 8, further comprising

a releasing step that releases a storage area other than the allocated storage area of the acquired available storage area with the smallest size.

12. A storage area allocation method according to claim 11, wherein

the releasing step releases the storage area other than the allocated storage area of the acquired available storage area with the smallest size in accordance with a buddy system.

14. A storage area release method that releases storage areas allocated by the storage area allocation method according to claim 8 comprising;

a release step that releases the storage areas according to a buddy system in a sequence from the storage area whose bit position in the above binary expression is the smallest.

19. A program that a computer is caused to execute, for performing the storage area allocation method according to claim 8.

20. A computer readable medium for storing a program that a computer is caused to execute, for performing the storage area allocation method according to claim 8.

23. A program that a computer is caused to execute, for performing the storage area release method according to claim 14.

24. A computer readable medium for storing a program that a computer is caused to execute, for performing the storage area release method according to claim 14.

30. A data storage apparatus wherein a storage area with the requested allocation size is allocated by the storage area allocation method according to claim 8.

31. A storage medium wherein a storage area with the requested allocation size is allocated by the storage area allocation method according to claim 8.

25. A data configuration adapted to a storage area management method for a data storage apparatus, in which the storage area management method acquires an allocation size of a region that is a storage area that is preliminarily allocated, and a sum of mutually differing powers of 2 is computed by a calculation using the allocation size and a region allocation unit size, and for each of exponents with mutually differing powers of 2 that is computed, the region is partitioned into primary segments each of whose size is calculated by multiplying that power of 2 with the region allocation unit size, and the region is managed for each primary segment, the data configuration comprising:

an allocated partition table that holds an allocation position and size of a primary segment for each primary segment number that identifies a primary segment, wherein

the allocated partition table enables allocation management for storage areas by means of a buddy system for each primary segment.

32. A storage area management apparatus for a data storage apparatus comprising:

a computing means that acquires an allocation size of a region, which is a storage area that has been preliminarily allocated and computes a sum of mutually differing powers of 2 by a calculation using the allocation size and a region allocation unit size; and

a managing means that partitions the region into primary segments for each of exponents with mutually differing powers of 2 that is computed, which primary segments are storage areas each of whose size is calculated by multiplying that power of 2 with the region allocation unit size and manages the region for each primary segment.

34. A storage area allocation apparatus for allocating a storage area with a requested allocation size, which is a size of a storage area that is requested to be allocated, from a region, which is a preliminary allocated storage area, comprising:

an allocation request receiving means that receives an allocation request for a storage area that includes a requested allocation size;

an available storage area acquiring means that acquires an available storage area whose size is a smallest size of the product of power-of-2 sizes and the region allocation unit size encompassing the requested allocation size from the region; and

an allocation means that obtains a binary expression whose value is the requested allocation size divided by the allocation unit size and allocates, in response to the received allocation request, from an available storage area with the acquired smallest size of the product of the power-of-2 size and the region allocation unit size, a contiguous storage area comprised of storage areas each of whose size is a product of the allocation unit size and a power of 2 of a value of a bit position wherein a 1 is set in the binary expression and which contiguous storage area is conjoined by the storage areas in a sequence of the magnitude of sizes of the storage areas.