An Introduction to Memento

Everything, everywhere, all at once.

One of the challenges with developing Ghostscript is that it runs everywhere. From tiny embedded systems with no backing store and very little RAM, to massive server farms with multiple CPUs, masses of storage, and extensive virtual memory; on every conceivable architecture, and on a wide range of operating systems; with many customisations such as new output devices and site integrations.

As such, it can frequently be tricky to reproduce issues that occur on real-world installations in a development environment where all the modern debugging tools that we have all become used to are unavailable.

This article will talk about one of the tools we at Artifex have developed to help us with this: Memento.

The Usual Suspects

Ghostscript is written in C. In common with most C programs, most of the issues that crop up in operation are to do with memory use. Whether it’s not allocating enough (and overrunning buffers), allocating too much (and leaking), using memory that isn’t there anymore (use after free), using memory before its been setup (uninitialised memory usage), or variations on these, most of the bugs plaguing C programs come down to memory issues.

And so, accordingly, there are a whole host of tools already out there for helping track such problems down. Memory Sanitiser, Address Sanitiser, Valgrind/MemCheck, Dr Memory, Bounds Checker, Electric Fence, Fortify, and many, many more. Whatever your favoured development environment is, it probably has a tool or three to help in this area.

Why then, faced with all these choices, have we coded another one?

Well, it’s certainly no disrespect to any of the other options. Many of them are exquisitely cleverly constructed pieces of engineering that leverage advanced facilities available in specific operating systems and architectures.

Memento, comparatively, is as dumb as a box of rocks.

But they are very attractively shaped rocks, that stack together very nicely and are exactly the right size for hitting things with. Over the years Memento has proven to be a really useful tool for finding many common problems, including some really tricky ones; we hope it can be useful for you too.

As you read on, I hope you’ll come to see Memento as a useful toolkit that can be deployed almost everywhere in a wide range of ways, including for solving a range of problems that cannot easily be solved with other tools - certainly in environments where other tools are not available.

Overall, the important thing about Memento is that it too, just like Ghostscript, runs everywhere.

Most of the memory debugging tools I mentioned above, take the form of a tool that you run on your compiled executable. For example, valgrind’s memcheck tool (henceforth, just valgrind) requires you to run a regular executable (well, probably a debug one) under valgrind. For example:

valgrind --track-origins=yes gs -sDEVICE=png16m -o out.png examples/tiger.eps

Others, such as memory or address sanitiser, require you to build your executable using a specific, modified version of the compiler. This gives an executable that will watch itself for problems when it runs.

Memento works in a different way to achieve the same thing.

Inception

Rather than relying on specific versions of tools, which may not be available on certain platforms, Memento consists of a single .c file, and a single .h file. It will work on any platform that supports standard C.

To link Memento into a project just follow these 3 steps:

1. Add memento.c into the list of files that make up your project.
2. Ensure that every .c file in the project includes memento.h (for most projects, this just involves adding #include “memento.h” to an existing header file).
3. Build every C file with the MEMENTO symbol predefined (i.e. pass -DMEMENTO to the C compiler).

Within Ghostscript, for example, builds (be they release or debug) always include memento.c. In the absence of the MEMENTO symbol, it compiles away to nothing. Our makefiles include a separate memento target (actually, several targets, gsmemento, pcl6memento, etc) that builds everything with -DMEMENTO.

Once built, the executable can be run as normal.

Cool Runnings

As it runs, Memento will keep track of each block that is allocated and freed, and will periodically check those blocks for corruption.

The techniques used here are lo-tech:

• malloc/free/realloc/calloc etc are intercepted, not using any clever compiler-specific techniques, but by using macros.
• Every time one of those calls is made, Memento counts that as an ‘event’, and keeps track of the number of events that have passed so far.
• When a block is allocated (or freed), the event number is stored with the history for that block.
• Blocks are ‘over-allocated’, with extra guard bytes at the start and end. That space is filled with known values, so that under/overruns can be detected.
• Freed blocks are kept around for a while, and are similarly filled with known values, so Memento can watch for ‘write after free’.
• At the end of execution, Memento outputs some statistics about memory use (total allocations/frees/reallocs, peak usage etc), and will list any outstanding blocks.

$ membin/gswin64c.exe -q -sDEVICE=png16m -o out.png examples/tiger.eps
Total memory malloced = 50649091 bytes
Peak memory malloced = 16907816 bytes
152033 mallocs, 152033 frees, 3 reallocs
Average allocation size 333 bytes

So, at its very simplest, just running a Memento build will give you confidence that your code isn't leaking, and isn’t obviously overrunning/underrunning or otherwise corrupting memory that it shouldn’t be.

Stop Loss

But the fun doesn’t stop there. What if it does find a problem? Suppose I run my program and it does report some leaks? Consider the following:

#include "memento.h"
#include <stdlib.h>

int main(int argc, const char *argv[])
{
  void *foo = malloc(1024);

  return 0;
}

#include "memento.h"
#include <stdlib.h>

int main(int argc, const char *argv[])
{
  void *foo = malloc(1024);

  return 0;
}

$ ./a.out
Total memory malloced = 1024 bytes
Peak memory malloced = 1024 bytes
1 mallocs, 0 frees, 0 reallocs
Average allocation size 1024 bytes
Allocated blocks:
 0x556fa969ba38:(size=1024,num=1)
 Total number of blocks = 1
 Total size of blocks = 1024

Well, in that instance, it’s pretty clear what’s going on, and it’s not hard to fix it.

What if that leak is in the middle of a lot of other processing though? Suppose you run your code, and are told at the end:

$ ./a.out
Total memory malloced = 345678 bytes
Peak memory malloced = 123456 bytes
89 mallocs, 88 frees, 0 reallocs
Average allocation size 3884 bytes
Allocated blocks:
 0x556fa969ba38:(size=1024,num=345)
 Total number of blocks = 1
 Total size of blocks = 1024

How can you track that block down?

Well, there are a few ways.

Firstly, if you’re lucky and on a system that Memento knows about, it’ll actually give you more information to start with. For instance, on my x64 Ubuntu box, I see:

0x556fa969ba38:(size=1024,num=1)
Events:
Event 1 (malloc)
0x0000560ae7b90d94 main(./test.c:6)

That list will contain the function details (with file and line) of where the block was allocated, together with the callstack which can give you valuable hints about exactly what task the program was doing at the time.

Next, you can label your blocks when you allocate them. Rather than doing:

foo_t *foo = malloc(sizeof(foo_t));

we could do:

foo_t *foo = Memento_label(malloc(sizeof(foo_t), "foo_t");

That associates a name (foo_t) with the block. When Memento spots that block leaking at the end, it will report it as:

Allocated blocks:
 0x556fa969ba38:(size=1024,num=345)  (foo_t)

In Ghostscript, most of our blocks are labeled like this, so when we see a leaked block it’s often fairly obvious where to look in the code.

Be Kind Rewind

But, that’s all very well if you’ve got your program set up like that. What if you aren’t lucky enough to have backtraces enabled on your system, and blocks aren’t labeled? And what if, even knowing where the block is being allocated, you can’t see why it’s being leaked?

What you really want to be able to do is to ‘rewind’ execution back to point that the block was allocated, and then to follow it through.

Well, reversible debuggers (like rrr and UndoDB) are a pretty new thing. If you’ve not got one set up then you’ll have to rely on Memento to approximate that for you.

Young Einstein

Madness, apparently, is doing the same thing over and over, and expecting different results. Fortunately, most programs are sane!

Many (most?) programs out there are deterministic in the way they run, in that if you execute them multiple times on the same input, they’ll do exactly the same sequence of operations to process them.

For instance, if I run Ghostscript twice on the same input file, I know that (barring resource problems, like running out of memory or disk space etc) the same sequence of allocations will be performed.

So if I run my program once, and block number 345 leaks, I know that if I run it again, block 345 will leak again.

Accordingly, I can run the program under a debugger and ask Memento to stop when it gets to the allocation I am interested in.

Point Break

For instance, with gdb, we can start debugging the program:

$ gdb -q —args myprogram
Reading symbols from myprogram

Then, at the prompt, we can ask it to put a breakpoint on a special function that Memento uses to stop at:

(gdb) break Memento_breakpoint
Breakpoint 1 at 0x684442: file ./memento.c, line 1162.

Then we start the program running:

(gdb) run
Starting program: /home/robin/myprogram

Immediately (OK, well, on the first allocation, which is generally pretty soon), this will stop at our breakpoint:

Breakpoint 1, Memento_breakpoint () at ./memento.c:1162
1162	{

At this point, we have the opportunity to give Memento some instructions. We do this by using the debugger’s ability to call functions in the C. In this instance, we want to tell Memento to stop at the breakpoint again, when we try to allocate block 345.

(gdb) call Memento_breakAt(345)
$1 = 345

Then, we’re off to the races. We tell gdb to continue:

(gdb) c
Continuing.

And the program will continue. We’ll see all the usual program output, until we reach our block:

Breaking at event 345

Breakpoint 1, Memento_breakpoint () at ./base/memento.c:1162
1162	{

At this point, we can use all our usual debugger tricks; bt gives us a backtrace of where we are, fin finishes the current function and steps back up into the calling code, n and s allow us to step over and into the next instructions respectively. We can examine (and even alter) variables.

We even have the option to give Memento more commands; maybe telling it to stop when another block is allocated, or we could ask it to tell us what block (if any) a given address is in:

(gdb) call Memento_find(ptr)
Address 0x55555790daf8 is in allocated block 0x55555790da98:(size=816,num=87)

or perhaps by telling it to stop when a given address is freed:

(gdb) call Memento_breakOnRealloc(ptr)

We can run through the program multiple times, gathering more and more information about how it behaves around the blocks that fail. While, in most cases, the addresses used for the blocks will change each time we run through the program (indeed, operating systems like Linux and Windows make a security feature of this!) the numbers of the blocks should remain constant, allowing execution to sanely be replayed again and again.

All the above applies to pretty much any debugger. The mechanics of driving the debugger may vary, but the basic steps are the same.

So much for leaks, then. How does Memento cope with other problems, like buffer overruns or other heap corruption?

Intacto

As the program runs Memento keeps a count of ‘events’ that have occurred (mallocs, reallocs, frees etc). Every so often, Memento will trigger a sanity check of all the memory it knows about. It’ll run through ensuring that the pre- and post-guard bytes on each block haven’t been corrupted, and that no one has written to any freed blocks.

If such an event is detected, Memento will output something akin to the following:

Allocated blocks:
  Block 0x55555790da98:(size=816,num=87) Postguard corrupted.
	Block last checked OK at allocation 240. Now 347.

This probably means that block 87 has had a buffer overrun. We know it was OK when the system last checked on event 240, but now (at event 347) it’s corrupt.

So, at some point between event 240 and event 347, someone has written somewhere they shouldn’t.

Wouldn’t it be nice if we could narrow that down a bit?

Paranoia

Previously, I’ve said that Memento will “periodically” check the block lists for corruption. In an ideal world, we’d get Memento to check all the blocks as often as possible - why not on every single operation?

Well, sadly, running through all the allocated memory (including the memory we keep on the free list) checking for corruption, turns out to be a bit too slow for us to do every time.

In order to allow us to tune this, we have a control, called the ‘paranoia’ level.

If we’re paranoid (paranoia = 1), then we run a check every single event. If we’re less paranoid (say, paranoia = 100), then we run a check every 100 events.

We can disable all such checking by setting paranoia = 0.

Finally, we can move to an exponentially backing off strategy by using negative numbers. (paranoia = -1024, will check after 1024, then 2048, then 4096 etc events).

So, if we’re faced with the earlier example of corruption, we might run under the debugger with the following example (with some of the output abridged):

$ gdb -q --args myprogram
(gdb) break Memento_breakpoint
(gdb) run
(gdb) call Memento_breakAt(240)
(gdb) c
(gdb) call Memento_setParanoia(1)
(gdb) c

Alternatively, we can use the more concise:

$ gdb -q --args myprogram
(gdb) break Memento_breakpoint
(gdb) run
(gdb) call Memento_paranoidAt(240)
(gdb) c

Both of those will run, and stop just after the corruption is detected, perhaps with:

Allocated blocks:
Block 0x55555790da98:(size=816,num=87) Postguard corrupted.
Block last checked OK at allocation 300. Now 301.

So, we’ve narrowed down the corruption to happening between events 300 and 301. Now we can start again, and run the program through to event 300:

$ gdb -q --args myprogram
(gdb) break Memento_breakpoint
(gdb) run
(gdb) call Memento_breakAt(300)
(gdb) c

At this point, we know the memory should be intact, which we can check with:

(gdb) call Memento_checkAllMemory()
$7 = 0

A return code of 0 means “good”, whereas non-zero means that errors have been detected. We can step forward, as usual, using the debugger either over or into functions, and we can call Memento_checkAllMemory() repeatedly as we go until we find the point at which the corruption occurs. If we step too far, we can always restart, returning to event 300 each time.

Bound

Another common problem is in simulating operation under limited memory. Ghostscript, for example, has to run in printers - the very definition of resource-constrained computing.

If someone sends a job to the printer that requires far more memory than the printer can cope with, it’s (grudgingly) OK for us to refuse to print it. It’s not OK for that job to cause the printer to crash, or to cause future jobs to run out of memory too.

Accordingly, Memento can be told to impose a maximum limit in which it should work. This can either be done by setting the MEMENTO_MAXMEMORY environment variable to the amount in bytes, or by the same amount being passed to Memento using the Memento_setMax() call.

A Bug’s Life

Even this is not enough for us to be confident that every single potential point of allocation failure is safe though.

As an example, imagine that we free a large block of memory, and then allocate a small amount.

In such cases, it’d be rare indeed for the small allocation to ever fail, because the memory freed from the first block should more than be enough for the second.

On some systems, however, we might have multiple applications competing for memory and so the system might swallow up the first block before the second can make use of it.

The only way to be sure of correctness is to check the behaviour of every single closedown route in an application. This is a huge endeavour, but fortunately, Memento has some tricks to help us.

Imagine that you run a program, causing every allocation from the very first one to fail. You can check this for leaks, crashes or corruption. Then you rerun the program, this time, causing every allocation from the second one to fail. Repeat this, again and again, until the program completes normally with no failures.

Memento can certainly do this, by setting the MEMENTO_FAILAT environment variable to the number of allocations at which we should start to fail before running the program each time.

As you can imagine, this quickly starts to take a very long time indeed. If it takes you 5 minutes for your program to run through to start to fail at allocation n, it’s going to take you at least 5 minutes to fail at allocation n+1 next time.

Again, Memento has you covered. On machines that can fork() (Linux and other *nix variants), Memento can work some magic so that the whole squeezing session can run as one.

When called with the MEMENTO_SQUEEZEAT environment variable set to n, the program will run through until it is about to perform the nth allocation. At this point, the program will fork(), producing 2 identical processes, which we’ll call the parent and the child.

• The parent waits patiently for the child to complete.
• The child fails the allocation (allocation n, and all subsequent allocations), and runs to completion. Any crashes, corruptions, or leaks are reported.
• The child exits, and the parent continues.
• It allows allocation n to succeed.
• If the parent reaches allocation n+1, it calls fork() again, and the process repeats.

In this way, the test of each successive operation only takes an incremental amount more, rather than having to repeat the entire run each time.

Repo Man

As stated before, Memento has been part of our internal development for years here at Artifex. We’ve just taken the time to extract it to its own repository, which can be found here:

https://github.com/ArtifexSoftware/memento

Please do try it out and let us know what you think!

Next

I haven’t listed everything that Memento is capable of here. Other features include:

• C++ integration.
• Detailed block histories.
• Reference counting integration.
• Pointer validity checks.
• List ‘all’ or ‘new’ blocks.
• Support for ‘known’ leaks.
• Block ‘nesting’ analysis for leaks.

And new features are being added as they occur to us.

It’s a live project, and we’d love to hear suggestions (or gripes) from others who have tried to use it.