47 ms·

Linux's strcmp() for the m68k has always been broken

99 points by marcodiego 4y ago

davikr 4y ago
I can't see much of a reason to even support such an old processor at this point.
- fulafel 4y ago
  680x0 are a newer ISA than x86 in a way, though it was 32 bit from the start so didn't need revising when 32 bit hw appeared.
- eschneider 4y ago
  Embedded systems
  - notwokeno 4y ago
    Is anyone making any new m68k chips these days? I looked for a hobby project earlier this year and it looked like Freescale was doing their best to sunset it.
    - eschneider 4y ago
      Not sure, but there are a lot of them in the field and, well, maintenance is a thing.
    - 0xcde4c3db 4y ago
      I went through a similar process a few years back. As far as I know, there is some extended availability through Rochester Electronics, but I don't know if anyone's still actually fabbing them or if they're dicing/packaging out of a stockpile of NOS wafers or what. I'm not aware of anyone still having a 68K/ColdFire chip that is "recommended for new designs". I also read somewhere that the 2011 earthquake+tsunami destroyed the only fab that had still been producing the original (well, CMOS) 68K-family chips, and Freescale had been planning to close that fab anyway.
    - zozbot234 4y ago
      The Vampire accelerator by Apollo Computers (which is FPGA-based AIUI) is not officially an m68k chip, but it's been developed as a drop-in replacement.
- johnklos 4y ago
  That's because you lack imagination, you lack knowledge about how we've gotten to where we are, and you lack understanding about the value of keeping software portable. There are many, many reasons for maintaining support for alternate architectures. How many problems would be baked in if we always had this attitude? Back in the day when "all the world is an i386", people complained when told about how their code has bugs when compiled on 64 bit processors. Imagine if we had baked in all of those 32-bit-centric bugs that broke compiling on 64 bit. People do the same thing now when told their code doesn't compile cleanly on 32 bit, on PowerPC, on ARM, on big endian, et cetera. Imagine if we now acted like "all the world is an amd64", and lots of code was simply broken on aarch64? If you were alive and paid attention through other transitions, you'd understand how every example of programmers being "forced" to care about the correctness and portability of their code has paid dividends years later.
  - Dylan16807 4y ago
    You're arguing a very different point. Linux supports a whole lot of architectures that are in active use, and nobody is suggesting changing that.
    - ryao 4y ago
      Evidently, m68k is still in use, otherwise the recent change would not have been noticed.
      - jabl 4y ago
        Indeed. The kernel isn't a museum, code or architectures that aren't used can and will get dropped. But the converse is also true, if somebody steps up to regularly test and fix issues in some code it can stay. Even if said somebody happens to be a bunch of retrocomputing enthusiasts and not a zillion dollar corporation.
      - Dylan16807 4y ago
        How many users do you think there are? I put "active" in there to contrast from a small/legacy amount. Though I wasn't making a definitive statement on which category m68k belongs to in the first place.
- brohee 4y ago
  You can still buy a Coldfire (now from NXP, after Motorola and Freescale) and I suspect it would have used that strcmp() implementation. The 68k family is not completely dead.
  - bierjunge 4y ago
    IIRC Texas Instruments uses 68k CPU's for their calculators. I'm pretty sure my TI Voyage 200 I've bought in highschool (15+ years ago) uses one and it's still great.
    - loeg 4y ago
      The older 9x and 89s do, yeah. The new ones just run ARM and emulate the older chips.
  - fredoralive 4y ago
    However NXP have Coldfire on a "Legacy MPU/MCUs" page, which doesn't exactly show them pushing for new design wins though. It's not dead, but it doesn't really have a future...
- spacedcowboy 4y ago
  Meanwhile I'm writing a compiler for the 6502....
