Undefined

I started to write this pass at the time when I looked into LLVM. Besides documents, source codes, practice is also important in studying a new thing.

With this pass, I wanted to track the dynamic memory allocation and release and it could be used to detect memory leak. I will just call it MemoryLeakDetector. It is used to analyze a C program and the source code has to be translated to LLVM IR.

The basic idea is to replace the function call to malloc() and free() with __m_malloc() and __m_free(). The new functions allocate and free memory just as malloc() and free(). But they keep track of those allocated memory. So that we can know what memory is not free'd before the program exists. The results are printed to standard output. From the results, we know the address and size of the unallocated memory, and the call stack with  file name and line number where the memory is allocated.

I needed to solve two major problems. First, replace the function calls. Second, get the call stack and the source code information. I'll address them one by one.

1. Replace a function call in LLVM.

I used a ModulePass. This is what is done in runOnModule().

bool is_change = false;
Function *custom_malloc = NULL;
Function *custom_free = NULL;Module::FunctionListType &functions = m.getFunctionList();
vector to_replace_functions;

for (Module::FunctionListType::iterator it = functions.begin(), it_end = functions.end(); it != it_end; ++it) {
    Function &func = *it;
    if (func.getName() == "malloc") {
        FunctionType *ft = func.getFunctionType();
        custom_malloc = Function::Create(ft, func.getLinkage());
        custom_malloc->copyAttributesFrom(&func);
        custom_malloc->setName("__m_malloc");
        to_replace_functions.push_back(&func);
    } else if (func.getName() == "free") {
        FunctionType *ft = func.getFunctionType();
        custom_free = Function::Create(ft, func.getLinkage());
        custom_free->copyAttributesFrom(&func);
        custom_free->setName("__m_free");
        to_replace_functions.push_back(&func);
    } else if (func.getName() == "main") {
         // add the initialize to the main function
         //main function's arguments.
         Function::arg_iterator arg_it = func.arg_begin();
         ++arg_it;
         Argument &argv = *arg_it;// create new function
         Type *new_func_return_type = Type::getVoidTy(m.getContext());
         Type *new_func_arg_type = argv.getType();
         ArrayRef new_func_arg(new_func_arg_type);
         FunctionType *inserting_func_type = FunctionType::get(
             new_func_return_type, new_func_arg, false);
         Twine function_name("__m_set_executable_file");
         Function *inserting_func = Function::Create(inserting_func_type,
         GlobalValue::ExternalLinkage, function_name, &m);

          // insert the new function
          BasicBlock &entryBlock = func.getEntryBlock();
          ArrayRef argv_value(&argv);
          Instruction *new_inst = CallInst::Create(inserting_func, argv_value,"");
          entryBlock.getInstList().push_front(new_inst);
          CallInst *ci = cast(new_inst);
          ci->setCallingConv(func.getCallingConv());
    }
}

for (vector::iterator it = to_replace_functions.begin(), it_end = to_replace_functions.end(); it != it_end; ++it) {
    Function *func = *it;
    Function *replace_func = NULL;

    if (func->getName() == "malloc") {
        replace_func = custom_malloc;
    } else if (func->getName() == "free") {
        replace_func = custom_free;
    }

    if (replace_func != NULL) {
        m.getFunctionList().insert(func, replace_func);

        while (!func->use_empty()) {
            CallSite CS(func->use_back());
            vector args(CS.arg_begin(), CS.arg_end());
            Instruction *call = CS.getInstruction();
            Instruction *new_call = NULL;
            const AttrListPtr &call_attr = CS.getAttributes();

            if (InvokeInst *ii = dyn_cast(call)) {
                new_call = InvokeInst::Create(replace_func,
                    ii->getNormalDest(),
                    ii->getUnwindDest(),
                    args, "", call);

                InvokeInst *inv = cast(new_call);
                inv->setCallingConv(CS.getCallingConv());
                inv->setAttributes(call_attr);
            } else {
                new_call = CallInst::Create
                    (replace_func, args, "", call);
                CallInst *ci = cast(new_call);
                ci->setCallingConv(CS.getCallingConv());
                ci->setAttributes(call_attr);
                
                if (ci->isTailCall())
                    ci->setTailCall();
             }

            new_call->setDebugLoc(call->getDebugLoc());

            if (!call->use_empty()) {
                call->replaceAllUsesWith(new_call);
             }

             new_call->takeName(call);
             call->eraseFromParent();
             is_change = true;
         }
    }
}

