Out of memory, out of luck?

6 01 2014

I was recently implementing a new feature that takes a user-supplied file, parses it and adds some slithy toves to the active manxome[1].

Now as I’m sure everyone knows toves consume a lot of memory and slithy toves are amongst the worst offenders. A typical manxome can be expected to contain a single digit number of toves, a number that in extreme cases may rise to the mid twenties. I soon got a defect complaining that if a file with many toves was imported we would encounter an OutOfMemoryException (OOME). This defect contained a screen recording of how to reproduce the defect, in it you could see a directory listing containing a file called 1000_toves.imp which the tester did not select, the directory also contained a file called 2000_toves.imp which was also not selected, the 3000_toves.imp file that was selected did indeed cause an OOME.

The problem with running out of memory is that almost anything you try to do in order to recover from this exception, does in itself, consume more memory. Even roll-back operations that will free up memory when  they are done usually consume some memory while being run. This is why the best way to deal with such an exception is not to be in that situation to begin with. The .NET framework supplies the tool needed in order to not be in that situation to begin with and it’s called MemoryFailPoint the problem I was facing was that I couldn’t find out in advance how much memory I would be consuming.

The simple solution was to define an arbitrarily limit on the number of toves I allowed a file to contain, this artificial limit went against my instincts as a programmer (Scott Meyers would call it a keyhole problem) and is the solution we ultimately chose. I would like to show another solution I explored since it may be the least worse option for someone in some bizarre situation.

The problem this method attempts to solve is of allowing the program to continue functioning after encountering the OOME while giving the strong exception guarantee (i.e. if an exception occurs the program state is as if the operation wasn’t attempted). As things stood not only was the program state changed (some but not all toves were added to the manxome) but worse, the program became unusable, we would encounter OOME after OOME. The basic idea isn’t new, it’s to put some memory aside for a rainy day. If an exception occurs we can then free this memory so that we have enough space to perform roll-back operations.

public void DoStuff(string param)
{
    try
    {
        var waste = new byte[1024 * 1024 * 100]; // set aside 100 MB
        var random = new Random();
        waste[random.Next(byte.Length)] = 1;

        DoStuffImpl(param);

        if (waste[random.Next(byte.Length)] == 1)
            Trace.WriteLine("Do something the compiler can't optimize away");
    }
    catch (OutOfMemoryException oom)
    {
        GC.Collect(); // Now `waste` is collectable, prompt the GC to collect it
        throw new InsufficientMemoryException("", oom); // Wrap OOM so it can be better handled
    }
}

A couple of notes about what’s going on here

  • I throw InsufficientMemoryException rather than re-throwing the original OOM exception to signal that the program has enough memory to continue, it’s just this operation that failed.
  • Originally there was none of this nonsense of setting a random byte but the compiler kept optimizing waste away. I think that GC.KeepAlive should also work but I didn’t think of it at the time and I no longer have the environment to check it out.

As I said this code was never put to the test so use it at your own risk and only as a last resort[2].


1. These are not the actual names of the entities.
2. I’m sensing a trend here, code I wrote that doesn’t get used seems to find its way to this blog, perhaps I should rename it to undead code.




Malkovich? Malkovich Malkovich!

15 07 2013

If you ever logged logged in to a windows computer that uses the Japanese display language you probably saw that the path separator is not the common backslash (\) but the Yen symbol (¥).

Well at least that was what I thought, I recently got a defect that we haven’t localized one of our dialogs correctly and it showed backslash on Japanese OSs. My first thought was that somebody hardcoded ‘\’ instead of Path.DirectorySeparatorChar but a quick look at the code showed that we were using the path as supplied by the OS. This forced me to learn something new which I will now inflict on you.

Since reading Joel’s classic The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!)  my understanding was that the Unicode range of [0-127] (aka ANSI or ASCII) was the same the world over. Quote:

Eventually this OEM free-for-all got codified in the ANSI standard. In the ANSI standard, everybody agreed on what to do below 128, which was pretty much the same as ASCII, but there were lots of different ways to handle the characters from 128 and on up…

