From patchwork Sat Feb 22 08:50:02 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Stefan Hajnoczi X-Patchwork-Id: 11397945 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 6626892A for ; Sat, 22 Feb 2020 08:54:37 +0000 (UTC) Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 2CE1A2071E for ; Sat, 22 Feb 2020 08:54:37 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="ZVeSmKOm" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 2CE1A2071E Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Received: from localhost ([::1]:40378 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1j5QYW-0002ny-Ak for patchwork-qemu-devel@patchwork.kernel.org; Sat, 22 Feb 2020 03:54:36 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:38065) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1j5QVA-0004he-MA for qemu-devel@nongnu.org; Sat, 22 Feb 2020 03:51:10 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1j5QV9-0007vj-AL for qemu-devel@nongnu.org; Sat, 22 Feb 2020 03:51:08 -0500 Received: from us-smtp-delivery-1.mimecast.com ([207.211.31.120]:55861 helo=us-smtp-1.mimecast.com) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1j5QV8-0007vO-PS for qemu-devel@nongnu.org; Sat, 22 Feb 2020 03:51:07 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1582361466; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=LfrkMKGEFDW++p9aI+7sOirpwZO/Gek1D2YqhVyWK4U=; b=ZVeSmKOm4VQpWx5zx0fdNASllNYhmkizHWKCAbal0nIVfLcucG5UWemLAVnUnM7dLwajL1 etrh1UZ3jW49wmmU9RbogTTPppCd+kJP98lZtgU/hIlhN4oHGC1J7880FHmP45oiGdJzca iARUK2LTY/gPyMZEbt7ujbGydVYyNb4= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-179-X0bkB8-FPWWy8FbA3lGBkg-1; Sat, 22 Feb 2020 03:51:03 -0500 X-MC-Unique: X0bkB8-FPWWy8FbA3lGBkg-1 Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.phx2.redhat.com [10.5.11.23]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 6981418A6EC4; Sat, 22 Feb 2020 08:51:02 +0000 (UTC) Received: from localhost (ovpn-116-74.ams2.redhat.com [10.36.116.74]) by smtp.corp.redhat.com (Postfix) with ESMTP id A63B019C7F; Sat, 22 Feb 2020 08:50:50 +0000 (UTC) From: Stefan Hajnoczi To: qemu-devel@nongnu.org Subject: [PULL 03/31] rcu_queue: add QSLIST functions Date: Sat, 22 Feb 2020 08:50:02 +0000 Message-Id: <20200222085030.1760640-4-stefanha@redhat.com> In-Reply-To: <20200222085030.1760640-1-stefanha@redhat.com> References: <20200222085030.1760640-1-stefanha@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 on 10.5.11.23 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 207.211.31.120 X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Kevin Wolf , Peter Maydell , Thomas Huth , Eduardo Habkost , qemu-block@nongnu.org, "Michael S. Tsirkin" , Laurent Vivier , Max Reitz , Alexander Bulekov , Bandan Das , Stefan Hajnoczi , =?utf-8?q?Marc-Andr=C3=A9_Lureau?= , Paolo Bonzini , Fam Zheng , Richard Henderson Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" From: Paolo Bonzini QSLIST is the only family of lists for which we do not have RCU-friendly accessors, add them. Signed-off-by: Paolo Bonzini Reviewed-by: Stefan Hajnoczi Message-id: 20200220103828.24525-1-pbonzini@redhat.com Signed-off-by: Stefan Hajnoczi --- include/qemu/queue.h | 15 +++++++++++-- include/qemu/rcu_queue.h | 47 ++++++++++++++++++++++++++++++++++++++++ tests/Makefile.include | 2 ++ tests/test-rcu-list.c | 16 ++++++++++++++ tests/test-rcu-slist.c | 2 ++ 5 files changed, 80 insertions(+), 2 deletions(-) create mode 100644 tests/test-rcu-slist.c diff --git a/include/qemu/queue.h b/include/qemu/queue.h index 19425f973f..fcecb70228 100644 --- a/include/qemu/queue.h +++ b/include/qemu/queue.h @@ -211,9 +211,20 @@ struct { \ (head)->slh_first = (head)->slh_first->field.sle_next; \ } while (/*CONSTCOND*/0) -#define QSLIST_REMOVE_AFTER(slistelm, field) do { \ +#define QSLIST_REMOVE_AFTER(slistelm, field) do { \ (slistelm)->field.sle_next = \ - QSLIST_NEXT(QSLIST_NEXT((slistelm), field), field); \ + QSLIST_NEXT(QSLIST_NEXT((slistelm), field), field); \ +} while (/*CONSTCOND*/0) + +#define QSLIST_REMOVE(head, elm, type, field) do { \ + if ((head)->slh_first == (elm)) { \ + QSLIST_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->slh_first; \ + while (curelm->field.sle_next != (elm)) \ + curelm = curelm->field.sle_next; \ + curelm->field.sle_next = curelm->field.sle_next->field.sle_next; \ + } \ } while (/*CONSTCOND*/0) #define QSLIST_FOREACH(var, head, field) \ diff --git a/include/qemu/rcu_queue.h b/include/qemu/rcu_queue.h index 2d386f303e..558961cc27 100644 --- a/include/qemu/rcu_queue.h +++ b/include/qemu/rcu_queue.h @@ -262,6 +262,53 @@ extern "C" { (var) && ((next) = atomic_rcu_read(&(var)->field.tqe_next), 1); \ (var) = (next)) +/* + * RCU singly-linked list + */ + +/* Singly-linked list access methods */ +#define QSLIST_EMPTY_RCU(head) (atomic_read(&(head)->slh_first) == NULL) +#define QSLIST_FIRST_RCU(head) atomic_rcu_read(&(head)->slh_first) +#define QSLIST_NEXT_RCU(elm, field) atomic_rcu_read(&(elm)->field.sle_next) + +/* Singly-linked list functions */ +#define QSLIST_INSERT_HEAD_RCU(head, elm, field) do { \ + (elm)->field.sle_next = (head)->slh_first; \ + atomic_rcu_set(&(head)->slh_first, (elm)); \ +} while (/*CONSTCOND*/0) + +#define QSLIST_INSERT_AFTER_RCU(head, listelm, elm, field) do { \ + (elm)->field.sle_next = (listelm)->field.sle_next; \ + atomic_rcu_set(&(listelm)->field.sle_next, (elm)); \ +} while (/*CONSTCOND*/0) + +#define QSLIST_REMOVE_HEAD_RCU(head, field) do { \ + atomic_set(&(head)->slh_first, (head)->slh_first->field.sle_next); \ +} while (/*CONSTCOND*/0) + +#define QSLIST_REMOVE_RCU(head, elm, type, field) do { \ + if ((head)->slh_first == (elm)) { \ + QSLIST_REMOVE_HEAD_RCU((head), field); \ + } else { \ + struct type *curr = (head)->slh_first; \ + while (curr->field.sle_next != (elm)) { \ + curr = curr->field.sle_next; \ + } \ + atomic_set(&curr->field.sle_next, \ + curr->field.sle_next->field.sle_next); \ + } \ +} while (/*CONSTCOND*/0) + +#define QSLIST_FOREACH_RCU(var, head, field) \ + for ((var) = atomic_rcu_read(&(head)->slh_first); \ + (var); \ + (var) = atomic_rcu_read(&(var)->field.sle_next)) + +#define QSLIST_FOREACH_SAFE_RCU(var, head, field, next) \ + for ((var) = atomic_rcu_read(&(head)->slh_first); \ + (var) && ((next) = atomic_rcu_read(&(var)->field.sle_next), 1); \ + (var) = (next)) + #ifdef __cplusplus } #endif diff --git a/tests/Makefile.include b/tests/Makefile.include index 2f1cafed72..edcbd475aa 100644 --- a/tests/Makefile.include +++ b/tests/Makefile.include @@ -98,6 +98,7 @@ check-unit-y += tests/rcutorture$(EXESUF) check-unit-y += tests/test-rcu-list$(EXESUF) check-unit-y += tests/test-rcu-simpleq$(EXESUF) check-unit-y += tests/test-rcu-tailq$(EXESUF) +check-unit-y += tests/test-rcu-slist$(EXESUF) check-unit-y += tests/test-qdist$(EXESUF) check-unit-y += tests/test-qht$(EXESUF) check-unit-y += tests/test-qht-par$(EXESUF) @@ -415,6 +416,7 @@ tests/rcutorture$(EXESUF): tests/rcutorture.o $(test-util-obj-y) tests/test-rcu-list$(EXESUF): tests/test-rcu-list.o $(test-util-obj-y) tests/test-rcu-simpleq$(EXESUF): tests/test-rcu-simpleq.o $(test-util-obj-y) tests/test-rcu-tailq$(EXESUF): tests/test-rcu-tailq.o $(test-util-obj-y) +tests/test-rcu-slist$(EXESUF): tests/test-rcu-slist.o $(test-util-obj-y) tests/test-qdist$(EXESUF): tests/test-qdist.o $(test-util-obj-y) tests/test-qht$(EXESUF): tests/test-qht.o $(test-util-obj-y) tests/test-qht-par$(EXESUF): tests/test-qht-par.o tests/qht-bench$(EXESUF) $(test-util-obj-y) diff --git a/tests/test-rcu-list.c b/tests/test-rcu-list.c index 6f076473e0..1442c0c982 100644 --- a/tests/test-rcu-list.c +++ b/tests/test-rcu-list.c @@ -93,6 +93,8 @@ struct list_element { QSIMPLEQ_ENTRY(list_element) entry; #elif TEST_LIST_TYPE == 3 QTAILQ_ENTRY(list_element) entry; +#elif TEST_LIST_TYPE == 4 + QSLIST_ENTRY(list_element) entry; #else #error Invalid TEST_LIST_TYPE #endif @@ -144,6 +146,20 @@ static QTAILQ_HEAD(, list_element) Q_list_head; #define TEST_LIST_INSERT_HEAD_RCU QTAILQ_INSERT_HEAD_RCU #define TEST_LIST_FOREACH_RCU QTAILQ_FOREACH_RCU #define TEST_LIST_FOREACH_SAFE_RCU QTAILQ_FOREACH_SAFE_RCU + +#elif TEST_LIST_TYPE == 4 +static QSLIST_HEAD(, list_element) Q_list_head; + +#define TEST_NAME "qslist" +#define TEST_LIST_REMOVE_RCU(el, f) \ + QSLIST_REMOVE_RCU(&Q_list_head, el, list_element, f) + +#define TEST_LIST_INSERT_AFTER_RCU(list_el, el, f) \ + QSLIST_INSERT_AFTER_RCU(&Q_list_head, list_el, el, f) + +#define TEST_LIST_INSERT_HEAD_RCU QSLIST_INSERT_HEAD_RCU +#define TEST_LIST_FOREACH_RCU QSLIST_FOREACH_RCU +#define TEST_LIST_FOREACH_SAFE_RCU QSLIST_FOREACH_SAFE_RCU #else #error Invalid TEST_LIST_TYPE #endif diff --git a/tests/test-rcu-slist.c b/tests/test-rcu-slist.c new file mode 100644 index 0000000000..868e1e472e --- /dev/null +++ b/tests/test-rcu-slist.c @@ -0,0 +1,2 @@ +#define TEST_LIST_TYPE 4 +#include "test-rcu-list.c"