From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from zimbra.cs.ucla.edu (zimbra.cs.ucla.edu [131.179.128.68]) by sourceware.org (Postfix) with ESMTPS id E6DC33857012 for ; Fri, 8 Jan 2021 20:14:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org E6DC33857012 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=cs.ucla.edu Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=eggert@cs.ucla.edu Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 0730716008F; Fri, 8 Jan 2021 12:14:22 -0800 (PST) Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id h88jF70tIl2d; Fri, 8 Jan 2021 12:14:17 -0800 (PST) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 7DEAB160099; Fri, 8 Jan 2021 12:14:17 -0800 (PST) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id O2QKaUlM5cjv; Fri, 8 Jan 2021 12:14:17 -0800 (PST) Received: from [192.168.1.9] (cpe-23-243-218-95.socal.res.rr.com [23.243.218.95]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 34E1D16008F; Fri, 8 Jan 2021 12:14:17 -0800 (PST) To: Adhemerval Zanella References: <20210106181707.1738066-1-adhemerval.zanella@linaro.org> From: Paul Eggert Organization: UCLA Computer Science Department Cc: libc-alpha@sourceware.org, bug-gnulib@gnu.org Subject: Re: [PATCH 1/3] posix: Remove alloca usage on regex set_regs Message-ID: Date: Fri, 8 Jan 2021 12:14:16 -0800 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0 MIME-Version: 1.0 In-Reply-To: <20210106181707.1738066-1-adhemerval.zanella@linaro.org> Content-Type: multipart/mixed; boundary="------------5D71767266BC13375F8948C7" Content-Language: en-US X-Spam-Status: No, score=-10.0 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, KAM_SHORT, NICE_REPLY_A, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 08 Jan 2021 20:14:28 -0000 This is a multi-part message in MIME format. --------------5D71767266BC13375F8948C7 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: quoted-printable On 1/6/21 10:17 AM, Adhemerval Zanella wrote: > It replaces the regmatch_t with a dynarray list. regexec.c is shared with Gnulib, so some work needed to be done on the=20 Gnulib side for this patch since Gnulib didn't have dynarray. Dynarray=20 is something I've been meaning to add to Gnulib for some time, so I did=20 that by installing the first attached patch into Gnulib. Could you=20 please propagate the new Gnulib dynarray sources into glibc so that they=20 stay in sync? As near as I can make out, the glibc dynarray files can=20 now be identical to the new Gnulib files; if not, please let me know. > posix/regexec.c | 62 ++++++++++++++++++++++++------------------------= - > 1 file changed, 31 insertions(+), 31 deletions(-) > ... > @@ -1355,6 +1352,16 @@ pop_fail_stack (struct re_fail_stack_t *fs, Idx = *pidx, Idx nregs, > return fs->stack[num].node; > } > =20 > + > +#define DYNARRAY_STRUCT regmatch_list > +#define DYNARRAY_ELEMENT regmatch_t > +#define DYNARRAY_PREFIX regmatch_list_ > +#include > + > +static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch, > + struct regmatch_list *prev_idx_match, Idx cur_node, > + Idx cur_idx, Idx nmatch); > + > /* Set the positions where the subexpressions are starts/ends to regi= sters > PMATCH. > Note: We assume that pmatch[0] is already set, and > @@ -1370,8 +1377,8 @@ set_regs (const regex_t *preg, const re_match_con= text_t *mctx, size_t nmatch, > re_node_set eps_via_nodes; > struct re_fail_stack_t *fs; > struct re_fail_stack_t fs_body =3D { 0, 2, NULL }; > - regmatch_t *prev_idx_match; > - bool prev_idx_match_malloced =3D false; > + struct regmatch_list prev_idx_match; > + regmatch_list_init (&prev_idx_match); > =20 > DEBUG_ASSERT (nmatch > 1); > DEBUG_ASSERT (mctx->state_log !=3D NULL); > @@ -1388,23 +1395,18 @@ set_regs (const regex_t *preg, const re_match_c= ontext_t *mctx, size_t nmatch, > cur_node =3D dfa->init_node; > re_node_set_init_empty (&eps_via_nodes); > =20 > - if (__libc_use_alloca (nmatch * sizeof (regmatch_t))) > - prev_idx_match =3D (regmatch_t *) alloca (nmatch * sizeof (regmatc= h_t)); > - else > + if (!regmatch_list_resize (&prev_idx_match, nmatch)) > { > - prev_idx_match =3D re_malloc (regmatch_t, nmatch); > - if (prev_idx_match =3D=3D NULL) > - { > - free_fail_stack_return (fs); > - return REG_ESPACE; > - } > - prev_idx_match_malloced =3D true; > + regmatch_list_free (&prev_idx_match); > + free_fail_stack_return (fs); > + return REG_ESPACE; > } These three hunks are good, but you can omit most of the other hunks=20 (and improve performance a bit) by inserting the following line after=20 the 3rd hunk: + regmatch_t *prev_idx_match =3D regmatch_list_begin (&prev_match); since the dynarray doesn't grow after that and this means you don't need=20 to change the rest of the code to use prev_match rather than=20 prev_idx_match. The only other hunks you need to retain are the ones=20 replacing re_free with regmastch_list_free. I've made this improvement to Gnulib by installing the second attached=20 patch, so you should be able to copy Gnulib regexec.c to glibc without=20 changing it. --------------5D71767266BC13375F8948C7 Content-Type: text/x-patch; charset=UTF-8; name="0001-dynarray-new-module.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="0001-dynarray-new-module.patch" =46rom ae1984c524f03f8e8bb104d3a2b5c533114cf552 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Fri, 8 Jan 2021 11:44:19 -0800 Subject: [PATCH 1/2] dynarray: new module MIME-Version: 1.0 Content-Type: text/plain; charset=3DUTF-8 Content-Transfer-Encoding: 8bit * config/srclist.txt: Mention the new files. * lib/cdefs.h (__attribute_maybe_unused__): New macro, like Gnulib=E2=80=99s _GL_ATTRIBUTE_MAYBE_UNUSED but with glibc naming conventions. * lib/libc-config.h: Use it instead of __glibc_likely. * lib/dynarray.h, modules/dynarray: New files. * lib/malloc/dynarray-skeleton.c, lib/malloc/dynarray.h: * lib/malloc/dynarray_at_failure.c: * lib/malloc/dynarray_emplace_enlarge.c: * lib/malloc/dynarray_finalize.c, lib/malloc/dynarray_resize.c: * lib/malloc/dynarray_resize_clear.c, modules/dynarray: New files, from glibc with the following changes needed for portability to compilers that are not recent-enough GCC. * lib/malloc/dynarray_at_failure.c: Include stdlib.h, for abort. (__libc_dynarray_at_failure) [!_LIBC]: Simply abort. * lib/malloc/dynarray_emplace_enlarge.c: * lib/malloc/dynarray_resize.c: Include intprops.h, and use INT_MULTIPLY_WRAPV instead of __builtin_mul_overflow. * lib/malloc/dynarray.h (__libc_dynarray_at_failure): Use _Noreturn instead of __attribute__ ((noreturn)). * lib/malloc/dynarray_resize_clear.c: Do not include stdlib.h; it=E2=80=99s not needed. (__libc_dynarray_resize_clear): Do not do arithmetic on void *. * lib/malloc/dynarray-skeleton.c (struct DYNARRAY_STRUCT): Do not use anonymous unions, as they are not in C99. All uses changed. Use __nonnull (X) instead of __attribute__ ((nonnull X)), and __attribute_maybe_unused__ instead of __attribute__ ((unused)). --- ChangeLog | 32 ++ config/srclist.txt | 7 + lib/cdefs.h | 8 + lib/dynarray.h | 31 ++ lib/libc-config.h | 10 +- lib/malloc/dynarray-skeleton.c | 521 ++++++++++++++++++++++++++ lib/malloc/dynarray.h | 178 +++++++++ lib/malloc/dynarray_at_failure.c | 35 ++ lib/malloc/dynarray_emplace_enlarge.c | 73 ++++ lib/malloc/dynarray_finalize.c | 62 +++ lib/malloc/dynarray_resize.c | 64 ++++ lib/malloc/dynarray_resize_clear.c | 35 ++ modules/dynarray | 37 ++ 13 files changed, 1087 insertions(+), 6 deletions(-) create mode 100644 lib/dynarray.h create mode 100644 lib/malloc/dynarray-skeleton.c create mode 100644 lib/malloc/dynarray.h create mode 100644 lib/malloc/dynarray_at_failure.c create mode 100644 lib/malloc/dynarray_emplace_enlarge.c create mode 100644 lib/malloc/dynarray_finalize.c create mode 100644 lib/malloc/dynarray_resize.c create mode 100644 lib/malloc/dynarray_resize_clear.c create mode 100644 modules/dynarray diff --git a/ChangeLog b/ChangeLog index df676e6ba..db37b0a24 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,35 @@ +2021-01-08 Paul Eggert + + dynarray: new module + * config/srclist.txt: Mention the new files. + * lib/cdefs.h (__attribute_maybe_unused__): New macro, + like Gnulib=E2=80=99s _GL_ATTRIBUTE_MAYBE_UNUSED but with glibc + naming conventions. + * lib/libc-config.h: Use it instead of __glibc_likely. + * lib/dynarray.h, modules/dynarray: New files. + * lib/malloc/dynarray-skeleton.c, lib/malloc/dynarray.h: + * lib/malloc/dynarray_at_failure.c: + * lib/malloc/dynarray_emplace_enlarge.c: + * lib/malloc/dynarray_finalize.c, lib/malloc/dynarray_resize.c: + * lib/malloc/dynarray_resize_clear.c, modules/dynarray: + New files, from glibc with the following changes needed for + portability to compilers that are not recent-enough GCC. + * lib/malloc/dynarray_at_failure.c: Include stdlib.h, for abort. + (__libc_dynarray_at_failure) [!_LIBC]: Simply abort. + * lib/malloc/dynarray_emplace_enlarge.c: + * lib/malloc/dynarray_resize.c: + Include intprops.h, and use INT_MULTIPLY_WRAPV instead + of __builtin_mul_overflow. + * lib/malloc/dynarray.h (__libc_dynarray_at_failure): + Use _Noreturn instead of __attribute__ ((noreturn)). + * lib/malloc/dynarray_resize_clear.c: Do not include stdlib.h; + it=E2=80=99s not needed. + (__libc_dynarray_resize_clear): Do not do arithmetic on void *. + * lib/malloc/dynarray-skeleton.c (struct DYNARRAY_STRUCT): + Do not use anonymous unions, as they are not in C99. All uses changed. + Use __nonnull (X) instead of __attribute__ ((nonnull X)), + and __attribute_maybe_unused__ instead of __attribute__ ((unused)). + 2021-01-06 Simon Josefsson =20 bootstrap: Fix parsing of package name. diff --git a/config/srclist.txt b/config/srclist.txt index a2b058d73..e7ceeb088 100644 --- a/config/srclist.txt +++ b/config/srclist.txt @@ -51,6 +51,13 @@ $GNUORG Copyright/request-disclaim.changes doc/Copyrig= ht =20 $LIBCSRC include/filename.h lib $LIBCSRC include/idx.h lib +#$LIBCSRC malloc/dynarray-skeleton.c lib/malloc +#$LIBCSRC malloc/dynarray.h lib/malloc +#$LIBCSRC malloc/dynarray_at_failure.c lib/malloc +#$LIBCSRC malloc/dynarray_emplace_enlarge.c lib/malloc +$LIBCSRC malloc/dynarray_finalize.c lib/malloc +#$LIBCSRC malloc/dynarray_resize.c lib/malloc +#$LIBCSRC malloc/dynarray_resize_clear.c lib/malloc $LIBCSRC include/scratch_buffer.h lib/malloc $LIBCSRC malloc/scratch_buffer_dupfree.c lib/malloc $LIBCSRC malloc/scratch_buffer_grow.c lib/malloc diff --git a/lib/cdefs.h b/lib/cdefs.h index c4769aa70..a22ae6db2 100644 --- a/lib/cdefs.h +++ b/lib/cdefs.h @@ -257,6 +257,14 @@ # define __attribute_const__ /* Ignore */ #endif =20 +#if defined __STDC_VERSION__ && 201710L < __STDC_VERSION__ +# define __attribute_maybe_unused__ [[__maybe_unused__]] +#elif __GNUC_PREREQ (2,7) || __glibc_has_attribute (__unused__) +# define __attribute_maybe_unused__ __attribute__ ((__unused__)) +#else +# define __attribute_maybe_unused__ /* Ignore */ +#endif + /* At some point during the gcc 3.1 development the `used' attribute for functions was introduced. We don't want to use it unconditionall= y (although this would be possible) since it generates warnings. */ diff --git a/lib/dynarray.h b/lib/dynarray.h new file mode 100644 index 000000000..6da3e87e5 --- /dev/null +++ b/lib/dynarray.h @@ -0,0 +1,31 @@ +/* Type-safe arrays which grow dynamically. + Copyright 2021 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see = =2E */ + +/* Written by Paul Eggert, 2021. */ + +#ifndef _GL_DYNARRAY_H +#define _GL_DYNARRAY_H + +#include + +#define __libc_dynarray_at_failure gl_dynarray_at_failure +#define __libc_dynarray_emplace_enlarge gl_dynarray_emplace_enlarge +#define __libc_dynarray_finalize gl_dynarray_finalize +#define __libc_dynarray_resize_clear gl_dynarray_resize_clear +#define __libc_dynarray_resize gl_dynarray_resize +#include + +#endif /* _GL_DYNARRAY_H */ diff --git a/lib/libc-config.h b/lib/libc-config.h index 19e852f45..fcdafcb96 100644 --- a/lib/libc-config.h +++ b/lib/libc-config.h @@ -71,12 +71,10 @@ # endif #endif =20 -#ifndef __glibc_likely -/* either does not exist, or predates glibc commit - 2012-12-28T06:33:01Z!siddhesh@redhat.com - (91998e449e0ce758db55aecf2abc3ee510fcbc8f) - and so does not suffice for Gnulib. Prepare to include , - which is Gnulib's copy of a more-recent glibc . */ +#ifndef __attribute_maybe_unused__ +/* either does not exist, or is too old for Gnulib. + Prepare to include , which is Gnulib's version of a + more-recent glibc . */ =20 /* Define _FEATURES_H so that does not include . = */ # ifndef _FEATURES_H diff --git a/lib/malloc/dynarray-skeleton.c b/lib/malloc/dynarray-skeleto= n.c new file mode 100644 index 000000000..fe886102c --- /dev/null +++ b/lib/malloc/dynarray-skeleton.c @@ -0,0 +1,521 @@ +/* Type-safe arrays which grow dynamically. + Copyright (C) 2017-2021 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +/* Pre-processor macros which act as parameters: + + DYNARRAY_STRUCT + The struct tag of dynamic array to be defined. + DYNARRAY_ELEMENT + The type name of the element type. Elements are copied + as if by memcpy, and can change address as the dynamic + array grows. + DYNARRAY_PREFIX + The prefix of the functions which are defined. + + The following parameters are optional: + + DYNARRAY_ELEMENT_FREE + DYNARRAY_ELEMENT_FREE (E) is evaluated to deallocate the + contents of elements. E is of type DYNARRAY_ELEMENT *. + DYNARRAY_ELEMENT_INIT + DYNARRAY_ELEMENT_INIT (E) is evaluated to initialize a new + element. E is of type DYNARRAY_ELEMENT *. + If DYNARRAY_ELEMENT_FREE but not DYNARRAY_ELEMENT_INIT is + defined, new elements are automatically zero-initialized. + Otherwise, new elements have undefined contents. + DYNARRAY_INITIAL_SIZE + The size of the statically allocated array (default: + at least 2, more elements if they fit into 128 bytes). + Must be a preprocessor constant. If DYNARRAY_INITIAL_SIZE is 0, + there is no statically allocated array at, and all non-empty + arrays are heap-allocated. + DYNARRAY_FINAL_TYPE + The name of the type which holds the final array. If not + defined, is PREFIX##finalize not provided. DYNARRAY_FINAL_TYPE + must be a struct type, with members of type DYNARRAY_ELEMENT and + size_t at the start (in this order). + + These macros are undefined after this header file has been + included. + + The following types are provided (their members are private to the + dynarray implementation): + + struct DYNARRAY_STRUCT + + The following functions are provided: + + void DYNARRAY_PREFIX##init (struct DYNARRAY_STRUCT *); + void DYNARRAY_PREFIX##free (struct DYNARRAY_STRUCT *); + bool DYNARRAY_PREFIX##has_failed (const struct DYNARRAY_STRUCT *); + void DYNARRAY_PREFIX##mark_failed (struct DYNARRAY_STRUCT *); + size_t DYNARRAY_PREFIX##size (const struct DYNARRAY_STRUCT *); + DYNARRAY_ELEMENT *DYNARRAY_PREFIX##begin (const struct DYNARRAY_STR= UCT *); + DYNARRAY_ELEMENT *DYNARRAY_PREFIX##end (const struct DYNARRAY_STRUC= T *); + DYNARRAY_ELEMENT *DYNARRAY_PREFIX##at (struct DYNARRAY_STRUCT *, si= ze_t); + void DYNARRAY_PREFIX##add (struct DYNARRAY_STRUCT *, DYNARRAY_ELEME= NT); + DYNARRAY_ELEMENT *DYNARRAY_PREFIX##emplace (struct DYNARRAY_STRUCT = *); + bool DYNARRAY_PREFIX##resize (struct DYNARRAY_STRUCT *, size_t); + void DYNARRAY_PREFIX##remove_last (struct DYNARRAY_STRUCT *); + void DYNARRAY_PREFIX##clear (struct DYNARRAY_STRUCT *); + + The following functions are provided are provided if the + prerequisites are met: + + bool DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *, + DYNARRAY_FINAL_TYPE *); + (if DYNARRAY_FINAL_TYPE is defined) + DYNARRAY_ELEMENT *DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT= *, + size_t *); + (if DYNARRAY_FINAL_TYPE is not defined) +*/ + +#include + +#include +#include +#include + +#ifndef DYNARRAY_STRUCT +# error "DYNARRAY_STRUCT must be defined" +#endif + +#ifndef DYNARRAY_ELEMENT +# error "DYNARRAY_ELEMENT must be defined" +#endif + +#ifndef DYNARRAY_PREFIX +# error "DYNARRAY_PREFIX must be defined" +#endif + +#ifdef DYNARRAY_INITIAL_SIZE +# if DYNARRAY_INITIAL_SIZE < 0 +# error "DYNARRAY_INITIAL_SIZE must be non-negative" +# endif +# if DYNARRAY_INITIAL_SIZE > 0 +# define DYNARRAY_HAVE_SCRATCH 1 +# else +# define DYNARRAY_HAVE_SCRATCH 0 +# endif +#else +/* Provide a reasonable default which limits the size of + DYNARRAY_STRUCT. */ +# define DYNARRAY_INITIAL_SIZE \ + (sizeof (DYNARRAY_ELEMENT) > 64 ? 2 : 128 / sizeof (DYNARRAY_ELEMENT))= +# define DYNARRAY_HAVE_SCRATCH 1 +#endif + +/* Public type definitions. */ + +/* All fields of this struct are private to the implementation. */ +struct DYNARRAY_STRUCT +{ + union + { + struct dynarray_header dynarray_abstract; + struct + { + /* These fields must match struct dynarray_header. */ + size_t used; + size_t allocated; + DYNARRAY_ELEMENT *array; + } dynarray_header; + } u; + +#if DYNARRAY_HAVE_SCRATCH + /* Initial inline allocation. */ + DYNARRAY_ELEMENT scratch[DYNARRAY_INITIAL_SIZE]; +#endif +}; + +/* Internal use only: Helper macros. */ + +/* Ensure macro-expansion of DYNARRAY_PREFIX. */ +#define DYNARRAY_CONCAT0(prefix, name) prefix##name +#define DYNARRAY_CONCAT1(prefix, name) DYNARRAY_CONCAT0(prefix, name) +#define DYNARRAY_NAME(name) DYNARRAY_CONCAT1(DYNARRAY_PREFIX, name) + +/* Address of the scratch buffer if any. */ +#if DYNARRAY_HAVE_SCRATCH +# define DYNARRAY_SCRATCH(list) (list)->scratch +#else +# define DYNARRAY_SCRATCH(list) NULL +#endif + +/* Internal use only: Helper functions. */ + +/* Internal function. Call DYNARRAY_ELEMENT_FREE with the array + elements. Name mangling needed due to the DYNARRAY_ELEMENT_FREE + macro expansion. */ +static inline void +DYNARRAY_NAME (free__elements__) (DYNARRAY_ELEMENT *__dynarray_array, + size_t __dynarray_used) +{ +#ifdef DYNARRAY_ELEMENT_FREE + for (size_t __dynarray_i =3D 0; __dynarray_i < __dynarray_used; ++__dy= narray_i) + DYNARRAY_ELEMENT_FREE (&__dynarray_array[__dynarray_i]); +#endif /* DYNARRAY_ELEMENT_FREE */ +} + +/* Internal function. Free the non-scratch array allocation. */ +static inline void +DYNARRAY_NAME (free__array__) (struct DYNARRAY_STRUCT *list) +{ +#if DYNARRAY_HAVE_SCRATCH + if (list->u.dynarray_header.array !=3D list->scratch) + free (list->u.dynarray_header.array); +#else + free (list->u.dynarray_header.array); +#endif +} + +/* Public functions. */ + +/* Initialize a dynamic array object. This must be called before any + use of the object. */ +__nonnull ((1)) +static void +DYNARRAY_NAME (init) (struct DYNARRAY_STRUCT *list) +{ + list->u.dynarray_header.used =3D 0; + list->u.dynarray_header.allocated =3D DYNARRAY_INITIAL_SIZE; + list->u.dynarray_header.array =3D DYNARRAY_SCRATCH (list); +} + +/* Deallocate the dynamic array and its elements. */ +__attribute_maybe_unused__ __nonnull ((1)) +static void +DYNARRAY_NAME (free) (struct DYNARRAY_STRUCT *list) +{ + DYNARRAY_NAME (free__elements__) + (list->u.dynarray_header.array, list->u.dynarray_header.used); + DYNARRAY_NAME (free__array__) (list); + DYNARRAY_NAME (init) (list); +} + +/* Return true if the dynamic array is in an error state. */ +__nonnull ((1)) +static inline bool +DYNARRAY_NAME (has_failed) (const struct DYNARRAY_STRUCT *list) +{ + return list->u.dynarray_header.allocated =3D=3D __dynarray_error_marke= r (); +} + +/* Mark the dynamic array as failed. All elements are deallocated as + a side effect. */ +__nonnull ((1)) +static void +DYNARRAY_NAME (mark_failed) (struct DYNARRAY_STRUCT *list) +{ + DYNARRAY_NAME (free__elements__) + (list->u.dynarray_header.array, list->u.dynarray_header.used); + DYNARRAY_NAME (free__array__) (list); + list->u.dynarray_header.array =3D DYNARRAY_SCRATCH (list); + list->u.dynarray_header.used =3D 0; + list->u.dynarray_header.allocated =3D __dynarray_error_marker (); +} + +/* Return the number of elements which have been added to the dynamic + array. */ +__nonnull ((1)) +static inline size_t +DYNARRAY_NAME (size) (const struct DYNARRAY_STRUCT *list) +{ + return list->u.dynarray_header.used; +} + +/* Return a pointer to the array element at INDEX. Terminate the + process if INDEX is out of bounds. */ +__nonnull ((1)) +static inline DYNARRAY_ELEMENT * +DYNARRAY_NAME (at) (struct DYNARRAY_STRUCT *list, size_t index) +{ + if (__glibc_unlikely (index >=3D DYNARRAY_NAME (size) (list))) + __libc_dynarray_at_failure (DYNARRAY_NAME (size) (list), index); + return list->u.dynarray_header.array + index; +} + +/* Return a pointer to the first array element, if any. For a + zero-length array, the pointer can be NULL even though the dynamic + array has not entered the failure state. */ +__nonnull ((1)) +static inline DYNARRAY_ELEMENT * +DYNARRAY_NAME (begin) (struct DYNARRAY_STRUCT *list) +{ + return list->u.dynarray_header.array; +} + +/* Return a pointer one element past the last array element. For a + zero-length array, the pointer can be NULL even though the dynamic + array has not entered the failure state. */ +__nonnull ((1)) +static inline DYNARRAY_ELEMENT * +DYNARRAY_NAME (end) (struct DYNARRAY_STRUCT *list) +{ + return list->u.dynarray_header.array + list->u.dynarray_header.used; +} + +/* Internal function. Slow path for the add function below. */ +static void +DYNARRAY_NAME (add__) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT it= em) +{ + if (__glibc_unlikely + (!__libc_dynarray_emplace_enlarge (&list->u.dynarray_abstract, + DYNARRAY_SCRATCH (list), + sizeof (DYNARRAY_ELEMENT)))) + { + DYNARRAY_NAME (mark_failed) (list); + return; + } + + /* Copy the new element and increase the array length. */ + list->u.dynarray_header.array[list->u.dynarray_header.used++] =3D item= ; +} + +/* Add ITEM at the end of the array, enlarging it by one element. + Mark *LIST as failed if the dynamic array allocation size cannot be + increased. */ +__nonnull ((1)) +static inline void +DYNARRAY_NAME (add) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item= ) +{ + /* Do nothing in case of previous error. */ + if (DYNARRAY_NAME (has_failed) (list)) + return; + + /* Enlarge the array if necessary. */ + if (__glibc_unlikely (list->u.dynarray_header.used + =3D=3D list->u.dynarray_header.allocated)) + { + DYNARRAY_NAME (add__) (list, item); + return; + } + + /* Copy the new element and increase the array length. */ + list->u.dynarray_header.array[list->u.dynarray_header.used++] =3D item= ; +} + +/* Internal function. Building block for the emplace functions below. + Assumes space for one more element in *LIST. */ +static inline DYNARRAY_ELEMENT * +DYNARRAY_NAME (emplace__tail__) (struct DYNARRAY_STRUCT *list) +{ + DYNARRAY_ELEMENT *result + =3D &list->u.dynarray_header.array[list->u.dynarray_header.used]; + ++list->u.dynarray_header.used; +#if defined (DYNARRAY_ELEMENT_INIT) + DYNARRAY_ELEMENT_INIT (result); +#elif defined (DYNARRAY_ELEMENT_FREE) + memset (result, 0, sizeof (*result)); +#endif + return result; +} + +/* Internal function. Slow path for the emplace function below. */ +static DYNARRAY_ELEMENT * +DYNARRAY_NAME (emplace__) (struct DYNARRAY_STRUCT *list) +{ + if (__glibc_unlikely + (!__libc_dynarray_emplace_enlarge (&list->u.dynarray_abstract, + DYNARRAY_SCRATCH (list), + sizeof (DYNARRAY_ELEMENT)))) + { + DYNARRAY_NAME (mark_failed) (list); + return NULL; + } + return DYNARRAY_NAME (emplace__tail__) (list); +} + +/* Allocate a place for a new element in *LIST and return a pointer to + it. The pointer can be NULL if the dynamic array cannot be + enlarged due to a memory allocation failure. */ +__attribute_maybe_unused__ __attribute_warn_unused_result__ __nonnull ((= 1)) +static +/* Avoid inlining with the larger initialization code. */ +#if !(defined (DYNARRAY_ELEMENT_INIT) || defined (DYNARRAY_ELEMENT_FREE)= ) +inline +#endif +DYNARRAY_ELEMENT * +DYNARRAY_NAME (emplace) (struct DYNARRAY_STRUCT *list) +{ + /* Do nothing in case of previous error. */ + if (DYNARRAY_NAME (has_failed) (list)) + return NULL; + + /* Enlarge the array if necessary. */ + if (__glibc_unlikely (list->u.dynarray_header.used + =3D=3D list->u.dynarray_header.allocated)) + return (DYNARRAY_NAME (emplace__) (list)); + return DYNARRAY_NAME (emplace__tail__) (list); +} + +/* Change the size of *LIST to SIZE. If SIZE is larger than the + existing size, new elements are added (which can be initialized). + Otherwise, the list is truncated, and elements are freed. Return + false on memory allocation failure (and mark *LIST as failed). */ +__attribute_maybe_unused__ __nonnull ((1)) +static bool +DYNARRAY_NAME (resize) (struct DYNARRAY_STRUCT *list, size_t size) +{ + if (size > list->u.dynarray_header.used) + { + bool ok; +#if defined (DYNARRAY_ELEMENT_INIT) + /* The new elements have to be initialized. */ + size_t old_size =3D list->u.dynarray_header.used; + ok =3D __libc_dynarray_resize (&list->u.dynarray_abstract, + size, DYNARRAY_SCRATCH (list), + sizeof (DYNARRAY_ELEMENT)); + if (ok) + for (size_t i =3D old_size; i < size; ++i) + { + DYNARRAY_ELEMENT_INIT (&list->u.dynarray_header.array[i]); + } +#elif defined (DYNARRAY_ELEMENT_FREE) + /* Zero initialization is needed so that the elements can be + safely freed. */ + ok =3D __libc_dynarray_resize_clear + (&list->u.dynarray_abstract, size, + DYNARRAY_SCRATCH (list), sizeof (DYNARRAY_ELEMENT)); +#else + ok =3D __libc_dynarray_resize (&list->u.dynarray_abstract, + size, DYNARRAY_SCRATCH (list), + sizeof (DYNARRAY_ELEMENT)); +#endif + if (__glibc_unlikely (!ok)) + DYNARRAY_NAME (mark_failed) (list); + return ok; + } + else + { + /* The list has shrunk in size. Free the removed elements. */ + DYNARRAY_NAME (free__elements__) + (list->u.dynarray_header.array + size, + list->u.dynarray_header.used - size); + list->u.dynarray_header.used =3D size; + return true; + } +} + +/* Remove the last element of LIST if it is present. */ +__attribute_maybe_unused__ __nonnull ((1)) +static void +DYNARRAY_NAME (remove_last) (struct DYNARRAY_STRUCT *list) +{ + /* used > 0 implies that the array is the non-failed state. */ + if (list->u.dynarray_header.used > 0) + { + size_t new_length =3D list->u.dynarray_header.used - 1; +#ifdef DYNARRAY_ELEMENT_FREE + DYNARRAY_ELEMENT_FREE (&list->u.dynarray_header.array[new_length])= ; +#endif + list->u.dynarray_header.used =3D new_length; + } +} + +/* Remove all elements from the list. The elements are freed, but the + list itself is not. */ +__attribute_maybe_unused__ __nonnull ((1)) +static void +DYNARRAY_NAME (clear) (struct DYNARRAY_STRUCT *list) +{ + /* free__elements__ does nothing if the list is in the failed + state. */ + DYNARRAY_NAME (free__elements__) + (list->u.dynarray_header.array, list->u.dynarray_header.used); + list->u.dynarray_header.used =3D 0; +} + +#ifdef DYNARRAY_FINAL_TYPE +/* Transfer the dynamic array to a permanent location at *RESULT. + Returns true on success on false on allocation failure. In either + case, *LIST is re-initialized and can be reused. A NULL pointer is + stored in *RESULT if LIST refers to an empty list. On success, the + pointer in *RESULT is heap-allocated and must be deallocated using + free. */ +__attribute_maybe_unused__ __attribute_warn_unused_result__ __nonnull ((= 1, 2)) +static bool +DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list, + DYNARRAY_FINAL_TYPE *result) +{ + struct dynarray_finalize_result res; + if (__libc_dynarray_finalize (&list->u.dynarray_abstract, + DYNARRAY_SCRATCH (list), + sizeof (DYNARRAY_ELEMENT), &res)) + { + /* On success, the result owns all the data. */ + DYNARRAY_NAME (init) (list); + *result =3D (DYNARRAY_FINAL_TYPE) { res.array, res.length }; + return true; + } + else + { + /* On error, we need to free all data. */ + DYNARRAY_NAME (free) (list); + errno =3D ENOMEM; + return false; + } +} +#else /* !DYNARRAY_FINAL_TYPE */ +/* Transfer the dynamic array to a heap-allocated array and return a + pointer to it. The pointer is NULL if memory allocation fails, or + if the array is empty, so this function should be used only for + arrays which are known not be empty (usually because they always + have a sentinel at the end). If LENGTHP is not NULL, the array + length is written to *LENGTHP. *LIST is re-initialized and can be + reused. */ +__attribute_maybe_unused__ __attribute_warn_unused_result__ __nonnull ((= 1)) +static DYNARRAY_ELEMENT * +DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list, size_t *lengthp)= +{ + struct dynarray_finalize_result res; + if (__libc_dynarray_finalize (&list->u.dynarray_abstract, + DYNARRAY_SCRATCH (list), + sizeof (DYNARRAY_ELEMENT), &res)) + { + /* On success, the result owns all the data. */ + DYNARRAY_NAME (init) (list); + if (lengthp !=3D NULL) + *lengthp =3D res.length; + return res.array; + } + else + { + /* On error, we need to free all data. */ + DYNARRAY_NAME (free) (list); + errno =3D ENOMEM; + return NULL; + } +} +#endif /* !DYNARRAY_FINAL_TYPE */ + +/* Undo macro definitions. */ + +#undef DYNARRAY_CONCAT0 +#undef DYNARRAY_CONCAT1 +#undef DYNARRAY_NAME +#undef DYNARRAY_SCRATCH +#undef DYNARRAY_HAVE_SCRATCH + +#undef DYNARRAY_STRUCT +#undef DYNARRAY_ELEMENT +#undef DYNARRAY_PREFIX +#undef DYNARRAY_ELEMENT_FREE +#undef DYNARRAY_ELEMENT_INIT +#undef DYNARRAY_INITIAL_SIZE +#undef DYNARRAY_FINAL_TYPE diff --git a/lib/malloc/dynarray.h b/lib/malloc/dynarray.h new file mode 100644 index 000000000..638c33f98 --- /dev/null +++ b/lib/malloc/dynarray.h @@ -0,0 +1,178 @@ +/* Type-safe arrays which grow dynamically. Shared definitions. + Copyright (C) 2017-2021 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +/* To use the dynarray facility, you need to include + and define the parameter macros + documented in that file. + + A minimal example which provides a growing list of integers can be + defined like this: + + struct int_array + { + // Pointer to result array followed by its length, + // as required by DYNARRAY_FINAL_TYPE. + int *array; + size_t length; + }; + + #define DYNARRAY_STRUCT dynarray_int + #define DYNARRAY_ELEMENT int + #define DYNARRAY_PREFIX dynarray_int_ + #define DYNARRAY_FINAL_TYPE struct int_array + #include + + To create a three-element array with elements 1, 2, 3, use this + code: + + struct dynarray_int dyn; + dynarray_int_init (&dyn); + for (int i =3D 1; i <=3D 3; ++i) + { + int *place =3D dynarray_int_emplace (&dyn); + assert (place !=3D NULL); + *place =3D i; + } + struct int_array result; + bool ok =3D dynarray_int_finalize (&dyn, &result); + assert (ok); + assert (result.length =3D=3D 3); + assert (result.array[0] =3D=3D 1); + assert (result.array[1] =3D=3D 2); + assert (result.array[2] =3D=3D 3); + free (result.array); + + If the elements contain resources which must be freed, define + DYNARRAY_ELEMENT_FREE appropriately, like this: + + struct str_array + { + char **array; + size_t length; + }; + + #define DYNARRAY_STRUCT dynarray_str + #define DYNARRAY_ELEMENT char * + #define DYNARRAY_ELEMENT_FREE(ptr) free (*ptr) + #define DYNARRAY_PREFIX dynarray_str_ + #define DYNARRAY_FINAL_TYPE struct str_array + #include + + Compared to scratch buffers, dynamic arrays have the following + features: + + - They have an element type, and are not just an untyped buffer of + bytes. + + - When growing, previously stored elements are preserved. (It is + expected that scratch_buffer_grow_preserve and + scratch_buffer_set_array_size eventually go away because all + current users are moved to dynamic arrays.) + + - Scratch buffers have a more aggressive growth policy because + growing them typically means a retry of an operation (across an + NSS service module boundary), which is expensive. + + - For the same reason, scratch buffers have a much larger initial + stack allocation. */ + +#ifndef _DYNARRAY_H +#define _DYNARRAY_H + +#include +#include +#include + +struct dynarray_header +{ + size_t used; + size_t allocated; + void *array; +}; + +/* Marker used in the allocated member to indicate that an error was + encountered. */ +static inline size_t +__dynarray_error_marker (void) +{ + return -1; +} + +/* Internal function. See the has_failed function in + dynarray-skeleton.c. */ +static inline bool +__dynarray_error (struct dynarray_header *list) +{ + return list->allocated =3D=3D __dynarray_error_marker (); +} + +/* Internal function. Enlarge the dynamically allocated area of the + array to make room for one more element. SCRATCH is a pointer to + the scratch area (which is not heap-allocated and must not be + freed). ELEMENT_SIZE is the size, in bytes, of one element. + Return false on failure, true on success. */ +bool __libc_dynarray_emplace_enlarge (struct dynarray_header *, + void *scratch, size_t element_size= ); + +/* Internal function. Enlarge the dynamically allocated area of the + array to make room for at least SIZE elements (which must be larger + than the existing used part of the dynamic array). SCRATCH is a + pointer to the scratch area (which is not heap-allocated and must + not be freed). ELEMENT_SIZE is the size, in bytes, of one element. + Return false on failure, true on success. */ +bool __libc_dynarray_resize (struct dynarray_header *, size_t size, + void *scratch, size_t element_size); + +/* Internal function. Like __libc_dynarray_resize, but clear the new + part of the dynamic array. */ +bool __libc_dynarray_resize_clear (struct dynarray_header *, size_t size= , + void *scratch, size_t element_size); + +/* Internal type. */ +struct dynarray_finalize_result +{ + void *array; + size_t length; +}; + +/* Internal function. Copy the dynamically-allocated area to an + explicitly-sized heap allocation. SCRATCH is a pointer to the + embedded scratch space. ELEMENT_SIZE is the size, in bytes, of the + element type. On success, true is returned, and pointer and length + are written to *RESULT. On failure, false is returned. The caller + has to take care of some of the memory management; this function is + expected to be called from dynarray-skeleton.c. */ +bool __libc_dynarray_finalize (struct dynarray_header *list, void *scrat= ch, + size_t element_size, + struct dynarray_finalize_result *result);= + + +/* Internal function. Terminate the process after an index error. + SIZE is the number of elements of the dynamic array. INDEX is the + lookup index which triggered the failure. */ +_Noreturn void __libc_dynarray_at_failure (size_t size, size_t index); + +#ifndef _ISOMAC +libc_hidden_proto (__libc_dynarray_emplace_enlarge) +libc_hidden_proto (__libc_dynarray_resize) +libc_hidden_proto (__libc_dynarray_resize_clear) +libc_hidden_proto (__libc_dynarray_finalize) +libc_hidden_proto (__libc_dynarray_at_failure) +#endif + +#endif /* _DYNARRAY_H */ diff --git a/lib/malloc/dynarray_at_failure.c b/lib/malloc/dynarray_at_fa= ilure.c new file mode 100644 index 000000000..0fa12c7cd --- /dev/null +++ b/lib/malloc/dynarray_at_failure.c @@ -0,0 +1,35 @@ +/* Report an dynamic array index out of bounds condition. + Copyright (C) 2017-2021 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include +#include + +void +__libc_dynarray_at_failure (size_t size, size_t index) +{ +#ifdef _LIBC + char buf[200]; + __snprintf (buf, sizeof (buf), "Fatal glibc error: " + "array index %zu not less than array length %zu\n", + index, size); +#else + abort (); +#endif +} +libc_hidden_def (__libc_dynarray_at_failure) diff --git a/lib/malloc/dynarray_emplace_enlarge.c b/lib/malloc/dynarray_= emplace_enlarge.c new file mode 100644 index 000000000..ddfe306fc --- /dev/null +++ b/lib/malloc/dynarray_emplace_enlarge.c @@ -0,0 +1,73 @@ +/* Increase the size of a dynamic array in preparation of an emplace ope= ration. + Copyright (C) 2017-2021 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include +#include +#include +#include + +bool +__libc_dynarray_emplace_enlarge (struct dynarray_header *list, + void *scratch, size_t element_size) +{ + size_t new_allocated; + if (list->allocated =3D=3D 0) + { + /* No scratch buffer provided. Choose a reasonable default + size. */ + if (element_size < 4) + new_allocated =3D 16; + else if (element_size < 8) + new_allocated =3D 8; + else + new_allocated =3D 4; + } + else + /* Increase the allocated size, using an exponential growth + policy. */ + { + new_allocated =3D list->allocated + list->allocated / 2 + 1; + if (new_allocated <=3D list->allocated) + { + /* Overflow. */ + __set_errno (ENOMEM); + return false; + } + } + + size_t new_size; + if (INT_MULTIPLY_WRAPV (new_allocated, element_size, &new_size)) + return false; + void *new_array; + if (list->array =3D=3D scratch) + { + /* The previous array was not heap-allocated. */ + new_array =3D malloc (new_size); + if (new_array !=3D NULL && list->array !=3D NULL) + memcpy (new_array, list->array, list->used * element_size); + } + else + new_array =3D realloc (list->array, new_size); + if (new_array =3D=3D NULL) + return false; + list->array =3D new_array; + list->allocated =3D new_allocated; + return true; +} +libc_hidden_def (__libc_dynarray_emplace_enlarge) diff --git a/lib/malloc/dynarray_finalize.c b/lib/malloc/dynarray_finaliz= e.c new file mode 100644 index 000000000..8ec6ad2bc --- /dev/null +++ b/lib/malloc/dynarray_finalize.c @@ -0,0 +1,62 @@ +/* Copy the dynamically-allocated area to an explicitly-sized heap alloc= ation. + Copyright (C) 2017-2021 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include +#include + +bool +__libc_dynarray_finalize (struct dynarray_header *list, + void *scratch, size_t element_size, + struct dynarray_finalize_result *result) +{ + if (__dynarray_error (list)) + /* The caller will reported the deferred error. */ + return false; + + size_t used =3D list->used; + + /* Empty list. */ + if (used =3D=3D 0) + { + /* An empty list could still be backed by a heap-allocated + array. Free it if necessary. */ + if (list->array !=3D scratch) + free (list->array); + *result =3D (struct dynarray_finalize_result) { NULL, 0 }; + return true; + } + + size_t allocation_size =3D used * element_size; + void *heap_array =3D malloc (allocation_size); + if (heap_array !=3D NULL) + { + /* The new array takes ownership of the strings. */ + if (list->array !=3D NULL) + memcpy (heap_array, list->array, allocation_size); + if (list->array !=3D scratch) + free (list->array); + *result =3D (struct dynarray_finalize_result) + { .array =3D heap_array, .length =3D used }; + return true; + } + else + /* The caller will perform the freeing operation. */ + return false; +} +libc_hidden_def (__libc_dynarray_finalize) diff --git a/lib/malloc/dynarray_resize.c b/lib/malloc/dynarray_resize.c new file mode 100644 index 000000000..5c60927f3 --- /dev/null +++ b/lib/malloc/dynarray_resize.c @@ -0,0 +1,64 @@ +/* Increase the size of a dynamic array. + Copyright (C) 2017-2021 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include +#include +#include +#include + +bool +__libc_dynarray_resize (struct dynarray_header *list, size_t size, + void *scratch, size_t element_size) +{ + /* The existing allocation provides sufficient room. */ + if (size <=3D list->allocated) + { + list->used =3D size; + return true; + } + + /* Otherwise, use size as the new allocation size. The caller is + expected to provide the final size of the array, so there is no + over-allocation here. */ + + size_t new_size_bytes; + if (INT_MULTIPLY_WRAPV (size, element_size, &new_size_bytes)) + { + /* Overflow. */ + __set_errno (ENOMEM); + return false; + } + void *new_array; + if (list->array =3D=3D scratch) + { + /* The previous array was not heap-allocated. */ + new_array =3D malloc (new_size_bytes); + if (new_array !=3D NULL && list->array !=3D NULL) + memcpy (new_array, list->array, list->used * element_size); + } + else + new_array =3D realloc (list->array, new_size_bytes); + if (new_array =3D=3D NULL) + return false; + list->array =3D new_array; + list->allocated =3D size; + list->used =3D size; + return true; +} +libc_hidden_def (__libc_dynarray_resize) diff --git a/lib/malloc/dynarray_resize_clear.c b/lib/malloc/dynarray_res= ize_clear.c new file mode 100644 index 000000000..e893d1d58 --- /dev/null +++ b/lib/malloc/dynarray_resize_clear.c @@ -0,0 +1,35 @@ +/* Increase the size of a dynamic array and clear the new part. + Copyright (C) 2017-2021 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include + +bool +__libc_dynarray_resize_clear (struct dynarray_header *list, size_t size,= + void *scratch, size_t element_size) +{ + size_t old_size =3D list->used; + if (!__libc_dynarray_resize (list, size, scratch, element_size)) + return false; + /* __libc_dynarray_resize already checked for overflow. */ + char *array =3D list->array; + memset (array + (old_size * element_size), 0, + (size - old_size) * element_size); + return true; +} +libc_hidden_def (__libc_dynarray_resize_clear) diff --git a/modules/dynarray b/modules/dynarray new file mode 100644 index 000000000..36a08adb7 --- /dev/null +++ b/modules/dynarray @@ -0,0 +1,37 @@ +Description: +Type-safe arrays which grow dynamically. + +Files: +lib/dynarray.h +lib/malloc/dynarray-skeleton.c +lib/malloc/dynarray.h +lib/malloc/dynarray_at_failure.c +lib/malloc/dynarray_emplace_enlarge.c +lib/malloc/dynarray_finalize.c +lib/malloc/dynarray_resize.c +lib/malloc/dynarray_resize_clear.c + +Depends-on: +c99 +libc-config +stdbool +stddef + +configure.ac: + +Makefile.am: +lib_SOURCES +=3D malloc/dynarray_at_failure.c \ + malloc/dynarray_emplace_enlarge.c \ + malloc/dynarray_finalize.c \ + malloc/dynarray_resize.c \ + malloc/dynarray_resize_clear.c + +Include: + + + +License: +LGPLv2+ + +Maintainer: +all, glibc --=20 2.27.0 --------------5D71767266BC13375F8948C7 Content-Type: text/x-patch; charset=UTF-8; name="0002-regex-remove-alloca-usage-on-regex-set_regs.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="0002-regex-remove-alloca-usage-on-regex-set_regs.patch" =46rom c26fbc3ecdf9eb30b34be34a452d5410908d2dba Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Fri, 8 Jan 2021 12:00:09 -0800 Subject: [PATCH 2/2] regex: remove alloca usage on regex set_regs Derived from this patch by Adhemerval Zanella: https://sourceware.org/pipermail/libc-alpha/2021-January/121372.html * lib/regex_internal.h: Include dynarray.h, for Gnulib. * lib/regexec.c (DYNARRAY_STRUCT, DYNARRAY_ELEMENT) (DYNARRAY_PREFIX): New macros. Include malloc/dynarray-skeleton.c. (set_regs): Use dynarray rather than alloca. * modules/regex (Depends-on): Add dynarray. --- ChangeLog | 10 ++++++++++ lib/regex_internal.h | 1 + lib/regexec.c | 40 ++++++++++++++++++---------------------- modules/regex | 1 + 4 files changed, 30 insertions(+), 22 deletions(-) diff --git a/ChangeLog b/ChangeLog index db37b0a24..aff3584e4 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,15 @@ 2021-01-08 Paul Eggert =20 + regex: remove alloca usage on regex set_regs + Derived from this patch by Adhemerval Zanella: + https://sourceware.org/pipermail/libc-alpha/2021-January/121372.html + * lib/regex_internal.h: Include dynarray.h, for Gnulib. + * lib/regexec.c (DYNARRAY_STRUCT, DYNARRAY_ELEMENT) + (DYNARRAY_PREFIX): New macros. + Include malloc/dynarray-skeleton.c. + (set_regs): Use dynarray rather than alloca. + * modules/regex (Depends-on): Add dynarray. + dynarray: new module * config/srclist.txt: Mention the new files. * lib/cdefs.h (__attribute_maybe_unused__): New macro, diff --git a/lib/regex_internal.h b/lib/regex_internal.h index e31ac9267..5d4d5fe2b 100644 --- a/lib/regex_internal.h +++ b/lib/regex_internal.h @@ -32,6 +32,7 @@ #include #include =20 +#include #include #include =20 diff --git a/lib/regexec.c b/lib/regexec.c index b083342f7..889b10be9 100644 --- a/lib/regexec.c +++ b/lib/regexec.c @@ -1355,6 +1355,12 @@ pop_fail_stack (struct re_fail_stack_t *fs, Idx *p= idx, Idx nregs, return fs->stack[num].node; } =20 + +#define DYNARRAY_STRUCT regmatch_list +#define DYNARRAY_ELEMENT regmatch_t +#define DYNARRAY_PREFIX regmatch_list_ +#include + /* Set the positions where the subexpressions are starts/ends to registe= rs PMATCH. Note: We assume that pmatch[0] is already set, and @@ -1370,8 +1376,8 @@ set_regs (const regex_t *preg, const re_match_conte= xt_t *mctx, size_t nmatch, re_node_set eps_via_nodes; struct re_fail_stack_t *fs; struct re_fail_stack_t fs_body =3D { 0, 2, NULL }; - regmatch_t *prev_idx_match; - bool prev_idx_match_malloced =3D false; + struct regmatch_list prev_match; + regmatch_list_init (&prev_match); =20 DEBUG_ASSERT (nmatch > 1); DEBUG_ASSERT (mctx->state_log !=3D NULL); @@ -1388,18 +1394,13 @@ set_regs (const regex_t *preg, const re_match_con= text_t *mctx, size_t nmatch, cur_node =3D dfa->init_node; re_node_set_init_empty (&eps_via_nodes); =20 - if (__libc_use_alloca (nmatch * sizeof (regmatch_t))) - prev_idx_match =3D (regmatch_t *) alloca (nmatch * sizeof (regmatch_= t)); - else + if (!regmatch_list_resize (&prev_match, nmatch)) { - prev_idx_match =3D re_malloc (regmatch_t, nmatch); - if (prev_idx_match =3D=3D NULL) - { - free_fail_stack_return (fs); - return REG_ESPACE; - } - prev_idx_match_malloced =3D true; + regmatch_list_free (&prev_match); + free_fail_stack_return (fs); + return REG_ESPACE; } + regmatch_t *prev_idx_match =3D regmatch_list_begin (&prev_match); memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch); =20 for (idx =3D pmatch[0].rm_so; idx <=3D pmatch[0].rm_eo ;) @@ -1417,8 +1418,7 @@ set_regs (const regex_t *preg, const re_match_conte= xt_t *mctx, size_t nmatch, if (reg_idx =3D=3D nmatch) { re_node_set_free (&eps_via_nodes); - if (prev_idx_match_malloced) - re_free (prev_idx_match); + regmatch_list_free (&prev_match); return free_fail_stack_return (fs); } cur_node =3D pop_fail_stack (fs, &idx, nmatch, pmatch, @@ -1427,8 +1427,7 @@ set_regs (const regex_t *preg, const re_match_conte= xt_t *mctx, size_t nmatch, else { re_node_set_free (&eps_via_nodes); - if (prev_idx_match_malloced) - re_free (prev_idx_match); + regmatch_list_free (&prev_match); return REG_NOERROR; } } @@ -1442,8 +1441,7 @@ set_regs (const regex_t *preg, const re_match_conte= xt_t *mctx, size_t nmatch, if (__glibc_unlikely (cur_node =3D=3D -2)) { re_node_set_free (&eps_via_nodes); - if (prev_idx_match_malloced) - re_free (prev_idx_match); + regmatch_list_free (&prev_match); free_fail_stack_return (fs); return REG_ESPACE; } @@ -1453,15 +1451,13 @@ set_regs (const regex_t *preg, const re_match_con= text_t *mctx, size_t nmatch, else { re_node_set_free (&eps_via_nodes); - if (prev_idx_match_malloced) - re_free (prev_idx_match); + regmatch_list_free (&prev_match); return REG_NOMATCH; } } } re_node_set_free (&eps_via_nodes); - if (prev_idx_match_malloced) - re_free (prev_idx_match); + regmatch_list_free (&prev_match); return free_fail_stack_return (fs); } =20 diff --git a/modules/regex b/modules/regex index 570b0bd55..39297dfe3 100644 --- a/modules/regex +++ b/modules/regex @@ -19,6 +19,7 @@ ssize_t alloca-opt [test $ac_use_included_regex =3D yes] btowc [test $ac_use_included_regex =3D yes] builtin-expect [test $ac_use_included_regex =3D yes] +dynarray [test $ac_use_included_regex =3D yes] intprops [test $ac_use_included_regex =3D yes] langinfo [test $ac_use_included_regex =3D yes] libc-config [test $ac_use_included_regex =3D yes] --=20 2.27.0 --------------5D71767266BC13375F8948C7--