United States Patent (19)
`Ban
`
`54 FLASH FILE SYSTEM
`
`75 Inventor: Amir Ban, Tel Aviv, Israel
`
`o
`(73) Assignee: M-Systems Flash Disk Pioneers Ltd.,
`Tel Aviv, Israel
`
`(21) Appl. No.: 27,131
`22 Filled
`M
`22
`C:
`ar. 8, 1993
`
`51) Int. Cl............................................... G06F 12/02
`52 U.S. C. ............................. 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
`
`US0054.04485A
`Patent Number:
`Date of Patent:
`
`11
`45
`
`5,404,485
`Apr. 4, 1995
`
`56
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,511,964 4/1985 Georget 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
`57
`ABS
`CT
`The provision of a flash memory, virtual mapping sys
`tem that allows data to be continuously written to un
`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
`
`
`
`
`
`MAP WRUAL ADD.
`TO LOGICA UN ADD.
`
`EXAMINE UNI
`ALLOCAT TABLE
`
`
`
`47
`
`
`
`YES
`
`48
`
`MAP OGICAL ADD.
`TO PHY. ADD.
`
`LOGICAL
`ADDRESS
`FREE
`NO
`
`LOCATE FREE ADD.
`EN UNIT ALLOCATION
`TABLES
`
`WRITE TO
`PHY. ADDRESS
`49 -/
`
`
`
`45
`
`46
`
`50
`
`53
`
`)
`
`
`
`
`
`UPDATE UNIT
`ALLOCATION
`TABLE(S)
`
`
`
`UPDATE LOGICAL
`ADD. TO PHY. ADD.
`MAP
`
`
`
`
`
`
`
`54
`
`END
`
`KIOXIA Ex-1013, Page 1
`
`

`

`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 1 of 5
`
`5,404,485
`
`FLASH
`
`16
`
`
`
`
`
`
`
`RANDOM
`ACCESS
`MEMORY
`
`FIG.1
`
`
`
`PROCESSOR
`
`
`
`m
`
`i
`
`ZONE AE ZONE. B.
`UNIT 1
`E
`E N
`
`----------
`:
`E
`: ZONE CE ZONE DN
`E
`|
`UNIT #6
`
`W
`
`R
`
`. .
`... .
`IZONE Xi ZONE n-unit -
`r
`
`i
`
`ZONE XZ E ZONE ZY
`
`N TRANSFER
`UNIt
`
`KIOXIA Ex-1013, Page 2
`
`

`

`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 2 of 5
`
`5,404,485
`
`FIG.3
`
`UNIT. HEADER
`
`
`
`BLOCK ALLOCATION
`MAP
`DATA BLOCK #1
`DATA BLOCK #2
`
`25
`
`25
`
`21
`
`21
`
`
`
`
`
`
`
`DATA BLOCK #N
`
`21
`
`FIG.7
`
`BEFORE
`
`AFTER
`
`LOGICAL UNIT
`
`
`
`TRANSFER UNIT
`
`TRANSFER UNIT
`
`LOGICAL UNT
`
`KIOXIA Ex-1013, Page 3
`
`

`

`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 3 of 5
`
`5,404,485
`
`29
`N
`V
`BLOCK NUMBER
`
`BLOCK OFFSET
`1.
`VIRTUAL ADDRESS
`
`
`
`
`
`
`
`
`
`
`
`
`
`BLOCK OFFSET
`CARRIED FORWARD
`
`-35 \
`
`
`
`35-N
`LOGICALPHYSICAL
`UNIT - UNIT #
`
`
`
`N
`LOGICAL
`UNIT
`
`NBLOCK OFFSET
`
`OFFSET IN UNIT
`-37
`M
`
`PHYSICAL
`UNIT | 1
`
`N BLOCK OFFSET
`N UNT
`
`FG.4
`
`START
`
`MAP VIRTUAL ADD.
`TO LOGICAL ADD.
`
`MAP LOGICAL ADD.
`TO PHY ADD.
`
`
`
`READ DATA AT
`PHY ADD.
`
`40
`
`41
`
`42
`
`FIG.5
`
`KIOXIA Ex-1013, Page 4
`
`

