[19]
`United States Patent
`Assar et al.
`[45]
`Date of Patent:
`
`Patent Number:
`
`[11]
`
`5,479,638
`
`Dec. 26, 1995
`
`||||||||||l|l||I|||||||l|||||||||||l|||||||||||||l|||||||||l||||||Illllllll
`USOOS479638A
`
`Kai Hwang & Faye A. Briggs, “Computer Architechture and
`Parallel Processing”, McGraw—Hill, p. 64, 1984.
`T. Nozaki et a1., “A 1—Mb EEPROM with MONOS Memory
`Cell for Semiconductor Disk Application,” IEEE Journal of
`Solid—State Circuits, vol. 26, No. 4, pp. 497—501,Apr. 1991.
`S.
`Leibson,
`“Nonvolatile
`in—circuit—reprogramrnable
`memories,” EDN, Jan. 3, 1991, pp. 89—102.
`W. Lahti and D. McCarron, “Store Data in a Flash,” BYTE,
`Nov. 1990, pp. 311—318.
`D. Auclair, “Optimal Solid State Disk Architecture For
`Portable Computers,” SunDisk, presented at The Silicon
`Valley PC Design Conference, Jul. 9, 1991.
`S. Mehroura et al., “Serial 9Mb Flash EEPROM for Solid
`State Disk Applications,” 1992 Symposium on VLSI Cir—
`cuits Digest of Technical Papers, pp. 24—25.
`
`
`
`[54] FLASH MEMORY MASS STORAGE
`ARCHITECTURE INCORPORATION WEAR
`LEVELING TECHNIQUE
`
`[75]
`
`Inventors: Mahmud Assar, Morgan Hill; Siamack
`Nemazie, San Jose; Petro Estakhri,
`Pleasonton, all of Calif.
`
`0489204A1
`0509184A1
`0501289A2
`59-45695
`62—283497
`62—283496
`
`12/1990
`4/1991
`2/1992
`3/1984
`12/1987
`12/1987
`
`European Pat. 01f. .
`European Pat. 01f. .
`European Pat. Off. .
`Japan .
`Japan .
`Japan .
`OTHER PUBLICATIONS
`
`Assignee: Cirrus Logic, Inc., Palo Alto, Calif.
`
`Appl. No.: 37,893
`
`Filed:
`
`Mar. 26, 1993
`
`Int. Cl.6 ........................... .. G06F 12/02; G06F 12/14
`U.S. Cl. ........................ .. 395/430; 395/435; 395/483;
`395/412; 395/492; 395/490; 365/900; 364IDIG. l;
`364/2446; 364/2452; 364/2468; 364/255.1;
`364/249
`Field of Search ........................... .. 395/425; 365/900,
`365/218, 189.07
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,943,962
`5,043,940
`5,053,990
`5,065,364
`5,095,344
`5,134,589
`5,155,705
`5,163,021
`5,168,465
`5,172,338
`5,270,979
`5,283,382
`5,303,198
`5,337,275
`5,341,330
`5,341,339
`5,341,368
`5,353,256
`5,357,475
`5,404,485
`
`................... 365/230.08
`7/1990 Imamiya et al.
`8/1991 Harari
`..............
`365/168
`10/1991 Kreifels et a1.
`..
`395/425
`11/1991 Atwood et a1.
`..
`365/185
`3/1992 Harari
`......
`257/328
`7/1992
`365/2385
`10/1992
`365l218
`11/1992
`365/185
`12/1992
`257/320
`12/1992 Mehrotra et al.
`365/185
`12/1993 Harari et a1.
`.
`365/218
`2/1994 Smith et a1.
`395/425
`4/1994 Adachi et al.
`..... .. 365/218
`8/1994 Garner .........
`.. 365/189.01
`8/1994 Wells etal.
`365/185
`8/1994 Wells
`...........
`365/218
`8/1994 Henning et a1.
`.. 370/581
`10/1994 Fandrich et a1.
`.. 365030.03
`10/1994 Hasbun et a1.
`365/218
`4/1995 Ban ......................................... 395/425
`
`.
`.
`
`FOREIGN PATENT DOCUMENTS
`
`0424191A2
`
`9/1990 European Pat. 01f. .
`
`Primary Examiner—Eddie P. Chan
`Assistant Examiner—Reginald G. Bragdon
`Attorney, Agent, or Finn—Haverstock & Associates
`ABSTRACT
`’ [57]
`
`A semiconductor mass storage device can be substituted for
`a rotating hard disk. The device avoids an erase cycle each
`time information stored in the mass storage is changed. (The
`erase cycle is understood to include, fully programming the
`block to be erased, and then erasing the block.) Erase cycles
`are avoided by programming an altered data file into an
`empty mass storage block rather than over itself as a hard
`disk would. Periodically, the mass storage will need to be
`cleaned up. Secondly, a circuit for evenly using all blocks in
`the mass storage is provided. These advantages are achieved
`through the use of several flags, a map to directly correlate
`a logical address of a block to a physical address of that
`block and a count register for each block. In particular, flags
`are provided for defective blocks, used blocks, old version
`of a block, a count to determine the number of times a block
`has been erased and written and erase inhibit.
`
`41 Claims, 8 Drawing Sheets
`
`10‘
`msenmsmnmmn
`Au.IIDCKS "mm;ASH
`ouwrw.Fur.
`
`21»
`RECEIVEwurems-mucnou
`10 new”Masssome]:
`
`:92
`ngmwfl-H
`YES
`206
`sfiusm FLAGAND
`PROGRAMDATAFILE
`
`m5
`WflI.nATASUI'ERCEDE
`memous mu
`
`2I2
`urmrnmpmmanure
`LOGICAL moms toPHVSICAL
`mum;
`
`
`
`NetApp Exhibit 1008 Page 1
`
`

