Sergey Fedorov <serge.f...@gmail.com> writes:
> On 25/05/16 04:13, Emilio G. Cota wrote:
>> diff --git a/include/qemu/qht.h b/include/qemu/qht.h
>> new file mode 100644
>> index 0000000..aec60aa
>> --- /dev/null
>> +++ b/include/qemu/qht.h
>> @@ -0,0 +1,183 @@
> (snip)
>> +/**
>> + * qht_init - Initialize a QHT
>> + * @ht: QHT to be initialized
>> + * @n_elems: number of entries the hash table should be optimized for.
>> + * @mode: bitmask with OR'ed QHT_MODE_*
>> + */
>> +void qht_init(struct qht *ht, size_t n_elems, unsigned int mode);
>
> First of all, thank you for spending your time on the documentation of
> the API!
>
> I was just wondering if it could be worthwhile to pass a hash function
> when initializing a QHT. Then we could have variants of qht_insert(),
> qht_remove() and qht_lookup() which does not require a computed hash
> value but call the function by themselves. This could make sense since a
> hash value passed the the functions should always be exactly the same
> for the same object.
Wouldn't this be for an expansion of the API when we actually have
something that would use it that way?
>
> (snip)
>> +/**
>> + * 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()?
>
>> + *
>> + * Returns true on success.
>> + * Returns false if the @p-@hash pair was not found.
>> + */
>> +bool qht_remove(struct qht *ht, const void *p, uint32_t hash);
>> +
> (snip)
>> diff --git a/util/qht.c b/util/qht.c
>> new file mode 100644
>> index 0000000..ca5a620
>> --- /dev/null
>> +++ b/util/qht.c
>> @@ -0,0 +1,837 @@
> (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?
>
>> +
>> +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.
>
> (snip)
>> +
>> +/* call with head->lock held */
>> +static bool qht_insert__locked(struct qht *ht, struct qht_map *map,
>> + struct qht_bucket *head, void *p, uint32_t
>> hash,
>> + bool *needs_resize)
>> +{
>> + struct qht_bucket *b = head;
>> + struct qht_bucket *prev = NULL;
>> + struct qht_bucket *new = NULL;
>> + int i;
>> +
>> + for (;;) {
>> + if (b == NULL) {
>> + b = qemu_memalign(QHT_BUCKET_ALIGN, sizeof(*b));
>> + memset(b, 0, sizeof(*b));
>> + new = b;
>> + atomic_inc(&map->n_added_buckets);
>> + if (unlikely(qht_map_needs_resize(map)) && needs_resize) {
>> + *needs_resize = true;
>> + }
>> + }
>> + for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
>> + if (b->pointers[i]) {
>> + if (unlikely(b->pointers[i] == p)) {
>> + return false;
>> + }
>> + continue;
>> + }
>> + /* found an empty key: acquire the seqlock and write */
>> + seqlock_write_begin(&head->sequence);
>> + if (new) {
>> + atomic_rcu_set(&prev->next, b);
>> + }
>> + b->hashes[i] = hash;
>> + atomic_set(&b->pointers[i], p);
>> + seqlock_write_end(&head->sequence);
>> + return true;
>> + }
>> + prev = b;
>> + b = b->next;
>> + }
>> +}
>
> Here is my attempt:
>
> static bool qht_insert__locked(struct qht *ht, struct qht_map
> *map,
> struct qht_bucket *head, void *p,
> uint32_t hash,
> bool
> *needs_resize)
> {
>
> struct qht_bucket **bpp = &head,
> *new;
> int i =
> 0;
>
>
> do
> {
> while (i < QHT_BUCKET_ENTRIES)
> {
> if ((*bpp)->pointers[i])
> {
> if (unlikely((*bpp)->pointers[i] == p))
> {
> return
> false;
>
> }
>
> i++;
>
> continue;
>
> }
> goto
> found;
>
> }
> bpp =
> &(*bpp)->next;
> i =
> 0;
> } while
> (*bpp);
>
>
> new = qemu_memalign(QHT_BUCKET_ALIGN,
> sizeof(*new));
> memset(new, 0,
> sizeof(*new));
> atomic_rcu_set(bpp,
> new);
>
> atomic_inc(&map->n_added_buckets);
> if (unlikely(qht_map_needs_resize(map)) && needs_resize)
> {
> *needs_resize =
> true;
>
> }
> found:
>
> /* found an empty key: acquire the seqlock and write
> */
>
> seqlock_write_begin(&head->sequence);
> (*bpp)->hashes[i] =
> hash;
> atomic_set(&(*bpp)->pointers[i],
> p);
>
> seqlock_write_end(&head->sequence);
> return
> true;
> }
>
>
> Feel free to use it as you wish.
>
>>
> (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.
>
>> + return qht_entry_move(orig, pos, prev, QHT_BUCKET_ENTRIES - 1);
>> + }
>> + prev = b;
>> + b = b->next;
>> + } while (b);
>> + /* no free entries other than orig[pos], so swap it with the last one */
>> + qht_entry_move(orig, pos, prev, QHT_BUCKET_ENTRIES - 1);
>> +}
>> +
>> +/* 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.
>
>> + seqlock_write_end(&head->sequence);
>> + return true;
>> + }
>> + }
>> + b = b->next;
>> + } while (b);
>> + return false;
>> +}
> (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().
>
>> +}
>
> Kind regards,
> Sergey
--
Alex Bennée
