Find the bug

Today, let’s take a short test. Find what is likely to be a bug in the following code and suggest how to fix it.

void Catalogue::populate(vector<string> const& names)

  for (size_t i = 0; i < names.size(); ++i)
    vec_[i] = make_unique<Entry>(names[i]);

You may object to thus stated task. We only see a small portion of the code. We do not know what it is supposed to do in the first place, so how could we possibly figure out what is wrong with it. True, but this unfortunate situation is similar to what we face in real production code (at least I do): no documentation, no clue what it is supposed to be doing. Yet people must deal with such code: fix it, improve it. And sometimes there is something characteristic about the code pattern that makes you suspicious about a potential bug. I claim this is the case here (although the task isn’t easy).

On new and delete

BTW, do you know what this make_unique is? In C++14 this is how you are supposed to create a unique_ptr. It is more-less equivalent to:

vec_[i] = unique_ptr<Entry>{new Entry(names[i])};

But two things: creating an object on the free store and committing to destroy it automatically by wrapping it into a unique, are performed in one go, without the possibility of them being interleaved by other operations. This avoids the possibility of a memory leak as in the case described by Herb Sutter in GotW #102.

It offers one other useful thing: you no longer need to have a naked new in your code. This is very important. In my work, I have a quick memory leak detection criterion. If I see a delete used in the code, then we have a memory leak. Although it is theoretically possible to write a program that has a delete and does not have a leak (this is how smart pointers are defined after all), every time I have seen a developer (however skilled) in my work type a delete, there was a memory leak: even if it was wrapped in a try-catch or inside the destructor. You will not get it right! Use values instead of pointers, or type-erased values, or use smart pointers.

This could not be said about new though, because even if you used std::unique_ptr, you still had to call a naked new. This has changed in C++14. Now you can use std::make_unique and apply a ‘best practise’ “never use naked new” (unless there is a very good exceptional reason to do otherwise).

The solution

Now, back to the solution. By using make_unique we out-ruled the possibility of having a memory leak caused by indeterminately sequenced evaluations of sub-expressions. So, what can we tell about this short code snippet? What can we tell about variable vec_? Form its member functions resize and operator[] we can gather that this is a sequence container. Judging from the name, most probably a vector. We cannot see its declaration inside the function; this means its life-time started outside the function: it is either a global or a class member. Because it ends with an underscore, I would guess it is a class member. Because we assign to its elements objects of type unique_ptr<Entry>, we can assume, with certain degree of probability, that vec_ is a class member of type std::vector<std::unique_ptr<Entry>>, or (and this is even more likely) std::vector<std::unique_ptr<Base>> (because otherwise we would be storing a vector of values Entry instead of pointers).

Now, what is this function’s purpose? It looks like it totally destroys the previous state of vec_. It calls resize to avoid too many allocations and content moves. By resizing, it can destroy some elements. Even if some are retained, they will be overwritten by per-element assignments. We can say that the functions resets the value of vec_.

Is it possible that we are accessing a non-existent vector element? No: the resize guarantees that every index in range [0; names.size()) is valid, and the index in the loop does not go outside this range.

Is it possible that the function is exception-unsafe? This is worth examining. In the context of C++ we often talk about three kinds of exception safety guarantees:

  • basic — no resource is leaked on failure, objects can be destroyed w/o causing a crash,
  • strong — on failure the function leaves everything untouched,
  • no-fail — the function never fails.

By default, all functions are expected to satisfy the basic guarantee. Does our function meet this expectation? I.e., if our function ends in exception, can the object of type Catalogue we were modifying be safely destroyed? If one composes one’s class of components that manage their resources (like vector and unique_ptr), one does not have to explicitly define a destructor: according to what R. Martinho Fernandes calls the rule of zero, the implicitly generated destructor will just do the right thing. If we start with empty vec_ and resize it, we get a range of null unique_ptrs. Then, if somewhere in the middle of the range an exception is thrown by Entry’s constructor, it leaves some pointers with null value. If vec_ is destroyed, null unique_ptr’s destructor will behave safely: it will do nothing. Basic exception safety is satisfied.

