From patchwork Fri Aug 5 15:20:30 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mark Wielaard X-Patchwork-Id: 56568 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DD4093857C50 for ; Fri, 5 Aug 2022 15:20:39 +0000 (GMT) X-Original-To: elfutils-devel@sourceware.org Delivered-To: elfutils-devel@sourceware.org Received: from gnu.wildebeest.org (gnu.wildebeest.org [45.83.234.184]) by sourceware.org (Postfix) with ESMTPS id 4B7A3385829F for ; Fri, 5 Aug 2022 15:20:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4B7A3385829F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=klomp.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=klomp.org Received: from tarox.wildebeest.org (83-87-18-245.cable.dynamic.v4.ziggo.nl [83.87.18.245]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by gnu.wildebeest.org (Postfix) with ESMTPSA id D034C300B36D; Fri, 5 Aug 2022 17:20:31 +0200 (CEST) Received: by tarox.wildebeest.org (Postfix, from userid 1000) id 36ACD403B4BC; Fri, 5 Aug 2022 17:20:31 +0200 (CEST) From: Mark Wielaard To: elfutils-devel@sourceware.org Subject: [PATCH] lib: Add documentation to explain concurrent htab resizing. Date: Fri, 5 Aug 2022 17:20:30 +0200 Message-Id: <20220805152030.31976-1-mark@klomp.org> X-Mailer: git-send-email 2.18.4 X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, GIT_PATCH_0, JMQ_SPF_NEUTRAL, KAM_DMARC_STATUS, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: elfutils-devel@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Elfutils-devel mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , Cc: Mark Wielaard Errors-To: elfutils-devel-bounces+patchwork=sourceware.org@sourceware.org Sender: "Elfutils-devel" Document which lock is held by which thread and how moving the htab data is coordinated. Signed-off-by: Mark Wielaard --- 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 + + * 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 * 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;