Wednesday, October 6, 2010

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."

Monday, October 4, 2010

Apps Has a New Meaning Now

Applebees table ad for apps $5 drafts $2

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

Thursday, September 30, 2010

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!"

Wednesday, September 29, 2010

Twitter URL Search No Worky?

Twitter logoSomething 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.

Monday, September 27, 2010

Peerrihelion

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

Wednesday, September 22, 2010

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().

Thursday, September 16, 2010

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");
  }
}

Monday, September 13, 2010

Lucky Numbers

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


Frys Ad for 808.8GB drive, $58

Thursday, September 9, 2010

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.


Screenshot with reversed video
(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.

Tuesday, September 7, 2010

Custom Body Parts On Demand

Several weeks ago I cracked a tooth, which had to be capped with a crown. Years ago this would have required the dentist to cut away the broken sections of tooth, and then a mold would be sent off to a manufacturer. The crown would come back several weeks later, while in the meantime I'd have to be very careful of the broken tooth.

That was then, this is now. Now the dentist uses a laser scanner to make a 3D model of the shape of the tooth before and after trimming out the broken section. The difference between the two gives the rough shape of the crown to be made, which the dentist can adjust with CAD software. He described the adjustments as "the tooth the way it was twenty years ago, not the way it is now."


CAD software sculpting dental crown

Now we don't send this CAD model off to be manufactured. The dentist has a CNC milling machine in the office. It starts from a ceramic ingot and cuts away anything which isn't shaped like the desired crown.



We're living in the future, where replacement body parts are sculpted on demand. It makes me feel old that I can remember it wasn't always this way.

Thursday, August 26, 2010

Code Test Haiku

Function works first time
Briefly feel elation...
Did it really work?

Having code work the first time is more annoying than having it fail.

If it doesn't work I go poke around to fix the failing tests, and when it finally passes I feel confident that it really works.

When code works the first time I still go poke around in the unit tests, only this time I have no idea what I'm looking for. Did it really get tested? Does it really test what I think its testing? Surely there is something wrong somewhere.

Wednesday, August 18, 2010

x86 vs ARM Mobile CPUs

The ARM architecture dominates mobile computing. It is used in all popular mobile phones and in a huge percentage of battery powered devices generally. This is due partly to its good overall performance, but especially due to its performance per watt expended. ARM chips consume very little power when compared to x86, and ARM's power consumption still excels even when compared to other RISC chips. At one time even Intel manufactured ARM chips, the result of its purchase of the DEC semiconductor business and its excellent StrongARM design. In 2006 Intel sold its ARM products to Marvell Semiconductor, committing to x86 for every segment of the computing market.

Its easy to assume that this state of affairs will continue, and that Intel will never successfully compete in the mobile market. I suspect that is too simplistic an assumption. There are two main sources of power dissipation in modern microprocessors: the power consumed by transistors actively switching, and the power lost to leakage current.

active current, leakage current into substrate
x86 vs ARM: Active Power

It requires power to switch a CMOS transistor 0->1 or 1->0, so one way to reduce power consumption is to have fewer transistors and to switch them at a lower frequency. x86 is at a disadvantage here compared to ARM, which Intel and AMD's design teams have to cover with extra work and cleverness. The vagaries of the x86 instruction set burdens it with hardware logic which ARM does not require.

  • Since the Pentium Pro, Intel has decoded complex x86 instructions down to simpler micro-ops for execution. AMD uses a similar technique. This instruction decode logic is active whenever new opcodes are fetched from RAM. ARM has no need for this logic, as even its alternate Thumb encoding is a relatively straightforward mapping to regular ARM instructions.
  • x86_32 exposes only a few registers to the compiler. To achieve good performance, x86 CPUs implement a much larger number of hardware registers which are dynamically renamed as needed. ARM does not require such extensive register renaming logic.
  • Every ARM instruction is conditional, and simple if-then-else constructs can be handled without branches. x86 relies much more heavily on branches, but frequent branches can stall the pipeline on a processor. Good performance in x86 requires extensive branch prediction hardware, where ARM is served with a far simpler implementation.

x86 vs ARM: Leakage Current

Intel Nehalem processor dieLeakage current became a significant contributor to power consumption in 2003 with the move from 0.18 to 0.13 micron feature sizes, and has become more significant in each subsequent generation. The industry is now moving into 0.032 micron technologies.

A capacitor is formed when two conductive materials are separated by an insulator, called the dielectric. The capacitance is determined by the quality of the insulating material, quantified by the dielectric constant k. Higher k means more capacitance. "Leakage" is current which is able to flow out of the ASIC transistors and into the silicon substrate. To reduce the current leaking out, one needs to make a better dielectric between the transistor and the bulk of the silicon. This is generically referred to as high-k silicon technology.

As we're now talking about silicon fabrication techniques, we have to start talking about Intel specifically rather than the x86 architecture in general. Intel began using a high-k dielectric in production in 2007, during the 45 nm generation of parts. The rest of the industry has been experimenting with such materials, but is only now rolling it into the 32 nm generation. Intel hasn't stopped working on the technique, their 32 nm process benefits from the last several years of experience.


x86 vs ARM: Predicting The Future

Leakage current becomes more significant with each generation of process technology. The power consumed by actively switching transistors has been radically reduced over the last few years, leaving leakage as the more significant source of current consumption. It is difficult to estimate how serious the effect is, but this article from March 2008 shows leakage current starting out relatively insignificant in 180 nm silicon but growing to nearly 40% of total power consumption in a 50 nm process.

So far as I can see, this trend will continue. Leakage current will soon become the dominant factor in CPU power consumption. In fact, in 32 nm processes it might already be the primary factor. This is where the game changes: the advantage for total power consumption shifts away from the efficiency of the CPU architecture and design, and to the process technology of the fab. Presumably, this trend informed Intel's decision to sell their ARM assets to Marvell: there is little reason to enrich a competitor if the advantages of doing so will diminish over time.


There is still room for clever design, of course. To reduce active power consumption, processor designs have long stopped the clock to unused portion of the CPU. To reduce leakage current, AMD is taking the next step to actually remove the power supply to those portions of the CPU. For ARM, that design choice makes even more sense. ARM has no control over the fab, their designs have to minimize assumptions about the underlying silicon technology.

Right now ARM reigns supreme in the mobile space, but the strengths which gave it an advantage over x86 are rapidly becoming less compelling. Having to compete directly on silicon process sophistication moves the game onto Intel's turf, which Intel is happy to capitalize on with its Medfield platform. Its a great time to be in the mobile space.

Monday, August 16, 2010

A Scene from the Near Future


FURNITURE LICENSE AGREEMENT

THIS FURNITURE IS LICENSED, NOT SOLD. By using the furniture you signify that you have read and agree to all the terms of this license agreement.

THIS IS A LEGAL AND BINDING AGREEMENT BETWEEN YOU, HEREINAFTER ALSO REFERRED TO AS "USER", AND THE FURNITURE RETAILER, HEREINAFTER ALSO REFERRED TO AS THE "STORE". BY SITTING ON, LYING ON, OR OTHERWISE MAKING USE OF THE FURNITURE, HERINAFTER REFERRED AS THE "PRODUCT", (OR AUTHORIZING ANY OTHER PERSON TO DO SO), YOU INDICATE YOUR COMPLETE AND UNCONDITIONAL ACCEPTANCE OF ALL THE TERMS AND CONDITIONS OF THIS LICENSE AGREEMENT. THIS LICENSE AGREEMENT CONSTITUTES THE COMPLETE AGREEMENT BETWEEN YOU AND THE STORE. IF YOU DO NOT AGREE TO THE TERMS OF THIS LICENSE AGREEMENT, YOU MUST DESTROY THE ITEM OF FURNITURE (WITH ALL ACCOMPANYING MATERIALS).

IMPORTANT: CAREFULLY READ THIS LICENSE BEFORE USING THIS PRODUCT. SITTING ON, LYING ON, OR OTHERWISE USING THIS PRODUCT INDICATES YOUR ACKNOWLEDGMENT THAT YOU HAVE READ THIS LICENSE AND AGREE TO BE BOUND BY AND COMPLY WITH ITS TERMS. IF YOU DO NOT AGREE, RETURN THE COMPLETE PRODUCT TO THE STORE WITHIN 30 DAYS OF THE DATE YOU PURCHASED IT FOR A FULL REFUND. THIS LICENSE AGREEMENT IS YOUR PROOF OF LICENSE. PLEASE TREAT IT AS VALUABLE PROPERTY.


A. LICENSE:

The STORE provides the user with the furniture and separate cushions (together called the "PRODUCT") and we grant the user a license to use the PRODUCT in accordance with the terms of this License. Any supplemental materials provided to the user as part of support services provided by the STORE for the PRODUCT shall be considered part of the PRODUCT and subject to the terms and conditions of this License. The copyright and all other rights to the PRODUCT shall remain with the STORE or its licensors.


B. THE USER MAY:

  1. transfer the PRODUCT to the USER's primary residence, and place it within a single room therein.
  2. move the PROUCT to a different room within the same structure. The user must acquire and dedicate a supplementary license for each separate room in which the PRODUCT may be used. A license for the PRODUCT may not be shared or used concurrently in different rooms.

C. THE USER MAY NOT:

  1. use the PRODUCT or make copies of it except as permitted in this License.
  2. use the PRODUCT within a structure which is not the USER's primary residence. A separate commercial license applies to these cases.
  3. use the PRODUCT outside a structure, i.e. outdoors. A separate public performance license applies to these cases.
  4. reupholster, except within the initial TEN (10) days of a license term. Outside of the initial ten days, reupholstery will require an early renewal.
  5. deconstruct, reverse engineer, or disassemble the PRODUCT except to the extent the foregoing restriction is expressly prohibited by applicable law. The PRODUCT may not be used as a template from which to build additional furniture.
  6. rent, lease, assign, sell, or transfer the PRODUCT.
  7. modify the PRODUCT or merge all or any part of the PRODUCT with another item of furniture.
  8. separate the component parts of the PRODUCT for use in more than one room.

D. TERM:

This license shall remain in effect only for so long as the user is in compliance with the terms and conditions of this agreement. This license will terminate if the user fails to comply with any of its terms or conditions. The user agrees, upon termination, to destroy the PRODUCT.


E. U.S. GOVERNMENT RIGHTS:

With respect to any acquisition of the PRODUCT by or for any unit or agency of the United States Government (the "Government"), the Product shall be classified as "commercial furniture", as that term is defined in the applicable provisions of the Federal acquisition Regulation (the "FAR") and supplements thereto, including the Department of Defense (DoD) FAR Supplement (the "DFARS"). The Product was developed entirely at private expense, and no part of the Product was first produced in the performance of a Government contract. If the Product is supplied for use by DoD, the Product is delivered subject to the terms of this Agreement and either (i) in accordance with DFARS 3.1415-9 (a) and 2.71(a), or (ii) with restricted rights in accordance with DFARS 012-345-6789 (c)(1)(ii)(JUN 1970), as applicable. If the Product is supplied for use by a Federal agency other than DoD, the Product is commercial furniture delivered subject to the terms of this Agreement and (i) FAR 6.66(a); (ii) FAR 57.57-57; or (iii) FAR 12.345-67(ALT VIII), as applicable.


F. GENERAL:

This License is the entire agreement between the STORE and the USER, superseding any other agreement or discussions, oral or written, and may not be changed except by a signed agreement. This License shall be governed by and construed in accordance with the laws of the state of Delaware, USA, excluding that body of law applicable to choice of law and excluding the United Nations Convention on Contracts for the International Sale of Goods and any legislation implementing such Convention, if otherwise applicable. If any provision of this License is declared by a Court of competent jurisdiction to be invalid, illegal, or unenforceable, such a provision shall be severed from the License and the other provisions shall remain in full force and effect.

Friday, August 13, 2010

Bury Brigades as the Future of Media?

Broadcast transmission towerI'm currently reading Cognitive Surplus, by Clay Shirky. It builds upon his earlier Here Comes Everybody, detailing how the Internet fundamentally changes the media landscape to an extent not seen since Gutenberg. Before the Internet, when the cost of distribution was non-trivial, you ended up with publishers, producers, TV networks, and a whole host of powerful institutions built upon managing the production. When the cost of distributing media drops to essentially nothing, when everybody who wants to can become a publisher without having to ask permission or convince anybody of the value of their work, it completely disrupts the models which evolved in the prior era. A lot more material will be produced. Much of it will be trash, as we've moved the filtering function away from an editor before publication and onto the audience after publication.

Something will evolve to fill an institutional role in the New Media. The current period of creative chaos is unlikely to continue forever. A portion of the population is willing to wade through the trash in order to surface the truly great, but only a small portion. The rest of us need some filtering, or curation as the cool kids seem to call it.


Warning: Speculation Ahead

Are Digg Bury Brigades early precursors to a form of New Media institution? Organized groups, loosely connected by shared interests but not centrally funded or managed, they influence the spread of material online and therefore gain some control over media distribution. Bury Brigades are negative filters, suppressing material they don't agree with rather than surfacing material they want to promote. There will be equally a role for positive filters, entities which seek out and promote material. Motivation for groups to organize as positive filters is less clear, as simple altruism and a desire for recognition only go so far.

Tuesday, August 10, 2010

A Barrrgain Indeed

Barrr screenshotIf you have an Android phone, Barrr is a wonderful game by FireDroid. It is available in the Android Market or direct from their site via a QR barcode. It was developed by two Dutch students as part of their degree program in Multimedia: Mariecke Kouwenberg and Roy van der Veen.

Barrr is a lighthearted simulation of a pirate bar complete with tattoo station, video games, karaoke, and a dart board. Each scenario takes a couple minutes to complete, making it a great diversion for short interludes.

Price: free.