Method and apparatus for multiple channel direct memory access control

• US 5,875,352 A
• Filed: 11/03/1995
• Issued: 02/23/1999
• Est. Priority Date: 11/03/1995
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Gentry, Denton E., Oskouy, Rasoul M.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US08/553,041
• Time in Patent Office: 1,208 Days
• Field of Search: 395/463, 395/487, 395/842, 395/444, 395/843, 395/845, 395/846, 395/851, 395/858
• US Class Current: 710/23
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 13/10 Program control for peripheral devices G06F13/14 - G06F13/42 take precedence
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence

Abstract

An on-chip cache memory is used to provide a high speed access mechanism to frequently used channel state information for operation of a DMA device that supports multiple virtual channels in a high speed network interface. When an access to a particular channel state is performed, e.g., by a host processor or the DMA device, the cache is first accessed and if the state information is not located currently in the cache, external memory is read and the state information is written to the cache. As the cache does not store all the states stored in external memory, replacement algorithms are utilize to determine which channel state information to remove from the cache in order to provide room to store a recently accessed channel. A doubly linked list is used to track the most recently used channel. As cached channel information is accessed, the corresponding entry is moved to the top of the list. The doubly linked list provides a rapid apparatus and method for updating pointers to the cache. Top and bottom pointers are maintained, pointing to the most recently used and least recently used channels. When a channel is used, it moved to the top of the list. When channel data is moved from external memory to the cache, the bottom pointer points to the channel data to be removed from the cache.

Claims

1. A network switch interface comprising:

interface circuitry for coupling data among at least one host computer and at least one of a plurality of channels of a network;

a memory coupled to the interface circuitry for storing a plurality of channel information for the plurality of channels, each channel information utilized to transfer data among the plurality of channels using at least one network switch;

a cache coupled to the interface circuitry comprising cache entries of recently used channel information;

a MRU list of the cache comprising a plurality of list entries, each list entry corresponding to a cache entry in the MRU cache;

a direct memory access (DMA) controller coupled to the interface circuitry for transferring the received data among the plurality of channels in accordance with corresponding channel information, said DMA controller accessing the cache to retrieve the corresponding channel information for the corresponding channel, if the corresponding channel information is not stored in the cache, said DMA controller accessing external memory to retrieve the corresponding channel information and store the corresponding channel information in the cache, said DMA controller further updating the MRU list to identify a current cache entry containing the corresponding channel information as most recently used.

2. The network switch interface as set forth in claim 1, wherein said DMA controller updates the MRU to identify the current cache entry as most recently used by modifying the MRU list to reflect that the current cache entry is at the top of the MRU list by updating previous pointer of a prior list entry corresponding to a prior most recently used cache entry to point to a current list entry associated with the current cache entry, updating the previous pointer of a list entry following the current list entry to point to a list entry pointed to by a previous pointer of the current list entry, updating a next pointer of a list entry prior to the current list entry to point to a list entry pointed to by a next pointer of the current list entry, and updating the previous and next pointer of the current list entry to respectively be a value indicative that the corresponding cache entry is the most recently used entry and a pointer to the prior list entry.

3. The network switch interface as set forth in claim 1, wherein said previous pointer for a most recently used list entry has a value indicative that the corresponding cache entry is the most recently used cache entry.

4. The network switch interface as set forth in claim 1, wherein said next pointer for a least recently used cache entry has a value indicative that the cache entry is the least recently used cache entry.

5. The network switch interface as set forth in claim 1, wherein said MRU list further comprises a MRU_-- first pointer which points to the most recently used entry.

6. The network switch interface as set forth in claim 1, wherein said MRU list further comprises a MRU_-- last pointer which points to the least recently used entry.

7. The network switch interface as set forth in claim 1, wherein the MRU list further comprises a MRU_-- last pointer which points to the least recently used entry, the current cache entry is the least recently used entry, and said DMA controller updates the MRU to identify the current cache entry as most recently used by modifying the MRU list to reflect that the current cache entry is at the top of the MRU list by updating previous pointer of a prior list entry corresponding to a prior most recently used cache entry to point to a current list entry associated with the current cache entry, updating the MRU_-- last pointer to point to a list entry prior to the current list entry, updating a next pointer of the list entry prior to the current list entry to point to a list entry pointed to by a next pointer of the current list entry, and updating the previous and next pointer of the current list entry to respectively be a value indicative that the corresponding cache entry is the most recently used entry and a pointer to the prior list entry.

8. The DMA system of claim 1, wherein each list entry in the MRU list comprises:

a cache pointer which points to a corresponding cache entry in the cache;

