grep-dctrl is ten years old

My message Intent to package a Debian control file grepper to WNPP and debian-devel is today a decade old. Apparently, the message predates the invention of the acronym ITP for Intent to Package (the first instance I can find is from May 1999).

The changelog reveals that the first upload was on March 1st, 1999. There is unfortunately no record of when the package hit unstable the first time, since dinstall did not send Installed (or even the later Accepted) mails to an archived mailing list at that time. I suppose I might have it in some old private email archive, but more likely it’s just gone. Similarly, the first fixed bug (#35527) predates BTS archiving and is now lost.

The grep-dctrl program came out of repeated awkward grepping of the dpkg available and status files. Eventually I decided there must be a better way, and failed to find any canned solutions (I was later pointed to sgrep, which didn’t look useful enough, and even later to dpkg-awk, but I had already committed to my own solution by then). I wrote a simple C program that processed these files as a sequence of records and did simple substring searches in each record. I rapidly added support for field selection, regular expressions and output field selection. By version 1.3a of March 2000 (which was released with Debian 2.2 ‘potato’), the program was as good as it was going to get – with one exception.

“Make disjunctive searches possible,” said my TODO file those days. Conjunctive searches (that is, AND-searches) were possible even then by using more than one grep-dctrl command in a pipeline. Disjunctive (OR) was not possible. The problem was not so much that it would be hard to program (although the program’s internal structure wasn’t very good, to be honest, making extensive changes difficult), it was more a problem of coming up with a good command line syntax.

Another thing that bothered me with the old grep-dctrl was how to implement Ben Armstrong’s feature request. Again, the programming part wasn’t the problem, the problem was coming up with a good, clean semantics for the feature.

It was finally the appearance of ara in 2003 that got me moving again. Ara’s author proudly compared eir program to grep-dctrl, claiming that my program did not do disjunctive searches while ara does. Competition being good for the soul, I took it as a challenge. In April 2003 I announced a complete rewrite of grep-dctrl, which was completed in January 2004 (the 2.0 release).

The rewrite changed the way the command line was handled – even though the usual Unix switch style is still used, the command line is regarded as a language with a parser (first an operator-precedence parser, then a recursive-descent one). The command line is transformed into an interpreted stack-based language which drives the actual grepping.

The rewrite also generalised the internal data structures into an internal library which could be used to write other tools. The first such tool was sort-dctrl (introcuded in 2.7, June 2005), which was soon followed by tbl-dctrl (2.8, July 2005). The later appearance of join-dctrl (2.11, August 2007) finally allowed me to close Ben Armstrong’s longstanding feature request mentioned above.

The unpronounceable part of the names, “dctrl”, is an abbreviation for “Debian control”, which I decided to call the file format used by dpkg. Some people call it a RFC-822 format, but that really is a misnomer, since the differences between dctrl and RFC-822 outweigh the mainly superficial similarities (and the historical connection). I did consider calling my program dpkg-grep, but I didn’t feel like I had the right to invade the dpkg namespace. The later rename to dctrl-tools reflects the fact that there are now several tools, grep-dctrl being just the oldest.

I have several plans for the dctrl-tools suite, but my time and energy are mostly claimed by other responsibilities. The suite is currently team-maintained, but unfortunately the team is not very active. I would love it if I weren’t the most active one with my busy schedule! Feel free to pop in on the dctrl-tools-devel mailing list, and to look at the Git repository and the todo list. If you decide to participate, please follow the rules.

RFH: dctrl-tools — Command-line tools to process Debian package information

I request assistance with maintaining the dctrl-tools package.

There are several tasks that could use more manpower (in no particular order):

  • Writing test cases
    One could mine the BTS for past bug reports and create regression tests for them.
    One could use standard black-box and white-box testing techniques to generate general tests.
  • Writing documentation
    The whole suite of tools could use a unified tutorial manual on how to best use it. The current documentation is reference material in the man pages.
  • Internationalise the man pages
    Use po4a?
  • Swatting the BTS wishlist entries
    I’ve kept the BTS clean of actual bugs pretty well, but there are a number of wishlist reports still outstanding.
  • Take over maintaining the debian/ directory
    If you commit to maintaining it (and I trust your judgment), you’ll get last say in that part of the package (including deciding what helper to use).
  • Whatever you wish :)
    Discuss on the dctrl-tools-devel mailing list first though.

