[HN Gopher] Linux's strcmp() for the m68k has always been broken
___________________________________________________________________
Linux's strcmp() for the m68k has always been broken
Author : marcodiego
Score : 90 points
Date : 2022-12-21 19:26 UTC (1 days ago)
(HTM) web link (www.phoronix.com)
(TXT) w3m dump (www.phoronix.com)
| dboreham wrote:
| 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/g...
| kentonv wrote:
| 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 wrote:
| That old C code relies on integer promotion to avoid the
| overflow problems that occurred in the m68k asm.
| _kst_ wrote:
| 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 wrote:
| > 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.
| jabl wrote:
| > UB for signed char
|
| Signed overflow is undefined in C, but this was implemented
| in ASM. I'm not familiar with the m68k isa, but I'd be very
| surprised if it doesn't define signed values to wraparound as
| is natural for a two's complement implementation.
| pavon wrote:
| 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.
| loeg wrote:
| As the article notes, Linux does not validate strings for
| 7-bit cleanness, so the routine needs to work on strings
| that use the high bit.
| layer8 wrote:
| The problem is not just that it results in a wrong order
| for 8-bit encodings, but that it doesn't result in a well-
| defined order at all. For example, you get:
| -2 > 127 > 64 > -2
|
| This can make sorting algorithms loop infinitely or crash.
| [deleted]
| ta988 wrote:
| 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 wrote:
| 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/ea2dd7c0875ed31955c...
| ), after kunit, a library for userspace testing of kernel code,
| was added.
| cornstalks wrote:
| Tangent: it drives me nuts how HN editorializes headlines and
| adds capitals to function names (it's "strcmp" not "Strcmp").
| tiahura wrote:
| It's in the title so it gets capitalized.
| smcl wrote:
| It also un-capitalised "for the" but left "has" capitalised
| :-/
| mananaysiempre wrote:
| 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/capitaliza...
| dpifke wrote:
| 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 wrote:
| Even if they do that others usually change it back. Or at
| least that's what I've observed on other threads.
| hackmiester wrote:
| Thanks for the tip!
| Dylan16807 wrote:
| Do you have an example that involves _adding_ capitals?
|
| Also I can't even remember the last time I saw a real article
| with all caps words in the title (on the original page), let
| alone one linked on HN.
| dpifke wrote:
| "Otherwise" was the operative word in my (slightly
| sarcastic) example. :)
|
| Avoiding all caps for emphasis means you sometimes have to
| change "Faa" back to "FAA" after submitting a story about
| the Federal Aviation Administration. And avoiding
| grammatically-incorrect or all-lowercase headlines means
| you sometimes have to change "Strcmp()" back to "strcmp()".
|
| HN's software is no longer open source, but at one time,
| this is how it processed titles on initial submission: http
| s://github.com/wting/hackernews/blob/master/news.arc#L15...
| (This function does _add_ capitals as well as remove them.)
| Dylan16807 wrote:
| > "Otherwise" was the operative word in my (slightly
| sarcastic) example. :)
|
| I know. I don't think you understood what I meant.
|
| I'm saying "What otherwise? If you removed that code, I
| still don't think those headlines would show up."
|
| But removing caps is easier to justify, so I'm also
| asking why, even if we decide we need caps-removing code,
| we would _also_ need the code to add caps.
| dpifke wrote:
| > I'm saying "What otherwise? If you removed that code, I
| still don't think those headlines would show up."
|
| You have more faith in the average HN submitter than I
| do. :)
| Dylan16807 wrote:
| Are we assuming these submitters are changing the
| headlines? Because I was focusing on articles that _have_
| headlines with all-caps words in them on the original
| site, and I can 't think of any I've seen on HN.
| usefulcat wrote:
| 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.
| icedchai wrote:
| 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 wrote:
| 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 wrote:
| 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.
| icedchai wrote:
| Right. They're not _supposed_ to test only the typical,
| minimal usage, but they often do. In very old C code, you
| 'll be lucky if it has any tests at all.
| loeg wrote:
| It's the m68k target -- to a first degree approximation, no one
| uses this.
| jeffrallen wrote:
| 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?
| michael1999 wrote:
| 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.
| ryao wrote:
| It is very difficult to review assembly code for bugs. Static
| analysis tools also cannot see bugs involving assembly code in
| general. :/
| Gordonjcp wrote:
| 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.
| davikr wrote:
| I can't see much of a reason to even support such an old
| processor at this point.
| johnklos wrote:
| 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 wrote:
| 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 wrote:
| Evidently, m68k is still in use, otherwise the recent
| change would not have been noticed.
| jabl wrote:
| 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.
| loeg wrote:
| Linux would still be a portable kernel if it dropped m68k
| support. It still targets PPC, ARM, x86, Sparc, avr, ia64,
| s390, blah blah blah. Dropping m68k is a far cry from
| dropping everything except amd64.
| Karellen wrote:
| > Back in the day when "all the world is an i386",
|
| If anyone wants a further back in an even earlier day
| example, see
| http://www.catb.org/jargon/html/V/vaxocentrism.html
| spacedcowboy wrote:
| Meanwhile I'm writing a compiler for the 6502....
| brohee wrote:
| 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 wrote:
| 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 wrote:
| The older 9x and 89s do, yeah. The new ones just run ARM
| and emulate the older chips.
| fredoralive wrote:
| 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...
| eschneider wrote:
| Embedded systems
| notwokeno wrote:
| 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.
| zozbot234 wrote:
| 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.
| eschneider wrote:
| Not sure, but there are a lot of them in the field and,
| well, maintenance is a thing.
| 0xcde4c3db wrote:
| 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.
| fulafel wrote:
| 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.
| thomasjb wrote:
| 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/ [2]
| https://www.farnell.com/datasheets/1703092.pdf
| duskwuff wrote:
| 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.
| pavon wrote:
| 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.
| [deleted]
| Negitivefrags wrote:
| 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.
| butlerm wrote:
| > 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 is surprising outside of the kernel. There are a large
| number of programs that would fail very hard very fast with
| that sort of artificial restriction.
| actionfromafar wrote:
| And people got funny looks for wanting to run 32 bit workloads
| in their own 32 bit VMs...
| guerrilla wrote:
| > 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 wrote:
| 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.
| guerrilla wrote:
| > 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.
|
| Ahhh I could see how that could be! Fascinating. That's
| exactly the kind of heisenbug I used to love. I always
| liked the ones that seemed literally impossible but had a
| nice explanation.
| iquerno wrote:
| schrodinbug*
| ryao wrote:
| That is not the first `memcpy()` issue that I have heard. There
| was the reverse `memcpy()` in glibc 2.13 that broke plenty of
| software using `memcpy()` in places where `memmove()` should
| have been used.
| ketralnis wrote:
| > What blew me away is the idea that there can be a bug in
| something that is used literally everywhere all the time.
|
| We've become so accustomed to computers being generally
| unreliable that I guess people see something weird and just
| reboot. We checksum, run reductant servers, and just generally
| tolerate and work around way more failures and weirdness than
| we should.
|
| It's funny because we're theoretically an industry that could
| be full of maths and proofs but ask anybody outside of it and
| you'll get "yeah computers just don't work sometimes I guess
| that's how it is"
| ratorx wrote:
| The problem is that even a perfectly implemented computer
| will fail randomly, due to inherent unreliability in the
| underlying hardware (cosmic rays, bad silicon etc.).
|
| And once you start designing around that unreliability, it is
| harder to justify chasing esoteric bugs rather than folding
| that alongside the probability model of random hardware
| failure.
|
| It's hard for any system dealing with the real world to be
| completely "maths and proofs". There is plenty of it that's
| applied even in the real world systems we operate today. At
| the end of the day, it's Engineering and not a pure science.
|
| And I guess the other problem is that quite often you don't
| need to quantify the failure modes and do "proper
| engineering", because a lot of the systems we build and use
| just don't need the level of reliability that e.g. a bridge
| needs (yet). There are definitely industries where software
| reliability is considered paramount, but that's not the
| majority of the market.
| ketralnis wrote:
| > a lot of the systems we build and use just don't need the
| level of reliability that e.g. a bridge needs
|
| Sure. As the saying goes, "Anybody can build a bridge that
| never falls down. But it takes an engineer to build a
| bridge that _almost_ doesn't fall down" (referring to being
| able to build it in a cost-conscious way). There's a
| spectrum there for sure, but as an industry we're on the
| other side of it from where I personally wish we were.
|
| We should be embarrassed that "it must have been a computer
| glitch" can be used to explain away nearly any problem.
| Because it's usually right, and it's usually our fault
| rather than the cosmic rays.
| CJefferson wrote:
| Similar issue,
| https://sourceware.org/bugzilla/show_bug.cgi?id=22644 , which
| was found by a friend of mine and took is ages to track down.
|
| memmove was broken on 32-bit executables on systems with SSE2
| whenever the move occurred over the 2GB memory boundary due to
| an issue with signed vs unsigned integers.
___________________________________________________________________
(page generated 2022-12-22 23:02 UTC)