Electrical computers and digital data processing systems: input/ – Input/output data processing – Direct memory accessing
Reexamination Certificate
2001-10-25
2004-02-03
Huynh, Kim (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Direct memory accessing
Reexamination Certificate
active
06687767
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer systems; more particularly, to methods and apparatus for transferring data and check information between computer main memory and data storage devices by means of direct memory access.
BACKGROUND OF THE INVENTION
Computer direct access data storage devices are typically organized into fixed-size blocks of data storage. For example, a computer disk drive may organize data storage into a number of blocks of data, each block holding 512 bytes of data, and each block having a unique logical block address, with the blocks being sequentially numbered starting with block zero. Other block addressing methods are also in use, including specifying cylinders, tracks, and sectors; but again, each block has a unique address, and the blocks are considered to appear on the device in a well-defined logical order. Other storage media such as tapes may also be organized into fixed-size blocks, depending on the application.
A substantial portion of the work carried out by a computer system is the storage and retrieval of data to and from data storage devices (I/O). In early computer systems this work was carried out by the central processing unit (CPU), requiring the use of a substantial portion of the CPU's available computing capacity to perform the detailed steps of the I/O. However, in modern systems the mechanics of data transfer to and from storage devices is often carried out by a separate direct memory access (DMA) controller.
FIG. 1A
shows a simplified block diagram of such a system, shown at
101
. System
101
has a CPU
103
, main memory
105
, DMA controller
107
, storage medium
109
, and communication bus
111
. In systems like
101
, to initiate the I/O data transfer, CPU
103
programs DMA controller
107
with the information it requires, and issues a command (via communication bus
111
) to begin the transfer. The CPU can then attend to other computations while the DMA controller carries out the detailed steps of the transfer. Thus, DMA controller
107
serves as an intermediary between main memory
105
and storage medium
109
. When the I/O operation is complete, CPU
103
is informed of the I/O completion by DMA controller
107
, whereupon the CPU may make use of the results of the transfer. In this way, most of the work required to carry out the I/O is offloaded from the CPU, thus freeing the CPU to carry out other work. For example, the CPU may perform processes such as interchange with main memory
105
.
To program a DMA device, a CPU typically specifies such information as: a start address in main memory to be used for the data transfer, the length of the data to be transferred, whether data should be transferred from the device to main memory (“read”) or from main memory to the device (“write”), and for direct access devices, the address of the block of data on the storage device.
Often it is desired to transfer more than one block of data to or from a storage device in a single I/O operation. In most cases the length of such transfers are constrained to be integral multiples of the storage device's block size.
FIG. 1B
depicts a scenario
113
, wherein data is transferred from main memory
105
to a storage medium
109
, via DMA controller
107
. If a CPU specifies to DMA controller
107
a length of more than one block of data, the I/O operation transfers data from sequential addresses in main memory, beginning at the specified start address, to sequential blocks in storage medium
109
. The data is stored beginning at a specified block address, or in some devices, at an implicit current location on the storage medium. The DMA controller typically has registers for main memory start address, data block length, and optionally a storage address associated with a storage medium. Thus, in this example, a chunk of data 4096 bytes (8-512 byte blocks, designated D
0
-D
7
) in length is transferred to storage medium
109
in one operation (stored in 8-512 byte blocks, designated B
0
-B
7
). By transferring multiple blocks of data in a single I/O operation, the CPU is relieved of the effort of initiating the DMA I/O operation for each of blocks D
0
-D
7
individually.
Often it is necessary or desirable to transfer multiple blocks of data between non-contiguous locations in main memory to a contiguous set of blocks on the data storage device. If the DMA controller only accepts a single main memory start address for any given I/O operation, then only sequentially addressable locations in main memory can be transferred in a single I/O operation. In cases where the granularity constraints of the device are met by the organization of the data in main memory, it may be possible to issue separate I/O commands for each contiguous chunk of memory. However, this would incur the CPU cost of initiating the additional I/O commands, and handling their completion.
To alleviate this problem, some DMA controllers implement what has been called a “scatter/gather” I/O operation. In such operations, instead of being programmed with a single main memory start address and length, the DMA controller is given a list of start addresses and lengths. Data is first transferred beginning with the main memory address specified in the first scatter/gather list element. When this element is exhausted; that is, when the specified length of data for the element has been transferred, the next element of the list is used to determine the next set of main memory addresses to be used in the transfer. In this way, a single I/O operation can transfer multiple blocks of data between the data storage device and non-contiguous locations in main memory. However, conventional DMA controllers commonly allow for only a small, limited number of scatter/gather list elements or do not implement scatter/gather capability at all.
In computing environments requiring high reliability data storage and retrieval, it may be necessary or desirable to keep check information for each block of stored data, which can be used to validate that the data has not become corrupted during storage. Although there are many types of check information, one common form is called a checksum. A checksum is the result of a mathematical calculation on a block of data, which produces the same result each time it is calculated. If a checksum is calculated on a block of data that is about to be stored, the checksum is typically stored along with the data. When the data is retrieved, the checksum is recalculated on the retrieved data and compared with the stored checksum. If the newly computed checksum differs from the stored checksum, then the data is known to be corrupt, and remedial measures can be initiated.
In many cases, it is advantageous for data integrity check information computations to be carried out at a very low level in the operating system. For example, these computations may be performed in a device driver, without knowledge of the software entities originally requesting the I/O. The entity requesting the I/O may simply request, for example, that 64 blocks of memory be written to the storage medium starting at a particular block address. The check information is computed and checked by the device driver, and does not appear in the data passed between the requesting entity and the device driver.
Considerable care must be taken in storing data and its associated check information in such a way that they remain consistent on the storage device in the event of a system failure. Significant simplification of this process can be achieved if the check information for a block of data is stored on the device in the same I/O operation that writes that data. One way to do this is to format the storage device so that each block of storage on the device is long enough to hold both the desired data block size, and the desired check information size. For example, if the desired data block size is 512 bytes, and the desired check information size is 8 bytes, then the storage device could be formatted into 520-byte blocks, each of which would hold 512 bytes of data and 8 bytes of chec
Beyer Weaver & Thomas LLP
Huynh Kim
Kim Harold
Sun Microsystems Inc.
LandOfFree
Efficient direct memory access transfer of data and check... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient direct memory access transfer of data and check..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient direct memory access transfer of data and check... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3338485