Monday, June 16, 2008

The Joy of Smart Pointers

One of the biggest mistakes people new to DirectShow (and COM, for that matter) is using raw COM pointers. This article aims to present a compelling alternative.

All COM objects implement the IUnknown interface. IUnknown defines three standard methods, of which two are a concern of this article: AddRef() and Release(). When a COM object is created, its "reference count" (the number of objects holding claim to the newly created object) is set to 1. A program never directly deletes these objects; instead, a program calls Release(), which de-increments the reference count. If the reference count reaches 0, the object self-destructs.

The benefit of this is an object will remain in memory only as long as it needs to; the lifetime of an object is managed by its reference count. A programmer cannot accidentally delete an object from memory that another module or portion of the application may be using. Only when the object's reference count goes to 0 (as a result of all involved parties calling Release() on their interface pointers) does the object automatically destroy itself.

This is, sadly, a double-edged sword; by mismanaging reference counts, you can easily get yourself in trouble, and leak memory in a very real way.

Take the following function as an example:


HRESULT StartGraph( IGraphBuilder * pIGraphBuilder )
{
IMediaControl * pIMediaControl;
hr = pIGraphBuilder->QueryInterface( IID_IMediaControl, ( void ** ) &pIMediaControl );
if( FAILED( hr ) )
return hr;

return pIMediaControl->Run(); // THIS WILL LEAK A REFERENCE COUNT
}

This is how we would normally start a filter graph in DirectShow. This code technically works, but it has a serious flaw. Because it queries the filter graph manager for the IMediaControl interface, this increments the reference count on pIGraphBuilder. However, when we return, because IMediaControl was declared locally, it goes out of scope without ever being released, thus leaving behind an extra reference count on pIGraphBuilder. The above code is leaking a reference count, which means abandoned COM objects galore!

One way to (sort of) fix the above code would be:


HRESULT StartGraph( IGraphBuilder * pIGraphBuilder )
{
IMediaControl * pIMediaControl;
HRESULT hr = pIGraphBuilder->QueryInterface( IID_IMediaControl, ( void ** ) &pIMediaControl );
if( FAILED( hr ) )
return hr;

hr = pIMediaControl->Run();
if( FAILED( hr ) )
return hr; // THIS WILL LEAK A REFERENCE COUNT!

// Release our interface....
SAFE_RELEASE( pIMediaControl );
return hr;
}

There are still major flaws with this code. We successfully release the interface before exiting the function at the end; this will automatically de-increment the reference count on the filter graph manager. However, what if the call to IMediaControl->Run() fails? Again, we leak a reference count because we fail to release pIMediaControl! We successfully queried for the interface, which adds a reference to our Filter Graph Manager, but by exiting before we've called SAFE_RELEASE() we've again leaked a reference count. We could easily add another SAFE_RELEASE() call to the middle return, but consider this: what if this method was 100 lines long? 200 lines long? What if it had elaborate loops or other conditional logic? It becomes easy to miss a release, and the code is visually convoluted by clean-up logic.

The solution to this problem is to use Smart Pointers to manage reference counting. When a COM pointer wrapped with a Smart Pointer goes out of scope, it automatically calls Release(), thus alleviating the pain of manually releasing:


#include ; // For Smart Pointers!

...

HRESULT StartGraph( IGraphBuilder * pIGraphBuilder )
{
CComPtr pIMediaControl;
HRESULT hr = pIGraphBuilder->QueryInterface( IID_IMediaControl, ( void ** ) &pIMediaControl );
if( FAILED( hr ) )
return hr;

return pIMediaControl->Run();
}

Notice that we don't have to release the pointer at the end of the method; upon going out of scope, the Smart Pointer will automatically call Release().

Alternately, you can also use CComQIPtr (QI = Query Interface) for slightly cleaner code; the above could be written like so:


HRESULT StartGraph( IGraphBuilder * pIGraphBuilder )
{
CComQIPtr pIMediaControl( pIGraphBuilder );
if( !pIMediaControl )
return E_FAIL;

return pIMediaControl->Run();
}

Either method will work; the second is slightly cleaner but I prefer the former for more accurate HRESULTs.

There are still instances where you'll need to manually release a smart pointer--take the following GetPin() function for example:


//---------------------------------------------------------------//
// GetPin - returns a pin of the specified direction on the
// specified filter. Note that this will return connected or
// unconnected pins.
HRESULT GetPin( IBaseFilter * pFilter, PIN_DIRECTION PinDir, IPin ** ppPin )
{
if( ppPin == NULL || pFilter == NULL )
{
return E_POINTER;
}

CComPtr pEnum;
HRESULT hr = pFilter->EnumPins( &pEnum );
if( FAILED( hr ) )
{
return hr;
}

CComPtr pPin;
hr = pEnum->Next( 1, &pPin, 0 );
while( hr == S_OK )
{
PIN_DIRECTION ThisPinDirection;
hr = pPin->QueryDirection( &ThisPinDirection );
if( FAILED( hr ) )
{
return hr;
}

if( PinDir == ThisPinDirection )
{
// Found a match. Return the IPin pointer to the caller.
return pPin.CopyTo( ppPin );
}
// Release the pin for the next time through the loop.
pPin.Release();
hr = pEnum->Next( 1, &pPin, 0 );
}

// No more pins. We did not find a match.
if( hr == VFW_E_ENUM_OUT_OF_SYNC )
{
return VFW_E_ENUM_OUT_OF_SYNC;
}
else
{
return E_FAIL;
}
}

The above function is the same function defined in the DirectShow documentation, with several errors corrected. And, of course, no more sloppy raw COM pointers.

Note the IPin object pPin--because we're enumerating the filter for a pin, we have to manually call pPin.Release() before reusing the object. Also of note is the pPin.CopyTo() call, which is another convenient feature of smart pointers. CopyTo() should be used in the event of copying a smart pointer to a dumb pointer. However, in the above function, since the passed in pPin is either going to be a dereferenced smart pointer (which is, again, a dumb pointer) or a regular dumb pointer, the CopyTo() is appropriate.

One other feature of Smart Pointers is the overloaded assignment operator. Observe:


CComPtr pSomeFilter;


//Somewhere else
HRESULT CreateFauxFilter()
{
CComPtr pSomeOtherFilter;
HRESULT hr = pSomeOtherFilter.CoCreateInstance( CLSID_OfSomeOtherFilter );
if( FAILED( hr ) )
{
return hr;
}
else
{
// Here, we can use the "=" operator to copy one smart pointer
// to another smart pointer.
pSomeFilter = pSomeOtherFilter;
return hr;
}
}

So, pSomeFilter is assigned to pSomeOtherFilter, and when pSomeOtherFilter goes out of scope, it'll clean up any remaining reference counting issues. It's a handy way to only keep around a pointer if we know everything has occurred successfully. A common use of this is to instantiate all of your filter graphs with locally declared smart pointers, and only assign the smart pointers to your member variables at the end of the function.

You may think these are equivalent to the CopyTo() method of a CComPtr, but the assignment operator should only be used when explicitly copying one smart pointer to another. The CopyTo() should be used when copying a smart pointer to a dumb pointer.

Also, be mindful of accidentally mixing smart pointers, dumb pointers, and the assignment operator:


IBaseFilter * pDumbPointer;
CComPtr pSmartPointer;

pSmartPointer = pDumbPointer; // THIS IS OKAY (sort of)

pDumbPointer = pSmartPointer; // THIS IS VERY, VERY BAD!!

The really nasty thing about the latter assignment is that pDumbPointer will not equal NULL (thus evading many common checks for validity) and subsequent attempt to call any methods on the dumb pointer will result in Very Bad Things™. If you're mixing smart pointers with dumb pointers, consider removing the dumb pointers entirely, as the use of dumb pointers is generally a sign of a greater problem and using both is generally confusing and/or odd.

Wednesday, April 02, 2008

The N Habits of Highly Defective DirectShow Applications

First off, let me pay proper homage by linking to the inspiration for this post, The n Habits of Highly Defective Windows Applications. If you do Windows development, I highly recommend reading through this article; it covers numerous pitfalls in Windows application development.

