1111111111111111 IIIIII IIIII 11111 1111111111 111111111111111 IIIII IIIII IIIII 1111111111 11111111
`US 20030163630Al
`
`(19) United States
`(12) Patent Application Publication
`Aasheim et al.
`
`(10) Pub. No.: US 2003/0163630 Al
`Aug. 28, 2003
`( 43) Pub. Date:
`
`(54) DYNAMIC DATA STRUCTURES FOR
`TRACKING DATA STORED IN A FLASH
`MEMORY DEVICE
`
`(76)
`
`Inventors: Jered Donald Aasheim, Bellevue, WA
`(US); Yongqi Yang, Bellevue, WA (US)
`
`Correspondence Address:
`LEE & HAYES PLLC
`421 W RIVERSIDE AVENUE SUITE 500
`SPOKANE, WA 99201
`
`(21) Appl. No.:
`
`10/087,251
`
`(22) Filed:
`
`Feb.27,2002
`
`Publication Classification
`
`(51)
`
`Int. Cl.7 ..................................................... G06F 12/00
`
`(52) U.S. Cl. ............................................ 711/103; 711/202
`
`(57)
`
`ABSTRACT
`
`One or more mapping data structures are maintained con(cid:173)
`taining mappings of logical flash memory addresses to
`physical flash memory addresses. Each mapping data struc(cid:173)
`ture has a predetermined capacity of mappings. A master
`data structure is also maintained containing a pointer to each
`of the one or more mapping data structures. Additional
`mapping data structures are allocated as needed to provide
`capacity for additional mappings. Each time a mapping data
`structure is allocated or de-allocated the pointers in the
`master data structure are changed accordingly.
`
`802
`
`800
`
`STORE THE LOGICAL SECTOR ADDRESS IN
`THE PHYSICAL SECTOR OF THE FLASH
`MEMORY MEDIUM WITH THE DATA
`
`No
`
`804
`
`SCAN THE FLASH MEMORY MEDIUM To
`LOCATE THE LOGICAL SECTOR ADDRESS
`STORED WITH THE DATA
`
`806
`
`REASSIGN THE PHYSICAL SECTOR
`ADDRESS CONTAINING THE DATA TO THE
`LOGICAL SECTOR ADDRESS STORED WITH
`THE DATA
`
`STORE THE REASSIGNED PHYSICAL SECTOR
`ADDRESS TO THE LOGICAL SECTOR
`ADDRESS IN THE TABLE
`
`808
`
`810
`
`812
`
`Go To NEXT SECTOR
`
`YES
`
`INTEL-1016
`8,010,740
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 1 of 15
`
`US 2003/0163630 Al
`
`102
`
`L
`BLOC KO
`
`BLOCK 1
`
`BLOCK N
`
`r100
`
`DATA AREA 103
`I
`
`SPARE
`A
`REA
`
`104
`
`K SECTORS PER
`BLOCK
`
`•
`
`Fig. 1
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 2 of 15
`
`US 2003/0163630 Al
`
`r200
`
`BLOCK 0
`
`I
`
`K SECTORS PER
`BLOCK
`
`BLOCK 1
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`•
`
`I
`
`BLOCK N
`
`Fig. 2
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 3 of 15
`
`US 2003/0163630 Al
`
`300
`
`COMPUTER DEVICE
`
`PROCESSOR
`
`302
`
`MEMORY
`
`APP(S)
`
`307
`
`309
`~
`305
`_/
`
`FLASH DRIVER
`~
`
`FLASH
`ABSTRACTION
`LOGIC
`
`308
`
`I
`
`PROGRAMMABLE
`FLASH MEDIUM
`LOGIC
`
`310
`
`306
`
`FLASH MEDIUM
`
`100/200
`
`Fig. 3
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 4 of 15
`
`US 2003/0163630 Al
`
`SECTOR
`MANAGER
`402
`
`COMPACTOR
`
`406
`
`r308
`
`LOGICAL-TO-
`PHYSICAL
`SECTOR
`MAPPING
`404
`
`Fig. 4
`
`r310
`
`PROGRAMMABLE
`ENTRY POINTS
`502
`
`1/0 [READ,
`WRITE, ERASE]
`504
`
`ERROR CODE
`CORRECTION
`506
`
`Fig. 5
`
`600A
`
`LOGICAL
`SECTOR
`604
`11
`12
`36
`
`PHYSICAL
`SECTOR
`602
`0
`1
`2
`3
`
`•
`•
`
`N
`
`Fig. 6A
`
`600B
`
`PHYSICAL
`SECTOR
`
`LOGICAL
`SECTOR
`
`0
`1
`2
`3
`
`_, ~_D_IR_TY_---;
`12
`36
`11
`
`N
`
`Fig. 68
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 5 of 15
`
`US 2003/0163630 Al
`
`,
`
`RECEIVE A REQUEST TO WRITE DATA To A v-
`
`LOGICAL SECTOR ADDRESS OF A FLASH
`MEMORY MEDIUM
`
`700
`
`702
`
`704
`
`!
`' ASSIGN A PHYSICAL SECTOR ADDRESS V
`
`'-
`
`'-
`
`To THE LOGICAL SECTOR ADDRESS
`FORMING A CORRESPONDING
`RELATIONSHIP
`
`+
`
`' I
`STORE THE CORRESPONDING
`RELATIONSHIP IN A TABLE
`!
`'WRITE THE DATA INTO A PHYSICAL SECTOR'
`OF THE FLASH MEMORY MEDIUM AT A V 708
`
`706
`
`'-
`
`,-
`
`\.
`
`/'
`
`,-
`
`,r
`
`'-
`
`LOCATION INDICATED BY THE PHYSICAL
`SECTOR ADDRESS
`!
`RECEIVE A REQUEST To REWRITE
`UPDATED DATA TO THE LOGICAL SECTOR
`ADDRESS
`
`...
`
`710
`
`v
`
`+
`ADDRESS To THE LOGICAL SECTOR v 712
`
`ASSIGN A NEW PHYSICAL SECTOR
`
`ADDRESS FORMING AN UPDATED
`CORRESPONDING RELATIONSHIP
`
`t
`
`STORE THE UPDATED CORRESPONDING
`RELATIONSHIP IN THE TABLE
`
`714
`
`r
`
`....
`
`t
`PHYSICAL SECTOR OF THE FLASH MEMORY r 716
`
`WRITE THE UPDATED DATA INTO A
`
`MEDIUM AT THE LOCATION INDICATED BY
`THE NEW PHYSICAL SECTOR ADDRESS
`
`!
`( MARK THE PHYSICAL SECTOR ADDRESS
`FROM STEP 704 As "DIRTY"
`Fig. 7
`
`718
`
`.r
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 6 of 15
`
`US 2003/0163630 Al
`
`(START~
`
`STORE THE LOGICAL SECTOR ADDRESS IN
`THE PHYSICAL SECTOR OF THE FLASH
`MEMORY MEDIUM WITH THE DATA
`
`No
`
`POWER
`
`804
`
`802
`
`800
`
`SCAN THE FLASH MEMORY MEDIUM To
`LOCATE THE LOGICAL SECTOR ADDRESS
`STORED WITH THE DATA
`
`806
`
`REASSIGN THE PHYSICAL SECTOR
`ADDRESS CONTAINING THE DATA To THE
`LOGICAL SECTOR ADDRESS STORED WITH
`THE DATA
`
`STORE THE REASSIGNED PHYSICAL SECTOR
`ADDRESS TO THE LOGICAL SECTOR
`ADDRESS IN THE TABLE
`
`808
`
`810
`
`812
`
`Go To NEXT SECTOR
`
`YES
`
`COMPLETE
`
`r814
`
`No
`
`Fig. 8
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 7 of 15
`
`US 2003/0163630 Al
`
`SECTOR
`
`0123456789101112131415
`
`Fig. 9
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 8 of 15
`
`US 2003/0163630 Al
`
`b
`
`b
`
`i
`
`--
`
`1 002")
`
`0
`1
`2
`3
`4
`5
`
`•
`
`POINTER
`POINTER
`NULL
`
`NULL
`NULL
`NULL
`
`NULL ~---
`•
`
`- ---
`
`•
`
`•
`
`NULL
`
`•
`
`N
`
`100~
`
`1000
`
`k
`
`I
`
`I
`
`k
`
`1006)
`
`•
`.
`
`•
`
`.
`
`•
`
`Fig. 10
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 9 of 15
`
`US 2003/0163630 Al
`
`,,
`
`'-
`
`GENERATE A MASTER TABLE CONTAINING v-
`
`'
`POINTERS To ONE OR MORE SECONDARY
`TABLES
`
`1102
`
`1100
`
`( DYNAMICALLY ALLOCATE SECONDARY
`
`TABLE(S)
`
`:r
`ENABLE/DISABLE POINTERS To TABLE(S) v 1106
`
`1104
`
`'-
`
`Fig. 11
`
`1200
`
`.
`
`1
`
`I
`I
`
`(
`
`•
`
`. /
`I
`I H
`\;A
`\/
`
`2 \
`
`Y:\
`~
`
`/~
`5
`/
`I
`
`6
`
`8
`
`7
`
`9
`
`Fig. 12
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 10 of 15
`
`US 2003/0163630 Al
`
`1200
`
`8
`
`1304
`
`1306
`
`=
`
`BLOCK
`COUNTER
`X
`
`+
`
`SECTOR
`COUNTER
`y
`
`Fig. 13
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 11 of 15
`
`US 2003/0163630 Al
`
`1400
`
`SET X= 0 Y=O
`,
`
`RECEIVE WRITE
`REQUEST
`
`WRITE DATA To
`SECTOR INDICATED BY
`X+Y
`
`Y=Y + 1
`
`1402
`
`1404
`
`1406
`
`1408
`
`1410
`
`No
`
`/
`
`Y> MAX
`SECT.OF
`
`YES
`SET Y = 0
`
`1417
`
`1412
`
`1414
`
`X=X+1
`
`1418
`
`No
`
`Fig. 14
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 12 of 15
`
`US 2003/0163630 Al
`
`(1200
`
`CP
`
`1502
`
`FREE
`
`1504
`
`~
`C 1302
`Fig. 15
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 13 of 15
`
`US 2003/0163630 Al
`
`1600
`
`MONITOR QUANTITIES
`OF FREE AND DIRTY
`SECTORS
`
`1602
`
`1604
`
`1606
`
`NONE
`
`SERVICE
`
`WAIT FOR Low
`PRIORITY THREAD
`
`CRITICAL-----------.....J
`
`1608
`
`1610
`
`1612
`
`SCAN SECTORS FOR DATA, REWRITE
`DATA TO FREE SECTORS, MARK SECTOR
`DIRTY AFTER REWRITING DATA
`
`ERASE BLOCK(S) MARKED DIRTY
`
`INCREASE SECTOR COUNT AND MOVE
`POINTER IN CONSECUTIVE AND
`CONTIGUOUS MANNER
`
`Fig. 16
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 14 of 15
`
`US 2003/0163630 Al
`
`(1200
`
`1502
`
`1504
`
`3
`
`4
`
`1302
`
`Fig. 17
`
`

`

`Patent Application Publication Aug. 28, 2003 Sheet 15 of 15
`
`US 2003/0163630 Al
`
`r-200
`
`1802
`
`DATA AREA 1803
`
`SPARE
`AREA
`
`1804
`
`BLOCK 0
`
`BLOCK 1
`
`BLOCK N
`
`K SECTORS PER
`BLOCK
`~
`1806
`
`•
`
`Fig. 18
`
`1806
`
`1806
`
`

`

`US 2003/0163630 Al
`
`Aug. 28, 2003
`
`1
`
`DYNAMIC DATA STRUCTURES FOR TRACKING
`DATA STORED IN A FLASH MEMORY DEVICE
`
`TECHNICAL FIELD
`
`[0001] This invention relates to flash memory devices, and
`more particularly, management of data associated with flash
`memory devices.
`
`BACKGROUND
`
`[0002] Flash memory devices have many advantages for a
`large number of applications. These advantages include their
`non-volatility, speed, ease of erasure and reprogramming,
`small physical size and related factors. There are no
`mechanical moving parts and as a result such systems are not
`subject to failures of the type most often encountered with
`hard disk storage systems. As a result many portable com(cid:173)
`puter devices, such as laptops, portable digital assistants,
`portable communication devices, and many other related
`devices are using flash memory as the primary medium for
`storage of information.
`[0003] Flash memory devices are generally operated by
`first setting all bits in a block to a common state, and then
`reprogramming them to a desired new state. Blocks of data
`need to be shuffled during the reprogramming process,
`which can slow the completion of the operation. Besides
`being time consuming, reprogramming a block of data can
`subject the entire block to accidental loss, in the event there
`is a power failure during the reprogramming process. Nor(cid:173)
`mally, as the block is shuffled, it is temporarily stored in a
`volatile memory device, such as Random Access Memory
`(RAM). The entire block of data (not just newly entered
`data) is susceptible to permanent loss if the reprogramming
`process has not completed prior to the power failure. In these
`circumstances, an entire block of data may need to be
`reentered by a user anew.
`
`SUMMARY
`
`[0004] A dynamic data structure for tracking data stored in
`a Flash memory device is described. In a described imple(cid:173)
`mentation, a process maintains one or more mapping data
`structures containing mappings of logical flash memory
`addresses to physical flash memory addresses. Each map(cid:173)
`ping data structure has a predetermined capacity of map(cid:173)
`pings. The process also maintains a master data structure
`containing a pointer to each of the one or more mapping data
`structures. Additional mapping data structures are allocated
`as needed to provide capacity for additional mappings. Each
`time a mapping data structure is allocated or de-allocated the
`pointers in the master data structure are changed accord(cid:173)
`ingly.
`[0005] The described implantations, therefore, introduce
`the broad concept of using a dynamic amount of memory to
`store logical-to-physical sector address mappings. Thus, the
`amount of memory needed to track data stored in the flash
`memory medium can be minimized.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0006] The detailed description is described with refer(cid:173)
`ence to the accompanying figures. In the figures, the left(cid:173)
`most digit(s) of a reference number identifies the figure in
`which the reference number first appears.
`
`[0007] FIG. 1 illustrates a logical representation of a
`NAND flash memory medium.
`[0008] FIG. 2 illustrates a logical representation of a NOR
`flash memory medium.
`[0009] FIG. 3 illustrates pertinent components of a com(cid:173)
`puter device, which uses one or more flash memory devices
`to store information.
`[0010] FIG. 4 illustrates a block diagram of flash abstrac(cid:173)
`tion logic.
`[0011] FIG. 5 illustrates an exemplary block diagram of a
`flash medium logic.
`[0012] FIG. 6A shows a data structure used to store a
`corresponding relationship between logical sector addresses
`and physical sector addresses.
`[0013] FIG. 6B shows a data structure which is the same
`as the data structure in FIG. 6B, except its contents have
`been updated.
`[0014] FIG. 7 illustrates a process used to track data on
`the flash memory medium when the file system issues write
`requests to the flash driver.
`[0015] FIG. 8 illustrates a process for safeguarding map(cid:173)
`ping of logical-to-physical sector address information stored
`in volatile data structures, such as the data structures shown
`in FIGS. 6A and 6B.
`[0016] FIG. 9 illustrates a location within the flash
`memory medium in which the logical sector address can be
`stored for safeguarding in the event of a power failure.
`[0017] FIG. 10 illustrates a dynamic look-up data struc(cid:173)
`ture to track data stored in the flash memory medium.
`[0018] FIG. 11 illustrates a process for dynamically allo(cid:173)
`cating look-up data structures for tracking data on the flash
`memory medium.
`[0019] FIG. 12 is a diagram of the flash memory medium
`viewed and/or treated as a continuous circle by the flash
`driver.
`[0020] FIG. 13 depicts another illustration of the media
`viewed as a continuous circle.
`[0021] FIG. 14 illustrates a process used by the sector
`manager to determine the next available free sector location
`for the flash driver to store data on the medium.
`[0022] FIG. 15 illustrates another view of media treated as
`a continuous circle.
`[0023] FIG. 16 is a flow chart illustrating a process used
`by the compactor to recycle sectors.
`[0024] FIG. 17 shows one exemplary result from the
`process illustrated in FIG. 16.
`[0025] FIG. 18 illustrates a logical representation of a
`NOR flash memory medium divided in way to better support
`the processes and techniques implemented by the flash
`driver.
`
`DETAILED DESCRIPTION
`
`[0026] The following discussion is directed to flash driv(cid:173)
`ers. The subject matter is described with specificity to meet
`statutory requirements. However, the description itself is not
`
`

`

`US 2003/0163630 Al
`
`Aug. 28, 2003
`
`2
`
`intended to limit the scope of this patent. Rather, the
`inventors have contemplated that the claimed subject matter
`might also be embodied in other ways, to include different
`elements or combinations of elements similar to the ones
`described in this document, in conjunction with other
`present or future technologies.
`
`[0027] Overview
`
`[0028] This discussion assumes that the reader is familiar
`with basic operating principles of flash memory media.
`Nevertheless, a general introduction to two common types
`of nonvolatile random access memory, NAND and NOR
`Flash memory media, is provided to better understand the
`exemplary implementations described herein. These two
`example flash memory media were selected for their current
`popularity, but their description is not intended to limit the
`described implementations to these types of flash media.
`Other electrically erasable and programmable read-only
`memories (EEPROMs) would work too. In most examples
`used throughout this Detailed Description numbers shown in
`data structures are in decimal format for illustrative pur(cid:173)
`poses.
`
`[0029] Universal Flash Medium Operating Characteristics
`
`[0030] FIG. 1 and FIG. 2 illustrate logical representations
`of example NAND and NOR flash memory media 100, 200,
`respectively. Both media have universal operating charac(cid:173)
`teristics that are common to each, respectively, regardless of
`the manufacturer. For example referring to FIG. 1, a NAND
`flash memory medium is generally split into contiguous
`blocks (0, 1, through N). Each block 0, 1, 2, etc. is further
`subdivided into K sectors 102; standard commercial NAND
`flash media commonly contain 8, 16, or 32 sectors per block.
`The amount of blocks and sectors can vary, however,
`depending on the manufacturer. Some manufacturers refer to
`"sectors" as "pages." Both terms as used herein are equiva(cid:173)
`lent and interchangeable.
`
`[0031] Each sector 102 is further divided into two distinct
`sections, a data area 103 used to store information and a
`spare area 104 which is used to store extra information such
`as error correction code (ECC). The data area 103 size is
`commonly implemented as 512 bytes, but again could be
`more or less depending on the manufacturer. At 512 bytes,
`the flash memory medium allows most file systems to treat
`the medium as a nonvolatile memory device, such as a fixed
`disk (hard drive). As used herein RAM refers generally to
`the random access memory family of memory devices such
`as DRAM, SRAM, VRAM, VDO, and so forth. Commonly,
`the size of the area spare 104 is implemented as 16 bytes of
`extra storage for NAND flash media devices. Again, other
`sizes, greater or smaller can be selected. In most instances,
`the spare area 104 is used for error correcting codes, and
`status information.
`
`[0032] A NOR memory medium 200 is different than
`NAND memory medium in that blocks are not subdivided
`into physical sectors. Similar to RAM, each byte stored
`within a block of NOR memory medium is individually
`addressable. Practically, however, blocks on NOR memory
`medium can logically be subdivided into physical sectors
`with the accompanying spare area.
`
`referred to herein as "memory requirements" or "rules") of
`flash devices can be summarized as follows:
`
`[0034] 1. Write operations to a sector can change an
`individual bit from a logical '1' to a logical '0', but not from
`a logical '0' to logical '1' (except for case No. 2 below);
`
`[0035] 2. Erasing a block sets all of the bits in the block
`to a logical '1';
`
`[0036] 3. It is not generally possible to erase individual
`sectors/bytes/bits in a block without erasing all sectors/bytes
`within the same block;
`
`[0037] 4. Blocks have a limited erase lifetime of between
`approximately 100,000 to 1,000,000 cycles;
`
`[0038] 5. NAND flash memory devices use ECC to safe(cid:173)
`guard against data corruption due to leakage currents; and
`
`[0039] 6. Read operations do not count against the write/
`erase lifetime.
`
`[0040] Flash Driver Architecture
`
`[0041] FIG. 3 illustrates pertinent components of a com(cid:173)
`puter device 300, which uses one or more flash memory
`devices to store information. Generally, various different
`general purpose or special purpose computing system con(cid:173)
`figurations can be used for computer device 300, including
`but not limited to personal computers, server computers,
`hand-held or laptop devices, portable communication
`devices, multiprocessor systems, microprocessor systems,
`microprocessor-based systems, programmable consumer
`electronics, gaming systems, multimedia systems, the com(cid:173)
`bination of any of the above example devices and/or sys(cid:173)
`tems, and the like.
`
`[0042] Computer device 300 generally includes a proces(cid:173)
`sor 302, memory 304, and a flash memory media 100/200.
`The computer device 300 can include more than one of any
`of the aforementioned elements. Other elements such as
`power supplies, keyboards, touch pads, 1/0 interfaces, dis(cid:173)
`plays, LEDs, audio generators, vibrating devices, and so
`forth are not shown, but could easily be a part of the
`exemplary computer device 300.
`
`[0043] Memory 304 generally includes both volatile
`memory (e.g., RAM) and non-volatile memory (e.g., ROM,
`PCMCIA cards, etc.). In most implementations described
`below, memory 304 is used as part of computer device's 302
`cache, permitting application data to be accessed quickly
`without having to permanently store data on a non-volatile
`memory such as flash medium 100/200.
`
`[0044] An operating system 309 is resident in the memory
`304 and executes on the processor 302. An example oper(cid:173)
`ating system implementation includes the Windows®CE
`operating system from Microsoft Corporation, but other
`operation systems can be selected from one of many oper(cid:173)
`ating systems, such as DOS, UNIX, etc. For purposes of
`illustration, programs and other executable program com(cid:173)
`ponents such as the operating system are illustrated herein as
`discrete blocks, although it is recognized that such programs
`and components reside at various times in different storage
`components of the computer, and are executed by the
`processor(s) of the computer device 300.
`
`[0033] Aside from the overall layout and operational com(cid:173)
`parisons, some universal electrical characteristics ( also
`
`[0045] One or more application programs 307 are loaded
`into memory 304 and run on the operating system 309.
`
`

`

`US 2003/0163630 Al
`
`Aug. 28, 2003
`
`3
`
`Examples of applications include, but are not limited to,
`email programs, word processing programs, spreadsheets
`programs, Internet browser programs, as so forth.
`[0046] Also loaded into memory 304 is a file system 305
`that also runs on the operating system 309. The file system
`305 is generally responsible for managing the storage and
`retrieval of data to memory devices, such as magnetic hard
`drives, and this exemplary implementation flash memory
`media 100/200. Most file systems 305 access and store
`information at a logical level in accordance with the con(cid:173)
`ventions of the operating system the file system 305 is
`running. It is possible for the file system 305 to be part of the
`operating system 309 or embedded as code as a separate
`logical module.
`[0047] Flash driver 306 is implemented to function as a
`direct interface between the file system 305 and flash
`medium 100/200. Flash driver 306 enables computer device
`300 through the file system 305 to control flash medium
`100/200 and ultimately send/retrieve data. As shall be
`described in more detail, however, flash driver 306 is
`responsible for more than read/write operations. Flash driver
`306 is implemented to maintain data integrity, perform
`wear-leveling of the flash medium, minimize data loss
`during a power interruption to computer device 300 and
`permit OEMs of computer devices 300 to support their
`respective flash memory devices regardless of the manufac(cid:173)
`turer. The flash driver 306 is file system agnostic. That
`means that the flash driver 306 supports many different types
`of files systems, such as File Allocation Data structure File
`System (FAT16), (FAT32), and other file systems. Addition(cid:173)
`ally, flash driver 306 is flash memory medium agnostic,
`which likewise means driver 306 supports flash memory
`devices regardless of the manufacturer of the flash memory
`device. That is, the flash driver 306 has the ability to
`read/write/erase data on a flash medium and can support
`most, if not all, flash devices.
`[0048]
`In the exemplary implementation, flash driver 306
`resides as a component within operating system 309, that
`when executed serves as a logical interface module between
`the file system 305 and flash medium 100/200. The flash
`driver 306 is illustrated as a separate box 306 for purposes
`of demonstrating that the flash driver when implemented
`serves as an interface. Nevertheless, flash driver 306 can
`reside in other applications, part of the file system 305 or
`independently as separate code on a computer-readable
`medium that executes in conjunction with a hardware/
`firmware device.
`[0049]
`In one implementation, flash driver 306 includes: a
`flash abstraction logic 308 and a programmable flash
`medium logic 310. Flash abstraction logic 308 and program(cid:173)
`mable medium logic 310 are coded instructions that support
`various features performed by the flash driver 306. Although
`the exemplary implementation is shown to include these two
`elements, various features from each of the flash abstraction
`logic 308 and flash medium logic 310 may be selected to
`carry out some of the more specific implementations
`described below. So while the described implementation
`shows two distinct layers of logic 308/310, many of the
`techniques described below can be implemented without
`necessarily requiring all or a portion of the features from
`either layer of logic. Furthermore, the techniques may be
`implemented without having the exact division of respon(cid:173)
`sibilities as described below.
`
`[0050]
`In one implementation, the Flash abstraction logic
`308 manages those operating characteristics that are univer(cid:173)
`sally common to flash memory media. These universal
`memory requirements include wear-leveling, maintaining
`data integrity, and handling recovery of data after a power
`failure. Additionally, the flash abstraction logic 308 is
`responsible for mapping information stored at a physical
`sector domain on the flash memory medium 100/200 to a
`logical sector domain associated with the file system 305.
`That is, the flash abstraction logic 308 tracks data going
`from a logical-to-physical sector addresses and/or from a
`physical-to-logical sector addresses. Driver 306 uses logi(cid:173)
`cal-to-physical sector addresses for both read/write opera(cid:173)
`tions. Driver 306 goes from physical-to-logical sector
`addresses when creating a look-up table (to be described
`below) during driver initialization. Some of the more spe(cid:173)
`cific commands issued by the file system that are dependent
`upon a certain type of flash memory media are sent directly
`to the flash medium logic 310 for execution and translation.
`Thus, the flash abstraction logic 308 serves as a manager to
`those universal operations, which are common to flash
`memory media regardless of the manufacturer for the media,
`such as wear-leveling, maintaining data integrity, handling
`data recovery after a power failure and so forth.
`[0051] FIG. 4 illustrates an exemplary block diagram of
`the flash abstraction logic 308. Flash abstraction logic 308
`includes a sector manager 402, a logical-to-physical sector
`mapping module 404, and a compactor 406. Briefly, the
`sector manager 402 provides a pointer to a sector available,
`i.e., "free" to receive new data. The logical-to-physical
`sector mapping module 404 manages data as it goes from a
`file system domain of logical sector addressing to a flash
`medium domain of physical sector addressing. The compac(cid:173)
`tor 406 provides a mechanism for clearing blocks of data
`(also commonly referred to in the industry as "erasing") to
`ensure that enough free sectors are available for writing data.
`Additionally, the compactor 406 helps the driver 306 system
`perform uniform and even wear leveling. All these elements
`shall be described in more detail below.
`
`[0052] Referring back to FIG. 3, the flash medium logic
`310 is used to translate logical commands, received from
`either the flash abstraction logic 308 or file system 305, to
`physical sector commands for issuance to the flash memory
`medium 100/200. For instance, the flash medium logic 310
`reads, writes, and erases data to and/or from the flash
`memory medium. The flash medium logic 310 is also
`responsible for performing ECC (if necessary). In one
`implementation, the flash medium logic 310 is program(cid:173)
`mable to permit users to match particular flash medium
`requirements of a specific manufacturer. Thus, the flash
`medium logic 310 is configured to handle specific nuances,
`ECC, and specific commands associated with controlling
`physical aspects of flash medium 100/200.
`
`[0053] FIG. 5 illustrates an exemplary block diagram of
`the flash medium logic 310. As shown, the flash medium
`logic 310 includes a programmable entry point module 502,
`1/0 module 504 and an ECC module 506. The program(cid:173)
`mable entry point module 502 defines a set of programming
`interfaces to communicate between flash abstraction logic
`308 and flash medium 100/200. In other words, the pro(cid:173)
`grammable entry points permit manufacturers of computer
`devices 300 to program the flash media logic 310 to interface
`with the actual flash memory medium 100/200 used in the
`
`

`

`US 2003/0163630 Al
`
`Aug. 28, 2003
`
`4
`
`computer device 300. The 1/0 module 504 contains specific
`code necessary for read/write/erase commands that are sent
`to the Flash memory medium 100/200. The user can pro(cid:173)
`gram the ECC module 506 to function in accordance with
`any particular ECC algorithm selected by the user.
`[0054] Tracking Data
`[0055] File system 305 uses logical sector addressing to
`read and store information on flash memory medium 100/
`200. Logical sector addresses are address locations that the
`file system reads and writes data to. They are "logical"
`because they are relative to the file system. In actuality, data
`may be stored in completely different physical locations on
`the flash memory medium 100/200. These physical locations
`are referred to as physical sector addresses.
`[0056] The flash driver 306 is responsible for linking all
`logical sector address requests (i.e., read & write) to physical
`sector address requests. The process of linking logical-to(cid:173)
`physical sector addresses is also referred to herein as map(cid:173)
`ping. Going from logical to physical sector addresses per(cid:173)
`mits flash driver 306 to have maximum flexibility when
`deciding where to store data on the flash memory medium
`100/200. The logical-to-physical sector mapping module
`404 permits data to be flexibly assigned to any physical
`location on the flash memory medium, which provides
`efficiency for other tasks, such as wear-leveling and recov(cid:173)
`ering from a power failure. It also permits the file system 305
`to store data in the fashion it is designed to do so, without
`needing intelligence to know that the data is actually being
`stored on a flash medium in a different fashion.
`[0057] FIG. 6A shows an exemplary implementation of a
`data structure (i.e., a table) 600A generated by the flash
`driver 306. The data structure 600A is stored in a volatile
`portion of memory 304, e.g. RAM. The data structure 600A
`includes physical sector addresses 602 that have a corre(cid:173)
`sponding logical sector address 604. An exemplary descrip(cid:173)
`tion of how table 600A is generated is described with
`reference to FIG. 7.
`[0058] FIG. 7 illustrates a process 700 used to track data
`on the flash memory medium 100/200 when the file system
`305 issues write requests to the flash driver 306. Process 700
`includes steps 702-718. Referring to FIGS. 6A and 7, in
`step 702, flash abstraction logic 308 receives a request to
`write data to a specified logical sector address 604.
`
`In step 704, the sector manager 402 ascertains a
`[0059]
`free physical sector address location on the flash medium
`100/200 that can accept data associated with the write
`request (how the sector manager 402 chooses physical sector
`addresses will be explained in more detail below). A free
`physical sector is any sector that can accept data without the
`need to be erased first. Once the sector manager 402 receives
`the physical sector address associated with a free physical
`sector location, the logical-to-physical sector mapping mod(cid:173)
`ule 404 assigns the physical sector address to the logical
`sector address 604 specified by write request forming a
`corresponding relationship. For example, a physical sector
`address of O through N can be assigned to any arbitrary
`logical sector address O through N.
`
`[0060] Next, in step 706, the logical-to-physical sector
`mapping module 404 stores the corresponding relationship
`of the physical sector address to the logical sector address in
`a data structure, such as the exemplary table 600A in
`
`memory 305. As shown in the exemplary data structure
`600A, three logical sector addresses 604 are assigned to
`corresponding physical sector addresses 602.
`
`[0061] Next, in step 708 data associated with the logical
`sector address write request is stored on the flash medium
`100/200 at the physical sector address location assigned in
`step 704. For example, data would be stored in physical
`sector address location of zero on the medium 100/200,
`which corresponds to the logical sector address of 11.
`
`[0062] Now, in step 710, suppose for example purposes
`the file system 305 issues another write request, but in this
`case, to modify data associated with a logical sector address
`previously issued in step 702. Then, flash driver 306 per(cid:173)
`forms steps 712 through 714, which are identical to steps
`704 through 708, respectively, which are described above.
`
`In step 718, however, after the updated data asso(cid:173)
`[0063]
`ciated with step 710 is successfully stored on the flash
`medium 100/200, the logical-to-physical sector mapping
`module 404 marks the old physical sector address assigned
`in step 704 as "dirty." Old data is marked dirty after new data
`is written to the medium 100/200, so in the event there is a
`power failure in the middle of the write operation, the
`logical-to-physical sector mapping module 404 will not lose
`old data. It is possible to lose new or updated data from steps
`702 or 710, but since there is no need to perform an erase
`operation only one item of new or modified data is lost in the
`event of a power failure.
`
`[0064] FIG. 6B shows a data structure 600B which is the
`same as data structure 600A, except its contents have been
`updated. In this example the file system 305 has updated
`data associated with logical sector address 11. Accordingly,
`the flash driver 306 reassigns logical sector address 11 to
`physical sector address 3 and stores the reassigned corre(cid:173)
`sponding relationship between the these two addresses in
`data structure 600B. As illustrated in data structure 600B,
`the contents of logical sector 11 are actually written to
`physical sector address 3 and the contents of sector O are
`marked "dirty" after the data contents are successfully
`written into physical sector address 3 as was described with
`reference to steps 710-718.
`
`[0065] This process of reassigning logical-to-physical sec(cid:173)
`tor address when previously stored data is updated by the file
`system 305, permits write operations