`

`Sheet 1 of 8
`
`5,479,638
`
`>m0§m§
`
`59916.,2oneD
`
`US. Patent
`
`NetApp Exhibit 1008 Page 2
`
`

`

`Sheet 2 of 8
`
`5,479,638
`
`>m02m§
`
`59916,2ceD
`
`US. Patent
`
`NetApp Exhibit 1008 Page 3
`
`

`

`Dec. 26, 1995
`
`Sheet 3 of 8
`
`5,479,638
`
`US. Patent
`
`COMMERCIAL
`
`APPLICATIONS ‘— 152
`
`NetApp Exhibit 1008 Page 4
`
`

`

`Dec. 26, 1995
`
`Sheet 4 of 3
`
`US. Patent
`
`5,479,638
`
`NetApp Exhibit 1008 Page 5
`
`

`

`US. Patent
`
`Dec. 26, 1995
`
`Sheet 5 of 8
`
`5,479,638
`
`200
`
`RECEIVE WRITE INSTRUCTION
`TO PROGRAM MASS STORAGE
`
`LOCATE BLOCK WITH
`UNSET USED/FREE
`
`204
`
`ERASE FLAGS AND DATA- FOR
`ALL BIDCKS HAVING A SET
`OLD/NEW FLAG
`
`ADDRESS
`
`212
`UPDATE MAP TO CORRELATE
`LOGICAL ADDRESS TO PHYSICAL
`
`206
`SET USED/FREE FLAG AND
`PROGRAM DATA FILE
`
`208
`
`WILL DATA SUPERCEDE
`PREVIOUS DATA
`
`210
`SET OLD/NEW FLAG ON
`SUPERCEDED BLOCK
`
`NetApp Exhibit 1008 Page 6
`
`

`

`Dec. 26, 1995
`
`Sheet 6 of 8
`
`5,479,638
`
`ERASE INHIBIT
`
`STATUS BIT
`
`ERASE COUNT
`
`US. Patent
`
`FLASH MEMORY DEVICE
`
`NetApp Exhibit 1008 Page 7
`
`

`

