post

Bash completion for ElectricAccelerator

Maybe you haven’t noticed, but Electric Make (emake) has a lot of command-line options. Besides the options it inherits from emulating GNU make (or NMAKE), it has about fifty of its own options, from –emake-annodetail to –emake-tmpdir. Remembering them all, and their exact spelling, and their allowed values is a nuisance, even for me — and I created half of those options myself. So, I spent the last few evenings hacking together Bash TAB completion support for emake (download from github here), with pretty good results:

$ emake --emake-h<TAB><TAB>
--emake-history=        --emake-historyfile=  
--emake-history-force=

In addition to helping with emake options, it can help me remember the valid values for those options:

$ emake --emake-history=<TAB><TAB>
create  merge  read

It handles options with compounds values too, like –emake-annodetail:

$ emake --emake-annodetail=<TAB><TAB>
basic  env  file  history  lookup  registry  waiting
$ emake --emake-annodetail=file,<TAB><TAB>
file,basic     file,history   file,registry  
file,env       file,lookup    file,waiting   
$ emake --emake-annodetail=file,history,<TAB><TAB>
file,history,basic     file,history,registry
file,history,env       file,history,waiting
file,history,lookup    

It can even do TAB completion on targets in makefiles, thanks to some clever code inherited from the gmake completion module that I used as the basis for my emake completion module:

$ emake <TAB><TAB>
all        check      distclean  Makefile   
buildtest  clean      install    

And since I was already tinkering with TAB completion for emake, it wasn’t much work to do TAB completion for ElectricInsight (einsight) as well. In that case, TAB completion doesn’t really do a whole lot — einsight doesn’t have many command-line options. But intelligent TAB completion is still pretty handy for one specific reason: I can make it only match files with the correct extension — .xml and .anno:

$ ls
build-272.dlog  build-272.xml
build-273.dlog  build-273.xml
$ einsight <TAB>
$ einsight build-27<TAB><TAB>
build-272.xml  build-273.xml  

Rather than suggesting all of the files in the directory, Bash now knows to suggest only the .xml files when I invoke einsight.

I was surprised to find that setting up custom TAB completion for my applications is pretty easy: just create a shell function that generates a list of possible completions based on a partial command-line, then instruct the shell to use that function to handle completions for whatever command you like. As far as I can tell, the mechanism is pretty flexible — you’re limited only by your own Bash scripting skill. If you’re interested in doing something like this yourself, I suggest you check out these online tutorials, as well as the Bash Completion project, which includes completion modules for nearly 200 commands.

Availability and installation

You can download the TAB completion module for emake and einsight from my github repository. As far as installation goes, you have a few options:

  1. Hook into the bash-completion package. Many modern Linux distributions, including Ubuntu 9.x/10.x and SUSE 11 install the bash-completion package and set up the default bashrc file to use it. On those systems, you can just copy accelerator.sh to /etc/bash_completion.d.
  2. Modify your personal .bashrc. If your system doesn’t have the bash-completion package, or if you can’t add files to etc, you can modify your own .bashrc to source accelerator.sh on startup. In that case I would rename it to $(HOME)/.accelerator.sh, so that it is normally hidden from directory listings, and add source $(HOME)/.accelerator.sh to your .bashrc file.

The image at the top of this post is free; you can redestribute it and/or modify it according to the terms of the Free Art License; it is based on this image by Aurelio Heckert.

post

Eternal vigilance and multithreaded programming

Given the following:

  • A multithreaded application written in C++, using the STL.
  • A class Mutex, which is a thin wrapper around a pthread_mutex_t.
  • A class Lock, which implements the RAII pattern for acquiring and releasing a Mutex.
  • A class FileInfo, which stores information about a file. The getSize() method retrieves the current size of the file. Because another thread may be changing the size of the file, getSize() is internally locked.
  • A class Cache, which manages a map of filenames to FileInfo objects.

Can you spot the bug in this bit of code?

class Cache {
protected:
    typedef std::map<string, FileInfo *> map_type;

    Mutex mLock;
    map_type mMap;

public:
    void insert(const string& filename, FileInfo *info)
    {
        // Add a new file to the cache.

        Lock lock(mLock);
        mMap.insert(make_pair(filename, info));
    }

