From patchwork Fri Jul 8 16:25:16 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12911448 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 EC59BC433EF for ; Fri, 8 Jul 2022 16:26:20 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239180AbiGHQ0S (ORCPT ); Fri, 8 Jul 2022 12:26:18 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34860 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S239243AbiGHQ0C (ORCPT ); Fri, 8 Jul 2022 12:26:02 -0400 Received: from mail-wm1-x329.google.com (mail-wm1-x329.google.com [IPv6:2a00:1450:4864:20::329]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3F8995C9C0 for ; Fri, 8 Jul 2022 09:25:24 -0700 (PDT) Received: by mail-wm1-x329.google.com with SMTP id o19-20020a05600c511300b003a2de48b4bbso91543wms.5 for ; Fri, 08 Jul 2022 09:25:24 -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=GpCdr+bWTbTkITp7S5m7Cnjjdw2zhhOllYYtDGz8z+3cYVcsCdD9y0xswTTbep7XjA mzYnY6IQ3dEuVadlaZMj2LcQqtSkvFHXPkPzu8ROYTEaQSpqT/JTZvIG2x2IrpTVvAof xeof0jN5uLTSu2+kf8+XwtwffdKF1tz3uXsVgPd1mRvqGxMK4uubSs/6pU9qJ7oPJdO2 6vxJ5B0ekukDmL0LPiLJpEdxLcoNCd/UYNeW38QvZdlczaRvMRCKPFa9B0m3qPwHn4vy u5fxnr04t3WFyCL7jiWXRRlcZGBds3Qgi/mxwZo+PqEOEz/+YC7SaHcTJwu6mdoAdnN2 EgBg== 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=cN/1+Sbqo53YRhQyQ5PkveFtAlmrM/1yun+w165e0YmZt7kC7Icd83nJEOSe21Hp5n LveG0T0az+SCE2tGDEcdm7o4DC5bLc0sVbJcJa0cUFchHm70oXwsEktOtSSvzsotIeeD YtXa+HhIW1ZNAz2vlJsHaG05oN9x6TYTn9wa3pE3nrsHjL5G3fL/fGkkFik2uTUTYQ7T hUUmOWOAQAyC9NZfpAbbgJDxGi4ZSRIlrBZ0CO/bWpHNXowv4RqKZDRrHu9hUYOq61GP G0vwHjj93ptAMYpgfEr6gNJO3Pf0R09K3EXzTjGM0X1BwwVh17icyx/XcwKXyw393BXF bcSA== X-Gm-Message-State: AJIora/AED8QN/lU0boGcsIZo8DdkpKXAALc/aEJV8PS1auNtAC6QDcE ypZjknuVPdJFoTP25yEmocK71KjScZc= X-Google-Smtp-Source: AGRyM1ufjYHylnEzBkx3xvbCNYMpD4/gUxnLHV24PR1VrCS1mLCiLjRSsrGBVkC99rxwQ5OmGHJJIg== X-Received: by 2002:a05:600c:3507:b0:3a1:9fbb:4d62 with SMTP id h7-20020a05600c350700b003a19fbb4d62mr600770wmq.161.1657297522474; Fri, 08 Jul 2022 09:25:22 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id q1-20020a1c4301000000b00397402ae674sm2638147wma.11.2022.07.08.09.25.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 08 Jul 2022 09:25:21 -0700 (PDT) Message-Id: <55fd62dc27d2bccfdb8ac300be23fc33d1795366.1657297520.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 08 Jul 2022 16:25:16 +0000 Subject: [PATCH v2 1/4] xdiff: introduce XDL_ALLOC_ARRAY() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: =?utf-8?b?w4Z2YXIgQXJuZmrDtnLDsA==?= Bjarmason , Phillip Wood , 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 Fri Jul 8 16:25:17 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12911447 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 402D5C43334 for ; Fri, 8 Jul 2022 16:26:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239353AbiGHQ0R (ORCPT ); Fri, 8 Jul 2022 12:26:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36512 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S239242AbiGHQ0C (ORCPT ); Fri, 8 Jul 2022 12:26:02 -0400 Received: from mail-wm1-x32e.google.com (mail-wm1-x32e.google.com [IPv6:2a00:1450:4864:20::32e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5E7D06D562 for ; Fri, 8 Jul 2022 09:25:25 -0700 (PDT) Received: by mail-wm1-x32e.google.com with SMTP id o16-20020a05600c379000b003a02eaea815so1166005wmr.0 for ; Fri, 08 Jul 2022 09:25:25 -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=dD85s/bxXv2q7lM4F7b9Vqnw0iZFNEaYnrxuhLyqNcM=; b=kCqpPmi0cXRhQhwjbfeXGBZ2KS2kcnaLGAFDk6WzDP/GS3KecqTNNCO1MIiGEayz6R 858HcITcVMsRnXxZUgZSsRumwd5pzZXTJ5s+uxuWj0oKn5FrvJT8PNHIVyCTLCvM1C9E PwfVnEkfrRQxxu9E4Cbc/ZzQ2xlOQA4sVl4k0WA6HmapIlBGY+Ai3VL0XGw0oJsX9b1p zGsDFo7T3xy3GJ2kfVtToOWdHQRCEvT1sjk9wiKAWhCur7wRDAfrGgzuQK7BsAg7BrDn IIcFjp2FJl11Nlo0ZClkvSoUeZbUgr2WYPoIDEVkvh/Y/lOD4EGGAX5Na0o4hOyBGPLV sVFQ== 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=dD85s/bxXv2q7lM4F7b9Vqnw0iZFNEaYnrxuhLyqNcM=; b=Ti8MaQ42NOzWsIO0O7ug9UcRlm8Q70EVfV4bLNGBVw1DJa0WgbINlYS3aWmYfALJ/P BV4UdrUdy0TJatJUfbPblP1tE0JrvB+TpjHus9emFZlbR5erqKbb2zej5RNfzgvT/dfu qythj3yuyHukbNeJ0/BEw5d9+HRPgV+PQzUG0vSGVwVpmEaoEGq4LWtsFGkBJFH6xe8+ DG5YlVv1gCwseauCWwRXB6WYsHlZ+jMEWED1ejPMtZb5rPBKke6yZpb2pO7bRM8iaFqI 1X3sfDLvOpklIrubA8hz6REz+/0hRLAZqjV2LPtodQ7ngo0UJG0DjW4dBcyivRMl/nfB ZjXA== X-Gm-Message-State: AJIora9U02moiAs7J2FpACrgcUm1QFvts0QPqWqCEIL4yn6/FvZZmlDD iH7z+30/iCmKmSWAj4uRxM33Qc0sXEE= X-Google-Smtp-Source: AGRyM1tJii/o/kJJOxMFbtrUUi0XBMi9yl9QWW7zjq8nDZMb7AS2YUscHYPLxweL99mUM42o3MQhrg== X-Received: by 2002:a05:600c:a192:b0:3a0:433a:9ca with SMTP id id18-20020a05600ca19200b003a0433a09camr691047wmb.108.1657297523529; Fri, 08 Jul 2022 09:25:23 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id co20-20020a0560000a1400b0021cf31e1f7csm5447581wrb.102.2022.07.08.09.25.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 08 Jul 2022 09:25:23 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Fri, 08 Jul 2022 16:25:17 +0000 Subject: [PATCH v2 2/4] xdiff: introduce xdl_calloc Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: =?utf-8?b?w4Z2YXIgQXJuZmrDtnLDsA==?= Bjarmason , Phillip Wood , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood In preparation for introducing XDL_CALLOC_ARRAY() use calloc() to obtain zeroed out memory rather than malloc() followed by memset(). To try and keep the lines a reasonable length this commit also stops casting the pointer returned by calloc() as this is unnecessary. Signed-off-by: Phillip Wood --- xdiff/xdiff.h | 1 + xdiff/xhistogram.c | 22 +++++++++------------- xdiff/xpatience.c | 4 +--- xdiff/xprepare.c | 12 ++++-------- 4 files changed, 15 insertions(+), 24 deletions(-) diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index 72e25a9ffa5..bb56b23f34c 100644 --- a/xdiff/xdiff.h +++ b/xdiff/xdiff.h @@ -120,6 +120,7 @@ typedef struct s_bdiffparam { #define xdl_malloc(x) xmalloc(x) +#define xdl_calloc(n, sz) xcalloc(n, sz) #define xdl_free(ptr) free(ptr) #define xdl_realloc(ptr,x) xrealloc(ptr,x) diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c index 01decffc332..c97edc1e29e 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,19 @@ 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 (!(index.records = xdl_calloc(index.records_size, + sizeof(*index.records)))) 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 (!(index.line_map = xdl_calloc(index.line_map_size, + sizeof(*index.line_map)))) 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 (!(index.next_ptrs = xdl_calloc(index.line_map_size, + sizeof(*index.next_ptrs)))) 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/xpatience.c b/xdiff/xpatience.c index ce87b9084ca..94f8886dd14 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -151,11 +151,9 @@ 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)); + result->entries = xdl_calloc(result->alloc, sizeof(*result->entries)); if (!result->entries) 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..45190e59fc8 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 (!(cf->rchash = xdl_calloc(cf->hsize, sizeof(*cf->rchash)))) { 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 (!(rhash = xdl_calloc(hsize, sizeof(*rhash)))) 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 (!(rchg = xdl_calloc((nrec + 2), sizeof(*rchg)))) 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,10 @@ 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 (!(dis = xdl_calloc(xdf1->nrec + xdf2->nrec + 2, sizeof(*dis)))) { return -1; } - memset(dis, 0, xdf1->nrec + xdf2->nrec + 2); dis1 = dis; dis2 = dis1 + xdf1->nrec + 1; From patchwork Fri Jul 8 16:25:18 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12911450 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 32002C433EF for ; Fri, 8 Jul 2022 16:26:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239183AbiGHQ0X (ORCPT ); Fri, 8 Jul 2022 12:26:23 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35856 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S239286AbiGHQ0C (ORCPT ); Fri, 8 Jul 2022 12:26:02 -0400 Received: from mail-wr1-x42e.google.com (mail-wr1-x42e.google.com [IPv6:2a00:1450:4864:20::42e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 645B5DEE for ; Fri, 8 Jul 2022 09:25:26 -0700 (PDT) Received: by mail-wr1-x42e.google.com with SMTP id s1so31233019wra.9 for ; Fri, 08 Jul 2022 09:25:26 -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=ab6DNjlfCGaxlfSosFC6Vg+UX4p6nTgmto90YH041oY=; b=kaCPikQj2m4vMduRyNBjNLs/WeaVHIIEwHRcwMddDS9ER5c2ok7VEt4Eqd2I3gLZq7 lWYbyNIBRgxFAYOv6kAO+G6pruQOsM2ISsjwqd1QDoGHWGYT9hDCBA69J9r0bezFqBNR J0+ka/mqK2M6eUbcjPIpn2IbvVHvJpjcJ0BC1Zt45juHVv9gPZ9Omvt+A9Q6w+9C81CZ MJj/ImolBtCqLqVtpC1Ygcot7MFlQDZHBm9PDctEfTz96R+pd1yoQWJbZdd3kQlazm7/ 9SCBoZjx3VOKCGWLEnelu8SmwjXwI6XUIU/dAbSJG46PRET3KN9EvY1wX64VaLI35q2M v3RQ== 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=ab6DNjlfCGaxlfSosFC6Vg+UX4p6nTgmto90YH041oY=; b=3+M3Rva+dWEIlZGVagAy3hOTp4yBOEB9oLzFzMaoG3knAZukKx7wYJIemDlKkGX/8O Z6rSAiOhzQ8KkJAI4qyYbj44FYDJcUUdH/Vg3JBBDKRr39iI0TNJ2mPaoUri/Y86k8/g qAT2x4gGP3Q/iAIBEzLtGQbdjg+STg7syyGAlXWk5TSiboORZ7GDs65n6MgGTKxPXYmL qYJ4VIespCLoRqLkEvuzT4bYOSyHQG83IyaKN7PGR5hKrqwn3elkHNDYSl1LNw7Q+F2I ZQjS8d5+ycMxnnS4cLSeDtBmkDFxcTvTxwkAorXKNWb0Vbb21+vN4uIvtG4lr80xrJrO 5N3w== X-Gm-Message-State: AJIora94u2SQoBrcOLAQwd0VprRb0GBZHFyTzeBSFaL1zaKajWbXD6Rs BNYPcoAqHNDUlX456dBVmmbZVqa/4Ss= X-Google-Smtp-Source: AGRyM1vgG6Ali/rvCe4KVIqTEXc+W0HfDnQBORT8U1KMnxxRHxwYZ62yw2Xi2oRGCqGrCgWwpMCHCA== X-Received: by 2002:a5d:6d84:0:b0:21b:9acb:c478 with SMTP id l4-20020a5d6d84000000b0021b9acbc478mr4209372wrs.491.1657297524608; Fri, 08 Jul 2022 09:25:24 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id t3-20020a05600c41c300b0039c362311d2sm2890331wmh.9.2022.07.08.09.25.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 08 Jul 2022 09:25:24 -0700 (PDT) Message-Id: <5490fd22579c8a65e097d79d0da4beea8549a02b.1657297520.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 08 Jul 2022 16:25:18 +0000 Subject: [PATCH v2 3/4] xdiff: introduce XDL_CALLOC_ARRAY() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: =?utf-8?b?w4Z2YXIgQXJuZmrDtnLDsA==?= Bjarmason , Phillip Wood , 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 | 9 +++------ xdiff/xmacros.h | 3 +++ xdiff/xpatience.c | 3 +-- xdiff/xprepare.c | 10 ++++------ 4 files changed, 11 insertions(+), 14 deletions(-) diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c index c97edc1e29e..df909004c10 100644 --- a/xdiff/xhistogram.c +++ b/xdiff/xhistogram.c @@ -266,17 +266,14 @@ static int find_lcs(xpparam_t const *xpp, xdfenv_t *env, index.table_bits = xdl_hashbits(count1); index.records_size = 1 << index.table_bits; - if (!(index.records = xdl_calloc(index.records_size, - sizeof(*index.records)))) + if (!XDL_CALLOC_ARRAY(index.records, index.records_size)) goto cleanup; index.line_map_size = count1; - if (!(index.line_map = xdl_calloc(index.line_map_size, - sizeof(*index.line_map)))) + if (!XDL_CALLOC_ARRAY(index.line_map, index.line_map_size)) goto cleanup; - if (!(index.next_ptrs = xdl_calloc(index.line_map_size, - sizeof(*index.next_ptrs)))) + if (!XDL_CALLOC_ARRAY(index.next_ptrs, index.line_map_size)) goto cleanup; /* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */ diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h index 9fd3c5da91a..0977d1615ac 100644 --- a/xdiff/xmacros.h +++ b/xdiff/xmacros.h @@ -55,4 +55,7 @@ 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) ((p) = xdl_calloc(nr, sizeof(*(p)))) + #endif /* #if !defined(XMACROS_H) */ diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index 94f8886dd14..fe39c2978cb 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -151,8 +151,7 @@ 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 = xdl_calloc(result->alloc, sizeof(*result->entries)); - if (!result->entries) + if (!XDL_CALLOC_ARRAY(result->entries, result->alloc)) return -1; /* First, fill with entries from the first file */ diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index 45190e59fc8..b016570c488 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c @@ -78,7 +78,7 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) { return -1; } - if (!(cf->rchash = xdl_calloc(cf->hsize, sizeof(*cf->rchash)))) { + if (!XDL_CALLOC_ARRAY(cf->rchash, cf->hsize)) { xdl_cha_free(&cf->ncha); return -1; @@ -182,7 +182,7 @@ 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 = xdl_calloc(hsize, sizeof(*rhash)))) + if (!XDL_CALLOC_ARRAY(rhash, hsize)) goto abort; nrec = 0; @@ -207,7 +207,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ } } - if (!(rchg = xdl_calloc((nrec + 2), sizeof(*rchg)))) + if (!XDL_CALLOC_ARRAY(rchg, nrec + 2)) goto abort; if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && @@ -380,10 +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 = xdl_calloc(xdf1->nrec + xdf2->nrec + 2, sizeof(*dis)))) { - + if (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2)) return -1; - } dis1 = dis; dis2 = dis1 + xdf1->nrec + 1; From patchwork Fri Jul 8 16:25:19 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12911449 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 8BFD1C43334 for ; Fri, 8 Jul 2022 16:26:22 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239016AbiGHQ0V (ORCPT ); Fri, 8 Jul 2022 12:26:21 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36518 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S239247AbiGHQ0C (ORCPT ); Fri, 8 Jul 2022 12:26:02 -0400 Received: from mail-wm1-x330.google.com (mail-wm1-x330.google.com [IPv6:2a00:1450:4864:20::330]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 808B2F6A for ; Fri, 8 Jul 2022 09:25:27 -0700 (PDT) Received: by mail-wm1-x330.google.com with SMTP id p4so3384161wms.0 for ; Fri, 08 Jul 2022 09:25:27 -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=0yc4f6BN9XkcJKB+aBFwXZF6Glat4pFQoTqrGB7dE+4=; b=BZzvCk+DxA6daALQe+lW7YEfZK6DX9vIthOFU0OgfurmqZETaVrkhZatqS1CC3FOsD EgNRFIc1G3C1nlxd6MCsD2etSoL8lpuxptqNDU/haOvWSorKCwZ4UzhUgjC8cPqHV0JM PtLBT37rvTpL4RKvS+0M4qMVhiCNHm7xy3cfk5T7l25fFROUA9Lxds/BjtrKC/mV+52I d6ZGItIu7xDhy+2L5WcYVCk/o2Y2fhjOD+j1hiviT/gdrAZ5v2zEVsGAz0/u4my9dT8M DdHMCRyTaRS3gzVbwFLAFsD8oQAgDSOGBCABn6TJHLD2SR8am3P5W7PUHeNG19QWwMVW EW+A== 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=0yc4f6BN9XkcJKB+aBFwXZF6Glat4pFQoTqrGB7dE+4=; b=uTo0ixs5lC5tyhnGOZNwpP1Q0tf59Jl38iErq8BwtddZw4zdKaiVpbyDkF0SPk9QJ/ J3O0JvETG/u3ZY7bgMvT8jdR7wczz9NxTM3h85I8LzoDlgxWeyVE+0y5vTL1ucs6SYbW ZrrSpb+ZPo52X63KftNCly+655mLVNFrP7gNVPTM1FUJKzF7nDrbNsk9ajJ7DXhlGg5w kMpHHu6D99ouKU9MI+0IjDwqeUpXUXqPnghkAo+47QaheYUcpN2eb5vdJZmkifdQxdcm TnzH4uFjcfMzCJDPHp9c9EGodcK5IxJCD3JCn4YhAYSA7Umk87S79C7v1KkvDpRMtJ+B tGhg== X-Gm-Message-State: AJIora+LzVgoumDhPNRiOWRsjgBJojvv9H12O6U6Xbn9gZmyxa3M1LHP Lj3/486seYhoCNTV1u/589k1aIe+fHI= X-Google-Smtp-Source: AGRyM1v+e4oIF5OS6JX8Zy1NANJceDOhxXAZ5XmhKJaiuRne57yu06NU8oF9Q3bMM+nL9vPRsxYH7g== X-Received: by 2002:a05:600c:3b8c:b0:3a0:4cc2:2b62 with SMTP id n12-20020a05600c3b8c00b003a04cc22b62mr621016wms.185.1657297525715; Fri, 08 Jul 2022 09:25:25 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id ay26-20020a5d6f1a000000b0021baf5e590dsm41308486wrb.71.2022.07.08.09.25.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 08 Jul 2022 09:25:25 -0700 (PDT) Message-Id: <8c24cd7737b29d461788b71f6a94eb74c468ad33.1657297520.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 08 Jul 2022 16:25:19 +0000 Subject: [PATCH v2 4/4] xdiff: introduce XDL_ALLOC_GROW() MIME-Version: 1.0 Fcc: Sent To: git@vger.kernel.org Cc: =?utf-8?b?w4Z2YXIgQXJuZmrDtnLDsA==?= Bjarmason , Phillip Wood , 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. Note that xdl_alloc_grow_helper() uses long rather than size_t for `nr` and `alloc` to match the existing code. 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 0977d1615ac..8487bb396fa 100644 --- a/xdiff/xmacros.h +++ b/xdiff/xmacros.h @@ -58,4 +58,14 @@ do { \ /* Allocate an array of nr zeroed out elements, returns NULL on failure */ #define XDL_CALLOC_ARRAY(p, nr) ((p) = xdl_calloc(nr, sizeof(*(p)))) +/* + * 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) */