1111111111111111111111111111111111118111111111111111111111111111111
`
`US005822781A
`[11] Patent Number:
`[111 Patent Number: (cid:9)
`[45] Date of Patent: (cid:9)
`[45] Date of Patent:
`
`5,822,781
`5,822,781
`Oct. 13, 1998
`Oct. 13, 1998
`
`United States Patent [19]
`Ulllted States Patent [19]
`Wells et al. (cid:9)
`Wells et al.
`
`[54] SECTOR-BASED STORAGE DEVICE
`[54] sECTOR-BAsEI) STORAGE DEVICE
`EMULATOR HAVING VARIABLE-SIZED
`EMULATOR HAVING VARIABLE-SIZED
`SECTOR
`SECTOR
`
`[75] Inventors: Steven Wells, Citrus Heights; Robert
`[75] Inventors: Steven Wells, Citrus Heights; Robert
`N. Hasbun, Shingle Springs; Kurt
`Robinson, Newcastle, all of Calif.
`
`
`NI Hasbun, ROblIlSOIl, Newcastle, all of Calif. [73] Assignee: Intel Corporation, Santa Clara, Calif. - Springs; Kurt -
`
`
`
`[73] Assignee: Intel Corporation, Santa Clara, Calif.
`
`21 A L N _. 969 131
`[21] Appl. No.: 969,131
`[
`1
`pp
`0
`’
`Oct. 30, 1992
`[22] Filed: (cid:9)
`[22] Filed:
`Oct. 30, 1992
`6
` GO6F 12/04
`[51] Int. C1.6
`[51]
`Int. Cl. .................................................... .. G06F 12/04
`[52] U.S. Cl. (cid:9)
` 711/171; 395/500
`[52] US. Cl. .......... ..
`711/171; 395/500
`[58] Field of Search (cid:9)
` 395/400, 425,
`[58] Field of Search ................................... .. 395/400, 425,
`395/412, 430, 497.01, 497.02, 497.03, 497.04,
`395/412, 430, 497.01, 497.02, 497.03, 497.04,
`500; 365/900 MS, 185; 711/171, 172
`500; 365/900 MS, 185; 711/171, 172
`
`[56]
`[56]
`
`References Cited
`References Cited
`
`U.S. PATENT DOCUMENTS
`U.S. PATENT DOCUMENTS
`
`7
`
`7
`
`u er_
`
`3,648,255 3/1972 Beausoleil et al. (cid:9)
` 340/172.5
`3,648,255
`3/1972 Beausoleil et a1. ................ .. 340/1725
`4,430,727 2/1984 Moore et al. (cid:9)
` 395/425
`4,430,727
`2/1984 Moore et al. ......................... .. 395/425
`4,642,759 2/1987 Foster .
`i/(fsltler -
`4,644,494 2/1987 Muller
`4758 944 7/1988 Bartley e161. ........................ .. 395/425
`4,758,944 7/1988 Bartley et al. (cid:9)
` 395/425
`’
`’
`4,763,305 8/1988 Kuo
`4,763,305
`8/1988 K110 .
`478027117
`1/1989 Chrosny et a1"
`1/1989 Chrosny et al. .
`4,802,117 (cid:9)
`4,849,878
`7/1989 Roy ....................................... .. 395/600
`4,849,878 7/1989 Roy (cid:9)
` 395/600
`4,864,497
`9/1989 Lowry et a],
`395/650
`4,864,497 9/1989 Lowry et al. (cid:9)
` 395/650
`4,896,262 1/1990 Wayama et al. (cid:9)
` 395/500
`4,896,262
`1/1990 Wayama et a1. ..
`395/500
`4,958,315 9/1990 Balch (cid:9)
` 395/500
`4,958,315
`9/1990 Balch ------------------------------------ -- 395/500
`5,012,425 4/1991 Brown .
`5,012,425
`4/1991 BTOWII-
`5,067,128 11/1991 Nakane .
`¥§I1::1:t~a1
`5,070,474 12/1991 Tuma et al. .
`5,077,737 12/1991 Leger et al. ......................... .. 371/10.1
`5,077,737 12/1991 Leger et al. (cid:9)
` 371/10.1
`5 109 498 4/1992 Kamiya et al'
`N 395/49703
`5,109,498 4/1992 Kamiya et al. (cid:9)
` 395/497.03
`5’111’385
`5/1992 Hattori ________ __
`395/425
`5,111,385 5/1992 Hattori (cid:9)
` 395/425
`5:131:089
`7/1992 Cole ________________ __
`395/500
`5,131,089 7/1992 Cole (cid:9)
` 395/500
`5,210,854 5/1993 Beaverton et al. (cid:9)
` 395/430
`5,210,854
`5/1993 Beaverton et a1,
`395/430
`5,237,460 8/1993 Miller et al. (cid:9)
` 360/8
`5,237,460
`8/1993 Miller et a1. . . . . . .
`. . . . . .. 360/8
`5,280,611 1/1994 Mohan et al. (cid:9)
` 395/600
`5,280,611
`1/ 1994 Mohan et al
`395/600
`5,291,584 3/1994 Challa et al. (cid:9)
` 395/500
`glam‘? 6: ‘11L
`3379171583
`5,297,148 3/1994 Harari et al. (cid:9)
` 371/10.2
`5,305,295 4/1994 Chu (cid:9)
` 369/30
`5,313,429 5/1994 Chevallier et al. (cid:9)
` 365/226
`5,313,429
`5/1994 Chevallier et al.
`365/226
`5,359,205 10/1994 Orshinsky (cid:9)
` 257/3
`5,359,205 10/1994 Orshinsky ................................. .. 257/3
`
`,
`
`,
`
`arari e a .
`
`..
`
`..
`
`.
`
`5,305,295
`
`4/1994 Chu . . . . . . . . . . . . . . . . . . .
`
`. . . . .. 369/30
`
`
`5,493,574 2/1996 McKinley (cid:9)
`371/40.1
`5,493,574
`2/1996 McKinley ............................ .. 371/401
`FOREIGN PATENT DOCUMENTS
`FOREIGN PATENT DOCUMENTS
`
`2088442 7/1993 Canada (cid:9)
` 13/16
`2088442 7/1993 Canada .................................... .. 13/16
`0175458A2 3/1986 European Pat. Off. .
`0175458A2 3/1986 European Pat. Off. .
`0392895 10/1990 European Pat. Off. (cid:9)
`2251323 1/1992 United Kingdom (cid:9)
`2251324 1/1992 United Kingdom (cid:9)
`
`
`
`2251323 ................... .. European Pat. 1/1992 United Kingdom 2251324 1/1992 United Kingdom OTHER PUBLICATIONS
`
`
` 16/6
` 12/2
` 12/2
`
`
`OTHER PUBLICATIONS
`
`Robinson, Kurt, "Trends in Flash Memory System Design",
`Robinson, Kurt, “Trends in Flash Memory System Design”,
`Wescon Conference Record, Nov. 1990, pp. 468-472.
`Wescon Conference Record, Nov. 1990, pp. 468—472.
`Markus A. Levy and Dave Elbert, "Solutions for High
`Markus A. Levy and Dave Elbert, “Solutions for High
`Density Applications Using Intel Flash Memory,” Intel
`Density Applications Using Intel Flash Memory," Intel
`Application Note AP—343, pp- 6—297 through 6—364 (Oct
`Application Note AP-343, pp. 6-297 through 6-364 (Oct.
`1990).
`199())_
`Solid–State Mass Storage Arrives, Product Feature, Memory
`Solid—State Mass Storage Arrives, Product Feature, Memory
`Card Systems & Design, Jul./Aug. 1992.
`Card Systems & Design, Jul./Aug. 1992.
`_
`_
`_
`Primary Examiner—Eddie P. Chan
`Primary Examtner—Edd1e P. Chan
`Assistant Examiner—Hiep T. Nguyen
`Assistant Examiner—Hiep T. Nguyen
`Attorney, Agent, or Firm—Blakely, Sokoloff, Taylor &
`Attorney, Agent, or Firm—Blakely, Sokoloff, Taylor &
`Zafman
`Zafman
`
`[57] (cid:9)
`[57]
`
`ABSTRACT
`ABSTRACT
`
`.
`
`.
`
`.
`
`.
`
`.
`
`A solid state memory disk that stores data on a sector basis
`A solid state memory disk that stores data on a sector basis
`is described. The solid state disk includes an array of
`15 descnbed' The 50.1101 State. dlsk Includes an array of
`FLASH memory devices, which store the sectors of data.
`FLASH memory devices, WhlCh store the sectors of data.
`E h M k f
`.th. th FLASH
`.
`1 d
`Each block of memory within the FLASH array includes
`ac
`oc 0 memory W1 in
`e
`array 1ncu es
`data space for storing many sectors of data and a block
`data Space for Stonng many Sectors of data and a block
`sector translation table. The block sector translation table
`sector translation table. The block sector translation table
`identifies each sector of data stored in the block's data space
`identi?es each sector of data stored in the block’s data space
`by a sector number. The solid state disk also includes a
`by a sector number. The solid state disk also includes a
`controller. Among its many responsibilities, the controller
`controller. Among its many responsibilities, the controller
`manages the writing of sector data into the array and the
`manages the Writing of sector data into the array and the
`reading of sectors of data from the array. The controller
`readmgd of Seem.“ of data 5mm {:16 may‘ {he Comfone;
`responds to a write request by seeking an earlier version of
`respon s to a vvrite request‘ y see ing an ear 1er version o
`the sector which has a logical sector number equal to the
`the sector Which has a logical sector number equal to the
`sector's sector number and marking that sector dirty.
`sector’s sector number and marking that sector dirty.
`Afterward, the controller allocates free memory space for
`Afterward, the controller allocates free memory space for
`the sector of data. The sector of data is then written into the
`the sector of data. The sector of data is then Written into the
`allocated memory space. The controller reads sectors of data
`allocated memory space. The controller reads sectors of data
`by seeking a sector header translation table to convert sector
`by seeking a sector header translation table to convert sector
`numbers into physical addresses.
`
`~
`
`-
`
`numbers Into physlcal addresses‘
`
`31 Claims, 22 Drawing Sheets
`31 Claims, 22 Drawing Sheets
`
`BLOCK SECTOR
`BLOCK SECTOR
`TRANSLATION
`TFtTAIrIBSLI-EITlJN
`TABLE 84
`GROWS
`GROWS
`DOWNWARD
`DOWNWARD
`
`HEADER FOR LSNB1
`HEADER FOR LSNB1
`BSO1
`(INCLUDES BSO1)
`(INCLUDES BSO1) \ B802
`HEADER FOR LSNB2
`HEADER FOR LSNB2
`(INCLUDES BSO2)
`(INCLUDES B502)
`
`88“
`88
`DATA SPACE 86
`DATA SPACE E
`GROWS
`enows
`UPWARD
`UPWAHD
`
`1
`
`SLACK (FFFF)
`SLACK (FFFF)
`
`DATA FOR LSNB2
`DATA FOR LSNB2
`DATA FOR LSNB1
`Q
`DATA FOR LSNB1
`89
`BLOCKATI'RIBUTE DATA E
`BLOCK ATTRIBUTE DATA LO
`
`16 BITS WIDE
` 16 BITS WIDE (cid:9)
`
`
`
`HIGH BYTE -+- LOW BYTE
`STORED IN
`STORED IN
`
`
`Sega]? * 24242515 HIGH CHIP @ LOW CHIPE
`HIGH CHIP 68
`DIRTY LOW CHIP 70
`
`BAD
`TRACK (cid:9)
`
` DIRTY
`BIT
`
`BIT (cid:9)
`
`
`an, IIrN‘NNXI/I‘I a?” a?“
`
`1111011 ge1111 (cid:9)
`COMPRESSION k DATA
`COMPRESSION
`DATA
`ATTACHED
`ATTACHED
`
`85
`85
`4 WORDS
`/4 WORDS
`LONG
`I
`LONG
`)
`CRC LSNB
`CRC
`LSN
`LSNB I LSN:
`LSNB LSNB
`ATTRIBUTE WORD
`ATTRIBUTE WORD
`BLOCK SECTOR
`BLOCK SECTOR
`OFFSET
`P1311128
`16 BITS (cid:9)
`WIDE
`REVISION
`nevso
`NUMBER
`
`
`
`IIIII
`NENE
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0001
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`
`U.S. Patent (cid:9)
`
`Oct. 13, 1998 (cid:9)
`
`Sheet 1 of 22 (cid:9)
`
`5,822,781
`
`—SIG (cid:9)
`
`50
`
`52
`
`CENTRAL
`PROCESSING
`UNIT
`CPU)
`
`SOLID STATE DISK
`
`SOLID STATE
`DISK CONTROLLER
`
`FLASH MEMORY
`ARRAY
`
`66
`
`64
`
`62
`
`T64
`
`-96
`
`RAM SECTOR
`BUFFER
`
`98
`
`93
`
`WINDOW
`ASIC
`
`5V TO 12V
`CHARGE PUMP
`
`10
`
`92
`
`MICROPROCESSOR
`
`FLASH ARRAY
`DATABASES
`(RAM)
`
`/- 94
`
`SECTOR HEADER
`TRANSLATION
`TABLE (RAM)
`
`1
`
`95
`
`FLASH MEMORY
`STORING
`SSD
`CONTROLLER
`ALGORITHIMS
`
`TO
`HOST CPU
`52
`
`r
`
`62
`
`68
`
`BLOCK 0
`
`80a
`
`BLOCK 0
`
`BLOCK 1
`•
`• •
`BLOCK 15
`
`80
`
`BLOCK 1
`•
`•
`•
`
`BLOCK 15
`
`HIGH CHIP (cid:9)
`
`LOW CHIP
`
`CHIP PAIR 66
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0002
`
`(cid:9)
`(cid:9)
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`0a. 13, 1998
`Oct. 13, 1998 (cid:9)
`
`Sheet 2 0f 22
`Sheet 2 of 22 (cid:9)
`
`5,822,781
`5,822,781
`
`—1F" I G (cid:9) 3
`E‘ I E _ 3
`
`r
`
`BLOCK SECTOR
`BLOCK SECToR
`TRANSLATION
`TRANSLATION
`TABLE a_4
`TABLE 84
`GROWS
`GROWS
`DOWNWARD
`DoWNWARD
`<>
`
`BSO1
`HEADER FOR LSNB1
`B801
`HEADER FoR LSNB1
`INCLUDES 580
`(INCLUDES BS01)
`(
`1) \ B802
`BS \2'''.--
`HEADER FOR LSNB2
`/
`HEADER FOR LSNB2
`(INCLUDES B802)
`(INCLUDES BSO2)
`;
`
`•
`•
`•
`k
`A
`.
`88 -----
`t SLACK (FFFF)
`88 m "
`SLACK (FFFF)
`r
`DATA SPACE 86
`DATA SPACE @
`GROWS
`GROWS <
`UPWARD
`uPWARD
`
`’
`
`4
`
`‘
`
`s5
`85
`4 WORDS
`/4 WORDS
`LONG
`LONG)
`
`L
`
`4}
`
`\
`
`HIGH BYTE —46— LOW BYTE
`<- HIGH BYTE
`LOW BYTE ——>
`STORED IN (cid:9)
`STORED IN
`SToRED IN
`SToRED IN
`HIGH CHIP 68 (cid:9)
`LOW CHIP 70
`HIGH CHIPg
`LOW CHIPE
`
`14
`
`A
`
`v
`
`DATA FOR LSNB2
`DATA FOR LSNB2
`
`89
`DATA FOR LSNB1
`Q
`DATA FoR LSNB1
`BLCCK A‘ITRIB TE DATA 90
`BLOCK ATTRIBUTE DATA 90
`U
`_
`
`CRC LSNB
`CR0
`LSNB
`LSNB LSNB
`LSNB
`LSNB
`ATTRIBUTE WORD
`-ATTRIBuTE WoRD
`16 BITS WIDE
`<--— 16 BITS WIDE ——>
`BLOCK SECTOR
`BLOCK SECToR
`OFFSET
`OFFSET
`16 ms
`16 BITS H
`W|DE
`WIDE
`REVISION
`EE‘A/A'S'ON
`NUMBER
`U BER
`a,..—........A..,
`l
`l
`l
`I
`
`BAD
`DIRTY DIRTY
`DIRTY
`DIRTY
`BAD
`TRACK
`BIT (cid:9)
`BIT
`BIT
`BITw
`TRACKv
`IIII'll 'Eli
`L II
`I
`l
`1
`LCOMPRESSION k DATA
`COMPRESSION (cid:9)
`DATA
`ATTACHED
`ATTACHED
`
`Ir
`
`L
`
`'
`
`—SIG 4
`P I E _ 4
`94
`ADDRESS IN
`ADDRESS IN
`94
`
`LSN
`LSN
`
`r
`
`83,300
`83,300
`ENTR|ES
`ENTRIES
`IN
`IN
`SHTT
`SHTT
`
`<
`
`SECTOR HEADER
`SECTOR HEADER
`TRANSLATION
`TRANSLATION
`TABLE
`TABLE
`(SHTT)
`(SHTT)
`
`\
`
`DATA OUT
`DATA OUT
`
`16 BITS OF A
`16 BITS OF A
`PHYSICAL
`PHYSICAL
`ADDRESS
`ADDRESS
`WITHIN FLASH
`WITHIN FLASH
`ARRAY 62
`ARRAY Q
`
`CHIP PAIR (4 BITS)
`CHIP PAIR (4 BITS)
`BLOCK (4 BITS)
`BLOCK (4 BITS)
`:> AND
`* AND
`HEADER POINTER
`HEADER POWER
`(8 BITS)
`(8 BITS)
`
`16 BITS WIDE
`H--— 16 BITS WIDE —>
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0003
`
`(cid:9)
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`Oct. 13,1998
`Oct. 13, 1998 (cid:9)
`
`Sheet 3 0122
`Sheet 3 of 22 (cid:9)
`
`5,822,781
`5,822,781
`
`PII_i_E
`"BUILDING SHTT"
`"BUILDING SHTT"
`
`I
`110
`110
`INITIALIzE SHTT TO EMPTY /
`INITIALIZE SHTT TO EMPTY
`I
`INITIALIZE TFFA TO MAX SIZE
`INITIALIZE TFFA TO MAX SIZE
`111
`111
`INITIALIzE TI=I=C (ALL CHIPS) /
`INITIALIZE TFFC (ALL CHIPS)
`TO MAX SIZE
`TO MAX SIzE
`
`NO
`
`136
`
`RETURN
`
`>}
`
`112
`112
`
`ARE
`ARE
`THERE
`THERE
`ANY MORE BLOCKS
`ANY MORE BLOCKS
`TO BE SCANNED?
`TO BE SCANNED?
`
`114
`
`SELECT A BLOCK TO SCAN
`115
`I
`lNlTlALlZE TFFBC TO /
`INITIALIZE TFFBC TO
`MAX SIZE
`MAX SIzE
`116
`+
`READ THE NEXT HEADER |;_—
`READ THE NEXT HEADER
`120
`120
`I f
`UPDATE TDFA AND
`UPDATE TDFA AND
`TDFB
`TDFB
`I
`UPDATE TFFA, TFFB &
`UPDATE TFFA, TFFB &
`TFFC BY SUBTRACTING
`TFFC BY SUBTRACTING +0
`SECTOR SIZE
`SECTOR SIZE
`
`IS THE
`SECTOR
`DIRTY?
`
`121 (cid:9)
`
`"
`124 \
`UPDATE TFFA, TFFC, & TFFB
`UPDATE TFFA, TFFC, & TFFB
`BY SUBTRACTING SECTOR SIZE
`BY SUBTRACTING SECTOR SIZE
`
`126
`126
`
`DOES AN
`DOES AN
`ENTRY ALEADY
`ENTRY ALEADY
`EXIST IN SHTT FOR THE
`EXIST IN SHTT FOR THE
`SECTOR NUMBER
`SECTOR NUMBER
`EQUAL TO THIS
`EQUAL TO THIS
`LSN?
`
`128
`
`NO
`
`L
`
`WRITE INTO SHTT CHIP PAIR,
`WRITE INTO SHTT CHIP PAIR,
`BLOCK, AND HEADER
`BLOCK, AND HEADER
`POINTER OF CURRENT LSN
`POINTER OF CURRENT LSN
`
`END OF
`BSTT
`REACHED?
`REACHED?
`
`YES
`YES
`
`IV
`
`/ 130
`130
`I /
`READ REVISION NUMBERS
`READ REVISION NUMBERS
`FOR BOTH SECTORS
`FOR BOTH SECTORS
`I
`MARK DIRTY HEADER WITH
`MARK DIRTY HEADER WITH
`132
`132 \ EARLIER REv NUMBER
`EARLIER REV NUMBER
`I
`133
`133 \ UPDATE TDFB AND TDFA
`UPDATE TDFB AND TDFA
`BY ADDING SECTOR SIZE
`BY ADDING SECToR SIzE
`4,
`I
`IF NECESSARY, WRITE INTO
`IF NECESSARY, WRITE INTO
`134
`134
`\ SHTT CHIP PAIR, BLOCK AND
`SHTT CHIP PAIR, BLOCK AND
`HEADER POINTER OF SECTOR
`HEADER POINTER OF SECTOR
`WITH LATER REV. NO.
`WITH LATER REV. NO.
`
`V
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0004
`
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`Oct. 13, 1998 (cid:9)
`Oct. 13,1998
`
`Sheet 4 of 22 (cid:9)
`Sheet 4 0f 22
`
`5,822,781
`5,822,781
`
`IIG (cid:9) 6
`FI[i___E
`150
`150
`TOP LEVEL /
`TOP LEVEL
`SCHEDULER
`scI-IEDULER
`—| |_—
`,c,
`
`156 ---\, (cid:9)
`
`INTERFACE
`INTERFACE
`
`CLEANUP
`CLEANUP
`
`‘
`
`:
`
`FLASH
`POWER
`
`162
`
`158 -N
`\
`SECTOR
`SECTOR
`BUFFER
`BUFFER
`M
`
`HOST I/F 15_2
`HOST I/F 152
`
`‘
`‘
`
`\ V
`>
`
`DISK
`
`SECTORS
`; sEcToRs / To
`TO
`FLASH
`ARRAY
`ARRAY
`62
`Q ‘
`'
`
`II
`FLASH ARRAY
`FLASH ARRAY
`INTERFACE
`INTERFACE
`
`I
`
`FLASH MEDIA 1_54
`FLASH MEDIA 154
`
`x167
`
`98
`98
`--\
`X
`SECTOR
`sEcToR
`BUFFER
`BUFFER
`
`168
`i-168
`II f
`SEQUENCER
`4
`4 U
`L , SEQUENCER L
`
`TO
`TO
`FLASH
`XFLI?',
`ARRAY
`62
`62
`
`— L
`7
`
`PIE__7
`----m i
`"DISK READ"
`"DISK READ"
`
`SECTOR NUMBER
`SECTOR NUMBER
`
`170
`170
`
`YES
`YES
`
`IS
`IS
`SECTOR NUMBER
`SECTOR NUMBER
`WITHIN VALID
`WITHIN VALID
`RANGE?
`RANGE?
`
`NO
`
`176 \ II
`SEEK SHTT FOR CHIP, BLOCK AND
`SEEK SHTT FoR CHIP, BLOCK AND
`HEADER POINTER CORRESPONDING
`HEADER PoINTER CORRESPONDING
`TO SECTOR NUMBER
`TO sEcToR NUMBER
`
`1s2\
`
`/172
`172
`II /
`SET RETURN STATUS
`SET RETURN STATUS
`TO INVALID
`TO INvALID
`SECTOR NUMBER RANGE
`sEcToR NUMBER RANGE
`
`CALL SECTORS
`SEEK
`
`184
`
`SECTOR
`FOUND?
`
`186
`\
`sEcTCgR'READ
`
`180
`" /
`RETURN
`551L522
`HEADER
`NOT FOUND
`NOT FOUND
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0005
`
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`Oct. 13, 1998 (cid:9)
`Oct. 13,1998
`
`Sheet 5 of 22 (cid:9)
`Sheet 5 0f 22
`
`5,822,781
`5,822,781
`
`P IIE=_3 "SEEK"
`1: "SEEK"
`
`SECTOR NUMBER (SNi)
`SECTOR NUMBER (SNi)
`
`190
`190
`x LAST
`LAST
`READ HEADER =
`READ HEADER =
`LAST HEADER IN
`LAST HEADER IN
`BLOCK?
`BLOCK?
`
`YES
`
`NO [192
`READ NEXT HEADER FROM
`READ NEXT HEADER FROM
`LAST HEADER READ BY
`LAST HEADER READ BY
`CALLER
`CALLER
`
`194
`
`SECTOR
`NUMBER =
`LSNc ?
`
`HEADER
`
`198
`YES
`
`CRCG =
`CRC STORED?
`
`READ SECTOR HEADER
`READ SECTOR HEADER
`TRANSLATION TABLE
`TRANSLATION TABLE
`
`‘
`
`IS
`VALUE OF
`CHIP PAIR, BLOCK AND
`HEADER OFFSET
`< FFFF?
`
`200
`T
`200
`DETERMINE SECTOR SIZE
`DETERMINE SECTCR SIzE /
`
`7-210
`210
`L f
`SET SCAN COUNT
`SET SCAN CouNT
`TO 0
`TO 0
`
`212
`212
`
`YES
`
`SCAN COUNT
`SCAN COUNT
`= MAXIMUM SCAN
`= MAXIMUM SCAN
`COUNT?
`COUNT?
`
`224
`s/
`RETURN
`HEADER
`HEADER
`NOT FOUND
`NOT FOUND
`
`NO
`
`214
`
`LSNC = SN ?
`
`216
`YES f 216
`YES
`
`GENERATE CRC FOR
`GENERATE CRC FOR
`CURRENT HEADER
`CURRENT HEADER
`
`218
`
`YES
`
`M
`
`IS CRCG =
`IS CRCG =
`CRC STORED ?
`CRC STORED ?
`
`220
`NO [ 220
`
`MARK HEADERS DIRTY
`MARK HEADERS DIRTY
`
`T
`\ (cid:9)
`RETURN CHIP PAIR, BLOCK,
`RETURN CHIP PAIR, BLOCK,
`OFFSET, SECTOR SIZE,
`AND ATTRIBUTE
`AND A‘ITRIBUTE
`
`\OFFSET, SECTOR SIZE, i
`
`202
`202
`
`RETURN
`
`204
`204
`
`INCREMENT SCAN COUNT
`INCREMENT SCAN COUNT —>
`
`si-- 222
`" f 222
`
`(cid:9) k
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0006
`
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`Oct. 13, 1998 (cid:9)
`Oct. 13,1998
`
`Sheet 6 of 22 (cid:9)
`Sheet 6 0f 22
`
`5,822,781
`5,822,781
`
`I: I IE: _ El "DISK WRITE"
`II X IIG ni "DISK WRITE"
`
`SECTOR NUMBER (SNi)
`SECTOR NUMBER (SNi)
`
`230
`
`NO
`NO
`
`SN i
`VALID ?
`
`
`
`YES (cid:9)
`
`2 236
`
`/236
`
`1- 232
`‘ f 232
`RETURN INvALID RANGE
`RETURN INVALID RANGE
`
`ENABLE CHARGE PUMP
`ENABLE CHARGE PUMP
`
`‘
`
`238
`{y CALL SEEK /
`
`CALL SEEK
`
`240
`240
`
`f 242
`242
`
`244
`
`Vpp
`VALID?
`
`YES
`
`246
`246
`
`YES
`
`HEADER
`HEADER
`ALREADY EXIST
`ALREADY ExIST
`FoR SM?
`FOR SN i?
`
`NO
`NO
`4
`
`ATTRIBUTE
`ATTRIBUTE
`woRD INDICATE
`WORD INDICATE
`TRACK
`TRACK
`BAD?
`BAD?
`
`YES
`YES
`
`RETURN
`BESTTLIJR'X'EK
`BAD TRACK
`
`>
`-O.
`
`NO
`NO
`/ 247 (cid:9)
`/ 247
`
`2423
`248
`
`MARK DIRTY
`MARK DIRTY
`HEADER OF
`HEADER OF
`PREVIOUS COPY
`PREvIoUS CCPY
`
`CACHE
`MARK DIRTY?
`
`YES
`
`NO
`
`1'
`249
`V
`249
`\ INCREMENT REv #
`INCREMENT REV #
`FOR LSN
`FOR LSN
`4
`I
`
`II
`
`V
`250
`ALLOCATE FREE PHYSICAL
`ALLoCATE FREE PHYSICAL / 250
`SECTOR
`SECTOR
`4
`Y
`252
`GENERATE CR0 FOR / 252
`GENERATE CRC FOR
`HEADER
`HEADER
`4
`+
`254
`254
`WRITE HEADER TO BSTT /
`WRITE HEADER TO BSTT
`
`4
`l
`256
`WRITE SECTOR DATA & ECC /256
`WRITE SECTOR DATA & ECC (cid:9)
`INTO DATA SPACE
`INTO DATA SPACE
`
`V
`
`. r
`
`258
`258
`f
`‘
`UPDATE SHTT TO PoINT MoST
`UPDATE SHTT TO POINT MOST
`RECENT VERSION OF SECTOR
`RECENT vERSIoN OF SECTOR
`I
`f 260
`,/- 260
`4,
`DISABLE CHARGE PUMP
`DISABLE CHARGE PUMP
`,7-- 262
`f 262
`l
`ENABLE CLEANUP STATE
`ENABLE CLEANUP STATE
`MACHINE
`MACHINE
`
`4
`
`V
`
`234
`
`RETURN
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0007
`
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`Oct. 13, 1998 (cid:9)
`Oct. 13, 1998
`
`Sheet 7 of 22 (cid:9)
`Sheet 7 0f 22
`
`5,822,781
`5,822,781
`
`G (cid:9) 10A
`PIE_1I]A
`"ALLOCATE FREE PHYSICAL MEMORY"
`IIALLOCATE FREE PHYSICAL MEMORY"
`
`SECTOR SIZE, CALLER TYPE
`SECTOR SIZE, CALLER TYPE
`271
`
`CALLER
`= HOST?
`YES (cid:9)
`
`272
`
`RESERVES - SECTOR SIZE > FLASH WARN1?
`
`NO
`
`YES (cid:9)
`
`274
`
`274 /
`
`RESERVE STATUS = OK I
`RESERVE STATUS = OK
`
`RESERVE STATUS = FLASH WARN1 I
`RESERVE STATUS : FLASH WARN1
`
`YES
`
`RESERVES - SECTOR SIZE > FLASH WARN2?
`RESERVES — SECTOR SIZE > FLASH WARN2?
`
`275
`275
`
`NO
`NO (cid:9)
`
`‘I
`
`276
`f 276
`
`RESERVE STATUS = FLASH WARN 2 I
`RESERVE STATUS = FLASH WARN 2
`
`YES
`
`RESERVES - SECTOR SIZE > STANDBY?
`RESERVES — SECTOR SIZE > STANDBY?
`
`278
`278
`
`140
`
`282
`282
`
`NO (cid:9)
`NO
`
`279
`279 f
`II
`RESERVE STATUS = STANDBY I
`RESERvE STATUS = STANDBY
`I
`f 280
`/- 280
`
`DISK NO MORE WRITES
`DISK NO MORE wRITES
`
`>
`
`(cid:9)
`285
`285
`\
`\
`SELECT A
`SELECT A
`NEW BLOCK
`NEW BLOCK
`CHAIN
`CHAIN
`‘I
`
`HAVE ALL
`HAVE ALL
`BLOCK CHAINS BEEN
`BLOCK CHAINS BEEN
`SEARCHED?
`SEARCHED?
`
`YES
`YES
`
`NO
`
`306
`306
`
`NO
`NO
`
`CALLER
`CALLER
`TYPE
`TYPE
`CLEAN-UP?
`CLEAN-UP?
`
`SET CSM STATE
`SET CSM STATE
`TO IDLE
`TO IDLE
`308 A
`FORCE FOREGROUND
`FORCE FOREGROUND
`CLEANUP
`CLEANUP
`
`SINGLE BLOCK
`SINGLE BLOCK
`MODE
`MODE
`
`*1, NO
`
`284
`284
`
`YES
`
`HAVE
`HAVE
`ALL CHIP
`ALL CHIP
`PAIRS IN CURRENT
`PAIRS IN CURRENT
`BLOCK CHAIN BEEN
`BLOCK CHAIN BEEN
`SEARCHED
`SEARCHED
`
`288
`
`SELECT ANOTHER
`SELECT ANOTHER YES
`6-4-CHIP PAIR IN CURREN
`‘<—CHIP PAIR IN CURRENT
`BLOCK CHAIN
`BLOCK CHAIN
`
`(PD
`
`I FIG. _1OB I
`4, FIG. _10B 4,
`
`286
`
`IS
`IS
`CURRENT
`CURRENT
`CH“: PA|R
`CHIP PAIR
`USY?
`USY?
`'
`NO
`NO
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0008
`
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`Oct. 13, 1998
`Oct. 13, 1998 (cid:9)
`
`Sheet 8 of 22 (cid:9)
`Sheet 8 0f 22
`
`5,822,781
`5,822,781
`
`0 PIE_ IIIIB
`,---IF" I G _ 1_ 1111 111
`t FIG. _10A f
`L_AJ . (cid:9)
`A M
`T FIG. _1OA T
`290 -,
`290 X
`SELECT ANOTHER
`SELECT ANOTHER
`CHIP PAIR IN
`‘
`CHIP PAIR IN
`4-
`A
`CURRENT
`CURRENT
`BLOCK CHAIN
`BLOCK CHAIN
`
`289
`
`YES
`IS CURRENT
`CHIP PAIR ALLOCATE
`TO ANOTHER
`TO ANOTHER
`- HD0533?
`ROCESS9
`
`NO
`
`292
`292 \
`SELECT ANOTHER
`SELECT ANOTHER
`CHIP PAIR IN
`CH'P PA'R 'N
`CURRENT
`CURRENT
`BLOCK CHAIN
`BLOCK CHAIN
`
`A‘
`A
`
`291
`
`NO
`
`YES
`
`IS CURRENT
`IS CURRENT
`CHIP PAIR FOCUS OF
`CHIP PAIR FOCUS OF
`CLEANUP,
`CLEAN-UP?
`-
`
`294 -,
`
`294x
`
`‘
`1E-
`“
`
`SELECT ANOTHER
`SELECT ANOTHER
`CHIP PAIR IN
`CHIP PAIR IN
`CURRENT
`CURRENT
`BLOCK CHAIN
`BLOCK CHAIN
`
`293
`
`YES
`
`NO
`
`MAX NUMBER
`IAIQXHEXQIEESR
`OF HEADERS
`STORED IN
`STORED IN
`BSTT?
`
`296 -\
`296 K
`SELECT ANOTHER
`SELECT ANOTHER
`BLOCK IN
`BLOCK IN
`CURRENT
`CURRENT
`BLOCK CHAIN
`BLOCK CHAIN
`298 -----\
`
`A- 4—
`<
`“
`
`NO
`
`‘A
`
`SELECT ANOTHER
`SELECT ANOTHER
`BLOCK IN
`BLOCK IN
`CURRENT
`CURRENT
`BLOCK CHAIN
`BLOCK CHAIN
`
`YES
`
`NO
`
`/- 295
`
`SPACE
`AVAILABLE
`AVAILABLE
`ON BLOCK?
`ON BLOCK?
`
`YES
`
`297
`
`BLOCK
`BAD?
`
`NO
`299 --
`STORE CHIP PAIR AND BLOCK
`299 \ STORE CHIP PAIR AND BLOCK
`NUMBERS IN RAM
`NUMBERS IN RAIvI
`II
`300
`WRITE BSO IN HEADER IN BSTT OF
`300 \ WRITE BSO IN HEADER IN BSTT OF
`CURRENT CHIP PAIR AND BLOCK
`CURRENT CHIP PAIR AND BLOCK
`III
`4,
`301
`301 \ DECREASE TFFA, TFFB, TFFC
`DECREASE TFFA, TFFB, TFFC
`+
`302 (cid:9)
`RETURN CHIP PAIR, BLOCK AND
`302 \ RETURN CHIP PAIR, BLOCK AND
`OFFSET TO HEADER TO CALLER
`OFFSET TO HEADER TO CALLER
`
`304
`304
`
`RETURN
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0009
`
`

`
`U.S. Patent (cid:9)
`Oct. 13,1998
`U.S. Patent
`Oct. 13, 1998 (cid:9)
`—FIG (cid:9) 11
`I_:' I I3: _ 1 1
`
`Sheet 9 0f 22
`Sheet 9 of 22 (cid:9)
`
`5,822,781
`5,822,781
`
`STARTING BLOCK OF WRITE
`STARTING BLOCK OF WRITE
`
`•
`•
`Q
`
`CP1O,
`B1
`
`. .
`
`.' \ 320
`.
`320
`•
`•
`'
`
`'
`.
`
`STARTING DESTINATION
`STARTING DESTINATION
`BLOCK OF CSM1
`BLOCK OF CSM1
`
`CP15,
`B15
`
`•
`•
`
`CF10,
`B15
`
`• • •
`
`Se (cid:9)
`•
`
`322
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0010
`
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`Oct. 13, 1998 (cid:9)
`061. 13, 1998
`
`Sheet 10 of 22 (cid:9)
`Sheet 10 0f 22
`
`5,822,781
`5,822,781
`
`-----IX G (cid:9)
`II I E _12 A "ALLOCATE FREE PHYSICAL MEMORY TO HOST"
`11_ (cid:9)
`Ar\_ "ALLOCATE FREE PHYSICAL MEMORY TO HOST"
`i
`
`1205
`1 205
`
`SECTOR SIZE
`SECTOR SIZE
`
`YES (cid:9)
`YES
`
`1202
`1202
`
`IF
`IF
`FREE FLASH -
`FREE FLASH -
`SECTORSIZE <
`SECTORSIZE <
`STANDBY
`STANDBY
`FLASH?
`FLASH?
`
`NO
`
`YES
`YES
`
`1204
`1204
`
`RETuRN IN
`RETURN IN
`STANDBY
`STANDBY
`
`
`
`IS THERE
`IS THERE
`SUFFICIENT FREE
`SUFFICIENT FREE
`MEMORY IN BLOCK HOST
`MEMORY IN BLOCK HOST
`LAST ALLOCATED INTO
`LAST ALLOCATED INTO
`TO STORE THIS
`TO STORE THIS
`SECTOR?
`SECTOR?
`,i, NO
`
`MOST FREE BLOCK = 0
`MOST FREE BLOCK = 0
`
`1206
`1206
`<-----'
`
`I
`1208
`1208
`MOST FREE CHIP = o /
`MOST FREE CHIP = 0
`+
`I
`1210
`1210
`<....___./
`GREATEST SCORE = 0
`GREATEST SCORE = 0 V
`
`MOST FREE <
`SECTOR SIZE?
`
`1212
`
`YES
`YES ALL BLOCKS IN ARRAY
`ALL BLOCKS IN ARRAY
`SEARCHED?
`SEARCHED?
`
`:
`
`1260
`/
`DO A FOREGROUND
`DO A FOREGROUND
`CLEANUP
`CLEANUP
`‘_—
`4
`1262
`SCAN FoR NEXT AVAILABLE 1262
`SCAN FOR NEXT AVAILABLE
`HEADER IN CURRENT
`>
`HEADER IN cuRRENT /
`CHIP PAIR AND BLOCK
`CHIP PAIR AND BLOCK
`1264
`I
`1264
`4
`WRITE 880 IN /
`WRITE BSO IN
`HEADER
`HEADER
`
`4,
`DECREASE TFFA, TFFB,
`DEcREAsE TFFA, TFFB,
`TFFC
`TFFC
`4
`1266
`1266
`\ RETURN CHIP PAIR,
`RETuRN CHIP PAIR,
`,---
`BLOCK, AND /
`BLOCK, AND
`HEADER OFFSET
`HEADER OFFSET
`
`II
`
`RETURN
`
`(cid:9))04
`
`+ NO 1214
`YES
`CURREN
`CHIP PAIR
`BUSY?
`NO 1216
`CURREN
`CHIP PAIR
`TARGETED FOR
`LEANUP?
`
`YES
`
`NO
`
`1218
`
`IS
`CURENT BLOCK
`ALLOCATED BY
`A CSM?
`NO 1220
`
`YES
`
`(cid:9)o*
`
`BLOCK BAD?
`
`YES
`
`(cid:9)>41
`
`1230
`
`,1, NO (cid:9)
`MAX
`NUMBER OF
`NUMBER OF
`HEADERS ALREADY
`HEADERS ALREADY
`WRITTEN
`WRITTEN
`IN BLOCK?
`IN BLOCK?
`
`YES
`YES
`
`IFIGURE12B I
`FIGURE 12B
`
`NO
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0011
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`Oct. 13, 1998 (cid:9)
`Oct. 13,1998
`
`Sheet 11 of 22 (cid:9)
`Sheet 11 0f 22
`
`5,822,781
`5,822,781
`
`-----m X n (cid:9)
`I: I E __1 2 B "ALLOCATE FREE PHYSICAL MEMORY TO HOST"
`1_I XII "ALLOCATE FREE PHYSICAL MEMORY TO HOST"
`lo
`fF|GURE12Af
`(E)
`
`t FIGURE 12A t yi
`
`"
`
`RULE 1 = TFFBC * W1
`RULE 1 = TFFBC * W1
`
`RULE 2 = (TPDFC - TDFC) * W2
`RULE 2 = (TPDFC - TDFC) * W2
`T
`4
`RULE 3 = TDFB * W3
`RULE 3 = TDFB * W3
`T
`4
`RULE 4 = DELTA CYCLE COUNT * W4
`RULE 4 = DELTA CYCLE COUNT * W4
`
`4
`RULE 5=
`RULE 5 =
`BLOCK IN CHIP NOT ALLOCATED * W5
`BLOCK IN CHIP NOT ALLOCATED * W5
`T
`4
`TOTAL =
`TOTAL =
`RULE 1 + RULE 2 + RULE 3 + RULE 4 + RULE 5
`RULE 1 + RULE 2 + RULE 3 + RULE 4 + RULE 5
`
`1232
`1232 /
`
`[1234
`1234
`
`1235
`1235
`/
`
`-1236
`/123s
`
`e„-1238
`/1238
`
`1240
`/1240
`
`1242
`1242
`
`TOTAL >
`GREATEST
`SCORE?
`
`YES
`
`NO
`NO
`
`•
`a»
`
`GREATEST SCORE = TOTAL
`GREATEST SOORE = TOTAL
`
`v
`MOST FREE = TFFBC
`MOST FREE = TFFBC
`
`v
`
`MOST FREE BLOCK = CURRENT BLOCK
`MOST FREE BLOCK = OURRENT BLOCK
`
`v
`
`MOST FREE CHIP = CURRENT CHIP
`MOST FREE CHIP = OURRENT CHIP
`
`1243
`
`/124s
`
`/ 1244
`/ 1244
`
`1246
`1246 /
`
`1248
`1248 /
`
`E
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0012
`
`(cid:9)
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`0a. 13, 1998
`Oct. 13, 1998 (cid:9)
`
`Sheet 12 0f 22
`Sheet 12 of 22 (cid:9)
`
`5,822,781
`5,822,781
`
`I IG (cid:9) 1 (cid:9)
`P IE_ 1 3 "MARK DIRTY"
`"MARK DIRTY"
`SN AND CHIP, BLOCK, POINTER TO HEADER
`SN AND CHIP, BLOCK, POINTER TO HEADER
`OF EARLIER REV.
`OF EARLIER REV.
`
`320
`320
`
`IS CHIP PAIR (cid:9)
`IS CHIP PAIR
`CONTAINING THAT
`CONTAINING THAT
`LOCATION
`LOCATION
`BUSY?
`
`BUSY?
`
`322 --\
`
`322
`
`YES
`YES
`
`NO
`NO
`
`324 f
`
`[324
`
`V
`'I
`
`SET DIRTY BITS OF
`sET DIRTY BITS OF
`ATI'RIBUTE WORD TO Ib
`ATTRIBUTE WORD TO ch
`
`CACHE THE CHIP PAIR,
`CACHE THE CHIP PAIR,
`BLOCK AND OFFSET
`BLOCK AND OFFSET
`
`326
`
`RETURN
`
`ey-} 326
`
`—FIG (cid:9) 1
`E‘ I E _ 1 E
`"ENABLE CSM"
`"ENABLE CSM"
`
`,--- 340
`/ 340
`
`NO
`NO
`
`CSM1 : ACTIVE?
`
`II
`ENABLE CSM1
`ENABLE CSM1
`(SET CSM1.STATUS TO ACTIVE)
`(SET CSM1.STATUS TO ACTIVE)
`
`362
`362
`
`YES
`YES
`
`V
`CSM1 NEXT STATE =
`CSM1 NEXT STATE =
`EVALUATE IF CLEANUP
`EVALUATE lF CLEANUP
`IS NEEDED
`IS NEEDED
`
`364
`/364
`
`"
`
`361
`361
`
`RETURN
`RETURN
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0013
`
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`0a. 13, 1998
`Oct. 13, 1998 (cid:9)
`
`Sheet 13 0f 22
`Sheet 13 of 22 (cid:9)
`
`5,822,781
`5,822,781
`
`co
`Cr)
`
`wwm \
`
`:
`
`EXECUTE ONE STATE
`
`3% \,
`
`>
`
`P _io_
`DD
`MZ
`Lil <
`OW
`11-10
`0
`LL
`
`FORCE CLEANUP
`
`ENABLE CSM
`
`CLEANUP SERVICES
`
`
`
`win |H-H|H.|
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0014
`
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`0a. 13, 1998
`Oct. 13, 1998 (cid:9)
`
`Sheet 14 0f 22
`Sheet 14 of 22 (cid:9)
`
`5,822,781
`5,822,781
`
`—E-1 G 16
`"EXECUTE ONE STATE"
`"EXECUTE ONE STATE"
`
`366
`
`346
`346
`K
`
`NO
`NO
`
`CSM2 = ACTIVE’?
`
`NO
`
`CSM1 = ACTIVE?
`
`368 X
`
`EXECUTE CSM2.NEXTSTATE
`
`EXECUTE CSM1.NEXTSTATE
`
`374
`
`RETURN
`
`—Jr' I G (cid:9) 1-7 "STATES OF CLEAN-UP STATE MACHINE"
`1: I E: _ 17 "STATES OF CLEAN-UP STATE MACHINE"
`
`380
`380
`
`NO
`
`EVALUATE IF
`CLEANUP
`NEEDED
`
`382
`
`382 \
`
`YES
`
`CHOOSE BLOCK TO CLEANUP
`CHOOSE BLOCK To CLEANUP
`
`10 KEEP EXECUTING
`KEEP EXECUTING
`UNTIL BLOCK CHOSEN
`UNTIL BLOCK CHOSEN
`
`383
`383
`
`BLOCK
`BLOCK
`SELECTED
`SELECTED
`
`NO MORE SECTORS TO COPY OUT
`NO MORE SECTORS TO COPY OUT
`
`390
`390
`v /
`START ERASE
`START ERASE I
`
`NEED TO
`NEED TO
`ALLCCATE FREE
`ALLOCATE FREE
`PHYSICAL
`PHYSICAL
`MEMORY?
`MEMORY?
`COPY SECTOR TO
`COPY SECTOR TO I
`384 SECTOR (cid:9) BUFFER
`SECTOR BUFFER
`384
`Q
`l \ 385
` \ 385
`ALLOCATE I--
`ALLCCATE
`386 n
`ERASE NOT
`ERASE NOT
`386
` COMPLETE
`392
`\ F— COMPLETE
`" f 392
`COPY PART 0|: SECTOR 6 WAIT FOR ERASE COMPLETE
`WAIT FOR ERASE COMPLETE I
`COPY PART OF SECTOR
`ERASE
`T
`ERASE
`COMPLETE
`POSTCOPY DATABASE UPDATE I
`v COMPLETE
`— POSTCOPY DATABASE UPDATE
`
`y
`SET CSM
`SET CSM (cid:9)
`TO IDLE
`TO IDLE
`
`
`
`396 \
`396 \ 388
`388
`
`POSTERASE DATABASE UPDATE H
`POSTEHASE DATABASE UPDATE ->
`\
`394
`394
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0015
`
`(cid:9)
`(cid:9)
`(cid:9)
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`0a. 13, 1998
`Oct. 13, 1998 (cid:9)
`
`Sheet 15 0f 22
`Sheet 15 of 22 (cid:9)
`
`5,822,781
`5,822,781
`
`11C
`E‘ I E _ 1 3
`"EVALUATE WHETHER CLEAN-UP
`"EVALUATE WHETHER CLEAN-UP
`IS NECESSARY"
`IS NECESSARY"
`tz-- 380
`380
`1/
`
`400
`400
`
`BLOCKS TO
`BLOCKS T0
`CLEANUP > 0?
`CLEANUP > 0?
`
`NO
`N0
`
`401
`401
`K
`CSM NEXT STATE =
`CSM NEXT STATE :
`CHOOSE BLOCK TO CLEANUP
`CHOOSE BLOCK TO CLEANUP
`
`YES
`
`\ (cid:9)
`
`409
`\ T
`SET CSM
`S$E1TS§¥O
`STATUS TO
`IDLE
`IDLE
`
`V
`
`402
`402
`I f
`CALCULATE TOTAL DIRTY
`CALCULATE TOTAL D|RTY
`AS PERCENTAGE OF TOTAL
`AS PERCENTAGE OF TOTAL
`REsERvEs
`RESERVES
`
`404
`404
`
`NQ
`NO
`
`PERCENTAGE
`PERCENTAGE
`OF DIRTY EXCEED
`OF DIRTY EXCEED
`TRIGGER
`TRIGGER
`POINT
`POINT
`406
`\ YES
`YES
`BLOCKS TO CLEANUP COUNT =
`BLOCKS TO CLEANUP COUNT =
`NUMBER OF BLOCKS TO CLEAN
`NUMBER OF BLOCKS TO CLEAN
`
`408
`408
`
`"
`CSM.NEXTSTATE =
`CSM.NEXTSTATE =
`CSM_CHOOSE BLOCK TO
`CSM_CHOOSE BLOCK TO
`CLEANUP
`CLEANUP
`I
`
`410
`410
`
`—JrI G (cid:9) 19 "ADAPTIVE ADJUSTMENT OF
`I I E — 1 5‘ "ADAPTIVE ADJUSTMENT OF
`CLEAN-UP TRIGGER"
`sTART
`CLEAN-UP TRIGGER"
`START (cid:9)
`
`412
`
`HAVE
`THERE BEEN
`SOME NUMBER OF
`SOME NUMBER OF
`FOREGROUND
`FOREGROUND
`CLEAN-UPS IN LAST
`CLEAN-UPS IN LAST
`M WRITES?
`M WRITES?
`
`414
`
`YES
`
`DECREASE TRIGGER POINT
`DECREASE TRIGGER POINT
`BY SOME DELTA
`BY SOME DELTA
`
`NO
`
`416
`416
`
`NO
`NO
`
`HAS
`THERE NOT BEEN A
`THERE NOT BEEN A
`FOREGROUND ERASE IN
`FOREGROUND ERASE IN
`THE LAST N WRITES?
`THE LAST N WRITES?
`
`418
`YES f 418
`YES
`
`INCREASE TRIGGER POINT
`INCREASE TRIGGER POINT
`BY SOME DELTA
`BY SOME DELTA
`
`420
`420
`
`RETURN
`RETURN
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0016
`
`

`
`U.S. Patent
`U.S. Patent
`
`Oct. 13, 1998
`Oct. 13, 1998
`
`Sheet 16 of 22 (cid:9)
`Sheet 16 0f 22
`
`5,822,781
`5,822,781
`
`G (cid:9)
`I ILI "CHOOSE BLOCK TO CLEAN-UP"
`1: I [i __ 2 I] "CHOOSE BLOCK TO CLEAN-UP"
`382
`K 382
`
`440
`440
`
`1
`
`ALL CHIPS SEARCHED
`ALI- CHIPS SEARCHED
`LOOP UNTIL ALL CHIP
`LOOP UNT L ALL CHIP
`PAIRS SEARCHED /
`PAIRS SEARCHED
`ALL CHIPS
`ISSL'IEICHED
`ALL BLOCKS
`NOT SEARCHED
`SEARCHED
`444
`SEARCHED
`"
`444
`LQQP UNT|L
`LOOP UNTIL
`ALL BLOCKS ON CH":
`ALL BLOCKS ON CHIP
`PAIR SEARCHED
`PAIR SEARCHED
`
`45s
`458
`v /
`WRITE CHIP PAIR AND BLOCK
`WRITE CHIP PA R AND BLOCK
`WITH GREATEST SCORE
`WITH GREATEST SCORE
`INTO FOCUS WINDOW
`INTO FOCUS WINDOW
`
`445
`
`NO
`
`V
`RULE 0 = CHIP PAIR
`RULE O = CHIP PAIR
`TARGETED FOR ERASE*
`TARGETED FOR ERASE*
`WEIGHTO
`WEIGHTO
`
`446
`446
`
`448
`448
`
`449
`449
`
`II
`RULE 1 = AMOUNT DIRTY*
`RULE 1 = AMOUNT DIRTY*
`WEIGHT1
`WEIGHT1
`I
`4,
`RULE 2 =
`RULE 2 =
`FREE FLASH ON SAME CHIP
`FREE FLASH ON SAME CHIP
`PAIR* WEIGHT2
`PAIR* WEIGHT2
`I
`4,
`RULE 3 =
`RULE 3 =
`LAST CHIP PAIR ERASED*
`LAST CHIP PAIR ERASED*
`WEIGHT3
`WEIGHT3
`I
`450
`450 \
`RULE 4 =
`RULE 4 =
`(BYTE PER BLOCK — CLEAN
`(BYTE PER BLOCK - CLEAN
`WORDS THIS BLOCK)*
`WORDS THIS BLOCK)*
`WEIGHT4
`WEIGHT4
`
`451
`
`I
`RULE 5 =
`A CYCLE COUNT*
`WEIGHT5
`I
`1
`TOTAL SCORE =
`TOTAL SCORE =
`RULE 1 — RULE 2 — RULE 3
`RULE1 — RULE2 — RULE3
`+ RULE 4 + RULE 5 — RULE 0
`+ RULE4 + RULE5 — RULEO
`
`452
`
`452 \
`
`460
`460
`I /
`CSM NEXTSTATE =
`CSM NEXTSTATE =
`ALLOCATE FREE PHYSICAL
`ALLOCATE FREE PHYSICAL
`SECTOR
`SECTOR
`
`462
`462
`
`( RETURN
`
`TOTAL SCORE =
`TOTAL SCORE =
`GREATEST
`GREATEST
`SCORE?
`SCORE?
`
`NO
`
`456 'x
`SAVE BLOCK AND CHIP PAIR
`SAVE BLOCK AND CHIP PAIR
`INFO AND TOTAL SCORE
`INFO AND TOTAL SCORE
`
`APPLE INC.
`EXHIBIT 1205 - PAGE 0017
`
`

`
`U.S. Patent (cid:9)
`U.S. Patent
`
`0a. 13, 1998
`Oct. 13, 1998 (cid:9)
`
`Sheet 17 of 22 (cid:9)
`Sheet 17 0f 22
`
`5,822,781
`5,822,781
`
`—SIG Z 1
`"CSM ALLOCATE FREE
`TI I; _ 2 1 "CSM ALLOCATE FREE
`PHYSICAL SECTOR
`PHYSICAL SECTOR
`
`z-- 384
`/ 384
`480
`
`480 /
`
`CSM.NEXTSTATE =
`CSM.NEXTSTATE =
`START ERASE
`START ERASE
`
`472
`472
`
`VALID
`VALID
`SECTOR LEFT
`SECTOR LEFT
`IN FOCUS BLOCK?
`IN FOCUS BLOCK?
`
`NO
`
`474
`YES
`CALL SECTORS_ALLOCATE /
`CALL SECTORS_ALLOCATE
`FREE PHYSICAL SECTOR
`FREE PHYSICAL SECTOR
`
`\ CSM.NEXTSTATE =
`CSM.NEXTSTATE =
`COPY SECTOR TO SECTOR
`COPY SECTOR TO SECTOR
`BUFFER
`BUFFER
`
`476 (cid:9)
`476
`
`478
`478
`
`RETURN
`
`I: I [i _ 2 3 "COPY SECTOR TO SECTOR BUFFER"
`—lir I L (cid:9)
`"COPY SECTOR TO SECTOR BUFFER"
`.k„---- 385
`480 K 385
`‘
`r 480
`/
`COPY SECTOR DATA TO SECTOR BUFFER
`COPY SECTOR DATA TO SECTOR BUFFER
`l
`1
`CSM.NEXTSTATE = COPY PART OF SECTOR
`CSM.NEXTSTATE = COPY PART OF SECTOR
`if
`
`
`
`482
`/ 482
`
`/ 484
`
`I? I I; __ 34 "COPY PART OF SECTOR"
`--ir 11 L7 (cid:9)
`At "COPY PART OF SECTOR" (cid:9)
`
`.- 386
`386
`1/
`
`496