Memory Barriers

Sorry for the long break in blogging; I’ve been catching up on 1001 things at work, and getting ready for an upcoming trip to the Old World. I promise I won’t let it happen again! <g>



I first heard about memory barriers from Ed Dekker’s book on NT Device Drivers. This is still probably my favorite overall book on driver-writing, even though it’s getting to be badly out of date. Ed can tell stories with the best of ‘em, and his is one of the few books that really has a personality. He addressed the concept of memory barriers in conjunction with the (slightly oddball) Alpha processor port of NT.


First, consider the following code:


int a = 0;
int b = 0;

f()
{
        while(a == 0)
        {
        }

        ASSERT(b == 1);
}

g()
{
        b = 1;
        a = 1;
}




Assume f() and g() are two threads started simultaneously. Will that ASSERT() ever fire? The naive answer is “no”. However, modern super-scalar processors sometimes re-order memory accesses for various reasons, and if that happens, the ASSERT can be tripped. This is subtle; think about it for a second if it’s not immediately obvious.



This problem can be fixed with a memory barrier. A memory barrier is an explicit instruction to the CPU that orders reads and writes to memory. In other words, it requires that any outstanding read or write accesses to memory be completed, processor-wide. The implementation of a memory barrier is CPU-specific, as are the situations in which one might be needed. IA-64 write combining presents different issues to programers than normal x86 semantics, for example.



On an x86 chip, any interlocked operation will force an implied memory barrier, and if you’re using a new enough DDK, you can call KeMemoryBarrier() to make your intentions obvious. The above code would be fixed, for example, by changing g() as follows:


g()
{
        b = 1;
        KeMemoryBarrier();
        a = 1;
}



So how can you tell when you need one? Well, the good news is that it doesn’t seem like I run into many situations where this is an issue. The operating system protects you with implicit memory barriers included in all locks, and if you always protect shared memory with a lock of some sort, you’re safe. However, if you try to minimize the use of locks in your code, this can jump up and bite you.



There is one other source of re-ordering that you should be aware of, as well: compilers tend to re-order things in certain cases, and while the rules for re-ordering are subtle and complex, you can always protect yourself using a combination of the “volitle” keyword in C code and compiler-specific intrinsics.


For more information on memory barriers, check out this paper at WHDC.



Extra credit: analyze the following code, in light of memory barriers:

int a = 0;
int b = 1;

f()
{
        for(;;)
        {
                ASSERT(a < b);
        }
}

g()
{
        for(;;)
        {
                b++;
                a++;
        }
}


3 thoughts on “Memory Barriers”

  1. Didn’t you mean to write this:

    while(a == 0)

    {

    ASSERT(b == 1);

    }

    in the first example?

    If not I think I misunderstood something. Nice article, BTW.

  2. No, I meant it that way (but I did have to ponder it again :) ). That loop means "spin forever until a is no longer equal to 0", and a is pre-initialized to 0 above.

    g() sets them both to 1(b first, then a). The point is that the ASSERT in f() might still fire because it’s missing a memory barrier. Even though g() writes b = 1 first, the CPU might re-order it behind the write of a = 1, and in that interim time between writing a first and b second (which is backwards of what the code says), the other thread might read a = 1 and b = 0, triggering the ASSERT.

  3. Oh, now I got it. Thanks. For some weird reason I had mixed up my understanding of ASSERT(x) and thought of it as ASSERT(!x) and your code made no sense to me. :-)

Leave a Reply

Your email address will not be published. Required fields are marked *


*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>