Anyway, I stumbled upon that article and though that it could use a DirectShow version, since there are many poor examples of DirectShow coding floating around. Many of the defects discussed in this post are common and have been addressed in the newsgroups numerous times. Generally when something is going amiss in a DirectShow program, it's for one of the following reasons.

If you find that I've listed something you're doing (or not doing) in your program, don't take it personally. I know most of the below are defects from personal experience, which is why I've been nice enough to compile them so you don't have to suffer like I did (and trust me, a messed up DirectShow program is a way to truly suffer). I think of this article as a means of helping people improve their code, rather than an attempt on my behalf to belittle other people's coding practices.

In keeping with the original article's overall layout, I've assigned a severity to defects:
  • Potentially Fatal: The use of this technique shouldn't work at all. If it appears to, it is an illusion.
  • Potentially Harmful: There is an excellent chance that minor changes in the program will result in a malfunctioning program, or necessitate gratuitous changes that a proper program construction would not have required.
  • Inefficient: this covers most polling situations. You will be wasting vast amounts of CPU time and accomplishing nothing.
  • Poor Style: While the code works, it represents poor style of programming. It should be cleaned up to something that is manageable.
  • Deeply Suspect: While the code works, there is almost certainly a better way to accomplish the same task which would be simpler, faster, cleaner, or some other suitably positive adjective. Generally, there are sometimes valid reasons for using the technique specified, but they are fairly rare and easily identified. You probably don't have one of these reasons.


Not using Smart Pointers
Severity: Potentially Harmful, Poor Style, Deeply Suspect

The most beneficial thing you can do for your program is use Smart Pointers instead of declaring regular COM pointers.

What are smart pointers, you ask? Smart Pointers are a simple wrapper class around a COM pointer which help manage the object's scope, in addition to several other nice perks. Instead of doing this:

IGraphBuilder * pIGraphBuilder; // A regular stupid pointer. This is bad.
HRESULT hr = CoCreateInstance( CLSID_FilterGraph, NULL, CLSCTX_INPROC_SERVER, IID_IGraphBuilder, ( void ** ) &pIGraphBuilder ); // yuk!

...try doing this:

CComPtr pIGraphBuilder; // A Smarter pointer--much better.
HRESULT hr = pIGraphBuilder.CoCreateInstance( CLSID_FilterGraph ); // just a tad less ugly than the one above

Using smart pointers will:

  • Make your code much cleaner.
  • Make your code much safer.
  • Enable you to do things that normally would be difficult, clumsy, and/or dangerous with normal pointers.

Since this is such a huge subject and so many people make the mistake of not using Smart Pointers(this is unsurprising, given that the DirectShow documentation itself does not use smart pointers--shame on MSFT!), I've written an entire article devoted to this very subject. Also, The March Hare (another newsgroup junkie) has a quick tutorial on his site--click here to visit that article.

Not using Smart Pointers will make any substantial DirectShow program buggy, unreliable, unstable, and prone to leaking memory. Using them also makes DirectShow code more maintainable and easy to read.

Using wrong synchronization primitives (i.e.: mutex, critical sections, etc.) for a given task.
Severity: Inefficient, Poor Style

Programming audio and video is a threaded endeavor, by its very nature. As such, Microsoft has provided us with all sorts of ways to manage threads. The three most common ways of doing this are:

  1. Mutexes - A mutex is a synchronization primitive that prevents two threads from executing the same code simultaneously. The two threads do not need to be in the same process space. See here for more information.
  2. Critical Sections - A Critical Section is a synchronization primitive that prevents two threads from executing the same code simultaneously (yes, its function is identical to that of a mutex). The two threads need to be in the same process space. See here for more information.
  3. Semaphores - A semaphore is a synchronization primitive that maintains a count between zero and a specified maximum value. The count is decremented each time a thread completes a wait for the semaphore and incremented each time a thread releases the semaphore. When the count reaches zero, no more threads can successfully wait for the semaphore object state to become signaled. The state of a semaphore is set to signaled when its count is greater than zero, and non signaled when its count is zero. The semaphore object is useful in controlling a shared resource that can support a limited number of users. It acts as a gate that limits the number of threads sharing the resource to a specified maximum number. See here for more information.

Phew!

Because a mutex actually shares a lock between processes (rather than within the same process space), it involves more overhead than a critical section, which only has a scope of the host process.

Semaphores aren't typically used in DirectShow coding, because they're more applicable to applications where the need to limit access to a given number of threads is a requirement (e.g.: database applications, web servers, etc.). While a semaphore with a one-thread limit is functionally the same thing as a mutex or critical section, the performance is not.

Generally, a critical section is the correct primitive to be using in DirectShow. Using anything else is suspect.

Lastly, using critical sections in filter and DirectShow code is easier as some very kind person has been nice enough to write the two classes that are the subject of our next bad habit:


Not using CCritSec and CAutoLock
Severity: Potentially Harmful, Inefficient, Poor Style, Deeply Suspect

CCritSec and CAutoLock are two classes provided by the DirectShow SDK that help simplify the implementation of thread synchronization.

The CCritSec class wraps a critical section object and contains methods to lock and unlock the critical section at will--additionally, it handles created and destruction of the critical section, making it very handy for keeping your code leak free.

However, the CAutoLock is where things get really slick. Observe the following code:


HRESULT CMyClass::SomeMethod()
{
// We can't have threads accessing this at will!
CAutoLock MyLock( &myCCritSecInstance );

// do something...

// Here we can return without releasing the lock--because the
// destructor of the CAutoLock class takes care of it for us
return S_OK;
}

...The beauty of the above code is that you can't forget to release the lock to your critical section because it's managed by our CAutoLock instance. This code, on the other hand, is heinously unsafe:

HRESULT CMyClass::SomeMethod()
{
myCCritSecInstance.Lock();

// Do something for a few hundred lines of code where we potentially
// forget to release the above lock, encounter an exception, or
// have some sort of failure that we didn't account for. This results in a
// deadlock.

myCCritSecInstance.Unlock();

return S_OK;
}
...the bad thing about it is that the programmer must do their own accounting throughout the code. It can be done, but the probability of programmer error increases substantially, and the resulting code is difficult to maintain and troubleshoot.

Why make an accounting nightmare? It's much easier and more reliable to let C++ handle scope than to attempt to deal with manually locking and unlocking critical sections. There's also an entire article devoted to using these classes for thread protection.


Not protecting graph construction and destruction with a synchronization primitive.
Severity: Potentially Fatal


Because graph construction and destruction can take substantial amounts of time to happen, the possibility of these two procedures overlapping becomes quite realistic.

I've seen this error several times. Somebody will post code that looks something like:


// Somewhere, Graph Builder is defined...
CComPtr m_pGraph;

// Function to build graph
HRESULT BuildMyGraph()
{
HRESULT hr = m_pGraph.CoCreateInstance( CLSID_FilterGraph );

// ...a couple hundred lines of code and setup pass

hr = m_pGraph->Render( &pSomeIPin );
return hr;
}


// Function to tear down graph
HRESULT TearDownGraph()
{
m_pGraph.Release();
return S_OK;
}

...there's nothing wrong with the above code, except for the fact that m_pGraph isn't protected by any thread synchronization mechanism. If your calls to the functions are protected by a critical section, great--read no further. Otherwise, the above code is dangerous because someone may call TearDownGraph() right in the middle of a call to BuildMyGraph(), which results in m_pGraph being a null pointer and ultimately an application crash.

If a programmer is really unlucky, the above code will always work until someone runs it on a dual core machine, or a faster/slower machine than your development machine, etc. Then they have something that worked without fail in the office, but crashes and burns out in the field.

Ideally, the above should be protected with a critical section that makes it impossible to call the two functions simultaneously. One would have to wait for the other to finish, and vice-versa.

Ideally, the above code should resemble something like so in order to be thread safe:

