std::once_flag is a glass hill

Yesterday I did a followup Q&A session for my CppCon 2020 presentation “Back to Basics: Concurrency.” (These followup sessions aren’t recorded.) During the Q&A, there was some discussion of std::once_flag. Let’s repeat my table of the three C++11 synchronization primitives (which was briefly flashed as slide 34 in the recorded talk, but I was running behind at that point and didn’t stop to discuss it):

mutex condition_variable once_flag
lock blocks only if someone “owns” the mutex. wait always blocks. call_once blocks only if the “done” flag isn’t yet set.
Many threads can queue up on lock. Many threads can queue up on wait. Many threads can queue up on call_once.
Calling unlock unblocks exactly one waiter: the new “owner.” Calling notify_one unblocks exactly one waiter. Failing at the callback unblocks exactly one waiter: the new “owner.”
  Calling notify_all unblocks all waiters. Succeeding at the callback unblocks all waiters and sets the “done” flag.

Now, the weird thing about once_flag is that its sole method, call_once, is not implemented as a C++ member function; it’s implemented as a free function that takes its “this parameter” explicitly. If you’ve seen me speak on synchronization primitives before, you know I think this is a super weird glitch in the C++11 concurrency API.

Incidentally, you can also write std::lock(myMutex); as a free function, but there is no corresponding std::unlock!

Are you surprised at the complexity of the third column there? A lot of people think of once_flag as a simple primitive. (Or perhaps I should say, they think of call_once as a simple primitive, and don’t even realize that the proper object of our attention is once_flag itself!) My mental model of once_flag took a while to develop. Here’s how I think of it now:

once_flag is a glass hill

The Princess on the Glass Hill, illustrated by Henry Justice Ford Andrew Lang’s Blue Fairy Book tells the story of “The Princess on the Glass Hill.”

Close to the King’s palace there was a high, high hill of glass, slippery as ice. Upon the very top of this sat the King’s daughter with three golden apples in her lap, and the man who could ride up and take the three golden apples should marry her and have half the kingdom.

Ignore the apples. They’re not part of this metaphor.

The important thing is that we’ve set a task to be accomplished; and in fact it can be accomplished by only one individual (you can’t have two knights marrying the princess!); and, importantly, it is also possible for an individual to fail at the task.

And so we end up with a line of knights at the base of the hill, each one waiting his turn to try the challenge. One knight tries the hill at a time; if he slides back down, he goes home in disgrace and the next one tries. (If, having failed once, a knight wants to come back the next day and try again, that’s totally fine.)

As soon as one knight succeeds, he marries the princess and everyone else can go on about their business.

This being C++, our “task” is expressed as a function (or a lambda, which is the same thing); and “success” means executing the function all the way to completion. “Failure” means that the function didn’t complete because it threw an exception. Throwing an exception is the only way to “fail,” as far as once_flag is concerned.

In code, our metaphor looks something like this:

struct Princess {};

Princess getPrincess(int id) {
    if (std::random_device()() % 10) {
        print("Knight ", id, " has slid back down the hill!\n");
        throw std::runtime_error("failed");
    }
    return Princess{};
}

void goQuesting(int id, std::once_flag& hill) {
    std::optional<Princess> wife;
    print("Knight ", id, " has arrived at the foot of the hill.\n");
try_again:
    try {
        std::call_once(hill, [&]() {
            print("Knight ", id, " is riding up the hill.\n");
            wife = getPrincess(id);
            print("Knight ", id, " has won the princess!\n");
        });
    } catch (...) {
        print("Knight ", id, " is ready to try again.\n");
        goto try_again;
    }
    print("Knight ", id, " has gone home ", (wife ? "with" : "without"), " a wife.\n");
}

int main() {
    std::vector<std::thread> knights;
    std::once_flag hill;
    for (int id=0; id < 4; ++id) {
        knights.emplace_back([id, &hill]() {
            goQuesting(id, hill);
        });
    }
    for (auto&& t : knights) t.join();
}

Godbolt Compiler Explorer can’t run multithreaded code as of this writing, but here is the code on Godbolt, anyway.

Static initializers are glass hills (with shared objectives)

Reminder: C++11 also introduced “thread-safe static initialization,” which means that static initializer expressions are also glass hills in the same sense as once_flag.

void goQuesting2(int id, std::once_flag& hill) {
    print("Knight ", id, " has arrived at the foot of the hill.\n");
    static std::optional<Princess> wife = [&]() {
        print("Knight ", id, " is riding up the hill.\n");
        auto p = getPrincess(id);
        print("Knight ", id, " has won the princess!\n");
        return p;
    }();
    print("Knight ", id, " has gone home ", (wife ? "with" : "without"), " a wife.\n");
}

The difference here is that the static local variable is shared by all callers of goQuesting2; so as soon as one knight succeeds at riding up the glass hill, all remaining knights immediately go home with a wife. Maybe the knights are all in the service of the same prince, and they’re bringing him his wife; or make up your own story, I don’t care.

Anyway, observe that the knights in this case still queue up at the foot of the hill, and it’s possible for N-1 of the threads to be blocked waiting while some other thread tackles the initialization task.

By the way, if you’re using some greenthread-esque programming framework where blocking any single std::thread could cause deadlock, I suppose you should carefully audit your use of non-constinit static initializers.

Posted 2020-10-23