United States Patent r191
`Ban
`
`[54] FLASH FILE SYSTEM
`
`[75]
`
`Inventor: Amir Ban, Tel Aviv, Israel
`
`[73] Assignee: M-Systems Flash Disk Pioneers Ltd.,
`Tel Aviv, Israel
`
`[21] Appl. No.: 27,131
`
`[22] Filed:
`
`Mar. 8, 1993
`
`Int. CI. 6 .............................................. G06F 12/02
`[ 51]
`[52] U.S. CI . ............................. 395/425; 364/DIG. 1;
`364/246.3; 364/256.3
`[58] Field of Search ............................... 395/400, 425;
`364/200 MS File, 900 MS File
`
`I IIIII IIIIIIII Ill lllll lllll lllll lllll lllll lllll lllll lllll llllll Ill lllll llll
`US005404485A
`5,404,485
`[11] Patent Number:
`Apr. 4, 1995
`[45] Date of Patent:
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,511,964 4/1985 Georg et al. ........................ 395/400
`5,193,184 3/1993 Belsan et al ......................... 395/600
`5,210,866 5/1993 Milligan et al. ..................... 395/575
`5,301,288 4/1994 Newman et al. .................... 395/400
`Primary Examiner-Joseph L. Dixon
`Assistant Examiner-Hiep T. Nguyen
`Attorney, Agent, or Firm-Mark M. Friedman
`ABSTRACT
`[57]
`The provision of a flash memory, virtual mapping sys(cid:173)
`tem that allows data to be continuously written to un(cid:173)
`written physical address locations. The virtual memory
`map relates flash memory physical location addresses in
`order to track the location of data in the memory.
`
`6 Claims, 5 Drawing Sheets
`
`START
`
`MAP VIRTUAL ADD.
`TO LOGICAL UNIT ADD.
`
`EXAMINE UNIT
`ALLOCAT TABLE
`
`47
`
`YES
`
`LOCATE FREE ADD.
`IN UNIT ALLOCATION
`TABLES
`
`45
`
`46
`
`50
`
`48
`
`MAP LOGICAL ADD.
`TO PHY. ADD.
`
`49_,,;
`
`WRITE TO
`PHY. ADDRESS
`
`I
`00
`
`MAP FREE LOGICAL
`ADD. TO PHY. ADD.
`
`51
`
`(7
`
`WRITE TO
`PHY. ADD.
`52 L - - - - - - '
`
`53
`\
`)
`
`UPDATE UNIT
`ALLOCATION
`TABLE(S)
`
`UPDATE LOGICAL
`ADD. TO PHY. ADD.
`MAP
`
`54
`
`INTEL-1031
`8,010,740
`
`