return is_change;

First, iterate through all the function definitions and the declarations in the current module. When there is one function with the name "malloc" (it is the same to the function "free"), creates a new declaration with the same function type, same linkage and same attributes but a new name "__m_malloc". Because if there is a function declaration in the current module, there should be at least one call of that function in the current module. Once I have the function to replace, I find out where the function to replace is called (CS) and the instruction to call it (call). Then I create a new instruction to call the new function (new_call) with the arguments to the old function, and set the attribute and the calling convention. Then I replace the instruction (replaceAllUseWith).

This is a pass of LLVM. So it can be used by opt. To use it, compile the C program to .bc file by using clang and then apply this pass to it to get a new .bc file. After that, use clang to link them with the necessary object files or libraries. So the executable file will call __m_malloc() and __m_free() instead of malloc() and free().

2. Memory Management.
After replacing malloc() and free() with __m_malloc() and __m_free(), we can implement our own memory management mechanism. Since my goal is to detect memory leak, I don't do my own management. Instead, I call malloc() and free() in the new functions. But I also do some bookkeeping. After malloc() is called, I put the new allocated memory's address and the call stack into a map. This map maps a memory address to a call stack. The call stack is the necessary information to allow me to get the line numbers. After free() is called, the address is removed from the map, which means that the memory is released. So before the program exists, I just need to iterate through the map to know what memory is not released and where the memory is allocated.

3. Get the call stack.
To get the call stack, I use the library libunwind. It provides API to get the call stack. Here is what I do to get the information. It is similar to the example code.

CallStack *cs = new CallStack;
unw_cursor_t cursor;
unw_context_t uc;
unw_word_t ip, sp;unw_getcontext(&uc);
unw_init_local(&cursor, &uc);

while (unw_step(&cursor) > 0) {
    unw_get_reg(&cursor, UNW_REG_IP, &ip);
    AddressDesc al;
    al.current_pc = ip - 1;
    al.size = size;
    cs->push_back(al);
}

What is really needed is the IP, the program counter. The above code iterates through the call frames and push the IP values to cs. And this cs has the enough information that allows us to find out the call stack where the memory is allocated.

4. Get the line number
From (2) and (3), the non-released memory and the call stack is known before the program exists. But how to convert the call stack to the line number?
There is a library bfd to do this. GDB and addr2line are using it to convert an address to the line number. There is no standalone library, but the functionality is integrated into binutils. I modify the addr2line code so that it works in my code. What addr2line does is to read the binary and its symbol table. For a given address, it goes through sections in the binary and finds the nearest line that matches the address. Here is the code I modify and the necessary header file. It can be compiled as a library.

#include "getopt.h"
// #include "libiberty.h"#include "string.h"
#include
#include
#include
#include
#includeusing namespace custom_memory;
using namespace std;

namespace
{
    /* Options passed to cplus_demangle (in 2nd parameter). */const static unsigned DMGL_NO_OPTS       =  0;              /* For readability... */
    const static unsigned DMGL_PARAMS        = (1 << 0);            /* Include function args */
    const static unsigned DMGL_ANSI          = (1 << 1);            /* Include const, volatile, etc */
    const static unsigned DMGL_JAVA          = (1 << 2);            /* Demangle as Java rather than C++. */
    const static unsigned DMGL_VERBOSE       = (1 << 3);            /* Include implementation details.  */
    const static unsigned DMGL_TYPES         = (1 << 4);            /* Also try to demangle type encodings.  */
    const static unsigned DMGL_RET_POSTFIX   = (1 << 5);            /* Print function return types (when present) after function signature.  It applies only to the
toplevel function type.  */
    const static unsigned DMGL_RET_DROP      = (1 << 6);            /* Suppress printing function return types, even if present.  It applies only to the toplevel
function type. */
    const static unsigned DMGL_AUTO          = (1 << 8);
    const static unsigned DMGL_GNU           = (1 << 9);
    const static unsigned DMGL_LUCID         = (1 << 10);
    const static unsigned DMGL_ARM           = (1 << 11);
    const static unsigned DMGL_HP            = (1 << 12);            /* For the HP aCC compiler; same as ARM except for template arguments, etc. */
    const static unsigned DMGL_EDG           = (1 << 13);
    const static unsigned DMGL_GNU_V3        = (1 << 14);
    const static unsigned DMGL_GNAT          = (1 << 15);/* If none of these are set, use 'current_demangling_style' as the default. */
    const static unsigned DMGL_STYLE_MASK    =
(DMGL_AUTO|DMGL_GNU|DMGL_LUCID|DMGL_ARM|DMGL_HP|DMGL_EDG|DMGL_GNU_V3|DMGL_JAVA|DMGL_GNAT);

