USOO7139864B2
`
`(12) United States Patent
`Bennett et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,139,864 B2
`Nov. 21, 2006
`
`(54) NON-VOLATILE MEMORY AND METHOD
`WITH BLOCK MANAGEMENT SYSTEM
`(75) Inventors: Alan David Bennett, Edinburgh (GB);
`Alan Douglas Bryce, Edinburgh (GB);
`Sergey Gorobets, Edinburgh (GB);
`Alan Welsh Sinclair, Falkirk (GB);
`Peter John Smith, Scotland (GB)
`
`(*) Notice:
`
`(73) Assignee: SanDisk Corporation, Milpitas, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 539 days.
`(21) Appl. No.: 10/750,155
`
`22) Filed:
`(22) File
`(65)
`
`Dec. 30, 2003
`ec. 5U,
`Prior Publication Data
`
`US 2005/O14436O A1
`
`Jun. 30, 2005
`
`(51) Int. Cl.
`(2006.01)
`G06F 12/00
`(52) U.S. Cl. ....................... 711/103; 711/100; 711/102;
`711/165; 711/200; 711/203; 711/209; 365/185.11;
`365/230.03
`(58) Field of Classification Search ........ 711/102-103,
`711/165
`See application file for complete search history.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`8, 1991 Harari
`5,043,940 A
`5,070,032 A 12/1991 Yuan et al.
`5,095,344 A
`3, 1992 Harari
`5,172,338 A 12/1992 Mehrotra et al.
`5,313,421 A
`5, 1994 Guterman et al.
`5,315,541 A
`5, 1994 Harari et al.
`5,343,063 A
`8, 1994 Yuan et al.
`5,367.484 A 1 1/1994 Alexander et al.
`5,404,485 A
`4, 1995 Ban ........................... T11 202
`5,532.962 A
`7, 1996 Auclair et al.
`
`5,570,315 A 10/1996 Tanaka et al.
`5,661,053 A
`8, 1997 Yuan
`5,742,934. A
`4, 1998 Shinohara ................... T11 103
`37. A
`3.
`th
`sy
`al
`5,774,397 A
`6/1998 Endoh et al.
`(Continued)
`FOREIGN PATENT DOCUMENTS
`O887732
`12/1998
`
`EP
`
`(Continued)
`OTHER PUBLICATIONS
`USPTO, “Office Action,” mailed in related U.S. Appl. No.
`10/841,118, filed Jun. 16, 2006, 29 pages.
`(Continued)
`Primary Examiner Matthew Kim
`Assistant Examiner—Zhuo H. Li
`(74) Attorney, Agent, or Firm Parsons Hsue & de Runtz
`LLP
`
`(57)
`
`ABSTRACT
`
`A non-volatile memory system is organized in physical
`groups of physical memory locations. Each physical group
`(metablock) is erasable as a unit and can be used to store a
`logical group of data. A memory management system allows
`for update of a logical group of data by allocating a
`metablock dedicated to recording the update data of the
`logical group. The update metablock records update data in
`the order received and has no restriction on whether the
`recording is in the correct logical order as originally stored
`(sequential) or not (chaotic). Eventually the update meta
`block is closed to further recording. One of several processes
`will take place, but will ultimately end up with a fully filled
`metablock in the correct order which replaces the original
`metablock. In the chaotic case, directory data is maintained
`in the non-volatile memory in a manner that is conducive to
`frequent updates. The system Supports multiple logical
`groups being updated concurrently.
`
`32 Claims, 29 Drawing Sheets
`
`
`
`Request to write sector in L3 (Logical Groupx)
`
`does open update NO
`
`is number of No
`update blocks
`> Ca
`
`chaotic
`update block
`
`sequential
`update block
`
`------------
`
`YES
`
`Close
`sequential
`update block
`for LG
`
`54
`
`539
`
`550;
`
`Chastle Cissural
`No.
`sturber of
`sso 540
`distinct logica:
`sectors s.c.
`consolidate. E .
`chaotic update
`update block
`block for LG,
`for LG
`
`KIOXIA Ex-1007, Page 1
`
`

