Eric Auger <[email protected]> wrote:
> Support QLIST migration using the same principle as QTAILQ:
> 94869d5c52 ("migration: migrate QTAILQ").
>
> The VMSTATE_QLIST_V macro has the same proto as VMSTATE_QTAILQ_V.
> The change mainly resides in QLIST_RAW_INSERT_TAIL implementation.
>
> Tests also are provided.
>
> Signed-off-by: Eric Auger <[email protected]>
Hi
How long are these lists normally? I think that the INSERT_TAIL is the
wrong approach. If lists can be long, it is much better to just insert
at the beggining and as last operation, reverse things, no?
> +#define QLIST_RAW_INSERT_TAIL(head, elm, entry) do {
> \
> + void *iter, *last = NULL;
> \
> + *QLIST_RAW_NEXT(elm, entry) = NULL;
> \
> + if (!*QLIST_RAW_FIRST(head)) {
> \
> + *QLIST_RAW_FIRST(head) = elm;
> \
> + *QLIST_RAW_PREVIOUS(elm, entry) = head;
> \
> + break;
> \
> + }
> \
> + for (iter = *QLIST_RAW_FIRST(head);
> \
> + iter; last = iter, iter = *QLIST_RAW_NEXT(iter, entry))
> \
> + { }
> \
> + *QLIST_RAW_NEXT(last, entry) = elm;
> \
> + *QLIST_RAW_PREVIOUS(elm, entry) = last;
> \
I think that you normally want to do this two instructions in the
reverse order, just in case (famous last words).
> +static int get_qlist(QEMUFile *f, void *pv, size_t unused_size,
> + const VMStateField *field)
> +{
> + int ret = 0;
> + const VMStateDescription *vmsd = field->vmsd;
> + /* size of a QLIST element */
> + size_t size = field->size;
> + /* offset of the QLIST entry in a QLIST element */
> + size_t entry_offset = field->start;
> + int version_id = field->version_id;
> + void *elm;
> +
> + trace_get_qlist(field->name, vmsd->name, vmsd->version_id);
> + if (version_id > vmsd->version_id) {
> + error_report("%s %s", vmsd->name, "too new");
> + return -EINVAL;
> + }
> + if (version_id < vmsd->minimum_version_id) {
> + error_report("%s %s", vmsd->name, "too old");
> + return -EINVAL;
> + }
> +
> + while (qemu_get_byte(f)) {
> + elm = g_malloc(size);
> + ret = vmstate_load_state(f, vmsd, elm, version_id);
> + if (ret) {
> + error_report("%s: failed to load %s (%d)", field->name,
> + vmsd->name, ret);
> + g_free(elm);
> + return ret;
> + }
> + QLIST_RAW_INSERT_TAIL(pv, elm, entry_offset);
Here we insert at the beggining.
> + }
Here we reverse?
We move from O(n^2) to O(2n), much better, no?
As said, except if the lists are normally very short.
The rest of the patch looks ok to me.
Later, Juan.
