It looks to me like I spend too much time moving around the file system. I should try to type more pathnames and stick around in one place…

I thought I was going insane. The people at the OSL that I told about this thought I was insane. The Mozilla developers that I work with and tried to explain this to thought I was insane.

Some research shows this: the remote Firefox actually starts and communicates with the X server running on the local machine. The X server tells the remote Firefox that there is already a process called Firefox running. The remote Firefox then sends a message to the local one to open a new window and then the remote Firefox dies. This protects a user from creating too many instances of a Firefox process on their machine. Clever, huh? But totally WRONG and counterintuitive!

Apparently you can stop this behavior if you start the remote Firefox with the intuitively named “no-remote” switch. That prevents the remote Firefox from “connecting” to the local Firefox.

Sigh, there goes an hour of my life that I’d like to have back…

#!/usr/bin/python

import sys, os, os.path
import fnmatch

def findFileGenerator(rootDirectory, acceptanceFunction):
  for aCurrentDirectoryItem in [ os.path.join(rootDirectory, x) for x in os.listdir(rootDirectory) ]:
    if acceptanceFunction(aCurrentDirectoryItem):
      yield aCurrentDirectoryItem
    if os.path.isdir(aCurrentDirectoryItem):
      for aSubdirectoryItem in findFileGenerator(aCurrentDirectoryItem, acceptanceFunction):
        yield aSubdirectoryItem

if __name__ == "__main__":
  rootOfSearch = '.'
  if sys.argv[1:]:
    rootOfSearch = sys.argv[1]
  if sys.argv[2:]:
    classnameFragment = sys.argv[2].replace('.', '/')
    def anAcceptanceFunction (itemToTest):
      return not os.path.isdir(itemToTest) and fnmatch.fnmatch(itemToTest, '*.jar') and
             classnameFragment in os.popen('jar -tf %s' % itemToTest).read()
  else:
    def anAcceptanceFunction (itemToTest):
      return not os.path.isdir(itemToTest) and fnmatch.fnmatch(itemToTest, '*.jar')

  try:
    for x in findFileGenerator(rootOfSearch, anAcceptanceFunction):
      print x
  except Exception, anException:
    print anException

The focus is on the generator function findFileGenerator. It creates an iterator for the results of a recursive search through a directory tree. It accepts as parameters a path to begin the search and a function to determine if a given file satisfies the search parameters.

Generators can be kind of confusing because even though they look like a function, they do not execute immediately when called. They return a reference to an object that works like an iterator. The code defined in the generator function is executed by that iterator object. The first time that the iterator’s ‘next’ function is called, execution begins at the beginning of the code and goes until it encounters a ‘yield’ statement. The ‘yield’ statement returns the next value of the iterator. The next time the ‘next’ function is called, execution resumes at the next statement after the ‘yield’.

Let’s examine this example closely. Imagine that the first call to the iterator has happened and we’ve got the resultant iterator-like object. The first call on that object to ‘next’ starts execution at this line:

for aCurrentDirectoryItem in [ os.path.join(rootDirectory, x) for x in os.listdir(rootDirectory) ]:

Here we’re getting our first directory listing of all the files in the current directory. Because the call to ‘os.listdir(rootDirectory)’ returns a list of file names with their paths stripped off, we’re going to have to re-attach them. The list comprehension (the code between the [ … ]) welds the current directory path to each of the files in the list and returns a new list. The for loop then sets us up to iterate through that list.

   if acceptanceFunction(aCurrentDirectoryItem):
      yield aCurrentDirectoryItem

Here’s where we decide if the current entry in this directory is interesting or not. We call the acceptance function on the item. Since the acceptance function is passed in when we originally called this generator, it could be anything the programmer desired. In the case of this particular utility, we’re looking for Java Jar files that meet a certain criteria. But it really could have been anything at all: find all files that have vowels in their name, or all files that have a specific type or content.
If the acceptance function returns ‘True’, then we yield. The current file is returned by the iterator and execution stops until the ‘next’ function is called.

  if os.path.isdir(aCurrentDirectoryItem):

If the acceptance function rejected the item, this is immediately the next line to execute. If the acceptance function accepted the item, this line won’t be called until after the next call to ‘next’. In either case, our goal is to find the next item for the iterator to return.

Since we’re iterating through a list of entries in a directory, some of those will be directories themselves. The item that we sent to the acceptance function could have been a subdirectory. Regardless of the outcome of the acceptance function, we need to recurse into subdirectories.

   for aSubdirectoryItem in findFileGenerator(aCurrentDirectoryItem, acceptanceFunction):
        yield aSubdirectoryItem

