From nobody Thu Nov 13 09:10:16 2025 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=1579006997; cv=none; d=zohomail.com; s=zohoarc; b=CP35Azy7X0dOU/7X3qXiq/Yuw3Mtw9xHV133BDDOpziGq1bXId+NjUjaNLDIfh+JYCMwSqE90efpUQwRvlcqQqKgHdOmhId0K4iraip+Mq2vmOW7veRURtanaseZGjeOgtDBcZ65vH3yb1kiHhCT04g3J8BEJ1bdh3sUC+bydnM= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1579006997; h=Content-Type: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=52j2mgmiA4z5vA2yqyRSfUxDIXdlaCqV+gsG8XIQ6+k=; b=dFv170FnuzHfj0RUI83ruPoCCFoQJj8HvZ38XWTiHCCxqVJSsMSxvS7hnMu6bfEKBYuaDk5CtNc01IPG1kLxgtZnCneulr9i2DqRUy5PWN2H+czyf96PeH7TZvKWVZy2q20BTxVGjoVyCc9iplI6bFFy0BywbUwrbrYrYOzcUwA= 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 157900699761260.67121524864467; Tue, 14 Jan 2020 05:03:17 -0800 (PST) Received: from localhost ([::1]:38984 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1irLql-0003I4-J9 for importer@patchew.org; Tue, 14 Jan 2020 08:03:15 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:41137) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1irLix-0002oh-2S for qemu-devel@nongnu.org; Tue, 14 Jan 2020 07:55:12 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1irLit-0001m3-4j for qemu-devel@nongnu.org; Tue, 14 Jan 2020 07:55:10 -0500 Received: from us-smtp-delivery-1.mimecast.com ([205.139.110.120]:54178 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 1irLit-0001le-0s for qemu-devel@nongnu.org; Tue, 14 Jan 2020 07:55:07 -0500 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-170-qWwRMI4uPa20JK2lf4T8_Q-1; Tue, 14 Jan 2020 07:55:04 -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 E60FB800D50; Tue, 14 Jan 2020 12:55:02 +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 0260D5D9E5; Tue, 14 Jan 2020 12:54:55 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1579006506; 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=aXzdqvVb+mZjpSr0IZXAGDFku0iYOyUee1IxQcVGfmU6f8ZrmO+BPdjBDggUBmC+ji75Qq yQ7B1tOb9pKTWBI/KS+AVg85Z0am1VMmp3Oy9JS5LKI01X8JEWKKrhk6wU+WWN8/+hwleM prZzNK+p5QS72tS8dTg7umtp0mlqgjI= From: Juan Quintela To: qemu-devel@nongnu.org Subject: [PULL 14/30] migration: savevm_state_handler_insert: constant-time element insertion Date: Tue, 14 Jan 2020 13:52:38 +0100 Message-Id: <20200114125254.4515-15-quintela@redhat.com> In-Reply-To: <20200114125254.4515-1-quintela@redhat.com> References: <20200114125254.4515-1-quintela@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-MC-Unique: qWwRMI4uPa20JK2lf4T8_Q-1 X-Mimecast-Spam-Score: 0 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 , Jason Wang , "Michael S. Tsirkin" , "Dr. David Alan Gilbert" , Stefan Berger , qemu-arm@nongnu.org, qemu-ppc@nongnu.org, Scott Cheloha , =?UTF-8?q?Marc-Andr=C3=A9=20Lureau?= , Paolo Bonzini , Richard Henderson , David Gibson 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" 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