[HN Gopher] Deep Bug
___________________________________________________________________
Deep Bug
Author : marginalia_nu
Score : 194 points
Date : 2024-04-10 09:30 UTC (13 hours ago)
(HTM) web link (www.marginalia.nu)
(TXT) w3m dump (www.marginalia.nu)
| marginalia_nu wrote:
| Unrelated but related: Doing systems programming in Java actually
| makes me appreciate all the little things C does to ensure your
| program run correctly.
| virgilp wrote:
| Like, what? Honest question. I can think of a few things that
| Java does (bounds checking, for one), but very few things that
| C does.
|
| (also, not entirely sure what you meant. There isn't a
| canonical C compiler, or toolset, and the language itself
| really doesn't do anything to prevent you from shooting
| yourself in the foot)
| marginalia_nu wrote:
| Like having unsigned integers and pointers. Java makes you do
| pointer arithmetic with all signed integers that all have the
| same type as every other integer in the program.
| afandian wrote:
| What do you mean by pointer arithmetic in Java? Real
| pointers in FFI? Or array indexes?
| marginalia_nu wrote:
| Offsets in files and mapped memory. None of this is done
| through Java objects or arrays, but rather by reading
| data directly from memory or disk and manually keeping
| track the data's type and structure.
| deely3 wrote:
| And how exactly C is better in these situations?
| marginalia_nu wrote:
| It has pointer types and unsigned integer types.
| shrx wrote:
| If you're using pointers in Java you're doing something
| wrong
| marginalia_nu wrote:
| If you're going to do this sort of low level database-
| adjacent work in Java, this is basically how you need to
| do it. It's pretty unpleasant and the language resists
| you in every way, but luckily in most cases it's only a
| small core of the program that needs to be written this
| way.
|
| Well, that or JNI/FFI in some C code I guess.
| mike_hearn wrote:
| Does the new Panama memory API help? There are new pointer-
| like classes for indexing into memory mapped files.
|
| Also, Kotlin has unsigned integers. So you could use that
| for the parts of your code that benefit from it.
| marginalia_nu wrote:
| It helps in the sense that it's no longer necessary to
| slice up the file into individual 2 GB byte buffers,
| though I'm not really using MemoryLayout/StructLayout
| much yet to do structured access. Haven't made sense of
| how to use that part of the API well yet.
| vsnf wrote:
| Hearing that C has assists for program correctness is, shall I
| say, unexpected to say the least. What kinds of things are you
| referring to?
| eddd-ddde wrote:
| Probably the things C does _not_ do? No messy vtables, no
| exceptions, no vm, etc. If you just do less stuff it 's less
| likely you do something wrong.
| elteto wrote:
| You trade that off by a healthy dose of foot guns and UB.
| And a non-existent standard library that encourages NIH
| write-my-own for the most common data structures. C barely
| does anything and it has a stark beauty of its own, agreed.
| And yet it is incredibly hard to write secure code with it.
| ignoramous wrote:
| > What kinds of things are you _referring_ to?
|
| Pointer arithmetic, I imagine. Elementary math after all.
| elteto wrote:
| You found one compiler bug after moving to a new version of
| your compiler/runtime. Not unheard of, to be honest. Now think
| of all the common bugs you _didn't_ get in all these years
| because you wrote your code in Java instead of C.
| marginalia_nu wrote:
| I'm mostly referring to the fact that half the debugging was
| spent on a wild goose chase combing through integer types.
|
| With unsigned integers, type aliases and pointer types this
| would have been a lot easier to keep track of. The limited
| range of primitive integers also means static analysis is
| basically impossible. Assing a pointer to an integer or vice
| versa and that's a code smell. Assign an integer to an
| integer and the compiler is none the wiser.
| elteto wrote:
| I think you went on a wild goose chase _because_ it was a
| compiler bug. You never assume "it's the compiler" on the
| first try, so you go looking for bugs in your code that
| don't exist. Java's integer types maybe didn't help in this
| situation, agreed. And the lack of unsigned integers is
| harebrained, agreed too. But I think you wouldn't have had
| an easier time in C.
|
| You say that the lack of unsigned types in Java is in part
| responsible for some of your wasted time. But C has
| notoriously bad integer types and promotion rules,
| especially for interactions between signed and unsigned! If
| you had found this same bug in C code (a compiler bug),
| your first instinct as a C programmer might have been "it's
| probably some signed/unsigned interaction issue". And you'd
| also have wasted time trying to find a non-existent issue
| in your code.
| kragen wrote:
| entirely by coincidence, i have spent a substantial part
| of the night finding signed/unsigned bugs in my c code by
| carefully reading through the disassembly, so i endorse
| this message
| kamov wrote:
| Sorry, I don't want to be _that guy_ , but I'm curious why use
| Java and not something like Rust? Is it because of the Lucene
| ecosystem?
| marginalia_nu wrote:
| The short story is I'm productive in Java, and I enjoy its
| mature ecosystem and stable APIs. Systems programming is
| awkward, but it's also a very small part of the project and
| for what it is, an interesting challenge.
|
| What I'm building is what Lucene does (i.e. document
| indexing) and then the rest of the search engine as well
| including crawling and serving traffic.
| mrkeen wrote:
| I did this.
|
| I previously worked at a search engine which did its index
| building and querying in C, with its higher-level stuff (web-
| apps, scheduling, tooling, etc.) in Java.
|
| Later when I built my own version, I started with C for the
| low-level and Haskell for the high-level. I made a few
| iterations in C, but eventually rewrote it in Rust, and I was
| pretty happy with that choice.
|
| I was more familiar with C, and it was a really good fit for
| what I was writing. Terms and Documents just become termIds
| and docIds (numbers) sitting in indexes (arrays). Memory-
| mapping is a really comfortable way to do things: files are
| just arrays; let the OS sort out when to page things in and
| out of disk.
|
| But where C fell down for me was in the _changing the code_.
| The meaning of the data &code were lost in nested for-loops
| and void-function-pointers, etc. Rust gave me a better shot
| at both writing _and rewriting_ the code.
|
| Java for the low-level was a non-starter for me for a few
| reasons, but the biggest two were startup time and difficulty
| of the mmap api (31-bits of address-space for a file?
| c'mon!).
| marginalia_nu wrote:
| > Java for the low-level was a non-starter for me for a few
| reasons, but the biggest two were startup time and
| difficulty of the mmap api (31-bits of address-space for a
| file? c'mon!).
|
| Neither of these are issues anymore though. Especially not
| with graal's native images.
| bluelu wrote:
| I had a similar bug more than 10 years ago, also while building a
| search index through Lucene. It would crash after hours of
| running with an impossible nullpointer exception. It always
| appeared after running for hours, and running that specific
| iteration would not trigger the exception, so hard to reproduce.
|
| Turned out it was a java jvm bug which was triggered when the jvm
| decided to recompile that code part since it was used more
| frequently.
|
| Try running your code with the -server flag and see if that makes
| a difference.
| NobleExpress wrote:
| -server is only a thing for HotSpot. They mention that HotSpot
| works perfectly fine. There is no option of "-server" for Graal
| native-image. It has "-O{0,1}" though for turning optimizations
| off and on respectively.
| marginalia_nu wrote:
| It's not a native image, it runs on the (JIT) Graal JDK.
| NobleExpress wrote:
| Ah right. I assumed it was a native image.
| marginalia_nu wrote:
| I think the project does have a bit of a naming problem.
| They've gotten the part out where it's very fast and
| pretty good, but everything is named GraalVM-something
| and it's not always entirely clear what's being referred
| to.
| blauditore wrote:
| Reminds me of a time where I almost certainly found a bug in
| Safari Mobile's JS implementation. Some variable ended up
| undefined in a place where it was provably impossible. It
| didn't happen consistently and was prone to right timing, so
| extremely hard to pin down and debug. Given the fact that all
| debugging had to be done tediously through a phone emulator and
| remote dev tools (it was inside a Cordova app), I eventually
| just gave up and added some sort of if-else for that case.
| darepublic wrote:
| Cannot hear the name cordova app without a rush of negative
| memories
| NobleExpress wrote:
| Interesting. Perhaps you can inspect the disassembly of the
| function in question when using Graal and HotSpot. It is likely
| related to that.
|
| Another debugging technique we use for heisenbugs is to see if
| `rr` [1] can reproduce it. If it can then that's great as it
| allows you to go back in time to debug what may have caused the
| bug. But `rr` is often not great for concurrency bugs since it
| emulates a single-core machine. Though debugging a VM is
| generally a nightmare. What we desperately need is a debugger
| that can debug both the VM and the language running on top of it.
| Usually it's one or the other.
|
| > In general I'd argue you haven't fixed a bug unless you
| understand why it happened and why your fix worked, which makes
| this frustrating, since every indication is that the bug exists
| within proprietary code that is out of my reach.
|
| Were you using Oracle GraalVM? GraalVM community edition is open
| source, so maybe it's worth checking if it is reproducible in
| that.
|
| [1]: https://github.com/rr-debugger/rr
| postatic wrote:
| I had a bug in my code during my research degree. I was able to
| get some results and write it up as a thesis, submit it and get
| my degree.
|
| That was almost 15 years ago. But to this day, every now and then
| I feel a little guilty about getting that degree because I
| haven't truly solved that bug.
| taneq wrote:
| Research code doesn't have to be bug free, it just has to work
| correctly long enough to generate the graphs for your paper.
| dangoodmanUT wrote:
| I think this is an interesting metaphor about "compatible"
| runtimes. I see the same a lot with Bun and Node. Node works, Bun
| doesn't, completely unable to explain why.
| joshstrange wrote:
| This is my biggest concern with bun and deno, they both look
| awesome and provide some really cool features out of the box,
| but I'm terrified that I won't be able to fix a low level
| problem if one arises. I'm already dealing with the extra layer
| of AWS lambda, I find the trade-off to be worth it, but adding
| more complexity seems like a bad idea.
| wwilson wrote:
| If you would like us to repro this bug in Antithesis and help you
| debug it there, email me and I'll hook you up:
| will@antithesis.com
| gaogao wrote:
| Ooo, I also had a graalvm migration bug, where it was corrupting
| a deep aes256 call which was costing us ~1M dollars a day or so
| until we figured it out.
| mastermedo wrote:
| Yikes, can you explain a bit more? It sounds like a nightmare
| to debug.
| gaogao wrote:
| Yeah, I think it was that an AES function/instructions and
| some array clearing were getting reordered unsafely, but only
| under some very specific distributed modes. We were mostly
| able to get repo after a couple of days, but it was
| complicated by having a pretty deep stack and the fact that
| the corrupting change was being canaried out, not released.
| justinclift wrote:
| Which architecture (and preferably) what models of cpu is it
| occurring on?
| marginalia_nu wrote:
| I've reproduced both in bare metal on an Epyc 7543 and a qemu-
| virtualized Ryzen 9 3900X; so x86_64.
| justinclift wrote:
| Interesting. Might be worth a try on something non-AMD if
| possible, just to rule out some weird microcode bug hanging
| around in the Zen family?
| KingOfCoders wrote:
| "The Bug" by Ellen Ullman
| tuyiown wrote:
| I had a similar problem on a nth program start, in seemingly the
| same conditions, was a disk cache memory hardware failure, some
| memory block return 1, whatever was written into it. The bug
| trigger was highly erratic, because corrupt reads only was on
| cache read, and crashed my program as it was one of the single
| thing running on the system most of the time, and one of the
| single thing that was re-read enough to be kept in cache despite
| large disk traffic.
|
| The program had a large number of hour without incident, was
| thoroughly tested with unit test, and had 0 valgrind warning. I'd
| been intermittently tracking the problem for months, and the fact
| that it was an hardware issue was a huge relief, as I really
| started to loose footing on the necessary minimum of confidence
| in predictability you need to write software.
| koliber wrote:
| Love a good debugging story. Curious if there is a way to narrow
| the bug down.
|
| Looking at the code, it seems it is copying val to counts. It
| does analogous arithmetic on val an on counts, and since they
| both should contain the same data, it's surprising that the
| result of the arithmetic does not match.
|
| Can you reorder the code to see if the error is reproducible? Do
| it only for a diagnostic run, and don't change the actual code.
| For example, change the first loop into two loops:
| for (int i = 0; i < length; i++) { counts[i] = val[i];
| } long offset = 0; for (int i = 0; i < length;
| i++) { offset += val[i]; }
|
| Perhaps some combination of writing val[i] and immediately
| reading it causes an issue.
|
| Another variant to try is to add another running counter that
| mimics the size arithmetic, but in the first loop, and compare
| the three values to see if you get 2 out of three to match:
| long offset = 0; long size_debug = 0; for (int i = 0;
| i < length; i++) { counts[i] = val[i]; offset +=
| val[i]; size_debug += counts[i]; }
|
| If this does not change the behavior, see if there is a region of
| the file where size and offset diverge. Maybe it is in a random
| place. Maybe it's always near the end. Maybe it's localized
| somehow. How to do this would involve writing a value of offset
| every X iterations of i, as well as writing the value of size
| every X iterations of i, and seeing if there is a pattern where
| they diverge. Do it every 1Gb or so.
|
| If I had to place a long bet, my guess is that somewhere in the
| first loop, after assigning counts[i] = val[i]; reading from
| val[i]; does not return the same value. You said it's in the same
| thread, but we need to admin this is a deep bug, so all bets are
| off.
| _wire_ wrote:
| "You can prove the presence of bugs, but not their absence" --A
| Programmer
|
| The systems employ concurrency at multiple levels, where the
| system design lacks a unified paradigm for establishing its
| correctness.
|
| So concurrency "errors" should be expected.
|
| I always start wondering why such bugs aren't more common. But
| then I realize a dilemma.
|
| For concurrency errors, you can know an error occurs but have no
| way to work backwards to the specific conditions of its cause
| (incorrect design). All you can do is perturb the system into not
| exhibiting the error.
|
| Lacking a formal way to establish correctness, we are left to an
| engineering of attrition, in which the author is engaged.
|
| If the failure becomes common, system parameters will be adjusted
| to perturb behavior back into obscurity with a black art called
| "debugging" that approximates correctness.
|
| The contravening property of the system is the underlying logic
| runs so fast with respect to human attention that failure modes
| are pressed into high likelihood of being observed and therefore
| "corrected" (approximately). Bugs which are common enough to
| merit attention are perturbed out of "existence" by "version
| charges."
|
| This seems to imply that such failures should be both expected as
| unavoidable and rare according to limits of human attention
| according to engineering by attrition.
|
| Welcome to the author's world. We are all facing this sunk cost.
|
| In the bug picture (haha) we simply abide systems that "work"
| according to a distribution of our tolerance for the nuisance of
| their inevitable failure in modes that are too rare to be
| "corrected."
|
| As the author explains he's working with newer versions of a
| machine. Huzzah!
|
| Meanwhile, the ubiquity of deployments is scaling towards
| infinity, implying that a small clique of individual humans can
| expect to be driven mad by faults that appear demonic while the
| hoard of humanity lumbers on enduring the costs of "good enough"
| design.
|
| Except maybe for the contingency that the strategic nuclear
| deterrent is be placed under control of an AI.
|
| Luckily for the individual human there is death.
|
| Unluckily for humanity, someone is likely trying to place the
| strategic nuclear deterrent under control of an AI
| pyinstallwoes wrote:
| Related the forbidden "glitch" - not allowed to discuss.
|
| https://www.youtube.com/watch?v=47lcjbyqF_k&t=4066s
|
| 1. Measuring Deep Metastability and Its Effect on Synchronizer
| Performance -
|
| 2. He Who Hesitates is Lost: Decisions and free will in men and
| machines - http://async.org.uk/David.Kinniment/DJKinniment-He-
| Who-Hesit...
|
| "Buridan's ass is an illustration of a paradox in philosophy in
| the conception of free will. It refers to a hypothetical
| situation wherein an ass (donkey) that is equally hungry and
| thirsty is placed precisely midway between a stack of hay and a
| pail of water. Since the paradox assumes the donkey will always
| go to whichever is closer, it dies of both hunger and thirst
| since it cannot make any rational decision between the hay and
| water.
|
| A common variant of the paradox substitutes the hay and water
| for two identical piles of hay; the ass, unable to choose
| between the two, dies of hunger.
|
| The paradox is named after the 14th-century French philosopher
| Jean Buridan, whose philosophy of moral determinism it
| satirizes.
|
| Although the illustration is named after Buridan, philosophers
| have discussed the concept before him, notably Aristotle, who
| put forward the example of a man equally hungry and thirsty,
| and Al-Ghazali, who used a man faced with the choice of equally
| good dates.
|
| A version of this situation appears as metastability in digital
| electronics, when a circuit must decide between two states
| based on an input that is in itself undefined (neither zero nor
| one).
|
| Metastability becomes a problem if the circuit spends more time
| than it should in this "undecided" state, which is usually set
| by the speed of the clock the system is using. Interesting"
| rc_kas wrote:
| > "Doesn't work" is famously not an error description
|
| This guy is extremely self-aware
| joncrocks wrote:
| Had a similar bug in a production system about 10 years ago.
| Indexes got corrupted after some length of time. Only in
| production, couldn't replicate. A distributed system as well.
|
| We (mainly a collegue of mine) eventually traced it down to a
| smaller part of the code until we noticed a subtle bug.
|
| Multi reader + multi writer and a atomic operation that
| miscounted the number of readers.
|
| Took us a couple of weeks to track down if I remember right.
|
| https://issues.redhat.com/browse/ISPN-4777
| dwattttt wrote:
| They're a little off when looking for 32bit overflows: unsigned
| 32bit integers top out at ~4gb, that kind of bug would've shown
| up much smaller than 32gb.
| marginalia_nu wrote:
| The indexed data consists of 128 bit records, not bytes.
| dwattttt wrote:
| Apologies, I was confused by the reference to 32bit integer
| overflows for file sizes over 32gb.
| marginalia_nu wrote:
| Yeah, file size is 2 GB x record size (2 and not 4 because
| signed ints.)
| 99112000 wrote:
| One word: fuzzing.
| marginalia_nu wrote:
| Fuzzing finds logic errors though. This appears to be a
| compiler error.
| neerajsi wrote:
| Seems like it could be a compiler or GC bug (or a bug with the
| safe pointing interaction between compiler and GC).
|
| It's possible that a write to the counts array is misdirected so
| it doesn't occur.
|
| Is the sum of counts always less than the sum of vals?
|
| On second thought, if counts is mmapped, GC might not be in play.
| But a similar bug might occur due to state being lost during an
| On-stack-replacement of one of the loops.
|
| I'm not familiar with deep jvm stuff, but is there a way to ask
| the jvm for a compilation log to see if JIT OSR is happening?
| pixelmonkey wrote:
| Great post. I posted about my real-world experience of a deep bug
| like this on lobste.rs. Here is that comment/explainer:
|
| https://lobste.rs/s/qjrdss/computers_can_be_understood#c_hqu...
|
| For any fellow sufferers, the needle in the haystack is "skb
| rides the rocket." Same bug was also hit by Brendan Gregg around
| the same time.
| kazinator wrote:
| [delayed]
___________________________________________________________________
(page generated 2024-04-10 23:01 UTC)