Oct 102010

I was thrilled with Ubuntu 10.04 Netbook Remix. It made excellent use of the small screen and the single-full-screen application usage model. It had its warts. You had to leave your application to access the menu. Some dialogs didn’t work well on small screens, making it difficult to get at the buttons on the bottom. But all in all, it worked really well. I was particularly fond of the menu system’s use of the desktop to display icons – with the caveat that it would have been nice to be able to get at things without completing obscuring your current application.

Enter Ubuntu 10.10 (Maverick) Netbook Edition with the new Unity interface. I was expecting a polished up version of 10.04 – what I got was… lost. The new menu system displays icons on the left-most column, and maximized windows do not obscure it. So far, so good in my opinion. But wait… where did the menu organization go? You know “Internet” “Graphics”… etc. You have to scroll down to the “Applications” icon (mouse hover is the only way to be sure that’s what it is) which brings up a menu system reminiscent of the 10.04 menu, except without much in the way useful organization. There are some breadcrumb style categories at the top, but all those that I would expect. Figuring there must be some preferences to adjust this sort of thing, I started looking for preferences… … … not a preferences category in sight – OK, I used the handy search bar. That brought up some plausible settings programs. Clicking on one of them brought up… the application installer! The search showed me preferences tools for applications that were not even installed!

Once an application is found, I expected to be able to add it to the menu as a favorite, or some other similar model. No such luck, right click is impotent, although it is used to remove icons from the menu. As it happens you can only add it to the menu by launching the application and then right clicking on the newly added icon on the menu and selecting “Keep in Launcher”. I found the “+” around the icon in 10.04 to be a much more discoverable mechanism.

Besides objections to its design, I ran into some implementation annoyances as well. The Application and System launchers took long enough to load that I was tempted to press them again. Perhaps this is do to time spent searching the package manager for applications I haven’t installed? The mouse-hover descriptions of the menu icons would occasionally stick – leaving “Firefox Web Browser” obscuring the browser itself.

Perhaps things will “click” and I’ll fall madly in love with Unity – but I doubt it. For now, I must bide my time until my better half logs into her account on this netbook and looks up at me with that knowing glare that says, “You just couldn’t resist could you? WTF is my browser?”

Aug 272010

You’ve received that email, “Please print, sign, scan, and return.” Possibly it said FAX – but like me, you just can’t wrap you’re head around using a FAX in 2010. So you fire up gimp (or xsane), scan a page, crop it, save it; repeat for N pages; then spend 10 minutes reading the absurdly obfuscated ImageMagick man pages to finally stitch the images together into a PDF, and return to sender. You do this once, and the memory of it provides a very significant mental barrier to ever repeating the process.

I had to do this again today for a pair of documents. The Simple Scan tool caught my eye and I gave it a try. It’s pure genius, in an “OMFG why did it take 10 years for this to appear?” kind of way. Simple Scan handles the intermediate files behind the scenes, crops all the pages to the same size, displays a thumbnail of each page you scan, and finally saves the document as a PDF. Like, wow. Thanks Simple Scan!

Aug 202010

Red Black trees are a critical data-structure in the Linux kernel. I’ve often wondered what made them unique to other trees, but ignored the impulse to dive into it much beyond reading the excellent Wikipedia article on red black trees.

