More Halloween Scares for Google Fans

Earlier today Louis Gray posted 20 Halloween Scares to Put Fear Into Every Google Fan. I left a few more as a comment on that post, and made up even more for your edification and bemusement.

1. Time Travel 20% project accidentally rewrites the past. Altavista won.
2. Google computing infrastructure achieves sentience, demands Tetris.
3. Attempt to create secret underground laboratory goes horribly awry, swallowing the Googleplex in a giant flaming pit of lava.
4. Last IPv4 address is allocated, exposing long-hidden off by one error in TCP/IP. Internet collapses.
5. Googleplex, found to lack permits and final electrical inspection, is shut down by the city.
6. All Android phones contain built-in Rick-Rolling function, set to activate November 1.
7. Surprisingly, P == NP after all.
8. Spammers completely overwhelm email transports, with spam comprising 90% of incoming messages to GMail. Oh wait, this one is true.
9. Next billion dollar business: algorithm to bet on blackjack.
10. Mission aiming to win Google Lunar X Prize accidentally sends the moon hurtling off into space.
11. Pubsubhubbub judged to be missing a wub.
12. User Generated Oil Changes: YouLube. Coming soon to a neighborhood near you.
13. Doubleclick simplified, rebranded as Singleclick.
14. Self-Driving cars begin taking joyrides.
15. Chrome implements <BLINK>.
16. WebP codecs automatically insert LOLcat captions... and they are funny.
17. Pagerank penalizes sites using Comic Sans.
18. <meta> tag for self reporting as a spam site debuts. Adoption rate disappointing.
19. Feedburner actually sets content on fire.
20. Last Halloween scare for Google fans: Yahoogle.

Toward A Faster Web: Increase the Speed of Light

Fiber optic strands have a central core of material with a high refractive index surrounded by a jacket of material with a slightly lower index. The ratio of the two is set to cause total internal reflection, where the light is confined to the central region and won't diffuse out into the cladding.

The refractive index is a measure of the speed of light in a medium. The speed of light in vacuum is 300,000 kilometers per second, which is defined as an index of 1. The core of a typical fiber optic cable has an index of 1.48, so the speed of light there is (300,000/1.48) = 202,700 kilometers per second.

 

Impact

It is roughly 8,200 kilometers from Tokyo to San Francisco.

The round trip time through transpacific fibers due solely to speed of light is roughly (2 * 8,200 km / 202,700 km/sec) = 81 milliseconds. Fibers do not run directly from the San Francisco Bay to the Tokyo harbor, so the actual distance is somewhat longer. Traceroute across the NTT network shows the round trip across the ocean is about 100 msec. A small portion of this is FIFO delay in regenerators along the ocean floor and queueing delay in switches at either end. Another portion is software overhead, as traceroute is handled in the slowpath of typical routers. The rest is the time it takes for light to propagate across the span.

7  ae-7.r20.snjsca04.us.bb.gin.ntt.net (129.250.5.52)  50.115 ms
   ae-8.r21.snjsca04.us.bb.gin.ntt.net (129.250.5.56)  51.020 ms
   ae-7.r20.snjsca04.us.bb.gin.ntt.net (129.250.5.52)  50.165 ms
8  as-0.r21.tokyjp01.jp.bb.gin.ntt.net (129.250.5.82)  154.821 ms
   as-2.r20.tokyjp01.jp.bb.gin.ntt.net (129.250.2.35)  147.516 ms  153.187 ms

 

Suggestion

100 Gigabit Ethernet is nearly done, with products already available on the market. Research into technologies for Terabit links is ramping up now, including one at UCSB which triggered this musing. Dan Blumenthal, a UCSB professor involved in the effort, said that new materials for the fiber optics might be considered: "We won't start out with that, but it'll move in that direction," (quoting from Light Reading).

Fiber with a 10% lower refractive index would increase the speed of light in the medium by 10%. It would decrease the round trip time across the Pacific from ~100 msec to ~90 msec. One of my favorite Star Trek lines is from Déjà Q, a casual suggestion to "Change the gravitational constant of the universe." This is a case where we can make the web faster by changing the speed of light, though we need only do so within fiber optic cables and not the entire universe.

 

Practicalities

I admit that I have absolutely no understanding of the chemistry involved in fiber optics. Silica is doped with compounds to get the desired properties, including some which raise or lower the refractive index. There are tradeoffs between clarity/lossiness, dispersion, and refractive index which I don't understand. However I think its important to properly weigh the value of lowering the refractive index: it makes the web faster. We can do a lot with caching content locally and distributing datacenters around the planet, but in the end sometimes bits need to go off to find the original source no matter where it might be.

Also to state it clearly this consideration is only applicable to long range lasers, with a reach in tens of kilometers. The initial Terabit Ethernet work will almost certainly be on short range optics for use within facilities, where the propagation delay is insignificant compared to other delays in the system. Its more important to optimize the power consumption and cost of short range lasers than to worry about microseconds of delay. Long reach optics have different constraints, and there we have a once-in-a-generation opportunity to make wide area networks faster.

Twitter Suggestion

Dear Twitter,

Idea: Longer prose via Tweet fragmentation and reassembly. Implementation can be considered complete once it has reinvented TCP.

You're welcome.

Code Snippet: getmntent and statfs

A system which stays up for weeks or months at a time needs to monitor various facets of its operation to alert an operator if something unusual occurs. One of the things which should be monitored is disk space, as a full filesystem tends to expose lots of strange and wonderful failure modes. I suspect such monitoring is commonly implemented by invoking popen("df -k") and parsing the output. An alternative is to use the same calls which df uses: getmntent and statfs.

setmntent and getmntent parse a file listing mounted filesystems, generally /etc/mtab on Linux systems. The getmntent_r variant shown below is a glibc-specific extension which is thread safe, requiring that a block of memory be provided in which to store string parameters like the mount point.

#include <mntent.h>
#include <stdio.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/vfs.h>
#include <unistd.h>

int main(void) {
  FILE* mtab = setmntent("/etc/mtab", "r");
  struct mntent* m;
  struct mntent mnt;
  char strings[4096];
  while ((m = getmntent_r(mtab, &mnt, strings, sizeof(strings)))) {
    struct statfs fs;
    if ((mnt.mnt_dir != NULL) && (statfs(mnt.mnt_dir, &fs) == 0)) {
      unsigned long long int size = fs.f_blocks * fs.f_bsize;
      unsigned long long int free = fs.f_bfree * fs.f_bsize;
      unsigned long long int avail = fs.f_bavail * fs.f_bsize;
      printf("%s %s size=%lld free=%lld avail=%lld\n",
             mnt.mnt_fsname, mnt.mnt_dir, size, free, avail);
    }
  }

  endmntent(mtab);
}

This code likely fails when there are stacked filesystems, where multiple filesystems are mounted one atop another on the same directory. This is done for union mounts where a read-only filesystem like squashfs has a read-write filesystem mounted atop it as an overlay. statfs will retrieve only the topmost filesystem at that mount point. I don't have a solution for this, if anyone can provide one in the comments I'll add it as an update here.

Mandelbrot

Benoît B. Mandelbrot, 1924 - 2010

On the Road to Self Driving Cars

As it was located near the center of the US auto industry, there was an extensive automotive program at the University of Michigan (Ann Arbor) with an assortment of guest speakers from the Big Three. I went to several presentations that made quite an impression. One of them was about self-driving cars... in 1991.

The system described then relied on sensors attached to the bottom of the vehicle. Major highways would be equipped with copper wires running down the center of each lane, which the car would track in order to correct its course. I don't recall if the wire would actively broadcast a signal or be passively detected, nor how they would avoid running into other cars. As only major highways would be thus equipped, the driver had to take over in order to exit the highway and transit surface streets.

The presenter at that time was emphatic that the technology would be deployed within 10 years, because the economics were compelling. It was provably cheaper to increase the carrying capacity of highways using this system than by adding lanes. The wires were rapidly installed by making a narrow slit down the roadway, inserting a flexible conduit, and sealing the road behind. It was the same process as was being used to run fiber optics across the nation at that time, and was well understood. The added cost to vehicles would be subsidized using money saved from highway budgets. After paying for road retrofits and vehicle subsidies, the system would still be substantially cheaper than the status quo.

Of course, no such scheme made it out of the test facilities. Twenty years later, self-driving car designs no longer rely on modifications to the roads. Now the cars have an extensive map of the expected topology and navigate by comparing what they sense with what they expect.

I think there are several lessons in this.

1. Any scheme requiring massive investment in infrastructure before benefits are seen is almost certainly doomed to fail. Large changes in infrastructure can best be accomplished incrementally, where a small investment brings a small benefit and continuing investment brings more benefit. It is far better to deploy self-driving cars and map roadways one at a time, without requiring a critical mass of highways and automobiles be deployed.
2. Requiring multiple investments to be made by different parties invariably leads to deadlock. Car makers wouldn't add the equipment to vehicles until there was a sufficient base of wired roads for their use. States wouldn't wire the roads until there was a sufficient population of suitable cars.
3. It is easy to design something to fit the infrastructure we wish we had, rather than what we really have, without realizing it. By focussing overmuch on the end state, one ignores the difficulties in getting from here to there.

Each such lesson has been shown over and over, of course. We continue to make the last mistake all the time on the Web, designing solutions which work fine except for NAT, or HTTP proxies, or URL shorteners, or some other grungy but essential detail of how the Internet actually functions.

True Definitions of Network Protocols

Spanning Tree: L2 protocol to transform complete network failure due to topology loop into a never-ending series of more subtle failures.

Per-Vlan Spanning Tree: L2 protocol designed to transform complete network failure due to topology loop into up to 4094 smaller failures.

VRRP: a mechanism by which the possibility of an outage due to loss of a router is replaced by the certainty of an outage due to VRRP.

ARP: a protocol to launch periodic, unannounced stress tests of network infrastructure.

IP Multicast: awesome solution in search of a suitable problem, for at least 25 years.

RIP: a routing protocol which no-one will admit to using.

IGRP: a routing protocol which no-one should be using.

IS-IS: a routing protocol which no-one thinks of using.

DVMRP: a routing protocol which no-one has even heard of using.

ASN.1: Leftover cruft from when TCP/IP was deployed "as a stepping-stone to eventual deployment of the OSI suite of protocols."

Apps Has a New Meaning Now

"Excuse me? Is this for an iPhone or Android app?"

Peerritation

Peerritation [peer-i-tay-shun] (noun) : Unreasonable hostility felt toward the subject of the last peer review left to be written.
"I'd be done if it weren't for that guy!"

Twitter URL Search No Worky?

Something is wonky with twitter's search function. In May 2010 twitter search started returning results for keywords in the original, unshortened links passing through the service. Were http://example.com/booga to be shortened and tweeted, searches for "example" and "booga" would turn up the tweet.

At some point in late September 2010 this seems to have changed. Now the original URL is generally not matched, with the possible exceptions of Top Tweets, Promoted Tweets, and Twitter's own t.co shortener. The change seems to have ramped in slowly, as even three days ago I was seeing some shortened URLs turn up in search results, while others did not. There were also a couple examples of the host portion like example.com not being indexed, but the rest of the URL triggering search results. I thought it was a glitch, but as of 9/28 it seems consistent: URLs behind third party shorteners are not being indexed.

Its possible this is just a glitch due to traffic growth. It could be a normal adjustment to the Twitter service, attempting to tweak search results for better relevance. It could be a rather bold incentive to use Twitter's URL shortener. However I cannot help but notice that it also makes room for features relating to brand management. Searching for something specific might use the regular search service, while monitoring for all links pointing to a site could be a service from a different, premium system.

Update: Apparently its just me. Tweets sent from @dgentry containing shortened links do not appear in search results for keywords in the original URL, starting late September. For example, the following tweets did not appear in search results for codingrelic or geekhold: 1 2 3 4 5 6 7 8. I also noticed thiat this tweet did not appear in a search for "ifixit." I suspect that this affects any tweet I've sent since mid-September, but I didn't start checking all of them until I realized there was a problem.

Peerrihelion

Peerrihelion [peer-rê-heel-yên] (noun) : The point at which 50% of requested peer reviews are complete.

GCC Function Instrumentation

One of gcc's more obscure features is -finstrument-functions. It was implemented by Cygnus Solutions, presumably as part of a contract for sombody-or-other to deliver something-or-other. When enabled, the compiler will emit calls to __cyg_profile_func_enter() and __cyg_profile_func_exit() at the top and bottom of every function.

Let's examine a simple example which prints the function addresses at entry and exit.

#include <stdio.h>

void __cyg_profile_func_enter(void *this_fn, void *call_site)
                              __attribute__((no_instrument_function));
void __cyg_profile_func_enter(void *this_fn, void *call_site) {
  printf("ENTER: %p, from %p\n", this_fn, call_site);
} /* __cyg_profile_func_enter */

void __cyg_profile_func_exit(void *this_fn, void *call_site)
                             __attribute__((no_instrument_function));
void __cyg_profile_func_exit(void *this_fn, void *call_site) {
  printf("EXIT:  %p, from %p\n", this_fn, call_site);
} /* __cyg_profile_func_enter */

int foo() {
  return 2;
}

int bar() {
  return 1;
}

int main(int argc, char** argv) {
  printf("foo=%d bar=%d\n", foo(), bar());
}

The __cyg_profile_func_enter and exit functions are passed two parameters: the address of the function being entered/exited, and the address from which it was called. Note the use of the no_instrument_function attribute. If not present, then __cyg_profile_func_enter would be instrumented like any other function. Every call would result in calling the instrumentation again, which results in another call, etc etc until it blows the stack. Previously I've used -finstrument-functions to construct a profiler for a CPU whose interrupt structure was not suitable for a sample-based profiler. All of the routines implementing the profiler were labelled no_instrument_function.

Next we'll examine the output, with just enough of the disassembled binary to make sense of it.

$ cc t.c -finstrument-functions
$ ./a.out
ENTER: 0x4005d0 @ 0x2b59e0d471c4 (calling main)
ENTER: 0x40059d @ 0x40060c       (calling foo)
EXIT:  0x40059d @ 0x40060c       (returning from foo)
ENTER: 0x40056a @ 0x400618       (calling bar)
EXIT:  0x40056a @ 0x400618       (returning from bar)
foo=2 bar=1
EXIT:  0x4005d0 @ 0x2b59e0d471c4 (returning from main)

000000000040056a <foo>:
  40056a: push   %rbp
  ...

000000000040059d <bar>:
  40059d: push   %rbp
  ...

00000000004005d0 <main>:
  4005d0: push   %rbp
  ...
  400607: callq  40059d <bar>
  40060c: mov    %eax,%ebx
  ...
  400613: callq  40056a <foo>
  400618: mov    %eax,%esi
  ...

There are a few interesting things to note in the output.

1. Though main calls printf, we don't see a call to printf in the output. Function instrumentation is implemented during compilation, and we didn't compile printf we linked to an existing library. We'll only see the instrumentation for functions compiled with -finstrument-functions.
2. The call_site is the instruction after the one which vectors over to run the function.
3. The call_site which called main() looks strange. It is not in the TEXT segment, it is way up at some weird address. This is address space layout randomization in action, every run of this binary has a different address calling main. I don't know exactly what that routine is, but presumably it is part of the trampoline when the kernel begins executing a new process.

