All Your Base Are Belong To Us

IsBadXxxPtr Is Really Harmful – Please Don’t Use These Functions

You might have stumbled upon posts like this one that tell you there’s a simple solution for verifying that a memory location is OK for read/write/execution: Just use the “IsBadXxxPtr” family of functions that take a memory address and return a BOOL indicating if you can use the memory.

It turns out (and I’m hardly the first to blog about it) that calling these functions causes more problems than it solves, and causes bugs rather than fixes them. Please heed the collective advice and stay away from these APIs.

Here are some reasons why:

Non-atomicity

If you want to test a page for reading, a standard approach would be to call IsBadReadPtr, get a FALSE result and then try reading from the page, right? Well, what stops some other thread (or even your thread in an APC, for example) from unmapping that page and rendering it invalid for reading just after your checked but before you had a chance to read from it? Guess what, you crash – and this time you crash in a very surprising location. If you try debugging, you’ll see that your app causes a read access violation after testing the address with IsBadReadPtr, and head-scratching is guaranteed.

“Corrupt memory if possible”

IsBadWritePtr is even worse. As Raymond Chen aptly put it, this method should really be called CorruptMemoryIfPossible. What this method does is try to write a single byte to the beginning of every page in the range that you passed to it, and then fix up the old value of that byte if the write succeeded.

Two horrible things come to mind: First, another thread can observe the changed byte before the API had a change to fix it up to the old value. This is clearly very bad. Another horrible thing (which is far less likely though) is that the page becomes read-only after the test byte has been written and before the API had a chance to fix it to the old value. Both of these things are random corruptions that you have no hopes of detecting.

Guard pages

Not many Windows programmers are familiar with guard pages, but they are very important nonetheless. A guard page is a page protected by the PAGE_GUARD page protection flag, which causes a one-shot page guard exception when the page is accessed. After the page is accessed, however, the guard is removed and will not be triggered again unless the page is protected by PAGE_GUARD again.

Guard pages are used by a variety of applications, but they have one very important role: Ensuring that thread stacks are lazily expanded. The way thread stacks work on Windows is that although by default 1MB of stack space is reserved for each thread, the individual pages in that range are committed page-by-page, when the thread attempts to expand the stack by calling a method or allocating stack-based memory. What happens is that the next page that is about to be used for the thread’s stack is a guard page, and there’s an exception handler that catches the page guard exception, properly commits the page and, most importantly, places a guard on the next stack page.

I suppose you can already see the potential for trouble if you touch guard pages using IsBadXxxPtr. The API will swallow the page guard exception like any other, and the exception handler responsible for placing a guard on the next stack page will not run. This means you just created a potential stack overflow where there was previously no reason for one to occur.

There are also other examples of why guard pages can be useful, and in most of these cases the IsBadXxxPtr family of APIs defeats the mechanism behind guard pages in varyingly fatal ways.

Not to mention that bad pointers will crash you anyway

There’s also the more philosophical argument here. If you get a bad pointer (and I’m not talking about a NULL pointer here, which can be easily detected* by other means), what do you think you can do about it? If you have the privilege of returning an error code, do you think the program that gave you an invalid pointer in the first place is going to check the error code?

What you often do by checking for “bad” pointers is turning a fail-fast crash into a subtle bug to be discovered maybe hours later. The worst thing that can happen if you have a memory corruption is that your application continues running. If you check for bad pointers, it’s as if you’re trying to guarantee that your application continues running with a memory corruption.

* By “easily detected” I mean that NULL pointers are not really that hard to identify. Windows guarantees that the first 64KB of memory are a PAGE_NOACCESS region, so there’s absolutely no chance that someone is handing you a valid address that is strictly smaller than 65,536. Corollary: It’s a moot point to try detecting NULL pointers by using IsBadXxxPtr. It’s true that a NULL pointer is not always NULL, e.g. if you’re accidentally obtaining a pointer to a field in a NULL structure pointer or obtaining a pointer to a member using a NULL this pointer. However, in all these cases (unless you have structures bigger than 64KB, which is a whole different problem) you can simply test the address for < 64KB.

Generating Prime Numbers in a Range (Was: LINQ Challenge), Part 4 – More on Sieves