Eventually I’d like to pass the package on to competent successors, but I have too much emotional attachment to the package to do that without a transitional period where I still retain a veto on what goes in the package. I also have some ideas for future tools that I’d like to be
able to concentrate on, and having co-maintainers might allow that.

The package is now under Git in collab-maint. See the new README.Debian for information and a push-access code of conduct.

It’s time to fix the ABI

SELinux is entirely correct about disallowing dynamic code generation, as it is a major security risk.

Disregarding Just-In-Time compilation, the main legitimate need for dynamic code generation is to support (downward) closures that are ABI-compatible with normal C functions. GCC’s local functions extension of C is one example, and many non-C languages need them badly in their foreign-function interfaces (Haskell is one, Ada I’m told is another).

A closure is a function pointer that refers to a function that is local to another function. That function has access to the local variables of the parent function, and this access is provided by having the caller give the callee a static link (a pointer to the parent function’s stack frame) as a hidden parameter. If the call is direct (that is, not through a function pointer), the caller knows the appropriate static link and can just pass it. The trouble comes with function pointers, as we need some way of including the static link in the function pointer.

The simplest way is to have function pointers be two words long; one of the words contains the classical function pointer (that is, the entry point address), and the other contains the static link. Unfortunately, the prevalent C ABIs, including the SYSV ABI used by GNU/Linux, mandate that function pointers are one word long. The only way I know to work around this is to dynamically generate, when the function pointer is created, a small snippet of code that loads the correct static link to the appropriate place and jumps to the actual code of the function, and use the address of this snippet (usually called a trampoline) as the function pointer. The snippet is generated on the stack or in the heap, and thus requires an executable stack or executable dynamic memory.

It’s time to fix the ABI to allow for proper two-word function pointers.

New C standard in 2012?

The C standards committee is apparently preparing to revise the C standard. The proposed C1x charter sets the goal of the committee draft’s completion in 2009, with publication of the new standard in 2012. The proposed charter adds security as a significant new goal for the standard:

Trust the programmer, as a goal, is outdated in respect to the security and safety programming communities.

The proposed charter also sets the requirement that all new features must have a history in non-experimental compilers and be in common use.

The Dying Philosophers Problem

Reading a masters thesis draft that mentions the dining philosophers problem – a parable about the difficulties of process synchronization very well known in computer science – it occurred to me that it must not be a very good idea to eat just spaghetti (or just rice). I asked a nutritionist about it, and here is her answer. Even if they manage to avoid deadlock or livelock, dying of malnutrition is not going to be their first problem, go read the full story!

[Typos and thinkos corrected after initial publication]

Everybody has their own conference management software

… or at least it feels that way. I just ran into Edd Dumbill’s post on Expectnation, and I just last week helped grade a master’s thesis on the application of Petri Nets to investigating the correctness of another conference management software written at my University (a thesis that I had co-advised). I seem to recall reading about a couple of others.

Announcing darcs-monitor 0.3.1

Darcs-monitor will send email to a specified recipient about new changes added to a specific darcs repository. It can be run as an apply posthook (resulting in near-instantaneous “push” emails), or periodically from Cron, or occasionally by hand, whatever seems most convenient.

This new release (0.3) contains the following changes:

  • there is now support for the %CHANGES% and %SHORTREPO% substitutions in the template
  • a default template is now provided
  • ' and " entity references in darcs changes –xml is now supported
  • patches with just the author email address (no real name) are now handled correctly
  • when multiple emails are sent, they are now sent in chronological order
  • emails are announced to the user

The minor update 0.3.1 brings the documentation up to date.

Benja Fallenstein and Benjamin Franksen provided some of the features and bug fixes in this release. My thanks to them :)

You can get it by darcs at (darcsweb
), or as a tarball at It depends on mtl and
HaXml and is written in Haskell, naturally. It has been tested only with GHC 6.6 so far. For installation and usage instructions, refer to the README at any of the locations above.

Please note that this software is very new and thus can be buggy. As with any email-sending software, bugs can result in major annoyance; user caution is warranted.