From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x533.google.com (mail-ed1-x533.google.com [IPv6:2a00:1450:4864:20::533]) by sourceware.org (Postfix) with ESMTPS id 6B09D3839D1E for ; Wed, 14 Dec 2022 17:18:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6B09D3839D1E 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-ed1-x533.google.com with SMTP id z92so23515678ede.1 for ; Wed, 14 Dec 2022 09:18:34 -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=h9BaQzN83lCBw5qtd/O+iY2zjtM/TRTwEFIm2NrBQUc=; b=dnE+D/r5NJ381fnJDRcNvtFm9MYkZQSguWY1gpSgl1Z9Fx5rz5sT3qZGplYDTRjLP9 cBdMGY38XSkwCL9zDZhGMo89NeWUmqgqklYbfGa9wONJuf28VJ++uNJcJbxV0BI6Sj9z d4S4aEmfjBwosfxkf+TmQuiHYK/BldccBhuQqS71L5oNGQsH670iupiWy4UOcFuusDhS /f/42IPChj7fEe8UqYJobtt7gLzeaaXGYTlxZ8HYrxgTOfWAJsFutL5SgmMcshOZ7/Wq F9x736jIazorbUkWPod8WQnffkZr8GKuG4Ks57sB7WxuVDmgmSmu1CaVWvEvB2tvqnZI tYGQ== 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=h9BaQzN83lCBw5qtd/O+iY2zjtM/TRTwEFIm2NrBQUc=; b=5gJrvxWIoR/yebNEDYp2Mkl0mBH4QW+S8KjbH8TMkYWzNHvSa7tcRR+RcPnr/J1mkN TDsEXVmKf3o06g1c/uxLbvApihr+mmePvMXmwzlbaZ9uEHz5NkWcSg7xLcvpCZheR7XU PUU70OfiQ1QD12gdRop5QjA2Nk1TSuxsvrEQdA9CWKYEhzmKw8x+FEwafCGqfFDAmroQ iKyGgCIYBju2q658cthAvjodKPyqmtyU4DL2oofCM2QeIUOMmMFOupnfZgvQK8emcJfg iAMaNupw1Flce1I+sI3uP1jDT+7YiOhlplqDDSzPQRYUyZpMnbyJvlNUT/BfcZM9bIUa m99g== X-Gm-Message-State: ANoB5pmq8OIg5bDnWRGxzXe9BQTwFn9sWoDK5ZbqOyKgab1P78PEDa3G KYoovJB5s9EGfdbb61Gp/MdNx2MPoGkBjBi4JRY= X-Google-Smtp-Source: AA0mqf76JiQP4T4cLp+QhtUYjaIsNB7dLBO4Rm1+VvGrxAiAQTuU9rWClgOH7vtN1u5KRW2sUALM5rAuTWZ2jwDtO6E= X-Received: by 2002:aa7:c90a:0:b0:46c:a9ce:9800 with SMTP id b10-20020aa7c90a000000b0046ca9ce9800mr18558046edt.218.1671038313083; Wed, 14 Dec 2022 09:18:33 -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 09:18:21 -0800 Message-ID: Subject: Re: [PATCH v3] x86: Prevent SIGSEGV in memcmp-sse2 when data is concurrently modified [BZ #29863] To: "Carlos O'Donell" Cc: "H.J. Lu" , libc-alpha@sourceware.org, carlos@systemhalted.org Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-9.5 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:57 AM Carlos O'Donell wrote: > > On 12/14/22 11:09, H.J. Lu via Libc-alpha 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. > > I do not recommend a test case. > > I would accept Noah's v3 as-is. I can add a comment around the 'addq' but agree a test case doesn't make sense because at the moment its failure / success is pretty arbitrary. > > Even with a two or three thread test you'd have to run for long enough to statistically > trigger the change at the right time, and that means spending developer CPU resources > to test that a specific IFUNC works under UB conditions. This slows down development > cycle time for a use case we don't actually support. > > I support Noah making this change because it doesn't have a performance impact and > I'm empathetic to fixing a developer reported issue. I wouldn't go any further than that. > > My strong suggestion to yottadb is that they need to write their own hand-crafted memcmp > to ensure the entire algorithm operates under the *must-only-read-bytes-once* conditions. > If you read bytes *twice* due to overlapped loads you may have problems if you read > inconsistent values where you didn't expect them. The algorithm limitations are quite > severe IMO, and any mix of C and asm here could result in the compiler exposing visible > UB to the application author. > > >> movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rsi, %rax), %ecx > >> movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rdi, %rax), %eax > >> subl %ecx, %eax > >> -- > >> 2.34.1 > >> > > > > > > -- > Cheers, > Carlos. >