Henry Gantt Would be Proud

Code Snippet: ctemplate

Content management systems like Django typically do not embed HTML strings directly in code. They separate the presentation of the data out from the code which assembles the data by using templates. Here is an example Django template taken from a small App Engine project of mine:

<div class="resultsSectionItems">
{% for comment in friend.comments|slice:":29" %}
  <div><a href="http://friendfeed.com/e/{{ comment.entryObj.entryId }}" ... etc
  <span class="commentText">{{ comment.commentText }}</span>
  </div>

Each "{%" block is a template command. This template iterates through comments, creating links.

Templates maintain a separation of responsibilities. The code prepares data structures populated with the data to display. The template iterates over those structures, generating and formatting output. Templates are widespread within content management systems, but they can also be useful in embedded systems work. Some examples:

• Presenting common system data to CLI, embedded web server, and SNMP backends.
• Allowing an OEM to customize the output to include their logos and branding, without having to change code.
• Easier support for multiple languages, as most text should be in templates not code. Templates also tend to compress well, lowering the footprint of internationalization.

Most CMSes are written in Python/Ruby/Java/Perl or other high level languages. There is an opensource C++ templating package by Craig Silverstein at Google called ctemplate. Here is an example which produces a portion of the Apache httpd.conf file based on internal configuration data:

# This file is autogenerated from configuration. Changes will be lost
# after the next config change.

