Coding Relic

Post-mortem debugging: core files

2009-06-30T06:05:00.000-07:00

When one has a core file, one runs gdb. Its simply the way things were Meant To Be, right? Yet gdb isn't the right tool for the job in all cases. If you're dealing with a corrupted heap, gdb is not very helpful. You can see the portion of the heap which caused the process to fault (most likely in malloc or free), but identifying the junk in memory is an exercise in puzzling it out and looking for patterns. It is often useful in such cases to search the rest of the process address space for pointers into the corrupted area of the heap. Though gdb can be used to search for patterns in memory, it isn't very good at it. For example consider the following macro:

define searchmem
    set $start = (char *) $arg0
    set $end = (char *) $arg1
    set $pattern = (unsigned int) $arg2
    set $p = $start
    while $p < $end
        if (*(unsigned int *) $p) == $pattern
            printf "pattern 0x%x found at 0x%x\n", $pattern, $p
        end
        set $p++
    end
end

document searchmem
    search between $argv0 and $argv1 for pattern $argv2
end

This macro can look only for 32 bit numbers, not any sort of regular expression, and it is very, very slow. We'd really like to run grep, but if gdb provides a way to run grep over the core contents I haven't found it. Instead, Gentle Reader, we'll write a utility to output the core file to text so that grep or any other Unix tool can be used. This would be a job for od or hexdump except for two things:

We'd like to see the addresses of the data being dumped.
The core might be in the wrong endianness, such as a MIPS-BE core file on an x86 host.

Instead of using a generic binary dump like od we'll construct a tool specifically for core files, but first we need to understand their contents.

Process Address Space

Linux and modern Unix-ish operating systems dynamically map shared libraries into the process address space. These libraries are not packed tightly up against one another. For alignment and page protection reasons, there are gaps between them.

Each library generally consists of multiple segments:

instructions, called the TEXT segment.
uninitialized data to be zero filled, called BSS
initialized data (i.e. variables initialized to a non-zero value), called DATA

You can see the memory segments for a running process in /proc/<pid>/maps. Here is an example:

# cat /proc/1261/maps
0fc73000-0fc80000 r-xp 00000000 01:00 713        /lib/libA.so.1
0fc80000-0fc83000 ---p 0000d000 01:00 713        /lib/libA.so.1
0fc83000-0fc92000 rwxp 00000000 01:00 713        /lib/libA.so.1
...deleted...
10000000-1000c000 r-xp 00000000 01:00 1190       /bin/myapp
1001b000-1001c000 rwxp 0000b000 01:00 1190       /bin/myapp
...deleted...

libA's callable functions are in the TEXT segment, mapped at addresses 0x0fc73000 through 0x0fc80000. Note the permission bits on these pages: read-only plus executable. Write permission is denied, making it safe to share the same physical pages of RAM amongst multiple processes.

The libA BSS segment extends from 0x0fc80000 through 0x0fc83000. These pages are mapped with no permissions at all, even a read access will trigger a page fault. The kernel will supply a zero-filled page on the first fault, and mark its permissions as read+write.

The libA DATA segment is at 0x0fc83000 though 0x0fc92000. This region is populated with the initialized data, so it has read+write permissions already. No page fault will be triggered on access to these pages.

When the process dies, the core file needs to preserve these scattered memory areas. Core files from a Linux process are written in ELF format, which I will stubbornly continue to refer to as the Extensible Linking Format. ELF defines data sections with associated virtual addresses, allowing it to describe data scattered across a process address space. Let's examine the output of "readelf -l" on the core from this process:

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz   Flg Align
  NOTE           0x0003f4 0x00000000 0x00000000 0x006f4 0x00000      0
  LOAD           0x001000 0x0fc73000 0x00000000 0x00000 0x0d000  R E 0x1000
  LOAD           0x001000 0x0fc80000 0x00000000 0x00000 0x03000      0x1000
  LOAD           0x001000 0x0fc83000 0x00000000 0x0f000 0x0f000  RWE 0x1000
  ..etc...

The NOTE section contains various global information about the dead process, including its name and the contents of the CPU registers at the time it died. If you use "objdump -h" to list the core sections you'll see two additional sections: reg0/2 and reg0. These sections don't actually exist in the file, objdump breaks out the register contents from the NOTE section into their own pseudo-sections.

The LOAD sections contain the data from the process address space. The first one starts at a virtual address of 0xfc73000. That is the TEXT segment for libA, which we looked at earlier. Note the FileSiz is 0: to save space, the kernel skips dumping the contents of non-writable pages. gdb would fetch these sections from the executable file instead. The second LOAD section contains the libA BSS, and similarly its FileSiz is zero: this process died before it ever referenced anything in the BSS of libA. None of the pages had been faulted in and therefore none were writable.

The third LOAD section is the interesting one. This is the initialized DATA section. Because these pages were writable, they were saved to the core file and so the FileSiz is 0x0f000 (which matches the size of the segment from the /proc/<pid>maps file, above).

BFD

libbfd is one of several libraries available for working with ELF files. We'll use libbfd to process the core file, dumping it as hex words to a text file.

According to the history I can find, libbfd was created at Cygnus Support to deal with the myriad binary formats that sprang up in the 1980s and 90s. In response to how difficult it would be to encapsulate the various formats in a single library David Henkel-Wallace reportedly responded "big f---ing deal," and thus libbfd was christened. The name has since been clarified as "binary file descriptor."

    #include <bfd.h>

    bfd        *abfd;
    asection   *sect;
    char       *corefilename;
    enum bfd_endian endian;

    if ((abfd = bfd_openr(corefilename, NULL)) == NULL) {
        /* ... error handling ... */
    }

First we open the file using bfd_openr(). *abfd is the handle used to access the file, all other libbfd APIs take it as an argument.

    if (!bfd_check_format (abfd, bfd_core)) {
        printf("%s does not appear to be a core file.\n", corefilename);
        /* ... error handling ... */
    }

We check that the file is actually a core and not some other type of file. bfd_core is part of an enumerated type; other types which libbfd can check for include bfd_object for ELF programs or .o files, and bfd_archive for ar-style arcives.

    endian = abfd->xvec->byteorder;