As it is often the case with algorithms, there’s a better one yet for the problem at hand. The Sieve of Eratosthenes that we employed in the previous step is significantly faster than naively testing every prime number in the range, but there are additional improvements on this approach.

The Sieve of Atkin is a much smarter algorithm that relies on certain properties of modulo-sixty remainders of prime numbers. The algorithm is based on the following facts (and do feel free to check the Wikipedia entry for more details):

• All numbers with a modulo-sixty remainder that is divisible by 2, 3, or 5 are not prime because they are divisible by 2, 3, or 5, respectively. (This leaves only a handful of modulo-sixty remainders to consider.)
• All numbers with a modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1 (because these remainders themselves have a modulo-four remainder of 1). These numbers are prime iff the number of solutions to 4x^2 + y^2 = n is odd and the number is not a square of another integer. (The proof to this and the following two claims is here, behind a paywall.)
• All numbers with a modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime iff the number of solutions to 3x^2 + y^2 = n is odd and the number is not a square of another integer.
• All numbers with a modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime iff the number solutions to 3x^2 - y^2 = n is odd and the number is not a square of another integer.

Hence, a relatively straightforward algorithm can be used to enumerate all solutions to the above quadratic equations in our range {2…N}. Another iteration of refinements will remove all numbers divisible by 2, 3, or 5 – and we have ourselves a sieve, the Sieve of Atkin.

Efficiently implementing the Sieve of Atkin is not trivial – the straightforward algorithm given on the Wikipedia page is in fact slower than the Sieve of Eratosthenes. Daniel J. Bernstein’s primegen is one of the most efficient implementations known, but it’s written in C and comparing its performance with that of a C# Sieve of Eratosthenes is not fair.

Therefore, I embarked on some refinements to the Wikipedia-provided algorithm and obtained the following results: [“Full” refers to the most naive algorithm, “Sqrt” and “SqrtN2” to its optimizations, “Sieve” to the Sieve of Eratosthenes and “Atkin” to the Sieve of Atkin]

In other words, the Sieve of Atkin is a significant improvement over the previous result, especially for very large ranges. A visualization is in place to show just how much better we got with these improvements:

This graph is rather hard to read because the naive algorithm explodes very quickly and looks like a vertical asymptote; there’s also an easily observable difference between the two sieves and the “sqrt”-optimizations.

The same on a log-log scale:

We can learn a few things from this graph. Recall that after plotting a function f(x) in a log-log scale, if we get a straight line with slope M, it means log x = M log y, or equivalently log x = log (y^M), so we get x = y^M. Therefore:

1. The slopes of the two “sqrt”-optimizations are roughly the same, and therefore there’s no big-O* difference between the two algorithms.
2. The slope of the naive algorithm is greater than 1, so the naive algorithm is “worse” than O(n).
3. The slope of the Sieve of Eratosthenes goes up at ~2,000,000 while the slope of the Sieve of Atkin remains constant. Both have a slope < 1 for small ranges, so both are sub-linear.

In the next (and final) post I will summarize some of our findings and point out a couple of other ideas for implementing primality tests in ranges.

* Recall that a function f(n) is big-O of g(n), i.e. f(n) = O(g(n)) if there exists a constant c such that f(n) = c g(n) for all n. (The Wikipedia definition requires this criterion to hold for all n > some constant, but it’s really irrelevant in the big picture.) Therefore, if the slope of two functions f, g is the same on a log-log scale, but their y-intercept is different, then we have: y1 + log f(x) = y2 + log g(x). From this, log f(x) = (y1 – y2) + log g(x) and therefore f(x) = exp (y1 – y2) g(x), but exp (y1 – y2) is a constant and the definition of big-O holds.

Generating Prime Numbers in a Range (Was: LINQ Challenge), Part 3 – Sieve Me One

It’s time for the big guns. We’ve already seen simple optimizations to the problem of generating the prime numbers in a range.

A completely different approach, the Sieve of Eratosthenes, is based on a very simple idea. Write down all the numbers in the range {1…N}. Mark 2 as prime. Now strike out every multiple of 2 as composite. Move on to the next number that is not marked as composite yet, and strike out every multiple of it as composite. (The next number, incidentally, is 3; then 5; then 7; and so on.)