An rbtree achieves O(log n) time complexity for search, insert, and remove. The key properties of an rbtree are as follows:

  1. A node is either red or black.
  2. The root is black. (This rule is used in some definitions and not others. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
  3. All leaves are black.
  4. Both children of every red node are black.
  5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

I finally manned-up and decided to write a sample red black tree in python. Despite having covered binary trees ad nauseam in college, I was surprised how challenging it was to write a completely functional red black tree. After a few nights of “free time” dedicated to the project, I finally have something to show for it.

$ ./rbtree.py 
***** Populating Red Black Tree with 1000 Nodes *****
***** Test Insert Complexity O(log N) *****
***** Test In-Order Traversal *****
***** Test Search Complexity O(log N)*****
***** Test Remove Functionality *****

The source comes with a built-in self test that inserts the values 1-1000 in random order, locates them all, then removes them in random order. It verifies the 5 properties of the rbtree at each step, and prints the results.

While I am glad to have done it, I am truly embarrassed at how long it took me to complete. On the bright side, the principles I had to dust off to get this done are now painfully fresh in my head. If you’d like to see the source, it’s available here: rbtree.py

Lastly, there is a clever interactive demo here (requires java):
Red Black Tree Demonstration

Next up… python metaclasses, and why Guido is an evil bastard.

Jul 152010

I finally got tired of lack specifiers in “git grep” and the cscope ncurses interface. I spent a few minutes and setup the vim cscope plugin using this mighty fine tutorial:


The one gotcha I ran into was having to disable my vim setting that automatically changed the working directory to that of the open file – it broke the cscope plugin relative filenames.

" automatically switch the cwd to that of the file in the buffer
" This breaks cscope plugin
" autocmd BufEnter * :cd %:p:h

Very, VERY VEERRRYYY nice. Now if only I could get a full call graph out of it…

Jun 172010

I use rdiff-backup to keep a few months worth of daily backups for my home systems (and those of my parents for that matter). The ability to recover any version of a file is great – although the process still requires a geek (me).

$ rdiff-backup --restore-as-of "7D" user@backupserver::/path/to/backup/file

Wouldn’t it be great if you could just mount the backup repository and browse by path or date and then just copy the desired version? Enter BackupFS, a fuse filesystem implemented with rdiff-backup.

I’ve only just started digging into this, and rdiff-backup’s python packages were not intended to be used as libraries (not with all the code buried in rdiff_backup.Main and all the global module variables floating around. Still, I was able to get a server test and a listing of the repositories root increments by using the python modules (and not just making multiple subprocess() calls).

I have a glorified version of the example hello world fuse filesystem able to mount and list a few meta-directories:

dvhart@vin:backupfs.git$ ./backupfs.py mnt && (tree mnt; fusermount -u mnt)
Testing server started by:  ssh -C katara rdiff-backup --server
Server OK
|-- By Date
|   `-- increments.2010-01-07T22:11:42-08:00.dir
|-- By Path
`-- hello

3 directories, 1 file
Fatal Error: Lost connection to the remote system

I still have some basic research to do in order to understand how to operate within the rdiff-backup packages (API isn’t quite the right term ;-). After that, it’ll be on to a more formal design and then some nicer code.

Jun 022010

I had Dad ship his old laptop for an upgrade. After installing Ubuntu Lucid (from a USB key) and upgrading the RAM, I was _really_ impressed that Empathy video chat over Google Talk “just worked”. I went and picked up a Logitech C120 web-cam for him for $20, took it home, plugged it in the USB slot and guess what – it just worked! We’ve come a long way in 10 years Linux! Honestly it felt weird… I kept thinking… isn’t there a driver I should have to download, build, fix, patch, build, etc… It’s like… having a mac or something. The only thing that would have made it better would be if the box had a penguin logo on the back.

Mar 292010

I’m working on some experimental futex operations to reduce userspace dependency on the ill-defined sched_yield system call. Anyone who has worked with futexes know that they are racy by their very nature as they share control of a userspace address between userspace and the kernel. After spending a couple _days_ verifying there was nothing wrong with the actual algorithm I used to implement FUTEX_LOCK, I started adding instrumenting the kernel (aka grasping at straws) with ftrace via my new favorite kernel debugging tool, trace_printk. This only provides half of the picture. In order to correlate events in the testcase (userspace) with the traces from the kernel I turned to the trace_marker feature of ftrace. By opening /debug/tracing/trace_marker and writing debug messages there I could correlate kernel and userspace progress in a single trace. Thanks to Steven Rostedt and the other tracing guys for such an excellent tool! See Steven’s series of articles on LWN for more details on ftrace. This trace led me right to the offending code… which, yes, was my own fault :-)

Dec 032009

I’ve taken longer than many to get comfortable with git. I’ve become very comfortable with quilt and git consistently behaved non-intuitively (for me). A couple months back someone pointed me at “git rebase -i” – the clouds parted, heavenly rays shone down upon me, and all was well once again in the Zion in my head.

With quilt you work with patches, and you really need to have them well defined in your head before you start. You can get away with some lack of planning if your various patches are restricted to distinct files. More often than not for me however, my patch series work on a single file, or maybe two or three. Merging patches in quilt is … well … just like merging patches without quilt … a flurry of filesystem commands and manual merging.

With git, you work with the source, and generate the patches from your changes. The git motto “commit often” is key to success here. I can start a project with only a rough idea of what needs doing and commit small changes along the way. When the project is done, I may have dozens of commits in my local git tree, none of which are functionally complete, and most likely won’t even compile. With “git rebase -i” I can rearrange these patches, merge them, annotate them, and generate a series suitable for submission to LKML. Ahhhhh. I git it! Finally.

Nov 272009

Todos pile up, balls get dropped, and I search for solutions to managing the chaos. Several years back I found inspiration in David Allen’s Getting Things Done (GTD) approach to task management. The simplicity of the various lists and the generic process definition that relied on no specific medium or implementation appealed to my need to customize and make everything my own. GTD seemed perfectly matched to a software application that could manage the various views and relationships of tasks, projects, and contexts. I tried various existing tools, but they each were cumbersome, slow, and unintelligent (forcing me to spend more time in the tool than I was willing to give). I went so far as to program my own, Braindump, which addressed my frustrations. While I accomplished what I had set out to do, the increasingly pervasive presence of smart phones, netbooks, and other internet devices were highlighting the rather crude single-computer usage model of my application. It also suffered from what every other stand-alone task manager suffers: lack of calendar integration.

Among the list of rejected applications years back was Remember the Milk (RTM). While RTM kept things simple and didn’t burden the user with a rigid work flow, I felt (at the time) that its extrememly free-form nature would leave too much process enforcement to the user, making it as awkward and cumbersome as its competitors which enforced too much process internally. I was also just not ready to make the leap into the world of “cloud services”. After catching a blurb about a new RTM Google Calendar gadget, I decided to give it another shot… and I’m glad I did. I read several other user experiences on using RTM for GTD, one in particular I feel is worthy of citing here as being influential in my approach: Guest Post: Advanced GTD with Remember The Milk by Doug Ireton.

GTD Overview

If you are already familiar with GTD, skip this section. For those of you that haven’t been indoctrinated, allow me to present a very brief introduction to the principles of GTD. It’s all about freeing your mind from thinking about what you have to do so you can focus on doing it. You need a trusted system to store information so your brain doesn’t have to. The process itself is defined by five stages: collect, process, organize, review, and do. These stages are implemented using lists of tasks, or “next actions”, and “projects” (work items that encompass more than one task). A key point about next actions is they are immediately actionable. They have no dependency on anything else. During the “do” stage, you should be able to open the next actions list and immediately get to work performing those tasks. Another core mechanism of GTD is the “context”. By organizing your next actions by context, such as Calls, Errands, Office, and Home, you can easily see the tasks that you can complete at any given time, based on where you are (by a phone, in the office, driving between work and home, etc.). Lastly, a weekly review is critical to making GTD work. During this review, you review each of your projects and ensure they have a next action so you can make progress on them during the week. Before getting too far into constructing a task management system, I’d recommend reading through GTD.

GTD with RTM

GTD is essentially implemented as a collection of lists. This translates well to Remember the Milk which is just that – a set of user defined lists. RTM also provides some basic properties to list items, such as due date, time estimate, and notes. What makes RTM smarter than a set of paper lists are the tags, locations, and powerful searches. Tags allow you to use short terms to relate tasks to eachother. Locations are intended to allow you to save off the address where a task needs to be completed, which is cute but largely useless IMNSHO, so I’ll overload this feature a bit later. RTM provides users with a powerful boolean logic search and the ability to save those searches as custom lists which are automatically updated when your tasks change. Let’s see how to put these all together to create a powerful GTD system using RTM!

Core GTD

Let’s start with a set of real lists (created via Settings->Lists). I find it useful to separate work and personal lists with “W-” and “P-” respectively.

Inbox and Sent are defined by RTM and cannot be changed. The Inbox works well as a staging ground for thoughts you have that you haven’t fully processed yet. You’ll work through these during the “Process” and “Organize” stages, converting them into projects and tasks. I use the Personal and Work lists to store all my tasks, currently actionable or not. I use the “na” tag to mark tasks as next actions to distinguish them from tasks that are dependent on something before they can be executed. The two Project lists are used to store an item for every project I’m working on. I tag each project with a short identifier which I also use to tag all the associated tasks so they can be identified by project. Let’s look at a project and a couple tasks.

Under the W-Project list I have an item titled “RT Elevator Pitch” tagged with “rt-elevator”. I then create a task on the Work list titled “Brainstorm topics” and tag it with “rt-elevator” as well as “na”. If I want to see all the tasks for this project, I can click on the project item on the W-Projects list and then click on “rt-elevator” in the Task box on the right. This will open a search for all the items tagged with “rt-elevator”.

GTD refers to next actions lists, not task lists. When it’s time to get something done, you shouldn’t have to wade through all the tasks to find one you can do right now. In the search box, enter “tag:na”, this will filter the list to only those tasks which are currently actionable. This doesn’t take into account work vs. personal though. To limit it to just actionable work tasks, search for: “list:Work AND tag:na”, click on the Save tab and call it “W-Next Actions”.

To refine your task list even further, let’s take a look at the GTD concept of “Contexts”. David Allen suggests the use of the @ (for various reasons) to indicate contexts. This is particularly convenient with RTM as that is the hotkey for specifying location when entering a task. Since I find the locations feature rather useless in its intended form, I overload it as my contexts list. Click on locations and create your GTD contexts list (RTM wants you to specify a map location for each context – pick some place exotic!). For me this list includes: Calls, Errands, Home, and Office. You might add “Computer” … but if you’re reading this that would probably be akin to adding an “awake” context… it just doesn’t refine your search very much ;-) Now you can specify a context for each task. To filter by context, search for each of your contexts and save the searches. For example, search for “tag:na AND location:office” and save the search as “@Office”. This list will show only those actionable tasks that must be completed at the office! Note that I don’t separate Work and Personal lists here. If I’m out running errands I might as well get those for work as well as home done in one go. Same for a batch of phone calls.

