Systems and methods for trimming logical block addresses corresponding to a data structure residing in non-volatile memory

• US 8,661,189 B2
• Filed: 08/31/2010
• Issued: 02/25/2014
• Est. Priority Date: 08/31/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Post, Daniel J., Tamura, Eric, Byom, Matthew, Crane, Neil, Herman, Kenneth, Barbou-des-Place, Francois
• Primary Examiner(s): PATEL, KAUSHIKKUMAR M
• Application Number:
  US12/872,849
• Publication Number:
  US 20120054465A1
• Time in Patent Office: 1,274 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

Systems and methods for trimming LBAs are provided. The LBAs can be trimmed from a file and from an NVM interface that maintains a logical-to-physical translation of the file'"'"'s LBAs and controls management of the file'"'"'s contents stored on non-volatile memory (“NVM”). The file can be any suitable file that has any number of associated LBAs. In addition, the file can be linked to one or more data chunks stored in the NVM, each data chunk associated with LBAs in the file. When a data chunk is retrieved or read from the NVM, that chunk no longer needs to be maintained in the NVM. Accordingly, after the data chunk is retrieved from the NVM and provided to an appropriate destination, the LBAs associated with the retrieved data chunk can be trimmed.

Claims

1. A method for use with non-volatile memory (“

NVM”

), the method comprising;

providing a swap file having a plurality of logical block addresses (“

LBAs”

) associated with data stored in the NVM;

paging in swap file data from the NVM into volatile memory such that the paged-in swap file exists simultaneously in the NVM and the volatile memory; and

in response to a successful page in event, trimming the LBAs associated with the paged-in swap file data without deleting the paged-in swap file data, wherein the paged-in swap file data remains in the NVM until a NVM memory management function causes the paged-in swap file data to be removed and wherein the paged-in swap file data contained in the volatile memory is accessible for use by an application.

2. The method of claim 1, wherein the swap file data stored in the NVM previously resided in a volatile memory.

3. The method of claim 1, wherein the trimming further comprises de-allocating the LBAs associated with the paged-in swap file data from the swap file.

4. The method of claim 1, wherein the trimming further comprises marking the LBAs associated with the paged-in swap file data in translation table metadata as invalid.

5. The method of claim 1, wherein the swap file is maintained as allocated by a file system manager even though LBAs within the swap file are trimmed.

6. The method of claim 1, wherein the swap-file data is stored at physical addresses within the NVM based on a logical-to-physical translation of the LBAs.

7. A system comprising:

volatile memory and non-volatile memory (“

NVM”

), wherein a portion of the NVM stores swap file data;

circuitry operative to execute an operating system, the operating system comprising;

a file system manager operative to manage files, wherein at least one of the files is a swap file; and

a swap file manager operative to;

manage page-in and page-out events between the volatile memory and NVM, wherein a paged-in swap file exists simultaneously in the NVM and the volatile memory; and

in response to a successful page in event, provide trim instructions to trim logical block addresses (“

LBAs”

) associated with the paged-in swap file data to a NVM interface without deleting the paged-in swap file data, wherein the paged-in swap file data remains in the NVM until a NVM memory management function causes the paged-in swap file data to be removed and wherein the paged-in swap file data contained in the volatile memory is accessible for use by an application; and

wherein the NVM interface is operative to manage the NVM in response to receiving the trim instructions.

8. The system of claim 7, wherein the swap file manager provides the trim instructions to the file system manager, wherein the file system manager trims the LBAs associated with the paged-in swap file data from the swap file.

9. The system of claim 7, wherein the NVM interface is further operative to mark the LBAs associated with the paged-in swap file data in translation table metadata as invalid.

10. The system of claim 7, wherein the NVM interface is further operative to cease maintaining the paged-in swap file data in the NVM.

11. The system of claim 7, wherein the NVM is nand flash memory.

12. A method for trimming logical block addresses (“

LBAs”

) from a swap file, the method implemented in a system comprising a file system layer, a translation layer, and a physical layer, the method comprising;

maintaining a swap file in the file system layer, the swap file having a plurality of LBAs allocated to swap file data stored in the physical layer;

paging in swap file data from the physical layer into volatile memory such that the paged-in swap file exists simultaneously in the NVM and the volatile memory;

in response to a successful page in event, trimming the LBAs associated with the paged-in swap file data from the swap file and from the translation layer without deleting the paged-in swap file data, wherein the paged-in swap file data remains in the NVM until a NVM memory management function causes the paged-in swap file data to be removed and wherein the paged-in swap file data contained in the volatile memory is accessible for use by an application.

13. The method of claim 12, wherein trimming the LBAs associated with the paged-in swap file data decreases a management burden of having to manage the trimmed LBAs in the translation layer.

14. The method of claim 12, wherein trimming the LBAs associated with the paged-in swap file data decreases a management burden of having to manage the swap file data corresponding to the trimmed LBAs that are stored in the physical layer.

15. The method of claim 12, wherein trimming the LBAs associated with the paged-in swap file data further comprises marking the trimmed LBAs for deletion in the translation layer.

16. The method of claim 12, wherein trimming the LBAs associated with the paged-in swap file data from the swap file comprises de-allocating the LBAs corresponding to the trimmed LBAs.

17. A method for trimming logical block addresses (“

LBAs”

) from a data file, the method comprising;

providing a data file having a plurality of LBAs, wherein content associated with the data file is stored in non-volatile memory (“

NVM”

) that requires use of an interface that handles logical-to-physical address translation;

retrieving data file content from the NVM for storage in volatile memory, wherein after the retrieved data is provided to a predetermined destination in the volatile memory, the retrieved data need not be preserved in the NVM even though it exists simultaneously in the NVM and the volatile memory; and

in response to a successful retrieval of the data file content, trimming LBAs associated with the retrieved data file content without deleting the retrieved data file content, wherein the retrieved data remains in the NVM until a NVM memory management function causes the retrieved data to be removed and wherein the retrieved data contained in the volatile memory is accessible for use by an application.

18. The method of claim 17, wherein trimming LBAs comprises de-allocating the LBAs associated with the retrieved data file content from the data file.

19. The method of claim 17, wherein trimming LBAs comprises ceasing management of the retrieved content stored in the NVM.

20. The method of claim 17, wherein the data file is a SQL database file.