After Sqrt[N] steps you have a list of all prime numbers; these are the numbers you did not strike out as composite. An implementation:

static int[] Sieve(IEnumerable<int> range)
{
    int highBound = range.Last();
    bool[] sieve = new bool[highBound];
    int sqrt = (int)Math.Sqrt(highBound);
    for (int i = 2; i <= sqrt; ++i)
    {
        if (sieve[i - 1])//this was already marked as composite
            continue;

        for (int j = 2 * i; j <= sieve.Length; j += i)
            sieve[j - 1] = true;//composite
    }
    sieve[1 - 1] = true;//1 is not prime
    List<int> numbers = new List<int>();
    for (int i = 1; i <= sieve.Length; ++i)
        if (!sieve[i - 1])
            numbers.Add(i);
    return numbers.ToArray();
}

The biggest drawback of using a sieve is its memory utilization. We’re using O(N) bytes of memory to store Boolean variables representing whether the number is prime or composite. [To save initialization costs, I assume that sieve[i] is false if the number is prime; otherwise, we’d have to initialize the sieve to true, which is a costly operation. BTW, it’s possible to use a single bit per integer instead of a whole bool. This is left as an exercise for the reader.]

As for the runtime complexity, well, we’re doing at most Sqrt[N] iterations through the sieve with values {2…Sqrt[N]}. For each value k in this range, we perform (N/k)-1 operations, marking the elements in the sieve as composite. One attempt to arrive to an upper bound is by saying that we have at most Sqrt[N] iterations and each iteration performs at most N/2 operations, hence we have ourselves an O(N^(3/2)) algorithm. However, this upper bound is very far from being tight, and the real upper bound is somewhere between O(N) and O(N(Log[Log[N]])).

Fortunately, the sieve fares very well in comparison to the other alternatives, because the whole purpose of our little exercise is to generate prime numbers in a big range. If we were concerned with primality testing of a small set of numbers, a sieve wouldn’t fit our purposes*; here, however, it scales much better than the iterative alternatives.

Here are some results: [run times in ms, “Full”, “Sqrt” and “SqrtN2” refer to the algorithms presented in the previous posts]

Note that the sieve beats the iterative algorithms by a factor of 10 and sometimes more, making it a much more likely option for generating prime numbers in a large range (more than 11,000,000 numbers scanned in just a little more than 2 seconds). In our final installment, we’ll examine the Sieve of Atkin, a final refinement to the idea of generating primes using a sieve.

* The whole idea of a sieve is feasible if you’re testing a very large range of numbers. If the method was called to calculate prime numbers in a range {K…K+100} where K is very large, creating a sieve up to K+100 would be prohibitive. Hence, for the measurements I used 1-based ranges.

Generating Prime Numbers in a Range (Was: LINQ Challenge), Part 2 – Simple Optimizations

There are two rather trivial optimizations to the problem of generating prime numbers that we saw in the previous post.

First there’s the observation that it suffices to test all potential divisors in the range {2…Floor[Sqrt[K]]} to ascertain that K is prime. This is not much harder to accomplish and is a significant running time optimization:

static int[] Sqrt(IEnumerable<int> range)
{
    return range.Where(n =>
    {
        if (n == 2) return true;
        int sqrt = (int)Math.Sqrt(n);
        for (int i = 2; i <= sqrt; ++i)
            if (n % i == 0)
                return false;
        return true;
    }).ToArray();
}

The idea is still the same – we iterate over lots of numbers and check if own target is divisible by these numbers. However, this “lots of numbers” is much less than the “lots of numbers” we had earlier.

Specifically, we’re still not using any memory other than a constant amount, but the runtime complexity has improved significantly. This time, for each of the prime numbers in the range K we do at most Sqrt[K] iterations of the inner loop. Assuming as earlier that there are roughly 2Sqrt[N]/Log[N] numbers, the biggest possible number is N, and the amount of work per number is Sqrt[N], we obtain an upper bound of 2N/Log[N] on the amount of work. (This disregards the work needed for the composite numbers; this is an assumption we’ve made before.)

This is a big improvement – the difference between N^2 and N^(3/2)/Log[N] is quite telling, and so is the difference between N^(3/2)/Log[N] and N/Log[N]. Here’s a graph:

Now we can introduce another optimization. It won’t reap us as many fruits as the previous algorithmic improvement, but it’s still worthwhile. Specifically, we note that there’s already a special treatment of the number 2 in our method. Why don’t we automatically discard all even numbers before embarking on the Math.Sqrt call, which is quite expensive?

Furthermore, if we discard all the even numbers in advance, we can start the loop from 3 and advance through only the odd numbers. (Obviously if K is divisible by 2k then K is divisible by 2, hence there’s no need to test even divisors other than 2.)

This brings us to:

static int[] SqrtN2(IEnumerable<int> range)
{
    return range.Where(n =>
    {
        if (n != 2 && n % 2 == 0)
            return false;
        int sqrt = (int)Math.Sqrt(n);
        for (int i = 3; i <= sqrt; i += 2)
            if (n % i == 0)
                return false;
        return true;
    }).ToArray();
}

Not much complicated, but has a potential for running quite faster. For the even numbers, we’re not performing the expensive Math.Sqrt call at all; for prime numbers, we’re going over half as many potential divisors as we did earlier. This is not an improvement if you’re analyzing theoretical runtime complexity, but from a practical standpoint it’s quite an improvement indeed: [times in ms, “Full” stands for the algorithm from the previous post]

Predictably enough, for values of N both small and large, the new version is almost twice as fast as the first one. Still, it takes us 1.5 seconds to generate less than 2,000,000 prime numbers. This scales linearly, but it’s still far from ideal.

The massive breakthrough can be obtained by using the Sieve of Eratosthenes, which is a completely different approach for generating prime numbers in a range. We’ll examine it in the next installment.

Generating Prime Numbers in a Range (Was: LINQ Challenge), Part 1 – Introduction

Justin Etheredge posted a nice LINQ challenge – write a LINQ query, using whatever chained lambdas you want, but no custom LINQ methods, to generate the prime numbers in a given range.

Over at his blog, Justin analyzes a couple of possible implementations with real LINQ queries (although the more efficient of them will have fairly complex lambdas in the query). I, on the other hand, would like to focus on the lessons you can learn from this kind of simple exercise, without using LINQ queries for now.

Here are the rules of engagement for this mini-series of posts: We want to implement a method that takes an IEnumerable<int> which is the range of numbers and returns an int[] which is an array of all prime numbers within that range. [It would be unfair to some algorithms if we require that an enumerable is returned, as it would be unfair to return a sieve that specifies which numbers are prime and which aren’t.]

Primality-wise, 1 is not a prime, but it doesn’t matter because no one will pass a range that starts with 1; 2 is a prime, so it 3, and so on.

Without further ado, here’s the most naive thing conceivable:

static int[] Full(IEnumerable<int> range)
{
    return range.Where(n =>
    {
        if (n == 2) return true;
        for (int i = 2; i < n; ++i)
            if (n % i == 0)
                return false;
        return true;
    }).ToArray();
}

This is rather horrible; we iterate over the entire sequence and for each element, check whether it’s prime by going through all possible candidates for a composite divisor and checking them individually. The ToArray() call at the end materializes the query.

Let’s attend to the complexity of this method. It does not use any additional memory (more accurately, it uses only a constant amount of memory that is not a function of the range size), which is a positive characteristic. However, its runtime complexity leaves much to be desired. Here’s a simple upper bound on its runtime, assuming that the range is {1…N} for some N:

For each number k in {1…N}, the algorithm performs k iterations of the loop if the number is prime, and less than k iterations if the number is composite. Therefore, the total number of steps performed by the algorithm is at most N(N+1)/2, or O(N^2). This is not a tight upper bound, because not all numbers in the range are prime (in fact, 50% of the numbers require only one step of the loop; another 33% of the numbers require only two steps; etc.).

Another approach for estimating the runtime complexity is evaluating the number of primes in the range {1…N}, because these are the numbers that are expensive to test. A known result for the number of primes less than X is roughly 2Sqrt[x]/Log[X]. For each of these numbers k we perform roughly k iterations inside the loop; the biggest possible one is N and therefore we perform at most N(2Sqrt[N]/Log[N]) operations, or O(N^(3/2)/Log[N])). This is much better than O(N^2) and is a tighter bound on the runtime complexity of our algorithm. It really grows much slower – here’s a plot of the two functions:

This doesn’t change the fact that it’s really horribly slow. Here are some results for relatively small values of N, times shown in milliseconds: [measured on my machine, of course]

There are some significant improvements that can be made to this. The most trivial of all is known to any high school student: If you’re checking whether K is prime, you don’t have to test all the factors {2…K} – it’s enough to test all the factors {2…Floor[Sqrt[K]]} and you’re good. We’ll attend to that in the next installment.

Beware of Evil Wizards

Ten years ago, Andrew Hunt and David Thomas published the incredible book, “The Pragmatic Programmer: From Journeyman to Master”. It’s not that I like this book because it has taught me so many things; I mainly like this book because of what it has not taught me.

And one thing this book has not taught me is to use Add New Item –> “Some Amazing Technology” Class Template and then just adjust the grid on the control ever so slightly, and bam – there’s your user interface in all its glory.

Here’s what “The Pragmatic Programmer” has to say about it:

[…] Tool makers and infrastructure vendors have come up with a magic bullet, the wizard. Wizards are great. […] But using a wizard designed by a guru does not automatically make Joe developer equally expert. […] Don’t Use Wizard Code You Don’t Fully Understand.

Why is that that we developers should not rely on wizard-generated code, but it’s OK for us to rely on the operating system’s code or on the .NET Framework’s code?

[…] We’d feel the same about wizards if they were simply a set of library calls […] that developers could rely on. But they’re not. Wizards generate code that becomes an integral part of Joe’s application. […] Eventually, it stops being the wizard’s code and starts being Joe’s.

It’s funny how these words never ceased to be true. Despite the ten-year-old warning against Evil Wizards, code generation inside the development environment has become an increasingly popular technique, and not just for spiffy user interface generation. Here are two wizards I use all the time, in Visual Studio:

• Adding a WCF service reference generates a whole bunch of proxy code into your project, and not just the bare minimum service contracts and data contracts that you would otherwise write by hand;
• Dragging a table across a LINQ to SQL design surface generates a strongly-typed data context, an entity class for each table, relationships between entities, identity constraints and whatnot.

Ten years after “The Pragmatic Programmer”, I’m not saying that you should stop using the Visual Studio wizards to generate code for you. But if you don’t understand the code generated by the wizard even though you’re using and adapting it to your needs, you’re in for some great trouble. (Unfortunately, presenters at conferences and class teachers are often guilty of spreading the trouble.*)

The telling sign is this: If a technology were easy enough so that you didn’t have to thoroughly learn it before applying it, why would there be a wizard for generating code associated with that technology?

* The most unfortunate thing is that sometimes even we, the public speakers who show other people the power of those Evil Wizards, don’t fully understand the code being generated by them. I had the chance to witness, time and again, a presenter showing a bunch of code effected by a simple click of a button, and when something goes wrong the only resort seems to be to regenerate the whole code from scratch. Is this something you would recommend to your fellow developers?

C++ in Visual Studio 2010: Windows Platform Developers User Group

Almost two years ago, I wrote about the TR1, a set of additions to the C++ standard that was implemented in a Feature Pack for Visual Studio 2008. Back then, I gave the post a rather provocative title: C++ Developers Just Got Lambdas?

Well, now we’ve got them. The new C++ standard, dubbed C++0x (where the x is going to be a hexadecimal digit, hopefully A) has lambda functions as one of its features. Visual Studio 2010 implements some of the standard (draft), including lambda functions.

Yesterday I had the pleasure of presenting C++0x to a group of Windows C++ developers, at the Windows Platform Developers User Group organized by Alon Fliess and Pavel Yosifovich. I tried my best to touch all aspects of C++0x, including auto variables, the new “for each” statement, lambda functions, static assertions, the “decltype” operator and a brief mention of rvalue references. [I plan to describe at least some of these features in greater detail in the future.]

Here’s a teaser from the session’s code:

template <typename Iterator, typename Combiner>
auto aggregate(
    Iterator begin,
    Iterator end,
    Combiner comb,
    decltype(comb(*begin,*begin)) initial)
        -> decltype(comb(*begin,*begin))
{
    decltype(comb(*begin,*begin)) result = initial;
    for (; begin != end; ++begin)
    {
        result = comb(result,*begin);
    }
    return result;
}

auto add_f = [](int a,int b) { return a+b; };
list<int> numbers = …;
auto something = aggregate(numbers.begin(),numbers.end(),add_f,0);

Confused? Regardless of whether you attended the session, feel free to download the slides and code. The code is very detailed and shows off some really neat things you can do in C++0x, especially with applications of lambda functions. The language becomes much richer, and naturally much more complicated, but I believe that in the course of the next few years we’re all going to ask ourselves how we managed to write any C++ at all without the features of the new standard.

By the way, if you have ideas for future meetings of the Windows Platform UG, or if you would like to deliver a presentation at the UG, I’m sure Alon and Pavel will be more than happy to hear about it. (You can also contact me if you want to, and I will forward your suggestion to them.)

SDP 2009: .NET Debugging Tutorial

A few days I delivered a full-day session titled “Debugging .NET Applications” at the Sela Developer Practice. The session was packed and I was really happy to see lots of people interested in .NET debugging – this seems to be an area of incessant popularity.

I only had one day to deliver lots of material – I basically tried to cram the entire .NET Debugging course I teach at Sela into a single day. We started with debugging basics such as dump files and symbols – and considering the dozens of ways to capture a dump these days, even seasoned programmers are in need of a refreshment. Next, we talked about Visual Studio debugging, including Managed Debugging Assistants which are a great but often overlooked feature. Most of the day, however, was dedicated to the WinDbg + SOS duo, which I used to diagnose a couple of memory leaks, a deadlock, a crash, and other scenarios. At the very end I also had a little time to mention other tools, such as Process Explorer, Process Monitor, Application Compatibility Toolkit, Hawkeye, SOSEX, my own Wait Chain Traversal helper and others.

I thoroughly enjoyed the session, as always. If you attended the session (and even if you didn’t), you can download the code samples here. (Unfortunately, the presentations won’t be available online.)

[To view the conference recordings, some of which are already available, with three sessions freely accessible to everyone, including the 3-hour MVPs panel on life, the universe and everything, start here.]

SDP 2009: Parallel Programming with .NET 4.0 and Visual Studio 2010

A few days ago, at the Sela Developer Practice, Eran and I delivered a session titled “Parallel Programming with .NET 4.0 and Visual Studio 2010”. In this session we wanted to highlight the new features for parallel programming in .NET 4.0 – the Task Parallel Library and PLINQ – as well as the new Visual Studio 2010 features in the debugging and profiling areas.

We started with what we call explicit parallelism – manually creating tasks and specifying what to do when they execute and when they complete. We used tasks to show some neat design patterns such as a pipeline of tasks and a tree of tasks. Then, we moved to implicit parallelism – using the facilities of the runtime to concurrently schedule a for loop and a foreach loop. At the end of the session we showed the new debugger windows and the new concurrency profiling mode.

The demos and slides that we used can be downloaded from here. If you’re looking for more comprehensive samples, don’t miss the recently updated Microsoft samples for Parallel Programming.

There will be video recordings of the conference available to attendees at the conference website, so don’t forget to check back.

SDP 2009: Building Workflow Services with WF 4.0 and WCF 4.0

Eran and I delivered a session titled “Building Workflow Services with WF 4.0 and WCF 4.0” at the Sela Developer Practice on Tuesday. This session was all about integrating the new features of WF 4.0 and WCF 4.0 to create a workflow application that orchestrates the execution of multiple WCF services.

During the session, we showed how to use WCF 4.0’s ad-hoc discovery, how to write declarative workflows and use custom activities, how to take advantage of the built-in messaging activities in WF 4.0 and how to integrate a workflow application into Windows Server AppFabric. It shows off basic and advanced features of WF 4.0 including bookmarking support, variables and arguments, persistence participants, tracking participants and more.

The demos and slides that we used are available here – feel free to use our sample application to learn more about WF 4.0, WCF 4.0 and workflow services.

Video recordings of the sessions will be available to attendees soon at the conference website. Stay tuned.