United States Patent [19J
`Smith et al.
`
`I 1111111111111111 11111 111111111111111 1111111111 1111111111111111 Ill lllll llll
`US005829053A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,829,053
`Oct. 27, 1998
`
`[54] BLOCK STORAGE MEMORY
`MANAGEMENT SYSTEM AND METHOD
`UTILIZING INDEPENDENT PARTITION
`MANAGERS AND DEVICE DRIVERS
`
`[75]
`
`Inventors: David Lee Smith, San Francisco;
`William J. Keenan, Redwood; Steven
`James Szymanski, Cupertino, all of
`Calif.
`
`[73] Assignee: Apple Computer, Inc., Cupertino,
`Calif.
`
`[21] Appl. No.: 644,412
`
`[22] Filed:
`
`May 10, 1996
`
`Int. Cl.6
`............................. G06F 12/00; G06F 12/10
`[51]
`[52] U.S. Cl. .......................... 711/202; 711/209; 711/173;
`711/114; 395/681
`[58] Field of Search ................................ 711/5, 202, 203,
`711/209, 129, 153, 173, 114; 395/681
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,117,350
`5,129,088
`5,546,557
`
`.............................. 711/1
`5/1992 Parrish et al.
`7/1992 Auslander ................................... 711/1
`8/1996 Allen et al. .............................. 711/111
`
`OIBER PUBLICATIONS
`
`"The Raid Primer" published by the RAID Advisory Board,
`Inc., St. Peter, Minnesota, Mar. 1994.
`
`Attorney, Agent, or Firm-Burns, Doane, Swecker &
`Mathis, L.L.P.
`
`[57]
`
`ABSTRACT
`
`A memory management system and method of managing a
`memory system are disclosed. The memory management
`system includes a plurality of physical storage media and a
`memory manager for generating virtual storage devices or
`"stores," with one or more first storage devices each having
`a corresponding first mapping plug-in, or device driver,
`associated with the plurality of physical storage media. Each
`first device driver scans its corresponding first storage
`device to determine its partitioning format and generates one
`or more second virtual storage devices from a partition map
`stored in the partitioning plug-in, or partition manager,
`associated with the corresponding first storage device, each
`second virtual storage device having one or more second
`partitioning formats, a second partition manager and second
`device driver. The first and second partition managers are
`independent of the first and second device drivers. The
`separation of disk driver and partition manager functions
`allows for the nesting of partition formats and avoids the
`replication of partitioning codes. The physical storage media
`may include at least one redundant array of independent
`disks (RAID), and the first device driver may be a small
`computer systems interface (SCSI) associated with the
`physical storage device.
`
`Primary Examiner-Glenn Gossage
`
`13 Claims, 5 Drawing Sheets
`
`62
`First Partition
`(Child Store)
`
`64
`Second Partition
`(Child Store)
`
`65
`Partitioning
`Plug-in
`(Partition Manager)
`
`67
`SCSI HD
`Mapping Plug-in
`(Device Driver)
`
`68
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1006, p. 1
`
`

`

`U.S. Patent
`
`Oct. 27, 1998
`
`Sheet 1 of 5
`
`5,829,053
`
`24
`
`26
`
`28
`
`30
`
`KEYBOARD
`
`CURSOR
`CONTROL
`
`DISPLAY
`
`PRINTER
`
`34
`
`14
`
`CPU
`
`32
`
`1/0
`
`22
`
`BLOCK STORAGE
`MEMORY MANAGEMENT
`SYSTEM
`
`16
`
`18
`
`20
`
`12
`
`FIG. 1
`
`10
`
`AddressRange 1
`AddressRange2
`AddressRangeJ
`AddressRange4
`AddressRange5
`AddressRange6
`AddressRange 7
`AddressRange8
`
`90
`
`FIG. 8
`
`DeviceDriver
`
`DeviceDriver
`
`DeviceDriver
`
`Device Driver
`
`67a
`
`67b
`
`67c
`
`67d
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1006, p. 2
`
`

`

`U.S. Patent
`
`Oct. 27, 1998
`
`Sheet 2 of 5
`
`5,829,053
`
`40
`
`42
`
`44
`
`Requests
`from
`CPU
`
`File
`Manager
`
`Block
`Storage
`Memory
`System
`
`FIG. 2
`
`SCSI
`Interface
`
`Commands
`
`54
`Partitioning
`Plug-in
`
`52
`Mopping
`Plug-in
`
`50
`Store
`
`FIG. 3
`
`60
`
`62
`First
`Partition
`
`64
`
`Disk Partition
`Header
`
`FIG. 4a
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1006, p. 3
`
`

`

`U.S. Patent
`
`Oct. 27, 1998
`
`Sheet 3 of 5
`
`5,829,053
`
`62
`First Partition
`{Child Store)
`
`64
`Second Partition
`{Child Store)
`
`Mopping
`Plug-in
`
`Mopping
`Plug-in
`
`65
`Partitioning
`Plug-in
`{Partition Manager)
`
`66
`SCSI Disk
`{Parent Store)
`
`67
`SCSI HD
`Mapping Plug-in
`{Device Driver)
`
`68
`FIG. 4b
`
`First Partition
`Header
`
`60
`
`62
`First
`Partition
`
`64
`Second
`Partition
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`70
`
`Second Partition
`Header
`
`74
`72
`Audio
`First
`Segment
`Segment
`FIG. 5a
`
`76
`PhotoCD
`Segment
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1006, p. 4
`
`

`

`U.S. Patent
`
`Oct. 27, 1998
`
`Sheet 4 of 5
`
`5,829,053
`
`72
`Audio
`Segment
`
`74
`First
`Segment
`
`76
`PhotoCD
`Segment
`
`Mapping
`Plug-in
`
`Mopping
`Plug-in
`
`Mapping
`Plug-in
`
`62
`First Partition
`(Child Store)
`
`69
`Partitioning
`Plug-in
`(Partition Manager)
`
`Mapping
`Plug-in
`
`64
`Second Partition
`(Child Store)
`
`Mopping
`Plug-in
`
`65
`Partitioning
`Plug-in
`(Partition Manager)
`
`66
`SCSI Disk
`(Parent Store)
`
`67
`SCSI HD
`Mopping Plug-in
`(Device Driver)
`
`68
`FIG. 5b
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1006, p. 5
`
`

`

`~
`
`.... = Ul
`
`\0
`N
`00
`....
`Ul
`
`Ul
`0 ....,
`Ul
`~ ....
`'JJ. =-~
`
`00
`\0
`'"""'
`\0
`
`~-..J
`N
`!""'"
`I")
`0
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`68d
`
`Store 3
`Physical
`81d
`
`(Device Driver)
`Mapping Plug-in
`
`SCSI HD
`
`67d __j
`Plug-in
`
`Partitioning
`
`68c
`
`Store 2
`Physical
`81c
`
`Store
`RAID Logical
`80
`
`Plug-in
`Mapping
`
`Store
`Third
`86c
`
`Store
`Second
`86b
`
`(Partition Manager)
`
`Plug-in
`
`Partitioning
`
`84
`
`Plug-in
`Mapping
`
`860
`
`Store
`First
`
`FIG. 6
`
`(Device Driver)
`Mapping Plug-in
`
`SCSI HD
`67c
`
`Partitioning
`
`Plug-in
`
`RAID
`
`Store 1
`Physical
`
`RAID Mopping
`82
`
`(RAID Driver)
`
`Plug-in
`
`67b ~ ~68b
`
`(Device Driver)
`Mapping Plug-in
`
`SCSI HD
`
`,,.-A68a
`
`SCSI HD
`67a
`
`(Device Driver)
`Mapping Plug-in
`
`RAID~ Jr
`
`Partitioning
`
`Plug-in
`
`RAID~ Jr
`
`Partitioning
`
`Plug-in
`
`Store 0
`Physical
`81a
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1006, p. 6
`
`

`

`5,829,053
`
`1
`BLOCK STORAGE MEMORY
`MANAGEMENT SYSTEM AND METHOD
`UTILIZING INDEPENDENT PARTITION
`MANAGERS AND DEVICE DRIVERS
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to block storage
`memory systems. More particularly, the present invention
`provides for a partitioning scheme for a block storage 10
`memory system which allows the nesting of partitioning
`formats and avoids replication of partitioning codes.
`
`BACKGROUND OF THE INVENTION
`
`2
`for the software implementation of devices such as RAID
`(redundant array of independent disks) or encrypted devices.
`As will be appreciated by those skilled in the art, RAID is
`a storage technology in which an array of disks appear to a
`5 user to be equivalent to a single disk. By scattering data
`across a number of individual disks, and storing redundancy
`information separately from the data, the system can con(cid:173)
`tinue to function without loss of data if an individual disk in
`the array fails. The redundancy information can be a copy of
`the data or other information that can be used to reconstruct
`data stored on failed disk. RAID technology is described in
`more detail in "The RAID Primer" (1994) published by the
`RAID Advisory Board, Inc. St. Peter, Minn., which is
`incorporated herein by reference.
`Partition maps are simple databases of a virtual device
`that describe how the virtual device is partitioned into
`sub-devices. There are many known partition map formats,
`and often a partition map format is more closely related to
`a specific machine or operating system than a file system
`20 format; many operating systems support multiple file system
`formats but few support multiple partitioning formats. Most
`operating systems can use the information in a partition map
`to produce a number of virtual devices corresponding to the
`partitions described in the map. Most operating systems,
`25 however, allow only this two-level hierarchy of physical
`devices and virtual devices. Partition maps are typically
`implemented by a single integrated disk or device driver and
`partition manager. The partition manager includes partition
`code which enables the partition to read the partition map
`30 data and perform the necessary partitioning. The conven(cid:173)
`tional integrated device driver and partition manager
`requires significant amounts of partition code to be copied
`and stored in each partitioned storage device, reducing the
`efficiency of the memory system.
`Input/output (1/0) operations in a computer system are
`typically performed between an 1/0 device and some portion
`of the system memory. There is currently no standard way
`for a user-level application to determine a particular portion
`of the memory involved in an 1/0 operation. Memory lists
`40 are abstract lists of data created from a set of address ranges
`defining a subset of a memory range. Each item in a memory
`list represents an address or address range in the memory
`range. Memory lists are used to store and retrieve physical
`and virtual page addresses for performing 1/0 operations.
`Typically, 1/0 operations in a block storage memory system
`are performed by remapping the items in the memory list to
`generate physical addresses necessary to perform the 1/0
`operation. If the memory system includes data scattered
`across several physical devices, such as in a RAID storage
`50 system described above, the memory list must necessarily be
`copied for each physical memory device containing data
`addresses included in each memory list. It will be appreci(cid:173)
`ated that as the complexity of the block storage memory
`system increases, extensive remappings and copying of
`55 memory lists will typically be required, thereby decreasing
`the speed and efficiency of the memory system. It would be
`desirable to reduce the need for copying and remapping, and
`thereby improve the performance of the system.
`
`15
`
`The present application is related to the copending, com(cid:173)
`monly assigned application Ser. No. 08/644,317 entitled
`"Block Storage Memory List", which was filed on the same
`date as the present application and which is incorporated
`herein by reference.
`Many types of memory storage devices are known, such
`as flash random access memory (RAM) cards and multigi(cid:173)
`gabyte disk arrays, each with different interfaces. All of
`these devices share common characteristics that can be
`abstracted out into a single interface which effectively hides
`the differences between the device interfaces. Additionally,
`many different partitioning formats can be used to describe
`how each device is divided into sub-devices; the details of
`these partitioning formats can be abstracted to form a single
`interface.
`A block storage memory system provides the abstractions
`and single interface to avoid the need to compensate for
`different device interfaces and partitioning formats. This
`allows for the easy addition and qualification of new devices
`and partitioning formats.
`Specifically, a block storage memory system abstracts the
`different characteristics of real, physical, storage devices to
`provide a single, consistent interface to "virtual" storage
`devices which are abstract representations of physical stor(cid:173)
`age devices. The block storage memory system partitions
`and aggregates storage devices to create a virtual device of
`the appropriate size for an application.
`Known block storage models and interfaces are typically
`directed to disk and disk-like devices with random-access
`capabilities.
`A typical block storage system includes virtual storage
`devices, multiple auto-recognized partitioning formats and
`automated media changers.
`Virtual storage devices, or "stores", are abstract represen(cid:173)
`tations of real disk devices. They provide a relatively simple
`but powerful interface of randomly accessible fixed-sized
`"blocks" of data. The blocks of data in a store must be stored
`somewhere, either in a real device or in one or more other
`stores. Of course, the chain of virtual devices must ulti(cid:173)
`mately include a store attached to a real device or the data
`could not be stored.
`If the only option were for a virtual store to have a l-to-1
`mapping of blocks to its parent store, virtual stores would
`have limited utility. However, a store can be mapped to a 60
`portion of another store or multiple stores can be aggregated
`together and mapped into a single store. The relationship
`between stores and between a store and a physical device is
`referred to as a "mapping." The algorithm used to perform
`the mapping is changeable and is typically provided by a 65
`simple "mapping plug-in" module associated with each
`store. Using different algorithms to map the blocks allows
`
`35
`
`45
`
`SUMMARY OF THE INVENTION
`According to exemplary embodiments, data can be
`retrieved from an arrangement of virtual storage devices by
`first identifying a physical or logical storage device and a
`corresponding first mapping plug-in (device driver) associ(cid:173)
`ated with the identified storage device. The first device
`driver scans the storage device to determine its partition
`formats. A first partition manager associated with the storage
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1006, p. 7
`
`

`

`5,829,053
`
`3
`device contains a first partlt10n map describing the first
`storage device, and a first partition code to read the first
`partition map data and generate a second virtual storage
`device having a second partitioning format and second
`device driver from the first partition map. The device driver
`and partition manager for each storage device are separated
`to allow the nesting of partition formats and avoid the
`replication of partitioning codes.
`By providing for partitioning managers independent from
`the device drivers for each partitioned device in each hier(cid:173)
`archical level of a block storage memory, it is no longer
`necessary to inefficiently replicate and store irrelevant par(cid:173)
`tition code in the partitioning managers of each partitioned
`device.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`5
`
`4
`peripheral devices communicates with the CPU 14 by means
`of one or more input/output ports 32 on the computer.
`The memory disk 20 can include multiple physical stor(cid:173)
`age devices, including one or more redundant arrays of
`independent disks (RAIDs), as described previously.
`Referring now to FIG. 2, a block storage memory man(cid:173)
`agement system 34 suitable for implementing the present
`invention in the computer system of FIG. 1 is shown. The
`system includes a file manager 40 for receiving requests for
`10 1/0 operations from CPU 14, a block storage memory
`system 42 for receiving the requests from file manager 40
`and converting the requests into physical commands
`instructing data to be retrieved from a source and transmitted
`to a destination, and a Small Computer System Interface
`15 (SCSI) interface 44 for receiving the physical commands
`and supplying the commands to the desired source and
`destination. The block storage memory system 42 includes
`virtual representations of some portions, or all, of RAM 16,
`ROM 19, or disk 20.
`Referring now to FIG. 3, an exemplary store in a block
`storage memory system is shown. A store is a linearly
`addressable set of blocks of data contained in the memory of
`the computer system of FIG. 1. The size of each block in a
`set can vary between stores, but any individual store
`25 includes blocks of only one size ( or "granularity"). Stores
`can be physical stores, which map to physical storage
`locations in the computer system memory in a one-to-one
`correspondence, or logical (virtual) stores, which map
`blocks from other logical or physical stores into the address
`30 range of the logical store. The store includes a core data
`structure 50 and a mapping plug-in module 52. The store can
`also include a partitioning plug-in module 54 (partition
`manager) if it is partitioned into sub-stores.
`A "mapping" defines the blocks of data that a store will
`return when the store is asked for block x. The mapping of
`logical blocks to physical blocks in a physical store is
`defined by its associated mapping plug-in 52. When a
`mapping is made between two stores, the store which is
`40 making a block of data available is called the parent, while
`the store which translates the block address is called the
`child store. The mapping plug-in module 52 translates a
`block address between a child store and its associated parent
`store(s), or between a physical store and its associated
`45 physical device. Both types of mapping plug-ins provide the
`same interface to their associated store.
`The physical store mapping plug-in preferably functions
`as a device driver for the associated physical storage device,
`and translates block requests into operations on the physical
`50 device. The terms "mapping plug-in" and "device driver"
`are used interchangeably herein. A logical store mapping
`plug-in is typically simpler than a physical store mapping
`plug-in. The logical store plug-in preferably handles parti(cid:173)
`tions and logical store needs. Complex storage systems
`55 incorporating one or more RAID arrays, however, may
`require more complex logical store mapping plug-ins.
`Partition maps are tables which describe how blocks of
`data in a virtual storage device are organized into sub(cid:173)
`storage devices. Since block storage allows storage devices
`60 to be both subdivided and aggregated, the relationship
`between storage devices is referred to as mapping, as
`described above; the mapping information is stored in a
`partition map.
`Partitioning plug-ins maintain a store partition map and
`65 partition codes necessary to read the partition map and
`generate the partitions of the store. The partition code
`information is extracted from the store, and determines
`
`The present invention will be better understood upon
`reading the following Detailed Description of the Preferred
`Embodiments in conjunction with the accompanying
`drawings, in which like reference indicia indicate like 20
`elements, and in which:
`FIG. 1 is a block diagram of an exemplary computer
`system;
`FIG. 2 is a block diagram of a block storage memory
`management system suitable for implementing the present
`invention;
`FIG. 3 is an exemplary store in a block storage memory
`system;
`FIGS. 4a-4b show an exemplary partitioning scheme and
`corresponding hierarchical structure, respectively;
`FIGS. 5a-5b show a nesting of partitioning formats and
`corresponding hierarchy, respectively;
`FIG. 6 shows a RAID hierarchy;
`FIG. 7 is a flowchart describing a method of creating and
`using a block storage memory list according to an embodi(cid:173)
`ment of the present invention; and
`FIG. 8 is an illustration of an exemplary mapping between
`a memory list and the device drivers of FIG. 6.
`
`35
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`The present invention is directed to a memory manage(cid:173)
`ment method and system incorporating partitioned storage
`devices having separate partition managers and device driv(cid:173)
`ers. An exemplary computer system for implementing the
`present invention will now be described with respect to FIG.
`1. The computer system includes a computer 10 having a
`variety of external peripheral devices 12 connected thereto.
`The computer 10 includes a central processing unit (CPU)
`14 and associated memory. This memory generally includes
`a main memory which is typically implemented in the form
`of a random access memory (RAM) 16, a static memory that
`can comprise a read only memory (ROM) 18, and a perma(cid:173)
`nent storage device, such as a magnetic or optical disk 20.
`The CPU 14 communicates with each of these forms of
`memory through an internal bus 22. The peripheral devices
`12 include a data entry device such as a keyboard 24, and a
`pointing or cursor control device 26 such as a mouse,
`trackball, pen or the like. A display device 28, such as a
`cathode-ray tube (CRT) monitor or an liquid crystal display
`(LCD) screen, provides a visual display of the information
`that is being processed within the computer, for example the
`contents of a document or a computer-generated image. A
`hard copy of this information can be provided through a
`printer 30, or similar such device. Each of these external
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1006, p. 8
`
`