// Function to build graph
HRESULT BuildMyGraph()
{
// LOCK THIS CODE
CAutoLock cAutoLock( &m_pMyCCritSecInstance );
CComPtr m_pGraph;
HRESULT hr = m_pGraph.CoCreateInstance( CLSID_FilterGraph );

// ...a couple hundred lines of code and setup pass

m_pGraph->Render( &pSomeIPin );
return hr;
}


// Function to tear down graph
HRESULT TearDownGraph()
{
// LOCK THIS CODE
CAutoLock cAutoLock( &m_pMyCCritSecInstance );

m_pGraph.Release();
return S_OK;
}

This is a pretty simplified example, but the point stands.

Assigning smart pointer to a regular pointer.
Severity: Potentially Fatal

One of the benefits of smart pointers is that you can assign one smart pointer to another smart pointer because someone has cleverly overloaded the "=" operator. This is very useful; you can use local smart pointers to build a graph and only assign them at the end of the build process, thus never keeping around any permanent COM pointers unless necessary. However, trying to assign a regular pointer to a smart pointer is a big, big mistake.

I've seen programmers do this several times. A lot of this comes from the fact that people typically don't use smart pointers to begin with because none of the DirectShow samples use them. So you'll see something that ends up like so:


// Somewhere:
IGraphBuilder * m_pIGraphBuilder;

// Somewhere else:
CComPtr pIGraphBuilder;
pIGraphBuilder.CoCreateInstance( CLSID_FilterGraph );

// And, somewhere else...
m_pIGraphBuilder = pIGraphBuilder; // this is bad!
...The insidious thing about this error is that m_pIGraphBuilder will appear to be a valid pointer, but drilling down to the guts, it'll be null and ultimately result in a crash.

Not calling CoInitialize and CoUninitialize on new threads.
Severity: Potentially Fatal or Harmful

One of the fundamental rules of modern-day COM is that every thread that uses COM should first initialize COM by calling either CoInitialize or CoInitializeEx. Not doing so can result in some strange behavior--if you're lucky, the behavior will just be failed COM API calls. If you're not so lucky, the problems can be rather sublime.

An example of correctly calling CoInitialize on a new thread:


unsigned int dwThreadId = 0;
HANDLE hThreadHandle;
hThreadHandle = (HANDLE) _beginthreadex( NULL, 0, BuildMyFilterGraph, pMyData, 0, &dwThreadId );

...the above code launches a new thread, calling some generic method/function called BuildMyFilterGraph. Now, in BuildMyFilterGraph:

unsigned int __stdcall BuildMyFilterGraph( LPVOID lpParam )
{
CoInitializeEx( NULL, COINIT_APARTMENTTHREADED );

// Build our graph, do something, etc....

// When we're ready to exit the thread
CoUninitialize();
return 1;
}
So, the above calls CoInitializeEx when the thread is launched, and calles CoUninitialize when it's all done. Great.

However, the above code has the same issue that not using smart pointers has--what if the thread exits before calling CoUninitialize? What if the function is modified by another programmer who exits the thread and forgets to call CoUninitialize? We could account for each and every one of these exits by calling CoUninitialize directly, but such a solution is clumsy at best, especially given that DirectShow code tends to be sequential and the accounting often snowballs out of control.

The solution to this is actually quite simple:


class CInitCom
{
public:
CInitCom(DWORD dwCoInit = COINIT_APARTMENTTHREADED )
{
CoInitializeEx( NULL, dwCoInit );
}
~CInitCom()
{
CoUninitialize();
}
};
A coworker of mine clued me in on this class, and it's quite elegant: the constructor calls CoInitializeEx, and the subsequent call to CoUninitialize is managed entirely by the scope of the class.

Using this class, our BuildMyFilterGraph method/function now becomes:


unsigned int __stdcall BuildMyFilterGraph( LPVOID lpParam )
{
CInitCom cInitCom;

// Build our graph, do something, etc....

// Here, we just exit. The call to cInitCom's destructor will take care
// of calling CoUninitialize for us.
return 1;
}
We no longer have to clean up after ourselves. The code is protected from people exiting or modifying the function/method in strange ways, and much cleaner overall.


Deriving transform filter from CTransInPlace when CTransform should be used.
Severity: Inefficient, Deeply Suspect


Probably once a month or so you'll see someone post a plea for help on the newsgroups about how their transform filter works, but it's really slow. This is almost always a consequence of people deriving their filter from CTransInPlaceFilter instead of CTransformFilter.

The difference between CTransInPlaceFilter and CTransformFilter can appear to be subtle, but they're really two very different creatures. Many people are attracted to the very simple implementations of CTransInPlaceFilter derived filters, which can be as short as fifty lines of code (see the null filter sample in the DirectShow samples for a good example of this). CTransInPlaceFilter derived implementations modify the frame data of passing samples in its original buffer and don't have their own allocator.

To paraphrase the notes in the base classes defining In-Place Transform Filters: An in-place transform tries to do its work in someone else's buffers. It tries to persuade the filters on either side to use the same allocator (and for that matter the same media type). So, essentially, an In-Place Transform filter that is positioned directly upstream from a video rendering filter typically ends up having access to frame data after it already resides in video memory.

Writing to video memory is really, really fast--reading from video memory is really, really slow. So if you read from the buffer in the IMediaSample supplied in the Transform method of a CTransInPlaceFilter, you can expect to have seriously slow performance. Writing to the buffer is very quick and incurs no additional penalty, but any sort of read operation will incur steep penalties.

Moral of the story: don't read from video memory. The most common way this happens is people deriving their transform filters from CTransInPlaceFilter instead of CTransformFilter, which has its own allocators. CTransformFilter is the appropriate base class to use if you're going to be reading from a buffer as it passes through your transform filter.


Not Checking returned HRESULT values
Severity: Potentially Harmful, Poor Style, Deeply Suspect

Almost all DirectShow functions (and COM functions, for that matter) return an HRESULT data type. This result indicates if a given function was successful or if it failed. Often times, the failure is very specific and can lead to easy troubleshooting of a problem. Other times, a function returns success, but it has multiple successful returns.

Knowing that, it's very clear that not checking an HRESULT for failure or success is a great way to write a program that fails miserably.

Observe the following function:


// Code creates a Filter graph manager and assigns it to a member
// variable.
HRESULT InstantiateGraphbuilder()
{
CComPtr pIGraphBuilder;
pIGraphBuilder.CoCreateInstance( CLSID_FilterGraph );

m_pIGraphBuilder = pIGraphBuilder;
return S_OK;
}
So, the above code has several flaws. For starters, CoCreateInstance returns an HRESULT, which the above code does absolutely nothing with. It falls right on the floor. If you forgot to initialize COM and called the above code, it would fail, attempt to assign the pointer, and the programmer would have no idea why the program failed, simply because there was no check for the HRESULT return value. This is a somewhat simplified example of forgetting to check the HRESULT, but the general idea is the same.

The second flaw is returning S_OK, which is the general HRESULT value for success--this is also pointless. This denies the calling function from making sure things were successful or taking any sort of action based on a more specific return value. As it stands, the above code might as well have a void return value.

A much better implementation:


// Code creates a Filter graph manager and assigns it to a member
// variable.
HRESULT InstantiateGraphbuilder()
{
CComPtr pIGraphBuilder;
HRESULT hr = pIGraphBuilder.CoCreateInstance( CLSID_FilterGraph );
if( FAILED( hr ) ) // CHECK RETURN VALUE USING FAILED MACRO
{
return hr;
}
else
{
m_pIGraphBuilder = pIGraphBuilder;
return hr;
}
}

The above code checks the return value of the CoCreateInstance using the FAILED() macro. You can also check an HRESULT for success using the SUCCEEDED() macro, which also takes an HRESULT as a parameter and functions in exactly the opposite way as FAILED().

This is really just a basic example; there are literally thousands of possible return types for an HRESULT, and certain methods have their own specific set of HRESULT values they return that should be checked consistently.

Lastly, you can do the following to get more information about a given error:

#include

HRESULT hr = S_OK;

// we encounter some error which has been assigned to hr

CString Error( ::DXGetErrorString9( hr ) );
Error += ::DXGetErrorDescription9( hr );