`

`US 7,139,864 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`8/1998 Lee et al.
`5,798,968 A
`1/1999 Matthews et al. .......... T11 165
`5,860,124 A
`3, 1999 Lee et al.
`5,890,192 A
`5, 1999 Takeuchi et al.
`5,903,495 A
`5, 1999 Estakhri et al.
`5,907,856 A
`6, 1999 So et al.
`5,909,449 A
`7, 1999 Lee et al.
`5,930,167 A
`8, 1999 Ban
`5.937,425 A
`1/2000 Eitan
`6,011,725 A
`3, 2000 Estakhri et al.
`6,034,897 A
`4/2000 Takeuchi et al.
`6,046,935 A
`9, 2000 Estakhri et al.
`6,125,435 A
`6,141,249 A 10, 2000 Estakhri et al.
`6,222,762 B1
`4/2001 Guterman et al.
`6,226,728 B1
`5, 2001 See et al.
`6,272.610 B1
`8/2001 Katayama et al.
`6,377,500 B1
`4/2002 Fujimoto et al.
`6,401,160 B1
`6/2002 See et al.
`6.421,279 B1
`7/2002 Tobita et al.
`6.426,893 B1
`7/2002 Conley et al.
`6,456,528 B1
`9, 2002 Chen
`6,490,649 B1
`12/2002 Sinclair
`6,522,580 B1
`2/2003 Chen et al.
`6,563,734 B1
`5, 2003 Taki
`6,567,307 B1
`5/2003 Estakhri ................ 365,185.11
`6,591,330 B1
`7/2003 Lasser
`6,725,321 B1
`4/2004 Sinclair et al.
`6,763,424 B1* 7/2004 Conley ....................... 711/103
`6,871,259 B1
`3/2005 Hagiwara et al. ........... T11 103
`6,895,464 B1
`5, 2005 Chow et al.
`6,898,662 B1
`5, 2005 Gorobets
`2002/0099904 A1
`7/2002 Conley
`2003.0053334 A1
`3/2003 Chen
`2003/0065899 A1
`4/2003 Gorobets .................... 711/165
`2003.0109093 A1
`6, 2003 Harari et al.
`2003/0110343 A1
`6, 2003 Masato et al.
`2004/O103241 A1
`5/2004 Chang et al. ............... T11 103
`2005, 0141312 A1
`6, 2005 Sinclair et al.
`2005, 0141313 A1
`6, 2005 Gorobets et al.
`2005/0143365 A1
`6/2005 Gorobets et al.
`2005/0144.357 A1
`6, 2005 Sinclair
`2005. O144358 A1
`6/2005 Conley et al.
`2005. O144363 A1
`6, 2005 Sinclair
`2005. O144367 A1
`6, 2005 Sinclair
`2005, 0166087 A1
`7/2005 Gorobets
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`JP
`WO
`
`O 977 121 A2
`1424631 A1
`5314019
`
`2, 2000
`6, 2004
`11, 1993
`8, 2000
`
`WO O2/O58074 A2
`WO
`WO O3,O27828
`WO
`WO O3,O29951 A2
`WO
`WO WO2004/04.0457 A1
`WO WO2004/04O458 A1
`WO WO2004/04.0459 A1
`WO WO2004/040578 A1
`
`7, 2002
`4/2003
`4, 2003
`5, 2004
`5, 2004
`5, 2004
`5, 2004
`
`OTHER PUBLICATIONS
`
`USPTO, “Office Action,” mailed in related U.S. Appl. No.
`10/749,189, filed Apr. 28, 2006, 13 pageS.
`EPO/ISA, "Notification of Transmittal of the International Search
`Report and the Written Opinion of the International Searching
`Authority, or the Declaration' mailed in related PCT/US2004/
`043762 (published as WO 2005/066793 A2) on Apr. 4, 2006, 14
`pages.
`Taiwanese Patent Office, “Preliminary Notice of Rejection of the
`IPO,” mailed in related Taiwanese patent application No.
`093141438 on Mar. 17, 2006, 2 pages.
`EPO/ISA, “Invitation to Pay Additional Fees, Communication
`Relating to the Results of the Partial International Search Report'.
`mailed in related International Application No. PCT/US2004/
`043762 on Dec. 8, 2005, 5 pages.
`EPO/ISA, "Notification of the Transmittal of the International
`Search Report and the Written Opinion of the International Search
`ing Authority, or the Declaration', mailed in related International
`Application No. PCT/US2004/043377 on Dec. 2, 2005, 10 pages.
`Bennett et al., “Scratch Pad Block”, U.S. Appl. No. 11/016,285,
`filed Dec. 16, 2004, 55 pages.
`Chang, Li-Pin et al., “An Adaptive Striping Architecture for Flash
`Memory Storage Systems of Embedded Systems'. Proceedings of
`the Eighth IEEE Real-Time and Embedded Technology and Appli
`cations Symposium, Sep. 24, 2002, pp. 187-196.
`EPO/ISA, "Notification of Transmittal of the International Search
`Report and the Written Opinion of the International Searching
`Authority, or the Declaration', mailed in related PCT/US2004/
`043597 on Aug. 8, 2005, 12 pages.
`EPO/ISA, "Notification of Transmittal of the International Search
`Report and the Written Opinion of the International Searching
`Authority, or the Declaration', mailed in related PCT/US2004/
`043680 on Sep. 23, 2005, 18 pages.
`ISA/EPO, “Communication Relating to the Results of the Partial
`International Search, mailed in related PCT/US2004/043680 on
`Jul. 5, 2005, 3 pages.
`EPO/ISA, "Notification of Transmittal of the International Search
`Report and the Written Opinion of the International Searching
`Authority, or the Declaration', mailed in related PCT/US2004/
`043692 on May 4, 2005, 9 pages.
`Eitan et al., “NROM: A Novel Localized Trapping, 2-Bit Nonvola
`tile Memory Cell.” IEEElectron Device Letters, vol. 21, No. 1, Nov.
`2000, pp. 543-545.
`* cited by examiner
`
`KIOXIA Ex-1007, Page 2
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 1 of 29
`
`US 7,139,864 B2
`
`
`
`MEMORY SYSTEM20
`
`Controller 100
`
`Processor 120
`
`Optional
`CoProcessor 121
`
`Optional
`Programmable
`Nonvolatile Memory
`124
`
`Flash Memory 200
`
`FIG. 1
`
`KIOXIA Ex-1007, Page 3
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 2 of 29
`
`US 7,139,864 B2
`
`
`
`HOST 10
`
`Application
`
`OS/
`File System
`
`Clusters(Logical sectors)
`
`Host-side Memory Manager (Optional)
`
`Logical sectors
`
`MEMORY SYSTEM2O
`
`Flash Memory 200
`
`Memory-side Memory
`Manager
`
`Logical to Physical
`Address
`Translation
`
`Update Block
`Manager
`
`Erased Block
`Manager
`
`Metablock Link
`Manager
`
`FIG. 2
`
`KIOXIA Ex-1007, Page 4
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 3 of 29
`
`US 7,139,864 B2
`
`Logical Group () LG,
`
`0 ||
`
`1
`
`...
`
`I k
`
`k+1 ...
`
`Physical Group
`(Metablock)
`
`(ii) MB, 0
`
`1
`
`...
`
`I k
`
`k+1 ...
`
`(iii) MB, k k+1. N-1
`h
`Page Tag
`
`0
`
`1
`
`N-1
`
`N-1
`
`k-1
`
`Logical Group
`
`
`
`Physical Group
`(Metablock)
`
`FIG. 3A
`
`Logical to
`Physical
`Directories
`
`FIG. 3B
`
`KIOXIA Ex-1007, Page 5
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 4 of 29
`
`US 7,139,864 B2
`
`PHYSICAL GROUP's ALIGNMENT WITH MINIMUM ERASE UNITs
`
`
`
`MB
`
`Min. Erase Unit O
`
`1
`
`Min. Erase Unit 1
`
`s.
`
`s. To so,
`
`Min. Erase Unit P-1
`
`serviserum sp.,
`
`(N = PM)
`
`Sector O
`
`overhead
`
`data -
`
`Sector N-1
`
`F.G. 4
`
`KIOXIA Ex-1007, Page 6
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 5 Of 29
`
`US 7,139,864 B2
`
`MEMORY 200
`Chip 0
`Plane OO Plane O1 Plane O2
`
`...
`
`. . . . . . . . . . . . .
`Plane OW
`Plane ZO
`
`Chip Z
`
`
`
`FIG. 5A
`
`MEU
`
`MEU
`
`FIG. 5B
`
`FIG. 5C
`
`KIOXIA Ex-1007, Page 7
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 6 of 29
`
`US 7,139,864 B2
`
`Logical Sectors
`
`- - - - - - - - - - -
`CONTROLLER 100
`
`HOST INTERFACE 110
`
`LOGICAL TO PHYSICAL
`ADDRESS TRANSLATION
`
`
`
`140
`READ
`
`132
`
`WRITE
`
`Allocation
`
`134
`
`136
`
`Block List
`(ABL)
`Cleared
`Block List
`(CBL)
`- 170
`INITIALIZATION
`
`
`
`180
`
`
`
`Flash Memory200
`Group Address 21 O
`Tables (GAT)
`
`Chaotic Block
`Indices (CBI)
`
`UPDATE BLOCK MANAGER
`152
`
`Sequential Update
`
`154
`
`Chaotic Update
`
`
`
`
`
`METABLOCK LINK MANAGER
`
`170
`
`- - - - - - -
`
`KIOXIA Ex-1007, Page 8
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 7 Of 29
`
`US 7,139,864 B2
`
`
`
`Original
`Block
`
`Host Write
`Operation
`#1
`
`|
`
`Operation
`
`Update Block
`(Sequential)
`
`- - as as as as as -
`
`
`
`SEQUENTIAL. UPDATE
`Example
`
`FIG. 7A
`
`KIOXIA Ex-1007, Page 9
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 8 of 29
`
`US 7,139,864 B2
`
`
`
`Original
`Block
`
`
`
`- - -
`
`HOSt Write
`
`- - -
`
`- - - - - - - - - - - - - - - -
`
`Host Write
`
`Host Write
`
`Update Block
`(Sequential)
`
`
`
`2 Key: %
`
`CHAOTIC UPDATE
`(NONSEQUENTIAL)
`Example
`
`FIG. 7B
`
`KIOXIA Ex-1007, Page 10
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 9 Of 29
`
`US 7,139,864 B2
`
`
`
`Original
`Block
`
`Host Write
`Operation
`
`- - - - - - - - - - - - - - -
`| HOSt Write
`Padding
`Operation
`operation
`
`Update Block
`(Sequential)
`
`- - - - - - - -
`
`Key:
`
`
`
`%5% Erased
`
`
`
`
`
`FORCED SEGUENTIAL
`UPDATE
`Example
`
`FIG. 8
`
`KIOXIA Ex-1007, Page 11
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 10 of 29
`
`US 7,139,864 B2
`
`in a nonvolatile memory organized into blocks, each block
`partitioned into memory units that are erasable, each memory unit
`for storing a logical unit of data that are erasable together
`Organizing data into logical groups, each logical group partitioned
`into logical units
`Storing all logical units of a given logical group LG. among
`memory units of a first block according to a first order
`
`Request to write logical unit in LG.
`
`Storing logical unit to a second block dedicated to the given
`logical group acCording to a Second Order
`
`Does a predetermined closure condition exists?
`
`
`
`
`
`
`
`ls Second Order similar to first Order?
`
`
`
`
`
`
`
`
`
`NO
`
`Consolidating onto a third
`block according to the first
`Order a latest version of each
`logical unit of the given logical
`group gathered from the first
`and Second blocks
`
`
`
`260
`
`262
`264
`
`27O
`
`272
`
`274
`
`276
`
`290
`
`Replacing the first block with
`the Second block
`
`Replacing the first block with
`the third block
`
`292
`
`
`
`299
`
`
`
`
`
`
`
`
`
`FIG. 9
`
`KIOXIA Ex-1007, Page 12
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 11 of 29
`
`US 7,139,864 B2
`
`Request to write sector in LG. (Logical Group x)
`
`
`
`
`
`
`
`ls number of
`update blocks
`> CA?
`
`Does open update
`block for LG exist?
`ls Update block
`sequential?
`
`ls sector sequential?
`
`ls address jump > N
`C?
`ls number of
`unfilled phys.
`Sectors > CP
`
`Convert to
`chaotic
`update block
`
`Write padding
`SectOrs
`
`Close
`sequential
`update block
`
`Close least
`active among
`update blocks
`
`
`
`
`
`- - - - - - - - - - - - - - - - - - - - -
`
`Chaotic Closure
`
`ls number of
`distinct logical
`Sectors > C?
`
`
`
`Consolidate
`chaotic update
`block for LG
`
`NO
`
`560
`
`540
`
`
`
`Compact
`chaotic
`update block
`for LG
`
`YES
`
`Close
`sequential
`update block
`for LG
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`KIOXIA Ex-1007, Page 13
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 12 of 29
`
`US 7,139,864 B2
`
`Consolidation
`
`550
`
`Allocate a new update block
`Gather latest version of each logical sector among the
`chaotic update block and its associated original block
`Record the gathered sectors onto the new update block in
`logically sequential order to form an intact block
`Replace the original block with the intact block
`
`Erase the closed out update block and the original block
`
`551
`
`552
`
`554
`
`556
`
`558
`
`FIG. 1 1A
`
`
`
`Compaction
`
`Allocate a new update block
`Gather latest version of each logical sector among the
`existing chaotic update block to be closed out
`Record the gathered sectors onto the new update block to
`form a new update block having Compacted sectors
`Replace the existing update block with the new update
`block having Compacted sectors
`Erase the closed out update block
`
`561
`
`562
`
`564
`
`566
`
`568
`
`FIG. 11B
`
`KIOXIA Ex-1007, Page 14
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 13 Of 29
`
`US 7,139,864 B2
`
`
`
`filling
`
`Sequential
`host Write
`
`SEOUENTIAL
`UPDATE
`
`Consolidation
`
`
`
`sequential
`host Write
`
`
`
`non-sequential
`host Write
`
`
`
`
`
`Compaction
`
`CHAOTIC
`UPDATE
`
`LOGICAL GROUP STATES
`
`F.G. 12A
`
`KIOXIA Ex-1007, Page 15
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 14 of 29
`
`US 7,139,864 B2
`
`
`
`LOGICAL
`GROUP STATE
`
`w
`DESCRIPTION
`
`Intact
`
`Complete Logical Group in logically sequential order in a
`single metablock
`
`UnWritten
`
`No portion of the Logical Group has ever been written
`
`Sequential
`Update
`
`An update segment of the Logical Group is Written to an update
`block without changing its existing sequential nature
`
`Chaotic Update
`
`An update segment of the Logical Group is written to an update
`block in logically non-sequential order
`
`FIG. 12B
`
`KIOXIA Ex-1007, Page 16
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 15 Of 29
`
`US 7,139,864 B2
`
`
`
`eraSUre
`
`CHAOTIC
`UPDATE
`
`
`
`Non-sequential
`Write o copy
`
`SEOUENTIAL
`UPDATE
`
`
`
`last in group
`Sequential write or copy
`
`eaSUe
`
`Sector superseded
`
`PHYSICAL METABLOCK STATES
`
`FIG. 13A
`
`KIOXIA Ex-1007, Page 17
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 16 of 29
`
`US 7,139,864 B2
`
`
`
`METABLOCK
`STATE
`
`DESCRIPTION
`
`All the SectOrS in the metablock are erased
`
`Sequential
`Update
`
`The metablock is partially written with sectors in logically
`Sequential Order, possibly using page tag. All the sectors
`belong to the same logical group.
`
`Non-Sequential
`(Chaotic) Update
`
`The metablock is partially or fully written with sectors in logically
`non-sequential order. Any sector can be written more than
`once. All sectors belong to the same logical group
`
`Intact
`
`The metablock is fully written in logically sequential order,
`pOSSibly using page tag
`
`Original
`9
`
`The metablock was previously Intact but at least one sector has
`been made obsolete by a host data update
`
`FIG. 13B
`
`KIOXIA Ex-1007, Page 18
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 17 Of 29
`
`US 7,139,864 B2
`
`
`
`Operation
`
`Logical Group
`Transitions
`
`Physical Metablock Transitions
`
`(A)
`First Write
`
`(B)
`First Intact
`
`FIGs. 14(A)-14(B)
`
`KIOXIA Ex-1007, Page 19
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 18 Of 29
`
`US 7,139,864 B2
`
`
`
`Operation
`
`Logical Group
`Transitions
`
`Physical Metablock Transitions
`
`(C)
`First
`Chaotic
`
`(D)
`First
`Compact
`ion
`
`(E)
`First
`Consolidat
`ion
`
`Original block
`
`update block
`
`FIGs. 14(C)-14(E)
`
`KIOXIA Ex-1007, Page 20
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 19 Of 29
`
`US 7,139,864 B2
`
`
`
`Operation
`
`Logical Group
`Transitions
`
`Physical Metablock Transitions
`
`original block
`
`update block
`
`(F)
`Sequential
`Write
`
`(G)
`Sequential
`Fi
`
`(H)
`Non
`sequential
`Write
`
`FIGs. 14(F)-14(H)
`
`KIOXIA Ex-1007, Page 21
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 20 of 29
`
`US 7,139,864 B2
`
`
`
`Operation
`
`Logical Group
`Transitions
`
`Physical Metablock Transitions
`
`original
`
`old chaotic
`
`new chaotic
`
`old chaotic
`
`new chaotic
`
`(J)
`Consolidat
`ion
`
`FIGs. 14(I)-14(J)
`
`KIOXIA Ex-1007, Page 22
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 21 of 29
`
`US 7,139,864 B2
`
`-610
`Allocation Block List (ABL) (in Controller RAM)
`- - - - - - - - - - - - - - - - - - - - - - - -
`aa- a--
`
`Seq/
`
`Open Update Block List 614
`ii of Sectors
`
`Page
`
`Closed Update Block List 616
`
`LG | MB
`
`PageTag
`
`MB,
`
`KIOXIA Ex-1007, Page 23
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 22 of 29
`
`US 7,139,864 B2
`
`Chaotic Block Index (CBI) Sector
`
`Chaotic Block Index
`
`Chaotic Block Info
`
`CB Sector index
`
`F.G. 1.6A
`
`
`
`CBI Block 620
`CB Sector for LGo
`CBI Sector for LG,
`CB Sector for LG
`
`CB Sector for LG,
`
`CB Sector for LG, (latest version)
`CB Sector for LG
`CB Sector for LG,
`CB Sector for LG, (last written))
`
`unWritten
`
`FIG. 16B
`
`KIOXIA Ex-1007, Page 24
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 23 Of 29
`
`US 7,139,864 B2
`
`Chaotic Sector Lookup (Logical Group, logical sector)
`
`Begin locating a given logical sector of a given Logical Group
`
`
`
`Locate the last written CBI sector in CBI block
`
`Locate the chaotic update block or original block associated with
`the given logical group by looking up the Chaotic Block info
`field of the last Written CB Sector
`
`
`
`ls the last Written CBI sector directed to given logical group?
`
`650
`
`652
`
`654
`
`658
`
`Locate the CB Sector for the given logical group by looking up
`the Sector Index field of the last written CB Sector
`
`
`
`
`
`
`
`
`
`Locate the given logical sector among either the chaotic block or
`the original block by looking up the Chaotic Block Index field
`Of the located CB Sector
`
`662
`
`FIG. 16C
`
`KIOXIA Ex-1007, Page 25
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 24 of 29
`
`US 7,139,864 B2
`
`Chaotic Sector Lookup (Logical Group, Subgroup, logical sector)
`
`Partition each Logical Group into multiple subgroups and assign
`a CBI sector to each subgroup
`
`Begin locating a given logical sector of a given subgroup of a
`given logical group
`
`Locate the last written CB sector in the CBI block
`
`Locate the chaotic update block or original block associated with
`the given Subgroup by looking up the Chaotic Block Info field
`Of the last Written CBI Sector
`
`ls the last written CBI sector directed to given logical group?
`
`670
`
`68O
`
`682
`
`684
`
`YES
`N 686
`
`Locate the last Written of the multiple CBI sectors for the given
`logical group by looking up the indirect Sector Index field of
`the last Written CB Sector
`
`690
`
`At least a CB sector associated with one of the subgroups for
`the given logical group has been located
`
`691
`YES
`ls the located CBI sector directed to the given subgroup? N
`
`692
`
`Locate the CBI sector for the given subgroup by looking up the
`Direct Sector field of the Current CB Sector located
`
`Locate the given logical sector among either the chaotic block or
`the Original block by looking up the Chaotic Block index field
`of the CBI sector for the given subgroup
`
`694
`
`696
`
`FIG. 16D
`
`
`
`
`
`
`
`
`
`
`
`KIOXIA Ex-1007, Page 26
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 25 Of 29
`
`US 7,139,864 B2
`
`CBI Block
`
`Chaotic ;
`Chaotic : Block
`Sector index
`Info
`:
`Block Index :
`: Direct : Indirect
`
`62O
`?
`
`Last Written
`CB Sector
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`7OO
`
`
`
`Logical
`Group
`Logical
`Subgroup f------
`for "
`B (B.)
`
`- - - - - - -
`
`C
`
`D
`
`Chaotic
`Update
`
`704
`
`E (C,j) (valid)
`
`ast SectOr
`
`Chaotic Block Indexing Structure
`FIG. 16E
`
`KIOXIA Ex-1007, Page 27
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 26 of 29
`
`US 7,139,864 B2
`
`Group Address Table (GAT) sector
`GAT Entries
`GAT Sector Index
`
`GAT entry for LG,
`Metablock
`Page
`Relinked
`Number
`Tag
`Flag
`
`FIG. 17A
`
`GAT Block 720
`GAT Sector 0 (LG - LG.)
`GAT Sector 1 (LG-LG)
`GAT Sector 2 (LG-LG)
`
`GAT Sector 45 (obsolete)
`
`GAT Sector 45 (latest version)
`GAT Sector 55
`GAT Sector 35
`GAT Sector 56 (last written)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`s %
`
`FIG. 17B
`
`KIOXIA Ex-1007, Page 28
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 27 Of 29
`
`US 7,139,864 B2
`
`Allocated
`Control Blocks
`
`Updated Block
`Addr. to GAT
`
`Block Addr.
`from GAT
`
`Erased
`Control Blocks
`
`
`
`
`
`
`
`616
`Closed Update
`BlockS
`
`
`
`1617
`
`(CBL)
`Cleared
`Block List
`
`
`
`Backup of
`ABL after
`each Fill (JE
`
`Fil (e.g., when no blocks
`available in ABL)
`
`Empty
`
`--------------------- -
`
`
`
`
`
`(ABB)
`Available
`Block Buffer
`
`
`
`-1813
`(EBB)
`N
`Erased
`Block Buffer re
`F
`N-IN ;x
`
`MAP Exchange
`(e.g. when EBB
`is empty)
`
`784
`- - - - - - - - - - - - - - - - - - - - - - - - - -
`
`KIOXIA Ex-1007, Page 29
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 28 Of 29
`
`US 7,139,864 B2
`
`Logical
`Sector Address
`
`
`
`
`
`
`
`
`
`
`
`
`
`Sequential
`Update Block
`Address
`Translation
`
`Chaotic
`Update Block
`Address
`Translation
`
`
`
`Closed
`Update Block
`Address
`Translation
`
`ass
`Translation
`aSatC
`
`
`
`
`
`Metablock
`to Physical
`Address
`Translation
`
`
`
`Physical
`Sector Address
`
`890
`
`Address Translation
`FIG. 19
`
`KIOXIA Ex-1007, Page 30
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 29 Of 29
`
`US 7,139,864 B2
`
`Update
`Chaotic Sector
`List
`
`RAM
`Data
`Structures
`
`
`
`ontrol Write Operation
`
`
`
`
`
`
`
`Update
`EBM Sector
`
`Update
`GAT Sector
`
`Update
`CB Sector
`
`
`
`
`
`Update
`MAP Sector
`
`ReWrite
`MAP BOCk
`
`
`
`
`
`ReWrite
`GAT Block
`
`ReWrite
`CBI BIOCK
`
`Flash
`Data
`Structures
`
`
`
`Update
`MAPA Sector
`
`Rewrite
`MAPA BIOCk
`
`Update
`Boot Sector
`
`Rewrite
`BOOtBlock
`
`Operations on Control Data Structures
`F.G. 20
`
`KIOXIA Ex-1007, Page 31
`
`

