Hood me!

I successfully defended my dissertation thesis yesterday, thus overcoming the final hurdle to the Ph.D. other than some paperwork and formatting/publishing the thesis itself. The title of my thesis is "Operating System Support for Shared Hardware Data Structures" and it spans a range of computer science topics from low-level computer hardware—not quite circuits, but close—up to application software and everything in between. I'm pleased with both the scope of the work, the technical contributions, and the outlook for carrying this work forward. I chose to find and pursue a topic that interested me, and my advisors (and wife!) were flexible enough to permit me to do so. It feels great to take the seed of an idea through germination and see it begin to grow.

Critical Bugs and Quality Assurance

Sebastian Huber recently posted a nasty RTEMS bug and fix. While simple, the bug manifested in their application as an increase in one task's latency from 20us to 170us! The cause of the problem was that RTEMS has two kinds of critical sections—dispatch and interrupt—and new SMP-aware code added a dispatch critical section to the thread dispatch code. The problem happens with overlapping a traditional interrupt disable critical section. The SMP dispatch code looks like:

void _Thread_Dispatch(void) {
  Thread_Disable_dispatch();
  SMP_Dispatch_other cores();
  Interrupt_Disable();
  ...
  ... do things, including context switch if needed
  ...
  Interrupt_Enable();
  // problem here!
  Thread_Unnest_dispatch(); // enable
  ...
}

The problem is that an interrupt can occur between Interrupt_Enable and Thread_Unnest_dispatch. Suppose a low-priority task (L) is executing _Thread_Dispatch, and the interrupt enables a high-priority task (H), but
H will not be dispatched because dispatching is disabled. Instead L enables dispatching and resumes executing, which is a priority inversion!

The fix reverts the changes made for SMP. For the SMP code, the priority inversion still exists and is unresolved. (RTEMS currently does not make real-time guarantees for the SMP support, so no one cares yet.)

In the broader picture, the bug seems like it should be easy to detect. The issue with free open-source software (FOSS) is that quality assurance (QA) is almost non-existent: the "many eyeballs" philosophy argues against QA. But what else can FOSS do? No one is going to pay for extensive testing, and if they do they have no incentive to share.

FOSS communities (and corporate developers) need better tools for software QA. This summer RTEMS had a GSOC student who was looking at testing. Testing is probably the first tool in the QA toolbox, and the only one most developers have a clue about; how about static analysis, path coverage, standards conformance, or certification? Some interesting work modeling, proving, and certifying systems is out there: Where is the undergraduate textbook and course on QA?

Web site update

Last night I decided to provide an html version of my CV, and then I remodeled my website. The old version was ugly and broken; the main problem were my iframes. I simplified the design, tried to make it mobile-friendly, and reduced the content. I kept my basic design elements (boxes), and tried to eliminate cruft. I think the product is leaner and cleaner.

Version control for text/LaTeX?

I often use version control (VC) for text documents—especially LaTeX. Modern VC software is good for code, and even text when working alone, but collaboratively editing text with VC is a nightmare. The biggest challenge for text VC seems to be structure/formatting. Code is well-structured within and between lines: text less so. Words/sentences can be re-arranged within sentences/paragraphs, and lines are meaningless. With VC, line wrapping propagates small changes and frustrates reviewing and merging.

Word processors track revisions, but such tools are restrictive and won't work for markup languages. Cloud tools for collaboration such as Docs exist, including some for LaTeX, but requiring connectivity while editing is a non-starter for me.  I would even be happy with a custom LaTeX solution; the features I desire for text VC are similar to those for code:

• Non-proprietary, application-agnostic, platform-independent FOSS
• Revision history: see what has changed.
• Revert: undo changes back to forever.
• Lock-free: work in parallel, which requires...
• Pain-free merge: help resolve conflicting commits.
• Distributed and offline editing: no active (server) connections
• External contributions: integrate changes made outside of VC

Most VC tracks changes either with changesets or snapshots. Changesets seem worthless because of the structural problems of text. Snapshots seem viable, but I haven't seen turn-key solutions for plain text or LaTeX, and handling external contributions seems especially troublesome.

GSOC2012: MMU project and musings

I finally made a pass at merging my student's final code for his GSOC2012 project. The project was the culmination of multiple summer projects and some work I did. I'm excited to try improving it to add sparc64 support and use it in my research.

While revising the student's submission for reviewing and merging, I thought of a few ways to improve future new developer participation:

• Better github integration. Staying up-to-date with rtems.git, tracking student progress, and getting code review from more developers would be helpful for quicker turnaround on submissions.
• Style: documentation and code conventions. Clear, consistent guidelines and examples of proper/improper coding style would make reviewing and merging a lot easier.
• Improved Git Workflow. Teaching students how to make useful branches and commits ahead of time would ease code merging, testing, and revising.
• More submissions. We need to get code reviewed if not merged in smaller increments; this need is well-known and repeated.