libbfd handles the endianness of fields in the program and section headers, returning the result in the CPU's native byte order regardless of the endianness of the ELF file. It doesn't do anything about the data within those sections. Since we're going to dump the data in the core file, we need to know the endianness.

    for (sect = abfd->sections; sect != NULL; sect = sect->next) {
        bfd_vma        vma  = bfd_section_vma (abfd, sect);
        bfd_size_type  size = bfd_section_size(abfd, sect);
        const char    *name = bfd_section_name(abfd, sect);

We loop over each ELF section, pulling out the virtual address and size of the data it holds. The size will be zero in many cases, as shown above for the libA TEXT and BSS sections.

        if (!bfd_get_section_contents(abfd, sect, buf, (file_ptr)0, size)) {
            fprintf(stderr, "Could not read section %s\n", name);
            exit(5);
        }

We fetch the contents of each section, ready to print them to hex.

With a modicum of string manipulation we have a hex dump of the core contents:

0fc84710:  615f6669  6e616c69  7a65005f  4a765f52    a_finalize._Jv_R
0fc84720:  65676973  74657243  6c617373  6573006c    egisterClasses.l
0fc84730:  6962632e  736f2e36  0061646c  65723332    ibc.so.6.adler32
0fc84740:  00636f6d  70726573  73320064  65666c61    .compress2.defla

libbfd licensing

libbfd is GPL. It is not LGPL, which allows dynamic linking to proprietary code, but the full GPL. Any use of libbfd encumbers the rest of the software linked to it with the GPL and obligates you to provide the source code to anyone to whom you provide a binary. Its important to consider what this means: if you're developing tools for internal use by developers, the GPL is not onerous. Indeed, the source code of the utility will likely be checked into the version control system that all developers can access anyway.

More later...

If you for need to incorporate ELF file support into a proprietary software tool, then libbfd is not useable. I intended to provide the same core2hex example using FreeBSD's libelf, but this article is already quite long so I'm going to defer it until next time.

Pre-mortem Backtracing

2009-05-15T05:17:00.000-07:00

A backtrace is often the first step in debugging a problem. Generating a backtrace is generally thought of as a function of the debugger, on a core file after a process has died. However it is sometimes quite useful to generate a live backtrace while a process runs. For example, crashing the process in the field may not be acceptable if a problem is survivable. Logging a backtrace and other information can provide enough to locate the root cause, without having to trigger any customer downtime.

gcc backtrace support

The simplest way to get a crude backtrace is the __builtin_return_address() macro supplied by gcc. You provide the frame number you want to retrieve, and get the return address for that stack frame:

void do_backtrace2()
{
    void *pc0 = __builtin_return_address(0);
    void *pc1 = __builtin_return_address(1);
    void *pc2 = __builtin_return_address(2);
    void *pc3 = __builtin_return_address(3);

    printf("Frame 0: PC=%p\n", pc0);
    printf("Frame 1: PC=%p\n", pc1);
    printf("Frame 2: PC=%p\n", pc2);
    printf("Frame 3: PC=%p\n", pc3);
}

This code will produce the following output:

Frame 0: PC=0x80483ca
Frame 1: PC=0x80483e1
Frame 2: PC=0x62079d
Frame 3: PC=0x80482b9

__builtin_return_address() has significant limitations. It constructs code at compile time to walk back through the stack frames. That means you cannot use a variable in a loop, you can only use integer constants like the 0,1,2,3 shown above. Also on some architectures, including my beloved MIPS, only __builtin_return_address(0) works. MIPS has no frame pointer, making it difficult to walk back up the stack. Frame 0 can use the return address register directly.

glibc's backtrace()

glibc contains a simple backtrace function, which is somewhat more powerful than __builtin_return_address(). The backtrace() call populates an array with the program counter of each calling function, while a separate backtrace_symbols() call can look up the symbolic names for each address:

#include <execinfo.h>

#define BACKTRACE_SIZ   64
void do_backtrace()
{
    void    *array[BACKTRACE_SIZ];
    size_t   size, i;
    char   **strings;

    size = backtrace(array, BACKTRACE_SIZ);
    strings = backtrace_symbols(array, size);

    for (i = 0; i < size; i++) {
        printf("%p : %s\n", array[i], strings[i]);
    }

    free(strings);  // malloced by backtrace_symbols
}

The output shows the backtrace with the address of each function call site:

# gcc -g -o backtrace ./backtrace.c
# ./backtrace 
0x8048422 : ./backtrace(backtrace_symbols+0xd6) [0x8048422]
0x80484be : ./backtrace(backtrace_symbols+0x172) [0x80484be]
0x80484d5 : ./backtrace(backtrace_symbols+0x189) [0x80484d5]
0x071479d : /lib/tls/libc.so.6(__libc_start_main+0xed) [0x71479d]
0x804837d : ./backtrace(backtrace_symbols+0x31) [0x804837d]

To get useful symbolic names, the -rdynamic option must be passed to the linker:

# gcc -g -rdynamic -o backtrace ./backtrace.c
# ./backtrace 
0x804874a : ./backtrace(do_backtrace+0x1a) [0x804874a]
0x80487e6 : ./backtrace(foo1+0xb) [0x80487e6]
0x80487fd : ./backtrace(main+0x15) [0x80487fd]
0x012679d : /lib/tls/libc.so.6(__libc_start_main+0xed) [0x12679d]
0x80486a5 : ./backtrace(backtrace_symbols+0x31) [0x80486a5]

There is also a backtrace_symbols_fd() function, which nicely prints the output to a file descriptor without having to malloc a table of strings. If thats all you're trying to do, it is a simpler API.

As an aside: notice how the address of __libc_start_main varies in the examples above, 0x62079d versus 0x71479d versus 0x12679d? That is address space randomization in action. libc is mapped at a randomized base address every time a binary is started. Yhe offset of __libc_start_main within the page is a constant 0x79d, but the upper bits of the address will vary from one run to the next. This helps prevent buffer overflow and other code injection attacks, by randomizing the address of library routines.

libunwind

libunwind is a library for extracting call chain information. It supports many different CPU architectures. Here is an example of using libunwind to accomplish a similar result as glibc's backtrace() function:

#include <libunwind.h>

void do_backtrace2()
{
    unw_cursor_t    cursor;
    unw_context_t   context;

    unw_getcontext(&context);
    unw_init_local(&cursor, &context);

    while (unw_step(&cursor) > 0) {
        unw_word_t  offset, pc;
        char        fname[64];

        unw_get_reg(&cursor, UNW_REG_IP, &pc);

        fname[0] = '\0';
        (void) unw_get_proc_name(&cursor, fname, sizeof(fname), &offset);

        printf ("%p : (%s+0x%x) [%p]\n", pc, fname, offset, pc);
    }
}

The output:

0x80486b3 : (foo+0xb) [0x80486b3]
0x80486ca : (main+0x15) [0x80486ca]
0x016379d : (__libc_start_main+0xed) [0x16379d]
0x80484c9 : (_start+0x21) [0x80484c9]

That is quite a bit more code to get a simple backtrace, but libunwind offers more capability to examine the program state at each frame. For example, one can print the saved register values:

#include <libunwind.h>

void do_backtrace2()
{
    unw_cursor_t    cursor;
    unw_context_t   context;

    unw_getcontext(&context);
    unw_init_local(&cursor, &context);
    while (unw_step(&cursor) > 0) {
        unw_word_t  offset;
        unw_word_t  pc, eax, ebx, ecx, edx;
        char        fname[64];

        unw_get_reg(&cursor, UNW_REG_IP,  &pc);
        unw_get_reg(&cursor, UNW_X86_EAX, &eax);
        unw_get_reg(&cursor, UNW_X86_EDX, &edx);
        unw_get_reg(&cursor, UNW_X86_ECX, &ecx);
        unw_get_reg(&cursor, UNW_X86_EBX, &ebx);

        fname[0] = '\0';
        unw_get_proc_name(&cursor, fname, sizeof(fname), &offset);
        printf ("%p : (%s+0x%x) [%p]\n", pc, fname, offset, pc);
        printf("\tEAX=0x%08x EDX=0x%08x ECX=0x%08x EBX=0x%08x\n",
                eax, edx, ecx, ebx);
    }
}

The output:

0x80486b3 : (foo1+0xb) [0x80486b3]
 EAX=0x00000000 EDX=0x00b548b0 ECX=0x00000000 EBX=0x00000000
0x80486ca : (main+0x15) [0x80486ca]
 EAX=0x00000000 EDX=0x00b548b0 ECX=0x00000000 EBX=0x00000000
0x044879d : (__libc_start_main+0xed) [0x44879d]
 EAX=0x00000000 EDX=0x003368b0 ECX=0x00000000 EBX=0x00000000
0x80484c9 : (_start+0x21) [0x80484c9]
 EAX=0x00000000 EDX=0x00b548b0 ECX=0x00000000 EBX=0x00000000

When would this be useful? Given the relative costs, it is not unusual to have an embedded CPU with considerably more RAM than flash. In the event of a crash there may not be enough flash to save a full core file. Having the process deliberately catch SIGSEGV and dump its own backtrace with register values means you'd at least have something to work with even if there is no core file.

Conclusion

Over time I think I have used __builtin_return_address(0) more often than any of the other techniques. Whether constructing simple performance instrumentation or logging problems from the field, knowing the caller has often been sufficient. For more extensive backtrace functionality I end up using libunwind. The backtrace() function in glibc always seems to be too heavy for the simple stuff yet not sufficient for the complex stuff.

Desperate Bugs Demand Desperate Measures

2009-05-01T04:57:00.000-07:00

After chasing a pernicious bug long enough, there is a strong temptation to find a way to make it be someone else's problem for a while.

if (critical_operation() == FAILED) {
    /* Uh oh. Quick, we need a distraction! */
    switch((rand() % 4)) {
        case 0: blame = "killall -SEGV kick_watchdog";     break;
        case 1: blame = "killall -ABRT cli_process";       break;
        case 2: blame = "cat /dev/urandom >/proc/kmem";    break;
        case 3: blame = "killall -FPE  hardware_manager";  break;
    }
    system(blame);
    system("rm /var/log/*.log"); /* Destroy the evidence */
    sleep(10); /* Wait for the other process to die first */
    return;
}

More Google App Engine - Feedflares

2009-04-09T05:27:00.000-07:00

Today's article is a discussion about some of the infrastructure for running this site. So far as I can tell from the logs and analytics, nearly everyone reading this blog does so via RSS. The RSS feed for this site is provided by FeedBurner, now part of Google. FeedBurner supports FeedFlares, small widgets appended after the content which can supply additional information or link to other services. I currently use several FeedFlares in the RSS feed, for del.icio.us and friendfeed. The friendfeed flare is new, and is the topic of this writeup.

friendfeed is a social media aggregation service, collecting updates from services like Digg, Flickr, and various blog platforms into a single stream of updates. Many good articles about friendfeed can be found on louisgray.com.

The RSS feed for this blog is imported into friendfeed where people can see it, mark it as something they liked, or leave comments. At the time I started working on this project there was not a FeedFlare for friendfeed. There is now, but I decided to finish my version anyway and post it here. As Google App Engine is my favorite new toy, the FeedFlare is a GAE application.

We'll go straight to the code which gathers information from friendfeed to create the FeedFlare. I'm going to skip the boilerplate code for an application on the Google App Engine. It can be found on an earlier article about the App Engine, if needed. The complete source for this feedflare is also available for download.

class FriendfeedFlare(webapp.RequestHandler):
  def get(self):
    self.response.headers['Content-Type'] = "text/plain"

    scheme, host, path, param, query, frag = urlparse.urlparse(self.request.url)
    args = cgi.parse_qs(query)

    url      = self.parseArg(args, "url")
    nickname = self.parseArg(args, "nickname")
    api_key  = self.parseArg(args, "api_key")

    if (url == None):
        self.response.out.write("<FeedFlare><Text>No URL specified!</Text></FeedFlare>\n")
        return

    subscribed = 1 if (nickname != None and api_key != None) else 0

Three arguments are accepted, using the standard CGI convention of http://host/path?arg1=value&arg2=value

url - the url of the RSS item this FeedFlare should reference. This argument is required.
nickname - the friendfeed account to authenticate as. If provided, the search will be restricted to friends of this nickname. If not provided, we search all entries on friendfeed.com.
api_key - the API Key to authenticate us. If nickname is provided the api_key must also be provided.

Note: At the time of this writing (4/9/2009) the nickname functionality to restrict results to subscribers is not working. It was working a couple days ago, but seemed to break just as I posted this article. I'll update the post if I get it working again, for now the feedflare is useable when searching all entries on friendfeed.com.

urlparse.urlparse() is employed to break the URL into its main components, and then cgi.parse_qs() pulls out the individual parameters. parse_qs() returns each argument as a list, because it allows multiple instances of an argument. In this case only one makes sense, so we get back a list with one member. self.parseArg() is a small helper routine to return None if the argument is not present, or the first element in the list returned from cgi.parse_qs().

    try:
        ffsession = friendfeed.FriendFeed(nickname, api_key);
        entries   = ffsession.fetch_url_feed(url, subscribed);
    except IOError:
        self.error(503);
        return

Friendfeed supplies Python wrapper functions for their API. The wrapper functions are used here to connect to friendfeed.com, using the authorization credentials (if present). If friendfeed is not responding, a 503 response is sent to feedburner.com. This Service Unavailable result tells feedburner to continue to use its cached information and to try again later.

fetch_url_feed() is a function added to the friendfeed API, to support their /api/feed/url API. It fetches all entries which reference the given url.

    totalshares   = 0
    totalcomments = 0
    likers        = set()
    linkurl       = "http://friendfeed.com/"
    linkcomments  = -1
    
    for entry in entries["entries"]:
        totalshares   += 1
        numcomments    = len(entry["comments"])
        totalcomments += numcomments
        if (numcomments > linkcomments):
            linkurl = "http://friendfeed.com/e/" + entry["id"]
            linkcomments = numcomments
        for like in entry["likes"]:
            liker = like["user"]
            likers.add(liker["name"])

    totallikes = len(likers)

The friendfeed API returns entries in JSON format, which is parsed by their API and returned as nested Python lists. To count the number of likes and comments, one needs to iterate over each entry.

likers is a Python set, a datatype I learned about while working on this project. A set is a group of objects which will contain no duplicates. If you add an item to the set which is already present the set will contain only one instance of the item, not two. This is used to avoid overcounting likes: if the URL we are looking for was shared multiple times in friendfeed and the same user marked every one of them as liked, we only want to count that as one like not many.

The linkurl is a compromise. I'd really like to direct the link to a page containing all of the results for this URL. Unfortunately only the friendfeed JSON API includes URL search functionality, the web search page does not. So far as I can tell there is no way to link back to friendfeed for more than one entry ID. So here we link to the entry with the most comments.

    self.response.out.write("<FeedFlare>\n")
    if (totalshares == 0):
        self.response.out.write("  <Text>On Friendfeed: 0 shares</Text>\n")
    else:
        self.response.out.write("  <Text>On Friendfeed: " +                      \
                                self.fmtTotal(totalshares,   "Share")   + ", " + \
                                self.fmtTotal(totallikes,    "Like")    + ", " + \
                                self.fmtTotal(totalcomments, "Comment") +        \
                                "</Text>\n");
    self.response.out.write("  <Link href=\"" + linkurl + "\"/>\n");
    self.response.out.write("</FeedFlare>")
    return

Generate the XML output. self.fmtTotal() is another little helper routine to pluralize the output correctly, "1 Comment" versus "2 Comments" The result of all this processing is a simple bit of XML:

<FeedFlare>
  <Text>On Friendfeed: 5 Shares, 1 Like, 2 Comments</Text>
  <Link href="http://friendfeed.com/e/1b0141a1-f6fa-1be2-e775-e5d36959e04c"/>
</FeedFlare>

This is all feedburner needs to create the FeedFlare. All formatting, including the font size and the blue text coloring, is hard-coded by feedburner. The FeedFlare does not get to supply any formatting, just some text and an optional link.

  def fmtTotal(self, count, descr):
    suffix = "" if (count == 1) else "s"
    return str(count) + " " + descr + suffix

  def parseArg(self, args, argname):
    try:
        ret = args[argname][0]
    except:
        ret = None
    return ret

The aforementioned helper routines.

Thats it, or rather thats the interesting part. The complete source can be downloaded.

The next question is, what is missing? What does it not do, that perhaps it should?

There is no caching of the result. Every request for the FeedFlare results in another API request to friendfeed.com. I believe this is acceptable because FeedBurner limits the rate of FeedFlare requests to about one per two hours.
The link in the generated FeedFlare points to the friendfeed entry with the most comments. This is a compromise. I'd rather to link to a search results page with all of the entries regarding the given URL, but can not find a good way to do it. I'd have to make the FeedFlare dynamically construct a page populated with all of the links, showing all of the likes and comments... and that is too much work for this little project. I hope that someday, friendfeed.com will provide a way to supply multiple entry IDs to appear on a single page.

Using the FeedFlare

If you are interested in using this FeedFlare on your own blog, please feel free. You have a few options:

To use it without a specific nickname (so the results will include Everyone on friendfeed whether they follow you or not) you can use this link as the Flare Unit URL in the Feedburner -> Optimize -> FeedFlares page for your feed.
To configure it to only include people who subscribe to you on friendfeed, download http://feedflare.geekhold.com/feedflareunit/friendfeeduser.xml">friendfeeduser.xml. Replace MY_NICKNAME with your friendfeed account name, and MY_API_KEY with your Remote API Key, and put the modified file somewhere on your own site to be used to configure FeedBurner.
The functionality to restrict the results to your subscribers is not working right now. Please stay tuned. I'll post an update on friendfeed.com if I get it working again.
If you don't like something about the way this code works, you're free to modify it. You can download the source code, set up your own Google App Engine application, and modify it as desired.

The Target Market is Not Obvious

2009-04-01T05:01:00.000-07:00

Exhibit A: a bottle warmer by munchkin, a company focussed mainly on baby products. You pour water into the base, put the bottle in the holder, and press the button. A heating element boils the water to steam, which warms the bottle.

Exhibit B: a piezoelectric buzzer. When the bottle is done heating, the lighted button on the front changes from red to green and the product emits a series of four shrill beeps to announce its successful completion. It is obviously very proud of itself.

The issue, and point of today's rant? When using the bottle warmer you are likely holding a squirming, ravenously hungry baby who really isn't interested in the details of the food preparation equipment. You don't need an audible alarm, as you'll be staring desperately at the warmer ready to snatch the bottle out the instant it has made it from "cold" to "tepid." So at best, the buzzer is annoying. With twins this feature is actively harmful: you really, really don't want to wake the second baby until the first is done eating. Trust me on this one.

Exhibit C: the empty space on the PCB where the buzzer used to be.

I have to say, I found their user interface to disable the buzzer feature somewhat difficult: a Torx screwdriver and soldering iron.

Who was this thing designed for anyway, and why did they feel a buzzer was necessary? One can only speculate about the product requirements document and user story which led to this feature...

This is Evilyn, a new parent.

When the baby is hungry she puts a bottle in the warmer, turns on the vacuum cleaner to drown out the crying, and goes to watch a little TV. When the bottle is heated there needs to be an indication noticeable despite both the vacuum cleaner and Oprah.

I'm kidding of course, I don't believe there was ever any such product plan. I think the problem is somewhat more subtle: the bottle warmer wasn't really designed for the parent at all — and no, it wasn't designed for the baby either.

Winning the Business

The munchkin corporation might well design some of its products, but as with any large company they would face the "build versus buy" decision for each niche product filling out their lineup. Their main concern is marketing and brand management. So the bottle warmer was quite possibly designed and manufactured by another company, and that other company does not sell directly to parents. Though the product obviously needs to perform its function, their customer is not the end user of the bottle warmer. Their customer is the buyer at the munchkin corporation. They might be designing it under contract or, quite possibly, designing it speculatively and hoping it will be picked up by one or more baby product companies. They have to make a good pitch, or be the most impressive offering at the trade show, to get the buyer to pick them instead of some other supplier.

In that sort of competition, a longer feature list can be the key to winning the business. The munchkin bottle warmer has several extra features: it can sterilize pacifiers and bottle nipples using steam, it has a lighted button which changes from red to green during operation, and it has the aforementioned infernal buzzer.

So there you have it. When you are vaguely dissatisfied with something you bought, if it just doesn't seem to have been completely thought through, this might be the reason. The designer's target was not you. It was targeted to catch the attention of the buyer for another company. This is also a primary reason why Apple has been so successful in consumer electronics: though they might buy components and software from outside, they never pick up a complete product to slap their logo onto. They retain control of the product design.

Exploring Google App Engine

2009-03-19T05:21:00.000-07:00

I registered my domain in 1996, when Network Solutions was the only registrar and their domain registration forms were faxed in. Back then email and web service providers were rather expensive for a small private domain, so I set up the appropriate services on an OpenBSD system at my house. We had a cable modem from @Home, with a static IP address because DHCP was new and unproven and PPPoE did not exist. We bought DNS service from Illuminati Online, and pointed it at the @Home static IP address.

In 2009 running servers on a system in ones home is far less the entertaining pursuit than it was in 1996. Botnets launch constant automated sweeps looking for vulnerable machines, and the deluge of spam is ever-increasing. So I started looking for alternatives, and fortunately the intervening years have radically changed the ISP market. Lots of hosting providers are available for a small fee. However the trickle of traffic to our current web site comes entirely from family, friends, and botnets, and I'd prefer to avoid paying for such a small installation. Google Sites is free of charge, but does not allow subdirectories. We have a modest collection of pages built up over a decade, I'm not interested in redoing all of the links to flatten the hierarchy.

There is another free option now: Google App Engine. Intended to run Python applications, it does handle static files and allows subdirectories in its file hierarchy. I started with the most straightforward approach for serving entirely static files, relying on Charles Engelke's writeup. You register for Google App Engine, put your HTML files in a subdirectory (which I've named named "static"), and create an app.yaml like so:

application: my-static-webpages
version: 1
runtime: python
api_version: 1

- url: (.*)/
  static_files: static\1/index.html
  upload: static/index.html

- url: /.*
  static_dir: static

This works, albeit with drawbacks, the most serious being the handling of inexact links. There are external links to our pages which lack the trailing slash, pointing to "http://www.example.com/foo" where foo is a directory. The existing Apache server would kindly send a redirect to "http://www.example.com/foo/" but the App Engine static handler returns a 404 error. I want to be forgiving, and not break existing links. Charles Engelke wrote a followup article describing how to perform basic HTTP redirects, so I decided to tackle something similar. Rather than use the static handler, we'll use Python. We configure app.yaml to run the Python handler:

application: my-static-webpages
version: 1
runtime: python
api_version: 1

handlers:
- url: /.*
  script: forgivedirectories.py

Though I bought my first Python book many years ago, I've done relatively little work in the language. This was quite a learning experience.

forgivedirectories.py: from google.appengine.ext import webapp from google.appengine.ext.webapp.util import run_wsgi_app import os class ForgiveDirectories(webapp.RequestHandler): def get(self): fullPath = 'static/' + self.request.path if not os.path.exists(fullPath): self.redirect('/404.html') return	If it really is a bad link, we send them to an error page.
if os.path.isdir(fullPath): if fullPath[-1] != '/': self.redirect(self.request.path + '/') return else: fullPath += '/index.html'	This is the "forgive" part of forgivedirectories.py. If the requested path is a directory but does not end in a slash, send them a redirect to the proper path. Note that its important to send a redirect, and not just send the index.html page. Relative links like "../bar/index.html" will only work if the browser's path ends in a slash.
# if Google App Engine adds a # sendfile equivalent, we should # use it here. fh = open(fullPath, 'r') while 1: block = fh.read(16384) if not block: break self.response.out.write(block) fh.close	If we make it here, we have a page to send. To limit the memory footprint we loop over every 16 KBytes; slurping the entire file into memory is neither necessary nor beneficial.
application = webapp.WSGIApplication( [('.*', ForgiveDirectories)], debug=True) def main(): run_wsgi_app(application) if __name__ == "__main__": main()	Boilerplate code to initialize the web services gateway and call into our function. Its possible to match regular expressions to dispatch to multiple different classes, but here we match everything and send it to ForgiveDirectories.

This works, sortof. You can see the web pages now. One problem is that the Content-Type is not being set, so browsers have to assume a default. Amusingly enough most browsers default to text/html, so at least the pages render even if images are broken. Google Chrome defaults to text/plain, so it shows the HTML source of the pages. So we obviously need to set the Content-Type, which we will do by examining the file's extension. Being new to Python, it took a few tries to get something reasonable.

def contentTypeFromExt(self, extension): if extension=='.html': return 'text/html' elif extension=='.jpg': return 'image/jpeg' elif extension=='.gif': return 'image/gif' elif extension=='.png': return 'image/png' elif extension=='.js': return 'application/x-javascript' elif extension=='.css': return 'text/css' else: return 'text/plain'	The first attempt. Its basically C code, translated into Python.
def contentTypeFromExt(self, ext): contenttype = { ext == '.html': 'text/html', ext == '.jpg' : 'image/jpeg', ext == '.gif' : 'image/gif', ext == '.png' : 'image/png', ext == '.js' : 'application/x-javascript', ext == '.css' : 'text/css'}[1] return contenttype	The second attempt. Python does not have a switch statement, but some Google searching showed how to construct something that looks like one if you squint at it just right. Unfortunately this version doesn't supply 'text/plain' as a default, and its just... weird. Trying to torture the code to vaguely resemble a switch statement is not very pleasing.
contentExtensions = { '.html' : 'text/html', '.jpg' : 'image/jpeg', '.gif' : 'image/gif', '.png' : 'image/png', '.js' : 'application/x-javascript', '.css' : 'text/css'} def contentTypeFromExt(self, ext): try: return self.contentExtensions[ext] except KeyError: return 'text/plain'	The third attempt, and the first real effort to do it in a Pythonic way. Python has hash tables as a fundamental type in the language, so let's use them! If the key is not found in the dictionary an exception will be thrown... so I guess we're supposed to catch it? I dunno. Obviously, not finding the key in the dictionary is expected to be an unusual occurrence. There must be a better way to do it.
contentExtensions = { '.html' : 'text/html', '.jpg' : 'image/jpeg', '.gif' : 'image/gif', '.png' : 'image/png', '.js' : 'application/x-javascript', '.css' : 'text/css'} def contentTypeFromExt(self, ext): return self.contentExtensions.get(ext, \ 'text/plain')	The current version, which I'm pretty happy with. By calling the get method directly we can supply a default value to be returned, instead of having it throw an exception.

Now we need to actually set the Content-Type header. I'm using os.path.splitext() to pull out the file extension, which is probably wrong: on Windows I think that method expects backslashes, where a URL will always be forward slashes. It is fine when used with the App Engine (which is not hosted on Windows), so I'll rely on it until I can figure out a more appropriate method to use.

  def contentTypeFromPath(self, path):
    (basename, extension) = os.path.splitext(path)
    return self.contentTypeFromExt(extension)
  
  # The following goes in the get() method
  # immediately before we open the fullPath file:
  self.response.headers['Content-Type'] = self.contentTypeFromPath(fullPath);

Left To Be Implemented...

The App Engine is a lot of fun. Its a way to experiment with web services without expense for hosting. The forgivedirectories.py script is now in service,handling our web site. There are a few things left to do, which I hope to cover in future updates:

After reorganizing the web site some time ago, the old Apache server was configured to send 302 redirects for the old hierarchy. The new AppEngine handler should too, just in case there are any links remaining to the old URLs.
For efficiency we should allow the browser to cache the pages, by implementing Last-Modified-Since support. The ipsojobs blog has a writeup about this which I intend to leverage

When the Universe Conspires to Prevent Backups

2009-03-09T05:54:00.000-07:00

You know you're having a bad day when your backup software requires 83 Terabytes of free space in order to proceed.

As it turns out, the filesystem on this disk needed repair. Disk Utility found an 82.95 terabyte file which appeared to be incorrect.

Inadvisable Externing

2009-02-26T06:01:00.000-08:00

The Principle of the Conservation of Software Quality postulates that for every best practice there is an equal and opposite worst practice which will be easier to implement. We're here today to talk about one of those balancing factors: declaration of externs within the C code.

Assume for a moment that foo() is defined somewhere within the codebase and, for reasons unclear, there is no header file declaring foo(). Perhaps foo() was not deemed important enough, or had been static when originally written and only later opened up to the rest of the module. However we got here if one has adopted the best practice of using -Wall -Werror when compiling, then calling foo() will require a declaration or result in a compilation error. One is then faced with several choices:

Add foo() to an existing header file
Make a new header file for foo() and any similar routines
Declare foo() as an extern in the C file where it will be called.

Perhaps the Gentle Reader is unfamiliar with that last option. If so, I salute you: your unfamiliarity with it speaks well of you. To summarize: "extern" means the function is not provided within this compilation unit and will be supplied later when linking. It is normally used in header files, but is also valid within C code:

do {
    extern int foo(int a, int b);
    c = foo(a, b);
} while (c != 1);

The benefit of a function declaration in a header file is that it can be included in multiple places, in the file which implements the function and any file which wants to use the function. If the implementation of the function changes such that it no longer matches the declaration, an error will result. If the header changes such that the callers no longer match, an error will also result. Declaring an extern within a C file accomplishes none of these things, because the compiler does not get to see both the declaration and the implementation of foo at the same time.

Lets examine what will happen if a third argument is added to foo() but the caller blissfully relies on an existing extern declaration with two arguments. We'll use one of my favorite techniques, disassembling a MIPS binary to see how it works. We'll use a ridiculously simple example for clarity:

int foo(int a, int b, int c)
{
    return (a + b + c);
}

<foo>:
addu v0,a0,a1	tmp = a + b
addu v0,v0,a2	tmp = tmp + c
jr ra	return to caller

foo() expects arguments in registers a0, a1, and a2, and sums them together. Now lets look at the code generated by an extern declaration with only two arguments:

extern int foo(int a, int b); /* Worst Practice */
int main()
{
    return foo(1, 2);
}

<main>:
li a0,1	load 1 into the first arg register
li a1,2	load 2 into the second arg register
lw t9,0(gp)	load address of foo()
jalr t9	jump to foo()

Not surprisingly, only registers a0 and a1 are loaded with values. The important point to note is that register a2 is not touched at all. One might have intuitively assumed that the third argument would be zero, but this is not the case. The third argument will be whatever garbage happens to be in register a2.

The third argument could be most anything, and might vary depending on the call chain or the data being processed. We end up with a sporadic and difficult to diagnose bug, hidden in a way that the compiler cannot help, and all because we didn't want to bother with a header file. This happened at a previous employer of mine, where a particular process would reliably crash at just one customer site because their particular environment ended up with a non-NULL value in the argument register. It was, of course, a crucial customer.

The moral of this article is that header files are your friend.

In Other News

Our family became larger in January, and the resulting lack of free time means postings will be less frequent. Previously I'd aimed for two postings per month, but now I think I'll be lucky to manage just one. I wrote several articles in advance, thinking that would be sufficient, but alas it was not enough. The Gentle Reader might have noticed one of those prepared postings appear twice. I accidentally marked the Blogroll article for 1/2008, and blogger.com happily sent it out immediately with a publication date one year prior. It also went out with the corrected date. I seem unable to expunge the mistaken early posting, that article still shows up twice in Google Reader. Oh well.

Variable Scoping with gcc

2009-01-07T06:01:00.000-08:00

Has this ever happened to you? You allocate some sort of resource which needs to be released before returning from the function. You can put the release at the end of the routine for the normal case, but there are a number of error checks which can cause it to return early. You consider calling the reclaim routine inside each error handler, but you're concerned that someone maintaining the code in the future will forget to do so. Instead you put all of the cleanup code at the end of the function, and have each error check use a goto.

Then of course someone argues very strenuously that goto is evil incarnate and must never be used, one thing leads to another, and then you have to find somewhere to hide the body ... wait, nevermind that last bit.

Consider this instead:

int foo()
{
    int fd LOCAL_SCOPE_FD = open("/path/to/file");

    if (error1()) {
        return -1;
    }

    return 0;
}

Though it might appear that I'm suggesting the file descriptor be leaked in order to simplify the code, that is not the case. The magic happens in LOCAL_SCOPE_FD:

#define LOCAL_SCOPE_FD __attribute__((cleanup(local_fd_close)))

void local_fd_close(int *fd)
{
    if (*fd >= 0) close(*fd);
}

__attribute__(cleanup) is a gcc extension. When an automatic variable goes out of scope, the function indicated by the cleanup attribute will be called. If the scope is exited unusually, such as via longjmp() or by calling exit(), the cleanup function does not get called, but normal return statements or falling off the end of the block do work.

It also works within inner blocks. For example:

int foo()
{
    if (do_something) {
        int fd LOCAL_SCOPE_FD = open("/path/to/file");
    }
    /* local_fd_close will be called here. */

    ... more code ...
}

Cleanup can only be applied to automatic variables, i.e. variables on the stack declared within a function. It cannot be used with global or static variables. The cleanup attribute can be used with any variable type, not just integers. The cleanup function receives a pointer to the automatic variable being cleaned up.

I assume that if the Gentle Reader is reading this article, there are good reasons to use C in your problem space. Needless to say, if you want automatic resource reclamation a language other than C would provide more capabilities. Garbage collection and object finalizers are powerful constructs, given a problem space where they are appropriate.

Acknowledgements

Many thanks to Matt Peters for pointing out the __attribute__(cleanup) capability to me.

Ian Lance Taylor recently wrote on a similar topic, about support for destructors and exceptions in C.

Updates

This article was picked up on reddit, with a few comments. One pertinent comment from erikd:

His local-fd-close() function has a bug, it needs to check the return value of close(), because close can return an error of EINTR which means the prcoess received an interrupt and should retry the close operation.

printf-acular

2008-12-19T08:42:00.000-08:00

Ahh, printf. What would we do without printf, sprintf, etc? It makes it easy to format integers, floats, strings, MAC addresses... Oh wait, there isn't a format specifier for MAC addresses is there? Well, lets rectify this obvious omission.

glibc (and uClibc) implement a facility to add new format codes to the printf family of functions. It is even possible to override the builtin implementations of the C standard formats, if the Gentle Reader has an irrational hatred for some aspect of the output. The GNU documentation for how to do this is adequate, but a bit obscure. So lets dive into an example by adding a %M specifier to handle MAC addresses:

uint8_t mac[6] = { 0x00, 0x11, 0x22, 0x33, 0x44, 0x55 };

if (register_printf_function ('M',
        printf_output_M, printf_arginfo_M)) {
    ... error handling ...
}

printf("%M\n", mac);

Output:
00:11:22:33:44:55

Huzzah! Now we'll dig into the implementation.

printf_arginfo_M

The first routine to be implemented tells glibc the arguments required by the new specifier:

#include <stdio.h>
#include <printf.h>

static int
printf_arginfo_M(const struct printf_info *info,
                 size_t      n,
                 int        *argtypes)
{
    /* "%M" always takes one argument, a pointer to uint8_t[6]. */
    if (n > 0) {
        argtypes[0] = PA_POINTER;
    }

    return 1;
} /* printf_arginfo_M */

The fields of the printf_info structure are described in the GNU manual. For the arginfo() implementation the only important field is spec, the character code of the specifier for which the information is sought. This allows a single arginfo() routine to implement support for multiple new specifiers.

glibc also passes in an array of argtypes[] with n members, which are to be filled in with the types of the arguments expected. The available types are documented in the GNU manual. The arginfo() routine must populate the argtypes[] with the expected arguments, after checking to ensure there is room. It should return the number of arguments it expects. If you define a format specifier which takes a large number of arguments, there might not be sufficient room in argtypes[] to store them all. If the arginfo() routine returns a larger value than n, glibc will call it again with a larger argtypes[] array.

For %M there is only one argument, the MAC address to be formatted. The ability to write a format specifier with more than one option is potentially useful, but also confusing as none of the standard format options do so.

printf_output_M

Next we need to implement the output routine, to generate the formatted output for the new specifier. Output always goes to a FILE *, no matter whether called from printf(), sprintf(), vfprintf(), etc.

One is free to use the stdio.h routines like fprintf(), so long as you do not use your new specifier in the format string. If you do, fprintf will call back into your output routine, which will call fprintf() again, which will call your output routine again... and hijinks ensue.

static int
printf_output_M(FILE *stream,
                const struct printf_info *info,
                const void *const *args)
{
    const unsigned char *mac;
    int len;

    mac = *(unsigned char **)(args[0]);

    len = fprintf(stream, "%02x:%02x:%02x:%02x:%02x:%02x",
                  mac[0], mac[1], mac[2], mac[3], mac[4], mac[5]);

    return len;
} /* printf_output_M */

We only take one argument for %M, so we only look at args[0]. There is no need to check for NULL: glibc validates the format before calling your output routine, you'll never get a NULL pointer. We call fprintf() to do most of the work, and return the number of bytes output.

printf("%30M\n", mac);

00:11:22:33:44:55

Voila! I hope you've enjoyed this article... oh wait, that wasn't very good was it? The "30" prepended to the M specifier was meant to right-justify the output within a 30 character region. The output did not reflect this. Oops.

printf_output_M, with modifiers

glibc parses out the modifiers prepended to the specifier, and passes them to the output routine via the printf_info structure. Many of the standard modifiers don't make sense for MAC addresses. For example, I have no idea what "%llM" would mean. A few modifiers do make sense, such as a field width and the '-' argument to left-justify.

We certainly could write a bunch of code to insert the proper number of spaces before or after the MAC address, but we'll use a slightly different approach. We call fprintf() to generate the output anyway, so we'll generate a format string for fprintf() to make it handle the width and justification.

static int
printf_output_M(FILE *stream,
                const struct printf_info *info,
                const void *const *args)
{
    const unsigned char *mac;
    char macstr[18]; /* 6 hex bytes, with colon seperators and trailing NUL */
    char fmtstr[32];
    int len;

    mac = *(unsigned char **)(args[0]);
    snprintf(macstr, sizeof(macstr), "%02x:%02x:%02x:%02x:%02x:%02x",
            mac[0], mac[1], mac[2], mac[3], mac[4], mac[5]);

    /* We handle some conversion specifier options as appropriate:
     * '-' and field width */
    if (info->width > 0) {
        snprintf(fmtstr, sizeof(fmtstr), "%%%s%ds",
                (info->left ? "-" : ""), info->width);
    } else {
        snprintf(fmtstr, sizeof(fmtstr), "%%s");
    }

    len = fprintf(stream, fmtstr, macstr);

    return len;
} /* printf_output_M */

We generate the formatted MAC address as a string buffer on the stack. The bolded code examines the modifiers in printf_info, and generates a format string in fmtstr[]. For example if the arguments to printf were ""%-30M", the fmtstr[] will be "%-30s"

Now the output is much more pleasing:

printf("%30M\n", mac);

               00:11:22:33:44:55

printf_output_M, Now with More Cisco

Which looks more natural to the Gentle Reader?

00:11:22:33:44:55

0011.2233.4455

If you chose the first one, you likely come from a desktop background with Operating systems such as Windows, MacOS, Linux, Solaris, or the various other Unixes which all use a colon-seperated MAC address.

If you chose the second one, you likely come from a Cisco networking background. Cisco uses a MAC address format which takes up three fewer columns on the screen, important if one's user interface is a text CLI.

Could we accommodate this variation? Certainly it could be done using another conversion specifier, perhaps using "%C" for a Cisco-style MAC address, but this seems inelegant. Coming to our rescue is a little used format modifier in printf: the 'alternate representation' hash mark. This modifier implements optional formatting, for example when used with the hex specifier as "%#x" it will prepend 0x to the output.

So we'll implement the Cisco MAC address format using "%#M" in printf_output_M, like so:

    if (info->alt) {
        /* Cisco style formatting */
        snprintf(macstr, sizeof(macstr), "%02x%02x.%02x%02x.%02x%02x",
                mac[0], mac[1], mac[2], mac[3], mac[4], mac[5]);
    } else {
        /* Unix/Linux/Windows/MacOS style formatting */
        snprintf(macstr, sizeof(macstr), "%02x:%02x:%02x:%02x:%02x:%02x",
                mac[0], mac[1], mac[2], mac[3], mac[4], mac[5]);
    }

If invoked with "%#M" we'll take the first code path and produce a Cisco-style MAC address. Otherwise, we generate a colon separated MAC address.

Whither -Wall?

With the -Wformat (or -Wall) argument, gcc will sanity check the arguments passed to the printf family of routines. It can ensure that the number of arguments matches the number of specifiers in the format string, for example. Unfortunately, it does not know about custom additions:

gcc -Wall testM.c
testM.c:57: warning: unknown conversion type character 'M' in format
testM.c:57: warning: too many arguments for format

I know of no way to teach gcc about the new specifiers, unfortunately. If the Gentle Reader knows of a way, please describe it in the comments.

GPL

I am not a lawyer, I do not play one on TV, and I do not want to play one on TV. So my opinions about GPL issues are really just quaint little notions of How The World Should Work.

An argument has been advanced in other contexts that if the only implementations of a particular API are licensed under the GPL, then any caller of that API should be considered a derivative work and be subjected to the GPL. As the register_printf_function() API only exists in glibc and uClibc, both of which are licensed under the LGPL, it could be argued that code calling register_printf_function() is therefore encumbered by the LGPL. Opinions may differ, but this is one possible interpretation.

Personally, I choose to treat custom printf formatters as LGPLd code.

Closing Thoughts

It is of course possible to implement routines to format a MAC address as a string, using "%s" in stdio.h routines for output. However I think it is more elegant to teach stdio.h how to deal with common output requirements for your application.

The C standard may claim additional lower case specifiers for standard formats in the future. It is best to rely on upper-case codes for custom formats.

The Six Million Dollar LibC

2008-11-28T12:40:00.000-08:00

Today, Gentle Reader, we will examine the Bionic library, a slim libc developed by Google for use in the Android mobile software platform. Bionic is clearly tailored for supporting the Android system, but it is interesting to see what might be done with it in other embedded system contexts.

Google's stated goals for Bionic include:

BSD license: Android uses a Linux kernel, but they wanted to keep the GPL and LGPL out of user space.
Small size: glibc is very large, and though uClibC is considerably smaller it is encumbered by the LGPL.
Speed: designed for CPUs at relatively low clock frequencies, Bionic needs to be fast. In practice this seems to drive the decisions of what to leave out, rather than any special Google pixie dust to make code go fast.

In this article we'll delve into the Bionic libc via source inspection, retrieved from the git repository in October 2008. The library is written to support ARM CPUs, though some x86 support is also present. There is no support for other CPU architectures, which makes it a bit inconvenient as all of my current systems are PowerPC or MIPS. Nonetheless I'll concede that for the mobile phone market which Bionic targets, ARM is the only architecture which matters.

As one might expect for a BSD-licensed libc, a significant amount of code is sourced from OpenBSD, NetBSD, and FreeBSD. Additional BSD-licensed bits come from Sun and public domain code like the time zone package. There is also a significant amount of new code written by Google, particularly in the pthread implementation.

C++ support

So what is different about the Bionic libc versus glibc? The most striking differences are in the C++ support, as detailed in the CAVEATS file:

The Bionic libc routines do not handle C++ exceptions. They neither throw exceptions themselves, nor will they pass exceptions from a called function back through to their caller. So for example, if the cmp() routine passed to qsort() throws an exception the caller of qsort() will not see it.

Support for C++ exceptions adds significant overhead to function calls, even just to pass thrown exceptions back to the caller. As Android's primary programming language is Java, which handles exceptions entirely within the runtime package, the designers chose to omit the lower level exception support. C++ code can still use exceptions internally, so long as they do not cross a libc routine. In practice, it would be difficult to actually guarantee that exceptions never try to transit a library routine.

There is no C++ Standard Template Library included. Developers are free supply their own, such as the free SGI implementation.

Lack of exceptions is obviously a big deal for C++ programmers, but nonetheless we'll push on.

libpthread

The pthread implementation appears to be completely new and developed by Google specifically for Android. It is, quite deliberately, not a complete implementation of POSIX pthreads. It implements those features necessary to support threads in the Dalvik JVM, and only selectively thereafter.

In other embedded Linux environments, the pthread library is crucial. There are a large number of developers in this space from a vxWorks background, to whom threads are simply the way software should be written. So we'll spend a bit more time delving into libpthread.

Mutexes, rwlocks, condvars, etc are all implemented using kernel futexes, which makes the user space implementation impressively simple. It seems a little too simple actually, I intend to spend a bit more time studying the implementation and Ulrich Drepper's futex whitepaper.

There is no pthread_cancel(). Threads can exit, but can not be killed by another thread.

There is no pthread_atfork(). This routine is useful if you're going to fork from a threaded process, allowing cleanups of resources which should not be held in the child. I've mostly seen pthread_atfork() used to deal with mutex locking issues, and need to study how the use of futexes affects fork().

Thread local storage is implemented, with up to 64 keys handled. Android reserves several of these for its own use: the per-thread id and errno, as well as two variables related to OpenGL whose function I do not understand. Interestingly the ARM implementation places the TLS map at the magic address 0xffff0ff0 in all processes. This technique is presumably part of the Google performance enhancing pixie dust.

POSIX realtime thread extensions like pthread_attr_{set,get}inheritsched and pthread_attr_{set,get}scope are not implemented. Frankly I've never worked on a system which did implement these APIs and am completely unfamiliar with them, so I don't find their omission surprising.

I haven't drawn a final conclusion of the Bionic pthread implementation yet. It is pleasingly simple, but lack of pthread_atfork() is troublesome and use of a magic address for the TLS map may make porting to other architectures more difficult. I need to get this puppy running on a PowerPC system and see how well it works.

Miscellaneous notes

In the course of digging through the library I generated a number of other notes, which don't really clump into categories. So I'm simply going to dump it all upon the Gentle Reader, in hopes that some of it is useful.

The README says there is no libm, though the source for libm is present with a large number of math routines. I need to investigate further whether it really works, or whether the README is out of date.

There is no wchar_t and no LOCALE support. I think this is fine: wchar_t is an idea whose time has come... and gone. The world has moved on to Unicode with its various fixed and variable width encodings, which the wide character type is not particularly useful for.
I've used ICU in recent projects for internationalization support, and this is also what Google suggests in the README for Bionic.

There is a shared memory region of configuration properties. For example, DNS settings are stored in shared memory and not /etc/resolv.conf. The Android API also makes this shared memory configuration store available to applications via property_get() and property_set().

As one might expect, the stdio/stdlib/string/unistd implementation comes from OpenBSD, NetBSD, and FreeBSD with minimal changes. The only change I noticed was to remove the LOCALE support from strtod() (i.e., is the decimal point a period or a comma? In the Bionic library it is always a period).

There is no openlog() or syslog() implementation. There is a __libc_android_log_print() routine, to support Android's own logging mechanism.

Bionic uses Doug Lea's malloc, dlmalloc. Bionic also provides a hash table to track allocations looking for leaks, in malloc_leak.c.

There is no pty support that I can find, and no openpty(). There are reports of people starting an SSH daemon on a jailbroken Android device, so presumably there is some pseudo-terminal implementation which I've missed.

There are no asynchronous AIO routines like aio_read() or aio_write().

Bionic contains an MD5 and SHA1 implementation, but no crypt(). Android uses OpenSSL for any cryptographic needs.

Android dispenses with most file-based Unix administration. Bionic does not implement getfsent, because there is no /etc/fstab. Somewhat incongruously there is a /var/run/utmp, and so getutent() is implemented.

Android implements its own account management, and does not use /etc/passwd. There is no getpwent(), and getpwnam()/getpwuid() are implemented as wrappers around an Android ID service. At present, the Android ID service consists of 25 hard-coded accounts in <android_filesystem_config.h>

Bionic isn't finished. getprotobyname(), for example, will simply print "FIX ME! implement getprotobyname() __FILE__:__LINE__"

There is no termios support (good riddance).

Conclusion

Bionic is certainly interesting, and pleasingly small. It also represents a philosophical outlook of keeping the GPL some distance away from the application code.

Bionic is a BSD-based libc with support for Linux system calls and interfaces. If the lack of C++ exceptions or other limitations prove untenable, the syscall and pthread mutex implementation could be repurposed into the heavier FreeBSD/NetBSD/OpenBSD libc, though handling thread cancellation using the Bionic mutexes could require additional work.

Postscript

If you don't understand the reference in the title of this article, don't fret: you have simply not watched enough bad 1970's American television.

Update: In the comments, Ahmed Darwish points out another Android-related article discussing the kernel and power management interfaces Google added.

Update2: Embedded Alley is working on a MIPS port of the Android software.

Update3: In the comments Shuhrat Dehkanov points out an interview with David Turner, who works at Google on the Bionic implementation. Shuhrat also notes that you might have to log in to Google Groups to see the attachment. "Here is an overview by David Turner (though non-official) which answers some of the questions/unclear parts in your article."

Ode to Enum

2008-10-31T06:50:00.000-07:00

Let's just get this out in the open: I love enum. Enum is a friend of mine. Enum and I go way, way back.

I also detest enum's evil twin, the series of #defines.

typedef enum { OP_FOO, OP_BAR, } operation_t;	#define OP_FOO 0 #define OP_BAR 1
GOOD	BAD

Why this irrational hatred for poor #define? After all, it has had a rough life. It isn't even a real part of the C language, being completely a pre-processor construct. Allow me to explain how #define has wronged me, not just once but on multiple occasions.

When one has a series of #defines and one needs to add a new code point, the natural inclination is to grab the next unused value:	Meanwhile on a different branch in the version control system, a colleague needs to add a new code point:
#define OP_FOO 0 #define OP_BAR 1 #define OP_BUCKAROO 2	#define OP_FOO 0 #define OP_BAR 1 #define OP_BANZAI 2

If you are lucky, this will be flagged as a merge conflict and someone will notice the duplicate values. If you are not lucky, the entries will have been added in slightly different locations such that there is no conflict... or perhaps the poor schmuck tasked to resolve the conflicts only cares about making the darn thing superficially compile so they can get back to their real work of pounding out new operation types.

#define OP_FOO       0
#define OP_BAR       1
#define OP_BUCKAROO  2
#define OP_BANZAI    2

... and much mayhem ensues.

Had we used enum instead, the bad outcome is prevented. The enumeration will assign unique values:

typedef enum {
    OP_FOO,
    OP_BAR,
    OP_BUCKAROO,
    OP_BANZAI,
} operation_t;

From this, Gentle Reader, we can conclude that version control systems must love enums.

gcc loves enums

gcc -Wswitch-enum provides a very nice benefit for enums and switch statements. The compiler will require that all enumerated values be handled in the switch, and will complain if they are not. Consider this code:

int test(operation_t op)
{
    switch(op) {
        case OP_FOO:
        case OP_BAR:
            return -2;
            break;
        default:
            return -3;
            break;
    }
 } /* test */

When new enumeration values are introduced, the compiler will flag the places where handling needs to be added:

./m.c:137: warning: enumeration value 'OP_BUCKAROO' not handled in switch
./m.c:138: warning: enumeration value 'OP_BANZAI' not handled in switch

Older gcc releases provided a weaker version of this checking in the form of -Wswitch, where a "default" case is considered to handle all enumerated values. So the presence of a default case renders -Wswitch useless. If you want to take advantage of -Wswitch but also want to practice defensive programming, unexpected values need to be handled outside of the switch:

int test(operation_t op)
{
    switch(op) {
        case OP_FOO:
        case OP_BAR:
            return -2;
            break;
    }

    return -3;
 } /* test */

The -Wall argument to gcc enables -Wswitch. If you are using a recent gcc, explicitly adding -Wswitch-enum is a good idea.

gdb loves enums

Enums make debugging easier, with symbolic values:

(gdb) print mydefine
$1 = 3
(gdb) print myenum
$2 = OP_BANZAI

Isn't that better?

enums on a diet

There is one minor disadvantage of using an enum: by default, an enum is the size of an int. So on a 32 bit machine an enum takes up 4 bytes of memory, even with only a small set of enumerations. However this bloat is easily eliminated, at least when using gcc:

typedef enum {
    OP_FOO,
    OP_BAR,
    OP_BUCKAROO,
    OP_BANZAI,
} __attribute__((packed)) operation_t;

A packed enum consumes the minimum footprint; in this example it is a single byte. If there are more than 256 enumerations, or if enumerations are explicitly assigned to a large absolute value, the footprint will grow to 2 or 4 bytes.

Do you love enums?

Enums have been very, very good to me.

Updates

In the comments, Rob asked:

all very good - but can you do in c as you do in GDB i.e. can you show me a function myReverseEnumFuction() which when called:
printf("enum string=%s", myReverseEnumFunction(2) );
would output "OP_BUCKAROO" ???

Unfortunately no, I do not think there is a good way to do this in the general case. gdb is able to print the symbolic names for enumerations by referencing debug sections in the binary. It is certainly possible to use the same debug sections to construct myReverseEnumFunction(), but there are two drawbacks:

Production binaries are routinely stripped of debugging information, which would render myReverseEnumFunction() inoperable.
There are a number of different (and incompatible) formats for debugging sections. Even within the Unix-ish world using the ELF binary format there is STABS and several variations of DWARF. myReverseEnumFunction() would not be very portable.

The DWARF format is an interesting topic, and I've put it on my list of things to research and write about. In the meantime I would like to mention the C pre-processor's stringify capability ("#(argument)"), which may come in handy when manually constructing a myReverseEnumFunction() function. The MAP() macro below uses stringify to populate a structure with the enumeration name.

#define MAP(x)  {x, #x}

struct enum_mapping {
    bb_t code;
    char *name;
} enum_map[] = {
    MAP(OP_BUCKAROO),
    MAP(OP_BANZAI)
};

char *myReverseEnumFuction(bb_t bb)
{
    int i, max = sizeof(enum_map) / sizeof(enum_map[0]);

    for (i = 0; i < max; i++) {
        struct enum_mapping *emap = &enum_map[i];
        if (emap->code == bb) {
            return emap->name;
        }
    }
}

Aliasing By Any Other Name

2008-10-14T06:01:00.000-07:00

This time, Gentle Reader, we'll delve into one of the sticky areas of the C language: pointer aliases. Let's dive directly into code:

void
printval(uint32_t val32)
{
    printf("0x%08x\n", val32);
}

int
main()
{
    uint32_t val32 = 0;
    uint16_t *p16 = (uint16_t *)&val32;

    p16[1] = 0xa1fa;

    printval(val32);
}

We have a 32 bit integer on the stack, to which we also direct a pointer to a 16 bit integer. Writing to p[1] overwrites 16 bits of the word.

$ cc -O0 ./test.c
$ ./a.out
0x0000a1fa

I can hear the groans already: not another little-versus-big endianness discussion. No, thats not it! It is true that the result would be different on a little endian machine, but the far more interesting discussion concerns what happens when we compile -O2:

$ cc -O2 ./test.c
$ ./a.out
0x00000000

Why is the result different? The plot thickens...

As it is one of my favorite techniques, we'll look at the generated MIPS instructions to see why this happens.

00:	li v1,0xa1fa	load 0xa1fa into register v1
04:	move a0,zero	load 0 into a0 (the 1st function argument)
08:	sh v1,26(sp)	store 0xa1fa to the stack, where val32 is stored
0c:	lw t9,0(gp)	load address of printval
10:	jalr t9	jump to printval
14:	nop

The second instruction loads zero into register a0, which will be passed as the first argument to printval(). val32 at that moment is zero. We then store 0xa1fa to 16 bits on the stack, overwriting part of val32. The zero in the argument register is untouched, so we end up passing zero to printval() even though val32 on the stack has changed to 0x0000a1fa. Surely this is a bug in gcc's optimizer, right?

No it isn't a flaw in gcc, but understanding this behavior will take us back in the history of the C language.

Set Wayback Machine to 1974

C has a reputation as a language for high performance code. Yet the language is over 30 years old, during which time computer architecture has changed considerably. Instruction execution and memory access performance have both increased phenomenally, but execution speed has improved far more rapidly than memory. Accesses to memory have become almost two orders of magnitude more expensive relative to the CPU speed compared to 30 years ago, and a great deal of silicon is now spent on data caches to avoid the cost of going to memory.

One difficulty with optimizing C code is the free-wheeling use of pointers. Two pointers are called aliases if they point to the same memory location, and in general the compiler cannot really know whether any two arbitrary pointers might be aliases. To be completely safe, whenever a write is done to a pointer the compiler would have to forget any values fetched using other pointers. Those values would be re-fetched from memory, just in case they had been changed by the aliasing pointer.

Unfortunately keeping values in registers is a key factor in good performance. Even if the CPU data cache still holds all of the data, the additional instructions to reload values into registers can easily bloat an inner loop and measurably slow its performance. For a long time C compilers were required to handle aliasing of arbitrary pointers. To get good performance they would "cheat" in specific cases, retaining values in registers when it was pretty certain there was no aliasing. Sometimes the compiler would be wrong, and you'd end up with incorrect behavior for a specific (and probably convoluted) segment of code with obscure aliasing somewhere. The subtle, inconsistent behavior of compiled code was becoming a problem.

Set Wayback Machine to 1999

To try to resolve the ambiguous nature of this handling, the C99 specification clarifies how compilers are allowed to optimize with respect to pointer aliasing:

void * can alias anything
char * can alias anything
any other two distinct pointer types are assumed not to be aliases

Two pointers of the same type must be treated as if they were aliases, reloading the value from memory whenever the other changes. Two pointers of different types are assumed not to alias: operations on a pointer will not invalidate the values of other pointers. In the vast majority of cases this assumption is true, and it helps the C compiler to generate faster code.

The problematic statement in our example code is:

uint16_t *p16 = (uint16_t *)&val32;

"&val32" is a pointer to uint32_t. p16 is a pointer to uint16_t. Because they are different types, they are treated as non-aliasing. The fact that they obviously are aliases due to the way they are assigned is not relevant. The point of specifying the aliasing rules in C99 was to get away from the hodgepodge of unclear assumptions and heuristics, to follow just one consistent set of rules. The pointers are different types, therefore they are assumed not to alias.

Solutions

Leaving aside the contrived example which kicked off the article, how does one resolve this problem? One possible solution is the use of void or char pointers, which the compiler must treat as a potential alias of any other pointer. For complex casts of one structure to another, passing a void pointer around may be worth considering. Unfortunately pervasive use of void sacrifices most of the type checks the compiler offers, so you can have argument bugs creep in which would otherwise have been easily caught.

Another, simpler solution is to have the compiler handle aliasing more leniently. Specifying C89 mode, for example, requires the compiler to operate by the earlier language rules where any pointer could potentially alias another. Also, gcc supports a -fno-strict-aliasing flag which disables only the aggressive alias optimizations without impacting the rest of the C99 handling.

A solution which does not work is passing the pointer around, for example if we passed a pointer to val32 to printval() in the example code. In theory this would require the called routine to fetch the value from memory (side-stepping any aliasing issues), but in practice the compiler could inline printval() and use the same registered value as caused the controversy in the first place. Even worse, the problem could suddenly appear years after the code is written when the compiler is updated or compilation flags are changed resulting in different inlining behavior.

In most cases where you have an existing codebase with aliasing problems, -fno-strict-aliasing is the best way to go. Aliasing bugs can be incredibly difficult to find. There is a slight performance hit to -fno-strict-aliasing in the form of additional references to memory, but in most cases it will be small as the data cache will satisfy all requests.

Update: In the comments, Lance talks about compiler warnings:

Also worth noting, compiling this bit of code with "-O2 -Wall" causes some versions of gcc to complain "warning: dereferencing type-punned pointer will break strict-aliasing rules", which can be useful when attempting to track down this type of problem. Interestingly, "-O0 -Wall" does not produce this warning because gcc only does the analysis required to detect this situation when optimizations requiring alias analysis are enabled.

Random Musings on stackoverflow.com

2008-09-11T07:30:00.000-07:00

Stackoverflow.com is a site by programmers and for programmers, whose purpose is answering questions on topics relating to software development. At the time of this writing it has completed a closed beta test and is in a more extensive test phase, ramping up to open on September 15, 2008. Access to the beta site is open to anyone who wants it during the test period, see blog.stackoverflow.com for details.

Stackoverflow is the brainchild of Jeff Atwood and Joel Spolsky, long-time bloggers on software development topics. It is described by its creators as the intersection of a Wiki, blog, forum, and digg/reddit voting site. Users post questions and answers about programming topics, and the questions and answers are voted on by the community. The highest voted answers rise to the top.

