DATA STRUCTURE AND ASSOCIATED MANAGEMENT ROUTINES FOR TCP CONTROL BLOCK (TCB) TABLE IN NETWORK STACKS

• US 20160044143A1
• Filed: 08/11/2014
• Published: 02/11/2016
• Est. Priority Date: 08/11/2014
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Narasimhamurthy, Giridhar
• Granted Patent: US 9,667,754 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

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.

Claims

1. A method for transport layer lookup, comprising:

receiving, by the 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,

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

searching the plurality of global transport layer data structures in main memory to obtain the matching second transport layer data structure, and storing a pointer to a memory address of the matching second transport layer data structure in the pointer cache, when a pointer cache miss occurs for the state information corresponding to the second incoming packet.

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 3, wherein a size of each of the plurality of pointer cache lines is a function of a CPU cache line size and a TCB pointer size.

5. 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.

6. The method of claim 1, wherein each of the plurality of pointer cache lines comprises a plurality of array elements, each of which stores a memory address for a recently accessed transport layer data structure.

7. The method of claim 6, wherein each of the plurality of pointer cache lines are aligned with a boundary of a CPU cache line, and wherein the method further comprises:

prefetching array elements of the pointer cache into a CPU cache.

8. 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.

9. 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.

10. A host, comprising:

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,

wherein the transport layer is further configured to;

search the pointer cache for a matching first transport layer data structure comprising state information corresponding to the first incoming packet;

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

searching the plurality of global transport layer data structures in the main memory to obtain the matching second transport layer data structure, and store a pointer to a memory address of the matching second transport layer data structure in the pointer cache, when a pointer cache miss occurs for the state information corresponding to the second incoming packet.

11. The host of claim 10, wherein each of the plurality of pointer cache lines comprises a plurality of array elements, each of which stores a memory address for a recently accessed transport layer data structure.

12. The host of claim 11, wherein the host further comprises:

a CPU and an associated CPU cache,

wherein a boundary of each pointer cache line is aligned with a boundary of the associated CPU cache to facilitate prefetching of adjacent pointer cache array elements by the CPU.

13. The host of claim 10, 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.

14. The host of claim 10, 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.

15. The host of claim 14, wherein a size of each of the plurality of pointer cache lines is a function of a CPU cache line size and a TCB pointer size.

16. The host of claim 14, 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.

17. A non-transitory computer readable medium comprising software instructions that when executed, perform a method for transport layer lookup, comprising:

receiving, by the 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,

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

searching the plurality of global transport layer data structures in main memory to obtain the matching second transport layer data structure, and storing a pointer to the memory address of the matching second transport layer data structure in the pointer cache, when a pointer cache miss occurs for the state information corresponding to the second incoming packet.