From patchwork Thu Dec 26 10:53:36 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Rheinhardt X-Patchwork-Id: 16970 Return-Path: X-Original-To: patchwork@ffaux-bg.ffmpeg.org Delivered-To: patchwork@ffaux-bg.ffmpeg.org Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by ffaux.localdomain (Postfix) with ESMTP id 18CF0449EFF for ; Thu, 26 Dec 2019 12:54:22 +0200 (EET) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id F142268AC2C; Thu, 26 Dec 2019 12:54:21 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-wm1-f67.google.com (mail-wm1-f67.google.com [209.85.128.67]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id EB2C768ABF3 for ; Thu, 26 Dec 2019 12:54:18 +0200 (EET) Received: by mail-wm1-f67.google.com with SMTP id c127so4884944wme.1 for ; Thu, 26 Dec 2019 02:54:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=oy5gLLpR5dBHBmBWjXscTDycmrJ0dgks2v3/NMAKgYU=; b=TcuBji0jhktUm5W1tABItU6M3CQNSwtjK+hcPUKdDEWDBZQGKmXeLP3/qpdWdltErX IQj8HhxkO3NaRy+bbLVow7zhKZHpxP+DdJbwGSLpnqE07Me9U0zcmzuxXRovXTjhyPjc rBMeuAzkB5kPVTb4DxXpLehen7oF72DfvxVlv0DBk1CqIiQ+fHkrs6K7VPMSrssvT4CN tgVktidxsKIrKWf/30eIzVOch+oUn7NXNJVRG41GOra3UhZvKaW+z7sTNi+f/ZgMyzn2 TExDzYiRn/kAAGJFcjEtjR/lwU5wobrAyiygqGYW4tie/mhdUPy80lzC/dpHCBSChCgw JM+A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=oy5gLLpR5dBHBmBWjXscTDycmrJ0dgks2v3/NMAKgYU=; b=hkJjla/DVPXTZ+G9YkIlcxVIAXWwGCnmVcokHQoRdSILmSXODZFsKzFAVUPFpRmpyz zmj3o/RAaJH9XbQQhlierkpwzv6qJZi0zRRPY57bjFQgRFzh+kSaN4n67Y6lRO/4sB6H 7dPQ7D55BoomL34K5qiHv5j9ofIGsCa7a/4H4xGjovcCiUp7m4rOmGn3jKBkeQLP7sM0 lF0g+0qP1zsc0AAYT0M3Qy9u9KE33PxR2u3a31Sa1Yk26v8ZF4MNTNUa20H7BbZzzEcv Yx3O7YOLdFwzA7RfUtFwrVVBtmJAOBDi9PNIV2Ui4xKa5lbwKeNXXnIsuZDznyvjpIiS 22+w== X-Gm-Message-State: APjAAAXma8ZD076OJ7cUE4dkMJF1K/ud9M8mNiiUXisnAxjhOmXTyUzN iCTtqdDLCkbD8CZBQ1rdMKrCDqGE X-Google-Smtp-Source: APXvYqy5Yx9Nb12IMHMxw56za5xKmalpvZeTfo+CFi6z+EMtgPHNsF7i2lNTV2pX3+C8xWxh/4k3Nw== X-Received: by 2002:a1c:48c1:: with SMTP id v184mr13907116wma.5.1577357656794; Thu, 26 Dec 2019 02:54:16 -0800 (PST) Received: from sblaptop.fritz.box (ipbcc10203.dynamic.kabel-deutschland.de. [188.193.2.3]) by smtp.gmail.com with ESMTPSA id c68sm7997618wme.13.2019.12.26.02.54.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 26 Dec 2019 02:54:16 -0800 (PST) From: Andreas Rheinhardt To: ffmpeg-devel@ffmpeg.org Date: Thu, 26 Dec 2019 11:53:36 +0100 Message-Id: <20191226105342.11175-11-andreas.rheinhardt@gmail.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20191226105342.11175-1-andreas.rheinhardt@gmail.com> References: <20191226105342.11175-1-andreas.rheinhardt@gmail.com> MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH 11/17] avutil/mem: Add av_fast_realloc_array() X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Cc: Andreas Rheinhardt Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" 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 --- 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. b) As can be seen from the code, the allocation limit is even lower than UINT_MAX - 1. This can of course be easily lifted if desired; it's only done because I don't see a need for such big arrays. doc/APIchanges | 3 +++ libavutil/mem.c | 30 ++++++++++++++++++++++++++++++ libavutil/mem.h | 30 ++++++++++++++++++++++++++++++ libavutil/version.h | 4 ++-- 4 files changed, 65 insertions(+), 2 deletions(-) diff --git a/doc/APIchanges b/doc/APIchanges index 401c65a753..7c64755650 100644 --- a/doc/APIchanges +++ b/doc/APIchanges @@ -15,6 +15,9 @@ libavutil: 2017-10-21 API changes, most recent first: +2019-12-25 - xxxxxxxxxx - lavu 56.37.100 - mem.h + Add av_fast_realloc_array(). + 2019-11-17 - 1c23abc88f - lavu 56.36.100 - eval API Add av_expr_count_vars(). 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 e18163388d..4de0fa1fc3 100644 --- a/libavutil/version.h +++ b/libavutil/version.h @@ -79,8 +79,8 @@ */ #define LIBAVUTIL_VERSION_MAJOR 56 -#define LIBAVUTIL_VERSION_MINOR 36 -#define LIBAVUTIL_VERSION_MICRO 101 +#define LIBAVUTIL_VERSION_MINOR 37 +#define LIBAVUTIL_VERSION_MICRO 100 #define LIBAVUTIL_VERSION_INT AV_VERSION_INT(LIBAVUTIL_VERSION_MAJOR, \ LIBAVUTIL_VERSION_MINOR, \