United States Patent
`Niijima et al.
`
`[19]
`
`[11] Patent Number:
`[45] Date of Patent:
`
`5,457,658
`Oct. 10, 1995
`
`V|||||l|||||||||l|l||||||Il||l|||||IlIllllllllllllllllllllllllllllIIIIHIII
`USO05457658A
`
`[54] NONVOLATILE MEMORY WITH
`CLUSTER-ERASE FLASH CAPABILITY AND
`SOLID STATE FILE APPARATUS USING
`THE SAME
`
`Primary Examiner—Tcrrell W. Fears
`Attorney, Agent, or Firm—Mattliew J. Bussan
`
`Inventors: Hideto Niijima, Tokyo; Hideo Asano,
`Machida; Yoshinori Sakaue, Tokyo;
`Takashi Toyooka, Kawasaki, an of
`Japan
`
`[73] Assignee:
`
`International Business Machines
`Corporation, Armonk, N.Y.
`
`[21] App1_ No_; 200,343
`[22]
`Filed:
`Feb. 23’ 1994
`[30]
`Foreign Application Priority Data
`
`Feb. 24, 1993
`
`[IP]
`
`Japan .................................. .. 5-035228
`
`Int. Cl.6 ..................................................... G11C 13/00
`[51]
`[52] U-S- CL ..............
`. 365/213; 361/1529
`[53] Field Of Search ............................... 365/230.(;é,5/291086
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`[57]
`A
`
`ABSTRACT
`-
`.
`fl h
`- h 1
`_
`-1
`1,
`as capability. A
`nonvo ati e memory wit
`c uster erase
`cluster information sector is included in each of N clusters,
`the cluster information sector of each cluster being written
`with the sequence number assigned to the cluster so that no
`two clusters have the same sequence number. When erasing
`
`a given sector, a controller saves its sequence number prior
`to erasure. Then, when initializing a given erased sector, the
`controller sets its sequence number to a value greater than
`the current maximum sequence number. The controller
`writes user data to sectors other than the cluster information
`
`sector for the cluster thus initialized according to their
`address sequence. Accordingly, an invalid sector can be
`distinguished from a valid Sector without using an overwrite
`approach.
`
`5,327,383
`
`,7/1994 Merchant et al.
`
`...................... 365/218
`
`17 Claims, 12 Drawing Sheets
`
`14
`
`15
`
`21
`
`coprocessor
`
`Main storage
`
`Solid state
`(SSF)
`file annaratus
`
`ggflgglcatio"
`
`BUS
`COHUOI IBF
`
`Central
`arbitration
`control
`circuit
`
`_
`DISDIHY
`device
`
`24
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0001
`
`

`
`U.S. Patent
`
`Oct. 10, 1995
`
`Sheet 1 of 12
`
`5,457,658
`
`T3
`n:
`
`< o
`
`:
`9.
`n:
`9.:
`
`9 u
`
`.
`
`
`
`Address_translatlontable
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0002
`
`

`
`U.S. Patent
`
`091Ll-CO
`
`59911
`
`Sheet 2 of 12
`
`PmqKOEEN.o_.._
`
`
`
`Suficoflmmwcmb
`
`mmEuu<
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0003
`
`

`
`U.S. Patent
`
`Oct. 10, 1995
`
`Sheet 3 of 12
`
`5,457,658
`
`coprocessor
`
`Main storage
`
`Solid state
`file apparatus
`(SSF)
`
`gg$?2giCat1°"
`
`0ptical_
`fxle un1t
`
`Bus
`Controller
`
`_
`Central
`arbltratlon
`control
`c1rcu1t
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0004
`
`

`
`U.S. Patent
`
`Oct. 10, 1995
`
`5
`
`Sheet 4 of 12
`
`5,457,658
`
`Controller
`
`Address
`transla-
`tio" ”"it
`
`Flash memory
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0005
`
`

