User scheduled direct memory access using virtual addresses

Claims

What is claimed is:

1. An interface device for transferring data associated with data processing commands directly between a user's host system having a main memory and an external data processing system in response to user commands without direct host operating system management during individual memory transfer transactions, comprising:

means for representing said data processing commands and associated data as command/pointer packets comprising said data processing commands and virtual pointers to said associated data in virtual memory space of the user's host system;

means on said interface device, coupled to said virtual memory space, for directly translating said virtual pointers of said command/pointer packets to physical pointers which identify physical addresses within said main memory at which said associated data is located; and

means on said interface device for transferring said associated data from and to said main memory at said physical addresses.

2. A device as in claim 1, wherein said external data processing system comprises a communications network.

3. A device as in claim 1, wherein said external data processing system comprises a graphics subsystem of said user's host system.

4. A device as in claim 3, wherein said data processing commands comprise graphics commands and said associated data comprises graphics primitives.

5. A device as in claim 4, wherein said representing means comprises a user applications program operating on said user's host system.

6. A device as in claim 5, wherein said translating means comprises a DMA processor having access to at least one shadow page table updated by a processor driven operating system of the user's host system, said at least one shadow page table containing physical pointers corresponding to said virtual pointers.

7. A device as in claim 6, wherein said DMA processor has a user privileged shadow page table for each user controlled process of said host system.

8. A device as in claim 7, wherein said DMA processor includes a translation lookaside buffer for storing virtual to physical translations found during recent accesses by the DMA processor to said shadow page table.

9. A device as in claim 8, further comprising additional data storage means for storing data, said DMA processor interrupting said processor driven operating system of the user's host system, when said translating means receives an indication that a required translation is not located in the shadow page table, so that said processor driven operating system can operate a fault algorithm for locating and swapping said associated data between said additional data storage means and said main memory, so that the processor driven operating system can then create the required translation and place said required translation into the shadow page table.

10. A device as in claim 7, wherein translations in said shadow page table are created and updated by said processor driven operating system in response to indications from said DMA processor that translations required to access associated data in main memory are not present in the shadow page table in said main memory.

11. A device as in claim 10, further comprising synchronizing means for synchronizing reads and writes of said shadow page table and user's virtual memory space in main memory by said user's host system to reads and writes of said shadow page table and user's virtual memory space in main memory by said transferring means so that data consistency in main memory is maintained.

12. A device as in claim 7, wherein said translating means further comprises a command/pointer packet buffer for sequentially storing said command/pointer packets for parsing by said DMA processor.

13. A device as in claim 7, wherein said transferring means comprises DMA state means responsive to said DMA processor for initiating a read or a write of said associated data from or to said main memory.

14. A device as in claim 13, wherein said DMA state means comprises a register written by said DMA processor to indicate a starting data buffer address for said associated data in said main memory.

15. A device as in claim 14, wherein said starting data buffer address represents a work buffer in said main memory in which said command/pointer packets are stored.

16. A device as in claim 7, wherein said transferring means comprises a bidirectional bus buffer and an input/output bus for connecting said translating means to said user's host system and said main memory.

17. An interface device for transferring graphics primitives associated with graphics commands directly between a user's host system having a main memory and a graphics subsystem in response to user commands without direct host operating system management during individual memory transfer transactions, comprising:

means for representing said graphics commands and graphics primitives as command/pointer packets comprising said graphics commands and virtual pointers to said graphics primitives in virtual memory space of the user's host system;

means on said interface device, coupled to said virtual memory space, for directly translating said virtual pointers to physical pointers which identify physical addresses within said main memory at which said graphics primitives are located; and

means on said interface device for transferring said graphics primitives from and to said main memory at said physical addresses.

18. A device as in claim 17, wherein said representing means comprises a user applications program operating on said user's host system and said translating means comprises a DMA processor having access to at least one shadow page table updated by a processor driven operating system of the user's host system, said at least one shadow page table containing physical pointers corresponding to said virtual pointers.

