[dpdk-dev] hash: fix to support multi process
Commit Message
Hash library used a function pointer to choose a different
key compare function, depending on the key size.
As a result, multiple processes could not use the same hash table,
as the function addresses vary from one process to another.
Instead, a jump table is used, so each process has its own
function addresses, accessing this table with an index stored
in the hash table (note that using a custom key compare function
is not supported in multi-process mode).
Fixes: 48a399119619 ("hash: replace with cuckoo hash implementation")
Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
doc/guides/rel_notes/release_16_04.rst | 5 ++
lib/librte_hash/rte_cuckoo_hash.c | 85 ++++++++++++++++++++++++++--------
2 files changed, 71 insertions(+), 19 deletions(-)
Comments
On Thu, Mar 24, 2016 at 01:56:44PM +0000, Pablo de Lara wrote:
> Hash library used a function pointer to choose a different
> key compare function, depending on the key size.
> As a result, multiple processes could not use the same hash table,
> as the function addresses vary from one process to another.
>
> Instead, a jump table is used, so each process has its own
> function addresses, accessing this table with an index stored
> in the hash table (note that using a custom key compare function
> is not supported in multi-process mode).
>
> Fixes: 48a399119619 ("hash: replace with cuckoo hash implementation")
>
> Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
This is a hard problem to solve, but this probably looks the least-worst solution
to it. Pablo, I assume the performance hit for lookups is pretty small here?
One small nit in the code below, and a comment on the doc change. Otherwise,
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
> ---
> doc/guides/rel_notes/release_16_04.rst | 5 ++
> lib/librte_hash/rte_cuckoo_hash.c | 85 ++++++++++++++++++++++++++--------
> 2 files changed, 71 insertions(+), 19 deletions(-)
>
> diff --git a/doc/guides/rel_notes/release_16_04.rst b/doc/guides/rel_notes/release_16_04.rst
> index 2785b29..c4359dd 100644
> --- a/doc/guides/rel_notes/release_16_04.rst
> +++ b/doc/guides/rel_notes/release_16_04.rst
> @@ -351,6 +351,11 @@ Libraries
> Fix crc32c hash functions to return a valid crc32c value for data lengths
> not multiple of 4 bytes.
>
> +* **hash: Fixed hash library to support multi-process mode.**
> +
> + Fix hash library to support multi-process mode, using a jump table,
> + instead of storing a function pointer to the key compare function.
> +
You probably need to clarify here and in the other docs (e.g. API doc) that:
* multi-process mode only works with the built-in functions and key sizes.
* a custom function not in the jump table can be used but only in single-process
mode.
> * **librte_port: Fixed segmentation fault for ring and ethdev writer nodrop.**
>
> Fixed core dump issue on txq and swq when dropless is set to yes.
> diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
> index 71b5b76..38c19ab 100644
> --- a/lib/librte_hash/rte_cuckoo_hash.c
> +++ b/lib/librte_hash/rte_cuckoo_hash.c
> @@ -102,6 +102,41 @@ EAL_REGISTER_TAILQ(rte_hash_tailq)
>
> #define LCORE_CACHE_SIZE 8
>
> +/*
> + * All different options to select a key compare function,
> + * based on the key size and custom function.
> + */
> +enum cmp_jump_table_case {
> + KEY_CUSTOM = 0,
> + KEY_16_BYTES,
> + KEY_32_BYTES,
> + KEY_48_BYTES,
> + KEY_64_BYTES,
> + KEY_80_BYTES,
> + KEY_96_BYTES,
> + KEY_112_BYTES,
> + KEY_128_BYTES,
> + KEY_OTHER_BYTES,
> + NUM_KEY_CMP_CASES,
> +};
> +
> +/*
> + * Table storing all different key compare functions
> + * (multi-process supported)
> + */
> +rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
> + NULL,
> + rte_hash_k16_cmp_eq,
> + rte_hash_k32_cmp_eq,
> + rte_hash_k48_cmp_eq,
> + rte_hash_k64_cmp_eq,
> + rte_hash_k80_cmp_eq,
> + rte_hash_k96_cmp_eq,
> + rte_hash_k112_cmp_eq,
> + rte_hash_k128_cmp_eq,
> + memcmp
> +};
Array should be const.
/Bruce
Hi,
> -----Original Message-----
> From: Richardson, Bruce
> Sent: Friday, March 25, 2016 2:41 PM
> To: De Lara Guarch, Pablo
> Cc: dev@dpdk.org; edreddy@gmail.com
> Subject: Re: [PATCH] hash: fix to support multi process
>
> On Thu, Mar 24, 2016 at 01:56:44PM +0000, Pablo de Lara wrote:
> > Hash library used a function pointer to choose a different
> > key compare function, depending on the key size.
> > As a result, multiple processes could not use the same hash table,
> > as the function addresses vary from one process to another.
> >
> > Instead, a jump table is used, so each process has its own
> > function addresses, accessing this table with an index stored
> > in the hash table (note that using a custom key compare function
> > is not supported in multi-process mode).
> >
> > Fixes: 48a399119619 ("hash: replace with cuckoo hash implementation")
> >
> > Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
>
> This is a hard problem to solve, but this probably looks the least-worst
> solution
> to it. Pablo, I assume the performance hit for lookups is pretty small here?
Yes, performance degradation is negligible.
>
> One small nit in the code below, and a comment on the doc change.
Will send a v2 with the changes. Anyway, I was waiting for Djama and Zhang
to give some feedback here and see if it works for them.
Thanks,
Pablo
> Otherwise,
>
> Acked-by: Bruce Richardson <bruce.richardson@intel.com>
>
> > ---
> > doc/guides/rel_notes/release_16_04.rst | 5 ++
> > lib/librte_hash/rte_cuckoo_hash.c | 85 ++++++++++++++++++++++++++-
> -------
> > 2 files changed, 71 insertions(+), 19 deletions(-)
> >
> > diff --git a/doc/guides/rel_notes/release_16_04.rst
> b/doc/guides/rel_notes/release_16_04.rst
> > index 2785b29..c4359dd 100644
> > --- a/doc/guides/rel_notes/release_16_04.rst
> > +++ b/doc/guides/rel_notes/release_16_04.rst
> > @@ -351,6 +351,11 @@ Libraries
> > Fix crc32c hash functions to return a valid crc32c value for data lengths
> > not multiple of 4 bytes.
> >
> > +* **hash: Fixed hash library to support multi-process mode.**
> > +
> > + Fix hash library to support multi-process mode, using a jump table,
> > + instead of storing a function pointer to the key compare function.
> > +
> You probably need to clarify here and in the other docs (e.g. API doc) that:
> * multi-process mode only works with the built-in functions and key sizes.
> * a custom function not in the jump table can be used but only in single-
> process
> mode.
>
> > * **librte_port: Fixed segmentation fault for ring and ethdev writer
> nodrop.**
> >
> > Fixed core dump issue on txq and swq when dropless is set to yes.
> > diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> b/lib/librte_hash/rte_cuckoo_hash.c
> > index 71b5b76..38c19ab 100644
> > --- a/lib/librte_hash/rte_cuckoo_hash.c
> > +++ b/lib/librte_hash/rte_cuckoo_hash.c
> > @@ -102,6 +102,41 @@ EAL_REGISTER_TAILQ(rte_hash_tailq)
> >
> > #define LCORE_CACHE_SIZE 8
> >
> > +/*
> > + * All different options to select a key compare function,
> > + * based on the key size and custom function.
> > + */
> > +enum cmp_jump_table_case {
> > + KEY_CUSTOM = 0,
> > + KEY_16_BYTES,
> > + KEY_32_BYTES,
> > + KEY_48_BYTES,
> > + KEY_64_BYTES,
> > + KEY_80_BYTES,
> > + KEY_96_BYTES,
> > + KEY_112_BYTES,
> > + KEY_128_BYTES,
> > + KEY_OTHER_BYTES,
> > + NUM_KEY_CMP_CASES,
> > +};
> > +
> > +/*
> > + * Table storing all different key compare functions
> > + * (multi-process supported)
> > + */
> > +rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
> > + NULL,
> > + rte_hash_k16_cmp_eq,
> > + rte_hash_k32_cmp_eq,
> > + rte_hash_k48_cmp_eq,
> > + rte_hash_k64_cmp_eq,
> > + rte_hash_k80_cmp_eq,
> > + rte_hash_k96_cmp_eq,
> > + rte_hash_k112_cmp_eq,
> > + rte_hash_k128_cmp_eq,
> > + memcmp
> > +};
>
> Array should be const.
>
> /Bruce
@@ -351,6 +351,11 @@ Libraries
Fix crc32c hash functions to return a valid crc32c value for data lengths
not multiple of 4 bytes.
+* **hash: Fixed hash library to support multi-process mode.**
+
+ Fix hash library to support multi-process mode, using a jump table,
+ instead of storing a function pointer to the key compare function.
+
* **librte_port: Fixed segmentation fault for ring and ethdev writer nodrop.**
Fixed core dump issue on txq and swq when dropless is set to yes.
@@ -102,6 +102,41 @@ EAL_REGISTER_TAILQ(rte_hash_tailq)
#define LCORE_CACHE_SIZE 8
+/*
+ * All different options to select a key compare function,
+ * based on the key size and custom function.
+ */
+enum cmp_jump_table_case {
+ KEY_CUSTOM = 0,
+ KEY_16_BYTES,
+ KEY_32_BYTES,
+ KEY_48_BYTES,
+ KEY_64_BYTES,
+ KEY_80_BYTES,
+ KEY_96_BYTES,
+ KEY_112_BYTES,
+ KEY_128_BYTES,
+ KEY_OTHER_BYTES,
+ NUM_KEY_CMP_CASES,
+};
+
+/*
+ * Table storing all different key compare functions
+ * (multi-process supported)
+ */
+rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
+ NULL,
+ rte_hash_k16_cmp_eq,
+ rte_hash_k32_cmp_eq,
+ rte_hash_k48_cmp_eq,
+ rte_hash_k64_cmp_eq,
+ rte_hash_k80_cmp_eq,
+ rte_hash_k96_cmp_eq,
+ rte_hash_k112_cmp_eq,
+ rte_hash_k128_cmp_eq,
+ memcmp
+};
+
struct lcore_cache {
unsigned len; /**< Cache len */
void *objs[LCORE_CACHE_SIZE]; /**< Cache objects */
@@ -115,7 +150,10 @@ struct rte_hash {
uint32_t key_len; /**< Length of hash key. */
rte_hash_function hash_func; /**< Function used to calculate hash. */
uint32_t hash_func_init_val; /**< Init value used by hash_func. */
- rte_hash_cmp_eq_t rte_hash_cmp_eq; /**< Function used to compare keys. */
+ rte_hash_cmp_eq_t rte_hash_custom_cmp_eq;
+ /**< Custom function used to compare keys. */
+ enum cmp_jump_table_case cmp_jump_table_idx;
+ /**< Indicates which compare function to use. */
uint32_t bucket_bitmask; /**< Bitmask for getting bucket index
from hash signature. */
uint32_t key_entry_size; /**< Size of each key entry. */
@@ -187,7 +225,16 @@ rte_hash_find_existing(const char *name)
void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func)
{
- h->rte_hash_cmp_eq = func;
+ h->rte_hash_custom_cmp_eq = func;
+}
+
+static inline int
+rte_hash_cmp_eq(const void *key1, const void *key2, const struct rte_hash *h)
+{
+ if (h->cmp_jump_table_idx == KEY_CUSTOM)
+ return h->rte_hash_custom_cmp_eq(key1, key2, h->key_len);
+ else
+ return cmp_jump_table[h->cmp_jump_table_idx](key1, key2, h->key_len);
}
struct rte_hash *
@@ -292,35 +339,35 @@ rte_hash_create(const struct rte_hash_parameters *params)
/* Select function to compare keys */
switch (params->key_len) {
case 16:
- h->rte_hash_cmp_eq = rte_hash_k16_cmp_eq;
+ h->cmp_jump_table_idx = KEY_16_BYTES;
break;
case 32:
- h->rte_hash_cmp_eq = rte_hash_k32_cmp_eq;
+ h->cmp_jump_table_idx = KEY_32_BYTES;
break;
case 48:
- h->rte_hash_cmp_eq = rte_hash_k48_cmp_eq;
+ h->cmp_jump_table_idx = KEY_48_BYTES;
break;
case 64:
- h->rte_hash_cmp_eq = rte_hash_k64_cmp_eq;
+ h->cmp_jump_table_idx = KEY_64_BYTES;
break;
case 80:
- h->rte_hash_cmp_eq = rte_hash_k80_cmp_eq;
+ h->cmp_jump_table_idx = KEY_80_BYTES;
break;
case 96:
- h->rte_hash_cmp_eq = rte_hash_k96_cmp_eq;
+ h->cmp_jump_table_idx = KEY_96_BYTES;
break;
case 112:
- h->rte_hash_cmp_eq = rte_hash_k112_cmp_eq;
+ h->cmp_jump_table_idx = KEY_112_BYTES;
break;
case 128:
- h->rte_hash_cmp_eq = rte_hash_k128_cmp_eq;
+ h->cmp_jump_table_idx = KEY_128_BYTES;
break;
default:
/* If key is not multiple of 16, use generic memcmp */
- h->rte_hash_cmp_eq = memcmp;
+ h->cmp_jump_table_idx = KEY_OTHER_BYTES;
}
#else
- h->rte_hash_cmp_eq = memcmp;
+ h->cmp_jump_table_idx = KEY_OTHER_BYTES;
#endif
snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
@@ -594,7 +641,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
prim_bkt->signatures[i].alt == alt_hash) {
k = (struct rte_hash_key *) ((char *)keys +
prim_bkt->key_idx[i] * h->key_entry_size);
- if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
+ if (rte_hash_cmp_eq(key, k->key, h) == 0) {
/* Enqueue index of free slot back in the ring. */
enqueue_slot_back(h, cached_free_slots, slot_id);
/* Update data */
@@ -614,7 +661,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
sec_bkt->signatures[i].current == alt_hash) {
k = (struct rte_hash_key *) ((char *)keys +
sec_bkt->key_idx[i] * h->key_entry_size);
- if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
+ if (rte_hash_cmp_eq(key, k->key, h) == 0) {
/* Enqueue index of free slot back in the ring. */
enqueue_slot_back(h, cached_free_slots, slot_id);
/* Update data */
@@ -725,7 +772,7 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
bkt->signatures[i].sig != NULL_SIGNATURE) {
k = (struct rte_hash_key *) ((char *)keys +
bkt->key_idx[i] * h->key_entry_size);
- if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
+ if (rte_hash_cmp_eq(key, k->key, h) == 0) {
if (data != NULL)
*data = k->pdata;
/*
@@ -748,7 +795,7 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
bkt->signatures[i].alt == sig) {
k = (struct rte_hash_key *) ((char *)keys +
bkt->key_idx[i] * h->key_entry_size);
- if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
+ if (rte_hash_cmp_eq(key, k->key, h) == 0) {
if (data != NULL)
*data = k->pdata;
/*
@@ -840,7 +887,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
bkt->signatures[i].sig != NULL_SIGNATURE) {
k = (struct rte_hash_key *) ((char *)keys +
bkt->key_idx[i] * h->key_entry_size);
- if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
+ if (rte_hash_cmp_eq(key, k->key, h) == 0) {
remove_entry(h, bkt, i);
/*
@@ -863,7 +910,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
bkt->signatures[i].sig != NULL_SIGNATURE) {
k = (struct rte_hash_key *) ((char *)keys +
bkt->key_idx[i] * h->key_entry_size);
- if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {
+ if (rte_hash_cmp_eq(key, k->key, h) == 0) {
remove_entry(h, bkt, i);
/*
@@ -980,7 +1027,7 @@ lookup_stage3(unsigned idx, const struct rte_hash_key *key_slot, const void * co
unsigned hit;
unsigned key_idx;
- hit = !h->rte_hash_cmp_eq(key_slot->key, keys[idx], h->key_len);
+ hit = !rte_hash_cmp_eq(key_slot->key, keys[idx], h);
if (data != NULL)
data[idx] = key_slot->pdata;