    const char *TARGET = "x86_64-unknown-linux-gnu";

    inline size_t get_file_size(const char * file_name)
    {
        struct stat statbuf;

        if (stat(file_name, &statbuf) < 0) {
            if (errno == ENOENT)
                cerr << "No such file: " << file_name << endl;
            else
                cout << "Warning: could not locate " << file_name << ", reason: " << strerror(errno) << endl;
        } else if (!S_ISREG(statbuf.st_mode))
            cout << "Warning: " << file_name << " is not an ordinary file." << endl;
        else if (statbuf.st_size < 0)
            cout << "Warning: " << file_name << " has negative size, probably it is too larget." << endl;
        else
            return statbuf.st_size;

        return static_cast(-1);
    }

    inline void set_default_bfd_target(void)
    {
        /* The macro TARGET is defined by Makefile.  */
        const char *target = TARGET;

        if (!bfd_set_default_target(target))
            cerr << "can't set BFD default target to " << target << " : " << bfd_errmsg(bfd_get_error()) << endl;
    }

} // namespace

struct AddressLine::InternalData
{
    InternalData() :
        syms(NULL),
        abfd(NULL),
        pc(0),
        filename(NULL),
        functionname(NULL),
        found(FALSE),
        target(NULL),
        path_pointer(NULL)
    {
    }

    ~InternalData()
    {
        if (syms != NULL)
            free(syms);

        if (abfd != NULL)
            bfd_close(abfd);
    }

    asymbol ** syms;
    bfd *abfd;
    bfd_vma pc;
    const char *filename;
    const char *functionname;
    unsigned line;
    bfd_boolean found;
    const char *target;
    const char *path_pointer; // pointer to the path's internal data, used in c interface.
    string path;
};

AddressLine::AddressLine() : data(new InternalData)
{
}

AddressLine::~AddressLine() = default;

void AddressLine::set_path(const string &_p)  // public
{
    data->path = _p;
    data->path_pointer = data->path.c_str();
}

bool AddressLine::init()                                  // public
{
    if (get_file_size(data->path_pointer) < 1) {
        cerr << "Failed to get file size.n";
        return false;
    }

    set_default_bfd_target();

    data->abfd = bfd_openr(data->path_pointer, data->target);

    if (data->abfd == NULL)
    {
        cerr << "Failed to open the file: " <path << endl;
        return false;
    }

    /* Decompress sections.  */
    data->abfd->flags |= BFD_DECOMPRESS;

#if 0
        if (bfd_check_format(data->abfd, bfd_archive)) {
            cerr <path << ": cannot get addresses from archive" << endl;
           return false;
        }
#endif

    asection *section;
    char **matching;

    if (!bfd_check_format_matches(data->abfd, bfd_object, &matching)) {
        cout << "Warning: check bfd format. "<< data->abfd << " : " << bfd_errmsg(bfd_get_error());

        if (bfd_get_error() == bfd_error_file_ambiguously_recognized)
        {
            list_matching_formats(matching);
            free(matching);
         }

         return false;
    }

    return slurp_symtab();
}

bool AddressLine::slurp_symtab()
{
    long storage;
    long symcount;
    bfd_boolean dynamic = FALSE;

    if ((bfd_get_file_flags(data->abfd) & HAS_SYMS) == 0)
        return false;

    storage = bfd_get_symtab_upper_bound(data->abfd);

    if (storage == 0) {
        storage = bfd_get_dynamic_symtab_upper_bound(data->abfd);
        dynamic = TRUE;
    }

    if (storage < 0)
    {
        cerr <path << " : " <abfd) << " : " << bfd_errmsg(bfd_get_error()) << endl;
        return false;
    }

    data->syms = (asymbol **) malloc(storage);
    if (dynamic)
        symcount = bfd_canonicalize_dynamic_symtab(data->abfd, data->syms);
    else
        symcount = bfd_canonicalize_symtab(data->abfd, data->syms);

    if (symcount < 0) {
        cerr <path << " : " <abfd) << " : " << bfd_errmsg(bfd_get_error()) << endl;
        return false;
    }

    return true;
}