Incentives, aka crackoverflow.com

The site has a series of incentives to keep people coming back. The biggest incentive is the reputation score, which goes up and down depending on how other users rate your questions and answers. Reputation encourages asking questions and providing answers, in order to improve ones score.

Reputation is in many ways similar to the Karma awarded by reddit.com and Hacker News. Capabilities on the site are unlocked by having a high enough reputation. For example voting on posts requires a score of 15 or more, where new users start with a score of 1.

The other, more unique rewards system on stackoverflow are the badges. Badges are directly modeled after the achievements awarded in Xbox games, which encourage gameplay by granting an award when a level is completed or other objectives achieved. The achievements show up in a gamers profile on Xbox Live, where they are used to talk smack about opponents.

The stackoverflow badges encourage exploration of the features of the site. The first few badges area easy to obtain: fill out your profile to obtain the Autobiographer badge, vote up to get the Supporter badge, and gain the Teacher badge by asking a question which is voted up. Later badges get harder, requiring larger numbers of users to vote on your submissions.

Are these mechanisms effective? I think the reputation score is, certainly. As in a video game, there is a certain thrill to seeing ones score go up. The badges seem, well, hokey to me. I'll grant that I'm probably not the target demographic anyway, badges might have more resonance with those who play games regularly.

Content

The questions during the stackoverflow beta have ranged widely, but by far the most common questions are about Microsoft topics like .Net and SQL Server. This is likely a reflection of the audience of Jeff and Joel's respective blogs being heavily invested in these technologies.

I've been pleasantly surprised by a number of the questions posed on the site. Where the programming sub-reddit is now completely dominated by Ruby, Python, and Haskell, stackoverflow is covering a much wider mix of technologies. There have even been a few embedded system and assembly language questions.

Technical solutions to social problems

The history of web communities dedicated to software developers has not been pretty. The comment section of the programming sub-reddit is now so filled with vitriol and casual slander as to be unpleasant to read, let alone participate in. Hacker News attempts to prevent this slide into toxicity by a combination of social pressure and technical measures like not allowing downvotes until a certain karma has been achieved.

Stackoverflow is relying heavily on technical solutions to social problems. For example:

Downvotes are only allowed by those at higher reputations, and reduce the target reputation by two where an upvote adds ten. Additionally downvoting costs the voter one point of reputation, to discourage frequent use.
To discourage trivial edits to bump a question to the top of the list, more than five edits to a post make it "community owned" and no longer grant reputation to its poster.
Users with sufficiently high reputation can edit another users posts or comments, for example to remove mean-spirited remarks. It is hoped they will use these powers for Good and not Evil.
Users can mark a question or answer as offensive. This does not merely signal a moderator; if enough users click offensive the question will be automatically removed.

Speed bumps coming

I really like the premise behind stackoverflow, of a social media site designed specifically for programmers. I think there is definitely a need which reddit, DZone, and other developer-focussed sites do not fill.

However I think this initial iteration of stackoverflow has a psychological problem: it tries to simultaneously be a voting site like reddit and digg, and a community site like Wikipedia. What you end up with is postings associated with a particular users name, and which provide benefits in the form of reputation, but which can be edited by other users. The site attempts to ameliorate this by making a post "community owned" after five edits, so it no longer belongs to the posting user. This step function solution brings the opposite problem: the poster feels cheated out of the reputation from what has become a popular topic.

This mismatch between the digg and wikipedia models is not working smoothly yet, in my opinion. The digg model thrives on ownership, the wikipedia model on anonymity.

Some other thoughts about future issues:

On other sites even replying to someone else's comment can elicit a defensive reaction. I suspect that editing another user's question or answer on stackoverflow will lead to a series of edit-revert-edit-revert struggles.
There is an enormous incentive to answer quickly: the early answers accrue upvotes and gain significant inertia to accrue more upvotes. A number of users answer immediately by quoting Wikipedia or the first Google result, and gain significant reputation by doing so. stackoverflow will have difficulty succeeding if the highest rated answers are mostly Wikipedia rehashes.
The site is far more active during US business hours, and relatively idle during nights and weekends. When combined with the strong incentive to answer immediately, the site can become a productivity drain. We may see companies block stackoverflow in the same way that Facebook is often blocked.

Conclusion

I really like stackoverflow, and I want it to succeed. I think its business model is sound: focus on a well-defined niche, provide real value, and carefully select advertising to target that specific audience.

UPDATE: This article was picked up on reddit, with amusing commentary. Also Sara Chipps and Dan Dyer have written about their initial impressions of stackoverflow.

The Good, Bad, and Ugly of Gizmo Construction

2008-09-03T05:01:00.000-07:00

Rather by definition, embedded software involves building a gizmo of some sort. Manufacturing the hardware portion of the gizmo turns out to be somewhat more complicated than writing a Makefile and starting the build... who knew?

Today, Gentle Reader, we'll discuss the realities of building hardware products by meandering through a few topics:

Contract Manufacturing
Distributors
Contract Engineering
DVT and Compliance

Contract Manufacturing

Contract manufacturers build a product according to a completed design including the Bill of Materials, the layout of the printed circuit board, assembly instructions, system tests, etc. They can do as much or as little as desired, from a single board up to a completed and tested system directly shipped to your customer.

In the last 25 years contract manufacturing has essentially taken over the production of all electronic goods. The economies of scale from producing such large volumes are overwhelming, and there are very few companies who maintain their own production facilities now. The capital expenses for kitting out an assembly line are daunting, the CM can amortize the cost over a huge number of products. Some well known contract manufacturing firms are Foxconn (also known as Hon Hai), Flextronics (which owns Solectron, another large CM), Celestica, and Sanmina-SCI.

Contract Manufacturers thrive on volume. If building something in really small volumes it is worth looking into production shops aimed at hobbyists, such ExpressPCB.

One thing to keep firmly in mind: the value of a customer to a CM is measured entirely by the volume of future business they expect. If order volumes drop off, the CM will rapidly lose interest. If your market suffers a serious downturn you may find that the quality of the product drops precipitously as the CM rushes through the build in order to get to another, more profitable customer. Similarly if you decide to terminate business with a CM and move to a competing firm, expect astonishingly bad build quality on the final order.

Distributors

Like it or not, distributors are absolutely necessary in the embedded market. There are tens of thousands of customers buying millions of components. The component manufacturers simply cannot afford to maintain individual relationships with each customer when a distributor can represent multiple manufacturers with the same effort and expense.

Many Distributors provide FAEs (Field Application Engineers) to assist their customers in selecting components. A good FAE is extremely valuable, due to the sheer number of product designs they have been involved in. They will often be able to suggest alternatives which you might not otherwise have found, and know which parts have been problematic in other designs.

Distributors and Registration

Distributors who perform a significant amount of technical support during the design of a product cannot allow themselves to be undercut by a cheaper alternative in production. Therefore the component manufacturers allow distributors to register as being responsible for the design win at a particular customer. Only that distributor will be allowed to offer advantageous pricing, other distributors will not be allowed to undercut them.

Distributors do a lot more business with the big Contract Manufacturers than any individual customer, and CMs value their relationship with the distributor more than any individual customer. It is not unknown for a Distie to legitimately claim the design win for one particular component, then obtain the Bill of Materials from the CM and register themselves for every chip in the design. Choosing a Distributor is much like getting married: be very certain that the relationship will work in the long term before signing on the botted line.

Contract Engineering

For a niche market with well-defined needs, a product can sell for years with minimal changes. In these cases its better to contract out the design than recruit a team. The contract will include the functional spec to be designed, timelines for completion, etc. The engineering firm will supply the requisite hardware, software, and firmware expertise, and the resulting design will belong to the customer.

Alternately, Contract Engineering firms can fill in gaps for an in-house design team. For example after components have been chosen and the design competed, a layout for the printed circuit board must be created. A good layout of a complex PCB requires an experienced designer and expensive CAD tools. It makes no sense to keep such a person on staff if only a few designs are done each year, so it is often contracted out. Mechanical design of the chassis and other sheet metal is also often done outside, for the same reason.

Contracts in this area are essentially always on a time and materials basis. The upfront estimate of total cost is not guaranteed. Fixed price contracts are exceedingly rare, because they represent an enormous risk to the engineering firm if the design time goes over estimates. In most cases this will work out fine: the engineering firm will want to get the design done quickly in order to move on to the next customer. However if business slows, watch out for unjustified padding of billable hours.

Design Verification Test

Not every unit coming out of the factory will be identical. Each component in the design has a tolerance, an allowed deviation which is still considered within specification. Every system coming off the line will contain parts slightly above spec or below, and it is important to insure that the complete system will still function reliably even if it contains components at the extreme ends of the tolerance. Though the hardware design takes these tolerances into account, in the real world it is difficult to anticipate every possible interaction of components and PCBs.

This is where DVT, for Design Verification test, comes in. During DVT the hardware engineers measure the system to ensure it not only does what it is supposed to do, but does so with sufficient margin to handle variances in its components. DVT is time-consuming work, and changes are often made in the production system based on what is found in the prototypes.

Compliance

The ubiquitous Underwriters Laboratories logo is likely the most widely known example of a compliance certification, but it is not the only one. There are a huge number of standards for product safety or performance, some recognized around the globe and others specific to each geographic market.

Some industries place much more stringent requirements on their products than others. For example, the NEBS Level 3 guidelines for the telecommunications market specifies that there be no noxious chemicals released if the equipment catches fire. It gives new meaning to the old joke about a "Halt and Catch Fire" instruction.

Conclusions

One of the aims of this blog is to provide insight into fields of software development which don't get as much exposure as Ruby on Rails or web frameworks. I've tried to provide an overview of some of the gritty details of building products. Its really quite exciting when the first prototype of a new system comes back from the factory, and you try to boot the software for the first time. When it doesn't boot, reality hits.

I'd like to thank John Walsh for excellent feedback and suggestions of topics to cover in this posting.

[0123456789abcdef]

2008-08-21T03:01:00.000-07:00

There are only 16 characters to work with, but programmers just love coming up with creative spellings using hex numbers. I suspect that leetspeak evolved out of these spellings, though personally I prefer the original form. I assume that everyone working as a software developer in English will have seen 0xdeadbeef, and probably some other favorites as well.
deadbeef	old standby #1
feedf00d	old standby #2
feedface	old standby #3
decafbad	developers love to complain about coffee
badcafe	developers really love to complain about coffee
badc0ffee	developers really, really love to complain about coffee
badc0c0a	MacOS X developers might find more meaning in this one.
c0c0abad	People who hate MacOS X developers might find more meaning in this one.
A little sed scripting on /usr/share/dist/words can turn up a lot of interesting combinations. For the edification and bemusement of the Gentle Reader, allow me to present a few of them here. I rejected most of the results where '5' replaced an 'S' as being too ugly, but a few passed muster. cat /usr/share/dict/words \| sed \ -e "s/nine/9/g" -e "s/eight/8/g" -e "s/seven/7/g" -e "s/six/6/g" \ -e "s/five/5/g" -e "s/four/4/g" -e "s/three/3/g" -e "s/two/2/g" \ -e "s/one/1/g" -e "s/zero/0/g" \ -e "s/ated/8ed/g" -e "s/[oO]/0/g" -e "s/[lL]/1/g" -e "s/[sS]/5/g" \ \| egrep -v "[^0123456789aAbBcCdDeEfF]" The first few seem particularly suitable for memory fenceposts, either guard words before and after allocations or patterns to scribble over freed memory when looking for use-after-free bugs.
a110c8ed	This memory is in use, buster!
5eef3712	This is ~(0xa110c8ed). No, it doesn't spell anything nifty.
dea110c8	Scribble over memory after free(), to catch dangling references.
defec8ed	to crap all over memory
defaced	another bit pattern to scribble over memory to catch use-after-free errors
To express one's true feelings about the quality of the code base there are really only two options: Profanity-laden comment blocks Clever use of constants
c0defaded	It is a well known fact that old code suffers bit rot. Refactor often!
badfacade	There are times when bad code can only be papered over. This is one of those times.
efface	Good code doesn't make a spectacle of itself.
deface	Bad code, on the other hand, gets drunk at its best friends wedding and hits on the bride.
decade	This code base has been under development for a long time.
baddeed	The EULA for this product specifies the precise amount of bad karma accumulated by using it.
acceded	The software has finally given in.
befa11	As in "what has befallen yon dead process?"
c0dedbad	self explanatory
Magic numbers are useful in all sorts of situations. Encoding one's birthday (0xMMDDYYYY) is clever, but obscure. Subtle jokes in hex also work well.
abbacadabba	Unfortunately 44 bits won't magically fit into a uint32_t.
abadabba dabbadabba abbadabbadabba	Said the monkey to the chimp. Real magic numbers are 128 bit.
d00bee	Debugging probably qualifies as "medicinal purposes."
d0dec0de	How does one pronounce ioctl anyway? "eye oh cottle," or "eye oct all ?"
babe2bed	The kid's bedtime is 7pm sharp.
b0cceba11	You know, I only discovered Bocce Ball in my 30s.
5ca1ab1e	Ignore what you see elsewhere, the secret to scalability is in using good magic numbers.
0x1de	With the leading 0x it sortof looks like "oxide" ... I admit it, this one sucks.
Why should return codes be boring? {0, 1, 2, ...} is so dull. We can do better.
cab0b	yummy
fa1afe1	even more yummy!
b1abbed	probably I/O related
bedded	The code went to sleep?
b0bbed	They call it "floating point" for a reason, bub.
beaded	Um, yeah. I can't think of anything funny about this one.
bab00	My sweet baboo!
10aded	I bet it has an itchy trigger finger, too.
ba11ad	I structure all my code to iambic pentameter.
a100f	My code doesn't like me.
acc01ade	Programmers rarely, if ever, hear praise of their work.
affab1e	Relatively approachable and friendly code, I guess.
babb1e	Why yes, my functions tend to be a bit on the longish side. Why?
baff1e	Why yes, my functions tend to be a bit on the complex side. Why?
babe1	You can write FORTRAN in any language.
ba1b0a	Its the Eye of the Tiger, baby!
ed1f1ce	large, imposing blocks of code
5eceded	This module has declared its independence from the rest of the system.
5c01ded	At times, it is necessary to be stern with the codebase. Give it a time out.
5caff01d	This code was intended to be temporary. That was four years ago. Such is the way of things.
ad0be	I bet they use this one in Photoshop.
ab0de	my humble abode
d8edbabe	In college, yeah, sure you did.
0ddba11	That is a strange one, alright.
Finally, here are some 16 bit numbers which are more interesting than "dead," "f00d" and "beef"
caca	A statement about software quality, I suppose.
deaf	When programming, no-one can hear you scream.
c0ed	It is the 21st century, after all.
ba1d	If tires can go bald, why not programs?
a1fa	I couldn't find a reasonable approximation of beta.
f01d	Origami programming!
fa11	If code falls in the forest, does it make a sound?
c01d	Software is a dish best served cold.
ab1e	Or ! 0xab1e, as the case may be.
cede	I give up, I'm done.
Do you have any additional hex numbers to share? The comments section is open for business.

Update: Lisa Simone wrote an article about teaching embedded systems and the use of hex words in an article on her site.

opensource.mycompany.com

2008-08-07T00:01:00.000-07:00

Using GPL software imposes the requirement to redistribute the source code, but this requirement is routinely ignored in commercial products. That is a shame: even if one doesn't care about the goals of the free software movement, simple pragmatism would still favor providing the source code. Violating the GPL can cause Bad Things™ to happen, and compliance isn't very difficult. It is quite common for products to incorporate an almost unmodified busybox, glibc, and Linux kernel. Providing the source code for these cases is straightforward, and doesn't risk inadvertently giving away intellectual property.

Section 3 of version 2 of the GNU Public License concerns the responsibility to distribute source code along with a binary:

  3. You may copy and distribute the Program (or a work based on it, under Section 2) in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following:

a) Accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or,

b) Accompany it with a written offer, valid for at least three years, to give any third party, for a charge no more than your cost of physically performing source distribution, a complete machine-readable copy of the corresponding source code, to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or,

c) Accompany it with the information you received as to the offer to distribute corresponding source code.  (This alternative is allowed only for noncommercial distribution and only if you received the program in object code or executable form with such an offer, in accord with Subsection b above.)

The source code for a work means the preferred form of the work for making modifications to it.  For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to
control compilation and installation of the executable.  However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable.

If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code.

I am not a lawyer, though I think it might be fun to play one on TV. There is a lot of detail in the GPL about the requirements for distribution of source code, and maybe I'm dense but I don't understand what half of it means. However I would contend that if you get to the point of needing to argue over the precise definition of the terms in a legal context, you've already failed.

The problem with violating the GPL is not that you'll get sued. Of course, it is quite possible you'll be sued for violating the GPL...