19. A device as in claim 18, wherein said DMA processor has a user privileged shadow page table for each user controlled process of said host system.

20. A device as in claim 19, wherein said DMA processor includes a translation lookaside buffer for storing translations found during recent accesses by the DMA processor to said shadow page table.

21. A device as in claim 20, further comprising additional data storage means for storing data, said DMA processor interrupting said processor driven operating system, when said translating means receives an indication that a required translation is not in said shadow page table, so that said processor driven operating system can operate a fault algorithm for locating and swapping said graphics primitives between said additional data storage means and said memory, so that the processor driven operating system can then create the required translation and place said required translation into the shadow page table.

22. A device as in claim 19, wherein translations between virtual pointers to physical pointers of associated graphics primitives in said shadow page table are created and updated by said processor driven operating system in response to indications from said DMA processor that translations required to access associated graphics primitives in main memory are not in said shadow page table.

23. A device as in claim 22, further comprising synchronizing means for synchronizing reads and writes of said shadow page table and user's virtual memory space in main memory by said user's host system to reads and writes of said shadow page table and user's virtual memory space in main memory by said transferring means so that data consistency in main memory is maintained.

24. A device as in claim 19, wherein said translating means further comprises a command/pointer packet buffer for sequentially storing said command/pointer packets for parsing by said DMA processor.

25. A device as in claim 19, wherein said transferring means comprises DMA state means responsive to said DMA processor for initiating a read or a write of said graphics primitives from or to said main memory.

26. A device as in claim 25, wherein said DMA state means comprises a register written by said DMA processor to indicate a starting data buffer address for said graphics primitives in said main memory.

27. A device as in claim 26, wherein said starting data buffer address represents a work buffer in said main memory in which said command/pointer packets are stored.

28. A device as in claim 19, wherein said transferring means comprises a bidirectional bus buffer and an input/output bus for connecting said translating means to said user's host system and said main memory.

29. An interface device for transferring graphics primitives associated with graphics commands directly between a user's host system having a main memory and a graphics subsystem in response to user commands without direct host operating system management during individual memory transfer transactions, comprising:

means for representing said graphics commands and graphics primitives as command/pointer packets comprising said graphics commands and virtual pointers to said graphics primitives in virtual memory space of the user's host system;

means on said interface device for translating said virtual pointers to physical pointers which identify physical addresses within said main memory at which said graphics primitives are located, said translating means comprising a DMA processor having access to a user privileged shadow page table for each user controlled process of said host system, each shadow page table being created and updated by a processor driven operating system of said user's host system in response to an indication that translations required to access graphics primitives are not in said shadow page table so as to contain current translations of physical pointers corresponding to said virtual pointers, and a command/pointer packet buffer for sequentially storing said command/pointer packets for parsing by said DMA processor;

DMA state means responsive to said DMA processor for transferring said graphics primitives from and to said main memory at said physical addresses; and

synchronizing means for synchronizing reads and writes of said shadow page tables and user's virtual memory space in main memory by said user's host system to reads and writes of said shadow page tables and user's virtual memory space in main memory by said DMA state means so that data consistency in main memory is maintained.

30. A method for providing direct memory access by an external data processing system to data stored in a main memory of a user's host system in response to a plurality of user's data processing commands without direct host operating system management during individual memory transfer transactions, comprising the steps of:

representing each of said user's data processing commands and associated data as a command/pointer packet including a virtual pointer to said associated data in virtual memory space of said user in said user's host system;

directly translating by an interface device said virtual pointer to a physical pointer which identifies a physical address within said main memory at which said associated data is located; and

accessing said main memory by said interface device at the physical address identified by said physical pointer in order to transfer data to and from said main memory.

31. A method as in claim 30, wherein said external data processing system comprises a graphics subsystem of said user's host system, each of said user's data processing commands is a graphics command and said associated data comprises graphics primitives.

32. A method as in claim 31, wherein said translating step by said interface device includes the steps of:

