From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 3809338388EF for ; Wed, 14 Dec 2022 04:42:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3809338388EF Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1670992972; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=uZRRJ4ekvfHDuPD1N/uLKFRrHmvMtV1wZaoRPSY1clE=; b=StWVkKTZfRyCGEREtZJcJOVOneI6DonJKXHdcvODxy4uapzttUX+ED1Kc6+Y/wqn9Y5fXy udN82iRuUgoayhrOckQtEvOhFVx7Q4B8lbtA5em2SI0hw+BZ+N/7DraM9z9hV5hzLa4b5Z lQkwcLhvmu6mrruI8bie+Ja+seFES6E= Received: from mail-io1-f70.google.com (mail-io1-f70.google.com [209.85.166.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-401-zEKigfdXPlC293j8Keg7Qw-1; Tue, 13 Dec 2022 23:42:51 -0500 X-MC-Unique: zEKigfdXPlC293j8Keg7Qw-1 Received: by mail-io1-f70.google.com with SMTP id s22-20020a6bdc16000000b006e2d7c78010so3227815ioc.21 for ; Tue, 13 Dec 2022 20:42:50 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:organization:from:references :cc:to:content-language:subject:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=uZRRJ4ekvfHDuPD1N/uLKFRrHmvMtV1wZaoRPSY1clE=; b=bBDrY6dH/eLVzDu4kKLjc0yaxdfh31Sb68lOIq8oFrWNSCgBWd4+yFfRDnOlGyu29q 6ZSzMtKBVfN0wgXYeSYXOLfaTWggRQTVf+oZE5R4lr+2WaBuP7X8SdtJVXMo4XAmGW6z Cas0MuxZZg8tcgqzTRU1ZSqxbMvDs3koIzJkfGDsPGP5yyp5GIG4UpDecCVN5dR00Z84 bzHk9p1D42wF4JA/zgTz+thRUcGo1Ub5SjzZH5GyulaFtBnWX752eZkSPziJ94ymU7pg UDQfc3TqK/DV3ay/A2MeOtqMVdXP9tL2NatS572LxXnzYJ/zUO88KethoJpebTWiuATk 9Y9Q== X-Gm-Message-State: ANoB5pmAi9pjaTemBLGvcvIQM1wC+fqabUGkVzw5dEFkzCUkJ7jo3ivI ZVo9xOH5vjux6BHlJRVBLWJvNsafEv/6WtSqJ5iV0BW2NJQAOlfwcKuPS8yZPqVYbifs6/gUWUe YpIIqRZszstkx/lF4jdY5 X-Received: by 2002:a05:6602:2593:b0:6bb:df57:d586 with SMTP id p19-20020a056602259300b006bbdf57d586mr14698397ioo.0.1670992970328; Tue, 13 Dec 2022 20:42:50 -0800 (PST) X-Google-Smtp-Source: AA0mqf4kGPTyUURE7eMJjCHF0Qop1VVKrPWoLVztlWIOeHg0vjvDGTNY2q2AVO3nUQlwb1mrJyxu9g== X-Received: by 2002:a05:6602:2593:b0:6bb:df57:d586 with SMTP id p19-20020a056602259300b006bbdf57d586mr14698387ioo.0.1670992969995; Tue, 13 Dec 2022 20:42:49 -0800 (PST) Received: from [192.168.0.241] (192-0-145-146.cpe.teksavvy.com. [192.0.145.146]) by smtp.gmail.com with ESMTPSA id g24-20020a02b718000000b0037556012c63sm1422763jam.132.2022.12.13.20.42.48 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 13 Dec 2022 20:42:49 -0800 (PST) Message-ID: <0bea29e1-f0d6-a0da-1b83-4d9aeccfa1ac@redhat.com> Date: Tue, 13 Dec 2022 23:42:48 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.4.0 Subject: Re: [PATCH v2] x86: Prevent SIGSEGV in memcmp-sse2 when data is concurrently modified [BZ #29863] To: Noah Goldstein , libc-alpha@sourceware.org Cc: hjl.tools@gmail.com, carlos@systemhalted.org References: <20221214001147.2814047-1-goldstein.w.n@gmail.com> <20221214032528.2859009-1-goldstein.w.n@gmail.com> From: Carlos O'Donell Organization: Red Hat In-Reply-To: <20221214032528.2859009-1-goldstein.w.n@gmail.com> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-12.6 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,NICE_REPLY_A,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,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: OK, last wordsmith pass, I promise. Please post a v3 and I'll ACK that. On 12/13/22 22:25, Noah Goldstein via Libc-alpha 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 "fix" does not mean this usage of `memcmp` is > supported. `memcmp` is incorrect when the values of `a` and/or `b` > are modified while its running, and that incorrectness may manifest > itself as a SIGSEGV. That being said, if we can make the results > less dramatic with no cost to regular use cases, there is no harm > in doing so. Suggest: 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. OK. > 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 non-sign extended to 64-bits is a random large value this is s/this/that/g > out of bounds. */ addl %edx, %eax Please put the addl on a new line. > > /* Crash here because 32-bit negative number in `eax` non-sign > 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 non-sign 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 OK. > movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rsi, %rax), %ecx > movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rdi, %rax), %eax > subl %ecx, %eax -- Cheers, Carlos.