`

`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 1 of 5
`
`5,404,485
`
`FIG.1
`
`(
`PROCESSOR
`
`I
`{
`FLASH
`CONTROL
`
`FIG.2
`
`FLASH
`MEMORY
`
`16
`
`I
`
`RANDOM
`ACCESS
`MEMORY
`
`FLASH
`MEMORY-----.
`,-------"-'-------·~--~------------
`7
`ZONE B :
`!
`
`i
`-
`: ZONE A
`;
`-
`
`UNIT #1
`
`f'---/
`
`: - - - -=- - - -~
`
`-- UNIT N-1
`
` ZONE xx I! ZONE yy·,·
`
`I:
`
`:
`l
`1-----:-----i
`I
`I
`I
`i
`I
`
`I
`
`; " \ TRANSFER
`!
`i ZONE XZ : ZONE ZY1
`UNIT
`I
`I
`I
`I
`;
`I
`L ____ I _ _ _ _ _J
`
`I
`
`ZONE D :-.. ,
`!
`\
`UNIT #6
`
`-
`
`ZONE C -
`-
`
`I
`I
`L ____ =: ____ _j
`
`

`

`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 2 of 5
`
`5,404,485
`
`FIG.3
`
`UNIT HEADER
`
`BLOCK ALLOCATION
`MAP
`DATA BLOCK 61
`DATA BLOCK #2
`
`DATA BLOCK #N
`
`23
`
`25
`
`21
`
`21
`
`21
`
`FIG.7
`
`BEFORE
`
`AFTER
`
`LOGICAL UNIT
`# M
`
`DELETED
`
`BLOCK# 563
`
`COPY
`
`DELETED
`
`FREE
`
`,
`
`1 BLOCK # 1171 COPY ~ .... _F_RE_E_ ...... J
`
`TRANSFER UNIT
`
`TRANSFER UNIT
`
`FREE
`
`FREE
`
`FREE
`
`FREE
`
`FREE
`
`FREE
`
`FREE
`
`FREE
`
`LOGICAL UNIT
`# M
`
`FREE
`
`BLOCK# 563
`
`FREE
`
`FREE
`
`,.~
`
`, I,
`
`,.,
`
`,.
`
`,
`
`::::
`
`~
`
`BLOCK # 117
`
`

`

`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 3 of 5
`
`5,404,485
`
`29 ---...._
`\
`
`,-- BLOCK OFFSET
`
`.-------~1 BLOCK NUMBER
`BLK # LOGICAL
`BLK ADD
`
`~ 3 1
`
`-
`
`LOGICAL BLOCK
`ADDRESS
`
`35~
`
`\
`
`LOGICAL PHYSICAL
`UNIT # UNIT #
`
`I
`I
`
`I
`
`\_ LOGICAL
`UNIT #
`
`_
`
`·-··'· VIRTUAL ADDRESS
`
`\ \ BLOCK OFFSET
`
`CARRIED F"ORWAR D
`
`/33 \ ,
`I
`I
`
`I
`I
`
`\
`\
`
`I
`
`LOGICAL ADDRESS
`
`"-- BLOCK OFFSET
`
`OFFSET IN UNIT
`
`!
`j
`
`~ - - , - -___ ___._ ___ ___,
`I PHYSICAL ADDRESS
`PHYSICAL
`UNIT # --
`
`. '- BLOCK OFFSET
`IN UNIT
`
`FIG.4
`
`40
`
`41
`
`42
`
`MAP VIRTUAL ADD.
`TO LOGICAL ADD.
`
`MAP LOGICAL ADO.
`TO PHY. ADD.
`
`READ DATA AT
`PHY. ADD.
`
`END
`
`FIG.5
`
`

`

`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 4 of 5
`
`5,404,485
`
`FIG.6
`
`START
`
`MAP VIRTUAL ADD.
`TO LOGICAL UNIT ADD.
`
`EXAMINE UNIT
`ALLOCAT TABLE
`
`47
`
`48
`
`YES
`
`MAP LOGICAL ADD.
`TO PHY. ADD.
`
`I
`i
`I
`t
`WRITE TO
`PHY. ADDRESS
`I
`49/
`~ ,
`
`51
`
`LOCATE FREE ADD.
`IN UNIT ALLOCATION
`TABLES
`
`MAP FREE LOGICAL
`ADD. TO PHY. ADD.
`
`45
`
`46
`
`50
`
`53
`\
`I
`)
`
`UPDATE UNIT
`ALLOCATION
`TABLE(S)
`
`UPDATE LOGICAL
`ADD. TO PHY. ADD.
`MAP
`
`54
`
`

`

`tD -UI
`
`Cl.l
`
`=- tD
`
`0 ...,
`
`OJ
`\0
`\0
`1-1.
`
`.. ~
`!"1
`'Cl
`>
`
`~
`
`tD =
`......
`a
`• 00. •
`L!
`
`UPDATE VIRTUAL MAP PAGE BLK I FIG.9
`
`I
`
`7 ~ -WRITE l.JPDATED PAGE BLK MAP-7
`\"-i
`73
`
`TO FREE PHY. FLASH LOCATION
`
`READ PAGE BLOCK VIRTUAL MAP
`
`FROM FLASH MEMORY
`
`PAGE# TO FLASH PAGE
`USE RAM TABLE TO MAP
`
`BLOCK VIRTUAL MAP
`
`I
`
`ADD. TO PAGE #
`CONVERT VIRTUAL
`
`I
`
`f
`
`START )
`
`72
`
`\
`71
`
`\__
`70
`
`~ = ~ ...
`...
`UI
`
`UI
`00
`~
`
`UI
`
`I
`
`)
`
`END
`
`~ UPDATE RAM MAP TO POINT
`
`UPDATED VIRTUAL MAP
`
`76
`
`MARK ORIG FLASH MEMORY PAGE
`
`BLK VIRTUAL MAP DELETED
`
`75
`
`FIG.8
`
`)
`
`END
`
`TO PHY. ADD. MAP
`UPDATE LOGICAL ADD.
`
`SELECTED UNIT
`FLASH ERASE
`
`HODS. IN TRANSFER UNIT
`CORRESPONDING OFFSET
`WRITE ACTIVE BLOCKS AT
`
`DATA BLOCKS
`READ ACTIVE
`
`FOR TRANSFER
`SELECT UNIT
`
`)
`
`START
`
`"'·
`
`64
`
`63
`
`62
`
`61
`
`60
`
`