performing table lookup in a translation lookaside buffer to find a translation of said virtual pointer to a physical pointer which identifies a corresponding physical address in main memory of the data associated with each of said user's data processing commands;

when said translation lookaside buffer does not contain said translation, searching a shadow page table in said main memory for said translation;

if said translation is found in said shadow page table, adding the virtual pointer to physical pointer translation to said translation lookaside buffer;

writing said corresponding physical address to an address register of a DMA state device; and

repeating said table lookup step to find a next translation.

33. A method as in claim 32, comprising the further steps of suspending said translating step and transmitting an interrupt to said user's host system when at least one of a memory and a protection fault is encountered during said translating step.

34. A method as in claim 30, wherein said translating step includes the step of checking a shadow page table for a translation of said virtual pointer into said physical pointer.

35. A method as in claim 34, comprising the further step of updating said shadow page table by adding a required translation when at least one of a memory and protection fault is encountered during said translating step.

36. A method as in claim 35, comprising the further step of synchronizing reads and writes of said shadow page tables and user's virtual memory space in main memory by said user's host system to reads and writes of said shadow page table and user's virtual memory space in main memory by said reading and writing step so that data consistency in main memory is maintained.

37. A method for providing direct memory access by an external data processing system having an interface device with a DMA processor to data stored in a main memory of a user's host system in response to a user's data processing command without direct host operating system management during individual memory transfer transactions, comprising the steps of:

preapproving all direct memory accesses by said external data processing system requested by said user in said user's data processing command by writing a shadow page table root address in the DMA processor;

assembling a plurality of command/pointer packets for each user process, each of said command pointer packets comprising a user's data processing command and a virtual pointer in virtual memory space of the user's host system to data in said main memory for use in processing of said user's data processing commands;

storing each of said command/pointer packets in a buffer on said interface device for sequentially storing said command/pointer packets for parsing by said DMA processor;

parsing each command/pointer packet by said DMA processor to obtain said user's data processing command and said virtual pointer;

writing said user's data processing command to an input of said external data processing system;

translating said virtual pointer into a corresponding physical pointer which identifies a physical address in said main memory at which said data is located, said translating performed by said DMA processor on said interface device by accessing translation information stored in said shadow page table, indicated by said shadow table root address;

determining a word count identifying the word length of said data; and

transferring to an input of said external data processing system a number words of said data corresponding to said word count, said data transfer starting at an address in said main memory identified by said physical pointer, said data transfer controlled by a DMA state device responsive to said DMA processor, said DMA state device and said DMA processor located on said interface device.

38. A method as in claim 37, comprising the further step of flushing a cache memory of said main memory before said data transferring step is attempted in order to maintain data consistency.

39. A method as in claim 37, wherein said translating step includes the steps of:

performing table lookup in a translation lookaside buffer to find a translation of said virtual pointer to a physical pointer which identifies a corresponding physical address in main memory of the data associated with each of said user's data processing commands;

when said translation lookaside buffer does not contain said translation, searching a shadow page table in said main memory for said translation;

if said translation is found in said shadow page table, adding the virtual pointer to physical pointer translation to said translation lookaside buffer;

writing said corresponding physical address to an address register of a DMA state device; and

repeating said table lookup step to find a next translation.

40. A method as in claim 37, comprising the further steps of suspending said translating step and transmitting an interrupt to said user's host system when at least one of a memory and a protection fault is encountered during said translating step.

41. A method as in claim 37, wherein said translating step includes the step of checking a shadow page table for a translation of said virtual pointer into said physical pointer.

42. A method as in claim 41, comprising the further step of synchronizing reads and writes of said shadow page table and user's virtual memory space in main memory by said user's host system to reads and writes of said shadow page table and user's virtual memory space in main memory by said transferring means so that data consistency in main memory is maintained.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a method and apparatus for providing direct access by an external data processing system to data stored in the main memory of a host system, and more particularly, to an interface method and apparatus for providing direct memory access by an external data processing system, such as a graphics subsystem, to virtual memory of the host system by transferring the contents of main memory of the host system at a location in virtual memory space specified by the user to the external data processing system under the user's control.