`

`5,829,053
`
`6
`5
`nested; that is, separate independent partlt10n managers
`whether and how child stores will be created from the parent
`associated with stores at different hierarchical levels can be
`store. Both logical and physical stores can have partition
`provided with individual partition codes tailored to imple(cid:173)
`plug-ins (and hence partition maps) associated with them;
`ment the partitioning necessary at each hierarchical level, as
`however, not all stores have partitioning plug-ins associated
`5 will now be described.
`with them. Mapping plug-ins scan their associated stores to
`Referring now to FIGS. 5a-5b, a nesting of partitioning
`identify the partitioning format of the store. After recogniz(cid:173)
`formats and corresponding hierarchy, respectively, are
`ing the format, the partitioning plug-in generates the next
`shown. The disk shown in FIG. Sa is a SCSI hard disk
`hierarchical layer of the block storage memory, and the
`partitioned into a first partition 62 and a second partition 64,
`partitioning process is repeated as needed. This process can
`be referred to as the recursive matching of partition man- 10 which is partitioned into audio, first and PhotoCD segments
`72, 74, and 76, respectively. If the second partition size is
`agers.
`chosen to correspond to the size of a compact disc read-only
`It will be appreciated that the present invention uses a
`memory (CDROM), a simple block copy can be used to
`distributed storage system configuration. All the information
`produce a master copy of a recordable compact disk after
`about where a specific device or piece of media fits in the
`any necessary editing is performed on the hard disk. The
`15 store hierarchy resulting from this configuration is shown in
`storage system is contained within the device. There is
`preferably no central configuration file that maps devices to
`FIG. Sb. Since the second partition 64 incorporates further
`file systems or other users of the storage. This approach
`partitions, it is provided with a second partition manager 69
`enables the block storage system to be "plug 'n play" or
`which is independent of first partition manager 65. The
`independent partition managers avoid the need to replicate
`"unplug 'n play"; in other words, substantially no user action
`20 the same partition code in each, thereby increasing the
`is required when a physical storage device is attached to or
`efficiency of the memory system. It will be appreciated that
`removed from the system.
`as the number of hierarchical layers is increased, so is the
`According to the present invention, the virtual devices
`improvement of the system.
`contain partition maps, which allows the hierarchy of virtual
`A store hierarchy for a storage system which includes one
`devices to be extended indefinitely. The process of building
`25 or more RAID devices is shown in FIG. 6. A RAID driver
`up ("instantiating") a hierarchy of stores according to the
`is implemented as a mapping plug-in 82 and is used at the
`present invention is done automatically as follows. First, a
`logical store level with a RAID logical store 80. A RAID
`device and an associated mapping plug-in (device driver) are
`partitioning plug-in 84 stores, for RAID store 80, the infor(cid:173)
`identified. Then, the device driver scans the device ( the
`mation about its associated devices. Instantiation of the
`"parent" store) for partition formats and determines if a
`30 RAID store 80 is performed according to the block storage
`partition map is associated with the device driver. The
`store instantiation method described earlier; that is, each
`partition map (if any) is used to generate "child" stores and
`store is identified and associated with a device driver,
`the process is repeated for the child stores. In this manner,
`partition formats are determined, and new devices are gen(cid:173)
`the block storage hierarchy of logical devices is generated
`erated. The RAID store 80 in this example contains first,
`by a device driver that can recognize and interact with the
`35 second, and third stores 86a, b, and c as its children. The
`device, from a minimal amount of information stored out(cid:173)
`logical RAID store 80, while appearing as a single disk to
`side the device.
`the system user, is actually comprised of, in this example,
`Exemplary store relationships will now be shown and
`four physical stores 81a, b, c, and d. The physical stores are
`described. It will be appreciated that in the following
`each associated with a physical storage device 68a-d and a
`diagrams, the child stores are drawn above the parent stores,
`40 mapping plug-in (device driver) 67a-d.
`showing the flow of control from top to bottom. Referring
`A method of creating and using a block storage memory
`now to FIGS. 4a and 4b, an exemplary partitioning scheme
`list according to an embodiment of the present invention will
`for partitioning operating systems on a SCSI (small com(cid:173)
`now be described with reference to FIG. 7. In step 100, a
`puter system interface) hard disk, and a corresponding store
`memory list range is defined using, for example, a starting
`hierarchy, respectively, are shown. The partition scheme
`45 virtual or physical address and a range length defined by a
`shows the device partitioned into a disk partition header 60,
`byte count.
`a first partition 62, and a second partition 64. The partitions
`In step 102, the memory list is initialized. Initialization is
`62 and 64 can define separate operating systems, for
`performed by first creating a memory list ( that is, allocating
`example.
`a new memory list) from an anticipated or estimated number
`The bottom-most store 66 in FIG. 4b is the parent store
`50 of ranges to be added to the memory list range defined in
`which is connected to SCSI hard disk 68. A SCSI hard disk
`step 100. During initialization, any desired address range
`mapping plug-in 67 is associated with store 66 which
`can be added to the memory list, based on the memory list
`communicates via a SCSI bus to the hard disk 68, but is
`to be added to, the starting address of the range in the
`shown as directly connected to the disk 68 for simplicity in
`address space, and the length of the range. The address
`the diagram. The two child stores 62 and 64 have standard
`55 ranges are preferably addressable from the address space
`mapping plug-ins associated with them, but have no parti(cid:173)
`specified by the memory list. Finally, the memory list is
`tioning plug-ins, since these stores contain no partition
`finalized by closing the memory list and creating an initial
`maps.
`descriptor describing the memory list. The memory list
`includes one or more address ranges, as shown in FIG. 8, and
`Conventionally, partition maps are implemented using a
`60 the initial descriptor is typically a simple descriptor describ(cid:173)
`disk driver as the partition manager, thus requiring a copy of
`ing a starting or other position in the memory list and some
`the partition code to be stored in the disk driver at each
`length value to describe one or more positions in the
`hierarchical layer. According to an aspect of the present
`memory list. Once finalized, no further address ranges can
`invention, the partition manager (partitioning plug in) 65
`be added to the memory list. When all descriptors are
`and disk driver (mapping plug-in) 67 are separated, as
`65 deleted, the initial memory list will be deleted.
`shown in FIG. 4b. The separation of the partition manager
`In step 104, one or more additional descriptors can be
`and disk driver, and the recursive matching of partition
`managers, as described above, allow partition formats to be
`created or deleted. The one or more additional descriptors
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1006, p. 9
`
`

