I would love to see a more in depth article about what kind of programming you need to do for a system controlling a rocket.
I remember reading that they cannot use exceptions and have to handle every possible scenario. Part of me wonders how much of the source code is just error handling.
I didn't mean "just" in that sense, I mean "just" as in "solely dedicated to".
Most apps have error handling code taking up what? 20-30% of the code at the most? For some reason I imagine this stuff being almost 70% error handling but I am not sure if that is realistic.
So, assuming there are shed loads of error handling that knocks on to everything else about the system. How do they test it? How do they spec out all the possible conditions? What do they do differently to someone writing a SaaS, Desktop app or IOS app?
It looks like it would be a very different world which is not really written about (Apart from the old articles posted in one of the above comments)
> Most apps have error handling code taking up what? 20-30% of the code at the most? For some reason I imagine this stuff being almost 70% error handling but I am not sure if that is realistic.
I work in a FreeBSD-derived kernel in areas related to the buf / caching subsystem, which probably has a lot of similarities to pre-2.6 linux (they have diverged more since the 90s). I don't know that I can quantify it, but 20-30% feels like a low number.
> So, assuming there are shed loads of error handling that knocks on to everything else about the system. How do they test it?
One thing we use to test error-case handling is "fail points" — sysctls usable from unit tests that trigger some fault condition. These aren't perfect — they are manually added to code, and because of this, coverage is fairly low — but they're a start.
> How do they spec out all the possible conditions? What do they do differently to someone writing a SaaS, Desktop app or IOS app?
I'm curious for more details about the software stack used on their rockets. If they are using gcc and gdb, it sounds like everything is C. Which is a scary thought. :\",
C has a number of safety-compromising properties that require positive human effort to counteract.
You can go a long way to counteracting some of these with automated toolchains.
You can probably go further by using languages which simply eliminate certain classes of error and then having the same level of toolchain elaboration.
That's not to say that C code can't be safe. It can absolutely be made safe. It just costs more, and any system that requires positive human effort is more likely to fail than one that doesn't.
This will compile. (Or maybe it won't, I haven't cut C for some time now).
But you've missed the ROCKET_FAULT case. In languages which check for case completeness, this kind of logical construction would cause a compiler failure. ML, F#, Rust etc will all complain that you haven't addressed all cases.
Sometimes this or something like it is added to a code template:
default: assert(false);
Which is defensive code that's great for test. But not as great for rockets. Better if bad code simply can't be written.
I believe static analysis tools can now pick up on missing cases, but there are still lots of reasons why C can't be as fully analysed as a language like ML, Haskell, ATS, Rust etc can be. Putting aside the obvious problem of undefined behaviour meaning you really want to push C code through multiple compilers and multiple static analysis tools, there's also the great universal escape hatch for C: direct memory access.
When you can simply go in and change memory, type systems and analysis are strictly speaking no longer going to work without positive human effort to refrain from doing that. Analysis can only make guarantees under certain assumptions; introduce direct memory access and all bets are off.
Yes, discipline and coding standards can also cut this down. Some analysis tools will do partial analysis of memory accesses. But it still requires positive human action. A computing system includes the humans who make it, run it and use it. Cutting down on the avenues for mistakes is a good thing.
Assuming gcc or similar, -Wall will pick up on this.
int main() {
enum states { A, B, C } x = A;
switch(x) {
case A: break;
case B: break;
// C not handled on purpose
}
return 0;
}
$ g++ -Wall -Werror -o enum enum.cc
cc1plus: warnings being treated as errors
enum.cc: In function ‘int main()’:
enum.cc:3: warning: enumeration value ‘C’ not handled in switch
I like this behavior since I can deliberately leave out a default and make sure I always have every case handled explicitly.
Thanks for the answer. I'm curious about the implication that there aren't any mature static analysis tools that catch all undefined behavior and memory access to potentially invalid or mis-typed objects. I expect such tools technically could exist but don't know if they actually do.
I might not understand what you mean regarding positive human action when talking about using static analysis tools -- are you referring to tools that require a manual process to run and evaluate, rather than having your tools outright fail to produce a program if static analysis isn't completely happy with the source code?
Positive human action means that somebody must take some action in order for the system to work. That is, effort above a natural baseline. Such systems are not failsafe.
The classic example in C/C++ is avoiding buffer overflow defects. If you code naively to the language, they will creep in. Additional effort is require to apply policies and procedures to prevent such errors from occurring -- enabling warnings, using static analysis, using particular libraries like BString and so on. Further effort is required to ensure compliance.
I use the term "positive" by analogy with legal positivism, which is (very roughly) that law is created by legislative action and doesn't exist until that has occurred. Similarly, many kinds of safety in C don't exist until you have taken that positive step to introduce additional safeguards.
In languages with a more complete view of strings, all of this additional activity is unnecessary. Positive human effort is not required to prevent buffer overflows in such languages. No new procedures, policies, libraries or tools need to be introduced or mandated. The system's baseline configuration is already safe against that class of errors.
Why does this matter?
Two reasons.
Firstly, positive human action is expensive.
Secondly, and this is more important, it's unreliable. Any time your safety depends on somebody always sticking to the rules, always remembering to flick a switch, then safety is not assurable. Humans subvert because they disagree, get distracted, make errors, have simple lapses of memory or judgement and so on.
That you can remedy some or all of these problems through lashing together a large management system is one thing. Whether that was the cheapest overall option is another thing entirely.
Mind you, this is all a bit pie in the sky. Apart from Ada (and even then only partly) I'm not aware of an industrial language that fulfills both my requirements and the requirements of SpaceX that I'm pretending can be solved at a stroke. I suspect Rust will be that language. Let's see.
C has the benefit that it's as close as you can get to a WYSIWYG language. There's no VM or garbage handler running behind your back doing god-knows-what at the most inopportune time. You can look at the code and know exactly what instructions it's going to execute, every time.
(Yes the compiler can do some trickery at certain optimization levels but even then, you're able to look at the generated assembly very easily and verify the output you expect to see).
I'm a little surprised they aren't running their own OS with a custom scheduler; I guess the odds of that being bug free vs the odds of running into a Linux bug make it a losing proposition.
Also, the idea that C or even Assembler creates guarantees of stability and predictability is contingent on the CPU design.
But now I am at the limits of my shallow pool of knowledge. The SpaceX stuff demonstrably works; Carmack has done fast control systems in C/C++ and it works. I'm probably making an unnecessary fuss.
GA144, from Green Arrays, is a chip which is very good for space applications - computational power, energy efficiency, predictability, versatility, radiation tolerance... Yet after a year and a half on the market there is still no sensible C compiler for it.
I doubt "C is as close as you can get to WYSIWYG" is always entirely correct.
I would be scared if they weren't using C (or a derivative like C++).
C is a highly deterministic language. It has no "features" per se. If you point to a line of C code, I can tell you with very high certainty what assembly opcode(s) it will compile to. The only thing C does that might be considered a "feature" is memory abstraction, which is kind of important for any large programming project.
Now, if you're trying to advocate using Java or Python or something, you've obviously never worked on embedded software. Not only does any very-high-level language introduce much higher resource requirements, but they are also much less deterministic (which is BAD for spacecraft).
Proper C code is not less stable than any very-high-level language. In fact, there is a lot less that could go wrong.
I wouldn't be supplied if they used MISRA [1]. It can be enforced just using static analysis too, and IIRC it's good enough for avionics used elsewhere.
The clockspeeds on the processors they're using are probably relatively slow. Plus they don't have to worry about retina displays or WiFi or other major power-consumers in today's devices... I bet the overall consumption isn't that bad.
You bet. The problem of getting to orbit was solved "somehow" in 1950's, with emphasis on reliability, then terminal control optimized the result some decades later, when the hardware became available... But the basic task is still way below capabilities of even modest modern computers. Space X may afford to have quite a bit of redundancy.
I imagine that if you are going into space, finding energy to run the computers should not be that hard. I am not sure about the falcon, but I know many jet planes simply attach a generator to the turbines. According to http://airandspace.si.edu/exhibitions/attm/a11.jo.fc.1.html , both Apollo and Gemini got power from fuel cells.
I have been told by aerospace engineers that when designing airplanes, you really don't have any extra anything, including energy. The avionics people have to lobby for as much energy as they can get, and try not to use too much.
I don't know if that's still true for space stuff... probably.
The problem is not the energy ... but the weight you need to lift to get that energy airborne. We don't send astronauts in paper aircraft although they are light - we put layer. There are some things that you need - you need them and you get them. If you need 3 x everything = you put them in. It is you engineering duty to make them best, lightest, coolest etc ... but you cannot cut corners.
If it was up to me though I would just create some of the external parts of the vehicle as a thermocouple and use the fact that one sight is frying on the syn briefly and the other is exposed into the almost absolute zero. That should create some juice. But I suppose there are good reasons they don't do it.
I recall hard realtime as being defined by an answer being worthless if it is late. If you are rocketing through the air, you can fire your rockets a few msec late, and as long as you compensate later nothing will break.
"The Byzantine generals' algorithm is used to handle situations where the computers do not agree. That situation could come about because of a radiation event changing memory or register values, for example."
This always got me wondering: what happens if the algorithm used for handling that is itself affected by a radiation event? Is that just too unlikely because such few code is executed? Or what if the computer in charge of verifying that the other computers do come up with a correct answer is itself dying, isn't it a SPOF?
I think the point is that all the redundant computers check on eachother, and it is very unlikely for the majority of computers to have the exact same fault at the exact same time.
Multi-version programming[1] (independent implementations of the same specification) is one of the classic solutions to this problem. Likewise for power, location, etc. If you really care about these failure modes, you'll have N different designs of PSU & hardware fed via redundantly pathed links, etc.
Aside from the (huge) cost/dev time, the biggest issue is that you still can't protect against logic errors in the specification, and the difficulty in testing every sequence of failure modes across implementations.
And for those who think the link is unrelated spam, it's not.
Description provided on spinroot.com: "Spin is a popular open-source software tool, used by thousands of people worldwide, that can be used for the formal verification of distributed software systems. The tool was developed at Bell Labs in the original Unix group of the Computing Sciences Research Center, starting in 1980."
Generally speaking, BGA solutions to fault-tolerance work by distributing everything across multiple computers. So every computer compares results with every other computer, and if a minority of computers find themselves in disagreement with a majority, the computers in the minority adopt the stance of the majority.
I don't believe this addresses the point the OP was trying to make. There is an algorithm or just a simple piece of code which does the distributing, what safeguards this algorithm?
Another way of putting it is "who watches the watchers?".
That's the whole point. There is no central authority; all computers are on the same level. Each computer does the calculations independently, and then they compare results. The computers in the majority either get the minority computers to accept the results or they somehow override the minority computers. I'm not sure how they negotiate, for example, low-level hardware access, but that's just an implementation issue.
Take a look at the Bitcoin protocol. It's a very impressive example of many different computers agreeing upon something precisely, despite the fact that many parties have a vested interest in disrupting the Bitcoin network.
> They have tried various techniques for estimating time requirements, from wideband delphi to evidence-based scheduling and found that no technique by itself works well for the group. Since they are software engineers, "we wrote our own tool", he said with a chuckle, that is a hybrid of several different techniques. There is "no silver bullet" for scheduling, and it is "unlikely you could pick up our method and apply it" to your domain.
It so happens that I'm working on a tool that amongst other things would allow combined PERT 3-point estimates and Delphi Wideband estimates.
However the most important lesson in estimating is: do not rely on one estimation method. Ever. Use as many as you can. For high stakes estimates, try to have at least one of each of the 4 main classes of estimate: judgement, analogical, parametric and decomposition/recomposition. My tool fits in the 4th category, which is IMO currently underserved.
Those of you in the machine learning world will recognise the vibe of ensemble learning.
Normally the biggest challenge for such software testing is formal testing methods. You cannot just keep on randomly testing every bit of input. Hence, you need to put formal proofs to get rid of that last shred of doubt about whether the software can fail.
> Linux runs everywhere at SpaceX,
> he said, on everything from desktops
> to spacecraft.
Yet every time I've seen them advertise for sysadmin sysadmin or programmer positions the indications are that at least all their internal network and website run heavily on Microsoft software, but their actual spacecraft use Linux/embedded.
It would be interesting to get an actual overview of what they use Linux for, and what they don't.
From the conclusion:
This study has shown that embedded space software are difficult to analyze due to non linearity (mainly in quaternion computations) and complex control command algorithms involved (e.g., Kalman filter).
It should be noticed that the software architecture which suits static analysis by abstract interpretat ion best is also the more readable one and maintainable one. This technique can thus be a metrics of good architectures. In spite of these difficulties, abstract interpretation techniques can greatly improve the quality of space embedded software.
* Qualification of the Atomated Transfer Vehicule (ATV) Flight Control
60 comments
[ 492 ms ] story [ 197 ms ] threadI remember reading that they cannot use exceptions and have to handle every possible scenario. Part of me wonders how much of the source code is just error handling.
SpaceX's programming rules are probably very similar to those used at NASA JPL: http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf
This article is often referenced for NASA's software practices, although it's now almost 20 years old: http://www.fastcompany.com/28121/they-write-right-stuff
Is there anything more comprehensive and current than that?
Most apps have error handling code taking up what? 20-30% of the code at the most? For some reason I imagine this stuff being almost 70% error handling but I am not sure if that is realistic.
So, assuming there are shed loads of error handling that knocks on to everything else about the system. How do they test it? How do they spec out all the possible conditions? What do they do differently to someone writing a SaaS, Desktop app or IOS app?
It looks like it would be a very different world which is not really written about (Apart from the old articles posted in one of the above comments)
I work mostly on integration code. I'd say I see more like 60% code to handle errors, exceptions, etc.
I work in a FreeBSD-derived kernel in areas related to the buf / caching subsystem, which probably has a lot of similarities to pre-2.6 linux (they have diverged more since the 90s). I don't know that I can quantify it, but 20-30% feels like a low number.
> So, assuming there are shed loads of error handling that knocks on to everything else about the system. How do they test it?
One thing we use to test error-case handling is "fail points" — sysctls usable from unit tests that trigger some fault condition. These aren't perfect — they are manually added to code, and because of this, coverage is fairly low — but they're a start.
> How do they spec out all the possible conditions? What do they do differently to someone writing a SaaS, Desktop app or IOS app?
Good questions :-).
"The rocket is all C++
The rocket and spacecraft are all C++. On the ground, we use National Instruments LabVIEW extensively." - spacexdevtty [2]
[1]http://www.reddit.com/r/IAmA/comments/1853ap/we_are_spacex_s...
[2]http://www.reddit.com/r/IAmA/comments/1853ap/we_are_spacex_s...
Why is that scary?
You can go a long way to counteracting some of these with automated toolchains.
You can probably go further by using languages which simply eliminate certain classes of error and then having the same level of toolchain elaboration.
That's not to say that C code can't be safe. It can absolutely be made safe. It just costs more, and any system that requires positive human effort is more likely to fail than one that doesn't.
Suppose you have an enum:
And a switch that runs off that enum: This will compile. (Or maybe it won't, I haven't cut C for some time now).But you've missed the ROCKET_FAULT case. In languages which check for case completeness, this kind of logical construction would cause a compiler failure. ML, F#, Rust etc will all complain that you haven't addressed all cases.
Sometimes this or something like it is added to a code template:
Which is defensive code that's great for test. But not as great for rockets. Better if bad code simply can't be written.I believe static analysis tools can now pick up on missing cases, but there are still lots of reasons why C can't be as fully analysed as a language like ML, Haskell, ATS, Rust etc can be. Putting aside the obvious problem of undefined behaviour meaning you really want to push C code through multiple compilers and multiple static analysis tools, there's also the great universal escape hatch for C: direct memory access.
When you can simply go in and change memory, type systems and analysis are strictly speaking no longer going to work without positive human effort to refrain from doing that. Analysis can only make guarantees under certain assumptions; introduce direct memory access and all bets are off.
Yes, discipline and coding standards can also cut this down. Some analysis tools will do partial analysis of memory accesses. But it still requires positive human action. A computing system includes the humans who make it, run it and use it. Cutting down on the avenues for mistakes is a good thing.
I'm ambivalent about whether to have default cases. The assert(FALSE) trick is still useful for catching missing breaks in the final case.
I might not understand what you mean regarding positive human action when talking about using static analysis tools -- are you referring to tools that require a manual process to run and evaluate, rather than having your tools outright fail to produce a program if static analysis isn't completely happy with the source code?
The classic example in C/C++ is avoiding buffer overflow defects. If you code naively to the language, they will creep in. Additional effort is require to apply policies and procedures to prevent such errors from occurring -- enabling warnings, using static analysis, using particular libraries like BString and so on. Further effort is required to ensure compliance.
I use the term "positive" by analogy with legal positivism, which is (very roughly) that law is created by legislative action and doesn't exist until that has occurred. Similarly, many kinds of safety in C don't exist until you have taken that positive step to introduce additional safeguards.
In languages with a more complete view of strings, all of this additional activity is unnecessary. Positive human effort is not required to prevent buffer overflows in such languages. No new procedures, policies, libraries or tools need to be introduced or mandated. The system's baseline configuration is already safe against that class of errors.
Why does this matter?
Two reasons.
Firstly, positive human action is expensive.
Secondly, and this is more important, it's unreliable. Any time your safety depends on somebody always sticking to the rules, always remembering to flick a switch, then safety is not assurable. Humans subvert because they disagree, get distracted, make errors, have simple lapses of memory or judgement and so on.
That you can remedy some or all of these problems through lashing together a large management system is one thing. Whether that was the cheapest overall option is another thing entirely.
Mind you, this is all a bit pie in the sky. Apart from Ada (and even then only partly) I'm not aware of an industrial language that fulfills both my requirements and the requirements of SpaceX that I'm pretending can be solved at a stroke. I suspect Rust will be that language. Let's see.
(Yes the compiler can do some trickery at certain optimization levels but even then, you're able to look at the generated assembly very easily and verify the output you expect to see).
I'm a little surprised they aren't running their own OS with a custom scheduler; I guess the odds of that being bug free vs the odds of running into a Linux bug make it a losing proposition.
Also, the idea that C or even Assembler creates guarantees of stability and predictability is contingent on the CPU design.
But now I am at the limits of my shallow pool of knowledge. The SpaceX stuff demonstrably works; Carmack has done fast control systems in C/C++ and it works. I'm probably making an unnecessary fuss.
I doubt "C is as close as you can get to WYSIWYG" is always entirely correct.
Unless you are talking about embedded processors or old 8 and 16 bit processors, this is no longer true in modern architectures.
C is a highly deterministic language. It has no "features" per se. If you point to a line of C code, I can tell you with very high certainty what assembly opcode(s) it will compile to. The only thing C does that might be considered a "feature" is memory abstraction, which is kind of important for any large programming project.
Now, if you're trying to advocate using Java or Python or something, you've obviously never worked on embedded software. Not only does any very-high-level language introduce much higher resource requirements, but they are also much less deterministic (which is BAD for spacecraft).
Proper C code is not less stable than any very-high-level language. In fact, there is a lot less that could go wrong.
Unless their static analysis tools just make C or C++ look like Ada.
[1] : http://en.wikipedia.org/wiki/MISRA_C
Granted, this might explain Richard Garriot fiddling with space companies, and John Carmack manufacturing space engines!
If I was rich I would do space research too!
Also, I must be a software engineer, since I don't like Justin Bieber either.
I don't know if that's still true for space stuff... probably.
If it was up to me though I would just create some of the external parts of the vehicle as a thermocouple and use the fact that one sight is frying on the syn briefly and the other is exposed into the almost absolute zero. That should create some juice. But I suppose there are good reasons they don't do it.
In the case of station, satellite or probe, solar panels are generally enough.
If spacecraft avionics doesn't have hard realtime requirements what does ?
I got the impression the article was talking about the totality of avionics software run on the spacecraft, perhaps that impression is inaccurate.
This always got me wondering: what happens if the algorithm used for handling that is itself affected by a radiation event? Is that just too unlikely because such few code is executed? Or what if the computer in charge of verifying that the other computers do come up with a correct answer is itself dying, isn't it a SPOF?
(curious mind wants to know)
It's quite likely actually.
Do you do your backups to an identical* computer right next to your main one? (* factor in wear)
Aside from the (huge) cost/dev time, the biggest issue is that you still can't protect against logic errors in the specification, and the difficulty in testing every sequence of failure modes across implementations.
[1] https://en.wikipedia.org/wiki/N-version_programming
Description provided on spinroot.com: "Spin is a popular open-source software tool, used by thousands of people worldwide, that can be used for the formal verification of distributed software systems. The tool was developed at Bell Labs in the original Unix group of the Computing Sciences Research Center, starting in 1980."
[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.164...
Another way of putting it is "who watches the watchers?".
Take a look at the Bitcoin protocol. It's a very impressive example of many different computers agreeing upon something precisely, despite the fact that many parties have a vested interest in disrupting the Bitcoin network.
It so happens that I'm working on a tool that amongst other things would allow combined PERT 3-point estimates and Delphi Wideband estimates.
However the most important lesson in estimating is: do not rely on one estimation method. Ever. Use as many as you can. For high stakes estimates, try to have at least one of each of the 4 main classes of estimate: judgement, analogical, parametric and decomposition/recomposition. My tool fits in the 4th category, which is IMO currently underserved.
Those of you in the machine learning world will recognise the vibe of ensemble learning.
It would be interesting to get an actual overview of what they use Linux for, and what they don't.
[1] http://www.reddit.com/r/IAmA/comments/1853ap/we_are_spacex_s...
http://www.ni.com/labview/os-support/
* Space Software Validation using Abstract Interpretation (2009)
http://www.di.ens.fr/~rival/dasia09.pdf
From the conclusion: This study has shown that embedded space software are difficult to analyze due to non linearity (mainly in quaternion computations) and complex control command algorithms involved (e.g., Kalman filter).
It should be noticed that the software architecture which suits static analysis by abstract interpretat ion best is also the more readable one and maintainable one. This technique can thus be a metrics of good architectures. In spite of these difficulties, abstract interpretation techniques can greatly improve the quality of space embedded software.
* Qualification of the Atomated Transfer Vehicule (ATV) Flight Control
ftp://ftp.elet.polimi.it/outgoing/Marco.Lovera/ESAGNC08/S01/01_Clerc.pdf
A lot of information about the test process, the usage of Hadware-In-the-Loop and Monte Carlo testing.
* Requirements review, Needs for launchers, space vehicles & orbital infrastructures (2006)
http://microelectronics.esa.int/conferences/ngmp2006/D2-1200...
High-level requirements for On-Board Computer (OBC).
Is that for real, or tongue-in-cheek?