Adaptive deterministic grouping of blocks into multi-block units

Abstract

The present invention presents techniques for the linking of physical blocks of a non-volatile memory into composite logical structures or “metablocks”. After determining an initial linking of good physical blocks into metablocks, a record of the linking is maintained in the non-volatile memory where it can be readily accessed when needed. In one set of embodiments, the initially linking is deterministically formed according to an algorithm and can be optimized according to the pattern of any bad blocks in the memory. As additional bad blocks arise, the linking is updated using by replacing the bad blocks in a linking with good blocks, preferably in the same sub-array of the memory as the block that they are replacing.

1 . A method of operating a memory system including a controller and a non-volatile memory, wherein the non-volatile memory is comprised of a plurality of units of erase, the method comprising: 
 establishing a set of metablock linkings, each comprised of a plurality of units of erase, by which the controller accesses the non-volatile memory; and    storing a record of said metablock linkings in the non-volatile memory.    
     
     
         2 . The method of  claim 1 , wherein said record is a complete specification of the set of linkings in terms of units of erase.  
     
     
         3 . The method of  claim 1 , wherein said set of linkings is formed according to a rule and the record consists of those linkings that are exceptions to the rule.  
     
     
         4 . The method of  claim 1 , further comprising: 
 determining that a unit of erase in a first of said metablock linkings is defective;    updating the first metablock linking so that it no longer contains said defective unit of erase; and    storing a record of the updated linking in the non-volatile memory.    
     
     
         5 . The method of  claim 4 , wherein said updating comprises replacing the defective unit of erase with another one of said units of erase.  
     
     
         6 . The method of  claim 5 , wherein said another one of said units of erase is selected from a list of unlinked units of erase.  
     
     
         7 . The method of  claim 6 , wherein said list of unlinked units of erase is maintained in the non-volatile memory.  
     
     
         8 . The method of  claim 7 , further comprising: 
 subsequent to said replacing the defective unit of erase with another one of said units of erase, updating said list of unlinked units of erase.    
     
     
         9 . The method of  claim 5 , wherein said another one of said units of erase is selected from a unit of erase formerly belonging to another linking.  
     
     
         10 . The method of  claim 1 , further comprising: 
 maintaining a list of unlinked units of erase;    determining that one or more units of erase in a first of said metablock linkings is defective; and    adding the non-defective units of erase in the first metablock to the list of unlinked units of erase.    
     
     
         11 . The method of  claim 1 , further comprising: 
 determining that a unit of erase in a first of said metablock linkings is defective;    determining whether an alternate unit of erase is available for the defective unit of erase; and    in response to determining that an alternate unit of erase is not available, removing the first metablock from the set of metablock linkings.    
     
     
         12 . The method of  claim 1 , wherein said non-volatile memory comprises a plurality of quasi-independent arrays and each of the plurality of units of erase in a given one of said metablock linkings are from a different one of said quasi-independent arrays.  
     
     
         13 . The method of  claim 1 , wherein said non-volatile memory comprises a plurality of quasi-independent arrays and the plurality of units of erase in a given one of said metablock linkings are comprised of pairs of units of erase from the same quasi-independent array, wherein each of the pairs are from a different one of said quasi-independent arrays.  
     
     
         14 . The method of  claim 10 , wherein said quasi-independent arrays are on separate chips.  
     
     
         15 . The method of  claim 1 , wherein said record of said metablock linkings is stored in a portion of the non-volatile memory other than those assigned for user data.  
     
     
         16 . The method of  claim 1 , wherein each of said units of erase is comprised of a plurality of sectors and each of the sectors includes a data area and an overhead area, and wherein the record information for those units of erase containing data is maintained in their overhead area.  
     
     
         17 . The method of  claim 16 , wherein the record information for those units of erase without data is maintained in a portion of the non-volatile memory other than those assigned for user data.  
     
     
         18 . A method of operating a memory system including a controller and a non-volatile memory, the memory comprising at least two independently accessible subarrays, wherein the individual subarrays are divided into a plurality of non-overlapping physical structures, and wherein at least one physical structure from individual ones of said subarrays are linked to form a composite logical structure whereby the controller accesses the composite logical structure components together as a unit, the method comprising: 
 determining that a physical structure in said composite logical structure is defective; and    in response to said determining that a physical structure in said composite logical structure is defective, replacing said defective physical structure in said composite logical structure with an alternate physical structure while maintaining the non-defective ones of the physical structures linked to form said composite logical structure.    
     
     
         19 . The method of  claim 18 , wherein said physical structures are physical blocks.  
     
     
         20 . The method of  claim 18 , wherein said subarrays are formed on the same chip.  
     
     
         21 . The method of  claim 18 , wherein less than all of said subarrays are formed on the same chip.  
     
     
         22 . The method of  claim 18 , wherein a record of the linking of physical structures to form a composite logical structure is maintained in said memory and wherein said record is updated to reflect said replacing.  
     
     
         23 . The method of  claim 22 , wherein the linking is formed according to an algorithm and the record describes deviations from the algorithm.  
     
     
         24 . The method of  claim 22 , wherein the record describes the physical address of all of the physical structures in the linking.  
     
     
         25 . The method of  claim 24 , further comprising: 
 prior to said determining that a physical structure in said composite logical structure is defective, forming an initial linking of physical structures to form said composite logical structure, and wherein said replacing includes updating said linking.    
     
     
         26 . The method of  claim 25  said forming an initial linking comprises: 
 selecting the physical structures forming the composite logical structure from a pool of available physical structures.    
     
     
         27 . The method of  claim 25  said forming an initial linking comprises: 
 forming the composite logical structure according to an algorithm.    
     
     
         28 . A memory system including a controller and a non-volatile memory, wherein the non-volatile memory is comprised of a plurality of units of erase, wherein the controller accesses the non-volatile memory according to a set of metablock linkings, each comprised of a plurality of units of erase, wherein the controller establishes the set of metablock linkings in a deterministic manner.  
     
     
         29 . The memory system of  claim 28 , wherein the set of metablock linkings is established according to an algorithm.  
     
     
         30 . The memory system of  claim 29 , wherein metablock linkings not formed according to the rule are indicated by a flag.  
     
     
         31 . The memory system of  claim 30 , wherein the flag is maintained in the controller.  
     
     
         32 . The memory system of  claim 30 , wherein the flag is maintained in the non-volatile memory  
     
     
         33 . The memory system of  claim 29 , wherein the algorithm optimizes the set of linkings according to the pattern of defective blocks in the non-volatile memory.  
     
     
         34 . The memory system of  claim 29 , wherein the controller determines the pattern of defective blocks in the non-volatile memory based on a scan of the non-volatile memory.  
     
     
         35 . The memory system of  claim 28 , wherein the set of metablock linkings is established based on a random allocation.  
     
     
         36 . The memory system of  claim 28 , wherein the set of metablock linkings is updated in response to defects by replacing a defective block in a linking with non-defective block from a list of one or more non-defective blocks.  
     
     
         37 . The memory system of  claim 36 , wherein a record of the list of one or more non-defective blocks maintained in the non-volatile memory.  
     
     
         38 . The memory system of  claim 37 , wherein the record of the list of one or more non-defective blocks is cached in volatile memory of said controller by said controller.  
     
     
         39 . The memory system of  claim 28 , wherein a record of the set of metablock linkings is maintained in the non-volatile memory.  
     
     
         40 . The memory system of  claim 39 , wherein the record of the set of metablock linkings is cached in volatile memory of said controller by said controller.  
     
     
         41 . The memory system of  claim 39 , wherein an initial set of metablock linkings is established according to an algorithm and wherein the record of the set of metablock linkings lists only those linkings that do not conform to the algorithm.  
     
     
         42 . The memory system of  claim 41 , wherein the record of the set of metablock linkings lists only those units of erase that do not conform to the algorithm.  
     
     
         43 . A method of operating a non-volatile memory system having an array of memory storage elements organized in at least two planes, wherein the individual planes are divided into a plurality of non-overlapping blocks of storage elements wherein a block contains the smallest group of memory storage elements that are erasable together, and the individual blocks are divided into a plurality of pages of storage elements wherein a page is the smallest group of memory storage elements that are programmable together, comprising: 
 linking at least one block from individual ones of said at least two planes to form a metablock wherein the metablock components are erased together as a unit;    redirecting a metablock component block associated with a defective physical block to a spare physical block in the same plane if a spare physical block is available in the same plane;    assigning the metablock components not associated with the defective physical block to a spare block area if no spare physical block is available in the same plane; and    updating a defect map structure, wherein the defect map structure includes an entry corresponding to the metablock.