LBA bitmap usage
AssigneeApple Inc.
InventorsDaniel J. Post, Nir Jacob Wakrat, Vadim Khmelnitsky
Life of this patent
Estimating the term…
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.
Claims13
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.
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;
- in response to determining that the tree does comprise the logical-to-physical mapping corresponding to the LBA, update the tree to reflect the unmapped LBA only if tree memory usage decreases with the update;
- 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.
Dependencies are inferred from the claim text.