Chip Overclock

Wireless Remote Sensing with Arduino and Zigbee

2012-01-27T16:26:00.009-07:00

In "Remote Sensing with Arduino" I described how to access light and temperature sensors on an Arduino board over Ethernet via a web server. In this article I'll describe how I've taken the same basic sensor platform and am now accessing it wirelessly via XBee radios.

Xbee is a family of tiny radios made by Digi International and based on Zigbee, the IEEE 802.15.4 standard for personal area networks (PAN) that are characterized by low power (one milliwatt), short ranges (about one hundred feet), and a pretty sophisticated network stack. Zigbee is capable of implementing a wireless mesh network, but the radios and firmware I am using in this application do something much simpler, so simple in fact that it requires no configuration and works right out of the box: a 9600 baud wireless serial connection.

I did this using a SparkFun Xbee Wireless Kit. The kit includes two XBee 2.4 gigaHertz series 1 radio modules, an XBee Arduino shield (some assembly required, so I had to break out the soldering iron to attach the Arduino headers), and an XBee Explorer. The Explorer is a tiny board with a socket for the radio module and an FTDI chip that performs the serial to USB conversions. The Explorer implements the PC/Mac end of the wireless serial connection. The Explorer requires the FTDI Virtual COM Port (VCP) drivers be installed on your PC or Mac. (I've written of my affection for FTDI and the quality of their products before, in "Deconstructing the AR.drone: Part 5".)

Below you can see the new setup. The breadboard at the top has exactly the same sensor setup as before. The Ethernet shield has been replaced on the Arduino board with the red XBee shield. The blue XBee radio module is plugged into a socket on the top of the shield. Jumper wires for power, ground, and the two sensors are plugged into the headers on top of the shield just as they were on the Ethernet shield. The Explorer is to the left with its own blue XBee radio module and a USB cable connecting it to my Mac. Note that there is no USB connection from the Arduino to my Mac; that's just a power cable from a wall wart powering the Arduino board. You could also power the Arduino side with something as simple as a nine volt transistor radio battery.

Here's a side view where you can see the power cable coming into the Arduino, with the XBee shield plugged in on top of it similar to the Ethernet shield.

Here's a closeup of the XBee shield. Near the lower right on the shield you might be able to see a tiny silver surface-mounted slider switch, so small you need a something like a toothpick to throw it. The switch has two positions, labelled DLINE, in which you can load your Arduino board over its USB cable just as you normally would, and UART, in which the XBee hijacks the serial pins on the Atmel ATmega328 so that, for example, whatever your software displays over the microcontroller's serial port goes across the wireless XBee channel instead of the USB cable.

And here's a closeup of the XBee Explorer. It is powered completely off the USB cable connected to my Mac. Although the XBee modules can be configured to do different things, right out of the box they implement a wireless serial connection and automatically pair with one another. Digi refers to this as transparent mode. Under the hood however, the radios are implementing a peer-to-peer network based on a Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) model.

So I loaded the FTDI drivers onto my Mac and restarted it. I plugged the USB cable from the XBee Explorer into my Mac and verified that a new serial device, /dev/tty.usbserial-A800f3aA, showed up. I hooked up the Arduino to its USB cable and downloaded my program over its own serial device, /dev/tty.usbmodem26431. I brought up the serial monitor tool in the Arduino IDE and verified that I was printing sensor values. I plugged in the power cable to the Arduino and removed the USB cable. I flipped the tiny switch on the XBee shield from DLINE to UART. I brought up the Arduino serial monitor tool again, this time using the Serial Port option in the IDE's Tools pull down menu to specify the new serial device from the XBee Explorer. And this is what I saw.

No, it is not 30.55°F in my office. Unfortunately I haven't replaced the temperature sensor I fried in "Another Victim of Electrostatic Discharge", so we'll ignore the actual temperature readings for now. But the Arduino is reliably reporting sensor readings wirelessly via its serial port once per second. Here's the complete program, which is mostly the same as before with all the Ethernet and Webduino stuff stripped out of it.

byte lightLevel = 0;
float temperatureCentigrade = 0;
float temperatureFahrenheit = 0;
unsigned long then = 0;

static const int lightAnalog = 4, lightDigital = A4;
static const int temperatureAnalog = 5, temperatureDigital = A5;

static const int oversample = 10;
static const float reference = 4.66; // Measured; nominally 5v, or 3.3v external.
static const boolean internal = true;

void sense(unsigned long now) {
 int lightRaw = 0;
 for (int ii = 0; ii < oversample; ++ii) {
   lightRaw += analogRead(lightAnalog);
   delay(1);
 }
 lightRaw /= oversample;
 int temperatureRaw = 0;
 for (int ii = 0; ii < oversample; ++ii) {
   temperatureRaw += analogRead(temperatureAnalog);
   delay(1);
 }
 temperatureRaw /= oversample;
 float lightVolts = (lightRaw * reference) / 1023.0;
 lightLevel = 100 - ((100UL * lightRaw) / 1023);
 float temperatureVolts = (temperatureRaw * reference) / 1023.0;
 temperatureCentigrade = (temperatureVolts - 0.5) * 100.0;
 temperatureFahrenheit = (temperatureCentigrade * 1.8) + 32.0;
 Serial.print(lightRaw);
 Serial.print('=');
 Serial.print(lightVolts);
 Serial.print('v');
 Serial.print('=');
 Serial.print(lightLevel);
 Serial.print('%');
 Serial.print(' ');
 Serial.print(temperatureRaw);
 Serial.print('=');
 Serial.print(temperatureVolts);
 Serial.print('v');
 Serial.print('=');
 Serial.print(temperatureCentigrade);
 Serial.print('C');
 Serial.print('=');
 Serial.print(temperatureFahrenheit);
 Serial.println('F');
 then = now;
}

void sense() {
 sense(millis());
}

void setup() {
 Serial.begin(9600);
 pinMode(lightDigital, INPUT);
 digitalWrite(lightDigital, LOW);
 pinMode(temperatureDigital, INPUT);
 digitalWrite(temperatureDigital, LOW);
 if (!internal) {
   analogReference(EXTERNAL);
   delay(1);
 }
 sense();
}

void loop() {
 unsigned long now = millis();
 if ((now - then) > 1000) {
   sense(now);
 }
}

Some models of the Xbee radios do allow you to some configuration, in order to, for example, use them in other than transparent mode. Unfortunately, the tool to do this from Digi, X-CTU, is only available for Windows. But as James Sentman has pointed out, you can run X-CTU on the Mac, although to do so requires that you install MacPorts, a software package that makes it easier to port GNU-based open source applications to MacOS, and Wine, a software package that lets you run Windows applications on MacOS (and other OSes as well). Being a glutton for punishment, I of course did all of this, eventually running the X-CTU installer on the Mac under Wine, and then running X-CTU itself under Wine to talk to the XBee Explorer. However, you don't need to do any of this to accomplish what I've described here.

I found some of these references handy (in no particular order):

"XBee Manual" from SparkFun;

"XBee Data Sheet" from SparkFun;

"Simple XBee Communication with Arduino" by Matt Fisher;

"XBee Introduction and Buying Guide" from SparkFun;

"Configuring XBees" from Indestructables;

"XBee radios - connecting, configuring, and upgrading" by Limor Fried.

But once again, you don't need any of these to actually get this wireless setup working. The hardest part was, for me, not being a hardware guy, soldering the headers onto the XBee shield, and even that worked the first time. I was, however, careful to wear an ESD strap while putting all of this together.

Another Tragic Victim of Electrostatic Discharge

2012-01-26T10:04:00.005-07:00

If Chip spends more than a day trying to solve a software problem, it's a hardware problem. -- Mrs. Overclock's Law

This isn't always true, but it's been true often enough, going all the way back to 1976 when a recalcitrant disk controller on a PDP-11/05 caused my device driver to work in the morning but not in the afternoon after the lab had warmed up. I typically work with hardware engineers of such caliber that I am extremely reluctant to invoke this law. However, when it's my hands on the hardware, all bets are off.

After writing the article "Remote Sensing with Arduino" I anxiously awaited for Mrs. Overclock (a.k.a. Dr. Overclock, Medicine Woman) to return home from a hard day courageously saving lives so that I could demonstrate my latest project on her own laptop. Here is what she saw.

Let me assure you that it is seldom if ever 38.77° Fahrenheit in my home office where the Arduino board was connected to the network. Convinced that I had somehow botched some recent software changes, or maybe knocked something loose on the breadboard, I spent several hours fiddling with the code, swapping jumper wires, peering at the Arduino source code that supports the analog pins, reading documentation about the analog-to-digital convertor in the Atmel ATmega328 microcontroller, and just generally wasting my time making all of this a lot harder than it needed to be. Everything pointed to the Analog Devices TMP36 temperature sensor as the problem.

Finally, first thing this morning, I invoked Mrs. Overclock's Law and found this excellent description of how to test the TMP36 by (as I was to find out only just now) none other than Limor Fried herself. Here's a close-up of the tiny TMP36 surrounded by probes to my multimeter and wires providing power right from the Arduino board.

Initially the device reported 140 millivolts; that's around -33°F. A few minutes later it was 350mV or 5°F. Right now it reports 624mV or 54°F. Since I have my sleeves rolled up, this seems unlikely. This is a semiconductor device that had been working just fine.

I have no one to blame but myself. While everything you see here is placed carefully on an anti-static mat, I am not always careful to ground myself using the anti-static wrist strap, to my woe. Especially in the dry winter months, it is not unusual for me to experience a spark here and there. I suspect I fried the part while putting my finger on it to warm it up during testing.

It's not really the semiconductor part that's the issue here, although if I had fried an OMAP microprocessor or some other expensive or hard to get component, it might have been. The TMP36 costs two bucks U.S. or less. It's the fact that my own carelessness cost me hours of my time. When you are self-employed and you bill by the hour, you are constantly aware of the value of your time in real dollars. Using a grounded wrist strap to protect against electrostatic discharge (ESD) would have saved me a lot of time and money.

I have a grounded ESD mat and wrist strap permanently wired up on my work table in my office.

I even carry a portable model in my tool bag.

Back in my Bell Labs days we were required to take an annual refresher course in ESD practices. Or, I can just learn the hard way. If you lay hands on bare hardware, get yourself an ESD mat and wrist strap. And have the discipline to use them.

Remote Sensing with Arduino

2012-01-24T09:00:00.017-07:00

If you have met me in meatspace then you know that I am so old as to be on the verge of being a brain in a jar connected to wires and tubes. When I started doing real-time development, it was on PDP-11s with just four kilobytes of memory. This goes a long way towards explaining my affection for microcontrollers like the tiny eight-bit sixteen mega-Hertz Atmel ATmega328 used on the Arduino Uno board. It has thirty-two kilobytes of non-volatile flash memory and a scant two kilobytes of volatile static random access memory (SRAM) all on-chip. (Update 2012-01-25: I got the SRAM size wrong in the original version of this article.) There is a skill, becoming rarer in these days of increasing software bloat, of writing code that will run on such a platform. Thanks to its resource constraints and powerful software toolkit, Arduino is an excellent platform with which to learn (or re-learn) this skill.

Why bother? Because it is microcontrollers just like this that are permeating our lives, whether we realize it or not: embedded in our appliances and toys and transportation and even computers, sometimes alongside much more powerful Intel or ARM processors that do the heavy lifting required by graphical user interfaces. Microcontrollers are the universal machines that are called upon to bridge the gap between the real world and the digital, between meatspace and cyberspace. It is a market that is growing even as the market for traditional high-end microprocessors is being impacted as the typical consumer finds less and less reason to own a desktop computer or even a laptop, finding their cyberneeds better met by a smartphone or tablet and more and more computation is moved into the cloud. Thanks to their relatively low price tags, microcontrollers are increasingly becoming replacements for more complex discrete circuitry for glueing other digital components together and for implementing complex behavior. Microcontrollers bring the added advantage of being able to have their firmware updated in the field; discrete electronics, not so much.

One application for tiny microcontrollers is remote sensing. Because of their small size and frugal power consumption, microcontrollers are useful for deploying digital control and sensing into the physical world, where they can gather intelligence and report back. Playing with remote sensing is easily done with Arduino with the addition of a Ethernet shield.

Shields in the world of Arduino are daughter boards that provide specialized hardware and peripherals. They are designed with interface pins protruding from their lower surfaces that mate with the connectors or headers on the Arduino board. Those digital connections that they need themselves they take, those that they don't or which can be shared with additional boards they connect to another set of headers on their top surfaces. The Ethernet shield adds an Ethernet RJ45 connector and supporting hardware to provide an Arduino board with a wired network connection. (There are shields which provide wireless connectivity as well; one step at a time.)

Here is a side view of my Arduino Uno board with the Ethernet shield plugged in on top of it. You can see the metal pins from the shield above plugged into the headers on the Uno below. A CAT5 Ethernet cable is connected to the shield on the left. Below that you can see USB and power cables connecting to the Uno below. Jumper wires are plugged into the headers on the shield.

The SparkFun Inventor's Kit for Arduino has all the hardware you need to do several projects that involve reading sensors. I chose to combine two of them, CIRC-09 ("Light") that uses a photoresister (a device whose resistance changes with the amount of light falling on it), and CIRC-10 ("Temperature") that uses a low voltage temperature sensor from Analog Devices. The TMP36 temperature sensor is a clever little device that is complex enough that its data sheet deserves a look.

Both of these devices can be hooked up to pins on the Arduino board and read using the analog-to-digital convertor built into the chip.

So what about the "remote" part? The Arduino software includes an Ethernet library that has a rudimentary internet protocol (IP) stack that, for example, responds to ping. (The Ethernet library supports DHCP but I gave the board a static IP address on the local private network.)

On top of that I added the Webduino software that allows you to build a tiny web server that runs on the Arduino board. This web server, when interrogated by the browser on my Mac desktop, responds with a measure of the amount of light impinging on the photoresistor and the temperature in both Centigrade and Fahrenheit. Here's what it looks like, right from Safari.

I compute the light measurement to look like a percentage, but some calibration might be necessary for other applications. Still, it is easy for the software to tell the difference between night and day or whether room lights are on or off.

Here's a photograph of the entire fixture from above. The photoresistor is on the left and the temperature sensor is on the right on the breadboard, but they are so tiny that the jumper wires make them hard to see. Green, yellow and blue are sensor wires (the green one is merely reading the power bus), red are for power, and brown are for ground.

Here is the complete source code for my remote sensing project. It's not long. The underlying libraries do most of the work.

#include <SPI.h>
#include <Dhcp.h>
#include <Dns.h>
#include <Ethernet.h>
#include <EthernetClient.h>
#include <EthernetServer.h>
#include <EthernetUdp.h>
#include <WebServer.h>
#include <util.h>
#include <avr/pgmspace.h>

byte lightLevel = 0;
float temperatureCentigrade = 0;
float temperatureFarenheit = 0;
unsigned long then = 0;

void getIndexHtml(WebServer & server, WebServer::ConnectionType type, char * urlTail, bool tailComplete) {
 server.httpSuccess();
 if (type == WebServer::HEAD) { return; }
 server.print("<h1>");
 server.print(lightLevel); server.print('%');
 server.print(' ');
 server.print(temperatureCentigrade); server.print('C');
 server.print(' ');
 server.print(temperatureFarenheit); server.print('F');
 server.print("</h1>");
}

static const int referencePin = 3;
static const int lightPin = 4;
static const int temperaturePin = 5;

void sense(unsigned long now) {
 int referenceRaw = analogRead(referencePin);
 int lightRaw = analogRead(lightPin);
 lightLevel = 100 - ((100UL * lightRaw) / 1023);
 int temperatureRaw = analogRead(temperaturePin);
 float temperatureVolts = (temperatureRaw * 5.0) / 1023.0;
 temperatureCentigrade = (temperatureVolts - 0.5) * 100.0;
 temperatureFarenheit = (temperatureCentigrade * 1.8) + 32.0;
 Serial.print(referenceRaw);
 Serial.print(' ');
 Serial.print(lightRaw);
 Serial.print(' ');
 Serial.print(lightLevel);
 Serial.print(' ');
 Serial.print(temperatureRaw);
 Serial.print(' ');
 Serial.print(temperatureVolts);
 Serial.print(' ');
 Serial.print(temperatureCentigrade);
 Serial.print(' ');
 Serial.println(temperatureFarenheit);
 then = now;
 delay(1);
}

void sense() {
 sense(millis());
}

static const byte __attribute__((__progmem__)) myMacAddress[] = { 0x90, 0xa2, 0xda, 0x0d, 0x03, 0x4c };
static const byte __attribute__((__progmem__)) myIpAddress[] = { 192, 168, 1, 223 };
static const byte __attribute__((__progmem__)) myGatewayAddress[] = { 192, 168, 1, 1 };
static const byte __attribute__((__progmem__)) mySubnetMask[] = { 255, 255, 255, 0 };

WebServer webServer;

#define countof(_ARRAY_) (sizeof(_ARRAY_)/sizeof(_ARRAY_[0]))
#define flash2sram(_TO_, _FROM_, _COUNT_) byte _TO_[_COUNT_]; memcpy_P(_TO_, _FROM_, sizeof(_TO_))

void setup() {
 Serial.begin(9600);
 flash2sram(tempMacAddress, myMacAddress, countof(myMacAddress));
 flash2sram(tempIpAddress, myIpAddress, countof(myIpAddress));
 flash2sram(tempGatewayAddress, myGatewayAddress, countof(myGatewayAddress));
 flash2sram(tempSubnetMask, mySubnetMask, countof(mySubnetMask));
 Ethernet.begin(tempMacAddress, tempIpAddress, tempGatewayAddress, tempSubnetMask);
 webServer.setDefaultCommand(&getIndexHtml);
 webServer.addCommand("index.html", &getIndexHtml);
 webServer.begin();
 sense();
}

void loop() {
 unsigned long now = millis();
 if ((now - then) > 1000) {
  sense(now);
 }
 webServer.processConnection();
}

As is typical, I made this a little more difficult than it needed to be for pedagogical reasons.

To assist in debugging, I displayed a lot of the partial and final results over the serial port that is part of the ATmega328 microcontroller. This travels back over the USB cable to my desktop where it can be displayed using the serial monitor tool that is part of the Arduino development environment. Serial is a C++ reference to a pre-built object in the Arduino run-time system that provides an API to do this.

When all of your storage for volatile variables has to fit in two kilobytes of SRAM, it pays to put data that doesn't change somewhere else. You'll notice that, for example, the hard-coded IP addresses all have a mysterious __attribute__((__progmem__)) as part of their definitions. The __attribute__ keyword is a special directive to GNU C++ that can be used to communicate special implementation details to the compiler. The __progmem__ argument, specific to this family of microcontrollers, tells the compiler that the variable to which it is applied resides not in volatile SRAM but in non-volatile program memory, meaning the flash memory where executable code is normally stored persistently.

Access to program memory on this microcontroller has to be done through a different machine instruction, load program memory (lpm), than when accessing data memory (SRAM). If you are into this kind of thing, you will now realize that the ATmega328 is an example of a Harvard architecture, one in which data and instructions are stored and processed separately. The lpm instruction bridges these two worlds by allowing you to copy from program memory into temporary variables in data memory. (A von Neumann architecture is one in which data and instructions are stored in the same memory and may be accessed similarly to one another.)

The Arduino and underlying microcontroller software define C/C++ macros (for example, PROGMEM), data types (prog_char), and functions (memcpy_P), that simplify using this mechanism. But I coded the __attribute__((__progmem__)) explicitly because the use of the GCC __attribute__ directive is so common when developing close to bare metal, and for similar reasons, that I knew that many embedded developers reading this would immediately see something they recognize.

In the loop function, the main work loop, I only interrogate the sensors once a second. The call to processConnection looks to see if a web request has arrived, and if so processes it. The only request I've defined is an HTML GET for the web page index.html. Querying that web page on Arduino returns the latest sensed values.

It's pretty impressive what can be done within the resource footprint of a tiny microcontroller. This program takes a little more than half of the thirty-two kilobytes of flash, and a little less than a quarter of the two kilobytes of SRAM not including the stack. That's without much optimization on my part.

Small is beautiful.

How to Contribute to the Robert Dixon Scholarship Fund

2012-01-20T09:20:00.001-07:00

I have already been contacted by several old friends and colleagues asking how to contribute to this cause. Write a check, specify that it is to go to the "Robert Dixon Scholarship Fund", and mail it to

Wright State University Foundation
3640 Colonel Glenn Hwy.
Dayton, OH 45435

The account is already established and I assure that that the Foundation will be delighted to expeditiously cash your check and send you an official acknowledgement for your generous tax deductible contribution.

You will also have my own undying gratitude and a promise that I will buy you an appropriate beverage of your choice the next time I see you.

Thanks!

The Robert Dixon Scholarship Fund

2012-01-19T13:01:00.005-07:00

The Wright State University Foundation has a scholarship fund endowed in honor of Robert Dixon. Bob was the first faculty member hired by Wright State. His first office was in the farm house on the property while the campus was being built. He founded the Department of Mathematics and the Department of Computer Science. He served as Chair of both of those departments (some more than once) as well as Vice President of the Faculty and occasionally the Director of the Computer Center. Bob was also my, and many others, mentor and thesis advisor. I first had him as a professor in 1975.

Bob is still around, still writing software and doing math, which is his version of enjoying retirement. I had lunch with him back in November when we were both visiting Dayton Ohio, home of Wright State University. I have Bob to thank for much of what I am and have accomplished over the decades. I am pleased to have been able to contribute to the Robert Dixon Scholarship Fund. It would be great for others to do so too. It would also be great to see others honor their mentors in a similar fashion. Perhaps it's time to reflect on how lucky we have been and to whom we owe in part for our good fortune.

Thanks, Bob.

Update (2012-01-20)

Wright State University Foundation
3640 Colonel Glenn Hwy.
Dayton, OH 45435

You will also have my own undying gratitude and a promise that I will buy you an appropriate beverage of your choice the next time I see you.

Thanks!

Can what you don't know hurt you?

2012-01-17T08:55:00.013-07:00

In my recent article Pulse-Width Modulation with Arduino I showed a series of screen captures from a Saleae Logic to illustrate the kinds of square waves you could generate using Pulse-Width Modulation (PWM). The use of the Logic was critical to my understanding of what was going on under the hood in my software. The Logic is a logic analyzer: a tool that captures, interprets, and displays signals from digital circuits.

Logic analyzers have been a standard piece of kit for digital hardware designers for decades. They come in a broad range of prices, capabilities, and form factors, from units costing tens of thousands of dollars that support sub-microsecond measurements and require a dedicated equipment cart to wheel them around, to the latest generation of relatively inexpensive devices that connect to your laptop and fit in your shirt pocket. The Logic fits in the latter category. We'll talk more about it in a bit. I've become convinced that devices like the Logic need to become part of the everyday toolkit of software developers like me who routinely deal with real-time events and work close to bare metal.

If you've perused that article on PWM with Arduino, and if you have any experience with Arduino, you can be excused if you thought I had gone off the deep end with my lengthy and seemingly overly complex software to generate a PWM square wave. Under other circumstances, I would have thought so as well. I had a Logic sitting in one of my tool bags and I thought it would be a great idea (and less effort than the alternatives) to use it to create snapshots of the PWM square wave output from my program. My original program was only a dozen or so lines long and was dirt simple. What could possibly go wrong?

The first clue that something was seriously amiss was one of my first Logic traces taken when I was hard-coding the duty cycle, before I'd added the code to read the potentiometer using the analog/digital convertor. (You can click on any of these images to get access to larger sizes.)

There are several things not to like about this trace.

First, I had intended to generate a square wave with a 50% duty cycle, but in this trace the off phase is significantly longer than the on phase, by nearly 13%. The off part of the square wave had significantly more software latency: it was taking me 13% longer to get around to turning the GPIO pin back on. I couldn't account for that in my own code.

Second, the frequency was a lot lower than I thought it should be, given the tiny amount of code I thought I was executing and the real-time delays I had built into my code. I was using the Arduino digitalWrite function and it was taking a long time to turn the GPIO bit on and off.

It was time to take a deep dive into the open-source of the Arduino run-time system. I was reminded of the various bootloaders I've had to hack in times past: no OS, no multi-threading, everything running in the equivalent of kernel mode, software accessing hardware as directly as possible and routinely using privileged machine instructions. This means that delays can't be accounted for by the kinds of scheduling latency you see when running software under non-real-time multi-tasking operating systems like Linux. Delays mean that my software was doing something, even if that something was busy-waiting for some peripheral hardware to respond.

The first step was to see who called the loop function that is the equivalent to the main function in every Arduino program. A common design pattern in this kind of low level OS-less software is to have a work loop that is continuously executed. It's a loop because modern microprocessors don't have a halt instruction; the only mode the central processing unit knows is to continuously execute machine code, even if it's just a tight loop. Operating systems like Linux also have such a work loop, you just don't see it. It consists of the Linux kernel looking for a runnable task to execute. There is always at least one such a task, if nothing else a do-nothing task typically referred to as the idle task.

Here's the code in Arduino that calls the setup and the loop functions that are part of every Arduino application program. It is the main program in Arduino that is automatically invoked by the C++ run-time system once it has completed initialization, and it is the complete contents of the file main.cpp.

#include <arduino.h>

int main(void)

{

init();

#if defined(USBCON)

USB.attach();

#endif

setup();

for (;;) {

loop();

if (serialEventRun) serialEventRun();

}

return 0;

}

Pretty simple. It calls its own init function, it calls the application's setup function, and then it enters an infinite loop that calls the application's loop function followed by some code that checks for events on the serial port.

The function serialEventRun is declared elsewhere as a weak external reference: it's a function that may not be defined, and if it's not, its address will be set to zero (NULL) instead of causing an error when the Arduino is compiled and linked. This allows Arduino to be compiled for microcontroller chips that do not have a serial port, or in hardware speak, a Universal Asynchronous Receiver/Transmitter (UART), in which case the serialEventRun code is conditionally not included as part of the Arduino run-time system.

The ATmega328P microcontroller I'm using has a serial port, so this code was being executed. This explains why the timing of the off period in the square wave wasn't quite right: my original naive code turned the GPIO bit on, delayed for a while, turned the GPIO bit off, delayed for a while, and then the main program was doing some additional work. That's when I added the more complex mechanism that computed a variable delay.

I tackled the second problem by looking the implementation of the digitalWrite function.

void digitalWrite(uint8_t pin, uint8_t val)

{

uint8_t timer = digitalPinToTimer(pin);

uint8_t bit = digitalPinToBitMask(pin);

uint8_t port = digitalPinToPort(pin);

volatile uint8_t *out;

if (port == NOT_A_PIN) return;

// If the pin that support PWM output, we need to turn it off

// before doing a digital write.

if (timer != NOT_ON_TIMER) turnOffPWM(timer);

out = portOutputRegister(port);

uint8_t oldSREG = SREG;

cli();

if (val == LOW) {

*out &= ~bit;

} else {

*out |= bit;

}

SREG = oldSREG;

}

This function in Arduino is doing a lot of computation to derive a register address and bit mask from an pin number, and it does it every time. A pin number in Arduino is an abstraction that simplifies the use of the GPIO pins by mapping a number printed on the actual Arduino circuit board to a GPIO register address and bit mask. This mapping may not seem like much overhead, but Jean-Claude Wippler of JeeLabs has characterized the digitalWrite function as taking as long as fifty-eight times (update from Jean-Claude: twenty-nine times) more processor cycles than a direct register write. So I added the code to my own setup function to compute the register address and bit mask once, and then added code to do direct register reads and writes in my loop function. After that it was just some minor tweaks here and there to get the timing right.

Then I added the code using the Arduino analogRead function to sense the value of the potentiometer at the beginning of every square wave period, which was every one hundred iterations of my loop function. My next Logic trace looked like this.

You can see the bounce in the GPIO pin output at the beginning of every square wave. So the next step was to look at the Arduino analogRead function.

int analogRead(uint8_t pin)

{

uint8_t low, high;

#if defined(__AVR_ATmega1280__) || defined(__AVR_ATmega2560__)

if (pin >= 54) pin -= 54; // allow for channel or pin numbers

#elif defined(__AVR_ATmega32U4__)

if (pin >= 18) pin -= 18; // allow for channel or pin numbers

#else

if (pin >= 14) pin -= 14; // allow for channel or pin numbers

#endif

#if defined(__AVR_ATmega32U4__)

pin = analogPinToChannel(pin);

ADCSRB = (ADCSRB & ~(1 << MUX5)) | (((pin >> 3) & 0x01) << MUX5);

#elif defined(ADCSRB) && defined(MUX5)

// the MUX5 bit of ADCSRB selects whether we're reading from channels

// 0 to 7 (MUX5 low) or 8 to 15 (MUX5 high).

ADCSRB = (ADCSRB & ~(1 << MUX5)) | (((pin >> 3) & 0x01) << MUX5);

#endif

// set the analog reference (high two bits of ADMUX) and select the

// channel (low 4 bits). this also sets ADLAR (left-adjust result)

// to 0 (the default).

#if defined(ADMUX)

ADMUX = (analog_reference << 6) | (pin & 0x07);

#endif

// without a delay, we seem to read from the wrong channel

//delay(1);

#if defined(ADCSRA) && defined(ADCL)

// start the conversion

sbi(ADCSRA, ADSC);

// ADSC is cleared when the conversion finishes

while (bit_is_set(ADCSRA, ADSC));

// we have to read ADCL first; doing so locks both ADCL

// and ADCH until ADCH is read. reading ADCL second would

// cause the results of each conversion to be discarded,

// as ADCL and ADCH would be locked when it completed.

low = ADCL;

high = ADCH;

#else

// we dont have an ADC, return 0

low = 0;

high = 0;

#endif

// combine the two bytes

return (high << 8) | low;

}

There is again a lot of mapping from the abstract pin number to the actual hardware resources. But there isn't anything that obviously links this code to the square wave output pin, which is different from the input pin for the potentiometer. Next step was the 567 page Atmel reference manual for this family of microcontrollers. Also, the Arduino Uno circuit board schematic was worth a look.

567 pages is not long compared to other processor reference manuals. When you are working close to bare metal you quickly learn that more detail is better. You'll groan when you find the manufacturer's reference manual for the microcontroller you are using is only 100 pages long. You know it's going to be relatively useless. (Simpler devices may have perfectly serviceable data sheets of only a dozen pages.) You'll be tempted to send candy and flowers to vendors whose reference manuals have a good table of contents and index. A searchable PDF is also a very good thing indeed.

Even if you're not a hardware person, if you work close to bare metal you should get used to reading schematics. Regardless of your age and your eyesight, unless you have a printer that prints pages the size of movie posters, buy a magnifying glass and get used to using it. You will be amazed at what you learn when you start following circuit traces from a GPIO pin that is misbehaving and discover to what it is really connected. You might even earn some respect from your hardware colleagues. Maybe.

The Atmel documentation warns against making changes in digital output pins close in time to doing analog/digital conversions. Rather than hosing up my timing that I worked so hard to refine, I decided to limit the number of times I read the potentiometer to four times a second. I figured this would minimize the number of times I hosed up the square wave while still giving me a reasonable response time between turning the dial on the potentiometer and the electric motor speeding up or slowing down. That seemed to work okay.

So what's the point of all of this?

I wouldn't even have known of any of these issues had I not hooked up the Saleae Logic and looked in detail at what was happening on microsecond scales. In fact, even with my original naive software design, the electric motor sped up and slowed down appropriately when I turned the potentiometer. For most applications of Arduino, that's something we call success.

But that's not always the case, with Arduino or other real-time applications of microcontrollers and microprocessors. For many products on which I've worked, what happens at the microsecond scale matters. If it doesn't matter to me, it may matter to another piece of hardware that has a much higher frequency attention span than I do. It may be that you, like me, routinely work on real-time systems which are expected to have 99.999% uptime. Or on which lives depend. Or perhaps you just don't want to be humiliated when something you wrote goes pear-shaped in the field in a failure that's visible to hundreds of people.

That's why I think tools like logic analyzers in general, and for lower speed applications, PC and Mac based tools like the Saleae Logic in particular, need to be part of every real-time software developer's toolkit. The Saleae comes in eight and sixteen channel models at prices of around US$150 to US$300. The eight channel model samples at 24MHz and the sixteen channel model can sample at 100MHz. I have the less expensive model and it is likely to be all I will ever need for this kind of work. The Logic can also decode common serial communication and bus standards at signal levels of 5V and below such as asynchronous serial, I²C, and SPI. I used it to verify the pin-outs on the diagnostic serial port of the AR.drone.

The device has a tiny logic pod smaller than my penknife, barely big enough for a company property sticker, to which you connect a wiring harness with eight signal inputs plus ground. You can connect the wires on the harness directly to pins on a circuit board or use the detachable logic clips.

The pod is a rugged piece made of machined aluminum, which, let's admit, is kind of sexy. It all goes into a little zippered case that fits handily in my tool bag.

The pod connects via USB 2.0 to your PC or Mac on which the Logic software runs. I run Logic on both a Windows 7 netbook I use for field troubleshooting and on my Mac Mini desktop in my home office. Here's a photograph of me using the Logic with the netbook on the AR.drone.

Other similar tools provide comparable capabilities at competitive prices. There is really no excuse not to use one of these tools. Sometimes you really need to know what's going on under the hood. What you don't know might just hurt you.

Pulse-Width Modulation with Arduino

2012-01-16T09:14:00.026-07:00

One of the most used features on microcontrollers and microprocessors that you find in embedded systems are the General Purpose I/O (GPIO) pins. These are pins directly on the chip that can be set to low (ground) or high (typically 3.3 or 5 volts) values, or whose digital voltages can be read and turned in to bits, under the control of software running on the chip.

System-on-a-chip (SoC) solutions are so-called because they incorporate one or more processor cores with on-chip peripheral controllers that handle I/O and other functions commonly used in embedded systems. Although many of these controllers can handle relatively sophisticated functions like Ethernet physical layer protocols or specialized communication busses like I²C, SoCs inevitably have at least a handful of pins that can be manipulated by an on-chip GPIO controller.

This capability gives the embedded developer a way to implement non-standard hardware protocols (or, sometimes, implement a protocol that the existing SoC controller didn't quite get right), to talk to application specific devices like a Field Programmable Gate Array (FPGA), to sense a button or switch on the front panel, or even to do something as mundane as blink a Light Emitting Diode (LED). This last example is exactly what was going on in my article Getting to Hello World with Arduino: some simple software used the digitalWrite function to blink an LED. If you spend five minutes poking around in the Arduino run-time software you will see that ultimately this is implemented by just setting and clearing a bit at a memory location that represents a memory-mapped register in a GPIO controller built into the little eight-bit ATmega328P chip. (This is also exactly what was going on in my article Memory Mapped Devices on the BeagleBoard with Android except with a Texas Instruments DM3730 SoC with a powerful thirty-two bit ARM Cortex-A8 processor running Linux and Android.)

So let's suppose that we hook up a Radio Shack digital multimeter and a Saleae Logic analyzer to an Arduino and look at a GPIO pin. What might we see? (Ignore for a moment the explosion of wiring on the breadboard. We'll get to that in a moment.)

The multimeter is reading negative millivolts, which I think is just noise below the logic level of the GPIO pin. (You can click on any of these photographs to get access to larger sizes.)

Channel zero on the logic analyzer is reading a logic zero. So far, not that interesting. So let's write a little Arduino code to set the GPIO pin to a logic one value, just as we did to blink the LED in the previous article.

The multimeter reads about 4.5 volts. (That should nominally be five volts; the reason it's not I believe is that I'm actually driving four GPIO pins all at one time; it simplified the wiring.)

Channel zero on the logic analyzer reads a logic one. That's what my Digital Signal Processor (DSP) buddies would call a DC (for direct current) signal, by which they mean it's a constant value. They would use the term unmodulated.

So lets say we write a little more Arduino code to modulate the output of the GPIO pin, that is, turn it on and off. We'll turn it on for the same amount of time we turn it off. That means the pin will be on half, or 50%, of the time, and off the other half of the time. When it's on, it will output its full voltage, and when it's off it will be zero volts or ground. We'll refer to this by saying that the output of the GPIO pin has a 50% duty cycle.

You can see that the output of the GPIO pin is a square wave with a period of a smidge over two milliseconds. In a bit you will see that I was shooting for a delay of two milliseconds in the Arduino software. The actual duty cycle, measured by the analyzer, and thanks to slop in timing, is a little over 50%. Any guess as to what the multimeter will read?

The multimeter reads this square wave as a voltage of a little over 50% of the maximum. That's because the multimeter is expecting a constant DC input and it is reporting the average voltage over some time window. It turns out a lot of electrical devices work this way. So if we can generalize this, we can fool other devices to think they're getting different voltages the same way we fooled the multimeter, and do it all under software control. Let's try an 80% duty cycle.

So far so good. What does the multimeter say?

Yep, that's about right. What we've just done is reinvent Pulse-Width Modulation (PWM). PWM is a method of modulation that encodes a digital signal by altering the duty cycle of a square wave, that is, by changing the width of the pulse. PWM can be used as a way of encoding bits onto a wire, although not in any modern communications system of which I am aware. But its ability to fool electrical devices into thinking they are seeing different voltages is used in lots of applications.

Digital power supplies, ranging from the desktop unit you might see on a lab bench to the unit inside the wall wart that is powering your laptop, use PWM to change 120V from your wall outlet to whatever output voltage is desired. Digitally controlled PWM circuitry replaced old heavy transformers which were nothing more than heavy iron cores with a lot of copper wire wrapped around them, enabling wall warts to become pocket sized and to be much more efficient. The variable speed cooling fans in your computer are probably controlled by firmware that is reading a temperature sensor and then using PWM to apparently alter the voltage going to the electric motors in the fans. The popular AR.drone, a WiFi-controlled quadcopter toy that I've obsessively written about, uses PWM to individually control the speed of each of the four electric motors that drive its fan blades.

Indeed, PWM is so widely used that many SoC chips include a dedicated PWM controller that modulates the output of a GPIO pin at a frequency synchronized to a hardware timer. The ATmega328P chip used in Arduino is such an SoC. PWM requires no more work on the software developer's part than using the Arduino analogWrite function to set a duty cycle encoded as a number from 0 to 255.

But what would the fun be in that?

PWM has long been on my list of things with which to experiment. Naturally, I insisted on doing it the hard way: by writing a PWM algorithm completely in software without taking advantage of the PWM controller built into the chip. I combined two of the circuits included in the SparkFun Inventor's Kit for Arduino, CIRC-03 ("Transistors and Motors") and CIRC-08 ("Potentiometers"), to create an electric motor whose speed could be digitally controlled by turning the dial on a potentiometer. The voltage drop across the potentiometer, a kind of variable resister that can be tuned by turning its dial, is read periodically by the software using an analog-to-digital (A/D) convertor built into the SoC that returns a value in the range 0 to 1023, corresponding to a range of zero to five volts from the reference source. That value is used to compute a duty cycle in the range 0 to 100 for the PWM square wave. The square wave is then fed into a transistor, which is used to switch power on and off to the electric motor. In the photographs above, you can see the electric motor sitting just above the SparkFun fixture, and the blue potentiometer in the lower center with an arrow on its dial.

Here's the complete Arduino program. (As usual, the Blogger editor did violence to the indentation.) I broke up the square wave generator (function square), the timing generator (function timing), and the potentiometer sensing (function control) to simplify trying different things, like hard-coding the duty cycle instead of reading it from the potentiometer. The specific mechanism of generating the square wave is a dirt simple one known as time-proportioning: there is a counter that cycles in the range 0 to 99; the on portion of the square wave begins when the counter is greater than or equal to 100 minus the duty cycle. I also included function toggle to toggle a GPIO pin as quickly as possible to see what my upper limit on frequency was (best case about 500 Hertz), and function pwm to use the built-in PWM controller (which is a lot simpler and is what you should do in an actual PWM application).

int sensorPin = 0;
int motorPin = 9;
int meterPin = 10;
int logicPin = 11;
int ledPin = 13;

volatile uint8_t * pointer = 0;
uint8_t mask = 0;

int tick = 0;              /* 0..99 */
int dutyCycle = 0;         /* 0..100 */
unsigned int period = 20;  /* microseconds duration */
long sample = 0;           /* 0.5 seconds */
long iteration = 0;        /* 0..(sample - 1) */
boolean before = false;    /* true or false */
unsigned long then = 0;    /* microseconds elapsed */

void setup() {
 pinMode(motorPin, OUTPUT);
 digitalWrite(motorPin, LOW);
 pinMode(meterPin, OUTPUT);
 digitalWrite(meterPin, LOW);
 pinMode(logicPin, OUTPUT);
 digitalWrite(logicPin, LOW);
 pointer = portOutputRegister(digitalPinToPort(motorPin));
 mask = digitalPinToBitMask(motorPin) | digitalPinToBitMask(meterPin) | digitalPinToBitMask(logicPin) | digitalPinToBitMask(ledPin);
 sample = 1000000L / period / 4;
 then = micros();
}

void toggle() {
 for (long ii = 0; ii < 25000000; ++ii) {
  *pointer |= mask;
  *pointer &= ~mask;
 }
}

void square() {
 boolean state = (tick >= (100 - dutyCycle));
 if (state != before) {
  uint8_t oldSREG = SREG;
  cli();
  if (state) {
   *pointer |= mask;
  } else {
   *pointer &= ~mask;
  }
  SREG = oldSREG;
  before = state;
 }
 tick = (tick + 1) % 100;
}

void timing() {
 unsigned long now = micros();
 unsigned int duration = now - then;
 if (duration < period) {
  delayMicroseconds(period - duration);
 }
 square();
 then = now;
}

void control() {
 timing();
 if (iteration == 0) {
  long value = analogRead(sensorPin) / (1024 / 16);
  dutyCycle = (value * 100) / 15;
 }
 iteration = (iteration + 1) % sample;
}

void pwm() {
 dutyCycle = analogRead(sensorPin) / 4; /* 0..255 */
 analogWrite(motorPin, dutyCycle);
 analogWrite(meterPin, dutyCycle);
 analogWrite(logicPin, dutyCycle);
 delay(250);
}

void loop() {
 control();
}

I used the hard-coded duty cycle capability to do the test cases presented above so I could get as close to the desired values as possible. But lest you think the potentiometer solution doesn't work, here's a test run in which I lovingly hand dialed the potentiometer to get a duty cycle of about 66% and a voltage of about three volts.

Just for comparison, here's a test run using my pwm function that uses the built-in PWM generator, at about a 50% duty cycle dialed-in manually using the potentiometer, instead of my purely software-only version. The SoC PWM square wave generator has a higher frequency and its timing is more precise, hence it is able to generate more accurate voltages, and with a lot less effort on my part.

I don't recommend the do-it-yourself approach for an actual application using PWM. I had to do a lot of work to get the timing to be even as precise as you see here, and to deal with the odd side effect here and there like the A/D conversion causing bounce in the GPIO output pin. But along the way I did learn an awful lot about the Atmel hardware and the Arduino software, as I used the Saleae Logic analyzer to characterize the square wave I was generating. That, I do recommend.

Getting to Hello World with Arduino

2012-01-11T10:06:00.014-07:00

I am not a hardware person. This admission might come as a surprise to my software buddies, who I am always boring with long rants about how things really work under the hood. My hardware buddies would all laugh at the very idea that I might ever claim to be a hardware person. The fact is, I haven't handled discrete electronic parts with intent to build since my undergraduate computer engineering classes circa 1975. That was back when a resistor was the size of a refrigerator. I confess too that I've always been a little jealous of a former colleague and office mate (Hi, Dan!) who was always doing really cool stuff with tiny microcontrollers.

I decided it was time to do something about my ignorance. I ordered a SparkFun Inventor's Kit for Arduino!

Arduino is an open-source/open-hardware project to create a platform on which to teach electronics and embedded development and to use as a basis for simple (or not so simple) multidisciplinary applications of small microcontrollers. Several versions of the Arduino board are available with variations in the microcontroller and available peripherals. Arduino includes a graphical integrated development environment [1] that supports a C-like language [2] and includes a library of functions [3] to control the various peripherals on the board. It has been widely applied to all sorts of cool stuff from controlling sensor networks in real-life laboratory experiments to animating Christmas lights. Arduino has become so popular that an broad ecosystem of hardware and software has become available based around the various versions of the board.

(SparkFun is an online electronics retailer based just up the road in Boulder Colorado. It seems to be staffed with people who love doing interesting things with electronics. Their web site is worth a look. I am merely a satisfied continuing customer.)

The Inventor's Kit is a plastic box full of embedded fun that includes an Arduino Uno (revision 3) board with an Atmel ATmega328P eight-bit RISC microcontroller [4] (I'm already getting excited here), a small breadboard for prototyping circuits, a USB cable that connects the board to your PC or MAC for both control and power, and a selection of electronic components ranging from LEDs to a solenoid and about which I know nothing.