Hang onto your hat, here’s where your brain may explode. We’ve got a sub-directory and we need to recurse into it and iterate through its entries. Well, we’ve got this handy generator that does exact that: it returns an iterator that will cycle through the contents of directory. ‘for’ statements in Python have a special relationship with iterators. You can provide one instead of a list and the ‘for’ loop will dutifully iterate through them for you. We recursively call the generator, passing in the subdirectory and the acceptance function. The generator returns an iterator to us and the for statement starts the iteration by silently calling the next function. Remember that the iterator returns only items that have passed the acceptance function, so each item that we get here we’re just going to pass on as the next item in our iterator. Hence, we yield every item that we get in this loop.

The rest of the file is in the problem domain: a command line utility that will find Java Jar files with certain classes in them.

if __name__ == "__main__":

Perhaps someday in the future, we’ll want to use the generator in another application. By putting the code of the command line utility under this ‘if’, we’ll prevent it from executing when we use the ‘import’ statement on this file.

  rootOfSearch = '.'
  if sys.argv[1:]:
    rootOfSearch = sys.argv[1]

The root of the path that we’re to search is option on the command line. If no path is specified, we’ll assume that we’re to start in the current working directory.

  if sys.argv[2:]:
    classnameFragment = sys.argv[2].replace('.', '/')
    def anAcceptanceFunction (itemToTest):
      return not os.path.isdir(itemToTest) and fnmatch.fnmatch(itemToTest, '*.jar') and
             classnameFragment in os.popen('jar -tf %s' % itemToTest).read()

The name of the class that we’re to search for is also optional. If the user does not provide one, then we’ll assume that we’re to just find all jar files regardless of their content.

This code fragment is the other case: a fragment of a class name has been given. It is our task here to create an acceptance function that meets the criterion.

First thing to do is cook the class name a bit. In Java, class names are qualifies with paths. Inside Java code, ‘.’ is used as a separator. However, inside jar files, ‘/’ is the separator. To be friendly, we want Java programmers to be able to use either notation. We make sure the command line argument is converted to the ‘/’ notation and stored in ‘classnameFragment’. Next we define an acceptance function that receives a pathname as a parameter. All we have to do is subject that pathname to some tests and give it either a thumbs up or down. In this case, we test to see if the pathname represents a directory, then test to see if it is a jar file and finally we run the command line function ‘jar \-tf’ to give us a listing of the jar to see if our class name fragment is in there. Since Python can do “short-circuit” expression evaluation, if any of the earlier tests fail in the boolean expression, the other tests do not get executed.

  else:
    def anAcceptanceFunction (itemToTest):
      return not os.path.isdir(itemToTest) and fnmatch.fnmatch(itemToTest, '*.jar')

In the case where the user did not provide a class name fragment, we assume that we’re looking for all jar files. The acceptance function here just drops the additional criterion where we looking into the content of the jar file.

  try:
    for x in findFileGenerator(rootOfSearch, anAcceptanceFunction):
      print x
  except Exception, anException:
    print anException

Finally, we ‘re ready to actually use the tools. We call the generator function with the path from which to start the search and our acceptance function. That returns an iterator that we loop through and print the matching jar files.

I’m suffering an ospid, I wrote some code last weekend that I keep looking at over and over again because I like it so much.

I’ve got relational database schema that looks like this:

For this blog posting, I am only interested in the first six tables of the top cascade of tables and the ‘updateParamters’ table just below them.

I’m trying to populate this schema with its initial data by walking a filesystem tree. I search for files within the filesystem fetching each file’s pathname. The directories in a pathname correspond to values in the cascading tables.

listOfTables = ['product','version','buildTarget','buildId','locale','channel']

I wrote a function that takes the name of a directory as an argument. The function’s objective is to put the directory name into an appropriate table whenever the value isn’t already there. I could have written the function such that the target table name is also a parameter to the function, but I took a different path instead. I decided that each table should have its own function. This didn’t mean that I had to individually write the function for each table, I could get Python to do that for me.

def getInsertFunctionForTable(tableName,  databaseConnection, cache,
                              insertSqlTemplate = genericInsertSql,
                              fetchSqlTemplate = genericFetchIdSql):
  insertSql = insertSqlTemplate.replace('TABLENAME', tableName)
  fetchSql = fetchSqlTemplate.replace('TABLENAME', tableName)
  def insertIntoTable(value):
    try:
      return cache[tableName][value]
    except KeyError:
      databaseConnection.executeSql(insertSql % value)
      id = databaseConndatabaseInsertFunctionsection.singleValueSql(fetchSql % value)
      cache[tableName][value] = id
      return id
  return insertIntoTable

