[igt-dev] [PATCH i-g-t v26 02/35] lib/igt_list: igt_hlist implementation.
Grzegorzek, Dominik
dominik.grzegorzek at intel.com
Wed Mar 17 20:44:50 UTC 2021
On Wed, 2021-03-17 at 20:13 +0100, Zbigniew Kempczyński wrote:
> 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 at 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 at 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
To be clear, this is not an exact kernel's hash table implementation.
The one in the kernel is statically sized, but it was based on the one
in the kernel. As you both noticed it is based on a linked list which
is an exact kernel's port. I kept igt_map as simple as it was possible,
just to avoid surprises. I carried also some Valgrind tests as Chris
proposed in a previous iteration of that series, the results were
clean. This, and the fact it has already been tested in a vast number
of cases during the time the series was developed, makes me feel
certain about the implementation.
~Dominik
>
> > --Jason
> >
> > > --
> > > Zbigniew
> > > > On Wed, Mar 17, 2021 at 9:46 AM Zbigniew Kempczyński
> > > > <zbigniew.kempczynski at intel.com> wrote:
> > > > > From: Dominik Grzegorzek <dominik.grzegorzek at 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 at intel.com>
> > > > > Cc: Zbigniew Kempczyński <zbigniew.kempczynski at intel.com>
> > > > > Cc: Chris Wilson <chris at chris-wilson.co.uk>
> > > > > Acked-by: Daniel Vetter <daniel.vetter at 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
> > > > >
More information about the igt-dev
mailing list