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

Andreas Rheinhardt andreas.rheinhardt at gmail.com
Thu Dec 26 21:04:07 EET 2019


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>
---
I missed that Marton has already pushed his patch for avutil/buffer
which also included changes to doc/APIchanges and the lavu version
number. Therefore I am resending this to solve the ensuing merge
conflict.

 doc/APIchanges      |  3 +++
 libavutil/mem.c     | 30 ++++++++++++++++++++++++++++++
 libavutil/mem.h     | 30 ++++++++++++++++++++++++++++++
 libavutil/version.h |  2 +-
 4 files changed, 64 insertions(+), 1 deletion(-)

diff --git a/doc/APIchanges b/doc/APIchanges
index 5b8d801f06..b7cede329a 100644
--- a/doc/APIchanges
+++ b/doc/APIchanges
@@ -15,6 +15,9 @@ libavutil:     2017-10-21
 
 API changes, most recent first:
 
+2019-12-26 - xxxxxxxxxx - lavu 56.38.100 - mem.h
+  Add av_fast_realloc_array().
+
 2019-12-xx - xxxxxxxxxx - lavu 56.37.100 - buffer.h
   Add av_buffer_pool_buffer_get_opaque().
 
diff --git a/libavutil/mem.c b/libavutil/mem.c
index 88fe09b179..151ab586c4 100644
--- a/libavutil/mem.c
+++ b/libavutil/mem.c
@@ -497,6 +497,36 @@ void *av_fast_realloc(void *ptr, unsigned int *size, size_t min_size)
     return ptr;
 }
 
+void *av_fast_realloc_array(void *ptr, unsigned *nb_allocated,
+                            unsigned min_nb, size_t elsize)
+{
+    unsigned max_nb, nb;
+
+    if (min_nb <= *nb_allocated)
+        return ptr;
+
+    /* The 16 / 17 implies that we do not need to check
+     * for overflow in the calculation of nb below. */
+    max_nb = FFMIN((UINT_MAX - 1) * 16 / 17, (max_alloc_size - 32) / elsize);
+
+    if (min_nb > max_nb) {
+        *nb_allocated = 0;
+        return NULL;
+    }
+
+    nb = FFMIN(max_nb, min_nb + (min_nb + 14) / 16);
+
+    ptr = av_realloc(ptr, nb * elsize);
+    /* We could keep *nb_allocated in case of failure, but this is safer
+     * if the user lost the ptr and uses NULL now. */
+    if (!ptr)
+        nb = 0;
+
+    *nb_allocated = nb;
+
+    return ptr;
+}
+
 void av_fast_malloc(void *ptr, unsigned int *size, size_t min_size)
 {
     ff_fast_malloc(ptr, size, min_size, 0);
diff --git a/libavutil/mem.h b/libavutil/mem.h
index 5fb1a02dd9..539a030387 100644
--- a/libavutil/mem.h
+++ b/libavutil/mem.h
@@ -370,11 +370,41 @@ int av_reallocp_array(void *ptr, size_t nmemb, size_t size);
  * @return `ptr` if the buffer is large enough, a pointer to newly reallocated
  *         buffer if the buffer was not large enough, or `NULL` in case of
  *         error
+ * @see av_fast_realloc_array()
  * @see av_realloc()
  * @see av_fast_malloc()
  */
 void *av_fast_realloc(void *ptr, unsigned int *size, size_t min_size);
 
+/**
+ * Reallocate the given array if it is not large enough, otherwise do nothing.
+ *
+ * If the given array is `NULL`, then a new uninitialized array is allocated.
+ *
+ * If the given array is not large enough, and reallocation fails, `NULL` is
+ * returned and `*nb_allocated` is set to 0, but the original array is not
+ * changed or freed.
+ *
+ * @param[in,out] ptr           Already allocated array, or `NULL`
+ * @param[in,out] nb_allocated  Pointer to the number of elements of the array
+ *                              `ptr`. `*nb_allocated` is updated to the new
+ *                              number of allocated elements, in particular 0
+ *                              in case of failure.
+ * @param[in]     min_nb        Desired minimal amount of elements in array `ptr`
+ * @param[in]     elsize        Size of a single element of the array.
+ *                              Must not be zero.
+ * @return `ptr` if the array is large enough, a pointer to newly reallocated
+ *         array if the array was not large enough, or `NULL` in case of
+ *         error
+ * @note This function will never allocate more than `UINT_MAX - 1` elements,
+ *       so incrementing in steps of one need not be checked for overflow.
+ * @see av_fast_realloc()
+ * @see av_realloc()
+ * @see av_fast_malloc()
+ */
+void *av_fast_realloc_array(void *ptr, unsigned *nb_allocated,
+                            unsigned min_nb, size_t elsize);
+
 /**
  * Allocate a buffer, reusing the given one if large enough.
  *
diff --git a/libavutil/version.h b/libavutil/version.h
index 4de0fa1fc3..af8f614aff 100644
--- a/libavutil/version.h
+++ b/libavutil/version.h
@@ -79,7 +79,7 @@
  */
 
 #define LIBAVUTIL_VERSION_MAJOR  56
-#define LIBAVUTIL_VERSION_MINOR  37
+#define LIBAVUTIL_VERSION_MINOR  38
 #define LIBAVUTIL_VERSION_MICRO 100
 
 #define LIBAVUTIL_VERSION_INT   AV_VERSION_INT(LIBAVUTIL_VERSION_MAJOR, \
-- 
2.20.1



More information about the ffmpeg-devel mailing list