CMPT 201 – Fall 2018, Assignment 2

Due: November 16, 2018, 11:00 pm.

Weight: 10% of your final mark

Work type: Individual assignment

Objective

Your assignment is to implement a memory manager module and use it to:

 Allocate and free memory regions

 Implement a program that manages a memory map – a binary file that represents the content of the memory

Milestones

This assignment has two milestones which are to be met:

 Milestone 1: October 26th,11:pm. Submit on eSubmit a text file containing details of your plan for working on the assignment. This includes dates, algorithms, implementation ideas, and issues you anticipate facing. Name the text file A2plan.txt.

 Milestone 2: Due during your lab session on the week of Nov 5-th to Nov 9-th You must have the implementation of the memAlloc function working and you have to demo it to your lab instructor.

Memory manager:

"The essential requirement of memory manager is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when no longer needed." [https://en.wikipedia.org/wiki/Memory_management].

For more information on memory managers please read: "A memory allocator", by Doug Lea. "A Malloc Tutorial" by Marwan Burelle, is also a very informative, but it does not use the most eloquent English .

For this assignment you will create a memory manager for a simulated memory of 64 Kb.

 memory addresses and sizes are represented on 2 bytes (16 bits) and are aligned at four bytes. This implies that all memory addresses and sizes are multiples of 4.

 a chunk of memory consists of

o size – the size of the chunk of memory. It is 4 bytes more than the size of the user data space. It occupies the first two bytes of the chunk.

o user data space – used for storage

o size – the size of the chunk of memory. It occupies the last two bytes of the chunk.

NOTE: Since all memory chunks are aligned at 4 bytes, the last bit of the size will be used as a status flag to indicate if the chunk is in used or free: 1 represents in use and 0 free.

 there are 19 bins of memory chunks.

o the first 8 bins contain chunks of exact sizes: 4, 8, 12, 16, 20, 24, 28, and 32.

o the last 11 bins contain chunks of variable sizes. The size of a chunk in each bin is bounded above by: 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, and 65536 bytes respectively. Each such bin contains chunks of memory which are larger than the size limit of the previous bin, and less than or equal to their own size limit.

 each bin is implemented as a circular double linked list. The lists for the variable size bins are to be sorted in increasing order of chunk sizes. The links of a free chunk are stored in the first 4 bytes of the user data space, the forward llink first and the backward link after it.

 the headers of the bins are stored in the first 76 bytes of the memory. The header of an empty list has circular references to itself.

 initially memory is made of a single chunk of size 65460 bytes

 memory regions are allocated using a best first strategy. If no chunck of requested size is available, the smallest chunk, larger than the requested size is divided into a chunk of requested size and a left over chunk that can fit in one of the bins. If the left over chunk does not fit any of the bins, then the entire chunk is allocated.

 when a memory region is freed, first it neighbors are checked; if they are free too, the original region and the free neighbor region(s) are coalesced into a larger region. The resulting region is added to the bin into which it fits.

Specification for the memory manager module:

You must make and justify any important design decisions for your implementation, based on the following important requirements:

 memManager.h is given to supply your module with a common public interface. You must have these functions written to spec. This way we can link your module with our own test program. You may add whatever other functions you need to this module, but it must run under these conditions.

 memManager.c contains your implementation of the memory manager

 We will test your memory manager implementation under the assumption that it can handle any number of entries (as long as memory is available).

 You must implement the memory manager, test it appropriately, and then report your effort in a test report. Test your programs extensively; including automated rules for your tests.

Description of the main program:

memMapMgr.c Contains the main memory manager program which works with a given memory map.

A memory map is a binary file containing 65,536 bytes. It is an external copy of the internal memory of the memManager module. The program must be able to:

 Create the memory map of a new empty internal memory

 Import a memory map in the internal memory

 Export internal memory to an external memory map

 Allocate memory regions in a memory map

 Free memory regions in a memory map

 Print statistics of a memory map

What mode it runs in is handled from the command line, this program does not take standard input. For sanity and practice, consider using getopt for the command line manipulation.

The possible program invocations are ([] indicate a filename):

./memMapMgr –c [memory map] to create an "empty" memory map

./memMapMgr –i [memory map] to import a memory map

./memMapMgr –e [memory map] to export a memory map

./memMapMgr –s [memory map] to print statistics about a memory map

./memMapMgr –a [memory map] – b <size> to allocate a region of <size> bytes in the memory map

./memMapMgr –f [memory map] – p <address> to free a region starting at address <address>

Notes:

1. Please follow Good Programming Style document for guidelines on style. You must not add more global variables in this assignment.

2. Function documentation should follow the example provided in the header file memManager.h.

3. Some information regarding memory organization and management will be covered in class. You are encouraged to seek out information about these subjects. Make sure to reference any sources you use.

4. You should design your data structure carefully.

Packaging and Deliverables

Your tar file should contain an A2 directory which includes all files related to this assignment. In particular, the A2 directory should contain:

 README a text file explaining the content of each file you have included in the directory and the usage of your submission

 makefile, in which make all produces all executables as you described in the README file

 memManager.h, memManager.c, memMapMgr.c and any other source files you might have created.

 design.txt a design document that describes the design decisions you made. The design document is supposed to record the important decisions you made about what had to be done (analysis) and how to do it (design). In particular, it should contain the reasons for why you made your decisions. Part of your design document will be the issues list, which identifies the issues that you encountered during the assignment, whether resolved or not, and how you resolved those that were resolved.

 Test, a directory containing a collection of your test files, which also must contain a testing report in a text file called testing.txt, describing what and how you tested. We want to be able to easily run the (highest level at least) tests that you ran, so be sure to automate their use in your makefile.

Your submission must only include source files and documentation files. Do not include any executable, object or core files.

You are expected to meet normal coding standards.

1. Packaging:

 makefile must work perfectly, so that:

 all executables are created when make all run

 A2.tar.gz tarball is created when make A2.tar.gz run

 Code must compile with no avoidable warnings under -Wall. We expect to see your makefile using this flag when compiling. Marks will be deducted if it does not.

2. Design

 Were design decisions documented?

 Was a coherent design approach attempted and how well did it work?

3. Coding:

 Produces reasonable output, even with unreasonable input (i.e., exits with error,warns about problems). Yes, that means you must check the input for correctness.

 Prints out warnings upon detection of problems (i.e., "Couldn't allocate memory !").

 Marks will be deducted for significant coding errors, such as:

Not checking the return code where it should be checked.

Not matching the specifications.

Failure to document a non-obvious loop.

4. Testing Strategy:

 Any programs (source code) used in order to test programs must be included. We expect you to submit the tests you used and explain why you believe them to be a satisfactory test of your program.

5. Style:

 All source files must have a header comment box giving the usage information and purpose of the program.

 All additional functions must have function information and purpose documented (put such documentation with the prototype of the function), as well as having the code documented internally.

 "Bad" documentation (spurious, misleading or just plain wrong) will be penalized.

Submission: Your compressed tar file will be submitted through esubmit.

Marking Scheme

The following marking scheme will be used for this assignment:

ITEM

MARKS

Milestone 1

5

Milestone 2

10

Packaging – module has correct structure (README, makefile, source files, Test directory, no extra files) , tarfile extracts properly, …etc.

3

memMapMgr.c compiles and runs

4

makefile:

 make all

 executable generated

 testing targets

3

memManager module and memMapMgr pass our tests

60

Module testing strategy, testing.txt, test documentation

5

Module and program documentation, design.txt, coding style

5

Program design, good program structure, no new global variables, use of multiple files, error checking (insufficient memory, files, …etc.), etc

5

TOTAL

100