`
`WO 03/027828 Al
`
`1111111111111111 IIIIII 111111111111111111111111111111 lllll lllll 11111111111111111111111
`
`European patent (AT, BE, BG, CH, CY, CZ, DE, DK, EE,
`ES, FI, FR, GB, GR, IE, IT, LU, MC, NL, PT, SE, SK,
`TR), OAPI patent (BF, BJ, CF, CG, CI, CM, GA, GN, GQ,
`GW, ML, MR, NE, SN, TD, TG).
`
`before the expiration of the time limit for amending the
`claims and to be republished in the event of receipt of
`amendments
`
`Published:
`with international search report
`
`For two-letter codes and other abbreviations, refer to the "Guid(cid:173)
`ance Notes on Codes and Abbreviations" appearing at the begin(cid:173)
`ning of each regular issue of the PCT Gazette.
`
`Micron Ex. 1050, p. 2
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`1
`
`METHOD OF WRITING DATA TO NON-VOLATILE MEMORY
`
`The present invention relates to a method of writing
`
`data to non volatile memory and in particular to a method
`
`of writing data to flash memory in order to ensure the
`
`uniform distribution of use over a prolonged period of
`
`operation.
`
`In
`
`known memory
`
`systems
`
`it is
`
`common
`
`for non
`
`volatile memory such as
`
`the flash memory of the memory
`
`systems ta-bave wear out mechanisms within their physical
`
`structures which mean
`
`that
`
`a block within
`
`the
`
`flash
`
`memory may experience failure after a cumulative number
`
`of operations. However,
`
`known data management methods
`
`typically do not perform block erasure in Flash memory in
`
`real time leading to the accumulation of blocks in Flash
`
`memory which contain obsolete versions of sectors. It is
`
`also the case that in known systems the physical address
`
`for writing a sector is dependant on the logical address
`
`of the sector thus logically non-contiguous sectors are
`
`written in non-contiguous physical address and logical to
`
`physical.
`
`In particular . an object of the present invention is
`
`to reduce the number of read and write accesses
`
`to the
`
`Micron Ex. 1050, p. 3
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`2
`
`PCT/GB02/04381
`
`non-volatile memory for control data structures, thereby
`
`increasing the write speed of the memory system for host
`
`data.
`
`A second object of the invention is t.o obtain even
`
`use of blocks in the non-volatile memory for storage of
`
`data over a
`
`long period of operation, and to avoid "hot(cid:173)
`
`spots" in non-volatile memory usage,
`
`thereby increasing
`
`the reliability of the memory system.
`
`According to a first aspect of the invention, there
`
`is provided a controller connected
`
`to a non-volatile
`
`memory and including a volatile memory, wherein
`
`the controller maintains lists in volatile memory of
`
`blocks in the non-volatile memory allovated for storage
`
`of logical sector data and of block:s recently erased in
`
`the non-volatile memory
`
`the controller transfers information from the lists
`
`in volatile memory to control data structures in the non(cid:173)
`
`volatile memory less frequently than the contents ·of the
`
`lists in volatile memory ?re changed
`
`such
`
`that
`
`the
`
`lists
`
`in volatile memory can be
`
`reconstructed at any time from existing informaion in the
`
`non-volatile memory.
`
`Preferably,
`
`information from
`
`the lists in volatile
`
`memory is transferred to control data struci:ures in the
`
`non-volatile memory concurrently with logical to physical
`
`Micron Ex. 1050, p. 4
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`3
`
`mapping
`
`information
`
`for sectors
`
`from other
`
`lists
`
`in
`
`volatile memory.
`
`According to a second aspect of the invention, there
`
`is provided a controller connected
`
`to a non-volatile
`
`memory and including a volatile memory, wherein
`
`the controller maintains a first list of all blocks
`
`in the non-volatile memory which are in the erased state
`
`and which are not included in other lists
`
`the controller maintains a second list of,blo~ks in
`
`the non-volatile memory which have beery recently erased.
`
`These and other aspects of the invention will become
`
`apparent
`
`from
`
`the
`
`following
`
`description
`
`taken
`
`in
`
`combination with
`
`the
`
`following drawings
`
`in which
`
`is
`
`shown:
`
`Figure 1
`
`-
`
`a host system and flash memory system
`
`arrangement which the present invention is implemented;
`
`Figure
`
`2
`
`the
`
`hardware
`
`architecture of
`
`the
`
`controller of the system of Figure 1 in which the .present
`
`invention is implemented;
`
`Figure 3
`
`the
`
`layered
`
`firmware structure which
`
`performs the media management operations according to the
`
`present invention;
`
`Figure 4a
`
`-
`
`schematic representation of
`
`the write
`
`operation according to the present invention;
`
`Micron Ex. 1050, p. 5
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`4
`
`PCT/GB02/04381
`
`Figure 4b
`
`-
`
`.schematic representation of the write
`
`and relocate operations of the present invention;
`
`Figure 5
`
`-
`
`a schematic representation of the three
`
`level hierarchy of mapping structures of
`
`the address
`
`translation process according to the present invention;
`
`Figure 6
`
`-
`
`a schematic representation of the data
`
`structures in the memory system of the present invention;
`
`Figure 7 -
`
`a schematic representation of the control
`
`..
`operations of the memory system according to the present
`
`invention;
`
`Figure 8 -
`
`a schematic representation of the flow of
`
`operations of the address translation operation of the
`
`present invention;
`
`Figure 9 - A schematic representation of the control
`
`write operation of
`
`the memory system according
`
`to the
`
`present invention;
`
`Figure 10
`
`-
`
`a schematic representation of the EBM
`
`sector write function operation of the memory system of
`
`the present invention;
`
`Figure 11 -
`
`a schematic representation of the state
`
`of
`
`the data structures at
`
`the sta~t of a map write
`
`operation;
`
`Figure 12 -
`
`a schematic representation of the state
`
`of the data structures following the CSL map operation;
`
`Micron Ex. 1050, p. 6
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`5
`
`Figure 13 -
`
`a schematic representation of the state
`
`of
`
`the data
`
`structures
`
`following
`
`·the ABL
`
`and CBL
`
`compaction operation;
`
`Figure 14
`
`-
`
`a schematic representation of the state
`
`of
`
`the data
`
`structure
`
`following
`
`the map
`
`to CBL
`
`operation;
`
`Figure 15 -
`
`a schematic representation of the state
`
`of
`
`the data
`
`structures
`
`following
`
`the CBL
`
`to
`
`EBL
`
`operation;
`
`Figure 16 -
`
`a schematic representation of the state
`
`of
`
`the data
`
`structures
`
`following
`
`· the EBL
`
`to ABL
`
`operation;
`
`Figure
`
`17
`
`a
`
`schematic
`
`representation of
`
`an
`
`al terna ti ve host system and flash system in which
`
`the
`
`present invention may be implemented.
`
`A Flash disk device, such as that shown in Figure 1,
`
`is
`
`a
`
`memory
`
`system which
`
`presents
`
`the
`
`logical
`
`characteristics of a disk storage device to a h6st· system
`
`1 2 , and which uses Flash semiconductor memory 20 as its
`
`physical data storage medium. A Flash disk memory system
`
`10
`
`requires
`
`a controller 12
`
`to manage
`
`the physical
`
`storage medium of the system 10 according to algorithms
`
`which create the logical characteristics of a disk and,
`
`in this case, it is the flash memory 20 and controller 16
`
`which are connected by physical interface 16 which form
`
`Micron Ex. 1050, p. 7
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`6
`
`the memory system 10. The controller 16 of
`
`the memory
`
`system 10 connects
`
`the system 10
`
`to
`
`the host 12 via
`
`logical interface 14.
`
`In
`
`this case
`
`the
`
`flash memory
`
`20
`
`comprises
`
`a
`
`plurality of flash chips which are formed of a plurality
`
`of flash blocks. The logical interface 14
`
`to the memory
`
`system 10 allows data to be written to and read from the
`
`system 10
`
`in
`
`fixed-size units called sectors,
`
`each
`
`containing 512 bytes of data, ~hich can b~
`
`ri~domly
`
`accessed. Each sector is identified by a logical address
`
`which in this case is a sequential Logical Block Address
`
`( LBA) .
`
`In the present arrangement data may be written to a
`
`sector even if the sector already contains data.
`
`The
`
`protocols at the logical interface 14 can, in this case,
`
`support, read or write access to the system 10 in multi(cid:173)
`
`sector blocks of logically contiguous sector addresses,
`
`these protocols conform
`
`to
`
`industry standards such as
`
`ATA, CompactFlash, or ~ultiMediaCard
`
`thus allowing
`
`the
`
`memory system 10 to be interchangeable between different
`
`host systems and not limited to use with host 12.
`
`The physical
`
`interface 18
`
`from controller 16
`
`to
`
`Flash Memory 2 0 allows data to be written
`
`to and read
`
`from Flash memory 20
`
`in fixed-size units which in this
`
`Micron Ex. 1050, p. 8
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`7
`
`case are called physical sectors and each of which can be
`
`a·cces sed randomly with each typically having sufficient
`
`capacity for 512 bytes of data from the host system plus
`
`16 bytes of overhead data appended by the controller 16.
`
`Each physical sector is identified by a physical sector
`
`address, which normally has separate components which
`
`respectively identify the Flash chip within
`
`the memory
`
`subsystem, the Flash block within the Flash chip, and the
`
`physical sector within the Flash block of the' mem·ory 20
`
`to which the physical sector is written.
`
`Within the system 10 shown, data may only be written
`
`to a physical sector if the sector has previously been
`
`eras .ed. The Flash memory 20 is erased in response to a
`
`command at the physical interface in uni ts of a Flash
`
`block, which typically contains 32 physical sectors. The
`
`relative times for performing operations within the Flash
`
`system 10 to read a physical sector, program a physical
`..
`typically . in
`
`sector, and erase a Flash block are
`
`the
`
`ratio 1
`
`: 20
`
`: 200.
`
`In the arrangement of Figure 1 the controller 16 is
`
`a Cyclic Storage controller which
`
`is
`
`a Flash media
`
`management controller
`
`in which
`
`a method of ensuring
`
`uniformity of distribution of use is implemented wherein
`
`the media management algorithms which
`
`implement
`
`this
`
`Micron Ex. 1050, p. 9
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`8
`
`method are implemented as firmware by a processor within
`
`the controller.
`
`With reference to Figure 2 there.is shown optimized
`
`hardware architecture which
`
`is defined for
`
`the Cyclic
`
`Storage controller 16.
`
`In
`
`this case
`
`the controller
`
`hardware
`
`is
`
`a dedicated architecture
`
`in
`
`a
`
`separate
`
`integrated circuit.
`
`The controller 16 comprises host interface control
`
`block-
`
`22, microprocessor 24,
`
`flash
`
`interface control
`
`block 26, ROM 28, SRAM 30 and expansion port 32, each of
`
`these being inter-connected by memory access control bus
`
`34.
`
`Cyclic Storage Flash media management plgorithms are
`
`implemented by firmware running on microprocessor 24 and
`
`the controller 16 is responsible for all Flash media
`
`management functions and for the characteristics of the
`
`logical interface 14 presented to host 12.
`
`The host
`
`interface control block 22 provides
`
`the
`
`path for data flow to and from host system 12 via logical
`
`interface 14.
`
`As,
`
`in this case,
`
`the controller 16 is in the form
`
`of a dedicated
`
`integrated circuit
`
`the host
`
`interface
`
`control block 2 2 provides
`
`logical
`
`interface 14 which
`
`conforms to an industry standard protocol as well as a
`
`Micron Ex. 1050, p. 10
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`9
`
`command
`
`register and set of
`
`taskfile registers which
`
`provide the route for
`
`the microprocessor 24
`
`to control
`
`the logical characteristics of the interface 14.
`
`The host interface control block 22 also allows for
`
`a sector of data to be transferred in either direction
`
`across
`
`the
`
`logical
`
`interface 14 between
`
`to
`
`the host
`
`system 12 and the controller's SRAM 30 by a direct memory
`
`access
`
`(DMA)
`
`operation without
`
`intervention
`
`from
`
`the
`
`microprocessor 24.
`
`The Flash interface control block 26 provides
`
`the
`
`path for data
`
`flow
`
`to and
`
`from Flash memory 20,
`
`and
`
`controls all operations which
`
`take place
`
`in
`
`the Flash
`
`memory 20.
`
`The operations taking pL~ce in Flash memory
`
`20 are defined and initiated by the microprocessor 24,
`
`which
`
`loads parameter and address
`
`information
`
`to
`
`the
`
`flash interface control block 26.
`
`The set of operations which typically take place are
`
`the transfer of a physical sector to Flash memory 20, the
`
`transfer of a physical sector from Flash memory 2 0,
`
`the
`
`programming of a physical sector into flash memory 20,
`
`the erasing of a Flash block, and
`
`the reading of
`
`the
`
`status of flash memory 20.
`
`Similarly
`
`a
`
`physical
`
`sector of data may
`
`be
`
`transferred
`
`in either direction across
`
`the physical
`
`Micron Ex. 1050, p. 11
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`10
`
`interface
`
`16
`
`between
`
`the Flash memory
`
`20
`
`and
`
`the
`
`controller's
`
`SRAM
`
`30
`
`by
`
`OMA
`
`operations without
`
`intervention
`
`from
`
`the microprocessor
`
`24.
`
`The
`
`organization of the 512 bytes of host data and 16 bytes
`
`of overhead data within
`
`a physical sector which
`
`is
`
`transferred to Flash memory 20 is determined within the
`
`Flash interface control block 26, under the control of
`
`parameters loaded by the microprocessor 24.
`
`The Flash interface control block 26 also generates
`
`a
`
`12-byte
`
`error
`
`correcting
`
`code
`
`(ECC)
`
`which
`
`is
`
`transferred to Flash memory 20 and programmed as overhead
`
`data within each physical sector,
`
`and which
`
`is also
`
`verified when a physical sector is transferred from Flash
`
`memory 20.
`
`The microprocessor 24 controls
`
`the
`
`flow of data
`
`sectors
`
`through
`
`the memory
`
`access control bus,
`
`or
`
`datapath,
`
`34 or of
`
`the controller 16,
`
`implements
`
`the
`
`Flash media management algorithms which define the sector
`
`and control data storag~ organisation in the Flash memory
`
`20,
`
`and defines
`
`the a characteristics of
`
`the
`
`logical
`
`interface
`
`14
`
`to host
`
`system 12.
`
`In
`
`this case
`
`che
`
`microprocessor 24 is a 32-bit RISC processor.
`
`The memory access control bus 34 allows transfe_r of
`
`information between the microprocessor 24, host interface
`
`Micron Ex. 1050, p. 12
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`11
`
`PCT/GB02/04381
`
`control block 22, and the Flash interface control blocks
`
`16, as well as between the host interface control block
`
`22,
`
`the flash interface control block 26 and a memory
`
`block 30 . .
`
`The microprocessor 24, host interface control block
`
`22, and Flash interface control block 26 may each be the
`
`master for a transaction on the memory access control bus
`
`34.
`
`Bus access is granted to requesting masters on a
`
`cycle-by-cycle basis.
`
`The SRAM block 30 stores all temporary information
`
`within the controller 16, this storing function includes
`
`the buffering of sector data and storage of control data
`
`structures and variables, as well as firmware code.
`
`The ROM
`
`28
`
`is. included
`
`in
`
`the controller 16
`
`for
`
`storage of code for execution by the microprocessor 2 4,
`
`or of
`
`information
`
`required by other hardware blocks
`
`within the controller.
`
`The inclusion in the controller architecture of an
`
`expansion port
`
`32 gives access
`
`to external hardware
`
`functions, RAM or ROM
`
`from the memory system 10.
`
`During
`
`the operation of
`
`the controller all sector
`
`data being transferred between the logical interface 14
`
`to host system 12, and the physical interface 18 to Flash
`
`memory
`
`20
`
`is buffered
`
`in
`
`the
`
`SRAM
`
`30.
`
`.Sufficient
`
`Micron Ex. 1050, p. 13
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`12
`
`capacit y in the SRAM 30 is allocated for buffering of two
`
`sectors
`
`of data
`
`to
`
`allow
`
`concurrent
`
`transfers
`
`of
`
`successive sectors at the host and Flash interfaces. Data
`
`transfer between
`
`the logical host interface 14 and SRAM
`
`30 is performed by OMA with
`
`the host interface control
`
`block 22 acting as bus master. Data transfer between the
`
`physical Flash interface 18 and SRAM 30 is performed by
`
`DMA with the Flash interface control block 2 6 acting as
`
`bus master.
`
`As the controller 16 is in the form of a dedicated
`
`integrated circuit, the host interface control block 22
`
`provides
`
`a
`
`logical
`
`interface which
`
`conforms
`
`to
`
`an
`
`industry standard protocol, and a command register and
`
`set of
`
`taskfile registers provide
`
`the
`
`route
`
`for
`
`the
`
`microprocessor 24
`
`to control the logical characteristics
`
`of
`
`the
`
`interface 14.
`
`Command, address and parameter
`
`information is written to these task file registers by
`
`the host 12,
`
`and
`
`read by
`
`the microprocessor · 24
`
`for
`
`execution of the command.
`'
`
`Information is also be written
`
`to the registers by the microprocessor 24 for return to
`
`the host 12.
`
`In Figure
`
`3
`
`there
`
`is
`
`illustrated
`
`the
`
`layered
`
`structure of
`
`the
`
`firmware which performs
`
`th~ Cyclic
`
`Storage flash media management operations. The firmware
`
`Micron Ex. 1050, p. 14
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`13
`
`PCT/GB02/04381
`
`has
`
`three
`
`layers,
`
`the first being
`
`the host
`
`in te rf ace
`
`layer 40,
`
`the
`
`second
`
`layer 42 comprising
`
`the sector
`
`transfer sequencer 42a and the media management layer 42b
`
`and the third being the flash control layer 44.
`
`These three firmware layers 40,42 and 44 control the
`
`transfer of data sectors between the l~gical interface 14
`
`to host 12 and the physical interface 18 to Flash memory
`
`20. However,
`
`the firmware
`
`layers do not directly pass
`
`data,
`
`instead data
`
`sectors
`
`are
`
`transferred by
`
`the
`
`hardware blocks of the controller 16 and therefore do not
`
`pass through the microprocessor 24.
`
`The host
`
`interface
`
`layer
`
`40
`
`supports
`
`the
`
`full
`
`command set
`
`for
`
`the host protocol.
`
`It
`
`interprets
`
`commands at the host interface 14, controls the logical
`
`behaviour
`
`of
`
`the
`
`interface
`
`14
`
`according
`
`to host
`
`protocols, executes host commands not associated with the
`
`transfer of data, and passes host commands which relate
`
`to data
`
`in Flash memory
`
`to be
`
`invoked
`
`in
`
`the layers
`
`below. Example of such commands are.
`
`I
`
`Read logical sector (single or multiple),
`
`Write logical sector (single or multiple),
`
`Erase iogical sector
`
`( single or multiple) , as well
`
`as other disk formatting and identification commands.
`
`Micron Ex. 1050, p. 15
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`14
`
`The
`
`sector
`
`transfer
`
`sequencer
`
`42a
`
`receives
`
`interpreted commands
`
`relating
`
`to
`
`logical data sectors
`
`from
`
`the host interface layer 40 and
`
`thus
`
`invokes
`
`the
`
`Flash media management layer 42b for logical to physical
`
`transformation operations, and invokes the Flash control
`
`layer for physical sector transfers· to or
`
`from Flash
`
`memory. The sector transfer sequencer 42a also perform
`
`sector buffer memory management. Another function of the
`
`sequencer
`
`42a
`
`is
`
`to create
`
`a
`
`sequence of
`
`sector
`
`transfers, at
`
`the host
`
`interface 14 and Flash memory
`
`interface 18, and a sequence of operations in the media
`
`management
`
`layer 42b,
`
`in accordance with
`
`the command
`
`received from the host 12 and the level of concurrent
`
`operations which is configured for the Flash memory 20.
`
`The media management layer 42b performs the logical
`
`to physical transformation operations which are required
`
`to support the write, read or erasure of a single logical
`
`sector. This layer is responsible for the implementation
`
`of Cyclic Storage media management algorithms.
`
`The Flash control
`
`layer 44 configures
`
`the Flash
`
`interface control block 26 hardware to execute operations
`
`according to calls from the sector transfer sequencer 42a
`
`or media management layer 42b.
`
`Micron Ex. 1050, p. 16
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`15
`
`The media management functions which are implemented
`
`within
`
`the media management layer 4 2b of the controller
`
`firmware create
`
`the
`
`logical characteristics of a disk
`
`storage device in the memory system 10 which uses Flash
`
`semiconductor memory 20 as
`
`the physical data storage
`
`medium.
`
`The effectiveness of the media management performed
`
`by the media management functions of the media management
`
`layer
`
`42b
`
`is measured by
`
`its speed
`
`for performing
`
`sustained writing of data to the memory system 10, its
`
`efficiency in maintaining its level of performance when
`
`operating with different file systems, and in this case,
`
`in host 12, and the long-term reliability of the Flash
`
`memory 20.
`
`Data write speed is defined as the speed which can
`
`be sustained when writing a
`
`large volume of contiguous
`
`data to the memory system 10.
`
`In some cases, when
`
`the
`
`sustained data write rate of a memory system is being
`
`tested,
`
`the volume of data to be written may exceed the
`
`capacity of the memory system 10 and therefore logical
`
`addresses may be repeated.
`
`Sustained write speed is determined by
`
`the sector
`
`data transfer speed at the logical interface U
`
`to the
`
`host 1 2 , and the physical interface 18
`
`to Flash memory
`
`Micron Ex. 1050, p. 17
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`16
`
`PCT/GB02/04381
`
`20, as well as
`
`the overhead percentage of accesses
`
`to
`
`Flash memory 20 at the physical interface 18 for Flash
`
`page
`
`read and write operations . and Flash block erase
`
`operations which are not directly associated with storage
`
`of data sectors written by
`
`the host 12 at the logical
`
`interface 14.
`
`In this case the control data structures
`
`and algorithms which are employed should ensure
`
`that
`
`access
`
`to Flash memory 20
`
`for control
`
`functions
`
`is
`
`required at a much
`
`lower frequency than for host sector
`
`write. The sustained write speed is also determined by
`
`the processing time within .the controller 16 for media
`
`management operations,
`
`and
`
`the page
`
`read and program
`
`times, and block erase times within the Flash memory 20.
`
`In
`
`order
`
`for
`
`the memory
`
`system
`
`to
`
`operate
`
`efficiently when having
`
`file
`
`systems with different
`
`characteristics, the Media management algorithms for the
`
`organization of host data and control-data structures on
`
`Flash · memory 20 are appropriately defined and data write
`
`performance is maintained in each environment.
`
`In a first embodiment, the file systems implementing
`
`the MS-DOS standard are provided with at least one of the
`
`following characteristics:
`
`the host
`
`12 writing data
`
`sectors in clusters using multiple sector write commands;
`
`the host 12 writing data sectors using single sector
`
`write commands;
`
`the host 12 writing some sectors with
`
`Micron Ex. 1050, p. 18
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`17
`
`PCT/GB02/04381
`
`single sector write commands in an address space which is
`
`shared with clustered file data; the host 12 writing non(cid:173)
`
`contiguous sectors for MS-DOS directory and FAT entries
`
`with single sector write commands;
`
`the host 12 writing
`
`non-contiguous
`
`sectors
`
`for MS-DOS directory and
`
`FAT
`
`entries
`
`interspersed with contiguous sectors for file
`
`data; and/or
`
`the host may rewrite sectors for MS-DOS directory
`
`and FAT entries on a frequent basis.
`
`It is a feature of flash memory, and in this case
`
`the Flash memory 20 of the memory system 10, that it has
`
`a wear-out mechanism within the physical structure of its
`
`cells whereby a block of flash memory may experience
`
`failure
`
`after
`
`a
`
`cumulative
`
`number
`
`of
`
`operations.
`
`Typically, this is in the range of 100,000 to 1,000,000
`
`program/erase cycles.
`
`In
`
`light of
`
`this
`
`the cyclic
`
`storage
`
`controller
`
`16
`
`of
`
`the
`
`p~esent
`
`arrangement
`
`implements
`
`a process of wear-leveling
`
`to ensure
`
`that
`
`"hot-spots" do not occur in the physical address space of
`
`the Flash memory 20 and that utilization of Flash blocks
`
`is uniformly distributed over a prolonged period of
`
`operation.
`
`The Cyclic Storage media management algorithms 2.re
`
`implemented within memory system 10 and perform the Media
`
`management operation of
`
`the physical Flash memory 2 0
`
`Micron Ex. 1050, p. 19
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`18
`
`PCT/GB02/04381
`
`within the system 10. The cyclic storage media management
`
`algorithms comprise four separate algorithms, namely the
`
`Data Write algorithm which controls
`
`the
`
`location
`
`for
`
`writing host
`
`information to,
`
`the Block Erase algorithm
`
`which controls erasure of areas of Flash memory 20
`
`containing obsolete
`
`information,
`
`the Block Sequencing
`
`algorithm which controls
`
`the sequence of use of Flash
`
`blocks
`
`for
`
`storing
`
`information,
`
`and
`
`the Address
`
`Translation algorithm which controls the mappiflg of host
`
`logical addresses to physical memory addresses.
`
`The method of Cyclic Storage media management
`
`implemented by
`
`these algorithms embodies
`
`the principle
`
`that data is written at physical sector
`
`locations
`
`in
`
`Flash memory 20 which
`
`follow
`
`the
`
`same order as
`
`th~
`
`sequence in which the data is written. This is achieved
`
`by writing each logical data sector at a physical sector
`
`position defined by a cyclic write pointer.
`
`A schematic representation of the· write operation of
`
`the cyclic storage media management method · is shown
`
`I
`
`in
`
`Figures 4A.
`
`The write pointer, in this case data write
`
`pointer
`
`(DWP)
`
`4 6 moves sequentially through
`
`the sector
`
`positions of Flash block X
`
`in Flash memory 20,
`
`and
`
`continues through the chain of blocks Y and Zin a manner
`
`defined by the block sequencing algorithm. Each block X,
`
`Micron Ex. 1050, p. 20
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`19
`
`PCT/GB02/04381
`
`Y and Z is a physical structure in Flash memory 20 which,
`
`in this case, comprises 32 sector loca ti ans which can be
`
`erased in a single operation.
`
`Logical data sectors are generally writ ten in files
`
`by a file system in the host 12, and the Cyclic Storage
`
`Data Write Algorithm locates the first sector of a file
`
`at the next available physical sector position following
`
`the last sector of the preceding file. When a file is
`
`written by host 12 using logical sectors for w'hich· valid
`
`data already e x ists in the device, the previous versions
`
`of the sectors become obsolete and the blocks containing
`
`them are erased according to the Block Erase Algorithm.
`
`In order
`
`to erase
`
`a block containing obsolete file
`
`sectors it is, in some cases necessary to relocate some
`
`valid sectors of another file. This generally occurs when
`
`a block contc;tins sectors of the head of a file, as well
`
`as sectors with unrelated logical addresses from the tail
`
`of a different file.
`
`A second write poi,nter in this case data relocate
`
`pointer DRP 47 is used for writing relocated sectors in
`
`order to avoid sectors of one file fragmenting a block
`
`containing sectors of another file. The use of a separate
`
`relocation
`
`pointer
`
`significantly
`
`reduces
`
`the
`
`fragmentation of blocks containing
`
`a
`
`file,
`
`leading
`
`to
`
`Micron Ex. 1050, p. 21
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`20
`
`PCT/GB02/04381
`
`minimum requirement for sector relocation and consequent
`
`maximum file write performance.
`
`A host file system is used which also writes sectors
`
`containing system information, such as directory or FAT
`
`sectors in the DOS file system, and these are generally
`
`written immediately before and after a group of sectors
`
`forming a file.
`
`A separate system pointer, system write
`
`pointer SWP 48 is used for this host file system in order
`
`to define the physical write location ior system sectors,
`
`which are identified by their logical address,
`
`in order
`
`to separate system sectors from file data sectors and
`
`a void them being treated in the same way. This ·avoids a
`
`small group of system sectors being "sandwichedn between
`
`the tail of one file and the head of another.
`
`These
`
`system sectors contain information about many files, and
`
`are generally re-written much more frequently than data
`
`for a file.
`
`"Sandwiched" system sectors would cause
`
`frequent relocation of file data sectors and thus the use
`
`of system pointer SWP ~8 minimises
`
`the requirement for
`
`data
`
`sector
`
`relocation
`
`and maximises
`
`file write
`
`performance.
`
`A fourth pointer, system relocate pointer SRP 4 9 is
`
`used for relocation of system sec;:tors, analogous
`
`to the
`
`relocation pointer DRP 47 for file data sectors.
`
`Micron Ex. 1050, p. 22
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`21
`
`PCT/GB02/04381
`
`To summarise the four write pointers are:
`
`Data write pointer, DWP 4 6 which is used to define
`
`the physical
`
`location
`
`for writing file data sectors
`
`transmitted by a host system;
`
`System write pointer, SWP 4 8 which is used to define
`
`the
`
`physical
`
`location
`
`for writing
`
`system
`
`sectors
`
`transmitted by a host · system wherein system sectors are
`
`identified by their logical address,
`
`in acco.r;s:!ance with
`
`the characteristics of the host file system in use;
`
`Data relocation pointer, DRP 47 which is used to
`
`define
`
`the physical
`
`location
`
`for writing
`
`file data
`
`sectors which must occasionally be relocated prior to a
`
`bLock erasure
`
`for
`
`recovery of capacity occupied by
`
`obsolete file data sectors; and
`
`System relocation pointer, SRP 4 9 which is used to
`
`define the physical location for writing system sectors
`
`which are being relocated prior to a block er-asure for
`
`recovery of capacity occupied by obsolete system sectors.
`
`A block must contain data associated with only a
`
`single write pointer and this results in four separate
`
`chains of blocks existing, one for each write pointer,
`
`this is shown in Figure. 4b. However, the same write and
`
`relocation algorithms of
`
`the cyclic storage algorithms
`
`apply to each write pointer 46, 47, 48 and 49.
`
`Micron Ex. 1050, p. 23
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`22
`
`PCT/GB02/04381
`
`This scheme for locating a sector to be ,vritten at
`
`the first available
`
`location
`
`following
`
`the preceding
`
`sector, combined with usage of multiple write pointers,
`
`is fully
`
`flexible,
`
`and provides high performance and
`
`total comp a tibi li ty for all host write con£ igura tions,
`
`including single sector data and data in clusters of any
`
`size.
`
`However,
`
`the Cyclic Storage media managem€nt method
`
`is defined not to allow the existence of a
`
`large number
`
`of obsolete data sectors and nor to implement background
`
`operations
`
`for
`
`functions
`
`such as garbage collection.
`
`Typically only
`
`two block containing obsolete sectors is
`
`allowed to exist for each of the Data Write Pointer DWP
`
`46 and System Write Pointer SWP 48, and block erasure is
`
`performed as a
`
`foreground operation during sector write
`
`sequences.
`
`This method of management means
`
`that
`
`the logical
`
`capacity of the flash memory does not have to be reduced
`
`to allow for the existence of a large volume of obsolete
`
`data, the data integrity is significantly improved by the
`
`absence of background operations, which are susceptible
`
`to interruption by power-down initiated by the host; and
`
`the pauses
`
`in data write sequences are short because
`
`Micron Ex. 1050, p. 24
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`23
`
`PCT/GB02/04381
`
`erase operations are required for only a single block at
`
`a time.
`
`If an obsolete data sector is created in a new block
`
`associated with either of the write pointers,
`
`then
`
`the
`
`existing
`
`"obsolete block"
`
`is eliminated by erasure,
`
`following
`
`sector
`
`relocation within
`
`the
`
`blocks
`
`if
`
`required.
`
`Erase sector
`
`commands
`
`sent
`
`from
`
`a
`
`ho.st
`
`12 are
`
`supported by· marking the target sector as obsolete, and
`
`allowing its erasure to follow acco~ding
`
`to
`
`the Block
`
`Erasure algorithm.
`
`The Cyclic Storage
`
`block
`
`sequencing
`
`algorithm
`
`determines the sequence in which blocks within the flash
`
`memory 20 are used for the writing of new or relocated
`
`data, and is therefore responsible for ensuring that no
`
`block experiences a number of write/erase cycles which
`
`exceeds
`
`the endurance
`
`limit specified
`
`for
`
`the Flash
`
`memory system 20 which is being used.
`
`When a logical sector is written by the host, any
`
`previous version which exists in the memorys system is
`
`treated as obsolete data.
`
`The block erase algorithm
`
`ensures
`
`t.hat blocks which contain obsolete data sectors
`
`are erased immediately, to allow recovery of the capacity
`
`occupied by these s