Lastly, you’ll want a tag and a saved search to keep track of tasks you are waiting on from someone else. I use the tag “wait” for this, and will sometimes include a nickname for the delegate, like “john”. Then create Waiting lists, such as “list:Work AND tag:wait” as “W-Waiting”.


Something that has always bothered me about the various advanced task management software that I’ve used, is the lack of integration with my calendaring. And no, the task add-ons in things like Evolution and Google calendar (and all the others) don’t count for reasons that are hopefully obvious by now. RTM provides several very nice services for calendaring. You can get an iCalendar (ics) URL for any of your lists. I add the Personal and Work lists to my Google Calendar and all the tasks with due dates appear on the day they are due. RTM also has two Google Calendar gadgets, one that displays a check icon on each day so you can work with tasks of that day (mostly useless IMO) as well as a very nice sidebar gadget that will display the list of your choosing and group the tasks by due date: Overdue, Today, Tomorrow, Monday, Anytime.

There are some tasks that must be done on a certain day, but not at a particular time. You could just add these to your calendar application, but I find it convenient to keep all my tasks in one place. You don’t want to have these tasks show up on your next actions lists until the day they are due. That means you either have to remember to set the na tag the morning of (yeah, not very likely right?) or come up with another mechanism. I tag these items as “cal” and ensure they have a due date. I then augment my next action searches to look for “tag:na OR (tag:cal AND dueBefore:tomorrow)”. This way I only see the cal tasks when they’re due (and afterwards if I failed to complete them).


