From nobody Wed May 8 22:07:39 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1582195169; cv=none; d=zohomail.com; s=zohoarc; b=HodvGOduElqxxnJqA/0D4KOftthU1e2SAbGhZfOw1R3QqDY2rwhtZ2E8tNdit/ykFfo2kxYR6KP+5MybdYt8pciL534QzQ522fovKt3Tv4Ssj4oEsxRyUQlOEqcXE6mMFddDrJWaHnBZ6XHJ7X1Cf4jsGgP70UO2top1KcqPEp0= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1582195169; h=Content-Transfer-Encoding:Cc:Date:From:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:Sender:Subject:To; bh=5YCilSFFWtLWlcpaHNeLRMfIZWehJ5IyMtE4Hluj81g=; b=SJ7b/tbh26E+eHqqtjBP148E+bMl2xCK3w13VpFfaZMuPqSrk8JBI0t4aNnM9gdVQCIwC27rGRnF8qFLpzVu0Ui+OFj+pmysdUkkCz124M19sg/MbxxYBnabCZmIh1IUeoxdA8Pxzzi+n2hoaVHUgYq7wyYzOuGiQNQakF8Au6c= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1582195169302303.93761700902655; Thu, 20 Feb 2020 02:39:29 -0800 (PST) Received: from localhost ([::1]:39502 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1j4jEt-0002Do-7g for importer@patchew.org; Thu, 20 Feb 2020 05:39:27 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:34374) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1j4jE2-0001ox-Ka for qemu-devel@nongnu.org; Thu, 20 Feb 2020 05:38:35 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1j4jE1-0002Yn-7H for qemu-devel@nongnu.org; Thu, 20 Feb 2020 05:38:34 -0500 Received: from mail-wr1-x442.google.com ([2a00:1450:4864:20::442]:44618) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1j4jE0-0002Yh-VA for qemu-devel@nongnu.org; Thu, 20 Feb 2020 05:38:33 -0500 Received: by mail-wr1-x442.google.com with SMTP id m16so3986852wrx.11 for ; Thu, 20 Feb 2020 02:38:32 -0800 (PST) Received: from donizetti.redhat.com (nat-pool-mxp-u.redhat.com. [149.6.153.187]) by smtp.gmail.com with ESMTPSA id s23sm4058602wra.15.2020.02.20.02.38.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Feb 2020 02:38:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=5YCilSFFWtLWlcpaHNeLRMfIZWehJ5IyMtE4Hluj81g=; b=OU/877VSgwEeGjWP7BDtoI8LN/TIfZw1RcYInIwGT7qg8keC/9V+Gtk1IYCQBb3aTG Q+4rr847WIUd8k+jMfgil7vUESJXbk2C47f+nCmgm2WhKcRydzqQnrL1stCmQG6ZDt33 5j3JTmFMy0i+ItPGSi6dCV2PTW5cNvTJ0zmNYqZXcd8p/QkPw5HI2gPv38MME2pueAsn xCSsc2zSJliymvHOZlHrGl7WCAN5AUQTgPzIm3Vxx67MqH+cvFsbcNscmRSVMZLiv775 yoVx+2fvYYL6sVidMhI5QP8qq/CZnio2yFg3V2264naUHtLfmBc5D3V2oK4Ceb3a/di1 JRQA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :mime-version:content-transfer-encoding; bh=5YCilSFFWtLWlcpaHNeLRMfIZWehJ5IyMtE4Hluj81g=; b=p+GRZrPxlJd964kzrhtCXeeqGePTEg9bJLb/TU+YrXa8XC0vK+BSpk0WxOThqttkKs M/mv/xkWbYDnhxye4x6flCpueTa454PqKKUWCPR1K8zFao9xEfsiqEGLY13yBViBrcsk Sz2aqZrGU7v9rGAezejhTGk4ZWjCB/UGBnocJxXbsGUH+sbRvz0mNr/agF2uu4Jw9TWa i6RSMXzPad/0Rc77Sxq/aUXpqSw/HXGQugzuoPB39xpaiJRRaTUWTZ+bwtDSdOGX9cG4 B8Iy1VevlH4EV5ItJA9D4LC5rsqJe8t3OGVq5KOvZWpK1hePVTub7VESGth6w4d8v5cW 2+Zg== X-Gm-Message-State: APjAAAXFOJ9QCRbFrEyTlJC4WmoY1A17xZCIiqcSKs3DPf4I8AJdDWpX HMS73/nh0dx1n203L1+PZRGp0yi0 X-Google-Smtp-Source: APXvYqy1pnWis1XcTk6gWXts3+Ejs3Y53Cc0+e37OgMZlhzt4msZQdf6m+ivqGx9h2k76cFzOzhrvg== X-Received: by 2002:adf:ec02:: with SMTP id x2mr8721743wrn.8.1582195110661; Thu, 20 Feb 2020 02:38:30 -0800 (PST) From: Paolo Bonzini To: qemu-devel@nongnu.org Subject: [PATCH] rcu_queue: add QSLIST functions Date: Thu, 20 Feb 2020 11:38:28 +0100 Message-Id: <20200220103828.24525-1-pbonzini@redhat.com> X-Mailer: git-send-email 2.21.1 MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:4864:20::442 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: stefanha@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) Content-Type: text/plain; charset="utf-8" QSLIST is the only family of lists for which we do not have RCU-friendly ac= cessors, add them. Signed-off-by: Paolo Bonzini Reviewed-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 =3D (head)->slh_first->field.sle_next; \ } while (/*CONSTCOND*/0) =20 -#define QSLIST_REMOVE_AFTER(slistelm, field) do { \ +#define QSLIST_REMOVE_AFTER(slistelm, field) do { \ (slistelm)->field.sle_next =3D \ - 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 =3D=3D (elm)) { = \ + QSLIST_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm =3D (head)->slh_first; \ + while (curelm->field.sle_next !=3D (elm)) \ + curelm =3D curelm->field.sle_next; \ + curelm->field.sle_next =3D curelm->field.sle_next->field.sle_next;= \ + } \ } while (/*CONSTCOND*/0) =20 #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) =3D atomic_rcu_read(&(var)->field.tqe_next), 1);= \ (var) =3D (next)) =20 +/* + * RCU singly-linked list + */ + +/* Singly-linked list access methods */ +#define QSLIST_EMPTY_RCU(head) (atomic_read(&(head)->slh_first) =3D= =3D NULL) +#define QSLIST_FIRST_RCU(head) atomic_rcu_read(&(head)->slh_first) +#define QSLIST_NEXT_RCU(elm, field) atomic_rcu_read(&(elm)->field.sle_nex= t) + +/* Singly-linked list functions */ +#define QSLIST_INSERT_HEAD_RCU(head, elm, field) do { \ + (elm)->field.sle_next =3D (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 =3D (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 =3D=3D (elm)) { \ + QSLIST_REMOVE_HEAD_RCU((head), field); \ + } else { \ + struct type *curr =3D (head)->slh_first; \ + while (curr->field.sle_next !=3D (elm)) { \ + curr =3D 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) =3D atomic_rcu_read(&(head)->slh_first); \ + (var); \ + (var) =3D atomic_rcu_read(&(var)->field.sle_next)) + +#define QSLIST_FOREACH_SAFE_RCU(var, head, field, next) \ + for ((var) =3D atomic_rcu_read(&(head)->slh_first); = \ + (var) && ((next) =3D atomic_rcu_read(&(var)->field.sle_next), 1);= \ + (var) =3D (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 +=3D tests/rcutorture$(EXESUF) check-unit-y +=3D tests/test-rcu-list$(EXESUF) check-unit-y +=3D tests/test-rcu-simpleq$(EXESUF) check-unit-y +=3D tests/test-rcu-tailq$(EXESUF) +check-unit-y +=3D tests/test-rcu-slist$(EXESUF) check-unit-y +=3D tests/test-qdist$(EXESUF) check-unit-y +=3D tests/test-qht$(EXESUF) check-unit-y +=3D tests/test-qht-par$(EXESUF) @@ -415,6 +416,7 @@ tests/rcutorture$(EXESUF): tests/rcutorture.o $(test-ut= il-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 =3D=3D 3 QTAILQ_ENTRY(list_element) entry; +#elif TEST_LIST_TYPE =3D=3D 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 =3D=3D 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" --=20 2.21.1