Method to perform hash table lookup for keys wider than data path size
Described are input output (IO) device configured to perform operations for performing a table lookup with a single wide key larger than a width of a system bus. These operations comprise: receiving the lookup key; performing a plurality of extraction cycles to determine a plurality of key fragments; calculating a final hash value for the lookup key by sequentially calculating, via a hash chain, an interim hash value for each of the key fragments; determine a read access address for a table entry of a logic table based on the final hash value for the lookup key; determine a plurality of read requests based on the read access address; determine a hit on the table entry with the lookup key by issuing each of the read requests to the memory subsystem; and provide the hit on the table entry to the requesting entity or a next processing entity.
1. A network interface card (NIC) comprising a memory unit, a communication system, and a memory subsystem coupled to the memory unit via the communication system, the NIC configured to perform at least:
receiving a transaction input from a requesting entity, the transaction input comprising a lookup key, wherein the lookup key includes data for processing within a hash table to determine a read access address for a table entry of a logic table stored in the memory unit;
identifying, by processing the transaction input, a plurality of fields within a data structure based on a field selection control, wherein the plurality of fields are scattered in non-contiguous locations within the data structure, and wherein the field selection control is based upon a static configuration of the hash table that identifies the plurality of fields within the data structure;
creating a plurality of key fragments from the plurality of fields by performing a plurality of extraction cycles, wherein a size of each of the key fragments is based on a width of a bus of the communication system coupled to a hash calculation circuit;
serially transmitting each of the key fragments to the hash calculation circuit using the bus;
calculating, via the hash calculation circuit, a final hash value for the lookup key by sequentially calculating, via a hash chain, an interim hash value for each of the key fragments using the hash table; and
identifying the read access address for the table entry of the logic table based on the final hash value for the lookup key.
2. The NIC of claim 1 , wherein the NIC configured to perform at least:
determining a plurality of read requests based on the read access address;
determining a hit on the table entry with the lookup key by issuing each of the read requests to the memory subsystem and comparing a plurality of respective read responses, received from the memory subsystem, to the respective fragment; and
providing the hit on the table entry to the requesting entity or a next processing entity, wherein each of the read requests include an incrementing address.
3. The NIC of claim 2 , wherein a size of each of the read requests is determined according to a bandwidth of the communication system.
4. The NIC of claim 3 , wherein each of the read requests is issued per each of the key fragments.
5. The NIC of claim 4 , wherein the each of the read responses comprise a data line in the memory unit, and wherein each of the key fragments are matched with the corresponding data line to determine the hit on the table entry.
6. The NIC of claim 5 , wherein the read responses are received from the memory subsystem in a first in, first out (FIFO) order.
7. The NIC of claim 5 , further configured to perform: reordering the read responses to a first in, first out (FIFO) order before determining the hit on the table entry.
8. The NIC of claim 5 , wherein the hit on the table entry is determined by:
maintaining, as comparisons for the matching are performed, a match indication on the lookup key via an AND of the matched data lines and the key fragments.
9. The NIC of claim 5 , wherein the hit on the table entry is determined by:
applying a configurable mask to the last key fragment and the last data line returned before the matching is performed.
10. The NIC of claim 1 , wherein the requesting entity comprises a processing unit, hardware logics that use the logic table, or a stage in a hardware processing pipeline.
11. The NIC of claim 2 , wherein the next processing entity comprises a processing unit, hardware logics that use the logic table, or a stage in a hardware processing pipeline.
12. The NIC of claim 1 , wherein the data structure further comprises a second plurality of fields are not used by the logic table, and wherein the second plurality of fields are provided to a next processing entity for downstream processing.
13. The NIC of claim 1 , wherein a start of transaction (SOT) control signal and an end of transaction (EOT) control signal, determined according to the transaction input, are stored on a sideband.
14. The NIC of claim 1 , wherein the communication system comprises a system bus, and wherein a bandwidth of the communication system comprise a width of the system bus.
15. The NIC of claim 1 , wherein the hash calculation circuit employs a cyclic redundancy check (CRC) as a hash function.
16. The NIC of claim 15 , wherein the CRC is serialized to support wide keys with a single temporary storage, and wherein the single temporary storage is a same width as output of the CRC.
17. The NIC of claim 1 , wherein the hash calculation circuit employs a configurable mask to the last fragment before determining the interim hash value for the last key fragment.
18. The NIC of claim 1 , wherein the interim hash value for the last key fragment comprises the final hash value for the transaction input.
19. The NIC of claim 1 , wherein a number of key fragments is configurable per the logic table.
20. The NIC of claim 1 , wherein a number of key fragments and a number of read requests are equal, and wherein the size of each of the key fragments and a size of each of the read requests are determined according to a bandwidth of the communication system.
21. The NIC of claim 1 , wherein a number of read requests is determined according to the table entry and a bandwidth of the communication system.
22. The NIC of claim 1 , wherein each table entry in the logic table comprises a full key matching the lookup key and data associated with the full key.
23. The NIC of claim 1 , wherein the NIC comprises a router, a switch, or a smart network interface card (smartNIC).
24. A method for a network interface card (NIC) performing a table lookup with a single wide key larger than a width of a system bus, the method comprising:
receiving a transaction input from a requesting entity, the transaction input comprising a lookup key, wherein the lookup key includes data for processing within a hash table to determine a read access address for a table entry of a logic table stored in a memory unit;
identifying, by processing the transaction input, a plurality of fields within a data structure based on a field selection control, wherein the plurality of fields are scattered in non-contiguous locations within the data structure, and wherein the field selection control is based upon a static configuration of the hash table that identifies the plurality of fields within the data structure;
creating a plurality of key fragments from the plurality of fields by performing a plurality of extraction cycle, wherein a size of each of the key fragments is based on the width of the system bus wherein the system bus is coupled to a hash calculation circuit;
serially transmitting each of the key fragments to the hash calculation circuit using the system bus;
calculating, via the hash calculation circuit, a final hash value for the lookup key by sequentially calculating, via a hash chain, an interim hash value for each of the key fragments using the hash table;
determining the read access address for the table entry of the logic table based on the final hash value for the lookup key;
identifying a plurality of read requests based on the read access address;
identifying a hit on the table entry with the lookup key by issuing each of the read requests to a memory subsystem and comparing a plurality of respective read responses, received from the memory subsystem, to the respective fragment; and
transmitting the hit on the table entry to the requesting entity or a next processing entity.
25. The method of claim 24 , wherein the each of the read responses comprise a data line in a memory unit, and wherein each of the key fragments are matched with the corresponding data line to determine the hit on the table entry, wherein the hit on the table entry is determined by:
maintaining, as comparisons for the matching are performed, a match indication on the lookup key via an AND of the matched data lines and the key fragments; and
applying a configurable mask to the last key fragment and the last data line returned before the matching is performed.
26. The method of claim 24 , wherein the hash calculation circuit employs a cyclic redundancy check (CRC) as a hash function.
27. The method of claim 24 , wherein the hash calculation circuit employs a configurable mask to the last fragment before determining the interim hash value for the last key fragment.
28. The method of claim 24 , wherein a number of key fragments and a number of read requests are equal, and wherein the size of each of the key fragments and a size of each of the read requests are determined according to the width of the system bus.
29. A programmable system with wide key support, comprising:
a requesting entity; and
a network interface card (NIC) comprising a memory unit, a system bus, and a memory subsystem coupled to the memory unit via the system bus, the NIC coupled to the requesting entity and configured to perform operations comprising:
receiving a transaction input from the requesting entity, the transaction input comprising a lookup key, wherein the lookup key includes data for processing within a hash table to determine a read access address for a table entry of a logic table stored in the memory unit;
identifying, by processing the transaction input, a plurality of fields within a data structure that in combination form the lookup key based on a field selection control, wherein the plurality of fields are scattered in non-contiguous locations within the data structure, and wherein the field selection control is based upon a static configuration of the hash table that identifies the plurality of fields within the data structure;
creating a plurality of key fragments from the plurality of fields by performing a plurality of extraction cycles, wherein a size of each of the key fragments is based on a width of the system bus wherein the system bus is coupled to a hash calculation circuit;
serially transmitting each of the key fragments to the hash calculation circuit using the system bus;
calculating, via the hash calculation circuit, a final hash value for the lookup key by sequentially calculating, via a hash chain, an interim hash value for each of the key fragments using the hash table;
identifying the read access address for the table entry of the logic table based on the final hash value for the lookup key;
identifying a plurality of read requests based on the read access address;
identifying a hit on the table entry with the lookup key by issuing each of the read requests to the memory subsystem and comparing a plurality of respective read responses, received from the memory subsystem, to the respective fragment; and
transmitting the hit on the table entry to the requesting entity or a next processing entity.
30. The NIC of claim 1 , wherein each of the interim hash values is stored to a temporary register and used as an initial value in a next calculation, and wherein a first interim hash value is calculated for a first key fragment using zero as the initial value.
31. The NIC of claim 1 , wherein the read access address is further determined based on a base address of the logic table and a size of the logic table, and wherein the table entry is populated with the lookup key.