Background memory manager that determines if data structures fits in memory with memory state transactions map

• US 7,502,876 B1
• Filed: 06/23/2000
• Issued: 03/10/2009
• Est. Priority Date: 06/23/2000
• Status: Expired due to Term

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Nemirovsky, Mario, Nemirovsky, Adolfo, Sankar, Narendra, Musoll, Enric
• Primary Examiner(s): PEYTON, TAMMARA R
• Application Number:
  US09/602,279
• Time in Patent Office: 3,182 Days
• Field of Search: 710/3, 710/4, 710/22, 710/23, 710/56, 709/104, 709/108, 711/100, 711/102, 711/171, 711/170, 718106-108
• US Class Current: 710/22
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence

Abstract

A background memory manager (BMM) for managing a memory in a data processing system has circuitry for transferring data to and from an outside device and to and from a memory, a memory state map associated with the memory, and a communication link to a processor. The BMM manages the memory, determining if each data structure fits into the memory, deciding exactly where to place the data structure in memory, performing all data transfers between the outside device and the memory, and maintaining the memory state map according to memory transactions made, and informing the processor of new data and its location. In preferred embodiments the BMM, in the process of storing data structures into the memory, provides an identifier for each structure to the processor. The system is particularly applicable to Internet packet processing in packet routers.

Claims

1. A background memory manager (BMM) for managing a memory in a data processing system, the BMM comprising:

circuitry for transfer a data structure to and from an outside device and to and from a memory; and

a communication link;

management logic coupled to a processor by the communication link and configured to determine if the data structure fits into the memory, to decide where, in a plurality of regions in the memory, to store the data structure, to perform data transfers between the outside device and the memory, to maintain a memory state map according to memory transactions made, and to inform the processor of new data and its location.

2. The BMM of claim 1, wherein the management logic is further configured to provide, for the data structure and when the data structure is stored, a data identifier on the communication link.

3. The BMM of claim 2, wherein the management logic is further configured to update, in response to the memory transactions, the memory state map to a new memory state to keep track of regions occupied by valid data and regions unoccupied by valid data.

4. The BMM of claim 2, wherein the management logic is further configured to copy, in response to a signal on the communication link that the processor is finished with identified data in the memory, the identified data from the memory to another device and to update the memory state map to indicate a new memory state for a region of the identified data data.

5. The BMM of claim 1, further comprising an interrupt handler configured to allow a remote data source to interrupt the BMM when data is available to be transferred to the memory.

6. The BMM of claim 1, wherein data handled by the BMM constitutes network data packets.

7. A data processing system, comprising:

a processor;

a memory coupled to the processor; and

a background memory manager (BMM) coupled to the memory and the processor, the BMM including circuitry to transfer a data structure to and from an outside device and to and from the memory and including management logic configured to determine if the data structure fits into the memory, to decide where, in a plurality of regions in the memory, to store the data structure, to perform data transfers between the outside device and the memory, to maintain a memory state map according to memory transactions made, and to inform the processor of new data and its location.

8. The data processing system of claim 7, wherein the management logic is further configured to provide, for the data structure and when the data structure is stored, a data identifier to the processor.

9. The data processing system of claim 8, wherein the management logic is further configured to update, in response to the memory transactions, the memory state map to a new memory state to keep track of regions occupied by valid data and regions unoccupied by valid data.

10. The data processing system of claim 8 wherein the management logic is further configured to copy, in response to a signal from the processor that the processor is finished with identified data in the memory, the identified data from the memory to another device and to update the memory state map to indicate a new memory state for a region of the identified data data.

11. The data processing system of claim 7, further comprising an interrupt handler configured to allow a remote data source to interrupt the BMM when data is available to be transferred to the memory.

12. The data processing system of claim 7, wherein data handled by the BMM constitutes network data packets.

13. A network packet router, comprising:

an input/output (I/O) device configured to receive and to send a packet on the network;

a processor;

a memory coupled to the processor; and

a background memory manager (BMM) coupled to the memory and the processor, the BMM including circuitry configured to transfer the packet to and from the I/O device and to and from the memory and including management logic configured to determine if the packet fits into the memory, to decide where, in a plurality of regions in the memory, to store the packet, to perform data transfers between the I/O device and the memory, to maintain a memory state map according to memory transactions made, and to inform the processor of new data and its location.

14. The data router of claim 13 wherein the management logic is further configured to provide, for the packet and when the packet is stored, a data identifier to the processor.

15. The data router of claim 14, wherein the management logic is further configured to update, in response to the memory transactions, the memory state map to a new memory state to keep track of regions occupied by valid packets and regions unoccupied by valid packets.

16. The data router of claim 14, wherein the management logic is further configured to copy, in response to a signal that the processor is finished with a first packet in the memory, the first packet from the memory to the I/O device and to update the memory state map to indicate a new memory state for a region of the first packet packet.

17. The data router of claim 13, further comprising an interrupt handler configured to allow the I/O device to interrupt the BMM when packets are available to be transferred to the memory.

18. The data router of claim 13, wherein the BMM is further characterized by being configured to notify the processor when enough of the packet is stored for the processor to being to perform desired processing.

19. A method for managing a memory in a data processing system having a processor, the method comprising:

(a) transferring a data structure to and from an outside device and to and from the memory by circuitry in a background memory manager (BMM);

(b) determining by the BMM if the data structure from the outside device will fit into available space in the memory;

(c) deciding by the BMM exactly where, in a plurality of regions in the memory, to store the data structure; and

(d) updating a memory state map in the BMM when a memory transaction is made.

20. The method of claim 19, further comprising providing, for the data structure and when the data structure is stored, a data identifier on a link to the processor.

21. The method of claim 20, further comprising keeping track of regions occupied by valid data and regions unoccupied by valid data.

22. The method of claim 20, further comprising:

copying, in response to a signal that the processor is finished with identified data in the memory, the identified data from the memory to another device; and

updating the memory state map to indicate a new memory state for a region of the identified data.

23. The method of claim 19, further comprising interrupting the BMM by the outside device when data is available to be transferred to the memory.

24. The method of claim 19, wherein data handled by the BMM constitutes network data packets.

25. The method of claim 24, wherein the network data packets are conveyed on the Internet.