Org-mode hack: tasks done last month

I'm a big fan of Emacs's org-mode. Over the past year, I've started using it for everything - tracking tasks, taking notes, and drafting all my reports, papers, and blog posts. Org-mode is the only task-tracking software that I've used for more then a week.

At work, I am required to produce a monthly status report. To automate part of the process, I figured out a way to have org-mode produce a list of the tasks completed during a specific month. Since I couldn't find a similar example through a Google search, I thought I would post my approach for the benefit of others (and as a reminder to myself!).

Below is an example org file containing completed tasks that I'll use to illustrate the approach. The tracking closed items feature has been configured to add a time-stamp when each task is transitioned to the DONE state. The header specifies a category, Foo, that org will associate with all of the tasks in the file.

#+Category: Foo

* DONE Feed the dog
   CLOSED: [2010-04-30 ]

* DONE Mow the lawn
   CLOSED: [2010-05-01 ]

* DONE Take out the trash
   CLOSED: [2010-05-20 ]

* DONE Pay the bills
   CLOSED: [2010-06-01 ]

First, configure org-mode's agenda feature and use the C-c [ command to add the example file to the agenda files list.

At this point, a list of the tasks completed in May can be produced by issuing the agenda tag matching command, C-c a m, and giving it the following match string:

CATEGORY="Foo"+TODO="DONE"+CLOSED>="[2010-05-01]"+CLOSED<="[2010-05-31]"

This should produce the following list (slightly reformatted to fit blog width):

Headlines with TAGS match: CATEGORY="Foo"+TODO="DONE"\
+CLOSED>="[2010-05-01]"+CLOSED<="[2010-05-31]"
Press `C-u r' to search again with new search string
  Foo:        DONE Mow the lawn
  Foo:        DONE Take out the trash

Although this works, entering the search string is a cumbersome task. A better solution would avoid this step.

Agenda provides a way to define custom commands that can perform searches using pre-defined match strings. The following elisp code defines a custom command that performs the above tag search automatically.

(setq org-agenda-custom-commands
  `(("F" "Closed Last Month" 
     tags (concat "CATEGORY=\"Foo\""
                  "+TODO=\"DONE\""
                  "+CLOSED>=\"[2010-05-01]\""
                  "+CLOSED<=\"[2010-05-30]\"")))

After eval-ing this command, typing C-c a F will produce the same list as above without having to enter the match string. This approach is indeed better but uses a hard-coded match string. An even better solution would generate the match string based on the current date.

Although the call to concat in the example above programatically generates the match string, it does so only when the setq is evaluated. If the setq is in an initialization file (e.g. ~/.emacs) the match string will get generated based on the date emacs was started and not the date on which the search is performed. This could produce erroneous searches when using an Emacs instance started before the turn of the month. In such cases, the setq could be manually re-evaluated to generate the correct match string but an automatic solution would be best.

Unfortunately, org doesn't currently support providing a lambda to generate the match string at search time. For instance, this example:

(setq org-agenda-custom-commands
  `(("F" "Closed Last Month" 
     tags
     (lambda ()   
       (concat "CATEGORY=\"Foo\""
               "+TODO=\"DONE\""
               "+CLOSED>=\"[2010-05-01]\""
               "+CLOSED<=\"[2010-05-30]\"")))))

produces the error message "Wrong type argument: stringp, …". Patching org-mode to support lambdas for match strings is an option but I prefer to maintain the stock org-mode code.

Thanks to the near infinite hackability of emacs, it's possible to extend the stock org mode functionality without modifying it directly. The below elisp code defines two new interactive functions that call into org-mode to perform a tag search for a specific month.

(require 'calendar)

(defun jtc-org-tasks-closed-in-month (&optional month year match-string)
  "Produces an org agenda tags view list of the tasks completed 
in the specified month and year. Month parameter expects a number 
from 1 to 12. Year parameter expects a four digit number. Defaults 
to the current month when arguments are not provided. Additional search
criteria can be provided via the optional match-string argument "
  (interactive)
  (let* ((today (calendar-current-date))
         (for-month (or month (calendar-extract-month today)))
         (for-year  (or year  (calendar-extract-year today))))
    (org-tags-view nil 
          (concat
           match-string
           (format "+CLOSED>=\"[%d-%02d-01]\"" 
                   for-year for-month)
           (format "+CLOSED<=\"[%d-%02d-%02d]\"" 
                   for-year for-month 
                   (calendar-last-day-of-month for-month for-year))))))

(defun jtc-foo-tasks-last-month ()
  "Produces an org agenda tags view list of all the tasks completed
last month with the Category Foo."
  (interactive)
  (let* ((today (calendar-current-date))
         (for-month (calendar-extract-month today))
         (for-year  (calendar-extract-year today)))
       (calendar-increment-month for-month for-year -1)
       (jtc-org-tasks-closed-in-month 
        for-month for-year "CATEGORY=\"Foo\"+TODO=\"DONE\"")))

The first function, jtc-org-tasks-closed-in-month, generates an appropriate query string and calls the internal org-mode agenda function org-tags-view. The function defaults to the current month but takes optional arguments for the desired month and year. The function also takes a match-string argument that can be used to provide additional match criteria.

The second function, jtc-foo-tasks-last-month, calculates the prior month and calls jtc-org-tasks-closed-in-month with an additional match string to limit the list to DONE tasks from the category Foo. Executing jtc-foo-tasks-last-month interactively automatically produces a list of the tasks closed in the prior month. For my purposes, this is close enough to the ideal solution. Using the optional match-string argument, I can re-use this solution to search for tasks completed in other categories or with specific tags.

My typical work flow is to archive the closed tasks after my status report is written. Org-mode's agenda makes this an easy task. First I mark all of the tasks for a bulk operation by typing m on each. Then I perform a bulk archive by typing the command B $. This will move the closed tasks to an archive file, typically a file of the same name with an added _archive suffix.

Org-mode is a great productivity tool. Combined with Emacs's hackability, it's possible to create tools optimized for your particular work flow.

Addendum

I found that searching on CLOSED date ranges didn't work in org-mode version 6.34a. The problem appears to be fixed in the 6.36c release so be sure to have the right version if you want to replicate this method.

Recovering Deleted JPEGs from a FAT File System - Part 9

Part 9 in a series of posts on recovering deleted JPEG files from a FAT file system.

A month ago (!), in part 8, we looked at the JPEG file format specification to determine if there was sufficient determinism in the on-disk layout to allow the recovery of deleted files through analyzing the residual data in the file system. The answer was mixed:

1. GOOD: Uniquely valued markers, discoverable through data inspection, identify the beginning and type of the segments that constitute a JPEG file.
2. GOOD: the metadata segments have a pre-defined size
3. BAD: the length of the entropy encoded image data is, to the best of my knowledge, unspecified in the START-OF-SCAN segment header. Instead, an END-OF-IMAGE marker is used to identify the end of the entropy encoded data. The theory is that this is done to allow JPEG files to be written as the image is processed.

Essentially, this means that there is no way to determine through data inspection the length or location of the clusters containing the encoded image data. The only clue available is the END-OF-IMAGE marker at the end of the entropy encoded data.

One option is to discover and analyze latent directory entries in the data area - doing so could provide valuable clues to the start and length of erased JPEG files. The downsides to this approach are added complexity (recovering deleted directory entries) and incompleteness (directory entries for deleted JPEG files may not exist due to reuse).

A simpler approach is to inspect each cluster in the data area to see if it begins with a START-OF-IMAGE marker or contains an END-OF-IMAGE marker. Any extent of clusters bounded by START-OF-IMAGE and END-OF-IMAGE markers stands a good chance of being the data for a contiguous JPEG file - the very kind of file we've been trying to recover in this series. In this post, I'll implement this simple method and test the results. Follow the "Read more" think for the rest of the post.

Wait a moment...

The other day, I posted a lament about modern (popular) programming being mostly a matter of connecting pre-existing components or libraries with minimal work. In the post I stated that I didn't find such work satisfying.

The next day, however, I realized something - I've just spent nearly a decade in advanced development roles happily creating prototypes by modifying and combining pre-existing software components with the minimal possible work. Spot the inconsistency?

This perplexed me - why did I react this way to Mike Taylor's post when I have enjoyed such prototyping work so much?

After some thought, I concluded that my prototype work has involved modifying complex systems. This has required first understanding enough about each system's design and software to determine the minimal changes required to implement the desired functionality. So, although the eventual changes were relatively minor (100s to 10Ks LOC), along the way I had to obtain a deep understanding to complete the task. I think this is the material difference between the prototyping work I've enjoyed and the kind of "library gluing" that I dislike (and Mike of course!). If true, then there is no inconsistency after all.

Clearly the issue isn't black-and-white - the amount of work performed doesn't represent the amount of understanding required. To some degree this reminds me of the Simplicity Cycle - after a certain point, enough understanding is achieved to make the solution simpler, not more complex. From this perspective, I suspect that the satisfaction that I - and perhaps others - seek is the result of crossing that complexity-understanding threshold - this may be the "grokking" point that was easier to achieve in simpler times (e.g. 8bit programming).

Grokking and Modern Programming

For this blog, I try not to repost popular links from high traffic aggregation sites - odds are you've already seen them. But Mike Taylor's comments in this post so resonated with me that I felt compelled to discuss it despite the attention it has received.

While reviewing a classic Commodore64 book, Mike segues into a follow-up discussion to his What Ever Happened to Programming post in which he says:

So I think this is part of what I was bemoaning in Whatever happened …: the loss of the total control that we had over our computers back when they were small enough that everything you needed to know would fit inside your head. It’s left me with a taste for grokking systems deeply and intimately, and that tendency is probably not a good fit for most modern programming, where you really don’t have time to go in an learn, say, Hibernate or Rails in detail: you just have to have the knack of skimming through a tutorial or two and picking up enough to get the current job done, more or less. I don’t mean to denigrate that: it’s an important and valuable skill. But it’s not one that moves my soul as Deep Knowing does.

I found this comment insightful as it made me realize that I have been possibly struggling with the same thing.

For as long as I can remember, I've felt compelled to Deeply Know the systems that I work on. Starting with my own adolescent experiments programming 8bit computers, I've enjoyed diving deep into the machine to understand its fundamental operation and then using that knowledge to grok whole-system behaviors. As Mike states in the post, this was possible to do in the 8bit days due to the simple machines and books providing all of the necessary information (my tome was Your Atari Computer which still sits on my bookshelf as a reminder of those happy times).

Unfortunately, two things have happened since then - machines have gotten more complicated and having a deep understanding seems to be less valued.

The first point is obvious, computers have gotten more complicated on every level - hardware architectures, operating systems, applications, and networking. Although the fundamentals can be learned, obtaining deep expertise in any of these areas requires specialization.

Having spent most of my career working on large-scale, enterprise computing and storage systems, I've experienced the leading edge of this expanding complexity first hand. In my first job, I think I did pretty well at understanding large portions of that machine but it's been a losing battle since then. The systems that I now work with are now so numerous and complex that it's impossible to deeply understand them all - but I try.

Lately, I've been trying to do more hobby projects to have fun, and expose myself to domains outside of work. But in doing so I find that I quickly run into the second point that Mike's What Ever Happened to Programming post captures well - the hero of modern programming is the person that can stitch together libraries in the shortest amount of time in the fewest lines of code. The greatest heroes are those that can create and launch a startup in less than 24 hours while on a bus. That's great but it's not for me - I just don't find this form of programming satisfying.

I've been overly nostalgic lately, hence recent posts on clicky keyboards, old computer books, and old computer commercials. At first, I thought a looming birthday was to blame but Mike's post has me thinking that it's really a reaction to the shift in programming. The kind of work I like to do doesn't seem to be where all the "action" (read capital investment) is.

It's unreasonable to expect the world to revert back to the way things were. Therefore, there are two possible reactions:

1. Deal with it and change with the times
2. Pick a niche were it is possible to "grok" the system and specialize. This doesn't mean building everything from scratch but rather picking a stable domain that allows an accumulated understanding of as much of the system as I care to know.

Traditionally I've been a generalist but I must admit that option 2 seems much more attractive than 1. I guess this is something to reflect on while planning out my future career.

Recovering Deleted JPEGs from a FAT File System - Part 8

Part 8 in a series of posts on recovering deleted JPEG files from a FAT file system.

In part 7, I demonstrated recovering deleted JPEG files through knowing their pre-deletion location in a FAT file system. In the real use-case of recovering accidentally deleted files, the locations are unknown making this approach impossible.

Recovering deleted files without knowing their location requires a method to find them within the unerased data. In this post, I'll show how the structure of a JPEG file can be used to do just that. Follow the read more link for the full discussion.

Recovering Deleted JPEGs from a FAT File System - Part 7

Part 7 in a series of posts on recovering deleted JPEG files from a FAT file system.

After a hiatus due to the holidays, personal matters, and work-stuff I'm ready to continue the FAT Recover project. In this post I'll

• finally demonstrate the two principal assumptions that this project is based on.
• actually recover deleted files using a manual approach.

Follow the "read more" link for the detailed discussion.

But first a mea culpa - I've discovered that the code for long file name support in post 5 is utterly broken. The code works for files that only use a single long file name entry but does not correctly process file names spanning multiple entries. For now, I'll side-step the issue and post a fix at a later time. I'll also update post 5 to warn future readers. Apologies for the error - that's the danger of hacking in the wee hours and minimal unit testing.

Recovering Deleted JPEGs from a FAT File System - Part 6

Part 6 in a series of posts on recovering deleted JPEG files from a FAT file system.

In this post we'll tackle the last major FAT file system data structure - the file allocation table. Compared to the previous post on the root directory, this post is much less complex. Follow the "read more" link for an overview of the file allocation table and the code required to process it.

Recovering Deleted JPEGs from a FAT File System - Part 5

Part 5 in a series of posts on recovering deleted JPEG files from a FAT file system.

UPDATE: 2010/1/28: it's come to my attention that the long file name support code described in this post is broken - it only works for files that utilize a single LFN entry. For the time being I plan to work around this bug for the FATRecover series but I do intend to post a fix eventually. I'll be sure to add another update with a link to the fix when it is available.

The topic of this installment is the root directory and the code required to process it. Although strictly speaking the file allocation table is the next major on-disk area, I think covering the root directory first will make the overall discussion clearer.

Note that this is a watershed post as the "hack" level of the example code increases dramatically. This was unfortunate but necessary to accommodate certain FAT functionality while limiting the discussion's length. That said, readers with sufficient skill should be able to use the example code to create more robust implementations.

Follow the "read more" link for a detailed description of how to read and interpret the root directory.

Recovering Deleted JPEGs from a FAT File System - Part 4

Part 4 in a series of posts on recovering deleted JPEG files from a FAT file system.

Now that we've created a test data set and covered the high-level structure of a FAT file system, it's time to get our hands dirty with some code. Enough talk, more action!!!

Follow the "read more" link for a detailed description of how to read and interpret a FAT file system boot sector.

Recovering Deleted JPEGs from a FAT File System - Part 3

Part 3 in a series of posts on recovering deleted JPEG files from a FAT file system.

The FAT file system was invented in 1980 by Tim Paterson while developing 86-DOS, the precursor of MS-DOS. Since its creation, FAT has gone through a number of evolutions to accommodate growing disk sizes, and provide more capabilities. Although FAT is nearly 30 years old, it remains in common use due to its ubiquitous OS support and simplicity - both important factors for embedded consumer devices like digital cameras.

FAT's history is complex, a retelling could consume an entire series of posts itself. For this project, it is sufficient to know that there are three main variants - FAT12, FAT16, and FAT32 - each successively supporting larger maximum disk sizes. Generally speaking, the on-disk format of all three variants is very similar, so much so that code developed to grok one format can, with reasonable effort, be hacked to grok another¹. In this project, we'll be working with a FAT16 file system which hdiutil can be explicitly requested to create by using the argument -fs "MS-DOS FAT16"².

The following diagram depicts the high-level, on-disk structure of a FAT16 file system (not drawn to scale).

+---------+-------+--------+-------+---------------------+
|   BOOT  | RESV  |   FAT  | ROOT  |  DATA ............. |
|  SECTOR | (OPT) |        | DIR   |  AREA ............. |
+---------+-------+--------+-------+---------------------+
0                                                        N

In computer storage, capacity is divided into fixed sized units called sectors - typically 512 bytes long³. The sector is the fundamental unit for addressing storage and smallest amount of data that can be transferred to/from a disk drive. While older disk drives used an awkward addressing scheme based on physical geometry, newer drives use a linear series of sector addresses.

The first sector (offset 0) of a FAT16 file system contains the BOOT SECTOR which provides critical information about the file system's organization. Optionally, a number of sectors may be reserved after the boot sector (RESV).

The next major data structure is the File Allocation Table (FAT) from which the file system gets its name. The FAT is essentially an array of 16bit elements ⁴ each representing a fixed size portion of the DATA AREA. To minimize the FAT's relative size, each element represents a cluster⁵, a power-of-two multiple number of sectors. In addition to tracking the allocation status of each DATA AREA cluster, FAT elements are also used to store pointers forming linked-lists describing the on-disk location of files and sub-directories spanning multiple clusters.

After the FAT comes the root directory area (ROOT DIR) used to hold the information describing the files and sub-directories at the top of the file system namespace tree. In FAT12 and FAT16, the root directory area is a fixed size which limits the numbers of files and sub-directories that can be stored in it.

The remainder of the disk capacity (DATA AREA) is essentially a heap allocated as needed to store file and sub-directory data. As mentioned previously, use of the DATA AREA is managed by the FAT.

In the next few posts, I'll describe each of these major areas in greater detail and present the code needed to interpret them. By the end, we should essentially have a read-only FAT file system implementation that will serve as the basis for the remainder of the project.

Footnotes:

¹ Here I am ignoring many, many subtle differences and complications. A thorough discussion of the technical details for all of FAT's variants is outside the scope of this series. The curious reader is recommended to read the bountiful information available via a Google search. Brian Carrier's book, File System Forensic Analysis, is another valuable resource (which sadly wasn't available when I first did this project in 2004).

² Note that FAT16 file systems have a minimum supported size - usually 16MB but some tools may allow smaller sizes.

³ Some enterprise level disk drives use a 520 byte sector - the additional 8 bytes are often used to store error checking and recovery information for RAID systems.

⁴ The size of the FAT elements is one of the principal differences between the file system variants. FAT12 uses 12bit entries while FAT32 uses 32bit entries. The FAT element size is one of the factors that determines each variant's maximum supported disk size.

⁵ Other file systems may use the term block instead of cluster.

Recovering Deleted JPEGs from a FAT File System - Part 2

Part 2 in a series of posts on recovering deleted JPEG files from a FAT file system.

Whenever I develop an analysis program I first create a dataset to test and experiment against. In part 1, I mentioned that I used my digital camera to create a test data set for the original project in 2004. For this series of posts, I thought it would be better to use a data set reproducible by others. Two things are required to accomplish this goal:

• A collection of commonly available test images
• A repeatable method for creating disk images of FAT file systems

A Google search for test images led me to this wikipedia page from which I selected the University of Southern California Signal & Image Processing Institute's data set - specifically the miscellaneous corpus. This collection consists of 44 TIFF images of various resolutions ranging in size from 64KB to 1MB (17MB in total). Since JPEG images are needed for this project, I used the following ImageMagick command to do the conversion.

mogrify -format jpg -quality 90 *.tiff

After the conversion, the file sizes ranged from 4.8KB to 350KB (3.4MB in total) - a conveniently sized collection for this project.

In the 2004 project, I used the UNIX dd command to make a disk image of my camera's memory card. However for this project, I wanted a way to create disk images without requiring a physical device. One option considered was to use Linux loop devices but I wanted to use my machine-of-choice, an Apple MacBookPro, for this project - an artificial but important constraint since this is for fun.

After some research, I discovered that Apple's hdiutil utility can create a suitable image using the following command:

hdiutil create \
        -fs "MS-DOS" \
        -megabytes <SIZE> \
        -layout NONE \
        -volname <VOLNAME> <IMAGENAME>

Executing this command creates the file <IMAGENAME>.dmg that is an image of a FAT file system called <VOLNAME> with a total capacity of <SIZE> megabytes. The remaining argument, -layout NONE, prevents a partition table from being added to the image - an unnecessary complication for this project.

The following example illustrates the OS X terminal commands needed to create a 16MB disk image with a single JPEG file on it¹

$ hdiutil create \
          -fs "MS-DOS" \
          -megabytes 16 \
          -layout NONE \
          -volname FRTEST1 frtest1
..................................................
created: /<PATH>/frtest1.dmg

$ hdiutil attach frtest1.dmg 
/dev/disk1             /Volumes/FRTEST1

$ cp images/4.2.04.jpg //Volumes/FRTEST1//

$ hdiutil detach //Volumes/FRTEST1//

Using the selected image corpus and above hdituil terminal commands, a wide variety of test disk images can be created programmatically via shell scripts - just what is needed for this project.

In the next post, we'll start down the path of grokking a FAT file system layout.

Footnotes:

¹ Minor changes were made to the example output to remove machine specific information (i.e. paths) and fit it within the limited size of the post area.

Recovering Deleted JPEGs from a FAT File System - Part 1

Part 1 in a series of posts on recovering deleted JPEG files from a FAT file system.

In 2004, my in-laws returned from a vacation and had all of the pictures accidentally deleted from their digital camera. When I heard the news my first thought was that the data may still be there!

Often, deleting a file only erases its associated file system metadata (i.e. name, owner, etc) - the file's data is left unchanged. As a result, a deleted file can sometimes be recovered by finding the unchanged data fragments and recombining them in the correct order. I reasoned that if their camera took this metadata-only approach then there was a good chance that some of the pictures could be recovered.

Unfortunately, my in-laws lived in another state so I couldn't examine their camera's memory card right away. I suggested that they remove the card from the camera and bring it with them on their next visit so that I could analyze it then.

My initial plan was to try one of the many file recovery tools that already existed. However, I soon began to wonder how hard it would be to write a program to recover the pictures myself. Finding the challenge exciting, I immediately began spending all of my spare time coding up a recovery program.

After one week, and a lot of caffeine, I had a C program capable of recovering deleted JPEG files from a FAT file system - the typical file system used by digital cameras. Using my own camera as a test bed, the program could reliably recover pictures after performing an "erase all" operation. Cool!

Unfortunately, the story didn't end as well for my in-laws. When I finally received their memory card I found that all of the file system data blocks had the value 0xFF - a clear sign that the entire FLASH memory had been erased¹. The data was gone.

Despite the unfortunate ending, this project was one of my favorite spare-time hacks. So much so in fact that I thought it would be fun to recreate it as a series of blog posts. Over the next few weeks I plan to write a series of posts under the label "FATrecover" describing how to develop such a program. By the end of the series, hopefully anyone with sufficient coding experience will be able to write their own FAT file system recovery program.

Footnotes:

¹ FLASH memory, being a form of EEPROM, cannot be re-written directly. Instead, the FLASH memory cells must first be returned to an unwritten state - an operation typically called an "erase". After being erased, the affected memory cells have a value of 0xFF.

C Bitfields and HW Registers

When I need a quick low-level programming "fix", I browse the archives at PageTable.com. Last week I read the post on Readable and Maintainable Bitfields in C which argued the merits of using bitfields over bitmasks+macros. Although I agree with the post's points I think it omitted one important detail - the danger of using bitfields with hardware registers.

Hardware registers can be mapped into a processor's memory space and accessed with standard memory read/write instructions. Therefore the temptation is to define a bitfield type representing a register's structure and set a pointer to its base memory address. For example, assuming register bar is four bytes wide, has five bit-fields, and is located at memory address 0xBAADF00D one might be tempted to do the following:

typedef struct {
    unsigned int f1:8;
    unsigned int f2:4;
    unsigned int f3:8;
    unsigned int f4:4;
    unsigned int f5:8;
  } registerBar_t;


// Set pointer to register's memory address
registerBar_t *pBar = 0xBAADF00D;

// Use pointer to access register
pBar->f1 = 0xFE;

One problem with this approach is that many registers are designed to be accessed only at their full size - all accesses must be aligned to the register's base address and read/write the whole thing. Unfortunately, the setting of f1 in the above example may produce a partial register write that can lead to unexpected and unintended results.

Another challenge when dealing with registers is that, unlike main memory, register accesses can have side effects. Even register reads can cause the hardware to initiate action or clear information. Consider the following example:

...
tmpf1 = pBar->f1;
tmpf2 = pBar->f2;
...

If reads of register bar are destructive causing its contents to be cleared then the read of f1 may clear the contents of f2 before it is read by the subsequent pointer dereference. The resulting loss of information could cause the driver, hardware, or both to behave unexpectedly.

Alternatively, if reads of register bar cause the hardware to initiate action then spurious activity may occur if the f1 and f2 accesses are done separately.

Because of these granularity and side effect issues, I was advised early in my career to avoid using bitfields with hardware registers. This is, I think, an important point that is captured in the PageTable.com post's comments but not in the post itself which is an unfortunate omission.

After reading the PageTable.com post, I realized that I always took this advice on faith and never looked at the instructions generated by bitfield accesses. So I decided to do a quick experiment, below is a short program that accesses a bitfield with fields of varying size and alignment.

#include <stdio.h>

typedef union {
  struct {
    unsigned int f1:8; // Bits 07:00
    unsigned int f2:4; // Bits 11:08
    unsigned int f3:8; // Bits 19:12
    unsigned int f4:4; // Bits 23:20
    unsigned int f5:8; // Bits 31:24
  };
  unsigned int raw;
} bitfield_t;


int main()
{
  bitfield_t bitfield;
  unsigned int tmp;

  bitfield.raw = 0x0;

  // Set bit field f1
  bitfield.f1 = 0xEF;
  tmp = bitfield.f1;
  printf(" After f1: F1(0x%02x) RAW(0x%08x)\n", 
         tmp,
         bitfield.raw);

  // Set bit field f2
  bitfield.f2 = 0xE;
  tmp = bitfield.f2;
  printf(" After f2: F2(0x%02x) RAW(0x%08x)\n", 
         tmp,
         bitfield.raw);

  // Set bit field f3
  bitfield.f3 = 0xDB;
  tmp = bitfield.f3;
  printf(" After f3: F3(0x%02x) RAW(0x%08x)\n", 
         tmp,
         bitfield.raw);

  // Set bit field f4
  bitfield.f4 = 0xA;
  tmp = bitfield.f4;
  printf(" After f4: F4(0x%02x) RAW(0x%08x)\n", 
         tmp,
         bitfield.raw);

  // Set bit field f5
  bitfield.f5 = 0xDE;
  tmp = bitfield.f5;
  printf(" After f5: F5(0x%02x) RAW(0x%08x)\n", 
         tmp,
         bitfield.raw);

  // Set with raw
  bitfield.raw = 0xDECAFBAD;
  tmp = bitfield.raw;
  printf("After raw: RAW(0x%08x)\n", 
         tmp);

  return 0;
}

Compiling and running this program on an Ubuntu system results in the expected output.

jcardent@ubuntu:~/tmp$ gcc -g -o foo foo.c 
jcardent@ubuntu:~/tmp$ ./foo 
 After f1: F1(0xef) RAW(0x000000ef)
 After f2: F2(0x0e) RAW(0x00000eef)
 After f3: F3(0xdb) RAW(0x000dbeef)
 After f4: F4(0x0a) RAW(0x00adbeef)
 After f5: F5(0xde) RAW(0xdeadbeef)
After raw: RAW(0xdecafbad)

Running the command

jcardent@ubuntu:~/tmp$ objdump -d -S foo 

reveals the instructions generated to access the bit-fields. Looking at the f1 write and read sequence shows:

  // Set bit field f1
  bitfield.f1 = 0xEF;
 80483dc:       c6 45 f8 ef        movb   $0xef,-0x8(%ebp)
  tmp = bitfield.f1;
 80483e0:       0f b6 45 f8        movzbl -0x8(%ebp),%eax
 80483e4:       0f b6 c0           movzbl %al,%eax
 80483e7:       89 45 f4           mov    %eax,-0xc(%ebp)

The first thing to note from this disassembly fragment is that bitfield is located on the stack eight bytes below %ebp. Likewise, tmp is located at offset 0xC.

From this example it's clear that the write to f1 uses a single byte move instruction. If bitfield had been mapped to a hardware register, this would have resulted in an aligned but too short write access that could have produced unintended behavior.

The read of f1 is less clear until the movzbl instruction is understood to be a move from a single byte to a word, four bytes in this case. So here again, if bitfield had been mapped to a register the single-byte access may have resulted in unintended behavior like dataloss (top three bytes cleared) or spurious action (if subsequent reads are done to other fields for the same operation).

Looking at the f2 write and read sequence shows:

 // Set bit field f2
  bitfield.f2 = 0xE;
 8048404:       0f b6 45 f9        movzbl -0x7(%ebp),%eax
 8048408:       83 e0 f0           and    $0xfffffff0,%eax
 804840b:       83 c8 0e           or     $0xe,%eax
 804840e:       88 45 f9           mov    %al,-0x7(%ebp)
  tmp = bitfield.f2;
 8048411:       0f b6 45 f9        movzbl -0x7(%ebp),%eax
 8048415:       83 e0 0f           and    $0xf,%eax
 8048418:       0f b6 c0           movzbl %al,%eax
 804841b:       89 45 f4           mov    %eax,-0xc(%ebp)

In this case, setting the four bit-wide field f2 results in a byte-wide read-modify-write sequence aligned with the second byte of bitfield, evidenced by the offset of 0x7 instead of 0x8. Similarly, reading f2 results in a byte-wide read aligned with the second byte of bitfield. Both accesses are too short and misaligned.

Since f3 spans bytes 2 and 3 of bitfield, its access sequence results in aligned, four byte-wide mov instructions.

  bitfield.f3 = 0xDB;
 8048438:       8b 45 f8           mov    -0x8(%ebp),%eax
 804843b:       25 ff 0f f0 ff     and    $0xfff00fff,%eax
 8048440:       0d 00 b0 0d 00     or     $0xdb000,%eax
 8048445:       89 45 f8           mov    %eax,-0x8(%ebp)
  tmp = bitfield.f3;
 8048448:       8b 45 f8           mov    -0x8(%ebp),%eax
 804844b:       c1 e8 0c           shr    $0xc,%eax
 804844e:       80 e4 ff           and    $0xff,%ah
 8048451:       0f b6 c0           movzbl %al,%eax
 8048454:       89 45 f4           mov    %eax,-0xc(%ebp)

Although the accesses themselves are well-formed, unintended behaviors can still result if f3 is only one of multiple fields that must be set for a single operation.

Since the structure of bitfield is symmetrical, the accesses to fields f4 and f5 produce instructions similar to those for f2 and f1 respectively albeit with different offsets.

Finally, the accesses to raw produce aligned, full-width instructions as expected.

  // Set with raw
  bitfield.raw = 0xDECAFBAD;
 80484cd:       c7 45 f8 ad fb ca de movl   $0xdecafbad,-0x8(%ebp)
  tmp = bitfield.raw;
 80484d4:       8b 45 f8           mov    -0x8(%ebp),%eax
 80484d7:       89 45 f4           mov    %eax,-0xc(%ebp)

This last example illustrates a tempting workaround for "safely" using bitfields to manage register accesses. Consider:

registerBar_t *pBar = 0xBAADF00D;
registerBar_t tmpBar;

// Set field f1 to 0xff
tmpBar.raw = pBar->raw;
tmpBar.f1  = 0xff;
pBar->raw  = tmpBar.raw;

While this approach works, it suffers the risk of an uninformed future maintainer "optimizing out" the temporary variable and just using the bitfield method directly. In this regard, it may be more maintainable to use bitmasks and macros for register accesses.

Of course, problems can arise regardless of the method used if "uninformed" developers are allowed to change the code. The only prevention here is to make sure there is suitable training and disciplined code reviews.

Book Review: Coders At Work

Coders At Work: Reflections on the Craft of Programming by Peter Seibel

I really enjoyed this book. Peter Seibel did an outstanding job in selecting a group of interviewees that are both legendary and represent a wide range of programming domains. In addition, Peter's questions were similar enough to allow comparisons between responses but maintained a conversational flow that prevented the interviews from feeling formulaic. Ehud Lamm's quote from the font cover perhaps says it best, "reading this book may be the next best thing to chatting with these illustrious programmers in person".

I read the interviews out of order based on my interests. All were good but my favorite ones were (in no particular order):

• Donald Knuth
• Peter Norvig
• Dan Ingalls
• Guy Steele
• Brendan Eich
• Bernie Cosell
• Simon Peyton Jones
• L Peter Deutsch
• Jamie Zawinski
• Brad Fitzpatrick

One striking observation was how many of the interviewees fit into Malcolm Gladwell's definition of an Outlier. Nearly all of them had opportunities to get a significant amount of programming experience at a young age and serendipitously found jobs that provided the right environment for them to succeed.

I also found interesting the "organic" approach most of the interviewees took to programming. None seemed to rely on formalized best practices but instead used their intuition to tailor their approach based on the task at hand. To me this suggests that you just can't codify great programming which matches my experiences with the great programmers that I have known.

Finally, it's notable how many of the people interviewed either starting out hacking Lisp or were heavily influenced by it. Of course this may be due to selection bias given that the author, Peter Seibel, is a a Lisp hacker himself and wrote the outstanding book Practical Common Lisp. As a Lisp fan, I don't mind the potential bias; it's a feature, not a bug!

The Case of the Bloated Firmware

A few years ago, a co-worker of mine was working on an embedded micro-controller for a proprietary enterprise class motherboard. I don't recall the exact details but my recollection is that the micro-controller was responsible for monitoring a group of sensors and reporting any anomalies.

My friend used a commercial C compiler to develop the code for the micro-controller which compiled fine but resulted in a binary that was too large for the device's EPROM. He tried a number of things to reduce the binary's size but was unable to get the code to fit. During a serendipitous hallway conversation he asked if I could take a look at the problem and we returned to his cube on a mission to shrink the binary.

First, he walked me through the source code to explain the overall purpose and design. At the C level the code looked fine so we next took a look at the disassembled binary and found our first clue - one of the for loops seemed to generate an excessive amount of instructions. Strange.

Again, the exact details escape me but the code in question looked roughly as follows:

 1:  int value1[NUM_SENSORS];
 2:  int value2[NUM_SENSORS];
 3:  int value3[NUM_SENSORS];
 4:  
 5:  for(sensor_num= 0; sensor_num < NUM_SENSORS; sensor_num++) {
 6:  
 7:    value1[sensor_num] = readSensorValue1(sensor_num);
 8:    value2[sensor_num] = readSensorValue2(sensor_num);
 9:    value3[sensor_num] = readSensorValue3(sensor_num);
10:  }

What we observed was that each of the array references resulted in a lot of instructions to compute the specified element's memory address. Since the loop body included three references, it generated a lot of instructions. Matters were made worse by the fact that there were multiple loops of this kind in the code. We found our culprit.

To work around the problem, I suggested that he re-write the code as follows:

 1:  struct {
 2:    int value1;
 3:    int value2;
 4:    int value3;
 5:  } sensors[NUM_SENSORS];
 6:  
 7:  for(sensor_num= 0; sensor_num < NUM_SENSORS; sensor_num++) {
 8:  
 9:    sensors[sensor_num].value1 = readSensorValue1(sensor_num);
10:    sensors[sensor_num].value2 = readSensorValue2(sensor_num);
11:    sensors[sensor_num].value3 = readSensorValue3(sensor_num);
12:  }

We changed the loops, recompiled the code, and presto chango the binary was small enough to fit!

A quick look at the disassembly confirmed my hypothesis that writing the code as proposed would result in only a single array element address calculation in the loop body - the address of each structure member was just an offset from the array element's starting address. The array element address calculations were still inefficient but we had reduced their number enough for the binary to fit within the device's EPROM. Success!

Overall, this wasn't a particularly difficult problem and didn't take that much time to resolve. However, the necessity to imagine how the compiler would respond to restructuring the code made this a fun, and memorable "bug" to work on.

Dan Weinreb Talk at Google

In August, Dan Weinreb gave an interesting talk at Google on ITA Software's high-performance transaction system for airline ticket searching and pricing. ITA's software serves as the foundation for more well known travel pricing services like Orbitz who is an ITA customer. The problem ITA attempts to solve is extremely complex as explained in this slideument by Carl de Marken.

Amongst the Lisp community, ITA is famous for the signficant use of Lisp in their system, hiring well-known Lisp hackers, and using programming puzzles to filter job applicants.

Given my deep interest in all things Lisp (programming, lisp-machines, A.I., etc), Dan's blog is one of my favorite websites and someday I hope to meet him at a Boston Lisp Users meeting (if I can ever make it to one again).

Nice talk and worth watching if you're interested in this kind of thing.

The Case of the Replayed Queue

A number of years ago, I wrote a Linux device driver for a host bus adapter (HBA). The interface to the HBA consisted of two circular buffers, one to send information to the HBA (TxQ) and another to receive information from the HBA (RxQ). In this particular project, the HBAs were being used in a non-standard way to implement a bi-directional communication link between two Linux systems. As a result, the driver sent both commands and responses via the TxQ and received both commands and responses via the RxQ. In both cases, the driver communicated with the HBA using fixed-size data structures called IO control blocks (IOCBs).

Another aspect of this non-traditional use of the HBAs was that a proprietary upper layer protocol was used instead of the standard protocol used with the HBA. In this case, the protocol command packets did not fit within a single IOCB. As a result, two IOCBs were needed to send and receive command packets between the driver and HBA. These IOCB pairs were required to be adjacent in the circular buffers.

As the project reached the beta-testing phase, a perplexing driver bug began manifesting during QA testing. The failure was extremely rare happening only once a day while under heavy load. Unfortunately, the unit-test I had created to test the driver ex-situ continued to run without error so the problem was only occurring in-situ in QA'a full system configuration and under their heavy load. Oh bother.

Faced with a difficult bug and a nearing deadline I got straight to work on figuring out the problem. To start, I reviewed the QA logs to determine a pattern to the failures. The evidence suggested that the driver was re-processing protocol packets that had already been handled. To me this indicated a potential problem with the RxQ circular buffer but a code-review didn't reveal any obvious bugs.

I proceeded on to debugging the driver in-situ. Unfortunately, for reasons that I can't recall, I had little success using a kernel debugger. As a result, I initially tried to use print statements but the verbose system messages generated by the failure caused the information to immediately scroll off the screen. I tried sending debug information out a serial port but this slowed the system down enough to significantly increase the time between failures beyond practicality. Hmph.

After a week of frustration and an increasing pressure from the team to resolve the bug, I decided to take a fresh view of the problem. First, I considered what could cause the driver to replay the RxQ and quickly concluded that erroneously putting the tail-pointer past the head-pointer could cause the problem. A quick review of the head-tail pointer management code didn't reveal any mistakes. Hmph.

Next, I considered how the head-tail pointer code could be tricked into putting the tail pointer beyond the head. I reasoned that one way this could happen was if the driver thought the contents of the circular buffer were longer than its actual size. If this were the case, then when the driver updated the tail pointer it would put it past the head which would erroneously make the circular appear full when the driver re-examined it. But what could make the driver think that the buffer contents were longer than they actually were?

After some deep pondering the problem hit me, it must those multi-IOCB commands! My thought was that if for some reason the second of the two IOCBs wasn't posted to the queue when the driver processed it and if the driver didn't check for this condition, that the driver would adjust the tail pointer as if the second IOCB was present which would put it after the head pointer. The timing window for this seemed to be impossibly small but the failure was taking a day to manifest under heavy load so it had to be a rare sequence of events. If there is one thing that I have learned from my years working on large-scale parallel computer systems it's that highly improbably events occur far more frequently than one suspects.

I checked the code and confirmed that I had failed to account for incomplete multi-IOCBs. I added the necessary guards to the code, gave a new binary to QA, and crossed my fingers. A few days later success was declared and from then on the driver performed without error.

I never figured out why the HBA was delayed in posting the second half of the protocol command IOCBs to the RxQ. But you can be sure that I'll never forget to check for circular buffer fragments again!

The Case of the Errant DMA

The C++ puzzle that I posted about the other day got me thinking of various bugs that I've helped root-cause in the past. I thought it would be fun to post about some of the most memorable ones as a series of posts tagged as BugHunts.

About a year ago, a programmer that I was mentoring ran into a problem with errant DMAs in a ATA device driver that he was writing for a proprietary operating system (mostly as a training exercise). Said programmer did his initial development in a virtualized environment (i.e. virtual machine running on a hypervisor) and the device driver worked just fine. However, when run on a real platform the second and subsequent DMA operations would access "random" memory locations instead of those specified in the supplied scatter-gather lists.

After confirming that the basic scatter-gather code was working properly, the developer asked if I could help identify the problem. I started off by asking him to walk me through how the DMA operations were supposed to occur. Next, we walked through the code to ensure that it matched his description. Not seeing any obvious bugs, we then proceeded on to running the code, breaking into the debugger, and inspecting the scatter-gather lists to make sure that they contained the correct source/destination addresses. We observed the first DMA operation, which always worked, and the subsequent operations, which always failed, but saw no differences between the two. Humph.

At this point, I suggested that we focus on the fact that the first operation always succeeded but the subsequent operations always failed. I asserted that there must be a difference between how the first and subsequent operations were set up. So again we inspected the code and watched the execution in the debugger but didn't see any differences. Double humph.

After some thought, I then hypothesized that perhaps the first DMA operation was unexpectedly altering settings that were setup during the device driver's initialization. Since these setup operations were performed outside of the DMA setup code, we wouldn't observe any execution differences between the first and subsequent operations. So again we walked through the DMA operation but this time considered the additional configuration settings that they depended on. Bingo.

The chipset in question used a memory resident scatter-gather list. Since only a single DMA operation was outstanding at any time (per ATA channel) the developer pre-allocated the memory region during the device driver's initialization and wrote the region's base address to the appropriate chipset register. Since the same memory region was re-used to hold the scatter-gather list for each operation, the developer didn't re-write the base address to the register for each operation.

It turned out that on the virtualized platform the emulated ATA chipset left this register unchanged between operations, hence the device driver worked fine. However, on the real platform the chipset modified the register to point to the active scatter-gather element as the DMA operation was performed. As a result, the first DMA operation completed OK while all subsequent DMA operations walked off the end of the scatter-gather table and misdirected the DMA accesses based on the random data present in memory above the scatter-gather table. Once the developer added the code to re-initialize the scatter-gather base address register for each operation everything worked fine.

After the bug was fixed, the developer stated that he found this behavior surprising. I explained that having worked on designing ASICs in the past, I wasn't at all surprised that the hardware reused the register to hold the address of each scatter-gather element as the operation progressed; all's fair in ASIC design when it means saving some gates!

He then wondered how he could find such bugs in the future without having similar low-level hardware experience. I told him that the important lesson from the exercise was that once the possible errors have been ruled out you need to suspend disbelief and begin considering the impossible errors. Often our understanding of complicated systems is incomplete or flawed, therefore things we assume to be impossible may in fact be possible and therefore must be considered. I explained that this is a skill that must be hard-won over time through solving progressively harder bugs. I encouraged him to seek out hard bugs, spend time trying to resolve them on his own, but if stuck to utilize the already hard-won experiences of his mentors to accelerate his own skill development. This is the advice that has worked for me during my career and I am confident that the developer in question will do just fine.

Anyway, this particular bug was fun because it required thinking about how the system affected the program rather than how the program affected the system. These kinds of puzzles are always fun… after you've figured out the problem that is.

Fun C++ Problem

Today a co-worker of mine ran into an interesting C++ inheritance problem that perplexed the usual lunch crowd. Some might call this a character flaw, but when presented with puzzles like this I feel compelled to figure them out. So, when I got back to my desk I reduced the problem to the following minimal program and got to work on figuring out the root-cause.

 1:  class Superclass
 2:  {
 3:  public:
 4:    void  foo(int aParameter);
 5:    void  foo(int  oneParameter,
 6:              int  twoParameter);
 7:  };
 8:  
 9:  class Subclass : public Superclass
10:  {
11:    void  foo(int aParameter);
12:    // inherits foo(int, int)
13:  };
14:  
15:  void Superclass::foo(int aParameter)
16:  {}
17:  
18:  void Superclass::foo(int  oneParameter,
19:                       int  twoParameter)
20:  {}
21:  
22:  void Subclass::foo(int aParameter)
23:  {
24:    foo(aParameter, 2);
25:  }
26:  
27:  int main(int argc, char * argv[])
28:  {
29:    return (0);
30:  }

In words, there is a super-class, Superclass, with an overloaded method, foo(), that has two variants - foo(int) and foo(int,int). In addition, there is a sub-class, Subclass, derived from Superclass that redefines the foo(int) variant but inherits Superclass's foo(int,int) method.

Straight forward, right? Nope.

$g++ borked.cpp 
borked.cpp: In member function ‘void Subclass::foo(int)’:
borked.cpp:26: error: no matching function for call to ‘Subclass::foo(int&, int)’
borked.cpp:24: note: candidates are: void Subclass::foo(int)

For some reason the compiler isn't able to resolve the call to the inherited foo(int,int) when called from Subclass's foo(int) method. How strange.

Commenting out the offending call on line 24 allows the program to compile and dumping the symbol table yields the expected results:

$nm a.out
0000000100000ea4 s  stub helpers
0000000100001048 D _NXArgc
0000000100001050 D _NXArgv
0000000100000e60 T __ZN10Superclass3fooEi
0000000100000e6e T __ZN10Superclass3fooEii
0000000100000e7e T __ZN8Subclass3fooEi
                 U ___gxx_personality_v0
0000000100001060 D ___progname
0000000100000000 A __mh_execute_header
0000000100001058 D _environ
                 U _exit
0000000100000e8b T _main
0000000100001020 s _pvars
                 U dyld_stub_binder
0000000100000e24 T start

All the methods are present and have unique signatures. Recompiling with the -fdump-class-hierachy option also doesn't produce any suprises - there is no vtable magic going on.

$g++ -fdump-class-hierarchy borked.cpp
$cat borked.cpp.002t.class 
Class Superclass
   size=1 align=1
   base size=0 base align=1
Superclass (0x1407c18c0) 0 empty

Class Subclass
   size=1 align=1
   base size=1 base align=1
Subclass (0x1407c1930) 0 empty
  Superclass (0x1407c19a0) 0 empty

As a final piece of the puzzle, fully qualifying the call to foo(int,int) as follows resolves the problem.

void Subclass::foo(int aParameter)
{
  Superclass::foo(aParameter, 2);
}

Now, I am no C++ guru but I do have a fair amount of experience with it - mostly from writing system level code for a proprietary RTOS that was written in C++. In fact, I wrote a loadable module framework for that RTOS that included a runtime dynamic linker capable of handling C++ intermediate object files. So, I'd like to think I have a decent knowledge of the C++ object model and yet this problem made little sense to me.

As is often the case, I didn't know the anwser to the problem but I did know enough to determine the right keywords to Google for the answer. The solution is to add a using declaration to the Sublcass's definition.

class Subclass : public Superclass
{
  using Superclass::foo;

  void  foo(int aParameter);
  // inherits foo(int, int)
};

As I now understand the situation, when a set of overloaded methods span the base and derived classes, the using declaration is required to introduce the base class's methods into the scope of the derived class. Without the using declaration, the compiler can't resolve the reference to the base class's method without fully qualifying it. Good to know!

I had a lot of fun figuring this out despite the fact that it took 20 minutes of time out of an already busy day. But, sometimes you just have to let the inner-geek exercise itself!

As an aside, I recommend Stanley Lippman's book Inside the C++ Object Model to anyone interested in learning the inner workings of the C++ object model.