`

`1.
`NON-VOLATILE MEMORY AND METHOD
`WITH BLOCK MANAGEMENT SYSTEM
`
`FIELD OF THE INVENTION
`
`This invention relates generally to non-volatile semicon
`ductor memory and specifically to those having a memory
`block management system.
`
`BACKGROUND OF THE INVENTION
`
`Solid-state memory capable of nonvolatile storage of
`charge, particularly in the form of EEPROM and flash
`EEPROM packaged as a small form factor card, has recently
`become the storage of choice in a variety of mobile and
`handheld devices, notably information appliances and con
`Sumer electronics products. Unlike RAM (random access
`memory) that is also solid-state memory, flash memory is
`non-volatile, and retaining its stored data even after power
`is turned off. Also, unlike ROM (read only memory), flash
`memory is rewritable similar to a disk storage device. In
`spite of the higher cost, flash memory is increasingly being
`used in mass storage applications. Conventional mass Stor
`age, based on rotating magnetic medium Such as hard drives
`and floppy disks, is unsuitable for the mobile and handheld
`environment. This is because disk drives tend to be bulky,
`are prone to mechanical failure and have high latency and
`high power requirements. These undesirable attributes make
`disk-based storage impractical in most mobile and portable
`applications. On the other hand, flash memory, both embed
`ded and in the form of a removable card is ideally suited in
`the mobile and handheld environment because of its small
`size, low power consumption, high speed and high reliability
`features.
`Flash EEPROM is similar to EEPROM (electrically eras
`able and programmable read-only memory) in that it is a
`non-volatile memory that can be erased and have new data
`written or “programmed' into their memory cells. Both
`utilize a floating (unconnected) conductive gate, in a field
`effect transistor structure, positioned over a channel region
`in a semiconductor Substrate, between Source and drain
`regions. A control gate is then provided over the floating
`gate. The threshold Voltage characteristic of the transistor is
`controlled by the amount of charge that is retained on the
`floating gate. That is, for a given level of charge on the
`floating gate, there is a corresponding Voltage (threshold)
`that must be applied to the control gate before the transistor
`is turned “on” to permit conduction between its source and
`drain regions. In particular, flash memory Such as Flash
`EEPROM allows entire blocks of memory cells to be erased
`at the same time.
`The floating gate can hold a range of charges and there
`fore can be programmed to any threshold Voltage level
`within a threshold voltage window. The size of the threshold
`Voltage window is delimited by the minimum and maximum
`threshold levels of the device, which in turn correspond to
`the range of the charges that can be programmed onto the
`floating gate. The threshold window generally depends on
`the memory device's characteristics, operating conditions
`and history. Each distinct, resolvable threshold voltage level
`range within the window may, in principle, be used to
`designate a definite memory state of the cell.
`The transistor serving as a memory cell is typically
`programmed to a “programmed' state by one of two mecha
`nisms. In "hot electron injection, a high Voltage applied to
`the drain accelerates electrons across the Substrate channel
`region. At the same time a high Voltage applied to the control
`
`2
`gate pulls the hot electrons through a thin gate dielectric onto
`the floating gate. In “tunneling injection, a high Voltage is
`applied to the control gate relative to the substrate. In this
`way, electrons are pulled from the substrate to the interven
`ing floating gate. While the term “program' has been used
`historically to describe writing to a memory by injecting
`electrons to an initially erased charge storage unit of the
`memory cell so as to alter the memory state, it has now been
`used interchangeable with more common terms such as
`“write or “record.”
`The memory device may be erased by a number of
`mechanisms. For EEPROM, a memory cell is electrically
`erasable, by applying a high Voltage to the Substrate relative
`to the control gate so as to induce electrons in the floating
`gate to tunnel through a thin oxide to the Substrate channel
`region (i.e., Fowler-Nordheim tunneling.) Typically, the
`EEPROM is erasable byte by byte. For flash EEPROM, the
`memory is electrically erasable either all at once or one or
`more minimum erasable blocks at a time, where a minimum
`erasable block may consist of one or more sectors and each
`sector may store 512 bytes or more of data.
`The memory device typically comprises one or more
`memory chips that may be mounted on a card. Each memory
`chip comprises an array of memory cells Supported by
`peripheral circuits such as decoders and erase, write and read
`circuits. The more Sophisticated memory devices also come
`with a controller that performs intelligent and higher level
`memory operations and interfacing.
`There are many commercially Successful non-volatile
`Solid-state memory devices being used today. These memory
`devices may be flash EEPROM or may employ other types
`of nonvolatile memory cells. Examples of flash memory and
`systems and methods of manufacturing them are given in
`U.S. Pat. Nos. 5,070,032, 5,095,344, 5,315,541, 5,343,063,
`and 5,661,053, 5,313,421 and 6.222,762. In particular, flash
`memory devices with NAND string structures are described
`in U.S. Pat. Nos. 5,570,315, 5,903,495, 6,046,935. Also
`nonvolatile memory devices are also manufactured from
`memory cells with a dielectric layer for storing charge.
`Instead of the conductive floating gate elements described
`earlier, a dielectric layer is used. Such memory devices
`utilizing dielectric storage element have been described by
`Eitan et al., “NROM: A Novel Localized Trapping, 2-Bit
`Nonvolatile Memory Cell.” IEEE Electron Device Letters,
`vol. 21, no. 11, November 2000, pp. 543–545. An ONO
`dielectric layer extends across the channel between Source
`and drain diffusions. The charge for one data bit is localized
`in the dielectric layer adjacent to the drain, and the charge
`for the other data bit is localized in the dielectric layer
`adjacent to the source. For example, U.S. Pat. Nos. 5,768,
`192 and 6,011,725 disclose a nonvolatile memory cell
`having a trapping dielectric sandwiched between two silicon
`dioxide layers. Multi-state data storage is implemented by
`separately reading the binary states of the spatially separated
`charge storage regions within the dielectric.
`In order to improve read and program performance,
`multiple charge storage elements or memory transistors in
`an array are read or programmed in parallel. Thus, a "page'
`of memory elements are read or programmed together. In
`existing memory architectures, a row typically contains
`several interleaved pages or it may constitute one page. All
`memory elements of a page will be read or programmed
`together.
`In flash memory systems, erase operation may take as
`much as an order of magnitude longer than read and program
`operations. Thus, it is desirable to have the erase block of
`
`US 7,139,864 B2
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`KIOXIA Ex-1007, Page 32
`
`

