CS 241 — Winter 2022 — Assignment 10

Assignments for CS 241
-->← Assignment 9 Assignment 10
Wednesday, Mar 30th at 5:00 pm Tuesday, Apr 5th at 11:59 pm
P1P2P3P4Bonus

In Part 1 of Assignment 10, you will implement your own memory allocators that can be used in any C or C++ program. These must be written in C++; there is no Racket option.

Assignment 10 also has a bonus Part 2 in which you will implement a linker for MERL files. You will have the choice to use C++ or Racket as usual.

Marmoset Notes

For each assignment question, some libraries are provided as C++ object files (or compiled Racket modules for the A10Bonus Racket option). You are not required to submit these libraries. Submit your main program, and Marmoset will provide the libraries for you.

For this assignment (not including the bonus), secret tests are worth 60% of the Marmoset test marks.

Restrictions

In Problems 1 through 4, there are various restrictions you are expected to follow. This is because this part of the assignment is about low level programming: implementing your own dynamic memory allocator when you have nothing but a big block of memory at your disposal. Using high level features like the existing C/C++ allocators or STL containers defeats the purpose of the assignment.

Marmoset tries to check some of these restrictions, and will reject your program if it finds any violations, but it is not perfect. We ask that you try to follow the restrictions in good faith, and do not assume that something is allowed just because Marmoset does not reject it.

We will perform some additional manual review of the submissions after the deadline to ensure no restrictions are violated, and marks will be deducted at our discretion if violations are found.

Please report any issues with Marmoset's checking of the restrictions (e.g., if a valid program is mistakenly rejected).

Part 1: Memory Allocation

The goal of this part of the assignment is to write your own memory allocator, using the free list algorithm. We will start with two warm-up problems to get you used to working with memory at a low level. Then you will write a memory allocator that only allocates fixed-size blocks. Finally, you will write a full-fledged memory allocator that handles variable-size blocks.

In this part of the assignment (Problems 1 to 4) we will be using 8 bytes (64 bits) as the size of a word.

This is because we will be working on the Linux servers, which are 64-bit computers and use 64-bit memory addresses. For most of the course, we have been using 4 bytes (32 bits) as the size of a word, but this is just because we have been working with a 32-bit MIPS machine. Remember that the size of a word depends on the machine.

Problem 1 — 30 marks of 150, 18 secret marks (filename: wrapper-p1.cc)

We have provided a header a10p1.h and an object file a10p1.o that provide a function

int64_t *arena()   // We are using int64_t instead of int in this part of the assignment, 
                   // so that our numeric values are the same width as our pointers (64 bits)

The arena function returns the address of the beginning of a block of RAM that may be used for dynamic memory allocation. Initially, the size of the arena (in bytes) is stored in the first word. That is, the expression *arena() returns the size of the arena, which will not be less than 223 or greater than 231. You may also assume it is a multiple of 8.

Aside from the first word, which contains the size of the arena in bytes, you can assume that every word in the arena is initialized to 0.

In C++, using the provided wrapper code as a starter, write a function wain(a,n) where a is the address of the first of n 64-bit words of RAM. Each word will contain a number between 1 and 1,000,000. Your wain function should return the number of times that the most frequent element occurs.

Restrictions

You must solve this problem in linear time (i.e., O(n) where n is the size of the input array). Otherwise, you will likely fail some of the Marmoset tests.

Apart from the stack space occupied by ordinary program variables, and the heap space occupied by user input, all of the memory your program uses (i.e., for arrays, etc.) must come from the memory returned by arena.

More specifically, the code you write is not permitted to use new, delete, malloc, calloc, realloc, free, or any STL containers, or any other function that accomplishes a similar purpose to these.

You are allowed to use a few integer, pointer and char variables for things like important values or addresses, loop counters, etc. but you should not store large amounts of data using these variables. In particular, do not create any array variables (e.g. int64_t array[1000000];).

You are not allowed to #include anything other than the headers already included by the starter code, and the header <cstdio> (C style input/output). You do not need <cstdio> at all for this problem, but Marmoset accepts it, mostly for consistency with Problem 2 (where you are allowed to use it for I/O if you prefer it to C++ streams). Perhaps you can use it for debugging if you are a fan of printf.

Testing

You must download the a10p1.o library and pass it to the compiler along with the starter code:

g++ -g -std=c++14 -Wall wrapper-p1.cc a10p1.o -o main-p1

This library is compiled for use on the Linux student environment, and may not work on your local computer.