- thomasjb 4y ago
  It is available [1] as a core for FPGAs (possibly used in some obscure ASICs to boot), and it is very possible that those applications need fairly current support. The ColdFire processors came in up to 300MHz, and modern FPGAs could probably enable even higher speeds. There are variants with Ethernet [2], so security is probably a real concern. I would very much like to learn how to get one 1) running on an FPGA 2) running Linux and then 3) set it up to automatically run new builds. [1] https://silvaco.com/design-ip/embedded-processors/ https://silvaco.com/design-ip/embedded-processors/ [2] https://www.farnell.com/datasheets/1703092.pdf https://www.farnell.com/datasheets/1703092.pdf
  - duskwuff 4y ago
    ColdFire isn't precisely 680x0. It has a similar instruction set, but it isn't identical, and (crucially) it doesn't have an external memory/peripheral bus. As far as I'm aware, there are no longer any "true" 680x0 parts in production. NXP stopped production of the 68SEC000 in 2014; anything still in stock is at least that old.
deleted 4y ago
[deleted]
cornstalks 4y ago
Tangent: it drives me nuts how HN editorializes headlines and adds capitals to function names (it’s “strcmp” not “Strcmp”).
- tiahura 4y ago
  It’s in the title so it gets capitalized.
  - smcl 4y ago
    It also un-capitalised "for the" but left "has" capitalised :-/
    - mananaysiempre 4y ago
      This follows the standard practice[1]: in titles, capitalize everything except articles, prepositions, particles, and conjunctions, as well as the first and the last word even if it’s one of those. Sometimes long prepositions etc. may also be capitalized. A linking “has” looks like one of those words that shouldn’t be capitalized, but it’s a verb so (as far as the rules go) it should. (There also publications that capitalize everything indiscriminately, I think.) [1] E.g. https://apastyle.apa.org/style-grammar-guidelines/capitalization/title-case https://apastyle.apa.org/style-grammar-guidelines/capitaliza...
- dpifke 4y ago
  The submitter can go back and correct this by clicking "edit". The software changes capitalization only on the initial submission, not subsequent edits. (Overall, I actually like this feature. You WOULDN'T BELIEVE the CRAZY Headlines We'd See Otherwise!)
  - cornstalks 4y ago
    Even if they do that others usually change it back. Or at least that’s what I’ve observed on other threads.
  - 4y ago
ta988 4y ago
I'm surprised to learn there is no test suite that would test the overflow case. I also realize I have no idea about the extent of testing in the kernel.
- slongfield 4y ago
  The Linux kernel has not historically had great unit testing practices--it's mostly tested with large integration tests. This is in part because it inherits old development practices where unit testing was less popular, and partially because it's kind of hard to test a lot of Kernel code outside of specialized environments (e.g., would need to include a m68k emulator in the test environment to test this code). The doubly-linked `list` type that's used ~everywhere in the kernel didn't have any in-repo unit tests until 2019 ( https://github.com/torvalds/linux/commit/ea2dd7c0875ed31955cda7b1b20612c8337192e5 https://github.com/torvalds/linux/commit/ea2dd7c0875ed31955c... ), after kunit, a library for userspace testing of kernel code, was added.
Gordonjcp 4y ago
I'm prepared to bet that both the people that ran into this bug went "huh, that's weird, you'd swear that was a bug in strcmp(). Oh well. Tell you what I'll do instead..." Then they promptly forgot all about it.
dboreham 4y ago
I dispute that it has "always" been broken -- the bug is to do with ordering non-ascii input data, when char is unsigned. I suspect strcmp() wasn't expected to provide order on non-ASCII data when that code was written, with char defined as u8. The original K&R code just subtracts the two (signed) chars too: https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/gen/strcmp.c https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/g...
- kentonv 4y ago
  Subtracting two chars produces an `int`. C generally promotes all smaller types to `int` before doing arithmetic, and `int` is required to be at least 16 bits. So I think the code you linked is correct?
- fanf2 4y ago
  That old C code relies on integer promotion to avoid the overflow problems that occurred in the m68k asm.
  - _kst_ 4y ago
    Exactly. C has no arithmetic operations on types narrower than int and unsigned int. This bug (which involves subtracting 8-bit values and yielding an 8-bit result) could only happen in assembly language (or in an exotic C implementation where CHAR_BIT > 8 and int is 1 byte, or in C code that uses casts to deliberately create the bug).
- loeg 4y ago
  > I dispute that it has "always" been broken -- the bug is to do with ordering non-ascii input data, when char is unsigned. No. As the article notes, there's also a bug when char is signed (the subtraction may overflow, which is UB for signed char, and additionally produces the wrong result even assuming defined overflow). It's just more obvious when char is unsigned.
  - pavon 4y ago
    Plain ASCII is 7-bit so it won't overflow with signed char. There are many extensions that use that extra bit to increase the number of characters, but they aren't ASCII, they are ISO 8859-*, or ANSI, or UTF-8 etc.
usefulcat 4y ago
This would have been so, sooooo easy to detect with a unit test. It boggles the mind that no one would bother to write a test for something both so fundamental AND so eminently testable.
- jeffrallen 4y ago
  Yes, it boggles the mind that you didn't. Because if you have enough time to criticize other open source maintainers, you certainly have time to write the unit tests they aren't writing, right?
- loeg 4y ago
  It's the m68k target -- to a first degree approximation, no one uses this.
- michael1999 4y ago
  That code is older than the culture of comprehensive automated testing. It's hard for modern minds to believe how little automated testing existed before the xunit revolution.
- icedchai 4y ago
  I'm skeptical. Odds are any such test would use short ASCII strings and probably not uncovered the problem. Also, the most common uses cases of strcmp are comparisons with 0. Any such unit test would probably do the same, further minimizing the odds of discovery.
  - mmcgaha 4y ago
    I agree, this is the type of bug where the test would not have been written until after the bug was found. When the bug gets found, the test will be written, the code will be updated and no one will touch it unless another bug gets found; rinse and repeat. Just like it is hard to proof read your own papers, it is hard to write complete tests for your own code.
  - layer8 4y ago
    Writing a good unit tests always means looking at the possible value ranges and specifically the edge cases within those ranges, and adding tests for those. That’s the standard course of action when writing unit tests for some API. Unit tests aren’t supposed to just mimic typical usage.
Negitivefrags 4y ago
If you think that is bad, then you might think that it’s even worse that memcpy() was broken for years when running a 32 bit process on a 64 bit linux system. Also due to a hand optimised assembly function. We had an issue for years where occasionally our backend database would fall over and we were just seeing strange corruption in the stored data sometimes. Turns out that memcpy() didn’t handle data that was not aligned to a 4 byte boundary correctly in the 32 on 64 case. It took one of our sysadmins a very very long time to find it. What blew me away is the idea that there can be a bug in something that is used literally everywhere all the time. In addition, there was a pull request with a fix that someone had written that got ignored for years that we found. We just applied the diff in the pull request and it fixed our issues. The fix was eventually applied upstream a few years later.
- guerrilla 4y ago
  > Turns out that memcpy() didn’t handle data that was not aligned to a 4 byte boundary correctly in the 32 on 64 case. It took one of our sysadmins a very very long time to find it. That sounds like an interesting detective story. Did they write it up anywhere?
  - Negitivefrags 4y ago
    They didn’t, but it was one hell of a pain in the ass. We only ever saw it on the production databases and the crash, which was the main thing we were debugging, would only happen every week or so. Core dumps didn’t show anything useful because the crashes were just that a pointer was mysteriously pointing into a bad place. But how did it get corrupted? We were doing increasingly insane things to reproduce the problem locally. An interesting idea I had to reproduce it was using a database replica, which did crash sometimes. We used TCPDump to capture the replication stream, then waited a week for the replica to crash. We could start up a copy of the replica in the state it was at the beginning and replay the week of replication data into the socket to reproduce the problem. My theory was that since a DB replica doesn’t do anything other than the sequence of operations that come to it via the replication stream, that this should deterministicly reproduce the problem. Turns out that it didn’t. Anyway, if my memory is correct, the issue was that memcpy was copying an extra 1-3 bytes at the end of the range, if the start of the range was unaligned. If there happened to be a pointer there then that would lead to a crash down the line. My memory could be off though.
pavon 4y ago
Note this bug is for the strcmp implementation used in Linux kernel code itself. The userland implementations of strcmp in glibc, etc, are separate so this didn't affect uses of strcmp in application code.
ryao 4y ago
It is very difficult to review assembly code for bugs. Static analysis tools also cannot see bugs involving assembly code in general. :/
deleted 4y ago
[deleted]

99 points by marcodiego 4y ago

davikr 4y ago

I can't see much of a reason to even support such an old processor at this point.

fulafel 4y ago
680x0 are a newer ISA than x86 in a way, though it was 32 bit from the start so didn't need revising when 32 bit hw appeared.
eschneider 4y ago
Embedded systems
- notwokeno 4y ago
  Is anyone making any new m68k chips these days? I looked for a hobby project earlier this year and it looked like Freescale was doing their best to sunset it.
  - eschneider 4y ago
    Not sure, but there are a lot of them in the field and, well, maintenance is a thing.
  - 0xcde4c3db 4y ago
    I went through a similar process a few years back. As far as I know, there is some extended availability through Rochester Electronics, but I don't know if anyone's still actually fabbing them or if they're dicing/packaging out of a stockpile of NOS wafers or what. I'm not aware of anyone still having a 68K/ColdFire chip that is "recommended for new designs". I also read somewhere that the 2011 earthquake+tsunami destroyed the only fab that had still been producing the original (well, CMOS) 68K-family chips, and Freescale had been planning to close that fab anyway.
  - zozbot234 4y ago
    The Vampire accelerator by Apollo Computers (which is FPGA-based AIUI) is not officially an m68k chip, but it's been developed as a drop-in replacement.
johnklos 4y ago
That's because you lack imagination, you lack knowledge about how we've gotten to where we are, and you lack understanding about the value of keeping software portable. There are many, many reasons for maintaining support for alternate architectures. How many problems would be baked in if we always had this attitude? Back in the day when "all the world is an i386", people complained when told about how their code has bugs when compiled on 64 bit processors. Imagine if we had baked in all of those 32-bit-centric bugs that broke compiling on 64 bit. People do the same thing now when told their code doesn't compile cleanly on 32 bit, on PowerPC, on ARM, on big endian, et cetera. Imagine if we now acted like "all the world is an amd64", and lots of code was simply broken on aarch64? If you were alive and paid attention through other transitions, you'd understand how every example of programmers being "forced" to care about the correctness and portability of their code has paid dividends years later.
- Dylan16807 4y ago
  You're arguing a very different point. Linux supports a whole lot of architectures that are in active use, and nobody is suggesting changing that.
  - ryao 4y ago
    Evidently, m68k is still in use, otherwise the recent change would not have been noticed.
    - jabl 4y ago
      Indeed. The kernel isn't a museum, code or architectures that aren't used can and will get dropped. But the converse is also true, if somebody steps up to regularly test and fix issues in some code it can stay. Even if said somebody happens to be a bunch of retrocomputing enthusiasts and not a zillion dollar corporation.
    - Dylan16807 4y ago
      How many users do you think there are? I put "active" in there to contrast from a small/legacy amount. Though I wasn't making a definitive statement on which category m68k belongs to in the first place.
brohee 4y ago
You can still buy a Coldfire (now from NXP, after Motorola and Freescale) and I suspect it would have used that strcmp() implementation. The 68k family is not completely dead.
- bierjunge 4y ago
  IIRC Texas Instruments uses 68k CPU's for their calculators. I'm pretty sure my TI Voyage 200 I've bought in highschool (15+ years ago) uses one and it's still great.
  - loeg 4y ago
    The older 9x and 89s do, yeah. The new ones just run ARM and emulate the older chips.
- fredoralive 4y ago
  However NXP have Coldfire on a "Legacy MPU/MCUs" page, which doesn't exactly show them pushing for new design wins though. It's not dead, but it doesn't really have a future...
spacedcowboy 4y ago
Meanwhile I'm writing a compiler for the 6502....
thomasjb 4y ago
It is available [1] as a core for FPGAs (possibly used in some obscure ASICs to boot), and it is very possible that those applications need fairly current support. The ColdFire processors came in up to 300MHz, and modern FPGAs could probably enable even higher speeds. There are variants with Ethernet [2], so security is probably a real concern. I would very much like to learn how to get one 1) running on an FPGA 2) running Linux and then 3) set it up to automatically run new builds. [1] https://silvaco.com/design-ip/embedded-processors/ https://silvaco.com/design-ip/embedded-processors/ [2] https://www.farnell.com/datasheets/1703092.pdf https://www.farnell.com/datasheets/1703092.pdf
- duskwuff 4y ago
  ColdFire isn't precisely 680x0. It has a similar instruction set, but it isn't identical, and (crucially) it doesn't have an external memory/peripheral bus. As far as I'm aware, there are no longer any "true" 680x0 parts in production. NXP stopped production of the 68SEC000 in 2014; anything still in stock is at least that old.