...this is nice because it's easy to output it to a message log or display the error in English rather than some weird value in hex. Additionally, there's a utility in the DXSDK called "DirectX Error Lookup"; as the name implies it will look up a given hex or decimal value and display the error for you.

Forgetting to catch and examine HRESULT values consistently is, without a doubt, deeply suspect. Additionally, make sure functions return HRESULT values that are useful.

Using a do...while(0) loop
Severity: Potentially Harmful, Poor Style, Deeply Suspect

Observe the following function:

HRESULT ShowFilterPropertyPage(IBaseFilter *pFilter, HWND hwndParent)
{
HRESULT hr;
ISpecifyPropertyPages *pSpecify=0;

if (!pFilter)
return E_NOINTERFACE;

// Discover if this filter contains a property page
hr = pFilter->QueryInterface(IID_ISpecifyPropertyPages, (void **)&pSpecify);
if (SUCCEEDED(hr))
{
do
{
FILTER_INFO FilterInfo;
hr = pFilter->QueryFilterInfo(&FilterInfo);
if (FAILED(hr))
break;

CAUUID caGUID;
hr = pSpecify->GetPages(&caGUID);
if (FAILED(hr))
break;

// Display the filter's property page
OleCreatePropertyFrame(
hwndParent, // Parent window
0, // x (Reserved)
0, // y (Reserved)
FilterInfo.achName, // Caption for the dialog box
1, // Number of filters
(IUnknown **)&pFilter, // Pointer to the filter
caGUID.cElems, // Number of property pages
caGUID.pElems, // Pointer to property page CLSIDs
0, // Locale identifier
0, // Reserved
NULL // Reserved
);

CoTaskMemFree(caGUID.pElems);
FilterInfo.pGraph->Release();

} while(0);
}

// Release interfaces
if (pSpecify)
pSpecify->Release();

pFilter->Release();
return hr;
}
This is an actual function taken out of the DirectShow samples provided by Microsoft. The use of the do...while(0) loop is strange for two reasons:

  1. If you're like me and chronically dyslexic, it looks as though the loop never exits because the break points will rarely (if ever) get hit, and
  2. It will exit, because it's a while(0) loop--which begs the very simple question: WHY?

Why would a programmer do such a strange thing? The removal of the loop causes the function to work exactly the same way, except for one small thing: the programmer didn't use smart pointers, which meant they had to find alternate ways to clean up. So in the event of an error, they "break" out of the loop and clean up after themselves (albeit poorly--the code will leak a reference inside the FILTER_INFO structure if the second break is executed).

If you're trying to find creative ways to clean up after COM pointers, please, just take a look at smart pointers to avoid the above, which is absolute foolishness. A much, much better rewrite of this function is:


HRESULT ShowFilterPropertyPage( IBaseFilter * pFilter, HWND hwndParent )
{
if( !pFilter )
{
return E_POINTER;
}

CComPtr pSpecify;

// Discover if this filter contains a property page
HRESULT hr = pFilter->QueryInterface( IID_ISpecifyPropertyPages, ( void ** ) &pSpecify );
if( SUCCEEDED( hr ) )
{
FILTER_INFO FilterInfo;
hr = pFilter->QueryFilterInfo( &FilterInfo );
if( FAILED( hr ) )
{
return hr;
}

CAUUID caGUID;
hr = pSpecify->GetPages(&caGUID);
if (FAILED(hr))
{
FilterInfo.pGraph->Release();
return hr;
}

// Display the filter's property page
OleCreatePropertyFrame(
hwndParent, // Parent window
0, // x (Reserved)
0, // y (Reserved)
FilterInfo.achName, // Caption for the dialog box
1, // Number of filters
(IUnknown **)&pFilter, // Pointer to the filter
caGUID.cElems, // Number of property pages
caGUID.pElems, // Pointer to property page CLSIDs
0, // Locale identifier
0, // Reserved
NULL // Reserved
);

CoTaskMemFree(caGUID.pElems);
FilterInfo.pGraph->Release();
}

return hr;
}

...no strange while loop, and no leaks.

Using a goto Statement
Severity: Potentially Harmful, Poor Style, Deeply Suspect


This is really a variant on the above issue (use of a do...while(0) loop) and not using smart pointers.

Statements like goto should not be used, because they produce unmanageable code. More importantly, people almost exclusively use the goto statement as a means of cleaning up after COM pointers in the event of an error. Something much like so:


HRESULT SomeFunction()
{
IBaseFilter * pSomeFilter; // a very friendly dumb pointer
HRESULT hr = pSomeFilter.CoCreateInstance( CLSID_SomeFilter );
if( FAILED( hr ) )
goto Exit;

// similar error checking for another couple hundred lines of code...

Exit:
SAFE_RELEASE( pSomeFilter );
return hr;
}

None of this nonsense is necessary with smart pointers. Much to my dismay, Microsoft even has this macro available in the WMFSDK and it is commonly used throughout their samples:

#ifndef GOTO_EXIT_IF_FAILED
#define GOTO_EXIT_IF_FAILED(hr) if(FAILED(hr)) goto Exit;
#endif
...this is employed liberally throughout the WMF samples to help deal with cleaning up errant COM pointers. I've seen this exact macro used in DirectShow code as well; needless to say, this is poor code! Not only does it employ an already suspect goto statement, but it will ultimately produce unmanageable, error prone code that's difficult to support.

Never use a goto statement in your DirectShow code. If you're tempted to use one, ask yourself the following questions:

  1. Why would I use a goto statement to clean up my COM pointers?
  2. Is there something better to use?

...and then go read up on smart pointers. Again, if you're having issues cleaning up after COM pointers, the simple, effective solution to that problem is to use Smart Pointers.


Leaking memory or ending up with invalid pointers while using AM_MEDIA_TYPE
Severity: Potentially Fatal


Because of the way AM_MEDIA_TYPE has been defined, it is very easy to leak memory using it. This problem is surprisingly pervasive, with examples of potential leaks riddled throughout the SDK samples.

First, let's look at how AM_MEDIA_TYPE is definied:


typedef struct _MediaType
{
GUID majortype;
GUID subtype;
BOOL bFixedSizeSamples;
BOOL bTemporalCompression;
ULONG lSampleSize;
GUID formattype;
IUnknown * pUnk;
ULONG cbFormat;
BYTE * pbFormat;
} AM_MEDIA_TYPE;
AM_MEDIA_TYPE is a structure used to define the format of a given audio or video type. Most of the variables are pretty self-explanatory. However, note the GUID value "formattype"; this variable defines a type that is subsequently represented with another structure. This "other" structure is referenced as a BYTE pointer, pbFormat, and a variable to specify the length of the structure, cbFormat. For example, pbFormat often points to a VIDEOINFOHEADER or WAVEFORMATEX structure.

pbFormat can, in theory, point to just about anything, and of just about any length. This can lead to some pretty elaborate memory leaks. For example, this code excerpt is from the contrast filter sample:


AM_MEDIA_TYPE * pAdjustedType = NULL;
pMediaSample->GetMediaType(&pAdjustedType);

if(pAdjustedType != NULL)
{
if(CheckInputType(&CMediaType(*pAdjustedType)) == S_OK)
{
m_pInput->CurrentMediaType() = *pAdjustedType;
CoTaskMemFree(pAdjustedType);
}
else
{
CoTaskMemFree(pAdjustedType);
return E_FAIL;
}
}

The above code looks fine--the AM_MEDIA_TYPE pointer is created using GetMediaType, and if created, should be destroyed using CoTaskMemFree().

Sadly, this is not the case--the above code will leak sizeof(cbFormat) bytes with every AM_MEDIA_TYPE that is successfully created. The reason for this is GetMediaType returns a full AM_MEDIA_TYPE structure, and internally will call CoTaskMemAlloc to allocate pbFormat--calling CoTaskMemFree merely deletes the AM_MEDIA_TYPE structure, and will not clean up the associated pbFormat structure. To delete this format block, DeleteMediaType should be called. DeleteMediaType deletes both the AM_MEDIA_TYPE structure and also the pbFormat structure. For reference, it looks like so:

void WINAPI DeleteMediaType(AM_MEDIA_TYPE *pmt)
{
// allow NULL pointers for coding simplicity

if (pmt == NULL)
{
return;
}

FreeMediaType(*pmt);
CoTaskMemFree((PVOID)pmt);
}

// DeleteMediaType calls FreeMediaType, although FreeMediaType can
// be used to only delete the pbFormat structure for an AM_MEDIA_TYPE
void WINAPI FreeMediaType(AM_MEDIA_TYPE& mt)
{
if (mt.cbFormat != 0)
{
CoTaskMemFree((PVOID)mt.pbFormat);

// Strictly unnecessary but tidier
mt.cbFormat = 0;
mt.pbFormat = NULL;
}

if (mt.pUnk != NULL)
{
mt.pUnk->Release();
mt.pUnk = NULL;
}
}

...DeleteMediaType calls FreeMediaType (which deletes pbFormat) and then calls CoTaskMemFree, which deletes the rest of the AM_MEDIA_TYPE structure.

Another major problem is using the assignment operator between two AM_MEDIA_TYPE structures. The problem with this is that it will only copy the value of the pbFormat pointer, and not the data it actually points to. Should the right hand argument be deleted correctly (although assuming someone is trying to use the "=" operator between AM_MEDIA_TYPE, they might not be deleting it correctly anyways), then the pointer in the copy will be null, which can result in some rather strange behavior when DirectShow is asked to handle a bogus pbFormat block.

A better solution to all of this is to avoid the use of AM_MEDIA_TYPE whenever possible, and instead use CMediaType. CMediaType is a class derived from an AM_MEDIA_TYPE structure that includes methods in the destructor that make it much more difficult to leak memory. It also overloads the assignment operators, so in most instances, it will copy the pbFormat block automatically. Basically, it provides a lot of protection against leaking memory and having bogus pointers.

Mixing AM_MEDIA_TYPE and CMediaType can still be nasty, however:

STDMETHODIMP SomeClass::GetAMMediaType( AM_MEDIA_TYPE * pAMMEDIATYPE )
{
*pAMMEDIATYPE = *m_pCMediaType;
return S_OK;
}

The above will work, but only so long as m_pCMediaType is a valid CMediaType structure. If m_pCMediaType is destroyed, the pointer in pAMMEDIATYPE is no longer valid, because it merely copied the value of pbFormat and not the contents. It would be much better to do this:

STDMETHODIMP SomeClass::GetAMMediaType( CMediaType * pCMediaType )
{
*pCMediaType = *m_pCMediaType;
return S_OK;
}

...now the format block will be copied automatically, and because the type here is CMediaType, deallocation is managed automatically.

Not listening for and responding to DirectShow events
Severity: Potentially Harmful, Deeply Suspect

DirectShow provides a mechanism for listening and responding to events from the underlying filter graph. Via the IMediaEvent and IMediaEventEx interfaces, an application can listen for events, many of which are highly useful and/or informative.

Not all of the events sent by the underlying filter graph and the filter graph manager are useful, but in many instances, failures in the baseclasses or the underlying graph are communicated exclusively by the DirectShow eventing. The underlying implication here is pretty straightforward. If an application isn't listening for events, those failures:

  1. Fall on deaf ears--the application doesn't know something has gone wrong, and:
  2. Are almost always impossible to debug after the fact, because the specific HRESULT failure returned in the event interface, as well as the specific event, are long gone. Had the events been received, the application can potentially recover from the error, and also log the problem for future troubleshooting.

To list one example, I troubleshot a DirectShow application with several custom filters, including a custom source filter derived from CSource and CSourceStream. The source filter was logging errors with a custom logging interface. In one run of the application, the Deliver() call in the overridden DoBufferProcessingLoop returned 0x8004020B (VFW_E_RUNTIME_ERROR: A run-time error occurred. How informative!). Going through the baseclasses, I quickly noticed that this error was commonly associated with render and transform filters, and whenever it occured, it would send EC_ERRORABORT along with an HRESULT detailing the failure. Some filter downstream from the source filter had encountered a runtime error, and was communicating it both via a failure to the Deliver call, and a much more informative event to the controlling application.

Because the application was not listening for events, it had no idea that a real issue had even occured. The source filter continued chugging away, for hours, doing almost nothing (well, nothing besides logging ridiculous amounts of VFW_E_RUNTIME_ERROR failures) and oblivious to the fact that a serious error had occured. To add insult to injury, because the event was not received (and thus no HRESULT was available for further troubleshooting), it's almost impossible to know "why" or "where" the problem even occured. It could have been in any of the several downstream filters, and for any number of reasons.

Mitigating this is very, very easy:

  • Make sure that your application listens for events.
  • Make sure it responds to events.
  • Make sure you log extranious events for post-run analysis. Not doing so will result in erratic behavior and strange failures that are impossible to isolate after they've occured.



Not using DirectShow eventing in custom filters, or using a secondary eventing scheme
Severity: Potentially Harmful, Deeply Suspect