Does our function satisfy strong exception safety guarantee? Definitely not. Is this a bug? It depends. A strong (commit-or-roll-back) guarantee is not something that you specify in the language: it is something you have to announce informally in the form of documentation to your users. We cannot see such information in our example, so for the remainder of this article we will assume that the author did not declare that the function offers commit-or-roll-back semantics. If you somehow feel wrong about this assumption, your intuition is right. We will address this at the end. But for now, please proceed with my assumption.

Then, perhaps there is no bug in the above code snippet, after all? This is a very reasonable hypothesis. You do not suspect every single piece of code of having a bug. There are lots of pieces of code out there that are bug-free. True, I somehow implied in this article that some bug exists, but in real life, in your projects there is noöne to imply such things. And besides, I could have just tricked you.

I do see a bug, though. We have to imagine how other pieces of code will be using the state that our function populate sets. One of the most common task you do on an array (vector is sort of an array with some bonus features) is to read or modify each element in the sequence. So, I am pretty sure that somewhere in the program we will have a function that does this:

for (auto && entry : vec_)

Even if you are cautious and write defensive ifs everywhere (which I do not recommend), you can be sure that someone will at some point try to access the object without the check for null address. This is not a problem in itself; but it may happen that two other things occur: function Catalogue::populate throws exception, and the exception is caught sooner than the Catalogue object goes out of scope:

  Catalogue catalogue;
  try {
    catalogue.populate(names);  // throws
  catch (exception & ex) {
  catalogue.cleanAllEntries(); // dereferences all pointers

Of course, real-life code will be more complicated, and what I have shown in a couple of lines could be scattered among a number of files. When this code is executed, exception thrown, then caught, our catalogue contains null pointers, and when they are dereferenced, we will enter what the Standard calls undefined behaviour, which will most likely end in a program crash.

Note that this problem would not occur if we weren’t catching the exception:

  Catalogue catalogue;
  catalogue.populate(names);   // throws
  catalogue.cleanAllEntries(); // this is skipped
} // destructor can deal with null pointers

If an exception is not caught too early, the object gets destroyed and noöne can access it and cause a UB. There is one function that still has to be called for our object: the destructor. However, most likely it will be safe; as noted above, the destructor is most likely implicitly defined, and it will know that it shouldn’t delete the objects under null address. This short digression illustrates how a ‘defensive’, premature trycatch can cause a program crash. Yet, there are people that would apply this philosophy: “if it throws, I need to catch it as soon as possible; otherwise it will terminate the program.”

So, an unchecked dereference of a pointer can in certain situations cause a crash. Should I put defensive ifs everywhere? Well defensive ifs come with a number of serious disadvantages. First, they make the program go slower. If you choose C++, runtime-performance is probably dear to you. Second, and this is probably more important, defensive checks make the program more obfuscated, difficult to understand, cause confusion, and indirectly cause bugs. This deserves a separate post, but for now let’s focus on the problem.

If I were to write an if in my code that checks for a null address, I would try to check, if it is intended for these pointers to be null, and if such null pointer conveys any meaning. Such a check would not be defensive: it would be part of program logic. So, I would look at function Catalogue::populate and find that it tries to assign a proper (non-null) address to every vector element. So, the content of Catalogue::populate implies its postcondition (or perhaps even an invariant) that pointers would not be null. With this implied postcondition, other functions can make an implicit precondition that pointers are not null.

Given that we imply the postcondition, the proper way of handling the bug is to make function Catalogue::populate satisfy it. But apart from the logical correctness, the function guarantees that there will be only one memory allocation. Our fix shouldn’t compromise it. And it will not. We can use reserve:

void Catalogue::populate(vector<string> const& names)

  for (size_t i = 0; i < names.size(); ++i)
    vec_.push_back( make_unique<Entry>(names[i]) );

Now we only push these elements to a vector that did not throw upon creation. Due to the call to reserve, we guarantee that the calls to push_back will not throw. (If we were sure that vec_ is of type vector<Entry> we could use emplace_back instead — for performance.)

We should feel obliged to rewrite Catalogue::populate because it avoids subtle bugs and at the same time doesn’t make the function slower or bigger. But I would go even further and rewrite the function to:

void Catalogue::populate(vector<string> const& names)
  decltype(vec_) tmp;

  for (size_t i = 0; i < names.size(); ++i)
    tmp.push_back( make_unique<Entry>(names[i]) );

  swap(tmp, vec_);

This implements the “do work on the side and swap” idiom, and thereby guarantees the commit-or-roll-back semantics; and still, it only requires one allocation. It appears reasonable to upgrade the exception safety guarantee (from basic to strong) when it doesn’t cost us in term of run-time performance.

Note also that I used good old swap even though in C++11 we have move assignment, which probably makes the intent more clear. This is for a reason. In case of vector (and most other STL containers), its move constructor and move assignment (and default constructor) can throw exceptions! You might find it strange: STL containers encourage you that their elements should have noexcept move constructor/assignment, but the containers themselves do not have this feature. This is so, to allow certain optimized implementations of containers that start (default-constructed) with some preallocated memory (e.g., a sentinel node). This also affects move operations, because semantically they are equivalent to a combination of the default constructor and a swap.

In contrast, swap on vector is guaranteed not to throw exceptions, even though it is noexcept(false). This is worth noting: it is not noexcept that gives us the no-fail guarantee, but the fact that that somebody commits to not throwing exceptions.

And if fact, we can improve the example even further, as suggested by Herb Sutter:

void Catalogue::populate(vector<string> const& names)
  decltype(vec_) tmp;

  for (auto const& name : names)
    tmp.push_back( make_unique<Entry>(name) );

  swap(tmp, vec_);

This is not just a cosmetic change. It is not that it is shorter. It is higher level. It makes the intention more clear, and avoids a bunch of potential bugs resulting from over-indexing the array, or confusing operator< with operator<=. Not that we had such a bug before, but this is how you fight with the bugs: you avoid doing things that are correct but “bug prone.”

This entry was posted in programming and tagged , . Bookmark the permalink.

37 Responses to Find the bug

  1. Hi Andrzej, nice article!

    I think

    for (auto && entry : vec_)

    should be

    for (auto && entry : vec_)

  2. rhalbersma says:

    How about replacing the raw loop with the range-insert member from `std:;vector` in combination with a `boost::transform_iterator`? See [here for live example](

    • It will probably work also. The only small problem I have with it is that it took me five minutes to study what it does and only be able to say ‘probably’. But it may be just me.

      • Nitro says:

        No, it’s not just you. I understood immediately your code, but it also took me a while to understand this version.

        Sometimes, better is worse than good. Andrzej code was good, he could have used standard sequence range insert indeed, but I’m wondering if by doing so you can guarantee that there will be no null pointer…

    • mttpd says:

      You can simplify it to a one-liner (with good names it’s possibly somewhat more readable):
      boost::push_back(tmp, names | transformed(made_unique));


    • Andy Prowl says:

      I would have used a standard algorithm too, but IMO a traditional transform() would be simpler and more readable than the version using a transform_iterator.

      transform(begin(names), end(names), std::back_inserter(tmp), …);

      Also, I would inline the lambda to improve readability further (

      I prefer “transform” over the range-based for loop because it tells immediately what the loop is for (although in this case it is pretty easy to figure out what it does either way).

      Anyway nice article, as usual!

    • If you were to use an algorithm, I would opt for ‘transform’ with a ‘back_inserter’, both already available in the standard without the need to pull additional dependencies.

      std::transform(names.begin(), names.end(), std::back_inserter(tmp),
      [](std::string const & s) { return std::make_unique(s); });

      • rhalbersma says:

        But even with a `reserve()` call beforehand, `transform()` will do a repeated `push_back()` whereas the ranged `insert()` with a `transform_iterator` can do this more efficiently (certainly never less efficiently). Effective STL has a specific item about this.

        • What would be the source of the innefficiency? I don’t think there is one (you are calling reserve(), and that call should be left there). [And to be honest, I am not sure Effective STL is a great reference for the STL]

        • rhalbersma says:

          With a reserve(N), there is no allocation overhead using either method. But N calls to push_back will still have to make N conditionals to check for out-of-capacity. This might be correctly branch predicted if the transform operation itself doesn’t contain complicated logic, but this is not guaranteed. A range-insert for N items can check for out-of-capacity once. So you break even at least, and possibly save N-1 conditionals.

  3. Nitro says:

    Nice article as usual, well written, I could not see something wrong and was wondering to the end where was the bug.
    Even if it is no actual bug (because we don’t know if vec_ is expected to hold null pointers or not) it is indeed a high probability of a bug, you are right. And your final rewrite is perfect.

  4. Andreas Weis says:

    Your final version has the additional benefit that it does not waste any memory if the new vector is significantly smaller than the original one. The original version would require an additional shrink_to_fit to achieve this.

    • Fredrik Littmarck says:

      Well, the drawback is that we use more memory during the call since we keep the old vector (with pointers to objects) while allocating a new one. Depending on the size of the vector and the size of the Entry type, this could theoretically be an issue in low memory conditions.

      And while vector::clear() does not guarantee reallocation, I’ve certainly seen it do it in some implementations, so the shrink_to_fit, while being correct, is not always needed.🙂

  5. When I read you, I just thought ‘ow. I may need to do some code review… quickly. now.’.

  6. decourse says:

    Now suppose the usage is more like this:

    Catalogue catalogue;
    for (auto& names: some_source_of_names()) {

    Now it’s not so clear-cut whether or not the final version is a net win. When populate is called the second time through the loop, vec_ already has data in it. In the final version of the code, the old entries and new entries co-exist in time, so it likely (though not guaranteed) to use more memory than the original version.

    Is that a problem? That depends. Without further information, it’s impossible to tell if it “doesn’t cost us in term of run-time performance”.

  7. KaiSt says:

    As always a well written article. Just a small comment/question about the swap. Although any serious C++ programmer should know about the swap idiom, doesn’t it better express the intent to use std::move instead of swap in C++11 and above, i.e. “vec_ = std::move(tmp)” !? Unless You really want to swap, of cause🙂

    • @KaiSt: Thank you for this question. I considered using move assignment for a moment, but vector’s move assignment (as well as move constructor and default constructor) are not noexcept! This is not by mistake: this allows certain implementations of C++ containers that start their life with some preallocated memory. I think I will update the post.

      • KaiSt says:

        Yes, I just recognized the fact, that move operators of STL containers are not noexcept. I am sorry, I should have looked up it, before writing the comment. However, it is worth noting, that swap helps me to ensure the strong guarantee only, if certain preconditions are fulfilled for the type of the objects to be swapped:

        1. Either the type implements a noexcept swap and specializes std::swap accordingly.
        2. Or the type implements noexcept move constructor and noexcept move operator.
        3. Otherwise the type implements noexcept copy constructor and noexcept copy operator.

        Did I miss something?

        • Again, your observation is very important.

          The standard says two things. First, as you observed in the last remark, swap on vector is noexcept(false). Second, section 23.2.1 paragraph 10 says that no swap operation on a vector throws an exception. So they are guaranteed not to throw, but are noexcept(false). Strange but acceptable.

          I disagree with your first statement, though. swap is no-fail not because it is noexcept(true), but because it guarantees it does not throw exceptions. Similarly, it helps you ensure strong guarantee not because it is noexcept(true), but because it guarantees it does not throw exceptions.

  8. dhardy says:

    Interesting spin. I agree that there’s a bug there, but in my opinion the bug is in catching an exception: anyone catching an exception should think carefully about what state the program may be in.

    Of course, providing a strong exception safety guarantee reduces the chance that a bug will be introduced elsewhere, but then you might as well argue that constructors (including move constructors) and destructors should not be allowed to throw: this would also be a nice property to have, but is also somewhat impractical.

    But we should think also about the consequences of a bug. Is it better to continue operating with what is likely to be incorrect behaviour, having only a message in a log users don’t normally see to explain the problem, or to have a clean crash with a message like this: “Oops, something went wrong. If you need to report this problem please include the text below.” ? Of course, it depends what else the program does, but every time I see a catch clause which logs a message and continues I think _bug_ (at a minimum there should be a comment explaining why it is safe to continue, but if it really is safe it probably doesn’t need to be logged either).

  9. nosenseetal says:

    At first I thought this article is nice and cool, but thinking about it it is a waste of time to do stuff like this. Taking care of your app running out of mem is a futile except in few cases when you know you are gonna allocate lightyearmetrictonbtyes of data in specific places in code…..
    What is really a problem with this code is that it is using loop instead of alg, i guess transform will fit here…
    So in short:
    fix makes code less readable(though for with int already is:/ ), harder to parse by maintainers and in my work only thing I care less than ex guarantees is int f(void)/ int f()

    so transform + back_inserter
    and also who says lovely Entry ctor wont throw? Or we dont care about that in a sense we want to eat exception and continue pushing_back remaining ones?
    That said .reserve() trick is nice when we are sure only exception can happen is OOM, but then again idk how many ppl actually care about this….

    also I wish c++ would give us a simple way to say when new fails pause program and call handler(most of the time it would be some exit I guess) . IDK if this can be done, but for sure I would prefer it to throw new or return nullptr “overload” of new.

    If somebody wants to bash me and sprinkle me with C++ holy water… MS STL had a broken merge implementation, that was broken in a sense that slower alg that kicks in in case OOM was broken… So if STL code was broken in OOM case caring about possible OOM cases in user code is a waste of time.

    • “also I wish c++ would give us a simple way to say when new fails pause program and call handler”

      — You can do that already, with set_new_handler.

      • nosenseetal says:

        Tnx for the A. It is always nice to find out smart people thought of solution to my problem and put in ISO long before I even knew about C++. Had same exp with rel_ops, I was like this could be cool way to do something, and rep_ops did a part of it.. thought I wish we would have language support for saying that for some user struct we want tupple like behaviour when it comes to operator < aka bool operator <(const MStruct& other) = default; //compares first members, if same second members… if same last…

        same for operator == (just compares every member of a struct)

    • dhardy says:

      I agree, worrying about OOM is a waste of time. On Linux this never happens anyway: first, stuff gets pushed to swap space and the computer potentially slows to a crawl, while second (or immediately if there’s no swap) the kernel starts killing processes (this is more designed to defend against memory/fork bomb malware than deal with legitimate programs running out of memory, though I’ve learned the hard way low-memory and no swap can mean processes die unexpectedly). Failure of a program after failure to allocate is mild by comparison.

      I think, though, the poster was more worried about Entry’s constructor throwing for other reasons.

      • nosenseetal says:

        IIRC Linux has a nasty tendency to promise memory that it doesnt have. then start killing processes if they really want to use it.😀 Could be there is a good technical reason for this, but idk what it is.

        • KaiSt says:

          @nosenseetal: Usually memory allocations will succeed in Linux as long as the allocating user process has an unmapped address range large enough to map the requested memory. In its default behaviour Linux will not immediately map the required physical memory. Once the allocated memory is referenced, it will cause page faults and the system starts mapping pages of physical memory into the referenced parts of the previously allocated virtual memory. Now it can happen, that there is no physical memory left. In this case the system starts to decrease file system cache, swaps stuff out and similar techniques. If even this is no longer possible, the out-of-memory-killer chooses a victim-process to kill in order to free resources. This is the default behaviour, but it can be changed. Just search the web for “Linux oom killer” to learn more.

          Having all this said, let’s come back to C++ and why this behaviour is really useful especially in conjunction with std::vector. If a std::vector must increase its capacity, a usual implementation will increase it with a certain amount of over-allocation in order to avoid a high frequency of reallocations. See for a program illustrating this behaviour. As You can see the over-allocation depends on the capacity and becomes significant for significant vector sizes (Please note, that the behaviour may vary between the implementations of libstdc++!). Now consider how many vector objects may exist in a complex C++ program. Immediately allocating physical memory for all these objects would really be a giant waste of physical memory!

          Developing software for embedded device I have experienced the OOM-killer in action. In our system we have a digital TV main application, which must work reliable. In addition we support web browsing. The web-browser is 3rth-party and we have little control on its behaviour. it depends on the rendered web content and on the tabs opened simultaneously. In the beginning of development we recognized, the the main application gets killed by the OOM-killer, because the browser needed to much resources. First we tried to switch of the OOM-behaviour completely. It turned out, that now the browser didn’t start at all, because it allocated to much memory right from the start. Then we configured the OOM-killer to choose the browser as victim application in order to keep the main application running. Now the system works with a satisfying compromise. The browser starts and the user can open several tabs. But if the browser needs to many resources, it gets killed by the OOM-killer. As the main application is still running, the browser can be restarted freshly. This is best compromise achievable with our systems memory limits. Without page fault based physical memory allocation and OOM-killer we wouldn’t be able to support any web browsing at all!

  10. wilhelmtell says:

    I’m probably missing something: how does he solution before the swap improvement solve the exception problem? After you reserve() and barring a fancy custom allocator you might still get an exception inside the loop; from make_unique() or from the Entry constructor. And without the swap you are still going to end up with a half-baked vec_.

    • The first part of the problem was to identify what the bug is. We identified as bug the situation when an exception in Entry’s leaves vec_ with null pointers (which could later cause the crash). We did not identify as bug the situation where old entries are mixed with new entries.

  11. Michael Golub says:

    The resize instead of reserve caught my attention almost immediately. Such inaccuracy is very common in production code. Usually when I fix it I change resize to reserve without introducing temporary variables. This does not provide strong exception guarantee, but usually I do not care.😦

    I wonder if
    can be used instead of:
    tmp.push_back( make_unique(name) );

  12. ahhz says:

    I think there is a second bug. If names is rvalue you do not want the constructor of Entry to make a copy of each string. I gave a solution here:

  13. First, thank you for your article.

    I definitely agree with the point you make about pre-mature pahantaic capturing of exception close to the origin. It is BAD practice, stop it. You don’t make a program more robust that way in fact just the contrary. let the exception propagate up the stack and have global unhandled exception handler function.

    However, the example you give is WRONG by DESIGN and you try further building on top of it😦 not so good. What I mean?
    the problem to which you point out is not present if you actually use constructors correctly! and not try to deligate a constructor job to megic functions like: init(); populate() etc.
    you code:
    Catalogue catalogue;
    try {
    catalogue.populate(names); // throws
    catch (exception & ex) {
    catalogue.cleanAllEntries(); // dereferences all pointers

    but what one should have done is simply drop the populate method and:
    Catalogue catalogue(names);

    that is the power of c++ :))))
    now we have much less code and way more robust.

    • @pip010: I agree with you to some extent. Namely, I agree that one should prefer single-phase initialization (initialize everything in constructor) to a two-phase initialization, unless there are good reasons to do otherwise.

      However, there exist reasons for not sticking to the above principle. Some frameworks that one is forced to use in work, may force you to use 2-stage initialization even if you do not need it. Sometimes you join an already working project, have deadlines, and you cannot afford and/or risk applying massive changes to the code, and you are forced to applying local solutions (that affect less code). 2-phase initialization is undesired for many reasons, but is not a bug (yet).

      I wouldn’t go as far as to say that any program can be refactored from using 2-phase init to 1-phase init. Sometimes you have two objects that need to have a reference to one another when they are initialized, and there is no easy syntax to achieve that.

      And by seeing only one function in the example above, we cannot be sure that this function is used for 2-phase init. It might as well be used for resetting the state. (Although I admit that wherever I have seen such ‘populate’ functions they would be used for 2-phase init.)

  14. Christopher Hite says:

    In the same way that it is more exception safe the corrected implementation is also more reenterancy safe. Suppose Entry’s constructor references vec_. In that case you probably do want to clear vec_ and push_back instead of swapping.

    A real life example might be reading in config and constructing objects where later objects are allowed to ask for earlier objects in their constructors.

    Even more basic rules:
    * avoid putting things in an inconsistent state
    * try to get them back to a consistent state quickly, obviously, rigorously
    * avoid giving up control while in an inconsistent state either by calling out, returning, throwing, task switching, etc

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s