In this code, I define a function that, when given the name of table, will return another function. This second returned function is the one that I defined earlier. If I take my list of table names, and use a list comprehension to create a second list of functions appropriate for handling each of the directories in a pathname.

databaseConnection = ...
cache = collections.defaultdict(dict)
databaseInsertFunctions = [ getInsertFunctionForTable(x, databaseConnection, cache) for x in listOfTables ]

Now I can take a pathname and my list of functions and use another list comprehension to process them:

pathname = 'firefox/2.00.12/linux-gcc3.1/2008020101/en/somechannel/file.txt'
idForPathname = [x[0](x[1]) for x in zip(databaseInsertFunctions, pathname.split('/'))]

The result is a list of the database’s id for each of the directory names in their respective tables.

As it happens, this is the value that I need to populate the next table in my diagram. Now I can use the same function again for this next table:

updateParametersInsertFunction = getInsertFunctionForTable('updateParameters', databaseConnection, cache,
                       updateParametersInsertSql, updateParametersFetchIdSql)

Using that idea, I can process entire tree of data, inserting all the values into all the tables with this loop:

for path, name, pathname in cse.FileSystem.findFileGenerator(root,lambda a: a[1] == 'complete.txt' ):
  updateParametersId = updateParametersInsertFunction(tuple([x[0](x[1]) for x in zip(databaseInsertFunctions, path.split('/'))]))

I keep looking at this over and over again. I really like it.

The actual software that I wrote was a touch more complicated. I added the capability to translate values in the tables with a reference to a translation function. I also took into account the rest of the tables that I’ve not mentioned in this posting.

The toughest part are the letters: o, e, i, d, c, r.  I’m always swapping those in pairs: o for e, i for d and c for r.  I run exercises to get them into muscle memory, but they just won’t stick.

This posting has taken an inordinate amount of time to write.

This is a line from a debugger. The code that I’m debugging stopped with an assertion failure on that line. While the code that interested me was further on the in the stack trace, this line was so absurd that I had to investigate it.

The code takes the constant zero, casts it to an unsigned long and then left shifts it 31 bits. It then takes another zero cast to an unsigned long and shifts it 16 bits to the left. These two results are bit-wised or’d together with a third zero cast to an unsigned long. The result, which is 0 as an unsigned long, is then cast to some type called HRESULT. Digging into the nested macro definitions, I see that HRESULT is defined as LONG32. LONG32 is a typedef for FIXED32. FIXED32 is a typedef for INT32. INT32 is a typedef for int. We’re taking a unsigned long zero, and then unceremoniously truncating it to be a signed integer. It’s a miracle, three signed integer zeros have magically become one signed integer zero.

The big question is why? How could code like this get written?

First I must say that any optimizing C++ compiler is going to resolve this absurdity at compile time. The compiler will throw all that crap away and just replace it with a zero. It may take even one step farther and get rid of it, too. So ultimately, it doesn’t matter to the compiler or compromise runtime efficiency. This essay is just an entertaining excursion into what seems like a comic farce.

The original line in the source code looks like this:

HX_VERIFY(HXR_OK == pContext->QueryInterface(IID_IHXScheduler, (void**) &m_pScheduler));


The offending token is the HXR_OK. This is a macro invocation. The macro is defined as:

#define HXR_OK MAKE_HRESULT(0,0,0)


The MAKE_HRESULT macro is defined as:

#define MAKE_HRESULT(sev,fac,code) \
((HRESULT) (((unsigned long)(sev)<<31) | ((unsigned long)(fac)<<16) | \
((unsigned long)(code))) )


This whole absurdity is the result of bit-packing. The coders wanted to take three values that described an error, the sev (severity), fac (facility) and code (error code), and pack them into one integer. In the header file that defines both HXR_OK and MAKE_HRESULT, I can see a number of other constants defined:

#define HXR_ABORT MAKE_HRESULT(1,0,0x4004) // 80004004
#define HXR_FAIL MAKE_HRESULT(1,0,0x4005) // 80004005
#define HXR_ACCESSDENIED MAKE_HRESULT(1,7,0x0005) // 80070005


So in each case, the code defines a constant in such an obfuscated manner that the programmer saw fit to add a comment to each line to show the hexadecimal value that he really intended and hopefully, what the macro eventually expresses.

There are several hundred constants defined in this manner. I see no facility to take these return codes apart to access any of the three values so painstakingly pieced together. Why go to all the trouble to tightly pack an encoding of these three values if you never unpack them? Is simply a case of over engineering?

