|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`USIJ06463509Bl
`
`US 6,463,509 Bl
`(10) Patent N0.:
`(12) United States Patent
`Teoman ct al. Oct. 8, 2002 (45) Date of Patent:
`
`
`
`(54) PRELOADING DATA IN A CACHE MEMORY
`ACCORDING To USER_SPEC[F1E])
`PRELOAD CRITERIA
`
`..
`-. n
`Inventor” 3:5"S::°I{l:::£i:;”
`
`(75)
`
`.
`
`(73) Assignec: Motive Power, Inc., San Mateo, (TA
`(US)
`
`*
`
`_
`) Notrce:
`
`(
`
`‘
`_
`_
`_
`_
`bub‘jectto any dlrsclatmeri, the term of {21?
`931$“! ‘5 “mm c‘ 0': allusmd und“ ‘3
`U'E‘L' 154th) by U (idyb'
`
`(21) APPI-N0-109i233fi56
`.
`7')
`.
`-
`_
`(W mm
`Jan 26’ 1999
`,
`.
`. 7
`(xtlfih IZJ'DII
`(2,1))
`Int: Ll.
`711.1137, 711i118é‘711il41,
`L.) US. Cl.
`711’}15-, 71 1’ 113
`.
`711f118, [37,
`(58) Field of Search
`711.138, 129, 113, 141, 152, 3, 125; 71052;
`713mm; 7145
`
`(56)
`‘
`
`References Cited
`
`'
`
`US. PATENT DOCUMENTS
`9 9
`K
`_
`$193,; Eggs“ ct al
`4;,197? (:D’diclal‘
`Denko
`10,1195“ {(0.1de
`"#1982 Stewart et al.
`.3er Branlingham ct al.
`
`
`251985 DIka El :11-
`[£1987 Dixon et al.
`I??? “a'ford
`(Me I
`@1993 Ho‘tle'
`3
`mg” Kobayashiel aL
`1U1993 walkins [.1 “L
`2f1994 Arintilli el al.
`3r1994 Challa ct al.
`
`3
`
`f
`
`__
`
`2
`{520966 A
`A
`4’295,305 A
`4,342,079 A
`4,435,?75 A
`4,5“),954 A "
`tl,63'i_.024 A ‘"
`Erlzs’Sm A
`i
`gills-689 A
`5;226:168 A
`5,263,142 A
`5,283,457 A
`3291584 A
`
`“U133
`Tl4r’819
`
`3.1994 Nicholson et al.
`5,293,622 A
`5,359,?13 A * 10,11994 Moran cl at.
`5,396,596 A
`3r1905 Hashemi el all.
`5,420,998 A
`SAWS llorning
`5,431,018 A
`7f1995 Kohayashi ct al.
`5,448,?19 A *
`snags Schultzetal.
`(List continued on next page.)
`
`OTHER PUBLICATIONS
`
`T1062
`
`anus
`
`International Search Report in connection with International
`Application NO, PCTEUSOOIOZUG (6 pages),
`“The NO System”, Inside Windows NT Second Edition,
`Microsoft Press, David A. Solomon, pp. v—xiv, 325—393,
`1998.
`
`"Filter Drivers", Windows NT File System Internals A
`Developer’s Guide Rajeev Nagar, O’Rielly 8.: Associates,
`..
`’
`Inc, pp. vtI—x, 615-667, 1997.
`Prim“? Emmfler_0avid Hudspcth
`Aflfsmm ExamflerAhd l;_ vI-Zeng
`(74) Attorney-Agent, or I‘Irrrr—Blakely, Sokolofi', Taylor &
`Zafman LL13
`
`(5?)
`
`‘
`
`ABSTRAC’I
`
`An apparatus and method for caching data in a storage
`device of a computer system. A relatively high-speed,
`intermediateAvolume storage device is operated as a user-
`configurable cachekequests to accessamassstorage device
`such as a disk or tape are intercepted by a device driver that
`compares the access request against a directory of [he
`Lflnlcnls (If
`[his “Slir‘LFIl-Ifigurabll‘z CHChC.
`“1‘: User-
`configurable cache contains the data sought to be accessed,
`the access request
`is carried out
`in the user-configurable
`cache instead of being forwarded to the device driver for the
`target mass storage device. Because the user-cache is imple-
`memcd using memory havng a dramalicauy shoner access
`time than most mechanical mass storage devices, the access
`request is fulfilled much more quickly than if the originally
`intended mass storage device was accessed. Data is pre-
`loaded and responsiver cached in the user-configurable
`cache memory based on user preferences.
`
`26 Claims, 12 Drawing Sheets
`
`'
`
`SYSIE'.‘ MEMO-"l"
`n
`- 30
`
`as
`all
`. 3.-
`] APPS|'
`MOE
`i uscrtcilt
`
`
`-.
`iIJHIvEFre| " 32
`.
`1G
`
`
`
`l
`
`
` lanaeEsstve
`nun
`
`ll‘
`
`' '
`
`armorial
`CC HI 30H 5. F
`
`'
`
`4.
`
`.é
`
`
`
`Famislnv
`iUSlB
`
`+
`.
`‘-
`
`' l_‘
`1‘.st onset
`cartrauttt'tj
`i.
`
`
`
`
`
`*
`NHWQRK
`access other
`l
`243
`r
`[AM-wan '
`NEIWDHK
`
`
`
`Human; r21“ mrwenx
`
`snava
`era'an [
`
`_
`.o '2?
`
`25 ’
`
`.
`
`3-55
`
`1
`
`Apple v. Realtime
`Proceeding No. |PR2016-01365
`APPLE 1020
`
`Apple v. Realtime
`Proceeding No. IPR2016-01365
`APPLE 1020
`
`1
`
`

`

`U.S. PATENT DOCUMENTS
`
`flay ellal-l
`29:32:? i
`ones e a.
`.
`,
`,
`2’1996 McKinley
`5,493,574 A
`$1996 Grynhcrg ct aL
`5,515,525 A
`5l1996 Moran et a].
`5,519,853 A *
`8l1996 Tan clal.
`5,551,000 A
`91,1996 Tuma cl a1.
`$555,402 A
`“1997 Lamzcnhciscr
`5594885 A
`2199? Piazza
`5 6050“ A
`50997 Zancho et al.
`5:633:484 A
`8).,199? Fisherman el al-
`3,6514?“ A
`91199? Fenwick at all
`1673394 A
`102'199? Ranlala e1 3|.
`5,680,570 A
`5,680,573 A * 10,0997 Rubin cl 3].
`
`713E400
`
`'I11f129
`
`‘ cited by examiner
`
`1111997 Williams
`5,692,190 A
`5,694,567 A * 12f1997 Bourckas el al.
`5,094,570 A * 121199? Beardsiey et al.
`-
`1:
`5:33: :13}!
`5331,1319 A
`4’1998 Judmn
`5345’?“ A
`4nqu Mizum
`_’
`’
`‘
`.
`5378,4133 A
`751998 Niel-an ct al.
`SJSLWO A
`TI1998 DeSmone el al.
`$802,566 A "‘
`9f1998 Hagerslcn
`5895'“? A
`4’1999 3°)“ ‘3' a"
`3,913,224”? A *
`6{1999 Maclhnald
`6,003,113 A * 121999 Spear elaL
`
`
`
`US 6,463,509 B1
`Page 2
`
`711;“3
`711,013
`
`711.3137
`-
`MIME.)
`71MB?
`
`
`
`2
`
`

`

`
`
`US. Patent
`
`um28.,m
`
`hS
`
`9]0
`
`mu
`
`US 6,463,509 B1
`
`w.a:
`
`m.mm
`
`3525
`
`$9552
`
`
`
`uwas553$32ama:
`éaamz
`
`mamaxma
`
`mmfiogzoo
`
`xmamamame
`
`
`
`mzoqomijmhzoo
`
`205255
`
`wemam
`
`w
`
`xuqomo
`
`mm
`
`.Wm\
`
`mamq
`
`om,
`
`
`
`>moEmEEmhm>m
`
`
`
` zofizgxma8.11$3258
`
`$9252
`
`aMafia
`
`wwDEmmam
`
`wzfiflaog
`
`:2:
`
`m:
`
`
`
`
`
`mmmk$0352xmoEEz
`
`mm>mmm
`
`
`
`3
`
`
`
`
`
`
`
`

`

`
`
`US. Patent
`
`Oct. 8, 2002
`
`Sheet 2 0f 12
`
`US 6,463,509 B1
`
`RETURN DATA
`RE READ}
`
`UO REOUEST
`40
`
`T
`
`’A T
`r 8 ES
`
`A
`|
`L“— __J
`
`N
`
`
`V SYSTEM MEMORY
`
`
`{08 CACHE}
`
`
`
`ACCESS
`TIME
`
`USER CACHE
`
`'
`SMALLEST
`
`g
`
`VOLUME
`
`ACCESS
`
`MASS STORAGE
`
`{DISK TAPE. SEMICONDUCTOR)
`
`
`
`SLOWEST
`
`LARGEST
`
`L___________._
`
`
`
`4
`
`

`

`US. Patent
`
`Oct. 8, 2002
`
`1B905.,3
`
`M86.EEO;352mmE
`
`mxo<o
`
`Emmacmm
`
`55%
`
`JnEm:mafiam.s_mm.w:Hm%_m:5$235£88.15
`
`o:
`
`am?)559QSmmygA_522%9.$32;
`a.;i
`
`o:
`
`mxoéEm:\mozoigdna
`
`HmmDONm
`
`ow
`
`
`
`5
`
`
`
`
`
`
`

`

`US. Patent
`
`Oct. 8, 2002
`
`Sheet 4 of 12
`
`1B905,36A,6SU
`
`_,_
`
`am.
`
`
`
`
`
`5..
`
`.mum:.
`
`we
`
`92fig
`
`boom
`
`mmqggm:
`
`aim
`
`03am
`
`
`
`EBEQQ.
`
`
`
`man.
`
`$53_$33.:F;
`
`hmwgcmm
`
`mm
`
`Egg:
`
`EEEE“
`
`>Eso¢a
`
`
`
`mumflommmgommm3Eton..35$
`
`
`
`
`EOE0mmdama524%3mgmamaamg5355
`|..853mi
`
`gamma3%«53fie
`
`
`.Emam. mm:”aa_.EjOEZSétgmamam325:5?52%5335..
`
`
`IIaI“V
`
`
`
`NWSE.AIJ
`
`
`
`6
`
`
`
`
`

`

`
`
`US. Patent
`
`Oct. 8, 2002
`
`Sheet 5 of 12
`
`US 6,463,509 B1
`
`md:
`
`wroqomum:
`
`ammamm
`
`mmmmimmmo
`
`
`
`awardgame
`
`amwe
`
`Amquzfia9:
`
`Immmmamaze..._mpmmzowm
`Emhm>mm3:0:1/A2mmmoomm
`
`
`
`zofiqojaafi
`
`4:“.Fmmmuomm
`
`m;
`
`mmwmooma
`
`zo_._.qo:n_1¢_
`
`.263
`
`m0
`
`Ebémm
`
`mmfla
`
`mw<mo+m
`
`elm
`
`32mmxmmo
`
`mlq
`
`
`
`H.556Emma
`
`mlm
`
`mofimfigm
`
`wrmmmmuo<
`
`m.m¢umwm2
`
`amcquzqg
`
`zoz¢uzlmqv
`
`Ammmoomm
`
`mmmum:
`
`$0535;
`
`
`
`7
`
`
`
`
`
`
`
`
`
`
`

`

`
`
`tnetaPQMU
`
`Oct. 8, 2002
`
`Sheet 6 of 12
`
`US 6,463,509 B1
`
`w:
`
`EEl
`
`mafiaEmmm<§
`
`mm>mmmmoEm:
`
`moSma
`
`
`
`mmmxoqommamm
`
`mm
`
`amino3.
`
`at!
`
`
`
`
`
`mmSmEhE35m.thmmgmnmtq
`
`/mop
`
`
`
`
`Guzmmfimmfir:BEBEmmmouq.fia
`
`w.0:
`
`mm;me
`
`bomwmo
`
`
`
`8
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Oct. 8, 2002
`
`Sheet 7 of 12
`
`US 6,463,509 B1
`
`U0 REQUESTS 40
`
`w‘—‘—|
`
`U0 MANAGER {L3
`
`114
`
`ACCESS TABLE 114
`
`— -——-J
`
`(DEVICEDRIVER)
`g
`
`
`
`
`FILE SYSTEM
`DRIVER
`9.6
`
`
`
`
`
`.TFHANDLEISWIé-TIC --
`'—
`OBSERVER
`
`
`fl
`
`J
`
`USER CACHE
`
`2.5
`
`'
`
`
`
`
`USER CACHE
`DRIVER
`E
`
`
`DiSK DRIVER
`
`47
`
`
`
`
`MASS
`STORAGE
`
`
`L
`
`FIG. 7
`
`9
`
`

`

`US. Patent
`
`Oct. 8, 2002
`
`Sheet 8 of 12
`
`US 6,463,509 B1
`
`—___..—-.-————..._._—..._
`
`User Cache Properties
`
`General
`
`Automatic
`
`
`
`
`
`
`
`
`
`
`
`
`Motive Power
`
`
`
`
`
`
`
`
`
`
`
`
`
`Registration:
`Deniz Teornan
`Motive Power
`
`1451-16J7-98?9-1955
`
`System:
`User Cache memory size 512MB
`
`User Cache Hardware Version: MPSOO
`User Cache Software Version 1.41
`
`System Physical RAM: 128MB
`BIOS Version: 4.51 PG
`
`
`|
`OK
`
`Cancel
`
`| willy-jig)?!
`
`FIG. 8
`
`10
`
`10
`
`

`

`US. Patent
`
`Oct. 8, 2002
`
`Sheet 9 of 12
`
`US 6,463,509 B1
`
`| User Qaehe Properttesnd_—M
`
`Dia rjostios
`
`Initialization
`
`E User Cache enabled
`
`Cl Encryption enabled
`
`
`
`Optimization ———___.-____
`
`Write Behavior:
`
`0 Write Through (all writes immediately passed on)
`
`(5) Write Back (writes deterred)
`
`Cl Only use as a cache, no data Locking
`
`
`
`
`
`
`
`
`I
`0K 1 Cancel
`
`
`
`El Use as a boot device
`
`E:
`-_H_J
`
`
`
`|
`
`
`
`
`FIG. 9
`
`11
`
`11
`
`

`

`US. Patent
`
`Oct. 8, 2002
`
`Sheet 100112
`
`US 6,463,509 B1
`
`._=___=__.fl==
`[User Cache Properties M”
`
`
`
`a:
`
`In the background:
`
`El Always allow sufficient array capacity for system page file
`D Neuerpreload afile biggerthan
`75 MB
`Qhange...
`I
`
`U Preload all files within a launched application's folder
`
`U Preload allfiles in afolder it 5
`
`have already been accessed
`
`files
`
`Qhange...
`
`l:':‘
`
`E] Match files by extension and preload after 3
`matching files have been accessed
`
`|
`
`l
`
`Chan
`
`_
`
`ge...
`
`i
`
`
` Automatic Operation
`
`Preloading
`El Preload the system folder always
`(default checked if volume boot enabled)
`El Preload lull files, not just segments
`
`UK
`
`I
`
`I
`
`Cancel
`
`I I
`
`Epply
`
`l
`
`35
`
`FIG.1O
`
`12
`
`12
`
`

`

`US. Patent
`
`Oct. 8, 2002
`
`Sheet 11 0f 12
`
`US 6,463,509 B1
`
`Choose specific files to preload and look into array:
`
`El D Cforogram F‘IIesWetscapemetscape.exe
`E] D CnProgram FilesWdobeWhotoshop\pshop.exe
`e]
`1] D:\WorkingDlrectoryWideosWrstBinhdaymov
`D C:\Russetl's Files\Docs\Business Planwrd
`D D:wideo Benchmark\Disk Test\speed.exe
`C] C:\Program Filesmmocm
`E! E“,
`
`13.3MB
`52.8MB
`300KB
`5.3%
`38.4MB
`25.9MB
`
`
`
`D Cz'xProgram Files\Winw0rd\* .doc
`
`TOMB
`
`
`
`
`[User Cache Properties____
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LL Data Type
`
`
`
`Total:
`
`128MB
`
`Data Exciudec!
`Data LOCKBU
`
`Add
`
`127
`
`FIG. 11
`
`13
`
`13
`
`

`

`US. Patent
`
`Oct. 8, 2002
`
`Sheet 12 0f 12
`
`US 6,463,509 B1
`
`
`
`
`| User Cagexfieyefiignmfl _
`
`E’]
`
`
`
`
`
`D Generate report of present array contents
`
`C] Test array memory
`
`
`
`
`
`
`
`
`
`
`
`[j Flush array new
`[1 Archive user cache data to disk:
`
`
`
`14
`
`14
`
`

`

`
`
`l
`PRI“:IJ()AI)IN(; DATA IN A CACHE MEMORY
`ACCORDING TO USER-SPECIFIED
`PRELOAI) CRITERIA
`FIELD OF THE INVENTION
`
`The present invention relates to the field of data storage in
`computer systems, and more particularly to a user-
`configurable cache memory implemented in a high-speed
`storage.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`15
`
`3o
`
`40
`
`Many modern computer systems use inputt’output (IIO)
`buffering to speed access to data stored in mass storage
`media such as disk or tape drives. The idea behind IKO
`buffering is to store frequently accessed data from mass
`storage in a relatively small memory that can be accessed
`more quickly than the mass storage itself. ’l‘wo common
`types of U0 buffering are operating system (05) cache and
`self-thlIered mass storage. In an OS cache, the operating
`system reserves a portion of system memory to buffer data
`obtained from mass storage. The OS responds to mass
`storage access requests by determining whether the data
`sought to be accessed is buffered in the reserved portion of
`system memory and, if so, performing the requested access
`in system memory without accessing mass storage.
`OS cache has a number of disadvantages. First, because
`the system memory used for data bulIering is usually “
`volatile, the OS cache contents are lost when the computer
`system is powered down. Consequently, the OS cache must
`be reloaded each time the computer system is booted.
`Among other things, this makes the OS cache unsuitable to
`source boot files during system startup. Another disadvan—
`tage of OS cache is that the amount of system memory
`reserved for data buffering in the OS cache usually is limited
`because system memory is needed for other purposes, such
`as providing space for user applications. In some cases, the
`amount of system memory reserved data buffering may be ~
`dynamically reduced in response to requests to provide
`system memory for other purposes. Yet another disadvan-
`tage of OS cache is that the algorithm used to control what
`data is stored and what data is overwritten in the data bulTer
`usually does not support user-preferences to cache certain
`types or grouris of files.
`In a self-buffered mass storage, the mass storage hardware
`includes a relatively small butler memory that is used to hold
`the contents of recently accessed regions of the mass storage
`media. When an access request (e.g., a read or write request)
`is received in the mass storage, control circuitry for the mass
`storage first determines whether the access hits the contents
`of the buffer memory. If so, the access occurs in the buffer
`memory, potentially saving the time required to access the
`mass storage media itself. Unfortunately, self-buffered mass
`storage sulfch from many of the same disadvantages as 05
`cache. Specifically, the contents of the bulIer memory are
`usually lost on power down, and the algorithm used to
`control what data is stored in the data buffer typically does
`not support user-preferences. Another disadvantage of self-
`l)ulTered mass storage is that, because the buffer memory is
`used only for accesses to the associated mass storage, data
`from other "0 sources are not buffered. For example, the
`butter memory of a self—buficrcd mass storage device typi—
`cally cannot be used to butler data from other non-buffered
`mass storage devices in the computer system or data from
`mass storage devices outside the computer system such as
`network servers.
`
`50
`
`55
`
`so
`
`SUMMARY 01-” THE INVENTION
`
`65
`
`A method and apparatus for storing data in a cache
`memory of a computer system. User input is received that
`
`15
`
`using memory having a dramatically shorter access time
`
`US 6,463,509 B]
`
`2
`requests data to be stored in the cache memory. If the data
`is not already stored in the cache memory,
`the data is
`retrieved from a mass storage coupled to the computer
`system and stored in the cache memory.
`Other features and advantages of the invention will be
`apparent from the accompanying drawings and from the
`detailed description that follows below.
`
`BRIEF DESCRiFI'ION OF THE DRAWINGS
`
`invention is illustrated by way of example
`The present
`and not
`limitation in the figures of the accompanying
`drawings in which like references indicate similar elements
`and in which:
`
`FIG. 1 isa block diagram of a computer system according
`to one embodiment;
`FIG. 2 illustrates a memory hierarchy in a computer
`system that
`includes a user cache 25 according to one
`embodiment;
`FIG. 3 illustrates the flow of an IEO request according to
`one embodiment;
`FIG. 4 is a block diagram of the user-cache according to
`one embodiment;
`FIG. 5 illustrates the processing of IIO requests according
`to one embodiment;
`FIG. 6 illustrates file and driver objects that are used, in
`at least one embodiment, to determine the sequence in which
`device drivers are called to service an HO request;
`FIG. 7 illustrates the manner in which the HO request
`propagates down a chain of device drivers according to one
`embodiment;
`FIG. 8 is an exemplary user interface generated by the
`user cache manager to inform the user of general informa-
`tion related to the user cache and the system in which the
`user cache is installed;
`FIG. 9 is an exemplary user interface generated by the
`user cache manager to enable the user to turn on and
`configure the basic operation of the user cache;
`FIG. ll] is an exemplary user interface generated by the
`user cache manager to permit the user to configure memory
`management and preloading policies for the user cache;
`FIG. 11 is an exemplary user interface generated by the
`user cache manager to allow the user to specify commanded
`preloads; and
`FIG. 12 is an exemplary user interface generated by the
`user cache manager to permit the user to generate a report of
`the user cache contents, test the memory in the user cache,
`flush the user cache or transfer the contents of the user cache
`to a mass storage such as a tape backup.
`
`DETAJ LED DESCRIPTION
`
`intermediate—volume storage
`A relatively high—speed,
`device is operated as a user-configurable cache memory
`(“user cache”) to provide 110 bulIering. ln one embodiment,
`the user cache is implemented using random access memory
`(RAM) arranged on a hardware module that is coupled to an
`expansion bus in a computer system. Requests to access a
`mass storage device such as a disk or
`tape drive are
`intercepted by a device driver that compares the access
`request against a directory of the contents of the user-cache.
`If the user—cache contains the data sought to be accessed, the
`access request
`is carried out
`in the user-cache instead of
`being forwarded to the device driver for the target mass
`storage device. Because the user-cache is implemented
`
`15
`
`

`

`
`
`5
`
`It)
`
`15
`
`3o
`
`3
`the
`than most electro-mechanical mass storage devices,
`access request
`is fulfilled much more quickly than if the
`originally intended mass storage device was accessed.
`In one embodiment,
`the user-cache is non-volatile and
`large enough to hold several hundred megabytes worth of
`data. Consequently, by configuring the user-cache to store
`program code and configuration information used for com-
`puter system startup, the user—cache may be used as a boot
`source to provide much faster system boot up than can be
`achieved by booting out of mass storage media such as disk
`or tape.
`In another embodiment, an application program called a
`uSer cache manager is executed to receive u5er preferences
`as to what data to store and not to store in the user cache. For
`example, a user may specify to cache the contents of a folder
`or directory (c.g., the system directory that includes much of
`the operating system and system configuration files), files
`having a particular file type identifier (e.g., files with a given
`filename extension), files having particular file names, files
`accessed by a particular user and so forth. Further, unlike
`Self-buffered mass storage, the user cache is not limited to
`caching information from a particular mass storage device.
`The user cache may be used to cache data from any storage
`device in the computer system or even to cache remotely
`located data, such as a web page identified by a user~
`specified specified uniform resource locator (URL) or files H
`or directories located on a server computer. A user may also
`specify particular files, directories, URLs or other file iden-
`tification criteria indicating files that are to be excluded from
`the user cache. Further, in at least one embodiment, the user
`is prompted to indicate whether files selected for caching are
`to be “locked down” in the user cache. Files that are locked
`down in the user cache are not flushed (i.e., overwritten or
`otherwise expelled) from the user cache if the user cache
`becomes full. In this way, files sttch as system startup files
`may be locked down in the cache to ensure their availability
`during system startup. These and other intended advantages
`of the present
`invention are described below in various
`embodiments.
`Overview of a System That Includes User Cache
`FIG.
`1 is a block diagram of a computer system 10
`according to one embodiment. The computer system
`includes a processing unit 12, a system memory 16 and an
`expansion bus 18. all
`interconnected by a memory
`controllertexpansion bus bridge device 14. The expansion
`bus 18 supports connection of a number of 120 devices
`including a self-buffered disk drive controller 20 and its
`associated disk drive 26, a non-buffered disk drive controller
`22 and its associated disk drive 28, a network access device
`24 such as a modem or locaWide area network communi-
`cations card and a user cache 25. Other IIO devices maybe
`coupled to the expansion bus according to user needs. As
`shown in FIG. 1, the network access device 24 is used to
`couple the computer system 10 to a local or wide area
`network 27 which may support number of devices, including
`one or more network servers 29A, 298.
`According to one embodiment,
`the user cache 25 is a
`non-volatile storage array that is used to cache data from
`mass storage devices, such as the local disk drives 26, 28 or
`disk drives on network servers 29A, 29B. Preferably, the
`user cache 25 is constructed using random access memory
`components that have access times several orders of mag-
`nitude shorter than the mass storage devices that source the
`cached data. Consequently, by redirecting requests to access
`a mass storage device to instead access the user cache 25, the
`overall time required to complete the requested access can
`be dramatically reduced. The implementation and operation
`of the user cache 25 is discussed in detail below.
`
`35
`
`4!)
`
`45
`
`50
`
`60
`
`65
`
`16
`
`US 6,463,509 B1
`
`4
`Still referring to FIG. I, the processing unit 12 includes
`one or more processors that fetch program code from system
`memory 16 and execute the code to operate on data and to
`read and write data to the system memory 16 and to the HO
`devices on the expansion bus 18. Although not shown, the
`computer system also includes input devices to receive
`user—input (cg, keyboard and mouse) and a display device
`for presenting a user interface.
`The program code in the system memory 16 includes
`operating system (OS) program code 30, application pro-
`gram code 34 and device driver program code 32. The
`application program code 34 is executed by the processing
`unit 12 to implement application processes which, in turn,
`invoke operating system services to display user-interfaces,
`operate on user-input and access user-specified data. Ser-
`vices provided by the operating system 30 include memory
`management services, HO management services, process
`and thread management services and so forth. The operating
`system 30 also supports.
`independently installable device
`drivers 32. Each of the device drivers 32 is a program code
`entity that includes a prescribed set of routines that adhere
`to a specification defined by the operating system 30 and that
`can be invoked to process the various stages of an input:t
`output request. Thus, the device drivers 32 provide a well
`defined, relatively simple set of services to the operating
`system 30 to permit the operating system 30 to interact with
`a broad range of hardware devices without having to include
`device specific program code in the operating system 30. For
`example, when an application process invokes an operating
`System service to perform Ii‘O to a device attached to the
`expansion bus 18, the operating system 30 invokes a stan—
`dard routine within the appropriate device driver 32 to carry
`out the requested Ir'O.
`Overview of a Memory Hierarchy
`FIG. 2 illustrates a memory hierarchy in a computer
`system that
`includes a user cache 25 according to an
`embodiment ofthc present invention.Asindicated in FIG. 2,
`the user cache 25 preferably has an intermediate storage
`volume and access time relative to the system memory 16
`and the mass storage 46, but this is not required. Also,
`because the computer system may be a network of
`computers, the mass storage 46 need not be in the same
`machine as the system memory 16 and the user cache 25. For
`example, the mass storage 46 may be a disk drive on a
`network server that is accessible via a local or wide area
`network (LAN or WAN) or that can be accessed via the
`Internet using any number of transfer protocols including
`file transfer protocol (I'TP), hyper-text
`transfer protocol
`(MIT?) and so forth.
`When an 110 request 40 to access the mass storage 46 is
`issued (e.g., a file read or write request issued in the course
`of executing an application program), the Ir‘O request 40 is
`first applied to the OS cache maintained in system memory
`16. If the 110 request 40 hits the OS cache (i.e., the data
`sought to be accessed is cached in the OS cache), the access
`is performed in the OS cache. [1' the “0 request 40 is a read
`request,
`the data is returned to the requester. If the 110
`request 40 does not hit the OS cache, the 110 request 40 is
`redirected from the mass storage 46 to the user cache 25 by
`software mechanisms described below. If the IKO request 40
`hits the user cache 25, the access is performed in the user
`cache 25 without having to access the mass storage 46,
`thereby substantially reducing the overall access time. Also,
`because the user cache 25 is significantly larger than the OS
`cache and supports data preloading (discussed below), much
`higher hit rates can be achieved in the user cache than in the
`
`OS cache. Consequently, significantly fewer ItO accesses to
`
`16
`
`

`

`
`
`5
`the mass storage device need to be performed than in prior
`art systems that rely solely on the OS cache for 1,30 bu lIer-
`ing. Also, unlike storage buffers in self-buffered mass stor-
`age devices, the user cache is not limited to caching data for
`a particular mass storage device. Instead the user cache can
`be used to cache [KO data from a variety of sources,
`including data from remote storage devices such as network
`servers and web servers.
`
`Still referring to FIG. 2, if the [£0 request 40 is a read
`request and the read request hits the user cache 25, data is
`returned to the requestor from the user cache 25. If space
`permits,
`the returned data may also be stored in the OS
`cache. If the read request misses the user cache 25, the data
`is returned from the mass storage 46 and conditionally
`stored in the user cache 25. The conditions used to determine
`whether to store data obtained from mass storage 46 in the
`user cache 25 are described below. Data returned from the
`mass storage 46 may also be stored in the OS cache.
`Overview of a Method
`
`10
`
`15
`
`FIG. 3 illustrates the flow of an IlO request according to -
`one embodiment. I-Ierein, the expression “HO request” refers
`to a request to read from or write to an address that does not
`resolve to system memory. Initially, an application process
`41 generates an [(0 request 40 to read or write a file 15
`stored on a mass storage device 46. A service in the n
`operating system called an IlO manager 43 receives the IiO
`request 40 and identifies a device driver 47 associated with
`the request based on a logical
`identifier included in the
`request 40. For example, a request to read data from file
`"C:\myfiles\data.txt“ indicates that the file data.txt is to be
`read from logical disk drive C and is organized under
`subdirectory “mytlles.” Ordinarily, the lit) manager 43 will
`pass the NO request to the device driver 47 for the mass
`storage device 46 as shown by dashed arrow 44.
`in the
`embodiment of FIG. 3, however, a device driver called a
`user cache driver 45 has been inserted into the device driver
`hierarchy above the device driver 47 to intercept the U0
`request before it reaches the device driver 47. The user cache
`driver 45 inspects a directory 51 of the user cache contents
`to determine whether the data sought to be accessed (i.e., file
`15] is in the user cache 25. If the tile 15 is in the user cache,
`the user cache driver redirects the “0 request to access the
`user cache 25 instead of forwarding the IIO request to the
`device driver 4?. Otherwise, the user cache driver forwards
`the [£0 request to the device driver 47 which in turn accesses
`the file 15 in mass storage 46.
`In one embodiment, the directory 51 is maintained in the
`user cache 25 to prevent loss of the directory 51 at power
`down. At power up, the directory 51 is copied from the user
`cache 25 to a shadow directory in system memory. The user
`cache driver 45 accesses the shadow directory instead of the
`directory 5] to more quickly determine whether to redirect
`HO requests to the user cache 25.
`In an alternate
`embodiment, the shadow directory is not maintained and the
`directory 51 in the user cache is used to determine whether
`to redirect HO requests. Although more time is required to
`make the redirect determination without
`the shadow
`
`an
`
`35
`
`4!)
`
`45
`
`50
`
`.
`
`directory, the programming effort required to ensure coher-
`ency between the shadow directory and the directory 51 in
`the user cache is saved.
`It should be noted that the user cache 25 is not simply used
`to implement a hierarchical storage system in which data is
`either stored in the user cache or alternatively in the mass
`storage 46 (c.g., in a typical hierarchical storage system, data
`may be swapped between a relatively fast and a relatively
`slow mass storage according to system needs). Instead, the
`user cache is operated to cache data from the mass storage.
`
`60
`
`65
`
`17
`
`US 6,463,509 B1
`
`6
`That is, a copy of the data stored in the mass storage 46 is
`stored in the user cache along with a directory entry indi-
`cating the address of the corresponding data in mass storage.
`Also, unless otherwise made clear from context, the term
`data isused broadly herein to refer to both program code and
`operand data.
`User Cache Hardware
`ll [(1. 4 is a block diagram of the user-cache 25 according
`to one embodiment. The user-cache 25 includes bus inter-
`face circuitry 61, a DRAM controller 63 and a plurality of
`rows (1 through N} of DRAM components 68A—68C,
`69A—69C, "NA—70C. Each of the DRAM components
`includes an address and control input (NC), a data path
`interface (D) and a power input (PWR). The data path
`interface of each DRAM component within a given row is
`coupled to the bus interface circuitry 61 via a respective
`portion of a datapath 73. The address and control inputs of
`the DRAM components within a given row are coupled to a
`common address path and a common control path from the
`DRAM controller 63. The address path and control path for
`each DRAM row are depicted for simplicity in FIG. 4 as a
`single path ADDRICTL 75A, 753, 75C. In one embodiment,
`the address path is a multiplexed address path in which a row
`and column address components of a complete address are
`transferred to the DRAM components in separate transfers.
`The control path to each row of DRAM components pro-
`vides a set of signals that
`indicate, for example, when to
`strobe a row or column address into a row of DRAM
`
`components, when to activate or preeharge an addressed row
`of memory cells within a row of DRAM components, and
`whether to read or write a column ot‘data within an activated
`row of memory cells. Commands to enter reduced prJWer
`state and to perform refresh operations are also delivered via
`the control path.
`According to one embodiment, older generation DRAM
`components, such as synchronous DRAM (SDRAM) com~
`ponents are used in the user cache 25 to implement a
`relatively large storage array at relatively low cost. For
`example, a 2.56 megabyte (MB) user cache may be imple-
`mented at relatively low cost using eight 32 MB SDRAM
`components. User caches having larger or smaller storage
`capacity may be implemented using even older generation
`DRAM components (e.g., extended data out (EDO) DRAM,
`fast page mode (FI’M) DRAM), or by using SDRAM
`components having different total storage and bit slice sizes.
`It will usually be unnecessary to resort
`to faster, more
`expensive types of memory, because even older generation
`DRAM components such as SDRAM are capable of deliv-
`ering and receiving data at rates that exceed the bandwidth
`of most expansion buses. Nonetheless, higher performance
`memory components including, but not limited to, Rambus
`DRAM, SyncLink DRAM or later developed memory types
`may be used to implement
`the user cache (Rambus is a
`trademark of Rambus Corporation}. Also,
`in alternate
`embodiments, memory components other than DRAM may
`be used, including, but not limited to, ferro-rnagnetic RAM
`(FRAM), electrically erasable programmable read only
`memory (EEPROM,
`including Flash EEPROM}, static
`RAM and holographic memory. Generally, any type of solid
`state memory or other memory that provides a speed advan—
`tage over electromechanical or other mass storage devices
`may be used without departing from the scope of the present
`invention.
`In one embodiment, the user cache 25 includes a power
`Source selector 6‘? that selects between a battery 65 and
`system power to power the DRAM array. In many modem
`
`computer systems. a reduced level of system power, called
`
`17
`
`

`

`
`
`US 6,463,509 B1
`
`It)
`
`15
`
`-
`
`3o
`
`35
`
`4t)
`
`45
`
`50
`
`7
`"trickle power," is available so long as the computer system
`is connected to line power. In such systems, trickle power
`can be titted to power the user cache even when the computer
`system is turned off. When system power is lost entirely, the
`power source selector detects the power loss and switches to
`the battery 65 to maintain power to the DRAM array.
`Preferably the battery 65 is recharged when system power is
`applied so that, if and when complete system power loss
`occurs,
`the battery 65 will be fully charged to provide
`auxiliary power.
`In one embodiment, the power source selector 67 distinn
`guishes between fill] system power and trickle power and
`asserts a sleep signal 81 to the DRAM controller 63 when—
`ever the user cache is being powered by trickle power or
`battery power. The DRAM controller 63 responds to the
`sleep signal 81 by issuing control signals to place the DRAM
`components of the user cache 25 in reduced power state. In
`the reduced power state, DRAM refresh operations are
`continued either under control of the DRAM controller 63 or
`by logic on board the DRAM components themselves. Other
`logic elemean within the user-cache 25, including the bus
`interface circuitry 61 and portions of the DRAM controller
`that operate on access requests from the bus interface
`circuitry are shut down to save power. Unused rows of the
`DRAM array may be shut down to save power.
`In one embodiment, the expansion bus 18 of FIG. 1 is a
`peripheral component interconnect (PCI) bus and the bus
`interface circuitry 61 of the user cache 25 is a PCI bus
`interfaCe for sending and receiv