Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Adopt Hopscotch hash table throughout Gatekeeper #662

Open
AltraMayor opened this issue Oct 13, 2023 · 0 comments
Open

Adopt Hopscotch hash table throughout Gatekeeper #662

AltraMayor opened this issue Oct 13, 2023 · 0 comments

Comments

@AltraMayor
Copy link
Owner

AltraMayor commented Oct 13, 2023

Gatekeeper version 1.2 introduces a general Hopscotch hash table library to implement the flow table, Gatekeeper counts with its own hash table library. We now may be able to replace all hash tables in Gatekeeper that use DPDK's hash library; search for rte_hash_create().

Currently, there are two use cases for hash tables:

  1. lls/cache.c: hash table for ARP and ND resolutions.
  2. gk/rt.c: hash table for cache of Ethernet headers. While the code has a single writer, care must be taken to support concurrent readers. The new code should leverage the internal QID of Gatekeeper's hash table to simplify the allocation of caches of Ethernet headers (see get_new_ether_cache_locked()). An entry array will be needed to hold the key of the entries and the data pointer. The GT block uses the code of this cache as well, so it makes sense to move it into its own library.

These use cases may require one to improve our hash library to support concurrent readers while a single writer updates the table. But before this improvement is done, one should review the synchronization model of the use cases to check if they can be rewritten in such a way that no synchronization is needed. If the improvement of our hash library is necessary, it must not have any significant performance penalty since this library is used to implement the flow table of Gatekeeper.

The hash tables of the use cases above are relatively small, so one can set their performance parameters as follows: max_probes = 8 and scale_num_bucket = 2.

@AltraMayor AltraMayor added this to the Code refactoring milestone Oct 13, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant