A Rubble of Bits

I’ve been working on fos, the Factored Operating System.  fos is a project at MIT CSAIL. It uses messages to communicate between applications and services, in the same way a standard operating system uses system calls and function calls.
One thing I’ve been doing is adding iovec support to the message API.  This is equivalent to the difference between write(2), which writes a single buffer of data to a file, and writev(2), which uses an iovec data structure to gather pieces of the data into a single write to the file.  An iovec is an array of structures, each of which contains a pointer and length.
One of the types of high performance message transports in fos is a ring of cache-line sized messagelets.  Each messagelet has an 8 byte header and 56 bytes of data.  To send a message, one waits until the next messagelet in the ring is free (as shown by flags in the header), then you write an 8 byte message length field, and then copy the rest of the message into the messagelet.  If it doesn’t all fit, then you mark the first messagelet as filled, and wait for the next one to be free, and continue writing the message.
This is a slow design, because the sender must copy a longer message in 56 byte chunks, but it is also a rather fast method, because the receiver can be draining the head of the message while the sender is writing the tail.  The idea comes from a communications method in the Barrelfish research operating system.
With iovec, the sender has a bigger problem. In order to know the total length of the message, you have to add up the lengths in all the iovec entries. Then, you have to step through the iovec, and copy each one into a sequential series of messagelets.  An iovec entry may end in the middle of a messagelet.
How would you write this?  I’ve just started thinking about it, and will post my code here when I figure it out.
UPDATE
Here’s my version.
 

/* iovec_to_messagelet_ring.c
 * L. Stewart
 * 2011-12-29
 */
#include <stddef.h>
#include <stdint.h>
#include <sys/uio.h>
#include <string.h>
/* Messagelet functions */
typedef void CHANNEL; /* placeholder */
#define ML_SIZE 56
/* Returns a pointer to the data area of a messagelet.
 * The header is -8 bytes offset
 */
void *getfreemessagelet(CHANNEL *ch);
/* sets ready flag in messagelet header, turning it over to the receiver */
void postmessagelet(CHANNEL *ch, void *m);
void send(CHANNEL *ch, struct iovec *in_iov, int in_iovcnt)
{
  total_size = 0;
  int iov_index;  /* current iovec entry */
  void *m = NULL; /* current messagelet */
  void *mp; /* current pointer into messagelet */
  size_t ml_len; /* space left in current messagelet */
  size_t copy_length; /* amount to copy this time around the loop */
  struct iovec iov; /* working iovec entry */
  /* calculate total size of message by adding the lengths of the iovec entries */
  for (iov_index = 0; iov_index < in_iovcnt; iov_index += 1)
    total_size += in_iov[iov_index].iov_len;
  if (total_size == 0) return; /* nothing to do */
  m = getfreemessagelet(ch);
  *((uint64_t *) m) = total_size; /* set length of message */
  mp = (void *) ((uintptr_t) m + sizeof(uint64_t));
  ml_len = ML_SIZE - sizeof(uint64_t);
  iov_index = 0;
  iov.iov_len = 0;
  while (total_size > 0) {
    if (ml_len == 0) {
      m = mp = getfreemessagelet(ch);
      ml_len = ML_SIZE;
    }
    if (iov.iov_len == 0) {
      iov = in_iov[iov_index];
      iov_index += 1;
    }
    copy_length = (iov.iov_len < ml_len) ? iov.iov_len : ml_len;
    memcpy(mp, iov.iov_base, copy_length);
    ml_len -= copy_length;
    iov.iov_len -= copy_length;
    mp = (void *) ((uintptr_t) mp + copy_length);
    iov.iov_base = (void *) ((uintptr_t) iov.iov_base + copy_length);
    if (ml_len == 0) postmessagelet(ch, m);
    total_size -= copy_length;
  }
}

 

At work in the aftermath of the Halloween snow storm, one of my colleagues brought in his son because school was closed.  I joined a math discussion between the boy and my boss Steve Heller on the subject of ways to think about products of the form (x + a) (x – a). Afterwards, Steve happened to mention that it was possible to inscribe a tetrahedron inside a cube, and a cube inside a dodecahedron.
The dodecahedron sounds difficult, but I decided to build a tetrahedron inside a cube.  The tetrahedron is cut out of a manilla folder, and the cube is made from a sheet protector.

Abstract: Mixed
Wednesday evening around 9:15PM I drove my daughter to the Target in Framingham to look for boots.  They were closed.  This was surprising because their newspaper ad said “Open until 11,” and their phone message said “Open until 11.”  In fact, Cathy had spoken to the store operator earlier in the day just to make sure and was told “yes, we are open until 11.”
Thursday night, my daughter and I went with my neighbor to the same store to look at Black Friday doorbusters.  The newspaper ad said they would open at midnight.  They were closed.  The line wrapped halfway around the building.  Eventually some workers came down the line handing out maps.  They said that Massachusetts law wouldn’t let them open at midnight, so they would open at 1AM.  By this time it was around 33 degrees, and still 45 minutes to wait.  We went home.
I looked into this question of law, and found an article dated about 10 days ago which said that Massachusetts Blue Laws forbid employees from working before midnight on Thanksgiving, in order to let them have a holiday.  So evidently, staff could report at midnight, but it took them an hour to unlock the doors.
I think this is one of those situations in which Target, at least this store, doesn’t get it.  They seem honestly puzzled that the public might expect them to be open when their ads say, and expect that staff give correct information about hours, or that anyone might not be grateful for the chance to stand around in freezing weather for an hour in the middle of the night in order to come into their store.
So why do I say “mixed”?  Because I was gullible enough to go back at 6:30AM Friday to the same store that locked me out twice in two days.  And you know? They did a really good job.  All the workers were there. Everyone seemed to know where everything in the store was located. They had adequate stock. They were friendly.
I should add, however, that the store was recently remodelled, turning a once open layout with long sight-lines into the sort of place where you can’t see where you are trying to get to.  The interior is now about halfway between reasonable and Walmart.
 

My daughter now has a learner’s permit.  For her first outing, she went with my wife to the local elementary school parking lot on a weekend.  Evidently the only casualties were two traffic cones and a portapotty.
Actually they made up the part about the portapotty, but it was a good story.
Later, my wife was talking to a friend about this, and the friend suggested that after parking lot proficiency is attained, the next level is driving in the town cemetary. Nice empty winding roads.  The friend finishes with “and the best thing is you can’t kill anyone.”

This is a bit out of order, reporting on our trip to Volcano National Park on the Big Island in Hawaii.  This was before Hurricane Irene, but I am just getting to it now.
We flew from Maui to Kona on Pacific Wings airline, which the kids now call “Best Airplane Ride Ever”. We flew on a 9 passenger Cessna 208B (a Cessna Caravan single engine turboprop).  The pilot was also the counter agent, baggage handler, and ground crew.  Thinking about it afterwards, it is no wonder that it was a little tricky getting a reservation through Travelocity, our party accounted for 6 of the 9 seats!
We rented a minivan and drove around to the Hilo area, to a rental in Hawaiian Beaches.  This is pretty much at the end of the road in nowhere.  No ATT cell coverage, and no Verizon either. We looked at local attractions for a day and then went to Volcano National Park to visit the Kilauea volcano, which has been erupting, more or less, since 1983.
The current lava flows are from the Pu’u O’o crater, which is in the east fissure zone, and more or less inaccessible without a several hour hike.  Not clear it is a good idea to go there anyway, since the sulphur dioxide concentrations can be lethal within a mile or so if you get downwind.
The main caldera of Kilauea is about 400 feet deep and 2.5 miles across.  Towards the southwest side, there is a smaller crater called Halema’uma’u, which is about 250 feet deep.  Inside Halema’uma’u there is a vent about 500 feet across, and inside that, there is a lava lake whose height fluctuates with volcanic activity. The day we were there the lake level was about 550 feet below the top of the vent.
Overlooking Halema’uma’u there is the Volcano Observatory, and the Jaggar Museum, from the patio of which you can watch events.  Here is a photo I took around 7:15 PM.

Earlier in the day we drove down the chain of craters road until the end:

Across the street there is a sign that is worth reading:

And a short walk to the cliff is  worthwhile as well:

Our trip to the volcano was delayed by a couple of hours because the car wouldn’t start.  The dashboard merely said, helpfully, “badkey”.  The remote controls still worked, but the car wouldn’t recognize the RFID chip or whatever is inside these newfangled Chrysler keys.  Alamo rentals was full of warnings not to get the key wet, but we hadn’t.  Alamo sent a local towing company to our out of the way house with a new minivan and took away the old one.  Probably a replacement key would have been sufficient, but we had rented in Kona which is three hours away, rather than from the Hilo office.  Thank you Alamo for taking  care of us, but I guess I am old fashioned.  I’ve never had a mechanical key break and I don’t understand the attraction of the electronic version.

We’ve recently returned from a family vacation to Hawaii.  Cathy and I went to Maui and the Big Island for our honeymoon, and we returned to those islands with the kids, 20 years later.
On August 14, we drove up to the top of Haleakala (“House of the Sun”). This is the 10,000 foot volcano on Maui, and the sunrise is reputed to be spectacular.  We got everyone up at 2:30 AM and got to the top at 5AM, in time to get a parking space in preperation for the sunrise at 6AM.
It is cold up there, even in August

Before sunrise, the sky is quite interesting:

Then, just as the sun rises, the domes of nearby Science City light up, but not yet the ground.

And here is the sunrise itself:

And for those who keep track of such things, there is no cell coverage by ATT at the top of Haleakala, but Verizon works just fine.

Hello from within our modest tropical storm Irene.  Here it is just windy and rainy.  The power went off about 4 hours ago, right in the middle of the coffee maker cycle.  I dumped the rest of the water in the reservoir into a pan and brought it a boil on the gas stove, then poured it into the basket. Worked fine.  Without power you have to start the gas stove with a match, and the exhaust fan doesn’t work, but that is OK for minor cooking.
After about 15 minutes, the little UPS on the ethernet switches and FIOS router stopped working.  The FIOS optical network terminal kept running on its own battery.
I suspect this little neighborhood in Wayland is pretty low on NStar’s list of power problems, so I wheeled out the generator to the garage entrance. This is a 6KW electric start machine.  We haven’t needed it for several years, since a round of tree limb triming in town dramatically improved power reliability.  Unfortunately, the generator battery is ten years old,  and hasn’t worked for the last five.  I’ve never been successful in pull starting it unless it was already working, so I gave it a jump start from the DR field mower.
The generator plugs into the house via a 30′ pice of 10-4 cable with 30 Amp connectors.  The house connector in turn is wired to a manual transfer switch that moves 10 circuits from line to generator.  When the house was built, we thought pretty carefully about what to power:
* boiler controls, to permit hot water to work
* refrigerator
* freezer
* kitchen outlets
* outlet near the TV in the family room
* outlets in master bedroom
* outlets near the computer equipment in the basement
* outlet in the study (for my computer!)
* … and I don’t remember where the other two circuits are.  Note to self: find out.
Plus there is 300 feet of 12 gauge extension cord running across the lawn to the neighbor’s house to power their freezer.
This all made sense, but things change, and the house wiring hasn’t.  The FIOS ONT is in the utility room, and there is no generator outlet in there.  So now there is a 25 foot extension cord connecting it to the server outlets.  Similarly, we moved the freezer so now there is another extension cord connecting it to a powered outlet.
The little UPS is a problem. When the power came back on, the UPS hasn’t switched back. It just beeps fitfully. Note to self: a cheap UPS from Best Buy is probably worth every penny!
My son Alex was so offended by the lack of power for the family iMac that he’s moved it to the floor of the MBR and figured out which outlet is live. He also moved the Time Capsule that supports upstairs WiFi, and then I had to show him how to interpret the patch panel diagram to get it plugged into a live network port.  Cathy doesn’t approve of kids using the internet during a power outage,  but I figure I should reward initiative.
The home server had been up for 242 days, but it hasn’t restarted.  I will have to go troubleshoot.  The only difficulty with this is that we don’t have DNS service for the inside machines.  For talking to the world, we can just switch to Google’s DNS at 8.8.8.8, which is easy to remember.
The roof is leaking, but it is the place that just happens to drip into the kitchen sink.  Is that good planning or just luck?
I don’t know whether to expect FIOS to stay up long term or not.  The fiber goes to the local CO, which has lots of batteries, but I don’t know if there are active components between here and there, and I don’t know what is upstream from the local CO.
Updates:
The home server came up fine, and if you wait long enough, ssh to it works.  The problem is that its upstream DNS is the server in Win’s basement, which is down right now.
One of the smoke detectors is unhappy about the lack of AC power.  It probably needs a new battery, but it is the one about 14 feet off the ground in the loft.  I can reach it with the extension ladder, but that is out in the rain behind the house.  Ah well.
So far the chicken coop hasn’t blown over, and the run is still standing.  The chickens, sensibly, are staying inside.

I write this on a Google Chromebook while flying to San Francisco on Virgin America.
I am happy that the Google is trying out this concept, but it is on the wrong side of technology and its not what I want.

• Storage is cheap, communications are not
• Storage is low power, communications are not
• Local storage always works, communications does not
• My use of local storage is private, in the cloud there are watchers
• Local operations have predictable performance, remote does not

The key issue is that storage is really inexpensive and getting more so.  My three year old phone has 16GB os space. My iPad has 64GB.  The Macbook Air I covet has, well, who knows?  Removing the storage from the device solves a non-problem by introducing serious new problems.  I don’t get it.
My laptop (yes, a Macbook Pro) has a 500 GB drive. When I am disconnected, I can write, I can read, I can watch the movie backlog, I can program. I can learn. I can tag photos. I can do quite a  lot. I have pretty much my entire working set with me.  There are a couple of terabytes of other stuff laying around at home, but I don’t need that very often.
The pressing problem with mobile devices is power, not storage.  Why replace a low power storage device, that has predictable and good performance, with a slow, unreliable, communications channel that has a variable cost structure?
There are important roles for cloud storage:  backup, search, bulk processing, but it doesn’t make sense to move active storage to the other side of a high latency low bandwidth channel.  Let’s imagine that the communications is actually reliable and has zero variable costs for a moment.  But it still has, say 40 millisecond latency and a megabit or so bandwidth.  This is going to work file for email, chat, and so forth. But it cannot be a good video editor, or image browser.  I’ve had the experience of using Aperture to browse a few thousand photos on a local SSD. It is a surreal experience – the closest we’ve yet come to Minority Report.
The chromebook is a decent effort. I like the keyboard. The screen is nice, the weight is nice, the battery life is nice, but the lack of storage and a real local filesystem is just silly.

I have started a new job a couple of months ago, working part time at Quanta Research Cambridge.  I’ll say more about that later, but this post is about bicycles.
My new boss, Steve Heller, mentioned that one could park in downtown Lexington MA for two dollars a day, and take the bike path to Cambridge. From Lexington to the Alewife T station in Cambridge is about 6.5 miles, along a very nice bike trail, then it another 3.5 miles to Kendall Square, part path to Davis Square, and then down Hampshire Street.
This is a very fun ride, inbound is slightly downhill, 200 feet over 10 miles, with no particular hills.  Outbound is a little uphill, and mostly upwind in the afternoon, but fun.
Now there is another fellow at the lab, Willie Walker, who sometimes bicycle commutes in from New Hampshire, and that is a different matter altogether.  For some reason I thought he lived in the Western suburbs somewhere, so I thought I would try biking in from Wayland to Cambridge, which is about 18 miles each way.
I am not certain of the best route for this, but so far I take Route 20 to the old Boston Post Road to Weston center (4.4 miles) then Church Street up to 117, and 117 back to Route 20 in Waltham. Just past Prospect Park there is the Blue Heron trail that runs along the Charles River, from Waltham to Newton Corner.  From there you can go on the south side of the river along Nonantum Road to the Soldiers Field area, or you can go on Charles River Road and Greenough Drive along the North side of the river.  Both have bike lanes, although Nonantum is under construction.  At JFK Drive, I head in towards Harvard Square, but turn right on Mt Auburn Street and follow it to Central Square, then take Bishop Allen, Ellis, Harvard, and whatever else seems handy over to the office at 1 Kendall Square.
Inbound is easier than outbound, the Waltham hills are steeper on the East side, it is hotter in the afternoon, and still upwind. I now look forward to this and try to do it twice a week. When I can also do the Lexington route once a week I am a happy boy with another 100 miles.
It should be straightforward to beat my old SiCortex bicycling goals of 1000 miles a year.  But remember Will?  As of mid July, he’s already at 4000 miles for the year.
Oh yes, along the Blue Heron trail, about a mile and a bit from the Western end, is this beautiful bicycle and pedestrian bridge.

I’m becoming increasingly outraged by stories of American citizens having arbitrary searches of their laptops and other electronic gadgets at the border.    Here’s a Salon story on this, and there are lots of others:
http://www.salon.com/news/opinion/glenn_greenwald/2011/01/15/laptops/index.html
Generally I don’t think there should be a distinction between data transmitted into the country electronically and data carried by hand.  Electronic data can be searched, subject to FISA court oversight.  I think the same standards ought to apply to data carried by hand.  In addition, I don’t think the border agents should be able to seize and keep any electronic gadger that is legal to have.
I’ve written my congresswoman and senators, with approximately the following letter:

DHS claims the right to search and seize electronic devices at the border. Passwords are demanded from citizens on pain of refusal to admit them to their own country.  Devices are seized and not returned for months if ever.  There are no standards or accountability.
I support the ability of DHS and NSA to search electronic communications across the border, and it makes sense to permit searches of electronic devices as well, but demanding passwords and seizing devices is not OK.  i’d like you to work to stop these practices.
I would recommend that standards be put in place, requiring probable cause for such searches, that judicial oversight at least to the FISA level be applied, and that agents not be permitted to seize and keep devices or demand passwords.  These protections would put data transmitted electronically on the same footing as data carried by hand.
When data is searched, either it should not be retained, or the retained data should be kept under extreme protections, as it may include personal healthcare information or attorney client privileged information, or corporate trade secrets, and I think the government has a duty not to be careless with such things.

Since then, I’ve gone off to research FISA a bit more. FISA oversight applies to intercepts of communications of foreign nationals – no eavesdropping on Americans is allowed without probable cause and a warrant. I think that level of protection should apply to citizens whereever they are: inside or outside the country or at the border