Re: [PATCH v3] migration: Support QLIST migration

[Auger Eric]

Hi Juan,

On 10/17/19 10:06 AM, Juan Quintela wrote:
> Eric Auger <address@hidden> 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 <address@hidden>
> 
> 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.
>