Category: hacking

I suppose I’m old enough now, and the rate of change in computing is fast enough, that I can regale young software developers with I-remember-when stories. You know, the ones that start off like “all of my punchcards were rubber-banded together, but I had neglected to number them…” I’ll spare you the tale of how we used to screen-scrape the mainframes at LargeAirline.com for today; instead you get to read my ramblings on languages-older-than-Go.

Today’s topic is inspired by my reading on LWN about the fact that Emacs is still around, which led me to David Wheeler’s argument that parentheses are why no one uses Lisp and that we can do better. Perhaps so, but I found his plugging of SKILL interesting, since once, long ago, when I was but a fresh young hacker, I spent a rather significant bit of time writing software in this language.

Since you have likely never heard of it, SKILL is a Lisp implementation that is (or was?) embedded in the Cadence suite of Electronic Design Automation products. As I recall, the biggest warts were:

• the fact that you could use C-like prefixing — f(x y) was equivalent to (f x y) — but other constructs, like using parentheses for grouping, behaved as in Lisp (i.e. errored).
• the runtime library used C-like functions, such as printf, fread, etc
• the developer’s manual encouraged using imperative style programming like loops; indeed using recursion instead would usually lead to stack overflows

I typically wrote in the Lisp style and just ignored the C-like features as much as possible. The experience soured me on functional languages forever, which isn’t really fair, because SKILL was particularly bad.

But I’ve often wondered why it was so horrible, and how it came to be that Cadence, a large successful company, selected it as its primary extension language. Of course, almost all EDA software is horrible so the bar is pretty low, but I wondered if this was a case of Cadence not realizing how bad it was, or if it was just historical baggage. Or did a bored programmer just decide one day, “hey, let’s write our own crappy Lisp!” (cf. much of Android).

Luckily, there’s a paper on it to shed some light: “SKILL: A Lisp-based extension language” by E. Petrus, 1993. I snagged a version from behind the ACM paywall, so I won’t post it, but I’ll quote a few interesting bits here.

SKILL was originally conceived as a base language for developing simulation and test description languages… Lisp was chosen as a base language because it lent itself well to an interpreter based implementation and Lisp is a natural choice for code generation and as a meta language. The first implementation was an interpreter based on the Franz Lisp developed at Cadence Design Systems in the mid-1980s.

Fair enough. Mostly historical baggage, partly not-invented-here.

The popular syntax for SKILL is a C-like alternative to Lisp. When SKILL was first introduced, the connection with Lisp was not promoted in electronic engineering circles.

Too bad. Maybe if the same engineers had compared it to an allegedly decent Lisp, they might have demanded better.

Because of the large installed SKILL base, it has been difficult to move SKILL [in the direction of Common Lisp].

Oops.

For the most part, SKILL developers come from a EE background and lack general familiarity with functional languages. As a result, company wide code inspections revealed the need for a high level code analysis tool.

Even Cadence internal staff couldn’t use SKILL.

The paper goes on to describe why extension languages are useful as a component of software-reuse. While I won’t disagree, I find the characterizations of EDA software more an indictment on the state of software development in the industry circa mid-90s. The products I used from Mentor Graphics, Cadence, and so on were just horrendous. Each application was typically a 40 meg, crashy, statically linked executable, in which a lot of functionality was shared between a few other executables that mostly did the same thing but had subtly different missing features (probably in the name of their byzantine licensing strategies).

• ECAD software is too large and diverse to be contained in a single executable
• Need “fire-walls” between products. Separating major products into separate executables reduces the chance of one set of code from corrupting data in another.
• Change control is easier when the software is built separately.
• Independent release of products. Products linked together in the same executable must be shipped together. In separate executables, products can be shipped whenever necessary.

(Shared libraries anyone?)

I think I wouldn’t mind SKILL if it had been a decent Lisp, but unfortunately Cadence got stuck with maintaining their own one-off fork and the software ecosystem that grew up around it. At the EDA firm at which I worked, we were lucky to be a late-comer, which allowed us to use a reasonable extension language: perl. I haven’t kept up with the industry, but I hope others have followed suit.

I have been investigating search trees to see if binary search trees’ memory layout can, in practice, make a large difference in performance. Now that I’ve fixed the bugs in my test application, I can say: yes! The theory here is in so-called “cache-oblivious” algorithms. The idea is that you can use divide-and-conquer algorithms and data structures to exploit locality and ensure that at some point you will be working with the granularity of your memory transfer size (such as the size of a cache line or disk block).

How well does it work? Take a look:

This machine has a 2 meg L2 cache and 32 K L1 d-cache. The size of nodes in this test was 32 bytes, so the L1 cache is blown at 2**10 items, and the L2 cache at 2**16.

With the exception of “base,” the trees are all laid out in an array; “vEB” is the cache-oblivious version in which the tree uses a van Emde Boas layout: the top half of the tree is stored in the array, followed by each of the subtrees in left-to-right order, recursively. Unfortunately, constructing the tree dynamically is rather complicated.

So far I’m just exploring ground that’s already been covered, but I do think this is an interesting class of data structures that hasn’t trickled out into the real world yet.