2. Description of the Prior Art

Generally, data transfer between the processor of a host system and an external data processing device is performed via an input/output (I/O) attachment under direct control of a program being run by the host processor. Typically, each byte or word of data requires the execution of several instructions to transfer. However, some I/O devices require higher data transfer rates than are achievable with this technique. For such devices, the I/O attachment may use a data transfer process known as direct memory access (DMA). DMA allows the direct transfer of data between the host processor memory and the I/O attachment without the necessity of executing instructions in the host processor. In particular, during DMA the host processor first initializes the DMA controller circuitry by storing a count and a starting memory address in its registers. Once started, DMA proceeds without further host processor intervention (except that an interrupt may be generated upon completion of the DMA operation), and hence data transmission is handled without the need to execute further instructions in the host processor.

I/O attachments using such a DMA technique are known and generally incorporate circuitry of the type shown in FIG. 1. The host processor of the DMA controller of FIG. 1 sets the address counter and counter registers 10 and 12. The signal Bus Cycle is assumed to define the interval of time during which the addresses are presented and data are exchanged on the bus. The DMA controller also connects to the I/O attachment with the lines Transmit Request and Request Granted. During operation, when the I/O attachment wishes to use a bus cycle, it raises the voltage on the line Transmit Request. If the DMA count register 12 is nonzero, the signal is placed on the Bus Request line to the host processor. The host processor hardware periodically examines this signal, and when it is of a high logic level the host processor waits until the end of the current bus cycle, stops any further bus activity, places its address and data line drivers in the high-impedance state, and raises the voltage of the line Bus Grant. The host processor is thus effectively isolated from the bus during bus cycles granted to the DMA controller. When a high logic level of Bus Grant is sensed by the DMA controller, it places the contents of its address counter register 10 on the Address lines and signals the I/O attachment on Request Granted that it may use the current bus cycle for transmission of data. The I/O attachment itself may thus drive the bus lines that determine the direction of data transfer, or additional circuitry in the DMA controller may drive these lines. As long as Transmit Request is held at a high logic level, consecutive bus cycles may be used by the I/O attachment. Such a technique is known as "cycle stealing".

The circuitry of prior art FIG. 1 is capable of using successive bus cycles ("burst mode") or using bus cycles intermittently. The choice depends on the data transfer rate of the I/O attachment. In fact, the processor of the host system often must use several bus cycles in preparation for relinquishing the bus by generating Bus Grant, and must use several bus cycles after regaining the bus. These cycles are unproductive in that they do not contribute to instruction execution or data transfer. Therefore, DMA transfers that use consecutive bus cycles make more efficient use of the bus.

Thus, in order to reduce the load on the host processor when transferring data to an external data processing system, it is known to use DMA to fetch data from the main memory of the host system and to pass it to the external data processing system without requiring additional processor instructions. However, such prior art DMA techniques have been typically initiated by the kernel software in the host processor to guarantee the integrity of multi-user memory space and have not been initiated by the user's code operating on the host system. As a result, when a user applications program of the host system calls for processing of large blocks of data as in conventional graphics processing or networking systems, user scheduled DMA has not been possible. Rather, access to the main memory of the host system has been typically provided only through system software (or kernel) control in the host processor, thereby significantly slowing the overall data transfer time of the system and complicating user programming. Hence, it has heretofore been extremely difficult to perform real-time manipulations of graphics and other such complex data profiles under user direction via a DMA interface.

Accordingly, there is a long-felt need in the art for a process and apparatus which enables an external process to access data in the main memory of a host system under user control whereby the time required for data transfer to the external process or data processing system can be substantially reduced so as to allow real-time data manipulation without losing system security. The present invention has been designed for this purpose.

SUMMARY OF THE INVENTION