`
`U.S. Patent
`
`59910:1LCO
`
`Sheet 5 of 12
`
`5,457,658
`
`
`
`
`
`
`
`mm_m:o_umeLo»:_uzzou_oae=:
`
`
`
`
`
`mu=a_guu<pcoeoumcmsLmzuoumm.o.mum=_umucoacmm
`
`
`
`
`
`mu=n_.uu<
`
`
`
`mm_%mumu.mw=
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0006
`
`

`
`U.S. Patent
`
`Oct. 10, 1995
`
`Sheet 6 of 12
`
`5,457,658
`
`Sequence Cluster Other
`number
`erase
`manage—
`count
`ment
`1nf9r—
`mat1on
`
`Attri-
`bute
`
`Cluster
`
`# 1
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0007
`
`

`
`U.S. Patent
`
`Oct. 10, 1995
`
`Sheet 7 of 12
`
`5,457,658
`
`Determine cluster to be
`erased (cluster X)
`
`Copy valid data of cluster
`X to another cluster
`
`Save sequence number of
`cluster X and cluster erase
`count
`
`Erase cluster X
`
`84
`
`Require
`
`N0
`
`Yes
`
`Initialization
`(Figure 9)
`
`85
`
`FIG. 8
`
`86
`
`.
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0008
`
`

`
`U.S. Patent
`
`Oct. 10, 1995
`
`Sheet 8 of 12
`
`5,457,658
`
`Determine cluster C to be initialized
`
`Find current maximum seuuence number M.
`and wrlte M+1 as sequence number of
`cluster C
`
`Save M+1 as maximum sequence number
`
`90
`
`92
`
`write value added with 1 to saved erase
`count of cluster C as erase count of
`cluster C
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0009
`
`

`
`U.S. Patent
`
`Oct. 10, 1995
`
`Sheet 9 of 12
`
`5,457,658
`
`Start
`
`Initialize address
`translation table
`
`100
`
`Read all cluster information
`sectors
`
`101
`
`Sort sequence numbers in
`ascendlng order
`
`192
`
`Select first sorted cluster
`
`103
`
`Read sectors in that
`cluster in order of
`address
`
`write physical address of that
`sector 1n address translation
`table by referencing RP of
`.that sector
`
`106
`
`of sector
`?
`
`Yes
`
`E
`of c?35ter
`9
`
`Select next cluster
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0010
`
`

`
`U.S. Patent
`
`Oct. 10, 1995
`
`Sheet 10 of 12
`
`5,457,658
`
`Sequence number table
`
`Address translation table
`
`Cluster Dfiint
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0011
`
`