As a warm up for a research topic I’m doing this semester, I am looking at static search tree performance. Consider the following tree fragment where nodes are numbered according to BFS order:

            1
      2            3
   4     5      6      7
  8 9  10 11  12 13  14 15

The nodes are located in memory wherever malloc() put them. An interesting question is whether a different in-memory layout has better search performance. One possible layout is in an array with the following order: 1,2,3,4,8,9,5,10,11,6,12,13,7,14,15 (this pattern is not original to me).

So far, the answer, surprisingly to me, is: not with this layout. With a benchmark of 10 million searches of a randomly-inserted (otherwise unbalanced) tree, I get:

Original Tree: 77s
Reordered Tree: 87s

The tree searches are exactly the same — only the memory layout changed. I can reduce these numbers quite a bit by using -O2 and reducing the size of tree nodes, but there’s still a consistent net loss to the array ordering.

I suspect my cache-emptying routines don’t, but if not, it will be interesting to see where I made the stupid mistake / mental lapse.

I’m technically on break from school now, although I’m still putting the final polish on one last project. But things have slowed down enough that I can bore you with technical crap again.

There’s an interesting section of TPOP wherein the authors discuss studying the “numerology” of a bug; that is, look for patterns in the data instead of just looking at the code. I’ve had a lot of practice with this idea lately when trying to decipher kernel crashes with nothing but an Oops message to go on (these being much easier than infrequent lockups with no output at all!). It’s quite useful for userspace as well, if you are using a language where memory corruption is a fact of life. To show why, here’s a lengthy anecdote about how I recently used the power of man ascii to find and fix a memory corruption bug in about five minutes while racing to meet a project deadline.

First, some background: in the kernel, linked lists are implemented by embedding the next and previous pointers directly into the linked object, by way of the struct list_node. For example:

struct list_node {
    struct list_node *next;
    struct list_node *prev;
};

/* one item in a list */
struct item {
    int id;
    struct list_node list;
};

/* some other object that has a list of items */
struct bar {
    struct list_node item_list_head;
};

This is a curious construction, but once you get used to it, it’s quite handy — you can embed an object in multiple simultaneous lists without having to worry about the lifetime of void pointers, and without having to malloc container structures all the time. The list code is object-agnostic, operating only on the list_node structures, but of course you need a way to get from a struct list_node back to the object that contains it. For that, there is the container_of macro and friends. These are just C macros that, given the address of the struct list_node, the variable name of the structure, and the type of the item in which the struct is embedded, finds the start of the containing structure with a little pointer arithmetic.

I had implemented a similar set of list routines for a userspace program and started getting weird crashes, so I fired up gdb to see something like the following:

gdb > p *item
$1 = {id = 134269966, item_list = {next = 0x804b008, prev = 0x804b008},
      global_list = {next = 0x72657375, prev = 0x40313030},
      src = "machine.org", '00' <repeats 69 times>}

Had I taken a minute to look at this in detail, I would have noticed that the value of id was quite higher than it should be, and that the leading part of src was truncated. But what jumped out at me immediately was that global_list.next and global_list.prev were obviously wrong pointer values. In Linux on x86, heap addresses are usually above 0x0804b000, and stack addresses are below 0xbfffc000. Clearly, the global_list pointers don’t meet these ranges. However, the item_list.next and item_list.prev addresses looked fine. So either the global list pointers weren’t being initialized, or they were being corrupted somehow. Sometimes that kind of corruption happens if the list pointers aren’t updated properly, causing the code to follow a next pointer into random memory, but then it would be unlikely that the item_list pointers and src had meaningful values. Plus, I unit-tested the list routines and was pretty confident they were working correctly.

My initial theory was that something was overwriting the global_list struct, and the byte values looked to be in the ascii range. So I turned to the ascii(7) man page, which gives you a nice little table of hex ordinal to character value mappings. Looking at the bytes in turn gives: 0x72 = ‘r’, 0x65 = ‘e’, 0x73 = ‘s’, 0x75 = ‘u’, 0x40 = ‘@’, 0x31 = ‘1’, 0x30 = ‘0’, 0x30 = ‘0’. Since x86 is little-endian, this works out to the string “user001@”, which should have been the first part of src. The bug must be where the code filled in the src string. However, that code looked fine. I then decided that the pointer to the entire structure must be offset somehow. Sure enough, when I looked at the surrounding code, I saw something like this:

    struct list_node *n;
    struct item *item;

    for (n = list_start(&item_list_head); n;
         n = list_next(&item_list_head, n))
    {
        item = container_of(n, struct item, global_list);
        /* strncpy and other stuff ... */
    }

Oops. I had passed the wrong list name to container_of(), with the effect that the item pointer was actually 8 bytes prior to the real start of the structure. As a result, the string copy overwrote the pointer values of just one of the list structures, a bug which didn’t actually have a negative effect until later.

There are morals a-plenty, including “macros are evil” and “this is why templates were invented.” Yet, I’ve seen Linus use this technique more than once when others were stuck on a kernel memory corruption bug, so I’ll go with “Kernighan and Pike are always right[1].”

[1] Except, I’m still not sold on using capital letters in Go. Perhaps in time I can be convinced.