`

`1
`
`FLASH FILE SYSTEM
`
`5,404,485
`
`2
`The flash memory physical locations are organized as
`an array of bytes. Each of the bytes in the array is as(cid:173)
`signed a number or address by means of which the byte
`is physically accessible, referred to herein as the physi-
`5 cal address space. Each of the bytes in the array has a
`second address, called the virtual address space. A ta(cid:173)
`ble, called a virtual map, converts virtual addresses to
`physical addresses. Here it should be noted, the virtual
`address space is not necessarily the same size as the
`IO physical address space.
`A contiguous, fixed-length group of physical byte
`addresses form a block. For example, assuming a block
`size of 512 bytes, a byte with a physical address of
`256211
`is
`byte number
`211
`in block
`500
`(256211 +512=500+211). One or more physically con(cid:173)
`tiguous flash memory areas (called zones) make up a
`unit which can be physically erased using suitable prior
`art flash memory technology. Each unit contains an
`integral number of blocks.
`The virtual memory map is a table in which the first
`entry belongs to virtual block 0, the second to virtual
`block 1, and so on. Associated in the table with each
`virtual block address there is a corresponding physical
`address. In a read from the flash memory operation, a
`computer generated address is decoded as a virtual
`block address and a byte location within the block. The
`virtual memory map is used to convert the virtual block
`address to a physical block address; the byte location is
`the same in the virtual address space and the physical
`address space.
`In a write operation, the computer generated address
`is again interpreted as a virtual block address and a byte
`location within the block. The virtual memory map
`converts this to a physical memory block address. If the
`flash memory block corresponding to the physical ad(cid:173)
`dress is then currently written, it is generally not possi-
`ble to write to this physical address. An unwritten block
`is therefore located and written to. The virtual memory
`map is changed so that the unwritten physical block
`address is mapped to the original virtual address and
`original physical address is denoted as unusable and
`remains unusable until there is a zone erase operation
`that erases the unit that includes that block. It will be
`noted that a write operation assumes that an entire
`block will be rewritten. This is the manner in which
`computer systems usually access data in a storage me-
`dia. However, it will be appreciated that in general, any
`desired number of bytes could be written to the new
`storage location.
`In a preferred embodiment of the invention, each unit
`is assigned a logical unit address that remains un(cid:173)
`. changed as the unit is rewritten into a new physical
`address location in flash memory. The virtual map con(cid:173)
`tains references to the logical unit addresses rather than
`the physical unit addresses so that data movement dur(cid:173)
`ing unit transfers has no effect on the virtual map.
`Each unit has a usage map of all the blocks within the
`unit; the virtual address of a block, if it is mapped, and
`special characters to denote free blocks and to denote
`unusable blocks.
`Unusable blocks of previously written flash memory
`are reclaimed by transferring memory units that include
`the unusable blocks to a reserved unwritten space in the
`flash memory. Only the usable blocks are written in the
`transfer operation so that, as rewritten, the locations
`where the unusable blocks were, are not rewritten in the
`reserved space and are thus usable. After having been
`rewritten, the original memory unit space is flash erased
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`This invention relates to an improved system for
`storing and retrieving information in flash memories,
`and more particularly to a system that organizes and
`manages data written to a flash memory.
`2. Description of the Prior Art
`As will be appreciated by those skilled in the art,
`electrically erasable and programmable read-only mem(cid:173)
`ories (EEPROMs) comprised of flash-type, floating(cid:173)
`gate transistors have been described in the art and are 15
`presently commercially available. These so-called flash
`memories are non-volatile memories similar in function(cid:173)
`ality and performance to EPROM memories, with an
`additional functionality that allows an in-circuit, pro(cid:173)
`grammable, operation to erase blocks of the memory. In 20
`a flash memory, it is not practical to rewrite a previ(cid:173)
`ously written area of the memory without a preceding
`block erase of the area. While this invention will be
`described in the context of a flash memory, those skilled
`in the art will understand that its teachings are also 25
`applicable to data storage devices with the same write,
`read, and block erase before write characteristics as
`flash memories.
`In a typical computer system, the operating system
`program is responsible for data management of the data 30
`storage devices that are a part of the system. A neces(cid:173)
`sary, and usually sufficient, attribute of a data storage
`device to achieve compatibility with the operating sys(cid:173)
`tem program is that it can read data from, and write
`data to, any location in the data storage medium. Thus, 35
`flash memories are not compatible with typical existing
`operating system programs, since data cannot be writ(cid:173)
`ten to an area of flash memory in which data has previ(cid:173)
`ously been written, unless the area is first erased.
`Software products have been proposed in the prior 40
`art to allow a flash memory to be managed by existing
`computer operating programs without modification of
`the operating system program. However, these prior art
`programs operate the flash memory as a "write once
`read many" device. This prior art software product 45
`cannot recycle previously written memory locations.
`When all locations are eventually written the memory
`cannot be further used without specific user interven-
`tion.
`
`50
`
`SUMMARY OF THE INVENTION
`An object of this invention is the provision of a
`method (i.e., software, firmware or hardware) to con(cid:173)
`trol and manage access to a flash memory so that the
`flash memory appears to the computer operating system 55
`as a data storage device in which it is possible to read
`data from, and write data to, any flash memory location.
`A method that allows flash memory to emulate random
`access memories and allows existing computer operat(cid:173)
`ing systems to provide all other required support in the 60
`same manner provided by standard random access
`memories and independent of the emulation method.
`Briefly, this invention contemplates the provision of a
`flash memory, virtual mapping system that allows data
`to be continuously written to unwritten physical ad- 65
`dress locations. The virtual memory map relates flash
`memory physical location addresses in order to track
`the location of data in the memory.
`
`

`