deleted 4y ago

[deleted]

cornstalks 4y ago

Tangent: it drives me nuts how HN editorializes headlines and adds capitals to function names (it’s “strcmp” not “Strcmp”).

tiahura 4y ago
It’s in the title so it gets capitalized.
- smcl 4y ago
  It also un-capitalised "for the" but left "has" capitalised :-/
  - mananaysiempre 4y ago
    This follows the standard practice[1]: in titles, capitalize everything except articles, prepositions, particles, and conjunctions, as well as the first and the last word even if it’s one of those. Sometimes long prepositions etc. may also be capitalized. A linking “has” looks like one of those words that shouldn’t be capitalized, but it’s a verb so (as far as the rules go) it should. (There also publications that capitalize everything indiscriminately, I think.) [1] E.g. https://apastyle.apa.org/style-grammar-guidelines/capitalization/title-case https://apastyle.apa.org/style-grammar-guidelines/capitaliza...
dpifke 4y ago
The submitter can go back and correct this by clicking "edit". The software changes capitalization only on the initial submission, not subsequent edits. (Overall, I actually like this feature. You WOULDN'T BELIEVE the CRAZY Headlines We'd See Otherwise!)
- cornstalks 4y ago
  Even if they do that others usually change it back. Or at least that’s what I’ve observed on other threads.