As appropriate for a post describing the “absolute minimum” this is not the whole story, Michael Kaplan’s post when is a backslash not a backslash taught me that on Japanese OSs a backslash (Unicode U+005c which is 92 – less than 128) it is displayed as Yen (¥), even though it is not the Unicode Yen character (Unicode U+00A5). This means that the path separator is still backslash it’s only displayed as a Yen, it also means that the actual Yen is not a path separator. Since Yen is not a path separator it can be used in file names and the following path can mean several different files:

C:¥¥¥¥¥¥¥¥¥¥¥¥¥.¥The first ¥ must actually be a backslash (and the second can’t be a backslash) which means that the file in question may be any of the following:

c:\¥¥¥¥¥¥¥¥\¥¥¥.¥
c:\¥¥¥\¥¥¥¥\¥¥¥.¥
c:\¥¥\¥¥\¥¥\¥¥¥.¥
c:\¥¥¥¥¥¥¥¥\¥¥¥.¥
c:\¥\¥\¥\¥\¥¥¥¥.¥
... and many more

c:\¥\¥\¥\¥\¥¥¥¥.¥

The same story applies to Korean Won ().

tl;dr how a backslash appears depends on the font you use, the path separator is not localized on Japanese OSs.


A more topical title for this post would probably be Hodor hodor hodor.





Global BSTRs

27 09 2012

Working with COM from C++ is pretty natural, after all COM’s interfaces are binary compatible with C++ virtual tables. However there are some places in which the fact that COM was designed to work with C leaks through and causes some friction.

A notable example of this is BSTR, under the covers all BSTR is is a typedef to wchar_t* however a BSTR is conceptually different from a plain string, a BSTR may contain embed Nul characters and is therefore not Nul terminated, instead the length is stored in the memory that precedes the actual string data. BSTRs also resist the concept of const correctness, you can’t have a const BSTR which can be a bit of a pain when you want to have BSTR constants.

What should one do when two different pieces of code want to share the value of a BSTR? There are several options.

1. #define a string literal in a header

#define XPATH_CHEAP_BOOKS L"//genre/book[price<7]/title"

One can pass a (wide) string literal to a function expecting a BSTR and this will even work …if you don’t use BSTR specific methods or marshal the parameter.

void Foo(BSTR bs)
{
    wcout << L"The length of '" << bs << "' is " << SysStringLen(bs) << endl;
}

Foo(L"Your guess is as good as mine");

Code that ran correctly (by accident) for years and years can suddenly start to fail if the class implementing an interface changes from C++ to .NET, if there’s an interop call between C++ and .NET the marshaller go into play. Since the marshaller knows that the correct way to determine the length of a BSTR is to call SysStringLen it will do so and quite probably get an enormous value, this will cause an out of memory exception when trying to allocate the .NET string.

Obviously the same problems happen with const wchar_t*.

Global CComBSTR

CComBSTR XPATH_CHEAP_BOOKS = L"//genre/book[price<7]/title";

Having a global CComBSTR  (in a header file) has several problems

  1. you have to choose it’s storage class
    •  it can’t be extern (which is the default) because then you’ll get a link-time multiple definition error
    • if it’s static there will be an instance for every translation unit (ie .cpp file), which makes point 2 worse
  2. Each constant will allocate a BSTR when the binary (dll or exe) is loaded, even if it’s never used and even if COM isn’t yet ready to successfully run SysAllocString.
  3. Since CComBSTRs can’t be const someone may change them during the application’s lifetime
  4. When the process terminates the destructors will call SysFreeString, this is just a waste of time, the process is going to return all its memory to the OS anyway, who cares if it’s freed or un-freed memory?

A solution

The first hint at a solution came from  __declspec( selectany), this solves problem #1, an extern global object with __declspec( selectany) will not cause a multiple definition error at link time, instead the linker will arbitrarily select one of the symbols and discard the rest.

