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>
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: Wed, 4 Dec 2019 16:47:17 +0000
Message-ID: <20191204164717.GL3325@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.
> 
> Signed-off-by: Scott Cheloha <cheloha@linux.vnet.ibm.com>

OK, it took me a while to figure out why you didn't just
turn handlers into handlers[MIG_PRI_MAX]; but I guess the problem is
you would have to change all the foreach's scattered around that walk
the list.  So


Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.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



      parent 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
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 [this message]

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=20191204164717.GL3325@work-vm \
    --to=dgilbert@redhat.com \
    --cc=cheloha@linux.vnet.ibm.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