These improvements could be addressed in part when students/developers are new to the scene. For example, instead of just making students prove they can build RTEMS and patch hello world, we could require them to document and fix the style of sample code using a branch, and submit a pull request for RTEMS github that contains their proof as separate commits on the same branch.

For getting students to submit and be reviewed more often will take more work on behalf of mentors, developers, and students. Something that may help would be requiring code review as part of the weekly status meetings we instituted this GSOC. Perhaps each student's weekly commits can be reviewed by their mentors as part of tracking progress and status.

Institutional support from RTEMS mentors and developers would help. For example, github integration requires developers and mentors to use github. Style consistency requires a style guide that we accordingly maintain and abide by. Teaching good workflow, and fixing the bad, takes effort: mentors need to (know how to) identify and correct a student who struggles. Increased submission frequency requires urging and commitment from mentors to review code. These improvements take effort, but I think they could substantially improve the participation, progress, and production of students.

My fall hiatus

I've been busy lately, between child-rearing and working on a grant proposal, and I haven't had the time and energy for much else. I'll be writing my thesis soon, too, but that might encourage me to write more here. Meanwhile, check out some fake ads for programming jobs.

Making and freezing food in bulk

My mom and one of my brothers visited my wife and me this past weekend in order to deliver the cradle—we're expecting a baby girl at the end of this month—made by my father-in-law. We decided to take advantage of this visit to prepare some frozen food to ease transitioning into parenthood. For about a day-and-a-half we cooked and froze one or more of the following meals to produce about 20 frozen ready-to-reheat meals:

• Jambalaya
• Mock Lasagna: layered cooked spaghetti with sauce and cream cheese
• Penne with sausage and vegetables in spaghetti sauce
• Chicken Cacciatore
• Chicken Tetrazzini
• Tuna Casserole
• Chili
• Chicken Curry with chickpeas, spinach, and rice 
• Rice, chicken and vegetables covered by cream of mushroom soup
• Enchiladas
• Meatloaf (uncooked)
• Meatballs (uncooked)

We started by prepping almost everything: chopping vegetables; thawing, cutting, and seasoning proteins; buying and organizing canned goods; cooking rice and pasta. Prep work transferred most of the contents of my freezer to my refrigerator, which was full and working hard to keep food cool.

The general procedure we followed was to prepare two dishes at a time, and we tried to make double batches when possible. We would cook the meat for each dish, let the meat cool a little, line a freezer-safe container with plastic wrap, apply non-stick spray to the wrap, build the dish in the container, cover with plastic wrap, and stick in the freezer.

After a dish had thoroughly frozen (a day) we removed the dish from its container and wrapped it in aluminum foil outside the plastic wrap, and then wrote the name of the dish and the name of the container we froze it in. When we reheat/cook the dish we know what container to use for best-fit.

All-in-all the batch cooking was a success, and I expect the pre-made dishes will be appreciated by future me.

Red-Black Trees Redux: Left-Right Symmetry

I previously compared top-down versus bottom-up red-black trees and concluded that bottom-up is faster and therefore preferred.

Recently I was working with binary search trees (BSTs) and happened to observe anomalous performance between two implementations of a BST (splay tree). One implementation was taking much longer than the other. After some investigation I attributed the variance to two factors: comparison functors and use of left-right BST symmetry. Cursory examination indicated that using a functor instead of direct comparison of keys was increasing execution time around 10-20% for a particular workload. Left-right symmetry was causing about 30-40% increases in execution time!

Comparison functors are important because an implementation of a BST cannot know ahead of time how to compare generic nodes, and—for languages that lack decent templates such as C—a functor is a fact of life. But left-right symmetry is a choice. Some arguments for left-right symmetry are that it reduces the source lines of code (SLOC) and increases correctness. I think the performance problems of using left-right symmetry comes from indexing in an array on top of a pointer dereference, and doing so multiple times. By separating the left and right cases explicitly the programmer specifies the pointer precisely.

Execution time increases for code that exploits left-right symmetry at least for splay trees. How much does the use of left-right symmetry affect red-black tree performance?

Using a search benchmark that I coded from a published description, I evaluated two versions of red-black trees: one that uses left-right symmetry to compress code paths and one that explicitly represents the two sides. (The left-right symmetrical code is the version currently in use in RTEMS.) The benchmark inserts search keys generated randomly until the tree reaches a specific size, and then issues a mix of update and search operations in sets of 100. For this work I used sizes between 16 and 4096 in powers of 2, and about 1000 update/search operations, with the mix varying between pure search and pure updates. Otherwise the benchmark is as described in the paper linked above.

The following charts show representative results from running these benchmarks in Simics/GEMS. The "rbtree" results use explicit left and right child pointers and split the cases; "rbtree sym" compresses the symmetrical cases together and uses an array of two child pointers.