`3
`as a unit and thus becomes an unwritten reserved space
`to which a subsequent transfer can be made.
`Also, in a preferred embodiment of the invention, the
`virtual map is stored primarily in the flash memory with
`only a small secondary virtual map in random access 5
`memory. The virtual map in flash memory is stored in
`blocks and organized into pages whose size is equal to
`the product of the number of bytes in a block times the
`number of physical block addresses this number of bytes
`represents. A secondary random access memory con- 10
`tains the page addresses. In reading data for a given
`virtual address, the page number is determined by divid(cid:173)
`ing address by the page size. The result indexes the
`secondary virtual map to find the correct primary vir(cid:173)
`tual map block. The remainder is used to calculate the 15
`required physical address for the virtual map stored in
`flash memory. To alter the virtual map in flash memory,
`the altered map is written into a free block and the
`secondary map in random access memory is altered to
`reflect the change in the primary virtual map location. 20
`The replaced block is marked as deleted.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The foregoing and other objects, aspects and advan(cid:173)
`tages will be better understood from the following de- 25
`tailed description of a preferred embodiment of the
`invention with reference to the drawings, in which:
`FIG. 1 is a block diagram illustrating functional com(cid:173)
`ponents of a system in accordance with one embodi(cid:173)
`ment of a system in accordance with the teachings of 30
`this invention.
`FIG. 2 is a pictorial illustration of one level of flash
`memory organization in accordance with the teachings
`of this invention.
`FIG. 3 is a pictorial illustration of how a unit is for- 35
`matted.
`FIG. 4 is a pictorial representation illustrating how
`the computer generated addresses are mapped to physi(cid:173)
`cal addresses.
`FIG. 5 is a flow diagram illustrating a read operation. 40
`FIG. 6 is a flow diagram illustrating a write opera(cid:173)
`tion.
`FIG. 7 is a pictorial diagram illustrating the status of
`a unit before and after a transfer operation.
`FIG. 8 is a flow diagram of a transfer operation.
`FIG. 9 is a flow diagram iIIustrating the operation
`where a major portion of the virtual to physical map is
`stored in flash memory.
`DETAILED DESCRIPTION OF A PREFERRED 50
`EMBODIMENT OF THE INVENTION
`Referring now to FIG. 1 of the drawings, in a typical
`system a processor 10, in combination with its operating
`system software, issues a series of read and write com(cid:173)
`mands to read from, and write data to, specific address 55
`locations in a random access memory. As will be appre(cid:173)
`ciated by those skilled in the art, in a random access
`storage device, such as a disk memory, data can be
`written to, or read from, any address location. In. the
`system of FIG. 1, the processor 10 writes data to, and 60
`reads data from, a flash memory 12 in blocks at specific
`address locations. Although zones of the flash memory
`12 can be erased, currently written address locations
`cannot be rewritten until the entire zone is erased. In
`accordance with the teachings of this invention, a flash 65
`memory controller 14 provides a fully rewritable vir(cid:173)
`tual address space so that the flash memory 12 emulates
`a random access memory, such as a disk memory, and
`
`5,404,485
`
`4
`the processor operating system software provides all
`other required operating support (such as a file system)
`in the same manner as it provides for a standard random
`access memory, and in a manner that is independent of
`the flash memory 12 and its controller 14. A typical
`system also includes a conventional random access
`memory 16. It will be appreciated that controller 14
`functions may be carried out in software, firmware or
`hardware, and would not necessarily exist as a physi(cid:173)
`cally separate unit as the drawing suggests.
`Referring now to FIG. 2, it illustrates in part the
`organization of the flash memory. The flash memory
`has a number of zones labeled here as zone A, zone B,
`etc. Each zone is comprised· of a number of contiguous
`physical memory locations that can be block erased
`using conventional, well known, flash memory technol-
`ogy. The zones are organized as units only four of
`which are shown, labeled in the drawing as; UNIT #1,
`UNIT #6, UNIT N-1 and TRANSFER UNIT. Each
`unit is comprised of at least one zone, or a plurality of
`contiguous zones. Here illustrated, each unit is com- ·
`prised of two zones (i.e., UNIT #1-zone A and zone
`B; UNIT #2-zone C and zone D, TRANSFER
`UNIT-zone X2 and 24).
`Each unit is comprised of an integral number of ad(cid:173)
`dressable blocks and each block, in tum, is comprised of
`a contiguous, fixed length group of bytes. At all times,
`there will be a unit in the memory 12 that is unwritten
`(i.e., TRANSFER UNIT), so that active blocks in a
`unit that is to be erased can be written to this unwritten
`unit prior to erasing the unit.
`Referring now to FIG. 3, each unit contains an inte-
`gral number of contiguous data blocks 21 that are in
`tum comprised of contiguous byte addresses, that can
`be addressed as a block number and offset within the
`block. Each block in a unit can be addressed by block
`number and offset with the unit. Each unit has a unit
`header 23 and a map 25 of the allocation status of each
`block in the unit. The unit header 23 includes a format
`identifier, and the logical unit number of the unit. Be(cid:173)
`cause data must move physically during a unit transfer,
`the unit number preferably remains unchanged even as
`the physical location of the unit in the flash memory 12
`changes. In addition, the header may also include sys-
`45 tern-wide information. The block allocation map 25 has
`a word for each block that denotes its status and its
`offset in the unit. The status indications are: "block free
`and writable"; "block deleted and not writable"; "block
`allocated and contains user data"; and virtual address of
`the block (back pointer).
`As previously mentioned, preferably each unit is
`assigned a logical unit number that does not change,
`even though the physical location in the memory of the
`unit changes. As illustrated in FIG. 4, the computer
`generated addresses 29 are comprised of a block number
`and a block offset. These addresses are interpreted by
`the flash controller 14 as virtual addresses, and a virtual
`map is used to establish a correspondence between the
`virtual address space and physical address space. The
`virtual map changes as blocks are rewritten and the
`virtual address space is therefore dynamic. It should be
`noted also that, at any given time, a block or blocks in
`the virtual address space may be unmapped to the phys(cid:173)
`ical address space, and that blocks in the physical ad(cid:173)
`dress space may be unwritten and, therefore, free to be
`written into.
`Since the data moves physically during a unit transfer
`to an unwritten unit space, the units are assigned logical
`
`

`

