Red Echo

July 30, 2015

Trindle kernel interface exploration

A computer’s fundamental resources are blocks of memory, interfaces to other pieces of hardware, and (for a portable device) a supply of battery power. An operating system’s fundamental job is to allow a computer to run more than one program at a time by dividing those resources among them in some fashion consistent with the priorities of the machine’s owner. The design of an OS kernel therefore begins with its mechanisms for allocating resources to specific programs and the interface through which it allows programs to manipulate them.

The fundamental tool of permission management is the MMU, and the MMU’s finest granularity is the 4K page, so we’ll give each system object a unique page-aligned address.
typedef void *object_t;

The operations a process may apply to an object are defined by an array of permission bits; an object may inspect an object address to find out what it can do.
enum permission_t {
  PERMISSION_READ = 1, // can supply data
  PERMISSION_WRITE = 2, // can receive data
  PERMISSION_EXECUTE = 4, // contains machine code
  PERMISSION_DIRECT = 8, // backed by physical storage
  PERMISSION_PIPE = 16 // contains a transfer queue
permission_t inspect(object_t obj);

A buffer is a contiguous group of writable pages beginning at its identifying address, which will have PERMISSION_READ|PERMISSION_WRITE|PERMISSION_DIRECT.
typedef object_t buffer_t;

Allocate a range of address space as a new buffer. Each page will be mapped against the zerofill page and reassigned to physical storage when it receives its first write.
buffer_t allocate(size_t page_count);

Truncate the buffer down to some number of pages, splitting the remaining pages off as a new, independent buffer and returning its address.
buffer_t split(buffer_t buf, size_t page_count);

Move the contents of these buffers into a new, contiguous buffer, releasing the original buffers in the process.
buffer_t join(buffer_t head, buffer_t tail);

Copy a range of pages into a new buffer; the source address must be page-aligned but may come from any region where the process has read permission.
buffer_t copy(void *source, size_t page_count);

A shared resource is an immutable buffer, which means that it can be owned by more than one process at a time. It offers PERMISSION_READ|PERMISSION_DIRECT.
typedef object_t resource_t;

Create a new shared resource by cloning the contents of an existing mutable buffer.
resource_t share(buffer_t data);

One process may communicate an object to another by transmitting it through a pipe. Unless the object is a shared resource, this transfers ownership from the sender to the receiver, and the object is removed from the sender’s access space. The pipe contains a queue, allowing communication to happen asynchronously.

An output is the end of the pipe you send objects into. It has PERMISSION_PIPE|PERMISSION_WRITE.
typedef object_t output_t;

Transmit a list of objects, one at a time, until they are all sent or the pipe’s queue has filled up. Returns the number of objects which were successfully transmitted.
size_t transmit(output_t dest, const object_t objs[], size_t count);

An input is the end of the pipe you receive objects from. It offers PERMISSION_PIPE|PERMISSION_READ.
typedef object_t input_t;

Receive objects from the pipe until its queue empties or the destination array fills up, then return the number of objects which were received, if any.
size_t receive(input_t src, object_t objs[], size_t array_size);

Allocate a new pipe able to queue up a certain number of elements, populating the variables pointed at by in and out with the pipe’s endpoint objects.
void pipe(size_t entries, input_t *in, output_t *out);

Close a pipe by releasing its input or output. The object representing the pipe’s other end will lose PERMISSION_READ or PERMISSION_WRITE and retain only PERMISSION_PIPE.

An executable is a shared resource which contains machine code. Since it is an immutable shared resource, it can be owned by more than one process at a time. It offers PERMISSION_EXECUTE|PERMISSION_DIRECT.
typedef object_t executable_t;

Create a new executable by cloning the contents of an existing shared resource.
executable_t prepare_code(resource_t text);

Create a new process in suspended state, configure its saved instruction pointer and stack pointer, and assign it ownership of some objects (thereby releasing all but the shared resources, as usual). The process will begin executing when the scheduler next gets around to granting it a timeslice and “resuming” it.
void launch(object_t bundle[], size_t bundle_count, void *entrypoint, void *stack);

Delete the current process and release all of its resources.
void exit();

Suspend the process until an empty input starts to fill, a blocked output starts to drain, a pipe closes, or a certain number of milliseconds have elapsed. If woken by an event involving a pipe, the call will return the relevant input or output, otherwise it will return zero.
object_t sleep(uint64_t milliseconds);

I’m starting to lose track of all the Trindle draft documents I’ve written, rewritten, replaced, and abandoned, scattered as they are across three laptops, my home desktop, and a remote server. This is either my fifth or sixth attempt at a concrete design for the system interface, but it’s the first time I’ve made it all the way through without discovering a fatal flaw, and that feels like progress.

July 27, 2015

This simple structure, made of rope and 2x4s, looks like a cozy little minimalist Burning Man hangout: it supports three hammocks and can be covered in tarps for shade. Author quotes $42.60 in materials.


July 21, 2015

Chrysler vehicles vulnerable to remote exploit

I’ve been joking for years that I refuse to drive a car that has a computer in it, because I’m a software engineer and am therefore unable to trust any system other software engineers have ever touched.

Except I’m not entirely joking. I really like my old-fashioned, non-upgradeable, non-networked, CAN-bus-free classic Range Rover, and part of the reason I am happy to keep on paying its hefty repair and maintenance bills is that I don’t have to worry that its 20-year-old electrical systems are vulnerable to control by malicious external agents like hackers or federal agents:

The Jeep’s strange behavior wasn’t entirely unexpected. I’d come to St. Louis to be Miller and Valasek’s digital crash-test dummy, a willing subject on whom they could test the car-hacking research they’d been doing over the past year. The result of their work was a hacking technique—what the security industry calls a zero-day exploit—that can target Jeep Cherokees and give the attacker wireless control, via the Internet, to any of thousands of vehicles. Their code is an automaker’s nightmare: software that lets hackers send commands through the Jeep’s entertainment system to its dashboard functions, steering, brakes, and transmission, all from a laptop that may be across the country.

Motorcycles are even more trustworthy; most of them don’t contain so much as a single microcontroller.

July 20, 2015

Yosemite backpacking

I’m back in Seattle after a week in California. The backpacking trip went well and I am really glad I went. The group was a little smaller than average, but even a small slice of my very large family adds up to a good-sized crowd. Still, it was funny that my mother and I were the only people present who had actually participated in the notorious Disaster Hike – for everyone else it was just a pretty loop among some alpine lakes.

The beginning of the hike was a bit stiffer than we’d anticipated; I’m not sure what the trail builders were thinking, but they had us do a lot of climbing and descending without encountering any notable vista or any other apparent justification. Once we reached Crescent Lake, however, the loop was steady and smooth.

Mom, AJ, Abigail, and I all scrambled up Buena Vista Peak as the trail crossed its shoulder, yielding a glorious panoramic view of the southern park, a perspective I’ve never seen before. We camped that night by Buena Vista Lake, peaceful and quiet, with a beautiful glowing sunset rolling across the granite; I’ve never seen waves on a lake reflecting quite so distinctly orange and blue.

We had planned to find an unmaintained cross-country trail leading from the main trail past Hart Lakes over to Ostrander Lake, but after looking at the terrain from atop Buena Vista, decided it would be easier and more fun to bushwack across Horse Ridge instead. This started out as a ridiculously pleasant walk through a spacious forest, but once we reached the crest of Horse Ridge we discovered that the far side is a precipice, not shown on our maps. With a bit of exploring we found a steep but workable ravine cutting through the sheer face, however, and after a little work we got everyone down and across to the Ostrander Lake bowl.

Oh, such a lovely day that was, and so satisfying to dip our feet in the water!

AJ and I weathered the trip with ease; you know you’ve got something good when the relationship-maintenance work flows so easily and automatically that it doesn’t even feel like work.

July 12, 2015

I’m on my way to California for a week’s backpacking in Yosemite with my family. It is the 25th anniversary of the “disaster hike” notorious in family lore, so we’re going to revisit the trail and see if we can do it a little more successfully this time. I will therefore be completely unable to communicate with anyone not in the immediate backpacking group until some time late Friday.

July 9, 2015

I’ve had a concept for an operating system bouncing around my head for a decade and a half or so. With the exception of a general affinity for exokernels, the structure I’m thinking about now bears no resemblance to anything I considered back in the ’90s, but on the basis of arbitrary convenience I’m going to say that this Ship of Theseus is, in fact, still the same boat. The current incarnation lives in a series of C header files named “trindle.h”, “trindle2.h”, “trindle3.h”, und so weiter, documenting the kernel API, which is the only part that actually exists.

I have at various times written all of the individual components necessary for an operating system, though if one were to imagine them all glommed together it would be form one unholy mongrel with no particular reason to exist. The Trindle concept is rather an attempt to answer the same sorts of questions I was exploring with the Radian language. Observing that all of the interesting problems in computing currently have to do with asynchrony and distributed processing, immutability has become a prominent and valuable tool: but “immutability” is really just a way of describing the way objects look when your tools require you to be explicit about the whens and hows of the changes you are making to observable state.

Trindle is therefore not a Unix: it is a single-user, single-address-space, capability-based, filesystem-driven architecture which may well end up offering a POSIX API but only as a secondary concern should it happen to be practical. It does, however, retain all the familiar notions of independent processes, protected memory, virtual memory, and the stdin/stdout/argv/envp conglomeration necessary for operating C programs.

The capability system works by attaching a list of inodes to each process. A process may read from those objects and no others; it doesn’t matter what sort of path-mangling shenanigans you get up to or what other subprocesses you launch, there is simply no way for a process to refer to any file not granted by its upstream launching process.

To be more precise, permission to open a read stream from an inode is a capability attached to some other stream. A stream is an interface to one end of a pipe connecting two processes; the upstream process can send data through the pipe, and can also attach permission to access some object it knows about.

A process may generate a new pipe either by forking or by loading an executable image. This pipe is itself a new file, which can be opened and read, or can be sent down an output stream so that some downstream process can read from it.

The only difference between an executable and a file is that the executable does not yet have an input stream, while the file does. To be solved: memoization and lazy computation of file contents.

Since processes cannot alter existing files, merely read from them, how do you actually get any work done? I’m imagining that the shell would be a process which reads from various processes representing user-interface devices and then pipes the filesystem root through various programs as the user requests. Changes would be made by generating a new directory tree as appropriate.

But that seems like a lot of copying and replacement. I think this system needs some sort of “log” object, preferably one which can merge writes from multiple inputs. A directory could thus be represented by a series of mutations, so that inserting a new file or deleting an old one just involves appending a log entry recording the fact, with periodic writes of a new summary of the current state.

The equivalent of a user’s home directory would then be something like an activity log, recording the various files the user has created, with an index of their names. The user can pass these files through various programs in order to generate new files, which can either live along side the originals under new names, or which can replace the originals by redefining their names.

Since the only way to gain access to a file is to be given it by the upstream process, the user is therefore in complete control over which programs get to see which files. If you don’t want a program to have access to your contact list, you simply don’t give it a pointer to your contact list, and that’s that – there is no mechanism by which it can name that file, ask for access to it, or raise its privilege level in order to read it. Nor can any program alter your files for you; programs merely generate files, and it is up to you, through the shell, to put the results where you want them.

I’m not sure whether I will ever actually build this thing, but it’s been an interesting concept to chew on while riding the bus or laying in bed unable to sleep.

July 8, 2015

High tech tuxedo shirt for musicians

A startup called Coregami has introduced a tuxedo shirt for symphony musicians using modern, wicking, machine-washable four-way-stretch material and a raglan sleeve for less restriction of shoulder movement. I would wear one of these, and $120 is a totally reasonable price.

July 7, 2015

Happy weekend

I spent Fourth of July weekend at Goodness, a 150-person campout on the Green River. It’s a happy, relaxed event with big trees, lots of kids, potluck dinners, swimming, and (of course) dancing all night under the stars. My burner friends have this party logistics business dialled in, and the festival flowed smoothly as the river’s current. Load-out and MOOP check on Sunday went so quickly that I felt like complaining that there was not enough work to do!

I had to restrain my ego somewhat because we used the PA system I bought a few weeks ago and it sounded ABSOLUTELY AWESOME. I mean, WOW. The sound was gorgeous – bigger, louder, and cleaner than I had expected – and I just wanted to bounce around with glee. So much fun, and I could not stop dancing. There is nothing else in the world like the luxurious glory of dancing til dawn in a wide-open grassy meadow with a couple dozen of your friends as the music rolls along like some enormous machine and the sun starts to peek up through the trees.

We’ll be bringing an even more impressive system out to Floodland next month, once Danne and Erik finish building their Danley-style tapped horn subs. I’m told to expect purple glitter sparkles. Perfect.