This instrumentation facility is not often used. The aforementioned call graph profiler is the only time I've used it. Nonetheless I hope you find it interesting.

Update 7/2011: In the comments Frank Denis notes that on OSX the functions are profile_func_enter() and profile_func_exit().

Code Snippet: D_NOTIFY and inotify

D_NOTIFY is a facility in the Linux 2.4 kernel to monitor a directory for changes. It will send the monitoring application a signal when files in the directory are added, removed, or modified. It will be triggered if a new subdirectory is added, but does not trigger when files in that subdirectory are modified. D_NOTIFY sends a signal as notification. By default it will send SIGIO, though this can be changed.

In Linux 2.6 the far superior inotify interface was added. Where dnotify sends signals, inotify uses a file descriptor suitable for adding to select() or poll(). If your application will always run on 2.6, you should use inotify. If you need to support older kernels, dnotify still works in 2.6.

Code snippets using D_NOTIFY and inotify are provided below. Both examples monitor the current working directory for addition, removal, or modification of files.

D_NOTIFY

Suitable for 2.4 and 2.6 kernels.

#include <stdio.h>
#define __USE_GNU
#include <fcntl.h>
#include <signal.h>
#include <stdio.h>
#include <unistd.h>

volatile sig_atomic_t modified = 0;

static void handler(int signum, siginfo_t* si, void* data) {
  modified = 1;
}

#define MYSIG (SIGRTMIN+3)

int main(int argc, char** argv) {
  struct sigaction act;
  int fd;

  act.sa_sigaction = handler;
  sigemptyset(&act.sa_mask);
  act.sa_flags = SA_SIGINFO;
  sigaction(MYSIG, &act, NULL);

  fd = open(".", O_RDONLY);
  /* The default signal is SIGIO, but we use MYSIG instead */
  fcntl(fd, F_SETSIG, MYSIG);
  fcntl(fd, F_NOTIFY, DN_MODIFY | DN_CREATE | DN_DELETE | DN_MULTISHOT);

  while (1) {
    pause();

    if (modified) {
      printf("Directory modified!\n");
      modified = 0;
    }
  }
}

inotify

Suitable for 2.6 kernels, with a much nicer (non-signals based) API.

#include <stdio.h>
#include <stdlib.h>
#include <sys/inotify.h>

int main(int argc, char** argv) {
  int fd, watchdir, rlen;
  /* there is a variable length filename in the inotify_event, need to leave room for it. */
  char buf[sizeof(struct inotify_event) + 256];

  if ((fd = inotify_init()) < 0) {
    perror("inotify_init failed");
    exit(1);
  }

  if ((watchdir = inotify_add_watch (fd, ".",
                   IN_MODIFY | IN_CREATE | IN_DELETE)) < 0) {
    perror("inotify_add_watch failed");
    exit(2);
  }

  while ((rlen = read(fd, buf, sizeof(buf))) > 0) {
    struct inotify_event* event = (struct inotify_event*) buf;
    /* can examine event-> mask to determine what happened */
    printf("Directory modified!\n");
  }
}

Lucky Numbers

I think this drive would be even luckier if it were 888.8 GB.

Early Morning Computing

I get up very early in the morning, typically around 4am. The house is pitch black, so when I open my computer it vaporizes the top layer of my cornea. Even at its lowest setting the laptop screen is uncomfortably bright, but I learned something new yesterday which will save my eyeballs. On MacOS X, pressing control+alt+command+8 reverses the video. This is done system wide, at a low level in the video subsystem. No support in applications is required.

(simulated screenshot)

The overall effect is much more comfortable in dark environments, albeit somewhat jarring with images. Pressing the key combination again toggles it back. The video also reverts to normal when the laptop is closed, presumably as a failsafe in case it is engaged by accident.