From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.5 required=3.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1FD7DC33CB1 for ; Tue, 14 Jan 2020 11:56:12 +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 DEAD2206D7 for ; Tue, 14 Jan 2020 11:56:11 +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="BeMwiKnE" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org DEAD2206D7 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+qemu-devel=archiver.kernel.org@nongnu.org Received: from localhost ([::1]:38006 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1irKnq-0008B4-Hp for qemu-devel@archiver.kernel.org; Tue, 14 Jan 2020 06:56:10 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:55964) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1irKZa-0006No-HF for qemu-devel@nongnu.org; Tue, 14 Jan 2020 06:41:30 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1irKZW-0003N2-HL for qemu-devel@nongnu.org; Tue, 14 Jan 2020 06:41:26 -0500 Received: from us-smtp-delivery-1.mimecast.com ([205.139.110.120]:37592 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 1irKZW-0003MZ-Dx for qemu-devel@nongnu.org; Tue, 14 Jan 2020 06:41:22 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1579002082; 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=52j2mgmiA4z5vA2yqyRSfUxDIXdlaCqV+gsG8XIQ6+k=; b=BeMwiKnE+TUZfqZuMWRCGP+M+omyYao6hsYQLFQC2I6JtJtZ8+YjtZ4rSvRSsNB75/7T/f iHqRJ6iNgO1qx40/i09jxs7FYuBsOEAOqcMO3HZJejpv/zW16V9O20Kiq9DtLwvRgscq7R 2I/Z0GSBU7Fw0T6UZTVIQLtsi5llZs8= 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-102-hiB7a0nkMUe_0QceA0_O0g-1; Tue, 14 Jan 2020 06:41:16 -0500 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 19EC9801E7A; Tue, 14 Jan 2020 11:41:15 +0000 (UTC) Received: from secure.mitica (ovpn-116-207.ams2.redhat.com [10.36.116.207]) by smtp.corp.redhat.com (Postfix) with ESMTP id E62D35DA70; Tue, 14 Jan 2020 11:41:05 +0000 (UTC) From: Juan Quintela To: qemu-devel@nongnu.org Subject: [PULL 13/30] migration: savevm_state_handler_insert: constant-time element insertion Date: Tue, 14 Jan 2020 12:39:09 +0100 Message-Id: <20200114113926.3556-14-quintela@redhat.com> In-Reply-To: <20200114113926.3556-1-quintela@redhat.com> References: <20200114113926.3556-1-quintela@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-MC-Unique: hiB7a0nkMUe_0QceA0_O0g-1 X-Mimecast-Spam-Score: 0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 205.139.110.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: Laurent Vivier , Peter Maydell , Thomas Huth , Corey Minyard , =?UTF-8?q?Daniel=20P=2E=20Berrang=C3=A9?= , Eduardo Habkost , Juan Quintela , Stefan Weil , Richard Henderson , "Michael S. Tsirkin" , "Dr. David Alan Gilbert" , qemu-arm@nongnu.org, qemu-ppc@nongnu.org, Scott Cheloha , =?UTF-8?q?Marc-Andr=C3=A9=20Lureau?= , Paolo Bonzini , David Gibson , Jason Wang , Stefan Berger Errors-To: qemu-devel-bounces+qemu-devel=archiver.kernel.org@nongnu.org Sender: "Qemu-devel" From: Scott Cheloha 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 Reviewed-by: Juan Quintela Signed-off-by: Juan Quintela --- migration/savevm.c | 26 +++++++++++++++++++++++--- 1 file changed, 23 insertions(+), 3 deletions(-) diff --git a/migration/savevm.c b/migration/savevm.c index 30d980caa2..e57686bca7 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.24.1