7

What strategy would you use to detect memory leaks?

I was asked this question in an interview that was mostly focused on C++, and couldn't find an answer. I said that there are tools that do it and that I would use them, but that wasn't sutisfactory, and I had nothing else I could think of.

When I searched later for an answer on the internet, all I could find was references on how to use different tools, and not what strategies they use.

  • 1
  • It is related to garbage collection. I recommend reading gchandbook.org – Basile Starynkevitch Mar 17 '17 at 8:24
  • "Strategies" and "tools" and "built-in software features" are different things. Did you ask the interviewer if "strategy" refers to steps taken by a human software developer tasked with investigating a reproducible memory leak, or something else? (That said, human investigation of memory leak is an advanced topic; the topic is highly specific to the particular software "technology stack" (platform and architecture), and only comes with work experience.) – rwong Mar 17 '17 at 8:34
  • 2
    Could you please define what exactly you mean by "strategy", and even more importantly, what exactly you mean by "detect"? – Jörg W Mittag Mar 17 '17 at 8:45
  • @gnat I may be wrong, but the fact that it was asked during an interview is irrelevant in this case. – BЈовић Mar 17 '17 at 14:51
4

You could have asked him a clarification question - "which type of memory leak?" :)

There are different types of memory leaks - obviously, some are trivial to observe and detect, some are on another extreme. Take a look at this post for types of leaks.

There are a few tools to detect leaks. Most of them are dynamic analysis tools such as DevPartner Boundschecker or Valgrind. Some static analysis tools may also detect some (trivial) cases of memory leaks.

If you have to write a memory leak detector, you need to track all memory allocations and deallocations. This can be done in many ways - hooking the system API calls directly, or instrument the code (source code, intermediate code, or even machine executable code) to keep an eye on allocations/deallocations.

| improve this answer | |
3

Personally my answer would be:

First utilise the warnings that the compiler provides, which in the case of some well known companies tool chain defaults to silent, by making sure that all the warnings were enabled. Actually I would recommend that the compiler warnings are all turned on and a coding standard used that called for zero warnings.

I would also strongly consider running static analysis with a tool such as Coverity, or even PCLint, as they are great at spotting potential issues like this.

Then I would run the entire test suite under a profiling tool to ensure that we had as near to 100% coverage as possible, then again under a checker such as Valgrind, or even the debugger if it support this.

Finally, and probably only if the tool chain & target did not support such tools and if I could not buy in a library to do this, I would consider implementing my own, either in a special build for test or as a background component of the product.

Only then, if asked to expand, I would start into how I would implement this.

If asked why this strategy I would reply cost, the compiler authors have spent a great many thousands of man hours addressing issues such as memory leaks, as have the static analysis tool developers and both provide 100% coverage of the code. Tools such as Valgrind can do an excellent job but only if the code is 100% exercised while they are watching - hence using a profiling tool to establish coverage.

Generally memory profiling tools do not belong in production code as, for the most part, they will normally be quite a heavy overhead and it is normally more effective to enable, install or enable garbage collection.

They may have been looking for you to mention RAII, Resource Acquisition Is Initialization, but strictly that is a strategy for avoiding rather than detecting memory leaks.

| improve this answer | |
  • 1
    While RAII does as you say avoid rather than detect leaks, it is worth noting that for any resource where it is used, you can be certain that leaks do not occur, which may make the job easier, as it could allow you to concentrate your efforts in a small section of am application where problems are much more likely to be found. In the extreme, if an application uses unique_ptrs for all objects except one that is held in a bare pointer, if unbounded memory usage growth is detected you can be very sure where the culprit is. – Jules Mar 17 '17 at 12:14
  • @Jules True enough - they you just have to locate all of the problems due to dangling pointers. – Steve Barnes Mar 17 '17 at 16:03
  • Wrong answer. A compile-time warning or hook will not be able to detect leaks. Leaks can only be detected at runtime – rurban Mar 20 '17 at 18:45
  • @rurban many of the memory leaks that I have found were associated with compile/link time warnings. Some compiler warnings deal with potential memory leaks. Code with no warnings very rarely has any memory leaks - possibly because of competent programming leading the lack of both warnings and leaks of course. – Steve Barnes Mar 20 '17 at 19:47
2

There are two major strategies:

A leak is a malloc without a free (which in C++ is a new without a delete). Global malloc's without a free are cheap, as the free is generally not needed. The process cleanup at the end of the program lifetime does it better and faster then searching the trees for the pointer and add it to the free list. But mallocs in nested functions may be called quite often, and this memory eats up, it needs a matching free. An alloca on the stack does not to be freed at all. That's the beauty of the stack.

Adding malloc/free hooks alone do not work for detecting leaks. You need to query the collected hook statistics at the end. Using compile-time tools, like bounds-checkers do not work for leak detection. It needs to mark and count each malloc'ed pointer and observe a matching free at run-time.

  1. Interpret/jit the CPU ops in a sandbox, detecting malloc and free calls at runtime. See How does valgrind work. valgrind memcheck works with every binary and is the general solution.
  2. Add the malloc/free hooks at compile time as in the new AddressSanitizerLeakSanitizer, as in -fsanitize=leak or -fsanitize=address and ASAN_OPTIONS: detect_leaks=1. This is of course much faster, but needs esp. prepared binaries.

