how memray works？

[ziyoujiyi]

do you have a paper or more docs to descripe it ? thx very much

[godlygeek]

I should write some docs on this, but we don't have any today. I'll try to explain some stuff here, with a goal of eventually writing some docs that explain this all.

There's basically 4 different major pieces to how Memray captures information about allocations:

1. Detecting when memory is allocated from the system or deallocated (via malloc, free, realloc, etc)
2. Recording the Python stack associated with each of those allocations
3. Optionally recording the native stack associated with each of those allocations (when --native is used)
4. Optionally also detecting allocations via the Python allocators (when --trace-python-allocators is used)

Detecting when memory is allocated

Any C or C++ extension module dynamically links against libc.so, the C runtime support library. Likewise, the interpreter itself dynamically links against that library as well. That C runtime support library provides the memory allocators that we're interested in tracking - malloc and free and realloc and so on.

Whenever you dynamically link against some library, you know what symbols you need from it, but not what address in the program's address space those symbols will be found at when the program runs - because libraries can be loaded anywhere in your program's address space. So, when you link against a shared library, the linker creates a mapping table (called the "procedure linkage table") of function pointers for each of the undefined symbols that the built library depends upon from other libraries. Those default to null pointers, but the runtime loader - /lib/ld-linux.so.2 on Linux - fills in that mapping table with real pointers to the symbols from the libraries that it has loaded. So, when the library is built, it winds up with a static table sort of like:

struct Entry {
    const char* symbol_name;
    intptr_t symbol_addr;
};
Entry entries[] = {
    {"malloc", NULL},
    {"free", NULL},
    {"strdup", NULL},
    {NULL, NULL},
};

and when it's loaded, the runtime loader overwrites that table to something sort of like:

Entry entries[] = {
    {"malloc", 0x1234},
    {"free", 0x5678},
    {"strdup", 0x3456},
    {NULL, NULL},
};

The whole story is more complicated than that, but that simplification is enough to understand how Memray works: when you tell Memray to start tracking allocations, it searches for all of those tables in every library loaded by the process, and replaces all of the malloc/free/realloc etc entries with its own functions that a) record information about the allocation to a capture file, and then b) call the original malloc/free/realloc function that was originally in the table. When you tell Memray to stop tracking allocations, it restores the original function pointers back into those tables.

Naturally the exact details are different on macOS and on Linux, and there are some tricks to how those tables are located and modified, and we need to do extra work to detect when new libraries are loaded so that we can patch their tables as well, but the basic answer to how Memray detects allocations is that it patches Procedure Linkage Tables to interpose its own code around calls to the allocators provided by libc.

Recording the Python stack

Again, there are some complex tricks that we need to play here, but the basic idea is pretty easy: we use a Python profile function with sys.setprofile() (or really, a C equivalent to sys.setprofile()) to let us know when a Python function is entered or exited, and we use that information to track the stack for each thread in a thread-local C++ vector. We can't just look up the current Python stack at the point where an allocation occurs because asking the Python interpreter for the current stack requires holding the GIL, and it's not reasonable to have arbitrary calls to malloc or free acquire the GIL (it could lead to deadlocks). So instead, as functions are entered or exited, we record that information in a place where we can later access it without the GIL held, and when an allocation occurs, we retrieve that information and write it to the capture file (as a delta from the last recorded stack).

Recording the native stack

We actually do have some documentation on this: https://bloomberg.github.io/memray/native_mode.html covers it. Whenever a library is loaded, we record to the capture file what file path was loaded, and where in memory it was loaded. Later, at the point when an allocation occurs, we use libbacktrace to unwind the native call stack to find the instruction pointer in each frame. We dump those instruction pointers directly into the capture file, and when reading the capture file, our reporters do their best to determine the function name and file name and line number corresponding to each of those instructions. We do that by figuring out which library the instruction pointer was in based on our dumped list of loaded libraries, then searching for that library on disk and extracting either DWARF information or symbol table information from it to figure out what function was being run.

Detecting Python allocator allocations

https://bloomberg.github.io/memray/python_allocators.html describes what the Python allocators are. There's a supported API provided by CPython for swapping in your own allocators that wrap the default ones - when you use --trace-python-allocators, we simply use PyMem_SetAllocator to install our own Python allocators that wrap the original ones and do the same sort of extra work as we do when the system allocators are called, and we restore the original ones when tracking ends.

[godlygeek]

If any of this doesn't make sense or you'd like more details, please ask, @ziyoujiyi! This is sort of just a brain dump so far, but it forms the initial outline that I would flesh out for a "How Memray Works" documentation page.

[xiaoniaoyouhuajiang]

Thank you very much for your answer, which gives me a relatively comprehensive understanding of the mechanism of memray. I'm wondering if once I enter the Tracker context, memray will immediately replace the symbol address of the memory-related operation that calls the library?
In addition, I would like to ask what method I should use if I want to debug the memray Tracker. I know that the wrapper code is developed in Cython, and there seems to be no good breakpoint debugging method, right?

[godlygeek]

Yes, the procedure linkage table is patched when you enter the memray.Tracker context, and the original symbols are restored when you exit it.

As for debugging...

By lines of code, the current version of Memray is about 65% C++, 23% Python, and 12% Cython, and the Cython stuff is mostly a pretty thin layer around the C++ code. I do read the Cython generated C++ code fairly regularly, to make sure that Cython generated what I expected it to and didn't do something less efficient like creating unnecessary copies of a large data structure. It's rare for me to ever need to step through or break in the Cython code, though. If I need to set breakpoints in it, I treat the Cython generated C++ exactly like I treat our hand written C++ code: I fire up GDB with something like:

gdb --args python -m memray run -fo output.bin -m test test_list

And then I run the process once before setting any breakpoints (so that Python loads the Memray extension module and GDB learns what symbols it has), and then I set some breakpoints using rbreak (which lets me use a pattern to search GDB's list of known symbols, rather than specifying the full mangled symbol name that Cython generates), and finally run the process again to hit those breakpoints. For instance, to break in the __enter__ of the Tracker, you can use rbreak Tracker.*__enter__ (note the .* in the regex to match arbitrary stuff in the mangled name between the class name and the method name). Note also that if you're going to be debugging Memray's code, it's best to build it from source with less aggressive inlining than it normally applies, using:

touch src/memray/_memray.pyx  # setuptools rebuilds everything if even one file is changed
make MEMRAY_MINIMIZE_INLINING=1

If you don't do that, you might find that the function you want to stop in has been inlined into some other function, making it much tougher to set breakpoints.

For debugging Cython code, I know that cygdb exists, though I've never tried using it personally.

[xiaoniaoyouhuajiang]

Thanks a lot, this debugging method worked. It helped me to understand and learn more about memray