Hashing algorithm for network receive filtering
First Claim
1. A method for use by a host computer system in dynamically reconfiguring a filter table in a network interface device, the filter table having a plurality of filter entries, the method comprising:
- receiving a request to close a specified network socket;
identifying in the network interface device filter table a particular filter entry in a particular chain of filter entries, the particular filter entry containing data that corresponds to the specified socket;
responsive to a determination that removing from the filter table data from a first set of filter entries including the particular filter entry would not reduce a maximum chain length of filter entries in the filter table, the module replacing the data in the particular filter entry in the filter table with a tombstone marker; and
responsive to a determination that removing from the filter table data from a second set of filter entries including the particular filter entry would reduce the maximum chain length of filter entries in the filter table, performing a garbage collection of tombstoned filter entries;
wherein the chain length of the particular chain of filter entries is the number of entries between a first filter entry of the particular chain and the last filter entry that contains data corresponding to an open socket, inclusive.
7 Assignments
0 Petitions
Accused Products
Abstract
Roughly described, a network interface device is assigned a maximum extent-of-search. A hash function is applied to the header information of each incoming packet, to generate a hash code for the packet. The hash code designates a particular subset of the table within which the particular header information should be found, and an iterative search is made within that subset. If the search locates a matching entry before the search limit is exceeded, then the incoming data packet is delivered to the receive queue identified in the matching entry. But if the search reaches the search limit before a matching entry is located, then device delivers the packet to a default queue, such as a kernel queue, in the host computer system. The kernel is then responsible for delivering the packet to the correct endpoint.
-
Citations
30 Claims
-
1. A method for use by a host computer system in dynamically reconfiguring a filter table in a network interface device, the filter table having a plurality of filter entries, the method comprising:
-
receiving a request to close a specified network socket; identifying in the network interface device filter table a particular filter entry in a particular chain of filter entries, the particular filter entry containing data that corresponds to the specified socket; responsive to a determination that removing from the filter table data from a first set of filter entries including the particular filter entry would not reduce a maximum chain length of filter entries in the filter table, the module replacing the data in the particular filter entry in the filter table with a tombstone marker; and responsive to a determination that removing from the filter table data from a second set of filter entries including the particular filter entry would reduce the maximum chain length of filter entries in the filter table, performing a garbage collection of tombstoned filter entries; wherein the chain length of the particular chain of filter entries is the number of entries between a first filter entry of the particular chain and the last filter entry that contains data corresponding to an open socket, inclusive. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A network interface device for processing data packets received from a network, for use with a computing device, comprising:
-
a memory having stored therein in a non-transitory manner a filter table having a plurality of filter entries for filtering incoming data packets for a plurality of transport protocols, each filter entry in the plurality storing values that specify comparison criteria and identifying a respective queue in the computing device to which matching incoming data packets are to be delivered; the comparison criteria identified by each of the filter entries including a destination IP address and at least one member of the group consisting of a source IP address, a source transport layer port number, and a destination transport layer port number; and logic which, in response to receipt by the network interface device of a first incoming data packet; calculates a first hash key in dependence upon content of the data packet, the first hash key identifying a first hash bucket in the filter table; performs a first iterative search of entries in the filter table for a matching entry whose comparison criteria are satisfied by content of the data packet received from the network; and if a matching entry was identified by the first iterative search, forwards the packet to the receive queue in the computing device that is indicated by the matching entry, wherein; a first one of the filter entries in the plurality of filter entries is associated with a first transport protocol, and a second one of the filter entries in the plurality of filter entries is associated with a second transport protocol different from the first transport protocol; and the first filter entry and the second filter entry store destination transport layer port numbers in different fields within the respective filter entry. - View Dependent Claims (19, 20, 21, 22, 23, 24)
-
-
25. A network interface device for processing data packets received from a network, for use with a computing device, comprising:
-
a memory having stored therein in a non-transitory manner a filter table having a plurality of filter entries for filtering incoming data packets, said filter entries comprising at least one chain of filter entries, a chain length of a respective chain of filter entries comprising a number of entries between a first filter entry of the respective chain and a last filter entry that contains data corresponding to an open socket, inclusive; and a resource configuration unit configured to; replace with a tombstone marker data in an identified filter table entry that corresponds to a specific socket, in response to receipt from the computing device of a request to remove the identified filter table entry, when removing from the filter table data from a chain of filter entries including the identified filter table entry would not reduce a maximum chain length of filter entries in the filter table; and receive from the computing device one or more requests that cause the resource configuration unit to perform garbage collection of tombstoned filter entries, responsive to a determination that removing from the filter table data from a chain of filter entries including the identified filter entry would reduce the maximum chain length of filter entries in the filter table.
-
-
26. A method for processing data packets received from a network, the method comprising:
-
storing a filter table having a plurality of filter entries for filtering incoming data packets for a plurality of transport protocols, each filter entry in the plurality of filter entries storing values that specify comparison criteria and identifying a respective queue in the computing device to which matching incoming data packets are to be delivered, wherein the comparison criteria identified by each of the filter entries includes a destination IP address and at least one member of the group consists of a source IP address, a source transport layer port number, and a destination transport layer port number; receiving a first incoming data packet; calculating a first hash key in dependence upon content of the first incoming data packet, the first hash key identifying a first hash bucket in the filter table; performing a first iterative search of entries in the filter table for a matching entry whose comparison criteria are satisfied by content of the data packet received from the network; and responsive to the first iterative search identifying a matching a filter table entry, forwarding the packet to the receive queue in the computing device that is indicated by the matching entry, wherein; a first one of the filter entries in the plurality of filter entries is associated with a first transport protocol, and a second one of the filter entries in the plurality of filter entries is associated with a second transport protocol different from the first transport protocol; and the first filter entry and the second filter entry store destination transport layer port numbers in different fields within the respective filter entry.
-
-
27. A network interface device for processing data packets received from a network, for use with a computing device, comprising:
-
a memory having stored therein in a non-transitory manner a filter table having a plurality of filter entries for filtering incoming data packets for a plurality of transport protocols, each filter entry in the plurality storing values that specify comparison criteria and identifying a respective queue in the computing device to which matching incoming data packets are to be delivered; the comparison criteria identified by each of the filter entries including a destination IP address and at least one member of the group consisting of a source IP address, a source transport layer port number, and a destination transport layer port number; and logic which, in response to receipt by the network interface device of a first incoming data packet; calculates a first hash key in dependence upon content of the data packet, the first hash key identifying a first hash bucket in the filter table; performs a first iterative search of entries in the filter table for a matching entry whose comparison criteria are satisfied by content of the data packet received from the network; and if a matching entry was identified by the first iterative search, forwards the packet to the receive queue in the computing device that is indicated by the matching entry, wherein; the first iterative search of filter entries is successful upon finding a filter entry that qualifies as a full match, wherein a full match comprises the incoming data packet matching a filter entry that specifies a non-wildcard value for a set of required fields comprising the destination IP address, the destination transport layer port address, and at least one of the source IP address or the source transport layer port address; and every value in the set of required fields matches the respective fields in the incoming data packet.
-
-
28. A network interface device for processing data packets received from a network, for use with a computing device, comprising:
-
a memory having stored therein in a non-transitory manner a filter table having a plurality of filter entries for filtering incoming data packets for a plurality of transport protocols, each filter entry in the plurality storing values that specify comparison criteria and identifying a respective queue in the computing device to which matching incoming data packets are to be delivered; the comparison criteria identified by each of the filter entries including a destination IP address and at least one member of the group consisting of a source IP address, a source transport layer port number, and a destination transport layer port number; and logic which, in response to receipt by the network interface device of a first incoming data packet; calculates a first hash key in dependence upon content of the data packet, the first hash key identifying a first hash bucket in the filter table; performs a first iterative search of entries in the filter table for a matching entry whose comparison criteria are satisfied by content of the data packet received from the network; and if a matching entry was identified by the first iterative search, forwards the packet to the receive queue in the computing device that is indicated by the matching entry, wherein; the logic considers the first iterative search of filter entries to be successful upon finding a filter entry that qualifies as a wildcard match with the incoming data packet, wherein the filter entry specifies a non-wildcard value for a set of required fields comprising the destination IP address, and the destination transport layer port address; and every value in the set of required fields matches the respective fields in the incoming data packet.
-
-
29. A method for processing data packets received from a network, the method comprising:
-
storing a filter table having a plurality of filter entries for filtering incoming data packets for a plurality of transport protocols, each filter entry in the plurality of filter entries storing values that specify comparison criteria and identifying a respective queue in the computing device to which matching incoming data packets are to be delivered, wherein the comparison criteria identified by each of the filter entries includes a destination IP address and at least one member of the group consists of a source IP address, a source transport layer port number, and a destination transport layer port number; receiving a first incoming data packet; calculating a first hash key in dependence upon content of the first incoming data packet, the first hash key identifying a first hash bucket in the filter table; performing a first iterative search of entries in the filter table for a matching entry whose comparison criteria are satisfied by content of the data packet received from the network; responsive to the first iterative search identifying a matching a filter table entry, forwarding the packet to the receive queue in the computing device that is indicated by the matching entry, wherein; the first iterative search of filter entries is successful upon finding a filter entry that qualifies as a full match, wherein a full match comprises the incoming data packet matching a filter entry that specifies a non-wildcard value for a set of required fields comprising the destination IP address, the destination transport layer port address, and at least one of the source IP address or the source transport layer port address; and every value in the set of required fields matches the respective fields in the incoming data packet.
-
-
30. A method for processing data packets received from a network, the method comprising:
-
storing a filter table having a plurality of filter entries for filtering incoming data packets for a plurality of transport protocols, each filter entry in the plurality of filter entries storing values that specify comparison criteria and identifying a respective queue in the computing device to which matching incoming data packets are to be delivered, wherein the comparison criteria identified by each of the filter entries includes a destination IP address and at least one member of the group consists of a source IP address, a source transport layer port number, and a destination transport layer port number; receiving a first incoming data packet; calculating a first hash key in dependence upon content of the first incoming data packet, the first hash key identifying a first hash bucket in the filter table; performing a first iterative search of entries in the filter table for a matching entry whose comparison criteria are satisfied by content of the data packet received from the network; and responsive to the first iterative search identifying a matching a filter table entry, forwarding the packet to the receive queue in the computing device that is indicated by the matching entry, wherein; the logic considers the first iterative search of filter entries to be successful upon finding a filter entry that qualifies as a wildcard match with the incoming data packet, wherein the filter entry specifies a non-wildcard value for a set of required fields comprising the destination IP address, and the destination transport layer port address; and every value in the set of required fields matches the respective fields in the incoming data packet.
-
Specification