United States Patent (19)
`Holzhammer
`
`(54) NON-VOLATILE DISK CACHE
`75 Inventor: Gerald S. Holzhammer, Aloha, Oreg.
`(73) Assignee: Intel Corporation, Santa Clara, Calif.
`
`(21) Appl. No.: 252,619
`22 Filed:
`Jun. 1, 1994
`Related U.S. Application Data
`
`63 Continuation of Ser. No. 715,105, Jun. 12, 1991, abandoned.
`(51) Int. Cl. ...................................... G06F 11/34
`52 U.S. Cl. ........................................ 395/1822; 365/228
`58) Field of Search ..................................... 395/575,403,
`395/468, 469, 488, 1822; 36.5/228, 229;
`371/66
`
`56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,327,410 4/1982 Patel et al..
`4,523,295 6/1985 Zato ........................................ 364/900
`4,578,774 3/1986 Muller ....................................... 371/62
`4,897,631
`1/1990 Jundt et al. .
`4,901,283 2/1990 Hanbury et al. ........................ 365/.222
`4,908,790 3/1990 Little et al. ...
`... 364,900
`4.959,774. 9/1990 Davis ........
`... 364/200
`4,977,537 12/1990 Dias et al. ...
`... 364/900
`4,979,143 12/1990 Takano et al.
`... 364/900
`5,018,148 5/1991 Patel et al. ................................ 371/66
`5,175,842 12/1992 Totani .......
`... 364,228
`5,204,840 4/1993 Mazur .......
`... 365,228
`5,204,963 4/1993 Noya et al. ...
`... 36.5/229
`5,283,884 2/1994 Menon et al. .......................... 364/200
`5,297,148 3/1994 Harari et al..
`
`
`
`||||||IIII
`USOO5519831A
`11
`Patent Number:
`5,519,831
`45) Date of Patent:
`May 21, 1996
`
`FOREIGN PATENT DOCUMENTS
`0528039 2/1993 Japan .............................. G06F 12/08
`6231053 8/1994 Japan ................................ G06F 1/30
`220 1268 8/1988 United Kingdom.
`
`Primary Examiner-Robert W. Beausoliel, Jr.
`Assistant Examiner-Albert Decady
`Attorney, Agent, or Firm-Blakely, Sokoloff, Taylor & Zaf
`al
`
`ABSTRACT
`57
`A method and apparatus in a computer system for storing
`data from a volatile cache during a power loss. The appa
`ratus comprises a volatile cache memory and a non-volatile
`memory. In a preferred embodiment, the non-volatile
`memory is an electrically erasable programmable read-only
`memory. The device further comprises power loss detection
`logic which detects the power loss in the computer system
`and copy control logic which copies the data contained in the
`volatile cache memory to the non-volatile memory upon
`detection of the power loss. The copy control logic is
`coupled to the volatile cache, the non-volatile memory, and
`the power loss detection logic. In a preferred embodiment,
`the copy control logic and the power loss detection logic
`comprise a microcontroller. The device lastly comprises a
`power source coupled to the volatile cache memory and the
`copy control logic, the power source being independent of
`the computer system power. In a preferred embodiment, the
`power source comprises a battery coupled to the microcon
`troller and the volatile and non-volatile memories. Methods
`are provided to copy to and restore data from a non-volatile
`memory when computer system power is lost or restored.
`
`18 Claims, 10 Drawing Sheets
`
`------------------
`
`u u u - - - - - - -w as ess m um um m ra
`
`
`
`1-4 MByte
`DRAM
`
`
`
`Non-Volatile Meno
`
`Non-Volatile
`Cache
`
`
`
`32
`
`322
`
`Backup State
`
`s
`
`323
`
`1-4MByte
`EEPROM
`
`a
`
`as
`
`Battery B
`
`350
`
`L-------------------
`
`- m ms a
`
`a ru r- -
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`U.S. Patent
`
`May 21, 1996
`
`Sheet 1 of 10
`
`5,519,831
`
`
`
`Processor
`102
`
`Memory
`04
`
`Cache SC
`12
`
`Bus
`
`101
`
`Figure 1 (Prior Art)
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`U.S. Patent
`
`May 21, 1996
`
`Sheet 2 of 10
`
`5,519,831
`
`200
`
`Device Switch
`Driver A 202
`
`Dev 1
`Dev 2
`
`
`
`
`
`201
`
`Dev in
`
`Driver A 204
`
`
`
`Figure 2 (Prior Art)
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`U.S. Patent
`
`May 21, 1996
`
`Sheet 3 of 10
`
`5,519,831
`
`
`
`Non-Volatile Memo
`
`Non-Volatile
`Cache
`
`1-4MByte
`EEPROM
`
`1N 1 V
`Dana. - uC
`
`---.
`r
`......... \ Battery B
`
`------------------------------------ -
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`U.S. Patent
`U.S. Patent
`
`May 21, 1996
`
`Sheet 4 of 10
`
`5,519,831
`5,519,831
`
`
`
`
`
`IcvVJoAL
`
`gJoAL
`
`painsi]
`
`
`
`a[NeIOA-UON
`
`AUGayoeD
`
`Tip
`
`uoneINnsIJUO-)
`
`uonezyenuy
`
`
`
`YOHMSao1Aoq
`
` tOFIOATIGSvIAUG
`
`¢AITAdd
`
`<I
`JOAUC
`uAdd
`
`lOv
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`
`
`

`

