Function inadvertently invalidates reference parameter - what went wrong?

Question

Today we found out the cause of a nasty bug that only happened intermittently on certain platforms. Boiled down, our code looked like this:

class Foo {
  map<string,string> m;

  void A(const string& key) {
    m.erase(key);
    cout << "Erased: " << key; // oops
  }

  void B() {
    while (!m.empty()) {
      auto toDelete = m.begin();
      A(toDelete->first);
    }
  }
}

The problem might seem obvious in this simplified case: B passes a reference to the key to A, which removes the map entry before attempting to print it. (In our case, it wasn't printed, but used in a more complicated way) This is of course undefined behavior, since key is a dangling reference after the call to erase.

Fixing this was trivial - we just changed the parameter type from const string& to string. The question is: how could we have avoided this bug in the first place? It seems both functions did the right thing:

• A has no way of knowing that key refers to the thing it's about to destroy.
• B could have made a copy before passing it to A, but isn't it the callee's job to decide whether to take parameters by value or by reference?

Is there some rule we failed to follow?

Answer 1

A has no way of knowing that key refers to the thing it's about to destroy.

While this is true, A does know the following things:

1. Its purpose is to destroy something.

2. It takes a parameter which is of the exact same type of the thing it will destroy.

Given these facts, it is possible for A to destroy its own parameter if it takes the parameter as a pointer/reference. This is not the only place in C++ where such considerations need to be addressed.

This situation is similar to how the nature of an operator= assignment operator means that you may need to be concerned about self assignment. That is a possibility because the type of this and the type of the reference parameter are the same.

It should be noted that this is only problematic because A later intends to use the key parameter after removing the entry. If it did not, then it would be fine. Of course, then it becomes easy to have everything working perfectly, then someone changes A to use key after it has potentially been destroyed.

That would be a good place for a comment.

Is there some rule we failed to follow?

In C++, you cannot operate under the assumption that if you blindly follow a set of rules, your code will be 100% safe. We cannot have rules for everything.

Consider point #2 above. A could have taken some parameter of a type different from the key, but the object itself could be a subobject of a key in the map. In C++14, find can take a type different from the key type, so long as there is a valid comparison between them. So if you do m.erase(m.find(key)), you can destroy the parameter even though the parameter's type isn't the key type.

So a rule like "if the parameter type and the key type are the same, take them by value" will not save you. You would need more information than just that.

Ultimately, you need to pay attention to your specific use cases and exercise judgment, informed by experience.

Answer 2

I would say yes, there's a fairly simple rule you broke that would have saved you: the single responsibility principle.

Right now, A is passed a parameter that it uses to both remove an item from a map, and do some other processed (printing as shown above, apparently something else in the real code). Combining those responsibilities looks to me like much of the source of the problem.

If we have one function that that just deletes the value from the map, and another that just does processing of a value from the map, we'd have to call each from higher level code, so we'd end up with something like this:

std::string &key = get_value_from_map();
destroy(key);
continue_to_use(key);

Granted, the names I've used undoubtedly make the problem more obvious than the real names would, but if the names are meaningful at all, they are almost certain to make it clear that we're trying to continue to use the reference after it's been invalidated. The simple change of context makes the problem much more obvious.

Answer 3

Is there some rule we failed to follow?

Yes, you failed to document the function.

Without a description of the parameter-passing contract (specifically the portion relating to validity of the parameter -- is it at the beginning of the function call or throughout) it is impossible to tell whether the error is in the implementation (if the call contract is that the parameter is valid when the call starts, the function must make a copy before performing any action that might invalidate the parameter) or in the caller (if the call contract is that the parameter must remain valid throughout the call, the caller cannot pass a reference to data inside the collection being modified).

For example, the C++ standard itself specifies that:

If an argument to a function has an invalid value (such as a value outside the domain of the function or a pointer invalid for its intended use), the behavior is undefined.

but it fails to specify whether this applies only to the instant the call is made, or throughout the execution of the function. However, in many cases it is clear that only the latter is even possible -- namely when the argument cannot be kept valid by making a copy.

There are quite a few real-world cases where this distinction comes into play. For example, appending a std::vector<T> to itself

Answer 4

Is there some rule we failed to follow?

Yes, you failed to test it correctly. You're not alone, and you're in the right place to learn :)

---

C++ has a lot of Undefined Behavior, Undefined Behavior manifests in subtle and annoying ways.

You probably cannot ever write 100% safe C++ code, but you can certainly decrease the probability of accidentally introducing Undefined Behavior in your code base by employing a number of tools.

1. Compiler warnings
2. Static Analysis (extended version of the warnings)
3. Instrumented Test Binaries
4. Hardened Production Binaries

In your case, I doubt (1) and (2) would have helped much, though in general I do advise to use them. For now let's concentrate on the other two.

Both gcc and Clang feature a -fsanitize flag which instrument the programs you compile to check for a variety of issues. -fsanitize=undefined for example will catch signed integer underflow/overflow, shifting by a too high quantity, etc... In your specific case, -fsanitize=address and -fsanitize=memory would have been likely to pick up on the issue... providing you have a test calling the function. For completeness, -fsanitize=thread is worth using if you have a multi-threaded codebase. If you cannot implement the binary (for example, you have 3rd party libraries without their source), then you can also use valgrind though it is slower in general.

Recent compilers also feature a wealth hardening possibilities. The main difference with instrumented binaries, is that hardening checks are designed to have a low impact on performance (< 1%), making them suitable for production code in general. The most well known are CFI checks (Control Flow Integrity) which are designed to foil stack-smashing attacks and virtual pointer hi-jacking among other ways to subvert control flow.

The point of both (3) and (4) is to transform an intermittent failure into a certain failure: they both follow the fail fast principle. This means that:

• it always fail when you step on the landmine
• it fails immediately, pointing you at the error rather than randomly corrupting memory, etc...

Combining (3) with a good test coverage should catch most issues before they hit production. Using (4) in production can be the difference between an annoying bug and an exploit.

Answer 5

@note: this post just adds more arguments on top of Ben Voigt's answer.

The question is: how could we have avoided this bug in the first place? It seems both functions did the right thing:

• A has no way of knowing that key refers to the thing it's about to destroy.
• B could have made a copy before passing it to A, but isn't it the callee's job to decide whether to take parameters by value or by reference?

Both functions did the correct thing.

The problem is within the client code, which did not take into account the side effects of calling A.

C++ has no direct way of specifying side effects in the language.

This means it is up to you (and your team) to make sure things such as side effects are visible in the code (as documentation), and maintained with the code (you should probably consider documenting pre-conditions, post-conditions and invariants as well, for visibility reasons as well).

Code change:

class Foo {
  map<string,string> m;

  /// \sideeffect invalidates iterators
  void A(const string& key) {
    m.erase(key);
    cout << "Erased: " << key; // oops
  }
  ...

From this point on you have something on top of the API that tells you that you should have a unit test for it; It also tells you how to use (and not use) the API.

Answer 6

how could we have avoided this bug in the first place?

There is only one way to avoid bugs: stop writing code. Everything else failed in some way.

However, testing code at various levels (unit tests, functional tests, integration tests, acceptance tests, etc) will not only improve the code quality, but also reduce number of bugs.