Memory controller with on-chip linked list memory

Patent metadata

Field	Value
Publication number	US-9436403-B1
Application number	US-201313856011-A
Country	US
Kind code	B1
Filing date	Apr 3, 2013
Priority date	Apr 3, 2012
Publication date	Sep 6, 2016
Grant date	Sep 6, 2016

Abstract

Systems, methods, and other embodiments associated with improving communication latencies by using a hardware linked list are described. According to one embodiment, an apparatus includes a pointer memory configured to store a free list that includes a plurality of pointers that each point to an address in a memory that is unallocated. The apparatus includes a memory controller configured to manage a linked list using pointers from the plurality of pointers stored in the free list. The apparatus includes a list memory configured to store the linked list.

First claim

What is claimed is:

1. An apparatus, comprising:
a pointer memory configured to store a free list that includes a plurality of pointers that each point to an address in a memory that is unallocated;
a memory controller configured to manage a linked list using pointers from the plurality of pointers stored in the free list, wherein pointers of the linked list are assigned from the plurality of pointers and reference data of a single network packet stored in the memory, and wherein the memory controller manages a separate linked list for each network packet of a plurality of network packets,
wherein the memory controller is configured to, in response to a memory access request for a portion of the single network packet, traverse the linked list using the pointers of the linked list to access the portion that is referenced by at least one of the pointers of the linked list and modify the portion according to the memory access request;
a list memory configured to store the linked list; and
a descriptor memory configured to store a descriptor of the linked list in a queue that is an on-chip memory of the apparatus, wherein the descriptor includes a head pointer that references a first entry of the linked list, a tail pointer that references a final entry of the linked list and a pointer count that indicates a number of pointers in the linked list for the network packet, and wherein the descriptor memory includes descriptors for network packets that are ingressing and network packets that are egressing the apparatus.

2. The apparatus of claim 1 , wherein the memory controller is configured to manage the linked list by assembling the linked list in response to receiving a plurality of separate portions of the single network packet, wherein the plurality of separate portions are stored in separate memory locations of the memory, and wherein the pointers of the linked list are assigned to the plurality of separate portions from the free list to maintain an order of the plurality of separate portions of the network packet.

3. The apparatus of claim 1 , wherein the linked list is a list of successive pointers that point to locations in the memory where successive portions of the single network packet are stored, wherein the list memory is an on-chip memory of the apparatus.

4. The apparatus of claim 1 , wherein the memory controller is configured to assemble and traverse the linked list independently of a central processing unit (CPU).

5. The apparatus of claim 1 , wherein the memory controller is configured to control storing the plurality of network packets that are ingressing and egressing the apparatus to and from a network.

6. A method, comprising:
receiving, in a memory controller, data to be stored in a memory;
managing, in the memory controller, a linked list using pointers retrieved from a free list, wherein the free list is implemented as part of the memory controller and contains a plurality of pointers that each point to locations in the memory that are unallocated,
wherein managing the linked list includes assembling the linked list from pointers of the free list in response to receiving the data that is to be stored in the memory, wherein the data is a network packet, and wherein pointers of the linked list indicate addresses of where the network packet is to be stored in the memory; and
storing, in a list memory that is an on-chip memory of the memory controller, the linked list,
wherein storing the linked list includes storing a descriptor of the linked list in a queue that is implemented in an on-chip memory of the memory controller, wherein the descriptor includes a head pointer that references a first entry of the linked list, a tail pointer that references a final entry of the linked list and a pointer count that indicates a number of pointers in the linked list for the network packet, and wherein storing the descriptor includes storing a descriptor for network packets that ingressing and for network packets that are egressing,
wherein receiving the network packet includes receiving the network packet in a network interface card that includes the memory controller;
in response to a memory access request for a portion of the data referenced by a pointer in the linked list, traversing, by the memory controller, the linked list using the pointers to access the portion that is referenced by at least one of the pointers and modify the portion of data according to the memory access request.

7. The method of claim 6 , wherein managing the linked list includes managing a separate linked list for each of a plurality of network packets.

8. The method of claim 7 , wherein storing the linked list in the on-chip memory permits accessing the data independently of a central processing unit (CPU) by traversing, in the memory controller, the linked list to locate a pointer in the linked list that points to data associated with the memory access request without using the CPU.

9. The method of claim 6 , wherein the linked list is a list of pointers that point to locations in the memory where successive portions of the data are stored once allocated, wherein managing the linked list includes assembling the linked list with a series of pointer entries that each reference a next pointer entry in the linked list.

10. The method of claim 6 , wherein managing the linked list includes assembling, in the memory controller, the linked list using pointers from the free list by iteratively assigning pointers from the free list to successive portions of the data and linking the pointers by referencing a next pointer in the linked list using a current pointer.

11. The method of claim 6 , wherein managing the linked list includes assembling the linked list using the pointers to cause addresses in the memory referenced by the pointers to be allocated to store the data.

12. The method of claim 6 , further comprising communicating with a network interface card that is configured to communicate with a cloud computing system.

13. The method of claim 6 , wherein storing the linked list includes storing a plurality of linked lists for network packets that are ingressing and egressing the memory controller to and from a network.

14. A device, comprising:
an ingress memory controller configured to assemble an ingress linked list of pointers for each network packet received from a network, wherein the ingress linked list of pointers includes pointers that are assigned to point to locations in a memory where successive portions of each network packet are to be stored once allocated;
an egress memory controller configured to assemble an egress linked list of pointers for each network packet egressing the device to the network, wherein the egress linked list of pointers includes pointers that are assigned to point to locations in the memory where successive portions of each network packet are to be stored once allocated;
a linked list memory connected to the egress memory controller and the ingress memory controller, wherein the egress memory controller and the ingress memory controller are configured to store the ingress linked list and the egress linked list respectively in the linked list memory, wherein the linked list memory is an on-chip memory of the device;
a pointer memory connected to the ingress controller and the egress controller, wherein the egress memory controller and the ingress memory controller are configured to store a free list of pointers in the pointer memory, wherein the free list of pointers includes pointers to addresses in the memory that are unallocated, wherein the ingress memory controller and egress memory controller are configured to use poi

Assignees

• Marvell Int Ltd

Inventors

• Zhang David

Classifications

• H04L67/568 Primary

  Storing data temporarily at an intermediate stage, e.g. caching · CPC title

• G06F3/0631 Primary

  by allocating resources to storage systems · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F12/023

  Free address space management · CPC title