[Qemu-devel] Re: [PATCH 1/4] Add a scatter-gather list type and accessors

[Avi Kivity <avi@redhat.com>]

Anthony Liguori wrote:
>>
>> malloc() will never fail on Linux with overcommit enabled; since 
>> Linux is fairly useless without overcommit, it means you'll never see 
>> a failure.
>
> Sure it will.  You just have to run out of VA space.
>

That's not recoverable, and is certainly a qemu bug if it happens.  
Especially on 47-bit hosts.

>>>> I expect this to trigger rarely since the allocation hint should 
>>>> suffice nearly 100% of the time.  But in case we miss, it's better 
>>>> to reallocate as little as possible.
>>>>
>>>> (what I really want is std::vector<>)
>>>
>>> Which I'm pretty sure has a linear growth strategy :-)
>>
>> Not in any of the implementations I'm familiar with.  I believe 
>> std::vector<> is required to have amortized O(1) append operations.
>
> Linear growth doesn't imply element-by-element growth.  You can have a 
> coefficient > 1.
>

If you have a coefficient, then it's exponential growth, even if it's 
less than two.  If you have an addition, then it's linear growth, even 
if the addend is greater than one.

  size *= k -> exponential
  size += k -> linear


-- 
I have a truly marvellous patch that fixes the bug which this
signature is too narrow to contain.