Fortunately it also includes an instruction booklet. The booklet has a series of fourteen projects of increasing complexity that use the components in the kit.

I immediately set off to get CIRC-01 "Blink LED" working. The Kit comes with a series of overlays that you lay right on top of the little prototyping breadboard that tell you what to plug where, and the instruction booklet tells you why. It also includes the code to get the project working. The intent here is to teach you the basics about how the microcontroller and each individual component works so you can later unleash your inner mad scientist and use Arduino for your own nefarious purposes.

In no more than a couple of hours, I managed to (1) assemble the little SparkFun prototyping fixture, (2) install the software off the web onto my Mac, (3) hook the fixture to my Mac via the USB cable and get it to power up, (4) poke a hole in my thumb and get blood all over everything, (5) wire up the circuit diagram, (6) type in the handful of lines of source code from the booklet, and (7) do a pretty good imitation of a fat old guy who wrote some software to blink an LED.

Here's the entire setup. That's the Arduino IDE on the Mac display on the left, and the tiny SparkFun fixture with the Arduino board on the right, with a USB cable providing both power to the fixture and communication with the IDE on the Mac. Yes, that's a magnifying class at the lower right. Did I mention I'm old?

Here's a screen snapshot of the IDE. (You can click on any of these images to get access to a larger version.)

And here's a closeup of the board with the LED blinking. Huzzah!

Trust me, if I can do this, anyone can do this. If you've ever wanted to learn some basic electronics and microcontroller programming, or if you have a hankering to put your latest evil experiment under digital control, this could be the platform for you. (You might skip the step requiring medical attention though.)

Update 2012-01-12

[1] Not satisfied with the documentation nor the Wikipedia page on Arduino, I naturally downloaded the tarball of the open source code from the web site and sucked it into an Eclipse project. The IDE and related host-based tools are written in Java.

[2] It's actually C++, but the run-time environment presents a much simplified API to the developer compared to other C++ environments with which you may be familiar. It might be too simple for a really complex application. But if you're that motivated you will, like me, want to dig under the hood anyway. Once you do, you'll see a lot of stuff familiar to anyone accustomed to doing embedded development. The lowest level routines to manipulate the hardware reminds me a lot of code in bootloaders that I've had to hack.

[3] The API you'll use to do the projects in the Kit is written in a way such that you could be excused if you thought it was Java. I admire the design because it is obvious that a lot of thought has been put into make it as simple as possible for someone who perhaps has only done some Java development to write useful embedded applications. You have programmatic access to the serial port on the microcontroller that connects to your desktop via USB. There is a console tool included in the IDE that gives you access to it, so you can for example print stuff to help you debug.

[4] Data types: char, byte and boolean are eight bits; int and word are sixteen bits; long, float and double are thirty-two bits. The basic register set of the processor is thirty-two eight-bit registers. If you're anything like me, you want to know this.

Since when has consistency not been eventual?

2012-01-10T12:36:00.011-07:00

Database isn't really my area.

But you don't have to be a database expert to understand what those folks mean when they use the acronym ACID (Reuter and Härder, 1983) that states for every database transaction:

Atomicity: either all or none of its changes are made;

Consistency: before and after, the database is in a consistent state;

Isolation: it either succeeds or fails regardless of concurrent transactions;

Durability: once it succeeds, its changes are persistent.

These requirements of database transactions are necessary to make sure, for example, that when you make a withdrawal from your bank account, the money you had yesterday is still there. Real-time guys like me get this because underneath the hood the database systems uses the same or similar synchronization primitives as those on which we depend on a daily basis to make sure planes keep flying and telephones keep ringing. For those readers not into this stuff, a lot of the synchronization mechanisms amount to a bank teller saying to the next guy in line "I'll be with you in a moment once I'm finished with this customer", except it has to be implemented all the way down to the lowest level of the hardware.

This was challenging enough when databases were hosted on single servers so large they frequently needed multiple processors to keep up with the workload. But when databases got so huge that they had to be distributed across multiple servers on a network, satisfying ACID suddenly got really hard. Brewer's Theorem (Brewer, 2000) and its more narrowly but formally defined cousin the CAP Theorem (Gilbert and Lynch, 2002), states that a distributed system can deliver at most two of the following three qualities:

Consistency: each server sees the same data at the same time;

Availability: each request gets a response, success or failure;

Partition tolerance: the system continues to run even when the network fails.

The need for availability and partition tolerance is especially compelling given that the network is basically unreliable. In fact, this assumption is at the very core of the initial design of what today we think of as the Internet, which started life out as a network for military communication in the face of a nuclear war. Network traffic would be briefly interrupted as cities were vaporized by megaton Soviet warheads and packets were routed around the flaming craters. Armageddon turns out to have been a good model for other catastrophic failures too, like someone accidentally powering down an equipment rack or inadvertently cutting a fiber optic cable with a back hoe.

Designers of software for distributed systems have to take this basic assumption of unreliability into account. It is in fact the first of the eight Fallacies of Distributed Computing (Deutsch 1994, Gosling 1997, et al.):

1. The network is reliable.

2. Latency is zero.

3. Bandwidth is infinite.

4. The network is secure.

5. Topology doesn't change.

6. There is one administrator.

7. Transport cost is zero.

8. The network is homogeneous.

For e-commerce giants like Amazon.com, it became a lot more important to tolerate some inconsistency issues than it was to have a system that didn't respond when I hit the Buy now with 1-Click button. (Which I do. All too often. 1-Click ordering is the bane of my credit card.) Sure, sometimes you can order something that is actually out of stock. Or order something twice. But those kinds of consistency errors are infrequent, and when they do occur, they can be detected and cleaned up after the fact. The same approach has been adopted by many cloud computing architectures for the same reason: it's the only way to build scalable systems, because scalability requires distribution.

Amazon.com coined their architectural willingness to incur some inconsistency as eventual consistency (Vogels, 2008), but the database folks adopted as the alternative to ACID the punnish acronym BASE (Pritchett, 2008):

Basically: more or less

Available: reliable

Soft state: with some inconsistencies here and there

Eventual consistency: that we'll fix later.

This approach allows, for example, Amazon.com to spread their Amazon Web Services (AWS) infrastructure across thousands of individual servers in a network that is distributed internationally. I've mentioned before that in testing Hayloft, my C++ interface to Amazon Simple Storage Service (S3), I not only could see the effects on my subsequent transactions of S3 updating its bicoastal server farm in the United States to take into account my prior transactions, but I could see the increase in latency of those updates on Black Friday, the day after Thanksgiving in the U.S., which is typically the biggest day of the year for retail commerce here, e- or otherwise.

So here's the thing. Eventual consistency is not a new idea. Probably not to the database community, but certainly not to the community of developers I hang out with who write software for both small embedded and gigantic distributed systems. (Those are the same people.) Or at least it shouldn't be. Let me give you an example.

The biggest distributed system I ever worked on was a Private Branch eXchange (PBX). This system had several distributed redundant servers controlling up to sixty-four cabinets of hardware. Each cabinet had as many as five racks. Each rack had as many as a dozen or so boards. The most complex of these boards (which I happened to have worked on) had three microprocessor chips, twenty-four individual digital signal processor (DSP) chips, and several big field programmable gate array (FPGA) chips. At least one of the microprocessor chips had dozens of concurrent software threads running at all times. The main controlling server, which these days probably has multiple cores, also had dozens, if not hundreds, of parallel threads. A single PBX could (and did) span national boundaries. And each PBX typically communicated with other PBXes, with the public telephone network, and with other equally distributed systems.

All of this stuff routinely communicated via message passing, over a combination of backplane wiring, dedicated telecommunications circuits, and internet connections. Even the simplest board in this system had at least one chip on it capable of responding to a limited set of messages coming across the backplane. When you look at the big picture, that's a lot of processors all independently doing stuff, all at the same time.

So what the heck was all this stuff doing? For the most part, each element was doing what it was told to do, either by a message from the main controlling server, from another board in the system, or in the case of inter-PBX connections from another system entirely. But whatever it was doing, it took time to do it. A typical pattern was: take a message from the queue of incoming messages, inject the message into a state machine that determines what to do given the current circumstances, and execute the resulting action. Some of these actions might (and typically did) result in one or more messages being dispatched to other threads on the same board, or other boards in the same cabinet, or back to the controlling server, or even to a completely different PBX.

Remember those fallacies of distributed computing? Not only is the network not reliable, but latency is not zero, and bandwidth is not infinite. So it takes a while for those messages to arrive at their destinations. If they arrive at all. Only to be queued up at the receiving end, perhaps behind other messages. Maybe many other messages, all waiting for a thread to finish what it's currently doing and go back and receive them. Thanks to communications latency, queueing latency, and processing latency, it might be seconds between the time a state machine makes a decision, a message is dispatched, that message is received, and acted upon.

If you could somehow take an instantaneous snapshot of the entire, gigantic system, what you would see is dozens, hundreds, thousands of processors, each acting on a message that doesn't describe the current state of things at all, but instead the state of things a while ago. How long a while? It's different for every system, every processor, every application, every workload, every instant from one to the next. It's not just eventually consistent. It's more or less perpetually inconsistent. Why? Because it was the only way to build a scalable system.

Being slightly out of sync all the time can result in a kind of positive feedback loop, where two threads, each having a different idea of the current state of affairs, both of them possibly being wrong, keep telling one another to do the wrong thing. The good news is that if this isn't addressed, it frequently results in something fairly obvious, like a communications system serving thousands of people crashing. But it can also lead to much more subtle emergent behavior in which the system as a whole acts mysteriously non-deterministic.

Once you appreciate the magnitude of it, it's a little miracle anything works at all. I used the example of a PBX because that's the biggest distributed system I could think of that I've worked on. But a similar analysis applies to any large distributed architecture: Amazon Web Services, traffic light systems, air traffic control systems, automated stock exchanges, Strategic Air Command. All of these systems have always had their own mechanisms for dealing with their special brand of eventual consistency. Here's some mechanisms I've seen used.

Audits. An audit simply means fixing a consistency issue when you encounter it, either in real-time (what the distributed database people call read repair and write repair), or by having software specifically tasked to go and look for it (asynchronous repair). More than once I've received email from Amazon.com telling me that something I ordered was actually out of stock, or asking me to verify that I meant to order two of an item. These are all the results of audits. Big distributed systems like PBXes routinely have dozens of audits running, all the time, just to apply corrective action to achieve eventual consistency.

Out of Band Messaging, Priority Messaging. Not all messages are created equal. Some messages get to take the equivalent of the passing lane and jump ahead of all the other queued messages. This is either done by using a different communications path or by jumping the message ahead of all the others in the queue. Once a thread receives such a message, it still has to decide what to do with each of the stale messages behind it: throw it away, reply to it with failure, or even reply with success under the assumption of what the sender doesn't know won't hurt it. Sometimes the result of such a high priority message is for the receiver to exit, reset, or reboot.

Hysteresis, Feedback. For a lot of real-time processes, it makes sense to take your time when you are changing something visible to others. When you receive a message telling you that you can increase your bandwidth, don't jack up your bandwidth all at once. Instead, turn that tap slowly, injecting some hysteresis or delay into the process. This gives everyone downstream more time to adjust to your changes, and to complain about it if it doesn't work for them. If you get active feedback, if for example you are monitoring real-time error rates or you start getting flow control messages from your downstream neighbors, you can stop turning the tap.

Traffic Shaping, Traffic Policing, Flow Control. All of these are mechanisms for controlling the rate at which a thread may send or receive messages. For a lot of applications, real-time data has an expiration date, and it is better to just throw it away than to process it late. If a thread is told that a message it is about to send will arrive with an unusual amount of delay (we might say that the message exceeds the traffic contract between the sender and the receiver), the sender might choose to implement a different strategy or take corrective action.

This article is in some ways my love letter to real-time systems. I have known the joy of analyzing a post mortem hemorrhage of thousands of lines of log messages late at night so that I could tell a customer why their multi-million dollar system crashed. Of watching LEDs flash on a board from across a data center equipment room and suddenly wondering "WHAT THE F...!?!?!?!" Of staring at a diagnostic laptop as I watched a system servicing an entire building increment error counters towards MAXINT. When I first starting reading about eventual consistency I knew that it was something with which I was already familiar.

Even though database isn't really my area.

Managing Actions in Simple Storage Service with Hayloft

2012-01-09T12:19:00.018-07:00

Hayloft provides a object oriented interface to the Amazon Web Services (AWS) Simple Storage Service (S3) in C++. When I started working on Hayloft, I had several goals. I'm wanted to learn something about cloud computing in general because I believe that's the direction everything is going and as someone else once said, "Amazon.com is the Coke of cloud computing, and there is no Pepsi". I wanted to learn something about S3 in particular because I have a background in mass storage systems and S3 might be the biggest one in the world. I wanted to write some software because I'm one of those people who can only learn by doing. I wanted to write it in C++ because I wanted to be able to use that software in small embedded systems and honking big distributed systems (turns out the skill sets are the same) where I've spent most of my career as a developer.

I didn't want to just slam out some code to talk to S3. I was interested in learning how to manage the individual operations, or what Hayloft refers to as an Action, with S3 using some of the patterns I've exploited in the past in the kinds of systems I've made a good living developing. I will show you some real, running code right from the Hayloft tarball (specifically in example.cpp) that will illustrate some of the different ways applications can use buckets and objects in S3 by integrating Hayloft. In S3 parlance, a bucket can be thought of as a web site with unique domain name, and an object is a flat file that a web browser can retrieve from that web site. Each of these examples will perform exactly the same sequence of S3 actions:

create BUCKET1 and BUCKET2 in S3;
put a local file unittest.txt into BUCKET1/OBJECT1 in S3;
copy BUCKET1/OBJECT1 to BUCKET2/OBJECT2 in S3;
get BUCKET2/OBJECT2 from S3 into a second temporary local file;
delete BUCKET1/OBJECT1 and BUCKET2/OBJECT2 in S3;
delete BUCKET1 and BUCKET2 in S3;
diff the first and second local files to verify they are the same.

Other than some surround to include some header files and set the some environmental variables so that Hayloft knows parameters like my access key ID and secret access key that Hayloft uses to authenticate my application to AWS, in the examples below I'm showing you all the running code that is in example.cpp.

The first example executes all actions synchronously. There is no need to start actions or wait for actions to complete. Each action is started in its C++ constructor, and the constructor blocks until that action completes. All processing is done in the calling thread.

const char * PATH = "unittest.txt";

Bucket BUCKET1("Synchronicity1");

Bucket BUCKET2("Synchronicity2");

Object OBJECT1("Synchronicity1.txt", BUCKET1);

Object OBJECT2("Synchronicity2.txt", BUCKET2);

PathInput input(PATH);

Octets length = size(PATH);

PathOutput output(OBJECT2.getKey());

BucketCreate bucketcreate1(BUCKET1);

BucketCreate bucketcreate2(BUCKET2);

if (!bucketcreate1.isSuccessful()) { break; }

if (!bucketcreate2.isSuccessful()) { break; }

ObjectPut objectput1(OBJECT1, input, length);

if (!objectput1.isSuccessful()) { break; }

ObjectCopy objectcopy(OBJECT1, OBJECT2);

if (!objectcopy.isSuccessful()) { break; }

ObjectGet objectget2(OBJECT2, output);

if (!objectget2.isSuccessful()) { break; }

ObjectDelete objectdelete1(OBJECT1);

ObjectDelete objectdelete2(OBJECT2);

if (!objectdelete1.isSuccessful()) { break; }

if (!objectdelete2.isSuccessful()) { break; }

BucketDelete bucketdelete1(BUCKET1);

BucketDelete bucketdelete2(BUCKET2);

if (!bucketdelete1.isSuccessful()) { break; }

if (!bucketdelete2.isSuccessful()) { break; }

std::string command = "diff ";

command += PATH;

command += " ";

command += OBJECT2.getKey();

if (std::system(command.c_str()) < 0) { break; }

if (::unlink(OBJECT2.getKey()) < 0) { break; }

There is no code here to recover from errors, although the extensive unit test suite for Hayloft, based on Google Test, includes examples of doing that using this paradigm. If you want to get started playing with S3 in C++ using Hayloft, this is the absolutely simplest way to do so. As with all the examples, local files are handled using Desperado input and output functors. The PathInput and PathOutput functors provide an abstract mechanism to read and write data from the local file system.

S3 actions can be managed by using a different C++ constructor that specifies a manager or what Hayloft generically refers to as a Plex. The simplest manager is Simplex, which is a bit of a cheat: it still uses the synchronous interface, but actions are not automatically started in the constructor. You must start each action explicitly, but when the start method returns, the action has completed. All actions are executed in the calling thread. I'll embolden the important differences between this and the prior example.

const char * PATH = "unittest.txt";

Bucket BUCKET1("Simplexity1");

Bucket BUCKET2("Simplexity2");

Object OBJECT1("Simplexity1.txt", BUCKET1);

Object OBJECT2("Simplexity2.txt", BUCKET2);

PathInput input(PATH);

Octets length = size(PATH);

PathOutput output(OBJECT2.getKey());

Simplex simplex;

BucketCreate bucketcreate1(BUCKET1, simplex);

BucketCreate bucketcreate2(BUCKET2, simplex);

bucketcreate1.start();

bucketcreate2.start();

if (!bucketcreate1.isSuccessful()) { break; }

if (!bucketcreate2.isSuccessful()) { break; }

ObjectPut objectput1(OBJECT1, simplex, input, length);

objectput1.start();

if (!objectput1.isSuccessful()) { break; }

ObjectCopy objectcopy(OBJECT1, OBJECT2, simplex);

objectcopy.start();

if (!objectcopy.isSuccessful()) { break; }

ObjectGet objectget2(OBJECT2, simplex, output);

objectget2.start();

if (!objectget2.isSuccessful()) { break; }

ObjectDelete objectdelete1(OBJECT1, simplex);

ObjectDelete objectdelete2(OBJECT2, simplex);

objectdelete1.start();

objectdelete2.start();

if (!objectdelete1.isSuccessful()) { break; }

if (!objectdelete2.isSuccessful()) { break; }

BucketDelete bucketdelete1(BUCKET1, simplex);

bucketdelete1.start();

BucketDelete bucketdelete2(BUCKET2, simplex);

bucketdelete2.start();

if (!bucketdelete1.isSuccessful()) { break; }

if (!bucketdelete2.isSuccessful()) { break; }

std::string command = "diff ";

command += PATH;

command += " ";

command += OBJECT2.getKey();

if (std::system(command.c_str()) < 0) { break; }

if (::unlink(OBJECT2.getKey()) < 0) { break; }

As before, there is no error recovery, although such recovery is important when using S3 or any other web or even internet based service. The most common errors will be failure to connect to the service. This can be due to connectivity problems at either end of the internet connection or indeed anywhere in between.

This next example uses a Multiplex to manage the actions. This will be the first example that uses the asynchronous interface. Because actions are executed asynchronously, multiple actions can use the same Multiplex and will be executed in parallel. Each action must be started, and the processing of each action must be explicitly driven. In this example, I'll use the Multiplex complete method that automatically drives any pending actions to completion. I'll show other approaches in subsequent examples.

const char * PATH = "unittest.txt";

Bucket BUCKET1("MultiplexityComplete1");

Bucket BUCKET2("MultiplexityComplete2");

Object OBJECT1("MultiplexityComplete1.txt", BUCKET1);

Object OBJECT2("MultiplexityComplete2.txt", BUCKET2);

PathInput input(PATH);

Octets length = size(PATH);

PathOutput output(OBJECT2.getKey());

Multiplex multiplex;

BucketCreate bucketcreate1(BUCKET1, multiplex);

BucketCreate bucketcreate2(BUCKET2, multiplex);

bucketcreate1.start();

bucketcreate2.start();

multiplex.complete();

if (!bucketcreate1.isSuccessful()) { break; }

if (!bucketcreate2.isSuccessful()) { break; }

ObjectPut objectput1(OBJECT1, multiplex, input, length);

objectput1.start();

multiplex.complete();

if (!objectput1.isSuccessful()) { break; }

ObjectCopy objectcopy(OBJECT1, OBJECT2, multiplex);

objectcopy.start();

multiplex.complete();

if (!objectcopy.isSuccessful()) { break; }

ObjectGet objectget2(OBJECT2, multiplex, output);

objectget2.start();

multiplex.complete();

if (!objectget2.isSuccessful()) { break; }

ObjectDelete objectdelete1(OBJECT1, multiplex);

ObjectDelete objectdelete2(OBJECT2, multiplex);

objectdelete1.start();

objectdelete2.start();

multiplex.complete();

if (!objectdelete1.isSuccessful()) { break; }

if (!objectdelete2.isSuccessful()) { break; }

BucketDelete bucketdelete1(BUCKET1, multiplex);

bucketdelete1.start();

BucketDelete bucketdelete2(BUCKET2, multiplex);

bucketdelete2.start();

multiplex.complete();

if (!bucketdelete1.isSuccessful()) { break; }

if (!bucketdelete2.isSuccessful()) { break; }

std::string command = "diff ";

command += PATH;

command += " ";

command += OBJECT2.getKey();

if (std::system(command.c_str()) < 0) { break; }

if (::unlink(OBJECT2.getKey()) < 0) { break; }

This approach is useful for testing, but in practice there isn't a huge advantage between it and the prior example other than the ability to run some actions in parallel, which this example does.

This next example uses Multiplex, but uses its service method to incrementally drive the underlying state machines to completion.

const char * PATH = "unittest.txt";

Bucket BUCKET1("MultiplexityService1");

Bucket BUCKET2("MultiplexityService2");

Object OBJECT1("MultiplexityService1.txt", BUCKET1);

Object OBJECT2("MultiplexityService2.txt", BUCKET2);

PathInput input(PATH);

Octets length = size(PATH);

PathOutput output(OBJECT2.getKey());

Multiplex multiplex;

BucketCreate bucketcreate1(BUCKET1, multiplex);

BucketCreate bucketcreate2(BUCKET2, multiplex);

bucketcreate1.start();

bucketcreate2.start();

while (multiplex.service() > 0) { }

if (!bucketcreate1.isSuccessful()) { break; }

if (!bucketcreate2.isSuccessful()) { break; }

ObjectPut objectput1(OBJECT1, multiplex, input, length);

objectput1.start();

while (multiplex.service() > 0) { }

if (!objectput1.isSuccessful()) { break; }

ObjectCopy objectcopy(OBJECT1, OBJECT2, multiplex);

objectcopy.start();

while (multiplex.service() > 0) { }

if (!objectcopy.isSuccessful()) { break; }

ObjectGet objectget2(OBJECT2, multiplex, output);

objectget2.start();

while (multiplex.service() > 0) { }

if (!objectget2.isSuccessful()) { break; }

ObjectDelete objectdelete1(OBJECT1, multiplex);

ObjectDelete objectdelete2(OBJECT2, multiplex);

objectdelete1.start();

objectdelete2.start();

while (multiplex.service() > 0) { }

if (!objectdelete1.isSuccessful()) { break; }

if (!objectdelete2.isSuccessful()) { break; }

BucketDelete bucketdelete1(BUCKET1, multiplex);

bucketdelete1.start();

BucketDelete bucketdelete2(BUCKET2, multiplex);

bucketdelete2.start();

while (multiplex.service() > 0) { }

if (!bucketdelete1.isSuccessful()) { break; }

if (!bucketdelete2.isSuccessful()) { break; }

std::string command = "diff ";

command += PATH;

command += " ";

command += OBJECT2.getKey();

if (std::system(command.c_str()) < 0) { break; }

if (::unlink(OBJECT2.getKey()) < 0) { break; }

I've just basically implemented the complete method by calling the service method iteratively until it reports that there is no more work to be done. But an application could instead time slice the calling of the service method with other work. The service method has embedded in it a timed select system call so that it relinquishes the processor while waiting for the sockets to S3 to become ready.

The next example is the first one in which you'll see multi-threading. The Complex manager has a service thread that runs in the background and executes all pending actions. Instead of starting actions itself, the application instead submits each action to Complex and then waits on a POSIX thread condition variable specific to that action. All action processing is done in the Complex thread. No matter how many Complex objects you create, there is just one Complex thread doing all the work, and many actions may be executed in parallel in the background by that one thread.

const char * PATH = "unittest.txt";

Bucket BUCKET1("ComplexityWait1");

Bucket BUCKET2("ComplexityWait2");

Object OBJECT1("ComplexityWait1.txt", BUCKET1);

Object OBJECT2("ComplexityWait2.txt", BUCKET2);

PathInput input(PATH);

Octets length = size(PATH);

PathOutput output(OBJECT2.getKey());

Complex complex;

BucketCreate bucketcreate1(BUCKET1, complex);

complex.start(bucketcreate1);

BucketCreate bucketcreate2(BUCKET2, complex);

complex.start(bucketcreate2);

complex.wait(bucketcreate1);

complex.wait(bucketcreate2);

if (!bucketcreate1.isSuccessful()) { break; }

if (!bucketcreate2.isSuccessful()) { break; }

ObjectPut objectput1(OBJECT1, complex, input, length);

complex.start(objectput1);

complex.wait(objectput1);

if (!objectput1.isSuccessful()) { break; }

ObjectCopy objectcopy(OBJECT1, OBJECT2, complex);

complex.start(objectcopy);

complex.wait(objectcopy);

if (!objectcopy.isSuccessful()) { break; }

ObjectGet objectget2(OBJECT2, complex, output);

complex.start(objectget2);

complex.wait(objectget2);

if (!objectget2.isSuccessful()) { break; }

ObjectDelete objectdelete1(OBJECT1, complex);

complex.start(objectdelete1);

ObjectDelete objectdelete2(OBJECT2, complex);

complex.start(objectdelete2);

complex.wait(objectdelete1);

complex.wait(objectdelete2);

if (!objectdelete1.isSuccessful()) { break; }

if (!objectdelete2.isSuccessful()) { break; }

BucketDelete bucketdelete1(BUCKET1, complex);

complex.start(bucketdelete1);

BucketDelete bucketdelete2(BUCKET2, complex);

complex.start(bucketdelete2);

complex.wait(bucketdelete1);

complex.wait(bucketdelete2);

if (!bucketdelete1.isSuccessful()) { break; }

if (!bucketdelete2.isSuccessful()) { break; }

std::string command = "diff ";

command += PATH;

command += " ";

command += OBJECT2.getKey();

if (std::system(command.c_str()) < 0) { break; }

if (::unlink(OBJECT2.getKey()) < 0) { break; }

Unless you have some strenuous objection to multi-threading, this is the approach you should use in a real application. The background service thread does a lot more than just execute the actions. If the actions fail for any reason deemed to be recoverable, like a network connection failure, the background service thread attempts to automatically retry the action. It does so after an appropriate back off interval to prevent the application from overloading the network, S3, or the local processor. The number of retries for any one action is limited so that execution of each action is guaranteed to eventually terminate. Once the application thread wakes up from its wait, the action will have either completed (either successfully or because of an unrecoverable error) or exceeded its retry limit.

One thing the background service thread cannot do by itself is know how to rewind the input or output functors if, for example, the network connection fails in the middle of the ObjectPut or ObjectGet. Hayloft has a way around that that involves overriding the reset method in ObjectPut or ObjectGet to handle the rewinding of the underlying data source or sink. In the case of PathInput and PathOutput, this just means closing and reopening the underlying local file. Although I don't show this example here, you can find it in example.cpp. It's trivial to implement in an application.

Hayloft currently doesn't offer a timed wait. I just haven't convinced myself it's either necessary or a good idea. But you can poll actions to see if the background service thread has completed them. In fact, if you don't mind burning a lot of processor cycles, you can dispense with the wait on the condition variable completely and just poll the actions until they complete.

const char * PATH = "unittest.txt";

Bucket BUCKET1("ComplexityPoll1");

Bucket BUCKET2("ComplexityPoll2");

Object OBJECT1("ComplexityPoll1.txt", BUCKET1);

Object OBJECT2("ComplexityPoll2.txt", BUCKET2);

PathInput input(PATH);

Octets length = size(PATH);

PathOutput output(OBJECT2.getKey());

Complex complex;

BucketCreate bucketcreate1(BUCKET1, complex);

complex.start(bucketcreate1);

BucketCreate bucketcreate2(BUCKET2, complex);

complex.start(bucketcreate2);

while (bucketcreate1 != true) { Thread::yield(); }

while (bucketcreate2 != true) { Thread::yield(); }

if (!bucketcreate1.isSuccessful()) { break; }

if (!bucketcreate2.isSuccessful()) { break; }

ObjectPut objectput1(OBJECT1, complex, input, length);

complex.start(objectput1);

while (objectput1 != true) { Thread::yield(); }

if (!objectput1.isSuccessful()) { break; }

ObjectCopy objectcopy(OBJECT1, OBJECT2, complex);

complex.start(objectcopy);

while (objectcopy != true) { Thread::yield(); }

if (!objectcopy.isSuccessful()) { break; }

ObjectGet objectget2(OBJECT2, complex, output);

complex.start(objectget2);

while (objectget2 != true) { Thread::yield(); }

if (!objectget2.isSuccessful()) { break; }

ObjectDelete objectdelete1(OBJECT1, complex);

complex.start(objectdelete1);

ObjectDelete objectdelete2(OBJECT2, complex);

complex.start(objectdelete2);

while (objectdelete1 != true) { Thread::yield(); }

while (objectdelete2 != true) { Thread::yield(); }

if (!objectdelete1.isSuccessful()) { break; }

if (!objectdelete2.isSuccessful()) { break; }

BucketDelete bucketdelete1(BUCKET1, complex);

complex.start(bucketdelete1);

BucketDelete bucketdelete2(BUCKET2, complex);

complex.start(bucketdelete2);

while (bucketdelete1 != true) { Thread::yield(); }

while (bucketdelete2 != true) { Thread::yield(); }

if (!bucketdelete1.isSuccessful()) { break; }

if (!bucketdelete2.isSuccessful()) { break; }

std::string command = "diff ";

command += PATH;

command += " ";

command += OBJECT2.getKey();

if (std::system(command.c_str()) < 0) { break; }

if (::unlink(OBJECT2.getKey()) < 0) { break; }

The polling queries a state variable inside every action that is protected by a mutex and is accessed using an overloaded C++ boolean cast operator.

It took me the better part of two solid months to slam out the code for Hayloft, including its extensive unit test suite. But once I did, writing these examples and getting them all running took just a morning, with occasional breaks to check out the latest LOLcats.

Even if you don't want to use Hayloft, or C++, there are many other libraries around for using S3 in other languages, or indeed for using other cloud-based services. I believe information technology is rapidly evolving into a model in which mobile wireless devices and their applications (driven by consumer-side economies of scale) act as front ends to very large distributed cloud based services (driven by information technology-side economies of scale). If you have a background in developing for embedded or distributed systems, I suspect that you are going to find your skills map well to those required for this kind of work.

Barnes & Noble Probably Stocks The Innovator's Dilemma

2012-01-06T15:40:00.006-07:00

CNN reports that Barnes & Noble is considering spinning off its Nook business. I was thinking about this very thing just the other day as I was totally loving the Kindle Touch that CyberSanta brought me for Christmas. (Mrs. Overclock got one too.)

Amazon.com has this profitable business that they can use to subsidize their Kindle research, development, and manufacturing. There has been speculation by those who have reverse engineered the Kindle that they may lose money on each device, depending on what kinds of discounts they have managed to negotiate with their suppliers and contract manufacturers. But unlike, say, Apple, which is a hardware company, and Microsoft, which is a software company, Amazon.com is a retail and e-commerce company evolving into a media production and distribution company. They can, and probably do, price the Kindle below their cost to manufacture but make it up in selling media for it. It's the whole printer versus ink and toner cartridges strategy. Or for that matter, razor versus razor blades, which has been around for decades.

B&N has no growing business with which to subsidize the Nook. In fact, it's the other way around: if they make money on the Nook, it may end up subsidizing the shrinking book store business. That makes it hard for them to make the Nook with the kind of tight (or even negative) margins that Amazon.com makes the Kindle. The only way they can compete with the Kindle is to spin-off the Nook into a separate business so it can't be used to subsidize the other side of the house. There, the Nook, and e-book distribution, can continue to be profitable, while the traditional brick-and-morter business evaporates.

I very much admire the design of the Kindle Touch. It cleverly leverages the use model of how people read books: they stare at a single page for seconds or minutes at a time. The electronic ink display of the Kindle is persistent - it only consumes power when changes are being made. The Kindle software can take advantage of all the power-saving modes in modern microprocessors intended for hand-held appliances like mobile phones and turn virtually everything on the device off, except for some hardware and software dealing with the touch sensor portion of the screen. Then it spins everything up, updates the display, and quiesces again. The monochrome display is slow to update, making it unsuitable for moving pictures, but it's perfect for books. Most of the time the device is being used no wireless network access is necessary. No wonder a single charge lasts for so long.

The design of these devices, and the evolution of their business models, is pretty darn interesting to a product developer like me who has made a good living doing development on embedded systems.

The Cost of Experimenting with the Cloud

2011-12-16T14:46:00.006-07:00

So after two months of my part-time experimentation with the Simple Storage Service (S3) from Amazon Web Services (AWS) using Hayloft, my company finally got charged for its usage. Three cents. It will be interesting to see if it actually shows up on my company credit card bill, or if Amazon.com defers it until the amount gets a little larger.

It's going to take a while. Typically I run the automated test suite many times a day, and each execution issues dozens of transactions to S3, but each transaction involves a tiny amount of data. Still, considering all I've learned while working on this project, this is a bargain.

Update 2011-12-18

I just counted: 198 individual S3 operations in the Hayloft test suite as of today, each one involving at least one request and response with S3.

Fibonacci Scaling

2011-12-09T09:21:00.007-07:00

Circa 1996 I found myself in an ideal situation: spending long hours working on a very technically challenging project with a multi-disciplinary bunch of engineers who were all smarter than I was. Good times.

During that project one of my esteemed colleagues, John Meiners, needed a way to scale up the bandwidth on communications channels allocated in real-time on an as-needed basis. We were using Asynchronous Transfer Mode (ATM), a technology in which endpoints have to negotiate with the network for the amount of bandwidth they needed. Asking for more bandwidth than we needed meant more cost for our customers. Asking for less meant data loss. Tearing down an existing channel to allocate a bigger one would be viewed as a catastrophic failure. Due to the hard real-time nature of the application, doing everything via best effort was not even on the table.

So we started small, then as load increased we allocated additional channels. But some back of the envelope calculations suggested that if we chose a fixed bandwidth increment, things could get out of hand quickly with the number of channels we had to manage. We needed to start small, but allocate larger channels as the need arose. What algorithm should we use?

John looked at various exponential algorithms, like doubling the bandwidth request of each subsequent channel. But that got really big (and hence really expensive) really quickly, and the scaling didn't match our expected use cases. What he finally settled on was Fibonacci numbers:

F_n = F_n-1 + F_n-2

where

F₀ = 0

F₁ = 1

Starting with F₁ just as Fibonacci himself did in 1202 (since using zero as a bandwidth multiplier doesn't make much sense) produces a sequence that looks like this:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

This turned out to be pretty much ideal. It starts small and conservative, expands but not too quickly, and is trivially computed since you just have to keep track of the last two numbers in the sequence and merely do an addition.

Fibonacci numbers have been around a long time. Although Leonardo of Pisa (a.k.a. Fibonacci) gets the credit, the sequence was written down earlier by Indian mathematicians. It occurs frequently in nature, most noticeably in spirals such as those found in pine cones and shells. John's idea seems pretty innovative in 1996, but lots of high-technology applications of the Fibonacci sequence exist today, including network back off algorithms, lossy data compression, pseudo-random number generators, and tree and heap data structures.

I'm thinking about this because I am once again using this sequence as a way to scale up back off time delays when recovering from network errors in Hayloft, my little C++ research project using Amazon Web Services Simple Storage Service (S3). I have no doubt that Fibonacci's simple little recursive algorithm will continue to serve me well.

Venkatesh Rao on Developernomics

2011-12-08T12:36:00.005-07:00

Venkatesh Rao had an article on the Forbes web site on the valuation of software developers: "The Rise of Developeronomics". He comes closer than anyone else so far (including me) to describing how I see things going career wise for software developers, although it's written from the perspective of someone desperately trying to hire competent developers to compete in a world in which every company has to become a software company, explicitly or implicitly. It's worth a read.

[I]f you don’t have a skill, like baking, which the developer-centric economy can actually use, you are in deep trouble. One reason the Occupy Wall Street movement is not having the impact it seems like it should, based on sheer numbers of people involved, is that many participants simply have no cards left to play in this national game of economic poker.

Investing in good developers is such a good bet at the moment, that if you have money and you happen to find a talented developer who seems to like you and wants to work with you, you should give him/her your money to build something, anything, even if you have no really good product ideas (those are cheap; I’ll sell you a dozen for a dollar). If you don’t have money, you should offer up whatever other kind of surplus you do have. The NPV on a strong and positive relationship with a talented developer today is ridiculously high. If you gain the trust of a talented developer to the point that they are likely to drop any active gig in the future in favor of joining one of your projects, the value is through the roof. The world is your oyster, which you with your developer will open.

The idea of using Net Present Value (NPV) to compare the value of a software developer with alternative investments is one of those things that for me is initially surprising yet obvious in hindsight. In today's economy, where instead of owning a factory and a warehouse of parts all of a company's worth is in intellectual capital (which really means, in the brains of its employees), it makes sense.

Rao writes the ribbonfarm.com blog where he ponders, among other things, organizational issues in high-technology firms, which is probably how he appeared on my radar screen. I don't always agree with him. Sometimes I'm not sure I'm smart enough to agree or disagree with him. But he's got some interesting ideas.

Eventual Consistency and Hayloft

2011-12-06T09:11:00.019-07:00

Given my thirty plus years of experience in distributed computing, it's a given that I've had to more or less continuously grapple with the Fallacies of Distributed Computing as laid out by L Peter Deutsch, James Gosling, and others:

The network is reliable.
Latency is zero.
Bandwidth is infinite.
The network is secure.
Topology doesn't change.
There is one administrator.
Transport cost is zero.
The network is homogeneous.

The implications of these myths led Eric Brewer to make Brewer's Conjecture, which became the CAP Theorem once it was proven by Seth Gilbert and Nancy Lynch.

A distributed system can guarantee at most two of the three following qualities:

all nodes can see the same data at the same time (consistency);
every request receives a response as to whether it succeeded or failed (availability);
the system continues to operate despite message loss (partition tolerance).

I've been thinking a lot about the implications of this for storage systems ever since attending the 27th IEEE Symposium on Massive Storage Systems and Technologies, a.k.a. MSST 2011. One of the big take aways I had from that conference was that distributed storage systems cannot reliably support POSIX semantics, in particular the POSIX features of file locking and consistency in file modification. Thanks to the CAP Theorem, POSIX semantics don't scale.

(I find that all of the really interesting problems are scalability problems, regardless of the problem domain. If solving a problem at scale n seems easy, trying applying the same solution at scale n x 1000. Not so much. That's why domains like cloud computing and exascale high performance systems have caught my interest. You can't just take current architectures and multiple by one thousand.)

This is one of the reasons that cloud storage has become popular: the various web-based mechanism for data transfer used by the cloud, like the RESTful HTTP GET and PUT, and XML-based SOAP, have semantics that have proven to be highly scalable. Hence they map well to large distributed system architectures.

It was this very issue that lead Amazon.com to adopt a strategy for its globally distributed Amazon Web Services (AWS), including S3, its non-POSIX-compliant Simple Storage Service, which its CTO Werner Vogels refers to as eventually consistent, choosing availability and partition tolerance over consistency:

Data inconsistency in large-scale reliable distributed systems has to be tolerated for two reasons: improving read and write performance under highly concurrent conditions; and handling partition cases where a majority model would render part of the system unavailable even though the nodes are up and running.

Indeed, the well publicized failures in AWS have been not in S3, but in its Elastic Block Store (EBS), which tries to support POSIX semantics on top of a globally distributed system.

I can see the Fallacies, and the eventual consistency architecture, at work when I play with Hayloft, my little C++ research project that uses S3. Any realistic application using S3 has to deal with network failures, where simply retrying the operation may be sufficient. But it also has to deal with the issues of consistency convergence: the fact that every S3 action may take place on a different AWS server that doesn't yet know what actions have taken place on other AWS servers, even though those actions may have been performed on the same storage objects.

Hayloft features both a synchronous and an asynchronous interface. The former makes it easy to play with. The latter is more likely to be what a production application would use. The asynchronous interface features a mechanism to block until an S3 action completes, or to execute multiple S3 actions incrementally and in parallel. Unlike my prior article on Hayloft, I'll use the asynchronous interface here, but use the blocking completion mechanism because it's simpler. (As before, all of this code is taken from working unit tests in the Hayloft distribution, but edited for readability. Apologies for any typos.)

Here is a code snippet that creates a bucket to hold objects. It starts the action and blocks until it completes.

Multiplex multiplex;

BucketCreate bucket("Bucket", multiplex);

bucket.start();

multiplex.complete();

But that's not sufficient. Sometimes (rarely), the action will return a status indicating a temporary failure, like "connection failed", "name lookup error", or "request timed out". The network isn't reliable, and the failure more likely to be on my end, or somewhere along the convoluted path between my system and S3, than in S3 itself. Simply retrying the action after a one second delay is usually sufficient unless the outage is severe. (Note that "success" is not a retryable condition.)

Multiplex multiplex;

BucketCreate bucket("Bucket", multiplex);

for (int ii = 0; ii < 10; ++ii) {

bucket.start();

multiplex.complete();

if (!bucket.isRetryable()) { break; }

platform.yield(platform.frequency());

}

Once the bucket is created, we can store an object in it. Here's a code snippet similar to the one above except it has to deal with rewinding the input data source if we need to retry the action. You can see that this might get a smidge complicated depending on where your data is coming from.

PathInput * source = new PathInput("./file.txt");

Size bytes = size(*input);

ObjectPut put("InputFile.txt", bucket, multiplex, source, bytes);

for (int ii = 0; ii < 10; ++ii) {

put.start();

multiplex.complete();

if (!put.isRetryable()) { break; }

platform.yield(platform.frequency());

source = new PathInput("./file.txt");

bytes = size(*input);

put.reset(source, bytes);

}

But network outages aren't the only failures we have to worry about. The following code snippet retrieves the metadata for the object we just created.

ObjectHead head(put, multiplex);

for (int ii = 0; ii < 10; ++ii) {

head.start();

multiplex.complete();

if (!head.isRetryable()) { break; }

platform.yield(platform.frequency());

}

This usually works. Except when it doesn't. Sometimes (and much more frequently than I see retries due to temporary network failures) the action will return a non-retryable status indicating the object wasn't found. WTF?

The object head action was serviced by a different AWS server than that of the object put action, one that hadn't yet been notified of the object put. This is eventual consistency in action. The unit test tries a code snippet like the following, treating the non-existence of the object as a retryable error, since it knows darn well the object put was successful.

ObjectHead head(put, multiplex);

for (int ii = 0; ii < 10; ++ii) {

head.start();

multiplex.complete();

if (head.isRetryable()) {

// Keep trying.

} else if (head.isNonexistent()) {

// Keep trying.

} else {

break;

}

platform.yield(platform.frequency());

}

Eventually this works. But it's even more complicated than that. If you ran this exact same code snippet again, it might still fail at first, because it was run on yet another server which had not yet been updated to be consistent with the others. In fact, its success on a subsequent attempt may be because it just happened to be executed on the original server, not because all the servers had been updated. Applications have to be designed around this. Amazon's S3 best practices document recommends not using code snippets like this to verify the successful put of an object.

The unit tests log a message every time they retry. I can actually watch how long it takes for the AWS servers to become consistent, and how this consistency convergence changes with the load on the system. Typically it converges so quickly that the unit test doesn't have to retry. Rarely, it takes a second or two. Or sometimes, not so rarely. I was testing a lot of this code on the day after the Thanksgiving holiday in the United States, also known as Black Friday, typically the busiest shopping day of the Christmas season. It frequently took two or three seconds for the system to converge to a consistent state. I haven't seen this kind of latency before or since. But, to its credit, S3 always converged and the unit tests all eventually ran successfully to completion.

Whether or not this is an issue for you depends on your S3 application. For a lot of applications, it won't matter. For applications where read-after-write consistency is important, AWS offers a higher (more expensive) tier of service where objects are co-located in one of their big data centers instead of possibly being spread out among multiple centers; this tier offers read-after-write consistency. If immediate consistency is an issue for you, S3 may not be right platform for your application. However, I would argue that distributed computing isn't the right paradigm for you.

The cloud is not the place for everyone.

Amazon.com's Simple Storage Service and Hayloft

2011-12-01T13:24:00.019-07:00

Information technology is like fashion: you live long enough, you see it change many times. And sometimes the new stuff looks kinda like the old stuff. But that doesn't mean you don't get excited about it. Change is inevitable; you might as well learn to enjoy it.

I'm watching the IT world evolve to a model that is handheld battery powered consumer devices, which these days we're calling smartphones and tablets, communicating wirelessly with enormous distributed computing systems, which we now call cloud computing. I'm all excited. For lots of reasons. Not the least of which is the fact that my professional career over the past thirty-five years as wobbled back and forth between developing software for small embedded systems and for high performance computers, gigantic distributed systems, and server farms. Turns out, the skill sets are the same. I am not the first person to have noticed this.

My most recent project is to develop Hayloft, a C++ object oriented interface to Amazon Web Services (AWS) Simple Storage Service (S3). My goal is for Hayloft to make it easy to use S3 from embedded devices. S3 is Amazon.com's web-based storage service that can (if you do it right) reliably and inexpensively store blobs of arbitrary data. How much data? A single blob, or object, can be up to five terabytes in size. And you can store a lot of objects. Objects are organized into buckets. Each bucket can be thought of as a web site with its own domain name, which means bucket names have to conform to the internet's Domain Name System (DNS) syntax. Each object is independently addressable via its own URL. To S3, these objects are simply opaque data files in the classic mass storage system reference model sense: they can range from HTML pages to scientific databases to virtual machine images to what have you.

(Indeed, I strongly suspect you could build a distributed mass storage system from S3 just as Cycle Computing built a 10,000 core distributed supercomputer from Amazon.com's Elastic Computing Cloud (EC2) for one of their customers. I'm pretty excited about that, too.)

Why would you you want to access S3 from an embedded device? Can you think of any applications for an infinitely large, internet-accessible, web-addressable, reliable, secure, storage system? Whether you are building clever consumer applications for the commercial space, developing sensor platforms for the defense and intelligence domain, or information processing applications for the industrial, financial, or medical markets, if the thought of this doesn't make your hands shake, you aren't thinking clearly. Seriously. Terabytes of storage are just a wireless connection away from your handheld and embedded applications.

Here's a little taste of what Hayloft is like. These examples are taken directly from the unit test suite included with Hayloft with all the EXPECT and ASSERT statements removed. I've also removed all of the error recovery and consistency convergence code which in any practical circumstances are very necessary; I'll talk more about that in later articles. Hayloft presents both a synchronous and an asynchronous interface. These examples use the simpler synchronous interface: when the C++ constructor completes, all the S3 work is done.

Here's a code snippet that creates a new bucket, and writes a local file into an object in it. The user key id and secret access key, which are sort of like your login and password for AWS, and which are provided by Amazon.com, are in environmental variables. Also in an environmental variable is a bucket suffix appended to all bucket names to make them globally unique; I use my internet domain name. All of the other S3 parameters, like location constraint, endpoint, access control list, and so forth can be omitted, because for experimenting, the defaults are reasonable. Input and output is handled using Desperado I/O functors.

BucketCreate create("bucket");

PathInput input("./oldfile.txt");

Size bytes = size(input);

ObjectPut put("Object.txt", create, input, bytes);

By default, buckets and objects are created by Hayloft with private access. With just a few more lines you can specify public read access so that you can (and I have) retrieve this object using your web browser.

AccessPublicRead access;

Context context;

context.setAccess(access);

BucketCreate create("bucket", context);

Properties properties;

properties.setAccess(access);

PathInput input("./oldfile.txt");

Size bytes = size(input);

ObjectPut put("Object.txt", create, input, bytes, properties);

This object can now be accessed using the following URL.

http://bucket.hayloft.diag.com.s3.amazonaws.com/Object.txt

This is a code snippet that reads the object into a local file, then deletes the object.

PathOutput output("./newfile.txt");

ObjectGet get("Object.txt", create, output);

ObjectDelete delete("Object.txt", create);

Other than some #include statements for header files, and some curly brackets and what not, that's about all there is to it, if you ignore (at your peril) error recovery. Here's a snippet that gets a table of contents from an existing bucket, then uses the C++ Standard Template Library (STL) to iterate through it and print the object names.

BucketManifest manifest("bucket");

BucketManifest::Manifest::const_iterator here = manifest.getManifest().begin();

BucketManifest::Manifest::const_iterator there = manifest.getManifest().end();

while (here != there) {

const char * key = here->first.c_str();

printf("%s\n", key);

++here;

}

While using Hayloft is easy, installing it may take a few minutes. Hayloft is built for GNU and Linux on top of Desperadito, my C++ systems programming library (a subset of the much larger Desperado), and libs3, Bryan Ischo's excellent C-based S3 library. libs3 is built on top of CURL, Open SSL, and XML2, all of which can be probably acquired through the standard package manager on your Linux system. The unit tests for Hayloft are built with Google Test (or Google Mock, which includes Google Test), Google's outstanding C++ unit testing framework, and Lariat, my thin layer over Google Test.

But once you get past the installation, starting to play with S3 in C++ applications is as simple as pulling out your credit card, signing up for an AWS account, and writing a few lines of code.

Making Both Archives and Shared Objects

2011-11-26T10:05:00.005-07:00

It's not uncommon to want to support both static linking, with a library archive, and dynamic linking, with a shared object. I almost always choose the latter, but it is not uncommon for small embedded applications to be statically linked. This can actually reduce the memory footprint of the entire system when not many object files are shared. Or sometimes it's necessary for esoteric reasons of shared memory or what not. Google Test, my favorite C++ unit testing framework, actually recommends static linking against its libgtest.a archive.

When supporting both static and dynamic linking, I always generate the library archive, for example libhayloft.a, then automate the generation of the shared object, libhayloft.so. Here's a Makefile snippet that does that. It simply unloads the entire archive into a temporary directory, creates a shared object, then removes the directory. (I've resolved all the make variable names to make this a little more comprehensible.)

libhayloft.so: libhayloft.a

HERE="`pwd`"; \

THERE="`mktemp -d /tmp/hayloft.XXXXXXXXXX`"; \

( cd $$THERE; ar xv $$HERE/libhayloft.a ); \

gcc -shared -Wl,-soname,libhayloft.so -o \

libhayloft.so $$THERE/*.o; \

rm -rf $$THERE

Dependency Generation with Subdirectories using gcc

2011-11-24T07:55:00.011-07:00

Here I am on Thanksgiving morning working on my latest project, Hayloft. As is not uncommon, Mrs. Overclock (a.k.a. Dr. Overclock, Medicine Woman) has to work today, leaving your fearless leader to finish up the dinner preparations later in the day. So I thought I'd debug an issue that's been driving me to distraction: automatic dependency generation using the GNU gcc/g++ compilers.

In Hayloft, I have translation units (that's what the standards call C and C++ source files) organized into subdirectories, for example hayloft/Logger.cpp and s3/BucketCreate.cpp, but using just one Makefile. This makes it easier to manage the code base, with absolutely no additional effort on my part, since the make command's pattern matching causes a rule like

%.o: %.cpp

g++ -o $@ -c $<

to do exactly what I want: The % in the target %.o matches the entire file name path, for example s3/BucketCreate, and is propagated into the prerequisite %.cpp. The object file ends up in the same subdirectory. Life is good.

Alas, if I do the usual command to generate dependencies

g++ -MM -MG s3/BucketCreate.cpp

it creates a rule not with the s3/BucketCreate.o target (which is what I want) but with BucketCreate.o. Since I'm running the Makefile from the project's root directory, there will never be a BucketCreate.o nor a requirement for it. If I edit a prerequisite for s3/BucketCreate.cpp (that is, any header file that it includes), s3/BucketCreate.o will never be automatically regenerated.

So I had to write a little rule to go through the source code base, generate the dependencies for each source file individually, and prepend the directory path for that source file onto the make target. Here's what this looks like. (Apologies as usual for any Blogger editor weirdness.)

DEPENDS:=${shell find . -type f \( -name '*.c' \

-o -name '*.cpp' \) -print}

depend:

cp /dev/null dependencies.mk

for F in $(DEPENDS); do \

D=`dirname $$F | sed "s/^\.\///"`; \

echo -n "$$D/" >> dependencies.mk; \

$(CXX) $(CPPFLAGS) -MM -MG $$F \

>> dependencies.mk; \

done

-include dependencies.mk

It's a bit of a tribute to make and the shell that this is even possible.

Abstraction in C++ using I/O Functors

2011-11-14T08:52:00.010-07:00

In Abstraction in C Using Source and Sinks, I wrote about how useful I've found it to abstract out I/O interfaces so that I could write software that didn't have to know from where its input was coming or to where its output was going: sockets, standard I/O library FILE pointers, memory buffers, the system log, etc. That C-based project, Concha, was a clean room reimplementation of work I had done for a client back in 2007. What I didn't mention was that it was in turn inspired by work I had done in 2006 for a C++-based project, Desperado. Now that I'm building yet another project, Hayloft, on top of Desperado, I'm reminded how much I like the Desperado I/O abstraction.

The Desperado I/O abstraction defines two interfaces, Input and Output. These interfaces make use of the ability in C++ to overload the parentheses operators to create functors (a.k.a. function objects): objects that can be manipulated through a function call interface. Looking at code, you will think you are looking at function calls. What you are really seeing are instance method calls against an object that overrides the parentheses operators.

The Input interface defines the following four operations.

int operator() ();

This returns the next character as an integer, or EOF (end of file) to indicate that no more input is available.

int operator() (int ch);

This pushes a single character back into the input stream. (This vastly simplifies the implementation of many common parsing algorithms that require one-token look ahead.) The interface guarantees that at least one character can be pushed back. It need not be the most recent character read. How the push back is actually done is up to the underlying implementation; buffering it inside the object in the derived class implementation is acceptable. If the push back is successful, the character is returned, otherwise EOF is returned.

ssize_t operator() (char * buffer, size_t size);

This returns a line terminated by a newline character (/n) or EOF. The optional size parameter allows the caller to place a limit on the number of characters returned. The result is guaranteed to be NUL terminated as long as the buffer is at least one byte in length. The actual number of characters input is returned, or EOF if none.

ssize_t operator() (void * buffer, size_t minimum, size_t maximum);

This is typically used for unformatted data. The minimum parameter indicates the minimum number of characters to be returned. The implementation blocks until that many characters are available or EOF is reached. The maximum parameter indicates the maximum number of characters to be returned if it can be done without blocking. Specifying a minimum of zero is a common way to implement non-blocking I/O using polling. Specifying the same value for minimum and maximum simply blocks for a fixed amount of data. Using the value one for minimum results in something similar to the POSIX read system call. The actual number of characters input is returned, or EOF if none.

That's it. No open or close: those are the job of either the caller, or of the implementation's constructor and destructor. The Input base class isn't pure: it actually implements all of these operators, returning EOF for all operations. That makes the base class the equivalent of /dev/null.

Since all implementations derive from the Input base class, you can pass a pointer or reference to any implementation to a function expecting an Input pointer or reference and it will read its data from that object without having any idea what the actual underlying data source is. Desperado implements a variety of derived classes, such as DescriptorInput (its constructor takes a file descriptor as an argument), FileInput (a FILE pointer), BufferInput (a read/write memory buffer), DataInput (a read-only memory buffer), and PathInput (a path name in the file system). All of these derived classes implement the full Input interface.

The Hayloft project leverages this in its Parameter class. Parameter takes an Input reference or pointer, uses the line input functor, and reads a parameter value into a C++ std::string that is a instance variable named parameter. It has no idea where this value is coming from: a file, a socket, a memory location, what have you. Here's the complete implementation of the method in Parameter that does this.

(I apologize in advance for any violence done to this and other code snippets by the Blogger formatter - which truly sucks at code examples even when editing raw HTML - and for any typos I make when transcribing this from actual working source code.)

void Parameter::source(Input & input, size_t maximum) {
int ch;
while (maximum > 0) {
ch = input();
if ((ch == EOF) || (ch == '\0') || (ch == '\n')) { break; }
parameter += ch;
--maximum;
}
}

You can see the Input functor called on the fourth line: the input object reference is used just as if it were a function.

The Output interface defines the following five operations.

int operator() (int c);

A single character in an integer is emitted. The character is returned or EOF if unsuccessful.

ssize_t operator() (const char * s, size_t size);

A null terminated string is emitted. The optional size parameter places a limit on the number of characters emitted. The actual number of characters emitted is returned or EOF if none.

ssize_t operator() (const char * format, va_list ap);

A variable length argument list is emitted according to the printf-style format string. The actual number of characters emitted is returned or EOF if none.

ssize_t operator() (const void * buffer, size_t minimum, size_t maximum);

At least a minimum and no more than a maximum number of bytes are emitted. As before, more than the minimum is emitted if it can be done without blocking. The actual number of characters emitted is returned or EOF if none.

int operator() ();

Any data buffered in the underlying implementation are flushed to the output stream. A non-negative number is returned for success, EOF for failure.

Similar to the Input interface, the Output base class is not pure: it implements all of these functors, each of which throws the data away and returns success. The Output base class is also the equivalent of /dev/null.

As you might expect, Desperado implements a variety of derived classes: DescriptorOutput, FileOutput, BufferOutput, PathOutput, and SyslogOutput (which writes all of its output to the system log).

The Desperado Print class makes effective of Output functors. Its constructor takes a single Output reference as its only parameter.

Print:Print(Output & output);

Print defines its own functor which takes a variable length argument list. Here is its entire implementation.

ssize_t Print::operator() (const char * format ...) {

va_list ap;

ssize_t rc;

va_start(ap, format);

rc = output(format, ap);

va_end(ap);

return rc;

}

You can see the output constructor reference used just like a function call on the fifth line.

In an application, you can now write code like this, which I do all the time. (Warning: head explosion may be imminent.)

extern Output * myoutputp;

Print printf(*myoutputp);

printf("An error occurred!\n");

printf("errno=%d\n", errno);

This illustrates one of the greatest strengths and greatest weaknesses of C++: if you encountered this while reading code, you would likely to assume that the printf was the standard I/O statement you know and love. But it isn't at all; it's a Print object. And that Print object has no idea where it's output is going. Depending on actual type of its constructor argument, it could be a socket, a file, or even a memory buffer.

It is possible to have a class that offers both an Input and an Output interface. Hayloft does this for its Packet class. Packet implements an infinite (as long as memory holds out anyway) bi-directional memory buffer. Although it offers specialized methods to prepend and append data, it also exposes both an Input and Output interface so that a Packet can be used as a data sink (by passing its Output interface) or as a data source (through its Input interface). A Packet can be used in this manner as a ring buffer.

This pattern is so common that Desperado defines an InputOutput interface for such implementations. This interface defines two methods that each return a reference to the appropriate interface.

Input & input();

Output & output();

This allows you to do things like

extern Packet * mypacketp;

Print printf(mypacketp->output());

to collect printed output into a Packet.

I/O functors illustrate one of those capabilities that makes C++ both extremely powerful and often hard to understand, because it allows one to use C++ not just as a programming language but as a meta-language, effectively creating a new domain specific language with its own operations, one that just happens to look vaguely like C++. It also means that while reading C++ code, especially in large code bases, it can be very difficult to make any assumptions about what is going on without both a broad and a deep understanding of both C++ and the underlying code.

Up the Source Code Organization

2011-10-31T11:59:00.029-06:00

I've spent decades working in humongous C and C++ source code bases. Humongous means many millions of lines of code. Some of it I even wrote. Most of it I didn't. Most of it didn't even originate in the organization in which I found myself working. Integrating large source bases in which major components weren't necessarily designed to work together can be a challenge.

With the plethora of open source software now available, it's not unusual that to use that new software stack that could save you months of development time, you discover you need to install a handful of other software stacks on which it depends. And those stacks have their own dependencies. And so on. Gone are the days in which you could just get by with the standard C library.

These days at Digital Aggregates I've been working on a project that incorporates not only several third-party software stacks written in C or C++, but some of my own software libraries, some of which I wrote years ago. My integration experience has caused me to revisit how I put those libraries together. Laziness being a virtue among software developers, I've come up with some organizational techniques to make my life easier at least when using my own software. These techniques exploit two things: the Digital Aggregates domain name, diag.com, and a project name unique within the company, and borrows from similar techniques used in the Java world.

Every Digital Aggregates project gets a project name. The name itself doesn't have to have any significance to the project, although it usually does in at least a pun-ish way that may only have meaning to me. The name is not an acronym, nor is it a name already used at the time by some well known (to me, anyway) software package

For example, today I wrote code using Desperado, a collection of C++ classes that implement design patterns I've found useful in embedded software development; Diminuto, a collection of C functions that implement design patterns I've found useful in systems programming on Linux and GNU based systems; Lariat, a small software wrapper around Google Test, Goggle's excellent C++ unit testing framework, that allows you to set resource limits like real-time execution duration on unit tests from the command line; and Hayloft, a work in progress. The project names help me keep everything straight.

As mundane as it sounds, the project name starts life on a manilla file folder. I keep at least some paper documentation around, either temporarily or permanently. The manilla file folder keeps all of it together and it can be easily identified as it lays on my desk or is filed in the file cabinet. On my desk in my home office right now I have file folders labelled Biscuit, Lariat, and Hayloft. Just minutes ago I consulted the file folder labelled Desperado in the file cabinet.

I keep lab notebooks that are organized not by project but chronologically and by client. I use the project name to identify notes I make in the notebook.

Obviously, I use the project name when I write about my work here in my blog, as in Automating Maintenance on Embedded Systems with Biscuits where Biscuit is the project name.

I also use it as part of the URL for the project page on the Digital Aggregates web site, for example

http://www.diag.com/navigation/downloads/Desperado.html

which of course incorporates the Digital Aggregates domain name as well. Furthermore, the project name becomes part of the tar ball name. For example

http://www.diag.com/ftp/desperado-zinc.tgz

is a compressed tar ball for the Zinc distribution of Desperado.

I use the project name as the repository name in Subversion, my current source code control system of choice. My Subversion layout for every project follows the pattern I used for Desperado, and is more or less right out of the Subversion documentation.

desperado/trunk/Desperado

desperado/tag/Desperado

desperado/branches/Desperado

desperado is the Subversion repository name. The directory trunk contains the main development branch, tag contains a check point of each major release, and branches contains any temporary or ancillary development branches.

Directory names on disk incorporate the project name. For example, the implementation files for Desperado are in

${HOME}/src/Desperado

where this is just a check out of the main development branch from Subversion.

I'm a big fan of Eclipse, the open source GUI-based IDE, for C, C++, and Java development. The project name becomes the Eclipse project name, so the name Desperado shows up in the Project Explorer or C/C++ views in Eclipse, with all the source files underneath it.

Organizing header files for projects which use multiple components can be especially challenging, and I frequently see it done especially poorly. For my C and C++ projects that result in libraries intended to be used in other work, I've borrowed from some Java best practices and use both the domain name and project name as part of the header file path name. For example, a source file I was edited today had the following #include statements.

#include "com/diag/hayloft/Packet.h"

#include "com/diag/desperado/Platform.h"

#include "com/diag/desperado/Print.h"

#include "com/diag/desperado/Dump.h"

The domain name becomes part of the path used to include the header file for a specific project. This approach is used not just by source files using the libraries, but also in the source files that implement the library. This makes it perfectly clear from which project a header file is being included, and prevents any header file name collisions. For example, the Desperado header files are under

${HOME}/src/Desperado/include/com/diag/desperado

while the Hayloft header files are under

${HOME}/src/Hayloft/include/com/diag/hayloft

and the GNU g++ or gcc command line options

-I${HOME}/src/Desperado/include

and

-I${HOME}/src/Hayloft/include

are used to point the compiler to the right places. (You might choose to use the -iquote option instead.) Although these point to the source code directories where I do development, they could just as easily point to /usr/include or maybe /usr/local/include and the same naming system would prevent any conflicts with other header files.

I'm also a fan of namespaces in C++, where I use a similar approach. All of the Desperado C++ symbols are in the namespace

::com::diag::desperado

where as all of the Hayloft C++ symbols are in the namespace

::com::diag::hayloft

which results in code snippets that look like the one below.

namespace com {

namespace diag {

namespace hayloft {

/**

* Ctor.

explicit Logger(::com::diag::desperado::Output &ro)

: ::com::diag::desperado::Logger(ro)

, mask(0)

{}

}

This is a constructor for the Hayloft class Logger that derives from the Desperado class Logger and uses a reference to an object of the Desperado Output class as an argument.

Furthermore, some projects require more complex namespace organizations, and this is reflected in both the implementation and header file directory hierarchies. For example, C++ symbols in the namespace

::com::diag::hayloft::s3

find their header files in

${HOME}/src/Hayloft/include/com/diag/hayloft/s3

and their implementation files in

${HOME}/src/Hayloft/s3 .

This may sound complex, but it is in practice easily done.

I predict now you are wondering what I do for C functions, where namespaces aren't an option. Using the Digital Aggregates domain name as part of C functions violates my laziness rule. It just seems to be more work than it's worth. But I do include the project name and a name roughly equivalent to a C++ class name into the function name. For example

void * diminuto_map_map(

uintptr_t start,

size_t length,

void ** startp,

size_t * lengthp

)

is a prototype for a C function in the Diminuto library that is part of the map feature for a function that maps a physical memory address to a virtual memory address.

I use a similar approach when defining macros that are expanded by the C preprocessor, resulting in names like

DIMINUTO_LOG_PRIORITY_NOTICE

diminuto_list_next

which can sometimes seem a little cumbersome.

I try not to use preprocessor macros at all when writing C++. But I do use the expanded naming system in both C and C++ when defining preprocessor guard symbols that prevent header files from being included more than once. This results, for example, in the guard preprocessor symbol

_H_COM_DIAG_HAYLOFT_S3_LOCATIONCONSTRAINT

for a C++ header file in the s3 sub-directory and sub-namespace.

I do use the domain name in the name of any environmental variables. For example, you can set the log level in Hayloft by setting the value of an environmental variable

COM_DIAG_HAYLOFT_LOGGER_MASK

which incorporates the domain name, the project name, and even the class name. Since environmental variables are in a global namespace that is be shared among pretty much all of the software being used by a particular user, and because you typically don't have to type the environmental variable name very often, this seems the safest approach.

In a future article I'll be talking about how I apply Google Test in projects like Hayloft, where I use a similar naming scheme that differs slightly to prevent collisions between the header files and classes under test and the test and mock classes themselves.

Automating Maintenance on Embedded Systems with Biscuits

2011-10-14T12:44:00.025-06:00

If you make a living, as I have from time to time, developing embedded systems, it's not unusual to find your work day interrupted on a regular basis by application developers that want their own development systems updated to the latest platform release, or firmware installed to support a new version of an FPGA, or some other routine system maintenance chore. Even embedded systems based on Linux and GNU are frequently too small to implement the tools used by big iron, graphical interfaces like the Synaptic Package Manager for Ubuntu, or even command line tools like yum, apt, or dpkg. Sometimes the chore is as mundane as creating a tar ball of the system logs to ship back to you so you can debug a field problem. But you still don't want to burden a non-geek user with all the skills, and maybe even the root password, necessary to do that. What would be great is if you could automate that system maintenance chore in a secure fashion and get it done by just handing the user a USB thumb drive and telling them where to stick it. Biscuits do that.

A biscuit is a cpio archive that has been compressed with bzip2 and then encrypted using gpg (GNU Privacy Guard a.k.a. GNUPG) into a binary file. The biscuit command decrypts and decompresses the file, by default named biscuit.bin in the current working directory, and extracts its contents into a temporary directory. It then looks for an unencrypted executable file named biscuit, script or binary, in that directory. If it finds it, it modifies the PATH and LD_LIBRARY_PATH environmental variables to include the temporary directory, changes its current working directory to the original delivery media (for example, a USB drive), and then runs the executable. What happens next is up to the executable. When the executable exits, the temporary directory is cleaned up and and deleted. While it runs, the executable has access to both the temporary directory, where any other collateral material from inside the biscuit can be found, and the working directory, where results may be placed.

Usage: biscuit [ -C working_directory ] [ -f biscuit_file ]

The encryption defaults to EIGamal (ELG-E), an asymmetric key encryption algorithm based on Diffie-Hellman key exchange, using 1024 bit keys. EIGamal is not patent encumbered, and although longer keys are possible, 1024 bits strikes a good balance between speed and security for slower embedded processors. The server where biscuits are packaged maintains a key ring containing the public (encrypting) keys for all the embedded systems on which biscuits may be deployed. Each embedded system has a key ring containing its own secret (decrypting) keys.

Different unique public/secret key pairs can be created, allowing you to distinguish between product lines, architectures, even individual systems, whatever makes sense for your business. This allows you to create biscuits for product flavor A that cannot be executed on product flavor B: the wrong biscuits simply won't successfully decrypt. The encryption serves as both an authentication mechanism (the biscuit comes from a reputable source) and an authorization mechanism (the biscuit can be executed using root privileges). Since users can't crack open biscuits, they not only can't create their own biscuits, they can't even see what your biscuits do. Biscuits are opaque binary files. They cannot be easily reverse engineered without cracking the encryption. They can be delivered on removable media such as USB thumb drives, CD-ROMs, or DVDs, or they can be downloaded across a network via ftp, tftp,or scp.

I've been using this or similar approaches to automating system maintenance of embedded systems for several years now. A link to a clean room implementation of biscuits can be found on the Biscuit project web page. It's mostly just a Makefile to build GNUPG for multiple architectures, generate and manage the keys for both the build server and the embedded hosts, create the biscuit command, and package up biscuit binary files, plus a couple of example biscuit scripts. But the distribution tar ball also contains some useful stuff for automating the use of biscuits in your embedded system, depending on your needs and comfort level.

Users can just run the biscuit command manually and point it at a biscuit.bin binary file. You can set your embedded host up so that only root can do so, so that users must use sudo to run biscuit.

If your embedded Linux system uses udev, like big iron distributions like Ubuntu, you can install the 99-com-diag-biscuit.rules file into /etc/udev/rules.d/99-com-diag-biscuit.rules . That will cause your system to temporarily mount any block device that is inserted, look for a biscuit.bin file, run the biscuit command against it, and unmount the device when it completes. The udev rules I wrote for my use only apply to removable storage devices by excluding the device names used for permanently attached block storage. You should customize these rules to fit your own platform.

If your system uses a simpler version of udev, like embedded distributions like Angström, you can install the mount.sh script into /etc/udev/scripts/mount.sh to do the same thing. Or just look at the one line I inserted into Angström's mount.sh that runs biscuit against the auto-mounted media, and do something similar on your system.

If you have an older embedded system that doesn't use udev but instead uses hotplug, you can install the biscuit.hotplug.sh script into /etc/hotplug.d/block/biscuit.hotplug to accomplish the same thing.

If your kernel was configured to support hotplug, but you don't have any of the infrastructure, you can still do the above, plus you can install hotplug.sh into /sbin/hotplug. Look for /proc/sys/kernel/hotplug on your embedded host. If it exists, your kernel is built to support it. If its contents are blank, then you need to tell the kernel to invoke /sbin/hotplug by echo-ing that string into /proc/sys/kernel/hotplug every time you boot your system, or rebuild your kernel configured to do this automatically.

There are some caveats you would be wise to heed.

Once biscuits are released into the wild, you must assume that they will go feral. People will dig up a USB drive you gave them years before, and insert it into a system. They may do so out of desperation, remembering that this did something useful long ago. Or they may simply have forgotten where the drive came from and don't even know that there is a biscuit on it. This is the dark side of biscuits: they are effectively viruses.

Biscuit scripts deal with the former by being paranoid: for example, before loading new firmware on a system, the script makes sure that the system isn't already running an even newer version of the firmware. I have also written scripts that deleted the original encrypted file from the USB drive, making it a use once biscuit. Or the script dropped an identifying file on the USB drive (I like using a MAC address from the host embedded system as a file name), and checked for the presence of this breadcrumb first whenever it runs to check whether it has passed this way before. This approach works well because the user can delete the breadcrumb manually to force the biscuit to rerun.

If you include collateral material on the USB drive, for example scripts, shared libraries, binaries, data, try hard to put it inside the biscuit. I have seen scripts that invoked another script in cleartext on the USB drive outside of the encrypted file. This allows a villain to simply rewrite the cleartext script to do whatever they want, like starting a root shell on the console, subverting the authentication and authorization provided by the encryption. Sometimes the collateral is simply too large to put inside the biscuit because of limits in available temporary storage, which on embedded systems is often RAM disk, into which the biscuit binary file is unpacked. If that's the case, put checksums or hashes (I like MD5 or SHA-1) of the collateral inside the biscuit and have the script verify the likely integrity of the collateral before using it.

Similarly, use some care when the biscuit script executes commands that are on the embedded host. This is of course typically done, for example running fundamental stuff like bash. But don't run scripts or binaries that can be altered by unprivileged users. Your security is only as good as that of your root password.

It is important that you build both the build server gpg and the host embedded system gpg from the same GNUPG source tree. You must not assume that different versions of GNUPG are interoperable. That may be the case, but if it isn't you'll end up creating biscuits on your build server that your embedded hosts can't use. If you do upgrade to a new version of GNUPG on your build server while you have deployed embedded hosts using the older version, be very thorough in your interoperability testing.

Once you build keys and have installed them on embedded hosts, check the keys into source code control or otherwise archive them. You will not get the same keys if you generate them again, even if you use exactly the same parameters. Again, you can render biscuits unusable if you are not careful. However, with some not too mad skills, you can recover lost keys from your deployed embedded systems themselves should a crisis occur.

Be paranoid about your keys, not just on the build server, but on your embedded hosts too. On the embedded hosts, which may be deployed into the field and hence presumably beyond your physical control, the keys and the directory that holds them should be accessible only by root. Unprivileged users should use sudo to run the biscuit command manually, if they can do so at all.

But with some care, biscuits are a means of safely automating a variety of system maintenance functions without giving away the keys to the kingdom or forcing end users or even application developers to become embedded systems programmers. For complex tasks like software update, they are a way of implementing complex logic and making it a part of the software distribution package, not part of a command in the embedded host itself.

Hidden Variables

2011-07-27T17:03:00.003-06:00

Ever wonder what preprocessor symbols your GNU C and C++ compiler automatically includes in your program? I'm talking about symbols above and beyond those specified in the ANSI C and ISO C++ standards, like __FILE__, __LINE__, __func__, and __cplusplus. Having gotten bit by this once or twice, I've learned it pays to know these things. Try

gcc -dM -E - < /dev/null

or

g++ -dM -E - < /dev/null

which produce the same set of #define lines for me.

#define __DBL_MIN_EXP__ (-1021)

#define __FLT_MIN__ 1.17549435e-38F

#define __CHAR_BIT__ 8

#define __WCHAR_MAX__ 2147483647

#define __GCC_HAVE_SYNC_COMPARE_AND_SWAP_1 1

#define __GCC_HAVE_SYNC_COMPARE_AND_SWAP_2 1

#define __GCC_HAVE_SYNC_COMPARE_AND_SWAP_4 1

#define __DBL_DENORM_MIN__ 4.9406564584124654e-324

#define __FLT_EVAL_METHOD__ 2

#define __unix__ 1

#define __DBL_MIN_10_EXP__ (-307)

#define __FINITE_MATH_ONLY__ 0

#define __GNUC_PATCHLEVEL__ 3

#define __DEC64_MAX_EXP__ 385

#define __SHRT_MAX__ 32767

#define __LDBL_MAX__ 1.18973149535723176502e+4932L

#define __UINTMAX_TYPE__ long long unsigned int

#define __linux 1

#define __DEC32_EPSILON__ 1E-6DF

#define __unix 1

#define __LDBL_MAX_EXP__ 16384

#define __linux__ 1

#define __SCHAR_MAX__ 127

#define __DBL_DIG__ 15

#define _FORTIFY_SOURCE 2

#define __SIZEOF_INT__ 4

#define __SIZEOF_POINTER__ 4

#define __USER_LABEL_PREFIX__

#define __STDC_HOSTED__ 1

#define __LDBL_HAS_INFINITY__ 1

#define __FLT_EPSILON__ 1.19209290e-7F

#define __LDBL_MIN__ 3.36210314311209350626e-4932L

#define __DEC32_MAX__ 9.999999E96DF

#define __SIZEOF_LONG__ 4

#define __DECIMAL_DIG__ 21

#define __gnu_linux__ 1

#define __LDBL_HAS_QUIET_NAN__ 1

#define __GNUC__ 4

#define __FLT_HAS_DENORM__ 1

#define __SIZEOF_LONG_DOUBLE__ 12

#define __BIGGEST_ALIGNMENT__ 16

#define __DBL_MAX__ 1.7976931348623157e+308

#define __DBL_HAS_INFINITY__ 1

#define __DEC32_MIN_EXP__ (-94)

#define __LDBL_HAS_DENORM__ 1

#define __DEC128_MAX__ 9.999999999999999999999999999999999E6144DL

#define __DEC32_MIN__ 1E-95DF

#define __DBL_MAX_EXP__ 1024

#define __DEC128_EPSILON__ 1E-33DL

#define __LONG_LONG_MAX__ 9223372036854775807LL

#define __SIZEOF_SIZE_T__ 4

#define __SIZEOF_WINT_T__ 4

#define __GXX_ABI_VERSION 1002

#define __FLT_MIN_EXP__ (-125)

#define __DBL_MIN__ 2.2250738585072014e-308

#define __DECIMAL_BID_FORMAT__ 1

#define __DEC128_MIN__ 1E-6143DL

#define __REGISTER_PREFIX__

#define __DBL_HAS_DENORM__ 1

#define __NO_INLINE__ 1

#define __i386 1

#define __FLT_MANT_DIG__ 24

#define __VERSION__ "4.4.3"

#define __DEC64_EPSILON__ 1E-15DD

#define __DEC128_MIN_EXP__ (-6142)

#define __i486__ 1

#define unix 1

#define __i386__ 1

#define __SIZE_TYPE__ unsigned int

#define __ELF__ 1

#define __FLT_RADIX__ 2

#define __LDBL_EPSILON__ 1.08420217248550443401e-19L

#define __SIZEOF_PTRDIFF_T__ 4

#define __DEC32_SUBNORMAL_MIN__ 0.000001E-95DF

#define __FLT_HAS_QUIET_NAN__ 1

#define __FLT_MAX_10_EXP__ 38

#define __LONG_MAX__ 2147483647L

#define __DEC128_SUBNORMAL_MIN__ 0.000000000000000000000000000000001E-6143DL

#define __FLT_HAS_INFINITY__ 1

#define __DEC64_MAX__ 9.999999999999999E384DD

#define __CHAR16_TYPE__ short unsigned int

#define __DEC64_MANT_DIG__ 16

#define __DEC32_MAX_EXP__ 97

#define linux 1

#define __LDBL_MANT_DIG__ 64

#define __DBL_HAS_QUIET_NAN__ 1

#define __WCHAR_TYPE__ int

#define __SIZEOF_FLOAT__ 4

#define __DEC64_MIN_EXP__ (-382)

#define __FLT_DIG__ 6

#define __INT_MAX__ 2147483647

#define __i486 1

#define __FLT_MAX_EXP__ 128

#define __DBL_MANT_DIG__ 53

#define __DEC64_MIN__ 1E-383DD

#define __WINT_TYPE__ unsigned int

#define __SIZEOF_SHORT__ 2

#define __LDBL_MIN_EXP__ (-16381)

#define __SSP__ 1

#define __LDBL_MAX_10_EXP__ 4932

#define __DBL_EPSILON__ 2.2204460492503131e-16

#define __SIZEOF_WCHAR_T__ 4

#define __DEC_EVAL_METHOD__ 2

#define __INTMAX_MAX__ 9223372036854775807LL

#define __FLT_DENORM_MIN__ 1.40129846e-45F

#define __CHAR32_TYPE__ unsigned int

#define __FLT_MAX__ 3.40282347e+38F

#define __SIZEOF_DOUBLE__ 8

#define __FLT_MIN_10_EXP__ (-37)

#define __INTMAX_TYPE__ long long int

#define i386 1

#define __DEC128_MAX_EXP__ 6145

#define __GNUC_MINOR__ 4

#define __DEC32_MANT_DIG__ 7

#define __DBL_MAX_10_EXP__ 308

#define __LDBL_DENORM_MIN__ 3.64519953188247460253e-4951L

#define __STDC__ 1

#define __PTRDIFF_TYPE__ int

#define __DEC64_SUBNORMAL_MIN__ 0.000000000000001E-383DD

#define __DEC128_MANT_DIG__ 34

#define __LDBL_MIN_10_EXP__ (-4931)

#define __SIZEOF_LONG_LONG__ 8

#define __LDBL_DIG__ 18

#define __GNUC_GNU_INLINE__ 1

Value Subtract

2011-07-23T11:33:00.007-06:00

Back in the mid 1990s I spent a few years as a manager at the National Center for Atmospheric Research, a national lab that was chock full of supercomputers and smart people. Apparently I wasn't one of the smart people. It wasn't the first time I'd made the career misstep to go into management. This is how I came to understand that I added no value to that organization while I was in that role.

I went off to the People's Republic of China for a month on a scientific exchange program sponsored by the U.S. National Science Foundation and it's PRC counterpart. This was a pretty major departure, pun intended. Nowadays I'd probably be able to keep up just carrying my Blackberry world phone and maybe my iPad. But way back then I was effectively cut off for a month pretty much from the entire English speaking and writing world.

Before I left, I programmed my desktop Solaris workstation to reply automatically to all of my incoming electronic mail, while filtering, categorizing, and filing it all away. At the time, I got maybe seventy email messages a day. That may seem like a low volume now, but remember this was BS, Before Spam, before the general public at large had access to electronic mail.

I had many adventures in China. I gave several talks. I kept a journal. I took photographs. It was like being on another planet. My journal could be read as a first contact story.

I returned to my office a month later, twelve pounds lighter and sporting a beard. I discovered that I had botched my email script. It had thrown all of the incoming email away. All of it. An entire month's worth of vitally important information consisting of status and problem reports, conference and request for proposal announcements, meeting summaries, vendor pleas, and cover their ass memos. All gone.

Here is what I learned in the days and weeks to come: it didn't matter. It never mattered. Ever. I never needed to know what was in any of those electronic communiques.

Perhaps you might have chosen to interpret this as a reflection on the low value of most of that email. Or on my ability to come back up to speed quickly. But I figured it meant I had actually very little to contribute to this organization, which for the most part ran just fine without me while I was gone for a twelfth of a year. If I wanted to make a difference, it was time for me to find something else to do with my life.

So I did. I quit that job just a few months later when an opportunity came along to join Bell Labs and return to being a technologist. I didn't fully appreciate at the time the impact, positive for the most part, this move would have on my career. And of course that job change would bring with it its own major life lessons.

But those are stories for another day.

Cyberspace Is The Next Battlefield

2011-07-19T15:21:00.009-06:00

The U.S. Department of Defense just released an unclassified version of the document Department of Defense Strategy for Operating in Cyberspace. Yes, this is what I read for fun. It's only thirteen pages long. It's worth a look.

This very readable document outlines five strategic initiatives in how the DoD is going to deal with threats on the battlefield of cyberspace. But it's not really the initiatives I'm so concerned with. I like getting some insight into what this over half a trillion dollar agency is actually worried about and where they are likely to be spending their money. When it comes to technology, I feel about the DoD the way I do about high performance computing and the big cloud providers: whither they go, soon I shall be.

Here are some snippets from the document that caught my eye. Emphasis is mine.

Low barriers to entry for malicious cyber activity, including the widespread availability of hacking tools, mean that an individual or small group of determined cyber actors can potentially cause significant damage ... Small-scale technologies have an impact disproportionate to their size ... (p. 3)

The potential for small groups to have an asymmetric impact in cyberspace creates very real incentives for malicious activity. ... Whether the goal is monetary, access to intellectual property, or the disruption of critical DoD systems, the rapidly evolving thread landscape presents a complex and vital challenge for national and economic security. ... (p. 3)

... DoD is particularly concerned with three areas of potential adversarial activity: theft or exploitation of data; disruption or denial of access or service ...; and destructive action including corruption, manipulation, or direct activity ... (p. 3)

... computer-induced failure of power grids, transportation networks, or financial systems could cause massive physical damage and economic disruption. (p. 4)

When I've seen the term asymmetric warfare in the past, it has usually been used in the context of a high-technology opponent versus a low-technology opponent, or adversaries using traditional versus guerrilla strategies. But it applies here in an economic sense: it doesn't take a weapons program the scope of the Manhattan Project to bring economic ruin in the realm of cyberspace.

The Stuxnet worm completely changed the way I think about threats. Although it was surely an expensive program, requiring huge amounts of technical talent, the impact it had on Iran's nuclear program was surely disproportionately large compared to its cost. It is not hard to imagine either state or non-state actors bringing similar talent to bear on other critical technical infrastructure in the U.S. or elsewhere.

At a recent conference, I got chills thinking what malware inspired by Stuxnet could do if it infiltrated the firmware of tape drives used in a mass storage system. Don't laugh: most of the data in the world is still stored in tape. Son of Stuxnet could modify or remove data as it is being written to tape or as it is read back. This could render ground installations invisible in satellite photographs or accounts untraceable in financial records. A colleague of mine quipped that this kind of thing already happens by accident due to firmware bugs. The idea of it happening deliberately with specific intent is alarming.

... Every year, an amount of intellectual property larger than that contained in the Library of Congress is stolen from networks maintained by U.S. businesses, universities, and government departments and agencies. ... military strength ultimately depends on economic vitality ... (p. 4)

... Many U.S. technology firms outsource software and hardware factors of production, and in some cases their knowledge base, to firms overseas. Additionally, increases in the number of counterfeit products and components demand procedures to both reduce risk and increase quality. ... (p. 9)

Globalization is here to stay. That means it's now more important than ever to manage your supply chain and understand where your parts, both software and hardware, are really coming from.

... DoD's acquisition processes and regulations must match the technology development life cycle. With information technology, this means cycles of 12 to 36 months, not seven to eight years. ... DoD will be willing to sacrifice or defer some customization to achieve speedy internal improvements. ... (p. 11)

In Product Development as War Fighting I applied the principles espoused by the late John Boyd, the U.S. Air Force officer who revolutionized both air and ground combat, to software development. The kind of rapid iteration that this document discusses is just the kind of thing Boyd was talking about about when he referred to fast transients and his Observe, Orient, Decide Act (OODA) cycle in combat. Victory goes to the opponent who can make the correct decision and act upon it the most quickly. This applies to the choice of technology and its deployment as well.

If your organization is developing its own strategy to deal with information security, it is worth your time to read this document and see if they thought of something that you missed. For sure, they have a lot more eyes on the problem.

Smaller Is Better

2011-07-16T11:18:00.004-06:00

The desktop that I use for software development is an Apple Mac Mini. It's mostly an X window server for a couple of Linux systems that are my build and repository servers. Below you can see the tiny silver Mac Mini sitting on a shelf above the Cinema Display.

Here are the servers in the basement, next to a spare LCD display, a honking big H-P full duplex color laser printer, and two two-drawer fire-rated filing cabinets. My backup strategy is as follows: I backup my two principle laptops, a MacBook Air and a ThinkPad X61t, to USB disk drives; I backup the two servers by doing disk-to-disk copies to removable disk drives; I do smaller incremental backups to media like CD and DVD ROMs and USB thumb drives; I also keep backups of individual projects on an off-site server.

The backups are kept in one of the fire safe drawers. When I travel, any of the laptops that don't travel with me also go into the drawer. The ThinkPad actually fits in a file folder. The Air doesn't quite fit, but there is enough clearance for it to just sit length-wise on top of the file folders.

On a recent trip I was just taking my Blackberry and my iPad. Both laptops went into the safe. I was regretting not having done a recent backup of my desktop system, when I realized I was thinking about this all wrong. The Mac Mini is small. Really small. File folder small.

All of the connectors on the business end of the Mini disconnect easily.

This makes it trivial to shutdown my desktop, disconnect it from the network, display, and USB cables, and place the entire desktop system in a file folder in the fire safe, leaving the cables velcro-tied together and just dangling.

Good luck doing that with a standard-sized white box PC cabinet.

Smaller is better.

We've all got time enough to cry.

2011-07-06T09:00:00.008-06:00

David Finkleman and his colleagues have published an article, "The Future of Time: UTC and the Leap Second", in the July-August 2011 issue of American Scientist (Vol. 99, No. 4, pp. 312-319; also: here and here) on the proposal by the Radiocommunications Sector of the International Telecommunications Union (ITU-R) to cease adding leap seconds to Coordinated Universal Time (UTC) so that it would no longer be kept in sync with the earth's rotation. The ITU-R organization is proposing this because it's just too hard.

GPS time already forgoes the use of leap seconds, and as a result, just in the time that GPS time has existed, the wall clock time we know from the rotation of the Earth, slowing due to the drag caused by the lunar tides, has drifted fifteen seconds from the time GPS keeps through the use of its atomic clocks. Hardware and software that displays wall clock time, but which synchronizes to GPS time, has to keep track of those missing leap seconds and add them back in. If such a change were to be made, it would mean UTC would be completely abstracted away from the wall clock time we use on a day to day basis.

Is this a good thing, or a bad thing? I don't know. But it sure as heck is not a minor thing. I got into the study of time for two reasons: it turned out to be critical to many of the products I've worked on in the past two decades, and much of the software I've used gets it wrong. UTC diverging from the wall clock time we use to manage our systems will only make this harder.

I've added an update to my 2006 article on date and time keeping "Does anybody really know what time it is?".

Data Remanence and Solid State Drives

2011-06-20T08:10:00.033-06:00

Deep in the subterranean bowels of the Palatial Overclock Estate (a.k.a. the Heavily Armed Overclock Compound) is a box containing every disk drive from every computer that has ever graced our home. There is another box containing every personal digital assistant, every mobile phone, and any other device featuring persistent read-write storage that may contain personal information about myself or Mrs. Overclock.

We're not paranoid. We're just thinking clearly.

The issue here is data remanence: how to insure that data has really been erased from a storage device. Data that may contain passwords, account numbers, records, schedules, notes, and anything else that could be used and misused by a miscreant, a competitor, or a court of law.

We're not the only ones concerned about this. Mrs. Overclock, a.k.a. Dr. Overclock, Medicine Woman, has to carefully conform to regulations and laws concerning the privacy of the personal medical records of her patients, and that includes computerized medical records. Several times I've been on site at a major financial firm back east whose privacy policies to deal with their clients' personal financial data required their security people to roam their multi-building campus and confiscate any device, ranging from laptop to thumb drive, that was left unsecured and unattended at some poor careless slob's desk. And it seems like every day brings another news story about someone who bought a used computer only to discover that it contained a fascinating wealth of personal data from the previous owner.

I'm writing this article on my beloved MacBook Air, a slim, light, beautifully designed laptop. It is the first laptop I've ever used that does not contain a rotating disk like my other laptops and desktops. I'm using the term "rotating" here quite deliberately to refer to traditional disk drives that have rotating platters that store information magnetically. Nor does it have flash memory, which is a semiconductor device that stores data even when powered off but unlike a rotating disk has no moving mechanical parts, like my personal digital assistants. Instead it has a hybrid device: a solid-state drive (SSD). An SSD stores data persistently in a semiconductor device with no moving parts but which emulates a traditional rotating disk drive. This allows the SSD to be used transparently (more or less, as we shall soon see) in applications which expect a disk drive.

SSDs offer extreme ruggedness, lower power consumption, and potentially much higher performance than rotating disk drives, albeit at a much higher price. This makes them attractive in applications ranging from hand-held portable devices such as mobile phones and laptops (where the attraction is principally the ruggedness and lower power consumption) to very high end servers (for the performance and lower power consumption). At the same time, SSDs bring exciting, some might say terrifying, new issues to the realm of data remanence. To understand why, we have to briefly look at other forms of digital storage, and kind of sneak up from behind on how SSDs actually work on the inside.

Rotating Disks and Tapes

Rotating disks and tapes are inherently mechanical devices that store data magnetically and have to go through a lot of drama involving moving parts which you never see to read and write your data. While they require power to read and write, when powered-off they are capable of storing data for a long long time, years or even decades, without significant degradation. With some extremely expensive equipment you can actually see the tiny magnetic dots that form the bits of your data. How tiny? Modern magnetic media store many gigabits per square inch. A single disk or tape that you can hold in your hand can store several terabytes of data. A terabyte is a million million bytes. That's a lot of bytes.

Both rotating disks and tapes store data in a chunk or block of bytes, and the disk or tape drive reads or writes an entire block at a time. A typical disk drive like you have in your laptop stores data in fixed sized blocks of 512 bytes each. Lots of software, including the operating system running on your laptop, was designed, implemented, and optimized under the assumption on the data being stored in 512 byte blocks. This assumption will become important when we look at SSDs.

Both rotating disks and tapes incur a lot of latency in both read and write operations. In the case of a random read or write to a rotating disk, a mechanical arm containing a read-write head has to swing laterally across the surface of the magnetic platter to be positioned over the correct cylinder where the data resides, and then wait for the correct sector where the data resides within the cylinder to travel beneath the head as the platter rotates. These two delays are referred to as the seek latency and the rotational latency respectively, and together can amount to several milliseconds. Tapes incur seek latency as well, but since tapes are typically used for strictly sequential reads and writes, and tape drive hardware and software is optimized to keep the tape moving, tape drives can and typically do out perform disk drives in terms of raw read and write performance. Only a mad man, or someone with lots of time on their hands, uses tapes for random reads and writes. I've done it.

With rotating disk drives and tapes, the issue of data remanence has been explored thoroughly since the 1960s. The gold-standard in paranoia is the U.S. National Security Agency (NSA), whose publicly available document on this topic, the Storage Device Declassification Manual, recommends degaussing a disk or tape, that is, using a strong electro-magnetic to disrupt the magnetic properties of the media, then physically damaging the drive so that it is a little more obvious to the casual observer that it cannot be used. In both cases, incineration is a second option. Other sources recommend dropping the disk drive in an industrial shredder that reduces it to tiny metal bits.

Note that merely deleting a disk file is entirely inadequate. As everyone who has not been living in a cave realizes, deleting a file merely deletes its metadata, its name and information about its location on the disk, from a directory that is also stored on the disk. It may not even do that; it may just mark the file as deleted, leaving all the metadata at least temporarily in place. Unless you are using some very clever software, the data bits in the original file are all still on disk, where they can be recovered by some even cleverer software, as a lot of crooked politicians, child pornographers, and bent accountants have all discovered to their woe.

To truly erase a file from disk or tape, you must write new bits directly over the old bits of the file. This will keep all but the most motivated and technically advanced individuals from recovering the data. But there as been a lot research that has shown that even then, some, many, or even most of the overwritten bits can be recovered, or at least inferred with a high degree of certainty, using devices like electronic microscopes. Which is exactly why the NSA requires destructive degaussing if not outright incineration. Nuke it from orbit. It's the only way to be sure.

Random Access Memory

Random access memory (RAM) is a semiconductor device, a hunk of metal and silicon, with no moving parts. It is used to store data and software temporarily while it is in active use. RAM is what software developers mean when they say "memory". RAM stores data reliably only as long as power is applied to it. Although we think of RAM as been read or written a byte at a time, modern memory systems only read and write a word at a time to a single RAM device, where a word might be two, four, or even eight bytes in width. There is a lot of hard-wired logic in current microprocessors to handle the conversion between byte access and word access.

The NSA seems quite confident that RAM data is not recoverable after loss of power. However, there has been some research regarding supercooling certain types of RAM right at power off, then using yet more extremely expensive devices to read or infer the bits from the deeply frozen device. As paranoid as I am, I can't say I'm concerned about data remanence in RAM. But people who are looking at the ability to extract secret keys from cryptographic devices that are used, for example, in automated teller machines, are.

Flash Memory

Like RAM, flash memory is also a semiconductor device with no moving parts. It stores your data at the atomic level, as electrons that are trapped in the physical material of the device. Like rotating disk drives, flash memory is persistent, maintaining its data after being powered off. Data storage in flash memory isn't permanent, and its longevity isn't measured in decades like that of the magnetic storage of rotating disks or tapes. But it takes years for the electrical charges stored in a flash device to bleed out, long after you have upgraded to a larger thumb drive.

There are broadly two kinds of flash memory: NOR flash and NAND flash. NOR (literally "not or") and NAND ("not and") describe the kinds of logical operations the device emulates in its very low level operation. That's of less interest to us here than the other properties that make NOR and NAND flash differ from one another, and that makes flash memory of either variety very different from rotating disks, tapes, or even RAM.

NOR flash can read just like like random access memory: data in memory are referenced directly using just an address and hence read by software without much drama. In fact, if the hardware and operating system is suitably designed, software programs can be executed directly out of NOR flash where the system is none the wiser as long as it doesn't try to write to the NOR flash as if it were RAM. This capability is called execute in place (XIP).

NOR flash is written more like a disk drive: commands are sent to a hardware controller implemented inside the NOR flash device that writes data a fixed-sized page at a time. The size of a single flash page depends on the specific flash device, but typical sizes are two or four kilobytes, or several times the size of a typical logical disk block. So you can't just write a single byte or even word of NOR flash. You have to write an entire page, and you have to go through a pretty arcane series of steps to do it. That's how NOR flash differs functionally from RAM, and is also why NOR flash is used as a read-only memory (ROM).

NAND flash extends this disk drive-like interface to both writing and reading. Writes and reads to and from NAND flash is done in a fixed sized page of bytes at a time. Unlike NOR flash, you can't just read a single word. That's how NAND flash differs functionally from NOR flash.

Now here's how both NOR and NAND flash differ from everything we've talked about so far. Whereas blocks on disk and tapes, and words on RAM, can be read, written and over-written, flash memory of either variety requires a third operation: erase. This isn't an optional operation like exists in some disk or tape drives that overwrites existing data. A write operation in flash can only change a binary one to a binary zero. That's how it works right down at the atomic level.

If you want to change the value of that bit, you first have to erase it, turning it back into a binary one. A virgin flash device right from the factory will read as all binary ones, because it arrives at your door in the fully erased state. When you write to it a page at a time, the silicon is selectively turning ones to zeros in the semiconductor media of the flash device. If you want to turn zeros back into ones, you must first erase. Furthermore, an erase operation is done not a page at a time, but a block at a time. The size of a flash block again depends on the specific flash device, but a typical size is 128 kilobytes, many times the size of a flash page.

You can see this is getting complicated. You read and write pages, but you erase blocks, and you must erase an entire block in order to write over even a single page within that block. But it gets worse. Erases don't come for free. Every time you erase a block in a flash device, you are actually permanently altering the device. Do enough erases and eventually the flash device quits working. Unlike RAM and other semiconductor devices, flash wears out. And yes, this applies to consumer devices that use NAND flash, like a USB thumb drive or your tiny digital music player.

Again broadly speaking, flash memory is manufactured in two basic flavors: single-level cell (SLC), and multi-level cell (MLC), depending on how many bits are stored in each flash cell, the basic unit of flash storage. SLC stores a single bit, MLC more than one bit. SLC can endure about a hundreds of thousand erase cycles of each block before it quits working. MLC can endure about a tenth of that amount. On a price per bit, SLC is much more expensive, so most of the flash you find in consumer devices is MLC.

In terms of data remanence, both the NSA and I are pretty confident that when you erase a flash block, whether it be of the NOR or NAND variety, you run very little risk of that data ever being recovered.

Solid State Drives

Flash memory, and in particular NAND flash, fills in interesting niche in the ecosystem of persistent digital storage devices. A read of a page of NAND flash takes on the order of tens of microseconds, making it a thousand times faster than a rotating disk drive with all the mechanical bits it has to move. The write of a page of NAND flash takes on the order of hundreds of microseconds, still pretty good. But the erase of a block of NAND flash takes on the order of thousands of microseconds, meaning milliseconds. Not so good.

It is NAND flash that is used in SSDs. Underneath the hood, SSDs are one or more NAND flash devices on top of which is layered a very smart (or in my personal experience, sometimes not so smart) controller that tries to make the NAND flash look like a rotating disk drive. This is no small feat, since the controller has to emulate the disk by handling application reads and writes in 512 byte blocks, while physically reading and writing two or four kilobyte pages, erasing 128 kilobyte blocks, and trying its best to hide the hideous erase latency inherent in the flash device.

This real-time juggling act is the responsibility of what is generically referred to as the flash translation layer (FTL). The FTL has the following sometimes contradictory goals: transparently map logical disk blocks to pages of flash; hide the write page and most especially the erase block latency; and even out erasing and writing across the entire device so that all erase blocks wear at more or less at the same rate, a process that is called wear leveling. All of these goals are accomplished through an interlocking set of design and implementation strategies in the SSD controller.

An SSD contains more flash storage capacity than the capacity of the disk drive it emulates. It uses this extra flash capacity so that it can maintain a pool of pre-erased blocks to which to write, instead of forcing the application to wait for a lengthly erase cycle to complete. This is called over provisioning. SSD vendors are for the most part quiet on the amount of over provisioning, but at a recent SSD seminar I attended one vendor quoted 28% as being typical for their SSDs.

The mapping of logical disk blocks to flash pages is completely abstract. On a rotating disk, when you write to logical block 42, you are always writing to the same logical block in the same physical location on the disk platter. Okay, this is not strictly speaking true: bad block replacement management in the disk controller firmware may map logical block 42 to a replacement block somewhere else on disk, but it is always the same replacement block. But when you write to logical block 42 on an SSD you are always writing to a completely different flash page than the last time you wrote to logical block 42.

This means the controller embedded in the SSD has to maintain a very complex and dynamic mapping of logical disk blocks to flash pages, not just because disk blocks and flash pages are different sizes, but because the mapping changes every time you think you are overwriting a logical disk block with new data. Because this mapping has to persist between power cycles on the SSD, it is stored in the very same flash device in the SSD, in overhead flash pages inaccessible to you, to be re-read the next time the SSD is powered up. These overhead flash pages are themselves subject to the same wear leveling and mapping algorithms as the flash pages that hold your data.

When you write logical disk block 42, your data is written to a flash page that was erased when the erase block of which it is a part was erased. The flash page containing the disk block formerly known as 42 is slated for eventual erasure, but it is part of an erase block that may contain flash pages that contain logical disk blocks that have not been overwritten. The SSD coalesces multiple logical disk blocks containing good data into a single flash page and updates its mapping in a process known as garbage collection. This activity and the erasure of completely unused erase blocks is a more or less constant background activity on the part of the SSD.

Because multiple disk blocks are stored per flash page, and multiple flash pages are stored per erase block, and because of the abstract mapping between disk blocks and flash pages, there are patterns of disk block writing behavior that appear to be uncorrelated from an application point of view, but that can result in the same erase block being erased and rewritten many times. This is called write amplification. Because the mapping from disk blocks to flash pages is opaque to the application, this is hard to detect, and even harder to prevent.

Flash cells can only be read so many times before the captured charge is depleted. To deal with this, the SSD controller reads flash pages containing good data and rewrites the data to a flash page in an erased block in a process called static wear leveling. This is also a constant background activity on the part of the SSD.

Write latency may be further hidden by the inclusion of a RAM buffer inside the SSD. Logical disk blocks that are read may be cached in RAM, and logical disk blocks written may be buffered in RAM until an erased flash page becomes available and they can be written. The mappings used by the SSD to keep all of this straight may also be cached in RAM and written asynchronously as time permits.

Garbage collection, static wear leveling, and cache write back are asynchronous processes inside the SSD over which you have no control, or even the ability to be aware that they are occurring, through the disk interface presented to your system by the device.

The algorithms that implement the FTL are very complex, much more complex than the relatively simple state machine controllers implemented within the flash device itself. Indeed, inside every SSD is a powerful processor core on which the FTL runs. The SSD also implements the external electrical and command interface (e.g. IDE or SATA) that allows the SSD to connect to its host system as if it were a rotating disk drive. On at least some SSDs, the firmware that implements all of this is stored in the very same flash memory inside the SSD. The SSD controller may, in some sense, boot from itself.

The integrity of not just your data, but of the mapping metadata, and of the SSD's own firmware, is of such critical importance to the stability of the SSD that vendors place capacitors on the SSD to power its operation in the event of a power failure, until the SSD can reach a stable recoverable state. Apparently this sometimes even works. But there is a lot of anecdotal evidence that it frequently does not. In his popular software development blog Coding Horror, Jeff Atwood as written several articles on his own experiences with SSDs. He loves them. For their performance. But in the article "The Hot/Crazy Solid State Drive Scale" he says:

I feel ethically and morally obligated to let you in on a dirty little secret I've discovered in the last two years of full time SSD ownership. Solid state hard drives fail. A lot. And not just any fail. I'm talking about catastrophic, oh-my-God-what-just-happened-to-all-my-data instant gigafail. It's not pretty.

The emphasis here is his. The comments for this article by his readership are similarly hair raising. There is a growing body of evidence that SSDs have to be treated with some care lest they be bricked, along with all your precious data. This is also in part why "Hard Power-Off Is Dead" will be a future article in my own blog.

But their reliability isn't my primary concern for this article. How do you deal with data remanence when using SSDs? They can't be degaussed like rotating disk drives because they aren't based on magnetic media. They can't be erased like NOR and NAND flash because even though they use NAND flash as their storage medium, they don't expose the low level flash erase function through their emulated disk drive interface.

Michael Wei and his colleagues at the Center for Magnetic Recording Research (CMRR) at U. C. San Diego very recently published a paper, "Reliably Erasing Data from Flash-Based Solid State Drives", trying to answer this question. What they found was that alternative methods of declassifying a disk drive, like overwriting all of the data on the drive, where not effective. You can overwrite every logical disk block on the drive. But thanks to RAM buffering, over provisioning, and background erasure, you can power off the SSD immediately after the overwrite operation completes, crack the SSD open, remove the flash components, plug them into a flash programming tool, and recover a significant portion of the supposedly overwritten data sitting in erase blocks pending erasure. Worse, because of the complex mapping between logical disk blocks and flash pages, sequentially overwriting the entire drive may cause erase blocks to be erased more than once, eating into the erase budget of the drive and reducing its longevity.

There is some hope. Many disk drive standards have some form of secure erase command that accomplishes the same thing as overwriting a disk block or even the entire disk. Most SSDs do not implement this command. Or, as Wei et al. point out, some say they do but it doesn't actually work. But as the SSD industry shakes out, a correct implementation of secure erase may become more common. Also, some disk drive standards have defined a trim command specifically in support of SSDs, where a logical disk block can be marked as no longer used without the necessity of writing over it. Few SSDs currently support this command, and as Wei et al. point out, even so this has no reliable effect on sanitizing an SSD. But again, as things shake out, an SSD controller might take all logical disk blocks being trimmed as a hint that all flash blocks used for logical disk block storage should be erased.

Until then, I find data remanence on solid state drives to be very problematic. SSDs are too new, alas, for the NSA to have an opinion, at least in the publicly available information to which I have access. I predict an industrial shredder will play a crucial role, making that expensive SSD even more expensive because it cannot be reused once it contains sensitive information. (I also question their use in mission critical applications because of questions concerning their reliability and stability, but that's a whole other soapbox.)

Flash-based file systems like JFFS2 and UBIFS used in Linux and other operating systems are FTLs implemented in software and that use raw flash devices. Although they have to deal with all the same issues as SSDs, data remanence isn't an problem because you have access to the low level erase functions on the flash device. You can simply unmount the file system and erase the flash using a standard utility program.

JFFS2 (and maybe UBIFS too, although I haven't had to dig into its internals) is a log-structured file system. It writes blocks not to a hierarchical structure but instead to a kind of sequential transaction journal. The file system that the application sees is the result of the file system software reading the journal and reconstructing the hierarchical file system in memory at mount time. This kind of architecture maps pretty well to flash memory. But how this is done by the FTL inside of SSDs is vendor proprietary and specific.

Given the growing popularity of SSDs, improving their performance, longevity, and reliability is an area of active research. At the 27th IEEE Symposium on Massive Storage Systems and Technologies (a.k.a. MSST 2011) conference I recently attended, there were many papers on the topic of improving FTLs or optimizing them for niche applications. Data remanence was only rarely mentioned, and then mostly by the cloud storage providers; never in the context of solid state drives.

Sources

O. Al Homaidi, Data Remanence: Secure Deletion of Data in SSDs, masters thesis, MCS-2009:3, Blekinge Institute of Technology, Sweden, 2009-02

J. Atwood, "The State of Solid State Hard Drives", Coding Horror, 2009-10

J. Atwood, "Revisiting Solid State Hard Drives", Coding Horror, 2010-10

J. Atwood, "The Hot/Crazy Solid State Drive Scale", Coding Horror, 2011-05

Department of Commerce NIST Computer Security Division, Guidelines for Media Sanitization, Recommendations of the National Institute of Standards and Technology, NIST Special Publication 800-88, 2006-09

Department of Defense, National Industrial Security Program Operating Manual (NISPOM), DoD 5220.22-M, 2006-02-28

Department of Energy Cyber Security Program, Media Clearing, Purging, and Destruction Guidance, DOE CIO Guidance CS-11, 2007-01

D. Feenberg, Can Intelligence Agencies Read Overwritten Data?, National Bureau of Economic Research, 2004-05-14

P. Gutmann, "Secure Deletion of Data from Magnetic and Solid-State Memory", USENIX Security Symposium Proceedings, 1996-07

P. Gutmann, Data Remanence in Semiconductor Devices, IBM T.J. Watson Research Center

J. Handy, SSDs in Enterprise, Embedded, and Client Applications, Objective Analysis, AvNet SSD Seminar, Westminster Colorado, 2011-05-17

G. Hughes, T. Coughlin, Tutorial on Disk Drive Data Sanitization, UCSD

M. Murugan, D. Du, "Rejuvenator : A Static Wear Leveling Algorithm for NAND Flash Memory with Minimized Overhead", Proceedings of the 27th IEEE Symposium on Massive Storage Systems and Technologies, Denver Colorado, 2011-05

National Security Agency/Central Security Service, Storage Device Declassification Manual, 9-12, (supercedes NSA/CSS Manual 130-2), 2000-11-10

National Security Center, A Guide to Understanding Data Remanence in Automated Information Systems, NCSC-TG-025, Library No. 5-236,082, Version-2

Royal Canadian Mounted Police Technical Security Branch, IT Media Overwrite and Secure Erase Products, Lead Agency Publication B2-002, 2009-05

S. Skorobogatov, Data Remanence in Flash Memory Devices, University of Cambridge, Computer Laboratory, UK

E. Spanjer, Security Features for Solid State Drivers in Defense Applications, ADTRON, 2008-03

M. Wei et al., "Reliably Erasing Data from Flash-Based Solid State Drives", Center for Magnetic Recording and Research, U. C. San Diego, 9th USENIX Conference on File and Storage Technologies, 2011-02

Wikipedia, Data remanence

Wikipedia, Flash memory

C. Wright, D. Kleiman, S. Sundhar R. S., Overwriting Hard Drive Data: The Great Wiping Controversy, Springer-Verlang, 2008

Android FroYo on the BeagleBoard xM Rev C

2011-06-13T15:18:00.008-06:00

There's a lot to like about the BeagleBoard xM compared to the BeagleBoard C4 I had been using for Contraption, my project to broker peace between the Android and GNU peoples. The xM has twice as much RAM: half a gigabyte. It has a built-in USB hub and four USB ports, eliminating the need for a separate USB hub, simplifying the attachment of a USB keyboard and mouse. It has a built-in RJ45 Ethernet port, eliminating the need for a USB Ethernet adaptor or, as I used, an expansion board like the Zippy2. And best yet, the price of the tiny xM board has come down to be the same as what I originally paid for the C4 board. This makes the xM a great platform for Contraption and for the kinds of things for which I use it.

At the time I chose to move off the C4, the currently shipping xM was the revision C board. The pre-built binaries available in the Rowboat validation port of Android FroYo to the xM did not support the rev C. In fact, neither the X-Load stage one loader, nor the U-Boot boot loader, nor the 2.6.32 Linux kernel with Android modifications, recognized the rev C board. Because the xM differed significantly in many ways from prior BeagleBoards (most significantly, in how the USB components were configured and powered), this made using the pre-built binaries from the developer's kit a non-starter.

Fortunately, I poked around and found Robert C. Nelson's patch to adapt the kernel's board support package (BSP) for the BeagleBoard to the rev C hardware. (Thank You, Robert!) And while I didn't find similar patches for X-Load or U-Boot, it was a simple thing to make the required changes to those packages as well using Robert's changes as a model. The patch files I used are now all part of the latest tarball available on the Contraption web page. As I've done in the past, I rebuilt all of the Android software and the root file system from scratch, because the graphics engine on the xM Rev C had to be built a little differently as well. This change has been incorporated into the make file.

Here's the BeagleBoard xM Rev C. Moving to the xM really cleaned up my workbench by eliminating a lot of cables and clutter. (You can click on any of the images below to open larger sizes.)

Here you can see the BeagleBoard xM rev C running Android FroYo. My desktop on the left is displaying an SSH window to Android (black on white) and a console window to the serial port on the xM board (green on black). The LCD monitor on the right is hooked to the xM and is displaying the Android browser.

Here's a photograph of the xM LCD display.

Here's a screen snapshot of the serial console. If you look closely you can see one of the things I did was change the root password using the /bin/busybox passwd applet. SSH doesn't seem happy with an empty root password.

After I SSHed into Android from my desktop and got a bash prompt, I ran the top command just to see who was doing what.

I'd like to move to the port of Android Gingerbread. But if I'm interpreting what I'm reading correctly (and please, someone, tell me I'm not), I have to run the 64-bit version of Java to build the Android software, and to do that I have to migrate to the 64-bit version of Linux on my build server. That's a pretty big leap. Might be a while.

MSST 2011

2011-05-30T11:09:00.031-06:00

Last week I attended the 27th IEEE Symposium on Massive Storage Systems and Technologies, a.k.a. MSST 2011. A couple of decades ago, when large scale storage was my field, I attended this conference annually. This year I attended it because it was a twenty-minute drive from the Palatial Overclock Estate (what the media insists on calling the Heavily-Armed Overclock Compound) and because it was being held at the Brown Palace Hotel, a stunning Victorian-era historic fixture in downtown Denver Colorado. It was also a good excuse to catch up on the state of the art.

Back when I was a regular at this conference, large meant terabytes, which is kind of remarkable considering today you can trivially buy a terabyte disk drive at your local big box store. Nowadays, large means exabytes; a single tape cartridge can hold several terabytes, and a single robotic tape library can hold thousands of tape cartridges.

Applications of storage on the exabyte scale falls into a variety of categories, such as long term archiving of data from observations and experiments (e.g. weather observations going back decades, satellite imagery, results from experiments with particle colliders, DNA sequencing of individuals); short or long term storage of output of applications running on high performance computers; and cloud storage much of which is driven by the consumer space. All of these domains were represented at this international conference, with speakers and attendees from national laboratories and agencies, storage vendors, cloud users and providers including Yahoo!, and academic and corporate researchers doing original work in this area.

Here are some of the notes I wrote down while attending this week-long conference. All original ideas are those of the speakers; all interpretations, and misinterpretations, are mine. And don't be surprised if some of these contradict one another. The notes are in chronological order. You can find a complete list of the papers, speakers, and panels from whence they came here.

Geoff Arnold/Yahoo!: Cloud storage: trends and questions

10x Effect: refers to the observation that scaling your application by a factor of ten requires that you to re-architect it.

Trend: deployment of components used in mass storage systems from enterprise-grade devices to consumer-grade devices. The consumer-grade devices may be less reliable, but you have to accommodate failures even in enterprise-grade devices anyway, and the consumer-grade devices offer better price performance.

Fail-in-place: strategy where when something fails, you don't replace it, you just power it off, and let the system work around it. It will be replaced anyway by the next technology refresh, which happen so often that replacing a failed component with the same technology isn't worth the cost.

RAID (Redundant Array of Inexpensive Disks) is dead. Instead: JBOD (Just a Bunch Of Disks, or Just a Box Of Drives), with geographic replication for reliability. Part of the problem with RAID is that they don't scale: they appear to be one I/O device with one serialized command queue, where as commands to JBODs can be more parallelized.

SAN (Storage Area Network, not to be confused with Network Attached Storage) is dead. Instead: converged networks using a single interconnect fabric. (But there were lots of folks proposing SAN architectures, too.)

Immutable objects: the concept where once an object is stored, it is never modified, except perhaps to be deleted. This vastly simplifies the storage system design. (This is very similar to the idea of single-assignment in programming languages, where variables can never be changed once assigned. As bizarre as this sounds, it's quite workable. I implemented a single-assignment programming language as part of my master's thesis, and another graduate student implemented a Prolog interpreter in my language.)

POSIX file semantics are dead, because they don't scale. The big problems are file locking and file modification. Instead: the future scalable storage interface will be RESTful, implementing HTTP-like operations limited to GET, PUT, POST, and DELETE and operate on objects instead of files and blocks.

Trend: movement from synchronous to asynchronous operations, because the former don't scale. One of the reasons POSIX file semantics are dead is we have to give up the API that has "an implicit guarantee of transactional consistency". Eventual consistency scales.

Trend: replacing MTBF (Mean Time Between Failures) with MTTR (Mean Time To Recover). The former doesn't scale. You have to design your system around the assumption that devices will fail, and optimize your ability to recover from those failures. (The routing architecture of the Internet Protocol was based on this concept, and the telecoms have been making this assumption for decades, for exactly the same reasons. I have also been attending an exascale computing conference, sponsored by the U.S. Department of Energy, for the past couple of years. To scale up to an exascale supercomputer with commodity memory chips, the MTBF calculation suggests that such a system will suffer a RAM chip failure every few minutes.)

Trend: replacing a "predictable business model" with one of "chaotic innovation". (I wish the speaker had said more about that. But I like the premise. It fits in well with my own reading on asymmetric warfare and John Boyd's OODA loops.)

Trend: replacing human operators with automation and self-service. The former doesn't scale. Sun Microsystems was quoted as observing that "the largest source of failures in the data center was humans opening the door".

Cloud computing requires operational refactoring: outsourcing lower portions of the application stack, taking advantage of economies of scale, implementing service level agreements, and leverage specialization on the part of your provider.

Virtualization is a nightmare for security. Hypervisor vulnerabilities are the major concern. No matter how bullet proof your application stack is, once you run it in a virtual machine, all bets are off. VMs make the cloud providers very very nervous. (This was a recurring theme.)

People get nervous about cloud computing, yet there are centuries of precedence in outsourcing critical infrastructure. You put all your money in a bank, and that's your money, for pete's sake. Not to mention hospitals, delivery services, lawyers, etc.

Stovepiped: when your application stack is vertically integrated. This is a problem when moving to cloud architectures since doing so means migrating the lower portions of the stack into the cloud. To gain efficiencies of scale requires cloud vendors to provide basically the same generic services to everyone. (That was a new term for me.)

The recent failure of Amazon.com's storage system was not in their S3 cloud computing service, which has RESTful semantics, but in their Elastic Block Storage (EBS), which has POSIX semantics. And even then, the failure fell within their Service Level Agreement. Cloud storage architects point to this as an example of why POSIX semantics don't scale.

On moving part of your application stack into the cloud: "Until a new airliner crashes, you have have no idea what will happen when that airliner crashes".

Trend: cloud providers have tended to optimize their stacks for "north-south" traffic (vertical within the stack) but are seeing a lot of growth in "east-west" traffic (horizontally between applications within the stack).

We need to automate systems originally designed for human time scales. An example of this is the internet's Domain Name System (DNS), which was designed to be updated by a human using a command line interface, not by automated systems in clouds registering and deleting many domains per second.

Joshua McKenty/Piston Cloud Computing: Openstack: cloud's big tent

Trend: moving computing closer to or even into the storage environment. This becomes more important as the datasets get larger. (This was reiterated time and again by many speakers.)

Tombstoned: destined or marked for deletion.

Patrick Quaid/Yahoo!: Lessons learned from a global DB

Trend: the cloud stack becomes (from the top down): SaaS (Software as a Service), KaaS (Knowledge as a Service), PaaS (Platform as a Service), IaaS (Infrastructure as a Service).

Trend: in social networking, the movement from "me-view" to "we-view". (I interpreted this to mean applications leveraging crowd sourcing.)

Cloud providers have found that implementing big-market infrastructures is wasted in developing markets. Once size does not fit all.

You can't retrofit consistency into your architecture.

Data remanence: how do you guarantee the data is deleted? In the domains like defense, finance, and medicine, there are legal requirements to ensure that deleted data cannot be recovered (particularly by the wrong parties). This is especially troublesome given the trend of geographic replication. You could encrypt the data and later delete the keys, but there is no guarantee that the keys themselves are not recoverable, and also no legal precedent that such a strategy is adequate. On the flip side, there are opposing legal requirements to ensure that some data flows can be wiretapped.

Scale: billions of records, ~600,000 users, one million reads per second, ~500,000 writes per second.

Sean Roberts/Yahoo!: Implementation problems and design principles

Black swan events: singularities like the death of Michael Jackson, the Royal Wedding.

No-ops are the enemy.

Chris King/Linkedin: Storage infrastructure design and management at scale

Google is moving from consumer-grade storage devices to enterprise-grade devices, because the latter are cheaper in the long run. Even if the enterprise-grade device lasts just a little longer before it fails, the savings in labor costs to have someone replace the device makes up for it.

Conway's Law: a system's architecture will recapitulate the bureaucracy that created it. This is a very old (circa 1968) assertion, but cloud providers have observed it in their domain.

Geoff Arnold/Yahoo!: Private clouds

Forget about the long tail; the problems are with the big head.

In a slowly changing environment, it's easy to assume some things are constant, when they in fact aren't. Result: correlators don't correlate, invariants aren't invariant. Example: IP addresses. (I've been bit by this one too. I used to use MAC addresses as a unique system identifier, until I started seeing systems in which users routinely reprogrammed their MAC addresses.)

On demand assumes that each individual customer is small compared to the entire pool of customers, and that there is no correlation of behavior among customers. These assumptions are frequently wrong.

A sufficiently large data replication process looks like a distributed denial of service (DDoS) attack.

Joshua McKenty/Piston Cloud Computing: Security

Blue Pill Attack: when the virtual machine attacks the underlying real machine. This is the opposite of the usual concern. (From the movie The Matrix, this is specifically when a real machine is compromised by it having been unwittingly virtualized, hence the attacker has wrested control of the real machine from the host operating system.)

Michael Ernst/Brookhaven National Laboratory: Experience with 30PB of data from the LHC

Storing petabytes of data is easy compared to moving petabytes of data to where it is needed. (This was a recurring theme, driving the rethinking of architecture.)

Ron Oldfield/Sandia National Laboratory: Addressing scalable IO challenges for exascale

Electrical power is the largest hurdle to exascale. At current efficiencies, an exascale system will require two gigawatts of power. Data movement is the largest user of power. (At the last exascale conference I attended someone mentioned that the Chinese have committed to building their supercomputer centers with a nuclear power plant. Everyone wonders how we'll compete with that.)

Applications use the storage system as a communications channel.

Trend: it may be more economical to recompute rather than to store. (This is theme I see recurring at all scales, from massive storage systems to variables in a single application.)

More than eighty percent of all I/O is done for reasons of resilience.

Applications today are not designed to survive failures. The larger the application, the higher the probability of failure. This is the reason for checkpoints (where the entire application state is periodically dumped to storage). As applications grow larger, and their data requirements bigger, checkpoints are increasingly expensive to generate and to store. (This is just another take on the theme that you have to expect failures and be able to recover from them.)

Asynchronous I/O still buries the network, and jitter becomes a real issue. But, storing data persistently at each intermediate stage is actually very resilient. (This was said in the context of Big Science, such as the Large Hadron Collider.)

Dave Fellinger/Data Direct Networks: Simplifying collaboration in the cloud

IDC predicts that by 2020 the world will have thirty-five zettabytes of digital storage.

There is no bandwidth faster than a 747 filled with tapes. (This is a variation on the idea that Fedex operates the highest bandwidth network in the world by virtue of overnight delivery of tapes.)

Alan Hall/NOAA: National Climate Data Center's plan for reprocessing large datasets

"80% of the world's data is on tape." (The speaker was quoting the CTO of a manufacturer of tape libraries.)

Trend: archiving the software applications along with the data that it produced or processed. The software effectively becomes part of the metadata, because it is the only formal description of the data. The application, the operating system on which is runs, and the data would all be deployed to a VM from the mass storage system.

Harry Hulen/IBM: Operational concepts and methods for using RAIT in high availability tape archives

Rule of thumb: it takes about one full time equivalent (FTE) of staff to manage every five petabytes of tape archive.

Todd Abrahamson/Imation: Tape media reliability

The black box flight recorder from the Columbia space shuttle disaster hit a tree in Texas at an estimated Mach 18. It took weeks to be found, during which time water got into the device. The data on its magnetic tape were still recoverable. (The speaker was the engineer that recovered and interpreted this data.)

Rule of thumb: current magnetic tape technologies offers about a thirty year longevity when stored at seventy degrees Fahrenheit and thirty percent relative humidity.

Current hard disk drive controller boards are tuned to the specific spindle with which they are manufactured. This makes it difficult to recover a disk whose controller has been damaged. You can't just replace the controller with one from another disk of the same model.

Panel Discussion

Trend: embed flash memory in tape cartridges so as to store metadata in the cartridge itself. (Cartridges today use an RFID chip to carry identity information.)

Economics drive tape technology migration, not reliability or longevity.

Latency means uncertainty.

The National Institute of Standards and Technology (NIST, formerly the U.S. National Bureau of Standards) defines the required archive duration for medical records as "the life of the Republic plus one hundred years".

Dimitry Ozerov/DESY: Data preservation in high energy physics

Both theory and common sense evolve over time. This requires that we periodically revisit legacy data.

Ian Fisk/Fermi National Accelerator Laboratory: Evolving WLCG data access strategy and storage management strategies

There is a 10⁸ magnitude difference in data popularity between the most and least popular datasets. (This strikes me as another example of the long tail phenomena.)

Like events tend to aggregate (be clumped together) in a dataset due to buffering, resulting in jitter in the data. This is an issue with the data is reprocessed for analysis since it is not stored in strictly the order that it occurred in the experiment. (This was said in the context of Big Science, like the Large Hadron Collider, where the raw datasets generated in real-time from a single experiment are petabytes in size.)

Panel Discussion

Funding agencies are no longer willing to pay for peak capacity. Sharing resources is necessary.

Amazon.com's Amazon Web Service (AWS) established not only that infrastructure has value, but what that value was, and it demonstrated that customers would be willing to pay for infrastructure.

Peter Braam/Xyratex: Bridging the peta- to exa-scale I/O gap

Rule of thumb for exascale storage requirements: memory capacity times thirty equals scratch space capacity, times three equals archive storage capacity per month. (I believe this was said in the context of Big Science.)

Metrics for an exascale system: 10⁸ CPU cores, 10 gigaFLOPS per core, 1 gigabyte of RAM per core, 5x10³ cores per node, 5 terabytes RAM per node, 50 teraFLOPS per node, 15 gigabytes/second I/O per node, 20x10³ nodes per cluster, 100 petabytes RAM per cluster, 300 terabytes/second I/O per cluster, file system capacity greater than 1 exabyte.

Architectures of exascale systems will have to be heterogeneous.

Dan Duffy/Goddard Space Flight Center: Alternative architectures for mass storage

NCCS, the smaller of NASA's two data centers, has enough storage for an iPod playlist 34,000 years long.

Mary Baker/HP Labs: Preserving bread crumbs

"All problems in computer science can be solved by another layer of indirection. Except for the problem of too many layers of indirection." -- David Wheeler (1927-2004) (Cited as the first person to be awarded a Ph.D. in Computer Science.)

The Japanese have developed a unique strategy for preserving their monuments: they periodically rebuild them from scratch. An example of this is the Sanctuary of Ise, in which the temple is rebuilt every twenty years on an adjacent plot using the prior temple as a model. This is also the strategy for long term data preservation: continuous renewal by coping to new media using new technology and verifying against the prior copy. (I've heard this strategy referred to as George Washington's Axe: "This is George Washington's axe. The handle rotted away so we replaced it. Then the head rusted away so we replaced that too.")

How do we communicate the value of data archives to future generations?

MTDL: Mean Time to Data Loss.

Phil Carns/Argonne National Lab: Understanding and improving computational science storage access through continuous characterization

MiB: a Mebibyte is 2²⁰ or 1,1048,576 bytes.

MB: a Megabyte is 10⁵ or 1,000,000 bytes.

Raja Appusuwamy/Free University of Amsterdam: Flexible, modular file system virtualization in Loris

Trend: designing a storage stack in a manner similar to a network stack. Layers: virtual file system, naming, cache, logical, physical, disk device driver, hardware.

Yangwook Kang/U. C. Santa Cruz: Object-based SCM: an efficient interface for storage class memories

SCM: storage-class memory e.g. flash memory and related memory-based persistent storage devices like solid state disk (SSD).

Yulai Xie/U. C. Santa Cruz: Design and evaluation of Oasis: an active storage framework based on T10 OSD standard

Trend: moving computation to the data via mechanisms like running workload on the storage servers, instead of moving the data to the compute servers. At least one site is doing this using Java applications with JVMs running on the storage system, or by running complete packages of application plus operating system on a VM on the storage system.

Panel Discussion

Blocks are dead. Instead: object stores. (This is another take on the death of POSIX file semantics, and was a common theme.)

Humans are bad at remembering why they saved something. We have to automate the capture of the provenance of the data being saved.

Disks will be with us forever. Probably tape too. We can't build enough chip fabrication facilities to make enough solid state storage for all the world's data requirements.

Fewer and fewer students are studying the "systems" area. (This has been my experience as well, and is principally why my career has lasted as long as it has.)

Academic research should be like science fiction: it should ask what if questions, and expect a high rate of failure. Lots of useful collateral may be produced by even a failed line of research.

Academia should have been doing research on flash memories way earlier; by the time it did, flash was already everywhere. (This was said in response to a number of research papers given on alternative flash translation layers.)

Storage systems are hard. Distributed systems are hard. Distributed storage systems are really hard.

In three to five years there will be no spinning media in any consumer device. (This was very controversial, but I'm not sure I disagree with it. Part of the reason is that cloud storage will eliminate much of the requirement for big storage in consumer devices.)

Startups can't fund long horizon research and development. Only large companies can do that, thanks to their existing revenue stream. (As a former employee of Bell Labs, I don't think this bodes well for long horizon R&D.)

There are too many people designing new systems without understanding what existing systems do and how they work. (In fact, a couple of the speakers on cloud computing remarked that they had come to realize they were on trails previously broken by the telecommunications industry who are used to developing very large scalable geographically distributed networked systems that had to recover automatically from frequent failures. Having spent time at Bell Labs working on such systems, this had occurred to me as well.)

BHAG: Big Hairy Audacious Goal. BHAGs are what the Defense Advanced Research Projects Agency (DARPA) and the National Science Foundation (NSF) should be funding. They are currently way too oriented towards near future applications and incremental improvements.

The reliability problem extends to people.

Specific workloads matter. I/Os per second (IOPS) are crap as a useful measure. (This same sentiment has been expressed by the high performance computing community regarding supercoputer vendors quoting GFLOPS of performance for their wares. HPC pundit Bill Buzbee was exactly right in saying "Any claims of performance by a vendor should be considered a guarantee that their product cannot exceed them.")

Trend: The Rise of the Stupid Storage Device (this is actually my term, not the speaker's), moving the storage management intelligence further up in the application stack. (This is a more general statement of the comment above about RAID, where you get better performance by moving disk management outside of the storage device. Compare with: The Rise of the Stupid Network.)

Negative results are still results. Disproving your hypothesis does not mean you failed. More is learned by failing gloriously in an ambitious endeavor than by succeeding in a modest incremental goal.

Wes Felter/IBM: Reliability-aware energy management for hybrid storage system

Energy-Proportional: Google's term for energy use that is proportional to a level of activity. Hard disk drives are not energy-proportional. spinning the disk takes energy, whether I/O is being done or not. Spinning a disk up from idle takes a lot of energy. You have to determine the break even point to know when or if to spin a disk down. Reliability is adversely affected by spinning a disk up. (I've also had some colleagues that had to deal with disk drives that had to be periodically spun down; otherwise, cavitation would cause bubbles to form in the working fluid of the drive leading to a disk crash. I've always assumed my colleagues were talking about the fluid bearings in the drive, but I might be wrong.)

Dean Hildebrand/IBM: ZoneFS: Stripe remodeling in cloud data centers

The MapReduce design pattern is a form of moving the computation to the data, since at least the map portion of the computation can be applied to local data.

Muthukumar Murugan/U. Minnesota: Rejuvenator: a static wear leveling algorithm for NAND flash memory with minimzed overhead

Rule of thumb: a read of a page of flash takes on the order of 10¹ microseconds (from another source: this is a random read, whereas a sequential read takes on the order of 10^-2 microseconds); a write of a page of flash 10² microseconds; an erase of a block of flash 10³ microseconds. Pages are typically two or four kilobytes; blocks are typically 128 kilobytes. Single-level cell (SLC) flash can endure about 10⁵ erase cycles per block; multi-level cell (MLC) flash about 10⁴ erase cycles.

Negative Space

2011-05-02T09:22:00.010-06:00

MSNBC and many other news outlets reported that one of the clues that led U.S. operatives to Osama Bin Laden's compound in a developed suburb of Abbottabad Pakistan just forty miles from the capital of that country was its lack of technology.

And unusual for a compound valued at more than $1 million: It had no telephone or Internet service.

Unless you have been living in a cave -- which, apparently, Bin Laden was not -- you are already aware of the concept of negative space. The Wikipedia article on this topic has an example of the image that introduced most of us to the idea.

Is the black and white image a vase, or opposing profiles of two men? This is when many children come to understand that what isn't there is just as important as what is there.

This breaking news found me smack in the middle of reading The Information: A History, A Theory, A Flood, a book on the history of information theory by science writer James Gleick. For me, it is a slow but rewarding read. Slow mostly because it's the kind of book that causes me to stare off in to space minutes at a time waiting for my brain to catch up making connections with existing material tucked away in its dark recesses. Material which for the most part hasn't been accessed since graduate school or my tenure at Bell Labs. The book is full of anecdotes and details about the lives of scientists, mathematicians, and engineers whose work ultimately informed my entire professional career and that of most of my colleagues: Turing, Gödel, Von Neumann, Nyquist, Shannon, and others.

Gleick's description of coding techniques, particularly that of Morse code, and of Shannon's and other's research into the redundancy of spoken and written natural languages, made me ponder how negative space, like the different durations of pauses between syllables, words, and sentences, was as or more important than the symbols that constitute the positive space in messages. Negative space is frequently crucial for correctly parsing the message, while much of the positive space is redundant because the symbols can be accurately predicted.

Gleick's example is the classic

f u cn rd ths

which nearly every English speaker can. But (and this is my example, not Gleick's) remove the negative space and

fucnrdths

becomes much more cryptic. The negative space actually carries more information content than the redundant symbols in the positive space.

But more to the point of Bin Laden, although nearly every English speaker can read that first sentence with the redundant symbols removed, everyone also recognizes it as malformed. It violates the principle of camouflage: it fails to blend in with its environment.

What Bin Laden might have realized had he survived his encounter with U.S. operatives is that this principle now applies to technology as well, and most specifically to signals intelligence. If you want to go unnoticed, you have to blend in with your surrounding telecommunications environment. This means generating signals that have about the same level of traffic as your surround, about the same signal to noise ratio, and about the same information content. Otherwise, the negative space you have created in your ambient communications environment makes you stand out.

I suppose in the twenty-first century this would mean lots of outgoing Facebook updates and Twitter tweets whose topics are trivial and banal, and lots of incoming spam from Nigerian princes. I have no idea how to realistically fake those sorts of things, but I'm now convinced that keeping a low profile does not mean keeping no profile. You don't wear black to camouflage yourself in the woods; you wear something that looks like woods.

Just as negative results are still results, negative space still imparts information. Some things become obvious by their omission.

Sturgeon's Law and Context Sensitivity

2011-04-24T12:42:00.011-06:00

Hi. My name is Chip, and I've been a manager. More than once. It's not something I'm proud of, nor did I find those experiences personally fulfilling, and only rarely enjoyable. Some misguided folks seemed to think I was good at it. It was an opinion I myself didn't share.

But I tried to be the best manager I could be, and part of that effort was spent reading books that made the bestseller lists in the various business magazines. Over the years I came to the conclusion that, like pretty much everything else, business books obey Sturgeon's Law:"Ninety percent of everything is crap" [1].

An article by Matthew Stewart, "The Management Myth", published in 2006 in the magazine The Atlantic (and also as a book reviewed in the Wall Street Journal), speaks to this. In it, Stewart relates how he spent seven years as a management consultant, ultimately co-founding a management consulting firm that employed six hundred people. Stewart did not have an M.B.A. He didn't have a business degree at all. He had a Ph.D. in nineteenth-century German philosophy. So, was he a natural born genius in business management? Not so much. To hear him tell the tale, he pretty much faked it. He doesn't make it sound that hard. He also runs to ground many of the classic epic tales in management, many of which I'd read or been told about during my own management training, revealing many to have actually been epic fails.

Frederick Winslow Taylor is credited with creating management as a profession by writing the book The Principles of Scientific Management based on his experience with figuring out in 1899 how to get laborers to load train cars faster: he bribed them. His book however described a much more complicated theory of management, which some called "Taylorism", which could only be accomplished by someone with an advanced education, an expensive suit, and for sure a higher salary. Unfortunately, it was a theory whose application could not be replicated by others. Bethlehem Steel Company eventually wised up, fired him, and scrapped his new fangled management techniques.

Another anecdote, and one that I had also heard about before, involved Homer Hibarger, who in the early twentieth century was doing research into how to increase productivity of workers by increasing workplace illumination. Since this research was being funded by a manufacturer of electric light bulbs, you may assume the results were a forgone conclusion, for otherwise they would have never, ah, seen the light of day. Indeed, productivity among a group of woman on a assembly line at a Western Electric plant increased when the illumination of the work area was increased. It also improved when illumination was decreased. In fact, productivity increased when almost any change was made in the work environment. What change resulted in the greatest improvement? Apparently, that occurred when some of the women on the line were replaced with others who were easier to get along with. And the fact that the women earned extra compensation for participating in the experiment.

Stewart isn't shy about relating his own experiences as a management consultant, watching his fellow consultants massage raw data to fit the curve that they needed, altering conclusions to match those required by their client, or reiterating the latest fad from a recent business bestseller whether it was applicable to the situation or not. Eventually his disillusionment led him to leave his consulting firm, only to watch it self-destruct in the receding distance under the squabbles of the remaining partners.

I had a similar period of disillusionment as a manager. I was a fan the 1982 bestseller In Search of Excellence by Tom Peters and Robert Waterman. It had what appeared to be hard data on how companies succeeded in their industries through both innovation and good management. That list of excellent companies included 3M, Walt Disney, and Intel. And also Amdahl, Data General, and Wang Laboratories. As I read other books by Tom Peters, I began to see less and less hard data from Peters backing up whatever management fad he was pushing. And about those excellent companies: many of them later fell on hard times, and some of them ceased to exist all together. Some, like NCR and Xerox, didn't even produce great financial results at the time the book was published. Peters was later accused of fudging the data for the book, a charge he denies.

But I'm reluctant to be too hard on Peters, or for that matter on Hibarger or even Taylor. Because although I'm a lousy manager, I have a pretty good track record as a software developer. And one thing I've learned over the past three-plus decades from studying, applying, and being painfully subjected to the latest software development process fad: the application of all processes and techniques, regardless of the problem domain, is very sensitive to context.

Extreme Programming was widely publicized before it had ever had its first big success. It was first applied to a project at Chrysler which never came to fruition; the project was cancelled when Chrysler was acquired by Daimler-Benz. Large development organizations (like the kind I have found myself in much of my career) have found the principles of Agile Development difficult to apply to non-co-located staff or to mission critical applications (ditto). The U.S. government (as well as many large development organizations) have found the classic Waterfall Process to be way too heavy-weight and inefficient to work at the rapidly changing pace of software development, although it works for things like building nuclear submarines.

That doesn't mean that Peter's eight themes of excellent companies, Boehm's tenets of Extreme Programming, the principles of the Agile Manifesto, or even the hoary old Waterfall Process, are fundamentally wrong. On the contrary, all of those have nuggets of great truths in them. It just means any particular technique or process can't be all things to all people all the time. Expecting any of them to work in all circumstances is just plain naive. And that includes whatever article on the latest thing in business management or software development that you are reading today. You might even apply Sturgeon's Law to mean that any of these ideas will be applicable at most 10% of the time.

Besides, it is in dealing with the exceptions where managers, and developers, earn their pay. The exceptions are what require innovation, insight, experience, and improvisation. As much as upper management would like to have a recipe for guaranteed success, sometimes you just have to make it up as you go long. And to come back to Stewart's article in The Atlantic, it's almost always more about the people you have than the process you use.

If it were easy, anybody could do it.

(Many thanks to my old friend and occasional colleague Jacque Marshall for passing the Stewart article along.)

[1] I was fortunate many years ago to hear the late Theodore Sturgeon relate this anecdote in person: at a dinner party a woman asked what he did for a living. "I'm a science fiction writer," he replied. "Oh dear," she said, "isn't ninety percent of it crap?" "Yes", he explained, "but ninety percent of everything is crap."

Elisabeth Sladen, a.k.a. Sarah Jane Smith, Dead of Cancer at 63

2011-04-19T16:03:00.007-06:00

This is being reported by the BBC.

http://www.bbc.co.uk/news/entertainment-arts-13137674

The SF media blog io9 has a warm and sentimental obituary.

http://io9.com/#!5793664/rip-elisabeth-sladen-doctor-whos-apprentice

Thanks to forsinain42 for this.

"Pain and loss define us as much as happiness or love. Whether it’s a world or a relationship… Everything has its time and everything ends."

Sarah Jane Smith
Doctor Who: Series 2 - School Reunion

I am crying at my desk.

Deconstructing the AR.drone: Part 6

2011-04-15T10:08:00.008-06:00

The other day the Free Flight app on my iPad told me that there was a new firmware release available for my AR.drone. I figured there was no better time to try loading new firmware using the diagnostic port on the bottom of the device.

Here is the bottom of my drone with the rubber plug with the USB symbol on it removed. You can see the port just to the lower left of center, and you can see the missing indexing pin of the eight-pin header in the upper left of the port.

Here's what I needed:

a cable I built that has a USB Type A connector on one end and an eight-pin Molex connector on the other, wired up as described on the AR.drone reference platform web site;
the AR.drone tools developed by user skorpion2k, which include the libplf library, the plf_inst_extract tool, and the usb_flash tool, the latter which includes the USB driver needed by the process;
a copy of the USB boot loader ardrone_usb_bootloader.zip kindly provided by user MAPGPS on the RC Groups web site;
a copy of the latest AR.drone firmware update file ardrone_update.plf from Parrot;
a Windows system with the usual accoutrements.

Here's the cable I fabricated, with the eight-pin Molex connector on the left and the Type A USB connector on the right. You can see the blocked socket that will match the missing indexing pin on the port when the cable is inserted in the correct orientation.

Here's the diagram of the cable that was provided by Parrot.

I unloaded all of the AR.drone tool zip files into separate directories on my Windows laptop so that the README files wouldn't overwrite one another, but consolidated all of the sub-directories, dynamic link libraries, and executables, plus the ardrone_usb_bootloader.zip file, into a single directory. There was a drivers sub-directory with the P6_USB_Stage1 device driver.

I used the plf_inst_extract tool to extract the ardrone_installer.plf file from the ardrone_update.plf file. The README file that comes with the usb_flash tool says to use a command like this

plf_inst_extract -i ardrone_update.plf -o ardrone_installer.plf

but as usual I am incapable of following simple instructions. Here's a screen shot.

I omitted the -o ardrone_installer.plf option. The plf_inst_extract tool uses the name extract_installer.plf by default, but the usb_flash tool expects it to be named ardrone_installer.plf. So I renamed it. Here's what was in the directory after doing that.

The order of these next steps is important. I connected my laptop to the unpowered drone using the cable that I had made. The diagnostic LED on the bottom of the drone lit up as a portion of the digital logic in the drone was powered from the USB cable itself. Then I connected the drone to its battery. The USB interface in the drone enumerated on my laptop. I went through the Windows device driver installation dialog to point it to the drivers subdirectory of the AR.drone tools. Windows installed the P6_USB_Stage1 driver. Here's a screen snapshot of the Windows Device Manager following that process.

I ran the usb_flash tool without any arguments at all. The first time it failed to establish contact with the drone, probably because I botched the order of something, but it worked fine the second time. Here's the successful run split into two screen snapshots.

I disconnected everything, cycled power on the AR.drone, connected my iPad to it, and the Free Flight app reported that the drone was running the new version of firmware.

This is a great example of how this kind of hacking depends upon the kindness of strangers. From the wiring diagram provided by the AR.drone's manufacturer Parrot, to the software tools developed and provided by skorpion2k, to the boot loader binary provided by MAPGPS, it is a combined effort of an avid community of AR.drone enthusiasts.

Deconstructing the AR.drone: Part 5

2011-04-11T09:47:00.019-06:00

In this article I will describe some of the tools I've been using in my quest to understand the AR.drone. Some of them I had to build myself; that's part of the fun.

When it's engines aren't rotating, the 11.1 volt AR.drone battery lasts considerably longer than the nine to twelve minutes of flight time you typically get. But I wanted to spend as much time as necessary poking around in the drone's software without having to worry about losing power. Unable to find the battery connector locally, I bought the cheapest used battery I could find off EBay, snipped the connector off of it, and attached it to a 12V power supply I got from Radio Shack.

Important safety tip: I probably voided the warranty on my drone as soon as I hooked it up. But it seemed to work fine and it permitted me to work at a much more leisurely pace. If I'd had an expensive lab bench-quality power supply, I probably would have used that instead.

The AR.drone has an eight-pin (one pin missing) diagnostic connector accessible from its underside, covered with a rubber plug with a USB symbol on it. This shows my drone lying upside down with the plug removed and a logic analyzer hooked up to three of the pins.

Important safety tip: the AR.drone really doesn't like sitting at much of an angle and its software will complain bitterly and eventually refuse to do useful things. But placing it upside down was relevant to my interests.

This is Parrot's diagram describing the USB cable you can build that allows you to flash new software onto your drone without relying on the wireless network connection. What this diagram doesn't tell you is that pins 4 and 6, shown unconnected here, are receive data (a.k.a. RX, RD, RXD) and transmit data (a.k.a. TX, TD, TXD) respectively for a TTL-level serial port right off the drone's microprocessor. Pin 7 is ground just as with the USB cable. This serial port is configured to be a console terminal for the system.

Important safety tip: the serial port pins are transistor-transistor-logic (TTL) level, which on the drone's ARM-based Parrot P6 processor means something like zero to 3.3 volts. RS-232 peak signal levels vary widely, but logic values can range from -15 to 15 volts, and the standard requires that hardware tolerate voltages as high as 25 volts. Standard compliant RS-232 ports will not recognize the input signal levels of the drone's serial port, and peak RS-232 output voltages may damage the microprocessor in the drone. More on this below.

This is the USB flash cable I fabricated using the Parrot cable diagram above. I just bought a USB cable at Radio Shack, hunted down another cable that had the right eight-pin Molex connector on it, snipped the ends off both cables and did a bit of soldering. I've successfully used this cable, and some software tools developed by others, to flash my drone with the latest drone software from Parrot. I'll describe that process in a later article.

This is a DB9 null-modem serial cable that I fabricated using the same approach as the USB cable, using the transmit and receive pins and the same ground pin as the USB cable. After using these cables for a bit it occurred to me that an even better approach would have been to build a single Y-cable with a the eight-pin Molex connector on one end and both a DB9 and a USB cable on the other end. That would have given me console access while reflashing my drone.

This is a commercially available USB to 3.3 volt TTL DB9 adaptor that uses an IC from Future Technology Devices International, Limited (FTDI). It automatically does the conversion from the TTL signal level to USB serial. Otherwise it works just like any other USB serial adaptor.

This is not my first experience with FTDI products, and it won't be the last; I'm an FTDI fanboy. This cable uses one of their ICs embedded in the DB9 hood. This same or similar FTDI chip can be surface mounted in a embedded application. This is a huge win. First, you can use one of the mini or micro USB B connectors, which have a tiny footprint compared to other serial connector alternatives, as a console port for your application. Second, USB cables with the right connectors are easier to come by these days than serial cables, and it is impossible to hook them up wrong. Third and most importantly, the FTDI chip is powered not from your embedded application, but over the USB cable from your laptop or desktop; this means it doesn't draw power when it's not being used, and it's active and running long before your microprocessor comes out of reset and the boot loader configures and starts using the serial port. (A big Thank You to my hardware colleagues for introducing me to this.)

Important safety tip: this is the third such device I've tried on the AR.drone, and is the only one that has worked, which it did flawlessly. The others, made by companies I'd never heard of, were crap. (This is in fact the reason for the long pause between articles on this project.)

It may sound like overkill, but I used a logic analyzer to make sure I had the pins right on the serial console port. But at around US$150 for an eight channel logic analyzer, that you can fit in your laptop bag, with a 24MHz sampling rate and serial decoders, doing so was kind of a no-brainer. I used a Saleae Logic, one of many USB-connected logic analyzer pods and software packages used in conjunction with a laptop. This is the Logic pod hooked up to my little HP 110 Mini netbook running the Logic software.

Here is the nice zippered case (complete with cat hair, I now notice) that the Logic comes in, and its contents, along with my little key ring pocket knife just for scale. The Logic pod is about one inch or so square and is shown here with a company property sticker on it that almost covers the entire unit.

This is a screen snapshot of the actual hexadecimal serial decode when the Logic was hooked up to the AR.drone while the drone was booting. It captured part of a "BMI Write Memory" message.

When you're building cables it pays to check voltages and continuity before committing yourself to your soldering. I use a Radio Shack digital multimeter. It's probably the slowest reading digital multimeter I've ever used. But it's also a fraction of the price of the nice lab bench-quality units I've used in the past, and otherwise seems to work fine.

If you're going to solder, particularly if you're going to solder digital components (as I did when adding an expansion connector to my Beagle Board), a quality soldering iron is an absolute must. And it'll make cables too. This is a Webber WESD51 Digital Soldering Station with digital temperature control. I really like the fact that I can just dial in the recommended soldering temperature right from the manufacturer's data sheet, and the unit heats up in seconds.

This is a Webber 6966C 250 Watt Industrial Heat Gun. It's overkill for use on shrink wrap when making cables. But it's ESD safe and gets hot enough to melt solder, so it is not one of Alton Brown's dreaded uni-taskers. Alton would also use it to brown the top of Creme Brulee.

There are also some tools in my AR.drone arsenal that I haven't quite needed yet, or which are more in the experimental stages.

Parrot sells a small tool kit with the specialized parts necessary to take the AR.drone apart and to replace parts like the propellers likely to be damaged during normal use. I'll be using these when I follow in other's footsteps and open the drone up to take a closer look at its digital components.

For sure when I open the AR.drone up I'll be using a grounded Electro-Static Discharge (ESD) or anti-static mat and wrist strap. I have a permanent one wired up on the computer desk where I do most of my poking around (you can see it in some of my other articles). But I like to keep this fold-up field service model in my big tool kit.

In one of my more speculative side-projects, I'm experimenting with how the AR.drone uses its ventral camera to stabilize itself during hovering. Consensus opinion on the web is that it is using edge detection, so I am using a vinyl checker board as a high contrast take off pad. Others have suggested that sometimes the drone has problems seeing the take off pad in dim light, so I'm trying to illuminate it with a tiny button cell-powered flashlight whose LED emits in the infrared (IR). Finally, I'm using an IR night vision viewer to see the LED myself; remarkably, this viewer can be found in your local toy store. You may also be surprised to find, as I did, how many LEDs in objects around the house emit in the IR portion of the spectrum.

Next up: I describe how I flashed new software into my AR.drone over its diagnostic port via the USB cable by depending upon the kindness of strangers.