{{#DIR}}<Directory {{PATH}}>
{{#OPTIONS}}  Options {{#OPT}}{{VAL}} {{/OPT}}{{/OPTIONS}}
  Order {{ORDER}}
</Directory>
{{/DIR}}

Code dealing with populating variables in dictionaries is bolded in the example below, as this is the key point of using ctemplate.

#include <assert.h>
#include <ctemplate/template.h>
#include <iostream>
#include <list>

void apache_example() {
  // Apache <Directory> blocks to create
  struct ApacheDir {
    const char* path;
    std::list<const char*> options;
    bool deny;
  } apache_dirs[] = {
    {"/var/www", {"FollowSymLinks"}, false},
    {"/SecretFeature", {"ExecCGI", "-Indexes"}, true},
    {"/Tetris", {}, false}
  };

  ctemplate::TemplateDictionary dict("APACHE_EXAMPLE");
  int num_dirs = sizeof(apache_dirs) / sizeof(apache_dirs[0]);
  for (int i = 0; i < num_dirs; ++i) {
    struct ApacheDir* entry = &apache_dirs[i];
    ctemplate::TemplateDictionary* sub_dict = dict.AddSectionDictionary("DIR");

    assert(entry->path != NULL);
    sub_dict->SetValue("PATH", entry->path);

    std::list<const char*>::const_iterator li;
    for (li = entry->options.begin(); li != entry->options.end(); ++li) {
      sub_dict->SetValueAndShowSection("OPT", *li, "OPTIONS");
    }
    sub_dict->SetValue("ORDER", (entry->deny ? "deny,allow" : "allow,deny"));
  }

  std::string output;
  ctemplate::ExpandTemplate("apache.tpl", ctemplate::DO_NOT_STRIP,
                            &dict, &output);
  std::cout << output << std::endl;
}

The example shows some interesting features beyond simple variable substitution. The OPTIONS section is only displayed if there are options present, by using SetValueAndShowSection() in the code. The output of running this code is:

# This file is autogenerated from configuration. Changes will be lost
# after the next config change.

<Directory /var/www>
  Options FollowSymLinks 
  Order allow,deny
</Directory>

<Directory /SecretFeature>
  Options ExecCGI -Indexes 
  Order deny,allow
</Directory>

<Directory /Tetris>

  Order allow,deny
</Directory>

Like many other templating systems, ctemplate can apply modifiers to expanded variables. The builtin modifiers mostly concern escaping of HTML, XML, or JSON to avoid common security issues like cross site scripting. It is possible to supply additional variable modifiers by subclassing ctemplate::TemplateModifier. The App Engine example at the top of this article pipes variables through a slice statement to truncate strings to a specific length. We can create equivalent functionality for ctemplate by subclassing the TemplateModifier. The Modify() method is shown in bold, as this is the key part of the implementation.

class MaxlenModifier : public ctemplate::TemplateModifier {
  virtual void Modify(const char* in, size_t inlen,
                      const ctemplate::PerExpandData* per_expand_data,
                      ctemplate::ExpandEmitter* outbuf,
                      const std::string& arg) const {
    unsigned int maxlen;
    if ((sscanf(arg.c_str(), "=%u", &maxlen) == 1) && (maxlen <= inlen)) {
      outbuf->Emit(std::string(in, maxlen));
    } else {
      outbuf->Emit(in);
    }
  }
};

void modifier_example() {
  MaxlenModifier* maxlen = new MaxlenModifier();
  if (!(ctemplate::AddModifier("x-maxlen=", maxlen))) {
    printf("AddModifier failed\n");
    exit(1);
  }

  ctemplate::TemplateDictionary dict("MAXLEN_TEST");
  dict.SetValue("LONGSTRING", "0123456789abcdefghijklmnopqrstuvwxyz0123456789");
  std::string output;
  ctemplate::ExpandTemplate("maxlen.tpl", ctemplate::DO_NOT_STRIP,
                            &dict, &output);
  std::cout << output << std::endl;
}

Our custom modifier is instantiated in the template using x-maxlen=N. Prefixing customer modifiers with "x-" is very strongly encouraged in the ctemplate documentation.

The original string: {{LONGSTRING}}
A maxlen=10  string: {{LONGSTRING:x-maxlen=10}}
A maxlen=20  string: {{LONGSTRING:x-maxlen=20}}
A maxlen=80  string: {{LONGSTRING:x-maxlen=80}}

Here is the output, with the long string truncated to various lengths:

The original string: 0123456789abcdefghijklmnopqrstuvwxyz
A maxlen=10  string: 0123456789
A maxlen=20  string: 0123456789abcdefghij
A maxlen=80  string: 0123456789abcdefghijklmnopqrstuvwxyz

I've found ctemplate to be quite useful, and I hope others do as well.

Cross Control Confusion

My first thought when starting Photoshop this morning: "Why does Photoshop need to know my location? I should turn that off."

Happy Birthday Microsoft Windows

Windows 1.0 shipped on November 20, 1985, making today the 25th birthday of Windows. Happy Birthday, Windows. What a long, strange trip it has been.

Code Snippet: getifaddrs

A few months ago I posted a description of how to use SIOCGIFCONF to retrieve information about interfaces. SIOCGIFCONF is somewhat clunky in that you use an ioctl to find out how many interfaces are present, allocate enough memory to retrieve them all, and then issue another ioctl to actually get the information. To handle the vanishingly small chance that more interfaces will be added during the time you spend allocating memory, a fudge factor of 2x is added to the memory allocation. Because, you know, its not likely the number of interfaces would double.

That was all very silly, and as it turns out in Linux there is a much better API for retrieving information about interfaces: getifaddr(). The call handles memory allocation so you don't have to pass in a buffer of sufficient size, though you do have to call freeifaddrs() afterwards to release the memory. getifaddrs allows each protocol family in the kernel to export information about an interface. The caller has to check the address family of each returned interface to know how to interpret it. For example, AF_INET/AF_INET6 contain the interface address, while AF_PACKET has statistics. Example code for these three families is shown here.

#include <arpa/inet.h>
#include <sys/socket.h>
#include <netdb.h>
#include <ifaddrs.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <linux/if_link.h>

int main(int argc, char *argv[]) {
  struct ifaddrs *ifaddr;
  int family, s;

  if (getifaddrs(&ifaddr) == -1) {
    perror("getifaddrs");
    exit(1);
  }

  struct ifaddrs *ifa = ifaddr;
  for (ifa = ifaddr; ifa != NULL; ifa = ifa->ifa_next) {
    if (ifa->ifa_addr != NULL) {
      int family = ifa->ifa_addr->sa_family;
      if (family == AF_INET || family == AF_INET6) {
        char ip_addr[NI_MAXHOST];
        int s = getnameinfo(ifa->ifa_addr,
                            ((family == AF_INET) ? sizeof(struct sockaddr_in) :
                                                   sizeof(struct sockaddr_in6)),
                            ip_addr, sizeof(ip_addr), NULL, 0, NI_NUMERICHOST);
        if (s != 0) {
          printf("getnameinfo() failed: %s\n", gai_strerror(s));
          exit(1);
        } else {
          printf("%-7s: %s\n", ifa->ifa_name, ip_addr);
        }
      } else if (family == AF_PACKET) {
        struct rtnl_link_stats *stats = ifa->ifa_data;
        printf("%-7s:\n"
               "\ttx_packets = %12u, rx_packets = %12u\n"
               "\ttx_bytes   = %12u, rx_bytes   = %12u\n",
               ifa->ifa_name,
               stats->tx_packets, stats->rx_packets,
               stats->tx_bytes, stats->rx_bytes);
      } else {
        printf("%-7s: family=%d\n", ifa->ifa_name, family);
      }
    }
  }

  freeifaddrs(ifaddr);
  exit(0);
}

On my system the output is as follows (though I've obscured the addresses):

lo     :
        tx_packets =     16714641, rx_packets =     16714641
        tx_bytes   =   1943837629, rx_bytes   =   1943837629
eth0   :
        tx_packets =    102862634, rx_packets =    118537985
        tx_bytes   =   3472339330, rx_bytes   =    698859563
gre0   :
        tx_packets =            0, rx_packets =            0
        tx_bytes   =            0, rx_bytes   =            0
lo     : 127.0.0.1
eth0   : 10.0.0.1
lo     : ::1
eth0   : 1111:1111:1111:1111:a800:1ff:fe00:1111
eth0   : fe80::a800:1ff:fe00:1111%eth0

More on Increasing the Speed of Light

A modest suggestion to increase the speed of light resulted in interesting discussion which I would like to highlight by Kit Dotson at SiliconANGLE and by Howard Marks at Network Computing. Howard Marks wrote about details of the chemistry of fiber optic cables, in particular that the index of refraction is related to the density of the material. A fiber with a 10% lower index would be less dense than water, which makes it unlikely to be practical. C'est la vie.

---

Also I'll state again: the speed of light in fiber only matters for wide area links. The propagation delay in 100 meters of fiber is dwarfed by queueing and software delays, to the point of insignificance. In fact if we could reduce the cost or power consumption of short range lasers by making the speed of light even slower in the fiber they drive, that would be a good tradeoff.

For long range links things become more interesting. Internet lore says that Amazon found each 100 msec of page load time resulted in a 1% increase in abandoned transactions, though I cannot find a hard reference for this data. E-commerce is heavily studied as there is money involved, but general satisfaction with a website increases when it has "teh snappy." This isn't just a function of bandwidth: most web pages require multiple round trips to fully render, owing to the pervasive use of JavaScript to trigger the loading of additional page elements. The round trip time matters.

For long reach fiber the useable spectral capacity is probably the most important factor, as this determines the numer of wavelengths it can carry and is the primary economic justification. Long reach fibers also have to trade off clarity (i.e. loss of signal) because that determines how far apart the amplifiers/regenerators have to be. This is where I'd throw the index of refraction into the mix, as another factor to be weighed and optimized for.

Twerpetition

Intel and Achronix Get Engaged

In January JP Morgan predicted that Intel would acquire an FPGA vendor in 2010. Speculation immediately focussed on Altera and Xilinx, which are large enough to have a material impact on Intel's sales. I wrote about it then, speculating that Intel would use the technology to get into various embedded market segments without needing a zillion SoC variants. Choose a die with appropriate I/O pins, load the logic into FPGA blocks alongside the CPU, and voila!

Yesterday the Wall Street Journal reported that Intel is opening their fabs to Achronix Semiconductor, a startup with interesting FPGA technology. The Achronix home page highlights what is presumably the immediate benefit to Intel, in unlocking additional sales to US military and intelligence agencies.

"The Achronix Speedster22i FPGA Platform uniquely enables applications that require an end-to-end supply chain within the United States. Being built at an onshore location offers significant advantages to programmable logic users who demand the highest level of security."

Presumably the agencies interested in using these parts want to embed optimized hardware to offload algorithms from software. This can be necessary for some applications, if the customer has the resources to implement it. The desire for an on-shore supply chain which can be audited is in reaction to the inadvertent use of counterfeit chips in previous military systems.

Achronix is using branding for the product line which looks remarkably like Intel's, and it seems certain the deal has provisions for cancellation or modification upon change of control to another party. This announcement also amounts to Intel marking their territory for an acquisition.

I/Os Considered Important

DoD requirements notwithstanding, there are relatively few applications where embedding algorithms in FPGAs makes sense. The drawback has never been a technological one, in requiring closer cooperation between CPU and FPGA. It is a business issue: once you commit to a specialized hardware design, the clock starts ticking. There will come a day when a software implementation could meet the requirements, and at that point the FPGA becomes an expensive liability in the BOM cost. You have to make enough profit from the hardware offload product to pay for its own design, plus a redesign in software, or the whole exercise turns out to be a waste of money.

There is another quote on the Achronix technology page which is quite relevant:

"Speedster FPGAs include four embedded DDR1/2/3 controllers, each offering up to 72 bits of data at 1066 Mbps. ... The DDR controllers are fully by-passable so the pins can be used as general I/O if the DDR controllers are not needed." (emphasis added)

Being able to select various I/O drivers for a pin in an FPGA is relatively common, but generally quite limited. Very high speed SERDES pins often cannot be reassigned or are restricted in what else they can be used for, because the high speed interface is sensitive to layout and loading. If Achronix has developed robust I/O muxing with more flexibility, this would be very interesting to Intel. It gets them closer to having a small selection of silicon dies, with different IP loads to target specific markets.

Using FPGAs as a way to tailor chips for specific markets makes a lot more sense than algorithm offload, IMHO. This provides products which could not otherwise exist, as it would be difficult to justify the incremental cost of each different chip. Amortizing the cost of silicon development over a much larger number of different applications makes more sense.