`

`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 4 of 5
`
`5,404,485
`
`FIG.6
`
`
`
`START
`
`
`
`48
`
`
`
`
`
`
`
`MAP LOGICAL ADD.
`TO PHY ADD.
`
`WRITE TO
`PHY ADDRESS
`49
`
`51
`
`2
`5
`
`LOCATE FREE ADD.
`IN UNIT ALLOCATION
`TABLES
`
`MAP FREE LOGICAL
`ADD, TO PHY ADD.
`
`WRITE TO
`PHY. ADD.
`
`MAP VIRTUAL ADD.
`TO LOGICAL UNIT ADD.
`
`EXAMINE UNIT
`ALLOCAT TABLE
`
`
`
`47
`
`YES
`
`LOGICAL
`ADDRESS
`FREE
`NO
`
`45
`
`46
`
`50
`
`
`
`
`
`
`
`UPDATE UN
`ALOCATION
`TABLE(S)
`
`53
`
`)
`
`
`
`UPDATE LOGICAL
`ADD. TO PHY ADD.
`MAP
`
`
`
`
`
`
`
`54
`
`END
`
`KIOXIA Ex-1013, Page 5
`
`

`

`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 5 of 5
`
`5,404,485
`
`6°Ol4
`
`
`dVWALYIAQ3LVddn
`
`AMOWSWNHSV1SNOs
`
`dVWWALYIA40078
`
`WALUIALY3ANOD
`#39VdOL‘Adv
`Cluvs)
`
`
`
`
`
`
`
`NOILW901HSV14“AHd33udOL
`
`
`
`
`
`
`
`1GJOVdGYANTWALYIAAlvddn
`
`
`
`
`
`GVW1830VdG3LVGdNALUM
`
`dVWWNALYIAMOOTJdaVIY
`
`d¥WOL318VLWyy3SN
`
`
`
`3OVdHSVI4OL#39Vd
`
`Ld
`
`
`Q313730
`
`
`
`
`
`d¥WTWALYIA8JOVdAMOWINHSV14SINOMeV
`
`LNIOdOLdVWWYSivddn
`
`QN3
`
`8°94
`
`‘QVWOI9073lvadn
`
`dVW‘QQ¥“AHdOL
`YSISNVYLYOI
`LINAG3L0373S
`SM0018Vivd
`LINNLOITIS
`ASVHSV
`JNLOVV4
`CLwvs_)
`
`
`
`
`
`LVSHOOTESAILOVSLIM
`
`
`
`138340OINIGNOdSIYYOO
`
`LINNYS4SNVYLNISOGH
`
`09
`
`19
`
`C9
`
`¢9
`
`KIOXIA Ex-1013, Page 6
`
`KIOXIA Ex-1013, Page 6
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`1.
`
`FLASH FLE SYSTEM
`
`10
`
`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
`ories (EEPROMs) comprised of flash-type, floating
`gate transistors have been described in the art and are
`presently commercially available. These so-called flash
`memories are non-volatile memories similar in function
`ality and performance to EPROM memories, with an
`additional functionality that allows an in-circuit, pro
`grammable, operation to erase blocks of the memory. In
`20
`a flash memory, it is not practical to rewrite a previ
`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 3
`storage devices that are a part of the system. A neces
`sary, and usually sufficient, attribute of a data storage
`device to achieve compatibility with the operating sys
`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
`ten to an area of flash memory in which data has previ
`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.
`
`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
`signed a number or address by means of which the byte
`is physically accessible, referred to herein as the physi
`cal address space. Each of the bytes in the array has a
`second address, called the virtual address space. A ta
`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
`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
`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
`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
`changed as the unit is rewritten into a new physical
`address location in flash memory. The virtual map con
`tains references to the logical unit addresses rather than
`the physical unit addresses so that data movement dur
`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
`
`15
`
`50
`SUMMARY OF THE INVENTION
`An object of this invention is the provision of a
`method (i.e., software, firmware or hardware) to con
`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
`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.
`
`KIOXIA Ex-1013, Page 7
`
`

`

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

`

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

`

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

`

`15
`
`5,404,485
`10
`dress of the changed page addressable block to the
`(c) if said block at said physical block address is in
`unwritten physical block location in which said
`written or deleted status:
`changed page addressable block has been written.
`(1) examining said allocation map for at least one
`3. A memory management method for a memory in
`of said units to identify an unwritten block
`which data can be written only in unwritten physical
`address;
`memory locations and in which a zone of contiguous