EFFICIENT ALLOCATION POLICIES FOR A SYSTEM HAVING NON-VOLATILE MEMORY

• US 20120047316A1
• Filed: 08/23/2010
• Published: 02/23/2012
• Est. Priority Date: 08/23/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Post, Daniel J., Sutton, Brian
• Granted Patent: US 8,966,209 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

Systems and methods are disclosed for efficient allocation policies for a system having non-volatile memory. A file system allocator of the system can be configured to allocate memory regions that are aligned with one or more logical blocks of a logical space (e.g., one or more super block-aligned regions). In some embodiments, the file system allocator can monitor the number of free sectors corresponding to each logical block. In other embodiments, the file system allocator can monitor a ratio of free space to total space corresponding to each logical block. The file system allocator can select a logical block based at least in part on the number of free sectors of the logical block. In some cases, the file system allocator can allocate the free sectors of the logical block in a sequential order.

Claims

1. A method for optimal memory allocations in a logical space corresponding to a non-volatile memory (“

NVM”

), the method comprising;

receiving a request to store data associated with a file in the NVM;

selecting a logical block of the logical space with a largest number of free sectors;

allocating the free sectors of the logical block in a sequential order to the file; and

writing the data to the free sectors based on the sequential order.

2. The method of claim 1, wherein the logical block corresponds to a super block-aligned region.

3. The method of claim 1, wherein the selecting the logical block further comprises monitoring a number of free sectors corresponding to each logical block in the logical space.

4. The method of claim 1, wherein the writing the data further comprises writing the data to a first free sector of the logical block.

5. The method of claim 4, wherein the writing the data further comprises:

determining whether a new logical block is needed; and

in response to determining that a new logical block is needed, selecting a logical block with a largest number of free sectors as the new logical block.

6. The method of claim 5, wherein the determining whether a new logical block is needed comprises monitoring an allocation point within the logical block.

7. The method of claim 5, wherein in response to determining that a new logical block is not needed, continuing to write the data to a next sequential free sector of the logical block.

8. The method of claim 1, wherein the NVM comprises a NAND flash memory.

9. A system comprising:

a non-volatile memory (“

NVM”

) comprising blocks; and

a file system allocator for allocating logical blocks of a logical space to files, wherein each of the logical blocks is aligned with at least one super block of the NVM, the file system allocator operative to;

receive a request to store data associated with a file in the NVM;

select a logical block as a current logical block based at least in part on a number of free sectors associated with the logical block; and

allocate at least a portion of the free sectors of the current logical block to the file.

10. The system of claim 9, wherein the file system allocator is operative to sequentially allocate at least the portion of the free sectors of the current logical block to the file.

11. The system of claim 9, wherein the file system allocator is operative to:

allocate a first free sector of the current logical block to the file;

determine that additional free sectors are needed;

determine if a new logical block is needed; and

in response to determining that a new logical block is not needed, allocate a second sector of the free sectors of the current logical block to the file.

12. The system of claim 11, wherein the file system allocator is operative to determine that a new logical block is not needed based on determining that an allocation point has not reached the number of free sectors in the current logical block.

13. The system of claim 11, wherein the file system allocator is operative to determine that a new logical block is not needed based on failing to detect an end of the current logical block.

14. The system of claim 11, wherein the file system allocator is operative to determine that a new logical block is not needed based on detecting additional free space in the current logical block.

15. The system of claim 11, wherein in response to determining that a new logical block is needed, the file system allocator is operative to:

select a new logical block as the current logical block based at least in part on a number of free sectors associated with the new logical block; and

allocate at least a portion of the free sectors of the new logical block to the file.

16. The system of claim 9, wherein the file system allocator is operative to maintain an array of a number of free sectors corresponding to each logical block of the logical space.

17. The system of claim 16, wherein the array is an array of integers.

18. The system of claim 9, wherein the file system allocator is operative to:

determine that the system has logical blocks that are constant in size; and

select the logical block that has a largest number of free sectors.

19. The system of claim 9, wherein the file system allocator is operative to:

determine that the system has logical blocks that are variable in size; and

select the logical block that has a largest ratio of free space to total space.

20. The system of claim 9, wherein the NVM comprises a NAND flash memory.

21. A method for allocating memory regions, the method comprising:

monitoring a number of free sectors corresponding to each memory region of a logical space, wherein each memory region is associated with at least one block of a non-volatile memory (“

NVM”

); and

allocating at least a portion of a memory region to a file, wherein the memory region is a super block-aligned region of the logical space with a largest number of free sectors.

22. The method of claim 21, wherein each memory region is associated with at least one physical block of the NVM.

23. The method of claim 21, wherein the allocating at least the portion of the memory region to the file comprises allocating the free sectors of the memory region in a forward sequential order.

24. The method of claim 21, wherein the monitoring the number of free sectors corresponding to each memory region comprises maintaining an array, wherein each element of the array corresponds to the number of free sectors of each memory region of the logical space.

25. The method of claim 24, further comprising:

determining the number of free sectors corresponding to a memory region using a free space mapping structure; and

updating an element in the array corresponding to the memory region based on the number of free sectors.

26. The method of claim 25, wherein the free space mapping structure comprises at least one of a block bitmap or a file allocation table (“

FAT”

).

27. The method of claim 25, further comprising:

detecting an end of the memory region;

determining the number of remaining free sectors corresponding to the memory region by searching the free space mapping structure; and

updating the element in the array corresponding to the memory region based on the number of remaining free sectors.

28. The method of claim 24, further comprising:

detecting that a free sector of the memory region has been allocated; and

decreasing the element in the array corresponding to the memory region by one.

29. The method of claim 24, further comprising:

detecting that a file associated with the memory region has been deleted; and

increasing at least one corresponding element in the array by the number of sectors previously associated with the file.

30. The method of claim 21, wherein the NVM comprises a NAND flash memory.