From: Mark Wielaard <mark@klomp.org>
To: elfutils-devel@sourceware.org
Cc: Mark Wielaard <mark@klomp.org>
Subject: [PATCH] lib: Add documentation to explain concurrent htab resizing.
Date: Fri, 5 Aug 2022 17:20:30 +0200 [thread overview]
Message-ID: <20220805152030.31976-1-mark@klomp.org> (raw)
Document which lock is held by which thread and how moving the
htab data is coordinated.
Signed-off-by: Mark Wielaard <mark@klomp.org>
---
lib/ChangeLog | 8 ++++++++
lib/dynamicsizehash_concurrent.c | 26 ++++++++++++++++++++------
2 files changed, 28 insertions(+), 6 deletions(-)
diff --git a/lib/ChangeLog b/lib/ChangeLog
index 32dda566..36c3131f 100644
--- a/lib/ChangeLog
+++ b/lib/ChangeLog
@@ -1,3 +1,11 @@
+2022-08-05 Mark Wielaard <mark@klomp.org>
+
+ * dynamicsizehash_concurrent.c (resize_helper): Add documentation.
+ (resize_master): Renamed to...
+ (resize_coordinator): ...this. And add documentation.
+ (resize_worker): Add documentation.
+ (FIND): Add documentation.
+
2022-04-25 Mark Wielaard <mark@klomp.org>
* printversion.c (print_version): Update copyright year.
diff --git a/lib/dynamicsizehash_concurrent.c b/lib/dynamicsizehash_concurrent.c
index 4e2e2476..7c4fedfc 100644
--- a/lib/dynamicsizehash_concurrent.c
+++ b/lib/dynamicsizehash_concurrent.c
@@ -179,7 +179,8 @@ insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
#define CEIL(A, B) (((A) + (B) - 1) / (B))
/* Initializes records and copies the data from the old table.
- It can share work with other threads */
+ It can share work with other threads. Only the coordinator
+ will pass blocking as 1, other worker threads pass 0. */
static void resize_helper(NAME *htab, int blocking)
{
size_t num_old_blocks = CEIL(htab->old_size, MOVE_BLOCK_SIZE);
@@ -244,13 +245,18 @@ static void resize_helper(NAME *htab, int blocking)
atomic_fetch_add_explicit(&htab->num_moved_blocks, num_finished_blocks,
memory_order_release);
+ /* The coordinating thread will block here waiting for all blocks to
+ be moved. */
if (blocking)
while (atomic_load_explicit(&htab->num_moved_blocks,
memory_order_acquire) != num_old_blocks);
}
+/* Called by the main thread holding the htab->resize_rwl lock to
+ coordinate the moving of hash table data. Allocates the new hash
+ table and frees the old one when moving all data is done. */
static void
-resize_master(NAME *htab)
+resize_coordinator(NAME *htab)
{
htab->old_size = htab->size;
htab->old_table = htab->table;
@@ -290,6 +296,10 @@ resize_master(NAME *htab)
}
+/* Called by any thread that wants to do an insert or find operation
+ but notices it cannot get the htab->resize_rwl lock because another
+ thread is resizing the hash table. Try to help out by moving table
+ data if still necessary. */
static void
resize_worker(NAME *htab)
{
@@ -391,6 +401,8 @@ INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
for(;;)
{
+ /* If we cannot get the resize_rwl lock someone is resizing
+ hash table, try to help out by moving table data. */
while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
resize_worker(htab);
@@ -421,17 +433,17 @@ INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
memory_order_acquire,
memory_order_acquire))
{
- /* Master thread */
+ /* Main resizing thread, will coordinate moving data. */
pthread_rwlock_unlock(&htab->resize_rwl);
pthread_rwlock_wrlock(&htab->resize_rwl);
- resize_master(htab);
+ resize_coordinator(htab);
pthread_rwlock_unlock(&htab->resize_rwl);
}
else
{
- /* Worker thread */
+ /* Worker thread, will help moving data. */
pthread_rwlock_unlock(&htab->resize_rwl);
resize_worker(htab);
}
@@ -458,8 +470,10 @@ TYPE
name##_find
FIND(NAME) (NAME *htab, HASHTYPE hval)
{
+ /* If we cannot get the resize_rwl lock someone is resizing
+ the hash table, try to help out by moving table data. */
while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
- resize_worker(htab);
+ resize_worker(htab);
size_t idx;
--
2.18.4
reply other threads:[~2022-08-05 15:20 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20220805152030.31976-1-mark@klomp.org \
--to=mark@klomp.org \
--cc=elfutils-devel@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).