LBA BITMAP USAGE

• US 20130151754A1
• Filed: 12/12/2011
• Published: 06/13/2013
• Est. Priority Date: 12/12/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Post, Daniel J., Wakrat, Nir Jacob, Khmelnitsky, Vadim
• Granted Patent: US 9,069,657 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• 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
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers

Abstract

Systems and methods are disclosed for logical block address (“LBA) bitmap usage for a system having non-volatile memory (“NVM”). A bitmap can be stored in volatile memory of the system, where the bitmap can store the mapping statuses of one or more logical addresses. By using the bitmap, the system can determine the mapping status of a LBA without having to access the NVM. In addition, the system can update the mapping status of a LBA with minimal NVM accesses. By reducing the number of NVM accesses, the system can avoid triggering a garbage collection process, which can improve overall system performance.

Claims

1. A method for unmapping logical block addresses (“

LBAs”

) for a system comprising a non-volatile memory (“

NVM”

), the method comprising;

storing mapping statuses of a plurality of LBAs in a bitmap stored in volatile memory;

receiving a request from a file system to unmap a first LBA;

changing a mapping status or the first LBA to unmapped by only updating the bitmap; and

decreasing a validity counter for a super block corresponding to the first LBA.

2. The method of claim 1, wherein each entry of the bitmap corresponds to one LBA.

3. The method of claim 1, wherein each entry of the bitmap corresponds to multiple LBAs.

4. The method of claim 1, further comprising receiving information associated with mapping statuses of the plurality of LBAs during system boot-up from the file system.

5. The method of claim 1, further comprising obtaining mapping statuses of the plurality of LBAs by scanning the NVM.

6. The method of claim 1, further comprising:

receiving a read request from the file system to read a second LBA;

consulting an entry of the bitmap associated with the second LBA;

determining whether the entry indicates that the second LBA is unmapped; and

in response to determining that the entry indicates that the second LBA is unmapped, transmit information to the file system, indicating that the second LBA does not have associated user data.

7. The method of claim 6, further comprising:

in response to determining that the entry indicates that the second LBA is not unmapped, consult an index page of the NVM to locate user data associated with the second LBA; and

transmit the user data to the file system.

8. A system comprising:

non-volatile memory (“

NVM”

);

volatile memory comprising;

a plurality of validity counters associated with a plurality of super blocks of the NVM,

a tree comprising a plurality of entries, wherein the tree provides a mapping between a plurality of logical block addresses (“

LBAs”

) and physical addresses of the NVM; and

a bitmap for storing mapping statuses of the plurality or LBAs; and

memory interface comprising control circuitry operative to;

receive a request to unmap a LBA of the plurality of LBAs;

consult the bitmap to determine whether the LBA is unmapped;

in response to determining that the LBA is not unmapped, unmap the LBA in the bitmap;

update at least one of the plurality of validity counters by consulting the tree; and

update the tree to reflect the unmapped LBA only if tree memory usage decreases with the update.

9. The system of claim 8, wherein the control circuitry is operative to:

locate an entry of the tree corresponding to the LBA; and

update a physical address in the entry associated with the LBA to a pre-determined token value.

10. The system of claim 8, wherein the control circuitry is operative to determine that updating the tree produces a net reduction in a total number of entries of the tree.

11. The system of claim 8, wherein in response to determining that the LBA is unmapped, the control circuitry is operative to transmit information to the file system indicating that the LBA is already unmapped.

12. The system of claim 8, wherein the control circuitry is operative to:

locate an entry of the tree corresponding to the LBA;

determine a super block that stores data associated with the LEA using the entry; and

decrement a validity counter of the plurality of validity counters associated with the super block.

13. The system of claim 8, wherein each entry of the bitmap corresponds to multiple LBAs.

14. The system of claim 13, wherein the control circuitry is operative to:

determine that a mapping status of an entry of the bitmap is an unknown status;

consult at least one of a tree and at least one index page to determine a mapping status of each LBA associated with the entry.

15. The system of claim 8, wherein the control circuitry is operative to:

initialize the bitmap such that each entry of the bitmap corresponds to one LBA; and

increase the number of LBAs corresponding to each entry of the bitmap if a number of entries of the bitmap that have unknown statuses is less than a pre-determined threshold.

16. The system of claim 8, wherein the control circuitry is operative to initialize the bitmap such that each entry of the bitmap corresponds to a pre-determined number of LBAs.

18. The memory interface of claim 16, wherein the control circuitry is operative to load the index page into an index table cache.

19. The memory interface of claim 16, wherein the control circuitry is operative to:

determine a super block of the NVM that is associated with the LBA by consulting the loaded index page; and

decrement a validity counter associated with the super block, wherein the validity counter is stored in the volatile memory.

20. The memory interface of claim 16, wherein in response to determining that the tree comprises the logical-to-physical mapping corresponding to the LBA, the control circuitry is operative to:

determine a super block of the NVM that is associated with the LBA using the tree; and

decrement a validity counter associated with the super block, wherein the validity counter is stored in the volatile memory.

17. A memory interface for accessing index pages in a non-volatile memory (“

NVM”

), the memory interface comprising control circuitry operative to;

receive a request to unmap a logical block address (“

LBA”

) of a plurality of LBAs;

unmap the LBA in a bitmap stored in volatile memory;

determine whether a tree stored in volatile memory comprises a logical-to-physical mapping corresponding to the LBA; and

in response to determining that the tree does not comprise the logical-to-physical mapping corresponding to the LBA, load an index page associated with the LBA from the NVM.

21. A method for faster data garbage collection (“

GC”

), the method comprising;

determining to perform garbage collection on a data block of a non-volatile memory (“

NVM”

);

loading a block table-of-contents (“

TOC”

) stored in the data block;

comparing a bitmap stored in volatile memory with the block TOC;

determining a subset of logical addresses of the data block that are mapped based on the comparison; and

performing garbage collection for only user data stored in the data block that are associated with the subset of logical addresses.

22. The method of claim 21, wherein the bitmap stores mapping statuses for a plurality of logical block addresses (“

LBAs”

).

23. The method of claim 21, further comprising locating the user data by accessing only index pages stored in the NVM corresponding to the subset of logical addresses.

24. The method of claim 23, further comprising:

for each logical address of the subset of logical addresses, accessing an index page associated with the logical address;

determining a physical address of the data block corresponding to the logical address based on the index page; and

copying user data from the physical address to a different data block, of the NVM.

25. The method of claim 21, further comprising:

for each logical address of the subset of logical addresses, consulting a tree stored in volatile memory to determine whether a logical-to-physical mapping exists for the logical address;

in response to determining that the logical-to-physical mapping does not exist for the logical address, accessing an index page associated with the logical address;

determining a physical address of the data block corresponding to the logical address based on the index page; and

copying user data from the physical address to a different data block of the NVM.

26. The method of claim 25, further comprising:

in response to determining that the logical-to-physical mapping exists for the logical address, determining the physical address of the data block corresponding to the logical address using the tree; and

copying the user data from the physical address to the different data block of the NVM.