`U.S. Patent
`
`May 21, 1996
`
`Sheet S of 10
`
`5,519,831
`
`RAM CACHE
`311
`------------------- '?----------------- -
`CACHE TAG
`CACHE DATA
`O
`Sector Length
`Number (In
`553 Sectors
`
`Data
`
`55S
`
`
`
`
`
`554.
`
`511 bytes
`
`-
`
`/ uCONTROLLERRAM
`312
`
`Non-Volatile Ti
`Memory Data
`--- Cache-SS
`- - - -
`- - - -
`Non-Volatile I
`Memory Cachel
`-- Index-90
`
`Figure 5
`
`
`
`
`
`Dirty Pointer
`71
`
`Length
`
`572
`
`56
`
`562
`
`Non-Volatile
`Cache
`Available Pointel
`- - - -
`Non-Volatile
`Index Pointer
`56
`
`Index Erase
`
`Cache Erase
`
`564
`
`574
`
`-
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`U.S. Patent
`
`May 21, 1996
`
`Sheet 6 of 10
`
`5,519,831
`
`NON-VOLATILE CACHE
`
`
`
`
`
`
`
`
`
`
`
`CACHE DATA
`650
`O
`Logical Sector Length
`Drive Number (In
`6S
`653. Sectors
`
`N"
`
`511 bytes
`
`Data
`
`655
`
`Non-Volatile
`Index
`-- Pointer-36
`
`
`
`
`
`
`
`562
`
`-----
`Non-Volatile
`Cache
`Available Pointed
`Figure 6
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`U.S. Patent
`
`May 21, 1996
`
`Sheet 7 of 10
`
`5,519,831
`
`
`
`
`
`T02
`Power Down
`
`
`
`T04
`NV POINTER(i) =
`DIRTYPOINTER(i)
`
`
`
`
`
`
`
`
`
`
`
`707
`NV DIRTY POINTER =
`NV POINTER
`
`708
`Update Non-Volatile Memory Cache
`Index at Non-Volatile Index Pointer
`
`709
`Turn Off Battery Power
`
`POWER-DOWNSEQUENCE
`700
`
`Figure 7
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`U.S. Patent
`
`May 21, 1996
`
`Sheet 8 of 10
`
`5,519,831
`
`
`
`
`
`802
`Locate Last Valid Entry. In
`Non-Volatile Cache Index
`
`POWER-UPRESTORATION
`PROCESS
`800
`
`804
`Update Fixed Media from
`NV DIRTY DATAi)
`
`
`
`No
`
`807
`Enough Memory In Non-Volatile
`Data Cache for Next Power
`Down
`
`No
`
`
`
`808
`Erase Non-Volatile Data Cache
`
`809
`Reset Non-Volatile Available Pointer
`
`
`
`
`
`
`
`Figure 8a
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`U.S. Patent
`
`May 21, 1996
`
`Sheet 9 of 10
`
`5,519,831
`
`
`
`
`
`810
`Increment Cache Erase Count
`
`POWER-UPRESTORATION
`PROCESS
`
`1.
`
`800
`
`811
`Enough Memory In
`Non-Volatile Index for Next
`Power down
`
`Yes
`
`
`
`
`
`
`
`NO
`
`812
`Erase Non-Volatile Cache Index
`
`
`
`813
`Reset Non-Volatile Index Pointer
`
`814
`Increment Index Erase Count
`
`1.
`
`815
`Erasures > 10,000?
`
`No
`
`818
`Update Pointers and Erase Counts
`
`1.
`
`
`
`
`
`816
`Disable Write-Back Caching
`
`Yes
`
`
`
`817
`Notify User to Replace Non-Volatile
`Cache Memory
`
`Figure 8b
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`U.S. Patent
`
`May 21, 1996
`
`Sheet 10 of 10
`
`5,519,831
`
`8x128Kx8 (1Mb EEPROM)
`
`
`
`Boot Block
`
`Parameter
`Parameter
`
`64 KLOBYTES
`
`32 KLOBYTES
`32 KILOBYTES
`
`896 KLOBYTES
`
`Figure 9
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`5,519,831
`
`1.
`NON.VOLATLE DISK CACHE
`
`This is a continuation of application Ser. No. 07/715,105,
`filed Jun. 12, 1991, now abandoned.
`
`BACKGROUND OF THE INVENTION
`
`2
`"write-through” (or store-through) cache replacement algo
`rithm; and the “write-back' (or copy back or store in) cache
`replacement algorithm. In a write-through replacement algo
`rithm, every time a write is made the information is written
`to the cache and a simultaneous request is made on the bus
`to write the data to the fixed media device(s). Cache contents
`always remain consistent with the contents of the disk drive.
`In a "write-back' cache replacement algorithm, the infor
`mation is written only to the cache. Logic in the computer
`system writes the cache block to the device only when the
`cache block is modified. In a write-back caching system,
`cache contents are considered "dirty' when they are incon
`sistent with the contents of fixed media device(s). If the
`cache contents are modified and the disk has not yet been
`updated from the cache, then the cache block is flagged as
`"dirty' indicating that it needs to be written to the disk. An
`area is typically reserved in a cache such as 120 to store
`information to indicate whether blocks stored in the cache
`are clean or dirty. This area is known as a cache "tag.” If a
`block is "dirty,’” then the location is flagged using a status
`bit. The dirty block is written back to the disk at a time when
`the cache is idle, or when modified cache contents are to be
`replaced by new data. After writing the databack to the disk,
`the "dirty" bit is cleared. Under normal operating circum
`stances, a write-back cache substantially increases device
`and thus overall system performance as disk operations are
`performed only when absolutely necessary. However, if
`computer system power is lost while data contained in the
`cache is "dirty,’” then the device will not be updated with
`current data. This may result in corruption of files stored on
`the disk, because certain allocation tables or other file
`linkage information stored on the device may not be com
`plete prior to the computer system losing power. Also, data
`contained within cache 120 is irretrievably lost. The losing
`of system power while the cache contains "dirty " data is
`therefore to be avoided whenever possible to avoid data loss
`and file corruption on disk drives coupled to the computer
`System.
`A typical prior art software architecture for controlling
`fixed media devices is shown in FIG. 2, 200 in FIG. 2 is
`representative of a software architecture used by a UNDX
`(UNIX is a trademark of AT&T Bell Laboratories of Murray
`Hill, N.J.) brand operating system. 200 comprises a device
`switch unit 201 which is responsible for directing logical
`device accesses to software drivers responsible for physical
`media devices coupled to the system. For example, one
`logical device driver 202 may be directed towards physical
`device driver driver A 210, thus controlling physical devices
`121 and 122. A second logical device driver 203 may result
`in an access to a second physical device driver 211, and thus
`be directed towards physical medium 123. Numerous logical
`devices may be defined in prior art system 200, all accesses
`to particular logical devices being directed by device switch
`unit 201. Numerous logical devices may map to the same
`physical device unit(s). For instance, yet another logical
`device 204 represented in device switch unit 201 may be
`directed towards the same physical device driver A 210, and
`thus to physical media 121 and 122. Caching schemes as
`implemented by certain prior art systems are contained
`within the device driver(s) such as 210 and 211 shown in
`FIG. 2. The device drivers handle all read and write opera
`tions, whether to the cache device(s) or to the physical media
`themselves. Also, drivers 210 and 211 handle all write-back
`requests to the physical media at appropriate times, such as
`when data becomes "dirty" and when specified periods of
`time elapse under an LRU (least recently used) algorithm.
`An alternative remedy to the loss of data contained in a
`volatile cache is the use of a battery to power the cache. If
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`1. Field of the Invention
`This invention relates to the field of computer systems
`employing non-volatile media. More specifically, this inven
`tion relates to a non-volatile cache for devices such as disk
`drives in a computer system.
`2. Description Of the Related Art
`Attempts are constantly made to increase the performance
`of modem computer systems. Typically, because input/
`output devices such as disk drives are slower than the
`circuitry in computer systems (such as central processing
`units and/or memory devices), attempts have been made to
`increase the performance of these I/O devices. However,
`because such devices are electromechanical in nature, there
`is a finite limit beyond which performance cannot be
`increased. Other methods and devices have thus been devel
`oped for reducing the I/O bottleneck in order to increase
`overall computer system performance.
`Once way to reduce the information bottleneck for I/O
`devices such as a disk drives is to use a cache. A cache is a
`memory device which logically resides between a device
`and the remainder of the computer system such as a central
`processing unit(s) and/or computer bus. A cache is an area
`of memory which serves as a temporary storage area for the
`device (such as computer memory or a disk drive). Fre
`quently accessed data resides in the cache after an initial
`access and a subsequent accesses to the same data will be
`made to the cache instead of the device. A cache for memory
`typically uses a higher speed type of memory, such as static
`memory, for the cache memory than the main computer
`system's memory, which is typically implemented in
`dynamic memory. A cache for a disk drive can generally
`reside in computer main memory, but may also reside in a
`40
`separate device coupled to the system bus. One such system
`containing memory, a processor and fixed media devices
`(such as disk drives) used in conjunction with a cache is
`shown as system 100 in FIG. 1.
`System 100 in FIG. 1 is a computer system with multiple
`45
`disk drives 121 through 125. Computer system 100 com
`prises a bus 101 for communicating information between a
`processor 102 and devices such as main memory 104 and
`disk drives 121 through 125. Disk drives 121 through 125
`are accessible via lines 110 coupled to bus 101, or, alterna
`tively, through cache 120. As discussed previously, if a
`particular datum in one of the disks 121 through 125 is
`accessed that was read on a previous access, that location
`will reside in cache 120. The datum will be in the cache
`unless it has been replaced using the system's cache replace
`ment or coherency algorithm. In the case of a "cache hit '
`(the data resides in the cache), the data will be retrieved
`directly from cache 120. In the case of a "cache-miss '' (the
`data is not contained in cache 120), the information will be
`retrieved directly from the fixed media drive over lines 110
`to bus 101. The data may be made available to processor
`102, or alternatively loaded into main memory 104 in a
`direct memory access (DMA) system. In the event of a
`"cache-miss" the data will also be placed into cache 120 for
`later accesses.
`Write operations are treated differently than reads. There
`are two basic methods for writing data to a cache: the
`
`50
`
`55
`
`60
`
`65
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`3
`computer system power is lost, data contained within the
`cache is retained because memory continues to be powered
`by the battery. When system power is restored, the system
`resumes normal operation and valid data still resides in the
`cache waiting to be written-back to disk. This solution is
`dependent upon the battery having power to retain the
`memory in the cache for the duration of the system power
`loss. If the battery is exhausted during the interval when
`there is no system power, data contained in the cache will be
`lost. Because battery power is finite and memory circuits
`such as dynamic memory devices require refreshing at
`regular intervals (thus consuming power at a fairly high rate)
`special care must be taken that the battery has the capacity
`to retain the data for a worst case. Worst case failures cannot
`be absolutely anticipated, batteries sometimes suffer from
`reliability problems, resulting in premature failure and a
`system may be without power for a long period of time, so
`the loss of data in a battery-backed cache may still occur.
`One prior method to avoid corruption of fixed media
`devices coupled to a computer system is that used by the
`UNIX brand operating system during the system power-up
`initialization process (or bootstrap). During a system boot
`strap, all fixed media devices coupled to a UNIX brand
`system are scanned to determine whether any file allocation
`tables or file indices residing on each disk need to be
`restored. Incomplete files or file indices results in the inabil
`ity of the system to read these files. If any file indices or
`other file linkage information is incomplete, then the system
`software repairs the indices and pointers for the files as best
`as can be approximated to prevent the file corruption. This
`process, however, consumes an inordinate amount of real
`time during system bootstrap, because all sectors and tracks
`of allocated sections in fixed media devices coupled to the
`System must be scanned. Depending on how much storage
`is available on the system, such a fie verification process
`substantially increases the amount of time needed for system
`initialization even after losing power for only a short period
`of time. In an MS-DOS brand operating system, in contrast,
`where no such file verification process takes place, the loss
`of system power while "dirty' information is still contained
`in the cache will result in the corruption or inability of files
`and data loss in fixed media devices coupled to the system.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`SUMMARY AND OBJECTS OF THE
`INVENTION
`One of the objects of the present invention is to provide
`an improved architecture and method for storing data con
`tained in a device cache for periods when the computer
`System power is lost.
`Another object of the present invention is to provide a
`means for storing data contained in a device cache indefi
`nitely for periods when a computer system loses power.
`Another object of the present invention is to provide a
`relatively fast and efficient way for a computer system using
`caching to perform an initialization after computer system
`power has been lost.
`These and other objects of the present invention are
`provided for by an apparatus in a computer system for
`storing data from a volatile cache during a power loss. The
`apparatus comprises a volatile cache memory and a non
`volatile memory. In a preferred embodiment, the non-vola
`tile memory is an electrically erasable programmable read
`only memory. The device further comprises a means for
`detecting the power loss in the computer system and a means
`for copying the data contained in the volatile cache memory
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,519,831
`
`4.
`to the non-volatile memory upon detection of the power loss.
`The copying means is coupled to the volatile cache, the
`non-volatile memory, and the detecting means. In a pre
`ferred embodiment, the detecting and the copying means
`comprise a microcontroller. The device lastly comprises a
`means for powering coupled to the volatile cache memory
`and the copying means, the means for powering being
`independent of the computer system power. In a preferred
`embodiment, the powering means comprises a battery
`coupled to the microcontroller and the volatile and non
`volatile memories.
`These and other objects of the present invention are
`provided for by a method in a computer system of storing the
`data contained in a volatile cache for a device coupled to the
`computer system to a non-volatile memory upon losing
`computer system power. The method first detects a power
`loss in the computer system. A first location is determined in
`the non-volatile memory, the fast location being at the last
`location in the non-volatile memory at which dam was
`written. Then, a first set of data is written from the volatile
`cache into the non-volatile cache starting at the last location,
`the first set of data comprising data which has been modified
`but has not been written to the device. The method may
`further comprise determining a last location in the non
`volatile memory at which valid data resided. The method
`then writes the first set of data to the device and determines
`whether there is sufficient memory in the non-volatile
`memory to store a second set of data. If there is not sufficient
`memory then the non-volatile memory is erased and it is
`determined whether the number of erasures of the non
`volatile memory has exceeded a first value. In a preferred
`embodiment the first value is the maximum number of times
`the non-volatile memory may be erased and guarantee data
`integrity. If the number of erasures exceeds this value, then
`the computer system is inhibited from writing to the non
`volatile memory.
`These and other objects of the present invention are
`provided for by a method of restoring the data contained in
`a non-volatile memory to a computer system device coupled
`to a computer system. The method determines a last location
`in the non-volatile memory at which valid device data
`resided. Then, data starting at the last location which was
`modified but not written to the device contained in the
`non-volatile memory is written to the device. It is then
`determined whether there is sufficient memory in the non
`volatile memory to store additional data. If there is not
`sufficient memory, the non-volatile memory is erased. Then,
`it is determined whether the number of erasures of the
`non-volatile memory has exceeded a first value. If it has, the
`computer system is inhibited from writing to the non
`volatile memory. If a preferred embodiment, the user is also
`notified that the non-volatile memory needs to be replaced.
`BRIEF DESCRIPTION OF DRAWINGS
`The present invention is illustrated by way of example
`and not limitation in the figures of the accompanying
`drawings in which like references indicate similar elements
`and in which:
`FIG. 1 shows a typical prior an computer system using a
`cache.
`FIG. 2 shows the software architecture of a prior art fixed
`media software drivers which are used for reading from and
`writing to fixed media devices such as disk drives in a prior
`an computer System.
`FIG.3 shows the non-volatile disk cache of the preferred
`embodiment.
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`5,519,831
`
`5
`FIG. 4 shows a software organization used for operation
`of the non-volatile cache.
`F.G. 5 shows various data structures used in the volatile
`memory portion of the non-volatile cache.
`FIG. 6 shows data structures contained in the non-volatile
`portion of the non-volatile cache.
`FIG. 7 shows a power down sequence executed by a
`computer system which has a non-volatile cache.
`FIG. 8a and 8b shows a process executed during system
`bootstrap to restore data contained in a non-volatile cache.
`FIG. 9 shows portions of a non-volatile memory device
`which may be allocated for various functions in the pre
`ferred embodiment.
`
`10
`
`15
`
`25
`
`35
`
`6
`in a preferred embodiment, is an 80960KB or 8096 micro
`controller available from Intel Corporation of Santa Clara,
`Calif. although any microcontroller of sufficient capability
`may be used. Microcontroller 330 provides all the necessary
`write-back operations required by the computer system via
`RAM cache 311, and/or fixed media devices such as disk
`drives 121 through 125 as shown in FIG. 1. Further, device
`300 comprises a non-volatile memory portion 320 which is
`comprised of one to four megabytes (depending on total disk
`storage space) of electrically erasable programmable read
`only memory (EEPROM) such as a one megabyte CMOS
`EEPROM SIMM (single inline memory module, for
`example, a pan No. iSM001FLKA manufactured by Intel
`Corporation of Santa Clara, Calif.), or a one or four mega
`byte memory card (for example, an iMC001FLKA one
`megabyte memory card, or iMC004FLKA four megabyte
`memory card available from Intel Corporation). Non-vola
`tile memory 320 in the preferred embodiment comprises
`three areas for the storage of various information. Nonvola
`tile cache 321 is used for storing information contained in
`RAM cache 311 when system power is lost. Backup state
`322 is used for storing status information regarding whether
`the backup of non-volatile cache 321 was "successful. '
`Further, memory device 320 comprises microcontroller
`instructions 323 for the performance of certain operations by
`microcontroller 330 such as copying data from 310 to
`non-volatile memory 320. Specific operations of microcon
`troller 330 will be discussed in more detail below.
`Organization for a system using device 300 shown in FIG.
`3 is discussed with reference to FIG. 4. 400 in FIG. 4 shows
`a computer system similar to that discussed with reference
`to FIG.2 except that 400 includes non-volatile cache driver
`410 which resides between device switch unit 401 and
`drivers 420 and 430. Drivers 420 and 430 control physical
`media such as 431 through 433. For instance, several logical
`drivers such as 402, 403, and 404 may be accessible on
`device switch unit 401. Each of these logical devices will be
`accessible through driver 410 which in turn drives com
`mands to physical device drivers 420 and 430 in system 400.
`Driver 410 will be operative upon certain configuration and
`initialization information 411 and timer interrupt informa
`tion 412 according to a user's requirements. For instance, a
`user may specify an LRU algorithm wherein certain infor
`mation residing in the cache is written back to devices such
`as 431 through 433 when the data contained in the RAM
`cache has not been accessed for a predetermined period of
`time as indicated by timer interrupt device 412. Non-volatile
`cache driver 410 operates as a write-back cache during
`system operation using RAM cache area 311 in FIG. 3
`although it may also operate in write-through mode. During
`system power loss events or system bootstrapping, cache
`driver 410 will perform certain procedures to backup or
`restore information in RAM cache 311. All of the logical
`drivers such as 402 through 404 residing in the system will
`map to non-volatile driver 410, and non-volatile driver 410,
`during write-backs from cache 300, will control physical
`device drivers such as 420 and 430.
`In a UNIX or MS-DOS brand operating system, driver
`410 is designed to intercept disk operations which are
`generated by drivers such as 402, 403, and 404 residing in
`the operating system. This is done by replacing the entry
`points of the standard drivers in device switch table 401 with
`the entry point of non-volatile cache driver 410. The original
`entry points are saved internally by cache driver 410 and
`each physical driver is invoked to transfer data to/from disks
`at required times. Thus, all accesses made by standard disk
`drivers residing in the operating system will appear to
`
`20
`
`DETALED DESCRIPTION
`A non-volatile cache and methods for using the cache are
`described. In the following description, for the purposes of
`explanation, numerous specific details are set forth such as
`dam structures, circuitry, etc. in order to provide a thorough
`understanding of the present invention. It will be obvious,
`however, to one skilled in the an that the present invention
`may be practiced without some of these specific details. In
`other instances, well known circuits, data structures and
`techniques have not been shown in detail in order to not
`unnecessarily obscure the present invention.
`FIG. 3 shows a block diagram of the non-volatile disk
`cache 300 as used by the preferred embodiment. 300 com
`prises a volatile memory portion 310 and a non-volatile
`30
`memory portion 320. In addition, non-volatile disk cache
`300 comprises a microcontroller 330 for processing infor
`mation between memories 310 and 320 and receiving infor
`mation from a bus interface unit 340. Bus interface unit 340
`is used for coupling with a computer system bus, such as bus
`101 as shown in prior art system 100 in FIG. 1. In addition,
`300 comprises a battery A350 which is used for powering
`volatile memory 310, non-volatile memory 320, and micro
`controller 330. Battery A350 in the preferred embodiment
`is a 100 mAh lithium battery. A battery with similar capacity
`40
`may be used in an alternative embodiment, such as a
`nickel-cadmium battery. In an alternative embodiment, 300
`may comprise a second battery B 360 which augments the
`capacity of battery A in case of a failure of battery A350.
`These batteries are used for powering cache memory 310,
`microcontroller 330, and EEPROM 320 when computer
`system power is lost.
`300 basically comprises two portions of memory: volatile
`memory 310 and non-volatile memory 320. Volatile memory
`310, in the preferred embodiment, comprises approximately
`one or four megabytes of dynamic random access memory
`(DRAM). This provides sufficient space for a RAM cache on
`a system comprising 10 to 40 gigabytes of fixed media
`storage space (as those skilled in the art will appreciate, to
`optimize performance, a cache should contain approxi
`mately 0.1 to 0.01% of the total disk storage space on a
`system). The cache and cache tag area may generally be
`known as area 311. In addition, volatile memory 310 com
`prises a temporary storage area 312 for microcontroller 330
`which is coupled to memory 310. During normal system
`operation, volatile memory 310 is used for storage and
`retrieval of information via bus 101 and bus interface 340.
`During computer system operation, 300 appears as a stan
`dard volatile memory RAM cache which may be operated in
`a write-back or write-through mode although the preferred
`embodiment operates in write-back mode to maximize per
`formance. 300 also comprises a microcontroller 330 which,
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Petitioner Intel Corp., Ex. 1036
`IPR2023-00783
`
`

`

`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`7
`application and system programs to be writing directly to
`disk media such as 431, 432, and 433. Read or write
`operations to physical media 431 through 433 are generally
`only performed when a read access is requested for data not
`in the cache or a write-back operation is performed.
`FIG. 5 shows various data structures contained in RAM
`cache 311 in FIG. 3. Cache 311 comprises two distinct
`sub-areas: cache tag 500; and cache data 550. Cache tag 500
`is the portion of memory used for indicating the state of
`cache data. For every entry in cache tag 500 there is a
`corresponding area in cache data area 550. Therefore, as
`shown in FIG. 5, an entry such as 501 in cache tag 500
`corresponds with an entry such as 551 in cache data 550.
`Cache tag 500 indicates whether the information contained
`in cache data area 550 is "dirty' (flagged for write-back to
`a device) and whether a location is allocated or not. Each
`entry such as 501 in cache tag 500 comprises three distinct
`fields: free field 502; dirty field 503; and pointer field 504.
`Free field 502 is a flag which indicates whether the block in
`cache data area 550 is available or not. A one indicates that
`the location is available, and a Zero indicates that the block
`is allocated. Dirty field 503 is a flag which indicates whether
`the corresponding location in cache data area 550 should be
`written-back to disk. A one indicates that a write-back is
`required (the block is “dirty'), and a zero indicates that the
`block is "clean' (a write-back is not required).
`Finally, each entry such as 501 contained in cache tag 500
`contains a pointer field 504 which points to the next dirty
`entry block in cache tag 500. When dirty data is written back
`to devices coupled to the system (such as 121 through 125),
`pointer 504 is tracked in each entry until no more dirty data
`is located. The write-back operation is optimized by using an
`"elevator-seeking " method to minimize disk head move
`ments. The elevator-seeking is performed in the preferred
`embodiment wherein microcontroller 330 scans through all
`dirty blocks in the cache to arrange the entries using a
`second data structure by track and sector number for each
`physical device. Then, using this second data structure, each
`of the blocks is written back to disk in an ordered fashion.
`In an alternative embodiment, data may be stored in the
`cache ordered by track and sector for each physical device
`in order to implement elevator-seeking write-backs. Write
`back operations should be optimized to make them as
`efficient as possible and various techniques for optimizing
`write-back operations are well-known to those skilled in the
`art.
`The second portion of data contained within RAM cache
`311 is cache data area 550. Cache data area 550 contains
`entries such as 551 which correspond to entries such as 501
`in cache tag 500. Each entry such as 551 in cache data 550
`comprises four distinct fields: logical drive 552; sector
`number 553; length (in sectors) 554; and data 555. When a
`write-back is performed by microcontroller 330, each of the
`fields is used to indicate the location, in a l