Managing data stored in a nonvolatile storage device

Patent metadata

Field	Value
Publication number	US-2016124668-A1
Application number	US-201514928897-A
Country	US
Kind code	A1
Filing date	Oct 30, 2015
Priority date	Oct 30, 2014
Publication date	May 5, 2016
Grant date	—

Abstract

A storage device may be configured to copy valid data units from a source memory area to a destination memory area according to a source-to-destination mapping. The source-to-destination mapping may be generated based on a ranking scheme that considers the number of valid data units being stored in each of a plurality of source pages storing the data.

First claim

1 - 20 . (canceled)

21 . An apparatus comprising:
a memory comprising a plurality of source storage pages and a plurality of destination storage pages; and control circuitry in communication with the memory, the control circuitry configured to:
rank the plurality of source storage pages based on numbers of valid data units stored in the plurality of source storage pages; and
map valid data units stored in the plurality of source storage pages to the plurality of destination storage pages based on the ranking.

22 . The apparatus of claim 21 , wherein the control circuitry is further configured to:
assign a plurality of source rankings to the plurality of source storage pages based on the ranking, the source rankings indicating numbers of valid data units stored in the plurality of source storage pages; and map the valid data units to the plurality of destination storages pages according to the source rankings assigned to the plurality of source storage pages.

23 . The apparatus of claim 21 , wherein the control circuitry is further configured to:
generate a source-to-destination mapping that maps the valid data units to the plurality of destination storage pages based on the ranking.

24 . The apparatus of claim 21 , wherein the control circuitry is further configured to:
select a number of highest-ranked source storage pages; and wherein, in order to map the valid data units, the control circuitry is configured to perform a first stage of mapping that maps valid data units stored in the selected number of highest-ranking source storage pages to the destination storage pages.

25 . The apparatus of claim 24 , wherein the control circuitry is further configured to:
assign a plurality of destination rankings to the plurality of destination storage pages, wherein each destination ranking of the plurality of destination rankings indicates a number of unmapped storage units of a respective destination storage page; and update the plurality of source rankings assigned to the plurality of source storage pages and the plurality of destination rankings assigned to the plurality of destination storage pages based on the first stage of mapping, wherein the update identifies remaining unmapped valid data units and unmapped destination storage units.

26 . The apparatus of claim 25 , wherein the control circuitry is further configured to:
in response to the update of the source rankings and the plurality of destination rankings, perform a second stage of mapping that maps remaining unmapped valid data units to the plurality of destination storage pages based on matches between the plurality of source rankings and the plurality of destination rankings.

27 . The apparatus of claim 26 , wherein the control circuitry is further configured to:
further update the plurality of source rankings assigned to the plurality of source storage pages and the plurality of destination rankings assigned to the plurality of destination storage pages based on the second stage of mapping, wherein the further update identifies further remaining unmapped valid data units and unmapped destination storage units; and in response to the further update of the source rankings and the plurality of destination rankings, perform a third stage of mapping that maps still remaining unmapped valid data units to the plurality of destination storage pages based on remaining highest-ranked source storage pages and remaining highest-ranked destination rankings.

28 . The apparatus of claim 24 , wherein the control circuitry is further configure to identify that the valid data units mapped during the first stage of mapping are each to be copied using an on-chip copy operation.

29 . The apparatus of claim 21 , wherein the control circuitry is further configured to, for source storage pages with the same source ranking, map valid data units stored in source storage pages storing valid data units in only one of the multiple planes before mapping valid data units stored in storage pages storing valid data units in the multiple planes.

30 . The apparatus of claim 21 , wherein the control circuitry is further configured to copy the valid data units to the plurality of destination pages according to the mapping.

31 . The apparatus of claim 21 , wherein the plurality of source storage pages have a lower bit-per-cell density than the plurality of destination storage pages.

32 . The apparatus of claim 21 , wherein the control circuitry is further configured to:
generate a plurality source ranking lists, each of the source ranking lists being associated with a different one of the plurality of source rankings; and initially populate the plurality of source ranking lists with source entries corresponding to the plurality of source storage pages, the plurality of source ranking lists initially populated with the source entries based on the ranking of the plurality of source storage pages.

33 . An apparatus comprising:
a memory comprising a plurality of source storage pages and a plurality of destination storage pages, the plurality of source storage pages storing a first set of valid data units and a second set of valid data units; and control circuitry in communication with the memory, the control circuitry configured to:
determine a set of source storage pages of the plurality of source storage pages based on a criterion for data stored in the plurality of source storage pages; and
map valid data units stored in the set of source storage pages to a set of destination storage pages of the plurality of destination pages, wherein the mapping corresponds to an on-chip-copy operation for each of the valid data units stored in the set.

34 . The apparatus of claim 33 , wherein the criterion comprises a highest number of valid data units stored among the plurality of source storage pages.

35 . The apparatus of claim 34 , wherein the set of source storage pages comprises a first set of source storage pages and the set of destination storage pages comprises a first set of destination storage pages, and wherein the control circuitry is further configured to:
determine a second set of source storage pages of the plurality of source storage pages based on a matching of source rankings of the second set of source storage pages to destination rankings of a second set of destination storage pages; and map valid data units stored in the second set of source storage pages to the second set of destination storage pages.

36 . The apparatus of claim 33 , wherein the control circuitry is further configured to communicate with the memory to have each of the valid data units stored in the set of source storage pages copied to the set of destination storage pages via the on-chip copy operation.

37 . A method comprising:
ranking, with control circuitry, a plurality of source locations and a plurality of destination locations, the ranking of the plurality of source locations being based on storage of valid data units and the ranking of the plurality of destination locations being based on storage availability; mapping, with the control circuitry, a first set of valid data units to the plurality of destination locations based on the ranking; after the mapping of the first set, re-ranking, with the control circuitry, the plurality of source locations based on the storage of valid data units and the plurality of destination locations based on the storage availability; and mapping, with the control circuitry, a second set of valid data units to the plurality of destination locations based on the re-ranking

Assignees

• Sandisk Technologies Inc

Inventors

• Inbar Karin
• Benner Yossi
• Grin Lola
• Lev Einat
• Naberezhnov Alexei

Classifications

• G06F2212/7208

  Multiple device management, e.g. distributing data over multiple flash devices · CPC title

• G06F2212/7209

  Validity control, e.g. using flags, time stamps or sequence numbers · CPC title

• G06F3/068

  Hybrid storage device · CPC title

• G06F12/0246

  in block erasable memory, e.g. flash memory · CPC title

• G06F3/0619 Primary

  in relation to data integrity, e.g. data losses, bit errors · CPC title