Writing Code for Spacecraft

CowboyRobot writes "In an article subtitled, "And you think *your* operating system needs to be reliable." Queue has an interview with the developer of the OS that runs on the Mars Rovers. Mike Deliman, chief engineer of operating systems at Wind River Systems, has quotes like, 'Writing the code for spacecraft is no harder than for any other realtime life- or mission-critical application. The thing that is hard is debugging a problem from another planet.' and, 'The operating system and kernel fit in less than 2 megabytes; the rest of the code, plus data space, eventually exceeded 30 megabytes.'"

Comments

hmm...

[opqdonut]

I wonder will they be releasing the source. It could be an interesting read.

Re:hmm...

[The Vulture]

Yes, and seeing as I'm currently working with embedded Linux, I can honestly say that it's a pain. (Note: I must preface this by saying that I am using Linux 2.4.18 for MIPS and my company is not using any sort of real-time extensions, just the bare 2.4.18 tree).

You get what you pay for... I've used VxWorks for a few years now, and while it does have it's share of problems, and while they are sometimes difficult to deal with, it is a great platform for development. You get much better control of the system as opposed to Linux (the main problem with using Linux in an embedded environment is the user to kernel relationship. It's solved neatly in vxWorks by getting rid of it (everything is in kernel space)). This works out very nicely for MIPS processors, which I deal with most of the time. Threading (or tasks as vxWorks has) is much better than Linux - you can at least somewhat guarantee when your tasks run, unlike with the default Linux scheduler.

I am very interested in trying QNX out, to see how it compares to vxWorks, one of these days.

-- Joe

hard to imagine..

[Chuck Bucket]

all software has bugs, what happens when 1/2 thru the trip they have an update? who installs remotely, and I guess having a sysop reboot is out of the question...

CBB

Re:hard to imagine..

[Cylix]

They had a section of the flash memory go bad... so they patched a work around for those sectors if I remember correctly.

Re:hard to imagine..

[Vardamir]

Yes, here is an email my OS prof sent our class on the subject:

Subject: What really happened on Mars Rover Pathfinder

The Mars Pathfinder mission was widely proclaimed as "flawless" in the early
days after its July 4th, 1997 landing on the Martian surface. Successes
included its unconventional "landing" -- bouncing onto the Martian surface
surrounded by airbags, deploying the Sojourner rover, and gathering and
transmitting voluminous data back to Earth, including the panoramic pictures
that were such a hit on the Web. But a few days into the mission, not long
after Pathfinder started gathering meteorological data, the spacecraft began
experiencing total system resets, each resulting in losses of data. The
press reported these failures in terms such as "software glitches" and "the
computer was trying to do too many things at once".

This week at the IEEE Real-Time Systems Symposium I heard a fascinating
keynote address by David Wilner, Chief Technical Officer of Wind River
Systems. Wind River makes VxWorks, the real-time embedded systems kernel
that was used in the Mars Pathfinder mission. In his talk, he explained in
detail the actual software problems that caused the total system resets of
the Pathfinder spacecraft, how they were diagnosed, and how they were
solved. I wanted to share his story with each of you.

VxWorks provides preemptive priority scheduling of threads. Tasks on the
Pathfinder spacecraft were executed as threads with priorities that were
assigned in the usual manner reflecting the relative urgency of these tasks.

Pathfinder contained an "information bus", which you can think of as a
shared memory area used for passing information between different components
of the spacecraft. A bus management task ran frequently with high priority
to move certain kinds of data in and out of the information bus. Access to
the bus was synchronized with mutual exclusion locks (mutexes).

The meteorological data gathering task ran as an infrequent, low priority
thread, and used the information bus to publish its data. When publishing
its data, it would acquire a mutex, do writes to the bus, and release the
mutex. If an interrupt caused the information bus thread to be scheduled
while this mutex was held, and if the information bus thread then attempted
to acquire this same mutex in order to retrieve published data, this would
cause it to block on the mutex, waiting until the meteorological thread
released the mutex before it could continue. The spacecraft also contained
a communications task that ran with medium priority.

Most of the time this combination worked fine. However, very infrequently
it was possible for an interrupt to occur that caused the (medium priority)
communications task to be scheduled during the short interval while the
(high priority) information bus thread was blocked waiting for the (low
priority) meteorological data thread. In this case, the long-running
communications task, having higher priority than the meteorological task,
would prevent it from running, consequently preventing the blocked
information bus task from running. After some time had passed, a watchdog
timer would go off, notice that the data bus task had not been executed for
some time, conclude that something had gone drastically wrong, and initiate
a total system reset.

This scenario is a classic case of priority inversion.

HOW WAS THIS DEBUGGED?

VxWorks can be run in a mode where it records a total trace of all
interesting system events, including context switches, uses of
synchronization objects, and interrupts. After the failure, JPL engineers
spent hours and hours running the system on the exact spacecraft replica in
their lab with tracing turned on, attempting to replicate the precise
conditions under which they believed that the reset occurred. Early in the
morning, after all but one engineer had gone

Re:hard to imagine..

[AaronW]

As someone who's worked with VxWorks for the last several years I'm surprised they didn't turn on priority inheritance to begin with for the semaphore. As a rule, we usually turn on priority inheritance for our mutex semaphores.

Other problems in the Mars Pathfinder were related to using the VxWorks filesystem. VxWorks basically only supports FAT on top of flash. For flash, FAT is a poor choice since some areas of the disk like the root directory and FAT tables will quickly wear out. Also, I don't think VxWorks has much support for working around bad sections of flash.

As far as VxWorks memory allocation support, in an ideal world one would statically allocate all memory, but oftentimes things are not ideal. In the product I work on, we have to have dynamic memory allocation, since depending on how the product is being used at the time, different data structures are required with no way of knowing beforehand how many of a particular type are needed, and this changes dynamically. For a simple device, it's easy to statically allocate everything, or if you have enough memory where you can statically allocate everything.

In our case, while we statically allocate memory where we can, however, in many cases we cannot. For example, I have to maintain a data structure keeping track of all of the network gateways connected to an output interface. We can have many thousands of gateways and thousands of output interfaces. There could be anything between one and thousands of gateways on an interface. In this case, I use static arrays for information on each gateway and each output interface, but must use dynamic data structures to list all the gateways connected to an output interface. It would be prohibitive to allocate storage for 30,000 gateways with 30,000 interfaces! I also can't use a linked list of gateways per interface since it doesn't scale, a linked list having access time O(n).

Also, we use third party libraries that perform dynamic memory allocation and it would be prohibitive to change that.

By replacing Wind River's malloc code with Doug Lea's code we eliminated fragmentation problems and saw our startup time jump from 50 minutes to 3 minutes. Doug Lea's malloc code is the basis of malloc in glibc and is very effecient. We also added support for tracing heap memory allocations to keep track of which task allocated a block and where it was allocated. This alone helped tremendously in tracking down a number of memory leaks since we can just walk the heap and see exactly where all the memory is being allocated. This is a sorely missing feature in VxWorks.

The lack of memory protection is another major problem for complex tasks. We have a bug we've spent weeks trying to track down the cause without any luck where random memory locations get corrupted.

Needless to say, all new projects where I work will not run on VxWorks. All of the chip vendors we're looking at are either dropping support for it or have already dropped it and are focusing on Linux.

BTW, this is one feature I would *REALLY* love to see added to Linux. The company I'm working for is looking at writing our next generation platform on top of an embedded Linux. We have not yet decided which one to use, but want something 2.6 based.

With priority inheritance, if a mutex is held by a low priority task and a high priority task tries to grab it, the low priority task is automatically boosted to the highest priority task that has attempted to acquire the semaphore. When the semaphore is released, the low priority task's priority is restored.

Some other nice features are interrupt scheduling and better priority based message passing support (which may already be present, I'm still looking into this).

Finally, one very useful feature would be the ability to guarantee a real-time thread a certain percentage of the CPU, with the option of placing a hard limit if it tries to exceed that or temporarily lowering it's priority to non-realtime so as to not starve no

Re:hard to imagine..

[GileadGreene]

You are confusing Mars Pathfinder (a 1997 mission, which suffered a priority inversion problem) with Mars Exploration Rover (a 2003-2004 mission which suffered a file allocation issue in Flash memory, and the subject of TFA). Although both used VxWorks.

Re:Efficiency

[Omicron32]

That's all well and good, but don't forget that this kernel only has to interface with one set of hardware.

Things like the Linux kernel has to know about hundereds and thousands of different devices which is why it's so big.

Carmack

[mfh]

I would like to think that this article embodies the reasons that John Carmack got into space program development to begin with.

In the beginning he got into 3d game applications for a similar reason. The cutting edge is always the very outer area of human development, and Carmack makes a good example of a programmer who has taken aim at the edge of what is known to programmers. Maybe Mr. Carmack would care to comment?

Much like how Id Software develops engines, the space craft programming is new an innovative, although the difference is that space craft have systems have no room for error.

Re:Efficiency

[UncleScrooge]

I can get Linux on a 1.44mb floppy and run a system from it. 2 megs ain't that hard.

Re:Efficiency

[Armchair Dissident]

I used to write embedded applications using OS-9 (NOT MacOS 9) on 68000-based systems as a sub-contractor for Nuclear Electric (nuclear power stations company in the UK before it became BNFL). Our development system - complete with OS/Kernel and compilers - had only about a meg of memory; the final embeded systems often only had 512K if we were lucky

Okay, so this was some 14 years ago - but it was doing a lot of work. 2 megabytes is a lot of memory! There's a phenomenal amount of code and data that can be stored in 2 meg. Maybe it's good by current standards, but - personally - I would suggest that current standards is a bad place to start from.

Re:Will they quit using FAT?

[xhispage]

Well , beta testing , anyone ? :-D

Re:Wait a minute?

[cpghost]

I would pick something like Qnx or NetBSD for any critical app

Okay, let's turn NetBSD into a real-time OS. Add some "hardening" features like watchdogs etc. Hmm... what should we call it? Perhaps: SpaceBSD?

my satellite debugging experience

[nil5]

I worked on a satellite mission where we had some trouble. Due to an error the satellite wound up pointing 16 degrees away from the sun in a higher-than-expected orbit of 443 miles (714 kilometers) above Earth.

The misalignment meant the spacecraft was unable to look directly at the sun's center to record the amount of radiation streaming toward Earth. To accurately measure sunlight, the darn thing needed to be pointed to within a quarter of a degree of dead center.

It took about four and a half months to fix that problem, due to uplink difficulties. Ground controllers from first had to slow the spacecraft's spin in order to transmit a series of software "patches" and then gradually speed it up to see how well the commands worked.

Then things were fixed.

Moral of the story: it is a tough job indeed!

mutex's always cause trouble

[hey]

In my experience mutex's, semaphores, etc always cause trouble. There is nearly always another way to write things.

And you'll never ever seem me coding an infinite wait for a mutex. That's just asking for trouble.

Bad: in Windows, FindNextChangeNotification()
requires those IPC operations and I always gives me grief.

Good: The Linux File Activity Monitor (FAM). Lets you open and read a pipe of actions. Nice!

Debugging in space: a case for dynamic systems.

[voodoo1man]

In 1998-2001, the JPL successfuly flew the Deep Space 1 spacecraft. One of the systems on board was the Remote Agent, a fully autonomous spacecraft control and guidance system. The software was written entirely in Common Lisp, and parts were verified in SPIN (there is an interesting paper written on the verification process, along with an informal account by one of the designers), which yielded the detection of several unforeseen race conditions. The parts that were not verified were thought to be thread-safe, but unfortunately this proved mistaken as a race condition occured in-flight. With the help of the Read-Eval-Print Loop and other Lisp debugging facilities, the bug was tracked down and fixed in less than a day, and Remote Agent went on to win NASA's Software of the Year Award.

Perhaps not surprisingly for anyone who has heard about the management at NASA, C++ was selected for the successors to the Remote Agent on the grounds that it is supposed to be more reliable (this despite the fact that the Remote Agent was originally to be developed in C++, an effort that was abandoned after a year of failure). This caused more than a few people to be upset (including a very personal account by one of the aforementioned designers). Clearly the debugging facilities of Common Lisp are far superior to static systems like C++, something which is very useful in diagnosing unexpected error conditions in spacecraft software (read the first question on p. 3 of the interview to see what pains the JPL staff went through to adapt similar, ad-hoc methods to VxWorks). It's also clear from this interview (question: "How is application programming done for a spacecraft?" Answer:"Much the same as for anything elsesoftware requirements are written, with specifications and test plans, then the software is written and tested, problems are fixed, and eventually its sent off to do its job.") that NASA has in no way tried to adapt formal verification methods for it's software, prefering instead to rely on the "tried and true" (at failing, maybe) poke-and-test development "methods."

Clearly, formal verification methods to eliminate bugs before critical software is deployed, and deployment in a system with advanced debugging facilities is a clear win for spacecraft software, and should be adapted as the standard model of development. Unfortunately, like in many other software development enterprises, inertia keeps outdated, inadequate systems going despite a strong failure correlation rate.

Re:Debugging in space: a case for dynamic systems.

[GileadGreene]

NASA has had an active formal methods/formal verification program for a number of years, located at NASA Langley. They mostly do research, but have worked on a few practical applications, mostly in the shuttle program. Additionally, JPL recently (2003) set up the JPL Laboratory for Reliable Software, which is chartered to look into formal verification among other things. The lead technologist in the LaRS is none other than Gerard Holzmann, the man behind SPIN.

Having said all of that, I'll agree that formal verification at NASA is in its infancy, and is facing an uphill battle for acceptance (witness how long the Langley group has been trying to push formal methods). It'll be interesting to see what happens with JPL's LaRS.

Out of curiousity

[FunkSoulBrother]

Why, in the 21st century, is it necessary to fit something like the Mars rover code in 2MB of memory? If something like a Gameboy Advance or a PDA can hold 64MB-a couple gigs, what is holding NASA back, with their gigantic budget and all?

I can't imagine it would be the cost of the memory... I mean I know it costs much much more to make chips to a very strict specification, but if you are already producing so few units, isn't your cost of production going to be extrodinarily high whether you are making 64KB chips or 2MB or even 64MB?

This is not to say that I don't have admiration for fitting all that code in such a small space, but is there a reason they feel the need to do so?

Similar, though terrestrial, problems

[renehollan]

I'll leave out the names to protect the guilty.

About five years ago, I worked for a major test equipment manufacturer who was contracted to deliver a test system for POTS lines (which could eventually do ADSL prequalification) to a national telco in a major European country. The idea was to test every POTS line in the system (millions of them) every night to detect early signs of degradation so repair crews could be dispatched before dialtone was completely lost.

As you can imagine, this involved a distributed system of test heads in each central office, networked back to a central command and control site. The sysem worked well, but had one flaw: downloading new firmware to the test heads was fraught with problems, and often led to the test head "locking up", even though a backup copy of firmware was always present, along with a hardware watchdog timer (though it was possible to lock out the watchdog interrupt, particularly when reprogramming flash, so it was a less than perfect watchdog). In these situations, one had to dispatch a "truck roll" to the affected central office, and replace EPROMs by hand.

Needless to say, the customer was pissed. More worrying was that even if we fixed the software download problem (which we were unable to reproduce in the lab), was that we'd be paying for truck rolls all over the country. This was a not insignificant amount of money.

Management frittered away time, instead of authorizing a root cause analysis, by requesting tweaks to TCP/IP operating parameters, and testing to see if the problem was getting better or worse. This did not prove illuminating, time was wasted, and the customer was getting royally angry.

Finally, a small team of us were permitted to undertake a root cause analysis to find and fix the problem: the engineer responsible for the embedded flash file system, the telecom engineer on the control side, and I: responsible for the embedded O/S, and TCP/IP stack (inherited from the supplier of the embedded O/S). We wanted a month. We got two weeks. Remember, deploying experimental software to live COs requires so many layers of approval, it isn't funny, and we were worried that would be our biggest bottleneck.

Finally, the controller telecom engineer was able to reproduce the problem, by attempting to download software from our controllers to deployed equipment in a single central office (getting permission was a feat in itself -- while there was little danger of affecting telephone service, this was a live CO).

The problem was clear: the data network was slow (9600 b/s over an X.25 PVC, carrying PPP-encapsulated TCP/IP), resulting in the use of large MTUs to minimize packetizing overhead (latency wasn't an issue - throughput was). Because of the way the controller's TCP/IP stack worked, it misestimated the packet/ack round trip time: it used a one byte payload for the first packet, and full MTUs after that. The resulting packet ACK timeout and retransmissions exposed an inconsistency between controller and embedded TCP/IP stacks that caused the embedded system to lock up.

Great. Now, how to fix it?

The fix wasn't a big deal (I implemented a fix in the embedded TCP/IP code since we didn't have source to the controller TCP/IP stack), but deploying it was: remember we couldn't download the code sucessfully, and we didn't want to pay for a truck roll.

At this point, I proposed something daring: download a small patch, in as few packets as possible (we could send three full MTUs safely). which would patch the existing code in place, which would be good enough to reliably download a complete replacement.

The thought of "self-modifying code" freaked management out to no end: it went against every rule in the book. But all three of us stood our ground: the only other alternative was a truck roll to each central office in the country. Reluctantly, we were allowed to proceed with that fix.

At this point, we had about ten days left. I had managed to get approval to pipeline the dev and tes

Re:Marketing crap

[Anonymous Coward]

Well said! And ditto.

I do embedded software for a living as well, and run like heck away from any project involving WindRiver.

WindRiver is great for those people who don't know what they are doing in the embedded space. And it's useful as a red flag for telling one as such.

But for people who actually know what they are doing, and who actually do understand OS's, Linux solutions are a far better choice. The time-to-market is absolutely unbeatable; as well as all the choices that one has in order to get a product out. Plus the reliability is also the best.

Sorry if that sounds like a troll; it's not meant to be. It's just my own first hand experience in this space.

Re:Open source spaceware

[johannesg]

You just don't dump some satellite code onto your PC and "test" it.

Sure you can. We make that kind of software. The reason you won't ever see it as open source is because the various instruments on the spacecraft are covered by confidentiality agreements (or worse, in case of military hardware). And as hardware goes it is typically rather obscure stuff, requiring significant domain knowledge as well to emulate correctly.

Another issue is that these systems are rather CPU-intensive - we have a 16-CPU box for the spacecraft instruments plus a dedicated PC to emulate the flight computer itself. But you could run it on simpler hardware if you are willing to run at less than realtime speed.

Interestingly, the closest we ever get to seeing the actual flight software is binary images of it. While that is a lot closer than most slashdotters are likely to get, it is still far removed from being able to do something useful with it.

Of course the other good reason why this isn't going to be open source is because of price. For details you should really contact a salesperson, but let me give you a clue: (raises little finger to mouth) "Mwuhahaha!" ;-)

NASA may use another OS when...

[Anonymous Coward]

NASA may consider using a new OS after it has finished V&V in house and by an independant testing company (per NASA procedures) and it has flown in space successfully. An order of magnitude estimate is ten times the development cost.

VxWorks is a well known OS with lots of experienced users. Priority inversion is a known problems, just set the SEM_INVERSION_SAFE flag in semMCreate() to fix it.

Besides making the OS, Wind River also sells Tornado(R) and other tools for developing, debugging, and testing embedded realtime code running in the target computer. Anyone who has ever done embedded and realtime code knows good tools are mandatory with any complex system.

VxWorks runs in a flat file space. There is no segment protection, but code does get extensively reviewed and tested so bad pointers are not a problem. Preventing memory fragmentation requires good design, the solutions are will known, and more reviews and testing.

The last time I priced a run time license (most satellites need two licenses), it was noise ($400) compared to the labor required to build a spacecraft.

I a VxWorks user in the space buisness.

_Richard

but a crash shutdown Spirit for two weeks!

[peter303]

It was around the first or second month of operation this year, but Spirit was unusable for a couple of weeks due to an OS failure. The symptom was Spirit tried to reboot itself about 20 times in a row- a default practice if something drastric happens. It was traced (according to the rumor mill) to flash memory overflow. Supposedly the VxWorks file manangement system improperly updated its flash memory free-inode list. So the memory appeared to run out of space.

The nice thing about software is that JPL was able to upload a patch and get both rovers working properly again. They reconfigured the Galileo mission to the bypass the broken high gain attenna and use the hundred times slower low gain attenna with software patches and achieved most of the mission objectives.