[igt-dev] [PATCH i-g-t v26 02/35] lib/igt_list: igt_hlist implementation.
Grzegorzek, Dominik
dominik.grzegorzek at intel.com
Thu Mar 18 13:26:40 UTC 2021
On Wed, 2021-03-17 at 21:44 +0100, Dominik Grzegorzek wrote:
> 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
After consideration I will take the implementation Jason sent.
This way will be much cleaner. Just ommit igt_map in review.
~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