Hi there! I had a really fun debugging session a couple weeks ago on illumos with my coworkers at Oxide, and I thought I’d write about it. We used mdb and pmap, among other tools, to debug an issue that seemed very strange at first but was ultimately simple.
Speak of the devil, I just started the application today and should submit tomorrow.
Do you normally keep notes similar to the article when troubleshooting (if so, I’d love to see your note taking strategy) or were you able to go back and collect each step? I adore the detail, but never know what output etc. to persist while digging and at the end, just end up with a list of bullets.
At Oxide we actually record all our meetings, so while writing up the report I ended up referring to the recording a few times. I did have an Obsidian page open to take notes in the moment as well, but those were mostly of the “dump terminal output and GitHub gist URLs” variety. (There’s also a little bit of parallel construction to make the blog post easier to digest, but not that much.)
One of the reasons I like using debugging tools like MDB that are shell- or REPL-shaped is that you can easily run them under script(1), a program that will log a terminal session to a file you can flick back through later. There are presumably also lots of other ways to achieve this; e.g., I believe tmux can log or dump a buffer to a file, I’m sure terminal emulators can probably do this on their own, etc. It’s also pretty easy to go and copy large chunks of a debugging session straight from your terminal scroll buffer into a notes file, either as you go or after a particular realisation.
this is super cool. Potentially a dumb question, but what is the purpose/goal of illumos? In other words, why would someone choose to use it over a BSD or Linux.
I’m decently aware of the lineage of the BSDs and GNU/Linux, but I’ve not really heard much about illumos. Is there compatibility that it maintains like HaikuOS with BeOS?
illumos is a descendent of Solaris, which is based on System V. So it forms a distinct lineage from either Linux or BSD. illumos pioneered a number of features such as the ZFS filesystem—illumos still has the most rock-solid implementation of ZFS.
Our choice of illumos was driven by several factors. Beyond the technologies we wanted to make use of like ZFS, there were also a couple of more social factors. One of them was that our team was deeply experienced in it—another was that it’s just easier to do what you need when you’re a big fish in a small pond. You might be familiar with the general temperament of folks on the LKML. (In one of my previous roles, I was on the source control team at Meta. Over there, we chose Mercurial over Git for very similar reasons, including the temperament reason!)
However, note that all of this is an implementation detail for our customers—all they see is a system that can run VMs and manage storage + networking via the web GUI, CLI, or HTTP/Terraform APIs.
Ha – even more embarrassingly, I’m the one who added it! Good going, Past Me – and please tell Past Future Me to check the RFD before assuming the link isn’t there. ;)
Brian Cantrill is not just “people from sun”, he worked on Solaris itself from his hiring back in 1996.
Though I don’t think the other founders are from Sun at all? AFAIK Jessie Frazelle was Linux all the way until she got hired by MS to work on containers and OSS over there until the foundation of Oxide, and I can’t find evidence that Steve Tuck worked at sun, though my refusal to get a LinkedIn account means I can’t see his entire profile.
I’ll admit I was befuddled by the decision to go with Illumos, but that article makes very sound arguments for it. Besides the technical aspects, one note I particularly appreciate is how they want to avoid the interpersonal issues that the Linux community is marred with. This really can’t be said enough, the entire Linux ecosystem is simply too much of a sociopolitical quagmire of power struggles and hurt egos for me to have any considerable investment in anymore (as an example, I don’t have any strong feelings towards systemd one way or the other, but I wince every time it gets mentioned because of how many people seemingly feel compelled to vent every practical and imagined grief they have with it). I’ve never given Illumos much credit in the past, but now I’ll have to give it more of an investigation, maybe I’ll add it to my list of OS projects I’m watching along with Redox. We really need more viable OS alternatives, otherwise the existing ones just get too bogged down with all manner of technical and personal problems.
A description of git I’ve seen recently that I find very fitting is that it’s not a VCS but rather a toolkit for building one.
Similarly Linux is not an operating system unto itself but rather a component of a GNU system. Except for when you choose to mix-and-match LLVM and MUSL stuff. I also find Linux to give me more powerful tools for building debugging utilities (eBPF) yet there are no complete utilities to match those by Brendan Gregg for SunOS/Solaris/Illumos that a Sun salesman tried to sell him back in 2005.
I suspect the Oxide people came to the conclusion that using Illumos is less work than building everything for Linux.
Probably because it’s easier to own your stack with it than with Linux. It’s the same reason why Apple has Darwin; Darwin isn’t interesting on its own, but the fact they have total control over it means it’s easier to add things that would benefit with less coordination/cross-cutting between projects.
My assumption with this is that it would imply that you have to do a lot more work. I don’t see it as impossible but it always strikes me as interesting when people go heavily against the grain - because they presumably know that they can handle a certain load of extra work compared to using another stack that has attention already.
What we’re doing at Oxide is so ambitious that we’d have to put extensive work into whatever stack we choose. At that point it’s a matter of balancing effort vs risk. (For instance, we use many pieces of third-party software like CockroachDB, and we need to validate it on illumos.)
The isle_opt.rs that triggered this bug is a fun example of generated code. There’s at least one place that it fills my entire screen with nothing but }’s.
I once ran into a bug in rustc that I first saw on a s390x machine where the compiler would break after the first compilation. It turned out to be a bug in the incremental compilation on Big Endian machines. It was pretty odd to me that no-one had found it, but I guess that close to no one develops on big endian anymore.
It is just in my free time as I was playing around with the hardware compression on s390x (which is very cool)
You can get borrow a small machine for no pay in IBM’s could which is pretty cool. And Marist University also have one you can get access to if you ask.
What a fantastic read! Thanks a lot for sharing the experience in such detail.
I know that many production compilers use recursive descent parsing, and I always wondered about how they deal with stack overflow. I thought that it was a very unlikely event, as you would need some extremely deeply nested source code to trigger such thing, but, as pointed out by the article, it seems that these cases do happen.
Today I learned that the stack can grow dynamically on modern OSes. This seems to work for rustc, but I guess it wont work on every platform. For example on Wasm, I don’t think this trick is possible. From what I have seen, Rust compiled to Wasm always picks a fixed point at the beginning of the linear memory for the stack base, and it grows downwards to zero. I don’t see a way to grow that. But maybe I’m wrong.
I’ve also seen that it’s possible to implement a recursive descent parser without using actual stack recursion (as it is possible for any recursive algorithm), just using a loop and a heap allocated object stack. This technique is used in the IntelliJ IDEA parser and I also read about it in a post on writing resilient parser by matklad.
As I learn about writing compilers, I wonder if it is worth dealing with this problem, or if it’s okay to simply forbid nesting up until certain limit.
This technique is used in the IntelliJ IDEA parser
Hm, I am 0.8 sure that that’s not the case, and that most parsers IJ are implemented with recursion, with a check to produce an error node if the tree gets too deep (my memory is hazy here, so best to double check against specific source code).
Non-recursive parsing wouldn’t have helped IJ much anyway, because the stuff would have blown up anyway the moment something tries to process the tree recursively. You need to forfeit not only recursive parsing, but recursive tree itself, and use something like RPN as the internal representation, which is convenient to process iteratively.
One toolchain that does that in a principled way is Carbon.
You are probably right, I remember looking at the code some time ago and I found it similar to the one in your post, but I haven’t looked in detail.
You need to forfeit not only recursive parsing, but recursive tree itself, and use something like RPN as the internal representation, which is convenient to process iteratively.
I’m not sure about this. It seems to me that it is possible to traverse a recursive data structure in a non stack recursive way. Using a (heap allocated) stack of node pointer and a loop, in a similar way as you would implement a depth first search algorithm on a graph. Or maybe I’m missing something?
But I understand your point in the sense that if you provide a recursive data structure as an API, users will be very tempted to use stack recursion to traverse it, as it’s the most straightforward way to do it. And if they do that, stack is likely to blow if the nodes go too deep.
I guess having a depth limit is a sensible approach for most compilers then. Thanks for the insights!
Yeah, you’re got it. While I haven’t worked much on compilers I have worked on systems that have to walk around on large data structures (mostly trees and approximately planar graphs). Converting the implementation of a recursive algorithm into a non-recursive implementation generally involves maintaining your own stack/priority queue/whatever housekeeping structure and establishing a formal “next-node” condition (i.e. for a given node, what do we do next? Pop from the stack, push its children into the priority queue, etc). It’s not always super straightforward to see but once you figure out how to determine what to do next it’s not too bad.
On the consumer side I use the Visitor pattern pretty frequently. The logic for how to walk the data structure is encapsulated in the data structure itself and consumers pass in a function/object/whatever with hooks that get called as the walk algorithm does its thing. Sometimes it’s just a visit() function that gets called once per node. Sometimes it’s split into enter()/exit() functions that get called, basically, when a node is pushed onto the stack and popped off the stack. In some cases the exit() function is actually allowed to modify the data structure since all of the child nodes have already been visited and won’t affect the rest of the traversal.
Edit: and on the arbitrary graph side, sometimes I’ve set it up so that the Visitor itself is responsible for determining which node to visit next. This is useful for things like pathfinding
Yeah, for a graph with heterogenous nodes, plain recursive code is just easier to write.
Something to consider as well is the performance implications. With plain recursive code the compiler can do a pretty good job inlining bits of it, particularly with PGO. With an explicit stack inlining might not be as good. Honestly I really like the stacker approach, as long as it is used appropriately.
I’ve also seen that it’s possible to implement a recursive descent parser without using actual stack recursion
Only by using the heap (via a dynamically growing vector or suchlike). Guess what stacker is doing? Using the heap too! From the perspective of the OS and the computation resource needs of the program, the two techniques are not meaningfully different (albeit for a small amount of overhead).
And since recursive algorithms like parsers are usually easier to implement with ‘proper’ in-language recursion… why not use that and defer memory management to a utility library like stacker instead? Much simpler.
As a more general point, context-free grammars, of which Rust is (sort of) one, cannot be parsed with finite memory and may potentially require unbounded recursion (and hence unbounded memory to track that recursion state). Compare that to something like regular grammars (think regex - again, sort of) that can be parsed with finite memory.
They differ significantly in the required runtime support. To do something like stacker, you need von Neumann architecture which allows you to manipulate your own call stack. So, this doesn’t work on WASM.
This is the same class of statement as “Rust doesn’t need async, because it can use runtime facilities to allocate cheap independent threads of execution”. The difference is mostly of degree: mappable stacks are more widely available than efficient support for small-scale concurrency.
They differ significantly in the required runtime support. To do something like stacker, you need von Neumann architecture which allows you to manipulate your own call stack.
I wonder if anyone thought of using threads as a portable way to extend the stack. That is, when you see you are about to run out of stack, spawn a new thread and continue your call chain there, blocking the current thread. One would probably want to reuse the threads rather than spawning/terminating them all the time. Though if the need to extend the stack is relatively rare, even spawning might be acceptable.
Yeah, that’s definitely come up! There are some performance implications to that, and also one of the challenges is that such code would have to be thread-safe (i.e. implement Send, and be prepared to handle a different set of thread-locals). But it would certainly work.
Hi there! I had a really fun debugging session a couple weeks ago on illumos with my coworkers at Oxide, and I thought I’d write about it. We used
mdbandpmap, among other tools, to debug an issue that seemed very strange at first but was ultimately simple.Speak of the devil, I just started the application today and should submit tomorrow.
Do you normally keep notes similar to the article when troubleshooting (if so, I’d love to see your note taking strategy) or were you able to go back and collect each step? I adore the detail, but never know what output etc. to persist while digging and at the end, just end up with a list of bullets.
Thanks for the kind words and good luck!
At Oxide we actually record all our meetings, so while writing up the report I ended up referring to the recording a few times. I did have an Obsidian page open to take notes in the moment as well, but those were mostly of the “dump terminal output and GitHub gist URLs” variety. (There’s also a little bit of parallel construction to make the blog post easier to digest, but not that much.)
One of the reasons I like using debugging tools like MDB that are shell- or REPL-shaped is that you can easily run them under script(1), a program that will log a terminal session to a file you can flick back through later. There are presumably also lots of other ways to achieve this; e.g., I believe tmux can log or dump a buffer to a file, I’m sure terminal emulators can probably do this on their own, etc. It’s also pretty easy to go and copy large chunks of a debugging session straight from your terminal scroll buffer into a notes file, either as you go or after a particular realisation.
Your thoroughly detailed and beginner friendly writing style is highly inspiring. Thank you!
this is super cool. Potentially a dumb question, but what is the purpose/goal of illumos? In other words, why would someone choose to use it over a BSD or Linux.
I’m decently aware of the lineage of the BSDs and GNU/Linux, but I’ve not really heard much about illumos. Is there compatibility that it maintains like HaikuOS with BeOS?
Thanks for the kind words!
illumos is a descendent of Solaris, which is based on System V. So it forms a distinct lineage from either Linux or BSD. illumos pioneered a number of features such as the ZFS filesystem—illumos still has the most rock-solid implementation of ZFS.
Our choice of illumos was driven by several factors. Beyond the technologies we wanted to make use of like ZFS, there were also a couple of more social factors. One of them was that our team was deeply experienced in it—another was that it’s just easier to do what you need when you’re a big fish in a small pond. You might be familiar with the general temperament of folks on the LKML. (In one of my previous roles, I was on the source control team at Meta. Over there, we chose Mercurial over Git for very similar reasons, including the temperament reason!)
However, note that all of this is an implementation detail for our customers—all they see is a system that can run VMs and manage storage + networking via the web GUI, CLI, or HTTP/Terraform APIs.
that’s super cool. I didn’t know that ZFS came from illumos. Maybe I’ll try running illumos myself for fun.
It did not come from illumos. It came from Solaris, the system that illumos is based on/forked from.
Yes, I was grouping Solaris into it. I think most of the resiliency work on it has been done in illumos, though.
This post is actually a decent example of one reason why you’d choose illumos over BSD or Linux: some of its dev tools are top-tier.
Yeah, I’m just scratching the surface here. I helped out with debugging a far more complex issue last year, which dtrace helped tremendously with.
Oxide have a public decision on why they have decided on Illumos, though it probably helps that it is founded by people from Sun.
https://rfd.shared.oxide.computer/rfd/0026
I should update RFD 26 to point to this, but we also have an Oxide and Friends episode on Helios that helps explain the rationale.
There’s a link to that already! Search for “oxf-s4e4”.
Ha – even more embarrassingly, I’m the one who added it! Good going, Past Me – and please tell Past Future Me to check the RFD before assuming the link isn’t there. ;)
Brian Cantrill is not just “people from sun”, he worked on Solaris itself from his hiring back in 1996.
Though I don’t think the other founders are from Sun at all? AFAIK Jessie Frazelle was Linux all the way until she got hired by MS to work on containers and OSS over there until the foundation of Oxide, and I can’t find evidence that Steve Tuck worked at sun, though my refusal to get a LinkedIn account means I can’t see his entire profile.
Steve didn’t work at Sun, but he did work at Joyent for a decade which had a big illumos deployment.
Which is true but has nothing to do with the comment I replied to.
Also Steve was SVP of Sales then COO at joyent, I doubt Illumos was of much direct relevance to his job.
You’d be surprised :)
You are right, seems like I was under a false impression.
I’ll admit I was befuddled by the decision to go with Illumos, but that article makes very sound arguments for it. Besides the technical aspects, one note I particularly appreciate is how they want to avoid the interpersonal issues that the Linux community is marred with. This really can’t be said enough, the entire Linux ecosystem is simply too much of a sociopolitical quagmire of power struggles and hurt egos for me to have any considerable investment in anymore (as an example, I don’t have any strong feelings towards systemd one way or the other, but I wince every time it gets mentioned because of how many people seemingly feel compelled to vent every practical and imagined grief they have with it). I’ve never given Illumos much credit in the past, but now I’ll have to give it more of an investigation, maybe I’ll add it to my list of OS projects I’m watching along with Redox. We really need more viable OS alternatives, otherwise the existing ones just get too bogged down with all manner of technical and personal problems.
A description of git I’ve seen recently that I find very fitting is that it’s not a VCS but rather a toolkit for building one. Similarly Linux is not an operating system unto itself but rather a component of a GNU system. Except for when you choose to mix-and-match LLVM and MUSL stuff. I also find Linux to give me more powerful tools for building debugging utilities (eBPF) yet there are no complete utilities to match those by Brendan Gregg for SunOS/Solaris/Illumos that a Sun salesman tried to sell him back in 2005. I suspect the Oxide people came to the conclusion that using Illumos is less work than building everything for Linux.
Probably because it’s easier to own your stack with it than with Linux. It’s the same reason why Apple has Darwin; Darwin isn’t interesting on its own, but the fact they have total control over it means it’s easier to add things that would benefit with less coordination/cross-cutting between projects.
My assumption with this is that it would imply that you have to do a lot more work. I don’t see it as impossible but it always strikes me as interesting when people go heavily against the grain - because they presumably know that they can handle a certain load of extra work compared to using another stack that has attention already.
What we’re doing at Oxide is so ambitious that we’d have to put extensive work into whatever stack we choose. At that point it’s a matter of balancing effort vs risk. (For instance, we use many pieces of third-party software like CockroachDB, and we need to validate it on illumos.)
The
isle_opt.rsthat triggered this bug is a fun example of generated code. There’s at least one place that it fills my entire screen with nothing but}’s.I once ran into a bug in rustc that I first saw on a s390x machine where the compiler would break after the first compilation. It turned out to be a bug in the incremental compilation on Big Endian machines. It was pretty odd to me that no-one had found it, but I guess that close to no one develops on big endian anymore.
https://github.com/rust-lang/rust/issues/90123
I’m jealous! I’ve always wanted to play around with a big-endian system.
It is just in my free time as I was playing around with the hardware compression on s390x (which is very cool)
You can get borrow a small machine for no pay in IBM’s could which is pretty cool. And Marist University also have one you can get access to if you ask.
You’ve gotta grab a SPARCstation of something off ebay!
What a fantastic read! Thanks a lot for sharing the experience in such detail.
I know that many production compilers use recursive descent parsing, and I always wondered about how they deal with stack overflow. I thought that it was a very unlikely event, as you would need some extremely deeply nested source code to trigger such thing, but, as pointed out by the article, it seems that these cases do happen.
Today I learned that the stack can grow dynamically on modern OSes. This seems to work for rustc, but I guess it wont work on every platform. For example on Wasm, I don’t think this trick is possible. From what I have seen, Rust compiled to Wasm always picks a fixed point at the beginning of the linear memory for the stack base, and it grows downwards to zero. I don’t see a way to grow that. But maybe I’m wrong.
I’ve also seen that it’s possible to implement a recursive descent parser without using actual stack recursion (as it is possible for any recursive algorithm), just using a loop and a heap allocated object stack. This technique is used in the IntelliJ IDEA parser and I also read about it in a post on writing resilient parser by matklad.
As I learn about writing compilers, I wonder if it is worth dealing with this problem, or if it’s okay to simply forbid nesting up until certain limit.
Hm, I am 0.8 sure that that’s not the case, and that most parsers IJ are implemented with recursion, with a check to produce an error node if the tree gets too deep (my memory is hazy here, so best to double check against specific source code).
Non-recursive parsing wouldn’t have helped IJ much anyway, because the stuff would have blown up anyway the moment something tries to process the tree recursively. You need to forfeit not only recursive parsing, but recursive tree itself, and use something like RPN as the internal representation, which is convenient to process iteratively.
One toolchain that does that in a principled way is Carbon.
You are probably right, I remember looking at the code some time ago and I found it similar to the one in your post, but I haven’t looked in detail.
I’m not sure about this. It seems to me that it is possible to traverse a recursive data structure in a non stack recursive way. Using a (heap allocated) stack of node pointer and a loop, in a similar way as you would implement a depth first search algorithm on a graph. Or maybe I’m missing something?
But I understand your point in the sense that if you provide a recursive data structure as an API, users will be very tempted to use stack recursion to traverse it, as it’s the most straightforward way to do it. And if they do that, stack is likely to blow if the nodes go too deep.
I guess having a depth limit is a sensible approach for most compilers then. Thanks for the insights!
To clarify, resilient LL parsing presents a recursive algorithm.
I do show a non-recursive approach in https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html
Yeah, you’re got it. While I haven’t worked much on compilers I have worked on systems that have to walk around on large data structures (mostly trees and approximately planar graphs). Converting the implementation of a recursive algorithm into a non-recursive implementation generally involves maintaining your own stack/priority queue/whatever housekeeping structure and establishing a formal “next-node” condition (i.e. for a given node, what do we do next? Pop from the stack, push its children into the priority queue, etc). It’s not always super straightforward to see but once you figure out how to determine what to do next it’s not too bad.
On the consumer side I use the Visitor pattern pretty frequently. The logic for how to walk the data structure is encapsulated in the data structure itself and consumers pass in a function/object/whatever with hooks that get called as the walk algorithm does its thing. Sometimes it’s just a visit() function that gets called once per node. Sometimes it’s split into enter()/exit() functions that get called, basically, when a node is pushed onto the stack and popped off the stack. In some cases the exit() function is actually allowed to modify the data structure since all of the child nodes have already been visited and won’t affect the rest of the traversal.
Edit: and on the arbitrary graph side, sometimes I’ve set it up so that the Visitor itself is responsible for determining which node to visit next. This is useful for things like pathfinding
Yeah, for a graph with heterogenous nodes, plain recursive code is just easier to write.
Something to consider as well is the performance implications. With plain recursive code the compiler can do a pretty good job inlining bits of it, particularly with PGO. With an explicit stack inlining might not be as good. Honestly I really like the stacker approach, as long as it is used appropriately.
Only by using the heap (via a dynamically growing vector or suchlike). Guess what stacker is doing? Using the heap too! From the perspective of the OS and the computation resource needs of the program, the two techniques are not meaningfully different (albeit for a small amount of overhead).
And since recursive algorithms like parsers are usually easier to implement with ‘proper’ in-language recursion… why not use that and defer memory management to a utility library like stacker instead? Much simpler.
As a more general point, context-free grammars, of which Rust is (sort of) one, cannot be parsed with finite memory and may potentially require unbounded recursion (and hence unbounded memory to track that recursion state). Compare that to something like regular grammars (think regex - again, sort of) that can be parsed with finite memory.
They differ significantly in the required runtime support. To do something like stacker, you need von Neumann architecture which allows you to manipulate your own call stack. So, this doesn’t work on WASM.
This is the same class of statement as “Rust doesn’t need async, because it can use runtime facilities to allocate cheap independent threads of execution”. The difference is mostly of degree: mappable stacks are more widely available than efficient support for small-scale concurrency.
I wonder if anyone thought of using threads as a portable way to extend the stack. That is, when you see you are about to run out of stack, spawn a new thread and continue your call chain there, blocking the current thread. One would probably want to reuse the threads rather than spawning/terminating them all the time. Though if the need to extend the stack is relatively rare, even spawning might be acceptable.
Yeah, that’s definitely come up! There are some performance implications to that, and also one of the challenges is that such code would have to be thread-safe (i.e. implement
Send, and be prepared to handle a different set of thread-locals). But it would certainly work.