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 <c...@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
