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 01:02:53PM -0500, Jason Ekstrand wrote:
> On Wed, Mar 17, 2021 at 12:43 PM Zbigniew Kempczyński
> <zbigniew.kempczynski@intel.com> wrote:
> >
> > 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.
> 
> If this is, indeed, a port of the kernel hash table, then it's
> probably ok.  Not sure how that works out on licenses, but it should
> be correct.  If this has been freshly hand-rolled expressly for this
> purpose, then it makes me nervous.
> 
> > 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.
> 
> I'm less worried about threads, so long as it's locked, as I am about
> weird insert/remove patterns.  Most of the bugs I've had to fix in
> mesa were because certain patterns of insert/remove with the right
> hashes would cause it to blow up.  If most of what you do is just add
> a bunch of stuff without a lot of removal, they can be unlikely and
> hard to find.  That said, given that it's linked list based and not
> re-hash based, a lot of those corner cases are less likely than they
> were with the Mesa implementation.  Again, my primary concern is with
> a NEW hash table impl. :-)

I'm not sure I've understand you correctly - it is re-hash based (see
igt_map_extend()), and it grows if necessary. Works properly when you
don't forget about locking during operations (not only add, but find
too because it is not funny when someone is taking the rug from under
your feet).

All multiprocess/multithread tests in api_intel_allocator heavily
exercise insert/remove scenarios (open/close allocator just give 
you new handle inserted/removed from handles hash table so lack 
of consistency would be quickly fount imo).

--
Zbigniew

> 
> --Jason
> 
> > --
> > 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