`

`5,829,053
`
`10
`
`7
`can be created from a base descriptor defining a base
`memory list (which can be a descriptor created in step 102),
`an offset defined as a beginning of an additional descriptor's
`memory list within the base descriptor's memory list, and a
`length of the area described by the additional descriptors. 5
`This step adds a descriptor to an existing memory list based
`upon a previously defined descriptor for the memory list,
`effectively creating a subset of the existing memory list. The
`additional descriptors can be simple descriptors or complex
`descriptors, as will be described in more detail below.
`A previously-created descriptor can be deleted, in which
`case resources specifically tied to the descriptor are deallo(cid:173)
`cated. Memory which has been made noncacheable
`("locked") is returned to its original state, unless other
`descriptors in the same memory list require the memory to 15
`remain locked. If the descriptor is the last descriptor for a
`memory list, all resources for the memory list are deallo(cid:173)
`cated.
`A complex "stride" descriptor can be created in step 104,
`which is particularly useful for RAID storage systems. The
`complex descriptor creates a memory list, composed of
`every nth block having a block size specified by a granu(cid:173)
`larity value, from the base descriptor. Preferably, the
`memory list described by the complex descriptor is com(cid:173)
`puted on demand (that is, when a physical address is 25
`necessary) and requires no memory allocation when it is
`calculated or used. The complex descriptor can be created
`from, for example, a base descriptor, an offset value defining
`the beginning of the complex descriptor's memory list with
`the base descriptor's memory list, a length value specifying 30
`the length of the complex descriptor's memory list, the
`granularity value, and a stride value indicating the number
`of blocks to skip. The complex descriptor thus defines an
`algorithmic mapping between a second memory list and a
`first memory list. The algorithm enables the second memory 35
`list to be generated as follows: starting at block ( or item) x
`in the first memory list described by the first descriptor,
`collect every nth block of a block size specified by the
`granularity value. This calculation of the second memory list
`is performed by the device driver associated with a physical 40
`store. Thus, the calculation is performed only when a
`physical address is necessary to retrieve data for transmis(cid:173)
`sion to a destination or to receive data transmitted from a
`source. This type of descriptor is particularly useful for
`RAID storage systems, or other storage systems where data 45
`is scattered throughout a memory system, such as in FIG. 6.
`According to the present invention, the algorithm contained
`in the complex descriptor is preferably not implemented to
`recover data from the second memory list until the data is
`necessary to perform an 1/0 operation. This is ensured by 50
`storing the complex descriptor in a physical store device
`driver, thereby avoiding the need to copy and store memory
`lists in each device driver at each hierarchical level, includ(cid:173)
`ing in each of the multiple devices replaced by a RAID array.
`In the RAID array, a complex descriptor is preferably 55
`generated and stored in each device driver of each physical
`store.
`In step 106, descriptor operations are performed. First, a
`memory list specified by a descriptor is prepared for 1/0 in
`a similar manner to preparing a memory for an 1/0 opera- 60
`tion. A new descriptor and a mapped length are generated
`from an identification of the descriptor to be mapped, a
`granularity measure, a requested map length, and additional
`information defining how the memory is to be prepared (i.e.,
`the specific operation to be performed, etc.). Caches are 65
`flushed appropriately, physical and logical addresses are
`translated as needed and pages may be invalidated from the
`
`8
`cache. As described above, calculation of physical addresses
`is preferably performed only at the physical store level by
`the physical device drivers, thereby delaying the calcula-
`tions until a physical address is necessary to perform the
`desired 1/0 operation. The reading or writing necessary for
`the 1/0 operation can be performed with the memory
`described by the descriptor, and when the operation is
`finished and the memory mappings no longer required, the
`descriptor is preferably deleted to free memory mappings
`and state.
`A