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

[Emilio G. Cota]

On Sun, May 29, 2016 at 22:52:27 +0300, Sergey Fedorov wrote:
> > +/**
> > + * qht_remove - remove a pointer from the hash table
> > + * @ht: QHT to remove from
> > + * @p: pointer to be removed
> > + * @hash: hash corresponding to @p
> > + *
> > + * Attempting to remove a NULL @p is a bug.
> > + *
> > + * Just-removed @p pointers cannot be immediately freed; they need to 
> > remain
> > + * valid until the end of the RCU grace period in which qht_remove() is 
> > called.
> > + * This guarantees that concurrent lookups will always compare against 
> > valid
> > + * data.
> 
> Mention rcu_call1()/call_rcu()/g_free_rcu()?

Probably using 'see also:' for non-qht functions is a little too much.
The pointer to RCU should be enough, me thinks.

> (snip)
> > +/* trigger a resize when n_added_buckets > n_buckets / div */
> > +#define QHT_NR_ADDED_BUCKETS_THRESHOLD_DIV 8
> 
> Just out of curiosity, how did you get this number?

Good question. Tested what gave the best performance for the ARM
bootup test :-) It matched the performance of the old behavior,
that was, to double the size when n_entries reached
n_buckets * QHT_BUCKET_ENTRIES / 2.

> > +
> > +static void qht_do_resize(struct qht *ht, struct qht_map *new);
> > +static void qht_grow_maybe(struct qht *ht);
> 
> qht_grow_maybe() is used just once. Please consider reordering of
> definitions and removing this forward declaration.

Done.

(snip)
> > +/*
> > + * Find the last valid entry in @head, and swap it with @orig[pos], which 
> > has
> > + * just been invalidated.
> > + */
> > +static inline void qht_bucket_fill_hole(struct qht_bucket *orig, int pos)
> > +{
> > +    struct qht_bucket *b = orig;
> > +    struct qht_bucket *prev = NULL;
> > +    int i;
> > +
> > +    if (qht_entry_is_last(orig, pos)) {
> > +        orig->hashes[pos] = 0;
> > +        atomic_set(&orig->pointers[pos], NULL);
> > +        return;
> > +    }
> > +    do {
> > +        for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
> > +            if (b->pointers[i]) {
> > +                continue;
> > +            }
> > +            if (i > 0) {
> > +                return qht_entry_move(orig, pos, b, i - 1);
> > +            }
> > +            qht_debug_assert(prev);
> 
> 'prev' can be NULL if this is the first iteration.

How can prev be NULL here and that not be a bug? NULL here would
mean there was a hole before orig[pos]. Or orig[pos] was
NULL, which is also a bug.

> > +
> > +/* call with b->lock held */
> > +static inline
> > +bool qht_remove__locked(struct qht_map *map, struct qht_bucket *head,
> > +                        const void *p, uint32_t hash)
> > +{
> > +    struct qht_bucket *b = head;
> > +    int i;
> > +
> > +    do {
> > +        for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
> > +            void *q = b->pointers[i];
> > +
> > +            if (unlikely(q == NULL)) {
> > +                return false;
> > +            }
> > +            if (q == p) {
> > +                qht_debug_assert(b->hashes[i] == hash);
> > +                seqlock_write_begin(&head->sequence);
> > +                qht_bucket_fill_hole(b, i);
> 
> "Fill hole" doesn't correspond to the function's new job since there's
> no hole. "Remove entry" would make more sense, I think.

Changed.

> (snip)
> > +/*
> > + * Call with ht->lock and all bucket locks held.
> > + *
> > + * Creating the @new map here would add unnecessary delay while all the 
> > locks
> > + * are held--holding up the bucket locks is particularly bad, since no 
> > writes
> > + * can occur while these are held. Thus, we let callers create the new map,
> > + * hopefully without the bucket locks held.
> > + */
> > +static void qht_do_resize(struct qht *ht, struct qht_map *new)
> > +{
> > +    struct qht_map *old;
> > +
> > +    old = ht->map;
> > +    g_assert_cmpuint(new->n_buckets, !=, old->n_buckets);
> > +
> > +    qht_map_iter__all_locked(ht, old, qht_map_copy, new);
> > +    qht_map_debug__all_locked(new);
> > +
> > +    atomic_rcu_set(&ht->map, new);
> > +    call_rcu1(&old->rcu, qht_map_reclaim);
> 
> call_rcu() macro is a more convenient way to do this and you wouldn't
> need qht_map_reclaim().

True. Originally the RCU struct wasn't at the head, then I changed
it to please valgrind. Changed now.

Thanks,

                Emilio