migration: savevm_state_handler_insert: constant-time element insertion
authorScott Cheloha <cheloha@linux.vnet.ibm.com>
Thu, 17 Oct 2019 20:59:53 +0000 (15:59 -0500)
committerJuan Quintela <quintela@redhat.com>
Mon, 20 Jan 2020 08:10:22 +0000 (09:10 +0100)
commit174723ffe586e453f8ed4010ea07bbf79805b63f
tree2f58b2e1797ce0b72e4cba4592adc8bf885d5d34
parentbd5de61e7b926b5bb9dae254630bf3c8be575bc0
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 <cheloha@linux.vnet.ibm.com>
Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
Reviewed-by: Juan Quintela <quintela@redhat.com>
Signed-off-by: Juan Quintela <quintela@redhat.com>
migration/savevm.c