Card-based management of discardable files

• US 8,463,802 B2
• Filed: 09/30/2010
• Issued: 06/11/2013
• Est. Priority Date: 08/19/2010
• Status: Active Grant

• Current Assignee: Western Digital Israel Limited (Western Digital Corporation)
• Original Assignee: SanDisk IL Ltd. (Western Digital Corporation)
• Inventors: Lin, Jason T., Hahn, Judah Gamliel
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): CHEEMA, AZAM M
• Application Number:
  US12/895,428
• Publication Number:
  US 20120047154A1
• Time in Patent Office: 985 Days
• Field of Search: None
• US Class Current: 707/756
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/1737 for reducing power consumption or coping with limited storage space, e.g. in mobile devices saving storage space on storage devices G06F3/0608; power saving in storage systems G06F3/0625
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket

Abstract

A method and storage device are disclosed for card-based management of discardable files, where discardable files are tracked in a discardable file system on a storage device and are invisible to a host file system, which only tracks user files and free space. The method includes the storage device detecting currently free logical clusters corresponding to at least a portion of free space in the storage area and determining whether addresses associated with a subsequent user file write request are in a range of free clusters managed in the discardable file system by the storage device. When addresses in a host write request overlap the addresses of space managed by the discardable file system, the storage device discards discardable files as necessary and removes the newly freed clusters from the discardable file system, such that the discardable file system data structure is resized when room for user files is needed.

Claims

1. A method for managing files with a storage device, the method comprising:

in a storage device operatively coupled to a host, the storage device having a storage area comprising user files, free space and discardable files, the storage device;

identifying a record of free clusters in a discardable file system data structure, wherein the discardable file system data structure is separate from a host file system data structure stored on the storage device;

receiving a request from the host to store a user file in the storage area;

determining whether logical block addresses (LBAs) associated with data in the request are in a range of logical block addresses associated with clusters in the record in the discardable file system data structure; and

when the LBAs are in the range and there is free space available in the range;

mapping the LBAs of the user file to free clusters identified in the discardable file system data structure; and

subsequently removing the clusters mapped to the LBAs of the user file from the discardable file system data structure.

2. The method of claim 1, further comprising:

when the LBAs are in the range and there is no free space available in the range;

discarding at least one discardable file to create free clusters;

mapping the LBAs of the user file to free clusters created by discarding the at least one discardable file; and

subsequently removing the clusters mapped to the LBAs of the user file from the discardable file system data structure.

3. The method of claim 2, wherein the clusters comprise logical clusters.

4. The method of claim 2, further comprising maintaining in the storage area of the storage device the host file system data structure independently of the discardable file system data structure, the storage device exclusively managing and generating the discardable file system data structure in a manner hidden from the host, the discardable file system data structure comprising a list of clusters in the storage area corresponding to at least one discardable file in the storage area, wherein the at least one discardable file is identified as free space in the host file system data structure.

5. The method of claim 4, wherein the discardable file system data structure comprises one of a table, a hash map, a binary tree, an array or a list.

6. The method of claim 4, wherein when the LBAs are outside the range:

associating the LBAs with free physical sectors in the storage area; and

updating the host file system data structure to reflect the association.

7. The method of claim 2, wherein discarding the at least one discardable file comprises the storage device, independently of a host operating system, identifying a lowest priority discardable file and discarding the identified lowest priority discardable file.

8. The method of claim 1, further comprising the storage device detecting currently free clusters by reading the host file system data structure to identify free clusters and updating the discardable file system data structure to include at least a portion of the free clusters in the storage area.

9. The method of claim 8, wherein updating the discardable file system data structure comprises including only free clusters in the discardable file system data structure that are arranged in a contiguous run of at least N free clusters, where N is a multiple of clusters equal to an erase block size in the storage device.

10. The method of claim 8, wherein the storage device initiates the step of detecting currently free clusters in response to a trigger event.

11. The method of claim 10, wherein the trigger event comprises the storage device detecting that a number of free clusters included in the discardable file system data structure is less than a threshold amount of free clusters.

12. The method of claim 10, wherein the trigger event comprises detecting a host write to the host file system data structure.

13. The method of claim 10, wherein the trigger event comprises the storage device receiving a notification signal from the host indicating that a user file has been deleted.

14. A storage device for removable connection with a host, the storage device comprising:

a storage area having user files, free space and discardable files; and

a controller in communication with the storage area, wherein the controller is configured to;

identify a record of the free clusters in a discardable file system data structure, wherein the discardable file system data structure is separate from a host file system data structure stored on the storage device;

receive a request from the host to store a user file in the storage area;

determine whether logical block addresses (LBAs) associated with data in the request are in a range of logical block addresses associated with clusters in the record in the discardable file system data structure; and

when the LBAs are in the range and there is free space available in the range;

map the LBAs of the user file to free clusters identified in the discardable file system data structure; and

subsequently remove the clusters mapped to the LBAs of the user file from the discardable file system data structure.

15. The storage device of claim 14, wherein the controller is further configured to,

when the LBAs are in the range and there is no free space available in the range:

discard at least one discardable file to create free clusters;

map the LBAs of the user file to free clusters created by discarding the at least one discardable file; and

subsequently remove the clusters mapped to the LBAs of the user file from the discardable file system data structure.

16. The method of claim 15, wherein the clusters comprise logical clusters.

17. The storage device of claim 15, wherein the controller is further configured to maintain the host file system data structure independently of the discardable file system data structure, the storage device exclusively managing and generating the discardable file system data structure in a manner hidden from the host, the discardable file system data structure comprising a list of clusters in the storage area corresponding to at least one discardable file in the storage area, wherein the at least one discardable file is identified as free space in the host file system data structure.

18. The storage device of claim 17, wherein the discardable file system data structure comprises one of a table, a hash map, a binary tree, an array or a list.

19. The storage device of claim 17, wherein the controller is configured to discard the at least one discardable file by, independently of a host operating system, identifying a lowest priority discardable file and discarding the identified lowest priority discardable file.

20. The storage device of claim 17, wherein the controller is further configured to, responsive to determining the LBAs are outside the range:

associate the LBAs with free physical sectors in the storage area; and

update the host file system data structure to reflect the association.

21. The storage device of claim 17, wherein the controller is configured to detect currently free clusters by reading the host file system data structure to identify free clusters and updating the discardable file system data structure to include at least a portion of the free clusters in the storage area.

22. The storage device of claim 21, wherein the controller is configured to update the discardable file system data structure by including only free clusters in the discardable file system data structure that are arranged in a contiguous run of at least N free clusters, where N is a multiple of clusters equal to an erase block size in the storage device.

23. The storage device of claim 21, wherein the controller is configured to initiate the step of detecting currently free clusters in response to a trigger event.

24. The storage device of claim 23, wherein the trigger event comprises detection by the controller that a number of free clusters included in the discardable file system data structure is less than a threshold amount of free clusters.

25. The storage device of claim 23, wherein the trigger event comprises a host write to the host file system data structure.

26. The storage device of claim 23, wherein the trigger event comprises receipt by the controller of a notification signal from the host indicating that a user file has been deleted.