The above-mentioned long-felt need has been met in accordance with the present invention, which relates to an intelligent direct memory access (DMA) controller which interprets commands from a host system in virtual memory space, translates virtual addresses to physical addresses, and retrieves blocks of data from the main system memory at the user's request, rather than at the request of the kernel software. This allows for rapid data access to be accomplished at the user's request, not the kernel's, while maintaining access security in a multi-user system.

In accordance with the invention, an interface device is provided for transferring data processing commands and associated data between a user's host system having a main memory and an external data processing system. The interface device in accordance with the invention comprises means for representing the data processing commands and associated data as respective command/pointer packets comprised of data processing commands and virtual pointers to the associated data in virtual memory space of the user's host system. The virtual pointers of the command/pointer packets are then translated by translating means to physical pointers for purposes of identifying physical addresses within the main memory at which the associated data is located so that the associated data may then be read from or written to the physical address in the main memory by reading and writing means. Such a direct memory access system is preferably used in conjunction with a graphics subsystem connected to the user's host system, whereby the data processing commands are graphics commands and the associated data comprises graphics primitive data. However, the external data processing system may be a communications network or some other such system in which direct memory access is desirable.

In a preferred embodiment, the functions of the representing means may be performed by the host processor, while the functions of the translating means may be performed by a DMA processor having at least one shadow page table which is updated by the host processor to contain current physical pointers corresponding to the virtual pointers of the command/pointer packet. Preferably, a shadow page table is provided for each user controlled process of the host system, each shadow page table being privileged to the user. Missing pages in the shadow page tables may be updated by interrupting the host processor so that its kernel software can swap in the missing page from an external memory. Also, in a preferred embodiment the interface device of the invention includes synchronizing means for synchronizing the processing of the host system to DMA read and write accesses of the main memory. Moreover, data consistency techniques are preferably implemented by the host system to prevent attempted data accesses before the main memory has been updated after the previous access.

In accordance with another aspect of the invention, an interface device is provided for transferring graphics commands and graphics primitives between a user's host system having a main memory and a graphics subsystem. This interface device preferably utilizes a command/pointer protocol by using means for representing the graphics commands and graphics primitives as respective command/pointer packets comprising the graphics commands and virtual pointers to the graphics primitive data in virtual memory space of the user's host system. In conjunction with this command/pointer protocol, means are provided for translating the virtual pointers to physical pointers which identify physical addresses within the main memory at which the graphics primitives are located. Preferably, the translating means comprises a DMA processor having a shadow page table for each user controlled process of the user's host system, and each shadow page table is updated by a processor driven operating system of the user's host system, in response to an indication that the graphics primitives are not in the main memory, so as to contain current physical pointers corresponding to the virtual pointers. The translating means further comprises a command/pointer packet buffer for sequentially storing the command/pointer packets for parsing by the DRA processor and DMA state means responsive to the DMA processor for initiating a read or a write of the graphics primitives from main memory at the physical addresses. Synchronizing means may also be provided for synchronizing the user's host system to reads and writes initiated by the DMA state means.

The invention also comprises a method for providing direct memory access by an external data processing system to data stored in a main memory of a user's host system in response to a user's data processing command. This method generally comprises the steps of:

preapproving all direct memory accesses by the external data processing system requested by the user in the user's data processing command;

assembling a series of command/pointer packets for each user process, the command/pointer packets comprising the user's data processing command and a virtual pointer in virtual memory space of the user's host system to data in the main memory for use in processing of the user's data processing command;

parsing each command/pointer packet to obtain the user's data processing command and the virtual pointer;

writing the user's data processing command to an input of the external data processing system;

translating the virtual pointer into a corresponding physical pointer to an actual memory location in the main memory; determining a word count identifying the length of the data; and

transferring to an input of the external data processing system a number of words of the data corresponding to the word count, the data transfer starting at an address in the main memory identified by the physical pointer.