... but getting sued is not the real problem. The real problem is when a posting about misappropriation of GPL software shows up on Slashdot and LWN. The real problem is when every public-facing phone number and email address for your company becomes swamped by legions of Linux fans demanding to know when you will provide the source code. The real problem persists for years after the event, when Google searches for the name of your products turn up links about GPL violations coupled with ill-informed but damaging rants.

So we want to avoid that outcome. If you read the legal complaints filed by the Software Freedom Law Center, they follow a similar pattern:

Someone discovers a product which incorporates GPL code such as busybox, but cannot find the source code on the company web site (probably because the company hasn't posted it).
This person sends a request for the source code to an address they find on that website, possibly support@mycompany.com.
This request is completely ignored or receives an unsatisfactory response.
The person contacts SFLC, who sends a letter to the legal department of the infringing company demanding compliance with the license and that steps be taken to ensure no future infringements take place.
SFLC also demands compensation for their legal expenses; thats how they fund their operation.
The corporate legal team, misreading the complaint as a shakedown attempt, stonewalls the whole thing or offers some steps but refuses to pay legal costs.
Lawsuit is filed, and the PR nightmare begins in earnest.

Keeping Bad Things From Happening

There are two points in that progression where the bad result could be averted, in steps #2 and #4. Unfortunately it is not likely you can influence either one:

In step #2 you have no idea where that initial request for the source code will go. They might send email to the sales department, or tech support. They might call the main corporate number and chat with the answering service. The request will very likely be filtered out before it makes it to someone who would realize its significance.
By the time the lawyers get involved in step #4, you're already toast. Corporations, particularly medium to large corporations, are routinely targeted to extract money for licensing intellectual property, business partnerships, or any number of reasons. The GPL claim will look like all the rest, and be treated in the same way.

This is a case where it is best to be proactive. One can't realistically wait until the first time someone requests the source code, too many things can go wrong and lead to the PR nightmare. Instead, Gentle Reader, it is best to post the GPL code somewhere that it can be found with little difficulty by someone looking for it, but otherwise draw little attention to itself.

When the GPL was created software was delivered via some physical medium (magnetic tapes, later supplanted by floppy disks, CDs, DVDs, etc). One was expected to include the source code on the same medium, or at least be willing to provide another tape containing the source. Nowadays many embedded systems are delivered with the software pre-installed and updates delivered via the Internet, so adding a CD of source code would add to the Cost of Goods Sold. Anything which adds COGS is probably a non-starter, so we'll move on.

It is certainly an option to tar up all of the GPL packages from the source tree and try to get it linked from the corporate website, likely controlled by someone in the marketing department. That conversation may not go the way you want:

"Tell me again why we need to do this?"

"We're not an opensource company, we build widgets."

"Isn't Montavista supposed to take care of this for us?"

"Our market messaging revolves around the power of our brand and the strength of our secret sauce, not opensource code. End of discussion, you commie punk."

The (hypothetical) marketing person is not being unreasonable. Ok, the last one would be unreasonable, but I thought it would be funny. Nonetheless putting GPL source code right up on the corporate website implies it is a primary focus of the corporation, when in reality it probably is just one of many tools you use in building a product. Rather than find a place on the corporate website, I advise a separate site specifically for opensource code. It needs to be something which people can easily find if they are motivated to look for it, but otherwise not draw much attention to itself. opensource.<mycompany>.com or gpl.<mycompany>.com are reasonable conventions.

Next you need a web server. Your company may already work with a web host, otherwise Google Sites is a reasonable (and free) choice. You'll need IT to set up a DNS CNAME directing opensource.<mycompany>.com to point to the new web site. If you're using Google Sites there is a Help Topic on how to do this.

The goal here is to avoid the bad result (GPL violation being posted to slashdot), not draw attention. You shouldn't spend time putting together a snazzy web site, a simple background with links to tarballs is fine. Ideally nobody will ever look at these pages.

Documentation

Lets talk about documentation. There are a number of other open source software licenses, besides the GPL. Many of them carry an "advertising clause," a requirement that "all advertising materials mentioning features or use of this software must display" an acknowledgement of the code used. The use of this clause derives from Berkeley's original license for BSD Unix, and though Berkeley has disavowed the practice there is still a great deal of open source software out there which requires it.

In practice the advertising clause results in a long appendix in the product documentation listing all of the various contributors. Honestly nobody will ever read that appendix, but nonetheless it is worth putting together. You can also include a notice that the GPL code is available for download from the following URL... so if despite your best efforts the company does get sued, you'll have something concrete to point to in defense.

Now for the hard part

The Gentle Reader may have noticed that we have not covered how to locate the GPL code used within a product. Really I'm hoping that the source tree is sufficiently organized to be able to browse the top few levels of directories and look for files named LICENSE and for copyright notices at the top of files. If it is difficult to determine whether the product contains any open source code, there is an article at Datamation which might be helpful. It discusses compliance tools, including tools which look for signatures from well-known codebases to track down more serious GPL violations.

What about the difficult case, where GPL code is being used and has been extended with proprietary code which cannot simply be posted to a website? Even if one doesn't care about the free software ethos, pragmatically this is a ticking time bomb and one that should not be ignored. I'd recommend putting up an opensource website anyway to post what you can, and working as soon as possible to disentangle the rest. Development of new features in that area of the code can be used as the lever to refactor it in a GPL-compliant way.

Update 8/2008: The Software Freedom Law Center has published a GPL compliance guide.

10/2008: Linux Hater's Redux holds up this blog post as an example of why Linux should be avoided. Okey dokey.

12/2008: Add Cisco to the list of companies sued by the SFLC over GPL issues. This time the suit was filed on behalf of the FSF for glibc, coreutils, and other core GNU components. Reactions to the news from Ars Technica and Joe Brockmeier @ ZDNET have already appeared.

5/2009: Cisco and the FSF have settled their lawsuit. Cisco will appoint a Free Software Director, make attempts to notify owners of Liksys products of their rights under the GPL, and will make a monetary contribution to the FSF.

The Control Plane is not an Aircraft

2008-07-23T06:50:00.000-07:00

In my industry at least, the high end of the margin curve is dominated by modular systems: a chassis into which cards can be added to add features, increase capacity, etc. Products at the cheaper end of the spectrum tend to be a fixed configuration, a closed box which does stuff but is not terribly expandable (often called a pizza box). The fixed configuration products sell in much larger volumes, but margins are lower.

In a pizza box system the control plane between the CPU and the chips it controls tends to be straightforward, as there is sufficient board space to route parallel busses everywhere. PCI is often used as the control interface, as most embedded CPUs contain a PCI controller and a lot of merchant silicon uses this interface.

In a chassis product, there is typically a central supervisor card (or perhaps two, for redundancy) controlling a series of line cards. There are a huge number of options for how to handle the control plane over the backplane, but they mainly fall into two categories: memory mapped and message oriented. In todays article we'll examine the big picture of control plane software for a modular chassis, and then dive into some of the details.

Memory Mapped Control Plane

A memory-mapped chassis control plane extends a bus like PCI over traces on the backplane.

To the software, all boards in the chassis appear as one enormous set of ASICs to manage.

Message Passing Control Plane

Alternately, the chassis may rely on a network running between the supervisor and line cards to handle control duties. There are PHY chips to run ethernet via PCB traces, and inexpensive switch products like the Roboswitch to fan out from the supervisor CPU out to each slot in the chassis.

This system requires more software, as each line card runs its own image in addition to the supervisor card. The line cards receive messages from the supervisor and control their local ASICs, while the supervisor has to handle any local ASICs directly and generate messages to control the remote cards.

Programming Model

As the Gentle Reader undoubtedly already knows, the programming model for these two different system arrangements will be radically different.

Memory mapped ASICs are mapped in as pointers	Message Passing ASICs controlled using, erm, messages. Yeah.
volatile myHWRegisters_t p; p = <map in the hardware>* p->reset = 1;	myHWMessage_t msg; msg.code = DO_RESET_ASIC; send(socket, &msg, sizeof(msg), 0);

Perhaps that was obvious. Moving on... At first glance the memory mapped model looks pretty compelling:

it the same as a fixed configuration product, allowing easy code reuse
in the message passing model you still have to write memory map code to run out on the line card CPUs, and then you have to write the messaging layer

Hot Swap Complicates Things

A big issue in the software support for a chassis is support for hot swap. Cards can be inserted or removed from the chassis at any time, while the system runs. The software needs to handle having cards come and go.

With a message passing system hotswap is fairly straightforward to handle: the software will be notified of insertion or removal events, and starts sending messages. If there is a race condition where a message is sent to a card which has just been removed, nothing terrible happens. The software needs to handle timeouts and gracefully recover from an unresponsive card, but this isn't too difficult to manage.

With a memory mapped chassis, hot insertion is relatively simple. The software is notified of an insertion event, and maps in the hardware registers. Removal is not so simple. If the software is given sufficient notice that the card is being removed, it can be cleanly unmapped and safely removed. If the card is yanked out of the chassis before the software is ready, havoc can ensue. Pointers will suddenly reference a non-existant device.

Blame the Hardware

So card removal is difficult to handle robustly in a chassis which memory-maps the line cards.

Ideally the hardware should help the software handle card removal. For example CompactPCI cards include a microswitch on the ejector lever, which signals the software of an imminent removal. The user is supposed to flip the switch and wait for an LED to light up, an indication that the card is ready to be removed. Of course, people ignore the LED and pull the card out anyway if it takes longer than 1.26 seconds... we did studies, and stuff... ok I just made that number up. Card removal is often then made into a software problem: "Just add a CLI command to deprovision the card, or something."

This makes for a reasonably nasty programming environment: to be robust you have to constantly double-check that the card is still present. Get a link up indication from one of the ports? Better check the card presence before trying to use that port, in case the linkup turns out to be the buswatcher's 0xdeadbeef pattern. Read an indication from one of the line cards that its waaaaay over temperature? Check that it is still there before you begin shutting the system down, it might just be a garbage reading.

Pragmatism is a Virtue

There is a maxim in the marketing strategy for a chassis product line: never let the customer remove the chassis from the rack - they might replace it with a competitors chassis. You can evolve the design of the line cards and other modules, but they must function in the chassis already present at the customer site. Backplane designs thus remain in production for a long time, often lasting through several generations of card designs before finally being retired. Though the Gentle Reader might have a firm preference for one control plane architecture or another, the harsh reality is that one likely has to accept whatever was designed in years ago.

So we'll spend a little time talking about the software support for the two alternatives.

Thoughts on Memory Mapped Designs

Software to control a hardware device does not automatically have to run in the kernel. There are only a few things which the kernel absolutely has to do:

map the physical address of the device in at a virtual address
handle interrupts and mask the hardware IRQ
deal with DMA, as this involves physical addressing of buffers

Everything else, all of the code to initialize the devices and all of the higher level handling in response to an interrupt, can go into a user space process where it will be easier to debug and maintain. The kernel driver needs to support an mmap() entry point, allowing the process to map in the hardware registers. Once mapped, the user process can program the hardware without ever calling into the kernel again.

Thoughts on Message Passing Designs

First, an assertion: RPC is a terrible way to implement a control plane. One of the advantages of having CPUs on each card is the ability to run operations in parallel, but using remote procedure calls means the CPUs will spend a lot of their time blocked. The control plane should be structured as a FIFO of operations in flight, without having to wait for each operation to complete. If information is needed from the remote card it should be structured as a callback, not a blocking operation.

It is tempting to implement the control communications as a series of commands sent from the supervisor CPU to the line cards. Individual commands would most likely be a high level operation, requiring the line card CPU to implement a series of accesses to the hardware. The amount of CPU time it takes for the supervisor to send the command would be relatively small compared to the amount of time the line card will spend implementing the command, likely accentuated by a significantly faster CPU in the supervisor. Therefore the supervisor will be able to generate operations far faster than the line cards can handle them. In networking gear this is most visible when a link is flapping [an ethernet link being established and lost very rapidly] where commands are sent each time to reconfigure the other links. If the flapping persists, you either cause a failure by overflowing buffers in the control plane or start making the supervisor block while waiting for the line card to drain its queue. Either way, its bad.

One technique to avoid these overloads is to have the supervisor delay sending a message for a short time. If additional operations need to be done, the supervisor can discard the earlier updates and send only the most recent ones. The downside of delaying messages in this way is that it is a delay, and responsiveness suffers.

Another technique involves a somewhat more radical restructuring. The line card most likely contains various distinct bits of functionality which are mostly decoupled. Falling back to my usual example of networking gear, the configuration of each port is mostly independent of the other ports. Rather than send a message describing the changes to be made to the port, have the supervisor send a message containing the complete port state. Because each message contains a complete snapshot of the desired state of the port, the line card can freely discard older messages so long as it implements the one most recently sent.

By structuring the control messages to contain a desired state, you allow the remote card to degrade gracefully under load. Under light load it can probably handle every message the supervisor sends, while under heavier load it will be able to skip multiple updates to the same state.

Note that the ordering of updates is lost, as events can be coalesced into a different order than that in which they were sent. This coalescing scheme can only work if the various bits of state really are independent, if one state depends on an earlier update to a different state then they are not independent.

Closing Thoughts

Gack, enough about control plane implementation already.

The comments section recently converted over to Disqus, which allows threading so the Gentle Reader can reply to an earlier comment. Anonymous comments are enabled for now, though if comment spam becomes a problem that may change.

gdb lies to you

2008-07-02T21:01:00.000-07:00

Because I'm a terrible programmer, I spend a lot of time in gdb. gdb is a fantastic tool that has (so far) kept me from getting fired, but it has its limitations. Today, Gentle Reader, we will talk about one of the particularly vexing limitations.

Not Always Correct, but Never Uncertain
Have you ever opened a core and immediately spotted the problem: "Oh, foo() was called with a bad argument. That isn't a valid widget ID." So you dig around in the data structures which were used to call foo(), but you cannot see how it could possibly have been called with the argument gdb is showing?

You're right, the program did not call foo with a bizarre argument. gdb is displaying incorrect information. Lets take a simple example:

int testgdb()
{
    return foo(123);
}

int foo(int a)
{
    return bar(456);
}

int bar (int a)
{
    *((int *)NULL) = 0;  /* Deliberately crash */
    return a;
}

foo is called with a constant argument of 123. foo calls bar(456), and bar deliberately segfaults. Now lets examine the backtrace:

(gdb) bt
#0  0x80045a1c in bar (a=456) at foo.c:4
#1  0x80045a30 in foo (a=456) at foo.c:10
#2  0x80045a4c in testgdb () at foo.c:15

Weird, huh? How did foo get called with an argument of 456? The answer, of course, is that it didn't. It was called with 123 as its argument, and gdb is displaying incorrect information.

More MIPS Assembly, Please
Because it is one of my favorite techniques, lets disassemble the object code to see why this happens. This was compiled for MIPS32 using gcc -O2, but with inlining disabled (because we need to have function calls if we're going to talk about function arguments).

We'll start with testgdb():

<testgdb>:
addiu sp,sp,-24	push a stack frame
sw ra,16(sp)	store the return address to the stack
jal <foo>	jump to foo()
li a0,123	pass 123 as the first argument to foo (in delay slot)
lw ra,16(sp)	load return address back from the stack
jr ra	return to the caller
addiu sp,sp,24	pop the stack frame

MIPS passes arguments in CPU registers, and this is crucial to understanding why gdb sometimes displays the arguments incorrectly. Every CPU architecture has a set of "calling conventions" of how the compiler should pass arguments to functions. A long time ago in architectures like VAX and 680x0, arguments would be pushed on the stack. Since then CPUs have gotten dramatically faster while memory speed has improved less rapidly, so modern calling conventions pass arguments in registers whenever possible. The original calling conventions for x86 used the stack but the more recent "fastcall" passes two arguments in registers, while x86_64 uses registers for up to four arguments.

In the assembly example above the argument to foo is loaded into register a0, using a "load immediate" instruction. This instructions happens to be in a delay slot: with MIPS the instruction immediately following a branch is always executed.

<foo>:
addiu sp,sp,-24	push a stack frame
sw ra,16(sp)	save return address to the stack
jal <bar>	jump to bar()
li a0,456	pass 456 as first argument to bar (in delay slot)
lw ra,16(sp)	after returning from bar(), load return address
jr ra	return to the caller
addiu sp,sp,24	pop the stack frame

foo() pushes a stack frame and loads 456 into a0 in order to call bar(). The crucial thing to notice is that the current value of a0 was not saved anywhere before overwriting it with 456. The compiler determined that the original value was no longer required for any further computation, and did not need to be saved. So the "123" value stored in a0 has been irrevocably lost. foo next calls bar, and crashes.

In the gdb backtrace the function arguments will be displayed from the stack if they are available. Otherwise, gdb displays the values of the argument registers and hopes for the best. The arguments in the backtrace are mostly correct because gdb can often pull them from the stack. When compiled -O0 functions always save their argument registers to the stack, so it is only optimized code which can make debugging difficult in this way.

Et tu, gdb?

What can one do about this? Mainly be aware that what the debugger shows is not always correct. I believe this is good practice in general, always be a little bit suspicious of the tools.

Personally I'd find it more helpful if gdb were to display "<argument unknown>" rather than an incorrect value, if it can determine that the argument register has been re-used. I've tried digging through the gdb sources to see if this could be improved, but got lost in mips-tdep.c (reference first paragraph about me being a terrible programmer). Information about register re-use is typically not included in the compiler's debugging information anyway, so gdb may not have sufficient information to know when a register still holds the correct argument value.

More Random Musings on Embedded Filesystems

2008-06-25T02:03:00.000-07:00

The first set of random musings ended up being far longer than planned, and rather a lot of material ended up on the cutting room floor. Some of it has been swept into this article.

Incremental Patches

The Gentle Reader may have noticed that using a read-only file system like squashfs has an important repercussion: it is impossible to copy in a modified file as an incremental patch. No matter how small the change, delivering a bug fix means delivering a complete new filesystem. Realistically, this means a complete new software image.

Personally I don't consider this to be a drawback for an embedded system. Microsoft, Apple, and most Linux distributions offer incremental patches because it suits their needs: when your software image is gigabytes in size and you have gazillions of users, it is important to deliver fixes in a bandwidth-efficient way. Embedded software is less affected by this problem, as it tends to be much smaller and have fewer downloads (either because the product sells in low volume, or has a relatively low fraction of users who will ever apply the updates).

Additionally, incremental patches come with their own set of costs:

perhaps obviously, you need management software to apply, remove, and list installed patches
tech support has a larger number of variations to deal with
test load increases rather dramatically: if you have 5 independent patches you may need to test the combinations: up to 2^5=32 variations to test, not just 5.

Again, for companies the size of Microsoft/Apple/RedHat these issues can be handled, but for a small company it can greatly add to the support and QA load for little real benefit.

So personally, I favor not delivering incremental patches. For each major release of the product, maintain a patch branch containing all accumulated fixes to date. When a new customer issue comes in, the fix is added to the tip of that branch and a complete new build released with an incremented version number. In exceptional cases (an issue for one specific customer which may be deleterious for other customers) a new branch can be made and a private image delivered, but for your own sanity you want to make this an infrequent occurrence.

General purpose OS vendors also use incremental patches to deliver fixes for specific problems without annoying their customers with superfluous changes or breakage. This is an issue for embedded vendors as well: there is no customer quite so pissed off as one where a software patch made things worse. However in the end I think this boils down to being disciplined about what changes are allowed in a maintenance release, and what needs to be pushed out to the next major release.

How to Implement Incremental Patches

If you really want to deliver incremental patches, it can still be done using the filesystem choices recommended here. The key observation is that even though there is a file in the filesystem, you don't have to use it. If a newer binary is present elsewhere, you can use it instead.

To implement this scheme it is easiest to segregate the locally developed applications into their own directory, for example /mycompany/bin instead of directly in /bin. For this example I'll assume that incremental patch binaries will be installed in a flash filesystem in /flash/mycompany. When assembling the squashfs/cramfs/etc for a release, place the application binaries in /ro/mycompany/bin and make /mycompany be a softlink to the writeable ramdisk:

# ls -l /
drwxr-xr-x    1 root     root          472 Jun  6 11:55 bin
drwxr-xr-x    1 root     root          836 Jun  6 11:55 dev
lrwxrwxrwx    1 root     root            7 Jun  6 11:55 etc -> /rw/etc
drwxr-xr-x    1 root     root          555 Jun  6 11:55 lib
lrwxrwxrwx    1 root     root            9 Jun  6 11:55 mycompany -> /rw/mycompany
drwxr-xr-x    1 root     root           12 Jun  6 11:55 ro
drwxrwxrwt    9 root     root          180 Jun  6 12:17 rw
lrwxrwxrwx    1 root     root            7 Jun  6 11:55 tmp -> /rw/tmp
lrwxrwxrwx    1 root     root            7 Jun  6 11:55 var -> /rw/var

At boot, you would use a script to populate softlinks in the /mycompany directory structure to point to each binary in /ro/mycompany. If an updated version of the application binary is available in /flash, the softlink will be updated to point to it instead.

# First populate links to the release binaries
cd /ro
for dir in `find mycompany -type d -noleaf`; do
    mkdir -p /$dir
done
for file in `find mycompany -not -type d -noleaf`; do
    ln -s -f /ro/$file /$file
done
        
# Now replace the softlinks for binaries which we've incrementally patched
cd /flash
for dir in `find mycompany -type d -noleaf`; do
    mkdir -p /$dir
done
for file in `find mycompany -not -type d -noleaf`; do
    ln -s -f /flash/$file /$file
done

What you'll end up with is a series of softlinks:

# ls -l /mycompany/bin/
lrwxrwxrwx 1 root  root 22 Jun 24 16:49 appNum1 -> /ro/mycompany/bin/appNum1
lrwxrwxrwx 1 root  root 22 Jun 24 16:49 appNum2 -> /ro/mycompany/bin/appNum2
lrwxrwxrwx 1 root  root 25 Jun 24 16:49 appNum3 -> /flash/mycompany/bin/appNum3

Flash filesystems

These two articles have focussed on in-memory filesystems. If the total size of the libraries and binaries is reasonably small an embedded system can get by with just the in-memory filesystem, but at some point it makes more sense to store the application binaries in a flash filesystem to be paged into memory as needed. The Gentle Reader might be interested in an overview of flash filesystem technology at the IBM developerWorks site, written by M. Tim Jones.

For now, I'll leave it at that.

Random Musings on Embedded Filesystems

2008-05-31T21:18:00.000-07:00

Getting the kernel to successfully boot on a new board is a wonderful feeling, which lasts about 5 seconds before the application developers begin clamoring for time on the box. For the apps work to make progress the application binaries have to be accessible in a filesystem somewhere. During platform bringup it is common to use NFS because it will "just work" almost immediately after you get the platform to boot.

I'd advise not relying on NFS for very long: using a server with gigabytes of disk means you're completely insulated from size constraints. You may find that the application footprint grows astronomically simply because nobody notices the pain. Adding library dependencies which pull in 20 Megs of DLLs is invisible on an NFS server, but a crisis when you discover very late in the process that it won't fit in flash.

Lets start by listing a few assumptions about the target:

it does not have a hard disk (i.e. a spinning, magnetic disk)
it has at least as much DRAM as flash, probably more.
it uses a 32 or 64 bit processor with an MMU (PowerPC, MIPS, ARM, x86, etc)

If your platform is significantly different from these assumptions, the recommendations in this article may not be appropriate. The biggest one is the hard disk: if your system has one, don't use these recommendations - your filesystem choices should revolve around what the disk can do for you. If your system does not have an MMU some of these recommendations may apply, but you need to look at using uCLinux and its associated best practices.

A Note about the Buffer Cache

The Linux I/O system is designed for a general purpose computer, with a disk connected to an I/O interface. Recently accessed files are stored in memory in the buffer cache; if the files are accessed again they can be provided from cache instead of hitting the disk a second time. You may also come across references to a page cache; in current kernel versions the page cache and buffer cache have been merged into a single pool of memory.

Embedded systems generally don't have a disk, their filesystems reside in RAM. Nonetheless Linux still relies on the buffer cache. So though a file resides in a RAMdisk it will be read into the buffer cache, and then to the process which requested it. The buffer cache doesn't add as much value in this setup (re-reading the filesystem would be quick), but the buffer cache is essential to support Linux APIs like mmap(). The effect of the buffer cache will be described in a bit more detail later in the article.

Option #1: Squashfs and tmpfs

SquashFS is a compressed, read-only filesystem. A squashfs filesystem is constructed offline, compressing a directory structure into a binary blob which can be loaded into memory and mounted. As blocks are read from the squashfs they are decompressed into the buffer cache; if memory becomes tight the cache can toss pages out and re-read them from the squashfs as needed. Thus the memory footprint is fairly well minimized, only files in active use will be decompressed.

Squashfs is inherently read-only. It is not mounted read-only, such that you could remount it read-write. The squashfs filesystem is assembled at compile time; once created it is immutable. This is generally acceptable for filesystems which shouldn't change anyway, like /bin or /lib, but is clearly not suitable for everything. There are configuration files like /etc/resolv.conf and /etc/timezone which probably need to be occasionally written, and numerous scratch files reside in /tmp. Therefore a second filesystem is needed, a writeable ramdisk.

tmpfs is a ramdisk, and is a good way to provide the writeable portions of the filesystem. Daniel Robbins wrote an excellent article about tmpfs, published at IBM DeveloperWorks a few years ago. Squashfs would be used for the root filesystem mounted on /, while the tmpfs would be mounted on a subdirectory like /rw. /etc, /var and /tmp are most easily provided as soft links to the tmpfs. For example:

# ls  -l /
dr-xr-xr-x    1 root     472 May 16 10:10 bin
dr-xr-xr-x    1 root     836 May 16 10:10 dev
lrwxrwxrwx    1 root       7 May 16 10:10 etc -> /rw/etc
dr-xr-xr-x    1 root     555 May 16 10:10 lib
dr-xr-xr-x   97 root       0 Dec 31  1969 proc
lrwxrwxrwx    1 root       8 May 16 10:10 root -> /rw/root
drwxrwxrwt    9 root     180 May 16 10:12 rw
dr-xr-xr-x    1 root     151 May 16 10:10 sbin
lrwxrwxrwx    1 root       7 May 16 10:10 tmp -> /rw/tmp
dr-xr-xr-x    1 root      23 May 16 10:09 usr
lrwxrwxrwx    1 root       7 May 16 10:10 var -> /rw/var

At boot, the init script would mount the tmpfs filesystem and create the directories which the softlinks point to. You can specify a maximum size when mounting the tmpfs, 8 megabytes in this example:

if mount -t tmpfs -o size=8m tmpfs /rw >/dev/null 2>&1; then
    mkdir /rw/tmp /rw/var /rw/etc /rw/root
else
    # Halt and catch fire
fi

Squashfs has not been accepted into the mainline kernel, so you will need to download patches from the project website. There is also a LZMA-enhanced version of Squashfs, though I have not personally used this version. LZMA appears to obtain better compression ratios than the zlib which Squashfs normally uses.

For the root directory ("/"), the kernel has to be able to recognize and mount the filesystem without relying on any external mount program. This is a chicken and egg problem: there is no way to run a mount program until there is a filesystem mounted. To use squashfs for the root filesystem, linux/init/do_mounts.c must be modified to recognize its magic number. A patch is available, if your kernel source does not already have this handling. The patch also handles a cramfs root filesystem.

Option #2: cramfs instead of squashfs

cramfs is an older compressed, read-only filesystem for Linux, developed by Linus Torvalds. Cramfs works quite well and is included in the kernel sources. However squashfs typically achieves better compression, because it uses larger blocks in zlib. In one project I worked on a 20 Meg cramfs filesystem became about 18 Megs with squashfs.

Like squashfs, cramfs must be paired with a second, writable ramdisk to be useful.

Option #3: ext2 instead of tmpfs

ext2 can be use to provide a writeable ramdisk, though there are relatively few reasons to use it for this purpose as opposed to tmpfs. Older tmpfs releases did not support certain filesystem features like sendfile(), but this is not an issue for most applications.

Nonetheless if there is a reason to do so, an ext2 filesystem can be created in a /dev/ram# device and mounted as a ramdisk. ext2 has to be formatted before it can be used, which would normally mean bundling mke2fs into your target image. However there is another way to create an ext2 which is generally smaller than mke2fs. Empty, zero filled ext2 filesystems compress extremely well using bzip2. You can create a filesystem of the appropriate size while compiling the target image, by running commands on your build system:

dd if=/dev/zero of=/tmp/e2file bs=1024 count=8192
sudo losetup /dev/loop7 /tmp/e2file
sudo mke2fs -b 4096 -m 1 -i 16384 /dev/loop7
sudo tune2fs -c -1 /dev/loop7
sudo losetup -d /dev/loop7
bzip2 -9 /tmp/e2file

The bs and count arguments to dd specify the size of file to create, filled with zeros. We use a /dev/loop device to create a new ext2 filesystem in this file, and then compress it. The result should be a couple hundred bytes in size, far smaller than mke2fs would be. The e2file.bz2 is copied into the target filesystem, and mounted by the boot scripts like so:

bunzip2 -c /e2file.bz2 >/dev/ram2 2>/dev/null
if mount -t ext2 /dev/ram2 /rw >/dev/null 2>&1; then
    mkdir /rw/tmp /rw/var /rw/etc /rw/root
else
    # Halt and catch fire
fi

Option #4: JFFS2 instead of tmpfs

In the discussion of the previous alternatives the read-only portion of the filesystem would be compressed in memory using squashfs or cramfs, but the writable portion would be stored uncompressed. If your system requires a large amount of ramdisk space but your memory is constrained, the natural solution is to look for a way to compress it.

If the applications generating this data can be modified to use zlib and compress their own output, that is probably the best way to proceed. If you cannot modify the apps, there are a couple ways to get compression at the filesystem layer. The only natively compressed, writable filesystem for Linux I know of is JFFS2, which is not designed to be a ramdisk but can be pressed into service if necessary using the mtdram.o module (which exists to ease debugging of MTD applications). The vast majority of the complexity in JFFS2, for handling erase blocks and wear leveling and all of the other nuances of flash chips, is wasted when used as a ramdisk, but it does provide compression. The boot scripts would work like so:

/sbin/insmod -q /lib/modules/mtdram.o total_size=8192 erase_size=16
if mount -n -t jffs2 -o umask=0666 /dev/mtdblocka /rw >/dev/null 2>&1; then
    mkdir /rw/tmp /rw/var /rw/etc /rw/root
else
    # Halt and catch fire
fi

JFFS2 consumes a great deal more CPU time than other filesystems, due to the compression. The throughput to a compressed ramdisk will be relatively low. On one platform I worked on a tmpfs ramdisk could handle writes at about 40 MBytes/sec while the JFFS2 ramdisk managed only 1 MByte/sec.

Note that this technique does not save as much memory as you might think. Whenever blocks are accessed they are decompressed by JFFS2 into the buffer cache, then copied up to the application. Likewise written blocks are held uncompressed in the buffer cache. If your system touches a large amount of data in the ramdisk, the footprint of the buffer cache will become more significant than the backing filesystem in JFFS2. This is another advantage of modifying applications to use zlib: the data remains compressed in the buffer cache, and is only decompressed within the application itself.

There are other ways to implement a compressed, writable filesystem, but I have not used them myself and can't add anything pithy about them. Some links:

cloop is a compressed block loopback device, allowing any filesystem to be mounted atop it
e2compr patches compression support into ext2/ext3. Development was moribund for a long time, it is not clear to me how stable these patches are.

Option #5: ext2 for everything

In large measure ext2 and the related ext3 are the "default" filesystem for Linux. When building a Linux desktop or server ext[23] is a reasonable solution, and the one generally chosen barring good reason to do otherwise. This notion of ext2 as the default often carries over into embedded systems as well, though there is far less advantage to doing so. It is certainly possible to create a large ext2 ramdisk (using the /dev/loop technique shown above) and use it to store both the application binaries as well as provide scratch space for /tmp et al. This does have the appeal of requiring only one filesystem, rather than the combinations recommended earlier.

The memory footprint of an ext2 ramdisk is always going to be larger than the options described above. It is common practice to create the ext2 filesystem in a file, gzip it, and compile the gzipped binary into the target image. This reduces the image size, but at boot the kernel will decompress the entire filesystem into memory. So if you have a 40 Meg ext2 which gzips down to 10 Megs, it will only add 10 Megs to the image size but expand to 40 Megs of RAM on the target. Compare this to squashfs, where a 10 Meg filesystem adds 10 Megs to the image size and also consumes 10 Megs of RAM on the target. The buffer cache does not perturb the result: when using either ext2 or squashfs, any files in active use will be present in the buffer cache and the footprint would be the same in both cases.

Postscript

This turned into an exceedingly long post. Early drafts were even longer, and much material got left on the cutting room floor. I'll collect more random musings on embedded filesystems into a future post.

Updates

A comment from Lance pointed to a discussion on LKML about extending cramfs to be writable. Changes made to files would be stored in the page cache, and as far as I can tell would be stored in uncompressed form. The same technique could presumably be applied to squashfs. This would make things a bit simpler for those who need a small amount of writable ramdisk.

Tom Ziomek notes that SquashFS has been accepted into the mainline kernel in 2.6.29. Scroll down to see Tom's comment; since this article appeared this blog switched to using Disqus, so you see the older comments first followed by the recent comments in a separate Disqus section.

The High-Level CPU Response

2008-05-08T21:27:00.000-07:00

This time, Gentle Readers, we will explore something completely different. It is still related to embedded systems, for a suitably generous definition of "embedded." Several weeks ago I read a posting by Yossi Kreinin regarding CPU architectures optimized for very high level languages, plus a followup on the same topic.

Yossi said:
Do you think high-level languages would run fast if the stock hardware weren't "brain-damaged"/"built to run C"/"a von Neumann machine (instead of some other wonderful thing)"? You do think so? I have a challenge for you. I bet you'll be interested.
...
My challenge is this. If you think that you know how hardware and/or compilers should be designed to support HLLs, why don't you actually tell us about it, instead of briefly mentioning it?

Really, the challenge would not normally appeal to me:

I generally don't spend time on high-level languages. I make my living in the guts of the system writing assembly and C code, where Lisp/Haskell/Erlang/<ShinyNewLanguage>/etc do not play.
I like C. Really, I do. I like assembly coding too. Really, I do.
I think von Neumann architectures are fine.

However in the past few years I've worked on three different ASICs involving custom embedded CPUs for the datapath (more accurately: two CPUs and one glorified state machine), and Yossi's challenge is interesting in a contemporary problem space. So I'll give it a whirl. Be warned, Gentle Readers, that it will probably suck. You have been warned.

The instruction set

In 2008, I believe the instruction set is the wrong place to look for these performance gains. The overwhelming effort put into optimizing the performance of current CPU architectures represents an enormous barrier to entry for a new instruction set. Intel itself has not made much headway with Itanium, unable to successfully compete with its own x86 products. A decade ago RISC was hailed as the superior alternative, but x86 now stands over the dead bodies of several of its erstwhile RISC competitors: Alpha and PA-RISC, for a start. Modern CPU instruction sets are pragmatically extended with new opcodes as needed, witnessed by the sheer number of times Intel and AMD have added more vector instructions to their x86 implementations.

Also (and crucially) CPU architectures so specialized as to only run code from a single programming language tend not to survive. There is a reason that Lisp Machines and the P-system CPUs no longer exist: they weren't terribly adaptable.

So I won't be suggesting a radically new instruction set.

Exploring the problem space

As I see it, there are three standout features of various high level languages which one might attempt to optimize for in the CPU design:

dynamic typing: Type checks are performed at run time, not compile time like C or Java
stackless languages: like Erlang, to support astonishing numbers of threads
functional languages: functions have no side effects and there is no global state. The complete state a function operates on will be passed to it, by value not by reference

For #1, Dynamic Typing: I don't think pushing type information down to be directly visible to the CPU is really productive. I'm quite likely wrong in this (there have certainly been a large number of processors over the years with tagged arithmetic operations), but I'm also not really qualified to comment further. So I won't.

For #2, Stacklessness: Many CPU designs have precious little hardware dedicated to "the stack." For example, in MIPS32 by convention two registers are used to store sp and fp, but they are really just normal registers and the compiler uses regular ADD/MOV/etc instructions to adjust them. Other CPU families may have more hardware supporting the concept of a stack, but I just don't think there is much to be gained by removing it. There is also a whole lot to be lost, if it is no longer possible to run stack-based languages like C.

For #3, Functional Languages: I believe this is the topic which has the most traction, and is where we'll focus for the rest of this writeup. Passing a large footprint of arguments by value implies a great deal of copying. Of course the runtime for these languages make efforts to avoid unnecessary copies, but perhaps modifications to the CPU can help the runtime perform this function more efficiently.

Avoiding unnecessary copies

Though the programming model for a functional language may guarantee each function call receives its own independent copy of all arguments, in implementation the runtime will avoid copying large amounts of data unnecessarily. If a function only reads and never writes an argument, it can be allowed to reference the parent's copy of the argument. The crucial bit, of course, is ensuring that there is no code path which results in writing to the parent data.

If the functional language compiles down to machine instructions, then any possible code path which results in modification of an argument makes it unsafe to reference the parent data. Even if the language is implemented by a VM, there is overhead in checking each store bytecode at runtime to ensure its target is allowed.

In other problem spaces there is a well-understood technique for optimistically allowing a child a read-only reference to the parent's data: Copy On Write. The relevant pages of memory will be mapped read-only. If a process attempts to write to this page it will trap into the operating system, which will make a private copy of the page for the process to modify. If Copy on Write were available, the functional language runtime would have another option available.

The trouble with applying existing Copy on Write mechanisms to functional languages is the sheer frequency of mappings. The current uses of Copy on Write are infrequent: process creation, periodic (but rare) snapshots of data, etc. The overhead of calling into the Operating System to change page tables is acceptable for these uses. The overhead of calling into the OS to change page tables for every function call would likely be prohibitive.

Overview of the proposal

"There is no problem in computer programming which cannot be solved by an added level of indirection." -- Dr Maurice Wilkes

64 bit CPUs are now the norm in the general purpose computing market. This is a truly staggering amount of virtual address space. If the application code could manage a section of its own address space with very low overhead, it could create and destroy mappings as needed. For cases where it makes sense, the language runtime could set up a read-only alias mapping of the parent data, and pass the alias address to the function. If the function attempts to modify its arguments there would be a trap, and a copy could be made.

Before delving further lets examine when it makes sense to do this:

if the function cannot possibly write to its arguments, and the runtime can be certain of this, there is no reason to create an aliased mapping. Just pass in the parents data.
if one or more of the arguments to the function are relatively small, just copy them. The brute force solution is cheaper than trying to finesse it.
if the function might modify its arguments and they are large, we have a candidate for an aliased argument.

What would the hardware need to provide, the Gentle Reader might ask? Nothing much really, just a second MMU TLB. Simple. Ok, I kid, thats actually an enormous burden to place on the hardware, but I think it might be worthwhile. This is how I think it would work:

I'll refer to the new TLB as the Aliasing TLB, which is looked up first. I'll refer to the existing MMU as the System TLB.
The CPU has a pair of limit registers, giving an upper and lower bound of addresses to be looked up in the Aliasing TLB. Most processes would probably not use the Aliasing TLB at all, and the limit registers would be zero.
Applications using this mechanism would be given a section of their address space to manage - an exabyte should do. Whenever there is a context switch, system code (i.e. the kernel) updates the limit registers for the new running process.
Memory operations whose target is within the range of the limit registers would be looked up in the Aliasing TLB. We'll come back to the miss case later, for now assume an entry is found.
The result of the Aliasing TLB lookup is a mapping to another virtual address, plus permission bits.

If the permissions allow the operation, the CPU now has a new virtual address to use as the target of the memory operation. This new virtual address (labelled Va in the diagram) proceeds down the "traditional" CPU MMU path, searching the System TLB to find the physical address. If the original target address was not within the range of the limit registers, then the unmodified virtual address goes to the System TLB to be translated to a physical address.

Handling a miss

Everything is fine and dandy if the CPU finds a matching entry in the Aliasing TLB, but what if it doesn't? I'm very fond of software-managed TLBs like MIPS and Sparc v9, and had initially written up a section on how the CPU could directly vector over to a TLB miss handler in the application's address space. The handler would need to be locked into memory so it could never be paged out, and immediately switch to a pre-allocated stack specifically for TLB handling, and ... yeah, it was really complicated.

On further reflection, I don't think it needs to be that complicated. There are two characteristics of the Aliasing TLB which are different from the System TLB: entries are added to the Aliasing TLB immediately before they are used, and the entries only live for the span of one function call - generally speaking, a very short lifespan.

When the OS adds a new entry to page tables the new entry is generally not immediately added to the System TLB, instead it will be added the first time the TLB faults on the new address. With the Aliasing TLB, when a new entry is added it should immediately be pushed into the hardware before resuming processing. We're expecting to immediately hit that address, and the number of Aliasing TLB misses would be dramatically reduced by doing so. Perhaps the misses which remain can take a more normal path of trapping into the OS, which would perform an upcall to the application to service the Aliasing TLB miss.

Page sizes

Function arguments can be of any size and alignment, and may not be aligned to any particular boundary. An earlier draft of this posting proposed segmented memory support, to handle arbitrary argument sizes. On further reflection, I don't think it needs to be that complicated. The Aliasing TLB mechanism only makes sense for relatively large arguments, and I think it is a reasonable tradeoff to require the runtime to pad such arguments to be an even multiple of a page size.

I do think it is important to support multiple page sizes, with the normal page size of the System TLB as a lower bound and truly enormous pages at the upper end. CPU MMUs have supported multiple page sizes for a long time, though Operating Systems generally only use one size for all memory pages. This is to avoid the complexity of fragmentation if one tried to actively page out memory with multiple page sizes in use. Some OSes do use large pages to map in things which can never be paged out, like the framebuffer.

Page replacement is not a concern for the Aliasing TLB: it is mapping one virtual address to another, there is no concept of removing a page from memory. If we have a 128 Megabyte argument to map, we might as well use a 128 Megabyte page to map it. Assembling a bunch of small mappings to handle a huge region is only beneficial in very specific cases. The software will take advantage of multiple page sizes in the Aliasing TLB.

Miscellaneous notes and drawbacks

The most serious downside of the Aliasing TLB is the latency it adds to instruction processing. To hide that latency the CPU will need additional pipeline stages, possibly many additional stages. Nobody wants a repeat of the SuperPipelineing of the Pentium IV, the additional pipelining may be a fatal drawback of this idea.
We'll need Address Space Identifiers (ASID) for the Aliasing TLB. The OS must populate the ASID of the currently running process in a CPU register, and any mappings created by the user code must inherit this ASID. If we allow application code to supply the ASID we'll destroy the security of the system: it could set up nearly arbitrary mappings in another process.
The map addresses in the Aliasing TLB are always looked up in the System TLB, never recursively looked up in the Aliasing TLB even if they fall within the specified range of addresses. I do not believe multiple levels of indirection add any capability to the mechanism, and the hardware complexity in the pipelining would be prohibitive.
I don't think it is reasonable to expect application code to deal with page coloring, so a CPU implementing an Aliasing TLB should use physically indexed caches (or some other solution which does not burden the software with coloring). This is probably not an issue, I believe page coloring has not been employed by any common processor for about ten years. A long time ago I worked on software for a Sparc processor which required it, and still bear the scars.

The disclaimer

Would an Aliasing TLB really boost the performance of a functional language runtime, and by how much? I've no idea. That is the sort of question best answered by an analysis of the behavior of existing functional language runtimes. Analyzing instruction and memory traces is the seventh most boring task in all of computer science, which means it is very, very boring. Since I'm writing this for a blog post, I choose to skip the boring and tedious stuff in favor of emphatic handwaving.

I'm not sure I've actually addressed the challenge Yossi issued. He was pretty clearly seeking CPU instruction set ideas, and I haven't provided any. Also the challenge was issued in late January and subsequent comments indicate it is pretty much wrapped up, so I'm late to the party. Nonetheless it was interesting to write this up, so to me the time was well spent.

Four Circles of Product Management Hell

2008-04-27T21:36:00.000-07:00

I typically work on software for hardware platforms, where the design cycle is considerably longer than that of a desktop or web application. 18 months for a new platform is not uncommon, and it is important to nail down the main feature set early enough in the process for the hardware capabilities to be designed in.

Nailing down these requirements is the job of the product manager, and at this point in my career I've worked closely with about a dozen of them. They generally approach the requirements definitions using a similar set of techniques:

visit current customers to find out what they like and dislike about the product, and what they need the product to do
visit prospective customers to get first impressions and feedback
work with the sales teams to break down barriers to a big sale (which can mean one-off feature development if the deal is big enough)
keep track of what the competition is doing
generally stay abreast of where the market is going

Over time my opinion of what constitutes "good product management" have evolved considerably. I'll give a few examples that portray what the younger, naive me thought of a particular style of product management versus what the older, cantankerous me thinks.

1. All requirements generated directly from customer requests

What I used to think:
"Wow, this is great. These are all features which obviously appeal to customers. We won't waste time on stuff that nobody will ever use, everything we develop will help sell the product."

What I now realize:
This is "Building Yesterdays Technology, Tomorrow!" Customers will ask for improvements and extensions to the existing functionality of your product, and that is fine. When a customer asks for something completely new, it is generally because they can already buy it from a competitor. In fact if the input is via an RFQ they are probably trying to steer the deal to that particular vendor by putting in a set of criteria which only that one vendor can meet. The competitor likely helped the customer put the RFQ together, as any good salescritter can supply a list of specifications which only their product can meet.

Certainly, there will always be a healthy amount of catch-up requirements in any ongoing product development. Competitors are not sitting idle, and they're probably not incompetent, so they will come up with things which your product will need to match. Any product manager will end up listing requirements which simply match what competitors already have.

However there must also be a significant amount of forward-looking development as well, building the product to meet anticipated features which the customer does not yet realize they need. Constantly playing catchup only works for companies in truly commanding (i.e. monopolistic) market positions.

2. Requirements list both externally visible behavior and internal implementation details

What I used to think:
"Umm, ok. Its a little weird that the product requirements are so detailed."

What I now realize:
The product manager believes themself to be a systems architect trapped in a product managers body. They almost certainly used to be an engineering individual contributor (many product managers come from a hardware or software engineering background). They likely feel they have such a firm grasp of the tradeoffs in developing the product that they can easily guide the engineers in how to proceed.

Also, and I am as guilty of this as anyone: engineers often have little respect for the product manager... and the reverse is true as well. The product manager may be trying to provide a top-level design for the product because they consider the engineering team to be incapable of doing it correctly.

3. Anticipates market needs with uncanny and unfailing accuracy, down to the smallest detail

What I used to think:
"Wow, this Product Manager really knows their stuff. This is great!"

What I now realize:
The company is doomed, because we're in a market which is too easy. We'll have five hundred competitors, who will all build exactly the same product and end up racing to the bottom of the price curve so nobody will make any money. Polish the resume.

The Gentle Reader might ask, "What about the product manager who can analyze a difficult and complex market to generate the perfect product requirements with 100% accuracy?" The answer is quite simple really: such a person does not exist. We developers very much want the paragon of product management to exist, someone who can predict the unpredictable and know the unknowable, in order to satisfy some deep-seated need in our world view. However there is no such thing as omniscience, the best product manager is one who can generate a market analysis which is good enough to get some initial traction and be refined in subsequent updates.

4. Product manager is often not in the office, and only revs the requirements document sporadically

What I thought then:
"Slacker."

What I now realize:
Actually, these are some of the signs of a really good product manager. When kicking off a new product they will spend a lot of time visiting customers and potential customers to gather inputs.

They apply a certain amount of skepticism, filtering and summarization to the raw inputs coming from outside the development environment, but without introducing too much delay. A product manager who passes on new inputs every time they meet with a customer or return from a trade show is not a good product manager, they're just a note taker. A product manager who suffers from analysis paralysis, not wanting to make a call until the correct course of action is absolutely clear, is also not a good product manager. There is a finite window of market opportunity, miss it and you'll find out from your competitors what the right thing to do was.

The best product managers know not to change the requirements too often, or the development team will never finish anything. So they will not be constantly releasing new versions of the requirements spec, and any changes which are made will have gotten enough validation to be credible without taking so long in validation as to be stale.

Unfortunately it is also possible that the reason they are not in the office and don't produce much is because they really are a slacker. Caveat emptor.

Afterthoughts

In fairness, I should acknowledge that the product manager job entails more than just defining the product. As they fit in a role equidistant between engineering, marketing and sales, the product manager is frequently pulled in to handle crises in any of the three areas.

as an expert user of the product, they do a lot of sales demos
they frequently end up training resellers (and customers) on the use of the product
they invariably get sent to all of the boring trade shows
they assist in preparing white papers, sales guides for particular vertical markets, etc

Finally, for a perspective from the other side of the fence I highly recommend The Cranky Product Manager. Entertaining, with a dash of truthiness.

Coding Relic

Post-mortem debugging: core files

Pre-mortem Backtracing

Desperate Bugs Demand Desperate Measures

More Google App Engine - Feedflares

The Target Market is Not Obvious

Exploring Google App Engine

When the Universe Conspires to Prevent Backups

Inadvisable Externing

Blogroll, January 2009

Variable Scoping with gcc

printf-acular

Blogroll, November 2008

The Six Million Dollar LibC

Ode to Enum

Aliasing By Any Other Name

Random Musings on stackoverflow.com

The Good, Bad, and Ugly of Gizmo Construction

[0123456789abcdef]

opensource.mycompany.com

The Control Plane is not an Aircraft

gdb lies to you

More Random Musings on Embedded Filesystems

Random Musings on Embedded Filesystems

The High-Level CPU Response

Four Circles of Product Management Hell