In dynamic languages it is much easier: You can easily hook your VM memory allocation calls, and report missing free calls at the end of the program.

| improve this answer | |
  • 2
    Given that it's tagged C++, perhaps that should read "new without a matching delete, new[] without a matchingdelete[] and/or malloc() without a matching free()`. But perhaps that's a bit long-winded... – Toby Speight Mar 20 '17 at 15:12
  • Well, new/delete is basically malloc/free with the additional complexity of method dispatch. To know which delete is called is walking the class chain to find the best delete method. So better is to the explain it with the underlying malloc/free call. – rurban Nov 10 '17 at 8:22
  • There's no requirement that new and new[] be implemented using malloc(). Although that's a common implementation, they are conceptually distinct. – Toby Speight Nov 10 '17 at 8:57
0

I think you were on the right track. The simple answer is "monitoring" and that's a good starting point for the conversation. I would have said something like:

I would implement a monitoring tool that would report the memory allocation of all programs on the machine. Then I would implement an alerting system that would send the on call person a text / phone call depending on the severity of the alert.

They may have been looking for you to mention a specific tool or possibly how the tool works?

You wouldn't happen to have been applying for a DevOps position, would you? :)

Anyway, back to the memory leak question. The easiest way to go about that would be to implement a tool like a .NET profiler, which basically has visibility into your code and report metrics about:

  • Method perfomrance (to the point where you can view the call stack and the performance for all methods all the way through)
  • CPU consumption
  • Memory consumption

I've used New Relic in the past for this (their APM product), which is an awesome tool.

And, yes, there is probably a slight "parasitic" effect you can get by using this kind of tool, but the benefits greatly outweigh it, in my opinion.

Also, if you were asked how you would write your own tool, I would first explain that it's not worth the effort because why re-invent the wheel? But if they really had to know, then I would say to create an agent that would be installed on the machine that would monitor all running apps and report their usage back up to some storage / API that could be reported on later. But then you'd ALSO have to build the reporting tool and tie it to some kind of alerting tool. However, there are existing tools that are well worth the price for these kinds of things.

In the end I would have double-downed on the tools approach. If they didn't like that then maybe they would rather write it themselves? But honestly that is just not worth the effort and they would most-likely spend more on developing / maintaining something like that than to just buy a tool. And if they're that stubborn than you probably dodged a bullet anyway.

| improve this answer | |
0

Leaving aside the various tools, environment warnings and moving to static memory structures, I can only guess what they were looking for here is some kind of reference count mechanism where a counter of some kind is incremented when memory is allocated and decremented when the memory is deallocated.

This is a portable method that works on any platform and doesn't require any further tooling.

| improve this answer | |
0

A strategy for memory leak detection is performance testing. Performance testing is not only for finding the limits of the application but should also include a steady state load over a span of N hours. For example, run the application under load for 4 hours.

If one does this as part of the development process then memory leaks can be identified prior to release and fixed.

Once a leak has been identified, a tool such as WINDBG can be used to find the offending methods so fixes can be applied.

| improve this answer | |
0

There are several ways to detect a memory leak:

  1. Try to have as high unit tests code coverage. Then execute unit tests, using valgrind, or similar tool. Since it takes really long, this can be done as a task for nightly build
  2. Ask testers to check the memory usage during tests, but this method may not be that reliable, since it may be normal memory usage
  3. Automate your tests as much as possible. Do a stress test by looking them for long time. After a week, if your PC didn't run out of memory, or get really low, you can assume it is either has no memory leak, or at least not significant leaks
  4. Execute your application using valgrind. I put that last, because I use it only if I search for memory leaks, since it is the slowest method and can't be automated
| improve this answer | |
0

I'm going to assume that the intent was to look specifically for leaks, not just general sanitation. I'm also going to assume that the intent was evaluating your coding ability, so it's not just about "I'd use valgrind" (or some other tool), but about the general approach you'd take to writing the tool itself.

In this case, the relatively simple starting point would be for your memory allocator to to a stack trace each time it's called, and keep a stack trace associated with each allocated block (along with other obvious "stuff" like the allocation size and the address of the block you allocated). When a block is freed, you remove the stack trace that's associated with that block.

When the program shuts down, you dump out any stack traces remaining in the table. Since you've dumped the stack each time, you can give a trace of not just the part of the code that allocated a block that wasn't freed, but also the full sequence of calls used to reach that point.

In most cases, along with memory leak detection, you want to handle at least writing past the end of the memory block. To do that, you typically want to allocate a block that's substantially larger than requested, write a known pattern to the extra memory, and give the client an address in the middle of the block. Then at the end of the program, if the memory contains values different than the expected pattern, you know it wrote outside the piece it allocated.

| improve this answer | |

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