Hint: As you may remember from working with arrays in WLP4, if p is a pointer and i is an integer, then p[i] is equivalent to *(p+i). You can treat the pointer returned by arena as if it is a very large array. However, note that the size stored in arena()[0] is the size of the array in terms of bytes, not in terms of elements. Each element is a 64-bit integer, so it takes up 8 bytes.

Problem 2 — 30 marks of 150, 16 secret marks (filename: wrapper-p2.cc)

In this problem, we will work with a different method of allocating memory. The following procedures are available in the header a10p2.h and object file a10p2.o:

//returns the address of a pair of words, initialized to a and b respectively, or 0 if no memory is available
int64_t *cons(int64_t a, int64_t *b)

//returns the first element of the pair whose address is p
int64_t car(int64_t *p)

//returns the second element of the pair whose address is p
int64_t *cdr(int64_t *p)

//sets the first element of p to the value v and returns p
int64_t *setcar(int64_t *p, int64_t v)

//sets the second element of p to the value v and returns p
int64_t *setcdr(int64_t *p, int64_t *v)

//deletes the pair whose address is p, or does nothing if p is null
void snoc(int64_t *p)

While the pairs returned by cons can be used for anything, the intended use is to construct linked lists, where the first element of a pair is an integer value, and the second is a pointer to the rest of the list. Those who learned Racket in first year might know the functions car and cdr (which are named this way for historical reasons) as first and rest.

Using the provided wrapper code, write a C++ program that reads an entire input file from standard input, and writes the file twice to standard output. The function wain's two arguments will both be zero for this question and can be ignored. You may assume that the input is no more than 100,000 bytes. Your wain function should return the number of bytes successfully read from standard input.

Restrictions

Your program must not leak memory. In other words, you must snoc everything that you cons.

Apart from the stack space occupied by ordinary program variables, and the heap space occupied by user input, all of the memory your program uses must come from the memory returned by cons.

More specifically, the code you write is not permitted to use new, delete, malloc, calloc, realloc, free, or any STL containers, or any other function that accomplishes a similar purpose to these.

You are allowed to use a few integer and pointer variables (including char variables) but you should not store large amounts of data using these variables. In particular, do not create any array variables and do not create any string variables.

You are not allowed to use the seekg, unget, or putback functions from std::istream. These functions allow you to "reset" an input stream and read from it a second time. Any functions with similar behaviour are also not allowed. You should solve this problem by using the memory returned by cons to store the input.

You are not allowed to #include anything other than these headers: <iostream>, <cstdio>, <cstdint>, and "a10p2.h". The starter code includes <iostream> by default, but you can decide whether you want to use C++ streams or C functions for input reading.

Testing

You must download the a10p2.o library and pass it to the compiler along with the starter code:

g++ -g -std=c++14 -Wall wrapper-p2.cc a10p2.o -o main-p2

This library is compiled for use on the Linux student environment, and may not work on your local computer.

The following two commands should produce the exact same result in outfile (assuming your executable is called main-p2):

./main-p2 < infile > outfile
cat infile infile > outfile 

Hint: You will probably want to use the std::noskipws I/O manipulator when reading input. If you have been doing the assignments in Racket and your C++ is rusty, you may find the following review of input reading techniques in C++ helpful for this problem. Although the memory returned by cons only stores integers and pointers, the input and output will be characters; you may need to use casting to deal with this.

Problem 3 — 40 marks of 150, 26 secret marks (filename: cons.cc)

Write C++ procedures to implement the functionality provided by a10p2.o using the more primitive library a10p1.o.

Specifically, the arena function produces the address of a large pool of memory. Your implementation of cons will give the client code memory addresses from this pool, and your implementation of snoc will return memory to this pool. You must also implement the other functions provided by a10p2.o.

In order for your solution for this problem to earn credit, all operations must run in constant time. Moreover, you must make maximally efficient use of space, so that as large a number of pairs as possible can be allocated (in particular, this means no size fields).

Restrictions

Apart from the stack space occupied by ordinary program variables, all of the memory your program uses must come from the memory returned by arena.

More specifically, the code you write is not permitted to use new, delete, malloc, calloc, realloc, free, or any STL containers, or any other function that accomplishes a similar purpose to these. You are allowed to store a small amount of information in program variables, but any data structures you use to organize or manage memory should be stored in the memory returned by arena.

You are not allowed to #include anything other than these headers: <iostream>, <cstdio>, <cstdint>, "a10p1.h", and "a10p2.h". While <iostream> and <cstdio> are not needed for any of the implementations, you may wish to use them for debugging. Marmoset will ignore output from your program.

