Grouped trim bitmap

• US 10,268,385 B2
• Filed: 12/23/2016
• Issued: 04/23/2019
• Est. Priority Date: 05/03/2016
• Status: Active Grant

• Current Assignee: SK Hynix Inc.
• Original Assignee: SK Hynix Inc.
• Inventors: Huang, Szutao, Lin, Chris
• Primary Examiner(s): Rojas, Midys
• Assistant Examiner(s): Doan, Khoa D
• Application Number:
  US15/390,268
• Publication Number:
  US 20170322728A1
• Time in Patent Office: 851 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0638 Combination of memories, e.g. ROM and RAM such as to permit replacement or supplementing of words in one module by words in another module address formation of the next microinstruction G06F9/26; masking faults in memories by using spares or by reconfiguring G11C29/70
• CPC Class Codes: G06F 2212/205 Hybrid memory, e.g. using both volatile and non-volatile memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Techniques and systems are provided for tracking commands. Such methods and systems can include receiving a data access request in a controller coupled to (a) a non-volatile memory configured to store a set of physical data pages, and (b) a volatile memory configured to store a plurality of physical data page addresses, wherein each physical data page address corresponding to a physical data page in the set of physical data pages, and each physical data page address is accessed via a corresponding logical address in a set of logical addresses; accessing, by the controller based on the received data access request, a bitmap stored on the volatile memory, the bitmap including a set of bits, each bit configured to indicate a validity state of a different plurality of logical addresses in a set of logical addresses; and determining, via the controller, an invalid state of at least one of a selected (a) logical address, or (b) plurality of logical addresses, based on a bit in the bitmap.

Claims

1. A device, comprising:

a non-volatile memory configured to store a set of physical data pages;

a volatile memory configured to store (a) a plurality of physical data page addresses, wherein each physical data page address corresponding to a physical data page in the set of physical data pages, and each physical data page address is accessed via a corresponding logical address in a set of logical addresses; and

(b) a bitmap including a set of bits, each bit configured to indicate a validity state of a different plurality of logical addresses in the set of logical addresses; and

a controller coupled to the volatile memory and the non-volatile memory and configured to determine a validity state of a logical address by;

determining the validity state of a bit in a bitmap that represents a selected plurality of logical addresses that includes the logical address; and

determining the validity state of the logical address in the selected plurality of logical addresses.

2. The device of claim 1, wherein the controller is further configured to:

receive a request for retrieving data from the physical data pages corresponding to the physical data address accessed via the corresponding selected logical address; and

retrieve the requested data based on determination of a valid state of the bit from the bit map and a valid state of the selected logical address.

3. The device of claim 1, wherein the controller is further configured to:

receive a request for storing data to a physical data pages accessed via a second corresponding logical address;

store the requested data based on determination of an invalid state of the bit from the bit map; and

update a bit in the bitmap corresponding to the second logical address to a valid state.

4. The device of claim 1, wherein the controller is further configured to:

receive a request for storing data to the physical data pages accessed via the corresponding logical address; and

store the requested data based on determination of a valid state of the corresponding logical address.

5. The device of claim 1, wherein the controller is further configured to store the bitmap to non-volatile memory in the event of a power-loss.

6. The device of claim 1, wherein the set of logical addresses are partitioned into sequentially numbered subsets, wherein each subset comprising a fixed plurality of sequentially numbered logical addresses, wherein the bits in the bitmap are sequentially numbered bits, each bit corresponding to a different fixed plurality of sequentially numbered logical addresses.

7. The device of claim 1, wherein the non-volatile memory comprising a flash memory and wherein the controller comprising a flash memory controller.

8. The device of claim 1, wherein the controller is further configured to modify the bitmap based on the determination.

9. The device of claim 1, wherein an invalid state of a plurality of logical addresses corresponds to a trimmed state of the plurality of logical pages.

10. The device of claim 9, wherein the trimmed state of the selected logical address is indicated by at least one predetermined invalid value corresponding to (a) the selected logical address for a physical data page address, or (b) the corresponding bit in the bitmap.

11. A method comprising:

receiving a data access request in a controller coupled to (a) a non-volatile memory configured to store a set of physical data pages, and (b) a volatile memory configured to store a plurality of physical data page addresses, wherein each physical data page address corresponding to a physical data page in the set of physical data pages, and each physical data page address is accessed via a corresponding logical address in a set of logical addresses;

accessing, by the controller based on the received data access request, a bitmap stored on the volatile memory, the bitmap including a set of bits, each bit configured to indicate a validity state of a different plurality of logical addresses in a set of logical addresses; and

determining, via the controller, a valid state of a logical address by;

determining the validity state of a bit in a bitmap that represents a selected plurality of logical addresses that includes the logical address; and

determining the validity state of the logical address in the selected plurality of logical addresses.

12. The method of claim 11, wherein the received data access request is for retrieving data from the physical data pages corresponding to the physical data address accessed via the corresponding selected logical address;

wherein the method further comprising;

determining, by the controller, a valid state of the bit from the bit map and a valid state of the selected logical address; and

retrieving, by the controller, the requested data based on the determining the valid state of the bit from the bit map and the valid state of the selected logical address.

13. The method of claim 11, further comprising:

receiving, by the controller, a request for storing data to a physical data page accessed via a second logical address;

determining, by the controller, an invalid state of the bit from the bit map;

storing, by the controller, the requested data based on determination of an invalid state of the bit from the bit map; and

updating, by the controller, a bit in the bitmap corresponding to the second logical address to a valid state.

14. The method of claim 11, wherein the received data access request is for storing data to the physical data pages accessed via the corresponding logical address;

wherein the method further comprising;

receiving, in the controller, a request

determining, by the controller, a valid state of the corresponding logical address; and

storing, by the controller, the requested data based on the determining of the valid state of the corresponding logical address.

15. The method of claim 11, further comprising:

storing, by the controller, the bitmap to non-volatile memory in the event of a power-loss.

16. The method of claim 11, further comprising:

modifying, by the controller, the bitmap based on the determining the validity state of the selected logical address in the selected plurality of logical addresses.

17. The method of claim 11, wherein the set of logical addresses are partitioned into sequentially numbered subsets, wherein each subset comprising a fixed plurality of sequentially numbered logical page addresses, wherein the bits in the bitmap are sequentially numbered bits, each bit corresponding to a different fixed plurality of sequentially numbered logical page addresses.

18. A non-transitory computer readable medium having stored thereon instructions that when executed by a processor perform a method, including:

receiving a data access request in a controller coupled to (a) a non-volatile memory configured to store a set of physical data pages, and (b) a volatile memory configured to store a plurality of physical data page addresses, wherein each physical data page address corresponding to a physical data page in the set of physical data pages, and each physical data page address is accessed via a corresponding logical address in a set of logical addresses;

accessing, by the controller based on the received data access request, a bitmap stored on the volatile memory, the bitmap including a set of bits, each bit configured to indicate a validity state of a different plurality of logical addresses in a set of logical addresses; and

determining, via the controller, a valid state of a logical address by;

determining the validity state of a bit in a bitmap that represents a selected plurality of logical addresses that includes the logical address; and

determining the validity state of the logical address in the selected plurality of logical addresses.