`Dec. 26, 1995
`
`Sheet 7 of 8
`
`5,479,638
`
`gm
`
`
`
`
`
`EUOAmZOHHQZHHmmDMOmrim,EEEZH,
`
`
`
`mMUOAm1344‘m0mo‘qfim
`
`
`
`\QmmDvJAEmmMED
`
`
`
`412mm<map/WEmmmm
`
`ova
`
`
`
`EDQmUOMEumémmHDOme
`
`
`
`
`
`UZH><EmmUOw—m33¢.mm<mmv
`
`
`
`mmémQZ<PmmDAVEBNEQAO
`
`
`
`HmmZDO<AmBREEZ—
`
`
`
`
`
`
`
`MUOAmmUDOmm0m0<4mBMZREOme
`
`US. Patent
`
`mmém92¢vim39,58Emz:93m52:5
`
`
`
`
`MDA<>HZDOUHm<m33,53M00150mm:m>02$.53MUOAm<mammalmg
`Em025$880$d<mmémmafia8,2Em93m<93BEE
`
`mm<mmmmbHmmmekAX<EVBZDOUHHZDOUfiEVHZDOUuFZDOUDZ<m:35>»M0013
`
`
`
`
`:mEZummém924.P7500mdm
`
`
`
`mmmmOEEmmZD0615mmMntflmmD
`wmmgm
`
`BEQAOgrow2mDZHHZOU
`
`NetApp Exhibit 1008 Page 8
`
`

`

`US. Patent
`
`Dec. 26, 1995
`
`Sheet 8 of 8
`
`5,479,638
`
`270
`
`RECEIVE INSTRUCTION TO
`READ MASS STORAGE
`
`271
`RECEIVE LOGICAL ADDRESS
`
`MATCHED LOGICAL ADDRESS
`
`.
`READ DATA FILE FROM THE
`PHYSICAL FILE ASSOCIATED WITH
`
`272
`
`CONCATENATE SET USED/FREE BIT AND
`UNSET NEW/OLD BIT UNSET DEFECT BIT
`
`MATCH FOUND???
`
`274
`SEND MATCH—NOT-FOUND
`SIGNAL
`
`275
`
`NetApp Exhibit 1008 Page 9
`
`

