Re: [PATCH] lib/hash,lib/rcu: feature hidden key count in hash

["Abdullah Ömer Yamaç" <aomeryamac@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 13430 bytes --]

Sorry for the late reply. I understood what you mean. I will create only
the reclaim API for the hash library. Thanks for the explanation.

On Wed, Feb 28, 2024 at 5:51 PM Honnappa Nagarahalli <
Honnappa.Nagarahalli@arm.com> wrote:

>
>
> > On Feb 28, 2024, at 5:44 AM, Abdullah Ömer Yamaç <aomeryamac@gmail.com>
> wrote:
> >
> > While I was implementing the new API, I realized one issue, and it would
> be good to discuss it here. First of all rte_rcu_qsbr_dq_reclaim function
> checks the state of the qsbr values. It means that all threads should
> report the quiescent states. It conflicts with my aim.
> >
> > Let's think about below scenario:
> > Eight threads use a hash table and periodically report their quiescent
> states. One additional thread (main thread) periodically reports the hash
> size. I implemented the reclaim function in that thread. I mean, the main
> thread calls reclaim before the rte_hash_count.
> >
> > Here is the exceptional case that I couldn't retrieve the correct hash
> size:
> > Assume that 6 of 8 threads reported quiescent states and 2 of them are
> still working on some process and haven't reported quiescent states yet.
> The main thread calls reclaim functions every time, but elements in dq will
> not be freed because 2 of the worker threads haven't reported their states
> (especially if they are waiting for some packets). So, my first proposed
> method is more suitable for this case. Any idea?
> If 2 out of 8 threads have not reported their quiescent state then the
> elements that have not been acknowledged by those 2 threads cannot be
> reclaimed and cannot be allocated for further use. Using this you can
> calculate the most accurate number of entries in the hash table available
> for allocation.
>
> >
> > On Thu, Feb 22, 2024 at 7:44 PM Honnappa Nagarahalli <
> Honnappa.Nagarahalli@arm.com> wrote:
> >
> >
> > > On Feb 22, 2024, at 6:39 AM, Abdullah Ömer Yamaç <aomeryamac@gmail.com>
> wrote:
> > >
> > > As a final decision, I will add a new hash API that forces the
> reclaim. Is it ok for everyone?
> > Ack from my side
> >
> > >
> > > On Thu, Feb 22, 2024 at 5:37 AM Honnappa Nagarahalli <
> Honnappa.Nagarahalli@arm.com> wrote:
> > >
> > >
> > > > On Feb 21, 2024, at 3:51 PM, Abdullah Ömer Yamaç <
> aomeryamac@gmail.com> wrote:
> > > >
> > > >
> > > >
> > > > On Wed, Feb 21, 2024 at 6:24 AM Honnappa Nagarahalli <
> Honnappa.Nagarahalli@arm.com> wrote:
> > > >
> > > >
> > > > > On Feb 20, 2024, at 12:58 PM, Abdullah Ömer Yamaç <
> aomeryamac@gmail.com> wrote:
> > > > >
> > > > > I appreciate that you gave me suggestions and comments. I will
> make changes according to all your recommendations, but before that, I want
> to make everyone's minds clear. Then, I will apply modifications.
> > > > >
> > > > > On Tue, Feb 20, 2024 at 2:35 AM Honnappa Nagarahalli <
> Honnappa.Nagarahalli@arm.com> wrote:
> > > > >
> > > > >
> > > > > > On Feb 19, 2024, at 3:28 PM, Abdullah Ömer Yamaç <
> aomeryamac@gmail.com> wrote:
> > > > > >
> > > > > > Hello,
> > > > > >
> > > > > > Let me explain a use case;
> > > > > >
> > > > > > I have a hash table whose key value is IP addresses, and data
> (let's say the username of the IP) is related to the IP address. The key
> point is matching these data with flows. Flows are dynamic, and this hash
> table is dynamic, as well; both can change anytime. For example, when a
> flow starts, we look up the hash table with the corresponding IP and
> retrieve the username. We need to hold this username until the flow
> terminates, although we removed this IP key from the hash table
> (multithread). That's why we have RCU and defer queue is necessary for high
> performance. In my application, I need to know the number of IP-username
> entries. These numbers can be calculated by rte_hash_count - defer queue
> size.
> > > > > The entries in the defer queue are not reclaimed (there is a
> probability that all of them can be reclaimed) and hence they are not
> available for allocation. So, rte_hash_count - defer queue size might not
> give you the correct number you are expecting.
> > > > >
> > > > > Currently, there is no API in hash library that forces a reclaim.
> Does it makes sense to have an API that just does the reclaim (and returns
> the number of entries pending in the defer queue)? A call to rte_hash_count
> should provide the exact count you are looking for.
> > > > > You are right; no API in the hash library forces a reclaim. In my
> application, I periodically call rte_count to retrieve hash size, and this
> data is shown in my GUI. So that means I need to call regularly reclaim. I
> am trying to figure out which is better, calling reclaim or retrieving the
> defer queue size. Any comment about this?
> > > > Retrieving the defer queue size will be cheaper. However, calling
> the reclaim API will ensure the entries are freed hence providing an
> accurate number. Calling the reclaim API on an empty defer queue does not
> consume many cycles. If needed we could add a check for empty defer queue
> in the reclaim API and return early.
> > > >
> > > > I am also wondering if a reclaim API in hash library is needed. Why
> not call rte_rcu_qsbr_dq_reclaim API from the application?
> > > > The reason is simple. struct rte_hash *h is an internal structure
> and we cannot access the h->dq. So it is not possible to call reclaim.
> > > Ack. This will be just a wrapper around the rte_rcu_qsbr_dq_reclaim.
> > >
> > > >
> > > >
> > > > > >
> > > > > > I think if you need a non-blocking and multithreaded hash table,
> an RCU-enabled hash table is necessary. Also, this API is necessary if you
> need to get the actual matchable size.
> > > > > >
> > > > > >
> > > > > >
> > > > > >
> > > > > >
> > > > > > On Mon, Feb 19, 2024 at 8:36 PM Medvedkin, Vladimir <
> vladimir.medvedkin@intel.com> wrote:
> > > > > > Hi Abdullah,
> > > > > >
> > > > > > Could you please tell more about use cases where this API may be
> useful?
> > > > > >
> > > > > > >a new API to get the hidden key count in the hash table if the
> rcu qsbr is enabled
> > > > > >
> > > > > > Here in commit message and down below in doxygen comments, I
> think this
> > > > > > statement should be more specific because rcu can be created
> with
> > > > > > RTE_HASH_QSBR_MODE_SYNC mode i.e. without defer queue.
> > > > > >
> > > > > > Also, new API must be reflected in release notes
> > > > > >
> > > > > > On 07/02/2024 15:33, Abdullah Ömer Yamaç wrote:
> > > > > > > This patch introduce a new API to get the hidden key count in
> the hash
> > > > > > > table if the rcu qsbr is enabled. When using rte_hash_count
> with rcu
> > > > > > > qsbr enabled, it will return the number of elements that are
> not in the
> > > > > > > free queue. Unless rte_rcu_qsbr_dq_reclaim is called, the
> number of
> > > > > > > elements in the defer queue will not be counted and freed.
> Therefore I
> > > > > > > added a new API to get the number of hidden (defer queue)
> elements
> > > > > > > in the hash table. Then the user can calculate the total
> number of
> > > > > > > elements that are available in the hash table.
> > > > > > >
> > > > > > > Signed-off-by: Abdullah Ömer Yamaç <aomeryamac@gmail.com>
> > > > > > >
> > > > > > > ---
> > > > > > > Cc: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
> > > > > > > Cc: Yipeng Wang <yipeng1.wang@intel.com>
> > > > > > > Cc: Sameh Gobriel <sameh.gobriel@intel.com>
> > > > > > > Cc: Bruce Richardson <bruce.richardson@intel.com>
> > > > > > > Cc: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
> > > > > > > ---
> > > > > > >   lib/hash/rte_cuckoo_hash.c |  9 +++++++++
> > > > > > >   lib/hash/rte_hash.h        | 13 +++++++++++++
> > > > > > >   lib/hash/version.map       |  1 +
> > > > > > >   lib/rcu/rte_rcu_qsbr.c     |  8 ++++++++
> > > > > > >   lib/rcu/rte_rcu_qsbr.h     | 11 +++++++++++
> > > > > > >   lib/rcu/version.map        |  1 +
> > > > > > >   6 files changed, 43 insertions(+)
> > > > > > >
> > > > > > > diff --git a/lib/hash/rte_cuckoo_hash.c
> b/lib/hash/rte_cuckoo_hash.c
> > > > > > > index 70456754c4..3553f3efc7 100644
> > > > > > > --- a/lib/hash/rte_cuckoo_hash.c
> > > > > > > +++ b/lib/hash/rte_cuckoo_hash.c
> > > > > > > @@ -555,6 +555,15 @@ rte_hash_max_key_id(const struct rte_hash
> *h)
> > > > > > >               return h->entries;
> > > > > > >   }
> > > > > > >
> > > > > > > +int32_t
> > > > > > > +rte_hash_dq_count(const struct rte_hash *h)
> > > > > > > +{
> > > > > > > +     if (h->dq == NULL)
> > > > > > input arguments must be checked since this is a public API, the
> same is
> > > > > > true for rte_rcu_qsbr_dq_count()
> > > > > > > +             return -EINVAL;
> > > > > > why not just return 0?
> > > > > > > +
> > > > > > > +     return rte_rcu_qsbr_dq_count(h->dq);
> > > > > > > +}
> > > > > > > +
> > > > > > >   int32_t
> > > > > > >   rte_hash_count(const struct rte_hash *h)
> > > > > > >   {
> > > > > > > diff --git a/lib/hash/rte_hash.h b/lib/hash/rte_hash.h
> > > > > > > index 7ecc021111..8ea97e297d 100644
> > > > > > > --- a/lib/hash/rte_hash.h
> > > > > > > +++ b/lib/hash/rte_hash.h
> > > > > > > @@ -193,6 +193,19 @@ rte_hash_free(struct rte_hash *h);
> > > > > > >   void
> > > > > > >   rte_hash_reset(struct rte_hash *h);
> > > > > > >
> > > > > > > +
> > > > > > > +/**
> > > > > > > + * Return the number of records in the defer queue of the
> hash table
> > > > > > > + * if RCU is enabled.
> > > > > > > + * @param h
> > > > > > > + *  Hash table to query from
> > > > > > > + * @return
> > > > > > > + *   - -EINVAL if parameters are invalid
> > > > > > > + *   - A value indicating how many records were inserted in
> the table.
> > > > > > did you mean how many records are kept in defer queue?
> > > > > > > + */
> > > > > > > +int32_t
> > > > > > > +rte_hash_dq_count(const struct rte_hash *h);
> > > > > > > +
> > > > > > >   /**
> > > > > > >    * Return the number of keys in the hash table
> > > > > > >    * @param h
> > > > > > > diff --git a/lib/hash/version.map b/lib/hash/version.map
> > > > > > > index 6b2afebf6b..7f7b158cf1 100644
> > > > > > > --- a/lib/hash/version.map
> > > > > > > +++ b/lib/hash/version.map
> > > > > > > @@ -9,6 +9,7 @@ DPDK_24 {
> > > > > > >       rte_hash_add_key_with_hash;
> > > > > > >       rte_hash_add_key_with_hash_data;
> > > > > > >       rte_hash_count;
> > > > > > > +     rte_hash_dq_count;
> > > > > > new API must introduced as an experimental API. The same is true
> for
> > > > > > rte_rcu_qsbr_dq_count()
> > > > > > >       rte_hash_crc32_alg;
> > > > > > >       rte_hash_crc_set_alg;
> > > > > > >       rte_hash_create;
> > > > > > > diff --git a/lib/rcu/rte_rcu_qsbr.c b/lib/rcu/rte_rcu_qsbr.c
> > > > > > > index bd0b83be0c..89f8da4c4c 100644
> > > > > > > --- a/lib/rcu/rte_rcu_qsbr.c
> > > > > > > +++ b/lib/rcu/rte_rcu_qsbr.c
> > > > > > > @@ -450,6 +450,14 @@ rte_rcu_qsbr_dq_reclaim(struct
> rte_rcu_qsbr_dq *dq, unsigned int n,
> > > > > > >       return 0;
> > > > > > >   }
> > > > > > >
> > > > > > > +/**
> > > > > > > + * Return the number of entries in a defer queue.
> > > > > > > + */
> > > > > > > +unsigned int rte_rcu_qsbr_dq_count(struct rte_rcu_qsbr_dq *dq)
> > > > > > > +{
> > > > > Please validate dq here.
> > > > >
> > > > > > > +     return rte_ring_count(dq->r);
> > > > > > > +}
> > > > > > > +
> > > > > > >   /* Delete a defer queue. */
> > > > > > >   int
> > > > > > >   rte_rcu_qsbr_dq_delete(struct rte_rcu_qsbr_dq *dq)
> > > > > > > diff --git a/lib/rcu/rte_rcu_qsbr.h b/lib/rcu/rte_rcu_qsbr.h
> > > > > > > index 23c9f89805..ed5a590edd 100644
> > > > > > > --- a/lib/rcu/rte_rcu_qsbr.h
> > > > > > > +++ b/lib/rcu/rte_rcu_qsbr.h
> > > > > > > @@ -794,6 +794,17 @@ int
> > > > > > >   rte_rcu_qsbr_dq_reclaim(struct rte_rcu_qsbr_dq *dq, unsigned
> int n,
> > > > > > >       unsigned int *freed, unsigned int *pending, unsigned int
> *available);
> > > > > > >
> > > > > > > +/**
> > > > > > > + * Return the number of entries in a defer queue.
> > > > > > > + *
> > > > > > > + * @param dq
> > > > > > > + *   Defer queue.
> > > > > > > + * @return
> > > > > > > + *   The number of entries in the defer queue.
> > > > > > > + */
> > > > > > > +unsigned int
> > > > > > > +rte_rcu_qsbr_dq_count(struct rte_rcu_qsbr_dq *dq);
> > > > > Agree on the need for this API in RCU
> > > > >
> > > > > > > +
> > > > > > >   /**
> > > > > > >    * Delete a defer queue.
> > > > > > >    *
> > > > > > > diff --git a/lib/rcu/version.map b/lib/rcu/version.map
> > > > > > > index 982ffd59d9..f410ab41e7 100644
> > > > > > > --- a/lib/rcu/version.map
> > > > > > > +++ b/lib/rcu/version.map
> > > > > > > @@ -5,6 +5,7 @@ DPDK_24 {
> > > > > > >       rte_rcu_qsbr_dq_create;
> > > > > > >       rte_rcu_qsbr_dq_delete;
> > > > > > >       rte_rcu_qsbr_dq_enqueue;
> > > > > > > +     rte_rcu_qsbr_dq_count;
> > > > > > >       rte_rcu_qsbr_dq_reclaim;
> > > > > > >       rte_rcu_qsbr_dump;
> > > > > > >       rte_rcu_qsbr_get_memsize;
> > > > > >
> > > > > > --
> > > > > > Regards,
> > > > > > Vladimir
> > > > > >
> > > > >
> > > >
> > >
> >
>
>

[-- Attachment #2: Type: text/html, Size: 18760 bytes --]