* Scott Cheloha (chel...@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 <chel...@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 <dgilb...@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 / dgilb...@redhat.com / Manchester, UK
