The Rover That Could Not Finish Booting — JavaScript Bug Hunt

Briefing

Modelled on NASA's Spirit rover, January 2004: about two and a half weeks after landing on Mars, Spirit stopped sending useful data and kept resetting. The cause was its flash file system — files had accumulated in flash memory, many of them left over from the cruise to Mars, and managing them at boot needed more RAM than the rover had, so every start-up failed. Engineers commanded Spirit to start without using the flash, deleted files and reformatted it.

This reconstruction keeps a directory table in flash and mounts it into a fixed RAM budget at boot. Deleting files and writing new ones slowly makes the table unmountable.

Fix filetable.js so the table can always be mounted.

Bug report

BUG-SOL18 · Priority: Critical · Reported by: flight software

Mounting costs limits.ENTRY_BYTES of RAM per entry in the table, and boot has limits.RAM_BUDGET_BYTES. The table must ALWAYS stay mountable:

• mountBytes() = (number of LIVE files) * ENTRY_BYTES — removing a file frees its entry immediately
• write(name, bytes): overwriting an existing live file returns true and adds no entry; a NEW file is refused (returns false, nothing stored) when the number of live files already equals limits.MAX_MOUNTABLE (= RAM_BUDGET_BYTES / ENTRY_BYTES)
• remove(name) returns true for a live file, false otherwise
• list() returns live names in the order they were (last) created; a name written again after removal goes to the end

Observed: after a few days of create/delete cycles boot.mount reports "out of memory" and the rover resets in a loop.

Logs

[boot] mount flash: need 2048 B, budget 512 B -> out of memory
[boot] reset (attempt 3)
[boot] mount flash: need 2048 B, budget 512 B -> out of memory

The code as shipped

src/flash/filetable.js (editable)

var limits = require("./limits");

exports.create = function () {
  var entries = [];

  function find(name) {
    for (var i = 0; i < entries.length; i++) {
      if (entries[i].name === name && !entries[i].deleted) return i;
    }
    return -1;
  }

  return {
    write: function (name, bytes) {
      var i = find(name);
      if (i !== -1) {
        entries[i].bytes = bytes;
        return true;
      }
      if (entries.length >= limits.MAX_FLASH_FILES) return false;
      entries.push({ name: name, bytes: bytes, deleted: false });
      return true;
    },
    remove: function (name) {
      var i = find(name);
      if (i === -1) return false;
      entries[i].deleted = true;
      return true;
    },
    list: function () {
      var out = [];
      for (var i = 0; i < entries.length; i++) if (!entries[i].deleted) out.push(entries[i].name);
      return out;
    },
    mountBytes: function () {
      return entries.length * limits.ENTRY_BYTES;
    }
  };
};

Read-only context: src/flash/boot.js, src/flash/limits.js.