Methods and structure for recursive scatter/gather lists

Details Methods and structure for recursive scatter/gather lists Methods and structure for recursive scatter/gather lists

2001-07-30

2004-01-13

Gaffin, Jeffrey (Department: 2182)

Electrical computers and digital data processing systems: input/

Input/output data processing

Direct memory accessing

C710S022000, C710S003000

Reexamination Certificate

active

06678754

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computing coprocessor architectures and more specifically relates to methods and structures for generating scatter/gather lists recursively.
2. Discussion of Related Art
It is common in computing and electronic applications for a processor device to manipulate large blocks of memory for particular application purposes. For example, direct memory access controllers (“DMAC”) are often used in conjunction with general-purpose processors (“CPU”) to handle movement of large blocks of data with minimal overhead processing by the general-purpose CPU. The DMAC is programmed by the CPU to indicate the block of memory to be manipulated including, for example, a source location, destination location, and count of the number of units of memory to be moved. The DMA controller then performs the requested block memory move operation without further intervention by the CPU. This generally frees the CPU computational power for processing of other operations for the particular application. When the DMA controller completes the block memory operation, it notifies the CPU o,f the completion and the CPU then continues processing as necessary following completion of the block memory operation.
It is also common for intelligent I/O processor (“IOP”) devices to include similar block memory manipulation structures. For example, a SCSI bus controller or Fibre Channel controller may include programmable capabilities such that it directly manipulates blocks of memory to transfer information between the SCSI bus (or Fibre Channel medium) and the system memory of a host computer. Similar to the purpose of a DMAC, IOP serve to offload the general-purpose CPU from the lower-level responsibilities of manipulating individual units of memory in the block memory operations. Rather, the DMAC or IOP is programmed to perform the particular block operation and interrupt or otherwise notify the general-purpose CPU when the block operation is completed.
It is common in the present day DMACs and IOPs to include a capability for processing multiple block memory operations under the programmable direction of an associated general-purpose CPU. Specifically, the general-purpose CPU may supply information to the DMAC or IOP to signify a plurality of memory blocks to be used in a plurality of block transfer operations. Frequently, a list of memory blocks to be manipulated is supplied to the DMAC or IOP by the general-purpose CPU. The list is often referred to as a scatter/gather list (“SGL”). The list may, for example, identify a plurality of blocks of memory to be “written” to one or more destination locations or may specify the “reading” of noncontiguous source locations of memory for transfer to one or more destination locations (i.e., the “scattering” or “gathering” of memory blocks).
The scatter/gather list may be specified utilizing any of a variety of well-known computing data structures to define a list of such elements for processing within the DMAC or IOP.
Software elements within a host computing system generate scatter/gather lists to provide to intelligent coprocessors for processing needed block transfer operations. For example, device driver software elements with an operating system frequently construct scatter/gather lists to provide to intelligent co-processors such as DMA controllers and/or I/O processors.
Because such construction of scatter/gather lists is a common function within device drivers, it is imperative that the function be as efficient as possible to maintain high performance levels in the computing system.
Presently practiced techniques utilize well-known looping software constructs to generate the scatter/gather list elements. Each iteration of the looping construct allocates memory for one or more scatter/gather elements to be added to the list. Various mathematical computations and comparisons are performed in each iteration of the looping construct. Such looping constructs generate certain complexities that affect computational performance of the method within, for example, a device driver. Further, if one iteration of the construction looping fails to properly allocate the scatter/gather element it is processing, memory previously allocated for earlier scatter/gather elements may need to be released. This need presents further complexities in the design of, for example, device drivers.
It is evident from the above discussion that a need exists for an improved method and structure for efficiently generating scatter/gather lists for intelligent co-processors.
SUMMARY OF THE INVENTION
The present invention solves the above and other problems, thereby advancing the state of the useful arts, by providing methods and associated structure for recursive generation of scatter/gather lists. The recursive methods of the present invention reduce computational complexity of scatter/gather list generation and simplify the allocation and release of memory allocated for the scatter/gather list in case of error in the generation process.
A first aspect of the invention provides for a method for generating scatter/gather lists comprising the steps of: providing a list segment for storing scatter/gather entries wherein the list segment has an associated size; providing a vector of descriptors used to generate scatter/gather entries; providing a number of remaining entries in the vector of descriptors; generating a number of scatter/gather entries into the list segment wherein the maximum number is determined in accordance with the size of the list segment; determining whether additional entries of the number of remaining entries need to be generated; returning successful completion status to the invoking function in response to a determination that no additional entries need be generated; performing steps to follow in response to a determination that a number of the additional entries need be generated; allocating a new list segment having a new associated size; adjusting the number of remaining entries and the vector of descriptors in accordance with the number of scatter/gather entries generated; and recursively invoking the above steps using the new list segment and using the new associated size and using the number of remaining entries as adjusted and using the vector of descriptors as adjusted.
A further aspect provides that the step of allocating includes the steps of: determining that the allocating of the new list segment failed; and returning a failure status to the invoking function in response to the determination that the allocating failed, and further provides that the step of recursively invoking includes the steps of: determining that the recursive invocation returned a failure status; deallocating the previously allocated the new list segment; and returning a failure status to the invoking function in response to the determination that the allocating failed.
Still a further aspect provides that the step of allocating includes the step of: linking the list segment to the new list segment.


REFERENCES:
patent: 5251303 (1993-10-01), Fogg, Jr. et al.
patent: 5497476 (1996-03-01), Oldfield et al.
patent: 5708849 (1998-01-01), Coke et al.
patent: 5948060 (1999-09-01), Gregg et al.
“Looping Scatter/Gather Bus Master to Coprocessor Data Transfer Mechanism”, Sep. 1, 1990, IBM Technical Disclosure Bulletin, TDB-ACC-NO: NN9009382.*
“Linked List Basics” by Nick Parlante, http://cslibrary.stanford.edu/103/, ©1998-2001.

Affiliated with

Also associated with

Rating

Methods and structure for recursive scatter/gather lists does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and structure for recursive scatter/gather lists, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and structure for recursive scatter/gather lists will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3267615