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
