From patchwork Wed Jun 23 06:31:50 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 43969 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id EEE32388C03A for ; Wed, 23 Jun 2021 06:34:07 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org EEE32388C03A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1624430048; bh=ZmM2bm8lYTNRdTkY/CpdWKW+zor0lB46Y0mIU5Iu9/c=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=Cd6dil1gtV2ncs2xjezEW6S8rA7auEy6CBs1wXbTVamAKD0R3qxIrHrOao/xlleKi KIdpNmCcoYCTI91mCeCJowRLfRlwBnIdSHFYVHVyr1OnAn0Y58mQ1cqmRp3UarQygT P1rUREhNV4svrEUPMlESYcpbUyqj+zE5Z+AIh2QE= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-qk1-x72b.google.com (mail-qk1-x72b.google.com [IPv6:2607:f8b0:4864:20::72b]) by sourceware.org (Postfix) with ESMTPS id EBDC83853816 for ; Wed, 23 Jun 2021 06:32:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EBDC83853816 Received: by mail-qk1-x72b.google.com with SMTP id q64so2475104qke.7 for ; Tue, 22 Jun 2021 23:32:15 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=ZmM2bm8lYTNRdTkY/CpdWKW+zor0lB46Y0mIU5Iu9/c=; b=pxx9DxSYaoSavS5EOMqriyXkTqt3N5a87hMZUPyX6i+PhzzwET2Riv+SEK7tLKcs8o Z8Mwm2LRVxrqHInU2nOkXQhgiAnX1GTb2hUE0qX8vEdglBsqyTFk2SbF6AuhMMA2q8Xz DZd07GlCMFasZSVWs61/GQg7tB3fXGyiNWN+JHzH7kRW3QNBdG4eBZV8b33GI6/+lQLC T30lMedBguNagNEu4CEB58ZXAcCR/KWKE1KCn07Qw5r6/kJomFjXy4XfSt0BJ+XHGFnq /KrDxfL3jI/VH+uooXXEWNN/D1d0KVJBcz4OAfXftbOAj4S2mVIcYglLk+bCiGULMleO cQgg== X-Gm-Message-State: AOAM531PMYTcnBdRZFKMjaljK6U9F66/yktI8GHw49gmljTKjvqM2bQf 7zqbU7ZEK59yInnAZwUj+jnOX28/lVM= X-Google-Smtp-Source: ABdhPJw/KWthO3JuJWP23DWjMWNQTdQzQ97fSMqRiP1iXaIEBGkif2EnrBeMbS2ux6ZYmIrVrrBJ+g== X-Received: by 2002:a37:468b:: with SMTP id t133mr8333345qka.189.1624429935341; Tue, 22 Jun 2021 23:32:15 -0700 (PDT) Received: from localhost.localdomain (pool-173-75-15-191.pitbpa.fios.verizon.net. [173.75.15.191]) by smtp.googlemail.com with ESMTPSA id r22sm3224613qtm.82.2021.06.22.23.32.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 22 Jun 2021 23:32:15 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v3 3/3] x86: Fix overflow bug in wcsnlen-sse4_1 and wcsnlen-avx2 [BZ #27974] Date: Wed, 23 Jun 2021 02:31:50 -0400 Message-Id: <20210623063149.1167067-3-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210609205257.123944-1-goldstein.w.n@gmail.com> References: <20210609205257.123944-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-12.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, 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-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" This commit fixes the bug mentioned in the previous commit. The previous implementations of wmemchr in these files relied on maxlen * sizeof(wchar_t) which was not guranteed by the standard. The new overflow tests added in the previous commit now pass (As well as all the other tests). Signed-off-by: Noah Goldstein Reviewed-by: H.J. Lu --- sysdeps/x86_64/multiarch/strlen-avx2.S | 130 ++++++++++++++++++------- sysdeps/x86_64/multiarch/strlen-vec.S | 15 ++- 2 files changed, 107 insertions(+), 38 deletions(-) diff --git a/sysdeps/x86_64/multiarch/strlen-avx2.S b/sysdeps/x86_64/multiarch/strlen-avx2.S index bd2e6ee44a..b282a75613 100644 --- a/sysdeps/x86_64/multiarch/strlen-avx2.S +++ b/sysdeps/x86_64/multiarch/strlen-avx2.S @@ -44,21 +44,21 @@ # define VEC_SIZE 32 # define PAGE_SIZE 4096 +# define CHAR_PER_VEC (VEC_SIZE / CHAR_SIZE) .section SECTION(.text),"ax",@progbits ENTRY (STRLEN) # ifdef USE_AS_STRNLEN /* Check zero length. */ +# ifdef __ILP32__ + /* Clear upper bits. */ + and %RSI_LP, %RSI_LP +# else test %RSI_LP, %RSI_LP +# endif jz L(zero) /* Store max len in R8_LP before adjusting if using WCSLEN. */ mov %RSI_LP, %R8_LP -# ifdef USE_AS_WCSLEN - shl $2, %RSI_LP -# elif defined __ILP32__ - /* Clear the upper 32 bits. */ - movl %esi, %esi -# endif # endif movl %edi, %eax movq %rdi, %rdx @@ -72,10 +72,10 @@ ENTRY (STRLEN) /* Check the first VEC_SIZE bytes. */ VPCMPEQ (%rdi), %ymm0, %ymm1 - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax # ifdef USE_AS_STRNLEN /* If length < VEC_SIZE handle special. */ - cmpq $VEC_SIZE, %rsi + cmpq $CHAR_PER_VEC, %rsi jbe L(first_vec_x0) # endif /* If empty continue to aligned_more. Otherwise return bit @@ -84,6 +84,7 @@ ENTRY (STRLEN) jz L(aligned_more) tzcntl %eax, %eax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrl $2, %eax # endif VZEROUPPER_RETURN @@ -97,9 +98,14 @@ L(zero): L(first_vec_x0): /* Set bit for max len so that tzcnt will return min of max len and position of first match. */ +# ifdef USE_AS_WCSLEN + /* NB: Multiply length by 4 to get byte count. */ + sall $2, %esi +# endif btsq %rsi, %rax tzcntl %eax, %eax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrl $2, %eax # endif VZEROUPPER_RETURN @@ -113,14 +119,19 @@ L(first_vec_x1): # ifdef USE_AS_STRNLEN /* Use ecx which was computed earlier to compute correct value. */ +# ifdef USE_AS_WCSLEN + leal -(VEC_SIZE * 4 + 1)(%rax, %rcx, 4), %eax +# else subl $(VEC_SIZE * 4 + 1), %ecx addl %ecx, %eax +# endif # else subl %edx, %edi incl %edi addl %edi, %eax # endif # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrl $2, %eax # endif VZEROUPPER_RETURN @@ -133,14 +144,19 @@ L(first_vec_x2): # ifdef USE_AS_STRNLEN /* Use ecx which was computed earlier to compute correct value. */ +# ifdef USE_AS_WCSLEN + leal -(VEC_SIZE * 3 + 1)(%rax, %rcx, 4), %eax +# else subl $(VEC_SIZE * 3 + 1), %ecx addl %ecx, %eax +# endif # else subl %edx, %edi addl $(VEC_SIZE + 1), %edi addl %edi, %eax # endif # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrl $2, %eax # endif VZEROUPPER_RETURN @@ -153,14 +169,19 @@ L(first_vec_x3): # ifdef USE_AS_STRNLEN /* Use ecx which was computed earlier to compute correct value. */ +# ifdef USE_AS_WCSLEN + leal -(VEC_SIZE * 2 + 1)(%rax, %rcx, 4), %eax +# else subl $(VEC_SIZE * 2 + 1), %ecx addl %ecx, %eax +# endif # else subl %edx, %edi addl $(VEC_SIZE * 2 + 1), %edi addl %edi, %eax # endif # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrl $2, %eax # endif VZEROUPPER_RETURN @@ -173,14 +194,19 @@ L(first_vec_x4): # ifdef USE_AS_STRNLEN /* Use ecx which was computed earlier to compute correct value. */ +# ifdef USE_AS_WCSLEN + leal -(VEC_SIZE * 1 + 1)(%rax, %rcx, 4), %eax +# else subl $(VEC_SIZE + 1), %ecx addl %ecx, %eax +# endif # else subl %edx, %edi addl $(VEC_SIZE * 3 + 1), %edi addl %edi, %eax # endif # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrl $2, %eax # endif VZEROUPPER_RETURN @@ -195,10 +221,14 @@ L(cross_page_continue): /* Check the first 4 * VEC_SIZE. Only one VEC_SIZE at a time since data is only aligned to VEC_SIZE. */ # ifdef USE_AS_STRNLEN - /* + 1 because rdi is aligned to VEC_SIZE - 1. + CHAR_SIZE because - it simplies the logic in last_4x_vec_or_less. */ + /* + 1 because rdi is aligned to VEC_SIZE - 1. + CHAR_SIZE + because it simplies the logic in last_4x_vec_or_less. */ leaq (VEC_SIZE * 4 + CHAR_SIZE + 1)(%rdi), %rcx subq %rdx, %rcx +# ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get the wchar_t count. */ + sarl $2, %ecx +# endif # endif /* Load first VEC regardless. */ VPCMPEQ 1(%rdi), %ymm0, %ymm1 @@ -207,34 +237,38 @@ L(cross_page_continue): subq %rcx, %rsi jb L(last_4x_vec_or_less) # endif - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax testl %eax, %eax jnz L(first_vec_x1) VPCMPEQ (VEC_SIZE + 1)(%rdi), %ymm0, %ymm1 - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax testl %eax, %eax jnz L(first_vec_x2) VPCMPEQ (VEC_SIZE * 2 + 1)(%rdi), %ymm0, %ymm1 - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax testl %eax, %eax jnz L(first_vec_x3) VPCMPEQ (VEC_SIZE * 3 + 1)(%rdi), %ymm0, %ymm1 - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax testl %eax, %eax jnz L(first_vec_x4) /* Align data to VEC_SIZE * 4 - 1. */ # ifdef USE_AS_STRNLEN /* Before adjusting length check if at last VEC_SIZE * 4. */ - cmpq $(VEC_SIZE * 4 - 1), %rsi + cmpq $(CHAR_PER_VEC * 4 - 1), %rsi jbe L(last_4x_vec_or_less_load) incq %rdi movl %edi, %ecx orq $(VEC_SIZE * 4 - 1), %rdi andl $(VEC_SIZE * 4 - 1), %ecx +# ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get the wchar_t count. */ + sarl $2, %ecx +# endif /* Readjust length. */ addq %rcx, %rsi # else @@ -246,13 +280,13 @@ L(cross_page_continue): L(loop_4x_vec): # ifdef USE_AS_STRNLEN /* Break if at end of length. */ - subq $(VEC_SIZE * 4), %rsi + subq $(CHAR_PER_VEC * 4), %rsi jb L(last_4x_vec_or_less_cmpeq) # endif - /* Save some code size by microfusing VPMINU with the load. Since - the matches in ymm2/ymm4 can only be returned if there where no - matches in ymm1/ymm3 respectively there is no issue with overlap. - */ + /* Save some code size by microfusing VPMINU with the load. + Since the matches in ymm2/ymm4 can only be returned if there + where no matches in ymm1/ymm3 respectively there is no issue + with overlap. */ vmovdqa 1(%rdi), %ymm1 VPMINU (VEC_SIZE + 1)(%rdi), %ymm1, %ymm2 vmovdqa (VEC_SIZE * 2 + 1)(%rdi), %ymm3 @@ -260,7 +294,7 @@ L(loop_4x_vec): VPMINU %ymm2, %ymm4, %ymm5 VPCMPEQ %ymm5, %ymm0, %ymm5 - vpmovmskb %ymm5, %ecx + vpmovmskb %ymm5, %ecx subq $-(VEC_SIZE * 4), %rdi testl %ecx, %ecx @@ -268,27 +302,28 @@ L(loop_4x_vec): VPCMPEQ %ymm1, %ymm0, %ymm1 - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax subq %rdx, %rdi testl %eax, %eax jnz L(last_vec_return_x0) VPCMPEQ %ymm2, %ymm0, %ymm2 - vpmovmskb %ymm2, %eax + vpmovmskb %ymm2, %eax testl %eax, %eax jnz L(last_vec_return_x1) /* Combine last 2 VEC. */ VPCMPEQ %ymm3, %ymm0, %ymm3 - vpmovmskb %ymm3, %eax - /* rcx has combined result from all 4 VEC. It will only be used if - the first 3 other VEC all did not contain a match. */ + vpmovmskb %ymm3, %eax + /* rcx has combined result from all 4 VEC. It will only be used + if the first 3 other VEC all did not contain a match. */ salq $32, %rcx orq %rcx, %rax tzcntq %rax, %rax subq $(VEC_SIZE * 2 - 1), %rdi addq %rdi, %rax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrq $2, %rax # endif VZEROUPPER_RETURN @@ -297,15 +332,19 @@ L(loop_4x_vec): # ifdef USE_AS_STRNLEN .p2align 4 L(last_4x_vec_or_less_load): - /* Depending on entry adjust rdi / prepare first VEC in ymm1. */ + /* Depending on entry adjust rdi / prepare first VEC in ymm1. + */ subq $-(VEC_SIZE * 4), %rdi L(last_4x_vec_or_less_cmpeq): VPCMPEQ 1(%rdi), %ymm0, %ymm1 L(last_4x_vec_or_less): - - vpmovmskb %ymm1, %eax - /* If remaining length > VEC_SIZE * 2. This works if esi is off by - VEC_SIZE * 4. */ +# ifdef USE_AS_WCSLEN + /* NB: Multiply length by 4 to get byte count. */ + sall $2, %esi +# endif + vpmovmskb %ymm1, %eax + /* If remaining length > VEC_SIZE * 2. This works if esi is off + by VEC_SIZE * 4. */ testl $(VEC_SIZE * 2), %esi jnz L(last_4x_vec) @@ -320,7 +359,7 @@ L(last_4x_vec_or_less): jb L(max) VPCMPEQ (VEC_SIZE + 1)(%rdi), %ymm0, %ymm1 - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax tzcntl %eax, %eax /* Check the end of data. */ cmpl %eax, %esi @@ -329,6 +368,7 @@ L(last_4x_vec_or_less): addl $(VEC_SIZE + 1), %eax addq %rdi, %rax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrq $2, %rax # endif VZEROUPPER_RETURN @@ -340,6 +380,7 @@ L(last_vec_return_x0): subq $(VEC_SIZE * 4 - 1), %rdi addq %rdi, %rax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrq $2, %rax # endif VZEROUPPER_RETURN @@ -350,6 +391,7 @@ L(last_vec_return_x1): subq $(VEC_SIZE * 3 - 1), %rdi addq %rdi, %rax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrq $2, %rax # endif VZEROUPPER_RETURN @@ -366,6 +408,7 @@ L(last_vec_x1_check): incl %eax addq %rdi, %rax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrq $2, %rax # endif VZEROUPPER_RETURN @@ -381,14 +424,14 @@ L(last_4x_vec): jnz L(last_vec_x1) VPCMPEQ (VEC_SIZE + 1)(%rdi), %ymm0, %ymm1 - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax testl %eax, %eax jnz L(last_vec_x2) /* Normalize length. */ andl $(VEC_SIZE * 4 - 1), %esi VPCMPEQ (VEC_SIZE * 2 + 1)(%rdi), %ymm0, %ymm1 - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax testl %eax, %eax jnz L(last_vec_x3) @@ -396,7 +439,7 @@ L(last_4x_vec): jb L(max) VPCMPEQ (VEC_SIZE * 3 + 1)(%rdi), %ymm0, %ymm1 - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax tzcntl %eax, %eax /* Check the end of data. */ cmpl %eax, %esi @@ -405,6 +448,7 @@ L(last_4x_vec): addl $(VEC_SIZE * 3 + 1), %eax addq %rdi, %rax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrq $2, %rax # endif VZEROUPPER_RETURN @@ -419,6 +463,7 @@ L(last_vec_x1): incl %eax addq %rdi, %rax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrq $2, %rax # endif VZEROUPPER_RETURN @@ -432,6 +477,7 @@ L(last_vec_x2): addl $(VEC_SIZE + 1), %eax addq %rdi, %rax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrq $2, %rax # endif VZEROUPPER_RETURN @@ -447,6 +493,7 @@ L(last_vec_x3): addl $(VEC_SIZE * 2 + 1), %eax addq %rdi, %rax # ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ shrq $2, %rax # endif VZEROUPPER_RETURN @@ -455,13 +502,13 @@ L(max_end): VZEROUPPER_RETURN # endif - /* Cold case for crossing page with first load. */ + /* Cold case for crossing page with first load. */ .p2align 4 L(cross_page_boundary): /* Align data to VEC_SIZE - 1. */ orq $(VEC_SIZE - 1), %rdi VPCMPEQ -(VEC_SIZE - 1)(%rdi), %ymm0, %ymm1 - vpmovmskb %ymm1, %eax + vpmovmskb %ymm1, %eax /* Remove the leading bytes. sarxl only uses bits [5:0] of COUNT so no need to manually mod rdx. */ sarxl %edx, %eax, %eax @@ -470,6 +517,10 @@ L(cross_page_boundary): jnz L(cross_page_less_vec) leaq 1(%rdi), %rcx subq %rdx, %rcx +# ifdef USE_AS_WCSLEN + /* NB: Divide bytes by 4 to get wchar_t count. */ + shrl $2, %ecx +# endif /* Check length. */ cmpq %rsi, %rcx jb L(cross_page_continue) @@ -479,6 +530,7 @@ L(cross_page_boundary): jz L(cross_page_continue) tzcntl %eax, %eax # ifdef USE_AS_WCSLEN + /* NB: Divide length by 4 to get wchar_t count. */ shrl $2, %eax # endif # endif @@ -489,6 +541,10 @@ L(return_vzeroupper): .p2align 4 L(cross_page_less_vec): tzcntl %eax, %eax +# ifdef USE_AS_WCSLEN + /* NB: Multiply length by 4 to get byte count. */ + sall $2, %esi +# endif cmpq %rax, %rsi cmovb %esi, %eax # ifdef USE_AS_WCSLEN diff --git a/sysdeps/x86_64/multiarch/strlen-vec.S b/sysdeps/x86_64/multiarch/strlen-vec.S index 8f660bb9c7..439e486a43 100644 --- a/sysdeps/x86_64/multiarch/strlen-vec.S +++ b/sysdeps/x86_64/multiarch/strlen-vec.S @@ -65,12 +65,25 @@ ENTRY(strlen) ret L(n_nonzero): # ifdef AS_WCSLEN - shl $2, %RSI_LP +/* Check for overflow from maxlen * sizeof(wchar_t). If it would + overflow the only way this program doesn't have undefined behavior + is if there is a null terminator in valid memory so wcslen will + suffice. */ + mov %RSI_LP, %R10_LP + sar $62, %R10_LP + test %R10_LP, %R10_LP + jnz __wcslen_sse4_1 + sal $2, %RSI_LP # endif + /* Initialize long lived registers. */ add %RDI_LP, %RSI_LP +# ifdef AS_WCSLEN +/* Check for overflow again from s + maxlen * sizeof(wchar_t). */ + jbe __wcslen_sse4_1 +# endif mov %RSI_LP, %R10_LP and $-64, %R10_LP mov %RSI_LP, %R11_LP