[FFmpeg-devel] [PATCH 11/17] avutil/mem: Add av_fast_realloc_array()

[Michael Niedermayer]

On Thu, Dec 26, 2019 at 11:53:36AM +0100, Andreas Rheinhardt wrote:
> This is an array-equivalent of av_fast_realloc(). Its advantages
> compared to using av_fast_realloc() for allocating arrays are as
> follows:
> 
> a) It performs its own overflow checks for the multiplication that is
> implicit in array allocations. (And it only needs to perform these
> checks (as well as the multiplication itself) in case the array needs to
> be reallocated.)
> b) It guarantees to not allocated more than UINT_MAX - 1 elements, so
> the caller needn't check for overflow if the desired size is increased
> in steps of one.
> c) Should the caller have increased max_alloc_size, av_fast_realloc()
> could come in a situation where it allocates more than what fits into an
> unsigned. In this case the variable containing the allocated size (an
> unsigned) won't accurately reflect how much has been allocated. After
> this point, lots of reallocations will happen despite the buffer
> actually being big enough.
> d) av_fast_realloc_array() will always allocate in multiples of array
> elements; no memory is wasted with partial elements.
> 
> av_fast_realloc() usually allocates size + size / 16 + 32 bytes if size
> bytes are desired and if the already existing buffer isn't big enough.
> av_fast_realloc_array() instead allocates nb + (nb + 14) / 16. Rounding
> up is done in order not to reallocate in steps of one if the current
> number is < 16; adding 14 instead of 15 has the effect of only
> allocating one element if one element is desired. This is done with an
> eye towards applications where arrays might commonly only contain one
> element (as happens with the Matroska CueTrackPositions).
> 
> Which of the two functions allocates faster depends upon the size of
> the elements. E.g. if the elements have a size of 32B and the desired
> size is incremented in steps of one, allocations happen at
> 1, 3, 5, 7, 9, 11, 13, 15, 17, 20, 23, 26 ... for av_fast_realloc(),
> 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 21, 24 ... for
> av_fast_realloc_array(). For element sizes of 96B, the numbers are
> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 21, 23, 25, 27, 30 ...
> for av_fast_realloc() whereas the pattern for av_fast_realloc_array() is
> unchanged.
> 
> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt at gmail.com>
> ---
> a) In most places where av_fast_realloc is currently used to reallocate an
> array the number of valid entries is stored in a variable of type int.
> This patch uses unsigned, because negative values make no sense and because
> av_fast_realloc already uses unsigned for the number of allocated bytes.
> But this means that when this function is used to replace
> av_fast_realloc (like in the patch in the Matroska demuxer in this
> patchset), the types of several other variables must be changed. If one
> used int for both, one could avoid this, but then one would either have
> to ignore the possibility of negative values or check for them and I
> like neither of these two possibilities.

using INT_MAX instead of UINT_MAX would solve this indepenandt of the
argument type.
And considering that most arrays we have are indexed by int type arguments.
If we use an arbitrary limit INT_MAX seems the more robust choice than UINT_MAX

thx

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

It is dangerous to be right in matters on which the established authorities
are wrong. -- Voltaire
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20191226/8df116d4/attachment.sig>