`

`US 7,139,864 B2
`
`3
`Substantial size. In this way, the erase time is amortized over
`a large aggregate of memory cells.
`The nature of flash memory predicates that data must be
`written to an erased memory location. If data of a certain
`logical address from a host is to be updated, one way is
`rewrite the update data in the same physical memory loca
`tion. That is, the logical to physical address mapping is
`unchanged. However, this will mean the entire erase block
`contain that physical location will have to be first erased and
`then rewritten with the updated data. This method of update
`is inefficient, as it requires an entire erase block to be erased
`and rewritten, especially if the data to be updated only
`occupies a small portion of the erase block. It will also result
`in a higher frequency of erase recycling of the memory
`block, which is undesirable in view of the limited endurance
`of this type of memory device.
`Another problem with managing flash memory system
`has to do with system control and directory data. The data is
`produced and accessed during the course of various memory
`operations. Thus, its efficient handling and ready access will
`directly impact performance. It would be desirable to main
`tain this type of data in flash memory because flash memory
`is meant for storage and is nonvolatile. However, with an
`intervening file management system between the controller
`and the flash memory, the data can not be accessed as
`directly. Also, system control and directory data tends to be
`active and fragmented, which is not conducive to storing in
`a system with large size block erase. Conventionally, this
`type of data is set up in the controller RAM, thereby
`allowing direct access by the controller. After the memory
`device is powered up, a process of initialization enables the
`flash memory to be scanned in order to compile the neces
`sary system control and directory information to be placed
`in the controller RAM. This process takes time and requires
`controller RAM capacity, all the more so with ever increas
`ing flash memory capacity.
`U.S. Pat. No. 6,567,307 discloses a method of dealing
`with sector updates among large erase block including
`recording the update data in multiple erase blocks acting as
`scratch pad and eventually consolidating the valid sectors
`among the various blocks and rewriting the sectors after
`rearranging them in logically sequential order. In this way,
`a block needs not be erased and rewritten at every slightest
`update.
`WO 03/027828 and WO OOf 49488 both disclose a
`memory system dealing with updates among large erase
`block including partitioning the logical sector addresses in
`Zones. A Small Zone of logical address range is reserved for
`active system control data separate from another Zone for
`user data. In this way, manipulation of the system control
`data in its own Zone will not interact with the associated user
`data in another