All of lore.kernel.org
 help / color / mirror / Atom feed
* Question regarding hash_resize
@ 2019-01-07 13:49 Junchang Wang
  2019-01-07 18:33 ` Paul E. McKenney
  0 siblings, 1 reply; 23+ messages in thread
From: Junchang Wang @ 2019-01-07 13:49 UTC (permalink / raw)
  To: perfbook

Hi all,

I'm reading hash_resize recently, and have a few questions regarding
this algorithm. Please take a look if you have time. Any suggestions
are warmly welcomed.

=== Question 1 ===
In hash_resize.c : hashtab_lock_mod
186         if (b > READ_ONCE(htp->ht_resize_cur)) {
187                 lsp->hbp[1] = NULL;
188                 return;
189         }
190         htp = rcu_dereference(htp->ht_new);

It seems we are missing a barrier (e.g., smp_mb) in between lines 189
and 190, because neither READ_ONCE() nor rcu_dereference() can prevent
compilers and hardware from reordering the two unrelated variables,
ht_resize_cur and ht_new. Is my understanding correct?

=== Question 2 ===
In hash_resize.c, each time an updater wants to access a bucket, the
updater must first acquire the bucket's lock (htb_lock), preventing
other updaters accessing the same bucket concurrently. This approach
is OK if the linked list of a bucket is relatively short, but for a
larger system where linked lists are long enough and the
perftest_resize thread is running simultaneously, it could become a
potential performance bottleneck. One naive solution is to allow
multiple updaters to access the same bucket, only if they don't
operate on the same item of the list of this bucket. I wonder if there
are any existing works or discussions on this topic?

=== Question 3 ===
Chapter Data Structures also discusses other resizable hash tables,
namely "Resizable, scalable, concurrent hash tables via relativistic
programming" from Josh Triplett, which can save memory footprint by
using a single pair of pointers. But my understanding is that
perftest_resize.c is unique in that it allows you to rebuild the hash
table by utilizing a different hash function, which could be very
useful in practice (e.g., to prevent DDoS attack). Other solutions do
not share this property. Is my understanding correct? Did I miss any
discussions on this topic in perfbook?

=== Question 4 ===
In the current implementation of hash_resize.c, the perftest_resize
could block an updater, and vice versa. It seems this is not what we
expected. Ideally, they should be allowed to run concurrently, or at
least the perftest_resize thread should have lower priority and
updaters should never be blocked by the perftest_resize thread. Is
that right? I'm very interested in helping improve. Please let me know
if you have any suggestions.

Thanks,
--Junchang


^ permalink raw reply	[flat|nested] 23+ messages in thread

end of thread, other threads:[~2019-01-18 18:34 UTC | newest]

Thread overview: 23+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2019-01-07 13:49 Question regarding hash_resize Junchang Wang
2019-01-07 18:33 ` Paul E. McKenney
2019-01-07 22:54   ` Akira Yokosawa
2019-01-07 23:06     ` Akira Yokosawa
2019-01-07 23:48       ` Paul E. McKenney
2019-01-08 15:18         ` Akira Yokosawa
2019-01-08 15:32           ` Paul E. McKenney
2019-01-08  1:56       ` Junchang Wang
2019-01-08 15:28         ` Paul E. McKenney
2019-01-08 15:35           ` Akira Yokosawa
2019-01-08 18:39             ` Paul E. McKenney
2019-01-08 22:16               ` Akira Yokosawa
2019-01-09  0:19                 ` Paul E. McKenney
2019-01-09  2:59                   ` Paul E. McKenney
2019-01-11  4:08                     ` Paul E. McKenney
2019-01-11 14:25                       ` Akira Yokosawa
2019-01-11 15:43                         ` Paul E. McKenney
2019-01-11 22:56                           ` Akira Yokosawa
2019-01-11 23:28                             ` Paul E. McKenney
2019-01-07 23:13     ` Paul E. McKenney
2019-01-07 23:33       ` Paul E. McKenney
2019-01-18 14:32   ` Junchang Wang
2019-01-18 18:34     ` Paul E. McKenney

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.