From nobody Sat May 18 12:12:36 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=1571246904; cv=none; d=zoho.com; s=zohoarc; b=VO1mgtikRj3/mqG1PzQ4XVLl1s5c1mFaIFbGVrWqUZiO+geKR9E6MEi13bmwEZ7xDdBiUn2n9iLFNEBUuNbvG5vexkODTCOoHFIg+C+y0GKtMeudPAGXD0q2qhd4IJtBNRGjHXSL/q7orw/yKB+ESLZyLjNdJuqmUJ0SjBH7KMM= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zoho.com; s=zohoarc; t=1571246904; 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=DAkgV4O6/GnIzZ7NoRtFTbD81JP/WatmnLAR5wdThTc=; b=P4phloje48x6GPCEEPpy7DfWux/mrPYIgk1fQ1Bme78pAeuUQDj2VGCdCb5WiJTe/1yhiLOgPLQVwTZD+J7zW3rrqQNeTTqSUt7R7Ci1/2C43Z760qpkyKyLDf5PKkFK6+SHWyEMM6UyS+c+EMg/HG7DS7NuNhbO22T0IIk4W48= 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 1571246904691219.1707236948282; Wed, 16 Oct 2019 10:28:24 -0700 (PDT) Received: from localhost ([::1]:46532 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iKn5z-0004wO-6k for importer@patchew.org; Wed, 16 Oct 2019 13:28:23 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:36020) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iKmNC-00041R-CR for qemu-devel@nongnu.org; Wed, 16 Oct 2019 12:42:07 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1iKmN9-00067s-8r for qemu-devel@nongnu.org; Wed, 16 Oct 2019 12:42:05 -0400 Received: from mx0a-001b2d01.pphosted.com ([148.163.156.1]:13836) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1iKmN8-00066L-VR for qemu-devel@nongnu.org; Wed, 16 Oct 2019 12:42:03 -0400 Received: from pps.filterd (m0098394.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x9GGbF6v055415 for ; Wed, 16 Oct 2019 12:41:59 -0400 Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com with ESMTP id 2vp67rhr37-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Wed, 16 Oct 2019 12:41:59 -0400 Received: from m0098394.ppops.net (m0098394.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.27/8.16.0.27) with SMTP id x9GGfw8o095682 for ; Wed, 16 Oct 2019 12:41:59 -0400 Received: from ppma03dal.us.ibm.com (b.bd.3ea9.ip4.static.sl-reverse.com [169.62.189.11]) by mx0a-001b2d01.pphosted.com with ESMTP id 2vp67rhr2q-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 16 Oct 2019 12:41:58 -0400 Received: from pps.filterd (ppma03dal.us.ibm.com [127.0.0.1]) by ppma03dal.us.ibm.com (8.16.0.27/8.16.0.27) with SMTP id x9GGeeJF023910; Wed, 16 Oct 2019 16:41:58 GMT Received: from b01cxnp22036.gho.pok.ibm.com (b01cxnp22036.gho.pok.ibm.com [9.57.198.26]) by ppma03dal.us.ibm.com with ESMTP id 2vk6f97jjd-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 16 Oct 2019 16:41:58 +0000 Received: from b01ledav002.gho.pok.ibm.com (b01ledav002.gho.pok.ibm.com [9.57.199.107]) by b01cxnp22036.gho.pok.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x9GGfvpw40632780 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 16 Oct 2019 16:41:57 GMT Received: from b01ledav002.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 406DE124053; Wed, 16 Oct 2019 16:41:57 +0000 (GMT) Received: from b01ledav002.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id D7884124052; Wed, 16 Oct 2019 16:41:56 +0000 (GMT) Received: from rascal.austin.ibm.com (unknown [9.41.179.32]) by b01ledav002.gho.pok.ibm.com (Postfix) with ESMTP; Wed, 16 Oct 2019 16:41:56 +0000 (GMT) From: Scott Cheloha To: qemu-devel@nongnu.org Subject: [PATCH] migration: savevm_state_insert_handler: constant-time element insertion Date: Wed, 16 Oct 2019 11:41:56 -0500 Message-Id: <20191016164156.4506-1-cheloha@linux.vnet.ibm.com> X-Mailer: git-send-email 2.23.0 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-16_07:, , 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=1011 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-1910160140 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [generic] [fuzzy] X-Received-From: 148.163.156.1 X-Mailman-Approved-At: Wed, 16 Oct 2019 13:27:17 -0400 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" Registering a SaveStateEntry object via savevm_state_insert_handler() is an O(n) operation because the list is a priority queue maintained by walking the list from head to tail to find a suitable insertion point. This adds considerable overhead for VMs with many such objects. For instance, ppc64 machines with large maxmem (8T+) spend ~10% or more of their CPU time in savevm_state_insert_handler() before attempting to boot a kernel. If we track the head for each priority's subqueue we can insert new elements in constant time. This commit also introduces a new function, savevm_state_remove_handler(), which abstracts the logic for replacing the head of an element's subqueue when removing it. Signed-off-by: Scott Cheloha --- migration/savevm.c | 35 ++++++++++++++++++++++++++++++----- 1 file changed, 30 insertions(+), 5 deletions(-) diff --git a/migration/savevm.c b/migration/savevm.c index 8d95e261f6..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,20 +711,43 @@ 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; + } +} + +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 /* TODO: Individual devices generally have very little idea about the rest @@ -777,7 +802,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 +866,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