a previous pointer which points to a previous list entry corresponding to a cache entry accessed previous to the cache entry corresponding to the list entry; and

a next pointer which points to a list entry corresponding to a cache entry accessed next after the corresponding cache entry.

9. The network switch interface of claim 1, wherein the network switch interface is coupled to an Asynchronous Transfer Mode (ATM) switch.

10. The network switch interface of claim 1, wherein the network switch interface is coupled through a local ATM switch to a public ATM switch to enable asynchronous transfer of data between host computer systems coupled to a network.

11. The network switch interface of claim 1, wherein at least one transmit and at least one receive channel are serviced as virtual connections of the network switch interface.

12. The network switch interface of claim 1, wherein the memory comprises a buffer memory, wherein the buffer memory comprises packet data for a plurality of transmit and receive channels of the network switch interface.

13. The network switch interface of claim 1, further comprising a storage memory, wherein the storage memory comprises DMA state information for the plurality of transmit and receive channels, wherein the storage memory comprises at least one pointer for data structures in a host memory for which DMA transfers are performed, wherein the storage memory comprises a data structure to manage at least one transmit and receive buffer for packets in transition between a host and the network switch interface.

14. A method for multiple channel direct memory access (DMA) control of a network switch interface, the method comprising the steps of:

receiving data from at least one of a plurality of channels of a network;

storing a plurality of channel information for the plurality of channels,

wherein the channel information is used to transfer data among the plurality of channels of at least one network switch;

transferring the received data among the plurality of channels in accordance with corresponding channel information using a DMA controller, said DMA controller accessing a cache to retrieve the corresponding channel information for the corresponding channel, if the corresponding channel information is not stored in the cache, said DMA controller accessing an external memory to retrieve the corresponding channel information and store the corresponding channel information in the cache, said DMA controller further updating an MRU list to identify a current cache entry containing the corresponding channel information as most recently used.

15. The method of claim 14, further comprising the step of rapidly updating identification of a most recently used (MRU) cache entry, the step of rapidly updating comprising the steps of:

generating a MRU list comprising a plurality of list entries corresponding to a plurality of cache entries of recently used channel information for the plurality of network channels coupled to the at least one network switch, each entry comprising;

a cache pointer which points to a corresponding cache entry in the cache,

a previous pointer which points to a previous list entry corresponding to a cache entry accessed previous to the cache entry corresponding to the list entry,

a next pointer which points to a list entry corresponding to a cache entry accessed next after the corresponding cache entry;

if data from a current cache entry is accessed, updating the MRU list such the corresponding current list entry identifies the current cache entry as most recently accessed.

16. The method as set forth in claim 15, wherein said previous pointer for a most recently used list entry having a value indicative that the corresponding cache entry is the most recently used cache entry.

17. The method as set forth in claims 15, wherein said next pointer for a least recently used entry has a value indicative that the least recently used entry is the least recently used entry.

18. The method as set forth in claim 15, wherein said step of updating comprising the steps of:

updating previous pointer of a prior list entry corresponding to a prior most recently used cache entry to point to a current list entry associated with the current cache entry,

updating the previous pointer of a list entry following a current list entry to point to a list entry pointed to by a previous pointer of the current list entry,

updating a next pointer of a list entry prior to current list entry to point to a list entry pointed to by a next pointer of current list entry, and

updating the previous and next pointer of the current list entry to respectively be a value indicative that the current cache entry is the most recently used entry and the prior list entry.

19. The method as set forth in claim 15, wherein said MRU list further includes a MRU_-- first pointer which points to the most recently used entry and MRU_-- last pointer which points to the least recently used entry and wherein the current list entry is the least recently used entry, said method for updating comprises the steps of:

updating previous pointer of a prior list entry corresponding to a prior most recently used cache entry to point to a current list entry associated with the current cache entry,

updating the MU^-- last pointer to point to a list entry pointed to by a previous pointer of the current list entry,

updating a next pointer of a list entry prior to current list entry to point to a list entry pointed to by a next pointer of current list entry, and

updating the previous and next pointer of the current list entry to respectively be a value indicative that the current cache entry is the most recently used entry and the prior list entry.

20. The method as set forth in claim 15, wherein the cache comprises cache entries of recently used channel information, said method further comprising the step of transferring data from a network to a host memory comprising the steps of:

storing in external memory a plurality of channel information for a plurality of channels, each channel information utilized to transfer data received at the host memory;

receiving data from a channel on the network;

accessing the cache to retrieve the corresponding channel information for the corresponding channel;

if the corresponding channel information is not stored in the cache, accessing external memory to retrieve the corresponding channel information and store the corresponding channel information in the cache; and

transferring the received data to host memory in accordance with corresponding channel information.