The next problem (#2) is that we don’t want to initialize each global too early (or indeed at all in case it isn’t used). In order to do this we can just create a class that has a cast operator to BSTR. This cast operator will use lazy evaluation to create the BSTR the first time it is used and cache the value.

Since the cast operator can be called on different threads some protection must be used, thankfully InterlockedCompareExchangePointer is a perfect fit for our needs.

The rest is pretty straight forward.

  • We can avoid #4 (waste of time in process destruction) by neglecting to write a destructor
  • Although we can’t prevent the clients of our code from changing the BSTR at compile time we can verify that nobody has at runtime (I chose to do so only in debug builds)

We want the class to be light weight therefore it’s best if it is initialized with a string literal so that we can grab the pointer and be sure it will be valid throughout the lifetime of the program and not have to copy it. In order to ensure that we really got a string literal we can make the constructor private and make a macro that creates these objects, in the macro we can verify that the string is a literal by concatenating another (empty) string to it (this will fail at compile time for non literal strings). The macro will use a public member factory function that is named in a way that makes it obvious that it should only be passed a string literal (we are protecting against Murphy, not Machiavelli after all).

Warning: The following code seems to work as expected but has not been rigorously tested, I welcome any corrections.

#ifndef GLOBAL_BSTR_HEADER_PROTECTION_
#define GLOBAL_BSTR_HEADER_PROTECTION_
#pragma once

#include "WTypes.h"// BSTR
#include "crtdbg.h"
#ifdef _DEBUG
#include <cwchar>// for ASSERT in LeakBSTR
#endif

// LeakBSTR is for creating globals with the GLOBAL_BSTR macro therefore there is no need 
// to free the BSTR at destruction (hence no destructor)
class LeakBSTR { 
    BSTR bs;
    // It's safe to hold on to the string pointer in the constructor since
    // the private ctor & macro enforce initialization by string literal
    const wchar_t* str; 

    LeakBSTR(const wchar_t* s)
        :  bs(NULL)
        , str(s)
    { }

public:
    static LeakBSTR constructFromStringLiteral(const wchar_t* s)
    {
        return s;
    }

    operator BSTR() 
    {
        if (bs == NULL) {
            BSTR tmp = SysAllocString(str);
            if (InterlockedCompareExchangePointer((void**)&bs, tmp, NULL) != NULL) 
                SysFreeString(tmp); // Another thread already initialized 'bs'
        }

        // make sure nobody messed with the BSTR since it was created
        _ASSERTE(std::wcscmp(str, bs) == 0); 
        return bs;
    }
};

#define GLOBAL_BSTR(name, value) __declspec(selectany) LeakBSTR \
    name(LeakBSTR::constructFromStringLiteral(L"" value L""))

GLOBAL_BSTR(EmptyBSTR, L"");

#endif




A const BSTR isn’t

11 06 2012

If you’ve programmed any COM you’ve come across the ubiquitous BSTR string type. You may have even been tempted to have a read-only BSTR and used a const BSTR. Unfortunately this is not to be. If we look at WTypes.h we’ll see that BSTR is defined thus:

typedef WCHAR OLECHAR;
typedef OLECHAR* BSTR;

Basically a BSTR is a wchar_t*[1], but what happens when we try using a const BSTR?

The rule of thumb when trying to understand what is const in a C++ deceleration is to push the const as far as you can to the right without passing an asterisk and then read from right to left.

const int i; // int const i => i is a const-int 
const int *p; // int const * p => p is a pointer to a const-int
int * const q; // q is a const-pointer to int
const int * const pq; // int const * const pq => pq is a const-pointer to a const-int

This implies that const BSTR is the same as BSTR const, since the typedef captured the asterisk as part of the type the const can travel over it and produce a “wchar_t* const“, i.e.  the pointer is immutable, not the individual characters.

const BSTR deceptive = SysAllocString(L"Read only!");
deceptive[9] = '?'; // deceptive = "Read only?"
deceptive = NULL; // Compile error, deceptive is const

This is probably the exact opposite of the intended purpose.

The same translates to CComBSTR (and _bstr_t), having a const CComBSTR (and passing parameters by const reference) probably don’t do what you think they should.

The only advantage a const CComBSTR has is that it has static linkage but if that’s what you want you should just say static CComBSTR.


[1] At least at the static type level, at the semantic level it’s another story.





Wrappers Unwrapped

6 01 2011
tl;dr; Avoid using Marshal.ReleaseComObject when possible.

When you use a COM object in .NET the .NET framework creates a Runtime Callable Wrapper (RCW) which shows up in the debugger as __ComObject. This allows interoperation between managed .NET and native COM code. One of the major differences between C++ COM and .NET is that in C++ you have deterministic destruction while in .NET objects are finalized at the garbage collector’s leisure. Which mode of operation is preferable is a matter of taste and not the topic of this post (I’ll just say that you can take my deterministic destruction when my cold dead hand goes out of scope) however mixing the two modes can cause problems.

The SOP is that the RCW calls AddRef[1] on the COM object it is holding so that it won’t disappear while it’s being used and then, when the RCW is collected by the GC, it will release this reference in its finalizer. This works if you don’t care exactly when the COM object is released and .NET exposes Marshal.ReleaseComObject for cases in which you want to manually control the object’s lifetime.

We recently re-implemented a few interfaces (that were previously native COM) in .NET and stuff stopped working. A bit of debugging later I find that we’re calling ReleaseComObject on an object that is now implemented in .NET, this causes an ArgumentException to be thrown. A cow-orker pointed me at a post titled Marshal.ReleaseComObject Considered Dangerous (well at least it’s not harmful), this post describes the problem we were facing and the solution I already put in place (check with Marshal.IsComObject before calling ReleaseComObject) but goes on saying that this isn’t enough since once you call ReleaseComObject the RCW is disconnected from the COM object and can’t be used (and that this can be a problem if the RCW is cached). I thought that this is a theoretical problem (I know we aren’t caching the RCWs) and kept trying to figure out why our code still wasn’t working.

It turns out that as in everything in programming it’s all about adding another level.  We had three levels, a .NET class (which we’ll call A) a native class (C) and class B which was native in a previous incarnation but is now .NET, A holds a reference to B which hands it a C (via a method or property), but why is this a problem?

For that we’ll need to dive a bit deeper into how RCWs work.

In order to preserve COM’s identity semantics whenever a COM object is passed into the CLR the .NET framework first checks if there is an active RCW for this object, if so it returns the existing object. You can see this by debugging your native object, after an object is returned from a native COM method (or property) it is followed by a QueryInterface for IUnknown and then by two calls to Release (one for the reference gained in the original function and one for the reference gained in QueryInterface). Additionally the RCW maintains a count of the times it has been reused, MSDN refers to this as a reference count but I’ll refer to it as marshal count in order to emphasise the difference between this number and the native COM object’s reference count. If an RCW is reused at the identity checking phase the marshal count is incremented. When ReleaseComObject is called on an RCW the marshal count is decremented. If the marshal count reaches zero the RCW releases its references to the native COM object and marks itself as invalid, any subsequent calls to the wrapped object will throw an InvalidComObjectException with the message “COM object that has been separated from its underlying RCW cannot be used”. If an RCW is collected by the GC while it is still in a valid state it will also release it’s wrapped object (regardless to its marshal count).

Now consider the situation we had when B was a native COM object. Whenever A got a C from B said C had crossed the CLR boundary and a new RCW was created (or at least the marshal count was incremented). Then when A was done with C it called ReleaseComObject and all was fine and dandy.

In order to highlight the point the following sequence diagram shows what happens if A acquires C several times in a loop. The RCWs (in blue) represent the boundary between native code and the CLR.

Sequence diagram of flow when B is a COM object

But now B is managed so A‘s RCW was created once when B acquired it. Now when B hands C to A it is passing a regular managed reference (that of the RCW), .NET references aren’t aware of being copied (there’s no copy-constructor to trigger a change in the marshal count) and when A will call ReleaseComObject it will invalidate A without B having a clue that its member is no longer valid. Note the fact that the incrementation and decrementation of the marshal count are not balanced (in respect to the loop).

Sequence diagram of flow when B is a .NET object

We have quite a few places which use ReleaseComObject, some of which are probably cargo cult programming but some are needed, how should we make sure that we detect all the problematic uses of ReleaseComObject?

The obvious solution is the one Microsoft chose, identify all the places you use ReleaseComObject and remove them unless they can be proven to be correct (this is also the route we chose). I’ll list a few other options we thought of so other people can be informed of all (?) their options.

Adopt .NET Semantics

Embrace the fact that destruction isn’t deterministic and make sure your code doesn’t depend on deterministic destruction, then remove all calls to ReleaseComObject.

  • Pro: You gain a consistent world view, your code is easier to reason about
  • Con: This can be very difficult and require a lot of work

Artificially Increment the Marshal Count

You can manually force the marshal count to be updated and do this for each RCW you hand out[2].

public static T AddRcwRef<T>(T t)
{
    IntPtr ptr = Marshal.GetIUnknownForObject(t);
    try {
        return (T)Marshal.GetObjectForIUnknown(ptr);
    }
    finally {
         Marshal.Release(ptr); // done with the IntPtr
    }
}
  • Pro: You don’t have to change your client code (perhaps you can’t)
  • Con: Every developer in the organization must be familiar with this (anti) idiom and maintain its use in the correct places. Also if you really do need deterministic destruction you’ll have to be sure to call ReleaseComObject on your member at the correct time otherwise the COM object won’t get destroyed.

Get the Finalizer to do the work

Instead of calling ReleaseComObject discard your reference to the object and let the GC check if it’s still in use.

public static void ReleaseRcw<T>(ref T t)
{
    t = default(T);
    GC.Collect();
    GC.WaitForPendingFinalizers();
}
  • Pro:
    • You gain a submission to TDWTF
    • If you thought of this you’ve probably exhausted all your other options and it’s time to choose the least bad one.
  • Con:
    • If the object in question is an argument to a function the call stack will have a reference and this won’t work
    • Performance killer
    • etc.

Conclusion

This brings us back to the tl;dr; when writing new code try to avoid using ReleaseComObject, it may save you a lot of trouble in the long run.


[1] Actually it may call AddRef several times but it calls Release for them all at the same point in time, in my test project the RCW held on to 4 references to the COM object.
[2] According to Eric Lippert on my stackoverflow question this function can be replaced with: Marshal.GetIUnknownForObject(o); // ignore return value and he should know what he’s talking about but I think the original version is more explicit.





Boolean “implies” operator

1 07 2010

A cow-orker recently asked me if XOR worked on boolean expressions. I told him that it did but I would consider it unreadable and he should use != instead:

// if either ptr is not null or length is not zero
// (but not both)
if ( (ptr != NULL) ^ (length != 0) ) 

// same but IMO clearer
if ( (ptr != NULL) != (length != 0) )

He then asked whether there is an implies operator, after meditating on this for some time I was inspired by the infamous goes to operator:

int x = 10;
while( x --> 0 ) { // x goes to 0
    printf("%d ", x);
}

I’m very proud to present the implies operator:

// ptr != NULL implies length != 0
if ( (length != 0) <= (ptr != NULL) )

Unfortunately this operator has the quality that it’s read right to left (X implies Y Y <= X) .

 

Edit: Two years after writing this I showed it to a friend who pointed out this is completely wrong, X implies Y X <= Y which pretty much blows the whole thing out of the water. Sorry for wasting your time 😦





The First Bug

27 10 2009

I don’t remember the first bug I ever made but as everybody knows [citation needed] half the fun of parenting is living vicariously through our children.

The other day my first born (age 5¾) decided to make a board game.

He had already made the dice (that’s another story), so he got out his crayons and went to work.

Buggy board game

Buggy board game

The rules were pretty simple

  • Boat: move one step forward
  • Guard tower: lose two turns
  • Torch: move back one step less than the last die throw
  • Cannon (that’s the one with lots of red circles): go back to the beginning
  • Etc.

We were playing merrily along when the configuration in the picture came up, two steps away from the boat, roll the die and…

  1. The die lands on 2
  2. Move two steps to boat
  3. Boat moves us a step forward
  4. Land on torch
  5. Torch moves us back one step less than was rolled
  6. Two was rolled so go back one step
  7. Land on boat (goto 2)

Whoops, we’re in an infinite loop! FB was quick to realize what was going on and quickly stopped his old man from executing the infinite loop (ruining all my fun), we arbitrarily chose which of the two locations to stay on an kept on playing.

What really made my day about this was that this was a non-trivial bug, any non-programmer (which includes most 5 year-olds) would not think to look for an infinite loop and even I who suspected such a thing might occur didn’t really see it before it happened (in my defense I wasn’t looking very hard), most flows didn’t expose this “bug” and it’s only by chance that we ran into it on the first time we played the game.

So anyway that’s my son’s first bug, what was yours?