#define xvec_get_elf_backend_data(xvec) ((const struct elf_backend_data *) (xvec)->backend_data)
#define get_elf_backend_data(abfd) xvec_get_elf_backend_data((abfd)->xvec)
// #define bfd_get_flavour(abfd) ((abfd)->xevc->flavour)

SourceInfo AddressLine::get_source_info(size_t address)   // public
{
    SourceInfo si;
    const struct elf_backend_data * bed;
    data->pc = address;

    if (bfd_get_flavour(data->abfd) == bfd_target_elf_flavour
        && (bed = get_elf_backend_data(data->abfd)) != NULL
        && bed->sign_extend_vma
        && (data->pc & (bfd_vma) 1 <s->arch_size - 1)))
        data->pc |= ((bfd_vma) - 1) <s->arch_size;

    data->found = false;
    bfd_map_over_sections(data->abfd);

    if (data->found) {
        while (1) {
        const char *name;
        char *demangled_name = NULL;

        name = data->functionname;

        if (name == NULL || *name == '')
            name = "??";
            demangled_name = bfd_demangle(data->abfd, name, DMGL_ANSI | DMGL_PARAMS);

            if (demangled_name != NULL)
                name = demangled_name;

            si.function = name;

            if (demangled_name != NULL)
                free(demangled_name);

            si.file = ((data->filename != NULL) ? data->filename : "??");
            si.line = data->line;
            data->found = bfd_find_inliner_info(data->abfd, &data->filename, &data->functionname, &data->line);

            if (!data->found)
                break;
        }
    }

    return si;
}

void AddressLine::bfd_map_over_sections(bfd *abfd)
{
    asection *sect;
    unsigned int i = 0;

    for (sect = abfd->sections; sect != NULL; i++, sect = sect->next)
        find_address_in_section(abfd, sect);

    if (i != abfd->section_count)    /* Debugging */
        abort ();
}

void AddressLine::find_address_in_section(bfd *abfd, asection *section)
{
    bfd_vma vma;
    bfd_size_type size;

    if (data->found)
        return;

    if ((bfd_get_section_flags(abfd, section) & SEC_ALLOC) == 0)
         return;

    vma = bfd_get_section_vma(abfd, section);

    if (data->pc < vma)
         return;

    size = bfd_get_section_size(section);
    if (data->pc >= vma + size)
         return;

    data->found = bfd_find_nearest_line(abfd,
    section, data->syms, data->pc - vma, &data->filename, &data->functionname, &data->line);
}

void AddressLine::list_matching_formats(char **p)
{
    cerr <path << ": Matching formats:";
    while(*p)
        cerr << " " << *p++;
    cerr << endl;
}

I created the header file elfbfd.h. It contains the macros, type declaration and function declaration extracted from binutils for ELF file format. It is a big file and all come from binutils so I don't paste it here.

5. Set the executable file.
When the program exists, the non-released memory is in the map and so is the call stack. By using the IP in the call stack and (4), it is easy to get the file and line number, as well as the function name. But we still need to read the executable file first, that is, the running program itself. So let's look back at the pass (1). In the pass, when it detects there is a function main() in the module, it creates a new function __m_set_executable_file, and then creates a call instruction and adds this instruction to the entry block.  __m_set_executable_file() will eventually call AddressLine::set_path(). __m_set_executable_file() receives the argv[] arguments passed to main and argv[0] is the name of the program. It also needs to get the absolute path of the program and pass this path to AddressLine::set_path().

Final thoughts

The above is the step I did in the project. There are still a lot to be done to make it more useful. There are some limitation though.
1. The pass is applied to .bc file. So one needs to compile the C source code to .bc file, runs opt to apply the pass and links the file. This may be addressed by converting it the a plugin to clang.
2. It only detects memory leak in the code that is compiled and linked by the above steps. If a library is used and is not compiled and linked as such, the memory leak in the library code won't be detected.
3. When linking, it has to link to a new library (2), (3), (4). I think this can be addressed by implementing a plugin to clang.

And note that IP is the address of next instruction. So if you pass IP directly to (4) AddressLine::get_source_info(), you will get the the line number of the next line where the function is called. I found passing IP - 1 works fine, but needs to figure out why. I think this may have something to do with the instruction length. And I don't know how it works in instruction branching.