I've seen several custom filters now that implement their own home-baked eventing scheme. This is bad for several reasons:

  • DirectShow provides an eventing mechanism, free of charge, that filters can leverage. Not using it means someone is developing something that already exists. Re-inventing the wheel = bad
  • The DirectShow eventing is asynchronous. Not using asynchronous eventing (which I've seen several instances of now) means the possibility of very elaborate deadlocks becomes much greater.
  • An application can consolidate two eventing interfaces into one. Really, why make things difficult? Multithreading is complicated as it is; having redundant eventing handlers (e.g.: the standard DShow eventing, as well as some other custom eventing) is literally begging for a few extra late nights at the office.

To elaborate on all of the above:

DirectShow filters can leverage the IMediaEventSink interface, which allows filters to notify the filter graph manager of events via the Notify() method. Applications should not use this interface; it is specifically for filters. Filters may also define custom events with the range of EC_USER and higher, with a few relatively minor caveats:

  • The Filter Graph Manager cannot free the event parameters using the normal IMediaEvent::FreeEventParams method. The application must free any memory or reference counts associated with the event parameters.
  • The filter should only send the event from within an application that is prepared to handle the event. (Possibly the application can set a custom property on the filter to indicate that it is safe to send the event.)

That being said, there is a very comprehensive listing of events, and most filters would probably not need to define custom events.

The other really helpful thing about using IMediaEventSink::Notify is not having to worry about sending off events synchronously. Sending a synchronous event from the CSourceStream's worker thread that causes the graph to get torn down is instantaneous deadlock. DirectShow is heavily threaded; between implementing my own asynchronous eventing service and simply leveraging the standard one provided to me, the choice becomes rather obvious.

Lastly, the calling application can now centralize graph handling in one routine. There are not multiple interfaces to reconcile, and assuming the second eventing interface is asynchronous (like it should be), no synchronization issues between the two handlers.

Make life easy: always use the standard DirectShow eventing in custom filters unless there is absolutely a need to do otherwise. Quite frankly, I can't think of an instance where the need would be absolute, but always and never are two words to always remember to never use.


Registering Filters with the Operating System
Severity: Potentially Harmful, Deeply Suspect

First off, I hesitate to list this defect. After all, I am essentially telling you not to do what the documentation tells you to do. But after supporting a production application for the last several years, I am of the opinion that anywhere you are using Intelligent Connect, your application will (sooner or later) fail in the wild. By using this feature of DirectShow, you are exposed to any arbitrary filter (or filters) the user installs (coughffdshowcough). Other downsides to filter registration include people being able to re-use your filters, making your application easier to reverse-engineer, and exposing settings in the registry that can be modified by third-party applications. You cannot count on filter merit to save you.

Simply put, you're asking for trouble. In the case of my application, it took a year or two, but one day a support case came in where the application was crashing. The source? I had forgotten to change a small piece of the application to use ConnectDirect() rather than Connect(), which resulted in my filter graph picking up some rogue filter. I was crashing inside someone else's code. I had previously removed all of the Connect() calls, since those had resulted in crashing in the wild via the same mechanism, but I missed one spot when I added a new feature to the application. And surprisingly, it caught up with me.

One other substantial pain-point with respect to registering filters is registration typically happens at install-time, so it's one more thing that can potentially cause the installer to fail. DirectShow filters often end up with numerous dependancies (many of my filters have dependancies on several other runtimes), and if any of them are unfulfilled, the filter will not register, resulting in a failed installer or error messages the user doesn't understand. Sometimes all that needs to happen is the filters need to be re-registered after the installer has run, but if you avoid the registry, you avoid this problem completely.

The solution? Do not register your filters. Simply instantiate them with new.

(addendum: this advice doesn't apply if you are in fact attempting to integrate with existing applications. If your filter is specific to your application, then consider not registering and using ConnectDirect() to manually build your graph)


Not using IFileSourceFilter in Custom Filters
Severity: Poor Style, Deeply Suspect

IFileSourceFilter is an interface "...to set the file name and media type of the media file that they are to render." This may sound like a minor interface, but the advantages of using IFileSourceFilter are huge. First of all, it is the standard interface for configuring source filters, so suddenly any code that uses IFileSourceFilter will be capable of loading up your filter. Second, testing your filters in applications like GraphEdit becomes trivial. Lastly, should you want to register a custom protocol or file type and associate it with your filter, you must implement IFileSourceFilter.

Do you have to implement IFileSourceFilter? No, of course not. But, without this interface, your filter is largely incompatible with most existing DirectShow applications, and people using your filter will have to do a lot of extra work to make it all happen. Your filter is also much more difficult to test because you can't fire it up in GraphEdit. And it also precludes you from using your filter in Windows Media Player, Windows Media Center, and a whole host of other applications that depend on this standard interface. In general, source filters should always implement IFileSourceFilter.

Wednesday, March 12, 2008

IsBad(Enum.IsDefined) == true

There isn't much to say about Enum.IsDefined that hasn't been said before. Much of the confusion about why this method is bad stems from the fact that many people don't understand how Enum types have been implemented in .NET. So let's start by reviewing .NET's Enum implementation.
Consider the following enum:

enum Animal
{
cat = 0,
dog,
bird,
cow,
pig,
}

...we've set cat to be equivalent to integer value 0, so dog will be 1, bird is 2, etc. .NET allows us to specify enum values explicitly (as has been done with cat), or have them be implied (as has been done with all of the other values in the enum). This is sort of nice; we can now write code that looks like:

Animal hopefullyIAmACat = (Animal)0;
Console.WriteLine(hopefullyIAmACat);

This prints:

cat

Super. We've successfully taken an integer value and converted it to our enum type.

Now for something completely different:

Animal notSoSureAboutThisAnimal = (Animal)(-1);
Animal orThisOne = (Animal)5;
Animal definitelyNotSureAboutThisAnimal = (Animal)0.0M;
Animal ohNoes = (Animal)1.1;

Console.WriteLine(notSoSureAboutThisAnimal);
Console.WriteLine(orThisOne);
Console.WriteLine(definitelyNotSureAboutThisAnimal);
Console.WriteLine(ohNoes);

To the surprise of many, this not only compiles, but runs exception free:

-1
5
cat
dog

You might be thinking this is a bug, but this is by design. To get at why such a design decision was made, we need to fully understand C#'s enum implementation. From the C# language specification:
11.1.9 Enumeration types
An enumeration type is a distinct type with named constants. Every enumeration type has an underlying type, which shall be byte, sbyte, short, ushort, int, uint, long or ulong. Enumeration types are defined through enumeration declarations (§21.1). The direct base type of every enumeration type is the class System.Enum. The direct base class of System.Enum is System.ValueType.


There are also specific sections which explain implicit and explicit conversions with respect to enumerations:
13.1.3 Implicit enumeration conversions
An implicit enumeration conversion permits the decimal-integer-literal 0 to be converted to any enum-type.

13.2.2 Explicit enumeration conversions
The explicit enumeration conversions are:
•From sbyte, byte, short, ushort, int, uint, long, ulong, char, float, double, or decimal to any enum-type.
•From any enum-type to sbyte, byte, short, ushort, int, uint, long, ulong, char, float, double, or decimal.
•From any enum-type to any other enum-type.
An explicit enumeration conversion between two types is processed by treating any participating enum-type as the underlying type of that enum-type, and then performing an implicit or explicit numeric conversion between the resulting types. [Example: Given an enum-type E with and underlying type of int, a conversion from E to byte is processed as an explicit numeric conversion (§13.2.1) from int to byte, and a
conversion from byte to E is processed as an implicit numeric conversion (§13.1.2) from byte to int.]


By definition, enums can be explicitly cast to and from almost all of .NET's fundamental value types, so assigning my Animal enum to be "0.0M" invokes a cast from Decimal to int. The decimal gets hacked off, resulting in a cat.

This malleability brings up a couple of huge questions. Brad Abrams brings up this point:
It’s a know issue that adding values to enums is bad (from a breaking change perspective), WHEN someone is exhaustively switching over that enum.

Case in point: assume someone is iterating over my Animal enum, and writes the following code:

switch (ohNoes)
{
case Animal.pig:
break;
case Animal.dog:
break;
case Animal.cow:
break;
case Animal.cat:
break;
default:
// This one MUST be a bird!
break;
}

...of course, it won't be a bird when someone changes the enum to include an elephant entry; suddenly default maps to two values. Also, more importantly, in the above code default is a catch all! Everything that doesn't fall into the range--for example, negative one--is going to hit the default switch.

This brings us back around to Enum.IsDefined, which returns true of the supplied value is defined by the Enum. Writing some code like so is very tempting:
       if (!Enum.IsDefined (typeof(Animal), 5)
throw new InvalidEnumArgumentException();

...but this is, again, fraught with peril. Our Animal type is defined at runtime. What if someone later adds elephant to our enum? The code following this check still needs to be capable of dealing with elephant or any future types that may be defined in the enum.

Furthermore, Enum.IsDefined is pricy. And by pricy, I mean all sorts of reflection and boxing and junk under the covers. I found this call being used in SharpMap, and removing it resulted in some very respectable performance gains in a tight loop used to parse some binary data:
I tested your (suggestion to remove Enum.IsDefined) with the method below. First with the polygons countries.shp that is in the DemoWebSite App_Data. This was 16% faster. Then with points in cities.shp. This was 85% faster, nice.

Pretty clear win: the project looses some potential versioning dilemmas, and gains some sizable performance in one of the most heavily used routines.

Moral of the story: enums are not objects that handle versioning well. I personally believe they should only be used where the enumeration is clear and not likely to be expounded upon in the future. Using Enum.IsDefined should be avoided.

Thursday, March 06, 2008

Starting My Media Center

I'm a huge hardware nerd. I'll be the first to admit it. One of my favorite ways to waste time on the Internet is by piecing together imaginary computers on Newegg. My interests really lie in creating efficient, fast, ergonomic computers, so a lot of my favorite hardware sites have some rather unconventional slants about them.

I get information from a number of hardware sites, but my favorites (listed in no particular order) are:
  • Silent PC Review - silence truly is golden. But it's more than just silence; how much power does your computer draw? How efficient (as in, work done verses energy used) are your components? People who can be fanatical about silence seem to be equally in tune with the overall quality and ergonomics of their system. This is what I find particularly endearing about SPCR.
  • AnandTech - A more general site, but it has a clean layout and generally good reviews.
  • XBitLabs - another general site. Good reviews, and great metrics for video card power consumption.
  • Jonny GURU - a finer power supply oriented site, there has never been. I truly enjoyed the article where he ran six junker PSUs through his rather vicious workbench, and managed to destroy all but one.
There are a few others, but these are the sites I frequent most.

Anyways, the point of this blog post is: I want a media center PC. In addition that that, I want the PC to run Slim Server software to power my squeezebox. In addition to that, I want it to run the video surveillance software that I develop.

So, let's get a sense of what I need. For media center, I need decent processor and graphics, ample disk space, and a spare USB port for the remote controller. For Slim Server, I need some network interfaces--pretty easy. For our software, I need another USB slot to hook up our receiver. I might also want an MX Air mouse, so a third USB would be useful.

Our software only runs on Windows, so that determines my operating system of choice: Windows Vista Premium SP1. Why not ultimate? Quite frankly, Ultimate doesn't have any features I'm interested in. I'd rather not have the extra crap.

I originally wanted to use my old Inspiron 600m, but the driver support in Vista is totally non-existent. The benefit of a laptop is the lower power consumption, but I have yet to figure out how to get it fully configured with Vista and my external monitor. So, for the time being, I'm scrapping this plan. The 600m is going to run Windows Home Server, which will also host SlimServer and my video surveillance software.

More in a bit; I'm going to post more specific hardware setups, and perhaps some network topology diagrams.

Thursday, November 29, 2007

How not to benchmark code.

The other day, I was searching for C# benchmarks. I came across this blog post. The "ultimate java verses C# benchmark" claims that:

The C# results? Well they're just too embarrassing to post. Suffice to say, it's several orders of magnitude slower! Furthermore, the memory usage exploded to who knows where! I can't believe that people may be thinking of deploying mission critical applications on this virtual machine!

Just like Cameron's benchmark, everything is self contained, you can cut and paste it, compile it and run it yourself. Better yet, send it to your resident C# expert, have him tweak it as much as he can. Bring a digital camera, capturing the anguish in his face when he realizes the truth, would be priceless.


...unfortunately my digital camera's batteries are hosed, so there will be nobody to capture the smile on my face as I tear this "benchmark" apart. The program put forth by the author "matches a DNA sequence against a million DNA patterns expressed as regular expressions." Both Java and C# variants of the program use java.util.regex.* and System.Text.RegularExpressions, respectively. Based on the authors's implementation, he concludes that "Java is at least 7,733x faster than C#."

Now I'm a pretty reasonable person. Seriously. I know that the .NET regex implementation has been shown to be slower than other implementations, but seven thousand times slower? Something is seriously wrong with the test.

The problem lies in how the C# benchmark was implemented:
Regex regexpr = new Regex(matchthis, RegexOptions.Compiled);

...what is this RegexOptions.Compiled flag? A blog post from the BCL team at Microsoft sheds some light:
In [the case of RegexOptions.Compiled], we first do the work to parse into opcodes. Then we also do more work to turn those opcodes into actual IL using Reflection.Emit. As you can imagine, this mode trades increased startup time for quicker runtime: in practice, compilation takes about an order of magnitude longer to startup, but yields 30% better runtime performance. There are even more costs for compilation that should mentioned, however. Emitting IL with Reflection.Emit loads a lot of code and uses a lot of memory, and that's not memory that you'll ever get back. In addition. in v1.0 and v1.1, we couldn't ever free the IL we generated, meaning you leaked memory by using this mode. We've fixed that problem in Whidbey. But the bottom line is that you should only use this mode for a finite set of expressions which you know will be used repeatedly.

Furthermore, the MSDN page on RegexOptions.Compiled has some very interesting commentary:
If a Regex object is constructed with the RegexOptions.Compiled option, it compiles the regular expression to explicit MSIL code instead of high-level regular expression internal instructions. This allows the.NET Framework's just-in-time (JIT) compiler to convert the expression to native machine code for higher performance.

However, generated MSIL cannot be unloaded. The only way to unload code is to unload an entire application domain (that is, to unload all of your application's code.). Effectively, once a regular expression is compiled with the RegexOptions.Compiled option, the .NET Framework never releases the resources used by the compiled expression, even if the Regex object itself is released to garbage collection.

You must be careful to limit the number of different regular expressions you compile with the RegexOptions.Compiled option to avoid consuming too many resources.
If an application must use a large or unbounded number of regular expressions, each expression should be interpreted, not compiled. However, if a small number of regular expressions are used repeatedly, they should be compiled with RegexOptions.Compiled for higher performance. An alternative is to use precompiled regular expressions. You can compile all of your expressions into a reusable DLL. This avoids the need to compile at runtime while still benefiting from the speed of compiled regular expressions.

What we can take away from this is:
  • RegexOptions.Compiled is intended for a small number of regular expressions which are used repeatedly, and in that instance, results in higher performance.
  • If an application must use a large or unbounded number of regular expressions, RegexOptions.Compiled should not be used.
What is our "benchmark" doing? It is creating a million Regex objects using RegexOptions.Compiled! If we correct this error, what is our performance like? I remeasured using the following C# program:
using System.Text.RegularExpressions;
using System.Text;
using System;
using System.Diagnostics;

namespace TestRegex
{

public class RegexBench2
{
private static String _doc = "CGAATCTAAAAATAGATTCGGACGTGATGTAGTCGTACAAATGAAAAAGTAAGCC";
private static int ITERATIONS = 1000000;

public static void Main()
{
Stopwatch sw = new Stopwatch();
sw.Start();

int length = 1;

for (int i = ITERATIONS; i <= ITERATIONS * 2; i++)
{
length = (int)(Math.Log((double)i) / Math.Log(4));
String matchthis = generateWord(i, length + 1);
Regex regexpr = new Regex(matchthis);

if (regexpr.IsMatch(_doc))
{
Console.WriteLine("found {0} at {1} it took {2} miliseconds", matchthis, i, sw.ElapsedMilliseconds);
}
}

Console.WriteLine(".NET regex took {0} miliseconds", sw.ElapsedMilliseconds);

}

public static String generateWord(int value, int length)
{
StringBuilder buf = new StringBuilder();
int current = value;
for (int i = 0; i < length; i++)
{
buf.Append(convert(current % 4));
current = current / 4;
}

return buf.ToString();
}

private static String convert(int value)
{
switch (value)
{
case 0: return "A";case 1: return "G";case 2: return "T";case 3: return "C";default: return "0";
}
}
}
}


My performance for the C# program was substantially better (as in, it actually completes) than the previous incarnation:



For the java program, I compiled using Eclipse 3.3.1.1 and the previous code the author used. The results were:
found AAAGTAAGCC at 1000000 it took 0 miliseconds
found AAATGAAAAAG at 1048960 it took 172 miliseconds
found GAAAAAGTAAG at 1085441 it took 265 miliseconds
found TCTAAAAATAG at 1179694 it took 547 miliseconds
found ACGTGATGTAG at 1204636 it took 625 miliseconds
found AATAGATTCGG at 1548576 it took 1578 miliseconds
found TCGTACAAATG at 1576094 it took 1656 miliseconds
found CGGACGTGATG at 1599255 it took 1734 miliseconds
found ATTCGGACGTG at 1689064 it took 1984 miliseconds
found AGATTCGGACG at 1859204 it took 2453 miliseconds
found TGATGTAGTCG at 1984902 it took 2797 miliseconds
found AAATAGATTCG at 2000000 it took 2843 miliseconds
Java regex took 2843 miliseconds

The java program is now roughly twice the speed of the C# program, which seems far more reasonable. The discrepancy resulted from misuse of the API; not from the C# regular expression implementation being seven thousand times slower than the Java implementation. The worst possible way to benchmark two language implementations is to incorrectly use one, and then compare it to a correct usage of the second. Obviously, the results are going to be skewed towards the language being used correctly.

The author's confusion probably stems over how the Java regex implementation uses a .Compile() method, but one has to wonder how he could seriously think the results were valid. The honest response to this would have been "Gee, 7,000x slower? Something must be wrong in my C# program!". The dishonest response is: "C# is a dog! 7000x slower? Java forever!"

On a more fundamental level, I completely disagree with the overall tone of the article. As the Computer Language Benchmarks Game points out,
Benchmarking programming languages?

How can we benchmark a programming language?
We can't - we benchmark programming language implementations.

How can we benchmark language implementations?
We can't - we measure particular programs.

You cannot benchmark a language, nor can you benchmark a language implementation. There is only performance for a specific program. So it's entirely possible that this one example posted isn't necessarily a strong indicator of overall performance. It's also possible that the results will change as both the Java and .NET implementations change over time.

Friday, October 26, 2007

Hardware Assisted Brute Force Attacks


Jeff Atwood recently blogged about a hardware assisted brute force password cracking product developed by Elcomsoft.

Using Elcomsoft's figures from a pdf they released, Atwood concludes that we can attempt this many passwords a second:


Dual Core CPU 10,000,000
GPU 200,000,000


...and using Elcomsoft's relatively weak 8-character alpha-based password (a-A, z-Z), there are this many passwords:


52^8 = 53,459,728,531,456


Some more basic math gives us:


53,459,728,531,456 / 10,000,000 pps / 60 / 60 / 24 = 61.9 days
53,459,728,531,456 / 200,000,000 pps / 60 / 60 / 24 = 3.1 days


To his credit, Atwood correctly assaults Elcomsoft's most questionable assumptions: allowing people only 8 characters, and using an extremely limited character set. Adding additional characters, it becomes clear that the exponent plays a rather sizable role. Here's the amount of time for twelve characters:


52^12 / 200,000,000 pps / 60 / 60 / 24 = 22,620,197 days


We can all agree that ~22 million days (about ~61,000 years) is an awful long time. But this is where Atwood makes an error:

For those of you keeping score at home, with a 12 character password this hardware assisted brute-force attack would take 61,973 years. Even if we increased the brute force attack rate by a factor of a thousand, it would still take 62 years.


The error here is pretty basic: over the next 62 years, what sort of new computing techniques will we develop? How much faster will GPUs run five years from now? Ten years from now? What did computing resemble 62 years ago?

I'll give you a hint:



This is ENIAC. It was the "first large-scale, electronic, digital computer capable of being reprogrammed to solve a full range of computing problems." In one second, it could perform:
  • 5,000 add or subtract operations
  • 357 multiply operations with two ten digit operands
  • 35 division or square root operations
...all of this, at a svelte 30 tons, while consuming 150 kW. This is state of the art in computing, roughly ~61 years ago.

Considering the operations being done to hash a password are substantially more complicated than simple arithmetic, how many passwords could ENIAC hash in a second? To be honest, I think it's more likely that this unit would be expressed in number of seconds per password rather than the number of passwords per second, but I'll be the first to admit that I'm not familiar enough with the NTLM hashing algorithm to say with certainty.

For the sake of argument (and not having to discuss a computing architecture that dates me by a good 35 years) let's assume that ENIAC can do one hash a second. This means our modern CPU is ten million times faster than ENIAC, or somewhere between 2^23 and 2^24 times the speed of ENIAC. The GPU is 2^27 to 2^28 times the speed of ENIAC. These are both commodity products, and ENIAC was state of the art, so a more fair comparison would be with something like Blue Gene, but I digress.

Using the above assumptions, this means that the number of hashes we can do should double every 2.25 years. This also means that it'd take 22.5 years for our current computing power to increase 2^10 (or 1024) times. Let's reread Jeff's statement:

Even if we increased the brute force attack rate by a factor of a thousand, it would still take 62 years.


...so this means that 22.5 years from now, a computer would still need another 62 years to crack the 12-character password, for a grand total of 84.5 years. But, if we increase our computing power by a million (2^20, or 45 years from now--it's no big deal, we just push the date out), it will only take .o62 years (roughly 22 days), or 45.062 years from today. If we increase our computing power by 2^27, it ends up being roughly 4.25 hours to crack a single 12 character password.

Obviously all of this is total speculation, with wild figures and estimates on my behalf that are obviously open to interpretation, huge questions about where computing will be 40 years from now, etc. But the point I'm trying to make is: it's a fallacy to assume today's computing power is what you'll have access to in a year. It's a gigantic fallacy to assume today's computing power is what you'll have access to in 20 years (what were you doing in 1987?). Discussing what we'll have at our disposal in 62 years is mind-boggling.

When we're computing the amount of time it takes to do something, it makes no sense to hold computing power constant, especially when we start talking about any amount of time in excess of a year. If we think it's going to take ten years to perform some computation, one viable option is to wait five years (at which point in time your computing power has quadrupled), kick off that batch job, and take a 2.5 year coffee break. It still took you 7.5 years, but that was 2.5 years saved.

Sunday, October 07, 2007

The Sorry State of Online Translation Tools


As of late, I've been working on a set of automated tools that query free online translation services to perform translations for some of our target languages. For example, all of our string data is in en-US, so we might request a fr translation from babelfish.

Yes, if you were paying attention, I am doing the unspeakable: I've developed an application to automate translation using AltaVista's translation services. Is it theft or abuse of their free services? Yeah, probably--but seriously: cry me a river. (If you're reading this, BabelFish, take note: your programmers are stupid. Yes, I said it. Stupid. You have the potential to offer a for-pay service, but your API is too deficient for it to be of any real use without jumping through ridiculous hoops.)

Anyways, this task has yielded some extremely interesting observations. AltaVista (BabelFish) doesn't expose any web services for doing translation, although I believe they may have in the past. So, what we were left with was good old HTTP requests. We submit a request through their web form, and parse the translated resource out of the response. Needless to say, this is problematic. We've glued together some extremely flexible, object-oriented C# classes to manage this.

The page for translation looks something like:



...okay, great. So it managed to do this basic translation, pretty easily. But maybe I don't want "fox" translated. AltaVista instructs users to wrap "fox" in "x" characters, which results in something like:



...seems obvious enough. But wait--notice that the no-translate specifiers (x) are left in the output. I have to manually remove the x's from the output. Slop, baby, slop. How about this:



Call me crazy, but I don't remember "l'examplesx de xextra" being in the French lexicon. And something tells me they aren't going to recall it either. And when it comes to language, the French may be the last people in the world you want to piss off. But I digess.

So one thing is pretty obvious: the characters that BabelFish has chosen to designate sections of text as "do not translate" are insufficient; this should be totally obvious to even the most stupid programmer, since attempting to parse out x's from English text is going to be problematic, given that character is used (somewhat infrequently, I must admit, but why use a letter in the language itself?). And why not go with the (more) obvious (but still incredibly stupid) choice of "z", which is encountered half as often as "x" in everyday language? Perhaps their justification was that there aren't words in the English language that start and end with x, but there are phrases like "xextra examplesx", which seems to make BabelFish's parser throw a temper tantrum.

This character selection snafu probably also explains why they're left in the output; good luck removing something as unspecific as "x" from the output. Because of this, our application has a post-processing step where we search for our wrapped phrases, and then replace them with the originals before the x's were inserted.

All of this begs the question: why not use something that is obviously not an element of the English language, or any other linguistic language, for that matter? Personally, I would propose something like:

<NoTranslate lexcat="">section to not translate</NoTranslate>

...which would have made the aforementioned sentence:

I need <NoTranslate>extra examples</NoTranslate> of this leaping fox.

...or maybe:

I need extra examples of this leaping <NoTranslate lexcat=noun>fox</NoTranslate>.

..."lexcat" is an idea I had (no idea how feasible or practical it is) to give the translator some idea of what is contained in the parenthesis to perform a more concise translation. The context would be for the source language, which would (hopefully) aid in translation to the target language. I suppose other attributes could be added based on the source language (maybe gender would be useful for French, for example). Anyways, with this way of marking text, it is clearly obvious what part you don't want translated. The odds of someone encountering <NoTranslate></NoTranslate> in everyday parlance are pretty damn low.

Unfortunately, this is hardly the beginning of the crap translation service offered. Consider multi-line translations, such as:

Here's the first line to be translated.

This is a leaping fox.

...translates to:

Voici la première ligne à traduire. C'est un renard de saut.

...the problem here is pretty obvious: the translator didn't preserve line breaks. The output should have had a break between the two sentences. This is almost an even bigger issue for automating translation--one option we've kicked around is inserting some xLINEBREAKx word where there's a \r\n; without modifying the input, the location of line breaks is lost in the output. Yet another pre/post processing step to add.

The really sad thing is we've looked for better translation services, and this is actually one of the better ones. Google's service is (surprisingly) even more deficient; rather than using x's as no mark, you use a single "." at the front of a word or phrase you don't want translated. Gee, who uses periods these days? I think I'll go and remove all of the periods from my writing from now on.