Re: [Qemu-devel] [PATCH 08/10] qht: QEMU's fast, resizable and scalable Hash Table

["Emilio G. Cota" <cota@braap.org>]

Hi Alex,

I'm sending a v3 in a few minutes. I've addressed all your comments there,
so I won't duplicate them here; please find inline my replies to some
questions you raised.

On Fri, Apr 08, 2016 at 11:27:19 +0100, Alex Bennée wrote:
> Emilio G. Cota <cota@braap.org> writes:
(snip)
> > +/* call only when there are no readers left */
> > +void qht_destroy(struct qht *ht);
> > +
> 
> What's the rationale for making the caller responsible for locking here?

Instead of embedding a mutex in struct qht, I decided to let callers
handle that, since most likely write accesses will be part of
other updates that will require their own lock.

> Are we going to be protected by tb_lock in the MTTCG case rather than a
> finer grained locking inside the qht?

Yes, this is an example of the external-lock-that-other-updates-require
that I refer to above.

(snip)
> > +static inline
> > +void *__qht_lookup(struct qht_bucket *b, struct qht_bucket **far_bucket,
> > +                    int *pos, qht_lookup_func_t func, const void *userp,
> > +                    uint32_t hash)
> 
> Aside the inline is there any reason to keep such an implementation
> detail in the header. I certainly couldn't measure a difference after I
> moved them into qht.c.

I thought I measured a small perf. increase in the past with the inline.
But I couldn't replicate it so I've moved this to qht.c in v3.

(snip)
> > +static inline void *qht_lookup(struct qht *ht, qht_lookup_func_t func,
> > +                                const void *userp, uint32_t hash)
> > +{
> > +    struct qht_bucket *far_bucket = NULL;
> > +    struct qht_bucket *b;
> > +    struct qht_map *map;
> > +    uint32_t version;
> > +    int pos = 0;
> > +    void *ret;
> > +
> > +    map = atomic_read(&ht->map);
> > +    /* paired with smp_wmb() before setting ht->map */
> > +    smp_rmb();
> > +    b = qht_map_to_bucket(map, hash);
> > +
> > +    do {
> > +        version = seqlock_read_begin(&b->sequence);
> > +        ret = __qht_lookup(b, &far_bucket, &pos, func, userp, hash);
> > +    } while (seqlock_read_retry(&b->sequence, version));
> 
> OK I was slightly confused by this until I got further along. Maybe some
> comments in the qht_bucket structure to point out the seqlock is
> important when a bucket is at the head of the list.

There is a comment at the top of qht.c that says exactly that. I'd rather
not duplicate it elsewhere.

(snip)
> > +    for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
> > +        if (i == QHT_BUCKET_ENTRIES - 1) {
> > +            dest_hash = &orig->hashes[pos];
> > +            dest_p = &o rig->pointers[pos];
> > +        } else {
> > +            dest_hash = &head->hashes[i + 1];
> > +            dest_p = &head->pointers[i + 1];
> > +        }
> > +        hash = *dest_hash;
> > +        p = *dest_p;
> > +
> > +        atomic_set(dest_hash, head->hashes[i]);
> > +        atomic_set(dest_p, head->pointers[i]);
> > +
> > +        atomic_set(&head->hashes[i], hash);
> > +        atomic_set(&head->pointers[i], p);
> > +    }
> 
> So the bucket that has just swapped the MRU entry for an evicted entry
> gets placed after head. Is there a chance we end up just bouncing the
> head->next bucket each hit?

Given a certain sequence of hits, it could happen that head->next
gets updated every time, yes. This is of course unlikely, which is
why I think it's fine. An alternative would be to simply swap
head[last] with orig[pos], and leave it there. I can't measure
much of a difference between the two options.

(snip until end of patch)
> This looks good and I can see this being a useful utility function
> across QEMU. My main problem was following exactly what happens when
> entries are moved around for the MRU case. As users don't have to have a
> deep knowledge of the implementation details this isn't a major issue
> although a few more expansive comments or ASCII diagrams may help if
> you are feeling up to it ;-)

I added comments in v3 to address this.

Thanks a lot for your review!

		Emilio