Testing

To test your implementation, you can compile it along with your solution to A10P2:

g++ -g -std=c++14 -Wall wrapper-p2.cc cons.cc a10p1.o -o main-p3

To fully test your functions, you will probably want to write other programs that follow other memory allocation patterns, and verify that your code works with those programs as well as your A10P2 solution.

Hint: To get your implementation to pass type checking, you will likely need to use casting. Treating pointers as integers, or vice versa, is common in this kind of low level code. Since cons always produces a pair of words, all blocks of memory will have the same size. You can implement something similar to the free list algorithm, but without size fields or merging of free blocks.

Problem 4 — 50 marks of 150, 30 secret marks (filename: malloc.cc)

Write C++ procedures to implement the following functions, in terms of a10p1.o, using the free list algorithm:

// allocates a block of memory of at least size words (not bytes), 
// and returns the address of that memory or 0 (NULL) if memory could not be allocated.
int64_t *mymalloc(int64_t size)

// deallocates the memory stored at address.
// assumes that address contains either an address allocated by mymalloc, in which case it deallocates that memory, 
// or the value 0 (NULL), in which case myfree does nothing.
void myfree(int64_t *address)

Specifically, the arena function produces the address of a large pool of memory. Your implementation of mymalloc will give the client code memory addresses from this pool, and your implementation of myfree will return memory to this pool.

Recommendations

You should use the free list algorithm to implement mymalloc and myfree. Each block should only use one word for bookkeeping information (block size). Although mymalloc is only required to allocate a block of at least the requested size, try to minimize the difference between the amount of memory the user requests and the amount of memory taken up by the block you allocate.

You should use the "first fit" heuristic when allocating. In other words, always use the first block in the free list that is large enough to fit the requested size.

The reason for these recommendations is that Marmoset has some "stress tests" that push the limits of your memory allocator. These tests may not work as intended if another algorithm like the binary buddy system algorithm is used, if your free list implementation wastes too much space, or if your implementation follows a different allocation pattern than first fit.

Unlike the "restrictions" below, we will not deduct marks if you do not follow these recommendations. However, we cannot guarantee you will pass the Marmoset secret tests if you do not follow them, even if your alternate implementation is correct.

Restrictions

Apart from the stack space occupied by ordinary program variables, all of the memory your program uses must come from the memory returned by arena.

More specifically, the code you write is not permitted to use new, delete, malloc, calloc, realloc, free, or any STL containers, or any other function that accomplishes a similar purpose to these. You can store pointers to parts of the free list (e.g., the head or tail) as ordinary program variables, but the free list itself should be stored in the memory returned by arena, rather than some kind of external data structure.

You are not allowed to #include anything other than these headers: <iostream>, <cstdio>, <cstdint>, and "a10p1.h". While <iostream> and <cstdio> are not needed for any of the implementations, you may wish to use them for debugging. Marmoset will ignore output from your program.

Testing

To test your implementation, compile it with a10p1.o. You will need to create some kind of main program that uses your implementation.

g++ -g -std=c++14 -Wall malloc.cc a10p1.o -o main-p4

While you should develop new test cases, you may also wish to define cons and snoc in terms of mymalloc and myfree in order to reuse your A10P3 tests in A10P4.

Hint: the main difference between this problem and the previous one is that memory blocks will no longer be of a fixed size. Therefore, if you have a good implementation for P3, you should be able to use it as a starting point for P4. Be warned though that you will probably need to make quite a few changes to properly support variable-size blocks.

Click here to return to the top of the page.

Part II: Linker (Bonus)

Bonus Problem — 15 bonus marks (filename: linker.cc or linker.rkt)

Note: The public and release tests for this problem are worth 0 marks. Since this is a bonus questions, all marks are for secret tests.

In this problem, you will implement a linker that uses the linking algorithm discussed in the course for linking two MERL files.

Note that in this problem, the "word size" is 4 bytes (32 bits). In the previous problems, we used 64-bit (8-byte) words since we were working on the 64-bit Linux servers. For this problem, we are back to working with 32-bit MIPS and 4-byte words.

The linker should expect a series of command line arguments, each containing the name of a MERL file. The linker should read each of these MERL files and link them together, and output the linked MERL file to standard output as raw binary data. For example, you could invoke your linker like this:
./linker A.merl B.merl C.merl > linked.merl            (for C++)
racket linker.rkt A.merl B.merl C.merl > linked.merl   (for Racket)