The method of the invention may also include the step of synchronizing the processing by the user's host system to the data transferring step to prevent attempted DMA to "dirty" memory. Data consistency problems are also prevented by flushing all display list elements as well as the user's data cache to main memory before the data transfer is attempted. Also, all shadow page table entries to the main memory may be flushed both before and after the virtual to physical pointer translation, where the translation includes the steps of:

performing table lookup in a translation lookaside buffer to find the physical address of the data associated with each user's data processing commands;

when the translation lookaside buffer does not contain the physical address, searching a shadow page table;

if the physical address is found in the shadow page table, adding a corresponding virtual to physical translation to the translation lookaside buffer;

writing the physical address to an address register of a DMA state device; and

repeating the table lookup step.

However, should a page or protection fault be encountered during the translating step, the translating step is suspended and an interrupt is transmitted to the user's host system so that a page swap or some other remedial operation may be performed. Moreover, this processing is performed by the host processor without the necessity of a task swap, thereby significantly increasing the response time of the system of the invention. Thus, the characteristics of a virtual memory system are maintained in accordance with the invention, while the processing efficiency of user scheduled DMA without kernel control also is made possible.

BRIEF DESCRIPTION OF THE DRAWINGS

The objects and advantages of the invention will become more apparent and more readily appreciated from the following detailed description of the presently preferred exemplary embodiments of the invention taken in conjunction with the accompanying drawings of which:

FIG. 1 schematically illustrates a prior art direct memory access (DMA) controller.

FIG. 2 schematically represents a conceptual block diagram of a host system and graphics processing system connected by a host interface embodying the present invention.

FIG. 3 schematically illustrates a user-scheduled direct memory access system for interfacing a host system to a graphics subsystem in accordance with the invention.

DETAILED DESCRIPTION OF THE PRESENTLY PREFERRED EMBODIMENTS

The inventors of the subject matter disclosed and claimed herein have satisfied the above-mentioned long-felt needs in the art by developing a host interface process and apparatus which allows an external data processing system, such as a graphics subsystem, to access data directly from main memory of the host system under user control without requiring the kernel to initiate and control each memory access.

In accordance with the invention, data may be transferred directly to and from the external data processing system from the main memory of the host system in response to the user's commands in virtual memory space, thereby reducing the bandwidth requirements of the interface. As a result, the host processor no longer must spend valuable computation time performing routine data copies. Also, since the host's user level software can initiate direct access to memory using virtual addresses, subrouting calls to kernel services are not required. Moreover, the above is accomplished in accordance with the invention without losing the benefits of conventional page swapping and virtual memory functions and protections.

An interface device with these and other beneficial features in accordance with presently preferred embodiments of the invention will be described with reference to FIGS. 2 and 3. As shown, the invention is described generally in conjunction with a host processing system and a graphics subsystem of the host system; however, it will be appreciated by those of ordinary skill in the art that the invention may be used in other environments as well. Moreover, the description given herein is for exemplary purposes only and is not intended in any way to limit the scope of the invention. All questions regarding the scope of the invention may be resolved by referring to the appended claims.

FIG. 2 shows a host processing system interfaced with a graphics subsystem by a host interface incorporating the invention. As shown, the processing system comprises a host processor 20 which is interfaced via system I/O bus 21 and VDMA host interface 22 to a graphics transform engine 24. The output of the transform engine 24 is input to graphics rendering circuitry 26 and then to a frame buffer 28. The output of the frame buffer 28 is then received by raster display 30 and output to a CRT screen, for example. As will be described in detail below, the present invention is particularly directed to the host interface circuitry 22 of FIG. 2 and the direct memory access (DMA) process performed by host interface circuitry 22 for allowing data to be transferred directly between the main memory of the host processor 20 and the graphics subsystem including transform engine 24, rendering circuitry 26, frame buffer 28 and raster display 30 without the immediate intervention of the software program (or kernel) of host processor 20.

For the DMA of the invention to be responsive to user input to the host processor 20, the user input must either be in a low level language (such as Assembly language) which directly references actual memory addresses, or as is usually the case, the user input must be converted from addresses in user memory space (hereinafter referre