Re: [PATCH v2 2/2] migration: savevm_state_handler_insert: constant-time element insertion

[Dr. David Alan Gilbert]

* Scott Cheloha (address@hidden) 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 <address@hidden>

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 <address@hidden>

> ---
>  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 / address@hidden / Manchester, UK