There is a clue in the same header file in which these abominations are defined. It turns out that the macro definition of MAKE_HRESULT is actually in one branch of a conditional compilation unit. The other branch does not define MAKE_HRESULT. Instead, it includes <winerror.h>. Ah, it all becomes clearer now. This an artifact of compatibility with Microsoft Windows. Microsoft must have defined a system of function return status codes that follows this form. So here we are with an Open Source project to be used on the OLPC, Linux systems, OS/X and numerous mobile platforms bound to a convention required by Microsoft. Is there no escape from this evil octopus?

Looking back to my debugger, I see now that the purpose of the shifted zeros. It just happens to be the degenerate case of what is supposed to be a flexible system to stuff multiple pieces of information into one scalar variable. Someday a future programmer can change how these status codes are assembled simply by changing the definition of the macro. Of course, that will make the comments incorrect. I will wager that the refactoring day will never come and this piece of flexible engineering will never get the chance to flex.

Grepping across all files in the project, I can find the symbol repeated in many files as a local static constant.

static const char kValueDescription[] = "Writes Null Files";

This same definition appears in many files, each file has its own unique string. So these definitions of my missing symbol are available only after the inclusion of my header file. Just to test, I moved the include of the header from the top of the cpp file to a point below the alleged definition of my missing symbol: the missing symbol error goes away. It just seems plain wrong to require something to be defined prior to inclusion of a header file. Header files should be self contained: it should forward declare classes it can’t know details about or include other headers to get the declarations that it needs.

So here’s what I think is going on: the code is banking on the assumption that the compiler will blindly treat the template as if it were a macro. The original author wanted the compiler to not process the template until it is actually instantiated (coincidentally immediately after the the declaration/definition of the missing symbol). In my case, the compiler is not cooperating and as far as the source file is concerned, compiling the template prematurely.

I know that the GNU C++ compiler has had a bug in the past that where templates were instantiated prematurely. I’m not yet sure if this is an instance of this problem. I’ve seen the premature template instantiation problem manifest as an unlawful symbol redefinition, not a missing symbol. The question is, should a compiler fully check a template prior to instantiation? I would say “yes”, unfortunately, this code says, “no.”

I need to find a solution. Either I have to make the new location of the include permanent, an option I find distasteful, or I need to find a way to forward declare the static const char array in the header file. Unfortunately, forward declarations are for classes, not data items. How do you forward declare data?

So I am forced to be unclean. I’ve moved the header inclusion from the top of the file where it belongs down into the middle of the source file. This makes me ill with foreboding that there will be more trouble in the future from this.

I have this big pile of C++ code in front of me representing a development project from the late nineties. It is a wild mixture of coding styles embracing complex preprocessor systems for class declarations simulating templates, real templates, multiple inheritance, private inheritance, a roll-it-your-own runtime type identification system, all wrapped around a chewy Microsoft COM API. There are several hundred classes in several hundred files riddled with conditional compilation directives switching on everything from Win16 to Solaris. Few declarations are not wrapped in defines while most types are typedef’d or macro’d within an inch of their lives. Oh yeah, it’s got some threading, too.

While a branch of this code allegedly compiles on Linux under GNU 3.x, I am trying to use version 4.1.x to compile it. I am told that the 4.x GNU compilers are significantly pickier than the version 3x compilers. The actual code hasn’t been touched in at least four years. Honestly, it looks as if the team of programmers assigned to this code were unexpectedly escorted from the building during a mass layoff. Several files look to be half way through a refactoring effort. I find undeclared variables, misspelled enumerations, missing and ambiguous scoping, unused parameters and many other problems.

My task is to make it all compile because it must be drafted into use. I’m all for recycling and have embraced the object oriented code reuse credo since 1988, but I am taken aback by the complexity of this task. It may be that the original coders were too clever several times over. There are some nether regions of the C++ standard that are terrifyingly beautiful with fractal complexity: but I would think twice about using them in production code. I must say that the coder’s intent is rendered rather opaque by the language.

I’ve been here before. However, I was on the other side: I have written opaque code while enthralled with the brilliant yet twisted beauty of the underlying structure. I wrote it during the same era that this code originates. No documentation would ever be needed for it, it’s so obvious, “a child could do it”.

With age comes a modicum of wisdom. I know where these people and, indeed, I myself, have gone wrong in the past. Code must be written knowing that the high priest will pass on. It is time for me to pay for the follies of my youth. I walk to my task of atonement willingly and with my eyes open. When my delayed penance is served and I am free once more, I will return to Python coding with an eye for those who will come after me.

