Garbage collection schemes for index block
AssigneeApple Inc.
InventorsDaniel J. Post, Vadim Khmelnitsky
Life of this patent
Estimating the term…
Abstract
Systems and methods are provided for handling uncorrectable errors that may occur during garbage collection of an index page or block in non-volatile memory.
Claims18
A method for performing garbage collection of an index block, the index block including index pages that store logical-to-physical mappings of data pages, the method comprising:
- determining that an index page has an uncorrectable error during garbage collection of the index block, the uncorrectable error preventing the logical-to-physical mapping contained in the index page from being reconstructed in a new index block;
- accessing a data structure in volatile memory to determine if the data structure contains the logical-to-physical mapping of the index page;
- and
- if the data structure has the logical-to-physical mapping of the index page, reconstructing the index page using the logical-to-physical mapping from the data structure in a new index block.
A memory interface for accessing a non-volatile memory, the non-volatile memory comprising index blocks, each index block comprising index pages that map logical-to-physical addresses of data pages, the memory interface comprising:
- a bus controller for communicating with the non-volatile memory;
- and
- control circuitry operative to direct the bus controller to perform a garbage collection operation on an index block, the control circuitry further operative to:
- determine which index pages in the index block are valid index pages;
- for a valid index page, determine whether a data structure held in volatile memory has the logical-to-physical mappings of the valid index page;
- if the data structure has the logical-to-physical mappings of the valid index page, reconstruct the valid index page in a new index block using the logical-to-physical mappings from the data structure.
A method for performing garbage collection of an index block, the index block including index pages that store logical-to-physical mappings of data pages, the method comprising:
- determining a number of valid index pages in a first index block;
- determining, based on the number of valid index pages, whether to reconstruct the valid index pages by first accessing a tree data structure held in volatile memory or to reconstruct the valid index pages by first reading data in the valid index pages.
Dependencies are inferred from the claim text.