54

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?

35

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.

  • 10
    Well, you could have the rule "never share mutable state" or it's dual "never mutate shared state", but then you would struggle to write identifiable c++ – Caleth Dec 8 '16 at 17:10
  • 7
    @Caleth If you want to use those rules C++ is probably not the language for you. – user253751 Dec 8 '16 at 20:38
  • 3
    @Caleth Are you describing Rust? – Malcolm Dec 9 '16 at 10:16
  • 1
    "We cannot have rules for everything." Yes, we can. cstheory.stackexchange.com/q/4052 – Ouroborus Dec 9 '16 at 11:17
23

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.

  • 3
    Well that's a valid observation, it applies only very narrowly to this case. There are plenty of example where the SRP is respected and there still are issues of the function potentially invalidating its own parameter. – Ben Voigt Dec 8 '16 at 19:31
  • 5
    @BenVoigt: Just invalidating its parameter doesn't cause a problem though. It's continuing to use the parameter after it's invalidated that leads to problems. But ultimately yes, you're right: while it would have saved him in this case, there are undoubtedly cases where it's insufficient. – Jerry Coffin Dec 8 '16 at 19:40
  • 3
    When writing a simplified example, you have to omit some details, and sometimes it turns out that one of those details was important. In our case, A actually looked for key in two different maps and, if found, removed the entries plus some extra cleanup. So it's not clear that our A violated SRP. I wonder if I should update the question at this point. – Nikolai Dec 8 '16 at 21:03
  • 2
    To expand on @BenVoigt 's point:in Nicolai's example, m.erase(key) has the first responsibility, and cout << "Erased: " << key has the second responsibility, so the structure of the code shown in this answer is actually no different from the structure of the code in the example, yet in the real world the problem was overlooked. The single responsibility principle does nothing to ensure, or even make it more likely, that contradictory sequences of single actions will appear in proximity in the real-world code. – sdenham Dec 9 '16 at 0:38
10

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

  • "it fails to specify whether this applies only to the instant the call is made, or throughout the execution of the function." In practice, compilers do pretty much anything they want throughout the function once UB is invoked. This can lead to some really weird behavior if the programmer does not catch the UB. – user22815 Dec 8 '16 at 18:31
  • @snowman while interesting, UB reordering is completely unrelated to what I discuss in this answer, which is the responsibility for ensuring validity (so that UB never happens). – Ben Voigt Dec 8 '16 at 18:39
  • which is exactly my point: the person writing the code needs to be responsible for avoiding UB to avoid a whole rabbit hole full of problems. – user22815 Dec 8 '16 at 18:41
  • @Snowman: There's no "one person" who writes all the code in a project. That's one reason that interface documentation is so important. Another is that well-defined interfaces reduce the amount of code that needs to be reasoned about at one time -- for any non-trivial project, it's just not possible for someone to "be responsible" for thinking about correctness of every statement. – Ben Voigt Dec 8 '16 at 19:30
  • I never said one person writes all the code. At one point in time, a programmer may be looking at a function or writing code. All I am trying to say is that whomever is looking at the code needs to be careful because in practice, UB is infectious and spreads from one line of code across broader scopes once the compiler is involved. This goes back to your point about violating the contract of a function: I am agreeing with you, but stating that it can grow to be an even larger problem. – user22815 Dec 8 '16 at 19:45
2

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.

0

@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.

-4

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.

  • 1
    This is complete nonsense. There is not only one way to avoid bugs. While it is trivially true that the only way to completely avoid the existence of bugs is to never write code, it is also true (and much more useful) that there are various software engineering procedures that you can follow, both when initially writing code and when testing it, that can significantly reduce the presence of bugs. Everyone knows about the testing phase, but the biggest impact can often be had at the lowest cost by following responsible design practices and idioms while writing the code in the first place. – Cody Gray Dec 9 '16 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.