- 4y ago

ta988 4y ago

I'm surprised to learn there is no test suite that would test the overflow case. I also realize I have no idea about the extent of testing in the kernel.

slongfield 4y ago
The Linux kernel has not historically had great unit testing practices--it's mostly tested with large integration tests. This is in part because it inherits old development practices where unit testing was less popular, and partially because it's kind of hard to test a lot of Kernel code outside of specialized environments (e.g., would need to include a m68k emulator in the test environment to test this code). The doubly-linked `list` type that's used ~everywhere in the kernel didn't have any in-repo unit tests until 2019 ( https://github.com/torvalds/linux/commit/ea2dd7c0875ed31955cda7b1b20612c8337192e5 https://github.com/torvalds/linux/commit/ea2dd7c0875ed31955c... ), after kunit, a library for userspace testing of kernel code, was added.

Gordonjcp 4y ago

I'm prepared to bet that both the people that ran into this bug went "huh, that's weird, you'd swear that was a bug in strcmp(). Oh well. Tell you what I'll do instead..." Then they promptly forgot all about it.

dboreham 4y ago

I dispute that it has "always" been broken -- the bug is to do with ordering non-ascii input data, when char is unsigned. I suspect strcmp() wasn't expected to provide order on non-ASCII data when that code was written, with char defined as u8. The original K&R code just subtracts the two (signed) chars too: https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/gen/strcmp.c https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/g...

kentonv 4y ago
Subtracting two chars produces an `int`. C generally promotes all smaller types to `int` before doing arithmetic, and `int` is required to be at least 16 bits. So I think the code you linked is correct?
fanf2 4y ago
That old C code relies on integer promotion to avoid the overflow problems that occurred in the m68k asm.
- _kst_ 4y ago
  Exactly. C has no arithmetic operations on types narrower than int and unsigned int. This bug (which involves subtracting 8-bit values and yielding an 8-bit result) could only happen in assembly language (or in an exotic C implementation where CHAR_BIT > 8 and int is 1 byte, or in C code that uses casts to deliberately create the bug).
loeg 4y ago
> I dispute that it has "always" been broken -- the bug is to do with ordering non-ascii input data, when char is unsigned. No. As the article notes, there's also a bug when char is signed (the subtraction may overflow, which is UB for signed char, and additionally produces the wrong result even assuming defined overflow). It's just more obvious when char is unsigned.
- pavon 4y ago
  Plain ASCII is 7-bit so it won't overflow with signed char. There are many extensions that use that extra bit to increase the number of characters, but they aren't ASCII, they are ISO 8859-*, or ANSI, or UTF-8 etc.

usefulcat 4y ago

This would have been so, sooooo easy to detect with a unit test. It boggles the mind that no one would bother to write a test for something both so fundamental AND so eminently testable.

jeffrallen 4y ago
Yes, it boggles the mind that you didn't. Because if you have enough time to criticize other open source maintainers, you certainly have time to write the unit tests they aren't writing, right?
loeg 4y ago
It's the m68k target -- to a first degree approximation, no one uses this.
michael1999 4y ago
That code is older than the culture of comprehensive automated testing. It's hard for modern minds to believe how little automated testing existed before the xunit revolution.
icedchai 4y ago
I'm skeptical. Odds are any such test would use short ASCII strings and probably not uncovered the problem. Also, the most common uses cases of strcmp are comparisons with 0. Any such unit test would probably do the same, further minimizing the odds of discovery.
- mmcgaha 4y ago
  I agree, this is the type of bug where the test would not have been written until after the bug was found. When the bug gets found, the test will be written, the code will be updated and no one will touch it unless another bug gets found; rinse and repeat. Just like it is hard to proof read your own papers, it is hard to write complete tests for your own code.
- layer8 4y ago
  Writing a good unit tests always means looking at the possible value ranges and specifically the edge cases within those ranges, and adding tests for those. That’s the standard course of action when writing unit tests for some API. Unit tests aren’t supposed to just mimic typical usage.

Negitivefrags 4y ago

If you think that is bad, then you might think that it’s even worse that memcpy() was broken for years when running a 32 bit process on a 64 bit linux system. Also due to a hand optimised assembly function. We had an issue for years where occasionally our backend database would fall over and we were just seeing strange corruption in the stored data sometimes. Turns out that memcpy() didn’t handle data that was not aligned to a 4 byte boundary correctly in the 32 on 64 case. It took one of our sysadmins a very very long time to find it. What blew me away is the idea that there can be a bug in something that is used literally everywhere all the time. In addition, there was a pull request with a fix that someone had written that got ignored for years that we found. We just applied the diff in the pull request and it fixed our issues. The fix was eventually applied upstream a few years later.

guerrilla 4y ago
> Turns out that memcpy() didn’t handle data that was not aligned to a 4 byte boundary correctly in the 32 on 64 case. It took one of our sysadmins a very very long time to find it. That sounds like an interesting detective story. Did they write it up anywhere?
- Negitivefrags 4y ago
  They didn’t, but it was one hell of a pain in the ass. We only ever saw it on the production databases and the crash, which was the main thing we were debugging, would only happen every week or so. Core dumps didn’t show anything useful because the crashes were just that a pointer was mysteriously pointing into a bad place. But how did it get corrupted? We were doing increasingly insane things to reproduce the problem locally. An interesting idea I had to reproduce it was using a database replica, which did crash sometimes. We used TCPDump to capture the replication stream, then waited a week for the replica to crash. We could start up a copy of the replica in the state it was at the beginning and replay the week of replication data into the socket to reproduce the problem. My theory was that since a DB replica doesn’t do anything other than the sequence of operations that come to it via the replication stream, that this should deterministicly reproduce the problem. Turns out that it didn’t. Anyway, if my memory is correct, the issue was that memcpy was copying an extra 1-3 bytes at the end of the range, if the start of the range was unaligned. If there happened to be a pointer there then that would lead to a crash down the line. My memory could be off though.

pavon 4y ago

Note this bug is for the strcmp implementation used in Linux kernel code itself. The userland implementations of strcmp in glibc, etc, are separate so this didn't affect uses of strcmp in application code.

ryao 4y ago

It is very difficult to review assembly code for bugs. Static analysis tools also cannot see bugs involving assembly code in general. :/

deleted 4y ago

[deleted]