QEMU-Devel Archive on lore.kernel.org
 help / color / Atom feed
From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
To: Scott Cheloha <cheloha@linux.vnet.ibm.com>,
	david@gibson.dropbear.id.au, lvivier@redhat.com
Cc: qemu-devel@nongnu.org, Juan Quintela <quintela@redhat.com>
Subject: Re: [PATCH v2 2/2] migration: savevm_state_handler_insert: constant-time element insertion
Date: Fri, 18 Oct 2019 09:16:25 +0100
Message-ID: <20191018081625.GA2990@work-vm> (raw)
In-Reply-To: <20191017205953.13122-3-cheloha@linux.vnet.ibm.com>

* Scott Cheloha (cheloha@linux.vnet.ibm.com) wrote:
> 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=8T has 40000 such
> objects to insert.

Separate from reviewing this patch, I'd like to understand why you've
got 40000 objects.  This feels very very wrong and is likely to cause
problems to random other bits of qemu as well.

Dave

> Signed-off-by: Scott Cheloha <cheloha@linux.vnet.ibm.com>
> ---
>  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 {
>  
>  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 {
>  
>  static SaveState savevm_state = {
>      .handlers = QTAILQ_HEAD_INITIALIZER(savevm_state.handlers),
> +    .handler_pri_head = { [MIG_PRI_DEFAULT ... MIG_PRI_MAX] = NULL },
>      .global_section_id = 0,
>  };
>  
> @@ -709,24 +711,42 @@ static void savevm_state_handler_insert(SaveStateEntry *nse)
>  {
>      MigrationPriority priority = save_state_priority(nse);
>      SaveStateEntry *se;
> +    int i;
>  
>      assert(priority <= MIG_PRI_MAX);
>  
> -    QTAILQ_FOREACH(se, &savevm_state.handlers, entry) {
> -        if (save_state_priority(se) < priority) {
> +    for (i = priority - 1; i >= 0; i--) {
> +        se = savevm_state.handler_pri_head[i];
> +        if (se != NULL) {
> +            assert(save_state_priority(se) < priority);
>              break;
>          }
>      }
>  
> -    if (se) {
> +    if (i >= 0) {
>          QTAILQ_INSERT_BEFORE(se, nse, entry);
>      } else {
>          QTAILQ_INSERT_TAIL(&savevm_state.handlers, nse, entry);
>      }
> +
> +    if (savevm_state.handler_pri_head[priority] == NULL) {
> +        savevm_state.handler_pri_head[priority] = nse;
> +    }
>  }
>  
>  static void savevm_state_handler_remove(SaveStateEntry *se)
>  {
> +    SaveStateEntry *next;
> +    MigrationPriority priority = save_state_priority(se);
> +
> +    if (se == savevm_state.handler_pri_head[priority]) {
> +        next = QTAILQ_NEXT(se, entry);
> +        if (next != NULL && save_state_priority(next) == priority) {
> +            savevm_state.handler_pri_head[priority] = next;
> +        } else {
> +            savevm_state.handler_pri_head[priority] = NULL;
> +        }
> +    }
>      QTAILQ_REMOVE(&savevm_state.handlers, se, entry);
>  }
>  
> -- 
> 2.23.0
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK


  reply index

Thread overview: 17+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-10-17 20:59 [PATCH v2 0/2] migration: faster savevm_state_handler_insert() Scott Cheloha
2019-10-17 20:59 ` [PATCH v2 1/2] migration: add savevm_state_handler_remove() Scott Cheloha
2019-12-04 16:43   ` Dr. David Alan Gilbert
2020-01-08 19:07   ` Juan Quintela
2019-10-17 20:59 ` [PATCH v2 2/2] migration: savevm_state_handler_insert: constant-time element insertion Scott Cheloha
2019-10-18  8:16   ` Dr. David Alan Gilbert [this message]
2019-10-18  8:34     ` Laurent Vivier
2019-10-18  9:43       ` Dr. David Alan Gilbert
2019-10-18 16:38         ` Michael Roth
2019-10-18 17:26           ` Dr. David Alan Gilbert
2019-10-21  7:33           ` David Gibson
2019-10-19 10:12         ` David Gibson
2019-10-21  8:14           ` Dr. David Alan Gilbert
2019-11-20 21:48             ` Scott Cheloha
2019-12-04 16:49               ` Dr. David Alan Gilbert
2019-12-04 22:28                 ` David Gibson
2019-12-04 16:47   ` Dr. David Alan Gilbert

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20191018081625.GA2990@work-vm \
    --to=dgilbert@redhat.com \
    --cc=cheloha@linux.vnet.ibm.com \
    --cc=david@gibson.dropbear.id.au \
    --cc=lvivier@redhat.com \
    --cc=qemu-devel@nongnu.org \
    --cc=quintela@redhat.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

QEMU-Devel Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/qemu-devel/0 qemu-devel/git/0.git
	git clone --mirror https://lore.kernel.org/qemu-devel/1 qemu-devel/git/1.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 qemu-devel qemu-devel/ https://lore.kernel.org/qemu-devel \
		qemu-devel@nongnu.org
	public-inbox-index qemu-devel

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.nongnu.qemu-devel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git