`

`described in the detailed description below.
`
`The present invention discloses two primary algorithms
`and an associated hardware architecture for a semiconductor
`mass storage device. It will be understood that data file in
`this patent document refers to any computer file including
`commercial software, a user program, word processing
`software document, spread sheet file and the like. The first
`algorithm provides means for avoiding an erase—before
`write cycle when writing a modified data file back onto the
`mass storage device. Instead, no erase is performed and the
`modified data file is written onto an empty portion of the
`mass storage. In addition, the second algorithm prevents any
`portion of the mass storage from being erased a substantially
`larger number of times than any other portion. This prevents
`any one block of the mass storage from failing and becoming
`unusable earlier than any other block thereby extending the
`life of the entire mass storage.
`The semiconductor mass storage architecture has blocks
`sized to conform with commercial hard disk sector sizes.
`The blocks are individually erasable, In one embodiment,
`the semiconductor mass storage of the present invention can
`be substituted for a rotating hard disk with no impact to the
`user, so that such a substitution will be transparent. Means
`are provided for avoiding the erase—before-write cycle each
`time information stored in the mass storage is changed. (The
`erase cycle is understood to include, frilly programming
`each bit in the block to be erased, and then erasing all the bits
`in the block.)
`According to the first algorithm, erase cycles are avoided
`by programming an altered data file into an empty mass
`storage block rather than over itself after an erase cycle of
`that block as done on a conventional hard disk. This would
`ordinarily not be possible when using conventional mass
`storage because the central processor and commercial soft-
`ware available in conventional computer systems are not
`configured to track continually changing physical locations
`of data files. The present invention includes a programmable
`map to maintain a correlation between the logical address
`408 and the physical address 408 of the updated information
`files.
`
`2
`memory condition. Unlike a hard disk device, in a flash
`memory device an erase cycle is slow which can signifi-
`cantly reduce the performance of a system utilizing flash
`memory as its mass storage.
`Though such an architecture provides a workable semi-
`conductor mass storage, there are several inefficiencies. First
`of all, each time a memory block is changed, there is a delay
`to the entire system due to the necessary erase-before—write
`cycle before reprogramming the altered information back
`into the block. The overhead associated with erase-before
`write cycles is costly in terms of system performance.
`Secondly, hard disk users typically store both information
`which is rarely changed and information which is frequently
`changed. For example, a commercial spread sheet or word
`processing software programs stored on a user’s system are
`rarely, if ever, changed. However, the spread sheet data files
`or word processing documents are frequently changed.
`Thus, different sectors of a hard disk typically have dra-
`matically different usage in terms of the number of times the
`information stored thereon is changed. While this disparity
`has no impact on a hard disk because of its insensitivity to
`data changes, in a flash memory device, this variance can
`cause sections of the mass storage to wear out and be
`unusable significantly sooner than other sections of the mass
`storage.
`
`SUMMARY OF THE lNVENTION
`
`Periodically, the mass storage will fill up because there
`have been no erase cycles. At such times, the mass storage
`needs to be cleaned up with a multi—sector erase as frilly
`
`5,479,638
`
`1
`FLASH MEMORY MASS STORAGE
`ARCHITECTURE INCORPORATION WEAR
`LEVELING TECHNIQUE
`FIELD OF THE INVENTION
`
`This invention relates to the field of mass storage for
`computers. More particularly, this invention relates to an
`architecture for replacing a hard disk with a semiconductor
`non-volatile memory and fin particular flash memory.
`BACKGROUND OF THE INVENTION
`
`Computers have used rotating magnetic media for mass
`storage of data, programs and information. Though widely
`used and commonly accepted, such hard disk drives suffer
`from a variety of deficiencies. Because of the rotation of the
`disk, there is an inherent latency in extracting information
`from a hard disk drive.
`
`Other problems are especially dramatic in portable com-
`puters. In particular, hard disks are unable to withstand many
`of the kinds of physical shock that a portable computer will
`likely sustain. Further,
`the motor for rotating the disk
`consumes significant amounts of power decreasing the bat-
`tery life for portable computers.
`Solid state memory is an ideal choice for replacing a hard
`disk drive for mass storage because it can resolve the
`problems cited above. Potential solutions have been pro-
`posed for replacing a hard disk drive with a semiconductor
`memory. For such a system to be truly useful, the memory
`must be non-volatile and altcrablc. The inventors have
`determined that flash memory is preferred for such a
`replacement. It should be noted that E2 PROM is also
`suitable as a replacement for a hard disk drive.
`Flash memory is a single transistor memory cell which is
`programmable through hot electron injection and erasable
`through Fowler-Nordheim tunneling. The programming and
`erasing of such a memory cell requires current to pass
`through the dielectric surrounding a floating gate electrode.
`Because of this, such types of memory have a finite number
`of erase-write cycles. Eventually, the dielectric will fail.
`Manufacturers of flash cell devices specify the limit for the
`number erase—write cycles as between 10,000 and 100,000.
`Accordingly, unlike rotating magnetic media, a flash
`memory mass storage device does not have an indefinite
`lifetime.
`
`Another requirement for a semiconductor mass storage
`device to be successful is that its use in lieu of a rotating
`media hard disk mass storage device be transparent to the
`system designer and the user. In other words, the designer of
`a computer incorporating such a semiconductor mass stor-
`age device could sirnply remove the hard disk and replace it
`with a semiconductor mass storage. All presently available
`commercial software should operate on a system employing
`such a semiconductor hard disk without the necessity of any
`modification.
`
`SunDisk proposed an architecture for a semiconductor
`mass storage using flash memory at the Silicon Valley PC
`Design Conference Jul. 9, 1991. That mass storage system
`included read-write block sizes of 512 Bytes (or multiples
`thereof) just like IBM PC compatible hard disk sector sizes.
`(IBM PC is a trademark of IBM Corporation.) During an
`erase cycle, an entire block is first fully programmed and
`then erased.
`
`As in conventional hard disks, it appears in the SunDisk
`architecture that there is an erase-before—write cycle each
`time data is changed in the mass storage. Thus, if a program
`or data block is to be changed, the data is written to RAM
`and appropriately changed, the flash block is fully pro-
`grammed, then erased and then reprogrammed to the new
`
`NetApp Exhibit 1008 Page 10
`
`

