* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change [not found] ` <PAWPR08MB898260DA844D695EA70ED3E483E09@PAWPR08MB8982.eurprd08.prod.outlook.com> @ 2022-12-14 21:56 ` Wilco Dijkstra 2022-12-29 7:21 ` Zack Weinberg 0 siblings, 1 reply; 22+ messages in thread From: Wilco Dijkstra @ 2022-12-14 21:56 UTC (permalink / raw) To: zack, Carlos O'Donell; +Cc: 'GNU C Library' Hi, >On Tue, Dec 13, 2022, at 11:16 PM, Carlos O'Donell wrote: >> The standards are in no way prescriptive in saying that memcmp shall not read or >> write to memory outside of the input domain. > > ... is (as I read it) contradicted by 7.1.4p5 (N1570) "A library function shall not directly or > indirectly access objects accessible by threads other than the current thread unless the > objects are accessed directly or indirectly via the function's arguments." There is more > wiggle room in this wording than I'd ideally like, but since memcmp has no way of knowing > whether any particular piece of data outside the ranges supplied as arguments is "accessible > by threads other than the current thread", it needs to be conservative and not touch any of it. I'd expect that mem* functions will never read outside their bounds since the bounds are explicitly defined by the arguments, not by the data. So that should be easy to guarantee. For the str* functions it may be harder since the data itself defines when to stop reading. So if an implementation uses multiple accesses to the same address, you could potentially mistake the end of a string (eg. first one detects a special case, while the 2nd then verifies it). Still, I wouldn't expect totally random memory accesses even in this case - you would read beyond the end of a string if the string end is changed concurrently. Note there is also a security risk here - an attacker could cause an out of bounds access to extract secret data that otherwise wouldn't be accessible. Eg. functions in the Linux kernel accessing user data should be resilient to concurrent modifications of the data. Finally it's worth mentioning that nscd does the exact same thing: it uses memcmp and non-atomic accesses on shared data that is being modified by other threads. It looks totally broken, especially with weaker memory ordering, however this kind of insanity may actually be a common design pattern... Cheers, Wilco ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-14 21:56 ` Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change Wilco Dijkstra @ 2022-12-29 7:21 ` Zack Weinberg 2022-12-29 20:02 ` Alejandro Colomar 0 siblings, 1 reply; 22+ messages in thread From: Zack Weinberg @ 2022-12-29 7:21 UTC (permalink / raw) To: Wilco Dijkstra; +Cc: Carlos O'Donell, 'GNU C Library' On Wed, 14 Dec 2022 16:56:28 -0500, Wilco Dijkstra wrote: > I'd expect that mem* functions will never read outside their bounds > since the bounds are explicitly defined by the arguments, not by the > data. So that should be easy to guarantee. I concur. > For the str* functions it may be harder since the data itself > defines when to stop reading. So if an implementation uses multiple > accesses to the same address, you could potentially mistake the end > of a string (eg. first one detects a special case, while the 2nd > then verifies it). I also concur here. > Still, I wouldn't expect totally random memory accesses even in this > case - you would read beyond the end of a string if the string end > is changed concurrently. We may run into a problem where it’s difficult to _state_ the limits of the misbehavior, just because the C standard doesn’t itself try to put limits on misbehavior in the face of an incorrect program, so we don’t have any language for it (which I would argue is a bug in the standard, see the detailed reply to Carlos that I’ll be writing, er, tomorrow). Still, taking strcmp(a, b) for example, and assuming WLOG a flat address space in which a < b, it should be possible to guarantee - no accesses to any byte in the range [0, a) ever - if an oracle for strlen(), capable of executing in zero cycles, would return the same value for strlen(a) throughout the execution of strcmp(), then no accesses to any byte in the range [a+strlen(a), b) - if an oracle for strlen(), capable of executing in zero cycles, would return the same value for strlen(b) throughout the execution of strcmp(), then no accesses to any byte in the range [b+strlen(b), ADDR_MAX) - however, if the oracle strlen() values _do_ change during the execution of strcmp(), then accesses to bytes in the latter two ranges are possible - a SIGSEGV is permissible if and only if there was at least one point during execution at which a call to the oracle strlen() would have triggered a SIGSEGV Ne? > Finally it's worth mentioning that nscd does the exact same thing: > it uses memcmp and non-atomic accesses on shared data that is being > modified by other threads. It looks totally broken, especially with > weaker memory ordering, however this kind of insanity may actually > be a common design pattern... I don’t want to hold up nscd as an example of quality design or implementation, but yeah, I share your concern re “may actually be a common design pattern”… zw ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-29 7:21 ` Zack Weinberg @ 2022-12-29 20:02 ` Alejandro Colomar 2022-12-30 18:02 ` Joseph Myers 0 siblings, 1 reply; 22+ messages in thread From: Alejandro Colomar @ 2022-12-29 20:02 UTC (permalink / raw) To: Zack Weinberg, Wilco Dijkstra Cc: Carlos O'Donell, 'GNU C Library' Hi Zack, On 12/29/22 08:21, Zack Weinberg via Libc-alpha wrote: > On Wed, 14 Dec 2022 16:56:28 -0500, Wilco Dijkstra wrote: >> I'd expect that mem* functions will never read outside their bounds >> since the bounds are explicitly defined by the arguments, not by the >> data. So that should be easy to guarantee. > > I concur. > >> For the str* functions it may be harder since the data itself >> defines when to stop reading. So if an implementation uses multiple >> accesses to the same address, you could potentially mistake the end >> of a string (eg. first one detects a special case, while the 2nd >> then verifies it). > > I also concur here. > >> Still, I wouldn't expect totally random memory accesses even in this >> case - you would read beyond the end of a string if the string end >> is changed concurrently. > > We may run into a problem where it’s difficult to _state_ the limits > of the misbehavior, just because the C standard doesn’t itself try to > put limits on misbehavior in the face of an incorrect program, so we > don’t have any language for it (which I would argue is a bug in the > standard, see the detailed reply to Carlos that I’ll be writing, er, > tomorrow). The standard already makes some kind of guarantee, when it differences between bound UB and critical UB. The problem is that once you've met bound UB, it's hard not to convert it to critical UB in the following lines of code. Even a compiler assumption that would otherwise be fine might result in critical UB. > > Still, taking strcmp(a, b) for example, and assuming WLOG a flat > address space in which a < b, it should be possible to guarantee > > - no accesses to any byte in the range [0, a) ever > - if an oracle for strlen(), capable of executing in zero cycles, > would return the same value for strlen(a) throughout the execution > of strcmp(), then no accesses to any byte in the range > [a+strlen(a), b) > - if an oracle for strlen(), capable of executing in zero cycles, > would return the same value for strlen(b) throughout the execution > of strcmp(), then no accesses to any byte in the range > [b+strlen(b), ADDR_MAX) > - however, if the oracle strlen() values _do_ change during the > execution of strcmp(), then accesses to bytes in the latter two > ranges are possible > - a SIGSEGV is permissible if and only if there was at least one > point during execution at which a call to the oracle strlen() would > have triggered a SIGSEGV Are you meaning this would be an invalid implementation of strcmp(3)?: int strcmp(const char *s1, const char *s2) { for (; *s1 != '\0' || *s1 != '\0'; s1++, s2++) { if (*s1 < *s2) return -1; if (*s1 > *s2) return 1; } } Okay, probably it's not the fastest one, but it's simple. This one would SIGSEGV in the following case: Another thread might insert a NUL at the beginning of each string (after the loop has passed over it), and in the next cycle remove the previously-terminating NUL from the strings. The loop would then run forever, until a crash. Cheers, Alex > > Ne? > >> Finally it's worth mentioning that nscd does the exact same thing: >> it uses memcmp and non-atomic accesses on shared data that is being >> modified by other threads. It looks totally broken, especially with >> weaker memory ordering, however this kind of insanity may actually >> be a common design pattern... > > I don’t want to hold up nscd as an example of quality design or > implementation, but yeah, I share your concern re “may actually be a > common design pattern”… > > zw ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-29 20:02 ` Alejandro Colomar @ 2022-12-30 18:02 ` Joseph Myers 2023-03-20 15:40 ` Zack Weinberg 0 siblings, 1 reply; 22+ messages in thread From: Joseph Myers @ 2022-12-30 18:02 UTC (permalink / raw) To: Alejandro Colomar Cc: Zack Weinberg, Wilco Dijkstra, Carlos O'Donell, 'GNU C Library' On Thu, 29 Dec 2022, Alejandro Colomar via Libc-alpha wrote: > Okay, probably it's not the fastest one, but it's simple. This one would > SIGSEGV in the following case: > > Another thread might insert a NUL at the beginning of each string (after the > loop has passed over it), and in the next cycle remove the > previously-terminating NUL from the strings. The loop would then run forever, > until a crash. I also think it should be OK for strcmp to SEGV if a NUL terminator byte in either string at the time strlen is called, or at any time during its execution, ceases at any point during the execution of strlen to be a NUL byte (even if there is an earlier or later NUL already present at the time the terminator byte is changed). (There is a reasonable case for avoiding a SEGV when the contents of the strings change during execution, as long as any byte that is the NUL terminator byte at any point during execution of the call never ceases to be a NUL byte during execution of that call - an earlier NUL might be added, however.) -- Joseph S. Myers joseph@codesourcery.com ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-30 18:02 ` Joseph Myers @ 2023-03-20 15:40 ` Zack Weinberg 0 siblings, 0 replies; 22+ messages in thread From: Zack Weinberg @ 2023-03-20 15:40 UTC (permalink / raw) To: Joseph Myers, 'Alejandro Colomar (man-pages)' Cc: Wilco Dijkstra, Carlos O'Donell, GNU libc development On Fri, Dec 30, 2022, at 1:02 PM, Joseph Myers wrote: > I also think it should be OK for strcmp to SEGV if a NUL terminator > byte in either string at the time strlen is called, or at any time > during its execution, ceases at any point during the execution of > strlen to be a NUL byte (even if there is an earlier or later NUL > already present at the time the terminator byte is changed). (There > is a reasonable case for avoiding a SEGV when the contents of the > strings change during execution, as long as any byte that is the NUL > terminator byte at any point during execution of the call never ceases > to be a NUL byte during execution of that call - an earlier NUL might > be added, however.) Coming back to this ages later, I'm not sure how this differs from what I said about the oracle for strlen... Imagine we have a hardware debugger that can freeze execution of the entire computer at the moment the call instruction for strcmp is invoked, perform strlen() on both strings passed to strcmp, and then resume execution. Call the string lengths measured by this hypothetical debugger the "original" string lengths. What I was trying to communicate is that any concurrent modification to the strings that *changes either string's length from its original* should still permit constrained-unpredictable behavior by the implementation of strcmp. It seems to me that this is the same as talking about insertion or deletion of NULs within the bounds of the original string lengths. zw ^ permalink raw reply [flat|nested] 22+ messages in thread
* Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change @ 2022-12-13 18:20 Narayanan Iyer 2022-12-13 18:31 ` Andrew Pinski ` (2 more replies) 0 siblings, 3 replies; 22+ messages in thread From: Narayanan Iyer @ 2022-12-13 18:20 UTC (permalink / raw) To: libc-alpha; +Cc: Narayanan Iyer Hi, I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863 And have included the title of that report in the email subject as well. It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression). Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers. I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37. Thanks, Narayanan. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 18:20 Narayanan Iyer @ 2022-12-13 18:31 ` Andrew Pinski 2022-12-13 18:39 ` Narayanan Iyer 2022-12-13 18:39 ` Cristian Rodríguez 2022-12-13 19:08 ` Noah Goldstein 2 siblings, 1 reply; 22+ messages in thread From: Andrew Pinski @ 2022-12-13 18:31 UTC (permalink / raw) To: Narayanan Iyer; +Cc: libc-alpha On Tue, Dec 13, 2022 at 10:21 AM Narayanan Iyer via Libc-alpha <libc-alpha@sourceware.org> wrote: > > Hi, > > I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863 > > And have included the title of that report in the email subject as well. > > It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression). I don't see how this is a valid well defined testcase. Changing memory without barriers in both threads is not well defined. memcmp is not guaranteed to be atomic or have any atomicity either. So you just happen to work before and now your undefined code does not work. Thanks, Andrew Pinski > > Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers. > > I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37. > > Thanks, > Narayanan. > > ^ permalink raw reply [flat|nested] 22+ messages in thread
* RE: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 18:31 ` Andrew Pinski @ 2022-12-13 18:39 ` Narayanan Iyer 0 siblings, 0 replies; 22+ messages in thread From: Narayanan Iyer @ 2022-12-13 18:39 UTC (permalink / raw) To: 'Andrew Pinski'; +Cc: libc-alpha As I also mentioned at https://sourceware.org/bugzilla/show_bug.cgi?id=29863#c3, it might not be a well defined test case. But memcmp() is never expected to SIG-11 in any circumstance as long as the buffers it is passed in are accessible from start to finish. In the same bug report, I had also provided a timeline of the instructions that I believe got executed in the crash case and pointed to the failing assembly instruction. The test case was just a easy way for you to see the problem yourself. Even if you don't accept the test case, can you take a look at the rest of my bug report to see if you agree with the finding. Thanks, Narayanan. -----Original Message----- From: Andrew Pinski [mailto:pinskia@gmail.com] Sent: Tuesday, December 13, 2022 1:32 PM To: Narayanan Iyer <nars@yottadb.com> Cc: libc-alpha@sourceware.org Subject: Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change On Tue, Dec 13, 2022 at 10:21 AM Narayanan Iyer via Libc-alpha <libc-alpha@sourceware.org> wrote: > > Hi, > > I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863 > > And have included the title of that report in the email subject as well. > > It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression). I don't see how this is a valid well defined testcase. Changing memory without barriers in both threads is not well defined. memcmp is not guaranteed to be atomic or have any atomicity either. So you just happen to work before and now your undefined code does not work. Thanks, Andrew Pinski > > Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers. > > I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37. > > Thanks, > Narayanan. > > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 18:20 Narayanan Iyer 2022-12-13 18:31 ` Andrew Pinski @ 2022-12-13 18:39 ` Cristian Rodríguez 2022-12-13 19:08 ` Noah Goldstein 2 siblings, 0 replies; 22+ messages in thread From: Cristian Rodríguez @ 2022-12-13 18:39 UTC (permalink / raw) To: Narayanan Iyer; +Cc: libc-alpha On Tue, Dec 13, 2022 at 3:20 PM Narayanan Iyer via Libc-alpha <libc-alpha@sourceware.org> wrote: > > Hi, > > I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863 > It might as well make a shelter.. from pigs on the wing... That's UB all the way. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 18:20 Narayanan Iyer 2022-12-13 18:31 ` Andrew Pinski 2022-12-13 18:39 ` Cristian Rodríguez @ 2022-12-13 19:08 ` Noah Goldstein 2022-12-13 19:13 ` Narayanan Iyer 2022-12-13 21:20 ` Florian Weimer 2 siblings, 2 replies; 22+ messages in thread From: Noah Goldstein @ 2022-12-13 19:08 UTC (permalink / raw) To: Narayanan Iyer; +Cc: libc-alpha On Tue, Dec 13, 2022 at 10:20 AM Narayanan Iyer via Libc-alpha <libc-alpha@sourceware.org> wrote: > > Hi, > > I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863 > > And have included the title of that report in the email subject as well. > > It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression). > > Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers. > > I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37. > > Thanks, > Narayanan. > > The fix: https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse2.S;h=afd450d0206d6633da9fbc4607a7fa6aeb4e137c;hb=HEAD#l46 ``` -# define SIZE_OFFSET (CHAR_PER_VEC * 2) +# define SIZE_OFFSET 0 ``` Is this something we have to support? I believe other functions / implementations of memcmp will suffer from a similar bug. ^ permalink raw reply [flat|nested] 22+ messages in thread
* RE: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 19:08 ` Noah Goldstein @ 2022-12-13 19:13 ` Narayanan Iyer 2022-12-13 19:25 ` Noah Goldstein 2022-12-13 21:20 ` Florian Weimer 1 sibling, 1 reply; 22+ messages in thread From: Narayanan Iyer @ 2022-12-13 19:13 UTC (permalink / raw) To: 'Noah Goldstein'; +Cc: libc-alpha Noah, Thank you for acknowledging that it is a bug. In case it helps, I found in our testing cluster, that a system which uses sysdeps/x86_64/multiarch/memcmp-sse2.S has the bug whereas a system that uses sysdeps/x86_64/multiarch/memcmp-avx2-movbe.S does not have the bug. So it is possible, the issue is only in the sse2 version. Thanks, Narayanan. -----Original Message----- From: Noah Goldstein [mailto:goldstein.w.n@gmail.com] Sent: Tuesday, December 13, 2022 2:08 PM To: Narayanan Iyer <nars@yottadb.com> Cc: libc-alpha@sourceware.org Subject: Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change On Tue, Dec 13, 2022 at 10:20 AM Narayanan Iyer via Libc-alpha <libc-alpha@sourceware.org> wrote: > > Hi, > > I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863 > > And have included the title of that report in the email subject as well. > > It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression). > > Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers. > > I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37. > > Thanks, > Narayanan. > > The fix: https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse2.S;h=afd450d0206d6633da9fbc4607a7fa6aeb4e137c;hb=HEAD#l46 ``` -# define SIZE_OFFSET (CHAR_PER_VEC * 2) +# define SIZE_OFFSET 0 ``` Is this something we have to support? I believe other functions / implementations of memcmp will suffer from a similar bug. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 19:13 ` Narayanan Iyer @ 2022-12-13 19:25 ` Noah Goldstein 2022-12-13 20:56 ` Zack Weinberg 0 siblings, 1 reply; 22+ messages in thread From: Noah Goldstein @ 2022-12-13 19:25 UTC (permalink / raw) To: Narayanan Iyer; +Cc: libc-alpha On Tue, Dec 13, 2022 at 11:13 AM Narayanan Iyer <nars@yottadb.com> wrote: > > Noah, > > Thank you for acknowledging that it is a bug. I'm not sure this is a bug, I'm just saying to avoid this behavior you can make that change. I think we all agree supporting a correct non-atomic memcmp when the values in memory can change during execution is not reasonable. I think SIG11 is not a great outcome (of the many possible behaviors when its incorrect), but am not sure it's worth fixing. > > In case it helps, I found in our testing cluster, that a system which uses sysdeps/x86_64/multiarch/memcmp-sse2.S has the bug whereas a system that uses sysdeps/x86_64/multiarch/memcmp-avx2-movbe.S does not have the bug. I wouldn't count on any of the other implementations being hardened to this. > > So it is possible, the issue is only in the sse2 version. I did a quick check of avx2/evex and don't see the same pattern but I think it might be present in the tail of the loops (end of much larger copies so probably comes up less). > > Thanks, > Narayanan. > > -----Original Message----- > From: Noah Goldstein [mailto:goldstein.w.n@gmail.com] > Sent: Tuesday, December 13, 2022 2:08 PM > To: Narayanan Iyer <nars@yottadb.com> > Cc: libc-alpha@sourceware.org > Subject: Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change > > On Tue, Dec 13, 2022 at 10:20 AM Narayanan Iyer via Libc-alpha > <libc-alpha@sourceware.org> wrote: > > > > Hi, > > > > I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863 > > > > And have included the title of that report in the email subject as well. > > > > It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression). > > > > Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers. > > > > I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37. > > > > Thanks, > > Narayanan. > > > > > > The fix: > https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse2.S;h=afd450d0206d6633da9fbc4607a7fa6aeb4e137c;hb=HEAD#l46 > ``` > -# define SIZE_OFFSET (CHAR_PER_VEC * 2) > +# define SIZE_OFFSET 0 > ``` > > Is this something we have to support? I believe other functions / > implementations > of memcmp will suffer from a similar bug. > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 19:25 ` Noah Goldstein @ 2022-12-13 20:56 ` Zack Weinberg 2022-12-13 23:29 ` Carlos O'Donell 0 siblings, 1 reply; 22+ messages in thread From: Zack Weinberg @ 2022-12-13 20:56 UTC (permalink / raw) To: GNU libc development On Tue, Dec 13, 2022, at 2:25 PM, Noah Goldstein via Libc-alpha wrote: > On Tue, Dec 13, 2022 at 11:13 AM Narayanan Iyer <nars@yottadb.com> wrote: >> Thank you for acknowledging that it is a bug. > I'm not sure this is a bug, I'm just saying to avoid this behavior you can > make that change. > > I think we all agree supporting a correct non-atomic memcmp when the values > in memory can change during execution is not reasonable. > I think SIG11 is not a great outcome (of the many possible behaviors when its > incorrect), but am not sure it's worth fixing. I think it would be reasonable for glibc to make the following weaker guarantee: for any call `memcmp(a, b, n)`, if the data pointed to by `a` and/or `b` is being concurrently modified, the return value is unspecified but *not* indeterminate. Also, memcmp will never access memory outside the bounds [a, a+n) and [b, b+n), no matter what. This would, I believe, be sufficient to prevent a crash under the conditions described by Narayanan Iyer. zw ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 20:56 ` Zack Weinberg @ 2022-12-13 23:29 ` Carlos O'Donell 2022-12-14 2:28 ` Zack Weinberg 0 siblings, 1 reply; 22+ messages in thread From: Carlos O'Donell @ 2022-12-13 23:29 UTC (permalink / raw) To: Zack Weinberg, GNU libc development On 12/13/22 15:56, Zack Weinberg via Libc-alpha wrote: > On Tue, Dec 13, 2022, at 2:25 PM, Noah Goldstein via Libc-alpha wrote: >> On Tue, Dec 13, 2022 at 11:13 AM Narayanan Iyer <nars@yottadb.com> wrote: >>> Thank you for acknowledging that it is a bug. >> I'm not sure this is a bug, I'm just saying to avoid this behavior you can >> make that change. >> >> I think we all agree supporting a correct non-atomic memcmp when the values >> in memory can change during execution is not reasonable. >> I think SIG11 is not a great outcome (of the many possible behaviors when its >> incorrect), but am not sure it's worth fixing. > > I think it would be reasonable for glibc to make the following weaker guarantee: > for any call `memcmp(a, b, n)`, if the data pointed to by `a` and/or `b` is being > concurrently modified, the return value is unspecified but *not* indeterminate. > Also, memcmp will never access memory outside the bounds [a, a+n) and [b, b+n), > no matter what. I disagree strongly. These are advanced lockless techniques. They should be hidden behind new APIs that provide the required guarantees. > This would, I believe, be sufficient to prevent a crash under the conditions > described by Narayanan Iyer. I would want to see compiler and langauge authors agree to such changes. -- Cheers, Carlos. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 23:29 ` Carlos O'Donell @ 2022-12-14 2:28 ` Zack Weinberg 2022-12-14 4:16 ` Carlos O'Donell 0 siblings, 1 reply; 22+ messages in thread From: Zack Weinberg @ 2022-12-14 2:28 UTC (permalink / raw) To: Carlos O'Donell; +Cc: GNU libc development Carlos O'Donell <carlos@redhat.com> writes: > On 12/13/22 15:56, Zack Weinberg via Libc-alpha wrote: >> I think it would be reasonable for glibc to make the following weaker guarantee: >> for any call `memcmp(a, b, n)`, if the data pointed to by `a` and/or `b` is being >> concurrently modified, the return value is unspecified but *not* indeterminate. >> Also, memcmp will never access memory outside the bounds [a, a+n) and [b, b+n), >> no matter what. > > I disagree strongly. I’m really surprised to hear you say that. To me this is a natural guarantee for memcmp — in fact, for *all* of the mem* functions — to make, to the point where my reaction was *of course* this is our bug! > These are advanced lockless techniques. > They should be hidden behind new APIs that provide the required guarantees. That the application was doing “advanced lockless techniques” is, to me, not relevant in the slightest. The important thing to me is that the memory regions `memcmp` is allowed to access are wholly specified by the mathematical values of its three arguments, and *not* by the data pointed to by the first two arguments. Nothing any other thread does can change the fact that memcmp has no business touching bytes at addresses outside [a, a+n) and [b, b+n). Why do you think it is important for the C library to have latitude to break that aspect of the mem* functions’ API contract? Even if only under exotic circumstances? zw ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-14 2:28 ` Zack Weinberg @ 2022-12-14 4:16 ` Carlos O'Donell 2022-12-14 14:16 ` Zack Weinberg 0 siblings, 1 reply; 22+ messages in thread From: Carlos O'Donell @ 2022-12-14 4:16 UTC (permalink / raw) To: Zack Weinberg; +Cc: GNU libc development On 12/13/22 21:28, Zack Weinberg wrote: > Carlos O'Donell <carlos@redhat.com> writes: > >> On 12/13/22 15:56, Zack Weinberg via Libc-alpha wrote: >>> I think it would be reasonable for glibc to make the following weaker guarantee: >>> for any call `memcmp(a, b, n)`, if the data pointed to by `a` and/or `b` is being >>> concurrently modified, the return value is unspecified but *not* indeterminate. >>> Also, memcmp will never access memory outside the bounds [a, a+n) and [b, b+n), >>> no matter what. >> >> I disagree strongly. > > I’m really surprised to hear you say that. To me this is a natural > guarantee for memcmp — in fact, for *all* of the mem* functions — to > make, to the point where my reaction was *of course* this is our bug! Please let me expand on my answer. We are talking about the C language, and when you write "unspecified" in that context it means the language *does* have something to say about the behaviour but does not pick one or other of the available behaviours. This is not the case, the language very clearly says this is undefined behaviour, so it says nothing about what should happen. My understanding was that you were trying to ascribe more determinism to the operation of memcpy under the presence of data races than could be granted by UB. I strongly disagree to ascribing more determinism than UB. Could you expand on why you think this is a "natural" guarantee and from what that derives from? Is it that you view the input domain to the function as the "natural" bytes upon which the function is allowed to operate? >> These are advanced lockless techniques. >> They should be hidden behind new APIs that provide the required guarantees. > > That the application was doing “advanced lockless techniques” is, to me, If the application does not follow the language requirements then it is UB. There are some advanced lockless techniques that do not follow the C memory model. My point is that such techniques and the requirements should be well understood and implemented by APIs that provide the required guarantees, not by existing C string and memory APIs. > not relevant in the slightest. The important thing to me is that the > memory regions `memcmp` is allowed to access are wholly specified by the > mathematical values of its three arguments, and *not* by the data > pointed to by the first two arguments. Nothing any other thread does > can change the fact that memcmp has no business touching bytes at > addresses outside [a, a+n) and [b, b+n). I strongly disagree (though the quiet theoretician in me agrees with you). The standards are in no way prescriptive in saying that memcmp shall not read or write to memory outside of the input domain. > Why do you think it is important for the C library to have latitude to > break that aspect of the mem* functions’ API contract? Even if only > under exotic circumstances? Why do you think an application programmer has the right to ignore the requirements of the language and expect the runtime to operate as intended? Why would we as library authors enter into an API contract that is *stronger* than the language guarantees? I am empathetic to the yottadb developers, but we need new APIs for these requirements. I will still review Noah's patch here: https://sourceware.org/pipermail/libc-alpha/2022-December/144058.html I do not have a sustained objection to modifying things to "just work" (tm) because with UB you could do anything, and it doesn't impact the normal use cases. That is to say for a specific patch, and a specific change, I can agree, but not to the larger generalizations about memcmp. -- Cheers, Carlos. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-14 4:16 ` Carlos O'Donell @ 2022-12-14 14:16 ` Zack Weinberg 2022-12-14 17:36 ` Paolo Bonzini 0 siblings, 1 reply; 22+ messages in thread From: Zack Weinberg @ 2022-12-14 14:16 UTC (permalink / raw) To: Carlos O'Donell; +Cc: GNU libc development I'll respond to this at more length later, but I want to point out that this statement ... On Tue, Dec 13, 2022, at 11:16 PM, Carlos O'Donell wrote: > The standards are in no way prescriptive in saying that memcmp shall not read or > write to memory outside of the input domain. ... is (as I read it) contradicted by 7.1.4p5 (N1570) "A library function shall not directly or indirectly access objects accessible by threads other than the current thread unless the objects are accessed directly or indirectly via the function's arguments." There is more wiggle room in this wording than I'd ideally like, but since memcmp has no way of knowing whether any particular piece of data outside the ranges supplied as arguments is "accessible by threads other than the current thread", it needs to be conservative and not touch any of it. zw ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-14 14:16 ` Zack Weinberg @ 2022-12-14 17:36 ` Paolo Bonzini 2022-12-29 7:09 ` Zack Weinberg 0 siblings, 1 reply; 22+ messages in thread From: Paolo Bonzini @ 2022-12-14 17:36 UTC (permalink / raw) To: Zack Weinberg, Carlos O'Donell; +Cc: GNU libc development On 12/14/22 15:16, Zack Weinberg via Libc-alpha wrote: >> The standards are in no way prescriptive in saying that memcmp >> shall not read or write to memory outside of the input domain. > > ... is (as I read it) contradicted by 7.1.4p5 (N1570) "A library > function shall not directly or indirectly access objects accessible > by threads other than the current thread unless the objects are > accessed directly or indirectly via the function's arguments." There > is more wiggle room in this wording than I'd ideally like, but since > memcmp has no way of knowing whether any particular piece of data > outside the ranges supplied as arguments is "accessible by threads > other than the current thread", it needs to be conservative and not > touch any of it. I don't think this applies here for two reasons though: 1) a SIGSEGV would always be acceptable (that's not a valid object), and so would an infinite loop 2) I think that the as-if rule would even allow reads to objects accessible by other threads, if they don't affect the result (so they are not observable by the calling thread) *and* are not observable by those other threads either. The classic case here is strlen() doing aligned word (or larger) reads, even though those reads might trespass the NUL terminator. Promising any kind of behavior when a data race happens involving the str*/mem* functions is harder than it seems. As soon as the functions read a byte more than once, the view of memory that they operate on does not even obey causality. The following code is admittedly a bit contrived but shows the pitfalls of reading more than once from the same location: while (*(u32*)s == *(u32*)d) { n-=4, s+=4, d+=4; if (n < 4) goto short; } // we know the loop will stop don't we? while (*s==*d) s++, d++; return *s < *d ? -1 : 1; short: while (n && *s == *d) s++, d++, n--; return n ? (*s < *d ? -1 : 1) : 0; ... and you could access beyond the [a,a+n) [b,b+n) range if a concurrent mutator causes the second while loop to go off the cliff. There are also compiler issues: it's also hard to ensure that the compiler won't decide to read twice for very down-to-Earth instruction selection reasons, for example by using a register-and-memory ALU operation. Many mem*/str* routines do not have a single memory write, so the compiler has a *lot* of leeway to reorder and rematerialize memory accesses. For example you could have something like this in a memmem(): c = *p; ... p += table[c]; If the compiler changes the second statement to "p += table1[*p]", for example to avoid a spill, concurrent mutation can result in out-of-bounds accesses or other kinds of UB. The standard certainly didn't require that str*/mem* be written in assembly, or that it does all of it's accesses as atomic loads or perhaps (argh!) volatile. Paolo ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-14 17:36 ` Paolo Bonzini @ 2022-12-29 7:09 ` Zack Weinberg 0 siblings, 0 replies; 22+ messages in thread From: Zack Weinberg @ 2022-12-29 7:09 UTC (permalink / raw) To: Paolo Bonzini; +Cc: Carlos O'Donell, GNU libc development On Wed, 14 Dec 2022 12:36:44 -0500, Paolo Bonzini wrote: > On 12/14/22 15:16, Zack Weinberg via Libc-alpha wrote: > > 7.1.4p5 (N1570) "A library > > function shall not directly or indirectly access objects accessible > > by threads other than the current thread unless the objects are > > accessed directly or indirectly via the function's arguments." > > I don't think this applies here for two reasons though: > > 1) a SIGSEGV would always be acceptable (that's not a valid object), > and so would an infinite loop An infinite loop would indeed be acceptable, but I don’t see any justification for a SIGSEGV as long as the _page tables_ are not being changed concurrently from another thread. To put it another way, given a call `memcmp(a, b, n)`, as long as the address ranges `[a, a+n)` and `[b, b+n)` remain _readable_ for the duration of the call, no, SIGSEGV is not an acceptable outcome in my book, no matter how unstable the contents of those address ranges are. > 2) I think that the as-if rule would even allow reads to objects > accessible by other threads, if they don't affect the result (so they > are not observable by the calling thread) *and* are not observable by > those other threads either. The classic case here is strlen() doing > aligned word (or larger) reads, even though those reads might trespass > the NUL terminator. I’m not entirely comfortable with that logic, because those reads are forbidden by the _abstract_ machine’s memory model, in which reading even a single byte beyond the bounds of an explicitly declared array or malloc() block is UB. Very few concrete machines can enforce that rule precisely; the only ones I can think of are the valgrind VM and _maybe_ CHERI. But that hasn’t so far stopped the compiler people from implementing optimizations that assume the concrete machine _does_ enforce that rule precisely. > The following code is admittedly a bit contrived but shows the > pitfalls of reading more than once from the same location: > > while (*(u32*)s == *(u32*)d) { > n-=4, s+=4, d+=4; > if (n < 4) goto short; > } > > // we know the loop will stop don't we? > while (*s==*d) s++, d++; > return *s < *d ? -1 : 1; > > short: > while (n && *s == *d) s++, d++, n--; > return n ? (*s < *d ? -1 : 1) : 0; In my book, this falls clearly into “don’t do that then” territory. It is our responsibility as library implementors to code memcmp so that it _does not_ access beyond the [a,a+n) [b,b+n) range, _even if_ there is a concurrent mutator. > There are also compiler issues: it's also hard to ensure that the > compiler won't decide to read twice for very down-to-Earth instruction > selection reasons, for example by using a register-and-memory ALU > operation. Many mem*/str* routines do not have a single memory write, > so the compiler has a *lot* of leeway to reorder and rematerialize > memory accesses. Again, “don’t do that then”―not “don’t read twice,” but “don’t elide bounds checks, specifically, based on the assumption that two reads from the same location will return the same value.” > For example you could have something like this in a > memmem(): > > c = *p; > ... > p += table[c]; > > If the compiler changes the second statement to "p += table1[*p]", for > example to avoid a spill, that should be _perfectly fine_, because the next line of code is something like if (p > limit) break; and not c = *p; If the compiler deletes the bounds check, I’m prepared to argue both that that’s an incorrect optimization, and that if the standard says it’s fine then the _standard_ is wrong. zw ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 19:08 ` Noah Goldstein 2022-12-13 19:13 ` Narayanan Iyer @ 2022-12-13 21:20 ` Florian Weimer 2022-12-13 22:59 ` Noah Goldstein 1 sibling, 1 reply; 22+ messages in thread From: Florian Weimer @ 2022-12-13 21:20 UTC (permalink / raw) To: Noah Goldstein via Libc-alpha; +Cc: Narayanan Iyer, Noah Goldstein * Noah Goldstein via Libc-alpha: > Is this something we have to support? I believe other functions / > implementations of memcmp will suffer from a similar bug. Of course the crash is by no means deterministic, so I'm not sure how useful it is to detect application bugs. Maybe papering over the application bug is the right approach here. On the other hand, I really don't see how such a racing memcmp call could deliver any useful information whatsoever. The result will always be arbitrary in practice. So I hope such application bugs are really rare. > The fix: > https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse2.S;h=afd450d0206d6633da9fbc4607a7fa6aeb4e137c;hb=HEAD#l46 > ``` > -# define SIZE_OFFSET (CHAR_PER_VEC * 2) > +# define SIZE_OFFSET 0 > ``` How costly is this change? I would have thought about ANDing the offset so that it is always in range (but maybe it will stil result in a page crossing, I don't really know how this works). Thanks, Florian ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 21:20 ` Florian Weimer @ 2022-12-13 22:59 ` Noah Goldstein 2022-12-14 12:06 ` Florian Weimer 0 siblings, 1 reply; 22+ messages in thread From: Noah Goldstein @ 2022-12-13 22:59 UTC (permalink / raw) To: Florian Weimer; +Cc: Noah Goldstein via Libc-alpha, Narayanan Iyer On Tue, Dec 13, 2022 at 1:20 PM Florian Weimer <fweimer@redhat.com> wrote: > > * Noah Goldstein via Libc-alpha: > > > Is this something we have to support? I believe other functions / > > implementations of memcmp will suffer from a similar bug. > > Of course the crash is by no means deterministic, so I'm not sure how > useful it is to detect application bugs. Maybe papering over the > application bug is the right approach here. > > On the other hand, I really don't see how such a racing memcmp call > could deliver any useful information whatsoever. The result will always > be arbitrary in practice. So I hope such application bugs are really > rare. The usecase in the bugzilla is optimistic reads in concurrent databases. > > > The fix: > > https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse2.S;h=afd450d0206d6633da9fbc4607a7fa6aeb4e137c;hb=HEAD#l46 > > ``` > > -# define SIZE_OFFSET (CHAR_PER_VEC * 2) > > +# define SIZE_OFFSET 0 > > ``` > > How costly is this change? I would have thought about ANDing the offset > so that it is always in range (but maybe it will stil result in a page > crossing, I don't really know how this works). Its a bit expensive b.c it misaligned a lot of hot paths. A better fix (untested) is probably: ``` @@ -308,7 +308,7 @@ L(ret_nonzero_vec_end_0): setg %dl leal -1(%rdx, %rdx), %eax # else - addl %edx, %eax + addq %rdx, %rax movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rsi, %rax), %ecx movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rdi, %rax), %eax subl %ecx, %eax ``` The issue is the 32-bit negative number becomes a very large unsigned 64-bit number. If we just use 64-bit addition the issue goes away (I think at least). I'm okay with this change going in (assuming it works). This fix can be a "happy accident" that this unsupported usage no longer causes a sig-11, but I think it's a mistake to explicitly support this use case as anything other than UB. > > Thanks, > Florian > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change 2022-12-13 22:59 ` Noah Goldstein @ 2022-12-14 12:06 ` Florian Weimer 0 siblings, 0 replies; 22+ messages in thread From: Florian Weimer @ 2022-12-14 12:06 UTC (permalink / raw) To: Noah Goldstein; +Cc: Noah Goldstein via Libc-alpha, Narayanan Iyer * Noah Goldstein: > On Tue, Dec 13, 2022 at 1:20 PM Florian Weimer <fweimer@redhat.com> wrote: >> >> * Noah Goldstein via Libc-alpha: >> >> > Is this something we have to support? I believe other functions / >> > implementations of memcmp will suffer from a similar bug. >> >> Of course the crash is by no means deterministic, so I'm not sure how >> useful it is to detect application bugs. Maybe papering over the >> application bug is the right approach here. >> >> On the other hand, I really don't see how such a racing memcmp call >> could deliver any useful information whatsoever. The result will always >> be arbitrary in practice. So I hope such application bugs are really >> rare. > > The usecase in the bugzilla is optimistic reads in concurrent > databases. So what happens is that whatever the result is, it is still validated with some separate mechanism (e.g., a seqlock or some other form of TM)? That does not seem unreasonable at all, so I'd be in favor of supporting this, given that the cost is so low. Thanks, Florian ^ permalink raw reply [flat|nested] 22+ messages in thread
end of thread, other threads:[~2023-03-20 15:41 UTC | newest] Thread overview: 22+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <PAWPR08MB89825887E12FF900540365F483E09@PAWPR08MB8982.eurprd08.prod.outlook.com> [not found] ` <PAWPR08MB898260DA844D695EA70ED3E483E09@PAWPR08MB8982.eurprd08.prod.outlook.com> 2022-12-14 21:56 ` Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change Wilco Dijkstra 2022-12-29 7:21 ` Zack Weinberg 2022-12-29 20:02 ` Alejandro Colomar 2022-12-30 18:02 ` Joseph Myers 2023-03-20 15:40 ` Zack Weinberg 2022-12-13 18:20 Narayanan Iyer 2022-12-13 18:31 ` Andrew Pinski 2022-12-13 18:39 ` Narayanan Iyer 2022-12-13 18:39 ` Cristian Rodríguez 2022-12-13 19:08 ` Noah Goldstein 2022-12-13 19:13 ` Narayanan Iyer 2022-12-13 19:25 ` Noah Goldstein 2022-12-13 20:56 ` Zack Weinberg 2022-12-13 23:29 ` Carlos O'Donell 2022-12-14 2:28 ` Zack Weinberg 2022-12-14 4:16 ` Carlos O'Donell 2022-12-14 14:16 ` Zack Weinberg 2022-12-14 17:36 ` Paolo Bonzini 2022-12-29 7:09 ` Zack Weinberg 2022-12-13 21:20 ` Florian Weimer 2022-12-13 22:59 ` Noah Goldstein 2022-12-14 12:06 ` Florian Weimer
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).