Re: [igt-dev] [PATCH i-g-t v26 02/35] lib/igt_list: igt_hlist implementation.

["Zbigniew Kempczyński" <zbigniew.kempczynski@intel.com>]

On Wed, Mar 17, 2021 at 11:43:38AM -0500, Jason Ekstrand wrote:
> Would it be better to pull the hash table implementation from Mesa?
> Or use https://cgit.freedesktop.org/~anholt/hash_table/ which should
> be identical, though it may be a bit out-of-date.  I've poured enough
> hours of my life into finding and fixing the bugs in the Mesa hash
> table that IGT rolling its own doesn't really fill me with happy
> feelings.
> 
> --Jason

I'm not going to be a devil advocate, I'll just ask Dominik how 
confident is he about that implementation, at least we can provide
some stress test with multithreading scenarios.

He's ported kernel hashtable so if he didn't introduce a non obvious
bug it should work.

Regarding Eric implementation - we need to adopt that implementation
to at least rename to igt_* and fix the code which is using. 
Should take few days max. 

If you'll take a look to tests api_intel_allocator@two-level-inception
you'll see we're stress testing that hashtable much from many
processes / threads and we see no problem with losing data coherency
in the map.

--
Zbigniew
> 
> On Wed, Mar 17, 2021 at 9:46 AM Zbigniew Kempczyński
> <zbigniew.kempczynski@intel.com> wrote:
> >
> > From: Dominik Grzegorzek <dominik.grzegorzek@intel.com>
> >
> > Double linked lists with a single pointer list head implementation,
> > based on similar in the kernel.
> >
> > Signed-off-by: Dominik Grzegorzek <dominik.grzegorzek@intel.com>
> > Cc: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>
> > Cc: Chris Wilson <chris@chris-wilson.co.uk>
> > Acked-by: Daniel Vetter <daniel.vetter@ffwll.ch>
> > ---
> >  lib/igt_list.c | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++
> >  lib/igt_list.h | 50 +++++++++++++++++++++++++++++++++--
> >  2 files changed, 120 insertions(+), 2 deletions(-)
> >
> > diff --git a/lib/igt_list.c b/lib/igt_list.c
> > index 37ae139c4..43200f9b3 100644
> > --- a/lib/igt_list.c
> > +++ b/lib/igt_list.c
> > @@ -22,6 +22,7 @@
> >   *
> >   */
> >
> > +#include "assert.h"
> >  #include "igt_list.h"
> >
> >  void IGT_INIT_LIST_HEAD(struct igt_list_head *list)
> > @@ -81,3 +82,74 @@ bool igt_list_empty(const struct igt_list_head *head)
> >  {
> >         return head->next == head;
> >  }
> > +
> > +void igt_hlist_init(struct igt_hlist_node *h)
> > +{
> > +       h->next = NULL;
> > +       h->pprev = NULL;
> > +}
> > +
> > +int igt_hlist_unhashed(const struct igt_hlist_node *h)
> > +{
> > +       return !h->pprev;
> > +}
> > +
> > +int igt_hlist_empty(const struct igt_hlist_head *h)
> > +{
> > +       return !h->first;
> > +}
> > +
> > +static void __igt_hlist_del(struct igt_hlist_node *n)
> > +{
> > +       struct igt_hlist_node *next = n->next;
> > +       struct igt_hlist_node **pprev = n->pprev;
> > +
> > +       *pprev = next;
> > +       if (next)
> > +               next->pprev = pprev;
> > +}
> > +
> > +void igt_hlist_del(struct igt_hlist_node *n)
> > +{
> > +       __igt_hlist_del(n);
> > +       n->next = NULL;
> > +       n->pprev = NULL;
> > +}
> > +
> > +void igt_hlist_del_init(struct igt_hlist_node *n)
> > +{
> > +       if (!igt_hlist_unhashed(n)) {
> > +               __igt_hlist_del(n);
> > +               igt_hlist_init(n);
> > +       }
> > +}
> > +
> > +void igt_hlist_add_head(struct igt_hlist_node *n, struct igt_hlist_head *h)
> > +{
> > +       struct igt_hlist_node *first = h->first;
> > +
> > +       n->next = first;
> > +       if (first)
> > +               first->pprev = &n->next;
> > +       h->first = n;
> > +       n->pprev = &h->first;
> > +}
> > +
> > +void igt_hlist_add_before(struct igt_hlist_node *n, struct igt_hlist_node *next)
> > +{
> > +       assert(next);
> > +       n->pprev = next->pprev;
> > +       n->next = next;
> > +       next->pprev = &n->next;
> > +       *(n->pprev) = n;
> > +}
> > +
> > +void igt_hlist_add_behind(struct igt_hlist_node *n, struct igt_hlist_node *prev)
> > +{
> > +       n->next = prev->next;
> > +       prev->next = n;
> > +       n->pprev = &prev->next;
> > +
> > +       if (n->next)
> > +               n->next->pprev  = &n->next;
> > +}
> > diff --git a/lib/igt_list.h b/lib/igt_list.h
> > index cc93d7a0d..78e761e05 100644
> > --- a/lib/igt_list.h
> > +++ b/lib/igt_list.h
> > @@ -40,6 +40,10 @@
> >   * igt_list is a doubly-linked list where an instance of igt_list_head is a
> >   * head sentinel and has to be initialized.
> >   *
> > + * igt_hist is also an double linked lists, but with a single pointer list head.
> > + * Mostly useful for hash tables where the two pointer list head is
> > + * too wasteful. You lose the ability to access the tail in O(1).
> > + *
> >   * Example usage:
> >   *
> >   * |[<!-- language="C" -->
> > @@ -71,6 +75,13 @@ struct igt_list_head {
> >         struct igt_list_head *next;
> >  };
> >
> > +struct igt_hlist_head {
> > +       struct igt_hlist_node *first;
> > +};
> > +
> > +struct igt_hlist_node {
> > +       struct igt_hlist_node *next, **pprev;
> > +};
> >
> >  void IGT_INIT_LIST_HEAD(struct igt_list_head *head);
> >  void igt_list_add(struct igt_list_head *elem, struct igt_list_head *head);
> > @@ -81,6 +92,17 @@ void igt_list_move_tail(struct igt_list_head *elem, struct igt_list_head *list);
> >  int igt_list_length(const struct igt_list_head *head);
> >  bool igt_list_empty(const struct igt_list_head *head);
> >
> > +void igt_hlist_init(struct igt_hlist_node *h);
> > +int igt_hlist_unhashed(const struct igt_hlist_node *h);
> > +int igt_hlist_empty(const struct igt_hlist_head *h);
> > +void igt_hlist_del(struct igt_hlist_node *n);
> > +void igt_hlist_del_init(struct igt_hlist_node *n);
> > +void igt_hlist_add_head(struct igt_hlist_node *n, struct igt_hlist_head *h);
> > +void igt_hlist_add_before(struct igt_hlist_node *n,
> > +                         struct igt_hlist_node *next);
> > +void igt_hlist_add_behind(struct igt_hlist_node *n,
> > +                         struct igt_hlist_node *prev);
> > +
> >  #define igt_container_of(ptr, sample, member)                          \
> >         (__typeof__(sample))((char *)(ptr) -                            \
> >                                 offsetof(__typeof__(*sample), member))
> > @@ -96,9 +118,10 @@ bool igt_list_empty(const struct igt_list_head *head);
> >   * Safe against removel of the *current* list element. To achive this it
> >   * requires an extra helper variable `tmp` with the same type as `pos`.
> >   */
> > -#define igt_list_for_each_entry_safe(pos, tmp, head, member)                   \
> > +
> > +#define igt_list_for_each_entry_safe(pos, tmp, head, member)           \
> >         for (pos = igt_container_of((head)->next, pos, member),         \
> > -            tmp = igt_container_of((pos)->member.next, tmp, member);   \
> > +            tmp = igt_container_of((pos)->member.next, tmp, member);   \
> >              &pos->member != (head);                                    \
> >              pos = tmp,                                                 \
> >              tmp = igt_container_of((pos)->member.next, tmp, member))
> > @@ -108,6 +131,27 @@ bool igt_list_empty(const struct igt_list_head *head);
> >              &pos->member != (head);                                    \
> >              pos = igt_container_of((pos)->member.prev, pos, member))
> >
> > +#define igt_list_for_each_entry_safe_reverse(pos, tmp, head, member)           \
> > +       for (pos = igt_container_of((head)->prev, pos, member),         \
> > +            tmp = igt_container_of((pos)->member.prev, tmp, member);   \
> > +            &pos->member != (head);                                    \
> > +            pos = tmp,                                                 \
> > +            tmp = igt_container_of((pos)->member.prev, tmp, member))
> > +
> > +#define igt_hlist_entry_safe(ptr, sample, member) \
> > +       ({ typeof(ptr) ____ptr = (ptr); \
> > +          ____ptr ? igt_container_of(____ptr, sample, member) : NULL; \
> > +       })
> > +
> > +#define igt_hlist_for_each_entry(pos, head, member)                    \
> > +       for (pos = igt_hlist_entry_safe((head)->first, pos, member);    \
> > +            pos;                                                       \
> > +            pos = igt_hlist_entry_safe((pos)->member.next, pos, member))
> > +
> > +#define igt_hlist_for_each_entry_safe(pos, n, head, member)            \
> > +       for (pos = igt_hlist_entry_safe((head)->first, pos, member);    \
> > +            pos && ({ n = pos->member.next; 1; });                     \
> > +            pos = igt_hlist_entry_safe(n, pos, member))
> >
> >  /* IGT custom helpers */
> >
> > @@ -127,4 +171,6 @@ bool igt_list_empty(const struct igt_list_head *head);
> >  #define igt_list_last_entry(head, type, member) \
> >         igt_container_of((head)->prev, (type), member)
> >
> > +#define IGT_INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
> > +
> >  #endif /* IGT_LIST_H */
> > --
> > 2.26.0
> >
_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev