From 174723ffe586e453f8ed4010ea07bbf79805b63f Mon Sep 17 00:00:00 2001 From: Scott Cheloha Date: Thu, 17 Oct 2019 15:59:53 -0500 Subject: migration: savevm_state_handler_insert: constant-time element insertion 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 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(-) (limited to 'migration') 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 { 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); } -- cgit v1.2.3