`

`5,479,638
`
`3
`According to the second algorithm, means are provided
`for evenly using all blocks in the mass storage. A counter
`tracks the number of times each block is erased. A prograrn—
`mable maximum value for the counter is also provided. As
`the number of erase cycles for a block becomes one less than
`the maximum, the block is erased one last time and written
`with another file having a then smallest number of erase
`cycles. It is also prevented from being erased thereafter by
`setting its erase inhibit flag. After all blocks approach this
`maximum, all the erase counters and inhibit flags are cleared
`and the second algorithm is then repeated. In this way, no
`block can be erased a substantial number of times more than
`any other block.
`These advantages are achieved through the use of several
`flags and a count register for each block. In particular, flags
`are provided for defective blocks, used blocks, old version
`of a block, a count to determine the number of times a block
`has been erased and written and an erase inhibit flag.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows an architecture for a semiconductor mass
`storage of the present invention.
`FIG. 2 shows the architecture of FIG. 1 wherein the data
`in one block has been altered and stored in a new physical
`address.
`
`FIG. 3 shows a block diagram of an erase cycle usage
`according to algorithm 1 of the present invention.
`FIG. 4 shows a simplified block diagram of the old/new
`flag system integrally formed with the memory of the
`present invention.
`FIG. 5 shows a flow chart block diagram for algorithm 1
`according to the present invention.
`FIG. 6 shows an additional architecture according to the
`preferred embodiment of the present invention.
`FIG. 7 shows a flow chart block diagram of algorithm 2
`of the present invention.
`FIG. 8 shows a flow chart block diagram of a read
`algorithm according to the present invention.
`
`4
`As described above in the Background of the Invention,
`conventional computer systems are not configured to track
`continually changing physical
`locations of data files.
`According to the present invention, each time a data file is
`changed it is stored into a new physical location in the mass
`storage. Thus, implementation of the architecture of the
`present invention requires a mapping of the logical address
`308, i.e., the address where the computer system believes the
`data file is stored to the physical address 408, i.e., the actual
`location the data file can be found is stored in the mass
`storage.
`The logical address 308 portion of the map 108 and the
`flags 112, 116 and 118 form part of the CAM 106. It is
`possible to use other storage means than a CAM to store the
`address map, such as a look-up table. However, a CAM is
`the most eflicient means known to the inventors. It is not
`necessary that the physical address 408 portion of the map
`108 form part of the CAM. Indeed, the physical address 408
`portion of the map 108 can bc ordinary flash memory,
`E2PROM or even ROM. IfROM is selected for the physical
`address 408 array of the map 108, a defect in the ROM will
`prevent the block corresponding to that physical address 408
`from ever being addressed. Accordingly, a changeable non—
`volatile memory is preferred. Note that any replacement
`circuit for the CAM should be nonvolatile. Otherwise, loss
`or removal of power to the system will result in loss of the
`ability to find the data files in the mass storage.
`Assume for example that a user is preparing a word
`processing document and instructs the computer to save the
`document. The document will be stored in the mass storage
`system as shown in FIG. 1. The computer system will assign
`it a logical address 308, for example 526H. The mass storage
`system of the present invention will select a physical address
`408 of an unused block or blocks in the mass storage 100 for
`storing the document, e.g. 728H. That map correlating the
`logical address 308 to the physical address 408 is stored in
`the CAM 106. As the data is programmed, the system of the
`present invention also sets the used/free flag 112 to indicate
`that this block has been written without being erased. The
`used/free flag 112 also forms a portion of the CAM 106. One
`used/free flag 112 is provided for each entry of the CAM
`106.
`
`a multi-.sector erase to occur. For example, if a data file
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIlVIENT
`
`FIG. 1 shows an architecture for a semiconductor mass
`storage according to the present invention. In the preferred
`embodiment, all of the memory storage is flash EEPROM.
`It is possible to substitute EZPROM for some or all of the
`data bits shown. A memory storage 100 is arranged into N
`blocks of data from zero through N—l. Each of the blocks of
`data is M Bytes long. In the preferred embodiment, each
`block is 512 Bytes long to correspond with a sector length
`in a commercially available hard disk drive. In addition to
`the memory data block 102, a flag 104 is directly related to
`each data block 102. The memory 100 can contain as much
`memory storage as a user desires. An example of a mass
`storage device might include 100 MByte of addressable
`storage.
`A non-volatile content addressable memory (CAM) 106 is
`associated with the memory storage 100. In the preferred
`embodiment, the CAM 106 is formed of flash memory. The
`CAM 106 can also be EZPROM. There is one entry in the
`CAM 106 for every one of the N blocks in the mass storage
`100. Each entry includes a number of fields which will be
`described below. The CAM 106 is also formed of a non-
`volatile memory because loss of its information would make
`retrieval of the data files stored in the mass storage 100
`impossible.
`
`Later, assume the user retrieves the document, makes a
`change and again instructs the computer to store the docu-
`ment. To avoid an erase—before—write cycle, the system of the
`present invention provides means for locating a block hav—
`ing its used/free flag 112 unset (not programmed) which
`indicates that the associated block is erased. The system then
`sets the used/free flag for the new block 114 (FIG. 2) and
`then stores the modified document in that new block 114.
`Next, the system sets the old/new flag 116 of the previous
`version of the document
`indicating that this is an old
`unneeded version of the document. Lastly,
`the system
`updates the correlation between the logical address 308 and
`the actual physical address 408. In this way, the system of
`the present invention avoids the overhead of an erase cycle
`which is required in the erase-before-write of conventional
`systems to store a modified version of a previous document.
`The writing to mass storage process outlined above is
`repeated until the entire mass storage memory 100 has been
`filled. A full mass storage is indicated by no unset used/free
`flags 112 in the CAM 106. At that time a multi-sector erase
`is necessary and those blocks in the memory 100 and their
`associated CAM 106 entries having an old/new flag 116 set
`are all erased simultaneously. Note that it is not necessary
`for 100% of the blocks to have a set used/free flag 112 for
`
`NetApp Exhibit 1008 Page 11
`
`

`

