Problem set 1 Hints

So you’re not sure how to start problem set 1! Not a problem. The problem set description is long.

One key to attacking a large problem is to divide it into smaller pieces. In this class, those pieces are often individual tests—for this pset, test001, test002, etc. Try to pass the tests in order. Make incremental progress.

test001

“You’ll want to examine the test programs to figure out what they’re doing and what output is expected.”

Here is test001.cc.

#include "m61.hh"
#include <cstdio>
// Trivial check: no allocations == zero statistics.

int main() {
    m61_print_statistics();
}

// Lines starting with "//!" define the expected output for this test.

//! alloc count: active          0   total          0   fail          0
//! alloc size:  active          0   total          0   fail          0

Now, here is a detective-style walk through the code that presents one way to pass the test. It goes very gradually—that’s the point. As you pass more tests, you will gain more familiarity with the code base, and future tests will go faster. Try to answer the following questions yourself before looking at the solutions.

Question. Which m61 functions are called by main?

Only m61_print_statistics.

Question. Given this, which m61 functions are relevant to the expected output?

Only m61_print_statistics and the functions it calls. Here is the handout m61_print_statistics and all the functions it calls:

pset1/m61.cc

/// m61_get_statistics(stats)
///    Store the current memory statistics in `*stats`.

void m61_get_statistics(m61_statistics* stats) {
    // Stub: set all statistics to enormous numbers
    memset(stats, 255, sizeof(m61_statistics));
    // Your code here.
}


/// m61_print_statistics()
///    Print the current memory statistics.

void m61_print_statistics() {
    m61_statistics stats;
    m61_get_statistics(&stats);

    printf("alloc count: active %10llu   total %10llu   fail %10llu\n",
           stats.nactive, stats.ntotal, stats.nfail);
    printf("alloc size:  active %10llu   total %10llu   fail %10llu\n",
           stats.active_size, stats.total_size, stats.fail_size);
}

Question. Does this test ever call m61_malloc or m61_free?

No.

Question. What output does the test expect?

It expects the following output, which we can read from the //! comments in pset1/test001.cc.

alloc count: active          0   total          0   fail          0
alloc size:  active          0   total          0   fail          0

Question. What output does the test generate in the handout code?

It generates this, which you can confirm by running make test001; ./test001.

alloc count: active 18446744073709551615   total 18446744073709551615   fail 18446744073709551615
alloc size:  active 18446744073709551615   total 18446744073709551615   fail 18446744073709551615

Question. How close is the output format to the expected output format?

Pretty close! All the verbatim words are right (alloc count:, active, total, fail). Just the numbers are wrong: they should be 0, but are 18446744073709551615.

Question. What is the source of the printed numbers?

The output is generated by the m61_print_statistics function through two printf statements. Looking at the format strings, we can see that the numbers are taken from an m61_statistics structure:

    m61_statistics stats;
    m61_get_statistics(&stats);

    printf("alloc count: active %10llu   total %10llu   fail %10llu\n",
           stats.nactive, stats.ntotal, stats.nfail);
    printf("alloc size:  active %10llu   total %10llu   fail %10llu\n",
           stats.active_size, stats.total_size, stats.fail_size);

That structure in turn is filled in by the m61_get_statistics function.

Question. Does that weird number have any meaning?

Why not Google it?

As this indicates, the number is 2⁶⁴−1, the largest representable 64-bit (= 8-byte) unsigned integer. Its representation in hexadecimal is 0xFFFFFFFFFFFFFFFF.

Question. Is the m61_statistics structure documented?

As the problem set says, this structure is defined and documented in m61.hh.

pset1/m61.hh

struct m61_statistics {
    unsigned long long nactive;           // number of active allocations [#malloc - #free]
    unsigned long long active_size;       // number of bytes in active allocations
    unsigned long long ntotal;            // number of allocations, total
    unsigned long long total_size;        // number of bytes in allocations, total
    unsigned long long nfail;             // number of failed allocation attempts
    unsigned long long fail_size;         // number of bytes in failed allocation attempts
    uintptr_t heap_min;                   // smallest address in any region ever allocated
    uintptr_t heap_max;                   // largest address in any region ever allocated
};

