Concurrent linked-list traversal for real-time hash processing in multi-core, multi-thread network processors

摘要

Described embodiments process hash operation requests of a network processor. A hash processor determines a job identifier, a corresponding hash table, and a setting of a traversal indicator for a received hash operation request that includes a desired key. The hash processor concurrently generates a read request for a first bucket of the hash table, and provides the job identifier, the key and the traversal indicator to a read return processor. The read return processor stores the key and traversal indicator in a job memory and stores, in a return memory, entries of the first bucket of the hash table. If a stored entry matches the desired key, the read return processor determines, based on the traversal indicator, whether to read a next bucket of the hash table and provides the job identifier, the matching key, and the address of the bucket containing the matching key to the hash processor.

主权项

1. A hardware network processor having a plurality of processing modules and at least one shared memory, the network processor comprising:
a hash processor configured to:
receive a hash operation request from at least one processing module, the hash operation request having a desired hash key and corresponding type, wherein the type of the hash operation request is one of (i) a non-table-modifying request and (ii) a table-modifying request;set and clear a traversal indicator corresponding to the received hash operation request;when the traversal indicator is set for a non-table-modifying request, search for a first matching hash key without traversing to a last bucket of the hash table;when the traversal indicator is cleared for a table-modifying request, search for one or more matching hash keys and to traverse to the last bucket of the hash table;select a hash table corresponding to the received hash operation request, each hash table comprising a plurality of entries, a first subset of entries located in a direct mapped table, and a second subset of entries located in one or more dynamic hash buckets in the at least one shared memory;determine a number of dynamic hash buckets corresponding to the selected hash table;wherein, when a number of entries in the first subset of entries corresponding to the given hash table reaches a threshold, the hash processor is configured to:
allocate an available dynamic hash bucket to the given hash table and update a link value of the corresponding hash table in the direct mapped table;process the received hash operation request based on the corresponding type of the hash operation request and the corresponding selected hash table; andprovide hash operation results to the processing module of the network processor corresponding to the hash operation request, wherein the hash processor is configured to concurrently process one or more non-table-modifying requests and one or more table-modifying requests for non-overlapping hash table entries.