Cycles to insert elements into a red-black tree until reaching the max size.

Cycles when searching in a red-black tree at certain sizes. 1000 searches at each point.

Cycles when updating and searching. 500 searches, 500 extractions, and 500 insertions at each point. Note that an extraction uses a search to find the node to remove.

The percent increase in execution time when using left-right symmetry of insertion is less than that of search: not good for a structure whose purpose is efficient searching!

Ben Pfaff's libavl uses left-right symmetry (and a table-based approach instead of parent-pointers), and comparing the performance of libavl using explicit cases for handling left and right might be interesting. Using his systems benchmarks to evaluate the RTEMS red-black tree implementation would be nice, although of limited value since the benchmarks target general-purpose (*nix) systems. The Linux (lib/rbtree.c) and FreeBSD (sys/sys/tree.h) kernels both have red-black tree implementations with explicit left and right pointers.

I have not evaluated whether the symmetrical case reduces code size (generated machine instructions in the binary). How much is SLOC reduced, and does that translate to reduced program size? If code size goes down due to symmetry then, for an embedded system, the choice of which implementation to use becomes more complicated. But if code size is the same (or increases!) then quantitative reasoning tells us not to use left-right symmetry.

Bike to work day

Today was bike to work day and I normally commute on Friday anyhow so I participated albeit without registering. There were noticeably more people out, particularly in small groups, although not many more than on a nice weekend day: fewer pedestrians though. I wore my new kit, which consists of the bib shorts and jersey of the 2008 Finnish champion (from team Francaise Des Jeux), blue/white helmet, blue gloves, white shoes, and my blue/white bike.

A skinny-tire caught my wheel shortly after I hooked up to the W&OD trail and we paced each other most of the way into DC. It was nice although for the first couple miles I didn't keep his wheel because he was a bit more brazen with rolling through stops. We had a pretty nice pace for the latter half of my ride. He was commuting from Ashburn, which is a sight farther than my own ride.

The ride home was a little rough, but the worst of it came near the end. Shortly after I got back onto the streets from the trail I was passed by a black BMW and the passenger yelled, "Get off the road %$#hole!" I have read that this is rather common, and so is having things thrown at you or being buzzed. The latter two constitute assault with a deadly weapon (vehicle) and can be brought to court.

Since I was only verbally harassed I decided to give a little back. So I chased the car down to the next stop light, pulled alongside, and yelled, "I have as much a right to the road as you!" The passenger, a young man, pretended not to hear because the window was up; the young girl driving seemed either embarrassed or amused, or maybe both. I went off to another lane to resume my ride. The same car passed me again a little later. Some people suck.

Downloading starred emails from GMail to apply git patches

Now that RTEMS is using git I frequently have to apply patches received by email, but GMail lacks a web interface for downloading selected emails. The conventional wisdom for how to apply a patch from an email is to "show original", save the page, manually remove the first blank line, and then use git-am to apply. Now do that ten times for a series of patches. How tedious!

So I wrote fetch-flagged-email—a small Python application—to accomplish my goal. Now I star patches in gmail and then run fetch-flagged-email.py followed by git-am. The script does the heavy lifting of saving emails to files in sequential order to a directory of my choosing.

productivity++;

Crufty Stuff

Joel Sherrill posted back in 2010 about the lines of code in RTEMS. I was curious about something related to this so first I replicated his work using sloccount. I think he may have neglected the inline files (because I had to add the .inl extension). I also added support for m4, .ac, and .am files. The latter two are part of the autotools build system and are filed under 'makefile'. Here are the current results on the RTEMS tree

Totals grouped by language (dominant language first):
ansic:       745153 (86.51%)
asm:          38574 (4.48%)
makefile:     34934 (4.06%)
ada:          26261 (3.05%)
sh:            7086 (0.82%)
cpp:           5248 (0.61%)
m4:            2996 (0.35%)
pascal:         814 (0.09%)
perl:           279 (0.03%)

Total SLOC  861,345

Now for the interesting part: I also ran sloccount after running bootstrap, which generates a bunch of files for the build system. I modified sloccount to also count the Makefile.in files (which are generated with autotools from Makefile.am sources). Here are the results

ansic:       745153 (35.73%)
sh:          638471 (30.61%)
makefile:    557257 (26.72%)
m4:           73475 (3.52%)
asm:          38574 (1.85%)
ada:          26261 (1.26%)
cpp:           5248 (0.25%)
pascal:         814 (0.04%)
perl:           279 (0.01%)

SLOC*     2,085,532
* includes generated files

And do you know how many humans look at that generated code? Any idea how much of it is tested?

It would be interesting to include all the other code that goes into making RTEMS work such as the compiler, RPM packing scripts, and so on. The moral of this data is that the build system is complex. Very complex.

This data was generated using David A. Wheeler's 'SLOCCount'.