Written by Julie Zelenski
This is your first foray into the nitty-gritty of systems program. The good news is there is not a particularly large amount of code to write and it doesn't involve any tricky algorithms. Past students have told us the most daunting issues were getting started in the first place and keeping track of the big picture: which data is where, how to access it, and how the parts relate. So take a deep breath, spend time up front to get oriented, ask questions, draw pictures, and poke around in gdb to be sure your understanding of the big picture is solid before tackling the code. Jump to the FAQ and read the question about the distinction in the two kinds of addresses being manipulated as an important bit of advice.
Here is a recommended plan of attack when ready to start coding:
Symbols
harvest_symbols.find_symbol to match symbol by address. With a correctly written comparator, qsort and bsearch work together like a dream.
Namelist
No coding for this step (we provide namelist pre-written), but stop here and use namelist to thoroughly vet your symbols functions, especially lookup by address. It will be much easier to find and fix bugs here than having to hunt them down while working on leak detector.
Leak detector
lmalloc.c to understand the lay of the landAny address just refers a location in memory, but knowing what that address represents and how it relates to other addresses can be critical. In this program, there are two distinct kinds of addresses being manipulated: symbol addresses and heap block addresses. First consider the symbol addresses. A symbol, e.g. main, occupies a range in memory where its compiled instructions are placed. Use objdump -d leaky to disassemble the executable. Find main in the disassembly listing and look at the addresses along the left side. Each address corresponds to an instruction of the main function. All of those instructions together form the range for the main symbol. The symbol table in an ELF file stores information about each symbol, including its name and address range. Use nm leaky to dump the symbol table and look for the entry for main and verify it has same address you saw in the objdump listing. The namelist program searches the symbol table to find the entry whose range encloses a target address. Now consider how these symbol addresses relate to an executing program. A symbol address is the address of an instruction, located within the text (code) segment of the executing program. The return address stored on the stack by a call instruction is also the address of the instruction. If you look up return address to find its match in the symbol table, you get the name of the function it corresponds to. The address range for a function symbol and the return addresses being read from the stack are the same kind of thing: address of an instruction.
The leak detector is also tracking a different kind of address: addresses that correspond to heap blocks. These are addressees returned by a a call to malloc and the leak detector tracks these addresses to confirm that they are later freed. These are address of data, located with the heap segment of the executing program. The address of the heap block is not a symbol address and it not expected to be found within a symbol address range nor will it match any return addresses found on the stack.
Nothing good comes from conflating the two kinds of addresses, so take the time to understand the difference and save yourself much headache and heartache.
Pro tip: gdb is wise to symbol addresses. Printing a pointer usually just prints the address, but if that address is within the range of a known symbol, gdb will also include a annotation with the symbol name and offset. The gdb run shown below prints two different addresses. gdb finds a match for the first address within the symbol table, the second one is not a match and gets no annotation.
(gdb) p (void *)0x400730
$3 = (void *) 0x400730 <singleton+11>
(gdb) p (void *)0x80329c
$4 = (void *)0x80329c
Asking gdb to print an address can be a quick way to validate whether that address lies within the range of a symbol. Pretty neat!
uintptr_t. This type is declared in <stdint.h> as an unsigned long guaranteed to have sufficient range to store any address. This type is intended for addresses that you intend to manipulate numerically, it is it is compatible with other numeric types, but it is not a pointer type and cannot be dereferenced. The symbols module, namelist program, and leak detector manipulate symbol addresses solely as numbers -- the addresses are never dereferenced or otherwise treated as pointers so uintptr_t is an appropriate choice to standardize on. Starting with a thoughtful choice of whether to declare an address as numeric type versus pointer type will lead to fewer conversions later and cleaner code.malloc call is sure to be a lot of trouble! Do your initial testing using the cpp approach as it only wraps the explicit calls from the client program which limits the potential for havoc.myth to avoid any surprises from platform-dependent discrepancies.Time spent. The leak detector is new this quarter, so we don't have any historical data on yet. It does share a lot with the assignment used in previous quarters, for which the students self-reported this amount of time spent:
Use the readelf tool. For example, to verify that you are correctly accessing the section headers, use readelf -S to dump the list of section headers and compare its entries to those your code is finding or use readelf -s to list the contents of the symbol table. By using readelf, you will learn there are some surprising entries (such as the first section header or symbol containing all zero fields), that might have otherwise had you wondering if your code was malfunctioning.
When dynamically allocating memory, it is desirable that the memory be "right-sized", but sometimes you won't know until after you've finished processing what the right size is. To get around this, consider adopting an idiom used in assignments 1 & 2: use the stack for cheap temporary storage of maximum-size, fill it, and copy the used part to dynamically-allocated memory of the correct size when the size is known. There is no pre-determined max on the number of symbols for any ELF file, but once you have found the symtab section header of a particular file, you will know the number of symbols it contains, of which only some will fit the required criteria.
Yes! You are strongly encouraged to decompose the longer tasks into smaller helper functions that are used internally. However, you should not change the public interface of the symbols module.
The strip utility (see man page) will destructively modify an object file to discard symbols. It does this by removing the entire symbol table section, both the section data and section header. There is no way to reverse/unstrip, but you can compile again to regenerate the object file with its symbol table intact. First make clean to discard any existing build products and make anew.
Yes, in lmalloc.c only. Our prohibition against global variables is relaxed for this module as it needs to maintain persistent state across function calls for which neither stack nor heap is appropriate. It is allowable to use global state to track in-use blocks.
There is a cap on the number of simultaneously in-use blocks that can be tracked. The leak detector sets aside a fixed amount of space for the in-use list and if that space is exhausted, the excess blocks go untracked. Programs can allocate and deallocate many more blocks during the program lifetime without running into the cap just as long as there is never more than maximum number of blocks simultaneously in-use. The constant of 100K in-use given in starter will cover most ordinary programs. The total number of loss records depends on how much consolidation can be done on the leaks when summarizing. If each leak is unique, the number of loss records would be same as leak count, but in practice, they will be consolidated into a tiny fraction. A client program that creates 100K leaks, easy, but 100K leaks each coming from a distinct code path of its own, not same as any others? That's some crazy code. We promise to not test on a program with more than 50K loss records. In fact, setting your cap to a number much, much lower would have no visible effect on any reasonable program.
A program that does have more than 100K blocks in-use at one time or more than 50K loss records may have an erroneous leak report, i.e. miss reporting a leak due to block going untracked or miss a loss record from the report. However, leak detector (both ld and cpp) should run without error/assert/crash on any correct client program, even one that makes a ridiculous number of allocation requests.
No. A linear search to find an entry in the in-use array definitely bogs down the leak detector as N gets large. This is expected. Switching to bsearch may seem appealing, but given that the in-use array is constantly being updated, the work to keep it in sorted order negates much of the benefit of the efficient search. Keep it simple and unsorted and use good old lfind and you'll be just fine.
qsort from my wrapper functions seems to blow out my stack. From gdb, I can see my code is 4000 calls deep into an endless qsort->malloc->qsort->malloc cycle. What gives?In certain situations (particularly when sorting large array with large elem size), qsort can make its own call to malloc/free internally -- surprise! Consider the consequence this can have: if you call qsort from your malloc wrapper and that qsort tries to malloc memory, it re-enters into your malloc wrapper, which tries to call qsort, which tries to malloc memory.... and you can see where this is going. The easiest fix is to heed our advice above and don't sort. Our recommendation is not specifically about avoiding this problem, it more that the sort is not worth it. Keeping the in-use array sorted requires an expensive update on every change (e.g. re-sort or a sorted insert/remove). Each of the operations that requires a search also does an update, so there is little benefit in providing a fast search if is always coupled with a slow update anyway. If you insist, you could turn off collecting before qsort and turn back on after to avoid the cycle. This will allow you to confirm for yourself that the performance of keeping sorted is disappointing rather than take our word for it. :-)
By return address. Matching by return address guarantees that allocations being consolidated are on the same exact code path, not just coming from somewhere within the same function. If there are two distinct calls to malloc within the binky function, both return addresses will be within the address range for the binky symbol, but the return point is different and these leaks should not be consolidated. These two allocations represent two distinct loss records.
The callstack should start at the allocation function (malloc/calloc/realloc/free wrapper) and stop after main or after DEPTH total frames (DEPTH is set to 10 in the starter code), whichever comes first. Similarly, when comparing two callstacks for possible consolidation into one loss record, you only need to consider at most DEPTH frames starting from the allocation function. Depending on where you call backtrace() you may have to adjust the callstack a bit to elide evidence of your helper functions. Sanity/grading require your callstack to cover the sequence from wrapper function to main (or stop after DEPTH), no more, no less. If the executable file has been stripped, you won't be able to identify main, so in that case just print the entire callstack (or at most DEPTH frames of it).
A buggy client program will likely crash the leak detector. You are not expected to devise handling to detect or prevent this, nor will we test on such buggy programs.
Your wrapper functions should track/report on every allocation event that they observe. For the cpp version you need to anticipate the possibility of mismatched events, as you may hear about allocation without free or vice versa. The leak report from the cpp version may be a bit erroneous in those situations (i.e. could miss reporting a leak, or report a block as leaked that was freed). However, leak detector (both ld and cpp) should run without error/assert/crash on any correct client program.
Some addresses may not have a matching symbol in the symbol table, such as symbols in dynamically-linked libraries or selectively stripped symbols. This is not an error, nor cause for alarm. Print those addresses normally and instead of identifying with symbol name, simply label as <unknown>. If the entire executable is stripped (i.e. has no symbol table at all), all addresses in the backtrace will be labelled <unknown>.
valgrind --leak-check=full?Yes. Your leak report from the ld-wrapped executable and Valgrind report from regular executable should match in terms of byte/block counts per loss record and total counts. Note that Valgrind divides leaks into categories of directly/indirectly/reachable, but we make no such distinctions-- any block that was allocated and not freed is considered "lost". To get a Valgrind leak report, remember to run Valgrind on the unadulterated programs (with no leak detection). Attempting to run your leak detector under Valgrind has interference due to both your code and Valgrind trying to interpose on the heap, so don't do that.
cpp-wrapped executable versus the ld-wrapped?The ld version wrap all calls to malloc/free, including allocation that is hidden with library functions such as strdup or fopen whereas the cpp version is only able to wrap calls that are explicit in the client program. If a block's allocation was wrapped and deallocation not wrapped or vice versa, the cpp leak report can have have erroneous/missing entry for that block.
To add a client program:
myprogram.c file with the desired program. hg add myprogram.c to add the file to your repo.myprogram to the names listed for LM_PROGS.Now myprogram is a part of your project and make will build it. Try adding your reassemble.c for a fun stress test!