From patchwork Mon Feb 5 13:27:33 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella X-Patchwork-Id: 25808 Received: (qmail 34413 invoked by alias); 5 Feb 2018 13:28:02 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 34253 invoked by uid 89); 5 Feb 2018 13:28:01 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.9 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=9577, EXT, _at, 11607 X-HELO: mail-qt0-f194.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=8Ng3SSnrFlKKnkbE4serckCACun5eVAFlc9iPT1MO3o=; b=aDljyw6dGdM9fMqflnKgGYWVBx2Z9j2vh8XbR41jb+u7WYQfAd0wm7INqpVwfG8mkY U5NNdC5QGTB1yFV44DVLD+K0zJCgozQjsmuVgmhSEwLdmJSGRI9NnbxIt5r/sPDgk1MC pSE+g4+Z61YCA1rOd54zEqmrzsosvfCHuEO+97IHAS0j5W63B3RUz+XsUE4FjkDyNx/G aQb3mtfnqPv1FJWjxBXxejjcwBBpgxc/62cI6epqBHefTSpzGXNd9xX/Ef6CYZrJ4ioS dgq6wG/BzsYATuI2PdBCC3hhMCDniMn04HcTR56ct3Vps/0g0VZzmoNP2b/z9eELjXbD W9eQ== X-Gm-Message-State: AKwxytddq6QxHxfMTHL44l2ZvEOq4XaIrY1zcwBk28xcJDqogNRwAzPt vs/IxCIvcze4K2yb/gaWA2Tjx0Za7nY= X-Google-Smtp-Source: AH8x226srJID46yLY9RNgIgBr/Jy2nFj62xpsXWlpH9T86YLQOAB6VDXl3IQYR9F+Qd5F9EE1StkIQ== X-Received: by 10.200.34.35 with SMTP id o32mr81179171qto.103.1517837276721; Mon, 05 Feb 2018 05:27:56 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH v2 11/12] posix: Remove alloca usage for internal fnmatch implementation Date: Mon, 5 Feb 2018 11:27:33 -0200 Message-Id: <1517837254-19399-12-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1517837254-19399-1-git-send-email-adhemerval.zanella@linaro.org> References: <1517837254-19399-1-git-send-email-adhemerval.zanella@linaro.org> This patch replaces the internal fnmatch pattern list generation from a linked list using alloca to a dynamic array. Checked on x86_64-linux-gnu. * posix/fnmatch_loop.c (FCT, EXT): Remove alloca_used argument and use dynamic_array for pattern list. Signed-off-by: Adhemerval Zanella --- ChangeLog | 3 + posix/fnmatch.c | 4 +- posix/fnmatch_loop.c | 162 +++++++++++++++++++++++++-------------------------- 3 files changed, 86 insertions(+), 83 deletions(-) diff --git a/posix/fnmatch.c b/posix/fnmatch.c index 4be7327..9c2cff0 100644 --- a/posix/fnmatch.c +++ b/posix/fnmatch.c @@ -342,7 +342,7 @@ fnmatch (const char *pattern, const char *string, int flags) mbsrtowcs (wstring, &string, strsize, &ps); int res = internal_fnwmatch (wpattern, wstring, wstring + strsize - 1, - flags & FNM_PERIOD, flags, NULL, 0); + flags & FNM_PERIOD, flags, NULL); scratch_buffer_free (&s); @@ -351,7 +351,7 @@ fnmatch (const char *pattern, const char *string, int flags) # endif /* mbstate_t and mbsrtowcs or _LIBC. */ return internal_fnmatch (pattern, string, string + strlen (string), - flags & FNM_PERIOD, flags, NULL, 0); + flags & FNM_PERIOD, flags, NULL); } # ifdef _LIBC diff --git a/posix/fnmatch_loop.c b/posix/fnmatch_loop.c index e298cac..eadb343 100644 --- a/posix/fnmatch_loop.c +++ b/posix/fnmatch_loop.c @@ -28,15 +28,14 @@ struct STRUCT it matches, nonzero if not. */ static int FCT (const CHAR *pattern, const CHAR *string, const CHAR *string_end, int no_leading_period, int flags, - struct STRUCT *ends, size_t alloca_used); + struct STRUCT *ends); static int EXT (INT opt, const CHAR *pattern, const CHAR *string, - const CHAR *string_end, int no_leading_period, int flags, - size_t alloca_used); + const CHAR *string_end, int no_leading_period, int flags); static const CHAR *END (const CHAR *patternp); static int FCT (const CHAR *pattern, const CHAR *string, const CHAR *string_end, - int no_leading_period, int flags, struct STRUCT *ends, size_t alloca_used) + int no_leading_period, int flags, struct STRUCT *ends) { const CHAR *p = pattern, *n = string; UCHAR c; @@ -61,7 +60,7 @@ FCT (const CHAR *pattern, const CHAR *string, const CHAR *string_end, if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(') { int res = EXT (c, p, n, string_end, no_leading_period, - flags, alloca_used); + flags); if (res != -1) return res; } @@ -91,7 +90,7 @@ FCT (const CHAR *pattern, const CHAR *string, const CHAR *string_end, if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(') { int res = EXT (c, p, n, string_end, no_leading_period, - flags, alloca_used); + flags); if (res != -1) return res; } @@ -180,7 +179,7 @@ FCT (const CHAR *pattern, const CHAR *string, const CHAR *string_end, for (--p; n < endp; ++n, no_leading_period = 0) if (FCT (p, n, string_end, no_leading_period, flags2, - &end, alloca_used) == 0) + &end) == 0) goto found; } else if (c == L('/') && (flags & FNM_FILE_NAME)) @@ -189,7 +188,7 @@ FCT (const CHAR *pattern, const CHAR *string, const CHAR *string_end, ++n; if (n < string_end && *n == L('/') && (FCT (p, n + 1, string_end, flags & FNM_PERIOD, flags, - NULL, alloca_used) == 0)) + NULL) == 0)) return 0; } else @@ -203,7 +202,7 @@ FCT (const CHAR *pattern, const CHAR *string, const CHAR *string_end, for (--p; n < endp; ++n, no_leading_period = 0) if (FOLD ((UCHAR) *n) == c && (FCT (p, n, string_end, no_leading_period, flags2, - &end, alloca_used) == 0)) + &end) == 0)) { found: if (end.pattern == NULL) @@ -958,8 +957,7 @@ FCT (const CHAR *pattern, const CHAR *string, const CHAR *string_end, case L('!'): if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(') { - int res = EXT (c, p, n, string_end, no_leading_period, flags, - alloca_used); + int res = EXT (c, p, n, string_end, no_leading_period, flags); if (res != -1) return res; } @@ -1038,26 +1036,37 @@ END (const CHAR *pattern) return p + 1; } +#if WIDE_CHAR_VERSION +# define PATTERN_PREFIX pattern_list +#else +# define PATTERN_PREFIX wpattern_list +#endif + +#define PASTE(a,b) PASTE1(a,b) +#define PASTE1(a,b) a##b + +#define DYNARRAY_STRUCT PATTERN_PREFIX +#define DYNARRAY_ELEMENT_FREE(ptr) free (*ptr) +#define DYNARRAY_ELEMENT CHAR * +#define DYNARRAY_PREFIX PASTE(PATTERN_PREFIX,_) +#define DYNARRAY_INITIAL_SIZE 8 +#include static int EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end, - int no_leading_period, int flags, size_t alloca_used) + int no_leading_period, int flags) { const CHAR *startp; int level; - struct patternlist - { - struct patternlist *next; - CHAR malloced; - CHAR str[0]; - } *list = NULL; - struct patternlist **lastp = &list; + struct PATTERN_PREFIX list; size_t pattern_len = STRLEN (pattern); - int any_malloced = 0; + size_t pattern_i = 0; const CHAR *p; const CHAR *rs; int retval = 0; + PASTE (PATTERN_PREFIX, _init) (&list); + /* Parse the pattern. Store the individual parts in the list. */ level = 0; for (startp = p = pattern + 1; level >= 0; ++p) @@ -1099,28 +1108,20 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end, { /* This means we found the end of the pattern. */ #define NEW_PATTERN \ - struct patternlist *newp; \ - size_t slen = (opt == L('?') || opt == L('@') \ - ? pattern_len : (p - startp + 1)); \ - slen = sizeof (struct patternlist) + (slen * sizeof (CHAR)); \ - int malloced = ! __libc_use_alloca (alloca_used + slen); \ - if (__builtin_expect (malloced, 0)) \ - { \ - newp = malloc (slen); \ - if (newp == NULL) \ - { \ - retval = -2; \ - goto out; \ - } \ - any_malloced = 1; \ - } \ - else \ - newp = alloca_account (slen, alloca_used); \ - newp->next = NULL; \ - newp->malloced = malloced; \ - *((CHAR *) MEMPCPY (newp->str, startp, p - startp)) = L('\0'); \ - *lastp = newp; \ - lastp = &newp->next + size_t slen = (opt == L('?') || opt == L('@') \ + ? pattern_len : (p - startp + 1)); \ + CHAR *newp = malloc (slen * sizeof (CHAR)); \ + if (newp != NULL) \ + { \ + *((CHAR *) MEMPCPY (newp, startp, p - startp)) = L('\0'); \ + PASTE (PATTERN_PREFIX,_add) (&list, newp); \ + } \ + if (newp == NULL || PASTE (PATTERN_PREFIX, _has_failed) (&list)) \ + { \ + retval = -2; \ + goto out; \ + } \ + NEW_PATTERN; } } @@ -1132,27 +1133,26 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end, startp = p + 1; } } - assert (list != NULL); assert (p[-1] == L(')')); #undef NEW_PATTERN switch (opt) { case L('*'): - if (FCT (p, string, string_end, no_leading_period, flags, NULL, - alloca_used) == 0) + if (FCT (p, string, string_end, no_leading_period, flags, NULL) == 0) goto success; /* FALLTHROUGH */ case L('+'): - do + for (; pattern_i < PASTE (PATTERN_PREFIX, _size)(&list); pattern_i++) { for (rs = string; rs <= string_end; ++rs) /* First match the prefix with the current pattern with the current pattern. */ - if (FCT (list->str, string, rs, no_leading_period, + if (FCT (*PASTE (PATTERN_PREFIX, _at) (&list, pattern_i), string, + rs, no_leading_period, flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD, - NULL, alloca_used) == 0 + NULL) == 0 /* This was successful. Now match the rest with the rest of the pattern. */ && (FCT (p, rs, string_end, @@ -1160,7 +1160,7 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end, ? no_leading_period : rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0, flags & FNM_FILE_NAME - ? flags : flags & ~FNM_PERIOD, NULL, alloca_used) == 0 + ? flags : flags & ~FNM_PERIOD, NULL) == 0 /* This didn't work. Try the whole pattern. */ || (rs != string && FCT (pattern - 1, rs, string_end, @@ -1169,36 +1169,34 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end, : (rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0), flags & FNM_FILE_NAME - ? flags : flags & ~FNM_PERIOD, NULL, - alloca_used) == 0))) + ? flags : flags & ~FNM_PERIOD, NULL) == 0))) /* It worked. Signal success. */ goto success; } - while ((list = list->next) != NULL); /* None of the patterns lead to a match. */ retval = FNM_NOMATCH; break; case L('?'): - if (FCT (p, string, string_end, no_leading_period, flags, NULL, - alloca_used) == 0) + if (FCT (p, string, string_end, no_leading_period, flags, NULL) == 0) goto success; /* FALLTHROUGH */ case L('@'): - do - /* I cannot believe it but `strcat' is actually acceptable - here. Match the entire string with the prefix from the - pattern list and the rest of the pattern following the - pattern list. */ - if (FCT (STRCAT (list->str, p), string, string_end, - no_leading_period, - flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD, - NULL, alloca_used) == 0) - /* It worked. Signal success. */ - goto success; - while ((list = list->next) != NULL); + for (; pattern_i < PASTE (PATTERN_PREFIX, _size) (&list); pattern_i++) + { + /* I cannot believe it but `strcat' is actually acceptable + here. Match the entire string with the prefix from the + pattern list and the rest of the pattern following the + pattern list. */ + if (FCT (STRCAT (*PASTE (PATTERN_PREFIX, _at) (&list, pattern_i), p), + string, string_end, no_leading_period, + flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD, + NULL) == 0) + /* It worked. Signal success. */ + goto success; + } /* None of the patterns lead to a match. */ retval = FNM_NOMATCH; @@ -1207,22 +1205,27 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end, case L('!'): for (rs = string; rs <= string_end; ++rs) { - struct patternlist *runp; + size_t runp_i; - for (runp = list; runp != NULL; runp = runp->next) - if (FCT (runp->str, string, rs, no_leading_period, - flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD, - NULL, alloca_used) == 0) + for (runp_i = pattern_i; + runp_i != PASTE (PATTERN_PREFIX, _size) (&list); + runp_i++) + { + if (FCT (*PASTE (PATTERN_PREFIX, _at) (&list, runp_i), string, rs, + no_leading_period, + flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD, + NULL) == 0) break; + } /* If none of the patterns matched see whether the rest does. */ - if (runp == NULL + if (runp_i == PASTE (PATTERN_PREFIX, _size) (&list) && (FCT (p, rs, string_end, rs == string ? no_leading_period : rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0, flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD, - NULL, alloca_used) == 0)) + NULL) == 0)) /* This is successful. */ goto success; } @@ -1240,18 +1243,15 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end, success: out: - if (any_malloced) - while (list != NULL) - { - struct patternlist *old = list; - list = list->next; - if (old->malloced) - free (old); - } + PASTE (PATTERN_PREFIX, _free) (&list); return retval; } +#undef PATTERN_PREFIX +#undef PASTE +#undef PASTE1 + #undef FOLD #undef CHAR