Re: [Qemu-devel] [PATCH v3 01/11] util/qht: Document memory ordering assumptions

[Paolo Bonzini]

On 15/07/2016 14:37, Sergey Fedorov wrote:
> On 13/07/16 14:13, Paolo Bonzini wrote:
>> diff --git a/include/qemu/qht.h b/include/qemu/qht.h
>> index 70bfc68..f4f1d55 100644
>> --- a/include/qemu/qht.h
>> +++ b/include/qemu/qht.h
>> @@ -69,6 +69,9 @@ void qht_destroy(struct qht *ht);
>>   * Attempting to insert a NULL @p is a bug.
>>   * Inserting the same pointer @p with different @hash values is a bug.
>>   *
>> + * In case of successful operation, smp_wmb() is implied before the pointer 
>> is
>> + * inserted into the hash table.
>> + *
>>   * Returns true on sucess.
>>   * Returns false if the @address@hidden pair already exists in the hash 
>> table.
>>   */
>> @@ -83,6 +86,8 @@ bool qht_insert(struct qht *ht, void *p, uint32_t hash);
>>   *
>>   * Needs to be called under an RCU read-critical section.
>>   *
>> + * smp_read_barrier_depends() is implied before the call to @func.
>> + *
>>   * The user-provided @func compares pointers in QHT against @userp.
>>   * If the function returns true, a match has been found.
>>   *
>> @@ -105,6 +110,10 @@ void *qht_lookup(struct qht *ht, qht_lookup_func_t 
>> func, const void *userp,
>>   * This guarantees that concurrent lookups will always compare against valid
>>   * data.
>>   *
>> + * In case of successful operation, a smp_wmb() barrier is implied before 
>> and
>> + * after the pointer is removed from the hash table.  In other words,
>> + * a successful qht_remove acts as a bidirectional write barrier.
>> + *
> 
> I understand why an implied wmb can be expected after the entry is
> removed: so that the caller can trash the contents of the object
> removed. However that would require double-check on lookup side to make
> sure the entry hadn't been removed after the first lookup (something
> like seqlock read side). But I have no idea why we might like to promise
> wmb before the removal. Could you please share your point regarding this?

The reasoning was to make qht_remove() "look to be ordered" with respect
to writes.  So anything after remove wouldn't bleed into it, nor would
anything before.

In the case of this series, it would let you remove the smp_wmb() after
tb_mark_invalid().  However, it's also okay to only handle qht_insert()
and qht_lookup(), and keep the memory barrier after the TB is marked
invalid (though it is unnecessary).

Paolo

> As of qht_insert() and qht_lookup(), I agree and this is enough
> guarantees for the series.
> 
> Thanks,
> Sergey
> 
>>   * Returns true on success.
>>   * Returns false if the @address@hidden pair was not found.
>>   */
>> diff --git a/util/qht.c b/util/qht.c
>> index 40d6e21..d38948e 100644
>> --- a/util/qht.c
>> +++ b/util/qht.c
>> @@ -445,7 +445,11 @@ void *qht_do_lookup(struct qht_bucket *head, 
>> qht_lookup_func_t func,
>>      do {
>>          for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
>>              if (b->hashes[i] == hash) {
>> -                void *p = atomic_read(&b->pointers[i]);
>> +                /* The pointer is dereferenced before seqlock_read_retry,
>> +                 * so (unlike qht_insert__locked) we need to use
>> +                 * atomic_rcu_read here.
>> +                 */
>> +                void *p = atomic_rcu_read(&b->pointers[i]);
>>  
>>                  if (likely(p) && likely(func(p, userp))) {
>>                      return p;
>> @@ -535,6 +539,7 @@ static bool qht_insert__locked(struct qht *ht, struct 
>> qht_map *map,
>>          atomic_rcu_set(&prev->next, b);
>>      }
>>      b->hashes[i] = hash;
>> +    /* smp_wmb() implicit in seqlock_write_begin.  */
>>      atomic_set(&b->pointers[i], p);
>>      seqlock_write_end(&head->sequence);
>>      return true;
>> @@ -659,6 +664,9 @@ bool qht_remove__locked(struct qht_map *map, struct 
>> qht_bucket *head,
>>              }
>>              if (q == p) {
>>                  qht_debug_assert(b->hashes[i] == hash);
>> +                /* seqlock_write_begin and seqlock_write_end provide write
>> +                 * memory barrier semantics to callers of qht_remove.
>> +                 */
>>                  seqlock_write_begin(&head->sequence);
>>                  qht_bucket_remove_entry(b, i);
>>                  seqlock_write_end(&head->sequence);
>