Your program should link the files in order. That is, in the above examples, the code segment of the output file linked.merl should contain the code segment of A.merl, followed by the code segment of B.merl, followed by the code segment of C.merl (where all three code segments have of course possibly been modified in the course of linking). The order of entries in the MERL footer (external symbol table) does not matter, however.

If the two files being linked have overlapping label names in their exports, you should produce an error message containing the string ERROR (in all caps) to standard error and stop. It does not matter what the program produces on standard output if an error occurs. For example, if A.merl exports a label called "loop" and B.merl also exports a label called "loop", you should produce an error. This is the only error case you need to handle. You may assume that all MERL files given as input by Marmoset will be valid.

As long as standard error does not contain the string ERROR in all caps, our test scripts will ignore standard error. So, you can print your own debugging information on standard error if you want. You may assume that none of the test inputs will contain labels with ERROR in the name.

Efficiency Note

For this problem, the MERL files your linker is tested with will be relatively small. Your algorithm should be reasonably efficient, but it does not need to be optimal. For example, using a linear search to look up a label in the MERL external symbol table is fine. In fact the starter code (discussed below) essentially expects you to do this, as it does not provide efficient lookup methods for entries in the MERL footer.

Starter Code and Libraries

This question can be done using C++ or Racket. In both cases, we are providing two files: one compiled closed-source "MERL library", and one piece of starter code.

The MERL library is used to read MERL files from standard input, store them in a MERL struct for processing, and write the MERL files back out to standard output.

The starter code requires the MERL library. It handles input and output for you, and provides a main function that reads the command line arguments and passes the MERL files into a linking function. It also defines, but does not implement, a function that links two MERL files and produces a new MERL file. If you correctly implement this two-file linking function, the starter code will handle everything else (i.e., linking all the files passed on the command line in the correct order).

The starter code, by default, prints some information about the linked MERL file to standard error after linking is complete. You can remove this if you do not want to see it, but it will not interfere with the Marmoset tests, and it might be useful for debugging.

Using the starter code and MERL library is optional, but it will do a lot of the work for you.

Below are some language-specific notes.

C++ Notes

The MERL library is specified in merl.h and implemented by merl.o.

The starter code is available here: linker.cc
It requires the MERL library. Therefore, you should compile it as follows:

g++ -g -std=c++14 -Wall linker.cc merl.o
Marmoset will provide the merl.o library for you, so you do not need to submit it along with your solution. As long as your solution contains the line #include "merl.h", Marmoset will link the merl.o library for you. If you do not wish to use the provided starter code and library, simply do not include "merl.h" in your program.

Racket Notes

The Racket starter code and MERL library are available in this ZIP file: linker-racket.zip

This ZIP file contains the linker.rkt starter code as well as a folder called "compiled" containing the MERL library. This folder must be in the same place as the starter code for it to work.

The MERL library is imported with require:

(require "merl.rkt")
This may seem strange since there is no file called "merl.rkt" in the ZIP file. How it works is Racket will end up searching the "compiled" folder, finding the compiled version of the modules, and using those. This is why it is necessary to have the "compiled" folder in the right place.

When submitting to Marmoset, you do not need to submit the "compiled" folder. Just submit linker.rkt (and any other Racket files your program uses, not including the compiled MERL library). Marmoset will provide the MERL library.

The following file contains documentation and function declarations (without implementations) for the Racket version of the MERL library: merl-docs.rkt

(This file is not meant to be used in your program, it is just here as a reference for how to use the MERL library.)

Testing your Linker

You can use cs241.linkasm to create MERL files from assembly language source code. On Assignments 8 and 9, you used the .import directive to import labels from the MERL files print.merl and alloc.merl. The cs241.linkasm assembler also supports the .export directive, which lets you make labels from your file "visible" to other MERL files, meaning other MERL files can import them with .import. In addition to testing with print.merl and alloc.merl, you should create your own MERL files with different arrangments of imports and exports for testing.

A reference implementation of a MERL linker (cs241.linker) is available, and you should be familiar with how to use it from Assignments 8 and 9. However, it is not possible to simply compare your output to the reference implementation's output directly, because the order of the external symbol table entries might be different from your linker. You can test your linker using the following steps:

You can put this all in a Bash script to make testing easier.

The xxd command, or our similar course tool cs241.binview, may also be useful here to examine the binary data in a MERL file, in case you are not sure precisely where your file differs from the expected one.

Click here to return to the top of the page.