From patchwork Wed Jun 29 15:25:32 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12900299 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 25AFFC433EF for ; Wed, 29 Jun 2022 15:25:57 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234072AbiF2PZz (ORCPT ); Wed, 29 Jun 2022 11:25:55 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37074 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234165AbiF2PZn (ORCPT ); Wed, 29 Jun 2022 11:25:43 -0400 Received: from mail-wm1-x331.google.com (mail-wm1-x331.google.com [IPv6:2a00:1450:4864:20::331]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C73F933EB1 for ; Wed, 29 Jun 2022 08:25:38 -0700 (PDT) Received: by mail-wm1-x331.google.com with SMTP id u12-20020a05600c210c00b003a02b16d2b8so9827932wml.2 for ; Wed, 29 Jun 2022 08:25:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=pyTDyHG/r3HDiqTRrfYUdwnY/9t53YoZ0wyo4fJc38E=; b=d59wmDersz7cJj8+hJRDJ6MctaLC/6QG6uXJOE1QCqkQex9eTfsKIqN22+CTDjkX+t 7uixH72x+3rla+eNBVQm0aSJflhSrKsHRppmYP9k2bxdXA4TZUnmzu4G8kKeDJauUwZG swo5CtA8J1qtgGeWzt/1W1WV7FCAzoDw87vr+ej7AXcxzIpUQI+2y0yzX+ZZ0jBk76Zf O7IqR9qVOCvwKmx7fczah/bs7cwTnrwdbWzq7f2qY1k7taEKDr30nvIzca2Ya75IC6Eq veqN/8FuAYd9VmWNv3x52JoMD1dNZua5tPnmDEZoBYXABsy//1EvT7iseUKMwuSuO6jO A2CA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=pyTDyHG/r3HDiqTRrfYUdwnY/9t53YoZ0wyo4fJc38E=; b=RqIT7qO7pCHwCIAZyjA4CzQmouaPq1KtjSi5t2+rR2mU/bMUeaGwHccRIbK3GC9Rgy RWQtduo7p5z/qHXN102AzsG+kYpjhEG6hFLmaVhAIubsi+hsYQ6WpPJZU555vuADtJki 9qpEDrxODqGMUl0hpoVH48PR10I71iHTAJ2VL2jAihTGupgeg2jueM0sH7WZbznAnwDM p5iv2vQasH8GLFAE03X9o/cGhYxOIhdwofmkR31glg/WykGsHieKJjLx7ou3u5fnvQOR 4HFghuakkgJBozF/BJsbn2ZMrjoQ9Pa20AlG1d7uAhqiacS+p1x44wkEHWYt2uY22M1E 0GOA== X-Gm-Message-State: AJIora+pplE2eeGtEF0dm5bj8Ieg4VK8FQ1qOEkrntKwHtKOEJf16XB2 IryMw4qLurC4waO3t+IC2ct33byPuWQMTA== X-Google-Smtp-Source: AGRyM1teCKdSr5BxShE+Y7JWuP+nb40EHCFVKfGSYzcAjYH8K/zNQz1jR9ZjF+YaxRnua/41+hz2qA== X-Received: by 2002:a1c:f305:0:b0:39c:4840:ab42 with SMTP id q5-20020a1cf305000000b0039c4840ab42mr6122714wmq.148.1656516336624; Wed, 29 Jun 2022 08:25:36 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j13-20020a05600c190d00b003973ea7e725sm5104525wmq.0.2022.06.29.08.25.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 29 Jun 2022 08:25:35 -0700 (PDT) Message-Id: <55fd62dc27d2bccfdb8ac300be23fc33d1795366.1656516334.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 29 Jun 2022 15:25:32 +0000 Subject: [PATCH 1/3] xdiff: introduce XDL_ALLOC_ARRAY() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood Add a helper to allocate an array that automatically calculates the allocation size. This is analogous to ALLOC_ARRAY() in the rest of the codebase but returns NULL if the allocation fails to accommodate other users of libxdiff such as libgit2. The helper will also return NULL if the multiplication in the allocation calculation overflows. Signed-off-by: Phillip Wood --- xdiff/xdiffi.c | 2 +- xdiff/xmacros.h | 5 +++++ xdiff/xpatience.c | 4 ++-- xdiff/xprepare.c | 8 ++++---- 4 files changed, 12 insertions(+), 7 deletions(-) diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c index 758410c11ac..53e803e6bcb 100644 --- a/xdiff/xdiffi.c +++ b/xdiff/xdiffi.c @@ -337,7 +337,7 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, * One is to store the forward path and one to store the backward path. */ ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3; - if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) { + if (!XDL_ALLOC_ARRAY(kvd, 2 * ndiags + 2)) { xdl_free_env(xe); return -1; diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h index ae4636c2477..9fd3c5da91a 100644 --- a/xdiff/xmacros.h +++ b/xdiff/xmacros.h @@ -49,5 +49,10 @@ do { \ ((unsigned long) __p[2]) << 16 | ((unsigned long) __p[3]) << 24; \ } while (0) +/* Allocate an array of nr elements, returns NULL on failure */ +#define XDL_ALLOC_ARRAY(p, nr) \ + ((p) = SIZE_MAX / sizeof(*(p)) >= (size_t)(nr) \ + ? xdl_malloc((nr) * sizeof(*(p))) \ + : NULL) #endif /* #if !defined(XMACROS_H) */ diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index 1a21c6a74b3..ce87b9084ca 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -200,7 +200,7 @@ static int binary_search(struct entry **sequence, int longest, */ static int find_longest_common_sequence(struct hashmap *map, struct entry **res) { - struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *)); + struct entry **sequence; int longest = 0, i; struct entry *entry; @@ -211,7 +211,7 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res) */ int anchor_i = -1; - if (!sequence) + if (!XDL_ALLOC_ARRAY(sequence, map->nr)) return -1; for (entry = map->first; entry; entry = entry->next) { diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index 105752758f2..25866a1667a 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c @@ -86,7 +86,7 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) { memset(cf->rchash, 0, cf->hsize * sizeof(xdlclass_t *)); cf->alloc = size; - if (!(cf->rcrecs = (xdlclass_t **) xdl_malloc(cf->alloc * sizeof(xdlclass_t *)))) { + if (!XDL_ALLOC_ARRAY(cf->rcrecs, cf->alloc)) { xdl_free(cf->rchash); xdl_cha_free(&cf->ncha); @@ -178,7 +178,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0) goto abort; - if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) + if (!XDL_ALLOC_ARRAY(recs, narec)) goto abort; hbits = xdl_hashbits((unsigned int) narec); @@ -215,9 +215,9 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) { - if (!(rindex = xdl_malloc((nrec + 1) * sizeof(*rindex)))) + if (!XDL_ALLOC_ARRAY(rindex, nrec + 1)) goto abort; - if (!(ha = xdl_malloc((nrec + 1) * sizeof(*ha)))) + if (!XDL_ALLOC_ARRAY(ha, nrec + 1)) goto abort; } From patchwork Wed Jun 29 15:25:33 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12900300 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id CC0E7C43334 for ; Wed, 29 Jun 2022 15:25:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234165AbiF2PZ5 (ORCPT ); Wed, 29 Jun 2022 11:25:57 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37532 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234192AbiF2PZv (ORCPT ); Wed, 29 Jun 2022 11:25:51 -0400 Received: from mail-wr1-x42d.google.com (mail-wr1-x42d.google.com [IPv6:2a00:1450:4864:20::42d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 18FF9344EF for ; Wed, 29 Jun 2022 08:25:40 -0700 (PDT) Received: by mail-wr1-x42d.google.com with SMTP id q9so23019199wrd.8 for ; Wed, 29 Jun 2022 08:25:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=J1UhH9HhQtWzjHtCaczDyQe98YD3U/bG5Y7eiJJmwdc=; b=nrPLFVI0yOB0dNshqadXE39kl/Ij3OVBycwjmc37wI+tUVP7Uz5vsfPFs5RTreXW+u zuQ8E6I1NUmbjNzIps6cVcRw8BJa74evAGXg5gCYgyWCSNryGmqE6JktSl8hEqFrbDEV Qrt2ijXnvgf0K/N2kXS84GF7DrgbwoeoomvUhrolwwIyAXD6JnbL/5g0V1dbsESkPfc9 PRDdCH/LxBJSIRsYFNDsACAjAsHQG/MXA8fF0Dbc3Vu0GGX/Me/6mBhEdycjKbA2aXa/ fsKe4r8ixBlPEPJejd6RN91FfMeTWFkJyquTYNmqgbNTdQ19P35RhddI8+JPRqkHkS3Y BklA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=J1UhH9HhQtWzjHtCaczDyQe98YD3U/bG5Y7eiJJmwdc=; b=a+N7Dig7q0BUIshAOiTU/fWPjw8ymL0ctZh8hRIhIMj42q6ft416uAv+rMvlDuhRPl ubCUrc71UzNeQxZQSlgLdOymMv8579VpxbFAAPuZBcooCs/lrIBcYfGFa2Eih5HmgxNv B5nl5WYPoxvAKZO62wrUH9F+8PJaul0TOdkZrJ1FI2kcdkIk9UZdM0VmJJI+zCqH9KgQ 0D/BFRfqDeoMW+pveTkcujkyYM0WSq5uZ99NqQtbwaWeBvaUtswEY34CexIVrxQ6Kyu1 U+ehY/CT6rJPBZpEMDFKKJEu+U59otMQoNYqWSSv+JJbU46aP9RhZ1DONSjYAn1CTkCx Edmg== X-Gm-Message-State: AJIora/N/RCqe/G3MslWDcOpR0Vi5+XagwakzDP8d+OzEuIM6JgF7yJo U4J9+kX1gDpP28zfDGWDNCEePvwhdsXYsA== X-Google-Smtp-Source: AGRyM1s/vMNmW+LiVpCJg+Li0W27PldJvQNMZhDf8lK0UF6fMn5uXEObe2p9/pgv1jQ7klldTZl3UA== X-Received: by 2002:a05:6000:1446:b0:21d:27ea:5a01 with SMTP id v6-20020a056000144600b0021d27ea5a01mr3770509wrx.314.1656516337722; Wed, 29 Jun 2022 08:25:37 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id t3-20020a0560001a4300b0021b9cc87aa9sm17198887wry.111.2022.06.29.08.25.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 29 Jun 2022 08:25:36 -0700 (PDT) Message-Id: <8bead9856be7b39d3d03f688f53d678832d60109.1656516334.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 29 Jun 2022 15:25:33 +0000 Subject: [PATCH 2/3] xdiff: introduce XDL_CALLOC_ARRAY() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood Add a helper for allocating an array and initialize the elements to zero. This is analogous to CALLOC_ARRAY() in the rest of the codebase but it returns NULL on allocation failures rather than dying to accommodate other users of libxdiff such as libgit2. Signed-off-by: Phillip Wood --- xdiff/xhistogram.c | 19 ++++++------------- xdiff/xmacros.h | 6 ++++++ xdiff/xpatience.c | 5 +---- xdiff/xprepare.c | 14 ++++---------- 4 files changed, 17 insertions(+), 27 deletions(-) diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c index 01decffc332..df909004c10 100644 --- a/xdiff/xhistogram.c +++ b/xdiff/xhistogram.c @@ -251,7 +251,7 @@ static int find_lcs(xpparam_t const *xpp, xdfenv_t *env, int line1, int count1, int line2, int count2) { int b_ptr; - int sz, ret = -1; + int ret = -1; struct histindex index; memset(&index, 0, sizeof(index)); @@ -265,23 +265,16 @@ static int find_lcs(xpparam_t const *xpp, xdfenv_t *env, index.rcha.head = NULL; index.table_bits = xdl_hashbits(count1); - sz = index.records_size = 1 << index.table_bits; - sz *= sizeof(struct record *); - if (!(index.records = (struct record **) xdl_malloc(sz))) + index.records_size = 1 << index.table_bits; + if (!XDL_CALLOC_ARRAY(index.records, index.records_size)) goto cleanup; - memset(index.records, 0, sz); - sz = index.line_map_size = count1; - sz *= sizeof(struct record *); - if (!(index.line_map = (struct record **) xdl_malloc(sz))) + index.line_map_size = count1; + if (!XDL_CALLOC_ARRAY(index.line_map, index.line_map_size)) goto cleanup; - memset(index.line_map, 0, sz); - sz = index.line_map_size; - sz *= sizeof(unsigned int); - if (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz))) + if (!XDL_CALLOC_ARRAY(index.next_ptrs, index.line_map_size)) goto cleanup; - memset(index.next_ptrs, 0, sz); /* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */ if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0) diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h index 9fd3c5da91a..23db8e785d7 100644 --- a/xdiff/xmacros.h +++ b/xdiff/xmacros.h @@ -55,4 +55,10 @@ do { \ ? xdl_malloc((nr) * sizeof(*(p))) \ : NULL) +/* Allocate an array of nr zeroed out elements, returns NULL on failure */ +#define XDL_CALLOC_ARRAY(p, nr) \ + (XDL_ALLOC_ARRAY((p), (nr)) \ + ? memset((p), 0, (nr) * sizeof(*(p))) \ + : NULL) + #endif /* #if !defined(XMACROS_H) */ diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index ce87b9084ca..fe39c2978cb 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -151,11 +151,8 @@ static int fill_hashmap(mmfile_t *file1, mmfile_t *file2, /* We know exactly how large we want the hash map */ result->alloc = count1 * 2; - result->entries = (struct entry *) - xdl_malloc(result->alloc * sizeof(struct entry)); - if (!result->entries) + if (!XDL_CALLOC_ARRAY(result->entries, result->alloc)) return -1; - memset(result->entries, 0, result->alloc * sizeof(struct entry)); /* First, fill with entries from the first file */ while (count1--) diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index 25866a1667a..b016570c488 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c @@ -78,12 +78,11 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) { return -1; } - if (!(cf->rchash = (xdlclass_t **) xdl_malloc(cf->hsize * sizeof(xdlclass_t *)))) { + if (!XDL_CALLOC_ARRAY(cf->rchash, cf->hsize)) { xdl_cha_free(&cf->ncha); return -1; } - memset(cf->rchash, 0, cf->hsize * sizeof(xdlclass_t *)); cf->alloc = size; if (!XDL_ALLOC_ARRAY(cf->rcrecs, cf->alloc)) { @@ -183,9 +182,8 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ hbits = xdl_hashbits((unsigned int) narec); hsize = 1 << hbits; - if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *)))) + if (!XDL_CALLOC_ARRAY(rhash, hsize)) goto abort; - memset(rhash, 0, hsize * sizeof(xrecord_t *)); nrec = 0; if ((cur = blk = xdl_mmfile_first(mf, &bsize))) { @@ -209,9 +207,8 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ } } - if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char)))) + if (!XDL_CALLOC_ARRAY(rchg, nrec + 2)) goto abort; - memset(rchg, 0, (nrec + 2) * sizeof(char)); if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) { @@ -383,11 +380,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd xdlclass_t *rcrec; char *dis, *dis1, *dis2; - if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) { - + if (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2)) return -1; - } - memset(dis, 0, xdf1->nrec + xdf2->nrec + 2); dis1 = dis; dis2 = dis1 + xdf1->nrec + 1; From patchwork Wed Jun 29 15:25:34 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12900301 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id B957AC43334 for ; Wed, 29 Jun 2022 15:26:08 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234324AbiF2P0I (ORCPT ); Wed, 29 Jun 2022 11:26:08 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37174 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234086AbiF2PZw (ORCPT ); Wed, 29 Jun 2022 11:25:52 -0400 Received: from mail-wr1-x433.google.com (mail-wr1-x433.google.com [IPv6:2a00:1450:4864:20::433]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2B11D34668 for ; Wed, 29 Jun 2022 08:25:40 -0700 (PDT) Received: by mail-wr1-x433.google.com with SMTP id r20so23030809wra.1 for ; Wed, 29 Jun 2022 08:25:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:mime-version :content-transfer-encoding:fcc:to:cc; bh=QWxGaVIjA8wmer+PxC09zUmethOKMXlSyygC3bfXdyw=; b=JFLFZLklWsjrLNk5TebZGmmGRmowdt6LcwWG/Y0WqW9xGNAWIf6L/K8N8w/W+xNwYg g89HYHTUE7gh84W3w31CrRm/6JCAmqT/VHGzeKruAh6PuBD+5jG2gEi6mCQB6SYJ9YnL aVy9U84GYJNWjZeg1FzavOSbzPpwRkCG3M2ApmaU5uGbo5SbwZGvxHbFq/h3TMgefOXm 51Si/mAiRdrQGOyNr/qJHqpf6+JYnHQHt8JpVdV020pMekBOcPv/oiXL6wh5icw1oWCo 69L24WmHJALGdE3w0FI2whR4CIkQD2ecXcYofzj2LBTIlNAI25ofTWk4h08X/XtOjgor CRag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:mime-version:content-transfer-encoding:fcc:to:cc; bh=QWxGaVIjA8wmer+PxC09zUmethOKMXlSyygC3bfXdyw=; b=f69SdlWUG0DZKvEejMFNZU+8+EMGdA+Evn0xd8O8CAcSy9s6BXsLe/pzBlz2/ry28o BbQJl4YMJmJhOXSspWr5nHcW/XSWdwLfjxV3O0lgyfqDLpzTN1ums7h0us0P2I5EsRKI tZ5EDSP5YZ9xg9Dl1vLGlnKGYLOA+ejiEfCkwo2v2zjR94jYIphAjS7J+8G3sfMW9MQD 8YMH/5/lv72pxn0IsZsck82WzsZrXfxgjTAtCCPCrROQLrbpct6yxRxZyMz50Y39j3hM wZx4yGGk0O8PEz83HccA+VU0p9eSmoOplCvvs/5eRhxZkbOl4vN/92elpL3XlZh6icX5 JPuQ== X-Gm-Message-State: AJIora+U+SggtqVmpibmiwg5Wjv3VEGZr+c6hU11KoIxzdzL1Nw9Gvmw 1fdw/7cmLgumZ4kRmEaiTAEMB+Rj2VFaVg== X-Google-Smtp-Source: AGRyM1sHboKnt0e8LpiFKXcHMrFhD4xUZKDCIhPBl0zWrcjJc8wTJ1KiXv9XR1H2OBrZGcTDeuWpdA== X-Received: by 2002:a5d:5481:0:b0:21a:3573:def0 with SMTP id h1-20020a5d5481000000b0021a3573def0mr3575640wrv.28.1656516338890; Wed, 29 Jun 2022 08:25:38 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id e20-20020a5d5954000000b0020fcaba73bcsm17124023wri.104.2022.06.29.08.25.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 29 Jun 2022 08:25:38 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Wed, 29 Jun 2022 15:25:34 +0000 Subject: [PATCH 3/3] xdiff: introduce XDL_ALLOC_GROW() MIME-Version: 1.0 Fcc: Sent To: git@vger.kernel.org Cc: Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood Add a helper to grow an array. This is analogous to ALLOC_GROW() in the rest of the codebase but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2. It will also return a error if the multiplication overflows while calculating the new allocation size. Note that this keeps doubling on reallocation like the code it is replacing rather than increasing the existing size by half like ALLOC_GROW(). It does however copy ALLOC_GROW()'s trick of adding a small amount to the new allocation to avoid a lot of reallocations at small sizes. Signed-off-by: Phillip Wood --- xdiff/xmacros.h | 10 ++++++++++ xdiff/xprepare.c | 19 ++++--------------- xdiff/xutils.c | 17 +++++++++++++++++ xdiff/xutils.h | 3 ++- 4 files changed, 33 insertions(+), 16 deletions(-) diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h index 23db8e785d7..d13a6724629 100644 --- a/xdiff/xmacros.h +++ b/xdiff/xmacros.h @@ -61,4 +61,14 @@ do { \ ? memset((p), 0, (nr) * sizeof(*(p))) \ : NULL) +/* + * Ensure array p can accommodate at least nr elements, growing the + * array and updating alloc (which is the number of allocated + * elements) as necessary. Frees p and returns -1 on failure, returns + * 0 on success + */ +#define XDL_ALLOC_GROW(p, nr, alloc) \ + (-!((nr) <= (alloc) || \ + ((p) = xdl_alloc_grow_helper((p), (nr), &(alloc), sizeof(*(p)))))) + #endif /* #if !defined(XMACROS_H) */ diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index b016570c488..c84549f6c50 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c @@ -111,7 +111,6 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t long hi; char const *line; xdlclass_t *rcrec; - xdlclass_t **rcrecs; line = rec->ptr; hi = (long) XDL_HASHLONG(rec->ha, cf->hbits); @@ -127,14 +126,8 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t return -1; } rcrec->idx = cf->count++; - if (cf->count > cf->alloc) { - cf->alloc *= 2; - if (!(rcrecs = (xdlclass_t **) xdl_realloc(cf->rcrecs, cf->alloc * sizeof(xdlclass_t *)))) { - + if (XDL_ALLOC_GROW(cf->rcrecs, cf->count, cf->alloc)) return -1; - } - cf->rcrecs = rcrecs; - } cf->rcrecs[rcrec->idx] = rcrec; rcrec->line = line; rcrec->size = rec->size; @@ -163,7 +156,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ unsigned long hav; char const *blk, *cur, *top, *prev; xrecord_t *crec; - xrecord_t **recs, **rrecs; + xrecord_t **recs; xrecord_t **rhash; unsigned long *ha; char *rchg; @@ -190,12 +183,8 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ for (top = blk + bsize; cur < top; ) { prev = cur; hav = xdl_hash_record(&cur, top, xpp->flags); - if (nrec >= narec) { - narec *= 2; - if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *)))) - goto abort; - recs = rrecs; - } + if (XDL_ALLOC_GROW(recs, nrec + 1, narec)) + goto abort; if (!(crec = xdl_cha_alloc(&xdf->rcha))) goto abort; crec->ptr = prev; diff --git a/xdiff/xutils.c b/xdiff/xutils.c index 115b2b1640b..9e36f24875d 100644 --- a/xdiff/xutils.c +++ b/xdiff/xutils.c @@ -432,3 +432,20 @@ int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, return 0; } + +void* xdl_alloc_grow_helper(void *p, long nr, long *alloc, size_t size) +{ + void *tmp = NULL; + size_t n = ((LONG_MAX - 16) / 2 >= *alloc) ? 2 * *alloc + 16 : LONG_MAX; + if (nr > n) + n = nr; + if (SIZE_MAX / size >= n) + tmp = xdl_realloc(p, n * size); + if (tmp) { + *alloc = n; + } else { + xdl_free(p); + *alloc = 0; + } + return tmp; +} diff --git a/xdiff/xutils.h b/xdiff/xutils.h index fba7bae03c7..fd0bba94e8b 100644 --- a/xdiff/xutils.h +++ b/xdiff/xutils.h @@ -42,6 +42,7 @@ int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, int line1, int count1, int line2, int count2); - +/* Do not call this function, use XDL_ALLOC_GROW instead */ +void* xdl_alloc_grow_helper(void* p, long nr, long* alloc, size_t size); #endif /* #if !defined(XUTILS_H) */