`5,479,638
`
`5
`requiring three blocks were being written and only two
`blocks having unset used/free flags 112 were available a
`multi-sector erase can be run.
`
`A simultaneous erase is not needed with prior art imple-
`mentations because those embodiments utilize an erase~
`before-write cycle rather than retaining superseded versions
`of data files. In such circuits a latch of volatile logic circuits
`is set to couple the voltage necessary to erase the flash cells
`in the block. Because of the likely large number of memory
`blocks in the mass storage 100, if the CAM 106 and mass
`storage 100 are on the same integrated circuit (chip) cou-
`pling the old/new flag 116 to the latches in parallel would
`typically be very expensive in terms of surface area of the
`chip and coupling the old/new flags 116 serially to the
`latches would be expensive in terms of system performance.
`If the CAM 106 and the mass storage 100 are on separate
`chips, it is doubtful that either device could have sufficient
`I/O capability to interconnect the old/new flags 116 to the
`latches in parallel and thus, the system would suffer from a
`serial transfer of that information for a multi—sector erase.
`
`Because of these problems it is preferable that no updat-
`ing of the latches be performed prior to an erase of all blocks
`having a set old/new flag 116. To avoid this step, a plurality
`of old/new flag systems 104 are intimately associated with
`each block in the memory 102 and is programmed by the
`same sequence of instructions as the old/new flag 116 of the
`CAM 106.
`
`maximum count and have their respective erase inhibit flags
`
`6
`If the data file is a modified version of a previously
`existing file, the system must prevent the superseded version
`from being accessed. The system determines whether the
`data file supersedes a previous data file (step 208). If so, the
`system sets the old/new flag associated with the superseded
`block (step 210). If on the other hand, the data file to be
`stored is a newly created data file, the step of setting the
`old/new flag (step 210) is skipped because there is no
`superseded block. Lastly, the map for correlating the logical
`address 308 to the physical address 408 is updated (step
`212).
`By following the procedure outlined above, the overhead
`associated with an erase cycle is avoided for each write to
`the memory 100 except
`for periodically. This vastly
`improves the performance of the overall computer system
`employing the architecture of the present invention.
`In the preferred embodiment of the present invention, the
`programming of the flash memory follows the procedure
`commonly understood by those of ordinary skill in the art.
`In other words,
`the program impulses are appropriately
`applied to the bits to be programmed and then compared to
`the data being programmed to ensure that proper program-
`ming has occurred. In the event that a bit fails to be erased
`or programmed properly, a defect flag 118 in the CAM 106
`is set preventing that block from being used again.
`In addition to saving the overhead of the erase cycle all
`but periodically, utilization of the present invention tends to
`more evenly distribute the erase cycles amongst certain
`portions of the blocks of the mass storage. FIG. 3 schemati-
`cally shows the types of information stored in utilizing a
`mass storage media 150. One portion of the mass storage
`150 contains commercial applications software 152 such as
`word processing, spreadsheet, calendaring, calculators and
`the like. These portions of the mass storage 150 rarely, if
`ever, require an erase-reprogram cycle according to the
`algorithm described above.
`A second section of the mass storage 150 contains user
`data 154. The user data 154 is frequently altered requiring
`the information to be reprogrammed into blocks of the free
`space 156 under the algorithm described above. A third
`portion of the mass storage 150 contains free space 156 of
`unprogrammed blocks.
`By following the algorithm above, the storage blocks in
`the portions 154 and 156 of the memory 150 will recycle
`data files and thus be erased and reprogrammed significantly
`more often than the commercial applications software por-
`tion 152 of the memory 150. Accordingly, the mass storage
`150 will wear out more quickly in the user data 154 and the
`free space 156 sections of the memory requiring earlier
`replacement than in sections 152 of the mass storage having
`data files which are rarely changed. As the number of free
`blocks diminishes providing a smaller number of blocks
`through which to recycle data files, the remaining blocks
`become erased more frequently exacerbating the problem.
`A second algorithm is provided for leveling erase cycles
`amongst all the blocks within the entire mass storage device
`as shown in FIG. 6. A counter is provided for each block to
`count the number of times each block has been erased and
`reprogrammed. An erase inhibit flag is also provided for
`each block. Once the erase count has reached the maximum
`for any block, the erase inhibit flag is set for that block. After
`that time that block cannot be erased until a clean-out erase
`is performed. Referring to FIG. 3, if only algorithm 1 is used
`eventually all of the blocks in the user data 154 and the free
`space 156 portions of the mass storage 150 will reach the
`
`FIG. 4 shows a simplified block diagram of the old/new
`flag system 104 which includes a non—volatile bit 120 having
`data which mirrors the old/new flag 116. In addition there is
`a volatile latch 122 coupled to receive the data in the bit 120
`from the latch during an erase cycle. At the time of an erase,
`the data in each of the bits 120 is simultaneously coupled to
`each appropriate ones of the latches 122 under control of a
`load signal coupled to each latch 122 over a load line L.
`Upon receiving a signal to perform the erase, the latch for
`every block having its associated bit 120 set then couples the
`voltage necessary to perform an erase of that block and its
`associated bit 120. After the erase is complete and verified,
`all the latches 122 are individually reset to a predetermined
`state under control of a reset signal coupled to each latch 122
`over a reset line R.
`
`For certain applications of the present invention, espe-
`cially for low Dower portable computers, a simultaneous
`erase of all blocks having their respective old/new flags set
`may be undesirable. For such applications, the blocks can be
`segregated into groups of blocks. Each group has a unique
`control line to load the latches from the nonvolatile bits. In
`this mode, during an erase cycle,
`the control
`lines are
`sequentially activated and the groups of blocks sequentially
`erased.
`
`FIG. 5 shows algorithm 1 according to the present inven-
`tion. When the system of the present invention receives an
`instruction to program data into the mass storage (step 200),
`then the system attempts to locate a free block (step 202),
`i.e., a block having an unset (not programmed) used/free
`flag. If successful, the system sets the used/free flag for that
`block and programs the data into that block (step 206).
`If on the other hand, the system is unable to locate a block
`having an unset used/free flag, the system erases the flags
`(used/free and old/new) and data for all blocks having a set
`old/new flag (step 204) and then searches for a block having
`an unset used/free flag (step 202). Such a block has just been
`formed by step 204. The system then sets the used/free flag
`for that block and programs the data file into that block (step
`206).
`
`NetApp Exhibit 1008 Page 12
`
`

`

`$479538
`
`appropriate flags to the logical address 308 including having
`
`7
`set. Because of this, a reallocation of the rarely erased data
`files stored in the memory 152 is made into the memory 154
`and/or 156. In this way, sections of the mass storage which
`have been erased numerous times are programmed with a
`reallocated data file which is rarely changed thereby allow-
`ing all sections of the mass storage to eventually approach
`parity of erase cycles. Like the multi-sector erase, a clean-
`out erase can be performed in the event
`that there is
`insufiicient available storage for a data file presently being
`performed. For example, if all but two blocks have their
`respective erase inhibit flags set, and a three or more block
`data file is being programmed, a clean-out erase can be
`performed to provide sufficient storage for the data file.
`Once the erase inhibit flag is set for all the blocks,
`indicating that all the blocks have achieved parity in erase
`cycles, the erase inhibit and erase count registers are erased
`and the cycle is repeated. The selection of the maximum
`count depends upon the system requirements. As the value
`for the maximum count increases, the disparity between
`erase count cycles of various blocks can also increase.
`However, because data is shifted as a result of achieving
`maximum erase count this process of smoothing cycles
`throughout the mass storage of itself introduces additional
`erase cycles because a block of information is transferred
`from a physical block having few erases to a block having
`the maximum number of erases. Accordingly, though low
`maximum count values reduce the disparity between erase
`cycles amongst the blocks it also increases the number of
`erase cycles to which the blocks are subjected. Accordingly,
`individual users may select an erase count depending upon
`the system needs.
`In the preferred embodiment, algorithm 2 is merged with
`algorithm 1 as shown in FIG. 7. An instruction is provided
`by the computer system to write a data file to the mass
`storage (step 230) which starts the combined algorithm 1
`and algorithm 2 sequence. It is first determined whether the
`mass storage is full (step 232). If the mass storage is not full,
`i.e., it has a block with its used/free flag unset, the algorithm
`continues and stores the data file into such a block (step
`234)
`If on the other hand, it is determined that there are no free
`blocks, then it is next determined whether there are any
`blocks which have both the old/new flag set AND the erase
`inhibit flag unset (step 236). If there are no blocks which
`have both the old/new flag set AND the erase inhibit flag
`unset (step 236), the system of the present invention erases
`the data file, used/free flag and old/new flag in each block
`having its old/new flag set, and erases the counter and erase
`inhibit flag for every block (step 238). Step 238 is also
`performed in the event there are insufficient blocks remain-
`ing to store a pending data file. The algorithm then returns
`to block (step 232) to determine whether the disk is full.
`Ifthe system can find a block having both the old/new flag
`set AND the erase inhibit flag unset (step 236), then the
`system executes an erase procedure and erases the data file,
`used/free flag and old/new flag in each block having its
`old/new flag set. The counter is incremented and the erase
`inhibit flag for such blocks is not disturbed.
`It is then determined whether any block having its used/
`free flag unset has its counter at the maximum count (step
`242). If not, then the system of the present invention retums
`to decision step 232 and investigates again whether there is
`any block having its used/free flag unset (step 232).
`On the other hand, if there is a block having its erase count
`at the maximum value, a data file is copied from another
`block having the then least count value (step 244) into the
`location having COUNT=C0UNTMW The erase inhibit flag
`is then set (step 244). Note that a data file will not be copied
`from a block having its erase count at one less than the
`
`8
`maximum value, COUNTMax-l. Making such a reallocation
`from a source block having COUNTMax-l to a destination
`block having COUNTMax results in having both blocks at
`COUNTMQX and no net gain. Further, the block previously
`having its erase count at COUNTMax—l
`is erased to no
`advantage, thus the erase cycle for that block would be
`wasted.
`
`The old/new flag from the source block is then set (step
`246) so that it can be erased during the next execution of an
`erase step 240. In that way the source block can be used for
`storage until its erase count reaches maximum and its erase
`inhibit flag is set. The algorithm then returns to step 242 to
`determine whether there are now any blocks having a