When you complete tasks in RTM, it records the completion date. You can use this in a search as well to generate a weekly (or monthly, etc.) report for your boss. Consider searching for ‘list:Work AND completedWithin:”1 week of today”‘ and saving it as “Weekly Status”.

If you can convince your colleagues to setup an RTM account (they don’t have to be GTD junkies by the way). You can use the RTM “Send To” feature to delegate tasks. The task will then appear be moved to the Sent list. You may need to adjust your waiting searches to include the Sent folder, and possible tag delegated items with “work” or “personal” as there aren’t seprate Sent lists. Personally, I’d rather RTM didn’t move my tasks to another list after I send them.


Remember the Milk provide an incredibly flexible tool for managing tasks. Not only is it highly functional in its own right, but it also integrates brilliantly with services like Google Calendar and Google Gears (for offline use). RTM also provides a minimal mobile web interface (which is well… minimal), but if you’re an iPhone or Android user, you can download an RTM application if you’re a pro user for a much improved mobile interface. Well worth the $25 a year in my opinion. RTM, almost you convince me to purchase a smart-phone… and a $30-40/month data plan. Almost.

Sep 222009

I look forward to the Linux conference circuit every year, but only partly for the opportunity to learn something new and “geek out” for a week or two. Each year I find that spending several days surrounded by some very intelligent, very dedicated people leaves me in a pensive mood. I often find myself yearning for a way to be better at what I do, and to be able to do it faster. Today, during a panel session, a panelist described the “iron triangle” as it relates to software development: Cost, Schedule, Quality/Features – pick two, the third will have to be allowed to vary. This concept has also been similarly described by Susan Susanka in her “Not So Big House” series of books and articles, slightly modified to address the architectural process. This led my wife to ask me what my third point of the triangle was. I had time and quality… so what was the third? Quantity is the obvious answer. I struggle with this as I somehow still believe, despite numerous concrete examples in my own experience to the contrary, that I should be able to be a perfect husband and father, a brilliant kernel developer (in numerous subsystems), a domain maintainer, a competent business strategist, a woodworker of unmatched craftsmanship, a capable chef, an intuitive dog trainer, a carpenter, mason, landscaper, architect, interior designer, model of fitness and health, all the while maintaining my quick wit, charisma, and enviable good looks.

On numerous occasions I have received a similar piece of advice from my mentors. “Be the best in your field.” “Pick one thing, and do it extremely well.” etc. While I’m not willing to give up everything else to become a better kernel developer, perhaps it is time to let the “Quantity” point vary in favor of the “Time” and “Quality” points.