So I thought to myself, “how does a program communicate with a device?” The answer is, of course, through device drivers. How do you talk to device drivers? My shaky memory dredges up the word “ioctl”. I grep for “ioctl” in the ProducerSDk code. It appears only once in code dedicated to output filtering. That looked like a dead end.

The Helix Producer SDK Developer’s Guide on page 37 states: “Capture devices are plug-ins that wrap operating-specific capture subsystems,
such as DirectShow or Video4Linux.” This states directly that the ProducerSDK delegates capturing to an underlying system. DirectShow is a Microsoft thing, so I can disregard it. Video4Linux (V4L) is my target.

Somewhere in the ProducerSDK there is code that interacts with V4L - it should be simple enough to find. I downloaded an example of C code that uses V4L (specifically: capture.c). Looking inside, I see lots of calls to “ioctl” to interact with the driver. I see no code in ProducerSDK that looks like this code.

Hmmm, I’m not sure what this means. I wonder if I have the right version of the ProducerSDK.

Digression - what is a smart pointer ?

Smart pointers, sometimes referred to as reference counted pointers, are a memory management technique used by C++ programmers. Unlike Java, C# or Python, unused memory is not automatically garbage collected in C++. By adding a layer of indirection, an instance of a special pointer class wraps a traditional C style pointer. This class instance has special copy and assignment constructor semantics: when it is copied, a counter on the thing it is pointing to is incremented. When one of these pointer wrappers is destructed, the counter is decremented. If the counter goes to zero, then it is known that the thing pointed to is no longer referenced by anything and can itself be deallocated.

Smart pointers must be very careful in multi-threaded environments. The act of copying itself must be atomic - very atomic. How does a smart pointer copy itself? Using a copy constructor, it first allocates a memory for a new instance of the smart pointer class and then initializes the instance variables. The only instance variable is the pointer to the thing of interest. Once the pointer is copied, then it increments the reference counter in the pointed-to object. What would happen if the original smart pointer’s destructor were called in the instant between the copy of the pointer and incrementing the reference counter? It is possible that the referenced object could be destructed before the copy gets the chance to increment the reference counter.

Helix Producer Smart Pointers Appear to be Vulnerable

Check out this the copy constructor from Helix Producer’s Smart Pointer Code in producersdk/common/include/hxtsmartpointer.h:

00113 template<class T>
00114 inline CHXTSmartPtr<T>::CHXTSmartPtr( const CHXTSmartPtr<T> &spCopy ) :
00115         m_ptr( spCopy.m_ptr )
00116 {
00117         if ( m_ptr )
00118         {
00119                 m_ptr->AddRef();
00120         }
00121 }

The actual pointer is copied in the initializer on line 00115. Then, in the body of the copy constructor, if the pointer is not zero, the referenced object’s counter is incremented. The member function “AddRef” is implemented in producersdk/common/include/hxtunknown.h as:

00084         STDMETHOD_(ULONG32, AddRef) (void)
00085         {
00086                 return InterlockedIncrement( &m_lCount );
00087         }

A little spelunking reveals that “InterlockedIncrement” is an atomic operation defined in a Microsoft API. This function call is properly protected in a multi-threaded environment.

As I stated above, though, I believe that both the copy of the referenced pointer and the increment must be protected. How is data shared between threads? It doesn’t seem to matter which thread invokes the copy constructor, the code is vulnerable.

Scenario 1: If a reference to a smart pointer is given to a thread and that thread invokes the copy constructor to make its own copy, then it is vulnerable to accessing deallocated memory. The original smart pointer could have been destructed between the time of the internal pointer’s assignment and incrementing the reference counter.

Scenario 2: If a master thread makes its own copy of the smart pointer object for use by a child thread, then the master thread must explicitly take care to not allow the copy go out of scope while the thread still lives. If the master thread lets the smart pointer destructor be invoked, then the thread has an invalid copy. If the child thread were to make its own copy, then we’re right back to scenario 1.

Does This Really Happen in Helix Producer?

I do not know. I will need to study how the threading model works in our target application. Perhaps we’ll be lucky and referenced counted objects are never shared between threads, but I doubt it.

Further problems with CHXTSmartPtr

CHXTSmartPtr’s assignment operator fails to take into account the tautological “self assignment“.

CHXTSmartPtr<SomeCHTXUnknownDerivative> p(new SomeCHTXUnknownDerivative);
CHXTSmartPtr<SomeCHTXUnknownDerivative>& q(p);
p = q;  //deallocated memory referenced

Granted, code such as direct as this would not be written. However, it is not unfathomable for the provenance of the R-value to be unknown. In such a situation, a self assignment could be completely inadvertent but ultimately disasterous.