From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:54011) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1b8mrh-0000q7-5g for qemu-devel@nongnu.org; Fri, 03 Jun 2016 07:02:13 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1b8mra-0007wt-7W for qemu-devel@nongnu.org; Fri, 03 Jun 2016 07:02:08 -0400 Received: from out2-smtp.messagingengine.com ([66.111.4.26]:51235) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1b8mrX-0007vZ-Tj for qemu-devel@nongnu.org; Fri, 03 Jun 2016 07:02:02 -0400 Date: Fri, 3 Jun 2016 07:01:49 -0400 From: "Emilio G. Cota" Message-ID: <20160603110149.GB5251@flamenco> References: <1464138802-23503-1-git-send-email-cota@braap.org> <1464138802-23503-11-git-send-email-cota@braap.org> <574B487B.5080200@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <574B487B.5080200@gmail.com> Subject: Re: [Qemu-devel] [PATCH v6 10/15] qht: QEMU's fast, resizable and scalable Hash Table List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Sergey Fedorov Cc: QEMU Developers , MTTCG Devel , Alex =?iso-8859-1?Q?Benn=E9e?= , Paolo Bonzini , Richard Henderson 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