From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x62c.google.com (mail-ej1-x62c.google.com [IPv6:2a00:1450:4864:20::62c]) by sourceware.org (Postfix) with ESMTPS id AAD043886A02 for ; Wed, 14 Dec 2022 18:52:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org AAD043886A02 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-ej1-x62c.google.com with SMTP id fc4so46718763ejc.12 for ; Wed, 14 Dec 2022 10:52:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=1AVbbYdawysq7k47L42k+kLSONNCDMAljatK1KXCGDY=; b=BHAVuWdlU64cYaQQLCYpBD5xbvMvvYQFMvWoUFFE2KKGG2knANRo+xe6pA2RKpmuEI 9FGWz7CXryDF99O2zw/Xs7noMDWcELesk3mXrtQzzkC7fl6n/m4AjtGow1IsQTadbhGc LzakcEaZl+ZkEBNkPilfQZwFQbLG12NjM65fVd1ltWExj7brYJb59UMfI5Q9X7DsIobC QsgTBBUZ9Wa9H3ibTfbpAreNpofiL5mvHZyN6gd9Znt7L6Lx5B2TIViSoEWlfg6LfRWW KlfEN7rdT6LYSolMsdAD4Bpn6hqQTpSTDHBr9CkX5vn1HglPbFlv2RrjYwupRL40+sxe lTiA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=1AVbbYdawysq7k47L42k+kLSONNCDMAljatK1KXCGDY=; b=DfMo4nuqibxBmDJKVM3FVgnkw4BhtDpUlGFfcJNm2/6vP/q06awwYYnhH4wJetPlZc smkPMRzWsXdPRmyggsBopoFTYP32Gy2LriE9BXXJGOAGddFYRPlBNQpFNV0yoFJSsUC0 Ayh8RM7T7uvT8IPoJm0i05v9bqhLOAMftSPD1x6bc0dFBOqj+7pwsT3TzbIvt1xV+0Py 2KiyqLfDUIjGX+d8EYIrDW13D1cFUiPHgX4WEOtnRxt1aOcxOYW5SoDDoeioPfPh84zp pKdrLopQ3YSBMt4/g6/kM4IT4RUIl+hs0XjbRxOGNXUVZ6B9EKw7qZuF/kdGtVzDb9F2 qbtw== X-Gm-Message-State: ANoB5pmzvQaa5a9hlFmyy/TMUEXxEK/LYUqWJOZYo1O3MDWMQIeXQrMA G4zl84h0gJGawIne6Bgb0JpmPfdxVFuf7ZS1aBQ= X-Google-Smtp-Source: AA0mqf7Dq0JLKx81VydFRXckQ+vFOO4NaqCT3LNVnhTdsqZJvSgv9h9UCUgvHvxXUrYBhckA9WxyBD1sR7HuAO0yPac= X-Received: by 2002:a17:906:809:b0:7c0:e4b8:7587 with SMTP id e9-20020a170906080900b007c0e4b87587mr17232274ejd.593.1671043968359; Wed, 14 Dec 2022 10:52:48 -0800 (PST) MIME-Version: 1.0 References: <20221214001147.2814047-1-goldstein.w.n@gmail.com> <20221214073633.2876766-1-goldstein.w.n@gmail.com> In-Reply-To: From: Noah Goldstein Date: Wed, 14 Dec 2022 10:52:37 -0800 Message-ID: Subject: Re: [PATCH v3] x86: Prevent SIGSEGV in memcmp-sse2 when data is concurrently modified [BZ #29863] To: "H.J. Lu" Cc: libc-alpha@sourceware.org, carlos@systemhalted.org Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-9.7 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.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Wed, Dec 14, 2022 at 8:10 AM H.J. Lu wrote: > > On Tue, Dec 13, 2022 at 11:36 PM Noah Goldstein wrote: > > > > In the case of INCORRECT usage of `memcmp(a, b, N)` where `a` and `b` > > are concurrently modified as `memcmp` runs, there can be a SIGSEGV > > in `L(ret_nonzero_vec_end_0)` because the sequential logic > > assumes that `(rdx - 32 + rax)` is a positive 32-bit integer. > > > > To be clear, this change does not mean the usage of `memcmp` is > > supported. The program behaviour is undefined (UB) in the > > presence of data races, and `memcmp` is incorrect when the values > > of `a` and/or `b` are modified concurrently (data race). This UB > > may manifest itself as a SIGSEGV. That being said, if we can > > allow the idiomatic use cases, like those in yottadb with > > opportunistic concurrency control (OCC), to execute without a > > SIGSEGV, at no cost to regular use cases, then we can aim to > > minimize harm to those existing users. > > > > The fix replaces a 32-bit `addl %edx, %eax` with the 64-bit variant > > `addq %rdx, %rax`. The 1-extra byte of code size from using the > > 64-bit instruction doesn't contribute to overall code size as the > > next target is aligned and has multiple bytes of `nop` padding > > before it. As well all the logic between the add and `ret` still > > fits in the same fetch block, so the cost of this change is > > basically zero. > > > > The relevant sequential logic can be seen in the following > > pseudo-code: > > ``` > > /* > > * rsi = a > > * rdi = b > > * rdx = len - 32 > > */ > > /* cmp a[0:15] and b[0:15]. Since length is known to be [17, 32] > > in this case, this check is also assumed to cover a[0:(31 - len)] > > and b[0:(31 - len)]. */ > > movups (%rsi), %xmm0 > > movups (%rdi), %xmm1 > > PCMPEQ %xmm0, %xmm1 > > pmovmskb %xmm1, %eax > > subl %ecx, %eax > > jnz L(END_NEQ) > > > > /* cmp a[len-16:len-1] and b[len-16:len-1]. */ > > movups 16(%rsi, %rdx), %xmm0 > > movups 16(%rdi, %rdx), %xmm1 > > PCMPEQ %xmm0, %xmm1 > > pmovmskb %xmm1, %eax > > subl %ecx, %eax > > jnz L(END_NEQ2) > > ret > > > > L(END2): > > /* Position first mismatch. */ > > bsfl %eax, %eax > > > > /* The sequential version is able to assume this value is a > > positive 32-bit value because the first check included bytes in > > range a[0:(31 - len)] and b[0:(31 - len)] so `eax` must be > > greater than `31 - len` so the minimum value of `edx` + `eax` is > > `(len - 32) + (32 - len) >= 0`. In the concurrent case, however, > > `a` or `b` could have been changed so a mismatch in `eax` less or > > equal than `(31 - len)` is possible (the new low bound is `(16 - > > len)`. This can result in a negative 32-bit signed integer, which > > when zero extended to 64-bits is a random large value this out > > out of bounds. */ > > addl %edx, %eax > > > > /* Crash here because 32-bit negative number in `eax` zero > > extends to out of bounds 64-bit offset. */ > > movzbl 16(%rdi, %rax), %ecx > > movzbl 16(%rsi, %rax), %eax > > ``` > > > > This fix is quite simple, just make the `addl %edx, %eax` 64 bit (i.e > > `addq %rdx, %rax`). This prevents the 32-bit zero extension > > and since `eax` is still a low bound of `16 - len` the `rdx + rax` > > is bound by `(len - 32) - (16 - len) >= -16`. Since we have a > > fixed offset of `16` in the memory access this must be in bounds. > > --- > > sysdeps/x86_64/multiarch/memcmp-sse2.S | 2 +- > > 1 file changed, 1 insertion(+), 1 deletion(-) > > > > diff --git a/sysdeps/x86_64/multiarch/memcmp-sse2.S b/sysdeps/x86_64/multiarch/memcmp-sse2.S > > index afd450d020..34e60e567d 100644 > > --- a/sysdeps/x86_64/multiarch/memcmp-sse2.S > > +++ b/sysdeps/x86_64/multiarch/memcmp-sse2.S > > @@ -308,7 +308,7 @@ L(ret_nonzero_vec_end_0): > > setg %dl > > leal -1(%rdx, %rdx), %eax > > # else > > - addl %edx, %eax > > + addq %rdx, %rax > > Please add some comments here and a testcase. Added comments. > > > movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rsi, %rax), %ecx > > movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rdi, %rax), %eax > > subl %ecx, %eax > > -- > > 2.34.1 > > > > > -- > H.J.