Hi Juan,
On 10/17/19 10:06 AM, Juan Quintela wrote:
> Eric Auger <eric.au...@redhat.com> 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 <eric.au...@redhat.com>
>
> 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.
Yes I agree with you. I derived the QTAILQ code without much thinking
about perf. Also in my case I expect the list to be short.
But as we want this code to be useful for other cases, I rewrote as you
suggested.
Thank you for your review.
Eric
>
>
> The rest of the patch looks ok to me.
>
> Later, Juan.
>