m61_print_statistics only prints the first six members.

Question. Why does m61_get_statistics produce statistics with that weird number in it?

The m61_get_statistics function overwrites its input structure with the byte 255, which equals 0xFF. This makes every 8-byte integer in the statistics structure equal 0xFFFFFFFFFFFFFFFF.

Question. How can you make the statistics have the right numbers?

Why not make m61_get_statistics initialize the statistics to zero?

memset(stats, 0, sizeof(m61_statistics));

Or, more verbosely but more clearly,

stats->nactive = 0;
stats->active_size = 0;
stats->ntotal = 0;
stats->total_size = 0;
stats->nfail = 0;
stats->fail_size = 0;
stats->heap_min = 0;
stats->heap_max = 0;

Either of these will pass test001!

test002

#include "m61.hh"
#include <cstdio>
// Total allocation counts.

int main() {
    for (int i = 0; i != 10; ++i) {
        (void) malloc(1);
    }
    m61_print_statistics();
}

// In expected output, "???" can match any number of characters.

//! alloc count: active        ???   total         10   fail        ???
//! alloc size:  active        ???   total        ???   fail        ???

Question. What does this test do?

It makes 10 calls to m61_malloc (each allocating one byte), then prints statistics. Because of the way the problem set is compiled, the malloc calls are actually calling m61_malloc instead: our m61.hh header file redefines malloc, calloc, and free to call the m61_ versions.

Question. Does this test ever call m61_malloc or m61_free?

Yes.

Question. What output is expected?

alloc count: active        ???   total         10   fail        ???
alloc size:  active        ???   total        ???   fail        ???

where the ???s are wildcards that match anything.

Question. What output is generated?

make test002; ./test002 reports:

alloc count: active          0   total          0   fail          0
alloc size:  active          0   total          0   fail          0

Question. What part of the generated output is wrong?

alloc count: total should be 10, but is 0. Everything else matches up.

Question. What is the source of the problematic part of the output?

From the stats.ntotal member of the statistics returned by m61_get_statistics.

Question. Is the meaning of that problematic output specified anywhere? What is it?

Yes, in the header:

unsigned long long ntotal;            // number of allocations, total

Question. Can this problem be solved by changing just m61_get_statistics?

No! We need to know how many allocations were made, and m61_get_statistics can’t figure that out on its own. There were 10 total allocations because there were 10 calls to m61_malloc.

Question. Can this problem be solved by changing just local variables?

No! We need to collect information in m61_malloc and then export that information in m61_get_statistics. You can’t do that with a local variable in either function—the information must be stored in a place both functions can access.

Question. Are global variables allowed in this problem set?

Yes!

Question. How can you make the statistics have the right numbers?

Introduce a global variable that counts the number of total allocations, and use that global variable to initialize the statistics in m61_get_statistics. For example:

static unsigned long long ntotal = 0;

void* m61_malloc(size_t sz, const char* file, long line) {
    (void) file, (void) line;   // avoid uninitialized variable warnings
    ++ntotal;
    return base_malloc(sz);
}

// ...

void m61_get_statistics(m61_statistics* stats) {
    memset(stats, 0, sizeof(m61_statistics));
    stats->ntotal = ntotal;
}

(The ntotal variable is marked as static because it is only meaningful to the m61 functions and should be hidden from code in other files.)

This will pass test002.

Question. Can you simplify your solution—especially for future tests—with a little advance planning?

Yes. It seems like every member of m61_statistics will require tracking in the m61_malloc family of functions. It will be more convenient to keep track of those statistics inside an m61_statistics structure, rather than as separate global variables.

static m61_statistics gstats = {0, 0, 0, 0, 0, 0, 0, 0};

void* m61_malloc(size_t sz, const char* file, long line) {
    (void) file, (void) line;   // avoid uninitialized variable warnings
    ++gstats.ntotal;
    return base_malloc(sz);
}

// ...

void m61_get_statistics(m61_statistics* stats) {
    *stats = gstats;   // or memcpy(stats, &gstats, sizeof(gstats))
}