Data structure and associated management routines for TCP control block (TCB) table in network stacks

Patent metadata

Field	Value
Publication number	US-9667754-B2
Application number	US-201414456924-A
Country	US
Kind code	B2
Filing date	Aug 11, 2014
Priority date	Aug 11, 2014
Publication date	May 30, 2017
Grant date	May 30, 2017

Abstract

A method for transport layer lookup involves receiving a first incoming transport layer packet, and searching a pointer cache for a first matching transport layer data structure including state information corresponding to the first incoming packet. The pointer cache includes pointer cache lines, each of which stores at least one pointer to a subset of global transport layer data structures. The method further involves returning the state information corresponding to the first incoming packet using the first matching transport layer data structure when a pointer cache hit occurs, receiving a second incoming transport layer packet, searching the pointer cache for a second matching transport layer data structure including state information corresponding to the second incoming packet, and searching the plurality of global transport layer data structures in main memory to obtain the matching second transport layer data structure, when a pointer cache miss occurs.

First claim

What is claimed is:

1. A method for transport layer lookup, comprising:
receiving, by a transport layer of a network protocol stack, a first incoming transport layer packet;
searching a pointer cache for a first matching transport layer data structure comprising state information corresponding to the first incoming packet, wherein the pointer cache comprises:
a plurality of pointer cache lines, each of which is configured to store at least one pointer to a subset of a plurality of global transport layer data structures in main memory, and a pointer cache line size, wherein each of the plurality of pointer cache lines comprises a plurality of array elements, each of which stores a pointer to a memory address for a recently accessed transport layer data structure, wherein each of the plurality of pointer cache lines is aligned with a boundary of a central processing unit (CPU) cache line of a plurality of CPU cache lines of a CPU cache, wherein the pointer cache line size is a function of a size of the CPU cache line and a transport control protocol control block (TCB) pointer size;
prefetching a plurality of array elements of a pointer cache line of the plurality of pointer cache lines into the CPU cache line, wherein the plurality of array elements comprises a pointer to the first matching transport layer data structure;
returning the state information corresponding to the first incoming packet using the first matching transport layer data structure when a pointer cache hit occurs for the state information corresponding to the first incoming packet; receiving, by the transport layer of a network protocol stack, a second incoming transport layer packet;
searching the pointer cache for a second matching transport layer data structure comprising state information corresponding to the second incoming packet;
and in response to a pointer cache miss when searching for the second matching transport layer data structure:
searching the plurality of global transport layer data structures in main memory to obtain the second matching transport layer data structure, and storing a pointer to a memory address of the second matching transport layer data structure in the pointer cache.

2. The method of claim 1 , wherein when the pointer cache hit occurs for the state information corresponding to the first incoming packet, only the subset of TCBs referenced by the pointer cache is searched.

3. The method of claim 1 , wherein the transport layer data structure is a TCP control block (TCB) implemented as one selected from a group consisting of a hash table, a binary tree, a Red-Black tree, an AVL tree, and a linked list.

4. The method of claim 1 , wherein each pointer cache line of the pointer cache stores a pointer to a memory address of the subset of plurality of global transport layer data structures.

5. The method of claim 2 , further comprising: populating the pointer cache by storing a memory address of a recently accessed TCB in an array element of one of the plurality of pointer cache lines.

6. The method of claim 1 , further comprising: evicting at least one pointer cache array element of the plurality of array elements of at least one pointer cache line when the pointer cache is full and a pointer cache miss occurs.

7. A host, comprising:
a central processing unit (CPU) and an associated CPU cache, wherein the associated CPU cache comprises a plurality of CPU cache lines; a network protocol stack comprising a transport layer configured to receive a first incoming packet and a second incoming packet; and main memory configured to store:
a plurality of global transport layer data structures, wherein the plurality of global transport layer data structures is configured to store state information for a plurality of incoming packets, and
a pointer cache comprising a plurality of pointer cache lines, each of which is configured to store at least one pointer to a subset of the plurality of global transport layer data structures, and a pointer cache line size, wherein each of the plurality of pointer cache lines comprises a plurality of array elements, each of which stores a pointer to a memory address for a recently accessed transport layer data structure,
wherein each of the plurality of pointer cache lines is aligned with a boundary of a central processing unit (CPU) cache line of the plurality of CPU cache lines, wherein the pointer cache line size is a function of a size of the CPU cache line and a transport control protocol control block (TCB) pointer size, wherein the transport layer is further configured to:
search the pointer cache for a first matching transport layer data structure comprising state information corresponding to the first incoming packet;
prefetch a plurality of array elements of a pointer cache line of the plurality of pointer cache lines into the CPU cache line, wherein the plurality of array elements comprises a pointer to the first matching transport layer data structure;
return the state information corresponding to the first incoming packet using the first matching transport layer data structure when a pointer cache hit occurs for the state information corresponding to the first incoming packet;
search the pointer cache for a second matching transport layer data structure comprising state information corresponding to the second incoming packet; and
in response to a pointer cache miss when searching for the second matching transport layer data structure:
search the plurality of global transport layer data structures in the main memory to obtain the second matching transport layer data structure, and store a pointer to a memory address of the second matching transport layer data structure in the pointer cache.

8. The host of claim 7 , wherein when the pointer cache hit occurs for the state information corresponding to the first incoming packet, only the subset of TCBs referenced by the pointer cache is searched.

9. The host of claim 7 , wherein the transport layer data structure is a TCP control block (TCB) implemented as one selected from a group consisting of a hash table, a binary tree, a Red-Black tree, an AVL tree, and a linked list.

10. A non-transitory computer readable medium comprising software instructions that when executed, perform a method for transport layer lookup, comprising:
receiving, by a transport layer of a network protocol stack, a first incoming transport layer packet;
searching a pointer cache for a first matching transport layer data structure comprising state information corresponding to the first incoming packet, wherein the pointer cache comprises:
a plurality of pointer cache lines, each of which is configured to store at least one pointer to a memory address of a subset of a plurality of global transport layer data structures in main memory, and a pointer cache line size, wherein each of the plurality of pointer cache lines comprises a plurality of array elements, each of which stores a pointer to a memory address for a recently accessed transport layer data structure, wherein each of the plurality of pointer cache lines is aligned with a boundary of a central processing unit (CPU) cache line of a plurality of CPU cache lines of a CPU cache, wherein the pointer cache line size is a function of a size of the CPU cache line and a transport control protocol control block (TCB) pointer size;
prefetching a plurality of array elements of a pointer cache line of the plurality of pointer cache lines into the CPU cache line, wherein the plurality of array elements comprises a pointer to the first matching transport layer data structure; returning the state information corresponding to the first incoming packet using the first matching transport layer data structure when a poi

Assignees

• Oracle Int Corp

Inventors

• Narasimhamurthy Giridhar

Classifications

• H04L69/16 Primary

  Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP] · CPC title