From nobody Tue May 7 05:38:44 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.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; spf=pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org ARC-Seal: i=1; a=rsa-sha256; t=1571346169; cv=none; d=zoho.com; s=zohoarc; b=bqDG8F/AX9DMS5NgtLVqc1rXH6R7mCuNE3BZLhrNF96QxCvd7L3+rxQzuV9rSqkrdGa80qqfVf7ido9orB8HEJ+Ujp4o/XP6ABZbyHkLtbZ31nx81UoHi7H4vJuK47eA3nRkTLE2IyFwtrthsLjqa/r8DobmGnU20yFvitjVClA= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zoho.com; s=zohoarc; t=1571346169; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=/k8OjbW+2sXTtrimQTdvtb6a2yR4k4Y7igiUFhxOMIU=; b=dsfkRbgR8rW4Vi11qB/5ccWmU3lfimcHrWRH402aeTNDvN1vpp6fRhFqtRLvVpRflGIiYGRnHxoN+DTIA3FLYjYf0KHRCss40c3MghZ61118uSkOBZ+wXqaNI9ifAe4idohH2hRcLmP6ecLR65RSZkTOSHQTpYzN7OLqDNW6jvc= ARC-Authentication-Results: i=1; mx.zoho.com; spf=pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 157134616974886.0044043038954; Thu, 17 Oct 2019 14:02:49 -0700 (PDT) Received: from localhost ([::1]:59860 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iLCv0-0001oa-LW for importer@patchew.org; Thu, 17 Oct 2019 17:02:46 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:55192) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iLCsM-0000SH-3k for qemu-devel@nongnu.org; Thu, 17 Oct 2019 17:00:03 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1iLCsJ-0008MA-UK for qemu-devel@nongnu.org; Thu, 17 Oct 2019 17:00:01 -0400 Received: from mx0b-001b2d01.pphosted.com ([148.163.158.5]:34528 helo=mx0a-001b2d01.pphosted.com) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1iLCsJ-0008La-54 for qemu-devel@nongnu.org; Thu, 17 Oct 2019 16:59:59 -0400 Received: from pps.filterd (m0098420.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x9HKdQd8161525 for ; Thu, 17 Oct 2019 16:59:57 -0400 Received: from pps.reinject (localhost [127.0.0.1]) by mx0b-001b2d01.pphosted.com with ESMTP id 2vpvsueufe-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Thu, 17 Oct 2019 16:59:57 -0400 Received: from m0098420.ppops.net (m0098420.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.27/8.16.0.27) with SMTP id x9HKdRYT161544 for ; Thu, 17 Oct 2019 16:59:56 -0400 Received: from ppma02wdc.us.ibm.com (aa.5b.37a9.ip4.static.sl-reverse.com [169.55.91.170]) by mx0b-001b2d01.pphosted.com with ESMTP id 2vpvsueuf6-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 17 Oct 2019 16:59:56 -0400 Received: from pps.filterd (ppma02wdc.us.ibm.com [127.0.0.1]) by ppma02wdc.us.ibm.com (8.16.0.27/8.16.0.27) with SMTP id x9HKtiKa031234; Thu, 17 Oct 2019 20:59:55 GMT Received: from b03cxnp08026.gho.boulder.ibm.com (b03cxnp08026.gho.boulder.ibm.com [9.17.130.18]) by ppma02wdc.us.ibm.com with ESMTP id 2vk6f7s608-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 17 Oct 2019 20:59:55 +0000 Received: from b03ledav002.gho.boulder.ibm.com (b03ledav002.gho.boulder.ibm.com [9.17.130.233]) by b03cxnp08026.gho.boulder.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x9HKxsZU55312806 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 17 Oct 2019 20:59:54 GMT Received: from b03ledav002.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id B45E5136051; Thu, 17 Oct 2019 20:59:54 +0000 (GMT) Received: from b03ledav002.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 80CDA136053; Thu, 17 Oct 2019 20:59:54 +0000 (GMT) Received: from rascal.austin.ibm.com (unknown [9.41.179.32]) by b03ledav002.gho.boulder.ibm.com (Postfix) with ESMTP; Thu, 17 Oct 2019 20:59:54 +0000 (GMT) From: Scott Cheloha To: qemu-devel@nongnu.org Subject: [PATCH v2 1/2] migration: add savevm_state_handler_remove() Date: Thu, 17 Oct 2019 15:59:52 -0500 Message-Id: <20191017205953.13122-2-cheloha@linux.vnet.ibm.com> X-Mailer: git-send-email 2.23.0 In-Reply-To: <20191017205953.13122-1-cheloha@linux.vnet.ibm.com> References: <20191017205953.13122-1-cheloha@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-TM-AS-GCONF: 00 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-10-17_06:, , signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 malwarescore=0 suspectscore=3 phishscore=0 bulkscore=0 spamscore=0 clxscore=1015 lowpriorityscore=0 mlxscore=0 impostorscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1908290000 definitions=main-1910170186 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [generic] [fuzzy] X-Received-From: 148.163.158.5 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: "Dr . David Alan Gilbert" , Juan Quintela Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" Content-Type: text/plain; charset="utf-8" Create a function to abstract common logic needed when removing a SaveStateEntry element from the savevm_state.handlers queue. For now we just remove the element. Soon it will involve additional cleanup. Signed-off-by: Scott Cheloha Reviewed-by: Dr. David Alan Gilbert Reviewed-by: Juan Quintela --- migration/savevm.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/migration/savevm.c b/migration/savevm.c index 8d95e261f6..b2e3b7222a 100644 --- a/migration/savevm.c +++ b/migration/savevm.c @@ -725,6 +725,11 @@ static void savevm_state_handler_insert(SaveStateEntry= *nse) } } =20 +static void savevm_state_handler_remove(SaveStateEntry *se) +{ + QTAILQ_REMOVE(&savevm_state.handlers, se, entry); +} + /* TODO: Individual devices generally have very little idea about the rest of the system, so instance_id should be removed/replaced. Meanwhile pass -1 as instance_id if you do not already have a clearly @@ -777,7 +782,7 @@ void unregister_savevm(DeviceState *dev, const char *id= str, void *opaque) =20 QTAILQ_FOREACH_SAFE(se, &savevm_state.handlers, entry, new_se) { if (strcmp(se->idstr, id) =3D=3D 0 && se->opaque =3D=3D opaque) { - QTAILQ_REMOVE(&savevm_state.handlers, se, entry); + savevm_state_handler_remove(se); g_free(se->compat); g_free(se); } @@ -841,7 +846,7 @@ void vmstate_unregister(DeviceState *dev, const VMState= Description *vmsd, =20 QTAILQ_FOREACH_SAFE(se, &savevm_state.handlers, entry, new_se) { if (se->vmsd =3D=3D vmsd && se->opaque =3D=3D opaque) { - QTAILQ_REMOVE(&savevm_state.handlers, se, entry); + savevm_state_handler_remove(se); g_free(se->compat); g_free(se); } --=20 2.23.0 From nobody Tue May 7 05:38:44 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.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; spf=pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org ARC-Seal: i=1; a=rsa-sha256; t=1571346290; cv=none; d=zoho.com; s=zohoarc; b=k5Dszq3jvZt+AJD27YL2NqvG12bDyNwO8ozPrOPs0jWq7vWmQ8+1DLajeeA8M2yHEUK9z0CmIMEkvg6ohKOz3C1O/trJdRoIEvNgYMjBE7GpURXDkPsq9XdJkqez7JJYfvjJgXMtBrOxP3V9exAX5rdjLWDHMCGf2xkWuxBPzwk= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zoho.com; s=zohoarc; t=1571346290; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=ijkezjHMpERMAuwx6tEW6kZTqO++wUIZW2Sr/KOfA30=; b=mttwqgebDnAu0lHf9DCCiwr976Pttbek/m0ca5SwDI2ORUMaR690ALrR8o9EHbG0c0bun2fpd+4yeFyOu44aKK0wpCE1hgK7RpOeX6ZFheXCsgOAGNq4Zirb4YW7bIGflqlnBROdKAUj/U1wvxFiD2reenUosL9DvlsEO5T/OsU= ARC-Authentication-Results: i=1; mx.zoho.com; spf=pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1571346290872462.2241037327582; Thu, 17 Oct 2019 14:04:50 -0700 (PDT) Received: from localhost ([::1]:59893 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iLCwz-0004g4-KE for importer@patchew.org; Thu, 17 Oct 2019 17:04:49 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:55191) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iLCsM-0000SG-4a for qemu-devel@nongnu.org; Thu, 17 Oct 2019 17:00:03 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1iLCsJ-0008ME-UQ for qemu-devel@nongnu.org; Thu, 17 Oct 2019 17:00:01 -0400 Received: from mx0b-001b2d01.pphosted.com ([148.163.158.5]:19462 helo=mx0a-001b2d01.pphosted.com) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1iLCsJ-0008LY-4J for qemu-devel@nongnu.org; Thu, 17 Oct 2019 16:59:59 -0400 Received: from pps.filterd (m0098413.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x9HKchW3075174 for ; Thu, 17 Oct 2019 16:59:57 -0400 Received: from pps.reinject (localhost [127.0.0.1]) by mx0b-001b2d01.pphosted.com with ESMTP id 2vpvtm6ty3-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Thu, 17 Oct 2019 16:59:57 -0400 Received: from m0098413.ppops.net (m0098413.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.27/8.16.0.27) with SMTP id x9HKq9VH106924 for ; Thu, 17 Oct 2019 16:59:57 -0400 Received: from ppma01dal.us.ibm.com (83.d6.3fa9.ip4.static.sl-reverse.com [169.63.214.131]) by mx0b-001b2d01.pphosted.com with ESMTP id 2vpvtm6txw-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 17 Oct 2019 16:59:57 -0400 Received: from pps.filterd (ppma01dal.us.ibm.com [127.0.0.1]) by ppma01dal.us.ibm.com (8.16.0.27/8.16.0.27) with SMTP id x9HKtfQv012820; Thu, 17 Oct 2019 20:59:56 GMT Received: from b03cxnp08027.gho.boulder.ibm.com (b03cxnp08027.gho.boulder.ibm.com [9.17.130.19]) by ppma01dal.us.ibm.com with ESMTP id 2vk6f85dk8-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 17 Oct 2019 20:59:56 +0000 Received: from b03ledav002.gho.boulder.ibm.com (b03ledav002.gho.boulder.ibm.com [9.17.130.233]) by b03cxnp08027.gho.boulder.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x9HKxtac44695904 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 17 Oct 2019 20:59:55 GMT Received: from b03ledav002.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 08A29136055; Thu, 17 Oct 2019 20:59:55 +0000 (GMT) Received: from b03ledav002.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id C945C136053; Thu, 17 Oct 2019 20:59:54 +0000 (GMT) Received: from rascal.austin.ibm.com (unknown [9.41.179.32]) by b03ledav002.gho.boulder.ibm.com (Postfix) with ESMTP; Thu, 17 Oct 2019 20:59:54 +0000 (GMT) From: Scott Cheloha To: qemu-devel@nongnu.org Subject: [PATCH v2 2/2] migration: savevm_state_handler_insert: constant-time element insertion Date: Thu, 17 Oct 2019 15:59:53 -0500 Message-Id: <20191017205953.13122-3-cheloha@linux.vnet.ibm.com> X-Mailer: git-send-email 2.23.0 In-Reply-To: <20191017205953.13122-1-cheloha@linux.vnet.ibm.com> References: <20191017205953.13122-1-cheloha@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-TM-AS-GCONF: 00 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-10-17_06:, , signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 malwarescore=0 suspectscore=1 phishscore=0 bulkscore=0 spamscore=0 clxscore=1015 lowpriorityscore=0 mlxscore=0 impostorscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1908290000 definitions=main-1910170186 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [generic] [fuzzy] X-Received-From: 148.163.158.5 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: "Dr . David Alan Gilbert" , Juan Quintela Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" Content-Type: text/plain; charset="utf-8" savevm_state's SaveStateEntry TAILQ is a priority queue. Priority sorting is maintained by searching from head to tail for a suitable insertion spot. Insertion is thus an O(n) operation. If we instead keep track of the head of each priority's subqueue within that larger queue we can reduce this operation to O(1) time. savevm_state_handler_remove() becomes slightly more complex to accomodate these gains: we need to replace the head of a priority's subqueue when removing it. With O(1) insertion, booting VMs with many SaveStateEntry objects is more plausible. For example, a ppc64 VM with maxmem=3D8T has 40000 such objects to insert. Signed-off-by: Scott Cheloha Reviewed-by: Dr. David Alan Gilbert --- migration/savevm.c | 26 +++++++++++++++++++++++--- 1 file changed, 23 insertions(+), 3 deletions(-) diff --git a/migration/savevm.c b/migration/savevm.c index b2e3b7222a..f7a2d36bba 100644 --- a/migration/savevm.c +++ b/migration/savevm.c @@ -250,6 +250,7 @@ typedef struct SaveStateEntry { =20 typedef struct SaveState { QTAILQ_HEAD(, SaveStateEntry) handlers; + SaveStateEntry *handler_pri_head[MIG_PRI_MAX + 1]; int global_section_id; uint32_t len; const char *name; @@ -261,6 +262,7 @@ typedef struct SaveState { =20 static SaveState savevm_state =3D { .handlers =3D QTAILQ_HEAD_INITIALIZER(savevm_state.handlers), + .handler_pri_head =3D { [MIG_PRI_DEFAULT ... MIG_PRI_MAX] =3D NULL }, .global_section_id =3D 0, }; =20 @@ -709,24 +711,42 @@ static void savevm_state_handler_insert(SaveStateEntr= y *nse) { MigrationPriority priority =3D save_state_priority(nse); SaveStateEntry *se; + int i; =20 assert(priority <=3D MIG_PRI_MAX); =20 - QTAILQ_FOREACH(se, &savevm_state.handlers, entry) { - if (save_state_priority(se) < priority) { + for (i =3D priority - 1; i >=3D 0; i--) { + se =3D savevm_state.handler_pri_head[i]; + if (se !=3D NULL) { + assert(save_state_priority(se) < priority); break; } } =20 - if (se) { + if (i >=3D 0) { QTAILQ_INSERT_BEFORE(se, nse, entry); } else { QTAILQ_INSERT_TAIL(&savevm_state.handlers, nse, entry); } + + if (savevm_state.handler_pri_head[priority] =3D=3D NULL) { + savevm_state.handler_pri_head[priority] =3D nse; + } } =20 static void savevm_state_handler_remove(SaveStateEntry *se) { + SaveStateEntry *next; + MigrationPriority priority =3D save_state_priority(se); + + if (se =3D=3D savevm_state.handler_pri_head[priority]) { + next =3D QTAILQ_NEXT(se, entry); + if (next !=3D NULL && save_state_priority(next) =3D=3D priority) { + savevm_state.handler_pri_head[priority] =3D next; + } else { + savevm_state.handler_pri_head[priority] =3D NULL; + } + } QTAILQ_REMOVE(&savevm_state.handlers, se, entry); } =20 --=20 2.23.0