`5
`unit numbers that do not change with changes in the
`physical location of the unit in the memory. A virtual
`map 31 maps block numbers to logical unit address in
`the first step of a two level address translation. The
`logical unit address is an address relative to a logical 5
`unit number, similar to a physical address, which is an
`address relative to a physical unit number. The logical
`unit number is the high order binary digits of the logical
`address and may be derived from the logical address by
`a bit shift operation. The logical address 33 obtained IO
`from map 31 includes a logical unit number along with
`the offset of the block within the unit.
`A logical unit table 35 translates the logical unit num(cid:173)
`ber to a physical unit number for the logical unit. This
`two-step address translation procedure obviates the 15
`need to change block addresses in the map when a unit
`is moved ~o a new physical location.
`In a read operation the virtual address 29 comprised
`of a block address, for example, initially is mapped to a
`logical unit number and a block offset within the unit in 20
`the addressed block. Map 35 maps the unit number 33 to
`a physical address 37 for the unit along with the offset
`of the addressed 37 block within the unit, and the ad(cid:173)
`dressed data block is read from this physical location.
`Here it is assumed that data is read and written on a 25
`block basis as is typically done. Of course, data could be
`written and read on a byte basis using the same princi(cid:173)
`ple, if desired. FIG. 5 is a flow diagram illustrating this
`read operation. As previously explained, the virtual
`address 29 is mapped to a logical address (block 40) in 30
`the first step of a two-step address translation. In the
`second step, the logical address is mapped to a physical
`address in the flash memory, block 41. Data at this
`physical address is read, block 42, which terminates this
`operation.
`In a write operation, the virtual address 29 is again
`mapped initially to a logical unit number and a block
`offset within the unit. The controller 14 algorithm ex(cid:173)
`amines the block allocation map 25 for this unit. If the
`block corresponding to this address has been written, a 40
`write command cannot be executed at the correspond(cid:173)
`ing physical address. The control algorithm scans the
`block allocation maps 25 for each unit until a free block
`is located. The status of the block in the block map 25 at
`the original unit address is changed to deleted in the 45
`block in the allocation map, and the status of the free
`block is changed to written. The virtual map 31 is up(cid:173)
`dated so that the original virtual address now points to
`the new logical address where the write operation is to
`take place. This logical address is mapped to a physical 50
`address, in the manner previously described, and the
`block is written to this address. FIG. 6 is a flow diagram
`illustrating this write operation. In a write operation the
`virtual address 29 is mapped to a logical unit address,
`block 45, and the unit allocation for the unit is exam- 55
`ined, block 46. If in decision block 47 the unit address is
`free, the unit address is mapped to a physical address,
`block 48, and data is written to this physical address,
`block 49, and the operation ends. If the logical address
`is not free (block 47), the unit tables are scanned to 60
`locate a free address in the unit allocation tables, block
`50. This new logical address is mapped to a physical
`address, block 51, and the data is written to this physical
`address, block 52. The unit allocation tables are updated
`(block 53) to indicate that the original block is deleted 65
`and not writable, and that the new block is allocated
`and contains user data. The virtual to logical address
`map is then updated to point to the new physical ad-
`
`35
`
`5,404,485
`
`6
`dress of the data corresponding to the original virtual
`address, blocks 54 and 55.
`To enable reading and writing operations to continue
`without limitation, physical memory space is reclaimed
`periodically. As explained previously, at least one unit
`of the memory is reserved at all times so that it consists
`entirely of free blocks and serves as a TRANSFER
`UNIT.
`Referring now to FIG. 7, an active unit is selected
`(here, UNIT #M) and all of its currently-mapped active
`blocks are read and then written to the TRANSFER
`UNIT. The selected unit #Mis then block erased, and
`it becomes the TRANSFER UNIT while the transfer
`unit to which the active blocks have been written be(cid:173)
`comes, in this example, unit #M. FIG. 7 illustrates the
`status of the units before and after a transfer operation.
`FIG. 8 is a flow diagram of this transfer operation. In a
`transfer operation a unit is selected for transfer, block
`60, and the active data blocks in the selected unit are
`read, block 61. These active data blocks are then writ(cid:173)
`ten to the transfer unit at positions in the transfer unit ·
`corresponding to the positions at which they were lo(cid:173)
`cated in the original unit, block 62. The original unit
`selected is then flash erased, block 63, and the logical to
`physical address map is changed so that the selected
`unit becomes the transfer unit and the transfer unit is
`assigned the unit number of the selected unit, block 64.
`The system thus far described requires a virtual map
`whose contents are freely updated, and such a map may
`be stored in a conventional random access memory.
`However, assuming, for example, a block size of 512
`bytes, since the virtual map contains a entry for each
`block, and each entry may be, for example, 4 bytes long
`(i.e., capable of addressing up to 4 Gigabytes of mem(cid:173)
`ory), a flash memory of 80 Mbytes would require a
`memory of 640 Kbytes to store the map tables. In order
`to limit the amount of random access memory required
`to store the virtual map, in a preferred embodiment of
`the invention, a major portion of the map data is stored
`in the flash memory 12 itself, and a secondary virtual
`map that maps virtual addresses from the computer to
`the primary virtual map is stored in a random access
`memory, such as memory 16. An important point to be
`made here is that the secondary virtual map arrange(cid:173)
`ment makes the procedure for reading and writing the
`virtual map identical to the procedures for reading and
`writing ordinary data explained earlier. The virtual map
`itself treated in a manner equivalent to the user data in
`the foregoing description and the virtual map stored in
`random access memory (i.e., secondary virtual map) is
`the equivalent of the virtual map in the previous de(cid:173)
`scription.
`In this embodiment, the virtual map resides in the
`flash memory 12 at negative virtual addresses; ordinary
`space starts at virtual address zero. The virtual map
`maps the negative address used by itself, so that the
`virtual map residing in flash memory can be read and
`written like ordinary user data, and only the portion of
`the virtual map that maps itself (i.e., the secondary
`virtual map) resides in random access memory.
`In a simplified example, assume a virtual map of 6000
`bytes stored in twelve virtual map blocks, each of 512
`bytes. Assuming a four-byte address, each block can
`store 128 physical addresses. Thus, each block contains
`the addresses of 64 Kbytes of virtual flash memory.
`Each block of virtual flash memory addresses is consid(cid:173)
`ered as a page and the random access memory stores the
`page addresses; (in this example, only 48 bytes) mapped
`
`

`

`20
`
`7
`to the address blocks. In reading data from a given
`virtual address, the address is divided by the page size
`(64 Kbytes) to obtain a page number in the secondary
`virtual memory that maps to the page block of the pri(cid:173)
`mary virtual map where the address is stored. With the 5
`virtual memory page block, the procedure to map to a
`specific flash memory physical address can proceed in
`the manner already described. For example, after the
`virtual address is divided by the page size, the remain(cid:173)
`der can be divided by the virtual memory block size 10
`( e.g., 512) to obtain an index to the array of address read
`from flash memory.
`In writing data to a given virtual address, the com(cid:173)
`puter generated address is also divided by the page size
`to obtain an index to the secondary virtual map in flash 15
`memory. The secondary virtual map maps to the pri(cid:173)
`mary virtual map, where the primary virtual map block
`is read; and this is used to map to the physical block that
`has been addressed where it is read. As this block can-
`not be rewritten, an unwritten block is identified and
`written into in the manner previously described, with
`the original data block marked as deleted. To update the
`virtual map residing flash memory, essentially the same
`procedure is followed. The virtual map block, in its 25
`modified form to reflect the new physical location of
`the addressed data, is written to an unwritten block in
`the flash memory and the old block is marked as de(cid:173)
`leted. The secondary virtual memory in random access
`memory is changed, as needed, to reflect the change in 30
`the primary virtual memory block locations.
`FIG. 9 is a flow diagram of this operation. The first
`step in this process is to convert a virtual address to a
`page number, block 70 and to use the page number to
`locate in RAM 16 the address, in flash memory 12, of 35
`the relevant page block of the virtual map stored in the
`flash memory, block 21. The page block of the virtual
`map at this address is read from the flash memory (block
`72) and used in the manner previously described to a
`locate physical address corresponding to the virtual 40
`address for a data read or data write operation. In a data
`write operation, the virtual map page block must be
`updated, block 73, and the updated page block virtual
`map is written to a free flash memory physical address
`location, block 74. The original flash memory address at 45
`which the page block virtual map was located is marked
`as deleted, block 75, and the RAM memory 16 is up(cid:173)
`dated to point to the virtual to physical map address for
`the updated map, block 76.
`The virtual map can be readily reconstructed upon 50
`system startup. The virtual maps residing in flash mem(cid:173)
`ory are non-volatile and do not require reconstruction.
`The secondary virtual map residing in volatile random
`access memory can be reconstructed by scanning, at
`startup, the block usage map that resides at the top of 55
`each unit. Blocks marked as mapped to a virtual address
`are identified, and the secondary virtual map is con(cid:173)
`structed accordingly.
`While the invention has been described in terms of a
`single preferred embodiment, those skilled in the art 60
`will recognize that the invention can be practiced with
`. modification within the spirit and scope of the appended
`claims.
`Having thus described my invention, what I claim as
`new and desire to secure by Letters Patent is as follows: 65
`1. A memory management method for a memory in
`which data can be written only in unwritten physical
`memory locations and in which a zone of contiguous
`
`5,404,485
`
`8
`memory locations can be simultaneously erased, com(cid:173)
`prising the steps of:
`organizing the memory into a plurality of units;
`organizing each unit into a plurality of blocks, each of
`said blocks made up of a plurality of contiguous
`physical memory locations;
`establishing an allocation map for each unit which
`indicates the status of each block in a unit as writ(cid:173)
`ten, unwritten or deleted;
`establishing a virtual map to map virtual addresses to
`physical addresses;
`in writing data to said memory at a virtual address:
`(a) mapping said virtual address to a physical block
`address using said virtual map;
`(b) examining said allocation map for said unit to
`which said virtual address has been mapped in step
`(a) to determine the status of a block at said physi(cid:173)
`cal block address as written, unwritten or deleted;
`(c) if said block at said physical block address is in
`written or deleted status:
`(1) examining said allocation map for at least one of
`said units to identify an unwritten block address;
`(2) writing said data into said memory to said un(cid:173)
`written block address;
`(3) changing said allocation map for a block in a
`unit in which said data have been written in
`paragraph (c)(2) to indicate as written said previ(cid:173)
`ously unwritten block address where said data
`have been written;
`(4) changing said virtual map to map virtual ad(cid:173)
`dresses to physical addresses within a unit so that
`said virtual map maps said virtual address to the
`physical address of said previously unwritten
`block in which said data have been written in
`step (c)(2);
`establishing a transfer unit in said memory in which
`all blocks are in unwritten status, said transfer unit
`including a transfer unit allocation map;
`periodically identifying a selected unit, other than
`said transfer unit, to be erased;
`reading each written block in said selected unit;
`writing each written block in said selected unit into
`said transfer unit;
`updating said transfer unit allocation map to indicate
`as written the status of blocks that have been writ(cid:173)
`ten in the just previous writing step;
`erasing said selected unit;
`updating . said virtual map to reflect the above(cid:173)
`described movement of said written blocks.
`2. A memory management method for a memory in
`which data can be written only in unwritten physical
`memory locations and in which a zone of contiguous
`memory locations can be si