    void invalidate(const string& filename)
    {
        // Eject a file from the cache; this only
        // invalidates the cache entry, it does not
        // delete the associated FileInfo.

        Lock lock(mLock);
        map_type::iterator i = mMap.find(filename);
        if (i != mMap.end()) {
            mMap.erase(i);
        }
    }

    int64_t getSize(const string& filename)
    {
        // Get the current size of a file in the cache.

        map_type::iterator i;

        {
            // Grab the cache lock for the lookup.

            Lock lock(mLock);
            i = mMap.find(filename);
            if (i == mMap.end()) {
                return 0;
            }
        } // release cache lock

        // Relay the getSize() request to the FileInfo
        // object; this must happen <i>after</i> releasing
        // the cache lock, because FileInfo::getSize() 
        // can block.

        return i->second->getSize();
    }
};

Even if you’re familiar with the STL and multithreaded programming, the defect can be hard to spot. In fact, this one escaped my notice until a recent mysterious core dump alerted me to its presence, despite having read this code several times for other reasons.

Here’s the bug: in Cache::getSize(), the iterator i is accessed outside the protection of the Cache lock. You may think that this is safe, since the lookup occurs inside the lock. But suppose we have two threads running simultaneously, one calling getSize(“foo”), and the other calling invalidate(“foo”):

Thread A: getSize(“foo”) Thread B: invalidate(“foo”)
{
    Lock lock(mLock);
    i = mMap.find(filename);
    if (i == mMap.end()) {
       return 0;
    }
} // release cache lock
Lock lock(mLock);
i = mMap.find(filename);
if (i != mMap.end()) {
    mMap.erase(i);
}
return i->second->getSize();

By the time Thread A uses the iterator returned by map::find(), the call to invalidate() has, well, invalidated it. I suspect that the author of this code remembered that map::erase() invalidates the iterator used in the erase() itself, but not the corollary that map::erase() also invalidates any other iterator that references the same element.

If you think about how std::map is implemented, it’s obvious that erase() should have this property. Internally, std::map usually uses some type of balanced tree. With that foundation, the simplest implementation of std::map::iterator is just a thin wrapper around a pointer to a node in the tree. map::erase() must delete that node (otherwise, when would it be deleted?), so accessing an iterator after it has been erase‘d is literally a free memory read, an obvious memory management error.

In this case, the solution is simple: just extract the FileInfo pointer from the iterator before releasing the Cache lock, as follows:

    int64_t getSize(const string& filename)
    {
        // Get the current size of a file in the cache.

        FileInfo *info;

        {
            // Grab the cache lock for the lookup.

            Lock lock(mLock);
            map_type::iterator i = mMap.find(filename);
            if (i == mMap.end()) {
                return 0;
            }
            info = i->second;
        } // release cache lock

        // Relay the getSize() request to the FileInfo
        // object; this must happen <i>after</i> releasing
        // the cache lock, because FileInfo::getSize() 
        // can block.

        return info->getSize();
    }

Eternal vigilance

The interesting thing about this bug is that it would have been nearly impossible to detect with testing alone. This is why code reviews are so important in our profession, and why projects that really demand bug-free code rely so heavily on them. As they say, “Eternal vigilance is the price of multithreaded programming.” With that, I’m off to review some more code. Shouldn’t you?

post

Top posts for November 2010

The following articles generated the most traffic in November. Still mostly articles that I wrote for the Electric Cloud Blog, but the number one entry is actually from blog.melski.net, and I think there would have been another, except that I only published the article on November 30:

  1. Shell commands in GNU make: 38% of page views
  2. Makefile performance: $(shell): 19% of page views
  3. A second look at SCons performance: 6% of page views
  4. What’s new in GNU make 3.82: 6% of page views
  5. The last word on SCons performance: 4% of page views

What’s most interesting to me this month is the search performance of Shell commands in GNU make. I wrote that article specifically because I see a lot of search traffic from queries like “makefile shell”, “shell command in makefile” and other variants of that theme. To my disappointment, all of those searches still bring people to Makefile performance: $(shell), rather than to the new article. Not sure what I did wrong there. Perhaps it was the inclusion of the word “GNU” in my new article? Anybody with more SEO experience care to comment?

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: