Mechanism to support multiple-writer/multiple-reader concurrency for software flow/packet classification on general purpose multi-core systems

Patent metadata

Field	Value
Publication number	US-10218647-B2
Application number	US-201514960993-A
Country	US
Kind code	B2
Filing date	Dec 7, 2015
Priority date	Dec 7, 2015
Publication date	Feb 26, 2019
Grant date	Feb 26, 2019

Abstract

Methods and apparatus to support multiple-writer/multiple-reader concurrency for software flow/packet classification on general purpose multi-core systems. A flow table with rows mapped to respective hash buckets with multiple entry slots is implemented in memory of a host platform with multiple cores, with each bucket being associated with a version counter. Multiple writer and reader threads are run on the cores, with writers providing updates to the flow table data. In connection with inserting new key data, a determination is made to which buckets will be changed, and access rights to those buckets are acquired prior to making any changes. For example, under a flow table employing cuckoo hashing, access rights are acquired to buckets along a full cuckoo path. Once the access rights are obtained, a writer is enabled to update data in the applicable buckets to effect entry of the new key data, while other writer threads are prevented from changing any of these buckets, but may concurrently insert or modify key data in other buckets.

First claim

What is claimed is:

1. A method for supporting multiple-writer and multiple-reader concurrency for packet flow data, comprising:
implementing a flow table in memory of a host platform including multiple processor cores, the flow table including multiple rows, each row mapped to a respective hash bucket, each hash bucket containing one or more entry slots in which key data are stored;
enabling concurrent read access to the flow table from multiple readers; and
enabling concurrent write access to the flow table from multiple writers by,
associating each bucket with a version counter, wherein a given version counter is associated with one or more buckets;
employing a plurality of threads, executing on the plurality of cores, to concurrently update data in the flow table, each thread comprising a writer;
inserting new key data into the flow table, the insertion of the new key data requiring updates to key data in multiple buckets; and
implementing an access mechanism that guarantees that only one writer can update any of the multiple buckets while the new key data is being inserted into the flow table,
wherein while the single writer is updating the multiple buckets required for a given insertion of new key data one or more other writers are enabled to concurrently insert new key data in the flow table by updating one or more buckets that are not among the multiple buckets being updated by the single writer.

2. The method of claim 1 , further comprising:
identifying multiple buckets that will include key data that will be updated in connection with inserting the new key data;
acquiring update-rights to each of the multiple buckets before updating any of the multiple buckets; and
updating key data in each of the multiple buckets to effect insertion of the new key data.

3. The method of claim 2 , wherein acquiring update-rights to each of identified buckets includes use of a compare and swap (CAS) instruction.

4. The method of claim 3 , wherein the CAS instruction comprises a compare and exchange instruction (CMPXCHG) instruction.

5. The method of claim 1 , wherein the flow table is a cuckoo hash table with multiple entry slots for each bucket, further comprising determining a full cuckoo path that will be used to insert the new key data to identify the multiple buckets that include key data that will be updated in connection with inserting the new key data.

6. The method of claim 1 , further comprising:
for each of the multiple buckets having key data that will be updated via insertion of the new key data,
determining whether the current data in the bucket is being updated; and
if the current data is not being updated, updating a count for the version counter associated with the bucket to indicate the current data in the bucket is in the process of being updated.

7. The method of claim 6 , further comprising:
determining that the current data for at least one of the buckets is not being updated;
incrementing the version counter associated with said at least one of the buckets that is not being updated;
subsequently determining that the current data in one of the buckets is being updated; and in response thereto;
rolling back each of the version counters associated with said at least one of the buckets that is not being updated that was incremented.

8. The method of claim 7 , wherein the operations are associated with a failed attempt to acquire update rights for each of the multiple buckets, the method further comprising:
waiting a random time interval after the version counters have been rolled back; and
re-attempting to acquire update-rights for each of the multiple buckets.

9. The method of claim 6 , wherein updating a count for a version counter comprises incrementing a current counter value, further comprising:
determining that update-rights for each of the multiple buckets has been acquired;
updating key data in each of the multiple buckets, and in associate with the update for each bucket, incrementing the version counter associated with that bucket.

10. The method of claim 1 , wherein the host platform comprises a multi-socketed platform having a non-uniform memory access (NUMA) architecture.

11. The method of claim 1 , wherein the plurality of readers are enabled to concurrently read key data in the flow table and the plurality of writers are enabled to concurrently update key data in the flow table without use of mutexes or locks.

12. One or more non-transient machine readable mediums, having instructions stored thereon configured to be executed on a host platform including a plurality of processor cores operatively coupled to system memory, wherein the instructions are configured, upon execution, to:
implement a flow table in a portion of the system memory, the flow table including multiple rows, each row mapped to a respective hash bucket, each hash bucket containing one or more entry slots in which key data are stored;
associate each bucket with a version counter, wherein a given version counter is associated with one or more buckets;
launch a plurality of threads, each comprising a writer or a reader, the plurality of threads including each of a plurality of writers and a plurality of readers, each writer configured to update data in the flow table and each reader configured to read data in the flow table;
enable the plurality of readers to concurrently read key data in the flow table; and
enable the plurality of writers to concurrently update key data in the flow table by,
inserting, via the plurality of writers, new key data into the flow table, the insertion of at least some of the new key data requiring updates to key data in multiple buckets; and
enabling only a single writer to update any of the multiple buckets required for a given insertion of new key data while the new key data is being inserted into the flow table, wherein while the single writer is updating the multiple buckets required for a given insertion of new key data one or more other writers are enabled to concurrently insert new key data in the flow table by updating one or more buckets that are not among the multiple buckets being updated by the single writer.

13. The one or more non-transient machine readable mediums of claim 12 , wherein the instructions are further configured, upon execution, to:
identify multiple buckets that will include key data that will be updated in connection with inserting the new key data;
acquire update-rights to each of the multiple buckets before updating any of the multiple buckets; and
update key data in each of the multiple buckets to effect insertion of the new key data.

14. The one or more non-transient machine readable mediums of claim 13 , wherein acquiring update-rights to each of identified buckets includes use of a compare and swap (CAS) instruction.

15. The one or more non-transient machine readable mediums of claim 14 , wherein the CAS instruction comprises a compare and exchange instruction (CMPXCHG) instruction.

16. The one or more non-transient machine readable mediums of claim 12 , wherein the flow table is a cuckoo hash table with multiple entry slots for each bucket, wherein the instructions are further configured, upon execution, to determine a full cuckoo path that will be used to insert the new key data to identify the multiple buckets that include key data that will be updated in connection with inserting the new key data.

17. The one or more non-transient machine readable mediums of claim 12 , wherein the instructions are further configured, upon execution, to:
for each of the multiple buckets havin

Assignees

• Wang Ren
• Maciocco Christian
• Venkatesan Namakkal N
• Tai Tsung Yuan C
• Intel Corp

Inventors

• Wang Ren
• Maciocco Christian
• Venkatesan Namakkal N
• Tai Tsung-Yuan C

Classifications

• H04L49/9094 Primary

  Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element · CPC title

• H04L45/38

  Flow based routing · CPC title

• H04L45/7453

  using hashing · CPC title

• H04L45/54

  Organization of routing tables · CPC title