`
`U.S. Patent
`
`Oct. 10, 1995
`
`Sheet 11 of 12
`
`5,457,658
`
`Start
`
`Initialize address
`translation table
`
`121
`
`Cluster number
`
`(C) = 1
`
`122
`
`Read cluster
`information sector
`
`123
`
`Register sequence number in
`sequence number table
`
`12”
`
`Sector number (8) = 2
`
`Read sector with cluster number C and
`sector number S
`
`Read entry of address translation table
`Dointed by RP
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0012
`
`

`
`U.S. Patent
`
`Oct. 10, 1995
`
`Sheet’ 12 of 12
`
`5,457,658
`
`Find sequence number of cluster to
`which already registered sector
`belongs by referencing sequence
`number table
`
`Is
`found cluster
`number smaller than
`cluster number
`C?
`
`Register physical address of
`(C. 8) Sector in address
`translation table
`
`of sector
`?
`
`Yes
`
`132
`
`FIG. l2B
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0013
`
`

`
`5,457,658
`
`1
`NONVOLATILE MEMORY WITH
`CLUSTER-ERASE FLASH CAPABILITY AND
`SOLID STATE FILE APPARATUS USING
`THE SAME
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`The present invention relates to a nonvolatile memory
`with cluster—erasc flash capability called a flash EEPROM
`(hereinafter referred to as a flash memory), and more par
`ticularly to a solid state file apparatus which can dynami-
`cally allocate sectors.
`2. Description of Prior Art
`As portable personal computers, such as notebook-types,
`have spread, the requirement for small—size, light weight,
`and low power consumption computer
`systems has
`increased. An external storage device or solid state file using
`solid state memories has a low power consumption and can
`operate at high speed because, unlike a magnetic disk
`apparatus,
`it does not have a mechanical drive system.
`Further, since it is composed of small memory modules, it
`is small in size, light in weight, and has a large degree of
`freedom with respect to shape as compared with a magnetic
`disk apparatus, and is also easily made in the form of a card.
`However, the conventional solid state memory has many
`problems with respect to such points as cost, capacity, and
`battery backup. If SRAMs are used as the memory, the cost
`is high and hence the capacity becomes small though the
`backup time by a battery becomes long. For DRAMs, which
`are excellent in cost and capacity, the standby power con-
`sumption is large and the backup time is limited to one week
`or so. There is also a problem of data loss due to problems
`in the battery system. EEPROMS are costly though they
`require no battery.
`A flash memory has been developed as a memory to solve
`these problems. Its memory element is composed of one
`transistor as a DRAM so that it can be packaged at high
`density, and it is expected to have a bit cost equivalent to or
`less than a DRAM (low cost, large capacity), depending on
`the future market. The memory element is nonvolatile and
`does not require battery backup. Erasure is generally per-
`formed for each chip for each smaller block. The outline of
`such a flash memory is introduced by Richard D. Pashley et
`al.
`in “Flash Memories:
`the best of two worlds,” [BEE
`SPECTRUM, December 1989, pp. 30-33. As far as perfor-
`mance is concerned, the block erase type is superior to the
`chip erase type.
`When the block erase type flash memory is used for a
`solid state file, it is convenient to memory management if the
`size of a block is made equal to a sector, which is a unit of
`access in the magnetic disk apparatus. European Patent
`Application 392895,
`for
`example, discloses
`a
`flash
`EEPROM system of the sector erase type. The system makes
`it possible to simultaneously erase any plural sectors by
`providing a latch for each sector, which is a unit of erasure,
`and setting a latch corresponding to a sector to be erased.
`Also known is a flash memory whose unit of erasure is a
`block having a size equivalent to a plurality of sectors (e. g.
`4K bytes). This is sometimes called the cluster erase type to
`distinguish it from the sector erase type.
`However, the flash memory has limitations which SRAMs
`and DRAMs do not have. First, the programming of memory
`bits is a one-way process and change is allowed only from
`0 to l or from 1 to 0. Therefore, when new data is to be
`
`2
`written to a memory location which has already been written
`on, writing should be performed after a block including that
`memory location has been erased to the all 0 or all 1 state.
`It is usually takes from several
`tens of milliseconds to
`several seconds for erasure and writing. Further, the flash
`memory is deteriorated by erasure and writing and reaches
`a usage limit, at present, after several tens of thousands to
`several hundreds of thousands of erasures and writings.
`If such a flash memory is used for a solid state file, a
`problem arises in that writing is based to a portion of the
`memory if the same logical sector is allocated to the same
`physical sector. For example,
`in a DOS-based personal
`computer system, a file allocation table (FAT) is frequently
`updated. However, since the FAT address is fixed, a block
`storing the FAT has to be erased and then written each time
`the FAT is updated, in the case of a flash memory, and it
`takes several tens of milliseconds to several seconds each
`time. If a particular block which is a portion of memory is
`frequently erased and written, that block reaches the use
`limit faster than other blocks, and therefore, the memory
`needs to be replaced even if the other blocks can still be
`used. Early replacement of the memory could be avoided if
`the block which has reached its use limit is invalidated and
`an alternative block is used instead. However, this means
`that a block on which writing is concentrated is merely
`changed to an alternative block, and therefore, does not
`provide a radical solution.
`Then, Japanese Pat. Appln. No. 3-197318 has succeeded
`in solving these problems by employing dynamic sector
`allocation. The method is briefly described referring to
`FIGS. 1 and 2. An address translation table is created in a
`RAM. By referencing the table, an address (logical address)
`specified by the host processor is translated to an address
`(physical address) specifying a sector (physical sector) of a
`solid state file apparatus (SSF). That is, the host processor
`specifies a location to be written with data by a logical
`address consisting of a head number, a cylinder number, and
`a sector number. A physical address corresponding to the
`logical address is stored in an entry identified by a logical
`address in the address translation table. Each sector of the
`SSF to be specified by the physical address contains an area
`for storing a reverse reference pointer (RP) and an area for
`storing the status of the sector in addition to the data area for
`storing data.
`Now, it is assumed that, when the SSF receives a write
`command regarding a logical address (H, C, S)=(l, 4, 5)
`from the host processor, a sector Y, which is empty until
`then, is allocated to the logical address. A controller of SSF
`writes data in the data area of the physical sector Y, and
`writes an RP area (1, 4, 5) to set the ‘sector valid’ flag in the
`status area. At the same time, a physical address ABC is
`written in an entry X in the translation table identified by the
`logical address (1, 4, 5). Thereafter, whenever reading of
`data from the logical address (1, 4, 5)
`is requested, the
`physical address ABC is accessed by using the address
`translation table (see FIG. 1).
`When the SSF again receives from the host processor a
`write command to the logical address (H, C, S)=(l, 4, 5), the
`controller of SSF invalidates the physical data Y, and allo-
`cates a physical, which is empty until then, to the logical
`address (1, 4, 5). For example, the entry X in the address
`translation table is rewritten to ABD, data is written in the
`data area of a sector Z at the physical address ABD in the
`SSF, (l, 4, 5) is written in the RP area, and a flag is set in
`the status area indicating that it is valid. At the same time,
`a flag is set in the status area of the sector Y indicating that
`it is invalid.
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0014
`
`

`
`5,457,658
`
`3
`Then, because the address translation table is lost when
`the system is turned ofl”, it is required to be reconstructed
`when the system is turned on again. In such a case, the
`physical address of that sector is registered in an entry in the
`address translation table specified by the reverse reference
`pointer. If one or more sectors have the same RP as shown
`in FIG. 2, the physical addresses of valid sectors are regis-
`tered. Thus, the valid/invalid information on a sector of the
`SSF is essential to the reconstruction of the address trans-
`lation table which is the key to the dynamic allocation.
`On the other hand, as described earlier, because data
`cannot be written in a sector contained in a block unless it
`is erased, it is generally difficult to update the status of
`sector. Against
`this problem, patent application No.
`3-197318 discloses a method in which the “blank,” “valid,”
`“invalid” or “being erased” state of each sector is indicated
`by changing the status flag bit from “l1ll”—>“lllO"—>
`1l00”—>0000” based on the property of some of flash
`memories that, when the bit change is limited to only one
`direction, it is overwritable. However, some NAND type
`flash EEPROMS cannot be overwritten at all, to which the
`method using the status bit cannot be used.
`
`SUMMARY OF THE INVENTION
`
`The object of this invention is to provide a nonvolatile
`memory with cluster—erase flash capability for which the
`valid sectors can be found without using the overwriting
`method, and a solid state file apparatus using the same.
`The nonvolatile memory with cluster-erase flash capabil-
`ity according to the present invention comprises N clusters,
`each comprising M sectors, wherein M and N are integers
`greater than one; each of said N clusters has a cluster
`information sector; sequence numbers are given to said N
`clusters in such a way that no two sectors have the same
`sequence number; and each cluster holds a sequence number
`given thereto in its cluster information sector. The solid state
`file apparatus according the present invention comprises
`such a nonvolatile memory with cluster-erase flash capabil-
`ity and a controller. To perform dynamic allocation, the
`controller maintains an area in a random access memory for
`an address translation table, selects a sector upon a write
`request from a processor, and writes a physical address of
`the selected sector into an entry of the address translation
`table as well as the given logical address into the selected
`sector as a reverse pointer.
`When erasing a given cluster, the controller saves its
`sequence number in a nonvolatile storage area such as
`another cluster previous to the erasure. Then, when initial-
`izing a given erased cluster, the controller sets the sequence
`number of the given cluster to a value more than a current
`maximum sequence number.
`The controller writes user data to sectors other than the
`cluster information sector for the cluster thus initialized
`according to their address sequence.
`When the controller reconstructs the address translation
`table, it reads M><N sectors of the nonvolatile memory, and
`writes the physical addresses of those sectors into entries of
`the address translation table specified by their reverse
`pointer. If a plurality of sectors have the same reverse
`pointer, it writes the physical address of the most recently
`written sector into said address translation table according to
`the sequence number of the cluster to which it belongs and
`the position in the cluster.
`
`When each cluster information sector is previously writ-
`ten with the erase counts of the clusters, including that
`
`4
`
`cluster itself, and the maximum sequence number is set
`equal to the sum of the erase counts of all the clusters, the
`erase counts are saved together with the sequence number
`when erasing a cluster. Then, when an erased cluster is
`initialized, the erase count of that cluster already stored is
`increased, in a manner similar to the sequence number, and
`written back into the cluster information sector. When the
`address translation table is reconstructed,
`the maximum
`sequence number is checked for agreement with the sum of
`the erase counts of all the clusters by utilizing the fact that
`all cluster information sectors have been read. Thus, it can
`found whether the integrity of data is maintained.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a diagram for explaining the dynamic sector
`allocation disclosed in Japanese Pat. Appln. No. 3-197318;
`FIG. 2 is a diagram for explaining the dynamic sector
`allocation disclosed in Japanese Pat. Appln. No. 3-197318;
`FIG. 3 is a block diagram showing an example of a
`computer system including a solid state file apparatus
`according to the present invention;
`FIG. 4 is a diagram showing a schematic configuration of
`the solid state file apparatus;
`FIG. 5 is a diagram showing a configuration of a cluster
`information sector;
`FIG. 6 is a diagram showing a configuration of a sector
`other than the cluster information sector (data sector);
`FIG. 7 is a diagram for setting of the initial value of the
`cluster information sector;
`FIG. 8 is a flowchart showing an operation of a controller
`in erasing a cluster;
`FIG. 9 is a flowchart showing an operation of the con-
`troller in initializing an erased cluster;
`FIG. 10 is a flowchart showing an example of operation
`of the controller in reconstructing the address translation
`table;
`
`FIG. 11 is a diagram showing a relationship between an
`address translation table and a sequence number table; and
`FIG. 12 is a flowchart showing an example of operation
`of the controller in reconstructing the address translation
`table.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`FIG. 3 shows an example of a computer system in which
`a flash memory according to the present invention is incor-
`porated as a solid state file apparatus. A CPU 10 commu-
`nicates, through a system bus 13, with a main storage 15, a
`bus controller 16, and an optional math coporoccssor 14.
`Communications between the CPU 10 and peripheral equip-
`ment are performed through the bus controller 16. To this
`end, the bus controller 16 is connected, through a family bus
`18, to the peripheral equipment. A solid state file apparatus
`(SSF) 20 made of the flash memory according to the present
`invention, a communication device 21, a floppy disk drive
`(FDD) 22, an optical file unit 23, and a display device 24 are
`connected to the family bus 18 as peripheral equipment. Of
`course, other peripheral equipment may also be connected.
`An example of such a computer system is the IBM PS/2
`(registered trademarks of International Business Machines
`Corporation) personal computer.
`A direct memory access controller (DMAC) 12 is pro-
`vided to enable memory access by all or some selected
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0015
`
`

`
`5,457,658
`
`5
`peripheral equipment. To this end, at least a portion of the
`family bus 18 is branched to the DMAC 12. Each peripheral
`device which is allowed direct memory access (DMA) is
`provided with an arbitration circuit, though not shown in the
`drawing, and is assigned an arbitration level (priority). In
`association with the DMAC 12, a central arbitration control
`circuit 11 is provided which arbitrates among a plurality of
`peripheral equipment simultaneously making requests to
`DMA and informs the DMAC 12 which peripheral equip-
`ment is granted the DMA. Details of the DMA control by the
`DMAC 12 and the central arbitration control circuit 11 are
`described in U.S. Pat. No. 4,901,234.
`The CPU 10 uses the SSF 20 as a hard disk drive.
`Therefore, when the SSF 20 is accessed, a relative block
`address (RBA) comprising a head number, a cylinder num-
`ber, and sector number, is sent to the SSF 20. The SSF 20
`performs dynamic sector allocation. Therefore, the relation-
`ship between the RBA provided by the CPU 10 and an
`address (physical address) of a block of the SSF 20, which
`is actually accessed, is not fixed and varies each time writing
`is performed. Then, an address translation table is provided
`for indicating the relationship. That is, the RBA from the
`CPU 10 is a logical address.
`FIG. 4 shows a schematic configuration of the SSF 20.
`The SSF 20 comprises a controller 30 connected to the
`family bus 18, and an interna.l bus 31 consisting of a random
`access memory (RAM) 32, a bus control element 33 and a
`flash memory 34. The RAM 32 includes an area 35 for
`storing the address translation table, and a bulfer area 36. In
`addition,
`the RAM 32 includes an area for storing the
`maximum sequence number (M), which is described later.
`The bus control element 33 has the well—known reeeiverl
`driver configuration for interconnecting the internal bus 31
`and a memory bus 37 connected to the flash memory 34.
`In this embodiment, the sector size specified by the CPU
`10 is 512 bytes, while the size of a physical sector, which is
`the minimum access unit of the CPU 10 to the SSF 20, is 512
`bytes+ot (see FIGS. 5 and 6). When a 16 Mbit flash memory
`is used, one physical sector uses two word lines in a flash
`EEPROM. That is, two pages constitute one sector. A sector
`(physical sector) of the SSF 20 is managed as follows.
`1) A logical set
`is created for which actual erasure is
`performed, and which is called a cluster. The cluster
`consists of one or more blocks each of which is a physical
`erasure unit. In the embodiment, eight sectors constitute
`one block, and eight blocks constitute one cluster. Each
`cluster is provided with a cluster information sector which
`holds areas for the cluster erase count and sequence
`number. The cluster erase count and the sequence number
`are saved as part of the management information in the
`cluster information sector. In the embodiment, a sector
`positioned at the top physical address of each cluster is
`assigned to the cluster information sector.
`FIG. 6 shows the configuration of sectors other than the
`cluster information sector of each cluster (hereinafter called
`“data sectors”). As shown, a data sector includes an area for
`storing an attribute and an error correction code (ECC) in
`addition to a data area for storing 512 byte user data.
`Here, it should be noted that, unlike Japanese Pat. Appln.
`No. 3-197318, the sector does not have a status area in which
`the valid/invalid flag is set. The attribute commonly included
`in each sector is used for identifying whether or not the
`sector is the cluster information sector.
`2) In the initialize process of the flash EEPROM in fabri-
`cation, an initial sequence number is provided for each
`cluster so that they do not overlap each other.
`It
`is
`preferable to provide such a condition that the sum of the
`
`6
`erase count for all clusters equals the maximum sequence
`number.
`As shown in FIG. 7, it is assumed that the SSF has N
`clusters, and each cluster is assigned cluster numbers from
`1 to N. (Actually, the cluster number is specified by the sum
`of high order bits.) An SSF initialization program executed
`by a computer in a plant sets the cluster erase count of each
`cluster to “l At the same time, it writes
`as the sequence
`number for a cluster at the cluster number i so that the
`sequence numbers do not overlap each other.
`Although, in this example, 1 is given as the initial value
`of the cluster erase count, the present invention can be also
`implemented in a case where an actual erase count is written.
`In addition, although in this example the order of initial
`values of sequence numbers are matched to that of the
`cluster numbers, the present invention is not limited to such
`numbering system of the initial sequence number, but the
`initial sequence numbers may be given regardless of the
`cluster number.
`
`The condition necessary to determine the validity or
`invalidity of a sector is that the sequence numbers do not
`overlap with each other. In the embodiment, it is further
`established that the maximum value of sequence number
`(maximum sequence number) equals the sum of the erase
`counts of each cluster. The above two conditions should be
`satisfied at any time during operation of the SSD, except for
`when a cluster is being erased. In the example shown in FIG.
`7, the sum of cluster erase counts is N and the maximum
`value of sequence number is also N so that the conditions are
`satisfied.
`If, in the example of FIG. 7, the cluster erase count of
`cluster N is 2 and that of other clusters is 1, the above two
`conditions will be satisfied by assigning the sequence num-
`bers 1 to N—l
`to the clusters 1 to N—l, and the sequence
`number N+l to the cluster N.
`3) The operation of the controller 30 in erasing a cluster
`(FIG. 4) will be explained by referring to FIG. 8. First, a
`cluster to be erased is determined. Although there are
`various methods, it is usual to determine a cluster as the
`one to be erased when the number of valid sectors for that
`cluster gets below a fixed value (step 80). If the cluster to
`be erased is X, the controller copies the valid data of X to
`a data sector in another cluster (step 81).
`To execute steps 80 and 81, it is necessary to determine
`the validity or invalidity of sectors. It is sufficient to refer-
`enee the entry in the address translation table pointed by the
`reverse pointer of a given sector, and to check whether or not
`the address written in that entry matches the address of that
`sector. If so, the sector is valid, otherwise it is invalid. Step
`81 detects valid sectors in such a manner. In addition, it
`checks the number of valid and invalid sectors once, records
`the result in a table (not shown) provided in the RAM 32
`(FIG. 4), and updates the table every time subsequent
`writing is performed. Then, a cluster to be erased can be
`determined by regularly referencing the table‘.
`Next, the controller copies the cluster information sector
`of the cluster X into another suitable cluster or a nonvolatile
`storage area such as a RAM with battery backup to save the
`current sequence number and erase count of the cluster X
`(step 82). Then, the cluster X is erased (step 83). If it is
`necessary to initialize an erased cluster, that is, if there is no
`cluster with completely blank data sector, it is immediately
`initialized (step 85). Otherwise, the SSF performs a normal
`operation (Step 86). Initialization as referred to here means
`to write a sequence number in the erased cluster so as to
`enable the data sector to be written into.
`The operation of the controller 30 (FIG. 4) in initializing
`the erased cluster will be explained by referring to FIG. 9.
`
`APPLE INC.
`EXHIBIT 1106 - PAGE 0016
`
`

`
`5,457,658
`
`7
`First, the controller selects the one with the minimum cluster
`erase count from one or more which have been erased but
`not yet initialized (step 90). The selected cluster is called C.
`Next, the current maximum sequence number M is found,
`and a value M+l (M added with 1 thereto) is written as the
`sequence number of the cluster C in the cluster information
`sector of that cluster (step 91). In this case, because the
`maximum sequence number M is stored in the area 38 of the
`RAM 32, it is accessed. In step 92, the value M+1 is written
`in the area 38.
`
`Thereafter, in step 93, the erase count stored in step 82 is
`read when erasing the cluster C, and a value added with l
`thereto is written in the cluster information sector of the
`cluster C. The cluster management information saved when
`erasing the cluster C is written as it is as that other than the
`sequence number, the cluster erase count, and ECC.
`The control flow shown in FIGS. 8 and 9 is merely an
`example, and can be modified in various manners. For
`example, an erased cluster may be immediately initialized.
`In such a case, the process immediately jumps from step 83
`of FIG. 8 to step 91 of FIG. 9. Then, the cluster erase count
`and the sequence number of the erased cluster, as well as the
`maximum sequence number saved in the RAM vary as
`follows.
`
`Cluster erase count
`Sequence number
`Maximum sequence number
`
`Value prior
`to erasure
`
`Value after
`initialization
`
`E
`S
`M
`
`E + 1
`M + 1
`M + 1
`
`In the above example, a value added with 1 to the current
`maximum sequence number is written in the cluster infor-
`mation sector. In short, it is suflicient to write a value larger
`than the current maximum sequence number M and it is not
`necessary to limit the increment to one.
`4) Writing into a sector uses a dynamic allocation method.
`However, unlike Japanese Pat. Appln. No. 3—l973l8, it
`does not set valid/invalid flags. Sectors in the same cluster
`are written in ascending or descending order of address.
`In the embodiment, because the cluster information sector
`is placed at the top of the cluster, data is written into the
`sector in ascending order of address, but, if it is placed at
`the end of a cluster, data is written in the sector in
`descending order of address.
`Until writing is complete for one cluster, that is, until all
`the sectors in the cluster are used, or it is decided that the rest
`of the cluster is to be left unused, data is not written into
`other clusters. If all sectors within a cluster are bad, writing
`of data is terminated therein. Such termination can be
`determined because bad sector information is previously
`written in a part of the flash memory 34 in the initialize
`process in SSF fabrication.
`Initially, user data is written into the cluster according to
`the initial sequence number assign in 2), but, once data is
`written into all the clusters, writing is performed in the
`cluster with the maximum sequence number through the
`erasure and initialization processes.
`Generally,
`it
`is easy to distinguish valid sectors from
`invalid sectors if the sequence of all sectors in time order can
`be determined. However, it is practically impossible to write
`time sequence information in all the clusters because area
`overhead of the information is too large. The present inven-
`tion maintains this time sequence information by two-level
`hierarchies,
`the cluster
`and the sector. Clusters
`are
`sequenced by sequence numbers in cluster information
`
`8
`sectors due to the erasure method described in 3). Sectors are
`sequenced by the locations where they are in their clusters
`due to the write method described in 4). By combining them,
`the sequence of all sectors in temporal order can be uniquely
`determined and the area overhead of the temporal informa-
`tion becomes very small.
`5) At the time when the system is powered-up, the address
`translation table is reconstructed while determining the
`validity or invalidity of sectors with the sequence number
`in the cluster and the location of sectors in the cluster. If
`there are a plurality of physical sectors for a specific
`logical sector, it is judged that the one in the cluster with
`the greatest sequence number is valid. If two or more
`physical sectors exist for one logical sector, a valid sector
`for the logical sector is settled by the time series infor-
`mation.
`Two methods are possible to attain the above. The first
`method is that which first sorts the sequence numbers and
`then scans the clusters in the sorted order. The second
`method is that which creates a sequence number table in a
`RAM. The former is fast and advantageous in various
`aspects once the sorting is complete. However, all
`the
`sequence numbers must be read prior to the sorting. There-
`fore,
`the cluster management information is read twice.
`Furthermore, because a large work area is generally required
`to perform sorting at high speed, the cost of the SSF may be
`increased depending on the status.
`The process flow of the first method will be explained by
`referring to FIG. 10. First, the area of the address translation
`table is held in the RAM so as to initialize the value of each
`entry at a specific value (for example, 0) (step 100). Then,
`all cluster information sectors are read and sorted in the
`ascending order of sequence number (steps 101 and 102).
`Thereafter, clusters are selected from the lowest sequence
`number, and the sectors in the selected cluster are read in the
`order of address. In the embodiment, the sectors are sequen-
`tially read from the cluster information sector in ascending
`order of address. The physical address of that cluster is
`written in the entry of the address translation table pointed
`by the reverse pointer of the read sector. Even if an address
`of another sector has been written in the entry, the address
`of the sector just read is written (steps 103-108).
`The sequence number table used for the sec